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