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 <random> 11 #include "llvm/Analysis/PostDominators.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 struct PostDomTree : PostDomTreeBase<BasicBlock> { 25 PostDomTree(Function &F) { recalculate(F); } 26 }; 27 28 /// Build the dominator tree for the function and run the Test. 29 static void runWithDomTree( 30 Module &M, StringRef FuncName, 31 function_ref<void(Function &F, DominatorTree *DT, PostDomTree *PDT)> Test) { 32 auto *F = M.getFunction(FuncName); 33 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 34 // Compute the dominator tree for the function. 35 DominatorTree DT(*F); 36 PostDomTree PDT(*F); 37 Test(*F, &DT, &PDT); 38 } 39 40 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 41 StringRef ModuleStr) { 42 SMDiagnostic Err; 43 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context); 44 assert(M && "Bad assembly?"); 45 return M; 46 } 47 48 TEST(DominatorTree, Unreachable) { 49 StringRef ModuleString = 50 "declare i32 @g()\n" 51 "define void @f(i32 %x) personality i32 ()* @g {\n" 52 "bb0:\n" 53 " %y1 = add i32 %x, 1\n" 54 " %y2 = add i32 %x, 1\n" 55 " %y3 = invoke i32 @g() to label %bb1 unwind label %bb2\n" 56 "bb1:\n" 57 " %y4 = add i32 %x, 1\n" 58 " br label %bb4\n" 59 "bb2:\n" 60 " %y5 = landingpad i32\n" 61 " cleanup\n" 62 " br label %bb4\n" 63 "bb3:\n" 64 " %y6 = add i32 %x, 1\n" 65 " %y7 = add i32 %x, 1\n" 66 " ret void\n" 67 "bb4:\n" 68 " %y8 = phi i32 [0, %bb2], [%y4, %bb1]\n" 69 " %y9 = phi i32 [0, %bb2], [%y4, %bb1]\n" 70 " ret void\n" 71 "}\n"; 72 73 // Parse the module. 74 LLVMContext Context; 75 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 76 77 runWithDomTree( 78 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 79 Function::iterator FI = F.begin(); 80 81 BasicBlock *BB0 = &*FI++; 82 BasicBlock::iterator BBI = BB0->begin(); 83 Instruction *Y1 = &*BBI++; 84 Instruction *Y2 = &*BBI++; 85 Instruction *Y3 = &*BBI++; 86 87 BasicBlock *BB1 = &*FI++; 88 BBI = BB1->begin(); 89 Instruction *Y4 = &*BBI++; 90 91 BasicBlock *BB2 = &*FI++; 92 BBI = BB2->begin(); 93 Instruction *Y5 = &*BBI++; 94 95 BasicBlock *BB3 = &*FI++; 96 BBI = BB3->begin(); 97 Instruction *Y6 = &*BBI++; 98 Instruction *Y7 = &*BBI++; 99 100 BasicBlock *BB4 = &*FI++; 101 BBI = BB4->begin(); 102 Instruction *Y8 = &*BBI++; 103 Instruction *Y9 = &*BBI++; 104 105 // Reachability 106 EXPECT_TRUE(DT->isReachableFromEntry(BB0)); 107 EXPECT_TRUE(DT->isReachableFromEntry(BB1)); 108 EXPECT_TRUE(DT->isReachableFromEntry(BB2)); 109 EXPECT_FALSE(DT->isReachableFromEntry(BB3)); 110 EXPECT_TRUE(DT->isReachableFromEntry(BB4)); 111 112 // BB dominance 113 EXPECT_TRUE(DT->dominates(BB0, BB0)); 114 EXPECT_TRUE(DT->dominates(BB0, BB1)); 115 EXPECT_TRUE(DT->dominates(BB0, BB2)); 116 EXPECT_TRUE(DT->dominates(BB0, BB3)); 117 EXPECT_TRUE(DT->dominates(BB0, BB4)); 118 119 EXPECT_FALSE(DT->dominates(BB1, BB0)); 120 EXPECT_TRUE(DT->dominates(BB1, BB1)); 121 EXPECT_FALSE(DT->dominates(BB1, BB2)); 122 EXPECT_TRUE(DT->dominates(BB1, BB3)); 123 EXPECT_FALSE(DT->dominates(BB1, BB4)); 124 125 EXPECT_FALSE(DT->dominates(BB2, BB0)); 126 EXPECT_FALSE(DT->dominates(BB2, BB1)); 127 EXPECT_TRUE(DT->dominates(BB2, BB2)); 128 EXPECT_TRUE(DT->dominates(BB2, BB3)); 129 EXPECT_FALSE(DT->dominates(BB2, BB4)); 130 131 EXPECT_FALSE(DT->dominates(BB3, BB0)); 132 EXPECT_FALSE(DT->dominates(BB3, BB1)); 133 EXPECT_FALSE(DT->dominates(BB3, BB2)); 134 EXPECT_TRUE(DT->dominates(BB3, BB3)); 135 EXPECT_FALSE(DT->dominates(BB3, BB4)); 136 137 // BB proper dominance 138 EXPECT_FALSE(DT->properlyDominates(BB0, BB0)); 139 EXPECT_TRUE(DT->properlyDominates(BB0, BB1)); 140 EXPECT_TRUE(DT->properlyDominates(BB0, BB2)); 141 EXPECT_TRUE(DT->properlyDominates(BB0, BB3)); 142 143 EXPECT_FALSE(DT->properlyDominates(BB1, BB0)); 144 EXPECT_FALSE(DT->properlyDominates(BB1, BB1)); 145 EXPECT_FALSE(DT->properlyDominates(BB1, BB2)); 146 EXPECT_TRUE(DT->properlyDominates(BB1, BB3)); 147 148 EXPECT_FALSE(DT->properlyDominates(BB2, BB0)); 149 EXPECT_FALSE(DT->properlyDominates(BB2, BB1)); 150 EXPECT_FALSE(DT->properlyDominates(BB2, BB2)); 151 EXPECT_TRUE(DT->properlyDominates(BB2, BB3)); 152 153 EXPECT_FALSE(DT->properlyDominates(BB3, BB0)); 154 EXPECT_FALSE(DT->properlyDominates(BB3, BB1)); 155 EXPECT_FALSE(DT->properlyDominates(BB3, BB2)); 156 EXPECT_FALSE(DT->properlyDominates(BB3, BB3)); 157 158 // Instruction dominance in the same reachable BB 159 EXPECT_FALSE(DT->dominates(Y1, Y1)); 160 EXPECT_TRUE(DT->dominates(Y1, Y2)); 161 EXPECT_FALSE(DT->dominates(Y2, Y1)); 162 EXPECT_FALSE(DT->dominates(Y2, Y2)); 163 164 // Instruction dominance in the same unreachable BB 165 EXPECT_TRUE(DT->dominates(Y6, Y6)); 166 EXPECT_TRUE(DT->dominates(Y6, Y7)); 167 EXPECT_TRUE(DT->dominates(Y7, Y6)); 168 EXPECT_TRUE(DT->dominates(Y7, Y7)); 169 170 // Invoke 171 EXPECT_TRUE(DT->dominates(Y3, Y4)); 172 EXPECT_FALSE(DT->dominates(Y3, Y5)); 173 174 // Phi 175 EXPECT_TRUE(DT->dominates(Y2, Y9)); 176 EXPECT_FALSE(DT->dominates(Y3, Y9)); 177 EXPECT_FALSE(DT->dominates(Y8, Y9)); 178 179 // Anything dominates unreachable 180 EXPECT_TRUE(DT->dominates(Y1, Y6)); 181 EXPECT_TRUE(DT->dominates(Y3, Y6)); 182 183 // Unreachable doesn't dominate reachable 184 EXPECT_FALSE(DT->dominates(Y6, Y1)); 185 186 // Instruction, BB dominance 187 EXPECT_FALSE(DT->dominates(Y1, BB0)); 188 EXPECT_TRUE(DT->dominates(Y1, BB1)); 189 EXPECT_TRUE(DT->dominates(Y1, BB2)); 190 EXPECT_TRUE(DT->dominates(Y1, BB3)); 191 EXPECT_TRUE(DT->dominates(Y1, BB4)); 192 193 EXPECT_FALSE(DT->dominates(Y3, BB0)); 194 EXPECT_TRUE(DT->dominates(Y3, BB1)); 195 EXPECT_FALSE(DT->dominates(Y3, BB2)); 196 EXPECT_TRUE(DT->dominates(Y3, BB3)); 197 EXPECT_FALSE(DT->dominates(Y3, BB4)); 198 199 EXPECT_TRUE(DT->dominates(Y6, BB3)); 200 201 // Post dominance. 202 EXPECT_TRUE(PDT->dominates(BB0, BB0)); 203 EXPECT_FALSE(PDT->dominates(BB1, BB0)); 204 EXPECT_FALSE(PDT->dominates(BB2, BB0)); 205 EXPECT_FALSE(PDT->dominates(BB3, BB0)); 206 EXPECT_TRUE(PDT->dominates(BB4, BB1)); 207 208 // Dominance descendants. 209 SmallVector<BasicBlock *, 8> DominatedBBs, PostDominatedBBs; 210 211 DT->getDescendants(BB0, DominatedBBs); 212 PDT->getDescendants(BB0, PostDominatedBBs); 213 EXPECT_EQ(DominatedBBs.size(), 4UL); 214 EXPECT_EQ(PostDominatedBBs.size(), 1UL); 215 216 // BB3 is unreachable. It should have no dominators nor postdominators. 217 DominatedBBs.clear(); 218 PostDominatedBBs.clear(); 219 DT->getDescendants(BB3, DominatedBBs); 220 DT->getDescendants(BB3, PostDominatedBBs); 221 EXPECT_EQ(DominatedBBs.size(), 0UL); 222 EXPECT_EQ(PostDominatedBBs.size(), 0UL); 223 224 // Check DFS Numbers before 225 DT->updateDFSNumbers(); 226 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 227 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 7UL); 228 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 229 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 2UL); 230 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 5UL); 231 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 6UL); 232 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 3UL); 233 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 4UL); 234 235 // Check levels before 236 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 237 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 238 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 239 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 240 241 // Reattach block 3 to block 1 and recalculate 242 BB1->getTerminator()->eraseFromParent(); 243 BranchInst::Create(BB4, BB3, ConstantInt::getTrue(F.getContext()), BB1); 244 DT->recalculate(F); 245 246 // Check DFS Numbers after 247 DT->updateDFSNumbers(); 248 EXPECT_EQ(DT->getNode(BB0)->getDFSNumIn(), 0UL); 249 EXPECT_EQ(DT->getNode(BB0)->getDFSNumOut(), 9UL); 250 EXPECT_EQ(DT->getNode(BB1)->getDFSNumIn(), 1UL); 251 EXPECT_EQ(DT->getNode(BB1)->getDFSNumOut(), 4UL); 252 EXPECT_EQ(DT->getNode(BB2)->getDFSNumIn(), 7UL); 253 EXPECT_EQ(DT->getNode(BB2)->getDFSNumOut(), 8UL); 254 EXPECT_EQ(DT->getNode(BB3)->getDFSNumIn(), 2UL); 255 EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL); 256 EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL); 257 EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL); 258 259 // Check levels after 260 EXPECT_EQ(DT->getNode(BB0)->getLevel(), 0U); 261 EXPECT_EQ(DT->getNode(BB1)->getLevel(), 1U); 262 EXPECT_EQ(DT->getNode(BB2)->getLevel(), 1U); 263 EXPECT_EQ(DT->getNode(BB3)->getLevel(), 2U); 264 EXPECT_EQ(DT->getNode(BB4)->getLevel(), 1U); 265 266 // Change root node 267 DT->verifyDomTree(); 268 BasicBlock *NewEntry = 269 BasicBlock::Create(F.getContext(), "new_entry", &F, BB0); 270 BranchInst::Create(BB0, NewEntry); 271 EXPECT_EQ(F.begin()->getName(), NewEntry->getName()); 272 EXPECT_TRUE(&F.getEntryBlock() == NewEntry); 273 DT->setNewRoot(NewEntry); 274 DT->verifyDomTree(); 275 }); 276 } 277 278 TEST(DominatorTree, NonUniqueEdges) { 279 StringRef ModuleString = 280 "define i32 @f(i32 %i, i32 *%p) {\n" 281 "bb0:\n" 282 " store i32 %i, i32 *%p\n" 283 " switch i32 %i, label %bb2 [\n" 284 " i32 0, label %bb1\n" 285 " i32 1, label %bb1\n" 286 " ]\n" 287 " bb1:\n" 288 " ret i32 1\n" 289 " bb2:\n" 290 " ret i32 4\n" 291 "}\n"; 292 293 // Parse the module. 294 LLVMContext Context; 295 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 296 297 runWithDomTree( 298 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 299 Function::iterator FI = F.begin(); 300 301 BasicBlock *BB0 = &*FI++; 302 BasicBlock *BB1 = &*FI++; 303 BasicBlock *BB2 = &*FI++; 304 305 const TerminatorInst *TI = BB0->getTerminator(); 306 assert(TI->getNumSuccessors() == 3 && "Switch has three successors"); 307 308 BasicBlockEdge Edge_BB0_BB2(BB0, TI->getSuccessor(0)); 309 assert(Edge_BB0_BB2.getEnd() == BB2 && 310 "Default label is the 1st successor"); 311 312 BasicBlockEdge Edge_BB0_BB1_a(BB0, TI->getSuccessor(1)); 313 assert(Edge_BB0_BB1_a.getEnd() == BB1 && "BB1 is the 2nd successor"); 314 315 BasicBlockEdge Edge_BB0_BB1_b(BB0, TI->getSuccessor(2)); 316 assert(Edge_BB0_BB1_b.getEnd() == BB1 && "BB1 is the 3rd successor"); 317 318 EXPECT_TRUE(DT->dominates(Edge_BB0_BB2, BB2)); 319 EXPECT_FALSE(DT->dominates(Edge_BB0_BB2, BB1)); 320 321 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB1)); 322 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB1)); 323 324 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_a, BB2)); 325 EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); 326 }); 327 } 328 329 // Verify that the PDT is correctly updated in case an edge removal results 330 // in a new unreachable CFG node. Also make sure that the updated PDT is the 331 // same as a freshly recalculated one. 332 // 333 // For the following input code and initial PDT: 334 // 335 // CFG PDT 336 // 337 // A Exit 338 // | | 339 // _B D 340 // / | \ | 341 // ^ v \ B 342 // \ / D / \ 343 // C \ C A 344 // v 345 // Exit 346 // 347 // we verify that CFG' and PDT-updated is obtained after removal of edge C -> B. 348 // 349 // CFG' PDT-updated 350 // 351 // A Exit 352 // | / | \ 353 // B C B D 354 // | \ | 355 // v \ A 356 // / D 357 // C \ 358 // | \ 359 // unreachable Exit 360 // 361 // Both the blocks that end with ret and with unreachable become trivial 362 // PostDomTree roots, as they have no successors. 363 // 364 TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { 365 StringRef ModuleString = 366 "define void @f() {\n" 367 "A:\n" 368 " br label %B\n" 369 "B:\n" 370 " br i1 undef, label %D, label %C\n" 371 "C:\n" 372 " br label %B\n" 373 "D:\n" 374 " ret void\n" 375 "}\n"; 376 377 // Parse the module. 378 LLVMContext Context; 379 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 380 381 runWithDomTree( 382 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 383 Function::iterator FI = F.begin(); 384 385 FI++; 386 BasicBlock *B = &*FI++; 387 BasicBlock *C = &*FI++; 388 BasicBlock *D = &*FI++; 389 390 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 391 EXPECT_TRUE(DT->verify()); 392 EXPECT_TRUE(PDT->verify()); 393 394 C->getTerminator()->eraseFromParent(); 395 new UnreachableInst(C->getContext(), C); 396 397 DT->deleteEdge(C, B); 398 PDT->deleteEdge(C, B); 399 400 EXPECT_TRUE(DT->verify()); 401 EXPECT_TRUE(PDT->verify()); 402 403 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 404 EXPECT_NE(PDT->getNode(C), nullptr); 405 406 DominatorTree NDT(F); 407 EXPECT_EQ(DT->compare(NDT), 0); 408 409 PostDomTree NPDT(F); 410 EXPECT_EQ(PDT->compare(NPDT), 0); 411 }); 412 } 413 414 // Verify that the PDT is correctly updated in case an edge removal results 415 // in an infinite loop. Also make sure that the updated PDT is the 416 // same as a freshly recalculated one. 417 // 418 // Test case: 419 // 420 // CFG PDT 421 // 422 // A Exit 423 // | | 424 // _B D 425 // / | \ | 426 // ^ v \ B 427 // \ / D / \ 428 // C \ C A 429 // / \ v 430 // ^ v Exit 431 // \_/ 432 // 433 // After deleting the edge C->B, C is part of an infinite reverse-unreachable 434 // loop: 435 // 436 // CFG' PDT' 437 // 438 // A Exit 439 // | / | \ 440 // B C B D 441 // | \ | 442 // v \ A 443 // / D 444 // C \ 445 // / \ v 446 // ^ v Exit 447 // \_/ 448 // 449 // As C now becomes reverse-unreachable, it forms a new non-trivial root and 450 // gets connected to the virtual exit. 451 // D does not postdominate B anymore, because there are two forward paths from 452 // B to the virtual exit: 453 // - B -> C -> VirtualExit 454 // - B -> D -> VirtualExit. 455 // 456 TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { 457 StringRef ModuleString = 458 "define void @f() {\n" 459 "A:\n" 460 " br label %B\n" 461 "B:\n" 462 " br i1 undef, label %D, label %C\n" 463 "C:\n" 464 " switch i32 undef, label %C [\n" 465 " i32 0, label %B\n" 466 " ]\n" 467 "D:\n" 468 " ret void\n" 469 "}\n"; 470 471 // Parse the module. 472 LLVMContext Context; 473 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 474 475 runWithDomTree( 476 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 477 Function::iterator FI = F.begin(); 478 479 FI++; 480 BasicBlock *B = &*FI++; 481 BasicBlock *C = &*FI++; 482 BasicBlock *D = &*FI++; 483 484 ASSERT_TRUE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 485 EXPECT_TRUE(DT->verify()); 486 EXPECT_TRUE(PDT->verify()); 487 488 auto SwitchC = cast<SwitchInst>(C->getTerminator()); 489 SwitchC->removeCase(SwitchC->case_begin()); 490 DT->deleteEdge(C, B); 491 EXPECT_TRUE(DT->verify()); 492 PDT->deleteEdge(C, B); 493 EXPECT_TRUE(PDT->verify()); 494 495 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 496 EXPECT_NE(PDT->getNode(C), nullptr); 497 498 DominatorTree NDT(F); 499 EXPECT_EQ(DT->compare(NDT), 0); 500 501 PostDomTree NPDT(F); 502 EXPECT_EQ(PDT->compare(NPDT), 0); 503 }); 504 } 505 506 // Verify that the PDT is correctly updated in case an edge removal results 507 // in an infinite loop. 508 // 509 // Test case: 510 // 511 // CFG PDT 512 // 513 // A Exit 514 // | / | \ 515 // B-- C2 B D 516 // | \ / | 517 // v \ C A 518 // / D 519 // C--C2 \ 520 // / \ \ v 521 // ^ v --Exit 522 // \_/ 523 // 524 // After deleting the edge C->E, C is part of an infinite reverse-unreachable 525 // loop: 526 // 527 // CFG' PDT' 528 // 529 // A Exit 530 // | / | \ 531 // B C B D 532 // | \ | 533 // v \ A 534 // / D 535 // C \ 536 // / \ v 537 // ^ v Exit 538 // \_/ 539 // 540 // In PDT, D does not post-dominate B. After the edge C -> C2 is removed, 541 // C becomes a new nontrivial PDT root. 542 // 543 TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { 544 StringRef ModuleString = 545 "define void @f() {\n" 546 "A:\n" 547 " br label %B\n" 548 "B:\n" 549 " br i1 undef, label %D, label %C\n" 550 "C:\n" 551 " switch i32 undef, label %C [\n" 552 " i32 0, label %C2\n" 553 " ]\n" 554 "C2:\n" 555 " ret void\n" 556 "D:\n" 557 " ret void\n" 558 "}\n"; 559 560 // Parse the module. 561 LLVMContext Context; 562 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString); 563 564 runWithDomTree( 565 *M, "f", [&](Function &F, DominatorTree *DT, PostDomTree *PDT) { 566 Function::iterator FI = F.begin(); 567 568 FI++; 569 BasicBlock *B = &*FI++; 570 BasicBlock *C = &*FI++; 571 BasicBlock *C2 = &*FI++; 572 BasicBlock *D = &*FI++; 573 574 EXPECT_TRUE(DT->verify()); 575 EXPECT_TRUE(PDT->verify()); 576 577 auto SwitchC = cast<SwitchInst>(C->getTerminator()); 578 SwitchC->removeCase(SwitchC->case_begin()); 579 DT->deleteEdge(C, C2); 580 PDT->deleteEdge(C, C2); 581 C2->removeFromParent(); 582 583 EXPECT_EQ(DT->getNode(C2), nullptr); 584 PDT->eraseNode(C2); 585 delete C2; 586 587 EXPECT_TRUE(DT->verify()); 588 EXPECT_TRUE(PDT->verify()); 589 590 EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B))); 591 EXPECT_NE(PDT->getNode(C), nullptr); 592 593 DominatorTree NDT(F); 594 EXPECT_EQ(DT->compare(NDT), 0); 595 596 PostDomTree NPDT(F); 597 EXPECT_EQ(PDT->compare(NPDT), 0); 598 }); 599 } 600 601 namespace { 602 const auto Insert = CFGBuilder::ActionKind::Insert; 603 const auto Delete = CFGBuilder::ActionKind::Delete; 604 605 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { 606 return std::tie(A.Action, A.Edge.From, A.Edge.To) < 607 std::tie(B.Action, B.Edge.From, B.Edge.To); 608 } 609 } // namespace 610 611 TEST(DominatorTree, InsertReachable) { 612 CFGHolder Holder; 613 std::vector<CFGBuilder::Arc> Arcs = { 614 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 615 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 616 617 std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}}, 618 {Insert, {"10", "9"}}, 619 {Insert, {"7", "6"}}, 620 {Insert, {"7", "5"}}}; 621 CFGBuilder B(Holder.F, Arcs, Updates); 622 DominatorTree DT(*Holder.F); 623 EXPECT_TRUE(DT.verify()); 624 PostDomTree PDT(*Holder.F); 625 EXPECT_TRUE(PDT.verify()); 626 627 Optional<CFGBuilder::Update> LastUpdate; 628 while ((LastUpdate = B.applyUpdate())) { 629 EXPECT_EQ(LastUpdate->Action, Insert); 630 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 631 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 632 DT.insertEdge(From, To); 633 EXPECT_TRUE(DT.verify()); 634 PDT.insertEdge(From, To); 635 EXPECT_TRUE(PDT.verify()); 636 } 637 } 638 639 TEST(DominatorTree, InsertReachable2) { 640 CFGHolder Holder; 641 std::vector<CFGBuilder::Arc> Arcs = { 642 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 643 {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"}, 644 {"10", "9"}, {"9", "10"}}; 645 646 std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}}; 647 CFGBuilder B(Holder.F, Arcs, Updates); 648 DominatorTree DT(*Holder.F); 649 EXPECT_TRUE(DT.verify()); 650 PostDomTree PDT(*Holder.F); 651 EXPECT_TRUE(PDT.verify()); 652 653 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 654 EXPECT_TRUE(LastUpdate); 655 656 EXPECT_EQ(LastUpdate->Action, Insert); 657 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 658 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 659 DT.insertEdge(From, To); 660 EXPECT_TRUE(DT.verify()); 661 PDT.insertEdge(From, To); 662 EXPECT_TRUE(PDT.verify()); 663 } 664 665 TEST(DominatorTree, InsertUnreachable) { 666 CFGHolder Holder; 667 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, 668 {"5", "6"}, {"5", "7"}, {"3", "8"}, 669 {"9", "10"}, {"11", "12"}}; 670 671 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 672 {Insert, {"8", "9"}}, 673 {Insert, {"10", "12"}}, 674 {Insert, {"10", "11"}}}; 675 CFGBuilder B(Holder.F, Arcs, Updates); 676 DominatorTree DT(*Holder.F); 677 EXPECT_TRUE(DT.verify()); 678 PostDomTree PDT(*Holder.F); 679 EXPECT_TRUE(PDT.verify()); 680 681 Optional<CFGBuilder::Update> LastUpdate; 682 while ((LastUpdate = B.applyUpdate())) { 683 EXPECT_EQ(LastUpdate->Action, Insert); 684 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 685 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 686 DT.insertEdge(From, To); 687 EXPECT_TRUE(DT.verify()); 688 PDT.insertEdge(From, To); 689 EXPECT_TRUE(PDT.verify()); 690 } 691 } 692 693 TEST(DominatorTree, InsertFromUnreachable) { 694 CFGHolder Holder; 695 std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}}; 696 697 std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}}; 698 CFGBuilder B(Holder.F, Arcs, Updates); 699 PostDomTree PDT(*Holder.F); 700 EXPECT_TRUE(PDT.verify()); 701 702 Optional<CFGBuilder::Update> LastUpdate = B.applyUpdate(); 703 EXPECT_TRUE(LastUpdate); 704 705 EXPECT_EQ(LastUpdate->Action, Insert); 706 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 707 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 708 PDT.insertEdge(From, To); 709 EXPECT_TRUE(PDT.verify()); 710 EXPECT_TRUE(PDT.getRoots().size() == 2); 711 EXPECT_NE(PDT.getNode(B.getOrAddBlock("5")), nullptr); 712 } 713 714 TEST(DominatorTree, InsertMixed) { 715 CFGHolder Holder; 716 std::vector<CFGBuilder::Arc> Arcs = { 717 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 718 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 719 720 std::vector<CFGBuilder::Update> Updates = { 721 {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, 722 {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, 723 {Insert, {"7", "5"}}}; 724 CFGBuilder B(Holder.F, Arcs, Updates); 725 DominatorTree DT(*Holder.F); 726 EXPECT_TRUE(DT.verify()); 727 PostDomTree PDT(*Holder.F); 728 EXPECT_TRUE(PDT.verify()); 729 730 Optional<CFGBuilder::Update> LastUpdate; 731 while ((LastUpdate = B.applyUpdate())) { 732 EXPECT_EQ(LastUpdate->Action, Insert); 733 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 734 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 735 DT.insertEdge(From, To); 736 EXPECT_TRUE(DT.verify()); 737 PDT.insertEdge(From, To); 738 EXPECT_TRUE(PDT.verify()); 739 } 740 } 741 742 TEST(DominatorTree, InsertPermut) { 743 std::vector<CFGBuilder::Arc> Arcs = { 744 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, 745 {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; 746 747 std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}}, 748 {Insert, {"2", "5"}}, 749 {Insert, {"10", "9"}}, 750 {Insert, {"12", "10"}}}; 751 752 while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { 753 CFGHolder Holder; 754 CFGBuilder B(Holder.F, Arcs, Updates); 755 DominatorTree DT(*Holder.F); 756 EXPECT_TRUE(DT.verify()); 757 PostDomTree PDT(*Holder.F); 758 EXPECT_TRUE(PDT.verify()); 759 760 Optional<CFGBuilder::Update> LastUpdate; 761 while ((LastUpdate = B.applyUpdate())) { 762 EXPECT_EQ(LastUpdate->Action, Insert); 763 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 764 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 765 DT.insertEdge(From, To); 766 EXPECT_TRUE(DT.verify()); 767 PDT.insertEdge(From, To); 768 EXPECT_TRUE(PDT.verify()); 769 } 770 } 771 } 772 773 TEST(DominatorTree, DeleteReachable) { 774 CFGHolder Holder; 775 std::vector<CFGBuilder::Arc> Arcs = { 776 {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, 777 {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 778 779 std::vector<CFGBuilder::Update> Updates = { 780 {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; 781 CFGBuilder B(Holder.F, Arcs, Updates); 782 DominatorTree DT(*Holder.F); 783 EXPECT_TRUE(DT.verify()); 784 PostDomTree PDT(*Holder.F); 785 EXPECT_TRUE(PDT.verify()); 786 787 Optional<CFGBuilder::Update> LastUpdate; 788 while ((LastUpdate = B.applyUpdate())) { 789 EXPECT_EQ(LastUpdate->Action, Delete); 790 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 791 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 792 DT.deleteEdge(From, To); 793 EXPECT_TRUE(DT.verify()); 794 PDT.deleteEdge(From, To); 795 EXPECT_TRUE(PDT.verify()); 796 } 797 } 798 799 TEST(DominatorTree, DeleteUnreachable) { 800 CFGHolder Holder; 801 std::vector<CFGBuilder::Arc> Arcs = { 802 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 803 {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; 804 805 std::vector<CFGBuilder::Update> Updates = { 806 {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; 807 CFGBuilder B(Holder.F, Arcs, Updates); 808 DominatorTree DT(*Holder.F); 809 EXPECT_TRUE(DT.verify()); 810 PostDomTree PDT(*Holder.F); 811 EXPECT_TRUE(PDT.verify()); 812 813 Optional<CFGBuilder::Update> LastUpdate; 814 while ((LastUpdate = B.applyUpdate())) { 815 EXPECT_EQ(LastUpdate->Action, Delete); 816 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 817 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 818 DT.deleteEdge(From, To); 819 EXPECT_TRUE(DT.verify()); 820 PDT.deleteEdge(From, To); 821 EXPECT_TRUE(PDT.verify()); 822 } 823 } 824 825 TEST(DominatorTree, DeletionsInSubtrees) { 826 CFGHolder Holder; 827 std::vector<CFGBuilder::Arc> Arcs = {{"0", "1"}, {"1", "2"}, {"1", "3"}, 828 {"1", "6"}, {"3", "4"}, {"2", "5"}, 829 {"5", "2"}}; 830 831 // It is possible to perform multiple deletions and inform the 832 // DominatorTree about them at the same time, if the all of the 833 // deletions happen in different subtrees. 834 std::vector<CFGBuilder::Update> Updates = {{Delete, {"1", "2"}}, 835 {Delete, {"1", "3"}}}; 836 CFGBuilder B(Holder.F, Arcs, Updates); 837 DominatorTree DT(*Holder.F); 838 EXPECT_TRUE(DT.verify()); 839 840 Optional<CFGBuilder::Update> LastUpdate; 841 while ((LastUpdate = B.applyUpdate())) 842 ; 843 844 DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("2")); 845 DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("3")); 846 847 EXPECT_TRUE(DT.verify()); 848 EXPECT_EQ(DT.getNode(B.getOrAddBlock("2")), nullptr); 849 EXPECT_EQ(DT.getNode(B.getOrAddBlock("3")), nullptr); 850 EXPECT_EQ(DT.getNode(B.getOrAddBlock("4")), nullptr); 851 EXPECT_EQ(DT.getNode(B.getOrAddBlock("5")), nullptr); 852 EXPECT_NE(DT.getNode(B.getOrAddBlock("6")), nullptr); 853 } 854 855 TEST(DominatorTree, InsertDelete) { 856 std::vector<CFGBuilder::Arc> Arcs = { 857 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 858 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 859 860 std::vector<CFGBuilder::Update> Updates = { 861 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 862 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 863 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 864 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 865 866 CFGHolder Holder; 867 CFGBuilder B(Holder.F, Arcs, Updates); 868 DominatorTree DT(*Holder.F); 869 EXPECT_TRUE(DT.verify()); 870 PostDomTree PDT(*Holder.F); 871 EXPECT_TRUE(PDT.verify()); 872 873 Optional<CFGBuilder::Update> LastUpdate; 874 while ((LastUpdate = B.applyUpdate())) { 875 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 876 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 877 if (LastUpdate->Action == Insert) { 878 DT.insertEdge(From, To); 879 PDT.insertEdge(From, To); 880 } else { 881 DT.deleteEdge(From, To); 882 PDT.deleteEdge(From, To); 883 } 884 885 EXPECT_TRUE(DT.verify()); 886 EXPECT_TRUE(PDT.verify()); 887 } 888 } 889 890 TEST(DominatorTree, InsertDeleteExhaustive) { 891 std::vector<CFGBuilder::Arc> Arcs = { 892 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, 893 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; 894 895 std::vector<CFGBuilder::Update> Updates = { 896 {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, 897 {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, 898 {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, 899 {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; 900 901 std::mt19937 Generator(0); 902 for (unsigned i = 0; i < 16; ++i) { 903 std::shuffle(Updates.begin(), Updates.end(), Generator); 904 CFGHolder Holder; 905 CFGBuilder B(Holder.F, Arcs, Updates); 906 DominatorTree DT(*Holder.F); 907 EXPECT_TRUE(DT.verify()); 908 PostDomTree PDT(*Holder.F); 909 EXPECT_TRUE(PDT.verify()); 910 911 Optional<CFGBuilder::Update> LastUpdate; 912 while ((LastUpdate = B.applyUpdate())) { 913 BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); 914 BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); 915 if (LastUpdate->Action == Insert) { 916 DT.insertEdge(From, To); 917 PDT.insertEdge(From, To); 918 } else { 919 DT.deleteEdge(From, To); 920 PDT.deleteEdge(From, To); 921 } 922 923 EXPECT_TRUE(DT.verify()); 924 EXPECT_TRUE(PDT.verify()); 925 } 926 } 927 } 928