Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |