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