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