[turbofan] Optimize certain chains of Branch into a Switch.

src/compiler/control-flow-optimizer.cc

Index: src/compiler/control-flow-optimizer.cc
diff --git a/src/compiler/control-flow-optimizer.cc b/src/compiler/control-flow-optimizer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..dbea6874e14f96df3252f0b16213e5816cf05b2d
--- /dev/null
+++ b/src/compiler/control-flow-optimizer.cc
@@ -0,0 +1,145 @@
+// 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/control-flow-optimizer.h"
+
+#include "src/compiler/js-graph.h"
+#include "src/compiler/node-matchers.h"
+#include "src/compiler/node-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+ControlFlowOptimizer::ControlFlowOptimizer(JSGraph* jsgraph, Zone* zone)
+    : jsgraph_(jsgraph),
+      queue_(zone),
+      queued_(jsgraph->graph(), 2),
+      zone_(zone) {}
+
+
+void ControlFlowOptimizer::Optimize() {
+  Enqueue(graph()->start());
+  while (!queue_.empty()) {
+    Node* node = queue_.front();
+    queue_.pop();
+    if (node->IsDead()) continue;
+    switch (node->opcode()) {
+      case IrOpcode::kBranch:
+        VisitBranch(node);
+        break;
+      default:
+        VisitNode(node);
+        break;
+    }
+  }
+}
+
+
+void ControlFlowOptimizer::Enqueue(Node* node) {
+  DCHECK_NOT_NULL(node);
+  if (node->IsDead() || queued_.Get(node)) return;
+  queued_.Set(node, true);
+  queue_.push(node);
+}
+
+
+void ControlFlowOptimizer::VisitNode(Node* node) {
+  for (Node* use : node->uses()) {
+    if (NodeProperties::IsControl(use)) Enqueue(use);
+  }
+}
+
+
+void ControlFlowOptimizer::VisitBranch(Node* node) {
+  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+
+  Node* branch = node;
+  Node* cond = NodeProperties::GetValueInput(branch, 0);
+  if (cond->opcode() != IrOpcode::kWord32Equal) return VisitNode(node);
+  Int32BinopMatcher m(cond);
+  Node* index = m.left().node();
+  if (!m.right().HasValue()) return VisitNode(node);
+  int32_t value = m.right().Value();
+  ZoneSet<int32_t> values(zone());
+  values.insert(value);
+
+  Node* if_false;
+  Node* if_true;
+  while (true) {
+    auto it = branch->uses().begin();
+    DCHECK(it != branch->uses().end());
+    if_true = *it++;
+    DCHECK(it != branch->uses().end());
+    if_false = *it++;
+    DCHECK(it == branch->uses().end());
+    if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);

[Michael Starzinger, 2015/02/17 12:23:35]

At some point I think we want to move CollectSuccessorProjections from the
Scheduler to NodeProperties so that we can use it in places like this. But that
is for a follow-up CL. Should we leave a TODO?

[Benedikt Meurer, 2015/02/17 12:30:38]

Done.

+    DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
+    DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
+
+    it = if_false->uses().begin();
+    if (it == if_false->uses().end()) break;
+    Node* branch1 = *it++;
+    if (branch1->opcode() != IrOpcode::kBranch) break;
+    if (it != if_false->uses().end()) break;
+    Node* cond1 = branch1->InputAt(0);
+    if (cond1->opcode() != IrOpcode::kWord32Equal) break;
+    Int32BinopMatcher m1(cond1);
+    if (m1.left().node() != index) break;
+    if (!m1.right().HasValue()) break;
+    int32_t value1 = m1.right().Value();
+    if (values.find(value1) != values.end()) break;
+    DCHECK_NE(value, value1);
+
+    if (branch != node) {
+      branch->RemoveAllInputs();
+      if_true->ReplaceInput(0, node);
+    }
+    if_true->set_op(common()->IfValue(value));
+    if_false->RemoveAllInputs();
+    Enqueue(if_true);
+
+    branch = branch1;
+    value = value1;
+    values.insert(value);
+  }
+
+  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
+  DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
+  DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
+  if (branch == node) {
+    DCHECK_EQ(1u, values.size());
+    Enqueue(if_true);
+    Enqueue(if_false);
+  } else {
+    DCHECK_LT(1u, values.size());
+    node->set_op(common()->Switch(values.size() + 1));
+    node->ReplaceInput(0, index);
+    if_true->set_op(common()->IfValue(value));
+    if_true->ReplaceInput(0, node);
+    Enqueue(if_true);
+    if_false->set_op(common()->IfDefault());
+    if_false->ReplaceInput(0, node);
+    Enqueue(if_false);
+    branch->RemoveAllInputs();
+  }
+}
+
+
+CommonOperatorBuilder* ControlFlowOptimizer::common() const {
+  return jsgraph()->common();
+}
+
+
+Graph* ControlFlowOptimizer::graph() const { return jsgraph()->graph(); }
+
+
+MachineOperatorBuilder* ControlFlowOptimizer::machine() const {
+  return jsgraph()->machine();
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8