Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -276,94 +276,6 @@ void print(raw_ostream &OS, const Module *M = nullptr) const override; }; - -//===------------------------------------- -/// Class to defer updates to a DominatorTree. -/// -/// Definition: Applying updates to every edge insertion and deletion is -/// expensive and not necessary. When one needs the DominatorTree for analysis -/// they can request a flush() to perform a larger batch update. This has the -/// advantage of the DominatorTree inspecting the set of updates to find -/// duplicates or unnecessary subtree updates. -/// -/// The scope of DeferredDominance operates at a Function level. -/// -/// It is not necessary for the user to scrub the updates for duplicates or -/// updates that point to the same block (Delete, BB_A, BB_A). Performance -/// can be gained if the caller attempts to batch updates before submitting -/// to applyUpdates(ArrayRef) in cases where duplicate edge requests will -/// occur. -/// -/// It is required for the state of the LLVM IR to be applied *before* -/// submitting updates. The update routines must analyze the current state -/// between a pair of (From, To) basic blocks to determine if the update -/// needs to be queued. -/// Example (good): -/// TerminatorInstructionBB->removeFromParent(); -/// DDT->deleteEdge(BB, Successor); -/// Example (bad): -/// DDT->deleteEdge(BB, Successor); -/// TerminatorInstructionBB->removeFromParent(); -class DeferredDominance { -public: - DeferredDominance(DominatorTree &DT_) : DT(DT_) {} - - /// Queues multiple updates and discards duplicates. - void applyUpdates(ArrayRef Updates); - - /// Helper method for a single edge insertion. It's almost always - /// better to batch updates and call applyUpdates to quickly remove duplicate - /// edges. This is best used when there is only a single insertion needed to - /// update Dominators. - void insertEdge(BasicBlock *From, BasicBlock *To); - - /// Helper method for a single edge deletion. It's almost always better - /// to batch updates and call applyUpdates to quickly remove duplicate edges. - /// This is best used when there is only a single deletion needed to update - /// Dominators. - void deleteEdge(BasicBlock *From, BasicBlock *To); - - /// Delays the deletion of a basic block until a flush() event. - void deleteBB(BasicBlock *DelBB); - - /// Returns true if DelBB is awaiting deletion at a flush() event. - bool pendingDeletedBB(BasicBlock *DelBB); - - /// Returns true if pending DT updates are queued for a flush() event. - bool pending(); - - /// Flushes all pending updates and block deletions. Returns a - /// correct DominatorTree reference to be used by the caller for analysis. - DominatorTree &flush(); - - /// Drops all internal state and forces a (slow) recalculation of the - /// DominatorTree based on the current state of the LLVM IR in F. This should - /// only be used in corner cases such as the Entry block of F being deleted. - void recalculate(Function &F); - - /// Debug method to help view the state of pending updates. - LLVM_DUMP_METHOD void dump() const; - -private: - DominatorTree &DT; - SmallVector PendUpdates; - SmallPtrSet DeletedBBs; - - /// Apply an update (Kind, From, To) to the internal queued updates. The - /// update is only added when determined to be necessary. Checks for - /// self-domination, unnecessary updates, duplicate requests, and balanced - /// pairs of requests are all performed. Returns true if the update is - /// queued and false if it is discarded. - bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, - BasicBlock *To); - - /// Performs all pending basic block deletions. We have to defer the deletion - /// of these blocks until after the DominatorTree updates are applied. The - /// internal workings of the DominatorTree code expect every update's From - /// and To blocks to exist and to be a member of the same Function. - bool flushDelBB(); -}; - } // end namespace llvm #endif // LLVM_IR_DOMINATORS_H Index: lib/IR/Dominators.cpp =================================================================== --- lib/IR/Dominators.cpp +++ lib/IR/Dominators.cpp @@ -372,193 +372,3 @@ DT.print(OS); } -//===----------------------------------------------------------------------===// -// DeferredDominance Implementation -//===----------------------------------------------------------------------===// -// -// The implementation details of the DeferredDominance class which allows -// one to queue updates to a DominatorTree. -// -//===----------------------------------------------------------------------===// - -/// Queues multiple updates and discards duplicates. -void DeferredDominance::applyUpdates( - ArrayRef Updates) { - SmallVector Seen; - for (auto U : Updates) - // Avoid duplicates to applyUpdate() to save on analysis. - if (std::none_of(Seen.begin(), Seen.end(), - [U](DominatorTree::UpdateType S) { return S == U; })) { - Seen.push_back(U); - applyUpdate(U.getKind(), U.getFrom(), U.getTo()); - } -} - -/// Helper method for a single edge insertion. It's almost always better -/// to batch updates and call applyUpdates to quickly remove duplicate edges. -/// This is best used when there is only a single insertion needed to update -/// Dominators. -void DeferredDominance::insertEdge(BasicBlock *From, BasicBlock *To) { - applyUpdate(DominatorTree::Insert, From, To); -} - -/// Helper method for a single edge deletion. It's almost always better -/// to batch updates and call applyUpdates to quickly remove duplicate edges. -/// This is best used when there is only a single deletion needed to update -/// Dominators. -void DeferredDominance::deleteEdge(BasicBlock *From, BasicBlock *To) { - applyUpdate(DominatorTree::Delete, From, To); -} - -/// Delays the deletion of a basic block until a flush() event. -void DeferredDominance::deleteBB(BasicBlock *DelBB) { - assert(DelBB && "Invalid push_back of nullptr DelBB."); - assert(pred_empty(DelBB) && "DelBB has one or more predecessors."); - // DelBB is unreachable and all its instructions are dead. - while (!DelBB->empty()) { - Instruction &I = DelBB->back(); - // Replace used instructions with an arbitrary value (undef). - if (!I.use_empty()) - I.replaceAllUsesWith(llvm::UndefValue::get(I.getType())); - DelBB->getInstList().pop_back(); - } - // Make sure DelBB has a valid terminator instruction. As long as DelBB is a - // Child of Function F it must contain valid IR. - new UnreachableInst(DelBB->getContext(), DelBB); - DeletedBBs.insert(DelBB); -} - -/// Returns true if DelBB is awaiting deletion at a flush() event. -bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) { - if (DeletedBBs.empty()) - return false; - return DeletedBBs.count(DelBB) != 0; -} - -/// Returns true if pending DT updates are queued for a flush() event. -bool DeferredDominance::pending() { return !PendUpdates.empty(); } - -/// Flushes all pending updates and block deletions. Returns a -/// correct DominatorTree reference to be used by the caller for analysis. -DominatorTree &DeferredDominance::flush() { - // Updates to DT must happen before blocks are deleted below. Otherwise the - // DT traversal will encounter badref blocks and assert. - if (!PendUpdates.empty()) { - DT.applyUpdates(PendUpdates); - PendUpdates.clear(); - } - flushDelBB(); - return DT; -} - -/// Drops all internal state and forces a (slow) recalculation of the -/// DominatorTree based on the current state of the LLVM IR in F. This should -/// only be used in corner cases such as the Entry block of F being deleted. -void DeferredDominance::recalculate(Function &F) { - // flushDelBB must be flushed before the recalculation. The state of the IR - // must be consistent before the DT traversal algorithm determines the - // actual DT. - if (flushDelBB() || !PendUpdates.empty()) { - DT.recalculate(F); - PendUpdates.clear(); - } -} - -/// Debug method to help view the state of pending updates. -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void DeferredDominance::dump() const { - raw_ostream &OS = llvm::dbgs(); - OS << "PendUpdates:\n"; - int I = 0; - for (auto U : PendUpdates) { - OS << " " << I << " : "; - ++I; - if (U.getKind() == DominatorTree::Insert) - OS << "Insert, "; - else - OS << "Delete, "; - BasicBlock *From = U.getFrom(); - if (From) { - auto S = From->getName(); - if (!From->hasName()) - S = "(no name)"; - OS << S << "(" << From << "), "; - } else { - OS << "(badref), "; - } - BasicBlock *To = U.getTo(); - if (To) { - auto S = To->getName(); - if (!To->hasName()) - S = "(no_name)"; - OS << S << "(" << To << ")\n"; - } else { - OS << "(badref)\n"; - } - } - OS << "DeletedBBs:\n"; - I = 0; - for (auto BB : DeletedBBs) { - OS << " " << I << " : "; - ++I; - if (BB->hasName()) - OS << BB->getName() << "("; - else - OS << "(no_name)("; - OS << BB << ")\n"; - } -} -#endif - -/// Apply an update (Kind, From, To) to the internal queued updates. The -/// update is only added when determined to be necessary. Checks for -/// self-domination, unnecessary updates, duplicate requests, and balanced -/// pairs of requests are all performed. Returns true if the update is -/// queued and false if it is discarded. -bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind, - BasicBlock *From, BasicBlock *To) { - if (From == To) - return false; // Cannot dominate self; discard update. - - // Discard updates by inspecting the current state of successors of From. - // Since applyUpdate() must be called *after* the Terminator of From is - // altered we can determine if the update is unnecessary. - bool HasEdge = std::any_of(succ_begin(From), succ_end(From), - [To](BasicBlock *B) { return B == To; }); - if (Kind == DominatorTree::Insert && !HasEdge) - return false; // Unnecessary Insert: edge does not exist in IR. - if (Kind == DominatorTree::Delete && HasEdge) - return false; // Unnecessary Delete: edge still exists in IR. - - // Analyze pending updates to determine if the update is unnecessary. - DominatorTree::UpdateType Update = {Kind, From, To}; - DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert - ? DominatorTree::Insert - : DominatorTree::Delete, - From, To}; - for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) { - if (Update == *I) - return false; // Discard duplicate updates. - if (Invert == *I) { - // Update and Invert are both valid (equivalent to a no-op). Remove - // Invert from PendUpdates and discard the Update. - PendUpdates.erase(I); - return false; - } - } - PendUpdates.push_back(Update); // Save the valid update. - return true; -} - -/// Performs all pending basic block deletions. We have to defer the deletion -/// of these blocks until after the DominatorTree updates are applied. The -/// internal workings of the DominatorTree code expect every update's From -/// and To blocks to exist and to be a member of the same Function. -bool DeferredDominance::flushDelBB() { - if (DeletedBBs.empty()) - return false; - for (auto *BB : DeletedBBs) - BB->eraseFromParent(); - DeletedBBs.clear(); - return true; -} Index: unittests/IR/CMakeLists.txt =================================================================== --- unittests/IR/CMakeLists.txt +++ unittests/IR/CMakeLists.txt @@ -15,7 +15,6 @@ ConstantsTest.cpp DebugInfoTest.cpp DebugTypeODRUniquingTest.cpp - DeferredDominanceTest.cpp DominatorTreeTest.cpp DominatorTreeBatchUpdatesTest.cpp DomTreeUpdaterTest.cpp Index: unittests/IR/DeferredDominanceTest.cpp =================================================================== --- unittests/IR/DeferredDominanceTest.cpp +++ /dev/null @@ -1,344 +0,0 @@ -//===- llvm/unittests/IR/DeferredDominanceTest.cpp - DDT unit tests -------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -using namespace llvm; - -static std::unique_ptr makeLLVMModule(LLVMContext &Context, - StringRef ModuleStr) { - SMDiagnostic Err; - std::unique_ptr M = parseAssemblyString(ModuleStr, Err, Context); - assert(M && "Bad LLVM IR?"); - return M; -} - -TEST(DeferredDominance, BasicOperations) { - StringRef FuncName = "f"; - StringRef ModuleString = - "define i32 @f(i32 %i, i32 *%p) {\n" - " bb0:\n" - " store i32 %i, i32 *%p\n" - " switch i32 %i, label %bb1 [\n" - " i32 0, label %bb2\n" - " i32 1, label %bb2\n" - " i32 2, label %bb3\n" - " ]\n" - " bb1:\n" - " ret i32 1\n" - " bb2:\n" - " ret i32 2\n" - " bb3:\n" - " ret i32 3\n" - "}\n"; - // Make the module. - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleString); - Function *F = M->getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << "."; - - // Make the DDT. - DominatorTree DT(*F); - DeferredDominance DDT(DT); - ASSERT_TRUE(DDT.flush().verify()); - - Function::iterator FI = F->begin(); - BasicBlock *BB0 = &*FI++; - BasicBlock *BB1 = &*FI++; - BasicBlock *BB2 = &*FI++; - BasicBlock *BB3 = &*FI++; - - // Test discards of invalid self-domination updates. These use the single - // short-hand interface but are still queued inside DDT. - DDT.deleteEdge(BB0, BB0); - DDT.insertEdge(BB1, BB1); - - // Delete edge bb0 -> bb3 and push the update twice to verify duplicate - // entries are discarded. - std::vector Updates; - Updates.reserve(4); - Updates.push_back({DominatorTree::Delete, BB0, BB3}); - Updates.push_back({DominatorTree::Delete, BB0, BB3}); - - // Unnecessary Insert: no edge bb1 -> bb2 after change to bb0. - Updates.push_back({DominatorTree::Insert, BB1, BB2}); - // Unnecessary Delete: edge exists bb0 -> bb1 after change to bb0. - Updates.push_back({DominatorTree::Delete, BB0, BB1}); - - // CFG Change: remove edge bb0 -> bb3 and one duplicate edge bb0 -> bb2. - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); - BB0->getTerminator()->eraseFromParent(); - BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); - - // Deletion of a BasicBlock is an immediate event. We remove all uses to the - // contained Instructions and change the Terminator to "unreachable" when - // queued for deletion. Its parent is still F until DDT.flush() is called. We - // don't defer this action because it can cause problems for other transforms - // or analysis as it's part of the actual CFG. We only defer updates to the - // DominatorTree. This code will crash if it is placed before the - // BranchInst::Create() call above. - ASSERT_FALSE(isa(BB3->getTerminator())); - EXPECT_FALSE(DDT.pendingDeletedBB(BB3)); - DDT.deleteBB(BB3); - EXPECT_TRUE(DDT.pendingDeletedBB(BB3)); - ASSERT_TRUE(isa(BB3->getTerminator())); - EXPECT_EQ(BB3->getParent(), F); - - // Verify. Updates to DDT must be applied *after* all changes to the CFG - // (including block deletion). - DDT.applyUpdates(Updates); - ASSERT_TRUE(DDT.flush().verify()); -} - -TEST(DeferredDominance, PairedUpdate) { - StringRef FuncName = "f"; - StringRef ModuleString = - "define i32 @f(i32 %i, i32 *%p) {\n" - " bb0:\n" - " store i32 %i, i32 *%p\n" - " switch i32 %i, label %bb1 [\n" - " i32 0, label %bb2\n" - " i32 1, label %bb2\n" - " ]\n" - " bb1:\n" - " ret i32 1\n" - " bb2:\n" - " ret i32 2\n" - "}\n"; - // Make the module. - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleString); - Function *F = M->getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << "."; - - // Make the DDT. - DominatorTree DT(*F); - DeferredDominance DDT(DT); - ASSERT_TRUE(DDT.flush().verify()); - - Function::iterator FI = F->begin(); - BasicBlock *BB0 = &*FI++; - BasicBlock *BB1 = &*FI++; - BasicBlock *BB2 = &*FI++; - - // CFG Change: only edge from bb0 is bb0 -> bb1. - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u); - BB0->getTerminator()->eraseFromParent(); - BranchInst::Create(BB1, BB0); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); - - // Must be done after the CFG change. The applyUpdate() routine analyzes the - // current state of the CFG. - DDT.deleteEdge(BB0, BB2); - - // CFG Change: bb0 now has bb0 -> bb1 and bb0 -> bb2. - // With this change no dominance has been altered from the original IR. DT - // doesn't care if the type of TerminatorInstruction changed, only if the - // unique edges have. - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); - BB0->getTerminator()->eraseFromParent(); - BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F->getContext()), BB0); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); - - // Must be done after the CFG change. The applyUpdate() routine analyzes the - // current state of the CFG. This DDT update pairs with the previous one and - // is cancelled out before ever applying updates to DT. - DDT.insertEdge(BB0, BB2); - - // Test the empty DeletedBB list. - EXPECT_FALSE(DDT.pendingDeletedBB(BB0)); - EXPECT_FALSE(DDT.pendingDeletedBB(BB1)); - EXPECT_FALSE(DDT.pendingDeletedBB(BB2)); - - // The DT has no changes, this flush() simply returns a reference to the - // internal DT calculated at the beginning of this test. - ASSERT_TRUE(DDT.flush().verify()); -} - -TEST(DeferredDominance, ReplaceEntryBB) { - StringRef FuncName = "f"; - StringRef ModuleString = - "define i32 @f() {\n" - "bb0:\n" - " br label %bb1\n" - " bb1:\n" - " ret i32 1\n" - "}\n"; - // Make the module. - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleString); - Function *F = M->getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << "."; - - // Make the DDT. - DominatorTree DT(*F); - DeferredDominance DDT(DT); - ASSERT_TRUE(DDT.flush().verify()); - - Function::iterator FI = F->begin(); - BasicBlock *BB0 = &*FI++; - BasicBlock *BB1 = &*FI++; - - // Add a block as the new function entry BB. We also link it to BB0. - BasicBlock *NewEntry = - BasicBlock::Create(F->getContext(), "new_entry", F, BB0); - BranchInst::Create(BB0, NewEntry); - EXPECT_EQ(F->begin()->getName(), NewEntry->getName()); - EXPECT_TRUE(&F->getEntryBlock() == NewEntry); - - // Insert the new edge between new_eentry -> bb0. Without this the - // recalculate() call below will not actually recalculate the DT as there - // are no changes pending and no blocks deleted. - DDT.insertEdge(NewEntry, BB0); - - // Changing the Entry BB requires a full recalulation. - DDT.recalculate(*F); - ASSERT_TRUE(DDT.flush().verify()); - - // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1. - EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u); - NewEntry->getTerminator()->eraseFromParent(); - BranchInst::Create(BB1, NewEntry); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); - - // Update the DDT. At this point bb0 now has no predecessors but is still a - // Child of F. - DDT.applyUpdates({{DominatorTree::Delete, NewEntry, BB0}, - {DominatorTree::Insert, NewEntry, BB1}}); - ASSERT_TRUE(DDT.flush().verify()); - - // Now remove bb0 from F. - ASSERT_FALSE(isa(BB0->getTerminator())); - EXPECT_FALSE(DDT.pendingDeletedBB(BB0)); - DDT.deleteBB(BB0); - EXPECT_TRUE(DDT.pendingDeletedBB(BB0)); - ASSERT_TRUE(isa(BB0->getTerminator())); - EXPECT_EQ(BB0->getParent(), F); - - // Perform a full recalculation of the DDT. It is not necessary here but we - // do this to test the case when there are no pending DT updates but there are - // pending deleted BBs. - DDT.recalculate(*F); - ASSERT_TRUE(DDT.flush().verify()); -} - -TEST(DeferredDominance, InheritedPreds) { - StringRef FuncName = "f"; - StringRef ModuleString = - "define i32 @f(i32 %i, i32 *%p) {\n" - " bb0:\n" - " store i32 %i, i32 *%p\n" - " switch i32 %i, label %bb1 [\n" - " i32 2, label %bb2\n" - " i32 3, label %bb3\n" - " ]\n" - " bb1:\n" - " br label %bb3\n" - " bb2:\n" - " br label %bb3\n" - " bb3:\n" - " ret i32 3\n" - "}\n"; - // Make the module. - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleString); - Function *F = M->getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << "."; - - // Make the DDT. - DominatorTree DT(*F); - DeferredDominance DDT(DT); - ASSERT_TRUE(DDT.flush().verify()); - - Function::iterator FI = F->begin(); - BasicBlock *BB0 = &*FI++; - BasicBlock *BB1 = &*FI++; - BasicBlock *BB2 = &*FI++; - BasicBlock *BB3 = &*FI++; - - // There are several CFG locations where we have: - // - // pred1..predN - // | | - // +> curr <+ converted into: pred1..predN curr - // | | | - // v +> succ <+ - // succ - // - // There is a specific shape of this we have to be careful of: - // - // pred1..predN - // || | - // |+> curr <+ converted into: pred1..predN curr - // | | | | - // | v +> succ <+ - // +-> succ - // - // While the final CFG form is functionally identical the updates to - // DDT are not. In the first case we must have DDT.insertEdge(Pred1, Succ) - // while in the latter case we must *NOT* have DDT.insertEdge(Pred1, Succ). - - // CFG Change: bb0 now only has bb0 -> bb1 and bb0 -> bb3. We are preparing to - // remove bb2. - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u); - BB0->getTerminator()->eraseFromParent(); - BranchInst::Create(BB1, BB3, ConstantInt::getTrue(F->getContext()), BB0); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); - - // Remove bb2 from F. This has to happen before the call to applyUpdates() for - // DDT to detect there is no longer an edge between bb2 -> bb3. The deleteBB() - // method converts bb2's TI into "unreachable". - ASSERT_FALSE(isa(BB2->getTerminator())); - EXPECT_FALSE(DDT.pendingDeletedBB(BB2)); - DDT.deleteBB(BB2); - EXPECT_TRUE(DDT.pendingDeletedBB(BB2)); - ASSERT_TRUE(isa(BB2->getTerminator())); - EXPECT_EQ(BB2->getParent(), F); - - // Queue up the DDT updates. - std::vector Updates; - Updates.reserve(4); - Updates.push_back({DominatorTree::Delete, BB0, BB2}); - Updates.push_back({DominatorTree::Delete, BB2, BB3}); - - // Handle the specific shape case next. - // CFG Change: bb0 now only branches to bb3. We are preparing to remove bb1. - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); - BB0->getTerminator()->eraseFromParent(); - BranchInst::Create(BB3, BB0); - EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u); - - // Remove bb1 from F. This has to happen before the call to applyUpdates() for - // DDT to detect there is no longer an edge between bb1 -> bb3. The deleteBB() - // method converts bb1's TI into "unreachable". - ASSERT_FALSE(isa(BB1->getTerminator())); - EXPECT_FALSE(DDT.pendingDeletedBB(BB1)); - DDT.deleteBB(BB1); - EXPECT_TRUE(DDT.pendingDeletedBB(BB1)); - ASSERT_TRUE(isa(BB1->getTerminator())); - EXPECT_EQ(BB1->getParent(), F); - - // Update the DDT. In this case we don't call DDT.insertEdge(BB0, BB3) because - // the edge previously existed at the start of this test when DT was first - // created. - Updates.push_back({DominatorTree::Delete, BB0, BB1}); - Updates.push_back({DominatorTree::Delete, BB1, BB3}); - - // Verify everything. - DDT.applyUpdates(Updates); - ASSERT_TRUE(DDT.flush().verify()); -}