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