Index: include/llvm/IR/DomTreeUpdater.h =================================================================== --- /dev/null +++ include/llvm/IR/DomTreeUpdater.h @@ -0,0 +1,242 @@ +//===- 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" +#include + +namespace llvm { +class DomTreeUpdater { +public: + enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; + + explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} + DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) + : DT(&DT_), Strategy(Strategy_) {} + DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) + : PDT(&PDT_), Strategy(Strategy_) {} + DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, + UpdateStrategy Strategy_) + : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} + + ~DomTreeUpdater() { flush(); } + + /// Returns the UpdateStrategy of the class instance. + UpdateStrategy getUpdateStrategy() const { return Strategy; }; + + /// Returns true if it holds a DominatorTree. + bool hasDomTree() const { return DT != nullptr; } + + /// Returns true if it holds a PostDominatorTree. + bool hasPostDomTree() const { return PDT != nullptr; } + + /// Returns true if there is BasicBlock awaiting deletion. + /// The deletion will only happen until a flush event and + /// all available trees are up-to-date. + /// Returns false under Eager UpdateStrategy. + bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); } + + /// Returns true if DelBB is awaiting deletion. + /// Returns false under Eager UpdateStrategy. + bool isBBPendingDeletion(BasicBlock *DelBB) const; + + /// Returns true if either of DT or PDT is valid and the tree has at + /// least one update pending. If DT or PDT is nullptr it is treated + /// as having no pending updates. This function does not check + /// whether there is BasicBlock awaiting deletion. + /// Returns false under Eager UpdateStrategy. + bool hasPendingUpdates() const; + + /// Returns true if there are DominatorTree updates queued. + /// Returns false under Eager UpdateStrategy. + bool hasPendingDomTreeUpdates() const; + + /// Returns true if there are PostDominatorTree updates queued. + /// Returns false under Eager UpdateStrategy. + bool hasPendingPostDomTreeUpdates() const; + + /// Apply updates on all available trees. Under Eager UpdateStrategy with + /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will + /// discard duplicated updates and self-dominance updates. The Eager + /// Strategy applies the updates immediately while the Lazy Strategy + /// queues the updates. It is required for the state of + /// the LLVM IR to be updated *before* applying the Updates because the + /// internal update routine will analyze the current state of the relationship + /// between a pair of (From, To) BasicBlocks to determine whether a single + /// update needs to be discarded. + void applyUpdates(ArrayRef Updates, + bool ForceRemoveDuplicates = false); + + /// Notify all available trees on an edge insertion. Under either Strategy, + /// self-dominance update will be removed. The Eager Strategy applies + /// the update immediately while the Lazy Strategy queues the update. + /// It is recommended to only use this method when you have exactly one + /// insertion (and no deletions). It is recommended to use applyUpdates() in + /// all other cases. This function has to be called *after* making the update + /// on the actual CFG. An internal functions checks if the edge exists in the + /// CFG in DEBUG mode. + void insertEdge(BasicBlock *From, BasicBlock *To); + + /// Notify all available trees on an edge insertion. + /// Under either Strategy, these updates will be discard silently in the + /// following sequence + /// 1. Invalid - Inserting an edge that does not exist in the CFG. + /// 2. Self-dominance update. + /// The Eager Strategy applies the update immediately while the Lazy Strategy + /// queues the update. It is recommended to only use this method when you have + /// exactly one insertion (and no deletions) and want to discard an invalid + /// update. Returns true if the update is valid. + bool insertEdgeRelaxed(BasicBlock *From, BasicBlock *To); + + /// Notify all available trees on an edge deletion. Under either Strategy, + /// self-dominance update will be removed. The Eager Strategy applies + /// the update immediately while the Lazy Strategy queues the update. + /// It is recommended to only use this method when you have exactly one + /// deletion (and no insertions). It is recommended to use applyUpdates() in + /// all other cases. This function has to be called *after* making the update + /// on the actual CFG. An internal functions checks if the edge doesn't exist + /// in the CFG in DEBUG mode. + void deleteEdge(BasicBlock *From, BasicBlock *To); + + /// Notify all available trees on an edge deletion. + /// Under either Strategy, these updates will be discard silently in the + /// following sequence: + /// 1. Invalid - Deleting an edge that still exists in the CFG. + /// 2. Self-dominance update. + /// The Eager Strategy applies the update immediately while the Lazy Strategy + /// queues the update. It is recommended to only use this method when you have + /// exactly one deletion (and no insertions) and want to discard an invalid + /// update. Returns true if the update is valid. + bool deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To); + + /// Delete DelBB. DelBB will be removed from its Parent and + /// erased from available trees if it exists and finally get deleted. + /// Under Eager UpdateStrategy, DelBB will be processed immediately. + /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and + /// all available trees are up-to-date. + void deleteBB(BasicBlock *DelBB); + + /// Delete DelBB. DelBB will be removed from its Parent and + /// erased from available trees if it exists. Then the callback will + /// be called. Finally, DelBB will be deleted. + /// Under Eager UpdateStrategy, DelBB will be processed immediately. + /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and + /// all available trees are up-to-date. + /// Multiple callbacks can be queued for one DelBB under Lazy UpdateStrategy. + void callbackDeleteBB(BasicBlock *DelBB, + function_ref Callback); + + /// Recalculate all available trees. + /// Under Lazy Strategy, available trees will only be recalculated if there + /// are pending updates or there is BasicBlock awaiting deletion. Returns true + /// if at least one tree is recalculated. + bool recalculate(Function &F); + + /// Flush DomTree updates and return DomTree. + /// It also flush out of date updates applied by all available trees + /// and flush Deleted BBs if both trees are up-to-date. + /// It must only be called when it has a DomTree. + DominatorTree &getDomTree(); + + /// Flush PostDomTree updates and return PostDomTree. + /// It also flush out of date updates applied by all available trees + /// and flush Deleted BBs if both trees are up-to-date. + /// It must only be called when it has a PostDomTree. + PostDominatorTree &getPostDomTree(); + + /// Apply all pending updates to available trees and flush all BasicBlocks + /// awaiting deletion. + /// Does nothing under Eager UpdateStrategy. + void flush(); + + /// Debug method to help view the internal state of this class. + 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 Strategy; + SmallPtrSet DeletedBBs; + std::vector Callbacks; + bool IsRecalculatingDomTree = false; + bool IsRecalculatingPostDomTree = false; + + /// First remove all the instructions of DelBB and then make sure DelBB has a + /// valid terminator instruction which is necessary to have when DelBB still + /// has to be inside of its parent Function while awaiting deletion under Lazy + /// UpdateStrategy to prevent other routines from asserting the state of the + /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. + void validateDeleteBB(BasicBlock *DelBB); + + /// Returns true if at least one BasicBlock is deleted. + bool forceFlushDeletedBB(); + + /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy + /// UpdateStrategy. Returns true if the update is queued for update. + bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, + BasicBlock *To); + + /// Helper function to apply all pending DomTree updates. + void applyDomTreeUpdates(); + + /// Helper function to apply all pending PostDomTree updates. + void applyPostDomTreeUpdates(); + + /// Helper function to flush deleted BasicBlocks if all available + /// trees are up-to-date. + void tryFlushDeletedBB(); + + /// Drop all updates applied by all available trees and delete BasicBlocks if + /// all available trees are up-to-date. + void dropOutOfDateUpdates(); + + /// Erase Basic Block node that has been unlinked from Function + /// in the DomTree and PostDomTree. + void eraseDelBBNode(BasicBlock *DelBB); + + /// Returns true if the update appears in the LLVM IR. + /// It is used to check whether an update is valid in + /// insertEdge/deleteEdge or is unnecessary in the batch update. + bool isUpdateValid(DominatorTree::UpdateType Update) const; + + /// Returns true if the update is self dominance. + bool isSelfDominance(DominatorTree::UpdateType Update) const; +}; +} // namespace llvm + +#endif // LLVM_DOMTREEUPDATER_H Index: include/llvm/module.modulemap =================================================================== --- include/llvm/module.modulemap +++ include/llvm/module.modulemap @@ -196,6 +196,8 @@ module IR_CFG { header "IR/CFG.h" export * } module IR_ConstantRange { header "IR/ConstantRange.h" export * } module IR_Dominators { header "IR/Dominators.h" export * } + module Analysis_PostDominators { header "Analysis/PostDominators.h" export * } + module IR_DomTreeUpdater { header "IR/DomTreeUpdater.h" export * } module IR_IRBuilder { header "IR/IRBuilder.h" export * } module IR_PassManager { header "IR/PassManager.h" export * } module IR_PredIteratorCache { header "IR/PredIteratorCache.h" export * } 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,511 @@ +//===- 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(); + + // 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 = llvm::any_of( + successors(From), [To](const BasicBlock *B) { return B == To; }); + + // If the IR does not match the update, + // 1. In batch updates, this update is unnecessary. + // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid. + // Edge does not exist in IR. + if (Kind == DominatorTree::Insert && !HasEdge) + return false; + + // Edge exists in IR. + if (Kind == DominatorTree::Delete && HasEdge) + return false; + + return true; +} + +bool DomTreeUpdater::isSelfDominance( + const DominatorTree::UpdateType Update) const { + // Won't affect DomTree and PostDomTree. + return Update.getFrom() == Update.getTo(); +} + +bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind, + BasicBlock *From, BasicBlock *To) { + assert(Strategy == 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); + const auto E = PendUpdates.end(); + + assert(I <= E && "Iterator out of range."); + + 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() { + // No pending DomTreeUpdates. + if (Strategy != UpdateStrategy::Lazy || !DT) + return; + + // Only apply updates not are applied by DomTree. + if (hasPendingDomTreeUpdates()) { + const auto I = PendUpdates.begin() + PendDTUpdateIndex; + const auto E = PendUpdates.end(); + assert(I < E && "Iterator range invalid; there should be DomTree updates."); + DT->applyUpdates(ArrayRef(I, E)); + PendDTUpdateIndex = PendUpdates.size(); + } +} + +void DomTreeUpdater::flush() { + applyDomTreeUpdates(); + applyPostDomTreeUpdates(); + dropOutOfDateUpdates(); +} + +void DomTreeUpdater::applyPostDomTreeUpdates() { + // No pending PostDomTreeUpdates. + if (Strategy != UpdateStrategy::Lazy || !PDT) + return; + + // Only apply updates not are applied by PostDomTree. + if (hasPendingPostDomTreeUpdates()) { + const auto I = PendUpdates.begin() + PendPDTUpdateIndex; + const auto E = PendUpdates.end(); + assert(I < E && + "Iterator range invalid; there should be PostDomTree updates."); + PDT->applyUpdates(ArrayRef(I, E)); + PendPDTUpdateIndex = PendUpdates.size(); + } +} + +void DomTreeUpdater::tryFlushDeletedBB() { + if (!hasPendingUpdates()) + forceFlushDeletedBB(); +} + +bool DomTreeUpdater::forceFlushDeletedBB() { + if (DeletedBBs.empty()) + return false; + + for (auto *BB : DeletedBBs) { + BB->removeFromParent(); + eraseDelBBNode(BB); + delete BB; + } + DeletedBBs.clear(); + Callbacks.clear(); + return true; +} + +bool DomTreeUpdater::recalculate(Function &F) { + if (!DT && !PDT) + return false; + + if (Strategy == UpdateStrategy::Eager) { + if (DT) + DT->recalculate(F); + if (PDT) + PDT->recalculate(F); + return true; + } + + // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = true; + + // Because all trees are going to be up-to-date after recalculation, + // flush awaiting deleted BasicBlocks. + if (forceFlushDeletedBB() || hasPendingUpdates()) { + if (DT) + DT->recalculate(F); + if (PDT) + PDT->recalculate(F); + + // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; + PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size(); + dropOutOfDateUpdates(); + return true; + } + + // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes. + IsRecalculatingDomTree = IsRecalculatingPostDomTree = false; + return false; +} + +bool DomTreeUpdater::hasPendingUpdates() const { + return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates(); +} + +bool DomTreeUpdater::hasPendingDomTreeUpdates() const { + if (!DT) + return false; + return PendUpdates.size() != PendDTUpdateIndex; +} + +bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const { + if (!PDT) + return false; + return PendUpdates.size() != PendPDTUpdateIndex; +} + +bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const { + if (Strategy == 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 (Strategy == UpdateStrategy::Lazy) { + DeletedBBs.insert(DelBB); + return; + } + + DelBB->removeFromParent(); + eraseDelBBNode(DelBB); + delete DelBB; +} + +void DomTreeUpdater::callbackDeleteBB( + BasicBlock *DelBB, function_ref Callback) { + validateDeleteBB(DelBB); + if (Strategy == 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)) + DT->eraseNode(DelBB); + + if (PDT && !IsRecalculatingPostDomTree) + if (PDT->getNode(DelBB)) + 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 ForceRemoveDuplicates) { + if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) { + SmallVector Seen; + for (const auto U : Updates) + // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save + // on analysis. + if (llvm::none_of( + Seen, + [U](const DominatorTree::UpdateType S) { return S == U; }) && + isUpdateValid(U) && !isSelfDominance(U)) { + Seen.push_back(U); + if (Strategy == UpdateStrategy::Lazy) + applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo()); + } + if (Strategy == 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::getDomTree() { + assert(DT && "Invalid acquisition of a null DomTree"); + applyDomTreeUpdates(); + dropOutOfDateUpdates(); + return *DT; +} + +PostDominatorTree &DomTreeUpdater::getPostDomTree() { + assert(PDT && "Invalid acquisition of a null PostDomTree"); + applyPostDomTreeUpdates(); + dropOutOfDateUpdates(); + return *PDT; +} + +void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) { + +#ifndef NDEBUG + assert(isUpdateValid({DominatorTree::Insert, From, To}) && + "Inserted edge does not appear in the CFG"); +#endif + + // Won't affect DomTree and PostDomTree; discard update. + if (From == To) + return; + + if (Strategy == UpdateStrategy::Eager) { + if (DT) + DT->insertEdge(From, To); + if (PDT) + PDT->insertEdge(From, To); + return; + } + + applyLazyUpdate(DominatorTree::Insert, From, To); +} + +bool DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) { + if (!isUpdateValid({DominatorTree::Insert, From, To})) + return false; + + if (From == To) + return true; + + if (Strategy == UpdateStrategy::Eager) { + if (DT) + DT->insertEdge(From, To); + if (PDT) + PDT->insertEdge(From, To); + return true; + } + + applyLazyUpdate(DominatorTree::Insert, From, To); + return true; +} + +void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) { + +#ifndef NDEBUG + assert(isUpdateValid({DominatorTree::Delete, From, To}) && + "Deleted edge still exists in the CFG!"); +#endif + + // Won't affect DomTree and PostDomTree; discard update. + if (From == To) + return; + + if (Strategy == UpdateStrategy::Eager) { + if (DT) + DT->deleteEdge(From, To); + if (PDT) + PDT->deleteEdge(From, To); + return; + } + + applyLazyUpdate(DominatorTree::Delete, From, To); +} + +bool DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) { + if (!isUpdateValid({DominatorTree::Delete, From, To})) + return false; + + if (From == To) + return true; + + if (Strategy == UpdateStrategy::Eager) { + if (DT) + DT->deleteEdge(From, To); + if (PDT) + PDT->deleteEdge(From, To); + return true; + } + + applyLazyUpdate(DominatorTree::Delete, From, To); + return true; +} + +void DomTreeUpdater::dropOutOfDateUpdates() { + if (Strategy == DomTreeUpdater::UpdateStrategy::Eager) + return; + + tryFlushDeletedBB(); + + // Drop all updates applied by both trees. + if (!DT) + PendDTUpdateIndex = PendUpdates.size(); + if (!PDT) + PendPDTUpdateIndex = PendUpdates.size(); + + const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex); + const auto B = PendUpdates.begin(); + const auto E = PendUpdates.begin() + dropIndex; + assert(B <= E && "Iterator out of range."); + PendUpdates.erase(B, E); + // Calculate current 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 << "Available Trees: "; + if (DT || PDT) { + if (DT) + OS << "DomTree "; + if (PDT) + OS << "PostDomTree "; + OS << "\n"; + } else + OS << "None\n"; + + OS << "UpdateStrategy: "; + if (Strategy == UpdateStrategy::Eager) { + OS << "Eager\n"; + return; + } else + OS << "Lazy\n"; + int Index = 0; + + auto printUpdates = + [&](ArrayRef::const_iterator begin, + ArrayRef::const_iterator end) { + if (begin == end) + OS << " None\n"; + Index = 0; + for (auto It = begin, ItEnd = end; It != ItEnd; ++It) { + auto U = *It; + OS << " " << Index << " : "; + ++Index; + 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) { + const auto I = PendUpdates.begin() + PendDTUpdateIndex; + assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && + "Iterator out of range."); + OS << "Applied but not cleared DomTreeUpdates:\n"; + printUpdates(PendUpdates.begin(), I); + OS << "Pending DomTreeUpdates:\n"; + printUpdates(I, PendUpdates.end()); + } + + if (PDT) { + const auto I = PendUpdates.begin() + PendPDTUpdateIndex; + assert(PendUpdates.begin() <= I && I <= PendUpdates.end() && + "Iterator out of range."); + OS << "Applied but not cleared PostDomTreeUpdates:\n"; + printUpdates(PendUpdates.begin(), I); + OS << "Pending PostDomTreeUpdates:\n"; + printUpdates(I, PendUpdates.end()); + } + + OS << "Pending DeletedBBs:\n"; + Index = 0; + for (auto BB : DeletedBBs) { + OS << " " << Index << " : "; + ++Index; + if (BB->hasName()) + OS << BB->getName() << "("; + else + OS << "(no_name)("; + OS << BB << ")\n"; + } + + OS << "Pending Callbacks:\n"; + Index = 0; + for (auto BB : Callbacks) { + OS << " " << Index << " : "; + ++Index; + if (BB->hasName()) + OS << BB->getName() << "("; + else + OS << "(no_name)("; + OS << BB << ")\n"; + } +} +#endif +} // namespace llvm 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,693 @@ +//==- 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 = R"( + define i32 @f(i32 %i, i32 *%p) { + bb0: + store i32 %i, i32 *%p + switch i32 %i, label %bb1 [ + i32 1, label %bb2 + i32 2, label %bb3 + ] + bb1: + ret i32 1 + bb2: + ret i32 2 + bb3: + ret i32 3 + })"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().verify()); + ASSERT_TRUE(DTU.getPostDomTree().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."; + + ASSERT_FALSE(DTU.insertEdgeRelaxed(BB0, BB0)); + ASSERT_TRUE(DTU.deleteEdgeRelaxed(BB0, BB0)); + + // 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(), 3u); + BB3->removePredecessor(BB0); + for (auto i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { + if (i->getCaseSuccessor() == BB3) { + SI->removeCase(i); + break; + } + } + 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. + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); + DTU.applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + // Invalid Insert: no edge bb1 -> bb2 after change to bb0. + ASSERT_FALSE(DTU.insertEdgeRelaxed(BB1, BB2)); + // Invalid Delete: edge exists bb0 -> bb1 after change to bb0. + ASSERT_FALSE(DTU.deleteEdgeRelaxed(BB0, BB1)); + + // 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()); + + // Unnecessary flush() test + DTU.flush(); + 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. + BB2->removePredecessor(BB0); + i = SI->removeCase(i); + e = SI->case_end(); + } else + ++i; + } + ASSERT_FALSE(DT.verify()); + ASSERT_FALSE(PDT.verify()); + DTU.recalculate(*F); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); +} + +TEST(DomTreeUpdater, EagerUpdateReplaceEntryBB) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f() { + bb0: + br label %bb1 + bb1: + ret i32 1 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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); + + ASSERT_TRUE(DTU.insertEdgeRelaxed(NewEntry, BB0)); + + // Changing the Entry BB requires a full recalculation of DomTree. + DTU.recalculate(*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.isBBPendingDeletion(BB0)); + DTU.deleteBB(BB0); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); +} + +TEST(DomTreeUpdater, LazyUpdateDTBasicOperations) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f(i32 %i, i32 *%p) { + bb0: + store i32 %i, i32 *%p + switch i32 %i, label %bb1 [ + i32 0, label %bb2 + i32 1, label %bb2 + i32 2, label %bb3 + ] + bb1: + ret i32 1 + bb2: + ret i32 2 + bb3: + ret i32 3 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().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()); + + // 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.getDomTree().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 trees held by the DomTreeUpdater (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.isBBPendingDeletion(BB3)); + EXPECT_FALSE(DTU.hasPendingDeletedBB()); + DTU.deleteBB(BB3); + EXPECT_TRUE(DTU.isBBPendingDeletion(BB3)); + EXPECT_TRUE(DTU.hasPendingDeletedBB()); + ASSERT_TRUE(isa(BB3->getTerminator())); + EXPECT_EQ(BB3->getParent(), F); + DTU.recalculate(*F); + + EXPECT_FALSE(DTU.hasPendingDeletedBB()); +} + +TEST(DomTreeUpdater, LazyUpdateDTInheritedPreds) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f(i32 %i, i32 *%p) { + bb0: + store i32 %i, i32 *%p + switch i32 %i, label %bb1 [ + i32 2, label %bb2 + i32 3, label %bb3 + ] + bb1: + br label %bb3 + bb2: + br label %bb3 + bb3: + ret i32 3 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().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.isBBPendingDeletion(BB2)); + DTU.callbackDeleteBB(BB2, Eraser); + EXPECT_TRUE(DTU.isBBPendingDeletion(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.isBBPendingDeletion(BB1)); + DTU.callbackDeleteBB(BB1, Eraser); + EXPECT_TRUE(DTU.isBBPendingDeletion(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.flush(); + ASSERT_EQ(BasicBlocks.size(), static_cast(0)); + ASSERT_TRUE(DT.verify()); +} + +TEST(DomTreeUpdater, LazyUpdateBasicOperations) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f(i32 %i, i32 *%p) { + bb0: + store i32 %i, i32 *%p + switch i32 %i, label %bb1 [ + i32 0, label %bb2 + i32 1, label %bb2 + i32 2, label %bb3 + ] + bb1: + ret i32 1 + bb2: + ret i32 2 + bb3: + ret i32 3 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().verify()); + ASSERT_TRUE(DTU.getPostDomTree().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); + + // 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.isBBPendingDeletion(BB3)); + DTU.callbackDeleteBB(BB3, [&](BasicBlock *) { CallbackFlag = true; }); + EXPECT_TRUE(DTU.isBBPendingDeletion(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.getDomTree().verify()); + ASSERT_TRUE(DTU.hasPendingUpdates()); + ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + ASSERT_TRUE(DTU.hasPendingDeletedBB()); + ASSERT_TRUE(DTU.getPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDeletedBB()); + ASSERT_EQ(CallbackFlag, true); +} + +TEST(DomTreeUpdater, LazyUpdateReplaceEntryBB) { + StringRef FuncName = "f"; + StringRef ModuleString = R"( + define i32 @f() { + bb0: + br label %bb1 + bb1: + ret i32 1 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().verify()); + ASSERT_TRUE(DTU.getPostDomTree().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.recalculate(*F); + ASSERT_TRUE(DTU.getDomTree().verify()); + ASSERT_TRUE(DTU.getPostDomTree().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.flush(); + ASSERT_TRUE(DT.verify()); + ASSERT_TRUE(PDT.verify()); + + // Now remove bb0 from F. + ASSERT_FALSE(isa(BB0->getTerminator())); + EXPECT_FALSE(DTU.isBBPendingDeletion(BB0)); + DTU.deleteBB(BB0); + EXPECT_TRUE(DTU.isBBPendingDeletion(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.hasPendingDeletedBB()); + DTU.recalculate(*F); + ASSERT_FALSE(DTU.hasPendingDeletedBB()); +} + +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 = R"( + define i32 @f(i32 %i, i32 *%p) { + bb0: + store i32 %i, i32 *%p + switch i32 %i, label %bb1 [ + i32 0, label %bb1 + i32 1, label %bb2 + i32 2, label %bb3 + i32 3, label %bb1 + ] + bb1: + ret i32 1 + bb2: + ret i32 2 + bb3: + ret i32 3 + } + )"; + // Make the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + Function *F = M->getFunction(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.getDomTree().verify()); + ASSERT_TRUE(DTU.getPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingUpdates()); + + Function::iterator FI = F->begin(); + BasicBlock *BB0 = &*FI++; + 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. + ASSERT_FALSE(isa(BB3->getTerminator())); + EXPECT_FALSE(DTU.isBBPendingDeletion(BB3)); + DTU.applyUpdates(Updates); + + // Only flush DomTree. + ASSERT_TRUE(DTU.getDomTree().verify()); + ASSERT_TRUE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_FALSE(DTU.hasPendingDomTreeUpdates()); + + 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. + BB2->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.getPostDomTree().verify()); + ASSERT_FALSE(DTU.hasPendingPostDomTreeUpdates()); + ASSERT_TRUE(DTU.hasPendingDomTreeUpdates()); + // flush both trees + DTU.flush(); + ASSERT_TRUE(DT.verify()); +}