First implementation of allocation elimination in Hydrogen.

src/hydrogen-escape-analysis.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 45 matching lines @@
     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
       HInstruction* instr = it.Current();
       if (instr->IsAllocate()) {
         CollectIfNoEscapingUses(instr);
       }
     }
   }
 }
 
 
+// Performs a forward data-flow analysis of all loads and stores on the
+// given captured allocation. This uses a reverse post-order iteration
+// over affected basic blocks. All non-escaping instructions are handled
+// and replaced during the analysis.
+void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) {
+  HBasicBlock* allocate_block = allocate->block();
+  block_states_.AddBlock(NULL, graph()->blocks()->length(), zone());
+
+  for (int i = 0; i < graph()->blocks()->length(); i++) {

[titzer, 2013/08/01 17:11:50]

You can start i at allocate_block->id(), since the allocation cannot dominate
blocks that come before.

[Michael Starzinger, 2013/08/05 15:13:00]

Done. So obvious, I feel embarrassed now.

+    HBasicBlock* block = graph()->blocks()->at(i);
+    Zone* graph_zone = graph()->zone();
+    HCapturedObject* state = NULL;
+
+    // Skip blocks that are not dominated by the captured allocation.
+    if (!allocate_block->Dominates(block) && allocate_block != block) continue;
+    if (FLAG_trace_escape_analysis) {
+      PrintF("Analyzing data-flow in B%d\n", block->block_id());
+    }
+
+    // Update block state using all predecessor blocks.
+    if (block->predecessors()->length() == 1) {
+      state = StateAt(block->predecessors()->first());
+    } else if (allocate_block != block) {
+      state = NewStateWithPhis(block->first(), block);
+      for (int i = 0; i < block->predecessors()->length(); i++) {
+        HBasicBlock* pred = block->predecessors()->at(i);
+        HCapturedObject* pred_state = StateAt(pred);
+        // Backwards branches will be post-processed later.
+        if (pred->block_id() >= block->block_id()) {
+          ASSERT(block->IsLoopHeader() && pred_state == NULL);
+          PushBackwardsBranch(pred, state);
+          continue;
+        }
+        for (int index = 0; index < number_of_values_; index++) {

[titzer, 2013/08/01 17:11:50]

You're creating a lot of phis here. You only need to create a phi if this block
is a loop header, or if the predecessors do not have the same HValue for a
tracked field.

[Michael Starzinger, 2013/08/05 15:13:00]

Done. Switched to lazy creation of phis only once one of the incoming values is
actually different from the others.

+          HPhi* phi = HPhi::cast(state->OperandAt(index));
+          phi->AddInput(pred_state->OperandAt(index));
+        }
+      }
+    }
+
+    // Go through all instructions of the current block.
+    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
+      HInstruction* instr = it.Current();
+      switch (instr->opcode()) {
+        case HValue::kAllocate: {
+          if (instr != allocate) continue;
+          state = NewStateWithUndefined(allocate);
+          break;
+        }
+        case HValue::kLoadNamedField: {
+          HLoadNamedField* load = HLoadNamedField::cast(instr);
+          int index = load->access().offset() / kPointerSize;

[titzer, 2013/08/01 17:11:50]

Are you only tracking in-object properties? Otherwise, you need to check the
in-objectness of the access as well.

[Michael Starzinger, 2013/08/05 15:13:00]

Done. Good point, currently we don't HAllocate objects that have out-of-object
fields and hence this doesn't happen. But I added asserts to guard that.

+          if (load->object() != allocate) continue;
+          HValue* replacement = state->OperandAt(index);
+          load->DeleteAndReplaceWith(replacement);
+          if (FLAG_trace_escape_analysis) {
+            PrintF("Replacing load #%d with #%d (%s)\n", instr->id(),
+                   replacement->id(), replacement->Mnemonic());
+          }
+          break;
+        }
+        case HValue::kStoreNamedField: {
+          HStoreNamedField* store = HStoreNamedField::cast(instr);
+          int index = store->access().offset() / kPointerSize;
+          if (store->object() != allocate) continue;
+          state = NewStateWithCopy(store, state);
+          state->SetOperandAt(index, store->value());
+          if (!store->transition().is_null()) {
+            // TODO(mstarzinger): Handle dereference is actually not allowed
+            // here. Fix this by allocating the HConstant at graph building.
+            AllowHandleDereference allow_deref;
+            HConstant* map = new(graph_zone) HConstant(store->transition());
+            map->FinalizeUniqueValueId();
+            map->InsertBefore(store);
+            state->SetOperandAt(0, map);
+          }
+          store->DeleteAndReplaceWith(NULL);
+          if (FLAG_trace_escape_analysis) {
+            PrintF("Replacing store #%d%s\n", instr->id(),
+                   store->transition().is_null() ? "" : " (with transition)");
+          }
+          break;
+        }
+        case HValue::kSimulate: {
+          HSimulate* simulate = HSimulate::cast(instr);
+          // TODO(mstarzinger): This doesn't track deltas for values on the
+          // operand stack yet. Find a repro test case and fix this.
+          for (int i = 0; i < simulate->OperandCount(); i++) {
+            if (simulate->OperandAt(i) != allocate) continue;
+            simulate->SetOperandAt(i, state);
+          }
+          break;
+        }
+        case HValue::kArgumentsObject:
+        case HValue::kCapturedObject: {
+          for (int i = 0; i < instr->OperandCount(); i++) {
+            if (instr->OperandAt(i) != allocate) continue;
+            instr->SetOperandAt(i, state);
+          }
+          break;
+        }
+        case HValue::kCheckHeapObject: {
+          HCheckHeapObject* check = HCheckHeapObject::cast(instr);
+          if (check->value() != allocate) continue;
+          check->DeleteAndReplaceWith(NULL);
+          break;
+        }
+        case HValue::kCheckMaps: {
+          HCheckMaps* mapcheck = HCheckMaps::cast(instr);
+          if (mapcheck->value() != allocate) continue;
+          // TODO(mstarzinger): This approach breaks if the tracked map value
+          // is not a HConstant. Find a repro test case and fix this.
+          ASSERT(mapcheck->HasNoUses());
+          mapcheck->DeleteAndReplaceWith(NULL);
+          break;
+        }
+        default:
+          // Nothing to see here, move along ...
+          break;
+      }
+    }
+
+    // Store block state at block exit into map.
+    SetStateAt(block, state);

[titzer, 2013/08/01 17:11:50]

You should forward-propagate the block state to all successors of this block;
then you can delete (or even reuse) the block state.

[Michael Starzinger, 2013/08/05 15:13:00]

Done. Switched to forward propagation of the block state.

+  }
+
+  // All uses have been handled.
+  ASSERT(allocate->HasNoUses());
+  allocate->DeleteAndReplaceWith(NULL);
+}
+
+
+// Post-process all loop headers and fill in values from backwards
+// branches into the phis added to analyzed loop headers.
+void HEscapeAnalysisPhase::AnalyzeLoopHeaders(HInstruction* allocate) {
+  BackwardsBranch* branch;
+  while (PopBackwardsBranch(&branch)) {
+    HBasicBlock* pred = branch->block_;
+    HCapturedObject* state = branch->state_;
+    HCapturedObject* pred_state = StateAt(pred);
+    for (int index = 0; index < number_of_values_; index++) {

[titzer, 2013/08/01 17:11:50]

This is somewhat brittle because the phi input indexes must match up with the
predecessor indexes, and since your edges are coming off a stack, I'm really
surprised you were so lucky. This needs to be more robust somehow.

[Michael Starzinger, 2013/08/05 15:13:00]

Done. Switched to use HBasicBlock::PredecessorIndexOf to always set operands at
the correct index. Also the post-processing step is obsolete after switching to
forward propagation.

+      HPhi* phi = HPhi::cast(state->OperandAt(index));
+      phi->AddInput(pred_state->OperandAt(index));
+    }
+  }
+}
+
+
+void HEscapeAnalysisPhase::PerformScalarReplacement() {
+  for (int i = 0; i < captured_.length(); i++) {
+    HAllocate* allocate = HAllocate::cast(captured_.at(i));
+
+    // Compute number of scalar values and start with clean slate.
+    if (!allocate->size()->IsInteger32Constant()) continue;
+    int size_in_bytes = allocate->size()->GetInteger32Constant();
+    number_of_values_ = size_in_bytes / kPointerSize;
+    loops_affected_by_stores_.Clear();
+    block_states_.Clear();
+
+    // Perform actual analysis steps.
+    AnalyzeDataFlow(allocate);
+    AnalyzeLoopHeaders(allocate);
+
+    cumulative_values_ += number_of_values_;
+    ASSERT(backwards_branch_stack_ == NULL);
+    ASSERT(allocate->HasNoUses());
+    ASSERT(!allocate->IsLinked());
+  }
+}
+
+
 } }  // namespace v8::internal