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

[TaWeiTu]

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.

[TaWeiTu]

Trigger rebuild

[Whitney]

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]

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!

[TaWeiTu]

Gentle ping.

[Whitney]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

161

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

[TaWeiTu]

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]

• Remove unnecessary lines in the test case

[Whitney]

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]

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]

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]

• Remove isTotallyNested

[TaWeiTu]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

453

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

llvm/include/llvm/Analysis/LoopNestAnalysis.h

public:
   static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
 
   /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
   /// (if there are any). Return the last basic block found or \p End if it was
   /// reached during the search.
   static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
                                                const BasicBlock *End);
 
+  /// Determine whether the loops structure violates basic requirements for
+  /// perfect nesting:
+  ///  - the inner loop should be the outer loop's only child
+  ///  - the outer loop header should 'flow' into the inner loop preheader
+  ///    or jump around the inner loop to the outer loop latch
+  ///  - if the inner loop latch exits the inner loop, it should 'flow' into
+  ///    the outer loop latch.
+  /// Returns true if the loop structure satisfies the basic requirements and
+  /// false otherwise.
+  static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
+                                  ScalarEvolution &SE);
+
   /// Return the outermost loop in the loop nest.
   Loop &getOutermostLoop() const { return *Loops.front(); }
 
   /// Return the innermost loop in the loop nest if the nest has only one
   /// innermost loop, and a nullptr otherwise.
   /// Note: the innermost loop returned is not necessarily perfectly nested.
   Loop *getInnermostLoop() const {
     if (Loops.size() == 1)
bool areAllLoopsRotatedForm() const {
     return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
   }
 
   /// Return the function to which the loop-nest belongs.
   Function *getParent() const {
     return Loops.front()->getHeader()->getParent();
   }
 
+  /// Return whether all loops in the loopnest (except for the innermost one)
+  /// have exactly one subloop and thus the loopnest is "totally-nested".
+  bool isTotallyNested() const {
+    return all_of(make_range(Loops.begin(), std::prev(Loops.end())),
+                  [](const Loop *L) { return L->getSubLoops().size() == 1; });
+  }
+
   StringRef getName() const { return Loops.front()->getName(); }
 
 protected:
   const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
 };
 
 raw_ostream &operator<<(raw_ostream &, const LoopNest &);

llvm/lib/Analysis/LoopNestAnalysis.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "loopnest"
 #ifndef NDEBUG
 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
 #endif
 
-/// Determine whether the loops structure violates basic requirements for
-/// perfect nesting:
-///  - the inner loop should be the outer loop's only child
-///  - the outer loop header should 'flow' into the inner loop preheader
-///    or jump around the inner loop to the outer loop latch
-///  - if the inner loop latch exits the inner loop, it should 'flow' into
-///    the outer loop latch.
-/// Returns true if the loop structure satisfies the basic requirements and
-/// false otherwise.
-static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
-                                ScalarEvolution &SE);
-
 //===----------------------------------------------------------------------===//
 // LoopNest implementation
 //
 
 LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
     : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
   append_range(Loops, breadth_first(&Root));
 }
while (BB && BB != End && IsEmpty(BB) && !Visited.count(BB)) {
     Visited.insert(BB);
     PredBB = BB;
     BB = BB->getUniqueSuccessor();
   }
 
   return (BB == End) ? *End : *PredBB;
 }
 
-static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
+bool LoopNest::checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop,
                                    ScalarEvolution &SE) {
   // The inner loop must be the only outer loop's child.
   if ((OuterLoop.getSubLoops().size() != 1) ||
       (InnerLoop.getParentLoop() != &OuterLoop))
     return false;
 
   // We expect loops in normal form which have a preheader, header, latch...
   if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm())
     return false;

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

struct LoopInterchange {
   bool run(Loop *L) {
     if (L->getParentLoop())
       return false;
 
     return processLoopList(populateWorklist(*L));
   }
 
   bool run(LoopNest &LN) {
-    const auto &LoopList = LN.getLoops();
-    for (unsigned I = 1; I < LoopList.size(); ++I)
-      if (LoopList[I]->getParentLoop() != LoopList[I - 1])
-        return false;
-    return processLoopList(LoopList);
+    if (!LN.isTotallyNested())
+    return processLoopList(LN.getLoops());
   }
 
   bool isComputableLoopNest(ArrayRef<Loop *> LoopList) {
     for (Loop *L : LoopList) {
       const SCEV *ExitCountOuter = SE->getBackedgeTakenCount(L);
       if (isa<SCEVCouldNotCompute>(ExitCountOuter)) {
         LLVM_DEBUG(dbgs() << "Couldn't compute backedge count\n");
         return false;

 
 bool LoopInterchangeLegality::containsUnsafeInstructions(BasicBlock *BB) {
   return any_of(*BB, [](const Instruction &I) {
     return I.mayHaveSideEffects() || I.mayReadFromMemory();
   });
 }
 
 bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
-  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
-  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
-  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
-
   LLVM_DEBUG(dbgs() << "Checking if loops are tightly nested\n");
 
-  // A perfectly nested loop will not have any branch in between the outer and
-  // inner block i.e. outer header will branch to either inner preheader and
-  // outerloop latch.
-  BranchInst *OuterLoopHeaderBI =
-      dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
-  if (!OuterLoopHeaderBI)
-    return false;
-
-  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
-    if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
-        Succ != OuterLoopLatch)
-      return false;
+  if (!LoopNest::checkLoopsStructure(*OuterLoop, *InnerLoop, *SE))
+  BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
+  BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
+  BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
 
-  LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
   // We do not have any basic block in between now make sure the outer header
   // and outer loop latch doesn't contain any unsafe instructions.
   if (containsUnsafeInstructions(OuterLoopHeader) ||
       containsUnsafeInstructions(OuterLoopLatch))
     return false;
 
   // Also make sure the inner loop preheader does not contain any unsafe
   // instructions. Note that all instructions in the preheader will be moved to

llvm/test/Transforms/LoopInterchange/pr48113.ll

+; RUN: opt -S -passes='loop-interchange' -debug-only=loop-interchange < %s 2>&1 > /dev/null | FileCheck %s
+@.str = private unnamed_addr constant [5 x i8] c"%lX\0A\00", align 1
+@d = dso_local local_unnamed_addr global i8 0, align 1
+@a = dso_local local_unnamed_addr global i8 0, align 1
+@b = dso_local local_unnamed_addr global [1 x [2 x i32]] zeroinitializer, align 4
+@c = dso_local local_unnamed_addr global [1 x [9 x i8]] zeroinitializer, align 1
+@e = dso_local local_unnamed_addr global i8* null, align 8
+@g = dso_local local_unnamed_addr global i16 0, align 2
+@f = internal unnamed_addr global i32 0, align 4
+
+; CHECK: Processing InnerLoopId = 1 and OuterLoopId = 0
+; CHECK-NEXT: Checking if loops are tightly nested
+; CHECK-NEXT: Loops not tightly nested
+; CHECK-NEXT: Not interchanging loops. Cannot prove legality
+
+; Function Attrs: nofree nounwind optsize uwtable
+define dso_local i32 @main() local_unnamed_addr #0 {
+entry:
+  %.pr.i = load i32, i32* @f, align 4, !tbaa !2
+  %cmp3.i = icmp ult i32 %.pr.i, 3
+  br i1 %cmp3.i, label %for.cond1.preheader.lr.ph.i, label %h.exit
+
+for.cond1.preheader.lr.ph.i:                      ; preds = %entry
+  %0 = load i8, i8* @a, align 1, !tbaa !6
+  %tobool.not.i = icmp eq i8 %0, 0
+  %1 = load i8*, i8** @e, align 8
+  %2 = zext i32 %.pr.i to i64
+  br label %for.cond1.preheader.i
+
+for.cond1.preheader.i:                            ; preds = %if.end.i, %for.cond1.preheader.lr.ph.i
+  %indvars.iv4.i = phi i64 [ %2, %for.cond1.preheader.lr.ph.i ], [ %indvars.iv.next5.i, %if.end.i ]
+  br label %for.body3.i
+
+for.body3.i:                                      ; preds = %for.body3.i, %for.cond1.preheader.i
+  %indvars.iv.i = phi i64 [ 0, %for.cond1.preheader.i ], [ %indvars.iv.next.i, %for.body3.i ]
+  %arrayidx5.i = getelementptr inbounds [1 x [9 x i8]], [1 x [9 x i8]]* @c, i64 0, i64 %indvars.iv.i, i64 %indvars.iv4.i
+  %3 = load i8, i8* %arrayidx5.i, align 1, !tbaa !6
+  %conv.i = sext i8 %3 to i32
+  %arrayidx8.i = getelementptr inbounds [1 x [2 x i32]], [1 x [2 x i32]]* @b, i64 0, i64 %indvars.iv.i, i64 1
+  store i32 %conv.i, i32* %arrayidx8.i, align 4, !tbaa !2
+  %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.i, 1
+  %exitcond.not.i = icmp eq i64 %indvars.iv.next.i, 3
+  br i1 %exitcond.not.i, label %for.end.i, label %for.body3.i, !llvm.loop !7
+
+for.end.i:                                        ; preds = %for.body3.i
+  %4 = load i8, i8* @d, align 1, !tbaa !6
+  %inc9.i = add i8 %4, 1
+  store i8 %inc9.i, i8* @d, align 1, !tbaa !6
+  br i1 %tobool.not.i, label %if.end.i, label %if.then.i
+
+if.then.i:                                        ; preds = %for.end.i
+  %5 = load i8, i8* %1, align 1, !tbaa !6
+  %conv10.i = sext i8 %5 to i16
+  store i16 %conv10.i, i16* @g, align 2, !tbaa !9
+  br label %if.end.i
+
+if.end.i:                                         ; preds = %if.then.i, %for.end.i
+  %indvars.iv.next5.i = add nuw nsw i64 %indvars.iv4.i, 1
+  %exitcond6.not.i = icmp eq i64 %indvars.iv.next5.i, 3
+  br i1 %exitcond6.not.i, label %for.cond.for.end13_crit_edge.i, label %for.cond1.preheader.i, !llvm.loop !11
+
+for.cond.for.end13_crit_edge.i:                   ; preds = %if.end.i
+  store i32 3, i32* @f, align 4, !tbaa !2
+  br label %h.exit
+
+h.exit:                                           ; preds = %entry, %for.cond.for.end13_crit_edge.i
+  %6 = load i8, i8* @d, align 1, !tbaa !6
+  %conv = sext i8 %6 to i32
+  %call1 = tail call i32 (i8*, ...) @printf(i8* nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0), i32 %conv) #2
+  ret i32 0
+}
+
+; Function Attrs: nofree nounwind optsize
+declare dso_local noundef i32 @printf(i8* nocapture noundef readonly, ...) local_unnamed_addr #1
+
+attributes #0 = { nofree nounwind optsize uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #1 = { nofree nounwind optsize "frame-pointer"="none" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #2 = { optsize }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 13.0.0 ([e-mail]:llvm/llvm-project.git ffba9e596d09a1d41f83102756e145b59d3f8495)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!4, !4, i64 0}
+!7 = distinct !{!7, !8}
+!8 = !{!"llvm.loop.mustprogress"}
+!9 = !{!10, !10, i64 0}
+!10 = !{!"short", !4, i64 0}
+!11 = distinct !{!11, !8}