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 int32_t order = 1;
87 while (true) {
88 BranchMatcher matcher(branch);
89 DCHECK(matcher.Matched());
90
91 if_true = matcher.IfTrue();
92 if_false = matcher.IfFalse();
93
94 auto it = if_false->uses().begin();
95 if (it == if_false->uses().end()) break;
96 Node* branch1 = *it++;
97 if (branch1->opcode() != IrOpcode::kBranch) break;
98 if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
99 if (it != if_false->uses().end()) break;
100 Node* cond1 = branch1->InputAt(0);
101 if (cond1->opcode() != IrOpcode::kWord32Equal) break;
102 Int32BinopMatcher m1(cond1);
103 if (m1.left().node() != index) break;
104 if (!m1.right().HasValue()) break;
105 int32_t value1 = m1.right().Value();
106 if (values.find(value1) != values.end()) break;
107 DCHECK_NE(value, value1);
108
109 if (branch != node) {
110 branch->NullAllInputs();
111 if_true->ReplaceInput(0, node);
112 }
113 NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
114 if_false->NullAllInputs();
115 Enqueue(if_true);
116
117 branch = branch1;
118 value = value1;
119 values.insert(value);
120 }
121
122 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
123 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
124 if (branch == node) {
125 DCHECK_EQ(1u, values.size());
126 return false;
127 }
128 DCHECK_LT(1u, values.size());
129 node->ReplaceInput(0, index);
130 NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
131 if_true->ReplaceInput(0, node);
132 NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
133 Enqueue(if_true);
134 if_false->ReplaceInput(0, node);
135 NodeProperties::ChangeOp(if_false, common()->IfDefault());
136 Enqueue(if_false);
137 branch->NullAllInputs();
138 return true;
139 }
140
141 } // namespace compiler
142 } // namespace internal
143 } // namespace v8
144