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/Pass.h"
  26 #include "llvm/Transforms/IPO.h"
  27 #include "llvm/Transforms/Utils/CtorUtils.h"
  28 #include "llvm/Transforms/Utils/GlobalStatus.h"
  29
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "globaldce"
  33
  34 static cl::opt<bool>
  35     ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
  36                 cl::desc("Enable virtual function elimination"));
  37
  38 STATISTIC(NumAliases  , "Number of global aliases removed");
  39 STATISTIC(NumFunctions, "Number of functions removed");
  40 STATISTIC(NumIFuncs,    "Number of indirect functions removed");
  41 STATISTIC(NumVariables, "Number of global variables removed");
  42 STATISTIC(NumVFuncs,    "Number of virtual functions removed");
  43
  44 namespace {
  45   class GlobalDCELegacyPass : public ModulePass {
  46   public:
  47     static char ID; // Pass identification, replacement for typeid
  48     GlobalDCELegacyPass() : ModulePass(ID) {
  49       initializeGlobalDCELegacyPassPass(*PassRegistry::getPassRegistry());
  50     }
  51
  52     // run - Do the GlobalDCE pass on the specified module, optionally updating
  53     // the specified callgraph to reflect the changes.
  54     //
  55     bool runOnModule(Module &M) override {
  56       if (skipModule(M))
  57         return false;
  58
  59       // We need a minimally functional dummy module analysis manager. It needs
  60       // to at least know about the possibility of proxying a function analysis
  61       // manager.
  62       FunctionAnalysisManager DummyFAM;
  63       ModuleAnalysisManager DummyMAM;
  64       DummyMAM.registerPass(
  65           [&] { return FunctionAnalysisManagerModuleProxy(DummyFAM); });
  66
  67       auto PA = Impl.run(M, DummyMAM);
  68       return !PA.areAllPreserved();
  69     }
  70
  71   private:
  72     GlobalDCEPass Impl;
  73   };
  74 }
  75
  76 char GlobalDCELegacyPass::ID = 0;
  77 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce",
  78                 "Dead Global Elimination", false, false)
  79
  80 // Public interface to the GlobalDCEPass.
  81 ModulePass *llvm::createGlobalDCEPass() {
  82   return new GlobalDCELegacyPass();
  83 }
  84
  85 /// Returns true if F is effectively empty.
  86 static bool isEmptyFunction(Function *F) {
  87   BasicBlock &Entry = F->getEntryBlock();
  88   for (auto &I : Entry) {
  89     if (isa<DbgInfoIntrinsic>(I))
  90       continue;
  91     if (auto *RI = dyn_cast<ReturnInst>(&I))
  92       return !RI->getReturnValue();
  93     break;
  94   }
  95   return false;
  96 }
  97
  98 /// Compute the set of GlobalValue that depends from V.
  99 /// The recursion stops as soon as a GlobalValue is met.
 100 void GlobalDCEPass::ComputeDependencies(Value *V,
 101                                         SmallPtrSetImpl<GlobalValue *> &Deps) {
 102   if (auto *I = dyn_cast<Instruction>(V)) {
 103     Function *Parent = I->getParent()->getParent();
 104     Deps.insert(Parent);
 105   } else if (auto *GV = dyn_cast<GlobalValue>(V)) {
 106     Deps.insert(GV);
 107   } else if (auto *CE = dyn_cast<Constant>(V)) {
 108     // Avoid walking the whole tree of a big ConstantExprs multiple times.
 109     auto Where = ConstantDependenciesCache.find(CE);
 110     if (Where != ConstantDependenciesCache.end()) {
 111       auto const &K = Where->second;
 112       Deps.insert(K.begin(), K.end());
 113     } else {
 114       SmallPtrSetImpl<GlobalValue *> &LocalDeps = ConstantDependenciesCache[CE];
 115       for (User *CEUser : CE->users())
 116         ComputeDependencies(CEUser, LocalDeps);
 117       Deps.insert(LocalDeps.begin(), LocalDeps.end());
 118     }
 119   }
 120 }
 121
 122 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
 123   SmallPtrSet<GlobalValue *, 8> Deps;
 124   for (User *User : GV.users())
 125     ComputeDependencies(User, Deps);
 126   Deps.erase(&GV); // Remove self-reference.
 127   for (GlobalValue *GVU : Deps) {
 128     // If this is a dep from a vtable to a virtual function, and we have
 129     // complete information about all virtual call sites which could call
 130     // though this vtable, then skip it, because the call site information will
 131     // be more precise.
 132     if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
 133       LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
 134                         << GV.getName() << "\n");
 135       continue;
 136     }
 137     GVDependencies[GVU].insert(&GV);
 138   }
 139 }
 140
 141 /// Mark Global value as Live
 142 void GlobalDCEPass::MarkLive(GlobalValue &GV,
 143                              SmallVectorImpl<GlobalValue *> *Updates) {
 144   auto const Ret = AliveGlobals.insert(&GV);
 145   if (!Ret.second)
 146     return;
 147
 148   if (Updates)
 149     Updates->push_back(&GV);
 150   if (Comdat *C = GV.getComdat()) {
 151     for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
 152       MarkLive(*CM.second, Updates); // Recursion depth is only two because only
 153                                      // globals in the same comdat are visited.
 154     }
 155   }
 156 }
 157
 158 void GlobalDCEPass::ScanVTables(Module &M) {
 159   SmallVector<MDNode *, 2> Types;
 160   LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
 161
 162   auto *LTOPostLinkMD =
 163       cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
 164   bool LTOPostLink =
 165       LTOPostLinkMD &&
 166       (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0);
 167
 168   for (GlobalVariable &GV : M.globals()) {
 169     Types.clear();
 170     GV.getMetadata(LLVMContext::MD_type, Types);
 171     if (GV.isDeclaration() || Types.empty())
 172       continue;
 173
 174     // Use the typeid metadata on the vtable to build a mapping from typeids to
 175     // the list of (GV, offset) pairs which are the possible vtables for that
 176     // typeid.
 177     for (MDNode *Type : Types) {
 178       Metadata *TypeID = Type->getOperand(1).get();
 179
 180       uint64_t Offset =
 181           cast<ConstantInt>(
 182               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 183               ->getZExtValue();
 184
 185       TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
 186     }
 187
 188     // If the type corresponding to the vtable is private to this translation
 189     // unit, we know that we can see all virtual functions which might use it,
 190     // so VFE is safe.
 191     if (auto GO = dyn_cast<GlobalObject>(&GV)) {
 192       GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
 193       if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
 194           (LTOPostLink &&
 195            TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
 196         LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
 197         VFESafeVTables.insert(&GV);
 198       }
 199     }
 200   }
 201 }
 202
 203 void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
 204                                    uint64_t CallOffset) {
 205   for (auto &VTableInfo : TypeIdMap[TypeId]) {
 206     GlobalVariable *VTable = VTableInfo.first;
 207     uint64_t VTableOffset = VTableInfo.second;
 208
 209     Constant *Ptr =
 210         getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
 211                            *Caller->getParent());
 212     if (!Ptr) {
 213       LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
 214       VFESafeVTables.erase(VTable);
 215       return;
 216     }
 217
 218     auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
 219     if (!Callee) {
 220       LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
 221       VFESafeVTables.erase(VTable);
 222       return;
 223     }
 224
 225     LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
 226                       << Callee->getName() << "\n");
 227     GVDependencies[Caller].insert(Callee);
 228   }
 229 }
 230
 231 void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {
 232   LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");
 233   Function *TypeCheckedLoadFunc =
 234       M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
 235
 236   if (!TypeCheckedLoadFunc)
 237     return;
 238
 239   for (auto U : TypeCheckedLoadFunc->users()) {
 240     auto CI = dyn_cast<CallInst>(U);
 241     if (!CI)
 242       continue;
 243
 244     auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 245     Value *TypeIdValue = CI->getArgOperand(2);
 246     auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
 247
 248     if (Offset) {
 249       ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
 250     } else {
 251       // type.checked.load with a non-constant offset, so assume every entry in
 252       // every matching vtable is used.
 253       for (auto &VTableInfo : TypeIdMap[TypeId]) {
 254         VFESafeVTables.erase(VTableInfo.first);
 255       }
 256     }
 257   }
 258 }
 259
 260 void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
 261   if (!ClEnableVFE)
 262     return;
 263
 264   ScanVTables(M);
 265
 266   if (VFESafeVTables.empty())
 267     return;
 268
 269   ScanTypeCheckedLoadIntrinsics(M);
 270
 271   LLVM_DEBUG(
 272     dbgs() << "VFE safe vtables:\n";
 273     for (auto *VTable : VFESafeVTables)
 274       dbgs() << "  " << VTable->getName() << "\n";
 275   );
 276 }
 277
 278 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
 279   bool Changed = false;
 280
 281   // The algorithm first computes the set L of global variables that are
 282   // trivially live.  Then it walks the initialization of these variables to
 283   // compute the globals used to initialize them, which effectively builds a
 284   // directed graph where nodes are global variables, and an edge from A to B
 285   // means B is used to initialize A.  Finally, it propagates the liveness
 286   // information through the graph starting from the nodes in L. Nodes note
 287   // marked as alive are discarded.
 288
 289   // Remove empty functions from the global ctors list.
 290   Changed |= optimizeGlobalCtorsList(M, isEmptyFunction);
 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 they
 304   // 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     Changed |= RemoveUnusedGlobalValue(GO);
 310     // Functions with external linkage are needed if they have a body.
 311     // Externally visible & appending globals are needed, if they have an
 312     // 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     Changed |= RemoveUnusedGlobalValue(GA);
 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     Changed |= RemoveUnusedGlobalValue(GIF);
 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 computed
 341   // 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 loop
 351   // 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 globals
 356   for (GlobalVariable &GV : M.globals())
 357     if (!AliveGlobals.count(&GV)) {
 358       DeadGlobalVars.push_back(&GV);         // Keep track of dead globals
 359       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 globals
 372       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 objects
 393   // themselves.
 394   auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {
 395     RemoveUnusedGlobalValue(*GV);
 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 the
 405       // virtual function pointers with null, allowing us to remove the
 406       // function itself.
 407       ++NumVFuncs;
 408       F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
 409     }
 410     EraseUnusedGlobalValue(F);
 411   }
 412
 413   NumVariables += DeadGlobalVars.size();
 414   for (GlobalVariable *GV : DeadGlobalVars)
 415     EraseUnusedGlobalValue(GV);
 416
 417   NumAliases += DeadAliases.size();
 418   for (GlobalAlias *GA : DeadAliases)
 419     EraseUnusedGlobalValue(GA);
 420
 421   NumIFuncs += DeadIFuncs.size();
 422   for (GlobalIFunc *GIF : DeadIFuncs)
 423     EraseUnusedGlobalValue(GIF);
 424
 425   // Make sure that all memory is released
 426   AliveGlobals.clear();
 427   ConstantDependenciesCache.clear();
 428   GVDependencies.clear();
 429   ComdatMembers.clear();
 430   TypeIdMap.clear();
 431   VFESafeVTables.clear();
 432
 433   if (Changed)
 434     return PreservedAnalyses::none();
 435   return PreservedAnalyses::all();
 436 }
 437
 438 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
 439 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
 440 // If found, check to see if the constant pointer ref is safe to destroy, and if
 441 // so, nuke it.  This will reduce the reference count on the global value, which
 442 // might make it deader.
 443 //
 444 bool GlobalDCEPass::RemoveUnusedGlobalValue(GlobalValue &GV) {
 445   if (GV.use_empty())
 446     return false;
 447   GV.removeDeadConstantUsers();
 448   return GV.use_empty();
 449 }