[LoopInterchange] Enable loop interchange with multiple outer loop indvars

[congzhe]

Summary

This is a feature patch.

Currently loop interchange only works when the outer loop has one induction variable. This patch extends it to work with more than one outer induction variables. After interchange, reduction phis in the original outer loop header should be moved to the original inner loop header, which becomes the outer loop header. All other phis, i.e., induction phis, stay in the original position.

[congzhe]

gentle ping @Whitney @bmahjour

[bmahjour]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

832–833

this imposes an ordering constraint...the OuterLoopInduction member variable is invalid until we get here. It would be cleaner to introduce an initialization step before calling either urrentLimitations() or adjustLoopBranches().

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

can these tests be changed to something more canonical (eg not relying on zero initialization of globals, and signed integer wrap for termination)?

[congzhe]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

Thanks for your comment! While working on the revision, can I clarify that regarding "signed integer wrap for termination", did you suggest to remove those nsw flags that are involved in the loop exit condition?

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

14

Removing the nsw flags would make things worse, since the loop seems to rely on sign wrap to terminate. The way it's written the loop body won't even get entered since the initial values of c and e would fail the c && e check. What I'm asking is to change this test to a more typical counted loop format, eg:

for (int i1 = 0, i2 = 0; i1 > n && i2 > m; i1++, i2++)
  for (int j1 = m; j >= 0;  j--)
     ...

[congzhe]

Thanks for the comments, I've updated the patch accordingly. @bmahjour

The updates include:

1. Reworked on test cases, made them cleaner by renaming IR variable names and removing unnecessary instructions, etc. Specifically, I made the tests more canonical by not relying on zero initialization of globals but using standard PHI nodes with proper intial values. The loop exit conditions are also updated and now cover different scenarios.

2. Updated the code in LoopInterchange.cpp. Especially, after investigation I now find OuterLoopInductions is not necessarily needed and the current pass trivially supports multiple outer loop indvars already. This is resulted from my previous patch https://reviews.llvm.org/D102743 which has properly handled PHI node movements.

So I removed OuterLoopInduction which I added to this patch earlier.

I'd appreciate any further comment, thanks in advance.

[bmahjour]

Looks good....I just added a couple more comments in the tests. Once they are addressed, I'll accept this revision.

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

Please use CHECK-NEXT and show full context

102

Same comment as above.

[congzhe]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

Thanks for the comment! I intentionally used "CHECK" instead of "CHECK-NEXT" since some time down the road even some trivial change in the pass could fail "CHECK-NEXT" (and one needs to update the tests accordingly), hence I extracted the essential IR I'd like to check using "CHECK".

But your comment also makes sense, I'll use "CHECK-NEXT" and update them shortly.

[congzhe]

Updated test cases by using "CHECK-NEXT".

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

20

I have had the same dilemma as well, but based on feedback from others, I'm now realizing the benefit of having full context in the LIT tests. It makes it much easier to follow the structure and semantics of the generated code. In case of future changes, the tests can be trivially regenerated (via utils/update_test_checks.py).

[bmahjour]

llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll

19

based on these checks, it doesn't look like the loops have been interchanged!

[congzhe]

Updated test cases.

My apologies, my last update used "update_test_checks.py" with a wrong opt binary.