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