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 | |
| 17 | #ifndef ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ |
| 18 | #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ |
| 19 | |
| 20 | #include "base/macros.h" |
Ian Rogers | e63db27 | 2014-07-15 15:36:11 -0700 | [diff] [blame] | 21 | #include "primitive.h" |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 22 | #include "utils/growable_array.h" |
| 23 | |
| 24 | namespace art { |
| 25 | |
| 26 | class CodeGenerator; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 27 | class HBasicBlock; |
| 28 | class HGraph; |
| 29 | class HInstruction; |
| 30 | class HParallelMove; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 31 | class LiveInterval; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 32 | class Location; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 33 | class SsaLivenessAnalysis; |
| 34 | |
| 35 | /** |
| 36 | * An implementation of a linear scan register allocator on an `HGraph` with SSA form. |
| 37 | */ |
| 38 | class RegisterAllocator { |
| 39 | public: |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 40 | RegisterAllocator(ArenaAllocator* allocator, |
| 41 | CodeGenerator* codegen, |
| 42 | const SsaLivenessAnalysis& analysis); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 43 | |
| 44 | // Main entry point for the register allocator. Given the liveness analysis, |
| 45 | // allocates registers to live intervals. |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 46 | void AllocateRegisters(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 47 | |
| 48 | // Validate that the register allocator did not allocate the same register to |
| 49 | // intervals that intersect each other. Returns false if it did not. |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 50 | bool Validate(bool log_fatal_on_failure) { |
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 | |
| 59 | // Helper method for validation. Used by unit testing. |
| 60 | static bool ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 61 | size_t number_of_spill_slots, |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 62 | size_t number_of_out_slots, |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 63 | const CodeGenerator& codegen, |
| 64 | ArenaAllocator* allocator, |
| 65 | bool processing_core_registers, |
| 66 | bool log_fatal_on_failure); |
| 67 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 68 | static bool CanAllocateRegistersFor(const HGraph& graph, InstructionSet instruction_set); |
| 69 | static bool Supports(InstructionSet instruction_set) { |
Nicolas Geoffray | 93bedb7 | 2014-07-18 10:23:59 +0100 | [diff] [blame] | 70 | return instruction_set == kX86 |
| 71 | || instruction_set == kArm |
| 72 | || instruction_set == kX86_64 |
| 73 | || instruction_set == kThumb2; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 74 | } |
| 75 | |
| 76 | size_t GetNumberOfSpillSlots() const { |
| 77 | return spill_slots_.Size(); |
| 78 | } |
| 79 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 80 | private: |
| 81 | // Main methods of the allocator. |
| 82 | void LinearScan(); |
| 83 | bool TryAllocateFreeReg(LiveInterval* interval); |
| 84 | bool AllocateBlockedReg(LiveInterval* interval); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 85 | void Resolve(); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 86 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 87 | // Add `interval` in the given sorted list. |
| 88 | static void AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval); |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 89 | |
| 90 | // Split `interval` at the position `at`. The new interval starts at `at`. |
| 91 | LiveInterval* Split(LiveInterval* interval, size_t at); |
| 92 | |
| 93 | // Returns whether `reg` is blocked by the code generator. |
| 94 | bool IsBlocked(int reg) const; |
| 95 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 96 | // Update the interval for the register in `location` to cover [start, end). |
| 97 | void BlockRegister(Location location, size_t start, size_t end, Primitive::Type type); |
| 98 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 99 | // Allocate a spill slot for the given interval. |
| 100 | void AllocateSpillSlotFor(LiveInterval* interval); |
Nicolas Geoffray | 412f10c | 2014-06-19 10:00:34 +0100 | [diff] [blame] | 101 | void AllocateOneSpillSlot(LiveInterval* interval, size_t end); |
| 102 | void AllocateTwoSpillSlots(LiveInterval* interval, size_t end); |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 103 | |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 104 | // Connect adjacent siblings within blocks. |
| 105 | void ConnectSiblings(LiveInterval* interval); |
| 106 | |
| 107 | // Connect siblings between block entries and exits. |
| 108 | void ConnectSplitSiblings(LiveInterval* interval, HBasicBlock* from, HBasicBlock* to) const; |
| 109 | |
| 110 | // Helper methods to insert parallel moves in the graph. |
| 111 | void InsertParallelMoveAtExitOf(HBasicBlock* block, Location source, Location destination) const; |
| 112 | void InsertParallelMoveAtEntryOf(HBasicBlock* block, Location source, Location destination) const; |
| 113 | void InsertMoveAfter(HInstruction* instruction, Location source, Location destination) const; |
| 114 | void AddInputMoveFor(HInstruction* instruction, Location source, Location destination) const; |
| 115 | void InsertParallelMoveAt(size_t position, Location source, Location destination) const; |
| 116 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 117 | // Helper methods. |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 118 | void AllocateRegistersInternal(); |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 119 | void ProcessInstruction(HInstruction* instruction); |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 120 | bool ValidateInternal(bool log_fatal_on_failure) const; |
| 121 | void DumpInterval(std::ostream& stream, LiveInterval* interval) const; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 122 | |
| 123 | ArenaAllocator* const allocator_; |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 124 | CodeGenerator* const codegen_; |
| 125 | const SsaLivenessAnalysis& liveness_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 126 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 127 | // List of intervals for core registers that must be processed, ordered by start |
| 128 | // position. Last entry is the interval that has the lowest start position. |
| 129 | // This list is initially populated before doing the linear scan. |
| 130 | GrowableArray<LiveInterval*> unhandled_core_intervals_; |
| 131 | |
| 132 | // List of intervals for floating-point registers. Same comments as above. |
| 133 | GrowableArray<LiveInterval*> unhandled_fp_intervals_; |
| 134 | |
| 135 | // Currently processed list of unhandled intervals. Either `unhandled_core_intervals_` |
| 136 | // or `unhandled_fp_intervals_`. |
| 137 | GrowableArray<LiveInterval*>* unhandled_; |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 138 | |
| 139 | // List of intervals that have been processed. |
| 140 | GrowableArray<LiveInterval*> handled_; |
| 141 | |
| 142 | // List of intervals that are currently active when processing a new live interval. |
| 143 | // That is, they have a live range that spans the start of the new interval. |
| 144 | GrowableArray<LiveInterval*> active_; |
| 145 | |
| 146 | // List of intervals that are currently inactive when processing a new live interval. |
| 147 | // That is, they have a lifetime hole that spans the start of the new interval. |
| 148 | GrowableArray<LiveInterval*> inactive_; |
| 149 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 150 | // Fixed intervals for physical registers. Such intervals cover the positions |
Nicolas Geoffray | 86dbb9a | 2014-06-04 11:12:39 +0100 | [diff] [blame] | 151 | // where an instruction requires a specific register. |
| 152 | GrowableArray<LiveInterval*> physical_register_intervals_; |
| 153 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 154 | // Intervals for temporaries. Such intervals cover the positions |
| 155 | // where an instruction requires a temporary. |
| 156 | GrowableArray<LiveInterval*> temp_intervals_; |
| 157 | |
Nicolas Geoffray | 31d76b4 | 2014-06-09 15:02:22 +0100 | [diff] [blame] | 158 | // The spill slots allocated for live intervals. |
| 159 | GrowableArray<size_t> spill_slots_; |
| 160 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 161 | // Instructions that need a safepoint. |
| 162 | GrowableArray<HInstruction*> safepoints_; |
| 163 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 164 | // True if processing core registers. False if processing floating |
| 165 | // point registers. |
| 166 | bool processing_core_registers_; |
| 167 | |
| 168 | // Number of registers for the current register kind (core or floating point). |
| 169 | size_t number_of_registers_; |
| 170 | |
| 171 | // Temporary array, allocated ahead of time for simplicity. |
| 172 | size_t* registers_array_; |
| 173 | |
| 174 | // Blocked registers, as decided by the code generator. |
| 175 | bool* const blocked_registers_; |
| 176 | |
Nicolas Geoffray | 3946844 | 2014-09-02 15:17:15 +0100 | [diff] [blame^] | 177 | // Slots reserved for out arguments. |
| 178 | size_t reserved_out_slots_; |
| 179 | |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 180 | DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); |
| 181 | }; |
| 182 | |
| 183 | } // namespace art |
| 184 | |
| 185 | #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ |