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