DCE.cpp revision 218893
1309124Sdim//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2234285Sdim// 3353358Sdim// The LLVM Compiler Infrastructure 4353358Sdim// 5353358Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file implements dead inst elimination and dead code elimination. 11234285Sdim// 12314564Sdim// Dead Inst Elimination performs a single pass over the function removing 13309124Sdim// instructions that are obviously dead. Dead Code Elimination is similar, but 14234285Sdim// it rechecks instructions that were used by removed instructions to see if 15234285Sdim// they are newly dead. 16314564Sdim// 17314564Sdim//===----------------------------------------------------------------------===// 18314564Sdim 19321369Sdim#define DEBUG_TYPE "dce" 20249423Sdim#include "llvm/Transforms/Scalar.h" 21249423Sdim#include "llvm/Transforms/Utils/Local.h" 22314564Sdim#include "llvm/Instruction.h" 23314564Sdim#include "llvm/Pass.h" 24249423Sdim#include "llvm/Support/InstIterator.h" 25314564Sdim#include "llvm/ADT/Statistic.h" 26234285Sdim#include <set> 27314564Sdimusing namespace llvm; 28314564Sdim 29249423SdimSTATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 30314564SdimSTATISTIC(DCEEliminated, "Number of insts removed"); 31314564Sdim 32314564Sdimnamespace { 33234285Sdim //===--------------------------------------------------------------------===// 34234285Sdim // DeadInstElimination pass implementation 35234285Sdim // 36309124Sdim struct DeadInstElimination : public BasicBlockPass { 37309124Sdim static char ID; // Pass identification, replacement for typeid 38309124Sdim DeadInstElimination() : BasicBlockPass(ID) { 39234285Sdim initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry()); 40309124Sdim } 41309124Sdim virtual bool runOnBasicBlock(BasicBlock &BB) { 42309124Sdim bool Changed = false; 43309124Sdim for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 44309124Sdim Instruction *Inst = DI++; 45309124Sdim if (isInstructionTriviallyDead(Inst)) { 46309124Sdim Inst->eraseFromParent(); 47309124Sdim Changed = true; 48309124Sdim ++DIEEliminated; 49309124Sdim } 50309124Sdim } 51321369Sdim return Changed; 52321369Sdim } 53321369Sdim 54321369Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55321369Sdim AU.setPreservesCFG(); 56321369Sdim } 57321369Sdim }; 58321369Sdim} 59309124Sdim 60309124Sdimchar DeadInstElimination::ID = 0; 61309124SdimINITIALIZE_PASS(DeadInstElimination, "die", 62309124Sdim "Dead Instruction Elimination", false, false) 63309124Sdim 64314564SdimPass *llvm::createDeadInstEliminationPass() { 65314564Sdim return new DeadInstElimination(); 66314564Sdim} 67314564Sdim 68314564Sdim 69314564Sdimnamespace { 70309124Sdim //===--------------------------------------------------------------------===// 71314564Sdim // DeadCodeElimination pass implementation 72314564Sdim // 73314564Sdim struct DCE : public FunctionPass { 74314564Sdim static char ID; // Pass identification, replacement for typeid 75314564Sdim DCE() : FunctionPass(ID) { 76341825Sdim initializeDCEPass(*PassRegistry::getPassRegistry()); 77314564Sdim } 78314564Sdim 79309124Sdim virtual bool runOnFunction(Function &F); 80309124Sdim 81309124Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 82309124Sdim AU.setPreservesCFG(); 83309124Sdim } 84309124Sdim }; 85309124Sdim} 86309124Sdim 87309124Sdimchar DCE::ID = 0; 88309124SdimINITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false) 89309124Sdim 90309124Sdimbool DCE::runOnFunction(Function &F) { 91309124Sdim // Start out with all of the instructions in the worklist... 92309124Sdim std::vector<Instruction*> WorkList; 93309124Sdim for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 94309124Sdim WorkList.push_back(&*i); 95309124Sdim 96309124Sdim // Loop over the worklist finding instructions that are dead. If they are 97309124Sdim // dead make them drop all of their uses, making other instructions 98309124Sdim // potentially dead, and work until the worklist is empty. 99309124Sdim // 100309124Sdim bool MadeChange = false; 101309124Sdim while (!WorkList.empty()) { 102309124Sdim Instruction *I = WorkList.back(); 103309124Sdim WorkList.pop_back(); 104309124Sdim 105309124Sdim if (isInstructionTriviallyDead(I)) { // If the instruction is dead. 106309124Sdim // Loop over all of the values that the instruction uses, if there are 107309124Sdim // instructions being used, add them to the worklist, because they might 108309124Sdim // go dead after this one is removed. 109309124Sdim // 110309124Sdim for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 111309124Sdim if (Instruction *Used = dyn_cast<Instruction>(*OI)) 112234285Sdim WorkList.push_back(Used); 113309124Sdim 114234285Sdim // Remove the instruction. 115280031Sdim I->eraseFromParent(); 116234285Sdim 117309124Sdim // Remove the instruction from the worklist if it still exists in it. 118309124Sdim for (std::vector<Instruction*>::iterator WI = WorkList.begin(); 119309124Sdim WI != WorkList.end(); ) { 120309124Sdim if (*WI == I) 121309124Sdim WI = WorkList.erase(WI); 122309124Sdim else 123309124Sdim ++WI; 124309124Sdim } 125234285Sdim 126234285Sdim MadeChange = true; 127309124Sdim ++DCEEliminated; 128314564Sdim } 129314564Sdim } 130314564Sdim return MadeChange; 131309124Sdim} 132314564Sdim 133314564SdimFunctionPass *llvm::createDeadCodeEliminationPass() { 134314564Sdim return new DCE(); 135314564Sdim} 136314564Sdim 137314564Sdim