lib/CodeGen/LiveIntervalAnalysis.cpp

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