1//===- DCE.cpp - Code to perform dead code elimination --------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/ADT/Statistic.h" 22#include "llvm/IR/Instruction.h" 23#include "llvm/Pass.h" 24#include "llvm/Support/InstIterator.h" 25#include "llvm/Target/TargetLibraryInfo.h" 26#include "llvm/Transforms/Utils/Local.h" 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 static char ID; // Pass identification, replacement for typeid 38 DeadInstElimination() : BasicBlockPass(ID) { 39 initializeDeadInstEliminationPass(*PassRegistry::getPassRegistry()); 40 } 41 virtual bool runOnBasicBlock(BasicBlock &BB) { 42 TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 43 bool Changed = false; 44 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 45 Instruction *Inst = DI++; 46 if (isInstructionTriviallyDead(Inst, TLI)) { 47 Inst->eraseFromParent(); 48 Changed = true; 49 ++DIEEliminated; 50 } 51 } 52 return Changed; 53 } 54 55 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56 AU.setPreservesCFG(); 57 } 58 }; 59} 60 61char DeadInstElimination::ID = 0; 62INITIALIZE_PASS(DeadInstElimination, "die", 63 "Dead Instruction Elimination", false, false) 64 65Pass *llvm::createDeadInstEliminationPass() { 66 return new DeadInstElimination(); 67} 68 69 70namespace { 71 //===--------------------------------------------------------------------===// 72 // DeadCodeElimination pass implementation 73 // 74 struct DCE : public FunctionPass { 75 static char ID; // Pass identification, replacement for typeid 76 DCE() : FunctionPass(ID) { 77 initializeDCEPass(*PassRegistry::getPassRegistry()); 78 } 79 80 virtual bool runOnFunction(Function &F); 81 82 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 83 AU.setPreservesCFG(); 84 } 85 }; 86} 87 88char DCE::ID = 0; 89INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false) 90 91bool DCE::runOnFunction(Function &F) { 92 TargetLibraryInfo *TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 93 94 // Start out with all of the instructions in the worklist... 95 std::vector<Instruction*> WorkList; 96 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 97 WorkList.push_back(&*i); 98 99 // Loop over the worklist finding instructions that are dead. If they are 100 // dead make them drop all of their uses, making other instructions 101 // potentially dead, and work until the worklist is empty. 102 // 103 bool MadeChange = false; 104 while (!WorkList.empty()) { 105 Instruction *I = WorkList.back(); 106 WorkList.pop_back(); 107 108 if (isInstructionTriviallyDead(I, TLI)) { // If the instruction is dead. 109 // Loop over all of the values that the instruction uses, if there are 110 // instructions being used, add them to the worklist, because they might 111 // go dead after this one is removed. 112 // 113 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 114 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 115 WorkList.push_back(Used); 116 117 // Remove the instruction. 118 I->eraseFromParent(); 119 120 // Remove the instruction from the worklist if it still exists in it. 121 WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I), 122 WorkList.end()); 123 124 MadeChange = true; 125 ++DCEEliminated; 126 } 127 } 128 return MadeChange; 129} 130 131FunctionPass *llvm::createDeadCodeEliminationPass() { 132 return new DCE(); 133} 134 135