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