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