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