Index: include/llvm/IR/DomTreeUpdater.h =================================================================== --- /dev/null +++ include/llvm/IR/DomTreeUpdater.h @@ -0,0 +1,196 @@ +//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the DomTreeUpdater class, which provides a uniform way to +// update dominator tree related data structures. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_DOMTREEUPDATER_H +#define LLVM_DOMTREEUPDATER_H + +#include "llvm/Analysis/PostDominators.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/GenericDomTree.h" + +namespace llvm { +class DomTreeUpdater { +public: + enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; + // Constructor + explicit DomTreeUpdater(UpdateStrategy Ups_) : Ups(Ups_) {} + explicit DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Ups_) + : DT(&DT_), Ups(Ups_) {} + explicit DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Ups_) + : PDT(&PDT_), Ups(Ups_) {} + explicit DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, + UpdateStrategy Ups_) + : DT(&DT_), PDT(&PDT_), Ups(Ups_) {} + // Query + /// Get UpdateStrategy to enable further low level optimizations + /// in codes. + UpdateStrategy getUpdateStrategy() const { return Ups; }; + /// Check whether the updater class holds a dominator tree. + /// \returns true if it holds a dominator tree. + bool hasDomTree() const { return DT != nullptr; } + /// Check whether the updater class holds a post dominator tree. + /// \returns true if it holds a post dominator tree. + bool hasPostDomTree() const { return PDT != nullptr; } + /// Check whether there is Basic Block pending to be deleted. + /// + /// \return true if there is Basic Block pending to be deleted. + bool hasPendDeletedBB() const; + /// Check whether a specific BasicBlock is waiting to be deleted. + /// + /// \param DelBB Basic Block to check. + /// \returns false when the updater is constructed using the eager updating + /// strategy. + /// \returns true when the specific BasicBlock is waiting to be deleted. + bool hasPendingDeletedBB(BasicBlock *DelBB) const; + /// Check whether there are any pending updates. + /// + /// \returns true if all holding data structures are up to date. + /// \returns false otherwise. + bool hasPendingUpdates() const; + /// Check whether the owned dominator Tree is up to date. + /// + /// \returns true when the dominator tree is up to date. + /// \returns false when the class does not hold a dominator + /// tree or the dominator tree is not up to date. + bool hasPendingDomTreeUpdates() const; + /// Check whether the owned Post dominator Tree is up to date. + /// + /// \returns true when the Post dominator tree is up to date. + /// \returns false when the class does not hold a Post dominator + /// tree or the Post dominator tree is not up to date. + bool hasPendingPostDomTreeUpdates() const; + // Modify + /// Apply updates according to the UpdateStrategy. + /// + /// \param Updates The updates to perform on data structures held. + void applyUpdates(ArrayRef Updates, + bool ForceRemoveInvalidUpdates = false); + /// Insert an Edge based on UpdateStrategy. + /// + /// \param From The BasicBlock edge starts. + /// \param To The BasicBlock edge ends. + void insertEdge(BasicBlock *From, BasicBlock *To, + bool ForceRemoveInvalidUpdate = false); + /// Delete an Edge based on UpdateStrategy. + /// + /// \param From The BasicBlock edge starts. + /// \param To The BasicBlock edge ends. + void deleteEdge(BasicBlock *From, BasicBlock *To, + bool ForceRemoveInvalidUpdate = false); + /// Delete a basic block based on UpdateStrategy. DelBB + /// will be automatically removed from all holding trees. + /// + /// \param DelBB The basic block to delete. + void deleteBB(BasicBlock *DelBB); + /// Delete a basic block based on UpdateStrategy with callback. + /// The callback will be called after DelBB -> removeFromParent() + /// , removal of DelBB from trees and before delete + /// DelBB. + /// + /// \param DelBB The basic block to delete. + /// \param Callback The callback function to be called before delete DelBB; + void callbackDeleteBB(BasicBlock *DelBB, + function_ref Callback); + /// Recalculate the dominator tree. + /// In this scenario, it is supposed the post dominator + /// tree should not be recalculated. + /// This function should be called when the class holds a DomTree. + void recalculateDomTree(Function &F); + /// Recalculate the post dominator tree. + /// In this scenario, it is supposed the dominator + /// tree should not be recalculated. + /// This function should be called when the class holds a PostDomTree. + void recalculatePostDomTree(Function &F); + /// Recalculate Both of the trees. + /// This function should be called when the class holds both of the trees. + void recalculateAll(Function &F); + // flush + /// FLush DomTree updates to get DomTree up to date. + /// It will also clear out of date updates and unnecessary + /// stored BasicBlocks. + /// It should only be called when there is a DomTree. + DominatorTree &flushDomTree(); + /// FLush PostDomTree updates to get PostDomTree up to date. + /// It will also clear out of date updates and unnecessary + /// stored BasicBlocks. + /// It should only be called when there is a PostDomTree. + PostDominatorTree &flushPostDomTree(); + /// Flush all pending updates to get DomTree and PostDomTree up to date. + /// PendingUpdates and PendingDeletedBBs will be cleared. + /// This function can be called not knowing which tree is held. + void flushAll(); + // Debug + /// Debug method to help view the state of the internal data structures. + LLVM_DUMP_METHOD void dump() const; + +private: + class CallBackOnDeletion final : public CallbackVH { + public: + CallBackOnDeletion(BasicBlock *V, function_ref Callback) + : CallbackVH(V), DelBB(V), Callback_(Callback) {} + + private: + BasicBlock *DelBB = nullptr; + function_ref Callback_; + void deleted() override { + Callback_(DelBB); + CallbackVH::deleted(); + } + }; + SmallVector PendUpdates; + size_t PendDTUpdateIndex = 0; + size_t PendPDTUpdateIndex = 0; + DominatorTree *DT = nullptr; + PostDominatorTree *PDT = nullptr; + const UpdateStrategy Ups; + SmallPtrSet DeletedBBs; + SmallVector Callbacks; + bool IsRecalculatingDomTree = false; + bool IsRecalculatingPostDomTree = false; + + /// Validate and pre-process before Basic Blocks are unlinked from parents + /// and deleted. + void validateDeleteBB(BasicBlock *DelBB); + /// Erase all deleted BasicBlocks from the Function. + /// + /// \returns false when nothing deleted. + /// \returns true otherwise. + bool forceFlushDeletedBB(); + /// Handle single updates when using Lazy UpdateStrategy. + /// This includes deduplicating, avoid no-ops. + /// + /// \returns true if the update is pushed into the PendUpdates + /// vector. False otherwise. + bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, + BasicBlock *To); + /// Apply all pending DomTree updates. + void applyDomTreeUpdates(); + /// Apply all pending PostDomTree updates. + void applyPostDomTreeUpdates(); + /// Flush unnecessary deleted BasicBlocks. + void tryFLushDeletedBB(); + /// Drop all out of date updates and delete unnecessary Basic Blocks. + void dropOutOfDateUpdates(); + /// Try to erase Basic Block node that has been unlinked from Function + /// in the DomTree and PostDomTree. + void eraseDelBBNode(BasicBlock *DelBB); + /// Determine whether the update is valid or is self-dominance + /// in a single step of update or needs to discard in the batch update. + bool isUpdateValid(const DominatorTree::UpdateType Update) const; +}; +} // namespace llvm + +#endif // LLVM_DOMTREEUPDATER_H Index: lib/IR/CMakeLists.txt =================================================================== --- lib/IR/CMakeLists.txt +++ lib/IR/CMakeLists.txt @@ -21,6 +21,7 @@ DiagnosticInfo.cpp DiagnosticPrinter.cpp Dominators.cpp + DomTreeUpdater.cpp Function.cpp GVMaterializer.cpp Globals.cpp Index: lib/IR/DomTreeUpdater.cpp =================================================================== --- /dev/null +++ lib/IR/DomTreeUpdater.cpp @@ -0,0 +1,448 @@ +//===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the DomTreeUpdater class, which provides a uniform way +// to update dominator tree related data structures. +// +//===----------------------------------------------------------------------===// + +#include "llvm/IR/DomTreeUpdater.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/IR/Dominators.h" +#include "llvm/Support/GenericDomTree.h" +#include + +namespace llvm { + +bool DomTreeUpdater::isUpdateValid( + const DominatorTree::UpdateType Update) const { + const auto From = Update.getFrom(); + const auto To = Update.getTo(); + const auto Kind = Update.getKind(); + if (From == To) + return false; // Won't affect DomTree and PostDomTree; discard update. + // Discard updates by inspecting the current state of successors of From. + // Since isUpdateValid() must be called *after* the Terminator of From is + // altered we can determine if the update is unnecessary for batch updates + // or invalid for a single update. + const bool HasEdge = + std::any_of(succ_begin(From), succ_end(From), + [To](const BasicBlock *B) { return B == To; }); + if (Kind == DominatorTree::Insert && !HasEdge) + return false; // Invalid Insert: edge does not exist in IR. + if (Kind == DominatorTree::Delete && HasEdge) + return false; // Invalid Delete: edge still exists in IR. + return true; +} + +bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind, + BasicBlock *From, BasicBlock *To) { + assert(Ups == DomTreeUpdater::UpdateStrategy::Lazy && + "Call applyLazyUpdate() with Eager strategy error"); + // Analyze pending updates to determine if the update is unnecessary. + const DominatorTree::UpdateType Update = {Kind, From, To}; + const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert + ? DominatorTree::Insert + : DominatorTree::Delete, + From, To}; + // Only check duplicates in updates that are not applied by both trees. + auto I = + PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex); + auto E = PendUpdates.end(); + assert(I <= E && "Error occurred in DomTreeUpdater::applyLazyUpdate"); + for (; 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; +} + +void DomTreeUpdater::applyDomTreeUpdates() { + if (Ups != UpdateStrategy::Lazy || !DT) + return; + if (hasPendingDomTreeUpdates()) { + DT->applyUpdates(ArrayRef( + PendUpdates.begin() + PendDTUpdateIndex, PendUpdates.end())); + PendDTUpdateIndex = PendUpdates.size(); + } +} + +void DomTreeUpdater::flushAll() { + applyDomTreeUpdates(); + applyPostDomTreeUpdates(); + dropOutOfDateUpdates(); +} + +void DomTreeUpdater::applyPostDomTreeUpdates() { + if (Ups != UpdateStrategy::Lazy || !PDT) + return; + if (hasPendingPostDomTreeUpdates()) { + PDT->applyUpdates(ArrayRef( + PendUpdates.begin() + PendPDTUpdateIndex, PendUpdates.end())); + PendPDTUpdateIndex = PendUpdates.size(); + } +} + +void DomTreeUpdater::tryFLushDeletedBB() { + if (!hasPendingUpdates()) + forceFlushDeletedBB(); +} + +bool DomTreeUpdater::hasPendDeletedBB() const { return !DeletedBBs.empty(); } + +bool DomTreeUpdater::forceFlushDeletedBB() { + if (DeletedBBs.empty()) + return false; + for (auto *BB : DeletedBBs) { + BB->removeFromParent(); + eraseDelBBNode(BB); + delete BB; + } + DeletedBBs.clear(); + Callbacks.clear(); + return true; +} + +void DomTreeUpdater::recalculateAll(Function &F) { + assert(DT != nullptr && PDT != nullptr && + "recalculateAll must be called with DomTree and PostDomTree."); + if (Ups == UpdateStrategy::Eager) { + DT->recalculate(F); + PDT->recalculate(F); + return; + } + // Prevent forceFlushDeletedBB() from erasing DomTree and PostDomTree nodes. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = true; + // Deleted BBs must be flushed before the recalculation. The state of the IR + // must be consistent before the DT traversal algorithm determines the + // actual DT. + if (forceFlushDeletedBB() || hasPendingDomTreeUpdates() || + hasPendingPostDomTreeUpdates()) { + DT->recalculate(F); + PDT->recalculate(F); + // Resume updating both two trees after recalculating. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; + PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); + dropOutOfDateUpdates(); + } +} +// This function should be used when the graph is changed significantly +// and DT must be recalculated, previous graph changes should be made. +void DomTreeUpdater::recalculateDomTree(Function &F) { + assert(DT != nullptr && "recalculateDomTree must be called with a DomTree."); + if (Ups == UpdateStrategy::Eager) { + DT->recalculate(F); + return; + } + // Prevent forceFlushDeletedBB() from erasing DomTree nodes. + IsRecalculatingDomTree = true; + if (hasPendDeletedBB() || hasPendingDomTreeUpdates()) { + // Deleted BBs must be flushed before the recalculation. The state of the IR + // must be consistent before the DT traversal algorithm determines the + // actual DT. + if (hasPendDeletedBB()) { + applyPostDomTreeUpdates(); + forceFlushDeletedBB(); + } + DT->recalculate(F); + // Resume updating DomTree after recalculating. + IsRecalculatingDomTree = false; + PendDTUpdateIndex = PendUpdates.size(); + dropOutOfDateUpdates(); + } +} +// This function should be used when the graph is changed significantly +// and PDT must be recalculated, previous graph changes should be made. +void DomTreeUpdater::recalculatePostDomTree(Function &F) { + assert(PDT != nullptr && + "recalculatePostDomTree must be called with a PostDomTree."); + if (Ups == UpdateStrategy::Eager) { + PDT->recalculate(F); + return; + } + // Prevent forceFlushDeletedBB() from erasing PostDomTree nodes. + IsRecalculatingPostDomTree = true; + if (hasPendDeletedBB() || hasPendingPostDomTreeUpdates()) { + if (hasPendDeletedBB()) { + // Deleted BBs must be flushed before the recalculation. The state of the + // IR must be consistent before the DT traversal algorithm determines the + // actual DT. + applyDomTreeUpdates(); + forceFlushDeletedBB(); + } + PDT->recalculate(F); + // Resume updating PostDomTree after recalculating. + IsRecalculatingPostDomTree = false; + PendPDTUpdateIndex = PendUpdates.size(); + dropOutOfDateUpdates(); + } +} + +bool DomTreeUpdater::hasPendingUpdates() const { + return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates(); +} + +bool DomTreeUpdater::hasPendingDomTreeUpdates() const { + if (DT == nullptr) + return false; + return PendUpdates.size() != PendDTUpdateIndex; +} + +bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const { + if (PDT == nullptr) + return false; + return PendUpdates.size() != PendPDTUpdateIndex; +} + +bool DomTreeUpdater::hasPendingDeletedBB(BasicBlock *DelBB) const { + if (Ups == UpdateStrategy::Eager || DeletedBBs.empty()) + return false; + return DeletedBBs.count(DelBB) != 0; +} +// The DT and PDT require the nodes related to updates +// are not deleted when update functions are called. +// So BasicBlock deletions must be pended when the +// UpdateStrategy is Lazy. When the UpdateStrategy is +// Eager, the BasicBlock will be deleted immediately. +void DomTreeUpdater::deleteBB(BasicBlock *DelBB) { + validateDeleteBB(DelBB); + if (Ups == UpdateStrategy::Lazy) { + DeletedBBs.insert(DelBB); + return; + } + DelBB->removeFromParent(); + eraseDelBBNode(DelBB); + delete DelBB; +} + +void DomTreeUpdater::callbackDeleteBB( + BasicBlock *DelBB, function_ref Callback) { + validateDeleteBB(DelBB); + if (Ups == UpdateStrategy::Lazy) { + Callbacks.push_back(CallBackOnDeletion(DelBB, Callback)); + DeletedBBs.insert(DelBB); + return; + } + DelBB->removeFromParent(); + eraseDelBBNode(DelBB); + Callback(DelBB); + delete DelBB; +} + +void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) { + if (DT && !IsRecalculatingDomTree) + if (DT->getNode(DelBB) != nullptr) + DT->eraseNode(DelBB); + if (PDT && !IsRecalculatingPostDomTree) + if (PDT->getNode(DelBB) != nullptr) + PDT->eraseNode(DelBB); +} + +void DomTreeUpdater::validateDeleteBB(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); +} + +void DomTreeUpdater::applyUpdates(ArrayRef Updates, + bool ForceRemoveInvalidUpdates) { + if (Ups == UpdateStrategy::Lazy || ForceRemoveInvalidUpdates) { + SmallVector Seen; + for (const auto U : Updates) + // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save + // on analysis. + if (std::none_of( + Seen.begin(), Seen.end(), + [U](const DominatorTree::UpdateType S) { return S == U; }) && + isUpdateValid(U)) { + Seen.push_back(U); + if (Ups == UpdateStrategy::Lazy) + applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo()); + } + if (Ups == UpdateStrategy::Lazy) + return; + if (DT) + DT->applyUpdates(Seen); + if (PDT) + PDT->applyUpdates(Seen); + return; + } + if (DT) + DT->applyUpdates(Updates); + if (PDT) + PDT->applyUpdates(Updates); +} + +DominatorTree &DomTreeUpdater::flushDomTree() { + assert(DT && "Invalid acquisition of a null DomTree"); + applyDomTreeUpdates(); + dropOutOfDateUpdates(); + return *DT; +} + +PostDominatorTree &DomTreeUpdater::flushPostDomTree() { + assert(PDT && "Invalid acquisition of a null PostDomTree"); + applyPostDomTreeUpdates(); + dropOutOfDateUpdates(); + return *PDT; +} + +void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To, + bool ForceRemoveInvalidUpdate) { + + if (Ups == UpdateStrategy::Lazy || ForceRemoveInvalidUpdate) + if (!isUpdateValid({DominatorTree::Insert, From, To})) + return; + if (Ups == UpdateStrategy::Eager) { + if (DT) + DT->insertEdge(From, To); + if (PDT) + PDT->insertEdge(From, To); + return; + } + applyLazyUpdate(DominatorTree::Insert, From, To); +} + +void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To, + bool ForceRemoveInvalidUpdate) { + if (Ups == UpdateStrategy::Lazy || ForceRemoveInvalidUpdate) + if (!isUpdateValid({DominatorTree::Delete, From, To})) + return; + if (Ups == UpdateStrategy::Eager) { + if (DT) + DT->deleteEdge(From, To); + if (PDT) + PDT->deleteEdge(From, To); + return; + } + applyLazyUpdate(DominatorTree::Delete, From, To); +} + +void DomTreeUpdater::dropOutOfDateUpdates() { + if (Ups == DomTreeUpdater::UpdateStrategy::Eager) + return; + // flush unneeded Basic Blocks + tryFLushDeletedBB(); + // Drop all updates applied by both trees + if (DT == nullptr) + PendDTUpdateIndex = PendUpdates.size(); + if (PDT == nullptr) + PendPDTUpdateIndex = PendUpdates.size(); + const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex); + PendUpdates.erase(PendUpdates.begin(), PendUpdates.begin() + dropIndex); + // reset index + PendDTUpdateIndex -= dropIndex; + PendPDTUpdateIndex -= dropIndex; +} + +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) +LLVM_DUMP_METHOD void DomTreeUpdater::dump() const { + raw_ostream &OS = llvm::dbgs(); + OS << "Holding Trees: "; + if (DT || PDT) { + if (DT) + OS << "DomTree "; + if (PDT) + OS << "PostDomTree "; + OS << "\n"; + } else + OS << "None\n"; + OS << "UpdateStrategy: "; + if (Ups == UpdateStrategy::Eager) { + OS << "Eager\n"; + return; + } else + OS << "Lazy\n"; + int I = 0; + auto printUpdates = + [&](ArrayRef::const_iterator begin, + ArrayRef::const_iterator end) { + I = 0; + for (auto It = begin, ItEnd = end; It != ItEnd; ++It) { + auto U = *It; + 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"; + } + } + }; + if (DT) { + OS << "Applied but not cleared DomTreeUpdates:\n"; + printUpdates(PendUpdates.begin(), PendUpdates.begin() + PendDTUpdateIndex); + OS << "Pending DomTreeUpdates:\n"; + printUpdates(PendUpdates.begin() + PendDTUpdateIndex, PendUpdates.end()); + } + if (PDT) { + OS << "Applied but not cleared PostDomTreeUpdates:\n"; + printUpdates(PendUpdates.begin(), PendUpdates.begin() + PendPDTUpdateIndex); + OS << "Pending PostDomTreeUpdates:\n"; + printUpdates(PendUpdates.begin() + PendPDTUpdateIndex, PendUpdates.end()); + } + OS << "Pending DeletedBBs:\n"; + I = 0; + for (auto BB : DeletedBBs) { + OS << " " << I << " : "; + ++I; + if (BB->hasName()) + OS << BB->getName() << "("; + else + OS << "(no_name)("; + OS << BB << ")\n"; + } + OS << "Pending Callbacks:\n"; + I = 0; + for (auto BB : Callbacks) { + OS << " " << I << " : "; + ++I; + if (BB->hasName()) + OS << BB->getName() << "("; + else + OS << "(no_name)("; + OS << BB << ")\n"; + } +} +#endif +} // namespace llvm \ No newline at end of file Index: unittests/IR/CMakeLists.txt =================================================================== --- unittests/IR/CMakeLists.txt +++ unittests/IR/CMakeLists.txt @@ -18,6 +18,7 @@ DeferredDominanceTest.cpp DominatorTreeTest.cpp DominatorTreeBatchUpdatesTest.cpp + DomTreeUpdaterTest.cpp FunctionTest.cpp PassBuilderCallbacksTest.cpp IRBuilderTest.cpp Index: unittests/IR/DomTreeUpdaterTest.cpp =================================================================== --- /dev/null +++ unittests/IR/DomTreeUpdaterTest.cpp @@ -0,0 +1,707 @@ +//==- llvm/unittests/IR/DomTreeUpdaterTest.cpp - DomTreeUpdater 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/IR/DomTreeUpdater.h" +#include "llvm/Analysis/PostDominators.h" +#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" +#include + +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(DomTreeUpdater, EagerUpdateBasicOperations) { + 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 %bb1\n" + " i32 1, label %bb2\n" + " i32 2, label %bb3\n" + " i32 3, label %bb1\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 DomTreeUpdater. + DominatorTree DT(*F); + PostDominatorTree PDT(*F); + DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); + + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_TRUE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.flushPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *BB3 = &*FI++; + SwitchInst *SI = dyn_cast(BB0->getTerminator()); + ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; + + // 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}); + + // Invalid Insert: no edge bb1 -> bb2 after change to bb0. + Updates.push_back({DominatorTree::Insert, BB1, BB2}); + // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. + Updates.push_back({DominatorTree::Delete, BB0, BB1}); + + // CFG Change: remove edge bb0 -> bb3. + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u); + BB3->removePredecessor(BB0); + for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { + if (i->getCaseIndex() == 2) { + SI->removeCase(i); + break; + } + } + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); + // 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. + SmallVector BBVec; + BBVec.push_back(BB3); + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB3)); + DTU.applyUpdates(Updates, /*ForceRemoveInvalidUpdates*/ true); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + // DTU working with Eager UpdateStrategy does not need to flush. + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); + + // Test callback utils. + ASSERT_EQ(BB3->getParent(), F); + DTU.callbackDeleteBB(BB3, + [&F](BasicBlock *BB) { ASSERT_NE(BB->getParent(), F); }); + + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + // Remove all case branch to BB1 to test Invalid deletion elimination. + // Code section from llvm::ConstantFoldTerminator + for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { + if (i->getCaseSuccessor() == BB1) { + // Remove this entry. + BB1->removePredecessor(BB0); + i = SI->removeCase(i); + e = SI->case_end(); + DTU.deleteEdge(BB0, BB1, /*ForceRemoveInvalidUpdate*/ true); + } else + ++i; + } + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 2u); + EXPECT_TRUE(DT.verify()); + EXPECT_TRUE(PDT.verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + // Unnecessary flushAll() test + DTU.flushAll(); + EXPECT_TRUE(DT.verify()); + EXPECT_TRUE(PDT.verify()); + + // Remove all case branch to BB2 to test Eager recalculation. + // Code section from llvm::ConstantFoldTerminator + for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { + if (i->getCaseSuccessor() == BB2) { + // Remove this entry. + BB1->removePredecessor(BB0); + i = SI->removeCase(i); + e = SI->case_end(); + } else + ++i; + } + ASSERT_FALSE(DT.verify()); + ASSERT_FALSE(PDT.verify()); + DTU.recalculateAll(*F); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); +} + +TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) { + 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 DTU. + DominatorTree DT(*F); + PostDominatorTree PDT(*F); + DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_TRUE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Eager); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.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); + + DTU.insertEdge(NewEntry, BB0); + + // Changing the Entry BB requires a full recalculation of DomTree. + DTU.recalculateDomTree(*F); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.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 DTU. At this point bb0 now has no predecessors but is still a + // Child of F. + DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0}, + {DominatorTree::Insert, NewEntry, BB1}}); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); + + // Now remove bb0 from F. + ASSERT_FALSE(isa(BB0->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB0)); + DTU.deleteBB(BB0); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); +} + +TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) { + 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 DTU. + DominatorTree DT(*F); + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_FALSE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.flushDomTree().verify()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *BB3 = &*FI++; + + // Test discards of self-domination update. + DTU.deleteEdge(BB0, BB0); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + // Test discards of invalid update (No edge exists between BB1 and BB1). + DTU.insertEdge(BB1, BB1); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + + // 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}); + + // Invalid Insert: no edge bb1 -> bb2 after change to bb0. + Updates.push_back({DominatorTree::Insert, BB1, BB2}); + // Invalid 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); + + // Verify. Updates to DTU must be applied *after* all changes to the CFG + // (including block deletion). + DTU.applyUpdates(Updates); + ASSERT_TRUE(DTU.flushDomTree().verify()); + + // 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 all the pending updates + // are applied to all the holding trees (DomTree/PostDomTree). 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 + // DominatorTrees. This code will crash if it is placed before the + // BranchInst::Create() call above. After a deletion of a BasicBlock. Only an + // explicit flush event can trigger the flushing of deleteBBs. Because some + // passes using Lazy UpdateStrategy rely on this behavior. + + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB3)); + EXPECT_FALSE(DTU.hasPendDeletedBB()); + DTU.deleteBB(BB3); + EXPECT_TRUE(DTU.hasPendingDeletedBB(BB3)); + EXPECT_TRUE(DTU.hasPendDeletedBB()); + ASSERT_TRUE(isa(BB3->getTerminator())); + EXPECT_EQ(BB3->getParent(), F); + DTU.recalculateDomTree(*F); + + EXPECT_FALSE(DTU.hasPendDeletedBB()); +} + +TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) { + 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 DTU. + DominatorTree DT(*F); + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_FALSE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.flushDomTree().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 + // DTU are not. In the first case we must have DTU.insertEdge(Pred1, Succ) + // while in the latter case we must *NOT* have DTU.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); + + // Test callback utils. + std::vector BasicBlocks; + BasicBlocks.push_back(BB1); + BasicBlocks.push_back(BB2); + auto Eraser = [&](BasicBlock *BB) { + BasicBlocks.erase( + std::remove_if(BasicBlocks.begin(), BasicBlocks.end(), + [&](const BasicBlock *i) { return i == BB; }), + BasicBlocks.end()); + }; + ASSERT_EQ(BasicBlocks.size(), static_cast(2)); + // Remove bb2 from F. This has to happen before the call to applyUpdates() for + // DTU 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(DTU.hasPendingDeletedBB(BB2)); + DTU.callbackDeleteBB(BB2, Eraser); + EXPECT_TRUE(DTU.hasPendingDeletedBB(BB2)); + ASSERT_TRUE(isa(BB2->getTerminator())); + EXPECT_EQ(BB2->getParent(), F); + + // Queue up the DTU 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 + // DTU 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(DTU.hasPendingDeletedBB(BB1)); + DTU.callbackDeleteBB(BB1, Eraser); + EXPECT_TRUE(DTU.hasPendingDeletedBB(BB1)); + ASSERT_TRUE(isa(BB1->getTerminator())); + EXPECT_EQ(BB1->getParent(), F); + + // Update the DTU. In this case we don't call DTU.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. + DTU.applyUpdates(Updates); + ASSERT_EQ(BasicBlocks.size(), static_cast(2)); + DTU.flushAll(); + ASSERT_EQ(BasicBlocks.size(), static_cast(0)); + ASSERT_TRUE(DT.verify()); +} + +TEST(DomTreeUpdater, LazyUpdateBasicOperations) { + 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 DTU. + DominatorTree DT(*F); + PostDominatorTree PDT(*F); + DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_TRUE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.flushPostDomTree().verify()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *BB3 = &*FI++; + // Test discards of self-domination update. + DTU.deleteEdge(BB0, BB0); + // Test discards of invalid update (No edge exists between BB1 and BB1). + DTU.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 DTU.flushDomTree 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. + bool CallbackFlag = false; + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB3)); + DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; }); + EXPECT_TRUE(DTU.hasPendingDeletedBB(BB3)); + ASSERT_TRUE(isa(BB3->getTerminator())); + EXPECT_EQ(BB3->getParent(), F); + + // Verify. Updates to DTU must be applied *after* all changes to the CFG + // (including block deletion). + DTU.applyUpdates(Updates); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.hasPendingUpdates()); + ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + ASSERT_TRUE(DTU.hasPendDeletedBB()); + ASSERT_TRUE(DTU.flushPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendDeletedBB()); + ASSERT_EQ(CallbackFlag, true); +} + +TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) { + 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 DTU. + DominatorTree DT(*F); + PostDominatorTree PDT(*F); + DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_TRUE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.flushPostDomTree().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_entry -> bb0. Without this the + // recalculate() call below will not actually recalculate the DT as there + // are no changes pending and no blocks deleted. + DTU.insertEdge(NewEntry, BB0); + + // Changing the Entry BB requires a full recalculation. + DTU.recalculateDomTree(*F); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.flushPostDomTree().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 DTU. At this point bb0 now has no predecessors but is still a + // Child of F. + DTU.applyUpdates({{DominatorTree::Delete, NewEntry, BB0}, + {DominatorTree::Insert, NewEntry, BB1}}); + DTU.flushAll(); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); + + // Now remove bb0 from F. + ASSERT_FALSE(isa(BB0->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB0)); + DTU.deleteBB(BB0); + EXPECT_TRUE(DTU.hasPendingDeletedBB(BB0)); + ASSERT_TRUE(isa(BB0->getTerminator())); + EXPECT_EQ(BB0->getParent(), F); + + // Perform a full recalculation of the DTU. 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. + ASSERT_TRUE(DTU.hasPendDeletedBB()); + DTU.recalculateAll(*F); + ASSERT_FALSE(DTU.hasPendDeletedBB()); +} + +TEST(DomTreeUpdater, LazyUpdateStepTest) { + // This test focus on testing a DTU holding both trees applying multiple + // updates and DT/PDT not flushed together. + 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 %bb1\n" + " i32 1, label %bb2\n" + " i32 2, label %bb3\n" + " i32 3, label %bb1\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 DomTreeUpdater. + DominatorTree DT(*F); + PostDominatorTree PDT(*F); + DomTreeUpdater DTU(DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); + + ASSERT_TRUE(DTU.hasDomTree()); + ASSERT_TRUE(DTU.hasPostDomTree()); + ASSERT_EQ(DTU.getUpdateStrategy(), DomTreeUpdater::UpdateStrategy::Lazy); + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.flushPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *BB3 = &*FI++; + SwitchInst *SI = dyn_cast(BB0->getTerminator()); + ASSERT_NE(SI, nullptr) << "Couldn't get SwitchInst."; + + // Delete edge bb0 -> bb3 and push the update twice to verify duplicate + // entries are discarded. + std::vector Updates; + Updates.reserve(1); + Updates.push_back({DominatorTree::Delete, BB0, BB3}); + + // CFG Change: remove edge bb0 -> bb3. + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 5u); + BB3->removePredecessor(BB0); + for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { + if (i->getCaseIndex() == 2) { + SI->removeCase(i); + break; + } + } + EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 4u); + // 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. + SmallVector BBVec; + BBVec.push_back(BB3); + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.hasPendingDeletedBB(BB3)); + DTU.applyUpdates(Updates); + + // Only flush DomTree. + ASSERT_TRUE(DTU.flushDomTree().verify()); + ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + + // Test callback utils. + ASSERT_EQ(BB3->getParent(), F); + DTU.deleteBB(BB3); + + Updates.clear(); + + // Remove all case branch to BB2 to test Eager recalculation. + // Code section from llvm::ConstantFoldTerminator + for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) { + if (i->getCaseSuccessor() == BB2) { + // Remove this entry. + BB1->removePredecessor(BB0); + i = SI->removeCase(i); + e = SI->case_end(); + Updates.push_back({DominatorTree::Delete, BB0, BB2}); + } else + ++i; + } + + DTU.applyUpdates(Updates); + // flush PostDomTree + ASSERT_TRUE(DTU.flushPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_TRUE(DTU.hasPendingDomTreeUpdates()); + // flush both trees + DTU.flushAll(); + ASSERT_TRUE(DT.verify()); +}