LLVM  10.0.0svn
GlobalDCE.cpp
Go to the documentation of this file.
1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This transform is designed to eliminate unreachable internal globals from the
10 // program. It uses an aggressive algorithm, searching out globals that are
11 // known to be alive. After it finds all of the globals which are needed, it
12 // deletes whatever is left over. This allows it to delete recursive chunks of
13 // the program which are unreachable.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Transforms/IPO.h"
27 
28 using namespace llvm;
29 
30 #define DEBUG_TYPE "globaldce"
31 
32 STATISTIC(NumAliases , "Number of global aliases removed");
33 STATISTIC(NumFunctions, "Number of functions removed");
34 STATISTIC(NumIFuncs, "Number of indirect functions removed");
35 STATISTIC(NumVariables, "Number of global variables removed");
36 
37 namespace {
38  class GlobalDCELegacyPass : public ModulePass {
39  public:
40  static char ID; // Pass identification, replacement for typeid
41  GlobalDCELegacyPass() : ModulePass(ID) {
43  }
44 
45  // run - Do the GlobalDCE pass on the specified module, optionally updating
46  // the specified callgraph to reflect the changes.
47  //
48  bool runOnModule(Module &M) override {
49  if (skipModule(M))
50  return false;
51 
52  // We need a minimally functional dummy module analysis manager. It needs
53  // to at least know about the possibility of proxying a function analysis
54  // manager.
55  FunctionAnalysisManager DummyFAM;
56  ModuleAnalysisManager DummyMAM;
57  DummyMAM.registerPass(
58  [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
59 
60  auto PA = Impl.run(M, DummyMAM);
61  return !PA.areAllPreserved();
62  }
63 
64  private:
65  GlobalDCEPass Impl;
66  };
67 }
68 
70 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
71  "Dead Global Elimination", false, false)
72 
73 // Public interface to the GlobalDCEPass.
75  return new GlobalDCELegacyPass();
76 }
77 
78 /// Returns true if F is effectively empty.
79 static bool isEmptyFunction(Function *F) {
81  for (auto &I : Entry) {
82  if (isa<DbgInfoIntrinsic>(I))
83  continue;
84  if (auto *RI = dyn_cast<ReturnInst>(&I))
85  return !RI->getReturnValue();
86  break;
87  }
88  return false;
89 }
90 
91 /// Compute the set of GlobalValue that depends from V.
92 /// The recursion stops as soon as a GlobalValue is met.
93 void GlobalDCEPass::ComputeDependencies(Value *V,
95  if (auto *I = dyn_cast<Instruction>(V)) {
96  Function *Parent = I->getParent()->getParent();
97  Deps.insert(Parent);
98  } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
99  Deps.insert(GV);
100  } else if (auto *CE = dyn_cast<Constant>(V)) {
101  // Avoid walking the whole tree of a big ConstantExprs multiple times.
102  auto Where = ConstantDependenciesCache.find(CE);
103  if (Where != ConstantDependenciesCache.end()) {
104  auto const &K = Where->second;
105  Deps.insert(K.begin(), K.end());
106  } else {
107  SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
108  for (User *CEUser : CE->users())
109  ComputeDependencies(CEUser, LocalDeps);
110  Deps.insert(LocalDeps.begin(), LocalDeps.end());
111  }
112  }
113 }
114 
115 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
117  for (User *User : GV.users())
118  ComputeDependencies(User, Deps);
119  Deps.erase(&GV); // Remove self-reference.
120  for (GlobalValue *GVU : Deps) {
121  GVDependencies[GVU].insert(&GV);
122  }
123 }
124 
125 /// Mark Global value as Live
126 void GlobalDCEPass::MarkLive(GlobalValue &GV,
128  auto const Ret = AliveGlobals.insert(&GV);
129  if (!Ret.second)
130  return;
131 
132  if (Updates)
133  Updates->push_back(&GV);
134  if (Comdat *C = GV.getComdat()) {
135  for (auto &&CM : make_range(ComdatMembers.equal_range(C)))
136  MarkLive(*CM.second, Updates); // Recursion depth is only two because only
137  // globals in the same comdat are visited.
138  }
139 }
140 
142  bool Changed = false;
143 
144  // The algorithm first computes the set L of global variables that are
145  // trivially live. Then it walks the initialization of these variables to
146  // compute the globals used to initialize them, which effectively builds a
147  // directed graph where nodes are global variables, and an edge from A to B
148  // means B is used to initialize A. Finally, it propagates the liveness
149  // information through the graph starting from the nodes in L. Nodes note
150  // marked as alive are discarded.
151 
152  // Remove empty functions from the global ctors list.
154 
155  // Collect the set of members for each comdat.
156  for (Function &F : M)
157  if (Comdat *C = F.getComdat())
158  ComdatMembers.insert(std::make_pair(C, &F));
159  for (GlobalVariable &GV : M.globals())
160  if (Comdat *C = GV.getComdat())
161  ComdatMembers.insert(std::make_pair(C, &GV));
162  for (GlobalAlias &GA : M.aliases())
163  if (Comdat *C = GA.getComdat())
164  ComdatMembers.insert(std::make_pair(C, &GA));
165 
166  // Loop over the module, adding globals which are obviously necessary.
167  for (GlobalObject &GO : M.global_objects()) {
168  Changed |= RemoveUnusedGlobalValue(GO);
169  // Functions with external linkage are needed if they have a body.
170  // Externally visible & appending globals are needed, if they have an
171  // initializer.
172  if (!GO.isDeclaration())
173  if (!GO.isDiscardableIfUnused())
174  MarkLive(GO);
175 
176  UpdateGVDependencies(GO);
177  }
178 
179  // Compute direct dependencies of aliases.
180  for (GlobalAlias &GA : M.aliases()) {
181  Changed |= RemoveUnusedGlobalValue(GA);
182  // Externally visible aliases are needed.
183  if (!GA.isDiscardableIfUnused())
184  MarkLive(GA);
185 
186  UpdateGVDependencies(GA);
187  }
188 
189  // Compute direct dependencies of ifuncs.
190  for (GlobalIFunc &GIF : M.ifuncs()) {
191  Changed |= RemoveUnusedGlobalValue(GIF);
192  // Externally visible ifuncs are needed.
193  if (!GIF.isDiscardableIfUnused())
194  MarkLive(GIF);
195 
196  UpdateGVDependencies(GIF);
197  }
198 
199  // Propagate liveness from collected Global Values through the computed
200  // dependencies.
201  SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
202  AliveGlobals.end()};
203  while (!NewLiveGVs.empty()) {
204  GlobalValue *LGV = NewLiveGVs.pop_back_val();
205  for (auto *GVD : GVDependencies[LGV])
206  MarkLive(*GVD, &NewLiveGVs);
207  }
208 
209  // Now that all globals which are needed are in the AliveGlobals set, we loop
210  // through the program, deleting those which are not alive.
211  //
212 
213  // The first pass is to drop initializers of global variables which are dead.
214  std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
215  for (GlobalVariable &GV : M.globals())
216  if (!AliveGlobals.count(&GV)) {
217  DeadGlobalVars.push_back(&GV); // Keep track of dead globals
218  if (GV.hasInitializer()) {
219  Constant *Init = GV.getInitializer();
220  GV.setInitializer(nullptr);
221  if (isSafeToDestroyConstant(Init))
222  Init->destroyConstant();
223  }
224  }
225 
226  // The second pass drops the bodies of functions which are dead...
227  std::vector<Function *> DeadFunctions;
228  for (Function &F : M)
229  if (!AliveGlobals.count(&F)) {
230  DeadFunctions.push_back(&F); // Keep track of dead globals
231  if (!F.isDeclaration())
232  F.deleteBody();
233  }
234 
235  // The third pass drops targets of aliases which are dead...
236  std::vector<GlobalAlias*> DeadAliases;
237  for (GlobalAlias &GA : M.aliases())
238  if (!AliveGlobals.count(&GA)) {
239  DeadAliases.push_back(&GA);
240  GA.setAliasee(nullptr);
241  }
242 
243  // The fourth pass drops targets of ifuncs which are dead...
244  std::vector<GlobalIFunc*> DeadIFuncs;
245  for (GlobalIFunc &GIF : M.ifuncs())
246  if (!AliveGlobals.count(&GIF)) {
247  DeadIFuncs.push_back(&GIF);
248  GIF.setResolver(nullptr);
249  }
250 
251  // Now that all interferences have been dropped, delete the actual objects
252  // themselves.
253  auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
254  RemoveUnusedGlobalValue(*GV);
255  GV->eraseFromParent();
256  Changed = true;
257  };
258 
259  NumFunctions += DeadFunctions.size();
260  for (Function *F : DeadFunctions)
261  EraseUnusedGlobalValue(F);
262 
263  NumVariables += DeadGlobalVars.size();
264  for (GlobalVariable *GV : DeadGlobalVars)
265  EraseUnusedGlobalValue(GV);
266 
267  NumAliases += DeadAliases.size();
268  for (GlobalAlias *GA : DeadAliases)
269  EraseUnusedGlobalValue(GA);
270 
271  NumIFuncs += DeadIFuncs.size();
272  for (GlobalIFunc *GIF : DeadIFuncs)
273  EraseUnusedGlobalValue(GIF);
274 
275  // Make sure that all memory is released
276  AliveGlobals.clear();
277  ConstantDependenciesCache.clear();
278  GVDependencies.clear();
279  ComdatMembers.clear();
280 
281  if (Changed)
282  return PreservedAnalyses::none();
283  return PreservedAnalyses::all();
284 }
285 
286 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
287 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
288 // If found, check to see if the constant pointer ref is safe to destroy, and if
289 // so, nuke it. This will reduce the reference count on the global value, which
290 // might make it deader.
291 //
292 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
293  if (GV.use_empty())
294  return false;
296  return GV.use_empty();
297 }
uint64_t CallInst * C
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void initializeGlobalDCELegacyPassPass(PassRegistry &)
STATISTIC(NumFunctions, "Total number of functions")
F(f)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", "Dead Global Elimination", false, false) ModulePass *llvm
Definition: GlobalDCE.cpp:70
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:828
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
Definition: PassManager.h:1127
Pass to remove unused function declarations.
Definition: GlobalDCE.h:29
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:558
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
const BasicBlock & getEntryBlock() const
Definition: Function.h:664
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:57
This is an important base class in LLVM.
Definition: Constant.h:41
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:370
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:417
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:377
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
static bool isEmptyFunction(Function *F)
Returns true if F is effectively empty.
Definition: GlobalDCE.cpp:79
const Comdat * getComdat() const
Definition: Globals.cpp:175
iterator_range< user_iterator > users()
Definition: Value.h:419
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing module and deletes it.
Definition: Globals.cpp:85
iterator begin() const
Definition: SmallPtrSet.h:396
#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:224
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:371
iterator end() const
Definition: SmallPtrSet.h:401
LLVM Value Representation.
Definition: Value.h:73
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:116
bool use_empty() const
Definition: Value.h:342
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: GlobalDCE.cpp:141