lib/CodeGen/LiveIntervalAnalysis.cpp

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