Liveness analysis for environment slots in Hydrogen

src/hydrogen.cc

Index: src/hydrogen.cc
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index b53e9b514e78ab19fe140422a23c1fb303809fa1..bf1bca45ccc30d7475a2163d81bd9f39f9c09ce4 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -71,6 +71,7 @@ HBasicBlock::HBasicBlock(HGraph* graph)
       last_instruction_index_(-1),
       deleted_phis_(4, graph->zone()),
       parent_loop_header_(NULL),
+      enter_inlined_block_(NULL),
       is_inline_return_target_(false),
       is_deoptimizing_(false),
       dominates_loop_successors_(false),
@@ -130,10 +131,13 @@ HDeoptimize* HBasicBlock::CreateDeoptimize(
     HDeoptimize::UseEnvironment has_uses) {
   ASSERT(HasEnvironment());
   if (has_uses == HDeoptimize::kNoUses)
-    return new(zone()) HDeoptimize(0, zone());
+    return new(zone()) HDeoptimize(0, 0, 0, zone());
 
   HEnvironment* environment = last_environment();
-  HDeoptimize* instr = new(zone()) HDeoptimize(environment->length(), zone());
+  int first_local_index = environment->first_local_index();
+  int first_expression_index = environment->first_expression_index();
+  HDeoptimize* instr = new(zone()) HDeoptimize(
+      environment->length(), first_local_index, first_expression_index, zone());
   for (int i = 0; i < environment->length(); i++) {
     HValue* val = environment->values()->at(i);
     instr->AddEnvironmentValue(val, zone());
@@ -192,7 +196,7 @@ void HBasicBlock::Goto(HBasicBlock* block,
 
   if (block->IsInlineReturnTarget()) {
     AddInstruction(new(zone()) HLeaveInlined());
-    last_environment_ = last_environment()->DiscardInlined(drop_extra);
+    UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
   }
 
   if (add_simulate) AddSimulate(BailoutId::None());
@@ -209,7 +213,7 @@ void HBasicBlock::AddLeaveInlined(HValue* return_value,
   ASSERT(target->IsInlineReturnTarget());
   ASSERT(return_value != NULL);
   AddInstruction(new(zone()) HLeaveInlined());
-  last_environment_ = last_environment()->DiscardInlined(drop_extra);
+  UpdateEnvironment(last_environment()->DiscardInlined(drop_extra));
   last_environment()->Push(return_value);
   AddSimulate(BailoutId::None());
   HGoto* instr = new(zone()) HGoto(target);
@@ -224,6 +228,12 @@ void HBasicBlock::SetInitialEnvironment(HEnvironment* env) {
 }
 
 
+void HBasicBlock::UpdateEnvironment(HEnvironment* env) {
+  last_environment_ = env;
+  graph()->update_biggest_environment_ever(env->first_expression_index());
+}
+
+
 void HBasicBlock::SetJoinId(BailoutId ast_id) {
   int length = predecessors_.length();
   ASSERT(length > 0);
@@ -731,8 +741,7 @@ HInstruction* HGraphBuilder::IfBuilder::IfCompare(
 HInstruction* HGraphBuilder::IfBuilder::IfCompareMap(HValue* left,
                                                      Handle<Map> map) {
   HCompareMap* compare =
-      new(zone()) HCompareMap(left, map,
-                              first_true_block_, first_false_block_);
+      new(zone()) HCompareMap(left, map, first_true_block_, first_false_block_);
   AddCompare(compare);
   return compare;
 }
@@ -811,9 +820,14 @@ void HGraphBuilder::IfBuilder::Then() {
   did_then_ = true;
   if (needs_compare_) {
     // Handle if's without any expressions, they jump directly to the "else"
-    // branch.
-    builder_->current_block()->GotoNoSimulate(first_false_block_);
-    first_true_block_ = NULL;
+    // branch. However, we must pretend that the "then" branch is reachable.

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

Why must we pretend that it's reachable?

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

So that the graph builder visits it and any environment lookups inside it. I've
updated the comment.

+    HConstant* constant_false = builder_->graph()->GetConstantFalse();
+    ToBooleanStub::Types boolean_type = ToBooleanStub::no_types();
+    boolean_type.Add(ToBooleanStub::BOOLEAN);
+    HBranch* branch =
+        new(zone()) HBranch(constant_false, first_true_block_,
+                            first_false_block_, boolean_type);
+    builder_->current_block()->Finish(branch);
   }
   builder_->set_current_block(first_true_block_);
 }
@@ -2103,7 +2117,8 @@ HGraph::HGraph(CompilationInfo* info)
       use_optimistic_licm_(false),
       has_soft_deoptimize_(false),
       depends_on_empty_array_proto_elements_(false),
-      type_change_checksum_(0) {
+      type_change_checksum_(0),
+      biggest_environment_ever_(0) {
   if (info->IsStub()) {
     HydrogenCodeStub* stub = info->code_stub();
     CodeStubInterfaceDescriptor* descriptor =
@@ -2486,6 +2501,177 @@ void HGraph::AssignDominators() {
 }
 
 
+void HGraph::ZapEnvironmentSlot(int index, HSimulate* simulate) {
+  int operand_index = simulate->ToOperandIndex(index);
+  if (operand_index == -1) {
+    simulate->AddAssignedValue(index, GetConstantUndefined());
+  } else {
+    simulate->SetOperandAt(operand_index, GetConstantUndefined());
+  }
+}
+
+
+void HGraph::EnvironmentLivenessAnalysis() {
+  HPhase phase("H_EnvironmentLivenessAnalysis", this);
+  if (biggest_environment_ever_ == 0) return;
+  int block_count = blocks()->length();
+  ZoneList<BitVector*> live_at_block_start(block_count, zone());
+  ZoneList<HSimulate*> first_simulate(block_count, zone());
+  BitVector* worklist = new(zone()) BitVector(block_count, zone());
+  for (int i = 0; i < block_count; ++i) {
+    live_at_block_start.Add(
+        new(zone()) BitVector(biggest_environment_ever_, zone()),
+        zone());
+    first_simulate.Add(NULL, zone());
+    worklist->Add(i);
+  }
+
+  // Liveness analysis of environment slots: visit blocks in reverse order,
+  // walk backwards through each block. We need several passes to propagate
+  // liveness through nested loops correctly.
+  // During the main iteration, compute liveness of environment slots, and
+  // store it for each block until it doesn't change any more.
+  // Then, in a last pass, zap dead environment slots, and remove the
+  // HEnvironment{Bind,Lookup} markers.
+  enum Pass { kIterateUntilFixedPoint, kLastPass, kDone };
+  Pass pass = kIterateUntilFixedPoint;
+  BitVector live(biggest_environment_ever_, zone());
+  while (pass != kDone) {

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

I realize there are some tricky cases inside this loop, but this enum / pass
flag that completely changes the loop behavior is way too complication. Please
extract this to two or three loops and loop-unswitch this code.

+    for (int block_id = block_count - 1; block_id >= 0; --block_id) {
+      if (pass == kIterateUntilFixedPoint && !worklist->Contains(block_id)) {

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

Your loop goes through the block order backwards. No problem. Any order would
work. Luckily the block order has been computed carefully in the previous phases
to match reverse-post order, thus making this loop efficient. Nevertheless your
main loop loops over all the blocks each time. The first time it will visit each
block, but then subsequent iterations (because of loops) will be sparse. 

I am not sure if now is the right time for a helper iterator, but we do seem to
be iterating manually in various order all over the place in the code. If we
have other backwards dataflow problems, we might consider either repurposing or
generalizing the PostorderProcessor to help here.

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

I'm explicitly going backwards in order to reduce the number of needed
iterations.
I'd prefer not to add any unrelated refactorings to this CL (and, frankly, I'm
not convinced we need a generic helper iterator. Ordering blocks once should be
quite sufficient.)

+        continue;
+      }
+      worklist->Remove(block_id);
+
+      // Liveness at the end of each block: union of liveness in successors.
+      live.Clear();
+      HBasicBlock* block = blocks()->at(block_id);
+      for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
+        live.Union(*live_at_block_start[it.Current()->block_id()]);
+      }
+
+      if (pass == kLastPass) {
+        // When a value is live in successor A but dead in B, we must
+        // explicitly zap it in B.
+        for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
+          HBasicBlock* successor = it.Current();
+          int successor_id = successor->block_id();
+          BitVector* live_in_successor = live_at_block_start[successor_id];
+          if (live_in_successor->Equals(live)) continue;
+          // Find the first simulate in the successor block.
+          HSimulate* simulate = NULL;
+          HInstruction* current = successor->first();
+          while (current != NULL && simulate == NULL) {
+            if (current->IsSimulate()) simulate = HSimulate::cast(current);
+            if (current->IsLeaveInlined()) break;
+            // No need to check for EnterInlined, because there's always
+            // a simulate before an EnterInlined.

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

Scary and brittle, and no ASSERT.

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

ASSERT added.

+            current = current->next();
+          }
+          if (simulate == NULL) continue;
+          for (int i = 0; i < live.length(); ++i) {
+            if (!live.Contains(i)) continue;
+            if (live_in_successor->Contains(i)) continue;
+            ZapEnvironmentSlot(i, simulate);
+          }
+        }
+      }
+
+      // Walk the block.
+      HInstruction* instr = block->last();
+      HInstruction* next = instr->previous();
+      HSimulate* last_simulate = NULL;
+      while (instr != NULL) {
+        if (instr->IsEnvironmentLookup()) {
+          // Begins an environment slot's live range.
+          HEnvironmentLookup* lookup = HEnvironmentLookup::cast(instr);
+          int index = lookup->index();
+          if (pass == kLastPass &&
+              !live.Contains(index) && last_simulate != NULL) {
+            // The Simulate following the point where the environment value
+            // dies is extended or modified to zap that value's slot.
+            ZapEnvironmentSlot(index, last_simulate);
+          }
+          live.Add(index);
+          if (pass == kLastPass) lookup->DeleteAndReplaceWith(NULL);
+        } else if (instr->IsEnvironmentBind()) {
+          // Ends an environment slot's live range.
+          HEnvironmentBind* bind = HEnvironmentBind::cast(instr);
+          int index = bind->index();
+          if (pass == 2 && !live.Contains(index) && last_simulate != NULL) {
+            // Don't bother binding this value if it's never looked up.
+            ZapEnvironmentSlot(index, last_simulate);
+          }
+          live.Remove(index);
+          if (pass == kLastPass) bind->DeleteAndReplaceWith(NULL);
+        } else if (instr->IsLeaveInlined()) {
+          // No environment values are live at the end of an inlined section.
+          live.Clear();
+          // Simulates are tied to environments, so last_simulate cannot be
+          // used for what comes next.
+          last_simulate = NULL;
+        } else if (instr->IsEnterInlined()) {

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

There is considerably more going on here than meets the eye; you are doing
liveness analysis on different environments for different inlined methods. This
currently works because you are only using the environment bind and environment
lookup as essentially reads and writes and thankfully before any other
optimizations happen, code from different inlined methods is not mixed up into
the same basic blocks. I am not sure if this would hold if the order of this
phase were changed. Also, below you are making assumptions about what order
instructions will appear in inlined methods. This makes this phase brittle and
restricts changes in other phases. Please consider ways to relax these
restrictions, or do something conservative when they do not hold.

+          HEnterInlined* enter = HEnterInlined::cast(instr);
+          // Those environment values are live that are live at any return
+          // target block. Here we make use of the fact that the end of an
+          // inline sequence always looks like this: HLeaveInlined, HSimulate,
+          // HGoto (to return_target block), with no environment lookups in
+          // between.
+          live.Clear();
+          for (int j = 0; j < enter->return_targets()->length(); ++j) {
+            int return_id = enter->return_targets()->at(j)->block_id();
+            // When an AbnormalExit is involved, it can happen that the return
+            // target block doesn't actually exist.
+            if (return_id < block_count) {
+              live.Union(*live_at_block_start[return_id]);
+            }
+          }
+          if (pass == kLastPass &&
+              enter->return_targets()->length() == 1 &&
+              enter->return_targets()->at(0)->block_id() < block_count) {
+            last_simulate =
+                first_simulate.at(enter->return_targets()->at(0)->block_id());
+          } else {
+            // Out of luck. We're inlining at a control flow split;
+            // if we wanted to retrieve the correct last_simulate we'd have to
+            // compute the corresponding join block, which is non-trivial.
+            last_simulate = NULL;
+          }
+        } else if (instr->IsDeoptimize()) {
+          // Keep all environment slots alive.
+          HDeoptimize* deopt = HDeoptimize::cast(instr);
+          for (int j = deopt->first_local_index();
+               j < deopt->first_expression_index(); ++j) {
+            live.Add(j);
+          }
+        } else if (instr->IsSimulate()) {
+          last_simulate = HSimulate::cast(instr);
+        }
+        instr = next;
+        next = (instr != NULL) ? instr->previous() : NULL;
+      }
+
+      // Reached the start of the block, do necessary bookkeeping.
+      if (pass == kIterateUntilFixedPoint &&
+          live_at_block_start[block_id]->UnionIsChanged(live)) {
+        for (int j = 0; j < block->predecessors()->length(); ++j) {
+          worklist->Add(block->predecessors()->at(j)->block_id());
+        }
+        if (block->IsInlineReturnTarget()) {
+          worklist->Add(block->enter_inlined_block()->block_id());
+        }
+      }
+      first_simulate.Set(block_id, last_simulate);
+    }
+    if (pass == kIterateUntilFixedPoint && worklist->IsEmpty()) {
+      pass = kLastPass;
+    } else if (pass == kLastPass) {
+      pass = kDone;
+    }
+  }
+}
+
+
 // Mark all blocks that are dominated by an unconditional soft deoptimize to
 // prevent code motion across those blocks.
 void HGraph::PropagateDeoptimizingMark() {
@@ -4431,8 +4617,8 @@ FunctionState::FunctionState(HOptimizedGraphBuilder* owner,
     if (owner->ast_context()->IsTest()) {
       HBasicBlock* if_true = owner->graph()->CreateBasicBlock();
       HBasicBlock* if_false = owner->graph()->CreateBasicBlock();
-      if_true->MarkAsInlineReturnTarget();
-      if_false->MarkAsInlineReturnTarget();
+      if_true->MarkAsInlineReturnTarget(owner->current_block());
+      if_false->MarkAsInlineReturnTarget(owner->current_block());
       TestContext* outer_test_context = TestContext::cast(owner->ast_context());
       Expression* cond = outer_test_context->condition();
       TypeFeedbackOracle* outer_oracle = outer_test_context->oracle();
@@ -4442,7 +4628,7 @@ FunctionState::FunctionState(HOptimizedGraphBuilder* owner,
           new TestContext(owner, cond, outer_oracle, if_true, if_false);
     } else {
       function_return_ = owner->graph()->CreateBasicBlock();
-      function_return()->MarkAsInlineReturnTarget();
+      function_return()->MarkAsInlineReturnTarget(owner->current_block());
     }
     // Set this after possibly allocating a new TestContext above.
     call_context_ = owner->ast_context();
@@ -4862,6 +5048,8 @@ bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
   Verify(true);
 #endif
 
+  EnvironmentLivenessAnalysis();

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

This phase should be guarded by a flag, and should be named verbly (as other
phases) to reflect that it makes modifications to the graph.

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

Done.
Side note: "DeadCodeElimination" isn't a verb either ;-)

+
   PropagateDeoptimizingMark();
   if (!CheckConstPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
@@ -6553,7 +6741,7 @@ void HOptimizedGraphBuilder::VisitVariableProxy(VariableProxy* expr) {
 
     case Variable::PARAMETER:
     case Variable::LOCAL: {
-      HValue* value = environment()->Lookup(variable);
+      HValue* value = LookupAndMakeLive(variable);
       if (value == graph()->GetConstantHole()) {
         ASSERT(IsDeclaredVariableMode(variable->mode()) &&
                variable->mode() != VAR);
@@ -7553,7 +7741,7 @@ void HOptimizedGraphBuilder::HandleCompoundAssignment(Assignment* expr) {
         if (var->mode() == CONST)  {
           return Bailout("unsupported const compound assignment");
         }
-        Bind(var, Top());
+        BindIfLive(var, Top());
         break;
 
       case Variable::CONTEXT: {
@@ -7782,7 +7970,7 @@ void HOptimizedGraphBuilder::VisitAssignment(Assignment* expr) {
         // permitted.
         CHECK_ALIVE(VisitForValue(expr->value(), ARGUMENTS_ALLOWED));
         HValue* value = Pop();
-        Bind(var, value);
+        BindIfLive(var, value);
         return ast_context()->ReturnValue(value);
       }
 
@@ -9002,7 +9190,8 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind,
                                 function_state()->inlining_kind(),
                                 function->scope()->arguments(),
                                 arguments_values,
-                                undefined_receiver);
+                                undefined_receiver,
+                                zone());
   function_state()->set_entry(enter_inlined);
   AddInstruction(enter_inlined);
 
@@ -9081,6 +9270,8 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind,
     HBasicBlock* if_true = inlined_test_context()->if_true();
     HBasicBlock* if_false = inlined_test_context()->if_false();
 
+    HEnterInlined* entry = function_state()->entry();
+
     // Pop the return test context from the expression context stack.
     ASSERT(ast_context() == inlined_test_context());
     ClearInlinedTestContext();
@@ -9088,11 +9279,13 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind,
 
     // Forward to the real test context.
     if (if_true->HasPredecessor()) {
+      entry->RegisterReturnTarget(if_true, zone());
       if_true->SetJoinId(ast_id);
       HBasicBlock* true_target = TestContext::cast(ast_context())->if_true();
       if_true->Goto(true_target, function_state());
     }
     if (if_false->HasPredecessor()) {
+      entry->RegisterReturnTarget(if_false, zone());
       if_false->SetJoinId(ast_id);
       HBasicBlock* false_target = TestContext::cast(ast_context())->if_false();
       if_false->Goto(false_target, function_state());
@@ -9101,6 +9294,7 @@ bool HOptimizedGraphBuilder::TryInline(CallKind call_kind,
     return true;
 
   } else if (function_return()->HasPredecessor()) {
+    function_state()->entry()->RegisterReturnTarget(function_return(), zone());
     function_return()->SetJoinId(ast_id);
     set_current_block(function_return());
   } else {
@@ -9407,7 +9601,7 @@ bool HOptimizedGraphBuilder::TryCallApply(Call* expr) {
 
   VariableProxy* arg_two = args->at(1)->AsVariableProxy();
   if (arg_two == NULL || !arg_two->var()->IsStackAllocated()) return false;
-  HValue* arg_two_value = environment()->Lookup(arg_two->var());
+  HValue* arg_two_value = LookupAndMakeLive(arg_two->var());
   if (!arg_two_value->CheckFlag(HValue::kIsArguments)) return false;
 
   // Found pattern f.apply(receiver, arguments).
@@ -10118,7 +10312,7 @@ void HOptimizedGraphBuilder::VisitCountOperation(CountOperation* expr) {
 
       case Variable::PARAMETER:
       case Variable::LOCAL:
-        Bind(var, after);
+        BindIfLive(var, after);
         break;
 
       case Variable::CONTEXT: {
@@ -11201,7 +11395,7 @@ void HOptimizedGraphBuilder::VisitFunctionDeclaration(
     case Variable::LOCAL: {
       CHECK_ALIVE(VisitForValue(declaration->fun()));
       HValue* value = Pop();
-      environment()->Bind(variable, value);
+      BindIfLive(variable, value);
       break;
     }
     case Variable::CONTEXT: {