LLVM 20.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
19#include "llvm/ADT/Statistic.h"
23#include "llvm/IR/Module.h"
25#include "llvm/Transforms/IPO.h"
28
29using namespace llvm;
30
31#define DEBUG_TYPE "globaldce"
32
33static cl::opt<bool>
34 ClEnableVFE("enable-vfe", cl::Hidden, cl::init(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>(&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,
63 if (auto *I = dyn_cast<Instruction>(V)) {
64 Function *Parent = I->getParent()->getParent();
65 Deps.insert(Parent);
66 } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
67 Deps.insert(GV);
68 } else if (auto *CE = dyn_cast<Constant>(V)) {
69 // Avoid walking the whole tree of a big ConstantExprs multiple times.
70 auto Where = ConstantDependenciesCache.find(CE);
71 if (Where != ConstantDependenciesCache.end()) {
72 auto const &K = Where->second;
73 Deps.insert(K.begin(), K.end());
74 } else {
75 SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
76 for (User *CEUser : CE->users())
77 ComputeDependencies(CEUser, LocalDeps);
78 Deps.insert(LocalDeps.begin(), LocalDeps.end());
79 }
80 }
81}
82
83void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
85 for (User *User : GV.users())
86 ComputeDependencies(User, Deps);
87 Deps.erase(&GV); // Remove self-reference.
88 for (GlobalValue *GVU : Deps) {
89 // If this is a dep from a vtable to a virtual function, and we have
90 // complete information about all virtual call sites which could call
91 // though this vtable, then skip it, because the call site information will
92 // be more precise.
93 if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
94 LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
95 << GV.getName() << "\n");
96 continue;
97 }
98 GVDependencies[GVU].insert(&GV);
99 }
100}
101
102/// Mark Global value as Live
103void GlobalDCEPass::MarkLive(GlobalValue &GV,
105 auto const Ret = AliveGlobals.insert(&GV);
106 if (!Ret.second)
107 return;
108
109 if (Updates)
110 Updates->push_back(&GV);
111 if (Comdat *C = GV.getComdat()) {
112 for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
113 MarkLive(*CM.second, Updates); // Recursion depth is only two because only
114 // globals in the same comdat are visited.
115 }
116 }
117}
118
119void GlobalDCEPass::ScanVTables(Module &M) {
121 LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
122
123 for (GlobalVariable &GV : M.globals()) {
124 Types.clear();
125 GV.getMetadata(LLVMContext::MD_type, Types);
126 if (GV.isDeclaration() || Types.empty())
127 continue;
128
129 // Use the typeid metadata on the vtable to build a mapping from typeids to
130 // the list of (GV, offset) pairs which are the possible vtables for that
131 // typeid.
132 for (MDNode *Type : Types) {
133 Metadata *TypeID = Type->getOperand(1).get();
134
136 cast<ConstantInt>(
137 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
138 ->getZExtValue();
139
140 TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
141 }
142
143 // If the type corresponding to the vtable is private to this translation
144 // unit, we know that we can see all virtual functions which might use it,
145 // so VFE is safe.
146 if (auto GO = dyn_cast<GlobalObject>(&GV)) {
147 GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
149 (InLTOPostLink &&
151 LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
152 VFESafeVTables.insert(&GV);
153 }
154 }
155 }
156}
157
158void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
159 uint64_t CallOffset) {
160 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
161 GlobalVariable *VTable = VTableInfo.first;
162 uint64_t VTableOffset = VTableInfo.second;
163
164 Constant *Ptr =
165 getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
166 *Caller->getParent(), VTable);
167 if (!Ptr) {
168 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
169 VFESafeVTables.erase(VTable);
170 continue;
171 }
172
173 auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
174 if (!Callee) {
175 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
176 VFESafeVTables.erase(VTable);
177 continue;
178 }
179
180 LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
181 << Callee->getName() << "\n");
182 GVDependencies[Caller].insert(Callee);
183 }
184}
185
186void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
187 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
188 Function *TypeCheckedLoadFunc =
189 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
190 Function *TypeCheckedLoadRelativeFunc =
191 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load_relative));
192
193 auto scan = [&](Function *CheckedLoadFunc) {
194 if (!CheckedLoadFunc)
195 return;
196
197 for (auto *U : CheckedLoadFunc->users()) {
198 auto CI = dyn_cast<CallInst>(U);
199 if (!CI)
200 continue;
201
202 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
203 Value *TypeIdValue = CI->getArgOperand(2);
204 auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
205
206 if (Offset) {
207 ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
208 } else {
209 // type.checked.load with a non-constant offset, so assume every entry
210 // in every matching vtable is used.
211 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
212 VFESafeVTables.erase(VTableInfo.first);
213 }
214 }
215 }
216 };
217
218 scan(TypeCheckedLoadFunc);
219 scan(TypeCheckedLoadRelativeFunc);
220}
221
222void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
223 if (!ClEnableVFE)
224 return;
225
226 // If the Virtual Function Elim module flag is present and set to zero, then
227 // the vcall_visibility metadata was inserted for another optimization (WPD)
228 // and we may not have type checked loads on all accesses to the vtable.
229 // Don't attempt VFE in that case.
230 auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
231 M.getModuleFlag("Virtual Function Elim"));
232 if (!Val || Val->isZero())
233 return;
234
235 ScanVTables(M);
236
237 if (VFESafeVTables.empty())
238 return;
239
240 ScanTypeCheckedLoadIntrinsics(M);
241
243 dbgs() << "VFE safe vtables:\n";
244 for (auto *VTable : VFESafeVTables)
245 dbgs() << " " << VTable->getName() << "\n";
246 );
247}
248
250 bool Changed = false;
251
252 // The algorithm first computes the set L of global variables that are
253 // trivially live. Then it walks the initialization of these variables to
254 // compute the globals used to initialize them, which effectively builds a
255 // directed graph where nodes are global variables, and an edge from A to B
256 // means B is used to initialize A. Finally, it propagates the liveness
257 // information through the graph starting from the nodes in L. Nodes note
258 // marked as alive are discarded.
259
260 // Remove empty functions from the global ctors list.
261 Changed |= optimizeGlobalCtorsList(
262 M, [](uint32_t, Function *F) { return isEmptyFunction(F); });
263
264 // Collect the set of members for each comdat.
265 for (Function &F : M)
266 if (Comdat *C = F.getComdat())
267 ComdatMembers.insert(std::make_pair(C, &F));
268 for (GlobalVariable &GV : M.globals())
269 if (Comdat *C = GV.getComdat())
270 ComdatMembers.insert(std::make_pair(C, &GV));
271 for (GlobalAlias &GA : M.aliases())
272 if (Comdat *C = GA.getComdat())
273 ComdatMembers.insert(std::make_pair(C, &GA));
274
275 // Add dependencies between virtual call sites and the virtual functions they
276 // might call, if we have that information.
277 AddVirtualFunctionDependencies(M);
278
279 // Loop over the module, adding globals which are obviously necessary.
280 for (GlobalObject &GO : M.global_objects()) {
281 GO.removeDeadConstantUsers();
282 // Functions with external linkage are needed if they have a body.
283 // Externally visible & appending globals are needed, if they have an
284 // initializer.
285 if (!GO.isDeclaration())
286 if (!GO.isDiscardableIfUnused())
287 MarkLive(GO);
288
289 UpdateGVDependencies(GO);
290 }
291
292 // Compute direct dependencies of aliases.
293 for (GlobalAlias &GA : M.aliases()) {
294 GA.removeDeadConstantUsers();
295 // Externally visible aliases are needed.
296 if (!GA.isDiscardableIfUnused())
297 MarkLive(GA);
298
299 UpdateGVDependencies(GA);
300 }
301
302 // Compute direct dependencies of ifuncs.
303 for (GlobalIFunc &GIF : M.ifuncs()) {
304 GIF.removeDeadConstantUsers();
305 // Externally visible ifuncs are needed.
306 if (!GIF.isDiscardableIfUnused())
307 MarkLive(GIF);
308
309 UpdateGVDependencies(GIF);
310 }
311
312 // Propagate liveness from collected Global Values through the computed
313 // dependencies.
314 SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
315 AliveGlobals.end()};
316 while (!NewLiveGVs.empty()) {
317 GlobalValue *LGV = NewLiveGVs.pop_back_val();
318 for (auto *GVD : GVDependencies[LGV])
319 MarkLive(*GVD, &NewLiveGVs);
320 }
321
322 // Now that all globals which are needed are in the AliveGlobals set, we loop
323 // through the program, deleting those which are not alive.
324 //
325
326 // The first pass is to drop initializers of global variables which are dead.
327 std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
328 for (GlobalVariable &GV : M.globals())
329 if (!AliveGlobals.count(&GV)) {
330 DeadGlobalVars.push_back(&GV); // Keep track of dead globals
331 if (GV.hasInitializer()) {
332 Constant *Init = GV.getInitializer();
333 GV.setInitializer(nullptr);
335 Init->destroyConstant();
336 }
337 }
338
339 // The second pass drops the bodies of functions which are dead...
340 std::vector<Function *> DeadFunctions;
341 for (Function &F : M)
342 if (!AliveGlobals.count(&F)) {
343 DeadFunctions.push_back(&F); // Keep track of dead globals
344 if (!F.isDeclaration())
345 F.deleteBody();
346 }
347
348 // The third pass drops targets of aliases which are dead...
349 std::vector<GlobalAlias*> DeadAliases;
350 for (GlobalAlias &GA : M.aliases())
351 if (!AliveGlobals.count(&GA)) {
352 DeadAliases.push_back(&GA);
353 GA.setAliasee(nullptr);
354 }
355
356 // The fourth pass drops targets of ifuncs which are dead...
357 std::vector<GlobalIFunc*> DeadIFuncs;
358 for (GlobalIFunc &GIF : M.ifuncs())
359 if (!AliveGlobals.count(&GIF)) {
360 DeadIFuncs.push_back(&GIF);
361 GIF.setResolver(nullptr);
362 }
363
364 // Now that all interferences have been dropped, delete the actual objects
365 // themselves.
366 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
368 GV->eraseFromParent();
369 Changed = true;
370 };
371
372 NumFunctions += DeadFunctions.size();
373 for (Function *F : DeadFunctions) {
374 if (!F->use_empty()) {
375 // Virtual functions might still be referenced by one or more vtables,
376 // but if we've proven them to be unused then it's safe to replace the
377 // virtual function pointers with null, allowing us to remove the
378 // function itself.
379 ++NumVFuncs;
380
381 // Detect vfuncs that are referenced as "relative pointers" which are used
382 // in Swift vtables, i.e. entries in the form of:
383 //
384 // i32 trunc (i64 sub (i64 ptrtoint @f, i64 ptrtoint ...)) to i32)
385 //
386 // In this case, replace the whole "sub" expression with constant 0 to
387 // avoid leaving a weird sub(0, symbol) expression behind.
389
390 F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
391 }
392 EraseUnusedGlobalValue(F);
393 }
394
395 NumVariables += DeadGlobalVars.size();
396 for (GlobalVariable *GV : DeadGlobalVars)
397 EraseUnusedGlobalValue(GV);
398
399 NumAliases += DeadAliases.size();
400 for (GlobalAlias *GA : DeadAliases)
401 EraseUnusedGlobalValue(GA);
402
403 NumIFuncs += DeadIFuncs.size();
404 for (GlobalIFunc *GIF : DeadIFuncs)
405 EraseUnusedGlobalValue(GIF);
406
407 // Make sure that all memory is released
408 AliveGlobals.clear();
409 ConstantDependenciesCache.clear();
410 GVDependencies.clear();
411 ComdatMembers.clear();
412 TypeIdMap.clear();
413 VFESafeVTables.clear();
414
415 if (Changed)
417 return PreservedAnalyses::all();
418}
419
421 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
422 static_cast<PassInfoMixin<GlobalDCEPass> *>(this)->printPipeline(
423 OS, MapClassName2PassName);
424 if (InLTOPostLink)
425 OS << "<vfe-linkage-unit-visibility>";
426}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool isEmptyFunction(Function *F)
Returns true if F is effectively empty.
Definition: GlobalDCE.cpp:44
static cl::opt< bool > ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::desc("Enable virtual function elimination"))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
ModuleAnalysisManager MAM
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1800
This is an important base class in LLVM.
Definition: Constant.h:42
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:723
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: GlobalDCE.cpp:420
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: GlobalDCE.cpp:249
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:290
const Comdat * getComdat() const
Definition: Globals.cpp:193
void eraseFromParent()
This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:91
Metadata node.
Definition: Metadata.h:1069
Root of the metadata hierarchy.
Definition: Metadata.h:62
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:346
bool erase(PtrType Ptr)
Remove pointer from the set.
Definition: SmallPtrSet.h:384
iterator end() const
Definition: SmallPtrSet.h:460
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:367
iterator begin() const
Definition: SmallPtrSet.h:455
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
TypeID
Definitions of all of the base types for the Type system.
Definition: Type.h:54
LLVM Value Representation.
Definition: Value.h:74
iterator_range< user_iterator > users()
Definition: Value.h:421
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
Definition: Value.h:565
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:1096
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
bool optimizeGlobalCtorsList(Module &M, function_ref< bool(uint32_t, Function *)> ShouldRemove)
Call "ShouldRemove" for every entry in M's global_ctor list and remove the entries for which it retur...
Definition: CtorUtils.cpp:110
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void replaceRelativePointerUsersWithZero(Constant *C)
Finds the same "relative pointer" pattern as described above, where the target is C,...
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)
Processes a Constant recursively looking into elements of arrays, structs and expressions to find a t...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69