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