DCE.cpp revision 96d4bf7aee0c6ce915e6eb77065df388f374fafb
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#include "llvm/Transforms/Scalar.h" 20#include "llvm/Transforms/Utils/Local.h" 21#include "llvm/Instruction.h" 22#include "llvm/Pass.h" 23#include "llvm/Support/InstIterator.h" 24#include "Support/Statistic.h" 25#include <set> 26using namespace llvm; 27 28namespace { 29 Statistic<> DIEEliminated("die", "Number of insts removed"); 30 Statistic<> DCEEliminated("dce", "Number of insts removed"); 31 32 //===--------------------------------------------------------------------===// 33 // DeadInstElimination pass implementation 34 // 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 RegisterOpt<DeadInstElimination> X("die", "Dead Instruction Elimination"); 54} 55 56Pass *llvm::createDeadInstEliminationPass() { 57 return new DeadInstElimination(); 58} 59 60 61//===----------------------------------------------------------------------===// 62// DeadCodeElimination pass implementation 63// 64 65namespace { 66 struct DCE : public FunctionPass { 67 virtual bool runOnFunction(Function &F); 68 69 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 70 AU.setPreservesCFG(); 71 } 72 }; 73 74 RegisterOpt<DCE> Y("dce", "Dead Code Elimination"); 75} 76 77bool DCE::runOnFunction(Function &F) { 78 // Start out with all of the instructions in the worklist... 79 std::vector<Instruction*> WorkList; 80 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { 81 WorkList.push_back(&*i); 82 } 83 std::set<Instruction*> DeadInsts; 84 85 // Loop over the worklist finding instructions that are dead. If they are 86 // dead make them drop all of their uses, making other instructions 87 // potentially dead, and work until the worklist is empty. 88 // 89 while (!WorkList.empty()) { 90 Instruction *I = WorkList.back(); 91 WorkList.pop_back(); 92 93 if (isInstructionTriviallyDead(I)) { // If the instruction is dead... 94 // Loop over all of the values that the instruction uses, if there are 95 // instructions being used, add them to the worklist, because they might 96 // go dead after this one is removed. 97 // 98 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 99 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 100 WorkList.push_back(Used); 101 102 // Tell the instruction to let go of all of the values it uses... 103 I->dropAllReferences(); 104 105 // Keep track of this instruction, because we are going to delete it later 106 DeadInsts.insert(I); 107 } 108 } 109 110 // If we found no dead instructions, we haven't changed the function... 111 if (DeadInsts.empty()) return false; 112 113 // Otherwise, loop over the program, removing and deleting the instructions... 114 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 115 for (BasicBlock::iterator BI = I->begin(); BI != I->end(); ) 116 if (DeadInsts.count(BI)) { // Is this instruction dead? 117 BI = I->getInstList().erase(BI); // Yup, remove and delete inst 118 ++DCEEliminated; 119 } else { // This instruction is not dead 120 ++BI; // Continue on to the next one... 121 } 122 123 return true; 124} 125 126FunctionPass *llvm::createDeadCodeEliminationPass() { 127 return new DCE(); 128} 129 130