From 21a8b605a1b3672384c7b14804f0288e1778fa36 Mon Sep 17 00:00:00 2001 From: Chijun Sima Date: Fri, 3 Aug 2018 05:08:17 +0000 Subject: [Dominators] Convert existing passes and utils to use the DomTreeUpdater class Summary: This patch is the second in a series of patches related to the [[ http://lists.llvm.org/pipermail/llvm-dev/2018-June/123883.html | RFC - A new dominator tree updater for LLVM ]]. It converts passes (e.g. adce/jump-threading) and various functions which currently accept DDT in local.cpp and BasicBlockUtils.cpp to use the new DomTreeUpdater class. These converted functions in utils can accept DomTreeUpdater with either UpdateStrategy and can deal with both DT and PDT held by the DomTreeUpdater. Reviewers: brzycki, kuhar, dmgreen, grosser, davide Reviewed By: brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D48967 llvm-svn: 338814 --- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp | 64 ++++++++++++++------------- 1 file changed, 33 insertions(+), 31 deletions(-) (limited to 'llvm/lib/Transforms/Utils/BasicBlockUtils.cpp') diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index 516a785dce1..7f61477d961 100644 --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -20,11 +20,12 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" -#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/DomTreeUpdater.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" @@ -37,6 +38,7 @@ #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Support/Casting.h" +#include "llvm/Transforms/Utils/Local.h" #include #include #include @@ -45,7 +47,7 @@ using namespace llvm; -void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) { +void llvm::DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU) { assert((pred_begin(BB) == pred_end(BB) || // Can delete self loop. BB->getSinglePredecessor() == BB) && "Block is not dead!"); @@ -54,11 +56,11 @@ void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) { // Loop through all of our successors and make sure they know that one // of their predecessors is going away. - if (DDT) + if (DTU) Updates.reserve(BBTerm->getNumSuccessors()); for (BasicBlock *Succ : BBTerm->successors()) { Succ->removePredecessor(BB); - if (DDT) + if (DTU) Updates.push_back({DominatorTree::Delete, BB, Succ}); } @@ -74,10 +76,15 @@ void llvm::DeleteDeadBlock(BasicBlock *BB, DeferredDominance *DDT) { I.replaceAllUsesWith(UndefValue::get(I.getType())); BB->getInstList().pop_back(); } - - if (DDT) { - DDT->applyUpdates(Updates); - DDT->deleteBB(BB); // Deferred deletion of BB. + new UnreachableInst(BB->getContext(), BB); + assert(BB->getInstList().size() == 1 && + isa(BB->getTerminator()) && + "The successor list of BB isn't empty before " + "applying corresponding DTU updates."); + + if (DTU) { + DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->deleteBB(BB); } else { BB->eraseFromParent(); // Zap the block! } @@ -115,11 +122,9 @@ bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) { return Changed; } -bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, +bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, LoopInfo *LI, - MemoryDependenceResults *MemDep, - DeferredDominance *DDT) { - assert(!(DT && DDT) && "Cannot call with both DT and DDT."); + MemoryDependenceResults *MemDep) { if (BB->hasAddressTaken()) return false; @@ -154,10 +159,10 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, FoldSingleEntryPHINodes(BB, MemDep); } - // Deferred DT update: Collect all the edges that exit BB. These - // dominator edges will be redirected from Pred. + // DTU update: Collect all the edges that exit BB. + // These dominator edges will be redirected from Pred. std::vector Updates; - if (DDT) { + if (DTU) { Updates.reserve(1 + (2 * succ_size(BB))); Updates.push_back({DominatorTree::Delete, PredBB, BB}); for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { @@ -175,6 +180,7 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, // Move all definitions in the successor to the predecessor... PredBB->getInstList().splice(PredBB->end(), BB->getInstList()); + new UnreachableInst(BB->getContext(), BB); // Eliminate duplicate dbg.values describing the entry PHI node post-splice. for (auto Incoming : IncomingValues) { @@ -195,28 +201,24 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, if (!PredBB->hasName()) PredBB->takeName(BB); - // Finally, erase the old block and update dominator info. - if (DT) - if (DomTreeNode *DTN = DT->getNode(BB)) { - DomTreeNode *PredDTN = DT->getNode(PredBB); - SmallVector Children(DTN->begin(), DTN->end()); - for (DomTreeNode *DI : Children) - DT->changeImmediateDominator(DI, PredDTN); - - DT->eraseNode(BB); - } - if (LI) LI->removeBlock(BB); if (MemDep) MemDep->invalidateCachedPredecessors(); - if (DDT) { - DDT->deleteBB(BB); // Deferred deletion of BB. - DDT->applyUpdates(Updates); - } else { - BB->eraseFromParent(); // Nuke BB. + // Finally, erase the old block and update dominator info. + if (DTU) { + assert(BB->getInstList().size() == 1 && + isa(BB->getTerminator()) && + "The successor list of BB isn't empty before " + "applying corresponding DTU updates."); + DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true); + DTU->deleteBB(BB); + } + + else { + BB->eraseFromParent(); // Nuke BB if DTU is nullptr. } return true; } -- cgit v1.2.3