lib/CodeGen/LiveIntervalAnalysis.cpp

   1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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 "regalloc"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/Value.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/CodeGen/LiveVariables.h"
  23 #include "llvm/CodeGen/MachineDominators.h"
  24 #include "llvm/CodeGen/MachineInstr.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/ADT/DenseSet.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include "LiveRangeCalc.h"
  37 #include <algorithm>
  38 #include <limits>
  39 #include <cmath>
  40 using namespace llvm;
  41
  42 // Switch to the new experimental algorithm for computing live intervals.
  43 static cl::opt<bool>
  44 NewLiveIntervals("new-live-intervals", cl::Hidden,
  45                  cl::desc("Use new algorithm forcomputing live intervals"));
  46
  47 char LiveIntervals::ID = 0;
  48 char &llvm::LiveIntervalsID = LiveIntervals::ID;
  49 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
  50                 "Live Interval Analysis", false, false)
  51 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  52 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
  53 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  54 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  55 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
  56                 "Live Interval Analysis", false, false)
  57
  58 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  59   AU.setPreservesCFG();
  60   AU.addRequired<AliasAnalysis>();
  61   AU.addPreserved<AliasAnalysis>();
  62   AU.addRequired<LiveVariables>();
  63   AU.addPreserved<LiveVariables>();
  64   AU.addPreservedID(MachineLoopInfoID);
  65   AU.addRequiredTransitiveID(MachineDominatorsID);
  66   AU.addPreservedID(MachineDominatorsID);
  67   AU.addPreserved<SlotIndexes>();
  68   AU.addRequiredTransitive<SlotIndexes>();
  69   MachineFunctionPass::getAnalysisUsage(AU);
  70 }
  71
  72 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
  73   DomTree(0), LRCalc(0) {
  74   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
  75 }
  76
  77 LiveIntervals::~LiveIntervals() {
  78   delete LRCalc;
  79 }
  80
  81 void LiveIntervals::releaseMemory() {
  82   // Free the live intervals themselves.
  83   for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
  84     delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
  85   VirtRegIntervals.clear();
  86   RegMaskSlots.clear();
  87   RegMaskBits.clear();
  88   RegMaskBlocks.clear();
  89
  90   for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
  91     delete RegUnitIntervals[i];
  92   RegUnitIntervals.clear();
  93
  94   // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
  95   VNInfoAllocator.Reset();
  96 }
  97
  98 /// runOnMachineFunction - Register allocate the whole function
  99 ///
 100 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 101   MF = &fn;
 102   MRI = &MF->getRegInfo();
 103   TM = &fn.getTarget();
 104   TRI = TM->getRegisterInfo();
 105   TII = TM->getInstrInfo();
 106   AA = &getAnalysis<AliasAnalysis>();
 107   LV = &getAnalysis<LiveVariables>();
 108   Indexes = &getAnalysis<SlotIndexes>();
 109   DomTree = &getAnalysis<MachineDominatorTree>();
 110   if (!LRCalc)
 111     LRCalc = new LiveRangeCalc();
 112   AllocatableRegs = TRI->getAllocatableSet(fn);
 113   ReservedRegs = TRI->getReservedRegs(fn);
 114
 115   // Allocate space for all virtual registers.
 116   VirtRegIntervals.resize(MRI->getNumVirtRegs());
 117
 118   if (NewLiveIntervals) {
 119     // This is the new way of computing live intervals.
 120     // It is independent of LiveVariables, and it can run at any time.
 121     computeVirtRegs();
 122     computeRegMasks();
 123   } else {
 124     // This is the old way of computing live intervals.
 125     // It depends on LiveVariables.
 126     computeIntervals();
 127   }
 128   computeLiveInRegUnits();
 129
 130   DEBUG(dump());
 131   return true;
 132 }
 133
 134 /// print - Implement the dump method.
 135 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
 136   OS << "********** INTERVALS **********\n";
 137
 138   // Dump the regunits.
 139   for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
 140     if (LiveInterval *LI = RegUnitIntervals[i])
 141       OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
 142
 143   // Dump the virtregs.
 144   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 145     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 146     if (hasInterval(Reg))
 147       OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
 148   }
 149
 150   printInstrs(OS);
 151 }
 152
 153 void LiveIntervals::printInstrs(raw_ostream &OS) const {
 154   OS << "********** MACHINEINSTRS **********\n";
 155   MF->print(OS, Indexes);
 156 }
 157
 158 void LiveIntervals::dumpInstrs() const {
 159   printInstrs(dbgs());
 160 }
 161
 162 static
 163 bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
 164   unsigned Reg = MI.getOperand(MOIdx).getReg();
 165   for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
 166     const MachineOperand &MO = MI.getOperand(i);
 167     if (!MO.isReg())
 168       continue;
 169     if (MO.getReg() == Reg && MO.isDef()) {
 170       assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
 171              MI.getOperand(MOIdx).getSubReg() &&
 172              (MO.getSubReg() || MO.isImplicit()));
 173       return true;
 174     }
 175   }
 176   return false;
 177 }
 178
 179 /// isPartialRedef - Return true if the specified def at the specific index is
 180 /// partially re-defining the specified live interval. A common case of this is
 181 /// a definition of the sub-register.
 182 bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
 183                                    LiveInterval &interval) {
 184   if (!MO.getSubReg() || MO.isEarlyClobber())
 185     return false;
 186
 187   SlotIndex RedefIndex = MIIdx.getRegSlot();
 188   const LiveRange *OldLR =
 189     interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
 190   MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
 191   if (DefMI != 0) {
 192     return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
 193   }
 194   return false;
 195 }
 196
 197 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 198                                              MachineBasicBlock::iterator mi,
 199                                              SlotIndex MIIdx,
 200                                              MachineOperand& MO,
 201                                              unsigned MOIdx,
 202                                              LiveInterval &interval) {
 203   DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, TRI));
 204
 205   // Virtual registers may be defined multiple times (due to phi
 206   // elimination and 2-addr elimination).  Much of what we do only has to be
 207   // done once for the vreg.  We use an empty interval to detect the first
 208   // time we see a vreg.
 209   LiveVariables::VarInfo& vi = LV->getVarInfo(interval.reg);
 210   if (interval.empty()) {
 211     // Get the Idx of the defining instructions.
 212     SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
 213
 214     // Make sure the first definition is not a partial redefinition.
 215     assert(!MO.readsReg() && "First def cannot also read virtual register "
 216            "missing <undef> flag?");
 217
 218     VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
 219     assert(ValNo->id == 0 && "First value in interval is not 0?");
 220
 221     // Loop over all of the blocks that the vreg is defined in.  There are
 222     // two cases we have to handle here.  The most common case is a vreg
 223     // whose lifetime is contained within a basic block.  In this case there
 224     // will be a single kill, in MBB, which comes after the definition.
 225     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 226       // FIXME: what about dead vars?
 227       SlotIndex killIdx;
 228       if (vi.Kills[0] != mi)
 229         killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot();
 230       else
 231         killIdx = defIndex.getDeadSlot();
 232
 233       // If the kill happens after the definition, we have an intra-block
 234       // live range.
 235       if (killIdx > defIndex) {
 236         assert(vi.AliveBlocks.empty() &&
 237                "Shouldn't be alive across any blocks!");
 238         LiveRange LR(defIndex, killIdx, ValNo);
 239         interval.addRange(LR);
 240         DEBUG(dbgs() << " +" << LR << "\n");
 241         return;
 242       }
 243     }
 244
 245     // The other case we handle is when a virtual register lives to the end
 246     // of the defining block, potentially live across some blocks, then is
 247     // live into some number of blocks, but gets killed.  Start by adding a
 248     // range that goes from this definition to the end of the defining block.
 249     LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
 250     DEBUG(dbgs() << " +" << NewLR);
 251     interval.addRange(NewLR);
 252
 253     bool PHIJoin = LV->isPHIJoin(interval.reg);
 254
 255     if (PHIJoin) {
 256       // A phi join register is killed at the end of the MBB and revived as a
 257       // new valno in the killing blocks.
 258       assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
 259       DEBUG(dbgs() << " phi-join");
 260     } else {
 261       // Iterate over all of the blocks that the variable is completely
 262       // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 263       // live interval.
 264       for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
 265                E = vi.AliveBlocks.end(); I != E; ++I) {
 266         MachineBasicBlock *aliveBlock = MF->getBlockNumbered(*I);
 267         LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock),
 268                      ValNo);
 269         interval.addRange(LR);
 270         DEBUG(dbgs() << " +" << LR);
 271       }
 272     }
 273
 274     // Finally, this virtual register is live from the start of any killing
 275     // block to the 'use' slot of the killing instruction.
 276     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 277       MachineInstr *Kill = vi.Kills[i];
 278       SlotIndex Start = getMBBStartIdx(Kill->getParent());
 279       SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot();
 280
 281       // Create interval with one of a NEW value number.  Note that this value
 282       // number isn't actually defined by an instruction, weird huh? :)
 283       if (PHIJoin) {
 284         assert(getInstructionFromIndex(Start) == 0 &&
 285                "PHI def index points at actual instruction.");
 286         ValNo = interval.getNextValue(Start, VNInfoAllocator);
 287       }
 288       LiveRange LR(Start, killIdx, ValNo);
 289       interval.addRange(LR);
 290       DEBUG(dbgs() << " +" << LR);
 291     }
 292
 293   } else {
 294     if (MultipleDefsBySameMI(*mi, MOIdx))
 295       // Multiple defs of the same virtual register by the same instruction.
 296       // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
 297       // This is likely due to elimination of REG_SEQUENCE instructions. Return
 298       // here since there is nothing to do.
 299       return;
 300
 301     // If this is the second time we see a virtual register definition, it
 302     // must be due to phi elimination or two addr elimination.  If this is
 303     // the result of two address elimination, then the vreg is one of the
 304     // def-and-use register operand.
 305
 306     // It may also be partial redef like this:
 307     // 80  %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
 308     // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
 309     bool PartReDef = isPartialRedef(MIIdx, MO, interval);
 310     if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
 311       // If this is a two-address definition, then we have already processed
 312       // the live range.  The only problem is that we didn't realize there
 313       // are actually two values in the live interval.  Because of this we
 314       // need to take the LiveRegion that defines this register and split it
 315       // into two values.
 316       SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
 317
 318       const LiveRange *OldLR =
 319         interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
 320       VNInfo *OldValNo = OldLR->valno;
 321       SlotIndex DefIndex = OldValNo->def.getRegSlot();
 322
 323       // Delete the previous value, which should be short and continuous,
 324       // because the 2-addr copy must be in the same MBB as the redef.
 325       interval.removeRange(DefIndex, RedefIndex);
 326
 327       // The new value number (#1) is defined by the instruction we claimed
 328       // defined value #0.
 329       VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
 330
 331       // Value#0 is now defined by the 2-addr instruction.
 332       OldValNo->def = RedefIndex;
 333
 334       // Add the new live interval which replaces the range for the input copy.
 335       LiveRange LR(DefIndex, RedefIndex, ValNo);
 336       DEBUG(dbgs() << " replace range with " << LR);
 337       interval.addRange(LR);
 338
 339       // If this redefinition is dead, we need to add a dummy unit live
 340       // range covering the def slot.
 341       if (MO.isDead())
 342         interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(),
 343                                     OldValNo));
 344
 345       DEBUG(dbgs() << " RESULT: " << interval);
 346     } else if (LV->isPHIJoin(interval.reg)) {
 347       // In the case of PHI elimination, each variable definition is only
 348       // live until the end of the block.  We've already taken care of the
 349       // rest of the live range.
 350
 351       SlotIndex defIndex = MIIdx.getRegSlot();
 352       if (MO.isEarlyClobber())
 353         defIndex = MIIdx.getRegSlot(true);
 354
 355       VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
 356
 357       SlotIndex killIndex = getMBBEndIdx(mbb);
 358       LiveRange LR(defIndex, killIndex, ValNo);
 359       interval.addRange(LR);
 360       DEBUG(dbgs() << " phi-join +" << LR);
 361     } else {
 362       llvm_unreachable("Multiply defined register");
 363     }
 364   }
 365
 366   DEBUG(dbgs() << '\n');
 367 }
 368
 369 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 370                                       MachineBasicBlock::iterator MI,
 371                                       SlotIndex MIIdx,
 372                                       MachineOperand& MO,
 373                                       unsigned MOIdx) {
 374   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 375     handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
 376                              getOrCreateInterval(MO.getReg()));
 377 }
 378
 379 /// computeIntervals - computes the live intervals for virtual
 380 /// registers. for some ordering of the machine instructions [1,N] a
 381 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 382 /// which a variable is live
 383 void LiveIntervals::computeIntervals() {
 384   DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
 385                << "********** Function: " << MF->getName() << '\n');
 386
 387   RegMaskBlocks.resize(MF->getNumBlockIDs());
 388
 389   SmallVector<unsigned, 8> UndefUses;
 390   for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
 391        MBBI != E; ++MBBI) {
 392     MachineBasicBlock *MBB = MBBI;
 393     RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size();
 394
 395     if (MBB->empty())
 396       continue;
 397
 398     // Track the index of the current machine instr.
 399     SlotIndex MIIndex = getMBBStartIdx(MBB);
 400     DEBUG(dbgs() << "BB#" << MBB->getNumber()
 401           << ":\t\t# derived from " << MBB->getName() << "\n");
 402
 403     // Skip over empty initial indices.
 404     if (getInstructionFromIndex(MIIndex) == 0)
 405       MIIndex = Indexes->getNextNonNullIndex(MIIndex);
 406
 407     for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 408          MI != miEnd; ++MI) {
 409       DEBUG(dbgs() << MIIndex << "\t" << *MI);
 410       if (MI->isDebugValue())
 411         continue;
 412       assert(Indexes->getInstructionFromIndex(MIIndex) == MI &&
 413              "Lost SlotIndex synchronization");
 414
 415       // Handle defs.
 416       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 417         MachineOperand &MO = MI->getOperand(i);
 418
 419         // Collect register masks.
 420         if (MO.isRegMask()) {
 421           RegMaskSlots.push_back(MIIndex.getRegSlot());
 422           RegMaskBits.push_back(MO.getRegMask());
 423           continue;
 424         }
 425
 426         if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 427           continue;
 428
 429         // handle register defs - build intervals
 430         if (MO.isDef())
 431           handleRegisterDef(MBB, MI, MIIndex, MO, i);
 432         else if (MO.isUndef())
 433           UndefUses.push_back(MO.getReg());
 434       }
 435
 436       // Move to the next instr slot.
 437       MIIndex = Indexes->getNextNonNullIndex(MIIndex);
 438     }
 439
 440     // Compute the number of register mask instructions in this block.
 441     std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
 442     RMB.second = RegMaskSlots.size() - RMB.first;;
 443   }
 444
 445   // Create empty intervals for registers defined by implicit_def's (except
 446   // for those implicit_def that define values which are liveout of their
 447   // blocks.
 448   for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
 449     unsigned UndefReg = UndefUses[i];
 450     (void)getOrCreateInterval(UndefReg);
 451   }
 452 }
 453
 454 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
 455   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
 456   return new LiveInterval(reg, Weight);
 457 }
 458
 459
 460 /// computeVirtRegInterval - Compute the live interval of a virtual register,
 461 /// based on defs and uses.
 462 void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) {
 463   assert(LRCalc && "LRCalc not initialized.");
 464   assert(LI->empty() && "Should only compute empty intervals.");
 465   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 466   LRCalc->createDeadDefs(LI);
 467   LRCalc->extendToUses(LI);
 468 }
 469
 470 void LiveIntervals::computeVirtRegs() {
 471   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 472     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 473     if (MRI->reg_nodbg_empty(Reg))
 474       continue;
 475     LiveInterval *LI = createInterval(Reg);
 476     VirtRegIntervals[Reg] = LI;
 477     computeVirtRegInterval(LI);
 478   }
 479 }
 480
 481 void LiveIntervals::computeRegMasks() {
 482   RegMaskBlocks.resize(MF->getNumBlockIDs());
 483
 484   // Find all instructions with regmask operands.
 485   for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
 486        MBBI != E; ++MBBI) {
 487     MachineBasicBlock *MBB = MBBI;
 488     std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
 489     RMB.first = RegMaskSlots.size();
 490     for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
 491          MI != ME; ++MI)
 492       for (MIOperands MO(MI); MO.isValid(); ++MO) {
 493         if (!MO->isRegMask())
 494           continue;
 495           RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
 496           RegMaskBits.push_back(MO->getRegMask());
 497       }
 498     // Compute the number of register mask instructions in this block.
 499     RMB.second = RegMaskSlots.size() - RMB.first;;
 500   }
 501 }
 502
 503 //===----------------------------------------------------------------------===//
 504 //                           Register Unit Liveness
 505 //===----------------------------------------------------------------------===//
 506 //
 507 // Fixed interference typically comes from ABI boundaries: Function arguments
 508 // and return values are passed in fixed registers, and so are exception
 509 // pointers entering landing pads. Certain instructions require values to be
 510 // present in specific registers. That is also represented through fixed
 511 // interference.
 512 //
 513
 514 /// computeRegUnitInterval - Compute the live interval of a register unit, based
 515 /// on the uses and defs of aliasing registers.  The interval should be empty,
 516 /// or contain only dead phi-defs from ABI blocks.
 517 void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
 518   unsigned Unit = LI->reg;
 519
 520   assert(LRCalc && "LRCalc not initialized.");
 521   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 522
 523   // The physregs aliasing Unit are the roots and their super-registers.
 524   // Create all values as dead defs before extending to uses. Note that roots
 525   // may share super-registers. That's OK because createDeadDefs() is
 526   // idempotent. It is very rare for a register unit to have multiple roots, so
 527   // uniquing super-registers is probably not worthwhile.
 528   for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
 529     unsigned Root = *Roots;
 530     if (!MRI->reg_empty(Root))
 531       LRCalc->createDeadDefs(LI, Root);
 532     for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
 533       if (!MRI->reg_empty(*Supers))
 534         LRCalc->createDeadDefs(LI, *Supers);
 535     }
 536   }
 537
 538   // Now extend LI to reach all uses.
 539   // Ignore uses of reserved registers. We only track defs of those.
 540   for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
 541     unsigned Root = *Roots;
 542     if (!isReserved(Root) && !MRI->reg_empty(Root))
 543       LRCalc->extendToUses(LI, Root);
 544     for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
 545       unsigned Reg = *Supers;
 546       if (!isReserved(Reg) && !MRI->reg_empty(Reg))
 547         LRCalc->extendToUses(LI, Reg);
 548     }
 549   }
 550 }
 551
 552
 553 /// computeLiveInRegUnits - Precompute the live ranges of any register units
 554 /// that are live-in to an ABI block somewhere. Register values can appear
 555 /// without a corresponding def when entering the entry block or a landing pad.
 556 ///
 557 void LiveIntervals::computeLiveInRegUnits() {
 558   RegUnitIntervals.resize(TRI->getNumRegUnits());
 559   DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
 560
 561   // Keep track of the intervals allocated.
 562   SmallVector<LiveInterval*, 8> NewIntvs;
 563
 564   // Check all basic blocks for live-ins.
 565   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 566        MFI != MFE; ++MFI) {
 567     const MachineBasicBlock *MBB = MFI;
 568
 569     // We only care about ABI blocks: Entry + landing pads.
 570     if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
 571       continue;
 572
 573     // Create phi-defs at Begin for all live-in registers.
 574     SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
 575     DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
 576     for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
 577          LIE = MBB->livein_end(); LII != LIE; ++LII) {
 578       for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
 579         unsigned Unit = *Units;
 580         LiveInterval *Intv = RegUnitIntervals[Unit];
 581         if (!Intv) {
 582           Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF);
 583           NewIntvs.push_back(Intv);
 584         }
 585         VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
 586         (void)VNI;
 587         DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
 588       }
 589     }
 590     DEBUG(dbgs() << '\n');
 591   }
 592   DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
 593
 594   // Compute the 'normal' part of the intervals.
 595   for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
 596     computeRegUnitInterval(NewIntvs[i]);
 597 }
 598
 599
 600 /// shrinkToUses - After removing some uses of a register, shrink its live
 601 /// range to just the remaining uses. This method does not compute reaching
 602 /// defs for new uses, and it doesn't remove dead defs.
 603 bool LiveIntervals::shrinkToUses(LiveInterval *li,
 604                                  SmallVectorImpl<MachineInstr*> *dead) {
 605   DEBUG(dbgs() << "Shrink: " << *li << '\n');
 606   assert(TargetRegisterInfo::isVirtualRegister(li->reg)
 607          && "Can only shrink virtual registers");
 608   // Find all the values used, including PHI kills.
 609   SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
 610
 611   // Blocks that have already been added to WorkList as live-out.
 612   SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
 613
 614   // Visit all instructions reading li->reg.
 615   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
 616        MachineInstr *UseMI = I.skipInstruction();) {
 617     if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
 618       continue;
 619     SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
 620     LiveRangeQuery LRQ(*li, Idx);
 621     VNInfo *VNI = LRQ.valueIn();
 622     if (!VNI) {
 623       // This shouldn't happen: readsVirtualRegister returns true, but there is
 624       // no live value. It is likely caused by a target getting <undef> flags
 625       // wrong.
 626       DEBUG(dbgs() << Idx << '\t' << *UseMI
 627                    << "Warning: Instr claims to read non-existent value in "
 628                     << *li << '\n');
 629       continue;
 630     }
 631     // Special case: An early-clobber tied operand reads and writes the
 632     // register one slot early.
 633     if (VNInfo *DefVNI = LRQ.valueDefined())
 634       Idx = DefVNI->def;
 635
 636     WorkList.push_back(std::make_pair(Idx, VNI));
 637   }
 638
 639   // Create a new live interval with only minimal live segments per def.
 640   LiveInterval NewLI(li->reg, 0);
 641   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 642        I != E; ++I) {
 643     VNInfo *VNI = *I;
 644     if (VNI->isUnused())
 645       continue;
 646     NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
 647   }
 648
 649   // Keep track of the PHIs that are in use.
 650   SmallPtrSet<VNInfo*, 8> UsedPHIs;
 651
 652   // Extend intervals to reach all uses in WorkList.
 653   while (!WorkList.empty()) {
 654     SlotIndex Idx = WorkList.back().first;
 655     VNInfo *VNI = WorkList.back().second;
 656     WorkList.pop_back();
 657     const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
 658     SlotIndex BlockStart = getMBBStartIdx(MBB);
 659
 660     // Extend the live range for VNI to be live at Idx.
 661     if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
 662       (void)ExtVNI;
 663       assert(ExtVNI == VNI && "Unexpected existing value number");
 664       // Is this a PHIDef we haven't seen before?
 665       if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
 666         continue;
 667       // The PHI is live, make sure the predecessors are live-out.
 668       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 669            PE = MBB->pred_end(); PI != PE; ++PI) {
 670         if (!LiveOut.insert(*PI))
 671           continue;
 672         SlotIndex Stop = getMBBEndIdx(*PI);
 673         // A predecessor is not required to have a live-out value for a PHI.
 674         if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
 675           WorkList.push_back(std::make_pair(Stop, PVNI));
 676       }
 677       continue;
 678     }
 679
 680     // VNI is live-in to MBB.
 681     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
 682     NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
 683
 684     // Make sure VNI is live-out from the predecessors.
 685     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 686          PE = MBB->pred_end(); PI != PE; ++PI) {
 687       if (!LiveOut.insert(*PI))
 688         continue;
 689       SlotIndex Stop = getMBBEndIdx(*PI);
 690       assert(li->getVNInfoBefore(Stop) == VNI &&
 691              "Wrong value out of predecessor");
 692       WorkList.push_back(std::make_pair(Stop, VNI));
 693     }
 694   }
 695
 696   // Handle dead values.
 697   bool CanSeparate = false;
 698   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 699        I != E; ++I) {
 700     VNInfo *VNI = *I;
 701     if (VNI->isUnused())
 702       continue;
 703     LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
 704     assert(LII != NewLI.end() && "Missing live range for PHI");
 705     if (LII->end != VNI->def.getDeadSlot())
 706       continue;
 707     if (VNI->isPHIDef()) {
 708       // This is a dead PHI. Remove it.
 709       VNI->markUnused();
 710       NewLI.removeRange(*LII);
 711       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 712       CanSeparate = true;
 713     } else {
 714       // This is a dead def. Make sure the instruction knows.
 715       MachineInstr *MI = getInstructionFromIndex(VNI->def);
 716       assert(MI && "No instruction defining live value");
 717       MI->addRegisterDead(li->reg, TRI);
 718       if (dead && MI->allDefsAreDead()) {
 719         DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
 720         dead->push_back(MI);
 721       }
 722     }
 723   }
 724
 725   // Move the trimmed ranges back.
 726   li->ranges.swap(NewLI.ranges);
 727   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
 728   return CanSeparate;
 729 }
 730
 731
 732 //===----------------------------------------------------------------------===//
 733 // Register allocator hooks.
 734 //
 735
 736 void LiveIntervals::addKillFlags() {
 737   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 738     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 739     if (MRI->reg_nodbg_empty(Reg))
 740       continue;
 741     LiveInterval *LI = &getInterval(Reg);
 742
 743     // Every instruction that kills Reg corresponds to a live range end point.
 744     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
 745          ++RI) {
 746       // A block index indicates an MBB edge.
 747       if (RI->end.isBlock())
 748         continue;
 749       MachineInstr *MI = getInstructionFromIndex(RI->end);
 750       if (!MI)
 751         continue;
 752       MI->addRegisterKilled(Reg, NULL);
 753     }
 754   }
 755 }
 756
 757 MachineBasicBlock*
 758 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
 759   // A local live range must be fully contained inside the block, meaning it is
 760   // defined and killed at instructions, not at block boundaries. It is not
 761   // live in or or out of any block.
 762   //
 763   // It is technically possible to have a PHI-defined live range identical to a
 764   // single block, but we are going to return false in that case.
 765
 766   SlotIndex Start = LI.beginIndex();
 767   if (Start.isBlock())
 768     return NULL;
 769
 770   SlotIndex Stop = LI.endIndex();
 771   if (Stop.isBlock())
 772     return NULL;
 773
 774   // getMBBFromIndex doesn't need to search the MBB table when both indexes
 775   // belong to proper instructions.
 776   MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
 777   MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
 778   return MBB1 == MBB2 ? MBB1 : NULL;
 779 }
 780
 781 bool
 782 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
 783   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
 784        I != E; ++I) {
 785     const VNInfo *PHI = *I;
 786     if (PHI->isUnused() || !PHI->isPHIDef())
 787       continue;
 788     const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
 789     // Conservatively return true instead of scanning huge predecessor lists.
 790     if (PHIMBB->pred_size() > 100)
 791       return true;
 792     for (MachineBasicBlock::const_pred_iterator
 793          PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
 794       if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
 795         return true;
 796   }
 797   return false;
 798 }
 799
 800 float
 801 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
 802   // Limit the loop depth ridiculousness.
 803   if (loopDepth > 200)
 804     loopDepth = 200;
 805
 806   // The loop depth is used to roughly estimate the number of times the
 807   // instruction is executed. Something like 10^d is simple, but will quickly
 808   // overflow a float. This expression behaves like 10^d for small d, but is
 809   // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
 810   // headroom before overflow.
 811   // By the way, powf() might be unavailable here. For consistency,
 812   // We may take pow(double,double).
 813   float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
 814
 815   return (isDef + isUse) * lc;
 816 }
 817
 818 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
 819                                                   MachineInstr* startInst) {
 820   LiveInterval& Interval = getOrCreateInterval(reg);
 821   VNInfo* VN = Interval.getNextValue(
 822     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
 823     getVNInfoAllocator());
 824   LiveRange LR(
 825      SlotIndex(getInstructionIndex(startInst).getRegSlot()),
 826      getMBBEndIdx(startInst->getParent()), VN);
 827   Interval.addRange(LR);
 828
 829   return LR;
 830 }
 831
 832
 833 //===----------------------------------------------------------------------===//
 834 //                          Register mask functions
 835 //===----------------------------------------------------------------------===//
 836
 837 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
 838                                              BitVector &UsableRegs) {
 839   if (LI.empty())
 840     return false;
 841   LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
 842
 843   // Use a smaller arrays for local live ranges.
 844   ArrayRef<SlotIndex> Slots;
 845   ArrayRef<const uint32_t*> Bits;
 846   if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
 847     Slots = getRegMaskSlotsInBlock(MBB->getNumber());
 848     Bits = getRegMaskBitsInBlock(MBB->getNumber());
 849   } else {
 850     Slots = getRegMaskSlots();
 851     Bits = getRegMaskBits();
 852   }
 853
 854   // We are going to enumerate all the register mask slots contained in LI.
 855   // Start with a binary search of RegMaskSlots to find a starting point.
 856   ArrayRef<SlotIndex>::iterator SlotI =
 857     std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
 858   ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
 859
 860   // No slots in range, LI begins after the last call.
 861   if (SlotI == SlotE)
 862     return false;
 863
 864   bool Found = false;
 865   for (;;) {
 866     assert(*SlotI >= LiveI->start);
 867     // Loop over all slots overlapping this segment.
 868     while (*SlotI < LiveI->end) {
 869       // *SlotI overlaps LI. Collect mask bits.
 870       if (!Found) {
 871         // This is the first overlap. Initialize UsableRegs to all ones.
 872         UsableRegs.clear();
 873         UsableRegs.resize(TRI->getNumRegs(), true);
 874         Found = true;
 875       }
 876       // Remove usable registers clobbered by this mask.
 877       UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
 878       if (++SlotI == SlotE)
 879         return Found;
 880     }
 881     // *SlotI is beyond the current LI segment.
 882     LiveI = LI.advanceTo(LiveI, *SlotI);
 883     if (LiveI == LiveE)
 884       return Found;
 885     // Advance SlotI until it overlaps.
 886     while (*SlotI < LiveI->start)
 887       if (++SlotI == SlotE)
 888         return Found;
 889   }
 890 }
 891
 892 //===----------------------------------------------------------------------===//
 893 //                         IntervalUpdate class.
 894 //===----------------------------------------------------------------------===//
 895
 896 // HMEditor is a toolkit used by handleMove to trim or extend live intervals.
 897 class LiveIntervals::HMEditor {
 898 private:
 899   LiveIntervals& LIS;
 900   const MachineRegisterInfo& MRI;
 901   const TargetRegisterInfo& TRI;
 902   SlotIndex NewIdx;
 903
 904   typedef std::pair<LiveInterval*, LiveRange*> IntRangePair;
 905   typedef DenseSet<IntRangePair> RangeSet;
 906
 907   struct RegRanges {
 908     LiveRange* Use;
 909     LiveRange* EC;
 910     LiveRange* Dead;
 911     LiveRange* Def;
 912     RegRanges() : Use(0), EC(0), Dead(0), Def(0) {}
 913   };
 914   typedef DenseMap<unsigned, RegRanges> BundleRanges;
 915
 916 public:
 917   HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
 918            const TargetRegisterInfo& TRI, SlotIndex NewIdx)
 919     : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {}
 920
 921   // Update intervals for all operands of MI from OldIdx to NewIdx.
 922   // This assumes that MI used to be at OldIdx, and now resides at
 923   // NewIdx.
 924   void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) {
 925     assert(NewIdx != OldIdx && "No-op move? That's a bit strange.");
 926
 927     // Collect the operands.
 928     RangeSet Entering, Internal, Exiting;
 929     bool hasRegMaskOp = false;
 930     collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
 931
 932     // To keep the LiveRanges valid within an interval, move the ranges closest
 933     // to the destination first. This prevents ranges from overlapping, to that
 934     // APIs like removeRange still work.
 935     if (NewIdx < OldIdx) {
 936       moveAllEnteringFrom(OldIdx, Entering);
 937       moveAllInternalFrom(OldIdx, Internal);
 938       moveAllExitingFrom(OldIdx, Exiting);
 939     }
 940     else {
 941       moveAllExitingFrom(OldIdx, Exiting);
 942       moveAllInternalFrom(OldIdx, Internal);
 943       moveAllEnteringFrom(OldIdx, Entering);
 944     }
 945
 946     if (hasRegMaskOp)
 947       updateRegMaskSlots(OldIdx);
 948
 949 #ifndef NDEBUG
 950     LIValidator validator;
 951     validator = std::for_each(Entering.begin(), Entering.end(), validator);
 952     validator = std::for_each(Internal.begin(), Internal.end(), validator);
 953     validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
 954     assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness.");
 955 #endif
 956
 957   }
 958
 959   // Update intervals for all operands of MI to refer to BundleStart's
 960   // SlotIndex.
 961   void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) {
 962     if (MI == BundleStart)
 963       return; // Bundling instr with itself - nothing to do.
 964
 965     SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI);
 966     assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI &&
 967            "SlotIndex <-> Instruction mapping broken for MI");
 968
 969     // Collect all ranges already in the bundle.
 970     MachineBasicBlock::instr_iterator BII(BundleStart);
 971     RangeSet Entering, Internal, Exiting;
 972     bool hasRegMaskOp = false;
 973     collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
 974     assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
 975     for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) {
 976       if (&*BII == MI)
 977         continue;
 978       collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
 979       assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
 980     }
 981
 982     BundleRanges BR = createBundleRanges(Entering, Internal, Exiting);
 983
 984     Entering.clear();
 985     Internal.clear();
 986     Exiting.clear();
 987     collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
 988     assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
 989
 990     DEBUG(dbgs() << "Entering: " << Entering.size() << "\n");
 991     DEBUG(dbgs() << "Internal: " << Internal.size() << "\n");
 992     DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n");
 993
 994     moveAllEnteringFromInto(OldIdx, Entering, BR);
 995     moveAllInternalFromInto(OldIdx, Internal, BR);
 996     moveAllExitingFromInto(OldIdx, Exiting, BR);
 997
 998
 999 #ifndef NDEBUG
1000     LIValidator validator;
1001     validator = std::for_each(Entering.begin(), Entering.end(), validator);
1002     validator = std::for_each(Internal.begin(), Internal.end(), validator);
1003     validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
1004     assert(validator.rangesOk() && "moveAllOperandsInto broke liveness.");
1005 #endif
1006   }
1007
1008 private:
1009
1010 #ifndef NDEBUG
1011   class LIValidator {
1012   private:
1013     DenseSet<const LiveInterval*> Checked, Bogus;
1014   public:
1015     void operator()(const IntRangePair& P) {
1016       const LiveInterval* LI = P.first;
1017       if (Checked.count(LI))
1018         return;
1019       Checked.insert(LI);
1020       if (LI->empty())
1021         return;
1022       SlotIndex LastEnd = LI->begin()->start;
1023       for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end();
1024            LRI != LRE; ++LRI) {
1025         const LiveRange& LR = *LRI;
1026         if (LastEnd > LR.start || LR.start >= LR.end)
1027           Bogus.insert(LI);
1028         LastEnd = LR.end;
1029       }
1030     }
1031
1032     bool rangesOk() const {
1033       return Bogus.empty();
1034     }
1035   };
1036 #endif
1037
1038   // Collect IntRangePairs for all operands of MI that may need fixing.
1039   // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes'
1040   // maps).
1041   void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal,
1042                      RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) {
1043     hasRegMaskOp = false;
1044     for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
1045                                     MOE = MI->operands_end();
1046          MOI != MOE; ++MOI) {
1047       const MachineOperand& MO = *MOI;
1048
1049       if (MO.isRegMask()) {
1050         hasRegMaskOp = true;
1051         continue;
1052       }
1053
1054       if (!MO.isReg() || MO.getReg() == 0)
1055         continue;
1056
1057       unsigned Reg = MO.getReg();
1058
1059       // TODO: Currently we're skipping uses that are reserved or have no
1060       // interval, but we're not updating their kills. This should be
1061       // fixed.
1062       if (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))
1063         continue;
1064
1065       // Collect ranges for register units. These live ranges are computed on
1066       // demand, so just skip any that haven't been computed yet.
1067       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1068         for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
1069           if (LiveInterval *LI = LIS.getCachedRegUnit(*Units))
1070             collectRanges(MO, LI, Entering, Internal, Exiting, OldIdx);
1071       } else {
1072         // Collect ranges for individual virtual registers.
1073         collectRanges(MO, &LIS.getInterval(Reg),
1074                       Entering, Internal, Exiting, OldIdx);
1075       }
1076     }
1077   }
1078
1079   void collectRanges(const MachineOperand &MO, LiveInterval *LI,
1080                      RangeSet &Entering, RangeSet &Internal, RangeSet &Exiting,
1081                      SlotIndex OldIdx) {
1082     if (MO.readsReg()) {
1083       LiveRange* LR = LI->getLiveRangeContaining(OldIdx);
1084       if (LR != 0)
1085         Entering.insert(std::make_pair(LI, LR));
1086     }
1087     if (MO.isDef()) {
1088       LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot());
1089       assert(LR != 0 && "No live range for def?");
1090       if (LR->end > OldIdx.getDeadSlot())
1091         Exiting.insert(std::make_pair(LI, LR));
1092       else
1093         Internal.insert(std::make_pair(LI, LR));
1094     }
1095   }
1096
1097   BundleRanges createBundleRanges(RangeSet& Entering,
1098                                   RangeSet& Internal,
1099                                   RangeSet& Exiting) {
1100     BundleRanges BR;
1101
1102     for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1103          EI != EE; ++EI) {
1104       LiveInterval* LI = EI->first;
1105       LiveRange* LR = EI->second;
1106       BR[LI->reg].Use = LR;
1107     }
1108
1109     for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1110          II != IE; ++II) {
1111       LiveInterval* LI = II->first;
1112       LiveRange* LR = II->second;
1113       if (LR->end.isDead()) {
1114         BR[LI->reg].Dead = LR;
1115       } else {
1116         BR[LI->reg].EC = LR;
1117       }
1118     }
1119
1120     for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1121          EI != EE; ++EI) {
1122       LiveInterval* LI = EI->first;
1123       LiveRange* LR = EI->second;
1124       BR[LI->reg].Def = LR;
1125     }
1126
1127     return BR;
1128   }
1129
1130   void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) {
1131     MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx);
1132     if (!OldKillMI->killsRegister(reg))
1133       return; // Bail out if we don't have kill flags on the old register.
1134     MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx);
1135     assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
1136     assert(!NewKillMI->killsRegister(reg) &&
1137            "New kill instr is already a kill.");
1138     OldKillMI->clearRegisterKills(reg, &TRI);
1139     NewKillMI->addRegisterKilled(reg, &TRI);
1140   }
1141
1142   void updateRegMaskSlots(SlotIndex OldIdx) {
1143     SmallVectorImpl<SlotIndex>::iterator RI =
1144       std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
1145                        OldIdx);
1146     assert(*RI == OldIdx && "No RegMask at OldIdx.");
1147     *RI = NewIdx;
1148     assert(*prior(RI) < *RI && *RI < *next(RI) &&
1149            "RegSlots out of order. Did you move one call across another?");
1150   }
1151
1152   // Return the last use of reg between NewIdx and OldIdx.
1153   SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {
1154     SlotIndex LastUse = NewIdx;
1155     for (MachineRegisterInfo::use_nodbg_iterator
1156            UI = MRI.use_nodbg_begin(Reg),
1157            UE = MRI.use_nodbg_end();
1158          UI != UE; UI.skipInstruction()) {
1159       const MachineInstr* MI = &*UI;
1160       SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1161       if (InstSlot > LastUse && InstSlot < OldIdx)
1162         LastUse = InstSlot;
1163     }
1164     return LastUse;
1165   }
1166
1167   void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) {
1168     LiveInterval* LI = P.first;
1169     LiveRange* LR = P.second;
1170     bool LiveThrough = LR->end > OldIdx.getRegSlot();
1171     if (LiveThrough)
1172       return;
1173     SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
1174     if (LastUse != NewIdx)
1175       moveKillFlags(LI->reg, NewIdx, LastUse);
1176     LR->end = LastUse.getRegSlot();
1177   }
1178
1179   void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
1180     LiveInterval* LI = P.first;
1181     LiveRange* LR = P.second;
1182     // Extend the LiveRange if NewIdx is past the end.
1183     if (NewIdx > LR->end) {
1184       // Move kill flags if OldIdx was not originally the end
1185       // (otherwise LR->end points to an invalid slot).
1186       if (LR->end.getRegSlot() != OldIdx.getRegSlot()) {
1187         assert(LR->end > OldIdx && "LiveRange does not cover original slot");
1188         moveKillFlags(LI->reg, LR->end, NewIdx);
1189       }
1190       LR->end = NewIdx.getRegSlot();
1191     }
1192   }
1193
1194   void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) {
1195     bool GoingUp = NewIdx < OldIdx;
1196
1197     if (GoingUp) {
1198       for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1199            EI != EE; ++EI)
1200         moveEnteringUpFrom(OldIdx, *EI);
1201     } else {
1202       for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1203            EI != EE; ++EI)
1204         moveEnteringDownFrom(OldIdx, *EI);
1205     }
1206   }
1207
1208   void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) {
1209     LiveInterval* LI = P.first;
1210     LiveRange* LR = P.second;
1211     assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
1212            LR->end <= OldIdx.getDeadSlot() &&
1213            "Range should be internal to OldIdx.");
1214     LiveRange Tmp(*LR);
1215     Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber());
1216     Tmp.valno->def = Tmp.start;
1217     Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot();
1218     LI->removeRange(*LR);
1219     LI->addRange(Tmp);
1220   }
1221
1222   void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) {
1223     for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1224          II != IE; ++II)
1225       moveInternalFrom(OldIdx, *II);
1226   }
1227
1228   void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) {
1229     LiveRange* LR = P.second;
1230     assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
1231            "Range should start in OldIdx.");
1232     assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx.");
1233     SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber());
1234     LR->start = NewStart;
1235     LR->valno->def = NewStart;
1236   }
1237
1238   void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) {
1239     for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1240          EI != EE; ++EI)
1241       moveExitingFrom(OldIdx, *EI);
1242   }
1243
1244   void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P,
1245                               BundleRanges& BR) {
1246     LiveInterval* LI = P.first;
1247     LiveRange* LR = P.second;
1248     bool LiveThrough = LR->end > OldIdx.getRegSlot();
1249     if (LiveThrough) {
1250       assert((LR->start < NewIdx || BR[LI->reg].Def == LR) &&
1251              "Def in bundle should be def range.");
1252       assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
1253              "If bundle has use for this reg it should be LR.");
1254       BR[LI->reg].Use = LR;
1255       return;
1256     }
1257
1258     SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
1259     moveKillFlags(LI->reg, OldIdx, LastUse);
1260
1261     if (LR->start < NewIdx) {
1262       // Becoming a new entering range.
1263       assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 &&
1264              "Bundle shouldn't be re-defining reg mid-range.");
1265       assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
1266              "Bundle shouldn't have different use range for same reg.");
1267       LR->end = LastUse.getRegSlot();
1268       BR[LI->reg].Use = LR;
1269     } else {
1270       // Becoming a new Dead-def.
1271       assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) &&
1272              "Live range starting at unexpected slot.");
1273       assert(BR[LI->reg].Def == LR && "Reg should have def range.");
1274       assert(BR[LI->reg].Dead == 0 &&
1275                "Can't have def and dead def of same reg in a bundle.");
1276       LR->end = LastUse.getDeadSlot();
1277       BR[LI->reg].Dead = BR[LI->reg].Def;
1278       BR[LI->reg].Def = 0;
1279     }
1280   }
1281
1282   void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P,
1283                                 BundleRanges& BR) {
1284     LiveInterval* LI = P.first;
1285     LiveRange* LR = P.second;
1286     if (NewIdx > LR->end) {
1287       // Range extended to bundle. Add to bundle uses.
1288       // Note: Currently adds kill flags to bundle start.
1289       assert(BR[LI->reg].Use == 0 &&
1290              "Bundle already has use range for reg.");
1291       moveKillFlags(LI->reg, LR->end, NewIdx);
1292       LR->end = NewIdx.getRegSlot();
1293       BR[LI->reg].Use = LR;
1294     } else {
1295       assert(BR[LI->reg].Use != 0 &&
1296              "Bundle should already have a use range for reg.");
1297     }
1298   }
1299
1300   void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering,
1301                                BundleRanges& BR) {
1302     bool GoingUp = NewIdx < OldIdx;
1303
1304     if (GoingUp) {
1305       for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1306            EI != EE; ++EI)
1307         moveEnteringUpFromInto(OldIdx, *EI, BR);
1308     } else {
1309       for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1310            EI != EE; ++EI)
1311         moveEnteringDownFromInto(OldIdx, *EI, BR);
1312     }
1313   }
1314
1315   void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P,
1316                             BundleRanges& BR) {
1317     // TODO: Sane rules for moving ranges into bundles.
1318   }
1319
1320   void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal,
1321                                BundleRanges& BR) {
1322     for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1323          II != IE; ++II)
1324       moveInternalFromInto(OldIdx, *II, BR);
1325   }
1326
1327   void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P,
1328                            BundleRanges& BR) {
1329     LiveInterval* LI = P.first;
1330     LiveRange* LR = P.second;
1331
1332     assert(LR->start.isRegister() &&
1333            "Don't know how to merge exiting ECs into bundles yet.");
1334
1335     if (LR->end > NewIdx.getDeadSlot()) {
1336       // This range is becoming an exiting range on the bundle.
1337       // If there was an old dead-def of this reg, delete it.
1338       if (BR[LI->reg].Dead != 0) {
1339         LI->removeRange(*BR[LI->reg].Dead);
1340         BR[LI->reg].Dead = 0;
1341       }
1342       assert(BR[LI->reg].Def == 0 &&
1343              "Can't have two defs for the same variable exiting a bundle.");
1344       LR->start = NewIdx.getRegSlot();
1345       LR->valno->def = LR->start;
1346       BR[LI->reg].Def = LR;
1347     } else {
1348       // This range is becoming internal to the bundle.
1349       assert(LR->end == NewIdx.getRegSlot() &&
1350              "Can't bundle def whose kill is before the bundle");
1351       if (BR[LI->reg].Dead || BR[LI->reg].Def) {
1352         // Already have a def for this. Just delete range.
1353         LI->removeRange(*LR);
1354       } else {
1355         // Make range dead, record.
1356         LR->end = NewIdx.getDeadSlot();
1357         BR[LI->reg].Dead = LR;
1358         assert(BR[LI->reg].Use == LR &&
1359                "Range becoming dead should currently be use.");
1360       }
1361       // In both cases the range is no longer a use on the bundle.
1362       BR[LI->reg].Use = 0;
1363     }
1364   }
1365
1366   void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting,
1367                               BundleRanges& BR) {
1368     for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1369          EI != EE; ++EI)
1370       moveExitingFromInto(OldIdx, *EI, BR);
1371   }
1372
1373 };
1374
1375 void LiveIntervals::handleMove(MachineInstr* MI) {
1376   SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1377   Indexes->removeMachineInstrFromMaps(MI);
1378   SlotIndex NewIndex = MI->isInsideBundle() ?
1379                         Indexes->getInstructionIndex(MI) :
1380                         Indexes->insertMachineInstrInMaps(MI);
1381   assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
1382          OldIndex < getMBBEndIdx(MI->getParent()) &&
1383          "Cannot handle moves across basic block boundaries.");
1384   assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
1385
1386   HMEditor HME(*this, *MRI, *TRI, NewIndex);
1387   HME.moveAllRangesFrom(MI, OldIndex);
1388 }
1389
1390 void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
1391                                          MachineInstr* BundleStart) {
1392   SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1393   HMEditor HME(*this, *MRI, *TRI, NewIndex);
1394   HME.moveAllRangesInto(MI, BundleStart);
1395 }