[interpreter] Faster and fewer flushes in 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 {
 
@@ skipping 30 matching lines @@
   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_;
@@ skipping 93 matching lines @@
     }
     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),
-      flushed_(false),
+      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
@@ skipping 19 matching lines @@
 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) {
-  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.
@@ skipping 43 matching lines @@
 
 // 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 (flushed_) {
+  if (!flush_required_) {
     return;
   }
 
-  // Materialize all live registers.
+  // 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->IsOnlyMemberOfEquivalenceSet() &&
-        !reg_info->materialized()) {
-      DCHECK(RegisterIsTemporary(reg_info->register_value()) ||
-             reg_info->register_value() == accumulator_);
-      Materialize(reg_info);
+    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);
+      }
     }
   }
 
-  // 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;
+  flush_required_ = false;
 }
 
 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);
@@ skipping 57 matching lines @@
   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)) {
-    output_info->AddToEquivalenceSetOf(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()) {
@@ skipping 214 matching lines @@
     if (info->materialized()) {
       CreateMaterializedEquivalent(info);
     }
     info->MoveToNewEquivalenceSet(kInvalidEquivalenceId, false);
   }
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8