lib/Transforms/Scalar/DCE.cpp

   1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
   2 //
   3 // This file implements dead inst elimination and dead code elimination.
   4 //
   5 // Dead Inst Elimination performs a single pass over the function removing
   6 // instructions that are obviously dead.  Dead Code Elimination is similar, but
   7 // it rechecks instructions that were used by removed instructions to see if
   8 // they are newly dead.
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Transforms/Scalar.h"
  13 #include "llvm/Transforms/Utils/Local.h"
  14 #include "llvm/Instruction.h"
  15 #include "llvm/Pass.h"
  16 #include "llvm/Support/InstIterator.h"
  17 #include "Support/StatisticReporter.h"
  18 #include <set>
  19
  20 static Statistic<> DIEEliminated("die\t\t- Number of insts removed");
  21 static Statistic<> DCEEliminated("dce\t\t- Number of insts removed");
  22
  23 //===----------------------------------------------------------------------===//
  24 // DeadInstElimination pass implementation
  25 //
  26
  27 namespace {
  28   struct DeadInstElimination : public BasicBlockPass {
  29     virtual bool runOnBasicBlock(BasicBlock &BB) {
  30       bool Changed = false;
  31       for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); )
  32         if (dceInstruction(DI)) {
  33           Changed = true;
  34           ++DIEEliminated;
  35         } else
  36           ++DI;
  37       return Changed;
  38     }
  39
  40     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  41       AU.preservesCFG();
  42     }
  43   };
  44
  45   RegisterOpt<DeadInstElimination> X("die", "Dead Instruction Elimination");
  46 }
  47
  48 Pass *createDeadInstEliminationPass() {
  49   return new DeadInstElimination();
  50 }
  51
  52
  53
  54 //===----------------------------------------------------------------------===//
  55 // DeadCodeElimination pass implementation
  56 //
  57
  58 namespace {
  59   struct DCE : public FunctionPass {
  60     virtual bool runOnFunction(Function &F);
  61
  62      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  63       AU.preservesCFG();
  64     }
  65  };
  66
  67   RegisterOpt<DCE> Y("dce", "Dead Code Elimination");
  68 }
  69
  70 bool DCE::runOnFunction(Function &F) {
  71   // Start out with all of the instructions in the worklist...
  72   std::vector<Instruction*> WorkList(inst_begin(F), inst_end(F));
  73   std::set<Instruction*> DeadInsts;
  74
  75   // Loop over the worklist finding instructions that are dead.  If they are
  76   // dead make them drop all of their uses, making other instructions
  77   // potentially dead, and work until the worklist is empty.
  78   //
  79   while (!WorkList.empty()) {
  80     Instruction *I = WorkList.back();
  81     WorkList.pop_back();
  82
  83     if (isInstructionTriviallyDead(I)) {       // If the instruction is dead...
  84       // Loop over all of the values that the instruction uses, if there are
  85       // instructions being used, add them to the worklist, because they might
  86       // go dead after this one is removed.
  87       //
  88       for (User::use_iterator UI = I->use_begin(), UE = I->use_end();
  89            UI != UE; ++UI)
  90         if (Instruction *Used = dyn_cast<Instruction>(*UI))
  91           WorkList.push_back(Used);
  92
  93       // Tell the instruction to let go of all of the values it uses...
  94       I->dropAllReferences();
  95
  96       // Keep track of this instruction, because we are going to delete it later
  97       DeadInsts.insert(I);
  98     }
  99   }
 100
 101   // If we found no dead instructions, we haven't changed the function...
 102   if (DeadInsts.empty()) return false;
 103
 104   // Otherwise, loop over the program, removing and deleting the instructions...
 105   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 106     for (BasicBlock::iterator BI = I->begin(); BI != I->end(); )
 107       if (DeadInsts.count(BI)) {             // Is this instruction dead?
 108         BI = I->getInstList().erase(BI);     // Yup, remove and delete inst
 109         ++DCEEliminated;
 110       } else {                               // This instruction is not dead
 111         ++BI;                                // Continue on to the next one...
 112       }
 113
 114   return true;
 115 }
 116
 117 Pass *createDeadCodeEliminationPass() {
 118   return new DCE();
 119 }