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/IR/Dominators.h" 11 #include "llvm/Analysis/PostDominators.h" 12 #include "llvm/AsmParser/Parser.h" 13 #include "llvm/IR/Instructions.h" 14 #include "llvm/IR/LLVMContext.h" 15 #include "llvm/IR/Module.h" 16 #include "llvm/PassManager.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "gtest/gtest.h" 19 20 using namespace llvm; 21 22 namespace llvm { 23 void initializeDPassPass(PassRegistry&); 24 25 namespace { 26 struct DPass : public FunctionPass { 27 static char ID; 28 virtual bool runOnFunction(Function &F) { 29 DominatorTree *DT = 30 &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 31 PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>(); 32 Function::iterator FI = F.begin(); 33 34 BasicBlock *BB0 = FI++; 35 BasicBlock::iterator BBI = BB0->begin(); 36 Instruction *Y1 = BBI++; 37 Instruction *Y2 = BBI++; 38 Instruction *Y3 = BBI++; 39 40 BasicBlock *BB1 = FI++; 41 BBI = BB1->begin(); 42 Instruction *Y4 = BBI++; 43 44 BasicBlock *BB2 = FI++; 45 BBI = BB2->begin(); 46 Instruction *Y5 = BBI++; 47 48 BasicBlock *BB3 = FI++; 49 BBI = BB3->begin(); 50 Instruction *Y6 = BBI++; 51 Instruction *Y7 = BBI++; 52 53 BasicBlock *BB4 = FI++; 54 BBI = BB4->begin(); 55 Instruction *Y8 = BBI++; 56 Instruction *Y9 = BBI++; 57 58 // Reachability 59 EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 60 EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 61 EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 62 EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 63 EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 64 65 // BB dominance 66 EXPECT_TRUE(DT->dominates(BB0, BB0)); 67 EXPECT_TRUE(DT->dominates(BB0, BB1)); 68 EXPECT_TRUE(DT->dominates(BB0, BB2)); 69 EXPECT_TRUE(DT->dominates(BB0, BB3)); 70 EXPECT_TRUE(DT->dominates(BB0, BB4)); 71 72 EXPECT_FALSE(DT->dominates(BB1, BB0)); 73 EXPECT_TRUE(DT->dominates(BB1, BB1)); 74 EXPECT_FALSE(DT->dominates(BB1, BB2)); 75 EXPECT_TRUE(DT->dominates(BB1, BB3)); 76 EXPECT_FALSE(DT->dominates(BB1, BB4)); 77 78 EXPECT_FALSE(DT->dominates(BB2, BB0)); 79 EXPECT_FALSE(DT->dominates(BB2, BB1)); 80 EXPECT_TRUE(DT->dominates(BB2, BB2)); 81 EXPECT_TRUE(DT->dominates(BB2, BB3)); 82 EXPECT_FALSE(DT->dominates(BB2, BB4)); 83 84 EXPECT_FALSE(DT->dominates(BB3, BB0)); 85 EXPECT_FALSE(DT->dominates(BB3, BB1)); 86 EXPECT_FALSE(DT->dominates(BB3, BB2)); 87 EXPECT_TRUE(DT->dominates(BB3, BB3)); 88 EXPECT_FALSE(DT->dominates(BB3, BB4)); 89 90 // BB proper dominance 91 EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 92 EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 93 EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 94 EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 95 96 EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 97 EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 98 EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 99 EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 100 101 EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 102 EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 103 EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 104 EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 105 106 EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 107 EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 108 EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 109 EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 110 111 // Instruction dominance in the same reachable BB 112 EXPECT_FALSE(DT->dominates(Y1, Y1)); 113 EXPECT_TRUE(DT->dominates(Y1, Y2)); 114 EXPECT_FALSE(DT->dominates(Y2, Y1)); 115 EXPECT_FALSE(DT->dominates(Y2, Y2)); 116 117 // Instruction dominance in the same unreachable BB 118 EXPECT_TRUE(DT->dominates(Y6, Y6)); 119 EXPECT_TRUE(DT->dominates(Y6, Y7)); 120 EXPECT_TRUE(DT->dominates(Y7, Y6)); 121 EXPECT_TRUE(DT->dominates(Y7, Y7)); 122 123 // Invoke 124 EXPECT_TRUE(DT->dominates(Y3, Y4)); 125 EXPECT_FALSE(DT->dominates(Y3, Y5)); 126 127 // Phi 128 EXPECT_TRUE(DT->dominates(Y2, Y9)); 129 EXPECT_FALSE(DT->dominates(Y3, Y9)); 130 EXPECT_FALSE(DT->dominates(Y8, Y9)); 131 132 // Anything dominates unreachable 133 EXPECT_TRUE(DT->dominates(Y1, Y6)); 134 EXPECT_TRUE(DT->dominates(Y3, Y6)); 135 136 // Unreachable doesn't dominate reachable 137 EXPECT_FALSE(DT->dominates(Y6, Y1)); 138 139 // Instruction, BB dominance 140 EXPECT_FALSE(DT->dominates(Y1, BB0)); 141 EXPECT_TRUE(DT->dominates(Y1, BB1)); 142 EXPECT_TRUE(DT->dominates(Y1, BB2)); 143 EXPECT_TRUE(DT->dominates(Y1, BB3)); 144 EXPECT_TRUE(DT->dominates(Y1, BB4)); 145 146 EXPECT_FALSE(DT->dominates(Y3, BB0)); 147 EXPECT_TRUE(DT->dominates(Y3, BB1)); 148 EXPECT_FALSE(DT->dominates(Y3, BB2)); 149 EXPECT_TRUE(DT->dominates(Y3, BB3)); 150 EXPECT_FALSE(DT->dominates(Y3, BB4)); 151 152 EXPECT_TRUE(DT->dominates(Y6, BB3)); 153 154 // Post dominance. 155 EXPECT_TRUE(PDT->dominates(BB0, BB0)); 156 EXPECT_FALSE(PDT->dominates(BB1, BB0)); 157 EXPECT_FALSE(PDT->dominates(BB2, BB0)); 158 EXPECT_FALSE(PDT->dominates(BB3, BB0)); 159 EXPECT_TRUE(PDT->dominates(BB4, BB1)); 160 161 // Dominance descendants. 162 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 163 164 DT->getDescendants(BB0, DominatedBBs); 165 PDT->getDescendants(BB0, PostDominatedBBs); 166 EXPECT_EQ(DominatedBBs.size(), 4UL); 167 EXPECT_EQ(PostDominatedBBs.size(), 1UL); 168 169 // BB3 is unreachable. It should have no dominators nor postdominators. 170 DominatedBBs.clear(); 171 PostDominatedBBs.clear(); 172 DT->getDescendants(BB3, DominatedBBs); 173 DT->getDescendants(BB3, PostDominatedBBs); 174 EXPECT_EQ(DominatedBBs.size(), 0UL); 175 EXPECT_EQ(PostDominatedBBs.size(), 0UL); 176 177 return false; 178 } 179 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 180 AU.addRequired<DominatorTreeWrapperPass>(); 181 AU.addRequired<PostDominatorTree>(); 182 } 183 DPass() : FunctionPass(ID) { 184 initializeDPassPass(*PassRegistry::getPassRegistry()); 185 } 186 }; 187 char DPass::ID = 0; 188 189 190 Module* makeLLVMModule(DPass *P) { 191 const char *ModuleStrig = 192 "declare i32 @g()\n" \ 193 "define void @f(i32 %x) {\n" \ 194 "bb0:\n" \ 195 " %y1 = add i32 %x, 1\n" \ 196 " %y2 = add i32 %x, 1\n" \ 197 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" \ 198 "bb1:\n" \ 199 " %y4 = add i32 %x, 1\n" \ 200 " br label %bb4\n" \ 201 "bb2:\n" \ 202 " %y5 = landingpad i32 personality i32 ()* @g\n" \ 203 " cleanup\n" \ 204 " br label %bb4\n" \ 205 "bb3:\n" \ 206 " %y6 = add i32 %x, 1\n" \ 207 " %y7 = add i32 %x, 1\n" \ 208 " ret void\n" \ 209 "bb4:\n" \ 210 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 211 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 212 " ret void\n" \ 213 "}\n"; 214 LLVMContext &C = getGlobalContext(); 215 SMDiagnostic Err; 216 return ParseAssemblyString(ModuleStrig, nullptr, Err, C); 217 } 218 219 TEST(DominatorTree, Unreachable) { 220 DPass *P = new DPass(); 221 std::unique_ptr<Module> M(makeLLVMModule(P)); 222 PassManager Passes; 223 Passes.add(P); 224 Passes.run(*M); 225 } 226 } 227 } 228 229 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false) 230 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 231 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 232 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false) 233
