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(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(ModuleStr, Err, Context);
42   assert(M && "Bad assembly?");
43   return M;
44 }
45 
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 
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 //
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 //
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 //
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 //
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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