[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..8ded7fdbfc9bbcd90fd8b711eeb5112d429236bc 100644
--- a/src/compiler/coalesced-live-ranges.h
+++ b/src/compiler/coalesced-live-ranges.h
@@ -13,9 +13,6 @@ namespace internal {
 namespace compiler {
 
 
-class AllocationScheduler;
-
-
 // Collection of live ranges allocated to the same register.
 // It supports efficiently finding all conflicts for a given, non-allocated
 // range. See AllocatedInterval.
@@ -35,20 +32,47 @@ 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;
+  // Visits each live range conflicting with the provided one. The same live
+  // range may be passed to the visitor multiple, but non-consecutive times.
+  template <typename ConstLiveRangePtrToBool>
+  void VisitConflicts(const LiveRange* range, ConstLiveRangePtrToBool visitor) {

[Benedikt Meurer, 2015/07/14 05:13:04]

Higher order functions which iterate over a data structure, and allow callbacks
to mutate the underlying data structure, are usually a bad idea, esp. in C++
(with STL). IMHO this is worse compared to the conflict_iterator.

What happened to the idea of simple loops? I thought we agreed on that as a
starting point.

[Mircea Trofin, 2015/07/14 15:21:07]

I called this out in the code review description: the starting point suffered
from code duplication and increased concept coupling. Both complicate (and
increase cost of) maintenance and testing.

The starting point wasn't really simple loops either: both
GetMaximumConflictingWeight and EvictAndRescheduleConflicts had to carefully
traverse the set of allocated ranges, and in a very similar way. The difference
between the 2 was subtle and unnecessary (eviction had to skip over successive
intervals of same range, finding max weight could do without that, but didn't
need to). When looking into unit testing, the code duplication became clear.

I'm assuming your concern with potentially mutating visitors is about mutation
invalidating the underlying iterator? I believe the implementation ensures safe
mutation, unless I'm missing something?

[Mircea Trofin, 2015/07/15 05:18:46]

(to capture our discussion) We agreed to move to an iterator - based design,
without attempting to emulate the surface area of STL iterators. Instead, it'll
have explicit "Current" and "Next" and "HasNext" APIs rather than overloaded
operators a'la STL (->, ++, etc)

+    auto end = storage().end();
+    for (auto query = range->first_interval(); query != nullptr;
+         query = query->next()) {
+      auto conflict = GetFirstConflict(query);
+
+      if (conflict == end) continue;
+      while (QueryIntersectsAllocatedInterval(query, conflict)) {
+        LiveRange* range = conflict->range;
+        // Bypass successive intervals belonging to the same range.
+        while (conflict != end && conflict->range == range) {
+          ++conflict;
+        }
+        bool may_continue = visitor(range);
+        if (!may_continue) break;
+      }
+    }
+  }
+
+
+  // Evicts all conflicts of the given range, calling the provided function
+  // for each found conflict.
+  template <typename OnConflictRemoveVisitor>
+  void RemoveConflicts(const LiveRange* range,
+                       OnConflictRemoveVisitor on_conflict_found) {
+    VisitConflicts(range, [this, on_conflict_found](LiveRange* conflict) {
+      Remove(conflict);
+      on_conflict_found(conflict);
+      return true;
+    });
+  }
 
-  // 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;
 
  private:
   static const float kAllocatedRangeMultiplier;
@@ -85,6 +109,7 @@ class CoalescedLiveRanges : public ZoneObject {
     return {pos, LifetimePosition::Invalid(), nullptr};
   }
 
+
   bool QueryIntersectsAllocatedInterval(const UseInterval* query,
                                         interval_iterator& pos) const {
     DCHECK(query != nullptr);