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/greedy-allocator.h b/src/compiler/greedy-allocator.h
new file mode 100644
index 0000000..b61ba42
--- /dev/null
+++ b/src/compiler/greedy-allocator.h
@@ -0,0 +1,199 @@
+// 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_GREEDY_ALLOCATOR_H_
+#define V8_GREEDY_ALLOCATOR_H_
+
+#include "src/compiler/coalesced-live-ranges.h"
+#include "src/compiler/register-allocator.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+
+// The object of allocation scheduling. At minimum, this is a LiveRange, but
+// we may extend this to groups of LiveRanges. It has to be comparable.
+class AllocationCandidate {
+ public:
+ explicit AllocationCandidate(LiveRange* range)
+ : is_group_(false), size_(range->GetSize()) {
+ candidate_.range_ = range;
+ }
+
+ explicit AllocationCandidate(LiveRangeGroup* ranges)
+ : is_group_(true), size_(CalculateGroupSize(ranges)) {
+ candidate_.group_ = ranges;
+ }
+
+ // Strict ordering operators
+ bool operator<(const AllocationCandidate& other) const {
+ return size() < other.size();
+ }
+
+ bool operator>(const AllocationCandidate& other) const {
+ return size() > other.size();
+ }
+
+ bool is_group() const { return is_group_; }
+ LiveRange* live_range() const { return candidate_.range_; }
+ LiveRangeGroup* group() const { return candidate_.group_; }
+
+ private:
+ unsigned CalculateGroupSize(LiveRangeGroup* group) {
+ unsigned ret = 0;
+ for (LiveRange* range : group->ranges()) {
+ ret += range->GetSize();
+ }
+ return ret;
+ }
+
+ unsigned size() const { return size_; }
+ bool is_group_;
+ unsigned size_;
+ union {
+ LiveRange* range_;
+ LiveRangeGroup* group_;
+ } candidate_;
+};
+
+
+// Schedule processing (allocating) of AllocationCandidates.
+class AllocationScheduler final : ZoneObject {
+ public:
+ explicit AllocationScheduler(Zone* zone) : queue_(zone) {}
+ void Schedule(LiveRange* range);
+ void Schedule(LiveRangeGroup* group);
+ AllocationCandidate GetNext();
+ bool empty() const { return queue_.empty(); }
+
+ private:
+ typedef ZonePriorityQueue<AllocationCandidate> ScheduleQueue;
+ ScheduleQueue queue_;
+
+ DISALLOW_COPY_AND_ASSIGN(AllocationScheduler);
+};
+
+
+// A variant of the LLVM Greedy Register Allocator. See
+// http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
+class GreedyAllocator final : public RegisterAllocator {
+ public:
+ explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind,
+ Zone* local_zone);
+
+ void AllocateRegisters();
+
+ private:
+ static const float kAllocatedRangeMultiplier;
+
+ static void UpdateWeightAtAllocation(LiveRange* range) {
+ DCHECK_NE(range->weight(), LiveRange::kInvalidWeight);
+ range->set_weight(range->weight() * kAllocatedRangeMultiplier);
+ }
+
+
+ static void UpdateWeightAtEviction(LiveRange* range) {
+ DCHECK_NE(range->weight(), LiveRange::kInvalidWeight);
+ range->set_weight(range->weight() / kAllocatedRangeMultiplier);
+ }
+
+ AllocationScheduler& scheduler() { return scheduler_; }
+ CoalescedLiveRanges* current_allocations(unsigned i) {
+ return allocations_[i];
+ }
+
+ CoalescedLiveRanges* current_allocations(unsigned i) const {
+ return allocations_[i];
+ }
+
+ Zone* local_zone() const { return local_zone_; }
+ ZoneVector<LiveRangeGroup*>& groups() { return groups_; }
+ const ZoneVector<LiveRangeGroup*>& groups() const { return groups_; }
+
+ // Insert fixed ranges.
+ void PreallocateFixedRanges();
+
+ void GroupLiveRanges();
+
+ // Schedule unassigned live ranges for allocation.
+ void ScheduleAllocationCandidates();
+
+ void AllocateRegisterToRange(unsigned reg_id, LiveRange* range) {
+ UpdateWeightAtAllocation(range);
+ current_allocations(reg_id)->AllocateRange(range);
+ }
+ // Evict and reschedule conflicts of a given range, at a given register.
+ void EvictAndRescheduleConflicts(unsigned reg_id, const LiveRange* range);
+
+ void TryAllocateCandidate(const AllocationCandidate& candidate);
+ void TryAllocateLiveRange(LiveRange* range);
+ void TryAllocateGroup(LiveRangeGroup* group);
+
+ // Calculate the weight of a candidate for allocation.
+ void EnsureValidRangeWeight(LiveRange* range);
+
+ // Calculate the new weight of a range that is about to be allocated.
+ float GetAllocatedRangeWeight(float candidate_weight);
+
+ // Returns kInvalidWeight if there are no conflicts, or the largest weight of
+ // a range conflicting with the given range, at the given register.
+ float GetMaximumConflictingWeight(unsigned reg_id, const LiveRange* range,
+ float competing_weight) const;
+
+ // Returns kInvalidWeight if there are no conflicts, or the largest weight of
+ // a range conflicting with the given range, at the given register.
+ float GetMaximumConflictingWeight(unsigned reg_id,
+ const LiveRangeGroup* group,
+ float group_weight) const;
+
+ // This is the extension point for splitting heuristics.
+ void SplitOrSpillBlockedRange(LiveRange* range);
+
+ // Find a good position where to fill, after a range was spilled after a call.
+ LifetimePosition FindSplitPositionAfterCall(const LiveRange* range,
+ int call_index);
+ // Split a range around all calls it passes over. Returns true if any changes
+ // were made, or false if no calls were found.
+ bool TrySplitAroundCalls(LiveRange* range);
+
+ // Find a split position at the outmost loop.
+ LifetimePosition FindSplitPositionBeforeLoops(LiveRange* range);
+
+ // Finds the first call instruction in the path of this range. Splits before
+ // and requeues that segment (if any), spills the section over the call, and
+ // returns the section after the call. The return is:
+ // - same range, if no call was found
+ // - nullptr, if the range finished at the call and there's no "after the
+ // call" portion.
+ // - the portion after the call.
+ LiveRange* GetRemainderAfterSplittingAroundFirstCall(LiveRange* range);
+
+ // While we attempt to merge spill ranges later on in the allocation pipeline,
+ // we want to ensure group elements get merged. Waiting until later may hinder
+ // merge-ability, since the pipeline merger (being naive) may create conflicts
+ // between spill ranges of group members.
+ void TryReuseSpillRangesForGroups();
+
+ LifetimePosition GetLastResortSplitPosition(const LiveRange* range);
+
+ bool IsProgressPossible(const LiveRange* range);
+
+ // Necessary heuristic: spill when all else failed.
+ void SpillRangeAsLastResort(LiveRange* range);
+
+ void AssignRangeToRegister(int reg_id, LiveRange* range);
+
+ Zone* local_zone_;
+ ZoneVector<CoalescedLiveRanges*> allocations_;
+ AllocationScheduler scheduler_;
+ ZoneVector<LiveRangeGroup*> groups_;
+
+ DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
+};
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+#endif // V8_GREEDY_ALLOCATOR_H_