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