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/MachineFunction.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/CodeGen/MachineFrameInfo.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Support/Debug.h"
25 Spiller::~Spiller() {}
29 /// Utility class for spillers.
30 class SpillerBase : public Spiller {
36 MachineFrameInfo *mfi;
37 MachineRegisterInfo *mri;
38 const TargetInstrInfo *tii;
41 /// Construct a spiller base.
42 SpillerBase(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
43 mf(mf), lis(lis), ls(ls), vrm(vrm)
45 mfi = mf->getFrameInfo();
46 mri = &mf->getRegInfo();
47 tii = mf->getTarget().getInstrInfo();
50 /// Ensures there is space before the given machine instruction, returns the
51 /// instruction's new number.
52 unsigned makeSpaceBefore(MachineInstr *mi) {
53 if (!lis->hasGapBeforeInstr(lis->getInstructionIndex(mi))) {
54 lis->scaleNumbering(2);
55 ls->scaleNumbering(2);
58 unsigned miIdx = lis->getInstructionIndex(mi);
60 assert(lis->hasGapBeforeInstr(miIdx));
65 /// Ensure there is space after the given machine instruction, returns the
66 /// instruction's new number.
67 unsigned makeSpaceAfter(MachineInstr *mi) {
68 if (!lis->hasGapAfterInstr(lis->getInstructionIndex(mi))) {
69 lis->scaleNumbering(2);
70 ls->scaleNumbering(2);
73 unsigned miIdx = lis->getInstructionIndex(mi);
75 assert(lis->hasGapAfterInstr(miIdx));
81 /// Insert a store of the given vreg to the given stack slot immediately
82 /// after the given instruction. Returns the base index of the inserted
83 /// instruction. The caller is responsible for adding an appropriate
84 /// LiveInterval to the LiveIntervals analysis.
85 unsigned insertStoreFor(MachineInstr *mi, unsigned ss,
87 const TargetRegisterClass *trc) {
88 MachineBasicBlock::iterator nextInstItr(mi);
91 unsigned miIdx = makeSpaceAfter(mi);
93 tii->storeRegToStackSlot(*mi->getParent(), nextInstItr, vreg,
95 MachineBasicBlock::iterator storeInstItr(mi);
97 MachineInstr *storeInst = &*storeInstItr;
98 unsigned storeInstIdx = miIdx + LiveInterval::InstrSlots::NUM;
100 assert(lis->getInstructionFromIndex(storeInstIdx) == 0 &&
101 "Store inst index already in use.");
103 lis->InsertMachineInstrInMaps(storeInst, storeInstIdx);
108 /// Insert a load of the given veg from the given stack slot immediately
109 /// before the given instruction. Returns the base index of the inserted
110 /// instruction. The caller is responsible for adding an appropriate
111 /// LiveInterval to the LiveIntervals analysis.
112 unsigned insertLoadFor(MachineInstr *mi, unsigned ss,
114 const TargetRegisterClass *trc) {
115 MachineBasicBlock::iterator useInstItr(mi);
117 unsigned miIdx = makeSpaceBefore(mi);
119 tii->loadRegFromStackSlot(*mi->getParent(), useInstItr, vreg, ss, trc);
120 MachineBasicBlock::iterator loadInstItr(mi);
122 MachineInstr *loadInst = &*loadInstItr;
123 unsigned loadInstIdx = miIdx - LiveInterval::InstrSlots::NUM;
125 assert(lis->getInstructionFromIndex(loadInstIdx) == 0 &&
126 "Load inst index already in use.");
128 lis->InsertMachineInstrInMaps(loadInst, loadInstIdx);
133 /// Add spill ranges for every use/def of the live interval, inserting loads
134 /// immediately before each use, and stores after each def. No folding is
136 std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
137 DOUT << "Spilling everywhere " << *li << "\n";
139 assert(li->weight != HUGE_VALF &&
140 "Attempting to spill already spilled value.");
142 assert(!li->isStackSlot() &&
143 "Trying to spill a stack slot.");
145 std::vector<LiveInterval*> added;
147 const TargetRegisterClass *trc = mri->getRegClass(li->reg);
148 unsigned ss = vrm->assignVirt2StackSlot(li->reg);
150 for (MachineRegisterInfo::reg_iterator
151 regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
153 MachineInstr *mi = &*regItr;
156 } while (regItr != mri->reg_end() && (&*regItr == mi));
158 SmallVector<unsigned, 2> indices;
162 for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
163 MachineOperand &op = mi->getOperand(i);
165 if (!op.isReg() || op.getReg() != li->reg)
168 hasUse |= mi->getOperand(i).isUse();
169 hasDef |= mi->getOperand(i).isDef();
171 indices.push_back(i);
174 unsigned newVReg = mri->createVirtualRegister(trc);
176 vrm->assignVirt2StackSlot(newVReg, ss);
178 LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
179 newLI->weight = HUGE_VALF;
181 for (unsigned i = 0; i < indices.size(); ++i) {
182 mi->getOperand(indices[i]).setReg(newVReg);
184 if (mi->getOperand(indices[i]).isUse()) {
185 mi->getOperand(indices[i]).setIsKill(true);
189 assert(hasUse || hasDef);
192 unsigned loadInstIdx = insertLoadFor(mi, ss, newVReg, trc);
193 unsigned start = lis->getDefIndex(loadInstIdx),
194 end = lis->getUseIndex(lis->getInstructionIndex(mi));
197 newLI->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
198 vni->kills.push_back(lis->getInstructionIndex(mi));
199 LiveRange lr(start, end, vni);
205 unsigned storeInstIdx = insertStoreFor(mi, ss, newVReg, trc);
206 unsigned start = lis->getDefIndex(lis->getInstructionIndex(mi)),
207 end = lis->getUseIndex(storeInstIdx);
210 newLI->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
211 vni->kills.push_back(storeInstIdx);
212 LiveRange lr(start, end, vni);
217 added.push_back(newLI);
226 /// Spills any live range using the spill-everywhere method with no attempt at
228 class TrivialSpiller : public SpillerBase {
230 TrivialSpiller(MachineFunction *mf, LiveIntervals *lis, LiveStacks *ls, VirtRegMap *vrm) :
231 SpillerBase(mf, lis, ls, vrm) {}
233 std::vector<LiveInterval*> spill(LiveInterval *li) {
234 return trivialSpillEverywhere(li);
241 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
242 LiveStacks *ls, VirtRegMap *vrm) {
243 return new TrivialSpiller(mf, lis, ls, vrm);