LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DCE.cpp

Go to the documentation of this file.
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