[turbofan] Sparse representation for state values

src/compiler/bytecode-graph-builder.cc

 // Copyright 2015 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/compiler/bytecode-graph-builder.h"
 
 #include "src/ast/ast.h"
 #include "src/ast/scopes.h"
 #include "src/compilation-info.h"
 #include "src/compiler/compiler-source-position-table.h"
@@ skipping 64 matching lines @@
   void PrepareForOsrEntry();
 
   void PrepareForLoopExit(Node* loop);
 
  private:
   explicit Environment(const Environment* copy);
   void PrepareForLoop();
 
   bool StateValuesRequireUpdate(Node** state_values, Node** values, int count);
   void UpdateStateValues(Node** state_values, Node** values, int count);
-  void UpdateStateValuesWithCache(Node** state_values, Node** values,
-                                  int count);
+  void UpdateStateValuesWithCache(Node** state_values, Node** values, int count,
+                                  const BitVector* liveness);
 
   int RegisterToValuesIndex(interpreter::Register the_register) const;
 
   Zone* zone() const { return builder_->local_zone(); }
   Graph* graph() const { return builder_->graph(); }
   CommonOperatorBuilder* common() const { return builder_->common(); }
   BytecodeGraphBuilder* builder() const { return builder_; }
   const NodeVector* values() const { return &values_; }
   NodeVector* values() { return &values_; }
   int register_base() const { return register_base_; }
   int accumulator_base() const { return accumulator_base_; }
 
   BytecodeGraphBuilder* builder_;
   int register_count_;
   int parameter_count_;
   Node* context_;
   Node* control_dependency_;
   Node* effect_dependency_;
   NodeVector values_;
   Node* parameters_state_values_;
   Node* registers_state_values_;
   Node* accumulator_state_values_;
   int register_base_;
   int accumulator_base_;
-
-  // A working area for writing maybe-dead values to when updating the state
-  // values for registers.
-  NodeVector state_value_working_area_;
 };
 
 
 // Issues:
 // - Scopes - intimately tied to AST. Need to eval what is needed.
 // - Need to resolve closure parameter treatment.
 BytecodeGraphBuilder::Environment::Environment(BytecodeGraphBuilder* builder,
                                                int register_count,
                                                int parameter_count,
                                                Node* control_dependency,
                                                Node* context)
     : builder_(builder),
       register_count_(register_count),
       parameter_count_(parameter_count),
       context_(context),
       control_dependency_(control_dependency),
       effect_dependency_(control_dependency),
       values_(builder->local_zone()),
       parameters_state_values_(nullptr),
       registers_state_values_(nullptr),
-      accumulator_state_values_(nullptr),
-      state_value_working_area_(builder->local_zone()) {
+      accumulator_state_values_(nullptr) {
   // The layout of values_ is:
   //
   // [receiver] [parameters] [registers] [accumulator]
   //
   // parameter[0] is the receiver (this), parameters 1..N are the
   // parameters supplied to the method (arg0..argN-1). The accumulator
   // is stored separately.
 
   // Parameters including the receiver
   for (int i = 0; i < parameter_count; i++) {
     const char* debug_name = (i == 0) ? "%this" : nullptr;
     const Operator* op = common()->Parameter(i, debug_name);
     Node* parameter = builder->graph()->NewNode(op, graph()->start());
     values()->push_back(parameter);
   }
 
   // Registers
   register_base_ = static_cast<int>(values()->size());
   Node* undefined_constant = builder->jsgraph()->UndefinedConstant();
   values()->insert(values()->end(), register_count, undefined_constant);
 
   // Accumulator
   accumulator_base_ = static_cast<int>(values()->size());
   values()->push_back(undefined_constant);
-
-  state_value_working_area_.resize(register_count_);
 }
 
 BytecodeGraphBuilder::Environment::Environment(
     const BytecodeGraphBuilder::Environment* other)
     : builder_(other->builder_),
       register_count_(other->register_count_),
       parameter_count_(other->parameter_count_),
       context_(other->context_),
       control_dependency_(other->control_dependency_),
       effect_dependency_(other->effect_dependency_),
       values_(other->zone()),
       parameters_state_values_(nullptr),
       registers_state_values_(nullptr),
       accumulator_state_values_(nullptr),
       register_base_(other->register_base_),
-      accumulator_base_(other->accumulator_base_),
-      // Environments can share their working area.
-      state_value_working_area_(other->state_value_working_area_) {
+      accumulator_base_(other->accumulator_base_) {
   values_ = other->values_;
 }
 
 
 int BytecodeGraphBuilder::Environment::RegisterToValuesIndex(
     interpreter::Register the_register) const {
   if (the_register.is_parameter()) {
     return the_register.ToParameterIndex(parameter_count());
   } else {
     return the_register.index() + register_base();
@@ skipping 200 matching lines @@
     Node* rename =
         graph()->NewNode(common()->LoopExitValue(), values_[i], loop_exit);
     values_[i] = rename;
   }
 }
 
 void BytecodeGraphBuilder::Environment::UpdateStateValues(Node** state_values,
                                                           Node** values,
                                                           int count) {
   if (StateValuesRequireUpdate(state_values, values, count)) {
-    const Operator* op = common()->StateValues(count);
+    const Operator* op = common()->StateValues(count, SparseInputMask::Dense());
     (*state_values) = graph()->NewNode(op, count, values);
   }
 }
 
 void BytecodeGraphBuilder::Environment::UpdateStateValuesWithCache(
-    Node** state_values, Node** values, int count) {
+    Node** state_values, Node** values, int count, const BitVector* liveness) {
   *state_values = builder_->state_values_cache_.GetNodeForValues(
-      values, static_cast<size_t>(count));
+      values, static_cast<size_t>(count), liveness);
 }
 
 Node* BytecodeGraphBuilder::Environment::Checkpoint(
     BailoutId bailout_id, OutputFrameStateCombine combine,
     bool owner_has_exception, const BytecodeLivenessState* liveness) {
   UpdateStateValues(&parameters_state_values_, &values()->at(0),
                     parameter_count());
 
-  if (liveness) {
-    Node* optimized_out = builder()->jsgraph()->OptimizedOutConstant();
+  // TODO(leszeks): We should pass a view of the liveness bitvector here, with
+  // offset and count, rather than passing the entire bitvector and assuming
+  // that register liveness starts at offset 0.
+  UpdateStateValuesWithCache(&registers_state_values_,
+                             &values()->at(register_base()), register_count(),
+                             liveness ? &liveness->bit_vector() : nullptr);
 
-    for (int i = 0; i < register_count(); ++i) {
-      state_value_working_area_[i] = liveness->RegisterIsLive(i)
-                                         ? values()->at(register_base() + i)
-                                         : optimized_out;
-    }
-
-    Node* accumulator_value = liveness->AccumulatorIsLive()
-                                  ? values()->at(accumulator_base())
-                                  : optimized_out;
-
-    UpdateStateValuesWithCache(&registers_state_values_,
-                               state_value_working_area_.data(),
-                               register_count());
-
-    UpdateStateValues(&accumulator_state_values_, &accumulator_value, 1);
-  } else {
-    UpdateStateValuesWithCache(&registers_state_values_,
-                               &values()->at(register_base()),
-                               register_count());
-    UpdateStateValues(&accumulator_state_values_,
-                      &values()->at(accumulator_base()), 1);
-  }
+  Node* accumulator_value = liveness == nullptr || liveness->AccumulatorIsLive()
+                                ? values()->at(accumulator_base())
+                                : builder()->jsgraph()->OptimizedOutConstant();
+  UpdateStateValues(&accumulator_state_values_, &accumulator_value, 1);
 
   const Operator* op = common()->FrameState(
       bailout_id, combine, builder()->frame_state_function_info());
   Node* result = graph()->NewNode(
       op, parameters_state_values_, registers_state_values_,
       accumulator_state_values_, Context(), builder()->GetFunctionClosure(),
       builder()->graph()->start());
 
   return result;
 }
@@ skipping 1783 matching lines @@
         it->source_position().ScriptOffset(), start_position_.InliningId()));
     it->Advance();
   } else {
     DCHECK_GT(it->code_offset(), offset);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8