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