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