lib/CodeGen/Spiller.cpp

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