diff options
Diffstat (limited to 'deps/v8/src/compiler/coalesced-live-ranges.h')
-rw-r--r-- | deps/v8/src/compiler/coalesced-live-ranges.h | 151 |
1 files changed, 100 insertions, 51 deletions
diff --git a/deps/v8/src/compiler/coalesced-live-ranges.h b/deps/v8/src/compiler/coalesced-live-ranges.h index f12517203f..e617c0a251 100644 --- a/deps/v8/src/compiler/coalesced-live-ranges.h +++ b/deps/v8/src/compiler/coalesced-live-ranges.h @@ -13,8 +13,96 @@ namespace internal { namespace compiler { -class AllocationScheduler; +// 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 @@ -30,45 +118,27 @@ class AllocationScheduler; // traversal of conflicts. class CoalescedLiveRanges : public ZoneObject { public: - explicit CoalescedLiveRanges(Zone* zone) : storage_(zone) {} - void clear() { storage_.clear(); } + explicit CoalescedLiveRanges(Zone* zone) : intervals_(zone) {} + void clear() { intervals_.clear(); } - bool empty() const { return storage_.empty(); } + bool empty() const { return intervals_.empty(); } - // Returns kInvalidWeight if there are no conflicts, or the largest weight of - // a range conflicting with the given range. - float GetMaximumConflictingWeight(const LiveRange* range) const; + // 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); - // Evicts all conflicts of the given range, and reschedules them with the - // provided scheduler. - void EvictAndRescheduleConflicts(LiveRange* range, - AllocationScheduler* scheduler); // Allocates a range with a pre-calculated candidate weight. void AllocateRange(LiveRange* range); - // TODO(mtrofin): remove this in favor of comprehensive unit tests. - bool VerifyAllocationsAreValid() const; + // Unit testing API, verifying that allocated intervals do not overlap. + bool VerifyAllocationsAreValidForTesting() const; private: static const float kAllocatedRangeMultiplier; - // Storage detail for CoalescedLiveRanges. - struct AllocatedInterval { - 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; - typedef IntervalStore::const_iterator interval_iterator; - IntervalStore& storage() { return storage_; } - const IntervalStore& storage() const { return storage_; } + 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); @@ -76,29 +146,8 @@ class CoalescedLiveRanges : public ZoneObject { // Reduce the weight of a range that has lost allocation. static void UpdateWeightAtEviction(LiveRange* range); - // 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; - } - static AllocatedInterval AsAllocatedInterval(LifetimePosition pos) { - return {pos, LifetimePosition::Invalid(), nullptr}; - } - - bool QueryIntersectsAllocatedInterval(const UseInterval* query, - interval_iterator& pos) const { - DCHECK(query != nullptr); - return pos != storage().end() && - Intersects(query->start(), query->end(), pos->start, pos->end); - } - - void Remove(LiveRange* range); - - // Get the first interval intersecting query. Since the intervals are sorted, - // subsequent intervals intersecting query follow. - interval_iterator GetFirstConflict(const UseInterval* query) const; - IntervalStore storage_; + IntervalStore intervals_; DISALLOW_COPY_AND_ASSIGN(CoalescedLiveRanges); }; |