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