[turbofan] Move replacements out of virtual object

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),
-        phi_(zone),
-        replacement_(nullptr) {}
+      : id_(id), status_(kUntracked), fields_(zone), phi_(zone) {}
 
   VirtualObject(const VirtualObject& other)
       : id_(other.id_),
         status_(other.status_),
         fields_(other.fields_),
-        phi_(other.phi_),
-        replacement_(other.replacement_) {}
+        phi_(other.phi_) {}
 
   VirtualObject(NodeId id, Zone* zone, size_t field_number)
-      : id_(id),
-        status_(kTracked),
-        fields_(zone),
-        phi_(zone),
-        replacement_(nullptr) {
+      : id_(id), status_(kTracked), fields_(zone), phi_(zone) {
     fields_.resize(field_number);
     phi_.resize(field_number, false);
   }
 
   Node* GetField(size_t offset) {
     if (offset < fields_.size()) {
       return fields_[offset];
     }
     return nullptr;
   }
@@ skipping 10 matching lines @@
     fields_[offset] = node;
     phi_[offset] = created_phi;
     if (changed && FLAG_trace_turbo_escape && node) {
       PrintF("Setting field %zu of #%d to #%d (%s)\n", offset, id(), node->id(),
              node->op()->mnemonic());
     }
     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;
-  }
 
   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);
       phi_.resize(field_count);
       return true;
     }
     return false;
@@ skipping 12 matching lines @@
   bool UpdateFrom(const VirtualObject& other);
 
   NodeId id() { return id_; }
   void id(NodeId id) { id_ = id; }
 
  private:
   NodeId id_;
   Status status_;
   ZoneVector<Node*> fields_;
   ZoneVector<bool> phi_;
-  Node* replacement_;
 };
 
 
 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_;
     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* ResolveVirtualObject(Node* node);
   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; }
   Node* GetLastChanged() { return last_changed_; }
   bool UpdateFrom(NodeId id, VirtualObject* state, Zone* zone);
-  Node* ResolveReplacement(Node* node);
-  bool UpdateReplacement(Node* node, Node* rep, Zone* zone);
   bool UpdateFrom(VirtualState* state, Zone* zone);
   bool MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
                  CommonOperatorBuilder* common, Node* control);
 
   size_t size() { return info_.size(); }
 
  private:
   ZoneVector<VirtualObject*> info_;
   Node* last_changed_;
 };
@@ skipping 27 matching lines @@
   if (id >= info_.size()) return nullptr;
   return info_[id];
 }
 
 
 VirtualObject* VirtualState::GetVirtualObject(Node* node) {
   return GetVirtualObject(node->id());
 }
 
 
-VirtualObject* VirtualState::ResolveVirtualObject(Node* node) {
-  VirtualObject* obj = GetVirtualObject(node->id());
-  while (obj && !obj->IsTracked() && obj->GetReplacement() &&
-         GetVirtualObject(obj->GetReplacement())) {
-    obj = GetVirtualObject(obj->GetReplacement());
-  }
-  return obj;
-}
-
-
 VirtualObject* VirtualState::GetOrCreateTrackedVirtualObject(NodeId id,
                                                              Zone* zone) {
   if (VirtualObject* obj = GetVirtualObject(id)) {
     return obj;
   }
   VirtualObject* obj = new (zone) VirtualObject(id, zone, 0);
   SetVirtualObject(id, obj);
   return obj;
 }
 
@@ skipping 100 matching lines @@
   Node* rep = objs.front()->GetField(pos);
   for (VirtualObject* obj : objs) {
     if (obj->GetField(pos) != rep) {
       return nullptr;
     }
   }
   return rep;
 }
 
 
-Node* GetReplacementIfSame(ZoneVector<VirtualObject*>& objs) {
-  Node* rep = objs.front()->GetReplacement();
-  for (VirtualObject* obj : objs) {
-    if (obj->GetReplacement() != rep) {
-      return nullptr;
-    }
-  }
-  return rep;
-}
-
-
 void GetFields(ZoneVector<VirtualObject*>& objs, ZoneVector<Node*>& fields,
                size_t pos) {
   fields.clear();
   for (VirtualObject* obj : objs) {
     if (Node* field = obj->GetField(pos)) {
       fields.push_back(field);
     }
   }
 }
 
@@ skipping 25 matching lines @@
     if (!IsEquivalentPhi(input, inputs[i])) {
       return false;
     }
   }
   return true;
 }
 
 }  // namespace
 
 
+Node* EscapeAnalysis::GetReplacementIfSame(ZoneVector<VirtualObject*>& objs) {
+  Node* rep = GetReplacement(objs.front()->id());
+  for (VirtualObject* obj : objs) {
+    if (GetReplacement(obj->id()) != rep) {
+      return nullptr;
+    }
+  }
+  return rep;
+}
+
+
 bool VirtualState::MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
                              CommonOperatorBuilder* common, Node* control) {
   DCHECK_GT(cache->states().size(), 0u);
   bool changed = false;
   for (NodeId id = 0; id < min_size(cache->states()); ++id) {
     GetVirtualObjects(cache->states(), cache->objects(), id);
     if (cache->objects().size() == cache->states().size()) {
       // Don't process linked objects.
       if (cache->objects()[0]->id() != id) continue;
       if (FLAG_trace_turbo_escape) {
         PrintF("  Merging virtual objects of #%d\n", id);
       }
       VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(id, zone);
-      mergeObject->SetReplacement(GetReplacementIfSame(cache->objects()));
       size_t fields = min_field_count(cache->objects());
       changed = mergeObject->ResizeFields(fields) || changed;
       for (size_t i = 0; i < fields; ++i) {
         if (Node* field = GetFieldIfSame(i, cache->objects())) {
           changed = mergeObject->SetField(i, field) || changed;
           if (FLAG_trace_turbo_escape) {
             PrintF("    Field %zu agree on rep #%d\n", i, field->id());
           }
         } else {
           GetFields(cache->objects(), cache->fields(), i);
@@ skipping 44 matching lines @@
     if (cache->objects().size() == cache->states().size()) {
       if (cache->objects()[0]->id() != id) {
         SetVirtualObject(id, GetVirtualObject(cache->objects()[0]->id()));
       }
     }
   }
   return changed;
 }
 
 
-Node* VirtualState::ResolveReplacement(Node* node) {
-  Node* replacement = node;
-  VirtualObject* obj = GetVirtualObject(node);
-  while (obj != nullptr && obj->GetReplacement()) {
-    replacement = obj->GetReplacement();
-    obj = GetVirtualObject(replacement);
-  }
-  return replacement;
-}
-
-
-bool VirtualState::UpdateReplacement(Node* node, Node* rep, Zone* zone) {
-  if (!GetVirtualObject(node)) {
-    if (rep) {
-      SetVirtualObject(node->id(), new (zone) VirtualObject(node->id(), zone));
-    } else {
-      return false;
-    }
-  }
-  if (GetVirtualObject(node)->SetReplacement(rep)) {
-    LastChangedAt(node);
-    if (FLAG_trace_turbo_escape) {
-      if (rep) {
-        PrintF("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(),
-               rep->op()->mnemonic());
-      } else {
-        PrintF("Replacement of #%d cleared\n", node->id());
-      }
-    }
-    return true;
-  }
-  return false;
-}
-
-
 // ------------------------------EscapeStatusAnalysis---------------------------
 
 
 EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis,
                                            Graph* graph, Zone* zone)
     : object_analysis_(object_analysis),
       graph_(graph),
       zone_(zone),
       info_(zone),
       queue_(zone) {
@@ skipping 80 matching lines @@
       ProcessFinishRegion(node);
       break;
     case IrOpcode::kStoreField:
       ProcessStoreField(node);
       break;
     case IrOpcode::kStoreElement:
       ProcessStoreElement(node);
       break;
     case IrOpcode::kLoadField:
     case IrOpcode::kLoadElement: {
-      if (Node* rep = object_analysis_->GetReplacement(node, node->id())) {
+      if (Node* rep = object_analysis_->GetReplacement(node->id())) {
         if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
           RevisitInputs(rep);
           RevisitUses(rep);
         }
       }
       break;
     }
     case IrOpcode::kPhi:
       if (!HasEntry(node)) {
         info_[node->id()] = kVirtual;
@@ skipping 152 matching lines @@
 
 // -----------------------------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_(zone) {}
 
 
 EscapeAnalysis::~EscapeAnalysis() {}
 
 
 void EscapeAnalysis::Run() {
+  replacements_.resize(graph()->NodeCount());
   RunObjectAnalysis();
   escape_status_.Run();
 }
 
 
 void EscapeAnalysis::RunObjectAnalysis() {
   virtual_states_.resize(graph()->NodeCount());
   ZoneVector<Node*> stack(zone());
   stack.push_back(graph()->start());
   while (!stack.empty()) {
@@ skipping 101 matching lines @@
       case IrOpcode::kLoadField:
       case IrOpcode::kStoreElement:
       case IrOpcode::kLoadElement:
       case IrOpcode::kFrameState:
       case IrOpcode::kStateValues:
       case IrOpcode::kReferenceEqual:
       case IrOpcode::kFinishRegion:
       case IrOpcode::kPhi:
         break;
       default:
-        VirtualState* states = virtual_states_[node->id()];
-        if (VirtualObject* obj = states->ResolveVirtualObject(input)) {
+        VirtualState* state = virtual_states_[node->id()];
+        if (VirtualObject* obj = ResolveVirtualObject(state, input)) {
           if (obj->ClearAllFields()) {
-            states->LastChangedAt(node);
+            state->LastChangedAt(node);
           }
         }
         break;
     }
   }
 }
 
 
 bool EscapeAnalysis::IsEffectBranchPoint(Node* node) {
   int count = 0;
@@ skipping 148 matching lines @@
       if (FLAG_trace_turbo_escape) {
         PrintF("Linked finish region node #%d to node #%d\n", node->id(),
                allocation->id());
       }
       states->LastChangedAt(node);
     }
   }
 }
 
 
-Node* EscapeAnalysis::GetReplacement(Node* at, NodeId id) {
-  VirtualState* states = virtual_states_[at->id()];
-  if (VirtualObject* obj = states->GetVirtualObject(id)) {
-    return obj->GetReplacement();
-  }
-  return nullptr;
+Node* EscapeAnalysis::replacement(NodeId id) {
+  if (id >= replacements_.size()) return nullptr;
+  return replacements_[id];
 }
 
 
+Node* EscapeAnalysis::replacement(Node* node) {
+  return replacement(node->id());
+}
+
+
+bool EscapeAnalysis::SetReplacement(Node* node, Node* rep) {
+  bool changed = replacements_[node->id()] != rep;
+  replacements_[node->id()] = rep;
+  return changed;
+}
+
+
+bool EscapeAnalysis::UpdateReplacement(VirtualState* state, Node* node,
+                                       Node* rep) {
+  if (SetReplacement(node, rep)) {
+    state->LastChangedAt(node);
+    if (FLAG_trace_turbo_escape) {
+      if (rep) {
+        PrintF("Replacement of #%d is #%d (%s)\n", node->id(), rep->id(),
+               rep->op()->mnemonic());
+      } else {
+        PrintF("Replacement of #%d cleared\n", node->id());
+      }
+    }
+    return true;
+  }
+  return false;
+}
+
+
+Node* EscapeAnalysis::ResolveReplacement(Node* node) {
+  while (replacement(node)) {
+    node = replacement(node);
+  }
+  return node;
+}
+
+
+Node* EscapeAnalysis::GetReplacement(NodeId id) {
+  Node* node = nullptr;
+  while (replacement(id)) {
+    node = replacement(id);
+    id = node->id();
+  }
+  return node;
+}
+
+
 bool EscapeAnalysis::IsVirtual(Node* node) {
   return escape_status_.IsVirtual(node);
 }
 
 
 bool EscapeAnalysis::IsEscaped(Node* node) {
   return escape_status_.IsEscaped(node);
 }
 
 
 bool EscapeAnalysis::SetEscaped(Node* node) {
   return escape_status_.SetEscaped(node);
 }
 
 
 VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) {
   if (VirtualState* states = virtual_states_[at->id()]) {
     return states->GetVirtualObject(id);
   }
   return nullptr;
 }
 
 
+VirtualObject* EscapeAnalysis::ResolveVirtualObject(VirtualState* state,
+                                                    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;
+}
+
+
 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());
   }
 
   ZoneVector<Node*> inputs(zone());
   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
     Node* input = NodeProperties::GetValueInput(node, i);
     inputs.push_back(input);
   }
 
   GetVirtualObjects(state, inputs, cache_.objects());
   if (cache_.objects().size() == inputs.size()) {
     GetFields(cache_.objects(), cache_.fields(), offset);
     if (cache_.fields().size() == cache_.objects().size()) {
-      if (!state->GetVirtualObject(node)) {
-        state->SetVirtualObject(node->id(),
-                                new (zone()) VirtualObject(node->id(), zone()));
-      }
-      Node* rep = state->GetVirtualObject(node)->GetReplacement();
+      Node* rep = replacement(node);
       if (!rep || !IsEquivalentPhi(rep, cache_.fields())) {
         cache_.fields().push_back(NodeProperties::GetControlInput(from));
         Node* phi = graph()->NewNode(
             common()->Phi(MachineRepresentation::kTagged, 2),
             static_cast<int>(cache_.fields().size()), &cache_.fields().front());
-        state->GetVirtualObject(node)->SetReplacement(phi);
+        SetReplacement(node, phi);
         state->LastChangedAt(node);
         if (FLAG_trace_turbo_escape) {
           PrintF(" got phi created.\n");
         }
       } else if (FLAG_trace_turbo_escape) {
         PrintF(" has already phi #%d.\n", rep->id());
       }
     } else if (FLAG_trace_turbo_escape) {
       PrintF(" has incomplete field info.\n");
     }
   } else if (FLAG_trace_turbo_escape) {
     PrintF(" has incomplete virtual object info.\n");
   }
 }
 
 
 void EscapeAnalysis::ProcessLoadField(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kLoadField);
   ForwardVirtualState(node);
   Node* from = NodeProperties::GetValueInput(node, 0);
   VirtualState* state = virtual_states_[node->id()];
-  if (VirtualObject* object = state->ResolveVirtualObject(from)) {
+  if (VirtualObject* object = ResolveVirtualObject(state, from)) {
     int offset = OffsetFromAccess(node);
     if (!object->IsTracked()) return;
     Node* value = object->GetField(offset);
     if (value) {
-      value = state->ResolveReplacement(value);
+      value = ResolveReplacement(value);
     }
     // Record that the load has this alias.
-    state->UpdateReplacement(node, value, zone());
+    UpdateReplacement(state, node, value);
   } else {
-    if (from->opcode() == IrOpcode::kPhi) {
+    if (from->opcode() == IrOpcode::kPhi &&
+        OpParameter<FieldAccess>(node).offset % kPointerSize == 0) {
       int offset = OffsetFromAccess(node);
       // Only binary phis are supported for now.
       ProcessLoadFromPhi(offset, from, node, state);
     }
   }
 }
 
 
 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);
   ElementAccess access = OpParameter<ElementAccess>(node);
   if (index.HasValue()) {
     int offset = index.Value() + access.header_size / kPointerSize;
-    if (VirtualObject* object = state->ResolveVirtualObject(from)) {
+    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);
       if (value) {
-        value = state->ResolveReplacement(value);
+        value = ResolveReplacement(value);
       }
       // Record that the load has this alias.
-      state->UpdateReplacement(node, value, zone());
+      UpdateReplacement(state, node, value);
     } else if (from->opcode() == IrOpcode::kPhi) {
       ElementAccess access = OpParameter<ElementAccess>(node);
       int offset = index.Value() + access.header_size / kPointerSize;
       ProcessLoadFromPhi(offset, from, node, state);
     }
   } else {
     // We have a load from a non-const index, cannot eliminate object.
     if (SetEscaped(from)) {
       if (FLAG_trace_turbo_escape) {
         PrintF(
             "Setting #%d (%s) to escaped because store element #%d to "
             "non-const "
             "index #%d (%s)\n",
             from->id(), from->op()->mnemonic(), node->id(), index_node->id(),
             index_node->op()->mnemonic());
       }
     }
   }
 }
 
 
 void EscapeAnalysis::ProcessStoreField(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kStoreField);
   ForwardVirtualState(node);
   Node* to = NodeProperties::GetValueInput(node, 0);
   Node* val = NodeProperties::GetValueInput(node, 1);
-  int offset = OffsetFromAccess(node);
-  VirtualState* states = virtual_states_[node->id()];
-  if (VirtualObject* obj = states->ResolveVirtualObject(to)) {
+  VirtualState* state = virtual_states_[node->id()];
+  if (VirtualObject* obj = ResolveVirtualObject(state, to)) {
     if (!obj->IsTracked()) return;
-    if (obj->SetField(offset, states->ResolveReplacement(val))) {
-      states->LastChangedAt(node);
+    int offset = OffsetFromAccess(node);
+    if (obj->SetField(offset, ResolveReplacement(val))) {
+      state->LastChangedAt(node);
     }
   }
 }
 
 
 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);
   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 = states->ResolveVirtualObject(to)) {
+    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);
-      if (obj->SetField(offset, states->ResolveReplacement(val))) {
+      if (obj->SetField(offset, ResolveReplacement(val))) {
         states->LastChangedAt(node);
       }
     }
   } else {
     // We have a store to a non-const index, cannot eliminate object.
     if (SetEscaped(to)) {
       if (FLAG_trace_turbo_escape) {
         PrintF(
             "Setting #%d (%s) to escaped because store element #%d to "
             "non-const "
             "index #%d (%s)\n",
             to->id(), to->op()->mnemonic(), node->id(), index_node->id(),
             index_node->op()->mnemonic());
       }
     }
   }
 }
 
 
 void EscapeAnalysis::DebugPrintObject(VirtualObject* object, NodeId id) {
-  PrintF("  Object #%d with %zu fields", id, object->field_count());
-  if (Node* rep = object->GetReplacement()) {
-    PrintF(", rep = #%d (%s)", rep->id(), rep->op()->mnemonic());
-  }
-  PrintF("\n");
+  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());
     }
   }
 }
 
 
 void EscapeAnalysis::DebugPrintState(VirtualState* state) {
   PrintF("Dumping object state %p\n", static_cast<void*>(state));
@@ skipping 20 matching lines @@
     }
   }
   for (size_t n = 0; n < object_states.size(); n++) {
     DebugPrintState(object_states[n]);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8