llvm/lib/Transforms/IPO/GlobalDCE.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-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/IR/Operator.h"
  25 #include "llvm/InitializePasses.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Transforms/IPO.h"
  29 #include "llvm/Transforms/Utils/CtorUtils.h"
  30 #include "llvm/Transforms/Utils/GlobalStatus.h"
  31
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "globaldce"
  35
  36 static cl::opt<bool>
  37     ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
  38                 cl::desc("Enable virtual function elimination"));
  39
  40 STATISTIC(NumAliases  , "Number of global aliases removed");
  41 STATISTIC(NumFunctions, "Number of functions removed");
  42 STATISTIC(NumIFuncs,    "Number of indirect functions removed");
  43 STATISTIC(NumVariables, "Number of global variables removed");
  44 STATISTIC(NumVFuncs,    "Number of virtual functions removed");
  45
  46 namespace {
  47   class GlobalDCELegacyPass : public ModulePass {
  48   public:
  49     static char ID; // Pass identification, replacement for typeid
  50     GlobalDCELegacyPass() : ModulePass(ID) {
  51       initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
  52     }
  53
  54     // run - Do the GlobalDCE pass on the specified module, optionally updating
  55     // the specified callgraph to reflect the changes.
  56     //
  57     bool runOnModule(Module &M) override {
  58       if (skipModule(M))
  59         return false;
  60
  61       // We need a minimally functional dummy module analysis manager. It needs
  62       // to at least know about the possibility of proxying a function analysis
  63       // manager.
  64       FunctionAnalysisManager DummyFAM;
  65       ModuleAnalysisManager DummyMAM;
  66       DummyMAM.registerPass(
  67           [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
  68
  69       auto PA = Impl.run(M, DummyMAM);
  70       return !PA.areAllPreserved();
  71     }
  72
  73   private:
  74     GlobalDCEPass Impl;
  75   };
  76 }
  77
  78 char GlobalDCELegacyPass::ID = 0;
  79 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
  80                 "Dead Global Elimination", false, false)
  81
  82 // Public interface to the GlobalDCEPass.
  83 ModulePass *llvm::createGlobalDCEPass() {
  84   return new GlobalDCELegacyPass();
  85 }
  86
  87 /// Returns true if F is effectively empty.
  88 static bool isEmptyFunction(Function *F) {
  89   BasicBlock &Entry = F->getEntryBlock();
  90   for (auto &I : Entry) {
  91     if (isa<DbgInfoIntrinsic>(I))
  92       continue;
  93     if (auto *RI = dyn_cast<ReturnInst>(&I))
  94       return !RI->getReturnValue();
  95     break;
  96   }
  97   return false;
  98 }
  99
 100 /// Compute the set of GlobalValue that depends from V.
 101 /// The recursion stops as soon as a GlobalValue is met.
 102 void GlobalDCEPass::ComputeDependencies(Value *V,
 103                                         SmallPtrSetImpl<GlobalValue *> &Deps) {
 104   if (auto *I = dyn_cast<Instruction>(V)) {
 105     Function *Parent = I->getParent()->getParent();
 106     Deps.insert(Parent);
 107   } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
 108     Deps.insert(GV);
 109   } else if (auto *CE = dyn_cast<Constant>(V)) {
 110     // Avoid walking the whole tree of a big ConstantExprs multiple times.
 111     auto Where = ConstantDependenciesCache.find(CE);
 112     if (Where != ConstantDependenciesCache.end()) {
 113       auto const &K = Where->second;
 114       Deps.insert(K.begin(), K.end());
 115     } else {
 116       SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
 117       for (User *CEUser : CE->users())
 118         ComputeDependencies(CEUser, LocalDeps);
 119       Deps.insert(LocalDeps.begin(), LocalDeps.end());
 120     }
 121   }
 122 }
 123
 124 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
 125   SmallPtrSet<GlobalValue *, 8> Deps;
 126   for (User *User : GV.users())
 127     ComputeDependencies(User, Deps);
 128   Deps.erase(&GV); // Remove self-reference.
 129   for (GlobalValue *GVU : Deps) {
 130     // If this is a dep from a vtable to a virtual function, and we have
 131     // complete information about all virtual call sites which could call
 132     // though this vtable, then skip it, because the call site information will
 133     // be more precise.
 134     if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
 135       LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
 136                         << GV.getName() << "\n");
 137       continue;
 138     }
 139     GVDependencies[GVU].insert(&GV);
 140   }
 141 }
 142
 143 /// Mark Global value as Live
 144 void GlobalDCEPass::MarkLive(GlobalValue &GV,
 145                              SmallVectorImpl<GlobalValue *> *Updates) {
 146   auto const Ret = AliveGlobals.insert(&GV);
 147   if (!Ret.second)
 148     return;
 149
 150   if (Updates)
 151     Updates->push_back(&GV);
 152   if (Comdat *C = GV.getComdat()) {
 153     for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
 154       MarkLive(*CM.second, Updates); // Recursion depth is only two because only
 155                                      // globals in the same comdat are visited.
 156     }
 157   }
 158 }
 159
 160 void GlobalDCEPass::ScanVTables(Module &M) {
 161   SmallVector<MDNode *, 2> Types;
 162   LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
 163
 164   auto *LTOPostLinkMD =
 165       cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
 166   bool LTOPostLink =
 167       LTOPostLinkMD &&
 168       (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0);
 169
 170   for (GlobalVariable &GV : M.globals()) {
 171     Types.clear();
 172     GV.getMetadata(LLVMContext::MD_type, Types);
 173     if (GV.isDeclaration() || Types.empty())
 174       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
 205 void 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
 233 void 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
 262 void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
 263   if (!ClEnableVFE)
 264     return;
 265
 266   // If the Virtual Function Elim module flag is present and set to zero, then
 267   // the vcall_visibility metadata was inserted for another optimization (WPD)
 268   // and we may not have type checked loads on all accesses to the vtable.
 269   // Don't attempt VFE in that case.
 270   auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
 271       M.getModuleFlag("Virtual Function Elim"));
 272   if (!Val || Val->getZExtValue() == 0)
 273     return;
 274
 275   ScanVTables(M);
 276
 277   if (VFESafeVTables.empty())
 278     return;
 279
 280   ScanTypeCheckedLoadIntrinsics(M);
 281
 282   LLVM_DEBUG(
 283     dbgs() << "VFE safe vtables:\n";
 284     for (auto *VTable : VFESafeVTables)
 285       dbgs() << "  " << VTable->getName() << "\n";
 286   );
 287 }
 288
 289 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
 290   bool Changed = false;
 291
 292   // The algorithm first computes the set L of global variables that are
 293   // trivially live.  Then it walks the initialization of these variables to
 294   // compute the globals used to initialize them, which effectively builds a
 295   // directed graph where nodes are global variables, and an edge from A to B
 296   // means B is used to initialize A.  Finally, it propagates the liveness
 297   // information through the graph starting from the nodes in L. Nodes note
 298   // marked as alive are discarded.
 299
 300   // Remove empty functions from the global ctors list.
 301   Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
 302
 303   // Collect the set of members for each comdat.
 304   for (Function &F : M)
 305     if (Comdat *C = F.getComdat())
 306       ComdatMembers.insert(std::make_pair(C, &F));
 307   for (GlobalVariable &GV : M.globals())
 308     if (Comdat *C = GV.getComdat())
 309       ComdatMembers.insert(std::make_pair(C, &GV));
 310   for (GlobalAlias &GA : M.aliases())
 311     if (Comdat *C = GA.getComdat())
 312       ComdatMembers.insert(std::make_pair(C, &GA));
 313
 314   // Add dependencies between virtual call sites and the virtual functions they
 315   // might call, if we have that information.
 316   AddVirtualFunctionDependencies(M);
 317
 318   // Loop over the module, adding globals which are obviously necessary.
 319   for (GlobalObject &GO : M.global_objects()) {
 320     Changed |= RemoveUnusedGlobalValue(GO);
 321     // Functions with external linkage are needed if they have a body.
 322     // Externally visible & appending globals are needed, if they have an
 323     // initializer.
 324     if (!GO.isDeclaration())
 325       if (!GO.isDiscardableIfUnused())
 326         MarkLive(GO);
 327
 328     UpdateGVDependencies(GO);
 329   }
 330
 331   // Compute direct dependencies of aliases.
 332   for (GlobalAlias &GA : M.aliases()) {
 333     Changed |= RemoveUnusedGlobalValue(GA);
 334     // Externally visible aliases are needed.
 335     if (!GA.isDiscardableIfUnused())
 336       MarkLive(GA);
 337
 338     UpdateGVDependencies(GA);
 339   }
 340
 341   // Compute direct dependencies of ifuncs.
 342   for (GlobalIFunc &GIF : M.ifuncs()) {
 343     Changed |= RemoveUnusedGlobalValue(GIF);
 344     // Externally visible ifuncs are needed.
 345     if (!GIF.isDiscardableIfUnused())
 346       MarkLive(GIF);
 347
 348     UpdateGVDependencies(GIF);
 349   }
 350
 351   // Propagate liveness from collected Global Values through the computed
 352   // dependencies.
 353   SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
 354                                            AliveGlobals.end()};
 355   while (!NewLiveGVs.empty()) {
 356     GlobalValue *LGV = NewLiveGVs.pop_back_val();
 357     for (auto *GVD : GVDependencies[LGV])
 358       MarkLive(*GVD, &NewLiveGVs);
 359   }
 360
 361   // Now that all globals which are needed are in the AliveGlobals set, we loop
 362   // through the program, deleting those which are not alive.
 363   //
 364
 365   // The first pass is to drop initializers of global variables which are dead.
 366   std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
 367   for (GlobalVariable &GV : M.globals())
 368     if (!AliveGlobals.count(&GV)) {
 369       DeadGlobalVars.push_back(&GV);         // Keep track of dead globals
 370       if (GV.hasInitializer()) {
 371         Constant *Init = GV.getInitializer();
 372         GV.setInitializer(nullptr);
 373         if (isSafeToDestroyConstant(Init))
 374           Init->destroyConstant();
 375       }
 376     }
 377
 378   // The second pass drops the bodies of functions which are dead...
 379   std::vector<Function *> DeadFunctions;
 380   for (Function &F : M)
 381     if (!AliveGlobals.count(&F)) {
 382       DeadFunctions.push_back(&F);         // Keep track of dead globals
 383       if (!F.isDeclaration())
 384         F.deleteBody();
 385     }
 386
 387   // The third pass drops targets of aliases which are dead...
 388   std::vector<GlobalAlias*> DeadAliases;
 389   for (GlobalAlias &GA : M.aliases())
 390     if (!AliveGlobals.count(&GA)) {
 391       DeadAliases.push_back(&GA);
 392       GA.setAliasee(nullptr);
 393     }
 394
 395   // The fourth pass drops targets of ifuncs which are dead...
 396   std::vector<GlobalIFunc*> DeadIFuncs;
 397   for (GlobalIFunc &GIF : M.ifuncs())
 398     if (!AliveGlobals.count(&GIF)) {
 399       DeadIFuncs.push_back(&GIF);
 400       GIF.setResolver(nullptr);
 401     }
 402
 403   // Now that all interferences have been dropped, delete the actual objects
 404   // themselves.
 405   auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
 406     RemoveUnusedGlobalValue(*GV);
 407     GV->eraseFromParent();
 408     Changed = true;
 409   };
 410
 411   NumFunctions += DeadFunctions.size();
 412   for (Function *F : DeadFunctions) {
 413     if (!F->use_empty()) {
 414       // Virtual functions might still be referenced by one or more vtables,
 415       // but if we've proven them to be unused then it's safe to replace the
 416       // virtual function pointers with null, allowing us to remove the
 417       // function itself.
 418       ++NumVFuncs;
 419       F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
 420     }
 421     EraseUnusedGlobalValue(F);
 422   }
 423
 424   NumVariables += DeadGlobalVars.size();
 425   for (GlobalVariable *GV : DeadGlobalVars)
 426     EraseUnusedGlobalValue(GV);
 427
 428   NumAliases += DeadAliases.size();
 429   for (GlobalAlias *GA : DeadAliases)
 430     EraseUnusedGlobalValue(GA);
 431
 432   NumIFuncs += DeadIFuncs.size();
 433   for (GlobalIFunc *GIF : DeadIFuncs)
 434     EraseUnusedGlobalValue(GIF);
 435
 436   // Make sure that all memory is released
 437   AliveGlobals.clear();
 438   ConstantDependenciesCache.clear();
 439   GVDependencies.clear();
 440   ComdatMembers.clear();
 441   TypeIdMap.clear();
 442   VFESafeVTables.clear();
 443
 444   if (Changed)
 445     return PreservedAnalyses::none();
 446   return PreservedAnalyses::all();
 447 }
 448
 449 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
 450 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
 451 // If found, check to see if the constant pointer ref is safe to destroy, and if
 452 // so, nuke it.  This will reduce the reference count on the global value, which
 453 // might make it deader.
 454 //
 455 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
 456   if (GV.use_empty())
 457     return false;
 458   GV.removeDeadConstantUsers();
 459   return GV.use_empty();
 460 }