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