[turbofan] Fix bugs in escape analysis.

src/compiler/escape-analysis-reducer.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-reducer.h"
 
 #include "src/compiler/js-graph.h"
 #include "src/counters.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 EscapeAnalysisReducer::EscapeAnalysisReducer(Editor* editor, JSGraph* jsgraph,
                                              EscapeAnalysis* escape_analysis,
                                              Zone* zone)
     : AdvancedReducer(editor),
       jsgraph_(jsgraph),
       escape_analysis_(escape_analysis),
       zone_(zone),
-      visited_(static_cast<int>(jsgraph->graph()->NodeCount()), zone) {}
+      visited_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
+      exists_virtual_allocate_(true) {}
 
 
 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kLoadField:
     case IrOpcode::kLoadElement:
       return ReduceLoad(node);
     case IrOpcode::kStoreField:
     case IrOpcode::kStoreElement:
       return ReduceStore(node);
     case IrOpcode::kAllocate:
       return ReduceAllocate(node);
     case IrOpcode::kFinishRegion:
       return ReduceFinishRegion(node);
     case IrOpcode::kReferenceEqual:
       return ReduceReferenceEqual(node);
     case IrOpcode::kObjectIsSmi:
       return ReduceObjectIsSmi(node);
+    case IrOpcode::kFrameState:

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

Here we identify FrameStates and StateValues that do not have virtual allocs as
input. Those need not be visited by ReduceDeoptState, and this saves time.

+    case IrOpcode::kStateValues: {
+      if (node->id() >= static_cast<NodeId>(visited_.length()) ||
+          visited_.Contains(node->id())) {
+        break;
+      }
+      bool needs_visit = false;
+      for (int i = 0; i < node->InputCount(); i++) {
+        Node* input = node->InputAt(i);
+        switch (input->opcode()) {
+          case IrOpcode::kAllocate:
+          case IrOpcode::kFinishRegion:
+            needs_visit = needs_visit || escape_analysis()->IsVirtual(input);
+            break;
+          case IrOpcode::kFrameState:
+          case IrOpcode::kStateValues:
+            needs_visit =
+                needs_visit ||
+                input->id() >= static_cast<NodeId>(visited_.length()) ||
+                !visited_.Contains(input->id());
+            break;
+          default:
+            break;
+        }
+      }
+      if (!needs_visit) {
+        visited_.Add(node->id());
+      }
+      break;
+    }
     default:
       // TODO(sigurds): Change this to GetFrameStateInputCount once
       // it is working. For now we use EffectInputCount > 0 to determine
       // whether a node might have a frame state input.
-      if (node->op()->EffectInputCount() > 0) {
+      if (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
         return ReduceFrameStateUses(node);
       }
       break;
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
   DCHECK(node->opcode() == IrOpcode::kLoadField ||
@@ skipping 112 matching lines @@
 
 
 Reduction EscapeAnalysisReducer::ReduceFrameStateUses(Node* node) {
   if (visited_.Contains(node->id())) return NoChange();
   visited_.Add(node->id());
   DCHECK_GE(node->op()->EffectInputCount(), 1);
   bool changed = false;
   for (int i = 0; i < node->InputCount(); ++i) {
     Node* input = node->InputAt(i);
     if (input->opcode() == IrOpcode::kFrameState) {
-      if (Node* ret = ReduceFrameState(input, node, false)) {
+      if (Node* ret = ReduceDeoptState(input, node, false)) {
         node->ReplaceInput(i, ret);
         changed = true;
       }
     }
   }
   if (changed) {
     return Changed(node);
   }
   return NoChange();
 }
 
 
 // Returns the clone if it duplicated the node, and null otherwise.
-Node* EscapeAnalysisReducer::ReduceFrameState(Node* node, Node* effect,
+Node* EscapeAnalysisReducer::ReduceDeoptState(Node* node, Node* effect,
                                               bool multiple_users) {
-  DCHECK(node->opcode() == IrOpcode::kFrameState);
+  DCHECK(node->opcode() == IrOpcode::kFrameState ||
+         node->opcode() == IrOpcode::kStateValues);
+  if (node->id() < static_cast<NodeId>(visited_.length()) &&
+      visited_.Contains(node->id())) {
+    return nullptr;
+  }
   if (FLAG_trace_turbo_escape) {
-    PrintF("Reducing FrameState %d\n", node->id());
+    PrintF("Reducing %s %d\n", node->op()->mnemonic(), node->id());
   }
   Node* clone = nullptr;
+  bool node_multiused = node->UseCount() > 1;

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

node->UseCount() is /really/ expensive; we just want to do it once.

+  bool multiple_users_rec = multiple_users || node_multiused;
   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
     Node* input = NodeProperties::GetValueInput(node, i);
-    Node* ret =
-        input->opcode() == IrOpcode::kStateValues
-            ? ReduceStateValueInputs(input, effect, node->UseCount() > 1)
-            : ReduceStateValueInput(node, i, effect, node->UseCount() > 1);
-    if (ret) {
-      if (node->UseCount() > 1 || multiple_users) {
-        if (FLAG_trace_turbo_escape) {
-          PrintF("  Cloning #%d", node->id());
+    if (input->opcode() == IrOpcode::kStateValues) {
+      if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
+        if (node_multiused || (multiple_users && !clone)) {
+          if (FLAG_trace_turbo_escape) {
+            PrintF("  Cloning #%d", node->id());
+          }
+          node = clone = jsgraph()->graph()->CloneNode(node);
+          if (FLAG_trace_turbo_escape) {
+            PrintF(" to #%d\n", node->id());
+          }
+          node_multiused = false;
         }
-        node = clone = jsgraph()->graph()->CloneNode(node);
-        if (FLAG_trace_turbo_escape) {
-          PrintF(" to #%d\n", node->id());
-        }
-        multiple_users = false;  // Don't clone anymore.
+        NodeProperties::ReplaceValueInput(node, ret, i);
       }
-      NodeProperties::ReplaceValueInput(node, ret, i);
+    } else {
+      if (Node* ret = ReduceStateValueInput(node, i, effect, node_multiused,
+                                            clone, multiple_users)) {
+        DCHECK_NULL(clone);
+        node_multiused = false;  // Don't clone anymore.
+        node = clone = ret;
+      }
     }
   }
-  Node* outer_frame_state = NodeProperties::GetFrameStateInput(node, 0);
-  if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
-    if (Node* ret =
-            ReduceFrameState(outer_frame_state, effect, node->UseCount() > 1)) {
-      if (node->UseCount() > 1 || multiple_users) {
-        if (FLAG_trace_turbo_escape) {
-          PrintF("  Cloning #%d", node->id());
+  if (node->opcode() == IrOpcode::kFrameState) {
+    Node* outer_frame_state = NodeProperties::GetFrameStateInput(node, 0);
+    if (outer_frame_state->opcode() == IrOpcode::kFrameState) {
+      if (Node* ret =
+              ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
+        if (node_multiused || (multiple_users && !clone)) {
+          if (FLAG_trace_turbo_escape) {
+            PrintF("    Cloning #%d", node->id());
+          }
+          node = clone = jsgraph()->graph()->CloneNode(node);
+          if (FLAG_trace_turbo_escape) {
+            PrintF(" to #%d\n", node->id());
+          }
         }
-        node = clone = jsgraph()->graph()->CloneNode(node);
-        if (FLAG_trace_turbo_escape) {
-          PrintF(" to #%d\n", node->id());
-        }
-        multiple_users = false;
+        NodeProperties::ReplaceFrameStateInput(node, 0, ret);
       }
-      NodeProperties::ReplaceFrameStateInput(node, 0, ret);
     }
   }
   return clone;
-}
-
-
-// Returns the clone if it duplicated the node, and null otherwise.
-Node* EscapeAnalysisReducer::ReduceStateValueInputs(Node* node, Node* effect,
-                                                    bool multiple_users) {
-  if (FLAG_trace_turbo_escape) {
-    PrintF("Reducing StateValue #%d\n", node->id());
-  }
-  DCHECK(node->opcode() == IrOpcode::kStateValues);
-  DCHECK_NOT_NULL(effect);
-  Node* clone = nullptr;
-  for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
-    Node* input = NodeProperties::GetValueInput(node, i);
-    Node* ret = nullptr;
-    if (input->opcode() == IrOpcode::kStateValues) {
-      ret = ReduceStateValueInputs(input, effect, multiple_users);
-    } else {
-      ret = ReduceStateValueInput(node, i, effect, multiple_users);
-    }
-    if (ret) {
-      node = ret;
-      DCHECK_NULL(clone);
-      clone = ret;
-      multiple_users = false;
-    }
-  }
-  return clone;
 }
 
 
 // Returns the clone if it duplicated the node, and null otherwise.
 Node* EscapeAnalysisReducer::ReduceStateValueInput(Node* node, int node_index,
                                                    Node* effect,
+                                                   bool node_multiused,
+                                                   bool already_cloned,
                                                    bool multiple_users) {
   Node* input = NodeProperties::GetValueInput(node, node_index);
   if (FLAG_trace_turbo_escape) {
     PrintF("Reducing State Input #%d (%s)\n", input->id(),
            input->op()->mnemonic());
   }
   Node* clone = nullptr;
   if (input->opcode() == IrOpcode::kFinishRegion ||
       input->opcode() == IrOpcode::kAllocate) {
     if (escape_analysis()->IsVirtual(input)) {
       if (Node* object_state =
               escape_analysis()->GetOrCreateObjectState(effect, input)) {
-        if (node->UseCount() > 1 || multiple_users) {
+        if (node_multiused || (multiple_users && !already_cloned)) {
           if (FLAG_trace_turbo_escape) {
             PrintF("Cloning #%d", node->id());
           }
           node = clone = jsgraph()->graph()->CloneNode(node);
           if (FLAG_trace_turbo_escape) {
             PrintF(" to #%d\n", node->id());
           }
+          node_multiused = false;
         }
         NodeProperties::ReplaceValueInput(node, object_state, node_index);
         if (FLAG_trace_turbo_escape) {
           PrintF("Replaced state #%d input #%d with object state #%d\n",
                  node->id(), input->id(), object_state->id());
         }
       } else {
         if (FLAG_trace_turbo_escape) {
           PrintF("No object state replacement available.\n");
         }
       }
     }
   }
   return clone;
 }
 
 
 Counters* EscapeAnalysisReducer::counters() const {
   return jsgraph_->isolate()->counters();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8