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_LINEAR_SCAN_H_ 18 #define ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_LINEAR_SCAN_H_ 19 20 #include "arch/instruction_set.h" 21 #include "base/macros.h" 22 #include "base/scoped_arena_containers.h" 23 #include "register_allocator.h" 24 25 namespace art HIDDEN { 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 RegisterAllocatorLinearScan : public RegisterAllocator { 41 public: 42 RegisterAllocatorLinearScan(ScopedArenaAllocator* allocator, 43 CodeGenerator* codegen, 44 const SsaLivenessAnalysis& analysis); 45 ~RegisterAllocatorLinearScan() override; 46 47 void AllocateRegisters() override; 48 Validate(bool log_fatal_on_failure)49 bool Validate(bool log_fatal_on_failure) override { 50 processing_core_registers_ = true; 51 if (!ValidateInternal(log_fatal_on_failure)) { 52 return false; 53 } 54 processing_core_registers_ = false; 55 return ValidateInternal(log_fatal_on_failure); 56 } 57 GetNumberOfSpillSlots()58 size_t GetNumberOfSpillSlots() const { 59 return int_spill_slots_.size() 60 + long_spill_slots_.size() 61 + float_spill_slots_.size() 62 + double_spill_slots_.size() 63 + catch_phi_spill_slots_; 64 } 65 66 private: 67 // Main methods of the allocator. 68 void LinearScan(); 69 bool TryAllocateFreeReg(LiveInterval* interval); 70 bool AllocateBlockedReg(LiveInterval* interval); 71 72 // Add `interval` in the given sorted list. 73 static void AddSorted(ScopedArenaVector<LiveInterval*>* array, LiveInterval* interval); 74 75 // Returns whether `reg` is blocked by the code generator. 76 bool IsBlocked(int reg) const; 77 78 // Update the interval for the register in `location` to cover [start, end). 79 void BlockRegister(Location location, size_t start, size_t end); 80 void BlockRegisters(size_t start, size_t end, bool caller_save_only = false); 81 82 // Allocate a spill slot for the given interval. Should be called in linear 83 // order of interval starting positions. 84 void AllocateSpillSlotFor(LiveInterval* interval); 85 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 91 // Helper methods. 92 void AllocateRegistersInternal(); 93 void ProcessInstruction(HInstruction* instruction); 94 bool ValidateInternal(bool log_fatal_on_failure) const; 95 void DumpInterval(std::ostream& stream, LiveInterval* interval) const; 96 void DumpAllIntervals(std::ostream& stream) const; 97 int FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const; 98 int FindAvailableRegister(size_t* next_use, LiveInterval* current) const; 99 bool IsCallerSaveRegister(int reg) const; 100 101 // If any inputs require specific registers, block those registers 102 // at the position of this instruction. 103 void CheckForFixedInputs(HInstruction* instruction); 104 105 // If the output of an instruction requires a specific register, split 106 // the interval and assign the register to the first part. 107 void CheckForFixedOutput(HInstruction* instruction); 108 109 // Add all applicable safepoints to a live interval. 110 // Currently depends on instruction processing order. 111 void AddSafepointsFor(HInstruction* instruction); 112 113 // Collect all live intervals associated with the temporary locations 114 // needed by an instruction. 115 void CheckForTempLiveIntervals(HInstruction* instruction); 116 117 // If a safe point is needed, add a synthesized interval to later record 118 // the number of live registers at this point. 119 void CheckForSafepoint(HInstruction* instruction); 120 121 // Try to remove the SuspendCheck at function entry. Returns true if it was successful. 122 bool TryRemoveSuspendCheckEntry(HInstruction* instruction); 123 124 // Try splitting an active non-pair or unaligned pair interval at the given `position`. 125 // Returns whether it was successful at finding such an interval. 126 bool TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 127 size_t first_register_use, 128 size_t* next_use); 129 130 // List of intervals for core registers that must be processed, ordered by start 131 // position. Last entry is the interval that has the lowest start position. 132 // This list is initially populated before doing the linear scan. 133 ScopedArenaVector<LiveInterval*> unhandled_core_intervals_; 134 135 // List of intervals for floating-point registers. Same comments as above. 136 ScopedArenaVector<LiveInterval*> unhandled_fp_intervals_; 137 138 // Currently processed list of unhandled intervals. Either `unhandled_core_intervals_` 139 // or `unhandled_fp_intervals_`. 140 ScopedArenaVector<LiveInterval*>* unhandled_; 141 142 // List of intervals that have been processed. 143 ScopedArenaVector<LiveInterval*> handled_; 144 145 // List of intervals that are currently active when processing a new live interval. 146 // That is, they have a live range that spans the start of the new interval. 147 ScopedArenaVector<LiveInterval*> active_; 148 149 // List of intervals that are currently inactive when processing a new live interval. 150 // That is, they have a lifetime hole that spans the start of the new interval. 151 ScopedArenaVector<LiveInterval*> inactive_; 152 153 // Fixed intervals for physical registers. Such intervals cover the positions 154 // where an instruction requires a specific register. 155 ScopedArenaVector<LiveInterval*> physical_core_register_intervals_; 156 ScopedArenaVector<LiveInterval*> physical_fp_register_intervals_; 157 158 // Intervals for temporaries. Such intervals cover the positions 159 // where an instruction requires a temporary. 160 ScopedArenaVector<LiveInterval*> temp_intervals_; 161 162 // The spill slots allocated for live intervals. We ensure spill slots 163 // are typed to avoid (1) doing moves and swaps between two different kinds 164 // of registers, and (2) swapping between a single stack slot and a double 165 // stack slot. This simplifies the parallel move resolver. 166 ScopedArenaVector<size_t> int_spill_slots_; 167 ScopedArenaVector<size_t> long_spill_slots_; 168 ScopedArenaVector<size_t> float_spill_slots_; 169 ScopedArenaVector<size_t> double_spill_slots_; 170 171 // Spill slots allocated to catch phis. This category is special-cased because 172 // (1) slots are allocated prior to linear scan and in reverse linear order, 173 // (2) equivalent phis need to share slots despite having different types. 174 size_t catch_phi_spill_slots_; 175 176 // Instructions that need a safepoint. 177 ScopedArenaVector<HInstruction*> safepoints_; 178 179 // True if processing core registers. False if processing floating 180 // point registers. 181 bool processing_core_registers_; 182 183 // Number of registers for the current register kind (core or floating point). 184 size_t number_of_registers_; 185 186 // Temporary array, allocated ahead of time for simplicity. 187 size_t* registers_array_; 188 189 // Blocked registers, as decided by the code generator. 190 bool* const blocked_core_registers_; 191 bool* const blocked_fp_registers_; 192 193 // Slots reserved for out arguments. 194 size_t reserved_out_slots_; 195 196 ART_FRIEND_TEST(RegisterAllocatorTest, FreeUntil); 197 ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); 198 199 DISALLOW_COPY_AND_ASSIGN(RegisterAllocatorLinearScan); 200 }; 201 202 } // namespace art 203 204 #endif // ART_COMPILER_OPTIMIZING_REGISTER_ALLOCATOR_LINEAR_SCAN_H_ 205