This is an archive of the discontinued LLVM Phabricator instance.

[LoopInterchange] Replace tightly-nesting-ness check with the one from `LoopNest`
ClosedPublic

Authored by TaWeiTu on Feb 23 2021, 7:07 AM.

Details

Summary

The check tightlyNested() in LoopInterchange is similar to the one in LoopNest.
In fact, the former misses some cases where loop-interchange is not feasible and results in incorrect behaviour.
Replacing it with the much robust version provided by LoopNest reduces code duplications and fixes https://bugs.llvm.org/show_bug.cgi?id=48113.

LoopInterchange has a weaker definition of tightly or perfectly nesting-ness than the one implemented in LoopNest::arePerfectlyNested().
Therefore, tightlyNested() is instead implemented with LoopNest::checkLoopsStructure and additional checks for unsafe instructions.

Diff Detail

Event Timeline

TaWeiTu created this revision.Feb 23 2021, 7:07 AM
TaWeiTu requested review of this revision.Feb 23 2021, 7:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 23 2021, 7:07 AM
TaWeiTu updated this revision to Diff 325803.Feb 23 2021, 8:19 AM

Trigger rebuild

Whitney added inline comments.Feb 23 2021, 10:49 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

As checkLoopsStructure is going to check the inner loop should be the outer loop's only child, do we really need to check isTotallyNested here?

TaWeiTu added inline comments.Feb 23 2021, 5:03 PM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

I think the logic would be different if we remove isTotallyNested. For example, consider the following loop-nest:

for (i)
  for (j1)
    for (k)
      for (l)
  for (j2)

Before removing isTotallyNested, k and l can never be interchanged. But since we only check whether the two loops that are currently being interchanged are tightly-nested or not, k and l might get interchanged before realizing that i has two subloops, in which case we simply return from processLoopList without unrolling the changes.

I'm not sure whether LoopInterchange is intended to operate only on "totally nested" loops or not, because in the previous example swapping k and l does seem feasible.
Anyhow, if such improvement is what we want, I think it will be better to have a separate patch for that.

What do you think?
Thanks!

Gentle ping.

Whitney added inline comments.Mar 1 2021, 9:03 AM
llvm/include/llvm/Analysis/LoopNestAnalysis.h
161

is totally-nested a known term or you come up with it?

TaWeiTu added inline comments.Mar 1 2021, 9:45 AM
llvm/include/llvm/Analysis/LoopNestAnalysis.h
161

Ah, that's the term I came up with and that's why is quoted.
It will be nice if there's a more appropriate term for this.
Thanks!

TaWeiTu updated this revision to Diff 327830.Mar 3 2021, 9:44 AM
  • Remove unnecessary lines in the test case
Whitney added inline comments.Mar 7 2021, 7:28 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

If we only want to operate on perfect loop nest, then we can check LN.getMaxPerfectDepth() == LN.getNestDepth() here.
Then we don't need to add function isTotallyNested.

TaWeiTu added inline comments.Mar 7 2021, 7:31 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

Yes, but currently the definition of tightly nested loops in LoopInterchange is weaker than the perfectly nested loops defined in LoopNest.
Replacing isTotallyNested with LN.getMaxPerfectDepth() == LN.getNestDepth() loses quite a lot of optimization chances IIRC.

Whitney added inline comments.Mar 7 2021, 7:39 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

I think we should try to loosen the the definition of perfect nest in loop nest first, instead of introducing a new term.
How about we keep the code:

const auto &LoopList = LN.getLoops();
for (unsigned I = 1; I < LoopList.size(); ++I)
  if (LoopList[I]->getParentLoop() != LoopList[I - 1])
    return false;

and not introduce isTotallyNested in this patch?
Other changes in this patch LGTM.

TaWeiTu updated this revision to Diff 328867.Mar 7 2021, 8:17 AM
  • Remove isTotallyNested
Whitney accepted this revision.Mar 7 2021, 8:19 AM
This revision is now accepted and ready to land.Mar 7 2021, 8:19 AM
TaWeiTu added inline comments.Mar 7 2021, 8:19 AM
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
453

Sure, removed isTotallyNested.
Will try making the two definitions compatible as well.
Thanks for the review!

This revision was landed with ongoing or failed builds.Mar 7 2021, 7:36 PM
This revision was automatically updated to reflect the committed changes.