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