unittests/Analysis/DomTreeUpdaterTest.cpp

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