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