|
121
|
1 //===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
|
|
|
2 //
|
|
147
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
121
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8
|
|
|
9 #include <random>
|
|
|
10 #include "CFGBuilder.h"
|
|
|
11 #include "gtest/gtest.h"
|
|
|
12 #include "llvm/Analysis/PostDominators.h"
|
|
|
13 #include "llvm/IR/Dominators.h"
|
|
|
14 #include "llvm/Support/GenericDomTreeConstruction.h"
|
|
|
15
|
|
|
16 #define DEBUG_TYPE "batch-update-tests"
|
|
|
17
|
|
|
18 using namespace llvm;
|
|
|
19
|
|
|
20 namespace {
|
|
|
21 const auto CFGInsert = CFGBuilder::ActionKind::Insert;
|
|
|
22 const auto CFGDelete = CFGBuilder::ActionKind::Delete;
|
|
|
23
|
|
|
24
|
|
|
25 using DomUpdate = DominatorTree::UpdateType;
|
|
|
26 static_assert(
|
|
147
|
27 std::is_same<DomUpdate, PostDominatorTree::UpdateType>::value,
|
|
121
|
28 "Trees differing only in IsPostDom should have the same update types");
|
|
|
29 using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;
|
|
|
30 using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;
|
|
|
31 const auto Insert = DominatorTree::Insert;
|
|
|
32 const auto Delete = DominatorTree::Delete;
|
|
|
33
|
|
|
34 std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,
|
|
|
35 std::vector<CFGBuilder::Update> &In) {
|
|
|
36 std::vector<DomUpdate> Res;
|
|
|
37 Res.reserve(In.size());
|
|
|
38
|
|
|
39 for (const auto &CFGU : In)
|
|
|
40 Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete,
|
|
|
41 B.getOrAddBlock(CFGU.Edge.From),
|
|
|
42 B.getOrAddBlock(CFGU.Edge.To)});
|
|
|
43 return Res;
|
|
|
44 }
|
|
|
45 } // namespace
|
|
|
46
|
|
|
47 TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {
|
|
|
48 CFGHolder Holder;
|
|
|
49 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
|
|
|
50
|
|
|
51 BasicBlock *A = Builder.getOrAddBlock("A");
|
|
|
52 BasicBlock *B = Builder.getOrAddBlock("B");
|
|
|
53 BasicBlock *C = Builder.getOrAddBlock("C");
|
|
|
54 BasicBlock *D = Builder.getOrAddBlock("D");
|
|
|
55
|
|
|
56 std::vector<DomUpdate> Updates = {
|
|
|
57 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
|
|
|
58 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
|
|
|
59 SmallVector<DomUpdate, 4> Legalized;
|
|
147
|
60 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, false);
|
|
|
61 LLVM_DEBUG(dbgs() << "Legalized updates:\t");
|
|
|
62 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
|
|
|
63 LLVM_DEBUG(dbgs() << "\n");
|
|
121
|
64 EXPECT_EQ(Legalized.size(), 3UL);
|
|
|
65 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end());
|
|
|
66 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end());
|
|
|
67 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end());
|
|
|
68 }
|
|
|
69
|
|
|
70 TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {
|
|
|
71 CFGHolder Holder;
|
|
|
72 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});
|
|
|
73
|
|
|
74 BasicBlock *A = Builder.getOrAddBlock("A");
|
|
|
75 BasicBlock *B = Builder.getOrAddBlock("B");
|
|
|
76 BasicBlock *C = Builder.getOrAddBlock("C");
|
|
|
77 BasicBlock *D = Builder.getOrAddBlock("D");
|
|
|
78
|
|
|
79 std::vector<DomUpdate> Updates = {
|
|
|
80 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},
|
|
|
81 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};
|
|
|
82 SmallVector<DomUpdate, 4> Legalized;
|
|
147
|
83 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, true);
|
|
|
84 LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");
|
|
|
85 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });
|
|
|
86 LLVM_DEBUG(dbgs() << "\n");
|
|
121
|
87 EXPECT_EQ(Legalized.size(), 3UL);
|
|
|
88 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end());
|
|
|
89 EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end());
|
|
|
90 EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end());
|
|
|
91 }
|
|
|
92
|
|
|
93 TEST(DominatorTreeBatchUpdates, SingleInsertion) {
|
|
|
94 CFGHolder Holder;
|
|
|
95 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});
|
|
|
96
|
|
|
97 DominatorTree DT(*Holder.F);
|
|
|
98 EXPECT_TRUE(DT.verify());
|
|
147
|
99 PostDominatorTree PDT(*Holder.F);
|
|
|
100 EXPECT_TRUE(PDT.verify());
|
|
121
|
101
|
|
|
102 BasicBlock *B = Builder.getOrAddBlock("B");
|
|
|
103 BasicBlock *C = Builder.getOrAddBlock("C");
|
|
|
104 std::vector<DomUpdate> Updates = {{Insert, B, C}};
|
|
|
105
|
|
|
106 ASSERT_TRUE(Builder.applyUpdate());
|
|
|
107
|
|
|
108 DT.applyUpdates(Updates);
|
|
|
109 EXPECT_TRUE(DT.verify());
|
|
|
110 PDT.applyUpdates(Updates);
|
|
|
111 EXPECT_TRUE(PDT.verify());
|
|
|
112 }
|
|
|
113
|
|
|
114 TEST(DominatorTreeBatchUpdates, SingleDeletion) {
|
|
|
115 CFGHolder Holder;
|
|
|
116 CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},
|
|
|
117 {{CFGDelete, {"B", "C"}}});
|
|
|
118
|
|
|
119 DominatorTree DT(*Holder.F);
|
|
|
120 EXPECT_TRUE(DT.verify());
|
|
147
|
121 PostDominatorTree PDT(*Holder.F);
|
|
|
122 EXPECT_TRUE(PDT.verify());
|
|
121
|
123
|
|
|
124 BasicBlock *B = Builder.getOrAddBlock("B");
|
|
|
125 BasicBlock *C = Builder.getOrAddBlock("C");
|
|
|
126 std::vector<DomUpdate> Updates = {{Delete, B, C}};
|
|
|
127
|
|
|
128 ASSERT_TRUE(Builder.applyUpdate());
|
|
|
129
|
|
|
130 DT.applyUpdates(Updates);
|
|
|
131 EXPECT_TRUE(DT.verify());
|
|
|
132 PDT.applyUpdates(Updates);
|
|
|
133 EXPECT_TRUE(PDT.verify());
|
|
|
134 }
|
|
|
135
|
|
|
136 TEST(DominatorTreeBatchUpdates, FewInsertion) {
|
|
|
137 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},
|
|
|
138 {CFGInsert, {"C", "B"}},
|
|
|
139 {CFGInsert, {"C", "D"}},
|
|
|
140 {CFGInsert, {"D", "E"}}};
|
|
|
141
|
|
|
142 CFGHolder Holder;
|
|
|
143 CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);
|
|
|
144
|
|
|
145 DominatorTree DT(*Holder.F);
|
|
|
146 EXPECT_TRUE(DT.verify());
|
|
147
|
147 PostDominatorTree PDT(*Holder.F);
|
|
121
|
148 EXPECT_TRUE(PDT.verify());
|
|
|
149
|
|
|
150 BasicBlock *B = Builder.getOrAddBlock("B");
|
|
|
151 BasicBlock *C = Builder.getOrAddBlock("C");
|
|
|
152 BasicBlock *D = Builder.getOrAddBlock("D");
|
|
|
153 BasicBlock *E = Builder.getOrAddBlock("E");
|
|
|
154
|
|
|
155 std::vector<DomUpdate> Updates = {
|
|
|
156 {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};
|
|
|
157
|
|
|
158 while (Builder.applyUpdate())
|
|
|
159 ;
|
|
|
160
|
|
|
161 DT.applyUpdates(Updates);
|
|
|
162 EXPECT_TRUE(DT.verify());
|
|
|
163 PDT.applyUpdates(Updates);
|
|
|
164 EXPECT_TRUE(PDT.verify());
|
|
|
165 }
|
|
|
166
|
|
|
167 TEST(DominatorTreeBatchUpdates, FewDeletions) {
|
|
|
168 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}},
|
|
|
169 {CFGDelete, {"C", "B"}},
|
|
|
170 {CFGDelete, {"B", "D"}},
|
|
|
171 {CFGDelete, {"D", "E"}}};
|
|
|
172
|
|
|
173 CFGHolder Holder;
|
|
|
174 CFGBuilder Builder(
|
|
|
175 Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},
|
|
|
176 CFGUpdates);
|
|
|
177
|
|
|
178 DominatorTree DT(*Holder.F);
|
|
|
179 EXPECT_TRUE(DT.verify());
|
|
147
|
180 PostDominatorTree PDT(*Holder.F);
|
|
121
|
181 EXPECT_TRUE(PDT.verify());
|
|
|
182
|
|
|
183 auto Updates = ToDomUpdates(Builder, CFGUpdates);
|
|
|
184
|
|
|
185 while (Builder.applyUpdate())
|
|
|
186 ;
|
|
|
187
|
|
|
188 DT.applyUpdates(Updates);
|
|
|
189 EXPECT_TRUE(DT.verify());
|
|
|
190 PDT.applyUpdates(Updates);
|
|
|
191 EXPECT_TRUE(PDT.verify());
|
|
|
192 }
|
|
|
193
|
|
|
194 TEST(DominatorTreeBatchUpdates, InsertDelete) {
|
|
|
195 std::vector<CFGBuilder::Arc> Arcs = {
|
|
|
196 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
|
|
|
197 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
|
|
|
198
|
|
|
199 std::vector<CFGBuilder::Update> Updates = {
|
|
|
200 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},
|
|
|
201 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
|
|
|
202 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},
|
|
|
203 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
|
|
|
204 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},
|
|
|
205 {CFGDelete, {"11", "12"}}};
|
|
|
206
|
|
|
207 CFGHolder Holder;
|
|
|
208 CFGBuilder B(Holder.F, Arcs, Updates);
|
|
|
209 DominatorTree DT(*Holder.F);
|
|
|
210 EXPECT_TRUE(DT.verify());
|
|
147
|
211 PostDominatorTree PDT(*Holder.F);
|
|
121
|
212 EXPECT_TRUE(PDT.verify());
|
|
|
213
|
|
|
214 while (B.applyUpdate())
|
|
|
215 ;
|
|
|
216
|
|
|
217 auto DomUpdates = ToDomUpdates(B, Updates);
|
|
|
218 DT.applyUpdates(DomUpdates);
|
|
|
219 EXPECT_TRUE(DT.verify());
|
|
|
220 PDT.applyUpdates(DomUpdates);
|
|
|
221 EXPECT_TRUE(PDT.verify());
|
|
|
222 }
|
|
|
223
|
|
|
224 TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {
|
|
|
225 std::vector<CFGBuilder::Arc> Arcs = {
|
|
|
226 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
|
|
|
227 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
|
|
|
228
|
|
|
229 std::vector<CFGBuilder::Update> Updates = {
|
|
|
230 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},
|
|
|
231 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},
|
|
|
232 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},
|
|
|
233 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},
|
|
|
234 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},
|
|
|
235 {CFGDelete, {"11", "12"}}};
|
|
|
236
|
|
|
237 std::mt19937 Generator(0);
|
|
|
238 for (unsigned i = 0; i < 16; ++i) {
|
|
|
239 std::shuffle(Updates.begin(), Updates.end(), Generator);
|
|
|
240 CFGHolder Holder;
|
|
|
241 CFGBuilder B(Holder.F, Arcs, Updates);
|
|
|
242 DominatorTree DT(*Holder.F);
|
|
|
243 EXPECT_TRUE(DT.verify());
|
|
147
|
244 PostDominatorTree PDT(*Holder.F);
|
|
121
|
245 EXPECT_TRUE(PDT.verify());
|
|
|
246
|
|
|
247 while (B.applyUpdate())
|
|
|
248 ;
|
|
|
249
|
|
|
250 auto DomUpdates = ToDomUpdates(B, Updates);
|
|
|
251 DT.applyUpdates(DomUpdates);
|
|
|
252 EXPECT_TRUE(DT.verify());
|
|
|
253 PDT.applyUpdates(DomUpdates);
|
|
|
254 EXPECT_TRUE(PDT.verify());
|
|
|
255 }
|
|
|
256 }
|
|
134
|
257
|
|
|
258 // These are some odd flowgraphs, usually generated from csmith cases,
|
|
|
259 // which are difficult on post dom trees.
|
|
|
260 TEST(DominatorTreeBatchUpdates, InfiniteLoop) {
|
|
|
261 std::vector<CFGBuilder::Arc> Arcs = {
|
|
|
262 {"1", "2"},
|
|
|
263 {"2", "3"},
|
|
|
264 {"3", "6"}, {"3", "5"},
|
|
|
265 {"4", "5"},
|
|
|
266 {"5", "2"},
|
|
|
267 {"6", "3"}, {"6", "4"}};
|
|
|
268
|
|
|
269 // SplitBlock on 3 -> 5
|
|
|
270 std::vector<CFGBuilder::Update> Updates = {
|
|
|
271 {CFGInsert, {"N", "5"}}, {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}};
|
|
|
272
|
|
|
273 CFGHolder Holder;
|
|
|
274 CFGBuilder B(Holder.F, Arcs, Updates);
|
|
|
275 DominatorTree DT(*Holder.F);
|
|
|
276 EXPECT_TRUE(DT.verify());
|
|
147
|
277 PostDominatorTree PDT(*Holder.F);
|
|
134
|
278 EXPECT_TRUE(PDT.verify());
|
|
|
279
|
|
|
280 while (B.applyUpdate())
|
|
|
281 ;
|
|
|
282
|
|
|
283 auto DomUpdates = ToDomUpdates(B, Updates);
|
|
|
284 DT.applyUpdates(DomUpdates);
|
|
|
285 EXPECT_TRUE(DT.verify());
|
|
|
286 PDT.applyUpdates(DomUpdates);
|
|
|
287 EXPECT_TRUE(PDT.verify());
|
|
|
288 }
|
|
|
289
|
|
|
290 TEST(DominatorTreeBatchUpdates, DeadBlocks) {
|
|
|
291 std::vector<CFGBuilder::Arc> Arcs = {
|
|
|
292 {"1", "2"},
|
|
|
293 {"2", "3"},
|
|
|
294 {"3", "4"}, {"3", "7"},
|
|
|
295 {"4", "4"},
|
|
|
296 {"5", "6"}, {"5", "7"},
|
|
|
297 {"6", "7"},
|
|
|
298 {"7", "2"}, {"7", "8"}};
|
|
|
299
|
|
|
300 // Remove dead 5 and 7,
|
|
|
301 // plus SplitBlock on 7 -> 8
|
|
|
302 std::vector<CFGBuilder::Update> Updates = {
|
|
|
303 {CFGDelete, {"6", "7"}}, {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}},
|
|
|
304 {CFGInsert, {"N", "8"}}, {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}};
|
|
|
305
|
|
|
306 CFGHolder Holder;
|
|
|
307 CFGBuilder B(Holder.F, Arcs, Updates);
|
|
|
308 DominatorTree DT(*Holder.F);
|
|
|
309 EXPECT_TRUE(DT.verify());
|
|
147
|
310 PostDominatorTree PDT(*Holder.F);
|
|
134
|
311 EXPECT_TRUE(PDT.verify());
|
|
|
312
|
|
|
313 while (B.applyUpdate())
|
|
|
314 ;
|
|
|
315
|
|
|
316 auto DomUpdates = ToDomUpdates(B, Updates);
|
|
|
317 DT.applyUpdates(DomUpdates);
|
|
|
318 EXPECT_TRUE(DT.verify());
|
|
|
319 PDT.applyUpdates(DomUpdates);
|
|
|
320 EXPECT_TRUE(PDT.verify());
|
|
|
321 }
|
|
|
322
|
|
|
323 TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {
|
|
|
324 std::vector<CFGBuilder::Arc> Arcs = {
|
|
|
325 {"1", "2"},
|
|
|
326 {"2", "6"}, {"2", "3"},
|
|
|
327 {"3", "4"},
|
|
|
328 {"4", "5"}, {"4", "6"},
|
|
|
329 {"5", "4"},
|
|
|
330 {"6", "2"}};
|
|
|
331
|
|
|
332 // SplitBlock on 4 -> 6
|
|
|
333 std::vector<CFGBuilder::Update> Updates = {
|
|
|
334 {CFGInsert, {"N", "6"}}, {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};
|
|
|
335
|
|
|
336 CFGHolder Holder;
|
|
|
337 CFGBuilder B(Holder.F, Arcs, Updates);
|
|
|
338 DominatorTree DT(*Holder.F);
|
|
|
339 EXPECT_TRUE(DT.verify());
|
|
147
|
340 PostDominatorTree PDT(*Holder.F);
|
|
134
|
341 EXPECT_TRUE(PDT.verify());
|
|
|
342
|
|
|
343 while (B.applyUpdate())
|
|
|
344 ;
|
|
|
345
|
|
|
346 auto DomUpdates = ToDomUpdates(B, Updates);
|
|
|
347 DT.applyUpdates(DomUpdates);
|
|
|
348 EXPECT_TRUE(DT.verify());
|
|
|
349 PDT.applyUpdates(DomUpdates);
|
|
|
350 EXPECT_TRUE(PDT.verify());
|
|
|
351 }
|
