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