Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -400,7 +400,15 @@ bool InnerLoopContainsReductions) : OuterLoop(Outer), InnerLoop(Inner), SE(SE), LI(LI), DT(DT), LoopExit(LoopNestExit), - InnerLoopHasReduction(InnerLoopContainsReductions) {} + InnerLoopHasReduction(InnerLoopContainsReductions), DTUpdates() {} + + ~LoopInterchangeTransform() { + DT->applyUpdates(DTUpdates); + DTUpdates.clear(); +#ifdef EXPENSIVE_CHECKS + DT->verifyDomTree(); +#endif + } /// Interchange OuterLoop and InnerLoop. bool transform(); @@ -426,6 +434,7 @@ DominatorTree *DT; BasicBlock *LoopExit; bool InnerLoopHasReduction; + std::vector DTUpdates; }; // Main LoopInterchange Pass. @@ -573,7 +582,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,6 +1273,23 @@ } } +/// \brief Update BI to jump to NewBB instead of OldBB. Records updates to +/// the dominator tree in DTUpdates. +static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB, + BasicBlock *NewBB, + std::vector &DTUpdates) { + unsigned NumSucc = BI->getNumSuccessors(); + for (unsigned i = 0; i < NumSucc; ++i) { + if (BI->getSuccessor(i) == OldBB) { + DTUpdates.push_back( + {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB}); + DTUpdates.push_back( + {DominatorTree::UpdateKind::Delete, BI->getParent(), OldBB}); + BI->setSuccessor(i, NewBB); + } + } +} + bool LoopInterchangeTransform::adjustLoopBranches() { DEBUG(dbgs() << "adjustLoopBranches called\n"); // Adjust the loop preheader @@ -1306,27 +1331,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 +1350,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 +1371,13 @@ 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); - } - return true; }