| /* |
| * 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 HIDDEN { |
| |
| 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_IMPLIES(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_->GetSlowPathFPWidth(); |
| 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; |
| size_t num_of_slots = interval->NumberOfSpillSlotsNeeded(); |
| loc = Location::StackSlotByNumOfSlots(num_of_slots, interval->GetParent()->GetSpillSlot()); |
| |
| CHECK_IMPLIES(loc.IsSIMDStackSlot(), |
| (codegen_->GetSIMDRegisterWidth() / kVRegSize == num_of_slots)) |
| << "Unexpected number of spill slots"; |
| 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()); |
| size_t num_of_slots = parent->NumberOfSpillSlotsNeeded(); |
| location_source = Location::StackSlotByNumOfSlots(num_of_slots, parent->GetSpillSlot()); |
| CHECK_IMPLIES(location_source.IsSIMDStackSlot(), |
| (codegen_->GetSIMDRegisterWidth() == num_of_slots * kVRegSize)) |
| << "Unexpected number of spill slots"; |
| } |
| } 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()->AsParallelMoveOrNull(); |
| // 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->AsParallelMoveOrNull(); |
| 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()->AsParallelMoveOrNull(); |
| // 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 |