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