Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
FPIIM-449
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/compiler/coalesced-live-ranges.cc b/src/compiler/coalesced-live-ranges.cc
new file mode 100644
index 0000000..4ac3e21
--- /dev/null
+++ b/src/compiler/coalesced-live-ranges.cc
@@ -0,0 +1,143 @@
+// 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.
+
+#include "src/compiler/coalesced-live-ranges.h"
+#include "src/compiler/greedy-allocator.h"
+#include "src/compiler/register-allocator.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+
+LiveRangeConflictIterator::LiveRangeConflictIterator(const LiveRange* range,
+ IntervalStore* storage)
+ : query_(range->first_interval()),
+ pos_(storage->end()),
+ intervals_(storage) {
+ MovePosAndQueryToFirstConflict();
+}
+
+
+LiveRange* LiveRangeConflictIterator::Current() const {
+ if (IsFinished()) return nullptr;
+ return pos_->range_;
+}
+
+
+void LiveRangeConflictIterator::MovePosToFirstConflictForQuery() {
+ DCHECK_NOT_NULL(query_);
+ auto end = intervals_->end();
+ LifetimePosition q_start = query_->start();
+ LifetimePosition q_end = query_->end();
+
+ if (intervals_->empty() || intervals_->rbegin()->end_ <= q_start ||
+ intervals_->begin()->start_ >= q_end) {
+ pos_ = end;
+ return;
+ }
+
+ pos_ = intervals_->upper_bound(AsAllocatedInterval(q_start));
+ // pos is either at the end (no start strictly greater than q_start) or
+ // at some position with the aforementioned property. In either case, the
+ // allocated interval before this one may intersect our query:
+ // either because, although it starts before this query's start, it ends
+ // after; or because it starts exactly at the query start. So unless we're
+ // right at the beginning of the storage - meaning the first allocated
+ // interval is also starting after this query's start - see what's behind.
+ if (pos_ != intervals_->begin()) {
+ --pos_;
+ if (!QueryIntersectsAllocatedInterval()) {
+ // The interval behind wasn't intersecting, so move back.
+ ++pos_;
+ }
+ }
+ if (pos_ == end || !QueryIntersectsAllocatedInterval()) {
+ pos_ = end;
+ }
+}
+
+
+void LiveRangeConflictIterator::MovePosAndQueryToFirstConflict() {
+ auto end = intervals_->end();
+ for (; query_ != nullptr; query_ = query_->next()) {
+ MovePosToFirstConflictForQuery();
+ if (pos_ != end) {
+ DCHECK(QueryIntersectsAllocatedInterval());
+ return;
+ }
+ }
+
+ Invalidate();
+}
+
+
+void LiveRangeConflictIterator::IncrementPosAndSkipOverRepetitions() {
+ auto end = intervals_->end();
+ DCHECK(pos_ != end);
+ LiveRange* current_conflict = Current();
+ while (pos_ != end && pos_->range_ == current_conflict) {
+ ++pos_;
+ }
+}
+
+
+LiveRange* LiveRangeConflictIterator::InternalGetNext(bool clean_behind) {
+ if (IsFinished()) return nullptr;
+
+ LiveRange* to_clear = Current();
+ IncrementPosAndSkipOverRepetitions();
+ // At this point, pos_ is either at the end, or on an interval that doesn't
+ // correspond to the same range as to_clear. This interval may not even be
+ // a conflict.
+ if (clean_behind) {
+ // Since we parked pos_ on an iterator that won't be affected by removal,
+ // we can safely delete to_clear's intervals.
+ for (auto interval = to_clear->first_interval(); interval != nullptr;
+ interval = interval->next()) {
+ AllocatedInterval erase_key(interval->start(), interval->end(), nullptr);
+ intervals_->erase(erase_key);
+ }
+ }
+ // We may have parked pos_ at the end, or on a non-conflict. In that case,
+ // move to the next query and reinitialize pos and query. This may invalidate
+ // the iterator, if no more conflicts are available.
+ if (!QueryIntersectsAllocatedInterval()) {
+ query_ = query_->next();
+ MovePosAndQueryToFirstConflict();
+ }
+ return Current();
+}
+
+
+LiveRangeConflictIterator CoalescedLiveRanges::GetConflicts(
+ const LiveRange* range) {
+ return LiveRangeConflictIterator(range, &intervals());
+}
+
+
+void CoalescedLiveRanges::AllocateRange(LiveRange* range) {
+ for (auto interval = range->first_interval(); interval != nullptr;
+ interval = interval->next()) {
+ AllocatedInterval to_insert(interval->start(), interval->end(), range);
+ intervals().insert(to_insert);
+ }
+}
+
+
+bool CoalescedLiveRanges::VerifyAllocationsAreValidForTesting() const {
+ LifetimePosition last_end = LifetimePosition::GapFromInstructionIndex(0);
+ for (auto i : intervals_) {
+ if (i.start_ < last_end) {
+ return false;
+ }
+ last_end = i.end_;
+ }
+ return true;
+}
+
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8