1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/IR/Dominators.h"
11 #include "llvm/Analysis/PostDominators.h"
12 #include "llvm/AsmParser/Parser.h"
13 #include "llvm/IR/Instructions.h"
14 #include "llvm/IR/LLVMContext.h"
15 #include "llvm/IR/Module.h"
16 #include "llvm/PassManager.h"
17 #include "llvm/Support/SourceMgr.h"
18 #include "gtest/gtest.h"
23 void initializeDPassPass(PassRegistry&);
26 struct DPass : public FunctionPass {
28 virtual bool runOnFunction(Function &F) {
30 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
31 PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
32 Function::iterator FI = F.begin();
34 BasicBlock *BB0 = FI++;
35 BasicBlock::iterator BBI = BB0->begin();
36 Instruction *Y1 = BBI++;
37 Instruction *Y2 = BBI++;
38 Instruction *Y3 = BBI++;
40 BasicBlock *BB1 = FI++;
42 Instruction *Y4 = BBI++;
44 BasicBlock *BB2 = FI++;
46 Instruction *Y5 = BBI++;
48 BasicBlock *BB3 = FI++;
50 Instruction *Y6 = BBI++;
51 Instruction *Y7 = BBI++;
53 BasicBlock *BB4 = FI++;
55 Instruction *Y8 = BBI++;
56 Instruction *Y9 = BBI++;
59 EXPECT_TRUE(DT->isReachableFromEntry(BB0));
60 EXPECT_TRUE(DT->isReachableFromEntry(BB1));
61 EXPECT_TRUE(DT->isReachableFromEntry(BB2));
62 EXPECT_FALSE(DT->isReachableFromEntry(BB3));
63 EXPECT_TRUE(DT->isReachableFromEntry(BB4));
66 EXPECT_TRUE(DT->dominates(BB0, BB0));
67 EXPECT_TRUE(DT->dominates(BB0, BB1));
68 EXPECT_TRUE(DT->dominates(BB0, BB2));
69 EXPECT_TRUE(DT->dominates(BB0, BB3));
70 EXPECT_TRUE(DT->dominates(BB0, BB4));
72 EXPECT_FALSE(DT->dominates(BB1, BB0));
73 EXPECT_TRUE(DT->dominates(BB1, BB1));
74 EXPECT_FALSE(DT->dominates(BB1, BB2));
75 EXPECT_TRUE(DT->dominates(BB1, BB3));
76 EXPECT_FALSE(DT->dominates(BB1, BB4));
78 EXPECT_FALSE(DT->dominates(BB2, BB0));
79 EXPECT_FALSE(DT->dominates(BB2, BB1));
80 EXPECT_TRUE(DT->dominates(BB2, BB2));
81 EXPECT_TRUE(DT->dominates(BB2, BB3));
82 EXPECT_FALSE(DT->dominates(BB2, BB4));
84 EXPECT_FALSE(DT->dominates(BB3, BB0));
85 EXPECT_FALSE(DT->dominates(BB3, BB1));
86 EXPECT_FALSE(DT->dominates(BB3, BB2));
87 EXPECT_TRUE(DT->dominates(BB3, BB3));
88 EXPECT_FALSE(DT->dominates(BB3, BB4));
90 // BB proper dominance
91 EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
92 EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
93 EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
94 EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
96 EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
97 EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
98 EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
99 EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
101 EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
102 EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
103 EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
104 EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
106 EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
107 EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
108 EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
109 EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
111 // Instruction dominance in the same reachable BB
112 EXPECT_FALSE(DT->dominates(Y1, Y1));
113 EXPECT_TRUE(DT->dominates(Y1, Y2));
114 EXPECT_FALSE(DT->dominates(Y2, Y1));
115 EXPECT_FALSE(DT->dominates(Y2, Y2));
117 // Instruction dominance in the same unreachable BB
118 EXPECT_TRUE(DT->dominates(Y6, Y6));
119 EXPECT_TRUE(DT->dominates(Y6, Y7));
120 EXPECT_TRUE(DT->dominates(Y7, Y6));
121 EXPECT_TRUE(DT->dominates(Y7, Y7));
124 EXPECT_TRUE(DT->dominates(Y3, Y4));
125 EXPECT_FALSE(DT->dominates(Y3, Y5));
128 EXPECT_TRUE(DT->dominates(Y2, Y9));
129 EXPECT_FALSE(DT->dominates(Y3, Y9));
130 EXPECT_FALSE(DT->dominates(Y8, Y9));
132 // Anything dominates unreachable
133 EXPECT_TRUE(DT->dominates(Y1, Y6));
134 EXPECT_TRUE(DT->dominates(Y3, Y6));
136 // Unreachable doesn't dominate reachable
137 EXPECT_FALSE(DT->dominates(Y6, Y1));
139 // Instruction, BB dominance
140 EXPECT_FALSE(DT->dominates(Y1, BB0));
141 EXPECT_TRUE(DT->dominates(Y1, BB1));
142 EXPECT_TRUE(DT->dominates(Y1, BB2));
143 EXPECT_TRUE(DT->dominates(Y1, BB3));
144 EXPECT_TRUE(DT->dominates(Y1, BB4));
146 EXPECT_FALSE(DT->dominates(Y3, BB0));
147 EXPECT_TRUE(DT->dominates(Y3, BB1));
148 EXPECT_FALSE(DT->dominates(Y3, BB2));
149 EXPECT_TRUE(DT->dominates(Y3, BB3));
150 EXPECT_FALSE(DT->dominates(Y3, BB4));
152 EXPECT_TRUE(DT->dominates(Y6, BB3));
155 EXPECT_TRUE(PDT->dominates(BB0, BB0));
156 EXPECT_FALSE(PDT->dominates(BB1, BB0));
157 EXPECT_FALSE(PDT->dominates(BB2, BB0));
158 EXPECT_FALSE(PDT->dominates(BB3, BB0));
159 EXPECT_TRUE(PDT->dominates(BB4, BB1));
161 // Dominance descendants.
162 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs;
164 DT->getDescendants(BB0, DominatedBBs);
165 PDT->getDescendants(BB0, PostDominatedBBs);
166 EXPECT_EQ(DominatedBBs.size(), 4UL);
167 EXPECT_EQ(PostDominatedBBs.size(), 1UL);
169 // BB3 is unreachable. It should have no dominators nor postdominators.
170 DominatedBBs.clear();
171 PostDominatedBBs.clear();
172 DT->getDescendants(BB3, DominatedBBs);
173 DT->getDescendants(BB3, PostDominatedBBs);
174 EXPECT_EQ(DominatedBBs.size(), 0UL);
175 EXPECT_EQ(PostDominatedBBs.size(), 0UL);
179 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
180 AU.addRequired<DominatorTreeWrapperPass>();
181 AU.addRequired<PostDominatorTree>();
183 DPass() : FunctionPass(ID) {
184 initializeDPassPass(*PassRegistry::getPassRegistry());
189 std::unique_ptr<Module> makeLLVMModule(DPass *P) {
190 const char *ModuleStrig =
191 "declare i32 @g()\n" \
192 "define void @f(i32 %x) {\n" \
194 " %y1 = add i32 %x, 1\n" \
195 " %y2 = add i32 %x, 1\n" \
196 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \
198 " %y4 = add i32 %x, 1\n" \
201 " %y5 = landingpad i32 personality i32 ()* @g\n" \
205 " %y6 = add i32 %x, 1\n" \
206 " %y7 = add i32 %x, 1\n" \
209 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
210 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
213 LLVMContext &C = getGlobalContext();
215 return parseAssemblyString(ModuleStrig, Err, C);
218 TEST(DominatorTree, Unreachable) {
219 DPass *P = new DPass();
220 std::unique_ptr<Module> M = makeLLVMModule(P);
228 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
229 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
230 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
231 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)