contrib/llvm/lib/Transforms/Scalar/ADCE.cpp

   1 //===- ADCE.cpp - Code to perform dead code elimination -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Aggressive Dead Code Elimination pass.  This pass
  11 // optimistically assumes that all instructions are dead until proven otherwise,
  12 // allowing it to eliminate dead computations that other DCE passes do not
  13 // catch, particularly involving loop computations.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Scalar/ADCE.h"
  18 #include "llvm/ADT/DepthFirstIterator.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Analysis/GlobalsModRef.h"
  23 #include "llvm/IR/BasicBlock.h"
  24 #include "llvm/IR/CFG.h"
  25 #include "llvm/IR/DebugInfoMetadata.h"
  26 #include "llvm/IR/InstIterator.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/ProfileData/InstrProf.h"
  31 #include "llvm/Transforms/Scalar.h"
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "adce"
  35
  36 STATISTIC(NumRemoved, "Number of instructions removed");
  37
  38 static void collectLiveScopes(const DILocalScope &LS,
  39                               SmallPtrSetImpl<const Metadata *> &AliveScopes) {
  40   if (!AliveScopes.insert(&LS).second)
  41     return;
  42
  43   if (isa<DISubprogram>(LS))
  44     return;
  45
  46   // Tail-recurse through the scope chain.
  47   collectLiveScopes(cast<DILocalScope>(*LS.getScope()), AliveScopes);
  48 }
  49
  50 static void collectLiveScopes(const DILocation &DL,
  51                               SmallPtrSetImpl<const Metadata *> &AliveScopes) {
  52   // Even though DILocations are not scopes, shove them into AliveScopes so we
  53   // don't revisit them.
  54   if (!AliveScopes.insert(&DL).second)
  55     return;
  56
  57   // Collect live scopes from the scope chain.
  58   collectLiveScopes(*DL.getScope(), AliveScopes);
  59
  60   // Tail-recurse through the inlined-at chain.
  61   if (const DILocation *IA = DL.getInlinedAt())
  62     collectLiveScopes(*IA, AliveScopes);
  63 }
  64
  65 // Check if this instruction is a runtime call for value profiling and
  66 // if it's instrumenting a constant.
  67 static bool isInstrumentsConstant(Instruction &I) {
  68   if (CallInst *CI = dyn_cast<CallInst>(&I))
  69     if (Function *Callee = CI->getCalledFunction())
  70       if (Callee->getName().equals(getInstrProfValueProfFuncName()))
  71         if (isa<Constant>(CI->getArgOperand(0)))
  72           return true;
  73   return false;
  74 }
  75
  76 static bool aggressiveDCE(Function& F) {
  77   SmallPtrSet<Instruction*, 32> Alive;
  78   SmallVector<Instruction*, 128> Worklist;
  79
  80   // Collect the set of "root" instructions that are known live.
  81   for (Instruction &I : instructions(F)) {
  82     if (isa<TerminatorInst>(I) || I.isEHPad() || I.mayHaveSideEffects()) {
  83       // Skip any value profile instrumentation calls if they are
  84       // instrumenting constants.
  85       if (isInstrumentsConstant(I))
  86         continue;
  87       Alive.insert(&I);
  88       Worklist.push_back(&I);
  89     }
  90   }
  91
  92   // Propagate liveness backwards to operands.  Keep track of live debug info
  93   // scopes.
  94   SmallPtrSet<const Metadata *, 32> AliveScopes;
  95   while (!Worklist.empty()) {
  96     Instruction *Curr = Worklist.pop_back_val();
  97
  98     // Collect the live debug info scopes attached to this instruction.
  99     if (const DILocation *DL = Curr->getDebugLoc())
 100       collectLiveScopes(*DL, AliveScopes);
 101
 102     for (Use &OI : Curr->operands()) {
 103       if (Instruction *Inst = dyn_cast<Instruction>(OI))
 104         if (Alive.insert(Inst).second)
 105           Worklist.push_back(Inst);
 106     }
 107   }
 108
 109   // The inverse of the live set is the dead set.  These are those instructions
 110   // which have no side effects and do not influence the control flow or return
 111   // value of the function, and may therefore be deleted safely.
 112   // NOTE: We reuse the Worklist vector here for memory efficiency.
 113   for (Instruction &I : instructions(F)) {
 114     // Check if the instruction is alive.
 115     if (Alive.count(&I))
 116       continue;
 117
 118     if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
 119       // Check if the scope of this variable location is alive.
 120       if (AliveScopes.count(DII->getDebugLoc()->getScope()))
 121         continue;
 122
 123       // Fallthrough and drop the intrinsic.
 124       DEBUG({
 125         // If intrinsic is pointing at a live SSA value, there may be an
 126         // earlier optimization bug: if we know the location of the variable,
 127         // why isn't the scope of the location alive?
 128         if (Value *V = DII->getVariableLocation())
 129           if (Instruction *II = dyn_cast<Instruction>(V))
 130             if (Alive.count(II))
 131               dbgs() << "Dropping debug info for " << *DII << "\n";
 132       });
 133     }
 134
 135     // Prepare to delete.
 136     Worklist.push_back(&I);
 137     I.dropAllReferences();
 138   }
 139
 140   for (Instruction *&I : Worklist) {
 141     ++NumRemoved;
 142     I->eraseFromParent();
 143   }
 144
 145   return !Worklist.empty();
 146 }
 147
 148 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &) {
 149   if (!aggressiveDCE(F))
 150     return PreservedAnalyses::all();
 151
 152   // FIXME: This should also 'preserve the CFG'.
 153   auto PA = PreservedAnalyses();
 154   PA.preserve<GlobalsAA>();
 155   return PA;
 156 }
 157
 158 namespace {
 159 struct ADCELegacyPass : public FunctionPass {
 160   static char ID; // Pass identification, replacement for typeid
 161   ADCELegacyPass() : FunctionPass(ID) {
 162     initializeADCELegacyPassPass(*PassRegistry::getPassRegistry());
 163   }
 164
 165   bool runOnFunction(Function& F) override {
 166     if (skipFunction(F))
 167       return false;
 168     return aggressiveDCE(F);
 169   }
 170
 171   void getAnalysisUsage(AnalysisUsage& AU) const override {
 172     AU.setPreservesCFG();
 173     AU.addPreserved<GlobalsAAWrapperPass>();
 174   }
 175 };
 176 }
 177
 178 char ADCELegacyPass::ID = 0;
 179 INITIALIZE_PASS(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
 180                 false, false)
 181
 182 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }