[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;
-
-
 // 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;
+  // 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);
 
-  // Evicts all conflicts of the given range, and reschedules them with the
-  // provided scheduler.
-  void EvictAndRescheduleConflicts(LiveRange* range,
-                                   AllocationScheduler* scheduler);
+      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;
+    });
+  }
+
 
   // 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;
   // Storage detail for CoalescedLiveRanges.
   struct AllocatedInterval {
     LifetimePosition start;
     LifetimePosition end;
     LiveRange* range;
     bool operator<(const AllocatedInterval& other) const {
       return start < other.start;
@@ skipping 16 matching lines @@
 
   // 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_