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