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