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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
//===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "spiller"
#include "Spiller.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
using namespace llvm;
Spiller::~Spiller() {}
namespace {
/// Utility class for spillers.
class SpillerBase : public Spiller {
protected:
MachineFunction *mf;
LiveIntervals *lis;
LiveStacks *ls;
MachineFrameInfo *mfi;
MachineRegisterInfo *mri;
const TargetInstrInfo *tii;
VirtRegMap *vrm;
/// Construct a spiller base.
SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
mf(mf), lis(lis), ls(ls), vrm(vrm)
{
mfi = mf->getFrameInfo();
mri = &mf->getRegInfo();
tii = mf->getTarget().getInstrInfo();
}
/// Insert a store of the given vreg to the given stack slot immediately
/// after the given instruction. Returns the base index of the inserted
/// instruction. The caller is responsible for adding an appropriate
/// LiveInterval to the LiveIntervals analysis.
unsigned insertStoreFor(MachineInstr *mi, unsigned ss,
unsigned newVReg,
const TargetRegisterClass *trc) {
MachineBasicBlock::iterator nextInstItr(mi);
++nextInstItr;
if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
lis->scaleNumbering(2);
ls->scaleNumbering(2);
}
unsigned miIdx = lis->getInstructionIndex(mi);
assert(lis->hasGapAfterInstr(miIdx));
tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, newVReg,
true, ss, trc);
MachineBasicBlock::iterator storeInstItr(mi);
++storeInstItr;
MachineInstr *storeInst = &*storeInstItr;
unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
"Store inst index already in use.");
lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
return storeInstIdx;
}
/// Insert a load of the given veg from the given stack slot immediately
/// before the given instruction. Returns the base index of the inserted
/// instruction. The caller is responsible for adding an appropriate
/// LiveInterval to the LiveIntervals analysis.
unsigned insertLoadFor(MachineInstr *mi, unsigned ss,
unsigned newVReg,
const TargetRegisterClass *trc) {
MachineBasicBlock::iterator useInstItr(mi);
if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
lis->scaleNumbering(2);
ls->scaleNumbering(2);
}
unsigned miIdx = lis->getInstructionIndex(mi);
assert(lis->hasGapBeforeInstr(miIdx));
tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, newVReg, ss, trc);
MachineBasicBlock::iterator loadInstItr(mi);
--loadInstItr;
MachineInstr *loadInst = &*loadInstItr;
unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
"Load inst index already in use.");
lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
return loadInstIdx;
}
/// Add spill ranges for every use/def of the live interval, inserting loads
/// immediately before each use, and stores after each def. No folding is
/// attempted.
std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
DOUT << "Spilling everywhere " << *li << "\n";
assert(li->weight != HUGE_VALF &&
"Attempting to spill already spilled value.");
assert(!li->isStackSlot() &&
"Trying to spill a stack slot.");
std::vector<LiveInterval*> added;
const TargetRegisterClass *trc = mri->getRegClass(li->reg);
unsigned ss = vrm->assignVirt2StackSlot(li->reg);
for (MachineRegisterInfo::reg_iterator
regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
MachineInstr *mi = &*regItr;
do {
++regItr;
} while (regItr != mri->reg_end() && (&*regItr == mi));
SmallVector<unsigned, 2> indices;
bool hasUse = false;
bool hasDef = false;
for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
MachineOperand &op = mi->getOperand(i);
if (!op.isReg() || op.getReg() != li->reg)
continue;
hasUse |= mi->getOperand(i).isUse();
hasDef |= mi->getOperand(i).isDef();
indices.push_back(i);
}
unsigned newVReg = mri->createVirtualRegister(trc);
vrm->grow();
vrm->assignVirt2StackSlot(newVReg, ss);
LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
newLI->weight = HUGE_VALF;
for (unsigned i = 0; i < indices.size(); ++i) {
mi->getOperand(indices[i]).setReg(newVReg);
if (mi->getOperand(indices[i]).isUse()) {
mi->getOperand(indices[i]).setIsKill(true);
}
}
assert(hasUse || hasDef);
if (hasUse) {
unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc);
unsigned start = lis->getDefIndex(loadInstIdx),
end = lis->getUseIndex(lis->getInstructionIndex(mi));
VNInfo *vni =
newLI->getNextValue(loadInstIdx, 0, lis->getVNInfoAllocator());
vni->kills.push_back(lis->getInstructionIndex(mi));
LiveRange lr(start, end, vni);
newLI->addRange(lr);
}
if (hasDef) {
unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc);
unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
end = lis->getUseIndex(storeInstIdx);
VNInfo *vni =
newLI->getNextValue(storeInstIdx, 0, lis->getVNInfoAllocator());
vni->kills.push_back(storeInstIdx);
LiveRange lr(start, end, vni);
newLI->addRange(lr);
}
added.push_back(newLI);
}
return added;
}
};
/// Spills any live range using the spill-everywhere method with no attempt at
/// folding.
class TrivialSpiller : public SpillerBase {
public:
TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
SpillerBase(mf, lis, ls, vrm) {}
std::vector<LiveInterval*> spill(LiveInterval *li) {
return trivialSpillEverywhere(li);
}
};
}
llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
LiveStacks *ls, VirtRegMap *vrm) {
return new TrivialSpiller(mf, lis, ls, vrm);
}
|
