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