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 "regalloc"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/Value.h"
  21 #include "llvm/Analysis/AliasAnalysis.h"
  22 #include "llvm/CodeGen/LiveVariables.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineLoopInfo.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include <algorithm>
  37 #include <limits>
  38 #include <cmath>
  39 using namespace llvm;
  40
  41 // Hidden options for help debugging.
  42 static cl::opt<bool> DisableReMat("disable-rematerialization",
  43                                   cl::init(false), cl::Hidden);
  44
  45 STATISTIC(numIntervals , "Number of original intervals");
  46
  47 char LiveIntervals::ID = 0;
  48 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
  49                 "Live Interval Analysis", false, false)
  50 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  51 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
  52 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  53 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  54 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
  55 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
  56                 "Live Interval Analysis", false, false)
  57
  58 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  59   AU.setPreservesCFG();
  60   AU.addRequired<AliasAnalysis>();
  61   AU.addPreserved<AliasAnalysis>();
  62   AU.addRequired<LiveVariables>();
  63   AU.addPreserved<LiveVariables>();
  64   AU.addRequired<MachineLoopInfo>();
  65   AU.addPreserved<MachineLoopInfo>();
  66   AU.addPreservedID(MachineDominatorsID);
  67   AU.addPreserved<SlotIndexes>();
  68   AU.addRequiredTransitive<SlotIndexes>();
  69   MachineFunctionPass::getAnalysisUsage(AU);
  70 }
  71
  72 void LiveIntervals::releaseMemory() {
  73   // Free the live intervals themselves.
  74   for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
  75        E = r2iMap_.end(); I != E; ++I)
  76     delete I->second;
  77
  78   r2iMap_.clear();
  79   RegMaskSlots.clear();
  80   RegMaskBits.clear();
  81   RegMaskBlocks.clear();
  82
  83   // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
  84   VNInfoAllocator.Reset();
  85 }
  86
  87 /// runOnMachineFunction - Register allocate the whole function
  88 ///
  89 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  90   mf_ = &fn;
  91   mri_ = &mf_->getRegInfo();
  92   tm_ = &fn.getTarget();
  93   tri_ = tm_->getRegisterInfo();
  94   tii_ = tm_->getInstrInfo();
  95   aa_ = &getAnalysis<AliasAnalysis>();
  96   lv_ = &getAnalysis<LiveVariables>();
  97   indexes_ = &getAnalysis<SlotIndexes>();
  98   allocatableRegs_ = tri_->getAllocatableSet(fn);
  99
 100   computeIntervals();
 101
 102   numIntervals += getNumIntervals();
 103
 104   DEBUG(dump());
 105   return true;
 106 }
 107
 108 /// print - Implement the dump method.
 109 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
 110   OS << "********** INTERVALS **********\n";
 111   for (const_iterator I = begin(), E = end(); I != E; ++I) {
 112     I->second->print(OS, tri_);
 113     OS << "\n";
 114   }
 115
 116   printInstrs(OS);
 117 }
 118
 119 void LiveIntervals::printInstrs(raw_ostream &OS) const {
 120   OS << "********** MACHINEINSTRS **********\n";
 121   mf_->print(OS, indexes_);
 122 }
 123
 124 void LiveIntervals::dumpInstrs() const {
 125   printInstrs(dbgs());
 126 }
 127
 128 static
 129 bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
 130   unsigned Reg = MI.getOperand(MOIdx).getReg();
 131   for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
 132     const MachineOperand &MO = MI.getOperand(i);
 133     if (!MO.isReg())
 134       continue;
 135     if (MO.getReg() == Reg && MO.isDef()) {
 136       assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
 137              MI.getOperand(MOIdx).getSubReg() &&
 138              (MO.getSubReg() || MO.isImplicit()));
 139       return true;
 140     }
 141   }
 142   return false;
 143 }
 144
 145 /// isPartialRedef - Return true if the specified def at the specific index is
 146 /// partially re-defining the specified live interval. A common case of this is
 147 /// a definition of the sub-register.
 148 bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
 149                                    LiveInterval &interval) {
 150   if (!MO.getSubReg() || MO.isEarlyClobber())
 151     return false;
 152
 153   SlotIndex RedefIndex = MIIdx.getRegSlot();
 154   const LiveRange *OldLR =
 155     interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
 156   MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
 157   if (DefMI != 0) {
 158     return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
 159   }
 160   return false;
 161 }
 162
 163 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 164                                              MachineBasicBlock::iterator mi,
 165                                              SlotIndex MIIdx,
 166                                              MachineOperand& MO,
 167                                              unsigned MOIdx,
 168                                              LiveInterval &interval) {
 169   DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
 170
 171   // Virtual registers may be defined multiple times (due to phi
 172   // elimination and 2-addr elimination).  Much of what we do only has to be
 173   // done once for the vreg.  We use an empty interval to detect the first
 174   // time we see a vreg.
 175   LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
 176   if (interval.empty()) {
 177     // Get the Idx of the defining instructions.
 178     SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
 179
 180     // Make sure the first definition is not a partial redefinition. Add an
 181     // <imp-def> of the full register.
 182     // FIXME: LiveIntervals shouldn't modify the code like this.  Whoever
 183     // created the machine instruction should annotate it with <undef> flags
 184     // as needed.  Then we can simply assert here.  The REG_SEQUENCE lowering
 185     // is the main suspect.
 186     if (MO.getSubReg()) {
 187       mi->addRegisterDefined(interval.reg);
 188       // Mark all defs of interval.reg on this instruction as reading <undef>.
 189       for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) {
 190         MachineOperand &MO2 = mi->getOperand(i);
 191         if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg())
 192           MO2.setIsUndef();
 193       }
 194     }
 195
 196     VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
 197     assert(ValNo->id == 0 && "First value in interval is not 0?");
 198
 199     // Loop over all of the blocks that the vreg is defined in.  There are
 200     // two cases we have to handle here.  The most common case is a vreg
 201     // whose lifetime is contained within a basic block.  In this case there
 202     // will be a single kill, in MBB, which comes after the definition.
 203     if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
 204       // FIXME: what about dead vars?
 205       SlotIndex killIdx;
 206       if (vi.Kills[0] != mi)
 207         killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot();
 208       else
 209         killIdx = defIndex.getDeadSlot();
 210
 211       // If the kill happens after the definition, we have an intra-block
 212       // live range.
 213       if (killIdx > defIndex) {
 214         assert(vi.AliveBlocks.empty() &&
 215                "Shouldn't be alive across any blocks!");
 216         LiveRange LR(defIndex, killIdx, ValNo);
 217         interval.addRange(LR);
 218         DEBUG(dbgs() << " +" << LR << "\n");
 219         return;
 220       }
 221     }
 222
 223     // The other case we handle is when a virtual register lives to the end
 224     // of the defining block, potentially live across some blocks, then is
 225     // live into some number of blocks, but gets killed.  Start by adding a
 226     // range that goes from this definition to the end of the defining block.
 227     LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
 228     DEBUG(dbgs() << " +" << NewLR);
 229     interval.addRange(NewLR);
 230
 231     bool PHIJoin = lv_->isPHIJoin(interval.reg);
 232
 233     if (PHIJoin) {
 234       // A phi join register is killed at the end of the MBB and revived as a new
 235       // valno in the killing blocks.
 236       assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
 237       DEBUG(dbgs() << " phi-join");
 238       ValNo->setHasPHIKill(true);
 239     } else {
 240       // Iterate over all of the blocks that the variable is completely
 241       // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
 242       // live interval.
 243       for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
 244                E = vi.AliveBlocks.end(); I != E; ++I) {
 245         MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
 246         LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
 247         interval.addRange(LR);
 248         DEBUG(dbgs() << " +" << LR);
 249       }
 250     }
 251
 252     // Finally, this virtual register is live from the start of any killing
 253     // block to the 'use' slot of the killing instruction.
 254     for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
 255       MachineInstr *Kill = vi.Kills[i];
 256       SlotIndex Start = getMBBStartIdx(Kill->getParent());
 257       SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot();
 258
 259       // Create interval with one of a NEW value number.  Note that this value
 260       // number isn't actually defined by an instruction, weird huh? :)
 261       if (PHIJoin) {
 262         assert(getInstructionFromIndex(Start) == 0 &&
 263                "PHI def index points at actual instruction.");
 264         ValNo = interval.getNextValue(Start, VNInfoAllocator);
 265         ValNo->setIsPHIDef(true);
 266       }
 267       LiveRange LR(Start, killIdx, ValNo);
 268       interval.addRange(LR);
 269       DEBUG(dbgs() << " +" << LR);
 270     }
 271
 272   } else {
 273     if (MultipleDefsBySameMI(*mi, MOIdx))
 274       // Multiple defs of the same virtual register by the same instruction.
 275       // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
 276       // This is likely due to elimination of REG_SEQUENCE instructions. Return
 277       // here since there is nothing to do.
 278       return;
 279
 280     // If this is the second time we see a virtual register definition, it
 281     // must be due to phi elimination or two addr elimination.  If this is
 282     // the result of two address elimination, then the vreg is one of the
 283     // def-and-use register operand.
 284
 285     // It may also be partial redef like this:
 286     // 80  %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
 287     // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
 288     bool PartReDef = isPartialRedef(MIIdx, MO, interval);
 289     if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
 290       // If this is a two-address definition, then we have already processed
 291       // the live range.  The only problem is that we didn't realize there
 292       // are actually two values in the live interval.  Because of this we
 293       // need to take the LiveRegion that defines this register and split it
 294       // into two values.
 295       SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
 296
 297       const LiveRange *OldLR =
 298         interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
 299       VNInfo *OldValNo = OldLR->valno;
 300       SlotIndex DefIndex = OldValNo->def.getRegSlot();
 301
 302       // Delete the previous value, which should be short and continuous,
 303       // because the 2-addr copy must be in the same MBB as the redef.
 304       interval.removeRange(DefIndex, RedefIndex);
 305
 306       // The new value number (#1) is defined by the instruction we claimed
 307       // defined value #0.
 308       VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
 309
 310       // Value#0 is now defined by the 2-addr instruction.
 311       OldValNo->def = RedefIndex;
 312
 313       // Add the new live interval which replaces the range for the input copy.
 314       LiveRange LR(DefIndex, RedefIndex, ValNo);
 315       DEBUG(dbgs() << " replace range with " << LR);
 316       interval.addRange(LR);
 317
 318       // If this redefinition is dead, we need to add a dummy unit live
 319       // range covering the def slot.
 320       if (MO.isDead())
 321         interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(),
 322                                     OldValNo));
 323
 324       DEBUG({
 325           dbgs() << " RESULT: ";
 326           interval.print(dbgs(), tri_);
 327         });
 328     } else if (lv_->isPHIJoin(interval.reg)) {
 329       // In the case of PHI elimination, each variable definition is only
 330       // live until the end of the block.  We've already taken care of the
 331       // rest of the live range.
 332
 333       SlotIndex defIndex = MIIdx.getRegSlot();
 334       if (MO.isEarlyClobber())
 335         defIndex = MIIdx.getRegSlot(true);
 336
 337       VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
 338
 339       SlotIndex killIndex = getMBBEndIdx(mbb);
 340       LiveRange LR(defIndex, killIndex, ValNo);
 341       interval.addRange(LR);
 342       ValNo->setHasPHIKill(true);
 343       DEBUG(dbgs() << " phi-join +" << LR);
 344     } else {
 345       llvm_unreachable("Multiply defined register");
 346     }
 347   }
 348
 349   DEBUG(dbgs() << '\n');
 350 }
 351
 352 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 353                                               MachineBasicBlock::iterator mi,
 354                                               SlotIndex MIIdx,
 355                                               MachineOperand& MO,
 356                                               LiveInterval &interval) {
 357   // A physical register cannot be live across basic block, so its
 358   // lifetime must end somewhere in its defining basic block.
 359   DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
 360
 361   SlotIndex baseIndex = MIIdx;
 362   SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber());
 363   SlotIndex end = start;
 364
 365   // If it is not used after definition, it is considered dead at
 366   // the instruction defining it. Hence its interval is:
 367   // [defSlot(def), defSlot(def)+1)
 368   // For earlyclobbers, the defSlot was pushed back one; the extra
 369   // advance below compensates.
 370   if (MO.isDead()) {
 371     DEBUG(dbgs() << " dead");
 372     end = start.getDeadSlot();
 373     goto exit;
 374   }
 375
 376   // If it is not dead on definition, it must be killed by a
 377   // subsequent instruction. Hence its interval is:
 378   // [defSlot(def), useSlot(kill)+1)
 379   baseIndex = baseIndex.getNextIndex();
 380   while (++mi != MBB->end()) {
 381
 382     if (mi->isDebugValue())
 383       continue;
 384     if (getInstructionFromIndex(baseIndex) == 0)
 385       baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 386
 387     if (mi->killsRegister(interval.reg, tri_)) {
 388       DEBUG(dbgs() << " killed");
 389       end = baseIndex.getRegSlot();
 390       goto exit;
 391     } else {
 392       int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
 393       if (DefIdx != -1) {
 394         if (mi->isRegTiedToUseOperand(DefIdx)) {
 395           // Two-address instruction.
 396           end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber());
 397         } else {
 398           // Another instruction redefines the register before it is ever read.
 399           // Then the register is essentially dead at the instruction that
 400           // defines it. Hence its interval is:
 401           // [defSlot(def), defSlot(def)+1)
 402           DEBUG(dbgs() << " dead");
 403           end = start.getDeadSlot();
 404         }
 405         goto exit;
 406       }
 407     }
 408
 409     baseIndex = baseIndex.getNextIndex();
 410   }
 411
 412   // The only case we should have a dead physreg here without a killing or
 413   // instruction where we know it's dead is if it is live-in to the function
 414   // and never used. Another possible case is the implicit use of the
 415   // physical register has been deleted by two-address pass.
 416   end = start.getDeadSlot();
 417
 418 exit:
 419   assert(start < end && "did not find end of interval?");
 420
 421   // Already exists? Extend old live interval.
 422   VNInfo *ValNo = interval.getVNInfoAt(start);
 423   bool Extend = ValNo != 0;
 424   if (!Extend)
 425     ValNo = interval.getNextValue(start, VNInfoAllocator);
 426   LiveRange LR(start, end, ValNo);
 427   interval.addRange(LR);
 428   DEBUG(dbgs() << " +" << LR << '\n');
 429 }
 430
 431 void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 432                                       MachineBasicBlock::iterator MI,
 433                                       SlotIndex MIIdx,
 434                                       MachineOperand& MO,
 435                                       unsigned MOIdx) {
 436   if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 437     handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
 438                              getOrCreateInterval(MO.getReg()));
 439   else
 440     handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
 441                               getOrCreateInterval(MO.getReg()));
 442 }
 443
 444 void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
 445                                          SlotIndex MIIdx,
 446                                          LiveInterval &interval) {
 447   DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
 448
 449   // Look for kills, if it reaches a def before it's killed, then it shouldn't
 450   // be considered a livein.
 451   MachineBasicBlock::iterator mi = MBB->begin();
 452   MachineBasicBlock::iterator E = MBB->end();
 453   // Skip over DBG_VALUE at the start of the MBB.
 454   if (mi != E && mi->isDebugValue()) {
 455     while (++mi != E && mi->isDebugValue())
 456       ;
 457     if (mi == E)
 458       // MBB is empty except for DBG_VALUE's.
 459       return;
 460   }
 461
 462   SlotIndex baseIndex = MIIdx;
 463   SlotIndex start = baseIndex;
 464   if (getInstructionFromIndex(baseIndex) == 0)
 465     baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 466
 467   SlotIndex end = baseIndex;
 468   bool SeenDefUse = false;
 469
 470   while (mi != E) {
 471     if (mi->killsRegister(interval.reg, tri_)) {
 472       DEBUG(dbgs() << " killed");
 473       end = baseIndex.getRegSlot();
 474       SeenDefUse = true;
 475       break;
 476     } else if (mi->definesRegister(interval.reg, tri_)) {
 477       // Another instruction redefines the register before it is ever read.
 478       // Then the register is essentially dead at the instruction that defines
 479       // it. Hence its interval is:
 480       // [defSlot(def), defSlot(def)+1)
 481       DEBUG(dbgs() << " dead");
 482       end = start.getDeadSlot();
 483       SeenDefUse = true;
 484       break;
 485     }
 486
 487     while (++mi != E && mi->isDebugValue())
 488       // Skip over DBG_VALUE.
 489       ;
 490     if (mi != E)
 491       baseIndex = indexes_->getNextNonNullIndex(baseIndex);
 492   }
 493
 494   // Live-in register might not be used at all.
 495   if (!SeenDefUse) {
 496     DEBUG(dbgs() << " live through");
 497     end = getMBBEndIdx(MBB);
 498   }
 499
 500   SlotIndex defIdx = getMBBStartIdx(MBB);
 501   assert(getInstructionFromIndex(defIdx) == 0 &&
 502          "PHI def index points at actual instruction.");
 503   VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator);
 504   vni->setIsPHIDef(true);
 505   LiveRange LR(start, end, vni);
 506
 507   interval.addRange(LR);
 508   DEBUG(dbgs() << " +" << LR << '\n');
 509 }
 510
 511 /// computeIntervals - computes the live intervals for virtual
 512 /// registers. for some ordering of the machine instructions [1,N] a
 513 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 514 /// which a variable is live
 515 void LiveIntervals::computeIntervals() {
 516   DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
 517                << "********** Function: "
 518                << ((Value*)mf_->getFunction())->getName() << '\n');
 519
 520   RegMaskBlocks.resize(mf_->getNumBlockIDs());
 521
 522   SmallVector<unsigned, 8> UndefUses;
 523   for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
 524        MBBI != E; ++MBBI) {
 525     MachineBasicBlock *MBB = MBBI;
 526     RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size();
 527
 528     if (MBB->empty())
 529       continue;
 530
 531     // Track the index of the current machine instr.
 532     SlotIndex MIIndex = getMBBStartIdx(MBB);
 533     DEBUG(dbgs() << "BB#" << MBB->getNumber()
 534           << ":\t\t# derived from " << MBB->getName() << "\n");
 535
 536     // Create intervals for live-ins to this BB first.
 537     for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
 538            LE = MBB->livein_end(); LI != LE; ++LI) {
 539       handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
 540     }
 541
 542     // Skip over empty initial indices.
 543     if (getInstructionFromIndex(MIIndex) == 0)
 544       MIIndex = indexes_->getNextNonNullIndex(MIIndex);
 545
 546     for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
 547          MI != miEnd; ++MI) {
 548       DEBUG(dbgs() << MIIndex << "\t" << *MI);
 549       if (MI->isDebugValue())
 550         continue;
 551       assert(indexes_->getInstructionFromIndex(MIIndex) == MI &&
 552              "Lost SlotIndex synchronization");
 553
 554       // Handle defs.
 555       for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
 556         MachineOperand &MO = MI->getOperand(i);
 557
 558         // Collect register masks.
 559         if (MO.isRegMask()) {
 560           RegMaskSlots.push_back(MIIndex.getRegSlot());
 561           RegMaskBits.push_back(MO.getRegMask());
 562           continue;
 563         }
 564
 565         if (!MO.isReg() || !MO.getReg())
 566           continue;
 567
 568         // handle register defs - build intervals
 569         if (MO.isDef())
 570           handleRegisterDef(MBB, MI, MIIndex, MO, i);
 571         else if (MO.isUndef())
 572           UndefUses.push_back(MO.getReg());
 573       }
 574
 575       // Move to the next instr slot.
 576       MIIndex = indexes_->getNextNonNullIndex(MIIndex);
 577     }
 578
 579     // Compute the number of register mask instructions in this block.
 580     std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
 581     RMB.second = RegMaskSlots.size() - RMB.first;;
 582   }
 583
 584   // Create empty intervals for registers defined by implicit_def's (except
 585   // for those implicit_def that define values which are liveout of their
 586   // blocks.
 587   for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
 588     unsigned UndefReg = UndefUses[i];
 589     (void)getOrCreateInterval(UndefReg);
 590   }
 591 }
 592
 593 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
 594   float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
 595   return new LiveInterval(reg, Weight);
 596 }
 597
 598 /// dupInterval - Duplicate a live interval. The caller is responsible for
 599 /// managing the allocated memory.
 600 LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
 601   LiveInterval *NewLI = createInterval(li->reg);
 602   NewLI->Copy(*li, mri_, getVNInfoAllocator());
 603   return NewLI;
 604 }
 605
 606 /// shrinkToUses - After removing some uses of a register, shrink its live
 607 /// range to just the remaining uses. This method does not compute reaching
 608 /// defs for new uses, and it doesn't remove dead defs.
 609 bool LiveIntervals::shrinkToUses(LiveInterval *li,
 610                                  SmallVectorImpl<MachineInstr*> *dead) {
 611   DEBUG(dbgs() << "Shrink: " << *li << '\n');
 612   assert(TargetRegisterInfo::isVirtualRegister(li->reg)
 613          && "Can only shrink virtual registers");
 614   // Find all the values used, including PHI kills.
 615   SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
 616
 617   // Blocks that have already been added to WorkList as live-out.
 618   SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
 619
 620   // Visit all instructions reading li->reg.
 621   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
 622        MachineInstr *UseMI = I.skipInstruction();) {
 623     if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
 624       continue;
 625     SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
 626     // Note: This intentionally picks up the wrong VNI in case of an EC redef.
 627     // See below.
 628     VNInfo *VNI = li->getVNInfoBefore(Idx);
 629     if (!VNI) {
 630       // This shouldn't happen: readsVirtualRegister returns true, but there is
 631       // no live value. It is likely caused by a target getting <undef> flags
 632       // wrong.
 633       DEBUG(dbgs() << Idx << '\t' << *UseMI
 634                    << "Warning: Instr claims to read non-existent value in "
 635                     << *li << '\n');
 636       continue;
 637     }
 638     // Special case: An early-clobber tied operand reads and writes the
 639     // register one slot early.  The getVNInfoBefore call above would have
 640     // picked up the value defined by UseMI.  Adjust the kill slot and value.
 641     if (SlotIndex::isSameInstr(VNI->def, Idx)) {
 642       Idx = VNI->def;
 643       VNI = li->getVNInfoBefore(Idx);
 644       assert(VNI && "Early-clobber tied value not available");
 645     }
 646     WorkList.push_back(std::make_pair(Idx, VNI));
 647   }
 648
 649   // Create a new live interval with only minimal live segments per def.
 650   LiveInterval NewLI(li->reg, 0);
 651   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 652        I != E; ++I) {
 653     VNInfo *VNI = *I;
 654     if (VNI->isUnused())
 655       continue;
 656     NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
 657   }
 658
 659   // Keep track of the PHIs that are in use.
 660   SmallPtrSet<VNInfo*, 8> UsedPHIs;
 661
 662   // Extend intervals to reach all uses in WorkList.
 663   while (!WorkList.empty()) {
 664     SlotIndex Idx = WorkList.back().first;
 665     VNInfo *VNI = WorkList.back().second;
 666     WorkList.pop_back();
 667     const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
 668     SlotIndex BlockStart = getMBBStartIdx(MBB);
 669
 670     // Extend the live range for VNI to be live at Idx.
 671     if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
 672       (void)ExtVNI;
 673       assert(ExtVNI == VNI && "Unexpected existing value number");
 674       // Is this a PHIDef we haven't seen before?
 675       if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
 676         continue;
 677       // The PHI is live, make sure the predecessors are live-out.
 678       for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 679            PE = MBB->pred_end(); PI != PE; ++PI) {
 680         if (!LiveOut.insert(*PI))
 681           continue;
 682         SlotIndex Stop = getMBBEndIdx(*PI);
 683         // A predecessor is not required to have a live-out value for a PHI.
 684         if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
 685           WorkList.push_back(std::make_pair(Stop, PVNI));
 686       }
 687       continue;
 688     }
 689
 690     // VNI is live-in to MBB.
 691     DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
 692     NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
 693
 694     // Make sure VNI is live-out from the predecessors.
 695     for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
 696          PE = MBB->pred_end(); PI != PE; ++PI) {
 697       if (!LiveOut.insert(*PI))
 698         continue;
 699       SlotIndex Stop = getMBBEndIdx(*PI);
 700       assert(li->getVNInfoBefore(Stop) == VNI &&
 701              "Wrong value out of predecessor");
 702       WorkList.push_back(std::make_pair(Stop, VNI));
 703     }
 704   }
 705
 706   // Handle dead values.
 707   bool CanSeparate = false;
 708   for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
 709        I != E; ++I) {
 710     VNInfo *VNI = *I;
 711     if (VNI->isUnused())
 712       continue;
 713     LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
 714     assert(LII != NewLI.end() && "Missing live range for PHI");
 715     if (LII->end != VNI->def.getDeadSlot())
 716       continue;
 717     if (VNI->isPHIDef()) {
 718       // This is a dead PHI. Remove it.
 719       VNI->setIsUnused(true);
 720       NewLI.removeRange(*LII);
 721       DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
 722       CanSeparate = true;
 723     } else {
 724       // This is a dead def. Make sure the instruction knows.
 725       MachineInstr *MI = getInstructionFromIndex(VNI->def);
 726       assert(MI && "No instruction defining live value");
 727       MI->addRegisterDead(li->reg, tri_);
 728       if (dead && MI->allDefsAreDead()) {
 729         DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
 730         dead->push_back(MI);
 731       }
 732     }
 733   }
 734
 735   // Move the trimmed ranges back.
 736   li->ranges.swap(NewLI.ranges);
 737   DEBUG(dbgs() << "Shrunk: " << *li << '\n');
 738   return CanSeparate;
 739 }
 740
 741
 742 //===----------------------------------------------------------------------===//
 743 // Register allocator hooks.
 744 //
 745
 746 void LiveIntervals::addKillFlags() {
 747   for (iterator I = begin(), E = end(); I != E; ++I) {
 748     unsigned Reg = I->first;
 749     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 750       continue;
 751     if (mri_->reg_nodbg_empty(Reg))
 752       continue;
 753     LiveInterval *LI = I->second;
 754
 755     // Every instruction that kills Reg corresponds to a live range end point.
 756     for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
 757          ++RI) {
 758       // A block index indicates an MBB edge.
 759       if (RI->end.isBlock())
 760         continue;
 761       MachineInstr *MI = getInstructionFromIndex(RI->end);
 762       if (!MI)
 763         continue;
 764       MI->addRegisterKilled(Reg, NULL);
 765     }
 766   }
 767 }
 768
 769 #ifndef NDEBUG
 770 static bool intervalRangesSane(const LiveInterval& li) {
 771   if (li.empty()) {
 772     return true;
 773   }
 774
 775   SlotIndex lastEnd = li.begin()->start;
 776   for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end();
 777        lrItr != lrEnd; ++lrItr) {
 778     const LiveRange& lr = *lrItr;
 779     if (lastEnd > lr.start || lr.start >= lr.end)
 780       return false;
 781     lastEnd = lr.end;
 782   }
 783
 784   return true;
 785 }
 786 #endif
 787
 788 template <typename DefSetT>
 789 static void handleMoveDefs(LiveIntervals& lis, SlotIndex origIdx,
 790                            SlotIndex miIdx, const DefSetT& defs) {
 791   for (typename DefSetT::const_iterator defItr = defs.begin(),
 792                                         defEnd = defs.end();
 793        defItr != defEnd; ++defItr) {
 794     unsigned def = *defItr;
 795     LiveInterval& li = lis.getInterval(def);
 796     LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
 797     assert(lr != 0 && "No range for def?");
 798     lr->start = miIdx.getRegSlot();
 799     lr->valno->def = miIdx.getRegSlot();
 800     assert(intervalRangesSane(li) && "Broke live interval moving def.");
 801   }
 802 }
 803
 804 template <typename DeadDefSetT>
 805 static void handleMoveDeadDefs(LiveIntervals& lis, SlotIndex origIdx,
 806                                SlotIndex miIdx, const DeadDefSetT& deadDefs) {
 807   for (typename DeadDefSetT::const_iterator deadDefItr = deadDefs.begin(),
 808                                             deadDefEnd = deadDefs.end();
 809        deadDefItr != deadDefEnd; ++deadDefItr) {
 810     unsigned deadDef = *deadDefItr;
 811     LiveInterval& li = lis.getInterval(deadDef);
 812     LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot());
 813     assert(lr != 0 && "No range for dead def?");
 814     assert(lr->start == origIdx.getRegSlot() && "Bad dead range start?");
 815     assert(lr->end == origIdx.getDeadSlot() && "Bad dead range end?");
 816     assert(lr->valno->def == origIdx.getRegSlot() && "Bad dead valno def.");
 817     LiveRange t(*lr);
 818     t.start = miIdx.getRegSlot();
 819     t.valno->def = miIdx.getRegSlot();
 820     t.end = miIdx.getDeadSlot();
 821     li.removeRange(*lr);
 822     li.addRange(t);
 823     assert(intervalRangesSane(li) && "Broke live interval moving dead def.");
 824   }
 825 }
 826
 827 template <typename ECSetT>
 828 static void handleMoveECs(LiveIntervals& lis, SlotIndex origIdx,
 829                           SlotIndex miIdx, const ECSetT& ecs) {
 830   for (typename ECSetT::const_iterator ecItr = ecs.begin(), ecEnd = ecs.end();
 831        ecItr != ecEnd; ++ecItr) {
 832     unsigned ec = *ecItr;
 833     LiveInterval& li = lis.getInterval(ec);
 834     LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot(true));
 835     assert(lr != 0 && "No range for early clobber?");
 836     assert(lr->start == origIdx.getRegSlot(true) && "Bad EC range start?");
 837     assert(lr->end == origIdx.getRegSlot() && "Bad EC range end.");
 838     assert(lr->valno->def == origIdx.getRegSlot(true) && "Bad EC valno def.");
 839     LiveRange t(*lr);
 840     t.start = miIdx.getRegSlot(true);
 841     t.valno->def = miIdx.getRegSlot(true);
 842     t.end = miIdx.getRegSlot();
 843     li.removeRange(*lr);
 844     li.addRange(t);
 845     assert(intervalRangesSane(li) && "Broke live interval moving EC.");
 846   }
 847 }
 848
 849 static void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newIdx,
 850                           LiveIntervals& lis,
 851                           const TargetRegisterInfo& tri) {
 852   MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx);
 853   MachineInstr* newKillMI = lis.getInstructionFromIndex(newIdx);
 854   assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
 855   assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill.");
 856   oldKillMI->clearRegisterKills(reg, &tri);
 857   newKillMI->addRegisterKilled(reg, &tri);
 858 }
 859
 860 template <typename UseSetT>
 861 static void handleMoveUses(const MachineBasicBlock *mbb,
 862                            const MachineRegisterInfo& mri,
 863                            const TargetRegisterInfo& tri,
 864                            const BitVector& reservedRegs, LiveIntervals &lis,
 865                            SlotIndex origIdx, SlotIndex miIdx,
 866                            const UseSetT &uses) {
 867   bool movingUp = miIdx < origIdx;
 868   for (typename UseSetT::const_iterator usesItr = uses.begin(),
 869                                         usesEnd = uses.end();
 870        usesItr != usesEnd; ++usesItr) {
 871     unsigned use = *usesItr;
 872     if (!lis.hasInterval(use))
 873       continue;
 874     if (TargetRegisterInfo::isPhysicalRegister(use) && reservedRegs.test(use))
 875       continue;
 876     LiveInterval& li = lis.getInterval(use);
 877     LiveRange* lr = li.getLiveRangeBefore(origIdx.getRegSlot());
 878     assert(lr != 0 && "No range for use?");
 879     bool liveThrough = lr->end > origIdx.getRegSlot();
 880
 881     if (movingUp) {
 882       // If moving up and liveThrough - nothing to do.
 883       // If not live through we need to extend the range to the last use
 884       // between the old location and the new one.
 885       if (!liveThrough) {
 886         SlotIndex lastUseInRange = miIdx.getRegSlot();
 887         for (MachineRegisterInfo::use_iterator useI = mri.use_begin(use),
 888                                                useE = mri.use_end();
 889              useI != useE; ++useI) {
 890           const MachineInstr* mopI = &*useI;
 891           const MachineOperand& mop = useI.getOperand();
 892           SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI);
 893           SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber());
 894           if (opSlot > lastUseInRange && opSlot < origIdx)
 895             lastUseInRange = opSlot;
 896         }
 897
 898         // If we found a new instr endpoint update the kill flags.
 899         if (lastUseInRange != miIdx.getRegSlot())
 900           moveKillFlags(use, miIdx, lastUseInRange, lis, tri);
 901
 902         // Fix up the range end.
 903         lr->end = lastUseInRange;
 904       }
 905     } else {
 906       // Moving down is easy - the existing live range end tells us where
 907       // the last kill is.
 908       if (!liveThrough) {
 909         // Easy fix - just update the range endpoint.
 910         lr->end = miIdx.getRegSlot();
 911       } else {
 912         bool liveOut = lr->end >= lis.getSlotIndexes()->getMBBEndIdx(mbb);
 913         if (!liveOut && miIdx.getRegSlot() > lr->end) {
 914           moveKillFlags(use, lr->end, miIdx, lis, tri);
 915           lr->end = miIdx.getRegSlot();
 916         }
 917       }
 918     }
 919     assert(intervalRangesSane(li) && "Broke live interval moving use.");
 920   }
 921 }
 922
 923 void LiveIntervals::moveInstr(MachineBasicBlock::iterator insertPt,
 924                               MachineInstr *mi) {
 925   MachineBasicBlock* mbb = mi->getParent();
 926   assert((insertPt == mbb->end() || insertPt->getParent() == mbb) &&
 927          "Cannot handle moves across basic block boundaries.");
 928   assert(&*insertPt != mi && "No-op move requested?");
 929   assert(!mi->isBundled() && "Can't handle bundled instructions yet.");
 930
 931   // Grab the original instruction index.
 932   SlotIndex origIdx = indexes_->getInstructionIndex(mi);
 933
 934   // Move the machine instr and obtain its new index.
 935   indexes_->removeMachineInstrFromMaps(mi);
 936   mbb->splice(insertPt, mbb, mi);
 937   SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi);
 938
 939   // Pick the direction.
 940   bool movingUp = miIdx < origIdx;
 941
 942   // Collect the operands.
 943   DenseSet<unsigned> uses, defs, deadDefs, ecs;
 944   for (MachineInstr::mop_iterator mopItr = mi->operands_begin(),
 945          mopEnd = mi->operands_end();
 946        mopItr != mopEnd; ++mopItr) {
 947     const MachineOperand& mop = *mopItr;
 948
 949     if (!mop.isReg() || mop.getReg() == 0)
 950       continue;
 951     unsigned reg = mop.getReg();
 952
 953     if (mop.readsReg() && !ecs.count(reg)) {
 954       uses.insert(reg);
 955     }
 956     if (mop.isDef()) {
 957       if (mop.isDead()) {
 958         assert(!defs.count(reg) && "Can't mix defs with dead-defs.");
 959         deadDefs.insert(reg);
 960       } else if (mop.isEarlyClobber()) {
 961         uses.erase(reg);
 962         ecs.insert(reg);
 963       } else {
 964         assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs.");
 965         defs.insert(reg);
 966       }
 967     }
 968   }
 969
 970   BitVector reservedRegs(tri_->getReservedRegs(*mbb->getParent()));
 971
 972   if (movingUp) {
 973     handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses);
 974     handleMoveECs(*this, origIdx, miIdx, ecs);
 975     handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
 976     handleMoveDefs(*this, origIdx, miIdx, defs);
 977   } else {
 978     handleMoveDefs(*this, origIdx, miIdx, defs);
 979     handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs);
 980     handleMoveECs(*this, origIdx, miIdx, ecs);
 981     handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses);
 982   }
 983 }
 984
 985 /// getReMatImplicitUse - If the remat definition MI has one (for now, we only
 986 /// allow one) virtual register operand, then its uses are implicitly using
 987 /// the register. Returns the virtual register.
 988 unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
 989                                             MachineInstr *MI) const {
 990   unsigned RegOp = 0;
 991   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 992     MachineOperand &MO = MI->getOperand(i);
 993     if (!MO.isReg() || !MO.isUse())
 994       continue;
 995     unsigned Reg = MO.getReg();
 996     if (Reg == 0 || Reg == li.reg)
 997       continue;
 998
 999     if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
1000         !allocatableRegs_[Reg])
1001       continue;
1002     RegOp = MO.getReg();
1003     break; // Found vreg operand - leave the loop.
1004   }
1005   return RegOp;
1006 }
1007
1008 /// isValNoAvailableAt - Return true if the val# of the specified interval
1009 /// which reaches the given instruction also reaches the specified use index.
1010 bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
1011                                        SlotIndex UseIdx) const {
1012   VNInfo *UValNo = li.getVNInfoAt(UseIdx);
1013   return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
1014 }
1015
1016 /// isReMaterializable - Returns true if the definition MI of the specified
1017 /// val# of the specified interval is re-materializable.
1018 bool
1019 LiveIntervals::isReMaterializable(const LiveInterval &li,
1020                                   const VNInfo *ValNo, MachineInstr *MI,
1021                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
1022                                   bool &isLoad) {
1023   if (DisableReMat)
1024     return false;
1025
1026   if (!tii_->isTriviallyReMaterializable(MI, aa_))
1027     return false;
1028
1029   // Target-specific code can mark an instruction as being rematerializable
1030   // if it has one virtual reg use, though it had better be something like
1031   // a PIC base register which is likely to be live everywhere.
1032   unsigned ImpUse = getReMatImplicitUse(li, MI);
1033   if (ImpUse) {
1034     const LiveInterval &ImpLi = getInterval(ImpUse);
1035     for (MachineRegisterInfo::use_nodbg_iterator
1036            ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
1037          ri != re; ++ri) {
1038       MachineInstr *UseMI = &*ri;
1039       SlotIndex UseIdx = getInstructionIndex(UseMI);
1040       if (li.getVNInfoAt(UseIdx) != ValNo)
1041         continue;
1042       if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
1043         return false;
1044     }
1045
1046     // If a register operand of the re-materialized instruction is going to
1047     // be spilled next, then it's not legal to re-materialize this instruction.
1048     if (SpillIs)
1049       for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
1050         if (ImpUse == (*SpillIs)[i]->reg)
1051           return false;
1052   }
1053   return true;
1054 }
1055
1056 /// isReMaterializable - Returns true if every definition of MI of every
1057 /// val# of the specified interval is re-materializable.
1058 bool
1059 LiveIntervals::isReMaterializable(const LiveInterval &li,
1060                                   const SmallVectorImpl<LiveInterval*> *SpillIs,
1061                                   bool &isLoad) {
1062   isLoad = false;
1063   for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1064        i != e; ++i) {
1065     const VNInfo *VNI = *i;
1066     if (VNI->isUnused())
1067       continue; // Dead val#.
1068     // Is the def for the val# rematerializable?
1069     MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
1070     if (!ReMatDefMI)
1071       return false;
1072     bool DefIsLoad = false;
1073     if (!ReMatDefMI ||
1074         !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
1075       return false;
1076     isLoad |= DefIsLoad;
1077   }
1078   return true;
1079 }
1080
1081 MachineBasicBlock*
1082 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
1083   // A local live range must be fully contained inside the block, meaning it is
1084   // defined and killed at instructions, not at block boundaries. It is not
1085   // live in or or out of any block.
1086   //
1087   // It is technically possible to have a PHI-defined live range identical to a
1088   // single block, but we are going to return false in that case.
1089
1090   SlotIndex Start = LI.beginIndex();
1091   if (Start.isBlock())
1092     return NULL;
1093
1094   SlotIndex Stop = LI.endIndex();
1095   if (Stop.isBlock())
1096     return NULL;
1097
1098   // getMBBFromIndex doesn't need to search the MBB table when both indexes
1099   // belong to proper instructions.
1100   MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start);
1101   MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop);
1102   return MBB1 == MBB2 ? MBB1 : NULL;
1103 }
1104
1105 float
1106 LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1107   // Limit the loop depth ridiculousness.
1108   if (loopDepth > 200)
1109     loopDepth = 200;
1110
1111   // The loop depth is used to roughly estimate the number of times the
1112   // instruction is executed. Something like 10^d is simple, but will quickly
1113   // overflow a float. This expression behaves like 10^d for small d, but is
1114   // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1115   // headroom before overflow.
1116   // By the way, powf() might be unavailable here. For consistency,
1117   // We may take pow(double,double).
1118   float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
1119
1120   return (isDef + isUse) * lc;
1121 }
1122
1123 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
1124                                                   MachineInstr* startInst) {
1125   LiveInterval& Interval = getOrCreateInterval(reg);
1126   VNInfo* VN = Interval.getNextValue(
1127     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
1128     getVNInfoAllocator());
1129   VN->setHasPHIKill(true);
1130   LiveRange LR(
1131      SlotIndex(getInstructionIndex(startInst).getRegSlot()),
1132      getMBBEndIdx(startInst->getParent()), VN);
1133   Interval.addRange(LR);
1134
1135   return LR;
1136 }
1137
1138
1139 //===----------------------------------------------------------------------===//
1140 //                          Register mask functions
1141 //===----------------------------------------------------------------------===//
1142
1143 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
1144                                              BitVector &UsableRegs) {
1145   if (LI.empty())
1146     return false;
1147   LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
1148
1149   // Use a smaller arrays for local live ranges.
1150   ArrayRef<SlotIndex> Slots;
1151   ArrayRef<const uint32_t*> Bits;
1152   if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
1153     Slots = getRegMaskSlotsInBlock(MBB->getNumber());
1154     Bits = getRegMaskBitsInBlock(MBB->getNumber());
1155   } else {
1156     Slots = getRegMaskSlots();
1157     Bits = getRegMaskBits();
1158   }
1159
1160   // We are going to enumerate all the register mask slots contained in LI.
1161   // Start with a binary search of RegMaskSlots to find a starting point.
1162   ArrayRef<SlotIndex>::iterator SlotI =
1163     std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
1164   ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
1165
1166   // No slots in range, LI begins after the last call.
1167   if (SlotI == SlotE)
1168     return false;
1169
1170   bool Found = false;
1171   for (;;) {
1172     assert(*SlotI >= LiveI->start);
1173     // Loop over all slots overlapping this segment.
1174     while (*SlotI < LiveI->end) {
1175       // *SlotI overlaps LI. Collect mask bits.
1176       if (!Found) {
1177         // This is the first overlap. Initialize UsableRegs to all ones.
1178         UsableRegs.clear();
1179         UsableRegs.resize(tri_->getNumRegs(), true);
1180         Found = true;
1181       }
1182       // Remove usable registers clobbered by this mask.
1183       UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
1184       if (++SlotI == SlotE)
1185         return Found;
1186     }
1187     // *SlotI is beyond the current LI segment.
1188     LiveI = LI.advanceTo(LiveI, *SlotI);
1189     if (LiveI == LiveE)
1190       return Found;
1191     // Advance SlotI until it overlaps.
1192     while (*SlotI < LiveI->start)
1193       if (++SlotI == SlotE)
1194         return Found;
1195   }
1196 }