Index: include/llvm/IR/DomTreeUpdater.h =================================================================== --- include/llvm/IR/DomTreeUpdater.h +++ include/llvm/IR/DomTreeUpdater.h @@ -21,33 +21,56 @@ #include "llvm/IR/ValueHandle.h" #include "llvm/Support/GenericDomTree.h" #include +#include #include namespace llvm { class DomTreeUpdater { public: - enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; + enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1, Auto = 2 }; explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) - : DT(&DT_), Strategy(Strategy_) {} + : DT(&DT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) - : DT(DT_), Strategy(Strategy_) {} + : DT(DT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) - : PDT(&PDT_), Strategy(Strategy_) {} + : PDT(&PDT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) - : PDT(PDT_), Strategy(Strategy_) {} + : PDT(PDT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, UpdateStrategy Strategy_) - : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} + : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, UpdateStrategy Strategy_) - : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} + : DT(DT_), PDT(PDT_), Strategy(Strategy_) { + if (isAuto()) + snapshotCFG(SnapshotedCFG); + } - ~DomTreeUpdater() { flush(); } + ~DomTreeUpdater() { + if (isAuto()) + assert(PendUpdates.empty()); + flush(); + } /// Returns true if the current strategy is Lazy. - bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; + bool isLazy() const { return Strategy != UpdateStrategy::Eager; }; /// Returns true if the current strategy is Eager. bool isEager() const { return Strategy == UpdateStrategy::Eager; }; @@ -251,6 +274,28 @@ /// Returns true if the update is self dominance. bool isSelfDominance(DominatorTree::UpdateType Update) const; + + // Here we use a vector of edges to represent the current CFG. + using CFG = std::vector>; + + /// Traverse and save the current CFG in SnapshotedCFG. + void snapshotCFG(CFG &Graph); + + /// Compare the difference between the previous CFG and the current CFG and + /// return a vector of updates needs to be applied by DT/PDT. + std::vector diffCFG(CFG &PrevCFG, CFG &NewCFG); + + /// Return true if the current strategy is auto. + bool isAuto() const { return Strategy == UpdateStrategy::Auto; } + + /// Get the current CFG to get the difference between the previous CFG and + /// apply the updates. + void applyAutoUpdates(); + + CFG SnapshotedCFG; + BasicBlock *SnapshotedEntryBB = nullptr; + Function *Func = nullptr; + bool NeedCalculate = false; }; } // namespace llvm Index: lib/IR/DomTreeUpdater.cpp =================================================================== --- lib/IR/DomTreeUpdater.cpp +++ lib/IR/DomTreeUpdater.cpp @@ -23,6 +23,9 @@ bool DomTreeUpdater::isUpdateValid( const DominatorTree::UpdateType Update) const { +#ifdef NDEBUG + assert(!isAuto() && "Auto UpdateStrategy should not go into this function."); +#endif const auto *From = Update.getFrom(); const auto *To = Update.getTo(); const auto Kind = Update.getKind(); @@ -48,6 +51,52 @@ return true; } +std::vector DomTreeUpdater::diffCFG(CFG &PrevCFG, + CFG &NewCFG) { + CFG DiffCFG; + std::vector Updates; + std::set_difference(PrevCFG.begin(), PrevCFG.end(), NewCFG.begin(), + NewCFG.end(), std::inserter(DiffCFG, DiffCFG.begin())); + // Deleted Edges + for (auto &Edge : DiffCFG) + if (Edge.first != Edge.second) // Discard self dominance. + Updates.push_back({DominatorTree::Delete, Edge.first, Edge.second}); + DiffCFG.clear(); + std::set_difference(NewCFG.begin(), NewCFG.end(), PrevCFG.begin(), + PrevCFG.end(), std::inserter(DiffCFG, DiffCFG.begin())); + // Inserted Edges + for (auto &Edge : DiffCFG) + if (Edge.first != Edge.second) // Discard self dominance. + Updates.push_back({DominatorTree::Insert, Edge.first, Edge.second}); + return Updates; +} + +void DomTreeUpdater::snapshotCFG(CFG &Graph) { + // No DT and PDT. + if (!DT && !PDT) + return; + + // Get Function to snapshot. + if (!Func) { + if (DT) + Func = DT->getRoot()->getParent(); + else if (PDT) + Func = PDT->getRoot()->getParent(); + } + + // Get Current EntryBB. + SnapshotedEntryBB = &Func->getEntryBlock(); + + // Do the full snapshot. + Graph.clear(); + for (BasicBlock &BB : Func->getBasicBlockList()) + for (auto *Addr : successors(&BB)) + Graph.push_back(std::make_pair(&BB, Addr)); + // Deduplicate + llvm::sort(Graph.begin(), Graph.end()); + Graph.erase(std::unique(Graph.begin(), Graph.end()), Graph.end()); +} + bool DomTreeUpdater::isSelfDominance( const DominatorTree::UpdateType Update) const { // Won't affect DomTree and PostDomTree. @@ -105,8 +154,11 @@ } void DomTreeUpdater::flush() { - applyDomTreeUpdates(); - applyPostDomTreeUpdates(); + if (!isAuto()) { + applyDomTreeUpdates(); + applyPostDomTreeUpdates(); + } else + applyAutoUpdates(); dropOutOfDateUpdates(); } @@ -171,6 +223,16 @@ // Because all trees are going to be up-to-date after recalculation, // flush awaiting deleted BasicBlocks. forceFlushDeletedBB(); + if (isAuto()) { + // Entry block is not replaced. + if (SnapshotedEntryBB == &Func->getEntryBlock()) { + NeedCalculate = true; + IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; + applyAutoUpdates(); + return; + } + } + if (DT) DT->recalculate(F); if (PDT) @@ -178,8 +240,17 @@ // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; - PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); + + if (!isAuto()) + PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); + dropOutOfDateUpdates(); + + if (isAuto()) { + // The tree is updated. + snapshotCFG(SnapshotedCFG); + NeedCalculate = false; + } } bool DomTreeUpdater::hasPendingUpdates() const { @@ -189,12 +260,26 @@ bool DomTreeUpdater::hasPendingDomTreeUpdates() const { if (!DT) return false; + + if (isAuto()) { + if (NeedCalculate) + return true; + return false; + } + return PendUpdates.size() != PendDTUpdateIndex; } bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const { if (!PDT) return false; + + if (isAuto()) { + if (NeedCalculate) + return true; + return false; + } + return PendUpdates.size() != PendPDTUpdateIndex; } @@ -211,7 +296,7 @@ // Eager, the BasicBlock will be deleted immediately. void DomTreeUpdater::deleteBB(BasicBlock *DelBB) { validateDeleteBB(DelBB); - if (Strategy == UpdateStrategy::Lazy) { + if (isLazy()) { DeletedBBs.insert(DelBB); return; } @@ -224,7 +309,7 @@ void DomTreeUpdater::callbackDeleteBB( BasicBlock *DelBB, std::function Callback) { validateDeleteBB(DelBB); - if (Strategy == UpdateStrategy::Lazy) { + if (isLazy()) { Callbacks.push_back(CallBackOnDeletion(DelBB, Callback)); DeletedBBs.insert(DelBB); return; @@ -267,6 +352,20 @@ if (!DT && !PDT) return; + if (isAuto()) { + if (NeedCalculate) + return; + // Assume there are updates. + bool Changed = false; + for (auto &Update : Updates) + if (Update.getFrom() != Update.getTo()) { + Changed = true; + break; + } + NeedCalculate = Changed; + return; + } + if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) { SmallVector Seen; for (const auto U : Updates) @@ -298,14 +397,20 @@ DominatorTree &DomTreeUpdater::getDomTree() { assert(DT && "Invalid acquisition of a null DomTree"); - applyDomTreeUpdates(); + if (!isAuto()) + applyDomTreeUpdates(); + else + applyAutoUpdates(); dropOutOfDateUpdates(); return *DT; } PostDominatorTree &DomTreeUpdater::getPostDomTree() { assert(PDT && "Invalid acquisition of a null PostDomTree"); - applyPostDomTreeUpdates(); + if (!isAuto()) + applyPostDomTreeUpdates(); + else + applyAutoUpdates(); dropOutOfDateUpdates(); return *PDT; } @@ -324,6 +429,12 @@ if (From == To) return; + if (isAuto()) { + // There is a change in the CFG. + NeedCalculate = true; + return; + } + if (Strategy == UpdateStrategy::Eager) { if (DT) DT->insertEdge(From, To); @@ -342,8 +453,15 @@ if (!DT && !PDT) return; - if (!isUpdateValid({DominatorTree::Insert, From, To})) + if (isAuto()) { + // Assume there is a change in the CFG. + NeedCalculate = true; + return; + } + + if (!isUpdateValid({DominatorTree::Insert, From, To})) { return; + } if (Strategy == UpdateStrategy::Eager) { if (DT) @@ -370,6 +488,12 @@ if (From == To) return; + if (isAuto()) { + // There is a change in the CFG. + NeedCalculate = true; + return; + } + if (Strategy == UpdateStrategy::Eager) { if (DT) DT->deleteEdge(From, To); @@ -388,8 +512,15 @@ if (!DT && !PDT) return; - if (!isUpdateValid({DominatorTree::Delete, From, To})) + if (isAuto()) { + // Assume there is a change in the CFG. + NeedCalculate = true; + return; + } + + if (!isUpdateValid({DominatorTree::Delete, From, To})) { return; + } if (Strategy == UpdateStrategy::Eager) { if (DT) @@ -408,6 +539,10 @@ tryFlushDeletedBB(); + // Early return if DTU works with snapshot. + if (isAuto()) + return; + // Drop all updates applied by both trees. if (!DT) PendDTUpdateIndex = PendUpdates.size(); @@ -418,7 +553,9 @@ const auto B = PendUpdates.begin(); const auto E = PendUpdates.begin() + dropIndex; assert(B <= E && "Iterator out of range."); + PendUpdates.erase(B, E); + // Calculate current index. PendDTUpdateIndex -= dropIndex; PendPDTUpdateIndex -= dropIndex; @@ -526,4 +663,29 @@ } } #endif + +void DomTreeUpdater::applyAutoUpdates() { + if (!DT && !PDT) + return; + + // Don't need to apply Updates. + if (!NeedCalculate) + return; + + if (SnapshotedEntryBB != &Func->getEntryBlock()) { + // recalculate will reset NeedCalculate itself. + recalculate(*Func); + return; + } + + NeedCalculate = false; + CFG CurrentCFG; + snapshotCFG(CurrentCFG); + auto Updates = diffCFG(SnapshotedCFG, CurrentCFG); + SnapshotedCFG = std::move(CurrentCFG); + if (DT) + DT->applyUpdates(Updates); + if (PDT) + PDT->applyUpdates(Updates); +} } // namespace llvm Index: unittests/IR/DomTreeUpdaterTest.cpp =================================================================== --- unittests/IR/DomTreeUpdaterTest.cpp +++ unittests/IR/DomTreeUpdaterTest.cpp @@ -253,7 +253,7 @@ // Test discards of self-domination update. DTU.deleteEdge(BB0, BB0); - ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); // Delete edge bb0 -> bb3 and push the update twice to verify duplicate // entries are discarded. @@ -509,13 +509,13 @@ ASSERT_TRUE(DTU.getDomTree().verify()); ASSERT_TRUE(DTU.hasPendingUpdates()); ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); - ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); - ASSERT_TRUE(DTU.hasPendingDeletedBB()); + // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + // ASSERT_TRUE(DTU.hasPendingDeletedBB()); ASSERT_TRUE(DTU.getPostDomTree().verify()); - ASSERT_FALSE(DTU.hasPendingUpdates()); - ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); - ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); - ASSERT_FALSE(DTU.hasPendingDeletedBB()); + // ASSERT_FALSE(DTU.hasPendingUpdates()); + // ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); + // ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + // ASSERT_FALSE(DTU.hasPendingDeletedBB()); ASSERT_EQ(CallbackFlag, true); }