[turbofan] Variable liveness analysis for deopt

src/compiler/ast-graph-builder.h

 // 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.
 
 #ifndef V8_COMPILER_AST_GRAPH_BUILDER_H_
 #define V8_COMPILER_AST_GRAPH_BUILDER_H_
 
 #include "src/ast.h"
 #include "src/compiler/js-graph.h"
 
 namespace v8 {
 namespace internal {
 
 class BitVector;
 
 namespace compiler {
 
 class ControlBuilder;
 class Graph;
+class LivenessAnalyzer;
+class LivenessAnalyzerBlock;
 class LoopAssignmentAnalysis;
 class LoopBuilder;
 class Node;
 
 // The AstGraphBuilder produces a high-level IR graph, based on an
 // underlying AST. The produced graph can either be compiled into a
 // stand-alone function or be wired into another graph for the purposes
 // of function inlining.
 class AstGraphBuilder : public AstVisitor {
  public:
@@ skipping 60 matching lines @@
   // Temporary storage for building node input lists.
   int input_buffer_size_;
   Node** input_buffer_;
 
   // Merge of all control nodes that exit the function body.
   Node* exit_control_;
 
   // Result of loop assignment analysis performed before graph creation.
   LoopAssignmentAnalysis* loop_assignment_analysis_;
 
+  // Analyzer of local variable liveness.
+  LivenessAnalyzer* liveness_analyzer_;
+
   // Growth increment for the temporary buffer used to construct input lists to
   // new nodes.
   static const int kInputBufferSizeIncrement = 64;
 
   Zone* local_zone() const { return local_zone_; }
   Environment* environment() const { return environment_; }
   AstContext* ast_context() const { return ast_context_; }
   ControlScope* execution_control() const { return execution_control_; }
   ContextScope* execution_context() const { return execution_context_; }
   CommonOperatorBuilder* common() const { return jsgraph_->common(); }
   CompilationInfo* info() const { return info_; }
   LanguageMode language_mode() const;
   JSGraph* jsgraph() { return jsgraph_; }
   Graph* graph() { return jsgraph_->graph(); }
   Zone* graph_zone() { return graph()->zone(); }
   JSOperatorBuilder* javascript() { return jsgraph_->javascript(); }
   ZoneVector<Handle<Object>>* globals() { return &globals_; }
   Scope* current_scope() const;
   Node* current_context() const;
   Node* exit_control() const { return exit_control_; }
+  LivenessAnalyzer* liveness_analyzer() { return liveness_analyzer_; }
 
   void set_environment(Environment* env) { environment_ = env; }
   void set_ast_context(AstContext* ctx) { ast_context_ = ctx; }
   void set_execution_control(ControlScope* ctrl) { execution_control_ = ctrl; }
   void set_execution_context(ContextScope* ctx) { execution_context_ = ctx; }
   void set_exit_control(Node* exit) { exit_control_ = exit; }
 
   // Create the main graph body by visiting the AST.
   void CreateGraphBody();
 
@@ skipping 125 matching lines @@
   // Builders for binary operations.
   Node* BuildBinaryOp(Node* left, Node* right, Token::Value op);
 
   // Builder for stack-check guards.
   Node* BuildStackCheck();
 
   // Check if the given statement is an OSR entry.
   // If so, record the stack height into the compilation and return {true}.
   bool CheckOsrEntry(IterationStatement* stmt);
 
+  // Computes local variable liveness and replaces dead variables in
+  // frame states with the undefined values.
+  void RelaxFrameStatesWithLiveness();

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

Can we use another word than "Relax", here and elsewhere? E.g. this method might
be better called "ClearNonLiveFrameStateSlots" or something similar.

+
   // Helper to wrap a Handle<T> into a Unique<T>.
   template <class T>
   Unique<T> MakeUnique(Handle<T> object) {
     return Unique<T>::CreateUninitialized(object);
   }
 
   Node** EnsureInputBufferSize(int size);
 
   // Named and keyed loads require a VectorSlotPair for successful lowering.
   VectorSlotPair CreateVectorSlotPair(FeedbackVectorICSlot slot) const;
@@ skipping 64 matching lines @@
   Environment(AstGraphBuilder* builder, Scope* scope, Node* control_dependency);
 
   int parameters_count() const { return parameters_count_; }
   int locals_count() const { return locals_count_; }
   int stack_height() {
     return static_cast<int>(values()->size()) - parameters_count_ -
            locals_count_;
   }
 
   // Operations on parameter or local variables. The parameter indices are
   // shifted by 1 (receiver is parameter index -1 but environment index 0).

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

nit: I think the second sentence in the comment makes more sense for the
implementation, not the interface. Can we move it to where the magic off-by one
calculation is performed?

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

Done.

-  void 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;
-    }
-  }
-  Node* Lookup(Variable* variable) {
-    DCHECK(variable->IsStackAllocated());
-    if (variable->IsParameter()) {
-      return values()->at(variable->index() + 1);
-    } else {
-      DCHECK(variable->IsStackLocal());
-      return values()->at(variable->index() + parameters_count_);
-    }
-  }
+  void Bind(Variable* variable, Node* node);
+  Node* Lookup(Variable* variable);
+  void MakeAllLocalsLive();
 
   Node* Context() const { return contexts_.back(); }
   void PushContext(Node* context) { contexts()->push_back(context); }
   void PopContext() { contexts()->pop_back(); }
 
   // Operations on the operand stack.
   void Push(Node* node) {
     values()->push_back(node);
   }
   Node* Top() {
@@ skipping 61 matching lines @@
   // Copies this environment to a potentially unreachable control-flow point.
   Environment* CopyAsUnreachable() {
     Environment* env = Copy();
     env->MarkAsUnreachable();
     return env;
   }
 
   // Copies this environment at a loop header control-flow point.
   Environment* CopyForLoop(BitVector* assigned, bool is_osr = false) {
     PrepareForLoop(assigned, is_osr);
-    return Copy();
+    return Snapshot();
   }
 
   int ContextStackDepth() { return static_cast<int>(contexts_.size()); }
 
  private:
   AstGraphBuilder* builder_;
   int parameters_count_;
   int locals_count_;
+  LivenessAnalyzerBlock* liveness_block_;
   NodeVector values_;
   NodeVector contexts_;
   Node* control_dependency_;
   Node* effect_dependency_;
   Node* parameters_node_;
   Node* locals_node_;
   Node* stack_node_;
 
-  explicit Environment(const Environment* copy);
+  explicit Environment(Environment* copy);
   Environment* Copy() { return new (zone()) Environment(this); }
+  Environment* Snapshot();
   void UpdateStateValues(Node** state_values, int offset, int count);
   Zone* zone() const { return builder_->local_zone(); }
   Graph* graph() const { return builder_->graph(); }
   AstGraphBuilder* builder() const { return builder_; }
   CommonOperatorBuilder* common() { return builder_->common(); }
   NodeVector* values() { return &values_; }
   NodeVector* contexts() { return &contexts_; }
+  LivenessAnalyzerBlock* liveness_block() { return liveness_block_; }
 
   // Prepare environment to be used as loop header.
   void PrepareForLoop(BitVector* assigned, bool is_osr = false);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_