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