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,
 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 (mi->registerDefIsDead(interval.reg, tri_))
 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                                               LiveInterval &interval,
 495                                               MachineInstr *CopyMI) {
 496   // A physical register cannot be live across basic block, so its
 497   // lifetime must end somewhere in its defining basic block.
 498   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 499
 500   unsigned baseIndex = MIIdx;
 501   unsigned start = getDefIndex(baseIndex);
 502   unsigned end = start;
 503
 504   // If it is not used after definition, it is considered dead at
 505   // the instruction defining it. Hence its interval is:
 506   // [defSlot(def), defSlot(def)+1)
 507   if (mi->registerDefIsDead(interval.reg, tri_)) {
 508     DOUT << " dead";
 509     end = getDefIndex(start) + 1;
 510     goto exit;
 511   }
 512
 513   // If it is not dead on definition, it must be killed by a
 514   // subsequent instruction. Hence its interval is:
 515   // [defSlot(def), useSlot(kill)+1)
 516   while (++mi != MBB->end()) {
 517     baseIndex += InstrSlots::NUM;
 518     if (mi->killsRegister(interval.reg, tri_)) {
 519       DOUT << " killed";
 520       end = getUseIndex(baseIndex) + 1;
 521       goto exit;
 522     } else if (mi->modifiesRegister(interval.reg, tri_)) {
 523       // Another instruction redefines the register before it is ever read.
 524       // Then the register is essentially dead at the instruction that defines
 525       // it. Hence its interval is:
 526       // [defSlot(def), defSlot(def)+1)
 527       DOUT << " dead";
 528       end = getDefIndex(start) + 1;
 529       goto exit;
 530     }
 531   }
 532
 533   // The only case we should have a dead physreg here without a killing or
 534   // instruction where we know it's dead is if it is live-in to the function
 535   // and never used.
 536   assert(!CopyMI && "physreg was not killed in defining block!");
 537   end = getDefIndex(start) + 1;  // It's dead.
 538
 539 exit:
 540   assert(start < end && "did not find end of interval?");
 541
 542   // Already exists? Extend old live interval.
 543   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 544   VNInfo *ValNo = (OldLR != interval.end())
 545     ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator);
 546   LiveRange LR(start, end, ValNo);
 547   interval.addRange(LR);
 548   interval.addKill(LR.valno, end);
 549   DOUT << " +" << LR << '\n';
 550 }
 551
 552 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 553                                       MachineBasicBlock::iterator MI,
 554                                       unsigned MIIdx,
 555                                       unsigned reg) {
 556   if (TargetRegisterInfo::isVirtualRegister(reg))
 557     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 558   else if (allocatableRegs_[reg]) {
 559     MachineInstr *CopyMI = NULL;
 560     unsigned SrcReg, DstReg;
 561     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
 562         MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG ||
 563         tii_->isMoveInstr(*MI, SrcReg, DstReg))
 564       CopyMI = MI;
 565     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
 566     // Def of a register also defines its sub-registers.
 567     for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS)
 568       // If MI also modifies the sub-register explicitly, avoid processing it
 569       // more than once. Do not pass in TRI here so it checks for exact match.
 570       if (!MI->modifiesRegister(*AS))
 571         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 572   }
 573 }
 574
 575 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 576                                          unsigned MIIdx,
 577                                          LiveInterval &interval, bool isAlias) {
 578   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 579
 580   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 581   // be considered a livein.
 582   MachineBasicBlock::iterator mi = MBB->begin();
 583   unsigned baseIndex = MIIdx;
 584   unsigned start = baseIndex;
 585   unsigned end = start;
 586   while (mi != MBB->end()) {
 587     if (mi->killsRegister(interval.reg, tri_)) {
 588       DOUT << " killed";
 589       end = getUseIndex(baseIndex) + 1;
 590       goto exit;
 591     } else if (mi->modifiesRegister(interval.reg, tri_)) {
 592       // Another instruction redefines the register before it is ever read.
 593       // Then the register is essentially dead at the instruction that defines
 594       // it. Hence its interval is:
 595       // [defSlot(def), defSlot(def)+1)
 596       DOUT << " dead";
 597       end = getDefIndex(start) + 1;
 598       goto exit;
 599     }
 600
 601     baseIndex += InstrSlots::NUM;
 602     ++mi;
 603   }
 604
 605 exit:
 606   // Live-in register might not be used at all.
 607   if (end == MIIdx) {
 608     if (isAlias) {
 609       DOUT << " dead";
 610       end = getDefIndex(MIIdx) + 1;
 611     } else {
 612       DOUT << " live through";
 613       end = baseIndex;
 614     }
 615   }
 616
 617   LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
 618   interval.addRange(LR);
 619   interval.addKill(LR.valno, end);
 620   DOUT << " +" << LR << '\n';
 621 }
 622
 623 /// computeIntervals - computes the live intervals for virtual
 624 /// registers. for some ordering of the machine instructions [1,N] a
 625 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 626 /// which a variable is live
 627 void LiveIntervals::computeIntervals() {
 628   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 629        << "********** Function: "
 630        << ((Value*)mf_->getFunction())->getName() << '\n';
 631   // Track the index of the current machine instr.
 632   unsigned MIIndex = 0;
 633   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 634        MBBI != E; ++MBBI) {
 635     MachineBasicBlock *MBB = MBBI;
 636     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 637
 638     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 639
 640     // Create intervals for live-ins to this BB first.
 641     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 642            LE = MBB->livein_end(); LI != LE; ++LI) {
 643       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 644       // Multiple live-ins can alias the same register.
 645       for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
 646         if (!hasInterval(*AS))
 647           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 648                                true);
 649     }
 650
 651     for (; MI != miEnd; ++MI) {
 652       DOUT << MIIndex << "\t" << *MI;
 653
 654       // Handle defs.
 655       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 656         MachineOperand &MO = MI->getOperand(i);
 657         // handle register defs - build intervals
 658         if (MO.isRegister() && MO.getReg() && MO.isDef())
 659           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 660       }
 661
 662       MIIndex += InstrSlots::NUM;
 663     }
 664
 665     if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB
 666   }
 667 }
 668
 669 bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
 670                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
 671   std::vector<IdxMBBPair>::const_iterator I =
 672     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
 673
 674   bool ResVal = false;
 675   while (I != Idx2MBBMap.end()) {
 676     if (LR.end <= I->first)
 677       break;
 678     MBBs.push_back(I->second);
 679     ResVal = true;
 680     ++I;
 681   }
 682   return ResVal;
 683 }
 684
 685
 686 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 687   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
 688                        HUGE_VALF : 0.0F;
 689   return LiveInterval(reg, Weight);
 690 }
 691
 692 /// getVNInfoSourceReg - Helper function that parses the specified VNInfo
 693 /// copy field and returns the source register that defines it.
 694 unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
 695   if (!VNI->copy)
 696     return 0;
 697
 698   if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 699     return VNI->copy->getOperand(1).getReg();
 700   if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG)
 701     return VNI->copy->getOperand(2).getReg();
 702   unsigned SrcReg, DstReg;
 703   if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
 704     return SrcReg;
 705   assert(0 && "Unrecognized copy instruction!");
 706   return 0;
 707 }
 708
 709 //===----------------------------------------------------------------------===//
 710 // Register allocator hooks.
 711 //
 712
 713 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
 714 /// allow one) virtual register operand, then its uses are implicitly using
 715 /// the register. Returns the virtual register.
 716 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
 717                                             MachineInstr *MI) const {
 718   unsigned RegOp = 0;
 719   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 720     MachineOperand &MO = MI->getOperand(i);
 721     if (!MO.isRegister() || !MO.isUse())
 722       continue;
 723     unsigned Reg = MO.getReg();
 724     if (Reg == 0 || Reg == li.reg)
 725       continue;
 726     // FIXME: For now, only remat MI with at most one register operand.
 727     assert(!RegOp &&
 728            "Can't rematerialize instruction with multiple register operand!");
 729     RegOp = MO.getReg();
 730     break;
 731   }
 732   return RegOp;
 733 }
 734
 735 /// isValNoAvailableAt - Return true if the val# of the specified interval
 736 /// which reaches the given instruction also reaches the specified use index.
 737 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
 738                                        unsigned UseIdx) const {
 739   unsigned Index = getInstructionIndex(MI);
 740   VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
 741   LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
 742   return UI != li.end() && UI->valno == ValNo;
 743 }
 744
 745 /// isReMaterializable - Returns true if the definition MI of the specified
 746 /// val# of the specified interval is re-materializable.
 747 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 748                                        const VNInfo *ValNo, MachineInstr *MI,
 749                                        bool &isLoad) {
 750   if (DisableReMat)
 751     return false;
 752
 753   isLoad = false;
 754   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
 755     return true;
 756
 757   int FrameIdx = 0;
 758   if (tii_->isLoadFromStackSlot(MI, FrameIdx) &&
 759       mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
 760     // FIXME: Let target specific isReallyTriviallyReMaterializable determines
 761     // this but remember this is not safe to fold into a two-address
 762     // instruction.
 763     // This is a load from fixed stack slot. It can be rematerialized.
 764     return true;
 765
 766   if (tii_->isTriviallyReMaterializable(MI)) {
 767     const TargetInstrDesc &TID = MI->getDesc();
 768     isLoad = TID.isSimpleLoad();
 769
 770     unsigned ImpUse = getReMatImplicitUse(li, MI);
 771     if (ImpUse) {
 772       const LiveInterval &ImpLi = getInterval(ImpUse);
 773       for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg),
 774              re = mri_->use_end(); ri != re; ++ri) {
 775         MachineInstr *UseMI = &*ri;
 776         unsigned UseIdx = getInstructionIndex(UseMI);
 777         if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
 778           continue;
 779         if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
 780           return false;
 781       }
 782     }
 783     return true;
 784   }
 785
 786   return false;
 787 }
 788
 789 /// isReMaterializable - Returns true if every definition of MI of every
 790 /// val# of the specified interval is re-materializable.
 791 bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
 792   isLoad = false;
 793   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 794        i != e; ++i) {
 795     const VNInfo *VNI = *i;
 796     unsigned DefIdx = VNI->def;
 797     if (DefIdx == ~1U)
 798       continue; // Dead val#.
 799     // Is the def for the val# rematerializable?
 800     if (DefIdx == ~0u)
 801       return false;
 802     MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
 803     bool DefIsLoad = false;
 804     if (!ReMatDefMI ||
 805         !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
 806       return false;
 807     isLoad |= DefIsLoad;
 808   }
 809   return true;
 810 }
 811
 812 /// FilterFoldedOps - Filter out two-address use operands. Return
 813 /// true if it finds any issue with the operands that ought to prevent
 814 /// folding.
 815 static bool FilterFoldedOps(MachineInstr *MI,
 816                             SmallVector<unsigned, 2> &Ops,
 817                             unsigned &MRInfo,
 818                             SmallVector<unsigned, 2> &FoldOps) {
 819   const TargetInstrDesc &TID = MI->getDesc();
 820
 821   MRInfo = 0;
 822   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 823     unsigned OpIdx = Ops[i];
 824     MachineOperand &MO = MI->getOperand(OpIdx);
 825     // FIXME: fold subreg use.
 826     if (MO.getSubReg())
 827       return true;
 828     if (MO.isDef())
 829       MRInfo |= (unsigned)VirtRegMap::isMod;
 830     else {
 831       // Filter out two-address use operand(s).
 832       if (!MO.isImplicit() &&
 833           TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
 834         MRInfo = VirtRegMap::isModRef;
 835         continue;
 836       }
 837       MRInfo |= (unsigned)VirtRegMap::isRef;
 838     }
 839     FoldOps.push_back(OpIdx);
 840   }
 841   return false;
 842 }
 843
 844
 845 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
 846 /// slot / to reg or any rematerialized load into ith operand of specified
 847 /// MI. If it is successul, MI is updated with the newly created MI and
 848 /// returns true.
 849 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
 850                                          VirtRegMap &vrm, MachineInstr *DefMI,
 851                                          unsigned InstrIdx,
 852                                          SmallVector<unsigned, 2> &Ops,
 853                                          bool isSS, int Slot, unsigned Reg) {
 854   // If it is an implicit def instruction, just delete it.
 855   if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
 856     RemoveMachineInstrFromMaps(MI);
 857     vrm.RemoveMachineInstrFromMaps(MI);
 858     MI->eraseFromParent();
 859     ++numFolds;
 860     return true;
 861   }
 862
 863   // Filter the list of operand indexes that are to be folded. Abort if
 864   // any operand will prevent folding.
 865   unsigned MRInfo = 0;
 866   SmallVector<unsigned, 2> FoldOps;
 867   if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
 868     return false;
 869
 870   // The only time it's safe to fold into a two address instruction is when
 871   // it's folding reload and spill from / into a spill stack slot.
 872   if (DefMI && (MRInfo & VirtRegMap::isMod))
 873     return false;
 874
 875   MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
 876                            : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
 877   if (fmi) {
 878     // Remember this instruction uses the spill slot.
 879     if (isSS) vrm.addSpillSlotUse(Slot, fmi);
 880
 881     // Attempt to fold the memory reference into the instruction. If
 882     // we can do this, we don't need to insert spill code.
 883     if (lv_)
 884       lv_->instructionChanged(MI, fmi);
 885     else
 886       fmi->copyKillDeadInfo(MI, tri_);
 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   bool isMem = MI->getDesc().mayLoad() || MI->getDesc().mayStore();
 983   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 984     MachineOperand& mop = MI->getOperand(i);
 985     if (!mop.isRegister())
 986       continue;
 987     unsigned Reg = mop.getReg();
 988     unsigned RegI = Reg;
 989     if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
 990       continue;
 991     if (Reg != li.reg)
 992       continue;
 993
 994     bool TryFold = !DefIsReMat;
 995     bool FoldSS = true; // Default behavior unless it's a remat.
 996     int FoldSlot = Slot;
 997     if (DefIsReMat) {
 998       // If this is the rematerializable definition MI itself and
 999       // all of its uses are rematerialized, simply delete it.
1000       if (MI == ReMatOrigDefMI && CanDelete) {
1001         DOUT << "\t\t\t\tErasing re-materlizable def: ";
1002         DOUT << MI << '\n';
1003         RemoveMachineInstrFromMaps(MI);
1004         vrm.RemoveMachineInstrFromMaps(MI);
1005         MI->eraseFromParent();
1006         break;
1007       }
1008
1009       // If def for this use can't be rematerialized, then try folding.
1010       // If def is rematerializable and it's a load, also try folding.
1011       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
1012       if (isLoad) {
1013         // Try fold loads (from stack slot, constant pool, etc.) into uses.
1014         FoldSS = isLoadSS;
1015         FoldSlot = LdSlot;
1016       }
1017     }
1018
1019     // Scan all of the operands of this instruction rewriting operands
1020     // to use NewVReg instead of li.reg as appropriate.  We do this for
1021     // two reasons:
1022     //
1023     //   1. If the instr reads the same spilled vreg multiple times, we
1024     //      want to reuse the NewVReg.
1025     //   2. If the instr is a two-addr instruction, we are required to
1026     //      keep the src/dst regs pinned.
1027     //
1028     // Keep track of whether we replace a use and/or def so that we can
1029     // create the spill interval with the appropriate range.
1030
1031     HasUse = mop.isUse();
1032     HasDef = mop.isDef();
1033     SmallVector<unsigned, 2> Ops;
1034     Ops.push_back(i);
1035     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
1036       const MachineOperand &MOj = MI->getOperand(j);
1037       if (!MOj.isRegister())
1038         continue;
1039       unsigned RegJ = MOj.getReg();
1040       if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
1041         continue;
1042       if (RegJ == RegI) {
1043         Ops.push_back(j);
1044         HasUse |= MOj.isUse();
1045         HasDef |= MOj.isDef();
1046       }
1047     }
1048
1049     // Update stack slot spill weight if we are splitting.
1050     float Weight = getSpillWeight(HasDef, HasUse, isMem, loopDepth);
1051       if (!TrySplit)
1052       SSWeight += Weight;
1053
1054     if (!TryFold)
1055       CanFold = false;
1056     else {
1057       // Do not fold load / store here if we are splitting. We'll find an
1058       // optimal point to insert a load / store later.
1059       if (!TrySplit) {
1060         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1061                                  Ops, FoldSS, FoldSlot, Reg)) {
1062           // Folding the load/store can completely change the instruction in
1063           // unpredictable ways, rescan it from the beginning.
1064           HasUse = false;
1065           HasDef = false;
1066           CanFold = false;
1067           if (isRemoved(MI)) {
1068             SSWeight -= Weight;
1069             break;
1070           }
1071           goto RestartInstruction;
1072         }
1073       } else {
1074         // We'll try to fold it later if it's profitable.
1075         CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
1076       }
1077     }
1078
1079     // Create a new virtual register for the spill interval.
1080     bool CreatedNewVReg = false;
1081     if (NewVReg == 0) {
1082       NewVReg = mri_->createVirtualRegister(rc);
1083       vrm.grow();
1084       CreatedNewVReg = true;
1085     }
1086     mop.setReg(NewVReg);
1087     if (mop.isImplicit())
1088       rewriteImplicitOps(li, MI, NewVReg, vrm);
1089
1090     // Reuse NewVReg for other reads.
1091     for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1092       MachineOperand &mopj = MI->getOperand(Ops[j]);
1093       mopj.setReg(NewVReg);
1094       if (mopj.isImplicit())
1095         rewriteImplicitOps(li, MI, NewVReg, vrm);
1096     }
1097
1098     if (CreatedNewVReg) {
1099       if (DefIsReMat) {
1100         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
1101         if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
1102           // Each valnum may have its own remat id.
1103           ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
1104         } else {
1105           vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
1106         }
1107         if (!CanDelete || (HasUse && HasDef)) {
1108           // If this is a two-addr instruction then its use operands are
1109           // rematerializable but its def is not. It should be assigned a
1110           // stack slot.
1111           vrm.assignVirt2StackSlot(NewVReg, Slot);
1112         }
1113       } else {
1114         vrm.assignVirt2StackSlot(NewVReg, Slot);
1115       }
1116     } else if (HasUse && HasDef &&
1117                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1118       // If this interval hasn't been assigned a stack slot (because earlier
1119       // def is a deleted remat def), do it now.
1120       assert(Slot != VirtRegMap::NO_STACK_SLOT);
1121       vrm.assignVirt2StackSlot(NewVReg, Slot);
1122     }
1123
1124     // Re-matting an instruction with virtual register use. Add the
1125     // register as an implicit use on the use MI.
1126     if (DefIsReMat && ImpUse)
1127       MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1128
1129     // create a new register interval for this spill / remat.
1130     LiveInterval &nI = getOrCreateInterval(NewVReg);
1131     if (CreatedNewVReg) {
1132       NewLIs.push_back(&nI);
1133       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
1134       if (TrySplit)
1135         vrm.setIsSplitFromReg(NewVReg, li.reg);
1136     }
1137
1138     if (HasUse) {
1139       if (CreatedNewVReg) {
1140         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
1141                      nI.getNextValue(~0U, 0, VNInfoAllocator));
1142         DOUT << " +" << LR;
1143         nI.addRange(LR);
1144       } else {
1145         // Extend the split live interval to this def / use.
1146         unsigned End = getUseIndex(index)+1;
1147         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1148                      nI.getValNumInfo(nI.getNumValNums()-1));
1149         DOUT << " +" << LR;
1150         nI.addRange(LR);
1151       }
1152     }
1153     if (HasDef) {
1154       LiveRange LR(getDefIndex(index), getStoreIndex(index),
1155                    nI.getNextValue(~0U, 0, VNInfoAllocator));
1156       DOUT << " +" << LR;
1157       nI.addRange(LR);
1158     }
1159
1160     DOUT << "\t\t\t\tAdded new interval: ";
1161     nI.print(DOUT, tri_);
1162     DOUT << '\n';
1163   }
1164   return CanFold;
1165 }
1166 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
1167                                    const VNInfo *VNI,
1168                                    MachineBasicBlock *MBB, unsigned Idx) const {
1169   unsigned End = getMBBEndIdx(MBB);
1170   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
1171     unsigned KillIdx = VNI->kills[j];
1172     if (KillIdx > Idx && KillIdx < End)
1173       return true;
1174   }
1175   return false;
1176 }
1177
1178 /// RewriteInfo - Keep track of machine instrs that will be rewritten
1179 /// during spilling.
1180 namespace {
1181   struct RewriteInfo {
1182     unsigned Index;
1183     MachineInstr *MI;
1184     bool HasUse;
1185     bool HasDef;
1186     RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d)
1187       : Index(i), MI(mi), HasUse(u), HasDef(d) {}
1188   };
1189
1190   struct RewriteInfoCompare {
1191     bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1192       return LHS.Index < RHS.Index;
1193     }
1194   };
1195 }
1196
1197 void LiveIntervals::
1198 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
1199                     LiveInterval::Ranges::const_iterator &I,
1200                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
1201                     unsigned Slot, int LdSlot,
1202                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
1203                     VirtRegMap &vrm,
1204                     const TargetRegisterClass* rc,
1205                     SmallVector<int, 4> &ReMatIds,
1206                     const MachineLoopInfo *loopInfo,
1207                     BitVector &SpillMBBs,
1208                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
1209                     BitVector &RestoreMBBs,
1210                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1211                     std::map<unsigned,unsigned> &MBBVRegsMap,
1212                     std::vector<LiveInterval*> &NewLIs, float &SSWeight) {
1213   bool AllCanFold = true;
1214   unsigned NewVReg = 0;
1215   unsigned start = getBaseIndex(I->start);
1216   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
1217
1218   // First collect all the def / use in this live range that will be rewritten.
1219   // Make sure they are sorted according to instruction index.
1220   std::vector<RewriteInfo> RewriteMIs;
1221   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1222          re = mri_->reg_end(); ri != re; ) {
1223     MachineInstr *MI = &*ri;
1224     MachineOperand &O = ri.getOperand();
1225     ++ri;
1226     assert(!O.isImplicit() && "Spilling register that's used as implicit use?");
1227     unsigned index = getInstructionIndex(MI);
1228     if (index < start || index >= end)
1229       continue;
1230     RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef()));
1231   }
1232   std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1233
1234   unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
1235   // Now rewrite the defs and uses.
1236   for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1237     RewriteInfo &rwi = RewriteMIs[i];
1238     ++i;
1239     unsigned index = rwi.Index;
1240     bool MIHasUse = rwi.HasUse;
1241     bool MIHasDef = rwi.HasDef;
1242     MachineInstr *MI = rwi.MI;
1243     bool isMem = MI->getDesc().mayLoad() || MI->getDesc().mayStore();
1244     // If MI def and/or use the same register multiple times, then there
1245     // are multiple entries.
1246     unsigned NumUses = MIHasUse;
1247     while (i != e && RewriteMIs[i].MI == MI) {
1248       assert(RewriteMIs[i].Index == index);
1249       bool isUse = RewriteMIs[i].HasUse;
1250       if (isUse) ++NumUses;
1251       MIHasUse |= isUse;
1252       MIHasDef |= RewriteMIs[i].HasDef;
1253       ++i;
1254     }
1255     MachineBasicBlock *MBB = MI->getParent();
1256
1257     if (ImpUse && MI != ReMatDefMI) {
1258       // Re-matting an instruction with virtual register use. Update the
1259       // register interval's spill weight to HUGE_VALF to prevent it from
1260       // being spilled.
1261       LiveInterval &ImpLi = getInterval(ImpUse);
1262       ImpLi.weight = HUGE_VALF;
1263     }
1264
1265     unsigned MBBId = MBB->getNumber();
1266     unsigned ThisVReg = 0;
1267     if (TrySplit) {
1268       std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId);
1269       if (NVI != MBBVRegsMap.end()) {
1270         ThisVReg = NVI->second;
1271         // One common case:
1272         // x = use
1273         // ...
1274         // ...
1275         // def = ...
1276         //     = use
1277         // It's better to start a new interval to avoid artifically
1278         // extend the new interval.
1279         if (MIHasDef && !MIHasUse) {
1280           MBBVRegsMap.erase(MBB->getNumber());
1281           ThisVReg = 0;
1282         }
1283       }
1284     }
1285
1286     bool IsNew = ThisVReg == 0;
1287     if (IsNew) {
1288       // This ends the previous live interval. If all of its def / use
1289       // can be folded, give it a low spill weight.
1290       if (NewVReg && TrySplit && AllCanFold) {
1291         LiveInterval &nI = getOrCreateInterval(NewVReg);
1292         nI.weight /= 10.0F;
1293       }
1294       AllCanFold = true;
1295     }
1296     NewVReg = ThisVReg;
1297
1298     bool HasDef = false;
1299     bool HasUse = false;
1300     bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
1301                          index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1302                          Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1303                          CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
1304                          ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight);
1305     if (!HasDef && !HasUse)
1306       continue;
1307
1308     AllCanFold &= CanFold;
1309
1310     // Update weight of spill interval.
1311     LiveInterval &nI = getOrCreateInterval(NewVReg);
1312     if (!TrySplit) {
1313       // The spill weight is now infinity as it cannot be spilled again.
1314       nI.weight = HUGE_VALF;
1315       continue;
1316     }
1317
1318     // Keep track of the last def and first use in each MBB.
1319     if (HasDef) {
1320       if (MI != ReMatOrigDefMI || !CanDelete) {
1321         bool HasKill = false;
1322         if (!HasUse)
1323           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1324         else {
1325           // If this is a two-address code, then this index starts a new VNInfo.
1326           const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index));
1327           if (VNI)
1328             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1329         }
1330         std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1331           SpillIdxes.find(MBBId);
1332         if (!HasKill) {
1333           if (SII == SpillIdxes.end()) {
1334             std::vector<SRInfo> S;
1335             S.push_back(SRInfo(index, NewVReg, true));
1336             SpillIdxes.insert(std::make_pair(MBBId, S));
1337           } else if (SII->second.back().vreg != NewVReg) {
1338             SII->second.push_back(SRInfo(index, NewVReg, true));
1339           } else if ((int)index > SII->second.back().index) {
1340             // If there is an earlier def and this is a two-address
1341             // instruction, then it's not possible to fold the store (which
1342             // would also fold the load).
1343             SRInfo &Info = SII->second.back();
1344             Info.index = index;
1345             Info.canFold = !HasUse;
1346           }
1347           SpillMBBs.set(MBBId);
1348         } else if (SII != SpillIdxes.end() &&
1349                    SII->second.back().vreg == NewVReg &&
1350                    (int)index > SII->second.back().index) {
1351           // There is an earlier def that's not killed (must be two-address).
1352           // The spill is no longer needed.
1353           SII->second.pop_back();
1354           if (SII->second.empty()) {
1355             SpillIdxes.erase(MBBId);
1356             SpillMBBs.reset(MBBId);
1357           }
1358         }
1359       }
1360     }
1361
1362     if (HasUse) {
1363       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1364         SpillIdxes.find(MBBId);
1365       if (SII != SpillIdxes.end() &&
1366           SII->second.back().vreg == NewVReg &&
1367           (int)index > SII->second.back().index)
1368         // Use(s) following the last def, it's not safe to fold the spill.
1369         SII->second.back().canFold = false;
1370       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1371         RestoreIdxes.find(MBBId);
1372       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1373         // If we are splitting live intervals, only fold if it's the first
1374         // use and there isn't another use later in the MBB.
1375         RII->second.back().canFold = false;
1376       else if (IsNew) {
1377         // Only need a reload if there isn't an earlier def / use.
1378         if (RII == RestoreIdxes.end()) {
1379           std::vector<SRInfo> Infos;
1380           Infos.push_back(SRInfo(index, NewVReg, true));
1381           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1382         } else {
1383           RII->second.push_back(SRInfo(index, NewVReg, true));
1384         }
1385         RestoreMBBs.set(MBBId);
1386       }
1387     }
1388
1389     // Update spill weight.
1390     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1391     nI.weight += getSpillWeight(HasDef, HasUse, isMem, loopDepth);
1392   }
1393
1394   if (NewVReg && TrySplit && AllCanFold) {
1395     // If all of its def / use can be folded, give it a low spill weight.
1396     LiveInterval &nI = getOrCreateInterval(NewVReg);
1397     nI.weight /= 10.0F;
1398   }
1399 }
1400
1401 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1402                         BitVector &RestoreMBBs,
1403                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1404   if (!RestoreMBBs[Id])
1405     return false;
1406   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1407   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1408     if (Restores[i].index == index &&
1409         Restores[i].vreg == vr &&
1410         Restores[i].canFold)
1411       return true;
1412   return false;
1413 }
1414
1415 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1416                         BitVector &RestoreMBBs,
1417                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1418   if (!RestoreMBBs[Id])
1419     return;
1420   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1421   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1422     if (Restores[i].index == index && Restores[i].vreg)
1423       Restores[i].index = -1;
1424 }
1425
1426 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1427 /// spilled and create empty intervals for their uses.
1428 void
1429 LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1430                                     const TargetRegisterClass* rc,
1431                                     std::vector<LiveInterval*> &NewLIs) {
1432   for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1433          re = mri_->reg_end(); ri != re; ) {
1434     MachineOperand &O = ri.getOperand();
1435     MachineInstr *MI = &*ri;
1436     ++ri;
1437     if (O.isDef()) {
1438       assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF &&
1439              "Register def was not rewritten?");
1440       RemoveMachineInstrFromMaps(MI);
1441       vrm.RemoveMachineInstrFromMaps(MI);
1442       MI->eraseFromParent();
1443     } else {
1444       // This must be an use of an implicit_def so it's not part of the live
1445       // interval. Create a new empty live interval for it.
1446       // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1447       unsigned NewVReg = mri_->createVirtualRegister(rc);
1448       vrm.grow();
1449       vrm.setIsImplicitlyDefined(NewVReg);
1450       NewLIs.push_back(&getOrCreateInterval(NewVReg));
1451       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1452         MachineOperand &MO = MI->getOperand(i);
1453         if (MO.isReg() && MO.getReg() == li.reg)
1454           MO.setReg(NewVReg);
1455       }
1456     }
1457   }
1458 }
1459
1460
1461 std::vector<LiveInterval*> LiveIntervals::
1462 addIntervalsForSpills(const LiveInterval &li,
1463                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
1464                       float &SSWeight) {
1465   // Since this is called after the analysis is done we don't know if
1466   // LiveVariables is available
1467   lv_ = getAnalysisToUpdate<LiveVariables>();
1468
1469   assert(li.weight != HUGE_VALF &&
1470          "attempt to spill already spilled interval!");
1471
1472   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1473   li.print(DOUT, tri_);
1474   DOUT << '\n';
1475
1476   // Spill slot weight.
1477   SSWeight = 0.0f;
1478
1479   // Each bit specify whether it a spill is required in the MBB.
1480   BitVector SpillMBBs(mf_->getNumBlockIDs());
1481   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1482   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1483   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1484   std::map<unsigned,unsigned> MBBVRegsMap;
1485   std::vector<LiveInterval*> NewLIs;
1486   const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
1487
1488   unsigned NumValNums = li.getNumValNums();
1489   SmallVector<MachineInstr*, 4> ReMatDefs;
1490   ReMatDefs.resize(NumValNums, NULL);
1491   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1492   ReMatOrigDefs.resize(NumValNums, NULL);
1493   SmallVector<int, 4> ReMatIds;
1494   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1495   BitVector ReMatDelete(NumValNums);
1496   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1497
1498   // Spilling a split live interval. It cannot be split any further. Also,
1499   // it's also guaranteed to be a single val# / range interval.
1500   if (vrm.getPreSplitReg(li.reg)) {
1501     vrm.setIsSplitFromReg(li.reg, 0);
1502     // Unset the split kill marker on the last use.
1503     unsigned KillIdx = vrm.getKillPoint(li.reg);
1504     if (KillIdx) {
1505       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1506       assert(KillMI && "Last use disappeared?");
1507       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1508       assert(KillOp != -1 && "Last use disappeared?");
1509       KillMI->getOperand(KillOp).setIsKill(false);
1510     }
1511     vrm.removeKillPoint(li.reg);
1512     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1513     Slot = vrm.getStackSlot(li.reg);
1514     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1515     MachineInstr *ReMatDefMI = DefIsReMat ?
1516       vrm.getReMaterializedMI(li.reg) : NULL;
1517     int LdSlot = 0;
1518     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1519     bool isLoad = isLoadSS ||
1520       (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
1521     bool IsFirstRange = true;
1522     for (LiveInterval::Ranges::const_iterator
1523            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1524       // If this is a split live interval with multiple ranges, it means there
1525       // are two-address instructions that re-defined the value. Only the
1526       // first def can be rematerialized!
1527       if (IsFirstRange) {
1528         // Note ReMatOrigDefMI has already been deleted.
1529         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1530                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1531                              false, vrm, rc, ReMatIds, loopInfo,
1532                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1533                              MBBVRegsMap, NewLIs, SSWeight);
1534       } else {
1535         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1536                              Slot, 0, false, false, false,
1537                              false, vrm, rc, ReMatIds, loopInfo,
1538                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1539                              MBBVRegsMap, NewLIs, SSWeight);
1540       }
1541       IsFirstRange = false;
1542     }
1543
1544     SSWeight = 0.0f;  // Already accounted for when split.
1545     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1546     return NewLIs;
1547   }
1548
1549   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1550   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1551     TrySplit = false;
1552   if (TrySplit)
1553     ++numSplits;
1554   bool NeedStackSlot = false;
1555   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1556        i != e; ++i) {
1557     const VNInfo *VNI = *i;
1558     unsigned VN = VNI->id;
1559     unsigned DefIdx = VNI->def;
1560     if (DefIdx == ~1U)
1561       continue; // Dead val#.
1562     // Is the def for the val# rematerializable?
1563     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1564       ? 0 : getInstructionFromIndex(DefIdx);
1565     bool dummy;
1566     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1567       // Remember how to remat the def of this val#.
1568       ReMatOrigDefs[VN] = ReMatDefMI;
1569       // Original def may be modified so we have to make a copy here. vrm must
1570       // delete these!
1571       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1572
1573       bool CanDelete = true;
1574       if (VNI->hasPHIKill) {
1575         // A kill is a phi node, not all of its uses can be rematerialized.
1576         // It must not be deleted.
1577         CanDelete = false;
1578         // Need a stack slot if there is any live range where uses cannot be
1579         // rematerialized.
1580         NeedStackSlot = true;
1581       }
1582       if (CanDelete)
1583         ReMatDelete.set(VN);
1584     } else {
1585       // Need a stack slot if there is any live range where uses cannot be
1586       // rematerialized.
1587       NeedStackSlot = true;
1588     }
1589   }
1590
1591   // One stack slot per live interval.
1592   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1593     Slot = vrm.assignVirt2StackSlot(li.reg);
1594
1595   // Create new intervals and rewrite defs and uses.
1596   for (LiveInterval::Ranges::const_iterator
1597          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1598     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1599     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1600     bool DefIsReMat = ReMatDefMI != NULL;
1601     bool CanDelete = ReMatDelete[I->valno->id];
1602     int LdSlot = 0;
1603     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1604     bool isLoad = isLoadSS ||
1605       (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
1606     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1607                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1608                                CanDelete, vrm, rc, ReMatIds, loopInfo,
1609                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1610                                MBBVRegsMap, NewLIs, SSWeight);
1611   }
1612
1613   // Insert spills / restores if we are splitting.
1614   if (!TrySplit) {
1615     handleSpilledImpDefs(li, vrm, rc, NewLIs);
1616     return NewLIs;
1617   }
1618
1619   SmallPtrSet<LiveInterval*, 4> AddedKill;
1620   SmallVector<unsigned, 2> Ops;
1621   if (NeedStackSlot) {
1622     int Id = SpillMBBs.find_first();
1623     while (Id != -1) {
1624       MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1625       unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1626       std::vector<SRInfo> &spills = SpillIdxes[Id];
1627       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1628         int index = spills[i].index;
1629         unsigned VReg = spills[i].vreg;
1630         LiveInterval &nI = getOrCreateInterval(VReg);
1631         bool isReMat = vrm.isReMaterialized(VReg);
1632         MachineInstr *MI = getInstructionFromIndex(index);
1633         bool isMem = MI->getDesc().mayLoad() || MI->getDesc().mayStore();
1634         bool CanFold = false;
1635         bool FoundUse = false;
1636         Ops.clear();
1637         if (spills[i].canFold) {
1638           CanFold = true;
1639           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1640             MachineOperand &MO = MI->getOperand(j);
1641             if (!MO.isRegister() || MO.getReg() != VReg)
1642               continue;
1643
1644             Ops.push_back(j);
1645             if (MO.isDef())
1646               continue;
1647             if (isReMat ||
1648                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1649                                                 RestoreMBBs, RestoreIdxes))) {
1650               // MI has two-address uses of the same register. If the use
1651               // isn't the first and only use in the BB, then we can't fold
1652               // it. FIXME: Move this to rewriteInstructionsForSpills.
1653               CanFold = false;
1654               break;
1655             }
1656             FoundUse = true;
1657           }
1658         }
1659         // Fold the store into the def if possible.
1660         bool Folded = false;
1661         if (CanFold && !Ops.empty()) {
1662           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1663             Folded = true;
1664             if (FoundUse > 0) {
1665               // Also folded uses, do not issue a load.
1666               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1667               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1668             }
1669             nI.removeRange(getDefIndex(index), getStoreIndex(index));
1670           }
1671         }
1672
1673         // Otherwise tell the spiller to issue a spill.
1674         if (!Folded) {
1675           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1676           bool isKill = LR->end == getStoreIndex(index);
1677           if (!MI->registerDefIsDead(nI.reg))
1678             // No need to spill a dead def.
1679             vrm.addSpillPoint(VReg, isKill, MI);
1680           if (isKill)
1681             AddedKill.insert(&nI);
1682         }
1683
1684         // Update spill slot weight.
1685         if (!isReMat)
1686           SSWeight += getSpillWeight(true, false, isMem, loopDepth);
1687       }
1688       Id = SpillMBBs.find_next(Id);
1689     }
1690   }
1691
1692   int Id = RestoreMBBs.find_first();
1693   while (Id != -1) {
1694     MachineBasicBlock *MBB = mf_->getBlockNumbered(Id);
1695     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1696
1697     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1698     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1699       int index = restores[i].index;
1700       if (index == -1)
1701         continue;
1702       unsigned VReg = restores[i].vreg;
1703       LiveInterval &nI = getOrCreateInterval(VReg);
1704       bool isReMat = vrm.isReMaterialized(VReg);
1705       MachineInstr *MI = getInstructionFromIndex(index);
1706       bool isMem = MI->getDesc().mayLoad() || MI->getDesc().mayStore();
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, isMem, 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 }