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 10 using namespace llvm; 11 12 namespace 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 193 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false) 194 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 195 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false) 196
