This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Fix the checking of tightly nested loop
Needs ReviewPublic

Authored by geng on Nov 17 2020, 11:03 PM.

Details

Reviewers
fhahn
Whitney
Summary

In the original implementation, it did not check if the loop latches are tightly nested. We added the checking on if the latches are tightly nested.

Diff Detail

Event Timeline

geng created this revision.Nov 17 2020, 11:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 17 2020, 11:03 PM
geng requested review of this revision.Nov 17 2020, 11:03 PM
geng updated this revision to Diff 305985.Nov 17 2020, 11:34 PM
Whitney added inline comments.Nov 18 2020, 11:55 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
126 ↗(On Diff #305985)

If there are multiple induction phi, how can we know the first one encountered is the induction phi used for the loop bound?

129 ↗(On Diff #305985)

This change the current definition of perfect loop nest.
Why do you think we should consider loop nest as perfect with inner loop invariant binary operator in between the outer and inner loop?
If all loops in the loop nest are LCSSA, then the only possible users of instructions defined in the inner loop is phi nodes at inner loop exit block. which makes all binary operator operands to be inner loop invariant.

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
1025

Have you considered using if (LN.getMaxPerfectDepth() != InnerLoop->getLoopDepth())?

fhahn added inline comments.Nov 18 2020, 12:13 PM
llvm/lib/Analysis/LoopNestAnalysis.cpp
129 ↗(On Diff #305985)

I think LoopInterchange uses a slightly more relaxed 'tightly nested' criteria. How much work would it be to check that the path from inner loop exit to outer loop latch?

llvm/lib/Transforms/Scalar/LoopInterchange.cpp
610

are those checks included in the new checks?

etiotto added inline comments.
llvm/test/Transforms/LoopInterchange/perfectly-nested.ll
11 ↗(On Diff #305985)

The name of this file perfectly-nested.ll is counter-intuitive because you have an imperfect loop nest in this file. Name the file "imperfectly-nested.ll" ?

geng updated this revision to Diff 306382.Nov 19 2020, 5:40 AM
geng edited the summary of this revision. (Show Details)
etiotto added inline comments.Nov 19 2020, 11:41 AM
llvm/lib/Analysis/LoopNestAnalysis.cpp
126 ↗(On Diff #306382)

I think that removing this restriction (allow binary operators that have loop invariant values) is not necessary and would make the definition of a perfect loop nest too loose.

In order to handle a loop with binary opcodes that have loop invariant values in the inner loop you could add a transformation that sink that instruction into the inner loop (therefore making the resulting loop nest perfect). Then loop interchange will be able to handle the resulting perfect loop nest.

geng updated this revision to Diff 307746.Nov 25 2020, 6:57 PM
geng marked 2 inline comments as not done.
geng edited the summary of this revision. (Show Details)
geng updated this revision to Diff 308271.Nov 30 2020, 12:14 AM
geng marked 4 inline comments as done.
Whitney added inline comments.Dec 1 2020, 4:55 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
590–591

Is there a reason to rename Outer->Parent and Inner->Child? As all the comments still use the term inner and outer to reference the loops.

1021

processLoop is called with loop i and i -1, so there are no loops in between InnerLoop and OuterLoop.
Am I missing something?

geng updated this revision to Diff 309457.Dec 3 2020, 10:11 PM
geng edited the summary of this revision. (Show Details)

https://reviews.llvm.org/D98263 covered some of this change now, can you please rebase the patch?
The test case LGTM. Thanks.