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