From e16912e0d0fc3e004565010d6bcf51112bd89227 Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Thu, 17 Aug 2017 16:45:35 +0000 Subject: [PATCH] [Dominators] Teach LoopUnswitch to use the incremental API Summary: This patch makes LoopUnswitch use new incremental API for updating dominators. It also updates SplitCriticalEdge, as it is called in LoopUnswitch. There doesn't seem to be any noticeable performance difference when bootstrapping clang with this patch. Reviewers: dberlin, davide, sanjoy, grosser, chandlerc Reviewed By: davide, grosser Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35528 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@311093 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnswitch.cpp | 58 +++++++++++++++++++------ lib/Transforms/Utils/BreakCriticalEdges.cpp | 66 +++++++---------------------- 2 files changed, 60 insertions(+), 64 deletions(-) diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index e434b863ff6..4a48d90e716 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -237,7 +237,7 @@ namespace { void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, - Instruction *InsertPt, + BranchInst *OldBranch, TerminatorInst *TI); void SimplifyCode(std::vector &Worklist, Loop *L); @@ -518,9 +518,6 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { Changed |= processCurrentLoop(); } while(redoLoop); - // FIXME: Reconstruct dom info, because it is not preserved properly. - if (Changed) - DT->recalculate(*F); return Changed; } @@ -896,31 +893,59 @@ static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, } /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst, -/// otherwise branch to FalseDest. Insert the code immediately before InsertPt. +/// otherwise branch to FalseDest. Insert the code immediately before OldBranch +/// and remove (but not erase!) it from the function. void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, - Instruction *InsertPt, + BranchInst *OldBranch, TerminatorInst *TI) { + assert(OldBranch->isUnconditional() && "Preheader is not split correctly"); // Insert a conditional branch on LIC to the two preheaders. The original // code is the true version and the new code is the false version. Value *BranchVal = LIC; bool Swapped = false; if (!isa(Val) || Val->getType() != Type::getInt1Ty(LIC->getContext())) - BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val); + BranchVal = new ICmpInst(OldBranch, ICmpInst::ICMP_EQ, LIC, Val); else if (Val != ConstantInt::getTrue(Val->getContext())) { // We want to enter the new loop when the condition is true. std::swap(TrueDest, FalseDest); Swapped = true; } + // Old branch will be removed, so save its parent and successor to update the + // DomTree. + auto *OldBranchSucc = OldBranch->getSuccessor(0); + auto *OldBranchParent = OldBranch->getParent(); + // Insert the new branch. BranchInst *BI = - IRBuilder<>(InsertPt).CreateCondBr(BranchVal, TrueDest, FalseDest, TI); + IRBuilder<>(OldBranch).CreateCondBr(BranchVal, TrueDest, FalseDest, TI); if (Swapped) BI->swapProfMetadata(); + // Remove the old branch so there is only one branch at the end. This is + // needed to perform DomTree's internal DFS walk on the function's CFG. + OldBranch->removeFromParent(); + + // Inform the DT about the new branch. + if (DT) { + // First, add both successors. + SmallVector Updates; + if (TrueDest != OldBranchParent) + Updates.push_back({DominatorTree::Insert, OldBranchParent, TrueDest}); + if (FalseDest != OldBranchParent) + Updates.push_back({DominatorTree::Insert, OldBranchParent, FalseDest}); + // If both of the new successors are different from the old one, inform the + // DT that the edge was deleted. + if (OldBranchSucc != TrueDest && OldBranchSucc != FalseDest) { + Updates.push_back({DominatorTree::Delete, OldBranchParent, OldBranchSucc}); + } + + DT->applyUpdates(Updates); + } + // If either edge is critical, split it. This helps preserve LoopSimplify // form for enclosing loops. auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA(); @@ -960,10 +985,14 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, // Okay, now we have a position to branch from and a position to branch to, // insert the new conditional branch. - EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, - loopPreheader->getTerminator(), TI); - LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L); - loopPreheader->getTerminator()->eraseFromParent(); + auto *OldBranch = dyn_cast(loopPreheader->getTerminator()); + assert(OldBranch && "Failed to split the preheader"); + EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI); + LPM->deleteSimpleAnalysisValue(OldBranch, L); + + // EmitPreheaderBranchOnCondition removed the OldBranch from the function. + // Delete it, as it is no longer needed. + delete OldBranch; // We need to reprocess this loop, it could be unswitched again. redoLoop = true; @@ -1278,7 +1307,10 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR, TI); LPM->deleteSimpleAnalysisValue(OldBR, L); - OldBR->eraseFromParent(); + + // The OldBr was replaced by a new one and removed (but not erased) by + // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it. + delete OldBR; LoopProcessWorklist.push_back(NewLoop); redoLoop = true; diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp index 175cbd2ce0d..417a771cf95 100644 --- a/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -198,59 +198,23 @@ llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (!DT && !LI) return NewBB; - // Now update analysis information. Since the only predecessor of NewBB is - // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate - // anything, as there are other successors of DestBB. However, if all other - // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a - // loop header) then NewBB dominates DestBB. - SmallVector OtherPreds; - - // If there is a PHI in the block, loop over predecessors with it, which is - // faster than iterating pred_begin/end. - if (PHINode *PN = dyn_cast(DestBB->begin())) { - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (PN->getIncomingBlock(i) != NewBB) - OtherPreds.push_back(PN->getIncomingBlock(i)); - } else { - for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); - I != E; ++I) { - BasicBlock *P = *I; - if (P != NewBB) - OtherPreds.push_back(P); - } - } - - bool NewBBDominatesDestBB = true; - - // Should we update DominatorTree information? if (DT) { - DomTreeNode *TINode = DT->getNode(TIBB); - - // The new block is not the immediate dominator for any other nodes, but - // TINode is the immediate dominator for the new node. + // Update the DominatorTree. + // ---> NewBB -----\ + // / V + // TIBB -------\\------> DestBB // - if (TINode) { // Don't break unreachable code! - DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); - DomTreeNode *DestBBNode = nullptr; - - // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. - if (!OtherPreds.empty()) { - DestBBNode = DT->getNode(DestBB); - while (!OtherPreds.empty() && NewBBDominatesDestBB) { - if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) - NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); - OtherPreds.pop_back(); - } - OtherPreds.clear(); - } - - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. - if (NewBBDominatesDestBB) { - if (!DestBBNode) DestBBNode = DT->getNode(DestBB); - DT->changeImmediateDominator(DestBBNode, NewBBNode); - } - } + // First, inform the DT about the new path from TIBB to DestBB via NewBB, + // then delete the old edge from TIBB to DestBB. By doing this in that order + // DestBB stays reachable in the DT the whole time and its subtree doesn't + // get disconnected. + SmallVector Updates; + Updates.push_back({DominatorTree::Insert, TIBB, NewBB}); + Updates.push_back({DominatorTree::Insert, NewBB, DestBB}); + if (llvm::find(successors(TIBB), DestBB) == succ_end(TIBB)) + Updates.push_back({DominatorTree::Delete, TIBB, DestBB}); + + DT->applyUpdates(Updates); } // Update LoopInfo if it is around. -- 2.11.0