Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 1 | // Copyright 2015 the V8 project authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | #ifndef V8_GREEDY_ALLOCATOR_H_ |
| 6 | #define V8_GREEDY_ALLOCATOR_H_ |
| 7 | |
| 8 | #include "src/compiler/coalesced-live-ranges.h" |
| 9 | #include "src/compiler/register-allocator.h" |
| 10 | #include "src/zone-containers.h" |
| 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | namespace compiler { |
| 15 | |
| 16 | |
| 17 | // The object of allocation scheduling. At minimum, this is a LiveRange, but |
| 18 | // we may extend this to groups of LiveRanges. It has to be comparable. |
| 19 | class AllocationCandidate { |
| 20 | public: |
| 21 | explicit AllocationCandidate(LiveRange* range) |
| 22 | : is_group_(false), size_(range->GetSize()) { |
| 23 | candidate_.range_ = range; |
| 24 | } |
| 25 | |
| 26 | explicit AllocationCandidate(LiveRangeGroup* ranges) |
| 27 | : is_group_(true), size_(CalculateGroupSize(ranges)) { |
| 28 | candidate_.group_ = ranges; |
| 29 | } |
| 30 | |
| 31 | // Strict ordering operators |
| 32 | bool operator<(const AllocationCandidate& other) const { |
| 33 | return size() < other.size(); |
| 34 | } |
| 35 | |
| 36 | bool operator>(const AllocationCandidate& other) const { |
| 37 | return size() > other.size(); |
| 38 | } |
| 39 | |
| 40 | bool is_group() const { return is_group_; } |
| 41 | LiveRange* live_range() const { return candidate_.range_; } |
| 42 | LiveRangeGroup* group() const { return candidate_.group_; } |
| 43 | |
| 44 | private: |
| 45 | unsigned CalculateGroupSize(LiveRangeGroup* group) { |
| 46 | unsigned ret = 0; |
| 47 | for (LiveRange* range : group->ranges()) { |
| 48 | ret += range->GetSize(); |
| 49 | } |
| 50 | return ret; |
| 51 | } |
| 52 | |
| 53 | unsigned size() const { return size_; } |
| 54 | bool is_group_; |
| 55 | unsigned size_; |
| 56 | union { |
| 57 | LiveRange* range_; |
| 58 | LiveRangeGroup* group_; |
| 59 | } candidate_; |
| 60 | }; |
| 61 | |
| 62 | |
| 63 | // Schedule processing (allocating) of AllocationCandidates. |
| 64 | class AllocationScheduler final : ZoneObject { |
| 65 | public: |
| 66 | explicit AllocationScheduler(Zone* zone) : queue_(zone) {} |
| 67 | void Schedule(LiveRange* range); |
| 68 | void Schedule(LiveRangeGroup* group); |
| 69 | AllocationCandidate GetNext(); |
| 70 | bool empty() const { return queue_.empty(); } |
| 71 | |
| 72 | private: |
| 73 | typedef ZonePriorityQueue<AllocationCandidate> ScheduleQueue; |
| 74 | ScheduleQueue queue_; |
| 75 | |
| 76 | DISALLOW_COPY_AND_ASSIGN(AllocationScheduler); |
| 77 | }; |
| 78 | |
| 79 | |
| 80 | // A variant of the LLVM Greedy Register Allocator. See |
| 81 | // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html |
| 82 | class GreedyAllocator final : public RegisterAllocator { |
| 83 | public: |
| 84 | explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind, |
| 85 | Zone* local_zone); |
| 86 | |
| 87 | void AllocateRegisters(); |
| 88 | |
| 89 | private: |
| 90 | static const float kAllocatedRangeMultiplier; |
| 91 | |
| 92 | static void UpdateWeightAtAllocation(LiveRange* range) { |
| 93 | DCHECK_NE(range->weight(), LiveRange::kInvalidWeight); |
| 94 | range->set_weight(range->weight() * kAllocatedRangeMultiplier); |
| 95 | } |
| 96 | |
| 97 | |
| 98 | static void UpdateWeightAtEviction(LiveRange* range) { |
| 99 | DCHECK_NE(range->weight(), LiveRange::kInvalidWeight); |
| 100 | range->set_weight(range->weight() / kAllocatedRangeMultiplier); |
| 101 | } |
| 102 | |
| 103 | AllocationScheduler& scheduler() { return scheduler_; } |
| 104 | CoalescedLiveRanges* current_allocations(unsigned i) { |
| 105 | return allocations_[i]; |
| 106 | } |
| 107 | |
| 108 | CoalescedLiveRanges* current_allocations(unsigned i) const { |
| 109 | return allocations_[i]; |
| 110 | } |
| 111 | |
| 112 | Zone* local_zone() const { return local_zone_; } |
| 113 | ZoneVector<LiveRangeGroup*>& groups() { return groups_; } |
| 114 | const ZoneVector<LiveRangeGroup*>& groups() const { return groups_; } |
| 115 | |
| 116 | // Insert fixed ranges. |
| 117 | void PreallocateFixedRanges(); |
| 118 | |
| 119 | void GroupLiveRanges(); |
| 120 | |
| 121 | // Schedule unassigned live ranges for allocation. |
| 122 | void ScheduleAllocationCandidates(); |
| 123 | |
| 124 | void AllocateRegisterToRange(unsigned reg_id, LiveRange* range) { |
| 125 | UpdateWeightAtAllocation(range); |
| 126 | current_allocations(reg_id)->AllocateRange(range); |
| 127 | } |
| 128 | // Evict and reschedule conflicts of a given range, at a given register. |
| 129 | void EvictAndRescheduleConflicts(unsigned reg_id, const LiveRange* range); |
| 130 | |
| 131 | void TryAllocateCandidate(const AllocationCandidate& candidate); |
| 132 | void TryAllocateLiveRange(LiveRange* range); |
| 133 | void TryAllocateGroup(LiveRangeGroup* group); |
| 134 | |
| 135 | // Calculate the weight of a candidate for allocation. |
| 136 | void EnsureValidRangeWeight(LiveRange* range); |
| 137 | |
| 138 | // Calculate the new weight of a range that is about to be allocated. |
| 139 | float GetAllocatedRangeWeight(float candidate_weight); |
| 140 | |
| 141 | // Returns kInvalidWeight if there are no conflicts, or the largest weight of |
| 142 | // a range conflicting with the given range, at the given register. |
| 143 | float GetMaximumConflictingWeight(unsigned reg_id, const LiveRange* range, |
| 144 | float competing_weight) const; |
| 145 | |
| 146 | // Returns kInvalidWeight if there are no conflicts, or the largest weight of |
| 147 | // a range conflicting with the given range, at the given register. |
| 148 | float GetMaximumConflictingWeight(unsigned reg_id, |
| 149 | const LiveRangeGroup* group, |
| 150 | float group_weight) const; |
| 151 | |
| 152 | // This is the extension point for splitting heuristics. |
| 153 | void SplitOrSpillBlockedRange(LiveRange* range); |
| 154 | |
| 155 | // Find a good position where to fill, after a range was spilled after a call. |
| 156 | LifetimePosition FindSplitPositionAfterCall(const LiveRange* range, |
| 157 | int call_index); |
| 158 | // Split a range around all calls it passes over. Returns true if any changes |
| 159 | // were made, or false if no calls were found. |
| 160 | bool TrySplitAroundCalls(LiveRange* range); |
| 161 | |
| 162 | // Find a split position at the outmost loop. |
| 163 | LifetimePosition FindSplitPositionBeforeLoops(LiveRange* range); |
| 164 | |
| 165 | // Finds the first call instruction in the path of this range. Splits before |
| 166 | // and requeues that segment (if any), spills the section over the call, and |
| 167 | // returns the section after the call. The return is: |
| 168 | // - same range, if no call was found |
| 169 | // - nullptr, if the range finished at the call and there's no "after the |
| 170 | // call" portion. |
| 171 | // - the portion after the call. |
| 172 | LiveRange* GetRemainderAfterSplittingAroundFirstCall(LiveRange* range); |
| 173 | |
| 174 | // While we attempt to merge spill ranges later on in the allocation pipeline, |
| 175 | // we want to ensure group elements get merged. Waiting until later may hinder |
| 176 | // merge-ability, since the pipeline merger (being naive) may create conflicts |
| 177 | // between spill ranges of group members. |
| 178 | void TryReuseSpillRangesForGroups(); |
| 179 | |
| 180 | LifetimePosition GetLastResortSplitPosition(const LiveRange* range); |
| 181 | |
| 182 | bool IsProgressPossible(const LiveRange* range); |
| 183 | |
| 184 | // Necessary heuristic: spill when all else failed. |
| 185 | void SpillRangeAsLastResort(LiveRange* range); |
| 186 | |
| 187 | void AssignRangeToRegister(int reg_id, LiveRange* range); |
| 188 | |
| 189 | Zone* local_zone_; |
| 190 | ZoneVector<CoalescedLiveRanges*> allocations_; |
| 191 | AllocationScheduler scheduler_; |
| 192 | ZoneVector<LiveRangeGroup*> groups_; |
| 193 | |
| 194 | DISALLOW_COPY_AND_ASSIGN(GreedyAllocator); |
| 195 | }; |
| 196 | } // namespace compiler |
| 197 | } // namespace internal |
| 198 | } // namespace v8 |
| 199 | #endif // V8_GREEDY_ALLOCATOR_H_ |