unittests/IR/DominatorTreeTest.cpp

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