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