1 #include "llvm/Analysis/Dominators.h"
2 #include "llvm/Assembly/Parser.h"
3 #include "llvm/IR/Instructions.h"
4 #include "llvm/IR/LLVMContext.h"
5 #include "llvm/IR/Module.h"
6 #include "llvm/PassManager.h"
7 #include "llvm/Support/SourceMgr.h"
8 #include "gtest/gtest.h"
13 void initializeDPassPass(PassRegistry&);
16 struct DPass : public FunctionPass {
18 virtual bool runOnFunction(Function &F) {
19 DominatorTree *DT = &getAnalysis<DominatorTree>();
20 Function::iterator FI = F.begin();
22 BasicBlock *BB0 = FI++;
23 BasicBlock::iterator BBI = BB0->begin();
24 Instruction *Y1 = BBI++;
25 Instruction *Y2 = BBI++;
26 Instruction *Y3 = BBI++;
28 BasicBlock *BB1 = FI++;
30 Instruction *Y4 = BBI++;
32 BasicBlock *BB2 = FI++;
34 Instruction *Y5 = BBI++;
36 BasicBlock *BB3 = FI++;
38 Instruction *Y6 = BBI++;
39 Instruction *Y7 = BBI++;
41 BasicBlock *BB4 = FI++;
43 Instruction *Y8 = BBI++;
44 Instruction *Y9 = BBI++;
47 EXPECT_TRUE(DT->isReachableFromEntry(BB0));
48 EXPECT_TRUE(DT->isReachableFromEntry(BB1));
49 EXPECT_TRUE(DT->isReachableFromEntry(BB2));
50 EXPECT_FALSE(DT->isReachableFromEntry(BB3));
51 EXPECT_TRUE(DT->isReachableFromEntry(BB4));
54 EXPECT_TRUE(DT->dominates(BB0, BB0));
55 EXPECT_TRUE(DT->dominates(BB0, BB1));
56 EXPECT_TRUE(DT->dominates(BB0, BB2));
57 EXPECT_TRUE(DT->dominates(BB0, BB3));
58 EXPECT_TRUE(DT->dominates(BB0, BB4));
60 EXPECT_FALSE(DT->dominates(BB1, BB0));
61 EXPECT_TRUE(DT->dominates(BB1, BB1));
62 EXPECT_FALSE(DT->dominates(BB1, BB2));
63 EXPECT_TRUE(DT->dominates(BB1, BB3));
64 EXPECT_FALSE(DT->dominates(BB1, BB4));
66 EXPECT_FALSE(DT->dominates(BB2, BB0));
67 EXPECT_FALSE(DT->dominates(BB2, BB1));
68 EXPECT_TRUE(DT->dominates(BB2, BB2));
69 EXPECT_TRUE(DT->dominates(BB2, BB3));
70 EXPECT_FALSE(DT->dominates(BB2, BB4));
72 EXPECT_FALSE(DT->dominates(BB3, BB0));
73 EXPECT_FALSE(DT->dominates(BB3, BB1));
74 EXPECT_FALSE(DT->dominates(BB3, BB2));
75 EXPECT_TRUE(DT->dominates(BB3, BB3));
76 EXPECT_FALSE(DT->dominates(BB3, BB4));
78 // BB proper dominance
79 EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
80 EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
81 EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
82 EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
84 EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
85 EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
86 EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
87 EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
89 EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
90 EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
91 EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
92 EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
94 EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
95 EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
96 EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
97 EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
99 // Instruction dominance in the same reachable BB
100 EXPECT_FALSE(DT->dominates(Y1, Y1));
101 EXPECT_TRUE(DT->dominates(Y1, Y2));
102 EXPECT_FALSE(DT->dominates(Y2, Y1));
103 EXPECT_FALSE(DT->dominates(Y2, Y2));
105 // Instruction dominance in the same unreachable BB
106 EXPECT_TRUE(DT->dominates(Y6, Y6));
107 EXPECT_TRUE(DT->dominates(Y6, Y7));
108 EXPECT_TRUE(DT->dominates(Y7, Y6));
109 EXPECT_TRUE(DT->dominates(Y7, Y7));
112 EXPECT_TRUE(DT->dominates(Y3, Y4));
113 EXPECT_FALSE(DT->dominates(Y3, Y5));
116 EXPECT_TRUE(DT->dominates(Y2, Y9));
117 EXPECT_FALSE(DT->dominates(Y3, Y9));
118 EXPECT_FALSE(DT->dominates(Y8, Y9));
120 // Anything dominates unreachable
121 EXPECT_TRUE(DT->dominates(Y1, Y6));
122 EXPECT_TRUE(DT->dominates(Y3, Y6));
124 // Unreachable doesn't dominate reachable
125 EXPECT_FALSE(DT->dominates(Y6, Y1));
127 // Instruction, BB dominance
128 EXPECT_FALSE(DT->dominates(Y1, BB0));
129 EXPECT_TRUE(DT->dominates(Y1, BB1));
130 EXPECT_TRUE(DT->dominates(Y1, BB2));
131 EXPECT_TRUE(DT->dominates(Y1, BB3));
132 EXPECT_TRUE(DT->dominates(Y1, BB4));
134 EXPECT_FALSE(DT->dominates(Y3, BB0));
135 EXPECT_TRUE(DT->dominates(Y3, BB1));
136 EXPECT_FALSE(DT->dominates(Y3, BB2));
137 EXPECT_TRUE(DT->dominates(Y3, BB3));
138 EXPECT_FALSE(DT->dominates(Y3, BB4));
140 EXPECT_TRUE(DT->dominates(Y6, BB3));
144 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
145 AU.addRequired<DominatorTree>();
147 DPass() : FunctionPass(ID) {
148 initializeDPassPass(*PassRegistry::getPassRegistry());
154 Module* makeLLVMModule(DPass *P) {
155 const char *ModuleStrig =
156 "declare i32 @g()\n" \
157 "define void @f(i32 %x) {\n" \
159 " %y1 = add i32 %x, 1\n" \
160 " %y2 = add i32 %x, 1\n" \
161 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \
163 " %y4 = add i32 %x, 1\n" \
166 " %y5 = landingpad i32 personality i32 ()* @g\n" \
170 " %y6 = add i32 %x, 1\n" \
171 " %y7 = add i32 %x, 1\n" \
174 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
175 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
178 LLVMContext &C = getGlobalContext();
180 return ParseAssemblyString(ModuleStrig, NULL, Err, C);
183 TEST(DominatorTree, Unreachable) {
184 DPass *P = new DPass();
185 Module *M = makeLLVMModule(P);
193 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
194 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
195 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)