lib/CodeGen/LiveIntervalAnalysis.cpp

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