in compiler/optimizing/register_allocator.cc [228:416]
void RegisterAllocator::ProcessInstruction(HInstruction* instruction) {
LocationSummary* locations = instruction->GetLocations();
size_t position = instruction->GetLifetimePosition();
if (locations == nullptr) return;
// Create synthesized intervals for temporaries.
for (size_t i = 0; i < locations->GetTempCount(); ++i) {
Location temp = locations->GetTemp(i);
if (temp.IsRegister() || temp.IsFpuRegister()) {
BlockRegister(temp, position, position + 1);
// Ensure that an explicit temporary register is marked as being allocated.
codegen_->AddAllocatedRegister(temp);
} else {
DCHECK(temp.IsUnallocated());
switch (temp.GetPolicy()) {
case Location::kRequiresRegister: {
LiveInterval* interval =
LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt);
temp_intervals_.push_back(interval);
interval->AddTempUse(instruction, i);
unhandled_core_intervals_.push_back(interval);
break;
}
case Location::kRequiresFpuRegister: {
LiveInterval* interval =
LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble);
temp_intervals_.push_back(interval);
interval->AddTempUse(instruction, i);
if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) {
interval->AddHighInterval(/* is_temp */ true);
LiveInterval* high = interval->GetHighInterval();
temp_intervals_.push_back(high);
unhandled_fp_intervals_.push_back(high);
}
unhandled_fp_intervals_.push_back(interval);
break;
}
default:
LOG(FATAL) << "Unexpected policy for temporary location "
<< temp.GetPolicy();
}
}
}
bool core_register = (instruction->GetType() != Primitive::kPrimDouble)
&& (instruction->GetType() != Primitive::kPrimFloat);
if (locations->NeedsSafepoint()) {
if (codegen_->IsLeafMethod()) {
// TODO: We do this here because we do not want the suspend check to artificially
// create live registers. We should find another place, but this is currently the
// simplest.
DCHECK(instruction->IsSuspendCheckEntry());
instruction->GetBlock()->RemoveInstruction(instruction);
return;
}
safepoints_.push_back(instruction);
if (locations->OnlyCallsOnSlowPath()) {
// We add a synthesized range at this position to record the live registers
// at this position. Ideally, we could just update the safepoints when locations
// are updated, but we currently need to know the full stack size before updating
// locations (because of parameters and the fact that we don't have a frame pointer).
// And knowing the full stack size requires to know the maximum number of live
// registers at calls in slow paths.
// By adding the following interval in the algorithm, we can compute this
// maximum before updating locations.
LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction);
interval->AddRange(position, position + 1);
AddSorted(&unhandled_core_intervals_, interval);
AddSorted(&unhandled_fp_intervals_, interval);
}
}
if (locations->WillCall()) {
BlockRegisters(position, position + 1, /* caller_save_only */ true);
}
for (size_t i = 0; i < instruction->InputCount(); ++i) {
Location input = locations->InAt(i);
if (input.IsRegister() || input.IsFpuRegister()) {
BlockRegister(input, position, position + 1);
} else if (input.IsPair()) {
BlockRegister(input.ToLow(), position, position + 1);
BlockRegister(input.ToHigh(), position, position + 1);
}
}
LiveInterval* current = instruction->GetLiveInterval();
if (current == nullptr) return;
ArenaVector<LiveInterval*>& unhandled = core_register
? unhandled_core_intervals_
: unhandled_fp_intervals_;
DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back()));
if (codegen_->NeedsTwoRegisters(current->GetType())) {
current->AddHighInterval();
}
for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) {
HInstruction* safepoint = safepoints_[safepoint_index - 1u];
size_t safepoint_position = safepoint->GetLifetimePosition();
// Test that safepoints are ordered in the optimal way.
DCHECK(safepoint_index == safepoints_.size() ||
safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position);
if (safepoint_position == current->GetStart()) {
// The safepoint is for this instruction, so the location of the instruction
// does not need to be saved.
DCHECK_EQ(safepoint_index, safepoints_.size());
DCHECK_EQ(safepoint, instruction);
continue;
} else if (current->IsDeadAt(safepoint_position)) {
break;
} else if (!current->Covers(safepoint_position)) {
// Hole in the interval.
continue;
}
current->AddSafepoint(safepoint);
}
current->ResetSearchCache();
// Some instructions define their output in fixed register/stack slot. We need
// to ensure we know these locations before doing register allocation. For a
// given register, we create an interval that covers these locations. The register
// will be unavailable at these locations when trying to allocate one for an
// interval.
//
// The backwards walking ensures the ranges are ordered on increasing start positions.
Location output = locations->Out();
if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) {
Location first = locations->InAt(0);
if (first.IsRegister() || first.IsFpuRegister()) {
current->SetFrom(position + 1);
current->SetRegister(first.reg());
} else if (first.IsPair()) {
current->SetFrom(position + 1);
current->SetRegister(first.low());
LiveInterval* high = current->GetHighInterval();
high->SetRegister(first.high());
high->SetFrom(position + 1);
}
} else if (output.IsRegister() || output.IsFpuRegister()) {
// Shift the interval's start by one to account for the blocked register.
current->SetFrom(position + 1);
current->SetRegister(output.reg());
BlockRegister(output, position, position + 1);
} else if (output.IsPair()) {
current->SetFrom(position + 1);
current->SetRegister(output.low());
LiveInterval* high = current->GetHighInterval();
high->SetRegister(output.high());
high->SetFrom(position + 1);
BlockRegister(output.ToLow(), position, position + 1);
BlockRegister(output.ToHigh(), position, position + 1);
} else if (output.IsStackSlot() || output.IsDoubleStackSlot()) {
current->SetSpillSlot(output.GetStackIndex());
} else {
DCHECK(output.IsUnallocated() || output.IsConstant());
}
if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) {
AllocateSpillSlotForCatchPhi(instruction->AsPhi());
}
// If needed, add interval to the list of unhandled intervals.
if (current->HasSpillSlot() || instruction->IsConstant()) {
// Split just before first register use.
size_t first_register_use = current->FirstRegisterUse();
if (first_register_use != kNoLifetime) {
LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1);
// Don't add directly to `unhandled`, it needs to be sorted and the start
// of this new interval might be after intervals already in the list.
AddSorted(&unhandled, split);
} else {
// Nothing to do, we won't allocate a register for this value.
}
} else {
// Don't add directly to `unhandled`, temp or safepoint intervals
// for this instruction may have been added, and those can be
// processed first.
AddSorted(&unhandled, current);
}
}