[turbofan] Unit tests for live range conflicts.

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 {
 
 
-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
 // 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) : storage_(zone) {}
   void clear() { storage_.clear(); }
 
   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_; }
 
   // 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);
 
-  // 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);
 };
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 #endif  // V8_COALESCED_LIVE_RANGES_H_