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