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