[turbofan] Variable liveness analysis for deopt

src/compiler/ast-graph-builder.cc

 // Copyright 2014 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/ast-graph-builder.h"
 
 #include "src/compiler.h"
 #include "src/compiler/ast-loop-assignment-analyzer.h"
 #include "src/compiler/control-builders.h"
 #include "src/compiler/linkage.h"
+#include "src/compiler/liveness-analyzer.h"
 #include "src/compiler/machine-operator.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/operator-properties.h"
 #include "src/full-codegen.h"
 #include "src/parser.h"
 #include "src/scopes.h"
 
 namespace v8 {
 namespace internal {
@@ skipping 365 matching lines @@
       jsgraph_(jsgraph),
       environment_(nullptr),
       ast_context_(nullptr),
       globals_(0, local_zone),
       execution_control_(nullptr),
       execution_context_(nullptr),
       try_nesting_level_(0),
       input_buffer_size_(0),
       input_buffer_(nullptr),
       exit_control_(nullptr),
-      loop_assignment_analysis_(loop) {
+      loop_assignment_analysis_(loop),
+      liveness_analyzer_(new (local_zone) LivenessAnalyzer(
+          static_cast<size_t>(info->scope()->num_stack_slots()), local_zone)) {
   InitializeAstVisitor(info->isolate(), local_zone);
 }
 
 
 Node* AstGraphBuilder::GetFunctionClosure() {
   if (!function_closure_.is_set()) {
     const Operator* op =
         common()->Parameter(Linkage::kJSFunctionCallClosureParamIndex);
     Node* node = NewNode(op, graph()->start());
     function_closure_.set(node);
@@ skipping 110 matching lines @@
 
   // Emit tracing call if requested to do so.
   if (FLAG_trace) {
     // TODO(mstarzinger): Only traces implicit return.
     Node* return_value = jsgraph()->UndefinedConstant();
     NewNode(javascript()->CallRuntime(Runtime::kTraceExit, 1), return_value);
   }
 
   // Return 'undefined' in case we can fall off the end.
   BuildReturn(jsgraph()->UndefinedConstant());
+
+  // Finish the basic structure of the graph.
+  environment()->UpdateControlDependency(exit_control());
+  graph()->SetEnd(NewNode(common()->End()));

[Michael Starzinger, 2015/03/01 21:00:56]

This duplicates the end node, please don't do this.

[Jarin, 2015/03/16 21:30:12]

Great catch, bad rebase. Done. 

+
+  // Compute local variable liveness information and use it to relax
+  // frame states.
+  RelaxFrameStatesWithLiveness();

[Michael Starzinger, 2015/03/01 21:00:56]

Rather move this call into CreateGraph() a few lines above.

[Jarin, 2015/03/16 21:30:12]

Done.

 }
 
 
+void AstGraphBuilder::RelaxFrameStatesWithLiveness() {
+  if (!FLAG_analyze_environment_liveness) return;
+
+  FrameStateRelaxer relaxer(jsgraph(), jsgraph()->UndefinedConstant(),
+                            liveness_analyzer()->local_count(), local_zone());
+  Variable* arguments = info()->scope()->arguments();
+  if (arguments != nullptr && arguments->IsStackAllocated()) {
+    relaxer.Blacklist(arguments->index());

[titzer, 2015/02/27 21:09:55]

Maybe "MarkPermanentlyLive(int index)" as a better name?

[Jarin, 2015/03/16 21:30:12]

Done.

+  }
+  liveness_analyzer()->Run(&relaxer);
+  if (FLAG_trace_environment_liveness) {
+    OFStream os(stdout);
+    liveness_analyzer()->Print(os);
+  }
+}
+
+
 // Left-hand side can only be a property, a global or a variable slot.
 enum LhsKind { VARIABLE, NAMED_PROPERTY, KEYED_PROPERTY };
 
 
 // Determine the left-hand side kind of an assignment.
 static LhsKind DetermineLhsKind(Expression* expr) {
   Property* property = expr->AsProperty();
   DCHECK(expr->IsValidReferenceExpression());
   LhsKind lhs_kind =
       (property == NULL) ? VARIABLE : (property->key()->IsPropertyName())
                                           ? NAMED_PROPERTY
                                           : KEYED_PROPERTY;
   return lhs_kind;
 }
 
 
 AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder,
                                           Scope* scope,
                                           Node* control_dependency)
     : builder_(builder),
       parameters_count_(scope->num_parameters() + 1),
       locals_count_(scope->num_stack_slots()),
+      liveness_block_(builder_->liveness_analyzer()->New()),
       values_(builder_->local_zone()),
       contexts_(builder_->local_zone()),
       control_dependency_(control_dependency),
       effect_dependency_(control_dependency),
       parameters_node_(nullptr),
       locals_node_(nullptr),
       stack_node_(nullptr) {
   DCHECK_EQ(scope->num_parameters() + 1, parameters_count());
 
   // Bind the receiver variable.
   Node* receiver = builder->graph()->NewNode(common()->Parameter(0),
                                              builder->graph()->start());
   values()->push_back(receiver);
 
   // Bind all parameter variables. The parameter indices are shifted by 1
   // (receiver is parameter index -1 but environment index 0).
   for (int i = 0; i < scope->num_parameters(); ++i) {
     Node* parameter = builder->graph()->NewNode(common()->Parameter(i + 1),
                                                 builder->graph()->start());
     values()->push_back(parameter);
   }
 
   // Bind all local variables to undefined.
   Node* undefined_constant = builder->jsgraph()->UndefinedConstant();
   values()->insert(values()->end(), locals_count(), undefined_constant);
 }
 
 
-AstGraphBuilder::Environment::Environment(
-    const AstGraphBuilder::Environment* copy)
+AstGraphBuilder::Environment::Environment(AstGraphBuilder::Environment* copy)
     : builder_(copy->builder_),
       parameters_count_(copy->parameters_count_),
       locals_count_(copy->locals_count_),
       values_(copy->zone()),
       contexts_(copy->zone()),
       control_dependency_(copy->control_dependency_),
       effect_dependency_(copy->effect_dependency_),
       parameters_node_(copy->parameters_node_),
       locals_node_(copy->locals_node_),
       stack_node_(copy->stack_node_) {
   const size_t kStackEstimate = 7;  // optimum from experimentation!
   values_.reserve(copy->values_.size() + kStackEstimate);
   values_.insert(values_.begin(), copy->values_.begin(), copy->values_.end());
   contexts_.reserve(copy->contexts_.size());
   contexts_.insert(contexts_.begin(), copy->contexts_.begin(),
                    copy->contexts_.end());
+
+  if (FLAG_analyze_environment_liveness) {
+    // Split the liveness blocks.
+    copy->liveness_block_ =
+        builder_->liveness_analyzer()->New(copy->liveness_block());
+    liveness_block_ =
+        builder_->liveness_analyzer()->New(copy->liveness_block());
+  }
 }
 
 
+void AstGraphBuilder::Environment::Bind(Variable* variable, Node* node) {
+  DCHECK(variable->IsStackAllocated());
+  if (variable->IsParameter()) {
+    values()->at(variable->index() + 1) = node;
+  } else {
+    DCHECK(variable->IsStackLocal());
+    values()->at(variable->index() + parameters_count_) = node;
+    if (FLAG_analyze_environment_liveness) {
+      liveness_block()->Bind(variable->index());
+    }
+  }
+}
+
+
+Node* AstGraphBuilder::Environment::Lookup(Variable* variable) {
+  DCHECK(variable->IsStackAllocated());
+  if (variable->IsParameter()) {
+    return values()->at(variable->index() + 1);
+  } else {
+    DCHECK(variable->IsStackLocal());
+    if (FLAG_analyze_environment_liveness) {
+      liveness_block()->Lookup(variable->index());
+    }
+    return values()->at(variable->index() + parameters_count_);
+  }
+}
+
+
+void AstGraphBuilder::Environment::MakeAllLocalsLive() {

[titzer, 2015/02/27 21:09:55]

Make -> Mark?

[Jarin, 2015/03/16 21:30:12]

Done.

+  if (FLAG_analyze_environment_liveness) {
+    for (int i = 0; i < locals_count_; i++) {
+      liveness_block()->Lookup(i);
+    }
+  }
+}
+
+
+AstGraphBuilder::Environment* AstGraphBuilder::Environment::Snapshot() {

[Michael Starzinger, 2015/03/02 10:56:34]

nit: How about s/Snapshot/CopyAndShareLiveness/ here, or anything else that
starts with the "Copy" prefix?

[Jarin, 2015/03/16 21:30:12]

Done.

+  Environment* env = new (zone()) Environment(this);
+  if (FLAG_analyze_environment_liveness) {
+    env->liveness_block_ = liveness_block();
+  }
+  return env;
+}
+
+
 void AstGraphBuilder::Environment::UpdateStateValues(Node** state_values,
                                                      int offset, int count) {
   bool should_update = false;
   Node** env_values = (count == 0) ? NULL : &values()->at(offset);
   if (*state_values == NULL || (*state_values)->InputCount() != count) {
     should_update = true;
   } else {
     DCHECK(static_cast<size_t>(offset + count) <= values()->size());
     for (int i = 0; i < count; i++) {
       if ((*state_values)->InputAt(i) != env_values[i]) {
@@ skipping 11 matching lines @@
 
 Node* AstGraphBuilder::Environment::Checkpoint(
     BailoutId ast_id, OutputFrameStateCombine combine) {
   UpdateStateValues(&parameters_node_, 0, parameters_count());
   UpdateStateValues(&locals_node_, parameters_count(), locals_count());
   UpdateStateValues(&stack_node_, parameters_count() + locals_count(),
                     stack_height());
 
   const Operator* op = common()->FrameState(JS_FRAME, ast_id, combine);
 
-  return graph()->NewNode(op, parameters_node_, locals_node_, stack_node_,
-                          builder()->current_context(),
-                          builder()->jsgraph()->UndefinedConstant());
+  Node* result = graph()->NewNode(op, parameters_node_, locals_node_,
+                                  stack_node_, builder()->current_context(),
+                                  builder()->jsgraph()->UndefinedConstant());
+  if (FLAG_analyze_environment_liveness) {
+    liveness_block()->Checkpoint(result);
+  }
+  return result;
 }
 
 
 AstGraphBuilder::AstContext::AstContext(AstGraphBuilder* own,
                                         Expression::Context kind)
     : kind_(kind), owner_(own), outer_(own->ast_context()) {
   owner()->set_ast_context(this);  // Push.
 #ifdef DEBUG
   original_height_ = environment()->stack_height();
 #endif
@@ skipping 639 matching lines @@
 
   // TODO(mstarzinger): Remove bailout once everything works.
   if (!FLAG_turbo_exceptions) SetStackOverflow();
 }
 
 
 void AstGraphBuilder::VisitDebuggerStatement(DebuggerStatement* stmt) {
   // TODO(turbofan): Do we really need a separate reloc-info for this?
   Node* node = NewNode(javascript()->CallRuntime(Runtime::kDebugBreak, 0));
   PrepareFrameState(node, stmt->DebugBreakId());
+  environment()->MakeAllLocalsLive();
 }
 
 
 void AstGraphBuilder::VisitFunctionLiteral(FunctionLiteral* expr) {
   Node* context = current_context();
 
   // Build a new shared function info if we cannot find one in the baseline
   // code. We also have a stack overflow if the recursive compilation did.
   expr->InitializeSharedInfo(handle(info()->shared_info()->code()));
   Handle<SharedFunctionInfo> shared_info = expr->shared_info();
@@ skipping 1748 matching lines @@
   DCHECK(contexts_.size() <= other->contexts_.size());
 
   // Nothing to do if the other environment is dead.
   if (other->IsMarkedAsUnreachable()) return;
 
   // Resurrect a dead environment by copying the contents of the other one and
   // placing a singleton merge as the new control dependency.
   if (this->IsMarkedAsUnreachable()) {
     Node* other_control = other->control_dependency_;
     Node* inputs[] = {other_control};
+    liveness_block_ = other->liveness_block_;
     control_dependency_ =
         graph()->NewNode(common()->Merge(1), arraysize(inputs), inputs, true);
     effect_dependency_ = other->effect_dependency_;
     values_ = other->values_;
     // TODO(titzer): make context stack heights match.
     size_t min = std::min(contexts_.size(), other->contexts_.size());
     contexts_ = other->contexts_;
     contexts_.resize(min, nullptr);
     return;
   }
 
+  // Record the merge for the local variable liveness calculation.
+  // Unfortunately, we have to mirror the logic in the MergeControl method:
+  // connect before merge or loop, or create a new merge otherwise.
+  if (FLAG_analyze_environment_liveness) {
+    if (GetControlDependency()->opcode() != IrOpcode::kLoop &&
+        GetControlDependency()->opcode() != IrOpcode::kMerge) {
+      liveness_block_ = builder_->liveness_analyzer()->New(liveness_block());
+    }
+    liveness_block()->AddPredecessor(other->liveness_block());
+  }
+
   // Create a merge of the control dependencies of both environments and update
   // the current environment's control dependency accordingly.
   Node* control = builder_->MergeControl(this->GetControlDependency(),
                                          other->GetControlDependency());
   UpdateControlDependency(control);
 
   // Create a merge of the effect dependencies of both environments and update
   // the current environment's effect dependency accordingly.
   Node* effect = builder_->MergeEffect(this->GetEffectDependency(),
                                        other->GetEffectDependency(), control);
@@ skipping 150 matching lines @@
     // Phi does not exist yet, introduce one.
     value = NewPhi(inputs, value, control);
     value->ReplaceInput(inputs - 1, other);
   }
   return value;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8