Home | History | Annotate | Download | only in Scalar 
      1 //===- DCE.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 dead inst elimination and dead code elimination.
     11 //
     12 // Dead Inst Elimination performs a single pass over the function removing
     13 // instructions that are obviously dead.  Dead Code Elimination is similar, but
     14 // it rechecks instructions that were used by removed instructions to see if
     15 // they are newly dead.
     16 //
     17 //===----------------------------------------------------------------------===//
     18 
     19 #include "llvm/Transforms/Scalar/DCE.h"
     20 #include "llvm/ADT/SetVector.h"
     21 #include "llvm/ADT/Statistic.h"
     22 #include "llvm/IR/InstIterator.h"
     23 #include "llvm/IR/Instruction.h"
     24 #include "llvm/Pass.h"
     25 #include "llvm/Analysis/TargetLibraryInfo.h"
     26 #include "llvm/Transforms/Scalar.h"
     27 #include "llvm/Transforms/Utils/Local.h"
     28 using namespace llvm;
     29 
     30 #define DEBUG_TYPE "dce"
     31 
     32 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
     33 STATISTIC(DCEEliminated, "Number of insts removed");
     34 
     35 namespace {
     36   //===--------------------------------------------------------------------===//
     37   // DeadInstElimination pass implementation
     38   //
     39   struct DeadInstElimination : public BasicBlockPass {
     40     static char ID; // Pass identification, replacement for typeid
     41     DeadInstElimination() : BasicBlockPass(ID) {
     42       initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
     43     }
     44     bool runOnBasicBlock(BasicBlock &BB) override {
     45       if (skipBasicBlock(BB))
     46         return false;
     47       auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
     48       TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
     49       bool Changed = false;
     50       for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
     51         Instruction *Inst = &*DI++;
     52         if (isInstructionTriviallyDead(Inst, TLI)) {
     53           Inst->eraseFromParent();
     54           Changed = true;
     55           ++DIEEliminated;
     56         }
     57       }
     58       return Changed;
     59     }
     60 
     61     void getAnalysisUsage(AnalysisUsage &AU) const override {
     62       AU.setPreservesCFG();
     63     }
     64   };
     65 }
     66 
     67 char DeadInstElimination::ID = 0;
     68 INITIALIZE_PASS(DeadInstElimination, "die",
     69                 "Dead Instruction Elimination", false, false)
     70 
     71 Pass *llvm::createDeadInstEliminationPass() {
     72   return new DeadInstElimination();
     73 }
     74 
     75 static bool DCEInstruction(Instruction *I,
     76                            SmallSetVector<Instruction *, 16> &WorkList,
     77                            const TargetLibraryInfo *TLI) {
     78   if (isInstructionTriviallyDead(I, TLI)) {
     79     // Null out all of the instruction's operands to see if any operand becomes
     80     // dead as we go.
     81     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
     82       Value *OpV = I->getOperand(i);
     83       I->setOperand(i, nullptr);
     84 
     85       if (!OpV->use_empty() || I == OpV)
     86         continue;
     87 
     88       // If the operand is an instruction that became dead as we nulled out the
     89       // operand, and if it is 'trivially' dead, delete it in a future loop
     90       // iteration.
     91       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
     92         if (isInstructionTriviallyDead(OpI, TLI))
     93           WorkList.insert(OpI);
     94     }
     95 
     96     I->eraseFromParent();
     97     ++DCEEliminated;
     98     return true;
     99   }
    100   return false;
    101 }
    102 
    103 static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
    104   bool MadeChange = false;
    105   SmallSetVector<Instruction *, 16> WorkList;
    106   // Iterate over the original function, only adding insts to the worklist
    107   // if they actually need to be revisited. This avoids having to pre-init
    108   // the worklist with the entire function's worth of instructions.
    109   for (inst_iterator FI = inst_begin(F), FE = inst_end(F); FI != FE;) {
    110     Instruction *I = &*FI;
    111     ++FI;
    112 
    113     // We're visiting this instruction now, so make sure it's not in the
    114     // worklist from an earlier visit.
    115     if (!WorkList.count(I))
    116       MadeChange |= DCEInstruction(I, WorkList, TLI);
    117   }
    118 
    119   while (!WorkList.empty()) {
    120     Instruction *I = WorkList.pop_back_val();
    121     MadeChange |= DCEInstruction(I, WorkList, TLI);
    122   }
    123   return MadeChange;
    124 }
    125 
    126 PreservedAnalyses DCEPass::run(Function &F, AnalysisManager<Function> &AM) {
    127   if (eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
    128     return PreservedAnalyses::none();
    129   return PreservedAnalyses::all();
    130 }
    131 
    132 namespace {
    133 struct DCELegacyPass : public FunctionPass {
    134   static char ID; // Pass identification, replacement for typeid
    135   DCELegacyPass() : FunctionPass(ID) {
    136     initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
    137   }
    138 
    139   bool runOnFunction(Function &F) override {
    140     if (skipFunction(F))
    141       return false;
    142 
    143     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
    144     TargetLibraryInfo *TLI = TLIP ? &TLIP->getTLI() : nullptr;
    145 
    146     return eliminateDeadCode(F, TLI);
    147   }
    148 
    149   void getAnalysisUsage(AnalysisUsage &AU) const override {
    150     AU.setPreservesCFG();
    151   }
    152 };
    153 }
    154 
    155 char DCELegacyPass::ID = 0;
    156 INITIALIZE_PASS(DCELegacyPass, "dce", "Dead Code Elimination", false, false)
    157 
    158 FunctionPass *llvm::createDeadCodeEliminationPass() {
    159   return new DCELegacyPass();
    160 }
    161