Home | History | Annotate | Download | only in Scalar 
      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(); }
    183