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..96f610faf5929665cf86a79dda76f6efda9d53db 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),
+      inlined_entry_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());
@@ -156,6 +160,9 @@ HSimulate* HBasicBlock::CreateSimulate(BailoutId ast_id,
 
   HSimulate* instr =
       new(zone()) HSimulate(ast_id, pop_count, zone(), removable);
+#ifdef DEBUG
+  instr->set_closure(environment->closure());
+#endif
   // Order of pushed values: newest (top of stack) first. This allows
   // HSimulate::MergeInto() to easily append additional pushed values
   // that are older (from further down the stack).
@@ -192,7 +199,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 +216,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 +231,12 @@ void HBasicBlock::SetInitialEnvironment(HEnvironment* env) {
 }
 
 
+void HBasicBlock::UpdateEnvironment(HEnvironment* env) {
+  last_environment_ = env;
+  graph()->update_maximum_environment_size(env->first_expression_index());
+}
+
+
 void HBasicBlock::SetJoinId(BailoutId ast_id) {
   int length = predecessors_.length();
   ASSERT(length > 0);
@@ -731,8 +744,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 +823,16 @@ 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,
+    // so that the graph builder visits it and sees any live range extending
+    // constructs within it.
+    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 +2122,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),
+      maximum_environment_size_(0) {
   if (info->IsStub()) {
     HydrogenCodeStub* stub = info->code_stub();
     CodeStubInterfaceDescriptor* descriptor =
@@ -2486,6 +2506,235 @@ void HGraph::AssignDominators() {
 }
 
 
+HSimulate* HGraph::ZapEnvironmentSlotInNextSimulate(int index,

[titzer, 2013/05/27 11:35:28]

In this function, we have to walk forward in the graph to find the next simulate
in order to zap a dead environment slot. This could go quadratic for N dead
instructions with a simulate at the end of the block. But recall, we've done a
backwards walk in the iterative phase. You could, for example, keep track of the
last simulate seen in the backward walk and store a pointer to it explicitly in
the HEnvironment{Bind,Lookup}. Then you can kill it in O(1).

+                                                    HInstruction* from_here) {
+  HInstruction* current = from_here;
+  for (; current != NULL && !current->IsSimulate(); current = current->next()) {
+    if (current->IsLeaveInlined()) return NULL;
+    // There's always a simulate before an EnterInlined.
+    ASSERT(!current->IsEnterInlined());
+    // Don't zap if a new live range starts before the next simulate.
+    if (current->IsEnvironmentBind() &&
+        HEnvironmentBind::cast(current)->index() == index) {
+      return NULL;
+    }
+  }
+  if (current == NULL) return NULL;
+  HSimulate* simulate = HSimulate::cast(current);
+  int operand_index = simulate->ToOperandIndex(index);
+  if (operand_index == -1) {
+    simulate->AddAssignedValue(index, GetConstantUndefined());
+  } else {
+    simulate->SetOperandAt(operand_index, GetConstantUndefined());
+  }
+  return simulate;
+}
+
+
+void HGraph::ZapEnvironmentSlotsInSuccessors(
+    BitVector* live,
+    HBasicBlock* block,
+    ZoneList<BitVector*>* live_at_block_start) {
+  // 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->at(successor_id);
+    if (live_in_successor->Equals(*live)) continue;
+    for (int i = 0; i < live->length(); ++i) {
+      if (!live->Contains(i)) continue;
+      if (live_in_successor->Contains(i)) continue;
+      HSimulate* sim = ZapEnvironmentSlotInNextSimulate(i, successor->first());
+      ASSERT(sim == NULL ||
+             sim->closure().is_identical_to(
+                 block->last_environment()->closure()));
+      USE(sim);
+    }
+  }
+}
+
+
+void HGraph::ZapEnvironmentSlotsForInstruction(BitVector* live,
+                                               HInstruction* instr) {
+  switch (instr->opcode()) {
+    case HValue::kEnvironmentLookup: {
+      int index = HEnvironmentLookup::cast(instr)->index();
+      if (!live->Contains(index)) {
+        // The Simulate following the point where the environment value
+        // dies is extended or modified to zap that value's slot.
+        HSimulate* sim = ZapEnvironmentSlotInNextSimulate(index, instr->next());
+        ASSERT(sim == NULL ||
+               sim->closure().is_identical_to(
+                   HEnvironmentLookup::cast(instr)->closure()));
+        USE(sim);
+      }
+      break;
+    }
+    case HValue::kEnvironmentBind: {
+      int index = HEnvironmentBind::cast(instr)->index();
+      if (!live->Contains(index)) {
+        // Don't bother binding this value if it's never looked up.
+        HSimulate* sim = ZapEnvironmentSlotInNextSimulate(index, instr->next());
+        ASSERT(sim == NULL ||
+               sim->closure().is_identical_to(
+                   HEnvironmentBind::cast(instr)->closure()));
+        USE(sim);
+      }
+      break;
+    }
+    default:
+      break;
+  }
+}
+
+
+void HGraph::UpdateLivenessAtBlockEnd(
+    BitVector* live,
+    HBasicBlock* block,
+    ZoneList<BitVector*>* live_at_block_start) {
+  // Liveness at the end of each block: union of liveness in successors.
+  live->Clear();
+  for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
+    live->Union(*live_at_block_start->at(it.Current()->block_id()));
+  }
+}
+
+
+void HGraph::UpdateLivenessAtInstruction(
+    BitVector* live,
+    HInstruction* instr,
+    ZoneList<BitVector*>* live_at_block_start) {
+  switch (instr->opcode()) {
+    case HValue::kEnvironmentLookup:
+      live->Add(HEnvironmentLookup::cast(instr)->index());
+      break;
+    case HValue::kEnvironmentBind:
+      live->Remove(HEnvironmentBind::cast(instr)->index());
+      break;
+    case HValue::kLeaveInlined:
+      // No environment values are live at the end of an inlined section.
+      live->Clear();
+
+      // The following ASSERTs guard the assumption used in case
+      // kEnterInlined below:
+      ASSERT(instr->next()->IsSimulate());
+      ASSERT(instr->next()->next()->IsGoto());
+
+      break;
+    case HValue::kEnterInlined: {
+      // 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 (see ASSERTs above).
+      HEnterInlined* enter = HEnterInlined::cast(instr);
+      live->Clear();
+      for (int i = 0; i < enter->return_targets()->length(); ++i) {
+        int return_id = enter->return_targets()->at(i)->block_id();
+        // When an AbnormalExit is involved, it can happen that the return
+        // target block doesn't actually exist.
+        if (return_id < live_at_block_start->length()) {
+          live->Union(*live_at_block_start->at(return_id));
+        }
+      }
+      break;
+    }
+    case HValue::kDeoptimize: {
+      // Keep all environment slots alive.
+      HDeoptimize* deopt = HDeoptimize::cast(instr);
+      for (int i = deopt->first_local_index();
+           i < deopt->first_expression_index(); ++i) {
+        live->Add(i);
+      }
+      break;
+    }
+    default:
+      break;
+  }
+}
+
+
+// Values in the environment are kept alive by every subsequent LInstruction
+// that is assigned an LEnvironment. This creates register pressure and
+// unnecessary spill slot moves. Therefore it is beneficial to trim the
+// live ranges of environment slots by zapping them with a constant after
+// the last lookup that refers to them. This is similar but not identical
+// to live range analysis for HValues, so we perform an explicit liveness
+// analysis on environment slots (identified by their index).
+// This only affects slots whitelisted by
+// HOptimizedGraphBuilder::IsEligibleForEnvironmentLivenessAnalysis().
+void HGraph::AnalyzeAndPruneEnvironmentLiveness() {
+  HPhase phase("H_EnvironmentLivenessAnalysis", this);
+  if (maximum_environment_size_ == 0) return;
+  int block_count = blocks()->length();
+  ZoneList<BitVector*> live_at_block_start(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(maximum_environment_size_, zone()),
+        zone());
+    worklist->Add(i);
+  }
+  BitVector live(maximum_environment_size_, zone());
+
+  // Main iteration. Compute liveness of environment slots, and store it
+  // for each block until it doesn't change any more. For efficiency, visit
+  // blocks in reverse order and walk backwards through each block. We
+  // need several iterations to propagate liveness through nested loops.
+  while (!worklist->IsEmpty()) {
+    for (int block_id = block_count - 1; block_id >= 0; --block_id) {
+      if (!worklist->Contains(block_id)) {
+        continue;
+      }
+      worklist->Remove(block_id);
+
+      HBasicBlock* block = blocks()->at(block_id);
+      UpdateLivenessAtBlockEnd(&live, block, &live_at_block_start);
+
+      for (HInstruction* instr = block->last(); instr != NULL;
+           instr = instr->previous()) {
+        UpdateLivenessAtInstruction(&live, instr, &live_at_block_start);
+      }
+
+      // Reached the start of the block, do necessary bookkeeping.
+      if (live_at_block_start[block_id]->UnionIsChanged(live)) {
+        for (int i = 0; i < block->predecessors()->length(); ++i) {
+          worklist->Add(block->predecessors()->at(i)->block_id());
+        }
+        if (block->IsInlineReturnTarget()) {
+          worklist->Add(block->inlined_entry_block()->block_id());
+        }
+      }
+    }
+  }
+
+  // Analysis finished. Zap dead environment slots.

[titzer, 2013/05/27 11:35:28]

I don't think we need the last pass over the blocks. We have the correct live_in
information for every block in the graph.

I think it would be more clear (and also more efficient) to have a liveness
field for each HEnvironment{Bind,Lookup} instruction in the graph. Set the
liveness during the iterative phase (since when an HEnvironment{Bind,Lookup}
becomes live, it never becomes dead again).

Collect all HEnvironment{Bind,Lookup} instructions into a list which you can
inspect at the end. In the last pass, do the ZapEnvironmentSlot() for the dead
ones, then remove all of them from the graph. You can use the live_in vectors
for the blocks directly in UpdateLivenessAtBlockEnd, which kills values
selectively in successors. This saves two whole passes over the hydrogen graph.

+  for (int block_id = block_count - 1; block_id >= 0; --block_id) {
+    HBasicBlock* block = blocks()->at(block_id);
+    UpdateLivenessAtBlockEnd(&live, block, &live_at_block_start);
+    ZapEnvironmentSlotsInSuccessors(&live, block, &live_at_block_start);
+
+    for (HInstruction* instr = block->last(); instr != NULL;
+         instr = instr->previous()) {
+      ZapEnvironmentSlotsForInstruction(&live, instr);
+      UpdateLivenessAtInstruction(&live, instr, &live_at_block_start);
+    }
+  }
+
+  // Finally, remove the HEnvironment{Bind,Lookup} markers.
+  for (int block_id = block_count - 1; block_id >= 0; --block_id) {
+    HBasicBlock* block = blocks()->at(block_id);
+    for (HInstruction* instr = block->last(); instr != NULL;
+         instr = instr->previous()) {
+      if (instr->IsEnvironmentBind() || instr->IsEnvironmentLookup()) {
+        instr->DeleteAndReplaceWith(NULL);
+      }
+    }
+  }
+}
+
+
 // Mark all blocks that are dominated by an unconditional soft deoptimize to
 // prevent code motion across those blocks.
 void HGraph::PropagateDeoptimizingMark() {
@@ -4431,8 +4680,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 +4691,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 +5111,10 @@ bool HGraph::Optimize(SmartArrayPointer<char>* bailout_reason) {
   Verify(true);
 #endif
 
+  if (FLAG_analyze_environment_liveness) {
+    AnalyzeAndPruneEnvironmentLiveness();
+  }
+
   PropagateDeoptimizingMark();
   if (!CheckConstPhiUses()) {
     *bailout_reason = SmartArrayPointer<char>(StrDup(
@@ -6553,7 +6806,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 +7806,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 +8035,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 +9255,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 +9335,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 +9344,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 +9359,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 +9666,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 +10377,7 @@ void HOptimizedGraphBuilder::VisitCountOperation(CountOperation* expr) {
 
       case Variable::PARAMETER:
       case Variable::LOCAL:
-        Bind(var, after);
+        BindIfLive(var, after);
         break;
 
       case Variable::CONTEXT: {
@@ -11201,7 +11460,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: {