1 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // The inline spiller modifies the machine function directly instead of
11 // inserting spills and restores in VirtRegMap.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #define DEBUG_TYPE "regalloc"
16 #include "Spiller.h"
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/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 
31 using namespace llvm;
32 
33 static cl::opt<bool>
34 VerifySpills("verify-spills", cl::desc("Verify after each spill/split"));
35 
36 namespace {
37 class InlineSpiller : public Spiller {
38   MachineFunctionPass &pass_;
39   MachineFunction &mf_;
40   LiveIntervals &lis_;
41   LiveStacks &lss_;
42   AliasAnalysis *aa_;
43   VirtRegMap &vrm_;
44   MachineFrameInfo &mfi_;
45   MachineRegisterInfo &mri_;
46   const TargetInstrInfo &tii_;
47   const TargetRegisterInfo &tri_;
48   const BitVector reserved_;
49 
50   // Variables that are valid during spill(), but used by multiple methods.
51   LiveRangeEdit *edit_;
52   const TargetRegisterClass *rc_;
53   int stackSlot_;
54 
55   // Values that failed to remat at some point.
56   SmallPtrSet<VNInfo*, 8> usedValues_;
57 
58   ~InlineSpiller() {}
59 
60 public:
61   InlineSpiller(MachineFunctionPass &pass,
62                 MachineFunction &mf,
63                 VirtRegMap &vrm)
64     : pass_(pass),
65       mf_(mf),
66       lis_(pass.getAnalysis<LiveIntervals>()),
67       lss_(pass.getAnalysis<LiveStacks>()),
68       aa_(&pass.getAnalysis<AliasAnalysis>()),
69       vrm_(vrm),
70       mfi_(*mf.getFrameInfo()),
71       mri_(mf.getRegInfo()),
72       tii_(*mf.getTarget().getInstrInfo()),
73       tri_(*mf.getTarget().getRegisterInfo()),
74       reserved_(tri_.getReservedRegs(mf_)) {}
75 
76   void spill(LiveInterval *li,
77              SmallVectorImpl<LiveInterval*> &newIntervals,
78              const SmallVectorImpl<LiveInterval*> &spillIs);
79 
80   void spill(LiveRangeEdit &);
81 
82 private:
83   bool reMaterializeFor(MachineBasicBlock::iterator MI);
84   void reMaterializeAll();
85 
86   bool coalesceStackAccess(MachineInstr *MI);
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, MachineBasicBlock::iterator MI);
92 };
93 }
94 
95 namespace llvm {
96 Spiller *createInlineSpiller(MachineFunctionPass &pass,
97                              MachineFunction &mf,
98                              VirtRegMap &vrm) {
99   if (VerifySpills)
100     mf.verify(&pass, "When creating inline spiller");
101   return new InlineSpiller(pass, mf, vrm);
102 }
103 }
104 
105 /// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
106 bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
107   SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex();
108   VNInfo *OrigVNI = edit_->getParent().getVNInfoAt(UseIdx);
109 
110   if (!OrigVNI) {
111     DEBUG(dbgs() << "\tadding <undef> flags: ");
112     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
113       MachineOperand &MO = MI->getOperand(i);
114       if (MO.isReg() && MO.isUse() && MO.getReg() == edit_->getReg())
115         MO.setIsUndef();
116     }
117     DEBUG(dbgs() << UseIdx << '\t' << *MI);
118     return true;
119   }
120 
121   LiveRangeEdit::Remat RM(OrigVNI);
122   if (!edit_->canRematerializeAt(RM, UseIdx, false, lis_)) {
123     usedValues_.insert(OrigVNI);
124     DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
125     return false;
126   }
127 
128   // If the instruction also writes edit_->getReg(), it had better not require
129   // the same register for uses and defs.
130   bool Reads, Writes;
131   SmallVector<unsigned, 8> Ops;
132   tie(Reads, Writes) = MI->readsWritesVirtualRegister(edit_->getReg(), &Ops);
133   if (Writes) {
134     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
135       MachineOperand &MO = MI->getOperand(Ops[i]);
136       if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) {
137         usedValues_.insert(OrigVNI);
138         DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
139         return false;
140       }
141     }
142   }
143 
144   // Before rematerializing into a register for a single instruction, try to
145   // fold a load into the instruction. That avoids allocating a new register.
146   if (RM.OrigMI->getDesc().canFoldAsLoad() &&
147       foldMemoryOperand(MI, Ops, RM.OrigMI)) {
148     edit_->markRematerialized(RM.ParentVNI);
149     return true;
150   }
151 
152   // Alocate a new register for the remat.
153   LiveInterval &NewLI = edit_->create(mri_, lis_, vrm_);
154   NewLI.markNotSpillable();
155 
156   // Rematting for a copy: Set allocation hint to be the destination register.
157   if (MI->isCopy())
158     mri_.setRegAllocationHint(NewLI.reg, 0, MI->getOperand(0).getReg());
159 
160   // Finally we can rematerialize OrigMI before MI.
161   SlotIndex DefIdx = edit_->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM,
162                                             lis_, tii_, tri_);
163   DEBUG(dbgs() << "\tremat:  " << DefIdx << '\t'
164                << *lis_.getInstructionFromIndex(DefIdx));
165 
166   // Replace operands
167   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
168     MachineOperand &MO = MI->getOperand(Ops[i]);
169     if (MO.isReg() && MO.isUse() && MO.getReg() == edit_->getReg()) {
170       MO.setReg(NewLI.reg);
171       MO.setIsKill();
172     }
173   }
174   DEBUG(dbgs() << "\t        " << UseIdx << '\t' << *MI);
175 
176   VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, lis_.getVNInfoAllocator());
177   NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
178   DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
179   return true;
180 }
181 
182 /// reMaterializeAll - Try to rematerialize as many uses as possible,
183 /// and trim the live ranges after.
184 void InlineSpiller::reMaterializeAll() {
185   // Do a quick scan of the interval values to find if any are remattable.
186   if (!edit_->anyRematerializable(lis_, tii_, aa_))
187     return;
188 
189   usedValues_.clear();
190 
191   // Try to remat before all uses of edit_->getReg().
192   bool anyRemat = false;
193   for (MachineRegisterInfo::use_nodbg_iterator
194        RI = mri_.use_nodbg_begin(edit_->getReg());
195        MachineInstr *MI = RI.skipInstruction();)
196      anyRemat |= reMaterializeFor(MI);
197 
198   if (!anyRemat)
199     return;
200 
201   // Remove any values that were completely rematted.
202   bool anyRemoved = false;
203   for (LiveInterval::vni_iterator I = edit_->getParent().vni_begin(),
204        E = edit_->getParent().vni_end(); I != E; ++I) {
205     VNInfo *VNI = *I;
206     if (VNI->hasPHIKill() || !edit_->didRematerialize(VNI) ||
207         usedValues_.count(VNI))
208       continue;
209     MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def);
210     DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI);
211     lis_.RemoveMachineInstrFromMaps(DefMI);
212     vrm_.RemoveMachineInstrFromMaps(DefMI);
213     DefMI->eraseFromParent();
214     VNI->def = SlotIndex();
215     anyRemoved = true;
216   }
217 
218   if (!anyRemoved)
219     return;
220 
221   // Removing values may cause debug uses where parent is not live.
222   for (MachineRegisterInfo::use_iterator RI = mri_.use_begin(edit_->getReg());
223        MachineInstr *MI = RI.skipInstruction();) {
224     if (!MI->isDebugValue())
225       continue;
226     // Try to preserve the debug value if parent is live immediately after it.
227     MachineBasicBlock::iterator NextMI = MI;
228     ++NextMI;
229     if (NextMI != MI->getParent()->end() && !lis_.isNotInMIMap(NextMI)) {
230       SlotIndex Idx = lis_.getInstructionIndex(NextMI);
231       VNInfo *VNI = edit_->getParent().getVNInfoAt(Idx);
232       if (VNI && (VNI->hasPHIKill() || usedValues_.count(VNI)))
233         continue;
234     }
235     DEBUG(dbgs() << "Removing debug info due to remat:" << "\t" << *MI);
236     MI->eraseFromParent();
237   }
238 }
239 
240 /// If MI is a load or store of stackSlot_, it can be removed.
241 bool InlineSpiller::coalesceStackAccess(MachineInstr *MI) {
242   int FI = 0;
243   unsigned reg;
244   if (!(reg = tii_.isLoadFromStackSlot(MI, FI)) &&
245       !(reg = tii_.isStoreToStackSlot(MI, FI)))
246     return false;
247 
248   // We have a stack access. Is it the right register and slot?
249   if (reg != edit_->getReg() || FI != stackSlot_)
250     return false;
251 
252   DEBUG(dbgs() << "Coalescing stack access: " << *MI);
253   lis_.RemoveMachineInstrFromMaps(MI);
254   MI->eraseFromParent();
255   return true;
256 }
257 
258 /// foldMemoryOperand - Try folding stack slot references in Ops into MI.
259 /// @param MI     Instruction using or defining the current register.
260 /// @param Ops    Operand indices from readsWritesVirtualRegister().
261 /// @param LoadMI Load instruction to use instead of stack slot when non-null.
262 /// @return       True on success, and MI will be erased.
263 bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
264                                       const SmallVectorImpl<unsigned> &Ops,
265                                       MachineInstr *LoadMI) {
266   // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
267   // operands.
268   SmallVector<unsigned, 8> FoldOps;
269   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
270     unsigned Idx = Ops[i];
271     MachineOperand &MO = MI->getOperand(Idx);
272     if (MO.isImplicit())
273       continue;
274     // FIXME: Teach targets to deal with subregs.
275     if (MO.getSubReg())
276       return false;
277     // We cannot fold a load instruction into a def.
278     if (LoadMI && MO.isDef())
279       return false;
280     // Tied use operands should not be passed to foldMemoryOperand.
281     if (!MI->isRegTiedToDefOperand(Idx))
282       FoldOps.push_back(Idx);
283   }
284 
285   MachineInstr *FoldMI =
286                 LoadMI ? tii_.foldMemoryOperand(MI, FoldOps, LoadMI)
287                        : tii_.foldMemoryOperand(MI, FoldOps, stackSlot_);
288   if (!FoldMI)
289     return false;
290   lis_.ReplaceMachineInstrInMaps(MI, FoldMI);
291   if (!LoadMI)
292     vrm_.addSpillSlotUse(stackSlot_, FoldMI);
293   MI->eraseFromParent();
294   DEBUG(dbgs() << "\tfolded: " << *FoldMI);
295   return true;
296 }
297 
298 /// insertReload - Insert a reload of NewLI.reg before MI.
299 void InlineSpiller::insertReload(LiveInterval &NewLI,
300                                  MachineBasicBlock::iterator MI) {
301   MachineBasicBlock &MBB = *MI->getParent();
302   SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
303   tii_.loadRegFromStackSlot(MBB, MI, NewLI.reg, stackSlot_, rc_, &tri_);
304   --MI; // Point to load instruction.
305   SlotIndex LoadIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
306   vrm_.addSpillSlotUse(stackSlot_, MI);
307   DEBUG(dbgs() << "\treload:  " << LoadIdx << '\t' << *MI);
308   VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0,
309                                        lis_.getVNInfoAllocator());
310   NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI));
311 }
312 
313 /// insertSpill - Insert a spill of NewLI.reg after MI.
314 void InlineSpiller::insertSpill(LiveInterval &NewLI,
315                                 MachineBasicBlock::iterator MI) {
316   MachineBasicBlock &MBB = *MI->getParent();
317 
318   // Get the defined value. It could be an early clobber so keep the def index.
319   SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
320   VNInfo *VNI = edit_->getParent().getVNInfoAt(Idx);
321   assert(VNI && VNI->def.getDefIndex() == Idx && "Inconsistent VNInfo");
322   Idx = VNI->def;
323 
324   tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_);
325   --MI; // Point to store instruction.
326   SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
327   vrm_.addSpillSlotUse(stackSlot_, MI);
328   DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
329   VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, lis_.getVNInfoAllocator());
330   NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
331 }
332 
333 void InlineSpiller::spill(LiveInterval *li,
334                           SmallVectorImpl<LiveInterval*> &newIntervals,
335                           const SmallVectorImpl<LiveInterval*> &spillIs) {
336   LiveRangeEdit edit(*li, newIntervals, spillIs);
337   spill(edit);
338   if (VerifySpills)
339     mf_.verify(&pass_, "After inline spill");
340 }
341 
342 void InlineSpiller::spill(LiveRangeEdit &edit) {
343   edit_ = &edit;
344   assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
345          && "Trying to spill a stack slot.");
346   DEBUG(dbgs() << "Inline spilling "
347                << mri_.getRegClass(edit.getReg())->getName()
348                << ':' << edit.getParent() << "\nFrom original "
349                << PrintReg(vrm_.getOriginal(edit.getReg())) << '\n');
350   assert(edit.getParent().isSpillable() &&
351          "Attempting to spill already spilled value.");
352 
353   reMaterializeAll();
354 
355   // Remat may handle everything.
356   if (edit_->getParent().empty())
357     return;
358 
359   rc_ = mri_.getRegClass(edit.getReg());
360 
361   // Share a stack slot among all descendants of Orig.
362   unsigned Orig = vrm_.getOriginal(edit.getReg());
363   stackSlot_ = vrm_.getStackSlot(Orig);
364   if (stackSlot_ == VirtRegMap::NO_STACK_SLOT)
365     stackSlot_ = vrm_.assignVirt2StackSlot(Orig);
366 
367   if (Orig != edit.getReg())
368     vrm_.assignVirt2StackSlot(edit.getReg(), stackSlot_);
369 
370   // Update LiveStacks now that we are committed to spilling.
371   LiveInterval &stacklvr = lss_.getOrCreateInterval(stackSlot_, rc_);
372   if (!stacklvr.hasAtLeastOneValue())
373     stacklvr.getNextValue(SlotIndex(), 0, lss_.getVNInfoAllocator());
374   stacklvr.MergeRangesInAsValue(edit_->getParent(), stacklvr.getValNumInfo(0));
375 
376   // Iterate over instructions using register.
377   for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(edit.getReg());
378        MachineInstr *MI = RI.skipInstruction();) {
379 
380     // Debug values are not allowed to affect codegen.
381     if (MI->isDebugValue()) {
382       // Modify DBG_VALUE now that the value is in a spill slot.
383       uint64_t Offset = MI->getOperand(1).getImm();
384       const MDNode *MDPtr = MI->getOperand(2).getMetadata();
385       DebugLoc DL = MI->getDebugLoc();
386       if (MachineInstr *NewDV = tii_.emitFrameIndexDebugValue(mf_, stackSlot_,
387                                                            Offset, MDPtr, DL)) {
388         DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
389         MachineBasicBlock *MBB = MI->getParent();
390         MBB->insert(MBB->erase(MI), NewDV);
391       } else {
392         DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
393         MI->eraseFromParent();
394       }
395       continue;
396     }
397 
398     // Stack slot accesses may coalesce away.
399     if (coalesceStackAccess(MI))
400       continue;
401 
402     // Analyze instruction.
403     bool Reads, Writes;
404     SmallVector<unsigned, 8> Ops;
405     tie(Reads, Writes) = MI->readsWritesVirtualRegister(edit.getReg(), &Ops);
406 
407     // Attempt to fold memory ops.
408     if (foldMemoryOperand(MI, Ops))
409       continue;
410 
411     // Allocate interval around instruction.
412     // FIXME: Infer regclass from instruction alone.
413     LiveInterval &NewLI = edit.create(mri_, lis_, vrm_);
414     NewLI.markNotSpillable();
415 
416     if (Reads)
417       insertReload(NewLI, MI);
418 
419     // Rewrite instruction operands.
420     bool hasLiveDef = false;
421     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
422       MachineOperand &MO = MI->getOperand(Ops[i]);
423       MO.setReg(NewLI.reg);
424       if (MO.isUse()) {
425         if (!MI->isRegTiedToDefOperand(Ops[i]))
426           MO.setIsKill();
427       } else {
428         if (!MO.isDead())
429           hasLiveDef = true;
430       }
431     }
432 
433     // FIXME: Use a second vreg if instruction has no tied ops.
434     if (Writes && hasLiveDef)
435       insertSpill(NewLI, MI);
436 
437     DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
438   }
439 }
440