[turbofan] Fix bugs in 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 <limits>
 
 #include "src/base/flags.h"
 #include "src/bootstrapper.h"
@@ skipping 106 matching lines @@
   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_;
+  phi_ = other.phi_;
   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;
 }
 
 
 class VirtualState : public ZoneObject {
  public:
   VirtualState(Zone* zone, size_t size);
   VirtualState(const VirtualState& states);
 
   VirtualObject* VirtualObjectFromAlias(size_t alias);
   VirtualObject* GetOrCreateTrackedVirtualObject(EscapeAnalysis::Alias alias,
-                                                 NodeId id, Zone* zone);
+                                                 NodeId id, size_t fields,
+                                                 Zone* zone);
   void SetVirtualObject(EscapeAnalysis::Alias alias, VirtualObject* state);
   void LastChangedAt(Node* node) { last_changed_ = node; }
   Node* GetLastChanged() { return last_changed_; }
   bool UpdateFrom(VirtualState* state, Zone* zone);
   bool MergeFrom(MergeCache* cache, Zone* zone, Graph* graph,
                  CommonOperatorBuilder* common, Node* control);
   size_t size() const { return info_.size(); }
 
  private:
   ZoneVector<VirtualObject*> info_;
@@ skipping 89 matching lines @@
   }
 }
 
 
 VirtualObject* VirtualState::VirtualObjectFromAlias(size_t alias) {
   return info_[alias];
 }
 
 
 VirtualObject* VirtualState::GetOrCreateTrackedVirtualObject(
-    EscapeAnalysis::Alias alias, NodeId id, Zone* zone) {
+    EscapeAnalysis::Alias alias, NodeId id, size_t field_number, Zone* zone) {
   if (VirtualObject* obj = VirtualObjectFromAlias(alias)) {
     return obj;
   }
   VirtualObject* obj = new (zone) VirtualObject(id, zone, 0);
   SetVirtualObject(alias, obj);
   return obj;
 }
 
 
 void VirtualState::SetVirtualObject(EscapeAnalysis::Alias alias,
@@ skipping 80 matching lines @@
                              CommonOperatorBuilder* common, Node* control) {
   DCHECK_GT(cache->states().size(), 0u);
   bool changed = false;
   for (EscapeAnalysis::Alias alias = 0; alias < size(); ++alias) {
     size_t fields = cache->LoadVirtualObjectsFromStatesFor(alias);
     if (cache->objects().size() == cache->states().size()) {
       if (FLAG_trace_turbo_escape) {
         PrintF("  Merging virtual objects of @%d\n", alias);
       }
       VirtualObject* mergeObject = GetOrCreateTrackedVirtualObject(
-          alias, cache->objects().front()->id(), zone);
+          alias, cache->objects().front()->id(), fields, 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 33 matching lines @@
                 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 {
+            if (FLAG_trace_turbo_escape) {
+              PrintF("    Field %zu cleared\n", i);
+            }
             changed = mergeObject->SetField(i, nullptr) || changed;
           }
         }
       }
     } else {
       SetVirtualObject(alias, nullptr);
     }
   }
   return changed;
 }
@@ skipping 10 matching lines @@
 
 EscapeStatusAnalysis::~EscapeStatusAnalysis() {}
 
 
 bool EscapeStatusAnalysis::HasEntry(Node* node) {
   return status_[node->id()] & (kTracked | kEscaped);
 }
 
 
 bool EscapeStatusAnalysis::IsVirtual(Node* node) {
-  return (status_[node->id()] & kTracked) && !(status_[node->id()] & kEscaped);
+  return IsVirtual(node->id());
 }
 
 
+bool EscapeStatusAnalysis::IsVirtual(NodeId id) {
+  return (status_[id] & kTracked) && !(status_[id] & kEscaped);
+}
+
+
 bool EscapeStatusAnalysis::IsEscaped(Node* node) {
   return status_[node->id()] & kEscaped;
 }
 
 
 bool EscapeStatusAnalysis::IsAllocation(Node* node) {
   return node->opcode() == IrOpcode::kAllocate ||
          node->opcode() == IrOpcode::kFinishRegion;
 }
 
@@ skipping 205 matching lines @@
         }
         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;
         }
         break;
+      case IrOpcode::kSelect:
+        if (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;
+        }
+        break;
       default:
         if (use->op()->EffectInputCount() == 0 &&
             uses->op()->EffectInputCount() > 0) {
           PrintF("Encountered unaccounted use by #%d (%s)\n", use->id(),
                  use->op()->mnemonic());
           UNREACHABLE();
         }
         if (SetEscaped(rep)) {
           if (FLAG_trace_turbo_escape) {
             PrintF("Setting #%d (%s) to escaped because of use by #%d (%s)\n",
@@ skipping 42 matching lines @@
       aliases_(zone),
       next_free_alias_(0) {}
 
 
 EscapeAnalysis::~EscapeAnalysis() {}
 
 
 void EscapeAnalysis::Run() {
   replacements_.resize(graph()->NodeCount());
   AssignAliases();
+  if (AliasCount() == 0) return;
   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);
@@ skipping 291 matching lines @@
     mergeState->LastChangedAt(node);
     escape_status_.Resize();
   }
   return changed;
 }
 
 
 void EscapeAnalysis::ProcessAllocation(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
   ForwardVirtualState(node);
+  VirtualState* state = virtual_states_[node->id()];
+  Alias alias = aliases_[node->id()];
 
   // Check if we have already processed this node.
-  if (virtual_states_[node->id()]->VirtualObjectFromAlias(
-          aliases_[node->id()])) {
+  if (state->VirtualObjectFromAlias(alias)) {
     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(
-        aliases_[node->id()],
-        new (zone())
-            VirtualObject(node->id(), zone(), size.Value() / kPointerSize));
+    state->SetVirtualObject(
+        alias, new (zone()) VirtualObject(node->id(), zone(),
+                                          size.Value() / kPointerSize));
   } else {
-    virtual_states_[node->id()]->SetVirtualObject(
-        aliases_[node->id()], new (zone()) VirtualObject(node->id(), zone()));
+    state->SetVirtualObject(alias,
+                            new (zone()) VirtualObject(node->id(), zone()));
   }
-  virtual_states_[node->id()]->LastChangedAt(node);
+  state->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* state = virtual_states_[node->id()];
     if (!state->VirtualObjectFromAlias(aliases_[node->id()])) {
@@ skipping 94 matching lines @@
 VirtualObject* EscapeAnalysis::GetVirtualObject(Node* at, NodeId id) {
   if (VirtualState* states = virtual_states_[at->id()]) {
     return states->VirtualObjectFromAlias(aliases_[id]);
   }
   return nullptr;
 }
 
 
 VirtualObject* EscapeAnalysis::ResolveVirtualObject(VirtualState* state,
                                                     Node* node) {
-  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;
+  return GetVirtualObject(state, ResolveReplacement(node));

[sigurds, 2016/01/18 12:13:17]

The loop is not necessary since we rely on aliases_ to resolve VirtualObjects
(i.e. kAllocate and kFinishRegion refer to the same VirtualObject)

 }
 
 
 bool EscapeAnalysis::CompareVirtualObjects(Node* left, Node* right) {
   DCHECK(IsVirtual(left) && IsVirtual(right));
   left = ResolveReplacement(left);
   right = ResolveReplacement(right);
   if (IsEquivalentPhi(left, right)) {
     return true;
   }
@@ skipping 44 matching lines @@
     }
   } 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);
+  Node* from = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
   VirtualState* state = virtual_states_[node->id()];
-  if (VirtualObject* object = ResolveVirtualObject(state, from)) {
+  if (VirtualObject* object = GetVirtualObject(state, from)) {
     int offset = OffsetFromAccess(node);
     if (!object->IsTracked()) return;
     Node* value = object->GetField(offset);
     if (value) {
       value = ResolveReplacement(value);
     }
     // Record that the load has this alias.
     UpdateReplacement(state, node, value);
-  } else {
-    if (from->opcode() == IrOpcode::kPhi &&
-        OpParameter<FieldAccess>(node).offset % kPointerSize == 0) {
+  } else 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);
-    }
+  } else {
+    UpdateReplacement(state, node, nullptr);
   }
 }
 
 
 void EscapeAnalysis::ProcessLoadElement(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kLoadElement);
   ForwardVirtualState(node);
-  Node* from = NodeProperties::GetValueInput(node, 0);
+  Node* from = ResolveReplacement(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)) {
+    if (VirtualObject* object = GetVirtualObject(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 = ResolveReplacement(value);
       }
       // Record that the load has this alias.
       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 {
+      UpdateReplacement(state, node, nullptr);

[sigurds, 2016/01/18 12:13:17]

This is a critical bug-fix

     }
   } 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 "
+            "Setting #%d (%s) to escaped because load element #%d from "
             "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);
+  Node* to = ResolveReplacement(NodeProperties::GetValueInput(node, 0));
   VirtualState* state = virtual_states_[node->id()];
-  if (VirtualObject* obj = ResolveVirtualObject(state, to)) {
-    if (!obj->IsTracked()) return;
+  VirtualObject* obj = GetVirtualObject(state, to);
+  if (obj && obj->IsTracked()) {
     int offset = OffsetFromAccess(node);
-    if (obj->SetField(offset, ResolveReplacement(val))) {
+    Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 1));
+    if (obj->SetField(offset, val)) {
       state->LastChangedAt(node);
     }
   }
 }
 
 
 void EscapeAnalysis::ProcessStoreElement(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kStoreElement);
   ForwardVirtualState(node);
-  Node* to = NodeProperties::GetValueInput(node, 0);
+  Node* to = ResolveReplacement(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;
+    VirtualState* state = virtual_states_[node->id()];
+    VirtualObject* obj = GetVirtualObject(state, to);
+    if (obj && obj->IsTracked()) {
       CHECK_GE(ElementSizeLog2Of(access.machine_type.representation()),
                kPointerSizeLog2);
       CHECK_EQ(access.header_size % kPointerSize, 0);
-      if (obj->SetField(offset, ResolveReplacement(val))) {
-        states->LastChangedAt(node);
+      Node* val = ResolveReplacement(NodeProperties::GetValueInput(node, 2));
+      if (obj->SetField(offset, val)) {
+        state->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",
@@ skipping 88 matching lines @@
 
 
 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);
 }
 
+
+bool EscapeAnalysis::ExistsVirtualAllocate() {
+  for (size_t id = 0; id < aliases_.size(); ++id) {
+    Alias alias = aliases_[id];
+    if (alias < kUntrackable) {
+      if (escape_status_.IsVirtual(static_cast<int>(id))) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8