1 // Copyright 2015 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/control-flow-optimizer.h"
6
7 #include "src/compiler/common-operator.h"
8 #include "src/compiler/graph.h"
9 #include "src/compiler/node-matchers.h"
10 #include "src/compiler/node-properties.h"
11
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
15
ControlFlowOptimizer(Graph * graph,CommonOperatorBuilder * common,MachineOperatorBuilder * machine,Zone * zone)16 ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
17 CommonOperatorBuilder* common,
18 MachineOperatorBuilder* machine,
19 Zone* zone)
20 : graph_(graph),
21 common_(common),
22 machine_(machine),
23 queue_(zone),
24 queued_(graph, 2),
25 zone_(zone) {}
26
27
Optimize()28 void ControlFlowOptimizer::Optimize() {
29 Enqueue(graph()->start());
30 while (!queue_.empty()) {
31 Node* node = queue_.front();
32 queue_.pop();
33 if (node->IsDead()) continue;
34 switch (node->opcode()) {
35 case IrOpcode::kBranch:
36 VisitBranch(node);
37 break;
38 default:
39 VisitNode(node);
40 break;
41 }
42 }
43 }
44
45
Enqueue(Node * node)46 void ControlFlowOptimizer::Enqueue(Node* node) {
47 DCHECK_NOT_NULL(node);
48 if (node->IsDead() || queued_.Get(node)) return;
49 queued_.Set(node, true);
50 queue_.push(node);
51 }
52
53
VisitNode(Node * node)54 void ControlFlowOptimizer::VisitNode(Node* node) {
55 for (Edge edge : node->use_edges()) {
56 if (NodeProperties::IsControlEdge(edge)) {
57 Enqueue(edge.from());
58 }
59 }
60 }
61
62
VisitBranch(Node * node)63 void ControlFlowOptimizer::VisitBranch(Node* node) {
64 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
65 if (TryBuildSwitch(node)) return;
66 VisitNode(node);
67 }
68
69
TryBuildSwitch(Node * node)70 bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
71 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
72
73 Node* branch = node;
74 if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
75 Node* cond = NodeProperties::GetValueInput(branch, 0);
76 if (cond->opcode() != IrOpcode::kWord32Equal) return false;
77 Int32BinopMatcher m(cond);
78 Node* index = m.left().node();
79 if (!m.right().HasValue()) return false;
80 int32_t value = m.right().Value();
81 ZoneSet<int32_t> values(zone());
82 values.insert(value);
83
84 Node* if_false;
85 Node* if_true;
86 while (true) {
87 BranchMatcher matcher(branch);
88 DCHECK(matcher.Matched());
89
90 if_true = matcher.IfTrue();
91 if_false = matcher.IfFalse();
92
93 auto it = if_false->uses().begin();
94 if (it == if_false->uses().end()) break;
95 Node* branch1 = *it++;
96 if (branch1->opcode() != IrOpcode::kBranch) break;
97 if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
98 if (it != if_false->uses().end()) break;
99 Node* cond1 = branch1->InputAt(0);
100 if (cond1->opcode() != IrOpcode::kWord32Equal) break;
101 Int32BinopMatcher m1(cond1);
102 if (m1.left().node() != index) break;
103 if (!m1.right().HasValue()) break;
104 int32_t value1 = m1.right().Value();
105 if (values.find(value1) != values.end()) break;
106 DCHECK_NE(value, value1);
107
108 if (branch != node) {
109 branch->NullAllInputs();
110 if_true->ReplaceInput(0, node);
111 }
112 NodeProperties::ChangeOp(if_true, common()->IfValue(value));
113 if_false->NullAllInputs();
114 Enqueue(if_true);
115
116 branch = branch1;
117 value = value1;
118 values.insert(value);
119 }
120
121 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
122 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
123 if (branch == node) {
124 DCHECK_EQ(1u, values.size());
125 return false;
126 }
127 DCHECK_LT(1u, values.size());
128 node->ReplaceInput(0, index);
129 NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
130 if_true->ReplaceInput(0, node);
131 NodeProperties::ChangeOp(if_true, common()->IfValue(value));
132 Enqueue(if_true);
133 if_false->ReplaceInput(0, node);
134 NodeProperties::ChangeOp(if_false, common()->IfDefault());
135 Enqueue(if_false);
136 branch->NullAllInputs();
137 return true;
138 }
139
140 } // namespace compiler
141 } // namespace internal
142 } // namespace v8
143