Index: llvm/include/llvm/Analysis/DomTreeUpdater.h =================================================================== --- llvm/include/llvm/Analysis/DomTreeUpdater.h +++ llvm/include/llvm/Analysis/DomTreeUpdater.h @@ -29,19 +29,29 @@ explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) - : DT(&DT_), Strategy(Strategy_) {} + : DT(&DT_), Strategy(Strategy_) { + EntryBlock = &DT->Parent->getEntryBlock(); + } DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) - : DT(DT_), Strategy(Strategy_) {} + : DT(DT_), Strategy(Strategy_) { + if (DT) + EntryBlock = &DT->Parent->getEntryBlock(); + } DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) : PDT(&PDT_), Strategy(Strategy_) {} DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) : PDT(PDT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, UpdateStrategy Strategy_) - : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} + : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) { + EntryBlock = &DT->Parent->getEntryBlock(); + } DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, UpdateStrategy Strategy_) - : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} + : DT(DT_), PDT(PDT_), Strategy(Strategy_) { + if (DT) + EntryBlock = &DT->Parent->getEntryBlock(); + } ~DomTreeUpdater() { flush(); } @@ -124,9 +134,9 @@ void applyUpdates(ArrayRef Updates, bool ForceRemoveDuplicates = false); - /// Notify DTU that the entry block was replaced. /// Recalculate all available trees and flush all BasicBlocks - /// awaiting deletion immediately. + /// awaiting deletion immediately. It is only used when you insert + /// a new BasicBlock to be the entry block without making other changes. void recalculate(Function &F); /// \deprecated { Submit an edge insertion to all available trees. The Eager @@ -207,7 +217,6 @@ /// Apply all pending updates to available trees and flush all BasicBlocks /// awaiting deletion. - void flush(); ///@} @@ -232,6 +241,8 @@ } }; + BasicBlock *EntryBlock = nullptr; + bool NeedRecalculate = false; SmallVector PendUpdates; size_t PendDTUpdateIndex = 0; size_t PendPDTUpdateIndex = 0; @@ -243,6 +254,15 @@ bool IsRecalculatingDomTree = false; bool IsRecalculatingPostDomTree = false; + /// If the entry block is changed, recalculate available trees. + /// Returns true if available trees are recalculated. + bool checkEntryBlockChange(); + + /// Notify DTU that the entry block was replaced. + /// Recalculate all available trees and flush all BasicBlocks + /// awaiting deletion immediately. + void internalrecalculate(); + /// First remove all the instructions of DelBB and then make sure DelBB has a /// valid terminator instruction which is necessary to have when DelBB still /// has to be inside of its parent Function while awaiting deletion under Lazy Index: llvm/include/llvm/Support/GenericDomTree.h =================================================================== --- llvm/include/llvm/Support/GenericDomTree.h +++ llvm/include/llvm/Support/GenericDomTree.h @@ -249,8 +249,9 @@ mutable unsigned int SlowQueries = 0; friend struct DomTreeBuilder::SemiNCAInfo; + friend class DomTreeUpdater; - public: +public: DominatorTreeBase() {} DominatorTreeBase(DominatorTreeBase &&Arg) Index: llvm/lib/Analysis/DomTreeUpdater.cpp =================================================================== --- llvm/lib/Analysis/DomTreeUpdater.cpp +++ llvm/lib/Analysis/DomTreeUpdater.cpp @@ -104,6 +104,14 @@ } void DomTreeUpdater::flush() { + if (isLazy() && NeedRecalculate) { + internalrecalculate(); + return; + } + + if (checkEntryBlockChange()) + return; + applyDomTreeUpdates(); applyPostDomTreeUpdates(); dropOutOfDateUpdates(); @@ -151,13 +159,34 @@ return true; } -void DomTreeUpdater::recalculate(Function &F) { +bool DomTreeUpdater::checkEntryBlockChange() { + // There is no DT. + if (!DT) + return false; + + BasicBlock *CurrentEntryBlock = &DT->Parent->getEntryBlock(); + if (CurrentEntryBlock != EntryBlock) { + internalrecalculate(); + return true; + } + + return false; +} + +void DomTreeUpdater::recalculate(Function &F) { internalrecalculate(); } + +void DomTreeUpdater::internalrecalculate() { + + NeedRecalculate = false; + + if (DT) + EntryBlock = &DT->Parent->getEntryBlock(); if (Strategy == UpdateStrategy::Eager) { if (DT) - DT->recalculate(F); + DT->recalculate(*DT->Parent); if (PDT) - PDT->recalculate(F); + PDT->recalculate(*PDT->Parent); return; } @@ -171,9 +200,9 @@ // flush awaiting deleted BasicBlocks. forceFlushDeletedBB(); if (DT) - DT->recalculate(F); + DT->recalculate(*DT->Parent); if (PDT) - PDT->recalculate(F); + PDT->recalculate(*PDT->Parent); // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; @@ -210,22 +239,30 @@ // Eager, the BasicBlock will be deleted immediately. void DomTreeUpdater::deleteBB(BasicBlock *DelBB) { validateDeleteBB(DelBB); + bool IsEntryBlock = DelBB == EntryBlock; if (Strategy == UpdateStrategy::Lazy) { DeletedBBs.insert(DelBB); + if (IsEntryBlock) + NeedRecalculate = true; return; } DelBB->removeFromParent(); eraseDelBBNode(DelBB); delete DelBB; + if (IsEntryBlock) + internalrecalculate(); } void DomTreeUpdater::callbackDeleteBB( BasicBlock *DelBB, std::function Callback) { validateDeleteBB(DelBB); + bool IsEntryBlock = DelBB == EntryBlock; if (Strategy == UpdateStrategy::Lazy) { Callbacks.push_back(CallBackOnDeletion(DelBB, Callback)); DeletedBBs.insert(DelBB); + if (IsEntryBlock) + NeedRecalculate = true; return; } @@ -233,6 +270,8 @@ eraseDelBBNode(DelBB); Callback(DelBB); delete DelBB; + if (IsEntryBlock) + internalrecalculate(); } void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) { @@ -263,6 +302,9 @@ void DomTreeUpdater::applyUpdates(ArrayRef Updates, bool ForceRemoveDuplicates) { + if (isEager() && checkEntryBlockChange()) + return; + if (!DT && !PDT) return; @@ -297,6 +339,14 @@ DominatorTree &DomTreeUpdater::getDomTree() { assert(DT && "Invalid acquisition of a null DomTree"); + if (isLazy() && NeedRecalculate) { + internalrecalculate(); + return *DT; + } + + if (checkEntryBlockChange()) + return *DT; + applyDomTreeUpdates(); dropOutOfDateUpdates(); return *DT; @@ -304,6 +354,14 @@ PostDominatorTree &DomTreeUpdater::getPostDomTree() { assert(PDT && "Invalid acquisition of a null PostDomTree"); + if (isLazy() && NeedRecalculate) { + internalrecalculate(); + return *PDT; + } + + if (checkEntryBlockChange()) + return *PDT; + applyPostDomTreeUpdates(); dropOutOfDateUpdates(); return *PDT; @@ -316,6 +374,9 @@ "Inserted edge does not appear in the CFG"); #endif + if (isEager() && checkEntryBlockChange()) + return; + if (!DT && !PDT) return; @@ -335,6 +396,9 @@ } void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { + if (isEager() && checkEntryBlockChange()) + return; + if (From == To) return; @@ -362,6 +426,9 @@ "Deleted edge still exists in the CFG!"); #endif + if (isEager() && checkEntryBlockChange()) + return; + if (!DT && !PDT) return; @@ -381,6 +448,9 @@ } void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { + if (isEager() && checkEntryBlockChange()) + return; + if (From == To) return; Index: llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp =================================================================== --- llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp +++ llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp @@ -573,6 +573,7 @@ NewEntry->takeName(OldEntry); OldEntry->setName("tailrecurse"); BranchInst *BI = BranchInst::Create(OldEntry, NewEntry); + DTU.insertEdge(NewEntry, OldEntry); BI->setDebugLoc(CI->getDebugLoc()); // If this tail call is marked 'tail' and if there are any allocas in the @@ -599,10 +600,6 @@ PN->addIncoming(&*I, NewEntry); ArgumentPHIs.push_back(PN); } - // The entry block was changed from OldEntry to NewEntry. - // The forward DominatorTree needs to be recalculated when the EntryBB is - // changed. In this corner-case we recalculate the entire tree. - DTU.recalculate(*NewEntry->getParent()); } // If this function has self recursive calls in the tail position where some Index: llvm/lib/Transforms/Utils/Local.cpp =================================================================== --- llvm/lib/Transforms/Utils/Local.cpp +++ llvm/lib/Transforms/Utils/Local.cpp @@ -735,14 +735,8 @@ "applying corresponding DTU updates."); DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); DTU->deleteBB(PredBB); - // Recalculation of DomTree is needed when updating a forward DomTree and - // the Entry BB is replaced. - if (ReplaceEntryBB && DTU->hasDomTree()) { - // The entry block was removed and there is no external interface for - // the dominator tree to be notified of this change. In this corner-case - // we recalculate the entire tree. - DTU->recalculate(*(DestBB->getParent())); - } + if (ReplaceEntryBB) + DTU->flush(); } else { Index: llvm/unittests/Analysis/DomTreeUpdaterTest.cpp =================================================================== --- llvm/unittests/Analysis/DomTreeUpdaterTest.cpp +++ llvm/unittests/Analysis/DomTreeUpdaterTest.cpp @@ -185,7 +185,7 @@ DTU.insertEdgeRelaxed(NewEntry, BB0); // Changing the Entry BB requires a full recalculation of DomTree. - DTU.recalculate(*F); + DTU.flush(); ASSERT_TRUE(DT.verify()); ASSERT_TRUE(PDT.verify()); @@ -561,7 +561,7 @@ DTU.insertEdge(NewEntry, BB0); // Changing the Entry BB requires a full recalculation. - DTU.recalculate(*F); + DTU.flush(); ASSERT_TRUE(DTU.getDomTree().verify()); ASSERT_TRUE(DTU.getPostDomTree().verify());