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/DCE.h"
  13 #include "llvm/Pass.h"
  14 #include "llvm/InstrTypes.h"
  15 #include "llvm/Function.h"
  16 #include "llvm/Support/InstIterator.h"
  17 #include <set>
  18
  19 static inline bool isInstDead(Instruction *I) {
  20   return I->use_empty() && !I->hasSideEffects() && !isa<TerminatorInst>(I);
  21 }
  22
  23 // dceInstruction - Inspect the instruction at *BBI and figure out if it's
  24 // [trivially] dead.  If so, remove the instruction and update the iterator
  25 // to point to the instruction that immediately succeeded the original
  26 // instruction.
  27 //
  28 bool dceInstruction(BasicBlock::InstListType &BBIL,
  29                     BasicBlock::iterator &BBI) {
  30   // Look for un"used" definitions...
  31   if (isInstDead(*BBI)) {
  32     delete BBIL.remove(BBI);   // Bye bye
  33     return true;
  34   }
  35   return false;
  36 }
  37
  38 //===----------------------------------------------------------------------===//
  39 // DeadInstElimination pass implementation
  40 //
  41
  42 namespace {
  43   struct DeadInstElimination : public BasicBlockPass {
  44     const char *getPassName() const { return "Dead Instruction Elimination"; }
  45
  46     virtual bool runOnBasicBlock(BasicBlock *BB) {
  47       BasicBlock::InstListType &Vals = BB->getInstList();
  48       bool Changed = false;
  49       for (BasicBlock::iterator DI = Vals.begin(); DI != Vals.end(); )
  50         if (dceInstruction(Vals, DI))
  51           Changed = true;
  52         else
  53           ++DI;
  54       return Changed;
  55     }
  56
  57     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  58       AU.preservesCFG();
  59     }
  60   };
  61 }
  62
  63 Pass *createDeadInstEliminationPass() {
  64   return new DeadInstElimination();
  65 }
  66
  67
  68
  69 //===----------------------------------------------------------------------===//
  70 // DeadCodeElimination pass implementation
  71 //
  72
  73 namespace {
  74   struct DCE : public FunctionPass {
  75     const char *getPassName() const { return "Dead Code Elimination"; }
  76
  77     virtual bool runOnFunction(Function *F);
  78
  79      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  80       AU.preservesCFG();
  81     }
  82  };
  83 }
  84
  85 bool DCE::runOnFunction(Function *F) {
  86   // Start out with all of the instructions in the worklist...
  87   std::vector<Instruction*> WorkList(inst_begin(F), inst_end(F));
  88   std::set<Instruction*> DeadInsts;
  89
  90   // Loop over the worklist finding instructions that are dead.  If they are
  91   // dead make them drop all of their uses, making other instructions
  92   // potentially dead, and work until the worklist is empty.
  93   //
  94   while (!WorkList.empty()) {
  95     Instruction *I = WorkList.back();
  96     WorkList.pop_back();
  97
  98     if (isInstDead(I)) {       // If the instruction is dead...
  99       // Loop over all of the values that the instruction uses, if there are
 100       // instructions being used, add them to the worklist, because they might
 101       // go dead after this one is removed.
 102       //
 103       for (User::use_iterator UI = I->use_begin(), UE = I->use_end();
 104            UI != UE; ++UI)
 105         if (Instruction *Used = dyn_cast<Instruction>(*UI))
 106           WorkList.push_back(Used);
 107
 108       // Tell the instruction to let go of all of the values it uses...
 109       I->dropAllReferences();
 110
 111       // Keep track of this instruction, because we are going to delete it later
 112       DeadInsts.insert(I);
 113     }
 114   }
 115
 116   // If we found no dead instructions, we haven't changed the function...
 117   if (DeadInsts.empty()) return false;
 118
 119   // Otherwise, loop over the program, removing and deleting the instructions...
 120   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
 121     BasicBlock::InstListType &BBIL = (*I)->getInstList();
 122     for (BasicBlock::iterator BI = BBIL.begin(); BI != BBIL.end(); )
 123       if (DeadInsts.count(*BI)) {            // Is this instruction dead?
 124         delete BBIL.remove(BI);              // Yup, remove and delete inst
 125       } else {                               // This instruction is not dead
 126         ++BI;                                // Continue on to the next one...
 127       }
 128   }
 129
 130   return true;
 131 }
 132
 133 Pass *createDeadCodeEliminationPass() {
 134   return new DCE();
 135 }