Implement graph trimming in ControlReducer.

src/compiler/control-reducer.cc

Index: src/compiler/control-reducer.cc
diff --git a/src/compiler/control-reducer.cc b/src/compiler/control-reducer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..cd35a8aaa4c34a28b3b4a42146c036d40db5fff5
--- /dev/null
+++ b/src/compiler/control-reducer.cc
@@ -0,0 +1,122 @@
+// 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 "src/compiler/common-operator.h"
+#include "src/compiler/control-reducer.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/js-graph.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/node-properties-inl.h"
+#include "src/zone-containers.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+enum VisitState { kUnvisited, kOnStack, kRevisit, kVisited };
+
+#define TRACE(x) \
+  if (FLAG_trace_turbo) PrintF x
+
+class ControlReducerImpl {
+ public:
+  ControlReducerImpl(JSGraph* jsgraph, CommonOperatorBuilder* common)
+      : zone_(jsgraph->zone()->isolate()),
+        jsgraph_(jsgraph),
+        common_(common),
+        state_(jsgraph->graph()->NodeCount(), kUnvisited, &zone_),
+        stack_(&zone_),
+        revisit_(&zone_),
+        dead_(NULL) {}
+
+  Zone zone_;
+  JSGraph* jsgraph_;
+  CommonOperatorBuilder* common_;
+  ZoneVector<VisitState> state_;
+  NodeVector stack_;

[Benedikt Meurer, 2014/10/17 09:46:44]

Nit: Use deque here, or even better std::stack with std::deque as backing store?

[titzer, 2014/10/17 11:15:50]

Done.

+  NodeVector revisit_;

[Benedikt Meurer, 2014/10/17 09:46:44]

Nit: Use deque here.

[titzer, 2014/10/17 11:15:50]

Done.

+  Node* dead_;
+
+  void Trim() {
+    //  Mark all nodes reachable from end.
+    state_.assign(jsgraph_->graph()->NodeCount(), kUnvisited);
+    Push(jsgraph_->graph()->end());
+    while (!stack_.empty()) {
+      Node* node = stack_[stack_.size() - 1];
+      stack_.pop_back();
+      state_[node->id()] = kVisited;
+      revisit_.push_back(node);
+      for (InputIter i = node->inputs().begin(); i != node->inputs().end();
+           ++i) {
+        Recurse(*i);  // pushes node onto the stack if necessary.
+      }
+    }
+    // Process cached nodes in the JSGraph too.
+    jsgraph_->GetCachedNodes(&revisit_);
+    // Remove dead->live edges.
+    for (size_t j = 0; j < revisit_.size(); j++) {
+      Node* node = revisit_[j];
+      for (UseIter i = node->uses().begin(); i != node->uses().end();) {
+        size_t id = static_cast<size_t>((*i)->id());
+        if (state_[id] != kVisited) {
+          TRACE(("DeadLink: #%d:%s(%d) -> #%d:%s\n", (*i)->id(),
+                 (*i)->op()->mnemonic(), i.index(), node->id(),
+                 node->op()->mnemonic()));
+          i.UpdateToAndIncrement(NULL);
+        } else {
+          ++i;
+        }
+      }
+    }
+#if DEBUG
+    // Verify that no inputs to live nodes are NULL.
+    for (size_t j = 0; j < revisit_.size(); j++) {
+      Node* node = revisit_[j];
+      for (InputIter i = node->inputs().begin(); i != node->inputs().end();
+           ++i) {
+        CHECK_NE(NULL, *i);
+      }
+      for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) {
+        size_t id = static_cast<size_t>((*i)->id());
+        CHECK_EQ(kVisited, state_[id]);
+      }
+    }
+#endif
+    revisit_.clear();
+  }
+
+  // Push a node onto the stack if its state is {kUnvisited} or {kRevisit}.
+  bool Recurse(Node* node) {
+    size_t id = static_cast<size_t>(node->id());
+    if (id < state_.size()) {
+      if (state_[id] != kRevisit && state_[id] != kUnvisited) return false;
+    } else {
+      state_.resize((3 * id) / 2, kUnvisited);
+    }
+    Push(node);
+    return true;
+  }
+
+  void Push(Node* node) {
+    state_[node->id()] = kOnStack;
+    stack_.push_back(node);
+  }
+};
+
+void ControlReducer::ReduceGraph(JSGraph* jsgraph,
+                                 CommonOperatorBuilder* common) {
+  ControlReducerImpl impl(jsgraph, NULL);
+  // Only trim the graph for now. Control reduction can reduce non-terminating
+  // loops to graphs that are unschedulable at the moment.
+  impl.Trim();
+}
+
+
+void ControlReducer::TrimGraph(JSGraph* jsgraph) {
+  ControlReducerImpl impl(jsgraph, NULL);
+  impl.Trim();
+}
+}
+}
+}  // namespace v8::internal::compiler