text: // Copyright 2016 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/interpreter/bytecode-register-optimizer.h"
  
  namespace v8 {
  namespace internal {
  namespace interpreter {
  
  const uint32_t BytecodeRegisterOptimizer::kInvalidEquivalenceId;
  
  // A class for tracking the state of a register. This class tracks
  // which equivalence set a register is a member of and also whether a
  // register is materialized in the bytecode stream.
  class BytecodeRegisterOptimizer::RegisterInfo final : public ZoneObject {
   public:
    RegisterInfo(Register reg, uint32_t equivalence_id, bool materialized)
        : register_(reg),
          equivalence_id_(equivalence_id),
          materialized_(materialized),
          next_(this),
          prev_(this) {}
  
    void AddToEquivalenceSetOf(RegisterInfo* info);
    void MoveToNewEquivalenceSet(uint32_t equivalence_id, bool materialized);
    bool IsOnlyMemberOfEquivalenceSet() const;
    bool IsOnlyMaterializedMemberOfEquivalenceSet() const;
    bool IsInSameEquivalenceSet(RegisterInfo* info) const;
  
    // Get a member of this register's equivalence set that is
    // materialized. The materialized equivalent will be this register
    // if it is materialized. Returns nullptr if no materialized
    // equivalent exists.
    RegisterInfo* GetMaterializedEquivalent();
  
    // Get a member of this register's equivalence set that is
    // materialized and not register |reg|. The materialized equivalent
    // will be this register if it is materialized. Returns nullptr if
    // no materialized equivalent exists.
    RegisterInfo* GetMaterializedEquivalentOtherThan(Register reg);
  
    // Get a member of this register's equivalence set that is intended
    // to be materialized in place of this register (which is currently
    // materialized). The best candidate is deemed to be the register
    // with the lowest index as this permits temporary registers to be
    // removed from the bytecode stream. Returns nullptr if no candidate
    // exists.
    RegisterInfo* GetEquivalentToMaterialize();
  
    // Get an equivalent register. Returns this if none exists.
    RegisterInfo* GetEquivalent();
  
    Register register_value() const { return register_; }
    bool materialized() const { return materialized_; }
    void set_materialized(bool materialized) { materialized_ = materialized; }
    void set_equivalence_id(uint32_t equivalence_id) {
      equivalence_id_ = equivalence_id;
    }
    uint32_t equivalence_id() const { return equivalence_id_; }
  
   private:
    Register register_;
    uint32_t equivalence_id_;
    bool materialized_;
  
    // Equivalence set pointers.
    RegisterInfo* next_;
    RegisterInfo* prev_;
  
    DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
  };
  
  void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
      RegisterInfo* info) {
    DCHECK_NE(kInvalidEquivalenceId, info->equivalence_id());
    // Fix old list
    next_->prev_ = prev_;
    prev_->next_ = next_;
    // Add to new list.
    next_ = info->next_;
    prev_ = info;
    prev_->next_ = this;
    next_->prev_ = this;
    set_equivalence_id(info->equivalence_id());
    set_materialized(false);
  }
  
  void BytecodeRegisterOptimizer::RegisterInfo::MoveToNewEquivalenceSet(
      uint32_t equivalence_id, bool materialized) {
    next_->prev_ = prev_;
    prev_->next_ = next_;
    next_ = prev_ = this;
    equivalence_id_ = equivalence_id;
    materialized_ = materialized;
  }
  
  bool BytecodeRegisterOptimizer::RegisterInfo::IsOnlyMemberOfEquivalenceSet()
      const {
    return this->next_ == this;
  }
  
  bool BytecodeRegisterOptimizer::RegisterInfo::
      IsOnlyMaterializedMemberOfEquivalenceSet() const {
    DCHECK(materialized());
  
    const RegisterInfo* visitor = this->next_;
    while (visitor != this) {
      if (visitor->materialized()) {
        return false;
      }
      visitor = visitor->next_;
    }
    return true;
  }
  
  bool BytecodeRegisterOptimizer::RegisterInfo::IsInSameEquivalenceSet(
      RegisterInfo* info) const {
    return equivalence_id() == info->equivalence_id();
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalent() {
    RegisterInfo* visitor = this;
    do {
      if (visitor->materialized()) {
        return visitor;
      }
      visitor = visitor->next_;
    } while (visitor != this);
  
    return nullptr;
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::RegisterInfo::GetMaterializedEquivalentOtherThan(
      Register reg) {
    RegisterInfo* visitor = this;
    do {
      if (visitor->materialized() && visitor->register_value() != reg) {
        return visitor;
      }
      visitor = visitor->next_;
    } while (visitor != this);
  
    return nullptr;
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
    DCHECK(this->materialized());
    RegisterInfo* visitor = this->next_;
    RegisterInfo* best_info = nullptr;
    while (visitor != this) {
      if (visitor->materialized()) {
        return nullptr;
      }
      if (best_info == nullptr ||
          visitor->register_value() < best_info->register_value()) {
        best_info = visitor;
      }
      visitor = visitor->next_;
    }
    return best_info;
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
    return next_;
  }
  
  BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
      Zone* zone, TemporaryRegisterAllocator* register_allocator,
      int parameter_count, BytecodePipelineStage* next_stage)
      : accumulator_(Register::virtual_accumulator()),
        temporary_base_(register_allocator->allocation_base()),
        register_info_table_(zone),
        equivalence_id_(0),
        next_stage_(next_stage),
        flush_required_(false),
        zone_(zone) {
    register_allocator->set_observer(this);
  
    // Calculate offset so register index values can be mapped into
    // a vector of register metadata.
    if (parameter_count != 0) {
      register_info_table_offset_ =
          -Register::FromParameterIndex(0, parameter_count).index();
    } else {
      // TODO(oth): This path shouldn't be necessary in bytecode generated
      // from Javascript, but a set of tests do not include the JS receiver.
      register_info_table_offset_ = -accumulator_.index();
    }
  
    // Initialize register map for parameters, locals, and the
    // accumulator.
    register_info_table_.resize(register_info_table_offset_ +
                                static_cast<size_t>(temporary_base_.index()));
    for (size_t i = 0; i < register_info_table_.size(); ++i) {
      register_info_table_[i] = new (zone) RegisterInfo(
          RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true);
      DCHECK_EQ(register_info_table_[i]->register_value().index(),
                RegisterFromRegisterInfoTableIndex(i).index());
    }
    accumulator_info_ = GetRegisterInfo(accumulator_);
    DCHECK(accumulator_info_->register_value() == accumulator_);
  }
  
  // override
  Handle<BytecodeArray> BytecodeRegisterOptimizer::ToBytecodeArray(
      Isolate* isolate, int fixed_register_count, int parameter_count,
      Handle<FixedArray> handler_table) {
    FlushState();
    return next_stage_->ToBytecodeArray(isolate, fixed_register_count,
                                        parameter_count, handler_table);
  }
  
  // override
  void BytecodeRegisterOptimizer::Write(BytecodeNode* node) {
    //
    // Transfers with observable registers as the destination will be
    // immediately materialized so the source position information will
    // be ordered correctly.
    //
    // Transfers without observable destination registers will initially
    // be emitted as Nop's with the source position. They may, or may
    // not, be materialized by the optimizer. However, the source
    // position is not lost and being attached to a Nop is fine as the
    // destination register is not observable in the debugger.
    //
    switch (node->bytecode()) {
      case Bytecode::kLdar: {
        DoLdar(node);
        return;
      }
      case Bytecode::kStar: {
        DoStar(node);
        return;
      }
      case Bytecode::kMov: {
        DoMov(node);
        return;
      }
      default:
        break;
    }
  
    if (Bytecodes::IsJump(node->bytecode()) ||
        node->bytecode() == Bytecode::kDebugger ||
        node->bytecode() == Bytecode::kSuspendGenerator) {
      // All state must be flushed before emitting
      // - a jump (due to how bytecode offsets for jumps are evaluated),
      // - a call to the debugger (as it can manipulate locals and parameters),
      // - a generator suspend (as this involves saving all registers).
      FlushState();
    }
  
    PrepareOperands(node);
    WriteToNextStage(node);
  }
  
  // override
  void BytecodeRegisterOptimizer::WriteJump(BytecodeNode* node,
                                            BytecodeLabel* label) {
    FlushState();
    next_stage_->WriteJump(node, label);
  }
  
  // override
  void BytecodeRegisterOptimizer::BindLabel(BytecodeLabel* label) {
    FlushState();
    next_stage_->BindLabel(label);
  }
  
  // override
  void BytecodeRegisterOptimizer::BindLabel(const BytecodeLabel& target,
                                            BytecodeLabel* label) {
    // There is no need to flush here, it will have been flushed when |target|
    // was bound.
    next_stage_->BindLabel(target, label);
  }
  
  void BytecodeRegisterOptimizer::FlushState() {
    if (!flush_required_) {
      return;
    }
  
    // Materialize all live registers and break equivalences.
    size_t count = register_info_table_.size();
    for (size_t i = 0; i < count; ++i) {
      RegisterInfo* reg_info = register_info_table_[i];
      if (reg_info->materialized()) {
        // Walk equivalents of materialized registers, materializing
        // each equivalent register as necessary and placing in their
        // own equivalence set.
        RegisterInfo* equivalent;
        while ((equivalent = reg_info->GetEquivalent()) != reg_info) {
          if (!equivalent->materialized()) {
            OutputRegisterTransfer(reg_info, equivalent);
          }
          equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
        }
      }
    }
  
    flush_required_ = false;
  }
  
  void BytecodeRegisterOptimizer::WriteToNextStage(BytecodeNode* node) const {
    next_stage_->Write(node);
  }
  
  void BytecodeRegisterOptimizer::WriteToNextStage(
      BytecodeNode* node, const BytecodeSourceInfo& source_info) const {
    if (source_info.is_valid()) {
      node->source_info().Clone(source_info);
    }
    next_stage_->Write(node);
  }
  
  void BytecodeRegisterOptimizer::OutputRegisterTransfer(
      RegisterInfo* input_info, RegisterInfo* output_info,
      const BytecodeSourceInfo& source_info) {
    Register input = input_info->register_value();
    Register output = output_info->register_value();
    DCHECK_NE(input.index(), output.index());
  
    if (input == accumulator_) {
      uint32_t operand = static_cast<uint32_t>(output.ToOperand());
      BytecodeNode node(Bytecode::kStar, operand);
      WriteToNextStage(&node, source_info);
    } else if (output == accumulator_) {
      uint32_t operand = static_cast<uint32_t>(input.ToOperand());
      BytecodeNode node(Bytecode::kLdar, operand);
      WriteToNextStage(&node, source_info);
    } else {
      uint32_t operand0 = static_cast<uint32_t>(input.ToOperand());
      uint32_t operand1 = static_cast<uint32_t>(output.ToOperand());
      BytecodeNode node(Bytecode::kMov, operand0, operand1);
      WriteToNextStage(&node, source_info);
    }
    output_info->set_materialized(true);
  }
  
  void BytecodeRegisterOptimizer::CreateMaterializedEquivalent(
      RegisterInfo* info) {
    DCHECK(info->materialized());
    RegisterInfo* unmaterialized = info->GetEquivalentToMaterialize();
    if (unmaterialized) {
      OutputRegisterTransfer(info, unmaterialized);
    }
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::GetMaterializedEquivalent(RegisterInfo* info) {
    return info->materialized() ? info : info->GetMaterializedEquivalent();
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::GetMaterializedEquivalentNotAccumulator(
      RegisterInfo* info) {
    if (info->materialized()) {
      return info;
    }
  
    RegisterInfo* result = info->GetMaterializedEquivalentOtherThan(accumulator_);
    if (result == nullptr) {
      Materialize(info);
      result = info;
    }
    DCHECK(result->register_value() != accumulator_);
    return result;
  }
  
  void BytecodeRegisterOptimizer::Materialize(RegisterInfo* info) {
    if (!info->materialized()) {
      RegisterInfo* materialized = info->GetMaterializedEquivalent();
      OutputRegisterTransfer(materialized, info);
    }
  }
  
  void BytecodeRegisterOptimizer::AddToEquivalenceSet(
      RegisterInfo* set_member, RegisterInfo* non_set_member) {
    non_set_member->AddToEquivalenceSetOf(set_member);
    // Flushing is only required when two or more registers are placed
    // in the same equivalence set.
    flush_required_ = true;
  }
  
  void BytecodeRegisterOptimizer::RegisterTransfer(
      RegisterInfo* input_info, RegisterInfo* output_info,
      const BytecodeSourceInfo& source_info) {
    // Materialize an alternate in the equivalence set that
    // |output_info| is leaving.
    if (output_info->materialized()) {
      CreateMaterializedEquivalent(output_info);
    }
  
    // Add |output_info| to new equivalence set.
    if (!output_info->IsInSameEquivalenceSet(input_info)) {
      AddToEquivalenceSet(input_info, output_info);
    }
  
    bool output_is_observable =
        RegisterIsObservable(output_info->register_value());
    if (output_is_observable) {
      // Force store to be emitted when register is observable.
      output_info->set_materialized(false);
      RegisterInfo* materialized_info = input_info->GetMaterializedEquivalent();
      OutputRegisterTransfer(materialized_info, output_info, source_info);
    } else if (source_info.is_valid()) {
      // Emit a placeholder nop to maintain source position info.
      EmitNopForSourceInfo(source_info);
    }
  }
  
  void BytecodeRegisterOptimizer::EmitNopForSourceInfo(
      const BytecodeSourceInfo& source_info) const {
    DCHECK(source_info.is_valid());
    BytecodeNode nop(Bytecode::kNop);
    nop.source_info().Clone(source_info);
    WriteToNextStage(&nop);
  }
  
  void BytecodeRegisterOptimizer::DoLdar(const BytecodeNode* const node) {
    Register input = GetRegisterInputOperand(
        0, node->bytecode(), node->operands(), node->operand_count());
    RegisterInfo* input_info = GetRegisterInfo(input);
    RegisterTransfer(input_info, accumulator_info_, node->source_info());
  }
  
  void BytecodeRegisterOptimizer::DoMov(const BytecodeNode* const node) {
    Register input = GetRegisterInputOperand(
        0, node->bytecode(), node->operands(), node->operand_count());
    RegisterInfo* input_info = GetRegisterInfo(input);
    Register output = GetRegisterOutputOperand(
        1, node->bytecode(), node->operands(), node->operand_count());
    RegisterInfo* output_info = GetOrCreateRegisterInfo(output);
    RegisterTransfer(input_info, output_info, node->source_info());
  }
  
  void BytecodeRegisterOptimizer::DoStar(const BytecodeNode* const node) {
    Register output = GetRegisterOutputOperand(
        0, node->bytecode(), node->operands(), node->operand_count());
    RegisterInfo* output_info = GetOrCreateRegisterInfo(output);
    RegisterTransfer(accumulator_info_, output_info, node->source_info());
  }
  
  void BytecodeRegisterOptimizer::PrepareRegisterOutputOperand(
      RegisterInfo* reg_info) {
    if (reg_info->materialized()) {
      CreateMaterializedEquivalent(reg_info);
    }
    reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
  }
  
  void BytecodeRegisterOptimizer::PrepareRegisterRangeOutputOperand(
      Register start, int count) {
    for (int i = 0; i < count; ++i) {
      Register reg(start.index() + i);
      RegisterInfo* reg_info = GetOrCreateRegisterInfo(reg);
      PrepareRegisterOutputOperand(reg_info);
    }
  }
  
  Register BytecodeRegisterOptimizer::GetEquivalentRegisterForInputOperand(
      Register reg) {
    // For a temporary register, RegInfo state may need be created. For
    // locals and parameters, the RegInfo state is created in the
    // BytecodeRegisterOptimizer constructor.
    RegisterInfo* reg_info = GetOrCreateRegisterInfo(reg);
    if (reg_info->materialized()) {
      return reg;
    } else {
      RegisterInfo* equivalent_info =
          GetMaterializedEquivalentNotAccumulator(reg_info);
      return equivalent_info->register_value();
    }
  }
  
  void BytecodeRegisterOptimizer::PrepareRegisterInputOperand(
      BytecodeNode* const node, Register reg, int operand_index) {
    Register equivalent = GetEquivalentRegisterForInputOperand(reg);
    node->operands()[operand_index] =
        static_cast<uint32_t>(equivalent.ToOperand());
  }
  
  void BytecodeRegisterOptimizer::PrepareRegisterRangeInputOperand(Register start,
                                                                   int count) {
    for (int i = 0; i < count; ++i) {
      Register current(start.index() + i);
      RegisterInfo* input_info = GetRegisterInfo(current);
      Materialize(input_info);
    }
  }
  
  void BytecodeRegisterOptimizer::PrepareRegisterOperands(
      BytecodeNode* const node) {
    //
    // For each input operand, get a materialized equivalent if it is
    // just a single register, otherwise materialize register range.
    // Update operand_scale if necessary.
    //
    // For each output register about to be clobbered, materialize an
    // equivalent if it exists. Put each register in it's own equivalence set.
    //
    const uint32_t* operands = node->operands();
    int operand_count = node->operand_count();
    const OperandType* operand_types =
        Bytecodes::GetOperandTypes(node->bytecode());
    for (int i = 0; i < operand_count; ++i) {
      int count;
      // operand_types is terminated by OperandType::kNone so this does not
      // go out of bounds.
      if (operand_types[i + 1] == OperandType::kRegCount) {
        count = static_cast<int>(operands[i + 1]);
      } else {
        count = Bytecodes::GetNumberOfRegistersRepresentedBy(operand_types[i]);
      }
  
      if (count == 0) {
        continue;
      }
  
      Register reg = Register::FromOperand(static_cast<int32_t>(operands[i]));
      if (Bytecodes::IsRegisterInputOperandType(operand_types[i])) {
        if (count == 1) {
          PrepareRegisterInputOperand(node, reg, i);
        } else if (count > 1) {
          PrepareRegisterRangeInputOperand(reg, count);
        }
      } else if (Bytecodes::IsRegisterOutputOperandType(operand_types[i])) {
        PrepareRegisterRangeOutputOperand(reg, count);
      }
    }
  }
  
  void BytecodeRegisterOptimizer::PrepareAccumulator(BytecodeNode* const node) {
    // Materialize the accumulator if it is read by the bytecode. The
    // accumulator is special and no other register can be materialized
    // in it's place.
    if (Bytecodes::ReadsAccumulator(node->bytecode()) &&
        !accumulator_info_->materialized()) {
      Materialize(accumulator_info_);
    }
  
    // Materialize an equivalent to the accumulator if it will be
    // clobbered when the bytecode is dispatched.
    if (Bytecodes::WritesAccumulator(node->bytecode())) {
      PrepareRegisterOutputOperand(accumulator_info_);
    }
  }
  
  void BytecodeRegisterOptimizer::PrepareOperands(BytecodeNode* const node) {
    PrepareAccumulator(node);
    PrepareRegisterOperands(node);
  }
  
  // static
  Register BytecodeRegisterOptimizer::GetRegisterInputOperand(
      int index, Bytecode bytecode, const uint32_t* operands, int operand_count) {
    DCHECK_LT(index, operand_count);
    DCHECK(Bytecodes::IsRegisterInputOperandType(
        Bytecodes::GetOperandType(bytecode, index)));
    return OperandToRegister(operands[index]);
  }
  
  // static
  Register BytecodeRegisterOptimizer::GetRegisterOutputOperand(
      int index, Bytecode bytecode, const uint32_t* operands, int operand_count) {
    DCHECK_LT(index, operand_count);
    DCHECK(Bytecodes::IsRegisterOutputOperandType(
        Bytecodes::GetOperandType(bytecode, index)));
    return OperandToRegister(operands[index]);
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::GetRegisterInfo(Register reg) {
    size_t index = GetRegisterInfoTableIndex(reg);
    return (index < register_info_table_.size()) ? register_info_table_[index]
                                                 : nullptr;
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::GetOrCreateRegisterInfo(Register reg) {
    size_t index = GetRegisterInfoTableIndex(reg);
    return index < register_info_table_.size() ? register_info_table_[index]
                                               : NewRegisterInfo(reg);
  }
  
  BytecodeRegisterOptimizer::RegisterInfo*
  BytecodeRegisterOptimizer::NewRegisterInfo(Register reg) {
    size_t index = GetRegisterInfoTableIndex(reg);
    DCHECK_GE(index, register_info_table_.size());
    GrowRegisterMap(reg);
    return register_info_table_[index];
  }
  
  void BytecodeRegisterOptimizer::GrowRegisterMap(Register reg) {
    DCHECK(RegisterIsTemporary(reg));
    size_t index = GetRegisterInfoTableIndex(reg);
    DCHECK_GE(index, register_info_table_.size());
    size_t new_size = index + 1;
    size_t old_size = register_info_table_.size();
    register_info_table_.resize(new_size);
    for (size_t i = old_size; i < new_size; ++i) {
      register_info_table_[i] = new (zone()) RegisterInfo(
          RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), false);
    }
  }
  
  void BytecodeRegisterOptimizer::TemporaryRegisterFreeEvent(Register reg) {
    RegisterInfo* info = GetRegisterInfo(reg);
    if (info != nullptr) {
      // If register is materialized and part of equivalence set, make
      // sure another member of the set holds the value before the
      // temporary register is removed.
      if (info->materialized()) {
        CreateMaterializedEquivalent(info);
      }
      info->MoveToNewEquivalenceSet(kInvalidEquivalenceId, false);
    }
  }
  
  }  // namespace interpreter
  }  // namespace internal
  }  // namespace v8
  