[turbofan] Deopt support for escape analysis

src/compiler/escape-analysis.cc

Index: src/compiler/escape-analysis.cc
diff --git a/src/compiler/escape-analysis.cc b/src/compiler/escape-analysis.cc
index dc331bbbe68e0e344f2f6e44258dd2fe32f08add..20f1e45d05cc5f40c8559b5098c9e97da24c6b5d 100644
--- a/src/compiler/escape-analysis.cc
+++ b/src/compiler/escape-analysis.cc
@@ -29,17 +29,26 @@ class VirtualObject : public ZoneObject {
  public:
   enum Status { kUntracked = 0, kTracked = 1 };
   VirtualObject(NodeId id, Zone* zone)
-      : id_(id), status_(kUntracked), fields_(zone), replacement_(nullptr) {}
+      : id_(id),
+        status_(kUntracked),
+        fields_(zone),
+        replacement_(nullptr),
+        object_state_(nullptr) {}
 
   VirtualObject(const VirtualObject& other)
       : id_(other.id_),
         status_(other.status_),
         fields_(other.fields_),
-        replacement_(other.replacement_) {}
+        replacement_(other.replacement_),
+        object_state_(other.object_state_) {}
 
-  VirtualObject(NodeId id, Zone* zone, size_t field_number)
-      : id_(id), status_(kTracked), fields_(zone), replacement_(nullptr) {
-    fields_.resize(field_number);
+  VirtualObject(NodeId id, Zone* zone, size_t field_count)
+      : id_(id),
+        status_(kTracked),
+        fields_(zone),
+        replacement_(nullptr),
+        object_state_(nullptr) {
+    fields_.resize(field_count);
   }
 
   Node* GetField(size_t offset) {
@@ -63,15 +72,17 @@ class VirtualObject : public ZoneObject {
     return changed;
   }
 
-  size_t fields() { return fields_.size(); }
-  bool ResizeFields(size_t field_number) {
-    if (field_number != fields_.size()) {
-      fields_.resize(field_number);
+  Node** fields_array() { return &fields_.front(); }
+  size_t field_count() { return fields_.size(); }
+  bool ResizeFields(size_t field_count) {
+    if (field_count != fields_.size()) {
+      fields_.resize(field_count);
       return true;
     }
     return false;
   }
-
+  void SetObjectState(Node* node) { object_state_ = node; }
+  Node* GetObjectState() { return object_state_; }
   bool UpdateFrom(const VirtualObject& other);
 
   NodeId id() { return id_; }
@@ -82,6 +93,7 @@ class VirtualObject : public ZoneObject {
   Status status_;
   ZoneVector<Node*> fields_;
   Node* replacement_;
+  Node* object_state_;
 };
 
 
@@ -246,7 +258,7 @@ bool VirtualState::MergeFrom(VirtualState* left, VirtualState* right,
         PrintF("  Merging fields of #%d\n", id);
       }
       VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(id, zone);
-      size_t fields = std::max(ls->fields(), rs->fields());
+      size_t fields = std::max(ls->field_count(), rs->field_count());
       changed = mergeObject->ResizeFields(fields) || changed;
       for (size_t i = 0; i < fields; ++i) {
         if (ls->GetField(i) == rs->GetField(i)) {
@@ -528,7 +540,8 @@ EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
       common_(common),
       zone_(zone),
       virtual_states_(zone),
-      escape_status_(this, graph, zone) {}
+      escape_status_(this, graph, zone),
+      effects_(zone) {}
 
 
 EscapeAnalysis::~EscapeAnalysis() {}
@@ -541,19 +554,20 @@ void EscapeAnalysis::Run() {
 
 
 void EscapeAnalysis::RunObjectAnalysis() {
+  effects_.resize(graph()->NodeCount());
   virtual_states_.resize(graph()->NodeCount());
-  ZoneVector<Node*> queue(zone());
-  queue.push_back(graph()->start());
-  while (!queue.empty()) {
-    Node* node = queue.back();
-    queue.pop_back();
+  ZoneVector<Node*> stack(zone());

[Jarin, 2015/12/04 13:41:11]

Nit: you can actually even say ZoneStack<...> here (and then use push, pop and
top methods).

+  stack.push_back(graph()->start());
+  while (!stack.empty()) {
+    Node* node = stack.back();
+    stack.pop_back();
     if (Process(node)) {
       for (Edge edge : node->use_edges()) {
         if (NodeProperties::IsEffectEdge(edge)) {
           Node* use = edge.from();
           if (use->opcode() != IrOpcode::kLoadField ||
               !IsDanglingEffectNode(use)) {
-            queue.push_back(use);
+            stack.push_back(use);
           }
         }
       }
@@ -563,7 +577,7 @@ void EscapeAnalysis::RunObjectAnalysis() {
           Node* use = edge.from();
           if (use->opcode() == IrOpcode::kLoadField &&
               IsDanglingEffectNode(use)) {
-            queue.push_back(use);
+            stack.push_back(use);
           }
         }
       }
@@ -587,6 +601,32 @@ bool EscapeAnalysis::IsDanglingEffectNode(Node* node) {
 }
 
 
+void EscapeAnalysis::RecordEffectForFrameStateUses(Node* node, Node* effect) {
+  DCHECK(effect->op()->EffectInputCount() > 0);
+  ZoneVector<Node*> stack(zone());
+  stack.push_back(node);
+  while (!stack.empty()) {
+    Node* cur = stack.back();
+    stack.pop_back();
+    for (Edge edge : cur->input_edges()) {
+      Node* input = edge.to();
+      if (input->opcode() == IrOpcode::kFrameState ||
+          input->opcode() == IrOpcode::kStateValues) {
+        if (effects_[input->id()] != effect) {
+          effects_[input->id()] = effect;
+          if (FLAG_trace_turbo_escape) {
+            PrintF("Recorded effect #%d (%s) for frame state %d\n",
+                   effect->id(), effect->op()->mnemonic(), input->id());
+          }
+        }
+        // Climb up the chain.
+        stack.push_back(input);
+      }
+    }
+  }
+}
+
+
 bool EscapeAnalysis::Process(Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kAllocate:
@@ -613,6 +653,7 @@ bool EscapeAnalysis::Process(Node* node) {
     default:
       if (node->op()->EffectInputCount() > 0) {
         ForwardVirtualState(node);
+        RecordEffectForFrameStateUses(node, node);
       }
       break;
   }
@@ -637,7 +678,8 @@ bool EscapeAnalysis::IsEffectBranchPoint(Node* node) {
 
 void EscapeAnalysis::ForwardVirtualState(Node* node) {
   DCHECK_EQ(node->op()->EffectInputCount(), 1);
-  if (node->opcode() != IrOpcode::kLoadField && IsDanglingEffectNode(node)) {
+  if (node->opcode() != IrOpcode::kLoadField &&
+      node->opcode() != IrOpcode::kLoad && IsDanglingEffectNode(node)) {
     PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
            node->op()->mnemonic());
     DCHECK(false);
@@ -790,6 +832,17 @@ bool EscapeAnalysis::IsEscaped(Node* node) {
 }
 
 
+VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) {
+  if (VirtualState* states = virtual_states_[at->id()]) {
+    return states->GetVirtualObject(id);
+  }
+  return nullptr;
+}
+
+
+Node* EscapeAnalysis::GetEffect(Node* node) { return effects_[node->id()]; }
+
+
 int EscapeAnalysis::OffsetFromAccess(Node* node) {
   DCHECK(OpParameter<FieldAccess>(node).offset % kPointerSize == 0);
   return OpParameter<FieldAccess>(node).offset / kPointerSize;
@@ -800,9 +853,9 @@ void EscapeAnalysis::ProcessLoadField(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kLoadField);
   ForwardVirtualState(node);
   Node* from = NodeProperties::GetValueInput(node, 0);
-  int offset = OffsetFromAccess(node);
   VirtualState* states = virtual_states_[node->id()];
   if (VirtualObject* state = states->GetVirtualObject(from)) {
+    int offset = OffsetFromAccess(node);
     if (!state->IsTracked()) return;
     Node* value = state->GetField(offset);
     if (value) {
@@ -813,6 +866,7 @@ void EscapeAnalysis::ProcessLoadField(Node* node) {
     }
   } else {
     if (from->opcode() == IrOpcode::kPhi) {
+      int offset = OffsetFromAccess(node);
       // Only binary phis are supported for now.
       CHECK_EQ(from->op()->ValueInputCount(), 2);
       if (FLAG_trace_turbo_escape) {
@@ -874,6 +928,37 @@ void EscapeAnalysis::ProcessStoreField(Node* node) {
 }
 
 
+Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) {
+  if ((node->opcode() == IrOpcode::kFinishRegion ||
+       node->opcode() == IrOpcode::kAllocate) &&
+      IsVirtual(node)) {
+    if (VirtualObject* vobj = GetVirtualObject(effect, node->id())) {
+      if (Node* object_state = vobj->GetObjectState()) {
+        return object_state;
+      } else {
+        Node* new_object_state = graph()->NewNode(
+            common()->ObjectState(static_cast<int>(vobj->field_count()),
+                                  vobj->id()),
+            static_cast<int>(vobj->field_count()), vobj->fields_array());
+        vobj->SetObjectState(new_object_state);
+        // Now fix uses of other objects.
+        for (size_t i = 0; i < vobj->field_count(); ++i) {
+          if (Node* field = vobj->GetField(i)) {
+            if (Node* field_object_state =
+                    GetOrCreateObjectState(effect, field)) {
+              NodeProperties::ReplaceValueInput(
+                  new_object_state, field_object_state, static_cast<int>(i));
+            }
+          }
+        }
+        return new_object_state;
+      }
+    }
+  }
+  return nullptr;
+}
+
+
 void EscapeAnalysis::DebugPrint() {
   ZoneVector<VirtualState*> object_states(zone());
   for (NodeId id = 0; id < virtual_states_.size(); id++) {
@@ -889,12 +974,12 @@ void EscapeAnalysis::DebugPrint() {
     for (size_t id = 0; id < object_states[n]->size(); id++) {
       if (VirtualObject* obj = object_states[n]->GetVirtualObject(id)) {
         if (obj->id() == id) {
-          PrintF("  Object #%zu with %zu fields", id, obj->fields());
+          PrintF("  Object #%zu with %zu fields", id, obj->field_count());
           if (Node* rep = obj->GetReplacement()) {
             PrintF(", rep = #%d (%s)", rep->id(), rep->op()->mnemonic());
           }
           PrintF("\n");
-          for (size_t i = 0; i < obj->fields(); ++i) {
+          for (size_t i = 0; i < obj->field_count(); ++i) {
             if (Node* f = obj->GetField(i)) {
               PrintF("    Field %zu = #%d (%s)\n", i, f->id(),
                      f->op()->mnemonic());