lib/Transforms/Scalar/DCE.cpp

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