Skip to content

Commit 2724d45

Browse files
kuharkuhar
committedAug 22, 2017
[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
1 parent a680a8f commit 2724d45

File tree

4 files changed

+130
-7
lines changed

4 files changed

+130
-7
lines changed
 

‎llvm/lib/Transforms/Scalar/ADCE.cpp

+49-7
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
#include "llvm/IR/BasicBlock.h"
2828
#include "llvm/IR/CFG.h"
2929
#include "llvm/IR/DebugInfoMetadata.h"
30+
#include "llvm/IR/Dominators.h"
3031
#include "llvm/IR/IRBuilder.h"
3132
#include "llvm/IR/InstIterator.h"
3233
#include "llvm/IR/Instructions.h"
@@ -89,6 +90,10 @@ struct BlockInfoType {
8990

9091
class AggressiveDeadCodeElimination {
9192
Function &F;
93+
94+
// ADCE does not use DominatorTree per se, but it updates it to preserve the
95+
// analysis.
96+
DominatorTree &DT;
9297
PostDominatorTree &PDT;
9398

9499
/// Mapping of blocks to associated information, an element in BlockInfoVec.
@@ -157,9 +162,10 @@ class AggressiveDeadCodeElimination {
157162
void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
158163

159164
public:
160-
AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
161-
: F(F), PDT(PDT) {}
162-
bool performDeadCodeElimination();
165+
AggressiveDeadCodeElimination(Function &F, DominatorTree &DT,
166+
PostDominatorTree &PDT)
167+
: F(F), DT(DT), PDT(PDT) {}
168+
bool performDeadCodeElimination();
163169
};
164170
}
165171

@@ -557,14 +563,34 @@ void AggressiveDeadCodeElimination::updateDeadRegions() {
557563
}
558564
assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
559565
"Failed to find safe successor for dead branch");
566+
567+
// Collect removed successors to update the (Post)DominatorTrees.
568+
SmallPtrSet<BasicBlock *, 4> RemovedSuccessors;
560569
bool First = true;
561570
for (auto *Succ : successors(BB)) {
562-
if (!First || Succ != PreferredSucc->BB)
571+
if (!First || Succ != PreferredSucc->BB) {
563572
Succ->removePredecessor(BB);
564-
else
573+
RemovedSuccessors.insert(Succ);
574+
} else
565575
First = false;
566576
}
567577
makeUnconditional(BB, PreferredSucc->BB);
578+
579+
// Inform the dominators about the deleted CFG edges.
580+
SmallVector<DominatorTree::UpdateType, 4> DeletedEdges;
581+
for (auto *Succ : RemovedSuccessors) {
582+
// It might have happened that the same successor appeared multiple times
583+
// and the CFG edge wasn't really removed.
584+
if (Succ != PreferredSucc->BB) {
585+
DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"
586+
<< BB->getName() << " -> " << Succ->getName() << "\n");
587+
DeletedEdges.push_back({DominatorTree::Delete, BB, Succ});
588+
}
589+
}
590+
591+
DT.applyUpdates(DeletedEdges);
592+
PDT.applyUpdates(DeletedEdges);
593+
568594
NumBranchesRemoved += 1;
569595
}
570596
}
@@ -609,6 +635,9 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
609635
InstInfo[NewTerm].Live = true;
610636
if (const DILocation *DL = PredTerm->getDebugLoc())
611637
NewTerm->setDebugLoc(DL);
638+
639+
InstInfo.erase(PredTerm);
640+
PredTerm->eraseFromParent();
612641
}
613642

614643
//===----------------------------------------------------------------------===//
@@ -617,13 +646,16 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
617646
//
618647
//===----------------------------------------------------------------------===//
619648
PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
649+
auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
620650
auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
621-
if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
651+
if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination())
622652
return PreservedAnalyses::all();
623653

624654
PreservedAnalyses PA;
625655
PA.preserveSet<CFGAnalyses>();
626656
PA.preserve<GlobalsAA>();
657+
PA.preserve<DominatorTreeAnalysis>();
658+
PA.preserve<PostDominatorTreeAnalysis>();
627659
return PA;
628660
}
629661

@@ -637,14 +669,23 @@ struct ADCELegacyPass : public FunctionPass {
637669
bool runOnFunction(Function &F) override {
638670
if (skipFunction(F))
639671
return false;
672+
673+
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
640674
auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
641-
return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
675+
return AggressiveDeadCodeElimination(F, DT, PDT)
676+
.performDeadCodeElimination();
642677
}
643678

644679
void getAnalysisUsage(AnalysisUsage &AU) const override {
680+
// We require DominatorTree here only to update and thus preserve it.
681+
AU.addRequired<DominatorTreeWrapperPass>();
645682
AU.addRequired<PostDominatorTreeWrapperPass>();
646683
if (!RemoveControlFlowFlag)
647684
AU.setPreservesCFG();
685+
else {
686+
AU.addPreserved<DominatorTreeWrapperPass>();
687+
AU.addPreserved<PostDominatorTreeWrapperPass>();
688+
}
648689
AU.addPreserved<GlobalsAAWrapperPass>();
649690
}
650691
};
@@ -653,6 +694,7 @@ struct ADCELegacyPass : public FunctionPass {
653694
char ADCELegacyPass::ID = 0;
654695
INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
655696
"Aggressive Dead Code Elimination", false, false)
697+
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
656698
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
657699
INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
658700
false, false)

‎llvm/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll

+24
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
; RUN: opt < %s -adce | llvm-dis
2+
; RUN: opt < %s -adce -verify-dom-info | llvm-dis
3+
4+
define void @foo() {
5+
entry:
6+
br label %switch
7+
switch: ; preds = %entry
8+
switch i32 undef, label %default [
9+
i32 2, label %two
10+
i32 5, label %five
11+
i32 4, label %four
12+
]
13+
four: ; preds = %switch
14+
br label %exit
15+
five: ; preds = %switch
16+
br label %exit
17+
two: ; preds = %switch
18+
br label %exit
19+
default: ; preds = %switch
20+
br label %exit
21+
exit: ; preds = %default, %two, %five, %four
22+
ret void
23+
}
24+

‎llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll

+39
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
; RUN: opt < %s -gvn -simplifycfg -adce | llvm-dis
2+
; RUN: opt < %s -gvn -simplifycfg -adce -verify-dom-info | llvm-dis
3+
4+
; This test makes sure that the DominatorTree properly handles
5+
; deletion of edges that go to forward-unreachable regions.
6+
; In this case, %land.end is already forward unreachable when
7+
; the DT gets informed about the deletion of %entry -> %land.end.
8+
9+
@a = common global i32 0, align 4
10+
11+
define i32 @main() {
12+
entry:
13+
%retval = alloca i32, align 4
14+
store i32 0, i32* %retval, align 4
15+
%0 = load i32, i32* @a, align 4
16+
%cmp = icmp ne i32 %0, 1
17+
br i1 %cmp, label %land.rhs, label %land.end4
18+
19+
land.rhs: ; preds = %entry
20+
%1 = load i32, i32* @a, align 4
21+
%tobool = icmp ne i32 %1, 0
22+
br i1 %tobool, label %land.rhs1, label %land.end
23+
24+
land.rhs1: ; preds = %land.rhs
25+
br label %land.end
26+
27+
land.end: ; preds = %land.rhs1, %land.rhs
28+
%2 = phi i1 [ false, %land.rhs ], [ true, %land.rhs1 ]
29+
%land.ext = zext i1 %2 to i32
30+
%conv = trunc i32 %land.ext to i16
31+
%conv2 = sext i16 %conv to i32
32+
%tobool3 = icmp ne i32 %conv2, 0
33+
br label %land.end4
34+
35+
land.end4: ; preds = %land.end, %entry
36+
%3 = phi i1 [ false, %entry ], [ %tobool3, %land.end ]
37+
%land.ext5 = zext i1 %3 to i32
38+
ret i32 0
39+
}

‎llvm/test/Transforms/ADCE/unreachable.ll

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
; RUN: opt < %s -adce -simplifycfg | llvm-dis
2+
; RUN: opt < %s -passes=adce | llvm-dis
3+
4+
define i32 @Test(i32 %A, i32 %B) {
5+
BB1:
6+
br label %BB4
7+
8+
BB2: ; No predecessors!
9+
br label %BB3
10+
11+
BB3: ; preds = %BB4, %BB2
12+
%ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ] ; <i32> [#uses=1]
13+
ret i32 %ret
14+
15+
BB4: ; preds = %BB1
16+
%X = phi i32 [ %A, %BB1 ] ; <i32> [#uses=1]
17+
br label %BB3
18+
}

0 commit comments

Comments
 (0)
Please sign in to comment.