Liveness analysis for environment slots in Hydrogen

src/hydrogen.h

Index: src/hydrogen.h
diff --git a/src/hydrogen.h b/src/hydrogen.h
index b053fc71c5fc33fbd449da41eadfb18e5cb4db4f..ade676b51f350a7baf3494675561c1f536e401f3 100644
--- a/src/hydrogen.h
+++ b/src/hydrogen.h
@@ -67,7 +67,6 @@ class HBasicBlock: public ZoneObject {
   HInstruction* first() const { return first_; }
   HInstruction* last() const { return last_; }
   void set_last(HInstruction* instr) { last_ = instr; }
-  HInstruction* GetLastInstruction();
   HControlInstruction* end() const { return end_; }
   HLoopInformation* loop_information() const { return loop_information_; }
   const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
@@ -112,7 +111,7 @@ class HBasicBlock: public ZoneObject {
   void SetInitialEnvironment(HEnvironment* env);
   void ClearEnvironment() { last_environment_ = NULL; }
   bool HasEnvironment() const { return last_environment_ != NULL; }
-  void UpdateEnvironment(HEnvironment* env) { last_environment_ = env; }
+  void UpdateEnvironment(HEnvironment* env);
   HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
 
   void set_parent_loop_header(HBasicBlock* block) {
@@ -156,7 +155,11 @@ class HBasicBlock: public ZoneObject {
   // Simulate (caller's environment)
   // Goto (target block)
   bool IsInlineReturnTarget() const { return is_inline_return_target_; }
-  void MarkAsInlineReturnTarget() { is_inline_return_target_ = true; }
+  void MarkAsInlineReturnTarget(HBasicBlock* enter_inlined_block) {

[titzer, 2013/05/23 12:34:55]

This name is somewhat difficult to parse. Is this the first block of the inlined
method? If so, inlined_entry_block might be a better name.

[Jakob Kummerow, 2013/05/24 09:49:35]

Done. (It's the block containing the HEnterInlined. We don't start a new block
when inlining.)

+    is_inline_return_target_ = true;
+    enter_inlined_block_ = enter_inlined_block;
+  }
+  HBasicBlock* enter_inlined_block() { return enter_inlined_block_; }
 
   bool IsDeoptimizing() const { return is_deoptimizing_; }
   void MarkAsDeoptimizing() { is_deoptimizing_ = true; }
@@ -199,10 +202,12 @@ class HBasicBlock: public ZoneObject {
   int last_instruction_index_;
   ZoneList<int> deleted_phis_;
   HBasicBlock* parent_loop_header_;
-  bool is_inline_return_target_;
-  bool is_deoptimizing_;
-  bool dominates_loop_successors_;
-  bool is_osr_entry_;
+  // For blocks marked as inline return target: the block with HEnterInlined.
+  HBasicBlock* enter_inlined_block_;
+  bool is_inline_return_target_ : 1;
+  bool is_deoptimizing_ : 1;
+  bool dominates_loop_successors_ : 1;
+  bool is_osr_entry_ : 1;
 };
 
 
@@ -286,6 +291,7 @@ class HGraph: public ZoneObject {
   void RestoreActualValues();
   void DeadCodeElimination(const char *phase_name);
   void PropagateDeoptimizingMark();
+  void EnvironmentLivenessAnalysis();
 
   // Returns false if there are phi-uses of the arguments-object
   // which are not supported by the optimizing compiler.
@@ -363,6 +369,12 @@ class HGraph: public ZoneObject {
     return type_change_checksum_;
   }
 
+  void update_biggest_environment_ever(int environment_size) {

[titzer, 2013/05/23 12:34:55]

Cute name, but "maximum_environment_size" would also work.

[Jakob Kummerow, 2013/05/24 09:49:35]

Done.

+    if (environment_size > biggest_environment_ever_) {
+      biggest_environment_ever_ = environment_size;
+    }
+  }
+
   bool use_optimistic_licm() {
     return use_optimistic_licm_;
   }
@@ -411,6 +423,7 @@ class HGraph: public ZoneObject {
   void MarkLive(HValue* ref, HValue* instr, ZoneList<HValue*>* worklist);
   void MarkLiveInstructions();
   void RemoveDeadInstructions();
+  void ZapEnvironmentSlot(int index, HSimulate* simulate);

[titzer, 2013/05/23 12:34:55]

Maybe "Kill" or "Null" or "Remove"?

[Jakob Kummerow, 2013/05/24 09:49:35]

We use "zap" in other places, so I'd like to keep the name.

   void MarkAsDeoptimizingRecursively(HBasicBlock* block);
   void NullifyUnreachableInstructions();
   void InsertTypeConversions(HInstruction* instr);
@@ -460,6 +473,7 @@ class HGraph: public ZoneObject {
   bool has_soft_deoptimize_;
   bool depends_on_empty_array_proto_elements_;
   int type_change_checksum_;
+  int biggest_environment_ever_;
 
   DISALLOW_COPY_AND_ASSIGN(HGraph);
 };
@@ -521,6 +535,10 @@ class HEnvironment: public ZoneObject {
     return parameter_count() + specials_count() + local_count();
   }
 
+  int first_local_index() const {
+    return parameter_count() + specials_count();
+  }
+
   void Bind(Variable* variable, HValue* value) {
     Bind(IndexFor(variable), value);
   }
@@ -618,6 +636,22 @@ class HEnvironment: public ZoneObject {
     values_[index] = value;
   }
 
+  // Map a variable to an environment index.  Parameter indices are shifted
+  // by 1 (receiver is parameter index -1 but environment index 0).
+  // Stack-allocated local indices are shifted by the number of parameters.
+  int IndexFor(Variable* variable) const {
+    ASSERT(variable->IsStackAllocated());
+    int shift = variable->IsParameter()
+        ? 1
+        : parameter_count_ + specials_count_;
+    return variable->index() + shift;
+  }
+
+  bool is_local_index(int i) const {
+    return i >= first_local_index() &&
+           i < first_expression_index();
+  }
+
   void PrintTo(StringStream* stream);
   void PrintToStd();
 
@@ -645,17 +679,6 @@ class HEnvironment: public ZoneObject {
   void Initialize(int parameter_count, int local_count, int stack_height);
   void Initialize(const HEnvironment* other);
 
-  // Map a variable to an environment index.  Parameter indices are shifted
-  // by 1 (receiver is parameter index -1 but environment index 0).
-  // Stack-allocated local indices are shifted by the number of parameters.
-  int IndexFor(Variable* variable) const {
-    ASSERT(variable->IsStackAllocated());
-    int shift = variable->IsParameter()
-        ? 1
-        : parameter_count_ + specials_count_;
-    return variable->index() + shift;
-  }
-
   Handle<JSFunction> closure_;
   // Value array [parameters] [specials] [locals] [temporaries].
   ZoneList<HValue*> values_;
@@ -1535,6 +1558,32 @@ class HOptimizedGraphBuilder: public HGraphBuilder, public AstVisitor {
   HValue* Top() const { return environment()->Top(); }
   void Drop(int n) { environment()->Drop(n); }
   void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
+  bool IsEligibleForEnvironmentLivenessAnalysis(Variable* var,
+                                                int index,
+                                                HEnvironment* env) {
+    // |this| and |arguments| are always live; zapping parameters isn't
+    // safe because function.arguments can inspect them at any time.
+    return !var->is_this() &&
+           !var->is_arguments() &&
+           env->is_local_index(index);
+  }
+  void BindIfLive(Variable* var, HValue* value) {
+    HEnvironment* env = environment();
+    int index = env->IndexFor(var);
+    env->Bind(index, value);
+    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, env)) {
+      AddInstruction(new(zone()) HEnvironmentBind(index));
+    }
+  }
+  HValue* LookupAndMakeLive(Variable* var) {
+    HEnvironment* env = environment();
+    int index = env->IndexFor(var);
+    HValue* value = env->Lookup(index);
+    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, env)) {
+      AddInstruction(new(zone()) HEnvironmentLookup(index));
+    }
+    return value;
+  }
 
   // The value of the arguments object is allowed in some but not most value
   // contexts.  (It's allowed in all effect contexts and disallowed in all