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
 611         EXPECT_EQ(DT->getNode(C2), nullptr);
 612         PDT->eraseNode(C2);
 613         C2->eraseFromParent();
 614
 615         EXPECT_TRUE(DT->verify());
 616         EXPECT_TRUE(PDT->verify());
 617
 618         EXPECT_FALSE(PDT->dominates(PDT->getNode(D), PDT->getNode(B)));
 619         EXPECT_NE(PDT->getNode(C), nullptr);
 620
 621         DominatorTree NDT(F);
 622         EXPECT_EQ(DT->compare(NDT), 0);
 623
 624         PostDominatorTree NPDT(F);
 625         EXPECT_EQ(PDT->compare(NPDT), 0);
 626       });
 627 }
 628
 629 // Verify that the IDF returns blocks in a deterministic way.
 630 //
 631 // Test case:
 632 //
 633 //          CFG
 634 //
 635 //          (A)
 636 //          / \
 637 //         /   \
 638 //       (B)   (C)
 639 //        |\   /|
 640 //        |  X  |
 641 //        |/   \|
 642 //       (D)   (E)
 643 //
 644 // IDF for block B is {D, E}, and the order of blocks in this list is defined by
 645 // their 1) level in dom-tree and 2) DFSIn number if the level is the same.
 646 //
 647 TEST(DominatorTree, IDFDeterminismTest) {
 648   StringRef ModuleString =
 649       "define void @f() {\n"
 650       "A:\n"
 651       "  br i1 undef, label %B, label %C\n"
 652       "B:\n"
 653       "  br i1 undef, label %D, label %E\n"
 654       "C:\n"
 655       "  br i1 undef, label %D, label %E\n"
 656       "D:\n"
 657       "  ret void\n"
 658       "E:\n"
 659       "  ret void\n"
 660       "}\n";
 661
 662   // Parse the module.
 663   LLVMContext Context;
 664   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 665
 666   runWithDomTree(
 667       *M, "f", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
 668         Function::iterator FI = F.begin();
 669
 670         BasicBlock *A = &*FI++;
 671         BasicBlock *B = &*FI++;
 672         BasicBlock *C = &*FI++;
 673         BasicBlock *D = &*FI++;
 674         BasicBlock *E = &*FI++;
 675         (void)C;
 676
 677         DT->updateDFSNumbers();
 678         ForwardIDFCalculator IDF(*DT);
 679         SmallPtrSet<BasicBlock *, 1> DefBlocks;
 680         DefBlocks.insert(B);
 681         IDF.setDefiningBlocks(DefBlocks);
 682
 683         SmallVector<BasicBlock *, 32> IDFBlocks;
 684         SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
 685         IDF.resetLiveInBlocks();
 686         IDF.calculate(IDFBlocks);
 687
 688
 689         EXPECT_EQ(IDFBlocks.size(), 2UL);
 690         EXPECT_EQ(DT->getNode(A)->getDFSNumIn(), 0UL);
 691         EXPECT_EQ(IDFBlocks[0], D);
 692         EXPECT_EQ(IDFBlocks[1], E);
 693         EXPECT_TRUE(DT->getNode(IDFBlocks[0])->getDFSNumIn() <
 694                     DT->getNode(IDFBlocks[1])->getDFSNumIn());
 695       });
 696 }
 697
 698 namespace {
 699 const auto Insert = CFGBuilder::ActionKind::Insert;
 700 const auto Delete = CFGBuilder::ActionKind::Delete;
 701
 702 bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) {
 703   return std::tie(A.Action, A.Edge.From, A.Edge.To) <
 704          std::tie(B.Action, B.Edge.From, B.Edge.To);
 705 }
 706 }  // namespace
 707
 708 TEST(DominatorTree, InsertReachable) {
 709   CFGHolder Holder;
 710   std::vector<CFGBuilder::Arc> Arcs = {
 711       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 712       {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
 713
 714   std::vector<CFGBuilder::Update> Updates = {{Insert, {"12", "10"}},
 715                                              {Insert, {"10", "9"}},
 716                                              {Insert, {"7", "6"}},
 717                                              {Insert, {"7", "5"}}};
 718   CFGBuilder B(Holder.F, Arcs, Updates);
 719   DominatorTree DT(*Holder.F);
 720   EXPECT_TRUE(DT.verify());
 721   PostDominatorTree PDT(*Holder.F);
 722   EXPECT_TRUE(PDT.verify());
 723
 724   std::optional<CFGBuilder::Update> LastUpdate;
 725   while ((LastUpdate = B.applyUpdate())) {
 726     EXPECT_EQ(LastUpdate->Action, Insert);
 727     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 728     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 729     DT.insertEdge(From, To);
 730     EXPECT_TRUE(DT.verify());
 731     PDT.insertEdge(From, To);
 732     EXPECT_TRUE(PDT.verify());
 733   }
 734 }
 735
 736 TEST(DominatorTree, InsertReachable2) {
 737   CFGHolder Holder;
 738   std::vector<CFGBuilder::Arc> Arcs = {
 739       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 740       {"7", "5"}, {"2", "8"}, {"8", "11"}, {"11", "12"}, {"12", "10"},
 741       {"10", "9"}, {"9", "10"}};
 742
 743   std::vector<CFGBuilder::Update> Updates = {{Insert, {"10", "7"}}};
 744   CFGBuilder B(Holder.F, Arcs, Updates);
 745   DominatorTree DT(*Holder.F);
 746   EXPECT_TRUE(DT.verify());
 747   PostDominatorTree PDT(*Holder.F);
 748   EXPECT_TRUE(PDT.verify());
 749
 750   std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
 751   EXPECT_TRUE(LastUpdate);
 752
 753   EXPECT_EQ(LastUpdate->Action, Insert);
 754   BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 755   BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 756   DT.insertEdge(From, To);
 757   EXPECT_TRUE(DT.verify());
 758   PDT.insertEdge(From, To);
 759   EXPECT_TRUE(PDT.verify());
 760 }
 761
 762 TEST(DominatorTree, InsertUnreachable) {
 763   CFGHolder Holder;
 764   std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"},  {"2", "3"},  {"3", "4"},
 765                                        {"5", "6"},  {"5", "7"},  {"3", "8"},
 766                                        {"9", "10"}, {"11", "12"}};
 767
 768   std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
 769                                              {Insert, {"8", "9"}},
 770                                              {Insert, {"10", "12"}},
 771                                              {Insert, {"10", "11"}}};
 772   CFGBuilder B(Holder.F, Arcs, Updates);
 773   DominatorTree DT(*Holder.F);
 774   EXPECT_TRUE(DT.verify());
 775   PostDominatorTree PDT(*Holder.F);
 776   EXPECT_TRUE(PDT.verify());
 777
 778   std::optional<CFGBuilder::Update> LastUpdate;
 779   while ((LastUpdate = B.applyUpdate())) {
 780     EXPECT_EQ(LastUpdate->Action, Insert);
 781     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 782     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 783     DT.insertEdge(From, To);
 784     EXPECT_TRUE(DT.verify());
 785     PDT.insertEdge(From, To);
 786     EXPECT_TRUE(PDT.verify());
 787   }
 788 }
 789
 790 TEST(DominatorTree, InsertFromUnreachable) {
 791   CFGHolder Holder;
 792   std::vector<CFGBuilder::Arc> Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}};
 793
 794   std::vector<CFGBuilder::Update> Updates = {{Insert, {"3", "5"}}};
 795   CFGBuilder B(Holder.F, Arcs, Updates);
 796   PostDominatorTree PDT(*Holder.F);
 797   EXPECT_TRUE(PDT.verify());
 798
 799   std::optional<CFGBuilder::Update> LastUpdate = B.applyUpdate();
 800   EXPECT_TRUE(LastUpdate);
 801
 802   EXPECT_EQ(LastUpdate->Action, Insert);
 803   BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 804   BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 805   PDT.insertEdge(From, To);
 806   EXPECT_TRUE(PDT.verify());
 807   EXPECT_EQ(PDT.root_size(), 2UL);
 808   // Make sure we can use a const pointer with getNode.
 809   const BasicBlock *BB5 = B.getOrAddBlock("5");
 810   EXPECT_NE(PDT.getNode(BB5), nullptr);
 811 }
 812
 813 TEST(DominatorTree, InsertMixed) {
 814   CFGHolder Holder;
 815   std::vector<CFGBuilder::Arc> Arcs = {
 816       {"1", "2"}, {"2", "3"},  {"3", "4"},  {"5", "6"},   {"5", "7"},
 817       {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
 818
 819   std::vector<CFGBuilder::Update> Updates = {
 820       {Insert, {"4", "5"}},   {Insert, {"2", "5"}},   {Insert, {"10", "9"}},
 821       {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}},
 822       {Insert, {"7", "5"}}};
 823   CFGBuilder B(Holder.F, Arcs, Updates);
 824   DominatorTree DT(*Holder.F);
 825   EXPECT_TRUE(DT.verify());
 826   PostDominatorTree PDT(*Holder.F);
 827   EXPECT_TRUE(PDT.verify());
 828
 829   std::optional<CFGBuilder::Update> LastUpdate;
 830   while ((LastUpdate = B.applyUpdate())) {
 831     EXPECT_EQ(LastUpdate->Action, Insert);
 832     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 833     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 834     DT.insertEdge(From, To);
 835     EXPECT_TRUE(DT.verify());
 836     PDT.insertEdge(From, To);
 837     EXPECT_TRUE(PDT.verify());
 838   }
 839 }
 840
 841 TEST(DominatorTree, InsertPermut) {
 842   std::vector<CFGBuilder::Arc> Arcs = {
 843       {"1", "2"}, {"2", "3"},  {"3", "4"},  {"5", "6"},   {"5", "7"},
 844       {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}};
 845
 846   std::vector<CFGBuilder::Update> Updates = {{Insert, {"4", "5"}},
 847                                              {Insert, {"2", "5"}},
 848                                              {Insert, {"10", "9"}},
 849                                              {Insert, {"12", "10"}}};
 850
 851   while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) {
 852     CFGHolder Holder;
 853     CFGBuilder B(Holder.F, Arcs, Updates);
 854     DominatorTree DT(*Holder.F);
 855     EXPECT_TRUE(DT.verify());
 856     PostDominatorTree PDT(*Holder.F);
 857     EXPECT_TRUE(PDT.verify());
 858
 859     std::optional<CFGBuilder::Update> LastUpdate;
 860     while ((LastUpdate = B.applyUpdate())) {
 861       EXPECT_EQ(LastUpdate->Action, Insert);
 862       BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 863       BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 864       DT.insertEdge(From, To);
 865       EXPECT_TRUE(DT.verify());
 866       PDT.insertEdge(From, To);
 867       EXPECT_TRUE(PDT.verify());
 868     }
 869   }
 870 }
 871
 872 TEST(DominatorTree, DeleteReachable) {
 873   CFGHolder Holder;
 874   std::vector<CFGBuilder::Arc> Arcs = {
 875       {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"},  {"5", "6"},
 876       {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
 877
 878   std::vector<CFGBuilder::Update> Updates = {
 879       {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}};
 880   CFGBuilder B(Holder.F, Arcs, Updates);
 881   DominatorTree DT(*Holder.F);
 882   EXPECT_TRUE(DT.verify());
 883   PostDominatorTree PDT(*Holder.F);
 884   EXPECT_TRUE(PDT.verify());
 885
 886   std::optional<CFGBuilder::Update> LastUpdate;
 887   while ((LastUpdate = B.applyUpdate())) {
 888     EXPECT_EQ(LastUpdate->Action, Delete);
 889     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 890     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 891     DT.deleteEdge(From, To);
 892     EXPECT_TRUE(DT.verify());
 893     PDT.deleteEdge(From, To);
 894     EXPECT_TRUE(PDT.verify());
 895   }
 896 }
 897
 898 TEST(DominatorTree, DeleteUnreachable) {
 899   CFGHolder Holder;
 900   std::vector<CFGBuilder::Arc> Arcs = {
 901       {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"},  {"5", "6"}, {"5", "7"},
 902       {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}};
 903
 904   std::vector<CFGBuilder::Update> Updates = {
 905       {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}};
 906   CFGBuilder B(Holder.F, Arcs, Updates);
 907   DominatorTree DT(*Holder.F);
 908   EXPECT_TRUE(DT.verify());
 909   PostDominatorTree PDT(*Holder.F);
 910   EXPECT_TRUE(PDT.verify());
 911
 912   std::optional<CFGBuilder::Update> LastUpdate;
 913   while ((LastUpdate = B.applyUpdate())) {
 914     EXPECT_EQ(LastUpdate->Action, Delete);
 915     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 916     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 917     DT.deleteEdge(From, To);
 918     EXPECT_TRUE(DT.verify());
 919     PDT.deleteEdge(From, To);
 920     EXPECT_TRUE(PDT.verify());
 921   }
 922 }
 923
 924 TEST(DominatorTree, InsertDelete) {
 925   std::vector<CFGBuilder::Arc> Arcs = {
 926       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 927       {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
 928
 929   std::vector<CFGBuilder::Update> Updates = {
 930       {Insert, {"2", "4"}},  {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
 931       {Insert, {"7", "6"}},  {Insert, {"7", "5"}},   {Delete, {"3", "8"}},
 932       {Insert, {"10", "7"}}, {Insert, {"2", "8"}},   {Delete, {"3", "4"}},
 933       {Delete, {"8", "9"}},  {Delete, {"11", "12"}}};
 934
 935   CFGHolder Holder;
 936   CFGBuilder B(Holder.F, Arcs, Updates);
 937   DominatorTree DT(*Holder.F);
 938   EXPECT_TRUE(DT.verify());
 939   PostDominatorTree PDT(*Holder.F);
 940   EXPECT_TRUE(PDT.verify());
 941
 942   std::optional<CFGBuilder::Update> LastUpdate;
 943   while ((LastUpdate = B.applyUpdate())) {
 944     BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 945     BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 946     if (LastUpdate->Action == Insert) {
 947       DT.insertEdge(From, To);
 948       PDT.insertEdge(From, To);
 949     } else {
 950       DT.deleteEdge(From, To);
 951       PDT.deleteEdge(From, To);
 952     }
 953
 954     EXPECT_TRUE(DT.verify());
 955     EXPECT_TRUE(PDT.verify());
 956   }
 957 }
 958
 959 TEST(DominatorTree, InsertDeleteExhaustive) {
 960   std::vector<CFGBuilder::Arc> Arcs = {
 961       {"1", "2"}, {"2", "3"}, {"3", "4"},  {"4", "5"},  {"5", "6"},  {"5", "7"},
 962       {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};
 963
 964   std::vector<CFGBuilder::Update> Updates = {
 965       {Insert, {"2", "4"}},  {Insert, {"12", "10"}}, {Insert, {"10", "9"}},
 966       {Insert, {"7", "6"}},  {Insert, {"7", "5"}},   {Delete, {"3", "8"}},
 967       {Insert, {"10", "7"}}, {Insert, {"2", "8"}},   {Delete, {"3", "4"}},
 968       {Delete, {"8", "9"}},  {Delete, {"11", "12"}}};
 969
 970   std::mt19937 Generator(0);
 971   for (unsigned i = 0; i < 16; ++i) {
 972     std::shuffle(Updates.begin(), Updates.end(), Generator);
 973     CFGHolder Holder;
 974     CFGBuilder B(Holder.F, Arcs, Updates);
 975     DominatorTree DT(*Holder.F);
 976     EXPECT_TRUE(DT.verify());
 977     PostDominatorTree PDT(*Holder.F);
 978     EXPECT_TRUE(PDT.verify());
 979
 980     std::optional<CFGBuilder::Update> LastUpdate;
 981     while ((LastUpdate = B.applyUpdate())) {
 982       BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From);
 983       BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To);
 984       if (LastUpdate->Action == Insert) {
 985         DT.insertEdge(From, To);
 986         PDT.insertEdge(From, To);
 987       } else {
 988         DT.deleteEdge(From, To);
 989         PDT.deleteEdge(From, To);
 990       }
 991
 992       EXPECT_TRUE(DT.verify());
 993       EXPECT_TRUE(PDT.verify());
 994     }
 995   }
 996 }
 997
 998 TEST(DominatorTree, InsertIntoIrreducible) {
 999   std::vector<CFGBuilder::Arc> Arcs = {
1000       {"0", "1"},
1001       {"1", "27"}, {"1", "7"},
1002       {"10", "18"},
1003       {"13", "10"},
1004       {"18", "13"}, {"18", "23"},
1005       {"23", "13"}, {"23", "24"},
1006       {"24", "1"}, {"24", "18"},
1007       {"27", "24"}};
1008
1009   CFGHolder Holder;
1010   CFGBuilder B(Holder.F, Arcs, {{Insert, {"7", "23"}}});
1011   DominatorTree DT(*Holder.F);
1012   EXPECT_TRUE(DT.verify());
1013
1014   B.applyUpdate();
1015   BasicBlock *From = B.getOrAddBlock("7");
1016   BasicBlock *To = B.getOrAddBlock("23");
1017   DT.insertEdge(From, To);
1018
1019   EXPECT_TRUE(DT.verify());
1020 }
1021
1022 TEST(DominatorTree, EdgeDomination) {
1023   StringRef ModuleString = "define i32 @f(i1 %cond) {\n"
1024                            " bb0:\n"
1025                            "   br i1 %cond, label %bb1, label %bb2\n"
1026                            " bb1:\n"
1027                            "   br label %bb3\n"
1028                            " bb2:\n"
1029                            "   br label %bb3\n"
1030                            " bb3:\n"
1031                            "   ret i32 4"
1032                            "}\n";
1033
1034   // Parse the module.
1035   LLVMContext Context;
1036   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1037
1038   runWithDomTree(*M, "f",
1039                  [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
1040     Function::iterator FI = F.begin();
1041
1042     BasicBlock *BB0 = &*FI++;
1043     BasicBlock *BB1 = &*FI++;
1044     BasicBlock *BB2 = &*FI++;
1045     BasicBlock *BB3 = &*FI++;
1046
1047     BasicBlockEdge E01(BB0, BB1);
1048     BasicBlockEdge E02(BB0, BB2);
1049     BasicBlockEdge E13(BB1, BB3);
1050     BasicBlockEdge E23(BB2, BB3);
1051
1052     EXPECT_TRUE(DT->dominates(E01, E01));
1053     EXPECT_FALSE(DT->dominates(E01, E02));
1054     EXPECT_TRUE(DT->dominates(E01, E13));
1055     EXPECT_FALSE(DT->dominates(E01, E23));
1056
1057     EXPECT_FALSE(DT->dominates(E02, E01));
1058     EXPECT_TRUE(DT->dominates(E02, E02));
1059     EXPECT_FALSE(DT->dominates(E02, E13));
1060     EXPECT_TRUE(DT->dominates(E02, E23));
1061
1062     EXPECT_FALSE(DT->dominates(E13, E01));
1063     EXPECT_FALSE(DT->dominates(E13, E02));
1064     EXPECT_TRUE(DT->dominates(E13, E13));
1065     EXPECT_FALSE(DT->dominates(E13, E23));
1066
1067     EXPECT_FALSE(DT->dominates(E23, E01));
1068     EXPECT_FALSE(DT->dominates(E23, E02));
1069     EXPECT_FALSE(DT->dominates(E23, E13));
1070     EXPECT_TRUE(DT->dominates(E23, E23));
1071   });
1072 }
1073
1074 TEST(DominatorTree, ValueDomination) {
1075   StringRef ModuleString = R"(
1076     @foo = global i8 0
1077     define i8 @f(i8 %arg) {
1078       ret i8 %arg
1079     }
1080   )";
1081
1082   LLVMContext Context;
1083   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1084
1085   runWithDomTree(*M, "f",
1086                  [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
1087     Argument *A = F.getArg(0);
1088     GlobalValue *G = M->getNamedValue("foo");
1089     Constant *C = ConstantInt::getNullValue(Type::getInt8Ty(Context));
1090
1091     Instruction *I = F.getEntryBlock().getTerminator();
1092     EXPECT_TRUE(DT->dominates(A, I));
1093     EXPECT_TRUE(DT->dominates(G, I));
1094     EXPECT_TRUE(DT->dominates(C, I));
1095
1096     const Use &U = I->getOperandUse(0);
1097     EXPECT_TRUE(DT->dominates(A, U));
1098     EXPECT_TRUE(DT->dominates(G, U));
1099     EXPECT_TRUE(DT->dominates(C, U));
1100   });
1101 }
1102 TEST(DominatorTree, CallBrDomination) {
1103   StringRef ModuleString = R"(
1104 define void @x() {
1105   %y = alloca i32
1106   %w = callbr i32 asm "", "=r,!i"()
1107           to label %asm.fallthrough [label %z]
1108
1109 asm.fallthrough:
1110   br label %cleanup
1111
1112 z:
1113   store i32 %w, ptr %y
1114   br label %cleanup
1115
1116 cleanup:
1117   ret void
1118 })";
1119
1120   LLVMContext Context;
1121   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1122
1123   runWithDomTree(
1124       *M, "x", [&](Function &F, DominatorTree *DT, PostDominatorTree *PDT) {
1125         Function::iterator FI = F.begin();
1126
1127         BasicBlock *Entry = &*FI++;
1128         BasicBlock *ASMFallthrough = &*FI++;
1129         BasicBlock *Z = &*FI++;
1130
1131         EXPECT_TRUE(DT->dominates(Entry, ASMFallthrough));
1132         EXPECT_TRUE(DT->dominates(Entry, Z));
1133
1134         BasicBlock::iterator BBI = Entry->begin();
1135         ++BBI;
1136         Instruction &I = *BBI;
1137         EXPECT_TRUE(isa<CallBrInst>(I));
1138         EXPECT_TRUE(isa<Value>(I));
1139         for (const User *U : I.users()) {
1140           EXPECT_TRUE(isa<Instruction>(U));
1141           EXPECT_TRUE(DT->dominates(cast<Value>(&I), cast<Instruction>(U)));
1142         }
1143       });
1144 }