1 /*
2 * Copyright (C) 2016 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 #include "register_allocator.h"
18
19 #include <iostream>
20 #include <sstream>
21
22 #include "base/scoped_arena_allocator.h"
23 #include "base/scoped_arena_containers.h"
24 #include "base/bit_vector-inl.h"
25 #include "code_generator.h"
26 #include "register_allocator_graph_color.h"
27 #include "register_allocator_linear_scan.h"
28 #include "ssa_liveness_analysis.h"
29
30 namespace art HIDDEN {
31
RegisterAllocator(ScopedArenaAllocator * allocator,CodeGenerator * codegen,const SsaLivenessAnalysis & liveness)32 RegisterAllocator::RegisterAllocator(ScopedArenaAllocator* allocator,
33 CodeGenerator* codegen,
34 const SsaLivenessAnalysis& liveness)
35 : allocator_(allocator),
36 codegen_(codegen),
37 liveness_(liveness) {}
38
Create(ScopedArenaAllocator * allocator,CodeGenerator * codegen,const SsaLivenessAnalysis & analysis,Strategy strategy)39 std::unique_ptr<RegisterAllocator> RegisterAllocator::Create(ScopedArenaAllocator* allocator,
40 CodeGenerator* codegen,
41 const SsaLivenessAnalysis& analysis,
42 Strategy strategy) {
43 switch (strategy) {
44 case kRegisterAllocatorLinearScan:
45 return std::unique_ptr<RegisterAllocator>(
46 new (allocator) RegisterAllocatorLinearScan(allocator, codegen, analysis));
47 case kRegisterAllocatorGraphColor:
48 return std::unique_ptr<RegisterAllocator>(
49 new (allocator) RegisterAllocatorGraphColor(allocator, codegen, analysis));
50 default:
51 LOG(FATAL) << "Invalid register allocation strategy: " << strategy;
52 UNREACHABLE();
53 }
54 }
55
~RegisterAllocator()56 RegisterAllocator::~RegisterAllocator() {
57 if (kIsDebugBuild) {
58 // Poison live interval pointers with "Error: BAD 71ve1nt3rval."
59 LiveInterval* bad_live_interval = reinterpret_cast<LiveInterval*>(0xebad7113u);
60 for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) {
61 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
62 it.Current()->SetLiveInterval(bad_live_interval);
63 }
64 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
65 it.Current()->SetLiveInterval(bad_live_interval);
66 }
67 }
68 }
69 }
70
71 class AllRangesIterator : public ValueObject {
72 public:
AllRangesIterator(LiveInterval * interval)73 explicit AllRangesIterator(LiveInterval* interval)
74 : current_interval_(interval),
75 current_range_(interval->GetFirstRange()) {}
76
Done() const77 bool Done() const { return current_interval_ == nullptr; }
CurrentRange() const78 LiveRange* CurrentRange() const { return current_range_; }
CurrentInterval() const79 LiveInterval* CurrentInterval() const { return current_interval_; }
80
Advance()81 void Advance() {
82 current_range_ = current_range_->GetNext();
83 if (current_range_ == nullptr) {
84 current_interval_ = current_interval_->GetNextSibling();
85 if (current_interval_ != nullptr) {
86 current_range_ = current_interval_->GetFirstRange();
87 }
88 }
89 }
90
91 private:
92 LiveInterval* current_interval_;
93 LiveRange* current_range_;
94
95 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator);
96 };
97
ValidateIntervals(ArrayRef<LiveInterval * const> intervals,size_t number_of_spill_slots,size_t number_of_out_slots,const CodeGenerator & codegen,bool processing_core_registers,bool log_fatal_on_failure)98 bool RegisterAllocator::ValidateIntervals(ArrayRef<LiveInterval* const> intervals,
99 size_t number_of_spill_slots,
100 size_t number_of_out_slots,
101 const CodeGenerator& codegen,
102 bool processing_core_registers,
103 bool log_fatal_on_failure) {
104 size_t number_of_registers = processing_core_registers
105 ? codegen.GetNumberOfCoreRegisters()
106 : codegen.GetNumberOfFloatingPointRegisters();
107 ScopedArenaAllocator allocator(codegen.GetGraph()->GetArenaStack());
108 ScopedArenaVector<ArenaBitVector*> liveness_of_values(
109 allocator.Adapter(kArenaAllocRegisterAllocatorValidate));
110 liveness_of_values.reserve(number_of_registers + number_of_spill_slots);
111
112 size_t max_end = 0u;
113 for (LiveInterval* start_interval : intervals) {
114 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) {
115 max_end = std::max(max_end, it.CurrentRange()->GetEnd());
116 }
117 }
118
119 // Allocate a bit vector per register. A live interval that has a register
120 // allocated will populate the associated bit vector based on its live ranges.
121 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) {
122 liveness_of_values.push_back(
123 ArenaBitVector::Create(&allocator, max_end, false, kArenaAllocRegisterAllocatorValidate));
124 liveness_of_values.back()->ClearAllBits();
125 }
126
127 for (LiveInterval* start_interval : intervals) {
128 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) {
129 LiveInterval* current = it.CurrentInterval();
130 HInstruction* defined_by = current->GetParent()->GetDefinedBy();
131 if (current->GetParent()->HasSpillSlot()
132 // Parameters and current method have their own stack slot.
133 && !(defined_by != nullptr && (defined_by->IsParameterValue()
134 || defined_by->IsCurrentMethod()))) {
135 BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers
136 + current->GetParent()->GetSpillSlot() / kVRegSize
137 - number_of_out_slots];
138 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
139 if (liveness_of_spill_slot->IsBitSet(j)) {
140 if (log_fatal_on_failure) {
141 std::ostringstream message;
142 message << "Spill slot conflict at " << j;
143 LOG(FATAL) << message.str();
144 } else {
145 return false;
146 }
147 } else {
148 liveness_of_spill_slot->SetBit(j);
149 }
150 }
151 }
152
153 if (current->HasRegister()) {
154 if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) {
155 // Only check when an error is fatal. Only tests code ask for non-fatal failures
156 // and test code may not properly fill the right information to the code generator.
157 CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister()));
158 }
159 BitVector* liveness_of_register = liveness_of_values[current->GetRegister()];
160 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
161 if (liveness_of_register->IsBitSet(j)) {
162 if (current->IsUsingInputRegister() && current->CanUseInputRegister()) {
163 continue;
164 }
165 if (log_fatal_on_failure) {
166 std::ostringstream message;
167 message << "Register conflict at " << j << " ";
168 if (defined_by != nullptr) {
169 message << "(" << defined_by->DebugName() << ")";
170 }
171 message << "for ";
172 if (processing_core_registers) {
173 codegen.DumpCoreRegister(message, current->GetRegister());
174 } else {
175 codegen.DumpFloatingPointRegister(message, current->GetRegister());
176 }
177 for (LiveInterval* interval : intervals) {
178 if (interval->HasRegister()
179 && interval->GetRegister() == current->GetRegister()
180 && interval->CoversSlow(j)) {
181 message << std::endl;
182 if (interval->GetDefinedBy() != nullptr) {
183 message << interval->GetDefinedBy()->GetKind() << " ";
184 } else {
185 message << "physical ";
186 }
187 interval->Dump(message);
188 }
189 }
190 LOG(FATAL) << message.str();
191 } else {
192 return false;
193 }
194 } else {
195 liveness_of_register->SetBit(j);
196 }
197 }
198 }
199 }
200 }
201 return true;
202 }
203
Split(LiveInterval * interval,size_t position)204 LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
205 DCHECK_GE(position, interval->GetStart());
206 DCHECK(!interval->IsDeadAt(position));
207 if (position == interval->GetStart()) {
208 // Spill slot will be allocated when handling `interval` again.
209 interval->ClearRegister();
210 if (interval->HasHighInterval()) {
211 interval->GetHighInterval()->ClearRegister();
212 } else if (interval->HasLowInterval()) {
213 interval->GetLowInterval()->ClearRegister();
214 }
215 return interval;
216 } else {
217 LiveInterval* new_interval = interval->SplitAt(position);
218 if (interval->HasHighInterval()) {
219 LiveInterval* high = interval->GetHighInterval()->SplitAt(position);
220 new_interval->SetHighInterval(high);
221 high->SetLowInterval(new_interval);
222 } else if (interval->HasLowInterval()) {
223 LiveInterval* low = interval->GetLowInterval()->SplitAt(position);
224 new_interval->SetLowInterval(low);
225 low->SetHighInterval(new_interval);
226 }
227 return new_interval;
228 }
229 }
230
SplitBetween(LiveInterval * interval,size_t from,size_t to)231 LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) {
232 HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2);
233 HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2);
234 DCHECK(block_from != nullptr);
235 DCHECK(block_to != nullptr);
236
237 // Both locations are in the same block. We split at the given location.
238 if (block_from == block_to) {
239 return Split(interval, to);
240 }
241
242 /*
243 * Non-linear control flow will force moves at every branch instruction to the new location.
244 * To avoid having all branches doing the moves, we find the next non-linear position and
245 * split the interval at this position. Take the following example (block number is the linear
246 * order position):
247 *
248 * B1
249 * / \
250 * B2 B3
251 * \ /
252 * B4
253 *
254 * B2 needs to split an interval, whose next use is in B4. If we were to split at the
255 * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval
256 * is now in the correct location. It makes performance worst if the interval is spilled
257 * and both B2 and B3 need to reload it before entering B4.
258 *
259 * By splitting at B3, we give a chance to the register allocator to allocate the
260 * interval to the same register as in B1, and therefore avoid doing any
261 * moves in B3.
262 */
263 if (block_from->GetDominator() != nullptr) {
264 for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) {
265 size_t position = dominated->GetLifetimeStart();
266 if ((position > from) && (block_to->GetLifetimeStart() > position)) {
267 // Even if we found a better block, we continue iterating in case
268 // a dominated block is closer.
269 // Note that dominated blocks are not sorted in liveness order.
270 block_to = dominated;
271 DCHECK_NE(block_to, block_from);
272 }
273 }
274 }
275
276 // If `to` is in a loop, find the outermost loop header which does not contain `from`.
277 for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) {
278 HBasicBlock* header = it.Current()->GetHeader();
279 if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) {
280 break;
281 }
282 block_to = header;
283 }
284
285 // Split at the start of the found block, to piggy back on existing moves
286 // due to resolution if non-linear control flow (see `ConnectSplitSiblings`).
287 return Split(interval, block_to->GetLifetimeStart());
288 }
289
290 } // namespace art
291