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/raw_ostream.h"
  23 #include <set>
  24
  25 using namespace llvm;
  26
  27 namespace {
  28   enum SpillerName { trivial, standard, splitting };
  29 }
  30
  31 static cl::opt<SpillerName>
  32 spillerOpt("spiller",
  33            cl::desc("Spiller to use: (default: standard)"),
  34            cl::Prefix,
  35            cl::values(clEnumVal(trivial,   "trivial spiller"),
  36                       clEnumVal(standard,  "default spiller"),
  37                       clEnumVal(splitting, "splitting spiller"),
  38                       clEnumValEnd),
  39            cl::init(standard));
  40
  41 // Spiller virtual destructor implementation.
  42 Spiller::~Spiller() {}
  43
  44 namespace {
  45
  46 /// Utility class for spillers.
  47 class SpillerBase : public Spiller {
  48 protected:
  49   MachineFunction *mf;
  50   LiveIntervals *lis;
  51   MachineFrameInfo *mfi;
  52   MachineRegisterInfo *mri;
  53   const TargetInstrInfo *tii;
  54   const TargetRegisterInfo *tri;
  55   VirtRegMap *vrm;
  56
  57   /// Construct a spiller base.
  58   SpillerBase(MachineFunction *mf, LiveIntervals *lis, VirtRegMap *vrm)
  59     : mf(mf), lis(lis), vrm(vrm)
  60   {
  61     mfi = mf->getFrameInfo();
  62     mri = &mf->getRegInfo();
  63     tii = mf->getTarget().getInstrInfo();
  64     tri = mf->getTarget().getRegisterInfo();
  65   }
  66
  67   /// Add spill ranges for every use/def of the live interval, inserting loads
  68   /// immediately before each use, and stores after each def. No folding or
  69   /// remat is attempted.
  70   std::vector<LiveInterval*> trivialSpillEverywhere(LiveInterval *li) {
  71     DEBUG(dbgs() << "Spilling everywhere " << *li << "\n");
  72
  73     assert(li->weight != HUGE_VALF &&
  74            "Attempting to spill already spilled value.");
  75
  76     assert(!li->isStackSlot() &&
  77            "Trying to spill a stack slot.");
  78
  79     DEBUG(dbgs() << "Trivial spill everywhere of reg" << li->reg << "\n");
  80
  81     std::vector<LiveInterval*> added;
  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         loadVNI->addKill(endIndex);
 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         storeVNI->addKill(storeIndex);
 157         newLI->addRange(LiveRange(beginIndex, storeIndex, storeVNI));
 158       }
 159
 160       added.push_back(newLI);
 161     }
 162
 163     return added;
 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   std::vector<LiveInterval*> spill(LiveInterval *li,
 180                                    SmallVectorImpl<LiveInterval*> &spillIs,
 181                                    SlotIndex*) {
 182     // Ignore spillIs - we don't use it.
 183     return trivialSpillEverywhere(li);
 184   }
 185 };
 186
 187 } // end anonymous namespace
 188
 189 namespace {
 190
 191 /// Falls back on LiveIntervals::addIntervalsForSpills.
 192 class StandardSpiller : public Spiller {
 193 protected:
 194   LiveIntervals *lis;
 195   const MachineLoopInfo *loopInfo;
 196   VirtRegMap *vrm;
 197 public:
 198   StandardSpiller(LiveIntervals *lis, const MachineLoopInfo *loopInfo,
 199                   VirtRegMap *vrm)
 200     : lis(lis), loopInfo(loopInfo), vrm(vrm) {}
 201
 202   /// Falls back on LiveIntervals::addIntervalsForSpills.
 203   std::vector<LiveInterval*> spill(LiveInterval *li,
 204                                    SmallVectorImpl<LiveInterval*> &spillIs,
 205                                    SlotIndex*) {
 206     return lis->addIntervalsForSpills(*li, spillIs, loopInfo, *vrm);
 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   std::vector<LiveInterval*> spill(LiveInterval *li,
 230                                    SmallVectorImpl<LiveInterval*> &spillIs,
 231                                    SlotIndex *earliestStart) {
 232
 233     if (worthTryingToSplit(li)) {
 234       return tryVNISplit(li, earliestStart);
 235     }
 236     // else
 237     return StandardSpiller::spill(li, spillIs, earliestStart);
 238   }
 239
 240 private:
 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, or VNIs with no kills.
 267       if (vni->isUnused() || vni->kills.empty())
 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     assert(!vni->kills.empty());
 306
 307     // Create a new vreg and live interval, copy VNI kills & ranges over.
 308     const TargetRegisterClass *trc = mri->getRegClass(li->reg);
 309     unsigned newVReg = mri->createVirtualRegister(trc);
 310     vrm->grow();
 311     LiveInterval *newLI = &lis->getOrCreateInterval(newVReg);
 312     VNInfo *newVNI = newLI->createValueCopy(vni, lis->getVNInfoAllocator());
 313
 314     // Start by copying all live ranges in the VN to the new interval.
 315     for (LiveInterval::iterator rItr = li->begin(), rEnd = li->end();
 316          rItr != rEnd; ++rItr) {
 317       if (rItr->valno == vni) {
 318         newLI->addRange(LiveRange(rItr->start, rItr->end, newVNI));
 319       }
 320     }
 321
 322     // Erase the old VNI & ranges.
 323     li->removeValNo(vni);
 324
 325     // Collect all current uses of the register belonging to the given VNI.
 326     // We'll use this to rename the register after we've dealt with the def.
 327     std::set<MachineInstr*> uses;
 328     for (MachineRegisterInfo::use_iterator
 329          useItr = mri->use_begin(li->reg), useEnd = mri->use_end();
 330          useItr != useEnd; ++useItr) {
 331       uses.insert(&*useItr);
 332     }
 333
 334     // Process the def instruction for this VNI.
 335     if (newVNI->isPHIDef()) {
 336       // Insert a copy at the start of the MBB. The range proceeding the
 337       // copy will be attached to the original LiveInterval.
 338       MachineBasicBlock *defMBB = lis->getMBBFromIndex(newVNI->def);
 339       tii->copyRegToReg(*defMBB, defMBB->begin(), newVReg, li->reg, trc, trc,
 340                         DebugLoc());
 341       MachineInstr *copyMI = defMBB->begin();
 342       copyMI->addRegisterKilled(li->reg, tri);
 343       SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
 344       VNInfo *phiDefVNI = li->getNextValue(lis->getMBBStartIdx(defMBB),
 345                                            0, false, lis->getVNInfoAllocator());
 346       phiDefVNI->setIsPHIDef(true);
 347       phiDefVNI->addKill(copyIdx.getDefIndex());
 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 use
 371       // 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         tii->copyRegToReg(*defMBB, defInst, newVReg, li->reg, trc, trc,
 394                           DebugLoc());
 395         MachineInstr *copyMI = prior(MachineBasicBlock::iterator(defInst));
 396         SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
 397         copyMI->addRegisterKilled(li->reg, tri);
 398         LiveRange *origUseRange =
 399           li->getLiveRangeContaining(newVNI->def.getUseIndex());
 400         VNInfo *origUseVNI = origUseRange->valno;
 401         origUseRange->end = copyIdx.getDefIndex();
 402         bool updatedKills = false;
 403         for (unsigned k = 0; k < origUseVNI->kills.size(); ++k) {
 404           if (origUseVNI->kills[k] == defIdx.getDefIndex()) {
 405             origUseVNI->kills[k] = copyIdx.getDefIndex();
 406             updatedKills = true;
 407             break;
 408           }
 409         }
 410         assert(updatedKills && "Failed to update VNI kill list.");
 411         VNInfo *copyVNI = newLI->getNextValue(copyIdx.getDefIndex(), copyMI,
 412                                               true, lis->getVNInfoAllocator());
 413         copyVNI->addKill(defIdx.getDefIndex());
 414         LiveRange copyRange(copyIdx.getDefIndex(),defIdx.getDefIndex(),copyVNI);
 415         newLI->addRange(copyRange);
 416       }
 417     }
 418
 419     for (std::set<MachineInstr*>::iterator
 420          usesItr = uses.begin(), usesEnd = uses.end();
 421          usesItr != usesEnd; ++usesItr) {
 422       MachineInstr *useInst = *usesItr;
 423       SlotIndex useIdx = lis->getInstructionIndex(useInst);
 424       LiveRange *useRange =
 425         newLI->getLiveRangeContaining(useIdx.getUseIndex());
 426
 427       // If this use doesn't belong to the new interval skip it.
 428       if (useRange == 0)
 429         continue;
 430
 431       // This use doesn't belong to the VNI, skip it.
 432       if (useRange->valno != newVNI)
 433         continue;
 434
 435       // Check if this instr is two address.
 436       unsigned useOpIdx = useInst->findRegisterUseOperandIdx(li->reg);
 437       bool isTwoAddress = useInst->isRegTiedToDefOperand(useOpIdx);
 438
 439       // Rename uses (and defs for two-address instrs).
 440       for (unsigned i = 0; i < useInst->getNumOperands(); ++i) {
 441         MachineOperand &mo = useInst->getOperand(i);
 442         if (mo.isReg() && (mo.isUse() || isTwoAddress) &&
 443             (mo.getReg() == li->reg)) {
 444           mo.setReg(newVReg);
 445         }
 446       }
 447
 448       // If this is a two address instruction we've got some extra work to do.
 449       if (isTwoAddress) {
 450         // We modified the def operand, so we need to copy back to the original
 451         // reg.
 452         MachineBasicBlock *useMBB = useInst->getParent();
 453         MachineBasicBlock::iterator useItr(useInst);
 454         tii->copyRegToReg(*useMBB, next(useItr), li->reg, newVReg, trc, trc,
 455                           DebugLoc());
 456         MachineInstr *copyMI = next(useItr);
 457         copyMI->addRegisterKilled(newVReg, tri);
 458         SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
 459
 460         // Change the old two-address defined range & vni to start at
 461         // (and be defined by) the copy.
 462         LiveRange *origDefRange =
 463           li->getLiveRangeContaining(useIdx.getDefIndex());
 464         origDefRange->start = copyIdx.getDefIndex();
 465         origDefRange->valno->def = copyIdx.getDefIndex();
 466         origDefRange->valno->setCopy(copyMI);
 467
 468         // Insert a new range & vni for the two-address-to-copy value. This
 469         // will be attached to the new live interval.
 470         VNInfo *copyVNI =
 471           newLI->getNextValue(useIdx.getDefIndex(), 0, true,
 472                               lis->getVNInfoAllocator());
 473         copyVNI->addKill(copyIdx.getDefIndex());
 474         LiveRange copyRange(useIdx.getDefIndex(),copyIdx.getDefIndex(),copyVNI);
 475         newLI->addRange(copyRange);
 476       }
 477     }
 478
 479     // Iterate over any PHI kills - we'll need to insert new copies for them.
 480     for (VNInfo::KillSet::iterator
 481          killItr = newVNI->kills.begin(), killEnd = newVNI->kills.end();
 482          killItr != killEnd; ++killItr) {
 483       SlotIndex killIdx(*killItr);
 484       if (killItr->isPHI()) {
 485         MachineBasicBlock *killMBB = lis->getMBBFromIndex(killIdx);
 486         LiveRange *oldKillRange =
 487           newLI->getLiveRangeContaining(killIdx);
 488
 489         assert(oldKillRange != 0 && "No kill range?");
 490
 491         tii->copyRegToReg(*killMBB, killMBB->getFirstTerminator(),
 492                           li->reg, newVReg, trc, trc,
 493                           DebugLoc());
 494         MachineInstr *copyMI = prior(killMBB->getFirstTerminator());
 495         copyMI->addRegisterKilled(newVReg, tri);
 496         SlotIndex copyIdx = lis->InsertMachineInstrInMaps(copyMI);
 497
 498         // Save the current end. We may need it to add a new range if the
 499         // current range runs of the end of the MBB.
 500         SlotIndex newKillRangeEnd = oldKillRange->end;
 501         oldKillRange->end = copyIdx.getDefIndex();
 502
 503         if (newKillRangeEnd != lis->getMBBEndIdx(killMBB)) {
 504           assert(newKillRangeEnd > lis->getMBBEndIdx(killMBB) &&
 505                  "PHI kill range doesn't reach kill-block end. Not sane.");
 506           newLI->addRange(LiveRange(lis->getMBBEndIdx(killMBB),
 507                                     newKillRangeEnd, newVNI));
 508         }
 509
 510         *killItr = oldKillRange->end;
 511         VNInfo *newKillVNI = li->getNextValue(copyIdx.getDefIndex(),
 512                                               copyMI, true,
 513                                               lis->getVNInfoAllocator());
 514         newKillVNI->addKill(lis->getMBBTerminatorGap(killMBB));
 515         newKillVNI->setHasPHIKill(true);
 516         li->addRange(LiveRange(copyIdx.getDefIndex(),
 517                                lis->getMBBEndIdx(killMBB),
 518                                newKillVNI));
 519       }
 520
 521     }
 522
 523     newVNI->setHasPHIKill(false);
 524
 525     return newLI;
 526   }
 527
 528 };
 529
 530 } // end anonymous namespace
 531
 532
 533 llvm::Spiller* llvm::createSpiller(MachineFunction *mf, LiveIntervals *lis,
 534                                    const MachineLoopInfo *loopInfo,
 535                                    VirtRegMap *vrm) {
 536   switch (spillerOpt) {
 537   default: assert(0 && "unknown spiller");
 538   case trivial: return new TrivialSpiller(mf, lis, vrm);
 539   case standard: return new StandardSpiller(lis, loopInfo, vrm);
 540   case splitting: return new SplittingSpiller(mf, lis, loopInfo, vrm);
 541   }
 542 }