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/InitializePasses.h"
25#include "llvm/Pass.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Transforms/IPO.h"
28#include "llvm/Transforms/Utils/CtorUtils.h"
29#include "llvm/Transforms/Utils/GlobalStatus.h"
30
31using namespace llvm;
32
33#define DEBUG_TYPE "globaldce"
34
35namespace {
36class GlobalDCELegacyPass : public ModulePass {
37public:
38 static char ID; // Pass identification, replacement for typeid
39 GlobalDCELegacyPass() : ModulePass(ID) {
40 initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
41 }
42 bool runOnModule(Module &M) override {
43 if (skipModule(M))
44 return false;
45 // Note: GlobalDCEPass does not use any analyses, so we're safe to call the
46 // new-pm style pass with a default-initialized analysis manager here
47 ModuleAnalysisManager MAM;
48 auto PA = Impl.run(M, MAM);
49 return !PA.areAllPreserved();
50 }
51
52private:
53 GlobalDCEPass Impl;
54};
55} // namespace
56
57char GlobalDCELegacyPass::ID = 0;
58INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", "Dead Global Elimination",
59 false, false)
60
61// Public interface to the GlobalDCEPass.
62ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCELegacyPass(); }
63
64static cl::opt<bool>
65 ClEnableVFE("enable-vfe", cl::Hidden, cl::init(Val: true),
66 cl::desc("Enable virtual function elimination"));
67
68STATISTIC(NumAliases , "Number of global aliases removed");
69STATISTIC(NumFunctions, "Number of functions removed");
70STATISTIC(NumIFuncs, "Number of indirect functions removed");
71STATISTIC(NumVariables, "Number of global variables removed");
72STATISTIC(NumVFuncs, "Number of virtual functions removed");
73
74/// Returns true if F is effectively empty.
75static bool isEmptyFunction(Function *F) {
76 // Skip external functions.
77 if (F->isDeclaration())
78 return false;
79 BasicBlock &Entry = F->getEntryBlock();
80 for (auto &I : Entry) {
81 if (I.isDebugOrPseudoInst())
82 continue;
83 if (auto *RI = dyn_cast<ReturnInst>(Val: &I))
84 return !RI->getReturnValue();
85 break;
86 }
87 return false;
88}
89
90/// Compute the set of GlobalValue that depends from V.
91/// The recursion stops as soon as a GlobalValue is met.
92void GlobalDCEPass::ComputeDependencies(Value *V,
93 SmallPtrSetImpl<GlobalValue *> &Deps) {
94 if (auto *I = dyn_cast<Instruction>(Val: V)) {
95 Function *Parent = I->getParent()->getParent();
96 Deps.insert(Ptr: Parent);
97 } else if (auto *GV = dyn_cast<GlobalValue>(Val: V)) {
98 Deps.insert(Ptr: GV);
99 } else if (auto *CE = dyn_cast<Constant>(Val: V)) {
100 // Avoid walking the whole tree of a big ConstantExprs multiple times.
101 auto [Where, Inserted] = ConstantDependenciesCache.try_emplace(k: CE);
102 SmallPtrSetImpl<GlobalValue *> &LocalDeps = Where->second;
103 if (Inserted) {
104 for (User *CEUser : CE->users())
105 ComputeDependencies(V: CEUser, Deps&: LocalDeps);
106 }
107 Deps.insert_range(R&: LocalDeps);
108 }
109}
110
111void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
112 SmallPtrSet<GlobalValue *, 8> Deps;
113 for (User *User : GV.users())
114 ComputeDependencies(V: User, Deps);
115 Deps.erase(Ptr: &GV); // Remove self-reference.
116 for (GlobalValue *GVU : Deps) {
117 // If this is a dep from a vtable to a virtual function, and we have
118 // complete information about all virtual call sites which could call
119 // though this vtable, then skip it, because the call site information will
120 // be more precise.
121 if (VFESafeVTables.count(Ptr: GVU) && isa<Function>(Val: &GV)) {
122 LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
123 << GV.getName() << "\n");
124 continue;
125 }
126 GVDependencies[GVU].insert(Ptr: &GV);
127 }
128}
129
130/// Mark Global value as Live
131void GlobalDCEPass::MarkLive(GlobalValue &GV,
132 SmallVectorImpl<GlobalValue *> *Updates) {
133 auto const Ret = AliveGlobals.insert(Ptr: &GV);
134 if (!Ret.second)
135 return;
136
137 if (Updates)
138 Updates->push_back(Elt: &GV);
139 if (Comdat *C = GV.getComdat()) {
140 for (auto &&CM : make_range(p: ComdatMembers.equal_range(x: C))) {
141 MarkLive(GV&: *CM.second, Updates); // Recursion depth is only two because only
142 // globals in the same comdat are visited.
143 }
144 }
145}
146
147void GlobalDCEPass::ScanVTables(Module &M) {
148 SmallVector<MDNode *, 2> Types;
149 LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
150
151 for (GlobalVariable &GV : M.globals()) {
152 Types.clear();
153 GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
154 if (GV.isDeclaration() || Types.empty())
155 continue;
156
157 // Use the typeid metadata on the vtable to build a mapping from typeids to
158 // the list of (GV, offset) pairs which are the possible vtables for that
159 // typeid.
160 for (MDNode *Type : Types) {
161 Metadata *TypeID = Type->getOperand(I: 1).get();
162
163 uint64_t Offset =
164 cast<ConstantInt>(
165 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
166 ->getZExtValue();
167
168 TypeIdMap[TypeID].insert(V: std::make_pair(x: &GV, y&: Offset));
169 }
170
171 // If the type corresponding to the vtable is private to this translation
172 // unit, we know that we can see all virtual functions which might use it,
173 // so VFE is safe.
174 if (auto GO = dyn_cast<GlobalObject>(Val: &GV)) {
175 GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
176 if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
177 (InLTOPostLink &&
178 TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
179 LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
180 VFESafeVTables.insert(Ptr: &GV);
181 }
182 }
183 }
184}
185
186void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
187 uint64_t CallOffset) {
188 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
189 GlobalVariable *VTable = VTableInfo.first;
190 uint64_t VTableOffset = VTableInfo.second;
191
192 Constant *Ptr =
193 getPointerAtOffset(I: VTable->getInitializer(), Offset: VTableOffset + CallOffset,
194 M&: *Caller->getParent(), TopLevelGlobal: VTable);
195 if (!Ptr) {
196 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
197 VFESafeVTables.erase(Ptr: VTable);
198 continue;
199 }
200
201 auto Callee = dyn_cast<Function>(Val: Ptr->stripPointerCasts());
202 if (!Callee) {
203 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
204 VFESafeVTables.erase(Ptr: VTable);
205 continue;
206 }
207
208 LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
209 << Callee->getName() << "\n");
210 GVDependencies[Caller].insert(Ptr: Callee);
211 }
212}
213
214void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
215 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
216 Function *TypeCheckedLoadFunc =
217 Intrinsic::getDeclarationIfExists(M: &M, id: Intrinsic::type_checked_load);
218 Function *TypeCheckedLoadRelativeFunc = Intrinsic::getDeclarationIfExists(
219 M: &M, id: Intrinsic::type_checked_load_relative);
220
221 auto scan = [&](Function *CheckedLoadFunc) {
222 if (!CheckedLoadFunc)
223 return;
224
225 for (auto *U : CheckedLoadFunc->users()) {
226 auto CI = dyn_cast<CallInst>(Val: U);
227 if (!CI)
228 continue;
229
230 auto *Offset = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 1));
231 Value *TypeIdValue = CI->getArgOperand(i: 2);
232 auto *TypeId = cast<MetadataAsValue>(Val: TypeIdValue)->getMetadata();
233
234 if (Offset) {
235 ScanVTableLoad(Caller: CI->getFunction(), TypeId, CallOffset: Offset->getZExtValue());
236 } else {
237 // type.checked.load with a non-constant offset, so assume every entry
238 // in every matching vtable is used.
239 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
240 VFESafeVTables.erase(Ptr: VTableInfo.first);
241 }
242 }
243 }
244 };
245
246 scan(TypeCheckedLoadFunc);
247 scan(TypeCheckedLoadRelativeFunc);
248}
249
250void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
251 if (!ClEnableVFE)
252 return;
253
254 // If the Virtual Function Elim module flag is present and set to zero, then
255 // the vcall_visibility metadata was inserted for another optimization (WPD)
256 // and we may not have type checked loads on all accesses to the vtable.
257 // Don't attempt VFE in that case.
258 auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
259 MD: M.getModuleFlag(Key: "Virtual Function Elim"));
260 if (!Val || Val->isZero())
261 return;
262
263 ScanVTables(M);
264
265 if (VFESafeVTables.empty())
266 return;
267
268 ScanTypeCheckedLoadIntrinsics(M);
269
270 LLVM_DEBUG(
271 dbgs() << "VFE safe vtables:\n";
272 for (auto *VTable : VFESafeVTables)
273 dbgs() << " " << VTable->getName() << "\n";
274 );
275}
276
277PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
278 bool Changed = false;
279
280 // The algorithm first computes the set L of global variables that are
281 // trivially live. Then it walks the initialization of these variables to
282 // compute the globals used to initialize them, which effectively builds a
283 // directed graph where nodes are global variables, and an edge from A to B
284 // means B is used to initialize A. Finally, it propagates the liveness
285 // information through the graph starting from the nodes in L. Nodes note
286 // marked as alive are discarded.
287
288 // Remove empty functions from the global ctors list.
289 Changed |= optimizeGlobalCtorsList(
290 M, ShouldRemove: [](uint32_t, Function *F) { return isEmptyFunction(F); });
291
292 // Collect the set of members for each comdat.
293 for (Function &F : M)
294 if (Comdat *C = F.getComdat())
295 ComdatMembers.insert(x: std::make_pair(x&: C, y: &F));
296 for (GlobalVariable &GV : M.globals())
297 if (Comdat *C = GV.getComdat())
298 ComdatMembers.insert(x: std::make_pair(x&: C, y: &GV));
299 for (GlobalAlias &GA : M.aliases())
300 if (Comdat *C = GA.getComdat())
301 ComdatMembers.insert(x: std::make_pair(x&: C, y: &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 GO.removeDeadConstantUsers();
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(GV&: GO);
316
317 UpdateGVDependencies(GV&: GO);
318 }
319
320 // Compute direct dependencies of aliases.
321 for (GlobalAlias &GA : M.aliases()) {
322 GA.removeDeadConstantUsers();
323 // Externally visible aliases are needed.
324 if (!GA.isDiscardableIfUnused())
325 MarkLive(GV&: GA);
326
327 UpdateGVDependencies(GV&: GA);
328 }
329
330 // Compute direct dependencies of ifuncs.
331 for (GlobalIFunc &GIF : M.ifuncs()) {
332 GIF.removeDeadConstantUsers();
333 // Externally visible ifuncs are needed.
334 if (!GIF.isDiscardableIfUnused())
335 MarkLive(GV&: GIF);
336
337 UpdateGVDependencies(GV&: 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(GV&: *GVD, Updates: &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(Ptr: &GV)) {
358 DeadGlobalVars.push_back(x: &GV); // Keep track of dead globals
359 if (GV.hasInitializer()) {
360 Constant *Init = GV.getInitializer();
361 GV.setInitializer(nullptr);
362 if (isSafeToDestroyConstant(C: 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(Ptr: &F)) {
371 DeadFunctions.push_back(x: &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(Ptr: &GA)) {
380 DeadAliases.push_back(x: &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(Ptr: &GIF)) {
388 DeadIFuncs.push_back(x: &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 GV->removeDeadConstantUsers();
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
409 // Detect vfuncs that are referenced as "relative pointers" which are used
410 // in Swift vtables, i.e. entries in the form of:
411 //
412 // i32 trunc (i64 sub (i64 ptrtoint @f, i64 ptrtoint ...)) to i32)
413 //
414 // In this case, replace the whole "sub" expression with constant 0 to
415 // avoid leaving a weird sub(0, symbol) expression behind.
416 replaceRelativePointerUsersWithZero(C: F);
417
418 F->replaceNonMetadataUsesWith(V: ConstantPointerNull::get(T: F->getType()));
419 }
420 EraseUnusedGlobalValue(F);
421 }
422
423 NumVariables += DeadGlobalVars.size();
424 for (GlobalVariable *GV : DeadGlobalVars)
425 EraseUnusedGlobalValue(GV);
426
427 NumAliases += DeadAliases.size();
428 for (GlobalAlias *GA : DeadAliases)
429 EraseUnusedGlobalValue(GA);
430
431 NumIFuncs += DeadIFuncs.size();
432 for (GlobalIFunc *GIF : DeadIFuncs)
433 EraseUnusedGlobalValue(GIF);
434
435 // Make sure that all memory is released
436 AliveGlobals.clear();
437 ConstantDependenciesCache.clear();
438 GVDependencies.clear();
439 ComdatMembers.clear();
440 TypeIdMap.clear();
441 VFESafeVTables.clear();
442
443 if (Changed)
444 return PreservedAnalyses::none();
445 return PreservedAnalyses::all();
446}
447
448void GlobalDCEPass::printPipeline(
449 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
450 static_cast<PassInfoMixin<GlobalDCEPass> *>(this)->printPipeline(
451 OS, MapClassName2PassName);
452 if (InLTOPostLink)
453 OS << "<vfe-linkage-unit-visibility>";
454}
455