This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Enable loop interchange with multiple inner loop indvars
ClosedPublic

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

Details

Summary

This is a feature patch.

Currently loop interchange only supports loops with one inner loop induction variable. This patch adds support for transformation with more than one inner loop induction variables.

Related patch: https://reviews.llvm.org/D114916

Diff Detail

Event Timeline

congzhe created this revision.Dec 1 2021, 4:12 PM
congzhe requested review of this revision.Dec 1 2021, 4:12 PM
congzhe edited the summary of this revision. (Show Details)Dec 1 2021, 4:13 PM
bmahjour added inline comments.Dec 3 2021, 2:07 PM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
315

[nit] InnerInductionVar -> InnerInductionVars

622

suggestion: Inductions ->InnerInductions

670–672

suggestion: Value *V -> const Value *V

671–672

suggestion: use llvm::is_contained()

690

What if we have a loop condition like this:

for (...)
  for (; i < j; i++, j--)

I'm not sure if this would be legal to interchange (need to think about it more). I would have expected we return false if both left and right are functions of inner-ivs, to be conservatively correct.

Should have a test for this case also.

850–851

why do we need this copy?

1296

use llvm::is_contained()

1305

use llvm::is_contained()

1624

Why did we need to check OuterInnerReductions before and not anymore?

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll
17

The loop latch in the IR only uses one IV anyway, so can we simplify this to only use one IV for the condition?
Please also add a test where more than one IV is used in the latch.

congzhe added a comment.EditedDec 6 2021, 10:12 PM

@bmahjour

Thanks for the review! While I am almost ready to post the next version that has attempted to address your comments, I found another piece of code that can be improved in interchange. It might be easier that I post that improvement patch first and rebase this patch.

To be specific, I'm thinking that the current limtation that there should be no instruction between induction variable increment and branch can be entirely removed. The limitation was there initially because we split the inner latch at the point of induction variable increment hence all instructions after induction variable increment will be moved to the block that is split. However, later the pass is improved such that we only split at the inner latch branch instruction and we properly move instructions to the new block as needed.

I'll do more testing and if it looks fine, I'll post a patch that removes that limitation. Removal of that limitation can also simplify this patch, that's why I'm thinking to post that first and rebase this patch.

@bmahjour

Thanks for the review! While I am almost ready to post the next version that has attempted to address your comments, I found another piece of code that can be improved in interchange. It might be easier that I post that improvement patch first and rebase this patch.

To be specific, I'm thinking that the current limtation that there should be no instruction between induction variable increment and branch can be entirely removed. The limitation was there initially because we split the inner latch at the point of induction variable increment hence all instructions after induction variable increment will be moved to the block that is split. However, later the pass is improved such that we only split at the inner latch branch instruction and we properly move instructions to the new block as needed.

I'll do more testing and if it looks fine, I'll post a patch that removes that limitation. Removal of that limitation can also simplify this patch, that's why I'm thinking to post that first and rebase this patch.

Posted https://reviews.llvm.org/D115238 that did what I mentioned above. I will update and rebase this patch on top of https://reviews.llvm.org/D115238.

congzhe updated this revision to Diff 392379.Dec 7 2021, 6:31 AM

Comments addressed with minor refactoring

congzhe added inline comments.Dec 7 2021, 6:49 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
622

Thank you for the comment, the code is now refactored and this argument is not needed.
We'll use the member variable LoopInterchangeLegality::InnerLoopInductions directly in LoopInterchangeLegality::isLoopStructureUnderstood().

670–672

Thanks, updated accordingly.

671–672

Thanks, updated accordingly.

690

Thank you, after consideration I would propose this loop can be interchanged. I added a corresponding test case (test3 in /Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll) that shows what the loop looks like after transformation.

Following the transformation steps in the pass, I would not think this loop is much of a difference -- the phi nodes of i and j will be split out from the inner header (and formed into the new outer header) and the indvar increments will be split out from the inner latch (and formed into the new outer latch).

850–851

The bulky removal starting from line 891 is from patch https://reviews.llvm.org/D115238.

It would be easier to just incorporate D115238 in this patch, meaning this patch will be rebased on top of D115238.

850–851

Thanks, InnerLoopInductions will be later used in the transformation phase, thus we keep a copy in class LoopInterchangeLegality and will use it later.

1296

Thanks, udpate accordingly.

1305

Thanks, udpate accordingly.

1624

Thanks, this is due to difference in downstream and upstream repos. I've updated as per upstream.

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll
17

Thanks, added what you suggested as test2() where all inner loop indvars are used in the inner latch.

I kept test1() as is, although we could simplify it to use one IV it would be serve as an example of multiple IVs anymore if I simplified it.

congzhe updated this revision to Diff 392385.Dec 7 2021, 6:54 AM

The build bot test case failures are expected, and will be fixed after merging https://reviews.llvm.org/D115238.

congzhe added a reviewer: Restricted Project.Dec 20 2021, 11:55 AM
congzhe updated this revision to Diff 399213.Jan 11 2022, 10:55 PM

Patch updated:

  1. Rebased on https://reviews.llvm.org/D115238.
  1. Reworked on test cases to make them more canonical and more straightforward, by removing unnecessary instructions and variables, etc.
  1. Created a new function findInductions() such that we initialize InnerLoopInductions early, hence removed a potential order constraint.
congzhe updated this revision to Diff 399349.Jan 12 2022, 9:03 AM

Trival update in test cases.

bmahjour added inline comments.Jan 12 2022, 9:53 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
670–672

suggestion: rename to IsPathToInnerIndVar

llvm/test/Transforms/LoopInterchange/interchangeable-innerloop-multiple-indvars.ll
22

please add check lines for all the BBs to show the control flow....and please use CHECK-NEXT.

97

same comment as above

179

same comment as above

congzhe updated this revision to Diff 399372.Jan 12 2022, 10:24 AM

Addressed comments: renamed to "isPathToInnerIndvar"; updated test cases by using "CHECK-NEXT".

This revision is now accepted and ready to land.Jan 12 2022, 10:42 AM
congzhe updated this revision to Diff 399820.Jan 13 2022, 3:53 PM

Removed a function getInductionVariable() that becomes unused, in order to avoid build bot sanitizer failures.

getInductionVariable() becomes unused since we now use getInnerLoopInductions() to return the vector of inner indvars, instead of returning a single inner indvar from getInductionVariable().

Does it look fine to you? @bmahjour

Removed a function getInductionVariable() that becomes unused, in order to avoid build bot sanitizer failures.

getInductionVariable() becomes unused since we now use getInnerLoopInductions() to return the vector of inner indvars, instead of returning a single inner indvar from getInductionVariable().

Does it look fine to you? @bmahjour

Yep, makes sense to remove it.