[turbofan] Unit tests for live range conflicts.

src/compiler/coalesced-live-ranges.h

Index: src/compiler/coalesced-live-ranges.h
diff --git a/src/compiler/coalesced-live-ranges.h b/src/compiler/coalesced-live-ranges.h
index f12517203f844e4a71a68e77eaff21eb16f67eff..1ba340e3dd6fc535aae60605504e811d19a72b7e 100644
--- a/src/compiler/coalesced-live-ranges.h
+++ b/src/compiler/coalesced-live-ranges.h
@@ -13,8 +13,92 @@ namespace internal {
 namespace compiler {
 
 
-class AllocationScheduler;
+// Storage detail for CoalescedLiveRanges.
+struct AllocatedInterval {
+  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* ClearCurrentAndGetNext() { return InternalGetNext(true); }

[Jarin, 2015/07/21 08:51:18]

ClearCurrent seems ambiguous to me, it sounds like it is somehow invalidating
the current range.

How about EvictCurrentAndGetNext, then? (Or RemoveCurrentAndGetNext.)

[Mircea Trofin, 2015/07/21 14:51:01]

Done.

+
+ 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 {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(query_ != nullptr);
+    return pos_ != storage_->end() &&
+           Intersects(query_->start(), query_->end(), pos_->start, pos_->end);
+  }
+
+  void Invalidate() {
+    query_ = nullptr;
+    pos_ = storage_->end();
+  }
+
+  const UseInterval* query_;
+  interval_iterator pos_;
+  IntervalStore* storage_;

[Jarin, 2015/07/21 08:51:18]

Could we please move away from the 'storage_' name? It does not say at all what
the field is (every field is in essence storage). How about intervals_?

[Mircea Trofin, 2015/07/21 14:51:01]

Done.

+};
 
 // Collection of live ranges allocated to the same register.
 // It supports efficiently finding all conflicts for a given, non-allocated
@@ -35,37 +119,19 @@ class CoalescedLiveRanges : public ZoneObject {
 
   bool empty() const { return storage_.empty(); }
 
-  // Returns kInvalidWeight if there are no conflicts, or the largest weight of
-  // a range conflicting with the given range.
-  float GetMaximumConflictingWeight(const LiveRange* range) const;
+  // 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);
 
-  // Evicts all conflicts of the given range, and reschedules them with the
-  // provided scheduler.
-  void EvictAndRescheduleConflicts(LiveRange* range,
-                                   AllocationScheduler* scheduler);
 
   // Allocates a range with a pre-calculated candidate weight.
   void AllocateRange(LiveRange* range);
 
-  // TODO(mtrofin): remove this in favor of comprehensive unit tests.
-  bool VerifyAllocationsAreValid() const;
+  // Unit testing API, verifying that allocated intervals do not overlap.
+  bool TestOnlyVerifyAllocationsAreValid() const;

[Jarin, 2015/07/21 08:51:18]

TestOnlyVerifyAllocationsAreValid -> VerifyAllocationsAreValidForTesting

The Chrome convention is to add the ForTesting suffix (and there are some rough
checks that aim to detect calls from production code to testing code (i.e.,
methods without the ForTesting suffix calling methods with the ForTesting
suffix).

[Mircea Trofin, 2015/07/21 14:51:01]

Ah, it was a suffix. Done.

 
  private:
   static const float kAllocatedRangeMultiplier;
-  // Storage detail for CoalescedLiveRanges.
-  struct AllocatedInterval {
-    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;
-  typedef IntervalStore::const_iterator interval_iterator;
 
   IntervalStore& storage() { return storage_; }

[Jarin, 2015/07/21 08:51:18]

Again, could we rename storage -> intervals.

[Mircea Trofin, 2015/07/21 14:51:01]

Done.

   const IntervalStore& storage() const { return storage_; }
@@ -76,27 +142,6 @@ class CoalescedLiveRanges : public ZoneObject {
   // Reduce the weight of a range that has lost allocation.
   static void UpdateWeightAtEviction(LiveRange* range);
 
-  // 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;
-  }
-  static AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
-    return {pos, LifetimePosition::Invalid(), nullptr};
-  }
-
-  bool QueryIntersectsAllocatedInterval(const UseInterval* query,
-                                        interval_iterator& pos) const {
-    DCHECK(query != nullptr);
-    return pos != storage().end() &&
-           Intersects(query->start(), query->end(), pos->start, pos->end);
-  }
-
-  void Remove(LiveRange* range);
-
-  // Get the first interval intersecting query. Since the intervals are sorted,
-  // subsequent intervals intersecting query follow.
-  interval_iterator GetFirstConflict(const UseInterval* query) const;
 
   IntervalStore storage_;
   DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);