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/MachineInstrBuilder.h"
19 #include "llvm/CodeGen/MachineLoopInfo.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Support/raw_ostream.h"
32 enum SpillerName
{ trivial
, standard
, inline_
};
35 static cl::opt
<SpillerName
>
37 cl::desc("Spiller to use: (default: standard)"),
39 cl::values(clEnumVal(trivial
, "trivial spiller"),
40 clEnumVal(standard
, "default spiller"),
41 clEnumValN(inline_
, "inline", "inline spiller"),
45 // Spiller virtual destructor implementation.
46 Spiller::~Spiller() {}
50 /// Utility class for spillers.
51 class SpillerBase
: public Spiller
{
53 MachineFunctionPass
*pass
;
57 MachineFrameInfo
*mfi
;
58 MachineRegisterInfo
*mri
;
59 const TargetInstrInfo
*tii
;
60 const TargetRegisterInfo
*tri
;
62 /// Construct a spiller base.
63 SpillerBase(MachineFunctionPass
&pass
, MachineFunction
&mf
, VirtRegMap
&vrm
)
64 : pass(&pass
), mf(&mf
), vrm(&vrm
)
66 lis
= &pass
.getAnalysis
<LiveIntervals
>();
67 mfi
= mf
.getFrameInfo();
68 mri
= &mf
.getRegInfo();
69 tii
= mf
.getTarget().getInstrInfo();
70 tri
= mf
.getTarget().getRegisterInfo();
73 /// Add spill ranges for every use/def of the live interval, inserting loads
74 /// immediately before each use, and stores after each def. No folding or
75 /// remat is attempted.
76 void trivialSpillEverywhere(LiveInterval
*li
,
77 SmallVectorImpl
<LiveInterval
*> &newIntervals
) {
78 DEBUG(dbgs() << "Spilling everywhere " << *li
<< "\n");
80 assert(li
->weight
!= HUGE_VALF
&&
81 "Attempting to spill already spilled value.");
83 assert(!TargetRegisterInfo::isStackSlot(li
->reg
) &&
84 "Trying to spill a stack slot.");
86 DEBUG(dbgs() << "Trivial spill everywhere of reg" << li
->reg
<< "\n");
88 const TargetRegisterClass
*trc
= mri
->getRegClass(li
->reg
);
89 unsigned ss
= vrm
->assignVirt2StackSlot(li
->reg
);
91 // Iterate over reg uses/defs.
92 for (MachineRegisterInfo::reg_iterator
93 regItr
= mri
->reg_begin(li
->reg
); regItr
!= mri
->reg_end();) {
95 // Grab the use/def instr.
96 MachineInstr
*mi
= &*regItr
;
98 DEBUG(dbgs() << " Processing " << *mi
);
100 // Step regItr to the next use/def instr.
103 } while (regItr
!= mri
->reg_end() && (&*regItr
== mi
));
105 // Collect uses & defs for this instr.
106 SmallVector
<unsigned, 2> indices
;
109 for (unsigned i
= 0; i
!= mi
->getNumOperands(); ++i
) {
110 MachineOperand
&op
= mi
->getOperand(i
);
111 if (!op
.isReg() || op
.getReg() != li
->reg
)
113 hasUse
|= mi
->getOperand(i
).isUse();
114 hasDef
|= mi
->getOperand(i
).isDef();
115 indices
.push_back(i
);
118 // Create a new vreg & interval for this instr.
119 unsigned newVReg
= mri
->createVirtualRegister(trc
);
121 vrm
->assignVirt2StackSlot(newVReg
, ss
);
122 LiveInterval
*newLI
= &lis
->getOrCreateInterval(newVReg
);
123 newLI
->weight
= HUGE_VALF
;
125 // Update the reg operands & kill flags.
126 for (unsigned i
= 0; i
< indices
.size(); ++i
) {
127 unsigned mopIdx
= indices
[i
];
128 MachineOperand
&mop
= mi
->getOperand(mopIdx
);
130 if (mop
.isUse() && !mi
->isRegTiedToDefOperand(mopIdx
)) {
134 assert(hasUse
|| hasDef
);
136 // Insert reload if necessary.
137 MachineBasicBlock::iterator
miItr(mi
);
139 tii
->loadRegFromStackSlot(*mi
->getParent(), miItr
, newVReg
, ss
, trc
,
141 MachineInstr
*loadInstr(prior(miItr
));
142 SlotIndex loadIndex
=
143 lis
->InsertMachineInstrInMaps(loadInstr
).getDefIndex();
144 vrm
->addSpillSlotUse(ss
, loadInstr
);
145 SlotIndex endIndex
= loadIndex
.getNextIndex();
147 newLI
->getNextValue(loadIndex
, 0, lis
->getVNInfoAllocator());
148 newLI
->addRange(LiveRange(loadIndex
, endIndex
, loadVNI
));
151 // Insert store if necessary.
153 tii
->storeRegToStackSlot(*mi
->getParent(), llvm::next(miItr
), newVReg
,
155 MachineInstr
*storeInstr(llvm::next(miItr
));
156 SlotIndex storeIndex
=
157 lis
->InsertMachineInstrInMaps(storeInstr
).getDefIndex();
158 vrm
->addSpillSlotUse(ss
, storeInstr
);
159 SlotIndex beginIndex
= storeIndex
.getPrevIndex();
161 newLI
->getNextValue(beginIndex
, 0, lis
->getVNInfoAllocator());
162 newLI
->addRange(LiveRange(beginIndex
, storeIndex
, storeVNI
));
165 newIntervals
.push_back(newLI
);
170 } // end anonymous namespace
174 /// Spills any live range using the spill-everywhere method with no attempt at
176 class TrivialSpiller
: public SpillerBase
{
179 TrivialSpiller(MachineFunctionPass
&pass
, MachineFunction
&mf
,
181 : SpillerBase(pass
, mf
, vrm
) {}
183 void spill(LiveInterval
*li
,
184 SmallVectorImpl
<LiveInterval
*> &newIntervals
,
185 const SmallVectorImpl
<LiveInterval
*> &) {
186 // Ignore spillIs - we don't use it.
187 trivialSpillEverywhere(li
, newIntervals
);
191 } // end anonymous namespace
195 /// Falls back on LiveIntervals::addIntervalsForSpills.
196 class StandardSpiller
: public Spiller
{
201 MachineLoopInfo
*loopInfo
;
204 StandardSpiller(MachineFunctionPass
&pass
, MachineFunction
&mf
,
207 lis(&pass
.getAnalysis
<LiveIntervals
>()),
208 lss(&pass
.getAnalysis
<LiveStacks
>()),
209 loopInfo(pass
.getAnalysisIfAvailable
<MachineLoopInfo
>()),
212 /// Falls back on LiveIntervals::addIntervalsForSpills.
213 void spill(LiveInterval
*li
,
214 SmallVectorImpl
<LiveInterval
*> &newIntervals
,
215 const SmallVectorImpl
<LiveInterval
*> &spillIs
) {
216 std::vector
<LiveInterval
*> added
=
217 lis
->addIntervalsForSpills(*li
, spillIs
, loopInfo
, *vrm
);
218 newIntervals
.insert(newIntervals
.end(), added
.begin(), added
.end());
220 // Update LiveStacks.
221 int SS
= vrm
->getStackSlot(li
->reg
);
222 if (SS
== VirtRegMap::NO_STACK_SLOT
)
224 const TargetRegisterClass
*RC
= mf
->getRegInfo().getRegClass(li
->reg
);
225 LiveInterval
&SI
= lss
->getOrCreateInterval(SS
, RC
);
226 if (!SI
.hasAtLeastOneValue())
227 SI
.getNextValue(SlotIndex(), 0, lss
->getVNInfoAllocator());
228 SI
.MergeRangesInAsValue(*li
, SI
.getValNumInfo(0));
232 } // end anonymous namespace
234 llvm::Spiller
* llvm::createSpiller(MachineFunctionPass
&pass
,
237 switch (spillerOpt
) {
238 default: assert(0 && "unknown spiller");
239 case trivial
: return new TrivialSpiller(pass
, mf
, vrm
);
240 case standard
: return new StandardSpiller(pass
, mf
, vrm
);
241 case inline_
: return createInlineSpiller(pass
, mf
, vrm
);