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/SmallSet.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include <algorithm>
  37 #include <cmath>
  38 using namespace llvm;
  39
  40 STATISTIC(numIntervals, "Number of original intervals");
  41 STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
  42 STATISTIC(numFolded   , "Number of loads/stores folded into instructions");
  43
  44 char LiveIntervals::ID = 0;
  45 namespace {
  46   RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
  47 }
  48
  49 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  50   AU.addPreserved<LiveVariables>();
  51   AU.addRequired<LiveVariables>();
  52   AU.addPreservedID(PHIEliminationID);
  53   AU.addRequiredID(PHIEliminationID);
  54   AU.addRequiredID(TwoAddressInstructionPassID);
  55   AU.addRequired<LoopInfo>();
  56   MachineFunctionPass::getAnalysisUsage(AU);
  57 }
  58
  59 void LiveIntervals::releaseMemory() {
  60   mi2iMap_.clear();
  61   i2miMap_.clear();
  62   r2iMap_.clear();
  63 }
  64
  65 /// runOnMachineFunction - Register allocate the whole function
  66 ///
  67 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  68   mf_ = &fn;
  69   tm_ = &fn.getTarget();
  70   mri_ = tm_->getRegisterInfo();
  71   tii_ = tm_->getInstrInfo();
  72   lv_ = &getAnalysis<LiveVariables>();
  73   allocatableRegs_ = mri_->getAllocatableSet(fn);
  74
  75   // Number MachineInstrs and MachineBasicBlocks.
  76   // Initialize MBB indexes to a sentinal.
  77   MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U);
  78
  79   unsigned MIIndex = 0;
  80   for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
  81        MBB != E; ++MBB) {
  82     // Set the MBB2IdxMap entry for this MBB.
  83     MBB2IdxMap[MBB->getNumber()] = MIIndex;
  84
  85     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
  86          I != E; ++I) {
  87       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
  88       assert(inserted && "multiple MachineInstr -> index mappings");
  89       i2miMap_.push_back(I);
  90       MIIndex += InstrSlots::NUM;
  91     }
  92   }
  93
  94   computeIntervals();
  95
  96   numIntervals += getNumIntervals();
  97
  98   DOUT << "********** INTERVALS **********\n";
  99   for (iterator I = begin(), E = end(); I != E; ++I) {
 100     I->second.print(DOUT, mri_);
 101     DOUT << "\n";
 102   }
 103
 104   numIntervalsAfter += getNumIntervals();
 105   DEBUG(dump());
 106   return true;
 107 }
 108
 109 /// print - Implement the dump method.
 110 void LiveIntervals::print(std::ostream &O, const Module* ) const {
 111   O << "********** INTERVALS **********\n";
 112   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 113     I->second.print(DOUT, mri_);
 114     DOUT << "\n";
 115   }
 116
 117   O << "********** MACHINEINSTRS **********\n";
 118   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 119        mbbi != mbbe; ++mbbi) {
 120     O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
 121     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 122            mie = mbbi->end(); mii != mie; ++mii) {
 123       O << getInstructionIndex(mii) << '\t' << *mii;
 124     }
 125   }
 126 }
 127
 128 // Not called?
 129 /// CreateNewLiveInterval - Create a new live interval with the given live
 130 /// ranges. The new live interval will have an infinite spill weight.
 131 LiveInterval&
 132 LiveIntervals::CreateNewLiveInterval(const LiveInterval *LI,
 133                                      const std::vector<LiveRange> &LRs) {
 134   const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(LI->reg);
 135
 136   // Create a new virtual register for the spill interval.
 137   unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(RC);
 138
 139   // Replace the old virtual registers in the machine operands with the shiny
 140   // new one.
 141   for (std::vector<LiveRange>::const_iterator
 142          I = LRs.begin(), E = LRs.end(); I != E; ++I) {
 143     unsigned Index = getBaseIndex(I->start);
 144     unsigned End = getBaseIndex(I->end - 1) + InstrSlots::NUM;
 145
 146     for (; Index != End; Index += InstrSlots::NUM) {
 147       // Skip deleted instructions
 148       while (Index != End && !getInstructionFromIndex(Index))
 149         Index += InstrSlots::NUM;
 150
 151       if (Index == End) break;
 152
 153       MachineInstr *MI = getInstructionFromIndex(Index);
 154
 155       for (unsigned J = 0, e = MI->getNumOperands(); J != e; ++J) {
 156         MachineOperand &MOp = MI->getOperand(J);
 157         if (MOp.isRegister() && MOp.getReg() == LI->reg)
 158           MOp.setReg(NewVReg);
 159       }
 160     }
 161   }
 162
 163   LiveInterval &NewLI = getOrCreateInterval(NewVReg);
 164
 165   // The spill weight is now infinity as it cannot be spilled again
 166   NewLI.weight = float(HUGE_VAL);
 167
 168   for (std::vector<LiveRange>::const_iterator
 169          I = LRs.begin(), E = LRs.end(); I != E; ++I) {
 170     DOUT << "  Adding live range " << *I << " to new interval\n";
 171     NewLI.addRange(*I);
 172   }
 173
 174   DOUT << "Created new live interval " << NewLI << "\n";
 175   return NewLI;
 176 }
 177
 178 std::vector<LiveInterval*> LiveIntervals::
 179 addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
 180   // since this is called after the analysis is done we don't know if
 181   // LiveVariables is available
 182   lv_ = getAnalysisToUpdate<LiveVariables>();
 183
 184   std::vector<LiveInterval*> added;
 185
 186   assert(li.weight != HUGE_VALF &&
 187          "attempt to spill already spilled interval!");
 188
 189   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
 190   li.print(DOUT, mri_);
 191   DOUT << '\n';
 192
 193   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
 194
 195   for (LiveInterval::Ranges::const_iterator
 196          i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
 197     unsigned index = getBaseIndex(i->start);
 198     unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM;
 199     for (; index != end; index += InstrSlots::NUM) {
 200       // skip deleted instructions
 201       while (index != end && !getInstructionFromIndex(index))
 202         index += InstrSlots::NUM;
 203       if (index == end) break;
 204
 205       MachineInstr *MI = getInstructionFromIndex(index);
 206
 207     RestartInstruction:
 208       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 209         MachineOperand& mop = MI->getOperand(i);
 210         if (mop.isRegister() && mop.getReg() == li.reg) {
 211           MachineInstr *fmi = li.remat ? NULL
 212             : mri_->foldMemoryOperand(MI, i, slot);
 213           if (fmi) {
 214             // Attempt to fold the memory reference into the instruction.  If we
 215             // can do this, we don't need to insert spill code.
 216             if (lv_)
 217               lv_->instructionChanged(MI, fmi);
 218             MachineBasicBlock &MBB = *MI->getParent();
 219             vrm.virtFolded(li.reg, MI, i, fmi);
 220             mi2iMap_.erase(MI);
 221             i2miMap_[index/InstrSlots::NUM] = fmi;
 222             mi2iMap_[fmi] = index;
 223             MI = MBB.insert(MBB.erase(MI), fmi);
 224             ++numFolded;
 225             // Folding the load/store can completely change the instruction in
 226             // unpredictable ways, rescan it from the beginning.
 227             goto RestartInstruction;
 228           } else {
 229             // Create a new virtual register for the spill interval.
 230             unsigned NewVReg = mf_->getSSARegMap()->createVirtualRegister(rc);
 231
 232             // Scan all of the operands of this instruction rewriting operands
 233             // to use NewVReg instead of li.reg as appropriate.  We do this for
 234             // two reasons:
 235             //
 236             //   1. If the instr reads the same spilled vreg multiple times, we
 237             //      want to reuse the NewVReg.
 238             //   2. If the instr is a two-addr instruction, we are required to
 239             //      keep the src/dst regs pinned.
 240             //
 241             // Keep track of whether we replace a use and/or def so that we can
 242             // create the spill interval with the appropriate range.
 243             mop.setReg(NewVReg);
 244
 245             bool HasUse = mop.isUse();
 246             bool HasDef = mop.isDef();
 247             for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 248               if (MI->getOperand(j).isReg() &&
 249                   MI->getOperand(j).getReg() == li.reg) {
 250                 MI->getOperand(j).setReg(NewVReg);
 251                 HasUse |= MI->getOperand(j).isUse();
 252                 HasDef |= MI->getOperand(j).isDef();
 253               }
 254             }
 255
 256             // create a new register for this spill
 257             vrm.grow();
 258             if (li.remat)
 259               vrm.setVirtIsReMaterialized(NewVReg, li.remat);
 260             vrm.assignVirt2StackSlot(NewVReg, slot);
 261             LiveInterval &nI = getOrCreateInterval(NewVReg);
 262             nI.remat = li.remat;
 263             assert(nI.empty());
 264
 265             // the spill weight is now infinity as it
 266             // cannot be spilled again
 267             nI.weight = HUGE_VALF;
 268
 269             if (HasUse) {
 270               LiveRange LR(getLoadIndex(index), getUseIndex(index),
 271                            nI.getNextValue(~0U, 0));
 272               DOUT << " +" << LR;
 273               nI.addRange(LR);
 274             }
 275             if (HasDef) {
 276               LiveRange LR(getDefIndex(index), getStoreIndex(index),
 277                            nI.getNextValue(~0U, 0));
 278               DOUT << " +" << LR;
 279               nI.addRange(LR);
 280             }
 281
 282             added.push_back(&nI);
 283
 284             // update live variables if it is available
 285             if (lv_)
 286               lv_->addVirtualRegisterKilled(NewVReg, MI);
 287
 288             DOUT << "\t\t\t\tadded new interval: ";
 289             nI.print(DOUT, mri_);
 290             DOUT << '\n';
 291           }
 292         }
 293       }
 294     }
 295   }
 296
 297   return added;
 298 }
 299
 300 void LiveIntervals::printRegName(unsigned reg) const {
 301   if (MRegisterInfo::isPhysicalRegister(reg))
 302     cerr << mri_->getName(reg);
 303   else
 304     cerr << "%reg" << reg;
 305 }
 306
 307 /// isReDefinedByTwoAddr - Returns true if the Reg re-definition is due to
 308 /// two addr elimination.
 309 static bool isReDefinedByTwoAddr(MachineInstr *MI, unsigned Reg,
 310                                 const TargetInstrInfo *TII) {
 311   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 312     MachineOperand &MO1 = MI->getOperand(i);
 313     if (MO1.isRegister() && MO1.isDef() && MO1.getReg() == Reg) {
 314       for (unsigned j = i+1; j < e; ++j) {
 315         MachineOperand &MO2 = MI->getOperand(j);
 316         if (MO2.isRegister() && MO2.isUse() && MO2.getReg() == Reg &&
 317             MI->getInstrDescriptor()->
 318             getOperandConstraint(j, TOI::TIED_TO) == (int)i)
 319           return true;
 320       }
 321     }
 322   }
 323   return false;
 324 }
 325
 326 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 327                                              MachineBasicBlock::iterator mi,
 328                                              unsigned MIIdx,
 329                                              LiveInterval &interval) {
 330   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 331   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 332
 333   // Virtual registers may be defined multiple times (due to phi
 334   // elimination and 2-addr elimination).  Much of what we do only has to be
 335   // done once for the vreg.  We use an empty interval to detect the first
 336   // time we see a vreg.
 337   if (interval.empty()) {
 338     // Remember if the definition can be rematerialized. All load's from fixed
 339     // stack slots are re-materializable.
 340     int FrameIdx = 0;
 341     if (vi.DefInst &&
 342         (tii_->isReMaterializable(vi.DefInst->getOpcode()) ||
 343          (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) &&
 344           mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))))
 345       interval.remat = vi.DefInst;
 346
 347     // Get the Idx of the defining instructions.
 348     unsigned defIndex = getDefIndex(MIIdx);
 349
 350     unsigned ValNum;
 351     unsigned SrcReg, DstReg;
 352     if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 353       ValNum = interval.getNextValue(~0U, 0);
 354     else
 355       ValNum = interval.getNextValue(defIndex, SrcReg);
 356
 357     assert(ValNum == 0 && "First value in interval is not 0?");
 358     ValNum = 0;  // Clue in the optimizer.
 359
 360     // Loop over all of the blocks that the vreg is defined in.  There are
 361     // two cases we have to handle here.  The most common case is a vreg
 362     // whose lifetime is contained within a basic block.  In this case there
 363     // will be a single kill, in MBB, which comes after the definition.
 364     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 365       // FIXME: what about dead vars?
 366       unsigned killIdx;
 367       if (vi.Kills[0] != mi)
 368         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 369       else
 370         killIdx = defIndex+1;
 371
 372       // If the kill happens after the definition, we have an intra-block
 373       // live range.
 374       if (killIdx > defIndex) {
 375         assert(vi.AliveBlocks.none() &&
 376                "Shouldn't be alive across any blocks!");
 377         LiveRange LR(defIndex, killIdx, ValNum);
 378         interval.addRange(LR);
 379         DOUT << " +" << LR << "\n";
 380         return;
 381       }
 382     }
 383
 384     // The other case we handle is when a virtual register lives to the end
 385     // of the defining block, potentially live across some blocks, then is
 386     // live into some number of blocks, but gets killed.  Start by adding a
 387     // range that goes from this definition to the end of the defining block.
 388     LiveRange NewLR(defIndex,
 389                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 390                     ValNum);
 391     DOUT << " +" << NewLR;
 392     interval.addRange(NewLR);
 393
 394     // Iterate over all of the blocks that the variable is completely
 395     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 396     // live interval.
 397     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 398       if (vi.AliveBlocks[i]) {
 399         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 400         if (!MBB->empty()) {
 401           LiveRange LR(getMBBStartIdx(i),
 402                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 403                        ValNum);
 404           interval.addRange(LR);
 405           DOUT << " +" << LR;
 406         }
 407       }
 408     }
 409
 410     // Finally, this virtual register is live from the start of any killing
 411     // block to the 'use' slot of the killing instruction.
 412     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 413       MachineInstr *Kill = vi.Kills[i];
 414       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 415                    getUseIndex(getInstructionIndex(Kill))+1,
 416                    ValNum);
 417       interval.addRange(LR);
 418       DOUT << " +" << LR;
 419     }
 420
 421   } else {
 422     // Can no longer safely assume definition is rematerializable.
 423     interval.remat = NULL;
 424
 425     // If this is the second time we see a virtual register definition, it
 426     // must be due to phi elimination or two addr elimination.  If this is
 427     // the result of two address elimination, then the vreg is one of the
 428     // def-and-use register operand.
 429     if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) {
 430       // If this is a two-address definition, then we have already processed
 431       // the live range.  The only problem is that we didn't realize there
 432       // are actually two values in the live interval.  Because of this we
 433       // need to take the LiveRegion that defines this register and split it
 434       // into two values.
 435       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
 436       unsigned RedefIndex = getDefIndex(MIIdx);
 437
 438       // Delete the initial value, which should be short and continuous,
 439       // because the 2-addr copy must be in the same MBB as the redef.
 440       interval.removeRange(DefIndex, RedefIndex);
 441
 442       // Two-address vregs should always only be redefined once.  This means
 443       // that at this point, there should be exactly one value number in it.
 444       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 445
 446       // The new value number (#1) is defined by the instruction we claimed
 447       // defined value #0.
 448       unsigned ValNo = interval.getNextValue(0, 0);
 449       interval.setValueNumberInfo(1, interval.getValNumInfo(0));
 450
 451       // Value#0 is now defined by the 2-addr instruction.
 452       interval.setValueNumberInfo(0, std::make_pair(~0U, 0U));
 453
 454       // Add the new live interval which replaces the range for the input copy.
 455       LiveRange LR(DefIndex, RedefIndex, ValNo);
 456       DOUT << " replace range with " << LR;
 457       interval.addRange(LR);
 458
 459       // If this redefinition is dead, we need to add a dummy unit live
 460       // range covering the def slot.
 461       if (lv_->RegisterDefIsDead(mi, interval.reg))
 462         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
 463
 464       DOUT << " RESULT: ";
 465       interval.print(DOUT, mri_);
 466
 467     } else {
 468       // Otherwise, this must be because of phi elimination.  If this is the
 469       // first redefinition of the vreg that we have seen, go back and change
 470       // the live range in the PHI block to be a different value number.
 471       if (interval.containsOneValue()) {
 472         assert(vi.Kills.size() == 1 &&
 473                "PHI elimination vreg should have one kill, the PHI itself!");
 474
 475         // Remove the old range that we now know has an incorrect number.
 476         MachineInstr *Killer = vi.Kills[0];
 477         unsigned Start = getMBBStartIdx(Killer->getParent());
 478         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 479         DOUT << " Removing [" << Start << "," << End << "] from: ";
 480         interval.print(DOUT, mri_); DOUT << "\n";
 481         interval.removeRange(Start, End);
 482         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 483
 484         // Replace the interval with one of a NEW value number.  Note that this
 485         // value number isn't actually defined by an instruction, weird huh? :)
 486         LiveRange LR(Start, End, interval.getNextValue(~0U, 0));
 487         DOUT << " replace range with " << LR;
 488         interval.addRange(LR);
 489         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 490       }
 491
 492       // In the case of PHI elimination, each variable definition is only
 493       // live until the end of the block.  We've already taken care of the
 494       // rest of the live range.
 495       unsigned defIndex = getDefIndex(MIIdx);
 496
 497       unsigned ValNum;
 498       unsigned SrcReg, DstReg;
 499       if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 500         ValNum = interval.getNextValue(~0U, 0);
 501       else
 502         ValNum = interval.getNextValue(defIndex, SrcReg);
 503
 504       LiveRange LR(defIndex,
 505                    getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum);
 506       interval.addRange(LR);
 507       DOUT << " +" << LR;
 508     }
 509   }
 510
 511   DOUT << '\n';
 512 }
 513
 514 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 515                                               MachineBasicBlock::iterator mi,
 516                                               unsigned MIIdx,
 517                                               LiveInterval &interval,
 518                                               unsigned SrcReg) {
 519   // A physical register cannot be live across basic block, so its
 520   // lifetime must end somewhere in its defining basic block.
 521   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 522
 523   unsigned baseIndex = MIIdx;
 524   unsigned start = getDefIndex(baseIndex);
 525   unsigned end = start;
 526
 527   // If it is not used after definition, it is considered dead at
 528   // the instruction defining it. Hence its interval is:
 529   // [defSlot(def), defSlot(def)+1)
 530   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 531     DOUT << " dead";
 532     end = getDefIndex(start) + 1;
 533     goto exit;
 534   }
 535
 536   // If it is not dead on definition, it must be killed by a
 537   // subsequent instruction. Hence its interval is:
 538   // [defSlot(def), useSlot(kill)+1)
 539   while (++mi != MBB->end()) {
 540     baseIndex += InstrSlots::NUM;
 541     if (lv_->KillsRegister(mi, interval.reg)) {
 542       DOUT << " killed";
 543       end = getUseIndex(baseIndex) + 1;
 544       goto exit;
 545     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 546       // Another instruction redefines the register before it is ever read.
 547       // Then the register is essentially dead at the instruction that defines
 548       // it. Hence its interval is:
 549       // [defSlot(def), defSlot(def)+1)
 550       DOUT << " dead";
 551       end = getDefIndex(start) + 1;
 552       goto exit;
 553     }
 554   }
 555
 556   // The only case we should have a dead physreg here without a killing or
 557   // instruction where we know it's dead is if it is live-in to the function
 558   // and never used.
 559   assert(!SrcReg && "physreg was not killed in defining block!");
 560   end = getDefIndex(start) + 1;  // It's dead.
 561
 562 exit:
 563   assert(start < end && "did not find end of interval?");
 564
 565   // Already exists? Extend old live interval.
 566   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 567   unsigned Id = (OldLR != interval.end())
 568     ? OldLR->ValId
 569     : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg);
 570   LiveRange LR(start, end, Id);
 571   interval.addRange(LR);
 572   DOUT << " +" << LR << '\n';
 573 }
 574
 575 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 576                                       MachineBasicBlock::iterator MI,
 577                                       unsigned MIIdx,
 578                                       unsigned reg) {
 579   if (MRegisterInfo::isVirtualRegister(reg))
 580     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 581   else if (allocatableRegs_[reg]) {
 582     unsigned SrcReg, DstReg;
 583     if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 584       SrcReg = 0;
 585     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 586     // Def of a register also defines its sub-registers.
 587     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 588       // Avoid processing some defs more than once.
 589       if (!MI->findRegisterDefOperand(*AS))
 590         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 591   }
 592 }
 593
 594 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 595                                          unsigned MIIdx,
 596                                          LiveInterval &interval, bool isAlias) {
 597   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 598
 599   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 600   // be considered a livein.
 601   MachineBasicBlock::iterator mi = MBB->begin();
 602   unsigned baseIndex = MIIdx;
 603   unsigned start = baseIndex;
 604   unsigned end = start;
 605   while (mi != MBB->end()) {
 606     if (lv_->KillsRegister(mi, interval.reg)) {
 607       DOUT << " killed";
 608       end = getUseIndex(baseIndex) + 1;
 609       goto exit;
 610     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 611       // Another instruction redefines the register before it is ever read.
 612       // Then the register is essentially dead at the instruction that defines
 613       // it. Hence its interval is:
 614       // [defSlot(def), defSlot(def)+1)
 615       DOUT << " dead";
 616       end = getDefIndex(start) + 1;
 617       goto exit;
 618     }
 619
 620     baseIndex += InstrSlots::NUM;
 621     ++mi;
 622   }
 623
 624 exit:
 625   // Alias of a live-in register might not be used at all.
 626   if (isAlias && end == 0) {
 627     DOUT << " dead";
 628     end = getDefIndex(start) + 1;
 629   }
 630
 631   assert(start < end && "did not find end of interval?");
 632
 633   LiveRange LR(start, end, interval.getNextValue(~0U, 0));
 634   DOUT << " +" << LR << '\n';
 635   interval.addRange(LR);
 636 }
 637
 638 /// computeIntervals - computes the live intervals for virtual
 639 /// registers. for some ordering of the machine instructions [1,N] a
 640 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 641 /// which a variable is live
 642 void LiveIntervals::computeIntervals() {
 643   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 644        << "********** Function: "
 645        << ((Value*)mf_->getFunction())->getName() << '\n';
 646   // Track the index of the current machine instr.
 647   unsigned MIIndex = 0;
 648   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 649        MBBI != E; ++MBBI) {
 650     MachineBasicBlock *MBB = MBBI;
 651     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 652
 653     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 654
 655     if (MBB->livein_begin() != MBB->livein_end()) {
 656       // Create intervals for live-ins to this BB first.
 657       for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 658              LE = MBB->livein_end(); LI != LE; ++LI) {
 659         handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 660         // Multiple live-ins can alias the same register.
 661         for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 662           if (!hasInterval(*AS))
 663             handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true);
 664       }
 665     }
 666
 667     for (; MI != miEnd; ++MI) {
 668       DOUT << MIIndex << "\t" << *MI;
 669
 670       // Handle defs.
 671       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 672         MachineOperand &MO = MI->getOperand(i);
 673         // handle register defs - build intervals
 674         if (MO.isRegister() && MO.getReg() && MO.isDef())
 675           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 676       }
 677
 678       MIIndex += InstrSlots::NUM;
 679     }
 680   }
 681 }
 682
 683 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 684   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 685                        HUGE_VALF : 0.0F;
 686   return LiveInterval(reg, Weight);
 687 }