4e5af9395cc8c5184f994548dac62f1719e16bd6
[oota-llvm.git] / unittests / IR / DominatorTreeTest.cpp
1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/Analysis/Dominators.h"
11 #include "llvm/Assembly/Parser.h"
12 #include "llvm/IR/Instructions.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/PassManager.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "gtest/gtest.h"
18
19 using namespace llvm;
20
21 namespace llvm {
22   void initializeDPassPass(PassRegistry&);
23
24   namespace {
25     struct DPass : public FunctionPass {
26       static char ID;
27       virtual bool runOnFunction(Function &F) {
28         DominatorTree *DT = &getAnalysis<DominatorTree>();
29         Function::iterator FI = F.begin();
30
31         BasicBlock *BB0 = FI++;
32         BasicBlock::iterator BBI = BB0->begin();
33         Instruction *Y1 = BBI++;
34         Instruction *Y2 = BBI++;
35         Instruction *Y3 = BBI++;
36
37         BasicBlock *BB1 = FI++;
38         BBI = BB1->begin();
39         Instruction *Y4 = BBI++;
40
41         BasicBlock *BB2 = FI++;
42         BBI = BB2->begin();
43         Instruction *Y5 = BBI++;
44
45         BasicBlock *BB3 = FI++;
46         BBI = BB3->begin();
47         Instruction *Y6 = BBI++;
48         Instruction *Y7 = BBI++;
49
50         BasicBlock *BB4 = FI++;
51         BBI = BB4->begin();
52         Instruction *Y8 = BBI++;
53         Instruction *Y9 = BBI++;
54
55         // Reachability
56         EXPECT_TRUE(DT->isReachableFromEntry(BB0));
57         EXPECT_TRUE(DT->isReachableFromEntry(BB1));
58         EXPECT_TRUE(DT->isReachableFromEntry(BB2));
59         EXPECT_FALSE(DT->isReachableFromEntry(BB3));
60         EXPECT_TRUE(DT->isReachableFromEntry(BB4));
61
62         // BB dominance
63         EXPECT_TRUE(DT->dominates(BB0, BB0));
64         EXPECT_TRUE(DT->dominates(BB0, BB1));
65         EXPECT_TRUE(DT->dominates(BB0, BB2));
66         EXPECT_TRUE(DT->dominates(BB0, BB3));
67         EXPECT_TRUE(DT->dominates(BB0, BB4));
68
69         EXPECT_FALSE(DT->dominates(BB1, BB0));
70         EXPECT_TRUE(DT->dominates(BB1, BB1));
71         EXPECT_FALSE(DT->dominates(BB1, BB2));
72         EXPECT_TRUE(DT->dominates(BB1, BB3));
73         EXPECT_FALSE(DT->dominates(BB1, BB4));
74
75         EXPECT_FALSE(DT->dominates(BB2, BB0));
76         EXPECT_FALSE(DT->dominates(BB2, BB1));
77         EXPECT_TRUE(DT->dominates(BB2, BB2));
78         EXPECT_TRUE(DT->dominates(BB2, BB3));
79         EXPECT_FALSE(DT->dominates(BB2, BB4));
80
81         EXPECT_FALSE(DT->dominates(BB3, BB0));
82         EXPECT_FALSE(DT->dominates(BB3, BB1));
83         EXPECT_FALSE(DT->dominates(BB3, BB2));
84         EXPECT_TRUE(DT->dominates(BB3, BB3));
85         EXPECT_FALSE(DT->dominates(BB3, BB4));
86
87         // BB proper dominance
88         EXPECT_FALSE(DT->properlyDominates(BB0, BB0));
89         EXPECT_TRUE(DT->properlyDominates(BB0, BB1));
90         EXPECT_TRUE(DT->properlyDominates(BB0, BB2));
91         EXPECT_TRUE(DT->properlyDominates(BB0, BB3));
92
93         EXPECT_FALSE(DT->properlyDominates(BB1, BB0));
94         EXPECT_FALSE(DT->properlyDominates(BB1, BB1));
95         EXPECT_FALSE(DT->properlyDominates(BB1, BB2));
96         EXPECT_TRUE(DT->properlyDominates(BB1, BB3));
97
98         EXPECT_FALSE(DT->properlyDominates(BB2, BB0));
99         EXPECT_FALSE(DT->properlyDominates(BB2, BB1));
100         EXPECT_FALSE(DT->properlyDominates(BB2, BB2));
101         EXPECT_TRUE(DT->properlyDominates(BB2, BB3));
102
103         EXPECT_FALSE(DT->properlyDominates(BB3, BB0));
104         EXPECT_FALSE(DT->properlyDominates(BB3, BB1));
105         EXPECT_FALSE(DT->properlyDominates(BB3, BB2));
106         EXPECT_FALSE(DT->properlyDominates(BB3, BB3));
107
108         // Instruction dominance in the same reachable BB
109         EXPECT_FALSE(DT->dominates(Y1, Y1));
110         EXPECT_TRUE(DT->dominates(Y1, Y2));
111         EXPECT_FALSE(DT->dominates(Y2, Y1));
112         EXPECT_FALSE(DT->dominates(Y2, Y2));
113
114         // Instruction dominance in the same unreachable BB
115         EXPECT_TRUE(DT->dominates(Y6, Y6));
116         EXPECT_TRUE(DT->dominates(Y6, Y7));
117         EXPECT_TRUE(DT->dominates(Y7, Y6));
118         EXPECT_TRUE(DT->dominates(Y7, Y7));
119
120         // Invoke
121         EXPECT_TRUE(DT->dominates(Y3, Y4));
122         EXPECT_FALSE(DT->dominates(Y3, Y5));
123
124         // Phi
125         EXPECT_TRUE(DT->dominates(Y2, Y9));
126         EXPECT_FALSE(DT->dominates(Y3, Y9));
127         EXPECT_FALSE(DT->dominates(Y8, Y9));
128
129         // Anything dominates unreachable
130         EXPECT_TRUE(DT->dominates(Y1, Y6));
131         EXPECT_TRUE(DT->dominates(Y3, Y6));
132
133         // Unreachable doesn't dominate reachable
134         EXPECT_FALSE(DT->dominates(Y6, Y1));
135
136         // Instruction, BB dominance
137         EXPECT_FALSE(DT->dominates(Y1, BB0));
138         EXPECT_TRUE(DT->dominates(Y1, BB1));
139         EXPECT_TRUE(DT->dominates(Y1, BB2));
140         EXPECT_TRUE(DT->dominates(Y1, BB3));
141         EXPECT_TRUE(DT->dominates(Y1, BB4));
142
143         EXPECT_FALSE(DT->dominates(Y3, BB0));
144         EXPECT_TRUE(DT->dominates(Y3, BB1));
145         EXPECT_FALSE(DT->dominates(Y3, BB2));
146         EXPECT_TRUE(DT->dominates(Y3, BB3));
147         EXPECT_FALSE(DT->dominates(Y3, BB4));
148
149         EXPECT_TRUE(DT->dominates(Y6, BB3));
150
151         return false;
152       }
153       virtual void getAnalysisUsage(AnalysisUsage &AU) const {
154         AU.addRequired<DominatorTree>();
155       }
156       DPass() : FunctionPass(ID) {
157         initializeDPassPass(*PassRegistry::getPassRegistry());
158       }
159     };
160     char DPass::ID = 0;
161
162
163     Module* makeLLVMModule(DPass *P) {
164       const char *ModuleStrig =
165         "declare i32 @g()\n" \
166         "define void @f(i32 %x) {\n" \
167         "bb0:\n" \
168         "  %y1 = add i32 %x, 1\n" \
169         "  %y2 = add i32 %x, 1\n" \
170         "  %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \
171         "bb1:\n" \
172         "  %y4 = add i32 %x, 1\n" \
173         "  br label %bb4\n" \
174         "bb2:\n" \
175         "  %y5 = landingpad i32 personality i32 ()* @g\n" \
176         "          cleanup\n" \
177         "  br label %bb4\n" \
178         "bb3:\n" \
179         "  %y6 = add i32 %x, 1\n" \
180         "  %y7 = add i32 %x, 1\n" \
181         "  ret void\n" \
182         "bb4:\n" \
183         "  %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
184         "  %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
185         "  ret void\n" \
186         "}\n";
187       LLVMContext &C = getGlobalContext();
188       SMDiagnostic Err;
189       return ParseAssemblyString(ModuleStrig, NULL, Err, C);
190     }
191
192     TEST(DominatorTree, Unreachable) {
193       DPass *P = new DPass();
194       OwningPtr<Module> M(makeLLVMModule(P));
195       PassManager Passes;
196       Passes.add(P);
197       Passes.run(*M);
198     }
199   }
200 }
201
202 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
203 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
204 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)