summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/lib/Transforms/Scalar/ADCE.cpp56
-rw-r--r--llvm/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll24
-rw-r--r--llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll39
-rw-r--r--llvm/test/Transforms/ADCE/unreachable.ll18
4 files changed, 130 insertions, 7 deletions
diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp
index 9d45c3da38f..c47e904692d 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 @@ struct BlockInfoType {
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 @@ class AggressiveDeadCodeElimination {
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 @@ void AggressiveDeadCodeElimination::updateDeadRegions() {
}
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 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
InstInfo[NewTerm].Live = true;
if (const DILocation *DL = PredTerm->getDebugLoc())
NewTerm->setDebugLoc(DL);
+
+ InstInfo.erase(PredTerm);
+ PredTerm->eraseFromParent();
}
//===----------------------------------------------------------------------===//
@@ -617,13 +646,16 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
//
//===----------------------------------------------------------------------===//
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 @@ struct ADCELegacyPass : public FunctionPass {
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 @@ struct ADCELegacyPass : public FunctionPass {
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)
diff --git a/llvm/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll b/llvm/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll
new file mode 100644
index 00000000000..e532f29e9f4
--- /dev/null
+++ b/llvm/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll
@@ -0,0 +1,24 @@
+; RUN: opt < %s -adce | llvm-dis
+; RUN: opt < %s -adce -verify-dom-info | llvm-dis
+
+define void @foo() {
+entry:
+ br label %switch
+switch: ; preds = %entry
+ switch i32 undef, label %default [
+ i32 2, label %two
+ i32 5, label %five
+ i32 4, label %four
+ ]
+four: ; preds = %switch
+ br label %exit
+five: ; preds = %switch
+ br label %exit
+two: ; preds = %switch
+ br label %exit
+default: ; preds = %switch
+ br label %exit
+exit: ; preds = %default, %two, %five, %four
+ ret void
+}
+
diff --git a/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll b/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll
new file mode 100644
index 00000000000..018eb79b26f
--- /dev/null
+++ b/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll
@@ -0,0 +1,39 @@
+; RUN: opt < %s -gvn -simplifycfg -adce | llvm-dis
+; RUN: opt < %s -gvn -simplifycfg -adce -verify-dom-info | llvm-dis
+
+; This test makes sure that the DominatorTree properly handles
+; deletion of edges that go to forward-unreachable regions.
+; In this case, %land.end is already forward unreachable when
+; the DT gets informed about the deletion of %entry -> %land.end.
+
+@a = common global i32 0, align 4
+
+define i32 @main() {
+entry:
+ %retval = alloca i32, align 4
+ store i32 0, i32* %retval, align 4
+ %0 = load i32, i32* @a, align 4
+ %cmp = icmp ne i32 %0, 1
+ br i1 %cmp, label %land.rhs, label %land.end4
+
+land.rhs: ; preds = %entry
+ %1 = load i32, i32* @a, align 4
+ %tobool = icmp ne i32 %1, 0
+ br i1 %tobool, label %land.rhs1, label %land.end
+
+land.rhs1: ; preds = %land.rhs
+ br label %land.end
+
+land.end: ; preds = %land.rhs1, %land.rhs
+ %2 = phi i1 [ false, %land.rhs ], [ true, %land.rhs1 ]
+ %land.ext = zext i1 %2 to i32
+ %conv = trunc i32 %land.ext to i16
+ %conv2 = sext i16 %conv to i32
+ %tobool3 = icmp ne i32 %conv2, 0
+ br label %land.end4
+
+land.end4: ; preds = %land.end, %entry
+ %3 = phi i1 [ false, %entry ], [ %tobool3, %land.end ]
+ %land.ext5 = zext i1 %3 to i32
+ ret i32 0
+}
diff --git a/llvm/test/Transforms/ADCE/unreachable.ll b/llvm/test/Transforms/ADCE/unreachable.ll
new file mode 100644
index 00000000000..aaacc184225
--- /dev/null
+++ b/llvm/test/Transforms/ADCE/unreachable.ll
@@ -0,0 +1,18 @@
+; RUN: opt < %s -adce -simplifycfg | llvm-dis
+; RUN: opt < %s -passes=adce | llvm-dis
+
+define i32 @Test(i32 %A, i32 %B) {
+BB1:
+ br label %BB4
+
+BB2: ; No predecessors!
+ br label %BB3
+
+BB3: ; preds = %BB4, %BB2
+ %ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ] ; <i32> [#uses=1]
+ ret i32 %ret
+
+BB4: ; preds = %BB1
+ %X = phi i32 [ %A, %BB1 ] ; <i32> [#uses=1]
+ br label %BB3
+}
OpenPOWER on IntegriCloud