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) 205
