1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_COALESCED_LIVE_RANGES_H_
#define V8_COALESCED_LIVE_RANGES_H_
#include "src/compiler/register-allocator.h"
#include "src/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
// Implementation detail for CoalescedLiveRanges.
struct AllocatedInterval {
AllocatedInterval(LifetimePosition start, LifetimePosition end,
LiveRange* range)
: start_(start), end_(end), range_(range) {}
LifetimePosition start_;
LifetimePosition end_;
LiveRange* range_;
bool operator<(const AllocatedInterval& other) const {
return start_ < other.start_;
}
bool operator>(const AllocatedInterval& other) const {
return start_ > other.start_;
}
};
typedef ZoneSet<AllocatedInterval> IntervalStore;
// An iterator over conflicts of a live range, obtained from CoalescedLiveRanges
// The design supports two main scenarios (see GreedyAllocator):
// (1) observing each conflicting range, without mutating the allocations, and
// (2) observing each conflicting range, and then moving to the next, after
// removing the current conflict.
class LiveRangeConflictIterator {
public:
// Current conflict. nullptr if no conflicts, or if we reached the end of
// conflicts.
LiveRange* Current() const;
// Get the next conflict. Caller should handle non-consecutive repetitions of
// the same range.
LiveRange* GetNext() { return InternalGetNext(false); }
// Get the next conflict, after evicting the current one. Caller may expect
// to never observe the same live range more than once.
LiveRange* RemoveCurrentAndGetNext() { return InternalGetNext(true); }
private:
friend class CoalescedLiveRanges;
typedef IntervalStore::const_iterator interval_iterator;
LiveRangeConflictIterator(const LiveRange* range, IntervalStore* store);
// Move the store iterator to first interval intersecting query. Since the
// intervals are sorted, subsequent intervals intersecting query follow. May
// leave the store iterator at "end", meaning that the current query does not
// have an intersection.
void MovePosToFirstConflictForQuery();
// Move both query and store iterator to the first intersection, if any. If
// none, then it invalidates the iterator (IsFinished() == true)
void MovePosAndQueryToFirstConflict();
// Increment pos and skip over intervals belonging to the same range we
// started with (i.e. Current() before the call). It is possible that range
// will be seen again, but not consecutively.
void IncrementPosAndSkipOverRepetitions();
// Common implementation used by both GetNext as well as
// ClearCurrentAndGetNext.
LiveRange* InternalGetNext(bool clean_behind);
bool IsFinished() const { return query_ == nullptr; }
static AllocatedInterval AsAllocatedInterval(LifetimePosition pos) {
return AllocatedInterval(pos, LifetimePosition::Invalid(), nullptr);
}
// Intersection utilities.
static bool Intersects(LifetimePosition a_start, LifetimePosition a_end,
LifetimePosition b_start, LifetimePosition b_end) {
return a_start < b_end && b_start < a_end;
}
bool QueryIntersectsAllocatedInterval() const {
DCHECK(query_ != nullptr);
return pos_ != intervals_->end() &&
Intersects(query_->start(), query_->end(), pos_->start_, pos_->end_);
}
void Invalidate() {
query_ = nullptr;
pos_ = intervals_->end();
}
const UseInterval* query_;
interval_iterator pos_;
IntervalStore* intervals_;
};
// Collection of live ranges allocated to the same register.
// It supports efficiently finding all conflicts for a given, non-allocated
// range. See AllocatedInterval.
// Allocated live ranges do not intersect. At most, individual use intervals
// touch. We store, for a live range, an AllocatedInterval corresponding to each
// of that range's UseIntervals. We keep the list of AllocatedIntervals sorted
// by starts. Then, given the non-intersecting property, we know that
// consecutive AllocatedIntervals have the property that the "smaller"'s end is
// less or equal to the "larger"'s start.
// This allows for quick (logarithmic complexity) identification of the first
// AllocatedInterval to conflict with a given LiveRange, and then for efficient
// traversal of conflicts.
class CoalescedLiveRanges : public ZoneObject {
public:
explicit CoalescedLiveRanges(Zone* zone) : intervals_(zone) {}
void clear() { intervals_.clear(); }
bool empty() const { return intervals_.empty(); }
// Iterate over each live range conflicting with the provided one.
// The same live range may be observed multiple, but non-consecutive times.
LiveRangeConflictIterator GetConflicts(const LiveRange* range);
// Allocates a range with a pre-calculated candidate weight.
void AllocateRange(LiveRange* range);
// Unit testing API, verifying that allocated intervals do not overlap.
bool VerifyAllocationsAreValidForTesting() const;
private:
static const float kAllocatedRangeMultiplier;
IntervalStore& intervals() { return intervals_; }
const IntervalStore& intervals() const { return intervals_; }
// Augment the weight of a range that is about to be allocated.
static void UpdateWeightAtAllocation(LiveRange* range);
// Reduce the weight of a range that has lost allocation.
static void UpdateWeightAtEviction(LiveRange* range);
IntervalStore intervals_;
DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges);
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COALESCED_LIVE_RANGES_H_
|
