[turbofan] Retiring Greedy Allocator

src/compiler/coalesced-live-ranges.cc

Index: src/compiler/coalesced-live-ranges.cc
diff --git a/src/compiler/coalesced-live-ranges.cc b/src/compiler/coalesced-live-ranges.cc
deleted file mode 100644
index 4ac3e2118de31f9e85eeaf08e998c631244f42ec..0000000000000000000000000000000000000000
--- a/src/compiler/coalesced-live-ranges.cc
+++ /dev/null
@@ -1,143 +0,0 @@
-// Copyright 2015 the V8 project authors. All rights reserved.
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-#include "src/compiler/coalesced-live-ranges.h"
-#include "src/compiler/greedy-allocator.h"
-#include "src/compiler/register-allocator.h"
-
-namespace v8 {
-namespace internal {
-namespace compiler {
-
-
-LiveRangeConflictIterator::LiveRangeConflictIterator(const LiveRange* range,
-                                                     IntervalStore* storage)
-    : query_(range->first_interval()),
-      pos_(storage->end()),
-      intervals_(storage) {
-  MovePosAndQueryToFirstConflict();
-}
-
-
-LiveRange* LiveRangeConflictIterator::Current() const {
-  if (IsFinished()) return nullptr;
-  return pos_->range_;
-}
-
-
-void LiveRangeConflictIterator::MovePosToFirstConflictForQuery() {
-  DCHECK_NOT_NULL(query_);
-  auto end = intervals_->end();
-  LifetimePosition q_start = query_->start();
-  LifetimePosition q_end = query_->end();
-
-  if (intervals_->empty() || intervals_->rbegin()->end_ <= q_start ||
-      intervals_->begin()->start_ >= q_end) {
-    pos_ = end;
-    return;
-  }
-
-  pos_ = intervals_->upper_bound(AsAllocatedInterval(q_start));
-  // pos is either at the end (no start strictly greater than q_start) or
-  // at some position with the aforementioned property. In either case, the
-  // allocated interval before this one may intersect our query:
-  // either because, although it starts before this query's start, it ends
-  // after; or because it starts exactly at the query start. So unless we're
-  // right at the beginning of the storage - meaning the first allocated
-  // interval is also starting after this query's start - see what's behind.
-  if (pos_ != intervals_->begin()) {
-    --pos_;
-    if (!QueryIntersectsAllocatedInterval()) {
-      // The interval behind wasn't intersecting, so move back.
-      ++pos_;
-    }
-  }
-  if (pos_ == end || !QueryIntersectsAllocatedInterval()) {
-    pos_ = end;
-  }
-}
-
-
-void LiveRangeConflictIterator::MovePosAndQueryToFirstConflict() {
-  auto end = intervals_->end();
-  for (; query_ != nullptr; query_ = query_->next()) {
-    MovePosToFirstConflictForQuery();
-    if (pos_ != end) {
-      DCHECK(QueryIntersectsAllocatedInterval());
-      return;
-    }
-  }
-
-  Invalidate();
-}
-
-
-void LiveRangeConflictIterator::IncrementPosAndSkipOverRepetitions() {
-  auto end = intervals_->end();
-  DCHECK(pos_ != end);
-  LiveRange* current_conflict = Current();
-  while (pos_ != end && pos_->range_ == current_conflict) {
-    ++pos_;
-  }
-}
-
-
-LiveRange* LiveRangeConflictIterator::InternalGetNext(bool clean_behind) {
-  if (IsFinished()) return nullptr;
-
-  LiveRange* to_clear = Current();
-  IncrementPosAndSkipOverRepetitions();
-  // At this point, pos_ is either at the end, or on an interval that doesn't
-  // correspond to the same range as to_clear. This interval may not even be
-  // a conflict.
-  if (clean_behind) {
-    // Since we parked pos_ on an iterator that won't be affected by removal,
-    // we can safely delete to_clear's intervals.
-    for (auto interval = to_clear->first_interval(); interval != nullptr;
-         interval = interval->next()) {
-      AllocatedInterval erase_key(interval->start(), interval->end(), nullptr);
-      intervals_->erase(erase_key);
-    }
-  }
-  // We may have parked pos_ at the end, or on a non-conflict. In that case,
-  // move to the next query and reinitialize pos and query. This may invalidate
-  // the iterator, if no more conflicts are available.
-  if (!QueryIntersectsAllocatedInterval()) {
-    query_ = query_->next();
-    MovePosAndQueryToFirstConflict();
-  }
-  return Current();
-}
-
-
-LiveRangeConflictIterator CoalescedLiveRanges::GetConflicts(
-    const LiveRange* range) {
-  return LiveRangeConflictIterator(range, &intervals());
-}
-
-
-void CoalescedLiveRanges::AllocateRange(LiveRange* range) {
-  for (auto interval = range->first_interval(); interval != nullptr;
-       interval = interval->next()) {
-    AllocatedInterval to_insert(interval->start(), interval->end(), range);
-    intervals().insert(to_insert);
-  }
-}
-
-
-bool CoalescedLiveRanges::VerifyAllocationsAreValidForTesting() const {
-  LifetimePosition last_end = LifetimePosition::GapFromInstructionIndex(0);
-  for (auto i : intervals_) {
-    if (i.start_ < last_end) {
-      return false;
-    }
-    last_end = i.end_;
-  }
-  return true;
-}
-
-
-}  // namespace compiler
-}  // namespace internal
-}  // namespace v8