DCE.cpp revision a92f696b74a99325026ebbdbffd2a44317e0c10b 
1//===- DCE.cpp - Code to perform dead code elimination --------------------===//
2//
3// This file implements dead inst elimination and dead code elimination.
4//
5// Dead Inst Elimination performs a single pass over the function removing
6// instructions that are obviously dead.  Dead Code Elimination is similar, but
7// it rechecks instructions that were used by removed instructions to see if
8// they are newly dead.
9//
10//===----------------------------------------------------------------------===//
11
12#include "llvm/Transforms/Scalar.h"
13#include "llvm/Transforms/Utils/Local.h"
14#include "llvm/Instruction.h"
15#include "llvm/Pass.h"
16#include "llvm/Support/InstIterator.h"
17#include "Support/Statistic.h"
18#include <set>
19
20namespace {
21  Statistic<> DIEEliminated("die", "Number of insts removed");
22  Statistic<> DCEEliminated("dce", "Number of insts removed");
23
24  //===--------------------------------------------------------------------===//
25  // DeadInstElimination pass implementation
26  //
27
28  struct DeadInstElimination : public BasicBlockPass {
29    virtual bool runOnBasicBlock(BasicBlock &BB) {
30      bool Changed = false;
31      for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); )
32        if (dceInstruction(DI)) {
33          Changed = true;
34          ++DIEEliminated;
35        } else
36          ++DI;
37      return Changed;
38    }
39
40    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
41      AU.preservesCFG();
42    }
43  };
44
45  RegisterOpt<DeadInstElimination> X("die", "Dead Instruction Elimination");
46}
47
48Pass *createDeadInstEliminationPass() {
49  return new DeadInstElimination();
50}
51
52
53
54//===----------------------------------------------------------------------===//
55// DeadCodeElimination pass implementation
56//
57
58namespace {
59  struct DCE : public FunctionPass {
60    virtual bool runOnFunction(Function &F);
61
62     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
63      AU.preservesCFG();
64    }
65 };
66
67  RegisterOpt<DCE> Y("dce", "Dead Code Elimination");
68}
69
70bool DCE::runOnFunction(Function &F) {
71  // Start out with all of the instructions in the worklist...
72  std::vector<Instruction*> WorkList(inst_begin(F), inst_end(F));
73  std::set<Instruction*> DeadInsts;
74
75  // Loop over the worklist finding instructions that are dead.  If they are
76  // dead make them drop all of their uses, making other instructions
77  // potentially dead, and work until the worklist is empty.
78  //
79  while (!WorkList.empty()) {
80    Instruction *I = WorkList.back();
81    WorkList.pop_back();
82
83    if (isInstructionTriviallyDead(I)) {       // If the instruction is dead...
84      // Loop over all of the values that the instruction uses, if there are
85      // instructions being used, add them to the worklist, because they might
86      // go dead after this one is removed.
87      //
88      for (User::use_iterator UI = I->use_begin(), UE = I->use_end();
89           UI != UE; ++UI)
90        if (Instruction *Used = dyn_cast<Instruction>(*UI))
91          WorkList.push_back(Used);
92
93      // Tell the instruction to let go of all of the values it uses...
94      I->dropAllReferences();
95
96      // Keep track of this instruction, because we are going to delete it later
97      DeadInsts.insert(I);
98    }
99  }
100
101  // If we found no dead instructions, we haven't changed the function...
102  if (DeadInsts.empty()) return false;
103
104  // Otherwise, loop over the program, removing and deleting the instructions...
105  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
106    for (BasicBlock::iterator BI = I->begin(); BI != I->end(); )
107      if (DeadInsts.count(BI)) {             // Is this instruction dead?
108        BI = I->getInstList().erase(BI);     // Yup, remove and delete inst
109        ++DCEEliminated;
110      } else {                               // This instruction is not dead
111        ++BI;                                // Continue on to the next one...
112      }
113
114  return true;
115}
116
117Pass *createDeadCodeEliminationPass() {
118  return new DCE();
119}
120