Home | History | Annotate | Download | only in Scalar 
      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 
    136