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 <algorithm>
using namespace llvm;

// SlotIndexIterator - adapt an iterator over LiveRanges to look
// like an iterator over SlotIndexes by accessing the .end member.
namespace {
struct SlotIndexIterator
  : std::iterator<std::random_access_iterator_tag, SlotIndex> {

  SlotIndexIterator() {
  }

  explicit SlotIndexIterator(LiveInterval::iterator it)
    : it(it) {
  }

  SlotIndexIterator(const SlotIndexIterator & that)
    : it(that.it) {
  }

  SlotIndexIterator & operator=(const SlotIndexIterator & that) {
    it = that.it;
    return *this;
  }

  SlotIndexIterator & operator++() {
    ++it;
    return *this;
  }

  SlotIndexIterator operator++(int) {
    SlotIndexIterator that(*this);
    ++*this;
    return that;
  }

  SlotIndexIterator & operator--() {
    --it;
    return *this;
  }

  SlotIndexIterator operator--(int) {
    SlotIndexIterator that(*this);
    --*this;
    return that;
  }

  SlotIndexIterator & operator+=(std::ptrdiff_t n) {
    it += n;
    return *this;
  }

  SlotIndexIterator & operator-=(std::ptrdiff_t n) {
    it -= n;
    return *this;
  }

  friend bool operator==(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it == rhs.it;
  }

  friend bool operator!=(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it != rhs.it;
  }

  friend bool operator<(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it < rhs.it;
  }

  friend bool operator<=(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it <= rhs.it;
  }

  friend bool operator>(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it > rhs.it;
  }

  friend bool operator>=(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it >= rhs.it;
  }

  friend SlotIndexIterator operator+(SlotIndexIterator that, std::ptrdiff_t n) {
    return SlotIndexIterator(that.it + n);
  }

  friend SlotIndexIterator operator+(std::ptrdiff_t n, SlotIndexIterator that) {
    return SlotIndexIterator(n + that.it);
  }

  friend SlotIndexIterator operator-(SlotIndexIterator that, std::ptrdiff_t n) {
    return SlotIndexIterator(that.it - n);
  }

  friend std::ptrdiff_t operator-(SlotIndexIterator lhs, SlotIndexIterator rhs) {
    return lhs.it - rhs.it;
  }

  reference operator*() const {
    return it->end;
  }

  reference operator[](std::ptrdiff_t n) const {
    return it[n].end;
  }

  pointer operator->() const {
    return &it->end;
  }

  LiveInterval::iterator base() const {
    return it;
  }

private:
  LiveInterval::iterator it;
};
}

LiveInterval::iterator LiveInterval::find(SlotIndex Pos) {
  assert(Pos.isValid() && "Cannot search for an invalid index");
  return std::upper_bound(
    SlotIndexIterator(begin()),
    SlotIndexIterator(end()), Pos).base();
}

/// 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 f