106f32e7eSjoerg //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This transform is designed to eliminate unreachable internal globals from the
1006f32e7eSjoerg // program. It uses an aggressive algorithm, searching out globals that are
1106f32e7eSjoerg // known to be alive. After it finds all of the globals which are needed, it
1206f32e7eSjoerg // deletes whatever is left over. This allows it to delete recursive chunks of
1306f32e7eSjoerg // the program which are unreachable.
1406f32e7eSjoerg //
1506f32e7eSjoerg //===----------------------------------------------------------------------===//
1606f32e7eSjoerg
1706f32e7eSjoerg #include "llvm/Transforms/IPO/GlobalDCE.h"
1806f32e7eSjoerg #include "llvm/ADT/SmallPtrSet.h"
1906f32e7eSjoerg #include "llvm/ADT/Statistic.h"
2006f32e7eSjoerg #include "llvm/Analysis/TypeMetadataUtils.h"
2106f32e7eSjoerg #include "llvm/IR/Instructions.h"
2206f32e7eSjoerg #include "llvm/IR/IntrinsicInst.h"
2306f32e7eSjoerg #include "llvm/IR/Module.h"
2406f32e7eSjoerg #include "llvm/IR/Operator.h"
25*da58b97aSjoerg #include "llvm/InitializePasses.h"
2606f32e7eSjoerg #include "llvm/Pass.h"
27*da58b97aSjoerg #include "llvm/Support/CommandLine.h"
2806f32e7eSjoerg #include "llvm/Transforms/IPO.h"
2906f32e7eSjoerg #include "llvm/Transforms/Utils/CtorUtils.h"
3006f32e7eSjoerg #include "llvm/Transforms/Utils/GlobalStatus.h"
3106f32e7eSjoerg
3206f32e7eSjoerg using namespace llvm;
3306f32e7eSjoerg
3406f32e7eSjoerg #define DEBUG_TYPE "globaldce"
3506f32e7eSjoerg
3606f32e7eSjoerg static cl::opt<bool>
3706f32e7eSjoerg ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
3806f32e7eSjoerg cl::desc("Enable virtual function elimination"));
3906f32e7eSjoerg
4006f32e7eSjoerg STATISTIC(NumAliases , "Number of global aliases removed");
4106f32e7eSjoerg STATISTIC(NumFunctions, "Number of functions removed");
4206f32e7eSjoerg STATISTIC(NumIFuncs, "Number of indirect functions removed");
4306f32e7eSjoerg STATISTIC(NumVariables, "Number of global variables removed");
4406f32e7eSjoerg STATISTIC(NumVFuncs, "Number of virtual functions removed");
4506f32e7eSjoerg
4606f32e7eSjoerg namespace {
4706f32e7eSjoerg class GlobalDCELegacyPass : public ModulePass {
4806f32e7eSjoerg public:
4906f32e7eSjoerg static char ID; // Pass identification, replacement for typeid
GlobalDCELegacyPass()5006f32e7eSjoerg GlobalDCELegacyPass() : ModulePass(ID) {
5106f32e7eSjoerg initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
5206f32e7eSjoerg }
5306f32e7eSjoerg
5406f32e7eSjoerg // run - Do the GlobalDCE pass on the specified module, optionally updating
5506f32e7eSjoerg // the specified callgraph to reflect the changes.
5606f32e7eSjoerg //
runOnModule(Module & M)5706f32e7eSjoerg bool runOnModule(Module &M) override {
5806f32e7eSjoerg if (skipModule(M))
5906f32e7eSjoerg return false;
6006f32e7eSjoerg
6106f32e7eSjoerg // We need a minimally functional dummy module analysis manager. It needs
6206f32e7eSjoerg // to at least know about the possibility of proxying a function analysis
6306f32e7eSjoerg // manager.
6406f32e7eSjoerg FunctionAnalysisManager DummyFAM;
6506f32e7eSjoerg ModuleAnalysisManager DummyMAM;
6606f32e7eSjoerg DummyMAM.registerPass(
6706f32e7eSjoerg [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
6806f32e7eSjoerg
6906f32e7eSjoerg auto PA = Impl.run(M, DummyMAM);
7006f32e7eSjoerg return !PA.areAllPreserved();
7106f32e7eSjoerg }
7206f32e7eSjoerg
7306f32e7eSjoerg private:
7406f32e7eSjoerg GlobalDCEPass Impl;
7506f32e7eSjoerg };
7606f32e7eSjoerg }
7706f32e7eSjoerg
7806f32e7eSjoerg char GlobalDCELegacyPass::ID = 0;
7906f32e7eSjoerg INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
8006f32e7eSjoerg "Dead Global Elimination", false, false)
8106f32e7eSjoerg
8206f32e7eSjoerg // Public interface to the GlobalDCEPass.
createGlobalDCEPass()8306f32e7eSjoerg ModulePass *llvm::createGlobalDCEPass() {
8406f32e7eSjoerg return new GlobalDCELegacyPass();
8506f32e7eSjoerg }
8606f32e7eSjoerg
8706f32e7eSjoerg /// Returns true if F is effectively empty.
isEmptyFunction(Function * F)8806f32e7eSjoerg static bool isEmptyFunction(Function *F) {
8906f32e7eSjoerg BasicBlock &Entry = F->getEntryBlock();
9006f32e7eSjoerg for (auto &I : Entry) {
9106f32e7eSjoerg if (isa<DbgInfoIntrinsic>(I))
9206f32e7eSjoerg continue;
9306f32e7eSjoerg if (auto *RI = dyn_cast<ReturnInst>(&I))
9406f32e7eSjoerg return !RI->getReturnValue();
9506f32e7eSjoerg break;
9606f32e7eSjoerg }
9706f32e7eSjoerg return false;
9806f32e7eSjoerg }
9906f32e7eSjoerg
10006f32e7eSjoerg /// Compute the set of GlobalValue that depends from V.
10106f32e7eSjoerg /// The recursion stops as soon as a GlobalValue is met.
ComputeDependencies(Value * V,SmallPtrSetImpl<GlobalValue * > & Deps)10206f32e7eSjoerg void GlobalDCEPass::ComputeDependencies(Value *V,
10306f32e7eSjoerg SmallPtrSetImpl<GlobalValue *> &Deps) {
10406f32e7eSjoerg if (auto *I = dyn_cast<Instruction>(V)) {
10506f32e7eSjoerg Function *Parent = I->getParent()->getParent();
10606f32e7eSjoerg Deps.insert(Parent);
10706f32e7eSjoerg } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
10806f32e7eSjoerg Deps.insert(GV);
10906f32e7eSjoerg } else if (auto *CE = dyn_cast<Constant>(V)) {
11006f32e7eSjoerg // Avoid walking the whole tree of a big ConstantExprs multiple times.
11106f32e7eSjoerg auto Where = ConstantDependenciesCache.find(CE);
11206f32e7eSjoerg if (Where != ConstantDependenciesCache.end()) {
11306f32e7eSjoerg auto const &K = Where->second;
11406f32e7eSjoerg Deps.insert(K.begin(), K.end());
11506f32e7eSjoerg } else {
11606f32e7eSjoerg SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
11706f32e7eSjoerg for (User *CEUser : CE->users())
11806f32e7eSjoerg ComputeDependencies(CEUser, LocalDeps);
11906f32e7eSjoerg Deps.insert(LocalDeps.begin(), LocalDeps.end());
12006f32e7eSjoerg }
12106f32e7eSjoerg }
12206f32e7eSjoerg }
12306f32e7eSjoerg
UpdateGVDependencies(GlobalValue & GV)12406f32e7eSjoerg void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
12506f32e7eSjoerg SmallPtrSet<GlobalValue *, 8> Deps;
12606f32e7eSjoerg for (User *User : GV.users())
12706f32e7eSjoerg ComputeDependencies(User, Deps);
12806f32e7eSjoerg Deps.erase(&GV); // Remove self-reference.
12906f32e7eSjoerg for (GlobalValue *GVU : Deps) {
13006f32e7eSjoerg // If this is a dep from a vtable to a virtual function, and we have
13106f32e7eSjoerg // complete information about all virtual call sites which could call
13206f32e7eSjoerg // though this vtable, then skip it, because the call site information will
13306f32e7eSjoerg // be more precise.
13406f32e7eSjoerg if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
13506f32e7eSjoerg LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
13606f32e7eSjoerg << GV.getName() << "\n");
13706f32e7eSjoerg continue;
13806f32e7eSjoerg }
13906f32e7eSjoerg GVDependencies[GVU].insert(&GV);
14006f32e7eSjoerg }
14106f32e7eSjoerg }
14206f32e7eSjoerg
14306f32e7eSjoerg /// Mark Global value as Live
MarkLive(GlobalValue & GV,SmallVectorImpl<GlobalValue * > * Updates)14406f32e7eSjoerg void GlobalDCEPass::MarkLive(GlobalValue &GV,
14506f32e7eSjoerg SmallVectorImpl<GlobalValue *> *Updates) {
14606f32e7eSjoerg auto const Ret = AliveGlobals.insert(&GV);
14706f32e7eSjoerg if (!Ret.second)
14806f32e7eSjoerg return;
14906f32e7eSjoerg
15006f32e7eSjoerg if (Updates)
15106f32e7eSjoerg Updates->push_back(&GV);
15206f32e7eSjoerg if (Comdat *C = GV.getComdat()) {
15306f32e7eSjoerg for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
15406f32e7eSjoerg MarkLive(*CM.second, Updates); // Recursion depth is only two because only
15506f32e7eSjoerg // globals in the same comdat are visited.
15606f32e7eSjoerg }
15706f32e7eSjoerg }
15806f32e7eSjoerg }
15906f32e7eSjoerg
ScanVTables(Module & M)16006f32e7eSjoerg void GlobalDCEPass::ScanVTables(Module &M) {
16106f32e7eSjoerg SmallVector<MDNode *, 2> Types;
16206f32e7eSjoerg LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
16306f32e7eSjoerg
16406f32e7eSjoerg auto *LTOPostLinkMD =
16506f32e7eSjoerg cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
16606f32e7eSjoerg bool LTOPostLink =
16706f32e7eSjoerg LTOPostLinkMD &&
16806f32e7eSjoerg (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0);
16906f32e7eSjoerg
17006f32e7eSjoerg for (GlobalVariable &GV : M.globals()) {
17106f32e7eSjoerg Types.clear();
17206f32e7eSjoerg GV.getMetadata(LLVMContext::MD_type, Types);
17306f32e7eSjoerg if (GV.isDeclaration() || Types.empty())
17406f32e7eSjoerg continue;
17506f32e7eSjoerg
17606f32e7eSjoerg // Use the typeid metadata on the vtable to build a mapping from typeids to
17706f32e7eSjoerg // the list of (GV, offset) pairs which are the possible vtables for that
17806f32e7eSjoerg // typeid.
17906f32e7eSjoerg for (MDNode *Type : Types) {
18006f32e7eSjoerg Metadata *TypeID = Type->getOperand(1).get();
18106f32e7eSjoerg
18206f32e7eSjoerg uint64_t Offset =
18306f32e7eSjoerg cast<ConstantInt>(
18406f32e7eSjoerg cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
18506f32e7eSjoerg ->getZExtValue();
18606f32e7eSjoerg
18706f32e7eSjoerg TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
18806f32e7eSjoerg }
18906f32e7eSjoerg
19006f32e7eSjoerg // If the type corresponding to the vtable is private to this translation
19106f32e7eSjoerg // unit, we know that we can see all virtual functions which might use it,
19206f32e7eSjoerg // so VFE is safe.
19306f32e7eSjoerg if (auto GO = dyn_cast<GlobalObject>(&GV)) {
19406f32e7eSjoerg GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
19506f32e7eSjoerg if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
19606f32e7eSjoerg (LTOPostLink &&
19706f32e7eSjoerg TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
19806f32e7eSjoerg LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
19906f32e7eSjoerg VFESafeVTables.insert(&GV);
20006f32e7eSjoerg }
20106f32e7eSjoerg }
20206f32e7eSjoerg }
20306f32e7eSjoerg }
20406f32e7eSjoerg
ScanVTableLoad(Function * Caller,Metadata * TypeId,uint64_t CallOffset)20506f32e7eSjoerg void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
20606f32e7eSjoerg uint64_t CallOffset) {
20706f32e7eSjoerg for (auto &VTableInfo : TypeIdMap[TypeId]) {
20806f32e7eSjoerg GlobalVariable *VTable = VTableInfo.first;
20906f32e7eSjoerg uint64_t VTableOffset = VTableInfo.second;
21006f32e7eSjoerg
21106f32e7eSjoerg Constant *Ptr =
21206f32e7eSjoerg getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
21306f32e7eSjoerg *Caller->getParent());
21406f32e7eSjoerg if (!Ptr) {
21506f32e7eSjoerg LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
21606f32e7eSjoerg VFESafeVTables.erase(VTable);
21706f32e7eSjoerg return;
21806f32e7eSjoerg }
21906f32e7eSjoerg
22006f32e7eSjoerg auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
22106f32e7eSjoerg if (!Callee) {
22206f32e7eSjoerg LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
22306f32e7eSjoerg VFESafeVTables.erase(VTable);
22406f32e7eSjoerg return;
22506f32e7eSjoerg }
22606f32e7eSjoerg
22706f32e7eSjoerg LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
22806f32e7eSjoerg << Callee->getName() << "\n");
22906f32e7eSjoerg GVDependencies[Caller].insert(Callee);
23006f32e7eSjoerg }
23106f32e7eSjoerg }
23206f32e7eSjoerg
ScanTypeCheckedLoadIntrinsics(Module & M)23306f32e7eSjoerg void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
23406f32e7eSjoerg LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
23506f32e7eSjoerg Function *TypeCheckedLoadFunc =
23606f32e7eSjoerg M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
23706f32e7eSjoerg
23806f32e7eSjoerg if (!TypeCheckedLoadFunc)
23906f32e7eSjoerg return;
24006f32e7eSjoerg
24106f32e7eSjoerg for (auto U : TypeCheckedLoadFunc->users()) {
24206f32e7eSjoerg auto CI = dyn_cast<CallInst>(U);
24306f32e7eSjoerg if (!CI)
24406f32e7eSjoerg continue;
24506f32e7eSjoerg
24606f32e7eSjoerg auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
24706f32e7eSjoerg Value *TypeIdValue = CI->getArgOperand(2);
24806f32e7eSjoerg auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
24906f32e7eSjoerg
25006f32e7eSjoerg if (Offset) {
25106f32e7eSjoerg ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
25206f32e7eSjoerg } else {
25306f32e7eSjoerg // type.checked.load with a non-constant offset, so assume every entry in
25406f32e7eSjoerg // every matching vtable is used.
25506f32e7eSjoerg for (auto &VTableInfo : TypeIdMap[TypeId]) {
25606f32e7eSjoerg VFESafeVTables.erase(VTableInfo.first);
25706f32e7eSjoerg }
25806f32e7eSjoerg }
25906f32e7eSjoerg }
26006f32e7eSjoerg }
26106f32e7eSjoerg
AddVirtualFunctionDependencies(Module & M)26206f32e7eSjoerg void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
26306f32e7eSjoerg if (!ClEnableVFE)
26406f32e7eSjoerg return;
26506f32e7eSjoerg
266*da58b97aSjoerg // If the Virtual Function Elim module flag is present and set to zero, then
267*da58b97aSjoerg // the vcall_visibility metadata was inserted for another optimization (WPD)
268*da58b97aSjoerg // and we may not have type checked loads on all accesses to the vtable.
269*da58b97aSjoerg // Don't attempt VFE in that case.
270*da58b97aSjoerg auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
271*da58b97aSjoerg M.getModuleFlag("Virtual Function Elim"));
272*da58b97aSjoerg if (!Val || Val->getZExtValue() == 0)
273*da58b97aSjoerg return;
274*da58b97aSjoerg
27506f32e7eSjoerg ScanVTables(M);
27606f32e7eSjoerg
27706f32e7eSjoerg if (VFESafeVTables.empty())
27806f32e7eSjoerg return;
27906f32e7eSjoerg
28006f32e7eSjoerg ScanTypeCheckedLoadIntrinsics(M);
28106f32e7eSjoerg
28206f32e7eSjoerg LLVM_DEBUG(
28306f32e7eSjoerg dbgs() << "VFE safe vtables:\n";
28406f32e7eSjoerg for (auto *VTable : VFESafeVTables)
28506f32e7eSjoerg dbgs() << " " << VTable->getName() << "\n";
28606f32e7eSjoerg );
28706f32e7eSjoerg }
28806f32e7eSjoerg
run(Module & M,ModuleAnalysisManager & MAM)28906f32e7eSjoerg PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
29006f32e7eSjoerg bool Changed = false;
29106f32e7eSjoerg
29206f32e7eSjoerg // The algorithm first computes the set L of global variables that are
29306f32e7eSjoerg // trivially live. Then it walks the initialization of these variables to
29406f32e7eSjoerg // compute the globals used to initialize them, which effectively builds a
29506f32e7eSjoerg // directed graph where nodes are global variables, and an edge from A to B
29606f32e7eSjoerg // means B is used to initialize A. Finally, it propagates the liveness
29706f32e7eSjoerg // information through the graph starting from the nodes in L. Nodes note
29806f32e7eSjoerg // marked as alive are discarded.
29906f32e7eSjoerg
30006f32e7eSjoerg // Remove empty functions from the global ctors list.
30106f32e7eSjoerg Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
30206f32e7eSjoerg
30306f32e7eSjoerg // Collect the set of members for each comdat.
30406f32e7eSjoerg for (Function &F : M)
30506f32e7eSjoerg if (Comdat *C = F.getComdat())
30606f32e7eSjoerg ComdatMembers.insert(std::make_pair(C, &F));
30706f32e7eSjoerg for (GlobalVariable &GV : M.globals())
30806f32e7eSjoerg if (Comdat *C = GV.getComdat())
30906f32e7eSjoerg ComdatMembers.insert(std::make_pair(C, &GV));
31006f32e7eSjoerg for (GlobalAlias &GA : M.aliases())
31106f32e7eSjoerg if (Comdat *C = GA.getComdat())
31206f32e7eSjoerg ComdatMembers.insert(std::make_pair(C, &GA));
31306f32e7eSjoerg
31406f32e7eSjoerg // Add dependencies between virtual call sites and the virtual functions they
31506f32e7eSjoerg // might call, if we have that information.
31606f32e7eSjoerg AddVirtualFunctionDependencies(M);
31706f32e7eSjoerg
31806f32e7eSjoerg // Loop over the module, adding globals which are obviously necessary.
31906f32e7eSjoerg for (GlobalObject &GO : M.global_objects()) {
32006f32e7eSjoerg Changed |= RemoveUnusedGlobalValue(GO);
32106f32e7eSjoerg // Functions with external linkage are needed if they have a body.
32206f32e7eSjoerg // Externally visible & appending globals are needed, if they have an
32306f32e7eSjoerg // initializer.
32406f32e7eSjoerg if (!GO.isDeclaration())
32506f32e7eSjoerg if (!GO.isDiscardableIfUnused())
32606f32e7eSjoerg MarkLive(GO);
32706f32e7eSjoerg
32806f32e7eSjoerg UpdateGVDependencies(GO);
32906f32e7eSjoerg }
33006f32e7eSjoerg
33106f32e7eSjoerg // Compute direct dependencies of aliases.
33206f32e7eSjoerg for (GlobalAlias &GA : M.aliases()) {
33306f32e7eSjoerg Changed |= RemoveUnusedGlobalValue(GA);
33406f32e7eSjoerg // Externally visible aliases are needed.
33506f32e7eSjoerg if (!GA.isDiscardableIfUnused())
33606f32e7eSjoerg MarkLive(GA);
33706f32e7eSjoerg
33806f32e7eSjoerg UpdateGVDependencies(GA);
33906f32e7eSjoerg }
34006f32e7eSjoerg
34106f32e7eSjoerg // Compute direct dependencies of ifuncs.
34206f32e7eSjoerg for (GlobalIFunc &GIF : M.ifuncs()) {
34306f32e7eSjoerg Changed |= RemoveUnusedGlobalValue(GIF);
34406f32e7eSjoerg // Externally visible ifuncs are needed.
34506f32e7eSjoerg if (!GIF.isDiscardableIfUnused())
34606f32e7eSjoerg MarkLive(GIF);
34706f32e7eSjoerg
34806f32e7eSjoerg UpdateGVDependencies(GIF);
34906f32e7eSjoerg }
35006f32e7eSjoerg
35106f32e7eSjoerg // Propagate liveness from collected Global Values through the computed
35206f32e7eSjoerg // dependencies.
35306f32e7eSjoerg SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
35406f32e7eSjoerg AliveGlobals.end()};
35506f32e7eSjoerg while (!NewLiveGVs.empty()) {
35606f32e7eSjoerg GlobalValue *LGV = NewLiveGVs.pop_back_val();
35706f32e7eSjoerg for (auto *GVD : GVDependencies[LGV])
35806f32e7eSjoerg MarkLive(*GVD, &NewLiveGVs);
35906f32e7eSjoerg }
36006f32e7eSjoerg
36106f32e7eSjoerg // Now that all globals which are needed are in the AliveGlobals set, we loop
36206f32e7eSjoerg // through the program, deleting those which are not alive.
36306f32e7eSjoerg //
36406f32e7eSjoerg
36506f32e7eSjoerg // The first pass is to drop initializers of global variables which are dead.
36606f32e7eSjoerg std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
36706f32e7eSjoerg for (GlobalVariable &GV : M.globals())
36806f32e7eSjoerg if (!AliveGlobals.count(&GV)) {
36906f32e7eSjoerg DeadGlobalVars.push_back(&GV); // Keep track of dead globals
37006f32e7eSjoerg if (GV.hasInitializer()) {
37106f32e7eSjoerg Constant *Init = GV.getInitializer();
37206f32e7eSjoerg GV.setInitializer(nullptr);
37306f32e7eSjoerg if (isSafeToDestroyConstant(Init))
37406f32e7eSjoerg Init->destroyConstant();
37506f32e7eSjoerg }
37606f32e7eSjoerg }
37706f32e7eSjoerg
37806f32e7eSjoerg // The second pass drops the bodies of functions which are dead...
37906f32e7eSjoerg std::vector<Function *> DeadFunctions;
38006f32e7eSjoerg for (Function &F : M)
38106f32e7eSjoerg if (!AliveGlobals.count(&F)) {
38206f32e7eSjoerg DeadFunctions.push_back(&F); // Keep track of dead globals
38306f32e7eSjoerg if (!F.isDeclaration())
38406f32e7eSjoerg F.deleteBody();
38506f32e7eSjoerg }
38606f32e7eSjoerg
38706f32e7eSjoerg // The third pass drops targets of aliases which are dead...
38806f32e7eSjoerg std::vector<GlobalAlias*> DeadAliases;
38906f32e7eSjoerg for (GlobalAlias &GA : M.aliases())
39006f32e7eSjoerg if (!AliveGlobals.count(&GA)) {
39106f32e7eSjoerg DeadAliases.push_back(&GA);
39206f32e7eSjoerg GA.setAliasee(nullptr);
39306f32e7eSjoerg }
39406f32e7eSjoerg
39506f32e7eSjoerg // The fourth pass drops targets of ifuncs which are dead...
39606f32e7eSjoerg std::vector<GlobalIFunc*> DeadIFuncs;
39706f32e7eSjoerg for (GlobalIFunc &GIF : M.ifuncs())
39806f32e7eSjoerg if (!AliveGlobals.count(&GIF)) {
39906f32e7eSjoerg DeadIFuncs.push_back(&GIF);
40006f32e7eSjoerg GIF.setResolver(nullptr);
40106f32e7eSjoerg }
40206f32e7eSjoerg
40306f32e7eSjoerg // Now that all interferences have been dropped, delete the actual objects
40406f32e7eSjoerg // themselves.
40506f32e7eSjoerg auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
40606f32e7eSjoerg RemoveUnusedGlobalValue(*GV);
40706f32e7eSjoerg GV->eraseFromParent();
40806f32e7eSjoerg Changed = true;
40906f32e7eSjoerg };
41006f32e7eSjoerg
41106f32e7eSjoerg NumFunctions += DeadFunctions.size();
41206f32e7eSjoerg for (Function *F : DeadFunctions) {
41306f32e7eSjoerg if (!F->use_empty()) {
41406f32e7eSjoerg // Virtual functions might still be referenced by one or more vtables,
41506f32e7eSjoerg // but if we've proven them to be unused then it's safe to replace the
41606f32e7eSjoerg // virtual function pointers with null, allowing us to remove the
41706f32e7eSjoerg // function itself.
41806f32e7eSjoerg ++NumVFuncs;
41906f32e7eSjoerg F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
42006f32e7eSjoerg }
42106f32e7eSjoerg EraseUnusedGlobalValue(F);
42206f32e7eSjoerg }
42306f32e7eSjoerg
42406f32e7eSjoerg NumVariables += DeadGlobalVars.size();
42506f32e7eSjoerg for (GlobalVariable *GV : DeadGlobalVars)
42606f32e7eSjoerg EraseUnusedGlobalValue(GV);
42706f32e7eSjoerg
42806f32e7eSjoerg NumAliases += DeadAliases.size();
42906f32e7eSjoerg for (GlobalAlias *GA : DeadAliases)
43006f32e7eSjoerg EraseUnusedGlobalValue(GA);
43106f32e7eSjoerg
43206f32e7eSjoerg NumIFuncs += DeadIFuncs.size();
43306f32e7eSjoerg for (GlobalIFunc *GIF : DeadIFuncs)
43406f32e7eSjoerg EraseUnusedGlobalValue(GIF);
43506f32e7eSjoerg
43606f32e7eSjoerg // Make sure that all memory is released
43706f32e7eSjoerg AliveGlobals.clear();
43806f32e7eSjoerg ConstantDependenciesCache.clear();
43906f32e7eSjoerg GVDependencies.clear();
44006f32e7eSjoerg ComdatMembers.clear();
44106f32e7eSjoerg TypeIdMap.clear();
44206f32e7eSjoerg VFESafeVTables.clear();
44306f32e7eSjoerg
44406f32e7eSjoerg if (Changed)
44506f32e7eSjoerg return PreservedAnalyses::none();
44606f32e7eSjoerg return PreservedAnalyses::all();
44706f32e7eSjoerg }
44806f32e7eSjoerg
44906f32e7eSjoerg // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
45006f32e7eSjoerg // GlobalValue, looking for the constant pointer ref that may be pointing to it.
45106f32e7eSjoerg // If found, check to see if the constant pointer ref is safe to destroy, and if
45206f32e7eSjoerg // so, nuke it. This will reduce the reference count on the global value, which
45306f32e7eSjoerg // might make it deader.
45406f32e7eSjoerg //
RemoveUnusedGlobalValue(GlobalValue & GV)45506f32e7eSjoerg bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
45606f32e7eSjoerg if (GV.use_empty())
45706f32e7eSjoerg return false;
45806f32e7eSjoerg GV.removeDeadConstantUsers();
45906f32e7eSjoerg return GV.use_empty();
46006f32e7eSjoerg }
461