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