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/Constants.h"
14 #include "llvm/IR/Instructions.h"
15 #include "llvm/IR/LLVMContext.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/IR/LegacyPassManager.h"
18 #include "llvm/Support/SourceMgr.h"
19 #include "gtest/gtest.h"
24 void initializeDPassPass(PassRegistry&);
27 struct DPass : public FunctionPass {
29 bool runOnFunction(Function &F) override {
31 &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
32 PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
33 Function::iterator FI = F.begin();
35 BasicBlock *BB0 = FI++;
36 BasicBlock::iterator BBI = BB0->begin();
37 Instruction *Y1 = BBI++;
38 Instruction *Y2 = BBI++;
39 Instruction *Y3 = BBI++;
41 BasicBlock *BB1 = FI++;
43 Instruction *Y4 = BBI++;
45 BasicBlock *BB2 = FI++;
47 Instruction *Y5 = BBI++;
49 BasicBlock *BB3 = FI++;
51 Instruction *Y6 = BBI++;
52 Instruction *Y7 = BBI++;
54 BasicBlock *BB4 = FI++;
56 Instruction *Y8 = BBI++;
57 Instruction *Y9 = BBI++;
60 EXPECT_TRUE(DT->isReachableFromEntry(BB0));
61 EXPECT_TRUE(DT->isReachableFromEntry(BB1));
62 EXPECT_TRUE(DT->isReachableFromEntry(BB2));
63 EXPECT_FALSE(DT->isReachableFromEntry(BB3));
64 EXPECT_TRUE(DT->isReachableFromEntry(BB4));
67 EXPECT_TRUE(DT->dominates(BB0, BB0));
68 EXPECT_TRUE(DT->dominates(BB0, BB1));
69 EXPECT_TRUE(DT->dominates(BB0, BB2));
70 EXPECT_TRUE(DT->dominates(BB0, BB3));
71 EXPECT_TRUE(DT->dominates(BB0, BB4));
73 EXPECT_FALSE(DT->dominates(BB1, BB0));
74 EXPECT_TRUE(DT->dominates(BB1, BB1));
75 EXPECT_FALSE(DT->dominates(BB1, BB2));
76 EXPECT_TRUE(DT->dominates(BB1, BB3));
77 EXPECT_FALSE(DT->dominates(BB1, BB4));
79 EXPECT_FALSE(DT->dominates(BB2, BB0));
80 EXPECT_FALSE(DT->dominates(BB2, BB1));
81 EXPECT_TRUE(DT->dominates(BB2, BB2));
82 EXPECT_TRUE(DT->dominates(BB2, BB3));
83 EXPECT_FALSE(DT->dominates(BB2, BB4));
85 EXPECT_FALSE(DT->dominates(BB3, BB0));
86 EXPECT_FALSE(DT->dominates(BB3, BB1));
87 EXPECT_FALSE(DT->dominates(BB3, BB2));
88 EXPECT_TRUE(DT->dominates(BB3, BB3));
89 EXPECT_FALSE(DT->dominates(BB3, BB4));
91 // BB proper dominance
92 EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
93 EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
94 EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
95 EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
97 EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
98 EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
99 EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
100 EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
102 EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
103 EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
104 EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
105 EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
107 EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
108 EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
109 EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
110 EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
112 // Instruction dominance in the same reachable BB
113 EXPECT_FALSE(DT->dominates(Y1, Y1));
114 EXPECT_TRUE(DT->dominates(Y1, Y2));
115 EXPECT_FALSE(DT->dominates(Y2, Y1));
116 EXPECT_FALSE(DT->dominates(Y2, Y2));
118 // Instruction dominance in the same unreachable BB
119 EXPECT_TRUE(DT->dominates(Y6, Y6));
120 EXPECT_TRUE(DT->dominates(Y6, Y7));
121 EXPECT_TRUE(DT->dominates(Y7, Y6));
122 EXPECT_TRUE(DT->dominates(Y7, Y7));
125 EXPECT_TRUE(DT->dominates(Y3, Y4));
126 EXPECT_FALSE(DT->dominates(Y3, Y5));
129 EXPECT_TRUE(DT->dominates(Y2, Y9));
130 EXPECT_FALSE(DT->dominates(Y3, Y9));
131 EXPECT_FALSE(DT->dominates(Y8, Y9));
133 // Anything dominates unreachable
134 EXPECT_TRUE(DT->dominates(Y1, Y6));
135 EXPECT_TRUE(DT->dominates(Y3, Y6));
137 // Unreachable doesn't dominate reachable
138 EXPECT_FALSE(DT->dominates(Y6, Y1));
140 // Instruction, BB dominance
141 EXPECT_FALSE(DT->dominates(Y1, BB0));
142 EXPECT_TRUE(DT->dominates(Y1, BB1));
143 EXPECT_TRUE(DT->dominates(Y1, BB2));
144 EXPECT_TRUE(DT->dominates(Y1, BB3));
145 EXPECT_TRUE(DT->dominates(Y1, BB4));
147 EXPECT_FALSE(DT->dominates(Y3, BB0));
148 EXPECT_TRUE(DT->dominates(Y3, BB1));
149 EXPECT_FALSE(DT->dominates(Y3, BB2));
150 EXPECT_TRUE(DT->dominates(Y3, BB3));
151 EXPECT_FALSE(DT->dominates(Y3, BB4));
153 EXPECT_TRUE(DT->dominates(Y6, BB3));
156 EXPECT_TRUE(PDT->dominates(BB0, BB0));
157 EXPECT_FALSE(PDT->dominates(BB1, BB0));
158 EXPECT_FALSE(PDT->dominates(BB2, BB0));
159 EXPECT_FALSE(PDT->dominates(BB3, BB0));
160 EXPECT_TRUE(PDT->dominates(BB4, BB1));
162 // Dominance descendants.
163 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs;
165 DT->getDescendants(BB0, DominatedBBs);
166 PDT->getDescendants(BB0, PostDominatedBBs);
167 EXPECT_EQ(DominatedBBs.size(), 4UL);
168 EXPECT_EQ(PostDominatedBBs.size(), 1UL);
170 // BB3 is unreachable. It should have no dominators nor postdominators.
171 DominatedBBs.clear();
172 PostDominatedBBs.clear();
173 DT->getDescendants(BB3, DominatedBBs);
174 DT->getDescendants(BB3, PostDominatedBBs);
175 EXPECT_EQ(DominatedBBs.size(), 0UL);
176 EXPECT_EQ(PostDominatedBBs.size(), 0UL);
178 // Check DFS Numbers before
179 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
180 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL);
181 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
182 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL);
183 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL);
184 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL);
185 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL);
186 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL);
188 // Reattach block 3 to block 1 and recalculate
189 BB1->getTerminator()->eraseFromParent();
190 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1);
193 // Check DFS Numbers after
194 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL);
195 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL);
196 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL);
197 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL);
198 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL);
199 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL);
200 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL);
201 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL);
202 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL);
203 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL);
207 void getAnalysisUsage(AnalysisUsage &AU) const override {
208 AU.addRequired<DominatorTreeWrapperPass>();
209 AU.addRequired<PostDominatorTree>();
211 DPass() : FunctionPass(ID) {
212 initializeDPassPass(*PassRegistry::getPassRegistry());
217 std::unique_ptr<Module> makeLLVMModule(DPass *P) {
218 const char *ModuleStrig =
219 "declare i32 @g()\n" \
220 "define void @f(i32 %x) {\n" \
222 " %y1 = add i32 %x, 1\n" \
223 " %y2 = add i32 %x, 1\n" \
224 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \
226 " %y4 = add i32 %x, 1\n" \
229 " %y5 = landingpad i32 personality i32 ()* @g\n" \
233 " %y6 = add i32 %x, 1\n" \
234 " %y7 = add i32 %x, 1\n" \
237 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
238 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
241 LLVMContext &C = getGlobalContext();
243 return parseAssemblyString(ModuleStrig, Err, C);
246 TEST(DominatorTree, Unreachable) {
247 DPass *P = new DPass();
248 std::unique_ptr<Module> M = makeLLVMModule(P);
249 legacy::PassManager Passes;
256 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
257 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
258 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
259 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)