Index: llvm/trunk/include/llvm/Analysis/DomTreeUpdater.h
===================================================================
--- llvm/trunk/include/llvm/Analysis/DomTreeUpdater.h
+++ llvm/trunk/include/llvm/Analysis/DomTreeUpdater.h
@@ -103,8 +103,24 @@
/// Although GenericDomTree provides several update primitives,
/// it is not encouraged to use these APIs directly.
- /// Submit updates to all available trees. Under Eager UpdateStrategy with
- /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
+ /// Submit updates to all available trees.
+ /// The Eager Strategy flushes updates immediately while the Lazy Strategy
+ /// queues the updates.
+ ///
+ /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
+ /// in sync with + all updates before that single update.
+ ///
+ /// CAUTION!
+ /// 1. It is required for the state of the LLVM IR to be updated
+ /// *before* submitting the updates because the internal update routine will
+ /// analyze the current state of the CFG to determine whether an update
+ /// is valid.
+ /// 2. It is illegal to submit any update that has already been submitted,
+ /// i.e., you are supposed not to insert an existent edge or delete a
+ /// nonexistent edge.
+ void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
+
+ /// Submit updates to all available trees. It will also
/// 1. discard duplicated updates,
/// 2. remove invalid updates. (Invalid updates means deletion of an edge that
/// still exists or insertion of an edge that does not exist.)
@@ -122,8 +138,10 @@
/// 2. It is illegal to submit any update that has already been submitted,
/// i.e., you are supposed not to insert an existent edge or delete a
/// nonexistent edge.
- void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
- bool ForceRemoveDuplicates = false);
+ /// 3. It is only legal to submit updates to an edge in the order CFG changes
+ /// are made. The order you submit updates on different edges is not
+ /// restricted.
+ void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);
/// Notify DTU that the entry block was replaced.
/// Recalculate all available trees and flush all BasicBlocks
@@ -149,7 +167,7 @@
/// submitted. }
LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From,
BasicBlock *To),
- "Use applyUpdates() instead.");
+ "Use applyUpdatesPermissive() instead.");
/// \deprecated { Submit an edge deletion to all available trees. The Eager
/// Strategy flushes this update immediately while the Lazy Strategy queues
@@ -171,7 +189,7 @@
/// submitted. }
LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From,
BasicBlock *To),
- "Use applyUpdates() instead.");
+ "Use applyUpdatesPermissive() instead.");
/// Delete DelBB. DelBB will be removed from its Parent and
/// erased from available trees if it exists and finally get deleted.
@@ -260,11 +278,6 @@
/// Returns true if at least one BasicBlock is deleted.
bool forceFlushDeletedBB();
- /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
- /// UpdateStrategy. Returns true if the update is queued for update.
- bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
- BasicBlock *To);
-
/// Helper function to apply all pending DomTree updates.
void applyDomTreeUpdates();
Index: llvm/trunk/lib/Analysis/DomTreeUpdater.cpp
===================================================================
--- llvm/trunk/lib/Analysis/DomTreeUpdater.cpp
+++ llvm/trunk/lib/Analysis/DomTreeUpdater.cpp
@@ -12,11 +12,13 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/ADT/SmallSet.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Support/GenericDomTree.h"
#include <algorithm>
#include <functional>
+#include <utility>
namespace llvm {
@@ -53,41 +55,6 @@
return Update.getFrom() == Update.getTo();
}
-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.
- const DominatorTree::UpdateType Update = {Kind, From, To};
- const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
- ? DominatorTree::Insert
- : DominatorTree::Delete,
- From, To};
- // Only check duplicates in updates that are not applied by both trees.
- auto I =
- PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
- const auto E = PendUpdates.end();
-
- assert(I <= E && "Iterator out of range.");
-
- for (; I != E; ++I) {
- if (Update == *I)
- return false; // Discard duplicate updates.
-
- if (Invert == *I) {
- // Update and Invert are both valid (equivalent to a no-op). Remove
- // Invert from PendUpdates and discard the Update.
- PendUpdates.erase(I);
- return false;
- }
- }
-
- PendUpdates.push_back(Update); // Save the valid update.
- return true;
-}
-
void DomTreeUpdater::applyDomTreeUpdates() {
// No pending DomTreeUpdates.
if (Strategy != UpdateStrategy::Lazy || !DT)
@@ -261,31 +228,15 @@
new UnreachableInst(DelBB->getContext(), DelBB);
}
-void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
- bool ForceRemoveDuplicates) {
+void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
if (!DT && !PDT)
return;
- if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
- SmallVector<DominatorTree::UpdateType, 8> Seen;
+ if (Strategy == UpdateStrategy::Lazy) {
for (const auto U : Updates)
- // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
- // on analysis.
- if (llvm::none_of(
- Seen,
- [U](const DominatorTree::UpdateType S) { return S == U; }) &&
- isUpdateValid(U) && !isSelfDominance(U)) {
- Seen.push_back(U);
- if (Strategy == UpdateStrategy::Lazy)
- applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
- }
- if (Strategy == UpdateStrategy::Lazy)
- return;
+ if (!isSelfDominance(U))
+ PendUpdates.push_back(U);
- if (DT)
- DT->applyUpdates(Seen);
- if (PDT)
- PDT->applyUpdates(Seen);
return;
}
@@ -295,6 +246,60 @@
PDT->applyUpdates(Updates);
}
+void DomTreeUpdater::applyUpdatesPermissive(
+ ArrayRef<DominatorTree::UpdateType> Updates) {
+ if (!DT && !PDT)
+ return;
+
+ SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
+ SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
+ for (const auto U : Updates) {
+ auto Edge = std::make_pair(U.getFrom(), U.getTo());
+ // Because it is illegal to submit updates that have already been applied
+ // and updates to an edge need to be strictly ordered,
+ // it is safe to infer the existence of an edge from the first update
+ // to this edge.
+ // If the first update to an edge is "Delete", it means that the edge
+ // existed before. If the first update to an edge is "Insert", it means
+ // that the edge didn't exist before.
+ //
+ // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
+ // because
+ // 1. it is illegal to submit updates that have already been applied,
+ // i.e., user cannot delete an nonexistent edge,
+ // 2. updates to an edge need to be strictly ordered,
+ // So, initially edge A -> B existed.
+ // We can then safely ignore future updates to this edge and directly
+ // inspect the current CFG:
+ // a. If the edge still exists, because the user cannot insert an existent
+ // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
+ // resulted in a no-op. DTU won't submit any update in this case.
+ // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
+ // actually happened but {Insert, A, B} was an invalid update which never
+ // happened. DTU will submit {Delete, A, B} in this case.
+ if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
+ Seen.insert(Edge);
+ // If the update doesn't appear in the CFG, it means that
+ // either the change isn't made or relevant operations
+ // result in a no-op.
+ if (isUpdateValid(U)) {
+ if (isLazy())
+ PendUpdates.push_back(U);
+ else
+ DeduplicatedUpdates.push_back(U);
+ }
+ }
+ }
+
+ if (Strategy == UpdateStrategy::Lazy)
+ return;
+
+ if (DT)
+ DT->applyUpdates(DeduplicatedUpdates);
+ if (PDT)
+ PDT->applyUpdates(DeduplicatedUpdates);
+}
+
DominatorTree &DomTreeUpdater::getDomTree() {
assert(DT && "Invalid acquisition of a null DomTree");
applyDomTreeUpdates();
@@ -331,7 +336,7 @@
return;
}
- applyLazyUpdate(DominatorTree::Insert, From, To);
+ PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -352,7 +357,7 @@
return;
}
- applyLazyUpdate(DominatorTree::Insert, From, To);
+ PendUpdates.push_back({DominatorTree::Insert, From, To});
}
void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
@@ -377,7 +382,7 @@
return;
}
- applyLazyUpdate(DominatorTree::Delete, From, To);
+ PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
@@ -398,7 +403,7 @@
return;
}
- applyLazyUpdate(DominatorTree::Delete, From, To);
+ PendUpdates.push_back({DominatorTree::Delete, From, To});
}
void DomTreeUpdater::dropOutOfDateUpdates() {
Index: llvm/trunk/lib/Transforms/Scalar/CallSiteSplitting.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/CallSiteSplitting.cpp
+++ llvm/trunk/lib/Transforms/Scalar/CallSiteSplitting.cpp
@@ -366,7 +366,7 @@
assert(Splits.size() == 2 && "Expected exactly 2 splits!");
for (unsigned i = 0; i < Splits.size(); i++) {
Splits[i]->getTerminator()->eraseFromParent();
- DTU.applyUpdates({{DominatorTree::Delete, Splits[i], TailBB}});
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
}
// Erase the tail block once done with musttail patching
Index: llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -373,7 +373,7 @@
++NumDeadCases;
Changed = true;
if (--SuccessorsCount[Succ] == 0)
- DTU.applyUpdates({{DominatorTree::Delete, BB, Succ}});
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, Succ}});
continue;
}
if (State == LazyValueInfo::True) {
Index: llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp
+++ llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp
@@ -1091,7 +1091,7 @@
<< "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
@@ -1159,7 +1159,8 @@
ConstantInt::getFalse(CondCmp->getType());
ReplaceFoldableUses(CondCmp, CI);
}
- DTU->applyUpdates({{DominatorTree::Delete, BB, ToRemoveSucc}});
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, BB, ToRemoveSucc}});
return true;
}
@@ -1246,7 +1247,7 @@
RemoveSucc->removePredecessor(BB);
BranchInst::Create(KeepSucc, BI);
BI->eraseFromParent();
- DTU->applyUpdates({{DominatorTree::Delete, BB, RemoveSucc}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
return true;
}
CurrentBB = CurrentPred;
@@ -1676,7 +1677,7 @@
Instruction *Term = BB->getTerminator();
BranchInst::Create(OnlyDest, Term);
Term->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
// If the condition is now dead due to the removal of the old terminator,
// erase it.
@@ -2018,9 +2019,9 @@
}
// Enqueue required DT updates.
- DTU->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
- {DominatorTree::Insert, PredBB, NewBB},
- {DominatorTree::Delete, PredBB, BB}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, SuccBB},
+ {DominatorTree::Insert, PredBB, NewBB},
+ {DominatorTree::Delete, PredBB, BB}});
// If there were values defined in BB that are used outside the block, then we
// now have to update all uses of the value to use either the original value,
@@ -2114,7 +2115,7 @@
BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
}
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return NewBBs[0];
}
@@ -2387,7 +2388,7 @@
// Remove the unconditional branch at the end of the PredBB block.
OldPredBranch->eraseFromParent();
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
++NumDupes;
return true;
@@ -2423,8 +2424,8 @@
// The select is now dead.
SI->eraseFromParent();
- DTU->applyUpdates({{DominatorTree::Insert, NewBB, BB},
- {DominatorTree::Insert, Pred, NewBB}});
+ DTU->applyUpdatesPermissive({{DominatorTree::Insert, NewBB, BB},
+ {DominatorTree::Insert, Pred, NewBB}});
// Update any other PHI nodes in BB.
for (BasicBlock::iterator BI = BB->begin();
@@ -2601,7 +2602,7 @@
Updates.push_back({DominatorTree::Delete, BB, Succ});
Updates.push_back({DominatorTree::Insert, SplitBB, Succ});
}
- DTU->applyUpdates(Updates);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
return false;
Index: llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -101,7 +101,7 @@
DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
for (BasicBlock *BB : BBs)
if (DTU)
@@ -235,7 +235,7 @@
isa<UnreachableInst>(BB->getTerminator()) &&
"The successor list of BB isn't empty before "
"applying corresponding DTU updates.");
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(BB);
}
Index: llvm/trunk/lib/Transforms/Utils/Local.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Utils/Local.cpp
+++ llvm/trunk/lib/Transforms/Utils/Local.cpp
@@ -128,8 +128,7 @@
Builder.CreateBr(Destination);
BI->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, OldDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, OldDest}});
return true;
}
@@ -205,8 +204,8 @@
i = SI->removeCase(i);
e = SI->case_end();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, ParentBB, DefaultDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, ParentBB, DefaultDest}});
continue;
}
@@ -254,7 +253,7 @@
if (DeleteDeadConditions)
RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
@@ -332,7 +331,7 @@
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return true;
}
}
@@ -666,8 +665,7 @@
if (PhiIt != OldPhiIt) PhiIt = &BB->front();
}
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, Pred, BB}});
}
/// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
@@ -736,7 +734,7 @@
isa<UnreachableInst>(PredBB->getTerminator()) &&
"The successor list of PredBB isn't empty before "
"applying corresponding DTU updates.");
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(PredBB);
// Recalculation of DomTree is needed when updating a forward DomTree and
// the Entry BB is replaced.
@@ -1078,7 +1076,7 @@
"applying corresponding DTU updates.");
if (DTU) {
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
DTU->deleteBB(BB);
} else {
BB->eraseFromParent(); // Delete the old basic block.
@@ -1942,7 +1940,7 @@
++NumInstrsRemoved;
}
if (DTU)
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
return NumInstrsRemoved;
}
@@ -1970,8 +1968,7 @@
UnwindDestBB->removePredecessor(BB);
II->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDestBB}});
}
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
@@ -2118,8 +2115,8 @@
UnwindDestBB->removePredecessor(II->getParent());
II->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDestBB}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(
+ {{DominatorTree::Delete, BB, UnwindDestBB}});
} else
changeToCall(II, DTU);
Changed = true;
@@ -2208,8 +2205,7 @@
TI->replaceAllUsesWith(NewTI);
TI->eraseFromParent();
if (DTU)
- DTU->applyUpdates({{DominatorTree::Delete, BB, UnwindDest}},
- /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, UnwindDest}});
}
/// removeUnreachableBlocks - Remove blocks that are not reachable, even
@@ -2274,7 +2270,7 @@
}
if (DTU) {
- DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->applyUpdatesPermissive(Updates);
bool Deleted = false;
for (auto *BB : DeadBlockSet) {
if (DTU->isBBPendingDeletion(BB))
Index: llvm/trunk/unittests/Analysis/DomTreeUpdaterTest.cpp
===================================================================
--- llvm/trunk/unittests/Analysis/DomTreeUpdaterTest.cpp
+++ llvm/trunk/unittests/Analysis/DomTreeUpdaterTest.cpp
@@ -71,9 +71,9 @@
SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
- DTU.applyUpdates(
- {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}},
- /*ForceRemoveDuplicates*/ true);
+ DTU.applyUpdatesPermissive(
+ {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}});
+ ASSERT_FALSE(DTU.hasPendingUpdates());
// Delete edge bb0 -> bb3 and push the update twice to verify duplicate
// entries are discarded.
@@ -102,14 +102,13 @@
// queued for deletion.
ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
- DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU.applyUpdatesPermissive(Updates);
ASSERT_FALSE(DTU.hasPendingUpdates());
// Invalid Insert: no edge bb1 -> bb2 after change to bb0.
// Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
- DTU.applyUpdates(
- {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}},
- /*ForceRemoveDuplicates*/ true);
+ DTU.applyUpdatesPermissive(
+ {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, BB0, BB1}});
// DTU working with Eager UpdateStrategy does not need to flush.
ASSERT_TRUE(DT.verify());
@@ -184,8 +183,7 @@
EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
- DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}},
- /*ForceRemoveDuplicates*/ true);
+ DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
// Changing the Entry BB requires a full recalculation of DomTree.
DTU.recalculate(*F);
@@ -254,7 +252,7 @@
BasicBlock *BB3 = &*FI++;
// Test discards of self-domination update.
- DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
+ DTU.applyUpdatesPermissive({{DominatorTree::Insert, BB0, BB0}});
ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
// Delete edge bb0 -> bb3 and push the update twice to verify duplicate
@@ -277,7 +275,7 @@
// Verify. Updates to DTU must be applied *after* all changes to the CFG
// (including block deletion).
- DTU.applyUpdates(Updates);
+ DTU.applyUpdatesPermissive(Updates);
ASSERT_TRUE(DTU.getDomTree().verify());
// Deletion of a BasicBlock is an immediate event. We remove all uses to the
@@ -362,9 +360,9 @@
//
// While the final CFG form is functionally identical the updates to
// DTU are not. In the first case we must have
- // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in the
- // latter case we must *NOT* have DTU.applyUpdates({{DominatorTree::Insert,
- // Pred1, Succ}}).
+ // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in
+ // the latter case we must *NOT* have
+ // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).
// CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
// remove bb2.
@@ -384,9 +382,9 @@
BasicBlocks.end());
};
ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
- // Remove bb2 from F. This has to happen before the call to applyUpdates() for
- // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
- // method converts bb2's TI into "unreachable".
+ // Remove bb2 from F. This has to happen before the call to
+ // applyUpdates() for DTU to detect there is no longer an edge between
+ // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
DTU.callbackDeleteBB(BB2, Eraser);
@@ -407,9 +405,9 @@
BranchInst::Create(BB3, BB0);
EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
- // Remove bb1 from F. This has to happen before the call to applyUpdates() for
- // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
- // method converts bb1's TI into "unreachable".
+ // Remove bb1 from F. This has to happen before the call to
+ // applyUpdates() for DTU to detect there is no longer an edge between
+ // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
DTU.callbackDeleteBB(BB1, Eraser);
@@ -424,7 +422,7 @@
Updates.push_back({DominatorTree::Delete, BB1, BB3});
// Verify everything.
- DTU.applyUpdates(Updates);
+ DTU.applyUpdatesPermissive(Updates);
ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
DTU.flush();
ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
@@ -509,7 +507,7 @@
// Verify. Updates to DTU must be applied *after* all changes to the CFG
// (including block deletion).
- DTU.applyUpdates(Updates);
+ DTU.applyUpdatesPermissive(Updates);
ASSERT_TRUE(DTU.getDomTree().verify());
ASSERT_TRUE(DTU.hasPendingUpdates());
ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
@@ -648,8 +646,7 @@
SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
- // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
- // entries are discarded.
+ // Delete edge bb0 -> bb3.
std::vector<DominatorTree::UpdateType> Updates;
Updates.reserve(1);
Updates.push_back({DominatorTree::Delete, BB0, BB3});
@@ -694,7 +691,7 @@
++i;
}
- DTU.applyUpdates(Updates);
+ DTU.applyUpdatesPermissive(Updates);
// flush PostDomTree
ASSERT_TRUE(DTU.getPostDomTree().verify());
ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
@@ -729,3 +726,69 @@
DTU.recalculate(*F);
ASSERT_FALSE(DTU.hasPendingDeletedBB());
}
+
+TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
+ StringRef FuncName = "f";
+ StringRef ModuleString = R"(
+ define i32 @f() {
+ bb0:
+ br label %bb1
+ bb1:
+ ret i32 1
+ bb2:
+ ret i32 1
+ }
+ )";
+ // Make the module.
+ LLVMContext Context;
+ std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+ Function *F = M->getFunction(FuncName);
+
+ // Make the DTU.
+ DominatorTree DT(*F);
+ DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
+ ASSERT_TRUE(DTU.getDomTree().verify());
+
+ Function::iterator FI = F->begin();
+ BasicBlock *BB0 = &*FI++;
+ BasicBlock *BB1 = &*FI++;
+ BasicBlock *BB2 = &*FI++;
+
+ // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
+ EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+ BB0->getTerminator()->eraseFromParent();
+ BranchInst::Create(BB1, BB0);
+ EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+
+ // Update the DTU and simulate duplicates.
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
+ {DominatorTree::Delete, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1}});
+
+ // The above operations result in a no-op.
+ ASSERT_FALSE(DTU.hasPendingUpdates());
+
+ // Update the DTU. Simulate an invalid update.
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}});
+ ASSERT_FALSE(DTU.hasPendingUpdates());
+
+ // CFG Change: remove bb0 -> bb1.
+ EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+ BB0->getTerminator()->eraseFromParent();
+
+ // Update the DTU and simulate invalid updates.
+ DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1},
+ {DominatorTree::Delete, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1},
+ {DominatorTree::Insert, BB0, BB1}});
+ ASSERT_TRUE(DTU.hasPendingUpdates());
+
+ // CFG Change: add bb0 -> bb2.
+ BranchInst::Create(BB2, BB0);
+ EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
+ DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});
+ ASSERT_TRUE(DTU.getDomTree().verify());
+}