[LoopInterchange] Support reductions across inner and outer loop.
ClosedPublic

Authored by fhahn on Feb 13 2018, 9:37 AM.

Details

Summary

This patch adds logic to detect reductions across the inner and outer
loop by following the incoming values of PHI nodes in the outer loop. If
the incoming values take part in a reduction in the inner loop or come
from outside the outer loop, we found a reduction spanning across inner
and outer loop.

With this change, ~10% more loops are interchanged in the LLVM
test-suite + SPEC2006.

Fixes https://bugs.llvm.org/show_bug.cgi?id=30472

Diff Detail

Repository
rL LLVM
fhahn updated this revision to Diff 144369.Apr 27 2018, 10:28 AM
fhahn edited the summary of this revision. (Show Details)

Rebased, simplified and moved parts to D46198. This patch now only contains the code to detect reduction PHIs across inner and outer loops.

fhahn updated this revision to Diff 151723.Jun 18 2018, 9:01 AM

Move PHI handling for reductions across inner and outer loop to this patch from D46198 and add an additional test case

fhahn added a comment.Jul 24 2018, 9:36 AM

ping. I would very much appreciate any feedback on the overall approach of following LCSSA nodes and classification of PHI nodes across inner & outer loop. Maybe there is some existing infrastructure for that, which I missed?

ping

@efriedma @hfinkel ?

Maybe you can try to write a RFC to llvm-dev

fhahn added a comment.Aug 14 2018, 4:16 PM

Maybe you can try to write a RFC to llvm-dev

I would be happy to write something, but I am not sure if that would make it easier to review this.

I think it is a fairly small change (thanks to Eli reviewing some patches leading up to this :)) and it would be great to get some feedback on whether this approach makes sense overall.

efriedma added inline comments.Aug 30 2018, 3:40 PM
lib/Transforms/Scalar/LoopInterchange.cpp
829 ↗(On Diff #151723)

Given you're deleting this, is there some check that disallows interchanging if a PHI is a reduction in the outer loop, but not the inner loop? Something like:

for( int i=1;i<N;i++) {
  for( int j=1;j<N;j++) {
    A[i][j]++;
  }
  X += j;
}
1506 ↗(On Diff #151723)

one kind?

1521 ↗(On Diff #151723)

Checking isa<PHINode>() here seems sort of confusing... is this supposed to be checking for a PHI node from the outer loop? If so, is there some guarantee it isn't a PHI node from somewhere else?

Thanks Eli!

lib/Transforms/Scalar/LoopInterchange.cpp
829 ↗(On Diff #151723)

Right! We should keep the check and could just not add PHIs across inner and outer loop there I think

1521 ↗(On Diff #151723)

Yeah, it seems like inner loop reductions are not handled properly to start with. I will look into that first. It might be helpful to keep track of reduction/induction phis after the initial checks and use that info here (and other places, rather than recomputing)

fhahn planned changes to this revision.Aug 31 2018, 12:26 PM

How this patch now interacts with LoopInterchange as LoopPass?

fhahn added a comment.Sep 28 2018, 3:12 AM

How this patch now interacts with LoopInterchange as LoopPass?

The change to being a loop pass should not really impact this patch. It needs a small change to work with the preserved LCSSA phis now (which I have locally), but before updating the patch, I need to find some time to improve the PHI handling in general and address Eli's comment properly.

fhahn updated this revision to Diff 168824.Oct 9 2018, 10:20 AM

Updated based on D53027, to keep sets PHIs that are part of inner loop only and across the inner and outer loop. This makes the checks during transform trivial. It also ensures that we do not deal with unclassified PHIs.

fhahn marked 3 inline comments as done.Oct 9 2018, 10:23 AM

Sorry for the delay Eli! I've restructured the code a bit to fix inner loop only reductions (D53027) and to keep 2 sets for reduction PHIs we can use to find out which kind of PHI we are dealing with.

lib/Transforms/Scalar/LoopInterchange.cpp
1521 ↗(On Diff #151723)

The code now just checks OuterInnerReductions and InnerReductions.

fhahn updated this revision to Diff 171961.Wed, Oct 31, 10:39 AM

Updated after removing support for inner loop only reductions in D53027. The code is now slightly simpler. What do you think?

fhahn added inline comments.Wed, Oct 31, 10:41 AM
lib/Transforms/Scalar/LoopInterchange.cpp
829 ↗(On Diff #151723)

With the new structure, those kinds of loops are ruled out, because reductions in the outer loop need to have a corresponding reduction in the inner loop. I've added test/Transforms/LoopInterchange/outer-only-reductions.ll, which should show this case.

fhahn added a comment.Wed, Nov 7, 9:11 AM

ping. Eli it would be great if you could have another look now that the patch removing support for inner loop only reductions is committed and this patch is simpler.

efriedma added inline comments.Wed, Nov 7, 1:40 PM
lib/Transforms/Scalar/LoopInterchange.cpp
689 ↗(On Diff #171961)

I think "PHI.getNumIncomingValues() == 2" must be true? If it weren't true, it would imply the loop header had more than two predecessors (and I think you disallow that elsewhere).

fhahn updated this revision to Diff 173144.Thu, Nov 8, 4:19 AM

Turned check into assertion, added a comment explaining the if (!InnerLoop) {} block and another comment to findInductionAndReductions.

fhahn marked an inline comment as done.Thu, Nov 8, 4:20 AM
fhahn added inline comments.
lib/Transforms/Scalar/LoopInterchange.cpp
689 ↗(On Diff #171961)

Yep, I turned it into an assertion.

This revision is now accepted and ready to land.Thu, Nov 8, 11:28 AM
This revision was automatically updated to reflect the committed changes.
fhahn marked an inline comment as done.
fhahn added a comment.Thu, Nov 8, 1:51 PM

Thank you very much for all the reviews, Eli!