/*
* Copyright (C) 2016 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "register_allocation_resolver.h"
#include "base/bit_vector-inl.h"
#include "code_generator.h"
#include "linear_order.h"
#include "ssa_liveness_analysis.h"
namespace art {
RegisterAllocationResolver::RegisterAllocationResolver(CodeGenerator* codegen,
const SsaLivenessAnalysis& liveness)
: allocator_(codegen->GetGraph()->GetAllocator()),
codegen_(codegen),
liveness_(liveness) {}
void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoints,
size_t reserved_out_slots,
size_t int_spill_slots,
size_t long_spill_slots,
size_t float_spill_slots,
size_t double_spill_slots,
size_t catch_phi_spill_slots,
ArrayRef<LiveInterval* const> temp_intervals) {
size_t spill_slots = int_spill_slots
+ long_spill_slots
+ float_spill_slots
+ double_spill_slots
+ catch_phi_spill_slots;
// Update safepoints and calculate the size of the spills.
UpdateSafepointLiveRegisters();
size_t maximum_safepoint_spill_size = CalculateMaximumSafepointSpillSize(safepoints);
// Computes frame size and spill mask.
codegen_->InitializeCodeGeneration(spill_slots,
maximum_safepoint_spill_size,
reserved_out_slots, // Includes slot(s) for the art method.
codegen_->GetGraph()->GetLinearOrder());
// Resolve outputs, including stack locations.
// TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration.
for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
LiveInterval* current = instruction->GetLiveInterval();
LocationSummary* locations = instruction->GetLocations();
Location location = locations->Out();
if (instruction->IsParameterValue()) {
// Now that we know the frame size, adjust the parameter's location.
if (location.IsStackSlot()) {
location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
current->SetSpillSlot(location.GetStackIndex());
locations->UpdateOut(location);
} else if (location.IsDoubleStackSlot()) {
location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize());
current->SetSpillSlot(location.GetStackIndex());
locations->UpdateOut(location);
} else if (current->HasSpillSlot()) {
current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize());
}
} else if (instruction->IsCurrentMethod()) {
// The current method is always at offset 0.
DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0));
} else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) {
DCHECK(current->HasSpillSlot());
size_t slot = current->GetSpillSlot()
+ spill_slots
+ reserved_out_slots
- catch_phi_spill_slots;
current->SetSpillSlot(slot * kVRegSize);
} else if (current->HasSpillSlot()) {
// Adjust the stack slot, now that we know the number of them for each type.
// The way this implementation lays out the stack is the following:
// [parameter slots ]
// [art method (caller) ]
// [entry spill (core) ]
// [entry spill (float) ]
// [should_deoptimize flag] (this is optional)
// [catch phi spill slots ]
// [double spill slots ]
// [long spill slots ]
// [float spill slots ]
// [int/ref values ]
// [maximum out values ] (number of arguments for calls)
// [art method ].
size_t slot = current->GetSpillSlot();
switch (current->GetType()) {
case DataType::Type::kFloat64:
slot += long_spill_slots;
FALLTHROUGH_INTENDED;
case DataType::Type::kUint64:
case DataType::Type::kInt64:
slot += float_spill_slots;
FALLTHROUGH_INTENDED;
case DataType::Type::kFloat32:
slot += int_spill_slots;
FALLTHROUGH_INTENDED;
case DataType::Type::kReference:
case DataType::Type::kUint32:
case DataType::Type::kInt32:
case DataType::Type::kUint16:
case DataType::Type::kUint8:
case DataType::Type::kInt8:
case DataType::Type::kBool:
case DataType::Type::kInt16:
slot += reserved_out_slots;
break;
case DataType::Type::kVoid:
LOG(FATAL) << "Unexpected type for interval " << current->GetType();
}
current->SetSpillSlot(slot * kVRegSize);
}
Location source = current->ToLocation();
if (location.IsUnallocated()) {
if (location.GetPolicy() == Location::kSameAsFirstInput) {
if (locations->InAt(0).IsUnallocated()) {
locations->SetInAt(0, source);
} else {
DCHECK(locations->InAt(0).Equals(source));
}
}
locations->UpdateOut(source);
} else {
DCHECK(source.Equals(location));
}
}
// Connect siblings and resolve inputs.
for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
ConnectSiblings(instruction->GetLiveInterval());
}
// Resolve non-linear control flow across branches. Order does not matter.
for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) {
if (block->IsCatchBlock() ||
(block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) {
// Instructions live at the top of catch blocks or irreducible loop header
// were forced to spill.
if (kIsDebugBuild) {
BitVector* live = liveness_.GetLiveInSet(*block);
for (uint32_t idx : live->Indexes()) {
LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
// `GetSiblingAt` returns the sibling that contains a position, but there could be
// a lifetime hole in it. `CoversSlow` returns whether the interval is live at that
// position.
if ((sibling != nullptr) && sibling->CoversSlow(block->GetLifetimeStart())) {
DCHECK(!sibling->HasRegister());
}
}
}
} else {
BitVector* live = liveness_.GetLiveInSet(*block);
for (uint32_t idx : live->Indexes()) {
LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
for (HBasicBlock* predecessor : block->GetPredecessors()) {
ConnectSplitSiblings(interval, predecessor, block);
}
}
}
}
// Resolve phi inputs. Order does not matter.
for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) {
if (block->IsCatchBlock()) {
// Catch phi values are set at runtime by the exception delivery mechanism.
} else {
for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
HInstruction* phi = inst_it.Current();
for (size_t i = 0, e = block->GetPredecessors().size(); i < e; ++i) {
HBasicBlock* predecessor = block->GetPredecessors()[i];
DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u);
HInstruction* input = phi->InputAt(i);
Location source = input->GetLiveInterval()->GetLocationAt(
predecessor->GetLifetimeEnd() - 1);
Location destination = phi->GetLiveInterval()->ToLocation();
InsertParallelMoveAtExitOf(predecessor, phi, source, destination);
}
}
}
}
// Resolve temp locations.
for (LiveInterval* temp : temp_intervals) {
if (temp->IsHighInterval()) {
// High intervals can be skipped, they are already handled by the low interval.
continue;
}
HInstruction* at = liveness_.GetTempUser(temp);
size_t temp_index = liveness_.GetTempIndex(temp);
LocationSummary* locations = at->GetLocations();
switch (temp->GetType()) {
case DataType::Type::kInt32:
locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister()));
break;
case DataType::Type::kFloat64:
if (codegen_->NeedsTwoRegisters(DataType::Type::kFloat64)) {
Location location = Location::FpuRegisterPairLocation(
temp->GetRegister(), temp->GetHighInterval()->GetRegister());
locations->SetTempAt(temp_index, location);
} else {
locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister()));
}
break;
default:
LOG(FATAL) << "Unexpected type for temporary location "
<< temp->GetType();
}
}
}
void RegisterAllocationResolver::UpdateSafepointLiveRegisters() {
for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) {
HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i);
for (LiveInterval* current = instruction->GetLiveInterval();
current != nullptr;
current = current->GetNextSibling()) {
if (!current->HasRegister()) {
continue;
}
Location source = current->ToLocation();
for (SafepointPosition* safepoint_position = current->GetFirstSafepoint();
safepoint_position != nullptr;
safepoint_position = safepoint_position->GetNext()) {
DCHECK(current->CoversSlow(safepoint_position->GetPosition()));
LocationSummary* locations = safepoint_position->GetLocations();
switch (source.GetKind()) {
case Location::kRegister:
case Location::kFpuRegister: {
locations->AddLiveRegister(source);
break;
}
case Location::kRegisterPair:
case Location::kFpuRegisterPair: {
locations->AddLiveRegister(source.ToLow());
locations->AddLiveRegister(source.ToHigh());
break;
}
case Location::kStackSlot: // Fall-through
case Location::kDoubleStackSlot: // Fall-through
case Location::kConstant: {
// Nothing to do.
break;
}
default: {
LOG(FATAL) << "Unexpected location for object";
}
}
}
}
}
}
size_t RegisterAllocationResolver::CalculateMaximumSafepointSpillSize(
ArrayRef<HInstruction* const> safepoints) {
size_t core_register_spill_size = codegen_->GetWordSize();
size_t fp_register_spill_size = codegen_->GetFloatingPointSpillSlotSize();
size_t maximum_safepoint_spill_size = 0u;
for (HInstruction* instruction : safepoints) {
LocationSummary* locations = instruction->GetLocations();
if (locations->OnlyCallsOnSlowPath()) {
size_t core_spills =
codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ true);
size_t fp_spills =
codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ false);
size_t spill_size =
core_register_spill_size * core_spills + fp_register_spill_size * fp_spills;
maximum_safepoint_spill_size = std::max(maximum_safepoint_spill_size, spill_size);
} else if (locations->CallsOnMainAndSlowPath()) {
// Nothing to spill on the slow path if the main path already clobbers caller-saves.
DCHECK_EQ(0u, codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ true));
DCHECK_EQ(0u, codegen_->GetNumberOfSlowPathSpills(locations, /* core_registers */ false));
}
}
return maximum_safepoint_spill_size;
}
void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
LiveInterval* current = interval;
if (current->HasSpillSlot()
&& current->HasRegister()
// Currently, we spill unconditionnally the current method in the code generators.
&& !interval->GetDefinedBy()->IsCurrentMethod()) {
// We spill eagerly, so move must be at definition.
Location loc;
switch (interval->NumberOfSpillSlotsNeeded()) {
case 1: loc = Location::StackSlot(interval->GetParent()->GetSpillSlot()); break;
case 2: loc = Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()); break;
case 4: loc = Location::SIMDStackSlot(interval->GetParent()->GetSpillSlot()); break;
default: LOG(FATAL) << "Unexpected number of spill slots"; UNREACHABLE();
}
InsertMoveAfter(interval->GetDefinedBy(), interval->ToLocation(), loc);
}
UsePositionList::const_iterator use_it = current->GetUses().begin();
const UsePositionList::const_iterator use_end = current->GetUses().end();
EnvUsePositionList::const_iterator env_use_it = current->GetEnvironmentUses().begin();
const EnvUsePositionList::const_iterator env_use_end = current->GetEnvironmentUses().end();
// Walk over all siblings, updating locations of use positions, and
// connecting them when they are adjacent.
do {
Location source = current->ToLocation();
// Walk over all uses covered by this interval, and update the location
// information.
LiveRange* range = current->GetFirstRange();
while (range != nullptr) {
// Process uses in the closed interval [range->GetStart(), range->GetEnd()].
// FindMatchingUseRange() expects a half-open interval, so pass `range->GetEnd() + 1u`.
size_t range_begin = range->GetStart();
size_t range_end = range->GetEnd() + 1u;
auto matching_use_range =
FindMatchingUseRange(use_it, use_end, range_begin, range_end);
DCHECK(std::all_of(use_it,
matching_use_range.begin(),
[](const UsePosition& pos) { return pos.IsSynthesized(); }));
for (const UsePosition& use : matching_use_range) {
DCHECK(current->CoversSlow(use.GetPosition()) || (use.GetPosition() == range->GetEnd()));
if (!use.IsSynthesized()) {
LocationSummary* locations = use.GetUser()->GetLocations();
Location expected_location = locations->InAt(use.GetInputIndex());
// The expected (actual) location may be invalid in case the input is unused. Currently
// this only happens for intrinsics.
if (expected_location.IsValid()) {
if (expected_location.IsUnallocated()) {
locations->SetInAt(use.GetInputIndex(), source);
} else if (!expected_location.IsConstant()) {
AddInputMoveFor(
interval->GetDefinedBy(), use.GetUser(), source, expected_location);
}
} else {
DCHECK(use.GetUser()->IsInvoke());
DCHECK(use.GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
}
}
}
use_it = matching_use_range.end();
// Walk over the environment uses, and update their locations.
auto matching_env_use_range =
FindMatchingUseRange(env_use_it, env_use_end, range_begin, range_end);
for (const EnvUsePosition& env_use : matching_env_use_range) {
DCHECK(current->CoversSlow(env_use.GetPosition())
|| (env_use.GetPosition() == range->GetEnd()));
HEnvironment* environment = env_use.GetEnvironment();
environment->SetLocationAt(env_use.GetInputIndex(), source);
}
env_use_it = matching_env_use_range.end();
range = range->GetNext();
}
// If the next interval starts just after this one, and has a register,
// insert a move.
LiveInterval* next_sibling = current->GetNextSibling();
if (next_sibling != nullptr
&& next_sibling->HasRegister()
&& current->GetEnd() == next_sibling->GetStart()) {
Location destination = next_sibling->ToLocation();
InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination);
}
for (SafepointPosition* safepoint_position = current->GetFirstSafepoint();
safepoint_position != nullptr;
safepoint_position = safepoint_position->GetNext()) {
DCHECK(current->CoversSlow(safepoint_position->GetPosition()));
if (current->GetType() == DataType::Type::kReference) {
DCHECK(interval->GetDefinedBy()->IsActualObject())
<< interval->GetDefinedBy()->DebugName()
<< '(' << interval->GetDefinedBy()->GetId() << ')'
<< "@" << safepoint_position->GetInstruction()->DebugName()
<< '(' << safepoint_position->GetInstruction()->GetId() << ')';
LocationSummary* locations = safepoint_position->GetLocations();
if (current->GetParent()->HasSpillSlot()) {
locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize);
}
if (source.GetKind() == Location::kRegister) {
locations->SetRegisterBit(source.reg());
}
}
}
current = next_sibling;
} while (current != nullptr);
// Following uses can only be synthesized uses.
DCHECK(std::all_of(use_it, use_end, [](const UsePosition& pos) { return pos.IsSynthesized(); }));
}
static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(
HInstruction* instruction) {
return instruction->GetBlock()->GetGraph()->HasIrreducibleLoops() &&
(instruction->IsConstant() || instruction->IsCurrentMethod());
}
void RegisterAllocationResolver::ConnectSplitSiblings(LiveInterval* interval,
HBasicBlock* from,
HBasicBlock* to) const {
if (interval->GetNextSibling() == nullptr) {
// Nothing to connect. The whole range was allocated to the same location.
return;
}
// Find the intervals that cover `from` and `to`.
size_t destination_position = to->GetLifetimeStart();
size_t source_position = from->GetLifetimeEnd() - 1;
LiveInterval* destination = interval->GetSiblingAt(destination_position);
LiveInterval* source = interval->GetSiblingAt(source_position);
if (destination == source) {
// Interval was not split.
return;
}
LiveInterval* parent = interval->GetParent();
HInstruction* defined_by = parent->GetDefinedBy();
if (codegen_->GetGraph()->HasIrreducibleLoops() &&
(destination == nullptr || !destination->CoversSlow(destination_position))) {
// Our live_in fixed point calculation has found that the instruction is live
// in the `to` block because it will eventually enter an irreducible loop. Our
// live interval computation however does not compute a fixed point, and
// therefore will not have a location for that instruction for `to`.
// Because the instruction is a constant or the ArtMethod, we don't need to
// do anything: it will be materialized in the irreducible loop.
DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by))
<< defined_by->DebugName() << ":" << defined_by->GetId()
<< " " << from->GetBlockId() << " -> " << to->GetBlockId();
return;
}
if (!destination->HasRegister()) {
// Values are eagerly spilled. Spill slot already contains appropriate value.
return;
}
Location location_source;
// `GetSiblingAt` returns the interval whose start and end cover `position`,
// but does not check whether the interval is inactive at that position.
// The only situation where the interval is inactive at that position is in the
// presence of irreducible loops for constants and ArtMethod.
if (codegen_->GetGraph()->HasIrreducibleLoops() &&
(source == nullptr || !source->CoversSlow(source_position))) {
DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by));
if (defined_by->IsConstant()) {
location_source = defined_by->GetLocations()->Out();
} else {
DCHECK(defined_by->IsCurrentMethod());
switch (parent->NumberOfSpillSlotsNeeded()) {
case 1: location_source = Location::StackSlot(parent->GetSpillSlot()); break;
case 2: location_source = Location::DoubleStackSlot(parent->GetSpillSlot()); break;
case 4: location_source = Location::SIMDStackSlot(parent->GetSpillSlot()); break;
default: LOG(FATAL) << "Unexpected number of spill slots"; UNREACHABLE();
}
}
} else {
DCHECK(source != nullptr);
DCHECK(source->CoversSlow(source_position));
DCHECK(destination->CoversSlow(destination_position));
location_source = source->ToLocation();
}
// If `from` has only one successor, we can put the moves at the exit of it. Otherwise
// we need to put the moves at the entry of `to`.
if (from->GetNormalSuccessors().size() == 1) {
InsertParallelMoveAtExitOf(from,
defined_by,
location_source,
destination->ToLocation());
} else {
DCHECK_EQ(to->GetPredecessors().size(), 1u);
InsertParallelMoveAtEntryOf(to,
defined_by,
location_source,
destination->ToLocation());
}
}
static bool IsValidDestination(Location destination) {
return destination.IsRegister()
|| destination.IsRegisterPair()
|| destination.IsFpuRegister()
|| destination.IsFpuRegisterPair()
|| destination.IsStackSlot()
|| destination.IsDoubleStackSlot()
|| destination.IsSIMDStackSlot();
}
void RegisterAllocationResolver::AddMove(HParallelMove* move,
Location source,
Location destination,
HInstruction* instruction,
DataType::Type type) const {
if (type == DataType::Type::kInt64
&& codegen_->ShouldSplitLongMoves()
// The parallel move resolver knows how to deal with long constants.
&& !source.IsConstant()) {
move->AddMove(source.ToLow(), destination.ToLow(), DataType::Type::kInt32, instruction);
move->AddMove(source.ToHigh(), destination.ToHigh(), DataType::Type::kInt32, nullptr);
} else {
move->AddMove(source, destination, type, instruction);
}
}
void RegisterAllocationResolver::AddInputMoveFor(HInstruction* input,
HInstruction* user,
Location source,
Location destination) const {
if (source.Equals(destination)) return;
DCHECK(!user->IsPhi());
HInstruction* previous = user->GetPrevious();
HParallelMove* move = nullptr;
if (previous == nullptr
|| !previous->IsParallelMove()
|| previous->GetLifetimePosition() < user->GetLifetimePosition()) {
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(user->GetLifetimePosition());
user->GetBlock()->InsertInstructionBefore(move, user);
} else {
move = previous->AsParallelMove();
}
DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition());
AddMove(move, source, destination, nullptr, input->GetType());
}
static bool IsInstructionStart(size_t position) {
return (position & 1) == 0;
}
static bool IsInstructionEnd(size_t position) {
return (position & 1) == 1;
}
void RegisterAllocationResolver::InsertParallelMoveAt(size_t position,
HInstruction* instruction,
Location source,
Location destination) const {
DCHECK(IsValidDestination(destination)) << destination;
if (source.Equals(destination)) return;
HInstruction* at = liveness_.GetInstructionFromPosition(position / 2);
HParallelMove* move;
if (at == nullptr) {
if (IsInstructionStart(position)) {
// Block boundary, don't do anything the connection of split siblings will handle it.
return;
} else {
// Move must happen before the first instruction of the block.
at = liveness_.GetInstructionFromPosition((position + 1) / 2);
// Note that parallel moves may have already been inserted, so we explicitly
// ask for the first instruction of the block: `GetInstructionFromPosition` does
// not contain the `HParallelMove` instructions.
at = at->GetBlock()->GetFirstInstruction();
if (at->GetLifetimePosition() < position) {
// We may insert moves for split siblings and phi spills at the beginning of the block.
// Since this is a different lifetime position, we need to go to the next instruction.
DCHECK(at->IsParallelMove());
at = at->GetNext();
}
if (at->GetLifetimePosition() != position) {
DCHECK_GT(at->GetLifetimePosition(), position);
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
at->GetBlock()->InsertInstructionBefore(move, at);
} else {
DCHECK(at->IsParallelMove());
move = at->AsParallelMove();
}
}
} else if (IsInstructionEnd(position)) {
// Move must happen after the instruction.
DCHECK(!at->IsControlFlow());
move = at->GetNext()->AsParallelMove();
// This is a parallel move for connecting siblings in a same block. We need to
// differentiate it with moves for connecting blocks, and input moves.
if (move == nullptr || move->GetLifetimePosition() > position) {
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
at->GetBlock()->InsertInstructionBefore(move, at->GetNext());
}
} else {
// Move must happen before the instruction.
HInstruction* previous = at->GetPrevious();
if (previous == nullptr
|| !previous->IsParallelMove()
|| previous->GetLifetimePosition() != position) {
// If the previous is a parallel move, then its position must be lower
// than the given `position`: it was added just after the non-parallel
// move instruction that precedes `instruction`.
DCHECK(previous == nullptr
|| !previous->IsParallelMove()
|| previous->GetLifetimePosition() < position);
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
at->GetBlock()->InsertInstructionBefore(move, at);
} else {
move = previous->AsParallelMove();
}
}
DCHECK_EQ(move->GetLifetimePosition(), position);
AddMove(move, source, destination, instruction, instruction->GetType());
}
void RegisterAllocationResolver::InsertParallelMoveAtExitOf(HBasicBlock* block,
HInstruction* instruction,
Location source,
Location destination) const {
DCHECK(IsValidDestination(destination)) << destination;
if (source.Equals(destination)) return;
DCHECK_EQ(block->GetNormalSuccessors().size(), 1u);
HInstruction* last = block->GetLastInstruction();
// We insert moves at exit for phi predecessors and connecting blocks.
// A block ending with an if or a packed switch cannot branch to a block
// with phis because we do not allow critical edges. It can also not connect
// a split interval between two blocks: the move has to happen in the successor.
DCHECK(!last->IsIf() && !last->IsPackedSwitch());
HInstruction* previous = last->GetPrevious();
HParallelMove* move;
// This is a parallel move for connecting blocks. We need to differentiate
// it with moves for connecting siblings in a same block, and output moves.
size_t position = last->GetLifetimePosition();
if (previous == nullptr || !previous->IsParallelMove()
|| previous->AsParallelMove()->GetLifetimePosition() != position) {
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
block->InsertInstructionBefore(move, last);
} else {
move = previous->AsParallelMove();
}
AddMove(move, source, destination, instruction, instruction->GetType());
}
void RegisterAllocationResolver::InsertParallelMoveAtEntryOf(HBasicBlock* block,
HInstruction* instruction,
Location source,
Location destination) const {
DCHECK(IsValidDestination(destination)) << destination;
if (source.Equals(destination)) return;
HInstruction* first = block->GetFirstInstruction();
HParallelMove* move = first->AsParallelMove();
size_t position = block->GetLifetimeStart();
// This is a parallel move for connecting blocks. We need to differentiate
// it with moves for connecting siblings in a same block, and input moves.
if (move == nullptr || move->GetLifetimePosition() != position) {
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
block->InsertInstructionBefore(move, first);
}
AddMove(move, source, destination, instruction, instruction->GetType());
}
void RegisterAllocationResolver::InsertMoveAfter(HInstruction* instruction,
Location source,
Location destination) const {
DCHECK(IsValidDestination(destination)) << destination;
if (source.Equals(destination)) return;
if (instruction->IsPhi()) {
InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination);
return;
}
size_t position = instruction->GetLifetimePosition() + 1;
HParallelMove* move = instruction->GetNext()->AsParallelMove();
// This is a parallel move for moving the output of an instruction. We need
// to differentiate with input moves, moves for connecting siblings in a
// and moves for connecting blocks.
if (move == nullptr || move->GetLifetimePosition() != position) {
move = new (allocator_) HParallelMove(allocator_);
move->SetLifetimePosition(position);
instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext());
}
AddMove(move, source, destination, instruction, instruction->GetType());
}
} // namespace art