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 bool 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     if (!VNI) {
 765       // This shouldn't happen: readsVirtualRegister returns true, but there is
 766       // no live value. It is likely caused by a target getting <undef> flags
 767       // wrong.
 768       DEBUG(dbgs() << Idx << '\t' << *UseMI
 769                    << "Warning: Instr claims to read non-existent value in "
 770                     << *li << '\n');
 771       continue;
 772     }
 773     if (VNI->def == Idx) {
 774       // Special case: An early-clobber tied operand reads and writes the
 775       // register one slot early.
 776       Idx = Idx.getPrevSlot();
 777       VNI = li->getVNInfoAt(Idx);
 778       assert(VNI && "Early-clobber tied value not available");
 779     }
 780     WorkList.push_back(std::make_pair(Idx, VNI));
 781   }
 782
 783   // Create a new live interval with only minimal live segments per def.
 784   LiveInterval NewLI(li->reg, 0);
 785   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 786        I != E; ++I) {
 787     VNInfo *VNI = *I;
 788     if (VNI->isUnused())
 789       continue;
 790     NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
 791
 792     // A use tied to an early-clobber def ends at the load slot and isn't caught
 793     // above. Catch it here instead. This probably only ever happens for inline
 794     // assembly.
 795     if (VNI->def.isUse())
 796       if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
 797         WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
 798   }
 799
 800   // Keep track of the PHIs that are in use.
 801   SmallPtrSet<VNInfo*, 8> UsedPHIs;
 802
 803   // Extend intervals to reach all uses in WorkList.
 804   while (!WorkList.empty()) {
 805     SlotIndex Idx = WorkList.back().first;
 806     VNInfo *VNI = WorkList.back().second;
 807     WorkList.pop_back();
 808     const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
 809     SlotIndex BlockStart = getMBBStartIdx(MBB);
 810
 811     // Extend the live range for VNI to be live at Idx.
 812     if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
 813       (void)ExtVNI;
 814       assert(ExtVNI == VNI && "Unexpected existing value number");
 815       // Is this a PHIDef we haven't seen before?
 816       if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
 817         continue;
 818       // The PHI is live, make sure the predecessors are live-out.
 819       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 820            PE = MBB->pred_end(); PI != PE; ++PI) {
 821         SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
 822         VNInfo *PVNI = li->getVNInfoAt(Stop);
 823         // A predecessor is not required to have a live-out value for a PHI.
 824         if (PVNI) {
 825           assert(PVNI->hasPHIKill() && "Missing hasPHIKill flag");
 826           WorkList.push_back(std::make_pair(Stop, PVNI));
 827         }
 828       }
 829       continue;
 830     }
 831
 832     // VNI is live-in to MBB.
 833     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
 834     NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
 835
 836     // Make sure VNI is live-out from the predecessors.
 837     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 838          PE = MBB->pred_end(); PI != PE; ++PI) {
 839       SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
 840       assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
 841       WorkList.push_back(std::make_pair(Stop, VNI));
 842     }
 843   }
 844
 845   // Handle dead values.
 846   bool CanSeparate = false;
 847   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 848        I != E; ++I) {
 849     VNInfo *VNI = *I;
 850     if (VNI->isUnused())
 851       continue;
 852     LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
 853     assert(LII != NewLI.end() && "Missing live range for PHI");
 854     if (LII->end != VNI->def.getNextSlot())
 855       continue;
 856     if (VNI->isPHIDef()) {
 857       // This is a dead PHI. Remove it.
 858       VNI->setIsUnused(true);
 859       NewLI.removeRange(*LII);
 860       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 861       CanSeparate = true;
 862     } else {
 863       // This is a dead def. Make sure the instruction knows.
 864       MachineInstr *MI = getInstructionFromIndex(VNI->def);
 865       assert(MI && "No instruction defining live value");
 866       MI->addRegisterDead(li->reg, tri_);
 867       if (dead && MI->allDefsAreDead()) {
 868         DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
 869         dead->push_back(MI);
 870       }
 871     }
 872   }
 873
 874   // Move the trimmed ranges back.
 875   li->ranges.swap(NewLI.ranges);
 876   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
 877   return CanSeparate;
 878 }
 879
 880
 881 //===----------------------------------------------------------------------===//
 882 // Register allocator hooks.
 883 //
 884
 885 MachineBasicBlock::iterator
 886 LiveIntervals::getLastSplitPoint(const LiveInterval &li,
 887                                  MachineBasicBlock *mbb) const {
 888   const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
 889
 890   // If li is not live into a landing pad, we can insert spill code before the
 891   // first terminator.
 892   if (!lpad || !isLiveInToMBB(li, lpad))
 893     return mbb->getFirstTerminator();
 894
 895   // When there is a landing pad, spill code must go before the call instruction
 896   // that can throw.
 897   MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
 898   while (I != B) {
 899     --I;
 900     if (I->getDesc().isCall())
 901       return I;
 902   }
 903   // The block contains no calls that can throw, so use the first terminator.
 904   return mbb->getFirstTerminator();
 905 }
 906
 907 void LiveIntervals::addKillFlags() {
 908   for (iterator I = begin(), E = end(); I != E; ++I) {
 909     unsigned Reg = I->first;
 910     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 911       continue;
 912     if (mri_->reg_nodbg_empty(Reg))
 913       continue;
 914     LiveInterval *LI = I->second;
 915
 916     // Every instruction that kills Reg corresponds to a live range end point.
 917     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
 918          ++RI) {
 919       // A LOAD index indicates an MBB edge.
 920       if (RI->end.isLoad())
 921         continue;
 922       MachineInstr *MI = getInstructionFromIndex(RI->end);
 923       if (!MI)
 924         continue;
 925       MI->addRegisterKilled(Reg, NULL);
 926     }
 927   }
 928 }
 929
 930 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
 931 /// allow one) virtual register operand, then its uses are implicitly using
 932 /// the register. Returns the virtual register.
 933 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
 934                                             MachineInstr *MI) const {
 935   unsigned RegOp = 0;
 936   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 937     MachineOperand &MO = MI->getOperand(i);
 938     if (!MO.isReg() || !MO.isUse())
 939       continue;
 940     unsigned Reg = MO.getReg();
 941     if (Reg == 0 || Reg == li.reg)
 942       continue;
 943
 944     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
 945         !allocatableRegs_[Reg])
 946       continue;
 947     // FIXME: For now, only remat MI with at most one register operand.
 948     assert(!RegOp &&
 949            "Can't rematerialize instruction with multiple register operand!");
 950     RegOp = MO.getReg();
 951 #ifndef NDEBUG
 952     break;
 953 #endif
 954   }
 955   return RegOp;
 956 }
 957
 958 /// isValNoAvailableAt - Return true if the val# of the specified interval
 959 /// which reaches the given instruction also reaches the specified use index.
 960 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
 961                                        SlotIndex UseIdx) const {
 962   VNInfo *UValNo = li.getVNInfoAt(UseIdx);
 963   return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
 964 }
 965
 966 /// isReMaterializable - Returns true if the definition MI of the specified
 967 /// val# of the specified interval is re-materializable.
 968 bool
 969 LiveIntervals::isReMaterializable(const LiveInterval &li,
 970                                   const VNInfo *ValNo, MachineInstr *MI,
 971                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
 972                                   bool &isLoad) {
 973   if (DisableReMat)
 974     return false;
 975
 976   if (!tii_->isTriviallyReMaterializable(MI, aa_))
 977     return false;
 978
 979   // Target-specific code can mark an instruction as being rematerializable
 980   // if it has one virtual reg use, though it had better be something like
 981   // a PIC base register which is likely to be live everywhere.
 982   unsigned ImpUse = getReMatImplicitUse(li, MI);
 983   if (ImpUse) {
 984     const LiveInterval &ImpLi = getInterval(ImpUse);
 985     for (MachineRegisterInfo::use_nodbg_iterator
 986            ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
 987          ri != re; ++ri) {
 988       MachineInstr *UseMI = &*ri;
 989       SlotIndex UseIdx = getInstructionIndex(UseMI);
 990       if (li.getVNInfoAt(UseIdx) != ValNo)
 991         continue;
 992       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
 993         return false;
 994     }
 995
 996     // If a register operand of the re-materialized instruction is going to
 997     // be spilled next, then it's not legal to re-materialize this instruction.
 998     if (SpillIs)
 999       for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
1000         if (ImpUse == (*SpillIs)[i]->reg)
1001           return false;
1002   }
1003   return true;
1004 }
1005
1006 /// isReMaterializable - Returns true if the definition MI of the specified
1007 /// val# of the specified interval is re-materializable.
1008 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1009                                        const VNInfo *ValNo, MachineInstr *MI) {
1010   bool Dummy2;
1011   return isReMaterializable(li, ValNo, MI, 0, Dummy2);
1012 }
1013
1014 /// isReMaterializable - Returns true if every definition of MI of every
1015 /// val# of the specified interval is re-materializable.
1016 bool
1017 LiveIntervals::isReMaterializable(const LiveInterval &li,
1018                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
1019                                   bool &isLoad) {
1020   isLoad = false;
1021   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1022        i != e; ++i) {
1023     const VNInfo *VNI = *i;
1024     if (VNI->isUnused())
1025       continue; // Dead val#.
1026     // Is the def for the val# rematerializable?
1027     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1028     if (!ReMatDefMI)
1029       return false;
1030     bool DefIsLoad = false;
1031     if (!ReMatDefMI ||
1032         !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1033       return false;
1034     isLoad |= DefIsLoad;
1035   }
1036   return true;
1037 }
1038
1039 /// FilterFoldedOps - Filter out two-address use operands. Return
1040 /// true if it finds any issue with the operands that ought to prevent
1041 /// folding.
1042 static bool FilterFoldedOps(MachineInstr *MI,
1043                             SmallVector<unsigned, 2> &Ops,
1044                             unsigned &MRInfo,
1045                             SmallVector<unsigned, 2> &FoldOps) {
1046   MRInfo = 0;
1047   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1048     unsigned OpIdx = Ops[i];
1049     MachineOperand &MO = MI->getOperand(OpIdx);
1050     // FIXME: fold subreg use.
1051     if (MO.getSubReg())
1052       return true;
1053     if (MO.isDef())
1054       MRInfo |= (unsigned)VirtRegMap::isMod;
1055     else {
1056       // Filter out two-address use operand(s).
1057       if (MI->isRegTiedToDefOperand(OpIdx)) {
1058         MRInfo = VirtRegMap::isModRef;
1059         continue;
1060       }
1061       MRInfo |= (unsigned)VirtRegMap::isRef;
1062     }
1063     FoldOps.push_back(OpIdx);
1064   }
1065   return false;
1066 }
1067
1068
1069 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1070 /// slot / to reg or any rematerialized load into ith operand of specified
1071 /// MI. If it is successul, MI is updated with the newly created MI and
1072 /// returns true.
1073 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1074                                          VirtRegMap &vrm, MachineInstr *DefMI,
1075                                          SlotIndex InstrIdx,
1076                                          SmallVector<unsigned, 2> &Ops,
1077                                          bool isSS, int Slot, unsigned Reg) {
1078   // If it is an implicit def instruction, just delete it.
1079   if (MI->isImplicitDef()) {
1080     RemoveMachineInstrFromMaps(MI);
1081     vrm.RemoveMachineInstrFromMaps(MI);
1082     MI->eraseFromParent();
1083     ++numFolds;
1084     return true;
1085   }
1086
1087   // Filter the list of operand indexes that are to be folded. Abort if
1088   // any operand will prevent folding.
1089   unsigned MRInfo = 0;
1090   SmallVector<unsigned, 2> FoldOps;
1091   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1092     return false;
1093
1094   // The only time it's safe to fold into a two address instruction is when
1095   // it's folding reload and spill from / into a spill stack slot.
1096   if (DefMI && (MRInfo & VirtRegMap::isMod))
1097     return false;
1098
1099   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
1100                            : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
1101   if (fmi) {
1102     // Remember this instruction uses the spill slot.
1103     if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1104
1105     // Attempt to fold the memory reference into the instruction. If
1106     // we can do this, we don't need to insert spill code.
1107     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
1108       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
1109     vrm.transferSpillPts(MI, fmi);
1110     vrm.transferRestorePts(MI, fmi);
1111     vrm.transferEmergencySpills(MI, fmi);
1112     ReplaceMachineInstrInMaps(MI, fmi);
1113     MI->eraseFromParent();
1114     MI = fmi;
1115     ++numFolds;
1116     return true;
1117   }
1118   return false;
1119 }
1120
1121 /// canFoldMemoryOperand - Returns true if the specified load / store
1122 /// folding is possible.
1123 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
1124                                          SmallVector<unsigned, 2> &Ops,
1125                                          bool ReMat) const {
1126   // Filter the list of operand indexes that are to be folded. Abort if
1127   // any operand will prevent folding.
1128   unsigned MRInfo = 0;
1129   SmallVector<unsigned, 2> FoldOps;
1130   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1131     return false;
1132
1133   // It's only legal to remat for a use, not a def.
1134   if (ReMat && (MRInfo & VirtRegMap::isMod))
1135     return false;
1136
1137   return tii_->canFoldMemoryOperand(MI, FoldOps);
1138 }
1139
1140 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
1141   LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
1142
1143   MachineBasicBlock *mbb =  indexes_->getMBBCoveringRange(itr->start, itr->end);
1144
1145   if (mbb == 0)
1146     return false;
1147
1148   for (++itr; itr != li.ranges.end(); ++itr) {
1149     MachineBasicBlock *mbb2 =
1150       indexes_->getMBBCoveringRange(itr->start, itr->end);
1151
1152     if (mbb2 != mbb)
1153       return false;
1154   }
1155
1156   return true;
1157 }
1158
1159 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1160 /// interval on to-be re-materialized operands of MI) with new register.
1161 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1162                                        MachineInstr *MI, unsigned NewVReg,
1163                                        VirtRegMap &vrm) {
1164   // There is an implicit use. That means one of the other operand is
1165   // being remat'ed and the remat'ed instruction has li.reg as an
1166   // use operand. Make sure we rewrite that as well.
1167   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1168     MachineOperand &MO = MI->getOperand(i);
1169     if (!MO.isReg())
1170       continue;
1171     unsigned Reg = MO.getReg();
1172     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1173       continue;
1174     if (!vrm.isReMaterialized(Reg))
1175       continue;
1176     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
1177     MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1178     if (UseMO)
1179       UseMO->setReg(NewVReg);
1180   }
1181 }
1182
1183 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1184 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
1185 bool LiveIntervals::
1186 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
1187                  bool TrySplit, SlotIndex index, SlotIndex end,
1188                  MachineInstr *MI,
1189                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1190                  unsigned Slot, int LdSlot,
1191                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1192                  VirtRegMap &vrm,
1193                  const TargetRegisterClass* rc,
1194                  SmallVector<int, 4> &ReMatIds,
1195                  const MachineLoopInfo *loopInfo,
1196                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
1197                  DenseMap<unsigned,unsigned> &MBBVRegsMap,
1198                  std::vector<LiveInterval*> &NewLIs) {
1199   bool CanFold = false;
1200  RestartInstruction:
1201   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1202     MachineOperand& mop = MI->getOperand(i);
1203     if (!mop.isReg())
1204       continue;
1205     unsigned Reg = mop.getReg();
1206     if (!TargetRegisterInfo::isVirtualRegister(Reg))
1207       continue;
1208     if (Reg != li.reg)
1209       continue;
1210
1211     bool TryFold = !DefIsReMat;
1212     bool FoldSS = true; // Default behavior unless it's a remat.
1213     int FoldSlot = Slot;
1214     if (DefIsReMat) {
1215       // If this is the rematerializable definition MI itself and
1216       // all of its uses are rematerialized, simply delete it.
1217       if (MI == ReMatOrigDefMI && CanDelete) {
1218         DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
1219                      << *MI << '\n');
1220         RemoveMachineInstrFromMaps(MI);
1221         vrm.RemoveMachineInstrFromMaps(MI);
1222         MI->eraseFromParent();
1223         break;
1224       }
1225
1226       // If def for this use can't be rematerialized, then try folding.
1227       // If def is rematerializable and it's a load, also try folding.
1228       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1229       if (isLoad) {
1230         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1231         FoldSS = isLoadSS;
1232         FoldSlot = LdSlot;
1233       }
1234     }
1235
1236     // Scan all of the operands of this instruction rewriting operands
1237     // to use NewVReg instead of li.reg as appropriate.  We do this for
1238     // two reasons:
1239     //
1240     //   1. If the instr reads the same spilled vreg multiple times, we
1241     //      want to reuse the NewVReg.
1242     //   2. If the instr is a two-addr instruction, we are required to
1243     //      keep the src/dst regs pinned.
1244     //
1245     // Keep track of whether we replace a use and/or def so that we can
1246     // create the spill interval with the appropriate range.
1247     SmallVector<unsigned, 2> Ops;
1248     tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
1249
1250     // Create a new virtual register for the spill interval.
1251     // Create the new register now so we can map the fold instruction
1252     // to the new register so when it is unfolded we get the correct
1253     // answer.
1254     bool CreatedNewVReg = false;
1255     if (NewVReg == 0) {
1256       NewVReg = mri_->createVirtualRegister(rc);
1257       vrm.grow();
1258       CreatedNewVReg = true;
1259
1260       // The new virtual register should get the same allocation hints as the
1261       // old one.
1262       std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1263       if (Hint.first || Hint.second)
1264         mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
1265     }
1266
1267     if (!TryFold)
1268       CanFold = false;
1269     else {
1270       // Do not fold load / store here if we are splitting. We'll find an
1271       // optimal point to insert a load / store later.
1272       if (!TrySplit) {
1273         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1274                                  Ops, FoldSS, FoldSlot, NewVReg)) {
1275           // Folding the load/store can completely change the instruction in
1276           // unpredictable ways, rescan it from the beginning.
1277
1278           if (FoldSS) {
1279             // We need to give the new vreg the same stack slot as the
1280             // spilled interval.
1281             vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1282           }
1283
1284           HasUse = false;
1285           HasDef = false;
1286           CanFold = false;
1287           if (isNotInMIMap(MI))
1288             break;
1289           goto RestartInstruction;
1290         }
1291       } else {
1292         // We'll try to fold it later if it's profitable.
1293         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1294       }
1295     }
1296
1297     mop.setReg(NewVReg);
1298     if (mop.isImplicit())
1299       rewriteImplicitOps(li, MI, NewVReg, vrm);
1300
1301     // Reuse NewVReg for other reads.
1302     bool HasEarlyClobber = false;
1303     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1304       MachineOperand &mopj = MI->getOperand(Ops[j]);
1305       mopj.setReg(NewVReg);
1306       if (mopj.isImplicit())
1307         rewriteImplicitOps(li, MI, NewVReg, vrm);
1308       if (mopj.isEarlyClobber())
1309         HasEarlyClobber = true;
1310     }
1311
1312     if (CreatedNewVReg) {
1313       if (DefIsReMat) {
1314         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
1315         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1316           // Each valnum may have its own remat id.
1317           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1318         } else {
1319           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1320         }
1321         if (!CanDelete || (HasUse && HasDef)) {
1322           // If this is a two-addr instruction then its use operands are
1323           // rematerializable but its def is not. It should be assigned a
1324           // stack slot.
1325           vrm.assignVirt2StackSlot(NewVReg, Slot);
1326         }
1327       } else {
1328         vrm.assignVirt2StackSlot(NewVReg, Slot);
1329       }
1330     } else if (HasUse && HasDef &&
1331                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1332       // If this interval hasn't been assigned a stack slot (because earlier
1333       // def is a deleted remat def), do it now.
1334       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1335       vrm.assignVirt2StackSlot(NewVReg, Slot);
1336     }
1337
1338     // Re-matting an instruction with virtual register use. Add the
1339     // register as an implicit use on the use MI.
1340     if (DefIsReMat && ImpUse)
1341       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1342
1343     // Create a new register interval for this spill / remat.
1344     LiveInterval &nI = getOrCreateInterval(NewVReg);
1345     if (CreatedNewVReg) {
1346       NewLIs.push_back(&nI);
1347       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1348       if (TrySplit)
1349         vrm.setIsSplitFromReg(NewVReg, li.reg);
1350     }
1351
1352     if (HasUse) {
1353       if (CreatedNewVReg) {
1354         LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
1355                      nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1356         DEBUG(dbgs() << " +" << LR);
1357         nI.addRange(LR);
1358       } else {
1359         // Extend the split live interval to this def / use.
1360         SlotIndex End = index.getDefIndex();
1361         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1362                      nI.getValNumInfo(nI.getNumValNums()-1));
1363         DEBUG(dbgs() << " +" << LR);
1364         nI.addRange(LR);
1365       }
1366     }
1367     if (HasDef) {
1368       // An early clobber starts at the use slot, except for an early clobber
1369       // tied to a use operand (yes, that is a thing).
1370       LiveRange LR(HasEarlyClobber && !HasUse ?
1371                    index.getUseIndex() : index.getDefIndex(),
1372                    index.getStoreIndex(),
1373                    nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
1374       DEBUG(dbgs() << " +" << LR);
1375       nI.addRange(LR);
1376     }
1377
1378     DEBUG({
1379         dbgs() << "\t\t\t\tAdded new interval: ";
1380         nI.print(dbgs(), tri_);
1381         dbgs() << '\n';
1382       });
1383   }
1384   return CanFold;
1385 }
1386 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1387                                    const VNInfo *VNI,
1388                                    MachineBasicBlock *MBB,
1389                                    SlotIndex Idx) const {
1390   return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
1391 }
1392
1393 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1394 /// during spilling.
1395 namespace {
1396   struct RewriteInfo {
1397     SlotIndex Index;
1398     MachineInstr *MI;
1399     RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
1400   };
1401
1402   struct RewriteInfoCompare {
1403     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1404       return LHS.Index < RHS.Index;
1405     }
1406   };
1407 }
1408
1409 void LiveIntervals::
1410 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1411                     LiveInterval::Ranges::const_iterator &I,
1412                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1413                     unsigned Slot, int LdSlot,
1414                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1415                     VirtRegMap &vrm,
1416                     const TargetRegisterClass* rc,
1417                     SmallVector<int, 4> &ReMatIds,
1418                     const MachineLoopInfo *loopInfo,
1419                     BitVector &SpillMBBs,
1420                     DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
1421                     BitVector &RestoreMBBs,
1422                     DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1423                     DenseMap<unsigned,unsigned> &MBBVRegsMap,
1424                     std::vector<LiveInterval*> &NewLIs) {
1425   bool AllCanFold = true;
1426   unsigned NewVReg = 0;
1427   SlotIndex start = I->start.getBaseIndex();
1428   SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
1429
1430   // First collect all the def / use in this live range that will be rewritten.
1431   // Make sure they are sorted according to instruction index.
1432   std::vector<RewriteInfo> RewriteMIs;
1433   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1434          re = mri_->reg_end(); ri != re; ) {
1435     MachineInstr *MI = &*ri;
1436     MachineOperand &O = ri.getOperand();
1437     ++ri;
1438     if (MI->isDebugValue()) {
1439       // Modify DBG_VALUE now that the value is in a spill slot.
1440       if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
1441         uint64_t Offset = MI->getOperand(1).getImm();
1442         const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1443         DebugLoc DL = MI->getDebugLoc();
1444         int FI = isLoadSS ? LdSlot : (int)Slot;
1445         if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
1446                                                            Offset, MDPtr, DL)) {
1447           DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1448           ReplaceMachineInstrInMaps(MI, NewDV);
1449           MachineBasicBlock *MBB = MI->getParent();
1450           MBB->insert(MBB->erase(MI), NewDV);
1451           continue;
1452         }
1453       }
1454
1455       DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1456       RemoveMachineInstrFromMaps(MI);
1457       vrm.RemoveMachineInstrFromMaps(MI);
1458       MI->eraseFromParent();
1459       continue;
1460     }
1461     assert(!(O.isImplicit() && O.isUse()) &&
1462            "Spilling register that's used as implicit use?");
1463     SlotIndex index = getInstructionIndex(MI);
1464     if (index < start || index >= end)
1465       continue;
1466
1467     if (O.isUndef())
1468       // Must be defined by an implicit def. It should not be spilled. Note,
1469       // this is for correctness reason. e.g.
1470       // 8   %reg1024<def> = IMPLICIT_DEF
1471       // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1472       // The live range [12, 14) are not part of the r1024 live interval since
1473       // it's defined by an implicit def. It will not conflicts with live
1474       // interval of r1025. Now suppose both registers are spilled, you can
1475       // easily see a situation where both registers are reloaded before
1476       // the INSERT_SUBREG and both target registers that would overlap.
1477       continue;
1478     RewriteMIs.push_back(RewriteInfo(index, MI));
1479   }
1480   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1481
1482   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1483   // Now rewrite the defs and uses.
1484   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1485     RewriteInfo &rwi = RewriteMIs[i];
1486     ++i;
1487     SlotIndex index = rwi.Index;
1488     MachineInstr *MI = rwi.MI;
1489     // If MI def and/or use the same register multiple times, then there
1490     // are multiple entries.
1491     while (i != e && RewriteMIs[i].MI == MI) {
1492       assert(RewriteMIs[i].Index == index);
1493       ++i;
1494     }
1495     MachineBasicBlock *MBB = MI->getParent();
1496
1497     if (ImpUse && MI != ReMatDefMI) {
1498       // Re-matting an instruction with virtual register use. Prevent interval
1499       // from being spilled.
1500       getInterval(ImpUse).markNotSpillable();
1501     }
1502
1503     unsigned MBBId = MBB->getNumber();
1504     unsigned ThisVReg = 0;
1505     if (TrySplit) {
1506       DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
1507       if (NVI != MBBVRegsMap.end()) {
1508         ThisVReg = NVI->second;
1509         // One common case:
1510         // x = use
1511         // ...
1512         // ...
1513         // def = ...
1514         //     = use
1515         // It's better to start a new interval to avoid artifically
1516         // extend the new interval.
1517         if (MI->readsWritesVirtualRegister(li.reg) ==
1518             std::make_pair(false,true)) {
1519           MBBVRegsMap.erase(MBB->getNumber());
1520           ThisVReg = 0;
1521         }
1522       }
1523     }
1524
1525     bool IsNew = ThisVReg == 0;
1526     if (IsNew) {
1527       // This ends the previous live interval. If all of its def / use
1528       // can be folded, give it a low spill weight.
1529       if (NewVReg && TrySplit && AllCanFold) {
1530         LiveInterval &nI = getOrCreateInterval(NewVReg);
1531         nI.weight /= 10.0F;
1532       }
1533       AllCanFold = true;
1534     }
1535     NewVReg = ThisVReg;
1536
1537     bool HasDef = false;
1538     bool HasUse = false;
1539     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1540                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1541                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1542                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1543                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1544     if (!HasDef && !HasUse)
1545       continue;
1546
1547     AllCanFold &= CanFold;
1548
1549     // Update weight of spill interval.
1550     LiveInterval &nI = getOrCreateInterval(NewVReg);
1551     if (!TrySplit) {
1552       // The spill weight is now infinity as it cannot be spilled again.
1553       nI.markNotSpillable();
1554       continue;
1555     }
1556
1557     // Keep track of the last def and first use in each MBB.
1558     if (HasDef) {
1559       if (MI != ReMatOrigDefMI || !CanDelete) {
1560         bool HasKill = false;
1561         if (!HasUse)
1562           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
1563         else {
1564           // If this is a two-address code, then this index starts a new VNInfo.
1565           const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
1566           if (VNI)
1567             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
1568         }
1569         DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1570           SpillIdxes.find(MBBId);
1571         if (!HasKill) {
1572           if (SII == SpillIdxes.end()) {
1573             std::vector<SRInfo> S;
1574             S.push_back(SRInfo(index, NewVReg, true));
1575             SpillIdxes.insert(std::make_pair(MBBId, S));
1576           } else if (SII->second.back().vreg != NewVReg) {
1577             SII->second.push_back(SRInfo(index, NewVReg, true));
1578           } else if (index > SII->second.back().index) {
1579             // If there is an earlier def and this is a two-address
1580             // instruction, then it's not possible to fold the store (which
1581             // would also fold the load).
1582             SRInfo &Info = SII->second.back();
1583             Info.index = index;
1584             Info.canFold = !HasUse;
1585           }
1586           SpillMBBs.set(MBBId);
1587         } else if (SII != SpillIdxes.end() &&
1588                    SII->second.back().vreg == NewVReg &&
1589                    index > SII->second.back().index) {
1590           // There is an earlier def that's not killed (must be two-address).
1591           // The spill is no longer needed.
1592           SII->second.pop_back();
1593           if (SII->second.empty()) {
1594             SpillIdxes.erase(MBBId);
1595             SpillMBBs.reset(MBBId);
1596           }
1597         }
1598       }
1599     }
1600
1601     if (HasUse) {
1602       DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
1603         SpillIdxes.find(MBBId);
1604       if (SII != SpillIdxes.end() &&
1605           SII->second.back().vreg == NewVReg &&
1606           index > SII->second.back().index)
1607         // Use(s) following the last def, it's not safe to fold the spill.
1608         SII->second.back().canFold = false;
1609       DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
1610         RestoreIdxes.find(MBBId);
1611       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1612         // If we are splitting live intervals, only fold if it's the first
1613         // use and there isn't another use later in the MBB.
1614         RII->second.back().canFold = false;
1615       else if (IsNew) {
1616         // Only need a reload if there isn't an earlier def / use.
1617         if (RII == RestoreIdxes.end()) {
1618           std::vector<SRInfo> Infos;
1619           Infos.push_back(SRInfo(index, NewVReg, true));
1620           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1621         } else {
1622           RII->second.push_back(SRInfo(index, NewVReg, true));
1623         }
1624         RestoreMBBs.set(MBBId);
1625       }
1626     }
1627
1628     // Update spill weight.
1629     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1630     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1631   }
1632
1633   if (NewVReg && TrySplit && AllCanFold) {
1634     // If all of its def / use can be folded, give it a low spill weight.
1635     LiveInterval &nI = getOrCreateInterval(NewVReg);
1636     nI.weight /= 10.0F;
1637   }
1638 }
1639
1640 bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
1641                         unsigned vr, BitVector &RestoreMBBs,
1642                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1643   if (!RestoreMBBs[Id])
1644     return false;
1645   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1646   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1647     if (Restores[i].index == index &&
1648         Restores[i].vreg == vr &&
1649         Restores[i].canFold)
1650       return true;
1651   return false;
1652 }
1653
1654 void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
1655                         unsigned vr, BitVector &RestoreMBBs,
1656                         DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1657   if (!RestoreMBBs[Id])
1658     return;
1659   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1660   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1661     if (Restores[i].index == index && Restores[i].vreg)
1662       Restores[i].index = SlotIndex();
1663 }
1664
1665 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1666 /// spilled and create empty intervals for their uses.
1667 void
1668 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1669                                     const TargetRegisterClass* rc,
1670                                     std::vector<LiveInterval*> &NewLIs) {
1671   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1672          re = mri_->reg_end(); ri != re; ) {
1673     MachineOperand &O = ri.getOperand();
1674     MachineInstr *MI = &*ri;
1675     ++ri;
1676     if (MI->isDebugValue()) {
1677       // Remove debug info for now.
1678       O.setReg(0U);
1679       DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1680       continue;
1681     }
1682     if (O.isDef()) {
1683       assert(MI->isImplicitDef() &&
1684              "Register def was not rewritten?");
1685       RemoveMachineInstrFromMaps(MI);
1686       vrm.RemoveMachineInstrFromMaps(MI);
1687       MI->eraseFromParent();
1688     } else {
1689       // This must be an use of an implicit_def so it's not part of the live
1690       // interval. Create a new empty live interval for it.
1691       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1692       unsigned NewVReg = mri_->createVirtualRegister(rc);
1693       vrm.grow();
1694       vrm.setIsImplicitlyDefined(NewVReg);
1695       NewLIs.push_back(&getOrCreateInterval(NewVReg));
1696       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1697         MachineOperand &MO = MI->getOperand(i);
1698         if (MO.isReg() && MO.getReg() == li.reg) {
1699           MO.setReg(NewVReg);
1700           MO.setIsUndef();
1701         }
1702       }
1703     }
1704   }
1705 }
1706
1707 float
1708 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1709   // Limit the loop depth ridiculousness.
1710   if (loopDepth > 200)
1711     loopDepth = 200;
1712
1713   // The loop depth is used to roughly estimate the number of times the
1714   // instruction is executed. Something like 10^d is simple, but will quickly
1715   // overflow a float. This expression behaves like 10^d for small d, but is
1716   // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1717   // headroom before overflow.
1718   float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth);
1719
1720   return (isDef + isUse) * lc;
1721 }
1722
1723 static void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
1724   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1725     NewLIs[i]->weight =
1726       normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize());
1727 }
1728
1729 std::vector<LiveInterval*> LiveIntervals::
1730 addIntervalsForSpills(const LiveInterval &li,
1731                       const SmallVectorImpl<LiveInterval*> *SpillIs,
1732                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1733   assert(li.isSpillable() && "attempt to spill already spilled interval!");
1734
1735   DEBUG({
1736       dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1737       li.print(dbgs(), tri_);
1738       dbgs() << '\n';
1739     });
1740
1741   // Each bit specify whether a spill is required in the MBB.
1742   BitVector SpillMBBs(mf_->getNumBlockIDs());
1743   DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
1744   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1745   DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1746   DenseMap<unsigned,unsigned> MBBVRegsMap;
1747   std::vector<LiveInterval*> NewLIs;
1748   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1749
1750   unsigned NumValNums = li.getNumValNums();
1751   SmallVector<MachineInstr*, 4> ReMatDefs;
1752   ReMatDefs.resize(NumValNums, NULL);
1753   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1754   ReMatOrigDefs.resize(NumValNums, NULL);
1755   SmallVector<int, 4> ReMatIds;
1756   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1757   BitVector ReMatDelete(NumValNums);
1758   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1759
1760   // Spilling a split live interval. It cannot be split any further. Also,
1761   // it's also guaranteed to be a single val# / range interval.
1762   if (vrm.getPreSplitReg(li.reg)) {
1763     vrm.setIsSplitFromReg(li.reg, 0);
1764     // Unset the split kill marker on the last use.
1765     SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1766     if (KillIdx != SlotIndex()) {
1767       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1768       assert(KillMI && "Last use disappeared?");
1769       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1770       assert(KillOp != -1 && "Last use disappeared?");
1771       KillMI->getOperand(KillOp).setIsKill(false);
1772     }
1773     vrm.removeKillPoint(li.reg);
1774     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1775     Slot = vrm.getStackSlot(li.reg);
1776     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1777     MachineInstr *ReMatDefMI = DefIsReMat ?
1778       vrm.getReMaterializedMI(li.reg) : NULL;
1779     int LdSlot = 0;
1780     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1781     bool isLoad = isLoadSS ||
1782       (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
1783     bool IsFirstRange = true;
1784     for (LiveInterval::Ranges::const_iterator
1785            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1786       // If this is a split live interval with multiple ranges, it means there
1787       // are two-address instructions that re-defined the value. Only the
1788       // first def can be rematerialized!
1789       if (IsFirstRange) {
1790         // Note ReMatOrigDefMI has already been deleted.
1791         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1792                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1793                              false, vrm, rc, ReMatIds, loopInfo,
1794                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1795                              MBBVRegsMap, NewLIs);
1796       } else {
1797         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1798                              Slot, 0, false, false, false,
1799                              false, vrm, rc, ReMatIds, loopInfo,
1800                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1801                              MBBVRegsMap, NewLIs);
1802       }
1803       IsFirstRange = false;
1804     }
1805
1806     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1807     normalizeSpillWeights(NewLIs);
1808     return NewLIs;
1809   }
1810
1811   bool TrySplit = !intervalIsInOneMBB(li);
1812   if (TrySplit)
1813     ++numSplits;
1814   bool NeedStackSlot = false;
1815   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1816        i != e; ++i) {
1817     const VNInfo *VNI = *i;
1818     unsigned VN = VNI->id;
1819     if (VNI->isUnused())
1820       continue; // Dead val#.
1821     // Is the def for the val# rematerializable?
1822     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1823     bool dummy;
1824     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
1825       // Remember how to remat the def of this val#.
1826       ReMatOrigDefs[VN] = ReMatDefMI;
1827       // Original def may be modified so we have to make a copy here.
1828       MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
1829       CloneMIs.push_back(Clone);
1830       ReMatDefs[VN] = Clone;
1831
1832       bool CanDelete = true;
1833       if (VNI->hasPHIKill()) {
1834         // A kill is a phi node, not all of its uses can be rematerialized.
1835         // It must not be deleted.
1836         CanDelete = false;
1837         // Need a stack slot if there is any live range where uses cannot be
1838         // rematerialized.
1839         NeedStackSlot = true;
1840       }
1841       if (CanDelete)
1842         ReMatDelete.set(VN);
1843     } else {
1844       // Need a stack slot if there is any live range where uses cannot be
1845       // rematerialized.
1846       NeedStackSlot = true;
1847     }
1848   }
1849
1850   // One stack slot per live interval.
1851   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1852     if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1853       Slot = vrm.assignVirt2StackSlot(li.reg);
1854
1855     // This case only occurs when the prealloc splitter has already assigned
1856     // a stack slot to this vreg.
1857     else
1858       Slot = vrm.getStackSlot(li.reg);
1859   }
1860
1861   // Create new intervals and rewrite defs and uses.
1862   for (LiveInterval::Ranges::const_iterator
1863          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1864     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1865     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1866     bool DefIsReMat = ReMatDefMI != NULL;
1867     bool CanDelete = ReMatDelete[I->valno->id];
1868     int LdSlot = 0;
1869     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1870     bool isLoad = isLoadSS ||
1871       (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
1872     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1873                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1874                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1875                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1876                                MBBVRegsMap, NewLIs);
1877   }
1878
1879   // Insert spills / restores if we are splitting.
1880   if (!TrySplit) {
1881     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1882     normalizeSpillWeights(NewLIs);
1883     return NewLIs;
1884   }
1885
1886   SmallPtrSet<LiveInterval*, 4> AddedKill;
1887   SmallVector<unsigned, 2> Ops;
1888   if (NeedStackSlot) {
1889     int Id = SpillMBBs.find_first();
1890     while (Id != -1) {
1891       std::vector<SRInfo> &spills = SpillIdxes[Id];
1892       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1893         SlotIndex index = spills[i].index;
1894         unsigned VReg = spills[i].vreg;
1895         LiveInterval &nI = getOrCreateInterval(VReg);
1896         bool isReMat = vrm.isReMaterialized(VReg);
1897         MachineInstr *MI = getInstructionFromIndex(index);
1898         bool CanFold = false;
1899         bool FoundUse = false;
1900         Ops.clear();
1901         if (spills[i].canFold) {
1902           CanFold = true;
1903           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1904             MachineOperand &MO = MI->getOperand(j);
1905             if (!MO.isReg() || MO.getReg() != VReg)
1906               continue;
1907
1908             Ops.push_back(j);
1909             if (MO.isDef())
1910               continue;
1911             if (isReMat ||
1912                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1913                                                 RestoreMBBs, RestoreIdxes))) {
1914               // MI has two-address uses of the same register. If the use
1915               // isn't the first and only use in the BB, then we can't fold
1916               // it. FIXME: Move this to rewriteInstructionsForSpills.
1917               CanFold = false;
1918               break;
1919             }
1920             FoundUse = true;
1921           }
1922         }
1923         // Fold the store into the def if possible.
1924         bool Folded = false;
1925         if (CanFold && !Ops.empty()) {
1926           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1927             Folded = true;
1928             if (FoundUse) {
1929               // Also folded uses, do not issue a load.
1930               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1931               nI.removeRange(index.getLoadIndex(), index.getDefIndex());
1932             }
1933             nI.removeRange(index.getDefIndex(), index.getStoreIndex());
1934           }
1935         }
1936
1937         // Otherwise tell the spiller to issue a spill.
1938         if (!Folded) {
1939           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1940           bool isKill = LR->end == index.getStoreIndex();
1941           if (!MI->registerDefIsDead(nI.reg))
1942             // No need to spill a dead def.
1943             vrm.addSpillPoint(VReg, isKill, MI);
1944           if (isKill)
1945             AddedKill.insert(&nI);
1946         }
1947       }
1948       Id = SpillMBBs.find_next(Id);
1949     }
1950   }
1951
1952   int Id = RestoreMBBs.find_first();
1953   while (Id != -1) {
1954     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1955     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1956       SlotIndex index = restores[i].index;
1957       if (index == SlotIndex())
1958         continue;
1959       unsigned VReg = restores[i].vreg;
1960       LiveInterval &nI = getOrCreateInterval(VReg);
1961       bool isReMat = vrm.isReMaterialized(VReg);
1962       MachineInstr *MI = getInstructionFromIndex(index);
1963       bool CanFold = false;
1964       Ops.clear();
1965       if (restores[i].canFold) {
1966         CanFold = true;
1967         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1968           MachineOperand &MO = MI->getOperand(j);
1969           if (!MO.isReg() || MO.getReg() != VReg)
1970             continue;
1971
1972           if (MO.isDef()) {
1973             // If this restore were to be folded, it would have been folded
1974             // already.
1975             CanFold = false;
1976             break;
1977           }
1978           Ops.push_back(j);
1979         }
1980       }
1981
1982       // Fold the load into the use if possible.
1983       bool Folded = false;
1984       if (CanFold && !Ops.empty()) {
1985         if (!isReMat)
1986           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1987         else {
1988           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1989           int LdSlot = 0;
1990           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1991           // If the rematerializable def is a load, also try to fold it.
1992           if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
1993             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1994                                           Ops, isLoadSS, LdSlot, VReg);
1995           if (!Folded) {
1996             unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1997             if (ImpUse) {
1998               // Re-matting an instruction with virtual register use. Add the
1999               // register as an implicit use on the use MI and mark the register
2000               // interval as unspillable.
2001               LiveInterval &ImpLi = getInterval(ImpUse);
2002               ImpLi.markNotSpillable();
2003               MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2004             }
2005           }
2006         }
2007       }
2008       // If folding is not possible / failed, then tell the spiller to issue a
2009       // load / rematerialization for us.
2010       if (Folded)
2011         nI.removeRange(index.getLoadIndex(), index.getDefIndex());
2012       else
2013         vrm.addRestorePoint(VReg, MI);
2014     }
2015     Id = RestoreMBBs.find_next(Id);
2016   }
2017
2018   // Finalize intervals: add kills, finalize spill weights, and filter out
2019   // dead intervals.
2020   std::vector<LiveInterval*> RetNewLIs;
2021   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2022     LiveInterval *LI = NewLIs[i];
2023     if (!LI->empty()) {
2024       if (!AddedKill.count(LI)) {
2025         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
2026         SlotIndex LastUseIdx = LR->end.getBaseIndex();
2027         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
2028         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
2029         assert(UseIdx != -1);
2030         if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
2031           LastUse->getOperand(UseIdx).setIsKill();
2032           vrm.addKillPoint(LI->reg, LastUseIdx);
2033         }
2034       }
2035       RetNewLIs.push_back(LI);
2036     }
2037   }
2038
2039   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
2040   normalizeSpillWeights(RetNewLIs);
2041   return RetNewLIs;
2042 }
2043
2044 /// hasAllocatableSuperReg - Return true if the specified physical register has
2045 /// any super register that's allocatable.
2046 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2047   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2048     if (allocatableRegs_[*AS] && hasInterval(*AS))
2049       return true;
2050   return false;
2051 }
2052
2053 /// getRepresentativeReg - Find the largest super register of the specified
2054 /// physical register.
2055 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
2056   // Find the largest super-register that is allocatable.
2057   unsigned BestReg = Reg;
2058   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2059     unsigned SuperReg = *AS;
2060     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2061       BestReg = SuperReg;
2062       break;
2063     }
2064   }
2065   return BestReg;
2066 }
2067
2068 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2069 /// specified interval that conflicts with the specified physical register.
2070 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2071                                                    unsigned PhysReg) const {
2072   unsigned NumConflicts = 0;
2073   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2074   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2075          E = mri_->reg_end(); I != E; ++I) {
2076     MachineOperand &O = I.getOperand();
2077     MachineInstr *MI = O.getParent();
2078     if (MI->isDebugValue())
2079       continue;
2080     SlotIndex Index = getInstructionIndex(MI);
2081     if (pli.liveAt(Index))
2082       ++NumConflicts;
2083   }
2084   return NumConflicts;
2085 }
2086
2087 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
2088 /// around all defs and uses of the specified interval. Return true if it
2089 /// was able to cut its interval.
2090 bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
2091                                             unsigned PhysReg, VirtRegMap &vrm) {
2092   unsigned SpillReg = getRepresentativeReg(PhysReg);
2093
2094   DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
2095                << " represented by " << tri_->getName(SpillReg) << '\n');
2096
2097   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2098     // If there are registers which alias PhysReg, but which are not a
2099     // sub-register of the chosen representative super register. Assert
2100     // since we can't handle it yet.
2101     assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
2102            tri_->isSuperRegister(*AS, SpillReg));
2103
2104   bool Cut = false;
2105   SmallVector<unsigned, 4> PRegs;
2106   if (hasInterval(SpillReg))
2107     PRegs.push_back(SpillReg);
2108   for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
2109     if (hasInterval(*SR))
2110       PRegs.push_back(*SR);
2111
2112   DEBUG({
2113     dbgs() << "Trying to spill:";
2114     for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
2115       dbgs() << ' ' << tri_->getName(PRegs[i]);
2116     dbgs() << '\n';
2117   });
2118
2119   SmallPtrSet<MachineInstr*, 8> SeenMIs;
2120   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2121          E = mri_->reg_end(); I != E; ++I) {
2122     MachineOperand &O = I.getOperand();
2123     MachineInstr *MI = O.getParent();
2124     if (MI->isDebugValue() || SeenMIs.count(MI))
2125       continue;
2126     SeenMIs.insert(MI);
2127     SlotIndex Index = getInstructionIndex(MI);
2128     bool LiveReg = false;
2129     for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
2130       unsigned PReg = PRegs[i];
2131       LiveInterval &pli = getInterval(PReg);
2132       if (!pli.liveAt(Index))
2133         continue;
2134       LiveReg = true;
2135       SlotIndex StartIdx = Index.getLoadIndex();
2136       SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
2137       if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
2138         std::string msg;
2139         raw_string_ostream Msg(msg);
2140         Msg << "Ran out of registers during register allocation!";
2141         if (MI->isInlineAsm()) {
2142           Msg << "\nPlease check your inline asm statement for invalid "
2143               << "constraints:\n";
2144           MI->print(Msg, tm_);
2145         }
2146         report_fatal_error(Msg.str());
2147       }
2148       pli.removeRange(StartIdx, EndIdx);
2149       LiveReg = true;
2150     }
2151     if (!LiveReg)
2152       continue;
2153     DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
2154     vrm.addEmergencySpill(SpillReg, MI);
2155     Cut = true;
2156   }
2157   return Cut;
2158 }
2159
2160 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
2161                                                   MachineInstr* startInst) {
2162   LiveInterval& Interval = getOrCreateInterval(reg);
2163   VNInfo* VN = Interval.getNextValue(
2164     SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2165     startInst, getVNInfoAllocator());
2166   VN->setHasPHIKill(true);
2167   LiveRange LR(
2168      SlotIndex(getInstructionIndex(startInst).getDefIndex()),
2169      getMBBEndIdx(startInst->getParent()), VN);
2170   Interval.addRange(LR);
2171
2172   return LR;
2173 }
2174