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