Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(10)

Side by Side Diff: test/unittests/compiler/coalesced-live-ranges-unittest.cc

Issue 2060673002: [turbofan] Retiring Greedy Allocator (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 4 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « test/unittests/BUILD.gn ('k') | test/unittests/compiler/register-allocator-unittest.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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
9 namespace v8 {
10 namespace internal {
11 namespace compiler {
12
13
14 class 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
33 bool CoalescedLiveRangesTest::ConflictsPreciselyWith(const LiveRange* range,
34 int id) {
35 LiveRangeIDs set(zone());
36 set.insert(id);
37 return IsRangeConflictingWith(range, set);
38 }
39
40
41 bool 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
50 bool CoalescedLiveRangesTest::HasNoConflicts(const LiveRange* range) {
51 LiveRangeIDs set(zone());
52 return IsRangeConflictingWith(range, set);
53 }
54
55
56 void 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
68 bool CoalescedLiveRangesTest::AllocationsAreValid() const {
69 return ranges().VerifyAllocationsAreValidForTesting();
70 }
71
72
73 bool 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
86 TEST_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
94 TEST_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
106 TEST_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
120 TEST_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
132 TEST_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
144 TEST_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
156 TEST_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
164 TEST_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
172 TEST_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
181 TEST_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
192 TEST_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
202 TEST_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
214 TEST_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
226 TEST_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
239 TEST_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
252 TEST_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
OLDNEW
« no previous file with comments | « test/unittests/BUILD.gn ('k') | test/unittests/compiler/register-allocator-unittest.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698