First implementation of allocation elimination in Hydrogen.

src/hydrogen-escape-analysis.h

Index: src/hydrogen-escape-analysis.h
diff --git a/src/hydrogen-escape-analysis.h b/src/hydrogen-escape-analysis.h
index 6ba6e823c54f25f2ef4c45a13c9aedba37cfa566..0eaad2552f65f93ba31bae49a9cee264614788eb 100644
--- a/src/hydrogen-escape-analysis.h
+++ b/src/hydrogen-escape-analysis.h
@@ -38,17 +38,112 @@ namespace internal {
 class HEscapeAnalysisPhase : public HPhase {
  public:
   explicit HEscapeAnalysisPhase(HGraph* graph)
-      : HPhase("H_Escape analysis", graph), captured_(0, zone()) { }
+      : HPhase("H_Escape analysis", graph),
+        captured_(0, zone()),
+        number_of_values_(0),
+        cumulative_values_(0),
+        backwards_branch_stack_(NULL),
+        block_states_(graph->blocks()->length(), zone()),
+        loops_affected_by_stores_(graph->blocks()->length(), zone()) { }
 
   void Run() {
     CollectCapturedValues();
+    PerformScalarReplacement();
   }
 
  private:
   void CollectCapturedValues();
   void CollectIfNoEscapingUses(HInstruction* instr);
+  void PerformScalarReplacement();
+  void AnalyzeDataFlow(HInstruction* instr);
+  void AnalyzeLoopHeaders(HInstruction* instr);
 
-  ZoneList<HValue*> captured_;
+  HCapturedObject* NewState(HInstruction* previous) {

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

Not sure why these New* methods are in the header. They seem pretty complicated,
too.

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

Done. Moved their implementation into the .cc file.

+    Zone* zone = graph()->zone();
+    HCapturedObject* state = new(zone) HCapturedObject(number_of_values_, zone);
+    state->InsertAfter(previous);
+    return state;
+  }
+
+  HCapturedObject* NewStateWithUndefined(HInstruction* previous) {
+    HConstant* undefined = graph()->GetConstantUndefined();
+    HCapturedObject* state = NewState(previous);
+    for (int index = 0; index < number_of_values_; index++) {
+      state->SetOperandAt(index, undefined);
+    }
+    return state;
+  }
+
+  HCapturedObject* NewStateWithPhis(HInstruction* previous,
+                                    HBasicBlock* block) {
+    Zone* zone = graph()->zone();
+    HCapturedObject* state = NewState(previous);
+    HBasicBlock* pred = block->predecessors()->first();
+    int phi_index = pred->last_environment()->length() + cumulative_values_;
+    for (int index = 0; index < number_of_values_; index++) {
+      HPhi* phi = new(zone) HPhi(phi_index + index, zone);
+      block->AddPhi(phi);
+      state->SetOperandAt(index, phi);
+    }
+    return state;
+  }
+
+  HCapturedObject* NewStateWithCopy(HInstruction* previous,
+                                    HCapturedObject* old_state) {
+    HCapturedObject* state = NewState(previous);
+    for (int index = 0; index < number_of_values_; index++) {
+      state->SetOperandAt(index, old_state->OperandAt(index));
+    }
+    return state;
+  }
+
+  HCapturedObject* StateAt(HBasicBlock* block) {
+    return block_states_.at(block->block_id());
+  }
+
+  void SetStateAt(HBasicBlock* block, HCapturedObject* state) {
+    block_states_.Set(block->block_id(), state);
+  }
+
+  // Stack entry of a backwards branch to be post-processed.
+  struct BackwardsBranch : public ZoneObject {
+    HBasicBlock* block_;         // Predecessor of backwards branch.
+    HCapturedObject* state_;     // Block state at loop header entry.
+    BackwardsBranch* previous_;  // Link to previous entry on stack.
+  };
+
+  void PushBackwardsBranch(HBasicBlock* block, HCapturedObject* state) {
+    BackwardsBranch* entry = new(zone()) BackwardsBranch();
+    entry->block_ = block;
+    entry->state_ = state;
+    entry->previous_ = backwards_branch_stack_;
+    backwards_branch_stack_ = entry;
+  }
+
+  bool PopBackwardsBranch(BackwardsBranch** branch) {
+    BackwardsBranch* entry = *branch = backwards_branch_stack_;
+    backwards_branch_stack_ = entry != NULL ? entry->previous_ : NULL;
+    return entry != NULL;
+  }
+
+  // List of allocations captured during collection phase.
+  ZoneList<HInstruction*> captured_;
+
+  // Number of scalar values tracked during scalar replacement phase.
+  int number_of_values_;
+  int cumulative_values_;
+
+  // Stack of backwards branches to be post-processed after data-flow
+  // analysis finished during the scalar replacement phase.
+  BackwardsBranch* backwards_branch_stack_;
+
+  // Map of block IDs to the data-flow state at block exit during the
+  // scalar replacement phase.
+  ZoneList<HCapturedObject*> block_states_;
+
+  // Vector of loop header block IDs that contain stores into captured
+  // allocations discovered during the scalar replacement phase.
+  BitVector loops_affected_by_stores_;

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

As I understand it, you were going to track which loops had stores in a later
CL. If so, you can just leave this guy out for now.

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

Done. Ooops, that is a leftover from a previous implementation and I forgot to
remove it. Removed.

 };