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