[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

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

129

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

958

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

[fhahn]

llvm/lib/Analysis/LoopNestAnalysis.cpp

129

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

12

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

120

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

586–587

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.

954–972

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/Analysis/LoopNestAnalysis.cpp

 //===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// The implementation for the loop nest analysis.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopNestAnalysis.h"
 #include "llvm/ADT/BreadthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loopnest"
 #ifndef NDEBUG
 static const char *VerboseDebug = DEBUG_TYPE "-verbose";
bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
   //    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.
   if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) {
     LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n");
     return false;
   }
 
-  // Bail out if we cannot retrieve the outer loop bounds.
-  auto OuterLoopLB = OuterLoop.getBounds(SE);
-  if (OuterLoopLB == None) {
-    LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: "
-                      << OuterLoop << "\n";);
-    return false;
-  }
-
   // Identify the outer loop latch comparison instruction.
   const BasicBlock *Latch = OuterLoop.getLoopLatch();
   assert(Latch && "Expecting a valid loop latch");
   const BranchInst *BI = dyn_cast<BranchInst>(Latch->getTerminator());
-  assert(BI && BI->isConditional() &&
-         "Expecting loop latch terminator to be a branch instruction");
+  assert(
+      BI && BI->isConditional() &&
+      "Expecting loop latch terminator to be a conditional branch instruction");
 
   const CmpInst *OuterLoopLatchCmp = dyn_cast<CmpInst>(BI->getCondition());
   DEBUG_WITH_TYPE(
       VerboseDebug, if (OuterLoopLatchCmp) {
         dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp
                << "\n";
       });
 
return llvm::all_of(BB, [&](const Instruction &I) {
       if (!isAllowed) {
         DEBUG_WITH_TYPE(VerboseDebug, {
           dbgs() << "Instruction: " << I << "\nin basic block: " << BB
                  << " is considered unsafe.\n";
         });
         return false;
       }
 
-      // The only binary instruction allowed is the outer loop step instruction,
-      // the only comparison instructions allowed are the inner loop guard
-      // compare instruction and the outer loop latch compare instruction.
-      if ((isa<BinaryOperator>(I) && &I != &OuterLoopLB->getStepInst()) ||
+      // The only binary instruction allowed is the outer loop step
+      // instruction, the only comparison instructions allowed are the inner
+      // loop guard compare instruction and the outer loop latch compare
+      // instruction.  For binary operations, if both of the operands are
+      // invariants of the inner loop, the corresponding operation can be
+      // considered in the inner loop. The loop is still perfectly nested.
+
+      InductionDescriptor ID;
+      for (PHINode &PHI : OuterLoop.getHeader()->phis())
+        if (InductionDescriptor::isInductionPHI(&PHI, &OuterLoop, &SE, ID))
+          break;
+      Instruction *StepInst = ID.getInductionBinOp();
+      if ((isa<BinaryOperator>(I) && &I != StepInst &&
+           !(InnerLoop.isLoopInvariant(I.getOperand(0)) &&
+             InnerLoop.isLoopInvariant(I.getOperand(1)))) ||
           (isa<CmpInst>(I) && &I != OuterLoopLatchCmp &&
            &I != InnerLoopGuardCmp)) {
         DEBUG_WITH_TYPE(VerboseDebug, {
           dbgs() << "Instruction: " << I << "\nin basic block:" << BB
                  << "is unsafe.\n";
         });
         return false;
       }
return BB.getFirstNonPHI() == BB.getTerminator() &&
                return IncomingBlock == InnerLoopExit ||
                       IncomingBlock == OuterLoopHeader;
              });
            });
   };
 
   const BasicBlock *ExtraPhiBlock = nullptr;
   // Ensure the only branch that may exist between the loops is the inner loop
-  // guard.
+  // guard. Or the branch jumps to the preheader of inner loop.
   if (OuterLoopHeader != InnerLoopPreHeader) {
     const BranchInst *BI =
         dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
 
-    if (!BI || BI != InnerLoop.getLoopGuardBranch())
+    if (!BI || (BI != InnerLoop.getLoopGuardBranch() &&
+                BI->getSuccessor(0) != InnerLoopPreHeader))
       return false;
 
     bool InnerLoopExitContainsLCSSA = ContainsLCSSAPhi(*InnerLoopExit);
 
     // The successors of the inner loop guard should be the inner loop
     // preheader and the outer loop latch.
     for (const BasicBlock *Succ : BI->successors()) {
       if (Succ == InnerLoopPreHeader)
for (const BasicBlock *Succ : BI->successors()) {
                   "outer loop latch.\n";
       });
       return false;
     }
   }
 
   // Ensure the inner loop exit block leads to the outer loop latch.
   const BasicBlock *SuccInner = InnerLoopExit->getSingleSuccessor();
-  if (!SuccInner ||
-      (SuccInner != OuterLoopLatch && SuccInner != ExtraPhiBlock)) {
+  if ((!SuccInner ||
+       (SuccInner != OuterLoopLatch && SuccInner != ExtraPhiBlock)) &&
+      InnerLoopExit != OuterLoopLatch) {
     DEBUG_WITH_TYPE(
         VerboseDebug,
         dbgs() << "Inner loop exit block " << *InnerLoopExit
-               << " does not directly lead to the outer loop latch.\n";);
+               << " does not directly lead/equal to the outer loop latch.\n";);
     return false;
   }
 
   return true;
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) {
   OS << "IsPerfect=";

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

 
 #include "llvm/Transforms/Scalar/LoopInterchange.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopNestAnalysis.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"

 static LoopVector populateWorklist(Loop &L) {
   LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
                     << L.getHeader()->getParent()->getName() << " Loop: %"
                     << L.getHeader()->getName() << '\n');
   LoopVector LoopList;
   Loop *CurrentLoop = &L;
   const std::vector<Loop *> *Vec = &CurrentLoop->getSubLoops();
   while (!Vec->empty()) {
-    // The current loop has multiple subloops in it hence it is not tightly
+    // The current loop has multiple subloops in it hence it is not perfectly
     // nested.
     // Discard all loops above it added into Worklist.
     if (Vec->size() != 1)
       return {};
 
     LoopList.push_back(CurrentLoop);
     CurrentLoop = Vec->front();
     Vec = &CurrentLoop->getSubLoops();
public:
 
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {
     return OuterInnerReductions;
   }
 
 private:
-  bool tightlyNested(Loop *Outer, Loop *Inner);
   bool containsUnsafeInstructions(BasicBlock *BB);
 
   /// Discover induction and reduction PHIs in the header of \p L. Induction
   /// PHIs are added to \p Inductions, reductions are added to
   /// OuterInnerReductions. When the outer loop is passed, the inner loop needs
   /// to be passed as \p InnerLoop.
   bool findInductionAndReductions(Loop *L,
                                   SmallVector<PHINode *, 8> &Inductions,

 
 } // 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();
-
-  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;
-
-  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
-  // the outer loop header when interchanging.
-  if (InnerLoopPreHeader != OuterLoopHeader &&
-      containsUnsafeInstructions(InnerLoopPreHeader))
-    return false;
-
-  LLVM_DEBUG(dbgs() << "Loops are perfectly nested\n");
-  // We have a perfect loop nest.
-  return true;
-}
-
 bool LoopInterchangeLegality::isLoopStructureUnderstood(
     PHINode *InnerInduction) {
   unsigned Num = InnerInduction->getNumOperands();
   BasicBlock *InnerLoopPreheader = InnerLoop->getLoopPreheader();
   for (unsigned i = 0; i < Num; ++i) {
     Value *Val = InnerInduction->getOperand(i);
     if (isa<Constant>(Val))
       continue;
     Instruction *I = dyn_cast<Instruction>(Val);
for (PHINode &PHI : LoopNestExit->phis()) {
     if (PHI.getType()->isFloatingPointTy())
       return false;
     for (unsigned i = 0; i < PHI.getNumIncomingValues(); i++) {
      Instruction *IncomingI = dyn_cast<Instruction>(PHI.getIncomingValue(i));
      if (!IncomingI || IncomingI->getParent() != OuterLoop->getLoopLatch())
        continue;
 
      // The incoming value is defined in the outer loop latch. Currently we
-     // only support that in case the outer loop latch has a single predecessor.
-     // This guarantees that the outer loop latch is executed if and only if
-     // the inner loop is executed (because tightlyNested() guarantees that the
-     // outer loop header only branches to the inner loop or the outer loop
-     // latch).
+     // only support that in case the outer loop latch has a single
+     // predecessor.  This guarantees that the outer loop latch is executed if
+     // and only if the inner loop is executed (because arePerfectlyNested()
+     // guarantees that the outer loop header only branches to the inner loop
+     // or the outer loop latch).
      // FIXME: We could weaken this logic and allow multiple predecessors,
      //        if the values are produced outside the loop latch. We would need
      //        additional logic to update the PHI nodes in the exit block as
      //        well.
      if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
        return false;
     }
   }
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)) {
-    LLVM_DEBUG(dbgs() << "Loops not tightly nested\n");
+  // Check if the loops are perfectly nested.
+  Loop *LoopInner = InnerLoop;
+  Loop *LoopOuter;
+  LoopNest LN(*OuterLoop, *SE);
+  do {
+    LoopOuter = LoopInner->getParentLoop();
+    if (!LN.arePerfectlyNested(*LoopOuter, *LoopInner, *SE)) {
+      LLVM_DEBUG(dbgs() << "Loops not perfectly nested\n");
       ORE->emit([&]() {
-      return OptimizationRemarkMissed(DEBUG_TYPE, "NotTightlyNested",
+        return OptimizationRemarkMissed(DEBUG_TYPE, "NotPerfectlyNested",
                                         InnerLoop->getStartLoc(),
                                         InnerLoop->getHeader())
-             << "Cannot interchange loops because they are not tightly "
+               << "Cannot interchange loops because they are not perfectly "
                   "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/perfectly-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: Not perfectly nested: invalid loop structure.
+; 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
+}