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 "liveintervals"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "VirtRegMap.h"
  21 #include "llvm/Value.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/CodeGen/CalcSpillWeights.h"
  24 #include "llvm/CodeGen/LiveVariables.h"
  25 #include "llvm/CodeGen/MachineFrameInfo.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/MachineLoopInfo.h"
  29 #include "llvm/CodeGen/MachineMemOperand.h"
  30 #include "llvm/CodeGen/MachineRegisterInfo.h"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/CodeGen/ProcessImplicitDefs.h"
  33 #include "llvm/Target/TargetRegisterInfo.h"
  34 #include "llvm/Target/TargetInstrInfo.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include "llvm/Target/TargetOptions.h"
  37 #include "llvm/Support/CommandLine.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/Support/raw_ostream.h"
  41 #include "llvm/ADT/DepthFirstIterator.h"
  42 #include "llvm/ADT/SmallSet.h"
  43 #include "llvm/ADT/Statistic.h"
  44 #include "llvm/ADT/STLExtras.h"
  45 #include <algorithm>
  46 #include <limits>
  47 #include <cmath>
  48 using namespace llvm;
  49
  50 // Hidden options for help debugging.
  51 static cl::opt<bool> DisableReMat("disable-rematerialization",
  52                                   cl::init(false), cl::Hidden);
  53
  54 STATISTIC(numIntervals , "Number of original intervals");
  55 STATISTIC(numFolds     , "Number of loads/stores folded into instructions");
  56 STATISTIC(numSplits    , "Number of intervals split");
  57
  58 char LiveIntervals::ID = 0;
  59 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
  60                 "Live Interval Analysis", false, false)
  61 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
  62 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  63 INITIALIZE_PASS_DEPENDENCY(PHIElimination)
  64 INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
  65 INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
  66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  67 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  68 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
  69                 "Live Interval Analysis", false, false)
  70
  71 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  72   AU.setPreservesCFG();
  73   AU.addRequired<AliasAnalysis>();
  74   AU.addPreserved<AliasAnalysis>();
  75   AU.addRequired<LiveVariables>();
  76   AU.addPreserved<LiveVariables>();
  77   AU.addRequired<MachineLoopInfo>();
  78   AU.addPreserved<MachineLoopInfo>();
  79   AU.addPreservedID(MachineDominatorsID);
  80
  81   if (!StrongPHIElim) {
  82     AU.addPreservedID(PHIEliminationID);
  83     AU.addRequiredID(PHIEliminationID);
  84   }
  85
  86   AU.addRequiredID(TwoAddressInstructionPassID);
  87   AU.addPreserved<ProcessImplicitDefs>();
  88   AU.addRequired<ProcessImplicitDefs>();
  89   AU.addPreserved<SlotIndexes>();
  90   AU.addRequiredTransitive<SlotIndexes>();
  91   MachineFunctionPass::getAnalysisUsage(AU);
  92 }
  93
  94 void LiveIntervals::releaseMemory() {
  95   // Free the live intervals themselves.
  96   for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
  97        E = r2iMap_.end(); I != E; ++I)
  98     delete I->second;
  99
 100   r2iMap_.clear();
 101
 102   // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
 103   VNInfoAllocator.Reset();
 104   while (!CloneMIs.empty()) {
 105     MachineInstr *MI = CloneMIs.back();
 106     CloneMIs.pop_back();
 107     mf_->DeleteMachineInstr(MI);
 108   }
 109 }
 110
 111 /// runOnMachineFunction - Register allocate the whole function
 112 ///
 113 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 114   mf_ = &fn;
 115   mri_ = &mf_->getRegInfo();
 116   tm_ = &fn.getTarget();
 117   tri_ = tm_->getRegisterInfo();
 118   tii_ = tm_->getInstrInfo();
 119   aa_ = &getAnalysis<AliasAnalysis>();
 120   lv_ = &getAnalysis<LiveVariables>();
 121   indexes_ = &getAnalysis<SlotIndexes>();
 122   allocatableRegs_ = tri_->getAllocatableSet(fn);
 123
 124   computeIntervals();
 125
 126   numIntervals += getNumIntervals();
 127
 128   DEBUG(dump());
 129   return true;
 130 }
 131
 132 /// print - Implement the dump method.
 133 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
 134   OS << "********** INTERVALS **********\n";
 135   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 136     I->second->print(OS, tri_);
 137     OS << "\n";
 138   }
 139
 140   printInstrs(OS);
 141 }
 142
 143 void LiveIntervals::printInstrs(raw_ostream &OS) const {
 144   OS << "********** MACHINEINSTRS **********\n";
 145   mf_->print(OS, indexes_);
 146 }
 147
 148 void LiveIntervals::dumpInstrs() const {
 149   printInstrs(dbgs());
 150 }
 151
 152 bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,
 153                                          VirtRegMap &vrm, unsigned reg) {
 154   // We don't handle fancy stuff crossing basic block boundaries
 155   if (li.ranges.size() != 1)
 156     return true;
 157   const LiveRange &range = li.ranges.front();
 158   SlotIndex idx = range.start.getBaseIndex();
 159   SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();
 160
 161   // Skip deleted instructions
 162   MachineInstr *firstMI = getInstructionFromIndex(idx);
 163   while (!firstMI && idx != end) {
 164     idx = idx.getNextIndex();
 165     firstMI = getInstructionFromIndex(idx);
 166   }
 167   if (!firstMI)
 168     return false;
 169
 170   // Find last instruction in range
 171   SlotIndex lastIdx = end.getPrevIndex();
 172   MachineInstr *lastMI = getInstructionFromIndex(lastIdx);
 173   while (!lastMI && lastIdx != idx) {
 174     lastIdx = lastIdx.getPrevIndex();
 175     lastMI = getInstructionFromIndex(lastIdx);
 176   }
 177   if (!lastMI)
 178     return false;
 179
 180   // Range cannot cross basic block boundaries or terminators
 181   MachineBasicBlock *MBB = firstMI->getParent();
 182   if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())
 183     return true;
 184
 185   MachineBasicBlock::const_iterator E = lastMI;
 186   ++E;
 187   for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {
 188     const MachineInstr &MI = *I;
 189
 190     // Allow copies to and from li.reg
 191     if (MI.isCopy())
 192       if (MI.getOperand(0).getReg() == li.reg ||
 193           MI.getOperand(1).getReg() == li.reg)
 194         continue;
 195
 196     // Check for operands using reg
 197     for (unsigned i = 0, e = MI.getNumOperands(); i != e;  ++i) {
 198       const MachineOperand& mop = MI.getOperand(i);
 199       if (!mop.isReg())
 200         continue;
 201       unsigned PhysReg = mop.getReg();
 202       if (PhysReg == 0 || PhysReg == li.reg)
 203         continue;
 204       if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
 205         if (!vrm.hasPhys(PhysReg))
 206           continue;
 207         PhysReg = vrm.getPhys(PhysReg);
 208       }
 209       if (PhysReg && tri_->regsOverlap(PhysReg, reg))
 210         return true;
 211     }
 212   }
 213
 214   // No conflicts found.
 215   return false;
 216 }
 217
 218 bool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg,
 219                                   SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
 220   for (LiveInterval::Ranges::const_iterator
 221          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 222     for (SlotIndex index = I->start.getBaseIndex(),
 223            end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
 224            index != end;
 225            index = index.getNextIndex()) {
 226       MachineInstr *MI = getInstructionFromIndex(index);
 227       if (!MI)
 228         continue;               // skip deleted instructions
 229
 230       if (JoinedCopies.count(MI))
 231         continue;
 232       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 233         MachineOperand& MO = MI->getOperand(i);
 234         if (!MO.isReg())
 235           continue;
 236         unsigned PhysReg = MO.getReg();
 237         if (PhysReg == 0 || PhysReg == Reg ||
 238             TargetRegisterInfo::isVirtualRegister(PhysReg))
 239           continue;
 240         if (tri_->regsOverlap(Reg, PhysReg))
 241           return true;
 242       }
 243     }
 244   }
 245
 246   return false;
 247 }
 248
 249 static
 250 bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
 251   unsigned Reg = MI.getOperand(MOIdx).getReg();
 252   for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
 253     const MachineOperand &MO = MI.getOperand(i);
 254     if (!MO.isReg())
 255       continue;
 256     if (MO.getReg() == Reg && MO.isDef()) {
 257       assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
 258              MI.getOperand(MOIdx).getSubReg() &&
 259              (MO.getSubReg() || MO.isImplicit()));
 260       return true;
 261     }
 262   }
 263   return false;
 264 }
 265
 266 /// isPartialRedef - Return true if the specified def at the specific index is
 267 /// partially re-defining the specified live interval. A common case of this is
 268 /// a definition of the sub-register.
 269 bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
 270                                    LiveInterval &interval) {
 271   if (!MO.getSubReg() || MO.isEarlyClobber())
 272     return false;
 273
 274   SlotIndex RedefIndex = MIIdx.getDefIndex();
 275   const LiveRange *OldLR =
 276     interval.getLiveRangeContaining(RedefIndex.getUseIndex());
 277   MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
 278   if (DefMI != 0) {
 279     return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
 280   }
 281   return false;
 282 }
 283
 284 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 285                                              MachineBasicBlock::iterator mi,
 286                                              SlotIndex MIIdx,
 287                                              MachineOperand& MO,
 288                                              unsigned MOIdx,
 289                                              LiveInterval &interval) {
 290   DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
 291
 292   // Virtual registers may be defined multiple times (due to phi
 293   // elimination and 2-addr elimination).  Much of what we do only has to be
 294   // done once for the vreg.  We use an empty interval to detect the first
 295   // time we see a vreg.
 296   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 297   if (interval.empty()) {
 298     // Get the Idx of the defining instructions.
 299     SlotIndex defIndex = MIIdx.getDefIndex();
 300     // Earlyclobbers move back one, so that they overlap the live range
 301     // of inputs.
 302     if (MO.isEarlyClobber())
 303       defIndex = MIIdx.getUseIndex();
 304
 305     // Make sure the first definition is not a partial redefinition. Add an
 306     // <imp-def> of the full register.
 307     if (MO.getSubReg())
 308       mi->addRegisterDefined(interval.reg);
 309
 310     MachineInstr *CopyMI = NULL;
 311     if (mi->isCopyLike()) {
 312       CopyMI = mi;
 313     }
 314
 315     VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
 316     assert(ValNo->id == 0 && "First value in interval is not 0?");
 317
 318     // Loop over all of the blocks that the vreg is defined in.  There are
 319     // two cases we have to handle here.  The most common case is a vreg
 320     // whose lifetime is contained within a basic block.  In this case there
 321     // will be a single kill, in MBB, which comes after the definition.
 322     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 323       // FIXME: what about dead vars?
 324       SlotIndex killIdx;
 325       if (vi.Kills[0] != mi)
 326         killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
 327       else
 328         killIdx = defIndex.getStoreIndex();
 329
 330       // If the kill happens after the definition, we have an intra-block
 331       // live range.
 332       if (killIdx > defIndex) {
 333         assert(vi.AliveBlocks.empty() &&
 334                "Shouldn't be alive across any blocks!");
 335         LiveRange LR(defIndex, killIdx, ValNo);
 336         interval.addRange(LR);
 337         DEBUG(dbgs() << " +" << LR << "\n");
 338         return;
 339       }
 340     }
 341
 342     // The other case we handle is when a virtual register lives to the end
 343     // of the defining block, potentially live across some blocks, then is
 344     // live into some number of blocks, but gets killed.  Start by adding a
 345     // range that goes from this definition to the end of the defining block.
 346     LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
 347     DEBUG(dbgs() << " +" << NewLR);
 348     interval.addRange(NewLR);
 349
 350     bool PHIJoin = lv_->isPHIJoin(interval.reg);
 351
 352     if (PHIJoin) {
 353       // A phi join register is killed at the end of the MBB and revived as a new
 354       // valno in the killing blocks.
 355       assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
 356       DEBUG(dbgs() << " phi-join");
 357       ValNo->setHasPHIKill(true);
 358     } else {
 359       // Iterate over all of the blocks that the variable is completely
 360       // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 361       // live interval.
 362       for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
 363                E = vi.AliveBlocks.end(); I != E; ++I) {
 364         MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
 365         LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
 366         interval.addRange(LR);
 367         DEBUG(dbgs() << " +" << LR);
 368       }
 369     }
 370
 371     // Finally, this virtual register is live from the start of any killing
 372     // block to the 'use' slot of the killing instruction.
 373     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 374       MachineInstr *Kill = vi.Kills[i];
 375       SlotIndex Start = getMBBStartIdx(Kill->getParent());
 376       SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
 377
 378       // Create interval with one of a NEW value number.  Note that this value
 379       // number isn't actually defined by an instruction, weird huh? :)
 380       if (PHIJoin) {
 381         assert(getInstructionFromIndex(Start) == 0 &&
 382                "PHI def index points at actual instruction.");
 383         ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
 384         ValNo->setIsPHIDef(true);
 385       }
 386       LiveRange LR(Start, killIdx, ValNo);
 387       interval.addRange(LR);
 388       DEBUG(dbgs() << " +" << LR);
 389     }
 390
 391   } else {
 392     if (MultipleDefsBySameMI(*mi, MOIdx))
 393       // Multiple defs of the same virtual register by the same instruction.
 394       // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
 395       // This is likely due to elimination of REG_SEQUENCE instructions. Return
 396       // here since there is nothing to do.
 397       return;
 398
 399     // If this is the second time we see a virtual register definition, it
 400     // must be due to phi elimination or two addr elimination.  If this is
 401     // the result of two address elimination, then the vreg is one of the
 402     // def-and-use register operand.
 403
 404     // It may also be partial redef like this:
 405     // 80  %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
 406     // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
 407     bool PartReDef = isPartialRedef(MIIdx, MO, interval);
 408     if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
 409       // If this is a two-address definition, then we have already processed
 410       // the live range.  The only problem is that we didn't realize there
 411       // are actually two values in the live interval.  Because of this we
 412       // need to take the LiveRegion that defines this register and split it
 413       // into two values.
 414       SlotIndex RedefIndex = MIIdx.getDefIndex();
 415       if (MO.isEarlyClobber())
 416         RedefIndex = MIIdx.getUseIndex();
 417
 418       const LiveRange *OldLR =
 419         interval.getLiveRangeContaining(RedefIndex.getUseIndex());
 420       VNInfo *OldValNo = OldLR->valno;
 421       SlotIndex DefIndex = OldValNo->def.getDefIndex();
 422
 423       // Delete the previous value, which should be short and continuous,
 424       // because the 2-addr copy must be in the same MBB as the redef.
 425       interval.removeRange(DefIndex, RedefIndex);
 426
 427       // The new value number (#1) is defined by the instruction we claimed
 428       // defined value #0.
 429       VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
 430
 431       // Value#0 is now defined by the 2-addr instruction.
 432       OldValNo->def  = RedefIndex;
 433       OldValNo->setCopy(0);
 434
 435       // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
 436       if (PartReDef && mi->isCopyLike())
 437         OldValNo->setCopy(&*mi);
 438
 439       // Add the new live interval which replaces the range for the input copy.
 440       LiveRange LR(DefIndex, RedefIndex, ValNo);
 441       DEBUG(dbgs() << " replace range with " << LR);
 442       interval.addRange(LR);
 443
 444       // If this redefinition is dead, we need to add a dummy unit live
 445       // range covering the def slot.
 446       if (MO.isDead())
 447         interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
 448                                     OldValNo));
 449
 450       DEBUG({
 451           dbgs() << " RESULT: ";
 452           interval.print(dbgs(), tri_);
 453         });
 454     } else if (lv_->isPHIJoin(interval.reg)) {
 455       // In the case of PHI elimination, each variable definition is only
 456       // live until the end of the block.  We've already taken care of the
 457       // rest of the live range.
 458
 459       SlotIndex defIndex = MIIdx.getDefIndex();
 460       if (MO.isEarlyClobber())
 461         defIndex = MIIdx.getUseIndex();
 462
 463       VNInfo *ValNo;
 464       MachineInstr *CopyMI = NULL;
 465       if (mi->isCopyLike())
 466         CopyMI = mi;
 467       ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
 468
 469       SlotIndex killIndex = getMBBEndIdx(mbb);
 470       LiveRange LR(defIndex, killIndex, ValNo);
 471       interval.addRange(LR);
 472       ValNo->setHasPHIKill(true);
 473       DEBUG(dbgs() << " phi-join +" << LR);
 474     } else {
 475       llvm_unreachable("Multiply defined register");
 476     }
 477   }
 478
 479   DEBUG(dbgs() << '\n');
 480 }
 481
 482 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 483                                               MachineBasicBlock::iterator mi,
 484                                               SlotIndex MIIdx,
 485                                               MachineOperand& MO,
 486                                               LiveInterval &interval,
 487                                               MachineInstr *CopyMI) {
 488   // A physical register cannot be live across basic block, so its
 489   // lifetime must end somewhere in its defining basic block.
 490   DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
 491
 492   SlotIndex baseIndex = MIIdx;
 493   SlotIndex start = baseIndex.getDefIndex();
 494   // Earlyclobbers move back one.
 495   if (MO.isEarlyClobber())
 496     start = MIIdx.getUseIndex();
 497   SlotIndex end = start;
 498
 499   // If it is not used after definition, it is considered dead at
 500   // the instruction defining it. Hence its interval is:
 501   // [defSlot(def), defSlot(def)+1)
 502   // For earlyclobbers, the defSlot was pushed back one; the extra
 503   // advance below compensates.
 504   if (MO.isDead()) {
 505     DEBUG(dbgs() << " dead");
 506     end = start.getStoreIndex();
 507     goto exit;
 508   }
 509
 510   // If it is not dead on definition, it must be killed by a
 511   // subsequent instruction. Hence its interval is:
 512   // [defSlot(def), useSlot(kill)+1)
 513   baseIndex = baseIndex.getNextIndex();
 514   while (++mi != MBB->end()) {
 515
 516     if (mi->isDebugValue())
 517       continue;
 518     if (getInstructionFromIndex(baseIndex) == 0)
 519       baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 520
 521     if (mi->killsRegister(interval.reg, tri_)) {
 522       DEBUG(dbgs() << " killed");
 523       end = baseIndex.getDefIndex();
 524       goto exit;
 525     } else {
 526       int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
 527       if (DefIdx != -1) {
 528         if (mi->isRegTiedToUseOperand(DefIdx)) {
 529           // Two-address instruction.
 530           end = baseIndex.getDefIndex();
 531         } else {
 532           // Another instruction redefines the register before it is ever read.
 533           // Then the register is essentially dead at the instruction that
 534           // defines it. Hence its interval is:
 535           // [defSlot(def), defSlot(def)+1)
 536           DEBUG(dbgs() << " dead");
 537           end = start.getStoreIndex();
 538         }
 539         goto exit;
 540       }
 541     }
 542
 543     baseIndex = baseIndex.getNextIndex();
 544   }
 545
 546   // The only case we should have a dead physreg here without a killing or
 547   // instruction where we know it's dead is if it is live-in to the function
 548   // and never used. Another possible case is the implicit use of the
 549   // physical register has been deleted by two-address pass.
 550   end = start.getStoreIndex();
 551
 552 exit:
 553   assert(start < end && "did not find end of interval?");
 554
 555   // Already exists? Extend old live interval.
 556   VNInfo *ValNo = interval.getVNInfoAt(start);
 557   bool Extend = ValNo != 0;
 558   if (!Extend)
 559     ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
 560   if (Extend && MO.isEarlyClobber())
 561     ValNo->setHasRedefByEC(true);
 562   LiveRange LR(start, end, ValNo);
 563   interval.addRange(LR);
 564   DEBUG(dbgs() << " +" << LR << '\n');
 565 }
 566
 567 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 568                                       MachineBasicBlock::iterator MI,
 569                                       SlotIndex MIIdx,
 570                                       MachineOperand& MO,
 571                                       unsigned MOIdx) {
 572   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 573     handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
 574                              getOrCreateInterval(MO.getReg()));
 575   else if (allocatableRegs_[MO.getReg()]) {
 576     MachineInstr *CopyMI = NULL;
 577     if (MI->isCopyLike())
 578       CopyMI = MI;
 579     handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
 580                               getOrCreateInterval(MO.getReg()), CopyMI);
 581     // Def of a register also defines its sub-registers.
 582     for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
 583       // If MI also modifies the sub-register explicitly, avoid processing it
 584       // more than once. Do not pass in TRI here so it checks for exact match.
 585       if (!MI->definesRegister(*AS))
 586         handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
 587                                   getOrCreateInterval(*AS), 0);
 588   }
 589 }
 590
 591 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 592                                          SlotIndex MIIdx,
 593                                          LiveInterval &interval, bool isAlias) {
 594   DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
 595
 596   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 597   // be considered a livein.
 598   MachineBasicBlock::iterator mi = MBB->begin();
 599   MachineBasicBlock::iterator E = MBB->end();
 600   // Skip over DBG_VALUE at the start of the MBB.
 601   if (mi != E && mi->isDebugValue()) {
 602     while (++mi != E && mi->isDebugValue())
 603       ;
 604     if (mi == E)
 605       // MBB is empty except for DBG_VALUE's.
 606       return;
 607   }
 608
 609   SlotIndex baseIndex = MIIdx;
 610   SlotIndex start = baseIndex;
 611   if (getInstructionFromIndex(baseIndex) == 0)
 612     baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 613
 614   SlotIndex end = baseIndex;
 615   bool SeenDefUse = false;
 616
 617   while (mi != E) {
 618     if (mi->killsRegister(interval.reg, tri_)) {
 619       DEBUG(dbgs() << " killed");
 620       end = baseIndex.getDefIndex();
 621       SeenDefUse = true;
 622       break;
 623     } else if (mi->definesRegister(interval.reg, tri_)) {
 624       // Another instruction redefines the register before it is ever read.
 625       // Then the register is essentially dead at the instruction that defines
 626       // it. Hence its interval is:
 627       // [defSlot(def), defSlot(def)+1)
 628       DEBUG(dbgs() << " dead");
 629       end = start.getStoreIndex();
 630       SeenDefUse = true;
 631       break;
 632     }
 633
 634     while (++mi != E && mi->isDebugValue())
 635       // Skip over DBG_VALUE.
 636       ;
 637     if (mi != E)
 638       baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 639   }
 640
 641   // Live-in register might not be used at all.
 642   if (!SeenDefUse) {
 643     if (isAlias) {
 644       DEBUG(dbgs() << " dead");
 645       end = MIIdx.getStoreIndex();
 646     } else {
 647       DEBUG(dbgs() << " live through");
 648       end = baseIndex;
 649     }
 650   }
 651
 652   SlotIndex defIdx = getMBBStartIdx(MBB);
 653   assert(getInstructionFromIndex(defIdx) == 0 &&
 654          "PHI def index points at actual instruction.");
 655   VNInfo *vni =
 656     interval.getNextValue(defIdx, 0, VNInfoAllocator);
 657   vni->setIsPHIDef(true);
 658   LiveRange LR(start, end, vni);
 659
 660   interval.addRange(LR);
 661   DEBUG(dbgs() << " +" << LR << '\n');
 662 }
 663
 664 /// computeIntervals - computes the live intervals for virtual
 665 /// registers. for some ordering of the machine instructions [1,N] a
 666 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 667 /// which a variable is live
 668 void LiveIntervals::computeIntervals() {
 669   DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
 670                << "********** Function: "
 671                << ((Value*)mf_->getFunction())->getName() << '\n');
 672
 673   SmallVector<unsigned, 8> UndefUses;
 674   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 675        MBBI != E; ++MBBI) {
 676     MachineBasicBlock *MBB = MBBI;
 677     if (MBB->empty())
 678       continue;
 679
 680     // Track the index of the current machine instr.
 681     SlotIndex MIIndex = getMBBStartIdx(MBB);
 682     DEBUG(dbgs() << "BB#" << MBB->getNumber()
 683           << ":\t\t# derived from " << MBB->getName() << "\n");
 684
 685     // Create intervals for live-ins to this BB first.
 686     for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
 687            LE = MBB->livein_end(); LI != LE; ++LI) {
 688       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 689       // Multiple live-ins can alias the same register.
 690       for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
 691         if (!hasInterval(*AS))
 692           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 693                                true);
 694     }
 695
 696     // Skip over empty initial indices.
 697     if (getInstructionFromIndex(MIIndex) == 0)
 698       MIIndex = indexes_->getNextNonNullIndex(MIIndex);
 699
 700     for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 701          MI != miEnd; ++MI) {
 702       DEBUG(dbgs() << MIIndex << "\t" << *MI);
 703       if (MI->isDebugValue())
 704         continue;
 705
 706       // Handle defs.
 707       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 708         MachineOperand &MO = MI->getOperand(i);
 709         if (!MO.isReg() || !MO.getReg())
 710           continue;
 711
 712         // handle register defs - build intervals
 713         if (MO.isDef())
 714           handleRegisterDef(MBB, MI, MIIndex, MO, i);
 715         else if (MO.isUndef())
 716           UndefUses.push_back(MO.getReg());
 717       }
 718
 719       // Move to the next instr slot.
 720       MIIndex = indexes_->getNextNonNullIndex(MIIndex);
 721     }
 722   }
 723
 724   // Create empty intervals for registers defined by implicit_def's (except
 725   // for those implicit_def that define values which are liveout of their
 726   // blocks.
 727   for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
 728     unsigned UndefReg = UndefUses[i];
 729     (void)getOrCreateInterval(UndefReg);
 730   }
 731 }
 732
 733 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
 734   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
 735   return new LiveInterval(reg, Weight);
 736 }
 737
 738 /// dupInterval - Duplicate a live interval. The caller is responsible for
 739 /// managing the allocated memory.
 740 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
 741   LiveInterval *NewLI = createInterval(li->reg);
 742   NewLI->Copy(*li, mri_, getVNInfoAllocator());
 743   return NewLI;
 744 }
 745
 746 /// shrinkToUses - After removing some uses of a register, shrink its live
 747 /// range to just the remaining uses. This method does not compute reaching
 748 /// defs for new uses, and it doesn't remove dead defs.
 749 void LiveIntervals::shrinkToUses(LiveInterval *li,
 750                                  SmallVectorImpl<MachineInstr*> *dead) {
 751   DEBUG(dbgs() << "Shrink: " << *li << '\n');
 752   assert(TargetRegisterInfo::isVirtualRegister(li->reg)
 753          && "Can't only shrink physical registers");
 754   // Find all the values used, including PHI kills.
 755   SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
 756
 757   // Visit all instructions reading li->reg.
 758   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
 759        MachineInstr *UseMI = I.skipInstruction();) {
 760     if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
 761       continue;
 762     SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
 763     VNInfo *VNI = li->getVNInfoAt(Idx);
 764     assert(VNI && "Live interval not live into reading instruction");
 765     if (VNI->def == Idx) {
 766       // Special case: An early-clobber tied operand reads and writes the
 767       // register one slot early.
 768       Idx = Idx.getPrevSlot();
 769       VNI = li->getVNInfoAt(Idx);
 770       assert(VNI && "Early-clobber tied value not available");
 771     }
 772     WorkList.push_back(std::make_pair(Idx, VNI));
 773   }
 774
 775   // Create a new live interval with only minimal live segments per def.
 776   LiveInterval NewLI(li->reg, 0);
 777   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 778        I != E; ++I) {
 779     VNInfo *VNI = *I;
 780     if (VNI->isUnused())
 781       continue;
 782     NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
 783
 784     // A use tied to an early-clobber def ends at the load slot and isn't caught
 785     // above. Catch it here instead. This probably only ever happens for inline
 786     // assembly.
 787     if (VNI->def.isUse())
 788       if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
 789         WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
 790   }
 791
 792   // Keep track of the PHIs that are in use.
 793   SmallPtrSet<VNInfo*, 8> UsedPHIs;
 794
 795   // Extend intervals to reach all uses in WorkList.
 796   while (!WorkList.empty()) {
 797     SlotIndex Idx = WorkList.back().first;
 798     VNInfo *VNI = WorkList.back().second;
 799     WorkList.pop_back();
 800     const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
 801     SlotIndex BlockStart = getMBBStartIdx(MBB);
 802
 803     // Extend the live range for VNI to be live at Idx.
 804     if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
 805       (void)ExtVNI;
 806       assert(ExtVNI == VNI && "Unexpected existing value number");
 807       // Is this a PHIDef we haven't seen before?
 808       if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
 809         continue;
 810       // The PHI is live, make sure the predecessors are live-out.
 811       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 812            PE = MBB->pred_end(); PI != PE; ++PI) {
 813         SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
 814         VNInfo *PVNI = li->getVNInfoAt(Stop);
 815         // A predecessor is not required to have a live-out value for a PHI.
 816         if (PVNI) {
 817           assert(PVNI->hasPHIKill() && "Missing hasPHIKill flag");
 818           WorkList.push_back(std::make_pair(Stop, PVNI));
 819         }
 820       }
 821       continue;
 822     }
 823
 824     // VNI is live-in to MBB.
 825     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
 826     NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
 827
 828     // Make sure VNI is live-out from the predecessors.
 829     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 830          PE = MBB->pred_end(); PI != PE; ++PI) {
 831       SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
 832       assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
 833       WorkList.push_back(std::make_pair(Stop, VNI));
 834     }
 835   }
 836
 837   // Handle dead values.
 838   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 839        I != E; ++I) {
 840     VNInfo *VNI = *I;
 841     if (VNI->isUnused())
 842       continue;
 843     LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
 844     assert(LII != NewLI.end() && "Missing live range for PHI");
 845     if (LII->end != VNI->def.getNextSlot())
 846       continue;
 847     if (VNI->isPHIDef()) {
 848       // This is a dead PHI. Remove it.
 849       VNI->setIsUnused(true);
 850       NewLI.removeRange(*LII);
 851     } else {
 852       // This is a dead def. Make sure the instruction knows.
 853       MachineInstr *MI = getInstructionFromIndex(VNI->def);
 854       assert(MI && "No instruction defining live value");
 855       MI->addRegisterDead(li->reg, tri_);
 856       if (dead && MI->allDefsAreDead()) {
 857         DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
 858         dead->push_back(MI);
 859       }
 860     }
 861   }
 862
 863   // Move the trimmed ranges back.
 864   li->ranges.swap(NewLI.ranges);
 865   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
 866 }
 867
 868
 869 //===----------------------------------------------------------------------===//
 870 // Register allocator hooks.
 871 //
 872
 873 MachineBasicBlock::iterator
 874 LiveIntervals::getLastSplitPoint(const LiveInterval &li,
 875                                  MachineBasicBlock *mbb) const {
 876   const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
 877
 878   // If li is not live into a landing pad, we can insert spill code before the
 879   // first terminator.
 880   if (!lpad || !isLiveInToMBB(li, lpad))
 881     return mbb->getFirstTerminator();
 882
 883   // When there is a landing pad, spill code must go before the call instruction
 884   // that can throw.
 885   MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
 886   while (I != B) {
 887     --I;
 888     if (I->getDesc().isCall())
 889       return I;
 890   }
 891   // The block contains no calls that can throw, so use the first terminator.
 892   return mbb->getFirstTerminator();
 893 }
 894
 895 void LiveIntervals::addKillFlags() {
 896   for (iterator I = begin(), E = end(); I != E; ++I) {
 897     unsigned Reg = I->first;
 898     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 899       continue;
 900     if (mri_->reg_nodbg_empty(Reg))
 901       continue;
 902     LiveInterval *LI = I->second;
 903
 904     // Every instruction that kills Reg corresponds to a live range end point.
 905     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
 906          ++RI) {
 907       // A LOAD index indicates an MBB edge.
 908       if (RI->end.isLoad())
 909         continue;
 910       MachineInstr *MI = getInstructionFromIndex(RI->end);
 911       if (!MI)
 912         continue;
 913       MI->addRegisterKilled(Reg, NULL);
 914     }
 915   }
 916 }
 917
 918 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
 919 /// allow one) virtual register operand, then its uses are implicitly using
 920 /// the register. Returns the virtual register.
 921 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
 922                                             MachineInstr *MI) const {
 923   unsigned RegOp = 0;
 924   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 925     MachineOperand &MO = MI->getOperand(i);
 926     if (!MO.isReg() || !MO.isUse())
 927       continue;
 928     unsigned Reg = MO.getReg();
 929     if (Reg == 0 || Reg == li.reg)
 930       continue;
 931
 932     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
 933         !allocatableRegs_[Reg])
 934       continue;
 935     // FIXME: For now, only remat MI with at most one register operand.
 936     assert(!RegOp &&
 937            "Can't rematerialize instruction with multiple register operand!");
 938     RegOp = MO.getReg();
 939 #ifndef NDEBUG
 940     break;
 941 #endif
 942   }
 943   return RegOp;
 944 }
 945
 946 /// isValNoAvailableAt - Return true if the val# of the specified interval
 947 /// which reaches the given instruction also reaches the specified use index.
 948 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
 949                                        SlotIndex UseIdx) const {
 950   VNInfo *UValNo = li.getVNInfoAt(UseIdx);
 951   return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
 952 }
 953
 954 /// isReMaterializable - Returns true if the definition MI of the specified
 955 /// val# of the specified interval is re-materializable.
 956 bool
 957 LiveIntervals::isReMaterializable(const LiveInterval &li,
 958                                   const VNInfo *ValNo, MachineInstr *MI,
 959                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
 960                                   bool &isLoad) {
 961   if (DisableReMat)
 962     return false;
 963
 964   if (!tii_->isTriviallyReMaterializable(MI, aa_))
 965     return false;
 966
 967   // Target-specific code can mark an instruction as being rematerializable
 968   // if it has one virtual reg use, though it had better be something like
 969   // a PIC base register which is likely to be live everywhere.
 970   unsigned ImpUse = getReMatImplicitUse(li, MI);
 971   if (ImpUse) {
 972     const LiveInterval &ImpLi = getInterval(ImpUse);
 973     for (MachineRegisterInfo::use_nodbg_iterator
 974            ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
 975          ri != re; ++ri) {
 976       MachineInstr *UseMI = &*ri;
 977       SlotIndex UseIdx = getInstructionIndex(UseMI);
 978       if (li.getVNInfoAt(UseIdx) != ValNo)
 979         continue;
 980       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
 981         return false;
 982     }
 983
 984     // If a register operand of the re-materialized instruction is going to
 985     // be spilled next, then it's not legal to re-materialize this instruction.
 986     if (SpillIs)
 987       for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
 988         if (ImpUse == (*SpillIs)[i]->reg)
 989           return false;
 990   }
 991   return true;
 992 }
 993
 994 /// isReMaterializable - Returns true if the definition MI of the specified
 995 /// val# of the specified interval is re-materializable.
 996 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 997                                        const VNInfo *ValNo, MachineInstr *MI) {
 998   bool Dummy2;
 999   return isReMaterializable(li, ValNo, MI, 0, Dummy2);
1000 }
1001
1002 /// isReMaterializable - Returns true if every definition of MI of every
1003 /// val# of the specified interval is re-materializable.
1004 bool
1005 LiveIntervals::isReMaterializable(const LiveInterval &li,
1006                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
1007                                   bool &isLoad) {
1008   isLoad = false;
1009   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1010        i != e; ++i) {
1011     const VNInfo *VNI = *i;
1012     if (VNI->isUnused())
1013       continue; // Dead val#.
1014     // Is the def for the val# rematerializable?
1015     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1016     if (!ReMatDefMI)
1017       return false;
1018     bool DefIsLoad = false;
1019     if (!ReMatDefMI ||
1020         !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1021       return false;
1022     isLoad |= DefIsLoad;
1023   }
1024   return true;
1025 }
1026
1027 /// FilterFoldedOps - Filter out two-address use operands. Return
1028 /// true if it finds any issue with the operands that ought to prevent
1029 /// folding.
1030 static bool FilterFoldedOps(MachineInstr *MI,
1031                             SmallVector<unsigned, 2> &Ops,
1032                             unsigned &MRInfo,
1033                             SmallVector<unsigned, 2> &FoldOps) {
1034   MRInfo = 0;
1035   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1036     unsigned OpIdx = Ops[i];
1037     MachineOperand &MO = MI->getOperand(OpIdx);
1038     // FIXME: fold subreg use.
1039     if (MO.getSubReg())
1040       return true;
1041     if (MO.isDef())
1042       MRInfo |= (unsigned)VirtRegMap::isMod;
1043     else {
1044       // Filter out two-address use operand(s).
1045       if (MI->isRegTiedToDefOperand(OpIdx)) {
1046         MRInfo = VirtRegMap::isModRef;
1047         continue;
1048       }
1049       MRInfo |= (unsigned)VirtRegMap::isRef;
1050     }
1051     FoldOps.push_back(OpIdx);
1052   }
1053   return false;
1054 }
1055
1056
1057 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1058 /// slot / to reg or any rematerialized load into ith operand of specified
1059 /// MI. If it is successul, MI is updated with the newly created MI and
1060 /// returns true.
1061 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1062                                          VirtRegMap &vrm, MachineInstr *DefMI,
1063                                          SlotIndex InstrIdx,
1064                                          SmallVector<unsigned, 2> &Ops,
1065                                          bool isSS, int Slot, unsigned Reg) {
1066   // If it is an implicit def instruction, just delete it.
1067   if (MI->isImplicitDef()) {
1068     RemoveMachineInstrFromMaps(MI);
1069     vrm.RemoveMachineInstrFromMaps(MI);
1070     MI->eraseFromParent();
1071     ++numFolds;
1072     return true;
1073   }
1074
1075   // Filter the list of operand indexes that are to be folded. Abort if
1076   // any operand will prevent folding.
1077   unsigned MRInfo = 0;
1078   SmallVector<unsigned, 2> FoldOps;
1079   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1080     return false;
1081
1082   // The only time it's safe to fold into a two address instruction is when
1083   // it's folding reload and spill from / into a spill stack slot.
1084   if (DefMI && (MRInfo & VirtRegMap::isMod))
1085     return false;
1086
1087   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
1088                            : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
1089   if (fmi) {
1090     // Remember this instruction uses the spill slot.
1091     if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1092
1093     // Attempt to fold the memory reference into the instruction. If
1094     // we can do this, we don't need to insert spill code.
1095     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1096       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1097     vrm.transferSpillPts(MI, fmi);
1098     vrm.transferRestorePts(MI, fmi);
1099     vrm.transferEmergencySpills(MI, fmi);
1100     ReplaceMachineInstrInMaps(MI, fmi);
1101     MI->eraseFromParent();
1102     MI = fmi;
1103     ++numFolds;
1104     return true;
1105   }
1106   return false;
1107 }
1108
1109 /// canFoldMemoryOperand - Returns true if the specified load / store
1110 /// folding is possible.
1111 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1112                                          SmallVector<unsigned, 2> &Ops,
1113                                          bool ReMat) const {
1114   // Filter the list of operand indexes that are to be folded. Abort if
1115   // any operand will prevent folding.
1116   unsigned MRInfo = 0;
1117   SmallVector<unsigned, 2> FoldOps;
1118   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1119     return false;
1120
1121   // It's only legal to remat for a use, not a def.
1122   if (ReMat && (MRInfo & VirtRegMap::isMod))
1123     return false;
1124
1125   return tii_->canFoldMemoryOperand(MI, FoldOps);
1126 }
1127
1128 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1129   LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
1130
1131   MachineBasicBlock *mbb =  indexes_->getMBBCoveringRange(itr->start, itr->end);
1132
1133   if (mbb == 0)
1134     return false;
1135
1136   for (++itr; itr != li.ranges.end(); ++itr) {
1137     MachineBasicBlock *mbb2 =
1138       indexes_->getMBBCoveringRange(itr->start, itr->end);
1139
1140     if (mbb2 != mbb)
1141       return false;
1142   }
1143
1144   return true;
1145 }
1146
1147 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1148 /// interval on to-be re-materialized operands of MI) with new register.
1149 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1150                                        MachineInstr *MI, unsigned NewVReg,
1151                                        VirtRegMap &vrm) {
1152   // There is an implicit use. That means one of the other operand is
1153   // being remat'ed and the remat'ed instruction has li.reg as an
1154   // use operand. Make sure we rewrite that as well.
1155   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1156     MachineOperand &MO = MI->getOperand(i);
1157     if (!MO.isReg())
1158       continue;
1159     unsigned Reg = MO.getReg();
1160     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1161       continue;
1162     if (!vrm.isReMaterialized(Reg))
1163       continue;
1164     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1165     MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1166     if (UseMO)
1167       UseMO->setReg(NewVReg);
1168   }
1169 }
1170
1171 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1172 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1173 bool LiveIntervals::
1174 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1175                  bool TrySplit, SlotIndex index, SlotIndex end,
1176                  MachineInstr *MI,
1177                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1178                  unsigned Slot, int LdSlot,
1179                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1180                  VirtRegMap &vrm,
1181                  const TargetRegisterClass* rc,
1182                  SmallVector<int, 4> &ReMatIds,
1183                  const MachineLoopInfo *loopInfo,
1184                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1185                  DenseMap<unsigned,unsigned> &MBBVRegsMap,
1186                  std::vector<LiveInterval*> &NewLIs) {
1187   bool CanFold = false;
1188  RestartInstruction:
1189   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1190     MachineOperand& mop = MI->getOperand(i);
1191     if (!mop.isReg())
1192       continue;
1193     unsigned Reg = mop.getReg();
1194     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1195       continue;
1196     if (Reg != li.reg)
1197       continue;
1198
1199     bool TryFold = !DefIsReMat;
1200     bool FoldSS = true; // Default behavior unless it's a remat.
1201     int FoldSlot = Slot;
1202     if (DefIsReMat) {
1203       // If this is the rematerializable definition MI itself and
1204       // all of its uses are rematerialized, simply delete it.
1205       if (MI == ReMatOrigDefMI && CanDelete) {
1206         DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
1207                      << *MI << '\n');
1208         RemoveMachineInstrFromMaps(MI);
1209         vrm.RemoveMachineInstrFromMaps(MI);
1210         MI->eraseFromParent();
1211         break;
1212       }
1213
1214       // If def for this use can't be rematerialized, then try folding.
1215       // If def is rematerializable and it's a load, also try folding.
1216       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1217       if (isLoad) {
1218         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1219         FoldSS = isLoadSS;
1220         FoldSlot = LdSlot;
1221       }
1222     }
1223
1224     // Scan all of the operands of this instruction rewriting operands
1225     // to use NewVReg instead of li.reg as appropriate.  We do this for
1226     // two reasons:
1227     //
1228     //   1. If the instr reads the same spilled vreg multiple times, we
1229     //      want to reuse the NewVReg.
1230     //   2. If the instr is a two-addr instruction, we are required to
1231     //      keep the src/dst regs pinned.
1232     //
1233     // Keep track of whether we replace a use and/or def so that we can
1234     // create the spill interval with the appropriate range.
1235     SmallVector<unsigned, 2> Ops;
1236     tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
1237
1238     // Create a new virtual register for the spill interval.
1239     // Create the new register now so we can map the fold instruction
1240     // to the new register so when it is unfolded we get the correct
1241     // answer.
1242     bool CreatedNewVReg = false;
1243     if (NewVReg == 0) {
1244       NewVReg = mri_->createVirtualRegister(rc);
1245       vrm.grow();
1246       CreatedNewVReg = true;
1247
1248       // The new virtual register should get the same allocation hints as the
1249       // old one.
1250       std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1251       if (Hint.first || Hint.second)
1252         mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
1253     }
1254
1255     if (!TryFold)
1256       CanFold = false;
1257     else {
1258       // Do not fold load / store here if we are splitting. We'll find an
1259       // optimal point to insert a load / store later.
1260       if (!TrySplit) {
1261         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1262                                  Ops, FoldSS, FoldSlot, NewVReg)) {
1263           // Folding the load/store can completely change the instruction in
1264           // unpredictable ways, rescan it from the beginning.
1265
1266           if (FoldSS) {
1267             // We need to give the new vreg the same stack slot as the
1268             // spilled interval.
1269             vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1270           }
1271
1272           HasUse = false;
1273           HasDef = false;
1274           CanFold = false;
1275           if (isNotInMIMap(MI))
1276             break;
1277           goto RestartInstruction;
1278         }
1279       } else {
1280         // We'll try to fold it later if it's profitable.
1281         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1282       }
1283     }
1284
1285     mop.setReg(NewVReg);
1286     if (mop.isImplicit())
1287       rewriteImplicitOps(li, MI, NewVReg, vrm);
1288
1289     // Reuse NewVReg for other reads.
1290     bool HasEarlyClobber = false;
1291     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1292       MachineOperand &mopj = MI->getOperand(Ops[j]);
1293       mopj.setReg(NewVReg);
1294       if (mopj.isImplicit())
1295         rewriteImplicitOps(li, MI, NewVReg, vrm);
1296       if (mopj.isEarlyClobber())
1297         HasEarlyClobber = true;
1298     }
1299
1300     if (CreatedNewVReg) {
1301       if (DefIsReMat) {
1302         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1303         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1304           // Each valnum may have its own remat id.
1305           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1306         } else {
1307           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1308         }
1309         if (!CanDelete || (HasUse && HasDef)) {
1310           // If this is a two-addr instruction then its use operands are
1311           // rematerializable but its def is not. It should be assigned a
1312           // stack slot.
1313           vrm.assignVirt2StackSlot(NewVReg, Slot);
1314         }
1315       } else {
1316         vrm.assignVirt2StackSlot(NewVReg, Slot);
1317       }
1318     } else if (HasUse && HasDef &&
1319                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1320       // If this interval hasn't been assigned a stack slot (because earlier
1321       // def is a deleted remat def), do it now.
1322       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1323       vrm.assignVirt2StackSlot(NewVReg, Slot);
1324     }
1325
1326     // Re-matting an instruction with virtual register use. Add the
1327     // register as an implicit use on the use MI.
1328     if (DefIsReMat && ImpUse)
1329       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1330
1331     // Create a new register interval for this spill / remat.
1332     LiveInterval &nI = getOrCreateInterval(NewVReg);
1333     if (CreatedNewVReg) {
1334       NewLIs.push_back(&nI);
1335       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1336       if (TrySplit)
1337         vrm.setIsSplitFromReg(NewVReg, li.reg);
1338     }
1339
1340     if (HasUse) {
1341       if (CreatedNewVReg) {
1342         LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
1343                      nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1344         DEBUG(dbgs() << " +" << LR);
1345         nI.addRange(LR);
1346       } else {
1347         // Extend the split live interval to this def / use.
1348         SlotIndex End = index.getDefIndex();
1349         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1350                      nI.getValNumInfo(nI.getNumValNums()-1));
1351         DEBUG(dbgs() << " +" << LR);
1352         nI.addRange(LR);
1353       }
1354     }
1355     if (HasDef) {
1356       // An early clobber starts at the use slot, except for an early clobber
1357       // tied to a use operand (yes, that is a thing).
1358       LiveRange LR(HasEarlyClobber && !HasUse ?
1359                    index.getUseIndex() : index.getDefIndex(),
1360                    index.getStoreIndex(),
1361                    nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1362       DEBUG(dbgs() << " +" << LR);
1363       nI.addRange(LR);
1364     }
1365
1366     DEBUG({
1367         dbgs() << "\t\t\t\tAdded new interval: ";
1368         nI.print(dbgs(), tri_);
1369         dbgs() << '\n';
1370       });
1371   }
1372   return CanFold;
1373 }
1374 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1375                                    const VNInfo *VNI,
1376                                    MachineBasicBlock *MBB,
1377                                    SlotIndex Idx) const {
1378   return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
1379 }
1380
1381 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1382 /// during spilling.
1383 namespace {
1384   struct RewriteInfo {
1385     SlotIndex Index;
1386     MachineInstr *MI;
1387     RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
1388   };
1389
1390   struct RewriteInfoCompare {
1391     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1392       return LHS.Index < RHS.Index;
1393     }
1394   };
1395 }
1396
1397 void LiveIntervals::
1398 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1399                     LiveInterval::Ranges::const_iterator &I,
1400                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1401                     unsigned Slot, int LdSlot,
1402                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1403                     VirtRegMap &vrm,
1404                     const TargetRegisterClass* rc,
1405                     SmallVector<int, 4> &ReMatIds,
1406                     const MachineLoopInfo *loopInfo,
1407                     BitVector &SpillMBBs,
1408                     DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1409                     BitVector &RestoreMBBs,
1410                     DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1411                     DenseMap<unsigned,unsigned> &MBBVRegsMap,
1412                     std::vector<LiveInterval*> &NewLIs) {
1413   bool AllCanFold = true;
1414   unsigned NewVReg = 0;
1415   SlotIndex start = I->start.getBaseIndex();
1416   SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
1417
1418   // First collect all the def / use in this live range that will be rewritten.
1419   // Make sure they are sorted according to instruction index.
1420   std::vector<RewriteInfo> RewriteMIs;
1421   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1422          re = mri_->reg_end(); ri != re; ) {
1423     MachineInstr *MI = &*ri;
1424     MachineOperand &O = ri.getOperand();
1425     ++ri;
1426     if (MI->isDebugValue()) {
1427       // Modify DBG_VALUE now that the value is in a spill slot.
1428       if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
1429         uint64_t Offset = MI->getOperand(1).getImm();
1430         const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1431         DebugLoc DL = MI->getDebugLoc();
1432         int FI = isLoadSS ? LdSlot : (int)Slot;
1433         if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
1434                                                            Offset, MDPtr, DL)) {
1435           DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1436           ReplaceMachineInstrInMaps(MI, NewDV);
1437           MachineBasicBlock *MBB = MI->getParent();
1438           MBB->insert(MBB->erase(MI), NewDV);
1439           continue;
1440         }
1441       }
1442
1443       DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1444       RemoveMachineInstrFromMaps(MI);
1445       vrm.RemoveMachineInstrFromMaps(MI);
1446       MI->eraseFromParent();
1447       continue;
1448     }
1449     assert(!(O.isImplicit() && O.isUse()) &&
1450            "Spilling register that's used as implicit use?");
1451     SlotIndex index = getInstructionIndex(MI);
1452     if (index < start || index >= end)
1453       continue;
1454
1455     if (O.isUndef())
1456       // Must be defined by an implicit def. It should not be spilled. Note,
1457       // this is for correctness reason. e.g.
1458       // 8   %reg1024<def> = IMPLICIT_DEF
1459       // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1460       // The live range [12, 14) are not part of the r1024 live interval since
1461       // it's defined by an implicit def. It will not conflicts with live
1462       // interval of r1025. Now suppose both registers are spilled, you can
1463       // easily see a situation where both registers are reloaded before
1464       // the INSERT_SUBREG and both target registers that would overlap.
1465       continue;
1466     RewriteMIs.push_back(RewriteInfo(index, MI));
1467   }
1468   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1469
1470   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1471   // Now rewrite the defs and uses.
1472   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1473     RewriteInfo &rwi = RewriteMIs[i];
1474     ++i;
1475     SlotIndex index = rwi.Index;
1476     MachineInstr *MI = rwi.MI;
1477     // If MI def and/or use the same register multiple times, then there
1478     // are multiple entries.
1479     while (i != e && RewriteMIs[i].MI == MI) {
1480       assert(RewriteMIs[i].Index == index);
1481       ++i;
1482     }
1483     MachineBasicBlock *MBB = MI->getParent();
1484
1485     if (ImpUse && MI != ReMatDefMI) {
1486       // Re-matting an instruction with virtual register use. Prevent interval
1487       // from being spilled.
1488       getInterval(ImpUse).markNotSpillable();
1489     }
1490
1491     unsigned MBBId = MBB->getNumber();
1492     unsigned ThisVReg = 0;
1493     if (TrySplit) {
1494       DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1495       if (NVI != MBBVRegsMap.end()) {
1496         ThisVReg = NVI->second;
1497         // One common case:
1498         // x = use
1499         // ...
1500         // ...
1501         // def = ...
1502         //     = use
1503         // It's better to start a new interval to avoid artifically
1504         // extend the new interval.
1505         if (MI->readsWritesVirtualRegister(li.reg) ==
1506             std::make_pair(false,true)) {
1507           MBBVRegsMap.erase(MBB->getNumber());
1508           ThisVReg = 0;
1509         }
1510       }
1511     }
1512
1513     bool IsNew = ThisVReg == 0;
1514     if (IsNew) {
1515       // This ends the previous live interval. If all of its def / use
1516       // can be folded, give it a low spill weight.
1517       if (NewVReg && TrySplit && AllCanFold) {
1518         LiveInterval &nI = getOrCreateInterval(NewVReg);
1519         nI.weight /= 10.0F;
1520       }
1521       AllCanFold = true;
1522     }
1523     NewVReg = ThisVReg;
1524
1525     bool HasDef = false;
1526     bool HasUse = false;
1527     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1528                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1529                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1530                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1531                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1532     if (!HasDef && !HasUse)
1533       continue;
1534
1535     AllCanFold &= CanFold;
1536
1537     // Update weight of spill interval.
1538     LiveInterval &nI = getOrCreateInterval(NewVReg);
1539     if (!TrySplit) {
1540       // The spill weight is now infinity as it cannot be spilled again.
1541       nI.markNotSpillable();
1542       continue;
1543     }
1544
1545     // Keep track of the last def and first use in each MBB.
1546     if (HasDef) {
1547       if (MI != ReMatOrigDefMI || !CanDelete) {
1548         bool HasKill = false;
1549         if (!HasUse)
1550           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
1551         else {
1552           // If this is a two-address code, then this index starts a new VNInfo.
1553           const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
1554           if (VNI)
1555             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
1556         }
1557         DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1558           SpillIdxes.find(MBBId);
1559         if (!HasKill) {
1560           if (SII == SpillIdxes.end()) {
1561             std::vector<SRInfo> S;
1562             S.push_back(SRInfo(index, NewVReg, true));
1563             SpillIdxes.insert(std::make_pair(MBBId, S));
1564           } else if (SII->second.back().vreg != NewVReg) {
1565             SII->second.push_back(SRInfo(index, NewVReg, true));
1566           } else if (index > SII->second.back().index) {
1567             // If there is an earlier def and this is a two-address
1568             // instruction, then it's not possible to fold the store (which
1569             // would also fold the load).
1570             SRInfo &Info = SII->second.back();
1571             Info.index = index;
1572             Info.canFold = !HasUse;
1573           }
1574           SpillMBBs.set(MBBId);
1575         } else if (SII != SpillIdxes.end() &&
1576                    SII->second.back().vreg == NewVReg &&
1577                    index > SII->second.back().index) {
1578           // There is an earlier def that's not killed (must be two-address).
1579           // The spill is no longer needed.
1580           SII->second.pop_back();
1581           if (SII->second.empty()) {
1582             SpillIdxes.erase(MBBId);
1583             SpillMBBs.reset(MBBId);
1584           }
1585         }
1586       }
1587     }
1588
1589     if (HasUse) {
1590       DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1591         SpillIdxes.find(MBBId);
1592       if (SII != SpillIdxes.end() &&
1593           SII->second.back().vreg == NewVReg &&
1594           index > SII->second.back().index)
1595         // Use(s) following the last def, it's not safe to fold the spill.
1596         SII->second.back().canFold = false;
1597       DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1598         RestoreIdxes.find(MBBId);
1599       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1600         // If we are splitting live intervals, only fold if it's the first
1601         // use and there isn't another use later in the MBB.
1602         RII->second.back().canFold = false;
1603       else if (IsNew) {
1604         // Only need a reload if there isn't an earlier def / use.
1605         if (RII == RestoreIdxes.end()) {
1606           std::vector<SRInfo> Infos;
1607           Infos.push_back(SRInfo(index, NewVReg, true));
1608           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1609         } else {
1610           RII->second.push_back(SRInfo(index, NewVReg, true));
1611         }
1612         RestoreMBBs.set(MBBId);
1613       }
1614     }
1615
1616     // Update spill weight.
1617     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1618     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1619   }
1620
1621   if (NewVReg && TrySplit && AllCanFold) {
1622     // If all of its def / use can be folded, give it a low spill weight.
1623     LiveInterval &nI = getOrCreateInterval(NewVReg);
1624     nI.weight /= 10.0F;
1625   }
1626 }
1627
1628 bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
1629                         unsigned vr, BitVector &RestoreMBBs,
1630                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1631   if (!RestoreMBBs[Id])
1632     return false;
1633   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1634   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1635     if (Restores[i].index == index &&
1636         Restores[i].vreg == vr &&
1637         Restores[i].canFold)
1638       return true;
1639   return false;
1640 }
1641
1642 void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
1643                         unsigned vr, BitVector &RestoreMBBs,
1644                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1645   if (!RestoreMBBs[Id])
1646     return;
1647   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1648   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1649     if (Restores[i].index == index && Restores[i].vreg)
1650       Restores[i].index = SlotIndex();
1651 }
1652
1653 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1654 /// spilled and create empty intervals for their uses.
1655 void
1656 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1657                                     const TargetRegisterClass* rc,
1658                                     std::vector<LiveInterval*> &NewLIs) {
1659   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1660          re = mri_->reg_end(); ri != re; ) {
1661     MachineOperand &O = ri.getOperand();
1662     MachineInstr *MI = &*ri;
1663     ++ri;
1664     if (MI->isDebugValue()) {
1665       // Remove debug info for now.
1666       O.setReg(0U);
1667       DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1668       continue;
1669     }
1670     if (O.isDef()) {
1671       assert(MI->isImplicitDef() &&
1672              "Register def was not rewritten?");
1673       RemoveMachineInstrFromMaps(MI);
1674       vrm.RemoveMachineInstrFromMaps(MI);
1675       MI->eraseFromParent();
1676     } else {
1677       // This must be an use of an implicit_def so it's not part of the live
1678       // interval. Create a new empty live interval for it.
1679       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1680       unsigned NewVReg = mri_->createVirtualRegister(rc);
1681       vrm.grow();
1682       vrm.setIsImplicitlyDefined(NewVReg);
1683       NewLIs.push_back(&getOrCreateInterval(NewVReg));
1684       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1685         MachineOperand &MO = MI->getOperand(i);
1686         if (MO.isReg() && MO.getReg() == li.reg) {
1687           MO.setReg(NewVReg);
1688           MO.setIsUndef();
1689         }
1690       }
1691     }
1692   }
1693 }
1694
1695 float
1696 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1697   // Limit the loop depth ridiculousness.
1698   if (loopDepth > 200)
1699     loopDepth = 200;
1700
1701   // The loop depth is used to roughly estimate the number of times the
1702   // instruction is executed. Something like 10^d is simple, but will quickly
1703   // overflow a float. This expression behaves like 10^d for small d, but is
1704   // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1705   // headroom before overflow.
1706   float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth);
1707
1708   return (isDef + isUse) * lc;
1709 }
1710
1711 static void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
1712   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1713     NewLIs[i]->weight =
1714       normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize());
1715 }
1716
1717 std::vector<LiveInterval*> LiveIntervals::
1718 addIntervalsForSpills(const LiveInterval &li,
1719                       const SmallVectorImpl<LiveInterval*> *SpillIs,
1720                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1721   assert(li.isSpillable() && "attempt to spill already spilled interval!");
1722
1723   DEBUG({
1724       dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1725       li.print(dbgs(), tri_);
1726       dbgs() << '\n';
1727     });
1728
1729   // Each bit specify whether a spill is required in the MBB.
1730   BitVector SpillMBBs(mf_->getNumBlockIDs());
1731   DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
1732   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1733   DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1734   DenseMap<unsigned,unsigned> MBBVRegsMap;
1735   std::vector<LiveInterval*> NewLIs;
1736   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1737
1738   unsigned NumValNums = li.getNumValNums();
1739   SmallVector<MachineInstr*, 4> ReMatDefs;
1740   ReMatDefs.resize(NumValNums, NULL);
1741   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1742   ReMatOrigDefs.resize(NumValNums, NULL);
1743   SmallVector<int, 4> ReMatIds;
1744   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1745   BitVector ReMatDelete(NumValNums);
1746   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1747
1748   // Spilling a split live interval. It cannot be split any further. Also,
1749   // it's also guaranteed to be a single val# / range interval.
1750   if (vrm.getPreSplitReg(li.reg)) {
1751     vrm.setIsSplitFromReg(li.reg, 0);
1752     // Unset the split kill marker on the last use.
1753     SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1754     if (KillIdx != SlotIndex()) {
1755       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1756       assert(KillMI && "Last use disappeared?");
1757       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1758       assert(KillOp != -1 && "Last use disappeared?");
1759       KillMI->getOperand(KillOp).setIsKill(false);
1760     }
1761     vrm.removeKillPoint(li.reg);
1762     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1763     Slot = vrm.getStackSlot(li.reg);
1764     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1765     MachineInstr *ReMatDefMI = DefIsReMat ?
1766       vrm.getReMaterializedMI(li.reg) : NULL;
1767     int LdSlot = 0;
1768     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1769     bool isLoad = isLoadSS ||
1770       (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
1771     bool IsFirstRange = true;
1772     for (LiveInterval::Ranges::const_iterator
1773            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1774       // If this is a split live interval with multiple ranges, it means there
1775       // are two-address instructions that re-defined the value. Only the
1776       // first def can be rematerialized!
1777       if (IsFirstRange) {
1778         // Note ReMatOrigDefMI has already been deleted.
1779         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1780                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1781                              false, vrm, rc, ReMatIds, loopInfo,
1782                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1783                              MBBVRegsMap, NewLIs);
1784       } else {
1785         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1786                              Slot, 0, false, false, false,
1787                              false, vrm, rc, ReMatIds, loopInfo,
1788                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1789                              MBBVRegsMap, NewLIs);
1790       }
1791       IsFirstRange = false;
1792     }
1793
1794     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1795     normalizeSpillWeights(NewLIs);
1796     return NewLIs;
1797   }
1798
1799   bool TrySplit = !intervalIsInOneMBB(li);
1800   if (TrySplit)
1801     ++numSplits;
1802   bool NeedStackSlot = false;
1803   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1804        i != e; ++i) {
1805     const VNInfo *VNI = *i;
1806     unsigned VN = VNI->id;
1807     if (VNI->isUnused())
1808       continue; // Dead val#.
1809     // Is the def for the val# rematerializable?
1810     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1811     bool dummy;
1812     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
1813       // Remember how to remat the def of this val#.
1814       ReMatOrigDefs[VN] = ReMatDefMI;
1815       // Original def may be modified so we have to make a copy here.
1816       MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
1817       CloneMIs.push_back(Clone);
1818       ReMatDefs[VN] = Clone;
1819
1820       bool CanDelete = true;
1821       if (VNI->hasPHIKill()) {
1822         // A kill is a phi node, not all of its uses can be rematerialized.
1823         // It must not be deleted.
1824         CanDelete = false;
1825         // Need a stack slot if there is any live range where uses cannot be
1826         // rematerialized.
1827         NeedStackSlot = true;
1828       }
1829       if (CanDelete)
1830         ReMatDelete.set(VN);
1831     } else {
1832       // Need a stack slot if there is any live range where uses cannot be
1833       // rematerialized.
1834       NeedStackSlot = true;
1835     }
1836   }
1837
1838   // One stack slot per live interval.
1839   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1840     if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1841       Slot = vrm.assignVirt2StackSlot(li.reg);
1842
1843     // This case only occurs when the prealloc splitter has already assigned
1844     // a stack slot to this vreg.
1845     else
1846       Slot = vrm.getStackSlot(li.reg);
1847   }
1848
1849   // Create new intervals and rewrite defs and uses.
1850   for (LiveInterval::Ranges::const_iterator
1851          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1852     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1853     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1854     bool DefIsReMat = ReMatDefMI != NULL;
1855     bool CanDelete = ReMatDelete[I->valno->id];
1856     int LdSlot = 0;
1857     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1858     bool isLoad = isLoadSS ||
1859       (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
1860     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1861                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1862                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1863                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1864                                MBBVRegsMap, NewLIs);
1865   }
1866
1867   // Insert spills / restores if we are splitting.
1868   if (!TrySplit) {
1869     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1870     normalizeSpillWeights(NewLIs);
1871     return NewLIs;
1872   }
1873
1874   SmallPtrSet<LiveInterval*, 4> AddedKill;
1875   SmallVector<unsigned, 2> Ops;
1876   if (NeedStackSlot) {
1877     int Id = SpillMBBs.find_first();
1878     while (Id != -1) {
1879       std::vector<SRInfo> &spills = SpillIdxes[Id];
1880       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1881         SlotIndex index = spills[i].index;
1882         unsigned VReg = spills[i].vreg;
1883         LiveInterval &nI = getOrCreateInterval(VReg);
1884         bool isReMat = vrm.isReMaterialized(VReg);
1885         MachineInstr *MI = getInstructionFromIndex(index);
1886         bool CanFold = false;
1887         bool FoundUse = false;
1888         Ops.clear();
1889         if (spills[i].canFold) {
1890           CanFold = true;
1891           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1892             MachineOperand &MO = MI->getOperand(j);
1893             if (!MO.isReg() || MO.getReg() != VReg)
1894               continue;
1895
1896             Ops.push_back(j);
1897             if (MO.isDef())
1898               continue;
1899             if (isReMat ||
1900                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1901                                                 RestoreMBBs, RestoreIdxes))) {
1902               // MI has two-address uses of the same register. If the use
1903               // isn't the first and only use in the BB, then we can't fold
1904               // it. FIXME: Move this to rewriteInstructionsForSpills.
1905               CanFold = false;
1906               break;
1907             }
1908             FoundUse = true;
1909           }
1910         }
1911         // Fold the store into the def if possible.
1912         bool Folded = false;
1913         if (CanFold && !Ops.empty()) {
1914           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1915             Folded = true;
1916             if (FoundUse) {
1917               // Also folded uses, do not issue a load.
1918               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1919               nI.removeRange(index.getLoadIndex(), index.getDefIndex());
1920             }
1921             nI.removeRange(index.getDefIndex(), index.getStoreIndex());
1922           }
1923         }
1924
1925         // Otherwise tell the spiller to issue a spill.
1926         if (!Folded) {
1927           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1928           bool isKill = LR->end == index.getStoreIndex();
1929           if (!MI->registerDefIsDead(nI.reg))
1930             // No need to spill a dead def.
1931             vrm.addSpillPoint(VReg, isKill, MI);
1932           if (isKill)
1933             AddedKill.insert(&nI);
1934         }
1935       }
1936       Id = SpillMBBs.find_next(Id);
1937     }
1938   }
1939
1940   int Id = RestoreMBBs.find_first();
1941   while (Id != -1) {
1942     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1943     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1944       SlotIndex index = restores[i].index;
1945       if (index == SlotIndex())
1946         continue;
1947       unsigned VReg = restores[i].vreg;
1948       LiveInterval &nI = getOrCreateInterval(VReg);
1949       bool isReMat = vrm.isReMaterialized(VReg);
1950       MachineInstr *MI = getInstructionFromIndex(index);
1951       bool CanFold = false;
1952       Ops.clear();
1953       if (restores[i].canFold) {
1954         CanFold = true;
1955         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1956           MachineOperand &MO = MI->getOperand(j);
1957           if (!MO.isReg() || MO.getReg() != VReg)
1958             continue;
1959
1960           if (MO.isDef()) {
1961             // If this restore were to be folded, it would have been folded
1962             // already.
1963             CanFold = false;
1964             break;
1965           }
1966           Ops.push_back(j);
1967         }
1968       }
1969
1970       // Fold the load into the use if possible.
1971       bool Folded = false;
1972       if (CanFold && !Ops.empty()) {
1973         if (!isReMat)
1974           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1975         else {
1976           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1977           int LdSlot = 0;
1978           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1979           // If the rematerializable def is a load, also try to fold it.
1980           if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
1981             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1982                                           Ops, isLoadSS, LdSlot, VReg);
1983           if (!Folded) {
1984             unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1985             if (ImpUse) {
1986               // Re-matting an instruction with virtual register use. Add the
1987               // register as an implicit use on the use MI and mark the register
1988               // interval as unspillable.
1989               LiveInterval &ImpLi = getInterval(ImpUse);
1990               ImpLi.markNotSpillable();
1991               MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1992             }
1993           }
1994         }
1995       }
1996       // If folding is not possible / failed, then tell the spiller to issue a
1997       // load / rematerialization for us.
1998       if (Folded)
1999         nI.removeRange(index.getLoadIndex(), index.getDefIndex());
2000       else
2001         vrm.addRestorePoint(VReg, MI);
2002     }
2003     Id = RestoreMBBs.find_next(Id);
2004   }
2005
2006   // Finalize intervals: add kills, finalize spill weights, and filter out
2007   // dead intervals.
2008   std::vector<LiveInterval*> RetNewLIs;
2009   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2010     LiveInterval *LI = NewLIs[i];
2011     if (!LI->empty()) {
2012       if (!AddedKill.count(LI)) {
2013         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2014         SlotIndex LastUseIdx = LR->end.getBaseIndex();
2015         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2016         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2017         assert(UseIdx != -1);
2018         if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2019           LastUse->getOperand(UseIdx).setIsKill();
2020           vrm.addKillPoint(LI->reg, LastUseIdx);
2021         }
2022       }
2023       RetNewLIs.push_back(LI);
2024     }
2025   }
2026
2027   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2028   normalizeSpillWeights(RetNewLIs);
2029   return RetNewLIs;
2030 }
2031
2032 /// hasAllocatableSuperReg - Return true if the specified physical register has
2033 /// any super register that's allocatable.
2034 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2035   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2036     if (allocatableRegs_[*AS] && hasInterval(*AS))
2037       return true;
2038   return false;
2039 }
2040
2041 /// getRepresentativeReg - Find the largest super register of the specified
2042 /// physical register.
2043 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2044   // Find the largest super-register that is allocatable.
2045   unsigned BestReg = Reg;
2046   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2047     unsigned SuperReg = *AS;
2048     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2049       BestReg = SuperReg;
2050       break;
2051     }
2052   }
2053   return BestReg;
2054 }
2055
2056 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2057 /// specified interval that conflicts with the specified physical register.
2058 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2059                                                    unsigned PhysReg) const {
2060   unsigned NumConflicts = 0;
2061   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2062   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2063          E = mri_->reg_end(); I != E; ++I) {
2064     MachineOperand &O = I.getOperand();
2065     MachineInstr *MI = O.getParent();
2066     if (MI->isDebugValue())
2067       continue;
2068     SlotIndex Index = getInstructionIndex(MI);
2069     if (pli.liveAt(Index))
2070       ++NumConflicts;
2071   }
2072   return NumConflicts;
2073 }
2074
2075 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2076 /// around all defs and uses of the specified interval. Return true if it
2077 /// was able to cut its interval.
2078 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2079                                             unsigned PhysReg, VirtRegMap &vrm) {
2080   unsigned SpillReg = getRepresentativeReg(PhysReg);
2081
2082   DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
2083                << " represented by " << tri_->getName(SpillReg) << '\n');
2084
2085   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2086     // If there are registers which alias PhysReg, but which are not a
2087     // sub-register of the chosen representative super register. Assert
2088     // since we can't handle it yet.
2089     assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2090            tri_->isSuperRegister(*AS, SpillReg));
2091
2092   bool Cut = false;
2093   SmallVector<unsigned, 4> PRegs;
2094   if (hasInterval(SpillReg))
2095     PRegs.push_back(SpillReg);
2096   for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
2097     if (hasInterval(*SR))
2098       PRegs.push_back(*SR);
2099
2100   DEBUG({
2101     dbgs() << "Trying to spill:";
2102     for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
2103       dbgs() << ' ' << tri_->getName(PRegs[i]);
2104     dbgs() << '\n';
2105   });
2106
2107   SmallPtrSet<MachineInstr*, 8> SeenMIs;
2108   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2109          E = mri_->reg_end(); I != E; ++I) {
2110     MachineOperand &O = I.getOperand();
2111     MachineInstr *MI = O.getParent();
2112     if (MI->isDebugValue() || SeenMIs.count(MI))
2113       continue;
2114     SeenMIs.insert(MI);
2115     SlotIndex Index = getInstructionIndex(MI);
2116     bool LiveReg = false;
2117     for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
2118       unsigned PReg = PRegs[i];
2119       LiveInterval &pli = getInterval(PReg);
2120       if (!pli.liveAt(Index))
2121         continue;
2122       LiveReg = true;
2123       SlotIndex StartIdx = Index.getLoadIndex();
2124       SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
2125       if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
2126         std::string msg;
2127         raw_string_ostream Msg(msg);
2128         Msg << "Ran out of registers during register allocation!";
2129         if (MI->isInlineAsm()) {
2130           Msg << "\nPlease check your inline asm statement for invalid "
2131               << "constraints:\n";
2132           MI->print(Msg, tm_);
2133         }
2134         report_fatal_error(Msg.str());
2135       }
2136       pli.removeRange(StartIdx, EndIdx);
2137       LiveReg = true;
2138     }
2139     if (!LiveReg)
2140       continue;
2141     DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
2142     vrm.addEmergencySpill(SpillReg, MI);
2143     Cut = true;
2144   }
2145   return Cut;
2146 }
2147
2148 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2149                                                   MachineInstr* startInst) {
2150   LiveInterval& Interval = getOrCreateInterval(reg);
2151   VNInfo* VN = Interval.getNextValue(
2152     SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2153     startInst, getVNInfoAllocator());
2154   VN->setHasPHIKill(true);
2155   LiveRange LR(
2156      SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2157      getMBBEndIdx(startInst->getParent()), VN);
2158   Interval.addRange(LR);
2159
2160   return LR;
2161 }
2162