LLVM API Documentation
00001 //===- DCE.cpp - Code to perform dead code elimination --------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements dead inst elimination and dead code elimination. 00011 // 00012 // Dead Inst Elimination performs a single pass over the function removing 00013 // instructions that are obviously dead. Dead Code Elimination is similar, but 00014 // it rechecks instructions that were used by removed instructions to see if 00015 // they are newly dead. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #include "llvm/Transforms/Scalar.h" 00020 #include "llvm/Transforms/Utils/Local.h" 00021 #include "llvm/Instruction.h" 00022 #include "llvm/Pass.h" 00023 #include "llvm/Support/InstIterator.h" 00024 #include "llvm/ADT/Statistic.h" 00025 #include <set> 00026 using namespace llvm; 00027 00028 namespace { 00029 Statistic<> DIEEliminated("die", "Number of insts removed"); 00030 Statistic<> DCEEliminated("dce", "Number of insts removed"); 00031 00032 //===--------------------------------------------------------------------===// 00033 // DeadInstElimination pass implementation 00034 // 00035 00036 struct DeadInstElimination : public BasicBlockPass { 00037 virtual bool runOnBasicBlock(BasicBlock &BB) { 00038 bool Changed = false; 00039 for (BasicBlock::iterator DI = BB.begin(); DI != BB.end(); ) 00040 if (dceInstruction(DI)) { 00041 Changed = true; 00042 ++DIEEliminated; 00043 } else 00044 ++DI; 00045 return Changed; 00046 } 00047 00048 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00049 AU.setPreservesCFG(); 00050 } 00051 }; 00052 00053 RegisterOpt<DeadInstElimination> X("die", "Dead Instruction Elimination"); 00054 } 00055 00056 FunctionPass *llvm::createDeadInstEliminationPass() { 00057 return new DeadInstElimination(); 00058 } 00059 00060 00061 //===----------------------------------------------------------------------===// 00062 // DeadCodeElimination pass implementation 00063 // 00064 00065 namespace { 00066 struct DCE : public FunctionPass { 00067 virtual bool runOnFunction(Function &F); 00068 00069 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00070 AU.setPreservesCFG(); 00071 } 00072 }; 00073 00074 RegisterOpt<DCE> Y("dce", "Dead Code Elimination"); 00075 } 00076 00077 bool DCE::runOnFunction(Function &F) { 00078 // Start out with all of the instructions in the worklist... 00079 std::vector<Instruction*> WorkList; 00080 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { 00081 WorkList.push_back(&*i); 00082 } 00083 std::set<Instruction*> DeadInsts; 00084 00085 // Loop over the worklist finding instructions that are dead. If they are 00086 // dead make them drop all of their uses, making other instructions 00087 // potentially dead, and work until the worklist is empty. 00088 // 00089 while (!WorkList.empty()) { 00090 Instruction *I = WorkList.back(); 00091 WorkList.pop_back(); 00092 00093 if (isInstructionTriviallyDead(I)) { // If the instruction is dead... 00094 // Loop over all of the values that the instruction uses, if there are 00095 // instructions being used, add them to the worklist, because they might 00096 // go dead after this one is removed. 00097 // 00098 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) 00099 if (Instruction *Used = dyn_cast<Instruction>(*OI)) 00100 WorkList.push_back(Used); 00101 00102 // Tell the instruction to let go of all of the values it uses... 00103 I->dropAllReferences(); 00104 00105 // Keep track of this instruction, because we are going to delete it later 00106 DeadInsts.insert(I); 00107 } 00108 } 00109 00110 // If we found no dead instructions, we haven't changed the function... 00111 if (DeadInsts.empty()) return false; 00112 00113 // Otherwise, loop over the program, removing and deleting the instructions... 00114 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00115 for (BasicBlock::iterator BI = I->begin(); BI != I->end(); ) 00116 if (DeadInsts.count(BI)) { // Is this instruction dead? 00117 BI = I->getInstList().erase(BI); // Yup, remove and delete inst 00118 ++DCEEliminated; 00119 } else { // This instruction is not dead 00120 ++BI; // Continue on to the next one... 00121 } 00122 00123 return true; 00124 } 00125 00126 FunctionPass *llvm::createDeadCodeEliminationPass() { 00127 return new DCE(); 00128 } 00129