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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
/*
* (C) 2017 by Computer System Laboratory, IIS, Academia Sinica, Taiwan.
* See COPYRIGHT in top-level directory.
*/
#include "llvm-debug.h"
#include "llvm-opc.h"
#include "llvm-target.h"
#include "llvm-pass.h"
#include "utils.h"
#define PASS_NAME "RedundantStateElimination"
/*
* The RedundantStateElimination pass aims to remove
* (1) redundant stores to PC, and
* (2) redundant loads and stores enclosed by two helper function calls.
*/
class RedundantStateElimination : public FunctionPass {
IRFactory *IF;
MDFactory *MF;
const DataLayout *DL;
Value *CPU;
IVec toErase;
public:
static char ID;
explicit RedundantStateElimination() : FunctionPass(ID) {}
explicit RedundantStateElimination(IRFactory *IF)
: FunctionPass(ID), IF(IF), MF(IF->getMDFactory()), DL(IF->getDL()) {}
int getNumUsers(Instruction *I) {
return distance(I->user_begin(), I->user_end());
}
bool isStateOfPC(Value *Ptr) {
intptr_t Off = 0;
Value *Base = getBaseWithConstantOffset(DL, Ptr, Off);
if (Base == CPU && IRFactory::isStateOfPC(Off))
return true;
return false;
}
bool isDirectDominator(LoadInst *LI, StoreInst *SI) {
Instruction *A = LI, *B = SI;
if (A->getParent() != B->getParent())
return false;
for (auto II = BasicBlock::iterator(A), EE = A->getParent()->end();
II != EE; ++II) {
if (&*II == B)
return true;
/* If a non-const helper function is between the two instructions,
* this is not a direct domination because the helper function could
* cause side effect. */
auto CI = dyn_cast<CallInst>(II);
if (CI && !MDFactory::isConst(CI))
return false;
}
return false;
}
bool removePCState(Function &F);
bool removeHelperState(Function &F);
bool runOnFunction(Function &F);
};
char RedundantStateElimination::ID = 0;
INITIALIZE_PASS(RedundantStateElimination, "rse",
"Eliminate redundant CPU state loads/stores", false, false)
FunctionPass *llvm::createRedundantStateElimination(IRFactory *IF)
{
return new RedundantStateElimination(IF);
}
/* Eliminate redundant stores to PC for each basic block. */
bool RedundantStateElimination::removePCState(Function &F)
{
for (auto FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
bool Found = false;
for (auto BI = FI->rbegin(), BE = FI->rend(); BI != BE; ++BI) {
Instruction *I = &*BI;
if (MF->isGuestMemory(I))
continue;
if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
if (isStateOfPC(getPointerOperand(SI))) {
if (!Found)
Found = true;
else
toErase.push_back(SI);
}
} else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
if (isStateOfPC(getPointerOperand(LI)))
Found = false;
}
}
}
if (toErase.empty())
return false;
ProcessErase(toErase);
return true;
}
/* Eliminate redundant loads/stores enclosed by two helper function calls.
* The redundant loads and stores are generated by StateMappingPass for
* handling synchronization of CPU states around helper function calls.
* A load and store can be removed if a state value is loaded and immediately
* stored back to the same state. For example:
*
* Before optimization: After optimization:
* instructions to sync states instructions to sync states
* call void @helper_function1() call void @helper_function1()
*
* %v0 = load i32, i32* %state0
* %v1 = load i32, i32* %state1
* store i32 %v0, i32* %state0
* store i32 %v1, i32* %state1
*
* call void @helper_function2() call void @helper_function2()
* instructions to reload states instructions to reload states
*/
bool RedundantStateElimination::removeHelperState(Function &F)
{
for (auto FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
for (auto BI = FI->begin(), BE = FI->end(); BI != BE; ++BI) {
Instruction *I = &*BI;
if (MF->isGuestMemory(I))
continue;
StoreInst *SI = dyn_cast<StoreInst>(I);
if (!SI || SI->isVolatile())
continue;
LoadInst *LI = dyn_cast<LoadInst>(getValueOperand(SI));
if (LI && isDirectDominator(LI, SI)) {
/* We can try removing the store instruction if LI is a direct
* dominator of SI. */
Value *PtrA = getPointerOperand(LI);
Value *PtrB = getPointerOperand(SI);
if (StripPointer(PtrA) == CPU && PtrA == PtrB)
toErase.push_back(SI);
}
}
}
if (toErase.empty())
return false;
ProcessErase(toErase);
return true;
}
bool RedundantStateElimination::runOnFunction(Function &F)
{
bool Changed = false;
CPU = IF->getDefaultCPU(F);
if (!CPU) {
dbg() << DEBUG_PASS << "RedundantStateElimination: Cannot find CPU pointer.\n";
return false;
}
Changed |= removePCState(F);
#if 0
Changed |= removeHelperState(F);
#endif
return Changed;
}
/*
* vim: ts=8 sts=4 sw=4 expandtab
*/
|
