[turbofan] Memory improvements for 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 {
 
 #ifdef DEBUG
 #define TRACE(...)                                    \
   do {                                                \
     if (FLAG_trace_turbo_escape) PrintF(__VA_ARGS__); \
   } while (false)
 #else
 #define TRACE(...)
 #endif  // DEBUG
 
 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() * 2), zone),
+      fully_reduced_(static_cast<int>(jsgraph->graph()->NodeCount() * 2), zone),
       exists_virtual_allocate_(true) {}
 
 
 Reduction EscapeAnalysisReducer::Reduce(Node* node) {
+  if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
+      fully_reduced_.Contains(node->id())) {
+    return NoChange();
+  }
+
   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);
+    // FrameStates and Value nodes are preprocessed here,
+    // and visited via ReduceFrameStateUses from their user nodes.
     case IrOpcode::kFrameState:
     case IrOpcode::kStateValues: {
-      if (node->id() >= static_cast<NodeId>(visited_.length()) ||
-          visited_.Contains(node->id())) {
+      if (node->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
+          fully_reduced_.Contains(node->id())) {
         break;
       }
-      bool needs_visit = false;
+      bool depends_on_object_state = 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);
+            depends_on_object_state =
+                depends_on_object_state || 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());
+            depends_on_object_state =
+                depends_on_object_state ||
+                input->id() >= static_cast<NodeId>(fully_reduced_.length()) ||
+                !fully_reduced_.Contains(input->id());
             break;
           default:
             break;
         }
       }
-      if (!needs_visit) {
-        visited_.Add(node->id());
+      if (!depends_on_object_state) {
+        fully_reduced_.Add(node->id());
       }
-      break;
+      return NoChange();
     }
     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 (exists_virtual_allocate_ && node->op()->EffectInputCount() > 0) {
         return ReduceFrameStateUses(node);
       }
       break;
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceLoad(Node* node) {
   DCHECK(node->opcode() == IrOpcode::kLoadField ||
          node->opcode() == IrOpcode::kLoadElement);
-  if (visited_.Contains(node->id())) return NoChange();
-  visited_.Add(node->id());
+  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
+    fully_reduced_.Add(node->id());
+  }
   if (Node* rep = escape_analysis()->GetReplacement(node)) {
-    visited_.Add(node->id());
     counters()->turbo_escape_loads_replaced()->Increment();
     TRACE("Replaced #%d (%s) with #%d (%s)\n", node->id(),
           node->op()->mnemonic(), rep->id(), rep->op()->mnemonic());
     ReplaceWithValue(node, rep);
     return Changed(rep);
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceStore(Node* node) {
   DCHECK(node->opcode() == IrOpcode::kStoreField ||
          node->opcode() == IrOpcode::kStoreElement);
-  if (visited_.Contains(node->id())) return NoChange();
-  visited_.Add(node->id());
+  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
+    fully_reduced_.Add(node->id());
+  }
   if (escape_analysis()->IsVirtual(NodeProperties::GetValueInput(node, 0))) {
     TRACE("Removed #%d (%s) from effect chain\n", node->id(),
           node->op()->mnemonic());
     RelaxEffectsAndControls(node);
     return Changed(node);
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceAllocate(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kAllocate);
-  if (visited_.Contains(node->id())) return NoChange();
-  visited_.Add(node->id());
   if (escape_analysis()->IsVirtual(node)) {
     RelaxEffectsAndControls(node);
     counters()->turbo_escape_allocs_replaced()->Increment();
     TRACE("Removed allocate #%d from effect chain\n", node->id());
     return Changed(node);
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceFinishRegion(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kFinishRegion);
   Node* effect = NodeProperties::GetEffectInput(node, 0);
   if (effect->opcode() == IrOpcode::kBeginRegion) {
+    if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
+      fully_reduced_.Add(node->id());
+    }
     RelaxEffectsAndControls(effect);
     RelaxEffectsAndControls(node);
 #ifdef DEBUG
     if (FLAG_trace_turbo_escape) {
       PrintF("Removed region #%d / #%d from effect chain,", effect->id(),
              node->id());
       PrintF(" %d user(s) of #%d remain(s):", node->UseCount(), node->id());
       for (Edge edge : node->use_edges()) {
         PrintF(" #%d", edge.from()->id());
       }
@@ skipping 17 matching lines @@
       TRACE("Replaced ref eq #%d with true\n", node->id());
     }
     // Right-hand side is not a virtual object, or a different one.
     ReplaceWithValue(node, jsgraph()->FalseConstant());
     TRACE("Replaced ref eq #%d with false\n", node->id());
     return Replace(node);
   } else if (escape_analysis()->IsVirtual(right)) {
     // Left-hand side is not a virtual object.
     ReplaceWithValue(node, jsgraph()->FalseConstant());
     TRACE("Replaced ref eq #%d with false\n", node->id());
+    return Replace(node);
   }
   return NoChange();
 }
 
 
 Reduction EscapeAnalysisReducer::ReduceObjectIsSmi(Node* node) {
   DCHECK_EQ(node->opcode(), IrOpcode::kObjectIsSmi);
   Node* input = NodeProperties::GetValueInput(node, 0);
   if (escape_analysis()->IsVirtual(input)) {
     ReplaceWithValue(node, jsgraph()->FalseConstant());
     TRACE("Replaced ObjectIsSmi #%d with false\n", node->id());
     return Replace(node);
   }
   return NoChange();
 }
 
 
 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 = 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::ReduceDeoptState(Node* node, Node* effect,
                                               bool multiple_users) {
   DCHECK(node->opcode() == IrOpcode::kFrameState ||
          node->opcode() == IrOpcode::kStateValues);
-  if (node->id() < static_cast<NodeId>(visited_.length()) &&
-      visited_.Contains(node->id())) {
+  if (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
+      fully_reduced_.Contains(node->id())) {
     return nullptr;
   }
   TRACE("Reducing %s %d\n", node->op()->mnemonic(), node->id());
   Node* clone = nullptr;
   bool node_multiused = node->UseCount() > 1;
   bool multiple_users_rec = multiple_users || node_multiused;
   for (int i = 0; i < node->op()->ValueInputCount(); ++i) {
     Node* input = NodeProperties::GetValueInput(node, i);
     if (input->opcode() == IrOpcode::kStateValues) {
       if (Node* ret = ReduceDeoptState(input, effect, multiple_users_rec)) {
@@ skipping 21 matching lines @@
               ReduceDeoptState(outer_frame_state, effect, multiple_users_rec)) {
         if (node_multiused || (multiple_users && !clone)) {
           TRACE("    Cloning #%d", node->id());
           node = clone = jsgraph()->graph()->CloneNode(node);
           TRACE(" to #%d\n", node->id());
         }
         NodeProperties::ReplaceFrameStateInput(node, 0, ret);
       }
     }
   }
+  if (node->id() < static_cast<NodeId>(fully_reduced_.length())) {
+    fully_reduced_.Add(node->id());
+  }
   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 (node->id() < static_cast<NodeId>(fully_reduced_.length()) &&
+      fully_reduced_.Contains(node->id())) {
+    return nullptr;
+  }
   TRACE("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_multiused || (multiple_users && !already_cloned)) {
           TRACE("Cloning #%d", node->id());
@@ skipping 13 matching lines @@
     }
   }
   return clone;
 }
 
 
 Counters* EscapeAnalysisReducer::counters() const {
   return jsgraph_->isolate()->counters();
 }
 
+
+class EscapeAnalysisVerifier final : public AdvancedReducer {
+ public:
+  EscapeAnalysisVerifier(Editor* editor, EscapeAnalysis* escape_analysis)
+      : AdvancedReducer(editor), escape_analysis_(escape_analysis) {}
+
+  Reduction Reduce(Node* node) final {
+    switch (node->opcode()) {
+      case IrOpcode::kAllocate:
+        CHECK(!escape_analysis_->IsVirtual(node));
+        break;
+      default:
+        break;
+    }
+    return NoChange();
+  }
+
+ private:
+  EscapeAnalysis* escape_analysis_;
+};
+
+void EscapeAnalysisReducer::VerifyReplacement() const {
+#ifdef DEBUG
+  GraphReducer graph_reducer(zone(), jsgraph()->graph());
+  EscapeAnalysisVerifier verifier(&graph_reducer, escape_analysis());
+  graph_reducer.AddReducer(&verifier);
+  graph_reducer.ReduceGraph();
+#endif  // DEBUG
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8