1 | //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// |
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 "llvm/Analysis/PostDominators.h" |
11 | #include "llvm/Analysis/IteratedDominanceFrontier.h" |
12 | #include "llvm/AsmParser/Parser.h" |
13 | #include "llvm/IR/Constants.h" |
14 | #include "llvm/IR/Dominators.h" |
15 | #include "llvm/IR/Instructions.h" |
16 | #include "llvm/IR/LLVMContext.h" |
17 | #include "llvm/IR/Module.h" |
18 | #include "llvm/Support/SourceMgr.h" |
19 | #include "CFGBuilder.h" |
20 | #include "gtest/gtest.h" |
21 | |
22 | using namespace llvm; |
23 | |
24 | |
25 | /// Build the dominator tree for the function and run the Test. |
26 | static void runWithDomTree( |
27 | Module &M, StringRef FuncName, |
28 | function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)> |
29 | Test) { |
30 | auto *F = M.getFunction(Name: FuncName); |
31 | ASSERT_NE(F, nullptr) << "Could not find " << FuncName; |
32 | // Compute the dominator tree for the function. |
33 | DominatorTree DT(*F); |
34 | PostDominatorTree PDT(*F); |
35 | Test(*F, &DT, &PDT); |
36 | } |
37 | |
38 | static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, |
39 | StringRef ModuleStr) { |
40 | SMDiagnostic Err; |
41 | std::unique_ptr<Module> M = parseAssemblyString(AsmString: ModuleStr, Err, Context); |
42 | assert(M && "Bad assembly?" ); |
43 | return M; |
44 | } |
45 | |
46 | TEST(DominatorTree, PHIs) { |
47 | StringRef ModuleString = R"( |
48 | define void @f() { |
49 | bb1: |
50 | br label %bb1 |
51 | bb2: |
52 | %a = phi i32 [0, %bb1], [1, %bb2] |
53 | %b = phi i32 [2, %bb1], [%a, %bb2] |
54 | br label %bb2 |
55 | }; |
56 | )" ; |
57 | |
58 | // Parse the module. |
59 | LLVMContext Context; |
60 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
61 | |
62 | runWithDomTree(M&: *M, FuncName: "f" , |
63 | Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
64 | auto FI = F.begin(); |
65 | ++FI; |
66 | BasicBlock *BB2 = &*FI; |
67 | auto BI = BB2->begin(); |
68 | Instruction *PhiA = &*BI++; |
69 | Instruction *PhiB = &*BI; |
70 | |
71 | // Phis are thought to execute "instantly, together". |
72 | EXPECT_TRUE(DT->dominates(PhiA, PhiB)); |
73 | EXPECT_TRUE(DT->dominates(PhiB, PhiA)); |
74 | }); |
75 | } |
76 | |
77 | TEST(DominatorTree, Unreachable) { |
78 | StringRef ModuleString = |
79 | "declare i32 @g()\n" |
80 | "define void @f(i32 %x) personality i32 ()* @g {\n" |
81 | "bb0:\n" |
82 | " %y1 = add i32 %x, 1\n" |
83 | " %y2 = add i32 %x, 1\n" |
84 | " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" |
85 | "bb1:\n" |
86 | " %y4 = add i32 %x, 1\n" |
87 | " br label %bb4\n" |
88 | "bb2:\n" |
89 | " %y5 = landingpad i32\n" |
90 | " cleanup\n" |
91 | " br label %bb4\n" |
92 | "bb3:\n" |
93 | " %y6 = add i32 %x, 1\n" |
94 | " %y7 = add i32 %x, 1\n" |
95 | " ret void\n" |
96 | "bb4:\n" |
97 | " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" |
98 | " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" |
99 | " ret void\n" |
100 | "}\n" ; |
101 | |
102 | // Parse the module. |
103 | LLVMContext Context; |
104 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
105 | |
106 | runWithDomTree( |
107 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
108 | Function::iterator FI = F.begin(); |
109 | |
110 | BasicBlock *BB0 = &*FI++; |
111 | BasicBlock::iterator BBI = BB0->begin(); |
112 | Instruction *Y1 = &*BBI++; |
113 | Instruction *Y2 = &*BBI++; |
114 | Instruction *Y3 = &*BBI++; |
115 | |
116 | BasicBlock *BB1 = &*FI++; |
117 | BBI = BB1->begin(); |
118 | Instruction *Y4 = &*BBI++; |
119 | |
120 | BasicBlock *BB2 = &*FI++; |
121 | BBI = BB2->begin(); |
122 | Instruction *Y5 = &*BBI++; |
123 | |
124 | BasicBlock *BB3 = &*FI++; |
125 | BBI = BB3->begin(); |
126 | Instruction *Y6 = &*BBI++; |
127 | Instruction *Y7 = &*BBI++; |
128 | |
129 | BasicBlock *BB4 = &*FI++; |
130 | BBI = BB4->begin(); |
131 | Instruction *Y8 = &*BBI++; |
132 | Instruction *Y9 = &*BBI++; |
133 | |
134 | // Reachability |
135 | EXPECT_TRUE(DT->isReachableFromEntry(BB0)); |
136 | EXPECT_TRUE(DT->isReachableFromEntry(BB1)); |
137 | EXPECT_TRUE(DT->isReachableFromEntry(BB2)); |
138 | EXPECT_FALSE(DT->isReachableFromEntry(BB3)); |
139 | EXPECT_TRUE(DT->isReachableFromEntry(BB4)); |
140 | |
141 | // BB dominance |
142 | EXPECT_TRUE(DT->dominates(BB0, BB0)); |
143 | EXPECT_TRUE(DT->dominates(BB0, BB1)); |
144 | EXPECT_TRUE(DT->dominates(BB0, BB2)); |
145 | EXPECT_TRUE(DT->dominates(BB0, BB3)); |
146 | EXPECT_TRUE(DT->dominates(BB0, BB4)); |
147 | |
148 | EXPECT_FALSE(DT->dominates(BB1, BB0)); |
149 | EXPECT_TRUE(DT->dominates(BB1, BB1)); |
150 | EXPECT_FALSE(DT->dominates(BB1, BB2)); |
151 | EXPECT_TRUE(DT->dominates(BB1, BB3)); |
152 | EXPECT_FALSE(DT->dominates(BB1, BB4)); |
153 | |
154 | EXPECT_FALSE(DT->dominates(BB2, BB0)); |
155 | EXPECT_FALSE(DT->dominates(BB2, BB1)); |
156 | EXPECT_TRUE(DT->dominates(BB2, BB2)); |
157 | EXPECT_TRUE(DT->dominates(BB2, BB3)); |
158 | EXPECT_FALSE(DT->dominates(BB2, BB4)); |
159 | |
160 | EXPECT_FALSE(DT->dominates(BB3, BB0)); |
161 | EXPECT_FALSE(DT->dominates(BB3, BB1)); |
162 | EXPECT_FALSE(DT->dominates(BB3, BB2)); |
163 | EXPECT_TRUE(DT->dominates(BB3, BB3)); |
164 | EXPECT_FALSE(DT->dominates(BB3, BB4)); |
165 | |
166 | // BB proper dominance |
167 | EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); |
168 | EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); |
169 | EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); |
170 | EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); |
171 | |
172 | EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); |
173 | EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); |
174 | EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); |
175 | EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); |
176 | |
177 | EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); |
178 | EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); |
179 | EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); |
180 | EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); |
181 | |
182 | EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); |
183 | EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); |
184 | EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); |
185 | EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); |
186 | |
187 | // Instruction dominance in the same reachable BB |
188 | EXPECT_FALSE(DT->dominates(Y1, Y1)); |
189 | EXPECT_TRUE(DT->dominates(Y1, Y2)); |
190 | EXPECT_FALSE(DT->dominates(Y2, Y1)); |
191 | EXPECT_FALSE(DT->dominates(Y2, Y2)); |
192 | |
193 | // Instruction dominance in the same unreachable BB |
194 | EXPECT_TRUE(DT->dominates(Y6, Y6)); |
195 | EXPECT_TRUE(DT->dominates(Y6, Y7)); |
196 | EXPECT_TRUE(DT->dominates(Y7, Y6)); |
197 | EXPECT_TRUE(DT->dominates(Y7, Y7)); |
198 | |
199 | // Invoke |
200 | EXPECT_TRUE(DT->dominates(Y3, Y4)); |
201 | EXPECT_FALSE(DT->dominates(Y3, Y5)); |
202 | |
203 | // Phi |
204 | EXPECT_TRUE(DT->dominates(Y2, Y9)); |
205 | EXPECT_FALSE(DT->dominates(Y3, Y9)); |
206 | EXPECT_FALSE(DT->dominates(Y8, Y9)); |
207 | |
208 | // Anything dominates unreachable |
209 | EXPECT_TRUE(DT->dominates(Y1, Y6)); |
210 | EXPECT_TRUE(DT->dominates(Y3, Y6)); |
211 | |
212 | // Unreachable doesn't dominate reachable |
213 | EXPECT_FALSE(DT->dominates(Y6, Y1)); |
214 | |
215 | // Instruction, BB dominance |
216 | EXPECT_FALSE(DT->dominates(Y1, BB0)); |
217 | EXPECT_TRUE(DT->dominates(Y1, BB1)); |
218 | EXPECT_TRUE(DT->dominates(Y1, BB2)); |
219 | EXPECT_TRUE(DT->dominates(Y1, BB3)); |
220 | EXPECT_TRUE(DT->dominates(Y1, BB4)); |
221 | |
222 | EXPECT_FALSE(DT->dominates(Y3, BB0)); |
223 | EXPECT_TRUE(DT->dominates(Y3, BB1)); |
224 | EXPECT_FALSE(DT->dominates(Y3, BB2)); |
225 | EXPECT_TRUE(DT->dominates(Y3, BB3)); |
226 | EXPECT_FALSE(DT->dominates(Y3, BB4)); |
227 | |
228 | EXPECT_TRUE(DT->dominates(Y6, BB3)); |
229 | |
230 | // Post dominance. |
231 | EXPECT_TRUE(PDT->dominates(BB0, BB0)); |
232 | EXPECT_FALSE(PDT->dominates(BB1, BB0)); |
233 | EXPECT_FALSE(PDT->dominates(BB2, BB0)); |
234 | EXPECT_FALSE(PDT->dominates(BB3, BB0)); |
235 | EXPECT_TRUE(PDT->dominates(BB4, BB1)); |
236 | |
237 | // Dominance descendants. |
238 | SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; |
239 | |
240 | DT->getDescendants(R: BB0, Result&: DominatedBBs); |
241 | PDT->getDescendants(R: BB0, Result&: PostDominatedBBs); |
242 | EXPECT_EQ(DominatedBBs.size(), 4UL); |
243 | EXPECT_EQ(PostDominatedBBs.size(), 1UL); |
244 | |
245 | // BB3 is unreachable. It should have no dominators nor postdominators. |
246 | DominatedBBs.clear(); |
247 | PostDominatedBBs.clear(); |
248 | DT->getDescendants(R: BB3, Result&: DominatedBBs); |
249 | DT->getDescendants(R: BB3, Result&: PostDominatedBBs); |
250 | EXPECT_EQ(DominatedBBs.size(), 0UL); |
251 | EXPECT_EQ(PostDominatedBBs.size(), 0UL); |
252 | |
253 | // Check DFS Numbers before |
254 | DT->updateDFSNumbers(); |
255 | EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); |
256 | EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); |
257 | EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); |
258 | EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); |
259 | EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); |
260 | EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); |
261 | EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); |
262 | EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); |
263 | |
264 | // Check levels before |
265 | EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); |
266 | EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); |
267 | EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); |
268 | EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); |
269 | |
270 | // Reattach block 3 to block 1 and recalculate |
271 | BB1->getTerminator()->eraseFromParent(); |
272 | BranchInst::Create(IfTrue: BB4, IfFalse: BB3, Cond: ConstantInt::getTrue(Context&: F.getContext()), InsertAtEnd: BB1); |
273 | DT->recalculate(Func&: F); |
274 | |
275 | // Check DFS Numbers after |
276 | DT->updateDFSNumbers(); |
277 | EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); |
278 | EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); |
279 | EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); |
280 | EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); |
281 | EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); |
282 | EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); |
283 | EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); |
284 | EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); |
285 | EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); |
286 | EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); |
287 | |
288 | // Check levels after |
289 | EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); |
290 | EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); |
291 | EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); |
292 | EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); |
293 | EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); |
294 | |
295 | // Change root node |
296 | EXPECT_TRUE(DT->verify()); |
297 | BasicBlock *NewEntry = |
298 | BasicBlock::Create(Context&: F.getContext(), Name: "new_entry" , Parent: &F, InsertBefore: BB0); |
299 | BranchInst::Create(IfTrue: BB0, InsertAtEnd: NewEntry); |
300 | EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); |
301 | EXPECT_TRUE(&F.getEntryBlock() == NewEntry); |
302 | DT->setNewRoot(NewEntry); |
303 | EXPECT_TRUE(DT->verify()); |
304 | }); |
305 | } |
306 | |
307 | TEST(DominatorTree, NonUniqueEdges) { |
308 | StringRef ModuleString = |
309 | "define i32 @f(i32 %i, i32 *%p) {\n" |
310 | "bb0:\n" |
311 | " store i32 %i, i32 *%p\n" |
312 | " switch i32 %i, label %bb2 [\n" |
313 | " i32 0, label %bb1\n" |
314 | " i32 1, label %bb1\n" |
315 | " ]\n" |
316 | " bb1:\n" |
317 | " ret i32 1\n" |
318 | " bb2:\n" |
319 | " ret i32 4\n" |
320 | "}\n" ; |
321 | |
322 | // Parse the module. |
323 | LLVMContext Context; |
324 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
325 | |
326 | runWithDomTree( |
327 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
328 | Function::iterator FI = F.begin(); |
329 | |
330 | BasicBlock *BB0 = &*FI++; |
331 | BasicBlock *BB1 = &*FI++; |
332 | BasicBlock *BB2 = &*FI++; |
333 | |
334 | const Instruction *TI = BB0->getTerminator(); |
335 | assert(TI->getNumSuccessors() == 3 && "Switch has three successors" ); |
336 | |
337 | BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(Idx: 0)); |
338 | assert(Edge_BB0_BB2.getEnd() == BB2 && |
339 | "Default label is the 1st successor" ); |
340 | |
341 | BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(Idx: 1)); |
342 | assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor" ); |
343 | |
344 | BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(Idx: 2)); |
345 | assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor" ); |
346 | |
347 | EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); |
348 | EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); |
349 | |
350 | EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); |
351 | EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); |
352 | |
353 | EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); |
354 | EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); |
355 | }); |
356 | } |
357 | |
358 | // Verify that the PDT is correctly updated in case an edge removal results |
359 | // in a new unreachable CFG node. Also make sure that the updated PDT is the |
360 | // same as a freshly recalculated one. |
361 | // |
362 | // For the following input code and initial PDT: |
363 | // |
364 | // CFG PDT |
365 | // |
366 | // A Exit |
367 | // | | |
368 | // _B D |
369 | // / | \ | |
370 | // ^ v \ B |
371 | // \ / D / \ |
372 | // C \ C A |
373 | // v |
374 | // Exit |
375 | // |
376 | // we verify that CFG' and PDT-updated is obtained after removal of edge C -> B. |
377 | // |
378 | // CFG' PDT-updated |
379 | // |
380 | // A Exit |
381 | // | / | \ |
382 | // B C B D |
383 | // | \ | |
384 | // v \ A |
385 | // / D |
386 | // C \ |
387 | // | \ |
388 | // unreachable Exit |
389 | // |
390 | // Both the blocks that end with ret and with unreachable become trivial |
391 | // PostDominatorTree roots, as they have no successors. |
392 | // |
393 | TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { |
394 | StringRef ModuleString = |
395 | "define void @f() {\n" |
396 | "A:\n" |
397 | " br label %B\n" |
398 | "B:\n" |
399 | " br i1 undef, label %D, label %C\n" |
400 | "C:\n" |
401 | " br label %B\n" |
402 | "D:\n" |
403 | " ret void\n" |
404 | "}\n" ; |
405 | |
406 | // Parse the module. |
407 | LLVMContext Context; |
408 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
409 | |
410 | runWithDomTree( |
411 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
412 | Function::iterator FI = F.begin(); |
413 | |
414 | FI++; |
415 | BasicBlock *B = &*FI++; |
416 | BasicBlock *C = &*FI++; |
417 | BasicBlock *D = &*FI++; |
418 | |
419 | ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); |
420 | EXPECT_TRUE(DT->verify()); |
421 | EXPECT_TRUE(PDT->verify()); |
422 | |
423 | C->getTerminator()->eraseFromParent(); |
424 | new UnreachableInst(C->getContext(), C); |
425 | |
426 | DT->deleteEdge(From: C, To: B); |
427 | PDT->deleteEdge(From: C, To: B); |
428 | |
429 | EXPECT_TRUE(DT->verify()); |
430 | EXPECT_TRUE(PDT->verify()); |
431 | |
432 | EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); |
433 | EXPECT_NE(PDT->getNode(C), nullptr); |
434 | |
435 | DominatorTree NDT(F); |
436 | EXPECT_EQ(DT->compare(NDT), 0); |
437 | |
438 | PostDominatorTree NPDT(F); |
439 | EXPECT_EQ(PDT->compare(NPDT), 0); |
440 | }); |
441 | } |
442 | |
443 | // Verify that the PDT is correctly updated in case an edge removal results |
444 | // in an infinite loop. Also make sure that the updated PDT is the |
445 | // same as a freshly recalculated one. |
446 | // |
447 | // Test case: |
448 | // |
449 | // CFG PDT |
450 | // |
451 | // A Exit |
452 | // | | |
453 | // _B D |
454 | // / | \ | |
455 | // ^ v \ B |
456 | // \ / D / \ |
457 | // C \ C A |
458 | // / \ v |
459 | // ^ v Exit |
460 | // \_/ |
461 | // |
462 | // After deleting the edge C->B, C is part of an infinite reverse-unreachable |
463 | // loop: |
464 | // |
465 | // CFG' PDT' |
466 | // |
467 | // A Exit |
468 | // | / | \ |
469 | // B C B D |
470 | // | \ | |
471 | // v \ A |
472 | // / D |
473 | // C \ |
474 | // / \ v |
475 | // ^ v Exit |
476 | // \_/ |
477 | // |
478 | // As C now becomes reverse-unreachable, it forms a new non-trivial root and |
479 | // gets connected to the virtual exit. |
480 | // D does not postdominate B anymore, because there are two forward paths from |
481 | // B to the virtual exit: |
482 | // - B -> C -> VirtualExit |
483 | // - B -> D -> VirtualExit. |
484 | // |
485 | TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { |
486 | StringRef ModuleString = |
487 | "define void @f() {\n" |
488 | "A:\n" |
489 | " br label %B\n" |
490 | "B:\n" |
491 | " br i1 undef, label %D, label %C\n" |
492 | "C:\n" |
493 | " switch i32 undef, label %C [\n" |
494 | " i32 0, label %B\n" |
495 | " ]\n" |
496 | "D:\n" |
497 | " ret void\n" |
498 | "}\n" ; |
499 | |
500 | // Parse the module. |
501 | LLVMContext Context; |
502 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
503 | |
504 | runWithDomTree( |
505 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
506 | Function::iterator FI = F.begin(); |
507 | |
508 | FI++; |
509 | BasicBlock *B = &*FI++; |
510 | BasicBlock *C = &*FI++; |
511 | BasicBlock *D = &*FI++; |
512 | |
513 | ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); |
514 | EXPECT_TRUE(DT->verify()); |
515 | EXPECT_TRUE(PDT->verify()); |
516 | |
517 | auto SwitchC = cast<SwitchInst>(Val: C->getTerminator()); |
518 | SwitchC->removeCase(I: SwitchC->case_begin()); |
519 | DT->deleteEdge(From: C, To: B); |
520 | EXPECT_TRUE(DT->verify()); |
521 | PDT->deleteEdge(From: C, To: B); |
522 | EXPECT_TRUE(PDT->verify()); |
523 | |
524 | EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); |
525 | EXPECT_NE(PDT->getNode(C), nullptr); |
526 | |
527 | DominatorTree NDT(F); |
528 | EXPECT_EQ(DT->compare(NDT), 0); |
529 | |
530 | PostDominatorTree NPDT(F); |
531 | EXPECT_EQ(PDT->compare(NPDT), 0); |
532 | }); |
533 | } |
534 | |
535 | // Verify that the PDT is correctly updated in case an edge removal results |
536 | // in an infinite loop. |
537 | // |
538 | // Test case: |
539 | // |
540 | // CFG PDT |
541 | // |
542 | // A Exit |
543 | // | / | \ |
544 | // B-- C2 B D |
545 | // | \ / | |
546 | // v \ C A |
547 | // / D |
548 | // C--C2 \ |
549 | // / \ \ v |
550 | // ^ v --Exit |
551 | // \_/ |
552 | // |
553 | // After deleting the edge C->E, C is part of an infinite reverse-unreachable |
554 | // loop: |
555 | // |
556 | // CFG' PDT' |
557 | // |
558 | // A Exit |
559 | // | / | \ |
560 | // B C B D |
561 | // | \ | |
562 | // v \ A |
563 | // / D |
564 | // C \ |
565 | // / \ v |
566 | // ^ v Exit |
567 | // \_/ |
568 | // |
569 | // In PDT, D does not post-dominate B. After the edge C -> C2 is removed, |
570 | // C becomes a new nontrivial PDT root. |
571 | // |
572 | TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { |
573 | StringRef ModuleString = |
574 | "define void @f() {\n" |
575 | "A:\n" |
576 | " br label %B\n" |
577 | "B:\n" |
578 | " br i1 undef, label %D, label %C\n" |
579 | "C:\n" |
580 | " switch i32 undef, label %C [\n" |
581 | " i32 0, label %C2\n" |
582 | " ]\n" |
583 | "C2:\n" |
584 | " ret void\n" |
585 | "D:\n" |
586 | " ret void\n" |
587 | "}\n" ; |
588 | |
589 | // Parse the module. |
590 | LLVMContext Context; |
591 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
592 | |
593 | runWithDomTree( |
594 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
595 | Function::iterator FI = F.begin(); |
596 | |
597 | FI++; |
598 | BasicBlock *B = &*FI++; |
599 | BasicBlock *C = &*FI++; |
600 | BasicBlock *C2 = &*FI++; |
601 | BasicBlock *D = &*FI++; |
602 | |
603 | EXPECT_TRUE(DT->verify()); |
604 | EXPECT_TRUE(PDT->verify()); |
605 | |
606 | auto SwitchC = cast<SwitchInst>(Val: C->getTerminator()); |
607 | SwitchC->removeCase(I: SwitchC->case_begin()); |
608 | DT->deleteEdge(From: C, To: C2); |
609 | PDT->deleteEdge(From: C, To: C2); |
610 | C2->removeFromParent(); |
611 | |
612 | EXPECT_EQ(DT->getNode(C2), nullptr); |
613 | PDT->eraseNode(BB: C2); |
614 | delete C2; |
615 | |
616 | EXPECT_TRUE(DT->verify()); |
617 | EXPECT_TRUE(PDT->verify()); |
618 | |
619 | EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); |
620 | EXPECT_NE(PDT->getNode(C), nullptr); |
621 | |
622 | DominatorTree NDT(F); |
623 | EXPECT_EQ(DT->compare(NDT), 0); |
624 | |
625 | PostDominatorTree NPDT(F); |
626 | EXPECT_EQ(PDT->compare(NPDT), 0); |
627 | }); |
628 | } |
629 | |
630 | // Verify that the IDF returns blocks in a deterministic way. |
631 | // |
632 | // Test case: |
633 | // |
634 | // CFG |
635 | // |
636 | // (A) |
637 | // / \ |
638 | // / \ |
639 | // (B) (C) |
640 | // |\ /| |
641 | // | X | |
642 | // |/ \| |
643 | // (D) (E) |
644 | // |
645 | // IDF for block B is {D, E}, and the order of blocks in this list is defined by |
646 | // their 1) level in dom-tree and 2) DFSIn number if the level is the same. |
647 | // |
648 | TEST(DominatorTree, IDFDeterminismTest) { |
649 | StringRef ModuleString = |
650 | "define void @f() {\n" |
651 | "A:\n" |
652 | " br i1 undef, label %B, label %C\n" |
653 | "B:\n" |
654 | " br i1 undef, label %D, label %E\n" |
655 | "C:\n" |
656 | " br i1 undef, label %D, label %E\n" |
657 | "D:\n" |
658 | " ret void\n" |
659 | "E:\n" |
660 | " ret void\n" |
661 | "}\n" ; |
662 | |
663 | // Parse the module. |
664 | LLVMContext Context; |
665 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
666 | |
667 | runWithDomTree( |
668 | M&: *M, FuncName: "f" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
669 | Function::iterator FI = F.begin(); |
670 | |
671 | BasicBlock *A = &*FI++; |
672 | BasicBlock *B = &*FI++; |
673 | BasicBlock *C = &*FI++; |
674 | BasicBlock *D = &*FI++; |
675 | BasicBlock *E = &*FI++; |
676 | (void)C; |
677 | |
678 | DT->updateDFSNumbers(); |
679 | ForwardIDFCalculator IDF(*DT); |
680 | SmallPtrSet<BasicBlock *, 1> DefBlocks; |
681 | DefBlocks.insert(Ptr: B); |
682 | IDF.setDefiningBlocks(DefBlocks); |
683 | |
684 | SmallVector<BasicBlock *, 32> IDFBlocks; |
685 | SmallPtrSet<BasicBlock *, 32> LiveInBlocks; |
686 | IDF.resetLiveInBlocks(); |
687 | IDF.calculate(IDFBlocks); |
688 | |
689 | |
690 | EXPECT_EQ(IDFBlocks.size(), 2UL); |
691 | EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL); |
692 | EXPECT_EQ(IDFBlocks[0], D); |
693 | EXPECT_EQ(IDFBlocks[1], E); |
694 | EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() < |
695 | DT->getNode(IDFBlocks[1])->getDFSNumIn()); |
696 | }); |
697 | } |
698 | |
699 | namespace { |
700 | const auto Insert = CFGBuilder::ActionKind::Insert; |
701 | const auto Delete = CFGBuilder::ActionKind::Delete; |
702 | |
703 | bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { |
704 | return std::tie(args: A.Action, args: A.Edge.From, args: A.Edge.To) < |
705 | std::tie(args: B.Action, args: B.Edge.From, args: B.Edge.To); |
706 | } |
707 | } // namespace |
708 | |
709 | TEST(DominatorTree, InsertReachable) { |
710 | CFGHolder Holder; |
711 | std::vector<CFGBuilder::Arc> Arcs = { |
712 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
713 | {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }}; |
714 | |
715 | std::vector<CFGBuilder::Update> Updates = {{.Action: Insert, .Edge: {.From: "12" , .To: "10" }}, |
716 | {.Action: Insert, .Edge: {.From: "10" , .To: "9" }}, |
717 | {.Action: Insert, .Edge: {.From: "7" , .To: "6" }}, |
718 | {.Action: Insert, .Edge: {.From: "7" , .To: "5" }}}; |
719 | CFGBuilder B(Holder.F, Arcs, Updates); |
720 | DominatorTree DT(*Holder.F); |
721 | EXPECT_TRUE(DT.verify()); |
722 | PostDominatorTree PDT(*Holder.F); |
723 | EXPECT_TRUE(PDT.verify()); |
724 | |
725 | std::optional<CFGBuilder::Update> LastUpdate; |
726 | while ((LastUpdate = B.applyUpdate())) { |
727 | EXPECT_EQ(LastUpdate->Action, Insert); |
728 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
729 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
730 | DT.insertEdge(From, To); |
731 | EXPECT_TRUE(DT.verify()); |
732 | PDT.insertEdge(From, To); |
733 | EXPECT_TRUE(PDT.verify()); |
734 | } |
735 | } |
736 | |
737 | TEST(DominatorTree, InsertReachable2) { |
738 | CFGHolder Holder; |
739 | std::vector<CFGBuilder::Arc> Arcs = { |
740 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
741 | {.From: "7" , .To: "5" }, {.From: "2" , .To: "8" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }, {.From: "12" , .To: "10" }, |
742 | {.From: "10" , .To: "9" }, {.From: "9" , .To: "10" }}; |
743 | |
744 | std::vector<CFGBuilder::Update> Updates = {{.Action: Insert, .Edge: {.From: "10" , .To: "7" }}}; |
745 | CFGBuilder B(Holder.F, Arcs, Updates); |
746 | DominatorTree DT(*Holder.F); |
747 | EXPECT_TRUE(DT.verify()); |
748 | PostDominatorTree PDT(*Holder.F); |
749 | EXPECT_TRUE(PDT.verify()); |
750 | |
751 | std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); |
752 | EXPECT_TRUE(LastUpdate); |
753 | |
754 | EXPECT_EQ(LastUpdate->Action, Insert); |
755 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
756 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
757 | DT.insertEdge(From, To); |
758 | EXPECT_TRUE(DT.verify()); |
759 | PDT.insertEdge(From, To); |
760 | EXPECT_TRUE(PDT.verify()); |
761 | } |
762 | |
763 | TEST(DominatorTree, InsertUnreachable) { |
764 | CFGHolder Holder; |
765 | std::vector<CFGBuilder::Arc> Arcs = {{.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, |
766 | {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, {.From: "3" , .To: "8" }, |
767 | {.From: "9" , .To: "10" }, {.From: "11" , .To: "12" }}; |
768 | |
769 | std::vector<CFGBuilder::Update> Updates = {{.Action: Insert, .Edge: {.From: "4" , .To: "5" }}, |
770 | {.Action: Insert, .Edge: {.From: "8" , .To: "9" }}, |
771 | {.Action: Insert, .Edge: {.From: "10" , .To: "12" }}, |
772 | {.Action: Insert, .Edge: {.From: "10" , .To: "11" }}}; |
773 | CFGBuilder B(Holder.F, Arcs, Updates); |
774 | DominatorTree DT(*Holder.F); |
775 | EXPECT_TRUE(DT.verify()); |
776 | PostDominatorTree PDT(*Holder.F); |
777 | EXPECT_TRUE(PDT.verify()); |
778 | |
779 | std::optional<CFGBuilder::Update> LastUpdate; |
780 | while ((LastUpdate = B.applyUpdate())) { |
781 | EXPECT_EQ(LastUpdate->Action, Insert); |
782 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
783 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
784 | DT.insertEdge(From, To); |
785 | EXPECT_TRUE(DT.verify()); |
786 | PDT.insertEdge(From, To); |
787 | EXPECT_TRUE(PDT.verify()); |
788 | } |
789 | } |
790 | |
791 | TEST(DominatorTree, InsertFromUnreachable) { |
792 | CFGHolder Holder; |
793 | std::vector<CFGBuilder::Arc> Arcs = {{.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }}; |
794 | |
795 | std::vector<CFGBuilder::Update> Updates = {{.Action: Insert, .Edge: {.From: "3" , .To: "5" }}}; |
796 | CFGBuilder B(Holder.F, Arcs, Updates); |
797 | PostDominatorTree PDT(*Holder.F); |
798 | EXPECT_TRUE(PDT.verify()); |
799 | |
800 | std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); |
801 | EXPECT_TRUE(LastUpdate); |
802 | |
803 | EXPECT_EQ(LastUpdate->Action, Insert); |
804 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
805 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
806 | PDT.insertEdge(From, To); |
807 | EXPECT_TRUE(PDT.verify()); |
808 | EXPECT_EQ(PDT.root_size(), 2UL); |
809 | // Make sure we can use a const pointer with getNode. |
810 | const BasicBlock *BB5 = B.getOrAddBlock(BlockName: "5" ); |
811 | EXPECT_NE(PDT.getNode(BB5), nullptr); |
812 | } |
813 | |
814 | TEST(DominatorTree, InsertMixed) { |
815 | CFGHolder Holder; |
816 | std::vector<CFGBuilder::Arc> Arcs = { |
817 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
818 | {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }, {.From: "7" , .To: "3" }}; |
819 | |
820 | std::vector<CFGBuilder::Update> Updates = { |
821 | {.Action: Insert, .Edge: {.From: "4" , .To: "5" }}, {.Action: Insert, .Edge: {.From: "2" , .To: "5" }}, {.Action: Insert, .Edge: {.From: "10" , .To: "9" }}, |
822 | {.Action: Insert, .Edge: {.From: "12" , .To: "10" }}, {.Action: Insert, .Edge: {.From: "12" , .To: "10" }}, {.Action: Insert, .Edge: {.From: "7" , .To: "8" }}, |
823 | {.Action: Insert, .Edge: {.From: "7" , .To: "5" }}}; |
824 | CFGBuilder B(Holder.F, Arcs, Updates); |
825 | DominatorTree DT(*Holder.F); |
826 | EXPECT_TRUE(DT.verify()); |
827 | PostDominatorTree PDT(*Holder.F); |
828 | EXPECT_TRUE(PDT.verify()); |
829 | |
830 | std::optional<CFGBuilder::Update> LastUpdate; |
831 | while ((LastUpdate = B.applyUpdate())) { |
832 | EXPECT_EQ(LastUpdate->Action, Insert); |
833 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
834 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
835 | DT.insertEdge(From, To); |
836 | EXPECT_TRUE(DT.verify()); |
837 | PDT.insertEdge(From, To); |
838 | EXPECT_TRUE(PDT.verify()); |
839 | } |
840 | } |
841 | |
842 | TEST(DominatorTree, InsertPermut) { |
843 | std::vector<CFGBuilder::Arc> Arcs = { |
844 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
845 | {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }, {.From: "7" , .To: "3" }}; |
846 | |
847 | std::vector<CFGBuilder::Update> Updates = {{.Action: Insert, .Edge: {.From: "4" , .To: "5" }}, |
848 | {.Action: Insert, .Edge: {.From: "2" , .To: "5" }}, |
849 | {.Action: Insert, .Edge: {.From: "10" , .To: "9" }}, |
850 | {.Action: Insert, .Edge: {.From: "12" , .To: "10" }}}; |
851 | |
852 | while (std::next_permutation(first: Updates.begin(), last: Updates.end(), comp: CompUpdates)) { |
853 | CFGHolder Holder; |
854 | CFGBuilder B(Holder.F, Arcs, Updates); |
855 | DominatorTree DT(*Holder.F); |
856 | EXPECT_TRUE(DT.verify()); |
857 | PostDominatorTree PDT(*Holder.F); |
858 | EXPECT_TRUE(PDT.verify()); |
859 | |
860 | std::optional<CFGBuilder::Update> LastUpdate; |
861 | while ((LastUpdate = B.applyUpdate())) { |
862 | EXPECT_EQ(LastUpdate->Action, Insert); |
863 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
864 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
865 | DT.insertEdge(From, To); |
866 | EXPECT_TRUE(DT.verify()); |
867 | PDT.insertEdge(From, To); |
868 | EXPECT_TRUE(PDT.verify()); |
869 | } |
870 | } |
871 | } |
872 | |
873 | TEST(DominatorTree, DeleteReachable) { |
874 | CFGHolder Holder; |
875 | std::vector<CFGBuilder::Arc> Arcs = { |
876 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "2" , .To: "4" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, |
877 | {.From: "5" , .To: "7" }, {.From: "7" , .To: "8" }, {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "10" , .To: "2" }}; |
878 | |
879 | std::vector<CFGBuilder::Update> Updates = { |
880 | {.Action: Delete, .Edge: {.From: "2" , .To: "4" }}, {.Action: Delete, .Edge: {.From: "7" , .To: "8" }}, {.Action: Delete, .Edge: {.From: "10" , .To: "2" }}}; |
881 | CFGBuilder B(Holder.F, Arcs, Updates); |
882 | DominatorTree DT(*Holder.F); |
883 | EXPECT_TRUE(DT.verify()); |
884 | PostDominatorTree PDT(*Holder.F); |
885 | EXPECT_TRUE(PDT.verify()); |
886 | |
887 | std::optional<CFGBuilder::Update> LastUpdate; |
888 | while ((LastUpdate = B.applyUpdate())) { |
889 | EXPECT_EQ(LastUpdate->Action, Delete); |
890 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
891 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
892 | DT.deleteEdge(From, To); |
893 | EXPECT_TRUE(DT.verify()); |
894 | PDT.deleteEdge(From, To); |
895 | EXPECT_TRUE(PDT.verify()); |
896 | } |
897 | } |
898 | |
899 | TEST(DominatorTree, DeleteUnreachable) { |
900 | CFGHolder Holder; |
901 | std::vector<CFGBuilder::Arc> Arcs = { |
902 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
903 | {.From: "7" , .To: "8" }, {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "10" , .To: "2" }}; |
904 | |
905 | std::vector<CFGBuilder::Update> Updates = { |
906 | {.Action: Delete, .Edge: {.From: "8" , .To: "9" }}, {.Action: Delete, .Edge: {.From: "7" , .To: "8" }}, {.Action: Delete, .Edge: {.From: "3" , .To: "4" }}}; |
907 | CFGBuilder B(Holder.F, Arcs, Updates); |
908 | DominatorTree DT(*Holder.F); |
909 | EXPECT_TRUE(DT.verify()); |
910 | PostDominatorTree PDT(*Holder.F); |
911 | EXPECT_TRUE(PDT.verify()); |
912 | |
913 | std::optional<CFGBuilder::Update> LastUpdate; |
914 | while ((LastUpdate = B.applyUpdate())) { |
915 | EXPECT_EQ(LastUpdate->Action, Delete); |
916 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
917 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
918 | DT.deleteEdge(From, To); |
919 | EXPECT_TRUE(DT.verify()); |
920 | PDT.deleteEdge(From, To); |
921 | EXPECT_TRUE(PDT.verify()); |
922 | } |
923 | } |
924 | |
925 | TEST(DominatorTree, InsertDelete) { |
926 | std::vector<CFGBuilder::Arc> Arcs = { |
927 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
928 | {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }}; |
929 | |
930 | std::vector<CFGBuilder::Update> Updates = { |
931 | {.Action: Insert, .Edge: {.From: "2" , .To: "4" }}, {.Action: Insert, .Edge: {.From: "12" , .To: "10" }}, {.Action: Insert, .Edge: {.From: "10" , .To: "9" }}, |
932 | {.Action: Insert, .Edge: {.From: "7" , .To: "6" }}, {.Action: Insert, .Edge: {.From: "7" , .To: "5" }}, {.Action: Delete, .Edge: {.From: "3" , .To: "8" }}, |
933 | {.Action: Insert, .Edge: {.From: "10" , .To: "7" }}, {.Action: Insert, .Edge: {.From: "2" , .To: "8" }}, {.Action: Delete, .Edge: {.From: "3" , .To: "4" }}, |
934 | {.Action: Delete, .Edge: {.From: "8" , .To: "9" }}, {.Action: Delete, .Edge: {.From: "11" , .To: "12" }}}; |
935 | |
936 | CFGHolder Holder; |
937 | CFGBuilder B(Holder.F, Arcs, Updates); |
938 | DominatorTree DT(*Holder.F); |
939 | EXPECT_TRUE(DT.verify()); |
940 | PostDominatorTree PDT(*Holder.F); |
941 | EXPECT_TRUE(PDT.verify()); |
942 | |
943 | std::optional<CFGBuilder::Update> LastUpdate; |
944 | while ((LastUpdate = B.applyUpdate())) { |
945 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
946 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
947 | if (LastUpdate->Action == Insert) { |
948 | DT.insertEdge(From, To); |
949 | PDT.insertEdge(From, To); |
950 | } else { |
951 | DT.deleteEdge(From, To); |
952 | PDT.deleteEdge(From, To); |
953 | } |
954 | |
955 | EXPECT_TRUE(DT.verify()); |
956 | EXPECT_TRUE(PDT.verify()); |
957 | } |
958 | } |
959 | |
960 | TEST(DominatorTree, InsertDeleteExhaustive) { |
961 | std::vector<CFGBuilder::Arc> Arcs = { |
962 | {.From: "1" , .To: "2" }, {.From: "2" , .To: "3" }, {.From: "3" , .To: "4" }, {.From: "4" , .To: "5" }, {.From: "5" , .To: "6" }, {.From: "5" , .To: "7" }, |
963 | {.From: "3" , .To: "8" }, {.From: "8" , .To: "9" }, {.From: "9" , .To: "10" }, {.From: "8" , .To: "11" }, {.From: "11" , .To: "12" }}; |
964 | |
965 | std::vector<CFGBuilder::Update> Updates = { |
966 | {.Action: Insert, .Edge: {.From: "2" , .To: "4" }}, {.Action: Insert, .Edge: {.From: "12" , .To: "10" }}, {.Action: Insert, .Edge: {.From: "10" , .To: "9" }}, |
967 | {.Action: Insert, .Edge: {.From: "7" , .To: "6" }}, {.Action: Insert, .Edge: {.From: "7" , .To: "5" }}, {.Action: Delete, .Edge: {.From: "3" , .To: "8" }}, |
968 | {.Action: Insert, .Edge: {.From: "10" , .To: "7" }}, {.Action: Insert, .Edge: {.From: "2" , .To: "8" }}, {.Action: Delete, .Edge: {.From: "3" , .To: "4" }}, |
969 | {.Action: Delete, .Edge: {.From: "8" , .To: "9" }}, {.Action: Delete, .Edge: {.From: "11" , .To: "12" }}}; |
970 | |
971 | std::mt19937 Generator(0); |
972 | for (unsigned i = 0; i < 16; ++i) { |
973 | std::shuffle(first: Updates.begin(), last: Updates.end(), g&: Generator); |
974 | CFGHolder Holder; |
975 | CFGBuilder B(Holder.F, Arcs, Updates); |
976 | DominatorTree DT(*Holder.F); |
977 | EXPECT_TRUE(DT.verify()); |
978 | PostDominatorTree PDT(*Holder.F); |
979 | EXPECT_TRUE(PDT.verify()); |
980 | |
981 | std::optional<CFGBuilder::Update> LastUpdate; |
982 | while ((LastUpdate = B.applyUpdate())) { |
983 | BasicBlock *From = B.getOrAddBlock(BlockName: LastUpdate->Edge.From); |
984 | BasicBlock *To = B.getOrAddBlock(BlockName: LastUpdate->Edge.To); |
985 | if (LastUpdate->Action == Insert) { |
986 | DT.insertEdge(From, To); |
987 | PDT.insertEdge(From, To); |
988 | } else { |
989 | DT.deleteEdge(From, To); |
990 | PDT.deleteEdge(From, To); |
991 | } |
992 | |
993 | EXPECT_TRUE(DT.verify()); |
994 | EXPECT_TRUE(PDT.verify()); |
995 | } |
996 | } |
997 | } |
998 | |
999 | TEST(DominatorTree, InsertIntoIrreducible) { |
1000 | std::vector<CFGBuilder::Arc> Arcs = { |
1001 | {.From: "0" , .To: "1" }, |
1002 | {.From: "1" , .To: "27" }, {.From: "1" , .To: "7" }, |
1003 | {.From: "10" , .To: "18" }, |
1004 | {.From: "13" , .To: "10" }, |
1005 | {.From: "18" , .To: "13" }, {.From: "18" , .To: "23" }, |
1006 | {.From: "23" , .To: "13" }, {.From: "23" , .To: "24" }, |
1007 | {.From: "24" , .To: "1" }, {.From: "24" , .To: "18" }, |
1008 | {.From: "27" , .To: "24" }}; |
1009 | |
1010 | CFGHolder Holder; |
1011 | CFGBuilder B(Holder.F, Arcs, {{.Action: Insert, .Edge: {.From: "7" , .To: "23" }}}); |
1012 | DominatorTree DT(*Holder.F); |
1013 | EXPECT_TRUE(DT.verify()); |
1014 | |
1015 | B.applyUpdate(); |
1016 | BasicBlock *From = B.getOrAddBlock(BlockName: "7" ); |
1017 | BasicBlock *To = B.getOrAddBlock(BlockName: "23" ); |
1018 | DT.insertEdge(From, To); |
1019 | |
1020 | EXPECT_TRUE(DT.verify()); |
1021 | } |
1022 | |
1023 | TEST(DominatorTree, EdgeDomination) { |
1024 | StringRef ModuleString = "define i32 @f(i1 %cond) {\n" |
1025 | " bb0:\n" |
1026 | " br i1 %cond, label %bb1, label %bb2\n" |
1027 | " bb1:\n" |
1028 | " br label %bb3\n" |
1029 | " bb2:\n" |
1030 | " br label %bb3\n" |
1031 | " bb3:\n" |
1032 | " ret i32 4" |
1033 | "}\n" ; |
1034 | |
1035 | // Parse the module. |
1036 | LLVMContext Context; |
1037 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
1038 | |
1039 | runWithDomTree(M&: *M, FuncName: "f" , |
1040 | Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
1041 | Function::iterator FI = F.begin(); |
1042 | |
1043 | BasicBlock *BB0 = &*FI++; |
1044 | BasicBlock *BB1 = &*FI++; |
1045 | BasicBlock *BB2 = &*FI++; |
1046 | BasicBlock *BB3 = &*FI++; |
1047 | |
1048 | BasicBlockEdge E01(BB0, BB1); |
1049 | BasicBlockEdge E02(BB0, BB2); |
1050 | BasicBlockEdge E13(BB1, BB3); |
1051 | BasicBlockEdge E23(BB2, BB3); |
1052 | |
1053 | EXPECT_TRUE(DT->dominates(E01, E01)); |
1054 | EXPECT_FALSE(DT->dominates(E01, E02)); |
1055 | EXPECT_TRUE(DT->dominates(E01, E13)); |
1056 | EXPECT_FALSE(DT->dominates(E01, E23)); |
1057 | |
1058 | EXPECT_FALSE(DT->dominates(E02, E01)); |
1059 | EXPECT_TRUE(DT->dominates(E02, E02)); |
1060 | EXPECT_FALSE(DT->dominates(E02, E13)); |
1061 | EXPECT_TRUE(DT->dominates(E02, E23)); |
1062 | |
1063 | EXPECT_FALSE(DT->dominates(E13, E01)); |
1064 | EXPECT_FALSE(DT->dominates(E13, E02)); |
1065 | EXPECT_TRUE(DT->dominates(E13, E13)); |
1066 | EXPECT_FALSE(DT->dominates(E13, E23)); |
1067 | |
1068 | EXPECT_FALSE(DT->dominates(E23, E01)); |
1069 | EXPECT_FALSE(DT->dominates(E23, E02)); |
1070 | EXPECT_FALSE(DT->dominates(E23, E13)); |
1071 | EXPECT_TRUE(DT->dominates(E23, E23)); |
1072 | }); |
1073 | } |
1074 | |
1075 | TEST(DominatorTree, ValueDomination) { |
1076 | StringRef ModuleString = R"( |
1077 | @foo = global i8 0 |
1078 | define i8 @f(i8 %arg) { |
1079 | ret i8 %arg |
1080 | } |
1081 | )" ; |
1082 | |
1083 | LLVMContext Context; |
1084 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
1085 | |
1086 | runWithDomTree(M&: *M, FuncName: "f" , |
1087 | Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
1088 | Argument *A = F.getArg(i: 0); |
1089 | GlobalValue *G = M->getNamedValue(Name: "foo" ); |
1090 | Constant *C = ConstantInt::getNullValue(Ty: Type::getInt8Ty(C&: Context)); |
1091 | |
1092 | Instruction *I = F.getEntryBlock().getTerminator(); |
1093 | EXPECT_TRUE(DT->dominates(A, I)); |
1094 | EXPECT_TRUE(DT->dominates(G, I)); |
1095 | EXPECT_TRUE(DT->dominates(C, I)); |
1096 | |
1097 | const Use &U = I->getOperandUse(i: 0); |
1098 | EXPECT_TRUE(DT->dominates(A, U)); |
1099 | EXPECT_TRUE(DT->dominates(G, U)); |
1100 | EXPECT_TRUE(DT->dominates(C, U)); |
1101 | }); |
1102 | } |
1103 | TEST(DominatorTree, CallBrDomination) { |
1104 | StringRef ModuleString = R"( |
1105 | define void @x() { |
1106 | %y = alloca i32 |
1107 | %w = callbr i32 asm "", "=r,!i"() |
1108 | to label %asm.fallthrough [label %z] |
1109 | |
1110 | asm.fallthrough: |
1111 | br label %cleanup |
1112 | |
1113 | z: |
1114 | store i32 %w, ptr %y |
1115 | br label %cleanup |
1116 | |
1117 | cleanup: |
1118 | ret void |
1119 | })" ; |
1120 | |
1121 | LLVMContext Context; |
1122 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr: ModuleString); |
1123 | |
1124 | runWithDomTree( |
1125 | M&: *M, FuncName: "x" , Test: [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { |
1126 | Function::iterator FI = F.begin(); |
1127 | |
1128 | BasicBlock *Entry = &*FI++; |
1129 | BasicBlock *ASMFallthrough = &*FI++; |
1130 | BasicBlock *Z = &*FI++; |
1131 | |
1132 | EXPECT_TRUE(DT->dominates(Entry, ASMFallthrough)); |
1133 | EXPECT_TRUE(DT->dominates(Entry, Z)); |
1134 | |
1135 | BasicBlock::iterator BBI = Entry->begin(); |
1136 | ++BBI; |
1137 | Instruction &I = *BBI; |
1138 | EXPECT_TRUE(isa<CallBrInst>(I)); |
1139 | EXPECT_TRUE(isa<Value>(I)); |
1140 | for (const User *U : I.users()) { |
1141 | EXPECT_TRUE(isa<Instruction>(U)); |
1142 | EXPECT_TRUE(DT->dominates(cast<Value>(&I), cast<Instruction>(U))); |
1143 | } |
1144 | }); |
1145 | } |
1146 | |