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