[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"
 #include "src/compiler/graph-reducer.h"
 #include "src/compiler/js-operator.h"
 #include "src/compiler/node.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/simplified-operator.h"
 #include "src/objects-inl.h"
 #include "src/type-cache.h"
 
 namespace v8 {
 namespace internal {
 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), phi_(zone) {}
+      : id_(id),
+        status_(kUntracked),
+        fields_(zone),
+        phi_(zone),
+        object_state_(nullptr) {}
 
   VirtualObject(const VirtualObject& other)
       : id_(other.id_),
         status_(other.status_),
         fields_(other.fields_),
-        phi_(other.phi_) {}
+        phi_(other.phi_),
+        object_state_(other.object_state_) {}
 
   VirtualObject(NodeId id, Zone* zone, size_t field_number)
-      : id_(id), status_(kTracked), fields_(zone), phi_(zone) {
+      : id_(id),
+        status_(kTracked),
+        fields_(zone),
+        phi_(zone),
+        object_state_(nullptr) {
     fields_.resize(field_number);
     phi_.resize(field_number, false);
   }
 
   Node* GetField(size_t offset) {
     if (offset < fields_.size()) {
       return fields_[offset];
     }
     return nullptr;
   }
@@ skipping 33 matching lines @@
     for (size_t i = 0; i < fields_.size(); ++i) {
       if (fields_[i] != nullptr) {
         fields_[i] = nullptr;
         changed = true;
       }
       phi_[i] = false;
     }
     return changed;
   }
   bool UpdateFrom(const VirtualObject& other);
+  void SetObjectState(Node* node) { object_state_ = node; }
+  Node* GetObjectState() { return object_state_; }
 
   NodeId id() { return id_; }
   void id(NodeId id) { id_ = id; }
 
  private:
   NodeId id_;
   Status status_;
   ZoneVector<Node*> fields_;
   ZoneVector<bool> phi_;
+  Node* object_state_;
 };
 
 
 bool VirtualObject::UpdateFrom(const VirtualObject& other) {
   bool changed = status_ != other.status_;
   status_ = other.status_;
   if (fields_.size() != other.fields_.size()) {
     fields_ = other.fields_;
     return true;
   }
   for (size_t i = 0; i < fields_.size(); ++i) {
     if (fields_[i] != other.fields_[i]) {
       changed = true;
       fields_[i] = other.fields_[i];
     }
   }
   return changed;
 }
 
 
-// ------------------------------VirtualState-----------------------------------
-
-
 class VirtualState : public ZoneObject {
  public:
   VirtualState(Zone* zone, size_t size);
   VirtualState(const VirtualState& states);
 
   VirtualObject* GetVirtualObject(Node* node);
   VirtualObject* GetVirtualObject(size_t id);
   VirtualObject* GetOrCreateTrackedVirtualObject(NodeId id, Zone* zone);
   void SetVirtualObject(NodeId id, VirtualObject* state);
   void LastChangedAt(Node* node) { last_changed_ = node; }
@@ skipping 80 matching lines @@
     }
     if (field != rep) {
       rep = nullptr;
     }
   }
   return rep;
 }
 
 
 VirtualState::VirtualState(Zone* zone, size_t size)
-    : info_(zone), last_changed_(nullptr) {
-  info_.resize(size);
-}
+    : info_(size, nullptr, zone), last_changed_(nullptr) {}
 
 
 VirtualState::VirtualState(const VirtualState& state)
-    : info_(state.info_.get_allocator().zone()),
+    : info_(state.info_.size(), nullptr, state.info_.get_allocator().zone()),
       last_changed_(state.last_changed_) {
-  info_.resize(state.info_.size());
   for (size_t i = 0; i < state.info_.size(); ++i) {
     if (state.info_[i] && state.info_[i]->id() == i) {
       info_[i] = new (state.info_.get_allocator().zone())
           VirtualObject(*state.info_[i]);
     }
   }
   for (size_t i = 0; i < state.info_.size(); ++i) {
     if (state.info_[i] && state.info_[i]->id() != i) {
       info_[i] = info_[state.info_[i]->id()];
     }
@@ skipping 175 matching lines @@
                     changed = true;
                     NodeProperties::ReplaceValueInput(rep, cache->fields()[n],
                                                       n);
                   }
                 } else {
                   changed = true;
                   rep->InsertInput(graph->zone(), n, cache->fields()[n]);
                 }
               }
               if (rep->op()->ValueInputCount() != value_input_count) {
-                PrintF("    Widening Phi #%d of arity %d to %d", rep->id(),
-                       rep->op()->ValueInputCount(), value_input_count);
+                if (FLAG_trace_turbo_escape) {
+                  PrintF("    Widening Phi #%d of arity %d to %d", rep->id(),
+                         rep->op()->ValueInputCount(), value_input_count);
+                }
                 NodeProperties::ChangeOp(
                     rep, common->Phi(MachineRepresentation::kTagged,
                                      value_input_count));
               }
             }
           } else {
             changed = mergeObject->SetField(i, nullptr) || changed;
           }
         }
       }
-
     } else {
       SetVirtualObject(id, nullptr);
     }
   }
   // Update linked objects.
   for (NodeId id = 0; id < cache->min_size(); ++id) {
     if (VirtualObject* obj = cache->states().front()->GetVirtualObject(id)) {
       if (obj->id() != id) {
         SetVirtualObject(id, GetVirtualObject(obj->id()));
       }
     }
   }
   return changed;
 }
 
 
-// ------------------------------EscapeStatusAnalysis---------------------------
-
-
 EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis,
                                            Graph* graph, Zone* zone)
     : object_analysis_(object_analysis),
       graph_(graph),
       zone_(zone),
       info_(graph->NodeCount(), kUnknown, zone),
       queue_(zone) {}
 
 
 EscapeStatusAnalysis::~EscapeStatusAnalysis() {}
@@ skipping 91 matching lines @@
         if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
           RevisitInputs(rep);
           RevisitUses(rep);
         }
       }
       break;
     }
     case IrOpcode::kPhi:
       if (!HasEntry(node)) {
         info_[node->id()] = kVirtual;
+        if (!IsAllocationPhi(node)) {
+          SetEscaped(node);
+          RevisitUses(node);
+        }
       }
       CheckUsesForEscape(node);
     default:
       break;
   }
 }
 
 
+bool EscapeStatusAnalysis::IsAllocationPhi(Node* node) {
+  for (Edge edge : node->input_edges()) {
+    Node* input = edge.to();
+    if (input->opcode() == IrOpcode::kPhi && !IsEscaped(input)) continue;
+    if (IsAllocation(input)) continue;
+    return false;
+  }
+  return true;
+}
+
+
 void EscapeStatusAnalysis::ProcessStoreField(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
   Node* to = NodeProperties::GetValueInput(node, 0);
   Node* val = NodeProperties::GetValueInput(node, 1);
   if ((IsEscaped(to) || !IsAllocation(to)) && SetEscaped(val)) {
     RevisitUses(val);
     RevisitInputs(val);
     if (FLAG_trace_turbo_escape) {
       PrintF("Setting #%d (%s) to escaped because of store to field of #%d\n",
              val->id(), val->op()->mnemonic(), to->id());
@@ skipping 19 matching lines @@
 
 void EscapeStatusAnalysis::ProcessAllocate(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
   if (!HasEntry(node)) {
     info_[node->id()] = kVirtual;
     if (FLAG_trace_turbo_escape) {
       PrintF("Created status entry for node #%d (%s)\n", node->id(),
              node->op()->mnemonic());
     }
     NumberMatcher size(node->InputAt(0));
+    DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
+           node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
+           node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
+           node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
     if (!size.HasValue() && SetEscaped(node)) {
       RevisitUses(node);
       if (FLAG_trace_turbo_escape) {
         PrintF("Setting #%d to escaped because of non-const alloc\n",
                node->id());
       }
       // This node is known to escape, uses do not have to be checked.
       return;
     }
   }
@@ skipping 86 matching lines @@
 void EscapeStatusAnalysis::DebugPrint() {
   for (NodeId id = 0; id < info_.size(); id++) {
     if (info_[id] != kUnknown) {
       PrintF("Node #%d is %s\n", id,
              info_[id] == kEscaped ? "escaping" : "virtual");
     }
   }
 }
 
 
-// -----------------------------EscapeAnalysis----------------------------------
-
-
 EscapeAnalysis::EscapeAnalysis(Graph* graph, CommonOperatorBuilder* common,
                                Zone* zone)
     : graph_(graph),
       common_(common),
       zone_(zone),
       virtual_states_(zone),
       replacements_(zone),
       escape_status_(this, graph, zone),
       cache_(new (zone) MergeCache(zone)) {}
 
@@ skipping 258 matching lines @@
 
 
 void EscapeAnalysis::ProcessAllocation(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
   ForwardVirtualState(node);
 
   // Check if we have already processed this node.
   if (virtual_states_[node->id()]->GetVirtualObject(node)) return;
 
   NumberMatcher size(node->InputAt(0));
+  DCHECK(node->InputAt(0)->opcode() != IrOpcode::kInt32Constant &&
+         node->InputAt(0)->opcode() != IrOpcode::kInt64Constant &&
+         node->InputAt(0)->opcode() != IrOpcode::kFloat32Constant &&
+         node->InputAt(0)->opcode() != IrOpcode::kFloat64Constant);
   if (size.HasValue()) {
     virtual_states_[node->id()]->SetVirtualObject(
         node->id(), new (zone()) VirtualObject(node->id(), zone(),
                                                size.Value() / kPointerSize));
   } else {
     virtual_states_[node->id()]->SetVirtualObject(
         node->id(), new (zone()) VirtualObject(node->id(), zone()));
   }
   virtual_states_[node->id()]->LastChangedAt(node);
 }
@@ skipping 111 matching lines @@
                                                     Node* node) {
   VirtualObject* obj = state->GetVirtualObject(ResolveReplacement(node));
   while (obj && replacement(obj->id()) &&
          state->GetVirtualObject(replacement(obj->id()))) {
     obj = state->GetVirtualObject(replacement(obj->id()));
   }
   return obj;
 }
 
 
+bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
+  DCHECK(IsVirtual(left) && IsVirtual(right));
+  left = ResolveReplacement(left);
+  right = ResolveReplacement(right);
+  if (IsEquivalentPhi(left, right)) {
+    return true;
+  }
+  return false;
+}
+
+
 int EscapeAnalysis::OffsetFromAccess(Node* node) {
   DCHECK(OpParameter<FieldAccess>(node).offset % kPointerSize == 0);
   return OpParameter<FieldAccess>(node).offset / kPointerSize;
 }
 
 
 void EscapeAnalysis::ProcessLoadFromPhi(int offset, Node* from, Node* node,
                                         VirtualState* state) {
   if (FLAG_trace_turbo_escape) {
     PrintF("Load #%d from phi #%d", node->id(), from->id());
@@ skipping 59 matching lines @@
 }
 
 
 void EscapeAnalysis::ProcessLoadElement(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement);
   ForwardVirtualState(node);
   Node* from = NodeProperties::GetValueInput(node, 0);
   VirtualState* state = virtual_states_[node->id()];
   Node* index_node = node->InputAt(1);
   NumberMatcher index(index_node);
+  DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
+         index_node->opcode() != IrOpcode::kInt64Constant &&
+         index_node->opcode() != IrOpcode::kFloat32Constant &&
+         index_node->opcode() != IrOpcode::kFloat64Constant);
   ElementAccess access = OpParameter<ElementAccess>(node);
   if (index.HasValue()) {
     int offset = index.Value() + access.header_size / kPointerSize;
     if (VirtualObject* object = ResolveVirtualObject(state, from)) {
       CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
                kPointerSizeLog2);
       CHECK_EQ(access.header_size % kPointerSize, 0);
 
       if (!object->IsTracked()) return;
       Node* value = object->GetField(offset);
@@ skipping 38 matching lines @@
   }
 }
 
 
 void EscapeAnalysis::ProcessStoreElement(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
   ForwardVirtualState(node);
   Node* to = NodeProperties::GetValueInput(node, 0);
   Node* index_node = node->InputAt(1);
   NumberMatcher index(index_node);
+  DCHECK(index_node->opcode() != IrOpcode::kInt32Constant &&
+         index_node->opcode() != IrOpcode::kInt64Constant &&
+         index_node->opcode() != IrOpcode::kFloat32Constant &&
+         index_node->opcode() != IrOpcode::kFloat64Constant);
   ElementAccess access = OpParameter<ElementAccess>(node);
   Node* val = NodeProperties::GetValueInput(node, 2);
   if (index.HasValue()) {
     int offset = index.Value() + access.header_size / kPointerSize;
     VirtualState* states = virtual_states_[node->id()];
     if (VirtualObject* obj = ResolveVirtualObject(states, to)) {
       if (!obj->IsTracked()) return;
       CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
                kPointerSizeLog2);
       CHECK_EQ(access.header_size % kPointerSize, 0);
@@ skipping 10 matching lines @@
             "non-const "
             "index #%d (%s)\n",
             to->id(), to->op()->mnemonic(), node->id(), index_node->id(),
             index_node->op()->mnemonic());
       }
     }
   }
 }
 
 
+Node* EscapeAnalysis::GetOrCreateObjectState(Node* effect, Node* node) {
+  if ((node->opcode() == IrOpcode::kFinishRegion ||
+       node->opcode() == IrOpcode::kAllocate) &&
+      IsVirtual(node)) {
+    if (VirtualObject* vobj =
+            ResolveVirtualObject(virtual_states_[effect->id()], node)) {
+      if (Node* object_state = vobj->GetObjectState()) {
+        return object_state;
+      } else {
+        cache_->fields().clear();
+        for (size_t i = 0; i < vobj->field_count(); ++i) {
+          if (Node* field = vobj->GetField(i)) {
+            cache_->fields().push_back(field);
+          }
+        }
+        int input_count = static_cast<int>(cache_->fields().size());
+        Node* new_object_state =
+            graph()->NewNode(common()->ObjectState(input_count, vobj->id()),
+                             input_count, &cache_->fields().front());
+        vobj->SetObjectState(new_object_state);
+        if (FLAG_trace_turbo_escape) {
+          PrintF(
+              "Creating object state #%d for vobj %p (from node #%d) at effect "
+              "#%d\n",
+              new_object_state->id(), static_cast<void*>(vobj), node->id(),
+              effect->id());
+        }
+        // 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::DebugPrintObject(VirtualObject* object, NodeId id) {
   PrintF("  Object #%d with %zu fields\n", id, object->field_count());
   for (size_t i = 0; i < object->field_count(); ++i) {
     if (Node* f = object->GetField(i)) {
       PrintF("    Field %zu = #%d (%s)\n", i, f->id(), f->op()->mnemonic());
     }
   }
 }
 
 
@@ skipping 22 matching lines @@
     }
   }
   for (size_t n = 0; n < object_states.size(); n++) {
     DebugPrintState(object_states[n]);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8