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