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

source code of llvm/unittests/IR/DominatorTreeTest.cpp