Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(77)

Side by Side Diff: src/compiler/coalesced-live-ranges.cc

Issue 2060673002: [turbofan] Retiring Greedy Allocator (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 4 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/coalesced-live-ranges.h ('k') | src/compiler/greedy-allocator.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(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
OLDNEW
« no previous file with comments | « src/compiler/coalesced-live-ranges.h ('k') | src/compiler/greedy-allocator.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698