| // Copyright 2020 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/compiler/backend/spill-placer.h" |
| |
| #include "src/base/bits-iterator.h" |
| #include "src/compiler/backend/register-allocator.h" |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| SpillPlacer::SpillPlacer(LiveRangeFinder* finder, |
| TopTierRegisterAllocationData* data, Zone* zone) |
| : finder_(finder), data_(data), zone_(zone) {} |
| |
| SpillPlacer::~SpillPlacer() { |
| if (assigned_indices_ > 0) { |
| CommitSpills(); |
| } |
| } |
| |
| void SpillPlacer::Add(TopLevelLiveRange* range) { |
| DCHECK(range->HasGeneralSpillRange()); |
| InstructionOperand spill_operand = range->GetSpillRangeOperand(); |
| range->FilterSpillMoves(data(), spill_operand); |
| |
| InstructionSequence* code = data_->code(); |
| InstructionBlock* top_start_block = |
| code->GetInstructionBlock(range->Start().ToInstructionIndex()); |
| RpoNumber top_start_block_number = top_start_block->rpo_number(); |
| |
| // Check for several cases where spilling at the definition is best. |
| // - The value is already moved on-stack somehow so the list of insertion |
| // locations for spilling at the definition is empty. |
| // - If the first LiveRange is spilled, then there's no sense in doing |
| // anything other than spilling at the definition. |
| // - If the value is defined in a deferred block, then the logic to select |
| // the earliest deferred block as the insertion point would cause |
| // incorrect behavior, so the value must be spilled at the definition. |
| // - We haven't seen any indication of performance improvements from seeking |
| // optimal spilling positions except on loop-top phi values, so spill |
| // any value that isn't a loop-top phi at the definition to avoid |
| // increasing the code size for no benefit. |
| if (range->GetSpillMoveInsertionLocations(data()) == nullptr || |
| range->spilled() || top_start_block->IsDeferred() || |
| (!FLAG_stress_turbo_late_spilling && !range->is_loop_phi())) { |
| range->CommitSpillMoves(data(), spill_operand); |
| return; |
| } |
| |
| // Iterate through the range and mark every block that needs the value to be |
| // spilled. |
| for (const LiveRange* child = range; child != nullptr; |
| child = child->next()) { |
| if (child->spilled()) { |
| // Add every block that contains part of this live range. |
| for (UseInterval* interval = child->first_interval(); interval != nullptr; |
| interval = interval->next()) { |
| RpoNumber start_block = |
| code->GetInstructionBlock(interval->start().ToInstructionIndex()) |
| ->rpo_number(); |
| if (start_block == top_start_block_number) { |
| // Can't do late spilling if the first spill is within the |
| // definition block. |
| range->CommitSpillMoves(data(), spill_operand); |
| // Verify that we never added any data for this range to the table. |
| DCHECK(!IsLatestVreg(range->vreg())); |
| return; |
| } |
| LifetimePosition end = interval->end(); |
| int end_instruction = end.ToInstructionIndex(); |
| // The end position is exclusive, so an end position exactly on a block |
| // boundary indicates that the range applies only to the prior block. |
| if (data()->IsBlockBoundary(end)) { |
| --end_instruction; |
| } |
| RpoNumber end_block = |
| code->GetInstructionBlock(end_instruction)->rpo_number(); |
| while (start_block <= end_block) { |
| SetSpillRequired(code->InstructionBlockAt(start_block), range->vreg(), |
| top_start_block_number); |
| start_block = start_block.Next(); |
| } |
| } |
| } else { |
| // Add every block that contains a use which requires the on-stack value. |
| for (const UsePosition* pos = child->first_pos(); pos != nullptr; |
| pos = pos->next()) { |
| if (pos->type() != UsePositionType::kRequiresSlot) continue; |
| InstructionBlock* block = |
| code->GetInstructionBlock(pos->pos().ToInstructionIndex()); |
| RpoNumber block_number = block->rpo_number(); |
| if (block_number == top_start_block_number) { |
| // Can't do late spilling if the first spill is within the |
| // definition block. |
| range->CommitSpillMoves(data(), spill_operand); |
| // Verify that we never added any data for this range to the table. |
| DCHECK(!IsLatestVreg(range->vreg())); |
| return; |
| } |
| SetSpillRequired(block, range->vreg(), top_start_block_number); |
| } |
| } |
| } |
| |
| // If we haven't yet marked anything for this range, then it never needs to |
| // spill at all. |
| if (!IsLatestVreg(range->vreg())) { |
| range->SetLateSpillingSelected(true); |
| return; |
| } |
| |
| SetDefinition(top_start_block_number, range->vreg()); |
| } |
| |
| class SpillPlacer::Entry { |
| public: |
| // Functions operating on single values (during setup): |
| |
| void SetSpillRequiredSingleValue(int value_index) { |
| DCHECK_LT(value_index, kValueIndicesPerEntry); |
| uint64_t bit = uint64_t{1} << value_index; |
| SetSpillRequired(bit); |
| } |
| void SetDefinitionSingleValue(int value_index) { |
| DCHECK_LT(value_index, kValueIndicesPerEntry); |
| uint64_t bit = uint64_t{1} << value_index; |
| SetDefinition(bit); |
| } |
| |
| // Functions operating on all values simultaneously, as bitfields: |
| |
| uint64_t SpillRequired() const { return GetValuesInState<kSpillRequired>(); } |
| void SetSpillRequired(uint64_t mask) { |
| UpdateValuesToState<kSpillRequired>(mask); |
| } |
| uint64_t SpillRequiredInNonDeferredSuccessor() const { |
| return GetValuesInState<kSpillRequiredInNonDeferredSuccessor>(); |
| } |
| void SetSpillRequiredInNonDeferredSuccessor(uint64_t mask) { |
| UpdateValuesToState<kSpillRequiredInNonDeferredSuccessor>(mask); |
| } |
| uint64_t SpillRequiredInDeferredSuccessor() const { |
| return GetValuesInState<kSpillRequiredInDeferredSuccessor>(); |
| } |
| void SetSpillRequiredInDeferredSuccessor(uint64_t mask) { |
| UpdateValuesToState<kSpillRequiredInDeferredSuccessor>(mask); |
| } |
| uint64_t Definition() const { return GetValuesInState<kDefinition>(); } |
| void SetDefinition(uint64_t mask) { UpdateValuesToState<kDefinition>(mask); } |
| |
| private: |
| // Possible states for every value, at every block. |
| enum State { |
| // This block is not (yet) known to require the on-stack value. |
| kUnmarked, |
| |
| // The value must be on the stack in this block. |
| kSpillRequired, |
| |
| // The value doesn't need to be on-stack in this block, but some |
| // non-deferred successor needs it. |
| kSpillRequiredInNonDeferredSuccessor, |
| |
| // The value doesn't need to be on-stack in this block, but some |
| // deferred successor needs it. |
| kSpillRequiredInDeferredSuccessor, |
| |
| // The value is defined in this block. |
| kDefinition, |
| }; |
| |
| template <State state> |
| uint64_t GetValuesInState() const { |
| STATIC_ASSERT(state < 8); |
| return ((state & 1) ? first_bit_ : ~first_bit_) & |
| ((state & 2) ? second_bit_ : ~second_bit_) & |
| ((state & 4) ? third_bit_ : ~third_bit_); |
| } |
| |
| template <State state> |
| void UpdateValuesToState(uint64_t mask) { |
| STATIC_ASSERT(state < 8); |
| first_bit_ = |
| Entry::UpdateBitDataWithMask<(state & 1) != 0>(first_bit_, mask); |
| second_bit_ = |
| Entry::UpdateBitDataWithMask<(state & 2) != 0>(second_bit_, mask); |
| third_bit_ = |
| Entry::UpdateBitDataWithMask<(state & 4) != 0>(third_bit_, mask); |
| } |
| |
| template <bool set_ones> |
| static uint64_t UpdateBitDataWithMask(uint64_t data, uint64_t mask) { |
| return set_ones ? data | mask : data & ~mask; |
| } |
| |
| // Storage for the states of up to 64 live ranges. |
| uint64_t first_bit_ = 0; |
| uint64_t second_bit_ = 0; |
| uint64_t third_bit_ = 0; |
| }; |
| |
| int SpillPlacer::GetOrCreateIndexForLatestVreg(int vreg) { |
| DCHECK_LE(assigned_indices_, kValueIndicesPerEntry); |
| // If this vreg isn't yet the last one in the list, then add it. |
| if (!IsLatestVreg(vreg)) { |
| if (vreg_numbers_ == nullptr) { |
| DCHECK_EQ(assigned_indices_, 0); |
| DCHECK_EQ(entries_, nullptr); |
| // We lazily allocate these arrays because many functions don't have any |
| // values that use SpillPlacer. |
| entries_ = |
| zone_->NewArray<Entry>(data()->code()->instruction_blocks().size()); |
| for (size_t i = 0; i < data()->code()->instruction_blocks().size(); ++i) { |
| new (&entries_[i]) Entry(); |
| } |
| vreg_numbers_ = zone_->NewArray<int>(kValueIndicesPerEntry); |
| } |
| |
| if (assigned_indices_ == kValueIndicesPerEntry) { |
| // The table is full; commit the current set of values and clear it. |
| CommitSpills(); |
| ClearData(); |
| } |
| |
| vreg_numbers_[assigned_indices_] = vreg; |
| ++assigned_indices_; |
| } |
| return assigned_indices_ - 1; |
| } |
| |
| void SpillPlacer::CommitSpills() { |
| FirstBackwardPass(); |
| ForwardPass(); |
| SecondBackwardPass(); |
| } |
| |
| void SpillPlacer::ClearData() { |
| assigned_indices_ = 0; |
| for (int i = 0; i < data()->code()->InstructionBlockCount(); ++i) { |
| new (&entries_[i]) Entry(); |
| } |
| first_block_ = RpoNumber::Invalid(); |
| last_block_ = RpoNumber::Invalid(); |
| } |
| |
| void SpillPlacer::ExpandBoundsToInclude(RpoNumber block) { |
| if (!first_block_.IsValid()) { |
| DCHECK(!last_block_.IsValid()); |
| first_block_ = block; |
| last_block_ = block; |
| } else { |
| if (first_block_ > block) { |
| first_block_ = block; |
| } |
| if (last_block_ < block) { |
| last_block_ = block; |
| } |
| } |
| } |
| |
| void SpillPlacer::SetSpillRequired(InstructionBlock* block, int vreg, |
| RpoNumber top_start_block) { |
| // Spilling in loops is bad, so if the block is non-deferred and nested |
| // within a loop, and the definition is before that loop, then mark the loop |
| // top instead. Of course we must find the outermost such loop. |
| if (!block->IsDeferred()) { |
| while (block->loop_header().IsValid() && |
| block->loop_header() > top_start_block) { |
| block = data()->code()->InstructionBlockAt(block->loop_header()); |
| } |
| } |
| |
| int value_index = GetOrCreateIndexForLatestVreg(vreg); |
| entries_[block->rpo_number().ToSize()].SetSpillRequiredSingleValue( |
| value_index); |
| ExpandBoundsToInclude(block->rpo_number()); |
| } |
| |
| void SpillPlacer::SetDefinition(RpoNumber block, int vreg) { |
| int value_index = GetOrCreateIndexForLatestVreg(vreg); |
| entries_[block.ToSize()].SetDefinitionSingleValue(value_index); |
| ExpandBoundsToInclude(block); |
| } |
| |
| void SpillPlacer::FirstBackwardPass() { |
| InstructionSequence* code = data()->code(); |
| |
| for (int i = last_block_.ToInt(); i >= first_block_.ToInt(); --i) { |
| RpoNumber block_id = RpoNumber::FromInt(i); |
| InstructionBlock* block = code->instruction_blocks()[i]; |
| |
| Entry& entry = entries_[i]; |
| |
| // State that will be accumulated from successors. |
| uint64_t spill_required_in_non_deferred_successor = 0; |
| uint64_t spill_required_in_deferred_successor = 0; |
| |
| for (RpoNumber successor_id : block->successors()) { |
| // Ignore loop back-edges. |
| if (successor_id <= block_id) continue; |
| |
| InstructionBlock* successor = code->InstructionBlockAt(successor_id); |
| const Entry& successor_entry = entries_[successor_id.ToSize()]; |
| if (successor->IsDeferred()) { |
| spill_required_in_deferred_successor |= successor_entry.SpillRequired(); |
| } else { |
| spill_required_in_non_deferred_successor |= |
| successor_entry.SpillRequired(); |
| } |
| spill_required_in_deferred_successor |= |
| successor_entry.SpillRequiredInDeferredSuccessor(); |
| spill_required_in_non_deferred_successor |= |
| successor_entry.SpillRequiredInNonDeferredSuccessor(); |
| } |
| |
| // Starting state of the current block. |
| uint64_t defs = entry.Definition(); |
| uint64_t needs_spill = entry.SpillRequired(); |
| |
| // Info about successors doesn't get to override existing info about |
| // definitions and spills required by this block itself. |
| spill_required_in_deferred_successor &= ~(defs | needs_spill); |
| spill_required_in_non_deferred_successor &= ~(defs | needs_spill); |
| |
| entry.SetSpillRequiredInDeferredSuccessor( |
| spill_required_in_deferred_successor); |
| entry.SetSpillRequiredInNonDeferredSuccessor( |
| spill_required_in_non_deferred_successor); |
| } |
| } |
| |
| void SpillPlacer::ForwardPass() { |
| InstructionSequence* code = data()->code(); |
| for (int i = first_block_.ToInt(); i <= last_block_.ToInt(); ++i) { |
| RpoNumber block_id = RpoNumber::FromInt(i); |
| InstructionBlock* block = code->instruction_blocks()[i]; |
| |
| // Deferred blocks don't need to participate in the forward pass, because |
| // their spills all get pulled forward to the earliest possible deferred |
| // block (where a non-deferred block jumps to a deferred block), and |
| // decisions about spill requirements for non-deferred blocks don't take |
| // deferred blocks into account. |
| if (block->IsDeferred()) continue; |
| |
| Entry& entry = entries_[i]; |
| |
| // State that will be accumulated from predecessors. |
| uint64_t spill_required_in_non_deferred_predecessor = 0; |
| uint64_t spill_required_in_all_non_deferred_predecessors = |
| static_cast<uint64_t>(int64_t{-1}); |
| |
| for (RpoNumber predecessor_id : block->predecessors()) { |
| // Ignore loop back-edges. |
| if (predecessor_id >= block_id) continue; |
| |
| InstructionBlock* predecessor = code->InstructionBlockAt(predecessor_id); |
| if (predecessor->IsDeferred()) continue; |
| const Entry& predecessor_entry = entries_[predecessor_id.ToSize()]; |
| spill_required_in_non_deferred_predecessor |= |
| predecessor_entry.SpillRequired(); |
| spill_required_in_all_non_deferred_predecessors &= |
| predecessor_entry.SpillRequired(); |
| } |
| |
| // Starting state of the current block. |
| uint64_t spill_required_in_non_deferred_successor = |
| entry.SpillRequiredInNonDeferredSuccessor(); |
| uint64_t spill_required_in_any_successor = |
| spill_required_in_non_deferred_successor | |
| entry.SpillRequiredInDeferredSuccessor(); |
| |
| // If all of the predecessors agree that a spill is required, then a |
| // spill is required. Note that we don't set anything for values that |
| // currently have no markings in this block, to avoid pushing data too |
| // far down the graph and confusing the next backward pass. |
| entry.SetSpillRequired(spill_required_in_any_successor & |
| spill_required_in_non_deferred_predecessor & |
| spill_required_in_all_non_deferred_predecessors); |
| |
| // If only some of the predecessors require a spill, but some successor |
| // of this block also requires a spill, then this merge point requires a |
| // spill. This ensures that no control-flow path through non-deferred |
| // blocks ever has to spill twice. |
| entry.SetSpillRequired(spill_required_in_non_deferred_successor & |
| spill_required_in_non_deferred_predecessor); |
| } |
| } |
| |
| void SpillPlacer::SecondBackwardPass() { |
| InstructionSequence* code = data()->code(); |
| for (int i = last_block_.ToInt(); i >= first_block_.ToInt(); --i) { |
| RpoNumber block_id = RpoNumber::FromInt(i); |
| InstructionBlock* block = code->instruction_blocks()[i]; |
| |
| Entry& entry = entries_[i]; |
| |
| // State that will be accumulated from successors. |
| uint64_t spill_required_in_non_deferred_successor = 0; |
| uint64_t spill_required_in_deferred_successor = 0; |
| uint64_t spill_required_in_all_non_deferred_successors = |
| static_cast<uint64_t>(int64_t{-1}); |
| |
| for (RpoNumber successor_id : block->successors()) { |
| // Ignore loop back-edges. |
| if (successor_id <= block_id) continue; |
| |
| InstructionBlock* successor = code->InstructionBlockAt(successor_id); |
| const Entry& successor_entry = entries_[successor_id.ToSize()]; |
| if (successor->IsDeferred()) { |
| spill_required_in_deferred_successor |= successor_entry.SpillRequired(); |
| } else { |
| spill_required_in_non_deferred_successor |= |
| successor_entry.SpillRequired(); |
| spill_required_in_all_non_deferred_successors &= |
| successor_entry.SpillRequired(); |
| } |
| } |
| |
| // Starting state of the current block. |
| uint64_t defs = entry.Definition(); |
| |
| // If all of the successors of a definition need the value to be |
| // spilled, then the value should be spilled at the definition. |
| uint64_t spill_at_def = defs & spill_required_in_non_deferred_successor & |
| spill_required_in_all_non_deferred_successors; |
| for (int index_to_spill : base::bits::IterateBits(spill_at_def)) { |
| int vreg_to_spill = vreg_numbers_[index_to_spill]; |
| TopLevelLiveRange* top = data()->live_ranges()[vreg_to_spill]; |
| top->CommitSpillMoves(data(), top->GetSpillRangeOperand()); |
| } |
| |
| if (block->IsDeferred()) { |
| DCHECK_EQ(defs, 0); |
| // Any deferred successor needing a spill is sufficient to make the |
| // current block need a spill. |
| entry.SetSpillRequired(spill_required_in_deferred_successor); |
| } |
| |
| // Propagate data upward if there are non-deferred successors and they |
| // all need a spill, regardless of whether the current block is |
| // deferred. |
| entry.SetSpillRequired(~defs & spill_required_in_non_deferred_successor & |
| spill_required_in_all_non_deferred_successors); |
| |
| // Iterate the successors again to find out which ones require spills at |
| // their beginnings, and insert those spills. |
| for (RpoNumber successor_id : block->successors()) { |
| // Ignore loop back-edges. |
| if (successor_id <= block_id) continue; |
| |
| InstructionBlock* successor = code->InstructionBlockAt(successor_id); |
| const Entry& successor_entry = entries_[successor_id.ToSize()]; |
| for (int index_to_spill : |
| base::bits::IterateBits(successor_entry.SpillRequired() & |
| ~entry.SpillRequired() & ~spill_at_def)) { |
| CommitSpill(vreg_numbers_[index_to_spill], block, successor); |
| } |
| } |
| } |
| } |
| |
| void SpillPlacer::CommitSpill(int vreg, InstructionBlock* predecessor, |
| InstructionBlock* successor) { |
| TopLevelLiveRange* top = data()->live_ranges()[vreg]; |
| LiveRangeBoundArray* array = finder_->ArrayFor(vreg); |
| LifetimePosition pred_end = LifetimePosition::InstructionFromInstructionIndex( |
| predecessor->last_instruction_index()); |
| LiveRangeBound* bound = array->Find(pred_end); |
| InstructionOperand pred_op = bound->range_->GetAssignedOperand(); |
| DCHECK(pred_op.IsAnyRegister()); |
| DCHECK_EQ(successor->PredecessorCount(), 1); |
| data()->AddGapMove(successor->first_instruction_index(), |
| Instruction::GapPosition::START, pred_op, |
| top->GetSpillRangeOperand()); |
| successor->mark_needs_frame(); |
| top->SetLateSpillingSelected(true); |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |