[turbofan] Add support for advanced reducers.

src/compiler/graph-reducer.cc

 // Copyright 2014 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 <functional>
+#include <limits>
 
 #include "src/compiler/graph.h"
 #include "src/compiler/graph-reducer.h"
 #include "src/compiler/node.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
+bool Reducer::Finish() { return true; }
+
+
 enum class GraphReducer::State : uint8_t {
   kUnvisited,
   kRevisit,
   kOnStack,
   kVisited
 };
 
 
 GraphReducer::GraphReducer(Graph* graph, Zone* zone)
     : graph_(graph),
       state_(graph, 4),
       reducers_(zone),
       revisit_(zone),
       stack_(zone) {}
 
 
+GraphReducer::~GraphReducer() {}
+
+
 void GraphReducer::AddReducer(Reducer* reducer) {
   reducers_.push_back(reducer);
 }
 
 
 void GraphReducer::ReduceNode(Node* node) {
   DCHECK(stack_.empty());
   DCHECK(revisit_.empty());
   Push(node);
   for (;;) {
@@ skipping 11 matching lines @@
       }
     } else {
       break;
     }
   }
   DCHECK(revisit_.empty());
   DCHECK(stack_.empty());
 }
 
 
-void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
+void GraphReducer::ReduceGraph() {
+  for (;;) {
+    ReduceNode(graph()->end());
+    // TODO(turbofan): Remove this once the dead node trimming is in the
+    // GraphReducer.
+    bool done = true;
+    for (Reducer* const reducer : reducers_) {
+      if (!reducer->Finish()) {
+        done = false;
+        break;
+      }
+    }
+    if (done) break;
+    // Reset all marks on the graph in preparation to re-reduce the graph.
+    state_.Reset(graph());
+  }
+}
 
 
 Reduction GraphReducer::Reduce(Node* const node) {
   auto skip = reducers_.end();
   for (auto i = reducers_.begin(); i != reducers_.end();) {
     if (i != skip) {
       Reduction reduction = (*i)->Reduce(node);
       if (!reduction.Changed()) {
         // No change from this reducer.
       } else if (reduction.replacement() == node) {
@@ skipping 32 matching lines @@
     Node* input = node->InputAt(i);
     entry.input_index = i + 1;
     if (input != node && Recurse(input)) return;
   }
   for (int i = 0; i < start; i++) {
     Node* input = node->InputAt(i);
     entry.input_index = i + 1;
     if (input != node && Recurse(input)) return;
   }
 
-  // Remember the node count before reduction.
-  const int node_count = graph()->NodeCount();
+  // Remember the max node id before reduction.
+  NodeId const max_id = graph()->NodeCount() - 1;
 
   // All inputs should be visited or on stack. Apply reductions to node.
   Reduction reduction = Reduce(node);
 
   // If there was no reduction, pop {node} and continue.
   if (!reduction.Changed()) return Pop();
 
   // Check if the reduction is an in-place update of the {node}.
   Node* const replacement = reduction.replacement();
   if (replacement == node) {
     // In-place update of {node}, may need to recurse on an input.
     for (int i = 0; i < node->InputCount(); ++i) {
       Node* input = node->InputAt(i);
       entry.input_index = i + 1;
       if (input != node && Recurse(input)) return;
     }
   }
 
   // After reducing the node, pop it off the stack.
   Pop();
 
-  // Revisit all uses of the node.
-  for (Node* const use : node->uses()) {
-    // Don't revisit this node if it refers to itself.
-    if (use != node) Revisit(use);
-  }
-
   // Check if we have a new replacement.
   if (replacement != node) {
-    if (node == graph()->start()) graph()->SetStart(replacement);
-    if (node == graph()->end()) graph()->SetEnd(replacement);
-    // If {node} was replaced by an old node, unlink {node} and assume that
-    // {replacement} was already reduced and finish.
-    if (replacement->id() < node_count) {
-      node->ReplaceUses(replacement);
-      node->Kill();
-    } else {
-      // Otherwise {node} was replaced by a new node. Replace all old uses of
-      // {node} with {replacement}. New nodes created by this reduction can
-      // use {node}.
-      for (Edge edge : node->use_edges()) {
-        if (edge.from()->id() < node_count) {
-          edge.UpdateTo(replacement);
-        }
-      }
-      // Unlink {node} if it's no longer used.
-      if (node->uses().empty()) {
-        node->Kill();
-      }
-
-      // If there was a replacement, reduce it after popping {node}.
-      Recurse(replacement);
+    // If {replacement}  is an old node, unlink {node} and assume that

[titzer, 2015/05/06 09:38:44]

Move this comment into the branch within the Replace() method below.

[Benedikt Meurer, 2015/05/06 09:42:56]

Done.

+    // {replacement} was already reduced and finish. Otherwise, replace
+    // all old uses of {node} with {replacement}, but allow new nodes
+    // created by this reduction to use {node}.
+    Replace(node, replacement, max_id);
+  } else {
+    // Revisit all uses of the node.
+    for (Node* const user : node->uses()) {
+      // Don't revisit this node if it refers to itself.
+      if (user != node) Revisit(user);
     }
   }
 }
 
+
+void GraphReducer::Replace(Node* node, Node* replacement) {
+  Replace(node, replacement, std::numeric_limits<NodeId>::max());
+}
+
+
+void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) {
+  if (node == graph()->start()) graph()->SetStart(replacement);
+  if (node == graph()->end()) graph()->SetEnd(replacement);
+  if (replacement->id() <= max_id) {
+    for (Edge edge : node->use_edges()) {
+      Node* const user = edge.from();
+      edge.UpdateTo(replacement);
+      // Don't revisit this node if it refers to itself.
+      if (user != node) Revisit(user);
+    }
+    node->Kill();
+  } else {
+    for (Edge edge : node->use_edges()) {
+      Node* const user = edge.from();
+      if (user->id() <= max_id) {
+        edge.UpdateTo(replacement);
+        // Don't revisit this node if it refers to itself.
+        if (user != node) Revisit(user);
+      }
+    }
+    // Unlink {node} if it's no longer used.
+    if (node->uses().empty()) node->Kill();
+
+    // If there was a replacement, reduce it after popping {node}.
+    Recurse(replacement);
+  }
+}
+
 
 void GraphReducer::Pop() {
   Node* node = stack_.top().node;
   state_.Set(node, State::kVisited);
   stack_.pop();
 }
 
 
 void GraphReducer::Push(Node* const node) {
   DCHECK(state_.Get(node) != State::kOnStack);
@@ skipping 12 matching lines @@
 void GraphReducer::Revisit(Node* node) {
   if (state_.Get(node) == State::kVisited) {
     state_.Set(node, State::kRevisit);
     revisit_.push(node);
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8