[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 ↗

(On Diff #133904)

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 ↗

(On Diff #133904)

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

[fhahn]

lib/Transforms/Scalar/LoopInterchange.cpp

465 ↗

(On Diff #133904)

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 ↗

(On Diff #133904)

Will do, thanks

[efriedma]

lib/Transforms/Scalar/LoopInterchange.cpp

465 ↗

(On Diff #133904)

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 ↗

(On Diff #133904)

Right, done!

[kuhar]

lib/Transforms/Scalar/LoopInterchange.cpp

407 ↗

(On Diff #133929)

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

588 ↗

(On Diff #133929)

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

1279 ↗

(On Diff #133929)

const unsigned NumSucc?

1285 ↗

(On Diff #133929)

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

588 ↗

(On Diff #133929)

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.

1285 ↗

(On Diff #133929)

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

1276 ↗

(On Diff #134052)

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

1285 ↗

(On Diff #133929)

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.

llvm/trunk/lib/Transforms/Scalar/LoopInterchange.cpp

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();
     DI = &getAnalysis<DependenceAnalysisWrapperPass>().getDI();
-    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-    DT = DTWP ? &DTWP->getDomTree() : nullptr;
+    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
     PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 
     // Build up a worklist of loop pairs to analyze.
     SmallVector<LoopVector, 8> Worklist;
 
     for (Loop *L : *LI)
       populateWorklist(*L, Worklist);
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;
   }
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,
+                            std::vector<DominatorTree::UpdateType> &DTUpdates) {
+  assert(llvm::count_if(BI->successors(),
+                        [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
+         "BI must jump to OldBB at most once.");
+  for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
+    if (BI->getSuccessor(i) == OldBB) {
+      BI->setSuccessor(i, NewBB);
+
+      DTUpdates.push_back(
+          {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});
+      DTUpdates.push_back(
+          {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB});
+      break;
+    }
+  }
+}
+
 bool LoopInterchangeTransform::adjustLoopBranches() {
   DEBUG(dbgs() << "adjustLoopBranches called\n");
+  std::vector<DominatorTree::UpdateType> DTUpdates;
+
   // Adjust the loop preheader
   BasicBlock *InnerLoopHeader = InnerLoop->getHeader();
   BasicBlock *OuterLoopHeader = OuterLoop->getHeader();
   BasicBlock *InnerLoopLatch = InnerLoop->getLoopLatch();
   BasicBlock *OuterLoopLatch = OuterLoop->getLoopLatch();
   BasicBlock *OuterLoopPreHeader = OuterLoop->getLoopPreheader();
   BasicBlock *InnerLoopPreHeader = InnerLoop->getLoopPreheader();
   BasicBlock *OuterLoopPredecessor = OuterLoopPreHeader->getUniquePredecessor();
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, DTUpdates);
+  updateSuccessor(OuterLoopHeaderBI, OuterLoopLatch, LoopExit, DTUpdates);
+  updateSuccessor(OuterLoopHeaderBI, InnerLoopPreHeader,
+                  InnerLoopHeaderSuccessor, 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, 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, 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, DTUpdates);
+  updateSuccessor(OuterLoopLatchBI, OuterLoopLatchSuccessor, InnerLoopLatch,
+                  DTUpdates);
 
   updateIncomingBlock(OuterLoopLatchSuccessor, OuterLoopLatch, InnerLoopLatch);
 
-  if (OuterLoopLatchBI->getSuccessor(0) == OuterLoopLatchSuccessor) {
-    OuterLoopLatchBI->setSuccessor(0, InnerLoopLatch);
-  } else {
-    OuterLoopLatchBI->setSuccessor(1, InnerLoopLatch);
-  }
-
+  DT->applyUpdates(DTUpdates);
   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.

llvm/trunk/test/Transforms/LoopInterchange/call-instructions.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 
 declare void @foo(i64 %a)

llvm/trunk/test/Transforms/LoopInterchange/currentLimitation.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; These are test that fail to interchange due to current limitation. This will go off once we extend the loop interchange pass.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
  
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x [100 x i32]]] zeroinitializer
  

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

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x i32] zeroinitializer
 @C = common global [100 x [100 x i32]] zeroinitializer

llvm/trunk/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 
 @A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16
 
 ;; Test to make sure we can handle zext intructions introduced by
 ;; IndVarSimplify.
 ;;
 ;;  for (int i = 0; i < 2; ++i)
 ;;    for(int j = 0; j < n; ++j) {

llvm/trunk/test/Transforms/LoopInterchange/interchange-output-dependencies.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 
 ;; Test to make sure we can handle output dependencies.

llvm/trunk/test/Transforms/LoopInterchange/interchange-simple-count-down.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x i32] zeroinitializer
 

llvm/trunk/test/Transforms/LoopInterchange/interchange-simple-count-up.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x i32] zeroinitializer
 

llvm/trunk/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x i32] zeroinitializer
 

llvm/trunk/test/Transforms/LoopInterchange/phi-ordering.ll

-; RUN: opt < %s -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; Checks the order of the inner phi nodes does not cause havoc.
 ;; The inner loop has a reduction into c. The IV is not the first phi.
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "armv8--linux-gnueabihf"
 
 ; Function Attrs: norecurse nounwind
 define void @test(i32 %T, [90 x i32]* noalias nocapture %C, i16* noalias nocapture readonly %A, i16* noalias nocapture readonly %B) local_unnamed_addr #0 {

llvm/trunk/test/Transforms/LoopInterchange/profitability.ll

-; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s
+; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -S | FileCheck %s
 ;; We test profitability model in these test cases.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @A = common global [100 x [100 x i32]] zeroinitializer
 @B = common global [100 x [100 x i32]] zeroinitializer
 

llvm/trunk/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++)