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