lib/Transforms/Scalar/RedundantLoadElimination.cpp

   1 //===- FastDLE.cpp - Fast Dead Load Elimination ---------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a trivial dead load elimination that only considers
  11 // basic-block local redundant load.
  12 //
  13 // FIXME: This should eventually be extended to be a post-dominator tree
  14 // traversal.  Doing so would be pretty trivial.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "fdle"
  19 #include "llvm/Transforms/Scalar.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/ADT/SmallPtrSet.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  26 #include "llvm/Transforms/Utils/Local.h"
  27 #include "llvm/Support/Compiler.h"
  28 using namespace llvm;
  29
  30 STATISTIC(NumFastLoads, "Number of loads deleted");
  31
  32 namespace {
  33   struct VISIBILITY_HIDDEN FDLE : public FunctionPass {
  34     static char ID; // Pass identification, replacement for typeid
  35     FDLE() : FunctionPass((intptr_t)&ID) {}
  36
  37     virtual bool runOnFunction(Function &F) {
  38       bool Changed = false;
  39       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  40         Changed |= runOnBasicBlock(*I);
  41       return Changed;
  42     }
  43
  44     bool runOnBasicBlock(BasicBlock &BB);
  45
  46     // getAnalysisUsage - We require post dominance frontiers (aka Control
  47     // Dependence Graph)
  48     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  49       AU.setPreservesCFG();
  50       AU.addRequired<MemoryDependenceAnalysis>();
  51       AU.addPreserved<MemoryDependenceAnalysis>();
  52     }
  53   };
  54   char FDLE::ID = 0;
  55   RegisterPass<FDLE> X("fdle", "Fast Dead Load Elimination");
  56 }
  57
  58 FunctionPass *llvm::createFastDeadLoadEliminationPass() { return new FDLE(); }
  59
  60 bool FDLE::runOnBasicBlock(BasicBlock &BB) {
  61   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
  62
  63   // Record the last-seen load from this pointer
  64   DenseMap<Value*, LoadInst*> lastLoad;
  65
  66   bool MadeChange = false;
  67
  68   // Do a top-down walk on the BB
  69   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ++BBI) {
  70     // If we find a store or a free...
  71     if (LoadInst* L = dyn_cast<LoadInst>(BBI)) {
  72       // We can't delete volatile loads
  73       if (L->isVolatile()) {
  74         lastLoad[L->getPointerOperand()] = L;
  75         continue;
  76       }
  77
  78       Value* pointer = L->getPointerOperand();
  79       LoadInst*& last = lastLoad[pointer];
  80
  81       // ... to a pointer that has been loaded from before...
  82       Instruction* dep = MD.getDependency(BBI);
  83       bool deletedLoad = false;
  84
  85       while (dep != MemoryDependenceAnalysis::None &&
  86              dep != MemoryDependenceAnalysis::NonLocal &&
  87              (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
  88         // ... that depends on a store ...
  89         if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
  90           if (S->getPointerOperand() == pointer) {
  91             // Remove it!
  92             MD.removeInstruction(BBI);
  93
  94             BBI--;
  95             L->replaceAllUsesWith(S->getOperand(0));
  96             L->eraseFromParent();
  97             NumFastLoads++;
  98             deletedLoad = true;
  99             MadeChange = true;
 100           }
 101
 102           // Whether we removed it or not, we can't
 103           // go any further
 104           break;
 105         } else if (!last) {
 106           // If we don't depend on a store, and we haven't
 107           // been loaded before, bail.
 108           break;
 109         } else if (dep == last) {
 110           // Remove it!
 111           MD.removeInstruction(BBI);
 112
 113           BBI--;
 114           L->replaceAllUsesWith(last);
 115           L->eraseFromParent();
 116           deletedLoad = true;
 117           NumFastLoads++;
 118           MadeChange = true;
 119
 120           break;
 121         } else {
 122           dep = MD.getDependency(BBI, dep);
 123         }
 124       }
 125
 126       if (!deletedLoad)
 127         last = L;
 128     }
 129   }
 130
 131   return MadeChange;
 132 }
 133
 134