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     delete 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     if (lv_)
 888       lv_->instructionChanged(MI, fmi);
 889     else
 890       fmi->copyKillDeadInfo(MI, tri_);
 891     MachineBasicBlock &MBB = *MI->getParent();
 892     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
 893       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
 894     vrm.transferSpillPts(MI, fmi);
 895     vrm.transferRestorePts(MI, fmi);
 896     vrm.transferEmergencySpills(MI, fmi);
 897     mi2iMap_.erase(MI);
 898     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
 899     mi2iMap_[fmi] = InstrIdx;
 900     MI = MBB.insert(MBB.erase(MI), fmi);
 901     ++numFolds;
 902     return true;
 903   }
 904   return false;
 905 }
 906
 907 /// canFoldMemoryOperand - Returns true if the specified load / store
 908 /// folding is possible.
 909 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
 910                                          SmallVector<unsigned, 2> &Ops,
 911                                          bool ReMat) const {
 912   // Filter the list of operand indexes that are to be folded. Abort if
 913   // any operand will prevent folding.
 914   unsigned MRInfo = 0;
 915   SmallVector<unsigned, 2> FoldOps;
 916   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
 917     return false;
 918
 919   // It's only legal to remat for a use, not a def.
 920   if (ReMat && (MRInfo & VirtRegMap::isMod))
 921     return false;
 922
 923   return tii_->canFoldMemoryOperand(MI, FoldOps);
 924 }
 925
 926 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
 927   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
 928   for (LiveInterval::Ranges::const_iterator
 929          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 930     std::vector<IdxMBBPair>::const_iterator II =
 931       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
 932     if (II == Idx2MBBMap.end())
 933       continue;
 934     if (I->end > II->first)  // crossing a MBB.
 935       return false;
 936     MBBs.insert(II->second);
 937     if (MBBs.size() > 1)
 938       return false;
 939   }
 940   return true;
 941 }
 942
 943 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
 944 /// interval on to-be re-materialized operands of MI) with new register.
 945 void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
 946                                        MachineInstr *MI, unsigned NewVReg,
 947                                        VirtRegMap &vrm) {
 948   // There is an implicit use. That means one of the other operand is
 949   // being remat'ed and the remat'ed instruction has li.reg as an
 950   // use operand. Make sure we rewrite that as well.
 951   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 952     MachineOperand &MO = MI->getOperand(i);
 953     if (!MO.isRegister())
 954       continue;
 955     unsigned Reg = MO.getReg();
 956     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 957       continue;
 958     if (!vrm.isReMaterialized(Reg))
 959       continue;
 960     MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
 961     MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
 962     if (UseMO)
 963       UseMO->setReg(NewVReg);
 964   }
 965 }
 966
 967 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
 968 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 969 bool LiveIntervals::
 970 rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
 971                  bool TrySplit, unsigned index, unsigned end,  MachineInstr *MI,
 972                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 973                  unsigned Slot, int LdSlot,
 974                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 975                  VirtRegMap &vrm,
 976                  const TargetRegisterClass* rc,
 977                  SmallVector<int, 4> &ReMatIds,
 978                  const MachineLoopInfo *loopInfo,
 979                  unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
 980                  std::map<unsigned,unsigned> &MBBVRegsMap,
 981                  std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
 982   MachineBasicBlock *MBB = MI->getParent();
 983   unsigned loopDepth = loopInfo->getLoopDepth(MBB);
 984   bool CanFold = false;
 985  RestartInstruction:
 986   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 987     MachineOperand& mop = MI->getOperand(i);
 988     if (!mop.isRegister())
 989       continue;
 990     unsigned Reg = mop.getReg();
 991     unsigned RegI = Reg;
 992     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 993       continue;
 994     if (Reg != li.reg)
 995       continue;
 996
 997     bool TryFold = !DefIsReMat;
 998     bool FoldSS = true; // Default behavior unless it's a remat.
 999     int FoldSlot = Slot;
1000     if (DefIsReMat) {
1001       // If this is the rematerializable definition MI itself and
1002       // all of its uses are rematerialized, simply delete it.
1003       if (MI == ReMatOrigDefMI && CanDelete) {
1004         DOUT << "\t\t\t\tErasing re-materlizable def: ";
1005         DOUT << MI << '\n';
1006         RemoveMachineInstrFromMaps(MI);
1007         vrm.RemoveMachineInstrFromMaps(MI);
1008         MI->eraseFromParent();
1009         break;
1010       }
1011
1012       // If def for this use can't be rematerialized, then try folding.
1013       // If def is rematerializable and it's a load, also try folding.
1014       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1015       if (isLoad) {
1016         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1017         FoldSS = isLoadSS;
1018         FoldSlot = LdSlot;
1019       }
1020     }
1021
1022     // Scan all of the operands of this instruction rewriting operands
1023     // to use NewVReg instead of li.reg as appropriate.  We do this for
1024     // two reasons:
1025     //
1026     //   1. If the instr reads the same spilled vreg multiple times, we
1027     //      want to reuse the NewVReg.
1028     //   2. If the instr is a two-addr instruction, we are required to
1029     //      keep the src/dst regs pinned.
1030     //
1031     // Keep track of whether we replace a use and/or def so that we can
1032     // create the spill interval with the appropriate range.
1033
1034     HasUse = mop.isUse();
1035     HasDef = mop.isDef();
1036     SmallVector<unsigned, 2> Ops;
1037     Ops.push_back(i);
1038     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1039       const MachineOperand &MOj = MI->getOperand(j);
1040       if (!MOj.isRegister())
1041         continue;
1042       unsigned RegJ = MOj.getReg();
1043       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1044         continue;
1045       if (RegJ == RegI) {
1046         Ops.push_back(j);
1047         HasUse |= MOj.isUse();
1048         HasDef |= MOj.isDef();
1049       }
1050     }
1051
1052     // Update stack slot spill weight if we are splitting.
1053     float Weight = getSpillWeight(HasDef, HasUse, loopDepth);
1054       if (!TrySplit)
1055       SSWeight += Weight;
1056
1057     if (!TryFold)
1058       CanFold = false;
1059     else {
1060       // Do not fold load / store here if we are splitting. We'll find an
1061       // optimal point to insert a load / store later.
1062       if (!TrySplit) {
1063         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1064                                  Ops, FoldSS, FoldSlot, Reg)) {
1065           // Folding the load/store can completely change the instruction in
1066           // unpredictable ways, rescan it from the beginning.
1067           HasUse = false;
1068           HasDef = false;
1069           CanFold = false;
1070           if (isRemoved(MI)) {
1071             SSWeight -= Weight;
1072             break;
1073           }
1074           goto RestartInstruction;
1075         }
1076       } else {
1077         // We'll try to fold it later if it's profitable.
1078         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1079       }
1080     }
1081
1082     // Create a new virtual register for the spill interval.
1083     bool CreatedNewVReg = false;
1084     if (NewVReg == 0) {
1085       NewVReg = mri_->createVirtualRegister(rc);
1086       vrm.grow();
1087       CreatedNewVReg = true;
1088     }
1089     mop.setReg(NewVReg);
1090     if (mop.isImplicit())
1091       rewriteImplicitOps(li, MI, NewVReg, vrm);
1092
1093     // Reuse NewVReg for other reads.
1094     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1095       MachineOperand &mopj = MI->getOperand(Ops[j]);
1096       mopj.setReg(NewVReg);
1097       if (mopj.isImplicit())
1098         rewriteImplicitOps(li, MI, NewVReg, vrm);
1099     }
1100
1101     if (CreatedNewVReg) {
1102       if (DefIsReMat) {
1103         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
1104         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1105           // Each valnum may have its own remat id.
1106           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1107         } else {
1108           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1109         }
1110         if (!CanDelete || (HasUse && HasDef)) {
1111           // If this is a two-addr instruction then its use operands are
1112           // rematerializable but its def is not. It should be assigned a
1113           // stack slot.
1114           vrm.assignVirt2StackSlot(NewVReg, Slot);
1115         }
1116       } else {
1117         vrm.assignVirt2StackSlot(NewVReg, Slot);
1118       }
1119     } else if (HasUse && HasDef &&
1120                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1121       // If this interval hasn't been assigned a stack slot (because earlier
1122       // def is a deleted remat def), do it now.
1123       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1124       vrm.assignVirt2StackSlot(NewVReg, Slot);
1125     }
1126
1127     // Re-matting an instruction with virtual register use. Add the
1128     // register as an implicit use on the use MI.
1129     if (DefIsReMat && ImpUse)
1130       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1131
1132     // create a new register interval for this spill / remat.
1133     LiveInterval &nI = getOrCreateInterval(NewVReg);
1134     if (CreatedNewVReg) {
1135       NewLIs.push_back(&nI);
1136       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1137       if (TrySplit)
1138         vrm.setIsSplitFromReg(NewVReg, li.reg);
1139     }
1140
1141     if (HasUse) {
1142       if (CreatedNewVReg) {
1143         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1144                      nI.getNextValue(~0U, 0, VNInfoAllocator));
1145         DOUT << " +" << LR;
1146         nI.addRange(LR);
1147       } else {
1148         // Extend the split live interval to this def / use.
1149         unsigned End = getUseIndex(index)+1;
1150         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1151                      nI.getValNumInfo(nI.getNumValNums()-1));
1152         DOUT << " +" << LR;
1153         nI.addRange(LR);
1154       }
1155     }
1156     if (HasDef) {
1157       LiveRange LR(getDefIndex(index), getStoreIndex(index),
1158                    nI.getNextValue(~0U, 0, VNInfoAllocator));
1159       DOUT << " +" << LR;
1160       nI.addRange(LR);
1161     }
1162
1163     DOUT << "\t\t\t\tAdded new interval: ";
1164     nI.print(DOUT, tri_);
1165     DOUT << '\n';
1166   }
1167   return CanFold;
1168 }
1169 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1170                                    const VNInfo *VNI,
1171                                    MachineBasicBlock *MBB, unsigned Idx) const {
1172   unsigned End = getMBBEndIdx(MBB);
1173   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1174     unsigned KillIdx = VNI->kills[j];
1175     if (KillIdx > Idx && KillIdx < End)
1176       return true;
1177   }
1178   return false;
1179 }
1180
1181 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1182 /// during spilling.
1183 namespace {
1184   struct RewriteInfo {
1185     unsigned Index;
1186     MachineInstr *MI;
1187     bool HasUse;
1188     bool HasDef;
1189     RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1190       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1191   };
1192
1193   struct RewriteInfoCompare {
1194     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1195       return LHS.Index < RHS.Index;
1196     }
1197   };
1198 }
1199
1200 void LiveIntervals::
1201 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1202                     LiveInterval::Ranges::const_iterator &I,
1203                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1204                     unsigned Slot, int LdSlot,
1205                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1206                     VirtRegMap &vrm,
1207                     const TargetRegisterClass* rc,
1208                     SmallVector<int, 4> &ReMatIds,
1209                     const MachineLoopInfo *loopInfo,
1210                     BitVector &SpillMBBs,
1211                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
1212                     BitVector &RestoreMBBs,
1213                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1214                     std::map<unsigned,unsigned> &MBBVRegsMap,
1215                     std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
1216   bool AllCanFold = true;
1217   unsigned NewVReg = 0;
1218   unsigned start = getBaseIndex(I->start);
1219   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1220
1221   // First collect all the def / use in this live range that will be rewritten.
1222   // Make sure they are sorted according to instruction index.
1223   std::vector<RewriteInfo> RewriteMIs;
1224   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1225          re = mri_->reg_end(); ri != re; ) {
1226     MachineInstr *MI = &*ri;
1227     MachineOperand &O = ri.getOperand();
1228     ++ri;
1229     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1230     unsigned index = getInstructionIndex(MI);
1231     if (index < start || index >= end)
1232       continue;
1233     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1234   }
1235   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1236
1237   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1238   // Now rewrite the defs and uses.
1239   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1240     RewriteInfo &rwi = RewriteMIs[i];
1241     ++i;
1242     unsigned index = rwi.Index;
1243     bool MIHasUse = rwi.HasUse;
1244     bool MIHasDef = rwi.HasDef;
1245     MachineInstr *MI = rwi.MI;
1246     // If MI def and/or use the same register multiple times, then there
1247     // are multiple entries.
1248     unsigned NumUses = MIHasUse;
1249     while (i != e && RewriteMIs[i].MI == MI) {
1250       assert(RewriteMIs[i].Index == index);
1251       bool isUse = RewriteMIs[i].HasUse;
1252       if (isUse) ++NumUses;
1253       MIHasUse |= isUse;
1254       MIHasDef |= RewriteMIs[i].HasDef;
1255       ++i;
1256     }
1257     MachineBasicBlock *MBB = MI->getParent();
1258
1259     if (ImpUse && MI != ReMatDefMI) {
1260       // Re-matting an instruction with virtual register use. Update the
1261       // register interval's spill weight to HUGE_VALF to prevent it from
1262       // being spilled.
1263       LiveInterval &ImpLi = getInterval(ImpUse);
1264       ImpLi.weight = HUGE_VALF;
1265     }
1266
1267     unsigned MBBId = MBB->getNumber();
1268     unsigned ThisVReg = 0;
1269     if (TrySplit) {
1270       std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
1271       if (NVI != MBBVRegsMap.end()) {
1272         ThisVReg = NVI->second;
1273         // One common case:
1274         // x = use
1275         // ...
1276         // ...
1277         // def = ...
1278         //     = use
1279         // It's better to start a new interval to avoid artifically
1280         // extend the new interval.
1281         if (MIHasDef && !MIHasUse) {
1282           MBBVRegsMap.erase(MBB->getNumber());
1283           ThisVReg = 0;
1284         }
1285       }
1286     }
1287
1288     bool IsNew = ThisVReg == 0;
1289     if (IsNew) {
1290       // This ends the previous live interval. If all of its def / use
1291       // can be folded, give it a low spill weight.
1292       if (NewVReg && TrySplit && AllCanFold) {
1293         LiveInterval &nI = getOrCreateInterval(NewVReg);
1294         nI.weight /= 10.0F;
1295       }
1296       AllCanFold = true;
1297     }
1298     NewVReg = ThisVReg;
1299
1300     bool HasDef = false;
1301     bool HasUse = false;
1302     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1303                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1304                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1305                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1306                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight);
1307     if (!HasDef && !HasUse)
1308       continue;
1309
1310     AllCanFold &= CanFold;
1311
1312     // Update weight of spill interval.
1313     LiveInterval &nI = getOrCreateInterval(NewVReg);
1314     if (!TrySplit) {
1315       // The spill weight is now infinity as it cannot be spilled again.
1316       nI.weight = HUGE_VALF;
1317       continue;
1318     }
1319
1320     // Keep track of the last def and first use in each MBB.
1321     if (HasDef) {
1322       if (MI != ReMatOrigDefMI || !CanDelete) {
1323         bool HasKill = false;
1324         if (!HasUse)
1325           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1326         else {
1327           // If this is a two-address code, then this index starts a new VNInfo.
1328           const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
1329           if (VNI)
1330             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1331         }
1332         std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1333           SpillIdxes.find(MBBId);
1334         if (!HasKill) {
1335           if (SII == SpillIdxes.end()) {
1336             std::vector<SRInfo> S;
1337             S.push_back(SRInfo(index, NewVReg, true));
1338             SpillIdxes.insert(std::make_pair(MBBId, S));
1339           } else if (SII->second.back().vreg != NewVReg) {
1340             SII->second.push_back(SRInfo(index, NewVReg, true));
1341           } else if ((int)index > SII->second.back().index) {
1342             // If there is an earlier def and this is a two-address
1343             // instruction, then it's not possible to fold the store (which
1344             // would also fold the load).
1345             SRInfo &Info = SII->second.back();
1346             Info.index = index;
1347             Info.canFold = !HasUse;
1348           }
1349           SpillMBBs.set(MBBId);
1350         } else if (SII != SpillIdxes.end() &&
1351                    SII->second.back().vreg == NewVReg &&
1352                    (int)index > SII->second.back().index) {
1353           // There is an earlier def that's not killed (must be two-address).
1354           // The spill is no longer needed.
1355           SII->second.pop_back();
1356           if (SII->second.empty()) {
1357             SpillIdxes.erase(MBBId);
1358             SpillMBBs.reset(MBBId);
1359           }
1360         }
1361       }
1362     }
1363
1364     if (HasUse) {
1365       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1366         SpillIdxes.find(MBBId);
1367       if (SII != SpillIdxes.end() &&
1368           SII->second.back().vreg == NewVReg &&
1369           (int)index > SII->second.back().index)
1370         // Use(s) following the last def, it's not safe to fold the spill.
1371         SII->second.back().canFold = false;
1372       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1373         RestoreIdxes.find(MBBId);
1374       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1375         // If we are splitting live intervals, only fold if it's the first
1376         // use and there isn't another use later in the MBB.
1377         RII->second.back().canFold = false;
1378       else if (IsNew) {
1379         // Only need a reload if there isn't an earlier def / use.
1380         if (RII == RestoreIdxes.end()) {
1381           std::vector<SRInfo> Infos;
1382           Infos.push_back(SRInfo(index, NewVReg, true));
1383           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1384         } else {
1385           RII->second.push_back(SRInfo(index, NewVReg, true));
1386         }
1387         RestoreMBBs.set(MBBId);
1388       }
1389     }
1390
1391     // Update spill weight.
1392     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1393     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1394   }
1395
1396   if (NewVReg && TrySplit && AllCanFold) {
1397     // If all of its def / use can be folded, give it a low spill weight.
1398     LiveInterval &nI = getOrCreateInterval(NewVReg);
1399     nI.weight /= 10.0F;
1400   }
1401 }
1402
1403 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1404                         BitVector &RestoreMBBs,
1405                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1406   if (!RestoreMBBs[Id])
1407     return false;
1408   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1409   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1410     if (Restores[i].index == index &&
1411         Restores[i].vreg == vr &&
1412         Restores[i].canFold)
1413       return true;
1414   return false;
1415 }
1416
1417 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1418                         BitVector &RestoreMBBs,
1419                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1420   if (!RestoreMBBs[Id])
1421     return;
1422   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1423   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1424     if (Restores[i].index == index && Restores[i].vreg)
1425       Restores[i].index = -1;
1426 }
1427
1428 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1429 /// spilled and create empty intervals for their uses.
1430 void
1431 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1432                                     const TargetRegisterClass* rc,
1433                                     std::vector<LiveInterval*> &NewLIs) {
1434   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1435          re = mri_->reg_end(); ri != re; ) {
1436     MachineOperand &O = ri.getOperand();
1437     MachineInstr *MI = &*ri;
1438     ++ri;
1439     if (O.isDef()) {
1440       assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
1441              "Register def was not rewritten?");
1442       RemoveMachineInstrFromMaps(MI);
1443       vrm.RemoveMachineInstrFromMaps(MI);
1444       MI->eraseFromParent();
1445     } else {
1446       // This must be an use of an implicit_def so it's not part of the live
1447       // interval. Create a new empty live interval for it.
1448       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1449       unsigned NewVReg = mri_->createVirtualRegister(rc);
1450       vrm.grow();
1451       vrm.setIsImplicitlyDefined(NewVReg);
1452       NewLIs.push_back(&getOrCreateInterval(NewVReg));
1453       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1454         MachineOperand &MO = MI->getOperand(i);
1455         if (MO.isReg() && MO.getReg() == li.reg)
1456           MO.setReg(NewVReg);
1457       }
1458     }
1459   }
1460 }
1461
1462
1463 std::vector<LiveInterval*> LiveIntervals::
1464 addIntervalsForSpills(const LiveInterval &li,
1465                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
1466                       float &SSWeight) {
1467   // Since this is called after the analysis is done we don't know if
1468   // LiveVariables is available
1469   lv_ = getAnalysisToUpdate<LiveVariables>();
1470
1471   assert(li.weight != HUGE_VALF &&
1472          "attempt to spill already spilled interval!");
1473
1474   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1475   li.print(DOUT, tri_);
1476   DOUT << '\n';
1477
1478   // Spill slot weight.
1479   SSWeight = 0.0f;
1480
1481   // Each bit specify whether it a spill is required in the MBB.
1482   BitVector SpillMBBs(mf_->getNumBlockIDs());
1483   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1484   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1485   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1486   std::map<unsigned,unsigned> MBBVRegsMap;
1487   std::vector<LiveInterval*> NewLIs;
1488   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1489
1490   unsigned NumValNums = li.getNumValNums();
1491   SmallVector<MachineInstr*, 4> ReMatDefs;
1492   ReMatDefs.resize(NumValNums, NULL);
1493   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1494   ReMatOrigDefs.resize(NumValNums, NULL);
1495   SmallVector<int, 4> ReMatIds;
1496   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1497   BitVector ReMatDelete(NumValNums);
1498   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1499
1500   // Spilling a split live interval. It cannot be split any further. Also,
1501   // it's also guaranteed to be a single val# / range interval.
1502   if (vrm.getPreSplitReg(li.reg)) {
1503     vrm.setIsSplitFromReg(li.reg, 0);
1504     // Unset the split kill marker on the last use.
1505     unsigned KillIdx = vrm.getKillPoint(li.reg);
1506     if (KillIdx) {
1507       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1508       assert(KillMI && "Last use disappeared?");
1509       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1510       assert(KillOp != -1 && "Last use disappeared?");
1511       KillMI->getOperand(KillOp).setIsKill(false);
1512     }
1513     vrm.removeKillPoint(li.reg);
1514     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1515     Slot = vrm.getStackSlot(li.reg);
1516     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1517     MachineInstr *ReMatDefMI = DefIsReMat ?
1518       vrm.getReMaterializedMI(li.reg) : NULL;
1519     int LdSlot = 0;
1520     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1521     bool isLoad = isLoadSS ||
1522       (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
1523     bool IsFirstRange = true;
1524     for (LiveInterval::Ranges::const_iterator
1525            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1526       // If this is a split live interval with multiple ranges, it means there
1527       // are two-address instructions that re-defined the value. Only the
1528       // first def can be rematerialized!
1529       if (IsFirstRange) {
1530         // Note ReMatOrigDefMI has already been deleted.
1531         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1532                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1533                              false, vrm, rc, ReMatIds, loopInfo,
1534                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1535                              MBBVRegsMap, NewLIs, SSWeight);
1536       } else {
1537         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1538                              Slot, 0, false, false, false,
1539                              false, vrm, rc, ReMatIds, loopInfo,
1540                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1541                              MBBVRegsMap, NewLIs, SSWeight);
1542       }
1543       IsFirstRange = false;
1544     }
1545
1546     SSWeight = 0.0f;  // Already accounted for when split.
1547     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1548     return NewLIs;
1549   }
1550
1551   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1552   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1553     TrySplit = false;
1554   if (TrySplit)
1555     ++numSplits;
1556   bool NeedStackSlot = false;
1557   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1558        i != e; ++i) {
1559     const VNInfo *VNI = *i;
1560     unsigned VN = VNI->id;
1561     unsigned DefIdx = VNI->def;
1562     if (DefIdx == ~1U)
1563       continue; // Dead val#.
1564     // Is the def for the val# rematerializable?
1565     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1566       ? 0 : getInstructionFromIndex(DefIdx);
1567     bool dummy;
1568     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1569       // Remember how to remat the def of this val#.
1570       ReMatOrigDefs[VN] = ReMatDefMI;
1571       // Original def may be modified so we have to make a copy here. vrm must
1572       // delete these!
1573       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1574
1575       bool CanDelete = true;
1576       if (VNI->hasPHIKill) {
1577         // A kill is a phi node, not all of its uses can be rematerialized.
1578         // It must not be deleted.
1579         CanDelete = false;
1580         // Need a stack slot if there is any live range where uses cannot be
1581         // rematerialized.
1582         NeedStackSlot = true;
1583       }
1584       if (CanDelete)
1585         ReMatDelete.set(VN);
1586     } else {
1587       // Need a stack slot if there is any live range where uses cannot be
1588       // rematerialized.
1589       NeedStackSlot = true;
1590     }
1591   }
1592
1593   // One stack slot per live interval.
1594   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1595     Slot = vrm.assignVirt2StackSlot(li.reg);
1596
1597   // Create new intervals and rewrite defs and uses.
1598   for (LiveInterval::Ranges::const_iterator
1599          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1600     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1601     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1602     bool DefIsReMat = ReMatDefMI != NULL;
1603     bool CanDelete = ReMatDelete[I->valno->id];
1604     int LdSlot = 0;
1605     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1606     bool isLoad = isLoadSS ||
1607       (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
1608     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1609                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1610                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1611                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1612                                MBBVRegsMap, NewLIs, SSWeight);
1613   }
1614
1615   // Insert spills / restores if we are splitting.
1616   if (!TrySplit) {
1617     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1618     return NewLIs;
1619   }
1620
1621   SmallPtrSet<LiveInterval*, 4> AddedKill;
1622   SmallVector<unsigned, 2> Ops;
1623   if (NeedStackSlot) {
1624     int Id = SpillMBBs.find_first();
1625     while (Id != -1) {
1626       MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1627       unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1628       std::vector<SRInfo> &spills = SpillIdxes[Id];
1629       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1630         int index = spills[i].index;
1631         unsigned VReg = spills[i].vreg;
1632         LiveInterval &nI = getOrCreateInterval(VReg);
1633         bool isReMat = vrm.isReMaterialized(VReg);
1634         MachineInstr *MI = getInstructionFromIndex(index);
1635         bool CanFold = false;
1636         bool FoundUse = false;
1637         Ops.clear();
1638         if (spills[i].canFold) {
1639           CanFold = true;
1640           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1641             MachineOperand &MO = MI->getOperand(j);
1642             if (!MO.isRegister() || MO.getReg() != VReg)
1643               continue;
1644
1645             Ops.push_back(j);
1646             if (MO.isDef())
1647               continue;
1648             if (isReMat ||
1649                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1650                                                 RestoreMBBs, RestoreIdxes))) {
1651               // MI has two-address uses of the same register. If the use
1652               // isn't the first and only use in the BB, then we can't fold
1653               // it. FIXME: Move this to rewriteInstructionsForSpills.
1654               CanFold = false;
1655               break;
1656             }
1657             FoundUse = true;
1658           }
1659         }
1660         // Fold the store into the def if possible.
1661         bool Folded = false;
1662         if (CanFold && !Ops.empty()) {
1663           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1664             Folded = true;
1665             if (FoundUse > 0) {
1666               // Also folded uses, do not issue a load.
1667               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1668               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1669             }
1670             nI.removeRange(getDefIndex(index), getStoreIndex(index));
1671           }
1672         }
1673
1674         // Otherwise tell the spiller to issue a spill.
1675         if (!Folded) {
1676           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1677           bool isKill = LR->end == getStoreIndex(index);
1678           if (!MI->registerDefIsDead(nI.reg))
1679             // No need to spill a dead def.
1680             vrm.addSpillPoint(VReg, isKill, MI);
1681           if (isKill)
1682             AddedKill.insert(&nI);
1683         }
1684
1685         // Update spill slot weight.
1686         if (!isReMat)
1687           SSWeight += getSpillWeight(true, false, loopDepth);
1688       }
1689       Id = SpillMBBs.find_next(Id);
1690     }
1691   }
1692
1693   int Id = RestoreMBBs.find_first();
1694   while (Id != -1) {
1695     MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1696     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1697
1698     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1699     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1700       int index = restores[i].index;
1701       if (index == -1)
1702         continue;
1703       unsigned VReg = restores[i].vreg;
1704       LiveInterval &nI = getOrCreateInterval(VReg);
1705       bool isReMat = vrm.isReMaterialized(VReg);
1706       MachineInstr *MI = getInstructionFromIndex(index);
1707       bool CanFold = false;
1708       Ops.clear();
1709       if (restores[i].canFold) {
1710         CanFold = true;
1711         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1712           MachineOperand &MO = MI->getOperand(j);
1713           if (!MO.isRegister() || MO.getReg() != VReg)
1714             continue;
1715
1716           if (MO.isDef()) {
1717             // If this restore were to be folded, it would have been folded
1718             // already.
1719             CanFold = false;
1720             break;
1721           }
1722           Ops.push_back(j);
1723         }
1724       }
1725
1726       // Fold the load into the use if possible.
1727       bool Folded = false;
1728       if (CanFold && !Ops.empty()) {
1729         if (!isReMat)
1730           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1731         else {
1732           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1733           int LdSlot = 0;
1734           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1735           // If the rematerializable def is a load, also try to fold it.
1736           if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
1737             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1738                                           Ops, isLoadSS, LdSlot, VReg);
1739           unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1740           if (ImpUse) {
1741             // Re-matting an instruction with virtual register use. Add the
1742             // register as an implicit use on the use MI and update the register
1743             // interval's spill weight to HUGE_VALF to prevent it from being
1744             // spilled.
1745             LiveInterval &ImpLi = getInterval(ImpUse);
1746             ImpLi.weight = HUGE_VALF;
1747             MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1748           }
1749         }
1750       }
1751       // If folding is not possible / failed, then tell the spiller to issue a
1752       // load / rematerialization for us.
1753       if (Folded)
1754         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1755       else
1756         vrm.addRestorePoint(VReg, MI);
1757
1758       // Update spill slot weight.
1759       if (!isReMat)
1760         SSWeight += getSpillWeight(false, true, loopDepth);
1761     }
1762     Id = RestoreMBBs.find_next(Id);
1763   }
1764
1765   // Finalize intervals: add kills, finalize spill weights, and filter out
1766   // dead intervals.
1767   std::vector<LiveInterval*> RetNewLIs;
1768   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1769     LiveInterval *LI = NewLIs[i];
1770     if (!LI->empty()) {
1771       LI->weight /= LI->getSize();
1772       if (!AddedKill.count(LI)) {
1773         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
1774         unsigned LastUseIdx = getBaseIndex(LR->end);
1775         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
1776         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
1777         assert(UseIdx != -1);
1778         if (LastUse->getOperand(UseIdx).isImplicit() ||
1779             LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){
1780           LastUse->getOperand(UseIdx).setIsKill();
1781           vrm.addKillPoint(LI->reg, LastUseIdx);
1782         }
1783       }
1784       RetNewLIs.push_back(LI);
1785     }
1786   }
1787
1788   handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
1789   return RetNewLIs;
1790 }
1791
1792 /// hasAllocatableSuperReg - Return true if the specified physical register has
1793 /// any super register that's allocatable.
1794 bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
1795   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
1796     if (allocatableRegs_[*AS] && hasInterval(*AS))
1797       return true;
1798   return false;
1799 }
1800
1801 /// getRepresentativeReg - Find the largest super register of the specified
1802 /// physical register.
1803 unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
1804   // Find the largest super-register that is allocatable.
1805   unsigned BestReg = Reg;
1806   for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
1807     unsigned SuperReg = *AS;
1808     if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
1809       BestReg = SuperReg;
1810       break;
1811     }
1812   }
1813   return BestReg;
1814 }
1815
1816 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the
1817 /// specified interval that conflicts with the specified physical register.
1818 unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
1819                                                    unsigned PhysReg) const {
1820   unsigned NumConflicts = 0;
1821   const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
1822   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1823          E = mri_->reg_end(); I != E; ++I) {
1824     MachineOperand &O = I.getOperand();
1825     MachineInstr *MI = O.getParent();
1826     unsigned Index = getInstructionIndex(MI);
1827     if (pli.liveAt(Index))
1828       ++NumConflicts;
1829   }
1830   return NumConflicts;
1831 }
1832
1833 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register
1834 /// around all defs and uses of the specified interval.
1835 void LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
1836                                             unsigned PhysReg, VirtRegMap &vrm) {
1837   unsigned SpillReg = getRepresentativeReg(PhysReg);
1838
1839   for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
1840     // If there are registers which alias PhysReg, but which are not a
1841     // sub-register of the chosen representative super register. Assert
1842     // since we can't handle it yet.
1843     assert(*AS == SpillReg || !allocatableRegs_[*AS] ||
1844            tri_->isSuperRegister(*AS, SpillReg));
1845
1846   LiveInterval &pli = getInterval(SpillReg);
1847   SmallPtrSet<MachineInstr*, 8> SeenMIs;
1848   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1849          E = mri_->reg_end(); I != E; ++I) {
1850     MachineOperand &O = I.getOperand();
1851     MachineInstr *MI = O.getParent();
1852     if (SeenMIs.count(MI))
1853       continue;
1854     SeenMIs.insert(MI);
1855     unsigned Index = getInstructionIndex(MI);
1856     if (pli.liveAt(Index)) {
1857       vrm.addEmergencySpill(SpillReg, MI);
1858       pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
1859       for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) {
1860         if (!hasInterval(*AS))
1861           continue;
1862         LiveInterval &spli = getInterval(*AS);
1863         if (spli.liveAt(Index))
1864           spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1);
1865       }
1866     }
1867   }
1868 }
1869
1870 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
1871                                                    MachineInstr* startInst) {
1872   LiveInterval& Interval = getOrCreateInterval(reg);
1873   VNInfo* VN = Interval.getNextValue(
1874             getInstructionIndex(startInst) + InstrSlots::DEF,
1875             startInst, getVNInfoAllocator());
1876   VN->hasPHIKill = true;
1877   VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
1878   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
1879                getMBBEndIdx(startInst->getParent()) + 1, VN);
1880   Interval.addRange(LR);
1881
1882   return LR;
1883 }