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.
Validate(bool log_fatal_on_failure)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 
GetNumberOfSpillSlots()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