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