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