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