Merge V8 5.3.332.45. DO NOT MERGE
Test: Manual
FPIIM-449
Change-Id: Id3254828b068abdea3cb10442e0172a8c9a98e03
(cherry picked from commit 13e2dadd00298019ed862f2b2fc5068bba730bcf)
diff --git a/src/interpreter/bytecode-register-optimizer.cc b/src/interpreter/bytecode-register-optimizer.cc
new file mode 100644
index 0000000..ab25f95
--- /dev/null
+++ b/src/interpreter/bytecode-register-optimizer.cc
@@ -0,0 +1,630 @@
+// 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(
+ int fixed_register_count, int parameter_count,
+ Handle<FixedArray> handler_table) {
+ FlushState();
+ return next_stage_->ToBytecodeArray(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.
+ //
+ 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