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

source code of llvm/lib/Transforms/IPO/GlobalDCE.cpp