[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
diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp
index 516a785..7f61477 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 <cassert>
#include <cstdint>
#include <string>
@@ -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 @@
// 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 @@
I.replaceAllUsesWith(UndefValue::get(I.getType()));
BB->getInstList().pop_back();
}
+ new UnreachableInst(BB->getContext(), BB);
+ assert(BB->getInstList().size() == 1 &&
+ isa<UnreachableInst>(BB->getTerminator()) &&
+ "The successor list of BB isn't empty before "
+ "applying corresponding DTU updates.");
- if (DDT) {
- DDT->applyUpdates(Updates);
- DDT->deleteBB(BB); // Deferred deletion of BB.
+ if (DTU) {
+ DTU->applyUpdates(Updates, /*ForceRemoveDuplicates*/ true);
+ DTU->deleteBB(BB);
} else {
BB->eraseFromParent(); // Zap the block!
}
@@ -115,11 +122,9 @@
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 @@
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<DominatorTree::UpdateType> 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 @@
// 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 @@
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<DomTreeNode *, 8> 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<UnreachableInst>(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;
}