DCE.cpp revision 0e5f499638c8d277b9dc4a4385712177c53b5681
1//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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#include <set> 27using namespace llvm; 28 29STATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 30STATISTIC(DCEEliminated, "Number of insts removed"); 31 32namespace { 33 //===--------------------------------------------------------------------===// 34 // DeadInstElimination pass implementation 35 // 36 struct DeadInstElimination : public BasicBlockPass { 37 virtual bool runOnBasicBlock(BasicBlock &BB) { 38 bool Changed = false; 39 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) 40 if (dceInstruction(DI)) { 41 Changed = true; 42 ++DIEEliminated; 43 } else 44 ++DI; 45 return Changed; 46 } 47 48 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 49 AU.setPreservesCFG(); 50 } 51 }; 52 53 RegisterPass<DeadInstElimination> X("die", "Dead Instruction Elimination"); 54} 55 56FunctionPass *llvm::createDeadInstEliminationPass() { 57 return new DeadInstElimination(); 58} 59 60 61namespace { 62 //===--------------------------------------------------------------------===// 63 // DeadCodeElimination pass implementation 64 // 65 struct DCE : public FunctionPass { 66 virtual bool runOnFunction(Function &F); 67 68 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 69 AU.setPreservesCFG(); 70 } 71 }; 72 73 RegisterPass<DCE> Y("dce", "Dead Code Elimination"); 74} 75 76bool DCE::runOnFunction(Function &F) { 77 // Start out with all of the instructions in the worklist... 78 std::vector<Instruction*> WorkList; 79 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 80 WorkList.push_back(&*i); 81 82 // Loop over the worklist finding instructions that are dead. If they are 83 // dead make them drop all of their uses, making other instructions 84 // potentially dead, and work until the worklist is empty. 85 // 86 bool MadeChange = false; 87 while (!WorkList.empty()) { 88 Instruction *I = WorkList.back(); 89 WorkList.pop_back(); 90 91 if (isInstructionTriviallyDead(I)) { // If the instruction is dead. 92 // Loop over all of the values that the instruction uses, if there are 93 // instructions being used, add them to the worklist, because they might 94 // go dead after this one is removed. 95 // 96 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 97 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 98 WorkList.push_back(Used); 99 100 // Remove the instruction. 101 I->eraseFromParent(); 102 103 // Remove the instruction from the worklist if it still exists in it. 104 for (std::vector<Instruction*>::iterator WI = WorkList.begin(), 105 E = WorkList.end(); WI != E; ++WI) 106 if (*WI == I) { 107 WorkList.erase(WI); 108 --E; 109 --WI; 110 } 111 112 MadeChange = true; 113 ++DCEEliminated; 114 } 115 } 116 return MadeChange; 117} 118 119FunctionPass *llvm::createDeadCodeEliminationPass() { 120 return new DCE(); 121} 122 123