lib/CodeGen/LiveIntervalAnalysis.cpp

   1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/LoopInfo.h"
  23 #include "llvm/CodeGen/LiveVariables.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/MRegisterInfo.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include <algorithm>
  36 #include <cmath>
  37 using namespace llvm;
  38
  39 namespace {
  40   // Hidden options for help debugging.
  41   cl::opt<bool> DisableReMat("disable-rematerialization",
  42                               cl::init(false), cl::Hidden);
  43
  44   cl::opt<bool> SplitAtBB("split-intervals-at-bb",
  45                           cl::init(false), cl::Hidden);
  46   cl::opt<int> SplitLimit("split-limit",
  47                           cl::init(-1), cl::Hidden);
  48 }
  49
  50 STATISTIC(numIntervals, "Number of original intervals");
  51 STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
  52 STATISTIC(numFolds    , "Number of loads/stores folded into instructions");
  53 STATISTIC(numSplits   , "Number of intervals split");
  54
  55 char LiveIntervals::ID = 0;
  56 namespace {
  57   RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
  58 }
  59
  60 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  61   AU.addPreserved<LiveVariables>();
  62   AU.addRequired<LiveVariables>();
  63   AU.addPreservedID(PHIEliminationID);
  64   AU.addRequiredID(PHIEliminationID);
  65   AU.addRequiredID(TwoAddressInstructionPassID);
  66   MachineFunctionPass::getAnalysisUsage(AU);
  67 }
  68
  69 void LiveIntervals::releaseMemory() {
  70   Idx2MBBMap.clear();
  71   mi2iMap_.clear();
  72   i2miMap_.clear();
  73   r2iMap_.clear();
  74   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
  75   VNInfoAllocator.Reset();
  76   for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
  77     delete ClonedMIs[i];
  78 }
  79
  80 namespace llvm {
  81   inline bool operator<(unsigned V, const IdxMBBPair &IM) {
  82     return V < IM.first;
  83   }
  84
  85   inline bool operator<(const IdxMBBPair &IM, unsigned V) {
  86     return IM.first < V;
  87   }
  88
  89   struct Idx2MBBCompare {
  90     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
  91       return LHS.first < RHS.first;
  92     }
  93   };
  94 }
  95
  96 /// runOnMachineFunction - Register allocate the whole function
  97 ///
  98 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  99   mf_ = &fn;
 100   tm_ = &fn.getTarget();
 101   mri_ = tm_->getRegisterInfo();
 102   tii_ = tm_->getInstrInfo();
 103   lv_ = &getAnalysis<LiveVariables>();
 104   allocatableRegs_ = mri_->getAllocatableSet(fn);
 105
 106   // Number MachineInstrs and MachineBasicBlocks.
 107   // Initialize MBB indexes to a sentinal.
 108   MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
 109
 110   unsigned MIIndex = 0;
 111   for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
 112        MBB != E; ++MBB) {
 113     unsigned StartIdx = MIIndex;
 114
 115     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
 116          I != E; ++I) {
 117       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
 118       assert(inserted && "multiple MachineInstr -> index mappings");
 119       i2miMap_.push_back(I);
 120       MIIndex += InstrSlots::NUM;
 121     }
 122
 123     // Set the MBB2IdxMap entry for this MBB.
 124     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
 125     Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
 126   }
 127   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
 128
 129   computeIntervals();
 130
 131   numIntervals += getNumIntervals();
 132
 133   DOUT << "********** INTERVALS **********\n";
 134   for (iterator I = begin(), E = end(); I != E; ++I) {
 135     I->second.print(DOUT, mri_);
 136     DOUT << "\n";
 137   }
 138
 139   numIntervalsAfter += getNumIntervals();
 140   DEBUG(dump());
 141   return true;
 142 }
 143
 144 /// print - Implement the dump method.
 145 void LiveIntervals::print(std::ostream &O, const Module* ) const {
 146   O << "********** INTERVALS **********\n";
 147   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 148     I->second.print(DOUT, mri_);
 149     DOUT << "\n";
 150   }
 151
 152   O << "********** MACHINEINSTRS **********\n";
 153   for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
 154        mbbi != mbbe; ++mbbi) {
 155     O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
 156     for (MachineBasicBlock::iterator mii = mbbi->begin(),
 157            mie = mbbi->end(); mii != mie; ++mii) {
 158       O << getInstructionIndex(mii) << '\t' << *mii;
 159     }
 160   }
 161 }
 162
 163 /// conflictsWithPhysRegDef - Returns true if the specified register
 164 /// is defined during the duration of the specified interval.
 165 bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
 166                                             VirtRegMap &vrm, unsigned reg) {
 167   for (LiveInterval::Ranges::const_iterator
 168          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 169     for (unsigned index = getBaseIndex(I->start),
 170            end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
 171          index += InstrSlots::NUM) {
 172       // skip deleted instructions
 173       while (index != end && !getInstructionFromIndex(index))
 174         index += InstrSlots::NUM;
 175       if (index == end) break;
 176
 177       MachineInstr *MI = getInstructionFromIndex(index);
 178       unsigned SrcReg, DstReg;
 179       if (tii_->isMoveInstr(*MI, SrcReg, DstReg))
 180         if (SrcReg == li.reg || DstReg == li.reg)
 181           continue;
 182       for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 183         MachineOperand& mop = MI->getOperand(i);
 184         if (!mop.isRegister())
 185           continue;
 186         unsigned PhysReg = mop.getReg();
 187         if (PhysReg == 0 || PhysReg == li.reg)
 188           continue;
 189         if (MRegisterInfo::isVirtualRegister(PhysReg)) {
 190           if (!vrm.hasPhys(PhysReg))
 191             continue;
 192           PhysReg = vrm.getPhys(PhysReg);
 193         }
 194         if (PhysReg && mri_->regsOverlap(PhysReg, reg))
 195           return true;
 196       }
 197     }
 198   }
 199
 200   return false;
 201 }
 202
 203 void LiveIntervals::printRegName(unsigned reg) const {
 204   if (MRegisterInfo::isPhysicalRegister(reg))
 205     cerr << mri_->getName(reg);
 206   else
 207     cerr << "%reg" << reg;
 208 }
 209
 210 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 211                                              MachineBasicBlock::iterator mi,
 212                                              unsigned MIIdx,
 213                                              LiveInterval &interval) {
 214   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 215   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 216
 217   // Virtual registers may be defined multiple times (due to phi
 218   // elimination and 2-addr elimination).  Much of what we do only has to be
 219   // done once for the vreg.  We use an empty interval to detect the first
 220   // time we see a vreg.
 221   if (interval.empty()) {
 222     // Get the Idx of the defining instructions.
 223     unsigned defIndex = getDefIndex(MIIdx);
 224     VNInfo *ValNo;
 225     unsigned SrcReg, DstReg;
 226     if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
 227       ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
 228     else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 229       ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 230                                     VNInfoAllocator);
 231     else
 232       ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 233
 234     assert(ValNo->id == 0 && "First value in interval is not 0?");
 235
 236     // Loop over all of the blocks that the vreg is defined in.  There are
 237     // two cases we have to handle here.  The most common case is a vreg
 238     // whose lifetime is contained within a basic block.  In this case there
 239     // will be a single kill, in MBB, which comes after the definition.
 240     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 241       // FIXME: what about dead vars?
 242       unsigned killIdx;
 243       if (vi.Kills[0] != mi)
 244         killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
 245       else
 246         killIdx = defIndex+1;
 247
 248       // If the kill happens after the definition, we have an intra-block
 249       // live range.
 250       if (killIdx > defIndex) {
 251         assert(vi.AliveBlocks.none() &&
 252                "Shouldn't be alive across any blocks!");
 253         LiveRange LR(defIndex, killIdx, ValNo);
 254         interval.addRange(LR);
 255         DOUT << " +" << LR << "\n";
 256         interval.addKill(ValNo, killIdx);
 257         return;
 258       }
 259     }
 260
 261     // The other case we handle is when a virtual register lives to the end
 262     // of the defining block, potentially live across some blocks, then is
 263     // live into some number of blocks, but gets killed.  Start by adding a
 264     // range that goes from this definition to the end of the defining block.
 265     LiveRange NewLR(defIndex,
 266                     getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
 267                     ValNo);
 268     DOUT << " +" << NewLR;
 269     interval.addRange(NewLR);
 270
 271     // Iterate over all of the blocks that the variable is completely
 272     // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 273     // live interval.
 274     for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
 275       if (vi.AliveBlocks[i]) {
 276         MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
 277         if (!MBB->empty()) {
 278           LiveRange LR(getMBBStartIdx(i),
 279                        getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
 280                        ValNo);
 281           interval.addRange(LR);
 282           DOUT << " +" << LR;
 283         }
 284       }
 285     }
 286
 287     // Finally, this virtual register is live from the start of any killing
 288     // block to the 'use' slot of the killing instruction.
 289     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 290       MachineInstr *Kill = vi.Kills[i];
 291       unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
 292       LiveRange LR(getMBBStartIdx(Kill->getParent()),
 293                    killIdx, ValNo);
 294       interval.addRange(LR);
 295       interval.addKill(ValNo, killIdx);
 296       DOUT << " +" << LR;
 297     }
 298
 299   } else {
 300     // If this is the second time we see a virtual register definition, it
 301     // must be due to phi elimination or two addr elimination.  If this is
 302     // the result of two address elimination, then the vreg is one of the
 303     // def-and-use register operand.
 304     if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
 305       // If this is a two-address definition, then we have already processed
 306       // the live range.  The only problem is that we didn't realize there
 307       // are actually two values in the live interval.  Because of this we
 308       // need to take the LiveRegion that defines this register and split it
 309       // into two values.
 310       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
 311       unsigned RedefIndex = getDefIndex(MIIdx);
 312
 313       const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
 314       VNInfo *OldValNo = OldLR->valno;
 315       unsigned OldEnd = OldLR->end;
 316
 317       // Delete the initial value, which should be short and continuous,
 318       // because the 2-addr copy must be in the same MBB as the redef.
 319       interval.removeRange(DefIndex, RedefIndex);
 320
 321       // Two-address vregs should always only be redefined once.  This means
 322       // that at this point, there should be exactly one value number in it.
 323       assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
 324
 325       // The new value number (#1) is defined by the instruction we claimed
 326       // defined value #0.
 327       VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
 328       interval.copyValNumInfo(ValNo, OldValNo);
 329
 330       // Value#0 is now defined by the 2-addr instruction.
 331       OldValNo->def = RedefIndex;
 332       OldValNo->reg = 0;
 333
 334       // Add the new live interval which replaces the range for the input copy.
 335       LiveRange LR(DefIndex, RedefIndex, ValNo);
 336       DOUT << " replace range with " << LR;
 337       interval.addRange(LR);
 338       interval.addKill(ValNo, RedefIndex);
 339       interval.removeKills(ValNo, RedefIndex, OldEnd);
 340
 341       // If this redefinition is dead, we need to add a dummy unit live
 342       // range covering the def slot.
 343       if (lv_->RegisterDefIsDead(mi, interval.reg))
 344         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
 345
 346       DOUT << " RESULT: ";
 347       interval.print(DOUT, mri_);
 348
 349     } else {
 350       // Otherwise, this must be because of phi elimination.  If this is the
 351       // first redefinition of the vreg that we have seen, go back and change
 352       // the live range in the PHI block to be a different value number.
 353       if (interval.containsOneValue()) {
 354         assert(vi.Kills.size() == 1 &&
 355                "PHI elimination vreg should have one kill, the PHI itself!");
 356
 357         // Remove the old range that we now know has an incorrect number.
 358         VNInfo *VNI = interval.getValNumInfo(0);
 359         MachineInstr *Killer = vi.Kills[0];
 360         unsigned Start = getMBBStartIdx(Killer->getParent());
 361         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
 362         DOUT << " Removing [" << Start << "," << End << "] from: ";
 363         interval.print(DOUT, mri_); DOUT << "\n";
 364         interval.removeRange(Start, End);
 365         interval.addKill(VNI, Start);
 366         VNI->hasPHIKill = true;
 367         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 368
 369         // Replace the interval with one of a NEW value number.  Note that this
 370         // value number isn't actually defined by an instruction, weird huh? :)
 371         LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
 372         DOUT << " replace range with " << LR;
 373         interval.addRange(LR);
 374         interval.addKill(LR.valno, End);
 375         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 376       }
 377
 378       // In the case of PHI elimination, each variable definition is only
 379       // live until the end of the block.  We've already taken care of the
 380       // rest of the live range.
 381       unsigned defIndex = getDefIndex(MIIdx);
 382
 383       VNInfo *ValNo;
 384       unsigned SrcReg, DstReg;
 385       if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
 386         ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
 387       else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 388         ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
 389                                       VNInfoAllocator);
 390       else
 391         ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
 392
 393       unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
 394       LiveRange LR(defIndex, killIndex, ValNo);
 395       interval.addRange(LR);
 396       interval.addKill(ValNo, killIndex);
 397       ValNo->hasPHIKill = true;
 398       DOUT << " +" << LR;
 399     }
 400   }
 401
 402   DOUT << '\n';
 403 }
 404
 405 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 406                                               MachineBasicBlock::iterator mi,
 407                                               unsigned MIIdx,
 408                                               LiveInterval &interval,
 409                                               unsigned SrcReg) {
 410   // A physical register cannot be live across basic block, so its
 411   // lifetime must end somewhere in its defining basic block.
 412   DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
 413
 414   unsigned baseIndex = MIIdx;
 415   unsigned start = getDefIndex(baseIndex);
 416   unsigned end = start;
 417
 418   // If it is not used after definition, it is considered dead at
 419   // the instruction defining it. Hence its interval is:
 420   // [defSlot(def), defSlot(def)+1)
 421   if (lv_->RegisterDefIsDead(mi, interval.reg)) {
 422     DOUT << " dead";
 423     end = getDefIndex(start) + 1;
 424     goto exit;
 425   }
 426
 427   // If it is not dead on definition, it must be killed by a
 428   // subsequent instruction. Hence its interval is:
 429   // [defSlot(def), useSlot(kill)+1)
 430   while (++mi != MBB->end()) {
 431     baseIndex += InstrSlots::NUM;
 432     if (lv_->KillsRegister(mi, interval.reg)) {
 433       DOUT << " killed";
 434       end = getUseIndex(baseIndex) + 1;
 435       goto exit;
 436     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 437       // Another instruction redefines the register before it is ever read.
 438       // Then the register is essentially dead at the instruction that defines
 439       // it. Hence its interval is:
 440       // [defSlot(def), defSlot(def)+1)
 441       DOUT << " dead";
 442       end = getDefIndex(start) + 1;
 443       goto exit;
 444     }
 445   }
 446
 447   // The only case we should have a dead physreg here without a killing or
 448   // instruction where we know it's dead is if it is live-in to the function
 449   // and never used.
 450   assert(!SrcReg && "physreg was not killed in defining block!");
 451   end = getDefIndex(start) + 1;  // It's dead.
 452
 453 exit:
 454   assert(start < end && "did not find end of interval?");
 455
 456   // Already exists? Extend old live interval.
 457   LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
 458   VNInfo *ValNo = (OldLR != interval.end())
 459     ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
 460   LiveRange LR(start, end, ValNo);
 461   interval.addRange(LR);
 462   interval.addKill(LR.valno, end);
 463   DOUT << " +" << LR << '\n';
 464 }
 465
 466 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 467                                       MachineBasicBlock::iterator MI,
 468                                       unsigned MIIdx,
 469                                       unsigned reg) {
 470   if (MRegisterInfo::isVirtualRegister(reg))
 471     handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
 472   else if (allocatableRegs_[reg]) {
 473     unsigned SrcReg, DstReg;
 474     if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
 475       SrcReg = MI->getOperand(1).getReg();
 476     else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
 477       SrcReg = 0;
 478     handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
 479     // Def of a register also defines its sub-registers.
 480     for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
 481       // Avoid processing some defs more than once.
 482       if (!MI->findRegisterDefOperand(*AS))
 483         handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
 484   }
 485 }
 486
 487 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 488                                          unsigned MIIdx,
 489                                          LiveInterval &interval, bool isAlias) {
 490   DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
 491
 492   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 493   // be considered a livein.
 494   MachineBasicBlock::iterator mi = MBB->begin();
 495   unsigned baseIndex = MIIdx;
 496   unsigned start = baseIndex;
 497   unsigned end = start;
 498   while (mi != MBB->end()) {
 499     if (lv_->KillsRegister(mi, interval.reg)) {
 500       DOUT << " killed";
 501       end = getUseIndex(baseIndex) + 1;
 502       goto exit;
 503     } else if (lv_->ModifiesRegister(mi, interval.reg)) {
 504       // Another instruction redefines the register before it is ever read.
 505       // Then the register is essentially dead at the instruction that defines
 506       // it. Hence its interval is:
 507       // [defSlot(def), defSlot(def)+1)
 508       DOUT << " dead";
 509       end = getDefIndex(start) + 1;
 510       goto exit;
 511     }
 512
 513     baseIndex += InstrSlots::NUM;
 514     ++mi;
 515   }
 516
 517 exit:
 518   // Live-in register might not be used at all.
 519   if (end == MIIdx) {
 520     if (isAlias) {
 521       DOUT << " dead";
 522       end = getDefIndex(MIIdx) + 1;
 523     } else {
 524       DOUT << " live through";
 525       end = baseIndex;
 526     }
 527   }
 528
 529   LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
 530   interval.addRange(LR);
 531   interval.addKill(LR.valno, end);
 532   DOUT << " +" << LR << '\n';
 533 }
 534
 535 /// computeIntervals - computes the live intervals for virtual
 536 /// registers. for some ordering of the machine instructions [1,N] a
 537 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 538 /// which a variable is live
 539 void LiveIntervals::computeIntervals() {
 540   DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
 541        << "********** Function: "
 542        << ((Value*)mf_->getFunction())->getName() << '\n';
 543   // Track the index of the current machine instr.
 544   unsigned MIIndex = 0;
 545   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 546        MBBI != E; ++MBBI) {
 547     MachineBasicBlock *MBB = MBBI;
 548     DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
 549
 550     MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 551
 552     // Create intervals for live-ins to this BB first.
 553     for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
 554            LE = MBB->livein_end(); LI != LE; ++LI) {
 555       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 556       // Multiple live-ins can alias the same register.
 557       for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
 558         if (!hasInterval(*AS))
 559           handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
 560                                true);
 561     }
 562
 563     for (; MI != miEnd; ++MI) {
 564       DOUT << MIIndex << "\t" << *MI;
 565
 566       // Handle defs.
 567       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 568         MachineOperand &MO = MI->getOperand(i);
 569         // handle register defs - build intervals
 570         if (MO.isRegister() && MO.getReg() && MO.isDef())
 571           handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
 572       }
 573
 574       MIIndex += InstrSlots::NUM;
 575     }
 576   }
 577 }
 578
 579 bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
 580                               SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
 581   std::vector<IdxMBBPair>::const_iterator I =
 582     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
 583
 584   bool ResVal = false;
 585   while (I != Idx2MBBMap.end()) {
 586     if (LR.end <= I->first)
 587       break;
 588     MBBs.push_back(I->second);
 589     ResVal = true;
 590     ++I;
 591   }
 592   return ResVal;
 593 }
 594
 595
 596 LiveInterval LiveIntervals::createInterval(unsigned reg) {
 597   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
 598                        HUGE_VALF : 0.0F;
 599   return LiveInterval(reg, Weight);
 600 }
 601
 602
 603 //===----------------------------------------------------------------------===//
 604 // Register allocator hooks.
 605 //
 606
 607 /// isReMaterializable - Returns true if the definition MI of the specified
 608 /// val# of the specified interval is re-materializable.
 609 bool LiveIntervals::isReMaterializable(const LiveInterval &li,
 610                                        const VNInfo *ValNo, MachineInstr *MI) {
 611   if (DisableReMat)
 612     return false;
 613
 614   if (tii_->isTriviallyReMaterializable(MI))
 615     return true;
 616
 617   int FrameIdx = 0;
 618   if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
 619       !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
 620     return false;
 621
 622   // This is a load from fixed stack slot. It can be rematerialized unless it's
 623   // re-defined by a two-address instruction.
 624   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 625        i != e; ++i) {
 626     const VNInfo *VNI = *i;
 627     if (VNI == ValNo)
 628       continue;
 629     unsigned DefIdx = VNI->def;
 630     if (DefIdx == ~1U)
 631       continue; // Dead val#.
 632     MachineInstr *DefMI = (DefIdx == ~0u)
 633       ? NULL : getInstructionFromIndex(DefIdx);
 634     if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
 635       return false;
 636   }
 637   return true;
 638 }
 639
 640 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
 641 /// slot / to reg or any rematerialized load into ith operand of specified
 642 /// MI. If it is successul, MI is updated with the newly created MI and
 643 /// returns true.
 644 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
 645                                          VirtRegMap &vrm,
 646                                          MachineInstr *DefMI,
 647                                          unsigned index, unsigned i,
 648                                          bool isSS, int slot, unsigned reg) {
 649   MachineInstr *fmi = isSS
 650     ? mri_->foldMemoryOperand(MI, i, slot)
 651     : mri_->foldMemoryOperand(MI, i, DefMI);
 652   if (fmi) {
 653     // Attempt to fold the memory reference into the instruction. If
 654     // we can do this, we don't need to insert spill code.
 655     if (lv_)
 656       lv_->instructionChanged(MI, fmi);
 657     else
 658       LiveVariables::transferKillDeadInfo(MI, fmi, mri_);
 659     MachineBasicBlock &MBB = *MI->getParent();
 660     if (isSS) {
 661       if (!mf_->getFrameInfo()->isFixedObjectIndex(slot))
 662         vrm.virtFolded(reg, MI, i, fmi);
 663     }
 664     vrm.transferSpillPts(MI, fmi);
 665     vrm.transferRestorePts(MI, fmi);
 666     mi2iMap_.erase(MI);
 667     i2miMap_[index/InstrSlots::NUM] = fmi;
 668     mi2iMap_[fmi] = index;
 669     MI = MBB.insert(MBB.erase(MI), fmi);
 670     ++numFolds;
 671     return true;
 672   }
 673   return false;
 674 }
 675
 676 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
 677   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
 678   for (LiveInterval::Ranges::const_iterator
 679          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 680     std::vector<IdxMBBPair>::const_iterator II =
 681       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
 682     if (II == Idx2MBBMap.end())
 683       continue;
 684     if (I->end > II->first)  // crossing a MBB.
 685       return false;
 686     MBBs.insert(II->second);
 687     if (MBBs.size() > 1)
 688       return false;
 689   }
 690   return true;
 691 }
 692
 693 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
 694 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 695 void LiveIntervals::
 696 rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
 697                  unsigned id, unsigned index, unsigned end,  MachineInstr *MI,
 698                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 699                  unsigned Slot, int LdSlot,
 700                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 701                  VirtRegMap &vrm, SSARegMap *RegMap,
 702                  const TargetRegisterClass* rc,
 703                  SmallVector<int, 4> &ReMatIds,
 704                  unsigned &NewVReg, bool &HasDef, bool &HasUse,
 705                  const LoopInfo *loopInfo,
 706                  std::map<unsigned,unsigned> &MBBVRegsMap,
 707                  std::vector<LiveInterval*> &NewLIs) {
 708  RestartInstruction:
 709   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 710     MachineOperand& mop = MI->getOperand(i);
 711     if (!mop.isRegister())
 712       continue;
 713     unsigned Reg = mop.getReg();
 714     unsigned RegI = Reg;
 715     if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
 716       continue;
 717     unsigned SubIdx = mop.getSubReg();
 718     bool isSubReg = SubIdx != 0;
 719     if (Reg != li.reg)
 720       continue;
 721
 722     bool TryFold = !DefIsReMat;
 723     bool FoldSS = true; // Default behavior unless it's a remat.
 724     int FoldSlot = Slot;
 725     if (DefIsReMat) {
 726       // If this is the rematerializable definition MI itself and
 727       // all of its uses are rematerialized, simply delete it.
 728       if (MI == ReMatOrigDefMI && CanDelete) {
 729         RemoveMachineInstrFromMaps(MI);
 730         vrm.RemoveMachineInstrFromMaps(MI);
 731         MI->eraseFromParent();
 732         break;
 733       }
 734
 735       // If def for this use can't be rematerialized, then try folding.
 736       // If def is rematerializable and it's a load, also try folding.
 737       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
 738       if (isLoad) {
 739         // Try fold loads (from stack slot, constant pool, etc.) into uses.
 740         FoldSS = isLoadSS;
 741         FoldSlot = LdSlot;
 742       }
 743     }
 744
 745     // Do not fold load / store here if we are splitting. We'll find an
 746     // optimal point to insert a load / store later.
 747     if (TryFold)
 748       TryFold = !TrySplit && NewVReg == 0;
 749
 750     // FIXME: fold subreg use
 751     if (!isSubReg && TryFold &&
 752         tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, i, FoldSS, FoldSlot,
 753                              Reg))
 754       // Folding the load/store can completely change the instruction in
 755       // unpredictable ways, rescan it from the beginning.
 756       goto RestartInstruction;
 757
 758     // Create a new virtual register for the spill interval.
 759     bool CreatedNewVReg = false;
 760     if (NewVReg == 0) {
 761       NewVReg = RegMap->createVirtualRegister(rc);
 762       vrm.grow();
 763       CreatedNewVReg = true;
 764     }
 765     mop.setReg(NewVReg);
 766
 767     // Scan all of the operands of this instruction rewriting operands
 768     // to use NewVReg instead of li.reg as appropriate.  We do this for
 769     // two reasons:
 770     //
 771     //   1. If the instr reads the same spilled vreg multiple times, we
 772     //      want to reuse the NewVReg.
 773     //   2. If the instr is a two-addr instruction, we are required to
 774     //      keep the src/dst regs pinned.
 775     //
 776     // Keep track of whether we replace a use and/or def so that we can
 777     // create the spill interval with the appropriate range.
 778
 779     HasUse = mop.isUse();
 780     HasDef = mop.isDef();
 781     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 782       if (!MI->getOperand(j).isRegister())
 783         continue;
 784       unsigned RegJ = MI->getOperand(j).getReg();
 785       if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ))
 786         continue;
 787       if (RegJ == RegI) {
 788         MI->getOperand(j).setReg(NewVReg);
 789         HasUse |= MI->getOperand(j).isUse();
 790         HasDef |= MI->getOperand(j).isDef();
 791       }
 792     }
 793
 794     if (CreatedNewVReg) {
 795       if (DefIsReMat) {
 796         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
 797         if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) {
 798           // Each valnum may have its own remat id.
 799           ReMatIds[id] = vrm.assignVirtReMatId(NewVReg);
 800         } else {
 801           vrm.assignVirtReMatId(NewVReg, ReMatIds[id]);
 802         }
 803         if (!CanDelete || (HasUse && HasDef)) {
 804           // If this is a two-addr instruction then its use operands are
 805           // rematerializable but its def is not. It should be assigned a
 806           // stack slot.
 807           vrm.assignVirt2StackSlot(NewVReg, Slot);
 808         }
 809       } else {
 810         vrm.assignVirt2StackSlot(NewVReg, Slot);
 811       }
 812     } else if (HasUse && HasDef &&
 813                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
 814       // If this interval hasn't been assigned a stack slot (because earlier
 815       // def is a deleted remat def), do it now.
 816       assert(Slot != VirtRegMap::NO_STACK_SLOT);
 817       vrm.assignVirt2StackSlot(NewVReg, Slot);
 818     }
 819
 820     // create a new register interval for this spill / remat.
 821     LiveInterval &nI = getOrCreateInterval(NewVReg);
 822     if (CreatedNewVReg) {
 823       NewLIs.push_back(&nI);
 824       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
 825       if (TrySplit)
 826         vrm.setIsSplitFromReg(NewVReg, li.reg);
 827     }
 828
 829     if (HasUse) {
 830       if (CreatedNewVReg) {
 831         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
 832                      nI.getNextValue(~0U, 0, VNInfoAllocator));
 833         DOUT << " +" << LR;
 834         nI.addRange(LR);
 835       } else {
 836         // Extend the split live interval to this def / use.
 837         unsigned End = getUseIndex(index)+1;
 838         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
 839                      nI.getValNumInfo(nI.getNumValNums()-1));
 840         DOUT << " +" << LR;
 841         nI.addRange(LR);
 842       }
 843     }
 844     if (HasDef) {
 845       LiveRange LR(getDefIndex(index), getStoreIndex(index),
 846                    nI.getNextValue(~0U, 0, VNInfoAllocator));
 847       DOUT << " +" << LR;
 848       nI.addRange(LR);
 849     }
 850
 851     DOUT << "\t\t\t\tAdded new interval: ";
 852     nI.print(DOUT, mri_);
 853     DOUT << '\n';
 854   }
 855 }
 856
 857 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
 858                                    const VNInfo *VNI,
 859                                    MachineBasicBlock *MBB, unsigned Idx) const {
 860   unsigned End = getMBBEndIdx(MBB);
 861   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
 862     unsigned KillIdx = VNI->kills[j];
 863     if (KillIdx > Idx && KillIdx < End)
 864       return true;
 865   }
 866   return false;
 867 }
 868
 869 static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
 870   const VNInfo *VNI = NULL;
 871   for (LiveInterval::const_vni_iterator i = li.vni_begin(),
 872          e = li.vni_end(); i != e; ++i)
 873     if ((*i)->def == DefIdx) {
 874       VNI = *i;
 875       break;
 876     }
 877   return VNI;
 878 }
 879
 880 void LiveIntervals::
 881 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
 882                     LiveInterval::Ranges::const_iterator &I,
 883                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 884                     unsigned Slot, int LdSlot,
 885                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 886                     VirtRegMap &vrm, SSARegMap *RegMap,
 887                     const TargetRegisterClass* rc,
 888                     SmallVector<int, 4> &ReMatIds,
 889                     const LoopInfo *loopInfo,
 890                     BitVector &SpillMBBs,
 891                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
 892                     BitVector &RestoreMBBs,
 893                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
 894                     std::map<unsigned,unsigned> &MBBVRegsMap,
 895                     std::vector<LiveInterval*> &NewLIs) {
 896   unsigned NewVReg = 0;
 897   unsigned index = getBaseIndex(I->start);
 898   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
 899   bool TrySplitMI = TrySplit && vrm.getPreSplitReg(li.reg) == 0;
 900   for (; index != end; index += InstrSlots::NUM) {
 901     // skip deleted instructions
 902     while (index != end && !getInstructionFromIndex(index))
 903       index += InstrSlots::NUM;
 904     if (index == end) break;
 905
 906     MachineInstr *MI = getInstructionFromIndex(index);
 907     MachineBasicBlock *MBB = MI->getParent();
 908     NewVReg = 0;
 909     if (TrySplitMI) {
 910       std::map<unsigned,unsigned>::const_iterator NVI =
 911         MBBVRegsMap.find(MBB->getNumber());
 912       if (NVI != MBBVRegsMap.end()) {
 913         NewVReg = NVI->second;
 914         // One common case:
 915         // x = use
 916         // ...
 917         // ...
 918         // def = ...
 919         //     = use
 920         // It's better to start a new interval to avoid artifically
 921         // extend the new interval.
 922         // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills?
 923         bool MIHasUse = false;
 924         bool MIHasDef = false;
 925         for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 926           MachineOperand& mop = MI->getOperand(i);
 927           if (!mop.isRegister() || mop.getReg() != li.reg)
 928             continue;
 929           if (mop.isUse())
 930             MIHasUse = true;
 931           else
 932             MIHasDef = true;
 933         }
 934         if (MIHasDef && !MIHasUse) {
 935           MBBVRegsMap.erase(MBB->getNumber());
 936           NewVReg = 0;
 937         }
 938       }
 939     }
 940     bool IsNew = NewVReg == 0;
 941     bool HasDef = false;
 942     bool HasUse = false;
 943     rewriteInstructionForSpills(li, TrySplitMI, I->valno->id, index, end,
 944                                 MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot,
 945                                 isLoad, isLoadSS, DefIsReMat, CanDelete, vrm,
 946                                 RegMap, rc, ReMatIds, NewVReg, HasDef, HasUse,
 947                                 loopInfo, MBBVRegsMap, NewLIs);
 948     if (!HasDef && !HasUse)
 949       continue;
 950
 951     // Update weight of spill interval.
 952     LiveInterval &nI = getOrCreateInterval(NewVReg);
 953     if (!TrySplitMI) {
 954       // The spill weight is now infinity as it cannot be spilled again.
 955       nI.weight = HUGE_VALF;
 956       continue;
 957     }
 958
 959     // Keep track of the last def and first use in each MBB.
 960     unsigned MBBId = MBB->getNumber();
 961     if (HasDef) {
 962       if (MI != ReMatOrigDefMI || !CanDelete) {
 963         bool HasKill = false;
 964         if (!HasUse)
 965           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
 966         else {
 967           // If this is a two-address code, then this index starts a new VNInfo.
 968           const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
 969           if (VNI)
 970             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
 971         }
 972         if (!HasKill) {
 973           std::map<unsigned, std::vector<SRInfo> >::iterator SII =
 974             SpillIdxes.find(MBBId);
 975           if (SII == SpillIdxes.end()) {
 976             std::vector<SRInfo> S;
 977             S.push_back(SRInfo(index, NewVReg, true));
 978             SpillIdxes.insert(std::make_pair(MBBId, S));
 979           } else if (SII->second.back().vreg != NewVReg) {
 980             SII->second.push_back(SRInfo(index, NewVReg, true));
 981           } else if ((int)index > SII->second.back().index) {
 982             // If there is an earlier def and this is a two-address
 983             // instruction, then it's not possible to fold the store (which
 984             // would also fold the load).
 985             SRInfo &Info = SII->second.back();
 986             Info.index = index;
 987             Info.canFold = !HasUse;
 988           }
 989           SpillMBBs.set(MBBId);
 990         }
 991       }
 992     }
 993
 994     if (HasUse) {
 995       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
 996         SpillIdxes.find(MBBId);
 997       if (SII != SpillIdxes.end() &&
 998           SII->second.back().vreg == NewVReg &&
 999           (int)index > SII->second.back().index)
1000         // Use(s) following the last def, it's not safe to fold the spill.
1001         SII->second.back().canFold = false;
1002       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1003         RestoreIdxes.find(MBBId);
1004       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1005         // If we are splitting live intervals, only fold if it's the first
1006         // use and there isn't another use later in the MBB.
1007         RII->second.back().canFold = false;
1008       else if (IsNew) {
1009         // Only need a reload if there isn't an earlier def / use.
1010         if (RII == RestoreIdxes.end()) {
1011           std::vector<SRInfo> Infos;
1012           Infos.push_back(SRInfo(index, NewVReg, true));
1013           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1014         } else {
1015           RII->second.push_back(SRInfo(index, NewVReg, true));
1016         }
1017         RestoreMBBs.set(MBBId);
1018       }
1019     }
1020
1021     // Update spill weight.
1022     unsigned loopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock());
1023     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1024   }
1025 }
1026
1027 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1028                         BitVector &RestoreMBBs,
1029                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1030   if (!RestoreMBBs[Id])
1031     return false;
1032   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1033   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1034     if (Restores[i].index == index &&
1035         Restores[i].vreg == vr &&
1036         Restores[i].canFold)
1037       return true;
1038   return false;
1039 }
1040
1041 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1042                         BitVector &RestoreMBBs,
1043                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1044   if (!RestoreMBBs[Id])
1045     return;
1046   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1047   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1048     if (Restores[i].index == index && Restores[i].vreg)
1049       Restores[i].index = -1;
1050 }
1051
1052
1053 std::vector<LiveInterval*> LiveIntervals::
1054 addIntervalsForSpills(const LiveInterval &li,
1055                       const LoopInfo *loopInfo, VirtRegMap &vrm) {
1056   // Since this is called after the analysis is done we don't know if
1057   // LiveVariables is available
1058   lv_ = getAnalysisToUpdate<LiveVariables>();
1059
1060   assert(li.weight != HUGE_VALF &&
1061          "attempt to spill already spilled interval!");
1062
1063   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1064   li.print(DOUT, mri_);
1065   DOUT << '\n';
1066
1067   // Each bit specify whether it a spill is required in the MBB.
1068   BitVector SpillMBBs(mf_->getNumBlockIDs());
1069   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1070   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1071   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1072   std::map<unsigned,unsigned> MBBVRegsMap;
1073   std::vector<LiveInterval*> NewLIs;
1074   SSARegMap *RegMap = mf_->getSSARegMap();
1075   const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
1076
1077   unsigned NumValNums = li.getNumValNums();
1078   SmallVector<MachineInstr*, 4> ReMatDefs;
1079   ReMatDefs.resize(NumValNums, NULL);
1080   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1081   ReMatOrigDefs.resize(NumValNums, NULL);
1082   SmallVector<int, 4> ReMatIds;
1083   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1084   BitVector ReMatDelete(NumValNums);
1085   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1086
1087   // Spilling a split live interval. It cannot be split any further. Also,
1088   // it's also guaranteed to be a single val# / range interval.
1089   if (vrm.getPreSplitReg(li.reg)) {
1090     vrm.setIsSplitFromReg(li.reg, 0);
1091     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1092     Slot = vrm.getStackSlot(li.reg);
1093     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1094     MachineInstr *ReMatDefMI = DefIsReMat ?
1095       vrm.getReMaterializedMI(li.reg) : NULL;
1096     int LdSlot = 0;
1097     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1098     bool isLoad = isLoadSS ||
1099       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1100     bool IsFirstRange = true;
1101     for (LiveInterval::Ranges::const_iterator
1102            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1103       // If this is a split live interval with multiple ranges, it means there
1104       // are two-address instructions that re-defined the value. Only the
1105       // first def can be rematerialized!
1106       if (IsFirstRange) {
1107         // Note ReMatOrigDefMI has already been deleted.
1108         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1109                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1110                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1111                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1112                              MBBVRegsMap, NewLIs);
1113       } else {
1114         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1115                              Slot, 0, false, false, false,
1116                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1117                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1118                              MBBVRegsMap, NewLIs);
1119       }
1120       IsFirstRange = false;
1121     }
1122     return NewLIs;
1123   }
1124
1125   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1126   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1127     TrySplit = false;
1128   if (TrySplit)
1129     ++numSplits;
1130   bool NeedStackSlot = false;
1131   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1132        i != e; ++i) {
1133     const VNInfo *VNI = *i;
1134     unsigned VN = VNI->id;
1135     unsigned DefIdx = VNI->def;
1136     if (DefIdx == ~1U)
1137       continue; // Dead val#.
1138     // Is the def for the val# rematerializable?
1139     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1140       ? 0 : getInstructionFromIndex(DefIdx);
1141     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI)) {
1142       // Remember how to remat the def of this val#.
1143       ReMatOrigDefs[VN] = ReMatDefMI;
1144       // Original def may be modified so we have to make a copy here. vrm must
1145       // delete these!
1146       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1147       vrm.setVirtIsReMaterialized(li.reg, ReMatDefMI);
1148
1149       bool CanDelete = true;
1150       if (VNI->hasPHIKill) {
1151         // A kill is a phi node, not all of its uses can be rematerialized.
1152         // It must not be deleted.
1153         CanDelete = false;
1154         // Need a stack slot if there is any live range where uses cannot be
1155         // rematerialized.
1156         NeedStackSlot = true;
1157       }
1158       if (CanDelete)
1159         ReMatDelete.set(VN);
1160     } else {
1161       // Need a stack slot if there is any live range where uses cannot be
1162       // rematerialized.
1163       NeedStackSlot = true;
1164     }
1165   }
1166
1167   // One stack slot per live interval.
1168   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1169     Slot = vrm.assignVirt2StackSlot(li.reg);
1170
1171   // Create new intervals and rewrite defs and uses.
1172   for (LiveInterval::Ranges::const_iterator
1173          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1174     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1175     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1176     bool DefIsReMat = ReMatDefMI != NULL;
1177     bool CanDelete = ReMatDelete[I->valno->id];
1178     int LdSlot = 0;
1179     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1180     bool isLoad = isLoadSS ||
1181       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1182     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1183                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1184                                CanDelete, vrm, RegMap, rc, ReMatIds, loopInfo,
1185                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1186                                MBBVRegsMap, NewLIs);
1187   }
1188
1189   // Insert spills / restores if we are splitting.
1190   if (!TrySplit)
1191     return NewLIs;
1192
1193   if (NeedStackSlot) {
1194     int Id = SpillMBBs.find_first();
1195     while (Id != -1) {
1196       std::vector<SRInfo> &spills = SpillIdxes[Id];
1197       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1198         int index = spills[i].index;
1199         unsigned VReg = spills[i].vreg;
1200         bool DoFold = spills[i].canFold;
1201         bool isReMat = vrm.isReMaterialized(VReg);
1202         MachineInstr *MI = getInstructionFromIndex(index);
1203         int OpIdx = -1;
1204         bool FoldedLoad = false;
1205         if (DoFold) {
1206           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1207             MachineOperand &MO = MI->getOperand(j);
1208             if (!MO.isRegister() || MO.getReg() != VReg)
1209               continue;
1210             if (MO.isUse()) {
1211               // Can't fold if it's two-address code and the use isn't the
1212               // first and only use.
1213               // If there are more than one uses, a load is still needed.
1214               if (!isReMat && !FoldedLoad &&
1215                   alsoFoldARestore(Id, index,VReg,RestoreMBBs,RestoreIdxes)) {
1216                 FoldedLoad = true;
1217                 continue;
1218               } else {
1219                 OpIdx = -1;
1220                 break;
1221               }
1222             }
1223             OpIdx = (int)j;
1224           }
1225         }
1226         // Fold the store into the def if possible.
1227         if (OpIdx == -1)
1228           DoFold = false;
1229         if (DoFold) {
1230           if (tryFoldMemoryOperand(MI, vrm, NULL, index,OpIdx,true,Slot,VReg)) {
1231             if (FoldedLoad)
1232               // Folded a two-address instruction, do not issue a load.
1233               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1234           } else
1235             DoFold = false;
1236         }
1237
1238         // Else tell the spiller to issue a store for us.
1239         if (!DoFold)
1240           vrm.addSpillPoint(VReg, MI);
1241       }
1242       Id = SpillMBBs.find_next(Id);
1243     }
1244   }
1245
1246   int Id = RestoreMBBs.find_first();
1247   while (Id != -1) {
1248     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1249     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1250       int index = restores[i].index;
1251       if (index == -1)
1252         continue;
1253       unsigned VReg = restores[i].vreg;
1254       bool DoFold = restores[i].canFold;
1255       MachineInstr *MI = getInstructionFromIndex(index);
1256       int OpIdx = -1;
1257       if (DoFold) {
1258         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1259           MachineOperand &MO = MI->getOperand(j);
1260           if (!MO.isRegister() || MO.getReg() != VReg)
1261             continue;
1262           if (MO.isDef()) {
1263             // Can't fold if it's two-address code.
1264             OpIdx = -1;
1265             break;
1266           }
1267           if (OpIdx != -1) {
1268             // Multiple uses, do not fold!
1269             OpIdx = -1;
1270             break;
1271           }
1272           OpIdx = (int)j;
1273         }
1274       }
1275
1276       // Fold the load into the use if possible.
1277       if (OpIdx == -1)
1278         DoFold = false;
1279       if (DoFold) {
1280         if (vrm.isReMaterialized(VReg)) {
1281           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1282           int LdSlot = 0;
1283           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1284           // If the rematerializable def is a load, also try to fold it.
1285           if (isLoadSS ||
1286               (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG))
1287             DoFold = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, OpIdx,
1288                                           isLoadSS, LdSlot, VReg);
1289           else
1290             DoFold = false;
1291         } else
1292           DoFold = tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx,
1293                                         true, Slot, VReg);
1294       }
1295       // If folding is not possible / failed, then tell the spiller to issue a
1296       // load / rematerialization for us.
1297       if (!DoFold)
1298         vrm.addRestorePoint(VReg, MI);
1299     }
1300     Id = RestoreMBBs.find_next(Id);
1301   }
1302
1303   // Finalize spill weights.
1304   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1305     NewLIs[i]->weight /= NewLIs[i]->getSize();
1306
1307   return NewLIs;
1308 }