LiveIntervalAnalysis.cpp revision ab847242976b8e7c495308f8b771ae5d0db8b340 
1//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source 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 "liveintervals"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "VirtRegMap.h"
21#include "llvm/Value.h"
22#include "llvm/CodeGen/LiveVariables.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/Passes.h"
26#include "llvm/CodeGen/SSARegMap.h"
27#include "llvm/Target/MRegisterInfo.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/ADT/Statistic.h"
33#include "llvm/ADT/STLExtras.h"
34#include <algorithm>
35#include <cmath>
36using namespace llvm;
37
38namespace {
39  // Hidden options for help debugging.
40  cl::opt<bool> DisableReMat("disable-rematerialization",
41                              cl::init(false), cl::Hidden);
42}
43
44STATISTIC(numIntervals, "Number of original intervals");
45STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
46STATISTIC(numFolded   , "Number of loads/stores folded into instructions");
47
48char LiveIntervals::ID = 0;
49namespace {
50  RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
51}
52
53void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
54  AU.addPreserved<LiveVariables>();
55  AU.addRequired<LiveVariables>();
56  AU.addPreservedID(PHIEliminationID);
57  AU.addRequiredID(PHIEliminationID);
58  AU.addRequiredID(TwoAddressInstructionPassID);
59  MachineFunctionPass::getAnalysisUsage(AU);
60}
61
62void LiveIntervals::releaseMemory() {
63  Idx2MBBMap.clear();
64  mi2iMap_.clear();
65  i2miMap_.clear();
66  r2iMap_.clear();
67  // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
68  VNInfoAllocator.Reset();
69  for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
70    delete ClonedMIs[i];
71}
72
73namespace llvm {
74  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
75    return V < IM.first;
76  }
77
78  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
79    return IM.first < V;
80  }
81
82  struct Idx2MBBCompare {
83    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
84      return LHS.first < RHS.first;
85    }
86  };
87}
88
89/// runOnMachineFunction - Register allocate the whole function
90///
91bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
92  mf_ = &fn;
93  tm_ = &fn.getTarget();
94  mri_ = tm_->getRegisterInfo();
95  tii_ = tm_->getInstrInfo();
96  lv_ = &getAnalysis<LiveVariables>();
97  allocatableRegs_ = mri_->getAllocatableSet(fn);
98
99  // Number MachineInstrs and MachineBasicBlocks.
100  // Initialize MBB indexes to a sentinal.
101  MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
102
103  unsigned MIIndex = 0;
104  for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
105       MBB != E; ++MBB) {
106    unsigned StartIdx = MIIndex;
107
108    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
109         I != E; ++I) {
110      bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
111      assert(inserted && "multiple MachineInstr -> index mappings");
112      i2miMap_.push_back(I);
113      MIIndex += InstrSlots::NUM;
114    }
115
116    // Set the MBB2IdxMap entry for this MBB.
117    MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
118    Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
119  }
120  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
121
122  computeIntervals();
123
124  numIntervals += getNumIntervals();
125
126  DOUT << "********** INTERVALS **********\n";
127  for (iterator I = begin(), E = end(); I != E; ++I) {
128    I->second.print(DOUT, mri_);
129    DOUT << "\n";
130  }
131
132  numIntervalsAfter += getNumIntervals();
133  DEBUG(dump());
134  return true;
135}
136
137/// print - Implement the dump method.
138void LiveIntervals::print(std::ostream &O, const Module* ) const {
139  O << "********** INTERVALS **********\n";
140  for (const_iterator I = begin(), E = end(); I != E; ++I) {
141    I->second.print(DOUT, mri_);
142    DOUT << "\n";
143  }
144
145  O << "********** MACHINEINSTRS **********\n";
146  for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
147       mbbi != mbbe; ++mbbi) {
148    O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
149    for (MachineBasicBlock::iterator mii = mbbi->begin(),
150           mie = mbbi->end(); mii != mie; ++mii) {
151      O << getInstructionIndex(mii) << '\t' << *mii;
152    }
153  }
154}
155
156/// isReMaterializable - Returns true if the definition MI of the specified
157/// val# of the specified interval is re-materializable.
158bool LiveIntervals::isReMaterializable(const LiveInterval &li,
159                                       const VNInfo *ValNo, MachineInstr *MI) {
160  if (DisableReMat)
161    return false;
162
163  if (tii_->isTriviallyReMaterializable(MI))
164    return true;
165
166  int FrameIdx = 0;
167  if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
168      !mf_->getFrameInfo()->isFixedObjectIndex(FrameIdx))
169    return false;
170
171  // This is a load from fixed stack slot. It can be rematerialized unless it's
172  // re-defined by a two-address instruction.
173  for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
174       i != e; ++i) {
175    const VNInfo *VNI = *i;
176    if (VNI == ValNo)
177      continue;
178    unsigned DefIdx = VNI->def;
179    if (DefIdx == ~1U)
180      continue; // Dead val#.
181    MachineInstr *DefMI = (DefIdx == ~0u)
182      ? NULL : getInstructionFromIndex(DefIdx);
183    if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg))
184      return false;
185  }
186  return true;
187}
188
189/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
190/// slot / to reg or any rematerialized load into ith operand of specified
191/// MI. If it is successul, MI is updated with the newly created MI and
192/// returns true.
193bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm,
194                                         MachineInstr *DefMI,
195                                         unsigned index, unsigned i,
196                                         bool isSS, int slot, unsigned reg) {
197  MachineInstr *fmi = isSS
198    ? mri_->foldMemoryOperand(MI, i, slot)
199    : mri_->foldMemoryOperand(MI, i, DefMI);
200  if (fmi) {
201    // Attempt to fold the memory reference into the instruction. If
202    // we can do this, we don't need to insert spill code.
203    if (lv_)
204      lv_->instructionChanged(MI, fmi);
205    MachineBasicBlock &MBB = *MI->getParent();
206    vrm.virtFolded(reg, MI, i, fmi);
207    mi2iMap_.erase(MI);
208    i2miMap_[index/InstrSlots::NUM] = fmi;
209    mi2iMap_[fmi] = index;
210    MI = MBB.insert(MBB.erase(MI), fmi);
211    ++numFolded;
212    return true;
213  }
214  return false;
215}
216
217std::vector<LiveInterval*> LiveIntervals::
218addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, unsigned reg) {
219  // since this is called after the analysis is done we don't know if
220  // LiveVariables is available
221  lv_ = getAnalysisToUpdate<LiveVariables>();
222
223  std::vector<LiveInterval*> added;
224
225  assert(li.weight != HUGE_VALF &&
226         "attempt to spill already spilled interval!");
227
228  DOUT << "\t\t\t\tadding intervals for spills for interval: ";
229  li.print(DOUT, mri_);
230  DOUT << '\n';
231
232  SSARegMap *RegMap = mf_->getSSARegMap();
233  const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
234
235  unsigned NumValNums = li.getNumValNums();
236  SmallVector<MachineInstr*, 4> ReMatDefs;
237  ReMatDefs.resize(NumValNums, NULL);
238  SmallVector<MachineInstr*, 4> ReMatOrigDefs;
239  ReMatOrigDefs.resize(NumValNums, NULL);
240  SmallVector<int, 4> ReMatIds;
241  ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
242  BitVector ReMatDelete(NumValNums);
243  unsigned slot = VirtRegMap::MAX_STACK_SLOT;
244
245  bool NeedStackSlot = false;
246  for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
247       i != e; ++i) {
248    const VNInfo *VNI = *i;
249    unsigned VN = VNI->id;
250    unsigned DefIdx = VNI->def;
251    if (DefIdx == ~1U)
252      continue; // Dead val#.
253    // Is the def for the val# rematerializable?
254    MachineInstr *DefMI = (DefIdx == ~0u)
255      ? NULL : getInstructionFromIndex(DefIdx);
256    if (DefMI && isReMaterializable(li, VNI, DefMI)) {
257      // Remember how to remat the def of this val#.
258      ReMatOrigDefs[VN] = DefMI;
259      // Original def may be modified so we have to make a copy here. vrm must
260      // delete these!
261      ReMatDefs[VN] = DefMI = DefMI->clone();
262      vrm.setVirtIsReMaterialized(reg, DefMI);
263
264      bool CanDelete = true;
265      for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
266        unsigned KillIdx = VNI->kills[j];
267        MachineInstr *KillMI = (KillIdx & 1)
268          ? NULL : getInstructionFromIndex(KillIdx);
269        // Kill is a phi node, not all of its uses can be rematerialized.
270        // It must not be deleted.
271        if (!KillMI) {
272          CanDelete = false;
273          // Need a stack slot if there is any live range where uses cannot be
274          // rematerialized.
275          NeedStackSlot = true;
276          break;
277        }
278      }
279
280      if (CanDelete)
281        ReMatDelete.set(VN);
282    } else {
283      // Need a stack slot if there is any live range where uses cannot be
284      // rematerialized.
285      NeedStackSlot = true;
286    }
287  }
288
289  // One stack slot per live interval.
290  if (NeedStackSlot)
291    slot = vrm.assignVirt2StackSlot(reg);
292
293  for (LiveInterval::Ranges::const_iterator
294         I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
295    MachineInstr *DefMI = ReMatDefs[I->valno->id];
296    MachineInstr *OrigDefMI = ReMatOrigDefs[I->valno->id];
297    bool DefIsReMat = DefMI != NULL;
298    bool CanDelete = ReMatDelete[I->valno->id];
299    int LdSlot = 0;
300    bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(DefMI, LdSlot);
301    bool isLoad = isLoadSS ||
302      (DefIsReMat && (DefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
303    unsigned index = getBaseIndex(I->start);
304    unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
305    for (; index != end; index += InstrSlots::NUM) {
306      // skip deleted instructions
307      while (index != end && !getInstructionFromIndex(index))
308        index += InstrSlots::NUM;
309      if (index == end) break;
310
311      MachineInstr *MI = getInstructionFromIndex(index);
312
313    RestartInstruction:
314      for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
315        MachineOperand& mop = MI->getOperand(i);
316        if (!mop.isRegister())
317          continue;
318        unsigned Reg = mop.getReg();
319        if (Reg == 0 || MRegisterInfo::isPhysicalRegister(Reg))
320          continue;
321        bool isSubReg = RegMap->isSubRegister(Reg);
322        unsigned SubIdx = 0;
323        if (isSubReg) {
324          SubIdx = RegMap->getSubRegisterIndex(Reg);
325          Reg = RegMap->getSuperRegister(Reg);
326        }
327        if (Reg != li.reg)
328          continue;
329
330        bool TryFold = !DefIsReMat;
331        bool FoldSS = true;
332        int FoldSlot = slot;
333        if (DefIsReMat) {
334          // If this is the rematerializable definition MI itself and
335          // all of its uses are rematerialized, simply delete it.
336          if (MI == OrigDefMI && CanDelete) {
337            RemoveMachineInstrFromMaps(MI);
338            MI->eraseFromParent();
339            break;
340          }
341
342          // If def for this use can't be rematerialized, then try folding.
343          TryFold = !OrigDefMI || (OrigDefMI && (MI == OrigDefMI || isLoad));
344          if (isLoad) {
345            // Try fold loads (from stack slot, constant pool, etc.) into uses.
346            FoldSS = isLoadSS;
347            FoldSlot = LdSlot;
348          }
349        }
350
351        // FIXME: fold subreg use
352        if (!isSubReg && TryFold &&
353            tryFoldMemoryOperand(MI, vrm, DefMI, index, i, FoldSS, FoldSlot, Reg))
354          // Folding the load/store can completely change the instruction in
355          // unpredictable ways, rescan it from the beginning.
356          goto RestartInstruction;
357
358        // Create a new virtual register for the spill interval.
359        unsigned NewVReg = RegMap->createVirtualRegister(rc);
360        if (isSubReg)
361          RegMap->setIsSubRegister(NewVReg, NewVReg, SubIdx);
362
363        // Scan all of the operands of this instruction rewriting operands
364        // to use NewVReg instead of li.reg as appropriate.  We do this for
365        // two reasons:
366        //
367        //   1. If the instr reads the same spilled vreg multiple times, we
368        //      want to reuse the NewVReg.
369        //   2. If the instr is a two-addr instruction, we are required to
370        //      keep the src/dst regs pinned.
371        //
372        // Keep track of whether we replace a use and/or def so that we can
373        // create the spill interval with the appropriate range.
374        mop.setReg(NewVReg);
375
376        bool HasUse = mop.isUse();
377        bool HasDef = mop.isDef();
378        for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
379          if (!MI->getOperand(j).isRegister())
380            continue;
381          unsigned RegJ = MI->getOperand(j).getReg();
382          if (RegJ != 0 && MRegisterInfo::isVirtualRegister(RegJ) &&
383              RegMap->isSubRegister(RegJ))
384            RegJ = RegMap->getSuperRegister(RegJ);
385          if (RegJ == li.reg) {
386            MI->getOperand(j).setReg(NewVReg);
387            HasUse |= MI->getOperand(j).isUse();
388            HasDef |= MI->getOperand(j).isDef();
389          }
390        }
391
392        vrm.grow();
393        if (DefIsReMat) {
394          vrm.setVirtIsReMaterialized(NewVReg, DefMI/*, CanDelete*/);
395          if (ReMatIds[I->valno->id] == VirtRegMap::MAX_STACK_SLOT) {
396            // Each valnum may have its own remat id.
397            ReMatIds[I->valno->id] = vrm.assignVirtReMatId(NewVReg);
398          } else {
399            vrm.assignVirtReMatId(NewVReg, ReMatIds[I->valno->id]);
400          }
401          if (!CanDelete || (HasUse && HasDef)) {
402            // If this is a two-addr instruction then its use operands are
403            // rematerializable but its def is not. It should be assigned a
404            // stack slot.
405            vrm.assignVirt2StackSlot(NewVReg, slot);
406          }
407        } else {
408          vrm.assignVirt2StackSlot(NewVReg, slot);
409        }
410
411        // create a new register interval for this spill / remat.
412        LiveInterval &nI = getOrCreateInterval(NewVReg);
413        assert(nI.empty());
414
415        // the spill weight is now infinity as it
416        // cannot be spilled again
417        nI.weight = HUGE_VALF;
418
419        if (HasUse) {
420          LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
421                       nI.getNextValue(~0U, 0, VNInfoAllocator));
422          DOUT << " +" << LR;
423          nI.addRange(LR);
424        }
425        if (HasDef) {
426          LiveRange LR(getDefIndex(index), getStoreIndex(index),
427                       nI.getNextValue(~0U, 0, VNInfoAllocator));
428          DOUT << " +" << LR;
429          nI.addRange(LR);
430        }
431
432        added.push_back(&nI);
433
434        // update live variables if it is available
435        if (lv_)
436          lv_->addVirtualRegisterKilled(NewVReg, MI);
437
438        DOUT << "\t\t\t\tadded new interval: ";
439        nI.print(DOUT, mri_);
440        DOUT << '\n';
441      }
442    }
443  }
444
445  return added;
446}
447
448/// conflictsWithPhysRegDef - Returns true if the specified register
449/// is defined during the duration of the specified interval.
450bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
451                                            VirtRegMap &vrm, unsigned reg) {
452  for (LiveInterval::Ranges::const_iterator
453         I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
454    for (unsigned index = getBaseIndex(I->start),
455           end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
456         index += InstrSlots::NUM) {
457      // skip deleted instructions
458      while (index != end && !getInstructionFromIndex(index))
459        index += InstrSlots::NUM;
460      if (index == end) break;
461
462      MachineInstr *MI = getInstructionFromIndex(index);
463      for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
464        MachineOperand& mop = MI->getOperand(i);
465        if (!mop.isRegister() || !mop.isDef())
466          continue;
467        unsigned PhysReg = mop.getReg();
468        if (PhysReg == 0)
469          continue;
470        if (MRegisterInfo::isVirtualRegister(PhysReg))
471          PhysReg = vrm.getPhys(PhysReg);
472        if (PhysReg && mri_->regsOverlap(PhysReg, reg))
473          return true;
474      }
475    }
476  }
477
478  return false;
479}
480
481void LiveIntervals::printRegName(unsigned reg) const {
482  if (MRegisterInfo::isPhysicalRegister(reg))
483    cerr << mri_->getName(reg);
484  else
485    cerr << "%reg" << reg;
486}
487
488void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
489                                             MachineBasicBlock::iterator mi,
490                                             unsigned MIIdx,
491                                             LiveInterval &interval) {
492  DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
493  LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
494
495  // Virtual registers may be defined multiple times (due to phi
496  // elimination and 2-addr elimination).  Much of what we do only has to be
497  // done once for the vreg.  We use an empty interval to detect the first
498  // time we see a vreg.
499  if (interval.empty()) {
500    // Get the Idx of the defining instructions.
501    unsigned defIndex = getDefIndex(MIIdx);
502    VNInfo *ValNo;
503    unsigned SrcReg, DstReg;
504    if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
505      ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
506    else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
507      ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
508                                    VNInfoAllocator);
509    else
510      ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
511
512    assert(ValNo->id == 0 && "First value in interval is not 0?");
513
514    // Loop over all of the blocks that the vreg is defined in.  There are
515    // two cases we have to handle here.  The most common case is a vreg
516    // whose lifetime is contained within a basic block.  In this case there
517    // will be a single kill, in MBB, which comes after the definition.
518    if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
519      // FIXME: what about dead vars?
520      unsigned killIdx;
521      if (vi.Kills[0] != mi)
522        killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
523      else
524        killIdx = defIndex+1;
525
526      // If the kill happens after the definition, we have an intra-block
527      // live range.
528      if (killIdx > defIndex) {
529        assert(vi.AliveBlocks.none() &&
530               "Shouldn't be alive across any blocks!");
531        LiveRange LR(defIndex, killIdx, ValNo);
532        interval.addRange(LR);
533        DOUT << " +" << LR << "\n";
534        interval.addKill(ValNo, killIdx);
535        return;
536      }
537    }
538
539    // The other case we handle is when a virtual register lives to the end
540    // of the defining block, potentially live across some blocks, then is
541    // live into some number of blocks, but gets killed.  Start by adding a
542    // range that goes from this definition to the end of the defining block.
543    LiveRange NewLR(defIndex,
544                    getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
545                    ValNo);
546    DOUT << " +" << NewLR;
547    interval.addRange(NewLR);
548
549    // Iterate over all of the blocks that the variable is completely
550    // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
551    // live interval.
552    for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
553      if (vi.AliveBlocks[i]) {
554        MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
555        if (!MBB->empty()) {
556          LiveRange LR(getMBBStartIdx(i),
557                       getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
558                       ValNo);
559          interval.addRange(LR);
560          DOUT << " +" << LR;
561        }
562      }
563    }
564
565    // Finally, this virtual register is live from the start of any killing
566    // block to the 'use' slot of the killing instruction.
567    for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
568      MachineInstr *Kill = vi.Kills[i];
569      unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
570      LiveRange LR(getMBBStartIdx(Kill->getParent()),
571                   killIdx, ValNo);
572      interval.addRange(LR);
573      interval.addKill(ValNo, killIdx);
574      DOUT << " +" << LR;
575    }
576
577  } else {
578    // If this is the second time we see a virtual register definition, it
579    // must be due to phi elimination or two addr elimination.  If this is
580    // the result of two address elimination, then the vreg is one of the
581    // def-and-use register operand.
582    if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
583      // If this is a two-address definition, then we have already processed
584      // the live range.  The only problem is that we didn't realize there
585      // are actually two values in the live interval.  Because of this we
586      // need to take the LiveRegion that defines this register and split it
587      // into two values.
588      unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
589      unsigned RedefIndex = getDefIndex(MIIdx);
590
591      const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
592      VNInfo *OldValNo = OldLR->valno;
593      unsigned OldEnd = OldLR->end;
594
595      // Delete the initial value, which should be short and continuous,
596      // because the 2-addr copy must be in the same MBB as the redef.
597      interval.removeRange(DefIndex, RedefIndex);
598
599      // Two-address vregs should always only be redefined once.  This means
600      // that at this point, there should be exactly one value number in it.
601      assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
602
603      // The new value number (#1) is defined by the instruction we claimed
604      // defined value #0.
605      VNInfo *ValNo = interval.getNextValue(0, 0, VNInfoAllocator);
606      interval.copyValNumInfo(ValNo, OldValNo);
607
608      // Value#0 is now defined by the 2-addr instruction.
609      OldValNo->def = RedefIndex;
610      OldValNo->reg = 0;
611
612      // Add the new live interval which replaces the range for the input copy.
613      LiveRange LR(DefIndex, RedefIndex, ValNo);
614      DOUT << " replace range with " << LR;
615      interval.addRange(LR);
616      interval.addKill(ValNo, RedefIndex);
617      interval.removeKills(ValNo, RedefIndex, OldEnd);
618
619      // If this redefinition is dead, we need to add a dummy unit live
620      // range covering the def slot.
621      if (lv_->RegisterDefIsDead(mi, interval.reg))
622        interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
623
624      DOUT << " RESULT: ";
625      interval.print(DOUT, mri_);
626
627    } else {
628      // Otherwise, this must be because of phi elimination.  If this is the
629      // first redefinition of the vreg that we have seen, go back and change
630      // the live range in the PHI block to be a different value number.
631      if (interval.containsOneValue()) {
632        assert(vi.Kills.size() == 1 &&
633               "PHI elimination vreg should have one kill, the PHI itself!");
634
635        // Remove the old range that we now know has an incorrect number.
636        VNInfo *VNI = interval.getValNumInfo(0);
637        MachineInstr *Killer = vi.Kills[0];
638        unsigned Start = getMBBStartIdx(Killer->getParent());
639        unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
640        DOUT << " Removing [" << Start << "," << End << "] from: ";
641        interval.print(DOUT, mri_); DOUT << "\n";
642        interval.removeRange(Start, End);
643        interval.addKill(VNI, Start+1); // odd # means phi node
644        DOUT << " RESULT: "; interval.print(DOUT, mri_);
645
646        // Replace the interval with one of a NEW value number.  Note that this
647        // value number isn't actually defined by an instruction, weird huh? :)
648        LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
649        DOUT << " replace range with " << LR;
650        interval.addRange(LR);
651        interval.addKill(LR.valno, End);
652        DOUT << " RESULT: "; interval.print(DOUT, mri_);
653      }
654
655      // In the case of PHI elimination, each variable definition is only
656      // live until the end of the block.  We've already taken care of the
657      // rest of the live range.
658      unsigned defIndex = getDefIndex(MIIdx);
659
660      VNInfo *ValNo;
661      unsigned SrcReg, DstReg;
662      if (tii_->isMoveInstr(*mi, SrcReg, DstReg))
663        ValNo = interval.getNextValue(defIndex, SrcReg, VNInfoAllocator);
664      else if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
665        ValNo = interval.getNextValue(defIndex, mi->getOperand(1).getReg(),
666                                      VNInfoAllocator);
667      else
668        ValNo = interval.getNextValue(defIndex, 0, VNInfoAllocator);
669
670      unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
671      LiveRange LR(defIndex, killIndex, ValNo);
672      interval.addRange(LR);
673      interval.addKill(ValNo, killIndex-1); // odd # means phi node
674      DOUT << " +" << LR;
675    }
676  }
677
678  DOUT << '\n';
679}
680
681void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
682                                              MachineBasicBlock::iterator mi,
683                                              unsigned MIIdx,
684                                              LiveInterval &interval,
685                                              unsigned SrcReg) {
686  // A physical register cannot be live across basic block, so its
687  // lifetime must end somewhere in its defining basic block.
688  DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
689
690  unsigned baseIndex = MIIdx;
691  unsigned start = getDefIndex(baseIndex);
692  unsigned end = start;
693
694  // If it is not used after definition, it is considered dead at
695  // the instruction defining it. Hence its interval is:
696  // [defSlot(def), defSlot(def)+1)
697  if (lv_->RegisterDefIsDead(mi, interval.reg)) {
698    DOUT << " dead";
699    end = getDefIndex(start) + 1;
700    goto exit;
701  }
702
703  // If it is not dead on definition, it must be killed by a
704  // subsequent instruction. Hence its interval is:
705  // [defSlot(def), useSlot(kill)+1)
706  while (++mi != MBB->end()) {
707    baseIndex += InstrSlots::NUM;
708    if (lv_->KillsRegister(mi, interval.reg)) {
709      DOUT << " killed";
710      end = getUseIndex(baseIndex) + 1;
711      goto exit;
712    } else if (lv_->ModifiesRegister(mi, interval.reg)) {
713      // Another instruction redefines the register before it is ever read.
714      // Then the register is essentially dead at the instruction that defines
715      // it. Hence its interval is:
716      // [defSlot(def), defSlot(def)+1)
717      DOUT << " dead";
718      end = getDefIndex(start) + 1;
719      goto exit;
720    }
721  }
722
723  // The only case we should have a dead physreg here without a killing or
724  // instruction where we know it's dead is if it is live-in to the function
725  // and never used.
726  assert(!SrcReg && "physreg was not killed in defining block!");
727  end = getDefIndex(start) + 1;  // It's dead.
728
729exit:
730  assert(start < end && "did not find end of interval?");
731
732  // Already exists? Extend old live interval.
733  LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
734  VNInfo *ValNo = (OldLR != interval.end())
735    ? OldLR->valno : interval.getNextValue(start, SrcReg, VNInfoAllocator);
736  LiveRange LR(start, end, ValNo);
737  interval.addRange(LR);
738  interval.addKill(LR.valno, end);
739  DOUT << " +" << LR << '\n';
740}
741
742void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
743                                      MachineBasicBlock::iterator MI,
744                                      unsigned MIIdx,
745                                      unsigned reg) {
746  if (MRegisterInfo::isVirtualRegister(reg))
747    handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
748  else if (allocatableRegs_[reg]) {
749    unsigned SrcReg, DstReg;
750    if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
751      SrcReg = MI->getOperand(1).getReg();
752    else if (!tii_->isMoveInstr(*MI, SrcReg, DstReg))
753      SrcReg = 0;
754    handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), SrcReg);
755    // Def of a register also defines its sub-registers.
756    for (const unsigned* AS = mri_->getSubRegisters(reg); *AS; ++AS)
757      // Avoid processing some defs more than once.
758      if (!MI->findRegisterDefOperand(*AS))
759        handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
760  }
761}
762
763void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
764                                         unsigned MIIdx,
765                                         LiveInterval &interval, bool isAlias) {
766  DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
767
768  // Look for kills, if it reaches a def before it's killed, then it shouldn't
769  // be considered a livein.
770  MachineBasicBlock::iterator mi = MBB->begin();
771  unsigned baseIndex = MIIdx;
772  unsigned start = baseIndex;
773  unsigned end = start;
774  while (mi != MBB->end()) {
775    if (lv_->KillsRegister(mi, interval.reg)) {
776      DOUT << " killed";
777      end = getUseIndex(baseIndex) + 1;
778      goto exit;
779    } else if (lv_->ModifiesRegister(mi, interval.reg)) {
780      // Another instruction redefines the register before it is ever read.
781      // Then the register is essentially dead at the instruction that defines
782      // it. Hence its interval is:
783      // [defSlot(def), defSlot(def)+1)
784      DOUT << " dead";
785      end = getDefIndex(start) + 1;
786      goto exit;
787    }
788
789    baseIndex += InstrSlots::NUM;
790    ++mi;
791  }
792
793exit:
794  // Live-in register might not be used at all.
795  if (end == MIIdx) {
796    if (isAlias) {
797      DOUT << " dead";
798      end = getDefIndex(MIIdx) + 1;
799    } else {
800      DOUT << " live through";
801      end = baseIndex;
802    }
803  }
804
805  LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
806  interval.addRange(LR);
807  interval.addKill(LR.valno, end);
808  DOUT << " +" << LR << '\n';
809}
810
811/// computeIntervals - computes the live intervals for virtual
812/// registers. for some ordering of the machine instructions [1,N] a
813/// live interval is an interval [i, j) where 1 <= i <= j < N for
814/// which a variable is live
815void LiveIntervals::computeIntervals() {
816  DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
817       << "********** Function: "
818       << ((Value*)mf_->getFunction())->getName() << '\n';
819  // Track the index of the current machine instr.
820  unsigned MIIndex = 0;
821  for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
822       MBBI != E; ++MBBI) {
823    MachineBasicBlock *MBB = MBBI;
824    DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
825
826    MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
827
828    // Create intervals for live-ins to this BB first.
829    for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
830           LE = MBB->livein_end(); LI != LE; ++LI) {
831      handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
832      // Multiple live-ins can alias the same register.
833      for (const unsigned* AS = mri_->getSubRegisters(*LI); *AS; ++AS)
834        if (!hasInterval(*AS))
835          handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
836                               true);
837    }
838
839    for (; MI != miEnd; ++MI) {
840      DOUT << MIIndex << "\t" << *MI;
841
842      // Handle defs.
843      for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
844        MachineOperand &MO = MI->getOperand(i);
845        // handle register defs - build intervals
846        if (MO.isRegister() && MO.getReg() && MO.isDef())
847          handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
848      }
849
850      MIIndex += InstrSlots::NUM;
851    }
852  }
853}
854
855bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
856                              SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
857  std::vector<IdxMBBPair>::const_iterator I =
858    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
859
860  bool ResVal = false;
861  while (I != Idx2MBBMap.end()) {
862    if (LR.end <= I->first)
863      break;
864    MBBs.push_back(I->second);
865    ResVal = true;
866    ++I;
867  }
868  return ResVal;
869}
870
871
872LiveInterval LiveIntervals::createInterval(unsigned reg) {
873  float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
874                       HUGE_VALF : 0.0F;
875  return LiveInterval(reg, Weight);
876}
877