1 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
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 // The inline spiller modifies the machine function directly instead of
11 // inserting spills and restores in VirtRegMap.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
17 #include "LiveRangeEdit.h"
18 #include "VirtRegMap.h"
19 #include "llvm/Analysis/AliasAnalysis.h"
20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
21 #include "llvm/CodeGen/LiveStackAnalysis.h"
22 #include "llvm/CodeGen/MachineFrameInfo.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/Target/TargetMachine.h"
26 #include "llvm/Target/TargetInstrInfo.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
33 class InlineSpiller : public Spiller {
34 MachineFunctionPass &Pass;
40 MachineFrameInfo &MFI;
41 MachineRegisterInfo &MRI;
42 const TargetInstrInfo &TII;
43 const TargetRegisterInfo &TRI;
45 // Variables that are valid during spill(), but used by multiple methods.
47 const TargetRegisterClass *RC;
50 // All registers to spill to StackSlot, including the main register.
51 SmallVector<unsigned, 8> RegsToSpill;
53 // All COPY instructions to/from snippets.
54 // They are ignored since both operands refer to the same stack slot.
55 SmallPtrSet<MachineInstr*, 8> SnippetCopies;
57 // Values that failed to remat at some point.
58 SmallPtrSet<VNInfo*, 8> UsedValues;
63 InlineSpiller(MachineFunctionPass &pass,
68 LIS(pass.getAnalysis<LiveIntervals>()),
69 LSS(pass.getAnalysis<LiveStacks>()),
70 AA(&pass.getAnalysis<AliasAnalysis>()),
72 MFI(*mf.getFrameInfo()),
74 TII(*mf.getTarget().getInstrInfo()),
75 TRI(*mf.getTarget().getRegisterInfo()) {}
77 void spill(LiveRangeEdit &);
80 bool isSnippet(const LiveInterval &SnipLI);
81 void collectRegsToSpill();
83 bool reMaterializeFor(MachineBasicBlock::iterator MI);
84 void reMaterializeAll();
86 bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
87 bool foldMemoryOperand(MachineBasicBlock::iterator MI,
88 const SmallVectorImpl<unsigned> &Ops,
89 MachineInstr *LoadMI = 0);
90 void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
91 void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
92 MachineBasicBlock::iterator MI);
94 void spillAroundUses(unsigned Reg);
99 Spiller *createInlineSpiller(MachineFunctionPass &pass,
102 return new InlineSpiller(pass, mf, vrm);
106 //===----------------------------------------------------------------------===//
108 //===----------------------------------------------------------------------===//
110 // When spilling a virtual register, we also spill any snippets it is connected
111 // to. The snippets are small live ranges that only have a single real use,
112 // leftovers from live range splitting. Spilling them enables memory operand
113 // folding or tightens the live range around the single use.
115 // This minimizes register pressure and maximizes the store-to-load distance for
116 // spill slots which can be important in tight loops.
118 /// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
119 /// otherwise return 0.
120 static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) {
123 if (MI->getOperand(0).getSubReg() != 0)
125 if (MI->getOperand(1).getSubReg() != 0)
127 if (MI->getOperand(0).getReg() == Reg)
128 return MI->getOperand(1).getReg();
129 if (MI->getOperand(1).getReg() == Reg)
130 return MI->getOperand(0).getReg();
134 /// isSnippet - Identify if a live interval is a snippet that should be spilled.
135 /// It is assumed that SnipLI is a virtual register with the same original as
137 bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
138 unsigned Reg = Edit->getReg();
140 // A snippet is a tiny live range with only a single instruction using it
141 // besides copies to/from Reg or spills/fills. We accept:
143 // %snip = COPY %Reg / FILL fi#
145 // %Reg = COPY %snip / SPILL %snip, fi#
147 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
150 MachineInstr *UseMI = 0;
152 // Check that all uses satisfy our criteria.
153 for (MachineRegisterInfo::reg_nodbg_iterator
154 RI = MRI.reg_nodbg_begin(SnipLI.reg);
155 MachineInstr *MI = RI.skipInstruction();) {
157 // Allow copies to/from Reg.
158 if (isFullCopyOf(MI, Reg))
161 // Allow stack slot loads.
163 if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
166 // Allow stack slot stores.
167 if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
170 // Allow a single additional instruction.
171 if (UseMI && MI != UseMI)
178 /// collectRegsToSpill - Collect live range snippets that only have a single
180 void InlineSpiller::collectRegsToSpill() {
181 unsigned Reg = Edit->getReg();
182 unsigned Orig = VRM.getOriginal(Reg);
184 // Main register always spills.
185 RegsToSpill.assign(1, Reg);
186 SnippetCopies.clear();
188 // Snippets all have the same original, so there can't be any for an original
193 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
194 MachineInstr *MI = RI.skipInstruction();) {
195 unsigned SnipReg = isFullCopyOf(MI, Reg);
198 if (!TargetRegisterInfo::isVirtualRegister(SnipReg))
200 if (VRM.getOriginal(SnipReg) != Orig)
202 LiveInterval &SnipLI = LIS.getInterval(SnipReg);
203 if (!isSnippet(SnipLI))
205 SnippetCopies.insert(MI);
206 if (std::find(RegsToSpill.begin(), RegsToSpill.end(),
207 SnipReg) == RegsToSpill.end())
208 RegsToSpill.push_back(SnipReg);
210 DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
214 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
215 bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
216 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex();
217 VNInfo *OrigVNI = Edit->getParent().getVNInfoAt(UseIdx);
220 DEBUG(dbgs() << "\tadding <undef> flags: ");
221 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
222 MachineOperand &MO = MI->getOperand(i);
223 if (MO.isReg() && MO.isUse() && MO.getReg() == Edit->getReg())
226 DEBUG(dbgs() << UseIdx << '\t' << *MI);
230 // FIXME: Properly remat for snippets as well.
231 if (SnippetCopies.count(MI)) {
232 UsedValues.insert(OrigVNI);
236 LiveRangeEdit::Remat RM(OrigVNI);
237 if (!Edit->canRematerializeAt(RM, UseIdx, false, LIS)) {
238 UsedValues.insert(OrigVNI);
239 DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
243 // If the instruction also writes Edit->getReg(), it had better not require
244 // the same register for uses and defs.
246 SmallVector<unsigned, 8> Ops;
247 tie(Reads, Writes) = MI->readsWritesVirtualRegister(Edit->getReg(), &Ops);
249 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
250 MachineOperand &MO = MI->getOperand(Ops[i]);
251 if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) {
252 UsedValues.insert(OrigVNI);
253 DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
259 // Before rematerializing into a register for a single instruction, try to
260 // fold a load into the instruction. That avoids allocating a new register.
261 if (RM.OrigMI->getDesc().canFoldAsLoad() &&
262 foldMemoryOperand(MI, Ops, RM.OrigMI)) {
263 Edit->markRematerialized(RM.ParentVNI);
267 // Alocate a new register for the remat.
268 LiveInterval &NewLI = Edit->create(MRI, LIS, VRM);
269 NewLI.markNotSpillable();
271 // Rematting for a copy: Set allocation hint to be the destination register.
273 MRI.setRegAllocationHint(NewLI.reg, 0, MI->getOperand(0).getReg());
275 // Finally we can rematerialize OrigMI before MI.
276 SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM,
278 DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
279 << *LIS.getInstructionFromIndex(DefIdx));
282 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
283 MachineOperand &MO = MI->getOperand(Ops[i]);
284 if (MO.isReg() && MO.isUse() && MO.getReg() == Edit->getReg()) {
285 MO.setReg(NewLI.reg);
289 DEBUG(dbgs() << "\t " << UseIdx << '\t' << *MI);
291 VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator());
292 NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
293 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
297 /// reMaterializeAll - Try to rematerialize as many uses as possible,
298 /// and trim the live ranges after.
299 void InlineSpiller::reMaterializeAll() {
300 // Do a quick scan of the interval values to find if any are remattable.
301 if (!Edit->anyRematerializable(LIS, TII, AA))
306 // Try to remat before all uses of Edit->getReg().
307 bool anyRemat = false;
308 for (MachineRegisterInfo::use_nodbg_iterator
309 RI = MRI.use_nodbg_begin(Edit->getReg());
310 MachineInstr *MI = RI.skipInstruction();)
311 anyRemat |= reMaterializeFor(MI);
316 // Remove any values that were completely rematted.
317 bool anyRemoved = false;
318 for (LiveInterval::vni_iterator I = Edit->getParent().vni_begin(),
319 E = Edit->getParent().vni_end(); I != E; ++I) {
321 if (VNI->hasPHIKill() || !Edit->didRematerialize(VNI) ||
322 UsedValues.count(VNI))
324 MachineInstr *DefMI = LIS.getInstructionFromIndex(VNI->def);
325 DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI);
326 LIS.RemoveMachineInstrFromMaps(DefMI);
327 VRM.RemoveMachineInstrFromMaps(DefMI);
328 DefMI->eraseFromParent();
329 VNI->def = SlotIndex();
336 // Removing values may cause debug uses where parent is not live.
337 for (MachineRegisterInfo::use_iterator RI = MRI.use_begin(Edit->getReg());
338 MachineInstr *MI = RI.skipInstruction();) {
339 if (!MI->isDebugValue())
341 // Try to preserve the debug value if parent is live immediately after it.
342 MachineBasicBlock::iterator NextMI = MI;
344 if (NextMI != MI->getParent()->end() && !LIS.isNotInMIMap(NextMI)) {
345 SlotIndex Idx = LIS.getInstructionIndex(NextMI);
346 VNInfo *VNI = Edit->getParent().getVNInfoAt(Idx);
347 if (VNI && (VNI->hasPHIKill() || UsedValues.count(VNI)))
350 DEBUG(dbgs() << "Removing debug info due to remat:" << "\t" << *MI);
351 MI->eraseFromParent();
355 /// If MI is a load or store of StackSlot, it can be removed.
356 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
359 if (!(InstrReg = TII.isLoadFromStackSlot(MI, FI)) &&
360 !(InstrReg = TII.isStoreToStackSlot(MI, FI)))
363 // We have a stack access. Is it the right register and slot?
364 if (InstrReg != Reg || FI != StackSlot)
367 DEBUG(dbgs() << "Coalescing stack access: " << *MI);
368 LIS.RemoveMachineInstrFromMaps(MI);
369 MI->eraseFromParent();
373 /// foldMemoryOperand - Try folding stack slot references in Ops into MI.
374 /// @param MI Instruction using or defining the current register.
375 /// @param Ops Operand indices from readsWritesVirtualRegister().
376 /// @param LoadMI Load instruction to use instead of stack slot when non-null.
377 /// @return True on success, and MI will be erased.
378 bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
379 const SmallVectorImpl<unsigned> &Ops,
380 MachineInstr *LoadMI) {
381 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
383 SmallVector<unsigned, 8> FoldOps;
384 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
385 unsigned Idx = Ops[i];
386 MachineOperand &MO = MI->getOperand(Idx);
389 // FIXME: Teach targets to deal with subregs.
392 // We cannot fold a load instruction into a def.
393 if (LoadMI && MO.isDef())
395 // Tied use operands should not be passed to foldMemoryOperand.
396 if (!MI->isRegTiedToDefOperand(Idx))
397 FoldOps.push_back(Idx);
400 MachineInstr *FoldMI =
401 LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI)
402 : TII.foldMemoryOperand(MI, FoldOps, StackSlot);
405 LIS.ReplaceMachineInstrInMaps(MI, FoldMI);
407 VRM.addSpillSlotUse(StackSlot, FoldMI);
408 MI->eraseFromParent();
409 DEBUG(dbgs() << "\tfolded: " << *FoldMI);
413 /// insertReload - Insert a reload of NewLI.reg before MI.
414 void InlineSpiller::insertReload(LiveInterval &NewLI,
415 MachineBasicBlock::iterator MI) {
416 MachineBasicBlock &MBB = *MI->getParent();
417 SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
418 TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot, RC, &TRI);
419 --MI; // Point to load instruction.
420 SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex();
421 VRM.addSpillSlotUse(StackSlot, MI);
422 DEBUG(dbgs() << "\treload: " << LoadIdx << '\t' << *MI);
423 VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0,
424 LIS.getVNInfoAllocator());
425 NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI));
428 /// insertSpill - Insert a spill of NewLI.reg after MI.
429 void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
430 MachineBasicBlock::iterator MI) {
431 MachineBasicBlock &MBB = *MI->getParent();
433 // Get the defined value. It could be an early clobber so keep the def index.
434 SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
435 VNInfo *VNI = OldLI.getVNInfoAt(Idx);
436 assert(VNI && VNI->def.getDefIndex() == Idx && "Inconsistent VNInfo");
439 TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot, RC, &TRI);
440 --MI; // Point to store instruction.
441 SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex();
442 VRM.addSpillSlotUse(StackSlot, MI);
443 DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
444 VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator());
445 NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
448 /// spillAroundUses - insert spill code around each use of Reg.
449 void InlineSpiller::spillAroundUses(unsigned Reg) {
450 LiveInterval &OldLI = LIS.getInterval(Reg);
452 // Iterate over instructions using Reg.
453 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
454 MachineInstr *MI = RI.skipInstruction();) {
456 // Debug values are not allowed to affect codegen.
457 if (MI->isDebugValue()) {
458 // Modify DBG_VALUE now that the value is in a spill slot.
459 uint64_t Offset = MI->getOperand(1).getImm();
460 const MDNode *MDPtr = MI->getOperand(2).getMetadata();
461 DebugLoc DL = MI->getDebugLoc();
462 if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot,
463 Offset, MDPtr, DL)) {
464 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
465 MachineBasicBlock *MBB = MI->getParent();
466 MBB->insert(MBB->erase(MI), NewDV);
468 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
469 MI->eraseFromParent();
474 // Ignore copies to/from snippets. We'll delete them.
475 if (SnippetCopies.count(MI))
478 // Stack slot accesses may coalesce away.
479 if (coalesceStackAccess(MI, Reg))
482 // Analyze instruction.
484 SmallVector<unsigned, 8> Ops;
485 tie(Reads, Writes) = MI->readsWritesVirtualRegister(Reg, &Ops);
487 // Attempt to fold memory ops.
488 if (foldMemoryOperand(MI, Ops))
491 // Allocate interval around instruction.
492 // FIXME: Infer regclass from instruction alone.
493 LiveInterval &NewLI = Edit->create(MRI, LIS, VRM);
494 NewLI.markNotSpillable();
497 insertReload(NewLI, MI);
499 // Rewrite instruction operands.
500 bool hasLiveDef = false;
501 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
502 MachineOperand &MO = MI->getOperand(Ops[i]);
503 MO.setReg(NewLI.reg);
505 if (!MI->isRegTiedToDefOperand(Ops[i]))
513 // FIXME: Use a second vreg if instruction has no tied ops.
514 if (Writes && hasLiveDef)
515 insertSpill(NewLI, OldLI, MI);
517 DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
521 void InlineSpiller::spill(LiveRangeEdit &edit) {
523 assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
524 && "Trying to spill a stack slot.");
525 DEBUG(dbgs() << "Inline spilling "
526 << MRI.getRegClass(edit.getReg())->getName()
527 << ':' << edit.getParent() << "\nFrom original "
528 << PrintReg(VRM.getOriginal(edit.getReg())) << '\n');
529 assert(edit.getParent().isSpillable() &&
530 "Attempting to spill already spilled value.");
532 // Share a stack slot among all descendants of Orig.
533 unsigned Orig = VRM.getOriginal(edit.getReg());
534 StackSlot = VRM.getStackSlot(Orig);
536 collectRegsToSpill();
540 // Remat may handle everything.
541 if (Edit->getParent().empty())
544 RC = MRI.getRegClass(edit.getReg());
546 if (StackSlot == VirtRegMap::NO_STACK_SLOT)
547 StackSlot = VRM.assignVirt2StackSlot(Orig);
549 if (Orig != edit.getReg())
550 VRM.assignVirt2StackSlot(edit.getReg(), StackSlot);
552 // Update LiveStacks now that we are committed to spilling.
553 LiveInterval &stacklvr = LSS.getOrCreateInterval(StackSlot, RC);
554 if (!stacklvr.hasAtLeastOneValue())
555 stacklvr.getNextValue(SlotIndex(), 0, LSS.getVNInfoAllocator());
556 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
557 stacklvr.MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]),
558 stacklvr.getValNumInfo(0));
560 // Spill around uses of all RegsToSpill.
561 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
562 spillAroundUses(RegsToSpill[i]);
564 // Finally delete the SnippetCopies.
565 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(edit.getReg());
566 MachineInstr *MI = RI.skipInstruction();) {
567 assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy");
568 // FIXME: Do this with a LiveRangeEdit callback.
569 VRM.RemoveMachineInstrFromMaps(MI);
570 LIS.RemoveMachineInstrFromMaps(MI);
571 MI->eraseFromParent();
574 for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
575 edit.eraseVirtReg(RegsToSpill[i], LIS);