lib/CodeGen/LiveIntervalAnalysis.cpp

   1 //===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LiveInterval analysis pass which is used
  11 // by the Linear Scan Register allocator. This pass linearizes the
  12 // basic blocks of the function in DFS order and uses the
  13 // LiveVariables pass to conservatively compute live intervals for
  14 // each virtual and physical register.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "liveintervals"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "VirtRegMap.h"
  21 #include "llvm/Value.h"
  22 #include "llvm/CodeGen/LiveVariables.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineInstr.h"
  25 #include "llvm/CodeGen/MachineLoopInfo.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(true), 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                                        bool &isLoad) {
 612   if (DisableReMat)
 613     return false;
 614
 615   isLoad = false;
 616   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 617   if ((TID->Flags & M_IMPLICIT_DEF_FLAG) ||
 618       tii_->isTriviallyReMaterializable(MI)) {
 619     isLoad = TID->Flags & M_LOAD_FLAG;
 620     return true;
 621   }
 622
 623   int FrameIdx = 0;
 624   if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
 625       !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
 626     return false;
 627
 628   // This is a load from fixed stack slot. It can be rematerialized unless it's
 629   // re-defined by a two-address instruction.
 630   isLoad = true;
 631   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 632        i != e; ++i) {
 633     const VNInfo *VNI = *i;
 634     if (VNI == ValNo)
 635       continue;
 636     unsigned DefIdx = VNI->def;
 637     if (DefIdx == ~1U)
 638       continue; // Dead val#.
 639     MachineInstr *DefMI = (DefIdx == ~0u)
 640       ? NULL : getInstructionFromIndex(DefIdx);
 641     if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) {
 642       isLoad = false;
 643       return false;
 644     }
 645   }
 646   return true;
 647 }
 648
 649 /// isReMaterializable - Returns true if every definition of MI of every
 650 /// val# of the specified interval is re-materializable.
 651 bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
 652   isLoad = false;
 653   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
 654        i != e; ++i) {
 655     const VNInfo *VNI = *i;
 656     unsigned DefIdx = VNI->def;
 657     if (DefIdx == ~1U)
 658       continue; // Dead val#.
 659     // Is the def for the val# rematerializable?
 660     if (DefIdx == ~0u)
 661       return false;
 662     MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
 663     bool DefIsLoad = false;
 664     if (!ReMatDefMI || !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
 665       return false;
 666     isLoad |= DefIsLoad;
 667   }
 668   return true;
 669 }
 670
 671 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
 672 /// slot / to reg or any rematerialized load into ith operand of specified
 673 /// MI. If it is successul, MI is updated with the newly created MI and
 674 /// returns true.
 675 bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
 676                                          VirtRegMap &vrm, MachineInstr *DefMI,
 677                                          unsigned InstrIdx,
 678                                          SmallVector<unsigned, 2> &Ops,
 679                                          bool isSS, int Slot, unsigned Reg) {
 680   unsigned MRInfo = 0;
 681   const TargetInstrDescriptor *TID = MI->getInstrDescriptor();
 682   // If it is an implicit def instruction, just delete it.
 683   if (TID->Flags & M_IMPLICIT_DEF_FLAG) {
 684     RemoveMachineInstrFromMaps(MI);
 685     vrm.RemoveMachineInstrFromMaps(MI);
 686     MI->eraseFromParent();
 687     ++numFolds;
 688     return true;
 689   }
 690
 691   SmallVector<unsigned, 2> FoldOps;
 692   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 693     unsigned OpIdx = Ops[i];
 694     // FIXME: fold subreg use.
 695     if (MI->getOperand(OpIdx).getSubReg())
 696       return false;
 697     if (MI->getOperand(OpIdx).isDef())
 698       MRInfo |= (unsigned)VirtRegMap::isMod;
 699     else {
 700       // Filter out two-address use operand(s).
 701       if (TID->getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
 702         MRInfo = VirtRegMap::isModRef;
 703         continue;
 704       }
 705       MRInfo |= (unsigned)VirtRegMap::isRef;
 706     }
 707     FoldOps.push_back(OpIdx);
 708   }
 709
 710   MachineInstr *fmi = isSS ? mri_->foldMemoryOperand(MI, FoldOps, Slot)
 711                            : mri_->foldMemoryOperand(MI, FoldOps, DefMI);
 712   if (fmi) {
 713     // Attempt to fold the memory reference into the instruction. If
 714     // we can do this, we don't need to insert spill code.
 715     if (lv_)
 716       lv_->instructionChanged(MI, fmi);
 717     else
 718       LiveVariables::transferKillDeadInfo(MI, fmi, mri_);
 719     MachineBasicBlock &MBB = *MI->getParent();
 720     if (isSS && !mf_->getFrameInfo()->isFixedObjectIndex(Slot))
 721       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
 722     vrm.transferSpillPts(MI, fmi);
 723     vrm.transferRestorePts(MI, fmi);
 724     mi2iMap_.erase(MI);
 725     i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
 726     mi2iMap_[fmi] = InstrIdx;
 727     MI = MBB.insert(MBB.erase(MI), fmi);
 728     ++numFolds;
 729     return true;
 730   }
 731   return false;
 732 }
 733
 734 /// canFoldMemoryOperand - Returns true if the specified load / store
 735 /// folding is possible.
 736 bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
 737                                          SmallVector<unsigned, 2> &Ops) const {
 738   SmallVector<unsigned, 2> FoldOps;
 739   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 740     unsigned OpIdx = Ops[i];
 741     // FIXME: fold subreg use.
 742     if (MI->getOperand(OpIdx).getSubReg())
 743       return false;
 744     FoldOps.push_back(OpIdx);
 745   }
 746
 747   return mri_->canFoldMemoryOperand(MI, FoldOps);
 748 }
 749
 750 bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
 751   SmallPtrSet<MachineBasicBlock*, 4> MBBs;
 752   for (LiveInterval::Ranges::const_iterator
 753          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
 754     std::vector<IdxMBBPair>::const_iterator II =
 755       std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
 756     if (II == Idx2MBBMap.end())
 757       continue;
 758     if (I->end > II->first)  // crossing a MBB.
 759       return false;
 760     MBBs.insert(II->second);
 761     if (MBBs.size() > 1)
 762       return false;
 763   }
 764   return true;
 765 }
 766
 767 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
 768 /// for addIntervalsForSpills to rewrite uses / defs for the given live range.
 769 bool LiveIntervals::
 770 rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
 771                  unsigned id, unsigned index, unsigned end,  MachineInstr *MI,
 772                  MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 773                  unsigned Slot, int LdSlot,
 774                  bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 775                  VirtRegMap &vrm, SSARegMap *RegMap,
 776                  const TargetRegisterClass* rc,
 777                  SmallVector<int, 4> &ReMatIds,
 778                  unsigned &NewVReg, bool &HasDef, bool &HasUse,
 779                  const MachineLoopInfo *loopInfo,
 780                  std::map<unsigned,unsigned> &MBBVRegsMap,
 781                  std::vector<LiveInterval*> &NewLIs) {
 782   bool CanFold = false;
 783  RestartInstruction:
 784   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 785     MachineOperand& mop = MI->getOperand(i);
 786     if (!mop.isRegister())
 787       continue;
 788     unsigned Reg = mop.getReg();
 789     unsigned RegI = Reg;
 790     if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
 791       continue;
 792     if (Reg != li.reg)
 793       continue;
 794
 795     bool TryFold = !DefIsReMat;
 796     bool FoldSS = true; // Default behavior unless it's a remat.
 797     int FoldSlot = Slot;
 798     if (DefIsReMat) {
 799       // If this is the rematerializable definition MI itself and
 800       // all of its uses are rematerialized, simply delete it.
 801       if (MI == ReMatOrigDefMI && CanDelete) {
 802         DOUT << "\t\t\t\tErasing re-materlizable def: ";
 803         DOUT << MI << '\n';
 804         RemoveMachineInstrFromMaps(MI);
 805         vrm.RemoveMachineInstrFromMaps(MI);
 806         MI->eraseFromParent();
 807         break;
 808       }
 809
 810       // If def for this use can't be rematerialized, then try folding.
 811       // If def is rematerializable and it's a load, also try folding.
 812       TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
 813       if (isLoad) {
 814         // Try fold loads (from stack slot, constant pool, etc.) into uses.
 815         FoldSS = isLoadSS;
 816         FoldSlot = LdSlot;
 817       }
 818     }
 819
 820     // Scan all of the operands of this instruction rewriting operands
 821     // to use NewVReg instead of li.reg as appropriate.  We do this for
 822     // two reasons:
 823     //
 824     //   1. If the instr reads the same spilled vreg multiple times, we
 825     //      want to reuse the NewVReg.
 826     //   2. If the instr is a two-addr instruction, we are required to
 827     //      keep the src/dst regs pinned.
 828     //
 829     // Keep track of whether we replace a use and/or def so that we can
 830     // create the spill interval with the appropriate range.
 831
 832     HasUse = mop.isUse();
 833     HasDef = mop.isDef();
 834     SmallVector<unsigned, 2> Ops;
 835     Ops.push_back(i);
 836     for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
 837       const MachineOperand &MOj = MI->getOperand(j);
 838       if (!MOj.isRegister())
 839         continue;
 840       unsigned RegJ = MOj.getReg();
 841       if (RegJ == 0 || MRegisterInfo::isPhysicalRegister(RegJ))
 842         continue;
 843       if (RegJ == RegI) {
 844         Ops.push_back(j);
 845         HasUse |= MOj.isUse();
 846         HasDef |= MOj.isDef();
 847       }
 848     }
 849
 850     if (TryFold) {
 851       // Do not fold load / store here if we are splitting. We'll find an
 852       // optimal point to insert a load / store later.
 853       if (!TrySplit) {
 854         if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
 855                                  Ops, FoldSS, FoldSlot, Reg)) {
 856           // Folding the load/store can completely change the instruction in
 857           // unpredictable ways, rescan it from the beginning.
 858           HasUse = false;
 859           HasDef = false;
 860           CanFold = false;
 861           goto RestartInstruction;
 862         }
 863       } else {
 864         CanFold = canFoldMemoryOperand(MI, Ops);
 865       }
 866     } else
 867       CanFold = false;
 868
 869     // Create a new virtual register for the spill interval.
 870     bool CreatedNewVReg = false;
 871     if (NewVReg == 0) {
 872       NewVReg = RegMap->createVirtualRegister(rc);
 873       vrm.grow();
 874       CreatedNewVReg = true;
 875     }
 876     mop.setReg(NewVReg);
 877
 878     // Reuse NewVReg for other reads.
 879     for (unsigned j = 0, e = Ops.size(); j != e; ++j)
 880       MI->getOperand(Ops[j]).setReg(NewVReg);
 881
 882     if (CreatedNewVReg) {
 883       if (DefIsReMat) {
 884         vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
 885         if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) {
 886           // Each valnum may have its own remat id.
 887           ReMatIds[id] = vrm.assignVirtReMatId(NewVReg);
 888         } else {
 889           vrm.assignVirtReMatId(NewVReg, ReMatIds[id]);
 890         }
 891         if (!CanDelete || (HasUse && HasDef)) {
 892           // If this is a two-addr instruction then its use operands are
 893           // rematerializable but its def is not. It should be assigned a
 894           // stack slot.
 895           vrm.assignVirt2StackSlot(NewVReg, Slot);
 896         }
 897       } else {
 898         vrm.assignVirt2StackSlot(NewVReg, Slot);
 899       }
 900     } else if (HasUse && HasDef &&
 901                vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
 902       // If this interval hasn't been assigned a stack slot (because earlier
 903       // def is a deleted remat def), do it now.
 904       assert(Slot != VirtRegMap::NO_STACK_SLOT);
 905       vrm.assignVirt2StackSlot(NewVReg, Slot);
 906     }
 907
 908     // create a new register interval for this spill / remat.
 909     LiveInterval &nI = getOrCreateInterval(NewVReg);
 910     if (CreatedNewVReg) {
 911       NewLIs.push_back(&nI);
 912       MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
 913       if (TrySplit)
 914         vrm.setIsSplitFromReg(NewVReg, li.reg);
 915     }
 916
 917     if (HasUse) {
 918       if (CreatedNewVReg) {
 919         LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
 920                      nI.getNextValue(~0U, 0, VNInfoAllocator));
 921         DOUT << " +" << LR;
 922         nI.addRange(LR);
 923       } else {
 924         // Extend the split live interval to this def / use.
 925         unsigned End = getUseIndex(index)+1;
 926         LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
 927                      nI.getValNumInfo(nI.getNumValNums()-1));
 928         DOUT << " +" << LR;
 929         nI.addRange(LR);
 930       }
 931     }
 932     if (HasDef) {
 933       LiveRange LR(getDefIndex(index), getStoreIndex(index),
 934                    nI.getNextValue(~0U, 0, VNInfoAllocator));
 935       DOUT << " +" << LR;
 936       nI.addRange(LR);
 937     }
 938
 939     DOUT << "\t\t\t\tAdded new interval: ";
 940     nI.print(DOUT, mri_);
 941     DOUT << '\n';
 942   }
 943   return CanFold;
 944 }
 945 bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
 946                                    const VNInfo *VNI,
 947                                    MachineBasicBlock *MBB, unsigned Idx) const {
 948   unsigned End = getMBBEndIdx(MBB);
 949   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
 950     unsigned KillIdx = VNI->kills[j];
 951     if (KillIdx > Idx && KillIdx < End)
 952       return true;
 953   }
 954   return false;
 955 }
 956
 957 static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
 958   const VNInfo *VNI = NULL;
 959   for (LiveInterval::const_vni_iterator i = li.vni_begin(),
 960          e = li.vni_end(); i != e; ++i)
 961     if ((*i)->def == DefIdx) {
 962       VNI = *i;
 963       break;
 964     }
 965   return VNI;
 966 }
 967
 968 void LiveIntervals::
 969 rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
 970                     LiveInterval::Ranges::const_iterator &I,
 971                     MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
 972                     unsigned Slot, int LdSlot,
 973                     bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
 974                     VirtRegMap &vrm, SSARegMap *RegMap,
 975                     const TargetRegisterClass* rc,
 976                     SmallVector<int, 4> &ReMatIds,
 977                     const MachineLoopInfo *loopInfo,
 978                     BitVector &SpillMBBs,
 979                     std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
 980                     BitVector &RestoreMBBs,
 981                     std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
 982                     std::map<unsigned,unsigned> &MBBVRegsMap,
 983                     std::vector<LiveInterval*> &NewLIs) {
 984   bool AllCanFold = true;
 985   unsigned NewVReg = 0;
 986   unsigned index = getBaseIndex(I->start);
 987   unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
 988   for (; index != end; index += InstrSlots::NUM) {
 989     // skip deleted instructions
 990     while (index != end && !getInstructionFromIndex(index))
 991       index += InstrSlots::NUM;
 992     if (index == end) break;
 993
 994     MachineInstr *MI = getInstructionFromIndex(index);
 995     MachineBasicBlock *MBB = MI->getParent();
 996     unsigned ThisVReg = 0;
 997     if (TrySplit) {
 998       std::map<unsigned,unsigned>::const_iterator NVI =
 999         MBBVRegsMap.find(MBB->getNumber());
1000       if (NVI != MBBVRegsMap.end()) {
1001         ThisVReg = NVI->second;
1002         // One common case:
1003         // x = use
1004         // ...
1005         // ...
1006         // def = ...
1007         //     = use
1008         // It's better to start a new interval to avoid artifically
1009         // extend the new interval.
1010         // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills?
1011         bool MIHasUse = false;
1012         bool MIHasDef = false;
1013         for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1014           MachineOperand& mop = MI->getOperand(i);
1015           if (!mop.isRegister() || mop.getReg() != li.reg)
1016             continue;
1017           if (mop.isUse())
1018             MIHasUse = true;
1019           else
1020             MIHasDef = true;
1021         }
1022         if (MIHasDef && !MIHasUse) {
1023           MBBVRegsMap.erase(MBB->getNumber());
1024           ThisVReg = 0;
1025         }
1026       }
1027     }
1028
1029     bool IsNew = ThisVReg == 0;
1030     if (IsNew) {
1031       // This ends the previous live interval. If all of its def / use
1032       // can be folded, give it a low spill weight.
1033       if (NewVReg && TrySplit && AllCanFold) {
1034         LiveInterval &nI = getOrCreateInterval(NewVReg);
1035         nI.weight /= 10.0F;
1036       }
1037       AllCanFold = true;
1038     }
1039     NewVReg = ThisVReg;
1040
1041     bool HasDef = false;
1042     bool HasUse = false;
1043     bool CanFold = rewriteInstructionForSpills(li, TrySplit, I->valno->id,
1044                                 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1045                                 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1046                                 CanDelete, vrm, RegMap, rc, ReMatIds, NewVReg,
1047                                 HasDef, HasUse, loopInfo, MBBVRegsMap, NewLIs);
1048     if (!HasDef && !HasUse)
1049       continue;
1050
1051     AllCanFold &= CanFold;
1052
1053     // Update weight of spill interval.
1054     LiveInterval &nI = getOrCreateInterval(NewVReg);
1055     if (!TrySplit) {
1056       // The spill weight is now infinity as it cannot be spilled again.
1057       nI.weight = HUGE_VALF;
1058       continue;
1059     }
1060
1061     // Keep track of the last def and first use in each MBB.
1062     unsigned MBBId = MBB->getNumber();
1063     if (HasDef) {
1064       if (MI != ReMatOrigDefMI || !CanDelete) {
1065         bool HasKill = false;
1066         if (!HasUse)
1067           HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1068         else {
1069           // If this is a two-address code, then this index starts a new VNInfo.
1070           const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
1071           if (VNI)
1072             HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1073         }
1074         std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1075           SpillIdxes.find(MBBId);
1076         if (!HasKill) {
1077           if (SII == SpillIdxes.end()) {
1078             std::vector<SRInfo> S;
1079             S.push_back(SRInfo(index, NewVReg, true));
1080             SpillIdxes.insert(std::make_pair(MBBId, S));
1081           } else if (SII->second.back().vreg != NewVReg) {
1082             SII->second.push_back(SRInfo(index, NewVReg, true));
1083           } else if ((int)index > SII->second.back().index) {
1084             // If there is an earlier def and this is a two-address
1085             // instruction, then it's not possible to fold the store (which
1086             // would also fold the load).
1087             SRInfo &Info = SII->second.back();
1088             Info.index = index;
1089             Info.canFold = !HasUse;
1090           }
1091           SpillMBBs.set(MBBId);
1092         } else if (SII != SpillIdxes.end() &&
1093                    SII->second.back().vreg == NewVReg &&
1094                    (int)index > SII->second.back().index) {
1095           // There is an earlier def that's not killed (must be two-address).
1096           // The spill is no longer needed.
1097           SII->second.pop_back();
1098           if (SII->second.empty()) {
1099             SpillIdxes.erase(MBBId);
1100             SpillMBBs.reset(MBBId);
1101           }
1102         }
1103       }
1104     }
1105
1106     if (HasUse) {
1107       std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1108         SpillIdxes.find(MBBId);
1109       if (SII != SpillIdxes.end() &&
1110           SII->second.back().vreg == NewVReg &&
1111           (int)index > SII->second.back().index)
1112         // Use(s) following the last def, it's not safe to fold the spill.
1113         SII->second.back().canFold = false;
1114       std::map<unsigned, std::vector<SRInfo> >::iterator RII =
1115         RestoreIdxes.find(MBBId);
1116       if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
1117         // If we are splitting live intervals, only fold if it's the first
1118         // use and there isn't another use later in the MBB.
1119         RII->second.back().canFold = false;
1120       else if (IsNew) {
1121         // Only need a reload if there isn't an earlier def / use.
1122         if (RII == RestoreIdxes.end()) {
1123           std::vector<SRInfo> Infos;
1124           Infos.push_back(SRInfo(index, NewVReg, true));
1125           RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1126         } else {
1127           RII->second.push_back(SRInfo(index, NewVReg, true));
1128         }
1129         RestoreMBBs.set(MBBId);
1130       }
1131     }
1132
1133     // Update spill weight.
1134     unsigned loopDepth = loopInfo->getLoopDepth(MBB);
1135     nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
1136   }
1137
1138   if (NewVReg && TrySplit && AllCanFold) {
1139     // If all of its def / use can be folded, give it a low spill weight.
1140     LiveInterval &nI = getOrCreateInterval(NewVReg);
1141     nI.weight /= 10.0F;
1142   }
1143 }
1144
1145 bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1146                         BitVector &RestoreMBBs,
1147                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1148   if (!RestoreMBBs[Id])
1149     return false;
1150   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1151   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1152     if (Restores[i].index == index &&
1153         Restores[i].vreg == vr &&
1154         Restores[i].canFold)
1155       return true;
1156   return false;
1157 }
1158
1159 void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1160                         BitVector &RestoreMBBs,
1161                         std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1162   if (!RestoreMBBs[Id])
1163     return;
1164   std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1165   for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1166     if (Restores[i].index == index && Restores[i].vreg)
1167       Restores[i].index = -1;
1168 }
1169
1170
1171 std::vector<LiveInterval*> LiveIntervals::
1172 addIntervalsForSpills(const LiveInterval &li,
1173                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
1174   // Since this is called after the analysis is done we don't know if
1175   // LiveVariables is available
1176   lv_ = getAnalysisToUpdate<LiveVariables>();
1177
1178   assert(li.weight != HUGE_VALF &&
1179          "attempt to spill already spilled interval!");
1180
1181   DOUT << "\t\t\t\tadding intervals for spills for interval: ";
1182   li.print(DOUT, mri_);
1183   DOUT << '\n';
1184
1185   // Each bit specify whether it a spill is required in the MBB.
1186   BitVector SpillMBBs(mf_->getNumBlockIDs());
1187   std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
1188   BitVector RestoreMBBs(mf_->getNumBlockIDs());
1189   std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1190   std::map<unsigned,unsigned> MBBVRegsMap;
1191   std::vector<LiveInterval*> NewLIs;
1192   SSARegMap *RegMap = mf_->getSSARegMap();
1193   const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
1194
1195   unsigned NumValNums = li.getNumValNums();
1196   SmallVector<MachineInstr*, 4> ReMatDefs;
1197   ReMatDefs.resize(NumValNums, NULL);
1198   SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1199   ReMatOrigDefs.resize(NumValNums, NULL);
1200   SmallVector<int, 4> ReMatIds;
1201   ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1202   BitVector ReMatDelete(NumValNums);
1203   unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1204
1205   // Spilling a split live interval. It cannot be split any further. Also,
1206   // it's also guaranteed to be a single val# / range interval.
1207   if (vrm.getPreSplitReg(li.reg)) {
1208     vrm.setIsSplitFromReg(li.reg, 0);
1209     // Unset the split kill marker on the last use.
1210     unsigned KillIdx = vrm.getKillPoint(li.reg);
1211     if (KillIdx) {
1212       MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1213       assert(KillMI && "Last use disappeared?");
1214       int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1215       assert(KillOp != -1 && "Last use disappeared?");
1216       KillMI->getOperand(KillOp).unsetIsKill();
1217     }
1218     vrm.removeKillPoint(li.reg);
1219     bool DefIsReMat = vrm.isReMaterialized(li.reg);
1220     Slot = vrm.getStackSlot(li.reg);
1221     assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1222     MachineInstr *ReMatDefMI = DefIsReMat ?
1223       vrm.getReMaterializedMI(li.reg) : NULL;
1224     int LdSlot = 0;
1225     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1226     bool isLoad = isLoadSS ||
1227       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1228     bool IsFirstRange = true;
1229     for (LiveInterval::Ranges::const_iterator
1230            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1231       // If this is a split live interval with multiple ranges, it means there
1232       // are two-address instructions that re-defined the value. Only the
1233       // first def can be rematerialized!
1234       if (IsFirstRange) {
1235         // Note ReMatOrigDefMI has already been deleted.
1236         rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1237                              Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1238                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1239                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1240                              MBBVRegsMap, NewLIs);
1241       } else {
1242         rewriteInstructionsForSpills(li, false, I, NULL, 0,
1243                              Slot, 0, false, false, false,
1244                              false, vrm, RegMap, rc, ReMatIds, loopInfo,
1245                              SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1246                              MBBVRegsMap, NewLIs);
1247       }
1248       IsFirstRange = false;
1249     }
1250     return NewLIs;
1251   }
1252
1253   bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
1254   if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1255     TrySplit = false;
1256   if (TrySplit)
1257     ++numSplits;
1258   bool NeedStackSlot = false;
1259   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1260        i != e; ++i) {
1261     const VNInfo *VNI = *i;
1262     unsigned VN = VNI->id;
1263     unsigned DefIdx = VNI->def;
1264     if (DefIdx == ~1U)
1265       continue; // Dead val#.
1266     // Is the def for the val# rematerializable?
1267     MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1268       ? 0 : getInstructionFromIndex(DefIdx);
1269     bool dummy;
1270     if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
1271       // Remember how to remat the def of this val#.
1272       ReMatOrigDefs[VN] = ReMatDefMI;
1273       // Original def may be modified so we have to make a copy here. vrm must
1274       // delete these!
1275       ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
1276
1277       bool CanDelete = true;
1278       if (VNI->hasPHIKill) {
1279         // A kill is a phi node, not all of its uses can be rematerialized.
1280         // It must not be deleted.
1281         CanDelete = false;
1282         // Need a stack slot if there is any live range where uses cannot be
1283         // rematerialized.
1284         NeedStackSlot = true;
1285       }
1286       if (CanDelete)
1287         ReMatDelete.set(VN);
1288     } else {
1289       // Need a stack slot if there is any live range where uses cannot be
1290       // rematerialized.
1291       NeedStackSlot = true;
1292     }
1293   }
1294
1295   // One stack slot per live interval.
1296   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
1297     Slot = vrm.assignVirt2StackSlot(li.reg);
1298
1299   // Create new intervals and rewrite defs and uses.
1300   for (LiveInterval::Ranges::const_iterator
1301          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1302     MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1303     MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1304     bool DefIsReMat = ReMatDefMI != NULL;
1305     bool CanDelete = ReMatDelete[I->valno->id];
1306     int LdSlot = 0;
1307     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1308     bool isLoad = isLoadSS ||
1309       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
1310     rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
1311                                Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1312                                CanDelete, vrm, RegMap, rc, ReMatIds, loopInfo,
1313                                SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
1314                                MBBVRegsMap, NewLIs);
1315   }
1316
1317   // Insert spills / restores if we are splitting.
1318   if (!TrySplit)
1319     return NewLIs;
1320
1321   SmallPtrSet<LiveInterval*, 4> AddedKill;
1322   SmallVector<unsigned, 2> Ops;
1323   if (NeedStackSlot) {
1324     int Id = SpillMBBs.find_first();
1325     while (Id != -1) {
1326       std::vector<SRInfo> &spills = SpillIdxes[Id];
1327       for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1328         int index = spills[i].index;
1329         unsigned VReg = spills[i].vreg;
1330         LiveInterval &nI = getOrCreateInterval(VReg);
1331         bool isReMat = vrm.isReMaterialized(VReg);
1332         MachineInstr *MI = getInstructionFromIndex(index);
1333         bool CanFold = false;
1334         bool FoundUse = false;
1335         Ops.clear();
1336         if (spills[i].canFold) {
1337           CanFold = true;
1338           for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1339             MachineOperand &MO = MI->getOperand(j);
1340             if (!MO.isRegister() || MO.getReg() != VReg)
1341               continue;
1342
1343             Ops.push_back(j);
1344             if (MO.isDef())
1345               continue;
1346             if (isReMat ||
1347                 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1348                                                 RestoreMBBs, RestoreIdxes))) {
1349               // MI has two-address uses of the same register. If the use
1350               // isn't the first and only use in the BB, then we can't fold
1351               // it. FIXME: Move this to rewriteInstructionsForSpills.
1352               CanFold = false;
1353               break;
1354             }
1355             FoundUse = true;
1356           }
1357         }
1358         // Fold the store into the def if possible.
1359         bool Folded = false;
1360         if (CanFold && !Ops.empty()) {
1361           if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
1362             Folded = true;
1363             if (FoundUse > 0) {
1364               // Also folded uses, do not issue a load.
1365               eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
1366               nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1367             }
1368             nI.removeRange(getDefIndex(index), getStoreIndex(index));
1369           }
1370         }
1371
1372         // Else tell the spiller to issue a spill.
1373         if (!Folded) {
1374           LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1375           bool isKill = LR->end == getStoreIndex(index);
1376           vrm.addSpillPoint(VReg, isKill, MI);
1377           if (isKill)
1378             AddedKill.insert(&nI);
1379         }
1380       }
1381       Id = SpillMBBs.find_next(Id);
1382     }
1383   }
1384
1385   int Id = RestoreMBBs.find_first();
1386   while (Id != -1) {
1387     std::vector<SRInfo> &restores = RestoreIdxes[Id];
1388     for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1389       int index = restores[i].index;
1390       if (index == -1)
1391         continue;
1392       unsigned VReg = restores[i].vreg;
1393       LiveInterval &nI = getOrCreateInterval(VReg);
1394       MachineInstr *MI = getInstructionFromIndex(index);
1395       bool CanFold = false;
1396       Ops.clear();
1397       if (restores[i].canFold) {
1398         CanFold = true;
1399         for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1400           MachineOperand &MO = MI->getOperand(j);
1401           if (!MO.isRegister() || MO.getReg() != VReg)
1402             continue;
1403
1404           if (MO.isDef()) {
1405             // If this restore were to be folded, it would have been folded
1406             // already.
1407             CanFold = false;
1408             break;
1409           }
1410           Ops.push_back(j);
1411         }
1412       }
1413
1414       // Fold the load into the use if possible.
1415       bool Folded = false;
1416       if (CanFold && !Ops.empty()) {
1417         if (!vrm.isReMaterialized(VReg))
1418           Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1419         else {
1420           MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1421           int LdSlot = 0;
1422           bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1423           // If the rematerializable def is a load, also try to fold it.
1424           if (isLoadSS ||
1425               (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG))
1426             Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1427                                           Ops, isLoadSS, LdSlot, VReg);
1428         }
1429       }
1430       // If folding is not possible / failed, then tell the spiller to issue a
1431       // load / rematerialization for us.
1432       if (Folded)
1433         nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1434       else
1435         vrm.addRestorePoint(VReg, MI);
1436     }
1437     Id = RestoreMBBs.find_next(Id);
1438   }
1439
1440   // Finalize intervals: add kills, finalize spill weights, and filter out
1441   // dead intervals.
1442   std::vector<LiveInterval*> RetNewLIs;
1443   for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1444     LiveInterval *LI = NewLIs[i];
1445     if (!LI->empty()) {
1446       LI->weight /= LI->getSize();
1447       if (!AddedKill.count(LI)) {
1448         LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
1449         unsigned LastUseIdx = getBaseIndex(LR->end);
1450         MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
1451         int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg);
1452         assert(UseIdx != -1);
1453         if (LastUse->getInstrDescriptor()->
1454             getOperandConstraint(UseIdx, TOI::TIED_TO) == -1) {
1455           LastUse->getOperand(UseIdx).setIsKill();
1456           vrm.addKillPoint(LI->reg, LastUseIdx);
1457         }
1458       }
1459       RetNewLIs.push_back(LI);
1460     }
1461   }
1462
1463   return RetNewLIs;
1464 }