[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

479

can we keep the const?

532

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

479

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

532

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(); });
   }
 
+  /// Return the function to which the loop-nest belongs.
+  Function *getParent() const {
+    return Loops.front()->getHeader()->getParent();
+  }
+
   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

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], LoopList[i - 1], i, i - 1,
-                                      LoopNestExit, DependencyMatrix);
+      bool Interchanged = processLoop(LoopToBeInterchanged, LoopList[i - 1], i,
+                                      i - 1, 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(Loop *InnerLoop, Loop *OuterLoop, unsigned InnerLoopId,
                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     LLVM_DEBUG(dbgs() << "Processing InnerLoopId = " << InnerLoopId
                       << " and OuterLoopId = " << OuterLoopId << "\n");
-
     LoopInterchangeLegality LIL(OuterLoop, InnerLoop, SE, ORE);
     if (!LIL.canInterchangeLoops(InnerLoopId, OuterLoopId, 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)) {

 
 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.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/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[k][j][i] = D[k][j][i]+t;
+
+; CHECK: Processing InnerLoopId = 2 and OuterLoopId = 1
+; CHECK: Loops interchanged.
+
+; 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 %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
+  %inc13 = add nuw nsw i32 %j.027, 1
+  %exitcond29 = icmp eq i32 %inc13, 100
+  br i1 %exitcond29, label %for.inc15, label %for.cond4.preheader
+
+for.inc15:                                        ; preds = %for.inc12
+  %inc16 = add nuw nsw i32 %i.028, 1
+  %exitcond30 = icmp eq i32 %inc16, 100
+  br i1 %exitcond30, label %for.end17, label %for.cond1.preheader
+
+for.end17:                                        ; preds = %for.inc15
+  ret void
+}