LLVM 17.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 auto *LTOPostLinkMD =
124 cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
125 bool LTOPostLink =
126 LTOPostLinkMD && !cast<ConstantInt>(LTOPostLinkMD->getValue())->isZero();
127
128 for (GlobalVariable &GV : M.globals()) {
129 Types.clear();
130 GV.getMetadata(LLVMContext::MD_type, Types);
131 if (GV.isDeclaration() || Types.empty())
132 continue;
133
134 // Use the typeid metadata on the vtable to build a mapping from typeids to
135 // the list of (GV, offset) pairs which are the possible vtables for that
136 // typeid.
137 for (MDNode *Type : Types) {
138 Metadata *TypeID = Type->getOperand(1).get();
139
141 cast<ConstantInt>(
142 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
143 ->getZExtValue();
144
145 TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
146 }
147
148 // If the type corresponding to the vtable is private to this translation
149 // unit, we know that we can see all virtual functions which might use it,
150 // so VFE is safe.
151 if (auto GO = dyn_cast<GlobalObject>(&GV)) {
152 GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
154 (LTOPostLink &&
156 LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
157 VFESafeVTables.insert(&GV);
158 }
159 }
160 }
161}
162
163void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
164 uint64_t CallOffset) {
165 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
166 GlobalVariable *VTable = VTableInfo.first;
167 uint64_t VTableOffset = VTableInfo.second;
168
169 Constant *Ptr =
170 getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
171 *Caller->getParent(), VTable);
172 if (!Ptr) {
173 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
174 VFESafeVTables.erase(VTable);
175 continue;
176 }
177
178 auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
179 if (!Callee) {
180 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
181 VFESafeVTables.erase(VTable);
182 continue;
183 }
184
185 LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
186 << Callee->getName() << "\n");
187 GVDependencies[Caller].insert(Callee);
188 }
189}
190
191void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
192 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
193 Function *TypeCheckedLoadFunc =
194 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
195
196 if (!TypeCheckedLoadFunc)
197 return;
198
199 for (auto *U : TypeCheckedLoadFunc->users()) {
200 auto CI = dyn_cast<CallInst>(U);
201 if (!CI)
202 continue;
203
204 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
205 Value *TypeIdValue = CI->getArgOperand(2);
206 auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
207
208 if (Offset) {
209 ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
210 } else {
211 // type.checked.load with a non-constant offset, so assume every entry in
212 // every matching vtable is used.
213 for (const auto &VTableInfo : TypeIdMap[TypeId]) {
214 VFESafeVTables.erase(VTableInfo.first);
215 }
216 }
217 }
218}
219
220void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
221 if (!ClEnableVFE)
222 return;
223
224 // If the Virtual Function Elim module flag is present and set to zero, then
225 // the vcall_visibility metadata was inserted for another optimization (WPD)
226 // and we may not have type checked loads on all accesses to the vtable.
227 // Don't attempt VFE in that case.
228 auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
229 M.getModuleFlag("Virtual Function Elim"));
230 if (!Val || Val->isZero())
231 return;
232
233 ScanVTables(M);
234
235 if (VFESafeVTables.empty())
236 return;
237
238 ScanTypeCheckedLoadIntrinsics(M);
239
241 dbgs() << "VFE safe vtables:\n";
242 for (auto *VTable : VFESafeVTables)
243 dbgs() << " " << VTable->getName() << "\n";
244 );
245}
246
248 bool Changed = false;
249
250 // The algorithm first computes the set L of global variables that are
251 // trivially live. Then it walks the initialization of these variables to
252 // compute the globals used to initialize them, which effectively builds a
253 // directed graph where nodes are global variables, and an edge from A to B
254 // means B is used to initialize A. Finally, it propagates the liveness
255 // information through the graph starting from the nodes in L. Nodes note
256 // marked as alive are discarded.
257
258 // Remove empty functions from the global ctors list.
259 Changed |= optimizeGlobalCtorsList(
260 M, [](uint32_t, Function *F) { return isEmptyFunction(F); });
261
262 // Collect the set of members for each comdat.
263 for (Function &F : M)
264 if (Comdat *C = F.getComdat())
265 ComdatMembers.insert(std::make_pair(C, &F));
266 for (GlobalVariable &GV : M.globals())
267 if (Comdat *C = GV.getComdat())
268 ComdatMembers.insert(std::make_pair(C, &GV));
269 for (GlobalAlias &GA : M.aliases())
270 if (Comdat *C = GA.getComdat())
271 ComdatMembers.insert(std::make_pair(C, &GA));
272
273 // Add dependencies between virtual call sites and the virtual functions they
274 // might call, if we have that information.
275 AddVirtualFunctionDependencies(M);
276
277 // Loop over the module, adding globals which are obviously necessary.
278 for (GlobalObject &GO : M.global_objects()) {
279 GO.removeDeadConstantUsers();
280 // Functions with external linkage are needed if they have a body.
281 // Externally visible & appending globals are needed, if they have an
282 // initializer.
283 if (!GO.isDeclaration())
284 if (!GO.isDiscardableIfUnused())
285 MarkLive(GO);
286
287 UpdateGVDependencies(GO);
288 }
289
290 // Compute direct dependencies of aliases.
291 for (GlobalAlias &GA : M.aliases()) {
292 GA.removeDeadConstantUsers();
293 // Externally visible aliases are needed.
294 if (!GA.isDiscardableIfUnused())
295 MarkLive(GA);
296
297 UpdateGVDependencies(GA);
298 }
299
300 // Compute direct dependencies of ifuncs.
301 for (GlobalIFunc &GIF : M.ifuncs()) {
302 GIF.removeDeadConstantUsers();
303 // Externally visible ifuncs are needed.
304 if (!GIF.isDiscardableIfUnused())
305 MarkLive(GIF);
306
307 UpdateGVDependencies(GIF);
308 }
309
310 // Propagate liveness from collected Global Values through the computed
311 // dependencies.
312 SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
313 AliveGlobals.end()};
314 while (!NewLiveGVs.empty()) {
315 GlobalValue *LGV = NewLiveGVs.pop_back_val();
316 for (auto *GVD : GVDependencies[LGV])
317 MarkLive(*GVD, &NewLiveGVs);
318 }
319
320 // Now that all globals which are needed are in the AliveGlobals set, we loop
321 // through the program, deleting those which are not alive.
322 //
323
324 // The first pass is to drop initializers of global variables which are dead.
325 std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
326 for (GlobalVariable &GV : M.globals())
327 if (!AliveGlobals.count(&GV)) {
328 DeadGlobalVars.push_back(&GV); // Keep track of dead globals
329 if (GV.hasInitializer()) {
330 Constant *Init = GV.getInitializer();
331 GV.setInitializer(nullptr);
333 Init->destroyConstant();
334 }
335 }
336
337 // The second pass drops the bodies of functions which are dead...
338 std::vector<Function *> DeadFunctions;
339 for (Function &F : M)
340 if (!AliveGlobals.count(&F)) {
341 DeadFunctions.push_back(&F); // Keep track of dead globals
342 if (!F.isDeclaration())
343 F.deleteBody();
344 }
345
346 // The third pass drops targets of aliases which are dead...
347 std::vector<GlobalAlias*> DeadAliases;
348 for (GlobalAlias &GA : M.aliases())
349 if (!AliveGlobals.count(&GA)) {
350 DeadAliases.push_back(&GA);
351 GA.setAliasee(nullptr);
352 }
353
354 // The fourth pass drops targets of ifuncs which are dead...
355 std::vector<GlobalIFunc*> DeadIFuncs;
356 for (GlobalIFunc &GIF : M.ifuncs())
357 if (!AliveGlobals.count(&GIF)) {
358 DeadIFuncs.push_back(&GIF);
359 GIF.setResolver(nullptr);
360 }
361
362 // Now that all interferences have been dropped, delete the actual objects
363 // themselves.
364 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
366 GV->eraseFromParent();
367 Changed = true;
368 };
369
370 NumFunctions += DeadFunctions.size();
371 for (Function *F : DeadFunctions) {
372 if (!F->use_empty()) {
373 // Virtual functions might still be referenced by one or more vtables,
374 // but if we've proven them to be unused then it's safe to replace the
375 // virtual function pointers with null, allowing us to remove the
376 // function itself.
377 ++NumVFuncs;
378
379 // Detect vfuncs that are referenced as "relative pointers" which are used
380 // in Swift vtables, i.e. entries in the form of:
381 //
382 // i32 trunc (i64 sub (i64 ptrtoint @f, i64 ptrtoint ...)) to i32)
383 //
384 // In this case, replace the whole "sub" expression with constant 0 to
385 // avoid leaving a weird sub(0, symbol) expression behind.
387
388 F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
389 }
390 EraseUnusedGlobalValue(F);
391 }
392
393 NumVariables += DeadGlobalVars.size();
394 for (GlobalVariable *GV : DeadGlobalVars)
395 EraseUnusedGlobalValue(GV);
396
397 NumAliases += DeadAliases.size();
398 for (GlobalAlias *GA : DeadAliases)
399 EraseUnusedGlobalValue(GA);
400
401 NumIFuncs += DeadIFuncs.size();
402 for (GlobalIFunc *GIF : DeadIFuncs)
403 EraseUnusedGlobalValue(GIF);
404
405 // Make sure that all memory is released
406 AliveGlobals.clear();
407 ConstantDependenciesCache.clear();
408 GVDependencies.clear();
409 ComdatMembers.clear();
410 TypeIdMap.clear();
411 VFESafeVTables.clear();
412
413 if (Changed)
415 return PreservedAnalyses::all();
416}
amdgpu Simplify well known AMD library false FunctionCallee Callee
#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
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:167
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
Definition: Constants.cpp:1691
This is an important base class in LLVM.
Definition: Constant.h:41
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:708
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: GlobalDCE.cpp:247
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:273
const Comdat * getComdat() const
Definition: Globals.cpp:183
void eraseFromParent()
This method unlinks 'this' from the containing module and deletes it.
Definition: Globals.cpp:86
Metadata node.
Definition: Metadata.h:950
Root of the metadata hierarchy.
Definition: Metadata.h:61
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: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
iterator end() const
Definition: SmallPtrSet.h:408
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:365
iterator begin() const
Definition: SmallPtrSet.h:403
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
Definition: Metadata.cpp:1354
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
@ 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:992
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
void replaceRelativePointerUsersWithZero(Function *F)
Finds the same "relative pointer" pattern as described above, where the target is F,...
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:113
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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...