LLVM  6.0.0svn
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 
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/Pass.h"
25 #include "llvm/Transforms/IPO.h"
28 
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "globaldce"
32 
33 STATISTIC(NumAliases , "Number of global aliases removed");
34 STATISTIC(NumFunctions, "Number of functions removed");
35 STATISTIC(NumIFuncs, "Number of indirect functions removed");
36 STATISTIC(NumVariables, "Number of global variables removed");
37 
38 namespace {
39  class GlobalDCELegacyPass : public ModulePass {
40  public:
41  static char ID; // Pass identification, replacement for typeid
42  GlobalDCELegacyPass() : ModulePass(ID) {
44  }
45 
46  // run - Do the GlobalDCE pass on the specified module, optionally updating
47  // the specified callgraph to reflect the changes.
48  //
49  bool runOnModule(Module &M) override {
50  if (skipModule(M))
51  return false;
52 
53  // We need a minimally functional dummy module analysis manager. It needs
54  // to at least know about the possibility of proxying a function analysis
55  // manager.
56  FunctionAnalysisManager DummyFAM;
57  ModuleAnalysisManager DummyMAM;
58  DummyMAM.registerPass(
59  [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
60 
61  auto PA = Impl.run(M, DummyMAM);
62  return !PA.areAllPreserved();
63  }
64 
65  private:
66  GlobalDCEPass Impl;
67  };
68 }
69 
71 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
72  "Dead Global Elimination", false, false)
73 
74 // Public interface to the GlobalDCEPass.
76  return new GlobalDCELegacyPass();
77 }
78 
79 /// Returns true if F contains only a single "ret" instruction.
80 static bool isEmptyFunction(Function *F) {
81  BasicBlock &Entry = F->getEntryBlock();
82  if (Entry.size() != 1 || !isa<ReturnInst>(Entry.front()))
83  return false;
84  ReturnInst &RI = cast<ReturnInst>(Entry.front());
85  return RI.getReturnValue() == nullptr;
86 }
87 
88 /// Compute the set of GlobalValue that depends from V.
89 /// The recursion stops as soon as a GlobalValue is met.
90 void GlobalDCEPass::ComputeDependencies(Value *V,
92  if (auto *I = dyn_cast<Instruction>(V)) {
93  Function *Parent = I->getParent()->getParent();
94  Deps.insert(Parent);
95  } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
96  Deps.insert(GV);
97  } else if (auto *CE = dyn_cast<Constant>(V)) {
98  // Avoid walking the whole tree of a big ConstantExprs multiple times.
99  auto Where = ConstantDependenciesCache.find(CE);
100  if (Where != ConstantDependenciesCache.end()) {
101  auto const &K = Where->second;
102  Deps.insert(K.begin(), K.end());
103  } else {
104  SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
105  for (User *CEUser : CE->users())
106  ComputeDependencies(CEUser, LocalDeps);
107  Deps.insert(LocalDeps.begin(), LocalDeps.end());
108  }
109  }
110 }
111 
112 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
114  for (User *User : GV.users())
115  ComputeDependencies(User, Deps);
116  Deps.erase(&GV); // Remove self-reference.
117  for (GlobalValue *GVU : Deps) {
118  GVDependencies.insert(std::make_pair(GVU, &GV));
119  }
120 }
121 
122 /// Mark Global value as Live
123 void GlobalDCEPass::MarkLive(GlobalValue &GV,
125  auto const Ret = AliveGlobals.insert(&GV);
126  if (!Ret.second)
127  return;
128 
129  if (Updates)
130  Updates->push_back(&GV);
131  if (Comdat *C = GV.getComdat()) {
132  for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
133  MarkLive(*CM.second, Updates); // Recursion depth is only two because only
134  // globals in the same comdat are visited.
135  }
136 }
137 
139  bool Changed = false;
140 
141  // The algorithm first computes the set L of global variables that are
142  // trivially live. Then it walks the initialization of these variables to
143  // compute the globals used to initialize them, which effectively builds a
144  // directed graph where nodes are global variables, and an edge from A to B
145  // means B is used to initialize A. Finally, it propagates the liveness
146  // information through the graph starting from the nodes in L. Nodes note
147  // marked as alive are discarded.
148 
149  // Remove empty functions from the global ctors list.
151 
152  // Collect the set of members for each comdat.
153  for (Function &F : M)
154  if (Comdat *C = F.getComdat())
155  ComdatMembers.insert(std::make_pair(C, &F));
156  for (GlobalVariable &GV : M.globals())
157  if (Comdat *C = GV.getComdat())
158  ComdatMembers.insert(std::make_pair(C, &GV));
159  for (GlobalAlias &GA : M.aliases())
160  if (Comdat *C = GA.getComdat())
161  ComdatMembers.insert(std::make_pair(C, &GA));
162 
163  // Loop over the module, adding globals which are obviously necessary.
164  for (GlobalObject &GO : M.global_objects()) {
165  Changed |= RemoveUnusedGlobalValue(GO);
166  // Functions with external linkage are needed if they have a body.
167  // Externally visible & appending globals are needed, if they have an
168  // initializer.
169  if (!GO.isDeclaration() && !GO.hasAvailableExternallyLinkage())
170  if (!GO.isDiscardableIfUnused())
171  MarkLive(GO);
172 
173  UpdateGVDependencies(GO);
174  }
175 
176  // Compute direct dependencies of aliases.
177  for (GlobalAlias &GA : M.aliases()) {
178  Changed |= RemoveUnusedGlobalValue(GA);
179  // Externally visible aliases are needed.
180  if (!GA.isDiscardableIfUnused())
181  MarkLive(GA);
182 
183  UpdateGVDependencies(GA);
184  }
185 
186  // Compute direct dependencies of ifuncs.
187  for (GlobalIFunc &GIF : M.ifuncs()) {
188  Changed |= RemoveUnusedGlobalValue(GIF);
189  // Externally visible ifuncs are needed.
190  if (!GIF.isDiscardableIfUnused())
191  MarkLive(GIF);
192 
193  UpdateGVDependencies(GIF);
194  }
195 
196  // Propagate liveness from collected Global Values through the computed
197  // dependencies.
198  SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
199  AliveGlobals.end()};
200  while (!NewLiveGVs.empty()) {
201  GlobalValue *LGV = NewLiveGVs.pop_back_val();
202  for (auto &&GVD : make_range(GVDependencies.equal_range(LGV)))
203  MarkLive(*GVD.second, &NewLiveGVs);
204  }
205 
206  // Now that all globals which are needed are in the AliveGlobals set, we loop
207  // through the program, deleting those which are not alive.
208  //
209 
210  // The first pass is to drop initializers of global variables which are dead.
211  std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
212  for (GlobalVariable &GV : M.globals())
213  if (!AliveGlobals.count(&GV)) {
214  DeadGlobalVars.push_back(&GV); // Keep track of dead globals
215  if (GV.hasInitializer()) {
216  Constant *Init = GV.getInitializer();
217  GV.setInitializer(nullptr);
218  if (isSafeToDestroyConstant(Init))
219  Init->destroyConstant();
220  }
221  }
222 
223  // The second pass drops the bodies of functions which are dead...
224  std::vector<Function *> DeadFunctions;
225  for (Function &F : M)
226  if (!AliveGlobals.count(&F)) {
227  DeadFunctions.push_back(&F); // Keep track of dead globals
228  if (!F.isDeclaration())
229  F.deleteBody();
230  }
231 
232  // The third pass drops targets of aliases which are dead...
233  std::vector<GlobalAlias*> DeadAliases;
234  for (GlobalAlias &GA : M.aliases())
235  if (!AliveGlobals.count(&GA)) {
236  DeadAliases.push_back(&GA);
237  GA.setAliasee(nullptr);
238  }
239 
240  // The fourth pass drops targets of ifuncs which are dead...
241  std::vector<GlobalIFunc*> DeadIFuncs;
242  for (GlobalIFunc &GIF : M.ifuncs())
243  if (!AliveGlobals.count(&GIF)) {
244  DeadIFuncs.push_back(&GIF);
245  GIF.setResolver(nullptr);
246  }
247 
248  // Now that all interferences have been dropped, delete the actual objects
249  // themselves.
250  auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
251  RemoveUnusedGlobalValue(*GV);
252  GV->eraseFromParent();
253  Changed = true;
254  };
255 
256  NumFunctions += DeadFunctions.size();
257  for (Function *F : DeadFunctions)
258  EraseUnusedGlobalValue(F);
259 
260  NumVariables += DeadGlobalVars.size();
261  for (GlobalVariable *GV : DeadGlobalVars)
262  EraseUnusedGlobalValue(GV);
263 
264  NumAliases += DeadAliases.size();
265  for (GlobalAlias *GA : DeadAliases)
266  EraseUnusedGlobalValue(GA);
267 
268  NumIFuncs += DeadIFuncs.size();
269  for (GlobalIFunc *GIF : DeadIFuncs)
270  EraseUnusedGlobalValue(GIF);
271 
272  // Make sure that all memory is released
273  AliveGlobals.clear();
274  ConstantDependenciesCache.clear();
275  GVDependencies.clear();
276  ComdatMembers.clear();
277 
278  if (Changed)
279  return PreservedAnalyses::none();
280  return PreservedAnalyses::all();
281 }
282 
283 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
284 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
285 // If found, check to see if the constant pointer ref is safe to destroy, and if
286 // so, nuke it. This will reduce the reference count on the global value, which
287 // might make it deader.
288 //
289 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
290  if (GV.use_empty())
291  return false;
293  return GV.use_empty();
294 }
uint64_t CallInst * C
Return a value (possibly void), from a function.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void initializeGlobalDCELegacyPassPass(PassRegistry &)
STATISTIC(NumFunctions, "Total number of functions")
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", "Dead Global Elimination", false, false) ModulePass *llvm
Definition: GlobalDCE.cpp:71
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:739
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
Definition: PassManager.h:1029
#define F(x, y, z)
Definition: MD5.cpp:55
Pass to remove unused function declarations.
Definition: GlobalDCE.h:30
ModulePass * createGlobalDCEPass()
createGlobalDCEPass - This transform is designed to eliminate unreachable internal globals (functions...
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:475
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
This file contains the declarations for the subclasses of Constant, which represent the different fla...
const Instruction & front() const
Definition: BasicBlock.h:264
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:372
size_t size() const
Definition: BasicBlock.h:262
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:379
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
static bool isEmptyFunction(Function *F)
Returns true if F contains only a single "ret" instruction.
Definition: GlobalDCE.cpp:80
const Comdat * getComdat() const
Definition: Globals.cpp:165
iterator_range< user_iterator > users()
Definition: Value.h:395
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing module and deletes it.
Definition: Globals.cpp:84
iterator begin() const
Definition: SmallPtrSet.h:398
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:235
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:300
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
iterator end() const
Definition: SmallPtrSet.h:405
LLVM Value Representation.
Definition: Value.h:73
A container for analyses that lazily runs them and caches their results.
bool optimizeGlobalCtorsList(Module &M, function_ref< bool(Function *)> ShouldRemove)
Call "ShouldRemove" for every entry in M&#39;s global_ctor list and remove the entries for which it retur...
Definition: CtorUtils.cpp:120
bool use_empty() const
Definition: Value.h:322
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: GlobalDCE.cpp:138