diff options
| -rw-r--r-- | include/llvm/IR/DomTreeUpdater.h | 43 | ||||
| -rw-r--r-- | lib/IR/DomTreeUpdater.cpp | 43 | ||||
| -rw-r--r-- | unittests/IR/DomTreeUpdaterTest.cpp | 10 |
3 files changed, 57 insertions, 39 deletions
diff --git a/include/llvm/IR/DomTreeUpdater.h b/include/llvm/IR/DomTreeUpdater.h index 089c8528794..91a7658a15f 100644 --- a/include/llvm/IR/DomTreeUpdater.h +++ b/include/llvm/IR/DomTreeUpdater.h @@ -76,26 +76,27 @@ public: bool hasPendingUpdates() const; /// Returns true if there are DominatorTree updates queued. - /// Returns false under Eager UpdateStrategy. + /// Returns false under Eager UpdateStrategy or DT is nullptr. bool hasPendingDomTreeUpdates() const; /// Returns true if there are PostDominatorTree updates queued. - /// Returns false under Eager UpdateStrategy. + /// Returns false under Eager UpdateStrategy or PDT is nullptr. bool hasPendingPostDomTreeUpdates() const; /// Apply updates on all available trees. Under Eager UpdateStrategy with /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will - /// discard duplicated updates and self-dominance updates. The Eager - /// Strategy applies the updates immediately while the Lazy Strategy - /// queues the updates. It is required for the state of - /// the LLVM IR to be updated *before* applying the Updates because the - /// internal update routine will analyze the current state of the relationship - /// between a pair of (From, To) BasicBlocks to determine whether a single - /// update needs to be discarded. + /// discard duplicated updates and self-dominance updates. If both DT and PDT + /// are nullptrs, this function discards all updates. The Eager Strategy + /// applies the updates immediately while the Lazy Strategy queues the + /// updates. It is required for the state of the LLVM IR to be updated + /// *before* applying the Updates because the internal update routine will + /// analyze the current state of the relationship between a pair of (From, To) + /// BasicBlocks to determine whether a single update needs to be discarded. void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates, bool ForceRemoveDuplicates = false); - /// Notify all available trees on an edge insertion. Under either Strategy, + /// Notify all available trees on an edge insertion. If both DT and PDT are + /// nullptrs, this function discards the update. Under either Strategy, /// self-dominance update will be removed. The Eager Strategy applies /// the update immediately while the Lazy Strategy queues the update. /// It is recommended to only use this method when you have exactly one @@ -106,17 +107,18 @@ public: void insertEdge(BasicBlock *From, BasicBlock *To); /// Notify all available trees on an edge insertion. - /// Under either Strategy, these updates will be discard silently in the - /// following sequence + /// Under either Strategy, the following updates will be discard silently /// 1. Invalid - Inserting an edge that does not exist in the CFG. /// 2. Self-dominance update. + /// 3. Both DT and PDT are nullptrs. /// The Eager Strategy applies the update immediately while the Lazy Strategy /// queues the update. It is recommended to only use this method when you have /// exactly one insertion (and no deletions) and want to discard an invalid - /// update. Returns true if the update is valid. - bool insertEdgeRelaxed(BasicBlock *From, BasicBlock *To); + /// update. + void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To); - /// Notify all available trees on an edge deletion. Under either Strategy, + /// Notify all available trees on an edge deletion. If both DT and PDT are + /// nullptrs, this function discards the update. Under either Strategy, /// self-dominance update will be removed. The Eager Strategy applies /// the update immediately while the Lazy Strategy queues the update. /// It is recommended to only use this method when you have exactly one @@ -127,21 +129,22 @@ public: void deleteEdge(BasicBlock *From, BasicBlock *To); /// Notify all available trees on an edge deletion. - /// Under either Strategy, these updates will be discard silently in the - /// following sequence: + /// Under either Strategy, the following updates will be discard silently /// 1. Invalid - Deleting an edge that still exists in the CFG. /// 2. Self-dominance update. + /// 3. Both DT and PDT are nullptrs. /// The Eager Strategy applies the update immediately while the Lazy Strategy /// queues the update. It is recommended to only use this method when you have /// exactly one deletion (and no insertions) and want to discard an invalid - /// update. Returns true if the update is valid. - bool deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To); + /// update. + void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To); /// Delete DelBB. DelBB will be removed from its Parent and /// erased from available trees if it exists and finally get deleted. /// Under Eager UpdateStrategy, DelBB will be processed immediately. /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and - /// all available trees are up-to-date. + /// all available trees are up-to-date. When both DT and PDT are nullptrs, + /// DelBB will be queued until flush() is called. void deleteBB(BasicBlock *DelBB); /// Delete DelBB. DelBB will be removed from its Parent and diff --git a/lib/IR/DomTreeUpdater.cpp b/lib/IR/DomTreeUpdater.cpp index ffdb5c7e0b1..51dd24bccfa 100644 --- a/lib/IR/DomTreeUpdater.cpp +++ b/lib/IR/DomTreeUpdater.cpp @@ -56,6 +56,8 @@ bool DomTreeUpdater::isSelfDominance( bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, BasicBlock *To) { + assert(DT || + PDT && "Call applyLazyUpdate() when both DT and PDT are nullptrs."); assert(Strategy == DomTreeUpdater::UpdateStrategy::Lazy && "Call applyLazyUpdate() with Eager strategy error"); // Analyze pending updates to determine if the update is unnecessary. @@ -260,6 +262,9 @@ void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) { void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates, bool ForceRemoveDuplicates) { + if (!DT && !PDT) + return; + if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) { SmallVector<DominatorTree::UpdateType, 8> Seen; for (const auto U : Updates) @@ -310,6 +315,9 @@ void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) { "Inserted edge does not appear in the CFG"); #endif + if (!DT && !PDT) + return; + // Won't affect DomTree and PostDomTree; discard update. if (From == To) return; @@ -325,23 +333,25 @@ void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) { applyLazyUpdate(DominatorTree::Insert, From, To); } -bool DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { - if (!isUpdateValid({DominatorTree::Insert, From, To})) - return false; - +void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { if (From == To) - return true; + return; + + if (!DT && !PDT) + return; + + if (!isUpdateValid({DominatorTree::Insert, From, To})) + return; if (Strategy == UpdateStrategy::Eager) { if (DT) DT->insertEdge(From, To); if (PDT) PDT->insertEdge(From, To); - return true; + return; } applyLazyUpdate(DominatorTree::Insert, From, To); - return true; } void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { @@ -351,6 +361,9 @@ void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { "Deleted edge still exists in the CFG!"); #endif + if (!DT && !PDT) + return; + // Won't affect DomTree and PostDomTree; discard update. if (From == To) return; @@ -366,23 +379,25 @@ void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { applyLazyUpdate(DominatorTree::Delete, From, To); } -bool DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { - if (!isUpdateValid({DominatorTree::Delete, From, To})) - return false; - +void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { if (From == To) - return true; + return; + + if (!DT && !PDT) + return; + + if (!isUpdateValid({DominatorTree::Delete, From, To})) + return; if (Strategy == UpdateStrategy::Eager) { if (DT) DT->deleteEdge(From, To); if (PDT) PDT->deleteEdge(From, To); - return true; + return; } applyLazyUpdate(DominatorTree::Delete, From, To); - return true; } void DomTreeUpdater::dropOutOfDateUpdates() { diff --git a/unittests/IR/DomTreeUpdaterTest.cpp b/unittests/IR/DomTreeUpdaterTest.cpp index 10d84442617..03b6b529fd8 100644 --- a/unittests/IR/DomTreeUpdaterTest.cpp +++ b/unittests/IR/DomTreeUpdaterTest.cpp @@ -72,8 +72,8 @@ TEST(DomTreeUpdater, EagerUpdateBasicOperations) { SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator()); ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; - ASSERT_FALSE(DTU.insertEdgeRelaxed(BB0, BB0)); - ASSERT_TRUE(DTU.deleteEdgeRelaxed(BB0, BB0)); + DTU.insertEdgeRelaxed(BB0, BB0); + DTU.deleteEdgeRelaxed(BB0, BB0); // Delete edge bb0 -> bb3 and push the update twice to verify duplicate // entries are discarded. @@ -106,9 +106,9 @@ TEST(DomTreeUpdater, EagerUpdateBasicOperations) { ASSERT_FALSE(DTU.hasPendingUpdates()); // Invalid Insert: no edge bb1 -> bb2 after change to bb0. - ASSERT_FALSE(DTU.insertEdgeRelaxed(BB1, BB2)); + DTU.insertEdgeRelaxed(BB1, BB2); // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. - ASSERT_FALSE(DTU.deleteEdgeRelaxed(BB0, BB1)); + DTU.deleteEdgeRelaxed(BB0, BB1); // DTU working with Eager UpdateStrategy does not need to flush. ASSERT_TRUE(DT.verify()); @@ -183,7 +183,7 @@ TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) { EXPECT_EQ(F->begin()->getName(), NewEntry->getName()); EXPECT_TRUE(&F->getEntryBlock() == NewEntry); - ASSERT_TRUE(DTU.insertEdgeRelaxed(NewEntry, BB0)); + DTU.insertEdgeRelaxed(NewEntry, BB0); // Changing the Entry BB requires a full recalculation of DomTree. DTU.recalculate(*F); |