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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
//===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This transform is designed to eliminate unreachable internal globals from the
// program. It uses an aggressive algorithm, searching out globals that are
// known to be alive. After it finds all of the globals which are needed, it
// deletes whatever is left over. This allows it to delete recursive chunks of
// the program which are unreachable.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "globaldce"
#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/ADT/Statistic.h"
#include <set>
using namespace llvm;
STATISTIC(NumFunctions, "Number of functions removed");
STATISTIC(NumVariables, "Number of global variables removed");
namespace {
struct GlobalDCE : public ModulePass {
// run - Do the GlobalDCE pass on the specified module, optionally updating
// the specified callgraph to reflect the changes.
//
bool runOnModule(Module &M);
private:
std::set<GlobalValue*> AliveGlobals;
/// MarkGlobalIsNeeded - the specific global value as needed, and
/// recursively mark anything that it uses as also needed.
void GlobalIsNeeded(GlobalValue *GV);
void MarkUsedGlobalsAsNeeded(Constant *C);
bool SafeToDestroyConstant(Constant* C);
bool RemoveUnusedGlobalValue(GlobalValue &GV);
};
RegisterPass<GlobalDCE> X("globaldce", "Dead Global Elimination");
}
ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); }
bool GlobalDCE::runOnModule(Module &M) {
bool Changed = false;
// Loop over the module, adding globals which are obviously necessary.
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
Changed |= RemoveUnusedGlobalValue(*I);
// Functions with external linkage are needed if they have a body
if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
!I->isExternal())
GlobalIsNeeded(I);
}
for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) {
Changed |= RemoveUnusedGlobalValue(*I);
// Externally visible & appending globals are needed, if they have an
// initializer.
if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
!I->isExternal())
GlobalIsNeeded(I);
}
// Now that all globals which are needed are in the AliveGlobals set, we loop
// through the program, deleting those which are not alive.
//
// The first pass is to drop initializers of global variables which are dead.
std::vector<GlobalVariable*> DeadGlobalVars; // Keep track of dead globals
for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
if (!AliveGlobals.count(I)) {
DeadGlobalVars.push_back(I); // Keep track of dead globals
I->setInitializer(0);
}
// The second pass drops the bodies of functions which are dead...
std::vector<Function*> DeadFunctions;
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!AliveGlobals.count(I)) {
DeadFunctions.push_back(I); // Keep track of dead globals
if (!I->isExternal())
I->deleteBody();
}
if (!DeadFunctions.empty()) {
// Now that all interreferences have been dropped, delete the actual objects
// themselves.
for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
RemoveUnusedGlobalValue(*DeadFunctions[i]);
M.getFunctionList().erase(DeadFunctions[i]);
}
NumFunctions += DeadFunctions.size();
Changed = true;
}
if (!DeadGlobalVars.empty()) {
for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
RemoveUnusedGlobalValue(*DeadGlobalVars[i]);
M.getGlobalList().erase(DeadGlobalVars[i]);
}
NumVariables += DeadGlobalVars.size();
Changed = true;
}
// Make sure that all memory is released
AliveGlobals.clear();
return Changed;
}
/// MarkGlobalIsNeeded - the specific global value as needed, and
/// recursively mark anything that it uses as also needed.
void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
std::set<GlobalValue*>::iterator I = AliveGlobals.lower_bound(G);
// If the global is already in the set, no need to reprocess it.
if (I != AliveGlobals.end() && *I == G) return;
// Otherwise insert it now, so we do not infinitely recurse
AliveGlobals.insert(I, G);
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
// If this is a global variable, we must make sure to add any global values
// referenced by the initializer to the alive set.
if (GV->hasInitializer())
MarkUsedGlobalsAsNeeded(GV->getInitializer());
} else {
// Otherwise this must be a function object. We have to scan the body of
// the function looking for constants and global values which are used as
// operands. Any operands of these types must be processed to ensure that
// any globals used will be marked as needed.
Function *F = cast<Function>(G);
// For all basic blocks...
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
// For all instructions...
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
// For all operands...
for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
GlobalIsNeeded(GV);
else if (Constant *C = dyn_cast<Constant>(*U))
MarkUsedGlobalsAsNeeded(C);
}
}
void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
GlobalIsNeeded(GV);
else {
// Loop over all of the operands of the constant, adding any globals they
// use to the list of needed globals.
for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I)
MarkUsedGlobalsAsNeeded(cast<Constant>(*I));
}
}
// RemoveUnusedGlobalValue - Loop over all of the uses of the specified
// GlobalValue, looking for the constant pointer ref that may be pointing to it.
// If found, check to see if the constant pointer ref is safe to destroy, and if
// so, nuke it. This will reduce the reference count on the global value, which
// might make it deader.
//
bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) {
if (GV.use_empty()) return false;
GV.removeDeadConstantUsers();
return GV.use_empty();
}
// SafeToDestroyConstant - It is safe to destroy a constant iff it is only used
// by constants itself. Note that constants cannot be cyclic, so this test is
// pretty easy to implement recursively.
//
bool GlobalDCE::SafeToDestroyConstant(Constant *C) {
for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I)
if (Constant *User = dyn_cast<Constant>(*I)) {
if (!SafeToDestroyConstant(User)) return false;
} else {
return false;
}
return true;
}
|
