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 #include "register_allocator.h"
18
19 #include <iostream>
20 #include <sstream>
21
22 #include "base/bit_vector-inl.h"
23 #include "code_generator.h"
24 #include "ssa_liveness_analysis.h"
25
26 namespace art {
27
28 static constexpr size_t kMaxLifetimePosition = -1;
29 static constexpr size_t kDefaultNumberOfSpillSlots = 4;
30
31 // For simplicity, we implement register pairs as (reg, reg + 1).
32 // Note that this is a requirement for double registers on ARM, since we
33 // allocate SRegister.
GetHighForLowRegister(int reg)34 static int GetHighForLowRegister(int reg) { return reg + 1; }
IsLowRegister(int reg)35 static bool IsLowRegister(int reg) { return (reg & 1) == 0; }
IsLowOfUnalignedPairInterval(LiveInterval * low)36 static bool IsLowOfUnalignedPairInterval(LiveInterval* low) {
37 return GetHighForLowRegister(low->GetRegister()) != low->GetHighInterval()->GetRegister();
38 }
39
RegisterAllocator(ArenaAllocator * allocator,CodeGenerator * codegen,const SsaLivenessAnalysis & liveness)40 RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator,
41 CodeGenerator* codegen,
42 const SsaLivenessAnalysis& liveness)
43 : allocator_(allocator),
44 codegen_(codegen),
45 liveness_(liveness),
46 unhandled_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)),
47 unhandled_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)),
48 unhandled_(nullptr),
49 handled_(allocator->Adapter(kArenaAllocRegisterAllocator)),
50 active_(allocator->Adapter(kArenaAllocRegisterAllocator)),
51 inactive_(allocator->Adapter(kArenaAllocRegisterAllocator)),
52 physical_core_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)),
53 physical_fp_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)),
54 temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)),
55 int_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)),
56 long_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)),
57 float_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)),
58 double_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)),
59 catch_phi_spill_slots_(0),
60 safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)),
61 processing_core_registers_(false),
62 number_of_registers_(-1),
63 registers_array_(nullptr),
64 blocked_core_registers_(codegen->GetBlockedCoreRegisters()),
65 blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()),
66 reserved_out_slots_(0),
67 maximum_number_of_live_core_registers_(0),
68 maximum_number_of_live_fp_registers_(0) {
69 temp_intervals_.reserve(4);
70 int_spill_slots_.reserve(kDefaultNumberOfSpillSlots);
71 long_spill_slots_.reserve(kDefaultNumberOfSpillSlots);
72 float_spill_slots_.reserve(kDefaultNumberOfSpillSlots);
73 double_spill_slots_.reserve(kDefaultNumberOfSpillSlots);
74
75 codegen->SetupBlockedRegisters();
76 physical_core_register_intervals_.resize(codegen->GetNumberOfCoreRegisters(), nullptr);
77 physical_fp_register_intervals_.resize(codegen->GetNumberOfFloatingPointRegisters(), nullptr);
78 // Always reserve for the current method and the graph's max out registers.
79 // TODO: compute it instead.
80 // ArtMethod* takes 2 vregs for 64 bits.
81 reserved_out_slots_ = InstructionSetPointerSize(codegen->GetInstructionSet()) / kVRegSize +
82 codegen->GetGraph()->GetMaximumNumberOfOutVRegs();
83 }
84
CanAllocateRegistersFor(const HGraph & graph ATTRIBUTE_UNUSED,InstructionSet instruction_set)85 bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED,
86 InstructionSet instruction_set) {
87 return instruction_set == kArm
88 || instruction_set == kArm64
89 || instruction_set == kMips
90 || instruction_set == kMips64
91 || instruction_set == kThumb2
92 || instruction_set == kX86
93 || instruction_set == kX86_64;
94 }
95
ShouldProcess(bool processing_core_registers,LiveInterval * interval)96 static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) {
97 if (interval == nullptr) return false;
98 bool is_core_register = (interval->GetType() != Primitive::kPrimDouble)
99 && (interval->GetType() != Primitive::kPrimFloat);
100 return processing_core_registers == is_core_register;
101 }
102
AllocateRegisters()103 void RegisterAllocator::AllocateRegisters() {
104 AllocateRegistersInternal();
105 Resolve();
106
107 if (kIsDebugBuild) {
108 processing_core_registers_ = true;
109 ValidateInternal(true);
110 processing_core_registers_ = false;
111 ValidateInternal(true);
112 // Check that the linear order is still correct with regards to lifetime positions.
113 // Since only parallel moves have been inserted during the register allocation,
114 // these checks are mostly for making sure these moves have been added correctly.
115 size_t current_liveness = 0;
116 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
117 HBasicBlock* block = it.Current();
118 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
119 HInstruction* instruction = inst_it.Current();
120 DCHECK_LE(current_liveness, instruction->GetLifetimePosition());
121 current_liveness = instruction->GetLifetimePosition();
122 }
123 for (HInstructionIterator inst_it(block->GetInstructions());
124 !inst_it.Done();
125 inst_it.Advance()) {
126 HInstruction* instruction = inst_it.Current();
127 DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName();
128 current_liveness = instruction->GetLifetimePosition();
129 }
130 }
131 }
132 }
133
BlockRegister(Location location,size_t start,size_t end)134 void RegisterAllocator::BlockRegister(Location location, size_t start, size_t end) {
135 int reg = location.reg();
136 DCHECK(location.IsRegister() || location.IsFpuRegister());
137 LiveInterval* interval = location.IsRegister()
138 ? physical_core_register_intervals_[reg]
139 : physical_fp_register_intervals_[reg];
140 Primitive::Type type = location.IsRegister()
141 ? Primitive::kPrimInt
142 : Primitive::kPrimFloat;
143 if (interval == nullptr) {
144 interval = LiveInterval::MakeFixedInterval(allocator_, reg, type);
145 if (location.IsRegister()) {
146 physical_core_register_intervals_[reg] = interval;
147 } else {
148 physical_fp_register_intervals_[reg] = interval;
149 }
150 }
151 DCHECK(interval->GetRegister() == reg);
152 interval->AddRange(start, end);
153 }
154
BlockRegisters(size_t start,size_t end,bool caller_save_only)155 void RegisterAllocator::BlockRegisters(size_t start, size_t end, bool caller_save_only) {
156 for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) {
157 if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) {
158 BlockRegister(Location::RegisterLocation(i), start, end);
159 }
160 }
161 for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) {
162 if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) {
163 BlockRegister(Location::FpuRegisterLocation(i), start, end);
164 }
165 }
166 }
167
AllocateRegistersInternal()168 void RegisterAllocator::AllocateRegistersInternal() {
169 // Iterate post-order, to ensure the list is sorted, and the last added interval
170 // is the one with the lowest start position.
171 for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
172 HBasicBlock* block = it.Current();
173 for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done();
174 back_it.Advance()) {
175 ProcessInstruction(back_it.Current());
176 }
177 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
178 ProcessInstruction(inst_it.Current());
179 }
180
181 if (block->IsCatchBlock() ||
182 (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) {
183 // By blocking all registers at the top of each catch block or irreducible loop, we force
184 // intervals belonging to the live-in set of the catch/header block to be spilled.
185 // TODO(ngeoffray): Phis in this block could be allocated in register.
186 size_t position = block->GetLifetimeStart();
187 BlockRegisters(position, position + 1);
188 }
189 }
190
191 number_of_registers_ = codegen_->GetNumberOfCoreRegisters();
192 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_,
193 kArenaAllocRegisterAllocator);
194 processing_core_registers_ = true;
195 unhandled_ = &unhandled_core_intervals_;
196 for (LiveInterval* fixed : physical_core_register_intervals_) {
197 if (fixed != nullptr) {
198 // Fixed interval is added to inactive_ instead of unhandled_.
199 // It's also the only type of inactive interval whose start position
200 // can be after the current interval during linear scan.
201 // Fixed interval is never split and never moves to unhandled_.
202 inactive_.push_back(fixed);
203 }
204 }
205 LinearScan();
206
207 inactive_.clear();
208 active_.clear();
209 handled_.clear();
210
211 number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters();
212 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_,
213 kArenaAllocRegisterAllocator);
214 processing_core_registers_ = false;
215 unhandled_ = &unhandled_fp_intervals_;
216 for (LiveInterval* fixed : physical_fp_register_intervals_) {
217 if (fixed != nullptr) {
218 // Fixed interval is added to inactive_ instead of unhandled_.
219 // It's also the only type of inactive interval whose start position
220 // can be after the current interval during linear scan.
221 // Fixed interval is never split and never moves to unhandled_.
222 inactive_.push_back(fixed);
223 }
224 }
225 LinearScan();
226 }
227
ProcessInstruction(HInstruction * instruction)228 void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
229 LocationSummary* locations = instruction->GetLocations();
230 size_t position = instruction->GetLifetimePosition();
231
232 if (locations == nullptr) return;
233
234 // Create synthesized intervals for temporaries.
235 for (size_t i = 0; i < locations->GetTempCount(); ++i) {
236 Location temp = locations->GetTemp(i);
237 if (temp.IsRegister() || temp.IsFpuRegister()) {
238 BlockRegister(temp, position, position + 1);
239 // Ensure that an explicit temporary register is marked as being allocated.
240 codegen_->AddAllocatedRegister(temp);
241 } else {
242 DCHECK(temp.IsUnallocated());
243 switch (temp.GetPolicy()) {
244 case Location::kRequiresRegister: {
245 LiveInterval* interval =
246 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt);
247 temp_intervals_.push_back(interval);
248 interval->AddTempUse(instruction, i);
249 unhandled_core_intervals_.push_back(interval);
250 break;
251 }
252
253 case Location::kRequiresFpuRegister: {
254 LiveInterval* interval =
255 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble);
256 temp_intervals_.push_back(interval);
257 interval->AddTempUse(instruction, i);
258 if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) {
259 interval->AddHighInterval(/* is_temp */ true);
260 LiveInterval* high = interval->GetHighInterval();
261 temp_intervals_.push_back(high);
262 unhandled_fp_intervals_.push_back(high);
263 }
264 unhandled_fp_intervals_.push_back(interval);
265 break;
266 }
267
268 default:
269 LOG(FATAL) << "Unexpected policy for temporary location "
270 << temp.GetPolicy();
271 }
272 }
273 }
274
275 bool core_register = (instruction->GetType() != Primitive::kPrimDouble)
276 && (instruction->GetType() != Primitive::kPrimFloat);
277
278 if (locations->NeedsSafepoint()) {
279 if (codegen_->IsLeafMethod()) {
280 // TODO: We do this here because we do not want the suspend check to artificially
281 // create live registers. We should find another place, but this is currently the
282 // simplest.
283 DCHECK(instruction->IsSuspendCheckEntry());
284 instruction->GetBlock()->RemoveInstruction(instruction);
285 return;
286 }
287 safepoints_.push_back(instruction);
288 if (locations->OnlyCallsOnSlowPath()) {
289 // We add a synthesized range at this position to record the live registers
290 // at this position. Ideally, we could just update the safepoints when locations
291 // are updated, but we currently need to know the full stack size before updating
292 // locations (because of parameters and the fact that we don't have a frame pointer).
293 // And knowing the full stack size requires to know the maximum number of live
294 // registers at calls in slow paths.
295 // By adding the following interval in the algorithm, we can compute this
296 // maximum before updating locations.
297 LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction);
298 interval->AddRange(position, position + 1);
299 AddSorted(&unhandled_core_intervals_, interval);
300 AddSorted(&unhandled_fp_intervals_, interval);
301 }
302 }
303
304 if (locations->WillCall()) {
305 BlockRegisters(position, position + 1, /* caller_save_only */ true);
306 }
307
308 for (size_t i = 0; i < instruction->InputCount(); ++i) {
309 Location input = locations->InAt(i);
310 if (input.IsRegister() || input.IsFpuRegister()) {
311 BlockRegister(input, position, position + 1);
312 } else if (input.IsPair()) {
313 BlockRegister(input.ToLow(), position, position + 1);
314 BlockRegister(input.ToHigh(), position, position + 1);
315 }
316 }
317
318 LiveInterval* current = instruction->GetLiveInterval();
319 if (current == nullptr) return;
320
321 ArenaVector<LiveInterval*>& unhandled = core_register
322 ? unhandled_core_intervals_
323 : unhandled_fp_intervals_;
324
325 DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back()));
326
327 if (codegen_->NeedsTwoRegisters(current->GetType())) {
328 current->AddHighInterval();
329 }
330
331 for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) {
332 HInstruction* safepoint = safepoints_[safepoint_index - 1u];
333 size_t safepoint_position = safepoint->GetLifetimePosition();
334
335 // Test that safepoints are ordered in the optimal way.
336 DCHECK(safepoint_index == safepoints_.size() ||
337 safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position);
338
339 if (safepoint_position == current->GetStart()) {
340 // The safepoint is for this instruction, so the location of the instruction
341 // does not need to be saved.
342 DCHECK_EQ(safepoint_index, safepoints_.size());
343 DCHECK_EQ(safepoint, instruction);
344 continue;
345 } else if (current->IsDeadAt(safepoint_position)) {
346 break;
347 } else if (!current->Covers(safepoint_position)) {
348 // Hole in the interval.
349 continue;
350 }
351 current->AddSafepoint(safepoint);
352 }
353 current->ResetSearchCache();
354
355 // Some instructions define their output in fixed register/stack slot. We need
356 // to ensure we know these locations before doing register allocation. For a
357 // given register, we create an interval that covers these locations. The register
358 // will be unavailable at these locations when trying to allocate one for an
359 // interval.
360 //
361 // The backwards walking ensures the ranges are ordered on increasing start positions.
362 Location output = locations->Out();
363 if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) {
364 Location first = locations->InAt(0);
365 if (first.IsRegister() || first.IsFpuRegister()) {
366 current->SetFrom(position + 1);
367 current->SetRegister(first.reg());
368 } else if (first.IsPair()) {
369 current->SetFrom(position + 1);
370 current->SetRegister(first.low());
371 LiveInterval* high = current->GetHighInterval();
372 high->SetRegister(first.high());
373 high->SetFrom(position + 1);
374 }
375 } else if (output.IsRegister() || output.IsFpuRegister()) {
376 // Shift the interval's start by one to account for the blocked register.
377 current->SetFrom(position + 1);
378 current->SetRegister(output.reg());
379 BlockRegister(output, position, position + 1);
380 } else if (output.IsPair()) {
381 current->SetFrom(position + 1);
382 current->SetRegister(output.low());
383 LiveInterval* high = current->GetHighInterval();
384 high->SetRegister(output.high());
385 high->SetFrom(position + 1);
386 BlockRegister(output.ToLow(), position, position + 1);
387 BlockRegister(output.ToHigh(), position, position + 1);
388 } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) {
389 current->SetSpillSlot(output.GetStackIndex());
390 } else {
391 DCHECK(output.IsUnallocated() || output.IsConstant());
392 }
393
394 if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) {
395 AllocateSpillSlotForCatchPhi(instruction->AsPhi());
396 }
397
398 // If needed, add interval to the list of unhandled intervals.
399 if (current->HasSpillSlot() || instruction->IsConstant()) {
400 // Split just before first register use.
401 size_t first_register_use = current->FirstRegisterUse();
402 if (first_register_use != kNoLifetime) {
403 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
404 // Don't add directly to `unhandled`, it needs to be sorted and the start
405 // of this new interval might be after intervals already in the list.
406 AddSorted(&unhandled, split);
407 } else {
408 // Nothing to do, we won't allocate a register for this value.
409 }
410 } else {
411 // Don't add directly to `unhandled`, temp or safepoint intervals
412 // for this instruction may have been added, and those can be
413 // processed first.
414 AddSorted(&unhandled, current);
415 }
416 }
417
418 class AllRangesIterator : public ValueObject {
419 public:
AllRangesIterator(LiveInterval * interval)420 explicit AllRangesIterator(LiveInterval* interval)
421 : current_interval_(interval),
422 current_range_(interval->GetFirstRange()) {}
423
Done() const424 bool Done() const { return current_interval_ == nullptr; }
CurrentRange() const425 LiveRange* CurrentRange() const { return current_range_; }
CurrentInterval() const426 LiveInterval* CurrentInterval() const { return current_interval_; }
427
Advance()428 void Advance() {
429 current_range_ = current_range_->GetNext();
430 if (current_range_ == nullptr) {
431 current_interval_ = current_interval_->GetNextSibling();
432 if (current_interval_ != nullptr) {
433 current_range_ = current_interval_->GetFirstRange();
434 }
435 }
436 }
437
438 private:
439 LiveInterval* current_interval_;
440 LiveRange* current_range_;
441
442 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator);
443 };
444
ValidateInternal(bool log_fatal_on_failure) const445 bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const {
446 // To simplify unit testing, we eagerly create the array of intervals, and
447 // call the helper method.
448 ArenaVector<LiveInterval*> intervals(allocator_->Adapter(kArenaAllocRegisterAllocatorValidate));
449 for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) {
450 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
451 if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) {
452 intervals.push_back(instruction->GetLiveInterval());
453 }
454 }
455
456 const ArenaVector<LiveInterval*>* physical_register_intervals = processing_core_registers_
457 ? &physical_core_register_intervals_
458 : &physical_fp_register_intervals_;
459 for (LiveInterval* fixed : *physical_register_intervals) {
460 if (fixed != nullptr) {
461 intervals.push_back(fixed);
462 }
463 }
464
465 for (LiveInterval* temp : temp_intervals_) {
466 if (ShouldProcess(processing_core_registers_, temp)) {
467 intervals.push_back(temp);
468 }
469 }
470
471 return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_,
472 allocator_, processing_core_registers_, log_fatal_on_failure);
473 }
474
ValidateIntervals(const ArenaVector<LiveInterval * > & intervals,size_t number_of_spill_slots,size_t number_of_out_slots,const CodeGenerator & codegen,ArenaAllocator * allocator,bool processing_core_registers,bool log_fatal_on_failure)475 bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals,
476 size_t number_of_spill_slots,
477 size_t number_of_out_slots,
478 const CodeGenerator& codegen,
479 ArenaAllocator* allocator,
480 bool processing_core_registers,
481 bool log_fatal_on_failure) {
482 size_t number_of_registers = processing_core_registers
483 ? codegen.GetNumberOfCoreRegisters()
484 : codegen.GetNumberOfFloatingPointRegisters();
485 ArenaVector<ArenaBitVector*> liveness_of_values(
486 allocator->Adapter(kArenaAllocRegisterAllocatorValidate));
487 liveness_of_values.reserve(number_of_registers + number_of_spill_slots);
488
489 size_t max_end = 0u;
490 for (LiveInterval* start_interval : intervals) {
491 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) {
492 max_end = std::max(max_end, it.CurrentRange()->GetEnd());
493 }
494 }
495
496 // Allocate a bit vector per register. A live interval that has a register
497 // allocated will populate the associated bit vector based on its live ranges.
498 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) {
499 liveness_of_values.push_back(
500 ArenaBitVector::Create(allocator, max_end, false, kArenaAllocRegisterAllocatorValidate));
501 }
502
503 for (LiveInterval* start_interval : intervals) {
504 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) {
505 LiveInterval* current = it.CurrentInterval();
506 HInstruction* defined_by = current->GetParent()->GetDefinedBy();
507 if (current->GetParent()->HasSpillSlot()
508 // Parameters and current method have their own stack slot.
509 && !(defined_by != nullptr && (defined_by->IsParameterValue()
510 || defined_by->IsCurrentMethod()))) {
511 BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers
512 + current->GetParent()->GetSpillSlot() / kVRegSize
513 - number_of_out_slots];
514 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
515 if (liveness_of_spill_slot->IsBitSet(j)) {
516 if (log_fatal_on_failure) {
517 std::ostringstream message;
518 message << "Spill slot conflict at " << j;
519 LOG(FATAL) << message.str();
520 } else {
521 return false;
522 }
523 } else {
524 liveness_of_spill_slot->SetBit(j);
525 }
526 }
527 }
528
529 if (current->HasRegister()) {
530 if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) {
531 // Only check when an error is fatal. Only tests code ask for non-fatal failures
532 // and test code may not properly fill the right information to the code generator.
533 CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister()));
534 }
535 BitVector* liveness_of_register = liveness_of_values[current->GetRegister()];
536 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) {
537 if (liveness_of_register->IsBitSet(j)) {
538 if (current->IsUsingInputRegister() && current->CanUseInputRegister()) {
539 continue;
540 }
541 if (log_fatal_on_failure) {
542 std::ostringstream message;
543 message << "Register conflict at " << j << " ";
544 if (defined_by != nullptr) {
545 message << "(" << defined_by->DebugName() << ")";
546 }
547 message << "for ";
548 if (processing_core_registers) {
549 codegen.DumpCoreRegister(message, current->GetRegister());
550 } else {
551 codegen.DumpFloatingPointRegister(message, current->GetRegister());
552 }
553 LOG(FATAL) << message.str();
554 } else {
555 return false;
556 }
557 } else {
558 liveness_of_register->SetBit(j);
559 }
560 }
561 }
562 }
563 }
564 return true;
565 }
566
DumpInterval(std::ostream & stream,LiveInterval * interval) const567 void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const {
568 interval->Dump(stream);
569 stream << ": ";
570 if (interval->HasRegister()) {
571 if (interval->IsFloatingPoint()) {
572 codegen_->DumpFloatingPointRegister(stream, interval->GetRegister());
573 } else {
574 codegen_->DumpCoreRegister(stream, interval->GetRegister());
575 }
576 } else {
577 stream << "spilled";
578 }
579 stream << std::endl;
580 }
581
DumpAllIntervals(std::ostream & stream) const582 void RegisterAllocator::DumpAllIntervals(std::ostream& stream) const {
583 stream << "inactive: " << std::endl;
584 for (LiveInterval* inactive_interval : inactive_) {
585 DumpInterval(stream, inactive_interval);
586 }
587 stream << "active: " << std::endl;
588 for (LiveInterval* active_interval : active_) {
589 DumpInterval(stream, active_interval);
590 }
591 stream << "unhandled: " << std::endl;
592 auto unhandled = (unhandled_ != nullptr) ?
593 unhandled_ : &unhandled_core_intervals_;
594 for (LiveInterval* unhandled_interval : *unhandled) {
595 DumpInterval(stream, unhandled_interval);
596 }
597 stream << "handled: " << std::endl;
598 for (LiveInterval* handled_interval : handled_) {
599 DumpInterval(stream, handled_interval);
600 }
601 }
602
603 // By the book implementation of a linear scan register allocator.
LinearScan()604 void RegisterAllocator::LinearScan() {
605 while (!unhandled_->empty()) {
606 // (1) Remove interval with the lowest start position from unhandled.
607 LiveInterval* current = unhandled_->back();
608 unhandled_->pop_back();
609
610 // Make sure the interval is an expected state.
611 DCHECK(!current->IsFixed() && !current->HasSpillSlot());
612 // Make sure we are going in the right order.
613 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() >= current->GetStart());
614 // Make sure a low interval is always with a high.
615 DCHECK(!current->IsLowInterval() || unhandled_->back()->IsHighInterval());
616 // Make sure a high interval is always with a low.
617 DCHECK(current->IsLowInterval() ||
618 unhandled_->empty() ||
619 !unhandled_->back()->IsHighInterval());
620
621 size_t position = current->GetStart();
622
623 // Remember the inactive_ size here since the ones moved to inactive_ from
624 // active_ below shouldn't need to be re-checked.
625 size_t inactive_intervals_to_handle = inactive_.size();
626
627 // (2) Remove currently active intervals that are dead at this position.
628 // Move active intervals that have a lifetime hole at this position
629 // to inactive.
630 auto active_kept_end = std::remove_if(
631 active_.begin(),
632 active_.end(),
633 [this, position](LiveInterval* interval) {
634 if (interval->IsDeadAt(position)) {
635 handled_.push_back(interval);
636 return true;
637 } else if (!interval->Covers(position)) {
638 inactive_.push_back(interval);
639 return true;
640 } else {
641 return false; // Keep this interval.
642 }
643 });
644 active_.erase(active_kept_end, active_.end());
645
646 // (3) Remove currently inactive intervals that are dead at this position.
647 // Move inactive intervals that cover this position to active.
648 auto inactive_to_handle_end = inactive_.begin() + inactive_intervals_to_handle;
649 auto inactive_kept_end = std::remove_if(
650 inactive_.begin(),
651 inactive_to_handle_end,
652 [this, position](LiveInterval* interval) {
653 DCHECK(interval->GetStart() < position || interval->IsFixed());
654 if (interval->IsDeadAt(position)) {
655 handled_.push_back(interval);
656 return true;
657 } else if (interval->Covers(position)) {
658 active_.push_back(interval);
659 return true;
660 } else {
661 return false; // Keep this interval.
662 }
663 });
664 inactive_.erase(inactive_kept_end, inactive_to_handle_end);
665
666 if (current->IsSlowPathSafepoint()) {
667 // Synthesized interval to record the maximum number of live registers
668 // at safepoints. No need to allocate a register for it.
669 if (processing_core_registers_) {
670 maximum_number_of_live_core_registers_ =
671 std::max(maximum_number_of_live_core_registers_, active_.size());
672 } else {
673 maximum_number_of_live_fp_registers_ =
674 std::max(maximum_number_of_live_fp_registers_, active_.size());
675 }
676 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() > current->GetStart());
677 continue;
678 }
679
680 if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) {
681 DCHECK(!current->HasRegister());
682 // Allocating the low part was unsucessful. The splitted interval for the high part
683 // will be handled next (it is in the `unhandled_` list).
684 continue;
685 }
686
687 // (4) Try to find an available register.
688 bool success = TryAllocateFreeReg(current);
689
690 // (5) If no register could be found, we need to spill.
691 if (!success) {
692 success = AllocateBlockedReg(current);
693 }
694
695 // (6) If the interval had a register allocated, add it to the list of active
696 // intervals.
697 if (success) {
698 codegen_->AddAllocatedRegister(processing_core_registers_
699 ? Location::RegisterLocation(current->GetRegister())
700 : Location::FpuRegisterLocation(current->GetRegister()));
701 active_.push_back(current);
702 if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) {
703 current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister()));
704 }
705 }
706 }
707 }
708
FreeIfNotCoverAt(LiveInterval * interval,size_t position,size_t * free_until)709 static void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) {
710 DCHECK(!interval->IsHighInterval());
711 // Note that the same instruction may occur multiple times in the input list,
712 // so `free_until` may have changed already.
713 // Since `position` is not the current scan position, we need to use CoversSlow.
714 if (interval->IsDeadAt(position)) {
715 // Set the register to be free. Note that inactive intervals might later
716 // update this.
717 free_until[interval->GetRegister()] = kMaxLifetimePosition;
718 if (interval->HasHighInterval()) {
719 DCHECK(interval->GetHighInterval()->IsDeadAt(position));
720 free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition;
721 }
722 } else if (!interval->CoversSlow(position)) {
723 // The interval becomes inactive at `defined_by`. We make its register
724 // available only until the next use strictly after `defined_by`.
725 free_until[interval->GetRegister()] = interval->FirstUseAfter(position);
726 if (interval->HasHighInterval()) {
727 DCHECK(!interval->GetHighInterval()->CoversSlow(position));
728 free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()];
729 }
730 }
731 }
732
733 // Find a free register. If multiple are found, pick the register that
734 // is free the longest.
TryAllocateFreeReg(LiveInterval * current)735 bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) {
736 size_t* free_until = registers_array_;
737
738 // First set all registers to be free.
739 for (size_t i = 0; i < number_of_registers_; ++i) {
740 free_until[i] = kMaxLifetimePosition;
741 }
742
743 // For each active interval, set its register to not free.
744 for (LiveInterval* interval : active_) {
745 DCHECK(interval->HasRegister());
746 free_until[interval->GetRegister()] = 0;
747 }
748
749 // An interval that starts an instruction (that is, it is not split), may
750 // re-use the registers used by the inputs of that instruciton, based on the
751 // location summary.
752 HInstruction* defined_by = current->GetDefinedBy();
753 if (defined_by != nullptr && !current->IsSplit()) {
754 LocationSummary* locations = defined_by->GetLocations();
755 if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) {
756 for (size_t i = 0, e = defined_by->InputCount(); i < e; ++i) {
757 // Take the last interval of the input. It is the location of that interval
758 // that will be used at `defined_by`.
759 LiveInterval* interval = defined_by->InputAt(i)->GetLiveInterval()->GetLastSibling();
760 // Note that interval may have not been processed yet.
761 // TODO: Handle non-split intervals last in the work list.
762 if (locations->InAt(i).IsValid()
763 && interval->HasRegister()
764 && interval->SameRegisterKind(*current)) {
765 // The input must be live until the end of `defined_by`, to comply to
766 // the linear scan algorithm. So we use `defined_by`'s end lifetime
767 // position to check whether the input is dead or is inactive after
768 // `defined_by`.
769 DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition()));
770 size_t position = defined_by->GetLifetimePosition() + 1;
771 FreeIfNotCoverAt(interval, position, free_until);
772 }
773 }
774 }
775 }
776
777 // For each inactive interval, set its register to be free until
778 // the next intersection with `current`.
779 for (LiveInterval* inactive : inactive_) {
780 // Temp/Slow-path-safepoint interval has no holes.
781 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint());
782 if (!current->IsSplit() && !inactive->IsFixed()) {
783 // Neither current nor inactive are fixed.
784 // Thanks to SSA, a non-split interval starting in a hole of an
785 // inactive interval should never intersect with that inactive interval.
786 // Only if it's not fixed though, because fixed intervals don't come from SSA.
787 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
788 continue;
789 }
790
791 DCHECK(inactive->HasRegister());
792 if (free_until[inactive->GetRegister()] == 0) {
793 // Already used by some active interval. No need to intersect.
794 continue;
795 }
796 size_t next_intersection = inactive->FirstIntersectionWith(current);
797 if (next_intersection != kNoLifetime) {
798 free_until[inactive->GetRegister()] =
799 std::min(free_until[inactive->GetRegister()], next_intersection);
800 }
801 }
802
803 int reg = kNoRegister;
804 if (current->HasRegister()) {
805 // Some instructions have a fixed register output.
806 reg = current->GetRegister();
807 if (free_until[reg] == 0) {
808 DCHECK(current->IsHighInterval());
809 // AllocateBlockedReg will spill the holder of the register.
810 return false;
811 }
812 } else {
813 DCHECK(!current->IsHighInterval());
814 int hint = current->FindFirstRegisterHint(free_until, liveness_);
815 if ((hint != kNoRegister)
816 // For simplicity, if the hint we are getting for a pair cannot be used,
817 // we are just going to allocate a new pair.
818 && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) {
819 DCHECK(!IsBlocked(hint));
820 reg = hint;
821 } else if (current->IsLowInterval()) {
822 reg = FindAvailableRegisterPair(free_until, current->GetStart());
823 } else {
824 reg = FindAvailableRegister(free_until, current);
825 }
826 }
827
828 DCHECK_NE(reg, kNoRegister);
829 // If we could not find a register, we need to spill.
830 if (free_until[reg] == 0) {
831 return false;
832 }
833
834 if (current->IsLowInterval()) {
835 // If the high register of this interval is not available, we need to spill.
836 int high_reg = current->GetHighInterval()->GetRegister();
837 if (high_reg == kNoRegister) {
838 high_reg = GetHighForLowRegister(reg);
839 }
840 if (free_until[high_reg] == 0) {
841 return false;
842 }
843 }
844
845 current->SetRegister(reg);
846 if (!current->IsDeadAt(free_until[reg])) {
847 // If the register is only available for a subset of live ranges
848 // covered by `current`, split `current` before the position where
849 // the register is not available anymore.
850 LiveInterval* split = SplitBetween(current, current->GetStart(), free_until[reg]);
851 DCHECK(split != nullptr);
852 AddSorted(unhandled_, split);
853 }
854 return true;
855 }
856
IsBlocked(int reg) const857 bool RegisterAllocator::IsBlocked(int reg) const {
858 return processing_core_registers_
859 ? blocked_core_registers_[reg]
860 : blocked_fp_registers_[reg];
861 }
862
FindAvailableRegisterPair(size_t * next_use,size_t starting_at) const863 int RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const {
864 int reg = kNoRegister;
865 // Pick the register pair that is used the last.
866 for (size_t i = 0; i < number_of_registers_; ++i) {
867 if (IsBlocked(i)) continue;
868 if (!IsLowRegister(i)) continue;
869 int high_register = GetHighForLowRegister(i);
870 if (IsBlocked(high_register)) continue;
871 int existing_high_register = GetHighForLowRegister(reg);
872 if ((reg == kNoRegister) || (next_use[i] >= next_use[reg]
873 && next_use[high_register] >= next_use[existing_high_register])) {
874 reg = i;
875 if (next_use[i] == kMaxLifetimePosition
876 && next_use[high_register] == kMaxLifetimePosition) {
877 break;
878 }
879 } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) {
880 // If one of the current register is known to be unavailable, just unconditionally
881 // try a new one.
882 reg = i;
883 }
884 }
885 return reg;
886 }
887
IsCallerSaveRegister(int reg) const888 bool RegisterAllocator::IsCallerSaveRegister(int reg) const {
889 return processing_core_registers_
890 ? !codegen_->IsCoreCalleeSaveRegister(reg)
891 : !codegen_->IsFloatingPointCalleeSaveRegister(reg);
892 }
893
FindAvailableRegister(size_t * next_use,LiveInterval * current) const894 int RegisterAllocator::FindAvailableRegister(size_t* next_use, LiveInterval* current) const {
895 // We special case intervals that do not span a safepoint to try to find a caller-save
896 // register if one is available. We iterate from 0 to the number of registers,
897 // so if there are caller-save registers available at the end, we continue the iteration.
898 bool prefers_caller_save = !current->HasWillCallSafepoint();
899 int reg = kNoRegister;
900 for (size_t i = 0; i < number_of_registers_; ++i) {
901 if (IsBlocked(i)) {
902 // Register cannot be used. Continue.
903 continue;
904 }
905
906 // Best case: we found a register fully available.
907 if (next_use[i] == kMaxLifetimePosition) {
908 if (prefers_caller_save && !IsCallerSaveRegister(i)) {
909 // We can get shorter encodings on some platforms by using
910 // small register numbers. So only update the candidate if the previous
911 // one was not available for the whole method.
912 if (reg == kNoRegister || next_use[reg] != kMaxLifetimePosition) {
913 reg = i;
914 }
915 // Continue the iteration in the hope of finding a caller save register.
916 continue;
917 } else {
918 reg = i;
919 // We know the register is good enough. Return it.
920 break;
921 }
922 }
923
924 // If we had no register before, take this one as a reference.
925 if (reg == kNoRegister) {
926 reg = i;
927 continue;
928 }
929
930 // Pick the register that is used the last.
931 if (next_use[i] > next_use[reg]) {
932 reg = i;
933 continue;
934 }
935 }
936 return reg;
937 }
938
939 // Remove interval and its other half if any. Return iterator to the following element.
RemoveIntervalAndPotentialOtherHalf(ArenaVector<LiveInterval * > * intervals,ArenaVector<LiveInterval * >::iterator pos)940 static ArenaVector<LiveInterval*>::iterator RemoveIntervalAndPotentialOtherHalf(
941 ArenaVector<LiveInterval*>* intervals, ArenaVector<LiveInterval*>::iterator pos) {
942 DCHECK(intervals->begin() <= pos && pos < intervals->end());
943 LiveInterval* interval = *pos;
944 if (interval->IsLowInterval()) {
945 DCHECK(pos + 1 < intervals->end());
946 DCHECK_EQ(*(pos + 1), interval->GetHighInterval());
947 return intervals->erase(pos, pos + 2);
948 } else if (interval->IsHighInterval()) {
949 DCHECK(intervals->begin() < pos);
950 DCHECK_EQ(*(pos - 1), interval->GetLowInterval());
951 return intervals->erase(pos - 1, pos + 1);
952 } else {
953 return intervals->erase(pos);
954 }
955 }
956
TrySplitNonPairOrUnalignedPairIntervalAt(size_t position,size_t first_register_use,size_t * next_use)957 bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position,
958 size_t first_register_use,
959 size_t* next_use) {
960 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) {
961 LiveInterval* active = *it;
962 DCHECK(active->HasRegister());
963 if (active->IsFixed()) continue;
964 if (active->IsHighInterval()) continue;
965 if (first_register_use > next_use[active->GetRegister()]) continue;
966
967 // Split the first interval found that is either:
968 // 1) A non-pair interval.
969 // 2) A pair interval whose high is not low + 1.
970 // 3) A pair interval whose low is not even.
971 if (!active->IsLowInterval() ||
972 IsLowOfUnalignedPairInterval(active) ||
973 !IsLowRegister(active->GetRegister())) {
974 LiveInterval* split = Split(active, position);
975 if (split != active) {
976 handled_.push_back(active);
977 }
978 RemoveIntervalAndPotentialOtherHalf(&active_, it);
979 AddSorted(unhandled_, split);
980 return true;
981 }
982 }
983 return false;
984 }
985
986 // Find the register that is used the last, and spill the interval
987 // that holds it. If the first use of `current` is after that register
988 // we spill `current` instead.
AllocateBlockedReg(LiveInterval * current)989 bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) {
990 size_t first_register_use = current->FirstRegisterUse();
991 if (current->HasRegister()) {
992 DCHECK(current->IsHighInterval());
993 // The low interval has allocated the register for the high interval. In
994 // case the low interval had to split both intervals, we may end up in a
995 // situation where the high interval does not have a register use anymore.
996 // We must still proceed in order to split currently active and inactive
997 // uses of the high interval's register, and put the high interval in the
998 // active set.
999 DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr));
1000 } else if (first_register_use == kNoLifetime) {
1001 AllocateSpillSlotFor(current);
1002 return false;
1003 }
1004
1005 // First set all registers as not being used.
1006 size_t* next_use = registers_array_;
1007 for (size_t i = 0; i < number_of_registers_; ++i) {
1008 next_use[i] = kMaxLifetimePosition;
1009 }
1010
1011 // For each active interval, find the next use of its register after the
1012 // start of current.
1013 for (LiveInterval* active : active_) {
1014 DCHECK(active->HasRegister());
1015 if (active->IsFixed()) {
1016 next_use[active->GetRegister()] = current->GetStart();
1017 } else {
1018 size_t use = active->FirstRegisterUseAfter(current->GetStart());
1019 if (use != kNoLifetime) {
1020 next_use[active->GetRegister()] = use;
1021 }
1022 }
1023 }
1024
1025 // For each inactive interval, find the next use of its register after the
1026 // start of current.
1027 for (LiveInterval* inactive : inactive_) {
1028 // Temp/Slow-path-safepoint interval has no holes.
1029 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint());
1030 if (!current->IsSplit() && !inactive->IsFixed()) {
1031 // Neither current nor inactive are fixed.
1032 // Thanks to SSA, a non-split interval starting in a hole of an
1033 // inactive interval should never intersect with that inactive interval.
1034 // Only if it's not fixed though, because fixed intervals don't come from SSA.
1035 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
1036 continue;
1037 }
1038 DCHECK(inactive->HasRegister());
1039 size_t next_intersection = inactive->FirstIntersectionWith(current);
1040 if (next_intersection != kNoLifetime) {
1041 if (inactive->IsFixed()) {
1042 next_use[inactive->GetRegister()] =
1043 std::min(next_intersection, next_use[inactive->GetRegister()]);
1044 } else {
1045 size_t use = inactive->FirstUseAfter(current->GetStart());
1046 if (use != kNoLifetime) {
1047 next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]);
1048 }
1049 }
1050 }
1051 }
1052
1053 int reg = kNoRegister;
1054 bool should_spill = false;
1055 if (current->HasRegister()) {
1056 DCHECK(current->IsHighInterval());
1057 reg = current->GetRegister();
1058 // When allocating the low part, we made sure the high register was available.
1059 DCHECK_LT(first_register_use, next_use[reg]);
1060 } else if (current->IsLowInterval()) {
1061 reg = FindAvailableRegisterPair(next_use, first_register_use);
1062 // We should spill if both registers are not available.
1063 should_spill = (first_register_use >= next_use[reg])
1064 || (first_register_use >= next_use[GetHighForLowRegister(reg)]);
1065 } else {
1066 DCHECK(!current->IsHighInterval());
1067 reg = FindAvailableRegister(next_use, current);
1068 should_spill = (first_register_use >= next_use[reg]);
1069 }
1070
1071 DCHECK_NE(reg, kNoRegister);
1072 if (should_spill) {
1073 DCHECK(!current->IsHighInterval());
1074 bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1));
1075 if (is_allocation_at_use_site) {
1076 if (!current->IsLowInterval()) {
1077 DumpInterval(std::cerr, current);
1078 DumpAllIntervals(std::cerr);
1079 // This situation has the potential to infinite loop, so we make it a non-debug CHECK.
1080 HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2);
1081 CHECK(false) << "There is not enough registers available for "
1082 << current->GetParent()->GetDefinedBy()->DebugName() << " "
1083 << current->GetParent()->GetDefinedBy()->GetId()
1084 << " at " << first_register_use - 1 << " "
1085 << (at == nullptr ? "" : at->DebugName());
1086 }
1087
1088 // If we're allocating a register for `current` because the instruction at
1089 // that position requires it, but we think we should spill, then there are
1090 // non-pair intervals or unaligned pair intervals blocking the allocation.
1091 // We split the first interval found, and put ourselves first in the
1092 // `unhandled_` list.
1093 bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(),
1094 first_register_use,
1095 next_use);
1096 DCHECK(success);
1097 LiveInterval* existing = unhandled_->back();
1098 DCHECK(existing->IsHighInterval());
1099 DCHECK_EQ(existing->GetLowInterval(), current);
1100 unhandled_->push_back(current);
1101 } else {
1102 // If the first use of that instruction is after the last use of the found
1103 // register, we split this interval just before its first register use.
1104 AllocateSpillSlotFor(current);
1105 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
1106 DCHECK(current != split);
1107 AddSorted(unhandled_, split);
1108 }
1109 return false;
1110 } else {
1111 // Use this register and spill the active and inactives interval that
1112 // have that register.
1113 current->SetRegister(reg);
1114
1115 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) {
1116 LiveInterval* active = *it;
1117 if (active->GetRegister() == reg) {
1118 DCHECK(!active->IsFixed());
1119 LiveInterval* split = Split(active, current->GetStart());
1120 if (split != active) {
1121 handled_.push_back(active);
1122 }
1123 RemoveIntervalAndPotentialOtherHalf(&active_, it);
1124 AddSorted(unhandled_, split);
1125 break;
1126 }
1127 }
1128
1129 // NOTE: Retrieve end() on each iteration because we're removing elements in the loop body.
1130 for (auto it = inactive_.begin(); it != inactive_.end(); ) {
1131 LiveInterval* inactive = *it;
1132 bool erased = false;
1133 if (inactive->GetRegister() == reg) {
1134 if (!current->IsSplit() && !inactive->IsFixed()) {
1135 // Neither current nor inactive are fixed.
1136 // Thanks to SSA, a non-split interval starting in a hole of an
1137 // inactive interval should never intersect with that inactive interval.
1138 // Only if it's not fixed though, because fixed intervals don't come from SSA.
1139 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime);
1140 } else {
1141 size_t next_intersection = inactive->FirstIntersectionWith(current);
1142 if (next_intersection != kNoLifetime) {
1143 if (inactive->IsFixed()) {
1144 LiveInterval* split = Split(current, next_intersection);
1145 DCHECK_NE(split, current);
1146 AddSorted(unhandled_, split);
1147 } else {
1148 // Split at the start of `current`, which will lead to splitting
1149 // at the end of the lifetime hole of `inactive`.
1150 LiveInterval* split = Split(inactive, current->GetStart());
1151 // If it's inactive, it must start before the current interval.
1152 DCHECK_NE(split, inactive);
1153 it = RemoveIntervalAndPotentialOtherHalf(&inactive_, it);
1154 erased = true;
1155 handled_.push_back(inactive);
1156 AddSorted(unhandled_, split);
1157 }
1158 }
1159 }
1160 }
1161 // If we have erased the element, `it` already points to the next element.
1162 // Otherwise we need to move to the next element.
1163 if (!erased) {
1164 ++it;
1165 }
1166 }
1167
1168 return true;
1169 }
1170 }
1171
AddSorted(ArenaVector<LiveInterval * > * array,LiveInterval * interval)1172 void RegisterAllocator::AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval) {
1173 DCHECK(!interval->IsFixed() && !interval->HasSpillSlot());
1174 size_t insert_at = 0;
1175 for (size_t i = array->size(); i > 0; --i) {
1176 LiveInterval* current = (*array)[i - 1u];
1177 // High intervals must be processed right after their low equivalent.
1178 if (current->StartsAfter(interval) && !current->IsHighInterval()) {
1179 insert_at = i;
1180 break;
1181 } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) {
1182 // Ensure the slow path interval is the last to be processed at its location: we want the
1183 // interval to know all live registers at this location.
1184 DCHECK(i == 1 || (*array)[i - 2u]->StartsAfter(current));
1185 insert_at = i;
1186 break;
1187 }
1188 }
1189
1190 // Insert the high interval before the low, to ensure the low is processed before.
1191 auto insert_pos = array->begin() + insert_at;
1192 if (interval->HasHighInterval()) {
1193 array->insert(insert_pos, { interval->GetHighInterval(), interval });
1194 } else if (interval->HasLowInterval()) {
1195 array->insert(insert_pos, { interval, interval->GetLowInterval() });
1196 } else {
1197 array->insert(insert_pos, interval);
1198 }
1199 }
1200
SplitBetween(LiveInterval * interval,size_t from,size_t to)1201 LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) {
1202 HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2);
1203 HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2);
1204 DCHECK(block_from != nullptr);
1205 DCHECK(block_to != nullptr);
1206
1207 // Both locations are in the same block. We split at the given location.
1208 if (block_from == block_to) {
1209 return Split(interval, to);
1210 }
1211
1212 /*
1213 * Non-linear control flow will force moves at every branch instruction to the new location.
1214 * To avoid having all branches doing the moves, we find the next non-linear position and
1215 * split the interval at this position. Take the following example (block number is the linear
1216 * order position):
1217 *
1218 * B1
1219 * / \
1220 * B2 B3
1221 * \ /
1222 * B4
1223 *
1224 * B2 needs to split an interval, whose next use is in B4. If we were to split at the
1225 * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval
1226 * is now in the correct location. It makes performance worst if the interval is spilled
1227 * and both B2 and B3 need to reload it before entering B4.
1228 *
1229 * By splitting at B3, we give a chance to the register allocator to allocate the
1230 * interval to the same register as in B1, and therefore avoid doing any
1231 * moves in B3.
1232 */
1233 if (block_from->GetDominator() != nullptr) {
1234 for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) {
1235 size_t position = dominated->GetLifetimeStart();
1236 if ((position > from) && (block_to->GetLifetimeStart() > position)) {
1237 // Even if we found a better block, we continue iterating in case
1238 // a dominated block is closer.
1239 // Note that dominated blocks are not sorted in liveness order.
1240 block_to = dominated;
1241 DCHECK_NE(block_to, block_from);
1242 }
1243 }
1244 }
1245
1246 // If `to` is in a loop, find the outermost loop header which does not contain `from`.
1247 for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) {
1248 HBasicBlock* header = it.Current()->GetHeader();
1249 if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) {
1250 break;
1251 }
1252 block_to = header;
1253 }
1254
1255 // Split at the start of the found block, to piggy back on existing moves
1256 // due to resolution if non-linear control flow (see `ConnectSplitSiblings`).
1257 return Split(interval, block_to->GetLifetimeStart());
1258 }
1259
Split(LiveInterval * interval,size_t position)1260 LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) {
1261 DCHECK_GE(position, interval->GetStart());
1262 DCHECK(!interval->IsDeadAt(position));
1263 if (position == interval->GetStart()) {
1264 // Spill slot will be allocated when handling `interval` again.
1265 interval->ClearRegister();
1266 if (interval->HasHighInterval()) {
1267 interval->GetHighInterval()->ClearRegister();
1268 } else if (interval->HasLowInterval()) {
1269 interval->GetLowInterval()->ClearRegister();
1270 }
1271 return interval;
1272 } else {
1273 LiveInterval* new_interval = interval->SplitAt(position);
1274 if (interval->HasHighInterval()) {
1275 LiveInterval* high = interval->GetHighInterval()->SplitAt(position);
1276 new_interval->SetHighInterval(high);
1277 high->SetLowInterval(new_interval);
1278 } else if (interval->HasLowInterval()) {
1279 LiveInterval* low = interval->GetLowInterval()->SplitAt(position);
1280 new_interval->SetLowInterval(low);
1281 low->SetHighInterval(new_interval);
1282 }
1283 return new_interval;
1284 }
1285 }
1286
AllocateSpillSlotFor(LiveInterval * interval)1287 void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) {
1288 if (interval->IsHighInterval()) {
1289 // The low interval already took care of allocating the spill slot.
1290 DCHECK(!interval->GetLowInterval()->HasRegister());
1291 DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot());
1292 return;
1293 }
1294
1295 LiveInterval* parent = interval->GetParent();
1296
1297 // An instruction gets a spill slot for its entire lifetime. If the parent
1298 // of this interval already has a spill slot, there is nothing to do.
1299 if (parent->HasSpillSlot()) {
1300 return;
1301 }
1302
1303 HInstruction* defined_by = parent->GetDefinedBy();
1304 DCHECK(!defined_by->IsPhi() || !defined_by->AsPhi()->IsCatchPhi());
1305
1306 if (defined_by->IsParameterValue()) {
1307 // Parameters have their own stack slot.
1308 parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue()));
1309 return;
1310 }
1311
1312 if (defined_by->IsCurrentMethod()) {
1313 parent->SetSpillSlot(0);
1314 return;
1315 }
1316
1317 if (defined_by->IsConstant()) {
1318 // Constants don't need a spill slot.
1319 return;
1320 }
1321
1322 ArenaVector<size_t>* spill_slots = nullptr;
1323 switch (interval->GetType()) {
1324 case Primitive::kPrimDouble:
1325 spill_slots = &double_spill_slots_;
1326 break;
1327 case Primitive::kPrimLong:
1328 spill_slots = &long_spill_slots_;
1329 break;
1330 case Primitive::kPrimFloat:
1331 spill_slots = &float_spill_slots_;
1332 break;
1333 case Primitive::kPrimNot:
1334 case Primitive::kPrimInt:
1335 case Primitive::kPrimChar:
1336 case Primitive::kPrimByte:
1337 case Primitive::kPrimBoolean:
1338 case Primitive::kPrimShort:
1339 spill_slots = &int_spill_slots_;
1340 break;
1341 case Primitive::kPrimVoid:
1342 LOG(FATAL) << "Unexpected type for interval " << interval->GetType();
1343 }
1344
1345 // Find an available spill slot.
1346 size_t slot = 0;
1347 for (size_t e = spill_slots->size(); slot < e; ++slot) {
1348 if ((*spill_slots)[slot] <= parent->GetStart()
1349 && (slot == (e - 1) || (*spill_slots)[slot + 1] <= parent->GetStart())) {
1350 break;
1351 }
1352 }
1353
1354 size_t end = interval->GetLastSibling()->GetEnd();
1355 if (parent->NeedsTwoSpillSlots()) {
1356 if (slot + 2u > spill_slots->size()) {
1357 // We need a new spill slot.
1358 spill_slots->resize(slot + 2u, end);
1359 }
1360 (*spill_slots)[slot] = end;
1361 (*spill_slots)[slot + 1] = end;
1362 } else {
1363 if (slot == spill_slots->size()) {
1364 // We need a new spill slot.
1365 spill_slots->push_back(end);
1366 } else {
1367 (*spill_slots)[slot] = end;
1368 }
1369 }
1370
1371 // Note that the exact spill slot location will be computed when we resolve,
1372 // that is when we know the number of spill slots for each type.
1373 parent->SetSpillSlot(slot);
1374 }
1375
IsValidDestination(Location destination)1376 static bool IsValidDestination(Location destination) {
1377 return destination.IsRegister()
1378 || destination.IsRegisterPair()
1379 || destination.IsFpuRegister()
1380 || destination.IsFpuRegisterPair()
1381 || destination.IsStackSlot()
1382 || destination.IsDoubleStackSlot();
1383 }
1384
AllocateSpillSlotForCatchPhi(HPhi * phi)1385 void RegisterAllocator::AllocateSpillSlotForCatchPhi(HPhi* phi) {
1386 LiveInterval* interval = phi->GetLiveInterval();
1387
1388 HInstruction* previous_phi = phi->GetPrevious();
1389 DCHECK(previous_phi == nullptr ||
1390 previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber())
1391 << "Phis expected to be sorted by vreg number, so that equivalent phis are adjacent.";
1392
1393 if (phi->IsVRegEquivalentOf(previous_phi)) {
1394 // This is an equivalent of the previous phi. We need to assign the same
1395 // catch phi slot.
1396 DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot());
1397 interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot());
1398 } else {
1399 // Allocate a new spill slot for this catch phi.
1400 // TODO: Reuse spill slots when intervals of phis from different catch
1401 // blocks do not overlap.
1402 interval->SetSpillSlot(catch_phi_spill_slots_);
1403 catch_phi_spill_slots_ += interval->NeedsTwoSpillSlots() ? 2 : 1;
1404 }
1405 }
1406
AddMove(HParallelMove * move,Location source,Location destination,HInstruction * instruction,Primitive::Type type) const1407 void RegisterAllocator::AddMove(HParallelMove* move,
1408 Location source,
1409 Location destination,
1410 HInstruction* instruction,
1411 Primitive::Type type) const {
1412 if (type == Primitive::kPrimLong
1413 && codegen_->ShouldSplitLongMoves()
1414 // The parallel move resolver knows how to deal with long constants.
1415 && !source.IsConstant()) {
1416 move->AddMove(source.ToLow(), destination.ToLow(), Primitive::kPrimInt, instruction);
1417 move->AddMove(source.ToHigh(), destination.ToHigh(), Primitive::kPrimInt, nullptr);
1418 } else {
1419 move->AddMove(source, destination, type, instruction);
1420 }
1421 }
1422
AddInputMoveFor(HInstruction * input,HInstruction * user,Location source,Location destination) const1423 void RegisterAllocator::AddInputMoveFor(HInstruction* input,
1424 HInstruction* user,
1425 Location source,
1426 Location destination) const {
1427 if (source.Equals(destination)) return;
1428
1429 DCHECK(!user->IsPhi());
1430
1431 HInstruction* previous = user->GetPrevious();
1432 HParallelMove* move = nullptr;
1433 if (previous == nullptr
1434 || !previous->IsParallelMove()
1435 || previous->GetLifetimePosition() < user->GetLifetimePosition()) {
1436 move = new (allocator_) HParallelMove(allocator_);
1437 move->SetLifetimePosition(user->GetLifetimePosition());
1438 user->GetBlock()->InsertInstructionBefore(move, user);
1439 } else {
1440 move = previous->AsParallelMove();
1441 }
1442 DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition());
1443 AddMove(move, source, destination, nullptr, input->GetType());
1444 }
1445
IsInstructionStart(size_t position)1446 static bool IsInstructionStart(size_t position) {
1447 return (position & 1) == 0;
1448 }
1449
IsInstructionEnd(size_t position)1450 static bool IsInstructionEnd(size_t position) {
1451 return (position & 1) == 1;
1452 }
1453
InsertParallelMoveAt(size_t position,HInstruction * instruction,Location source,Location destination) const1454 void RegisterAllocator::InsertParallelMoveAt(size_t position,
1455 HInstruction* instruction,
1456 Location source,
1457 Location destination) const {
1458 DCHECK(IsValidDestination(destination)) << destination;
1459 if (source.Equals(destination)) return;
1460
1461 HInstruction* at = liveness_.GetInstructionFromPosition(position / 2);
1462 HParallelMove* move;
1463 if (at == nullptr) {
1464 if (IsInstructionStart(position)) {
1465 // Block boundary, don't do anything the connection of split siblings will handle it.
1466 return;
1467 } else {
1468 // Move must happen before the first instruction of the block.
1469 at = liveness_.GetInstructionFromPosition((position + 1) / 2);
1470 // Note that parallel moves may have already been inserted, so we explicitly
1471 // ask for the first instruction of the block: `GetInstructionFromPosition` does
1472 // not contain the `HParallelMove` instructions.
1473 at = at->GetBlock()->GetFirstInstruction();
1474
1475 if (at->GetLifetimePosition() < position) {
1476 // We may insert moves for split siblings and phi spills at the beginning of the block.
1477 // Since this is a different lifetime position, we need to go to the next instruction.
1478 DCHECK(at->IsParallelMove());
1479 at = at->GetNext();
1480 }
1481
1482 if (at->GetLifetimePosition() != position) {
1483 DCHECK_GT(at->GetLifetimePosition(), position);
1484 move = new (allocator_) HParallelMove(allocator_);
1485 move->SetLifetimePosition(position);
1486 at->GetBlock()->InsertInstructionBefore(move, at);
1487 } else {
1488 DCHECK(at->IsParallelMove());
1489 move = at->AsParallelMove();
1490 }
1491 }
1492 } else if (IsInstructionEnd(position)) {
1493 // Move must happen after the instruction.
1494 DCHECK(!at->IsControlFlow());
1495 move = at->GetNext()->AsParallelMove();
1496 // This is a parallel move for connecting siblings in a same block. We need to
1497 // differentiate it with moves for connecting blocks, and input moves.
1498 if (move == nullptr || move->GetLifetimePosition() > position) {
1499 move = new (allocator_) HParallelMove(allocator_);
1500 move->SetLifetimePosition(position);
1501 at->GetBlock()->InsertInstructionBefore(move, at->GetNext());
1502 }
1503 } else {
1504 // Move must happen before the instruction.
1505 HInstruction* previous = at->GetPrevious();
1506 if (previous == nullptr
1507 || !previous->IsParallelMove()
1508 || previous->GetLifetimePosition() != position) {
1509 // If the previous is a parallel move, then its position must be lower
1510 // than the given `position`: it was added just after the non-parallel
1511 // move instruction that precedes `instruction`.
1512 DCHECK(previous == nullptr
1513 || !previous->IsParallelMove()
1514 || previous->GetLifetimePosition() < position);
1515 move = new (allocator_) HParallelMove(allocator_);
1516 move->SetLifetimePosition(position);
1517 at->GetBlock()->InsertInstructionBefore(move, at);
1518 } else {
1519 move = previous->AsParallelMove();
1520 }
1521 }
1522 DCHECK_EQ(move->GetLifetimePosition(), position);
1523 AddMove(move, source, destination, instruction, instruction->GetType());
1524 }
1525
InsertParallelMoveAtExitOf(HBasicBlock * block,HInstruction * instruction,Location source,Location destination) const1526 void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block,
1527 HInstruction* instruction,
1528 Location source,
1529 Location destination) const {
1530 DCHECK(IsValidDestination(destination)) << destination;
1531 if (source.Equals(destination)) return;
1532
1533 DCHECK_EQ(block->GetNormalSuccessors().size(), 1u);
1534 HInstruction* last = block->GetLastInstruction();
1535 // We insert moves at exit for phi predecessors and connecting blocks.
1536 // A block ending with an if or a packed switch cannot branch to a block
1537 // with phis because we do not allow critical edges. It can also not connect
1538 // a split interval between two blocks: the move has to happen in the successor.
1539 DCHECK(!last->IsIf() && !last->IsPackedSwitch());
1540 HInstruction* previous = last->GetPrevious();
1541 HParallelMove* move;
1542 // This is a parallel move for connecting blocks. We need to differentiate
1543 // it with moves for connecting siblings in a same block, and output moves.
1544 size_t position = last->GetLifetimePosition();
1545 if (previous == nullptr || !previous->IsParallelMove()
1546 || previous->AsParallelMove()->GetLifetimePosition() != position) {
1547 move = new (allocator_) HParallelMove(allocator_);
1548 move->SetLifetimePosition(position);
1549 block->InsertInstructionBefore(move, last);
1550 } else {
1551 move = previous->AsParallelMove();
1552 }
1553 AddMove(move, source, destination, instruction, instruction->GetType());
1554 }
1555
InsertParallelMoveAtEntryOf(HBasicBlock * block,HInstruction * instruction,Location source,Location destination) const1556 void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block,
1557 HInstruction* instruction,
1558 Location source,
1559 Location destination) const {
1560 DCHECK(IsValidDestination(destination)) << destination;
1561 if (source.Equals(destination)) return;
1562
1563 HInstruction* first = block->GetFirstInstruction();
1564 HParallelMove* move = first->AsParallelMove();
1565 size_t position = block->GetLifetimeStart();
1566 // This is a parallel move for connecting blocks. We need to differentiate
1567 // it with moves for connecting siblings in a same block, and input moves.
1568 if (move == nullptr || move->GetLifetimePosition() != position) {
1569 move = new (allocator_) HParallelMove(allocator_);
1570 move->SetLifetimePosition(position);
1571 block->InsertInstructionBefore(move, first);
1572 }
1573 AddMove(move, source, destination, instruction, instruction->GetType());
1574 }
1575
InsertMoveAfter(HInstruction * instruction,Location source,Location destination) const1576 void RegisterAllocator::InsertMoveAfter(HInstruction* instruction,
1577 Location source,
1578 Location destination) const {
1579 DCHECK(IsValidDestination(destination)) << destination;
1580 if (source.Equals(destination)) return;
1581
1582 if (instruction->IsPhi()) {
1583 InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination);
1584 return;
1585 }
1586
1587 size_t position = instruction->GetLifetimePosition() + 1;
1588 HParallelMove* move = instruction->GetNext()->AsParallelMove();
1589 // This is a parallel move for moving the output of an instruction. We need
1590 // to differentiate with input moves, moves for connecting siblings in a
1591 // and moves for connecting blocks.
1592 if (move == nullptr || move->GetLifetimePosition() != position) {
1593 move = new (allocator_) HParallelMove(allocator_);
1594 move->SetLifetimePosition(position);
1595 instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext());
1596 }
1597 AddMove(move, source, destination, instruction, instruction->GetType());
1598 }
1599
ConnectSiblings(LiveInterval * interval)1600 void RegisterAllocator::ConnectSiblings(LiveInterval* interval) {
1601 LiveInterval* current = interval;
1602 if (current->HasSpillSlot()
1603 && current->HasRegister()
1604 // Currently, we spill unconditionnally the current method in the code generators.
1605 && !interval->GetDefinedBy()->IsCurrentMethod()) {
1606 // We spill eagerly, so move must be at definition.
1607 InsertMoveAfter(interval->GetDefinedBy(),
1608 interval->ToLocation(),
1609 interval->NeedsTwoSpillSlots()
1610 ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot())
1611 : Location::StackSlot(interval->GetParent()->GetSpillSlot()));
1612 }
1613 UsePosition* use = current->GetFirstUse();
1614 UsePosition* env_use = current->GetFirstEnvironmentUse();
1615
1616 // Walk over all siblings, updating locations of use positions, and
1617 // connecting them when they are adjacent.
1618 do {
1619 Location source = current->ToLocation();
1620
1621 // Walk over all uses covered by this interval, and update the location
1622 // information.
1623
1624 LiveRange* range = current->GetFirstRange();
1625 while (range != nullptr) {
1626 while (use != nullptr && use->GetPosition() < range->GetStart()) {
1627 DCHECK(use->IsSynthesized());
1628 use = use->GetNext();
1629 }
1630 while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
1631 DCHECK(!use->GetIsEnvironment());
1632 DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
1633 if (!use->IsSynthesized()) {
1634 LocationSummary* locations = use->GetUser()->GetLocations();
1635 Location expected_location = locations->InAt(use->GetInputIndex());
1636 // The expected (actual) location may be invalid in case the input is unused. Currently
1637 // this only happens for intrinsics.
1638 if (expected_location.IsValid()) {
1639 if (expected_location.IsUnallocated()) {
1640 locations->SetInAt(use->GetInputIndex(), source);
1641 } else if (!expected_location.IsConstant()) {
1642 AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
1643 }
1644 } else {
1645 DCHECK(use->GetUser()->IsInvoke());
1646 DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
1647 }
1648 }
1649 use = use->GetNext();
1650 }
1651
1652 // Walk over the environment uses, and update their locations.
1653 while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) {
1654 env_use = env_use->GetNext();
1655 }
1656
1657 while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) {
1658 DCHECK(current->CoversSlow(env_use->GetPosition())
1659 || (env_use->GetPosition() == range->GetEnd()));
1660 HEnvironment* environment = env_use->GetEnvironment();
1661 environment->SetLocationAt(env_use->GetInputIndex(), source);
1662 env_use = env_use->GetNext();
1663 }
1664
1665 range = range->GetNext();
1666 }
1667
1668 // If the next interval starts just after this one, and has a register,
1669 // insert a move.
1670 LiveInterval* next_sibling = current->GetNextSibling();
1671 if (next_sibling != nullptr
1672 && next_sibling->HasRegister()
1673 && current->GetEnd() == next_sibling->GetStart()) {
1674 Location destination = next_sibling->ToLocation();
1675 InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
1676 }
1677
1678 for (SafepointPosition* safepoint_position = current->GetFirstSafepoint();
1679 safepoint_position != nullptr;
1680 safepoint_position = safepoint_position->GetNext()) {
1681 DCHECK(current->CoversSlow(safepoint_position->GetPosition()));
1682
1683 LocationSummary* locations = safepoint_position->GetLocations();
1684 if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) {
1685 DCHECK(interval->GetDefinedBy()->IsActualObject())
1686 << interval->GetDefinedBy()->DebugName()
1687 << "@" << safepoint_position->GetInstruction()->DebugName();
1688 locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize);
1689 }
1690
1691 switch (source.GetKind()) {
1692 case Location::kRegister: {
1693 locations->AddLiveRegister(source);
1694 if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) {
1695 DCHECK_LE(locations->GetNumberOfLiveRegisters(),
1696 maximum_number_of_live_core_registers_ +
1697 maximum_number_of_live_fp_registers_);
1698 }
1699 if (current->GetType() == Primitive::kPrimNot) {
1700 DCHECK(interval->GetDefinedBy()->IsActualObject())
1701 << interval->GetDefinedBy()->DebugName()
1702 << "@" << safepoint_position->GetInstruction()->DebugName();
1703 locations->SetRegisterBit(source.reg());
1704 }
1705 break;
1706 }
1707 case Location::kFpuRegister: {
1708 locations->AddLiveRegister(source);
1709 break;
1710 }
1711
1712 case Location::kRegisterPair:
1713 case Location::kFpuRegisterPair: {
1714 locations->AddLiveRegister(source.ToLow());
1715 locations->AddLiveRegister(source.ToHigh());
1716 break;
1717 }
1718 case Location::kStackSlot: // Fall-through
1719 case Location::kDoubleStackSlot: // Fall-through
1720 case Location::kConstant: {
1721 // Nothing to do.
1722 break;
1723 }
1724 default: {
1725 LOG(FATAL) << "Unexpected location for object";
1726 }
1727 }
1728 }
1729 current = next_sibling;
1730 } while (current != nullptr);
1731
1732 if (kIsDebugBuild) {
1733 // Following uses can only be synthesized uses.
1734 while (use != nullptr) {
1735 DCHECK(use->IsSynthesized());
1736 use = use->GetNext();
1737 }
1738 }
1739 }
1740
IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(HInstruction * instruction)1741 static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(
1742 HInstruction* instruction) {
1743 return instruction->GetBlock()->GetGraph()->HasIrreducibleLoops() &&
1744 (instruction->IsConstant() || instruction->IsCurrentMethod());
1745 }
1746
ConnectSplitSiblings(LiveInterval * interval,HBasicBlock * from,HBasicBlock * to) const1747 void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
1748 HBasicBlock* from,
1749 HBasicBlock* to) const {
1750 if (interval->GetNextSibling() == nullptr) {
1751 // Nothing to connect. The whole range was allocated to the same location.
1752 return;
1753 }
1754
1755 // Find the intervals that cover `from` and `to`.
1756 size_t destination_position = to->GetLifetimeStart();
1757 size_t source_position = from->GetLifetimeEnd() - 1;
1758 LiveInterval* destination = interval->GetSiblingAt(destination_position);
1759 LiveInterval* source = interval->GetSiblingAt(source_position);
1760
1761 if (destination == source) {
1762 // Interval was not split.
1763 return;
1764 }
1765
1766 LiveInterval* parent = interval->GetParent();
1767 HInstruction* defined_by = parent->GetDefinedBy();
1768 if (codegen_->GetGraph()->HasIrreducibleLoops() &&
1769 (destination == nullptr || !destination->CoversSlow(destination_position))) {
1770 // Our live_in fixed point calculation has found that the instruction is live
1771 // in the `to` block because it will eventually enter an irreducible loop. Our
1772 // live interval computation however does not compute a fixed point, and
1773 // therefore will not have a location for that instruction for `to`.
1774 // Because the instruction is a constant or the ArtMethod, we don't need to
1775 // do anything: it will be materialized in the irreducible loop.
1776 DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
1777 << defined_by->DebugName() << ":" << defined_by->GetId()
1778 << " " << from->GetBlockId() << " -> " << to->GetBlockId();
1779 return;
1780 }
1781
1782 if (!destination->HasRegister()) {
1783 // Values are eagerly spilled. Spill slot already contains appropriate value.
1784 return;
1785 }
1786
1787 Location location_source;
1788 // `GetSiblingAt` returns the interval whose start and end cover `position`,
1789 // but does not check whether the interval is inactive at that position.
1790 // The only situation where the interval is inactive at that position is in the
1791 // presence of irreducible loops for constants and ArtMethod.
1792 if (codegen_->GetGraph()->HasIrreducibleLoops() &&
1793 (source == nullptr || !source->CoversSlow(source_position))) {
1794 DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
1795 if (defined_by->IsConstant()) {
1796 location_source = defined_by->GetLocations()->Out();
1797 } else {
1798 DCHECK(defined_by->IsCurrentMethod());
1799 location_source = parent->NeedsTwoSpillSlots()
1800 ? Location::DoubleStackSlot(parent->GetSpillSlot())
1801 : Location::StackSlot(parent->GetSpillSlot());
1802 }
1803 } else {
1804 DCHECK(source != nullptr);
1805 DCHECK(source->CoversSlow(source_position));
1806 DCHECK(destination->CoversSlow(destination_position));
1807 location_source = source->ToLocation();
1808 }
1809
1810 // If `from` has only one successor, we can put the moves at the exit of it. Otherwise
1811 // we need to put the moves at the entry of `to`.
1812 if (from->GetNormalSuccessors().size() == 1) {
1813 InsertParallelMoveAtExitOf(from,
1814 defined_by,
1815 location_source,
1816 destination->ToLocation());
1817 } else {
1818 DCHECK_EQ(to->GetPredecessors().size(), 1u);
1819 InsertParallelMoveAtEntryOf(to,
1820 defined_by,
1821 location_source,
1822 destination->ToLocation());
1823 }
1824 }
1825
Resolve()1826 void RegisterAllocator::Resolve() {
1827 codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(),
1828 maximum_number_of_live_core_registers_,
1829 maximum_number_of_live_fp_registers_,
1830 reserved_out_slots_,
1831 codegen_->GetGraph()->GetLinearOrder());
1832
1833 // Adjust the Out Location of instructions.
1834 // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration.
1835 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
1836 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
1837 LiveInterval* current = instruction->GetLiveInterval();
1838 LocationSummary* locations = instruction->GetLocations();
1839 Location location = locations->Out();
1840 if (instruction->IsParameterValue()) {
1841 // Now that we know the frame size, adjust the parameter's location.
1842 if (location.IsStackSlot()) {
1843 location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
1844 current->SetSpillSlot(location.GetStackIndex());
1845 locations->UpdateOut(location);
1846 } else if (location.IsDoubleStackSlot()) {
1847 location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
1848 current->SetSpillSlot(location.GetStackIndex());
1849 locations->UpdateOut(location);
1850 } else if (current->HasSpillSlot()) {
1851 current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
1852 }
1853 } else if (instruction->IsCurrentMethod()) {
1854 // The current method is always at offset 0.
1855 DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0));
1856 } else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) {
1857 DCHECK(current->HasSpillSlot());
1858 size_t slot = current->GetSpillSlot()
1859 + GetNumberOfSpillSlots()
1860 + reserved_out_slots_
1861 - catch_phi_spill_slots_;
1862 current->SetSpillSlot(slot * kVRegSize);
1863 } else if (current->HasSpillSlot()) {
1864 // Adjust the stack slot, now that we know the number of them for each type.
1865 // The way this implementation lays out the stack is the following:
1866 // [parameter slots ]
1867 // [catch phi spill slots ]
1868 // [double spill slots ]
1869 // [long spill slots ]
1870 // [float spill slots ]
1871 // [int/ref values ]
1872 // [maximum out values ] (number of arguments for calls)
1873 // [art method ].
1874 size_t slot = current->GetSpillSlot();
1875 switch (current->GetType()) {
1876 case Primitive::kPrimDouble:
1877 slot += long_spill_slots_.size();
1878 FALLTHROUGH_INTENDED;
1879 case Primitive::kPrimLong:
1880 slot += float_spill_slots_.size();
1881 FALLTHROUGH_INTENDED;
1882 case Primitive::kPrimFloat:
1883 slot += int_spill_slots_.size();
1884 FALLTHROUGH_INTENDED;
1885 case Primitive::kPrimNot:
1886 case Primitive::kPrimInt:
1887 case Primitive::kPrimChar:
1888 case Primitive::kPrimByte:
1889 case Primitive::kPrimBoolean:
1890 case Primitive::kPrimShort:
1891 slot += reserved_out_slots_;
1892 break;
1893 case Primitive::kPrimVoid:
1894 LOG(FATAL) << "Unexpected type for interval " << current->GetType();
1895 }
1896 current->SetSpillSlot(slot * kVRegSize);
1897 }
1898
1899 Location source = current->ToLocation();
1900
1901 if (location.IsUnallocated()) {
1902 if (location.GetPolicy() == Location::kSameAsFirstInput) {
1903 if (locations->InAt(0).IsUnallocated()) {
1904 locations->SetInAt(0, source);
1905 } else {
1906 DCHECK(locations->InAt(0).Equals(source));
1907 }
1908 }
1909 locations->UpdateOut(source);
1910 } else {
1911 DCHECK(source.Equals(location));
1912 }
1913 }
1914
1915 // Connect siblings.
1916 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
1917 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
1918 ConnectSiblings(instruction->GetLiveInterval());
1919 }
1920
1921 // Resolve non-linear control flow across branches. Order does not matter.
1922 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
1923 HBasicBlock* block = it.Current();
1924 if (block->IsCatchBlock() ||
1925 (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) {
1926 // Instructions live at the top of catch blocks or irreducible loop header
1927 // were forced to spill.
1928 if (kIsDebugBuild) {
1929 BitVector* live = liveness_.GetLiveInSet(*block);
1930 for (uint32_t idx : live->Indexes()) {
1931 LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
1932 LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
1933 // `GetSiblingAt` returns the sibling that contains a position, but there could be
1934 // a lifetime hole in it. `CoversSlow` returns whether the interval is live at that
1935 // position.
1936 if ((sibling != nullptr) && sibling->CoversSlow(block->GetLifetimeStart())) {
1937 DCHECK(!sibling->HasRegister());
1938 }
1939 }
1940 }
1941 } else {
1942 BitVector* live = liveness_.GetLiveInSet(*block);
1943 for (uint32_t idx : live->Indexes()) {
1944 LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
1945 for (HBasicBlock* predecessor : block->GetPredecessors()) {
1946 ConnectSplitSiblings(interval, predecessor, block);
1947 }
1948 }
1949 }
1950 }
1951
1952 // Resolve phi inputs. Order does not matter.
1953 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) {
1954 HBasicBlock* current = it.Current();
1955 if (current->IsCatchBlock()) {
1956 // Catch phi values are set at runtime by the exception delivery mechanism.
1957 } else {
1958 for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
1959 HInstruction* phi = inst_it.Current();
1960 for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) {
1961 HBasicBlock* predecessor = current->GetPredecessors()[i];
1962 DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u);
1963 HInstruction* input = phi->InputAt(i);
1964 Location source = input->GetLiveInterval()->GetLocationAt(
1965 predecessor->GetLifetimeEnd() - 1);
1966 Location destination = phi->GetLiveInterval()->ToLocation();
1967 InsertParallelMoveAtExitOf(predecessor, phi, source, destination);
1968 }
1969 }
1970 }
1971 }
1972
1973 // Assign temp locations.
1974 for (LiveInterval* temp : temp_intervals_) {
1975 if (temp->IsHighInterval()) {
1976 // High intervals can be skipped, they are already handled by the low interval.
1977 continue;
1978 }
1979 HInstruction* at = liveness_.GetTempUser(temp);
1980 size_t temp_index = liveness_.GetTempIndex(temp);
1981 LocationSummary* locations = at->GetLocations();
1982 switch (temp->GetType()) {
1983 case Primitive::kPrimInt:
1984 locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister()));
1985 break;
1986
1987 case Primitive::kPrimDouble:
1988 if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) {
1989 Location location = Location::FpuRegisterPairLocation(
1990 temp->GetRegister(), temp->GetHighInterval()->GetRegister());
1991 locations->SetTempAt(temp_index, location);
1992 } else {
1993 locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister()));
1994 }
1995 break;
1996
1997 default:
1998 LOG(FATAL) << "Unexpected type for temporary location "
1999 << temp->GetType();
2000 }
2001 }
2002 }
2003
2004 } // namespace art
2005