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/PostDominators.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Constants.h" 13 #include "llvm/IR/Dominators.h" 14 #include "llvm/IR/Instructions.h" 15 #include "llvm/IR/LLVMContext.h" 16 #include "llvm/IR/Module.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "CFGBuilder.h" 19 #include "gtest/gtest.h" 20 21 using namespace llvm; 22 23 struct PostDomTree : PostDomTreeBase<BasicBlock> { 24 PostDomTree(Function &F) { recalculate(F); } 25 }; 26 27 /// Build the dominator tree for the function and run the Test. 28 static void runWithDomTree( 29 Module &M, StringRef FuncName, 30 function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) { 31 auto *F = M.getFunction(FuncName); 32 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 33 // Compute the dominator tree for the function. 34 DominatorTree DT(*F); 35 PostDomTree PDT(*F); 36 Test(*F, &DT, &PDT); 37 } 38 39 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 40 StringRef ModuleStr) { 41 SMDiagnostic Err; 42 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); 43 assert(M && "Bad assembly?"); 44 return M; 45 } 46 47 TEST(DominatorTree, Unreachable) { 48 StringRef ModuleString = 49 "declare i32 @g()\n" 50 "define void @f(i32 %x) personality i32 ()* @g {\n" 51 "bb0:\n" 52 " %y1 = add i32 %x, 1\n" 53 " %y2 = add i32 %x, 1\n" 54 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" 55 "bb1:\n" 56 " %y4 = add i32 %x, 1\n" 57 " br label %bb4\n" 58 "bb2:\n" 59 " %y5 = landingpad i32\n" 60 " cleanup\n" 61 " br label %bb4\n" 62 "bb3:\n" 63 " %y6 = add i32 %x, 1\n" 64 " %y7 = add i32 %x, 1\n" 65 " ret void\n" 66 "bb4:\n" 67 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 68 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 69 " ret void\n" 70 "}\n"; 71 72 // Parse the module. 73 LLVMContext Context; 74 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 75 76 runWithDomTree( 77 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 78 Function::iterator FI = F.begin(); 79 80 BasicBlock *BB0 = &*FI++; 81 BasicBlock::iterator BBI = BB0->begin(); 82 Instruction *Y1 = &*BBI++; 83 Instruction *Y2 = &*BBI++; 84 Instruction *Y3 = &*BBI++; 85 86 BasicBlock *BB1 = &*FI++; 87 BBI = BB1->begin(); 88 Instruction *Y4 = &*BBI++; 89 90 BasicBlock *BB2 = &*FI++; 91 BBI = BB2->begin(); 92 Instruction *Y5 = &*BBI++; 93 94 BasicBlock *BB3 = &*FI++; 95 BBI = BB3->begin(); 96 Instruction *Y6 = &*BBI++; 97 Instruction *Y7 = &*BBI++; 98 99 BasicBlock *BB4 = &*FI++; 100 BBI = BB4->begin(); 101 Instruction *Y8 = &*BBI++; 102 Instruction *Y9 = &*BBI++; 103 104 // Reachability 105 EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 106 EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 107 EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 108 EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 109 EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 110 111 // BB dominance 112 EXPECT_TRUE(DT->dominates(BB0, BB0)); 113 EXPECT_TRUE(DT->dominates(BB0, BB1)); 114 EXPECT_TRUE(DT->dominates(BB0, BB2)); 115 EXPECT_TRUE(DT->dominates(BB0, BB3)); 116 EXPECT_TRUE(DT->dominates(BB0, BB4)); 117 118 EXPECT_FALSE(DT->dominates(BB1, BB0)); 119 EXPECT_TRUE(DT->dominates(BB1, BB1)); 120 EXPECT_FALSE(DT->dominates(BB1, BB2)); 121 EXPECT_TRUE(DT->dominates(BB1, BB3)); 122 EXPECT_FALSE(DT->dominates(BB1, BB4)); 123 124 EXPECT_FALSE(DT->dominates(BB2, BB0)); 125 EXPECT_FALSE(DT->dominates(BB2, BB1)); 126 EXPECT_TRUE(DT->dominates(BB2, BB2)); 127 EXPECT_TRUE(DT->dominates(BB2, BB3)); 128 EXPECT_FALSE(DT->dominates(BB2, BB4)); 129 130 EXPECT_FALSE(DT->dominates(BB3, BB0)); 131 EXPECT_FALSE(DT->dominates(BB3, BB1)); 132 EXPECT_FALSE(DT->dominates(BB3, BB2)); 133 EXPECT_TRUE(DT->dominates(BB3, BB3)); 134 EXPECT_FALSE(DT->dominates(BB3, BB4)); 135 136 // BB proper dominance 137 EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 138 EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 139 EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 140 EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 141 142 EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 143 EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 144 EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 145 EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 146 147 EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 148 EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 149 EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 150 EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 151 152 EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 153 EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 154 EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 155 EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 156 157 // Instruction dominance in the same reachable BB 158 EXPECT_FALSE(DT->dominates(Y1, Y1)); 159 EXPECT_TRUE(DT->dominates(Y1, Y2)); 160 EXPECT_FALSE(DT->dominates(Y2, Y1)); 161 EXPECT_FALSE(DT->dominates(Y2, Y2)); 162 163 // Instruction dominance in the same unreachable BB 164 EXPECT_TRUE(DT->dominates(Y6, Y6)); 165 EXPECT_TRUE(DT->dominates(Y6, Y7)); 166 EXPECT_TRUE(DT->dominates(Y7, Y6)); 167 EXPECT_TRUE(DT->dominates(Y7, Y7)); 168 169 // Invoke 170 EXPECT_TRUE(DT->dominates(Y3, Y4)); 171 EXPECT_FALSE(DT->dominates(Y3, Y5)); 172 173 // Phi 174 EXPECT_TRUE(DT->dominates(Y2, Y9)); 175 EXPECT_FALSE(DT->dominates(Y3, Y9)); 176 EXPECT_FALSE(DT->dominates(Y8, Y9)); 177 178 // Anything dominates unreachable 179 EXPECT_TRUE(DT->dominates(Y1, Y6)); 180 EXPECT_TRUE(DT->dominates(Y3, Y6)); 181 182 // Unreachable doesn't dominate reachable 183 EXPECT_FALSE(DT->dominates(Y6, Y1)); 184 185 // Instruction, BB dominance 186 EXPECT_FALSE(DT->dominates(Y1, BB0)); 187 EXPECT_TRUE(DT->dominates(Y1, BB1)); 188 EXPECT_TRUE(DT->dominates(Y1, BB2)); 189 EXPECT_TRUE(DT->dominates(Y1, BB3)); 190 EXPECT_TRUE(DT->dominates(Y1, BB4)); 191 192 EXPECT_FALSE(DT->dominates(Y3, BB0)); 193 EXPECT_TRUE(DT->dominates(Y3, BB1)); 194 EXPECT_FALSE(DT->dominates(Y3, BB2)); 195 EXPECT_TRUE(DT->dominates(Y3, BB3)); 196 EXPECT_FALSE(DT->dominates(Y3, BB4)); 197 198 EXPECT_TRUE(DT->dominates(Y6, BB3)); 199 200 // Post dominance. 201 EXPECT_TRUE(PDT->dominates(BB0, BB0)); 202 EXPECT_FALSE(PDT->dominates(BB1, BB0)); 203 EXPECT_FALSE(PDT->dominates(BB2, BB0)); 204 EXPECT_FALSE(PDT->dominates(BB3, BB0)); 205 EXPECT_TRUE(PDT->dominates(BB4, BB1)); 206 207 // Dominance descendants. 208 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 209 210 DT->getDescendants(BB0, DominatedBBs); 211 PDT->getDescendants(BB0, PostDominatedBBs); 212 EXPECT_EQ(DominatedBBs.size(), 4UL); 213 EXPECT_EQ(PostDominatedBBs.size(), 1UL); 214 215 // BB3 is unreachable. It should have no dominators nor postdominators. 216 DominatedBBs.clear(); 217 PostDominatedBBs.clear(); 218 DT->getDescendants(BB3, DominatedBBs); 219 DT->getDescendants(BB3, PostDominatedBBs); 220 EXPECT_EQ(DominatedBBs.size(), 0UL); 221 EXPECT_EQ(PostDominatedBBs.size(), 0UL); 222 223 // Check DFS Numbers before 224 DT->updateDFSNumbers(); 225 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 226 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); 227 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 228 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); 229 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); 230 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); 231 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); 232 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); 233 234 // Check levels before 235 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 236 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 237 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 238 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 239 240 // Reattach block 3 to block 1 and recalculate 241 BB1->getTerminator()->eraseFromParent(); 242 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); 243 DT->recalculate(F); 244 245 // Check DFS Numbers after 246 DT->updateDFSNumbers(); 247 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 248 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); 249 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 250 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); 251 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); 252 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); 253 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); 254 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); 255 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); 256 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); 257 258 // Check levels after 259 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 260 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 261 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 262 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); 263 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 264 265 // Change root node 266 DT->verifyDomTree(); 267 BasicBlock *NewEntry = 268 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); 269 BranchInst::Create(BB0, NewEntry); 270 EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); 271 EXPECT_TRUE(&F.getEntryBlock() == NewEntry); 272 DT->setNewRoot(NewEntry); 273 DT->verifyDomTree(); 274 }); 275 } 276 277 TEST(DominatorTree, NonUniqueEdges) { 278 StringRef ModuleString = 279 "define i32 @f(i32 %i, i32 *%p) {\n" 280 "bb0:\n" 281 " store i32 %i, i32 *%p\n" 282 " switch i32 %i, label %bb2 [\n" 283 " i32 0, label %bb1\n" 284 " i32 1, label %bb1\n" 285 " ]\n" 286 " bb1:\n" 287 " ret i32 1\n" 288 " bb2:\n" 289 " ret i32 4\n" 290 "}\n"; 291 292 // Parse the module. 293 LLVMContext Context; 294 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 295 296 runWithDomTree( 297 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 298 Function::iterator FI = F.begin(); 299 300 BasicBlock *BB0 = &*FI++; 301 BasicBlock *BB1 = &*FI++; 302 BasicBlock *BB2 = &*FI++; 303 304 const TerminatorInst *TI = BB0->getTerminator(); 305 assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); 306 307 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); 308 assert(Edge_BB0_BB2.getEnd() == BB2 && 309 "Default label is the 1st successor"); 310 311 BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1)); 312 assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor"); 313 314 BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2)); 315 assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor"); 316 317 EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); 318 EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); 319 320 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); 321 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); 322 323 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); 324 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); 325 }); 326 } 327 328 namespace { 329 const auto Insert = CFGBuilder::ActionKind::Insert; 330 331 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { 332 return std::tie(A.Action, A.Edge.From, A.Edge.To) < 333 std::tie(B.Action, B.Edge.From, B.Edge.To); 334 }; 335 } // namespace 336 337 TEST(DominatorTree, InsertReachable) { 338 CFGHolder Holder; 339 std::vector<CFGBuilder::Arc> Arcs = { 340 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 341 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 342 343 std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}}, 344 {Insert, {"10", "9"}}, 345 {Insert, {"7", "6"}}, 346 {Insert, {"7", "5"}}}; 347 CFGBuilder B(Holder.F, Arcs, Updates); 348 DominatorTree DT(*Holder.F); 349 EXPECT_TRUE(DT.verify()); 350 PostDomTree PDT(*Holder.F); 351 EXPECT_TRUE(PDT.verify()); 352 353 Optional<CFGBuilder::Update> LastUpdate; 354 while ((LastUpdate = B.applyUpdate())) { 355 EXPECT_EQ(LastUpdate->Action, Insert); 356 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 357 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 358 DT.insertEdge(From, To); 359 EXPECT_TRUE(DT.verify()); 360 PDT.insertEdge(From, To); 361 EXPECT_TRUE(PDT.verify()); 362 } 363 } 364 365 TEST(DominatorTree, InsertUnreachable) { 366 CFGHolder Holder; 367 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, 368 {"5", "6"}, {"5", "7"}, {"3", "8"}, 369 {"9", "10"}, {"11", "12"}}; 370 371 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 372 {Insert, {"8", "9"}}, 373 {Insert, {"10", "12"}}, 374 {Insert, {"10", "11"}}}; 375 CFGBuilder B(Holder.F, Arcs, Updates); 376 DominatorTree DT(*Holder.F); 377 EXPECT_TRUE(DT.verify()); 378 PostDomTree PDT(*Holder.F); 379 EXPECT_TRUE(PDT.verify()); 380 381 Optional<CFGBuilder::Update> LastUpdate; 382 while ((LastUpdate = B.applyUpdate())) { 383 EXPECT_EQ(LastUpdate->Action, Insert); 384 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 385 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 386 DT.insertEdge(From, To); 387 EXPECT_TRUE(DT.verify()); 388 PDT.insertEdge(From, To); 389 EXPECT_TRUE(PDT.verify()); 390 } 391 } 392 393 TEST(DominatorTree, InsertMixed) { 394 CFGHolder Holder; 395 std::vector<CFGBuilder::Arc> Arcs = { 396 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 397 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 398 399 std::vector<CFGBuilder::Update> Updates = { 400 {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, 401 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, 402 {Insert, {"7", "5"}}}; 403 CFGBuilder B(Holder.F, Arcs, Updates); 404 DominatorTree DT(*Holder.F); 405 EXPECT_TRUE(DT.verify()); 406 PostDomTree PDT(*Holder.F); 407 EXPECT_TRUE(PDT.verify()); 408 409 Optional<CFGBuilder::Update> LastUpdate; 410 while ((LastUpdate = B.applyUpdate())) { 411 EXPECT_EQ(LastUpdate->Action, Insert); 412 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 413 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 414 DT.insertEdge(From, To); 415 EXPECT_TRUE(DT.verify()); 416 PDT.insertEdge(From, To); 417 EXPECT_TRUE(PDT.verify()); 418 } 419 } 420 421 TEST(DominatorTree, InsertPermut) { 422 std::vector<CFGBuilder::Arc> Arcs = { 423 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 424 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 425 426 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 427 {Insert, {"2", "5"}}, 428 {Insert, {"10", "9"}}, 429 {Insert, {"12", "10"}}}; 430 431 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { 432 CFGHolder Holder; 433 CFGBuilder B(Holder.F, Arcs, Updates); 434 DominatorTree DT(*Holder.F); 435 EXPECT_TRUE(DT.verify()); 436 PostDomTree PDT(*Holder.F); 437 EXPECT_TRUE(PDT.verify()); 438 439 Optional<CFGBuilder::Update> LastUpdate; 440 while ((LastUpdate = B.applyUpdate())) { 441 EXPECT_EQ(LastUpdate->Action, Insert); 442 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 443 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 444 DT.insertEdge(From, To); 445 EXPECT_TRUE(DT.verify()); 446 PDT.insertEdge(From, To); 447 EXPECT_TRUE(PDT.verify()); 448 } 449 } 450 } 451