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, MachineInstr *DefMI,
 646                                          unsigned InstrIdx, unsigned OpIdx,
 647                                          SmallVector<unsigned, 2> &UseOps,
 648                                          bool isSS, int Slot, unsigned Reg) {
 649   // FIXME: fold subreg use
 650   if (MI->getOperand(OpIdx).getSubReg())
 651     return false;
 652
 653   MachineInstr *fmi = NULL;
 654
 655   if (UseOps.size() < 2)
 656     fmi = isSS ? mri_->foldMemoryOperand(MI, OpIdx, Slot)
 657                : mri_->foldMemoryOperand(MI, OpIdx, DefMI);
 658   else {
 659     if (OpIdx != UseOps[0])
 660       // Must be two-address instruction + one more use. Not going to fold.
 661       return false;
 662     // It may be possible to fold load when there are multiple uses.
 663     // e.g. On x86, TEST32rr r, r -> CMP32rm [mem], 0
 664     fmi = isSS ? mri_->foldMemoryOperand(MI, UseOps, Slot)
 665                : mri_->foldMemoryOperand(MI, UseOps, DefMI);
 666   }
 667
 668   if (fmi) {
 669     // Attempt to fold the memory reference into the instruction. If
 670     // we can do this, we don't need to insert spill code.
 671     if (lv_)
 672       lv_->instructionChanged(MI, fmi);
 673     else
 674       LiveVariables::transferKillDeadInfo(MI, fmi, mri_);
 675     MachineBasicBlock &MBB = *MI->getParent();
 676     if (isSS && !mf_->getFrameInfo()->isFixedObjectIndex(Slot))
 677       vrm.virtFolded(Reg, MI, OpIdx, fmi);
 678     vrm.transferSpillPts(MI, fmi);
 679     vrm.transferRestorePts(MI, fmi);
 680     mi2iMap_.erase(MI);
 681     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
 682     mi2iMap_[fmi] = InstrIdx;
 683     MI = MBB.insert(MBB.erase(MI), fmi);
 684     ++numFolds;
 685     return true;
 686   }
 687   return false;
 688 }
 689
 690 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
 691   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
 692   for (LiveInterval::Ranges::const_iterator
 693          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 694     std::vector<IdxMBBPair>::const_iterator II =
 695       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
 696     if (II == Idx2MBBMap.end())
 697       continue;
 698     if (I->end > II->first)  // crossing a MBB.
 699       return false;
 700     MBBs.insert(II->second);
 701     if (MBBs.size() > 1)
 702       return false;
 703   }
 704   return true;
 705 }
 706
 707 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
 708 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 709 void LiveIntervals::
 710 rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
 711                  unsigned id, unsigned index, unsigned end,  MachineInstr *MI,
 712                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 713                  unsigned Slot, int LdSlot,
 714                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 715                  VirtRegMap &vrm, SSARegMap *RegMap,
 716                  const TargetRegisterClass* rc,
 717                  SmallVector<int, 4> &ReMatIds,
 718                  unsigned &NewVReg, bool &HasDef, bool &HasUse,
 719                  const LoopInfo *loopInfo,
 720                  std::map<unsigned,unsigned> &MBBVRegsMap,
 721                  std::vector<LiveInterval*> &NewLIs) {
 722  RestartInstruction:
 723   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 724     MachineOperand& mop = MI->getOperand(i);
 725     if (!mop.isRegister())
 726       continue;
 727     unsigned Reg = mop.getReg();
 728     unsigned RegI = Reg;
 729     if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
 730       continue;
 731     if (Reg != li.reg)
 732       continue;
 733
 734     bool TryFold = !DefIsReMat;
 735     bool FoldSS = true; // Default behavior unless it's a remat.
 736     int FoldSlot = Slot;
 737     if (DefIsReMat) {
 738       // If this is the rematerializable definition MI itself and
 739       // all of its uses are rematerialized, simply delete it.
 740       if (MI == ReMatOrigDefMI && CanDelete) {
 741         DOUT << "\t\t\t\tErasing re-materlizable def: ";
 742         DOUT << MI << '\n';
 743         RemoveMachineInstrFromMaps(MI);
 744         vrm.RemoveMachineInstrFromMaps(MI);
 745         MI->eraseFromParent();
 746         break;
 747       }
 748
 749       // If def for this use can't be rematerialized, then try folding.
 750       // If def is rematerializable and it's a load, also try folding.
 751       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
 752       if (isLoad) {
 753         // Try fold loads (from stack slot, constant pool, etc.) into uses.
 754         FoldSS = isLoadSS;
 755         FoldSlot = LdSlot;
 756       }
 757     }
 758
 759     // Do not fold load / store here if we are splitting. We'll find an
 760     // optimal point to insert a load / store later.
 761     if (TryFold)
 762       TryFold = !TrySplit && NewVReg == 0;
 763
 764     // Scan all of the operands of this instruction rewriting operands
 765     // to use NewVReg instead of li.reg as appropriate.  We do this for
 766     // two reasons:
 767     //
 768     //   1. If the instr reads the same spilled vreg multiple times, we
 769     //      want to reuse the NewVReg.
 770     //   2. If the instr is a two-addr instruction, we are required to
 771     //      keep the src/dst regs pinned.
 772     //
 773     // Keep track of whether we replace a use and/or def so that we can
 774     // create the spill interval with the appropriate range.
 775
 776     HasUse = mop.isUse();
 777     HasDef = mop.isDef();
 778     SmallVector<unsigned, 2> UseOps;
 779     if (HasUse)
 780       UseOps.push_back(i);
 781     std::vector<unsigned> UpdateOps;
 782     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 783       if (!MI->getOperand(j).isRegister())
 784         continue;
 785       unsigned RegJ = MI->getOperand(j).getReg();
 786       if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ))
 787         continue;
 788       if (RegJ == RegI) {
 789         UpdateOps.push_back(j);
 790         if (MI->getOperand(j).isUse())
 791           UseOps.push_back(j);
 792         HasUse |= MI->getOperand(j).isUse();
 793         HasDef |= MI->getOperand(j).isDef();
 794       }
 795     }
 796
 797     if (TryFold &&
 798         tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, i,
 799                              UseOps, FoldSS, FoldSlot, Reg)) {
 800       // Folding the load/store can completely change the instruction in
 801       // unpredictable ways, rescan it from the beginning.
 802       HasUse = false;
 803       HasDef = false;
 804       goto RestartInstruction;
 805     }
 806
 807     // Create a new virtual register for the spill interval.
 808     bool CreatedNewVReg = false;
 809     if (NewVReg == 0) {
 810       NewVReg = RegMap->createVirtualRegister(rc);
 811       vrm.grow();
 812       CreatedNewVReg = true;
 813     }
 814     mop.setReg(NewVReg);
 815
 816     // Reuse NewVReg for other reads.
 817     for (unsigned j = 0, e = UpdateOps.size(); j != e; ++j)
 818       MI->getOperand(UpdateOps[j]).setReg(NewVReg);
 819
 820     if (CreatedNewVReg) {
 821       if (DefIsReMat) {
 822         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
 823         if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) {
 824           // Each valnum may have its own remat id.
 825           ReMatIds[id] = vrm.assignVirtReMatId(NewVReg);
 826         } else {
 827           vrm.assignVirtReMatId(NewVReg, ReMatIds[id]);
 828         }
 829         if (!CanDelete || (HasUse && HasDef)) {
 830           // If this is a two-addr instruction then its use operands are
 831           // rematerializable but its def is not. It should be assigned a
 832           // stack slot.
 833           vrm.assignVirt2StackSlot(NewVReg, Slot);
 834         }
 835       } else {
 836         vrm.assignVirt2StackSlot(NewVReg, Slot);
 837       }
 838     } else if (HasUse && HasDef &&
 839                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
 840       // If this interval hasn't been assigned a stack slot (because earlier
 841       // def is a deleted remat def), do it now.
 842       assert(Slot != VirtRegMap::NO_STACK_SLOT);
 843       vrm.assignVirt2StackSlot(NewVReg, Slot);
 844     }
 845
 846     // create a new register interval for this spill / remat.
 847     LiveInterval &nI = getOrCreateInterval(NewVReg);
 848     if (CreatedNewVReg) {
 849       NewLIs.push_back(&nI);
 850       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
 851       if (TrySplit)
 852         vrm.setIsSplitFromReg(NewVReg, li.reg);
 853     }
 854
 855     if (HasUse) {
 856       if (CreatedNewVReg) {
 857         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
 858                      nI.getNextValue(~0U, 0, VNInfoAllocator));
 859         DOUT << " +" << LR;
 860         nI.addRange(LR);
 861       } else {
 862         // Extend the split live interval to this def / use.
 863         unsigned End = getUseIndex(index)+1;
 864         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
 865                      nI.getValNumInfo(nI.getNumValNums()-1));
 866         DOUT << " +" << LR;
 867         nI.addRange(LR);
 868       }
 869     }
 870     if (HasDef) {
 871       LiveRange LR(getDefIndex(index), getStoreIndex(index),
 872                    nI.getNextValue(~0U, 0, VNInfoAllocator));
 873       DOUT << " +" << LR;
 874       nI.addRange(LR);
 875     }
 876
 877     DOUT << "\t\t\t\tAdded new interval: ";
 878     nI.print(DOUT, mri_);
 879     DOUT << '\n';
 880   }
 881 }
 882
 883 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
 884                                    const VNInfo *VNI,
 885                                    MachineBasicBlock *MBB, unsigned Idx) const {
 886   unsigned End = getMBBEndIdx(MBB);
 887   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
 888     unsigned KillIdx = VNI->kills[j];
 889     if (KillIdx > Idx && KillIdx < End)
 890       return true;
 891   }
 892   return false;
 893 }
 894
 895 static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
 896   const VNInfo *VNI = NULL;
 897   for (LiveInterval::const_vni_iterator i = li.vni_begin(),
 898          e = li.vni_end(); i != e; ++i)
 899     if ((*i)->def == DefIdx) {
 900       VNI = *i;
 901       break;
 902     }
 903   return VNI;
 904 }
 905
 906 void LiveIntervals::
 907 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
 908                     LiveInterval::Ranges::const_iterator &I,
 909                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 910                     unsigned Slot, int LdSlot,
 911                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 912                     VirtRegMap &vrm, SSARegMap *RegMap,
 913                     const TargetRegisterClass* rc,
 914                     SmallVector<int, 4> &ReMatIds,
 915                     const LoopInfo *loopInfo,
 916                     BitVector &SpillMBBs,
 917                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
 918                     BitVector &RestoreMBBs,
 919                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
 920                     std::map<unsigned,unsigned> &MBBVRegsMap,
 921                     std::vector<LiveInterval*> &NewLIs) {
 922   unsigned NewVReg = 0;
 923   unsigned index = getBaseIndex(I->start);
 924   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
 925   bool TrySplitMI = TrySplit && vrm.getPreSplitReg(li.reg) == 0;
 926   for (; index != end; index += InstrSlots::NUM) {
 927     // skip deleted instructions
 928     while (index != end && !getInstructionFromIndex(index))
 929       index += InstrSlots::NUM;
 930     if (index == end) break;
 931
 932     MachineInstr *MI = getInstructionFromIndex(index);
 933     MachineBasicBlock *MBB = MI->getParent();
 934     NewVReg = 0;
 935     if (TrySplitMI) {
 936       std::map<unsigned,unsigned>::const_iterator NVI =
 937         MBBVRegsMap.find(MBB->getNumber());
 938       if (NVI != MBBVRegsMap.end()) {
 939         NewVReg = NVI->second;
 940         // One common case:
 941         // x = use
 942         // ...
 943         // ...
 944         // def = ...
 945         //     = use
 946         // It's better to start a new interval to avoid artifically
 947         // extend the new interval.
 948         // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills?
 949         bool MIHasUse = false;
 950         bool MIHasDef = false;
 951         for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 952           MachineOperand& mop = MI->getOperand(i);
 953           if (!mop.isRegister() || mop.getReg() != li.reg)
 954             continue;
 955           if (mop.isUse())
 956             MIHasUse = true;
 957           else
 958             MIHasDef = true;
 959         }
 960         if (MIHasDef && !MIHasUse) {
 961           MBBVRegsMap.erase(MBB->getNumber());
 962           NewVReg = 0;
 963         }
 964       }
 965     }
 966     bool IsNew = NewVReg == 0;
 967     bool HasDef = false;
 968     bool HasUse = false;
 969     rewriteInstructionForSpills(li, TrySplitMI, I->valno->id, index, end,
 970                                 MI, ReMatOrigDefMI, ReMatDefMI, Slot, LdSlot,
 971                                 isLoad, isLoadSS, DefIsReMat, CanDelete, vrm,
 972                                 RegMap, rc, ReMatIds, NewVReg, HasDef, HasUse,
 973                                 loopInfo, MBBVRegsMap, NewLIs);
 974     if (!HasDef && !HasUse)
 975       continue;
 976
 977     // Update weight of spill interval.
 978     LiveInterval &nI = getOrCreateInterval(NewVReg);
 979     if (!TrySplitMI) {
 980       // The spill weight is now infinity as it cannot be spilled again.
 981       nI.weight = HUGE_VALF;
 982       continue;
 983     }
 984
 985     // Keep track of the last def and first use in each MBB.
 986     unsigned MBBId = MBB->getNumber();
 987     if (HasDef) {
 988       if (MI != ReMatOrigDefMI || !CanDelete) {
 989         bool HasKill = false;
 990         if (!HasUse)
 991           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
 992         else {
 993           // If this is a two-address code, then this index starts a new VNInfo.
 994           const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
 995           if (VNI)
 996             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
 997         }
 998         if (!HasKill) {
 999           std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1000             SpillIdxes.find(MBBId);
1001           if (SII == SpillIdxes.end()) {
1002             std::vector<SRInfo> S;
1003             S.push_back(SRInfo(index, NewVReg, true));
1004             SpillIdxes.insert(std::make_pair(MBBId, S));
1005           } else if (SII->second.back().vreg != NewVReg) {
1006             SII->second.push_back(SRInfo(index, NewVReg, true));
1007           } else if ((int)index > SII->second.back().index) {
1008             // If there is an earlier def and this is a two-address
1009             // instruction, then it's not possible to fold the store (which
1010             // would also fold the load).
1011             SRInfo &Info = SII->second.back();
1012             Info.index = index;
1013             Info.canFold = !HasUse;
1014           }
1015           SpillMBBs.set(MBBId);
1016         }
1017       }
1018     }
1019
1020     if (HasUse) {
1021       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1022         SpillIdxes.find(MBBId);
1023       if (SII != SpillIdxes.end() &&
1024           SII->second.back().vreg == NewVReg &&
1025           (int)index > SII->second.back().index)
1026         // Use(s) following the last def, it's not safe to fold the spill.
1027         SII->second.back().canFold = false;
1028       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1029         RestoreIdxes.find(MBBId);
1030       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1031         // If we are splitting live intervals, only fold if it's the first
1032         // use and there isn't another use later in the MBB.
1033         RII->second.back().canFold = false;
1034       else if (IsNew) {
1035         // Only need a reload if there isn't an earlier def / use.
1036         if (RII == RestoreIdxes.end()) {
1037           std::vector<SRInfo> Infos;
1038           Infos.push_back(SRInfo(index, NewVReg, true));
1039           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1040         } else {
1041           RII->second.push_back(SRInfo(index, NewVReg, true));
1042         }
1043         RestoreMBBs.set(MBBId);
1044       }
1045     }
1046
1047     // Update spill weight.
1048     unsigned loopDepth = loopInfo->getLoopDepth(MBB->getBasicBlock());
1049     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1050   }
1051 }
1052
1053 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1054                         BitVector &RestoreMBBs,
1055                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1056   if (!RestoreMBBs[Id])
1057     return false;
1058   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1059   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1060     if (Restores[i].index == index &&
1061         Restores[i].vreg == vr &&
1062         Restores[i].canFold)
1063       return true;
1064   return false;
1065 }
1066
1067 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1068                         BitVector &RestoreMBBs,
1069                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1070   if (!RestoreMBBs[Id])
1071     return;
1072   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1073   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1074     if (Restores[i].index == index && Restores[i].vreg)
1075       Restores[i].index = -1;
1076 }
1077
1078
1079 std::vector<LiveInterval*> LiveIntervals::
1080 addIntervalsForSpills(const LiveInterval &li,
1081                       const LoopInfo *loopInfo, VirtRegMap &vrm) {
1082   // Since this is called after the analysis is done we don't know if
1083   // LiveVariables is available
1084   lv_ = getAnalysisToUpdate<LiveVariables>();
1085
1086   assert(li.weight != HUGE_VALF &&
1087          "attempt to spill already spilled interval!");
1088
1089   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1090   li.print(DOUT, mri_);
1091   DOUT << '\n';
1092
1093   // Each bit specify whether it a spill is required in the MBB.
1094   BitVector SpillMBBs(mf_->getNumBlockIDs());
1095   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1096   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1097   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1098   std::map<unsigned,unsigned> MBBVRegsMap;
1099   std::vector<LiveInterval*> NewLIs;
1100   SSARegMap *RegMap = mf_->getSSARegMap();
1101   const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
1102
1103   unsigned NumValNums = li.getNumValNums();
1104   SmallVector<MachineInstr*, 4> ReMatDefs;
1105   ReMatDefs.resize(NumValNums, NULL);
1106   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1107   ReMatOrigDefs.resize(NumValNums, NULL);
1108   SmallVector<int, 4> ReMatIds;
1109   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1110   BitVector ReMatDelete(NumValNums);
1111   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1112
1113   // Spilling a split live interval. It cannot be split any further. Also,
1114   // it's also guaranteed to be a single val# / range interval.
1115   if (vrm.getPreSplitReg(li.reg)) {
1116     vrm.setIsSplitFromReg(li.reg, 0);
1117     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1118     Slot = vrm.getStackSlot(li.reg);
1119     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1120     MachineInstr *ReMatDefMI = DefIsReMat ?
1121       vrm.getReMaterializedMI(li.reg) : NULL;
1122     int LdSlot = 0;
1123     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1124     bool isLoad = isLoadSS ||
1125       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1126     bool IsFirstRange = true;
1127     for (LiveInterval::Ranges::const_iterator
1128            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1129       // If this is a split live interval with multiple ranges, it means there
1130       // are two-address instructions that re-defined the value. Only the
1131       // first def can be rematerialized!
1132       if (IsFirstRange) {
1133         // Note ReMatOrigDefMI has already been deleted.
1134         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1135                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1136                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1137                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1138                              MBBVRegsMap, NewLIs);
1139       } else {
1140         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1141                              Slot, 0, false, false, false,
1142                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1143                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1144                              MBBVRegsMap, NewLIs);
1145       }
1146       IsFirstRange = false;
1147     }
1148     return NewLIs;
1149   }
1150
1151   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1152   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1153     TrySplit = false;
1154   if (TrySplit)
1155     ++numSplits;
1156   bool NeedStackSlot = false;
1157   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1158        i != e; ++i) {
1159     const VNInfo *VNI = *i;
1160     unsigned VN = VNI->id;
1161     unsigned DefIdx = VNI->def;
1162     if (DefIdx == ~1U)
1163       continue; // Dead val#.
1164     // Is the def for the val# rematerializable?
1165     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1166       ? 0 : getInstructionFromIndex(DefIdx);
1167     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI)) {
1168       // Remember how to remat the def of this val#.
1169       ReMatOrigDefs[VN] = ReMatDefMI;
1170       // Original def may be modified so we have to make a copy here. vrm must
1171       // delete these!
1172       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1173       vrm.setVirtIsReMaterialized(li.reg, ReMatDefMI);
1174
1175       bool CanDelete = true;
1176       if (VNI->hasPHIKill) {
1177         // A kill is a phi node, not all of its uses can be rematerialized.
1178         // It must not be deleted.
1179         CanDelete = false;
1180         // Need a stack slot if there is any live range where uses cannot be
1181         // rematerialized.
1182         NeedStackSlot = true;
1183       }
1184       if (CanDelete)
1185         ReMatDelete.set(VN);
1186     } else {
1187       // Need a stack slot if there is any live range where uses cannot be
1188       // rematerialized.
1189       NeedStackSlot = true;
1190     }
1191   }
1192
1193   // One stack slot per live interval.
1194   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1195     Slot = vrm.assignVirt2StackSlot(li.reg);
1196
1197   // Create new intervals and rewrite defs and uses.
1198   for (LiveInterval::Ranges::const_iterator
1199          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1200     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1201     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1202     bool DefIsReMat = ReMatDefMI != NULL;
1203     bool CanDelete = ReMatDelete[I->valno->id];
1204     int LdSlot = 0;
1205     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1206     bool isLoad = isLoadSS ||
1207       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1208     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1209                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1210                                CanDelete, vrm, RegMap, rc, ReMatIds, loopInfo,
1211                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1212                                MBBVRegsMap, NewLIs);
1213   }
1214
1215   // Insert spills / restores if we are splitting.
1216   if (!TrySplit)
1217     return NewLIs;
1218
1219   SmallVector<unsigned, 2> UseOps;
1220   if (NeedStackSlot) {
1221     int Id = SpillMBBs.find_first();
1222     while (Id != -1) {
1223       std::vector<SRInfo> &spills = SpillIdxes[Id];
1224       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1225         int index = spills[i].index;
1226         unsigned VReg = spills[i].vreg;
1227         bool isReMat = vrm.isReMaterialized(VReg);
1228         MachineInstr *MI = getInstructionFromIndex(index);
1229         int OpIdx = -1;
1230         UseOps.clear();
1231         if (spills[i].canFold) {
1232           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1233             MachineOperand &MO = MI->getOperand(j);
1234             if (!MO.isRegister() || MO.getReg() != VReg)
1235               continue;
1236             if (MO.isDef()) {
1237               OpIdx = (int)j;
1238               continue;
1239             }
1240             // Can't fold if it's two-address code and the use isn't the
1241             // first and only use.
1242             if (isReMat ||
1243                 (UseOps.empty() && !alsoFoldARestore(Id, index, VReg,
1244                                                   RestoreMBBs, RestoreIdxes))) {
1245               OpIdx = -1;
1246               break;
1247             }
1248             UseOps.push_back(j);
1249           }
1250         }
1251         // Fold the store into the def if possible.
1252         bool Folded = false;
1253         if (OpIdx != -1) {
1254           if (tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx, UseOps,
1255                                    true, Slot, VReg)) {
1256             if (!UseOps.empty())
1257               // Folded a two-address instruction, do not issue a load.
1258               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1259             Folded = true;
1260           }
1261         }
1262
1263         // Else tell the spiller to issue a store for us.
1264         if (!Folded)
1265           vrm.addSpillPoint(VReg, MI);
1266       }
1267       Id = SpillMBBs.find_next(Id);
1268     }
1269   }
1270
1271   int Id = RestoreMBBs.find_first();
1272   while (Id != -1) {
1273     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1274     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1275       int index = restores[i].index;
1276       if (index == -1)
1277         continue;
1278       unsigned VReg = restores[i].vreg;
1279       MachineInstr *MI = getInstructionFromIndex(index);
1280       int OpIdx = -1;
1281       UseOps.clear();
1282       if (restores[i].canFold) {
1283         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1284           MachineOperand &MO = MI->getOperand(j);
1285           if (!MO.isRegister() || MO.getReg() != VReg)
1286             continue;
1287           if (MO.isDef()) {
1288             // Can't fold if it's two-address code and it hasn't already
1289             // been folded.
1290             OpIdx = -1;
1291             break;
1292           }
1293           if (UseOps.empty())
1294             // Use the first use index.
1295             OpIdx = (int)j;
1296           UseOps.push_back(j);
1297         }
1298       }
1299
1300       // Fold the load into the use if possible.
1301       bool Folded = false;
1302       if (OpIdx != -1) {
1303         if (vrm.isReMaterialized(VReg)) {
1304           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1305           int LdSlot = 0;
1306           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1307           // If the rematerializable def is a load, also try to fold it.
1308           if (isLoadSS ||
1309               (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG))
1310             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, OpIdx,
1311                                           UseOps, isLoadSS, LdSlot, VReg);
1312         } else
1313           Folded = tryFoldMemoryOperand(MI, vrm, NULL, index, OpIdx, UseOps,
1314                                         true, Slot, VReg);
1315       }
1316       // If folding is not possible / failed, then tell the spiller to issue a
1317       // load / rematerialization for us.
1318       if (!Folded)
1319         vrm.addRestorePoint(VReg, MI);
1320     }
1321     Id = RestoreMBBs.find_next(Id);
1322   }
1323
1324   // Finalize spill weights.
1325   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1326     NewLIs[i]->weight /= NewLIs[i]->getSize();
1327
1328   return NewLIs;
1329 }