OLD | NEW |
1 // Copyright 2015 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_GREEDY_ALLOCATOR_H_ | 5 #ifndef V8_GREEDY_ALLOCATOR_H_ |
6 #define V8_GREEDY_ALLOCATOR_H_ | 6 #define V8_GREEDY_ALLOCATOR_H_ |
7 | 7 |
8 #include "src/compiler/coalesced-live-ranges.h" | 8 #include "src/compiler/coalesced-live-ranges.h" |
9 #include "src/compiler/register-allocator.h" | 9 #include "src/compiler/register-allocator.h" |
10 #include "src/zone-containers.h" | 10 #include "src/zone-containers.h" |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
55 // A variant of the LLVM Greedy Register Allocator. See | 55 // A variant of the LLVM Greedy Register Allocator. See |
56 // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html | 56 // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html |
57 class GreedyAllocator final : public RegisterAllocator { | 57 class GreedyAllocator final : public RegisterAllocator { |
58 public: | 58 public: |
59 explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind, | 59 explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind, |
60 Zone* local_zone); | 60 Zone* local_zone); |
61 | 61 |
62 void AllocateRegisters(); | 62 void AllocateRegisters(); |
63 | 63 |
64 private: | 64 private: |
| 65 static const float kAllocatedRangeMultiplier; |
| 66 |
| 67 static void UpdateWeightAtAllocation(LiveRange* range) { |
| 68 DCHECK_NE(range->weight(), LiveRange::kInvalidWeight); |
| 69 range->set_weight(range->weight() * kAllocatedRangeMultiplier); |
| 70 } |
| 71 |
| 72 |
| 73 static void UpdateWeightAtEviction(LiveRange* range) { |
| 74 DCHECK_NE(range->weight(), LiveRange::kInvalidWeight); |
| 75 range->set_weight(range->weight() / kAllocatedRangeMultiplier); |
| 76 } |
| 77 |
65 AllocationScheduler& scheduler() { return scheduler_; } | 78 AllocationScheduler& scheduler() { return scheduler_; } |
66 CoalescedLiveRanges* current_allocations(unsigned i) { | 79 CoalescedLiveRanges* current_allocations(unsigned i) { |
67 return allocations_[i]; | 80 return allocations_[i]; |
68 } | 81 } |
| 82 |
| 83 CoalescedLiveRanges* current_allocations(unsigned i) const { |
| 84 return allocations_[i]; |
| 85 } |
| 86 |
69 Zone* local_zone() const { return local_zone_; } | 87 Zone* local_zone() const { return local_zone_; } |
70 | 88 |
71 // Insert fixed ranges. | 89 // Insert fixed ranges. |
72 void PreallocateFixedRanges(); | 90 void PreallocateFixedRanges(); |
73 | 91 |
74 // Schedule unassigned live ranges for allocation. | 92 // Schedule unassigned live ranges for allocation. |
75 // TODO(mtrofin): groups. | 93 // TODO(mtrofin): groups. |
76 void ScheduleAllocationCandidates(); | 94 void ScheduleAllocationCandidates(); |
77 | 95 |
| 96 void AllocateRegisterToRange(unsigned reg_id, LiveRange* range) { |
| 97 UpdateWeightAtAllocation(range); |
| 98 current_allocations(reg_id)->AllocateRange(range); |
| 99 } |
| 100 // Evict and reschedule conflicts of a given range, at a given register. |
| 101 void EvictAndRescheduleConflicts(unsigned reg_id, const LiveRange* range); |
| 102 |
78 // Find the optimal split for ranges defined by a memory operand, e.g. | 103 // Find the optimal split for ranges defined by a memory operand, e.g. |
79 // constants or function parameters passed on the stack. | 104 // constants or function parameters passed on the stack. |
80 void SplitAndSpillRangesDefinedByMemoryOperand(); | 105 void SplitAndSpillRangesDefinedByMemoryOperand(); |
81 | 106 |
82 void TryAllocateCandidate(const AllocationCandidate& candidate); | 107 void TryAllocateCandidate(const AllocationCandidate& candidate); |
83 void TryAllocateLiveRange(LiveRange* range); | 108 void TryAllocateLiveRange(LiveRange* range); |
84 | 109 |
85 bool CanProcessRange(LiveRange* range) const { | 110 bool CanProcessRange(LiveRange* range) const { |
86 return range != nullptr && !range->IsEmpty() && range->kind() == mode(); | 111 return range != nullptr && !range->IsEmpty() && range->kind() == mode(); |
87 } | 112 } |
88 | 113 |
89 // Calculate the weight of a candidate for allocation. | 114 // Calculate the weight of a candidate for allocation. |
90 void EnsureValidRangeWeight(LiveRange* range); | 115 void EnsureValidRangeWeight(LiveRange* range); |
91 | 116 |
92 // Calculate the new weight of a range that is about to be allocated. | 117 // Calculate the new weight of a range that is about to be allocated. |
93 float GetAllocatedRangeWeight(float candidate_weight); | 118 float GetAllocatedRangeWeight(float candidate_weight); |
94 | 119 |
| 120 // Returns kInvalidWeight if there are no conflicts, or the largest weight of |
| 121 // a range conflicting with the given range, at the given register. |
| 122 float GetMaximumConflictingWeight(unsigned reg_id, |
| 123 const LiveRange* range) const; |
| 124 |
95 // This is the extension point for splitting heuristics. | 125 // This is the extension point for splitting heuristics. |
96 void SplitOrSpillBlockedRange(LiveRange* range); | 126 void SplitOrSpillBlockedRange(LiveRange* range); |
97 | 127 |
98 // Necessary heuristic: spill when all else failed. | 128 // Necessary heuristic: spill when all else failed. |
99 void SpillRangeAsLastResort(LiveRange* range); | 129 void SpillRangeAsLastResort(LiveRange* range); |
100 | 130 |
101 void AssignRangeToRegister(int reg_id, LiveRange* range); | 131 void AssignRangeToRegister(int reg_id, LiveRange* range); |
102 | 132 |
103 Zone* local_zone_; | 133 Zone* local_zone_; |
104 ZoneVector<CoalescedLiveRanges*> allocations_; | 134 ZoneVector<CoalescedLiveRanges*> allocations_; |
105 AllocationScheduler scheduler_; | 135 AllocationScheduler scheduler_; |
106 DISALLOW_COPY_AND_ASSIGN(GreedyAllocator); | 136 DISALLOW_COPY_AND_ASSIGN(GreedyAllocator); |
107 }; | 137 }; |
108 } // namespace compiler | 138 } // namespace compiler |
109 } // namespace internal | 139 } // namespace internal |
110 } // namespace v8 | 140 } // namespace v8 |
111 #endif // V8_GREEDY_ALLOCATOR_H_ | 141 #endif // V8_GREEDY_ALLOCATOR_H_ |
OLD | NEW |