[LoopInterchange] Incrementally update the dominator tree.
We can use incremental dominator tree updates to avoid re-calculating
the dominator tree after interchanging 2 loops.
Reviewers: dmgreen, kuhar
Reviewed By: kuhar
Differential Revision: https://reviews.llvm.org/D43176
llvm-svn: 325122
diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
index 4cda6ed..93ff71f 100644
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -453,6 +453,8 @@
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
+
+ AU.addPreserved<DominatorTreeWrapperPass>();
}
bool runOnFunction(Function &F) override {
@@ -462,8 +464,7 @@
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);
@@ -573,7 +574,6 @@
// Update the DependencyMatrix
interChangeDependencies(DependencyMatrix, i, i - 1);
- DT->recalculate(F);
#ifdef DUMP_DEP_MATRICIES
DEBUG(dbgs() << "Dependence after interchange\n");
printDepMatrix(DependencyMatrix);
@@ -1265,8 +1265,31 @@
}
}
+/// \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();
@@ -1306,27 +1329,18 @@
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)
@@ -1334,11 +1348,8 @@
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.
@@ -1358,19 +1369,14 @@
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;
}
diff --git a/llvm/test/Transforms/LoopInterchange/call-instructions.ll b/llvm/test/Transforms/LoopInterchange/call-instructions.ll
index e2428ac..c33abde 100644
--- a/llvm/test/Transforms/LoopInterchange/call-instructions.ll
+++ b/llvm/test/Transforms/LoopInterchange/call-instructions.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll
index 8045dd8..a0acf7e 100644
--- a/llvm/test/Transforms/LoopInterchange/currentLimitation.ll
+++ b/llvm/test/Transforms/LoopInterchange/currentLimitation.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll b/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll
index b0b8240..284d73e 100644
--- a/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll
+++ b/llvm/test/Transforms/LoopInterchange/interchange-flow-dep-outer.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll b/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll
index b609490..51c0a16 100644
--- a/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll
+++ b/llvm/test/Transforms/LoopInterchange/interchange-insts-between-indvar.ll
@@ -1,4 +1,4 @@
-; 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
diff --git a/llvm/test/Transforms/LoopInterchange/interchange-output-dependencies.ll b/llvm/test/Transforms/LoopInterchange/interchange-output-dependencies.ll
index 98deba9..bf9b80c 100644
--- a/llvm/test/Transforms/LoopInterchange/interchange-output-dependencies.ll
+++ b/llvm/test/Transforms/LoopInterchange/interchange-output-dependencies.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/interchange-simple-count-down.ll b/llvm/test/Transforms/LoopInterchange/interchange-simple-count-down.ll
index 70ba594..5aee1f1 100644
--- a/llvm/test/Transforms/LoopInterchange/interchange-simple-count-down.ll
+++ b/llvm/test/Transforms/LoopInterchange/interchange-simple-count-down.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/interchange-simple-count-up.ll b/llvm/test/Transforms/LoopInterchange/interchange-simple-count-up.ll
index 4febe02..b4c1421 100644
--- a/llvm/test/Transforms/LoopInterchange/interchange-simple-count-up.ll
+++ b/llvm/test/Transforms/LoopInterchange/interchange-simple-count-up.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll b/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll
index cf4f83b..eaff177 100644
--- a/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll
+++ b/llvm/test/Transforms/LoopInterchange/not-interchanged-dependencies-1.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/phi-ordering.ll b/llvm/test/Transforms/LoopInterchange/phi-ordering.ll
index d2d2947..c24e6eb 100644
--- a/llvm/test/Transforms/LoopInterchange/phi-ordering.ll
+++ b/llvm/test/Transforms/LoopInterchange/phi-ordering.ll
@@ -1,4 +1,4 @@
-; 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.
diff --git a/llvm/test/Transforms/LoopInterchange/profitability.ll b/llvm/test/Transforms/LoopInterchange/profitability.ll
index ae1f793..548e491 100644
--- a/llvm/test/Transforms/LoopInterchange/profitability.ll
+++ b/llvm/test/Transforms/LoopInterchange/profitability.ll
@@ -1,4 +1,4 @@
-; 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"
diff --git a/llvm/test/Transforms/LoopInterchange/reductions.ll b/llvm/test/Transforms/LoopInterchange/reductions.ll
index 86a44da..ccd4fef 100644
--- a/llvm/test/Transforms/LoopInterchange/reductions.ll
+++ b/llvm/test/Transforms/LoopInterchange/reductions.ll
@@ -1,4 +1,4 @@
-; 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