lib/Transforms/Scalar/DCE.cpp

   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 #define DEBUG_TYPE "dce"
  20 #include "llvm/Transforms/Scalar.h"
  21 #include "llvm/Transforms/Utils/Local.h"
  22 #include "llvm/Instruction.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/InstIterator.h"
  25 #include "llvm/ADT/Statistic.h"
  26 using namespace llvm;
  27
  28 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass");
  29 STATISTIC(DCEEliminated, "Number of insts removed");
  30
  31 namespace {
  32   //===--------------------------------------------------------------------===//
  33   // DeadInstElimination pass implementation
  34   //
  35   struct DeadInstElimination : public BasicBlockPass {
  36     static char ID; // Pass identification, replacement for typeid
  37     DeadInstElimination() : BasicBlockPass(ID) {
  38       initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry());
  39     }
  40     virtual bool runOnBasicBlock(BasicBlock &BB) {
  41       bool Changed = false;
  42       for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) {
  43         Instruction *Inst = DI++;
  44         if (isInstructionTriviallyDead(Inst)) {
  45           Inst->eraseFromParent();
  46           Changed = true;
  47           ++DIEEliminated;
  48         }
  49       }
  50       return Changed;
  51     }
  52
  53     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  54       AU.setPreservesCFG();
  55     }
  56   };
  57 }
  58
  59 char DeadInstElimination::ID = 0;
  60 INITIALIZE_PASS(DeadInstElimination, "die",
  61                 "Dead Instruction Elimination", false, false)
  62
  63 Pass *llvm::createDeadInstEliminationPass() {
  64   return new DeadInstElimination();
  65 }
  66
  67
  68 namespace {
  69   //===--------------------------------------------------------------------===//
  70   // DeadCodeElimination pass implementation
  71   //
  72   struct DCE : public FunctionPass {
  73     static char ID; // Pass identification, replacement for typeid
  74     DCE() : FunctionPass(ID) {
  75       initializeDCEPass(*PassRegistry::getPassRegistry());
  76     }
  77
  78     virtual bool runOnFunction(Function &F);
  79
  80      virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  81       AU.setPreservesCFG();
  82     }
  83  };
  84 }
  85
  86 char DCE::ID = 0;
  87 INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false)
  88
  89 bool DCE::runOnFunction(Function &F) {
  90   // Start out with all of the instructions in the worklist...
  91   std::vector<Instruction*> WorkList;
  92   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)
  93     WorkList.push_back(&*i);
  94
  95   // Loop over the worklist finding instructions that are dead.  If they are
  96   // dead make them drop all of their uses, making other instructions
  97   // potentially dead, and work until the worklist is empty.
  98   //
  99   bool MadeChange = false;
 100   while (!WorkList.empty()) {
 101     Instruction *I = WorkList.back();
 102     WorkList.pop_back();
 103
 104     if (isInstructionTriviallyDead(I)) {       // If the instruction is dead.
 105       // Loop over all of the values that the instruction uses, if there are
 106       // instructions being used, add them to the worklist, because they might
 107       // go dead after this one is removed.
 108       //
 109       for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
 110         if (Instruction *Used = dyn_cast<Instruction>(*OI))
 111           WorkList.push_back(Used);
 112
 113       // Remove the instruction.
 114       I->eraseFromParent();
 115
 116       // Remove the instruction from the worklist if it still exists in it.
 117       for (std::vector<Instruction*>::iterator WI = WorkList.begin();
 118            WI != WorkList.end(); ) {
 119         if (*WI == I)
 120           WI = WorkList.erase(WI);
 121         else
 122           ++WI;
 123       }
 124
 125       MadeChange = true;
 126       ++DCEEliminated;
 127     }
 128   }
 129   return MadeChange;
 130 }
 131
 132 FunctionPass *llvm::createDeadCodeEliminationPass() {
 133   return new DCE();
 134 }
 135