Index: llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -237,7 +237,7 @@ 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 @@ 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 @@ } /// 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 @@ // 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 @@ 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; Index: llvm/trunk/lib/Transforms/Utils/BreakCriticalEdges.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ llvm/trunk/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -198,59 +198,23 @@ 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(); - } + // 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}); - // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it - // doesn't dominate anything. - if (NewBBDominatesDestBB) { - if (!DestBBNode) DestBBNode = DT->getNode(DestBB); - DT->changeImmediateDominator(DestBBNode, NewBBNode); - } - } + DT->applyUpdates(Updates); } // Update LoopInfo if it is around.