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