summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/IR/Dominators.h6
-rw-r--r--llvm/include/llvm/Support/GenericDomTree.h46
-rw-r--r--llvm/include/llvm/Support/GenericDomTreeConstruction.h223
-rw-r--r--llvm/lib/IR/Dominators.cpp5
-rw-r--r--llvm/unittests/IR/DominatorTreeTest.cpp127
5 files changed, 396 insertions, 11 deletions
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h
index 72369541dcc..5b21a2c83e4 100644
--- a/llvm/include/llvm/IR/Dominators.h
+++ b/llvm/include/llvm/IR/Dominators.h
@@ -51,6 +51,12 @@ extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
BasicBlock *From,
BasicBlock *To);
+extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
+ BasicBlock *To);
+extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
+ BasicBlock *From,
+ BasicBlock *To);
+
extern template bool Verify<BBDomTree>(const BBDomTree &DT);
extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT);
} // namespace DomTreeBuilder
diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h
index a5dafd39d8e..df06ac170fe 100644
--- a/llvm/include/llvm/Support/GenericDomTree.h
+++ b/llvm/include/llvm/Support/GenericDomTree.h
@@ -194,6 +194,10 @@ template <class DomTreeT>
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
typename DomTreeT::NodePtr To);
+template <class DomTreeT>
+void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To);
+
template <typename DomTreeT>
bool Verify(const DomTreeT &DT);
} // namespace DomTreeBuilder
@@ -211,6 +215,8 @@ class DominatorTreeBase {
DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *RootNode;
+ using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
+ ParentPtr Parent = nullptr;
mutable bool DFSInfoValid = false;
mutable unsigned int SlowQueries = 0;
@@ -229,18 +235,20 @@ class DominatorTreeBase {
DominatorTreeBase(DominatorTreeBase &&Arg)
: Roots(std::move(Arg.Roots)),
DomTreeNodes(std::move(Arg.DomTreeNodes)),
- RootNode(std::move(Arg.RootNode)),
- DFSInfoValid(std::move(Arg.DFSInfoValid)),
- SlowQueries(std::move(Arg.SlowQueries)) {
+ RootNode(Arg.RootNode),
+ Parent(Arg.Parent),
+ DFSInfoValid(Arg.DFSInfoValid),
+ SlowQueries(Arg.SlowQueries) {
Arg.wipe();
}
DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
Roots = std::move(RHS.Roots);
DomTreeNodes = std::move(RHS.DomTreeNodes);
- RootNode = std::move(RHS.RootNode);
- DFSInfoValid = std::move(RHS.DFSInfoValid);
- SlowQueries = std::move(RHS.SlowQueries);
+ RootNode = RHS.RootNode;
+ Parent = RHS.Parent;
+ DFSInfoValid = RHS.DFSInfoValid;
+ SlowQueries = RHS.SlowQueries;
RHS.wipe();
return *this;
}
@@ -261,6 +269,7 @@ class DominatorTreeBase {
/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
bool compare(const DominatorTreeBase &Other) const {
+ if (Parent != Other.Parent) return true;
const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
if (DomTreeNodes.size() != OtherDomTreeNodes.size())
@@ -453,15 +462,37 @@ class DominatorTreeBase {
/// This function has to be called just before or just after making the update
/// on the actual CFG. There cannot be any other updates that the dominator
/// tree doesn't know about.
+ ///
/// Note that for postdominators it automatically takes care of inserting
/// a reverse edge internally (so there's no need to swap the parameters).
///
void insertEdge(NodeT *From, NodeT *To) {
assert(From);
assert(To);
+ assert(From->getParent() == Parent);
+ assert(To->getParent() == Parent);
DomTreeBuilder::InsertEdge(*this, From, To);
}
+ /// Inform the dominator tree about a CFG edge deletion and update the tree.
+ ///
+ /// This function has to be called just after making the update
+ /// on the actual CFG. There cannot be any other updates that the dominator
+ /// tree doesn't know about. The only exception is when the deletion that the
+ /// tree is informed about makes some (domominator) subtree unreachable -- in
+ /// this case, it is fine to perform deletions within this subtree.
+ ///
+ /// Note that for postdominators it automatically takes care of deleting
+ /// a reverse edge internally (so there's no need to swap the parameters).
+ ///
+ void deleteEdge(NodeT *From, NodeT *To) {
+ assert(From);
+ assert(To);
+ assert(From->getParent() == Parent);
+ assert(To->getParent() == Parent);
+ DomTreeBuilder::DeleteEdge(*this, From, To);
+ }
+
/// Add a new node to the dominator tree information.
///
/// This creates a new node as a child of DomBB dominator node, linking it
@@ -622,6 +653,7 @@ public:
template <class FT> void recalculate(FT &F) {
using TraitsTy = GraphTraits<FT *>;
reset();
+ Parent = &F;
if (!IsPostDominator) {
// Initialize root
@@ -647,6 +679,7 @@ public:
DomTreeNodes.clear();
Roots.clear();
RootNode = nullptr;
+ Parent = nullptr;
DFSInfoValid = false;
SlowQueries = 0;
}
@@ -728,6 +761,7 @@ public:
void wipe() {
DomTreeNodes.clear();
RootNode = nullptr;
+ Parent = nullptr;
}
};
diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
index 45c4c2300f4..220b777b883 100644
--- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h
+++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h
@@ -106,7 +106,7 @@ struct SemiNCAInfo {
// Add a new tree node for this NodeT, and link it as a child of
// IDomNode
return (DT.DomTreeNodes[BB] = IDomNode->addChild(
- llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
+ llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
.get();
}
@@ -327,6 +327,17 @@ struct SemiNCAInfo {
}
}
+ void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
+ NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
+ for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
+ const NodePtr N = NumToNode[i];
+ const TreeNodePtr TN = DT.getNode(N);
+ assert(TN);
+ const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
+ TN->setIDom(NewIDom);
+ }
+ }
+
// Helper struct used during edge insertions.
struct InsertionInfo {
using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
@@ -338,7 +349,7 @@ struct SemiNCAInfo {
};
std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
- DecreasingLevel>
+ DecreasingLevel>
Bucket; // Queue of tree nodes sorted by level in descending order.
SmallDenseSet<TreeNodePtr, 8> Affected;
SmallDenseSet<TreeNodePtr, 8> Visited;
@@ -415,7 +426,7 @@ struct SemiNCAInfo {
assert(TN->getBlock());
for (const NodePtr Succ :
- ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
+ ChildrenGetter<NodePtr, IsPostDom>::Get(TN->getBlock())) {
const TreeNodePtr SuccTN = DT.getNode(Succ);
assert(SuccTN && "Unreachable successor found at reachable insertion");
const unsigned SuccLevel = SuccTN->getLevel();
@@ -468,7 +479,7 @@ struct SemiNCAInfo {
}
}
- // Handles insertion to previousely unreachable nodes.
+ // Handles insertion to previously unreachable nodes.
static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From,
const NodePtr To) {
DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
@@ -498,7 +509,7 @@ struct SemiNCAInfo {
static void ComputeUnreachableDominators(
DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming,
SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
- &DiscoveredConnectingEdges) {
+ &DiscoveredConnectingEdges) {
assert(!DT.getNode(Root) && "Root must not be reachable");
// Visit only previously unreachable nodes.
@@ -554,6 +565,201 @@ struct SemiNCAInfo {
return true;
}
+ static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) {
+ assert(From && To && "Cannot disconnect nullptrs");
+ DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
+ << BlockNamePrinter(To) << "\n");
+ const TreeNodePtr FromTN = DT.getNode(From);
+ // Deletion in an unreachable subtree -- nothing to do.
+ if (!FromTN) return;
+
+ const TreeNodePtr ToTN = DT.getNode(To);
+ const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
+ const TreeNodePtr NCD = DT.getNode(NCDBlock);
+
+ // To dominates From -- nothing to do.
+ if (ToTN == NCD) return;
+
+ const TreeNodePtr ToIDom = ToTN->getIDom();
+ DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
+ << BlockNamePrinter(ToIDom) << "\n");
+
+ // To remains reachable after deletion.
+ // (Based on the caption under Figure 4. from the second paper.)
+ if (FromTN != ToIDom || HasProperSupport(DT, ToTN))
+ DeleteReachable(DT, FromTN, ToTN);
+ else
+ DeleteUnreachable(DT, ToTN);
+ }
+
+ // Handles deletions that leave destination nodes reachable.
+ static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN,
+ const TreeNodePtr ToTN) {
+ DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> "
+ << BlockNamePrinter(ToTN) << "\n");
+ DEBUG(dbgs() << "\tRebuilding subtree\n");
+
+ // Find the top of the subtree that needs to be rebuilt.
+ // (Based on the lemma 2.6 from the second paper.)
+ const NodePtr ToIDom =
+ DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
+ assert(ToIDom || DT.isPostDominator());
+ const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
+ assert(ToIDomTN);
+ const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
+ // Top of the subtree to rebuild is the root node. Rebuild the tree from
+ // scratch.
+ if (!PrevIDomSubTree) {
+ DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
+ DT.recalculate(*DT.Parent);
+ return;
+ }
+
+ // Only visit nodes in the subtree starting at To.
+ const unsigned Level = ToIDomTN->getLevel();
+ auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
+ return DT.getNode(To)->getLevel() > Level;
+ };
+
+ DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n");
+
+ SemiNCAInfo SNCA;
+ SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0);
+ DEBUG(dbgs() << "\tRunning Semi-NCA\n");
+ SNCA.runSemiNCA(DT, Level);
+ SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
+ }
+
+ // Checks if a node has proper support, as defined on the page 3 and later
+ // explained on the page 7 of the second paper.
+ static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) {
+ DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n");
+ for (const NodePtr Pred :
+ ChildrenGetter<NodePtr, !IsPostDom>::Get(TN->getBlock())) {
+ DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
+ if (!DT.getNode(Pred)) continue;
+
+ const NodePtr Support =
+ DT.findNearestCommonDominator(TN->getBlock(), Pred);
+ DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
+ if (Support != TN->getBlock()) {
+ DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
+ << " is reachable from support "
+ << BlockNamePrinter(Support) << "\n");
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ // Handle deletions that make destination node unreachable.
+ // (Based on the lemma 2.7 from the second paper.)
+ static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) {
+ DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN)
+ << "\n");
+ assert(ToTN);
+ assert(ToTN->getBlock());
+
+ SmallVector<NodePtr, 16> AffectedQueue;
+ const unsigned Level = ToTN->getLevel();
+
+ // Traverse destination node's descendants with greater level in the tree
+ // and collect visited nodes.
+ auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
+ const TreeNodePtr TN = DT.getNode(To);
+ assert(TN);
+ if (TN->getLevel() > Level) return true;
+ if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
+ AffectedQueue.push_back(To);
+
+ return false;
+ };
+
+ SemiNCAInfo SNCA;
+ unsigned LastDFSNum =
+ SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0);
+
+ TreeNodePtr MinNode = ToTN;
+
+ // Identify the top of the subtree to rebuilt by finding the NCD of all
+ // the affected nodes.
+ for (const NodePtr N : AffectedQueue) {
+ const TreeNodePtr TN = DT.getNode(N);
+ const NodePtr NCDBlock =
+ DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
+ assert(NCDBlock || DT.isPostDominator());
+ const TreeNodePtr NCD = DT.getNode(NCDBlock);
+ assert(NCD);
+
+ DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
+ << " with NCD = " << BlockNamePrinter(NCD)
+ << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
+ if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
+ }
+
+ // Root reached, rebuild the whole tree from scratch.
+ if (!MinNode->getIDom()) {
+ DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
+ DT.recalculate(*DT.Parent);
+ return;
+ }
+
+ // Erase the unreachable subtree in reverse preorder to process all children
+ // before deleting their parent.
+ for (unsigned i = LastDFSNum; i > 0; --i) {
+ const NodePtr N = SNCA.NumToNode[i];
+ const TreeNodePtr TN = DT.getNode(N);
+ DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
+
+ EraseNode(DT, TN);
+ }
+
+ // The affected subtree start at the To node -- there's no extra work to do.
+ if (MinNode == ToTN) return;
+
+ DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
+ << BlockNamePrinter(MinNode) << "\n");
+ const unsigned MinLevel = MinNode->getLevel();
+ const TreeNodePtr PrevIDom = MinNode->getIDom();
+ assert(PrevIDom);
+ SNCA.clear();
+
+ // Identify nodes that remain in the affected subtree.
+ auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
+ const TreeNodePtr ToTN = DT.getNode(To);
+ return ToTN && ToTN->getLevel() > MinLevel;
+ };
+ SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0);
+
+ DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom)
+ << "\nRunning Semi-NCA\n");
+
+ // Rebuild the remaining part of affected subtree.
+ SNCA.runSemiNCA(DT, MinLevel);
+ SNCA.reattachExistingSubtree(DT, PrevIDom);
+ }
+
+ // Removes leaf tree nodes from the dominator tree.
+ static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
+ assert(TN);
+ assert(TN->getNumChildren() == 0 && "Not a tree leaf");
+
+ const TreeNodePtr IDom = TN->getIDom();
+ assert(IDom);
+
+ auto ChIt = llvm::find(IDom->Children, TN);
+ assert(ChIt != IDom->Children.end());
+ std::swap(*ChIt, IDom->Children.back());
+ IDom->Children.pop_back();
+
+ DT.DomTreeNodes.erase(TN->getBlock());
+ }
+
+ //~~
+ //===--------------- DomTree correctness verification ---------------------===
+ //~~
+
// Check if for every parent with a level L in the tree all of its children
// have level L + 1.
static bool VerifyLevels(const DomTreeT &DT) {
@@ -740,6 +946,13 @@ void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
}
template <class DomTreeT>
+void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
+ typename DomTreeT::NodePtr To) {
+ if (DT.isPostDominator()) std::swap(From, To);
+ SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To);
+}
+
+template <class DomTreeT>
bool Verify(const DomTreeT &DT) {
SemiNCAInfo<DomTreeT> SNCA;
return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
diff --git a/llvm/lib/IR/Dominators.cpp b/llvm/lib/IR/Dominators.cpp
index d6675cf128a..4d7e3040ecd 100644
--- a/llvm/lib/IR/Dominators.cpp
+++ b/llvm/lib/IR/Dominators.cpp
@@ -76,6 +76,11 @@ template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
+template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
+ DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To);
+template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
+ DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
+
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
const DomTreeBuilder::BBDomTree &DT);
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp
index 2adc09af2c5..bdeeffde152 100644
--- a/llvm/unittests/IR/DominatorTreeTest.cpp
+++ b/llvm/unittests/IR/DominatorTreeTest.cpp
@@ -327,6 +327,7 @@ TEST(DominatorTree, NonUniqueEdges) {
namespace {
const auto Insert = CFGBuilder::ActionKind::Insert;
+const auto Delete = CFGBuilder::ActionKind::Delete;
bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {
return std::tie(A.Action, A.Edge.From, A.Edge.To) <
@@ -448,3 +449,129 @@ TEST(DominatorTree, InsertPermut) {
}
}
}
+
+TEST(DominatorTree, DeleteReachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"},
+ {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Delete);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.deleteEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.deleteEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, DeleteUnreachable) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ EXPECT_EQ(LastUpdate->Action, Delete);
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ DT.deleteEdge(From, To);
+ EXPECT_TRUE(DT.verify());
+ PDT.deleteEdge(From, To);
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertDelete) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
+ {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},
+ {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},
+ {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};
+
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ if (LastUpdate->Action == Insert) {
+ DT.insertEdge(From, To);
+ PDT.insertEdge(From, To);
+ } else {
+ DT.deleteEdge(From, To);
+ PDT.deleteEdge(From, To);
+ }
+
+ EXPECT_TRUE(DT.verify());
+ EXPECT_TRUE(PDT.verify());
+ }
+}
+
+TEST(DominatorTree, InsertDeleteExhaustive) {
+ std::vector<CFGBuilder::Arc> Arcs = {
+ {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
+ {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
+
+ std::vector<CFGBuilder::Update> Updates = {
+ {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
+ {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}},
+ {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}},
+ {Delete, {"8", "9"}}, {Delete, {"11", "12"}}};
+
+ std::mt19937 Generator(0);
+ for (unsigned i = 0; i < 16; ++i) {
+ std::shuffle(Updates.begin(), Updates.end(), Generator);
+ CFGHolder Holder;
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+ PostDomTree PDT(*Holder.F);
+ EXPECT_TRUE(PDT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate())) {
+ BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
+ BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
+ if (LastUpdate->Action == Insert) {
+ DT.insertEdge(From, To);
+ PDT.insertEdge(From, To);
+ } else {
+ DT.deleteEdge(From, To);
+ PDT.deleteEdge(From, To);
+ }
+
+ EXPECT_TRUE(DT.verify());
+ EXPECT_TRUE(PDT.verify());
+ }
+ }
+}
OpenPOWER on IntegriCloud