[LoopInterchange] Incrementally update the dominator tree.

[fhahn]

Summary

We can use incremental dominator tree updates to avoid re-calculating
the dominator tree after interchanging 2 loops.

[fhahn]

Add DominatorTreeWrapperPass to preserved analysis.

[fhahn]

Only update DT if DT != nullptr, add -verify-dom-info to a test.

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

465

This list of preserved passes seems really short; at the very least, it should preserve GlobalsAA. Would be nice to preserve LoopInfo, LCSSA, and ScalarEvolution; I think the pass needs to preserve them anyway to interact correctly with itself?

test/Transforms/LoopInterchange/reductions.ll

1

Maybe add verify-dom-info to all the LoopInterchange tests?

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

465

Yes, making it preserve the DT is a first step. It indeed relies on LoopInfo, LCSSA, and ScalarEvolution being preserved too after interchanging 2 loops, for loop nests > 2.

At least LoopInfo is not preserved properly at the moment. I plan to fix those issues in follow up commits.

test/Transforms/LoopInterchange/reductions.ll

1

Will do, thanks

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

465

Okay.

You should probably make DomTree required, to simplify the code; you'll always have it anyway because LoopInfo requires it.

[fhahn]

Thanks again Eli! I've updated the patch to always preserve the DT and also added -verify-dom-info to the tests that interchange loops.

lib/Transforms/Scalar/LoopInterchange.cpp

465

Right, done!

[kuhar]

lib/Transforms/Scalar/LoopInterchange.cpp

407

Is this necessary? I guess you want to make the vector look clean in case a crash happens, is that it?

591

Is there a reason why the updates are applied int the destructor instead of at the end of this loop?

1282

const unsigned NumSucc?

1288

Can you have multiple successors that are the same BB? If so, you would have to exclude the redundant ones here.

[fhahn]

Thanks! I've moved collecting and applying updates to adjustLoopLinks and added an assertion to make sure we do not have BBs with redundant successors.

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

591

The first version of the patch had to collect updates from multiple code paths, but I've simplified things so there actually is no need to have DTUpdates as member variable. The only point where we adjust branches is in adjustLoopLinks, at the end we can apply the updates. I think we have to apply the updates after every transform, so we have a valid DT when we deal with loops with nests > 2.

1288

That should never happen I think. I've added a break and also an assertion. Please let me know if this is exactly the case you meant

[kuhar]

Looks good to me now.

One last question: is DomTreeWrapperPass always available when LoopInterchange is run? I'm thinking about requireAnalysis vs. getAnalysisIfAvailable.

lib/Transforms/Scalar/LoopInterchange.cpp

1285

for (unsigned i = 0, e = BI->getNumSuccessors(); i != e; ++i) {

1288

Looks fine, thanks!

[fhahn]

Thanks!

One last question: is DomTreeWrapperPass always available when LoopInterchange is run? I'm thinking about requireAnalysis vs. getAnalysisIfAvailable.

Yep, LoopInterchange relies on LoopInfo, so the DT should be computed already.

lib/Transforms/Scalar/LoopInterchange.cpp

 class LoopInterchangeTransform {
 public:
   LoopInterchangeTransform(Loop *Outer, Loop *Inner, ScalarEvolution *SE,
                            LoopInfo *LI, DominatorTree *DT,
                            BasicBlock *LoopNestExit,
                            bool InnerLoopContainsReductions)
       : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT),
         LoopExit(LoopNestExit),
-        InnerLoopHasReduction(InnerLoopContainsReductions) {}
+        InnerLoopHasReduction(InnerLoopContainsReductions), DTUpdates() {}
+
+  ~LoopInterchangeTransform() {
+    if (DT != nullptr) {
+      DT->applyUpdates(DTUpdates);
+      DTUpdates.clear();
+    }
+  }
 
   /// Interchange OuterLoop and InnerLoop.
   bool transform();
   void restructureLoops(Loop *InnerLoop, Loop *OuterLoop);
   void removeChildLoop(Loop *OuterLoop, Loop *InnerLoop);
 
 private:
   void splitInnerLoopLatch(Instruction *);
private:
 
   /// Scev analysis.
   ScalarEvolution *SE;
 
   LoopInfo *LI;
   DominatorTree *DT;
   BasicBlock *LoopExit;
   bool InnerLoopHasReduction;
+  std::vector<DominatorTree::UpdateType> DTUpdates;
 };
 
 // Main LoopInterchange Pass.
 struct LoopInterchange : public FunctionPass {
   static char ID;
   ScalarEvolution *SE = nullptr;
   LoopInfo *LI = nullptr;
   DependenceInfo *DI = nullptr;
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<DependenceAnalysisWrapperPass>();
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequiredID(LCSSAID);
     AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
+
+    AU.addPreserved<DominatorTreeWrapperPass>();
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
for (unsigned i = SelecLoopId; i > 0; i--) {
           processLoop(LoopList, 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);
-      DT->recalculate(F);
 #ifdef DUMP_DEP_MATRICIES
       DEBUG(dbgs() << "Dependence after interchange\n");
       printDepMatrix(DependencyMatrix);
 #endif
       Changed |= Interchanged;
     }
     return Changed;
   }
 
   bool processLoop(LoopVector LoopList, unsigned InnerLoopId,
                    unsigned OuterLoopId, BasicBlock *LoopNestExit,
                    std::vector<std::vector<char>> &DependencyMatrix) {
     DEBUG(dbgs() << "Processing Inner Loop Id = " << InnerLoopId
                  << " and OuterLoopId = " << OuterLoopId << "\n");
for (auto I = CurrBlock->begin(); isa<PHINode>(I); ++I) {
     unsigned Num = PHI->getNumIncomingValues();
     for (unsigned i = 0; i < Num; ++i) {
       if (PHI->getIncomingBlock(i) == OldPred)
         PHI->setIncomingBlock(i, NewPred);
     }
   }
 }
 
+/// \brief Update BI to jump to NewBB instead of OldBB. Records updates to
+/// the dominator tree in DTUpdates, if DT should be preserved.
+static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
+                            BasicBlock *NewBB, bool PreserveDT,
+                            std::vector<DominatorTree::UpdateType> &DTUpdates) {
+  unsigned NumSucc = BI->getNumSuccessors();
+  for (unsigned i = 0; i < NumSucc; ++i) {
+    if (BI->getSuccessor(i) == OldBB) {
+      BI->setSuccessor(i, NewBB);
+
+      if (PreserveDT) {
+        DTUpdates.push_back(
+            {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
+        DTUpdates.push_back(
+            {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
+      }
+    }
+  }
+}
+
 bool LoopInterchangeTransform::adjustLoopBranches() {
   DEBUG(dbgs() << "adjustLoopBranches called\n");
   // Adjust the loop preheader
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
bool LoopInterchangeTransform::adjustLoopBranches() {
 
   if (!OuterLoopPredecessorBI || !InnerLoopLatchPredecessorBI)
     return false;
   BasicBlock *InnerLoopHeaderSuccessor = InnerLoopHeader->getUniqueSuccessor();
   if (!InnerLoopHeaderSuccessor)
     return false;
 
   // Adjust Loop Preheader and headers
-
-  unsigned NumSucc = OuterLoopPredecessorBI->getNumSuccessors();
-  for (unsigned i = 0; i < NumSucc; ++i) {
-    if (OuterLoopPredecessorBI->getSuccessor(i) == OuterLoopPreHeader)
-      OuterLoopPredecessorBI->setSuccessor(i, InnerLoopPreHeader);
-  }
-
-  NumSucc = OuterLoopHeaderBI->getNumSuccessors();
-  for (unsigned i = 0; i < NumSucc; ++i) {
-    if (OuterLoopHeaderBI->getSuccessor(i) == OuterLoopLatch)
-      OuterLoopHeaderBI->setSuccessor(i, LoopExit);
-    else if (OuterLoopHeaderBI->getSuccessor(i) == InnerLoopPreHeader)
-      OuterLoopHeaderBI->setSuccessor(i, InnerLoopHeaderSuccessor);
-  }
+  updateSuccessor(OuterLoopPredecessorBI, OuterLoopPreHeader,
+                  InnerLoopPreHeader, DT != nullptr, DTUpdates);
+  updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DT != nullptr,
+                  DTUpdates);
+  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
+                  InnerLoopHeaderSuccessor, DT != nullptr, DTUpdates);
 
   // Adjust reduction PHI's now that the incoming block has changed.
   updateIncomingBlock(InnerLoopHeaderSuccessor, InnerLoopHeader,
                       OuterLoopHeader);
 
-  BranchInst::Create(OuterLoopPreHeader, InnerLoopHeaderBI);
-  InnerLoopHeaderBI->eraseFromParent();
+  updateSuccessor(InnerLoopHeaderBI, InnerLoopHeaderSuccessor,
+                  OuterLoopPreHeader, DT != nullptr, DTUpdates);
 
   // -------------Adjust loop latches-----------
   if (InnerLoopLatchBI->getSuccessor(0) == InnerLoopHeader)
     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(1);
   else
     InnerLoopLatchSuccessor = InnerLoopLatchBI->getSuccessor(0);
 
-  NumSucc = InnerLoopLatchPredecessorBI->getNumSuccessors();
-  for (unsigned i = 0; i < NumSucc; ++i) {
-    if (InnerLoopLatchPredecessorBI->getSuccessor(i) == InnerLoopLatch)
-      InnerLoopLatchPredecessorBI->setSuccessor(i, InnerLoopLatchSuccessor);
-  }
+  updateSuccessor(InnerLoopLatchPredecessorBI, InnerLoopLatch,
+                  InnerLoopLatchSuccessor, DT != nullptr, DTUpdates);
 
   // Adjust PHI nodes in InnerLoopLatchSuccessor. Update all uses of PHI with
   // the value and remove this PHI node from inner loop.
   SmallVector<PHINode *, 8> LcssaVec;
   for (auto I = InnerLoopLatchSuccessor->begin(); isa<PHINode>(I); ++I) {
     PHINode *LcssaPhi = cast<PHINode>(I);
     LcssaVec.push_back(LcssaPhi);
   }
   for (PHINode *P : LcssaVec) {
     Value *Incoming = P->getIncomingValueForBlock(InnerLoopLatch);
     P->replaceAllUsesWith(Incoming);
     P->eraseFromParent();
   }
 
   if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopHeader)
     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(1);
   else
     OuterLoopLatchSuccessor = OuterLoopLatchBI->getSuccessor(0);
 
-  if (InnerLoopLatchBI->getSuccessor(1) == InnerLoopLatchSuccessor)
-    InnerLoopLatchBI->setSuccessor(1, OuterLoopLatchSuccessor);
-  else
-    InnerLoopLatchBI->setSuccessor(0, OuterLoopLatchSuccessor);
+  updateSuccessor(InnerLoopLatchBI, InnerLoopLatchSuccessor,
+                  OuterLoopLatchSuccessor, DT != nullptr, DTUpdates);
+  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
+                  DT != nullptr, DTUpdates);
 
   updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
 
-  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
-    OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
-  } else {
-    OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
-  }
-
   return true;
 }
 
 void LoopInterchangeTransform::adjustLoopPreheaders() {
   // We have interchanged the preheaders so we need to interchange the data in
   // the preheader as well.
   // This is because the content of inner preheader was previously executed
   // inside the outer loop.

test/Transforms/LoopInterchange/reductions.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 
 @A = common global [500 x [500 x i32]] zeroinitializer
 @X = common global i32 0
 @B = common global [500 x [500 x i32]] zeroinitializer
 @Y = common global i32 0
 
 ;;  for( int i=1;i<N;i++)
 ;;    for( int j=1;j<N;j++)