LLVM API Documentation

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   // Loop over the worklist finding instructions that are dead.  If they are
00084   // dead make them drop all of their uses, making other instructions
00085   // potentially dead, and work until the worklist is empty.
00086   //
00087   bool MadeChange = false;
00088   while (!WorkList.empty()) {
00089     Instruction *I = WorkList.back();
00090     WorkList.pop_back();
00091 
00092     if (isInstructionTriviallyDead(I)) {       // If the instruction is dead.
00093       // Loop over all of the values that the instruction uses, if there are
00094       // instructions being used, add them to the worklist, because they might
00095       // go dead after this one is removed.
00096       //
00097       for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
00098         if (Instruction *Used = dyn_cast<Instruction>(*OI))
00099           WorkList.push_back(Used);
00100 
00101       // Remove the instruction.
00102       I->eraseFromParent();
00103 
00104       // Remove the instruction from the worklist if it still exists in it.
00105       for (std::vector<Instruction*>::iterator WI = WorkList.begin(),
00106              E = WorkList.end(); WI != E; ++WI)
00107         if (*WI == I) {
00108           WorkList.erase(WI);
00109           --E;
00110           --WI;
00111         }
00112 
00113       MadeChange = true;
00114       ++DCEEliminated;
00115     }
00116   }
00117   return MadeChange;
00118 }
00119 
00120 FunctionPass *llvm::createDeadCodeEliminationPass() {
00121   return new DCE();
00122 }
00123