[turbofan] Performance enhancements 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 <limits>
+
 #include "src/compiler/escape-analysis.h"

[Michael Starzinger, 2016/01/12 17:27:43]

nit: Let's keep the "escape-analysis.h" include at the top as per style-guide
recommendation.

https://google.github.io/styleguide/cppguide.html#Names_and_Order_of_Includes

 
 #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/operator-properties.h"
 #include "src/compiler/simplified-operator.h"
 #include "src/objects-inl.h"
 #include "src/type-cache.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
+const EscapeAnalysis::Alias EscapeAnalysis::kNotReachable =
+    std::numeric_limits<Alias>::max();
+const EscapeAnalysis::Alias EscapeAnalysis::kUntrackable =
+    std::numeric_limits<Alias>::max() - 1;
+
+
 class VirtualObject : public ZoneObject {
  public:
   enum Status { kUntracked = 0, kTracked = 1 };
   VirtualObject(NodeId id, Zone* zone)
       : id_(id),
         status_(kUntracked),
         fields_(zone),
         phi_(zone),
         object_state_(nullptr) {}
 
@@ skipping 57 matching lines @@
       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_; }
+  Node* GetObjectState() const { return object_state_; }
 
-  NodeId id() { return id_; }
+  NodeId id() const { return id_; }
   void id(NodeId id) { id_ = id; }
 
  private:
   NodeId id_;
   Status status_;
   ZoneVector<Node*> fields_;
   ZoneVector<bool> phi_;
   Node* object_state_;
 };
 
@@ skipping 13 matching lines @@
   }
   return changed;
 }
 
 
 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);
+  VirtualObject* VirtualObjectFromAlias(size_t alias);
+  VirtualObject* GetOrCreateTrackedVirtualObject(EscapeAnalysis::Alias alias,
+                                                 NodeId id, Zone* zone);
+  void SetVirtualObject(EscapeAnalysis::Alias alias, VirtualObject* state);
   void LastChangedAt(Node* node) { last_changed_ = node; }
   Node* GetLastChanged() { return last_changed_; }
-  bool UpdateFrom(NodeId id, VirtualObject* state, 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(); }
+  size_t size() const { return info_.size(); }
 
  private:
   ZoneVector<VirtualObject*> info_;
   Node* last_changed_;
 };
 
 
 class MergeCache : public ZoneObject {
  public:
   explicit MergeCache(Zone* zone)
-      : states_(zone), objects_(zone), fields_(zone), min_size_(SIZE_MAX) {
+      : states_(zone), objects_(zone), fields_(zone) {
     states_.reserve(4);
     objects_.reserve(4);
     fields_.reserve(4);
   }
   ZoneVector<VirtualState*>& states() { return states_; }
   ZoneVector<VirtualObject*>& objects() { return objects_; }
   ZoneVector<Node*>& fields() { return fields_; }
   void Clear() {
     states_.clear();
     objects_.clear();
     fields_.clear();
-    min_size_ = SIZE_MAX;
   }
-  void push_back(VirtualState* state) {
-    states_.push_back(state);
-    min_size_ = std::min(state->size(), min_size_);
-  }
-  size_t min_size() { return min_size_; }
-
-  size_t LoadVirtualObjectsFromStatesFor(NodeId id);
-  void LoadVirtualObjectsForFieldsFrom(VirtualState* state);
+  size_t LoadVirtualObjectsFromStatesFor(EscapeAnalysis::Alias alias);
+  void LoadVirtualObjectsForFieldsFrom(
+      VirtualState* state, const ZoneVector<EscapeAnalysis::Alias>& aliases);
   Node* GetFields(size_t pos);
 
  private:
   ZoneVector<VirtualState*> states_;
   ZoneVector<VirtualObject*> objects_;
   ZoneVector<Node*> fields_;
-  size_t min_size_;
 };
 
 
-size_t MergeCache::LoadVirtualObjectsFromStatesFor(NodeId id) {
+size_t MergeCache::LoadVirtualObjectsFromStatesFor(
+    EscapeAnalysis::Alias alias) {
   objects_.clear();
   DCHECK_GT(states_.size(), 0u);
-  size_t min = SIZE_MAX;
+  size_t min = std::numeric_limits<size_t>::max();
   for (VirtualState* state : states_) {
-    if (VirtualObject* obj = state->GetVirtualObject(id)) {
+    if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
       objects_.push_back(obj);
       min = std::min(obj->field_count(), min);
     }
   }
   return min;
 }
 
 
-void MergeCache::LoadVirtualObjectsForFieldsFrom(VirtualState* state) {
+void MergeCache::LoadVirtualObjectsForFieldsFrom(
+    VirtualState* state, const ZoneVector<EscapeAnalysis::Alias>& aliases) {
   objects_.clear();
+  size_t max_alias = state->size();
   for (Node* field : fields_) {
-    if (VirtualObject* obj = state->GetVirtualObject(field)) {
+    EscapeAnalysis::Alias alias = aliases[field->id()];
+    if (alias >= max_alias) continue;
+    if (VirtualObject* obj = state->VirtualObjectFromAlias(alias)) {
       objects_.push_back(obj);
     }
   }
 }
 
 
 Node* MergeCache::GetFields(size_t pos) {
   fields_.clear();
   Node* rep = objects_.front()->GetField(pos);
   for (VirtualObject* obj : objects_) {
@@ skipping 10 matching lines @@
 
 
 VirtualState::VirtualState(Zone* zone, size_t size)
     : info_(size, nullptr, zone), last_changed_(nullptr) {}
 
 
 VirtualState::VirtualState(const VirtualState& state)
     : info_(state.info_.size(), nullptr, state.info_.get_allocator().zone()),
       last_changed_(state.last_changed_) {
   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()];
+    if (state.info_[i]) {
+      info_[i] =
+          new (info_.get_allocator().zone()) VirtualObject(*state.info_[i]);
     }
   }
 }
 
 
-VirtualObject* VirtualState::GetVirtualObject(size_t id) {
-  if (id >= info_.size()) return nullptr;
-  return info_[id];
+VirtualObject* VirtualState::VirtualObjectFromAlias(size_t alias) {
+  return info_[alias];
 }
 
 
-VirtualObject* VirtualState::GetVirtualObject(Node* node) {
-  return GetVirtualObject(node->id());
-}
-
-
-VirtualObject* VirtualState::GetOrCreateTrackedVirtualObject(NodeId id,
-                                                             Zone* zone) {
-  if (VirtualObject* obj = GetVirtualObject(id)) {
+VirtualObject* VirtualState::GetOrCreateTrackedVirtualObject(
+    EscapeAnalysis::Alias alias, NodeId id, Zone* zone) {
+  if (VirtualObject* obj = VirtualObjectFromAlias(alias)) {
     return obj;
   }
   VirtualObject* obj = new (zone) VirtualObject(id, zone, 0);
-  SetVirtualObject(id, obj);
+  SetVirtualObject(alias, obj);
   return obj;
 }
 
 
-void VirtualState::SetVirtualObject(NodeId id, VirtualObject* obj) {
-  info_[id] = obj;
-}
-
-
-bool VirtualState::UpdateFrom(NodeId id, VirtualObject* fromObj, Zone* zone) {
-  VirtualObject* obj = GetVirtualObject(id);
-  if (!obj) {
-    obj = new (zone) VirtualObject(*fromObj);
-    SetVirtualObject(id, obj);
-    if (FLAG_trace_turbo_escape) {
-      PrintF("  Taking field for #%d from %p\n", id,
-             static_cast<void*>(fromObj));
-    }
-    return true;
-  }
-
-  if (obj->UpdateFrom(*fromObj)) {
-    if (FLAG_trace_turbo_escape) {
-      PrintF("  Updating field for #%d from %p\n", id,
-             static_cast<void*>(fromObj));
-    }
-    return true;
-  }
-
-  return false;
+void VirtualState::SetVirtualObject(EscapeAnalysis::Alias alias,
+                                    VirtualObject* obj) {
+  info_[alias] = obj;
 }
 
 
 bool VirtualState::UpdateFrom(VirtualState* from, Zone* zone) {
   bool changed = false;
-  for (NodeId id = 0; id < size(); ++id) {
-    VirtualObject* ls = GetVirtualObject(id);
-    VirtualObject* rs = from->GetVirtualObject(id);
+  for (EscapeAnalysis::Alias alias = 0; alias < size(); ++alias) {
+    VirtualObject* ls = VirtualObjectFromAlias(alias);
+    VirtualObject* rs = from->VirtualObjectFromAlias(alias);
 
     if (rs == nullptr) {
       continue;
     }
 
     if (ls == nullptr) {
       ls = new (zone) VirtualObject(*rs);
-      SetVirtualObject(id, ls);
+      SetVirtualObject(alias, ls);
       changed = true;
       continue;
     }
 
     if (FLAG_trace_turbo_escape) {
-      PrintF("  Updating fields of #%d\n", id);
+      PrintF("  Updating fields of @%d\n", alias);
     }
 
     changed = ls->UpdateFrom(*rs) || changed;
   }
   return false;
 }
 
 
 namespace {
 
@@ skipping 39 matching lines @@
     }
   }
   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 < cache->min_size(); ++id) {
-    size_t fields = cache->LoadVirtualObjectsFromStatesFor(id);
+  for (EscapeAnalysis::Alias alias = 0; alias < size(); ++alias) {
+    size_t fields = cache->LoadVirtualObjectsFromStatesFor(alias);
     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);
+        PrintF("  Merging virtual objects of @%d\n", alias);
       }
-      VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(id, zone);
+      VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(
+          alias, cache->objects().front()->id(), zone);
       changed = mergeObject->ResizeFields(fields) || changed;
       for (size_t i = 0; i < fields; ++i) {
         if (Node* field = cache->GetFields(i)) {
           changed = mergeObject->SetField(i, field) || changed;
           if (FLAG_trace_turbo_escape) {
             PrintF("    Field %zu agree on rep #%d\n", i, field->id());
           }
         } else {
           int value_input_count = static_cast<int>(cache->fields().size());
           if (cache->fields().size() == cache->objects().size()) {
@@ skipping 38 matching lines @@
                     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()));
-      }
+      SetVirtualObject(alias, nullptr);
     }
   }
   return changed;
 }
 
 
 EscapeStatusAnalysis::EscapeStatusAnalysis(EscapeAnalysis* object_analysis,
                                            Graph* graph, Zone* zone)
     : object_analysis_(object_analysis),
       graph_(graph),
       zone_(zone),
-      info_(graph->NodeCount(), kUnknown, zone),
+      status_(graph->NodeCount(), kUnknown, zone),
       queue_(zone) {}
 
 
 EscapeStatusAnalysis::~EscapeStatusAnalysis() {}
 
 
 bool EscapeStatusAnalysis::HasEntry(Node* node) {
-  return info_[node->id()] != kUnknown;
+  return status_[node->id()] & (kTracked | kEscaped);
 }
 
 
 bool EscapeStatusAnalysis::IsVirtual(Node* node) {
-  return info_[node->id()] == kVirtual;
+  return (status_[node->id()] & kTracked) && !(status_[node->id()] & kEscaped);
 }
 
 
 bool EscapeStatusAnalysis::IsEscaped(Node* node) {
-  return info_[node->id()] == kEscaped;
+  return status_[node->id()] & kEscaped;
 }
 
 
 bool EscapeStatusAnalysis::IsAllocation(Node* node) {
   return node->opcode() == IrOpcode::kAllocate ||
          node->opcode() == IrOpcode::kFinishRegion;
 }
 
 
 bool EscapeStatusAnalysis::SetEscaped(Node* node) {
-  bool changed = info_[node->id()] != kEscaped;
-  info_[node->id()] = kEscaped;
+  bool changed = !(status_[node->id()] & kEscaped);
+  status_[node->id()] |= kEscaped | kTracked;
   return changed;
 }
 
 
 void EscapeStatusAnalysis::Resize() {
-  info_.resize(graph()->NodeCount(), kUnknown);
+  status_.resize(graph()->NodeCount(), kUnknown);
 }
 
 
-size_t EscapeStatusAnalysis::size() { return info_.size(); }
+size_t EscapeStatusAnalysis::size() { return status_.size(); }
 
 
 void EscapeStatusAnalysis::Run() {
   Resize();
-  ZoneVector<bool> visited(zone());
-  visited.resize(graph()->NodeCount());
   queue_.push_back(graph()->end());
+  status_[graph()->end()->id()] |= kOnStack;
   while (!queue_.empty()) {
     Node* node = queue_.front();
     queue_.pop_front();
+    status_[node->id()] = EscapeStatusFlags(status_[node->id()] & ~kOnStack);

[Michael Starzinger, 2016/01/12 17:27:43]

nit: Would "status_[node->id()] &= ~kOnStack" do the trick here?

     Process(node);
-    if (!visited[node->id()]) {
-      RevisitInputs(node);
+    status_[node->id()] |= kVisited;
+    for (Edge edge : node->input_edges()) {
+      Node* input = edge.to();
+      if (!(status_[input->id()] & (kVisited | kOnStack))) {
+        queue_.push_back(input);
+        status_[input->id()] |= kOnStack;
+      }
     }
-    visited[node->id()] = true;
-  }
-  if (FLAG_trace_turbo_escape) {
-    DebugPrint();
   }
 }
 
 
 void EscapeStatusAnalysis::RevisitInputs(Node* node) {
   for (Edge edge : node->input_edges()) {
     Node* input = edge.to();
-    queue_.push_back(input);
+    if (!(status_[input->id()] & kOnStack)) {
+      queue_.push_back(input);
+      status_[input->id()] |= kOnStack;
+    }
   }
 }
 
 
 void EscapeStatusAnalysis::RevisitUses(Node* node) {
   for (Edge edge : node->use_edges()) {
     Node* use = edge.from();
-    queue_.push_back(use);
+    if (!(status_[use->id()] & kOnStack)) {
+      queue_.push_back(use);
+      status_[use->id()] |= kOnStack;
+    }
   }
 }
 
 
 void EscapeStatusAnalysis::Process(Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kAllocate:
       ProcessAllocate(node);
       break;
     case IrOpcode::kFinishRegion:
@@ skipping 10 matching lines @@
       if (Node* rep = object_analysis_->GetReplacement(node)) {
         if (IsAllocation(rep) && CheckUsesForEscape(node, rep)) {
           RevisitInputs(rep);
           RevisitUses(rep);
         }
       }
       break;
     }
     case IrOpcode::kPhi:
       if (!HasEntry(node)) {
-        info_[node->id()] = kVirtual;
+        status_[node->id()] |= kTracked;
         if (!IsAllocationPhi(node)) {
           SetEscaped(node);
           RevisitUses(node);
         }
       }
       CheckUsesForEscape(node);
     default:
       break;
   }
 }
@@ skipping 36 matching lines @@
       PrintF("Setting #%d (%s) to escaped because of store to field of #%d\n",
              val->id(), val->op()->mnemonic(), to->id());
     }
   }
 }
 
 
 void EscapeStatusAnalysis::ProcessAllocate(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
   if (!HasEntry(node)) {
-    info_[node->id()] = kVirtual;
+    status_[node->id()] |= kTracked;
     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;
     }
   }
   if (CheckUsesForEscape(node, true)) {
     RevisitUses(node);
   }
 }
 
 
 bool EscapeStatusAnalysis::CheckUsesForEscape(Node* uses, Node* rep,
                                               bool phi_escaping) {
   for (Edge edge : uses->use_edges()) {
     Node* use = edge.from();
-    if (!NodeProperties::IsValueEdge(edge) &&
-        !NodeProperties::IsContextEdge(edge))
+    if (edge.index() >= use->op()->ValueInputCount() +
+                            OperatorProperties::GetContextInputCount(use->op()))
       continue;
     switch (use->opcode()) {
+      case IrOpcode::kPhi:
+        if (phi_escaping && SetEscaped(rep)) {
+          if (FLAG_trace_turbo_escape) {
+            PrintF(
+                "Setting #%d (%s) to escaped because of use by phi node "
+                "#%d (%s)\n",
+                rep->id(), rep->op()->mnemonic(), use->id(),
+                use->op()->mnemonic());
+          }
+          return true;
+        }
+      // Fallthrough.
       case IrOpcode::kStoreField:
       case IrOpcode::kLoadField:
       case IrOpcode::kStoreElement:
       case IrOpcode::kLoadElement:
       case IrOpcode::kFrameState:
       case IrOpcode::kStateValues:
       case IrOpcode::kReferenceEqual:
       case IrOpcode::kFinishRegion:
-      case IrOpcode::kPhi:
-        if (HasEntry(use) && IsEscaped(use) && SetEscaped(rep)) {
+        if (IsEscaped(use) && SetEscaped(rep)) {
           if (FLAG_trace_turbo_escape) {
             PrintF(
                 "Setting #%d (%s) to escaped because of use by escaping node "
                 "#%d (%s)\n",
                 rep->id(), rep->op()->mnemonic(), use->id(),
                 use->op()->mnemonic());
-          }
-          return true;
-        }
-        if (phi_escaping && use->opcode() == IrOpcode::kPhi &&
-            SetEscaped(rep)) {
-          if (FLAG_trace_turbo_escape) {
-            PrintF(
-                "Setting #%d (%s) to escaped because of use by phi node "
-                "#%d (%s)\n",
-                rep->id(), rep->op()->mnemonic(), use->id(),
-                use->op()->mnemonic());
           }
           return true;
         }
         break;
       case IrOpcode::kObjectIsSmi:
         if (!IsAllocation(rep) && SetEscaped(rep)) {
           PrintF("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
                  rep->id(), rep->op()->mnemonic(), use->id(),
                  use->op()->mnemonic());
           return true;
@@ skipping 16 matching lines @@
         }
     }
   }
   return false;
 }
 
 
 void EscapeStatusAnalysis::ProcessFinishRegion(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
   if (!HasEntry(node)) {
-    info_[node->id()] = kVirtual;
+    status_[node->id()] |= kTracked;
     RevisitUses(node);
   }
   if (CheckUsesForEscape(node, true)) {
     RevisitInputs(node);
   }
 }
 
 
 void EscapeStatusAnalysis::DebugPrint() {
-  for (NodeId id = 0; id < info_.size(); id++) {
-    if (info_[id] != kUnknown) {
+  for (NodeId id = 0; id < status_.size(); id++) {
+    if (status_[id] & kTracked) {
       PrintF("Node #%d is %s\n", id,
-             info_[id] == kEscaped ? "escaping" : "virtual");
+             (status_[id] & kEscaped) ? "escaping" : "virtual");
     }
   }
 }
 
 
 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)) {}
+      cache_(new (zone) MergeCache(zone)),
+      aliases_(zone),
+      next_free_alias_(0) {}
 
 
 EscapeAnalysis::~EscapeAnalysis() {}
 
 
 void EscapeAnalysis::Run() {
   replacements_.resize(graph()->NodeCount());
+  AssignAliases();
   RunObjectAnalysis();
   escape_status_.Run();
 }
 
 
+void EscapeAnalysis::AssignAliases() {
+  ZoneVector<Node*> stack(zone());
+  stack.push_back(graph()->end());
+  CHECK_LT(graph()->NodeCount(), kUntrackable);
+  aliases_.resize(graph()->NodeCount(), kNotReachable);
+  aliases_[graph()->end()->id()] = kUntrackable;
+  while (!stack.empty()) {
+    Node* node = stack.back();
+    stack.pop_back();
+    switch (node->opcode()) {
+      case IrOpcode::kAllocate:
+        if (aliases_[node->id()] >= kUntrackable) {
+          aliases_[node->id()] = NextAlias();
+        }
+        break;
+      case IrOpcode::kFinishRegion: {
+        Node* allocate = NodeProperties::GetValueInput(node, 0);
+        if (allocate->opcode() == IrOpcode::kAllocate) {
+          if (aliases_[allocate->id()] >= kUntrackable) {
+            if (aliases_[allocate->id()] == kNotReachable) {
+              stack.push_back(allocate);
+            }
+            aliases_[allocate->id()] = NextAlias();
+          }
+          aliases_[node->id()] = aliases_[allocate->id()];
+        } else {
+          aliases_[node->id()] = NextAlias();
+        }
+      } break;

[Michael Starzinger, 2016/01/12 17:27:43]

nit: Funny formatting, I actually like it, but V8 uses different style.

+      default:
+        DCHECK_EQ(aliases_[node->id()], kUntrackable);
+        break;
+    }
+    for (Edge edge : node->input_edges()) {
+      Node* input = edge.to();
+      if (aliases_[input->id()] == kNotReachable) {
+        stack.push_back(input);
+        aliases_[input->id()] = kUntrackable;
+      }
+    }
+  }
+
+  if (FLAG_trace_turbo_escape) {
+    PrintF("Discovered trackable nodes");
+    for (EscapeAnalysis::Alias id = 0; id < graph()->NodeCount(); ++id) {
+      if (aliases_[id] < kUntrackable) {
+        if (FLAG_trace_turbo_escape) {
+          PrintF(" #%u", id);
+        }
+      }
+    }
+    PrintF("\n");
+  }
+}
+
+
 void EscapeAnalysis::RunObjectAnalysis() {
   virtual_states_.resize(graph()->NodeCount());
   ZoneVector<Node*> stack(zone());
   stack.push_back(graph()->start());
   while (!stack.empty()) {
     Node* node = stack.back();
     stack.pop_back();
-    if (Process(node)) {
+    if (aliases_[node->id()] != kNotReachable && Process(node)) {
       for (Edge edge : node->use_edges()) {
         if (NodeProperties::IsEffectEdge(edge)) {
           Node* use = edge.from();
           if ((use->opcode() != IrOpcode::kLoadField &&
                use->opcode() != IrOpcode::kLoadElement) ||
               !IsDanglingEffectNode(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 ||
                use->opcode() == IrOpcode::kLoadElement) &&
-
-
               IsDanglingEffectNode(use)) {
             stack.push_back(use);
           }
         }
       }
     }
   }
   if (FLAG_trace_turbo_escape) {
     DebugPrint();
   }
@@ skipping 109 matching lines @@
       node->opcode() != IrOpcode::kLoad && IsDanglingEffectNode(node)) {
     PrintF("Dangeling effect node: #%d (%s)\n", node->id(),
            node->op()->mnemonic());
     UNREACHABLE();
   }
   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());
+          new (zone()) VirtualState(zone(), AliasCount());
     }
   }
   DCHECK_NOT_NULL(virtual_states_[effect->id()]);
   if (IsEffectBranchPoint(effect)) {
     if (FLAG_trace_turbo_escape) {
       PrintF("Copying object state %p from #%d (%s) to #%d (%s)\n",
              static_cast<void*>(virtual_states_[effect->id()]), effect->id(),
              effect->op()->mnemonic(), node->id(), node->op()->mnemonic());
     }
     if (!virtual_states_[node->id()]) {
       virtual_states_[node->id()] =
           new (zone()) VirtualState(*virtual_states_[effect->id()]);
     } else {
       virtual_states_[node->id()]->UpdateFrom(virtual_states_[effect->id()],
                                               zone());
     }
   } else {
     virtual_states_[node->id()] = virtual_states_[effect->id()];
     if (FLAG_trace_turbo_escape) {
       PrintF("Forwarding object state %p from #%d (%s) to #%d (%s)\n",
              static_cast<void*>(virtual_states_[effect->id()]), effect->id(),
              effect->op()->mnemonic(), node->id(), node->op()->mnemonic());
     }
   }
 }
 
 
 void EscapeAnalysis::ProcessStart(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kStart);
-  virtual_states_[node->id()] =
-      new (zone()) VirtualState(zone(), graph()->NodeCount());
+  virtual_states_[node->id()] = new (zone()) VirtualState(zone(), AliasCount());
 }
 
 
 bool EscapeAnalysis::ProcessEffectPhi(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kEffectPhi);
   bool changed = false;
 
   VirtualState* mergeState = virtual_states_[node->id()];
   if (!mergeState) {
-    mergeState = new (zone()) VirtualState(zone(), graph()->NodeCount());
+    mergeState = new (zone()) VirtualState(zone(), AliasCount());
     virtual_states_[node->id()] = mergeState;
     changed = true;
     if (FLAG_trace_turbo_escape) {
       PrintF("Effect Phi #%d got new states map %p.\n", node->id(),
              static_cast<void*>(mergeState));
     }
   } else if (mergeState->GetLastChanged() != node) {
     changed = true;
   }
 
   cache_->Clear();
 
   if (FLAG_trace_turbo_escape) {
     PrintF("At Effect Phi #%d, merging states into %p:", node->id(),
            static_cast<void*>(mergeState));
   }
 
   for (int i = 0; i < node->op()->EffectInputCount(); ++i) {
     Node* input = NodeProperties::GetEffectInput(node, i);
     VirtualState* state = virtual_states_[input->id()];
     if (state) {
-      cache_->push_back(state);
+      cache_->states().push_back(state);
     }
     if (FLAG_trace_turbo_escape) {
       PrintF(" %p (from %d %s)", static_cast<void*>(state), input->id(),
              input->op()->mnemonic());
     }
   }
   if (FLAG_trace_turbo_escape) {
     PrintF("\n");
   }
 
@@ skipping 15 matching lines @@
   }
   return changed;
 }
 
 
 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;
+  if (virtual_states_[node->id()]->VirtualObjectFromAlias(
+          aliases_[node->id()])) {
+    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));
+        aliases_[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()));
+        aliases_[node->id()], new (zone()) VirtualObject(node->id(), zone()));
   }
   virtual_states_[node->id()]->LastChangedAt(node);
 }
 
 
 void EscapeAnalysis::ProcessFinishRegion(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
   ForwardVirtualState(node);
   Node* allocation = NodeProperties::GetValueInput(node, 0);
   if (allocation->opcode() == IrOpcode::kAllocate) {
-    VirtualState* states = virtual_states_[node->id()];
-    DCHECK_NOT_NULL(states->GetVirtualObject(allocation));
-    if (!states->GetVirtualObject(node->id())) {
-      states->SetVirtualObject(node->id(),
-                               states->GetVirtualObject(allocation));
+    VirtualState* state = virtual_states_[node->id()];
+    if (!state->VirtualObjectFromAlias(aliases_[node->id()])) {
+      VirtualObject* vobj_alloc =
+          state->VirtualObjectFromAlias(aliases_[allocation->id()]);
+      DCHECK_NOT_NULL(vobj_alloc);
+      state->SetVirtualObject(aliases_[node->id()], vobj_alloc);
       if (FLAG_trace_turbo_escape) {
         PrintF("Linked finish region node #%d to node #%d\n", node->id(),
                allocation->id());
       }
-      states->LastChangedAt(node);
+      state->LastChangedAt(node);
     }
   }
 }
 
 
 Node* EscapeAnalysis::replacement(NodeId id) {
   if (id >= replacements_.size()) return nullptr;
   return replacements_[id];
 }
 
@@ skipping 67 matching lines @@
 }
 
 
 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 states->VirtualObjectFromAlias(aliases_[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()));
+  VirtualObject* obj = GetVirtualObject(state, ResolveReplacement(node));
+  while (obj && replacement(obj->id())) {
+    if (VirtualObject* next = GetVirtualObject(state, replacement(obj->id()))) {
+      obj = next;
+    } else {
+      break;
+    }
   }
   return obj;
 }
 
 
 bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
   DCHECK(IsVirtual(left) && IsVirtual(right));
   left = ResolveReplacement(left);
   right = ResolveReplacement(right);
   if (IsEquivalentPhi(left, right)) {
@@ skipping 14 matching lines @@
   if (FLAG_trace_turbo_escape) {
     PrintF("Load #%d from phi #%d", node->id(), from->id());
   }
 
   cache_->fields().clear();
   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
     Node* input = NodeProperties::GetValueInput(node, i);
     cache_->fields().push_back(input);
   }
 
-  cache_->LoadVirtualObjectsForFieldsFrom(state);
+  cache_->LoadVirtualObjectsForFieldsFrom(state, aliases_);
   if (cache_->objects().size() == cache_->fields().size()) {
     cache_->GetFields(offset);
     if (cache_->fields().size() == cache_->objects().size()) {
       Node* rep = replacement(node);
       if (!rep || !IsEquivalentPhi(rep, cache_->fields())) {
         int value_input_count = static_cast<int>(cache_->fields().size());
         cache_->fields().push_back(NodeProperties::GetControlInput(from));
         Node* phi = graph()->NewNode(
             common()->Phi(MachineRepresentation::kTagged, value_input_count),
             value_input_count + 1, &cache_->fields().front());
@@ skipping 181 matching lines @@
           }
         }
         return new_object_state;
       }
     }
   }
   return nullptr;
 }
 
 
-void EscapeAnalysis::DebugPrintObject(VirtualObject* object, NodeId id) {
-  PrintF("  Object #%d with %zu fields\n", id, object->field_count());
+void EscapeAnalysis::DebugPrintObject(VirtualObject* object, Alias alias) {
+  PrintF("  Alias @%d: Object #%d with %zu fields\n", alias, object->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));
-  for (size_t id = 0; id < state->size(); id++) {
-    if (VirtualObject* object = state->GetVirtualObject(id)) {
-      if (object->id() == id) {
-        DebugPrintObject(object, static_cast<int>(id));
-      } else {
-        PrintF("  Object #%zu links to object #%d\n", id, object->id());
-      }
+  for (Alias alias = 0; alias < AliasCount(); ++alias) {
+    if (VirtualObject* object = state->VirtualObjectFromAlias(alias)) {
+      DebugPrintObject(object, alias);
     }
   }
 }
 
 
 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++) {
     DebugPrintState(object_states[n]);
   }
 }
 
+
+VirtualObject* EscapeAnalysis::GetVirtualObject(VirtualState* state,
+                                                Node* node) {
+  if (node->id() >= aliases_.size()) return nullptr;
+  Alias alias = aliases_[node->id()];
+  if (alias >= state->size()) return nullptr;
+  return state->VirtualObjectFromAlias(alias);
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8