[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 69 matching lines @@
 
   return nullptr;
 }
 
 BytecodeRegisterOptimizer::RegisterInfo*
 BytecodeRegisterOptimizer::RegisterInfo::GetEquivalentToMaterialize() {
   DCHECK(this->materialized());
   RegisterInfo* visitor = this->next_;
   RegisterInfo* best_info = nullptr;
   while (visitor != this) {
     if (visitor->materialized()) {

[mythria, 2016/09/28 11:45:29]

I am not sure I understand it fully, but what would happen if this was a
unallocated register that was materialized. We can reuse it and there will be a
register create event which will just move it out of this equivalence set. There
may be allocated registers which should have got materialized in this call, but
this check might prevent it. Should we have visitor->materialized() &&
visitor->allocated() here? 

[rmcilroy, 2016/09/30 08:37:54]

As discussed offline, yes we can reuse it even if unallocated, since nothing has
overridden it yet.

       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);
+  }

[mythria, 2016/09/28 11:45:29]

If I understand correctly, the idea here is that, we retain an unallocated
register in the equivalent set and hope to use its value. Is that the reason we
don't remove it from the existing equivalence set. I also don't understand why
we don't need to materialize some other register in that set. I mean why don't
we need CreateMaterializedEquivalent(info) here?

[rmcilroy, 2016/09/30 08:37:54]

As discussed offline, we don't need to materialize another register because that
will be done whenever the register get's used again after being reallocated, and
the value is fine in this register until then.

+}
+
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8