| OLD | NEW |
|---|
| (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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2060673002:
[turbofan] Retiring Greedy Allocator (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master