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