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. The target may permit other
 340     // instructions to be re-materialized as well.
 341     int FrameIdx = 0;
 342     if (vi.DefInst &&
 343         (tii_->isTriviallyReMaterializable(vi.DefInst) ||
 344          (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) &&
 345           mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))))
 346       interval.remat = vi.DefInst;
 347
 348     // Get the Idx of the defining instructions.
 349     unsigned defIndex = getDefIndex(MIIdx);
 350     unsigned ValNum;
 351     unsigned SrcReg, DstReg;
 352     if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 353       ValNum = interval.getNextValue(defIndex, 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         interval.addKillForValNum(ValNum, killIdx);
 381         return;
 382       }
 383     }
 384
 385     // The other case we handle is when a virtual register lives to the end
 386     // of the defining block, potentially live across some blocks, then is
 387     // live into some number of blocks, but gets killed.  Start by adding a
 388     // range that goes from this definition to the end of the defining block.
 389     LiveRange NewLR(defIndex,
 390                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 391                     ValNum);
 392     DOUT << " +" << NewLR;
 393     interval.addRange(NewLR);
 394
 395     // Iterate over all of the blocks that the variable is completely
 396     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 397     // live interval.
 398     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 399       if (vi.AliveBlocks[i]) {
 400         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 401         if (!MBB->empty()) {
 402           LiveRange LR(getMBBStartIdx(i),
 403                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 404                        ValNum);
 405           interval.addRange(LR);
 406           DOUT << " +" << LR;
 407         }
 408       }
 409     }
 410
 411     // Finally, this virtual register is live from the start of any killing
 412     // block to the 'use' slot of the killing instruction.
 413     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 414       MachineInstr *Kill = vi.Kills[i];
 415       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
 416       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 417                    killIdx, ValNum);
 418       interval.addRange(LR);
 419       interval.addKillForValNum(ValNum, killIdx);
 420       DOUT << " +" << LR;
 421     }
 422
 423   } else {
 424     // Can no longer safely assume definition is rematerializable.
 425     interval.remat = NULL;
 426
 427     // If this is the second time we see a virtual register definition, it
 428     // must be due to phi elimination or two addr elimination.  If this is
 429     // the result of two address elimination, then the vreg is one of the
 430     // def-and-use register operand.
 431     if (isReDefinedByTwoAddr(mi, interval.reg, tii_)) {
 432       // If this is a two-address definition, then we have already processed
 433       // the live range.  The only problem is that we didn't realize there
 434       // are actually two values in the live interval.  Because of this we
 435       // need to take the LiveRegion that defines this register and split it
 436       // into two values.
 437       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
 438       unsigned RedefIndex = getDefIndex(MIIdx);
 439
 440       // Delete the initial value, which should be short and continuous,
 441       // because the 2-addr copy must be in the same MBB as the redef.
 442       interval.removeRange(DefIndex, RedefIndex);
 443
 444       // Two-address vregs should always only be redefined once.  This means
 445       // that at this point, there should be exactly one value number in it.
 446       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 447
 448       // The new value number (#1) is defined by the instruction we claimed
 449       // defined value #0.
 450       unsigned ValNo = interval.getNextValue(0, 0);
 451       interval.setValueNumberInfo(1, interval.getValNumInfo(0));
 452
 453       // Value#0 is now defined by the 2-addr instruction.
 454       interval.setValueNumberInfo(0, LiveInterval::VNInfo(DefIndex, 0U));
 455
 456       // Add the new live interval which replaces the range for the input copy.
 457       LiveRange LR(DefIndex, RedefIndex, ValNo);
 458       DOUT << " replace range with " << LR;
 459       interval.addRange(LR);
 460       interval.addKillForValNum(ValNo, RedefIndex);
 461
 462       // If this redefinition is dead, we need to add a dummy unit live
 463       // range covering the def slot.
 464       if (lv_->RegisterDefIsDead(mi, interval.reg))
 465         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
 466
 467       DOUT << " RESULT: ";
 468       interval.print(DOUT, mri_);
 469
 470     } else {
 471       // Otherwise, this must be because of phi elimination.  If this is the
 472       // first redefinition of the vreg that we have seen, go back and change
 473       // the live range in the PHI block to be a different value number.
 474       if (interval.containsOneValue()) {
 475         assert(vi.Kills.size() == 1 &&
 476                "PHI elimination vreg should have one kill, the PHI itself!");
 477
 478         // Remove the old range that we now know has an incorrect number.
 479         MachineInstr *Killer = vi.Kills[0];
 480         unsigned Start = getMBBStartIdx(Killer->getParent());
 481         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 482         DOUT << " Removing [" << Start << "," << End << "] from: ";
 483         interval.print(DOUT, mri_); DOUT << "\n";
 484         interval.removeRange(Start, End);
 485         bool replaced = interval.replaceKillForValNum(0, End, Start);
 486         assert(replaced && "Incorrect kill info?");
 487         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 488
 489         // Replace the interval with one of a NEW value number.  Note that this
 490         // value number isn't actually defined by an instruction, weird huh? :)
 491         LiveRange LR(Start, End, interval.getNextValue(~0, 0));
 492         DOUT << " replace range with " << LR;
 493         interval.addRange(LR);
 494         interval.addKillForValNum(LR.ValId, End);
 495         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 496       }
 497
 498       // In the case of PHI elimination, each variable definition is only
 499       // live until the end of the block.  We've already taken care of the
 500       // rest of the live range.
 501       unsigned defIndex = getDefIndex(MIIdx);
 502
 503       unsigned ValNum;
 504       unsigned SrcReg, DstReg;
 505       if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 506         ValNum = interval.getNextValue(defIndex, 0);
 507       else
 508         ValNum = interval.getNextValue(defIndex, SrcReg);
 509
 510       unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
 511       LiveRange LR(defIndex, killIndex, ValNum);
 512       interval.addRange(LR);
 513       interval.addKillForValNum(ValNum, killIndex);
 514       DOUT << " +" << LR;
 515     }
 516   }
 517
 518   DOUT << '\n';
 519 }
 520
 521 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 522                                               MachineBasicBlock::iterator mi,
 523                                               unsigned MIIdx,
 524                                               LiveInterval &interval,
 525                                               unsigned SrcReg) {
 526   // A physical register cannot be live across basic block, so its
 527   // lifetime must end somewhere in its defining basic block.
 528   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 529
 530   unsigned baseIndex = MIIdx;
 531   unsigned start = getDefIndex(baseIndex);
 532   unsigned end = start;
 533
 534   // If it is not used after definition, it is considered dead at
 535   // the instruction defining it. Hence its interval is:
 536   // [defSlot(def), defSlot(def)+1)
 537   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 538     DOUT << " dead";
 539     end = getDefIndex(start) + 1;
 540     goto exit;
 541   }
 542
 543   // If it is not dead on definition, it must be killed by a
 544   // subsequent instruction. Hence its interval is:
 545   // [defSlot(def), useSlot(kill)+1)
 546   while (++mi != MBB->end()) {
 547     baseIndex += InstrSlots::NUM;
 548     if (lv_->KillsRegister(mi, interval.reg)) {
 549       DOUT << " killed";
 550       end = getUseIndex(baseIndex) + 1;
 551       goto exit;
 552     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 553       // Another instruction redefines the register before it is ever read.
 554       // Then the register is essentially dead at the instruction that defines
 555       // it. Hence its interval is:
 556       // [defSlot(def), defSlot(def)+1)
 557       DOUT << " dead";
 558       end = getDefIndex(start) + 1;
 559       goto exit;
 560     }
 561   }
 562
 563   // The only case we should have a dead physreg here without a killing or
 564   // instruction where we know it's dead is if it is live-in to the function
 565   // and never used.
 566   assert(!SrcReg && "physreg was not killed in defining block!");
 567   end = getDefIndex(start) + 1;  // It's dead.
 568
 569 exit:
 570   assert(start < end && "did not find end of interval?");
 571
 572   // Already exists? Extend old live interval.
 573   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 574   unsigned Id = (OldLR != interval.end())
 575     ? OldLR->ValId : interval.getNextValue(start, SrcReg);
 576   LiveRange LR(start, end, Id);
 577   interval.addRange(LR);
 578   interval.addKillForValNum(LR.ValId, end);
 579   DOUT << " +" << LR << '\n';
 580 }
 581
 582 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 583                                       MachineBasicBlock::iterator MI,
 584                                       unsigned MIIdx,
 585                                       unsigned reg) {
 586   if (MRegisterInfo::isVirtualRegister(reg))
 587     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 588   else if (allocatableRegs_[reg]) {
 589     unsigned SrcReg, DstReg;
 590     if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 591       SrcReg = 0;
 592     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 593     // Def of a register also defines its sub-registers.
 594     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 595       // Avoid processing some defs more than once.
 596       if (!MI->findRegisterDefOperand(*AS))
 597         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 598   }
 599 }
 600
 601 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 602                                          unsigned MIIdx,
 603                                          LiveInterval &interval, bool isAlias) {
 604   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 605
 606   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 607   // be considered a livein.
 608   MachineBasicBlock::iterator mi = MBB->begin();
 609   unsigned baseIndex = MIIdx;
 610   unsigned start = baseIndex;
 611   unsigned end = start;
 612   while (mi != MBB->end()) {
 613     if (lv_->KillsRegister(mi, interval.reg)) {
 614       DOUT << " killed";
 615       end = getUseIndex(baseIndex) + 1;
 616       goto exit;
 617     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 618       // Another instruction redefines the register before it is ever read.
 619       // Then the register is essentially dead at the instruction that defines
 620       // it. Hence its interval is:
 621       // [defSlot(def), defSlot(def)+1)
 622       DOUT << " dead";
 623       end = getDefIndex(start) + 1;
 624       goto exit;
 625     }
 626
 627     baseIndex += InstrSlots::NUM;
 628     ++mi;
 629   }
 630
 631 exit:
 632   // Live-in register might not be used at all.
 633   if (end == MIIdx) {
 634     if (isAlias) {
 635       DOUT << " dead";
 636       end = getDefIndex(MIIdx) + 1;
 637     } else {
 638       DOUT << " live through";
 639       end = baseIndex;
 640     }
 641   }
 642
 643   LiveRange LR(start, end, interval.getNextValue(start, 0));
 644   interval.addRange(LR);
 645   interval.addKillForValNum(LR.ValId, end);
 646   DOUT << " +" << LR << '\n';
 647 }
 648
 649 /// computeIntervals - computes the live intervals for virtual
 650 /// registers. for some ordering of the machine instructions [1,N] a
 651 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 652 /// which a variable is live
 653 void LiveIntervals::computeIntervals() {
 654   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 655        << "********** Function: "
 656        << ((Value*)mf_->getFunction())->getName() << '\n';
 657   // Track the index of the current machine instr.
 658   unsigned MIIndex = 0;
 659   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 660        MBBI != E; ++MBBI) {
 661     MachineBasicBlock *MBB = MBBI;
 662     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 663
 664     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 665
 666     if (MBB->livein_begin() != MBB->livein_end()) {
 667       // Create intervals for live-ins to this BB first.
 668       for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 669              LE = MBB->livein_end(); LI != LE; ++LI) {
 670         handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 671         // Multiple live-ins can alias the same register.
 672         for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 673           if (!hasInterval(*AS))
 674             handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 675                                  true);
 676       }
 677     }
 678
 679     for (; MI != miEnd; ++MI) {
 680       DOUT << MIIndex << "\t" << *MI;
 681
 682       // Handle defs.
 683       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 684         MachineOperand &MO = MI->getOperand(i);
 685         // handle register defs - build intervals
 686         if (MO.isRegister() && MO.getReg() && MO.isDef())
 687           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 688       }
 689
 690       MIIndex += InstrSlots::NUM;
 691     }
 692   }
 693 }
 694
 695 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 696   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 697                        HUGE_VALF : 0.0F;
 698   return LiveInterval(reg, Weight);
 699 }