Reland "[turbofan] Fix select lowering" with fix.

src/compiler/select-lowering.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/select-lowering.h"
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/diamond.h"
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/graph.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
 SelectLowering::SelectLowering(Graph* graph, CommonOperatorBuilder* common)
     : common_(common),
       graph_(graph),
       merges_(Merges::key_compare(), Merges::allocator_type(graph->zone())) {}
 
 
 SelectLowering::~SelectLowering() {}
 
 
 Reduction SelectLowering::Reduce(Node* node) {
   if (node->opcode() != IrOpcode::kSelect) return NoChange();
   SelectParameters const p = SelectParametersOf(node->op());
 
-  Node* const cond = node->InputAt(0);
+  Node* cond = node->InputAt(0);
+  Node* vthen = node->InputAt(1);
+  Node* velse = node->InputAt(2);
+  Node* merge = nullptr;
 
   // Check if we already have a diamond for this condition.
-  auto i = merges_.find(cond);
-  if (i == merges_.end()) {
-    // Create a new diamond for this condition and remember its merge node.
-    Diamond d(graph(), common(), cond, p.hint());
-    i = merges_.insert(std::make_pair(cond, d.merge)).first;
+  auto range = merges_.equal_range(cond);
+  for (auto i = range.first;; ++i) {
+    if (i == range.second) {
+      // Create a new diamond for this condition and remember its merge node.
+      Diamond d(graph(), common(), cond, p.hint());
+      merges_.insert(std::make_pair(cond, d.merge));
+      merge = d.merge;
+      break;
+    }
+
+    // If the diamond is reachable from the Select, merging them would result in
+    // an unschedulable graph, so we cannot reuse the diamond in that case.
+    merge = i->second;
+    if (!ReachableFrom(merge, node)) {
+      break;
+    }
   }
 
-  DCHECK_EQ(cond, i->first);
-
   // Create a Phi hanging off the previously determined merge.
   node->set_op(common()->Phi(p.type(), 2));
-  node->ReplaceInput(0, node->InputAt(1));
-  node->ReplaceInput(1, node->InputAt(2));
-  node->ReplaceInput(2, i->second);
+  node->ReplaceInput(0, vthen);
+  node->ReplaceInput(1, velse);
+  node->ReplaceInput(2, merge);
   return Changed(node);
 }
 
+
+bool SelectLowering::ReachableFrom(Node* const sink, Node* const source) {
+  // TODO(turbofan): This is probably horribly expensive, and it should be moved
+  // into node.h or somewhere else?!
+  Zone zone(graph()->zone()->isolate());
+  std::queue<Node*, NodeDeque> queue((NodeDeque(&zone)));
+  BoolVector queued(graph()->NodeCount(), false, &zone);

[Jarin, 2014/11/10 11:52:15]

Please, rename to 'visited'. 'queued' seems to imply that it is set iff the node
is in the queue.

[Benedikt Meurer, 2014/11/10 11:55:32]

Done.

+  queue.push(source);
+  queued[source->id()] = true;
+  while (!queue.empty()) {
+    Node* current = queue.front();
+    if (current == sink) return true;
+    queue.pop();
+    for (auto input : current->inputs()) {
+      if (!queued[input->id()]) {
+        queue.push(input);
+        queued[input->id()] = true;
+      }
+    }
+  }
+  return false;
+}
+
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8