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/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> 27 using namespace llvm; 28 29 STATISTIC(DIEEliminated, "Number of insts removed by DIE pass"); 30 STATISTIC(DCEEliminated, "Number of insts removed"); 31 32 namespace { 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 bool Changed = false; 43 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) { 44 Instruction *Inst = DI++; 45 if (isInstructionTriviallyDead(Inst)) { 46 Inst->eraseFromParent(); 47 Changed = true; 48 ++DIEEliminated; 49 } 50 } 51 return Changed; 52 } 53 54 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55 AU.setPreservesCFG(); 56 } 57 }; 58 } 59 60 char DeadInstElimination::ID = 0; 61 INITIALIZE_PASS(DeadInstElimination, "die", 62 "Dead Instruction Elimination", false, false) 63 64 Pass *llvm::createDeadInstEliminationPass() { 65 return new DeadInstElimination(); 66 } 67 68 69 namespace { 70 //===--------------------------------------------------------------------===// 71 // DeadCodeElimination pass implementation 72 // 73 struct DCE : public FunctionPass { 74 static char ID; // Pass identification, replacement for typeid 75 DCE() : FunctionPass(ID) { 76 initializeDCEPass(*PassRegistry::getPassRegistry()); 77 } 78 79 virtual bool runOnFunction(Function &F); 80 81 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 82 AU.setPreservesCFG(); 83 } 84 }; 85 } 86 87 char DCE::ID = 0; 88 INITIALIZE_PASS(DCE, "dce", "Dead Code Elimination", false, false) 89 90 bool DCE::runOnFunction(Function &F) { 91 // Start out with all of the instructions in the worklist... 92 std::vector<Instruction*> WorkList; 93 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) 94 WorkList.push_back(&*i); 95 96 // Loop over the worklist finding instructions that are dead. If they are 97 // dead make them drop all of their uses, making other instructions 98 // potentially dead, and work until the worklist is empty. 99 // 100 bool MadeChange = false; 101 while (!WorkList.empty()) { 102 Instruction *I = WorkList.back(); 103 WorkList.pop_back(); 104 105 if (isInstructionTriviallyDead(I)) { // If the instruction is dead. 106 // Loop over all of the values that the instruction uses, if there are 107 // instructions being used, add them to the worklist, because they might 108 // go dead after this one is removed. 109 // 110 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 111 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 112 WorkList.push_back(Used); 113 114 // Remove the instruction. 115 I->eraseFromParent(); 116 117 // Remove the instruction from the worklist if it still exists in it. 118 for (std::vector<Instruction*>::iterator WI = WorkList.begin(); 119 WI != WorkList.end(); ) { 120 if (*WI == I) 121 WI = WorkList.erase(WI); 122 else 123 ++WI; 124 } 125 126 MadeChange = true; 127 ++DCEEliminated; 128 } 129 } 130 return MadeChange; 131 } 132 133 FunctionPass *llvm::createDeadCodeEliminationPass() { 134 return new DCE(); 135 } 136 137