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