[turbofan] Match selects in control reducer (configurable).

src/compiler/control-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 "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-marker.h"
 #include "src/compiler/node-matchers.h"
@@ skipping 38 matching lines @@
 
 class ControlReducerImpl {
  public:
   ControlReducerImpl(Zone* zone, JSGraph* jsgraph,
                      CommonOperatorBuilder* common)
       : zone_(zone),
         jsgraph_(jsgraph),
         common_(common),
         state_(jsgraph->graph()->NodeCount(), kUnvisited, zone_),
         stack_(zone_),
-        revisit_(zone_) {}
+        revisit_(zone_),
+        max_phis_for_select_(0) {}
 
   Zone* zone_;
   JSGraph* jsgraph_;
   CommonOperatorBuilder* common_;
   ZoneVector<VisitState> state_;
   ZoneDeque<Node*> stack_;
   ZoneDeque<Node*> revisit_;
+  int max_phis_for_select_;
 
   void Reduce() {
     Push(graph()->end());
     do {
       // Process the node on the top of the stack, potentially pushing more
       // or popping the node off the stack.
       ReduceTop();
       // If the stack becomes empty, revisit any nodes in the revisit queue.
       // If no nodes in the revisit queue, try removing dead loops.
       // If no dead loops, then finish.
@@ skipping 452 matching lines @@
       }
       index++;
     }
 
     TRACE("ReduceMerge: #%d:%s (%d of %d live)\n", node->id(),
           node->op()->mnemonic(), live, index);
 
     if (live == 0) return dead();  // no remaining inputs.
 
     // Gather phis and effect phis to be edited.
-    ZoneVector<Node*> phis(zone_);
+    NodeVector phis(zone_);
     for (Node* const use : node->uses()) {
       if (NodeProperties::IsPhi(use)) phis.push_back(use);
     }
 
     if (live == 1) {
       // All phis are redundant. Replace them with their live input.
       for (Node* const phi : phis) ReplaceNode(phi, phi->InputAt(live_index));
       // The merge itself is redundant.
       return node->InputAt(live_index);
     }
 
     DCHECK_LE(2, live);
 
     if (live < node->InputCount()) {
       // Edit phis in place, removing dead inputs and revisiting them.
       for (Node* const phi : phis) {
         TRACE("  PhiInMerge: #%d:%s (%d live)\n", phi->id(),
               phi->op()->mnemonic(), live);
         RemoveDeadInputs(node, phi);
         Revisit(phi);
       }
       // Edit the merge in place, removing dead inputs.
       RemoveDeadInputs(node, node);
     }
 
     DCHECK_EQ(live, node->InputCount());
 
-    // Check if it's an unused diamond.
-    if (live == 2 && phis.empty()) {
+    // Try to remove dead diamonds or introduce selects.
+    if (live == 2 && CheckPhisForSelect(phis)) {
       DiamondMatcher matcher(node);
       if (matcher.Matched() && matcher.IfProjectionsAreOwned()) {
-        // It's a dead diamond, i.e. neither the IfTrue nor the IfFalse nodes
-        // have uses except for the Merge and the Merge has no Phi or
-        // EffectPhi uses, so replace the Merge with the control input of the
-        // diamond.
-        TRACE("  DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n",
-              matcher.Branch()->id(), matcher.IfTrue()->id(),
-              matcher.IfFalse()->id());
-        // TODO(turbofan): replace single-phi diamonds with selects.
-        return NodeProperties::GetControlInput(matcher.Branch());
+        // Dead diamond, i.e. neither the IfTrue nor the IfFalse nodes
+        // have uses except for the Merge. Remove the branch if there
+        // are no phis or replace phis with selects.
+        Node* control = NodeProperties::GetControlInput(matcher.Branch());
+        if (phis.size() == 0) {
+          // No phis. Remove the branch altogether.
+          TRACE("  DeadDiamond: #%d:Branch #%d:IfTrue #%d:IfFalse\n",
+                matcher.Branch()->id(), matcher.IfTrue()->id(),
+                matcher.IfFalse()->id());
+          return control;
+        } else {
+          // A small number of phis. Replace with selects.
+          Node* cond = matcher.Branch()->InputAt(0);
+          for (Node* phi : phis) {
+            Node* select = graph()->NewNode(
+                common_->Select(OpParameter<MachineType>(phi),
+                                BranchHintOf(matcher.Branch()->op())),
+                cond, matcher.TrueInputOf(phi), matcher.FalseInputOf(phi));
+            TRACE("  MatchSelect: #%d:Branch #%d:IfTrue #%d:IfFalse -> #%d\n",
+                  matcher.Branch()->id(), matcher.IfTrue()->id(),
+                  matcher.IfFalse()->id(), select->id());
+            ReplaceNode(phi, select);
+          }
+          return control;
+        }
       }
     }
 
     return node;
   }
 
+  bool CheckPhisForSelect(const NodeVector& phis) {
+    if (phis.size() > static_cast<size_t>(max_phis_for_select_)) return false;
+    for (Node* phi : phis) {
+      if (phi->opcode() != IrOpcode::kPhi) return false;  // no EffectPhis.
+    }
+    return true;
+  }
+
   // Reduce if projections if the branch has a constant input.
   Node* ReduceIfProjection(Node* node, Decision decision) {
     Node* branch = node->InputAt(0);
     DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     Decision result = DecideCondition(branch->InputAt(0));
     if (result == decision) {
       // Fold a branch by replacing IfTrue/IfFalse with the branch control.
       TRACE("  BranchReduce: #%d:%s => #%d:%s\n", branch->id(),
             branch->op()->mnemonic(), node->id(), node->op()->mnemonic());
       return branch->InputAt(1);
@@ skipping 35 matching lines @@
     }
     node->ReplaceUses(replacement);
     node->Kill();
   }
 
   Graph* graph() { return jsgraph_->graph(); }
 };
 
 
 void ControlReducer::ReduceGraph(Zone* zone, JSGraph* jsgraph,
-                                 CommonOperatorBuilder* common) {
+                                 CommonOperatorBuilder* common,
+                                 int max_phis_for_select) {
   ControlReducerImpl impl(zone, jsgraph, common);
+  impl.max_phis_for_select_ = max_phis_for_select;
   impl.Reduce();
 }
 
 
 void ControlReducer::TrimGraph(Zone* zone, JSGraph* jsgraph) {
   ControlReducerImpl impl(zone, jsgraph, NULL);
   impl.Trim();
 }
 
 
 Node* ControlReducer::ReduceMerge(JSGraph* jsgraph,
-                                  CommonOperatorBuilder* common, Node* node) {
+                                  CommonOperatorBuilder* common, Node* node,
+                                  int max_phis_for_select) {
   Zone zone;
   ControlReducerImpl impl(&zone, jsgraph, common);
+  impl.max_phis_for_select_ = max_phis_for_select;
   return impl.ReduceMerge(node);
 }
 
 
 Node* ControlReducer::ReducePhiForTesting(JSGraph* jsgraph,
                                           CommonOperatorBuilder* common,
                                           Node* node) {
   Zone zone;
   ControlReducerImpl impl(&zone, jsgraph, common);
   return impl.ReducePhi(node);
@@ skipping 10 matching lines @@
       return impl.ReduceIfProjection(node, kTrue);
     case IrOpcode::kIfFalse:
       return impl.ReduceIfProjection(node, kFalse);
     default:
       return node;
   }
 }
 }
 }
 }  // namespace v8::internal::compiler