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