[turbofan] Variable liveness analysis for deopt

src/compiler/ast-graph-builder.cc

Index: src/compiler/ast-graph-builder.cc
diff --git a/src/compiler/ast-graph-builder.cc b/src/compiler/ast-graph-builder.cc
index b6c6e0fb3f5bc1a0f396d178d09931f978332bda..24f6c0cfb1ebe8a2ab4c11c4f6d47c29b1aaf54b 100644
--- a/src/compiler/ast-graph-builder.cc
+++ b/src/compiler/ast-graph-builder.cc
@@ -8,6 +8,7 @@
 #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"
@@ -393,7 +394,9 @@ AstGraphBuilder::AstGraphBuilder(Zone* local_zone, CompilationInfo* info,
       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);
 }
 
@@ -524,6 +527,31 @@ void AstGraphBuilder::CreateGraphBody() {
 
   // 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);
+  }
 }
 
 
@@ -549,6 +577,7 @@ AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder,
     : 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),
@@ -577,8 +606,7 @@ AstGraphBuilder::Environment::Environment(AstGraphBuilder* builder,
 }
 
 
-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_),
@@ -595,6 +623,60 @@ AstGraphBuilder::Environment::Environment(
   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;
 }
 
 
@@ -629,9 +711,13 @@ Node* AstGraphBuilder::Environment::Checkpoint(
 
   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;
 }
 
 
@@ -1291,6 +1377,7 @@ 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();
 }
 
 
@@ -3059,6 +3146,7 @@ void AstGraphBuilder::Environment::Merge(Environment* other) {
   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_;
@@ -3070,6 +3158,17 @@ void AstGraphBuilder::Environment::Merge(Environment* other) {
     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(),