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     // This is a load from fixed stack slot. It can be rematerialized unless
 651     // it's re-defined by a two-address instruction.
 652     isLoad = true;
 653     for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 654          i != e; ++i) {
 655       const VNInfo *VNI = *i;
 656       if (VNI == ValNo)
 657         continue;
 658       unsigned DefIdx = VNI->def;
 659       if (DefIdx == ~1U)
 660         continue; // Dead val#.
 661       MachineInstr *DefMI = (DefIdx == ~0u)
 662         ? NULL : getInstructionFromIndex(DefIdx);
 663       if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) {
 664         isLoad = false;
 665         return false;
 666       }
 667     }
 668     return true;
 669   }
 670
 671   if (tii_->isTriviallyReMaterializable(MI)) {
 672     isLoad = TID.isSimpleLoad();
 673
 674     unsigned ImpUse = getReMatImplicitUse(li, MI);
 675     if (ImpUse) {
 676       const LiveInterval &ImpLi = getInterval(ImpUse);
 677       for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
 678              re = mri_->use_end(); ri != re; ++ri) {
 679         MachineInstr *UseMI = &*ri;
 680         unsigned UseIdx = getInstructionIndex(UseMI);
 681         if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
 682           continue;
 683         if (!canFoldMemoryOperand(UseMI, li.reg) &&
 684             !isValNoAvailableAt(ImpLi, MI, UseIdx))
 685           return false;
 686       }
 687     }
 688     return true;
 689   }
 690
 691   return false;
 692 }
 693
 694 /// isReMaterializable - Returns true if every definition of MI of every
 695 /// val# of the specified interval is re-materializable.
 696 bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
 697   isLoad = false;
 698   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 699        i != e; ++i) {
 700     const VNInfo *VNI = *i;
 701     unsigned DefIdx = VNI->def;
 702     if (DefIdx == ~1U)
 703       continue; // Dead val#.
 704     // Is the def for the val# rematerializable?
 705     if (DefIdx == ~0u)
 706       return false;
 707     MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
 708     bool DefIsLoad = false;
 709     if (!ReMatDefMI ||
 710         !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
 711       return false;
 712     isLoad |= DefIsLoad;
 713   }
 714   return true;
 715 }
 716
 717 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
 718 /// slot / to reg or any rematerialized load into ith operand of specified
 719 /// MI. If it is successul, MI is updated with the newly created MI and
 720 /// returns true.
 721 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
 722                                          VirtRegMap &vrm, MachineInstr *DefMI,
 723                                          unsigned InstrIdx,
 724                                          SmallVector<unsigned, 2> &Ops,
 725                                          bool isSS, int Slot, unsigned Reg) {
 726   unsigned MRInfo = 0;
 727   const TargetInstrDesc &TID = MI->getDesc();
 728   // If it is an implicit def instruction, just delete it.
 729   if (TID.isImplicitDef()) {
 730     RemoveMachineInstrFromMaps(MI);
 731     vrm.RemoveMachineInstrFromMaps(MI);
 732     MI->eraseFromParent();
 733     ++numFolds;
 734     return true;
 735   }
 736
 737   SmallVector<unsigned, 2> FoldOps;
 738   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 739     unsigned OpIdx = Ops[i];
 740     MachineOperand &MO = MI->getOperand(OpIdx);
 741     // FIXME: fold subreg use.
 742     if (MO.getSubReg())
 743       return false;
 744     if (MO.isDef())
 745       MRInfo |= (unsigned)VirtRegMap::isMod;
 746     else {
 747       // Filter out two-address use operand(s).
 748       if (!MO.isImplicit() &&
 749           TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
 750         MRInfo = VirtRegMap::isModRef;
 751         continue;
 752       }
 753       MRInfo |= (unsigned)VirtRegMap::isRef;
 754     }
 755     FoldOps.push_back(OpIdx);
 756   }
 757
 758   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
 759                            : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
 760   if (fmi) {
 761     // Attempt to fold the memory reference into the instruction. If
 762     // we can do this, we don't need to insert spill code.
 763     if (lv_)
 764       lv_->instructionChanged(MI, fmi);
 765     else
 766       fmi->copyKillDeadInfo(MI, tri_);
 767     MachineBasicBlock &MBB = *MI->getParent();
 768     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
 769       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
 770     vrm.transferSpillPts(MI, fmi);
 771     vrm.transferRestorePts(MI, fmi);
 772     mi2iMap_.erase(MI);
 773     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
 774     mi2iMap_[fmi] = InstrIdx;
 775     MI = MBB.insert(MBB.erase(MI), fmi);
 776     ++numFolds;
 777     return true;
 778   }
 779   return false;
 780 }
 781
 782 /// canFoldMemoryOperand - Returns true if the specified load / store
 783 /// folding is possible.
 784 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
 785                                          SmallVector<unsigned, 2> &Ops) const {
 786   SmallVector<unsigned, 2> FoldOps;
 787   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 788     unsigned OpIdx = Ops[i];
 789     // FIXME: fold subreg use.
 790     if (MI->getOperand(OpIdx).getSubReg())
 791       return false;
 792     FoldOps.push_back(OpIdx);
 793   }
 794
 795   return tii_->canFoldMemoryOperand(MI, FoldOps);
 796 }
 797
 798 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, unsigned Reg) const {
 799   SmallVector<unsigned, 2> FoldOps;
 800   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 801     MachineOperand& mop = MI->getOperand(i);
 802     if (!mop.isRegister())
 803       continue;
 804     unsigned UseReg = mop.getReg();
 805     if (UseReg != Reg)
 806       continue;
 807     // FIXME: fold subreg use.
 808     if (mop.getSubReg())
 809       return false;
 810     FoldOps.push_back(i);
 811   }
 812   return tii_->canFoldMemoryOperand(MI, FoldOps);
 813 }
 814
 815 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
 816   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
 817   for (LiveInterval::Ranges::const_iterator
 818          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 819     std::vector<IdxMBBPair>::const_iterator II =
 820       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
 821     if (II == Idx2MBBMap.end())
 822       continue;
 823     if (I->end > II->first)  // crossing a MBB.
 824       return false;
 825     MBBs.insert(II->second);
 826     if (MBBs.size() > 1)
 827       return false;
 828   }
 829   return true;
 830 }
 831
 832 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
 833 /// interval on to-be re-materialized operands of MI) with new register.
 834 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
 835                                        MachineInstr *MI, unsigned NewVReg,
 836                                        VirtRegMap &vrm) {
 837   // There is an implicit use. That means one of the other operand is
 838   // being remat'ed and the remat'ed instruction has li.reg as an
 839   // use operand. Make sure we rewrite that as well.
 840   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 841     MachineOperand &MO = MI->getOperand(i);
 842     if (!MO.isRegister())
 843       continue;
 844     unsigned Reg = MO.getReg();
 845     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 846       continue;
 847     if (!vrm.isReMaterialized(Reg))
 848       continue;
 849     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
 850     int OpIdx = ReMatMI->findRegisterUseOperandIdx(li.reg);
 851     if (OpIdx != -1)
 852       ReMatMI->getOperand(OpIdx).setReg(NewVReg);
 853   }
 854 }
 855
 856 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
 857 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 858 bool LiveIntervals::
 859 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
 860                  bool TrySplit, unsigned index, unsigned end,  MachineInstr *MI,
 861                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 862                  unsigned Slot, int LdSlot,
 863                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 864                  VirtRegMap &vrm,
 865                  const TargetRegisterClass* rc,
 866                  SmallVector<int, 4> &ReMatIds,
 867                  const MachineLoopInfo *loopInfo,
 868                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
 869                  std::map<unsigned,unsigned> &MBBVRegsMap,
 870                  std::vector<LiveInterval*> &NewLIs) {
 871   bool CanFold = false;
 872  RestartInstruction:
 873   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 874     MachineOperand& mop = MI->getOperand(i);
 875     if (!mop.isRegister())
 876       continue;
 877     unsigned Reg = mop.getReg();
 878     unsigned RegI = Reg;
 879     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 880       continue;
 881     if (Reg != li.reg)
 882       continue;
 883
 884     bool TryFold = !DefIsReMat;
 885     bool FoldSS = true; // Default behavior unless it's a remat.
 886     int FoldSlot = Slot;
 887     if (DefIsReMat) {
 888       // If this is the rematerializable definition MI itself and
 889       // all of its uses are rematerialized, simply delete it.
 890       if (MI == ReMatOrigDefMI && CanDelete) {
 891         DOUT << "\t\t\t\tErasing re-materlizable def: ";
 892         DOUT << MI << '\n';
 893         unsigned ImpUse = getReMatImplicitUse(li, MI);
 894         if (ImpUse) {
 895           // To be deleted MI has a virtual register operand, update the
 896           // spill weight of the register interval.
 897           unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
 898           LiveInterval &ImpLi = getInterval(ImpUse);
 899           ImpLi.weight -=
 900             getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
 901         }
 902         RemoveMachineInstrFromMaps(MI);
 903         vrm.RemoveMachineInstrFromMaps(MI);
 904         MI->eraseFromParent();
 905         break;
 906       }
 907
 908       // If def for this use can't be rematerialized, then try folding.
 909       // If def is rematerializable and it's a load, also try folding.
 910       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
 911       if (isLoad) {
 912         // Try fold loads (from stack slot, constant pool, etc.) into uses.
 913         FoldSS = isLoadSS;
 914         FoldSlot = LdSlot;
 915       }
 916     }
 917
 918     // Scan all of the operands of this instruction rewriting operands
 919     // to use NewVReg instead of li.reg as appropriate.  We do this for
 920     // two reasons:
 921     //
 922     //   1. If the instr reads the same spilled vreg multiple times, we
 923     //      want to reuse the NewVReg.
 924     //   2. If the instr is a two-addr instruction, we are required to
 925     //      keep the src/dst regs pinned.
 926     //
 927     // Keep track of whether we replace a use and/or def so that we can
 928     // create the spill interval with the appropriate range.
 929
 930     HasUse = mop.isUse();
 931     HasDef = mop.isDef();
 932     SmallVector<unsigned, 2> Ops;
 933     Ops.push_back(i);
 934     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 935       const MachineOperand &MOj = MI->getOperand(j);
 936       if (!MOj.isRegister())
 937         continue;
 938       unsigned RegJ = MOj.getReg();
 939       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
 940         continue;
 941       if (RegJ == RegI) {
 942         Ops.push_back(j);
 943         HasUse |= MOj.isUse();
 944         HasDef |= MOj.isDef();
 945       }
 946     }
 947
 948     if (TryFold) {
 949       // Do not fold load / store here if we are splitting. We'll find an
 950       // optimal point to insert a load / store later.
 951       if (!TrySplit) {
 952         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
 953                                  Ops, FoldSS, FoldSlot, Reg)) {
 954           // Folding the load/store can completely change the instruction in
 955           // unpredictable ways, rescan it from the beginning.
 956           HasUse = false;
 957           HasDef = false;
 958           CanFold = false;
 959           goto RestartInstruction;
 960         }
 961       } else {
 962         CanFold = canFoldMemoryOperand(MI, Ops);
 963       }
 964     } else
 965       CanFold = false;
 966
 967     // Create a new virtual register for the spill interval.
 968     bool CreatedNewVReg = false;
 969     if (NewVReg == 0) {
 970       NewVReg = mri_->createVirtualRegister(rc);
 971       vrm.grow();
 972       CreatedNewVReg = true;
 973     }
 974     mop.setReg(NewVReg);
 975     if (mop.isImplicit())
 976       rewriteImplicitOps(li, MI, NewVReg, vrm);
 977
 978     // Reuse NewVReg for other reads.
 979     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
 980       MachineOperand &mopj = MI->getOperand(Ops[j]);
 981       mopj.setReg(NewVReg);
 982       if (mopj.isImplicit())
 983         rewriteImplicitOps(li, MI, NewVReg, vrm);
 984     }
 985
 986     if (CreatedNewVReg) {
 987       if (DefIsReMat) {
 988         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
 989         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
 990           // Each valnum may have its own remat id.
 991           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
 992         } else {
 993           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
 994         }
 995         if (!CanDelete || (HasUse && HasDef)) {
 996           // If this is a two-addr instruction then its use operands are
 997           // rematerializable but its def is not. It should be assigned a
 998           // stack slot.
 999           vrm.assignVirt2StackSlot(NewVReg, Slot);
1000         }
1001       } else {
1002         vrm.assignVirt2StackSlot(NewVReg, Slot);
1003       }
1004     } else if (HasUse && HasDef &&
1005                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1006       // If this interval hasn't been assigned a stack slot (because earlier
1007       // def is a deleted remat def), do it now.
1008       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1009       vrm.assignVirt2StackSlot(NewVReg, Slot);
1010     }
1011
1012     // Re-matting an instruction with virtual register use. Add the
1013     // register as an implicit use on the use MI.
1014     if (DefIsReMat && ImpUse)
1015       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1016
1017     // create a new register interval for this spill / remat.
1018     LiveInterval &nI = getOrCreateInterval(NewVReg);
1019     if (CreatedNewVReg) {
1020       NewLIs.push_back(&nI);
1021       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1022       if (TrySplit)
1023         vrm.setIsSplitFromReg(NewVReg, li.reg);
1024     }
1025
1026     if (HasUse) {
1027       if (CreatedNewVReg) {
1028         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1029                      nI.getNextValue(~0U, 0, VNInfoAllocator));
1030         DOUT << " +" << LR;
1031         nI.addRange(LR);
1032       } else {
1033         // Extend the split live interval to this def / use.
1034         unsigned End = getUseIndex(index)+1;
1035         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1036                      nI.getValNumInfo(nI.getNumValNums()-1));
1037         DOUT << " +" << LR;
1038         nI.addRange(LR);
1039       }
1040     }
1041     if (HasDef) {
1042       LiveRange LR(getDefIndex(index), getStoreIndex(index),
1043                    nI.getNextValue(~0U, 0, VNInfoAllocator));
1044       DOUT << " +" << LR;
1045       nI.addRange(LR);
1046     }
1047
1048     DOUT << "\t\t\t\tAdded new interval: ";
1049     nI.print(DOUT, tri_);
1050     DOUT << '\n';
1051   }
1052   return CanFold;
1053 }
1054 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1055                                    const VNInfo *VNI,
1056                                    MachineBasicBlock *MBB, unsigned Idx) const {
1057   unsigned End = getMBBEndIdx(MBB);
1058   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1059     unsigned KillIdx = VNI->kills[j];
1060     if (KillIdx > Idx && KillIdx < End)
1061       return true;
1062   }
1063   return false;
1064 }
1065
1066 static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
1067   const VNInfo *VNI = NULL;
1068   for (LiveInterval::const_vni_iterator i = li.vni_begin(),
1069          e = li.vni_end(); i != e; ++i)
1070     if ((*i)->def == DefIdx) {
1071       VNI = *i;
1072       break;
1073     }
1074   return VNI;
1075 }
1076
1077 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1078 /// during spilling.
1079 struct RewriteInfo {
1080   unsigned Index;
1081   MachineInstr *MI;
1082   bool HasUse;
1083   bool HasDef;
1084   RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1085     : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1086 };
1087
1088 struct RewriteInfoCompare {
1089   bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1090     return LHS.Index < RHS.Index;
1091   }
1092 };
1093
1094 void LiveIntervals::
1095 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1096                     LiveInterval::Ranges::const_iterator &I,
1097                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1098                     unsigned Slot, int LdSlot,
1099                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1100                     VirtRegMap &vrm,
1101                     const TargetRegisterClass* rc,
1102                     SmallVector<int, 4> &ReMatIds,
1103                     const MachineLoopInfo *loopInfo,
1104                     BitVector &SpillMBBs,
1105                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
1106                     BitVector &RestoreMBBs,
1107                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1108                     std::map<unsigned,unsigned> &MBBVRegsMap,
1109                     std::vector<LiveInterval*> &NewLIs) {
1110   bool AllCanFold = true;
1111   unsigned NewVReg = 0;
1112   unsigned start = getBaseIndex(I->start);
1113   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1114
1115   // First collect all the def / use in this live range that will be rewritten.
1116   // Make sure they are sorted according instruction index.
1117   std::vector<RewriteInfo> RewriteMIs;
1118   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1119          re = mri_->reg_end(); ri != re; ) {
1120     MachineInstr *MI = &(*ri);
1121     MachineOperand &O = ri.getOperand();
1122     ++ri;
1123     unsigned index = getInstructionIndex(MI);
1124     if (index < start || index >= end)
1125       continue;
1126     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1127   }
1128   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1129
1130   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1131   // Now rewrite the defs and uses.
1132   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1133     RewriteInfo &rwi = RewriteMIs[i];
1134     ++i;
1135     unsigned index = rwi.Index;
1136     bool MIHasUse = rwi.HasUse;
1137     bool MIHasDef = rwi.HasDef;
1138     MachineInstr *MI = rwi.MI;
1139     // If MI def and/or use the same register multiple times, then there
1140     // are multiple entries.
1141     unsigned NumUses = MIHasUse;
1142     while (i != e && RewriteMIs[i].MI == MI) {
1143       assert(RewriteMIs[i].Index == index);
1144       bool isUse = RewriteMIs[i].HasUse;
1145       if (isUse) ++NumUses;
1146       MIHasUse |= isUse;
1147       MIHasDef |= RewriteMIs[i].HasDef;
1148       ++i;
1149     }
1150     MachineBasicBlock *MBB = MI->getParent();
1151
1152     if (ImpUse && MI != ReMatDefMI) {
1153       // Re-matting an instruction with virtual register use. Update the
1154       // register interval's spill weight.
1155       unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
1156       LiveInterval &ImpLi = getInterval(ImpUse);
1157       ImpLi.weight +=
1158         getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize();
1159     }
1160
1161     unsigned MBBId = MBB->getNumber();
1162     unsigned ThisVReg = 0;
1163     if (TrySplit) {
1164       std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
1165       if (NVI != MBBVRegsMap.end()) {
1166         ThisVReg = NVI->second;
1167         // One common case:
1168         // x = use
1169         // ...
1170         // ...
1171         // def = ...
1172         //     = use
1173         // It's better to start a new interval to avoid artifically
1174         // extend the new interval.
1175         if (MIHasDef && !MIHasUse) {
1176           MBBVRegsMap.erase(MBB->getNumber());
1177           ThisVReg = 0;
1178         }
1179       }
1180     }
1181
1182     bool IsNew = ThisVReg == 0;
1183     if (IsNew) {
1184       // This ends the previous live interval. If all of its def / use
1185       // can be folded, give it a low spill weight.
1186       if (NewVReg && TrySplit && AllCanFold) {
1187         LiveInterval &nI = getOrCreateInterval(NewVReg);
1188         nI.weight /= 10.0F;
1189       }
1190       AllCanFold = true;
1191     }
1192     NewVReg = ThisVReg;
1193
1194     bool HasDef = false;
1195     bool HasUse = false;
1196     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1197                                 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1198                                 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1199                                 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1200                                 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
1201     if (!HasDef && !HasUse)
1202       continue;
1203
1204     AllCanFold &= CanFold;
1205
1206     // Update weight of spill interval.
1207     LiveInterval &nI = getOrCreateInterval(NewVReg);
1208     if (!TrySplit) {
1209       // The spill weight is now infinity as it cannot be spilled again.
1210       nI.weight = HUGE_VALF;
1211       continue;
1212     }
1213
1214     // Keep track of the last def and first use in each MBB.
1215     if (HasDef) {
1216       if (MI != ReMatOrigDefMI || !CanDelete) {
1217         bool HasKill = false;
1218         if (!HasUse)
1219           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1220         else {
1221           // If this is a two-address code, then this index starts a new VNInfo.
1222           const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
1223           if (VNI)
1224             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1225         }
1226         std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1227           SpillIdxes.find(MBBId);
1228         if (!HasKill) {
1229           if (SII == SpillIdxes.end()) {
1230             std::vector<SRInfo> S;
1231             S.push_back(SRInfo(index, NewVReg, true));
1232             SpillIdxes.insert(std::make_pair(MBBId, S));
1233           } else if (SII->second.back().vreg != NewVReg) {
1234             SII->second.push_back(SRInfo(index, NewVReg, true));
1235           } else if ((int)index > SII->second.back().index) {
1236             // If there is an earlier def and this is a two-address
1237             // instruction, then it's not possible to fold the store (which
1238             // would also fold the load).
1239             SRInfo &Info = SII->second.back();
1240             Info.index = index;
1241             Info.canFold = !HasUse;
1242           }
1243           SpillMBBs.set(MBBId);
1244         } else if (SII != SpillIdxes.end() &&
1245                    SII->second.back().vreg == NewVReg &&
1246                    (int)index > SII->second.back().index) {
1247           // There is an earlier def that's not killed (must be two-address).
1248           // The spill is no longer needed.
1249           SII->second.pop_back();
1250           if (SII->second.empty()) {
1251             SpillIdxes.erase(MBBId);
1252             SpillMBBs.reset(MBBId);
1253           }
1254         }
1255       }
1256     }
1257
1258     if (HasUse) {
1259       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1260         SpillIdxes.find(MBBId);
1261       if (SII != SpillIdxes.end() &&
1262           SII->second.back().vreg == NewVReg &&
1263           (int)index > SII->second.back().index)
1264         // Use(s) following the last def, it's not safe to fold the spill.
1265         SII->second.back().canFold = false;
1266       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1267         RestoreIdxes.find(MBBId);
1268       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1269         // If we are splitting live intervals, only fold if it's the first
1270         // use and there isn't another use later in the MBB.
1271         RII->second.back().canFold = false;
1272       else if (IsNew) {
1273         // Only need a reload if there isn't an earlier def / use.
1274         if (RII == RestoreIdxes.end()) {
1275           std::vector<SRInfo> Infos;
1276           Infos.push_back(SRInfo(index, NewVReg, true));
1277           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1278         } else {
1279           RII->second.push_back(SRInfo(index, NewVReg, true));
1280         }
1281         RestoreMBBs.set(MBBId);
1282       }
1283     }
1284
1285     // Update spill weight.
1286     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1287     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1288   }
1289
1290   if (NewVReg && TrySplit && AllCanFold) {
1291     // If all of its def / use can be folded, give it a low spill weight.
1292     LiveInterval &nI = getOrCreateInterval(NewVReg);
1293     nI.weight /= 10.0F;
1294   }
1295 }
1296
1297 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1298                         BitVector &RestoreMBBs,
1299                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1300   if (!RestoreMBBs[Id])
1301     return false;
1302   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1303   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1304     if (Restores[i].index == index &&
1305         Restores[i].vreg == vr &&
1306         Restores[i].canFold)
1307       return true;
1308   return false;
1309 }
1310
1311 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1312                         BitVector &RestoreMBBs,
1313                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1314   if (!RestoreMBBs[Id])
1315     return;
1316   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1317   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1318     if (Restores[i].index == index && Restores[i].vreg)
1319       Restores[i].index = -1;
1320 }
1321
1322
1323 std::vector<LiveInterval*> LiveIntervals::
1324 addIntervalsForSpills(const LiveInterval &li,
1325                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1326   // Since this is called after the analysis is done we don't know if
1327   // LiveVariables is available
1328   lv_ = getAnalysisToUpdate<LiveVariables>();
1329
1330   assert(li.weight != HUGE_VALF &&
1331          "attempt to spill already spilled interval!");
1332
1333   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1334   li.print(DOUT, tri_);
1335   DOUT << '\n';
1336
1337   // Each bit specify whether it a spill is required in the MBB.
1338   BitVector SpillMBBs(mf_->getNumBlockIDs());
1339   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1340   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1341   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1342   std::map<unsigned,unsigned> MBBVRegsMap;
1343   std::vector<LiveInterval*> NewLIs;
1344   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1345
1346   unsigned NumValNums = li.getNumValNums();
1347   SmallVector<MachineInstr*, 4> ReMatDefs;
1348   ReMatDefs.resize(NumValNums, NULL);
1349   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1350   ReMatOrigDefs.resize(NumValNums, NULL);
1351   SmallVector<int, 4> ReMatIds;
1352   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1353   BitVector ReMatDelete(NumValNums);
1354   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1355
1356   // Spilling a split live interval. It cannot be split any further. Also,
1357   // it's also guaranteed to be a single val# / range interval.
1358   if (vrm.getPreSplitReg(li.reg)) {
1359     vrm.setIsSplitFromReg(li.reg, 0);
1360     // Unset the split kill marker on the last use.
1361     unsigned KillIdx = vrm.getKillPoint(li.reg);
1362     if (KillIdx) {
1363       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1364       assert(KillMI && "Last use disappeared?");
1365       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1366       assert(KillOp != -1 && "Last use disappeared?");
1367       KillMI->getOperand(KillOp).setIsKill(false);
1368     }
1369     vrm.removeKillPoint(li.reg);
1370     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1371     Slot = vrm.getStackSlot(li.reg);
1372     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1373     MachineInstr *ReMatDefMI = DefIsReMat ?
1374       vrm.getReMaterializedMI(li.reg) : NULL;
1375     int LdSlot = 0;
1376     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1377     bool isLoad = isLoadSS ||
1378       (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
1379     bool IsFirstRange = true;
1380     for (LiveInterval::Ranges::const_iterator
1381            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1382       // If this is a split live interval with multiple ranges, it means there
1383       // are two-address instructions that re-defined the value. Only the
1384       // first def can be rematerialized!
1385       if (IsFirstRange) {
1386         // Note ReMatOrigDefMI has already been deleted.
1387         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1388                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1389                              false, vrm, rc, ReMatIds, loopInfo,
1390                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1391                              MBBVRegsMap, NewLIs);
1392       } else {
1393         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1394                              Slot, 0, false, false, false,
1395                              false, vrm, rc, ReMatIds, loopInfo,
1396                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1397                              MBBVRegsMap, NewLIs);
1398       }
1399       IsFirstRange = false;
1400     }
1401     return NewLIs;
1402   }
1403
1404   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1405   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1406     TrySplit = false;
1407   if (TrySplit)
1408     ++numSplits;
1409   bool NeedStackSlot = false;
1410   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1411        i != e; ++i) {
1412     const VNInfo *VNI = *i;
1413     unsigned VN = VNI->id;
1414     unsigned DefIdx = VNI->def;
1415     if (DefIdx == ~1U)
1416       continue; // Dead val#.
1417     // Is the def for the val# rematerializable?
1418     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1419       ? 0 : getInstructionFromIndex(DefIdx);
1420     bool dummy;
1421     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1422       // Remember how to remat the def of this val#.
1423       ReMatOrigDefs[VN] = ReMatDefMI;
1424       // Original def may be modified so we have to make a copy here. vrm must
1425       // delete these!
1426       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1427
1428       bool CanDelete = true;
1429       if (VNI->hasPHIKill) {
1430         // A kill is a phi node, not all of its uses can be rematerialized.
1431         // It must not be deleted.
1432         CanDelete = false;
1433         // Need a stack slot if there is any live range where uses cannot be
1434         // rematerialized.
1435         NeedStackSlot = true;
1436       }
1437       if (CanDelete)
1438         ReMatDelete.set(VN);
1439     } else {
1440       // Need a stack slot if there is any live range where uses cannot be
1441       // rematerialized.
1442       NeedStackSlot = true;
1443     }
1444   }
1445
1446   // One stack slot per live interval.
1447   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1448     Slot = vrm.assignVirt2StackSlot(li.reg);
1449
1450   // Create new intervals and rewrite defs and uses.
1451   for (LiveInterval::Ranges::const_iterator
1452          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1453     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1454     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1455     bool DefIsReMat = ReMatDefMI != NULL;
1456     bool CanDelete = ReMatDelete[I->valno->id];
1457     int LdSlot = 0;
1458     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1459     bool isLoad = isLoadSS ||
1460       (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
1461     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1462                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1463                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1464                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1465                                MBBVRegsMap, NewLIs);
1466   }
1467
1468   // Insert spills / restores if we are splitting.
1469   if (!TrySplit)
1470     return NewLIs;
1471
1472   SmallPtrSet<LiveInterval*, 4> AddedKill;
1473   SmallVector<unsigned, 2> Ops;
1474   if (NeedStackSlot) {
1475     int Id = SpillMBBs.find_first();
1476     while (Id != -1) {
1477       std::vector<SRInfo> &spills = SpillIdxes[Id];
1478       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1479         int index = spills[i].index;
1480         unsigned VReg = spills[i].vreg;
1481         LiveInterval &nI = getOrCreateInterval(VReg);
1482         bool isReMat = vrm.isReMaterialized(VReg);
1483         MachineInstr *MI = getInstructionFromIndex(index);
1484         bool CanFold = false;
1485         bool FoundUse = false;
1486         Ops.clear();
1487         if (spills[i].canFold) {
1488           CanFold = true;
1489           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1490             MachineOperand &MO = MI->getOperand(j);
1491             if (!MO.isRegister() || MO.getReg() != VReg)
1492               continue;
1493
1494             Ops.push_back(j);
1495             if (MO.isDef())
1496               continue;
1497             if (isReMat ||
1498                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1499                                                 RestoreMBBs, RestoreIdxes))) {
1500               // MI has two-address uses of the same register. If the use
1501               // isn't the first and only use in the BB, then we can't fold
1502               // it. FIXME: Move this to rewriteInstructionsForSpills.
1503               CanFold = false;
1504               break;
1505             }
1506             FoundUse = true;
1507           }
1508         }
1509         // Fold the store into the def if possible.
1510         bool Folded = false;
1511         if (CanFold && !Ops.empty()) {
1512           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1513             Folded = true;
1514             if (FoundUse > 0) {
1515               // Also folded uses, do not issue a load.
1516               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1517               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1518             }
1519             nI.removeRange(getDefIndex(index), getStoreIndex(index));
1520           }
1521         }
1522
1523         // Else tell the spiller to issue a spill.
1524         if (!Folded) {
1525           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1526           bool isKill = LR->end == getStoreIndex(index);
1527           vrm.addSpillPoint(VReg, isKill, MI);
1528           if (isKill)
1529             AddedKill.insert(&nI);
1530         }
1531       }
1532       Id = SpillMBBs.find_next(Id);
1533     }
1534   }
1535
1536   int Id = RestoreMBBs.find_first();
1537   while (Id != -1) {
1538     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1539     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1540       int index = restores[i].index;
1541       if (index == -1)
1542         continue;
1543       unsigned VReg = restores[i].vreg;
1544       LiveInterval &nI = getOrCreateInterval(VReg);
1545       MachineInstr *MI = getInstructionFromIndex(index);
1546       bool CanFold = false;
1547       Ops.clear();
1548       if (restores[i].canFold) {
1549         CanFold = true;
1550         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1551           MachineOperand &MO = MI->getOperand(j);
1552           if (!MO.isRegister() || MO.getReg() != VReg)
1553             continue;
1554
1555           if (MO.isDef()) {
1556             // If this restore were to be folded, it would have been folded
1557             // already.
1558             CanFold = false;
1559             break;
1560           }
1561           Ops.push_back(j);
1562         }
1563       }
1564
1565       // Fold the load into the use if possible.
1566       bool Folded = false;
1567       if (CanFold && !Ops.empty()) {
1568         if (!vrm.isReMaterialized(VReg))
1569           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1570         else {
1571           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1572           int LdSlot = 0;
1573           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1574           // If the rematerializable def is a load, also try to fold it.
1575           if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
1576             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1577                                           Ops, isLoadSS, LdSlot, VReg);
1578           unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1579           if (ImpUse) {
1580             // Re-matting an instruction with virtual register use. Add the
1581             // register as an implicit use on the use MI and update the register
1582             // interval's spill weight.
1583             unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
1584             LiveInterval &ImpLi = getInterval(ImpUse);
1585             ImpLi.weight +=
1586               getSpillWeight(false, true, loopDepth) / ImpLi.getSize();
1587
1588             MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1589           }
1590         }
1591       }
1592       // If folding is not possible / failed, then tell the spiller to issue a
1593       // load / rematerialization for us.
1594       if (Folded)
1595         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1596       else
1597         vrm.addRestorePoint(VReg, MI);
1598     }
1599     Id = RestoreMBBs.find_next(Id);
1600   }
1601
1602   // Finalize intervals: add kills, finalize spill weights, and filter out
1603   // dead intervals.
1604   std::vector<LiveInterval*> RetNewLIs;
1605   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1606     LiveInterval *LI = NewLIs[i];
1607     if (!LI->empty()) {
1608       LI->weight /= LI->getSize();
1609       if (!AddedKill.count(LI)) {
1610         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
1611         unsigned LastUseIdx = getBaseIndex(LR->end);
1612         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
1613         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg);
1614         assert(UseIdx != -1);
1615         if (LastUse->getOperand(UseIdx).isImplicit() ||
1616             LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
1617           LastUse->getOperand(UseIdx).setIsKill();
1618           vrm.addKillPoint(LI->reg, LastUseIdx);
1619         }
1620       }
1621       RetNewLIs.push_back(LI);
1622     }
1623   }
1624
1625   return RetNewLIs;
1626 }