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