1193323Sed//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements dead inst elimination and dead code elimination. 11193323Sed// 12193323Sed// Dead Inst Elimination performs a single pass over the function removing 13193323Sed// instructions that are obviously dead. Dead Code Elimination is similar, but 14193323Sed// it rechecks instructions that were used by removed instructions to see if 15193323Sed// they are newly dead. 16193323Sed// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#define DEBUG_TYPE "dce" 20193323Sed#include "llvm/Transforms/Scalar.h" 21249423Sdim#include "llvm/ADT/Statistic.h" 22249423Sdim#include "llvm/IR/Instruction.h" 23193323Sed#include "llvm/Pass.h" 24193323Sed#include "llvm/Support/InstIterator.h" 25243830Sdim#include "llvm/Target/TargetLibraryInfo.h" 26249423Sdim#include "llvm/Transforms/Utils/Local.h" 27193323Sedusing namespace llvm; 28193323Sed 29193323SedSTATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 30193323SedSTATISTIC(DCEEliminated, "Number of insts removed"); 31193323Sed 32193323Sednamespace { 33193323Sed //===--------------------------------------------------------------------===// 34193323Sed // DeadInstElimination pass implementation 35193323Sed // 36198090Srdivacky struct DeadInstElimination : public BasicBlockPass { 37193323Sed static char ID; // Pass identification, replacement for typeid 38218893Sdim DeadInstElimination() : BasicBlockPass(ID) { 39218893Sdim initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry()); 40218893Sdim } 41193323Sed virtual bool runOnBasicBlock(BasicBlock &BB) { 42243830Sdim TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 43193323Sed bool Changed = false; 44193323Sed for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 45193323Sed Instruction *Inst = DI++; 46243830Sdim if (isInstructionTriviallyDead(Inst, TLI)) { 47193323Sed Inst->eraseFromParent(); 48193323Sed Changed = true; 49193323Sed ++DIEEliminated; 50193323Sed } 51193323Sed } 52193323Sed return Changed; 53193323Sed } 54193323Sed 55193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56193323Sed AU.setPreservesCFG(); 57193323Sed } 58193323Sed }; 59193323Sed} 60193323Sed 61193323Sedchar DeadInstElimination::ID = 0; 62212904SdimINITIALIZE_PASS(DeadInstElimination, "die", 63218893Sdim "Dead Instruction Elimination", false, false) 64193323Sed 65193323SedPass *llvm::createDeadInstEliminationPass() { 66193323Sed return new DeadInstElimination(); 67193323Sed} 68193323Sed 69193323Sed 70193323Sednamespace { 71193323Sed //===--------------------------------------------------------------------===// 72193323Sed // DeadCodeElimination pass implementation 73193323Sed // 74193323Sed struct DCE : public FunctionPass { 75193323Sed static char ID; // Pass identification, replacement for typeid 76218893Sdim DCE() : FunctionPass(ID) { 77218893Sdim initializeDCEPass(*PassRegistry::getPassRegistry()); 78218893Sdim } 79193323Sed 80193323Sed virtual bool runOnFunction(Function &F); 81193323Sed 82193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 83193323Sed AU.setPreservesCFG(); 84193323Sed } 85193323Sed }; 86193323Sed} 87193323Sed 88193323Sedchar DCE::ID = 0; 89218893SdimINITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false) 90193323Sed 91193323Sedbool DCE::runOnFunction(Function &F) { 92243830Sdim TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 93243830Sdim 94193323Sed // Start out with all of the instructions in the worklist... 95193323Sed std::vector<Instruction*> WorkList; 96193323Sed for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 97193323Sed WorkList.push_back(&*i); 98193323Sed 99193323Sed // Loop over the worklist finding instructions that are dead. If they are 100193323Sed // dead make them drop all of their uses, making other instructions 101193323Sed // potentially dead, and work until the worklist is empty. 102193323Sed // 103193323Sed bool MadeChange = false; 104193323Sed while (!WorkList.empty()) { 105193323Sed Instruction *I = WorkList.back(); 106193323Sed WorkList.pop_back(); 107193323Sed 108243830Sdim if (isInstructionTriviallyDead(I, TLI)) { // If the instruction is dead. 109193323Sed // Loop over all of the values that the instruction uses, if there are 110193323Sed // instructions being used, add them to the worklist, because they might 111193323Sed // go dead after this one is removed. 112193323Sed // 113193323Sed for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 114193323Sed if (Instruction *Used = dyn_cast<Instruction>(*OI)) 115193323Sed WorkList.push_back(Used); 116193323Sed 117193323Sed // Remove the instruction. 118193323Sed I->eraseFromParent(); 119193323Sed 120193323Sed // Remove the instruction from the worklist if it still exists in it. 121243830Sdim WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I), 122243830Sdim WorkList.end()); 123193323Sed 124193323Sed MadeChange = true; 125193323Sed ++DCEEliminated; 126193323Sed } 127193323Sed } 128193323Sed return MadeChange; 129193323Sed} 130193323Sed 131193323SedFunctionPass *llvm::createDeadCodeEliminationPass() { 132193323Sed return new DCE(); 133193323Sed} 134193323Sed 135