1193323Sed//===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// 2193323Sed// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6193323Sed// 7193323Sed//===----------------------------------------------------------------------===// 8193323Sed// 9193323Sed// This transform is designed to eliminate unreachable internal globals from the 10193323Sed// program. It uses an aggressive algorithm, searching out globals that are 11193323Sed// known to be alive. After it finds all of the globals which are needed, it 12193323Sed// deletes whatever is left over. This allows it to delete recursive chunks of 13193323Sed// the program which are unreachable. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17309124Sdim#include "llvm/Transforms/IPO/GlobalDCE.h" 18198892Srdivacky#include "llvm/ADT/SmallPtrSet.h" 19193323Sed#include "llvm/ADT/Statistic.h" 20360784Sdim#include "llvm/Analysis/TypeMetadataUtils.h" 21276479Sdim#include "llvm/IR/Instructions.h" 22344779Sdim#include "llvm/IR/IntrinsicInst.h" 23249423Sdim#include "llvm/IR/Module.h" 24360784Sdim#include "llvm/IR/Operator.h" 25360784Sdim#include "llvm/InitializePasses.h" 26309124Sdim#include "llvm/Pass.h" 27360784Sdim#include "llvm/Support/CommandLine.h" 28309124Sdim#include "llvm/Transforms/IPO.h" 29276479Sdim#include "llvm/Transforms/Utils/CtorUtils.h" 30280031Sdim#include "llvm/Transforms/Utils/GlobalStatus.h" 31321369Sdim 32193323Sedusing namespace llvm; 33193323Sed 34276479Sdim#define DEBUG_TYPE "globaldce" 35276479Sdim 36360784Sdimstatic cl::opt<bool> 37360784Sdim ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore, 38360784Sdim cl::desc("Enable virtual function elimination")); 39360784Sdim 40193323SedSTATISTIC(NumAliases , "Number of global aliases removed"); 41193323SedSTATISTIC(NumFunctions, "Number of functions removed"); 42309124SdimSTATISTIC(NumIFuncs, "Number of indirect functions removed"); 43193323SedSTATISTIC(NumVariables, "Number of global variables removed"); 44360784SdimSTATISTIC(NumVFuncs, "Number of virtual functions removed"); 45193323Sed 46193323Sednamespace { 47309124Sdim class GlobalDCELegacyPass : public ModulePass { 48309124Sdim public: 49193323Sed static char ID; // Pass identification, replacement for typeid 50309124Sdim GlobalDCELegacyPass() : ModulePass(ID) { 51309124Sdim initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry()); 52218893Sdim } 53193323Sed 54193323Sed // run - Do the GlobalDCE pass on the specified module, optionally updating 55193323Sed // the specified callgraph to reflect the changes. 56193323Sed // 57309124Sdim bool runOnModule(Module &M) override { 58309124Sdim if (skipModule(M)) 59309124Sdim return false; 60193323Sed 61321369Sdim // We need a minimally functional dummy module analysis manager. It needs 62321369Sdim // to at least know about the possibility of proxying a function analysis 63321369Sdim // manager. 64321369Sdim FunctionAnalysisManager DummyFAM; 65309124Sdim ModuleAnalysisManager DummyMAM; 66321369Sdim DummyMAM.registerPass( 67321369Sdim [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); }); 68321369Sdim 69309124Sdim auto PA = Impl.run(M, DummyMAM); 70309124Sdim return !PA.areAllPreserved(); 71309124Sdim } 72309124Sdim 73193323Sed private: 74309124Sdim GlobalDCEPass Impl; 75309124Sdim }; 76309124Sdim} 77193323Sed 78309124Sdimchar GlobalDCELegacyPass::ID = 0; 79309124SdimINITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", 80309124Sdim "Dead Global Elimination", false, false) 81193323Sed 82309124Sdim// Public interface to the GlobalDCEPass. 83309124SdimModulePass *llvm::createGlobalDCEPass() { 84309124Sdim return new GlobalDCELegacyPass(); 85193323Sed} 86193323Sed 87344779Sdim/// Returns true if F is effectively empty. 88276479Sdimstatic bool isEmptyFunction(Function *F) { 89276479Sdim BasicBlock &Entry = F->getEntryBlock(); 90344779Sdim for (auto &I : Entry) { 91344779Sdim if (isa<DbgInfoIntrinsic>(I)) 92344779Sdim continue; 93344779Sdim if (auto *RI = dyn_cast<ReturnInst>(&I)) 94344779Sdim return !RI->getReturnValue(); 95344779Sdim break; 96344779Sdim } 97344779Sdim return false; 98276479Sdim} 99276479Sdim 100321369Sdim/// Compute the set of GlobalValue that depends from V. 101321369Sdim/// The recursion stops as soon as a GlobalValue is met. 102321369Sdimvoid GlobalDCEPass::ComputeDependencies(Value *V, 103321369Sdim SmallPtrSetImpl<GlobalValue *> &Deps) { 104321369Sdim if (auto *I = dyn_cast<Instruction>(V)) { 105321369Sdim Function *Parent = I->getParent()->getParent(); 106321369Sdim Deps.insert(Parent); 107321369Sdim } else if (auto *GV = dyn_cast<GlobalValue>(V)) { 108321369Sdim Deps.insert(GV); 109321369Sdim } else if (auto *CE = dyn_cast<Constant>(V)) { 110321369Sdim // Avoid walking the whole tree of a big ConstantExprs multiple times. 111321369Sdim auto Where = ConstantDependenciesCache.find(CE); 112321369Sdim if (Where != ConstantDependenciesCache.end()) { 113321369Sdim auto const &K = Where->second; 114321369Sdim Deps.insert(K.begin(), K.end()); 115321369Sdim } else { 116321369Sdim SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE]; 117321369Sdim for (User *CEUser : CE->users()) 118321369Sdim ComputeDependencies(CEUser, LocalDeps); 119321369Sdim Deps.insert(LocalDeps.begin(), LocalDeps.end()); 120321369Sdim } 121321369Sdim } 122321369Sdim} 123321369Sdim 124321369Sdimvoid GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) { 125321369Sdim SmallPtrSet<GlobalValue *, 8> Deps; 126321369Sdim for (User *User : GV.users()) 127321369Sdim ComputeDependencies(User, Deps); 128321369Sdim Deps.erase(&GV); // Remove self-reference. 129321369Sdim for (GlobalValue *GVU : Deps) { 130360784Sdim // If this is a dep from a vtable to a virtual function, and we have 131360784Sdim // complete information about all virtual call sites which could call 132360784Sdim // though this vtable, then skip it, because the call site information will 133360784Sdim // be more precise. 134360784Sdim if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) { 135360784Sdim LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> " 136360784Sdim << GV.getName() << "\n"); 137360784Sdim continue; 138360784Sdim } 139327952Sdim GVDependencies[GVU].insert(&GV); 140321369Sdim } 141321369Sdim} 142321369Sdim 143321369Sdim/// Mark Global value as Live 144321369Sdimvoid GlobalDCEPass::MarkLive(GlobalValue &GV, 145321369Sdim SmallVectorImpl<GlobalValue *> *Updates) { 146321369Sdim auto const Ret = AliveGlobals.insert(&GV); 147321369Sdim if (!Ret.second) 148321369Sdim return; 149321369Sdim 150321369Sdim if (Updates) 151321369Sdim Updates->push_back(&GV); 152321369Sdim if (Comdat *C = GV.getComdat()) { 153360784Sdim for (auto &&CM : make_range(ComdatMembers.equal_range(C))) { 154321369Sdim MarkLive(*CM.second, Updates); // Recursion depth is only two because only 155321369Sdim // globals in the same comdat are visited. 156360784Sdim } 157321369Sdim } 158321369Sdim} 159321369Sdim 160360784Sdimvoid GlobalDCEPass::ScanVTables(Module &M) { 161360784Sdim SmallVector<MDNode *, 2> Types; 162360784Sdim LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n"); 163360784Sdim 164360784Sdim auto *LTOPostLinkMD = 165360784Sdim cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink")); 166360784Sdim bool LTOPostLink = 167360784Sdim LTOPostLinkMD && 168360784Sdim (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0); 169360784Sdim 170360784Sdim for (GlobalVariable &GV : M.globals()) { 171360784Sdim Types.clear(); 172360784Sdim GV.getMetadata(LLVMContext::MD_type, Types); 173360784Sdim if (GV.isDeclaration() || Types.empty()) 174360784Sdim continue; 175360784Sdim 176360784Sdim // Use the typeid metadata on the vtable to build a mapping from typeids to 177360784Sdim // the list of (GV, offset) pairs which are the possible vtables for that 178360784Sdim // typeid. 179360784Sdim for (MDNode *Type : Types) { 180360784Sdim Metadata *TypeID = Type->getOperand(1).get(); 181360784Sdim 182360784Sdim uint64_t Offset = 183360784Sdim cast<ConstantInt>( 184360784Sdim cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 185360784Sdim ->getZExtValue(); 186360784Sdim 187360784Sdim TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset)); 188360784Sdim } 189360784Sdim 190360784Sdim // If the type corresponding to the vtable is private to this translation 191360784Sdim // unit, we know that we can see all virtual functions which might use it, 192360784Sdim // so VFE is safe. 193360784Sdim if (auto GO = dyn_cast<GlobalObject>(&GV)) { 194360784Sdim GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility(); 195360784Sdim if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit || 196360784Sdim (LTOPostLink && 197360784Sdim TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) { 198360784Sdim LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n"); 199360784Sdim VFESafeVTables.insert(&GV); 200360784Sdim } 201360784Sdim } 202360784Sdim } 203360784Sdim} 204360784Sdim 205360784Sdimvoid GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId, 206360784Sdim uint64_t CallOffset) { 207360784Sdim for (auto &VTableInfo : TypeIdMap[TypeId]) { 208360784Sdim GlobalVariable *VTable = VTableInfo.first; 209360784Sdim uint64_t VTableOffset = VTableInfo.second; 210360784Sdim 211360784Sdim Constant *Ptr = 212360784Sdim getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset, 213360784Sdim *Caller->getParent()); 214360784Sdim if (!Ptr) { 215360784Sdim LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n"); 216360784Sdim VFESafeVTables.erase(VTable); 217360784Sdim return; 218360784Sdim } 219360784Sdim 220360784Sdim auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts()); 221360784Sdim if (!Callee) { 222360784Sdim LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n"); 223360784Sdim VFESafeVTables.erase(VTable); 224360784Sdim return; 225360784Sdim } 226360784Sdim 227360784Sdim LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> " 228360784Sdim << Callee->getName() << "\n"); 229360784Sdim GVDependencies[Caller].insert(Callee); 230360784Sdim } 231360784Sdim} 232360784Sdim 233360784Sdimvoid GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) { 234360784Sdim LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n"); 235360784Sdim Function *TypeCheckedLoadFunc = 236360784Sdim M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load)); 237360784Sdim 238360784Sdim if (!TypeCheckedLoadFunc) 239360784Sdim return; 240360784Sdim 241360784Sdim for (auto U : TypeCheckedLoadFunc->users()) { 242360784Sdim auto CI = dyn_cast<CallInst>(U); 243360784Sdim if (!CI) 244360784Sdim continue; 245360784Sdim 246360784Sdim auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 247360784Sdim Value *TypeIdValue = CI->getArgOperand(2); 248360784Sdim auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata(); 249360784Sdim 250360784Sdim if (Offset) { 251360784Sdim ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue()); 252360784Sdim } else { 253360784Sdim // type.checked.load with a non-constant offset, so assume every entry in 254360784Sdim // every matching vtable is used. 255360784Sdim for (auto &VTableInfo : TypeIdMap[TypeId]) { 256360784Sdim VFESafeVTables.erase(VTableInfo.first); 257360784Sdim } 258360784Sdim } 259360784Sdim } 260360784Sdim} 261360784Sdim 262360784Sdimvoid GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) { 263360784Sdim if (!ClEnableVFE) 264360784Sdim return; 265360784Sdim 266360784Sdim ScanVTables(M); 267360784Sdim 268360784Sdim if (VFESafeVTables.empty()) 269360784Sdim return; 270360784Sdim 271360784Sdim ScanTypeCheckedLoadIntrinsics(M); 272360784Sdim 273360784Sdim LLVM_DEBUG( 274360784Sdim dbgs() << "VFE safe vtables:\n"; 275360784Sdim for (auto *VTable : VFESafeVTables) 276360784Sdim dbgs() << " " << VTable->getName() << "\n"; 277360784Sdim ); 278360784Sdim} 279360784Sdim 280321369SdimPreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) { 281193323Sed bool Changed = false; 282276479Sdim 283321369Sdim // The algorithm first computes the set L of global variables that are 284321369Sdim // trivially live. Then it walks the initialization of these variables to 285321369Sdim // compute the globals used to initialize them, which effectively builds a 286321369Sdim // directed graph where nodes are global variables, and an edge from A to B 287321369Sdim // means B is used to initialize A. Finally, it propagates the liveness 288321369Sdim // information through the graph starting from the nodes in L. Nodes note 289321369Sdim // marked as alive are discarded. 290321369Sdim 291276479Sdim // Remove empty functions from the global ctors list. 292276479Sdim Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); 293276479Sdim 294288943Sdim // Collect the set of members for each comdat. 295288943Sdim for (Function &F : M) 296288943Sdim if (Comdat *C = F.getComdat()) 297288943Sdim ComdatMembers.insert(std::make_pair(C, &F)); 298288943Sdim for (GlobalVariable &GV : M.globals()) 299288943Sdim if (Comdat *C = GV.getComdat()) 300288943Sdim ComdatMembers.insert(std::make_pair(C, &GV)); 301288943Sdim for (GlobalAlias &GA : M.aliases()) 302288943Sdim if (Comdat *C = GA.getComdat()) 303288943Sdim ComdatMembers.insert(std::make_pair(C, &GA)); 304288943Sdim 305360784Sdim // Add dependencies between virtual call sites and the virtual functions they 306360784Sdim // might call, if we have that information. 307360784Sdim AddVirtualFunctionDependencies(M); 308360784Sdim 309193323Sed // Loop over the module, adding globals which are obviously necessary. 310309124Sdim for (GlobalObject &GO : M.global_objects()) { 311309124Sdim Changed |= RemoveUnusedGlobalValue(GO); 312309124Sdim // Functions with external linkage are needed if they have a body. 313193323Sed // Externally visible & appending globals are needed, if they have an 314193323Sed // initializer. 315344779Sdim if (!GO.isDeclaration()) 316309124Sdim if (!GO.isDiscardableIfUnused()) 317321369Sdim MarkLive(GO); 318321369Sdim 319321369Sdim UpdateGVDependencies(GO); 320193323Sed } 321193323Sed 322321369Sdim // Compute direct dependencies of aliases. 323296417Sdim for (GlobalAlias &GA : M.aliases()) { 324296417Sdim Changed |= RemoveUnusedGlobalValue(GA); 325193323Sed // Externally visible aliases are needed. 326296417Sdim if (!GA.isDiscardableIfUnused()) 327321369Sdim MarkLive(GA); 328321369Sdim 329321369Sdim UpdateGVDependencies(GA); 330193323Sed } 331193323Sed 332321369Sdim // Compute direct dependencies of ifuncs. 333309124Sdim for (GlobalIFunc &GIF : M.ifuncs()) { 334309124Sdim Changed |= RemoveUnusedGlobalValue(GIF); 335309124Sdim // Externally visible ifuncs are needed. 336309124Sdim if (!GIF.isDiscardableIfUnused()) 337321369Sdim MarkLive(GIF); 338321369Sdim 339321369Sdim UpdateGVDependencies(GIF); 340309124Sdim } 341309124Sdim 342321369Sdim // Propagate liveness from collected Global Values through the computed 343321369Sdim // dependencies. 344321369Sdim SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(), 345321369Sdim AliveGlobals.end()}; 346321369Sdim while (!NewLiveGVs.empty()) { 347321369Sdim GlobalValue *LGV = NewLiveGVs.pop_back_val(); 348327952Sdim for (auto *GVD : GVDependencies[LGV]) 349327952Sdim MarkLive(*GVD, &NewLiveGVs); 350321369Sdim } 351321369Sdim 352193323Sed // Now that all globals which are needed are in the AliveGlobals set, we loop 353193323Sed // through the program, deleting those which are not alive. 354193323Sed // 355193323Sed 356193323Sed // The first pass is to drop initializers of global variables which are dead. 357296417Sdim std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals 358296417Sdim for (GlobalVariable &GV : M.globals()) 359296417Sdim if (!AliveGlobals.count(&GV)) { 360296417Sdim DeadGlobalVars.push_back(&GV); // Keep track of dead globals 361296417Sdim if (GV.hasInitializer()) { 362296417Sdim Constant *Init = GV.getInitializer(); 363296417Sdim GV.setInitializer(nullptr); 364280031Sdim if (isSafeToDestroyConstant(Init)) 365280031Sdim Init->destroyConstant(); 366280031Sdim } 367193323Sed } 368193323Sed 369193323Sed // The second pass drops the bodies of functions which are dead... 370296417Sdim std::vector<Function *> DeadFunctions; 371296417Sdim for (Function &F : M) 372296417Sdim if (!AliveGlobals.count(&F)) { 373296417Sdim DeadFunctions.push_back(&F); // Keep track of dead globals 374296417Sdim if (!F.isDeclaration()) 375296417Sdim F.deleteBody(); 376193323Sed } 377193323Sed 378193323Sed // The third pass drops targets of aliases which are dead... 379193323Sed std::vector<GlobalAlias*> DeadAliases; 380296417Sdim for (GlobalAlias &GA : M.aliases()) 381296417Sdim if (!AliveGlobals.count(&GA)) { 382296417Sdim DeadAliases.push_back(&GA); 383296417Sdim GA.setAliasee(nullptr); 384193323Sed } 385193323Sed 386321369Sdim // The fourth pass drops targets of ifuncs which are dead... 387309124Sdim std::vector<GlobalIFunc*> DeadIFuncs; 388309124Sdim for (GlobalIFunc &GIF : M.ifuncs()) 389309124Sdim if (!AliveGlobals.count(&GIF)) { 390309124Sdim DeadIFuncs.push_back(&GIF); 391309124Sdim GIF.setResolver(nullptr); 392309124Sdim } 393309124Sdim 394314564Sdim // Now that all interferences have been dropped, delete the actual objects 395314564Sdim // themselves. 396314564Sdim auto EraseUnusedGlobalValue = [&](GlobalValue *GV) { 397314564Sdim RemoveUnusedGlobalValue(*GV); 398314564Sdim GV->eraseFromParent(); 399193323Sed Changed = true; 400314564Sdim }; 401193323Sed 402314564Sdim NumFunctions += DeadFunctions.size(); 403360784Sdim for (Function *F : DeadFunctions) { 404360784Sdim if (!F->use_empty()) { 405360784Sdim // Virtual functions might still be referenced by one or more vtables, 406360784Sdim // but if we've proven them to be unused then it's safe to replace the 407360784Sdim // virtual function pointers with null, allowing us to remove the 408360784Sdim // function itself. 409360784Sdim ++NumVFuncs; 410360784Sdim F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType())); 411360784Sdim } 412314564Sdim EraseUnusedGlobalValue(F); 413360784Sdim } 414193323Sed 415314564Sdim NumVariables += DeadGlobalVars.size(); 416314564Sdim for (GlobalVariable *GV : DeadGlobalVars) 417314564Sdim EraseUnusedGlobalValue(GV); 418193323Sed 419314564Sdim NumAliases += DeadAliases.size(); 420314564Sdim for (GlobalAlias *GA : DeadAliases) 421314564Sdim EraseUnusedGlobalValue(GA); 422309124Sdim 423314564Sdim NumIFuncs += DeadIFuncs.size(); 424314564Sdim for (GlobalIFunc *GIF : DeadIFuncs) 425314564Sdim EraseUnusedGlobalValue(GIF); 426314564Sdim 427193323Sed // Make sure that all memory is released 428193323Sed AliveGlobals.clear(); 429321369Sdim ConstantDependenciesCache.clear(); 430321369Sdim GVDependencies.clear(); 431288943Sdim ComdatMembers.clear(); 432360784Sdim TypeIdMap.clear(); 433360784Sdim VFESafeVTables.clear(); 434198090Srdivacky 435309124Sdim if (Changed) 436309124Sdim return PreservedAnalyses::none(); 437309124Sdim return PreservedAnalyses::all(); 438193323Sed} 439193323Sed 440193323Sed// RemoveUnusedGlobalValue - Loop over all of the uses of the specified 441193323Sed// GlobalValue, looking for the constant pointer ref that may be pointing to it. 442193323Sed// If found, check to see if the constant pointer ref is safe to destroy, and if 443193323Sed// so, nuke it. This will reduce the reference count on the global value, which 444193323Sed// might make it deader. 445193323Sed// 446309124Sdimbool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) { 447296417Sdim if (GV.use_empty()) 448296417Sdim return false; 449193323Sed GV.removeDeadConstantUsers(); 450193323Sed return GV.use_empty(); 451193323Sed} 452