Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Matthew Gharrity | e928885 | 2016-07-14 14:08:16 -0700 | [diff] [blame] | 17 | #ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_LINEAR_SCAN_H_ |
| 18 | #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_LINEAR_SCAN_H_ |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 19 | |
Vladimir Marko | 80afd02 | 2015-05-19 18:08:00 +0100 | [diff] [blame] | 20 | #include "arch/instruction_set.h" |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 21 | #include "base/arena_containers.h" |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 22 | #include "base/macros.h" |
Ian Rogers | e63db27 | 2014-07-15 15:36:11 -0700 | [diff] [blame] | 23 | #include "primitive.h" |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 24 | #include "register_allocator.h" |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 25 | |
| 26 | namespace art { |
| 27 | |
| 28 | class CodeGenerator; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 29 | class HBasicBlock; |
| 30 | class HGraph; |
| 31 | class HInstruction; |
| 32 | class HParallelMove; |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 33 | class HPhi; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 34 | class LiveInterval; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 35 | class Location; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 36 | class SsaLivenessAnalysis; |
| 37 | |
| 38 | /** |
| 39 | * An implementation of a linear scan register allocator on an `HGraph` with SSA form. |
| 40 | */ |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 41 | class RegisterAllocatorLinearScan : public RegisterAllocator { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 42 | public: |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 43 | RegisterAllocatorLinearScan(ArenaAllocator* allocator, |
| 44 | CodeGenerator* codegen, |
| 45 | const SsaLivenessAnalysis& analysis); |
Matthew Gharrity | d9ffd0d | 2016-06-22 10:27:55 -0700 | [diff] [blame] | 46 | ~RegisterAllocatorLinearScan() OVERRIDE {} |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 47 | |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 48 | void AllocateRegisters() OVERRIDE; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 49 | |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 50 | bool Validate(bool log_fatal_on_failure) OVERRIDE { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 51 | processing_core_registers_ = true; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 52 | if (!ValidateInternal(log_fatal_on_failure)) { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 53 | return false; |
| 54 | } |
| 55 | processing_core_registers_ = false; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 56 | return ValidateInternal(log_fatal_on_failure); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 57 | } |
| 58 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 59 | size_t GetNumberOfSpillSlots() const { |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 60 | return int_spill_slots_.size() |
| 61 | + long_spill_slots_.size() |
| 62 | + float_spill_slots_.size() |
| 63 | + double_spill_slots_.size() |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 64 | + catch_phi_spill_slots_; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 65 | } |
| 66 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 67 | private: |
| 68 | // Main methods of the allocator. |
| 69 | void LinearScan(); |
| 70 | bool TryAllocateFreeReg(LiveInterval* interval); |
| 71 | bool AllocateBlockedReg(LiveInterval* interval); |
| 72 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 73 | // Add `interval` in the given sorted list. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 74 | static void AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 75 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 76 | // Returns whether `reg` is blocked by the code generator. |
| 77 | bool IsBlocked(int reg) const; |
| 78 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 79 | // Update the interval for the register in `location` to cover [start, end). |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 80 | void BlockRegister(Location location, size_t start, size_t end); |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 81 | void BlockRegisters(size_t start, size_t end, bool caller_save_only = false); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 82 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 83 | // Allocate a spill slot for the given interval. Should be called in linear |
| 84 | // order of interval starting positions. |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 85 | void AllocateSpillSlotFor(LiveInterval* interval); |
| 86 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 87 | // Allocate a spill slot for the given catch phi. Will allocate the same slot |
| 88 | // for phis which share the same vreg. Must be called in reverse linear order |
| 89 | // of lifetime positions and ascending vreg numbers for correctness. |
| 90 | void AllocateSpillSlotForCatchPhi(HPhi* phi); |
| 91 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 92 | // Helper methods. |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 93 | void AllocateRegistersInternal(); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 94 | void ProcessInstruction(HInstruction* instruction); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 95 | bool ValidateInternal(bool log_fatal_on_failure) const; |
| 96 | void DumpInterval(std::ostream& stream, LiveInterval* interval) const; |
Mingyao Yang | 296bd60 | 2014-10-06 16:47:28 -0700 | [diff] [blame] | 97 | void DumpAllIntervals(std::ostream& stream) const; |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 98 | int FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const; |
Nicolas Geoffray | 8826f67 | 2015-04-17 09:15:11 +0100 | [diff] [blame] | 99 | int FindAvailableRegister(size_t* next_use, LiveInterval* current) const; |
| 100 | bool IsCallerSaveRegister(int reg) const; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 101 | |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 102 | // Try splitting an active non-pair or unaligned pair interval at the given `position`. |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 103 | // Returns whether it was successful at finding such an interval. |
Nicolas Geoffray | 234d69d | 2015-03-09 10:28:50 +0000 | [diff] [blame] | 104 | bool TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, |
| 105 | size_t first_register_use, |
| 106 | size_t* next_use); |
Nicolas Geoffray | 6c2dff8 | 2015-01-21 14:56:54 +0000 | [diff] [blame] | 107 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 108 | // List of intervals for core registers that must be processed, ordered by start |
| 109 | // position. Last entry is the interval that has the lowest start position. |
| 110 | // This list is initially populated before doing the linear scan. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 111 | ArenaVector<LiveInterval*> unhandled_core_intervals_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 112 | |
| 113 | // List of intervals for floating-point registers. Same comments as above. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 114 | ArenaVector<LiveInterval*> unhandled_fp_intervals_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 115 | |
| 116 | // Currently processed list of unhandled intervals. Either `unhandled_core_intervals_` |
| 117 | // or `unhandled_fp_intervals_`. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 118 | ArenaVector<LiveInterval*>* unhandled_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 119 | |
| 120 | // List of intervals that have been processed. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 121 | ArenaVector<LiveInterval*> handled_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 122 | |
| 123 | // List of intervals that are currently active when processing a new live interval. |
| 124 | // That is, they have a live range that spans the start of the new interval. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 125 | ArenaVector<LiveInterval*> active_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 126 | |
| 127 | // List of intervals that are currently inactive when processing a new live interval. |
| 128 | // That is, they have a lifetime hole that spans the start of the new interval. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 129 | ArenaVector<LiveInterval*> inactive_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 130 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 131 | // Fixed intervals for physical registers. Such intervals cover the positions |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 132 | // where an instruction requires a specific register. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 133 | ArenaVector<LiveInterval*> physical_core_register_intervals_; |
| 134 | ArenaVector<LiveInterval*> physical_fp_register_intervals_; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 135 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 136 | // Intervals for temporaries. Such intervals cover the positions |
| 137 | // where an instruction requires a temporary. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 138 | ArenaVector<LiveInterval*> temp_intervals_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 139 | |
Nicolas Geoffray | 776b318 | 2015-02-23 14:14:57 +0000 | [diff] [blame] | 140 | // The spill slots allocated for live intervals. We ensure spill slots |
| 141 | // are typed to avoid (1) doing moves and swaps between two different kinds |
| 142 | // of registers, and (2) swapping between a single stack slot and a double |
| 143 | // stack slot. This simplifies the parallel move resolver. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 144 | ArenaVector<size_t> int_spill_slots_; |
| 145 | ArenaVector<size_t> long_spill_slots_; |
| 146 | ArenaVector<size_t> float_spill_slots_; |
| 147 | ArenaVector<size_t> double_spill_slots_; |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 148 | |
David Brazdil | 77a48ae | 2015-09-15 12:34:04 +0000 | [diff] [blame] | 149 | // Spill slots allocated to catch phis. This category is special-cased because |
| 150 | // (1) slots are allocated prior to linear scan and in reverse linear order, |
| 151 | // (2) equivalent phis need to share slots despite having different types. |
| 152 | size_t catch_phi_spill_slots_; |
| 153 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 154 | // Instructions that need a safepoint. |
Vladimir Marko | 2aaa4b5 | 2015-09-17 17:03:26 +0100 | [diff] [blame] | 155 | ArenaVector<HInstruction*> safepoints_; |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 156 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 157 | // True if processing core registers. False if processing floating |
| 158 | // point registers. |
| 159 | bool processing_core_registers_; |
| 160 | |
| 161 | // Number of registers for the current register kind (core or floating point). |
| 162 | size_t number_of_registers_; |
| 163 | |
| 164 | // Temporary array, allocated ahead of time for simplicity. |
| 165 | size_t* registers_array_; |
| 166 | |
| 167 | // Blocked registers, as decided by the code generator. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 168 | bool* const blocked_core_registers_; |
| 169 | bool* const blocked_fp_registers_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 170 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame] | 171 | // Slots reserved for out arguments. |
| 172 | size_t reserved_out_slots_; |
| 173 | |
Ian Rogers | 6f3dbba | 2014-10-14 17:41:57 -0700 | [diff] [blame] | 174 | ART_FRIEND_TEST(RegisterAllocatorTest, FreeUntil); |
Nicolas Geoffray | dd8f887 | 2015-01-15 15:37:37 +0000 | [diff] [blame] | 175 | ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); |
Nicolas Geoffray | aac0f39 | 2014-09-16 14:11:14 +0100 | [diff] [blame] | 176 | |
Matthew Gharrity | 8f49d4b | 2016-07-14 13:24:00 -0700 | [diff] [blame] | 177 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorLinearScan); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 178 | }; |
| 179 | |
| 180 | } // namespace art |
| 181 | |
Matthew Gharrity | e928885 | 2016-07-14 14:08:16 -0700 | [diff] [blame] | 182 | #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_LINEAR_SCAN_H_ |