[Interpreter] Replace BytecodeRegisterAllocator with a simple bump pointer.

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 {
 
 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)
+  RegisterInfo(Register reg, uint32_t equivalence_id, bool materialized,
+               bool allocated)
       : register_(reg),
         equivalence_id_(equivalence_id),
         materialized_(materialized),
+        allocated_(allocated),
         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();
 
+  // Marks all temporary registers of the equivalence set as unmaterialized.
+  void MarkTemporariesAsUnmaterialized(Register temporary_base);
+
   // 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; }
+  bool allocated() const { return allocated_; }
+  void set_allocated(bool allocated) { allocated_ = allocated; }
   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_;
+  bool allocated_;
 
   // Equivalence set pointers.
   RegisterInfo* next_;
   RegisterInfo* prev_;
 
   DISALLOW_COPY_AND_ASSIGN(RegisterInfo);
 };
 
 void BytecodeRegisterOptimizer::RegisterInfo::AddToEquivalenceSetOf(
     RegisterInfo* info) {
@@ skipping 72 matching lines @@
 
 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()) {
+    if (visitor->allocated() &&
+        (best_info == nullptr ||
+         visitor->register_value() < best_info->register_value())) {
       best_info = visitor;
     }
     visitor = visitor->next_;
   }
   return best_info;
 }
 
+void BytecodeRegisterOptimizer::RegisterInfo::MarkTemporariesAsUnmaterialized(
+    Register temporary_base) {
+  DCHECK(this->register_value() < temporary_base);
+  DCHECK(this->materialized());
+  RegisterInfo* visitor = this->next_;
+  while (visitor != this) {
+    if (visitor->register_value() >= temporary_base) {
+      visitor->set_materialized(false);
+    }
+    visitor = visitor->next_;
+  }
+}
+
 BytecodeRegisterOptimizer::RegisterInfo*
 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalent() {
   return next_;
 }
 
 BytecodeRegisterOptimizer::BytecodeRegisterOptimizer(
-    Zone* zone, TemporaryRegisterAllocator* register_allocator,
-    int parameter_count, BytecodePipelineStage* next_stage)
+    Zone* zone, BytecodeRegisterAllocator* register_allocator,
+    int fixed_registers_count, int parameter_count,
+    BytecodePipelineStage* next_stage)
     : accumulator_(Register::virtual_accumulator()),
-      temporary_base_(register_allocator->allocation_base()),
-      max_register_index_(register_allocator->allocation_base() - 1),
+      temporary_base_(fixed_registers_count),
+      max_register_index_(fixed_registers_count - 1),
       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);
+        RegisterFromRegisterInfoTableIndex(i), NextEquivalenceId(), true, 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 register_count, int parameter_count,
@@ skipping 76 matching lines @@
   // 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()) {
+        if (equivalent->allocated() && !equivalent->materialized()) {
           OutputRegisterTransfer(reg_info, equivalent);
         }
         equivalent->MoveToNewEquivalenceSet(NextEquivalenceId(), true);
       }
     }
   }
 
   flush_required_ = false;
 }
 
@@ skipping 87 matching lines @@
       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);
   }
+
+  bool input_is_observable = RegisterIsObservable(input_info->register_value());
+  if (input_is_observable) {
+    // If input is observable by the debugger, mark all other temporaries
+    // registers as unmaterialized so that this register is used in preference.
+    input_info->MarkTemporariesAsUnmaterialized(temporary_base_);
+  }
 }
 
 void BytecodeRegisterOptimizer::EmitNopForSourceInfo(
     BytecodeSourceInfo* source_info) const {
   DCHECK(source_info->is_valid());
   BytecodeNode nop(Bytecode::kNop, source_info);
   next_stage_->Write(&nop);
 }
 
 void BytecodeRegisterOptimizer::DoLdar(BytecodeNode* 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_ptr());
 }
 
 void BytecodeRegisterOptimizer::DoMov(BytecodeNode* 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);
+  RegisterInfo* output_info = GetRegisterInfo(output);
   RegisterTransfer(input_info, output_info, node->source_info_ptr());
 }
 
 void BytecodeRegisterOptimizer::DoStar(BytecodeNode* node) {
   Register output = GetRegisterOutputOperand(
       0, node->bytecode(), node->operands(), node->operand_count());
-  RegisterInfo* output_info = GetOrCreateRegisterInfo(output);
+  RegisterInfo* output_info = GetRegisterInfo(output);
   RegisterTransfer(accumulator_info_, output_info, node->source_info_ptr());
 }
 
 void BytecodeRegisterOptimizer::PrepareRegisterOutputOperand(
     RegisterInfo* reg_info) {
   if (reg_info->materialized()) {
     CreateMaterializedEquivalent(reg_info);
   }
   max_register_index_ =
       std::max(max_register_index_, reg_info->register_value().index());
   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);
+    RegisterInfo* reg_info = GetRegisterInfo(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);
+  RegisterInfo* reg_info = GetRegisterInfo(reg);
   if (reg_info->materialized()) {
     return reg;
   } else {
     RegisterInfo* equivalent_info =
         GetMaterializedEquivalentNotAccumulator(reg_info);
     return equivalent_info->register_value();
   }
 }
 
 void BytecodeRegisterOptimizer::PrepareRegisterInputOperand(
@@ skipping 88 matching lines @@
     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;
+  DCHECK_LT(index, register_info_table_.size());
+  return register_info_table_[index];
 }
 
 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);
+  if (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, 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);
+void BytecodeRegisterOptimizer::RegisterAllocateEvent(Register reg) {
+  GetOrCreateRegisterInfo(reg)->set_allocated(true);
+}
+
+void BytecodeRegisterOptimizer::RegisterListAllocateEvent(
+    RegisterList reg_list) {
+  if (reg_list.register_count() != 0) {
+    int first_index = reg_list.first_register().index();
+    GrowRegisterMap(Register(first_index + reg_list.register_count() - 1));
+    for (int i = 0; i < reg_list.register_count(); i++) {
+      GetRegisterInfo(Register(first_index + i))->set_allocated(true);
     }
-    info->MoveToNewEquivalenceSet(kInvalidEquivalenceId, false);
   }
 }
 
+void BytecodeRegisterOptimizer::RegisterListFreeEvent(RegisterList reg_list) {
+  int first_index = reg_list.first_register().index();
+  for (int i = 0; i < reg_list.register_count(); i++) {
+    GetRegisterInfo(Register(first_index + i))->set_allocated(false);
+  }
+}
+
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8