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