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
230
231
232
233
234
235
|
//===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The inline spiller modifies the machine function directly instead of
// inserting spills and restores in VirtRegMap.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "spiller"
#include "Spiller.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace {
class InlineSpiller : public Spiller {
MachineFunction &mf_;
LiveIntervals &lis_;
VirtRegMap &vrm_;
MachineFrameInfo &mfi_;
MachineRegisterInfo &mri_;
const TargetInstrInfo &tii_;
const TargetRegisterInfo &tri_;
const BitVector reserved_;
// Variables that are valid during spill(), but used by multiple methods.
LiveInterval *li_;
const TargetRegisterClass *rc_;
int stackSlot_;
const SmallVectorImpl<LiveInterval*> *spillIs_;
~InlineSpiller() {}
public:
InlineSpiller(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm)
: mf_(*mf), lis_(*lis), vrm_(*vrm),
mfi_(*mf->getFrameInfo()),
mri_(mf->getRegInfo()),
tii_(*mf->getTarget().getInstrInfo()),
tri_(*mf->getTarget().getRegisterInfo()),
reserved_(tri_.getReservedRegs(mf_)) {}
void spill(LiveInterval *li,
std::vector<LiveInterval*> &newIntervals,
SmallVectorImpl<LiveInterval*> &spillIs,
SlotIndex *earliestIndex);
bool reMaterialize(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
void insertSpill(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
};
}
namespace llvm {
Spiller *createInlineSpiller(MachineFunction *mf,
LiveIntervals *lis,
const MachineLoopInfo *mli,
VirtRegMap *vrm) {
return new InlineSpiller(mf, lis, vrm);
}
}
/// reMaterialize - Attempt to rematerialize li_->reg before MI instead of
/// reloading it.
bool InlineSpiller::reMaterialize(LiveInterval &NewLI,
MachineBasicBlock::iterator MI) {
SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex();
LiveRange *LR = li_->getLiveRangeContaining(UseIdx);
if (!LR) {
DEBUG(dbgs() << "\tundef at " << UseIdx << ", adding <undef> flags.\n");
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(i);
if (MO.isReg() && MO.isUse() && MO.getReg() == li_->reg)
MO.setIsUndef();
}
return true;
}
// Find the instruction that defined this value of li_->reg.
if (!LR->valno->isDefAccurate())
return false;
SlotIndex OrigDefIdx = LR->valno->def;
MachineInstr *OrigDefMI = lis_.getInstructionFromIndex(OrigDefIdx);
if (!OrigDefMI)
return false;
// FIXME: Provide AliasAnalysis argument.
if (!tii_.isTriviallyReMaterializable(OrigDefMI))
return false;
// A rematerializable instruction may be using other virtual registers.
// Make sure they are available at the new location.
for (unsigned i = 0, e = OrigDefMI->getNumOperands(); i != e; ++i) {
MachineOperand &MO = OrigDefMI->getOperand(i);
if (!MO.isReg() || !MO.getReg() || MO.getReg() == li_->reg)
continue;
// Reserved physregs are OK. Others are not (probably from coalescing).
if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) {
if (reserved_.test(MO.getReg()))
continue;
else
return false;
}
// We don't want to move any virtual defs.
if (MO.isDef())
return false;
// We have a use of a virtual register other than li_->reg.
if (MO.isUndef())
continue;
// We cannot depend on virtual registers in spillIs_. They will be spilled.
for (unsigned si = 0, se = spillIs_->size(); si != se; ++si)
if ((*spillIs_)[si]->reg == MO.getReg())
return false;
// Is the register available here with the same value as at OrigDefMI?
LiveInterval &ULI = lis_.getInterval(MO.getReg());
LiveRange *HereLR = ULI.getLiveRangeContaining(UseIdx);
if (!HereLR)
return false;
LiveRange *DefLR = ULI.getLiveRangeContaining(OrigDefIdx.getUseIndex());
if (!DefLR || DefLR->valno != HereLR->valno)
return false;
}
// Finally we can rematerialize OrigDefMI before MI.
MachineBasicBlock &MBB = *MI->getParent();
tii_.reMaterialize(MBB, MI, NewLI.reg, 0, OrigDefMI, tri_);
SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(--MI).getDefIndex();
DEBUG(dbgs() << "\tremat: " << DefIdx << '\t' << *MI);
VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, true,
lis_.getVNInfoAllocator());
NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
return true;
}
/// insertReload - Insert a reload of NewLI.reg before MI.
void InlineSpiller::insertReload(LiveInterval &NewLI,
MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();
SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
tii_.loadRegFromStackSlot(MBB, MI, NewLI.reg, stackSlot_, rc_, &tri_);
--MI; // Point to load instruction.
SlotIndex LoadIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
vrm_.addSpillSlotUse(stackSlot_, MI);
DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI);
VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0, true,
lis_.getVNInfoAllocator());
NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI));
}
/// insertSpill - Insert a spill of NewLI.reg after MI.
void InlineSpiller::insertSpill(LiveInterval &NewLI,
MachineBasicBlock::iterator MI) {
MachineBasicBlock &MBB = *MI->getParent();
SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_);
--MI; // Point to store instruction.
SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
vrm_.addSpillSlotUse(stackSlot_, MI);
DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, true,
lis_.getVNInfoAllocator());
NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
}
void InlineSpiller::spill(LiveInterval *li,
std::vector<LiveInterval*> &newIntervals,
SmallVectorImpl<LiveInterval*> &spillIs,
SlotIndex *earliestIndex) {
DEBUG(dbgs() << "Inline spilling " << *li << "\n");
assert(li->isSpillable() && "Attempting to spill already spilled value.");
assert(!li->isStackSlot() && "Trying to spill a stack slot.");
li_ = li;
rc_ = mri_.getRegClass(li->reg);
stackSlot_ = vrm_.assignVirt2StackSlot(li->reg);
spillIs_ = &spillIs;
// Iterate over instructions using register.
for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(li->reg);
MachineInstr *MI = RI.skipInstruction();) {
// Analyze instruction.
bool Reads, Writes;
SmallVector<unsigned, 8> Ops;
tie(Reads, Writes) = MI->readsWritesVirtualRegister(li->reg, &Ops);
// Allocate interval around instruction.
// FIXME: Infer regclass from instruction alone.
unsigned NewVReg = mri_.createVirtualRegister(rc_);
vrm_.grow();
LiveInterval &NewLI = lis_.getOrCreateInterval(NewVReg);
NewLI.markNotSpillable();
// Attempt remat instead of reload.
bool NeedsReload = Reads && !reMaterialize(NewLI, MI);
if (NeedsReload)
insertReload(NewLI, MI);
// Rewrite instruction operands.
bool hasLiveDef = false;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
MachineOperand &MO = MI->getOperand(Ops[i]);
MO.setReg(NewVReg);
if (MO.isUse()) {
if (!MI->isRegTiedToDefOperand(Ops[i]))
MO.setIsKill();
} else {
if (!MO.isDead())
hasLiveDef = true;
}
}
// FIXME: Use a second vreg if instruction has no tied ops.
if (Writes && hasLiveDef)
insertSpill(NewLI, MI);
DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
newIntervals.push_back(&NewLI);
}
}
|
