1 //===- FastDLE.cpp - Fast Dead Load Elimination ---------------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements a trivial dead load elimination that only considers
11 // basic-block local redundant load.
13 // FIXME: This should eventually be extended to be a post-dominator tree
14 // traversal. Doing so would be pretty trivial.
16 //===----------------------------------------------------------------------===//
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"
30 STATISTIC(NumFastLoads, "Number of loads deleted");
33 struct VISIBILITY_HIDDEN RLE : public FunctionPass {
34 static char ID; // Pass identification, replacement for typeid
35 RLE() : FunctionPass((intptr_t)&ID) {}
37 virtual bool runOnFunction(Function &F) {
39 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
40 Changed |= runOnBasicBlock(*I);
44 bool runOnBasicBlock(BasicBlock &BB);
46 // getAnalysisUsage - We require post dominance frontiers (aka Control
48 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
50 AU.addRequired<MemoryDependenceAnalysis>();
51 AU.addPreserved<MemoryDependenceAnalysis>();
55 RegisterPass<RLE> X("rle", "Redundant Load Elimination");
58 FunctionPass *llvm::createRedundantLoadEliminationPass() { return new RLE(); }
60 bool RLE::runOnBasicBlock(BasicBlock &BB) {
61 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
63 // Record the last-seen load from this pointer
64 DenseMap<Value*, LoadInst*> lastLoad;
66 bool MadeChange = false;
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;
78 Value* pointer = L->getPointerOperand();
79 LoadInst*& last = lastLoad[pointer];
81 // ... to a pointer that has been loaded from before...
82 Instruction* dep = MD.getDependency(BBI);
83 bool deletedLoad = false;
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) {
92 MD.removeInstruction(BBI);
95 L->replaceAllUsesWith(S->getOperand(0));
102 // Whether we removed it or not, we can't
106 // If we don't depend on a store, and we haven't
107 // been loaded before, bail.
109 } else if (dep == last) {
111 MD.removeInstruction(BBI);
114 L->replaceAllUsesWith(last);
115 L->eraseFromParent();
122 dep = MD.getDependency(BBI, dep);