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"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/IntrinsicInst.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/Operator.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Transforms/IPO.h"
29 
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "globaldce"
33 
34 static cl::opt<bool>
35  ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
36  cl::desc("Enable virtual function elimination"));
37 
38 STATISTIC(NumAliases , "Number of global aliases removed");
39 STATISTIC(NumFunctions, "Number of functions removed");
40 STATISTIC(NumIFuncs, "Number of indirect functions removed");
41 STATISTIC(NumVariables, "Number of global variables removed");
42 STATISTIC(NumVFuncs, "Number of virtual functions removed");
43 
44 namespace {
45  class GlobalDCELegacyPass : public ModulePass {
46  public:
47  static char ID; // Pass identification, replacement for typeid
48  GlobalDCELegacyPass() : ModulePass(ID) {
50  }
51 
52  // run - Do the GlobalDCE pass on the specified module, optionally updating
53  // the specified callgraph to reflect the changes.
54  //
55  bool runOnModule(Module &M) override {
56  if (skipModule(M))
57  return false;
58 
59  // We need a minimally functional dummy module analysis manager. It needs
60  // to at least know about the possibility of proxying a function analysis
61  // manager.
62  FunctionAnalysisManager DummyFAM;
63  ModuleAnalysisManager DummyMAM;
64  DummyMAM.registerPass(
65  [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
66 
67  auto PA = Impl.run(M, DummyMAM);
68  return !PA.areAllPreserved();
69  }
70 
71  private:
72  GlobalDCEPass Impl;
73  };
74 }
75 
77 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
78  "Dead Global Elimination", false, false)
79 
80 // Public interface to the GlobalDCEPass.
82  return new GlobalDCELegacyPass();
83 }
84 
85 /// Returns true if F is effectively empty.
86 static bool isEmptyFunction(Function *F) {
88  for (auto &I : Entry) {
89  if (isa<DbgInfoIntrinsic>(I))
90  continue;
91  if (auto *RI = dyn_cast<ReturnInst>(&I))
92  return !RI->getReturnValue();
93  break;
94  }
95  return false;
96 }
97 
98 /// Compute the set of GlobalValue that depends from V.
99 /// The recursion stops as soon as a GlobalValue is met.
100 void GlobalDCEPass::ComputeDependencies(Value *V,
102  if (auto *I = dyn_cast<Instruction>(V)) {
103  Function *Parent = I->getParent()->getParent();
104  Deps.insert(Parent);
105  } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
106  Deps.insert(GV);
107  } else if (auto *CE = dyn_cast<Constant>(V)) {
108  // Avoid walking the whole tree of a big ConstantExprs multiple times.
109  auto Where = ConstantDependenciesCache.find(CE);
110  if (Where != ConstantDependenciesCache.end()) {
111  auto const &K = Where->second;
112  Deps.insert(K.begin(), K.end());
113  } else {
114  SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
115  for (User *CEUser : CE->users())
116  ComputeDependencies(CEUser, LocalDeps);
117  Deps.insert(LocalDeps.begin(), LocalDeps.end());
118  }
119  }
120 }
121 
122 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
124  for (User *User : GV.users())
125  ComputeDependencies(User, Deps);
126  Deps.erase(&GV); // Remove self-reference.
127  for (GlobalValue *GVU : Deps) {
128  // If this is a dep from a vtable to a virtual function, and we have
129  // complete information about all virtual call sites which could call
130  // though this vtable, then skip it, because the call site information will
131  // be more precise.
132  if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
133  LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
134  << GV.getName() << "\n");
135  continue;
136  }
137  GVDependencies[GVU].insert(&GV);
138  }
139 }
140 
141 /// Mark Global value as Live
142 void GlobalDCEPass::MarkLive(GlobalValue &GV,
144  auto const Ret = AliveGlobals.insert(&GV);
145  if (!Ret.second)
146  return;
147 
148  if (Updates)
149  Updates->push_back(&GV);
150  if (Comdat *C = GV.getComdat()) {
151  for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
152  MarkLive(*CM.second, Updates); // Recursion depth is only two because only
153  // globals in the same comdat are visited.
154  }
155  }
156 }
157 
158 void GlobalDCEPass::ScanVTables(Module &M) {
160  LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
161 
162  auto *LTOPostLinkMD =
163  cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
164  bool LTOPostLink =
165  LTOPostLinkMD &&
166  (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0);
167 
168  for (GlobalVariable &GV : M.globals()) {
169  Types.clear();
170  GV.getMetadata(LLVMContext::MD_type, Types);
171  if (GV.isDeclaration() || Types.empty())
172  continue;
173 
174  // Use the typeid metadata on the vtable to build a mapping from typeids to
175  // the list of (GV, offset) pairs which are the possible vtables for that
176  // typeid.
177  for (MDNode *Type : Types) {
178  Metadata *TypeID = Type->getOperand(1).get();
179 
180  uint64_t Offset =
181  cast<ConstantInt>(
182  cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
183  ->getZExtValue();
184 
185  TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
186  }
187 
188  // If the type corresponding to the vtable is private to this translation
189  // unit, we know that we can see all virtual functions which might use it,
190  // so VFE is safe.
191  if (auto GO = dyn_cast<GlobalObject>(&GV)) {
192  GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
194  (LTOPostLink &&
196  LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
197  VFESafeVTables.insert(&GV);
198  }
199  }
200  }
201 }
202 
203 void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
204  uint64_t CallOffset) {
205  for (auto &VTableInfo : TypeIdMap[TypeId]) {
206  GlobalVariable *VTable = VTableInfo.first;
207  uint64_t VTableOffset = VTableInfo.second;
208 
209  Constant *Ptr =
210  getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
211  *Caller->getParent());
212  if (!Ptr) {
213  LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
214  VFESafeVTables.erase(VTable);
215  return;
216  }
217 
218  auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
219  if (!Callee) {
220  LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
221  VFESafeVTables.erase(VTable);
222  return;
223  }
224 
225  LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
226  << Callee->getName() << "\n");
227  GVDependencies[Caller].insert(Callee);
228  }
229 }
230 
231 void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
232  LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
233  Function *TypeCheckedLoadFunc =
234  M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
235 
236  if (!TypeCheckedLoadFunc)
237  return;
238 
239  for (auto U : TypeCheckedLoadFunc->users()) {
240  auto CI = dyn_cast<CallInst>(U);
241  if (!CI)
242  continue;
243 
244  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
245  Value *TypeIdValue = CI->getArgOperand(2);
246  auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
247 
248  if (Offset) {
249  ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
250  } else {
251  // type.checked.load with a non-constant offset, so assume every entry in
252  // every matching vtable is used.
253  for (auto &VTableInfo : TypeIdMap[TypeId]) {
254  VFESafeVTables.erase(VTableInfo.first);
255  }
256  }
257  }
258 }
259 
260 void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
261  if (!ClEnableVFE)
262  return;
263 
264  ScanVTables(M);
265 
266  if (VFESafeVTables.empty())
267  return;
268 
269  ScanTypeCheckedLoadIntrinsics(M);
270 
271  LLVM_DEBUG(
272  dbgs() << "VFE safe vtables:\n";
273  for (auto *VTable : VFESafeVTables)
274  dbgs() << " " << VTable->getName() << "\n";
275  );
276 }
277 
279  bool Changed = false;
280 
281  // The algorithm first computes the set L of global variables that are
282  // trivially live. Then it walks the initialization of these variables to
283  // compute the globals used to initialize them, which effectively builds a
284  // directed graph where nodes are global variables, and an edge from A to B
285  // means B is used to initialize A. Finally, it propagates the liveness
286  // information through the graph starting from the nodes in L. Nodes note
287  // marked as alive are discarded.
288 
289  // Remove empty functions from the global ctors list.
291 
292  // Collect the set of members for each comdat.
293  for (Function &F : M)
294  if (Comdat *C = F.getComdat())
295  ComdatMembers.insert(std::make_pair(C, &F));
296  for (GlobalVariable &GV : M.globals())
297  if (Comdat *C = GV.getComdat())
298  ComdatMembers.insert(std::make_pair(C, &GV));
299  for (GlobalAlias &GA : M.aliases())
300  if (Comdat *C = GA.getComdat())
301  ComdatMembers.insert(std::make_pair(C, &GA));
302 
303  // Add dependencies between virtual call sites and the virtual functions they
304  // might call, if we have that information.
305  AddVirtualFunctionDependencies(M);
306 
307  // Loop over the module, adding globals which are obviously necessary.
308  for (GlobalObject &GO : M.global_objects()) {
309  Changed |= RemoveUnusedGlobalValue(GO);
310  // Functions with external linkage are needed if they have a body.
311  // Externally visible & appending globals are needed, if they have an
312  // initializer.
313  if (!GO.isDeclaration())
314  if (!GO.isDiscardableIfUnused())
315  MarkLive(GO);
316 
317  UpdateGVDependencies(GO);
318  }
319 
320  // Compute direct dependencies of aliases.
321  for (GlobalAlias &GA : M.aliases()) {
322  Changed |= RemoveUnusedGlobalValue(GA);
323  // Externally visible aliases are needed.
324  if (!GA.isDiscardableIfUnused())
325  MarkLive(GA);
326 
327  UpdateGVDependencies(GA);
328  }
329 
330  // Compute direct dependencies of ifuncs.
331  for (GlobalIFunc &GIF : M.ifuncs()) {
332  Changed |= RemoveUnusedGlobalValue(GIF);
333  // Externally visible ifuncs are needed.
334  if (!GIF.isDiscardableIfUnused())
335  MarkLive(GIF);
336 
337  UpdateGVDependencies(GIF);
338  }
339 
340  // Propagate liveness from collected Global Values through the computed
341  // dependencies.
342  SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
343  AliveGlobals.end()};
344  while (!NewLiveGVs.empty()) {
345  GlobalValue *LGV = NewLiveGVs.pop_back_val();
346  for (auto *GVD : GVDependencies[LGV])
347  MarkLive(*GVD, &NewLiveGVs);
348  }
349 
350  // Now that all globals which are needed are in the AliveGlobals set, we loop
351  // through the program, deleting those which are not alive.
352  //
353 
354  // The first pass is to drop initializers of global variables which are dead.
355  std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
356  for (GlobalVariable &GV : M.globals())
357  if (!AliveGlobals.count(&GV)) {
358  DeadGlobalVars.push_back(&GV); // Keep track of dead globals
359  if (GV.hasInitializer()) {
360  Constant *Init = GV.getInitializer();
361  GV.setInitializer(nullptr);
362  if (isSafeToDestroyConstant(Init))
363  Init->destroyConstant();
364  }
365  }
366 
367  // The second pass drops the bodies of functions which are dead...
368  std::vector<Function *> DeadFunctions;
369  for (Function &F : M)
370  if (!AliveGlobals.count(&F)) {
371  DeadFunctions.push_back(&F); // Keep track of dead globals
372  if (!F.isDeclaration())
373  F.deleteBody();
374  }
375 
376  // The third pass drops targets of aliases which are dead...
377  std::vector<GlobalAlias*> DeadAliases;
378  for (GlobalAlias &GA : M.aliases())
379  if (!AliveGlobals.count(&GA)) {
380  DeadAliases.push_back(&GA);
381  GA.setAliasee(nullptr);
382  }
383 
384  // The fourth pass drops targets of ifuncs which are dead...
385  std::vector<GlobalIFunc*> DeadIFuncs;
386  for (GlobalIFunc &GIF : M.ifuncs())
387  if (!AliveGlobals.count(&GIF)) {
388  DeadIFuncs.push_back(&GIF);
389  GIF.setResolver(nullptr);
390  }
391 
392  // Now that all interferences have been dropped, delete the actual objects
393  // themselves.
394  auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
395  RemoveUnusedGlobalValue(*GV);
396  GV->eraseFromParent();
397  Changed = true;
398  };
399 
400  NumFunctions += DeadFunctions.size();
401  for (Function *F : DeadFunctions) {
402  if (!F->use_empty()) {
403  // Virtual functions might still be referenced by one or more vtables,
404  // but if we've proven them to be unused then it's safe to replace the
405  // virtual function pointers with null, allowing us to remove the
406  // function itself.
407  ++NumVFuncs;
408  F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
409  }
410  EraseUnusedGlobalValue(F);
411  }
412 
413  NumVariables += DeadGlobalVars.size();
414  for (GlobalVariable *GV : DeadGlobalVars)
415  EraseUnusedGlobalValue(GV);
416 
417  NumAliases += DeadAliases.size();
418  for (GlobalAlias *GA : DeadAliases)
419  EraseUnusedGlobalValue(GA);
420 
421  NumIFuncs += DeadIFuncs.size();
422  for (GlobalIFunc *GIF : DeadIFuncs)
423  EraseUnusedGlobalValue(GIF);
424 
425  // Make sure that all memory is released
426  AliveGlobals.clear();
427  ConstantDependenciesCache.clear();
428  GVDependencies.clear();
429  ComdatMembers.clear();
430  TypeIdMap.clear();
431  VFESafeVTables.clear();
432 
433  if (Changed)
434  return PreservedAnalyses::none();
435  return PreservedAnalyses::all();
436 }
437 
438 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
439 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
440 // If found, check to see if the constant pointer ref is safe to destroy, and if
441 // so, nuke it. This will reduce the reference count on the global value, which
442 // might make it deader.
443 //
444 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
445  if (GV.use_empty())
446  return false;
448  return GV.use_empty();
449 }
uint64_t CallInst * C
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
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:66
static cl::opt< bool > ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore, cl::desc("Enable virtual function elimination"))
This class represents a function call, abstracting a target machine&#39;s calling convention.
void initializeGlobalDCELegacyPassPass(PassRegistry &)
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:863
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:77
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:640
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:829
TypeID
Definitions of all of the base types for the Type system.
Definition: Type.h:55
InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy
Provide the FunctionAnalysisManager to Module proxy.
Definition: PassManager.h:1128
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:571
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:157
const BasicBlock & getEntryBlock() const
Definition: Function.h:669
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1432
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Metadata * getModuleFlag(StringRef Key) const
Return the corresponding value if Key appears in module flags, otherwise return null.
Definition: Module.cpp:310
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
Type::TypeID TypeID
const Constant * stripPointerCasts() const
Definition: Constant.h:183
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:160
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
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
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:86
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:174
const Comdat * getComdat() const
Definition: Globals.cpp:175
amdgpu Simplify well known AMD library false FunctionCallee Callee
iterator_range< user_iterator > users()
Definition: Value.h:420
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
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#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
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
void destroyConstant()
Called if some element of this constant is no longer valid.
Definition: Constants.cpp:386
iterator end() const
Definition: SmallPtrSet.h:401
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:231
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:74
iterator_range< global_iterator > globals()
Definition: Module.h:588
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:116
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Root of the metadata hierarchy.
Definition: Metadata.h:57
bool use_empty() const
Definition: Value.h:343
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: GlobalDCE.cpp:278