1 //===-- llvm/CodeGen/Spiller.cpp - Spiller -------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "spiller"
13 #include "VirtRegMap.h"
14 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
15 #include "llvm/CodeGen/LiveStackAnalysis.h"
16 #include "llvm/CodeGen/MachineFrameInfo.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
26 Spiller::~Spiller() {}
30 /// Utility class for spillers.
31 class SpillerBase : public Spiller {
37 MachineFrameInfo *mfi;
38 MachineRegisterInfo *mri;
39 const TargetInstrInfo *tii;
42 /// Construct a spiller base.
43 SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
45 mf(mf), lis(lis), ls(ls), vrm(vrm)
47 mfi = mf->getFrameInfo();
48 mri = &mf->getRegInfo();
49 tii = mf->getTarget().getInstrInfo();
52 /// Ensures there is space before the given machine instruction, returns the
53 /// instruction's new number.
54 SlotIndex makeSpaceBefore(MachineInstr *mi) {
55 if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
56 // FIXME: Should be updated to use rewrite-in-place methods when they're
57 // introduced. Currently broken.
58 //lis->scaleNumbering(2);
59 //ls->scaleNumbering(2);
62 SlotIndex miIdx = lis->getInstructionIndex(mi);
64 assert(lis->hasGapBeforeInstr(miIdx));
69 /// Ensure there is space after the given machine instruction, returns the
70 /// instruction's new number.
71 SlotIndex makeSpaceAfter(MachineInstr *mi) {
72 if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
73 // FIXME: Should be updated to use rewrite-in-place methods when they're
74 // introduced. Currently broken.
75 // lis->scaleNumbering(2);
76 // ls->scaleNumbering(2);
79 SlotIndex miIdx = lis->getInstructionIndex(mi);
81 assert(lis->hasGapAfterInstr(miIdx));
86 /// Insert a store of the given vreg to the given stack slot immediately
87 /// after the given instruction. Returns the base index of the inserted
88 /// instruction. The caller is responsible for adding an appropriate
89 /// LiveInterval to the LiveIntervals analysis.
90 SlotIndex insertStoreAfter(MachineInstr *mi, unsigned ss,
92 const TargetRegisterClass *trc) {
94 MachineBasicBlock::iterator nextInstItr(next(mi));
96 SlotIndex miIdx = makeSpaceAfter(mi);
98 tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
100 MachineBasicBlock::iterator storeInstItr(next(mi));
101 MachineInstr *storeInst = &*storeInstItr;
102 SlotIndex storeInstIdx = miIdx.getNextIndex();
104 assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
105 "Store inst index already in use.");
107 lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
112 /// Insert a store of the given vreg to the given stack slot immediately
113 /// before the given instructnion. Returns the base index of the inserted
115 SlotIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
117 const TargetRegisterClass *trc) {
118 SlotIndex miIdx = makeSpaceBefore(mi);
120 tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
121 MachineBasicBlock::iterator storeInstItr(prior(mi));
122 MachineInstr *storeInst = &*storeInstItr;
123 SlotIndex storeInstIdx = miIdx.getPrevIndex();
125 assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
126 "Store inst index already in use.");
128 lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
133 void insertStoreAfterInstOnInterval(LiveInterval *li,
134 MachineInstr *mi, unsigned ss,
136 const TargetRegisterClass *trc) {
138 SlotIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
139 SlotIndex start = lis->getInstructionIndex(mi).getDefIndex(),
140 end = storeInstIdx.getUseIndex();
143 li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
144 vni->addKill(storeInstIdx);
145 DEBUG(errs() << " Inserting store range: [" << start
146 << ", " << end << ")\n");
147 LiveRange lr(start, end, vni);
152 /// Insert a load of the given vreg from the given stack slot immediately
153 /// after the given instruction. Returns the base index of the inserted
154 /// instruction. The caller is responsibel for adding/removing an appropriate
155 /// range vreg's LiveInterval.
156 SlotIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
158 const TargetRegisterClass *trc) {
160 MachineBasicBlock::iterator nextInstItr(next(mi));
162 SlotIndex miIdx = makeSpaceAfter(mi);
164 tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
165 MachineBasicBlock::iterator loadInstItr(next(mi));
166 MachineInstr *loadInst = &*loadInstItr;
167 SlotIndex loadInstIdx = miIdx.getNextIndex();
169 assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
170 "Store inst index already in use.");
172 lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
177 /// Insert a load of the given vreg from the given stack slot immediately
178 /// before the given instruction. Returns the base index of the inserted
179 /// instruction. The caller is responsible for adding an appropriate
180 /// LiveInterval to the LiveIntervals analysis.
181 SlotIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
183 const TargetRegisterClass *trc) {
184 SlotIndex miIdx = makeSpaceBefore(mi);
186 tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
187 MachineBasicBlock::iterator loadInstItr(prior(mi));
188 MachineInstr *loadInst = &*loadInstItr;
189 SlotIndex loadInstIdx = miIdx.getPrevIndex();
191 assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
192 "Load inst index already in use.");
194 lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
199 void insertLoadBeforeInstOnInterval(LiveInterval *li,
200 MachineInstr *mi, unsigned ss,
202 const TargetRegisterClass *trc) {
204 SlotIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
205 SlotIndex start = loadInstIdx.getDefIndex(),
206 end = lis->getInstructionIndex(mi).getUseIndex();
209 li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
210 vni->addKill(lis->getInstructionIndex(mi));
211 DEBUG(errs() << " Intserting load range: [" << start
212 << ", " << end << ")\n");
213 LiveRange lr(start, end, vni);
220 /// Add spill ranges for every use/def of the live interval, inserting loads
221 /// immediately before each use, and stores after each def. No folding is
223 std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
224 DEBUG(errs() << "Spilling everywhere " << *li << "\n");
226 assert(li->weight != HUGE_VALF &&
227 "Attempting to spill already spilled value.");
229 assert(!li->isStackSlot() &&
230 "Trying to spill a stack slot.");
232 DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n");
234 std::vector<LiveInterval*> added;
236 const TargetRegisterClass *trc = mri->getRegClass(li->reg);
237 unsigned ss = vrm->assignVirt2StackSlot(li->reg);
239 for (MachineRegisterInfo::reg_iterator
240 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
242 MachineInstr *mi = &*regItr;
244 DEBUG(errs() << " Processing " << *mi);
248 } while (regItr != mri->reg_end() && (&*regItr == mi));
250 SmallVector<unsigned, 2> indices;
254 for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
255 MachineOperand &op = mi->getOperand(i);
257 if (!op.isReg() || op.getReg() != li->reg)
260 hasUse |= mi->getOperand(i).isUse();
261 hasDef |= mi->getOperand(i).isDef();
263 indices.push_back(i);
266 unsigned newVReg = mri->createVirtualRegister(trc);
268 vrm->assignVirt2StackSlot(newVReg, ss);
270 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
271 newLI->weight = HUGE_VALF;
273 for (unsigned i = 0; i < indices.size(); ++i) {
274 mi->getOperand(indices[i]).setReg(newVReg);
276 if (mi->getOperand(indices[i]).isUse()) {
277 mi->getOperand(indices[i]).setIsKill(true);
281 assert(hasUse || hasDef);
284 insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc);
288 insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc);
291 added.push_back(newLI);
300 /// Spills any live range using the spill-everywhere method with no attempt at
302 class TrivialSpiller : public SpillerBase {
305 TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
307 SpillerBase(mf, lis, ls, vrm) {}
309 std::vector<LiveInterval*> spill(LiveInterval *li) {
310 return trivialSpillEverywhere(li);
313 std::vector<LiveInterval*> intraBlockSplit(LiveInterval *li, VNInfo *valno) {
314 std::vector<LiveInterval*> spillIntervals;
316 if (!valno->isDefAccurate() && !valno->isPHIDef()) {
317 // Early out for values which have no well defined def point.
318 return spillIntervals;
321 // Ok.. we should be able to proceed...
322 const TargetRegisterClass *trc = mri->getRegClass(li->reg);
323 unsigned ss = vrm->assignVirt2StackSlot(li->reg);
325 vrm->assignVirt2StackSlot(li->reg, ss);
327 MachineInstr *mi = 0;
328 SlotIndex storeIdx = SlotIndex();
330 if (valno->isDefAccurate()) {
331 // If we have an accurate def we can just grab an iterator to the instr
333 mi = lis->getInstructionFromIndex(valno->def);
334 storeIdx = insertStoreAfter(mi, ss, li->reg, trc).getDefIndex();
336 // if we get here we have a PHI def.
337 mi = &lis->getMBBFromIndex(valno->def)->front();
338 storeIdx = insertStoreBefore(mi, ss, li->reg, trc).getDefIndex();
341 MachineBasicBlock *defBlock = mi->getParent();
342 SlotIndex loadIdx = SlotIndex();
344 // Now we need to find the load...
345 MachineBasicBlock::iterator useItr(mi);
346 for (; !useItr->readsRegister(li->reg); ++useItr) {}
348 if (useItr != defBlock->end()) {
349 MachineInstr *loadInst = useItr;
350 loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc).getUseIndex();
353 MachineInstr *loadInst = &defBlock->back();
354 loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc).getUseIndex();
357 li->removeRange(storeIdx, loadIdx, true);
359 return spillIntervals;
366 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
367 LiveStacks *ls, VirtRegMap *vrm) {
368 return new TrivialSpiller(mf, lis, ls, vrm);