llvm/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.applyUpdatesPermissive(
  75       {{DominatorTree::Insert, BB0, BB0}, {DominatorTree::Delete, BB0, BB0}});
  76   ASSERT_FALSE(DTU.hasPendingUpdates());
  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.applyUpdatesPermissive(Updates);
 106   ASSERT_FALSE(DTU.hasPendingUpdates());
 107
 108   // Invalid Insert: no edge bb1 -> bb2 after change to bb0.
 109   // Invalid Delete: edge exists bb0 -> bb1 after change to bb0.
 110   DTU.applyUpdatesPermissive(
 111       {{DominatorTree::Insert, BB1, BB2}, {DominatorTree::Delete, 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.applyUpdates({{DominatorTree::Insert, 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.applyUpdatesPermissive({{DominatorTree::Insert, 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.applyUpdatesPermissive(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
 363   // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}) while in
 364   // the latter case we must *NOT* have
 365   // DTU.applyUpdates({{DominatorTree::Insert, Pred1, Succ}}).
 366
 367   // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to
 368   // remove bb2.
 369   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
 370   BB0->getTerminator()->eraseFromParent();
 371   BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0);
 372   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 373
 374   // Test callback utils.
 375   std::vector<BasicBlock *> BasicBlocks;
 376   BasicBlocks.push_back(BB1);
 377   BasicBlocks.push_back(BB2);
 378   auto Eraser = [&](BasicBlock *BB) { llvm::erase(BasicBlocks, BB); };
 379   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
 380   // Remove bb2 from F. This has to happen before the call to
 381   // applyUpdates() for DTU to detect there is no longer an edge between
 382   // bb2 -> bb3. The deleteBB() method converts bb2's TI into "unreachable".
 383   ASSERT_FALSE(isa<UnreachableInst>(BB2->getTerminator()));
 384   EXPECT_FALSE(DTU.isBBPendingDeletion(BB2));
 385   DTU.callbackDeleteBB(BB2, Eraser);
 386   EXPECT_TRUE(DTU.isBBPendingDeletion(BB2));
 387   ASSERT_TRUE(isa<UnreachableInst>(BB2->getTerminator()));
 388   EXPECT_EQ(BB2->getParent(), F);
 389
 390   // Queue up the DTU updates.
 391   std::vector<DominatorTree::UpdateType> Updates;
 392   Updates.reserve(4);
 393   Updates.push_back({DominatorTree::Delete, BB0, BB2});
 394   Updates.push_back({DominatorTree::Delete, BB2, BB3});
 395
 396   // Handle the specific shape case next.
 397   // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1.
 398   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 399   BB0->getTerminator()->eraseFromParent();
 400   BranchInst::Create(BB3, BB0);
 401   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 402
 403   // Remove bb1 from F. This has to happen before the call to
 404   // applyUpdates() for DTU to detect there is no longer an edge between
 405   // bb1 -> bb3. The deleteBB() method converts bb1's TI into "unreachable".
 406   ASSERT_FALSE(isa<UnreachableInst>(BB1->getTerminator()));
 407   EXPECT_FALSE(DTU.isBBPendingDeletion(BB1));
 408   DTU.callbackDeleteBB(BB1, Eraser);
 409   EXPECT_TRUE(DTU.isBBPendingDeletion(BB1));
 410   ASSERT_TRUE(isa<UnreachableInst>(BB1->getTerminator()));
 411   EXPECT_EQ(BB1->getParent(), F);
 412
 413   // Update the DTU. In this case we don't submit {DominatorTree::Insert, BB0,
 414   // BB3} because the edge previously existed at the start of this test when DT
 415   // was first created.
 416   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 417   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 418
 419   // Verify everything.
 420   DTU.applyUpdatesPermissive(Updates);
 421   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(2));
 422   DTU.flush();
 423   ASSERT_EQ(BasicBlocks.size(), static_cast<size_t>(0));
 424   ASSERT_TRUE(DT.verify());
 425 }
 426
 427 TEST(DomTreeUpdater, LazyUpdateBasicOperations) {
 428   StringRef FuncName = "f";
 429   StringRef ModuleString = R"(
 430                            define i32 @f(i32 %i, i32 *%p) {
 431                             bb0:
 432                               store i32 %i, i32 *%p
 433                               switch i32 %i, label %bb1 [
 434                                 i32 0, label %bb2
 435                                 i32 1, label %bb2
 436                                 i32 2, label %bb3
 437                               ]
 438                             bb1:
 439                               ret i32 1
 440                             bb2:
 441                               ret i32 2
 442                             bb3:
 443                               ret i32 3
 444                            }
 445                            )";
 446   // Make the module.
 447   LLVMContext Context;
 448   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 449   Function *F = M->getFunction(FuncName);
 450
 451   // Make the DTU.
 452   DominatorTree DT(*F);
 453   PostDominatorTree PDT(*F);
 454   DomTreeUpdater DTU(&DT, &PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 455   ASSERT_TRUE(DTU.hasDomTree());
 456   ASSERT_TRUE(DTU.hasPostDomTree());
 457   ASSERT_FALSE(DTU.isEager());
 458   ASSERT_TRUE(DTU.isLazy());
 459   ASSERT_TRUE(DTU.getDomTree().verify());
 460   ASSERT_TRUE(DTU.getPostDomTree().verify());
 461
 462   Function::iterator FI = F->begin();
 463   BasicBlock *BB0 = &*FI++;
 464   BasicBlock *BB1 = &*FI++;
 465   BasicBlock *BB2 = &*FI++;
 466   BasicBlock *BB3 = &*FI++;
 467   // Test discards of self-domination update.
 468   DTU.applyUpdates({{DominatorTree::Delete, BB0, BB0}});
 469
 470   // Delete edge bb0 -> bb3 and push the update twice to verify duplicate
 471   // entries are discarded.
 472   std::vector<DominatorTree::UpdateType> Updates;
 473   Updates.reserve(4);
 474   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 475   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 476
 477   // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0.
 478   Updates.push_back({DominatorTree::Insert, BB1, BB2});
 479   // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0.
 480   Updates.push_back({DominatorTree::Delete, BB0, BB1});
 481
 482   // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2.
 483   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
 484   BB0->getTerminator()->eraseFromParent();
 485   BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0);
 486   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u);
 487
 488   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 489   // contained Instructions and change the Terminator to "unreachable" when
 490   // queued for deletion. Its parent is still F until DTU.flushDomTree is
 491   // called. We don't defer this action because it can cause problems for other
 492   // transforms or analysis as it's part of the actual CFG. We only defer
 493   // updates to the DominatorTree. This code will crash if it is placed before
 494   // the BranchInst::Create() call above.
 495   bool CallbackFlag = false;
 496   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 497   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 498   DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; });
 499   EXPECT_TRUE(DTU.isBBPendingDeletion(BB3));
 500   ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
 501   EXPECT_EQ(BB3->getParent(), F);
 502
 503   // Verify. Updates to DTU must be applied *after* all changes to the CFG
 504   // (including block deletion).
 505   DTU.applyUpdatesPermissive(Updates);
 506   ASSERT_TRUE(DTU.getDomTree().verify());
 507   ASSERT_TRUE(DTU.hasPendingUpdates());
 508   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
 509   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 510   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 511   ASSERT_TRUE(DTU.getPostDomTree().verify());
 512   ASSERT_FALSE(DTU.hasPendingUpdates());
 513   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
 514   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 515   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 516   ASSERT_EQ(CallbackFlag, true);
 517 }
 518
 519 TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) {
 520   StringRef FuncName = "f";
 521   StringRef ModuleString = R"(
 522                            define i32 @f() {
 523                            bb0:
 524                               br label %bb1
 525                             bb1:
 526                               ret i32 1
 527                            }
 528                            )";
 529   // Make the module.
 530   LLVMContext Context;
 531   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 532   Function *F = M->getFunction(FuncName);
 533
 534   // Make the DTU.
 535   DominatorTree DT(*F);
 536   PostDominatorTree PDT(*F);
 537   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 538   ASSERT_TRUE(DTU.hasDomTree());
 539   ASSERT_TRUE(DTU.hasPostDomTree());
 540   ASSERT_FALSE(DTU.isEager());
 541   ASSERT_TRUE(DTU.isLazy());
 542   ASSERT_TRUE(DTU.getDomTree().verify());
 543   ASSERT_TRUE(DTU.getPostDomTree().verify());
 544
 545   Function::iterator FI = F->begin();
 546   BasicBlock *BB0 = &*FI++;
 547   BasicBlock *BB1 = &*FI++;
 548
 549   // Add a block as the new function entry BB. We also link it to BB0.
 550   BasicBlock *NewEntry =
 551       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
 552   BranchInst::Create(BB0, NewEntry);
 553   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
 554   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 555
 556   // Insert the new edge between new_entry -> bb0. Without this the
 557   // recalculate() call below will not actually recalculate the DT as there
 558   // are no changes pending and no blocks deleted.
 559   DTU.applyUpdates({{DominatorTree::Insert, NewEntry, BB0}});
 560
 561   // Changing the Entry BB requires a full recalculation.
 562   DTU.recalculate(*F);
 563   ASSERT_TRUE(DTU.getDomTree().verify());
 564   ASSERT_TRUE(DTU.getPostDomTree().verify());
 565
 566   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
 567   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
 568   NewEntry->getTerminator()->eraseFromParent();
 569   BranchInst::Create(BB1, NewEntry);
 570   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 571
 572   // Update the DTU. At this point bb0 now has no predecessors but is still a
 573   // Child of F.
 574   DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
 575                     {DominatorTree::Insert, NewEntry, BB1}});
 576   DTU.flush();
 577   ASSERT_TRUE(DT.verify());
 578   ASSERT_TRUE(PDT.verify());
 579
 580   // Now remove bb0 from F.
 581   ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
 582   EXPECT_FALSE(DTU.isBBPendingDeletion(BB0));
 583   DTU.deleteBB(BB0);
 584   EXPECT_TRUE(DTU.isBBPendingDeletion(BB0));
 585   ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
 586   EXPECT_EQ(BB0->getParent(), F);
 587
 588   // Perform a full recalculation of the DTU. It is not necessary here but we
 589   // do this to test the case when there are no pending DT updates but there are
 590   // pending deleted BBs.
 591   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 592   DTU.recalculate(*F);
 593   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 594 }
 595
 596 TEST(DomTreeUpdater, LazyUpdateStepTest) {
 597   // This test focus on testing a DTU holding both trees applying multiple
 598   // updates and DT/PDT not flushed together.
 599   StringRef FuncName = "f";
 600   StringRef ModuleString = R"(
 601                            define i32 @f(i32 %i, i32 *%p) {
 602                             bb0:
 603                               store i32 %i, i32 *%p
 604                               switch i32 %i, label %bb1 [
 605                                 i32 0, label %bb1
 606                                 i32 1, label %bb2
 607                                 i32 2, label %bb3
 608                                 i32 3, label %bb1
 609                               ]
 610                             bb1:
 611                               ret i32 1
 612                             bb2:
 613                               ret i32 2
 614                             bb3:
 615                               ret i32 3
 616                            }
 617                            )";
 618   // Make the module.
 619   LLVMContext Context;
 620   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 621   Function *F = M->getFunction(FuncName);
 622
 623   // Make the DomTreeUpdater.
 624   DominatorTree DT(*F);
 625   PostDominatorTree PDT(*F);
 626   DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy);
 627
 628   ASSERT_TRUE(DTU.hasDomTree());
 629   ASSERT_TRUE(DTU.hasPostDomTree());
 630   ASSERT_FALSE(DTU.isEager());
 631   ASSERT_TRUE(DTU.isLazy());
 632   ASSERT_TRUE(DTU.getDomTree().verify());
 633   ASSERT_TRUE(DTU.getPostDomTree().verify());
 634   ASSERT_FALSE(DTU.hasPendingUpdates());
 635
 636   Function::iterator FI = F->begin();
 637   BasicBlock *BB0 = &*FI++;
 638   FI++;
 639   BasicBlock *BB2 = &*FI++;
 640   BasicBlock *BB3 = &*FI++;
 641   SwitchInst *SI = dyn_cast<SwitchInst>(BB0->getTerminator());
 642   ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst.";
 643
 644   // Delete edge bb0 -> bb3.
 645   std::vector<DominatorTree::UpdateType> Updates;
 646   Updates.reserve(1);
 647   Updates.push_back({DominatorTree::Delete, BB0, BB3});
 648
 649   // CFG Change: remove edge bb0 -> bb3.
 650   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u);
 651   BB3->removePredecessor(BB0);
 652   for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) {
 653     if (i->getCaseIndex() == 2) {
 654       SI->removeCase(i);
 655       break;
 656     }
 657   }
 658   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u);
 659   // Deletion of a BasicBlock is an immediate event. We remove all uses to the
 660   // contained Instructions and change the Terminator to "unreachable" when
 661   // queued for deletion.
 662   ASSERT_FALSE(isa<UnreachableInst>(BB3->getTerminator()));
 663   EXPECT_FALSE(DTU.isBBPendingDeletion(BB3));
 664   DTU.applyUpdates(Updates);
 665
 666   // Only flush DomTree.
 667   ASSERT_TRUE(DTU.getDomTree().verify());
 668   ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates());
 669   ASSERT_FALSE(DTU.hasPendingDomTreeUpdates());
 670
 671   ASSERT_EQ(BB3->getParent(), F);
 672   DTU.deleteBB(BB3);
 673
 674   Updates.clear();
 675
 676   // Remove all case branch to BB2 to test Eager recalculation.
 677   // Code section from llvm::ConstantFoldTerminator
 678   for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
 679     if (i->getCaseSuccessor() == BB2) {
 680       // Remove this entry.
 681       BB2->removePredecessor(BB0);
 682       i = SI->removeCase(i);
 683       e = SI->case_end();
 684       Updates.push_back({DominatorTree::Delete, BB0, BB2});
 685     } else
 686       ++i;
 687   }
 688
 689   DTU.applyUpdatesPermissive(Updates);
 690   // flush PostDomTree
 691   ASSERT_TRUE(DTU.getPostDomTree().verify());
 692   ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates());
 693   ASSERT_TRUE(DTU.hasPendingDomTreeUpdates());
 694   // flush both trees
 695   DTU.flush();
 696   ASSERT_TRUE(DT.verify());
 697 }
 698
 699 TEST(DomTreeUpdater, NoTreeTest) {
 700   StringRef FuncName = "f";
 701   StringRef ModuleString = R"(
 702                            define i32 @f() {
 703                            bb0:
 704                               ret i32 0
 705                            }
 706                            )";
 707   // Make the module.
 708   LLVMContext Context;
 709   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 710   Function *F = M->getFunction(FuncName);
 711
 712   // Make the DTU.
 713   DomTreeUpdater DTU(nullptr, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
 714   ASSERT_FALSE(DTU.hasDomTree());
 715   ASSERT_FALSE(DTU.hasPostDomTree());
 716   Function::iterator FI = F->begin();
 717   BasicBlock *BB0 = &*FI++;
 718   // Test whether PendingDeletedBB is flushed after the recalculation.
 719   DTU.deleteBB(BB0);
 720   ASSERT_TRUE(DTU.hasPendingDeletedBB());
 721   DTU.recalculate(*F);
 722   ASSERT_FALSE(DTU.hasPendingDeletedBB());
 723 }
 724
 725 TEST(DomTreeUpdater, LazyUpdateDeduplicationTest) {
 726   StringRef FuncName = "f";
 727   StringRef ModuleString = R"(
 728                            define i32 @f() {
 729                            bb0:
 730                               br label %bb1
 731                            bb1:
 732                               ret i32 1
 733                            bb2:
 734                               ret i32 1
 735                            }
 736                            )";
 737   // Make the module.
 738   LLVMContext Context;
 739   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 740   Function *F = M->getFunction(FuncName);
 741
 742   // Make the DTU.
 743   DominatorTree DT(*F);
 744   DomTreeUpdater DTU(&DT, nullptr, DomTreeUpdater::UpdateStrategy::Lazy);
 745   ASSERT_TRUE(DTU.getDomTree().verify());
 746
 747   Function::iterator FI = F->begin();
 748   BasicBlock *BB0 = &*FI++;
 749   BasicBlock *BB1 = &*FI++;
 750   BasicBlock *BB2 = &*FI++;
 751
 752   // CFG Change: remove bb0 -> bb1 and add back bb0 -> bb1.
 753   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 754   BB0->getTerminator()->eraseFromParent();
 755   BranchInst::Create(BB1, BB0);
 756   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 757
 758   // Update the DTU and simulate duplicates.
 759   DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
 760                               {DominatorTree::Delete, BB0, BB1},
 761                               {DominatorTree::Insert, BB0, BB1},
 762                               {DominatorTree::Insert, BB0, BB1},
 763                               {DominatorTree::Insert, BB0, BB1}});
 764
 765   // The above operations result in a no-op.
 766   ASSERT_FALSE(DTU.hasPendingUpdates());
 767
 768   // Update the DTU. Simulate an invalid update.
 769   DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1}});
 770   ASSERT_FALSE(DTU.hasPendingUpdates());
 771
 772   // CFG Change: remove bb0 -> bb1.
 773   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 774   BB0->getTerminator()->eraseFromParent();
 775
 776   // Update the DTU and simulate invalid updates.
 777   DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB0, BB1},
 778                               {DominatorTree::Insert, BB0, BB1},
 779                               {DominatorTree::Delete, BB0, BB1},
 780                               {DominatorTree::Insert, BB0, BB1},
 781                               {DominatorTree::Insert, BB0, BB1}});
 782   ASSERT_TRUE(DTU.hasPendingUpdates());
 783
 784   // CFG Change: add bb0 -> bb2.
 785   BranchInst::Create(BB2, BB0);
 786   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 787   DTU.applyUpdates({{DominatorTree::Insert, BB0, BB2}});
 788   ASSERT_TRUE(DTU.getDomTree().verify());
 789 }