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
25namespace art {
26
27class CodeGenerator;
28class HBasicBlock;
29class HGraph;
30class HInstruction;
31class HParallelMove;
32class HPhi;
33class LiveInterval;
34class Location;
35class SsaLivenessAnalysis;
36
37/**
38 * An implementation of a linear scan register allocator on an `HGraph` with SSA form.
39 */
40class 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