Skip to content

Commit 624463a

Browse files
kuharkuhar
committedAug 16, 2017
[Dominators] Introduce batch updates
Summary: This patch introduces a way of informing the (Post)DominatorTree about multiple CFG updates that happened since the last tree update. This makes performing tree updates much easier, as it internally takes care of applying the updates in lockstep with the (virtual) updates to the CFG, which is done by reverse-applying future CFG updates. The batch updater is able to remove redundant updates that cancel each other out. In the future, it should be also possible to reorder updates to reduce the amount of work needed to perform the updates. Reviewers: dberlin, sanjoy, grosser, davide, brzycki Reviewed By: brzycki Subscribers: mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D36167 llvm-svn: 311015
1 parent 9e54b70 commit 624463a

File tree

6 files changed

+667
-96
lines changed

6 files changed

+667
-96
lines changed
 

‎llvm/include/llvm/IR/Dominators.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,10 @@ namespace DomTreeBuilder {
4141
using BBDomTree = DomTreeBase<BasicBlock>;
4242
using BBPostDomTree = PostDomTreeBase<BasicBlock>;
4343

44+
extern template struct Update<BasicBlock *>;
45+
46+
using BBUpdates = ArrayRef<Update<BasicBlock *>>;
47+
4448
extern template void Calculate<BBDomTree>(BBDomTree &DT);
4549
extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
4650

@@ -56,6 +60,9 @@ extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
5660
BasicBlock *From,
5761
BasicBlock *To);
5862

63+
extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
64+
extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
65+
5966
extern template bool Verify<BBDomTree>(const BBDomTree &DT);
6067
extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT);
6168
} // namespace DomTreeBuilder

‎llvm/include/llvm/Support/GenericDomTree.h

Lines changed: 82 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -24,12 +24,6 @@
2424
#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
2525
#define LLVM_SUPPORT_GENERICDOMTREE_H
2626

27-
#include "llvm/ADT/DenseMap.h"
28-
#include "llvm/ADT/GraphTraits.h"
29-
#include "llvm/ADT/STLExtras.h"
30-
#include "llvm/ADT/SmallPtrSet.h"
31-
#include "llvm/ADT/SmallVector.h"
32-
#include "llvm/Support/raw_ostream.h"
3327
#include <algorithm>
3428
#include <cassert>
3529
#include <cstddef>
@@ -38,14 +32,21 @@
3832
#include <type_traits>
3933
#include <utility>
4034
#include <vector>
35+
#include "llvm/ADT/DenseMap.h"
36+
#include "llvm/ADT/GraphTraits.h"
37+
#include "llvm/ADT/PointerIntPair.h"
38+
#include "llvm/ADT/STLExtras.h"
39+
#include "llvm/ADT/SmallPtrSet.h"
40+
#include "llvm/ADT/SmallVector.h"
41+
#include "llvm/Support/raw_ostream.h"
4142

4243
namespace llvm {
4344

4445
template <typename NodeT, bool IsPostDom>
4546
class DominatorTreeBase;
4647

4748
namespace DomTreeBuilder {
48-
template <class DomTreeT>
49+
template <typename DomTreeT>
4950
struct SemiNCAInfo;
5051
} // namespace DomTreeBuilder
5152

@@ -190,14 +191,48 @@ namespace DomTreeBuilder {
190191
template <typename DomTreeT>
191192
void Calculate(DomTreeT &DT);
192193

193-
template <class DomTreeT>
194+
template <typename DomTreeT>
194195
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
195196
typename DomTreeT::NodePtr To);
196197

197-
template <class DomTreeT>
198+
template <typename DomTreeT>
198199
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
199200
typename DomTreeT::NodePtr To);
200201

202+
// UpdateKind and Update are used by the batch update API and it's easiest to
203+
// define them here.
204+
enum class UpdateKind : unsigned char { Insert, Delete };
205+
206+
template <typename NodePtr>
207+
struct Update {
208+
using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
209+
210+
NodePtr From;
211+
NodeKindPair ToAndKind;
212+
213+
Update(UpdateKind Kind, NodePtr From, NodePtr To)
214+
: From(From), ToAndKind(To, Kind) {}
215+
216+
UpdateKind getKind() const { return ToAndKind.getInt(); }
217+
NodePtr getFrom() const { return From; }
218+
NodePtr getTo() const { return ToAndKind.getPointer(); }
219+
bool operator==(const Update &RHS) const {
220+
return From == RHS.From && ToAndKind == RHS.ToAndKind;
221+
}
222+
223+
friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
224+
OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
225+
U.getFrom()->printAsOperand(OS, false);
226+
OS << " -> ";
227+
U.getTo()->printAsOperand(OS, false);
228+
return OS;
229+
}
230+
};
231+
232+
template <typename DomTreeT>
233+
void ApplyUpdates(DomTreeT &DT,
234+
ArrayRef<typename DomTreeT::UpdateType> Updates);
235+
201236
template <typename DomTreeT>
202237
bool Verify(const DomTreeT &DT);
203238
} // namespace DomTreeBuilder
@@ -219,6 +254,11 @@ class DominatorTreeBase {
219254
using ParentType = typename std::remove_pointer<ParentPtr>::type;
220255
static constexpr bool IsPostDominator = IsPostDom;
221256

257+
using UpdateType = DomTreeBuilder::Update<NodePtr>;
258+
using UpdateKind = DomTreeBuilder::UpdateKind;
259+
static constexpr UpdateKind Insert = UpdateKind::Insert;
260+
static constexpr UpdateKind Delete = UpdateKind::Delete;
261+
222262
protected:
223263
// Dominators always have a single root, postdominators can have more.
224264
SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
@@ -463,6 +503,39 @@ class DominatorTreeBase {
463503
// API to update (Post)DominatorTree information based on modifications to
464504
// the CFG...
465505

506+
/// Inform the dominator tree about a sequence of CFG edge insertions and
507+
/// deletions and perform a batch update on the tree.
508+
///
509+
/// This function should be used when there were multiple CFG updates after
510+
/// the last dominator tree update. It takes care of performing the updates
511+
/// in sync with the CFG and optimizes away the redundant operations that
512+
/// cancel each other.
513+
/// The functions expects the sequence of updates to be balanced. Eg.:
514+
/// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
515+
/// logically it results in a single insertions.
516+
/// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
517+
/// sense to insert the same edge twice.
518+
///
519+
/// What's more, the functions assumes that it's safe to ask every node in the
520+
/// CFG about its children and inverse children. This implies that deletions
521+
/// of CFG edges must not delete the CFG nodes before calling this function.
522+
///
523+
/// Batch updates should be generally faster when performing longer sequences
524+
/// of updates than calling insertEdge/deleteEdge manually multiple times, as
525+
/// they can reorder the updates and remove redundant ones internally.
526+
///
527+
/// Note that for postdominators it automatically takes care of applying
528+
/// updates on reverse edges internally (so there's no need to swap the
529+
/// From and To pointers when constructing DominatorTree::UpdateType).
530+
/// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
531+
/// with the same template parameter T.
532+
///
533+
/// \param Updates An unordered sequence of updates to perform.
534+
///
535+
void applyUpdates(ArrayRef<UpdateType> Updates) {
536+
DomTreeBuilder::ApplyUpdates(*this, Updates);
537+
}
538+
466539
/// Inform the dominator tree about a CFG edge insertion and update the tree.
467540
///
468541
/// This function has to be called just before or just after making the update
@@ -487,11 +560,6 @@ class DominatorTreeBase {
487560
/// DEBUG mode. There cannot be any other updates that the
488561
/// dominator tree doesn't know about.
489562
///
490-
/// However, it is fine to perform multiple CFG deletions that make different
491-
/// subtrees forward-unreachable and to inform the DomTree about them all at
492-
/// the same time, as the incremental algorithm doesn't walk the tree above
493-
/// the NearestCommonDominator of a deleted edge
494-
///
495563
/// Note that for postdominators it automatically takes care of deleting
496564
/// a reverse edge internally (so there's no need to swap the parameters).
497565
///
@@ -678,7 +746,6 @@ class DominatorTreeBase {
678746

679747
/// recalculate - compute a dominator tree for the given function
680748
void recalculate(ParentType &Func) {
681-
reset();
682749
Parent = &Func;
683750
DomTreeBuilder::Calculate(*this);
684751
}

‎llvm/include/llvm/Support/GenericDomTreeConstruction.h

Lines changed: 307 additions & 81 deletions
Large diffs are not rendered by default.

‎llvm/lib/IR/Dominators.cpp

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,8 @@ template class llvm::DomTreeNodeBase<BasicBlock>;
6464
template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
6565
template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
6666

67+
template struct llvm::DomTreeBuilder::Update<BasicBlock *>;
68+
6769
template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
6870
DomTreeBuilder::BBDomTree &DT);
6971
template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
@@ -79,6 +81,11 @@ template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
7981
template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
8082
DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To);
8183

84+
template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
85+
DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates);
86+
template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
87+
DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates);
88+
8289
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
8390
const DomTreeBuilder::BBDomTree &DT);
8491
template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
@@ -312,6 +319,9 @@ void DominatorTree::verifyDomTree() const {
312319
print(errs());
313320
errs() << "\nActual:\n";
314321
OtherDT.print(errs());
322+
errs() << "\nCFG:\n";
323+
F.print(errs());
324+
errs().flush();
315325
abort();
316326
}
317327
}

‎llvm/unittests/IR/CMakeLists.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@ set(IRSources
1616
DebugInfoTest.cpp
1717
DebugTypeODRUniquingTest.cpp
1818
DominatorTreeTest.cpp
19+
DominatorTreeBatchUpdatesTest.cpp
1920
FunctionTest.cpp
2021
PassBuilderCallbacksTest.cpp
2122
IRBuilderTest.cpp

‎llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp

Lines changed: 260 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,260 @@
1+
//===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===----------------------------------------------------------------------===//
9+
10+
#include <random>
11+
#include "CFGBuilder.h"
12+
#include "gtest/gtest.h"
13+
#include "llvm/Analysis/PostDominators.h"
14+
#include "llvm/IR/Dominators.h"
15+
#include "llvm/Support/GenericDomTreeConstruction.h"
16+
17+
#define DEBUG_TYPE "batch-update-tests"
18+
19+
using namespace llvm;
20+
21+
namespace {
22+
const auto CFGInsert = CFGBuilder::ActionKind::Insert;
23+
const auto CFGDelete = CFGBuilder::ActionKind::Delete;
24+
25+
struct PostDomTree : PostDomTreeBase<BasicBlock> {
26+
PostDomTree(Function &F) { recalculate(F); }
27+
};
28+
29+
using DomUpdate = DominatorTree::UpdateType;
30+
static_assert(
31+
std::is_same<DomUpdate, PostDomTree::UpdateType>::value,
32+
"Trees differing only in IsPostDom should have the same update types");
33+
using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
34+
using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
35+
const auto Insert = DominatorTree::Insert;
36+
const auto Delete = DominatorTree::Delete;
37+
38+
std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
39+
std::vector<CFGBuilder::Update> &In) {
40+
std::vector<DomUpdate> Res;
41+
Res.reserve(In.size());
42+
43+
for (const auto &CFGU : In)
44+
Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete,
45+
B.getOrAddBlock(CFGU.Edge.From),
46+
B.getOrAddBlock(CFGU.Edge.To)});
47+
return Res;
48+
}
49+
} // namespace
50+
51+
TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
52+
CFGHolder Holder;
53+
CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
54+
55+
BasicBlock *A = Builder.getOrAddBlock("A");
56+
BasicBlock *B = Builder.getOrAddBlock("B");
57+
BasicBlock *C = Builder.getOrAddBlock("C");
58+
BasicBlock *D = Builder.getOrAddBlock("D");
59+
60+
std::vector<DomUpdate> Updates = {
61+
{Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
62+
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
63+
SmallVector<DomUpdate, 4> Legalized;
64+
DomSNCA::LegalizeUpdates(Updates, Legalized);
65+
DEBUG(dbgs() << "Legalized updates:\t");
66+
DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
67+
DEBUG(dbgs() << "\n");
68+
EXPECT_EQ(Legalized.size(), 3UL);
69+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
70+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
71+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end());
72+
}
73+
74+
TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
75+
CFGHolder Holder;
76+
CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
77+
78+
BasicBlock *A = Builder.getOrAddBlock("A");
79+
BasicBlock *B = Builder.getOrAddBlock("B");
80+
BasicBlock *C = Builder.getOrAddBlock("C");
81+
BasicBlock *D = Builder.getOrAddBlock("D");
82+
83+
std::vector<DomUpdate> Updates = {
84+
{Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
85+
{Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
86+
SmallVector<DomUpdate, 4> Legalized;
87+
PostDomSNCA::LegalizeUpdates(Updates, Legalized);
88+
DEBUG(dbgs() << "Legalized postdom updates:\t");
89+
DEBUG(for (auto &U : Legalized) dbgs() << U << ", ");
90+
DEBUG(dbgs() << "\n");
91+
EXPECT_EQ(Legalized.size(), 3UL);
92+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
93+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
94+
EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end());
95+
}
96+
97+
TEST(DominatorTreeBatchUpdates, SingleInsertion) {
98+
CFGHolder Holder;
99+
CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
100+
101+
DominatorTree DT(*Holder.F);
102+
EXPECT_TRUE(DT.verify());
103+
PostDomTree PDT(*Holder.F);
104+
EXPECT_TRUE(DT.verify());
105+
106+
BasicBlock *B = Builder.getOrAddBlock("B");
107+
BasicBlock *C = Builder.getOrAddBlock("C");
108+
std::vector<DomUpdate> Updates = {{Insert, B, C}};
109+
110+
ASSERT_TRUE(Builder.applyUpdate());
111+
112+
DT.applyUpdates(Updates);
113+
EXPECT_TRUE(DT.verify());
114+
PDT.applyUpdates(Updates);
115+
EXPECT_TRUE(PDT.verify());
116+
}
117+
118+
TEST(DominatorTreeBatchUpdates, SingleDeletion) {
119+
CFGHolder Holder;
120+
CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
121+
{{CFGDelete, {"B", "C"}}});
122+
123+
DominatorTree DT(*Holder.F);
124+
EXPECT_TRUE(DT.verify());
125+
PostDomTree PDT(*Holder.F);
126+
EXPECT_TRUE(DT.verify());
127+
128+
BasicBlock *B = Builder.getOrAddBlock("B");
129+
BasicBlock *C = Builder.getOrAddBlock("C");
130+
std::vector<DomUpdate> Updates = {{Delete, B, C}};
131+
132+
ASSERT_TRUE(Builder.applyUpdate());
133+
134+
DT.applyUpdates(Updates);
135+
EXPECT_TRUE(DT.verify());
136+
PDT.applyUpdates(Updates);
137+
EXPECT_TRUE(PDT.verify());
138+
}
139+
140+
TEST(DominatorTreeBatchUpdates, FewInsertion) {
141+
std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},
142+
{CFGInsert, {"C", "B"}},
143+
{CFGInsert, {"C", "D"}},
144+
{CFGInsert, {"D", "E"}}};
145+
146+
CFGHolder Holder;
147+
CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
148+
149+
DominatorTree DT(*Holder.F);
150+
EXPECT_TRUE(DT.verify());
151+
PostDomTree PDT(*Holder.F);
152+
EXPECT_TRUE(PDT.verify());
153+
154+
BasicBlock *B = Builder.getOrAddBlock("B");
155+
BasicBlock *C = Builder.getOrAddBlock("C");
156+
BasicBlock *D = Builder.getOrAddBlock("D");
157+
BasicBlock *E = Builder.getOrAddBlock("E");
158+
159+
std::vector<DomUpdate> Updates = {
160+
{Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};
161+
162+
while (Builder.applyUpdate())
163+
;
164+
165+
DT.applyUpdates(Updates);
166+
EXPECT_TRUE(DT.verify());
167+
PDT.applyUpdates(Updates);
168+
EXPECT_TRUE(PDT.verify());
169+
}
170+
171+
TEST(DominatorTreeBatchUpdates, FewDeletions) {
172+
std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}},
173+
{CFGDelete, {"C", "B"}},
174+
{CFGDelete, {"B", "D"}},
175+
{CFGDelete, {"D", "E"}}};
176+
177+
CFGHolder Holder;
178+
CFGBuilder Builder(
179+
Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
180+
CFGUpdates);
181+
182+
DominatorTree DT(*Holder.F);
183+
EXPECT_TRUE(DT.verify());
184+
PostDomTree PDT(*Holder.F);
185+
EXPECT_TRUE(PDT.verify());
186+
187+
auto Updates = ToDomUpdates(Builder, CFGUpdates);
188+
189+
while (Builder.applyUpdate())
190+
;
191+
192+
DT.applyUpdates(Updates);
193+
EXPECT_TRUE(DT.verify());
194+
PDT.applyUpdates(Updates);
195+
EXPECT_TRUE(PDT.verify());
196+
}
197+
198+
TEST(DominatorTreeBatchUpdates, InsertDelete) {
199+
std::vector<CFGBuilder::Arc> Arcs = {
200+
{"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
201+
{"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
202+
203+
std::vector<CFGBuilder::Update> Updates = {
204+
{CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},
205+
{CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
206+
{CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},
207+
{CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
208+
{CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},
209+
{CFGDelete, {"11", "12"}}};
210+
211+
CFGHolder Holder;
212+
CFGBuilder B(Holder.F, Arcs, Updates);
213+
DominatorTree DT(*Holder.F);
214+
EXPECT_TRUE(DT.verify());
215+
PostDomTree PDT(*Holder.F);
216+
EXPECT_TRUE(PDT.verify());
217+
218+
while (B.applyUpdate())
219+
;
220+
221+
auto DomUpdates = ToDomUpdates(B, Updates);
222+
DT.applyUpdates(DomUpdates);
223+
EXPECT_TRUE(DT.verify());
224+
PDT.applyUpdates(DomUpdates);
225+
EXPECT_TRUE(PDT.verify());
226+
}
227+
228+
TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
229+
std::vector<CFGBuilder::Arc> Arcs = {
230+
{"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
231+
{"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
232+
233+
std::vector<CFGBuilder::Update> Updates = {
234+
{CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},
235+
{CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
236+
{CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},
237+
{CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
238+
{CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},
239+
{CFGDelete, {"11", "12"}}};
240+
241+
std::mt19937 Generator(0);
242+
for (unsigned i = 0; i < 16; ++i) {
243+
std::shuffle(Updates.begin(), Updates.end(), Generator);
244+
CFGHolder Holder;
245+
CFGBuilder B(Holder.F, Arcs, Updates);
246+
DominatorTree DT(*Holder.F);
247+
EXPECT_TRUE(DT.verify());
248+
PostDomTree PDT(*Holder.F);
249+
EXPECT_TRUE(PDT.verify());
250+
251+
while (B.applyUpdate())
252+
;
253+
254+
auto DomUpdates = ToDomUpdates(B, Updates);
255+
DT.applyUpdates(DomUpdates);
256+
EXPECT_TRUE(DT.verify());
257+
PDT.applyUpdates(DomUpdates);
258+
EXPECT_TRUE(PDT.verify());
259+
}
260+
}

0 commit comments

Comments
 (0)
Please sign in to comment.