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
17#include "llvm/Transforms/IPO/GlobalDCE.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/TypeMetadataUtils.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"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Transforms/IPO.h"
29#include "llvm/Transforms/Utils/CtorUtils.h"
30#include "llvm/Transforms/Utils/GlobalStatus.h"
31
32using namespace llvm;
33
34#define DEBUG_TYPE "globaldce"
35
36static cl::opt<bool>
37    ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
38                cl::desc("Enable virtual function elimination"));
39
40STATISTIC(NumAliases  , "Number of global aliases removed");
41STATISTIC(NumFunctions, "Number of functions removed");
42STATISTIC(NumIFuncs,    "Number of indirect functions removed");
43STATISTIC(NumVariables, "Number of global variables removed");
44STATISTIC(NumVFuncs,    "Number of virtual functions removed");
45
46namespace {
47  class GlobalDCELegacyPass : public ModulePass {
48  public:
49    static char ID; // Pass identification, replacement for typeid
50    GlobalDCELegacyPass() : ModulePass(ID) {
51      initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
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
78char GlobalDCELegacyPass::ID = 0;
79INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
80                "Dead Global Elimination", false, false)
81
82// Public interface to the GlobalDCEPass.
83ModulePass *llvm::createGlobalDCEPass() {
84  return new GlobalDCELegacyPass();
85}
86
87/// Returns true if F is effectively empty.
88static 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.
102void GlobalDCEPass::ComputeDependencies(Value *V,
103                                        SmallPtrSetImpl<GlobalValue *> &Deps) {
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
124void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
125  SmallPtrSet<GlobalValue *, 8> Deps;
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
144void GlobalDCEPass::MarkLive(GlobalValue &GV,
145                             SmallVectorImpl<GlobalValue *> *Updates) {
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
160void GlobalDCEPass::ScanVTables(Module &M) {
161  SmallVector<MDNode *, 2> Types;
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();
195      if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
196          (LTOPostLink &&
197           TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
198        LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
199        VFESafeVTables.insert(&GV);
200      }
201    }
202  }
203}
204
205void 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
233void 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
262void 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
289PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
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.
301  Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
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//
455bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
456  if (GV.use_empty())
457    return false;
458  GV.removeDeadConstantUsers();
459  return GV.use_empty();
460}
461