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, float &SSWeight) {
 976   MachineBasicBlock *MBB = MI->getParent();
 977   unsigned loopDepth = loopInfo->getLoopDepth(MBB);
 978   bool CanFold = false;
 979  RestartInstruction:
 980   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 981     MachineOperand& mop = MI->getOperand(i);
 982     if (!mop.isRegister())
 983       continue;
 984     unsigned Reg = mop.getReg();
 985     unsigned RegI = Reg;
 986     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 987       continue;
 988     if (Reg != li.reg)
 989       continue;
 990
 991     bool TryFold = !DefIsReMat;
 992     bool FoldSS = true; // Default behavior unless it's a remat.
 993     int FoldSlot = Slot;
 994     if (DefIsReMat) {
 995       // If this is the rematerializable definition MI itself and
 996       // all of its uses are rematerialized, simply delete it.
 997       if (MI == ReMatOrigDefMI && CanDelete) {
 998         DOUT << "\t\t\t\tErasing re-materlizable def: ";
 999         DOUT << MI << '\n';
1000         RemoveMachineInstrFromMaps(MI);
1001         vrm.RemoveMachineInstrFromMaps(MI);
1002         MI->eraseFromParent();
1003         break;
1004       }
1005
1006       // If def for this use can't be rematerialized, then try folding.
1007       // If def is rematerializable and it's a load, also try folding.
1008       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1009       if (isLoad) {
1010         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1011         FoldSS = isLoadSS;
1012         FoldSlot = LdSlot;
1013       }
1014     }
1015
1016     // Scan all of the operands of this instruction rewriting operands
1017     // to use NewVReg instead of li.reg as appropriate.  We do this for
1018     // two reasons:
1019     //
1020     //   1. If the instr reads the same spilled vreg multiple times, we
1021     //      want to reuse the NewVReg.
1022     //   2. If the instr is a two-addr instruction, we are required to
1023     //      keep the src/dst regs pinned.
1024     //
1025     // Keep track of whether we replace a use and/or def so that we can
1026     // create the spill interval with the appropriate range.
1027
1028     HasUse = mop.isUse();
1029     HasDef = mop.isDef();
1030     SmallVector<unsigned, 2> Ops;
1031     Ops.push_back(i);
1032     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1033       const MachineOperand &MOj = MI->getOperand(j);
1034       if (!MOj.isRegister())
1035         continue;
1036       unsigned RegJ = MOj.getReg();
1037       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1038         continue;
1039       if (RegJ == RegI) {
1040         Ops.push_back(j);
1041         HasUse |= MOj.isUse();
1042         HasDef |= MOj.isDef();
1043       }
1044     }
1045
1046     // Update stack slot spill weight if we are splitting.
1047     float Weight = getSpillWeight(HasDef, HasUse, loopDepth);
1048       if (!TrySplit)
1049       SSWeight += Weight;
1050
1051     if (!TryFold)
1052       CanFold = false;
1053     else {
1054       // Do not fold load / store here if we are splitting. We'll find an
1055       // optimal point to insert a load / store later.
1056       if (!TrySplit) {
1057         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1058                                  Ops, FoldSS, FoldSlot, Reg)) {
1059           // Folding the load/store can completely change the instruction in
1060           // unpredictable ways, rescan it from the beginning.
1061           HasUse = false;
1062           HasDef = false;
1063           CanFold = false;
1064           if (isRemoved(MI)) {
1065             SSWeight -= Weight;
1066             break;
1067           }
1068           goto RestartInstruction;
1069         }
1070       } else {
1071         // We'll try to fold it later if it's profitable.
1072         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1073       }
1074     }
1075
1076     // Create a new virtual register for the spill interval.
1077     bool CreatedNewVReg = false;
1078     if (NewVReg == 0) {
1079       NewVReg = mri_->createVirtualRegister(rc);
1080       vrm.grow();
1081       CreatedNewVReg = true;
1082     }
1083     mop.setReg(NewVReg);
1084     if (mop.isImplicit())
1085       rewriteImplicitOps(li, MI, NewVReg, vrm);
1086
1087     // Reuse NewVReg for other reads.
1088     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1089       MachineOperand &mopj = MI->getOperand(Ops[j]);
1090       mopj.setReg(NewVReg);
1091       if (mopj.isImplicit())
1092         rewriteImplicitOps(li, MI, NewVReg, vrm);
1093     }
1094
1095     if (CreatedNewVReg) {
1096       if (DefIsReMat) {
1097         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
1098         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1099           // Each valnum may have its own remat id.
1100           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1101         } else {
1102           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1103         }
1104         if (!CanDelete || (HasUse && HasDef)) {
1105           // If this is a two-addr instruction then its use operands are
1106           // rematerializable but its def is not. It should be assigned a
1107           // stack slot.
1108           vrm.assignVirt2StackSlot(NewVReg, Slot);
1109         }
1110       } else {
1111         vrm.assignVirt2StackSlot(NewVReg, Slot);
1112       }
1113     } else if (HasUse && HasDef &&
1114                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1115       // If this interval hasn't been assigned a stack slot (because earlier
1116       // def is a deleted remat def), do it now.
1117       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1118       vrm.assignVirt2StackSlot(NewVReg, Slot);
1119     }
1120
1121     // Re-matting an instruction with virtual register use. Add the
1122     // register as an implicit use on the use MI.
1123     if (DefIsReMat && ImpUse)
1124       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1125
1126     // create a new register interval for this spill / remat.
1127     LiveInterval &nI = getOrCreateInterval(NewVReg);
1128     if (CreatedNewVReg) {
1129       NewLIs.push_back(&nI);
1130       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1131       if (TrySplit)
1132         vrm.setIsSplitFromReg(NewVReg, li.reg);
1133     }
1134
1135     if (HasUse) {
1136       if (CreatedNewVReg) {
1137         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1138                      nI.getNextValue(~0U, 0, VNInfoAllocator));
1139         DOUT << " +" << LR;
1140         nI.addRange(LR);
1141       } else {
1142         // Extend the split live interval to this def / use.
1143         unsigned End = getUseIndex(index)+1;
1144         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1145                      nI.getValNumInfo(nI.getNumValNums()-1));
1146         DOUT << " +" << LR;
1147         nI.addRange(LR);
1148       }
1149     }
1150     if (HasDef) {
1151       LiveRange LR(getDefIndex(index), getStoreIndex(index),
1152                    nI.getNextValue(~0U, 0, VNInfoAllocator));
1153       DOUT << " +" << LR;
1154       nI.addRange(LR);
1155     }
1156
1157     DOUT << "\t\t\t\tAdded new interval: ";
1158     nI.print(DOUT, tri_);
1159     DOUT << '\n';
1160   }
1161   return CanFold;
1162 }
1163 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1164                                    const VNInfo *VNI,
1165                                    MachineBasicBlock *MBB, unsigned Idx) const {
1166   unsigned End = getMBBEndIdx(MBB);
1167   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1168     unsigned KillIdx = VNI->kills[j];
1169     if (KillIdx > Idx && KillIdx < End)
1170       return true;
1171   }
1172   return false;
1173 }
1174
1175 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1176 /// during spilling.
1177 namespace {
1178   struct RewriteInfo {
1179     unsigned Index;
1180     MachineInstr *MI;
1181     bool HasUse;
1182     bool HasDef;
1183     RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1184       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1185   };
1186
1187   struct RewriteInfoCompare {
1188     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1189       return LHS.Index < RHS.Index;
1190     }
1191   };
1192 }
1193
1194 void LiveIntervals::
1195 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1196                     LiveInterval::Ranges::const_iterator &I,
1197                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1198                     unsigned Slot, int LdSlot,
1199                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1200                     VirtRegMap &vrm,
1201                     const TargetRegisterClass* rc,
1202                     SmallVector<int, 4> &ReMatIds,
1203                     const MachineLoopInfo *loopInfo,
1204                     BitVector &SpillMBBs,
1205                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
1206                     BitVector &RestoreMBBs,
1207                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1208                     std::map<unsigned,unsigned> &MBBVRegsMap,
1209                     std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
1210   bool AllCanFold = true;
1211   unsigned NewVReg = 0;
1212   unsigned start = getBaseIndex(I->start);
1213   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1214
1215   // First collect all the def / use in this live range that will be rewritten.
1216   // Make sure they are sorted according to instruction index.
1217   std::vector<RewriteInfo> RewriteMIs;
1218   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1219          re = mri_->reg_end(); ri != re; ) {
1220     MachineInstr *MI = &*ri;
1221     MachineOperand &O = ri.getOperand();
1222     ++ri;
1223     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1224     unsigned index = getInstructionIndex(MI);
1225     if (index < start || index >= end)
1226       continue;
1227     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1228   }
1229   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1230
1231   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1232   // Now rewrite the defs and uses.
1233   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1234     RewriteInfo &rwi = RewriteMIs[i];
1235     ++i;
1236     unsigned index = rwi.Index;
1237     bool MIHasUse = rwi.HasUse;
1238     bool MIHasDef = rwi.HasDef;
1239     MachineInstr *MI = rwi.MI;
1240     // If MI def and/or use the same register multiple times, then there
1241     // are multiple entries.
1242     unsigned NumUses = MIHasUse;
1243     while (i != e && RewriteMIs[i].MI == MI) {
1244       assert(RewriteMIs[i].Index == index);
1245       bool isUse = RewriteMIs[i].HasUse;
1246       if (isUse) ++NumUses;
1247       MIHasUse |= isUse;
1248       MIHasDef |= RewriteMIs[i].HasDef;
1249       ++i;
1250     }
1251     MachineBasicBlock *MBB = MI->getParent();
1252
1253     if (ImpUse && MI != ReMatDefMI) {
1254       // Re-matting an instruction with virtual register use. Update the
1255       // register interval's spill weight to HUGE_VALF to prevent it from
1256       // being spilled.
1257       LiveInterval &ImpLi = getInterval(ImpUse);
1258       ImpLi.weight = HUGE_VALF;
1259     }
1260
1261     unsigned MBBId = MBB->getNumber();
1262     unsigned ThisVReg = 0;
1263     if (TrySplit) {
1264       std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
1265       if (NVI != MBBVRegsMap.end()) {
1266         ThisVReg = NVI->second;
1267         // One common case:
1268         // x = use
1269         // ...
1270         // ...
1271         // def = ...
1272         //     = use
1273         // It's better to start a new interval to avoid artifically
1274         // extend the new interval.
1275         if (MIHasDef && !MIHasUse) {
1276           MBBVRegsMap.erase(MBB->getNumber());
1277           ThisVReg = 0;
1278         }
1279       }
1280     }
1281
1282     bool IsNew = ThisVReg == 0;
1283     if (IsNew) {
1284       // This ends the previous live interval. If all of its def / use
1285       // can be folded, give it a low spill weight.
1286       if (NewVReg && TrySplit && AllCanFold) {
1287         LiveInterval &nI = getOrCreateInterval(NewVReg);
1288         nI.weight /= 10.0F;
1289       }
1290       AllCanFold = true;
1291     }
1292     NewVReg = ThisVReg;
1293
1294     bool HasDef = false;
1295     bool HasUse = false;
1296     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1297                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1298                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1299                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1300                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight);
1301     if (!HasDef && !HasUse)
1302       continue;
1303
1304     AllCanFold &= CanFold;
1305
1306     // Update weight of spill interval.
1307     LiveInterval &nI = getOrCreateInterval(NewVReg);
1308     if (!TrySplit) {
1309       // The spill weight is now infinity as it cannot be spilled again.
1310       nI.weight = HUGE_VALF;
1311       continue;
1312     }
1313
1314     // Keep track of the last def and first use in each MBB.
1315     if (HasDef) {
1316       if (MI != ReMatOrigDefMI || !CanDelete) {
1317         bool HasKill = false;
1318         if (!HasUse)
1319           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1320         else {
1321           // If this is a two-address code, then this index starts a new VNInfo.
1322           const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
1323           if (VNI)
1324             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1325         }
1326         std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1327           SpillIdxes.find(MBBId);
1328         if (!HasKill) {
1329           if (SII == SpillIdxes.end()) {
1330             std::vector<SRInfo> S;
1331             S.push_back(SRInfo(index, NewVReg, true));
1332             SpillIdxes.insert(std::make_pair(MBBId, S));
1333           } else if (SII->second.back().vreg != NewVReg) {
1334             SII->second.push_back(SRInfo(index, NewVReg, true));
1335           } else if ((int)index > SII->second.back().index) {
1336             // If there is an earlier def and this is a two-address
1337             // instruction, then it's not possible to fold the store (which
1338             // would also fold the load).
1339             SRInfo &Info = SII->second.back();
1340             Info.index = index;
1341             Info.canFold = !HasUse;
1342           }
1343           SpillMBBs.set(MBBId);
1344         } else if (SII != SpillIdxes.end() &&
1345                    SII->second.back().vreg == NewVReg &&
1346                    (int)index > SII->second.back().index) {
1347           // There is an earlier def that's not killed (must be two-address).
1348           // The spill is no longer needed.
1349           SII->second.pop_back();
1350           if (SII->second.empty()) {
1351             SpillIdxes.erase(MBBId);
1352             SpillMBBs.reset(MBBId);
1353           }
1354         }
1355       }
1356     }
1357
1358     if (HasUse) {
1359       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1360         SpillIdxes.find(MBBId);
1361       if (SII != SpillIdxes.end() &&
1362           SII->second.back().vreg == NewVReg &&
1363           (int)index > SII->second.back().index)
1364         // Use(s) following the last def, it's not safe to fold the spill.
1365         SII->second.back().canFold = false;
1366       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1367         RestoreIdxes.find(MBBId);
1368       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1369         // If we are splitting live intervals, only fold if it's the first
1370         // use and there isn't another use later in the MBB.
1371         RII->second.back().canFold = false;
1372       else if (IsNew) {
1373         // Only need a reload if there isn't an earlier def / use.
1374         if (RII == RestoreIdxes.end()) {
1375           std::vector<SRInfo> Infos;
1376           Infos.push_back(SRInfo(index, NewVReg, true));
1377           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1378         } else {
1379           RII->second.push_back(SRInfo(index, NewVReg, true));
1380         }
1381         RestoreMBBs.set(MBBId);
1382       }
1383     }
1384
1385     // Update spill weight.
1386     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1387     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1388   }
1389
1390   if (NewVReg && TrySplit && AllCanFold) {
1391     // If all of its def / use can be folded, give it a low spill weight.
1392     LiveInterval &nI = getOrCreateInterval(NewVReg);
1393     nI.weight /= 10.0F;
1394   }
1395 }
1396
1397 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1398                         BitVector &RestoreMBBs,
1399                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1400   if (!RestoreMBBs[Id])
1401     return false;
1402   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1403   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1404     if (Restores[i].index == index &&
1405         Restores[i].vreg == vr &&
1406         Restores[i].canFold)
1407       return true;
1408   return false;
1409 }
1410
1411 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1412                         BitVector &RestoreMBBs,
1413                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1414   if (!RestoreMBBs[Id])
1415     return;
1416   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1417   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1418     if (Restores[i].index == index && Restores[i].vreg)
1419       Restores[i].index = -1;
1420 }
1421
1422 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1423 /// spilled and create empty intervals for their uses.
1424 void
1425 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1426                                     const TargetRegisterClass* rc,
1427                                     std::vector<LiveInterval*> &NewLIs) {
1428   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1429          re = mri_->reg_end(); ri != re; ) {
1430     MachineOperand &O = ri.getOperand();
1431     MachineInstr *MI = &*ri;
1432     ++ri;
1433     if (O.isDef()) {
1434       assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
1435              "Register def was not rewritten?");
1436       RemoveMachineInstrFromMaps(MI);
1437       vrm.RemoveMachineInstrFromMaps(MI);
1438       MI->eraseFromParent();
1439     } else {
1440       // This must be an use of an implicit_def so it's not part of the live
1441       // interval. Create a new empty live interval for it.
1442       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1443       unsigned NewVReg = mri_->createVirtualRegister(rc);
1444       vrm.grow();
1445       vrm.setIsImplicitlyDefined(NewVReg);
1446       NewLIs.push_back(&getOrCreateInterval(NewVReg));
1447       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1448         MachineOperand &MO = MI->getOperand(i);
1449         if (MO.isReg() && MO.getReg() == li.reg)
1450           MO.setReg(NewVReg);
1451       }
1452     }
1453   }
1454 }
1455
1456
1457 std::vector<LiveInterval*> LiveIntervals::
1458 addIntervalsForSpills(const LiveInterval &li,
1459                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
1460                       float &SSWeight) {
1461   // Since this is called after the analysis is done we don't know if
1462   // LiveVariables is available
1463   lv_ = getAnalysisToUpdate<LiveVariables>();
1464
1465   assert(li.weight != HUGE_VALF &&
1466          "attempt to spill already spilled interval!");
1467
1468   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1469   li.print(DOUT, tri_);
1470   DOUT << '\n';
1471
1472   // Spill slot weight.
1473   SSWeight = 0.0f;
1474
1475   // Each bit specify whether it a spill is required in the MBB.
1476   BitVector SpillMBBs(mf_->getNumBlockIDs());
1477   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1478   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1479   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1480   std::map<unsigned,unsigned> MBBVRegsMap;
1481   std::vector<LiveInterval*> NewLIs;
1482   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1483
1484   unsigned NumValNums = li.getNumValNums();
1485   SmallVector<MachineInstr*, 4> ReMatDefs;
1486   ReMatDefs.resize(NumValNums, NULL);
1487   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1488   ReMatOrigDefs.resize(NumValNums, NULL);
1489   SmallVector<int, 4> ReMatIds;
1490   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1491   BitVector ReMatDelete(NumValNums);
1492   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1493
1494   // Spilling a split live interval. It cannot be split any further. Also,
1495   // it's also guaranteed to be a single val# / range interval.
1496   if (vrm.getPreSplitReg(li.reg)) {
1497     vrm.setIsSplitFromReg(li.reg, 0);
1498     // Unset the split kill marker on the last use.
1499     unsigned KillIdx = vrm.getKillPoint(li.reg);
1500     if (KillIdx) {
1501       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1502       assert(KillMI && "Last use disappeared?");
1503       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1504       assert(KillOp != -1 && "Last use disappeared?");
1505       KillMI->getOperand(KillOp).setIsKill(false);
1506     }
1507     vrm.removeKillPoint(li.reg);
1508     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1509     Slot = vrm.getStackSlot(li.reg);
1510     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1511     MachineInstr *ReMatDefMI = DefIsReMat ?
1512       vrm.getReMaterializedMI(li.reg) : NULL;
1513     int LdSlot = 0;
1514     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1515     bool isLoad = isLoadSS ||
1516       (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
1517     bool IsFirstRange = true;
1518     for (LiveInterval::Ranges::const_iterator
1519            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1520       // If this is a split live interval with multiple ranges, it means there
1521       // are two-address instructions that re-defined the value. Only the
1522       // first def can be rematerialized!
1523       if (IsFirstRange) {
1524         // Note ReMatOrigDefMI has already been deleted.
1525         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1526                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1527                              false, vrm, rc, ReMatIds, loopInfo,
1528                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1529                              MBBVRegsMap, NewLIs, SSWeight);
1530       } else {
1531         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1532                              Slot, 0, false, false, false,
1533                              false, vrm, rc, ReMatIds, loopInfo,
1534                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1535                              MBBVRegsMap, NewLIs, SSWeight);
1536       }
1537       IsFirstRange = false;
1538     }
1539
1540     SSWeight = 0.0f;  // Already accounted for when split.
1541     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1542     return NewLIs;
1543   }
1544
1545   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1546   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1547     TrySplit = false;
1548   if (TrySplit)
1549     ++numSplits;
1550   bool NeedStackSlot = false;
1551   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1552        i != e; ++i) {
1553     const VNInfo *VNI = *i;
1554     unsigned VN = VNI->id;
1555     unsigned DefIdx = VNI->def;
1556     if (DefIdx == ~1U)
1557       continue; // Dead val#.
1558     // Is the def for the val# rematerializable?
1559     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1560       ? 0 : getInstructionFromIndex(DefIdx);
1561     bool dummy;
1562     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1563       // Remember how to remat the def of this val#.
1564       ReMatOrigDefs[VN] = ReMatDefMI;
1565       // Original def may be modified so we have to make a copy here. vrm must
1566       // delete these!
1567       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1568
1569       bool CanDelete = true;
1570       if (VNI->hasPHIKill) {
1571         // A kill is a phi node, not all of its uses can be rematerialized.
1572         // It must not be deleted.
1573         CanDelete = false;
1574         // Need a stack slot if there is any live range where uses cannot be
1575         // rematerialized.
1576         NeedStackSlot = true;
1577       }
1578       if (CanDelete)
1579         ReMatDelete.set(VN);
1580     } else {
1581       // Need a stack slot if there is any live range where uses cannot be
1582       // rematerialized.
1583       NeedStackSlot = true;
1584     }
1585   }
1586
1587   // One stack slot per live interval.
1588   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1589     Slot = vrm.assignVirt2StackSlot(li.reg);
1590
1591   // Create new intervals and rewrite defs and uses.
1592   for (LiveInterval::Ranges::const_iterator
1593          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1594     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1595     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1596     bool DefIsReMat = ReMatDefMI != NULL;
1597     bool CanDelete = ReMatDelete[I->valno->id];
1598     int LdSlot = 0;
1599     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1600     bool isLoad = isLoadSS ||
1601       (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
1602     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1603                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1604                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1605                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1606                                MBBVRegsMap, NewLIs, SSWeight);
1607   }
1608
1609   // Insert spills / restores if we are splitting.
1610   if (!TrySplit) {
1611     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1612     return NewLIs;
1613   }
1614
1615   SmallPtrSet<LiveInterval*, 4> AddedKill;
1616   SmallVector<unsigned, 2> Ops;
1617   if (NeedStackSlot) {
1618     int Id = SpillMBBs.find_first();
1619     while (Id != -1) {
1620       MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1621       unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1622       std::vector<SRInfo> &spills = SpillIdxes[Id];
1623       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1624         int index = spills[i].index;
1625         unsigned VReg = spills[i].vreg;
1626         LiveInterval &nI = getOrCreateInterval(VReg);
1627         bool isReMat = vrm.isReMaterialized(VReg);
1628         MachineInstr *MI = getInstructionFromIndex(index);
1629         bool CanFold = false;
1630         bool FoundUse = false;
1631         Ops.clear();
1632         if (spills[i].canFold) {
1633           CanFold = true;
1634           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1635             MachineOperand &MO = MI->getOperand(j);
1636             if (!MO.isRegister() || MO.getReg() != VReg)
1637               continue;
1638
1639             Ops.push_back(j);
1640             if (MO.isDef())
1641               continue;
1642             if (isReMat ||
1643                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1644                                                 RestoreMBBs, RestoreIdxes))) {
1645               // MI has two-address uses of the same register. If the use
1646               // isn't the first and only use in the BB, then we can't fold
1647               // it. FIXME: Move this to rewriteInstructionsForSpills.
1648               CanFold = false;
1649               break;
1650             }
1651             FoundUse = true;
1652           }
1653         }
1654         // Fold the store into the def if possible.
1655         bool Folded = false;
1656         if (CanFold && !Ops.empty()) {
1657           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1658             Folded = true;
1659             if (FoundUse > 0) {
1660               // Also folded uses, do not issue a load.
1661               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1662               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1663             }
1664             nI.removeRange(getDefIndex(index), getStoreIndex(index));
1665           }
1666         }
1667
1668         // Otherwise tell the spiller to issue a spill.
1669         if (!Folded) {
1670           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1671           bool isKill = LR->end == getStoreIndex(index);
1672           if (!MI->registerDefIsDead(nI.reg))
1673             // No need to spill a dead def.
1674             vrm.addSpillPoint(VReg, isKill, MI);
1675           if (isKill)
1676             AddedKill.insert(&nI);
1677         }
1678
1679         // Update spill slot weight.
1680         if (!isReMat)
1681           SSWeight += getSpillWeight(true, false, loopDepth);
1682       }
1683       Id = SpillMBBs.find_next(Id);
1684     }
1685   }
1686
1687   int Id = RestoreMBBs.find_first();
1688   while (Id != -1) {
1689     MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1690     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1691
1692     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1693     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1694       int index = restores[i].index;
1695       if (index == -1)
1696         continue;
1697       unsigned VReg = restores[i].vreg;
1698       LiveInterval &nI = getOrCreateInterval(VReg);
1699       bool isReMat = vrm.isReMaterialized(VReg);
1700       MachineInstr *MI = getInstructionFromIndex(index);
1701       bool CanFold = false;
1702       Ops.clear();
1703       if (restores[i].canFold) {
1704         CanFold = true;
1705         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1706           MachineOperand &MO = MI->getOperand(j);
1707           if (!MO.isRegister() || MO.getReg() != VReg)
1708             continue;
1709
1710           if (MO.isDef()) {
1711             // If this restore were to be folded, it would have been folded
1712             // already.
1713             CanFold = false;
1714             break;
1715           }
1716           Ops.push_back(j);
1717         }
1718       }
1719
1720       // Fold the load into the use if possible.
1721       bool Folded = false;
1722       if (CanFold && !Ops.empty()) {
1723         if (!isReMat)
1724           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1725         else {
1726           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1727           int LdSlot = 0;
1728           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1729           // If the rematerializable def is a load, also try to fold it.
1730           if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
1731             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1732                                           Ops, isLoadSS, LdSlot, VReg);
1733           unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1734           if (ImpUse) {
1735             // Re-matting an instruction with virtual register use. Add the
1736             // register as an implicit use on the use MI and update the register
1737             // interval's spill weight to HUGE_VALF to prevent it from being
1738             // spilled.
1739             LiveInterval &ImpLi = getInterval(ImpUse);
1740             ImpLi.weight = HUGE_VALF;
1741             MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1742           }
1743         }
1744       }
1745       // If folding is not possible / failed, then tell the spiller to issue a
1746       // load / rematerialization for us.
1747       if (Folded)
1748         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1749       else
1750         vrm.addRestorePoint(VReg, MI);
1751
1752       // Update spill slot weight.
1753       if (!isReMat)
1754         SSWeight += getSpillWeight(false, true, loopDepth);
1755     }
1756     Id = RestoreMBBs.find_next(Id);
1757   }
1758
1759   // Finalize intervals: add kills, finalize spill weights, and filter out
1760   // dead intervals.
1761   std::vector<LiveInterval*> RetNewLIs;
1762   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1763     LiveInterval *LI = NewLIs[i];
1764     if (!LI->empty()) {
1765       LI->weight /= LI->getSize();
1766       if (!AddedKill.count(LI)) {
1767         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
1768         unsigned LastUseIdx = getBaseIndex(LR->end);
1769         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
1770         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
1771         assert(UseIdx != -1);
1772         if (LastUse->getOperand(UseIdx).isImplicit() ||
1773             LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
1774           LastUse->getOperand(UseIdx).setIsKill();
1775           vrm.addKillPoint(LI->reg, LastUseIdx);
1776         }
1777       }
1778       RetNewLIs.push_back(LI);
1779     }
1780   }
1781
1782   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
1783   return RetNewLIs;
1784 }
1785
1786 /// hasAllocatableSuperReg - Return true if the specified physical register has
1787 /// any super register that's allocatable.
1788 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
1789   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
1790     if (allocatableRegs_[*AS] && hasInterval(*AS))
1791       return true;
1792   return false;
1793 }
1794
1795 /// getRepresentativeReg - Find the largest super register of the specified
1796 /// physical register.
1797 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
1798   // Find the largest super-register that is allocatable.
1799   unsigned BestReg = Reg;
1800   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
1801     unsigned SuperReg = *AS;
1802     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
1803       BestReg = SuperReg;
1804       break;
1805     }
1806   }
1807   return BestReg;
1808 }
1809
1810 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
1811 /// specified interval that conflicts with the specified physical register.
1812 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
1813                                                    unsigned PhysReg) const {
1814   unsigned NumConflicts = 0;
1815   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
1816   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1817          E = mri_->reg_end(); I != E; ++I) {
1818     MachineOperand &O = I.getOperand();
1819     MachineInstr *MI = O.getParent();
1820     unsigned Index = getInstructionIndex(MI);
1821     if (pli.liveAt(Index))
1822       ++NumConflicts;
1823   }
1824   return NumConflicts;
1825 }
1826
1827 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
1828 /// around all defs and uses of the specified interval.
1829 void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
1830                                             unsigned PhysReg, VirtRegMap &vrm) {
1831   unsigned SpillReg = getRepresentativeReg(PhysReg);
1832
1833   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
1834     // If there are registers which alias PhysReg, but which are not a
1835     // sub-register of the chosen representative super register. Assert
1836     // since we can't handle it yet.
1837     assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
1838            tri_->isSuperRegister(*AS, SpillReg));
1839
1840   LiveInterval &pli = getInterval(SpillReg);
1841   SmallPtrSet<MachineInstr*, 8> SeenMIs;
1842   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1843          E = mri_->reg_end(); I != E; ++I) {
1844     MachineOperand &O = I.getOperand();
1845     MachineInstr *MI = O.getParent();
1846     if (SeenMIs.count(MI))
1847       continue;
1848     SeenMIs.insert(MI);
1849     unsigned Index = getInstructionIndex(MI);
1850     if (pli.liveAt(Index)) {
1851       vrm.addEmergencySpill(SpillReg, MI);
1852       pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
1853       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
1854         if (!hasInterval(*AS))
1855           continue;
1856         LiveInterval &spli = getInterval(*AS);
1857         if (spli.liveAt(Index))
1858           spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
1859       }
1860     }
1861   }
1862 }
1863
1864 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
1865                                                    MachineInstr* startInst) {
1866   LiveInterval& Interval = getOrCreateInterval(reg);
1867   VNInfo* VN = Interval.getNextValue(
1868             getInstructionIndex(startInst) + InstrSlots::DEF,
1869             startInst, getVNInfoAllocator());
1870   VN->hasPHIKill = true;
1871   VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
1872   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
1873                getMBBEndIdx(startInst->getParent()) + 1, VN);
1874   Interval.addRange(LR);
1875
1876   return LR;
1877 }