LiveIntervalAnalysis.cpp revision 5d446265c740c17ed12e693423f0363296670d60
1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveInterval analysis pass which is used 11// by the Linear Scan Register allocator. This pass linearizes the 12// basic blocks of the function in DFS order and uses the 13// LiveVariables pass to conservatively compute live intervals for 14// each virtual and physical register. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "liveintervals" 19#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20#include "VirtRegMap.h" 21#include "llvm/Value.h" 22#include "llvm/CodeGen/LiveVariables.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/SSARegMap.h" 27#include "llvm/Target/MRegisterInfo.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetMachine.h" 30#include "llvm/Support/CommandLine.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/ADT/Statistic.h" 33#include "llvm/ADT/STLExtras.h" 34#include <algorithm> 35#include <cmath> 36using namespace llvm; 37 38namespace { 39 // Hidden options for help debugging. 40 cl::opt<bool> DisableReMat("disable-rematerialization", 41 cl::init(false), cl::Hidden); 42} 43 44STATISTIC(numIntervals, "Number of original intervals"); 45STATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 46STATISTIC(numFolded , "Number of loads/stores folded into instructions"); 47 48char LiveIntervals::ID = 0; 49namespace { 50 RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 51} 52 53void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 54 AU.addPreserved<LiveVariables>(); 55 AU.addRequired<LiveVariables>(); 56 AU.addPreservedID(PHIEliminationID); 57 AU.addRequiredID(PHIEliminationID); 58 AU.addRequiredID(TwoAddressInstructionPassID); 59 MachineFunctionPass::getAnalysisUsage(AU); 60} 61 62void LiveIntervals::releaseMemory() { 63 Idx2MBBMap.clear(); 64 mi2iMap_.clear(); 65 i2miMap_.clear(); 66 r2iMap_.clear(); 67 // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 68 VNInfoAllocator.Reset(); 69 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 70 delete ClonedMIs[i]; 71} 72 73namespace llvm { 74 inline bool operator<(unsigned V, const IdxMBBPair &IM) { 75 return V < IM.first; 76 } 77 78 inline bool operator<(const IdxMBBPair &IM, unsigned V) { 79 return IM.first < V; 80 } 81 82 struct Idx2MBBCompare { 83 bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const { 84 return LHS.first < RHS.first; 85 } 86 }; 87} 88 89/// runOnMachineFunction - Register allocate the whole function 90/// 91bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 92 mf_ = &fn; 93 tm_ = &fn.getTarget(); 94 mri_ = tm_->getRegisterInfo(); 95 tii_ = tm_->getInstrInfo(); 96 lv_ = &getAnalysis<LiveVariables>(); 97 allocatableRegs_ = mri_->getAllocatableSet(fn); 98 99 // Number MachineInstrs and MachineBasicBlocks. 100 // Initialize MBB indexes to a sentinal. 101 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 102 103 unsigned MIIndex = 0; 104 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 105 MBB != E; ++MBB) { 106 unsigned StartIdx = MIIndex; 107 108 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 109 I != E; ++I) { 110 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 111 assert(inserted && "multiple MachineInstr -> index mappings"); 112 i2miMap_.push_back(I); 113 MIIndex += InstrSlots::NUM; 114 } 115 116 // Set the MBB2IdxMap entry for this MBB. 117 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 118 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 119 } 120 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 121 122 computeIntervals(); 123 124 numIntervals += getNumIntervals(); 125 126 DOUT << "********** INTERVALS **********\n"; 127 for (iterator I = begin(), E = end(); I != E; ++I) { 128 I->second.print(DOUT, mri_); 129 DOUT << "\n"; 130 } 131 132 numIntervalsAfter += getNumIntervals(); 133 DEBUG(dump()); 134 return true; 135} 136 137/// print - Implement the dump method. 138void LiveIntervals::print(std::ostream &O, const Module* ) const { 139 O << "********** INTERVALS **********\n"; 140 for (const_iterator I = begin(), E = end(); I != E; ++I) { 141 I->second.print(DOUT, mri_); 142 DOUT << "\n"; 143 } 144 145 O << "********** MACHINEINSTRS **********\n"; 146 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 147 mbbi != mbbe; ++mbbi) { 148 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 149 for (MachineBasicBlock::iterator mii = mbbi->begin(), 150 mie = mbbi->end(); mii != mie; ++mii) { 151 O << getInstructionIndex(mii) << '\t' << *mii; 152 } 153 } 154} 155 156/// conflictsWithPhysRegDef - Returns true if the specified register 157/// is defined during the duration of the specified interval. 158bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 159 VirtRegMap &vrm, unsigned reg) { 160 for (LiveInterval::Ranges::const_iterator 161 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 162 for (unsigned index = getBaseIndex(I->start), 163 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 164 index += InstrSlots::NUM) { 165 // skip deleted instructions 166 while (index != end && !getInstructionFromIndex(index)) 167 index += InstrSlots::NUM; 168 if (index == end) break; 169 170 MachineInstr *MI = getInstructionFromIndex(index); 171 unsigned SrcReg, DstReg; 172 if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 173 if (SrcReg == li.reg || DstReg == li.reg) 174 continue; 175 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 176 MachineOperand& mop = MI->getOperand(i); 177 if (!mop.isRegister()) 178 continue; 179 unsigned PhysReg = mop.getReg(); 180 if (PhysReg == 0 || PhysReg == li.reg) 181 continue; 182 if (MRegisterInfo::isVirtualRegister(PhysReg)) { 183 if (!vrm.hasPhys(PhysReg)) 184 continue; 185 PhysReg = vrm.getPhys(PhysReg); 186 } 187 if (PhysReg && mri_->regsOverlap(PhysReg, reg)) 188 return true; 189 } 190 } 191 } 192 193 return false; 194} 195 196void LiveIntervals::printRegName(unsigned reg) const { 197 if (MRegisterInfo::isPhysicalRegister(reg)) 198 cerr << mri_->getName(reg); 199 else 200 cerr << "%reg" << reg; 201} 202 203void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 204 MachineBasicBlock::iterator mi, 205 unsigned MIIdx, 206 LiveInterval &interval) { 207 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 208 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 209 210 // Virtual registers may be defined multiple times (due to phi 211 // elimination and 2-addr elimination). Much of what we do only has to be 212 // done once for the vreg. We use an empty interval to detect the first 213 // time we see a vreg. 214 if (interval.empty()) { 215 // Get the Idx of the defining instructions. 216 unsigned defIndex = getDefIndex(MIIdx); 217 VNInfo *ValNo; 218 unsigned SrcReg, DstReg; 219 if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 220 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 221 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 222 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 223 VNInfoAllocator); 224 else 225 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 226 227 assert(ValNo->id == 0 && "First value in interval is not 0?"); 228 229 // Loop over all of the blocks that the vreg is defined in. There are 230 // two cases we have to handle here. The most common case is a vreg 231 // whose lifetime is contained within a basic block. In this case there 232 // will be a single kill, in MBB, which comes after the definition. 233 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 234 // FIXME: what about dead vars? 235 unsigned killIdx; 236 if (vi.Kills[0] != mi) 237 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 238 else 239 killIdx = defIndex+1; 240 241 // If the kill happens after the definition, we have an intra-block 242 // live range. 243 if (killIdx > defIndex) { 244 assert(vi.AliveBlocks.none() && 245 "Shouldn't be alive across any blocks!"); 246 LiveRange LR(defIndex, killIdx, ValNo); 247 interval.addRange(LR); 248 DOUT << " +" << LR << "\n"; 249 interval.addKill(ValNo, killIdx); 250 return; 251 } 252 } 253 254 // The other case we handle is when a virtual register lives to the end 255 // of the defining block, potentially live across some blocks, then is 256 // live into some number of blocks, but gets killed. Start by adding a 257 // range that goes from this definition to the end of the defining block. 258 LiveRange NewLR(defIndex, 259 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 260 ValNo); 261 DOUT << " +" << NewLR; 262 interval.addRange(NewLR); 263 264 // Iterate over all of the blocks that the variable is completely 265 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 266 // live interval. 267 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 268 if (vi.AliveBlocks[i]) { 269 MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 270 if (!MBB->empty()) { 271 LiveRange LR(getMBBStartIdx(i), 272 getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 273 ValNo); 274 interval.addRange(LR); 275 DOUT << " +" << LR; 276 } 277 } 278 } 279 280 // Finally, this virtual register is live from the start of any killing 281 // block to the 'use' slot of the killing instruction. 282 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 283 MachineInstr *Kill = vi.Kills[i]; 284 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 285 LiveRange LR(getMBBStartIdx(Kill->getParent()), 286 killIdx, ValNo); 287 interval.addRange(LR); 288 interval.addKill(ValNo, killIdx); 289 DOUT << " +" << LR; 290 } 291 292 } else { 293 // If this is the second time we see a virtual register definition, it 294 // must be due to phi elimination or two addr elimination. If this is 295 // the result of two address elimination, then the vreg is one of the 296 // def-and-use register operand. 297 if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 298 // If this is a two-address definition, then we have already processed 299 // the live range. The only problem is that we didn't realize there 300 // are actually two values in the live interval. Because of this we 301 // need to take the LiveRegion that defines this register and split it 302 // into two values. 303 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 304 unsigned RedefIndex = getDefIndex(MIIdx); 305 306 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 307 VNInfo *OldValNo = OldLR->valno; 308 unsigned OldEnd = OldLR->end; 309 310 // Delete the initial value, which should be short and continuous, 311 // because the 2-addr copy must be in the same MBB as the redef. 312 interval.removeRange(DefIndex, RedefIndex); 313 314 // Two-address vregs should always only be redefined once. This means 315 // that at this point, there should be exactly one value number in it. 316 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 317 318 // The new value number (#1) is defined by the instruction we claimed 319 // defined value #0. 320 VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator); 321 interval.copyValNumInfo(ValNo, OldValNo); 322 323 // Value#0 is now defined by the 2-addr instruction. 324 OldValNo->def = RedefIndex; 325 OldValNo->reg = 0; 326 327 // Add the new live interval which replaces the range for the input copy. 328 LiveRange LR(DefIndex, RedefIndex, ValNo); 329 DOUT << " replace range with " << LR; 330 interval.addRange(LR); 331 interval.addKill(ValNo, RedefIndex); 332 interval.removeKills(ValNo, RedefIndex, OldEnd); 333 334 // If this redefinition is dead, we need to add a dummy unit live 335 // range covering the def slot. 336 if (lv_->RegisterDefIsDead(mi, interval.reg)) 337 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 338 339 DOUT << " RESULT: "; 340 interval.print(DOUT, mri_); 341 342 } else { 343 // Otherwise, this must be because of phi elimination. If this is the 344 // first redefinition of the vreg that we have seen, go back and change 345 // the live range in the PHI block to be a different value number. 346 if (interval.containsOneValue()) { 347 assert(vi.Kills.size() == 1 && 348 "PHI elimination vreg should have one kill, the PHI itself!"); 349 350 // Remove the old range that we now know has an incorrect number. 351 VNInfo *VNI = interval.getValNumInfo(0); 352 MachineInstr *Killer = vi.Kills[0]; 353 unsigned Start = getMBBStartIdx(Killer->getParent()); 354 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 355 DOUT << " Removing [" << Start << "," << End << "] from: "; 356 interval.print(DOUT, mri_); DOUT << "\n"; 357 interval.removeRange(Start, End); 358 interval.addKill(VNI, Start+1); // odd # means phi node 359 DOUT << " RESULT: "; interval.print(DOUT, mri_); 360 361 // Replace the interval with one of a NEW value number. Note that this 362 // value number isn't actually defined by an instruction, weird huh? :) 363 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 364 DOUT << " replace range with " << LR; 365 interval.addRange(LR); 366 interval.addKill(LR.valno, End); 367 DOUT << " RESULT: "; interval.print(DOUT, mri_); 368 } 369 370 // In the case of PHI elimination, each variable definition is only 371 // live until the end of the block. We've already taken care of the 372 // rest of the live range. 373 unsigned defIndex = getDefIndex(MIIdx); 374 375 VNInfo *ValNo; 376 unsigned SrcReg, DstReg; 377 if (tii_->isMoveInstr(*mi, SrcReg, DstReg)) 378 ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator); 379 else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 380 ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(), 381 VNInfoAllocator); 382 else 383 ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator); 384 385 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 386 LiveRange LR(defIndex, killIndex, ValNo); 387 interval.addRange(LR); 388 interval.addKill(ValNo, killIndex-1); // odd # means phi node 389 DOUT << " +" << LR; 390 } 391 } 392 393 DOUT << '\n'; 394} 395 396void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 397 MachineBasicBlock::iterator mi, 398 unsigned MIIdx, 399 LiveInterval &interval, 400 unsigned SrcReg) { 401 // A physical register cannot be live across basic block, so its 402 // lifetime must end somewhere in its defining basic block. 403 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 404 405 unsigned baseIndex = MIIdx; 406 unsigned start = getDefIndex(baseIndex); 407 unsigned end = start; 408 409 // If it is not used after definition, it is considered dead at 410 // the instruction defining it. Hence its interval is: 411 // [defSlot(def), defSlot(def)+1) 412 if (lv_->RegisterDefIsDead(mi, interval.reg)) { 413 DOUT << " dead"; 414 end = getDefIndex(start) + 1; 415 goto exit; 416 } 417 418 // If it is not dead on definition, it must be killed by a 419 // subsequent instruction. Hence its interval is: 420 // [defSlot(def), useSlot(kill)+1) 421 while (++mi != MBB->end()) { 422 baseIndex += InstrSlots::NUM; 423 if (lv_->KillsRegister(mi, interval.reg)) { 424 DOUT << " killed"; 425 end = getUseIndex(baseIndex) + 1; 426 goto exit; 427 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 428 // Another instruction redefines the register before it is ever read. 429 // Then the register is essentially dead at the instruction that defines 430 // it. Hence its interval is: 431 // [defSlot(def), defSlot(def)+1) 432 DOUT << " dead"; 433 end = getDefIndex(start) + 1; 434 goto exit; 435 } 436 } 437 438 // The only case we should have a dead physreg here without a killing or 439 // instruction where we know it's dead is if it is live-in to the function 440 // and never used. 441 assert(!SrcReg && "physreg was not killed in defining block!"); 442 end = getDefIndex(start) + 1; // It's dead. 443 444exit: 445 assert(start < end && "did not find end of interval?"); 446 447 // Already exists? Extend old live interval. 448 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 449 VNInfo *ValNo = (OldLR != interval.end()) 450 ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator); 451 LiveRange LR(start, end, ValNo); 452 interval.addRange(LR); 453 interval.addKill(LR.valno, end); 454 DOUT << " +" << LR << '\n'; 455} 456 457void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 458 MachineBasicBlock::iterator MI, 459 unsigned MIIdx, 460 unsigned reg) { 461 if (MRegisterInfo::isVirtualRegister(reg)) 462 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 463 else if (allocatableRegs_[reg]) { 464 unsigned SrcReg, DstReg; 465 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 466 SrcReg = MI->getOperand(1).getReg(); 467 else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 468 SrcReg = 0; 469 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 470 // Def of a register also defines its sub-registers. 471 for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 472 // Avoid processing some defs more than once. 473 if (!MI->findRegisterDefOperand(*AS)) 474 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 475 } 476} 477 478void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 479 unsigned MIIdx, 480 LiveInterval &interval, bool isAlias) { 481 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 482 483 // Look for kills, if it reaches a def before it's killed, then it shouldn't 484 // be considered a livein. 485 MachineBasicBlock::iterator mi = MBB->begin(); 486 unsigned baseIndex = MIIdx; 487 unsigned start = baseIndex; 488 unsigned end = start; 489 while (mi != MBB->end()) { 490 if (lv_->KillsRegister(mi, interval.reg)) { 491 DOUT << " killed"; 492 end = getUseIndex(baseIndex) + 1; 493 goto exit; 494 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 495 // Another instruction redefines the register before it is ever read. 496 // Then the register is essentially dead at the instruction that defines 497 // it. Hence its interval is: 498 // [defSlot(def), defSlot(def)+1) 499 DOUT << " dead"; 500 end = getDefIndex(start) + 1; 501 goto exit; 502 } 503 504 baseIndex += InstrSlots::NUM; 505 ++mi; 506 } 507 508exit: 509 // Live-in register might not be used at all. 510 if (end == MIIdx) { 511 if (isAlias) { 512 DOUT << " dead"; 513 end = getDefIndex(MIIdx) + 1; 514 } else { 515 DOUT << " live through"; 516 end = baseIndex; 517 } 518 } 519 520 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 521 interval.addRange(LR); 522 interval.addKill(LR.valno, end); 523 DOUT << " +" << LR << '\n'; 524} 525 526/// computeIntervals - computes the live intervals for virtual 527/// registers. for some ordering of the machine instructions [1,N] a 528/// live interval is an interval [i, j) where 1 <= i <= j < N for 529/// which a variable is live 530void LiveIntervals::computeIntervals() { 531 DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 532 << "********** Function: " 533 << ((Value*)mf_->getFunction())->getName() << '\n'; 534 // Track the index of the current machine instr. 535 unsigned MIIndex = 0; 536 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 537 MBBI != E; ++MBBI) { 538 MachineBasicBlock *MBB = MBBI; 539 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 540 541 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 542 543 // Create intervals for live-ins to this BB first. 544 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 545 LE = MBB->livein_end(); LI != LE; ++LI) { 546 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 547 // Multiple live-ins can alias the same register. 548 for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 549 if (!hasInterval(*AS)) 550 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 551 true); 552 } 553 554 for (; MI != miEnd; ++MI) { 555 DOUT << MIIndex << "\t" << *MI; 556 557 // Handle defs. 558 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 559 MachineOperand &MO = MI->getOperand(i); 560 // handle register defs - build intervals 561 if (MO.isRegister() && MO.getReg() && MO.isDef()) 562 handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 563 } 564 565 MIIndex += InstrSlots::NUM; 566 } 567 } 568} 569 570bool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 571 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 572 std::vector<IdxMBBPair>::const_iterator I = 573 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 574 575 bool ResVal = false; 576 while (I != Idx2MBBMap.end()) { 577 if (LR.end <= I->first) 578 break; 579 MBBs.push_back(I->second); 580 ResVal = true; 581 ++I; 582 } 583 return ResVal; 584} 585 586 587LiveInterval LiveIntervals::createInterval(unsigned reg) { 588 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 589 HUGE_VALF : 0.0F; 590 return LiveInterval(reg, Weight); 591} 592 593 594//===----------------------------------------------------------------------===// 595// Register allocator hooks. 596// 597 598/// isReMaterializable - Returns true if the definition MI of the specified 599/// val# of the specified interval is re-materializable. 600bool LiveIntervals::isReMaterializable(const LiveInterval &li, 601 const VNInfo *ValNo, MachineInstr *MI) { 602 if (DisableReMat) 603 return false; 604 605 if (tii_->isTriviallyReMaterializable(MI)) 606 return true; 607 608 int FrameIdx = 0; 609 if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || 610 !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) 611 return false; 612 613 // This is a load from fixed stack slot. It can be rematerialized unless it's 614 // re-defined by a two-address instruction. 615 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 616 i != e; ++i) { 617 const VNInfo *VNI = *i; 618 if (VNI == ValNo) 619 continue; 620 unsigned DefIdx = VNI->def; 621 if (DefIdx == ~1U) 622 continue; // Dead val#. 623 MachineInstr *DefMI = (DefIdx == ~0u) 624 ? NULL : getInstructionFromIndex(DefIdx); 625 if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) 626 return false; 627 } 628 return true; 629} 630 631/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 632/// slot / to reg or any rematerialized load into ith operand of specified 633/// MI. If it is successul, MI is updated with the newly created MI and 634/// returns true. 635bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 636 MachineInstr *DefMI, 637 unsigned index, unsigned i, 638 bool isSS, int slot, unsigned reg) { 639 MachineInstr *fmi = isSS 640 ? mri_->foldMemoryOperand(MI, i, slot) 641 : mri_->foldMemoryOperand(MI, i, DefMI); 642 if (fmi) { 643 // Attempt to fold the memory reference into the instruction. If 644 // we can do this, we don't need to insert spill code. 645 if (lv_) 646 lv_->instructionChanged(MI, fmi); 647 MachineBasicBlock &MBB = *MI->getParent(); 648 vrm.virtFolded(reg, MI, i, fmi); 649 mi2iMap_.erase(MI); 650 i2miMap_[index/InstrSlots::NUM] = fmi; 651 mi2iMap_[fmi] = index; 652 MI = MBB.insert(MBB.erase(MI), fmi); 653 ++numFolded; 654 return true; 655 } 656 return false; 657} 658 659/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 660/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 661void LiveIntervals:: 662rewriteInstructionForSpills(const LiveInterval &li, 663 unsigned id, unsigned index, unsigned end, 664 MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, 665 unsigned Slot, int LdSlot, 666 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 667 VirtRegMap &vrm, SSARegMap *RegMap, 668 const TargetRegisterClass* rc, 669 SmallVector<int, 4> &ReMatIds, 670 std::vector<LiveInterval*> &NewLIs) { 671 RestartInstruction: 672 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 673 MachineOperand& mop = MI->getOperand(i); 674 if (!mop.isRegister()) 675 continue; 676 unsigned Reg = mop.getReg(); 677 unsigned RegI = Reg; 678 if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg)) 679 continue; 680 unsigned SubIdx = mop.getSubReg(); 681 bool isSubReg = SubIdx != 0; 682 if (Reg != li.reg) 683 continue; 684 685 bool TryFold = !DefIsReMat; 686 bool FoldSS = true; 687 int FoldSlot = Slot; 688 if (DefIsReMat) { 689 // If this is the rematerializable definition MI itself and 690 // all of its uses are rematerialized, simply delete it. 691 if (MI == OrigDefMI && CanDelete) { 692 RemoveMachineInstrFromMaps(MI); 693 MI->eraseFromParent(); 694 break; 695 } 696 697 // If def for this use can't be rematerialized, then try folding. 698 TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad)); 699 if (isLoad) { 700 // Try fold loads (from stack slot, constant pool, etc.) into uses. 701 FoldSS = isLoadSS; 702 FoldSlot = LdSlot; 703 } 704 } 705 706 // FIXME: fold subreg use 707 if (!isSubReg && TryFold && 708 tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg)) 709 // Folding the load/store can completely change the instruction in 710 // unpredictable ways, rescan it from the beginning. 711 goto RestartInstruction; 712 713 // Create a new virtual register for the spill interval. 714 unsigned NewVReg = RegMap->createVirtualRegister(rc); 715 vrm.grow(); 716 717 // Scan all of the operands of this instruction rewriting operands 718 // to use NewVReg instead of li.reg as appropriate. We do this for 719 // two reasons: 720 // 721 // 1. If the instr reads the same spilled vreg multiple times, we 722 // want to reuse the NewVReg. 723 // 2. If the instr is a two-addr instruction, we are required to 724 // keep the src/dst regs pinned. 725 // 726 // Keep track of whether we replace a use and/or def so that we can 727 // create the spill interval with the appropriate range. 728 mop.setReg(NewVReg); 729 730 bool HasUse = mop.isUse(); 731 bool HasDef = mop.isDef(); 732 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 733 if (!MI->getOperand(j).isRegister()) 734 continue; 735 unsigned RegJ = MI->getOperand(j).getReg(); 736 if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ)) 737 continue; 738 if (RegJ == RegI) { 739 MI->getOperand(j).setReg(NewVReg); 740 HasUse |= MI->getOperand(j).isUse(); 741 HasDef |= MI->getOperand(j).isDef(); 742 } 743 } 744 745 if (DefIsReMat) { 746 vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/); 747 if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) { 748 // Each valnum may have its own remat id. 749 ReMatIds[id] = vrm.assignVirtReMatId(NewVReg); 750 } else { 751 vrm.assignVirtReMatId(NewVReg, ReMatIds[id]); 752 } 753 if (!CanDelete || (HasUse && HasDef)) { 754 // If this is a two-addr instruction then its use operands are 755 // rematerializable but its def is not. It should be assigned a 756 // stack slot. 757 vrm.assignVirt2StackSlot(NewVReg, Slot); 758 } 759 } else { 760 vrm.assignVirt2StackSlot(NewVReg, Slot); 761 } 762 763 // create a new register interval for this spill / remat. 764 LiveInterval &nI = getOrCreateInterval(NewVReg); 765 assert(nI.empty()); 766 NewLIs.push_back(&nI); 767 768 // the spill weight is now infinity as it 769 // cannot be spilled again 770 nI.weight = HUGE_VALF; 771 772 if (HasUse) { 773 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 774 nI.getNextValue(~0U, 0, VNInfoAllocator)); 775 DOUT << " +" << LR; 776 nI.addRange(LR); 777 } 778 if (HasDef) { 779 LiveRange LR(getDefIndex(index), getStoreIndex(index), 780 nI.getNextValue(~0U, 0, VNInfoAllocator)); 781 DOUT << " +" << LR; 782 nI.addRange(LR); 783 } 784 785 // update live variables if it is available 786 if (lv_) 787 lv_->addVirtualRegisterKilled(NewVReg, MI); 788 789 DOUT << "\t\t\t\tAdded new interval: "; 790 nI.print(DOUT, mri_); 791 DOUT << '\n'; 792 } 793} 794 795void LiveIntervals:: 796rewriteInstructionsForSpills(const LiveInterval &li, 797 LiveInterval::Ranges::const_iterator &I, 798 MachineInstr *OrigDefMI, MachineInstr *DefMI, 799 unsigned Slot, int LdSlot, 800 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 801 VirtRegMap &vrm, SSARegMap *RegMap, 802 const TargetRegisterClass* rc, 803 SmallVector<int, 4> &ReMatIds, 804 std::vector<LiveInterval*> &NewLIs) { 805 unsigned index = getBaseIndex(I->start); 806 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 807 for (; index != end; index += InstrSlots::NUM) { 808 // skip deleted instructions 809 while (index != end && !getInstructionFromIndex(index)) 810 index += InstrSlots::NUM; 811 if (index == end) break; 812 813 MachineInstr *MI = getInstructionFromIndex(index); 814 rewriteInstructionForSpills(li, I->valno->id, index, end, MI, 815 OrigDefMI, DefMI, Slot, LdSlot, isLoad, 816 isLoadSS, DefIsReMat, CanDelete, vrm, 817 RegMap, rc, ReMatIds, NewLIs); 818 } 819} 820 821std::vector<LiveInterval*> LiveIntervals:: 822addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm) { 823 // Since this is called after the analysis is done we don't know if 824 // LiveVariables is available 825 lv_ = getAnalysisToUpdate<LiveVariables>(); 826 827 assert(li.weight != HUGE_VALF && 828 "attempt to spill already spilled interval!"); 829 830 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 831 li.print(DOUT, mri_); 832 DOUT << '\n'; 833 834 std::vector<LiveInterval*> NewLIs; 835 SSARegMap *RegMap = mf_->getSSARegMap(); 836 const TargetRegisterClass* rc = RegMap->getRegClass(li.reg); 837 838 unsigned NumValNums = li.getNumValNums(); 839 SmallVector<MachineInstr*, 4> ReMatDefs; 840 ReMatDefs.resize(NumValNums, NULL); 841 SmallVector<MachineInstr*, 4> ReMatOrigDefs; 842 ReMatOrigDefs.resize(NumValNums, NULL); 843 SmallVector<int, 4> ReMatIds; 844 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 845 BitVector ReMatDelete(NumValNums); 846 unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 847 848 bool NeedStackSlot = false; 849 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 850 i != e; ++i) { 851 const VNInfo *VNI = *i; 852 unsigned VN = VNI->id; 853 unsigned DefIdx = VNI->def; 854 if (DefIdx == ~1U) 855 continue; // Dead val#. 856 // Is the def for the val# rematerializable? 857 MachineInstr *DefMI = (DefIdx == ~0u) ? 0 : getInstructionFromIndex(DefIdx); 858 if (DefMI && isReMaterializable(li, VNI, DefMI)) { 859 // Remember how to remat the def of this val#. 860 ReMatOrigDefs[VN] = DefMI; 861 // Original def may be modified so we have to make a copy here. vrm must 862 // delete these! 863 ReMatDefs[VN] = DefMI = DefMI->clone(); 864 vrm.setVirtIsReMaterialized(li.reg, DefMI); 865 866 bool CanDelete = true; 867 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 868 unsigned KillIdx = VNI->kills[j]; 869 MachineInstr *KillMI = (KillIdx & 1) 870 ? NULL : getInstructionFromIndex(KillIdx); 871 // Kill is a phi node, not all of its uses can be rematerialized. 872 // It must not be deleted. 873 if (!KillMI) { 874 CanDelete = false; 875 // Need a stack slot if there is any live range where uses cannot be 876 // rematerialized. 877 NeedStackSlot = true; 878 break; 879 } 880 } 881 882 if (CanDelete) 883 ReMatDelete.set(VN); 884 } else { 885 // Need a stack slot if there is any live range where uses cannot be 886 // rematerialized. 887 NeedStackSlot = true; 888 } 889 } 890 891 // One stack slot per live interval. 892 if (NeedStackSlot) 893 Slot = vrm.assignVirt2StackSlot(li.reg); 894 895 // Create new intervals and rewrite defs and uses. 896 for (LiveInterval::Ranges::const_iterator 897 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 898 MachineInstr *DefMI = ReMatDefs[I->valno->id]; 899 MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id]; 900 bool DefIsReMat = DefMI != NULL; 901 bool CanDelete = ReMatDelete[I->valno->id]; 902 int LdSlot = 0; 903 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot); 904 bool isLoad = isLoadSS || 905 (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG)); 906 rewriteInstructionsForSpills(li, I, OrigDefMI, DefMI, Slot, LdSlot, 907 isLoad, isLoadSS, DefIsReMat, CanDelete, 908 vrm, RegMap, rc, ReMatIds, NewLIs); 909 } 910 911 return NewLIs; 912} 913