unittests/IR/DomTreeUpdaterTest.cpp

   1 //==- llvm/unittests/IR/DomTreeUpdaterTest.cpp - DomTreeUpdater unit tests ===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/IR/DomTreeUpdater.h"
  11 #include "llvm/Analysis/PostDominators.h"
  12 #include "llvm/AsmParser/Parser.h"
  13 #include "llvm/IR/Constants.h"
  14 #include "llvm/IR/Dominators.h"
  15 #include "llvm/IR/Instructions.h"
  16 #include "llvm/IR/LLVMContext.h"
  17 #include "llvm/IR/Module.h"
  18 #include "llvm/Support/SourceMgr.h"
  19 #include "gtest/gtest.h"
  20 #include <algorithm>
  21
  22 using namespace llvm;
  23
  24 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
  25                                               StringRef ModuleStr) {
  26   SMDiagnostic Err;
  27   std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
  28   assert(M && "Bad LLVM IR?");
  29   return M;
  30 }
  31
  32 TEST(DomTreeUpdater, EagerUpdateBasicOperations) {
  33   StringRef FuncName = "f";
  34   StringRef ModuleString = R"(
  35                           define i32 @f(i32 %i, i32 *%p) {
  36                           bb0:
  37                              store i32 %i, i32 *%p
  38                              switch i32 %i, label %bb1 [
  39                                i32 1, label %bb2
  40                                i32 2, label %bb3
  41                              ]
  42                           bb1:
  43                              ret i32 1
  44                           bb2:
  45                              ret i32 2
  46                           bb3:
  47                              ret i32 3
  48                           })";
  49   // Make the module.
  50   LLVMContext Context;
  51   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
  52   Function *F = M->getFunction(FuncName);
  53
  54   // Make the DomTreeUpdater.
  55   DominatorTree DT(*F);
  56   PostDominatorTree PDT(*F);
  57   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
  58
  59   ASSERT_TRUE(DTU.hasDomTree());
  60   ASSERT_TRUE(DTU.hasPostDomTree());
  61   ASSERT_TRUE(DTU.isEager());
  62   ASSERT_FALSE(DTU.isLazy());
  63   ASSERT_TRUE(DTU.getDomTree().verify());
  64   ASSERT_TRUE(DTU.getPostDomTree().verify());
  65   ASSERT_FALSE(DTU.hasPendingUpdates());
  66
  67   Function::iterator FI = F->begin();
  68   BasicBlock *BB0 = &*FI++;
  69   BasicBlock *BB1 = &*FI++;
  70   BasicBlock *BB2 = &*FI++;
  71   BasicBlock *BB3 = &*FI++;
  72   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
  73   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
  74
  75   DTU.insertEdgeRelaxed(BB0, BB0);
  76   DTU.deleteEdgeRelaxed(BB0, BB0);
  77
  78   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
  79   // entries are discarded.
  80   std::vector<DominatorTree::UpdateType> Updates;
  81   Updates.reserve(4);
  82   Updates.push_back({DominatorTree::Delete, BB0, BB3});
  83   Updates.push_back({DominatorTree::Delete, BB0, BB3});
  84
  85   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
  86   Updates.push_back({DominatorTree::Insert, BB1, BB2});
  87   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
  88   Updates.push_back({DominatorTree::Delete, BB0, BB1});
  89
  90   // CFG Change: remove edge bb0 -> bb3.
  91   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
  92   BB3->removePredecessor(BB0);
  93   for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
  94     if (i->getCaseSuccessor() == BB3) {
  95       SI->removeCase(i);
  96       break;
  97     }
  98   }
  99   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 100   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 101   // contained Instructions and change the Terminator to "unreachable" when
 102   // queued for deletion.
 103   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 104   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 105   DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
 106   ASSERT_FALSE(DTU.hasPendingUpdates());
 107
 108   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
 109   DTU.insertEdgeRelaxed(BB1, BB2);
 110   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
 111   DTU.deleteEdgeRelaxed(BB0, BB1);
 112
 113   // DTU working with Eager UpdateStrategy does not need to flush.
 114   ASSERT_TRUE(DT.verify());
 115   ASSERT_TRUE(PDT.verify());
 116
 117   // Test callback utils.
 118   ASSERT_EQ(BB3->getParent(), F);
 119   DTU.callbackDeleteBB(BB3,
 120                        [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); });
 121
 122   ASSERT_TRUE(DT.verify());
 123   ASSERT_TRUE(PDT.verify());
 124   ASSERT_FALSE(DTU.hasPendingUpdates());
 125
 126   // Unnecessary flush() test
 127   DTU.flush();
 128   EXPECT_TRUE(DT.verify());
 129   EXPECT_TRUE(PDT.verify());
 130
 131   // Remove all case branch to BB2 to test Eager recalculation.
 132   // Code section from llvm::ConstantFoldTerminator
 133   for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
 134     if (i->getCaseSuccessor() == BB2) {
 135       // Remove this entry.
 136       BB2->removePredecessor(BB0);
 137       i = SI->removeCase(i);
 138       e = SI->case_end();
 139     } else
 140       ++i;
 141   }
 142   ASSERT_FALSE(DT.verify());
 143   ASSERT_FALSE(PDT.verify());
 144   DTU.recalculate(*F);
 145   ASSERT_TRUE(DT.verify());
 146   ASSERT_TRUE(PDT.verify());
 147 }
 148
 149 TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) {
 150   StringRef FuncName = "f";
 151   StringRef ModuleString = R"(
 152                            define i32 @f() {
 153                            bb0:
 154                               br label %bb1
 155                             bb1:
 156                               ret i32 1
 157                            }
 158                            )";
 159   // Make the module.
 160   LLVMContext Context;
 161   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 162   Function *F = M->getFunction(FuncName);
 163
 164   // Make the DTU.
 165   DominatorTree DT(*F);
 166   PostDominatorTree PDT(*F);
 167   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager);
 168   ASSERT_TRUE(DTU.hasDomTree());
 169   ASSERT_TRUE(DTU.hasPostDomTree());
 170   ASSERT_TRUE(DTU.isEager());
 171   ASSERT_FALSE(DTU.isLazy());
 172   ASSERT_TRUE(DT.verify());
 173   ASSERT_TRUE(PDT.verify());
 174
 175   Function::iterator FI = F->begin();
 176   BasicBlock *BB0 = &*FI++;
 177   BasicBlock *BB1 = &*FI++;
 178
 179   // Add a block as the new function entry BB. We also link it to BB0.
 180   BasicBlock *NewEntry =
 181       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
 182   BranchInst::Create(BB0, NewEntry);
 183   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
 184   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 185
 186   DTU.insertEdgeRelaxed(NewEntry, BB0);
 187
 188   // Changing the Entry BB requires a full recalculation of DomTree.
 189   DTU.recalculate(*F);
 190   ASSERT_TRUE(DT.verify());
 191   ASSERT_TRUE(PDT.verify());
 192
 193   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
 194   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
 195   NewEntry->getTerminator()->eraseFromParent();
 196   BranchInst::Create(BB1, NewEntry);
 197   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 198
 199   // Update the DTU. At this point bb0 now has no predecessors but is still a
 200   // Child of F.
 201   DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
 202                     {DominatorTree::Insert, NewEntry, BB1}});
 203   ASSERT_TRUE(DT.verify());
 204   ASSERT_TRUE(PDT.verify());
 205
 206   // Now remove bb0 from F.
 207   ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
 208   EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
 209   DTU.deleteBB(BB0);
 210   ASSERT_TRUE(DT.verify());
 211   ASSERT_TRUE(PDT.verify());
 212 }
 213
 214 TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) {
 215   StringRef FuncName = "f";
 216   StringRef ModuleString = R"(
 217                            define i32 @f(i32 %i, i32 *%p) {
 218                             bb0:
 219                               store i32 %i, i32 *%p
 220                               switch i32 %i, label %bb1 [
 221                                 i32 0, label %bb2
 222                                 i32 1, label %bb2
 223                                 i32 2, label %bb3
 224                               ]
 225                             bb1:
 226                               ret i32 1
 227                             bb2:
 228                               ret i32 2
 229                             bb3:
 230                               ret i32 3
 231                            }
 232                            )";
 233   // Make the module.
 234   LLVMContext Context;
 235   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 236   Function *F = M->getFunction(FuncName);
 237
 238   // Make the DTU.
 239   DominatorTree DT(*F);
 240   PostDominatorTree *PDT = nullptr;
 241   DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 242   ASSERT_TRUE(DTU.hasDomTree());
 243   ASSERT_FALSE(DTU.hasPostDomTree());
 244   ASSERT_FALSE(DTU.isEager());
 245   ASSERT_TRUE(DTU.isLazy());
 246   ASSERT_TRUE(DTU.getDomTree().verify());
 247
 248   Function::iterator FI = F->begin();
 249   BasicBlock *BB0 = &*FI++;
 250   BasicBlock *BB1 = &*FI++;
 251   BasicBlock *BB2 = &*FI++;
 252   BasicBlock *BB3 = &*FI++;
 253
 254   // Test discards of self-domination update.
 255   DTU.deleteEdge(BB0, BB0);
 256   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 257
 258   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
 259   // entries are discarded.
 260   std::vector<DominatorTree::UpdateType> Updates;
 261   Updates.reserve(4);
 262   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 263   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 264
 265   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
 266   Updates.push_back({DominatorTree::Insert, BB1, BB2});
 267   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
 268   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 269
 270   // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
 271   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
 272   BB0->getTerminator()->eraseFromParent();
 273   BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
 274   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 275
 276   // Verify. Updates to DTU must be applied *after* all changes to the CFG
 277   // (including block deletion).
 278   DTU.applyUpdates(Updates);
 279   ASSERT_TRUE(DTU.getDomTree().verify());
 280
 281   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 282   // contained Instructions and change the Terminator to "unreachable" when
 283   // queued for deletion. Its parent is still F until all the pending updates
 284   // are applied to all trees held by the DomTreeUpdater (DomTree/PostDomTree).
 285   // We don't defer this action because it can cause problems for other
 286   // transforms or analysis as it's part of the actual CFG. We only defer
 287   // updates to the DominatorTrees. This code will crash if it is placed before
 288   // the BranchInst::Create() call above. After a deletion of a BasicBlock. Only
 289   // an explicit flush event can trigger the flushing of deleteBBs. Because some
 290   // passes using Lazy UpdateStrategy rely on this behavior.
 291
 292   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 293   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 294   EXPECT_FALSE(DTU.hasPendingDeletedBB());
 295   DTU.deleteBB(BB3);
 296   EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
 297   EXPECT_TRUE(DTU.hasPendingDeletedBB());
 298   ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
 299   EXPECT_EQ(BB3->getParent(), F);
 300   DTU.recalculate(*F);
 301   EXPECT_FALSE(DTU.hasPendingDeletedBB());
 302 }
 303
 304 TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) {
 305   StringRef FuncName = "f";
 306   StringRef ModuleString = R"(
 307                            define i32 @f(i32 %i, i32 *%p) {
 308                             bb0:
 309                               store i32 %i, i32 *%p
 310                               switch i32 %i, label %bb1 [
 311                                 i32 2, label %bb2
 312                                 i32 3, label %bb3
 313                               ]
 314                             bb1:
 315                               br label %bb3
 316                             bb2:
 317                               br label %bb3
 318                             bb3:
 319                               ret i32 3
 320                            }
 321                            )";
 322   // Make the module.
 323   LLVMContext Context;
 324   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 325   Function *F = M->getFunction(FuncName);
 326
 327   // Make the DTU.
 328   DominatorTree DT(*F);
 329   PostDominatorTree *PDT = nullptr;
 330   DomTreeUpdater DTU(&DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 331   ASSERT_TRUE(DTU.hasDomTree());
 332   ASSERT_FALSE(DTU.hasPostDomTree());
 333   ASSERT_FALSE(DTU.isEager());
 334   ASSERT_TRUE(DTU.isLazy());
 335   ASSERT_TRUE(DTU.getDomTree().verify());
 336
 337   Function::iterator FI = F->begin();
 338   BasicBlock *BB0 = &*FI++;
 339   BasicBlock *BB1 = &*FI++;
 340   BasicBlock *BB2 = &*FI++;
 341   BasicBlock *BB3 = &*FI++;
 342
 343   // There are several CFG locations where we have:
 344   //
 345   //   pred1..predN
 346   //    |        |
 347   //    +> curr <+    converted into:   pred1..predN curr
 348   //        |                            |        |
 349   //        v                            +> succ <+
 350   //       succ
 351   //
 352   // There is a specific shape of this we have to be careful of:
 353   //
 354   //   pred1..predN
 355   //   ||        |
 356   //   |+> curr <+    converted into:   pred1..predN curr
 357   //   |    |                            |        |
 358   //   |    v                            +> succ <+
 359   //   +-> succ
 360   //
 361   // While the final CFG form is functionally identical the updates to
 362   // DTU are not. In the first case we must have DTU.insertEdge(Pred1, Succ)
 363   // while in the latter case we must *NOT* have DTU.insertEdge(Pred1, Succ).
 364
 365   // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
 366   // remove bb2.
 367   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
 368   BB0->getTerminator()->eraseFromParent();
 369   BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
 370   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 371
 372   // Test callback utils.
 373   std::vector<BasicBlock *> BasicBlocks;
 374   BasicBlocks.push_back(BB1);
 375   BasicBlocks.push_back(BB2);
 376   auto Eraser = [&](BasicBlock *BB) {
 377     BasicBlocks.erase(
 378         std::remove_if(BasicBlocks.begin(), BasicBlocks.end(),
 379                        [&](const BasicBlock *i) { return i == BB; }),
 380         BasicBlocks.end());
 381   };
 382   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
 383   // Remove bb2 from F. This has to happen before the call to applyUpdates() for
 384   // DTU to detect there is no longer an edge between bb2 -> bb3. The deleteBB()
 385   // method converts bb2's TI into "unreachable".
 386   ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
 387   EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
 388   DTU.callbackDeleteBB(BB2, Eraser);
 389   EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
 390   ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
 391   EXPECT_EQ(BB2->getParent(), F);
 392
 393   // Queue up the DTU updates.
 394   std::vector<DominatorTree::UpdateType> Updates;
 395   Updates.reserve(4);
 396   Updates.push_back({DominatorTree::Delete, BB0, BB2});
 397   Updates.push_back({DominatorTree::Delete, BB2, BB3});
 398
 399   // Handle the specific shape case next.
 400   // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
 401   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 402   BB0->getTerminator()->eraseFromParent();
 403   BranchInst::Create(BB3, BB0);
 404   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 405
 406   // Remove bb1 from F. This has to happen before the call to applyUpdates() for
 407   // DTU to detect there is no longer an edge between bb1 -> bb3. The deleteBB()
 408   // method converts bb1's TI into "unreachable".
 409   ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
 410   EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
 411   DTU.callbackDeleteBB(BB1, Eraser);
 412   EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
 413   ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
 414   EXPECT_EQ(BB1->getParent(), F);
 415
 416   // Update the DTU. In this case we don't call DTU.insertEdge(BB0, BB3) because
 417   // the edge previously existed at the start of this test when DT was first
 418   // created.
 419   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 420   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 421
 422   // Verify everything.
 423   DTU.applyUpdates(Updates);
 424   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
 425   DTU.flush();
 426   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
 427   ASSERT_TRUE(DT.verify());
 428 }
 429
 430 TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
 431   StringRef FuncName = "f";
 432   StringRef ModuleString = R"(
 433                            define i32 @f(i32 %i, i32 *%p) {
 434                             bb0:
 435                               store i32 %i, i32 *%p
 436                               switch i32 %i, label %bb1 [
 437                                 i32 0, label %bb2
 438                                 i32 1, label %bb2
 439                                 i32 2, label %bb3
 440                               ]
 441                             bb1:
 442                               ret i32 1
 443                             bb2:
 444                               ret i32 2
 445                             bb3:
 446                               ret i32 3
 447                            }
 448                            )";
 449   // Make the module.
 450   LLVMContext Context;
 451   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 452   Function *F = M->getFunction(FuncName);
 453
 454   // Make the DTU.
 455   DominatorTree DT(*F);
 456   PostDominatorTree PDT(*F);
 457   DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 458   ASSERT_TRUE(DTU.hasDomTree());
 459   ASSERT_TRUE(DTU.hasPostDomTree());
 460   ASSERT_FALSE(DTU.isEager());
 461   ASSERT_TRUE(DTU.isLazy());
 462   ASSERT_TRUE(DTU.getDomTree().verify());
 463   ASSERT_TRUE(DTU.getPostDomTree().verify());
 464
 465   Function::iterator FI = F->begin();
 466   BasicBlock *BB0 = &*FI++;
 467   BasicBlock *BB1 = &*FI++;
 468   BasicBlock *BB2 = &*FI++;
 469   BasicBlock *BB3 = &*FI++;
 470   // Test discards of self-domination update.
 471   DTU.deleteEdge(BB0, BB0);
 472
 473   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
 474   // entries are discarded.
 475   std::vector<DominatorTree::UpdateType> Updates;
 476   Updates.reserve(4);
 477   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 478   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 479
 480   // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
 481   Updates.push_back({DominatorTree::Insert, BB1, BB2});
 482   // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
 483   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 484
 485   // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
 486   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
 487   BB0->getTerminator()->eraseFromParent();
 488   BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
 489   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 490
 491   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 492   // contained Instructions and change the Terminator to "unreachable" when
 493   // queued for deletion. Its parent is still F until DTU.flushDomTree is
 494   // called. We don't defer this action because it can cause problems for other
 495   // transforms or analysis as it's part of the actual CFG. We only defer
 496   // updates to the DominatorTree. This code will crash if it is placed before
 497   // the BranchInst::Create() call above.
 498   bool CallbackFlag = false;
 499   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 500   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 501   DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });
 502   EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
 503   ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
 504   EXPECT_EQ(BB3->getParent(), F);
 505
 506   // Verify. Updates to DTU must be applied *after* all changes to the CFG
 507   // (including block deletion).
 508   DTU.applyUpdates(Updates);
 509   ASSERT_TRUE(DTU.getDomTree().verify());
 510   ASSERT_TRUE(DTU.hasPendingUpdates());
 511   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
 512   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 513   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 514   ASSERT_TRUE(DTU.getPostDomTree().verify());
 515   ASSERT_FALSE(DTU.hasPendingUpdates());
 516   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
 517   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 518   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 519   ASSERT_EQ(CallbackFlag, true);
 520 }
 521
 522 TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
 523   StringRef FuncName = "f";
 524   StringRef ModuleString = R"(
 525                            define i32 @f() {
 526                            bb0:
 527                               br label %bb1
 528                             bb1:
 529                               ret i32 1
 530                            }
 531                            )";
 532   // Make the module.
 533   LLVMContext Context;
 534   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 535   Function *F = M->getFunction(FuncName);
 536
 537   // Make the DTU.
 538   DominatorTree DT(*F);
 539   PostDominatorTree PDT(*F);
 540   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 541   ASSERT_TRUE(DTU.hasDomTree());
 542   ASSERT_TRUE(DTU.hasPostDomTree());
 543   ASSERT_FALSE(DTU.isEager());
 544   ASSERT_TRUE(DTU.isLazy());
 545   ASSERT_TRUE(DTU.getDomTree().verify());
 546   ASSERT_TRUE(DTU.getPostDomTree().verify());
 547
 548   Function::iterator FI = F->begin();
 549   BasicBlock *BB0 = &*FI++;
 550   BasicBlock *BB1 = &*FI++;
 551
 552   // Add a block as the new function entry BB. We also link it to BB0.
 553   BasicBlock *NewEntry =
 554       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
 555   BranchInst::Create(BB0, NewEntry);
 556   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
 557   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 558
 559   // Insert the new edge between new_entry -> bb0. Without this the
 560   // recalculate() call below will not actually recalculate the DT as there
 561   // are no changes pending and no blocks deleted.
 562   DTU.insertEdge(NewEntry, BB0);
 563
 564   // Changing the Entry BB requires a full recalculation.
 565   DTU.recalculate(*F);
 566   ASSERT_TRUE(DTU.getDomTree().verify());
 567   ASSERT_TRUE(DTU.getPostDomTree().verify());
 568
 569   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
 570   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
 571   NewEntry->getTerminator()->eraseFromParent();
 572   BranchInst::Create(BB1, NewEntry);
 573   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 574
 575   // Update the DTU. At this point bb0 now has no predecessors but is still a
 576   // Child of F.
 577   DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
 578                     {DominatorTree::Insert, NewEntry, BB1}});
 579   DTU.flush();
 580   ASSERT_TRUE(DT.verify());
 581   ASSERT_TRUE(PDT.verify());
 582
 583   // Now remove bb0 from F.
 584   ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
 585   EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
 586   DTU.deleteBB(BB0);
 587   EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
 588   ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
 589   EXPECT_EQ(BB0->getParent(), F);
 590
 591   // Perform a full recalculation of the DTU. It is not necessary here but we
 592   // do this to test the case when there are no pending DT updates but there are
 593   // pending deleted BBs.
 594   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 595   DTU.recalculate(*F);
 596   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 597 }
 598
 599 TEST(DomTreeUpdater, LazyUpdateStepTest) {
 600   // This test focus on testing a DTU holding both trees applying multiple
 601   // updates and DT/PDT not flushed together.
 602   StringRef FuncName = "f";
 603   StringRef ModuleString = R"(
 604                            define i32 @f(i32 %i, i32 *%p) {
 605                             bb0:
 606                               store i32 %i, i32 *%p
 607                               switch i32 %i, label %bb1 [
 608                                 i32 0, label %bb1
 609                                 i32 1, label %bb2
 610                                 i32 2, label %bb3
 611                                 i32 3, label %bb1
 612                               ]
 613                             bb1:
 614                               ret i32 1
 615                             bb2:
 616                               ret i32 2
 617                             bb3:
 618                               ret i32 3
 619                            }
 620                            )";
 621   // Make the module.
 622   LLVMContext Context;
 623   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 624   Function *F = M->getFunction(FuncName);
 625
 626   // Make the DomTreeUpdater.
 627   DominatorTree DT(*F);
 628   PostDominatorTree PDT(*F);
 629   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 630
 631   ASSERT_TRUE(DTU.hasDomTree());
 632   ASSERT_TRUE(DTU.hasPostDomTree());
 633   ASSERT_FALSE(DTU.isEager());
 634   ASSERT_TRUE(DTU.isLazy());
 635   ASSERT_TRUE(DTU.getDomTree().verify());
 636   ASSERT_TRUE(DTU.getPostDomTree().verify());
 637   ASSERT_FALSE(DTU.hasPendingUpdates());
 638
 639   Function::iterator FI = F->begin();
 640   BasicBlock *BB0 = &*FI++;
 641   FI++;
 642   BasicBlock *BB2 = &*FI++;
 643   BasicBlock *BB3 = &*FI++;
 644   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
 645   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 646
 647   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
 648   // entries are discarded.
 649   std::vector<DominatorTree::UpdateType> Updates;
 650   Updates.reserve(1);
 651   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 652
 653   // CFG Change: remove edge bb0 -> bb3.
 654   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
 655   BB3->removePredecessor(BB0);
 656   for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
 657     if (i->getCaseIndex() == 2) {
 658       SI->removeCase(i);
 659       break;
 660     }
 661   }
 662   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
 663   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 664   // contained Instructions and change the Terminator to "unreachable" when
 665   // queued for deletion.
 666   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 667   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 668   DTU.applyUpdates(Updates);
 669
 670   // Only flush DomTree.
 671   ASSERT_TRUE(DTU.getDomTree().verify());
 672   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
 673   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 674
 675   ASSERT_EQ(BB3->getParent(), F);
 676   DTU.deleteBB(BB3);
 677
 678   Updates.clear();
 679
 680   // Remove all case branch to BB2 to test Eager recalculation.
 681   // Code section from llvm::ConstantFoldTerminator
 682   for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
 683     if (i->getCaseSuccessor() == BB2) {
 684       // Remove this entry.
 685       BB2->removePredecessor(BB0);
 686       i = SI->removeCase(i);
 687       e = SI->case_end();
 688       Updates.push_back({DominatorTree::Delete, BB0, BB2});
 689     } else
 690       ++i;
 691   }
 692
 693   DTU.applyUpdates(Updates);
 694   // flush PostDomTree
 695   ASSERT_TRUE(DTU.getPostDomTree().verify());
 696   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
 697   ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
 698   // flush both trees
 699   DTU.flush();
 700   ASSERT_TRUE(DT.verify());
 701 }
 702
 703 TEST(DomTreeUpdater, NoTreeTest) {
 704   StringRef FuncName = "f";
 705   StringRef ModuleString = R"(
 706                            define i32 @f() {
 707                            bb0:
 708                               ret i32 0
 709                            }
 710                            )";
 711   // Make the module.
 712   LLVMContext Context;
 713   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 714   Function *F = M->getFunction(FuncName);
 715
 716   // Make the DTU.
 717   DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
 718   ASSERT_FALSE(DTU.hasDomTree());
 719   ASSERT_FALSE(DTU.hasPostDomTree());
 720   Function::iterator FI = F->begin();
 721   BasicBlock *BB0 = &*FI++;
 722   // Test whether PendingDeletedBB is flushed after the recalculation.
 723   DTU.deleteBB(BB0);
 724   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 725   DTU.recalculate(*F);
 726   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 727 }