1 //===- DCE.cpp - Code to perform dead code elimination --------------------===// 2 // 3 // This file implements dead inst elimination and dead code elimination. 4 // 5 // Dead Inst Elimination performs a single pass over the function removing 6 // instructions that are obviously dead. Dead Code Elimination is similar, but 7 // it rechecks instructions that were used by removed instructions to see if 8 // they are newly dead. 9 // 10 //===----------------------------------------------------------------------===// 11 12 #include "llvm/Transforms/Scalar.h" 13 #include "llvm/Transforms/Utils/Local.h" 14 #include "llvm/Instruction.h" 15 #include "llvm/Pass.h" 16 #include "llvm/Support/InstIterator.h" 17 #include <set> 18 19 //===----------------------------------------------------------------------===// 20 // DeadInstElimination pass implementation 21 // 22 23 namespace { 24 struct DeadInstElimination : public BasicBlockPass { 25 const char *getPassName() const { return "Dead Instruction Elimination"; } 26 27 virtual bool runOnBasicBlock(BasicBlock *BB) { 28 BasicBlock::InstListType &Vals = BB->getInstList(); 29 bool Changed = false; 30 for (BasicBlock::iterator DI = Vals.begin(); DI != Vals.end(); ) 31 if (dceInstruction(Vals, DI)) 32 Changed = true; 33 else 34 ++DI; 35 return Changed; 36 } 37 38 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 39 AU.preservesCFG(); 40 } 41 }; 42 } 43 44 Pass *createDeadInstEliminationPass() { 45 return new DeadInstElimination(); 46 } 47 48 49 50 //===----------------------------------------------------------------------===// 51 // DeadCodeElimination pass implementation 52 // 53 54 namespace { 55 struct DCE : public FunctionPass { 56 const char *getPassName() const { return "Dead Code Elimination"; } 57 58 virtual bool runOnFunction(Function *F); 59 60 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 61 AU.preservesCFG(); 62 } 63 }; 64 } 65 66 bool DCE::runOnFunction(Function *F) { 67 // Start out with all of the instructions in the worklist... 68 std::vector<Instruction*> WorkList(inst_begin(F), inst_end(F)); 69 std::set<Instruction*> DeadInsts; 70 71 // Loop over the worklist finding instructions that are dead. If they are 72 // dead make them drop all of their uses, making other instructions 73 // potentially dead, and work until the worklist is empty. 74 // 75 while (!WorkList.empty()) { 76 Instruction *I = WorkList.back(); 77 WorkList.pop_back(); 78 79 if (isInstructionTriviallyDead(I)) { // If the instruction is dead... 80 // Loop over all of the values that the instruction uses, if there are 81 // instructions being used, add them to the worklist, because they might 82 // go dead after this one is removed. 83 // 84 for (User::use_iterator UI = I->use_begin(), UE = I->use_end(); 85 UI != UE; ++UI) 86 if (Instruction *Used = dyn_cast<Instruction>(*UI)) 87 WorkList.push_back(Used); 88 89 // Tell the instruction to let go of all of the values it uses... 90 I->dropAllReferences(); 91 92 // Keep track of this instruction, because we are going to delete it later 93 DeadInsts.insert(I); 94 } 95 } 96 97 // If we found no dead instructions, we haven't changed the function... 98 if (DeadInsts.empty()) return false; 99 100 // Otherwise, loop over the program, removing and deleting the instructions... 101 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 102 BasicBlock::InstListType &BBIL = (*I)->getInstList(); 103 for (BasicBlock::iterator BI = BBIL.begin(); BI != BBIL.end(); ) 104 if (DeadInsts.count(*BI)) { // Is this instruction dead? 105 delete BBIL.remove(BI); // Yup, remove and delete inst 106 } else { // This instruction is not dead 107 ++BI; // Continue on to the next one... 108 } 109 } 110 111 return true; 112 } 113 114 Pass *createDeadCodeEliminationPass() { 115 return new DCE(); 116 } 117