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