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