src/third_party/v8/src/compiler/backend/spill-placer.cc - cobalt - Git at Google

 // 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
	// 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