lib/CodeGen/LiveIntervalAnalysis.cpp

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