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