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 | |
33 | std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B, |
34 | std::vector<CFGBuilder::Update> &In) { |
35 | std::vector<DomUpdate> Res; |
36 | Res.reserve(n: In.size()); |
37 | |
38 | for (const auto &CFGU : In) |
39 | Res.push_back(x: {CFGU.Action == CFGInsert ? Insert : Delete, |
40 | B.getOrAddBlock(BlockName: CFGU.Edge.From), |
41 | B.getOrAddBlock(BlockName: CFGU.Edge.To)}); |
42 | return Res; |
43 | } |
44 | } // namespace |
45 | |
46 | TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) { |
47 | CFGHolder Holder; |
48 | CFGBuilder Builder(Holder.F, {{.From: "A" , .To: "B" }}, {}); |
49 | |
50 | BasicBlock *A = Builder.getOrAddBlock(BlockName: "A" ); |
51 | BasicBlock *B = Builder.getOrAddBlock(BlockName: "B" ); |
52 | BasicBlock *C = Builder.getOrAddBlock(BlockName: "C" ); |
53 | BasicBlock *D = Builder.getOrAddBlock(BlockName: "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 *>(AllUpdates: Updates, Result&: Legalized, InverseGraph: 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 | |
69 | TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) { |
70 | CFGHolder Holder; |
71 | CFGBuilder Builder(Holder.F, {{.From: "A" , .To: "B" }}, {}); |
72 | |
73 | BasicBlock *A = Builder.getOrAddBlock(BlockName: "A" ); |
74 | BasicBlock *B = Builder.getOrAddBlock(BlockName: "B" ); |
75 | BasicBlock *C = Builder.getOrAddBlock(BlockName: "C" ); |
76 | BasicBlock *D = Builder.getOrAddBlock(BlockName: "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 *>(AllUpdates: Updates, Result&: Legalized, InverseGraph: 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 | |
92 | TEST(DominatorTreeBatchUpdates, SingleInsertion) { |
93 | CFGHolder Holder; |
94 | CFGBuilder Builder(Holder.F, {{.From: "A" , .To: "B" }}, {{.Action: CFGInsert, .Edge: {.From: "B" , .To: "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(BlockName: "B" ); |
102 | BasicBlock *C = Builder.getOrAddBlock(BlockName: "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 | |
113 | TEST(DominatorTreeBatchUpdates, SingleDeletion) { |
114 | CFGHolder Holder; |
115 | CFGBuilder Builder(Holder.F, {{.From: "A" , .To: "B" }, {.From: "B" , .To: "C" }}, |
116 | {{.Action: CFGDelete, .Edge: {.From: "B" , .To: "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(BlockName: "B" ); |
124 | BasicBlock *C = Builder.getOrAddBlock(BlockName: "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 | |
135 | TEST(DominatorTreeBatchUpdates, FewInsertion) { |
136 | std::vector<CFGBuilder::Update> CFGUpdates = {{.Action: CFGInsert, .Edge: {.From: "B" , .To: "C" }}, |
137 | {.Action: CFGInsert, .Edge: {.From: "C" , .To: "B" }}, |
138 | {.Action: CFGInsert, .Edge: {.From: "C" , .To: "D" }}, |
139 | {.Action: CFGInsert, .Edge: {.From: "D" , .To: "E" }}}; |
140 | |
141 | CFGHolder Holder; |
142 | CFGBuilder Builder(Holder.F, {{.From: "A" , .To: "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(BlockName: "B" ); |
150 | BasicBlock *C = Builder.getOrAddBlock(BlockName: "C" ); |
151 | BasicBlock *D = Builder.getOrAddBlock(BlockName: "D" ); |
152 | BasicBlock *E = Builder.getOrAddBlock(BlockName: "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 | |
166 | TEST(DominatorTreeBatchUpdates, FewDeletions) { |
167 | std::vector<CFGBuilder::Update> CFGUpdates = {{.Action: CFGDelete, .Edge: {.From: "B" , .To: "C" }}, |
168 | {.Action: CFGDelete, .Edge: {.From: "C" , .To: "B" }}, |
169 | {.Action: CFGDelete, .Edge: {.From: "B" , .To: "D" }}, |
170 | {.Action: CFGDelete, .Edge: {.From: "D" , .To: "E" }}}; |
171 | |
172 | CFGHolder Holder; |
173 | CFGBuilder Builder( |
174 | Holder.F, {{.From: "A" , .To: "B" }, {.From: "B" , .To: "C" }, {.From: "B" , .To: "D" }, {.From: "D" , .To: "E" }, {.From: "C" , .To: "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(B&: Builder, In&: 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 | |
193 | TEST(DominatorTreeBatchUpdates, InsertDelete) { |
194 | std::vector<CFGBuilder::Arc> Arcs = { |
195 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
196 | {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }}; |
197 | |
198 | std::vector<CFGBuilder::Update> Updates = { |
199 | {.Action: CFGInsert, .Edge: {.From: "2" , .To: "4" }}, {.Action: CFGInsert, .Edge: {.From: "12" , .To: "10" }}, |
200 | {.Action: CFGInsert, .Edge: {.From: "10" , .To: "9" }}, {.Action: CFGInsert, .Edge: {.From: "7" , .To: "6" }}, |
201 | {.Action: CFGInsert, .Edge: {.From: "7" , .To: "5" }}, {.Action: CFGDelete, .Edge: {.From: "3" , .To: "8" }}, |
202 | {.Action: CFGInsert, .Edge: {.From: "10" , .To: "7" }}, {.Action: CFGInsert, .Edge: {.From: "2" , .To: "8" }}, |
203 | {.Action: CFGDelete, .Edge: {.From: "3" , .To: "4" }}, {.Action: CFGDelete, .Edge: {.From: "8" , .To: "9" }}, |
204 | {.Action: CFGDelete, .Edge: {.From: "11" , .To: "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, In&: Updates); |
217 | DT.applyUpdates(Updates: DomUpdates); |
218 | EXPECT_TRUE(DT.verify()); |
219 | PDT.applyUpdates(Updates: DomUpdates); |
220 | EXPECT_TRUE(PDT.verify()); |
221 | } |
222 | |
223 | TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) { |
224 | std::vector<CFGBuilder::Arc> Arcs = { |
225 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
226 | {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }}; |
227 | |
228 | std::vector<CFGBuilder::Update> Updates = { |
229 | {.Action: CFGInsert, .Edge: {.From: "2" , .To: "4" }}, {.Action: CFGInsert, .Edge: {.From: "12" , .To: "10" }}, |
230 | {.Action: CFGInsert, .Edge: {.From: "10" , .To: "9" }}, {.Action: CFGInsert, .Edge: {.From: "7" , .To: "6" }}, |
231 | {.Action: CFGInsert, .Edge: {.From: "7" , .To: "5" }}, {.Action: CFGDelete, .Edge: {.From: "3" , .To: "8" }}, |
232 | {.Action: CFGInsert, .Edge: {.From: "10" , .To: "7" }}, {.Action: CFGInsert, .Edge: {.From: "2" , .To: "8" }}, |
233 | {.Action: CFGDelete, .Edge: {.From: "3" , .To: "4" }}, {.Action: CFGDelete, .Edge: {.From: "8" , .To: "9" }}, |
234 | {.Action: CFGDelete, .Edge: {.From: "11" , .To: "12" }}}; |
235 | |
236 | std::mt19937 Generator(0); |
237 | for (unsigned i = 0; i < 16; ++i) { |
238 | std::shuffle(first: Updates.begin(), last: Updates.end(), g&: 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, In&: Updates); |
250 | DT.applyUpdates(Updates: DomUpdates); |
251 | EXPECT_TRUE(DT.verify()); |
252 | PDT.applyUpdates(Updates: 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. |
259 | TEST(DominatorTreeBatchUpdates, InfiniteLoop) { |
260 | std::vector<CFGBuilder::Arc> Arcs = { |
261 | {.From: "1" , .To: "2" }, |
262 | {.From: "2" , .To: "3" }, |
263 | {.From: "3" , .To: "6" }, {.From: "3" , .To: "5" }, |
264 | {.From: "4" , .To: "5" }, |
265 | {.From: "5" , .To: "2" }, |
266 | {.From: "6" , .To: "3" }, {.From: "6" , .To: "4" }}; |
267 | |
268 | // SplitBlock on 3 -> 5 |
269 | std::vector<CFGBuilder::Update> Updates = { |
270 | {.Action: CFGInsert, .Edge: {.From: "N" , .To: "5" }}, {.Action: CFGInsert, .Edge: {.From: "3" , .To: "N" }}, {.Action: CFGDelete, .Edge: {.From: "3" , .To: "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, In&: Updates); |
283 | DT.applyUpdates(Updates: DomUpdates); |
284 | EXPECT_TRUE(DT.verify()); |
285 | PDT.applyUpdates(Updates: DomUpdates); |
286 | EXPECT_TRUE(PDT.verify()); |
287 | } |
288 | |
289 | TEST(DominatorTreeBatchUpdates, DeadBlocks) { |
290 | std::vector<CFGBuilder::Arc> Arcs = { |
291 | {.From: "1" , .To: "2" }, |
292 | {.From: "2" , .To: "3" }, |
293 | {.From: "3" , .To: "4" }, {.From: "3" , .To: "7" }, |
294 | {.From: "4" , .To: "4" }, |
295 | {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
296 | {.From: "6" , .To: "7" }, |
297 | {.From: "7" , .To: "2" }, {.From: "7" , .To: "8" }}; |
298 | |
299 | // Remove dead 5 and 7, |
300 | // plus SplitBlock on 7 -> 8 |
301 | std::vector<CFGBuilder::Update> Updates = { |
302 | {.Action: CFGDelete, .Edge: {.From: "6" , .To: "7" }}, {.Action: CFGDelete, .Edge: {.From: "5" , .To: "7" }}, {.Action: CFGDelete, .Edge: {.From: "5" , .To: "6" }}, |
303 | {.Action: CFGInsert, .Edge: {.From: "N" , .To: "8" }}, {.Action: CFGInsert, .Edge: {.From: "7" , .To: "N" }}, {.Action: CFGDelete, .Edge: {.From: "7" , .To: "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, In&: Updates); |
316 | DT.applyUpdates(Updates: DomUpdates); |
317 | EXPECT_TRUE(DT.verify()); |
318 | PDT.applyUpdates(Updates: DomUpdates); |
319 | EXPECT_TRUE(PDT.verify()); |
320 | } |
321 | |
322 | TEST(DominatorTreeBatchUpdates, InfiniteLoop2) { |
323 | std::vector<CFGBuilder::Arc> Arcs = { |
324 | {.From: "1" , .To: "2" }, |
325 | {.From: "2" , .To: "6" }, {.From: "2" , .To: "3" }, |
326 | {.From: "3" , .To: "4" }, |
327 | {.From: "4" , .To: "5" }, {.From: "4" , .To: "6" }, |
328 | {.From: "5" , .To: "4" }, |
329 | {.From: "6" , .To: "2" }}; |
330 | |
331 | // SplitBlock on 4 -> 6 |
332 | std::vector<CFGBuilder::Update> Updates = { |
333 | {.Action: CFGInsert, .Edge: {.From: "N" , .To: "6" }}, {.Action: CFGInsert, .Edge: {.From: "4" , .To: "N" }}, {.Action: CFGDelete, .Edge: {.From: "4" , .To: "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, In&: Updates); |
346 | DT.applyUpdates(Updates: DomUpdates); |
347 | EXPECT_TRUE(DT.verify()); |
348 | PDT.applyUpdates(Updates: DomUpdates); |
349 | EXPECT_TRUE(PDT.verify()); |
350 | } |
351 | |