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 269
