[turbofan] Deopt support for escape analysis

src/compiler/escape-analysis.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/escape-analysis.h"
 
 #include "src/base/flags.h"
 #include "src/bootstrapper.h"
 #include "src/compilation-dependencies.h"
 #include "src/compiler/common-operator.h"
@@ skipping 11 matching lines @@
 namespace compiler {
 
 
 // ------------------------------VirtualObject----------------------------------
 
 
 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) {
     if (offset < fields_.size()) {
       return fields_[offset];
     }
     return nullptr;
   }
 
   bool SetField(size_t offset, Node* node) {
     bool changed = fields_[offset] != node;
     fields_[offset] = node;
     return changed;
   }
   bool IsVirtual() const { return status_ == kTracked; }
   bool IsTracked() const { return status_ != kUntracked; }
   Node* GetReplacement() { return replacement_; }
   bool SetReplacement(Node* node) {
     bool changed = replacement_ != node;
     replacement_ = node;
     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_; }
   void id(NodeId id) { id_ = id; }
 
  private:
   NodeId id_;
   Status status_;
   ZoneVector<Node*> fields_;
   Node* replacement_;
+  Node* object_state_;
 };
 
 
 bool VirtualObject::UpdateFrom(const VirtualObject& other) {
   bool changed = status_ != other.status_;
   status_ = other.status_;
   changed = replacement_ != other.replacement_ || changed;
   replacement_ = other.replacement_;
   if (fields_.size() != other.fields_.size()) {
     fields_ = other.fields_;
@@ skipping 144 matching lines @@
   bool changed = false;
   for (NodeId id = 0; id < std::min(left->size(), right->size()); ++id) {
     VirtualObject* ls = left->GetVirtualObject(id);
     VirtualObject* rs = right->GetVirtualObject(id);
 
     if (ls != nullptr && rs != nullptr) {
       if (FLAG_trace_turbo_escape) {
         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)) {
           changed = mergeObject->SetField(i, ls->GetField(i)) || changed;
           if (FLAG_trace_turbo_escape && ls->GetField(i)) {
             PrintF("    Field %zu agree on rep #%d\n", i,
                    ls->GetField(i)->id());
           }
         } else if (ls->GetField(i) != nullptr && rs->GetField(i) != nullptr) {
           Node* phi = graph->NewNode(common->Phi(kMachAnyTagged, 2),
@@ skipping 261 matching lines @@
 
 // -----------------------------EscapeAnalysis----------------------------------
 
 
 EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
                                Zone* zone)
     : graph_(graph),
       common_(common),
       zone_(zone),
       virtual_states_(zone),
-      escape_status_(this, graph, zone) {}
+      escape_status_(this, graph, zone),
+      effects_(zone) {}
 
 
 EscapeAnalysis::~EscapeAnalysis() {}
 
 
 void EscapeAnalysis::Run() {
   RunObjectAnalysis();
   escape_status_.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);
           }
         }
       }
       // First process loads: dangling loads are a problem otherwise.
       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);
           }
         }
       }
     }
   }
   if (FLAG_trace_turbo_escape) {
     DebugPrint();
   }
 }
 
 
 bool EscapeAnalysis::IsDanglingEffectNode(Node* node) {
   if (node->op()->EffectInputCount() == 0) return false;
   if (node->op()->EffectOutputCount() == 0) return false;
   for (Edge edge : node->use_edges()) {
     if (NodeProperties::IsEffectEdge(edge)) {
       return false;
     }
   }
   return true;
 }
 
 
+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:
       ProcessAllocation(node);
       break;
     case IrOpcode::kBeginRegion:
       ForwardVirtualState(node);
       break;
     case IrOpcode::kFinishRegion:
       ProcessFinishRegion(node);
       break;
     case IrOpcode::kStoreField:
       ProcessStoreField(node);
       break;
     case IrOpcode::kLoadField:
       ProcessLoadField(node);
       break;
     case IrOpcode::kStart:
       ProcessStart(node);
       break;
     case IrOpcode::kEffectPhi:
       return ProcessEffectPhi(node);
       break;
     default:
       if (node->op()->EffectInputCount() > 0) {
         ForwardVirtualState(node);
+        RecordEffectForFrameStateUses(node, node);
       }
       break;
   }
   return true;
 }
 
 
 bool EscapeAnalysis::IsEffectBranchPoint(Node* node) {
   int count = 0;
   for (Edge edge : node->use_edges()) {
     Node* use = edge.from();
     if (NodeProperties::IsEffectEdge(edge) &&
         use->opcode() != IrOpcode::kLoadField) {
       if (++count > 1) {
         return true;
       }
     }
   }
   return false;
 }
 
 
 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);
   }
   Node* effect = NodeProperties::GetEffectInput(node);
   // Break the cycle for effect phis.
   if (effect->opcode() == IrOpcode::kEffectPhi) {
     if (virtual_states_[effect->id()] == nullptr) {
       virtual_states_[effect->id()] =
           new (zone()) VirtualState(zone(), graph()->NodeCount());
@@ skipping 132 matching lines @@
 bool EscapeAnalysis::IsVirtual(Node* node) {
   return escape_status_.IsVirtual(node);
 }
 
 
 bool EscapeAnalysis::IsEscaped(Node* node) {
   return escape_status_.IsEscaped(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;
 }
 
 
 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) {
       // Record that the load has this alias.
       states->UpdateReplacement(node, value, zone());
     } else if (FLAG_trace_turbo_escape) {
       PrintF("No field %d on record for #%d\n", offset, from->id());
     }
   } 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) {
         PrintF("Load #%d from phi #%d", node->id(), from->id());
       }
       Node* left = NodeProperties::GetValueInput(from, 0);
       Node* right = NodeProperties::GetValueInput(from, 1);
       VirtualObject* l = states->GetVirtualObject(left);
       VirtualObject* r = states->GetVirtualObject(right);
       if (l && r) {
@@ skipping 41 matching lines @@
   VirtualState* states = virtual_states_[node->id()];
   if (VirtualObject* obj = states->GetVirtualObject(to)) {
     if (!obj->IsTracked()) return;
     if (obj->SetField(offset, states->ResolveReplacement(val))) {
       states->LastChangedAt(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++) {
     if (VirtualState* states = virtual_states_[id]) {
       if (std::find(object_states.begin(), object_states.end(), states) ==
           object_states.end()) {
         object_states.push_back(states);
       }
     }
   }
   for (size_t n = 0; n < object_states.size(); n++) {
     PrintF("Dumping object state %p\n", static_cast<void*>(object_states[n]));
     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());
             }
           }
         } else {
           PrintF("  Object #%zu links to object #%d\n", id, obj->id());
         }
       }
     }
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8