[X86] Rewrite how X86PartialReduction finds candidates to consider optimizing.
authorCraig Topper <craig.topper@gmail.com>
Sun, 31 May 2020 19:39:14 +0000 (12:39 -0700)
committerCraig Topper <craig.topper@gmail.com>
Sun, 31 May 2020 19:53:01 +0000 (12:53 -0700)
commit8abe830093f65a0fc6ba398ee1786d4d96607fdf
tree52a6b7dce2564243255da79ad728a37f01fe51cf
parent22e50833e9564f6be75fcbbabe9d75ca745e778d
[X86] Rewrite how X86PartialReduction finds candidates to consider optimizing.

Previously we walked the users of any vector binop looking for
more binops with the same opcode or phis that eventually ended up
in a reduction. While this is simple it also means visiting the
same nodes many times since we'll do a forward walk for each
BinaryOperator in the chain. It was also far more general than what
we have tests for or expect to see.

This patch replaces the algorithm with a new method that starts at
extract elements looking for a horizontal reduction. Once we find
a reduction we walk through backwards through phis and adds to
collect leaves that we can consider for rewriting.

We only consider single use adds and phis. Except for a special
case if the Add is used by a phi that forms a loop back to the
Add. Including other single use Adds to support unrolled loops.

Ultimately, I want to narrow the Adds, Phis, and final reduction
based on the partial reduction we're doing. I still haven't
figured out exactly what that looks like yet. But restricting
the types of graphs we expect to handle seemed like a good first
step. As does having all the leaves and the reduction at once.

Differential Revision: https://reviews.llvm.org/D79971
llvm/lib/Target/X86/X86PartialReduction.cpp
llvm/test/CodeGen/X86/madd.ll
llvm/test/CodeGen/X86/sad.ll