Spiller.cpp revision e9157e10cd2be2b3dbaf26baa925765562819266 
1//===-- llvm/CodeGen/Spiller.cpp -  Spiller -------------------------------===//
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#define DEBUG_TYPE "spiller"
11
12#include "Spiller.h"
13#include "VirtRegMap.h"
14#include "llvm/CodeGen/LiveIntervalAnalysis.h"
15#include "llvm/CodeGen/LiveStackAnalysis.h"
16#include "llvm/CodeGen/MachineFrameInfo.h"
17#include "llvm/CodeGen/MachineFunction.h"
18#include "llvm/CodeGen/MachineInstrBuilder.h"
19#include "llvm/CodeGen/MachineLoopInfo.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/Target/TargetMachine.h"
22#include "llvm/Target/TargetInstrInfo.h"
23#include "llvm/Support/CommandLine.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27#include <set>
28
29using namespace llvm;
30
31namespace {
32  enum SpillerName { trivial, standard, splitting, inline_ };
33}
34
35static cl::opt<SpillerName>
36spillerOpt("spiller",
37           cl::desc("Spiller to use: (default: standard)"),
38           cl::Prefix,
39           cl::values(clEnumVal(trivial,   "trivial spiller"),
40                      clEnumVal(standard,  "default spiller"),
41                      clEnumVal(splitting, "splitting spiller"),
42                      clEnumValN(inline_,  "inline", "inline spiller"),
43                      clEnumValEnd),
44           cl::init(standard));
45
46// Spiller virtual destructor implementation.
47Spiller::~Spiller() {}
48
49namespace {
50
51/// Utility class for spillers.
52class SpillerBase : public Spiller {
53protected:
54  MachineFunctionPass *pass;
55  MachineFunction *mf;
56  VirtRegMap *vrm;
57  LiveIntervals *lis;
58  MachineFrameInfo *mfi;
59  MachineRegisterInfo *mri;
60  const TargetInstrInfo *tii;
61  const TargetRegisterInfo *tri;
62
63  /// Construct a spiller base.
64  SpillerBase(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
65    : pass(&pass), mf(&mf), vrm(&vrm)
66  {
67    lis = &pass.getAnalysis<LiveIntervals>();
68    mfi = mf.getFrameInfo();
69    mri = &mf.getRegInfo();
70    tii = mf.getTarget().getInstrInfo();
71    tri = mf.getTarget().getRegisterInfo();
72  }
73
74  /// Add spill ranges for every use/def of the live interval, inserting loads
75  /// immediately before each use, and stores after each def. No folding or
76  /// remat is attempted.
77  void trivialSpillEverywhere(LiveInterval *li,
78                              SmallVectorImpl<LiveInterval*> &newIntervals) {
79    DEBUG(dbgs() << "Spilling everywhere " << *li << "\n");
80
81    assert(li->weight != HUGE_VALF &&
82           "Attempting to spill already spilled value.");
83
84    assert(!li->isStackSlot() &&
85           "Trying to spill a stack slot.");
86
87    DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n");
88
89    const TargetRegisterClass *trc = mri->getRegClass(li->reg);
90    unsigned ss = vrm->assignVirt2StackSlot(li->reg);
91
92    // Iterate over reg uses/defs.
93    for (MachineRegisterInfo::reg_iterator
94         regItr = mri->reg_begin(li->reg); regItr != mri->reg_end();) {
95
96      // Grab the use/def instr.
97      MachineInstr *mi = &*regItr;
98
99      DEBUG(dbgs() << "  Processing " << *mi);
100
101      // Step regItr to the next use/def instr.
102      do {
103        ++regItr;
104      } while (regItr != mri->reg_end() && (&*regItr == mi));
105
106      // Collect uses & defs for this instr.
107      SmallVector<unsigned, 2> indices;
108      bool hasUse = false;
109      bool hasDef = false;
110      for (unsigned i = 0; i != mi->getNumOperands(); ++i) {
111        MachineOperand &op = mi->getOperand(i);
112        if (!op.isReg() || op.getReg() != li->reg)
113          continue;
114        hasUse |= mi->getOperand(i).isUse();
115        hasDef |= mi->getOperand(i).isDef();
116        indices.push_back(i);
117      }
118
119      // Create a new vreg & interval for this instr.
120      unsigned newVReg = mri->createVirtualRegister(trc);
121      vrm->grow();
122      vrm->assignVirt2StackSlot(newVReg, ss);
123      LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
124      newLI->weight = HUGE_VALF;
125
126      // Update the reg operands & kill flags.
127      for (unsigned i = 0; i < indices.size(); ++i) {
128        unsigned mopIdx = indices[i];
129        MachineOperand &mop = mi->getOperand(mopIdx);
130        mop.setReg(newVReg);
131        if (mop.isUse() && !mi->isRegTiedToDefOperand(mopIdx)) {
132          mop.setIsKill(true);
133        }
134      }
135      assert(hasUse || hasDef);
136
137      // Insert reload if necessary.
138      MachineBasicBlock::iterator miItr(mi);
139      if (hasUse) {
140        tii->loadRegFromStackSlot(*mi->getParent(), miItr, newVReg, ss, trc,
141                                  tri);
142        MachineInstr *loadInstr(prior(miItr));
143        SlotIndex loadIndex =
144          lis->InsertMachineInstrInMaps(loadInstr).getDefIndex();
145        vrm->addSpillSlotUse(ss, loadInstr);
146        SlotIndex endIndex = loadIndex.getNextIndex();
147        VNInfo *loadVNI =
148          newLI->getNextValue(loadIndex, 0, lis->getVNInfoAllocator());
149        newLI->addRange(LiveRange(loadIndex, endIndex, loadVNI));
150      }
151
152      // Insert store if necessary.
153      if (hasDef) {
154        tii->storeRegToStackSlot(*mi->getParent(), llvm::next(miItr), newVReg,
155                                 true, ss, trc, tri);
156        MachineInstr *storeInstr(llvm::next(miItr));
157        SlotIndex storeIndex =
158          lis->InsertMachineInstrInMaps(storeInstr).getDefIndex();
159        vrm->addSpillSlotUse(ss, storeInstr);
160        SlotIndex beginIndex = storeIndex.getPrevIndex();
161        VNInfo *storeVNI =
162          newLI->getNextValue(beginIndex, 0, lis->getVNInfoAllocator());
163        newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI));
164      }
165
166      newIntervals.push_back(newLI);
167    }
168  }
169};
170
171} // end anonymous namespace
172
173namespace {
174
175/// Spills any live range using the spill-everywhere method with no attempt at
176/// folding.
177class TrivialSpiller : public SpillerBase {
178public:
179
180  TrivialSpiller(MachineFunctionPass &pass, MachineFunction &mf,
181                 VirtRegMap &vrm)
182    : SpillerBase(pass, mf, vrm) {}
183
184  void spill(LiveInterval *li,
185             SmallVectorImpl<LiveInterval*> &newIntervals,
186             const SmallVectorImpl<LiveInterval*> &) {
187    // Ignore spillIs - we don't use it.
188    trivialSpillEverywhere(li, newIntervals);
189  }
190};
191
192} // end anonymous namespace
193
194namespace {
195
196/// Falls back on LiveIntervals::addIntervalsForSpills.
197class StandardSpiller : public Spiller {
198protected:
199  MachineFunction *mf;
200  LiveIntervals *lis;
201  LiveStacks *lss;
202  MachineLoopInfo *loopInfo;
203  VirtRegMap *vrm;
204public:
205  StandardSpiller(MachineFunctionPass &pass, MachineFunction &mf,
206                  VirtRegMap &vrm)
207    : mf(&mf),
208      lis(&pass.getAnalysis<LiveIntervals>()),
209      lss(&pass.getAnalysis<LiveStacks>()),
210      loopInfo(pass.getAnalysisIfAvailable<MachineLoopInfo>()),
211      vrm(&vrm) {}
212
213  /// Falls back on LiveIntervals::addIntervalsForSpills.
214  void spill(LiveInterval *li,
215             SmallVectorImpl<LiveInterval*> &newIntervals,
216             const SmallVectorImpl<LiveInterval*> &spillIs) {
217    std::vector<LiveInterval*> added =
218      lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm);
219    newIntervals.insert(newIntervals.end(), added.begin(), added.end());
220
221    // Update LiveStacks.
222    int SS = vrm->getStackSlot(li->reg);
223    if (SS == VirtRegMap::NO_STACK_SLOT)
224      return;
225    const TargetRegisterClass *RC = mf->getRegInfo().getRegClass(li->reg);
226    LiveInterval &SI = lss->getOrCreateInterval(SS, RC);
227    if (!SI.hasAtLeastOneValue())
228      SI.getNextValue(SlotIndex(), 0, lss->getVNInfoAllocator());
229    SI.MergeRangesInAsValue(*li, SI.getValNumInfo(0));
230  }
231};
232
233} // end anonymous namespace
234
235namespace {
236
237/// When a call to spill is placed this spiller will first try to break the
238/// interval up into its component values (one new interval per value).
239/// If this fails, or if a call is placed to spill a previously split interval
240/// then the spiller falls back on the standard spilling mechanism.
241class SplittingSpiller : public StandardSpiller {
242public:
243  SplittingSpiller(MachineFunctionPass &pass, MachineFunction &mf,
244                   VirtRegMap &vrm)
245    : StandardSpiller(pass, mf, vrm) {
246    mri = &mf.getRegInfo();
247    tii = mf.getTarget().getInstrInfo();
248    tri = mf.getTarget().getRegisterInfo();
249  }
250
251  void spill(LiveInterval *li,
252             SmallVectorImpl<LiveInterval*> &newIntervals,
253             const SmallVectorImpl<LiveInterval*> &spillIs) {
254    if (worthTryingToSplit(li))
255      tryVNISplit(li);
256    else
257      StandardSpiller::spill(li, newIntervals, spillIs);
258  }
259
260private:
261
262  MachineRegisterInfo *mri;
263  const TargetInstrInfo *tii;
264  const TargetRegisterInfo *tri;
265  DenseSet<LiveInterval*> alreadySplit;
266
267  bool worthTryingToSplit(LiveInterval *li) const {
268    return (!alreadySplit.count(li) && li->getNumValNums() > 1);
269  }
270
271  /// Try to break a LiveInterval into its component values.
272  std::vector<LiveInterval*> tryVNISplit(LiveInterval *li) {
273
274    DEBUG(dbgs() << "Trying VNI split of %reg" << *li << "\n");
275
276    std::vector<LiveInterval*> added;
277    SmallVector<VNInfo*, 4> vnis;
278
279    std::copy(li->vni_begin(), li->vni_end(), std::back_inserter(vnis));
280
281    for (SmallVectorImpl<VNInfo*>::iterator vniItr = vnis.begin(),
282         vniEnd = vnis.end(); vniItr != vniEnd; ++vniItr) {
283      VNInfo *vni = *vniItr;
284
285      // Skip unused VNIs.
286      if (vni->isUnused())
287        continue;
288
289      DEBUG(dbgs() << "  Extracted Val #" << vni->id << " as ");
290      LiveInterval *splitInterval = extractVNI(li, vni);
291
292      if (splitInterval != 0) {
293        DEBUG(dbgs() << *splitInterval << "\n");
294        added.push_back(splitInterval);
295        alreadySplit.insert(splitInterval);
296      } else {
297        DEBUG(dbgs() << "0\n");
298      }
299    }
300
301    DEBUG(dbgs() << "Original LI: " << *li << "\n");
302
303    // If there original interval still contains some live ranges
304    // add it to added and alreadySplit.
305    if (!li->empty()) {
306      added.push_back(li);
307      alreadySplit.insert(li);
308    }
309
310    return added;
311  }
312
313  /// Extract the given value number from the interval.
314  LiveInterval* extractVNI(LiveInterval *li, VNInfo *vni) const {
315    assert((lis->getInstructionFromIndex(vni->def) != 0 || vni->isPHIDef()) &&
316           "Def index not sane?");
317
318    // Create a new vreg and live interval, copy VNI ranges over.
319    const TargetRegisterClass *trc = mri->getRegClass(li->reg);
320    unsigned newVReg = mri->createVirtualRegister(trc);
321    vrm->grow();
322    LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
323    VNInfo *newVNI = newLI->createValueCopy(vni, lis->getVNInfoAllocator());
324
325    // Start by copying all live ranges in the VN to the new interval.
326    for (LiveInterval::iterator rItr = li->begin(), rEnd = li->end();
327         rItr != rEnd; ++rItr) {
328      if (rItr->valno == vni) {
329        newLI->addRange(LiveRange(rItr->start, rItr->end, newVNI));
330      }
331    }
332
333    // Erase the old VNI & ranges.
334    li->removeValNo(vni);
335
336    // Collect all current uses of the register belonging to the given VNI.
337    // We'll use this to rename the register after we've dealt with the def.
338    std::set<MachineInstr*> uses;
339    for (MachineRegisterInfo::use_iterator
340         useItr = mri->use_begin(li->reg), useEnd = mri->use_end();
341         useItr != useEnd; ++useItr) {
342      uses.insert(&*useItr);
343    }
344
345    // Process the def instruction for this VNI.
346    if (newVNI->isPHIDef()) {
347      // Insert a copy at the start of the MBB. The range proceeding the
348      // copy will be attached to the original LiveInterval.
349      MachineBasicBlock *defMBB = lis->getMBBFromIndex(newVNI->def);
350      MachineInstr *copyMI = BuildMI(*defMBB, defMBB->begin(), DebugLoc(),
351                                     tii->get(TargetOpcode::COPY), newVReg)
352                               .addReg(li->reg, RegState::Kill);
353      SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
354      SlotIndex phiDefIdx = lis->getMBBStartIdx(defMBB);
355      assert(lis->getInstructionFromIndex(phiDefIdx) == 0 &&
356             "PHI def index points at actual instruction.");
357      VNInfo *phiDefVNI = li->getNextValue(phiDefIdx,
358                                           0, lis->getVNInfoAllocator());
359      phiDefVNI->setIsPHIDef(true);
360      li->addRange(LiveRange(phiDefVNI->def, copyIdx.getDefIndex(), phiDefVNI));
361      LiveRange *oldPHIDefRange =
362        newLI->getLiveRangeContaining(lis->getMBBStartIdx(defMBB));
363
364      // If the old phi def starts in the middle of the range chop it up.
365      if (oldPHIDefRange->start < lis->getMBBStartIdx(defMBB)) {
366        LiveRange oldPHIDefRange2(copyIdx.getDefIndex(), oldPHIDefRange->end,
367                                  oldPHIDefRange->valno);
368        oldPHIDefRange->end = lis->getMBBStartIdx(defMBB);
369        newLI->addRange(oldPHIDefRange2);
370      } else if (oldPHIDefRange->start == lis->getMBBStartIdx(defMBB)) {
371        // Otherwise if it's at the start of the range just trim it.
372        oldPHIDefRange->start = copyIdx.getDefIndex();
373      } else {
374        assert(false && "PHI def range doesn't cover PHI def?");
375      }
376
377      newVNI->def = copyIdx.getDefIndex();
378      newVNI->setCopy(copyMI);
379      newVNI->setIsPHIDef(false); // not a PHI def anymore.
380    } else {
381      // non-PHI def. Rename the def. If it's two-addr that means renaming the
382      // use and inserting a new copy too.
383      MachineInstr *defInst = lis->getInstructionFromIndex(newVNI->def);
384      // We'll rename this now, so we can remove it from uses.
385      uses.erase(defInst);
386      unsigned defOpIdx = defInst->findRegisterDefOperandIdx(li->reg);
387      bool isTwoAddr = defInst->isRegTiedToUseOperand(defOpIdx),
388        twoAddrUseIsUndef = false;
389
390      for (unsigned i = 0; i < defInst->getNumOperands(); ++i) {
391        MachineOperand &mo = defInst->getOperand(i);
392        if (mo.isReg() && (mo.isDef() || isTwoAddr) && (mo.getReg()==li->reg)) {
393          mo.setReg(newVReg);
394          if (isTwoAddr && mo.isUse() && mo.isUndef())
395            twoAddrUseIsUndef = true;
396        }
397      }
398
399      SlotIndex defIdx = lis->getInstructionIndex(defInst);
400      newVNI->def = defIdx.getDefIndex();
401
402      if (isTwoAddr && !twoAddrUseIsUndef) {
403        MachineBasicBlock *defMBB = defInst->getParent();
404        MachineInstr *copyMI = BuildMI(*defMBB, defInst, DebugLoc(),
405                                       tii->get(TargetOpcode::COPY), newVReg)
406                                 .addReg(li->reg, RegState::Kill);
407        SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
408        LiveRange *origUseRange =
409          li->getLiveRangeContaining(newVNI->def.getUseIndex());
410        origUseRange->end = copyIdx.getDefIndex();
411        VNInfo *copyVNI = newLI->getNextValue(copyIdx.getDefIndex(), copyMI,
412                                              lis->getVNInfoAllocator());
413        LiveRange copyRange(copyIdx.getDefIndex(),defIdx.getDefIndex(),copyVNI);
414        newLI->addRange(copyRange);
415      }
416    }
417
418    for (std::set<MachineInstr*>::iterator
419         usesItr = uses.begin(), usesEnd = uses.end();
420         usesItr != usesEnd; ++usesItr) {
421      MachineInstr *useInst = *usesItr;
422      SlotIndex useIdx = lis->getInstructionIndex(useInst);
423      LiveRange *useRange =
424        newLI->getLiveRangeContaining(useIdx.getUseIndex());
425
426      // If this use doesn't belong to the new interval skip it.
427      if (useRange == 0)
428        continue;
429
430      // This use doesn't belong to the VNI, skip it.
431      if (useRange->valno != newVNI)
432        continue;
433
434      // Check if this instr is two address.
435      unsigned useOpIdx = useInst->findRegisterUseOperandIdx(li->reg);
436      bool isTwoAddress = useInst->isRegTiedToDefOperand(useOpIdx);
437
438      // Rename uses (and defs for two-address instrs).
439      for (unsigned i = 0; i < useInst->getNumOperands(); ++i) {
440        MachineOperand &mo = useInst->getOperand(i);
441        if (mo.isReg() && (mo.isUse() || isTwoAddress) &&
442            (mo.getReg() == li->reg)) {
443          mo.setReg(newVReg);
444        }
445      }
446
447      // If this is a two address instruction we've got some extra work to do.
448      if (isTwoAddress) {
449        // We modified the def operand, so we need to copy back to the original
450        // reg.
451        MachineBasicBlock *useMBB = useInst->getParent();
452        MachineBasicBlock::iterator useItr(useInst);
453        MachineInstr *copyMI = BuildMI(*useMBB, llvm::next(useItr), DebugLoc(),
454                                       tii->get(TargetOpcode::COPY), newVReg)
455                                 .addReg(li->reg, RegState::Kill);
456        SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
457
458        // Change the old two-address defined range & vni to start at
459        // (and be defined by) the copy.
460        LiveRange *origDefRange =
461          li->getLiveRangeContaining(useIdx.getDefIndex());
462        origDefRange->start = copyIdx.getDefIndex();
463        origDefRange->valno->def = copyIdx.getDefIndex();
464        origDefRange->valno->setCopy(copyMI);
465
466        // Insert a new range & vni for the two-address-to-copy value. This
467        // will be attached to the new live interval.
468        VNInfo *copyVNI =
469          newLI->getNextValue(useIdx.getDefIndex(), 0,
470                              lis->getVNInfoAllocator());
471        LiveRange copyRange(useIdx.getDefIndex(),copyIdx.getDefIndex(),copyVNI);
472        newLI->addRange(copyRange);
473      }
474    }
475
476    // Iterate over any PHI kills - we'll need to insert new copies for them.
477    for (LiveInterval::iterator LRI = newLI->begin(), LRE = newLI->end();
478         LRI != LRE; ++LRI) {
479      if (LRI->valno != newVNI)
480        continue;
481      SlotIndex killIdx = LRI->end;
482      MachineBasicBlock *killMBB = lis->getMBBFromIndex(killIdx);
483      MachineInstr *copyMI = BuildMI(*killMBB, killMBB->getFirstTerminator(),
484                                     DebugLoc(), tii->get(TargetOpcode::COPY),
485                                     li->reg)
486                               .addReg(newVReg, RegState::Kill);
487      SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
488
489      // Save the current end. We may need it to add a new range if the
490      // current range runs of the end of the MBB.
491      SlotIndex newKillRangeEnd = LRI->end;
492      LRI->end = copyIdx.getDefIndex();
493
494      if (newKillRangeEnd != lis->getMBBEndIdx(killMBB)) {
495        assert(newKillRangeEnd > lis->getMBBEndIdx(killMBB) &&
496               "PHI kill range doesn't reach kill-block end. Not sane.");
497        newLI->addRange(LiveRange(lis->getMBBEndIdx(killMBB),
498                                  newKillRangeEnd, newVNI));
499      }
500
501      VNInfo *newKillVNI = li->getNextValue(copyIdx.getDefIndex(),
502                                            copyMI, lis->getVNInfoAllocator());
503      newKillVNI->setHasPHIKill(true);
504      li->addRange(LiveRange(copyIdx.getDefIndex(),
505                             lis->getMBBEndIdx(killMBB),
506                             newKillVNI));
507    }
508    newVNI->setHasPHIKill(false);
509
510    return newLI;
511  }
512
513};
514
515} // end anonymous namespace
516
517
518namespace llvm {
519Spiller *createInlineSpiller(MachineFunctionPass &pass,
520                             MachineFunction &mf,
521                             VirtRegMap &vrm);
522}
523
524llvm::Spiller* llvm::createSpiller(MachineFunctionPass &pass,
525                                   MachineFunction &mf,
526                                   VirtRegMap &vrm) {
527  switch (spillerOpt) {
528  default: assert(0 && "unknown spiller");
529  case trivial: return new TrivialSpiller(pass, mf, vrm);
530  case standard: return new StandardSpiller(pass, mf, vrm);
531  case splitting: return new SplittingSpiller(pass, mf, vrm);
532  case inline_: return createInlineSpiller(pass, mf, vrm);
533  }
534}
535