[LoopInterchange] Fix the checking of tightly nested loop

[geng]

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.

[Whitney]

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

1010

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

[fhahn]

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]

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" ?

[etiotto]

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.

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

587–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.

1006–1022

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

[Whitney]

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

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 } // end anonymous namespace
 
 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();
+bool LoopInterchangeLegality::tightlyNested(Loop *LoopOuter, Loop *LoopInner) {
+  BasicBlock *LoopOuterHeader = LoopOuter->getHeader();
+  BasicBlock *LoopInnerPreHeader = LoopInner->getLoopPreheader();
+  BasicBlock *LoopOuterLatch = LoopOuter->getLoopLatch();
+  BasicBlock *LoopInnerExit = LoopInner->getExitBlock();
 
   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)
+  // outer latch.
+  BranchInst *LoopOuterHeaderBI =
+      dyn_cast<BranchInst>(LoopOuterHeader->getTerminator());
+  if (!LoopOuterHeaderBI)
     return false;
 
-  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
-    if (Succ != InnerLoopPreHeader && Succ != InnerLoop->getHeader() &&
-        Succ != OuterLoopLatch)
+  for (BasicBlock *Succ : successors(LoopOuterHeaderBI))
+    if (Succ != LoopInnerPreHeader && Succ != LoopInner->getHeader() &&
+        Succ != LoopOuterLatch)
       return false;
 
+  // Ensure the inner loop exit block leads to the outer loop latch.
+  const BasicBlock *SuccInner = LoopInnerExit->getSingleSuccessor();
+  if ((!SuccInner || (SuccInner != LoopOuterLatch)) &&
+      LoopInnerExit != LoopOuterLatch) {
+    LLVM_DEBUG(
+        dbgs() << "Inner loop exit block " << *LoopInnerExit
+               << " does not directly lead/equal to the outer loop latch.\n";);
+    return false;
+  }
+
   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))
+  if (containsUnsafeInstructions(LoopOuterHeader) ||
+      containsUnsafeInstructions(LoopOuterLatch))
     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
-  // the outer loop header when interchanging.
-  if (InnerLoopPreHeader != OuterLoopHeader &&
-      containsUnsafeInstructions(InnerLoopPreHeader))
+  // Also make sure the inner loop preheader and inner loop exit does not
+  // contain any unsafe instructions. Note that all instructions in the
+  // preheader will be moved to the outer loop header when interchanging. Inner
+  // loop exit will be moved to the new inner loop after interchanging.
+  if (LoopInnerPreHeader != LoopOuterHeader &&
+      (containsUnsafeInstructions(LoopInnerPreHeader) ||
+       containsUnsafeInstructions(LoopInnerExit)))
     return false;
 
   LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
   // We have a perfect loop nest.
   return true;
 }
 
 bool LoopInterchangeLegality::isLoopStructureUnderstood(
bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
   // TODO: The loops could not be interchanged due to current limitations in the
   // transform module.
   if (currentLimitations()) {
     LLVM_DEBUG(dbgs() << "Not legal because of current transform limitation\n");
     return false;
   }
 
   // Check if the loops are tightly nested.
-  if (!tightlyNested(OuterLoop, InnerLoop)) {
+  Loop *LoopInner = InnerLoop;
+  Loop *LoopOuter = nullptr;
+  do {
+    LoopOuter = LoopInner->getParentLoop();
+    if (!tightlyNested(LoopOuter, LoopInner)) {
       LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
       ORE->emit([&]() {
         return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
-                                      InnerLoop->getStartLoc(),
-                                      InnerLoop->getHeader())
+                                        LoopInner->getStartLoc(),
+                                        LoopInner->getHeader())
                << "Cannot interchange loops because they are not tightly "
                   "nested.";
       });
       return false;
     }
+    LoopInner = LoopOuter;
+  } while (LoopOuter != OuterLoop);
 
   if (!areInnerLoopExitPHIsSupported(OuterLoop, InnerLoop,
                                      OuterInnerReductions)) {
     LLVM_DEBUG(dbgs() << "Found unsupported PHI nodes in inner loop exit.\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedExitPHI",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())

llvm/test/Transforms/LoopInterchange/imperfectly-nested.ll

+; REQUIRES: asserts
+; RUN: opt < %s -basicaa -loop-interchange -S -debug 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-gnu"
+
+@a = common dso_local local_unnamed_addr global i8 0, align 1
+@b = common dso_local local_unnamed_addr global [1 x [2 x i32]] zeroinitializer, align 4
+@c = common dso_local local_unnamed_addr global [1 x [9 x i8]] zeroinitializer, align 1
+
+;; The following case is not perfectly nested,
+;; should not be interchanged.
+;;
+;; char a;
+;; int b[][2];
+;; char c[][9];
+;; int h() {
+;;   for (; f <= 2; f++) {
+;;     for (int j = 0; j <= 2; j++) {
+;;       b[j][1] = c[j][f];
+;;     }
+;;     if (a)
+;;   }
+;;   return 0;
+;; }
+
+; CHECK: Loops not tightly nested
+; CHECK: Not interchanging loops. Cannot prove legality.
+
+define i32 @h() {
+outer.preheader:
+  %0 = load i8, i8* @a, align 1
+  %tobool.i = icmp eq i8 %0, 0
+  br label %outer.header
+
+outer.header:                            ; preds = %if.end.i, %outer.preheader
+  %indvars.iv4.i = phi i64 [ 0, %outer.preheader ], [ %indvars.iv.next5.i, %if.end.i ]
+  br label %inner.header
+
+inner.header:                                      ; preds = %inner.header, %outer.header
+  %indvars.iv.i = phi i64 [ 0, %outer.header ], [ %indvars.iv.next.i, %inner.header ]
+  %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
+  %1 = load i8, i8* %arrayidx5.i, align 1
+  %conv.i = zext i8 %1 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
+  %indvars.iv.next.i = add nuw nsw i64 %indvars.iv.i, 1
+  %exitcond.i = icmp eq i64 %indvars.iv.next.i, 3
+  br i1 %exitcond.i, label %for.cond.cleanup.i, label %inner.header
+
+for.cond.cleanup.i:                               ; preds = %inner.header
+  br i1 %tobool.i, label %if.end.i, label %if.then.i
+
+if.then.i:                                        ; preds = %for.cond.cleanup.i
+  br label %if.end.i
+
+if.end.i:                                         ; preds = %if.then.i, %for.cond.cleanup.i
+  %indvars.iv.next5.i = add nuw nsw i64 %indvars.iv4.i, 1
+  %exitcond6.i = icmp eq i64 %indvars.iv.next5.i, 3
+  br i1 %exitcond6.i, label %outer.exit, label %outer.header
+
+outer.exit:                   ; preds = %if.end.i
+  br label %h.exit
+
+h.exit:                                           ; preds = %outer.exit
+  ret i32 0
+}