1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
//===- DCE.cpp - Code to perform dead code elimination --------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the Aggressive Dead Code Elimination pass. This pass
// optimistically assumes that all instructions are dead until proven otherwise,
// allowing it to eliminate dead computations that other DCE passes do not
// catch, particularly involving loop computations.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "adce"
#include "llvm/Transforms/Scalar.h"
#include "llvm/BasicBlock.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumRemoved, "Number of instructions removed");
namespace {
struct VISIBILITY_HIDDEN ADCE : public FunctionPass {
static char ID; // Pass identification, replacement for typeid
ADCE() : FunctionPass((intptr_t)&ID) {}
virtual bool runOnFunction(Function& F);
virtual void getAnalysisUsage(AnalysisUsage& AU) const {
AU.setPreservesCFG();
}
};
}
char ADCE::ID = 0;
static RegisterPass<ADCE> X("adce", "Aggressive Dead Code Elimination");
bool ADCE::runOnFunction(Function& F) {
SmallPtrSet<Instruction*, 128> alive;
SmallVector<Instruction*, 128> worklist;
SmallPtrSet<BasicBlock*, 64> reachable;
SmallVector<BasicBlock*, 16> unreachable;
// First, collect the set of reachable blocks ...
for (df_ext_iterator<BasicBlock*, SmallPtrSet<BasicBlock*, 64> >
DI = df_ext_begin(&F.getEntryBlock(), reachable),
DE = df_ext_end(&F.getEntryBlock(), reachable); DI != DE; ++DI)
; // Deliberately empty, df_ext_iterator will fill in the set.
// ... and then invert it into the list of unreachable ones. These
// blocks will be removed from the function.
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
if (!reachable.count(FI))
unreachable.push_back(FI);
// Prepare to remove blocks by removing the PHI node entries for those blocks
// in their successors, and remove them from reference counting.
for (SmallVector<BasicBlock*, 16>::iterator UI = unreachable.begin(),
UE = unreachable.end(); UI != UE; ++UI) {
BasicBlock* BB = *UI;
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
SI != SE; ++SI) {
BasicBlock* succ = *SI;
BasicBlock::iterator succ_inst = succ->begin();
while (PHINode* P = dyn_cast<PHINode>(succ_inst)) {
P->removeIncomingValue(BB);
++succ_inst;
}
}
BB->dropAllReferences();
}
// Finally, erase the unreachable blocks.
for (SmallVector<BasicBlock*, 16>::iterator UI = unreachable.begin(),
UE = unreachable.end(); UI != UE; ++UI)
(*UI)->eraseFromParent();
// Collect the set of "root" instructions that are known live.
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (isa<TerminatorInst>(I.getInstructionIterator()) ||
I->mayWriteToMemory()) {
alive.insert(I.getInstructionIterator());
worklist.push_back(I.getInstructionIterator());
}
// Propagate liveness backwards to operands.
while (!worklist.empty()) {
Instruction* curr = worklist.back();
worklist.pop_back();
for (Instruction::op_iterator OI = curr->op_begin(), OE = curr->op_end();
OI != OE; ++OI)
if (Instruction* Inst = dyn_cast<Instruction>(OI))
if (alive.insert(Inst))
worklist.push_back(Inst);
}
// The inverse of the live set is the dead set. These are those instructions
// which have no side effects and do not influence the control flow or return
// value of the function, and may therefore be deleted safely.
// NOTE: We reuse the worklist vector here for memory efficiency.
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
if (!alive.count(I.getInstructionIterator())) {
worklist.push_back(I.getInstructionIterator());
I->dropAllReferences();
}
for (SmallVector<Instruction*, 1024>::iterator I = worklist.begin(),
E = worklist.end(); I != E; ++I) {
NumRemoved++;
(*I)->eraseFromParent();
}
return !worklist.empty();
}
FunctionPass *llvm::createAggressiveDCEPass() {
return new ADCE();
}
|
