This is an archive of the discontinued LLVM Phabricator instance.

[X86] Rewrite how X86PartialReduction find candidates to consider optimizing.
ClosedPublic

Authored by craig.topper on May 14 2020, 3:07 PM.

Details

Summary

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.

Diff Detail

Event Timeline

craig.topper created this revision.May 14 2020, 3:07 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 14 2020, 3:07 PM
Herald added a subscriber: hiraditya. · View Herald Transcript

Fix accidental duplicate change flag variable.

I think this is ok, but it's hard to tell what might go wrong in the matching. Do we have enough negative tests in place for this analysis?

llvm/lib/Target/X86/X86PartialReduction.cpp
123

Either we still need a parent block check here or this always true comparison should be removed.

297–303

its -> it is

298

if find -> if we find?

342

typo - pyramid

354

its -> it is

406

its -> it is

craig.topper marked an inline comment as done.May 29 2020, 12:02 PM
craig.topper added inline comments.
llvm/lib/Target/X86/X86PartialReduction.cpp
123

There's a shadowing issue here. There are two BOs and I was trying to compare their parents. But obviously only one is in scope.

Address review comments.

Still need more negative tests. And probably more tests involving single use phis.

spatel accepted this revision.May 31 2020, 7:52 AM

LGTM - probably still want to make sure there's good enough negative test coverage, but that is true even before this patch.

llvm/lib/Target/X86/X86PartialReduction.cpp
406

grammar nit still here

This revision is now accepted and ready to land.May 31 2020, 7:52 AM
This revision was automatically updated to reflect the committed changes.