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 "arch/instruction_set.h" 21 #include "base/arena_containers.h" 22 #include "base/macros.h" 23 #include "primitive.h" 24 25 namespace art { 26 27 class CodeGenerator; 28 class HBasicBlock; 29 class HGraph; 30 class HInstruction; 31 class HParallelMove; 32 class HPhi; 33 class LiveInterval; 34 class Location; 35 class SsaLivenessAnalysis; 36 37 /** 38 * An implementation of a linear scan register allocator on an `HGraph` with SSA form. 39 */ 40 class RegisterAllocator { 41 public: 42 RegisterAllocator(ArenaAllocator* allocator, 43 CodeGenerator* codegen, 44 const SsaLivenessAnalysis& analysis); 45 46 // Main entry point for the register allocator. Given the liveness analysis, 47 // allocates registers to live intervals. 48 void AllocateRegisters(); 49 50 // Validate that the register allocator did not allocate the same register to 51 // intervals that intersect each other. Returns false if it did not. 52 bool Validate(bool log_fatal_on_failure) { 53 processing_core_registers_ = true; 54 if (!ValidateInternal(log_fatal_on_failure)) { 55 return false; 56 } 57 processing_core_registers_ = false; 58 return ValidateInternal(log_fatal_on_failure); 59 } 60 61 // Helper method for validation. Used by unit testing. 62 static bool ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, 63 size_t number_of_spill_slots, 64 size_t number_of_out_slots, 65 const CodeGenerator& codegen, 66 ArenaAllocator* allocator, 67 bool processing_core_registers, 68 bool log_fatal_on_failure); 69 70 static bool CanAllocateRegistersFor(const HGraph& graph, InstructionSet instruction_set); 71 72 size_t GetNumberOfSpillSlots() const { 73 return int_spill_slots_.size() 74 + long_spill_slots_.size() 75 + float_spill_slots_.size() 76 + double_spill_slots_.size() 77 + catch_phi_spill_slots_; 78 } 79 80 static constexpr const char* kRegisterAllocatorPassName = "register"; 81 82 private: 83 // Main methods of the allocator. 84 void LinearScan(); 85 bool TryAllocateFreeReg(LiveInterval* interval); 86 bool AllocateBlockedReg(LiveInterval* interval); 87 void Resolve(); 88 89 // Add `interval` in the given sorted list. 90 static void AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval); 91 92 // Split `interval` at the position `position`. The new interval starts at `position`. 93 LiveInterval* Split(LiveInterval* interval, size_t position); 94 95 // Split `interval` at a position between `from` and `to`. The method will try 96 // to find an optimal split position. 97 LiveInterval* SplitBetween(LiveInterval* interval, size_t from, size_t to); 98 99 // Returns whether `reg` is blocked by the code generator. 100 bool IsBlocked(int reg) const; 101 102 // Update the interval for the register in `location` to cover [start, end). 103 void BlockRegister(Location location, size_t start, size_t end); 104 void BlockRegisters(size_t start, size_t end, bool caller_save_only = false); 105 106 // Allocate a spill slot for the given interval. Should be called in linear 107 // order of interval starting positions. 108 void AllocateSpillSlotFor(LiveInterval* interval); 109 110 // Allocate a spill slot for the given catch phi. Will allocate the same slot 111 // for phis which share the same vreg. Must be called in reverse linear order 112 // of lifetime positions and ascending vreg numbers for correctness. 113 void AllocateSpillSlotForCatchPhi(HPhi* phi); 114 115 // Connect adjacent siblings within blocks. 116 void ConnectSiblings(LiveInterval* interval); 117 118 // Connect siblings between block entries and exits. 119 void ConnectSplitSiblings(LiveInterval* interval, HBasicBlock* from, HBasicBlock* to) const; 120 121 // Helper methods to insert parallel moves in the graph. 122 void InsertParallelMoveAtExitOf(HBasicBlock* block, 123 HInstruction* instruction, 124 Location source, 125 Location destination) const; 126 void InsertParallelMoveAtEntryOf(HBasicBlock* block, 127 HInstruction* instruction, 128 Location source, 129 Location destination) const; 130 void InsertMoveAfter(HInstruction* instruction, Location source, Location destination) const; 131 void AddInputMoveFor(HInstruction* input, 132 HInstruction* user, 133 Location source, 134 Location destination) const; 135 void InsertParallelMoveAt(size_t position, 136 HInstruction* instruction, 137 Location source, 138 Location destination) const; 139 140 void AddMove(HParallelMove* move, 141 Location source, 142 Location destination, 143 HInstruction* instruction, 144 Primitive::Type type) const; 145 146 // Helper methods. 147 void AllocateRegistersInternal(); 148 void ProcessInstruction(HInstruction* instruction); 149 bool ValidateInternal(bool log_fatal_on_failure) const; 150 void DumpInterval(std::ostream& stream, LiveInterval* interval) const; 151 void DumpAllIntervals(std::ostream& stream) const; 152 int FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const; 153 int FindAvailableRegister(size_t* next_use, LiveInterval* current) const; 154 bool IsCallerSaveRegister(int reg) const; 155 156 // Try splitting an active non-pair or unaligned pair interval at the given `position`. 157 // Returns whether it was successful at finding such an interval. 158 bool TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 159 size_t first_register_use, 160 size_t* next_use); 161 162 ArenaAllocator* const allocator_; 163 CodeGenerator* const codegen_; 164 const SsaLivenessAnalysis& liveness_; 165 166 // List of intervals for core registers that must be processed, ordered by start 167 // position. Last entry is the interval that has the lowest start position. 168 // This list is initially populated before doing the linear scan. 169 ArenaVector<LiveInterval*> unhandled_core_intervals_; 170 171 // List of intervals for floating-point registers. Same comments as above. 172 ArenaVector<LiveInterval*> unhandled_fp_intervals_; 173 174 // Currently processed list of unhandled intervals. Either `unhandled_core_intervals_` 175 // or `unhandled_fp_intervals_`. 176 ArenaVector<LiveInterval*>* unhandled_; 177 178 // List of intervals that have been processed. 179 ArenaVector<LiveInterval*> handled_; 180 181 // List of intervals that are currently active when processing a new live interval. 182 // That is, they have a live range that spans the start of the new interval. 183 ArenaVector<LiveInterval*> active_; 184 185 // List of intervals that are currently inactive when processing a new live interval. 186 // That is, they have a lifetime hole that spans the start of the new interval. 187 ArenaVector<LiveInterval*> inactive_; 188 189 // Fixed intervals for physical registers. Such intervals cover the positions 190 // where an instruction requires a specific register. 191 ArenaVector<LiveInterval*> physical_core_register_intervals_; 192 ArenaVector<LiveInterval*> physical_fp_register_intervals_; 193 194 // Intervals for temporaries. Such intervals cover the positions 195 // where an instruction requires a temporary. 196 ArenaVector<LiveInterval*> temp_intervals_; 197 198 // The spill slots allocated for live intervals. We ensure spill slots 199 // are typed to avoid (1) doing moves and swaps between two different kinds 200 // of registers, and (2) swapping between a single stack slot and a double 201 // stack slot. This simplifies the parallel move resolver. 202 ArenaVector<size_t> int_spill_slots_; 203 ArenaVector<size_t> long_spill_slots_; 204 ArenaVector<size_t> float_spill_slots_; 205 ArenaVector<size_t> double_spill_slots_; 206 207 // Spill slots allocated to catch phis. This category is special-cased because 208 // (1) slots are allocated prior to linear scan and in reverse linear order, 209 // (2) equivalent phis need to share slots despite having different types. 210 size_t catch_phi_spill_slots_; 211 212 // Instructions that need a safepoint. 213 ArenaVector<HInstruction*> safepoints_; 214 215 // True if processing core registers. False if processing floating 216 // point registers. 217 bool processing_core_registers_; 218 219 // Number of registers for the current register kind (core or floating point). 220 size_t number_of_registers_; 221 222 // Temporary array, allocated ahead of time for simplicity. 223 size_t* registers_array_; 224 225 // Blocked registers, as decided by the code generator. 226 bool* const blocked_core_registers_; 227 bool* const blocked_fp_registers_; 228 229 // Slots reserved for out arguments. 230 size_t reserved_out_slots_; 231 232 // The maximum live core registers at safepoints. 233 size_t maximum_number_of_live_core_registers_; 234 235 // The maximum live FP registers at safepoints. 236 size_t maximum_number_of_live_fp_registers_; 237 238 ART_FRIEND_TEST(RegisterAllocatorTest, FreeUntil); 239 ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); 240 241 DISALLOW_COPY_AND_ASSIGN(RegisterAllocator); 242 }; 243 244 } // namespace art 245 246 #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_H_ 247
