1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/compiler/select-lowering.h"
6
7 #include "src/compiler/common-operator.h"
8 #include "src/compiler/diamond.h"
9 #include "src/compiler/graph.h"
10 #include "src/compiler/node.h"
11 #include "src/compiler/node-properties.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
SelectLowering(Graph * graph,CommonOperatorBuilder * common)17 SelectLowering::SelectLowering(Graph* graph, CommonOperatorBuilder* common)
18 : common_(common),
19 graph_(graph),
20 merges_(Merges::key_compare(), Merges::allocator_type(graph->zone())) {}
21
22
~SelectLowering()23 SelectLowering::~SelectLowering() {}
24
25
Reduce(Node * node)26 Reduction SelectLowering::Reduce(Node* node) {
27 if (node->opcode() != IrOpcode::kSelect) return NoChange();
28 SelectParameters const p = SelectParametersOf(node->op());
29
30 Node* cond = node->InputAt(0);
31 Node* vthen = node->InputAt(1);
32 Node* velse = node->InputAt(2);
33 Node* merge = nullptr;
34
35 // Check if we already have a diamond for this condition.
36 auto range = merges_.equal_range(cond);
37 for (auto i = range.first;; ++i) {
38 if (i == range.second) {
39 // Create a new diamond for this condition and remember its merge node.
40 Diamond d(graph(), common(), cond, p.hint());
41 merges_.insert(std::make_pair(cond, d.merge));
42 merge = d.merge;
43 break;
44 }
45
46 // If the diamond is reachable from the Select, merging them would result in
47 // an unschedulable graph, so we cannot reuse the diamond in that case.
48 merge = i->second;
49 if (!ReachableFrom(merge, node)) {
50 break;
51 }
52 }
53
54 // Create a Phi hanging off the previously determined merge.
55 node->ReplaceInput(0, vthen);
56 node->ReplaceInput(1, velse);
57 node->ReplaceInput(2, merge);
58 NodeProperties::ChangeOp(node, common()->Phi(p.representation(), 2));
59 return Changed(node);
60 }
61
62
ReachableFrom(Node * const sink,Node * const source)63 bool SelectLowering::ReachableFrom(Node* const sink, Node* const source) {
64 // TODO(turbofan): This is probably horribly expensive, and it should be moved
65 // into node.h or somewhere else?!
66 Zone zone;
67 std::queue<Node*, NodeDeque> queue((NodeDeque(&zone)));
68 BoolVector visited(graph()->NodeCount(), false, &zone);
69 queue.push(source);
70 visited[source->id()] = true;
71 while (!queue.empty()) {
72 Node* current = queue.front();
73 if (current == sink) return true;
74 queue.pop();
75 for (auto input : current->inputs()) {
76 if (!visited[input->id()]) {
77 queue.push(input);
78 visited[input->id()] = true;
79 }
80 }
81 }
82 return false;
83 }
84
85 } // namespace compiler
86 } // namespace internal
87 } // namespace v8
88