[turbofan] Initial version of branch cloning.

src/compiler/control-flow-optimizer.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/control-flow-optimizer.h"
 
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-matchers.h"
 #include "src/compiler/node-properties.h"
 
@@ skipping 36 matching lines @@
 
 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());
+  if (TryBuildSwitch(node)) return;
+  if (TryCloneBranch(node)) return;
+  VisitNode(node);
+}
+
+
+bool ControlFlowOptimizer::TryCloneBranch(Node* node) {
+  DCHECK_EQ(IrOpcode::kBranch, node->opcode());
+
+  // This optimization is a special case of (super)block cloning. It takes an
+  // input graph as shown below and clones the Branch node for every predecessor
+  // to the Merge, essentially removing the Merge completely. This avoids
+  // materializing the bit for the Phi and may offer potential for further
+  // branch folding optimizations (i.e. because one or more inputs to the Phi is
+  // a constant). Note that there may be more Phi nodes hanging off the Merge,
+  // but we can only a certain subset of them currently (actually only Phi and
+  // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
+  // input).
+
+  //   Control1 ... ControlN
+  //      ^            ^
+  //      |            |   Cond1 ... CondN
+  //      +----+  +----+     ^         ^
+  //           |  |          |         |
+  //           |  |     +----+         |
+  //          Merge<--+ | +------------+
+  //            ^      \|/
+  //            |      Phi
+  //            |       |
+  //          Branch----+
+  //            ^
+  //            |
+  //      +-----+-----+
+  //      |           |
+  //    IfTrue     IfFalse
+  //      ^           ^
+  //      |           |
+
+  // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:
+
+  // Control1 Cond1 ... ControlN CondN
+  //    ^      ^           ^      ^
+  //    \      /           \      /
+  //     Branch     ...     Branch
+  //       ^                  ^
+  //       |                  |
+  //   +---+---+          +---+----+
+  //   |       |          |        |
+  // IfTrue IfFalse ... IfTrue  IfFalse
+  //   ^       ^          ^        ^
+  //   |       |          |        |
+  //   +--+ +-------------+        |
+  //      | |  +--------------+ +--+
+  //      | |                 | |
+  //     Merge               Merge
+  //       ^                   ^
+  //       |                   |
+
+  Node* branch = node;
+  Node* cond = NodeProperties::GetValueInput(branch, 0);
+  if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false;
+  Node* merge = NodeProperties::GetControlInput(branch);
+  if (merge->opcode() != IrOpcode::kMerge ||
+      NodeProperties::GetControlInput(cond) != merge) {
+    return false;
+  }
+  // Grab the IfTrue/IfFalse projections of the Branch.
+  Node* control_projections[2];
+  NodeProperties::CollectControlProjections(branch, control_projections,
+                                            arraysize(control_projections));
+  Node* if_true = control_projections[0];
+  Node* if_false = control_projections[1];
+  DCHECK_EQ(IrOpcode::kIfTrue, if_true->opcode());
+  DCHECK_EQ(IrOpcode::kIfFalse, if_false->opcode());
+  // Check/collect other Phi/EffectPhi nodes hanging off the Merge.
+  NodeVector phis(zone());
+  for (Node* const use : merge->uses()) {
+    if (use == branch || use == cond) continue;
+    // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the
+    // Merge. Ideally, we would just clone the nodes (and everything that
+    // depends on it to some distant join point), but that requires knowledge
+    // about dominance/post-dominance.
+    if (!NodeProperties::IsPhi(use)) return false;
+    for (Edge edge : use->use_edges()) {
+      // Right now we can only handle Phi/EffectPhi nodes whose uses are
+      // directly control-dependend on either the IfTrue or the IfFalse
+      // successor, because we know exactly how to update those uses.
+      // TODO(turbofan): Generalize this to all Phi/EffectPhi nodes using
+      // dominance/post-dominance on the sea of nodes.
+      if (edge.from()->op()->ControlInputCount() != 1) return false;
+      Node* control = NodeProperties::GetControlInput(edge.from());
+      if (NodeProperties::IsPhi(edge.from())) {
+        control = NodeProperties::GetControlInput(control, edge.index());
+      }
+      if (control != if_true && control != if_false) return false;
+    }
+    phis.push_back(use);
+  }
+  BranchHint const hint = BranchHintOf(branch->op());
+  int const input_count = merge->op()->ControlInputCount();
+  DCHECK_LE(1, input_count);
+  Node** const inputs = zone()->NewArray<Node*>(2 * input_count);
+  Node** const merge_true_inputs = &inputs[0];
+  Node** const merge_false_inputs = &inputs[input_count];
+  for (int index = 0; index < input_count; ++index) {
+    Node* cond1 = NodeProperties::GetValueInput(cond, index);
+    Node* control1 = NodeProperties::GetControlInput(merge, index);
+    Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1);
+    merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1);
+    merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1);
+    Enqueue(branch1);
+  }
+  Node* const merge_true = graph()->NewNode(common()->Merge(input_count),
+                                            input_count, merge_true_inputs);
+  Node* const merge_false = graph()->NewNode(common()->Merge(input_count),
+                                             input_count, merge_false_inputs);
+  for (Node* const phi : phis) {
+    for (int index = 0; index < input_count; ++index) {
+      inputs[index] = phi->InputAt(index);
+    }
+    inputs[input_count] = merge_true;
+    Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs);
+    inputs[input_count] = merge_false;
+    Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs);
+    for (Edge edge : phi->use_edges()) {
+      Node* control = NodeProperties::GetControlInput(edge.from());
+      if (NodeProperties::IsPhi(edge.from())) {
+        control = NodeProperties::GetControlInput(control, edge.index());
+      }
+      DCHECK(control == if_true || control == if_false);
+      edge.UpdateTo((control == if_true) ? phi_true : phi_false);
+    }
+    phi->Kill();
+  }
+  // Fix up IfTrue and IfFalse and kill all dead nodes.
+  if_false->ReplaceUses(merge_false);
+  if_true->ReplaceUses(merge_true);
+  if_false->Kill();
+  if_true->Kill();
+  branch->Kill();
+  cond->Kill();
+  merge->Kill();
+  return true;
+}
+
+
+bool ControlFlowOptimizer::TryBuildSwitch(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);
+  if (cond->opcode() != IrOpcode::kWord32Equal) return false;
   Int32BinopMatcher m(cond);
   Node* index = m.left().node();
-  if (!m.right().HasValue()) return VisitNode(node);
+  if (!m.right().HasValue()) return false;
   int32_t value = m.right().Value();
   ZoneSet<int32_t> values(zone());
   values.insert(value);
 
   Node* if_false;
   Node* if_true;
   while (true) {
     Node* control_projections[2];
     NodeProperties::CollectControlProjections(branch, control_projections, 2);
     if_true = control_projections[0];
@@ skipping 41 matching lines @@
     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();
   }
+  return true;
 }
 
 
 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