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
LiveRangeConflictIterator(const LiveRange * range,IntervalStore * storage)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
Current() const23 LiveRange* LiveRangeConflictIterator::Current() const {
24 if (IsFinished()) return nullptr;
25 return pos_->range_;
26 }
27
28
MovePosToFirstConflictForQuery()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
MovePosAndQueryToFirstConflict()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
IncrementPosAndSkipOverRepetitions()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
InternalGetNext(bool clean_behind)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
GetConflicts(const LiveRange * range)114 LiveRangeConflictIterator CoalescedLiveRanges::GetConflicts(
115 const LiveRange* range) {
116 return LiveRangeConflictIterator(range, &intervals());
117 }
118
119
AllocateRange(LiveRange * range)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
VerifyAllocationsAreValidForTesting() const129 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
144