]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/IPO/GlobalDCE.cpp
1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This transform is designed to eliminate unreachable internal globals from the
11 // program. It uses an aggressive algorithm, searching out globals that are
12 // known to be alive. After it finds all of the globals which are needed, it
13 // deletes whatever is left over. This allows it to delete recursive chunks of
14 // the program which are unreachable.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/Transforms/IPO.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/Statistic.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Transforms/Utils/CtorUtils.h"
25 #include "llvm/Transforms/Utils/GlobalStatus.h"
26 #include "llvm/Pass.h"
29 #define DEBUG_TYPE "globaldce"
31 STATISTIC(NumAliases
, "Number of global aliases removed");
32 STATISTIC(NumFunctions
, "Number of functions removed");
33 STATISTIC(NumVariables
, "Number of global variables removed");
36 struct GlobalDCE
: public ModulePass
{
37 static char ID
; // Pass identification, replacement for typeid
38 GlobalDCE() : ModulePass(ID
) {
39 initializeGlobalDCEPass(*PassRegistry::getPassRegistry());
42 // run - Do the GlobalDCE pass on the specified module, optionally updating
43 // the specified callgraph to reflect the changes.
45 bool runOnModule(Module
&M
) override
;
48 SmallPtrSet
<GlobalValue
*, 32> AliveGlobals
;
49 SmallPtrSet
<Constant
*, 8> SeenConstants
;
51 /// GlobalIsNeeded - mark the specific global value as needed, and
52 /// recursively mark anything that it uses as also needed.
53 void GlobalIsNeeded(GlobalValue
*GV
);
54 void MarkUsedGlobalsAsNeeded(Constant
*C
);
56 bool RemoveUnusedGlobalValue(GlobalValue
&GV
);
60 /// Returns true if F contains only a single "ret" instruction.
61 static bool isEmptyFunction(Function
*F
) {
62 BasicBlock
&Entry
= F
->getEntryBlock();
63 if (Entry
.size() != 1 || !isa
<ReturnInst
>(Entry
.front()))
65 ReturnInst
&RI
= cast
<ReturnInst
>(Entry
.front());
66 return RI
.getReturnValue() == nullptr;
69 char GlobalDCE::ID
= 0;
70 INITIALIZE_PASS(GlobalDCE
, "globaldce",
71 "Dead Global Elimination", false, false)
73 ModulePass
*llvm::createGlobalDCEPass() { return new GlobalDCE(); }
75 bool GlobalDCE::runOnModule(Module
&M
) {
78 // Remove empty functions from the global ctors list.
79 Changed
|= optimizeGlobalCtorsList(M
, isEmptyFunction
);
81 // Loop over the module, adding globals which are obviously necessary.
82 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ++I
) {
83 Changed
|= RemoveUnusedGlobalValue(*I
);
84 // Functions with external linkage are needed if they have a body
85 if (!I
->isDeclaration() && !I
->hasAvailableExternallyLinkage()) {
86 if (!I
->isDiscardableIfUnused())
91 for (Module::global_iterator I
= M
.global_begin(), E
= M
.global_end();
93 Changed
|= RemoveUnusedGlobalValue(*I
);
94 // Externally visible & appending globals are needed, if they have an
96 if (!I
->isDeclaration() && !I
->hasAvailableExternallyLinkage()) {
97 if (!I
->isDiscardableIfUnused())
102 for (Module::alias_iterator I
= M
.alias_begin(), E
= M
.alias_end();
104 Changed
|= RemoveUnusedGlobalValue(*I
);
105 // Externally visible aliases are needed.
106 if (!I
->isDiscardableIfUnused()) {
111 // Now that all globals which are needed are in the AliveGlobals set, we loop
112 // through the program, deleting those which are not alive.
115 // The first pass is to drop initializers of global variables which are dead.
116 std::vector
<GlobalVariable
*> DeadGlobalVars
; // Keep track of dead globals
117 for (Module::global_iterator I
= M
.global_begin(), E
= M
.global_end();
119 if (!AliveGlobals
.count(I
)) {
120 DeadGlobalVars
.push_back(I
); // Keep track of dead globals
121 if (I
->hasInitializer()) {
122 Constant
*Init
= I
->getInitializer();
123 I
->setInitializer(nullptr);
124 if (isSafeToDestroyConstant(Init
))
125 Init
->destroyConstant();
129 // The second pass drops the bodies of functions which are dead...
130 std::vector
<Function
*> DeadFunctions
;
131 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ++I
)
132 if (!AliveGlobals
.count(I
)) {
133 DeadFunctions
.push_back(I
); // Keep track of dead globals
134 if (!I
->isDeclaration())
138 // The third pass drops targets of aliases which are dead...
139 std::vector
<GlobalAlias
*> DeadAliases
;
140 for (Module::alias_iterator I
= M
.alias_begin(), E
= M
.alias_end(); I
!= E
;
142 if (!AliveGlobals
.count(I
)) {
143 DeadAliases
.push_back(I
);
144 I
->setAliasee(nullptr);
147 if (!DeadFunctions
.empty()) {
148 // Now that all interferences have been dropped, delete the actual objects
150 for (unsigned i
= 0, e
= DeadFunctions
.size(); i
!= e
; ++i
) {
151 RemoveUnusedGlobalValue(*DeadFunctions
[i
]);
152 M
.getFunctionList().erase(DeadFunctions
[i
]);
154 NumFunctions
+= DeadFunctions
.size();
158 if (!DeadGlobalVars
.empty()) {
159 for (unsigned i
= 0, e
= DeadGlobalVars
.size(); i
!= e
; ++i
) {
160 RemoveUnusedGlobalValue(*DeadGlobalVars
[i
]);
161 M
.getGlobalList().erase(DeadGlobalVars
[i
]);
163 NumVariables
+= DeadGlobalVars
.size();
167 // Now delete any dead aliases.
168 if (!DeadAliases
.empty()) {
169 for (unsigned i
= 0, e
= DeadAliases
.size(); i
!= e
; ++i
) {
170 RemoveUnusedGlobalValue(*DeadAliases
[i
]);
171 M
.getAliasList().erase(DeadAliases
[i
]);
173 NumAliases
+= DeadAliases
.size();
177 // Make sure that all memory is released
178 AliveGlobals
.clear();
179 SeenConstants
.clear();
184 /// GlobalIsNeeded - the specific global value as needed, and
185 /// recursively mark anything that it uses as also needed.
186 void GlobalDCE::GlobalIsNeeded(GlobalValue
*G
) {
187 // If the global is already in the set, no need to reprocess it.
188 if (!AliveGlobals
.insert(G
).second
)
191 Module
*M
= G
->getParent();
192 if (Comdat
*C
= G
->getComdat()) {
193 for (Function
&F
: *M
)
194 if (F
.getComdat() == C
)
196 for (GlobalVariable
&GV
: M
->globals())
197 if (GV
.getComdat() == C
)
199 for (GlobalAlias
&GA
: M
->aliases())
200 if (GA
.getComdat() == C
)
204 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(G
)) {
205 // If this is a global variable, we must make sure to add any global values
206 // referenced by the initializer to the alive set.
207 if (GV
->hasInitializer())
208 MarkUsedGlobalsAsNeeded(GV
->getInitializer());
209 } else if (GlobalAlias
*GA
= dyn_cast
<GlobalAlias
>(G
)) {
210 // The target of a global alias is needed.
211 MarkUsedGlobalsAsNeeded(GA
->getAliasee());
213 // Otherwise this must be a function object. We have to scan the body of
214 // the function looking for constants and global values which are used as
215 // operands. Any operands of these types must be processed to ensure that
216 // any globals used will be marked as needed.
217 Function
*F
= cast
<Function
>(G
);
219 if (F
->hasPrefixData())
220 MarkUsedGlobalsAsNeeded(F
->getPrefixData());
222 if (F
->hasPrologueData())
223 MarkUsedGlobalsAsNeeded(F
->getPrologueData());
225 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
)
226 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
)
227 for (User::op_iterator U
= I
->op_begin(), E
= I
->op_end(); U
!= E
; ++U
)
228 if (GlobalValue
*GV
= dyn_cast
<GlobalValue
>(*U
))
230 else if (Constant
*C
= dyn_cast
<Constant
>(*U
))
231 MarkUsedGlobalsAsNeeded(C
);
235 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant
*C
) {
236 if (GlobalValue
*GV
= dyn_cast
<GlobalValue
>(C
))
237 return GlobalIsNeeded(GV
);
239 // Loop over all of the operands of the constant, adding any globals they
240 // use to the list of needed globals.
241 for (User::op_iterator I
= C
->op_begin(), E
= C
->op_end(); I
!= E
; ++I
) {
242 // If we've already processed this constant there's no need to do it again.
243 Constant
*Op
= dyn_cast
<Constant
>(*I
);
244 if (Op
&& SeenConstants
.insert(Op
).second
)
245 MarkUsedGlobalsAsNeeded(Op
);
249 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
250 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
251 // If found, check to see if the constant pointer ref is safe to destroy, and if
252 // so, nuke it. This will reduce the reference count on the global value, which
253 // might make it deader.
255 bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue
&GV
) {
256 if (GV
.use_empty()) return false;
257 GV
.removeDeadConstantUsers();
258 return GV
.use_empty();