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 "IPOOptions.h"
19#include "llvm/ADT/DenseSet.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/Analysis/TypeMetadataUtils.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/Module.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/Pass.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
36namespace {
37class GlobalDCELegacyPass : public ModulePass {
38public:
39 static char ID; // Pass identification, replacement for typeid
40 GlobalDCELegacyPass() : ModulePass(ID) {}
41 bool runOnModule(Module &M) override {
42 if (skipModule(M))
43 return false;
44 // Note: GlobalDCEPass does not use any analyses, so we're safe to call the
45 // new-pm style pass with a default-initialized analysis manager here
46 ModuleAnalysisManager MAM;
47 auto PA = Impl.run(M, MAM);
48 return !PA.areAllPreserved();
49 }
50
51private:
52 GlobalDCEPass Impl;
53};
54} // namespace
55
56char GlobalDCELegacyPass::ID = 0;
57INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", "Dead Global Elimination",
58 false, false)
59
60// Public interface to the GlobalDCEPass.
61ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCELegacyPass(); }
62
63STATISTIC(NumAliases , "Number of global aliases removed");
64STATISTIC(NumFunctions, "Number of functions removed");
65STATISTIC(NumIFuncs, "Number of indirect functions removed");
66STATISTIC(NumVariables, "Number of global variables removed");
67STATISTIC(NumVFuncs, "Number of virtual functions removed");
68
69/// Returns true if F is effectively empty.
70static bool isEmptyFunction(Function *F) {
71 // Skip external functions.
72 if (F->isDeclaration())
73 return false;
74 BasicBlock &Entry = F->getEntryBlock();
75 for (auto &I : Entry) {
76 if (isa<PseudoProbeInst>(Val: I))
77 continue;
78 if (auto *RI = dyn_cast<ReturnInst>(Val: &I))
79 return !RI->getReturnValue();
80 break;
81 }
82 return false;
83}
84
85/// Compute the set of GlobalValue that depends from V.
86/// The recursion stops as soon as a GlobalValue is met.
87void GlobalDCEPass::ComputeDependencies(Value *V,
88 SmallPtrSetImpl<GlobalValue *> &Deps) {
89 if (auto *I = dyn_cast<Instruction>(Val: V)) {
90 Function *Parent = I->getParent()->getParent();
91 Deps.insert(Ptr: Parent);
92 } else if (auto *GV = dyn_cast<GlobalValue>(Val: V)) {
93 Deps.insert(Ptr: GV);
94 } else if (auto *CE = dyn_cast<Constant>(Val: V)) {
95 // Avoid walking the whole tree of a big ConstantExprs multiple times.
96 auto Where = ConstantDependenciesCache.find(Val: CE);
97 if (Where == ConstantDependenciesCache.end()) {
98 // Compute into a local set first: the recursion can insert into the
99 // cache, which would invalidate references into it.
100 SmallPtrSet<GlobalValue *, 8> LocalDeps;
101 for (User *CEUser : CE->users())
102 ComputeDependencies(V: CEUser, Deps&: LocalDeps);
103 Where =
104 ConstantDependenciesCache.try_emplace(Key: CE, Args: std::move(LocalDeps)).first;
105 }
106 Deps.insert_range(R&: Where->second);
107 }
108}
109
110void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
111 SmallPtrSet<GlobalValue *, 8> Deps;
112 for (User *User : GV.users())
113 ComputeDependencies(V: User, Deps);
114 Deps.erase(Ptr: &GV); // Remove self-reference.
115 for (GlobalValue *GVU : Deps) {
116 // If this is a dep from a vtable to a virtual function, and we have
117 // complete information about all virtual call sites which could call
118 // though this vtable, then skip it, because the call site information will
119 // be more precise.
120 if (VFESafeVTables.count(Ptr: GVU) && isa<Function>(Val: &GV)) {
121 LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
122 << GV.getName() << "\n");
123 continue;
124 }
125 GVDependencies[GVU].insert(Ptr: &GV);
126 }
127}
128
129/// Mark Global value as Live
130void GlobalDCEPass::MarkLive(GlobalValue &GV,
131 SmallVectorImpl<GlobalValue *> *Updates) {
132 auto const Ret = AliveGlobals.insert(Ptr: &GV);
133 if (!Ret.second)
134 return;
135
136 if (Updates)
137 Updates->push_back(Elt: &GV);
138 if (Comdat *C = GV.getComdat()) {
139 for (auto &&CM : make_range(p: ComdatMembers.equal_range(x: C))) {
140 MarkLive(GV&: *CM.second, Updates); // Recursion depth is only two because only
141 // globals in the same comdat are visited.
142 }
143 }
144}
145
146void GlobalDCEPass::ScanVTables(Module &M) {
147 SmallVector<MDNode *, 2> Types;
148 LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
149
150 for (GlobalVariable &GV : M.globals()) {
151 Types.clear();
152 GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
153 if (GV.isDeclaration() || Types.empty())
154 continue;
155
156 // Use the typeid metadata on the vtable to build a mapping from typeids to
157 // the list of (GV, offset) pairs which are the possible vtables for that
158 // typeid.
159 for (MDNode *Type : Types) {
160 Metadata *TypeID = Type->getOperand(I: 1).get();
161
162 uint64_t Offset =
163 cast<ConstantInt>(
164 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
165 ->getZExtValue();
166
167 TypeIdMap[TypeID].insert(V: std::make_pair(x: &GV, y&: Offset));
168 }
169
170 // If the type corresponding to the vtable is private to this translation
171 // unit, we know that we can see all virtual functions which might use it,
172 // so VFE is safe.
173 GlobalObject::VCallVisibility TypeVis = GV.getVCallVisibility();
174 if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
175 (InLTOPostLink &&
176 TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
177 LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
178 VFESafeVTables.insert(Ptr: &GV);
179 }
180 }
181}
182
183void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
184 uint64_t CallOffset) {
185 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
186 GlobalVariable *VTable = VTableInfo.first;
187 uint64_t VTableOffset = VTableInfo.second;
188
189 Constant *Ptr =
190 getPointerAtOffset(I: VTable->getInitializer(), Offset: VTableOffset + CallOffset,
191 M&: *Caller->getParent(), TopLevelGlobal: VTable);
192 if (!Ptr) {
193 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
194 VFESafeVTables.erase(Ptr: VTable);
195 continue;
196 }
197
198 auto Callee = dyn_cast<Function>(Val: Ptr->stripPointerCasts());
199 if (!Callee) {
200 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
201 VFESafeVTables.erase(Ptr: VTable);
202 continue;
203 }
204
205 LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
206 << Callee->getName() << "\n");
207 VFuncDependencies[Caller].insert(X: {VTable, Callee});
208 }
209}
210
211void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
212 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
213 Function *TypeCheckedLoadFunc =
214 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_checked_load);
215 Function *TypeCheckedLoadRelativeFunc = Intrinsic::getDeclarationIfExists(
216 M: &M, id: Intrinsic::type_checked_load_relative);
217
218 // Keep track of which (function, type id, offset) triples we've already
219 // scanned, to prevent repeated work.
220 DenseSet<std::tuple<Function *, Metadata *, uint64_t>> ScannedLoads;
221
222 auto scan = [&](Function *CheckedLoadFunc) {
223 if (!CheckedLoadFunc)
224 return;
225
226 for (auto *U : CheckedLoadFunc->users()) {
227 auto CI = dyn_cast<CallInst>(Val: U);
228 if (!CI)
229 continue;
230
231 auto *Offset = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 1));
232 Value *TypeIdValue = CI->getArgOperand(i: 2);
233 auto *TypeId = cast<MetadataAsValue>(Val: TypeIdValue)->getMetadata();
234
235 if (Offset) {
236 if (ScannedLoads
237 .insert(V: {CI->getFunction(), TypeId, Offset->getZExtValue()})
238 .second)
239 ScanVTableLoad(Caller: CI->getFunction(), TypeId, CallOffset: Offset->getZExtValue());
240 } else {
241 // type.checked.load with a non-constant offset, so assume every entry
242 // in every matching vtable is used.
243 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
244 VFESafeVTables.erase(Ptr: VTableInfo.first);
245 }
246 }
247 }
248 };
249
250 scan(TypeCheckedLoadFunc);
251 scan(TypeCheckedLoadRelativeFunc);
252}
253
254void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
255 if (!getIPOOptions(M).enable_vfe)
256 return;
257
258 // If the Virtual Function Elim module flag is present and set to zero, then
259 // the vcall_visibility metadata was inserted for another optimization (WPD)
260 // and we may not have type checked loads on all accesses to the vtable.
261 // Don't attempt VFE in that case.
262 auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
263 MD: M.getModuleFlag(Key: "Virtual Function Elim"));
264 if (!Val || Val->isZero())
265 return;
266
267 ScanVTables(M);
268
269 if (VFESafeVTables.empty())
270 return;
271
272 ScanTypeCheckedLoadIntrinsics(M);
273
274 LLVM_DEBUG(
275 dbgs() << "VFE safe vtables:\n";
276 for (auto *VTable : VFESafeVTables)
277 dbgs() << " " << VTable->getName() << "\n";
278 );
279}
280
281PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
282 bool Changed = false;
283
284 // Only the analyses of the deleted functions need to be cleared.
285 FunctionAnalysisManager *FAM = nullptr;
286 if (MAM.isPassRegistered<FunctionAnalysisManagerModuleProxy>()) {
287 if (auto *FAMProxy =
288 MAM.getCachedResult<FunctionAnalysisManagerModuleProxy>(IR&: M))
289 FAM = &FAMProxy->getManager();
290 }
291
292 // The algorithm first computes the set L of global variables that are
293 // trivially live.
294 //
295 // Then it walks the initialization of these variables to compute the globals
296 // used to initialize them, which effectively builds a directed graph where
297 // nodes are global variables, and an edge from A to B means B is used to
298 // initialize A.
299 //
300 // Finally, it propagates the liveness information through the graph starting
301 // from the nodes in L. A virtual call only keeps a virtual function alive
302 // when its vtable is also live.
303 //
304 // Nodes not marked as alive are discarded.
305
306 // Remove empty functions from the global ctors list.
307 Changed |= optimizeGlobalCtorsList(
308 M, ShouldRemove: [](uint32_t, Function *F) { return isEmptyFunction(F); });
309
310 // Collect the set of members for each comdat.
311 for (Function &F : M)
312 if (Comdat *C = F.getComdat())
313 ComdatMembers.insert(x: std::make_pair(x&: C, y: &F));
314 for (GlobalVariable &GV : M.globals())
315 if (Comdat *C = GV.getComdat())
316 ComdatMembers.insert(x: std::make_pair(x&: C, y: &GV));
317 for (GlobalAlias &GA : M.aliases())
318 if (Comdat *C = GA.getComdat())
319 ComdatMembers.insert(x: std::make_pair(x&: C, y: &GA));
320
321 // Add dependencies between virtual call sites and the virtual functions they
322 // might call, if we have that information.
323 AddVirtualFunctionDependencies(M);
324
325 // Loop over the module, adding globals which are obviously necessary.
326 for (GlobalObject &GO : M.global_objects()) {
327 GO.removeDeadConstantUsers();
328 // Functions with external linkage are needed if they have a body.
329 // Externally visible & appending globals are needed, if they have an
330 // initializer.
331 if (!GO.isDeclaration())
332 if (!GO.isDiscardableIfUnused())
333 MarkLive(GV&: GO);
334
335 UpdateGVDependencies(GV&: GO);
336 }
337
338 // Compute direct dependencies of aliases.
339 for (GlobalAlias &GA : M.aliases()) {
340 GA.removeDeadConstantUsers();
341 // Externally visible aliases are needed.
342 if (!GA.isDiscardableIfUnused())
343 MarkLive(GV&: GA);
344
345 UpdateGVDependencies(GV&: GA);
346 }
347
348 // Compute direct dependencies of ifuncs.
349 for (GlobalIFunc &GIF : M.ifuncs()) {
350 GIF.removeDeadConstantUsers();
351 // Externally visible ifuncs are needed.
352 if (!GIF.isDiscardableIfUnused())
353 MarkLive(GV&: GIF);
354
355 UpdateGVDependencies(GV&: GIF);
356 }
357
358 // Propagate liveness from collected Global Values through the computed
359 // dependencies.
360 SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
361 AliveGlobals.end()};
362 while (!NewLiveGVs.empty()) {
363 GlobalValue *LGV = NewLiveGVs.pop_back_val();
364 for (auto *GVD : GVDependencies[LGV])
365 MarkLive(GV&: *GVD, Updates: &NewLiveGVs);
366
367 // A virtual call keeps a virtual function alive only if the vtable it is
368 // loaded from is alive too. If the vtable is not live, defer the function:
369 // the vtable may become live later.
370 if (auto *F = dyn_cast<Function>(Val: LGV)) {
371 if (auto It = VFuncDependencies.find(Val: F); It != VFuncDependencies.end()) {
372 for (auto [VTable, VFunc] : It->second) {
373 if (AliveGlobals.contains(Ptr: VTable))
374 MarkLive(GV&: *VFunc, Updates: &NewLiveGVs);
375 else
376 PendingVFuncs[VTable].push_back(Elt: VFunc);
377 }
378 }
379 }
380
381 // If LGV is a vtable that became alive later, mark its deferred functions
382 // live.
383 if (auto *VT = dyn_cast<GlobalVariable>(Val: LGV)) {
384 if (auto It = PendingVFuncs.find(Val: VT); It != PendingVFuncs.end()) {
385 for (auto *VFunc : It->second)
386 MarkLive(GV&: *VFunc, Updates: &NewLiveGVs);
387 }
388 }
389 }
390
391 // Now that all globals which are needed are in the AliveGlobals set, we loop
392 // through the program, deleting those which are not alive.
393 //
394
395 // The first pass is to drop initializers of global variables which are dead.
396 std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
397 for (GlobalVariable &GV : M.globals())
398 if (!AliveGlobals.count(Ptr: &GV)) {
399 DeadGlobalVars.push_back(x: &GV); // Keep track of dead globals
400 if (GV.hasInitializer()) {
401 Constant *Init = GV.getInitializer();
402 GV.setInitializer(nullptr);
403 if (isSafeToDestroyConstant(C: Init))
404 Init->destroyConstant();
405 }
406 }
407
408 // The second pass drops the bodies of functions which are dead...
409 std::vector<Function *> DeadFunctions;
410 for (Function &F : M)
411 if (!AliveGlobals.count(Ptr: &F)) {
412 DeadFunctions.push_back(x: &F); // Keep track of dead globals
413 if (FAM)
414 FAM->clear(IR&: F, Name: F.getName());
415 if (!F.isDeclaration())
416 F.deleteBody();
417 }
418
419 // The third pass drops targets of aliases which are dead...
420 std::vector<GlobalAlias*> DeadAliases;
421 for (GlobalAlias &GA : M.aliases())
422 if (!AliveGlobals.count(Ptr: &GA)) {
423 DeadAliases.push_back(x: &GA);
424 GA.setAliasee(nullptr);
425 }
426
427 // The fourth pass drops targets of ifuncs which are dead...
428 std::vector<GlobalIFunc*> DeadIFuncs;
429 for (GlobalIFunc &GIF : M.ifuncs())
430 if (!AliveGlobals.count(Ptr: &GIF)) {
431 DeadIFuncs.push_back(x: &GIF);
432 GIF.setResolver(nullptr);
433 }
434
435 // Now that all interferences have been dropped, delete the actual objects
436 // themselves.
437 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
438 GV->removeDeadConstantUsers();
439 GV->eraseFromParent();
440 Changed = true;
441 };
442
443 NumFunctions += DeadFunctions.size();
444 for (Function *F : DeadFunctions) {
445 if (!F->use_empty()) {
446 // Virtual functions might still be referenced by one or more vtables,
447 // but if we've proven them to be unused then it's safe to replace the
448 // virtual function pointers with null, allowing us to remove the
449 // function itself.
450 ++NumVFuncs;
451
452 // Detect vfuncs that are referenced as "relative pointers" which are used
453 // in Swift vtables, i.e. entries in the form of:
454 //
455 // i32 trunc (i64 sub (i64 ptrtoint @f, i64 ptrtoint ...)) to i32)
456 //
457 // In this case, replace the whole "sub" expression with constant 0 to
458 // avoid leaving a weird sub(0, symbol) expression behind.
459 replaceRelativePointerUsersWithZero(C: F);
460
461 F->replaceNonMetadataUsesWith(V: ConstantPointerNull::get(T: F->getType()));
462 }
463 EraseUnusedGlobalValue(F);
464 }
465
466 NumVariables += DeadGlobalVars.size();
467 for (GlobalVariable *GV : DeadGlobalVars)
468 EraseUnusedGlobalValue(GV);
469
470 NumAliases += DeadAliases.size();
471 for (GlobalAlias *GA : DeadAliases)
472 EraseUnusedGlobalValue(GA);
473
474 NumIFuncs += DeadIFuncs.size();
475 for (GlobalIFunc *GIF : DeadIFuncs)
476 EraseUnusedGlobalValue(GIF);
477
478 // Make sure that all memory is released
479 AliveGlobals.clear();
480 ConstantDependenciesCache.clear();
481 GVDependencies.clear();
482 VFuncDependencies.clear();
483 PendingVFuncs.clear();
484 ComdatMembers.clear();
485 TypeIdMap.clear();
486 VFESafeVTables.clear();
487
488 if (!Changed)
489 return PreservedAnalyses::all();
490
491 PreservedAnalyses PA;
492 PA.preserve<FunctionAnalysisManagerModuleProxy>();
493 PA.preserveSet<AllAnalysesOn<Function>>();
494 return PA;
495}
496
497void GlobalDCEPass::printPipeline(
498 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
499 static_cast<PassInfoMixin<GlobalDCEPass> *>(this)->printPipeline(
500 OS, MapClassName2PassName);
501 if (InLTOPostLink)
502 OS << "<vfe-linkage-unit-visibility>";
503}
504