This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Enable loop interchange with multiple outer loop indvars

Authored by congzhe on Dec 1 2021, 4:09 PM.



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.

Diff Detail

Event Timeline

congzhe created this revision.Dec 1 2021, 4:09 PM
congzhe requested review of this revision.Dec 1 2021, 4:09 PM
congzhe edited the summary of this revision. (Show Details)Dec 1 2021, 4:10 PM
congzhe updated this revision to Diff 391182.Dec 1 2021, 6:27 PM
congzhe updated this revision to Diff 391214.Dec 1 2021, 10:17 PM
congzhe added a reviewer: Restricted Project.Dec 20 2021, 11:55 AM
bmahjour added inline comments.Dec 23 2021, 1:39 PM

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().


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

congzhe added inline comments.Dec 30 2021, 10:55 AM

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 added inline comments.Jan 5 2022, 2:59 PM

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 updated this revision to Diff 398385.Jan 8 2022, 5:03 PM

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.
  1. 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 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.

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


Please use CHECK-NEXT and show full context


Same comment as above.

congzhe added inline comments.Jan 12 2022, 9:51 AM

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 this revision to Diff 399371.Jan 12 2022, 10:22 AM

Updated test cases by using "CHECK-NEXT".

bmahjour added inline comments.Jan 12 2022, 10:23 AM

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/

bmahjour added inline comments.Jan 12 2022, 10:27 AM

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

congzhe updated this revision to Diff 399375.Jan 12 2022, 10:35 AM

Updated test cases.

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

bmahjour accepted this revision as: bmahjour.Jan 12 2022, 10:47 AM
This revision is now accepted and ready to land.Jan 12 2022, 10:47 AM
This revision was landed with ongoing or failed builds.Jan 13 2022, 1:54 PM
This revision was automatically updated to reflect the committed changes.