1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/coalesced-live-ranges.h"
6#include "test/unittests/compiler/live-range-builder.h"
7#include "test/unittests/test-utils.h"
8
9namespace v8 {
10namespace internal {
11namespace compiler {
12
13
14class CoalescedLiveRangesTest : public TestWithZone {
15 public:
16  CoalescedLiveRangesTest() : TestWithZone(), ranges_(zone()) {}
17  bool HasNoConflicts(const LiveRange* range);
18  bool ConflictsPreciselyWith(const LiveRange* range, int id);
19  bool ConflictsPreciselyWith(const LiveRange* range, int id1, int id2);
20
21  CoalescedLiveRanges& ranges() { return ranges_; }
22  const CoalescedLiveRanges& ranges() const { return ranges_; }
23  bool AllocationsAreValid() const;
24  void RemoveConflicts(LiveRange* range);
25
26 private:
27  typedef ZoneSet<int> LiveRangeIDs;
28  bool IsRangeConflictingWith(const LiveRange* range, const LiveRangeIDs& ids);
29  CoalescedLiveRanges ranges_;
30};
31
32
33bool CoalescedLiveRangesTest::ConflictsPreciselyWith(const LiveRange* range,
34                                                     int id) {
35  LiveRangeIDs set(zone());
36  set.insert(id);
37  return IsRangeConflictingWith(range, set);
38}
39
40
41bool CoalescedLiveRangesTest::ConflictsPreciselyWith(const LiveRange* range,
42                                                     int id1, int id2) {
43  LiveRangeIDs set(zone());
44  set.insert(id1);
45  set.insert(id2);
46  return IsRangeConflictingWith(range, set);
47}
48
49
50bool CoalescedLiveRangesTest::HasNoConflicts(const LiveRange* range) {
51  LiveRangeIDs set(zone());
52  return IsRangeConflictingWith(range, set);
53}
54
55
56void CoalescedLiveRangesTest::RemoveConflicts(LiveRange* range) {
57  auto conflicts = ranges().GetConflicts(range);
58  LiveRangeIDs seen(zone());
59  for (auto c = conflicts.Current(); c != nullptr;
60       c = conflicts.RemoveCurrentAndGetNext()) {
61    int id = c->TopLevel()->vreg();
62    EXPECT_FALSE(seen.count(id) > 0);
63    seen.insert(c->TopLevel()->vreg());
64  }
65}
66
67
68bool CoalescedLiveRangesTest::AllocationsAreValid() const {
69  return ranges().VerifyAllocationsAreValidForTesting();
70}
71
72
73bool CoalescedLiveRangesTest::IsRangeConflictingWith(const LiveRange* range,
74                                                     const LiveRangeIDs& ids) {
75  LiveRangeIDs found_ids(zone());
76
77  auto conflicts = ranges().GetConflicts(range);
78  for (auto conflict = conflicts.Current(); conflict != nullptr;
79       conflict = conflicts.GetNext()) {
80    found_ids.insert(conflict->TopLevel()->vreg());
81  }
82  return found_ids == ids;
83}
84
85
86TEST_F(CoalescedLiveRangesTest, VisitEmptyAllocations) {
87  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
88  ASSERT_TRUE(ranges().empty());
89  ASSERT_TRUE(AllocationsAreValid());
90  ASSERT_TRUE(HasNoConflicts(range));
91}
92
93
94TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterAllocations) {
95  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(5, 6);
96  ranges().AllocateRange(range);
97  ASSERT_FALSE(ranges().empty());
98  ASSERT_TRUE(AllocationsAreValid());
99  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 2);
100  ASSERT_TRUE(HasNoConflicts(query));
101  query = TestRangeBuilder(zone()).Id(3).Build(1, 5);
102  ASSERT_TRUE(HasNoConflicts(query));
103}
104
105
106TEST_F(CoalescedLiveRangesTest, CandidateBeforeAfterManyAllocations) {
107  LiveRange* range =
108      TestRangeBuilder(zone()).Id(1).Add(5, 7).Add(10, 12).Build();
109  ranges().AllocateRange(range);
110  ASSERT_FALSE(ranges().empty());
111  ASSERT_TRUE(AllocationsAreValid());
112  LiveRange* query =
113      TestRangeBuilder(zone()).Id(2).Add(1, 2).Add(13, 15).Build();
114  ASSERT_TRUE(HasNoConflicts(query));
115  query = TestRangeBuilder(zone()).Id(3).Add(1, 5).Add(12, 15).Build();
116  ASSERT_TRUE(HasNoConflicts(query));
117}
118
119
120TEST_F(CoalescedLiveRangesTest, SelfConflictsPreciselyWithSelf) {
121  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
122  ranges().AllocateRange(range);
123  ASSERT_FALSE(ranges().empty());
124  ASSERT_TRUE(AllocationsAreValid());
125  ASSERT_TRUE(ConflictsPreciselyWith(range, 1));
126  range = TestRangeBuilder(zone()).Id(2).Build(8, 10);
127  ranges().AllocateRange(range);
128  ASSERT_TRUE(ConflictsPreciselyWith(range, 2));
129}
130
131
132TEST_F(CoalescedLiveRangesTest, QueryStartsBeforeConflict) {
133  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5);
134  ranges().AllocateRange(range);
135  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 3);
136  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
137  range = TestRangeBuilder(zone()).Id(3).Build(8, 10);
138  ranges().AllocateRange(range);
139  query = TestRangeBuilder(zone()).Id(4).Build(6, 9);
140  ASSERT_TRUE(ConflictsPreciselyWith(query, 3));
141}
142
143
144TEST_F(CoalescedLiveRangesTest, QueryStartsInConflict) {
145  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 5);
146  ranges().AllocateRange(range);
147  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(3, 6);
148  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
149  range = TestRangeBuilder(zone()).Id(3).Build(8, 10);
150  ranges().AllocateRange(range);
151  query = TestRangeBuilder(zone()).Id(4).Build(9, 11);
152  ASSERT_TRUE(ConflictsPreciselyWith(query, 3));
153}
154
155
156TEST_F(CoalescedLiveRangesTest, QueryContainedInConflict) {
157  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
158  ranges().AllocateRange(range);
159  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 3);
160  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
161}
162
163
164TEST_F(CoalescedLiveRangesTest, QueryContainsConflict) {
165  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(2, 3);
166  ranges().AllocateRange(range);
167  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(1, 5);
168  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
169}
170
171
172TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsSameRange) {
173  LiveRange* range =
174      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(7, 9).Add(20, 25).Build();
175  ranges().AllocateRange(range);
176  LiveRange* query = TestRangeBuilder(zone()).Id(2).Build(2, 8);
177  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
178}
179
180
181TEST_F(CoalescedLiveRangesTest, QueryCoversManyIntervalsDifferentRanges) {
182  LiveRange* range =
183      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(20, 25).Build();
184  ranges().AllocateRange(range);
185  range = TestRangeBuilder(zone()).Id(2).Build(7, 10);
186  ranges().AllocateRange(range);
187  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(2, 22);
188  ASSERT_TRUE(ConflictsPreciselyWith(query, 1, 2));
189}
190
191
192TEST_F(CoalescedLiveRangesTest, QueryFitsInGaps) {
193  LiveRange* range =
194      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 15).Add(20, 25).Build();
195  ranges().AllocateRange(range);
196  LiveRange* query =
197      TestRangeBuilder(zone()).Id(3).Add(5, 10).Add(16, 19).Add(27, 30).Build();
198  ASSERT_TRUE(HasNoConflicts(query));
199}
200
201
202TEST_F(CoalescedLiveRangesTest, DeleteConflictBefore) {
203  LiveRange* range = TestRangeBuilder(zone()).Id(1).Add(1, 4).Add(5, 6).Build();
204  ranges().AllocateRange(range);
205  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
206  ranges().AllocateRange(range);
207  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(3, 7);
208  RemoveConflicts(query);
209  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
210  ASSERT_TRUE(ConflictsPreciselyWith(query, 2));
211}
212
213
214TEST_F(CoalescedLiveRangesTest, DeleteConflictAfter) {
215  LiveRange* range = TestRangeBuilder(zone()).Id(1).Build(1, 5);
216  ranges().AllocateRange(range);
217  range = TestRangeBuilder(zone()).Id(2).Add(40, 50).Add(60, 70).Build();
218  ranges().AllocateRange(range);
219  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(45, 60);
220  RemoveConflicts(query);
221  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
222  ASSERT_TRUE(ConflictsPreciselyWith(query, 1));
223}
224
225
226TEST_F(CoalescedLiveRangesTest, DeleteConflictStraddle) {
227  LiveRange* range =
228      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(10, 20).Build();
229  ranges().AllocateRange(range);
230  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
231  ranges().AllocateRange(range);
232  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15);
233  RemoveConflicts(query);
234  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
235  ASSERT_TRUE(ConflictsPreciselyWith(query, 2));
236}
237
238
239TEST_F(CoalescedLiveRangesTest, DeleteConflictManyOverlapsBefore) {
240  LiveRange* range =
241      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(6, 10).Add(10, 20).Build();
242  ranges().AllocateRange(range);
243  range = TestRangeBuilder(zone()).Id(2).Build(40, 50);
244  ranges().AllocateRange(range);
245  LiveRange* query = TestRangeBuilder(zone()).Id(3).Build(4, 15);
246  RemoveConflicts(query);
247  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
248  ASSERT_TRUE(ConflictsPreciselyWith(query, 2));
249}
250
251
252TEST_F(CoalescedLiveRangesTest, DeleteWhenConflictRepeatsAfterNonConflict) {
253  LiveRange* range =
254      TestRangeBuilder(zone()).Id(1).Add(1, 5).Add(6, 10).Add(20, 30).Build();
255  ranges().AllocateRange(range);
256  range = TestRangeBuilder(zone()).Id(2).Build(12, 15);
257  ranges().AllocateRange(range);
258  LiveRange* query =
259      TestRangeBuilder(zone()).Id(3).Add(1, 8).Add(22, 25).Build();
260  RemoveConflicts(query);
261  query = TestRangeBuilder(zone()).Id(4).Build(0, 60);
262  ASSERT_TRUE(ConflictsPreciselyWith(query, 2));
263}
264
265
266}  // namespace compiler
267}  // namespace internal
268}  // namespace v8
269