1 //===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//
2 //
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
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(
27 std::is_same<DomUpdate, PostDominatorTree::UpdateType>::value,
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
ToDomUpdates(CFGBuilder & B,std::vector<CFGBuilder::Update> & In)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
TEST(DominatorTreeBatchUpdates,LegalizeDomUpdates)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;
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");
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
TEST(DominatorTreeBatchUpdates,LegalizePostDomUpdates)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;
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");
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
TEST(DominatorTreeBatchUpdates,SingleInsertion)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());
99 PostDominatorTree PDT(*Holder.F);
100 EXPECT_TRUE(PDT.verify());
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
TEST(DominatorTreeBatchUpdates,SingleDeletion)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());
121 PostDominatorTree PDT(*Holder.F);
122 EXPECT_TRUE(PDT.verify());
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
TEST(DominatorTreeBatchUpdates,FewInsertion)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 PostDominatorTree PDT(*Holder.F);
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
TEST(DominatorTreeBatchUpdates,FewDeletions)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());
180 PostDominatorTree PDT(*Holder.F);
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
TEST(DominatorTreeBatchUpdates,InsertDelete)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());
211 PostDominatorTree PDT(*Holder.F);
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
TEST(DominatorTreeBatchUpdates,InsertDeleteExhaustive)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());
244 PostDominatorTree PDT(*Holder.F);
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 }
257
258 // These are some odd flowgraphs, usually generated from csmith cases,
259 // which are difficult on post dom trees.
TEST(DominatorTreeBatchUpdates,InfiniteLoop)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());
277 PostDominatorTree PDT(*Holder.F);
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
TEST(DominatorTreeBatchUpdates,DeadBlocks)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());
310 PostDominatorTree PDT(*Holder.F);
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
TEST(DominatorTreeBatchUpdates,InfiniteLoop2)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());
340 PostDominatorTree PDT(*Holder.F);
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 }
352