InlineSpiller.cpp revision c1d22d8adbd40c3e5d704fdae90f9ed2089bb67e 
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/MachineDominators.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
24#include "llvm/CodeGen/MachineFunction.h"
25#include "llvm/CodeGen/MachineLoopInfo.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/Target/TargetMachine.h"
28#include "llvm/Target/TargetInstrInfo.h"
29#include "llvm/Support/Debug.h"
30#include "llvm/Support/raw_ostream.h"
31
32using namespace llvm;
33
34namespace {
35class InlineSpiller : public Spiller {
36  MachineFunctionPass &Pass;
37  MachineFunction &MF;
38  LiveIntervals &LIS;
39  LiveStacks &LSS;
40  AliasAnalysis *AA;
41  MachineDominatorTree &MDT;
42  MachineLoopInfo &Loops;
43  VirtRegMap &VRM;
44  MachineFrameInfo &MFI;
45  MachineRegisterInfo &MRI;
46  const TargetInstrInfo &TII;
47  const TargetRegisterInfo &TRI;
48
49  // Variables that are valid during spill(), but used by multiple methods.
50  LiveRangeEdit *Edit;
51  LiveInterval *StackInt;
52  int StackSlot;
53  unsigned Original;
54
55  // All registers to spill to StackSlot, including the main register.
56  SmallVector<unsigned, 8> RegsToSpill;
57
58  // All COPY instructions to/from snippets.
59  // They are ignored since both operands refer to the same stack slot.
60  SmallPtrSet<MachineInstr*, 8> SnippetCopies;
61
62  // Values that failed to remat at some point.
63  SmallPtrSet<VNInfo*, 8> UsedValues;
64
65  // Information about a value that was defined by a copy from a sibling
66  // register.
67  struct SibValueInfo {
68    // True when all reaching defs were reloads: No spill is necessary.
69    bool AllDefsAreReloads;
70
71    // The preferred register to spill.
72    unsigned SpillReg;
73
74    // The value of SpillReg that should be spilled.
75    VNInfo *SpillVNI;
76
77    // A defining instruction that is not a sibling copy or a reload, or NULL.
78    // This can be used as a template for rematerialization.
79    MachineInstr *DefMI;
80
81    SibValueInfo(unsigned Reg, VNInfo *VNI)
82      : AllDefsAreReloads(false), SpillReg(Reg), SpillVNI(VNI), DefMI(0) {}
83  };
84
85  // Values in RegsToSpill defined by sibling copies.
86  typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
87  SibValueMap SibValues;
88
89  // Dead defs generated during spilling.
90  SmallVector<MachineInstr*, 8> DeadDefs;
91
92  ~InlineSpiller() {}
93
94public:
95  InlineSpiller(MachineFunctionPass &pass,
96                MachineFunction &mf,
97                VirtRegMap &vrm)
98    : Pass(pass),
99      MF(mf),
100      LIS(pass.getAnalysis<LiveIntervals>()),
101      LSS(pass.getAnalysis<LiveStacks>()),
102      AA(&pass.getAnalysis<AliasAnalysis>()),
103      MDT(pass.getAnalysis<MachineDominatorTree>()),
104      Loops(pass.getAnalysis<MachineLoopInfo>()),
105      VRM(vrm),
106      MFI(*mf.getFrameInfo()),
107      MRI(mf.getRegInfo()),
108      TII(*mf.getTarget().getInstrInfo()),
109      TRI(*mf.getTarget().getRegisterInfo()) {}
110
111  void spill(LiveRangeEdit &);
112
113private:
114  bool isSnippet(const LiveInterval &SnipLI);
115  void collectRegsToSpill();
116
117  bool isRegToSpill(unsigned Reg) {
118    return std::find(RegsToSpill.begin(),
119                     RegsToSpill.end(), Reg) != RegsToSpill.end();
120  }
121
122  bool isSibling(unsigned Reg);
123  MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
124  void analyzeSiblingValues();
125
126  bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
127  void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
128
129  void markValueUsed(LiveInterval*, VNInfo*);
130  bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI);
131  void reMaterializeAll();
132
133  bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
134  bool foldMemoryOperand(MachineBasicBlock::iterator MI,
135                         const SmallVectorImpl<unsigned> &Ops,
136                         MachineInstr *LoadMI = 0);
137  void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
138  void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
139                   MachineBasicBlock::iterator MI);
140
141  void spillAroundUses(unsigned Reg);
142};
143}
144
145namespace llvm {
146Spiller *createInlineSpiller(MachineFunctionPass &pass,
147                             MachineFunction &mf,
148                             VirtRegMap &vrm) {
149  return new InlineSpiller(pass, mf, vrm);
150}
151}
152
153//===----------------------------------------------------------------------===//
154//                                Snippets
155//===----------------------------------------------------------------------===//
156
157// When spilling a virtual register, we also spill any snippets it is connected
158// to. The snippets are small live ranges that only have a single real use,
159// leftovers from live range splitting. Spilling them enables memory operand
160// folding or tightens the live range around the single use.
161//
162// This minimizes register pressure and maximizes the store-to-load distance for
163// spill slots which can be important in tight loops.
164
165/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
166/// otherwise return 0.
167static unsigned isFullCopyOf(const MachineInstr *MI, unsigned Reg) {
168  if (!MI->isCopy())
169    return 0;
170  if (MI->getOperand(0).getSubReg() != 0)
171    return 0;
172  if (MI->getOperand(1).getSubReg() != 0)
173    return 0;
174  if (MI->getOperand(0).getReg() == Reg)
175      return MI->getOperand(1).getReg();
176  if (MI->getOperand(1).getReg() == Reg)
177      return MI->getOperand(0).getReg();
178  return 0;
179}
180
181/// isSnippet - Identify if a live interval is a snippet that should be spilled.
182/// It is assumed that SnipLI is a virtual register with the same original as
183/// Edit->getReg().
184bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
185  unsigned Reg = Edit->getReg();
186
187  // A snippet is a tiny live range with only a single instruction using it
188  // besides copies to/from Reg or spills/fills. We accept:
189  //
190  //   %snip = COPY %Reg / FILL fi#
191  //   %snip = USE %snip
192  //   %Reg = COPY %snip / SPILL %snip, fi#
193  //
194  if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
195    return false;
196
197  MachineInstr *UseMI = 0;
198
199  // Check that all uses satisfy our criteria.
200  for (MachineRegisterInfo::reg_nodbg_iterator
201         RI = MRI.reg_nodbg_begin(SnipLI.reg);
202       MachineInstr *MI = RI.skipInstruction();) {
203
204    // Allow copies to/from Reg.
205    if (isFullCopyOf(MI, Reg))
206      continue;
207
208    // Allow stack slot loads.
209    int FI;
210    if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
211      continue;
212
213    // Allow stack slot stores.
214    if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
215      continue;
216
217    // Allow a single additional instruction.
218    if (UseMI && MI != UseMI)
219      return false;
220    UseMI = MI;
221  }
222  return true;
223}
224
225/// collectRegsToSpill - Collect live range snippets that only have a single
226/// real use.
227void InlineSpiller::collectRegsToSpill() {
228  unsigned Reg = Edit->getReg();
229
230  // Main register always spills.
231  RegsToSpill.assign(1, Reg);
232  SnippetCopies.clear();
233
234  // Snippets all have the same original, so there can't be any for an original
235  // register.
236  if (Original == Reg)
237    return;
238
239  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
240       MachineInstr *MI = RI.skipInstruction();) {
241    unsigned SnipReg = isFullCopyOf(MI, Reg);
242    if (!isSibling(SnipReg))
243      continue;
244    LiveInterval &SnipLI = LIS.getInterval(SnipReg);
245    if (!isSnippet(SnipLI))
246      continue;
247    SnippetCopies.insert(MI);
248    if (!isRegToSpill(SnipReg))
249      RegsToSpill.push_back(SnipReg);
250
251    DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
252  }
253}
254
255
256//===----------------------------------------------------------------------===//
257//                            Sibling Values
258//===----------------------------------------------------------------------===//
259
260// After live range splitting, some values to be spilled may be defined by
261// copies from sibling registers. We trace the sibling copies back to the
262// original value if it still exists. We need it for rematerialization.
263//
264// Even when the value can't be rematerialized, we still want to determine if
265// the value has already been spilled, or we may want to hoist the spill from a
266// loop.
267
268bool InlineSpiller::isSibling(unsigned Reg) {
269  return TargetRegisterInfo::isVirtualRegister(Reg) &&
270           VRM.getOriginal(Reg) == Original;
271}
272
273/// traceSiblingValue - Trace a value that is about to be spilled back to the
274/// real defining instructions by looking through sibling copies. Always stay
275/// within the range of OrigVNI so the registers are known to carry the same
276/// value.
277///
278/// Determine if the value is defined by all reloads, so spilling isn't
279/// necessary - the value is already in the stack slot.
280///
281/// Return a defining instruction that may be a candidate for rematerialization.
282///
283MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
284                                               VNInfo *OrigVNI) {
285  DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
286               << UseVNI->id << '@' << UseVNI->def << '\n');
287  SmallPtrSet<VNInfo*, 8> Visited;
288  SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList;
289  WorkList.push_back(std::make_pair(UseReg, UseVNI));
290
291  // Best spill candidate seen so far. This must dominate UseVNI.
292  SibValueInfo SVI(UseReg, UseVNI);
293  MachineBasicBlock *UseMBB = LIS.getMBBFromIndex(UseVNI->def);
294  unsigned SpillDepth = Loops.getLoopDepth(UseMBB);
295  bool SeenOrigPHI = false; // Original PHI met.
296
297  do {
298    unsigned Reg;
299    VNInfo *VNI;
300    tie(Reg, VNI) = WorkList.pop_back_val();
301    if (!Visited.insert(VNI))
302      continue;
303
304    // Is this value a better spill candidate?
305    if (!isRegToSpill(Reg)) {
306      MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
307      if (MBB != UseMBB && MDT.dominates(MBB, UseMBB)) {
308        // This is a valid spill location dominating UseVNI.
309        // Prefer to spill at a smaller loop depth.
310        unsigned Depth = Loops.getLoopDepth(MBB);
311        if (Depth < SpillDepth) {
312          DEBUG(dbgs() << "  spill depth " << Depth << ": " << PrintReg(Reg)
313                       << ':' << VNI->id << '@' << VNI->def << '\n');
314          SVI.SpillReg = Reg;
315          SVI.SpillVNI = VNI;
316          SpillDepth = Depth;
317        }
318      }
319    }
320
321    // Trace through PHI-defs created by live range splitting.
322    if (VNI->isPHIDef()) {
323      if (VNI->def == OrigVNI->def) {
324        DEBUG(dbgs() << "  orig phi value " << PrintReg(Reg) << ':'
325                     << VNI->id << '@' << VNI->def << '\n');
326        SeenOrigPHI = true;
327        continue;
328      }
329      // Get values live-out of predecessors.
330      LiveInterval &LI = LIS.getInterval(Reg);
331      MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
332      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
333             PE = MBB->pred_end(); PI != PE; ++PI) {
334        VNInfo *PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot());
335        if (PVNI)
336          WorkList.push_back(std::make_pair(Reg, PVNI));
337      }
338      continue;
339    }
340
341    MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
342    assert(MI && "Missing def");
343
344    // Trace through sibling copies.
345    if (unsigned SrcReg = isFullCopyOf(MI, Reg)) {
346      if (isSibling(SrcReg)) {
347        LiveInterval &SrcLI = LIS.getInterval(SrcReg);
348        VNInfo *SrcVNI = SrcLI.getVNInfoAt(VNI->def.getUseIndex());
349        assert(SrcVNI && "Copy from non-existing value");
350        DEBUG(dbgs() << "  copy of " << PrintReg(SrcReg) << ':'
351                     << SrcVNI->id << '@' << SrcVNI->def << '\n');
352        WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
353        continue;
354      }
355    }
356
357    // Track reachable reloads.
358    int FI;
359    if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) {
360      DEBUG(dbgs() << "  reload " << PrintReg(Reg) << ':'
361                   << VNI->id << "@" << VNI->def << '\n');
362      SVI.AllDefsAreReloads = true;
363      continue;
364    }
365
366    // We have an 'original' def. Don't record trivial cases.
367    if (VNI == UseVNI) {
368      DEBUG(dbgs() << "Not a sibling copy.\n");
369      return MI;
370    }
371
372    // Potential remat candidate.
373    DEBUG(dbgs() << "  def " << PrintReg(Reg) << ':'
374                 << VNI->id << '@' << VNI->def << '\t' << *MI);
375    SVI.DefMI = MI;
376  } while (!WorkList.empty());
377
378  if (SeenOrigPHI || SVI.DefMI)
379    SVI.AllDefsAreReloads = false;
380
381  DEBUG({
382    if (SVI.AllDefsAreReloads)
383      dbgs() << "All defs are reloads.\n";
384    else
385      dbgs() << "Prefer to spill " << PrintReg(SVI.SpillReg) << ':'
386             << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def << '\n';
387  });
388  SibValues.insert(std::make_pair(UseVNI, SVI));
389  return SVI.DefMI;
390}
391
392/// analyzeSiblingValues - Trace values defined by sibling copies back to
393/// something that isn't a sibling copy.
394///
395/// Keep track of values that may be rematerializable.
396void InlineSpiller::analyzeSiblingValues() {
397  SibValues.clear();
398
399  // No siblings at all?
400  if (Edit->getReg() == Original)
401    return;
402
403  LiveInterval &OrigLI = LIS.getInterval(Original);
404  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
405    unsigned Reg = RegsToSpill[i];
406    LiveInterval &LI = LIS.getInterval(Reg);
407    for (LiveInterval::const_vni_iterator VI = LI.vni_begin(),
408         VE = LI.vni_end(); VI != VE; ++VI) {
409      VNInfo *VNI = *VI;
410      if (VNI->isUnused())
411        continue;
412      MachineInstr *DefMI = 0;
413      // Check possible sibling copies.
414      if (VNI->isPHIDef() || VNI->getCopy()) {
415        VNInfo *OrigVNI = OrigLI.getVNInfoAt(VNI->def);
416        if (OrigVNI->def != VNI->def)
417          DefMI = traceSiblingValue(Reg, VNI, OrigVNI);
418      }
419      if (!DefMI && !VNI->isPHIDef())
420        DefMI = LIS.getInstructionFromIndex(VNI->def);
421      if (DefMI)
422        Edit->checkRematerializable(VNI, DefMI, TII, AA);
423    }
424  }
425}
426
427/// hoistSpill - Given a sibling copy that defines a value to be spilled, insert
428/// a spill at a better location.
429bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) {
430  SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
431  VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getDefIndex());
432  assert(VNI && VNI->def == Idx.getDefIndex() && "Not defined by copy");
433  SibValueMap::const_iterator I = SibValues.find(VNI);
434  if (I == SibValues.end())
435    return false;
436
437  const SibValueInfo &SVI = I->second;
438
439  // Let the normal folding code deal with the boring case.
440  if (!SVI.AllDefsAreReloads && SVI.SpillVNI == VNI)
441    return false;
442
443  // Conservatively extend the stack slot range to the range of the original
444  // value. We may be able to do better with stack slot coloring by being more
445  // careful here.
446  assert(StackInt && "No stack slot assigned yet.");
447  LiveInterval &OrigLI = LIS.getInterval(Original);
448  VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
449  StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
450  DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
451               << *StackInt << '\n');
452
453  // Already spilled everywhere.
454  if (SVI.AllDefsAreReloads)
455    return true;
456
457  // We are going to spill SVI.SpillVNI immediately after its def, so clear out
458  // any later spills of the same value.
459  eliminateRedundantSpills(LIS.getInterval(SVI.SpillReg), SVI.SpillVNI);
460
461  MachineBasicBlock *MBB = LIS.getMBBFromIndex(SVI.SpillVNI->def);
462  MachineBasicBlock::iterator MII;
463  if (SVI.SpillVNI->isPHIDef())
464    MII = MBB->SkipPHIsAndLabels(MBB->begin());
465  else {
466    MII = LIS.getInstructionFromIndex(SVI.SpillVNI->def);
467    ++MII;
468  }
469  // Insert spill without kill flag immediately after def.
470  TII.storeRegToStackSlot(*MBB, MII, SVI.SpillReg, false, StackSlot,
471                          MRI.getRegClass(SVI.SpillReg), &TRI);
472  --MII; // Point to store instruction.
473  LIS.InsertMachineInstrInMaps(MII);
474  VRM.addSpillSlotUse(StackSlot, MII);
475  DEBUG(dbgs() << "\thoisted: " << SVI.SpillVNI->def << '\t' << *MII);
476  return true;
477}
478
479/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
480/// redundant spills of this value in SLI.reg and sibling copies.
481void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
482  assert(VNI && "Missing value");
483  SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
484  WorkList.push_back(std::make_pair(&SLI, VNI));
485  assert(StackInt && "No stack slot assigned yet.");
486
487  do {
488    LiveInterval *LI;
489    tie(LI, VNI) = WorkList.pop_back_val();
490    unsigned Reg = LI->reg;
491    DEBUG(dbgs() << "Checking redundant spills for " << PrintReg(Reg) << ':'
492                 << VNI->id << '@' << VNI->def << '\n');
493
494    // Regs to spill are taken care of.
495    if (isRegToSpill(Reg))
496      continue;
497
498    // Add all of VNI's live range to StackInt.
499    StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
500    DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
501
502    // Find all spills and copies of VNI.
503    for (MachineRegisterInfo::use_nodbg_iterator UI = MRI.use_nodbg_begin(Reg);
504         MachineInstr *MI = UI.skipInstruction();) {
505      if (!MI->isCopy() && !MI->getDesc().mayStore())
506        continue;
507      SlotIndex Idx = LIS.getInstructionIndex(MI);
508      if (LI->getVNInfoAt(Idx) != VNI)
509        continue;
510
511      // Follow sibling copies down the dominator tree.
512      if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
513        if (isSibling(DstReg)) {
514           LiveInterval &DstLI = LIS.getInterval(DstReg);
515           VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getDefIndex());
516           assert(DstVNI && "Missing defined value");
517           assert(DstVNI->def == Idx.getDefIndex() && "Wrong copy def slot");
518           WorkList.push_back(std::make_pair(&DstLI, DstVNI));
519        }
520        continue;
521      }
522
523      // Erase spills.
524      int FI;
525      if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
526        DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << *MI);
527        // eliminateDeadDefs won't normally remove stores, so switch opcode.
528        MI->setDesc(TII.get(TargetOpcode::KILL));
529        DeadDefs.push_back(MI);
530      }
531    }
532  } while (!WorkList.empty());
533}
534
535
536//===----------------------------------------------------------------------===//
537//                            Rematerialization
538//===----------------------------------------------------------------------===//
539
540/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
541/// instruction cannot be eliminated. See through snippet copies
542void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
543  SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
544  WorkList.push_back(std::make_pair(LI, VNI));
545  do {
546    tie(LI, VNI) = WorkList.pop_back_val();
547    if (!UsedValues.insert(VNI))
548      continue;
549
550    if (VNI->isPHIDef()) {
551      MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
552      for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
553             PE = MBB->pred_end(); PI != PE; ++PI) {
554        VNInfo *PVNI = LI->getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot());
555        if (PVNI)
556          WorkList.push_back(std::make_pair(LI, PVNI));
557      }
558      continue;
559    }
560
561    // Follow snippet copies.
562    MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
563    if (!SnippetCopies.count(MI))
564      continue;
565    LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
566    assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
567    VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getUseIndex());
568    assert(SnipVNI && "Snippet undefined before copy");
569    WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
570  } while (!WorkList.empty());
571}
572
573/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
574bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg,
575                                     MachineBasicBlock::iterator MI) {
576  SlotIndex UseIdx = LIS.getInstructionIndex(MI).getUseIndex();
577  VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx);
578
579  if (!ParentVNI) {
580    DEBUG(dbgs() << "\tadding <undef> flags: ");
581    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
582      MachineOperand &MO = MI->getOperand(i);
583      if (MO.isReg() && MO.isUse() && MO.getReg() == Edit->getReg())
584        MO.setIsUndef();
585    }
586    DEBUG(dbgs() << UseIdx << '\t' << *MI);
587    return true;
588  }
589
590  if (SnippetCopies.count(MI))
591    return false;
592
593  // Use an OrigVNI from traceSiblingValue when ParentVNI is a sibling copy.
594  LiveRangeEdit::Remat RM(ParentVNI);
595  SibValueMap::const_iterator SibI = SibValues.find(ParentVNI);
596  if (SibI != SibValues.end())
597    RM.OrigMI = SibI->second.DefMI;
598  if (!Edit->canRematerializeAt(RM, UseIdx, false, LIS)) {
599    markValueUsed(&VirtReg, ParentVNI);
600    DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
601    return false;
602  }
603
604  // If the instruction also writes Edit->getReg(), it had better not require
605  // the same register for uses and defs.
606  bool Reads, Writes;
607  SmallVector<unsigned, 8> Ops;
608  tie(Reads, Writes) = MI->readsWritesVirtualRegister(Edit->getReg(), &Ops);
609  if (Writes) {
610    for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
611      MachineOperand &MO = MI->getOperand(Ops[i]);
612      if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) {
613        markValueUsed(&VirtReg, ParentVNI);
614        DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
615        return false;
616      }
617    }
618  }
619
620  // Before rematerializing into a register for a single instruction, try to
621  // fold a load into the instruction. That avoids allocating a new register.
622  if (RM.OrigMI->getDesc().canFoldAsLoad() &&
623      foldMemoryOperand(MI, Ops, RM.OrigMI)) {
624    Edit->markRematerialized(RM.ParentVNI);
625    return true;
626  }
627
628  // Alocate a new register for the remat.
629  LiveInterval &NewLI = Edit->create(LIS, VRM);
630  NewLI.markNotSpillable();
631
632  // Rematting for a copy: Set allocation hint to be the destination register.
633  if (MI->isCopy())
634    MRI.setRegAllocationHint(NewLI.reg, 0, MI->getOperand(0).getReg());
635
636  // Finally we can rematerialize OrigMI before MI.
637  SlotIndex DefIdx = Edit->rematerializeAt(*MI->getParent(), MI, NewLI.reg, RM,
638                                           LIS, TII, TRI);
639  DEBUG(dbgs() << "\tremat:  " << DefIdx << '\t'
640               << *LIS.getInstructionFromIndex(DefIdx));
641
642  // Replace operands
643  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
644    MachineOperand &MO = MI->getOperand(Ops[i]);
645    if (MO.isReg() && MO.isUse() && MO.getReg() == Edit->getReg()) {
646      MO.setReg(NewLI.reg);
647      MO.setIsKill();
648    }
649  }
650  DEBUG(dbgs() << "\t        " << UseIdx << '\t' << *MI);
651
652  VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, LIS.getVNInfoAllocator());
653  NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
654  DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
655  return true;
656}
657
658/// reMaterializeAll - Try to rematerialize as many uses as possible,
659/// and trim the live ranges after.
660void InlineSpiller::reMaterializeAll() {
661  // analyzeSiblingValues has already tested all relevant defining instructions.
662  if (!Edit->anyRematerializable(LIS, TII, AA))
663    return;
664
665  UsedValues.clear();
666
667  // Try to remat before all uses of snippets.
668  bool anyRemat = false;
669  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
670    unsigned Reg = RegsToSpill[i];
671    LiveInterval &LI = LIS.getInterval(Reg);
672    for (MachineRegisterInfo::use_nodbg_iterator
673         RI = MRI.use_nodbg_begin(Reg);
674         MachineInstr *MI = RI.skipInstruction();)
675      anyRemat |= reMaterializeFor(LI, MI);
676  }
677  if (!anyRemat)
678    return;
679
680  // Remove any values that were completely rematted.
681  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i) {
682    unsigned Reg = RegsToSpill[i];
683    LiveInterval &LI = LIS.getInterval(Reg);
684    for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
685         I != E; ++I) {
686      VNInfo *VNI = *I;
687      if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
688        continue;
689      MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
690      MI->addRegisterDead(Reg, &TRI);
691      if (!MI->allDefsAreDead())
692        continue;
693      DEBUG(dbgs() << "All defs dead: " << *MI);
694      DeadDefs.push_back(MI);
695    }
696  }
697
698  // Eliminate dead code after remat. Note that some snippet copies may be
699  // deleted here.
700  if (DeadDefs.empty())
701    return;
702  DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
703  Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII);
704
705  // Get rid of deleted and empty intervals.
706  for (unsigned i = RegsToSpill.size(); i != 0; --i) {
707    unsigned Reg = RegsToSpill[i-1];
708    if (!LIS.hasInterval(Reg)) {
709      RegsToSpill.erase(RegsToSpill.begin() + (i - 1));
710      continue;
711    }
712    LiveInterval &LI = LIS.getInterval(Reg);
713    if (!LI.empty())
714      continue;
715    Edit->eraseVirtReg(Reg, LIS);
716    RegsToSpill.erase(RegsToSpill.begin() + (i - 1));
717  }
718  DEBUG(dbgs() << RegsToSpill.size() << " registers to spill after remat.\n");
719}
720
721/// If MI is a load or store of StackSlot, it can be removed.
722bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
723  int FI = 0;
724  unsigned InstrReg;
725  if (!(InstrReg = TII.isLoadFromStackSlot(MI, FI)) &&
726      !(InstrReg = TII.isStoreToStackSlot(MI, FI)))
727    return false;
728
729  // We have a stack access. Is it the right register and slot?
730  if (InstrReg != Reg || FI != StackSlot)
731    return false;
732
733  DEBUG(dbgs() << "Coalescing stack access: " << *MI);
734  LIS.RemoveMachineInstrFromMaps(MI);
735  MI->eraseFromParent();
736  return true;
737}
738
739/// foldMemoryOperand - Try folding stack slot references in Ops into MI.
740/// @param MI     Instruction using or defining the current register.
741/// @param Ops    Operand indices from readsWritesVirtualRegister().
742/// @param LoadMI Load instruction to use instead of stack slot when non-null.
743/// @return       True on success, and MI will be erased.
744bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
745                                      const SmallVectorImpl<unsigned> &Ops,
746                                      MachineInstr *LoadMI) {
747  // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
748  // operands.
749  SmallVector<unsigned, 8> FoldOps;
750  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
751    unsigned Idx = Ops[i];
752    MachineOperand &MO = MI->getOperand(Idx);
753    if (MO.isImplicit())
754      continue;
755    // FIXME: Teach targets to deal with subregs.
756    if (MO.getSubReg())
757      return false;
758    // We cannot fold a load instruction into a def.
759    if (LoadMI && MO.isDef())
760      return false;
761    // Tied use operands should not be passed to foldMemoryOperand.
762    if (!MI->isRegTiedToDefOperand(Idx))
763      FoldOps.push_back(Idx);
764  }
765
766  MachineInstr *FoldMI =
767                LoadMI ? TII.foldMemoryOperand(MI, FoldOps, LoadMI)
768                       : TII.foldMemoryOperand(MI, FoldOps, StackSlot);
769  if (!FoldMI)
770    return false;
771  LIS.ReplaceMachineInstrInMaps(MI, FoldMI);
772  if (!LoadMI)
773    VRM.addSpillSlotUse(StackSlot, FoldMI);
774  MI->eraseFromParent();
775  DEBUG(dbgs() << "\tfolded: " << *FoldMI);
776  return true;
777}
778
779/// insertReload - Insert a reload of NewLI.reg before MI.
780void InlineSpiller::insertReload(LiveInterval &NewLI,
781                                 MachineBasicBlock::iterator MI) {
782  MachineBasicBlock &MBB = *MI->getParent();
783  SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
784  TII.loadRegFromStackSlot(MBB, MI, NewLI.reg, StackSlot,
785                           MRI.getRegClass(NewLI.reg), &TRI);
786  --MI; // Point to load instruction.
787  SlotIndex LoadIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex();
788  VRM.addSpillSlotUse(StackSlot, MI);
789  DEBUG(dbgs() << "\treload:  " << LoadIdx << '\t' << *MI);
790  VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0,
791                                       LIS.getVNInfoAllocator());
792  NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI));
793}
794
795/// insertSpill - Insert a spill of NewLI.reg after MI.
796void InlineSpiller::insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
797                                MachineBasicBlock::iterator MI) {
798  MachineBasicBlock &MBB = *MI->getParent();
799
800  // Get the defined value. It could be an early clobber so keep the def index.
801  SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
802  VNInfo *VNI = OldLI.getVNInfoAt(Idx);
803  assert(VNI && VNI->def.getDefIndex() == Idx && "Inconsistent VNInfo");
804  Idx = VNI->def;
805
806  TII.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, StackSlot,
807                          MRI.getRegClass(NewLI.reg), &TRI);
808  --MI; // Point to store instruction.
809  SlotIndex StoreIdx = LIS.InsertMachineInstrInMaps(MI).getDefIndex();
810  VRM.addSpillSlotUse(StackSlot, MI);
811  DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
812  VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, LIS.getVNInfoAllocator());
813  NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
814}
815
816/// spillAroundUses - insert spill code around each use of Reg.
817void InlineSpiller::spillAroundUses(unsigned Reg) {
818  LiveInterval &OldLI = LIS.getInterval(Reg);
819
820  // Iterate over instructions using Reg.
821  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Reg);
822       MachineInstr *MI = RI.skipInstruction();) {
823
824    // Debug values are not allowed to affect codegen.
825    if (MI->isDebugValue()) {
826      // Modify DBG_VALUE now that the value is in a spill slot.
827      uint64_t Offset = MI->getOperand(1).getImm();
828      const MDNode *MDPtr = MI->getOperand(2).getMetadata();
829      DebugLoc DL = MI->getDebugLoc();
830      if (MachineInstr *NewDV = TII.emitFrameIndexDebugValue(MF, StackSlot,
831                                                           Offset, MDPtr, DL)) {
832        DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
833        MachineBasicBlock *MBB = MI->getParent();
834        MBB->insert(MBB->erase(MI), NewDV);
835      } else {
836        DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
837        MI->eraseFromParent();
838      }
839      continue;
840    }
841
842    // Ignore copies to/from snippets. We'll delete them.
843    if (SnippetCopies.count(MI))
844      continue;
845
846    // Stack slot accesses may coalesce away.
847    if (coalesceStackAccess(MI, Reg))
848      continue;
849
850    // Analyze instruction.
851    bool Reads, Writes;
852    SmallVector<unsigned, 8> Ops;
853    tie(Reads, Writes) = MI->readsWritesVirtualRegister(Reg, &Ops);
854
855    // Check for a sibling copy.
856    unsigned SibReg = isFullCopyOf(MI, Reg);
857    if (SibReg && isSibling(SibReg)) {
858      if (Writes) {
859        // Hoist the spill of a sib-reg copy.
860        if (hoistSpill(OldLI, MI)) {
861          // This COPY is now dead, the value is already in the stack slot.
862          MI->getOperand(0).setIsDead();
863          DeadDefs.push_back(MI);
864          continue;
865        }
866      } else {
867        // This is a reload for a sib-reg copy. Drop spills downstream.
868        SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
869        LiveInterval &SibLI = LIS.getInterval(SibReg);
870        eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
871        // The COPY will fold to a reload below.
872      }
873    }
874
875    // Attempt to fold memory ops.
876    if (foldMemoryOperand(MI, Ops))
877      continue;
878
879    // Allocate interval around instruction.
880    // FIXME: Infer regclass from instruction alone.
881    LiveInterval &NewLI = Edit->createFrom(Reg, LIS, VRM);
882    NewLI.markNotSpillable();
883
884    if (Reads)
885      insertReload(NewLI, MI);
886
887    // Rewrite instruction operands.
888    bool hasLiveDef = false;
889    for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
890      MachineOperand &MO = MI->getOperand(Ops[i]);
891      MO.setReg(NewLI.reg);
892      if (MO.isUse()) {
893        if (!MI->isRegTiedToDefOperand(Ops[i]))
894          MO.setIsKill();
895      } else {
896        if (!MO.isDead())
897          hasLiveDef = true;
898      }
899    }
900
901    // FIXME: Use a second vreg if instruction has no tied ops.
902    if (Writes && hasLiveDef)
903      insertSpill(NewLI, OldLI, MI);
904
905    DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
906  }
907}
908
909void InlineSpiller::spill(LiveRangeEdit &edit) {
910  Edit = &edit;
911  assert(!TargetRegisterInfo::isStackSlot(edit.getReg())
912         && "Trying to spill a stack slot.");
913  // Share a stack slot among all descendants of Original.
914  Original = VRM.getOriginal(edit.getReg());
915  StackSlot = VRM.getStackSlot(Original);
916  StackInt = 0;
917
918  DEBUG(dbgs() << "Inline spilling "
919               << MRI.getRegClass(edit.getReg())->getName()
920               << ':' << edit.getParent() << "\nFrom original "
921               << LIS.getInterval(Original) << '\n');
922  assert(edit.getParent().isSpillable() &&
923         "Attempting to spill already spilled value.");
924  assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
925
926  collectRegsToSpill();
927  analyzeSiblingValues();
928  reMaterializeAll();
929
930  // Remat may handle everything.
931  if (RegsToSpill.empty())
932    return;
933
934  // Update LiveStacks now that we are committed to spilling.
935  if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
936    StackSlot = VRM.assignVirt2StackSlot(Original);
937    StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
938    StackInt->getNextValue(SlotIndex(), 0, LSS.getVNInfoAllocator());
939  } else
940    StackInt = &LSS.getInterval(StackSlot);
941
942  if (Original != edit.getReg())
943    VRM.assignVirt2StackSlot(edit.getReg(), StackSlot);
944
945  assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
946  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
947    StackInt->MergeRangesInAsValue(LIS.getInterval(RegsToSpill[i]),
948                                   StackInt->getValNumInfo(0));
949  DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
950
951  // Spill around uses of all RegsToSpill.
952  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
953    spillAroundUses(RegsToSpill[i]);
954
955  // Hoisted spills may cause dead code.
956  if (!DeadDefs.empty()) {
957    DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
958    Edit->eliminateDeadDefs(DeadDefs, LIS, VRM, TII);
959  }
960
961  // Finally delete the SnippetCopies.
962  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(edit.getReg());
963       MachineInstr *MI = RI.skipInstruction();) {
964    assert(SnippetCopies.count(MI) && "Remaining use wasn't a snippet copy");
965    // FIXME: Do this with a LiveRangeEdit callback.
966    VRM.RemoveMachineInstrFromMaps(MI);
967    LIS.RemoveMachineInstrFromMaps(MI);
968    MI->eraseFromParent();
969  }
970
971  for (unsigned i = 0, e = RegsToSpill.size(); i != e; ++i)
972    edit.eraseVirtReg(RegsToSpill[i], LIS);
973}
974