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