| // 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_ |