<commit_before>//===-- LiveInterval.cpp - Live Interval Representation -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and 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' abd 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 "LiveInterval.h"
#include "Support/STLExtras.h"
#include <iostream>
#include <map>
using namespace llvm;

// An example for liveAt():
//
// this = [1,4), liveAt(0) will return false. The instruction defining this
// spans slots [0,3]. The interval belongs to an spilled definition of the
// variable it represents. This is because slot 1 is used (def slot) and spans
// up to slot 3 (store slot).
//
bool LiveInterval::liveAt(unsigned I) const {
  Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
                                              
  if (r == ranges.begin())
    return false;

  --r;
  return r->contains(I);
}

// 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::overlaps(const LiveInterval& other) const {
  Ranges::const_iterator i = ranges.begin();
  Ranges::const_iterator ie = ranges.end();
  Ranges::const_iterator j = other.ranges.begin();
  Ranges::const_iterator je = other.ranges.end();
  if (i->start < j->start) {
    i = std::upper_bound(i, ie, j->start);
    if (i != ranges.begin()) --i;
  } else if (j->start < i->start) {
    j = std::upper_bound(j, je, i->start);
    if (j != other.ranges.begin()) --j;
  } else {
    return true;
  }

  while (i != ie && j != je) {
    if (i->start == j->start)
      return true;

    if (i->start > j->start) {
      std::swap(i, j);
      std::swap(ie, je);
    }
    assert(i->start < j->start);

    if (i->end > j->start)
      return true;
    ++i;
  }

  return false;
}

/// joinable - Two intervals are joinable if the either don't overlap at all
/// or if the destination of the copy is a single assignment value, and it
/// only overlaps with one value in the source interval.
bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const {
  return overlaps(other);
}


/// extendIntervalEndTo - This method is used when we want to extend the range
/// specified by I to end at the specified endpoint.  To do this, we should
/// merge and eliminate all ranges that this will overlap with.  The iterator is<commit_msg>This patch makes use of the infrastructure implemented before to safely and aggressively coallesce live ranges even if they overlap.  Consider this LLVM code for example:<commit_after>//===-- LiveInterval.cpp - Live Interval Representation -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and 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' abd 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 "LiveInterval.h"
#include "Support/STLExtras.h"
#include <iostream>
#include <map>
using namespace llvm;

// An example for liveAt():
//
// this = [1,4), liveAt(0) will return false. The instruction defining this
// spans slots [0,3]. The interval belongs to an spilled definition of the
// variable it represents. This is because slot 1 is used (def slot) and spans
// up to slot 3 (store slot).
//
bool LiveInterval::liveAt(unsigned I) const {
  Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
                                              
  if (r == ranges.begin())
    return false;

  --r;
  return r->contains(I);
}

// 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::overlaps(const LiveInterval& other) const {
  Ranges::const_iterator i = ranges.begin();
  Ranges::const_iterator ie = ranges.end();
  Ranges::const_iterator j = other.ranges.begin();
  Ranges::const_iterator je = other.ranges.end();

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

  while (i != ie && j != je) {
    if (i->start == j->start)
      return true;

    if (i->start > j->start) {
      std::swap(i, j);
      std::swap(ie, je);
    }
    assert(i->start < j->start);

    if (i->end > j->start)
      return true;
    ++i;
  }

  return false;
}

/// joinable - Two intervals are joinable if the either don't overlap at all
/// or if the destination of the copy is a single assignment value, and it
/// only overlaps with one value in the source interval.
bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const {
  const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1);
  const LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
  assert(SourceLR && DestLR && "Not joining due to a copy?");
  unsigned OtherValIdx = SourceLR->ValId;
  unsigned ThisValIdx = DestLR->ValId;

  Ranges::const_iterator i = ranges.begin();
  Ranges::const_iterator ie = ranges.end();
  Ranges::const_iterator j = other.ranges.begin();
  Ranges::const_iterator je = other.ranges.end();

  if (i->start < j->start) {
    i = std::upper_bound(i, ie, j->start);
    if (i != ranges.begin()) --i;
  } else if (j->start < i->start) {
    j = std::upper_bound(j, je, i->start);
    if (j != other.ranges.begin()) --j;
  }

  while (i != ie && j != je) {
    if (i->start == j->start) {
      // If this is not the allowed value merge, we cannot join.
      if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
        return true;
    } else if (i->start < j->start) {
      if (i->end > j->start) {
        if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
          return true;
      }
    } else {
      if (j->end > i->start) {
        if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
          return true;
      }
    }
    if (i->end < j->end)
      ++i;
    else
      ++j;
  }

  return false;
}


/// extendIntervalEndTo - This method is used when we want to extend the range
/// specified by I to end at the specified endpoint.  To do this, we should
/// merge and eliminate all ranges that this will overlap with.  The iterator is
{'fraction_non_alphanumeric': 0.1760606431104047, 'fraction_numerical': 0.0077026531360802055, 'mean_word_length': 2.364870423693953, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1334412', 'n_tokens_mistral': 2497, 'n_tokens_neox': 2417, 'n_words': 949}