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;
103 return lis->InsertMachineInstrInMaps(storeInst);
106 /// Insert a store of the given vreg to the given stack slot immediately
107 /// before the given instructnion. Returns the base index of the inserted
109 SlotIndex insertStoreBefore(MachineInstr *mi, unsigned ss,
111 const TargetRegisterClass *trc) {
112 SlotIndex miIdx = makeSpaceBefore(mi);
114 tii->storeRegToStackSlot(*mi->getParent(), mi, vreg, true, ss, trc);
115 MachineBasicBlock::iterator storeInstItr(prior(mi));
116 MachineInstr *storeInst = &*storeInstItr;
118 return lis->InsertMachineInstrInMaps(storeInst);
121 void insertStoreAfterInstOnInterval(LiveInterval *li,
122 MachineInstr *mi, unsigned ss,
124 const TargetRegisterClass *trc) {
126 SlotIndex storeInstIdx = insertStoreAfter(mi, ss, vreg, trc);
127 SlotIndex start = lis->getInstructionIndex(mi).getDefIndex(),
128 end = storeInstIdx.getUseIndex();
131 li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
132 vni->addKill(storeInstIdx);
133 DEBUG(errs() << " Inserting store range: [" << start
134 << ", " << end << ")\n");
135 LiveRange lr(start, end, vni);
140 /// Insert a load of the given vreg from the given stack slot immediately
141 /// after the given instruction. Returns the base index of the inserted
142 /// instruction. The caller is responsibel for adding/removing an appropriate
143 /// range vreg's LiveInterval.
144 SlotIndex insertLoadAfter(MachineInstr *mi, unsigned ss,
146 const TargetRegisterClass *trc) {
148 MachineBasicBlock::iterator nextInstItr(next(mi));
150 SlotIndex miIdx = makeSpaceAfter(mi);
152 tii->loadRegFromStackSlot(*mi->getParent(), nextInstItr, vreg, ss, trc);
153 MachineBasicBlock::iterator loadInstItr(next(mi));
154 MachineInstr *loadInst = &*loadInstItr;
156 return lis->InsertMachineInstrInMaps(loadInst);
159 /// Insert a load of the given vreg from the given stack slot immediately
160 /// before the given instruction. Returns the base index of the inserted
161 /// instruction. The caller is responsible for adding an appropriate
162 /// LiveInterval to the LiveIntervals analysis.
163 SlotIndex insertLoadBefore(MachineInstr *mi, unsigned ss,
165 const TargetRegisterClass *trc) {
166 SlotIndex miIdx = makeSpaceBefore(mi);
168 tii->loadRegFromStackSlot(*mi->getParent(), mi, vreg, ss, trc);
169 MachineBasicBlock::iterator loadInstItr(prior(mi));
170 MachineInstr *loadInst = &*loadInstItr;
172 return lis->InsertMachineInstrInMaps(loadInst);
175 void insertLoadBeforeInstOnInterval(LiveInterval *li,
176 MachineInstr *mi, unsigned ss,
178 const TargetRegisterClass *trc) {
180 SlotIndex loadInstIdx = insertLoadBefore(mi, ss, vreg, trc);
181 SlotIndex start = loadInstIdx.getDefIndex(),
182 end = lis->getInstructionIndex(mi).getUseIndex();
185 li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
186 vni->addKill(lis->getInstructionIndex(mi));
187 DEBUG(errs() << " Intserting load range: [" << start
188 << ", " << end << ")\n");
189 LiveRange lr(start, end, vni);
196 /// Add spill ranges for every use/def of the live interval, inserting loads
197 /// immediately before each use, and stores after each def. No folding is
199 std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
200 DEBUG(errs() << "Spilling everywhere " << *li << "\n");
202 assert(li->weight != HUGE_VALF &&
203 "Attempting to spill already spilled value.");
205 assert(!li->isStackSlot() &&
206 "Trying to spill a stack slot.");
208 DEBUG(errs() << "Trivial spill everywhere of reg" << li->reg << "\n");
210 std::vector<LiveInterval*> added;
212 const TargetRegisterClass *trc = mri->getRegClass(li->reg);
213 unsigned ss = vrm->assignVirt2StackSlot(li->reg);
215 for (MachineRegisterInfo::reg_iterator
216 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
218 MachineInstr *mi = &*regItr;
220 DEBUG(errs() << " Processing " << *mi);
224 } while (regItr != mri->reg_end() && (&*regItr == mi));
226 SmallVector<unsigned, 2> indices;
230 for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
231 MachineOperand &op = mi->getOperand(i);
233 if (!op.isReg() || op.getReg() != li->reg)
236 hasUse |= mi->getOperand(i).isUse();
237 hasDef |= mi->getOperand(i).isDef();
239 indices.push_back(i);
242 unsigned newVReg = mri->createVirtualRegister(trc);
244 vrm->assignVirt2StackSlot(newVReg, ss);
246 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
247 newLI->weight = HUGE_VALF;
249 for (unsigned i = 0; i < indices.size(); ++i) {
250 mi->getOperand(indices[i]).setReg(newVReg);
252 if (mi->getOperand(indices[i]).isUse()) {
253 mi->getOperand(indices[i]).setIsKill(true);
257 assert(hasUse || hasDef);
260 insertLoadBeforeInstOnInterval(newLI, mi, ss, newVReg, trc);
264 insertStoreAfterInstOnInterval(newLI, mi, ss, newVReg, trc);
267 added.push_back(newLI);
276 /// Spills any live range using the spill-everywhere method with no attempt at
278 class TrivialSpiller : public SpillerBase {
281 TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls,
283 SpillerBase(mf, lis, ls, vrm) {}
285 std::vector<LiveInterval*> spill(LiveInterval *li) {
286 return trivialSpillEverywhere(li);
289 std::vector<LiveInterval*> intraBlockSplit(LiveInterval *li, VNInfo *valno) {
290 std::vector<LiveInterval*> spillIntervals;
292 if (!valno->isDefAccurate() && !valno->isPHIDef()) {
293 // Early out for values which have no well defined def point.
294 return spillIntervals;
297 // Ok.. we should be able to proceed...
298 const TargetRegisterClass *trc = mri->getRegClass(li->reg);
299 unsigned ss = vrm->assignVirt2StackSlot(li->reg);
301 vrm->assignVirt2StackSlot(li->reg, ss);
303 MachineInstr *mi = 0;
304 SlotIndex storeIdx = SlotIndex();
306 if (valno->isDefAccurate()) {
307 // If we have an accurate def we can just grab an iterator to the instr
309 mi = lis->getInstructionFromIndex(valno->def);
310 storeIdx = insertStoreAfter(mi, ss, li->reg, trc).getDefIndex();
312 // if we get here we have a PHI def.
313 mi = &lis->getMBBFromIndex(valno->def)->front();
314 storeIdx = insertStoreBefore(mi, ss, li->reg, trc).getDefIndex();
317 MachineBasicBlock *defBlock = mi->getParent();
318 SlotIndex loadIdx = SlotIndex();
320 // Now we need to find the load...
321 MachineBasicBlock::iterator useItr(mi);
322 for (; !useItr->readsRegister(li->reg); ++useItr) {}
324 if (useItr != defBlock->end()) {
325 MachineInstr *loadInst = useItr;
326 loadIdx = insertLoadBefore(loadInst, ss, li->reg, trc).getUseIndex();
329 MachineInstr *loadInst = &defBlock->back();
330 loadIdx = insertLoadAfter(loadInst, ss, li->reg, trc).getUseIndex();
333 li->removeRange(storeIdx, loadIdx, true);
335 return spillIntervals;
342 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
343 LiveStacks *ls, VirtRegMap *vrm) {
344 return new TrivialSpiller(mf, lis, ls, vrm);