[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& operator()(int start, int end) {

[Benedikt Meurer, 2015/07/13 05:01:25]

Operator overloading is strongly discouraged. Please just use an Add method for
that.

[Mircea Trofin, 2015/07/13 16:54:07]

Done.

+    pairs_.push_back({start, end});
+    return *this;
+  }
+  operator LiveRange*() {

[Benedikt Meurer, 2015/07/13 05:01:25]

How about a Build method instead?

[Mircea Trofin, 2015/07/13 16:54:07]

Done.

+    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 TestSetBuilder {
+ public:
+  TestSetBuilder(int count, ...) {
+    va_list list;
+    va_start(list, count);
+    for (int i = 0; i < count; ++i) {
+      int val = va_arg(list, int);
+      set_.insert(val);
+    }
+    va_end(list);
+  }
+
+  operator LiveRangeIDs&() { return set_; }
+
+ private:
+  LiveRangeIDs 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)(1, 5);
+  ASSERT_TRUE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  ASSERT_TRUE(CheckConflictsMatch(range, TestSetBuilder(0)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterAllocations) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(5, 6);
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(1, 2);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(0)));
+  query = TestRangeBuilder(zone()).Id(3)(1, 5);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(0)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterManyAllocations) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(5, 7)(10, 12);
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(1, 2)(13, 15);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(0)));
+  query = TestRangeBuilder(zone()).Id(3)(1, 5)(12, 15);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(0)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, SelfConflictsWithSelf) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5);
+  ranges().AllocateRange(range);
+  ASSERT_FALSE(ranges().empty());
+  ASSERT_TRUE(AllocationsAreValid());
+  ASSERT_TRUE(CheckConflictsMatch(range, TestSetBuilder(1, 1)));
+  range = TestRangeBuilder(zone()).Id(2)(8, 10);
+  ranges().AllocateRange(range);
+  ASSERT_TRUE(CheckConflictsMatch(range, TestSetBuilder(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryStartsBeforeConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(2, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(1, 3);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+  range = TestRangeBuilder(zone()).Id(3)(8, 10);
+  ranges().AllocateRange(range);
+  query = TestRangeBuilder(zone()).Id(4)(6, 9);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 3)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryStartsInConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(2, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(3, 6);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+  range = TestRangeBuilder(zone()).Id(3)(8, 10);
+  ranges().AllocateRange(range);
+  query = TestRangeBuilder(zone()).Id(4)(9, 11);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 3)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryContainedInConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(2, 3);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryContainsConflict) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(2, 3);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(1, 5);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsSameRange) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5)(7, 9)(20, 25);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(2)(2, 8);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsDifferentRanges) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5)(20, 25);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2)(7, 10);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(2, 22);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(2, 1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, QueryFitsInGaps) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5)(10, 15)(20, 25);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(5, 10)(16, 19)(27, 30);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(0)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictBefore) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 4)(5, 6);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2)(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(3, 7);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4)(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictAfter) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2)(40, 50)(60, 70);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(45, 60);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4)(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 1)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictStraddle) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5)(10, 20);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2)(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(4, 15);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4)(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 2)));
+}
+
+
+TEST_F(CoalescedLiveRangesTest, DeleteConflictManyOverlapsBefore) {
+  LiveRange* range = TestRangeBuilder(zone()).Id(1)(1, 5)(6, 10)(10, 20);
+  ranges().AllocateRange(range);
+  range = TestRangeBuilder(zone()).Id(2)(40, 50);
+  ranges().AllocateRange(range);
+  LiveRange* query = TestRangeBuilder(zone()).Id(3)(4, 15);
+  RemoveConflicts(query);
+  query = TestRangeBuilder(zone()).Id(4)(0, 60);
+  ASSERT_TRUE(CheckConflictsMatch(query, TestSetBuilder(1, 2)));
+}
+
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8