GlobalDCE.cpp revision 360784
123228Swosch//===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// 223228Swosch// 323228Swosch// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 423228Swosch// See https://llvm.org/LICENSE.txt for license information. 523228Swosch// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 623228Swosch// 723228Swosch//===----------------------------------------------------------------------===// 823228Swosch// 923228Swosch// This transform is designed to eliminate unreachable internal globals from the 1023228Swosch// program. It uses an aggressive algorithm, searching out globals that are 1123228Swosch// known to be alive. After it finds all of the globals which are needed, it 1223228Swosch// deletes whatever is left over. This allows it to delete recursive chunks of 1323228Swosch// the program which are unreachable. 1423228Swosch// 1523228Swosch//===----------------------------------------------------------------------===// 1623228Swosch 1723228Swosch#include "llvm/Transforms/IPO/GlobalDCE.h" 1823228Swosch#include "llvm/ADT/SmallPtrSet.h" 1923228Swosch#include "llvm/ADT/Statistic.h" 2023228Swosch#include "llvm/Analysis/TypeMetadataUtils.h" 2123228Swosch#include "llvm/IR/Instructions.h" 2223228Swosch#include "llvm/IR/IntrinsicInst.h" 2323228Swosch#include "llvm/IR/Module.h" 2423228Swosch#include "llvm/IR/Operator.h" 2523228Swosch#include "llvm/InitializePasses.h" 2623228Swosch#include "llvm/Pass.h" 2723228Swosch#include "llvm/Support/CommandLine.h" 2823228Swosch#include "llvm/Transforms/IPO.h" 2923228Swosch#include "llvm/Transforms/Utils/CtorUtils.h" 3023228Swosch#include "llvm/Transforms/Utils/GlobalStatus.h" 3123228Swosch 3223228Swoschusing namespace llvm; 3323228Swosch 3423228Swosch#define DEBUG_TYPE "globaldce" 3523228Swosch 3623228Swoschstatic cl::opt<bool> 3723228Swosch ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore, 3823228Swosch cl::desc("Enable virtual function elimination")); 3923228Swosch 4023228SwoschSTATISTIC(NumAliases , "Number of global aliases removed"); 4123228SwoschSTATISTIC(NumFunctions, "Number of functions removed"); 4223228SwoschSTATISTIC(NumIFuncs, "Number of indirect functions removed"); 4323228SwoschSTATISTIC(NumVariables, "Number of global variables removed"); 4423228SwoschSTATISTIC(NumVFuncs, "Number of virtual functions removed"); 4523228Swosch 4623228Swoschnamespace { 4723228Swosch class GlobalDCELegacyPass : public ModulePass { 4823228Swosch public: 4923228Swosch static char ID; // Pass identification, replacement for typeid 5023228Swosch GlobalDCELegacyPass() : ModulePass(ID) { 5123228Swosch initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry()); 5223228Swosch } 5323228Swosch 5423228Swosch // run - Do the GlobalDCE pass on the specified module, optionally updating 5523228Swosch // the specified callgraph to reflect the changes. 5623228Swosch // 5723228Swosch bool runOnModule(Module &M) override { 5823228Swosch if (skipModule(M)) 5923228Swosch return false; 6023228Swosch 6123228Swosch // We need a minimally functional dummy module analysis manager. It needs 6223228Swosch // to at least know about the possibility of proxying a function analysis 6323228Swosch // manager. 6423228Swosch FunctionAnalysisManager DummyFAM; 6523228Swosch ModuleAnalysisManager DummyMAM; 6623228Swosch DummyMAM.registerPass( 6723228Swosch [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); }); 6823228Swosch 6923228Swosch auto PA = Impl.run(M, DummyMAM); 7023228Swosch return !PA.areAllPreserved(); 7123228Swosch } 7223228Swosch 7323228Swosch private: 7423228Swosch GlobalDCEPass Impl; 7523228Swosch }; 7623228Swosch} 7723228Swosch 7823228Swoschchar GlobalDCELegacyPass::ID = 0; 7923228SwoschINITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", 8023228Swosch "Dead Global Elimination", false, false) 8123228Swosch 8223228Swosch// Public interface to the GlobalDCEPass. 8323228SwoschModulePass *llvm::createGlobalDCEPass() { 8423228Swosch return new GlobalDCELegacyPass(); 8523228Swosch} 8623228Swosch 8723228Swosch/// Returns true if F is effectively empty. 8823228Swoschstatic bool isEmptyFunction(Function *F) { 8923228Swosch BasicBlock &Entry = F->getEntryBlock(); 9023228Swosch for (auto &I : Entry) { 9123228Swosch if (isa<DbgInfoIntrinsic>(I)) 9223228Swosch continue; 9323228Swosch if (auto *RI = dyn_cast<ReturnInst>(&I)) 9423228Swosch return !RI->getReturnValue(); 9523228Swosch break; 9623228Swosch } 9723228Swosch return false; 9823228Swosch} 9923228Swosch 10023228Swosch/// Compute the set of GlobalValue that depends from V. 10123228Swosch/// The recursion stops as soon as a GlobalValue is met. 10223228Swoschvoid GlobalDCEPass::ComputeDependencies(Value *V, 10323228Swosch SmallPtrSetImpl<GlobalValue *> &Deps) { 10423228Swosch if (auto *I = dyn_cast<Instruction>(V)) { 10523228Swosch Function *Parent = I->getParent()->getParent(); 10623228Swosch Deps.insert(Parent); 10723228Swosch } else if (auto *GV = dyn_cast<GlobalValue>(V)) { 10823228Swosch Deps.insert(GV); 10923228Swosch } else if (auto *CE = dyn_cast<Constant>(V)) { 11023228Swosch // Avoid walking the whole tree of a big ConstantExprs multiple times. 11123228Swosch auto Where = ConstantDependenciesCache.find(CE); 11223228Swosch if (Where != ConstantDependenciesCache.end()) { 11323228Swosch auto const &K = Where->second; 11423228Swosch Deps.insert(K.begin(), K.end()); 11523228Swosch } else { 11623228Swosch SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE]; 11723228Swosch for (User *CEUser : CE->users()) 11823228Swosch ComputeDependencies(CEUser, LocalDeps); 11923228Swosch Deps.insert(LocalDeps.begin(), LocalDeps.end()); 12023228Swosch } 12123228Swosch } 12223228Swosch} 12323228Swosch 12423228Swoschvoid GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) { 12523228Swosch SmallPtrSet<GlobalValue *, 8> Deps; 12623228Swosch for (User *User : GV.users()) 12723228Swosch ComputeDependencies(User, Deps); 12823228Swosch Deps.erase(&GV); // Remove self-reference. 12923228Swosch for (GlobalValue *GVU : Deps) { 13023228Swosch // If this is a dep from a vtable to a virtual function, and we have 13123228Swosch // complete information about all virtual call sites which could call 13223228Swosch // though this vtable, then skip it, because the call site information will 13323228Swosch // be more precise. 13423228Swosch if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) { 13523228Swosch LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> " 13623228Swosch << GV.getName() << "\n"); 13723228Swosch continue; 13823228Swosch } 13923228Swosch GVDependencies[GVU].insert(&GV); 14023228Swosch } 14123228Swosch} 14223228Swosch 14323228Swosch/// Mark Global value as Live 14423228Swoschvoid GlobalDCEPass::MarkLive(GlobalValue &GV, 14523228Swosch SmallVectorImpl<GlobalValue *> *Updates) { 14623228Swosch auto const Ret = AliveGlobals.insert(&GV); 14723228Swosch if (!Ret.second) 14823228Swosch return; 14923228Swosch 15023228Swosch if (Updates) 15123228Swosch Updates->push_back(&GV); 15223228Swosch if (Comdat *C = GV.getComdat()) { 15323228Swosch for (auto &&CM : make_range(ComdatMembers.equal_range(C))) { 15423228Swosch MarkLive(*CM.second, Updates); // Recursion depth is only two because only 15523228Swosch // globals in the same comdat are visited. 15623228Swosch } 15723228Swosch } 15823228Swosch} 15923228Swosch 16023228Swoschvoid GlobalDCEPass::ScanVTables(Module &M) { 16123228Swosch SmallVector<MDNode *, 2> Types; 16223228Swosch LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n"); 16323228Swosch 16423228Swosch auto *LTOPostLinkMD = 16523228Swosch cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink")); 16623228Swosch bool LTOPostLink = 16723228Swosch LTOPostLinkMD && 16823228Swosch (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0); 16923228Swosch 17023228Swosch for (GlobalVariable &GV : M.globals()) { 17123228Swosch Types.clear(); 17223228Swosch GV.getMetadata(LLVMContext::MD_type, Types); 17323228Swosch if (GV.isDeclaration() || Types.empty()) 17423228Swosch continue; 175 176 // Use the typeid metadata on the vtable to build a mapping from typeids to 177 // the list of (GV, offset) pairs which are the possible vtables for that 178 // typeid. 179 for (MDNode *Type : Types) { 180 Metadata *TypeID = Type->getOperand(1).get(); 181 182 uint64_t Offset = 183 cast<ConstantInt>( 184 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 185 ->getZExtValue(); 186 187 TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset)); 188 } 189 190 // If the type corresponding to the vtable is private to this translation 191 // unit, we know that we can see all virtual functions which might use it, 192 // so VFE is safe. 193 if (auto GO = dyn_cast<GlobalObject>(&GV)) { 194 GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility(); 195 if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit || 196 (LTOPostLink && 197 TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) { 198 LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n"); 199 VFESafeVTables.insert(&GV); 200 } 201 } 202 } 203} 204 205void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId, 206 uint64_t CallOffset) { 207 for (auto &VTableInfo : TypeIdMap[TypeId]) { 208 GlobalVariable *VTable = VTableInfo.first; 209 uint64_t VTableOffset = VTableInfo.second; 210 211 Constant *Ptr = 212 getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset, 213 *Caller->getParent()); 214 if (!Ptr) { 215 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n"); 216 VFESafeVTables.erase(VTable); 217 return; 218 } 219 220 auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts()); 221 if (!Callee) { 222 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n"); 223 VFESafeVTables.erase(VTable); 224 return; 225 } 226 227 LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> " 228 << Callee->getName() << "\n"); 229 GVDependencies[Caller].insert(Callee); 230 } 231} 232 233void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) { 234 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n"); 235 Function *TypeCheckedLoadFunc = 236 M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load)); 237 238 if (!TypeCheckedLoadFunc) 239 return; 240 241 for (auto U : TypeCheckedLoadFunc->users()) { 242 auto CI = dyn_cast<CallInst>(U); 243 if (!CI) 244 continue; 245 246 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 247 Value *TypeIdValue = CI->getArgOperand(2); 248 auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata(); 249 250 if (Offset) { 251 ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue()); 252 } else { 253 // type.checked.load with a non-constant offset, so assume every entry in 254 // every matching vtable is used. 255 for (auto &VTableInfo : TypeIdMap[TypeId]) { 256 VFESafeVTables.erase(VTableInfo.first); 257 } 258 } 259 } 260} 261 262void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) { 263 if (!ClEnableVFE) 264 return; 265 266 ScanVTables(M); 267 268 if (VFESafeVTables.empty()) 269 return; 270 271 ScanTypeCheckedLoadIntrinsics(M); 272 273 LLVM_DEBUG( 274 dbgs() << "VFE safe vtables:\n"; 275 for (auto *VTable : VFESafeVTables) 276 dbgs() << " " << VTable->getName() << "\n"; 277 ); 278} 279 280PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) { 281 bool Changed = false; 282 283 // The algorithm first computes the set L of global variables that are 284 // trivially live. Then it walks the initialization of these variables to 285 // compute the globals used to initialize them, which effectively builds a 286 // directed graph where nodes are global variables, and an edge from A to B 287 // means B is used to initialize A. Finally, it propagates the liveness 288 // information through the graph starting from the nodes in L. Nodes note 289 // marked as alive are discarded. 290 291 // Remove empty functions from the global ctors list. 292 Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); 293 294 // Collect the set of members for each comdat. 295 for (Function &F : M) 296 if (Comdat *C = F.getComdat()) 297 ComdatMembers.insert(std::make_pair(C, &F)); 298 for (GlobalVariable &GV : M.globals()) 299 if (Comdat *C = GV.getComdat()) 300 ComdatMembers.insert(std::make_pair(C, &GV)); 301 for (GlobalAlias &GA : M.aliases()) 302 if (Comdat *C = GA.getComdat()) 303 ComdatMembers.insert(std::make_pair(C, &GA)); 304 305 // Add dependencies between virtual call sites and the virtual functions they 306 // might call, if we have that information. 307 AddVirtualFunctionDependencies(M); 308 309 // Loop over the module, adding globals which are obviously necessary. 310 for (GlobalObject &GO : M.global_objects()) { 311 Changed |= RemoveUnusedGlobalValue(GO); 312 // Functions with external linkage are needed if they have a body. 313 // Externally visible & appending globals are needed, if they have an 314 // initializer. 315 if (!GO.isDeclaration()) 316 if (!GO.isDiscardableIfUnused()) 317 MarkLive(GO); 318 319 UpdateGVDependencies(GO); 320 } 321 322 // Compute direct dependencies of aliases. 323 for (GlobalAlias &GA : M.aliases()) { 324 Changed |= RemoveUnusedGlobalValue(GA); 325 // Externally visible aliases are needed. 326 if (!GA.isDiscardableIfUnused()) 327 MarkLive(GA); 328 329 UpdateGVDependencies(GA); 330 } 331 332 // Compute direct dependencies of ifuncs. 333 for (GlobalIFunc &GIF : M.ifuncs()) { 334 Changed |= RemoveUnusedGlobalValue(GIF); 335 // Externally visible ifuncs are needed. 336 if (!GIF.isDiscardableIfUnused()) 337 MarkLive(GIF); 338 339 UpdateGVDependencies(GIF); 340 } 341 342 // Propagate liveness from collected Global Values through the computed 343 // dependencies. 344 SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(), 345 AliveGlobals.end()}; 346 while (!NewLiveGVs.empty()) { 347 GlobalValue *LGV = NewLiveGVs.pop_back_val(); 348 for (auto *GVD : GVDependencies[LGV]) 349 MarkLive(*GVD, &NewLiveGVs); 350 } 351 352 // Now that all globals which are needed are in the AliveGlobals set, we loop 353 // through the program, deleting those which are not alive. 354 // 355 356 // The first pass is to drop initializers of global variables which are dead. 357 std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals 358 for (GlobalVariable &GV : M.globals()) 359 if (!AliveGlobals.count(&GV)) { 360 DeadGlobalVars.push_back(&GV); // Keep track of dead globals 361 if (GV.hasInitializer()) { 362 Constant *Init = GV.getInitializer(); 363 GV.setInitializer(nullptr); 364 if (isSafeToDestroyConstant(Init)) 365 Init->destroyConstant(); 366 } 367 } 368 369 // The second pass drops the bodies of functions which are dead... 370 std::vector<Function *> DeadFunctions; 371 for (Function &F : M) 372 if (!AliveGlobals.count(&F)) { 373 DeadFunctions.push_back(&F); // Keep track of dead globals 374 if (!F.isDeclaration()) 375 F.deleteBody(); 376 } 377 378 // The third pass drops targets of aliases which are dead... 379 std::vector<GlobalAlias*> DeadAliases; 380 for (GlobalAlias &GA : M.aliases()) 381 if (!AliveGlobals.count(&GA)) { 382 DeadAliases.push_back(&GA); 383 GA.setAliasee(nullptr); 384 } 385 386 // The fourth pass drops targets of ifuncs which are dead... 387 std::vector<GlobalIFunc*> DeadIFuncs; 388 for (GlobalIFunc &GIF : M.ifuncs()) 389 if (!AliveGlobals.count(&GIF)) { 390 DeadIFuncs.push_back(&GIF); 391 GIF.setResolver(nullptr); 392 } 393 394 // Now that all interferences have been dropped, delete the actual objects 395 // themselves. 396 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) { 397 RemoveUnusedGlobalValue(*GV); 398 GV->eraseFromParent(); 399 Changed = true; 400 }; 401 402 NumFunctions += DeadFunctions.size(); 403 for (Function *F : DeadFunctions) { 404 if (!F->use_empty()) { 405 // Virtual functions might still be referenced by one or more vtables, 406 // but if we've proven them to be unused then it's safe to replace the 407 // virtual function pointers with null, allowing us to remove the 408 // function itself. 409 ++NumVFuncs; 410 F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType())); 411 } 412 EraseUnusedGlobalValue(F); 413 } 414 415 NumVariables += DeadGlobalVars.size(); 416 for (GlobalVariable *GV : DeadGlobalVars) 417 EraseUnusedGlobalValue(GV); 418 419 NumAliases += DeadAliases.size(); 420 for (GlobalAlias *GA : DeadAliases) 421 EraseUnusedGlobalValue(GA); 422 423 NumIFuncs += DeadIFuncs.size(); 424 for (GlobalIFunc *GIF : DeadIFuncs) 425 EraseUnusedGlobalValue(GIF); 426 427 // Make sure that all memory is released 428 AliveGlobals.clear(); 429 ConstantDependenciesCache.clear(); 430 GVDependencies.clear(); 431 ComdatMembers.clear(); 432 TypeIdMap.clear(); 433 VFESafeVTables.clear(); 434 435 if (Changed) 436 return PreservedAnalyses::none(); 437 return PreservedAnalyses::all(); 438} 439 440// RemoveUnusedGlobalValue - Loop over all of the uses of the specified 441// GlobalValue, looking for the constant pointer ref that may be pointing to it. 442// If found, check to see if the constant pointer ref is safe to destroy, and if 443// so, nuke it. This will reduce the reference count on the global value, which 444// might make it deader. 445// 446bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) { 447 if (GV.use_empty()) 448 return false; 449 GV.removeDeadConstantUsers(); 450 return GV.use_empty(); 451} 452