| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2015 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 "src/compiler/greedy-allocator.h" | |
| 7 #include "src/compiler/register-allocator.h" | |
| 8 | |
| 9 namespace v8 { | |
| 10 namespace internal { | |
| 11 namespace compiler { | |
| 12 | |
| 13 | |
| 14 LiveRangeConflictIterator::LiveRangeConflictIterator(const LiveRange* range, | |
| 15 IntervalStore* storage) | |
| 16 : query_(range->first_interval()), | |
| 17 pos_(storage->end()), | |
| 18 intervals_(storage) { | |
| 19 MovePosAndQueryToFirstConflict(); | |
| 20 } | |
| 21 | |
| 22 | |
| 23 LiveRange* LiveRangeConflictIterator::Current() const { | |
| 24 if (IsFinished()) return nullptr; | |
| 25 return pos_->range_; | |
| 26 } | |
| 27 | |
| 28 | |
| 29 void LiveRangeConflictIterator::MovePosToFirstConflictForQuery() { | |
| 30 DCHECK_NOT_NULL(query_); | |
| 31 auto end = intervals_->end(); | |
| 32 LifetimePosition q_start = query_->start(); | |
| 33 LifetimePosition q_end = query_->end(); | |
| 34 | |
| 35 if (intervals_->empty() || intervals_->rbegin()->end_ <= q_start || | |
| 36 intervals_->begin()->start_ >= q_end) { | |
| 37 pos_ = end; | |
| 38 return; | |
| 39 } | |
| 40 | |
| 41 pos_ = intervals_->upper_bound(AsAllocatedInterval(q_start)); | |
| 42 // pos is either at the end (no start strictly greater than q_start) or | |
| 43 // at some position with the aforementioned property. In either case, the | |
| 44 // allocated interval before this one may intersect our query: | |
| 45 // either because, although it starts before this query's start, it ends | |
| 46 // after; or because it starts exactly at the query start. So unless we're | |
| 47 // right at the beginning of the storage - meaning the first allocated | |
| 48 // interval is also starting after this query's start - see what's behind. | |
| 49 if (pos_ != intervals_->begin()) { | |
| 50 --pos_; | |
| 51 if (!QueryIntersectsAllocatedInterval()) { | |
| 52 // The interval behind wasn't intersecting, so move back. | |
| 53 ++pos_; | |
| 54 } | |
| 55 } | |
| 56 if (pos_ == end || !QueryIntersectsAllocatedInterval()) { | |
| 57 pos_ = end; | |
| 58 } | |
| 59 } | |
| 60 | |
| 61 | |
| 62 void LiveRangeConflictIterator::MovePosAndQueryToFirstConflict() { | |
| 63 auto end = intervals_->end(); | |
| 64 for (; query_ != nullptr; query_ = query_->next()) { | |
| 65 MovePosToFirstConflictForQuery(); | |
| 66 if (pos_ != end) { | |
| 67 DCHECK(QueryIntersectsAllocatedInterval()); | |
| 68 return; | |
| 69 } | |
| 70 } | |
| 71 | |
| 72 Invalidate(); | |
| 73 } | |
| 74 | |
| 75 | |
| 76 void LiveRangeConflictIterator::IncrementPosAndSkipOverRepetitions() { | |
| 77 auto end = intervals_->end(); | |
| 78 DCHECK(pos_ != end); | |
| 79 LiveRange* current_conflict = Current(); | |
| 80 while (pos_ != end && pos_->range_ == current_conflict) { | |
| 81 ++pos_; | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 | |
| 86 LiveRange* LiveRangeConflictIterator::InternalGetNext(bool clean_behind) { | |
| 87 if (IsFinished()) return nullptr; | |
| 88 | |
| 89 LiveRange* to_clear = Current(); | |
| 90 IncrementPosAndSkipOverRepetitions(); | |
| 91 // At this point, pos_ is either at the end, or on an interval that doesn't | |
| 92 // correspond to the same range as to_clear. This interval may not even be | |
| 93 // a conflict. | |
| 94 if (clean_behind) { | |
| 95 // Since we parked pos_ on an iterator that won't be affected by removal, | |
| 96 // we can safely delete to_clear's intervals. | |
| 97 for (auto interval = to_clear->first_interval(); interval != nullptr; | |
| 98 interval = interval->next()) { | |
| 99 AllocatedInterval erase_key(interval->start(), interval->end(), nullptr); | |
| 100 intervals_->erase(erase_key); | |
| 101 } | |
| 102 } | |
| 103 // We may have parked pos_ at the end, or on a non-conflict. In that case, | |
| 104 // move to the next query and reinitialize pos and query. This may invalidate | |
| 105 // the iterator, if no more conflicts are available. | |
| 106 if (!QueryIntersectsAllocatedInterval()) { | |
| 107 query_ = query_->next(); | |
| 108 MovePosAndQueryToFirstConflict(); | |
| 109 } | |
| 110 return Current(); | |
| 111 } | |
| 112 | |
| 113 | |
| 114 LiveRangeConflictIterator CoalescedLiveRanges::GetConflicts( | |
| 115 const LiveRange* range) { | |
| 116 return LiveRangeConflictIterator(range, &intervals()); | |
| 117 } | |
| 118 | |
| 119 | |
| 120 void CoalescedLiveRanges::AllocateRange(LiveRange* range) { | |
| 121 for (auto interval = range->first_interval(); interval != nullptr; | |
| 122 interval = interval->next()) { | |
| 123 AllocatedInterval to_insert(interval->start(), interval->end(), range); | |
| 124 intervals().insert(to_insert); | |
| 125 } | |
| 126 } | |
| 127 | |
| 128 | |
| 129 bool CoalescedLiveRanges::VerifyAllocationsAreValidForTesting() const { | |
| 130 LifetimePosition last_end = LifetimePosition::GapFromInstructionIndex(0); | |
| 131 for (auto i : intervals_) { | |
| 132 if (i.start_ < last_end) { | |
| 133 return false; | |
| 134 } | |
| 135 last_end = i.end_; | |
| 136 } | |
| 137 return true; | |
| 138 } | |
| 139 | |
| 140 | |
| 141 } // namespace compiler | |
| 142 } // namespace internal | |
| 143 } // namespace v8 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2060673002:
[turbofan] Retiring Greedy Allocator (Closed)
Base URL: https://chromium.googlesource.com/v8/v8.git@master