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