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