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