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 "LiveRangeCalc.h"
  21 #include "llvm/ADT/DenseSet.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/Analysis/AliasAnalysis.h"
  24 #include "llvm/CodeGen/LiveVariables.h"
  25 #include "llvm/CodeGen/MachineDominators.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/CodeGen/Passes.h"
  29 #include "llvm/CodeGen/VirtRegMap.h"
  30 #include "llvm/IR/Value.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include "llvm/Target/TargetInstrInfo.h"
  36 #include "llvm/Target/TargetMachine.h"
  37 #include "llvm/Target/TargetRegisterInfo.h"
  38 #include <algorithm>
  39 #include <cmath>
  40 #include <limits>
  41 using namespace llvm;
  42
  43 char LiveIntervals::ID = 0;
  44 char &llvm::LiveIntervalsID = LiveIntervals::ID;
  45 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
  46                 "Live Interval Analysis", false, false)
  47 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  48 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
  49 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  50 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  51 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
  52                 "Live Interval Analysis", false, false)
  53
  54 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  55   AU.setPreservesCFG();
  56   AU.addRequired<AliasAnalysis>();
  57   AU.addPreserved<AliasAnalysis>();
  58   // LiveVariables isn't really required by this analysis, it is only required
  59   // here to make sure it is live during TwoAddressInstructionPass and
  60   // PHIElimination. This is temporary.
  61   AU.addRequired<LiveVariables>();
  62   AU.addPreserved<LiveVariables>();
  63   AU.addPreservedID(MachineLoopInfoID);
  64   AU.addRequiredTransitiveID(MachineDominatorsID);
  65   AU.addPreservedID(MachineDominatorsID);
  66   AU.addPreserved<SlotIndexes>();
  67   AU.addRequiredTransitive<SlotIndexes>();
  68   MachineFunctionPass::getAnalysisUsage(AU);
  69 }
  70
  71 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
  72   DomTree(0), LRCalc(0) {
  73   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
  74 }
  75
  76 LiveIntervals::~LiveIntervals() {
  77   delete LRCalc;
  78 }
  79
  80 void LiveIntervals::releaseMemory() {
  81   // Free the live intervals themselves.
  82   for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
  83     delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
  84   VirtRegIntervals.clear();
  85   RegMaskSlots.clear();
  86   RegMaskBits.clear();
  87   RegMaskBlocks.clear();
  88
  89   for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
  90     delete RegUnitIntervals[i];
  91   RegUnitIntervals.clear();
  92
  93   // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
  94   VNInfoAllocator.Reset();
  95 }
  96
  97 /// runOnMachineFunction - Register allocate the whole function
  98 ///
  99 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 100   MF = &fn;
 101   MRI = &MF->getRegInfo();
 102   TM = &fn.getTarget();
 103   TRI = TM->getRegisterInfo();
 104   TII = TM->getInstrInfo();
 105   AA = &getAnalysis<AliasAnalysis>();
 106   Indexes = &getAnalysis<SlotIndexes>();
 107   DomTree = &getAnalysis<MachineDominatorTree>();
 108   if (!LRCalc)
 109     LRCalc = new LiveRangeCalc();
 110
 111   // Allocate space for all virtual registers.
 112   VirtRegIntervals.resize(MRI->getNumVirtRegs());
 113
 114   computeVirtRegs();
 115   computeRegMasks();
 116   computeLiveInRegUnits();
 117
 118   DEBUG(dump());
 119   return true;
 120 }
 121
 122 /// print - Implement the dump method.
 123 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
 124   OS << "********** INTERVALS **********\n";
 125
 126   // Dump the regunits.
 127   for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
 128     if (LiveInterval *LI = RegUnitIntervals[i])
 129       OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
 130
 131   // Dump the virtregs.
 132   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 133     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 134     if (hasInterval(Reg))
 135       OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
 136   }
 137
 138   OS << "RegMasks:";
 139   for (unsigned i = 0, e = RegMaskSlots.size(); i != e; ++i)
 140     OS << ' ' << RegMaskSlots[i];
 141   OS << '\n';
 142
 143   printInstrs(OS);
 144 }
 145
 146 void LiveIntervals::printInstrs(raw_ostream &OS) const {
 147   OS << "********** MACHINEINSTRS **********\n";
 148   MF->print(OS, Indexes);
 149 }
 150
 151 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 152 void LiveIntervals::dumpInstrs() const {
 153   printInstrs(dbgs());
 154 }
 155 #endif
 156
 157 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
 158   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
 159   return new LiveInterval(reg, Weight);
 160 }
 161
 162
 163 /// computeVirtRegInterval - Compute the live interval of a virtual register,
 164 /// based on defs and uses.
 165 void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) {
 166   assert(LRCalc && "LRCalc not initialized.");
 167   assert(LI->empty() && "Should only compute empty intervals.");
 168   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 169   LRCalc->createDeadDefs(LI);
 170   LRCalc->extendToUses(LI);
 171 }
 172
 173 void LiveIntervals::computeVirtRegs() {
 174   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 175     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 176     if (MRI->reg_nodbg_empty(Reg))
 177       continue;
 178     LiveInterval *LI = createInterval(Reg);
 179     VirtRegIntervals[Reg] = LI;
 180     computeVirtRegInterval(LI);
 181   }
 182 }
 183
 184 void LiveIntervals::computeRegMasks() {
 185   RegMaskBlocks.resize(MF->getNumBlockIDs());
 186
 187   // Find all instructions with regmask operands.
 188   for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
 189        MBBI != E; ++MBBI) {
 190     MachineBasicBlock *MBB = MBBI;
 191     std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
 192     RMB.first = RegMaskSlots.size();
 193     for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
 194          MI != ME; ++MI)
 195       for (MIOperands MO(MI); MO.isValid(); ++MO) {
 196         if (!MO->isRegMask())
 197           continue;
 198           RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
 199           RegMaskBits.push_back(MO->getRegMask());
 200       }
 201     // Compute the number of register mask instructions in this block.
 202     RMB.second = RegMaskSlots.size() - RMB.first;
 203   }
 204 }
 205
 206 //===----------------------------------------------------------------------===//
 207 //                           Register Unit Liveness
 208 //===----------------------------------------------------------------------===//
 209 //
 210 // Fixed interference typically comes from ABI boundaries: Function arguments
 211 // and return values are passed in fixed registers, and so are exception
 212 // pointers entering landing pads. Certain instructions require values to be
 213 // present in specific registers. That is also represented through fixed
 214 // interference.
 215 //
 216
 217 /// computeRegUnitInterval - Compute the live interval of a register unit, based
 218 /// on the uses and defs of aliasing registers.  The interval should be empty,
 219 /// or contain only dead phi-defs from ABI blocks.
 220 void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
 221   unsigned Unit = LI->reg;
 222
 223   assert(LRCalc && "LRCalc not initialized.");
 224   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 225
 226   // The physregs aliasing Unit are the roots and their super-registers.
 227   // Create all values as dead defs before extending to uses. Note that roots
 228   // may share super-registers. That's OK because createDeadDefs() is
 229   // idempotent. It is very rare for a register unit to have multiple roots, so
 230   // uniquing super-registers is probably not worthwhile.
 231   for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
 232     for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
 233          Supers.isValid(); ++Supers) {
 234       if (!MRI->reg_empty(*Supers))
 235         LRCalc->createDeadDefs(LI, *Supers);
 236     }
 237   }
 238
 239   // Now extend LI to reach all uses.
 240   // Ignore uses of reserved registers. We only track defs of those.
 241   for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
 242     for (MCSuperRegIterator Supers(*Roots, TRI, /*IncludeSelf=*/true);
 243          Supers.isValid(); ++Supers) {
 244       unsigned Reg = *Supers;
 245       if (!MRI->isReserved(Reg) && !MRI->reg_empty(Reg))
 246         LRCalc->extendToUses(LI, Reg);
 247     }
 248   }
 249 }
 250
 251
 252 /// computeLiveInRegUnits - Precompute the live ranges of any register units
 253 /// that are live-in to an ABI block somewhere. Register values can appear
 254 /// without a corresponding def when entering the entry block or a landing pad.
 255 ///
 256 void LiveIntervals::computeLiveInRegUnits() {
 257   RegUnitIntervals.resize(TRI->getNumRegUnits());
 258   DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
 259
 260   // Keep track of the intervals allocated.
 261   SmallVector<LiveInterval*, 8> NewIntvs;
 262
 263   // Check all basic blocks for live-ins.
 264   for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
 265        MFI != MFE; ++MFI) {
 266     const MachineBasicBlock *MBB = MFI;
 267
 268     // We only care about ABI blocks: Entry + landing pads.
 269     if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
 270       continue;
 271
 272     // Create phi-defs at Begin for all live-in registers.
 273     SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
 274     DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
 275     for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
 276          LIE = MBB->livein_end(); LII != LIE; ++LII) {
 277       for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
 278         unsigned Unit = *Units;
 279         LiveInterval *Intv = RegUnitIntervals[Unit];
 280         if (!Intv) {
 281           Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF);
 282           NewIntvs.push_back(Intv);
 283         }
 284         VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
 285         (void)VNI;
 286         DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
 287       }
 288     }
 289     DEBUG(dbgs() << '\n');
 290   }
 291   DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
 292
 293   // Compute the 'normal' part of the intervals.
 294   for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
 295     computeRegUnitInterval(NewIntvs[i]);
 296 }
 297
 298
 299 /// shrinkToUses - After removing some uses of a register, shrink its live
 300 /// range to just the remaining uses. This method does not compute reaching
 301 /// defs for new uses, and it doesn't remove dead defs.
 302 bool LiveIntervals::shrinkToUses(LiveInterval *li,
 303                                  SmallVectorImpl<MachineInstr*> *dead) {
 304   DEBUG(dbgs() << "Shrink: " << *li << '\n');
 305   assert(TargetRegisterInfo::isVirtualRegister(li->reg)
 306          && "Can only shrink virtual registers");
 307   // Find all the values used, including PHI kills.
 308   SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
 309
 310   // Blocks that have already been added to WorkList as live-out.
 311   SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
 312
 313   // Visit all instructions reading li->reg.
 314   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
 315        MachineInstr *UseMI = I.skipInstruction();) {
 316     if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
 317       continue;
 318     SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
 319     LiveRangeQuery LRQ(*li, Idx);
 320     VNInfo *VNI = LRQ.valueIn();
 321     if (!VNI) {
 322       // This shouldn't happen: readsVirtualRegister returns true, but there is
 323       // no live value. It is likely caused by a target getting <undef> flags
 324       // wrong.
 325       DEBUG(dbgs() << Idx << '\t' << *UseMI
 326                    << "Warning: Instr claims to read non-existent value in "
 327                     << *li << '\n');
 328       continue;
 329     }
 330     // Special case: An early-clobber tied operand reads and writes the
 331     // register one slot early.
 332     if (VNInfo *DefVNI = LRQ.valueDefined())
 333       Idx = DefVNI->def;
 334
 335     WorkList.push_back(std::make_pair(Idx, VNI));
 336   }
 337
 338   // Create a new live interval with only minimal live segments per def.
 339   LiveInterval NewLI(li->reg, 0);
 340   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 341        I != E; ++I) {
 342     VNInfo *VNI = *I;
 343     if (VNI->isUnused())
 344       continue;
 345     NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
 346   }
 347
 348   // Keep track of the PHIs that are in use.
 349   SmallPtrSet<VNInfo*, 8> UsedPHIs;
 350
 351   // Extend intervals to reach all uses in WorkList.
 352   while (!WorkList.empty()) {
 353     SlotIndex Idx = WorkList.back().first;
 354     VNInfo *VNI = WorkList.back().second;
 355     WorkList.pop_back();
 356     const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
 357     SlotIndex BlockStart = getMBBStartIdx(MBB);
 358
 359     // Extend the live range for VNI to be live at Idx.
 360     if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
 361       (void)ExtVNI;
 362       assert(ExtVNI == VNI && "Unexpected existing value number");
 363       // Is this a PHIDef we haven't seen before?
 364       if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
 365         continue;
 366       // The PHI is live, make sure the predecessors are live-out.
 367       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 368            PE = MBB->pred_end(); PI != PE; ++PI) {
 369         if (!LiveOut.insert(*PI))
 370           continue;
 371         SlotIndex Stop = getMBBEndIdx(*PI);
 372         // A predecessor is not required to have a live-out value for a PHI.
 373         if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
 374           WorkList.push_back(std::make_pair(Stop, PVNI));
 375       }
 376       continue;
 377     }
 378
 379     // VNI is live-in to MBB.
 380     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
 381     NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
 382
 383     // Make sure VNI is live-out from the predecessors.
 384     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 385          PE = MBB->pred_end(); PI != PE; ++PI) {
 386       if (!LiveOut.insert(*PI))
 387         continue;
 388       SlotIndex Stop = getMBBEndIdx(*PI);
 389       assert(li->getVNInfoBefore(Stop) == VNI &&
 390              "Wrong value out of predecessor");
 391       WorkList.push_back(std::make_pair(Stop, VNI));
 392     }
 393   }
 394
 395   // Handle dead values.
 396   bool CanSeparate = false;
 397   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 398        I != E; ++I) {
 399     VNInfo *VNI = *I;
 400     if (VNI->isUnused())
 401       continue;
 402     LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
 403     assert(LII != NewLI.end() && "Missing live range for PHI");
 404     if (LII->end != VNI->def.getDeadSlot())
 405       continue;
 406     if (VNI->isPHIDef()) {
 407       // This is a dead PHI. Remove it.
 408       VNI->markUnused();
 409       NewLI.removeRange(*LII);
 410       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 411       CanSeparate = true;
 412     } else {
 413       // This is a dead def. Make sure the instruction knows.
 414       MachineInstr *MI = getInstructionFromIndex(VNI->def);
 415       assert(MI && "No instruction defining live value");
 416       MI->addRegisterDead(li->reg, TRI);
 417       if (dead && MI->allDefsAreDead()) {
 418         DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
 419         dead->push_back(MI);
 420       }
 421     }
 422   }
 423
 424   // Move the trimmed ranges back.
 425   li->ranges.swap(NewLI.ranges);
 426   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
 427   return CanSeparate;
 428 }
 429
 430 void LiveIntervals::extendToIndices(LiveInterval *LI,
 431                                     ArrayRef<SlotIndex> Indices) {
 432   assert(LRCalc && "LRCalc not initialized.");
 433   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
 434   for (unsigned i = 0, e = Indices.size(); i != e; ++i)
 435     LRCalc->extend(LI, Indices[i]);
 436 }
 437
 438 void LiveIntervals::pruneValue(LiveInterval *LI, SlotIndex Kill,
 439                                SmallVectorImpl<SlotIndex> *EndPoints) {
 440   LiveRangeQuery LRQ(*LI, Kill);
 441   VNInfo *VNI = LRQ.valueOut();
 442   if (!VNI)
 443     return;
 444
 445   MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
 446   SlotIndex MBBStart, MBBEnd;
 447   tie(MBBStart, MBBEnd) = Indexes->getMBBRange(KillMBB);
 448
 449   // If VNI isn't live out from KillMBB, the value is trivially pruned.
 450   if (LRQ.endPoint() < MBBEnd) {
 451     LI->removeRange(Kill, LRQ.endPoint());
 452     if (EndPoints) EndPoints->push_back(LRQ.endPoint());
 453     return;
 454   }
 455
 456   // VNI is live out of KillMBB.
 457   LI->removeRange(Kill, MBBEnd);
 458   if (EndPoints) EndPoints->push_back(MBBEnd);
 459
 460   // Find all blocks that are reachable from KillMBB without leaving VNI's live
 461   // range. It is possible that KillMBB itself is reachable, so start a DFS
 462   // from each successor.
 463   typedef SmallPtrSet<MachineBasicBlock*, 9> VisitedTy;
 464   VisitedTy Visited;
 465   for (MachineBasicBlock::succ_iterator
 466        SuccI = KillMBB->succ_begin(), SuccE = KillMBB->succ_end();
 467        SuccI != SuccE; ++SuccI) {
 468     for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
 469          I = df_ext_begin(*SuccI, Visited), E = df_ext_end(*SuccI, Visited);
 470          I != E;) {
 471       MachineBasicBlock *MBB = *I;
 472
 473       // Check if VNI is live in to MBB.
 474       tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
 475       LiveRangeQuery LRQ(*LI, MBBStart);
 476       if (LRQ.valueIn() != VNI) {
 477         // This block isn't part of the VNI live range. Prune the search.
 478         I.skipChildren();
 479         continue;
 480       }
 481
 482       // Prune the search if VNI is killed in MBB.
 483       if (LRQ.endPoint() < MBBEnd) {
 484         LI->removeRange(MBBStart, LRQ.endPoint());
 485         if (EndPoints) EndPoints->push_back(LRQ.endPoint());
 486         I.skipChildren();
 487         continue;
 488       }
 489
 490       // VNI is live through MBB.
 491       LI->removeRange(MBBStart, MBBEnd);
 492       if (EndPoints) EndPoints->push_back(MBBEnd);
 493       ++I;
 494     }
 495   }
 496 }
 497
 498 //===----------------------------------------------------------------------===//
 499 // Register allocator hooks.
 500 //
 501
 502 void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
 503   // Keep track of regunit ranges.
 504   SmallVector<std::pair<LiveInterval*, LiveInterval::iterator>, 8> RU;
 505
 506   for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
 507     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 508     if (MRI->reg_nodbg_empty(Reg))
 509       continue;
 510     LiveInterval *LI = &getInterval(Reg);
 511     if (LI->empty())
 512       continue;
 513
 514     // Find the regunit intervals for the assigned register. They may overlap
 515     // the virtual register live range, cancelling any kills.
 516     RU.clear();
 517     for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
 518          ++Units) {
 519       LiveInterval *RUInt = &getRegUnit(*Units);
 520       if (RUInt->empty())
 521         continue;
 522       RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end)));
 523     }
 524
 525     // Every instruction that kills Reg corresponds to a live range end point.
 526     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
 527          ++RI) {
 528       // A block index indicates an MBB edge.
 529       if (RI->end.isBlock())
 530         continue;
 531       MachineInstr *MI = getInstructionFromIndex(RI->end);
 532       if (!MI)
 533         continue;
 534
 535       // Check if any of the reguints are live beyond the end of RI. That could
 536       // happen when a physreg is defined as a copy of a virtreg:
 537       //
 538       //   %EAX = COPY %vreg5
 539       //   FOO %vreg5         <--- MI, cancel kill because %EAX is live.
 540       //   BAR %EAX<kill>
 541       //
 542       // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
 543       bool CancelKill = false;
 544       for (unsigned u = 0, e = RU.size(); u != e; ++u) {
 545         LiveInterval *RInt = RU[u].first;
 546         LiveInterval::iterator &I = RU[u].second;
 547         if (I == RInt->end())
 548           continue;
 549         I = RInt->advanceTo(I, RI->end);
 550         if (I == RInt->end() || I->start >= RI->end)
 551           continue;
 552         // I is overlapping RI.
 553         CancelKill = true;
 554         break;
 555       }
 556       if (CancelKill)
 557         MI->clearRegisterKills(Reg, NULL);
 558       else
 559         MI->addRegisterKilled(Reg, NULL);
 560     }
 561   }
 562 }
 563
 564 MachineBasicBlock*
 565 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
 566   // A local live range must be fully contained inside the block, meaning it is
 567   // defined and killed at instructions, not at block boundaries. It is not
 568   // live in or or out of any block.
 569   //
 570   // It is technically possible to have a PHI-defined live range identical to a
 571   // single block, but we are going to return false in that case.
 572
 573   SlotIndex Start = LI.beginIndex();
 574   if (Start.isBlock())
 575     return NULL;
 576
 577   SlotIndex Stop = LI.endIndex();
 578   if (Stop.isBlock())
 579     return NULL;
 580
 581   // getMBBFromIndex doesn't need to search the MBB table when both indexes
 582   // belong to proper instructions.
 583   MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
 584   MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
 585   return MBB1 == MBB2 ? MBB1 : NULL;
 586 }
 587
 588 bool
 589 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
 590   for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
 591        I != E; ++I) {
 592     const VNInfo *PHI = *I;
 593     if (PHI->isUnused() || !PHI->isPHIDef())
 594       continue;
 595     const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
 596     // Conservatively return true instead of scanning huge predecessor lists.
 597     if (PHIMBB->pred_size() > 100)
 598       return true;
 599     for (MachineBasicBlock::const_pred_iterator
 600          PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
 601       if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
 602         return true;
 603   }
 604   return false;
 605 }
 606
 607 float
 608 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
 609   // Limit the loop depth ridiculousness.
 610   if (loopDepth > 200)
 611     loopDepth = 200;
 612
 613   // The loop depth is used to roughly estimate the number of times the
 614   // instruction is executed. Something like 10^d is simple, but will quickly
 615   // overflow a float. This expression behaves like 10^d for small d, but is
 616   // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
 617   // headroom before overflow.
 618   // By the way, powf() might be unavailable here. For consistency,
 619   // We may take pow(double,double).
 620   float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
 621
 622   return (isDef + isUse) * lc;
 623 }
 624
 625 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
 626                                                   MachineInstr* startInst) {
 627   LiveInterval& Interval = getOrCreateInterval(reg);
 628   VNInfo* VN = Interval.getNextValue(
 629     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
 630     getVNInfoAllocator());
 631   LiveRange LR(
 632      SlotIndex(getInstructionIndex(startInst).getRegSlot()),
 633      getMBBEndIdx(startInst->getParent()), VN);
 634   Interval.addRange(LR);
 635
 636   return LR;
 637 }
 638
 639
 640 //===----------------------------------------------------------------------===//
 641 //                          Register mask functions
 642 //===----------------------------------------------------------------------===//
 643
 644 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
 645                                              BitVector &UsableRegs) {
 646   if (LI.empty())
 647     return false;
 648   LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
 649
 650   // Use a smaller arrays for local live ranges.
 651   ArrayRef<SlotIndex> Slots;
 652   ArrayRef<const uint32_t*> Bits;
 653   if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
 654     Slots = getRegMaskSlotsInBlock(MBB->getNumber());
 655     Bits = getRegMaskBitsInBlock(MBB->getNumber());
 656   } else {
 657     Slots = getRegMaskSlots();
 658     Bits = getRegMaskBits();
 659   }
 660
 661   // We are going to enumerate all the register mask slots contained in LI.
 662   // Start with a binary search of RegMaskSlots to find a starting point.
 663   ArrayRef<SlotIndex>::iterator SlotI =
 664     std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
 665   ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
 666
 667   // No slots in range, LI begins after the last call.
 668   if (SlotI == SlotE)
 669     return false;
 670
 671   bool Found = false;
 672   for (;;) {
 673     assert(*SlotI >= LiveI->start);
 674     // Loop over all slots overlapping this segment.
 675     while (*SlotI < LiveI->end) {
 676       // *SlotI overlaps LI. Collect mask bits.
 677       if (!Found) {
 678         // This is the first overlap. Initialize UsableRegs to all ones.
 679         UsableRegs.clear();
 680         UsableRegs.resize(TRI->getNumRegs(), true);
 681         Found = true;
 682       }
 683       // Remove usable registers clobbered by this mask.
 684       UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
 685       if (++SlotI == SlotE)
 686         return Found;
 687     }
 688     // *SlotI is beyond the current LI segment.
 689     LiveI = LI.advanceTo(LiveI, *SlotI);
 690     if (LiveI == LiveE)
 691       return Found;
 692     // Advance SlotI until it overlaps.
 693     while (*SlotI < LiveI->start)
 694       if (++SlotI == SlotE)
 695         return Found;
 696   }
 697 }
 698
 699 //===----------------------------------------------------------------------===//
 700 //                         IntervalUpdate class.
 701 //===----------------------------------------------------------------------===//
 702
 703 // HMEditor is a toolkit used by handleMove to trim or extend live intervals.
 704 class LiveIntervals::HMEditor {
 705 private:
 706   LiveIntervals& LIS;
 707   const MachineRegisterInfo& MRI;
 708   const TargetRegisterInfo& TRI;
 709   SlotIndex OldIdx;
 710   SlotIndex NewIdx;
 711   SmallPtrSet<LiveInterval*, 8> Updated;
 712   bool UpdateFlags;
 713
 714 public:
 715   HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
 716            const TargetRegisterInfo& TRI,
 717            SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
 718     : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
 719       UpdateFlags(UpdateFlags) {}
 720
 721   // FIXME: UpdateFlags is a workaround that creates live intervals for all
 722   // physregs, even those that aren't needed for regalloc, in order to update
 723   // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
 724   // flags, and postRA passes will use a live register utility instead.
 725   LiveInterval *getRegUnitLI(unsigned Unit) {
 726     if (UpdateFlags)
 727       return &LIS.getRegUnit(Unit);
 728     return LIS.getCachedRegUnit(Unit);
 729   }
 730
 731   /// Update all live ranges touched by MI, assuming a move from OldIdx to
 732   /// NewIdx.
 733   void updateAllRanges(MachineInstr *MI) {
 734     DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
 735     bool hasRegMask = false;
 736     for (MIOperands MO(MI); MO.isValid(); ++MO) {
 737       if (MO->isRegMask())
 738         hasRegMask = true;
 739       if (!MO->isReg())
 740         continue;
 741       // Aggressively clear all kill flags.
 742       // They are reinserted by VirtRegRewriter.
 743       if (MO->isUse())
 744         MO->setIsKill(false);
 745
 746       unsigned Reg = MO->getReg();
 747       if (!Reg)
 748         continue;
 749       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 750         updateRange(LIS.getInterval(Reg));
 751         continue;
 752       }
 753
 754       // For physregs, only update the regunits that actually have a
 755       // precomputed live range.
 756       for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
 757         if (LiveInterval *LI = getRegUnitLI(*Units))
 758           updateRange(*LI);
 759     }
 760     if (hasRegMask)
 761       updateRegMaskSlots();
 762   }
 763
 764 private:
 765   /// Update a single live range, assuming an instruction has been moved from
 766   /// OldIdx to NewIdx.
 767   void updateRange(LiveInterval &LI) {
 768     if (!Updated.insert(&LI))
 769       return;
 770     DEBUG({
 771       dbgs() << "     ";
 772       if (TargetRegisterInfo::isVirtualRegister(LI.reg))
 773         dbgs() << PrintReg(LI.reg);
 774       else
 775         dbgs() << PrintRegUnit(LI.reg, &TRI);
 776       dbgs() << ":\t" << LI << '\n';
 777     });
 778     if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
 779       handleMoveDown(LI);
 780     else
 781       handleMoveUp(LI);
 782     DEBUG(dbgs() << "        -->\t" << LI << '\n');
 783     LI.verify();
 784   }
 785
 786   /// Update LI to reflect an instruction has been moved downwards from OldIdx
 787   /// to NewIdx.
 788   ///
 789   /// 1. Live def at OldIdx:
 790   ///    Move def to NewIdx, assert endpoint after NewIdx.
 791   ///
 792   /// 2. Live def at OldIdx, killed at NewIdx:
 793   ///    Change to dead def at NewIdx.
 794   ///    (Happens when bundling def+kill together).
 795   ///
 796   /// 3. Dead def at OldIdx:
 797   ///    Move def to NewIdx, possibly across another live value.
 798   ///
 799   /// 4. Def at OldIdx AND at NewIdx:
 800   ///    Remove live range [OldIdx;NewIdx) and value defined at OldIdx.
 801   ///    (Happens when bundling multiple defs together).
 802   ///
 803   /// 5. Value read at OldIdx, killed before NewIdx:
 804   ///    Extend kill to NewIdx.
 805   ///
 806   void handleMoveDown(LiveInterval &LI) {
 807     // First look for a kill at OldIdx.
 808     LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
 809     LiveInterval::iterator E = LI.end();
 810     // Is LI even live at OldIdx?
 811     if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
 812       return;
 813
 814     // Handle a live-in value.
 815     if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
 816       bool isKill = SlotIndex::isSameInstr(OldIdx, I->end);
 817       // If the live-in value already extends to NewIdx, there is nothing to do.
 818       if (!SlotIndex::isEarlierInstr(I->end, NewIdx))
 819         return;
 820       // Aggressively remove all kill flags from the old kill point.
 821       // Kill flags shouldn't be used while live intervals exist, they will be
 822       // reinserted by VirtRegRewriter.
 823       if (MachineInstr *KillMI = LIS.getInstructionFromIndex(I->end))
 824         for (MIBundleOperands MO(KillMI); MO.isValid(); ++MO)
 825           if (MO->isReg() && MO->isUse())
 826             MO->setIsKill(false);
 827       // Adjust I->end to reach NewIdx. This may temporarily make LI invalid by
 828       // overlapping ranges. Case 5 above.
 829       I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
 830       // If this was a kill, there may also be a def. Otherwise we're done.
 831       if (!isKill)
 832         return;
 833       ++I;
 834     }
 835
 836     // Check for a def at OldIdx.
 837     if (I == E || !SlotIndex::isSameInstr(OldIdx, I->start))
 838       return;
 839     // We have a def at OldIdx.
 840     VNInfo *DefVNI = I->valno;
 841     assert(DefVNI->def == I->start && "Inconsistent def");
 842     DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
 843     // If the defined value extends beyond NewIdx, just move the def down.
 844     // This is case 1 above.
 845     if (SlotIndex::isEarlierInstr(NewIdx, I->end)) {
 846       I->start = DefVNI->def;
 847       return;
 848     }
 849     // The remaining possibilities are now:
 850     // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx).
 851     // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot().
 852     // In either case, it is possible that there is an existing def at NewIdx.
 853     assert((I->end == OldIdx.getDeadSlot() ||
 854             SlotIndex::isSameInstr(I->end, NewIdx)) &&
 855             "Cannot move def below kill");
 856     LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot());
 857     if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
 858       // There is an existing def at NewIdx, case 4 above. The def at OldIdx is
 859       // coalesced into that value.
 860       assert(NewI->valno != DefVNI && "Multiple defs of value?");
 861       LI.removeValNo(DefVNI);
 862       return;
 863     }
 864     // There was no existing def at NewIdx. Turn *I into a dead def at NewIdx.
 865     // If the def at OldIdx was dead, we allow it to be moved across other LI
 866     // values. The new range should be placed immediately before NewI, move any
 867     // intermediate ranges up.
 868     assert(NewI != I && "Inconsistent iterators");
 869     std::copy(llvm::next(I), NewI, I);
 870     *llvm::prior(NewI) = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
 871   }
 872
 873   /// Update LI to reflect an instruction has been moved upwards from OldIdx
 874   /// to NewIdx.
 875   ///
 876   /// 1. Live def at OldIdx:
 877   ///    Hoist def to NewIdx.
 878   ///
 879   /// 2. Dead def at OldIdx:
 880   ///    Hoist def+end to NewIdx, possibly move across other values.
 881   ///
 882   /// 3. Dead def at OldIdx AND existing def at NewIdx:
 883   ///    Remove value defined at OldIdx, coalescing it with existing value.
 884   ///
 885   /// 4. Live def at OldIdx AND existing def at NewIdx:
 886   ///    Remove value defined at NewIdx, hoist OldIdx def to NewIdx.
 887   ///    (Happens when bundling multiple defs together).
 888   ///
 889   /// 5. Value killed at OldIdx:
 890   ///    Hoist kill to NewIdx, then scan for last kill between NewIdx and
 891   ///    OldIdx.
 892   ///
 893   void handleMoveUp(LiveInterval &LI) {
 894     // First look for a kill at OldIdx.
 895     LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
 896     LiveInterval::iterator E = LI.end();
 897     // Is LI even live at OldIdx?
 898     if (I == E || SlotIndex::isEarlierInstr(OldIdx, I->start))
 899       return;
 900
 901     // Handle a live-in value.
 902     if (!SlotIndex::isSameInstr(I->start, OldIdx)) {
 903       // If the live-in value isn't killed here, there is nothing to do.
 904       if (!SlotIndex::isSameInstr(OldIdx, I->end))
 905         return;
 906       // Adjust I->end to end at NewIdx. If we are hoisting a kill above
 907       // another use, we need to search for that use. Case 5 above.
 908       I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
 909       ++I;
 910       // If OldIdx also defines a value, there couldn't have been another use.
 911       if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
 912         // No def, search for the new kill.
 913         // This can never be an early clobber kill since there is no def.
 914         llvm::prior(I)->end = findLastUseBefore(LI.reg).getRegSlot();
 915         return;
 916       }
 917     }
 918
 919     // Now deal with the def at OldIdx.
 920     assert(I != E && SlotIndex::isSameInstr(I->start, OldIdx) && "No def?");
 921     VNInfo *DefVNI = I->valno;
 922     assert(DefVNI->def == I->start && "Inconsistent def");
 923     DefVNI->def = NewIdx.getRegSlot(I->start.isEarlyClobber());
 924
 925     // Check for an existing def at NewIdx.
 926     LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot());
 927     if (SlotIndex::isSameInstr(NewI->start, NewIdx)) {
 928       assert(NewI->valno != DefVNI && "Same value defined more than once?");
 929       // There is an existing def at NewIdx.
 930       if (I->end.isDead()) {
 931         // Case 3: Remove the dead def at OldIdx.
 932         LI.removeValNo(DefVNI);
 933         return;
 934       }
 935       // Case 4: Replace def at NewIdx with live def at OldIdx.
 936       I->start = DefVNI->def;
 937       LI.removeValNo(NewI->valno);
 938       return;
 939     }
 940
 941     // There is no existing def at NewIdx. Hoist DefVNI.
 942     if (!I->end.isDead()) {
 943       // Leave the end point of a live def.
 944       I->start = DefVNI->def;
 945       return;
 946     }
 947
 948     // DefVNI is a dead def. It may have been moved across other values in LI,
 949     // so move I up to NewI. Slide [NewI;I) down one position.
 950     std::copy_backward(NewI, I, llvm::next(I));
 951     *NewI = LiveRange(DefVNI->def, NewIdx.getDeadSlot(), DefVNI);
 952   }
 953
 954   void updateRegMaskSlots() {
 955     SmallVectorImpl<SlotIndex>::iterator RI =
 956       std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
 957                        OldIdx);
 958     assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
 959            "No RegMask at OldIdx.");
 960     *RI = NewIdx.getRegSlot();
 961     assert((RI == LIS.RegMaskSlots.begin() ||
 962             SlotIndex::isEarlierInstr(*llvm::prior(RI), *RI)) &&
 963             "Cannot move regmask instruction above another call");
 964     assert((llvm::next(RI) == LIS.RegMaskSlots.end() ||
 965             SlotIndex::isEarlierInstr(*RI, *llvm::next(RI))) &&
 966             "Cannot move regmask instruction below another call");
 967   }
 968
 969   // Return the last use of reg between NewIdx and OldIdx.
 970   SlotIndex findLastUseBefore(unsigned Reg) {
 971
 972     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 973       SlotIndex LastUse = NewIdx;
 974       for (MachineRegisterInfo::use_nodbg_iterator
 975              UI = MRI.use_nodbg_begin(Reg),
 976              UE = MRI.use_nodbg_end();
 977            UI != UE; UI.skipInstruction()) {
 978         const MachineInstr* MI = &*UI;
 979         SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
 980         if (InstSlot > LastUse && InstSlot < OldIdx)
 981           LastUse = InstSlot;
 982       }
 983       return LastUse;
 984     }
 985
 986     // This is a regunit interval, so scanning the use list could be very
 987     // expensive. Scan upwards from OldIdx instead.
 988     assert(NewIdx < OldIdx && "Expected upwards move");
 989     SlotIndexes *Indexes = LIS.getSlotIndexes();
 990     MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx);
 991
 992     // OldIdx may not correspond to an instruction any longer, so set MII to
 993     // point to the next instruction after OldIdx, or MBB->end().
 994     MachineBasicBlock::iterator MII = MBB->end();
 995     if (MachineInstr *MI = Indexes->getInstructionFromIndex(
 996                            Indexes->getNextNonNullIndex(OldIdx)))
 997       if (MI->getParent() == MBB)
 998         MII = MI;
 999
1000     MachineBasicBlock::iterator Begin = MBB->begin();
1001     while (MII != Begin) {
1002       if ((--MII)->isDebugValue())
1003         continue;
1004       SlotIndex Idx = Indexes->getInstructionIndex(MII);
1005
1006       // Stop searching when NewIdx is reached.
1007       if (!SlotIndex::isEarlierInstr(NewIdx, Idx))
1008         return NewIdx;
1009
1010       // Check if MII uses Reg.
1011       for (MIBundleOperands MO(MII); MO.isValid(); ++MO)
1012         if (MO->isReg() &&
1013             TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
1014             TRI.hasRegUnit(MO->getReg(), Reg))
1015           return Idx;
1016     }
1017     // Didn't reach NewIdx. It must be the first instruction in the block.
1018     return NewIdx;
1019   }
1020 };
1021
1022 void LiveIntervals::handleMove(MachineInstr* MI, bool UpdateFlags) {
1023   assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
1024   SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1025   Indexes->removeMachineInstrFromMaps(MI);
1026   SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
1027   assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
1028          OldIndex < getMBBEndIdx(MI->getParent()) &&
1029          "Cannot handle moves across basic block boundaries.");
1030
1031   HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1032   HME.updateAllRanges(MI);
1033 }
1034
1035 void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
1036                                          MachineInstr* BundleStart,
1037                                          bool UpdateFlags) {
1038   SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1039   SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1040   HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
1041   HME.updateAllRanges(MI);
1042 }
1043
1044 void
1045 LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
1046                                       MachineBasicBlock::iterator Begin,
1047                                       MachineBasicBlock::iterator End,
1048                                       ArrayRef<unsigned> OrigRegs) {
1049   // Find anchor points, which are at the beginning/end of blocks or at
1050   // instructions that already have indexes.
1051   while (Begin != MBB->begin() && !Indexes->hasIndex(Begin))
1052     --Begin;
1053   while (End != MBB->end() && !Indexes->hasIndex(End))
1054     ++End;
1055
1056   SlotIndex endIdx;
1057   if (End == MBB->end())
1058     endIdx = getMBBEndIdx(MBB).getPrevSlot();
1059   else
1060     endIdx = getInstructionIndex(End);
1061
1062   Indexes->repairIndexesInRange(MBB, Begin, End);
1063
1064   for (MachineBasicBlock::iterator I = End; I != Begin;) {
1065     --I;
1066     MachineInstr *MI = I;
1067     if (MI->isDebugValue())
1068       continue;
1069     for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(),
1070          MOE = MI->operands_end(); MOI != MOE; ++MOI) {
1071       if (MOI->isReg() &&
1072           TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
1073           !hasInterval(MOI->getReg())) {
1074         LiveInterval &LI = getOrCreateInterval(MOI->getReg());
1075         computeVirtRegInterval(&LI);
1076       }
1077     }
1078   }
1079
1080   for (unsigned i = 0, e = OrigRegs.size(); i != e; ++i) {
1081     unsigned Reg = OrigRegs[i];
1082     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1083       continue;
1084
1085     LiveInterval &LI = getInterval(Reg);
1086     // FIXME: Should we support undefs that gain defs?
1087     if (!LI.hasAtLeastOneValue())
1088       continue;
1089
1090     LiveInterval::iterator LII = LI.find(endIdx);
1091     SlotIndex lastUseIdx;
1092     if (LII != LI.end() && LII->start < endIdx)
1093       lastUseIdx = LII->end;
1094     else
1095       --LII;
1096
1097     for (MachineBasicBlock::iterator I = End; I != Begin;) {
1098       --I;
1099       MachineInstr *MI = I;
1100       if (MI->isDebugValue())
1101         continue;
1102
1103       SlotIndex instrIdx = getInstructionIndex(MI);
1104       bool isStartValid = getInstructionFromIndex(LII->start);
1105       bool isEndValid = getInstructionFromIndex(LII->end);
1106
1107       // FIXME: This doesn't currently handle early-clobber or multiple removed
1108       // defs inside of the region to repair.
1109       for (MachineInstr::mop_iterator OI = MI->operands_begin(),
1110            OE = MI->operands_end(); OI != OE; ++OI) {
1111         const MachineOperand &MO = *OI;
1112         if (!MO.isReg() || MO.getReg() != Reg)
1113           continue;
1114
1115         if (MO.isDef()) {
1116           if (!isStartValid) {
1117             if (LII->end.isDead()) {
1118               SlotIndex prevStart;
1119               if (LII != LI.begin())
1120                 prevStart = llvm::prior(LII)->start;
1121
1122               // FIXME: This could be more efficient if there was a removeRange
1123               // method that returned an iterator.
1124               LI.removeRange(*LII, true);
1125               if (prevStart.isValid())
1126                 LII = LI.find(prevStart);
1127               else
1128                 LII = LI.begin();
1129             } else {
1130               LII->start = instrIdx.getRegSlot();
1131               LII->valno->def = instrIdx.getRegSlot();
1132               if (MO.getSubReg() && !MO.isUndef())
1133                 lastUseIdx = instrIdx.getRegSlot();
1134               else
1135                 lastUseIdx = SlotIndex();
1136               continue;
1137             }
1138           }
1139
1140           if (!lastUseIdx.isValid()) {
1141             VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
1142                                           VNInfoAllocator);
1143             LiveRange LR(instrIdx.getRegSlot(), instrIdx.getDeadSlot(), VNI);
1144             LII = LI.addRange(LR);
1145           } else if (LII->start != instrIdx.getRegSlot()) {
1146             VNInfo *VNI = LI.getNextValue(instrIdx.getRegSlot(),
1147                                           VNInfoAllocator);
1148             LiveRange LR(instrIdx.getRegSlot(), lastUseIdx, VNI);
1149             LII = LI.addRange(LR);
1150           }
1151
1152           if (MO.getSubReg() && !MO.isUndef())
1153             lastUseIdx = instrIdx.getRegSlot();
1154           else
1155             lastUseIdx = SlotIndex();
1156         } else if (MO.isUse()) {
1157           // FIXME: This should probably be handled outside of this branch,
1158           // either as part of the def case (for defs inside of the region) or
1159           // after the loop over the region.
1160           if (!isEndValid && !LII->end.isBlock())
1161             LII->end = instrIdx.getRegSlot();
1162           if (!lastUseIdx.isValid())
1163             lastUseIdx = instrIdx.getRegSlot();
1164         }
1165       }
1166     }
1167   }
1168 }