1#include "llvm/Instructions.h"
2#include "llvm/LLVMContext.h"
3#include "llvm/Module.h"
4#include "llvm/PassManager.h"
5#include "llvm/Analysis/Dominators.h"
6#include "llvm/Assembly/Parser.h"
7#include "llvm/Support/SourceMgr.h"
8#include "gtest/gtest.h"
9
10using namespace llvm;
11
12namespace llvm {
13  void initializeDPassPass(PassRegistry&);
14
15  namespace {
16    struct DPass : public FunctionPass {
17      static char ID;
18      virtual bool runOnFunction(Function &F) {
19        DominatorTree *DT = &getAnalysis<DominatorTree>();
20        Function::iterator FI = F.begin();
21
22        BasicBlock *BB0 = FI++;
23        BasicBlock::iterator BBI = BB0->begin();
24        Instruction *Y1 = BBI++;
25        Instruction *Y2 = BBI++;
26        Instruction *Y3 = BBI++;
27
28        BasicBlock *BB1 = FI++;
29        BBI = BB1->begin();
30        Instruction *Y4 = BBI++;
31
32        BasicBlock *BB2 = FI++;
33        BBI = BB2->begin();
34        Instruction *Y5 = BBI++;
35
36        BasicBlock *BB3 = FI++;
37        BBI = BB3->begin();
38        Instruction *Y6 = BBI++;
39        Instruction *Y7 = BBI++;
40
41        BasicBlock *BB4 = FI++;
42        BBI = BB4->begin();
43        Instruction *Y8 = BBI++;
44        Instruction *Y9 = BBI++;
45
46        // Reachability
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));
52
53        // BB dominance
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));
59
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));
65
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));
71
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));
77
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));
83
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));
88
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));
93
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));
98
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));
104
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));
110
111        // Invoke
112        EXPECT_TRUE(DT->dominates(Y3, Y4));
113        EXPECT_FALSE(DT->dominates(Y3, Y5));
114
115        // Phi
116        EXPECT_TRUE(DT->dominates(Y2, Y9));
117        EXPECT_FALSE(DT->dominates(Y3, Y9));
118        EXPECT_FALSE(DT->dominates(Y8, Y9));
119
120        // Anything dominates unreachable
121        EXPECT_TRUE(DT->dominates(Y1, Y6));
122        EXPECT_TRUE(DT->dominates(Y3, Y6));
123
124        // Unreachable doesn't dominate reachable
125        EXPECT_FALSE(DT->dominates(Y6, Y1));
126
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));
133
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));
139
140        EXPECT_TRUE(DT->dominates(Y6, BB3));
141
142        return false;
143      }
144      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
145        AU.addRequired<DominatorTree>();
146      }
147      DPass() : FunctionPass(ID) {
148        initializeDPassPass(*PassRegistry::getPassRegistry());
149      }
150    };
151    char DPass::ID = 0;
152
153
154    Module* makeLLVMModule(DPass *P) {
155      const char *ModuleStrig =
156        "declare i32 @g()\n" \
157        "define void @f(i32 %x) {\n" \
158        "bb0:\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" \
162        "bb1:\n" \
163        "  %y4 = add i32 %x, 1\n" \
164        "  br label %bb4\n" \
165        "bb2:\n" \
166        "  %y5 = landingpad i32 personality i32 ()* @g\n" \
167        "          cleanup\n" \
168        "  br label %bb4\n" \
169        "bb3:\n" \
170        "  %y6 = add i32 %x, 1\n" \
171        "  %y7 = add i32 %x, 1\n" \
172        "  ret void\n" \
173        "bb4:\n" \
174        "  %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n"
175        "  %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n"
176        "  ret void\n" \
177        "}\n";
178      LLVMContext &C = getGlobalContext();
179      SMDiagnostic Err;
180      return ParseAssemblyString(ModuleStrig, NULL, Err, C);
181    }
182
183    TEST(DominatorTree, Unreachable) {
184      DPass *P = new DPass();
185      Module *M = makeLLVMModule(P);
186      PassManager Passes;
187      Passes.add(P);
188      Passes.run(*M);
189    }
190  }
191}
192
193INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
194INITIALIZE_PASS_DEPENDENCY(DominatorTree)
195INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)
196