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