LiveIntervalAnalysis.cpp revision e3abb0a858ceaea4a4ffa7c1874be8426d2724bc
1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 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// This file implements the LiveInterval analysis pass which is used 11// by the Linear Scan Register allocator. This pass linearizes the 12// basic blocks of the function in DFS order and uses the 13// LiveVariables pass to conservatively compute live intervals for 14// each virtual and physical register. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "liveintervals" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "VirtRegMap.h" 21#include "llvm/Value.h" 22#include "llvm/CodeGen/LiveVariables.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/MachineLoopInfo.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/CodeGen/Passes.h" 28#include "llvm/Target/TargetRegisterInfo.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/ADT/STLExtras.h" 35#include <algorithm> 36#include <cmath> 37using namespace llvm; 38 39// Hidden options for help debugging. 40static cl::opt<bool> DisableReMat("disable-rematerialization", 41 cl::init(false), cl::Hidden); 42 43static cl::opt<bool> SplitAtBB("split-intervals-at-bb", 44 cl::init(true), cl::Hidden); 45static cl::opt<int> SplitLimit("split-limit", 46 cl::init(-1), cl::Hidden); 47 48STATISTIC(numIntervals, "Number of original intervals"); 49STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 50STATISTIC(numFolds , "Number of loads/stores folded into instructions"); 51STATISTIC(numSplits , "Number of intervals split"); 52 53char LiveIntervals::ID = 0; 54static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 55 56void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 57 AU.addPreserved<LiveVariables>(); 58 AU.addRequired<LiveVariables>(); 59 AU.addPreservedID(MachineLoopInfoID); 60 AU.addPreservedID(MachineDominatorsID); 61 AU.addPreservedID(PHIEliminationID); 62 AU.addRequiredID(PHIEliminationID); 63 AU.addRequiredID(TwoAddressInstructionPassID); 64 MachineFunctionPass::getAnalysisUsage(AU); 65} 66 67void LiveIntervals::releaseMemory() { 68 Idx2MBBMap.clear(); 69 mi2iMap_.clear(); 70 i2miMap_.clear(); 71 r2iMap_.clear(); 72 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 73 VNInfoAllocator.Reset(); 74 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 75 delete ClonedMIs[i]; 76} 77 78void LiveIntervals::computeNumbering() { 79 Index2MiMap OldI2MI = i2miMap_; 80 81 Idx2MBBMap.clear(); 82 MBB2IdxMap.clear(); 83 mi2iMap_.clear(); 84 i2miMap_.clear(); 85 86 // Number MachineInstrs and MachineBasicBlocks. 87 // Initialize MBB indexes to a sentinal. 88 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 89 90 unsigned MIIndex = 0; 91 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 92 MBB != E; ++MBB) { 93 unsigned StartIdx = MIIndex; 94 95 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 96 I != E; ++I) { 97 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 98 assert(inserted && "multiple MachineInstr -> index mappings"); 99 i2miMap_.push_back(I); 100 MIIndex += InstrSlots::NUM; 101 } 102 103 // Set the MBB2IdxMap entry for this MBB. 104 MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex) 105 ? std::make_pair(StartIdx, StartIdx) // Empty MBB 106 : std::make_pair(StartIdx, MIIndex - 1); 107 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 108 } 109 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 110 111 if (!OldI2MI.empty()) 112 for (iterator I = begin(), E = end(); I != E; ++I) 113 for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end(); 114 LI != LE; ++LI) { 115 116 // Remap the start index of the live range to the corresponding new 117 // number, or our best guess at what it _should_ correspond to if the 118 // original instruction has been erased. This is either the following 119 // instruction or its predecessor. 120 unsigned offset = LI->start % InstrSlots::NUM; 121 if (OldI2MI[LI->start / InstrSlots::NUM]) 122 LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset; 123 else { 124 unsigned i = 0; 125 MachineInstr* newInstr = 0; 126 do { 127 newInstr = OldI2MI[LI->start / InstrSlots::NUM + i]; 128 i++; 129 } while (!newInstr); 130 131 if (mi2iMap_[newInstr] == 132 MBB2IdxMap[newInstr->getParent()->getNumber()].first) 133 LI->start = mi2iMap_[newInstr]; 134 else 135 LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset; 136 } 137 138 // Remap the ending index in the same way that we remapped the start, 139 // except for the final step where we always map to the immediately 140 // following instruction. 141 if (LI->end / InstrSlots::NUM < OldI2MI.size()) { 142 offset = LI->end % InstrSlots::NUM; 143 if (OldI2MI[LI->end / InstrSlots::NUM]) 144 LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset; 145 else { 146 unsigned i = 0; 147 MachineInstr* newInstr = 0; 148 do { 149 newInstr = OldI2MI[LI->end / InstrSlots::NUM + i]; 150 i++; 151 } while (!newInstr); 152 153 LI->end = mi2iMap_[newInstr]; 154 } 155 } else { 156 LI->end = i2miMap_.size() * InstrSlots::NUM; 157 } 158 159 // Remap the VNInfo def index, which works the same as the 160 // start indices above. 161 VNInfo* vni = LI->valno; 162 offset = vni->def % InstrSlots::NUM; 163 if (OldI2MI[vni->def / InstrSlots::NUM]) 164 vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset; 165 else { 166 unsigned i = 0; 167 MachineInstr* newInstr = 0; 168 do { 169 newInstr = OldI2MI[vni->def / InstrSlots::NUM + i]; 170 i++; 171 } while (!newInstr); 172 173 if (mi2iMap_[newInstr] == 174 MBB2IdxMap[newInstr->getParent()->getNumber()].first) 175 vni->def = mi2iMap_[newInstr]; 176 else 177 vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset; 178 } 179 180 // Remap the VNInfo kill indices, which works the same as 181 // the end indices above. 182 for (size_t i = 0; i < vni->kills.size(); ++i) { 183 offset = vni->kills[i] % InstrSlots::NUM; 184 if (OldI2MI[vni->kills[i] / InstrSlots::NUM]) 185 vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] + 186 offset; 187 else { 188 unsigned e = 0; 189 MachineInstr* newInstr = 0; 190 do { 191 newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e]; 192 e++; 193 } while (!newInstr); 194 195 vni->kills[i] = mi2iMap_[newInstr]; 196 } 197 } 198 } 199} 200 201/// runOnMachineFunction - Register allocate the whole function 202/// 203bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 204 mf_ = &fn; 205 mri_ = &mf_->getRegInfo(); 206 tm_ = &fn.getTarget(); 207 tri_ = tm_->getRegisterInfo(); 208 tii_ = tm_->getInstrInfo(); 209 lv_ = &getAnalysis<LiveVariables>(); 210 allocatableRegs_ = tri_->getAllocatableSet(fn); 211 212 computeNumbering(); 213 computeIntervals(); 214 215 numIntervals += getNumIntervals(); 216 217 DOUT << "********** INTERVALS **********\n"; 218 for (iterator I = begin(), E = end(); I != E; ++I) { 219 I->second.print(DOUT, tri_); 220 DOUT << "\n"; 221 } 222 223 numIntervalsAfter += getNumIntervals(); 224 DEBUG(dump()); 225 return true; 226} 227 228/// print - Implement the dump method. 229void LiveIntervals::print(std::ostream &O, const Module* ) const { 230 O << "********** INTERVALS **********\n"; 231 for (const_iterator I = begin(), E = end(); I != E; ++I) { 232 I->second.print(DOUT, tri_); 233 DOUT << "\n"; 234 } 235 236 O << "********** MACHINEINSTRS **********\n"; 237 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 238 mbbi != mbbe; ++mbbi) { 239 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 240 for (MachineBasicBlock::iterator mii = mbbi->begin(), 241 mie = mbbi->end(); mii != mie; ++mii) { 242 O << getInstructionIndex(mii) << '\t' << *mii; 243 } 244 } 245} 246 247/// conflictsWithPhysRegDef - Returns true if the specified register 248/// is defined during the duration of the specified interval. 249bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 250 VirtRegMap &vrm, unsigned reg) { 251 for (LiveInterval::Ranges::const_iterator 252 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 253 for (unsigned index = getBaseIndex(I->start), 254 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 255 index += InstrSlots::NUM) { 256 // skip deleted instructions 257 while (index != end && !getInstructionFromIndex(index)) 258 index += InstrSlots::NUM; 259 if (index == end) break; 260 261 MachineInstr *MI = getInstructionFromIndex(index); 262 unsigned SrcReg, DstReg; 263 if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 264 if (SrcReg == li.reg || DstReg == li.reg) 265 continue; 266 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 267 MachineOperand& mop = MI->getOperand(i); 268 if (!mop.isRegister()) 269 continue; 270 unsigned PhysReg = mop.getReg(); 271 if (PhysReg == 0 || PhysReg == li.reg) 272 continue; 273 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 274 if (!vrm.hasPhys(PhysReg)) 275 continue; 276 PhysReg = vrm.getPhys(PhysReg); 277 } 278 if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 279 return true; 280 } 281 } 282 } 283 284 return false; 285} 286 287void LiveIntervals::printRegName(unsigned reg) const { 288 if (TargetRegisterInfo::isPhysicalRegister(reg)) 289 cerr << tri_->getName(reg); 290 else 291 cerr << "%reg" << reg; 292} 293 294void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 295 MachineBasicBlock::iterator mi, 296 unsigned MIIdx, 297 LiveInterval &interval) { 298 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 299 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 300 301 if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 302 DOUT << "is a implicit_def\n"; 303 return; 304 } 305 306 // Virtual registers may be defined multiple times (due to phi 307 // elimination and 2-addr elimination). Much of what we do only has to be 308 // done once for the vreg. We use an empty interval to detect the first 309 // time we see a vreg. 310 if (interval.empty()) { 311 // Get the Idx of the defining instructions. 312 unsigned defIndex = getDefIndex(MIIdx); 313 VNInfo *ValNo; 314 MachineInstr *CopyMI = NULL; 315 unsigned SrcReg, DstReg; 316 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 317 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 318 tii_->isMoveInstr(*mi, SrcReg, DstReg)) 319 CopyMI = mi; 320 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 321 322 assert(ValNo->id == 0 && "First value in interval is not 0?"); 323 324 // Loop over all of the blocks that the vreg is defined in. There are 325 // two cases we have to handle here. The most common case is a vreg 326 // whose lifetime is contained within a basic block. In this case there 327 // will be a single kill, in MBB, which comes after the definition. 328 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 329 // FIXME: what about dead vars? 330 unsigned killIdx; 331 if (vi.Kills[0] != mi) 332 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 333 else 334 killIdx = defIndex+1; 335 336 // If the kill happens after the definition, we have an intra-block 337 // live range. 338 if (killIdx > defIndex) { 339 assert(vi.AliveBlocks.none() && 340 "Shouldn't be alive across any blocks!"); 341 LiveRange LR(defIndex, killIdx, ValNo); 342 interval.addRange(LR); 343 DOUT << " +" << LR << "\n"; 344 interval.addKill(ValNo, killIdx); 345 return; 346 } 347 } 348 349 // The other case we handle is when a virtual register lives to the end 350 // of the defining block, potentially live across some blocks, then is 351 // live into some number of blocks, but gets killed. Start by adding a 352 // range that goes from this definition to the end of the defining block. 353 LiveRange NewLR(defIndex, 354 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 355 ValNo); 356 DOUT << " +" << NewLR; 357 interval.addRange(NewLR); 358 359 // Iterate over all of the blocks that the variable is completely 360 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 361 // live interval. 362 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 363 if (vi.AliveBlocks[i]) { 364 MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 365 if (!MBB->empty()) { 366 LiveRange LR(getMBBStartIdx(i), 367 getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 368 ValNo); 369 interval.addRange(LR); 370 DOUT << " +" << LR; 371 } 372 } 373 } 374 375 // Finally, this virtual register is live from the start of any killing 376 // block to the 'use' slot of the killing instruction. 377 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 378 MachineInstr *Kill = vi.Kills[i]; 379 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 380 LiveRange LR(getMBBStartIdx(Kill->getParent()), 381 killIdx, ValNo); 382 interval.addRange(LR); 383 interval.addKill(ValNo, killIdx); 384 DOUT << " +" << LR; 385 } 386 387 } else { 388 // If this is the second time we see a virtual register definition, it 389 // must be due to phi elimination or two addr elimination. If this is 390 // the result of two address elimination, then the vreg is one of the 391 // def-and-use register operand. 392 if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 393 // If this is a two-address definition, then we have already processed 394 // the live range. The only problem is that we didn't realize there 395 // are actually two values in the live interval. Because of this we 396 // need to take the LiveRegion that defines this register and split it 397 // into two values. 398 assert(interval.containsOneValue()); 399 unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 400 unsigned RedefIndex = getDefIndex(MIIdx); 401 402 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 403 VNInfo *OldValNo = OldLR->valno; 404 405 // Delete the initial value, which should be short and continuous, 406 // because the 2-addr copy must be in the same MBB as the redef. 407 interval.removeRange(DefIndex, RedefIndex); 408 409 // Two-address vregs should always only be redefined once. This means 410 // that at this point, there should be exactly one value number in it. 411 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 412 413 // The new value number (#1) is defined by the instruction we claimed 414 // defined value #0. 415 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 416 VNInfoAllocator); 417 418 // Value#0 is now defined by the 2-addr instruction. 419 OldValNo->def = RedefIndex; 420 OldValNo->copy = 0; 421 422 // Add the new live interval which replaces the range for the input copy. 423 LiveRange LR(DefIndex, RedefIndex, ValNo); 424 DOUT << " replace range with " << LR; 425 interval.addRange(LR); 426 interval.addKill(ValNo, RedefIndex); 427 428 // If this redefinition is dead, we need to add a dummy unit live 429 // range covering the def slot. 430 if (mi->registerDefIsDead(interval.reg, tri_)) 431 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 432 433 DOUT << " RESULT: "; 434 interval.print(DOUT, tri_); 435 436 } else { 437 // Otherwise, this must be because of phi elimination. If this is the 438 // first redefinition of the vreg that we have seen, go back and change 439 // the live range in the PHI block to be a different value number. 440 if (interval.containsOneValue()) { 441 assert(vi.Kills.size() == 1 && 442 "PHI elimination vreg should have one kill, the PHI itself!"); 443 444 // Remove the old range that we now know has an incorrect number. 445 VNInfo *VNI = interval.getValNumInfo(0); 446 MachineInstr *Killer = vi.Kills[0]; 447 unsigned Start = getMBBStartIdx(Killer->getParent()); 448 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 449 DOUT << " Removing [" << Start << "," << End << "] from: "; 450 interval.print(DOUT, tri_); DOUT << "\n"; 451 interval.removeRange(Start, End); 452 VNI->hasPHIKill = true; 453 DOUT << " RESULT: "; interval.print(DOUT, tri_); 454 455 // Replace the interval with one of a NEW value number. Note that this 456 // value number isn't actually defined by an instruction, weird huh? :) 457 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 458 DOUT << " replace range with " << LR; 459 interval.addRange(LR); 460 interval.addKill(LR.valno, End); 461 DOUT << " RESULT: "; interval.print(DOUT, tri_); 462 } 463 464 // In the case of PHI elimination, each variable definition is only 465 // live until the end of the block. We've already taken care of the 466 // rest of the live range. 467 unsigned defIndex = getDefIndex(MIIdx); 468 469 VNInfo *ValNo; 470 MachineInstr *CopyMI = NULL; 471 unsigned SrcReg, DstReg; 472 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 473 mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 474 tii_->isMoveInstr(*mi, SrcReg, DstReg)) 475 CopyMI = mi; 476 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 477 478 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 479 LiveRange LR(defIndex, killIndex, ValNo); 480 interval.addRange(LR); 481 interval.addKill(ValNo, killIndex); 482 ValNo->hasPHIKill = true; 483 DOUT << " +" << LR; 484 } 485 } 486 487 DOUT << '\n'; 488} 489 490void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 491 MachineBasicBlock::iterator mi, 492 unsigned MIIdx, 493 LiveInterval &interval, 494 MachineInstr *CopyMI) { 495 // A physical register cannot be live across basic block, so its 496 // lifetime must end somewhere in its defining basic block. 497 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 498 499 unsigned baseIndex = MIIdx; 500 unsigned start = getDefIndex(baseIndex); 501 unsigned end = start; 502 503 // If it is not used after definition, it is considered dead at 504 // the instruction defining it. Hence its interval is: 505 // [defSlot(def), defSlot(def)+1) 506 if (mi->registerDefIsDead(interval.reg, tri_)) { 507 DOUT << " dead"; 508 end = getDefIndex(start) + 1; 509 goto exit; 510 } 511 512 // If it is not dead on definition, it must be killed by a 513 // subsequent instruction. Hence its interval is: 514 // [defSlot(def), useSlot(kill)+1) 515 while (++mi != MBB->end()) { 516 baseIndex += InstrSlots::NUM; 517 if (mi->killsRegister(interval.reg, tri_)) { 518 DOUT << " killed"; 519 end = getUseIndex(baseIndex) + 1; 520 goto exit; 521 } else if (mi->modifiesRegister(interval.reg, tri_)) { 522 // Another instruction redefines the register before it is ever read. 523 // Then the register is essentially dead at the instruction that defines 524 // it. Hence its interval is: 525 // [defSlot(def), defSlot(def)+1) 526 DOUT << " dead"; 527 end = getDefIndex(start) + 1; 528 goto exit; 529 } 530 } 531 532 // The only case we should have a dead physreg here without a killing or 533 // instruction where we know it's dead is if it is live-in to the function 534 // and never used. 535 assert(!CopyMI && "physreg was not killed in defining block!"); 536 end = getDefIndex(start) + 1; // It's dead. 537 538exit: 539 assert(start < end && "did not find end of interval?"); 540 541 // Already exists? Extend old live interval. 542 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 543 VNInfo *ValNo = (OldLR != interval.end()) 544 ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 545 LiveRange LR(start, end, ValNo); 546 interval.addRange(LR); 547 interval.addKill(LR.valno, end); 548 DOUT << " +" << LR << '\n'; 549} 550 551void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 552 MachineBasicBlock::iterator MI, 553 unsigned MIIdx, 554 unsigned reg) { 555 if (TargetRegisterInfo::isVirtualRegister(reg)) 556 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 557 else if (allocatableRegs_[reg]) { 558 MachineInstr *CopyMI = NULL; 559 unsigned SrcReg, DstReg; 560 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 561 MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 562 tii_->isMoveInstr(*MI, SrcReg, DstReg)) 563 CopyMI = MI; 564 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); 565 // Def of a register also defines its sub-registers. 566 for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) 567 // If MI also modifies the sub-register explicitly, avoid processing it 568 // more than once. Do not pass in TRI here so it checks for exact match. 569 if (!MI->modifiesRegister(*AS)) 570 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 571 } 572} 573 574void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 575 unsigned MIIdx, 576 LiveInterval &interval, bool isAlias) { 577 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 578 579 // Look for kills, if it reaches a def before it's killed, then it shouldn't 580 // be considered a livein. 581 MachineBasicBlock::iterator mi = MBB->begin(); 582 unsigned baseIndex = MIIdx; 583 unsigned start = baseIndex; 584 unsigned end = start; 585 while (mi != MBB->end()) { 586 if (mi->killsRegister(interval.reg, tri_)) { 587 DOUT << " killed"; 588 end = getUseIndex(baseIndex) + 1; 589 goto exit; 590 } else if (mi->modifiesRegister(interval.reg, tri_)) { 591 // Another instruction redefines the register before it is ever read. 592 // Then the register is essentially dead at the instruction that defines 593 // it. Hence its interval is: 594 // [defSlot(def), defSlot(def)+1) 595 DOUT << " dead"; 596 end = getDefIndex(start) + 1; 597 goto exit; 598 } 599 600 baseIndex += InstrSlots::NUM; 601 ++mi; 602 } 603 604exit: 605 // Live-in register might not be used at all. 606 if (end == MIIdx) { 607 if (isAlias) { 608 DOUT << " dead"; 609 end = getDefIndex(MIIdx) + 1; 610 } else { 611 DOUT << " live through"; 612 end = baseIndex; 613 } 614 } 615 616 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 617 interval.addRange(LR); 618 interval.addKill(LR.valno, end); 619 DOUT << " +" << LR << '\n'; 620} 621 622/// computeIntervals - computes the live intervals for virtual 623/// registers. for some ordering of the machine instructions [1,N] a 624/// live interval is an interval [i, j) where 1 <= i <= j < N for 625/// which a variable is live 626void LiveIntervals::computeIntervals() { 627 DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 628 << "********** Function: " 629 << ((Value*)mf_->getFunction())->getName() << '\n'; 630 // Track the index of the current machine instr. 631 unsigned MIIndex = 0; 632 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 633 MBBI != E; ++MBBI) { 634 MachineBasicBlock *MBB = MBBI; 635 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 636 637 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 638 639 // Create intervals for live-ins to this BB first. 640 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 641 LE = MBB->livein_end(); LI != LE; ++LI) { 642 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 643 // Multiple live-ins can alias the same register. 644 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 645 if (!hasInterval(*AS)) 646 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 647 true); 648 } 649 650 for (; MI != miEnd; ++MI) { 651 DOUT << MIIndex << "\t" << *MI; 652 653 // Handle defs. 654 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 655 MachineOperand &MO = MI->getOperand(i); 656 // handle register defs - build intervals 657 if (MO.isRegister() && MO.getReg() && MO.isDef()) 658 handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 659 } 660 661 MIIndex += InstrSlots::NUM; 662 } 663 } 664} 665 666bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 667 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 668 std::vector<IdxMBBPair>::const_iterator I = 669 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 670 671 bool ResVal = false; 672 while (I != Idx2MBBMap.end()) { 673 if (LR.end <= I->first) 674 break; 675 MBBs.push_back(I->second); 676 ResVal = true; 677 ++I; 678 } 679 return ResVal; 680} 681 682 683LiveInterval LiveIntervals::createInterval(unsigned reg) { 684 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 685 HUGE_VALF : 0.0F; 686 return LiveInterval(reg, Weight); 687} 688 689/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 690/// copy field and returns the source register that defines it. 691unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 692 if (!VNI->copy) 693 return 0; 694 695 if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 696 return VNI->copy->getOperand(1).getReg(); 697 if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 698 return VNI->copy->getOperand(2).getReg(); 699 unsigned SrcReg, DstReg; 700 if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 701 return SrcReg; 702 assert(0 && "Unrecognized copy instruction!"); 703 return 0; 704} 705 706//===----------------------------------------------------------------------===// 707// Register allocator hooks. 708// 709 710/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 711/// allow one) virtual register operand, then its uses are implicitly using 712/// the register. Returns the virtual register. 713unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 714 MachineInstr *MI) const { 715 unsigned RegOp = 0; 716 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 717 MachineOperand &MO = MI->getOperand(i); 718 if (!MO.isRegister() || !MO.isUse()) 719 continue; 720 unsigned Reg = MO.getReg(); 721 if (Reg == 0 || Reg == li.reg) 722 continue; 723 // FIXME: For now, only remat MI with at most one register operand. 724 assert(!RegOp && 725 "Can't rematerialize instruction with multiple register operand!"); 726 RegOp = MO.getReg(); 727 break; 728 } 729 return RegOp; 730} 731 732/// isValNoAvailableAt - Return true if the val# of the specified interval 733/// which reaches the given instruction also reaches the specified use index. 734bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 735 unsigned UseIdx) const { 736 unsigned Index = getInstructionIndex(MI); 737 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 738 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 739 return UI != li.end() && UI->valno == ValNo; 740} 741 742/// isReMaterializable - Returns true if the definition MI of the specified 743/// val# of the specified interval is re-materializable. 744bool LiveIntervals::isReMaterializable(const LiveInterval &li, 745 const VNInfo *ValNo, MachineInstr *MI, 746 bool &isLoad) { 747 if (DisableReMat) 748 return false; 749 750 isLoad = false; 751 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 752 return true; 753 754 int FrameIdx = 0; 755 if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 756 mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 757 // FIXME: Let target specific isReallyTriviallyReMaterializable determines 758 // this but remember this is not safe to fold into a two-address 759 // instruction. 760 // This is a load from fixed stack slot. It can be rematerialized. 761 return true; 762 763 if (tii_->isTriviallyReMaterializable(MI)) { 764 const TargetInstrDesc &TID = MI->getDesc(); 765 isLoad = TID.isSimpleLoad(); 766 767 unsigned ImpUse = getReMatImplicitUse(li, MI); 768 if (ImpUse) { 769 const LiveInterval &ImpLi = getInterval(ImpUse); 770 for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 771 re = mri_->use_end(); ri != re; ++ri) { 772 MachineInstr *UseMI = &*ri; 773 unsigned UseIdx = getInstructionIndex(UseMI); 774 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 775 continue; 776 if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 777 return false; 778 } 779 } 780 return true; 781 } 782 783 return false; 784} 785 786/// isReMaterializable - Returns true if every definition of MI of every 787/// val# of the specified interval is re-materializable. 788bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 789 isLoad = false; 790 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 791 i != e; ++i) { 792 const VNInfo *VNI = *i; 793 unsigned DefIdx = VNI->def; 794 if (DefIdx == ~1U) 795 continue; // Dead val#. 796 // Is the def for the val# rematerializable? 797 if (DefIdx == ~0u) 798 return false; 799 MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 800 bool DefIsLoad = false; 801 if (!ReMatDefMI || 802 !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 803 return false; 804 isLoad |= DefIsLoad; 805 } 806 return true; 807} 808 809/// FilterFoldedOps - Filter out two-address use operands. Return 810/// true if it finds any issue with the operands that ought to prevent 811/// folding. 812static bool FilterFoldedOps(MachineInstr *MI, 813 SmallVector<unsigned, 2> &Ops, 814 unsigned &MRInfo, 815 SmallVector<unsigned, 2> &FoldOps) { 816 const TargetInstrDesc &TID = MI->getDesc(); 817 818 MRInfo = 0; 819 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 820 unsigned OpIdx = Ops[i]; 821 MachineOperand &MO = MI->getOperand(OpIdx); 822 // FIXME: fold subreg use. 823 if (MO.getSubReg()) 824 return true; 825 if (MO.isDef()) 826 MRInfo |= (unsigned)VirtRegMap::isMod; 827 else { 828 // Filter out two-address use operand(s). 829 if (!MO.isImplicit() && 830 TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 831 MRInfo = VirtRegMap::isModRef; 832 continue; 833 } 834 MRInfo |= (unsigned)VirtRegMap::isRef; 835 } 836 FoldOps.push_back(OpIdx); 837 } 838 return false; 839} 840 841 842/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 843/// slot / to reg or any rematerialized load into ith operand of specified 844/// MI. If it is successul, MI is updated with the newly created MI and 845/// returns true. 846bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 847 VirtRegMap &vrm, MachineInstr *DefMI, 848 unsigned InstrIdx, 849 SmallVector<unsigned, 2> &Ops, 850 bool isSS, int Slot, unsigned Reg) { 851 // If it is an implicit def instruction, just delete it. 852 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 853 RemoveMachineInstrFromMaps(MI); 854 vrm.RemoveMachineInstrFromMaps(MI); 855 MI->eraseFromParent(); 856 ++numFolds; 857 return true; 858 } 859 860 // Filter the list of operand indexes that are to be folded. Abort if 861 // any operand will prevent folding. 862 unsigned MRInfo = 0; 863 SmallVector<unsigned, 2> FoldOps; 864 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 865 return false; 866 867 // The only time it's safe to fold into a two address instruction is when 868 // it's folding reload and spill from / into a spill stack slot. 869 if (DefMI && (MRInfo & VirtRegMap::isMod)) 870 return false; 871 872 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 873 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 874 if (fmi) { 875 // Remember this instruction uses the spill slot. 876 if (isSS) vrm.addSpillSlotUse(Slot, fmi); 877 878 // Attempt to fold the memory reference into the instruction. If 879 // we can do this, we don't need to insert spill code. 880 if (lv_) 881 lv_->instructionChanged(MI, fmi); 882 else 883 fmi->copyKillDeadInfo(MI, tri_); 884 MachineBasicBlock &MBB = *MI->getParent(); 885 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 886 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 887 vrm.transferSpillPts(MI, fmi); 888 vrm.transferRestorePts(MI, fmi); 889 vrm.transferEmergencySpills(MI, fmi); 890 mi2iMap_.erase(MI); 891 i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 892 mi2iMap_[fmi] = InstrIdx; 893 MI = MBB.insert(MBB.erase(MI), fmi); 894 ++numFolds; 895 return true; 896 } 897 return false; 898} 899 900/// canFoldMemoryOperand - Returns true if the specified load / store 901/// folding is possible. 902bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 903 SmallVector<unsigned, 2> &Ops, 904 bool ReMat) const { 905 // Filter the list of operand indexes that are to be folded. Abort if 906 // any operand will prevent folding. 907 unsigned MRInfo = 0; 908 SmallVector<unsigned, 2> FoldOps; 909 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 910 return false; 911 912 // It's only legal to remat for a use, not a def. 913 if (ReMat && (MRInfo & VirtRegMap::isMod)) 914 return false; 915 916 return tii_->canFoldMemoryOperand(MI, FoldOps); 917} 918 919bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 920 SmallPtrSet<MachineBasicBlock*, 4> MBBs; 921 for (LiveInterval::Ranges::const_iterator 922 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 923 std::vector<IdxMBBPair>::const_iterator II = 924 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 925 if (II == Idx2MBBMap.end()) 926 continue; 927 if (I->end > II->first) // crossing a MBB. 928 return false; 929 MBBs.insert(II->second); 930 if (MBBs.size() > 1) 931 return false; 932 } 933 return true; 934} 935 936/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 937/// interval on to-be re-materialized operands of MI) with new register. 938void LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 939 MachineInstr *MI, unsigned NewVReg, 940 VirtRegMap &vrm) { 941 // There is an implicit use. That means one of the other operand is 942 // being remat'ed and the remat'ed instruction has li.reg as an 943 // use operand. Make sure we rewrite that as well. 944 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 945 MachineOperand &MO = MI->getOperand(i); 946 if (!MO.isRegister()) 947 continue; 948 unsigned Reg = MO.getReg(); 949 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 950 continue; 951 if (!vrm.isReMaterialized(Reg)) 952 continue; 953 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 954 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 955 if (UseMO) 956 UseMO->setReg(NewVReg); 957 } 958} 959 960/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 961/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 962bool LiveIntervals:: 963rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 964 bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 965 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 966 unsigned Slot, int LdSlot, 967 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 968 VirtRegMap &vrm, 969 const TargetRegisterClass* rc, 970 SmallVector<int, 4> &ReMatIds, 971 const MachineLoopInfo *loopInfo, 972 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 973 std::map<unsigned,unsigned> &MBBVRegsMap, 974 std::vector<LiveInterval*> &NewLIs) { 975 bool CanFold = false; 976 RestartInstruction: 977 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 978 MachineOperand& mop = MI->getOperand(i); 979 if (!mop.isRegister()) 980 continue; 981 unsigned Reg = mop.getReg(); 982 unsigned RegI = Reg; 983 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 984 continue; 985 if (Reg != li.reg) 986 continue; 987 988 bool TryFold = !DefIsReMat; 989 bool FoldSS = true; // Default behavior unless it's a remat. 990 int FoldSlot = Slot; 991 if (DefIsReMat) { 992 // If this is the rematerializable definition MI itself and 993 // all of its uses are rematerialized, simply delete it. 994 if (MI == ReMatOrigDefMI && CanDelete) { 995 DOUT << "\t\t\t\tErasing re-materlizable def: "; 996 DOUT << MI << '\n'; 997 RemoveMachineInstrFromMaps(MI); 998 vrm.RemoveMachineInstrFromMaps(MI); 999 MI->eraseFromParent(); 1000 break; 1001 } 1002 1003 // If def for this use can't be rematerialized, then try folding. 1004 // If def is rematerializable and it's a load, also try folding. 1005 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1006 if (isLoad) { 1007 // Try fold loads (from stack slot, constant pool, etc.) into uses. 1008 FoldSS = isLoadSS; 1009 FoldSlot = LdSlot; 1010 } 1011 } 1012 1013 // Scan all of the operands of this instruction rewriting operands 1014 // to use NewVReg instead of li.reg as appropriate. We do this for 1015 // two reasons: 1016 // 1017 // 1. If the instr reads the same spilled vreg multiple times, we 1018 // want to reuse the NewVReg. 1019 // 2. If the instr is a two-addr instruction, we are required to 1020 // keep the src/dst regs pinned. 1021 // 1022 // Keep track of whether we replace a use and/or def so that we can 1023 // create the spill interval with the appropriate range. 1024 1025 HasUse = mop.isUse(); 1026 HasDef = mop.isDef(); 1027 SmallVector<unsigned, 2> Ops; 1028 Ops.push_back(i); 1029 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1030 const MachineOperand &MOj = MI->getOperand(j); 1031 if (!MOj.isRegister()) 1032 continue; 1033 unsigned RegJ = MOj.getReg(); 1034 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1035 continue; 1036 if (RegJ == RegI) { 1037 Ops.push_back(j); 1038 HasUse |= MOj.isUse(); 1039 HasDef |= MOj.isDef(); 1040 } 1041 } 1042 1043 if (TryFold) { 1044 // Do not fold load / store here if we are splitting. We'll find an 1045 // optimal point to insert a load / store later. 1046 if (!TrySplit) { 1047 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1048 Ops, FoldSS, FoldSlot, Reg)) { 1049 // Folding the load/store can completely change the instruction in 1050 // unpredictable ways, rescan it from the beginning. 1051 HasUse = false; 1052 HasDef = false; 1053 CanFold = false; 1054 if (isRemoved(MI)) 1055 break; 1056 goto RestartInstruction; 1057 } 1058 } else { 1059 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1060 } 1061 } else 1062 CanFold = false; 1063 1064 // Create a new virtual register for the spill interval. 1065 bool CreatedNewVReg = false; 1066 if (NewVReg == 0) { 1067 NewVReg = mri_->createVirtualRegister(rc); 1068 vrm.grow(); 1069 CreatedNewVReg = true; 1070 } 1071 mop.setReg(NewVReg); 1072 if (mop.isImplicit()) 1073 rewriteImplicitOps(li, MI, NewVReg, vrm); 1074 1075 // Reuse NewVReg for other reads. 1076 for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1077 MachineOperand &mopj = MI->getOperand(Ops[j]); 1078 mopj.setReg(NewVReg); 1079 if (mopj.isImplicit()) 1080 rewriteImplicitOps(li, MI, NewVReg, vrm); 1081 } 1082 1083 if (CreatedNewVReg) { 1084 if (DefIsReMat) { 1085 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1086 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 1087 // Each valnum may have its own remat id. 1088 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 1089 } else { 1090 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 1091 } 1092 if (!CanDelete || (HasUse && HasDef)) { 1093 // If this is a two-addr instruction then its use operands are 1094 // rematerializable but its def is not. It should be assigned a 1095 // stack slot. 1096 vrm.assignVirt2StackSlot(NewVReg, Slot); 1097 } 1098 } else { 1099 vrm.assignVirt2StackSlot(NewVReg, Slot); 1100 } 1101 } else if (HasUse && HasDef && 1102 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1103 // If this interval hasn't been assigned a stack slot (because earlier 1104 // def is a deleted remat def), do it now. 1105 assert(Slot != VirtRegMap::NO_STACK_SLOT); 1106 vrm.assignVirt2StackSlot(NewVReg, Slot); 1107 } 1108 1109 // Re-matting an instruction with virtual register use. Add the 1110 // register as an implicit use on the use MI. 1111 if (DefIsReMat && ImpUse) 1112 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1113 1114 // create a new register interval for this spill / remat. 1115 LiveInterval &nI = getOrCreateInterval(NewVReg); 1116 if (CreatedNewVReg) { 1117 NewLIs.push_back(&nI); 1118 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 1119 if (TrySplit) 1120 vrm.setIsSplitFromReg(NewVReg, li.reg); 1121 } 1122 1123 if (HasUse) { 1124 if (CreatedNewVReg) { 1125 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 1126 nI.getNextValue(~0U, 0, VNInfoAllocator)); 1127 DOUT << " +" << LR; 1128 nI.addRange(LR); 1129 } else { 1130 // Extend the split live interval to this def / use. 1131 unsigned End = getUseIndex(index)+1; 1132 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 1133 nI.getValNumInfo(nI.getNumValNums()-1)); 1134 DOUT << " +" << LR; 1135 nI.addRange(LR); 1136 } 1137 } 1138 if (HasDef) { 1139 LiveRange LR(getDefIndex(index), getStoreIndex(index), 1140 nI.getNextValue(~0U, 0, VNInfoAllocator)); 1141 DOUT << " +" << LR; 1142 nI.addRange(LR); 1143 } 1144 1145 DOUT << "\t\t\t\tAdded new interval: "; 1146 nI.print(DOUT, tri_); 1147 DOUT << '\n'; 1148 } 1149 return CanFold; 1150} 1151bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 1152 const VNInfo *VNI, 1153 MachineBasicBlock *MBB, unsigned Idx) const { 1154 unsigned End = getMBBEndIdx(MBB); 1155 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 1156 unsigned KillIdx = VNI->kills[j]; 1157 if (KillIdx > Idx && KillIdx < End) 1158 return true; 1159 } 1160 return false; 1161} 1162 1163static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { 1164 const VNInfo *VNI = NULL; 1165 for (LiveInterval::const_vni_iterator i = li.vni_begin(), 1166 e = li.vni_end(); i != e; ++i) 1167 if ((*i)->def == DefIdx) { 1168 VNI = *i; 1169 break; 1170 } 1171 return VNI; 1172} 1173 1174/// RewriteInfo - Keep track of machine instrs that will be rewritten 1175/// during spilling. 1176namespace { 1177 struct RewriteInfo { 1178 unsigned Index; 1179 MachineInstr *MI; 1180 bool HasUse; 1181 bool HasDef; 1182 RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1183 : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1184 }; 1185 1186 struct RewriteInfoCompare { 1187 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1188 return LHS.Index < RHS.Index; 1189 } 1190 }; 1191} 1192 1193void LiveIntervals:: 1194rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1195 LiveInterval::Ranges::const_iterator &I, 1196 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1197 unsigned Slot, int LdSlot, 1198 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1199 VirtRegMap &vrm, 1200 const TargetRegisterClass* rc, 1201 SmallVector<int, 4> &ReMatIds, 1202 const MachineLoopInfo *loopInfo, 1203 BitVector &SpillMBBs, 1204 std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 1205 BitVector &RestoreMBBs, 1206 std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1207 std::map<unsigned,unsigned> &MBBVRegsMap, 1208 std::vector<LiveInterval*> &NewLIs) { 1209 bool AllCanFold = true; 1210 unsigned NewVReg = 0; 1211 unsigned start = getBaseIndex(I->start); 1212 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1213 1214 // First collect all the def / use in this live range that will be rewritten. 1215 // Make sure they are sorted according to instruction index. 1216 std::vector<RewriteInfo> RewriteMIs; 1217 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1218 re = mri_->reg_end(); ri != re; ) { 1219 MachineInstr *MI = &*ri; 1220 MachineOperand &O = ri.getOperand(); 1221 ++ri; 1222 assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1223 unsigned index = getInstructionIndex(MI); 1224 if (index < start || index >= end) 1225 continue; 1226 RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1227 } 1228 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1229 1230 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1231 // Now rewrite the defs and uses. 1232 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1233 RewriteInfo &rwi = RewriteMIs[i]; 1234 ++i; 1235 unsigned index = rwi.Index; 1236 bool MIHasUse = rwi.HasUse; 1237 bool MIHasDef = rwi.HasDef; 1238 MachineInstr *MI = rwi.MI; 1239 // If MI def and/or use the same register multiple times, then there 1240 // are multiple entries. 1241 unsigned NumUses = MIHasUse; 1242 while (i != e && RewriteMIs[i].MI == MI) { 1243 assert(RewriteMIs[i].Index == index); 1244 bool isUse = RewriteMIs[i].HasUse; 1245 if (isUse) ++NumUses; 1246 MIHasUse |= isUse; 1247 MIHasDef |= RewriteMIs[i].HasDef; 1248 ++i; 1249 } 1250 MachineBasicBlock *MBB = MI->getParent(); 1251 1252 if (ImpUse && MI != ReMatDefMI) { 1253 // Re-matting an instruction with virtual register use. Update the 1254 // register interval's spill weight to HUGE_VALF to prevent it from 1255 // being spilled. 1256 LiveInterval &ImpLi = getInterval(ImpUse); 1257 ImpLi.weight = HUGE_VALF; 1258 } 1259 1260 unsigned MBBId = MBB->getNumber(); 1261 unsigned ThisVReg = 0; 1262 if (TrySplit) { 1263 std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 1264 if (NVI != MBBVRegsMap.end()) { 1265 ThisVReg = NVI->second; 1266 // One common case: 1267 // x = use 1268 // ... 1269 // ... 1270 // def = ... 1271 // = use 1272 // It's better to start a new interval to avoid artifically 1273 // extend the new interval. 1274 if (MIHasDef && !MIHasUse) { 1275 MBBVRegsMap.erase(MBB->getNumber()); 1276 ThisVReg = 0; 1277 } 1278 } 1279 } 1280 1281 bool IsNew = ThisVReg == 0; 1282 if (IsNew) { 1283 // This ends the previous live interval. If all of its def / use 1284 // can be folded, give it a low spill weight. 1285 if (NewVReg && TrySplit && AllCanFold) { 1286 LiveInterval &nI = getOrCreateInterval(NewVReg); 1287 nI.weight /= 10.0F; 1288 } 1289 AllCanFold = true; 1290 } 1291 NewVReg = ThisVReg; 1292 1293 bool HasDef = false; 1294 bool HasUse = false; 1295 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1296 index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1297 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1298 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1299 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 1300 if (!HasDef && !HasUse) 1301 continue; 1302 1303 AllCanFold &= CanFold; 1304 1305 // Update weight of spill interval. 1306 LiveInterval &nI = getOrCreateInterval(NewVReg); 1307 if (!TrySplit) { 1308 // The spill weight is now infinity as it cannot be spilled again. 1309 nI.weight = HUGE_VALF; 1310 continue; 1311 } 1312 1313 // Keep track of the last def and first use in each MBB. 1314 if (HasDef) { 1315 if (MI != ReMatOrigDefMI || !CanDelete) { 1316 bool HasKill = false; 1317 if (!HasUse) 1318 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 1319 else { 1320 // If this is a two-address code, then this index starts a new VNInfo. 1321 const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); 1322 if (VNI) 1323 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 1324 } 1325 std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1326 SpillIdxes.find(MBBId); 1327 if (!HasKill) { 1328 if (SII == SpillIdxes.end()) { 1329 std::vector<SRInfo> S; 1330 S.push_back(SRInfo(index, NewVReg, true)); 1331 SpillIdxes.insert(std::make_pair(MBBId, S)); 1332 } else if (SII->second.back().vreg != NewVReg) { 1333 SII->second.push_back(SRInfo(index, NewVReg, true)); 1334 } else if ((int)index > SII->second.back().index) { 1335 // If there is an earlier def and this is a two-address 1336 // instruction, then it's not possible to fold the store (which 1337 // would also fold the load). 1338 SRInfo &Info = SII->second.back(); 1339 Info.index = index; 1340 Info.canFold = !HasUse; 1341 } 1342 SpillMBBs.set(MBBId); 1343 } else if (SII != SpillIdxes.end() && 1344 SII->second.back().vreg == NewVReg && 1345 (int)index > SII->second.back().index) { 1346 // There is an earlier def that's not killed (must be two-address). 1347 // The spill is no longer needed. 1348 SII->second.pop_back(); 1349 if (SII->second.empty()) { 1350 SpillIdxes.erase(MBBId); 1351 SpillMBBs.reset(MBBId); 1352 } 1353 } 1354 } 1355 } 1356 1357 if (HasUse) { 1358 std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1359 SpillIdxes.find(MBBId); 1360 if (SII != SpillIdxes.end() && 1361 SII->second.back().vreg == NewVReg && 1362 (int)index > SII->second.back().index) 1363 // Use(s) following the last def, it's not safe to fold the spill. 1364 SII->second.back().canFold = false; 1365 std::map<unsigned, std::vector<SRInfo> >::iterator RII = 1366 RestoreIdxes.find(MBBId); 1367 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 1368 // If we are splitting live intervals, only fold if it's the first 1369 // use and there isn't another use later in the MBB. 1370 RII->second.back().canFold = false; 1371 else if (IsNew) { 1372 // Only need a reload if there isn't an earlier def / use. 1373 if (RII == RestoreIdxes.end()) { 1374 std::vector<SRInfo> Infos; 1375 Infos.push_back(SRInfo(index, NewVReg, true)); 1376 RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 1377 } else { 1378 RII->second.push_back(SRInfo(index, NewVReg, true)); 1379 } 1380 RestoreMBBs.set(MBBId); 1381 } 1382 } 1383 1384 // Update spill weight. 1385 unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1386 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1387 } 1388 1389 if (NewVReg && TrySplit && AllCanFold) { 1390 // If all of its def / use can be folded, give it a low spill weight. 1391 LiveInterval &nI = getOrCreateInterval(NewVReg); 1392 nI.weight /= 10.0F; 1393 } 1394} 1395 1396bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 1397 BitVector &RestoreMBBs, 1398 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1399 if (!RestoreMBBs[Id]) 1400 return false; 1401 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1402 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1403 if (Restores[i].index == index && 1404 Restores[i].vreg == vr && 1405 Restores[i].canFold) 1406 return true; 1407 return false; 1408} 1409 1410void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 1411 BitVector &RestoreMBBs, 1412 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 1413 if (!RestoreMBBs[Id]) 1414 return; 1415 std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 1416 for (unsigned i = 0, e = Restores.size(); i != e; ++i) 1417 if (Restores[i].index == index && Restores[i].vreg) 1418 Restores[i].index = -1; 1419} 1420 1421/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 1422/// spilled and create empty intervals for their uses. 1423void 1424LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 1425 const TargetRegisterClass* rc, 1426 std::vector<LiveInterval*> &NewLIs) { 1427 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1428 re = mri_->reg_end(); ri != re; ) { 1429 MachineOperand &O = ri.getOperand(); 1430 MachineInstr *MI = &*ri; 1431 ++ri; 1432 if (O.isDef()) { 1433 assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 1434 "Register def was not rewritten?"); 1435 RemoveMachineInstrFromMaps(MI); 1436 vrm.RemoveMachineInstrFromMaps(MI); 1437 MI->eraseFromParent(); 1438 } else { 1439 // This must be an use of an implicit_def so it's not part of the live 1440 // interval. Create a new empty live interval for it. 1441 // FIXME: Can we simply erase some of the instructions? e.g. Stores? 1442 unsigned NewVReg = mri_->createVirtualRegister(rc); 1443 vrm.grow(); 1444 vrm.setIsImplicitlyDefined(NewVReg); 1445 NewLIs.push_back(&getOrCreateInterval(NewVReg)); 1446 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1447 MachineOperand &MO = MI->getOperand(i); 1448 if (MO.isReg() && MO.getReg() == li.reg) 1449 MO.setReg(NewVReg); 1450 } 1451 } 1452 } 1453} 1454 1455 1456std::vector<LiveInterval*> LiveIntervals:: 1457addIntervalsForSpills(const LiveInterval &li, 1458 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1459 // Since this is called after the analysis is done we don't know if 1460 // LiveVariables is available 1461 lv_ = getAnalysisToUpdate<LiveVariables>(); 1462 1463 assert(li.weight != HUGE_VALF && 1464 "attempt to spill already spilled interval!"); 1465 1466 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 1467 li.print(DOUT, tri_); 1468 DOUT << '\n'; 1469 1470 // Each bit specify whether it a spill is required in the MBB. 1471 BitVector SpillMBBs(mf_->getNumBlockIDs()); 1472 std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 1473 BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1474 std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 1475 std::map<unsigned,unsigned> MBBVRegsMap; 1476 std::vector<LiveInterval*> NewLIs; 1477 const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1478 1479 unsigned NumValNums = li.getNumValNums(); 1480 SmallVector<MachineInstr*, 4> ReMatDefs; 1481 ReMatDefs.resize(NumValNums, NULL); 1482 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1483 ReMatOrigDefs.resize(NumValNums, NULL); 1484 SmallVector<int, 4> ReMatIds; 1485 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1486 BitVector ReMatDelete(NumValNums); 1487 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1488 1489 // Spilling a split live interval. It cannot be split any further. Also, 1490 // it's also guaranteed to be a single val# / range interval. 1491 if (vrm.getPreSplitReg(li.reg)) { 1492 vrm.setIsSplitFromReg(li.reg, 0); 1493 // Unset the split kill marker on the last use. 1494 unsigned KillIdx = vrm.getKillPoint(li.reg); 1495 if (KillIdx) { 1496 MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1497 assert(KillMI && "Last use disappeared?"); 1498 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1499 assert(KillOp != -1 && "Last use disappeared?"); 1500 KillMI->getOperand(KillOp).setIsKill(false); 1501 } 1502 vrm.removeKillPoint(li.reg); 1503 bool DefIsReMat = vrm.isReMaterialized(li.reg); 1504 Slot = vrm.getStackSlot(li.reg); 1505 assert(Slot != VirtRegMap::MAX_STACK_SLOT); 1506 MachineInstr *ReMatDefMI = DefIsReMat ? 1507 vrm.getReMaterializedMI(li.reg) : NULL; 1508 int LdSlot = 0; 1509 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1510 bool isLoad = isLoadSS || 1511 (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 1512 bool IsFirstRange = true; 1513 for (LiveInterval::Ranges::const_iterator 1514 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1515 // If this is a split live interval with multiple ranges, it means there 1516 // are two-address instructions that re-defined the value. Only the 1517 // first def can be rematerialized! 1518 if (IsFirstRange) { 1519 // Note ReMatOrigDefMI has already been deleted. 1520 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 1521 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1522 false, vrm, rc, ReMatIds, loopInfo, 1523 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1524 MBBVRegsMap, NewLIs); 1525 } else { 1526 rewriteInstructionsForSpills(li, false, I, NULL, 0, 1527 Slot, 0, false, false, false, 1528 false, vrm, rc, ReMatIds, loopInfo, 1529 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1530 MBBVRegsMap, NewLIs); 1531 } 1532 IsFirstRange = false; 1533 } 1534 1535 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1536 return NewLIs; 1537 } 1538 1539 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 1540 if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 1541 TrySplit = false; 1542 if (TrySplit) 1543 ++numSplits; 1544 bool NeedStackSlot = false; 1545 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1546 i != e; ++i) { 1547 const VNInfo *VNI = *i; 1548 unsigned VN = VNI->id; 1549 unsigned DefIdx = VNI->def; 1550 if (DefIdx == ~1U) 1551 continue; // Dead val#. 1552 // Is the def for the val# rematerializable? 1553 MachineInstr *ReMatDefMI = (DefIdx == ~0u) 1554 ? 0 : getInstructionFromIndex(DefIdx); 1555 bool dummy; 1556 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1557 // Remember how to remat the def of this val#. 1558 ReMatOrigDefs[VN] = ReMatDefMI; 1559 // Original def may be modified so we have to make a copy here. vrm must 1560 // delete these! 1561 ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); 1562 1563 bool CanDelete = true; 1564 if (VNI->hasPHIKill) { 1565 // A kill is a phi node, not all of its uses can be rematerialized. 1566 // It must not be deleted. 1567 CanDelete = false; 1568 // Need a stack slot if there is any live range where uses cannot be 1569 // rematerialized. 1570 NeedStackSlot = true; 1571 } 1572 if (CanDelete) 1573 ReMatDelete.set(VN); 1574 } else { 1575 // Need a stack slot if there is any live range where uses cannot be 1576 // rematerialized. 1577 NeedStackSlot = true; 1578 } 1579 } 1580 1581 // One stack slot per live interval. 1582 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1583 Slot = vrm.assignVirt2StackSlot(li.reg); 1584 1585 // Create new intervals and rewrite defs and uses. 1586 for (LiveInterval::Ranges::const_iterator 1587 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 1588 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 1589 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 1590 bool DefIsReMat = ReMatDefMI != NULL; 1591 bool CanDelete = ReMatDelete[I->valno->id]; 1592 int LdSlot = 0; 1593 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1594 bool isLoad = isLoadSS || 1595 (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 1596 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 1597 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1598 CanDelete, vrm, rc, ReMatIds, loopInfo, 1599 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1600 MBBVRegsMap, NewLIs); 1601 } 1602 1603 // Insert spills / restores if we are splitting. 1604 if (!TrySplit) { 1605 handleSpilledImpDefs(li, vrm, rc, NewLIs); 1606 return NewLIs; 1607 } 1608 1609 SmallPtrSet<LiveInterval*, 4> AddedKill; 1610 SmallVector<unsigned, 2> Ops; 1611 if (NeedStackSlot) { 1612 int Id = SpillMBBs.find_first(); 1613 while (Id != -1) { 1614 std::vector<SRInfo> &spills = SpillIdxes[Id]; 1615 for (unsigned i = 0, e = spills.size(); i != e; ++i) { 1616 int index = spills[i].index; 1617 unsigned VReg = spills[i].vreg; 1618 LiveInterval &nI = getOrCreateInterval(VReg); 1619 bool isReMat = vrm.isReMaterialized(VReg); 1620 MachineInstr *MI = getInstructionFromIndex(index); 1621 bool CanFold = false; 1622 bool FoundUse = false; 1623 Ops.clear(); 1624 if (spills[i].canFold) { 1625 CanFold = true; 1626 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1627 MachineOperand &MO = MI->getOperand(j); 1628 if (!MO.isRegister() || MO.getReg() != VReg) 1629 continue; 1630 1631 Ops.push_back(j); 1632 if (MO.isDef()) 1633 continue; 1634 if (isReMat || 1635 (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1636 RestoreMBBs, RestoreIdxes))) { 1637 // MI has two-address uses of the same register. If the use 1638 // isn't the first and only use in the BB, then we can't fold 1639 // it. FIXME: Move this to rewriteInstructionsForSpills. 1640 CanFold = false; 1641 break; 1642 } 1643 FoundUse = true; 1644 } 1645 } 1646 // Fold the store into the def if possible. 1647 bool Folded = false; 1648 if (CanFold && !Ops.empty()) { 1649 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1650 Folded = true; 1651 if (FoundUse > 0) { 1652 // Also folded uses, do not issue a load. 1653 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1654 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1655 } 1656 nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1657 } 1658 } 1659 1660 // Otherwise tell the spiller to issue a spill. 1661 if (!Folded) { 1662 LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1663 bool isKill = LR->end == getStoreIndex(index); 1664 if (!MI->registerDefIsDead(nI.reg)) 1665 // No need to spill a dead def. 1666 vrm.addSpillPoint(VReg, isKill, MI); 1667 if (isKill) 1668 AddedKill.insert(&nI); 1669 } 1670 } 1671 Id = SpillMBBs.find_next(Id); 1672 } 1673 } 1674 1675 int Id = RestoreMBBs.find_first(); 1676 while (Id != -1) { 1677 std::vector<SRInfo> &restores = RestoreIdxes[Id]; 1678 for (unsigned i = 0, e = restores.size(); i != e; ++i) { 1679 int index = restores[i].index; 1680 if (index == -1) 1681 continue; 1682 unsigned VReg = restores[i].vreg; 1683 LiveInterval &nI = getOrCreateInterval(VReg); 1684 MachineInstr *MI = getInstructionFromIndex(index); 1685 bool CanFold = false; 1686 Ops.clear(); 1687 if (restores[i].canFold) { 1688 CanFold = true; 1689 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 1690 MachineOperand &MO = MI->getOperand(j); 1691 if (!MO.isRegister() || MO.getReg() != VReg) 1692 continue; 1693 1694 if (MO.isDef()) { 1695 // If this restore were to be folded, it would have been folded 1696 // already. 1697 CanFold = false; 1698 break; 1699 } 1700 Ops.push_back(j); 1701 } 1702 } 1703 1704 // Fold the load into the use if possible. 1705 bool Folded = false; 1706 if (CanFold && !Ops.empty()) { 1707 if (!vrm.isReMaterialized(VReg)) 1708 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1709 else { 1710 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 1711 int LdSlot = 0; 1712 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1713 // If the rematerializable def is a load, also try to fold it. 1714 if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1715 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1716 Ops, isLoadSS, LdSlot, VReg); 1717 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1718 if (ImpUse) { 1719 // Re-matting an instruction with virtual register use. Add the 1720 // register as an implicit use on the use MI and update the register 1721 // interval's spill weight to HUGE_VALF to prevent it from being 1722 // spilled. 1723 LiveInterval &ImpLi = getInterval(ImpUse); 1724 ImpLi.weight = HUGE_VALF; 1725 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1726 } 1727 } 1728 } 1729 // If folding is not possible / failed, then tell the spiller to issue a 1730 // load / rematerialization for us. 1731 if (Folded) 1732 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1733 else 1734 vrm.addRestorePoint(VReg, MI); 1735 } 1736 Id = RestoreMBBs.find_next(Id); 1737 } 1738 1739 // Finalize intervals: add kills, finalize spill weights, and filter out 1740 // dead intervals. 1741 std::vector<LiveInterval*> RetNewLIs; 1742 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1743 LiveInterval *LI = NewLIs[i]; 1744 if (!LI->empty()) { 1745 LI->weight /= LI->getSize(); 1746 if (!AddedKill.count(LI)) { 1747 LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1748 unsigned LastUseIdx = getBaseIndex(LR->end); 1749 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 1750 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1751 assert(UseIdx != -1); 1752 if (LastUse->getOperand(UseIdx).isImplicit() || 1753 LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1754 LastUse->getOperand(UseIdx).setIsKill(); 1755 vrm.addKillPoint(LI->reg, LastUseIdx); 1756 } 1757 } 1758 RetNewLIs.push_back(LI); 1759 } 1760 } 1761 1762 handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1763 return RetNewLIs; 1764} 1765 1766/// hasAllocatableSuperReg - Return true if the specified physical register has 1767/// any super register that's allocatable. 1768bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1769 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1770 if (allocatableRegs_[*AS] && hasInterval(*AS)) 1771 return true; 1772 return false; 1773} 1774 1775/// getRepresentativeReg - Find the largest super register of the specified 1776/// physical register. 1777unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1778 // Find the largest super-register that is allocatable. 1779 unsigned BestReg = Reg; 1780 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1781 unsigned SuperReg = *AS; 1782 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1783 BestReg = SuperReg; 1784 break; 1785 } 1786 } 1787 return BestReg; 1788} 1789 1790/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1791/// specified interval that conflicts with the specified physical register. 1792unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1793 unsigned PhysReg) const { 1794 unsigned NumConflicts = 0; 1795 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1796 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1797 E = mri_->reg_end(); I != E; ++I) { 1798 MachineOperand &O = I.getOperand(); 1799 MachineInstr *MI = O.getParent(); 1800 unsigned Index = getInstructionIndex(MI); 1801 if (pli.liveAt(Index)) 1802 ++NumConflicts; 1803 } 1804 return NumConflicts; 1805} 1806 1807/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1808/// around all defs and uses of the specified interval. 1809void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1810 unsigned PhysReg, VirtRegMap &vrm) { 1811 unsigned SpillReg = getRepresentativeReg(PhysReg); 1812 1813 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1814 // If there are registers which alias PhysReg, but which are not a 1815 // sub-register of the chosen representative super register. Assert 1816 // since we can't handle it yet. 1817 assert(*AS == SpillReg || !allocatableRegs_[*AS] || 1818 tri_->isSuperRegister(*AS, SpillReg)); 1819 1820 LiveInterval &pli = getInterval(SpillReg); 1821 SmallPtrSet<MachineInstr*, 8> SeenMIs; 1822 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1823 E = mri_->reg_end(); I != E; ++I) { 1824 MachineOperand &O = I.getOperand(); 1825 MachineInstr *MI = O.getParent(); 1826 if (SeenMIs.count(MI)) 1827 continue; 1828 SeenMIs.insert(MI); 1829 unsigned Index = getInstructionIndex(MI); 1830 if (pli.liveAt(Index)) { 1831 vrm.addEmergencySpill(SpillReg, MI); 1832 pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1833 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 1834 if (!hasInterval(*AS)) 1835 continue; 1836 LiveInterval &spli = getInterval(*AS); 1837 if (spli.liveAt(Index)) 1838 spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1839 } 1840 } 1841 } 1842} 1843