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 loads to
 340     // be re-materialized as well.
 341     int FrameIdx = 0;
 342     if (vi.DefInst &&
 343         (tii_->isReMaterializable(vi.DefInst->getOpcode()) ||
 344          (tii_->isLoadFromStackSlot(vi.DefInst, FrameIdx) &&
 345           mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx)) ||
 346          tii_->isOtherReMaterializableLoad(vi.DefInst)))
 347       interval.remat = vi.DefInst;
 348
 349     // Get the Idx of the defining instructions.
 350     unsigned defIndex = getDefIndex(MIIdx);
 351
 352     unsigned ValNum;
 353     unsigned SrcReg, DstReg;
 354     if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 355       ValNum = interval.getNextValue(~0U, 0);
 356     else
 357       ValNum = interval.getNextValue(defIndex, SrcReg);
 358
 359     assert(ValNum == 0 && "First value in interval is not 0?");
 360     ValNum = 0;  // Clue in the optimizer.
 361
 362     // Loop over all of the blocks that the vreg is defined in.  There are
 363     // two cases we have to handle here.  The most common case is a vreg
 364     // whose lifetime is contained within a basic block.  In this case there
 365     // will be a single kill, in MBB, which comes after the definition.
 366     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 367       // FIXME: what about dead vars?
 368       unsigned killIdx;
 369       if (vi.Kills[0] != mi)
 370         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 371       else
 372         killIdx = defIndex+1;
 373
 374       // If the kill happens after the definition, we have an intra-block
 375       // live range.
 376       if (killIdx > defIndex) {
 377         assert(vi.AliveBlocks.none() &&
 378                "Shouldn't be alive across any blocks!");
 379         LiveRange LR(defIndex, killIdx, ValNum);
 380         interval.addRange(LR);
 381         DOUT << " +" << LR << "\n";
 382         return;
 383       }
 384     }
 385
 386     // The other case we handle is when a virtual register lives to the end
 387     // of the defining block, potentially live across some blocks, then is
 388     // live into some number of blocks, but gets killed.  Start by adding a
 389     // range that goes from this definition to the end of the defining block.
 390     LiveRange NewLR(defIndex,
 391                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 392                     ValNum);
 393     DOUT << " +" << NewLR;
 394     interval.addRange(NewLR);
 395
 396     // Iterate over all of the blocks that the variable is completely
 397     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 398     // live interval.
 399     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 400       if (vi.AliveBlocks[i]) {
 401         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 402         if (!MBB->empty()) {
 403           LiveRange LR(getMBBStartIdx(i),
 404                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 405                        ValNum);
 406           interval.addRange(LR);
 407           DOUT << " +" << LR;
 408         }
 409       }
 410     }
 411
 412     // Finally, this virtual register is live from the start of any killing
 413     // block to the 'use' slot of the killing instruction.
 414     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 415       MachineInstr *Kill = vi.Kills[i];
 416       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 417                    getUseIndex(getInstructionIndex(Kill))+1,
 418                    ValNum);
 419       interval.addRange(LR);
 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, std::make_pair(~0U, 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
 461       // If this redefinition is dead, we need to add a dummy unit live
 462       // range covering the def slot.
 463       if (lv_->RegisterDefIsDead(mi, interval.reg))
 464         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
 465
 466       DOUT << " RESULT: ";
 467       interval.print(DOUT, mri_);
 468
 469     } else {
 470       // Otherwise, this must be because of phi elimination.  If this is the
 471       // first redefinition of the vreg that we have seen, go back and change
 472       // the live range in the PHI block to be a different value number.
 473       if (interval.containsOneValue()) {
 474         assert(vi.Kills.size() == 1 &&
 475                "PHI elimination vreg should have one kill, the PHI itself!");
 476
 477         // Remove the old range that we now know has an incorrect number.
 478         MachineInstr *Killer = vi.Kills[0];
 479         unsigned Start = getMBBStartIdx(Killer->getParent());
 480         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 481         DOUT << " Removing [" << Start << "," << End << "] from: ";
 482         interval.print(DOUT, mri_); DOUT << "\n";
 483         interval.removeRange(Start, End);
 484         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 485
 486         // Replace the interval with one of a NEW value number.  Note that this
 487         // value number isn't actually defined by an instruction, weird huh? :)
 488         LiveRange LR(Start, End, interval.getNextValue(~0U, 0));
 489         DOUT << " replace range with " << LR;
 490         interval.addRange(LR);
 491         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 492       }
 493
 494       // In the case of PHI elimination, each variable definition is only
 495       // live until the end of the block.  We've already taken care of the
 496       // rest of the live range.
 497       unsigned defIndex = getDefIndex(MIIdx);
 498
 499       unsigned ValNum;
 500       unsigned SrcReg, DstReg;
 501       if (!tii_->isMoveInstr(*mi, SrcReg, DstReg))
 502         ValNum = interval.getNextValue(~0U, 0);
 503       else
 504         ValNum = interval.getNextValue(defIndex, SrcReg);
 505
 506       LiveRange LR(defIndex,
 507                    getInstructionIndex(&mbb->back()) + InstrSlots::NUM, ValNum);
 508       interval.addRange(LR);
 509       DOUT << " +" << LR;
 510     }
 511   }
 512
 513   DOUT << '\n';
 514 }
 515
 516 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 517                                               MachineBasicBlock::iterator mi,
 518                                               unsigned MIIdx,
 519                                               LiveInterval &interval,
 520                                               unsigned SrcReg) {
 521   // A physical register cannot be live across basic block, so its
 522   // lifetime must end somewhere in its defining basic block.
 523   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 524
 525   unsigned baseIndex = MIIdx;
 526   unsigned start = getDefIndex(baseIndex);
 527   unsigned end = start;
 528
 529   // If it is not used after definition, it is considered dead at
 530   // the instruction defining it. Hence its interval is:
 531   // [defSlot(def), defSlot(def)+1)
 532   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 533     DOUT << " dead";
 534     end = getDefIndex(start) + 1;
 535     goto exit;
 536   }
 537
 538   // If it is not dead on definition, it must be killed by a
 539   // subsequent instruction. Hence its interval is:
 540   // [defSlot(def), useSlot(kill)+1)
 541   while (++mi != MBB->end()) {
 542     baseIndex += InstrSlots::NUM;
 543     if (lv_->KillsRegister(mi, interval.reg)) {
 544       DOUT << " killed";
 545       end = getUseIndex(baseIndex) + 1;
 546       goto exit;
 547     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 548       // Another instruction redefines the register before it is ever read.
 549       // Then the register is essentially dead at the instruction that defines
 550       // it. Hence its interval is:
 551       // [defSlot(def), defSlot(def)+1)
 552       DOUT << " dead";
 553       end = getDefIndex(start) + 1;
 554       goto exit;
 555     }
 556   }
 557
 558   // The only case we should have a dead physreg here without a killing or
 559   // instruction where we know it's dead is if it is live-in to the function
 560   // and never used.
 561   assert(!SrcReg && "physreg was not killed in defining block!");
 562   end = getDefIndex(start) + 1;  // It's dead.
 563
 564 exit:
 565   assert(start < end && "did not find end of interval?");
 566
 567   // Already exists? Extend old live interval.
 568   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 569   unsigned Id = (OldLR != interval.end())
 570     ? OldLR->ValId
 571     : interval.getNextValue(SrcReg != 0 ? start : ~0U, SrcReg);
 572   LiveRange LR(start, end, Id);
 573   interval.addRange(LR);
 574   DOUT << " +" << LR << '\n';
 575 }
 576
 577 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 578                                       MachineBasicBlock::iterator MI,
 579                                       unsigned MIIdx,
 580                                       unsigned reg) {
 581   if (MRegisterInfo::isVirtualRegister(reg))
 582     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 583   else if (allocatableRegs_[reg]) {
 584     unsigned SrcReg, DstReg;
 585     if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 586       SrcReg = 0;
 587     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 588     // Def of a register also defines its sub-registers.
 589     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 590       // Avoid processing some defs more than once.
 591       if (!MI->findRegisterDefOperand(*AS))
 592         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 593   }
 594 }
 595
 596 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 597                                          unsigned MIIdx,
 598                                          LiveInterval &interval, bool isAlias) {
 599   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 600
 601   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 602   // be considered a livein.
 603   MachineBasicBlock::iterator mi = MBB->begin();
 604   unsigned baseIndex = MIIdx;
 605   unsigned start = baseIndex;
 606   unsigned end = start;
 607   while (mi != MBB->end()) {
 608     if (lv_->KillsRegister(mi, interval.reg)) {
 609       DOUT << " killed";
 610       end = getUseIndex(baseIndex) + 1;
 611       goto exit;
 612     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 613       // Another instruction redefines the register before it is ever read.
 614       // Then the register is essentially dead at the instruction that defines
 615       // it. Hence its interval is:
 616       // [defSlot(def), defSlot(def)+1)
 617       DOUT << " dead";
 618       end = getDefIndex(start) + 1;
 619       goto exit;
 620     }
 621
 622     baseIndex += InstrSlots::NUM;
 623     ++mi;
 624   }
 625
 626 exit:
 627   // Alias of a live-in register might not be used at all.
 628   if (isAlias && end == 0) {
 629     DOUT << " dead";
 630     end = getDefIndex(start) + 1;
 631   }
 632
 633   assert(start < end && "did not find end of interval?");
 634
 635   LiveRange LR(start, end, interval.getNextValue(~0U, 0));
 636   DOUT << " +" << LR << '\n';
 637   interval.addRange(LR);
 638 }
 639
 640 /// computeIntervals - computes the live intervals for virtual
 641 /// registers. for some ordering of the machine instructions [1,N] a
 642 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 643 /// which a variable is live
 644 void LiveIntervals::computeIntervals() {
 645   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 646        << "********** Function: "
 647        << ((Value*)mf_->getFunction())->getName() << '\n';
 648   // Track the index of the current machine instr.
 649   unsigned MIIndex = 0;
 650   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 651        MBBI != E; ++MBBI) {
 652     MachineBasicBlock *MBB = MBBI;
 653     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 654
 655     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 656
 657     if (MBB->livein_begin() != MBB->livein_end()) {
 658       // Create intervals for live-ins to this BB first.
 659       for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 660              LE = MBB->livein_end(); LI != LE; ++LI) {
 661         handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 662         // Multiple live-ins can alias the same register.
 663         for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 664           if (!hasInterval(*AS))
 665             handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), true);
 666       }
 667     }
 668
 669     for (; MI != miEnd; ++MI) {
 670       DOUT << MIIndex << "\t" << *MI;
 671
 672       // Handle defs.
 673       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 674         MachineOperand &MO = MI->getOperand(i);
 675         // handle register defs - build intervals
 676         if (MO.isRegister() && MO.getReg() && MO.isDef())
 677           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 678       }
 679
 680       MIIndex += InstrSlots::NUM;
 681     }
 682   }
 683 }
 684
 685 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 686   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 687                        HUGE_VALF : 0.0F;
 688   return LiveInterval(reg, Weight);
 689 }