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/Analysis/Dominators.h"
11 #include "llvm/Analysis/PostDominators.h"
12 #include "llvm/Assembly/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) {
29 DominatorTree *DT = &getAnalysis<DominatorTree>();
30 PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
31 Function::iterator FI = F.begin();
33 BasicBlock *BB0 = FI++;
34 BasicBlock::iterator BBI = BB0->begin();
35 Instruction *Y1 = BBI++;
36 Instruction *Y2 = BBI++;
37 Instruction *Y3 = BBI++;
39 BasicBlock *BB1 = FI++;
41 Instruction *Y4 = BBI++;
43 BasicBlock *BB2 = FI++;
45 Instruction *Y5 = BBI++;
47 BasicBlock *BB3 = FI++;
49 Instruction *Y6 = BBI++;
50 Instruction *Y7 = BBI++;
52 BasicBlock *BB4 = FI++;
54 Instruction *Y8 = BBI++;
55 Instruction *Y9 = BBI++;
58 EXPECT_TRUE(DT->isReachableFromEntry(BB0));
59 EXPECT_TRUE(DT->isReachableFromEntry(BB1));
60 EXPECT_TRUE(DT->isReachableFromEntry(BB2));
61 EXPECT_FALSE(DT->isReachableFromEntry(BB3));
62 EXPECT_TRUE(DT->isReachableFromEntry(BB4));
65 EXPECT_TRUE(DT->dominates(BB0, BB0));
66 EXPECT_TRUE(DT->dominates(BB0, BB1));
67 EXPECT_TRUE(DT->dominates(BB0, BB2));
68 EXPECT_TRUE(DT->dominates(BB0, BB3));
69 EXPECT_TRUE(DT->dominates(BB0, BB4));
71 EXPECT_FALSE(DT->dominates(BB1, BB0));
72 EXPECT_TRUE(DT->dominates(BB1, BB1));
73 EXPECT_FALSE(DT->dominates(BB1, BB2));
74 EXPECT_TRUE(DT->dominates(BB1, BB3));
75 EXPECT_FALSE(DT->dominates(BB1, BB4));
77 EXPECT_FALSE(DT->dominates(BB2, BB0));
78 EXPECT_FALSE(DT->dominates(BB2, BB1));
79 EXPECT_TRUE(DT->dominates(BB2, BB2));
80 EXPECT_TRUE(DT->dominates(BB2, BB3));
81 EXPECT_FALSE(DT->dominates(BB2, BB4));
83 EXPECT_FALSE(DT->dominates(BB3, BB0));
84 EXPECT_FALSE(DT->dominates(BB3, BB1));
85 EXPECT_FALSE(DT->dominates(BB3, BB2));
86 EXPECT_TRUE(DT->dominates(BB3, BB3));
87 EXPECT_FALSE(DT->dominates(BB3, BB4));
89 // BB proper dominance
90 EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
91 EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
92 EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
93 EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
95 EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
96 EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
97 EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
98 EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
100 EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
101 EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
102 EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
103 EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
105 EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
106 EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
107 EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
108 EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
110 // Instruction dominance in the same reachable BB
111 EXPECT_FALSE(DT->dominates(Y1, Y1));
112 EXPECT_TRUE(DT->dominates(Y1, Y2));
113 EXPECT_FALSE(DT->dominates(Y2, Y1));
114 EXPECT_FALSE(DT->dominates(Y2, Y2));
116 // Instruction dominance in the same unreachable BB
117 EXPECT_TRUE(DT->dominates(Y6, Y6));
118 EXPECT_TRUE(DT->dominates(Y6, Y7));
119 EXPECT_TRUE(DT->dominates(Y7, Y6));
120 EXPECT_TRUE(DT->dominates(Y7, Y7));
123 EXPECT_TRUE(DT->dominates(Y3, Y4));
124 EXPECT_FALSE(DT->dominates(Y3, Y5));
127 EXPECT_TRUE(DT->dominates(Y2, Y9));
128 EXPECT_FALSE(DT->dominates(Y3, Y9));
129 EXPECT_FALSE(DT->dominates(Y8, Y9));
131 // Anything dominates unreachable
132 EXPECT_TRUE(DT->dominates(Y1, Y6));
133 EXPECT_TRUE(DT->dominates(Y3, Y6));
135 // Unreachable doesn't dominate reachable
136 EXPECT_FALSE(DT->dominates(Y6, Y1));
138 // Instruction, BB dominance
139 EXPECT_FALSE(DT->dominates(Y1, BB0));
140 EXPECT_TRUE(DT->dominates(Y1, BB1));
141 EXPECT_TRUE(DT->dominates(Y1, BB2));
142 EXPECT_TRUE(DT->dominates(Y1, BB3));
143 EXPECT_TRUE(DT->dominates(Y1, BB4));
145 EXPECT_FALSE(DT->dominates(Y3, BB0));
146 EXPECT_TRUE(DT->dominates(Y3, BB1));
147 EXPECT_FALSE(DT->dominates(Y3, BB2));
148 EXPECT_TRUE(DT->dominates(Y3, BB3));
149 EXPECT_FALSE(DT->dominates(Y3, BB4));
151 EXPECT_TRUE(DT->dominates(Y6, BB3));
154 EXPECT_TRUE(PDT->dominates(BB0, BB0));
155 EXPECT_FALSE(PDT->dominates(BB1, BB0));
156 EXPECT_FALSE(PDT->dominates(BB2, BB0));
157 EXPECT_FALSE(PDT->dominates(BB3, BB0));
158 EXPECT_TRUE(PDT->dominates(BB4, BB1));
160 // Dominance descendants.
161 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs;
163 DT->getDescendants(BB0, DominatedBBs);
164 PDT->getDescendants(BB0, PostDominatedBBs);
165 EXPECT_EQ(DominatedBBs.size(), 4UL);
166 EXPECT_EQ(PostDominatedBBs.size(), 1UL);
168 // BB3 is unreachable. It should have no dominators nor postdominators.
169 DominatedBBs.clear();
170 PostDominatedBBs.clear();
171 DT->getDescendants(BB3, DominatedBBs);
172 DT->getDescendants(BB3, PostDominatedBBs);
173 EXPECT_EQ(DominatedBBs.size(), 0UL);
174 EXPECT_EQ(PostDominatedBBs.size(), 0UL);
178 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
179 AU.addRequired<DominatorTree>();
180 AU.addRequired<PostDominatorTree>();
182 DPass() : FunctionPass(ID) {
183 initializeDPassPass(*PassRegistry::getPassRegistry());
189 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, NULL, Err, C);
218 TEST(DominatorTree, Unreachable) {
219 DPass *P = new DPass();
220 OwningPtr<Module> M(makeLLVMModule(P));
228 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
229 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
230 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
231 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)