LiveIntervalAnalysis.cpp revision a8d94f1315f722de056af03763664b77a5baac26
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. The target may permit other 340 // instructions to be re-materialized as well. 341 int FrameIdx = 0; 342 if (vi.DefInst && 343 (tii_->isTriviallyReMaterializable(vi.DefInst) || 344 (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) && 345 mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)))) 346 interval.remat = vi.DefInst; 347 348 // Get the Idx of the defining instructions. 349 unsigned defIndex = getDefIndex(MIIdx); 350 351 unsigned ValNum; 352 unsigned SrcReg, DstReg; 353 if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 354 ValNum = interval.getNextValue(defIndex, 0); 355 else 356 ValNum = interval.getNextValue(defIndex, SrcReg); 357 358 assert(ValNum == 0 && "First value in interval is not 0?"); 359 ValNum = 0; // Clue in the optimizer. 360 361 // Loop over all of the blocks that the vreg is defined in. There are 362 // two cases we have to handle here. The most common case is a vreg 363 // whose lifetime is contained within a basic block. In this case there 364 // will be a single kill, in MBB, which comes after the definition. 365 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 366 // FIXME: what about dead vars? 367 unsigned killIdx; 368 if (vi.Kills[0] != mi) 369 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 370 else 371 killIdx = defIndex+1; 372 373 // If the kill happens after the definition, we have an intra-block 374 // live range. 375 if (killIdx > defIndex) { 376 assert(vi.AliveBlocks.none() && 377 "Shouldn't be alive across any blocks!"); 378 LiveRange LR(defIndex, killIdx, ValNum); 379 interval.addRange(LR); 380 DOUT << " +" << LR << "\n"; 381 return; 382 } 383 } 384 385 // The other case we handle is when a virtual register lives to the end 386 // of the defining block, potentially live across some blocks, then is 387 // live into some number of blocks, but gets killed. Start by adding a 388 // range that goes from this definition to the end of the defining block. 389 LiveRange NewLR(defIndex, 390 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 391 ValNum); 392 DOUT << " +" << NewLR; 393 interval.addRange(NewLR); 394 395 // Iterate over all of the blocks that the variable is completely 396 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 397 // live interval. 398 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 399 if (vi.AliveBlocks[i]) { 400 MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 401 if (!MBB->empty()) { 402 LiveRange LR(getMBBStartIdx(i), 403 getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 404 ValNum); 405 interval.addRange(LR); 406 DOUT << " +" << LR; 407 } 408 } 409 } 410 411 // Finally, this virtual register is live from the start of any killing 412 // block to the 'use' slot of the killing instruction. 413 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 414 MachineInstr *Kill = vi.Kills[i]; 415 LiveRange LR(getMBBStartIdx(Kill->getParent()), 416 getUseIndex(getInstructionIndex(Kill))+1, 417 ValNum); 418 interval.addRange(LR); 419 DOUT << " +" << LR; 420 } 421 422 } else { 423 // Can no longer safely assume definition is rematerializable. 424 interval.remat = NULL; 425 426 // If this is the second time we see a virtual register definition, it 427 // must be due to phi elimination or two addr elimination. If this is 428 // the result of two address elimination, then the vreg is one of the 429 // def-and-use register operand. 430 if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) { 431 // If this is a two-address definition, then we have already processed 432 // the live range. The only problem is that we didn't realize there 433 // are actually two values in the live interval. Because of this we 434 // need to take the LiveRegion that defines this register and split it 435 // into two values. 436 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 437 unsigned RedefIndex = getDefIndex(MIIdx); 438 439 // Delete the initial value, which should be short and continuous, 440 // because the 2-addr copy must be in the same MBB as the redef. 441 interval.removeRange(DefIndex, RedefIndex); 442 443 // Two-address vregs should always only be redefined once. This means 444 // that at this point, there should be exactly one value number in it. 445 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 446 447 // The new value number (#1) is defined by the instruction we claimed 448 // defined value #0. 449 unsigned ValNo = interval.getNextValue(0, 0); 450 interval.setValueNumberInfo(1, interval.getValNumInfo(0)); 451 452 // Value#0 is now defined by the 2-addr instruction. 453 interval.setValueNumberInfo(0, LiveInterval::VNInfo(DefIndex, ~0U, 0U)); 454 455 // Add the new live interval which replaces the range for the input copy. 456 LiveRange LR(DefIndex, RedefIndex, ValNo); 457 DOUT << " replace range with " << LR; 458 interval.addRange(LR); 459 460 // If this redefinition is dead, we need to add a dummy unit live 461 // range covering the def slot. 462 if (lv_->RegisterDefIsDead(mi, interval.reg)) 463 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 464 465 DOUT << " RESULT: "; 466 interval.print(DOUT, mri_); 467 468 } else { 469 // Otherwise, this must be because of phi elimination. If this is the 470 // first redefinition of the vreg that we have seen, go back and change 471 // the live range in the PHI block to be a different value number. 472 if (interval.containsOneValue()) { 473 assert(vi.Kills.size() == 1 && 474 "PHI elimination vreg should have one kill, the PHI itself!"); 475 476 // Remove the old range that we now know has an incorrect number. 477 MachineInstr *Killer = vi.Kills[0]; 478 unsigned Start = getMBBStartIdx(Killer->getParent()); 479 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 480 DOUT << " Removing [" << Start << "," << End << "] from: "; 481 interval.print(DOUT, mri_); DOUT << "\n"; 482 interval.removeRange(Start, End); 483 DOUT << " RESULT: "; interval.print(DOUT, mri_); 484 485 // Replace the interval with one of a NEW value number. Note that this 486 // value number isn't actually defined by an instruction, weird huh? :) 487 LiveRange LR(Start, End, interval.getNextValue(~0, 0)); 488 DOUT << " replace range with " << LR; 489 interval.addRange(LR); 490 DOUT << " RESULT: "; interval.print(DOUT, mri_); 491 } 492 493 // In the case of PHI elimination, each variable definition is only 494 // live until the end of the block. We've already taken care of the 495 // rest of the live range. 496 unsigned defIndex = getDefIndex(MIIdx); 497 498 unsigned ValNum; 499 unsigned SrcReg, DstReg; 500 if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 501 ValNum = interval.getNextValue(defIndex, 0); 502 else 503 ValNum = interval.getNextValue(defIndex, SrcReg); 504 505 LiveRange LR(defIndex, 506 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); 507 interval.addRange(LR); 508 DOUT << " +" << LR; 509 } 510 } 511 512 DOUT << '\n'; 513} 514 515void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 516 MachineBasicBlock::iterator mi, 517 unsigned MIIdx, 518 LiveInterval &interval, 519 unsigned SrcReg) { 520 // A physical register cannot be live across basic block, so its 521 // lifetime must end somewhere in its defining basic block. 522 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 523 524 unsigned baseIndex = MIIdx; 525 unsigned start = getDefIndex(baseIndex); 526 unsigned end = start; 527 528 // If it is not used after definition, it is considered dead at 529 // the instruction defining it. Hence its interval is: 530 // [defSlot(def), defSlot(def)+1) 531 if (lv_->RegisterDefIsDead(mi, interval.reg)) { 532 DOUT << " dead"; 533 end = getDefIndex(start) + 1; 534 goto exit; 535 } 536 537 // If it is not dead on definition, it must be killed by a 538 // subsequent instruction. Hence its interval is: 539 // [defSlot(def), useSlot(kill)+1) 540 while (++mi != MBB->end()) { 541 baseIndex += InstrSlots::NUM; 542 if (lv_->KillsRegister(mi, interval.reg)) { 543 DOUT << " killed"; 544 end = getUseIndex(baseIndex) + 1; 545 goto exit; 546 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 547 // Another instruction redefines the register before it is ever read. 548 // Then the register is essentially dead at the instruction that defines 549 // it. Hence its interval is: 550 // [defSlot(def), defSlot(def)+1) 551 DOUT << " dead"; 552 end = getDefIndex(start) + 1; 553 goto exit; 554 } 555 } 556 557 // The only case we should have a dead physreg here without a killing or 558 // instruction where we know it's dead is if it is live-in to the function 559 // and never used. 560 assert(!SrcReg && "physreg was not killed in defining block!"); 561 end = getDefIndex(start) + 1; // It's dead. 562 563exit: 564 assert(start < end && "did not find end of interval?"); 565 566 // Already exists? Extend old live interval. 567 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 568 unsigned Id = (OldLR != interval.end()) 569 ? OldLR->ValId : interval.getNextValue(start, 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 // Live-in register might not be used at all. 626 if (end == MIIdx) { 627 if (isAlias) { 628 DOUT << " dead"; 629 end = getDefIndex(MIIdx) + 1; 630 } else { 631 DOUT << " live through"; 632 end = baseIndex; 633 } 634 } 635 636 LiveRange LR(start, end, interval.getNextValue(start, 0)); 637 DOUT << " +" << LR << '\n'; 638 interval.addRange(LR); 639} 640 641/// computeIntervals - computes the live intervals for virtual 642/// registers. for some ordering of the machine instructions [1,N] a 643/// live interval is an interval [i, j) where 1 <= i <= j < N for 644/// which a variable is live 645void LiveIntervals::computeIntervals() { 646 DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 647 << "********** Function: " 648 << ((Value*)mf_->getFunction())->getName() << '\n'; 649 // Track the index of the current machine instr. 650 unsigned MIIndex = 0; 651 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 652 MBBI != E; ++MBBI) { 653 MachineBasicBlock *MBB = MBBI; 654 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 655 656 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 657 658 if (MBB->livein_begin() != MBB->livein_end()) { 659 // Create intervals for live-ins to this BB first. 660 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 661 LE = MBB->livein_end(); LI != LE; ++LI) { 662 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 663 // Multiple live-ins can alias the same register. 664 for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 665 if (!hasInterval(*AS)) 666 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 667 true); 668 } 669 } 670 671 for (; MI != miEnd; ++MI) { 672 DOUT << MIIndex << "\t" << *MI; 673 674 // Handle defs. 675 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 676 MachineOperand &MO = MI->getOperand(i); 677 // handle register defs - build intervals 678 if (MO.isRegister() && MO.getReg() && MO.isDef()) 679 handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 680 } 681 682 MIIndex += InstrSlots::NUM; 683 } 684 } 685} 686 687LiveInterval LiveIntervals::createInterval(unsigned reg) { 688 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 689 HUGE_VALF : 0.0F; 690 return LiveInterval(reg, Weight); 691} 692