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