lib/CodeGen/LiveIntervalAnalysis.cpp

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