[ADCE][Dominators] Reapply: Teach ADCE to preserve dominators
Summary:
This patch teaches ADCE to preserve both DominatorTrees and PostDominatorTrees.
This is reapplies the original patch r311057 that was reverted in r311381.
The previous version wasn't using the batch update api for updating dominators,
which in vary rare cases caused assertion failures.
This also fixes PR34258.
Reviewers: dberlin, chandlerc, sanjoy, davide, grosser, brzycki
Reviewed By: davide
Subscribers: grandinj, zhendongsu, llvm-commits, david2050
Differential Revision: https://reviews.llvm.org/D35869
llvm-svn: 311467
diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp
index 9d45c3d..c47e904 100644
--- a/llvm/lib/Transforms/Scalar/ADCE.cpp
+++ b/llvm/lib/Transforms/Scalar/ADCE.cpp
@@ -27,6 +27,7 @@
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
@@ -89,6 +90,10 @@
class AggressiveDeadCodeElimination {
Function &F;
+
+ // ADCE does not use DominatorTree per se, but it updates it to preserve the
+ // analysis.
+ DominatorTree &DT;
PostDominatorTree &PDT;
/// Mapping of blocks to associated information, an element in BlockInfoVec.
@@ -157,9 +162,10 @@
void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
public:
- AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
- : F(F), PDT(PDT) {}
- bool performDeadCodeElimination();
+ AggressiveDeadCodeElimination(Function &F, DominatorTree &DT,
+ PostDominatorTree &PDT)
+ : F(F), DT(DT), PDT(PDT) {}
+ bool performDeadCodeElimination();
};
}
@@ -557,14 +563,34 @@
}
assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
"Failed to find safe successor for dead branch");
+
+ // Collect removed successors to update the (Post)DominatorTrees.
+ SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
bool First = true;
for (auto *Succ : successors(BB)) {
- if (!First || Succ != PreferredSucc->BB)
+ if (!First || Succ != PreferredSucc->BB) {
Succ->removePredecessor(BB);
- else
+ RemovedSuccessors.insert(Succ);
+ } else
First = false;
}
makeUnconditional(BB, PreferredSucc->BB);
+
+ // Inform the dominators about the deleted CFG edges.
+ SmallVector<DominatorTree::UpdateType, 4> DeletedEdges;
+ for (auto *Succ : RemovedSuccessors) {
+ // It might have happened that the same successor appeared multiple times
+ // and the CFG edge wasn't really removed.
+ if (Succ != PreferredSucc->BB) {
+ DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
+ << BB->getName() << " -> " << Succ->getName() << "\n");
+ DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
+ }
+ }
+
+ DT.applyUpdates(DeletedEdges);
+ PDT.applyUpdates(DeletedEdges);
+
NumBranchesRemoved += 1;
}
}
@@ -609,6 +635,9 @@
InstInfo[NewTerm].Live = true;
if (const DILocation *DL = PredTerm->getDebugLoc())
NewTerm->setDebugLoc(DL);
+
+ InstInfo.erase(PredTerm);
+ PredTerm->eraseFromParent();
}
//===----------------------------------------------------------------------===//
@@ -617,13 +646,16 @@
//
//===----------------------------------------------------------------------===//
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
+ auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
- if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
+ if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
return PreservedAnalyses::all();
PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>();
PA.preserve<GlobalsAA>();
+ PA.preserve<DominatorTreeAnalysis>();
+ PA.preserve<PostDominatorTreeAnalysis>();
return PA;
}
@@ -637,14 +669,23 @@
bool runOnFunction(Function &F) override {
if (skipFunction(F))
return false;
+
+ auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
- return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
+ return AggressiveDeadCodeElimination(F, DT, PDT)
+ .performDeadCodeElimination();
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
+ // We require DominatorTree here only to update and thus preserve it.
+ AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<PostDominatorTreeWrapperPass>();
if (!RemoveControlFlowFlag)
AU.setPreservesCFG();
+ else {
+ AU.addPreserved<DominatorTreeWrapperPass>();
+ AU.addPreserved<PostDominatorTreeWrapperPass>();
+ }
AU.addPreserved<GlobalsAAWrapperPass>();
}
};
@@ -653,6 +694,7 @@
char ADCELegacyPass::ID = 0;
INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
"Aggressive Dead Code Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
false, false)