[turbofan] Unit tests for live range conflicts.

test/unittests/compiler/coalesced-live-ranges-unittest.cc

+// Copyright 2014 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.
+
+#include "src/compiler/coalesced-live-ranges.h"
+#include "test/unittests/test-utils.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+
+// Utility offering shorthand syntax for building up a range by providing its ID
+// and pairs (start, end) specifying intervals. Circumvents current incomplete
+// support for C++ features such as instantiation lists, on OS X and Android.
+class TestRangeBuilder {
+ public:
+  explicit TestRangeBuilder(Zone* zone) : id_(-1), pairs_(), zone_(zone) {}
+
+  TestRangeBuilder& Id(int id) {
+    id_ = id;
+    return *this;
+  }
+  TestRangeBuilder& Add(int start, int end) {
+    pairs_.push_back({start, end});
+    return *this;
+  }
+
+  LiveRange* Build(int start, int end) { return Add(start, end).Build(); }
+
+  LiveRange* Build() {
+    LiveRange* range = new (zone_) LiveRange(id_, MachineType::kRepTagged);
+    // Traverse the provided interval specifications backwards, because that is
+    // what LiveRange expects.
+    for (int i = static_cast<int>(pairs_.size()) - 1; i >= 0; --i) {
+      auto pair = pairs_[i];
+      LifetimePosition start = LifetimePosition::FromInt(pair.first);
+      LifetimePosition end = LifetimePosition::FromInt(pair.second);
+      CHECK(start < end);
+      range->AddUseInterval(start, end, zone_);
+    }
+
+    pairs_.clear();
+    return range;
+  }
+
+ private:
+  typedef std::pair<int, int> Interval;
+  typedef std::vector<Interval> IntervalList;
+  int id_;
+  IntervalList pairs_;
+  Zone* zone_;
+};
+
+
+typedef std::set<int> LiveRangeIDs;
+
+
+// Utility offering shorthand building of a set of integers. Circumvents current
+// incomplete support for C++ features such as instantiation lists, on OS X and
+// Android.
+class Conflicts {
+ public:
+  Conflicts(int number_of_conflicts, ...) : set_() {

[Benedikt Meurer, 2015/07/14 04:35:01]

Do we really need to use varargs here? You could apply the builder pattern again
instead.

[Mircea Trofin, 2015/07/14 16:19:18]

Agreed, and even easier, since the purpose was simplifying authoring lists of
range IDs, and it turned out I just needed 0 (no conflicts), 1, or 2 conflicts,
I removed the entire builder for this scenario.

In contrast, there's still a benefit for the builder for LiveRange authoring,
because the data structures (pairs) are more complex.

+    CHECK(number_of_conflicts > 0);
+    va_list conflict_list;
+    va_start(conflict_list, number_of_conflicts);
+    for (int i = 0; i < number_of_conflicts; ++i) {
+      int val = va_arg(conflict_list, int);
+      set_.insert(val);
+    }
+    va_end(conflict_list);
+  }
+
+  operator LiveRangeIDs&() { return set_; }

[Benedikt Meurer, 2015/07/14 04:35:01]

Same here, there's no need for operator overloading.

[Mircea Trofin, 2015/07/14 16:19:18]

Done.

+  static LiveRangeIDs& None() { return empty_set; }
+
+ private:
+  static LiveRangeIDs empty_set;
+  LiveRangeIDs set_;
+};
+
+LiveRangeIDs Conflicts::empty_set;
+
+class CoalescedLiveRangesTest : public TestWithZone {
+ public:
+  CoalescedLiveRangesTest() : TestWithZone(), ranges_(zone()) {}
+  bool CheckConflictsMatch(const LiveRange* range, const LiveRangeIDs& ids);
+
+  CoalescedLiveRanges& ranges() { return ranges_; }
+  const CoalescedLiveRanges& ranges() const { return ranges_; }
+  bool AllocationsAreValid() const;
+  void RemoveConflicts(LiveRange* range);
+
+ private:
+  CoalescedLiveRanges ranges_;
+};
+
+
+void CoalescedLiveRangesTest::RemoveConflicts(LiveRange* range) {
+  ranges().RemoveConflicts(range, [](LiveRange* conflict) {});
+}
+
+
+bool CoalescedLiveRangesTest::AllocationsAreValid() const {
+  return ranges().TestOnlyVerifyAllocationsAreValid();
+}
+
+
+bool CoalescedLiveRangesTest::CheckConflictsMatch(const LiveRange* range,
+                                                  const LiveRangeIDs& ids) {
+  LiveRangeIDs found_ids;
+
+  ranges().VisitConflicts(range, [&](const LiveRange* conflict) {
+    found_ids.insert(conflict->id());
+    return true;
+  });
+  return found_ids == ids;
+}
+
+
+TEST_F(CoalescedLiveRangesTest, VisitEmptyAllocations) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
+  ASSERT_TRUE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  ASSERT_TRUE(CheckConflictsMatch(range, Conflicts::None()));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterAllocations) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(5, 6);
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 2);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts::None()));
+  query = TestRangeBuilder(zone()).Id(3).Build(1, 5);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts::None()));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterManyAllocations) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(5, 7).Add(10, 12).Build();
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  LiveRange* query =
+      TestRangeBuilder(zone()).Id(2).Add(1, 2).Add(13, 15).Build();
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts::None()));
+  query = TestRangeBuilder(zone()).Id(3).Add(1, 5).Add(12, 15).Build();
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts::None()));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, SelfConflictsWithSelf) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  ASSERT_TRUE(CheckConflictsMatch(range, Conflicts(1, 1)));
+  range = TestRangeBuilder(zone()).Id(2).Build(8, 10);
+  ranges().AllocateRange(range);
+  ASSERT_TRUE(CheckConflictsMatch(range, Conflicts(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryStartsBeforeConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 3);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+  range = TestRangeBuilder(zone()).Id(3).Build(8, 10);
+  ranges().AllocateRange(range);
+  query = TestRangeBuilder(zone()).Id(4).Build(6, 9);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 3)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryStartsInConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(3, 6);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+  range = TestRangeBuilder(zone()).Id(3).Build(8, 10);
+  ranges().AllocateRange(range);
+  query = TestRangeBuilder(zone()).Id(4).Build(9, 11);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 3)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryContainedInConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 3);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryContainsConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 3);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 5);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsSameRange) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(7, 9).Add(20, 25).Build();
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 8);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsDifferentRanges) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(20, 25).Build();
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2).Build(7, 10);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(2, 22);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(2, 1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryFitsInGaps) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 15).Add(20, 25).Build();
+  ranges().AllocateRange(range);
+  LiveRange* query =
+      TestRangeBuilder(zone()).Id(3).Add(5, 10).Add(16, 19).Add(27, 30).Build();
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts::None()));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictBefore) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Add(1, 4).Add(5, 6).Build();
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(3, 7);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictAfter) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2).Add(40, 50).Add(60, 70).Build();
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(45, 60);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictStraddle) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 20).Build();
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictManyOverlapsBefore) {
+  LiveRange* range =
+      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(6, 10).Add(10, 20).Build();
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, Conflicts(1, 2)));
+}
+
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8