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