[turbofan] Retiring Greedy Allocator

src/compiler/coalesced-live-ranges.h

-// 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.
-
-#ifndef V8_COALESCED_LIVE_RANGES_H_
-#define V8_COALESCED_LIVE_RANGES_H_
-
-#include "src/compiler/register-allocator.h"
-#include "src/zone-containers.h"
-
-namespace v8 {
-namespace internal {
-namespace compiler {
-
-
-// Implementation detail for CoalescedLiveRanges.
-struct AllocatedInterval {
-  AllocatedInterval(LifetimePosition start, LifetimePosition end,
-                    LiveRange* range)
-      : start_(start), end_(end), range_(range) {}
-
-  LifetimePosition start_;
-  LifetimePosition end_;
-  LiveRange* range_;
-  bool operator<(const AllocatedInterval& other) const {
-    return start_ < other.start_;
-  }
-  bool operator>(const AllocatedInterval& other) const {
-    return start_ > other.start_;
-  }
-};
-typedef ZoneSet<AllocatedInterval> IntervalStore;
-
-
-// An iterator over conflicts of a live range, obtained from CoalescedLiveRanges
-// The design supports two main scenarios (see GreedyAllocator):
-// (1) observing each conflicting range, without mutating the allocations, and
-// (2) observing each conflicting range, and then moving to the next, after
-// removing the current conflict.
-class LiveRangeConflictIterator {
- public:
-  // Current conflict. nullptr if no conflicts, or if we reached the end of
-  // conflicts.
-  LiveRange* Current() const;
-
-  // Get the next conflict. Caller should handle non-consecutive repetitions of
-  // the same range.
-  LiveRange* GetNext() { return InternalGetNext(false); }
-
-  // Get the next conflict, after evicting the current one. Caller may expect
-  // to never observe the same live range more than once.
-  LiveRange* RemoveCurrentAndGetNext() { return InternalGetNext(true); }
-
- private:
-  friend class CoalescedLiveRanges;
-
-  typedef IntervalStore::const_iterator interval_iterator;
-  LiveRangeConflictIterator(const LiveRange* range, IntervalStore* store);
-
-  // Move the store iterator to  first interval intersecting query. Since the
-  // intervals are sorted, subsequent intervals intersecting query follow. May
-  // leave the store iterator at "end", meaning that the current query does not
-  // have an intersection.
-  void MovePosToFirstConflictForQuery();
-
-  // Move both query and store iterator to the first intersection, if any. If
-  // none, then it invalidates the iterator (IsFinished() == true)
-  void MovePosAndQueryToFirstConflict();
-
-  // Increment pos and skip over intervals belonging to the same range we
-  // started with (i.e. Current() before the call). It is possible that range
-  // will be seen again, but not consecutively.
-  void IncrementPosAndSkipOverRepetitions();
-
-  // Common implementation used by both GetNext as well as
-  // ClearCurrentAndGetNext.
-  LiveRange* InternalGetNext(bool clean_behind);
-
-  bool IsFinished() const { return query_ == nullptr; }
-
-  static AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
-    return AllocatedInterval(pos, LifetimePosition::Invalid(), nullptr);
-  }
-
-  // Intersection utilities.
-  static bool Intersects(LifetimePosition a_start, LifetimePosition a_end,
-                         LifetimePosition b_start, LifetimePosition b_end) {
-    return a_start < b_end && b_start < a_end;
-  }
-
-  bool QueryIntersectsAllocatedInterval() const {
-    DCHECK_NOT_NULL(query_);
-    return pos_ != intervals_->end() &&
-           Intersects(query_->start(), query_->end(), pos_->start_, pos_->end_);
-  }
-
-  void Invalidate() {
-    query_ = nullptr;
-    pos_ = intervals_->end();
-  }
-
-  const UseInterval* query_;
-  interval_iterator pos_;
-  IntervalStore* intervals_;
-};
-
-// Collection of live ranges allocated to the same register.
-// It supports efficiently finding all conflicts for a given, non-allocated
-// range. See AllocatedInterval.
-// Allocated live ranges do not intersect. At most, individual use intervals
-// touch. We store, for a live range, an AllocatedInterval corresponding to each
-// of that range's UseIntervals. We keep the list of AllocatedIntervals sorted
-// by starts. Then, given the non-intersecting property, we know that
-// consecutive AllocatedIntervals have the property that the "smaller"'s end is
-// less or equal to the "larger"'s start.
-// This allows for quick (logarithmic complexity) identification of the first
-// AllocatedInterval to conflict with a given LiveRange, and then for efficient
-// traversal of conflicts.
-class CoalescedLiveRanges : public ZoneObject {
- public:
-  explicit CoalescedLiveRanges(Zone* zone) : intervals_(zone) {}
-  void clear() { intervals_.clear(); }
-
-  bool empty() const { return intervals_.empty(); }
-
-  // Iterate over each live range conflicting with the provided one.
-  // The same live range may be observed multiple, but non-consecutive times.
-  LiveRangeConflictIterator GetConflicts(const LiveRange* range);
-
-
-  // Allocates a range with a pre-calculated candidate weight.
-  void AllocateRange(LiveRange* range);
-
-  // Unit testing API, verifying that allocated intervals do not overlap.
-  bool VerifyAllocationsAreValidForTesting() const;
-
- private:
-  static const float kAllocatedRangeMultiplier;
-
-  IntervalStore& intervals() { return intervals_; }
-  const IntervalStore& intervals() const { return intervals_; }
-
-  // Augment the weight of a range that is about to be allocated.
-  static void UpdateWeightAtAllocation(LiveRange* range);
-
-  // Reduce the weight of a range that has lost allocation.
-  static void UpdateWeightAtEviction(LiveRange* range);
-
-
-  IntervalStore intervals_;
-  DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);
-};
-
-
-}  // namespace compiler
-}  // namespace internal
-}  // namespace v8
-#endif  // V8_COALESCED_LIVE_RANGES_H_