Home | History | Annotate | Download | only in Scalar 
      1 //===- DCE.cpp - Code to perform dead code elimination --------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the Aggressive Dead Code Elimination pass.  This pass
     11 // optimistically assumes that all instructions are dead until proven otherwise,
     12 // allowing it to eliminate dead computations that other DCE passes do not
     13 // catch, particularly involving loop computations.
     14 //
     15 //===----------------------------------------------------------------------===//
     16 
     17 #define DEBUG_TYPE "adce"
     18 #include "llvm/Transforms/Scalar.h"
     19 #include "llvm/BasicBlock.h"
     20 #include "llvm/Instructions.h"
     21 #include "llvm/IntrinsicInst.h"
     22 #include "llvm/Pass.h"
     23 #include "llvm/Support/CFG.h"
     24 #include "llvm/Support/InstIterator.h"
     25 #include "llvm/ADT/DepthFirstIterator.h"
     26 #include "llvm/ADT/SmallPtrSet.h"
     27 #include "llvm/ADT/SmallVector.h"
     28 #include "llvm/ADT/Statistic.h"
     29 using namespace llvm;
     30 
     31 STATISTIC(NumRemoved, "Number of instructions removed");
     32 
     33 namespace {
     34   struct ADCE : public FunctionPass {
     35     static char ID; // Pass identification, replacement for typeid
     36     ADCE() : FunctionPass(ID) {
     37       initializeADCEPass(*PassRegistry::getPassRegistry());
     38     }
     39 
     40     virtual bool runOnFunction(Function& F);
     41 
     42     virtual void getAnalysisUsage(AnalysisUsage& AU) const {
     43       AU.setPreservesCFG();
     44     }
     45 
     46   };
     47 }
     48 
     49 char ADCE::ID = 0;
     50 INITIALIZE_PASS(ADCE, "adce", "Aggressive Dead Code Elimination", false, false)
     51 
     52 bool ADCE::runOnFunction(Function& F) {
     53   SmallPtrSet<Instruction*, 128> alive;
     54   SmallVector<Instruction*, 128> worklist;
     55 
     56   // Collect the set of "root" instructions that are known live.
     57   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
     58     if (isa<TerminatorInst>(I.getInstructionIterator()) ||
     59         isa<DbgInfoIntrinsic>(I.getInstructionIterator()) ||
     60         I->mayHaveSideEffects()) {
     61       alive.insert(I.getInstructionIterator());
     62       worklist.push_back(I.getInstructionIterator());
     63     }
     64 
     65   // Propagate liveness backwards to operands.
     66   while (!worklist.empty()) {
     67     Instruction* curr = worklist.pop_back_val();
     68 
     69     for (Instruction::op_iterator OI = curr->op_begin(), OE = curr->op_end();
     70          OI != OE; ++OI)
     71       if (Instruction* Inst = dyn_cast<Instruction>(OI))
     72         if (alive.insert(Inst))
     73           worklist.push_back(Inst);
     74   }
     75 
     76   // The inverse of the live set is the dead set.  These are those instructions
     77   // which have no side effects and do not influence the control flow or return
     78   // value of the function, and may therefore be deleted safely.
     79   // NOTE: We reuse the worklist vector here for memory efficiency.
     80   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
     81     if (!alive.count(I.getInstructionIterator())) {
     82       worklist.push_back(I.getInstructionIterator());
     83       I->dropAllReferences();
     84     }
     85 
     86   for (SmallVector<Instruction*, 1024>::iterator I = worklist.begin(),
     87        E = worklist.end(); I != E; ++I) {
     88     ++NumRemoved;
     89     (*I)->eraseFromParent();
     90   }
     91 
     92   return !worklist.empty();
     93 }
     94 
     95 FunctionPass *llvm::createAggressiveDCEPass() {
     96   return new ADCE();
     97 }
     98