LiveIntervalAnalysis.cpp revision c718288f4939258a51ec5ae0c5be7b1a05eb6898
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(numJoins , "Number of interval joins performed"); 43STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 44STATISTIC(numFolded , "Number of loads/stores folded into instructions"); 45STATISTIC(numAborts , "Number of times interval joining aborted"); 46 47const int LiveIntervals::ID = 0; 48namespace { 49 RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 50 51 static cl::opt<bool> 52 EnableJoining("join-liveintervals", 53 cl::desc("Coallesce copies (default=true)"), 54 cl::init(true)); 55} 56 57void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 58 AU.addRequired<LiveVariables>(); 59 AU.addPreservedID(PHIEliminationID); 60 AU.addRequiredID(PHIEliminationID); 61 AU.addRequiredID(TwoAddressInstructionPassID); 62 AU.addRequired<LoopInfo>(); 63 MachineFunctionPass::getAnalysisUsage(AU); 64} 65 66void LiveIntervals::releaseMemory() { 67 mi2iMap_.clear(); 68 i2miMap_.clear(); 69 r2iMap_.clear(); 70 r2rMap_.clear(); 71 JoinedLIs.clear(); 72} 73 74 75static bool isZeroLengthInterval(LiveInterval *li) { 76 for (LiveInterval::Ranges::const_iterator 77 i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) 78 if (i->end - i->start > LiveIntervals::InstrSlots::NUM) 79 return false; 80 return true; 81} 82 83 84/// runOnMachineFunction - Register allocate the whole function 85/// 86bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 87 mf_ = &fn; 88 tm_ = &fn.getTarget(); 89 mri_ = tm_->getRegisterInfo(); 90 tii_ = tm_->getInstrInfo(); 91 lv_ = &getAnalysis<LiveVariables>(); 92 r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg()); 93 allocatableRegs_ = mri_->getAllocatableSet(fn); 94 for (MRegisterInfo::regclass_iterator I = mri_->regclass_begin(), 95 E = mri_->regclass_end(); I != E; ++I) 96 allocatableRCRegs_.insert(std::make_pair(*I,mri_->getAllocatableSet(fn, *I))); 97 98 // Number MachineInstrs and MachineBasicBlocks. 99 // Initialize MBB indexes to a sentinal. 100 MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U); 101 102 unsigned MIIndex = 0; 103 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 104 MBB != E; ++MBB) { 105 // Set the MBB2IdxMap entry for this MBB. 106 MBB2IdxMap[MBB->getNumber()] = MIIndex; 107 108 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 109 I != E; ++I) { 110 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 111 assert(inserted && "multiple MachineInstr -> index mappings"); 112 i2miMap_.push_back(I); 113 MIIndex += InstrSlots::NUM; 114 } 115 } 116 117 computeIntervals(); 118 119 numIntervals += getNumIntervals(); 120 121 DOUT << "********** INTERVALS **********\n"; 122 for (iterator I = begin(), E = end(); I != E; ++I) { 123 I->second.print(DOUT, mri_); 124 DOUT << "\n"; 125 } 126 127 // Join (coallesce) intervals if requested. 128 if (EnableJoining) { 129 joinIntervals(); 130 DOUT << "********** INTERVALS POST JOINING **********\n"; 131 for (iterator I = begin(), E = end(); I != E; ++I) { 132 I->second.print(DOUT, mri_); 133 DOUT << "\n"; 134 } 135 } 136 137 numIntervalsAfter += getNumIntervals(); 138 139 // perform a final pass over the instructions and compute spill 140 // weights, coalesce virtual registers and remove identity moves. 141 const LoopInfo &loopInfo = getAnalysis<LoopInfo>(); 142 143 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 144 mbbi != mbbe; ++mbbi) { 145 MachineBasicBlock* mbb = mbbi; 146 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 147 148 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 149 mii != mie; ) { 150 // if the move will be an identity move delete it 151 unsigned srcReg, dstReg, RegRep; 152 if (tii_->isMoveInstr(*mii, srcReg, dstReg) && 153 (RegRep = rep(srcReg)) == rep(dstReg)) { 154 // remove from def list 155 LiveInterval &RegInt = getOrCreateInterval(RegRep); 156 MachineOperand *MO = mii->findRegisterDefOperand(dstReg); 157 // If def of this move instruction is dead, remove its live range from 158 // the dstination register's live interval. 159 if (MO->isDead()) { 160 unsigned MoveIdx = getDefIndex(getInstructionIndex(mii)); 161 LiveInterval::iterator MLR = RegInt.FindLiveRangeContaining(MoveIdx); 162 RegInt.removeRange(MLR->start, MoveIdx+1); 163 if (RegInt.empty()) 164 removeInterval(RegRep); 165 } 166 RemoveMachineInstrFromMaps(mii); 167 mii = mbbi->erase(mii); 168 ++numPeep; 169 } else { 170 SmallSet<unsigned, 4> UniqueUses; 171 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 172 const MachineOperand &mop = mii->getOperand(i); 173 if (mop.isRegister() && mop.getReg() && 174 MRegisterInfo::isVirtualRegister(mop.getReg())) { 175 // replace register with representative register 176 unsigned reg = rep(mop.getReg()); 177 mii->getOperand(i).setReg(reg); 178 179 // Multiple uses of reg by the same instruction. It should not 180 // contribute to spill weight again. 181 if (UniqueUses.count(reg) != 0) 182 continue; 183 LiveInterval &RegInt = getInterval(reg); 184 float w = (mop.isUse()+mop.isDef()) * powf(10.0F, (float)loopDepth); 185 // If the definition instruction is re-materializable, its spill 186 // weight is half of what it would have been normally unless it's 187 // a load from fixed stack slot. 188 int Dummy; 189 if (RegInt.remat && !tii_->isLoadFromStackSlot(RegInt.remat, Dummy)) 190 w /= 2; 191 RegInt.weight += w; 192 UniqueUses.insert(reg); 193 } 194 } 195 ++mii; 196 } 197 } 198 } 199 200 for (iterator I = begin(), E = end(); I != E; ++I) { 201 LiveInterval &LI = I->second; 202 if (MRegisterInfo::isVirtualRegister(LI.reg)) { 203 // If the live interval length is essentially zero, i.e. in every live 204 // range the use follows def immediately, it doesn't make sense to spill 205 // it and hope it will be easier to allocate for this li. 206 if (isZeroLengthInterval(&LI)) 207 LI.weight = HUGE_VALF; 208 209 // Slightly prefer live interval that has been assigned a preferred reg. 210 if (LI.preference) 211 LI.weight *= 1.01F; 212 213 // Divide the weight of the interval by its size. This encourages 214 // spilling of intervals that are large and have few uses, and 215 // discourages spilling of small intervals with many uses. 216 LI.weight /= LI.getSize(); 217 } 218 } 219 220 DEBUG(dump()); 221 return true; 222} 223 224/// print - Implement the dump method. 225void LiveIntervals::print(std::ostream &O, const Module* ) const { 226 O << "********** INTERVALS **********\n"; 227 for (const_iterator I = begin(), E = end(); I != E; ++I) { 228 I->second.print(DOUT, mri_); 229 DOUT << "\n"; 230 } 231 232 O << "********** MACHINEINSTRS **********\n"; 233 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 234 mbbi != mbbe; ++mbbi) { 235 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 236 for (MachineBasicBlock::iterator mii = mbbi->begin(), 237 mie = mbbi->end(); mii != mie; ++mii) { 238 O << getInstructionIndex(mii) << '\t' << *mii; 239 } 240 } 241} 242 243/// CreateNewLiveInterval - Create a new live interval with the given live 244/// ranges. The new live interval will have an infinite spill weight. 245LiveInterval& 246LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI, 247 const std::vector<LiveRange> &LRs) { 248 const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg); 249 250 // Create a new virtual register for the spill interval. 251 unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC); 252 253 // Replace the old virtual registers in the machine operands with the shiny 254 // new one. 255 for (std::vector<LiveRange>::const_iterator 256 I = LRs.begin(), E = LRs.end(); I != E; ++I) { 257 unsigned Index = getBaseIndex(I->start); 258 unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM; 259 260 for (; Index != End; Index += InstrSlots::NUM) { 261 // Skip deleted instructions 262 while (Index != End && !getInstructionFromIndex(Index)) 263 Index += InstrSlots::NUM; 264 265 if (Index == End) break; 266 267 MachineInstr *MI = getInstructionFromIndex(Index); 268 269 for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) { 270 MachineOperand &MOp = MI->getOperand(J); 271 if (MOp.isRegister() && rep(MOp.getReg()) == LI->reg) 272 MOp.setReg(NewVReg); 273 } 274 } 275 } 276 277 LiveInterval &NewLI = getOrCreateInterval(NewVReg); 278 279 // The spill weight is now infinity as it cannot be spilled again 280 NewLI.weight = float(HUGE_VAL); 281 282 for (std::vector<LiveRange>::const_iterator 283 I = LRs.begin(), E = LRs.end(); I != E; ++I) { 284 DOUT << " Adding live range " << *I << " to new interval\n"; 285 NewLI.addRange(*I); 286 } 287 288 DOUT << "Created new live interval " << NewLI << "\n"; 289 return NewLI; 290} 291 292std::vector<LiveInterval*> LiveIntervals:: 293addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) { 294 // since this is called after the analysis is done we don't know if 295 // LiveVariables is available 296 lv_ = getAnalysisToUpdate<LiveVariables>(); 297 298 std::vector<LiveInterval*> added; 299 300 assert(li.weight != HUGE_VALF && 301 "attempt to spill already spilled interval!"); 302 303 DOUT << "\t\t\t\tadding intervals for spills for interval: "; 304 li.print(DOUT, mri_); 305 DOUT << '\n'; 306 307 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 308 309 for (LiveInterval::Ranges::const_iterator 310 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 311 unsigned index = getBaseIndex(i->start); 312 unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 313 for (; index != end; index += InstrSlots::NUM) { 314 // skip deleted instructions 315 while (index != end && !getInstructionFromIndex(index)) 316 index += InstrSlots::NUM; 317 if (index == end) break; 318 319 MachineInstr *MI = getInstructionFromIndex(index); 320 321 RestartInstruction: 322 for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 323 MachineOperand& mop = MI->getOperand(i); 324 if (mop.isRegister() && mop.getReg() == li.reg) { 325 MachineInstr *fmi = li.remat ? NULL 326 : mri_->foldMemoryOperand(MI, i, slot); 327 if (fmi) { 328 // Attempt to fold the memory reference into the instruction. If we 329 // can do this, we don't need to insert spill code. 330 if (lv_) 331 lv_->instructionChanged(MI, fmi); 332 MachineBasicBlock &MBB = *MI->getParent(); 333 vrm.virtFolded(li.reg, MI, i, fmi); 334 mi2iMap_.erase(MI); 335 i2miMap_[index/InstrSlots::NUM] = fmi; 336 mi2iMap_[fmi] = index; 337 MI = MBB.insert(MBB.erase(MI), fmi); 338 ++numFolded; 339 // Folding the load/store can completely change the instruction in 340 // unpredictable ways, rescan it from the beginning. 341 goto RestartInstruction; 342 } else { 343 // Create a new virtual register for the spill interval. 344 unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc); 345 346 // Scan all of the operands of this instruction rewriting operands 347 // to use NewVReg instead of li.reg as appropriate. We do this for 348 // two reasons: 349 // 350 // 1. If the instr reads the same spilled vreg multiple times, we 351 // want to reuse the NewVReg. 352 // 2. If the instr is a two-addr instruction, we are required to 353 // keep the src/dst regs pinned. 354 // 355 // Keep track of whether we replace a use and/or def so that we can 356 // create the spill interval with the appropriate range. 357 mop.setReg(NewVReg); 358 359 bool HasUse = mop.isUse(); 360 bool HasDef = mop.isDef(); 361 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 362 if (MI->getOperand(j).isReg() && 363 MI->getOperand(j).getReg() == li.reg) { 364 MI->getOperand(j).setReg(NewVReg); 365 HasUse |= MI->getOperand(j).isUse(); 366 HasDef |= MI->getOperand(j).isDef(); 367 } 368 } 369 370 // create a new register for this spill 371 vrm.grow(); 372 if (li.remat) 373 vrm.setVirtIsReMaterialized(NewVReg, li.remat); 374 vrm.assignVirt2StackSlot(NewVReg, slot); 375 LiveInterval &nI = getOrCreateInterval(NewVReg); 376 nI.remat = li.remat; 377 assert(nI.empty()); 378 379 // the spill weight is now infinity as it 380 // cannot be spilled again 381 nI.weight = HUGE_VALF; 382 383 if (HasUse) { 384 LiveRange LR(getLoadIndex(index), getUseIndex(index), 385 nI.getNextValue(~0U, 0)); 386 DOUT << " +" << LR; 387 nI.addRange(LR); 388 } 389 if (HasDef) { 390 LiveRange LR(getDefIndex(index), getStoreIndex(index), 391 nI.getNextValue(~0U, 0)); 392 DOUT << " +" << LR; 393 nI.addRange(LR); 394 } 395 396 added.push_back(&nI); 397 398 // update live variables if it is available 399 if (lv_) 400 lv_->addVirtualRegisterKilled(NewVReg, MI); 401 402 DOUT << "\t\t\t\tadded new interval: "; 403 nI.print(DOUT, mri_); 404 DOUT << '\n'; 405 } 406 } 407 } 408 } 409 } 410 411 return added; 412} 413 414void LiveIntervals::printRegName(unsigned reg) const { 415 if (MRegisterInfo::isPhysicalRegister(reg)) 416 cerr << mri_->getName(reg); 417 else 418 cerr << "%reg" << reg; 419} 420 421/// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to 422/// two addr elimination. 423static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg, 424 const TargetInstrInfo *TII) { 425 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 426 MachineOperand &MO1 = MI->getOperand(i); 427 if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) { 428 for (unsigned j = i+1; j < e; ++j) { 429 MachineOperand &MO2 = MI->getOperand(j); 430 if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg && 431 MI->getInstrDescriptor()-> 432 getOperandConstraint(j, TOI::TIED_TO) == (int)i) 433 return true; 434 } 435 } 436 } 437 return false; 438} 439 440void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 441 MachineBasicBlock::iterator mi, 442 unsigned MIIdx, 443 LiveInterval &interval) { 444 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 445 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 446 447 // Virtual registers may be defined multiple times (due to phi 448 // elimination and 2-addr elimination). Much of what we do only has to be 449 // done once for the vreg. We use an empty interval to detect the first 450 // time we see a vreg. 451 if (interval.empty()) { 452 // Remember if the definition can be rematerialized. All load's from fixed 453 // stack slots are re-materializable. 454 int FrameIdx = 0; 455 if (vi.DefInst && 456 (tii_->isReMaterializable(vi.DefInst->getOpcode()) || 457 (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) && 458 mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)))) 459 interval.remat = vi.DefInst; 460 461 // Get the Idx of the defining instructions. 462 unsigned defIndex = getDefIndex(MIIdx); 463 464 unsigned ValNum; 465 unsigned SrcReg, DstReg; 466 if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 467 ValNum = interval.getNextValue(~0U, 0); 468 else 469 ValNum = interval.getNextValue(defIndex, SrcReg); 470 471 assert(ValNum == 0 && "First value in interval is not 0?"); 472 ValNum = 0; // Clue in the optimizer. 473 474 // Loop over all of the blocks that the vreg is defined in. There are 475 // two cases we have to handle here. The most common case is a vreg 476 // whose lifetime is contained within a basic block. In this case there 477 // will be a single kill, in MBB, which comes after the definition. 478 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 479 // FIXME: what about dead vars? 480 unsigned killIdx; 481 if (vi.Kills[0] != mi) 482 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 483 else 484 killIdx = defIndex+1; 485 486 // If the kill happens after the definition, we have an intra-block 487 // live range. 488 if (killIdx > defIndex) { 489 assert(vi.AliveBlocks.none() && 490 "Shouldn't be alive across any blocks!"); 491 LiveRange LR(defIndex, killIdx, ValNum); 492 interval.addRange(LR); 493 DOUT << " +" << LR << "\n"; 494 return; 495 } 496 } 497 498 // The other case we handle is when a virtual register lives to the end 499 // of the defining block, potentially live across some blocks, then is 500 // live into some number of blocks, but gets killed. Start by adding a 501 // range that goes from this definition to the end of the defining block. 502 LiveRange NewLR(defIndex, 503 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 504 ValNum); 505 DOUT << " +" << NewLR; 506 interval.addRange(NewLR); 507 508 // Iterate over all of the blocks that the variable is completely 509 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 510 // live interval. 511 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 512 if (vi.AliveBlocks[i]) { 513 MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 514 if (!MBB->empty()) { 515 LiveRange LR(getMBBStartIdx(i), 516 getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 517 ValNum); 518 interval.addRange(LR); 519 DOUT << " +" << LR; 520 } 521 } 522 } 523 524 // Finally, this virtual register is live from the start of any killing 525 // block to the 'use' slot of the killing instruction. 526 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 527 MachineInstr *Kill = vi.Kills[i]; 528 LiveRange LR(getMBBStartIdx(Kill->getParent()), 529 getUseIndex(getInstructionIndex(Kill))+1, 530 ValNum); 531 interval.addRange(LR); 532 DOUT << " +" << LR; 533 } 534 535 } else { 536 // Can no longer safely assume definition is rematerializable. 537 interval.remat = NULL; 538 539 // If this is the second time we see a virtual register definition, it 540 // must be due to phi elimination or two addr elimination. If this is 541 // the result of two address elimination, then the vreg is one of the 542 // def-and-use register operand. 543 if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) { 544 // If this is a two-address definition, then we have already processed 545 // the live range. The only problem is that we didn't realize there 546 // are actually two values in the live interval. Because of this we 547 // need to take the LiveRegion that defines this register and split it 548 // into two values. 549 unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst)); 550 unsigned RedefIndex = getDefIndex(MIIdx); 551 552 // Delete the initial value, which should be short and continuous, 553 // because the 2-addr copy must be in the same MBB as the redef. 554 interval.removeRange(DefIndex, RedefIndex); 555 556 // Two-address vregs should always only be redefined once. This means 557 // that at this point, there should be exactly one value number in it. 558 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 559 560 // The new value number (#1) is defined by the instruction we claimed 561 // defined value #0. 562 unsigned ValNo = interval.getNextValue(0, 0); 563 interval.setValueNumberInfo(1, interval.getValNumInfo(0)); 564 565 // Value#0 is now defined by the 2-addr instruction. 566 interval.setValueNumberInfo(0, std::make_pair(~0U, 0U)); 567 568 // Add the new live interval which replaces the range for the input copy. 569 LiveRange LR(DefIndex, RedefIndex, ValNo); 570 DOUT << " replace range with " << LR; 571 interval.addRange(LR); 572 573 // If this redefinition is dead, we need to add a dummy unit live 574 // range covering the def slot. 575 if (lv_->RegisterDefIsDead(mi, interval.reg)) 576 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0)); 577 578 DOUT << " RESULT: "; 579 interval.print(DOUT, mri_); 580 581 } else { 582 // Otherwise, this must be because of phi elimination. If this is the 583 // first redefinition of the vreg that we have seen, go back and change 584 // the live range in the PHI block to be a different value number. 585 if (interval.containsOneValue()) { 586 assert(vi.Kills.size() == 1 && 587 "PHI elimination vreg should have one kill, the PHI itself!"); 588 589 // Remove the old range that we now know has an incorrect number. 590 MachineInstr *Killer = vi.Kills[0]; 591 unsigned Start = getMBBStartIdx(Killer->getParent()); 592 unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 593 DOUT << " Removing [" << Start << "," << End << "] from: "; 594 interval.print(DOUT, mri_); DOUT << "\n"; 595 interval.removeRange(Start, End); 596 DOUT << " RESULT: "; interval.print(DOUT, mri_); 597 598 // Replace the interval with one of a NEW value number. Note that this 599 // value number isn't actually defined by an instruction, weird huh? :) 600 LiveRange LR(Start, End, interval.getNextValue(~0U, 0)); 601 DOUT << " replace range with " << LR; 602 interval.addRange(LR); 603 DOUT << " RESULT: "; interval.print(DOUT, mri_); 604 } 605 606 // In the case of PHI elimination, each variable definition is only 607 // live until the end of the block. We've already taken care of the 608 // rest of the live range. 609 unsigned defIndex = getDefIndex(MIIdx); 610 611 unsigned ValNum; 612 unsigned SrcReg, DstReg; 613 if (!tii_->isMoveInstr(*mi, SrcReg, DstReg)) 614 ValNum = interval.getNextValue(~0U, 0); 615 else 616 ValNum = interval.getNextValue(defIndex, SrcReg); 617 618 LiveRange LR(defIndex, 619 getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum); 620 interval.addRange(LR); 621 DOUT << " +" << LR; 622 } 623 } 624 625 DOUT << '\n'; 626} 627 628void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 629 MachineBasicBlock::iterator mi, 630 unsigned MIIdx, 631 LiveInterval &interval, 632 unsigned SrcReg) { 633 // A physical register cannot be live across basic block, so its 634 // lifetime must end somewhere in its defining basic block. 635 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 636 637 unsigned baseIndex = MIIdx; 638 unsigned start = getDefIndex(baseIndex); 639 unsigned end = start; 640 641 // If it is not used after definition, it is considered dead at 642 // the instruction defining it. Hence its interval is: 643 // [defSlot(def), defSlot(def)+1) 644 if (lv_->RegisterDefIsDead(mi, interval.reg)) { 645 DOUT << " dead"; 646 end = getDefIndex(start) + 1; 647 goto exit; 648 } 649 650 // If it is not dead on definition, it must be killed by a 651 // subsequent instruction. Hence its interval is: 652 // [defSlot(def), useSlot(kill)+1) 653 while (++mi != MBB->end()) { 654 baseIndex += InstrSlots::NUM; 655 if (lv_->KillsRegister(mi, interval.reg)) { 656 DOUT << " killed"; 657 end = getUseIndex(baseIndex) + 1; 658 goto exit; 659 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 660 // Another instruction redefines the register before it is ever read. 661 // Then the register is essentially dead at the instruction that defines 662 // it. Hence its interval is: 663 // [defSlot(def), defSlot(def)+1) 664 DOUT << " dead"; 665 end = getDefIndex(start) + 1; 666 goto exit; 667 } 668 } 669 670 // The only case we should have a dead physreg here without a killing or 671 // instruction where we know it's dead is if it is live-in to the function 672 // and never used. 673 assert(!SrcReg && "physreg was not killed in defining block!"); 674 end = getDefIndex(start) + 1; // It's dead. 675 676exit: 677 assert(start < end && "did not find end of interval?"); 678 679 // Already exists? Extend old live interval. 680 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 681 unsigned Id = (OldLR != interval.end()) 682 ? OldLR->ValId 683 : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg); 684 LiveRange LR(start, end, Id); 685 interval.addRange(LR); 686 DOUT << " +" << LR << '\n'; 687} 688 689void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 690 MachineBasicBlock::iterator MI, 691 unsigned MIIdx, 692 unsigned reg) { 693 if (MRegisterInfo::isVirtualRegister(reg)) 694 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 695 else if (allocatableRegs_[reg]) { 696 unsigned SrcReg, DstReg; 697 if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) 698 SrcReg = 0; 699 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg); 700 // Def of a register also defines its sub-registers. 701 for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS) 702 // Avoid processing some defs more than once. 703 if (!MI->findRegisterDefOperand(*AS)) 704 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 705 } 706} 707 708void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 709 unsigned MIIdx, 710 LiveInterval &interval, bool isAlias) { 711 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 712 713 // Look for kills, if it reaches a def before it's killed, then it shouldn't 714 // be considered a livein. 715 MachineBasicBlock::iterator mi = MBB->begin(); 716 unsigned baseIndex = MIIdx; 717 unsigned start = baseIndex; 718 unsigned end = start; 719 while (mi != MBB->end()) { 720 if (lv_->KillsRegister(mi, interval.reg)) { 721 DOUT << " killed"; 722 end = getUseIndex(baseIndex) + 1; 723 goto exit; 724 } else if (lv_->ModifiesRegister(mi, interval.reg)) { 725 // Another instruction redefines the register before it is ever read. 726 // Then the register is essentially dead at the instruction that defines 727 // it. Hence its interval is: 728 // [defSlot(def), defSlot(def)+1) 729 DOUT << " dead"; 730 end = getDefIndex(start) + 1; 731 goto exit; 732 } 733 734 baseIndex += InstrSlots::NUM; 735 ++mi; 736 } 737 738exit: 739 // Alias of a live-in register might not be used at all. 740 if (isAlias && end == 0) { 741 DOUT << " dead"; 742 end = getDefIndex(start) + 1; 743 } 744 745 assert(start < end && "did not find end of interval?"); 746 747 LiveRange LR(start, end, interval.getNextValue(~0U, 0)); 748 DOUT << " +" << LR << '\n'; 749 interval.addRange(LR); 750} 751 752/// computeIntervals - computes the live intervals for virtual 753/// registers. for some ordering of the machine instructions [1,N] a 754/// live interval is an interval [i, j) where 1 <= i <= j < N for 755/// which a variable is live 756void LiveIntervals::computeIntervals() { 757 DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 758 << "********** Function: " 759 << ((Value*)mf_->getFunction())->getName() << '\n'; 760 // Track the index of the current machine instr. 761 unsigned MIIndex = 0; 762 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 763 MBBI != E; ++MBBI) { 764 MachineBasicBlock *MBB = MBBI; 765 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 766 767 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 768 769 if (MBB->livein_begin() != MBB->livein_end()) { 770 // Create intervals for live-ins to this BB first. 771 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 772 LE = MBB->livein_end(); LI != LE; ++LI) { 773 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 774 // Multiple live-ins can alias the same register. 775 for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS) 776 if (!hasInterval(*AS)) 777 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true); 778 } 779 } 780 781 for (; MI != miEnd; ++MI) { 782 DOUT << MIIndex << "\t" << *MI; 783 784 // Handle defs. 785 for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 786 MachineOperand &MO = MI->getOperand(i); 787 // handle register defs - build intervals 788 if (MO.isRegister() && MO.getReg() && MO.isDef()) 789 handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 790 } 791 792 MIIndex += InstrSlots::NUM; 793 } 794 } 795} 796 797/// AdjustCopiesBackFrom - We found a non-trivially-coallescable copy with IntA 798/// being the source and IntB being the dest, thus this defines a value number 799/// in IntB. If the source value number (in IntA) is defined by a copy from B, 800/// see if we can merge these two pieces of B into a single value number, 801/// eliminating a copy. For example: 802/// 803/// A3 = B0 804/// ... 805/// B1 = A3 <- this copy 806/// 807/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 808/// value number to be replaced with B0 (which simplifies the B liveinterval). 809/// 810/// This returns true if an interval was modified. 811/// 812bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, 813 MachineInstr *CopyMI) { 814 unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI)); 815 816 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 817 // the example above. 818 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 819 unsigned BValNo = BLR->ValId; 820 821 // Get the location that B is defined at. Two options: either this value has 822 // an unknown definition point or it is defined at CopyIdx. If unknown, we 823 // can't process it. 824 unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo); 825 if (BValNoDefIdx == ~0U) return false; 826 assert(BValNoDefIdx == CopyIdx && 827 "Copy doesn't define the value?"); 828 829 // AValNo is the value number in A that defines the copy, A0 in the example. 830 LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1); 831 unsigned AValNo = AValLR->ValId; 832 833 // If AValNo is defined as a copy from IntB, we can potentially process this. 834 835 // Get the instruction that defines this value number. 836 unsigned SrcReg = IntA.getSrcRegForValNum(AValNo); 837 if (!SrcReg) return false; // Not defined by a copy. 838 839 // If the value number is not defined by a copy instruction, ignore it. 840 841 // If the source register comes from an interval other than IntB, we can't 842 // handle this. 843 if (rep(SrcReg) != IntB.reg) return false; 844 845 // Get the LiveRange in IntB that this value number starts with. 846 unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo); 847 LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1); 848 849 // Make sure that the end of the live range is inside the same block as 850 // CopyMI. 851 MachineInstr *ValLREndInst = getInstructionFromIndex(ValLR->end-1); 852 if (!ValLREndInst || 853 ValLREndInst->getParent() != CopyMI->getParent()) return false; 854 855 // Okay, we now know that ValLR ends in the same block that the CopyMI 856 // live-range starts. If there are no intervening live ranges between them in 857 // IntB, we can merge them. 858 if (ValLR+1 != BLR) return false; 859 860 DOUT << "\nExtending: "; IntB.print(DOUT, mri_); 861 862 // We are about to delete CopyMI, so need to remove it as the 'instruction 863 // that defines this value #'. 864 IntB.setValueNumberInfo(BValNo, std::make_pair(~0U, 0)); 865 866 // Okay, we can merge them. We need to insert a new liverange: 867 // [ValLR.end, BLR.begin) of either value number, then we merge the 868 // two value numbers. 869 unsigned FillerStart = ValLR->end, FillerEnd = BLR->start; 870 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 871 872 // If the IntB live range is assigned to a physical register, and if that 873 // physreg has aliases, 874 if (MRegisterInfo::isPhysicalRegister(IntB.reg)) { 875 // Update the liveintervals of sub-registers. 876 for (const unsigned *AS = mri_->getSubRegisters(IntB.reg); *AS; ++AS) { 877 LiveInterval &AliasLI = getInterval(*AS); 878 AliasLI.addRange(LiveRange(FillerStart, FillerEnd, 879 AliasLI.getNextValue(~0U, 0))); 880 } 881 } 882 883 // Okay, merge "B1" into the same value number as "B0". 884 if (BValNo != ValLR->ValId) 885 IntB.MergeValueNumberInto(BValNo, ValLR->ValId); 886 DOUT << " result = "; IntB.print(DOUT, mri_); 887 DOUT << "\n"; 888 889 // If the source instruction was killing the source register before the 890 // merge, unset the isKill marker given the live range has been extended. 891 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 892 if (UIdx != -1) 893 ValLREndInst->getOperand(UIdx).unsetIsKill(); 894 895 // Finally, delete the copy instruction. 896 RemoveMachineInstrFromMaps(CopyMI); 897 CopyMI->eraseFromParent(); 898 ++numPeep; 899 return true; 900} 901 902 903/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 904/// which are the src/dst of the copy instruction CopyMI. This returns true 905/// if the copy was successfully coallesced away, or if it is never possible 906/// to coallesce this copy, due to register constraints. It returns 907/// false if it is not currently possible to coallesce this interval, but 908/// it may be possible if other things get coallesced. 909bool LiveIntervals::JoinCopy(MachineInstr *CopyMI, 910 unsigned SrcReg, unsigned DstReg, bool PhysOnly) { 911 DOUT << getInstructionIndex(CopyMI) << '\t' << *CopyMI; 912 913 // Get representative registers. 914 unsigned repSrcReg = rep(SrcReg); 915 unsigned repDstReg = rep(DstReg); 916 917 // If they are already joined we continue. 918 if (repSrcReg == repDstReg) { 919 DOUT << "\tCopy already coallesced.\n"; 920 return true; // Not coallescable. 921 } 922 923 bool SrcIsPhys = MRegisterInfo::isPhysicalRegister(repSrcReg); 924 bool DstIsPhys = MRegisterInfo::isPhysicalRegister(repDstReg); 925 if (PhysOnly && !SrcIsPhys && !DstIsPhys) 926 // Only joining physical registers with virtual registers in this round. 927 return true; 928 929 // If they are both physical registers, we cannot join them. 930 if (SrcIsPhys && DstIsPhys) { 931 DOUT << "\tCan not coallesce physregs.\n"; 932 return true; // Not coallescable. 933 } 934 935 // We only join virtual registers with allocatable physical registers. 936 if (SrcIsPhys && !allocatableRegs_[repSrcReg]) { 937 DOUT << "\tSrc reg is unallocatable physreg.\n"; 938 return true; // Not coallescable. 939 } 940 if (DstIsPhys && !allocatableRegs_[repDstReg]) { 941 DOUT << "\tDst reg is unallocatable physreg.\n"; 942 return true; // Not coallescable. 943 } 944 945 // If they are not of the same register class, we cannot join them. 946 if (differingRegisterClasses(repSrcReg, repDstReg)) { 947 DOUT << "\tSrc/Dest are different register classes.\n"; 948 return true; // Not coallescable. 949 } 950 951 LiveInterval &SrcInt = getInterval(repSrcReg); 952 LiveInterval &DstInt = getInterval(repDstReg); 953 assert(SrcInt.reg == repSrcReg && DstInt.reg == repDstReg && 954 "Register mapping is horribly broken!"); 955 956 DOUT << "\t\tInspecting "; SrcInt.print(DOUT, mri_); 957 DOUT << " and "; DstInt.print(DOUT, mri_); 958 DOUT << ": "; 959 960 // Check if it is necessary to propagate "isDead" property before intervals 961 // are joined. 962 MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg); 963 bool isDead = mopd->isDead(); 964 bool isShorten = false; 965 unsigned SrcStart = 0, RemoveStart = 0; 966 unsigned SrcEnd = 0, RemoveEnd = 0; 967 if (isDead) { 968 unsigned CopyIdx = getInstructionIndex(CopyMI); 969 LiveInterval::iterator SrcLR = 970 SrcInt.FindLiveRangeContaining(getUseIndex(CopyIdx)); 971 RemoveStart = SrcStart = SrcLR->start; 972 RemoveEnd = SrcEnd = SrcLR->end; 973 // The instruction which defines the src is only truly dead if there are 974 // no intermediate uses and there isn't a use beyond the copy. 975 // FIXME: find the last use, mark is kill and shorten the live range. 976 if (SrcEnd > getDefIndex(CopyIdx)) { 977 isDead = false; 978 } else { 979 MachineOperand *MOU; 980 MachineInstr *LastUse= lastRegisterUse(repSrcReg, SrcStart, CopyIdx, MOU); 981 if (LastUse) { 982 // Shorten the liveinterval to the end of last use. 983 MOU->setIsKill(); 984 isDead = false; 985 isShorten = true; 986 RemoveStart = getDefIndex(getInstructionIndex(LastUse)); 987 RemoveEnd = SrcEnd; 988 } else { 989 MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); 990 if (SrcMI) { 991 MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); 992 if (mops) 993 // A dead def should have a single cycle interval. 994 ++RemoveStart; 995 } 996 } 997 } 998 } 999 1000 // We need to be careful about coalescing a source physical register with a 1001 // virtual register. Once the coalescing is done, it cannot be broken and 1002 // these are not spillable! If the destination interval uses are far away, 1003 // think twice about coalescing them! 1004 if (!mopd->isDead() && (SrcIsPhys || DstIsPhys)) { 1005 LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; 1006 unsigned JoinVReg = SrcIsPhys ? repDstReg : repSrcReg; 1007 unsigned JoinPReg = SrcIsPhys ? repSrcReg : repDstReg; 1008 const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(JoinVReg); 1009 unsigned Threshold = allocatableRCRegs_[RC].count(); 1010 1011 // If the virtual register live interval is long has it has low use desity, 1012 // do not join them, instead mark the physical register as its allocation 1013 // preference. 1014 unsigned Length = JoinVInt.getSize() / InstrSlots::NUM; 1015 LiveVariables::VarInfo &vi = lv_->getVarInfo(JoinVReg); 1016 if (Length > Threshold && 1017 (((float)vi.NumUses / Length) < (1.0 / Threshold))) { 1018 JoinVInt.preference = JoinPReg; 1019 ++numAborts; 1020 DOUT << "\tMay tie down a physical register, abort!\n"; 1021 return false; 1022 } 1023 } 1024 1025 // Okay, attempt to join these two intervals. On failure, this returns false. 1026 // Otherwise, if one of the intervals being joined is a physreg, this method 1027 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1028 // been modified, so we can use this information below to update aliases. 1029 if (JoinIntervals(DstInt, SrcInt)) { 1030 if (isDead) { 1031 // Result of the copy is dead. Propagate this property. 1032 if (SrcStart == 0) { 1033 assert(MRegisterInfo::isPhysicalRegister(repSrcReg) && 1034 "Live-in must be a physical register!"); 1035 // Live-in to the function but dead. Remove it from entry live-in set. 1036 // JoinIntervals may end up swapping the two intervals. 1037 mf_->begin()->removeLiveIn(repSrcReg); 1038 } else { 1039 MachineInstr *SrcMI = getInstructionFromIndex(SrcStart); 1040 if (SrcMI) { 1041 MachineOperand *mops = findDefOperand(SrcMI, repSrcReg); 1042 if (mops) 1043 mops->setIsDead(); 1044 } 1045 } 1046 } 1047 1048 if (isShorten || isDead) { 1049 // Shorten the live interval. 1050 LiveInterval &LiveInInt = (repSrcReg == DstInt.reg) ? DstInt : SrcInt; 1051 LiveInInt.removeRange(RemoveStart, RemoveEnd); 1052 } 1053 } else { 1054 // Coallescing failed. 1055 1056 // If we can eliminate the copy without merging the live ranges, do so now. 1057 if (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI)) 1058 return true; 1059 1060 // Otherwise, we are unable to join the intervals. 1061 DOUT << "Interference!\n"; 1062 return false; 1063 } 1064 1065 bool Swapped = repSrcReg == DstInt.reg; 1066 if (Swapped) 1067 std::swap(repSrcReg, repDstReg); 1068 assert(MRegisterInfo::isVirtualRegister(repSrcReg) && 1069 "LiveInterval::join didn't work right!"); 1070 1071 // If we're about to merge live ranges into a physical register live range, 1072 // we have to update any aliased register's live ranges to indicate that they 1073 // have clobbered values for this range. 1074 if (MRegisterInfo::isPhysicalRegister(repDstReg)) { 1075 // Update the liveintervals of sub-registers. 1076 for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS) 1077 getInterval(*AS).MergeInClobberRanges(SrcInt); 1078 } else { 1079 // Merge use info if the destination is a virtual register. 1080 LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg); 1081 LiveVariables::VarInfo& sVI = lv_->getVarInfo(repSrcReg); 1082 dVI.NumUses += sVI.NumUses; 1083 } 1084 1085 DOUT << "\n\t\tJoined. Result = "; DstInt.print(DOUT, mri_); 1086 DOUT << "\n"; 1087 1088 // Remember these liveintervals have been joined. 1089 JoinedLIs.set(repSrcReg - MRegisterInfo::FirstVirtualRegister); 1090 if (MRegisterInfo::isVirtualRegister(repDstReg)) 1091 JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister); 1092 1093 // If the intervals were swapped by Join, swap them back so that the register 1094 // mapping (in the r2i map) is correct. 1095 if (Swapped) SrcInt.swap(DstInt); 1096 removeInterval(repSrcReg); 1097 r2rMap_[repSrcReg] = repDstReg; 1098 1099 // Finally, delete the copy instruction. 1100 RemoveMachineInstrFromMaps(CopyMI); 1101 CopyMI->eraseFromParent(); 1102 ++numPeep; 1103 ++numJoins; 1104 return true; 1105} 1106 1107/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1108/// compute what the resultant value numbers for each value in the input two 1109/// ranges will be. This is complicated by copies between the two which can 1110/// and will commonly cause multiple value numbers to be merged into one. 1111/// 1112/// VN is the value number that we're trying to resolve. InstDefiningValue 1113/// keeps track of the new InstDefiningValue assignment for the result 1114/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1115/// whether a value in this or other is a copy from the opposite set. 1116/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1117/// already been assigned. 1118/// 1119/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1120/// contains the value number the copy is from. 1121/// 1122static unsigned ComputeUltimateVN(unsigned VN, 1123 SmallVector<std::pair<unsigned, 1124 unsigned>, 16> &ValueNumberInfo, 1125 SmallVector<int, 16> &ThisFromOther, 1126 SmallVector<int, 16> &OtherFromThis, 1127 SmallVector<int, 16> &ThisValNoAssignments, 1128 SmallVector<int, 16> &OtherValNoAssignments, 1129 LiveInterval &ThisLI, LiveInterval &OtherLI) { 1130 // If the VN has already been computed, just return it. 1131 if (ThisValNoAssignments[VN] >= 0) 1132 return ThisValNoAssignments[VN]; 1133// assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); 1134 1135 // If this val is not a copy from the other val, then it must be a new value 1136 // number in the destination. 1137 int OtherValNo = ThisFromOther[VN]; 1138 if (OtherValNo == -1) { 1139 ValueNumberInfo.push_back(ThisLI.getValNumInfo(VN)); 1140 return ThisValNoAssignments[VN] = ValueNumberInfo.size()-1; 1141 } 1142 1143 // Otherwise, this *is* a copy from the RHS. If the other side has already 1144 // been computed, return it. 1145 if (OtherValNoAssignments[OtherValNo] >= 0) 1146 return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo]; 1147 1148 // Mark this value number as currently being computed, then ask what the 1149 // ultimate value # of the other value is. 1150 ThisValNoAssignments[VN] = -2; 1151 unsigned UltimateVN = 1152 ComputeUltimateVN(OtherValNo, ValueNumberInfo, 1153 OtherFromThis, ThisFromOther, 1154 OtherValNoAssignments, ThisValNoAssignments, 1155 OtherLI, ThisLI); 1156 return ThisValNoAssignments[VN] = UltimateVN; 1157} 1158 1159static bool InVector(unsigned Val, const SmallVector<unsigned, 8> &V) { 1160 return std::find(V.begin(), V.end(), Val) != V.end(); 1161} 1162 1163/// SimpleJoin - Attempt to joint the specified interval into this one. The 1164/// caller of this method must guarantee that the RHS only contains a single 1165/// value number and that the RHS is not defined by a copy from this 1166/// interval. This returns false if the intervals are not joinable, or it 1167/// joins them and returns true. 1168bool LiveIntervals::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS) { 1169 assert(RHS.containsOneValue()); 1170 1171 // Some number (potentially more than one) value numbers in the current 1172 // interval may be defined as copies from the RHS. Scan the overlapping 1173 // portions of the LHS and RHS, keeping track of this and looking for 1174 // overlapping live ranges that are NOT defined as copies. If these exist, we 1175 // cannot coallesce. 1176 1177 LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end(); 1178 LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end(); 1179 1180 if (LHSIt->start < RHSIt->start) { 1181 LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start); 1182 if (LHSIt != LHS.begin()) --LHSIt; 1183 } else if (RHSIt->start < LHSIt->start) { 1184 RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start); 1185 if (RHSIt != RHS.begin()) --RHSIt; 1186 } 1187 1188 SmallVector<unsigned, 8> EliminatedLHSVals; 1189 1190 while (1) { 1191 // Determine if these live intervals overlap. 1192 bool Overlaps = false; 1193 if (LHSIt->start <= RHSIt->start) 1194 Overlaps = LHSIt->end > RHSIt->start; 1195 else 1196 Overlaps = RHSIt->end > LHSIt->start; 1197 1198 // If the live intervals overlap, there are two interesting cases: if the 1199 // LHS interval is defined by a copy from the RHS, it's ok and we record 1200 // that the LHS value # is the same as the RHS. If it's not, then we cannot 1201 // coallesce these live ranges and we bail out. 1202 if (Overlaps) { 1203 // If we haven't already recorded that this value # is safe, check it. 1204 if (!InVector(LHSIt->ValId, EliminatedLHSVals)) { 1205 // Copy from the RHS? 1206 unsigned SrcReg = LHS.getSrcRegForValNum(LHSIt->ValId); 1207 if (rep(SrcReg) != RHS.reg) 1208 return false; // Nope, bail out. 1209 1210 EliminatedLHSVals.push_back(LHSIt->ValId); 1211 } 1212 1213 // We know this entire LHS live range is okay, so skip it now. 1214 if (++LHSIt == LHSEnd) break; 1215 continue; 1216 } 1217 1218 if (LHSIt->end < RHSIt->end) { 1219 if (++LHSIt == LHSEnd) break; 1220 } else { 1221 // One interesting case to check here. It's possible that we have 1222 // something like "X3 = Y" which defines a new value number in the LHS, 1223 // and is the last use of this liverange of the RHS. In this case, we 1224 // want to notice this copy (so that it gets coallesced away) even though 1225 // the live ranges don't actually overlap. 1226 if (LHSIt->start == RHSIt->end) { 1227 if (InVector(LHSIt->ValId, EliminatedLHSVals)) { 1228 // We already know that this value number is going to be merged in 1229 // if coallescing succeeds. Just skip the liverange. 1230 if (++LHSIt == LHSEnd) break; 1231 } else { 1232 // Otherwise, if this is a copy from the RHS, mark it as being merged 1233 // in. 1234 if (rep(LHS.getSrcRegForValNum(LHSIt->ValId)) == RHS.reg) { 1235 EliminatedLHSVals.push_back(LHSIt->ValId); 1236 1237 // We know this entire LHS live range is okay, so skip it now. 1238 if (++LHSIt == LHSEnd) break; 1239 } 1240 } 1241 } 1242 1243 if (++RHSIt == RHSEnd) break; 1244 } 1245 } 1246 1247 // If we got here, we know that the coallescing will be successful and that 1248 // the value numbers in EliminatedLHSVals will all be merged together. Since 1249 // the most common case is that EliminatedLHSVals has a single number, we 1250 // optimize for it: if there is more than one value, we merge them all into 1251 // the lowest numbered one, then handle the interval as if we were merging 1252 // with one value number. 1253 unsigned LHSValNo; 1254 if (EliminatedLHSVals.size() > 1) { 1255 // Loop through all the equal value numbers merging them into the smallest 1256 // one. 1257 unsigned Smallest = EliminatedLHSVals[0]; 1258 for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { 1259 if (EliminatedLHSVals[i] < Smallest) { 1260 // Merge the current notion of the smallest into the smaller one. 1261 LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); 1262 Smallest = EliminatedLHSVals[i]; 1263 } else { 1264 // Merge into the smallest. 1265 LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); 1266 } 1267 } 1268 LHSValNo = Smallest; 1269 } else { 1270 assert(!EliminatedLHSVals.empty() && "No copies from the RHS?"); 1271 LHSValNo = EliminatedLHSVals[0]; 1272 } 1273 1274 // Okay, now that there is a single LHS value number that we're merging the 1275 // RHS into, update the value number info for the LHS to indicate that the 1276 // value number is defined where the RHS value number was. 1277 LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0)); 1278 1279 // Okay, the final step is to loop over the RHS live intervals, adding them to 1280 // the LHS. 1281 LHS.MergeRangesInAsValue(RHS, LHSValNo); 1282 LHS.weight += RHS.weight; 1283 if (RHS.preference && !LHS.preference) 1284 LHS.preference = RHS.preference; 1285 1286 return true; 1287} 1288 1289/// JoinIntervals - Attempt to join these two intervals. On failure, this 1290/// returns false. Otherwise, if one of the intervals being joined is a 1291/// physreg, this method always canonicalizes LHS to be it. The output 1292/// "RHS" will not have been modified, so we can use this information 1293/// below to update aliases. 1294bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) { 1295 // Compute the final value assignment, assuming that the live ranges can be 1296 // coallesced. 1297 SmallVector<int, 16> LHSValNoAssignments; 1298 SmallVector<int, 16> RHSValNoAssignments; 1299 SmallVector<std::pair<unsigned,unsigned>, 16> ValueNumberInfo; 1300 1301 // If a live interval is a physical register, conservatively check if any 1302 // of its sub-registers is overlapping the live interval of the virtual 1303 // register. If so, do not coalesce. 1304 if (MRegisterInfo::isPhysicalRegister(LHS.reg) && 1305 *mri_->getSubRegisters(LHS.reg)) { 1306 for (const unsigned* SR = mri_->getSubRegisters(LHS.reg); *SR; ++SR) 1307 if (hasInterval(*SR) && RHS.overlaps(getInterval(*SR))) { 1308 DOUT << "Interfere with sub-register "; 1309 DEBUG(getInterval(*SR).print(DOUT, mri_)); 1310 return false; 1311 } 1312 } else if (MRegisterInfo::isPhysicalRegister(RHS.reg) && 1313 *mri_->getSubRegisters(RHS.reg)) { 1314 for (const unsigned* SR = mri_->getSubRegisters(RHS.reg); *SR; ++SR) 1315 if (hasInterval(*SR) && LHS.overlaps(getInterval(*SR))) { 1316 DOUT << "Interfere with sub-register "; 1317 DEBUG(getInterval(*SR).print(DOUT, mri_)); 1318 return false; 1319 } 1320 } 1321 1322 // Compute ultimate value numbers for the LHS and RHS values. 1323 if (RHS.containsOneValue()) { 1324 // Copies from a liveinterval with a single value are simple to handle and 1325 // very common, handle the special case here. This is important, because 1326 // often RHS is small and LHS is large (e.g. a physreg). 1327 1328 // Find out if the RHS is defined as a copy from some value in the LHS. 1329 int RHSValID = -1; 1330 std::pair<unsigned,unsigned> RHSValNoInfo; 1331 unsigned RHSSrcReg = RHS.getSrcRegForValNum(0); 1332 if ((RHSSrcReg == 0 || rep(RHSSrcReg) != LHS.reg)) { 1333 // If RHS is not defined as a copy from the LHS, we can use simpler and 1334 // faster checks to see if the live ranges are coallescable. This joiner 1335 // can't swap the LHS/RHS intervals though. 1336 if (!MRegisterInfo::isPhysicalRegister(RHS.reg)) { 1337 return SimpleJoin(LHS, RHS); 1338 } else { 1339 RHSValNoInfo = RHS.getValNumInfo(0); 1340 } 1341 } else { 1342 // It was defined as a copy from the LHS, find out what value # it is. 1343 unsigned ValInst = RHS.getInstForValNum(0); 1344 RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId; 1345 RHSValNoInfo = LHS.getValNumInfo(RHSValID); 1346 } 1347 1348 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1349 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1350 ValueNumberInfo.resize(LHS.getNumValNums()); 1351 1352 // Okay, *all* of the values in LHS that are defined as a copy from RHS 1353 // should now get updated. 1354 for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 1355 if (unsigned LHSSrcReg = LHS.getSrcRegForValNum(VN)) { 1356 if (rep(LHSSrcReg) != RHS.reg) { 1357 // If this is not a copy from the RHS, its value number will be 1358 // unmodified by the coallescing. 1359 ValueNumberInfo[VN] = LHS.getValNumInfo(VN); 1360 LHSValNoAssignments[VN] = VN; 1361 } else if (RHSValID == -1) { 1362 // Otherwise, it is a copy from the RHS, and we don't already have a 1363 // value# for it. Keep the current value number, but remember it. 1364 LHSValNoAssignments[VN] = RHSValID = VN; 1365 ValueNumberInfo[VN] = RHSValNoInfo; 1366 } else { 1367 // Otherwise, use the specified value #. 1368 LHSValNoAssignments[VN] = RHSValID; 1369 if (VN != (unsigned)RHSValID) 1370 ValueNumberInfo[VN].first = ~1U; 1371 else 1372 ValueNumberInfo[VN] = RHSValNoInfo; 1373 } 1374 } else { 1375 ValueNumberInfo[VN] = LHS.getValNumInfo(VN); 1376 LHSValNoAssignments[VN] = VN; 1377 } 1378 } 1379 1380 assert(RHSValID != -1 && "Didn't find value #?"); 1381 RHSValNoAssignments[0] = RHSValID; 1382 1383 } else { 1384 // Loop over the value numbers of the LHS, seeing if any are defined from 1385 // the RHS. 1386 SmallVector<int, 16> LHSValsDefinedFromRHS; 1387 LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1); 1388 for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 1389 unsigned ValSrcReg = LHS.getSrcRegForValNum(VN); 1390 if (ValSrcReg == 0) // Src not defined by a copy? 1391 continue; 1392 1393 // DstReg is known to be a register in the LHS interval. If the src is 1394 // from the RHS interval, we can use its value #. 1395 if (rep(ValSrcReg) != RHS.reg) 1396 continue; 1397 1398 // Figure out the value # from the RHS. 1399 unsigned ValInst = LHS.getInstForValNum(VN); 1400 LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId; 1401 } 1402 1403 // Loop over the value numbers of the RHS, seeing if any are defined from 1404 // the LHS. 1405 SmallVector<int, 16> RHSValsDefinedFromLHS; 1406 RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1); 1407 for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { 1408 unsigned ValSrcReg = RHS.getSrcRegForValNum(VN); 1409 if (ValSrcReg == 0) // Src not defined by a copy? 1410 continue; 1411 1412 // DstReg is known to be a register in the RHS interval. If the src is 1413 // from the LHS interval, we can use its value #. 1414 if (rep(ValSrcReg) != LHS.reg) 1415 continue; 1416 1417 // Figure out the value # from the LHS. 1418 unsigned ValInst = RHS.getInstForValNum(VN); 1419 RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId; 1420 } 1421 1422 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1423 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1424 ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1425 1426 for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) { 1427 if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~2U) 1428 continue; 1429 ComputeUltimateVN(VN, ValueNumberInfo, 1430 LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1431 LHSValNoAssignments, RHSValNoAssignments, LHS, RHS); 1432 } 1433 for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) { 1434 if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~2U) 1435 continue; 1436 // If this value number isn't a copy from the LHS, it's a new number. 1437 if (RHSValsDefinedFromLHS[VN] == -1) { 1438 ValueNumberInfo.push_back(RHS.getValNumInfo(VN)); 1439 RHSValNoAssignments[VN] = ValueNumberInfo.size()-1; 1440 continue; 1441 } 1442 1443 ComputeUltimateVN(VN, ValueNumberInfo, 1444 RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1445 RHSValNoAssignments, LHSValNoAssignments, RHS, LHS); 1446 } 1447 } 1448 1449 // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1450 // interval lists to see if these intervals are coallescable. 1451 LiveInterval::const_iterator I = LHS.begin(); 1452 LiveInterval::const_iterator IE = LHS.end(); 1453 LiveInterval::const_iterator J = RHS.begin(); 1454 LiveInterval::const_iterator JE = RHS.end(); 1455 1456 // Skip ahead until the first place of potential sharing. 1457 if (I->start < J->start) { 1458 I = std::upper_bound(I, IE, J->start); 1459 if (I != LHS.begin()) --I; 1460 } else if (J->start < I->start) { 1461 J = std::upper_bound(J, JE, I->start); 1462 if (J != RHS.begin()) --J; 1463 } 1464 1465 while (1) { 1466 // Determine if these two live ranges overlap. 1467 bool Overlaps; 1468 if (I->start < J->start) { 1469 Overlaps = I->end > J->start; 1470 } else { 1471 Overlaps = J->end > I->start; 1472 } 1473 1474 // If so, check value # info to determine if they are really different. 1475 if (Overlaps) { 1476 // If the live range overlap will map to the same value number in the 1477 // result liverange, we can still coallesce them. If not, we can't. 1478 if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId]) 1479 return false; 1480 } 1481 1482 if (I->end < J->end) { 1483 ++I; 1484 if (I == IE) break; 1485 } else { 1486 ++J; 1487 if (J == JE) break; 1488 } 1489 } 1490 1491 // If we get here, we know that we can coallesce the live ranges. Ask the 1492 // intervals to coallesce themselves now. 1493 LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], 1494 ValueNumberInfo); 1495 return true; 1496} 1497 1498 1499namespace { 1500 // DepthMBBCompare - Comparison predicate that sort first based on the loop 1501 // depth of the basic block (the unsigned), and then on the MBB number. 1502 struct DepthMBBCompare { 1503 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1504 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1505 if (LHS.first > RHS.first) return true; // Deeper loops first 1506 return LHS.first == RHS.first && 1507 LHS.second->getNumber() < RHS.second->getNumber(); 1508 } 1509 }; 1510} 1511 1512 1513void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB, 1514 std::vector<CopyRec> *TryAgain, bool PhysOnly) { 1515 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 1516 1517 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1518 MII != E;) { 1519 MachineInstr *Inst = MII++; 1520 1521 // If this isn't a copy, we can't join intervals. 1522 unsigned SrcReg, DstReg; 1523 if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue; 1524 1525 if (TryAgain && !JoinCopy(Inst, SrcReg, DstReg, PhysOnly)) 1526 TryAgain->push_back(getCopyRec(Inst, SrcReg, DstReg)); 1527 } 1528} 1529 1530 1531void LiveIntervals::joinIntervals() { 1532 DOUT << "********** JOINING INTERVALS ***********\n"; 1533 1534 JoinedLIs.resize(getNumIntervals()); 1535 JoinedLIs.reset(); 1536 1537 std::vector<CopyRec> TryAgainList; 1538 const LoopInfo &LI = getAnalysis<LoopInfo>(); 1539 if (LI.begin() == LI.end()) { 1540 // If there are no loops in the function, join intervals in function order. 1541 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 1542 I != E; ++I) 1543 CopyCoallesceInMBB(I, &TryAgainList); 1544 } else { 1545 // Otherwise, join intervals in inner loops before other intervals. 1546 // Unfortunately we can't just iterate over loop hierarchy here because 1547 // there may be more MBB's than BB's. Collect MBB's for sorting. 1548 1549 // Join intervals in the function prolog first. We want to join physical 1550 // registers with virtual registers before the intervals got too long. 1551 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1552 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); I != E;++I) 1553 MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 1554 1555 // Sort by loop depth. 1556 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1557 1558 // Finally, join intervals in loop nest order. 1559 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1560 CopyCoallesceInMBB(MBBs[i].second, NULL, true); 1561 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1562 CopyCoallesceInMBB(MBBs[i].second, &TryAgainList, false); 1563 } 1564 1565 // Joining intervals can allow other intervals to be joined. Iteratively join 1566 // until we make no progress. 1567 bool ProgressMade = true; 1568 while (ProgressMade) { 1569 ProgressMade = false; 1570 1571 for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 1572 CopyRec &TheCopy = TryAgainList[i]; 1573 if (TheCopy.MI && 1574 JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) { 1575 TheCopy.MI = 0; // Mark this one as done. 1576 ProgressMade = true; 1577 } 1578 } 1579 } 1580 1581 // Some live range has been lengthened due to colaescing, eliminate the 1582 // unnecessary kills. 1583 int RegNum = JoinedLIs.find_first(); 1584 while (RegNum != -1) { 1585 unsigned Reg = RegNum + MRegisterInfo::FirstVirtualRegister; 1586 unsigned repReg = rep(Reg); 1587 LiveInterval &LI = getInterval(repReg); 1588 LiveVariables::VarInfo& svi = lv_->getVarInfo(Reg); 1589 for (unsigned i = 0, e = svi.Kills.size(); i != e; ++i) { 1590 MachineInstr *Kill = svi.Kills[i]; 1591 // Suppose vr1 = op vr2, x 1592 // and vr1 and vr2 are coalesced. vr2 should still be marked kill 1593 // unless it is a two-address operand. 1594 if (isRemoved(Kill) || hasRegisterDef(Kill, repReg)) 1595 continue; 1596 if (LI.liveAt(getInstructionIndex(Kill) + InstrSlots::NUM)) 1597 unsetRegisterKill(Kill, repReg); 1598 } 1599 RegNum = JoinedLIs.find_next(RegNum); 1600 } 1601 1602 DOUT << "*** Register mapping ***\n"; 1603 for (int i = 0, e = r2rMap_.size(); i != e; ++i) 1604 if (r2rMap_[i]) { 1605 DOUT << " reg " << i << " -> "; 1606 DEBUG(printRegName(r2rMap_[i])); 1607 DOUT << "\n"; 1608 } 1609} 1610 1611/// Return true if the two specified registers belong to different register 1612/// classes. The registers may be either phys or virt regs. 1613bool LiveIntervals::differingRegisterClasses(unsigned RegA, 1614 unsigned RegB) const { 1615 1616 // Get the register classes for the first reg. 1617 if (MRegisterInfo::isPhysicalRegister(RegA)) { 1618 assert(MRegisterInfo::isVirtualRegister(RegB) && 1619 "Shouldn't consider two physregs!"); 1620 return !mf_->getSSARegMap()->getRegClass(RegB)->contains(RegA); 1621 } 1622 1623 // Compare against the regclass for the second reg. 1624 const TargetRegisterClass *RegClass = mf_->getSSARegMap()->getRegClass(RegA); 1625 if (MRegisterInfo::isVirtualRegister(RegB)) 1626 return RegClass != mf_->getSSARegMap()->getRegClass(RegB); 1627 else 1628 return !RegClass->contains(RegB); 1629} 1630 1631/// lastRegisterUse - Returns the last use of the specific register between 1632/// cycles Start and End. It also returns the use operand by reference. It 1633/// returns NULL if there are no uses. 1634MachineInstr * 1635LiveIntervals::lastRegisterUse(unsigned Reg, unsigned Start, unsigned End, 1636 MachineOperand *&MOU) { 1637 int e = (End-1) / InstrSlots::NUM * InstrSlots::NUM; 1638 int s = Start; 1639 while (e >= s) { 1640 // Skip deleted instructions 1641 MachineInstr *MI = getInstructionFromIndex(e); 1642 while ((e - InstrSlots::NUM) >= s && !MI) { 1643 e -= InstrSlots::NUM; 1644 MI = getInstructionFromIndex(e); 1645 } 1646 if (e < s || MI == NULL) 1647 return NULL; 1648 1649 for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { 1650 MachineOperand &MO = MI->getOperand(i); 1651 if (MO.isReg() && MO.isUse() && MO.getReg() && 1652 mri_->regsOverlap(rep(MO.getReg()), Reg)) { 1653 MOU = &MO; 1654 return MI; 1655 } 1656 } 1657 1658 e -= InstrSlots::NUM; 1659 } 1660 1661 return NULL; 1662} 1663 1664 1665/// findDefOperand - Returns the MachineOperand that is a def of the specific 1666/// register. It returns NULL if the def is not found. 1667MachineOperand *LiveIntervals::findDefOperand(MachineInstr *MI, unsigned Reg) { 1668 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1669 MachineOperand &MO = MI->getOperand(i); 1670 if (MO.isReg() && MO.isDef() && 1671 mri_->regsOverlap(rep(MO.getReg()), Reg)) 1672 return &MO; 1673 } 1674 return NULL; 1675} 1676 1677/// unsetRegisterKill - Unset IsKill property of all uses of specific register 1678/// of the specific instruction. 1679void LiveIntervals::unsetRegisterKill(MachineInstr *MI, unsigned Reg) { 1680 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1681 MachineOperand &MO = MI->getOperand(i); 1682 if (MO.isReg() && MO.isUse() && MO.isKill() && MO.getReg() && 1683 mri_->regsOverlap(rep(MO.getReg()), Reg)) 1684 MO.unsetIsKill(); 1685 } 1686} 1687 1688/// hasRegisterDef - True if the instruction defines the specific register. 1689/// 1690bool LiveIntervals::hasRegisterDef(MachineInstr *MI, unsigned Reg) { 1691 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1692 MachineOperand &MO = MI->getOperand(i); 1693 if (MO.isReg() && MO.isDef() && 1694 mri_->regsOverlap(rep(MO.getReg()), Reg)) 1695 return true; 1696 } 1697 return false; 1698} 1699 1700LiveInterval LiveIntervals::createInterval(unsigned reg) { 1701 float Weight = MRegisterInfo::isPhysicalRegister(reg) ? 1702 HUGE_VALF : 0.0F; 1703 return LiveInterval(reg, Weight); 1704} 1705