[NFC] Refactor LoopInterchange into a loop-nest pass

[TaWeiTu]

Summary

This is the preliminary patch of converting LoopInterchange pass to a loop-nest pass and has no intended functional change.
Changes that are not loop-nest related are split to D96650.

[Whitney]

Can we have a separate patch for Besides replacing Loop with LoopNest, this patch also removes the parameters OuterLoopId in many functions since it always has the value of InnerLoopId - 1. first?

[TaWeiTu]

Rebase on top of D96650

[Whitney]

llvm/include/llvm/Analysis/LoopNestAnalysis.h

142

I am not sure it is clear that getHeader of a loop nest is the outermost loop header.
Looks like you added it for getting the loopnest function?
Function &F = *LN.getHeader()->getParent();

maybe adding a getParent() is more appropriate?

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

477

can we keep the const?

530

why is it safe to remove

// Loops interchanged reflect the same in LoopList
std::swap(LoopList[i - 1], LoopList[i]);

[TaWeiTu]

Replace LoopNest::getHeader() with LoopNest::getParent()

[TaWeiTu]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

477

I thought that ArrayRef is by definition a constant reference to the array. Am I missing something here?

530

Because previously the only place where LoopList is used is to retrieve the InnerLoop and OuterLoop to be interchanged by their indices in the array. After D96650, both loops are now explicitly passed to processLoop and thus maintaining the order of the loops in LoopList is irrelevant now.

[TaWeiTu]

Rebase

llvm/include/llvm/Analysis/LoopNestAnalysis.h

bool areAllLoopsSimplifyForm() const {
     return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
   }
 
   /// Return true if all loops in the loop nest are in rotated form.
   bool areAllLoopsRotatedForm() const {
     return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
   }
 
+  BasicBlock *getHeader() const { return Loops.front()->getHeader(); }
+
   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/include/llvm/Transforms/Scalar/LoopInterchange.h

 #define LLVM_TRANSFORMS_SCALAR_LOOPINTERCHANGE_H
 
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
 struct LoopInterchangePass : public PassInfoMixin<LoopInterchangePass> {
-  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+  PreservedAnalyses run(LoopNest &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPINTERCHANGE_H

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

static bool validDepInterchange(CharMatrix &DepMatrix, unsigned Row,
   return false;
 }
 
 // Checks if it is legal to interchange 2 loops.
 // [Theorem] A permutation of the loops in a perfect nest is legal if and only
 // if the direction matrix, after the same permutation is applied to its
 // columns, has no ">" direction as the leftmost non-"=" direction in any row.
 static bool isLegalToInterChangeLoops(CharMatrix &DepMatrix,
-                                      unsigned InnerLoopId,
-                                      unsigned OuterLoopId) {
+                                      unsigned InnerLoopId) {
   unsigned NumRows = DepMatrix.size();
   // For each row check if it is valid to interchange.
   for (unsigned Row = 0; Row < NumRows; ++Row) {
     char InnerDep = DepMatrix[Row][InnerLoopId];
-    char OuterDep = DepMatrix[Row][OuterLoopId];
+    char OuterDep = DepMatrix[Row][InnerLoopId - 1];
     if (InnerDep == '*' || OuterDep == '*')
       return false;
-    if (!validDepInterchange(DepMatrix, Row, OuterLoopId, InnerDep, OuterDep))
+    if (!validDepInterchange(DepMatrix, Row, InnerLoopId - 1, InnerDep,
+                             OuterDep))
       return false;
   }
   return true;
 }
 
 static LoopVector populateWorklist(Loop &L) {
   LLVM_DEBUG(dbgs() << "Calling populateWorklist on Func: "
                     << L.getHeader()->getParent()->getName() << " Loop: %"

 /// LoopInterchangeLegality checks if it is legal to interchange the loop.
 class LoopInterchangeLegality {
 public:
   LoopInterchangeLegality(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                           OptimizationRemarkEmitter *ORE)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
 
   /// Check if the loops can be interchanged.
-  bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId,
-                           CharMatrix &DepMatrix);
+  bool canInterchangeLoops(unsigned InnerLoopId, CharMatrix &DepMatrix);
 
   /// Check if the loop structure is understood. We do not handle triangular
   /// loops for now.
   bool isLoopStructureUnderstood(PHINode *InnerInductionVar);
 
   bool currentLimitations();
 
   const SmallPtrSetImpl<PHINode *> &getOuterInnerReductions() const {

 /// loop.
 class LoopInterchangeProfitability {
 public:
   LoopInterchangeProfitability(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                                OptimizationRemarkEmitter *ORE)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), ORE(ORE) {}
 
   /// Check if the loop interchange is profitable.
-  bool isProfitable(unsigned InnerLoopId, unsigned OuterLoopId,
-                    CharMatrix &DepMatrix);
+  bool isProfitable(unsigned InnerLoopId, CharMatrix &DepMatrix);
 
 private:
   int getInstrOrderCost();
 
   Loop *OuterLoop;
   Loop *InnerLoop;
 
   /// Scev analysis.
struct LoopInterchange {
 
   bool run(Loop *L) {
     if (L->getParentLoop())
       return false;
 
     return processLoopList(populateWorklist(*L));
   }
 
-  bool isComputableLoopNest(LoopVector LoopList) {
+  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);
+  }
+
+  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;
       }
       if (L->getNumBackEdges() != 1) {
         LLVM_DEBUG(dbgs() << "NumBackEdges is not equal to 1\n");
         return false;
       }
       if (!L->getExitingBlock()) {
         LLVM_DEBUG(dbgs() << "Loop doesn't have unique exit block\n");
         return false;
       }
     }
     return true;
   }
 
-  unsigned selectLoopForInterchange(const LoopVector &LoopList) {
+  unsigned selectLoopForInterchange(ArrayRef<Loop *> LoopList) {
     // TODO: Add a better heuristic to select the loop to be interchanged based
     // on the dependence matrix. Currently we select the innermost loop.
     return LoopList.size() - 1;
   }
 
-  bool processLoopList(LoopVector LoopList) {
+  bool processLoopList(ArrayRef<Loop *> LoopList) {
     bool Changed = false;
     unsigned LoopNestDepth = LoopList.size();
     if (LoopNestDepth < 2) {
       LLVM_DEBUG(dbgs() << "Loop doesn't contain minimum nesting level.\n");
       return false;
     }
     if (LoopNestDepth > MaxLoopNestDepth) {
       LLVM_DEBUG(dbgs() << "Cannot handle loops of depth greater than "
#endif
     BasicBlock *LoopNestExit = OuterMostLoop->getExitBlock();
     if (!LoopNestExit) {
       LLVM_DEBUG(dbgs() << "OuterMostLoop needs an unique exit block");
       return false;
     }
 
     unsigned SelecLoopId = selectLoopForInterchange(LoopList);
     // Move the selected loop outwards to the best possible position.
+    Loop *LoopToBeInterchanged = LoopList[SelecLoopId];
     for (unsigned i = SelecLoopId; i > 0; i--) {
-      bool Interchanged =
-          processLoop(LoopList, i, i - 1, LoopNestExit, DependencyMatrix);
+      bool Interchanged = processLoop(LoopToBeInterchanged, LoopList[i - 1], i,
+                                      LoopNestExit, DependencyMatrix);
       if (!Interchanged)
         return Changed;
-      // Loops interchanged reflect the same in LoopList
-      std::swap(LoopList[i - 1], LoopList[i]);
-
       // Update the DependencyMatrix
       interChangeDependencies(DependencyMatrix, i, i - 1);
 #ifdef DUMP_DEP_MATRICIES
       LLVM_DEBUG(dbgs() << "Dependence after interchange\n");
       printDepMatrix(DependencyMatrix);
 #endif
       Changed |= Interchanged;
     }
     return Changed;
   }
 
-  bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
-                   unsigned OuterLoopId, BasicBlock *LoopNestExit,
+  bool processLoop(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
+                   BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
-    LLVM_DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
-                      << " and OuterLoopId = " << OuterLoopId << "\n");
-    Loop *InnerLoop = LoopList[InnerLoopId];
-    Loop *OuterLoop = LoopList[OuterLoopId];
-
+    LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
+                      << " and OuterLoopId = " << InnerLoopId - 1 << "\n");
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
-    if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, DependencyMatrix)) {
+    if (!LIL.canInterchangeLoops(InnerLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Not interchanging loops. Cannot prove legality.\n");
       return false;
     }
     LLVM_DEBUG(dbgs() << "Loops are legal to interchange\n");
     LoopInterchangeProfitability LIP(OuterLoop, InnerLoop, SE, ORE);
-    if (!LIP.isProfitable(InnerLoopId, OuterLoopId, DependencyMatrix)) {
+    if (!LIP.isProfitable(InnerLoopId, DependencyMatrix)) {
       LLVM_DEBUG(dbgs() << "Interchanging loops not profitable.\n");
       return false;
     }
 
     ORE->emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Interchanged",
                                 InnerLoop->getStartLoc(),
                                 InnerLoop->getHeader())
for (PHINode &PHI : LoopNestExit->phis()) {
      if (OuterLoop->getLoopLatch()->getUniquePredecessor() == nullptr)
        return false;
     }
   }
   return true;
 }
 
 bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId,
-                                                  unsigned OuterLoopId,
                                                   CharMatrix &DepMatrix) {
-  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId, OuterLoopId)) {
+  if (!isLegalToInterChangeLoops(DepMatrix, InnerLoopId)) {
     LLVM_DEBUG(dbgs() << "Failed interchange InnerLoopId = " << InnerLoopId
-                      << " and OuterLoopId = " << OuterLoopId
+                      << " and OuterLoopId = " << InnerLoopId - 1
                       << " due to dependence\n");
     ORE->emit([&]() {
       return OptimizationRemarkMissed(DEBUG_TYPE, "Dependence",
                                       InnerLoop->getStartLoc(),
                                       InnerLoop->getHeader())
              << "Cannot interchange loops due to dependences.";
     });
     return false;
for (Instruction &Ins : *BB) {
         }
       }
     }
   }
   return GoodOrder - BadOrder;
 }
 
 static bool isProfitableForVectorization(unsigned InnerLoopId,
-                                         unsigned OuterLoopId,
                                          CharMatrix &DepMatrix) {
   // TODO: Improve this heuristic to catch more cases.
   // If the inner loop is loop independent or doesn't carry any dependency it is
   // profitable to move this to outer position.
   for (auto &Row : DepMatrix) {
     if (Row[InnerLoopId] != 'S' && Row[InnerLoopId] != 'I')
       return false;
     // TODO: We need to improve this heuristic.
-    if (Row[OuterLoopId] != '=')
+    if (Row[InnerLoopId - 1] != '=')
       return false;
   }
   // If outer loop has dependence and inner loop is loop independent then it is
   // profitable to interchange to enable parallelism.
   // If there are no dependences, interchanging will not improve anything.
   return !DepMatrix.empty();
 }
 
 bool LoopInterchangeProfitability::isProfitable(unsigned InnerLoopId,
-                                                unsigned OuterLoopId,
                                                 CharMatrix &DepMatrix) {
   // TODO: Add better profitability checks.
   // e.g
   // 1) Construct dependency matrix and move the one with no loop carried dep
   //    inside to enable vectorization.
 
   // This is rough cost estimation algorithm. It counts the good and bad order
   // of induction variables in the instruction and allows reordering if number
   // of bad orders is more than good.
   int Cost = getInstrOrderCost();
   LLVM_DEBUG(dbgs() << "Cost = " << Cost << "\n");
   if (Cost < -LoopInterchangeCostThreshold)
     return true;
 
   // It is not profitable as per current cache profitability model. But check if
   // we can move this loop outside to improve parallelism.
-  if (isProfitableForVectorization(InnerLoopId, OuterLoopId, DepMatrix))
+  if (isProfitableForVectorization(InnerLoopId, DepMatrix))
     return true;
 
   ORE->emit([&]() {
     return OptimizationRemarkMissed(DEBUG_TYPE, "InterchangeNotProfitable",
                                     InnerLoop->getStartLoc(),
                                     InnerLoop->getHeader())
            << "Interchanging loops is too costly (cost="
            << ore::NV("Cost", Cost) << ", threshold="

 
 INITIALIZE_PASS_END(LoopInterchangeLegacyPass, "loop-interchange",
                     "Interchanges loops for cache reuse", false, false)
 
 Pass *llvm::createLoopInterchangePass() {
   return new LoopInterchangeLegacyPass();
 }
 
-PreservedAnalyses LoopInterchangePass::run(Loop &L, LoopAnalysisManager &AM,
+PreservedAnalyses LoopInterchangePass::run(LoopNest &LN,
+                                           LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) {
-  Function &F = *L.getHeader()->getParent();
+  Function &F = *LN.getHeader()->getParent();
 
   DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
   OptimizationRemarkEmitter ORE(&F);
-  if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(&L))
+  if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, &ORE).run(LN))
     return PreservedAnalyses::all();
   return getLoopPassPreservedAnalyses();
 }

llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll

 ;;  for (int k = 0; k < 100; ++k) {
 ;;    T[k] = fn1();
 ;;    for (int i = 0; i < 1000; ++i)
 ;;      for(int j = 1; j < 1000; ++j)
 ;;        Arr[j][i] = Arr[j][i]+k;
 ;;    fn2(T[k]);
 ;;  }
 
-; CHECK: Processing Inner Loop Id = 2 and OuterLoopId = 1
+; CHECK: Processing InnerLoopId = 2 and OuterLoopId = 1
 ; CHECK: Loops interchanged.
 
-; CHECK: Processing Inner Loop Id = 1 and OuterLoopId = 0
+; CHECK: Processing InnerLoopId = 1 and OuterLoopId = 0
 ; CHECK: Not interchanging loops. Cannot prove legality.
 
 @T = internal global [100 x double] zeroinitializer, align 4
 @Arr = internal global [1000 x [1000 x i32]] zeroinitializer, align 4
 
 define void @interchange_09(i32 %k) {
 entry:
   br label %for.body

llvm/test/Transforms/LoopInterchange/interchanged-loop-nest-3.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info \
 ; RUN:     -S -debug 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @D = common global [100 x [100 x [100 x i32]]] zeroinitializer
 
 ;; Test for interchange in loop nest greater than 2.
 ;;  for(int i=0;i<100;i++)
 ;;    for(int j=0;j<100;j++)
 ;;      for(int k=0;k<100;k++)
-;;        D[i][k][j] = D[i][k][j]+t;
+;;        D[k][j][i] = D[k][j][i]+t;
 
-; CHECK: Processing Inner Loop Id = 2 and OuterLoopId = 1
+; CHECK: Processing InnerLoopId = 2 and OuterLoopId = 1
 ; CHECK: Loops interchanged.
 
-; CHECK: Processing Inner Loop Id = 1 and OuterLoopId = 0
-; CHECK: Interchanging loops not profitable.
+; CHECK: Processing InnerLoopId = 1 and OuterLoopId = 0
+; CHECK: Loops interchanged.
 
 define void @interchange_08(i32 %t){
 entry:
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.inc15, %entry
   %i.028 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
   br label %for.cond4.preheader
 
 for.cond4.preheader:                              ; preds = %for.inc12, %for.cond1.preheader
   %j.027 = phi i32 [ 0, %for.cond1.preheader ], [ %inc13, %for.inc12 ]
   br label %for.body6
 
 for.body6:                                        ; preds = %for.body6, %for.cond4.preheader
   %k.026 = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.body6 ]
-  %arrayidx8 = getelementptr inbounds [100 x [100 x [100 x i32]]], [100 x [100 x [100 x i32]]]* @D, i32 0, i32 %i.028, i32 %k.026, i32 %j.027
+  %arrayidx8 = getelementptr inbounds [100 x [100 x [100 x i32]]], [100 x [100 x [100 x i32]]]* @D, i32 0, i32 %k.026, i32 %j.027, i32 %i.028
   %0 = load i32, i32* %arrayidx8
   %add = add nsw i32 %0, %t
   store i32 %add, i32* %arrayidx8
   %inc = add nuw nsw i32 %k.026, 1
   %exitcond = icmp eq i32 %inc, 100
   br i1 %exitcond, label %for.inc12, label %for.body6
 
 for.inc12:                                        ; preds = %for.body6

llvm/test/Transforms/LoopInterchange/not-interchanged-loop-nest-3.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info \
 ; RUN:     -S -debug 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @D = common global [100 x [100 x [100 x i32]]] zeroinitializer
 
 ;; Test for interchange in loop nest greater than 2.
 ;;  for(int i=0;i<100;i++)
 ;;    for(int j=0;j<100;j++)
 ;;      for(int k=0;k<100;k++)
 ;;        D[i][k][j] = D[i][k][j]+t;
 
-; CHECK: Processing Inner Loop Id = 2 and OuterLoopId = 1
+; CHECK: Processing InnerLoopId = 2 and OuterLoopId = 1
 ; CHECK: Loops interchanged.
 
-; CHECK: Processing Inner Loop Id = 1 and OuterLoopId = 0
+; CHECK: Processing InnerLoopId = 1 and OuterLoopId = 0
 ; CHECK: Interchanging loops not profitable.
 
 define void @interchange_08(i32 %t){
 entry:
   br label %for.cond1.preheader
 
 for.cond1.preheader:                              ; preds = %for.inc15, %entry
   %i.028 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]