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 "rle"
  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 RLE : public FunctionPass {
  34     static char ID; // Pass identification, replacement for typeid
  35     RLE() : 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 RLE::ID = 0;
  55   RegisterPass<RLE> X("rle", "Redundant Load Elimination");
  56 }
  57
  58 FunctionPass *llvm::createRedundantLoadEliminationPass() { return new RLE(); }
  59
  60 bool RLE::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();
  70        BBI != BBE; ++BBI) {
  71     // If we find a store or a free...
  72     if (LoadInst* L = dyn_cast<LoadInst>(BBI)) {
  73       // We can't delete volatile loads
  74       if (L->isVolatile()) {
  75         lastLoad[L->getPointerOperand()] = L;
  76         continue;
  77       }
  78
  79       Value* pointer = L->getPointerOperand();
  80       LoadInst*& last = lastLoad[pointer];
  81
  82       // ... to a pointer that has been loaded from before...
  83       Instruction* dep = MD.getDependency(BBI);
  84       bool deletedLoad = false;
  85
  86       while (dep != MemoryDependenceAnalysis::None &&
  87              dep != MemoryDependenceAnalysis::NonLocal &&
  88              (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
  89         // ... that depends on a store ...
  90         if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
  91           if (S->getPointerOperand() == pointer) {
  92             // Remove it!
  93             MD.removeInstruction(BBI);
  94
  95             BBI--;
  96             L->replaceAllUsesWith(S->getOperand(0));
  97             L->eraseFromParent();
  98             NumFastLoads++;
  99             deletedLoad = true;
 100             MadeChange = true;
 101           }
 102
 103           // Whether we removed it or not, we can't
 104           // go any further
 105           break;
 106         } else if (!last) {
 107           // If we don't depend on a store, and we haven't
 108           // been loaded before, bail.
 109           break;
 110         } else if (dep == last) {
 111           // Remove it!
 112           MD.removeInstruction(BBI);
 113
 114           BBI--;
 115           L->replaceAllUsesWith(last);
 116           L->eraseFromParent();
 117           deletedLoad = true;
 118           NumFastLoads++;
 119           MadeChange = true;
 120
 121           break;
 122         } else {
 123           dep = MD.getDependency(BBI, dep);
 124         }
 125       }
 126
 127       if (!deletedLoad)
 128         last = L;
 129     }
 130   }
 131
 132   return MadeChange;
 133 }
 134
 135