[interpreter] Bytecode register optimizer.

src/interpreter/bytecode-register-optimizer.cc

+// 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 {
+
+// 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();
+
+  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) {
+  // 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::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),
+      flushed_(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_);
+}
+
+void BytecodeRegisterOptimizer::FlushState() {
+  if (flushed_) {
+    return;
+  }
+
+  // Materialize all live registers.
+  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->IsOnlyMemberOfEquivalenceSet() &&
+        !reg_info->materialized()) {
+      DCHECK(RegisterIsTemporary(reg_info->register_value()) ||
+             reg_info->register_value() == accumulator_);
+      Materialize(reg_info);
+    }
+  }
+
+  // Break all existing equivalences.
+  for (size_t i = 0; i < count; ++i) {
+    RegisterInfo* reg_info = register_info_table_[i];
+    if (!reg_info->IsOnlyMemberOfEquivalenceSet()) {
+      reg_info->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
+    }
+  }
+
+  flushed_ = true;
+}
+
+// override
+void BytecodeRegisterOptimizer::FlushBasicBlock() {
+  FlushState();
+  next_stage_->FlushBasicBlock();
+}
+
+// override
+size_t BytecodeRegisterOptimizer::FlushForOffset() {
+  FlushState();
+  return next_stage_->FlushForOffset();
+}
+
+// override
+void BytecodeRegisterOptimizer::Write(BytecodeNode* node) {
+  flushed_ = false;
+
+  //
+  // 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) {
+    // The debugger can manipulate locals and parameters, flush
+    // everything before handing over to it. Similarly, all state must
+    // be flushed before emitting a jump due to how bytecode offsets
+    // for jumps are evaluated.
+    FlushState();
+  }
+
+  PrepareOperands(node);
+  WriteToNextStage(node);
+}
+
+void BytecodeRegisterOptimizer::WriteToNextStage(BytecodeNode* node) const {
+  next_stage_->Write(node);
+}
+
+void BytecodeRegisterOptimizer::WriteToNextStage(
+    BytecodeNode* node, const BytecodeSourceInfo& source_info) const {
+  node->source_info().Update(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());
+    OperandScale scale = Bytecodes::OperandSizesToScale(output.SizeOfOperand());
+    BytecodeNode node(Bytecode::kStar, operand, scale);
+    WriteToNextStage(&node, source_info);
+  } else if (output == accumulator_) {
+    uint32_t operand = static_cast<uint32_t>(input.ToOperand());
+    OperandScale scale = Bytecodes::OperandSizesToScale(input.SizeOfOperand());
+    BytecodeNode node(Bytecode::kLdar, operand, scale);
+    WriteToNextStage(&node, source_info);
+  } else {
+    uint32_t operand0 = static_cast<uint32_t>(input.ToOperand());
+    uint32_t operand1 = static_cast<uint32_t>(output.ToOperand());
+    OperandScale scale = Bytecodes::OperandSizesToScale(input.SizeOfOperand(),
+                                                        output.SizeOfOperand());
+    BytecodeNode node(Bytecode::kMov, operand0, operand1, scale);
+    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::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)) {
+    output_info->AddToEquivalenceSetOf(input_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 {
+  BytecodeNode nop(Bytecode::kNop);
+  nop.source_info().Update(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());
+  // Update operand scale as equivalent may be different.
+  OperandScale operand_scale =
+      Bytecodes::OperandSizesToScale(equivalent.SizeOfOperand());
+  if (operand_scale > node->operand_scale()) {
+    node->set_operand_scale(operand_scale);
+  }
+}
+
+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.
+  //
+  int register_operand_bitmap =
+      Bytecodes::GetRegisterOperandBitmap(node->bytecode());
+  const OperandType* operand_types =
+      Bytecodes::GetOperandTypes(node->bytecode());
+  uint32_t* operands = node->operands();
+  for (int i = 0; register_operand_bitmap != 0;
+       ++i, register_operand_bitmap >>= 1) {
+    if ((register_operand_bitmap & 1) == 0) {
+      continue;
+    }
+    OperandType operand_type = operand_types[i];
+    int count = 0;
+    if (operand_types[i + 1] == OperandType::kRegCount) {
+      count = static_cast<int>(operands[i + 1]);
+      if (count == 0) {
+        continue;
+      }
+    } else {
+      count = Bytecodes::GetNumberOfRegistersRepresentedBy(operand_type);
+    }
+
+    Register reg = Register::FromOperand(static_cast<int32_t>(operands[i]));
+    if (Bytecodes::IsRegisterInputOperandType(operand_type)) {
+      if (count == 1) {
+        PrepareRegisterInputOperand(node, reg, i);
+      } else if (count > 1) {
+        PrepareRegisterRangeInputOperand(reg, count);
+      }
+    } else if (Bytecodes::IsRegisterOutputOperandType(operand_type)) {
+      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