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