1 //===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include <random> 10 #include "llvm/Analysis/PostDominators.h" 11 #include "llvm/Analysis/IteratedDominanceFrontier.h" 12 #include "llvm/AsmParser/Parser.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/Dominators.h" 15 #include "llvm/IR/Instructions.h" 16 #include "llvm/IR/LLVMContext.h" 17 #include "llvm/IR/Module.h" 18 #include "llvm/Support/SourceMgr.h" 19 #include "CFGBuilder.h" 20 #include "gtest/gtest.h" 21 22 using namespace llvm; 23 24 25 /// Build the dominator tree for the function and run the Test. 26 static void runWithDomTree( 27 Module &M, StringRef FuncName, 28 function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)> 29 Test) { 30 auto *F = M.getFunction(FuncName); 31 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 32 // Compute the dominator tree for the function. 33 DominatorTree DT(*F); 34 PostDominatorTree PDT(*F); 35 Test(*F, &DT, &PDT); 36 } 37 38 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 39 StringRef ModuleStr) { 40 SMDiagnostic Err; 41 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); 42 assert(M && "Bad assembly?"); 43 return M; 44 } 45 46 TEST(DominatorTree, PHIs) { 47 StringRef ModuleString = R"( 48 define void @f() { 49 bb1: 50 br label %bb1 51 bb2: 52 %a = phi i32 [0, %bb1], [1, %bb2] 53 %b = phi i32 [2, %bb1], [%a, %bb2] 54 br label %bb2 55 }; 56 )"; 57 58 // Parse the module. 59 LLVMContext Context; 60 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 61 62 runWithDomTree(*M, "f", 63 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 64 auto FI = F.begin(); 65 ++FI; 66 BasicBlock *BB2 = &*FI; 67 auto BI = BB2->begin(); 68 Instruction *PhiA = &*BI++; 69 Instruction *PhiB = &*BI; 70 71 // Phis are thought to execute "instantly, together". 72 EXPECT_TRUE(DT->dominates(PhiA, PhiB)); 73 EXPECT_TRUE(DT->dominates(PhiB, PhiA)); 74 }); 75 } 76 77 TEST(DominatorTree, Unreachable) { 78 StringRef ModuleString = 79 "declare i32 @g()\n" 80 "define void @f(i32 %x) personality i32 ()* @g {\n" 81 "bb0:\n" 82 " %y1 = add i32 %x, 1\n" 83 " %y2 = add i32 %x, 1\n" 84 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" 85 "bb1:\n" 86 " %y4 = add i32 %x, 1\n" 87 " br label %bb4\n" 88 "bb2:\n" 89 " %y5 = landingpad i32\n" 90 " cleanup\n" 91 " br label %bb4\n" 92 "bb3:\n" 93 " %y6 = add i32 %x, 1\n" 94 " %y7 = add i32 %x, 1\n" 95 " ret void\n" 96 "bb4:\n" 97 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 98 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 99 " ret void\n" 100 "}\n"; 101 102 // Parse the module. 103 LLVMContext Context; 104 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 105 106 runWithDomTree( 107 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 108 Function::iterator FI = F.begin(); 109 110 BasicBlock *BB0 = &*FI++; 111 BasicBlock::iterator BBI = BB0->begin(); 112 Instruction *Y1 = &*BBI++; 113 Instruction *Y2 = &*BBI++; 114 Instruction *Y3 = &*BBI++; 115 116 BasicBlock *BB1 = &*FI++; 117 BBI = BB1->begin(); 118 Instruction *Y4 = &*BBI++; 119 120 BasicBlock *BB2 = &*FI++; 121 BBI = BB2->begin(); 122 Instruction *Y5 = &*BBI++; 123 124 BasicBlock *BB3 = &*FI++; 125 BBI = BB3->begin(); 126 Instruction *Y6 = &*BBI++; 127 Instruction *Y7 = &*BBI++; 128 129 BasicBlock *BB4 = &*FI++; 130 BBI = BB4->begin(); 131 Instruction *Y8 = &*BBI++; 132 Instruction *Y9 = &*BBI++; 133 134 // Reachability 135 EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 136 EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 137 EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 138 EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 139 EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 140 141 // BB dominance 142 EXPECT_TRUE(DT->dominates(BB0, BB0)); 143 EXPECT_TRUE(DT->dominates(BB0, BB1)); 144 EXPECT_TRUE(DT->dominates(BB0, BB2)); 145 EXPECT_TRUE(DT->dominates(BB0, BB3)); 146 EXPECT_TRUE(DT->dominates(BB0, BB4)); 147 148 EXPECT_FALSE(DT->dominates(BB1, BB0)); 149 EXPECT_TRUE(DT->dominates(BB1, BB1)); 150 EXPECT_FALSE(DT->dominates(BB1, BB2)); 151 EXPECT_TRUE(DT->dominates(BB1, BB3)); 152 EXPECT_FALSE(DT->dominates(BB1, BB4)); 153 154 EXPECT_FALSE(DT->dominates(BB2, BB0)); 155 EXPECT_FALSE(DT->dominates(BB2, BB1)); 156 EXPECT_TRUE(DT->dominates(BB2, BB2)); 157 EXPECT_TRUE(DT->dominates(BB2, BB3)); 158 EXPECT_FALSE(DT->dominates(BB2, BB4)); 159 160 EXPECT_FALSE(DT->dominates(BB3, BB0)); 161 EXPECT_FALSE(DT->dominates(BB3, BB1)); 162 EXPECT_FALSE(DT->dominates(BB3, BB2)); 163 EXPECT_TRUE(DT->dominates(BB3, BB3)); 164 EXPECT_FALSE(DT->dominates(BB3, BB4)); 165 166 // BB proper dominance 167 EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 168 EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 169 EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 170 EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 171 172 EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 173 EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 174 EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 175 EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 176 177 EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 178 EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 179 EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 180 EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 181 182 EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 183 EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 184 EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 185 EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 186 187 // Instruction dominance in the same reachable BB 188 EXPECT_FALSE(DT->dominates(Y1, Y1)); 189 EXPECT_TRUE(DT->dominates(Y1, Y2)); 190 EXPECT_FALSE(DT->dominates(Y2, Y1)); 191 EXPECT_FALSE(DT->dominates(Y2, Y2)); 192 193 // Instruction dominance in the same unreachable BB 194 EXPECT_TRUE(DT->dominates(Y6, Y6)); 195 EXPECT_TRUE(DT->dominates(Y6, Y7)); 196 EXPECT_TRUE(DT->dominates(Y7, Y6)); 197 EXPECT_TRUE(DT->dominates(Y7, Y7)); 198 199 // Invoke 200 EXPECT_TRUE(DT->dominates(Y3, Y4)); 201 EXPECT_FALSE(DT->dominates(Y3, Y5)); 202 203 // Phi 204 EXPECT_TRUE(DT->dominates(Y2, Y9)); 205 EXPECT_FALSE(DT->dominates(Y3, Y9)); 206 EXPECT_FALSE(DT->dominates(Y8, Y9)); 207 208 // Anything dominates unreachable 209 EXPECT_TRUE(DT->dominates(Y1, Y6)); 210 EXPECT_TRUE(DT->dominates(Y3, Y6)); 211 212 // Unreachable doesn't dominate reachable 213 EXPECT_FALSE(DT->dominates(Y6, Y1)); 214 215 // Instruction, BB dominance 216 EXPECT_FALSE(DT->dominates(Y1, BB0)); 217 EXPECT_TRUE(DT->dominates(Y1, BB1)); 218 EXPECT_TRUE(DT->dominates(Y1, BB2)); 219 EXPECT_TRUE(DT->dominates(Y1, BB3)); 220 EXPECT_TRUE(DT->dominates(Y1, BB4)); 221 222 EXPECT_FALSE(DT->dominates(Y3, BB0)); 223 EXPECT_TRUE(DT->dominates(Y3, BB1)); 224 EXPECT_FALSE(DT->dominates(Y3, BB2)); 225 EXPECT_TRUE(DT->dominates(Y3, BB3)); 226 EXPECT_FALSE(DT->dominates(Y3, BB4)); 227 228 EXPECT_TRUE(DT->dominates(Y6, BB3)); 229 230 // Post dominance. 231 EXPECT_TRUE(PDT->dominates(BB0, BB0)); 232 EXPECT_FALSE(PDT->dominates(BB1, BB0)); 233 EXPECT_FALSE(PDT->dominates(BB2, BB0)); 234 EXPECT_FALSE(PDT->dominates(BB3, BB0)); 235 EXPECT_TRUE(PDT->dominates(BB4, BB1)); 236 237 // Dominance descendants. 238 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 239 240 DT->getDescendants(BB0, DominatedBBs); 241 PDT->getDescendants(BB0, PostDominatedBBs); 242 EXPECT_EQ(DominatedBBs.size(), 4UL); 243 EXPECT_EQ(PostDominatedBBs.size(), 1UL); 244 245 // BB3 is unreachable. It should have no dominators nor postdominators. 246 DominatedBBs.clear(); 247 PostDominatedBBs.clear(); 248 DT->getDescendants(BB3, DominatedBBs); 249 DT->getDescendants(BB3, PostDominatedBBs); 250 EXPECT_EQ(DominatedBBs.size(), 0UL); 251 EXPECT_EQ(PostDominatedBBs.size(), 0UL); 252 253 // Check DFS Numbers before 254 DT->updateDFSNumbers(); 255 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 256 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); 257 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 258 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); 259 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); 260 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); 261 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); 262 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); 263 264 // Check levels before 265 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 266 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 267 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 268 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 269 270 // Reattach block 3 to block 1 and recalculate 271 BB1->getTerminator()->eraseFromParent(); 272 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); 273 DT->recalculate(F); 274 275 // Check DFS Numbers after 276 DT->updateDFSNumbers(); 277 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 278 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); 279 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 280 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); 281 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); 282 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); 283 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); 284 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); 285 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); 286 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); 287 288 // Check levels after 289 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 290 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 291 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 292 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); 293 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 294 295 // Change root node 296 EXPECT_TRUE(DT->verify()); 297 BasicBlock *NewEntry = 298 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); 299 BranchInst::Create(BB0, NewEntry); 300 EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); 301 EXPECT_TRUE(&F.getEntryBlock() == NewEntry); 302 DT->setNewRoot(NewEntry); 303 EXPECT_TRUE(DT->verify()); 304 }); 305 } 306 307 TEST(DominatorTree, NonUniqueEdges) { 308 StringRef ModuleString = 309 "define i32 @f(i32 %i, i32 *%p) {\n" 310 "bb0:\n" 311 " store i32 %i, i32 *%p\n" 312 " switch i32 %i, label %bb2 [\n" 313 " i32 0, label %bb1\n" 314 " i32 1, label %bb1\n" 315 " ]\n" 316 " bb1:\n" 317 " ret i32 1\n" 318 " bb2:\n" 319 " ret i32 4\n" 320 "}\n"; 321 322 // Parse the module. 323 LLVMContext Context; 324 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 325 326 runWithDomTree( 327 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 328 Function::iterator FI = F.begin(); 329 330 BasicBlock *BB0 = &*FI++; 331 BasicBlock *BB1 = &*FI++; 332 BasicBlock *BB2 = &*FI++; 333 334 const Instruction *TI = BB0->getTerminator(); 335 assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); 336 337 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); 338 assert(Edge_BB0_BB2.getEnd() == BB2 && 339 "Default label is the 1st successor"); 340 341 BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1)); 342 assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor"); 343 344 BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2)); 345 assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor"); 346 347 EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); 348 EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); 349 350 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); 351 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); 352 353 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); 354 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); 355 }); 356 } 357 358 // Verify that the PDT is correctly updated in case an edge removal results 359 // in a new unreachable CFG node. Also make sure that the updated PDT is the 360 // same as a freshly recalculated one. 361 // 362 // For the following input code and initial PDT: 363 // 364 // CFG PDT 365 // 366 // A Exit 367 // | | 368 // _B D 369 // / | \ | 370 // ^ v \ B 371 // \ / D / \ 372 // C \ C A 373 // v 374 // Exit 375 // 376 // we verify that CFG' and PDT-updated is obtained after removal of edge C -> B. 377 // 378 // CFG' PDT-updated 379 // 380 // A Exit 381 // | / | \ 382 // B C B D 383 // | \ | 384 // v \ A 385 // / D 386 // C \ 387 // | \ 388 // unreachable Exit 389 // 390 // Both the blocks that end with ret and with unreachable become trivial 391 // PostDominatorTree roots, as they have no successors. 392 // 393 TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { 394 StringRef ModuleString = 395 "define void @f() {\n" 396 "A:\n" 397 " br label %B\n" 398 "B:\n" 399 " br i1 undef, label %D, label %C\n" 400 "C:\n" 401 " br label %B\n" 402 "D:\n" 403 " ret void\n" 404 "}\n"; 405 406 // Parse the module. 407 LLVMContext Context; 408 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 409 410 runWithDomTree( 411 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 412 Function::iterator FI = F.begin(); 413 414 FI++; 415 BasicBlock *B = &*FI++; 416 BasicBlock *C = &*FI++; 417 BasicBlock *D = &*FI++; 418 419 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 420 EXPECT_TRUE(DT->verify()); 421 EXPECT_TRUE(PDT->verify()); 422 423 C->getTerminator()->eraseFromParent(); 424 new UnreachableInst(C->getContext(), C); 425 426 DT->deleteEdge(C, B); 427 PDT->deleteEdge(C, B); 428 429 EXPECT_TRUE(DT->verify()); 430 EXPECT_TRUE(PDT->verify()); 431 432 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 433 EXPECT_NE(PDT->getNode(C), nullptr); 434 435 DominatorTree NDT(F); 436 EXPECT_EQ(DT->compare(NDT), 0); 437 438 PostDominatorTree NPDT(F); 439 EXPECT_EQ(PDT->compare(NPDT), 0); 440 }); 441 } 442 443 // Verify that the PDT is correctly updated in case an edge removal results 444 // in an infinite loop. Also make sure that the updated PDT is the 445 // same as a freshly recalculated one. 446 // 447 // Test case: 448 // 449 // CFG PDT 450 // 451 // A Exit 452 // | | 453 // _B D 454 // / | \ | 455 // ^ v \ B 456 // \ / D / \ 457 // C \ C A 458 // / \ v 459 // ^ v Exit 460 // \_/ 461 // 462 // After deleting the edge C->B, C is part of an infinite reverse-unreachable 463 // loop: 464 // 465 // CFG' PDT' 466 // 467 // A Exit 468 // | / | \ 469 // B C B D 470 // | \ | 471 // v \ A 472 // / D 473 // C \ 474 // / \ v 475 // ^ v Exit 476 // \_/ 477 // 478 // As C now becomes reverse-unreachable, it forms a new non-trivial root and 479 // gets connected to the virtual exit. 480 // D does not postdominate B anymore, because there are two forward paths from 481 // B to the virtual exit: 482 // - B -> C -> VirtualExit 483 // - B -> D -> VirtualExit. 484 // 485 TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { 486 StringRef ModuleString = 487 "define void @f() {\n" 488 "A:\n" 489 " br label %B\n" 490 "B:\n" 491 " br i1 undef, label %D, label %C\n" 492 "C:\n" 493 " switch i32 undef, label %C [\n" 494 " i32 0, label %B\n" 495 " ]\n" 496 "D:\n" 497 " ret void\n" 498 "}\n"; 499 500 // Parse the module. 501 LLVMContext Context; 502 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 503 504 runWithDomTree( 505 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 506 Function::iterator FI = F.begin(); 507 508 FI++; 509 BasicBlock *B = &*FI++; 510 BasicBlock *C = &*FI++; 511 BasicBlock *D = &*FI++; 512 513 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 514 EXPECT_TRUE(DT->verify()); 515 EXPECT_TRUE(PDT->verify()); 516 517 auto SwitchC = cast<SwitchInst>(C->getTerminator()); 518 SwitchC->removeCase(SwitchC->case_begin()); 519 DT->deleteEdge(C, B); 520 EXPECT_TRUE(DT->verify()); 521 PDT->deleteEdge(C, B); 522 EXPECT_TRUE(PDT->verify()); 523 524 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 525 EXPECT_NE(PDT->getNode(C), nullptr); 526 527 DominatorTree NDT(F); 528 EXPECT_EQ(DT->compare(NDT), 0); 529 530 PostDominatorTree NPDT(F); 531 EXPECT_EQ(PDT->compare(NPDT), 0); 532 }); 533 } 534 535 // Verify that the PDT is correctly updated in case an edge removal results 536 // in an infinite loop. 537 // 538 // Test case: 539 // 540 // CFG PDT 541 // 542 // A Exit 543 // | / | \ 544 // B-- C2 B D 545 // | \ / | 546 // v \ C A 547 // / D 548 // C--C2 \ 549 // / \ \ v 550 // ^ v --Exit 551 // \_/ 552 // 553 // After deleting the edge C->E, C is part of an infinite reverse-unreachable 554 // loop: 555 // 556 // CFG' PDT' 557 // 558 // A Exit 559 // | / | \ 560 // B C B D 561 // | \ | 562 // v \ A 563 // / D 564 // C \ 565 // / \ v 566 // ^ v Exit 567 // \_/ 568 // 569 // In PDT, D does not post-dominate B. After the edge C -> C2 is removed, 570 // C becomes a new nontrivial PDT root. 571 // 572 TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { 573 StringRef ModuleString = 574 "define void @f() {\n" 575 "A:\n" 576 " br label %B\n" 577 "B:\n" 578 " br i1 undef, label %D, label %C\n" 579 "C:\n" 580 " switch i32 undef, label %C [\n" 581 " i32 0, label %C2\n" 582 " ]\n" 583 "C2:\n" 584 " ret void\n" 585 "D:\n" 586 " ret void\n" 587 "}\n"; 588 589 // Parse the module. 590 LLVMContext Context; 591 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 592 593 runWithDomTree( 594 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 595 Function::iterator FI = F.begin(); 596 597 FI++; 598 BasicBlock *B = &*FI++; 599 BasicBlock *C = &*FI++; 600 BasicBlock *C2 = &*FI++; 601 BasicBlock *D = &*FI++; 602 603 EXPECT_TRUE(DT->verify()); 604 EXPECT_TRUE(PDT->verify()); 605 606 auto SwitchC = cast<SwitchInst>(C->getTerminator()); 607 SwitchC->removeCase(SwitchC->case_begin()); 608 DT->deleteEdge(C, C2); 609 PDT->deleteEdge(C, C2); 610 611 EXPECT_EQ(DT->getNode(C2), nullptr); 612 PDT->eraseNode(C2); 613 C2->eraseFromParent(); 614 615 EXPECT_TRUE(DT->verify()); 616 EXPECT_TRUE(PDT->verify()); 617 618 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 619 EXPECT_NE(PDT->getNode(C), nullptr); 620 621 DominatorTree NDT(F); 622 EXPECT_EQ(DT->compare(NDT), 0); 623 624 PostDominatorTree NPDT(F); 625 EXPECT_EQ(PDT->compare(NPDT), 0); 626 }); 627 } 628 629 // Verify that the IDF returns blocks in a deterministic way. 630 // 631 // Test case: 632 // 633 // CFG 634 // 635 // (A) 636 // / \ 637 // / \ 638 // (B) (C) 639 // |\ /| 640 // | X | 641 // |/ \| 642 // (D) (E) 643 // 644 // IDF for block B is {D, E}, and the order of blocks in this list is defined by 645 // their 1) level in dom-tree and 2) DFSIn number if the level is the same. 646 // 647 TEST(DominatorTree, IDFDeterminismTest) { 648 StringRef ModuleString = 649 "define void @f() {\n" 650 "A:\n" 651 " br i1 undef, label %B, label %C\n" 652 "B:\n" 653 " br i1 undef, label %D, label %E\n" 654 "C:\n" 655 " br i1 undef, label %D, label %E\n" 656 "D:\n" 657 " ret void\n" 658 "E:\n" 659 " ret void\n" 660 "}\n"; 661 662 // Parse the module. 663 LLVMContext Context; 664 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 665 666 runWithDomTree( 667 *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 668 Function::iterator FI = F.begin(); 669 670 BasicBlock *A = &*FI++; 671 BasicBlock *B = &*FI++; 672 BasicBlock *C = &*FI++; 673 BasicBlock *D = &*FI++; 674 BasicBlock *E = &*FI++; 675 (void)C; 676 677 DT->updateDFSNumbers(); 678 ForwardIDFCalculator IDF(*DT); 679 SmallPtrSet<BasicBlock *, 1> DefBlocks; 680 DefBlocks.insert(B); 681 IDF.setDefiningBlocks(DefBlocks); 682 683 SmallVector<BasicBlock *, 32> IDFBlocks; 684 SmallPtrSet<BasicBlock *, 32> LiveInBlocks; 685 IDF.resetLiveInBlocks(); 686 IDF.calculate(IDFBlocks); 687 688 689 EXPECT_EQ(IDFBlocks.size(), 2UL); 690 EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL); 691 EXPECT_EQ(IDFBlocks[0], D); 692 EXPECT_EQ(IDFBlocks[1], E); 693 EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() < 694 DT->getNode(IDFBlocks[1])->getDFSNumIn()); 695 }); 696 } 697 698 namespace { 699 const auto Insert = CFGBuilder::ActionKind::Insert; 700 const auto Delete = CFGBuilder::ActionKind::Delete; 701 702 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { 703 return std::tie(A.Action, A.Edge.From, A.Edge.To) < 704 std::tie(B.Action, B.Edge.From, B.Edge.To); 705 } 706 } // namespace 707 708 TEST(DominatorTree, InsertReachable) { 709 CFGHolder Holder; 710 std::vector<CFGBuilder::Arc> Arcs = { 711 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 712 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 713 714 std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}}, 715 {Insert, {"10", "9"}}, 716 {Insert, {"7", "6"}}, 717 {Insert, {"7", "5"}}}; 718 CFGBuilder B(Holder.F, Arcs, Updates); 719 DominatorTree DT(*Holder.F); 720 EXPECT_TRUE(DT.verify()); 721 PostDominatorTree PDT(*Holder.F); 722 EXPECT_TRUE(PDT.verify()); 723 724 std::optional<CFGBuilder::Update> LastUpdate; 725 while ((LastUpdate = B.applyUpdate())) { 726 EXPECT_EQ(LastUpdate->Action, Insert); 727 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 728 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 729 DT.insertEdge(From, To); 730 EXPECT_TRUE(DT.verify()); 731 PDT.insertEdge(From, To); 732 EXPECT_TRUE(PDT.verify()); 733 } 734 } 735 736 TEST(DominatorTree, InsertReachable2) { 737 CFGHolder Holder; 738 std::vector<CFGBuilder::Arc> Arcs = { 739 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 740 {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"}, 741 {"10", "9"}, {"9", "10"}}; 742 743 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}}; 744 CFGBuilder B(Holder.F, Arcs, Updates); 745 DominatorTree DT(*Holder.F); 746 EXPECT_TRUE(DT.verify()); 747 PostDominatorTree PDT(*Holder.F); 748 EXPECT_TRUE(PDT.verify()); 749 750 std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 751 EXPECT_TRUE(LastUpdate); 752 753 EXPECT_EQ(LastUpdate->Action, Insert); 754 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 755 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 756 DT.insertEdge(From, To); 757 EXPECT_TRUE(DT.verify()); 758 PDT.insertEdge(From, To); 759 EXPECT_TRUE(PDT.verify()); 760 } 761 762 TEST(DominatorTree, InsertUnreachable) { 763 CFGHolder Holder; 764 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, 765 {"5", "6"}, {"5", "7"}, {"3", "8"}, 766 {"9", "10"}, {"11", "12"}}; 767 768 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 769 {Insert, {"8", "9"}}, 770 {Insert, {"10", "12"}}, 771 {Insert, {"10", "11"}}}; 772 CFGBuilder B(Holder.F, Arcs, Updates); 773 DominatorTree DT(*Holder.F); 774 EXPECT_TRUE(DT.verify()); 775 PostDominatorTree PDT(*Holder.F); 776 EXPECT_TRUE(PDT.verify()); 777 778 std::optional<CFGBuilder::Update> LastUpdate; 779 while ((LastUpdate = B.applyUpdate())) { 780 EXPECT_EQ(LastUpdate->Action, Insert); 781 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 782 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 783 DT.insertEdge(From, To); 784 EXPECT_TRUE(DT.verify()); 785 PDT.insertEdge(From, To); 786 EXPECT_TRUE(PDT.verify()); 787 } 788 } 789 790 TEST(DominatorTree, InsertFromUnreachable) { 791 CFGHolder Holder; 792 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}}; 793 794 std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}}; 795 CFGBuilder B(Holder.F, Arcs, Updates); 796 PostDominatorTree PDT(*Holder.F); 797 EXPECT_TRUE(PDT.verify()); 798 799 std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 800 EXPECT_TRUE(LastUpdate); 801 802 EXPECT_EQ(LastUpdate->Action, Insert); 803 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 804 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 805 PDT.insertEdge(From, To); 806 EXPECT_TRUE(PDT.verify()); 807 EXPECT_EQ(PDT.root_size(), 2UL); 808 // Make sure we can use a const pointer with getNode. 809 const BasicBlock *BB5 = B.getOrAddBlock("5"); 810 EXPECT_NE(PDT.getNode(BB5), nullptr); 811 } 812 813 TEST(DominatorTree, InsertMixed) { 814 CFGHolder Holder; 815 std::vector<CFGBuilder::Arc> Arcs = { 816 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 817 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 818 819 std::vector<CFGBuilder::Update> Updates = { 820 {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, 821 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, 822 {Insert, {"7", "5"}}}; 823 CFGBuilder B(Holder.F, Arcs, Updates); 824 DominatorTree DT(*Holder.F); 825 EXPECT_TRUE(DT.verify()); 826 PostDominatorTree PDT(*Holder.F); 827 EXPECT_TRUE(PDT.verify()); 828 829 std::optional<CFGBuilder::Update> LastUpdate; 830 while ((LastUpdate = B.applyUpdate())) { 831 EXPECT_EQ(LastUpdate->Action, Insert); 832 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 833 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 834 DT.insertEdge(From, To); 835 EXPECT_TRUE(DT.verify()); 836 PDT.insertEdge(From, To); 837 EXPECT_TRUE(PDT.verify()); 838 } 839 } 840 841 TEST(DominatorTree, InsertPermut) { 842 std::vector<CFGBuilder::Arc> Arcs = { 843 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 844 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 845 846 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 847 {Insert, {"2", "5"}}, 848 {Insert, {"10", "9"}}, 849 {Insert, {"12", "10"}}}; 850 851 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { 852 CFGHolder Holder; 853 CFGBuilder B(Holder.F, Arcs, Updates); 854 DominatorTree DT(*Holder.F); 855 EXPECT_TRUE(DT.verify()); 856 PostDominatorTree PDT(*Holder.F); 857 EXPECT_TRUE(PDT.verify()); 858 859 std::optional<CFGBuilder::Update> LastUpdate; 860 while ((LastUpdate = B.applyUpdate())) { 861 EXPECT_EQ(LastUpdate->Action, Insert); 862 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 863 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 864 DT.insertEdge(From, To); 865 EXPECT_TRUE(DT.verify()); 866 PDT.insertEdge(From, To); 867 EXPECT_TRUE(PDT.verify()); 868 } 869 } 870 } 871 872 TEST(DominatorTree, DeleteReachable) { 873 CFGHolder Holder; 874 std::vector<CFGBuilder::Arc> Arcs = { 875 {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, 876 {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 877 878 std::vector<CFGBuilder::Update> Updates = { 879 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; 880 CFGBuilder B(Holder.F, Arcs, Updates); 881 DominatorTree DT(*Holder.F); 882 EXPECT_TRUE(DT.verify()); 883 PostDominatorTree PDT(*Holder.F); 884 EXPECT_TRUE(PDT.verify()); 885 886 std::optional<CFGBuilder::Update> LastUpdate; 887 while ((LastUpdate = B.applyUpdate())) { 888 EXPECT_EQ(LastUpdate->Action, Delete); 889 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 890 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 891 DT.deleteEdge(From, To); 892 EXPECT_TRUE(DT.verify()); 893 PDT.deleteEdge(From, To); 894 EXPECT_TRUE(PDT.verify()); 895 } 896 } 897 898 TEST(DominatorTree, DeleteUnreachable) { 899 CFGHolder Holder; 900 std::vector<CFGBuilder::Arc> Arcs = { 901 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 902 {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 903 904 std::vector<CFGBuilder::Update> Updates = { 905 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; 906 CFGBuilder B(Holder.F, Arcs, Updates); 907 DominatorTree DT(*Holder.F); 908 EXPECT_TRUE(DT.verify()); 909 PostDominatorTree PDT(*Holder.F); 910 EXPECT_TRUE(PDT.verify()); 911 912 std::optional<CFGBuilder::Update> LastUpdate; 913 while ((LastUpdate = B.applyUpdate())) { 914 EXPECT_EQ(LastUpdate->Action, Delete); 915 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 916 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 917 DT.deleteEdge(From, To); 918 EXPECT_TRUE(DT.verify()); 919 PDT.deleteEdge(From, To); 920 EXPECT_TRUE(PDT.verify()); 921 } 922 } 923 924 TEST(DominatorTree, InsertDelete) { 925 std::vector<CFGBuilder::Arc> Arcs = { 926 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 927 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 928 929 std::vector<CFGBuilder::Update> Updates = { 930 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 931 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 932 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 933 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 934 935 CFGHolder Holder; 936 CFGBuilder B(Holder.F, Arcs, Updates); 937 DominatorTree DT(*Holder.F); 938 EXPECT_TRUE(DT.verify()); 939 PostDominatorTree PDT(*Holder.F); 940 EXPECT_TRUE(PDT.verify()); 941 942 std::optional<CFGBuilder::Update> LastUpdate; 943 while ((LastUpdate = B.applyUpdate())) { 944 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 945 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 946 if (LastUpdate->Action == Insert) { 947 DT.insertEdge(From, To); 948 PDT.insertEdge(From, To); 949 } else { 950 DT.deleteEdge(From, To); 951 PDT.deleteEdge(From, To); 952 } 953 954 EXPECT_TRUE(DT.verify()); 955 EXPECT_TRUE(PDT.verify()); 956 } 957 } 958 959 TEST(DominatorTree, InsertDeleteExhaustive) { 960 std::vector<CFGBuilder::Arc> Arcs = { 961 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 962 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 963 964 std::vector<CFGBuilder::Update> Updates = { 965 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 966 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 967 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 968 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 969 970 std::mt19937 Generator(0); 971 for (unsigned i = 0; i < 16; ++i) { 972 std::shuffle(Updates.begin(), Updates.end(), Generator); 973 CFGHolder Holder; 974 CFGBuilder B(Holder.F, Arcs, Updates); 975 DominatorTree DT(*Holder.F); 976 EXPECT_TRUE(DT.verify()); 977 PostDominatorTree PDT(*Holder.F); 978 EXPECT_TRUE(PDT.verify()); 979 980 std::optional<CFGBuilder::Update> LastUpdate; 981 while ((LastUpdate = B.applyUpdate())) { 982 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 983 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 984 if (LastUpdate->Action == Insert) { 985 DT.insertEdge(From, To); 986 PDT.insertEdge(From, To); 987 } else { 988 DT.deleteEdge(From, To); 989 PDT.deleteEdge(From, To); 990 } 991 992 EXPECT_TRUE(DT.verify()); 993 EXPECT_TRUE(PDT.verify()); 994 } 995 } 996 } 997 998 TEST(DominatorTree, InsertIntoIrreducible) { 999 std::vector<CFGBuilder::Arc> Arcs = { 1000 {"0", "1"}, 1001 {"1", "27"}, {"1", "7"}, 1002 {"10", "18"}, 1003 {"13", "10"}, 1004 {"18", "13"}, {"18", "23"}, 1005 {"23", "13"}, {"23", "24"}, 1006 {"24", "1"}, {"24", "18"}, 1007 {"27", "24"}}; 1008 1009 CFGHolder Holder; 1010 CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}}); 1011 DominatorTree DT(*Holder.F); 1012 EXPECT_TRUE(DT.verify()); 1013 1014 B.applyUpdate(); 1015 BasicBlock *From = B.getOrAddBlock("7"); 1016 BasicBlock *To = B.getOrAddBlock("23"); 1017 DT.insertEdge(From, To); 1018 1019 EXPECT_TRUE(DT.verify()); 1020 } 1021 1022 TEST(DominatorTree, EdgeDomination) { 1023 StringRef ModuleString = "define i32 @f(i1 %cond) {\n" 1024 " bb0:\n" 1025 " br i1 %cond, label %bb1, label %bb2\n" 1026 " bb1:\n" 1027 " br label %bb3\n" 1028 " bb2:\n" 1029 " br label %bb3\n" 1030 " bb3:\n" 1031 " ret i32 4" 1032 "}\n"; 1033 1034 // Parse the module. 1035 LLVMContext Context; 1036 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 1037 1038 runWithDomTree(*M, "f", 1039 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 1040 Function::iterator FI = F.begin(); 1041 1042 BasicBlock *BB0 = &*FI++; 1043 BasicBlock *BB1 = &*FI++; 1044 BasicBlock *BB2 = &*FI++; 1045 BasicBlock *BB3 = &*FI++; 1046 1047 BasicBlockEdge E01(BB0, BB1); 1048 BasicBlockEdge E02(BB0, BB2); 1049 BasicBlockEdge E13(BB1, BB3); 1050 BasicBlockEdge E23(BB2, BB3); 1051 1052 EXPECT_TRUE(DT->dominates(E01, E01)); 1053 EXPECT_FALSE(DT->dominates(E01, E02)); 1054 EXPECT_TRUE(DT->dominates(E01, E13)); 1055 EXPECT_FALSE(DT->dominates(E01, E23)); 1056 1057 EXPECT_FALSE(DT->dominates(E02, E01)); 1058 EXPECT_TRUE(DT->dominates(E02, E02)); 1059 EXPECT_FALSE(DT->dominates(E02, E13)); 1060 EXPECT_TRUE(DT->dominates(E02, E23)); 1061 1062 EXPECT_FALSE(DT->dominates(E13, E01)); 1063 EXPECT_FALSE(DT->dominates(E13, E02)); 1064 EXPECT_TRUE(DT->dominates(E13, E13)); 1065 EXPECT_FALSE(DT->dominates(E13, E23)); 1066 1067 EXPECT_FALSE(DT->dominates(E23, E01)); 1068 EXPECT_FALSE(DT->dominates(E23, E02)); 1069 EXPECT_FALSE(DT->dominates(E23, E13)); 1070 EXPECT_TRUE(DT->dominates(E23, E23)); 1071 }); 1072 } 1073 1074 TEST(DominatorTree, ValueDomination) { 1075 StringRef ModuleString = R"( 1076 @foo = global i8 0 1077 define i8 @f(i8 %arg) { 1078 ret i8 %arg 1079 } 1080 )"; 1081 1082 LLVMContext Context; 1083 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 1084 1085 runWithDomTree(*M, "f", 1086 [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 1087 Argument *A = F.getArg(0); 1088 GlobalValue *G = M->getNamedValue("foo"); 1089 Constant *C = ConstantInt::getNullValue(Type::getInt8Ty(Context)); 1090 1091 Instruction *I = F.getEntryBlock().getTerminator(); 1092 EXPECT_TRUE(DT->dominates(A, I)); 1093 EXPECT_TRUE(DT->dominates(G, I)); 1094 EXPECT_TRUE(DT->dominates(C, I)); 1095 1096 const Use &U = I->getOperandUse(0); 1097 EXPECT_TRUE(DT->dominates(A, U)); 1098 EXPECT_TRUE(DT->dominates(G, U)); 1099 EXPECT_TRUE(DT->dominates(C, U)); 1100 }); 1101 } 1102 TEST(DominatorTree, CallBrDomination) { 1103 StringRef ModuleString = R"( 1104 define void @x() { 1105 %y = alloca i32 1106 %w = callbr i32 asm "", "=r,!i"() 1107 to label %asm.fallthrough [label %z] 1108 1109 asm.fallthrough: 1110 br label %cleanup 1111 1112 z: 1113 store i32 %w, ptr %y 1114 br label %cleanup 1115 1116 cleanup: 1117 ret void 1118 })"; 1119 1120 LLVMContext Context; 1121 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 1122 1123 runWithDomTree( 1124 *M, "x", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) { 1125 Function::iterator FI = F.begin(); 1126 1127 BasicBlock *Entry = &*FI++; 1128 BasicBlock *ASMFallthrough = &*FI++; 1129 BasicBlock *Z = &*FI++; 1130 1131 EXPECT_TRUE(DT->dominates(Entry, ASMFallthrough)); 1132 EXPECT_TRUE(DT->dominates(Entry, Z)); 1133 1134 BasicBlock::iterator BBI = Entry->begin(); 1135 ++BBI; 1136 Instruction &I = *BBI; 1137 EXPECT_TRUE(isa<CallBrInst>(I)); 1138 EXPECT_TRUE(isa<Value>(I)); 1139 for (const User *U : I.users()) { 1140 EXPECT_TRUE(isa<Instruction>(U)); 1141 EXPECT_TRUE(DT->dominates(cast<Value>(&I), cast<Instruction>(U))); 1142 } 1143 }); 1144 } 1145