LiveIntervalAnalysis.cpp revision 3dc7c5138d219048d69952bead22f75efb984fa3 
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
362static bool isRegLiveIntoSuccessor(const MachineBasicBlock *MBB, unsigned Reg) {
363  for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
364                                              SE = MBB->succ_end();
365       SI != SE; ++SI) {
366    const MachineBasicBlock* succ = *SI;
367    if (succ->isLiveIn(Reg))
368      return true;
369  }
370  return false;
371}
372
373void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
374                                              MachineBasicBlock::iterator mi,
375                                              SlotIndex MIIdx,
376                                              MachineOperand& MO,
377                                              LiveInterval &interval) {
378  DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
379
380  SlotIndex baseIndex = MIIdx;
381  SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber());
382  SlotIndex end = start;
383
384  // If it is not used after definition, it is considered dead at
385  // the instruction defining it. Hence its interval is:
386  // [defSlot(def), defSlot(def)+1)
387  // For earlyclobbers, the defSlot was pushed back one; the extra
388  // advance below compensates.
389  if (MO.isDead()) {
390    DEBUG(dbgs() << " dead");
391    end = start.getDeadSlot();
392    goto exit;
393  }
394
395  // If it is not dead on definition, it must be killed by a
396  // subsequent instruction. Hence its interval is:
397  // [defSlot(def), useSlot(kill)+1)
398  baseIndex = baseIndex.getNextIndex();
399  while (++mi != MBB->end()) {
400
401    if (mi->isDebugValue())
402      continue;
403    if (getInstructionFromIndex(baseIndex) == 0)
404      baseIndex = indexes_->getNextNonNullIndex(baseIndex);
405
406    if (mi->killsRegister(interval.reg, tri_)) {
407      DEBUG(dbgs() << " killed");
408      end = baseIndex.getRegSlot();
409      goto exit;
410    } else {
411      int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
412      if (DefIdx != -1) {
413        if (mi->isRegTiedToUseOperand(DefIdx)) {
414          // Two-address instruction.
415          end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber());
416        } else {
417          // Another instruction redefines the register before it is ever read.
418          // Then the register is essentially dead at the instruction that
419          // defines it. Hence its interval is:
420          // [defSlot(def), defSlot(def)+1)
421          DEBUG(dbgs() << " dead");
422          end = start.getDeadSlot();
423        }
424        goto exit;
425      }
426    }
427
428    baseIndex = baseIndex.getNextIndex();
429  }
430
431  // If we get here the register *should* be live out.
432  assert(!isAllocatable(interval.reg) && "Physregs shouldn't be live out!");
433
434  // FIXME: We need saner rules for reserved regs.
435  if (isReserved(interval.reg)) {
436    end = start.getDeadSlot();
437  } else {
438    // Unreserved, unallocable registers like EFLAGS can be live across basic
439    // block boundaries.
440    assert(isRegLiveIntoSuccessor(MBB, interval.reg) &&
441           "Unreserved reg not live-out?");
442    end = getMBBEndIdx(MBB);
443  }
444exit:
445  assert(start < end && "did not find end of interval?");
446
447  // Already exists? Extend old live interval.
448  VNInfo *ValNo = interval.getVNInfoAt(start);
449  bool Extend = ValNo != 0;
450  if (!Extend)
451    ValNo = interval.getNextValue(start, VNInfoAllocator);
452  LiveRange LR(start, end, ValNo);
453  interval.addRange(LR);
454  DEBUG(dbgs() << " +" << LR << '\n');
455}
456
457void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
458                                      MachineBasicBlock::iterator MI,
459                                      SlotIndex MIIdx,
460                                      MachineOperand& MO,
461                                      unsigned MOIdx) {
462  if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
463    handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
464                             getOrCreateInterval(MO.getReg()));
465  else
466    handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
467                              getOrCreateInterval(MO.getReg()));
468}
469
470void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
471                                         SlotIndex MIIdx,
472                                         LiveInterval &interval) {
473  assert(TargetRegisterInfo::isPhysicalRegister(interval.reg) &&
474         "Only physical registers can be live in.");
475  assert((!isAllocatable(interval.reg) || MBB->getParent()->begin() ||
476          MBB->isLandingPad()) &&
477          "Allocatable live-ins only valid for entry blocks and landing pads.");
478
479  DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
480
481  // Look for kills, if it reaches a def before it's killed, then it shouldn't
482  // be considered a livein.
483  MachineBasicBlock::iterator mi = MBB->begin();
484  MachineBasicBlock::iterator E = MBB->end();
485  // Skip over DBG_VALUE at the start of the MBB.
486  if (mi != E && mi->isDebugValue()) {
487    while (++mi != E && mi->isDebugValue())
488      ;
489    if (mi == E)
490      // MBB is empty except for DBG_VALUE's.
491      return;
492  }
493
494  SlotIndex baseIndex = MIIdx;
495  SlotIndex start = baseIndex;
496  if (getInstructionFromIndex(baseIndex) == 0)
497    baseIndex = indexes_->getNextNonNullIndex(baseIndex);
498
499  SlotIndex end = baseIndex;
500  bool SeenDefUse = false;
501
502  while (mi != E) {
503    if (mi->killsRegister(interval.reg, tri_)) {
504      DEBUG(dbgs() << " killed");
505      end = baseIndex.getRegSlot();
506      SeenDefUse = true;
507      break;
508    } else if (mi->modifiesRegister(interval.reg, tri_)) {
509      // Another instruction redefines the register before it is ever read.
510      // Then the register is essentially dead at the instruction that defines
511      // it. Hence its interval is:
512      // [defSlot(def), defSlot(def)+1)
513      DEBUG(dbgs() << " dead");
514      end = start.getDeadSlot();
515      SeenDefUse = true;
516      break;
517    }
518
519    while (++mi != E && mi->isDebugValue())
520      // Skip over DBG_VALUE.
521      ;
522    if (mi != E)
523      baseIndex = indexes_->getNextNonNullIndex(baseIndex);
524  }
525
526  // Live-in register might not be used at all.
527  if (!SeenDefUse) {
528    if (isAllocatable(interval.reg) ||
529        !isRegLiveIntoSuccessor(MBB, interval.reg)) {
530      // Allocatable registers are never live through.
531      // Non-allocatable registers that aren't live into any successors also
532      // aren't live through.
533      DEBUG(dbgs() << " dead");
534      return;
535    } else {
536      // If we get here the register is non-allocatable and live into some
537      // successor. We'll conservatively assume it's 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/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
813/// allow one) virtual register operand, then its uses are implicitly using
814/// the register. Returns the virtual register.
815unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
816                                            MachineInstr *MI) const {
817  unsigned RegOp = 0;
818  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
819    MachineOperand &MO = MI->getOperand(i);
820    if (!MO.isReg() || !MO.isUse())
821      continue;
822    unsigned Reg = MO.getReg();
823    if (Reg == 0 || Reg == li.reg)
824      continue;
825
826    if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isAllocatable(Reg))
827      continue;
828    RegOp = MO.getReg();
829    break; // Found vreg operand - leave the loop.
830  }
831  return RegOp;
832}
833
834/// isValNoAvailableAt - Return true if the val# of the specified interval
835/// which reaches the given instruction also reaches the specified use index.
836bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
837                                       SlotIndex UseIdx) const {
838  VNInfo *UValNo = li.getVNInfoAt(UseIdx);
839  return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
840}
841
842/// isReMaterializable - Returns true if the definition MI of the specified
843/// val# of the specified interval is re-materializable.
844bool
845LiveIntervals::isReMaterializable(const LiveInterval &li,
846                                  const VNInfo *ValNo, MachineInstr *MI,
847                                  const SmallVectorImpl<LiveInterval*> *SpillIs,
848                                  bool &isLoad) {
849  if (DisableReMat)
850    return false;
851
852  if (!tii_->isTriviallyReMaterializable(MI, aa_))
853    return false;
854
855  // Target-specific code can mark an instruction as being rematerializable
856  // if it has one virtual reg use, though it had better be something like
857  // a PIC base register which is likely to be live everywhere.
858  unsigned ImpUse = getReMatImplicitUse(li, MI);
859  if (ImpUse) {
860    const LiveInterval &ImpLi = getInterval(ImpUse);
861    for (MachineRegisterInfo::use_nodbg_iterator
862           ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
863         ri != re; ++ri) {
864      MachineInstr *UseMI = &*ri;
865      SlotIndex UseIdx = getInstructionIndex(UseMI);
866      if (li.getVNInfoAt(UseIdx) != ValNo)
867        continue;
868      if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
869        return false;
870    }
871
872    // If a register operand of the re-materialized instruction is going to
873    // be spilled next, then it's not legal to re-materialize this instruction.
874    if (SpillIs)
875      for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
876        if (ImpUse == (*SpillIs)[i]->reg)
877          return false;
878  }
879  return true;
880}
881
882/// isReMaterializable - Returns true if every definition of MI of every
883/// val# of the specified interval is re-materializable.
884bool
885LiveIntervals::isReMaterializable(const LiveInterval &li,
886                                  const SmallVectorImpl<LiveInterval*> *SpillIs,
887                                  bool &isLoad) {
888  isLoad = false;
889  for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
890       i != e; ++i) {
891    const VNInfo *VNI = *i;
892    if (VNI->isUnused())
893      continue; // Dead val#.
894    // Is the def for the val# rematerializable?
895    MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
896    if (!ReMatDefMI)
897      return false;
898    bool DefIsLoad = false;
899    if (!ReMatDefMI ||
900        !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
901      return false;
902    isLoad |= DefIsLoad;
903  }
904  return true;
905}
906
907MachineBasicBlock*
908LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
909  // A local live range must be fully contained inside the block, meaning it is
910  // defined and killed at instructions, not at block boundaries. It is not
911  // live in or or out of any block.
912  //
913  // It is technically possible to have a PHI-defined live range identical to a
914  // single block, but we are going to return false in that case.
915
916  SlotIndex Start = LI.beginIndex();
917  if (Start.isBlock())
918    return NULL;
919
920  SlotIndex Stop = LI.endIndex();
921  if (Stop.isBlock())
922    return NULL;
923
924  // getMBBFromIndex doesn't need to search the MBB table when both indexes
925  // belong to proper instructions.
926  MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start);
927  MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop);
928  return MBB1 == MBB2 ? MBB1 : NULL;
929}
930
931float
932LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
933  // Limit the loop depth ridiculousness.
934  if (loopDepth > 200)
935    loopDepth = 200;
936
937  // The loop depth is used to roughly estimate the number of times the
938  // instruction is executed. Something like 10^d is simple, but will quickly
939  // overflow a float. This expression behaves like 10^d for small d, but is
940  // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
941  // headroom before overflow.
942  // By the way, powf() might be unavailable here. For consistency,
943  // We may take pow(double,double).
944  float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
945
946  return (isDef + isUse) * lc;
947}
948
949LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
950                                                  MachineInstr* startInst) {
951  LiveInterval& Interval = getOrCreateInterval(reg);
952  VNInfo* VN = Interval.getNextValue(
953    SlotIndex(getInstructionIndex(startInst).getRegSlot()),
954    getVNInfoAllocator());
955  VN->setHasPHIKill(true);
956  LiveRange LR(
957     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
958     getMBBEndIdx(startInst->getParent()), VN);
959  Interval.addRange(LR);
960
961  return LR;
962}
963
964
965//===----------------------------------------------------------------------===//
966//                          Register mask functions
967//===----------------------------------------------------------------------===//
968
969bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
970                                             BitVector &UsableRegs) {
971  if (LI.empty())
972    return false;
973  LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
974
975  // Use a smaller arrays for local live ranges.
976  ArrayRef<SlotIndex> Slots;
977  ArrayRef<const uint32_t*> Bits;
978  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
979    Slots = getRegMaskSlotsInBlock(MBB->getNumber());
980    Bits = getRegMaskBitsInBlock(MBB->getNumber());
981  } else {
982    Slots = getRegMaskSlots();
983    Bits = getRegMaskBits();
984  }
985
986  // We are going to enumerate all the register mask slots contained in LI.
987  // Start with a binary search of RegMaskSlots to find a starting point.
988  ArrayRef<SlotIndex>::iterator SlotI =
989    std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
990  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
991
992  // No slots in range, LI begins after the last call.
993  if (SlotI == SlotE)
994    return false;
995
996  bool Found = false;
997  for (;;) {
998    assert(*SlotI >= LiveI->start);
999    // Loop over all slots overlapping this segment.
1000    while (*SlotI < LiveI->end) {
1001      // *SlotI overlaps LI. Collect mask bits.
1002      if (!Found) {
1003        // This is the first overlap. Initialize UsableRegs to all ones.
1004        UsableRegs.clear();
1005        UsableRegs.resize(tri_->getNumRegs(), true);
1006        Found = true;
1007      }
1008      // Remove usable registers clobbered by this mask.
1009      UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
1010      if (++SlotI == SlotE)
1011        return Found;
1012    }
1013    // *SlotI is beyond the current LI segment.
1014    LiveI = LI.advanceTo(LiveI, *SlotI);
1015    if (LiveI == LiveE)
1016      return Found;
1017    // Advance SlotI until it overlaps.
1018    while (*SlotI < LiveI->start)
1019      if (++SlotI == SlotE)
1020        return Found;
1021  }
1022}
1023
1024//===----------------------------------------------------------------------===//
1025//                         IntervalUpdate class.
1026//===----------------------------------------------------------------------===//
1027
1028/// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
1029class LiveIntervals::HMEditor {
1030private:
1031  LiveIntervals& lis;
1032  SlotIndex newIdx;
1033
1034public:
1035  HMEditor(LiveIntervals& lis, SlotIndex newIdx)
1036    : lis(lis), newIdx(newIdx) {}
1037
1038  // Update lr to be defined at newIdx. Preserves lr.
1039  void moveDef(LiveRange& lr, LiveInterval& li) {
1040    lr.start = newIdx.getRegSlot();
1041    lr.valno->def = newIdx.getRegSlot();
1042    assert(intervalRangesSane(li) && "Broke live interval moving def.");
1043  }
1044
1045  // Removes lr from li, inserting a new dead-def range starting at newIdx.
1046  void moveDeadDefOrEC(LiveRange& lr, LiveInterval& li, bool isEC) {
1047    LiveRange t(lr);
1048    t.start = newIdx.getRegSlot(isEC);
1049    t.valno->def = newIdx.getRegSlot(isEC);
1050    t.end = isEC ? newIdx.getRegSlot() : newIdx.getDeadSlot();
1051    li.removeRange(lr);
1052    li.addRange(t);
1053    assert(intervalRangesSane(li) && "Broke live interval moving dead def.");
1054  }
1055
1056  void moveUseDown(SlotIndex oldIdx, LiveRange& lr, LiveInterval& li,
1057                   const MachineBasicBlock* mbb) {
1058    bool liveThrough = lr.end > oldIdx.getRegSlot();
1059    if (!liveThrough) {
1060      // Easy fix - just update the range endpoint.
1061      lr.end = newIdx.getRegSlot();
1062    } else {
1063      bool liveOut = lr.end >= lis.getSlotIndexes()->getMBBEndIdx(mbb);
1064      if (!liveOut) {
1065        moveKillFlags(li.reg, lr.end, newIdx);
1066        lr.end = newIdx.getRegSlot();
1067      }
1068    }
1069    assert(intervalRangesSane(li) && "Broke live interval moving use.");
1070  }
1071
1072  // Returns the new
1073  void moveUseUp(SlotIndex oldIdx, LiveRange& lr, LiveInterval& li) {
1074    bool liveThrough = lr.end > oldIdx.getRegSlot();
1075    if (liveThrough)
1076      return; // If we moving up and live through there's nothing to do.
1077    SlotIndex lastUseInRange = newIdx.getRegSlot();
1078    for (MachineRegisterInfo::use_nodbg_iterator
1079           useI = lis.mri_->use_nodbg_begin(li.reg),
1080           useE = lis.mri_->use_nodbg_end();
1081         useI != useE; ++useI) {
1082      const MachineInstr* mopI = &*useI;
1083      const MachineOperand& mop = useI.getOperand();
1084      SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI);
1085      SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber());
1086      if (opSlot > lastUseInRange && opSlot < oldIdx)
1087        lastUseInRange = opSlot;
1088    }
1089
1090    // If we found a new instr endpoint update the kill flags.
1091    if (lastUseInRange != newIdx.getRegSlot())
1092      moveKillFlags(li.reg, newIdx, lastUseInRange);
1093
1094    // Fix up the range end.
1095    lr.end = lastUseInRange;
1096
1097    assert(intervalRangesSane(li) && "Broke live interval moving use.");
1098  }
1099
1100  // Update intervals for all operands of mi from oldIndex to newIndex.
1101  void moveAllOperands(MachineInstr* mi, SlotIndex oldIdx) {
1102    // Figure out the direction we're moving.
1103    bool movingUp = newIdx < oldIdx;
1104
1105    // Collect the operands.
1106    DenseSet<unsigned> uses, defs, deadDefs, ecs;
1107    for (MachineInstr::mop_iterator mopItr = mi->operands_begin(),
1108                                    mopEnd = mi->operands_end();
1109         mopItr != mopEnd; ++mopItr) {
1110      const MachineOperand& mop = *mopItr;
1111
1112      if (!mop.isReg() || mop.getReg() == 0)
1113        continue;
1114
1115      unsigned reg = mop.getReg();
1116
1117      // TODO: Currently we're skipping uses that are reserved or have no
1118      // interval, but we're not updating their kills. This should be
1119      // fixed.
1120      if (!lis.hasInterval(reg) ||
1121          (TargetRegisterInfo::isPhysicalRegister(reg) && lis.isReserved(reg)))
1122        continue;
1123
1124      if (mop.readsReg() && !ecs.count(reg)) {
1125        uses.insert(reg);
1126      }
1127      if (mop.isDef()) {
1128        if (mop.isDead()) {
1129          assert(!defs.count(reg) && "Can't mix defs with dead-defs.");
1130          deadDefs.insert(reg);
1131        } else if (mop.isEarlyClobber()) {
1132          uses.erase(reg);
1133          ecs.insert(reg);
1134        } else {
1135          assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs.");
1136          defs.insert(reg);
1137        }
1138      }
1139    }
1140
1141    if (movingUp) {
1142      moveUsesUp(oldIdx, uses);
1143      moveECs(oldIdx, ecs);
1144      moveDeadDefs(oldIdx, deadDefs);
1145      moveDefs(oldIdx, defs);
1146    } else {
1147      moveDefs(oldIdx, defs);
1148      moveDeadDefs(oldIdx, deadDefs);
1149      moveECs(oldIdx, ecs);
1150      moveUsesDown(oldIdx, uses, mi->getParent());
1151    }
1152  }
1153
1154private:
1155
1156#ifndef NDEBUG
1157    bool intervalRangesSane(const LiveInterval& li) {
1158    if (li.empty()) {
1159      return true;
1160    }
1161
1162    SlotIndex lastEnd = li.begin()->start;
1163    for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end();
1164         lrItr != lrEnd; ++lrItr) {
1165      const LiveRange& lr = *lrItr;
1166      if (lastEnd > lr.start || lr.start >= lr.end)
1167        return false;
1168      lastEnd = lr.end;
1169    }
1170
1171    return true;
1172  }
1173#endif
1174
1175  void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newKillIdx) {
1176    MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx);
1177    if (!oldKillMI->killsRegister(reg))
1178      return; // Bail out if we don't have kill flags on the old register.
1179    MachineInstr* newKillMI = lis.getInstructionFromIndex(newKillIdx);
1180    assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
1181    assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill.");
1182    oldKillMI->clearRegisterKills(reg, lis.tri_);
1183    newKillMI->addRegisterKilled(reg, lis.tri_);
1184  }
1185
1186  template <typename DefSetT>
1187  void moveDefs(SlotIndex oldIdx, const DefSetT& defs) {
1188    typedef typename DefSetT::const_iterator DefItr;
1189    for (DefItr di = defs.begin(), de = defs.end(); di != de; ++di) {
1190      unsigned def = *di;
1191      LiveInterval& li = lis.getInterval(def);
1192      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot());
1193      assert(lr != 0 && "No range?");
1194      moveDef(*lr, li);
1195    }
1196  }
1197
1198  template <typename DeadDefSetT>
1199  void moveDeadDefs(SlotIndex oldIdx, const DeadDefSetT& deadDefs) {
1200    typedef typename DeadDefSetT::const_iterator DeadDefItr;
1201    for (DeadDefItr di = deadDefs.begin(),de = deadDefs.end(); di != de; ++di) {
1202      unsigned deadDef = *di;
1203      LiveInterval& li = lis.getInterval(deadDef);
1204      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot());
1205      assert(lr != 0 && "No range for dead def?");
1206      assert(lr->start == oldIdx.getRegSlot() && "Bad dead range start?");
1207      assert(lr->end == oldIdx.getDeadSlot() && "Bad dead range end?");
1208      assert(lr->valno->def == oldIdx.getRegSlot() && "Bad dead valno def.");
1209      moveDeadDefOrEC(*lr, li, false);
1210    }
1211  }
1212
1213  template <typename ECSetT>
1214  void moveECs(SlotIndex oldIdx, const ECSetT& ecs) {
1215    typedef typename ECSetT::const_iterator ECItr;
1216    for (ECItr eci = ecs.begin(), ece = ecs.end(); eci != ece; ++eci) {
1217      unsigned ec = *eci;
1218      LiveInterval& li = lis.getInterval(ec);
1219      LiveRange* lr = li.getLiveRangeContaining(oldIdx.getRegSlot(true));
1220      assert(lr != 0 && "No range for early clobber?");
1221      assert(lr->start == oldIdx.getRegSlot(true) && "Bad EC range start?");
1222      assert(lr->end == oldIdx.getRegSlot() && "Bad EC range end.");
1223      assert(lr->valno->def == oldIdx.getRegSlot(true) && "Bad EC valno def.");
1224      moveDeadDefOrEC(*lr, li, true);
1225    }
1226  }
1227
1228  template <typename UseSetT>
1229  void moveUsesUp(SlotIndex oldIdx, const UseSetT &uses) {
1230    typedef typename UseSetT::const_iterator UseItr;
1231    for (UseItr ui = uses.begin(), ue = uses.end(); ui != ue; ++ui) {
1232      unsigned use = *ui;
1233      LiveInterval& li = lis.getInterval(use);
1234      LiveRange* lr = li.getLiveRangeBefore(oldIdx.getRegSlot());
1235      assert(lr != 0 && "No range for use?");
1236      moveUseUp(oldIdx, *lr, li);
1237    }
1238  }
1239
1240  template <typename UseSetT>
1241  void moveUsesDown(SlotIndex oldIdx, const UseSetT &uses,
1242                    const MachineBasicBlock* mbb) {
1243    typedef typename UseSetT::const_iterator UseItr;
1244    for (UseItr ui = uses.begin(), ue = uses.end(); ui != ue; ++ui) {
1245      unsigned use = *ui;
1246      LiveInterval& li = lis.getInterval(use);
1247      LiveRange* lr = li.getLiveRangeBefore(oldIdx.getRegSlot());
1248      assert(lr != 0 && "No range for use?");
1249      moveUseDown(oldIdx, *lr, li, mbb);
1250    }
1251  }
1252};
1253
1254void LiveIntervals::handleMove(MachineInstr* mi) {
1255  SlotIndex oldIndex = indexes_->getInstructionIndex(mi);
1256  indexes_->removeMachineInstrFromMaps(mi);
1257  SlotIndex newIndex = mi->isInsideBundle() ?
1258                        indexes_->getInstructionIndex(mi->getBundleStart()) :
1259                        indexes_->insertMachineInstrInMaps(mi);
1260  MachineBasicBlock* mbb = mi->getParent();
1261  assert(getMBBStartIdx(mbb) <= oldIndex && oldIndex < getMBBEndIdx(mbb) &&
1262         "Cannot handle moves across basic block boundaries.");
1263  assert(!mi->isBundled() && "Can't handle bundled instructions yet.");
1264
1265  HMEditor hme(*this, newIndex);
1266  hme.moveAllOperands(mi, oldIndex);
1267}
1268