lib/CodeGen/LiveIntervalAnalysis.cpp

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