[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
     // 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_) {
+  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->IsOnlyMemberOfEquivalenceSet() || !reg_info->materialized()) {
+      continue;

[rmcilroy, 2016/06/02 12:51:33]

nit - could you add a comment here that you are skipping non-materialized reg
info, and they will be materialized when a materialized equivalent is reached.

[oth, 2016/06/02 14:14:24]

Done.

+    }
+
+    // Walk equivalents of this materialized register, materializing
+    // each equivalent if necessary and moving to own equivalent 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;
 }
 
 // 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.
@@ skipping 108 matching lines @@
     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);
+    flush_required_ = true;

[rmcilroy, 2016/06/02 12:51:34]

This scares me a bit since if we add another call to ddToEquivalenceSetOf
somewhere else and forget the flush_required_ things will break. Maybe add a
helper function which does both operations and call this from here?

[oth, 2016/06/02 14:14:24]

Done.

If flushes aren't correctly emitted many tests fail. 

We've consciously made a common path for the register transfer bytecodes so I'm
unclear why we'd ever have another path doing this operation.

[rmcilroy, 2016/06/02 15:07:13]

Acknowledged, I'm fine with this if you are.

   }
 
   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