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