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