LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GlobalDCE.cpp
Go to the documentation of this file.
1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #define DEBUG_TYPE "globaldce"
19 #include "llvm/Transforms/IPO.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Pass.h"
25 using namespace llvm;
26 
27 STATISTIC(NumAliases , "Number of global aliases removed");
28 STATISTIC(NumFunctions, "Number of functions removed");
29 STATISTIC(NumVariables, "Number of global variables removed");
30 
31 namespace {
32  struct GlobalDCE : public ModulePass {
33  static char ID; // Pass identification, replacement for typeid
34  GlobalDCE() : ModulePass(ID) {
36  }
37 
38  // run - Do the GlobalDCE pass on the specified module, optionally updating
39  // the specified callgraph to reflect the changes.
40  //
41  bool runOnModule(Module &M);
42 
43  private:
44  SmallPtrSet<GlobalValue*, 32> AliveGlobals;
45  SmallPtrSet<Constant *, 8> SeenConstants;
46 
47  /// GlobalIsNeeded - mark the specific global value as needed, and
48  /// recursively mark anything that it uses as also needed.
49  void GlobalIsNeeded(GlobalValue *GV);
50  void MarkUsedGlobalsAsNeeded(Constant *C);
51 
52  bool RemoveUnusedGlobalValue(GlobalValue &GV);
53  };
54 }
55 
56 char GlobalDCE::ID = 0;
57 INITIALIZE_PASS(GlobalDCE, "globaldce",
58  "Dead Global Elimination", false, false)
59 
60 ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); }
61 
62 bool GlobalDCE::runOnModule(Module &M) {
63  bool Changed = false;
64 
65  // Loop over the module, adding globals which are obviously necessary.
66  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
67  Changed |= RemoveUnusedGlobalValue(*I);
68  // Functions with external linkage are needed if they have a body
69  if (!I->isDiscardableIfUnused() &&
70  !I->isDeclaration() && !I->hasAvailableExternallyLinkage())
71  GlobalIsNeeded(I);
72  }
73 
75  I != E; ++I) {
76  Changed |= RemoveUnusedGlobalValue(*I);
77  // Externally visible & appending globals are needed, if they have an
78  // initializer.
79  if (!I->isDiscardableIfUnused() &&
80  !I->isDeclaration() && !I->hasAvailableExternallyLinkage())
81  GlobalIsNeeded(I);
82  }
83 
84  for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
85  I != E; ++I) {
86  Changed |= RemoveUnusedGlobalValue(*I);
87  // Externally visible aliases are needed.
88  if (!I->isDiscardableIfUnused())
89  GlobalIsNeeded(I);
90  }
91 
92  // Now that all globals which are needed are in the AliveGlobals set, we loop
93  // through the program, deleting those which are not alive.
94  //
95 
96  // The first pass is to drop initializers of global variables which are dead.
97  std::vector<GlobalVariable*> DeadGlobalVars; // Keep track of dead globals
99  I != E; ++I)
100  if (!AliveGlobals.count(I)) {
101  DeadGlobalVars.push_back(I); // Keep track of dead globals
102  I->setInitializer(0);
103  }
104 
105  // The second pass drops the bodies of functions which are dead...
106  std::vector<Function*> DeadFunctions;
107  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
108  if (!AliveGlobals.count(I)) {
109  DeadFunctions.push_back(I); // Keep track of dead globals
110  if (!I->isDeclaration())
111  I->deleteBody();
112  }
113 
114  // The third pass drops targets of aliases which are dead...
115  std::vector<GlobalAlias*> DeadAliases;
116  for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E;
117  ++I)
118  if (!AliveGlobals.count(I)) {
119  DeadAliases.push_back(I);
120  I->setAliasee(0);
121  }
122 
123  if (!DeadFunctions.empty()) {
124  // Now that all interferences have been dropped, delete the actual objects
125  // themselves.
126  for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
127  RemoveUnusedGlobalValue(*DeadFunctions[i]);
128  M.getFunctionList().erase(DeadFunctions[i]);
129  }
130  NumFunctions += DeadFunctions.size();
131  Changed = true;
132  }
133 
134  if (!DeadGlobalVars.empty()) {
135  for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
136  RemoveUnusedGlobalValue(*DeadGlobalVars[i]);
137  M.getGlobalList().erase(DeadGlobalVars[i]);
138  }
139  NumVariables += DeadGlobalVars.size();
140  Changed = true;
141  }
142 
143  // Now delete any dead aliases.
144  if (!DeadAliases.empty()) {
145  for (unsigned i = 0, e = DeadAliases.size(); i != e; ++i) {
146  RemoveUnusedGlobalValue(*DeadAliases[i]);
147  M.getAliasList().erase(DeadAliases[i]);
148  }
149  NumAliases += DeadAliases.size();
150  Changed = true;
151  }
152 
153  // Make sure that all memory is released
154  AliveGlobals.clear();
155  SeenConstants.clear();
156 
157  return Changed;
158 }
159 
160 /// GlobalIsNeeded - the specific global value as needed, and
161 /// recursively mark anything that it uses as also needed.
162 void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
163  // If the global is already in the set, no need to reprocess it.
164  if (!AliveGlobals.insert(G))
165  return;
166 
167  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
168  // If this is a global variable, we must make sure to add any global values
169  // referenced by the initializer to the alive set.
170  if (GV->hasInitializer())
171  MarkUsedGlobalsAsNeeded(GV->getInitializer());
172  } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(G)) {
173  // The target of a global alias is needed.
174  MarkUsedGlobalsAsNeeded(GA->getAliasee());
175  } else {
176  // Otherwise this must be a function object. We have to scan the body of
177  // the function looking for constants and global values which are used as
178  // operands. Any operands of these types must be processed to ensure that
179  // any globals used will be marked as needed.
180  Function *F = cast<Function>(G);
181 
182  if (F->hasPrefixData())
183  MarkUsedGlobalsAsNeeded(F->getPrefixData());
184 
185  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
186  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
187  for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
188  if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
189  GlobalIsNeeded(GV);
190  else if (Constant *C = dyn_cast<Constant>(*U))
191  MarkUsedGlobalsAsNeeded(C);
192  }
193 }
194 
195 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
196  if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
197  return GlobalIsNeeded(GV);
198 
199  // Loop over all of the operands of the constant, adding any globals they
200  // use to the list of needed globals.
201  for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) {
202  // If we've already processed this constant there's no need to do it again.
203  Constant *Op = dyn_cast<Constant>(*I);
204  if (Op && SeenConstants.insert(Op))
205  MarkUsedGlobalsAsNeeded(Op);
206  }
207 }
208 
209 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
210 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
211 // If found, check to see if the constant pointer ref is safe to destroy, and if
212 // so, nuke it. This will reduce the reference count on the global value, which
213 // might make it deader.
214 //
215 bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) {
216  if (GV.use_empty()) return false;
218  return GV.use_empty();
219 }
static PassRegistry * getPassRegistry()
The main container class for the LLVM Intermediate Representation.
Definition: Module.h:112
iterator end()
Definition: Function.h:397
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:266
const GlobalListType & getGlobalList() const
Get the Module's list of global variables (constant).
Definition: Module.h:485
F(f)
STATISTIC(NumAliases,"Number of global aliases removed")
const AliasListType & getAliasList() const
Get the Module's list of aliases (constant).
Definition: Module.h:499
op_iterator op_begin()
Definition: User.h:116
Definition: Use.h:60
ID
LLVM Calling Convention Representation.
Definition: CallingConv.h:26
#define G(x, y, z)
Definition: MD5.cpp:52
global_iterator global_begin()
Definition: Module.h:521
INITIALIZE_PASS(GlobalDCE,"globaldce","Dead Global Elimination", false, false) ModulePass *llvm
Definition: GlobalDCE.cpp:57
iterator begin()
Definition: Function.h:395
ModulePass * createGlobalDCEPass()
alias_iterator alias_end()
Definition: Module.h:544
LLVM Constant Representation.
Definition: Constant.h:41
op_iterator op_end()
Definition: User.h:118
iterator erase(iterator where)
Definition: ilist.h:465
global_iterator global_end()
Definition: Module.h:523
const FunctionListType & getFunctionList() const
Get the Module's list of functions (constant).
Definition: Module.h:492
alias_iterator alias_begin()
Definition: Module.h:542
void initializeGlobalDCEPass(PassRegistry &)
iterator end()
Definition: Module.h:533
#define I(x, y, z)
Definition: MD5.cpp:54
iterator begin()
Definition: Module.h:531
bool hasPrefixData() const
Definition: Function.h:430
Constant * getPrefixData() const
Definition: Function.cpp:741
bool use_empty() const
Definition: Value.h:149
void removeDeadConstantUsers() const
Definition: Constants.cpp:395