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/MachineDominators.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineRegisterInfo.h"
26#include "llvm/CodeGen/Passes.h"
27#include "llvm/Target/TargetRegisterInfo.h"
28#include "llvm/Target/TargetInstrInfo.h"
29#include "llvm/Target/TargetMachine.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/ADT/DenseSet.h"
35#include "llvm/ADT/STLExtras.h"
36#include "LiveRangeCalc.h"
37#include "VirtRegMap.h"
38#include <algorithm>
39#include <limits>
40#include <cmath>
41using namespace llvm;
42
43// Switch to the new experimental algorithm for computing live intervals.
44static cl::opt<bool>
45NewLiveIntervals("new-live-intervals", cl::Hidden,
46                 cl::desc("Use new algorithm forcomputing live intervals"));
47
48char LiveIntervals::ID = 0;
49char &llvm::LiveIntervalsID = LiveIntervals::ID;
50INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
51                "Live Interval Analysis", false, false)
52INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
53INITIALIZE_PASS_DEPENDENCY(LiveVariables)
54INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
55INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
56INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
57                "Live Interval Analysis", false, false)
58
59void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
60  AU.setPreservesCFG();
61  AU.addRequired<AliasAnalysis>();
62  AU.addPreserved<AliasAnalysis>();
63  AU.addRequired<LiveVariables>();
64  AU.addPreserved<LiveVariables>();
65  AU.addPreservedID(MachineLoopInfoID);
66  AU.addRequiredTransitiveID(MachineDominatorsID);
67  AU.addPreservedID(MachineDominatorsID);
68  AU.addPreserved<SlotIndexes>();
69  AU.addRequiredTransitive<SlotIndexes>();
70  MachineFunctionPass::getAnalysisUsage(AU);
71}
72
73LiveIntervals::LiveIntervals() : MachineFunctionPass(ID),
74  DomTree(0), LRCalc(0) {
75  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
76}
77
78LiveIntervals::~LiveIntervals() {
79  delete LRCalc;
80}
81
82void LiveIntervals::releaseMemory() {
83  // Free the live intervals themselves.
84  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
85    delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
86  VirtRegIntervals.clear();
87  RegMaskSlots.clear();
88  RegMaskBits.clear();
89  RegMaskBlocks.clear();
90
91  for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
92    delete RegUnitIntervals[i];
93  RegUnitIntervals.clear();
94
95  // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
96  VNInfoAllocator.Reset();
97}
98
99/// runOnMachineFunction - Register allocate the whole function
100///
101bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
102  MF = &fn;
103  MRI = &MF->getRegInfo();
104  TM = &fn.getTarget();
105  TRI = TM->getRegisterInfo();
106  TII = TM->getInstrInfo();
107  AA = &getAnalysis<AliasAnalysis>();
108  LV = &getAnalysis<LiveVariables>();
109  Indexes = &getAnalysis<SlotIndexes>();
110  DomTree = &getAnalysis<MachineDominatorTree>();
111  if (!LRCalc)
112    LRCalc = new LiveRangeCalc();
113  AllocatableRegs = TRI->getAllocatableSet(fn);
114  ReservedRegs = TRI->getReservedRegs(fn);
115
116  // Allocate space for all virtual registers.
117  VirtRegIntervals.resize(MRI->getNumVirtRegs());
118
119  if (NewLiveIntervals) {
120    // This is the new way of computing live intervals.
121    // It is independent of LiveVariables, and it can run at any time.
122    computeVirtRegs();
123    computeRegMasks();
124  } else {
125    // This is the old way of computing live intervals.
126    // It depends on LiveVariables.
127    computeIntervals();
128  }
129  computeLiveInRegUnits();
130
131  DEBUG(dump());
132  return true;
133}
134
135/// print - Implement the dump method.
136void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
137  OS << "********** INTERVALS **********\n";
138
139  // Dump the regunits.
140  for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
141    if (LiveInterval *LI = RegUnitIntervals[i])
142      OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
143
144  // Dump the virtregs.
145  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
146    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
147    if (hasInterval(Reg))
148      OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
149  }
150
151  printInstrs(OS);
152}
153
154void LiveIntervals::printInstrs(raw_ostream &OS) const {
155  OS << "********** MACHINEINSTRS **********\n";
156  MF->print(OS, Indexes);
157}
158
159#ifndef NDEBUG
160void LiveIntervals::dumpInstrs() const {
161  printInstrs(dbgs());
162}
163#endif
164
165static
166bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
167  unsigned Reg = MI.getOperand(MOIdx).getReg();
168  for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
169    const MachineOperand &MO = MI.getOperand(i);
170    if (!MO.isReg())
171      continue;
172    if (MO.getReg() == Reg && MO.isDef()) {
173      assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
174             MI.getOperand(MOIdx).getSubReg() &&
175             (MO.getSubReg() || MO.isImplicit()));
176      return true;
177    }
178  }
179  return false;
180}
181
182/// isPartialRedef - Return true if the specified def at the specific index is
183/// partially re-defining the specified live interval. A common case of this is
184/// a definition of the sub-register.
185bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
186                                   LiveInterval &interval) {
187  if (!MO.getSubReg() || MO.isEarlyClobber())
188    return false;
189
190  SlotIndex RedefIndex = MIIdx.getRegSlot();
191  const LiveRange *OldLR =
192    interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
193  MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
194  if (DefMI != 0) {
195    return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
196  }
197  return false;
198}
199
200void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
201                                             MachineBasicBlock::iterator mi,
202                                             SlotIndex MIIdx,
203                                             MachineOperand& MO,
204                                             unsigned MOIdx,
205                                             LiveInterval &interval) {
206  DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, TRI));
207
208  // Virtual registers may be defined multiple times (due to phi
209  // elimination and 2-addr elimination).  Much of what we do only has to be
210  // done once for the vreg.  We use an empty interval to detect the first
211  // time we see a vreg.
212  LiveVariables::VarInfo& vi = LV->getVarInfo(interval.reg);
213  if (interval.empty()) {
214    // Get the Idx of the defining instructions.
215    SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
216
217    // Make sure the first definition is not a partial redefinition.
218    assert(!MO.readsReg() && "First def cannot also read virtual register "
219           "missing <undef> flag?");
220
221    VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
222    assert(ValNo->id == 0 && "First value in interval is not 0?");
223
224    // Loop over all of the blocks that the vreg is defined in.  There are
225    // two cases we have to handle here.  The most common case is a vreg
226    // whose lifetime is contained within a basic block.  In this case there
227    // will be a single kill, in MBB, which comes after the definition.
228    if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
229      // FIXME: what about dead vars?
230      SlotIndex killIdx;
231      if (vi.Kills[0] != mi)
232        killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot();
233      else
234        killIdx = defIndex.getDeadSlot();
235
236      // If the kill happens after the definition, we have an intra-block
237      // live range.
238      if (killIdx > defIndex) {
239        assert(vi.AliveBlocks.empty() &&
240               "Shouldn't be alive across any blocks!");
241        LiveRange LR(defIndex, killIdx, ValNo);
242        interval.addRange(LR);
243        DEBUG(dbgs() << " +" << LR << "\n");
244        return;
245      }
246    }
247
248    // The other case we handle is when a virtual register lives to the end
249    // of the defining block, potentially live across some blocks, then is
250    // live into some number of blocks, but gets killed.  Start by adding a
251    // range that goes from this definition to the end of the defining block.
252    LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
253    DEBUG(dbgs() << " +" << NewLR);
254    interval.addRange(NewLR);
255
256    bool PHIJoin = LV->isPHIJoin(interval.reg);
257
258    if (PHIJoin) {
259      // A phi join register is killed at the end of the MBB and revived as a
260      // new valno in the killing blocks.
261      assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
262      DEBUG(dbgs() << " phi-join");
263    } else {
264      // Iterate over all of the blocks that the variable is completely
265      // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
266      // live interval.
267      for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
268               E = vi.AliveBlocks.end(); I != E; ++I) {
269        MachineBasicBlock *aliveBlock = MF->getBlockNumbered(*I);
270        LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock),
271                     ValNo);
272        interval.addRange(LR);
273        DEBUG(dbgs() << " +" << LR);
274      }
275    }
276
277    // Finally, this virtual register is live from the start of any killing
278    // block to the 'use' slot of the killing instruction.
279    for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
280      MachineInstr *Kill = vi.Kills[i];
281      SlotIndex Start = getMBBStartIdx(Kill->getParent());
282      SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot();
283
284      // Create interval with one of a NEW value number.  Note that this value
285      // number isn't actually defined by an instruction, weird huh? :)
286      if (PHIJoin) {
287        assert(getInstructionFromIndex(Start) == 0 &&
288               "PHI def index points at actual instruction.");
289        ValNo = interval.getNextValue(Start, VNInfoAllocator);
290      }
291      LiveRange LR(Start, killIdx, ValNo);
292      interval.addRange(LR);
293      DEBUG(dbgs() << " +" << LR);
294    }
295
296  } else {
297    if (MultipleDefsBySameMI(*mi, MOIdx))
298      // Multiple defs of the same virtual register by the same instruction.
299      // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
300      // This is likely due to elimination of REG_SEQUENCE instructions. Return
301      // here since there is nothing to do.
302      return;
303
304    // If this is the second time we see a virtual register definition, it
305    // must be due to phi elimination or two addr elimination.  If this is
306    // the result of two address elimination, then the vreg is one of the
307    // def-and-use register operand.
308
309    // It may also be partial redef like this:
310    // 80  %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
311    // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
312    bool PartReDef = isPartialRedef(MIIdx, MO, interval);
313    if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
314      // If this is a two-address definition, then we have already processed
315      // the live range.  The only problem is that we didn't realize there
316      // are actually two values in the live interval.  Because of this we
317      // need to take the LiveRegion that defines this register and split it
318      // into two values.
319      SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber());
320
321      const LiveRange *OldLR =
322        interval.getLiveRangeContaining(RedefIndex.getRegSlot(true));
323      VNInfo *OldValNo = OldLR->valno;
324      SlotIndex DefIndex = OldValNo->def.getRegSlot();
325
326      // Delete the previous value, which should be short and continuous,
327      // because the 2-addr copy must be in the same MBB as the redef.
328      interval.removeRange(DefIndex, RedefIndex);
329
330      // The new value number (#1) is defined by the instruction we claimed
331      // defined value #0.
332      VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
333
334      // Value#0 is now defined by the 2-addr instruction.
335      OldValNo->def = RedefIndex;
336
337      // Add the new live interval which replaces the range for the input copy.
338      LiveRange LR(DefIndex, RedefIndex, ValNo);
339      DEBUG(dbgs() << " replace range with " << LR);
340      interval.addRange(LR);
341
342      // If this redefinition is dead, we need to add a dummy unit live
343      // range covering the def slot.
344      if (MO.isDead())
345        interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(),
346                                    OldValNo));
347
348      DEBUG(dbgs() << " RESULT: " << interval);
349    } else if (LV->isPHIJoin(interval.reg)) {
350      // In the case of PHI elimination, each variable definition is only
351      // live until the end of the block.  We've already taken care of the
352      // rest of the live range.
353
354      SlotIndex defIndex = MIIdx.getRegSlot();
355      if (MO.isEarlyClobber())
356        defIndex = MIIdx.getRegSlot(true);
357
358      VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator);
359
360      SlotIndex killIndex = getMBBEndIdx(mbb);
361      LiveRange LR(defIndex, killIndex, ValNo);
362      interval.addRange(LR);
363      DEBUG(dbgs() << " phi-join +" << LR);
364    } else {
365      llvm_unreachable("Multiply defined register");
366    }
367  }
368
369  DEBUG(dbgs() << '\n');
370}
371
372void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
373                                      MachineBasicBlock::iterator MI,
374                                      SlotIndex MIIdx,
375                                      MachineOperand& MO,
376                                      unsigned MOIdx) {
377  if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
378    handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
379                             getOrCreateInterval(MO.getReg()));
380}
381
382/// computeIntervals - computes the live intervals for virtual
383/// registers. for some ordering of the machine instructions [1,N] a
384/// live interval is an interval [i, j) where 1 <= i <= j < N for
385/// which a variable is live
386void LiveIntervals::computeIntervals() {
387  DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
388               << "********** Function: " << MF->getName() << '\n');
389
390  RegMaskBlocks.resize(MF->getNumBlockIDs());
391
392  SmallVector<unsigned, 8> UndefUses;
393  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
394       MBBI != E; ++MBBI) {
395    MachineBasicBlock *MBB = MBBI;
396    RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size();
397
398    if (MBB->empty())
399      continue;
400
401    // Track the index of the current machine instr.
402    SlotIndex MIIndex = getMBBStartIdx(MBB);
403    DEBUG(dbgs() << "BB#" << MBB->getNumber()
404          << ":\t\t# derived from " << MBB->getName() << "\n");
405
406    // Skip over empty initial indices.
407    if (getInstructionFromIndex(MIIndex) == 0)
408      MIIndex = Indexes->getNextNonNullIndex(MIIndex);
409
410    for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
411         MI != miEnd; ++MI) {
412      DEBUG(dbgs() << MIIndex << "\t" << *MI);
413      if (MI->isDebugValue())
414        continue;
415      assert(Indexes->getInstructionFromIndex(MIIndex) == MI &&
416             "Lost SlotIndex synchronization");
417
418      // Handle defs.
419      for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
420        MachineOperand &MO = MI->getOperand(i);
421
422        // Collect register masks.
423        if (MO.isRegMask()) {
424          RegMaskSlots.push_back(MIIndex.getRegSlot());
425          RegMaskBits.push_back(MO.getRegMask());
426          continue;
427        }
428
429        if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
430          continue;
431
432        // handle register defs - build intervals
433        if (MO.isDef())
434          handleRegisterDef(MBB, MI, MIIndex, MO, i);
435        else if (MO.isUndef())
436          UndefUses.push_back(MO.getReg());
437      }
438
439      // Move to the next instr slot.
440      MIIndex = Indexes->getNextNonNullIndex(MIIndex);
441    }
442
443    // Compute the number of register mask instructions in this block.
444    std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
445    RMB.second = RegMaskSlots.size() - RMB.first;
446  }
447
448  // Create empty intervals for registers defined by implicit_def's (except
449  // for those implicit_def that define values which are liveout of their
450  // blocks.
451  for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
452    unsigned UndefReg = UndefUses[i];
453    (void)getOrCreateInterval(UndefReg);
454  }
455}
456
457LiveInterval* LiveIntervals::createInterval(unsigned reg) {
458  float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
459  return new LiveInterval(reg, Weight);
460}
461
462
463/// computeVirtRegInterval - Compute the live interval of a virtual register,
464/// based on defs and uses.
465void LiveIntervals::computeVirtRegInterval(LiveInterval *LI) {
466  assert(LRCalc && "LRCalc not initialized.");
467  assert(LI->empty() && "Should only compute empty intervals.");
468  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
469  LRCalc->createDeadDefs(LI);
470  LRCalc->extendToUses(LI);
471}
472
473void LiveIntervals::computeVirtRegs() {
474  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
475    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
476    if (MRI->reg_nodbg_empty(Reg))
477      continue;
478    LiveInterval *LI = createInterval(Reg);
479    VirtRegIntervals[Reg] = LI;
480    computeVirtRegInterval(LI);
481  }
482}
483
484void LiveIntervals::computeRegMasks() {
485  RegMaskBlocks.resize(MF->getNumBlockIDs());
486
487  // Find all instructions with regmask operands.
488  for (MachineFunction::iterator MBBI = MF->begin(), E = MF->end();
489       MBBI != E; ++MBBI) {
490    MachineBasicBlock *MBB = MBBI;
491    std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()];
492    RMB.first = RegMaskSlots.size();
493    for (MachineBasicBlock::iterator MI = MBB->begin(), ME = MBB->end();
494         MI != ME; ++MI)
495      for (MIOperands MO(MI); MO.isValid(); ++MO) {
496        if (!MO->isRegMask())
497          continue;
498          RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
499          RegMaskBits.push_back(MO->getRegMask());
500      }
501    // Compute the number of register mask instructions in this block.
502    RMB.second = RegMaskSlots.size() - RMB.first;
503  }
504}
505
506//===----------------------------------------------------------------------===//
507//                           Register Unit Liveness
508//===----------------------------------------------------------------------===//
509//
510// Fixed interference typically comes from ABI boundaries: Function arguments
511// and return values are passed in fixed registers, and so are exception
512// pointers entering landing pads. Certain instructions require values to be
513// present in specific registers. That is also represented through fixed
514// interference.
515//
516
517/// computeRegUnitInterval - Compute the live interval of a register unit, based
518/// on the uses and defs of aliasing registers.  The interval should be empty,
519/// or contain only dead phi-defs from ABI blocks.
520void LiveIntervals::computeRegUnitInterval(LiveInterval *LI) {
521  unsigned Unit = LI->reg;
522
523  assert(LRCalc && "LRCalc not initialized.");
524  LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
525
526  // The physregs aliasing Unit are the roots and their super-registers.
527  // Create all values as dead defs before extending to uses. Note that roots
528  // may share super-registers. That's OK because createDeadDefs() is
529  // idempotent. It is very rare for a register unit to have multiple roots, so
530  // uniquing super-registers is probably not worthwhile.
531  for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
532    unsigned Root = *Roots;
533    if (!MRI->reg_empty(Root))
534      LRCalc->createDeadDefs(LI, Root);
535    for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
536      if (!MRI->reg_empty(*Supers))
537        LRCalc->createDeadDefs(LI, *Supers);
538    }
539  }
540
541  // Now extend LI to reach all uses.
542  // Ignore uses of reserved registers. We only track defs of those.
543  for (MCRegUnitRootIterator Roots(Unit, TRI); Roots.isValid(); ++Roots) {
544    unsigned Root = *Roots;
545    if (!isReserved(Root) && !MRI->reg_empty(Root))
546      LRCalc->extendToUses(LI, Root);
547    for (MCSuperRegIterator Supers(Root, TRI); Supers.isValid(); ++Supers) {
548      unsigned Reg = *Supers;
549      if (!isReserved(Reg) && !MRI->reg_empty(Reg))
550        LRCalc->extendToUses(LI, Reg);
551    }
552  }
553}
554
555
556/// computeLiveInRegUnits - Precompute the live ranges of any register units
557/// that are live-in to an ABI block somewhere. Register values can appear
558/// without a corresponding def when entering the entry block or a landing pad.
559///
560void LiveIntervals::computeLiveInRegUnits() {
561  RegUnitIntervals.resize(TRI->getNumRegUnits());
562  DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
563
564  // Keep track of the intervals allocated.
565  SmallVector<LiveInterval*, 8> NewIntvs;
566
567  // Check all basic blocks for live-ins.
568  for (MachineFunction::const_iterator MFI = MF->begin(), MFE = MF->end();
569       MFI != MFE; ++MFI) {
570    const MachineBasicBlock *MBB = MFI;
571
572    // We only care about ABI blocks: Entry + landing pads.
573    if ((MFI != MF->begin() && !MBB->isLandingPad()) || MBB->livein_empty())
574      continue;
575
576    // Create phi-defs at Begin for all live-in registers.
577    SlotIndex Begin = Indexes->getMBBStartIdx(MBB);
578    DEBUG(dbgs() << Begin << "\tBB#" << MBB->getNumber());
579    for (MachineBasicBlock::livein_iterator LII = MBB->livein_begin(),
580         LIE = MBB->livein_end(); LII != LIE; ++LII) {
581      for (MCRegUnitIterator Units(*LII, TRI); Units.isValid(); ++Units) {
582        unsigned Unit = *Units;
583        LiveInterval *Intv = RegUnitIntervals[Unit];
584        if (!Intv) {
585          Intv = RegUnitIntervals[Unit] = new LiveInterval(Unit, HUGE_VALF);
586          NewIntvs.push_back(Intv);
587        }
588        VNInfo *VNI = Intv->createDeadDef(Begin, getVNInfoAllocator());
589        (void)VNI;
590        DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
591      }
592    }
593    DEBUG(dbgs() << '\n');
594  }
595  DEBUG(dbgs() << "Created " << NewIntvs.size() << " new intervals.\n");
596
597  // Compute the 'normal' part of the intervals.
598  for (unsigned i = 0, e = NewIntvs.size(); i != e; ++i)
599    computeRegUnitInterval(NewIntvs[i]);
600}
601
602
603/// shrinkToUses - After removing some uses of a register, shrink its live
604/// range to just the remaining uses. This method does not compute reaching
605/// defs for new uses, and it doesn't remove dead defs.
606bool LiveIntervals::shrinkToUses(LiveInterval *li,
607                                 SmallVectorImpl<MachineInstr*> *dead) {
608  DEBUG(dbgs() << "Shrink: " << *li << '\n');
609  assert(TargetRegisterInfo::isVirtualRegister(li->reg)
610         && "Can only shrink virtual registers");
611  // Find all the values used, including PHI kills.
612  SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
613
614  // Blocks that have already been added to WorkList as live-out.
615  SmallPtrSet<MachineBasicBlock*, 16> LiveOut;
616
617  // Visit all instructions reading li->reg.
618  for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(li->reg);
619       MachineInstr *UseMI = I.skipInstruction();) {
620    if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
621      continue;
622    SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
623    LiveRangeQuery LRQ(*li, Idx);
624    VNInfo *VNI = LRQ.valueIn();
625    if (!VNI) {
626      // This shouldn't happen: readsVirtualRegister returns true, but there is
627      // no live value. It is likely caused by a target getting <undef> flags
628      // wrong.
629      DEBUG(dbgs() << Idx << '\t' << *UseMI
630                   << "Warning: Instr claims to read non-existent value in "
631                    << *li << '\n');
632      continue;
633    }
634    // Special case: An early-clobber tied operand reads and writes the
635    // register one slot early.
636    if (VNInfo *DefVNI = LRQ.valueDefined())
637      Idx = DefVNI->def;
638
639    WorkList.push_back(std::make_pair(Idx, VNI));
640  }
641
642  // Create a new live interval with only minimal live segments per def.
643  LiveInterval NewLI(li->reg, 0);
644  for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
645       I != E; ++I) {
646    VNInfo *VNI = *I;
647    if (VNI->isUnused())
648      continue;
649    NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI));
650  }
651
652  // Keep track of the PHIs that are in use.
653  SmallPtrSet<VNInfo*, 8> UsedPHIs;
654
655  // Extend intervals to reach all uses in WorkList.
656  while (!WorkList.empty()) {
657    SlotIndex Idx = WorkList.back().first;
658    VNInfo *VNI = WorkList.back().second;
659    WorkList.pop_back();
660    const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot());
661    SlotIndex BlockStart = getMBBStartIdx(MBB);
662
663    // Extend the live range for VNI to be live at Idx.
664    if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
665      (void)ExtVNI;
666      assert(ExtVNI == VNI && "Unexpected existing value number");
667      // Is this a PHIDef we haven't seen before?
668      if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
669        continue;
670      // The PHI is live, make sure the predecessors are live-out.
671      for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
672           PE = MBB->pred_end(); PI != PE; ++PI) {
673        if (!LiveOut.insert(*PI))
674          continue;
675        SlotIndex Stop = getMBBEndIdx(*PI);
676        // A predecessor is not required to have a live-out value for a PHI.
677        if (VNInfo *PVNI = li->getVNInfoBefore(Stop))
678          WorkList.push_back(std::make_pair(Stop, PVNI));
679      }
680      continue;
681    }
682
683    // VNI is live-in to MBB.
684    DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
685    NewLI.addRange(LiveRange(BlockStart, Idx, VNI));
686
687    // Make sure VNI is live-out from the predecessors.
688    for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
689         PE = MBB->pred_end(); PI != PE; ++PI) {
690      if (!LiveOut.insert(*PI))
691        continue;
692      SlotIndex Stop = getMBBEndIdx(*PI);
693      assert(li->getVNInfoBefore(Stop) == VNI &&
694             "Wrong value out of predecessor");
695      WorkList.push_back(std::make_pair(Stop, VNI));
696    }
697  }
698
699  // Handle dead values.
700  bool CanSeparate = false;
701  for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
702       I != E; ++I) {
703    VNInfo *VNI = *I;
704    if (VNI->isUnused())
705      continue;
706    LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
707    assert(LII != NewLI.end() && "Missing live range for PHI");
708    if (LII->end != VNI->def.getDeadSlot())
709      continue;
710    if (VNI->isPHIDef()) {
711      // This is a dead PHI. Remove it.
712      VNI->markUnused();
713      NewLI.removeRange(*LII);
714      DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
715      CanSeparate = true;
716    } else {
717      // This is a dead def. Make sure the instruction knows.
718      MachineInstr *MI = getInstructionFromIndex(VNI->def);
719      assert(MI && "No instruction defining live value");
720      MI->addRegisterDead(li->reg, TRI);
721      if (dead && MI->allDefsAreDead()) {
722        DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
723        dead->push_back(MI);
724      }
725    }
726  }
727
728  // Move the trimmed ranges back.
729  li->ranges.swap(NewLI.ranges);
730  DEBUG(dbgs() << "Shrunk: " << *li << '\n');
731  return CanSeparate;
732}
733
734
735//===----------------------------------------------------------------------===//
736// Register allocator hooks.
737//
738
739void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
740  // Keep track of regunit ranges.
741  SmallVector<std::pair<LiveInterval*, LiveInterval::iterator>, 8> RU;
742
743  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
744    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
745    if (MRI->reg_nodbg_empty(Reg))
746      continue;
747    LiveInterval *LI = &getInterval(Reg);
748    if (LI->empty())
749      continue;
750
751    // Find the regunit intervals for the assigned register. They may overlap
752    // the virtual register live range, cancelling any kills.
753    RU.clear();
754    for (MCRegUnitIterator Units(VRM->getPhys(Reg), TRI); Units.isValid();
755         ++Units) {
756      LiveInterval *RUInt = &getRegUnit(*Units);
757      if (RUInt->empty())
758        continue;
759      RU.push_back(std::make_pair(RUInt, RUInt->find(LI->begin()->end)));
760    }
761
762    // Every instruction that kills Reg corresponds to a live range end point.
763    for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
764         ++RI) {
765      // A block index indicates an MBB edge.
766      if (RI->end.isBlock())
767        continue;
768      MachineInstr *MI = getInstructionFromIndex(RI->end);
769      if (!MI)
770        continue;
771
772      // Check if any of the reguints are live beyond the end of RI. That could
773      // happen when a physreg is defined as a copy of a virtreg:
774      //
775      //   %EAX = COPY %vreg5
776      //   FOO %vreg5         <--- MI, cancel kill because %EAX is live.
777      //   BAR %EAX<kill>
778      //
779      // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
780      bool CancelKill = false;
781      for (unsigned u = 0, e = RU.size(); u != e; ++u) {
782        LiveInterval *RInt = RU[u].first;
783        LiveInterval::iterator &I = RU[u].second;
784        if (I == RInt->end())
785          continue;
786        I = RInt->advanceTo(I, RI->end);
787        if (I == RInt->end() || I->start >= RI->end)
788          continue;
789        // I is overlapping RI.
790        CancelKill = true;
791        break;
792      }
793      if (CancelKill)
794        MI->clearRegisterKills(Reg, NULL);
795      else
796        MI->addRegisterKilled(Reg, NULL);
797    }
798  }
799}
800
801MachineBasicBlock*
802LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
803  // A local live range must be fully contained inside the block, meaning it is
804  // defined and killed at instructions, not at block boundaries. It is not
805  // live in or or out of any block.
806  //
807  // It is technically possible to have a PHI-defined live range identical to a
808  // single block, but we are going to return false in that case.
809
810  SlotIndex Start = LI.beginIndex();
811  if (Start.isBlock())
812    return NULL;
813
814  SlotIndex Stop = LI.endIndex();
815  if (Stop.isBlock())
816    return NULL;
817
818  // getMBBFromIndex doesn't need to search the MBB table when both indexes
819  // belong to proper instructions.
820  MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
821  MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
822  return MBB1 == MBB2 ? MBB1 : NULL;
823}
824
825bool
826LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
827  for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
828       I != E; ++I) {
829    const VNInfo *PHI = *I;
830    if (PHI->isUnused() || !PHI->isPHIDef())
831      continue;
832    const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
833    // Conservatively return true instead of scanning huge predecessor lists.
834    if (PHIMBB->pred_size() > 100)
835      return true;
836    for (MachineBasicBlock::const_pred_iterator
837         PI = PHIMBB->pred_begin(), PE = PHIMBB->pred_end(); PI != PE; ++PI)
838      if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(*PI)))
839        return true;
840  }
841  return false;
842}
843
844float
845LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
846  // Limit the loop depth ridiculousness.
847  if (loopDepth > 200)
848    loopDepth = 200;
849
850  // The loop depth is used to roughly estimate the number of times the
851  // instruction is executed. Something like 10^d is simple, but will quickly
852  // overflow a float. This expression behaves like 10^d for small d, but is
853  // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
854  // headroom before overflow.
855  // By the way, powf() might be unavailable here. For consistency,
856  // We may take pow(double,double).
857  float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
858
859  return (isDef + isUse) * lc;
860}
861
862LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
863                                                  MachineInstr* startInst) {
864  LiveInterval& Interval = getOrCreateInterval(reg);
865  VNInfo* VN = Interval.getNextValue(
866    SlotIndex(getInstructionIndex(startInst).getRegSlot()),
867    getVNInfoAllocator());
868  LiveRange LR(
869     SlotIndex(getInstructionIndex(startInst).getRegSlot()),
870     getMBBEndIdx(startInst->getParent()), VN);
871  Interval.addRange(LR);
872
873  return LR;
874}
875
876
877//===----------------------------------------------------------------------===//
878//                          Register mask functions
879//===----------------------------------------------------------------------===//
880
881bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
882                                             BitVector &UsableRegs) {
883  if (LI.empty())
884    return false;
885  LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
886
887  // Use a smaller arrays for local live ranges.
888  ArrayRef<SlotIndex> Slots;
889  ArrayRef<const uint32_t*> Bits;
890  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
891    Slots = getRegMaskSlotsInBlock(MBB->getNumber());
892    Bits = getRegMaskBitsInBlock(MBB->getNumber());
893  } else {
894    Slots = getRegMaskSlots();
895    Bits = getRegMaskBits();
896  }
897
898  // We are going to enumerate all the register mask slots contained in LI.
899  // Start with a binary search of RegMaskSlots to find a starting point.
900  ArrayRef<SlotIndex>::iterator SlotI =
901    std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
902  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
903
904  // No slots in range, LI begins after the last call.
905  if (SlotI == SlotE)
906    return false;
907
908  bool Found = false;
909  for (;;) {
910    assert(*SlotI >= LiveI->start);
911    // Loop over all slots overlapping this segment.
912    while (*SlotI < LiveI->end) {
913      // *SlotI overlaps LI. Collect mask bits.
914      if (!Found) {
915        // This is the first overlap. Initialize UsableRegs to all ones.
916        UsableRegs.clear();
917        UsableRegs.resize(TRI->getNumRegs(), true);
918        Found = true;
919      }
920      // Remove usable registers clobbered by this mask.
921      UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
922      if (++SlotI == SlotE)
923        return Found;
924    }
925    // *SlotI is beyond the current LI segment.
926    LiveI = LI.advanceTo(LiveI, *SlotI);
927    if (LiveI == LiveE)
928      return Found;
929    // Advance SlotI until it overlaps.
930    while (*SlotI < LiveI->start)
931      if (++SlotI == SlotE)
932        return Found;
933  }
934}
935
936//===----------------------------------------------------------------------===//
937//                         IntervalUpdate class.
938//===----------------------------------------------------------------------===//
939
940// HMEditor is a toolkit used by handleMove to trim or extend live intervals.
941class LiveIntervals::HMEditor {
942private:
943  LiveIntervals& LIS;
944  const MachineRegisterInfo& MRI;
945  const TargetRegisterInfo& TRI;
946  SlotIndex NewIdx;
947
948  typedef std::pair<LiveInterval*, LiveRange*> IntRangePair;
949  typedef DenseSet<IntRangePair> RangeSet;
950
951  struct RegRanges {
952    LiveRange* Use;
953    LiveRange* EC;
954    LiveRange* Dead;
955    LiveRange* Def;
956    RegRanges() : Use(0), EC(0), Dead(0), Def(0) {}
957  };
958  typedef DenseMap<unsigned, RegRanges> BundleRanges;
959
960public:
961  HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
962           const TargetRegisterInfo& TRI, SlotIndex NewIdx)
963    : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {}
964
965  // Update intervals for all operands of MI from OldIdx to NewIdx.
966  // This assumes that MI used to be at OldIdx, and now resides at
967  // NewIdx.
968  void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) {
969    assert(NewIdx != OldIdx && "No-op move? That's a bit strange.");
970
971    // Collect the operands.
972    RangeSet Entering, Internal, Exiting;
973    bool hasRegMaskOp = false;
974    collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
975
976    // To keep the LiveRanges valid within an interval, move the ranges closest
977    // to the destination first. This prevents ranges from overlapping, to that
978    // APIs like removeRange still work.
979    if (NewIdx < OldIdx) {
980      moveAllEnteringFrom(OldIdx, Entering);
981      moveAllInternalFrom(OldIdx, Internal);
982      moveAllExitingFrom(OldIdx, Exiting);
983    }
984    else {
985      moveAllExitingFrom(OldIdx, Exiting);
986      moveAllInternalFrom(OldIdx, Internal);
987      moveAllEnteringFrom(OldIdx, Entering);
988    }
989
990    if (hasRegMaskOp)
991      updateRegMaskSlots(OldIdx);
992
993#ifndef NDEBUG
994    LIValidator validator;
995    validator = std::for_each(Entering.begin(), Entering.end(), validator);
996    validator = std::for_each(Internal.begin(), Internal.end(), validator);
997    validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
998    assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness.");
999#endif
1000
1001  }
1002
1003  // Update intervals for all operands of MI to refer to BundleStart's
1004  // SlotIndex.
1005  void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) {
1006    if (MI == BundleStart)
1007      return; // Bundling instr with itself - nothing to do.
1008
1009    SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI);
1010    assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI &&
1011           "SlotIndex <-> Instruction mapping broken for MI");
1012
1013    // Collect all ranges already in the bundle.
1014    MachineBasicBlock::instr_iterator BII(BundleStart);
1015    RangeSet Entering, Internal, Exiting;
1016    bool hasRegMaskOp = false;
1017    collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
1018    assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
1019    for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) {
1020      if (&*BII == MI)
1021        continue;
1022      collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx);
1023      assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
1024    }
1025
1026    BundleRanges BR = createBundleRanges(Entering, Internal, Exiting);
1027
1028    Entering.clear();
1029    Internal.clear();
1030    Exiting.clear();
1031    collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx);
1032    assert(!hasRegMaskOp && "Can't have RegMask operand in bundle.");
1033
1034    DEBUG(dbgs() << "Entering: " << Entering.size() << "\n");
1035    DEBUG(dbgs() << "Internal: " << Internal.size() << "\n");
1036    DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n");
1037
1038    moveAllEnteringFromInto(OldIdx, Entering, BR);
1039    moveAllInternalFromInto(OldIdx, Internal, BR);
1040    moveAllExitingFromInto(OldIdx, Exiting, BR);
1041
1042
1043#ifndef NDEBUG
1044    LIValidator validator;
1045    validator = std::for_each(Entering.begin(), Entering.end(), validator);
1046    validator = std::for_each(Internal.begin(), Internal.end(), validator);
1047    validator = std::for_each(Exiting.begin(), Exiting.end(), validator);
1048    assert(validator.rangesOk() && "moveAllOperandsInto broke liveness.");
1049#endif
1050  }
1051
1052private:
1053
1054#ifndef NDEBUG
1055  class LIValidator {
1056  private:
1057    DenseSet<const LiveInterval*> Checked, Bogus;
1058  public:
1059    void operator()(const IntRangePair& P) {
1060      const LiveInterval* LI = P.first;
1061      if (Checked.count(LI))
1062        return;
1063      Checked.insert(LI);
1064      if (LI->empty())
1065        return;
1066      SlotIndex LastEnd = LI->begin()->start;
1067      for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end();
1068           LRI != LRE; ++LRI) {
1069        const LiveRange& LR = *LRI;
1070        if (LastEnd > LR.start || LR.start >= LR.end)
1071          Bogus.insert(LI);
1072        LastEnd = LR.end;
1073      }
1074    }
1075
1076    bool rangesOk() const {
1077      return Bogus.empty();
1078    }
1079  };
1080#endif
1081
1082  // Collect IntRangePairs for all operands of MI that may need fixing.
1083  // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes'
1084  // maps).
1085  void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal,
1086                     RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) {
1087    hasRegMaskOp = false;
1088    for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
1089                                    MOE = MI->operands_end();
1090         MOI != MOE; ++MOI) {
1091      const MachineOperand& MO = *MOI;
1092
1093      if (MO.isRegMask()) {
1094        hasRegMaskOp = true;
1095        continue;
1096      }
1097
1098      if (!MO.isReg() || MO.getReg() == 0)
1099        continue;
1100
1101      unsigned Reg = MO.getReg();
1102
1103      // TODO: Currently we're skipping uses that are reserved or have no
1104      // interval, but we're not updating their kills. This should be
1105      // fixed.
1106      if (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))
1107        continue;
1108
1109      // Collect ranges for register units. These live ranges are computed on
1110      // demand, so just skip any that haven't been computed yet.
1111      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
1112        for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
1113          if (LiveInterval *LI = LIS.getCachedRegUnit(*Units))
1114            collectRanges(MO, LI, Entering, Internal, Exiting, OldIdx);
1115      } else {
1116        // Collect ranges for individual virtual registers.
1117        collectRanges(MO, &LIS.getInterval(Reg),
1118                      Entering, Internal, Exiting, OldIdx);
1119      }
1120    }
1121  }
1122
1123  void collectRanges(const MachineOperand &MO, LiveInterval *LI,
1124                     RangeSet &Entering, RangeSet &Internal, RangeSet &Exiting,
1125                     SlotIndex OldIdx) {
1126    if (MO.readsReg()) {
1127      LiveRange* LR = LI->getLiveRangeContaining(OldIdx);
1128      if (LR != 0)
1129        Entering.insert(std::make_pair(LI, LR));
1130    }
1131    if (MO.isDef()) {
1132      LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot());
1133      assert(LR != 0 && "No live range for def?");
1134      if (LR->end > OldIdx.getDeadSlot())
1135        Exiting.insert(std::make_pair(LI, LR));
1136      else
1137        Internal.insert(std::make_pair(LI, LR));
1138    }
1139  }
1140
1141  BundleRanges createBundleRanges(RangeSet& Entering,
1142                                  RangeSet& Internal,
1143                                  RangeSet& Exiting) {
1144    BundleRanges BR;
1145
1146    for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1147         EI != EE; ++EI) {
1148      LiveInterval* LI = EI->first;
1149      LiveRange* LR = EI->second;
1150      BR[LI->reg].Use = LR;
1151    }
1152
1153    for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1154         II != IE; ++II) {
1155      LiveInterval* LI = II->first;
1156      LiveRange* LR = II->second;
1157      if (LR->end.isDead()) {
1158        BR[LI->reg].Dead = LR;
1159      } else {
1160        BR[LI->reg].EC = LR;
1161      }
1162    }
1163
1164    for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1165         EI != EE; ++EI) {
1166      LiveInterval* LI = EI->first;
1167      LiveRange* LR = EI->second;
1168      BR[LI->reg].Def = LR;
1169    }
1170
1171    return BR;
1172  }
1173
1174  void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) {
1175    MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx);
1176    if (!OldKillMI->killsRegister(reg))
1177      return; // Bail out if we don't have kill flags on the old register.
1178    MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx);
1179    assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill.");
1180    assert(!NewKillMI->killsRegister(reg) &&
1181           "New kill instr is already a kill.");
1182    OldKillMI->clearRegisterKills(reg, &TRI);
1183    NewKillMI->addRegisterKilled(reg, &TRI);
1184  }
1185
1186  void updateRegMaskSlots(SlotIndex OldIdx) {
1187    SmallVectorImpl<SlotIndex>::iterator RI =
1188      std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
1189                       OldIdx);
1190    assert(*RI == OldIdx && "No RegMask at OldIdx.");
1191    *RI = NewIdx;
1192    assert(*prior(RI) < *RI && *RI < *next(RI) &&
1193           "RegSlots out of order. Did you move one call across another?");
1194  }
1195
1196  // Return the last use of reg between NewIdx and OldIdx.
1197  SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) {
1198    SlotIndex LastUse = NewIdx;
1199    for (MachineRegisterInfo::use_nodbg_iterator
1200           UI = MRI.use_nodbg_begin(Reg),
1201           UE = MRI.use_nodbg_end();
1202         UI != UE; UI.skipInstruction()) {
1203      const MachineInstr* MI = &*UI;
1204      SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
1205      if (InstSlot > LastUse && InstSlot < OldIdx)
1206        LastUse = InstSlot;
1207    }
1208    return LastUse;
1209  }
1210
1211  void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) {
1212    LiveInterval* LI = P.first;
1213    LiveRange* LR = P.second;
1214    bool LiveThrough = LR->end > OldIdx.getRegSlot();
1215    if (LiveThrough)
1216      return;
1217    SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
1218    if (LastUse != NewIdx)
1219      moveKillFlags(LI->reg, NewIdx, LastUse);
1220    LR->end = LastUse.getRegSlot(LR->end.isEarlyClobber());
1221  }
1222
1223  void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) {
1224    LiveInterval* LI = P.first;
1225    LiveRange* LR = P.second;
1226    // Extend the LiveRange if NewIdx is past the end.
1227    if (NewIdx > LR->end) {
1228      // Move kill flags if OldIdx was not originally the end
1229      // (otherwise LR->end points to an invalid slot).
1230      if (LR->end.getRegSlot() != OldIdx.getRegSlot()) {
1231        assert(LR->end > OldIdx && "LiveRange does not cover original slot");
1232        moveKillFlags(LI->reg, LR->end, NewIdx);
1233      }
1234      LR->end = NewIdx.getRegSlot(LR->end.isEarlyClobber());
1235    }
1236  }
1237
1238  void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) {
1239    bool GoingUp = NewIdx < OldIdx;
1240
1241    if (GoingUp) {
1242      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1243           EI != EE; ++EI)
1244        moveEnteringUpFrom(OldIdx, *EI);
1245    } else {
1246      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1247           EI != EE; ++EI)
1248        moveEnteringDownFrom(OldIdx, *EI);
1249    }
1250  }
1251
1252  void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) {
1253    LiveInterval* LI = P.first;
1254    LiveRange* LR = P.second;
1255    assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
1256           LR->end <= OldIdx.getDeadSlot() &&
1257           "Range should be internal to OldIdx.");
1258    LiveRange Tmp(*LR);
1259    Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber());
1260    Tmp.valno->def = Tmp.start;
1261    Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot();
1262    LI->removeRange(*LR);
1263    LI->addRange(Tmp);
1264  }
1265
1266  void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) {
1267    for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1268         II != IE; ++II)
1269      moveInternalFrom(OldIdx, *II);
1270  }
1271
1272  void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) {
1273    LiveRange* LR = P.second;
1274    assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() &&
1275           "Range should start in OldIdx.");
1276    assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx.");
1277    SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber());
1278    LR->start = NewStart;
1279    LR->valno->def = NewStart;
1280  }
1281
1282  void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) {
1283    for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1284         EI != EE; ++EI)
1285      moveExitingFrom(OldIdx, *EI);
1286  }
1287
1288  void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P,
1289                              BundleRanges& BR) {
1290    LiveInterval* LI = P.first;
1291    LiveRange* LR = P.second;
1292    bool LiveThrough = LR->end > OldIdx.getRegSlot();
1293    if (LiveThrough) {
1294      assert((LR->start < NewIdx || BR[LI->reg].Def == LR) &&
1295             "Def in bundle should be def range.");
1296      assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
1297             "If bundle has use for this reg it should be LR.");
1298      BR[LI->reg].Use = LR;
1299      return;
1300    }
1301
1302    SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx);
1303    moveKillFlags(LI->reg, OldIdx, LastUse);
1304
1305    if (LR->start < NewIdx) {
1306      // Becoming a new entering range.
1307      assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 &&
1308             "Bundle shouldn't be re-defining reg mid-range.");
1309      assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) &&
1310             "Bundle shouldn't have different use range for same reg.");
1311      LR->end = LastUse.getRegSlot();
1312      BR[LI->reg].Use = LR;
1313    } else {
1314      // Becoming a new Dead-def.
1315      assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) &&
1316             "Live range starting at unexpected slot.");
1317      assert(BR[LI->reg].Def == LR && "Reg should have def range.");
1318      assert(BR[LI->reg].Dead == 0 &&
1319               "Can't have def and dead def of same reg in a bundle.");
1320      LR->end = LastUse.getDeadSlot();
1321      BR[LI->reg].Dead = BR[LI->reg].Def;
1322      BR[LI->reg].Def = 0;
1323    }
1324  }
1325
1326  void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P,
1327                                BundleRanges& BR) {
1328    LiveInterval* LI = P.first;
1329    LiveRange* LR = P.second;
1330    if (NewIdx > LR->end) {
1331      // Range extended to bundle. Add to bundle uses.
1332      // Note: Currently adds kill flags to bundle start.
1333      assert(BR[LI->reg].Use == 0 &&
1334             "Bundle already has use range for reg.");
1335      moveKillFlags(LI->reg, LR->end, NewIdx);
1336      LR->end = NewIdx.getRegSlot();
1337      BR[LI->reg].Use = LR;
1338    } else {
1339      assert(BR[LI->reg].Use != 0 &&
1340             "Bundle should already have a use range for reg.");
1341    }
1342  }
1343
1344  void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering,
1345                               BundleRanges& BR) {
1346    bool GoingUp = NewIdx < OldIdx;
1347
1348    if (GoingUp) {
1349      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1350           EI != EE; ++EI)
1351        moveEnteringUpFromInto(OldIdx, *EI, BR);
1352    } else {
1353      for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end();
1354           EI != EE; ++EI)
1355        moveEnteringDownFromInto(OldIdx, *EI, BR);
1356    }
1357  }
1358
1359  void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P,
1360                            BundleRanges& BR) {
1361    // TODO: Sane rules for moving ranges into bundles.
1362  }
1363
1364  void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal,
1365                               BundleRanges& BR) {
1366    for (RangeSet::iterator II = Internal.begin(), IE = Internal.end();
1367         II != IE; ++II)
1368      moveInternalFromInto(OldIdx, *II, BR);
1369  }
1370
1371  void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P,
1372                           BundleRanges& BR) {
1373    LiveInterval* LI = P.first;
1374    LiveRange* LR = P.second;
1375
1376    assert(LR->start.isRegister() &&
1377           "Don't know how to merge exiting ECs into bundles yet.");
1378
1379    if (LR->end > NewIdx.getDeadSlot()) {
1380      // This range is becoming an exiting range on the bundle.
1381      // If there was an old dead-def of this reg, delete it.
1382      if (BR[LI->reg].Dead != 0) {
1383        LI->removeRange(*BR[LI->reg].Dead);
1384        BR[LI->reg].Dead = 0;
1385      }
1386      assert(BR[LI->reg].Def == 0 &&
1387             "Can't have two defs for the same variable exiting a bundle.");
1388      LR->start = NewIdx.getRegSlot();
1389      LR->valno->def = LR->start;
1390      BR[LI->reg].Def = LR;
1391    } else {
1392      // This range is becoming internal to the bundle.
1393      assert(LR->end == NewIdx.getRegSlot() &&
1394             "Can't bundle def whose kill is before the bundle");
1395      if (BR[LI->reg].Dead || BR[LI->reg].Def) {
1396        // Already have a def for this. Just delete range.
1397        LI->removeRange(*LR);
1398      } else {
1399        // Make range dead, record.
1400        LR->end = NewIdx.getDeadSlot();
1401        BR[LI->reg].Dead = LR;
1402        assert(BR[LI->reg].Use == LR &&
1403               "Range becoming dead should currently be use.");
1404      }
1405      // In both cases the range is no longer a use on the bundle.
1406      BR[LI->reg].Use = 0;
1407    }
1408  }
1409
1410  void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting,
1411                              BundleRanges& BR) {
1412    for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end();
1413         EI != EE; ++EI)
1414      moveExitingFromInto(OldIdx, *EI, BR);
1415  }
1416
1417};
1418
1419void LiveIntervals::handleMove(MachineInstr* MI) {
1420  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
1421  Indexes->removeMachineInstrFromMaps(MI);
1422  SlotIndex NewIndex = MI->isInsideBundle() ?
1423                        Indexes->getInstructionIndex(MI) :
1424                        Indexes->insertMachineInstrInMaps(MI);
1425  assert(getMBBStartIdx(MI->getParent()) <= OldIndex &&
1426         OldIndex < getMBBEndIdx(MI->getParent()) &&
1427         "Cannot handle moves across basic block boundaries.");
1428  assert(!MI->isBundled() && "Can't handle bundled instructions yet.");
1429
1430  HMEditor HME(*this, *MRI, *TRI, NewIndex);
1431  HME.moveAllRangesFrom(MI, OldIndex);
1432}
1433
1434void LiveIntervals::handleMoveIntoBundle(MachineInstr* MI,
1435                                         MachineInstr* BundleStart) {
1436  SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
1437  HMEditor HME(*this, *MRI, *TRI, NewIndex);
1438  HME.moveAllRangesInto(MI, BundleStart);
1439}
1440