unittests/IR/DominatorTreeTest.cpp

   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
 929 TEST(DominatorTree, InsertIntoIrreducible) {
 930   std::vector<CFGBuilder::Arc> Arcs = {
 931       {"0", "1"},
 932       {"1", "27"}, {"1", "7"},
 933       {"10", "18"},
 934       {"13", "10"},
 935       {"18", "13"}, {"18", "23"},
 936       {"23", "13"}, {"23", "24"},
 937       {"24", "1"}, {"24", "18"},
 938       {"27", "24"}};
 939
 940   CFGHolder Holder;
 941   CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});
 942   DominatorTree DT(*Holder.F);
 943   EXPECT_TRUE(DT.verify());
 944
 945   B.applyUpdate();
 946   BasicBlock *From = B.getOrAddBlock("7");
 947   BasicBlock *To = B.getOrAddBlock("23");
 948   DT.insertEdge(From, To);
 949
 950   EXPECT_TRUE(DT.verify());
 951 }
 952