InlineSpiller.cpp revision 57d0f2deb0afefe69770a28937a4363e7b1f9753 
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 "spiller"
16#include "Spiller.h"
17#include "SplitKit.h"
18#include "VirtRegMap.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/CodeGen/MachineFrameInfo.h"
21#include "llvm/CodeGen/MachineFunction.h"
22#include "llvm/CodeGen/MachineLoopInfo.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Target/TargetMachine.h"
25#include "llvm/Target/TargetInstrInfo.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28
29using namespace llvm;
30
31namespace {
32class InlineSpiller : public Spiller {
33  MachineFunctionPass &pass_;
34  MachineFunction &mf_;
35  LiveIntervals &lis_;
36  MachineLoopInfo &loops_;
37  VirtRegMap &vrm_;
38  MachineFrameInfo &mfi_;
39  MachineRegisterInfo &mri_;
40  const TargetInstrInfo &tii_;
41  const TargetRegisterInfo &tri_;
42  const BitVector reserved_;
43
44  SplitAnalysis splitAnalysis_;
45
46  // Variables that are valid during spill(), but used by multiple methods.
47  LiveInterval *li_;
48  SmallVectorImpl<LiveInterval*> *newIntervals_;
49  const TargetRegisterClass *rc_;
50  int stackSlot_;
51  const SmallVectorImpl<LiveInterval*> *spillIs_;
52
53  // Values of the current interval that can potentially remat.
54  SmallPtrSet<VNInfo*, 8> reMattable_;
55
56  // Values in reMattable_ that failed to remat at some point.
57  SmallPtrSet<VNInfo*, 8> usedValues_;
58
59  ~InlineSpiller() {}
60
61public:
62  InlineSpiller(MachineFunctionPass &pass,
63                MachineFunction &mf,
64                VirtRegMap &vrm)
65    : pass_(pass),
66      mf_(mf),
67      lis_(pass.getAnalysis<LiveIntervals>()),
68      loops_(pass.getAnalysis<MachineLoopInfo>()),
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      splitAnalysis_(mf, lis_, loops_) {}
76
77  void spill(LiveInterval *li,
78             SmallVectorImpl<LiveInterval*> &newIntervals,
79             SmallVectorImpl<LiveInterval*> &spillIs);
80
81private:
82  bool split();
83
84  bool allUsesAvailableAt(const MachineInstr *OrigMI, SlotIndex OrigIdx,
85                          SlotIndex UseIdx);
86  bool reMaterializeFor(MachineBasicBlock::iterator MI);
87  void reMaterializeAll();
88
89  bool coalesceStackAccess(MachineInstr *MI);
90  bool foldMemoryOperand(MachineBasicBlock::iterator MI,
91                         const SmallVectorImpl<unsigned> &Ops);
92  void insertReload(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
93  void insertSpill(LiveInterval &NewLI, MachineBasicBlock::iterator MI);
94};
95}
96
97namespace llvm {
98Spiller *createInlineSpiller(MachineFunctionPass &pass,
99                             MachineFunction &mf,
100                             VirtRegMap &vrm) {
101  return new InlineSpiller(pass, mf, vrm);
102}
103}
104
105/// split - try splitting the current interval into pieces that may allocate
106/// separately. Return true if successful.
107bool InlineSpiller::split() {
108  splitAnalysis_.analyze(li_);
109
110  // Try splitting around loops.
111  if (const MachineLoop *loop = splitAnalysis_.getBestSplitLoop()) {
112    SplitEditor(splitAnalysis_, lis_, vrm_, *newIntervals_)
113      .splitAroundLoop(loop);
114    return true;
115  }
116
117  // Try splitting into single block intervals.
118  SplitAnalysis::BlockPtrSet blocks;
119  if (splitAnalysis_.getMultiUseBlocks(blocks)) {
120    SplitEditor(splitAnalysis_, lis_, vrm_, *newIntervals_)
121      .splitSingleBlocks(blocks);
122    return true;
123  }
124
125  // Try splitting inside a basic block.
126  if (const MachineBasicBlock *MBB = splitAnalysis_.getBlockForInsideSplit()) {
127    SplitEditor(splitAnalysis_, lis_, vrm_, *newIntervals_)
128      .splitInsideBlock(MBB);
129    return true;
130  }
131
132  return false;
133}
134
135/// allUsesAvailableAt - Return true if all registers used by OrigMI at
136/// OrigIdx are also available with the same value at UseIdx.
137bool InlineSpiller::allUsesAvailableAt(const MachineInstr *OrigMI,
138                                       SlotIndex OrigIdx,
139                                       SlotIndex UseIdx) {
140  OrigIdx = OrigIdx.getUseIndex();
141  UseIdx = UseIdx.getUseIndex();
142  for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
143    const MachineOperand &MO = OrigMI->getOperand(i);
144    if (!MO.isReg() || !MO.getReg() || MO.getReg() == li_->reg)
145      continue;
146    // Reserved registers are OK.
147    if (MO.isUndef() || !lis_.hasInterval(MO.getReg()))
148      continue;
149    // We don't want to move any defs.
150    if (MO.isDef())
151      return false;
152    // We cannot depend on virtual registers in spillIs_. They will be spilled.
153    for (unsigned si = 0, se = spillIs_->size(); si != se; ++si)
154      if ((*spillIs_)[si]->reg == MO.getReg())
155        return false;
156
157    LiveInterval &LI = lis_.getInterval(MO.getReg());
158    const VNInfo *OVNI = LI.getVNInfoAt(OrigIdx);
159    if (!OVNI)
160      continue;
161    if (OVNI != LI.getVNInfoAt(UseIdx))
162      return false;
163  }
164  return true;
165}
166
167/// reMaterializeFor - Attempt to rematerialize li_->reg before MI instead of
168/// reloading it.
169bool InlineSpiller::reMaterializeFor(MachineBasicBlock::iterator MI) {
170  SlotIndex UseIdx = lis_.getInstructionIndex(MI).getUseIndex();
171  VNInfo *OrigVNI = li_->getVNInfoAt(UseIdx);
172  if (!OrigVNI) {
173    DEBUG(dbgs() << "\tadding <undef> flags: ");
174    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
175      MachineOperand &MO = MI->getOperand(i);
176      if (MO.isReg() && MO.isUse() && MO.getReg() == li_->reg)
177        MO.setIsUndef();
178    }
179    DEBUG(dbgs() << UseIdx << '\t' << *MI);
180    return true;
181  }
182  if (!reMattable_.count(OrigVNI)) {
183    DEBUG(dbgs() << "\tusing non-remat valno " << OrigVNI->id << ": "
184                 << UseIdx << '\t' << *MI);
185    return false;
186  }
187  MachineInstr *OrigMI = lis_.getInstructionFromIndex(OrigVNI->def);
188  if (!allUsesAvailableAt(OrigMI, OrigVNI->def, UseIdx)) {
189    usedValues_.insert(OrigVNI);
190    DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << *MI);
191    return false;
192  }
193
194  // If the instruction also writes li_->reg, it had better not require the same
195  // register for uses and defs.
196  bool Reads, Writes;
197  SmallVector<unsigned, 8> Ops;
198  tie(Reads, Writes) = MI->readsWritesVirtualRegister(li_->reg, &Ops);
199  if (Writes) {
200    for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
201      MachineOperand &MO = MI->getOperand(Ops[i]);
202      if (MO.isUse() ? MI->isRegTiedToDefOperand(Ops[i]) : MO.getSubReg()) {
203        usedValues_.insert(OrigVNI);
204        DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << *MI);
205        return false;
206      }
207    }
208  }
209
210  // Alocate a new register for the remat.
211  unsigned NewVReg = mri_.createVirtualRegister(rc_);
212  vrm_.grow();
213  LiveInterval &NewLI = lis_.getOrCreateInterval(NewVReg);
214  NewLI.markNotSpillable();
215  newIntervals_->push_back(&NewLI);
216
217  // Finally we can rematerialize OrigMI before MI.
218  MachineBasicBlock &MBB = *MI->getParent();
219  tii_.reMaterialize(MBB, MI, NewLI.reg, 0, OrigMI, tri_);
220  MachineBasicBlock::iterator RematMI = MI;
221  SlotIndex DefIdx = lis_.InsertMachineInstrInMaps(--RematMI).getDefIndex();
222  DEBUG(dbgs() << "\tremat:  " << DefIdx << '\t' << *RematMI);
223
224  // Replace operands
225  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
226    MachineOperand &MO = MI->getOperand(Ops[i]);
227    if (MO.isReg() && MO.isUse() && MO.getReg() == li_->reg) {
228      MO.setReg(NewVReg);
229      MO.setIsKill();
230    }
231  }
232  DEBUG(dbgs() << "\t        " << UseIdx << '\t' << *MI);
233
234  VNInfo *DefVNI = NewLI.getNextValue(DefIdx, 0, lis_.getVNInfoAllocator());
235  NewLI.addRange(LiveRange(DefIdx, UseIdx.getDefIndex(), DefVNI));
236  DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
237  return true;
238}
239
240/// reMaterializeAll - Try to rematerialize as many uses of li_ as possible,
241/// and trim the live ranges after.
242void InlineSpiller::reMaterializeAll() {
243  // Do a quick scan of the interval values to find if any are remattable.
244  reMattable_.clear();
245  usedValues_.clear();
246  for (LiveInterval::const_vni_iterator I = li_->vni_begin(),
247       E = li_->vni_end(); I != E; ++I) {
248    VNInfo *VNI = *I;
249    if (VNI->isUnused())
250      continue;
251    MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def);
252    if (!DefMI || !tii_.isTriviallyReMaterializable(DefMI))
253      continue;
254    reMattable_.insert(VNI);
255  }
256
257  // Often, no defs are remattable.
258  if (reMattable_.empty())
259    return;
260
261  // Try to remat before all uses of li_->reg.
262  bool anyRemat = false;
263  for (MachineRegisterInfo::use_nodbg_iterator
264       RI = mri_.use_nodbg_begin(li_->reg);
265       MachineInstr *MI = RI.skipInstruction();)
266     anyRemat |= reMaterializeFor(MI);
267
268  if (!anyRemat)
269    return;
270
271  // Remove any values that were completely rematted.
272  bool anyRemoved = false;
273  for (SmallPtrSet<VNInfo*, 8>::iterator I = reMattable_.begin(),
274       E = reMattable_.end(); I != E; ++I) {
275    VNInfo *VNI = *I;
276    if (VNI->hasPHIKill() || usedValues_.count(VNI))
277      continue;
278    MachineInstr *DefMI = lis_.getInstructionFromIndex(VNI->def);
279    DEBUG(dbgs() << "\tremoving dead def: " << VNI->def << '\t' << *DefMI);
280    lis_.RemoveMachineInstrFromMaps(DefMI);
281    vrm_.RemoveMachineInstrFromMaps(DefMI);
282    DefMI->eraseFromParent();
283    VNI->def = SlotIndex();
284    anyRemoved = true;
285  }
286
287  if (!anyRemoved)
288    return;
289
290  // Removing values may cause debug uses where li_ is not live.
291  for (MachineRegisterInfo::use_iterator RI = mri_.use_begin(li_->reg);
292       MachineInstr *MI = RI.skipInstruction();) {
293    if (!MI->isDebugValue())
294      continue;
295    // Try to preserve the debug value if li_ is live immediately after it.
296    MachineBasicBlock::iterator NextMI = MI;
297    ++NextMI;
298    if (NextMI != MI->getParent()->end() && !lis_.isNotInMIMap(NextMI)) {
299      VNInfo *VNI = li_->getVNInfoAt(lis_.getInstructionIndex(NextMI));
300      if (VNI && (VNI->hasPHIKill() || usedValues_.count(VNI)))
301        continue;
302    }
303    DEBUG(dbgs() << "Removing debug info due to remat:" << "\t" << *MI);
304    MI->eraseFromParent();
305  }
306}
307
308/// If MI is a load or store of stackSlot_, it can be removed.
309bool InlineSpiller::coalesceStackAccess(MachineInstr *MI) {
310  int FI = 0;
311  unsigned reg;
312  if (!(reg = tii_.isLoadFromStackSlot(MI, FI)) &&
313      !(reg = tii_.isStoreToStackSlot(MI, FI)))
314    return false;
315
316  // We have a stack access. Is it the right register and slot?
317  if (reg != li_->reg || FI != stackSlot_)
318    return false;
319
320  DEBUG(dbgs() << "Coalescing stack access: " << *MI);
321  lis_.RemoveMachineInstrFromMaps(MI);
322  MI->eraseFromParent();
323  return true;
324}
325
326/// foldMemoryOperand - Try folding stack slot references in Ops into MI.
327/// Return true on success, and MI will be erased.
328bool InlineSpiller::foldMemoryOperand(MachineBasicBlock::iterator MI,
329                                      const SmallVectorImpl<unsigned> &Ops) {
330  // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
331  // operands.
332  SmallVector<unsigned, 8> FoldOps;
333  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
334    unsigned Idx = Ops[i];
335    MachineOperand &MO = MI->getOperand(Idx);
336    if (MO.isImplicit())
337      continue;
338    // FIXME: Teach targets to deal with subregs.
339    if (MO.getSubReg())
340      return false;
341    // Tied use operands should not be passed to foldMemoryOperand.
342    if (!MI->isRegTiedToDefOperand(Idx))
343      FoldOps.push_back(Idx);
344  }
345
346  MachineInstr *FoldMI = tii_.foldMemoryOperand(MI, FoldOps, stackSlot_);
347  if (!FoldMI)
348    return false;
349  lis_.ReplaceMachineInstrInMaps(MI, FoldMI);
350  vrm_.addSpillSlotUse(stackSlot_, FoldMI);
351  MI->eraseFromParent();
352  DEBUG(dbgs() << "\tfolded: " << *FoldMI);
353  return true;
354}
355
356/// insertReload - Insert a reload of NewLI.reg before MI.
357void InlineSpiller::insertReload(LiveInterval &NewLI,
358                                 MachineBasicBlock::iterator MI) {
359  MachineBasicBlock &MBB = *MI->getParent();
360  SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
361  tii_.loadRegFromStackSlot(MBB, MI, NewLI.reg, stackSlot_, rc_, &tri_);
362  --MI; // Point to load instruction.
363  SlotIndex LoadIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
364  vrm_.addSpillSlotUse(stackSlot_, MI);
365  DEBUG(dbgs() << "\treload:  " << LoadIdx << '\t' << *MI);
366  VNInfo *LoadVNI = NewLI.getNextValue(LoadIdx, 0,
367                                       lis_.getVNInfoAllocator());
368  NewLI.addRange(LiveRange(LoadIdx, Idx, LoadVNI));
369}
370
371/// insertSpill - Insert a spill of NewLI.reg after MI.
372void InlineSpiller::insertSpill(LiveInterval &NewLI,
373                                MachineBasicBlock::iterator MI) {
374  MachineBasicBlock &MBB = *MI->getParent();
375  SlotIndex Idx = lis_.getInstructionIndex(MI).getDefIndex();
376  tii_.storeRegToStackSlot(MBB, ++MI, NewLI.reg, true, stackSlot_, rc_, &tri_);
377  --MI; // Point to store instruction.
378  SlotIndex StoreIdx = lis_.InsertMachineInstrInMaps(MI).getDefIndex();
379  vrm_.addSpillSlotUse(stackSlot_, MI);
380  DEBUG(dbgs() << "\tspilled: " << StoreIdx << '\t' << *MI);
381  VNInfo *StoreVNI = NewLI.getNextValue(Idx, 0, lis_.getVNInfoAllocator());
382  NewLI.addRange(LiveRange(Idx, StoreIdx, StoreVNI));
383}
384
385void InlineSpiller::spill(LiveInterval *li,
386                          SmallVectorImpl<LiveInterval*> &newIntervals,
387                          SmallVectorImpl<LiveInterval*> &spillIs) {
388  DEBUG(dbgs() << "Inline spilling " << *li << "\n");
389  assert(li->isSpillable() && "Attempting to spill already spilled value.");
390  assert(!li->isStackSlot() && "Trying to spill a stack slot.");
391
392  li_ = li;
393  newIntervals_ = &newIntervals;
394  rc_ = mri_.getRegClass(li->reg);
395  spillIs_ = &spillIs;
396
397  if (split())
398    return;
399
400  reMaterializeAll();
401
402  // Remat may handle everything.
403  if (li_->empty())
404    return;
405
406  stackSlot_ = vrm_.getStackSlot(li->reg);
407  if (stackSlot_ == VirtRegMap::NO_STACK_SLOT)
408    stackSlot_ = vrm_.assignVirt2StackSlot(li->reg);
409
410  // Iterate over instructions using register.
411  for (MachineRegisterInfo::reg_iterator RI = mri_.reg_begin(li->reg);
412       MachineInstr *MI = RI.skipInstruction();) {
413
414    // Debug values are not allowed to affect codegen.
415    if (MI->isDebugValue()) {
416      // Modify DBG_VALUE now that the value is in a spill slot.
417      uint64_t Offset = MI->getOperand(1).getImm();
418      const MDNode *MDPtr = MI->getOperand(2).getMetadata();
419      DebugLoc DL = MI->getDebugLoc();
420      if (MachineInstr *NewDV = tii_.emitFrameIndexDebugValue(mf_, stackSlot_,
421                                                           Offset, MDPtr, DL)) {
422        DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
423        MachineBasicBlock *MBB = MI->getParent();
424        MBB->insert(MBB->erase(MI), NewDV);
425      } else {
426        DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
427        MI->eraseFromParent();
428      }
429      continue;
430    }
431
432    // Stack slot accesses may coalesce away.
433    if (coalesceStackAccess(MI))
434      continue;
435
436    // Analyze instruction.
437    bool Reads, Writes;
438    SmallVector<unsigned, 8> Ops;
439    tie(Reads, Writes) = MI->readsWritesVirtualRegister(li->reg, &Ops);
440
441    // Attempt to fold memory ops.
442    if (foldMemoryOperand(MI, Ops))
443      continue;
444
445    // Allocate interval around instruction.
446    // FIXME: Infer regclass from instruction alone.
447    unsigned NewVReg = mri_.createVirtualRegister(rc_);
448    vrm_.grow();
449    LiveInterval &NewLI = lis_.getOrCreateInterval(NewVReg);
450    NewLI.markNotSpillable();
451
452    if (Reads)
453      insertReload(NewLI, MI);
454
455    // Rewrite instruction operands.
456    bool hasLiveDef = false;
457    for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
458      MachineOperand &MO = MI->getOperand(Ops[i]);
459      MO.setReg(NewVReg);
460      if (MO.isUse()) {
461        if (!MI->isRegTiedToDefOperand(Ops[i]))
462          MO.setIsKill();
463      } else {
464        if (!MO.isDead())
465          hasLiveDef = true;
466      }
467    }
468
469    // FIXME: Use a second vreg if instruction has no tied ops.
470    if (Writes && hasLiveDef)
471      insertSpill(NewLI, MI);
472
473    DEBUG(dbgs() << "\tinterval: " << NewLI << '\n');
474    newIntervals.push_back(&NewLI);
475  }
476}
477