path: root/lib/CodeGen/LiveInterval.cpp

//===-- LiveInterval.cpp - Live Interval Representation -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveRange and LiveInterval classes.  Given some
// numbering of each the machine instructions an interval [i, j) is said to be a
// live interval for register v if there is no instruction with number j' > j
// such that v is live at j' and there is no instruction with number i' < i such
// that v is live at i'. In this implementation intervals can have holes,
// i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
// individual range is represented as an instance of LiveRange, and the whole
// interval is represented as an instance of LiveInterval.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "RegisterCoalescer.h"
#include <algorithm>
using namespace llvm;

LiveInterval::iterator LiveInterval::find(SlotIndex Pos) {
  // This algorithm is basically std::upper_bound.
  // Unfortunately, std::upper_bound cannot be used with mixed types until we
  // adopt C++0x. Many libraries can do it, but not all.
  if (empty() || Pos >= endIndex())
    return end();
  iterator I = begin();
  size_t Len = ranges.size();
  do {
    size_t Mid = Len >> 1;
    if (Pos < I[Mid].end)
      Len = Mid;
    else
      I += Mid + 1, Len -= Mid + 1;
  } while (Len);
  return I;
}

VNInfo *LiveInterval::createDeadDef(SlotIndex Def,
                                    VNInfo::Allocator &VNInfoAllocator) {
  assert(!Def.isDead() && "Cannot define a value at the dead slot");
  iterator I = find(Def);
  if (I == end()) {
    VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
    ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI));
    return VNI;
  }
  if (SlotIndex::isSameInstr(Def, I->start)) {
    assert(I->start == Def && "Cannot insert def, already live");
    assert(I->valno->def == Def && "Inconsistent existing value def");
    return I->valno;
  }
  assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def");
  VNInfo *VNI = getNextValue(Def, VNInfoAllocator);
  ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI));
  return VNI;
}

/// killedInRange - Return true if the interval has kills in [Start,End).
bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
  Ranges::const_iterator r =
    std::lower_bound(ranges.begin(), ranges.end(), End);

  // Now r points to the first interval with start >= End, or ranges.end().
  if (r == ranges.begin())
    return false;

  --r;
  // Now r points to the last interval with end <= End.
  // r->end is the kill point.
  return r->end >= Start && r->end < End;
}

// overlaps - Return true if the intersection of the two live intervals is
// not empty.
//
// An example for overlaps():
//
// 0: A = ...
// 4: B = ...
// 8: C = A + B ;; last use of A
//
// The live intervals should look like:
//
// A = [3, 11)
// B = [7, x)
// C = [11, y)
//
// A->overlaps(C) should return false since we want to be able to join
// A and C.
//
bool LiveInterval::overlapsFrom(const LiveInterval& other,
                                const_iterator StartPos) const {
  assert(!empty() && "empty interval");
  const_iterator i = begin();
  const_iterator ie = end();
  const_iterator j = StartPos;
  const_iterator je = other.end();

  assert((StartPos->start <= i->start || StartPos == other.begin()) &&
         StartPos != other.end() && "Bogus start position hint!");

  if (i->start < j->start) {
    i = std::upper_bound(i, ie, j->start);
    if (i != ranges.begin()) --i;
  } else if (j->start < i->start) {
    ++StartPos;
    if (StartPos != other.end() && StartPos->start <= i->start) {
      assert(StartPos < other.end() && i < end());
      j = std::upper_bound(j, je, i->start);
      if (j != other.ranges.begin()) --j;
    }
  } else {
    return true;
  }

  if (j == je) return false;

  while (i != ie) {
    if (i->start > j->start) {
      std::swap(i, j);
      std::