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