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

Unified Diff: src/compiler/coalesced-live-ranges.h

Issue 1219063017: [turbofan] Unit tests for live range conflicts. (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Created 5 years, 5 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 side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | src/compiler/coalesced-live-ranges.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/compiler/coalesced-live-ranges.h
diff --git a/src/compiler/coalesced-live-ranges.h b/src/compiler/coalesced-live-ranges.h
index f12517203f844e4a71a68e77eaff21eb16f67eff..e617c0a25194bd38b43f93dc8a2c99b5307f29b5 100644
--- a/src/compiler/coalesced-live-ranges.h
+++ b/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);
};
« no previous file with comments | « no previous file | src/compiler/coalesced-live-ranges.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698