Line data Source code
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 :
16 395302 : 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 790606 : zone_(zone) {}
26 :
27 :
28 395304 : void ControlFlowOptimizer::Optimize() {
29 395304 : Enqueue(graph()->start());
30 18508858 : while (!queue_.empty()) {
31 35436577 : Node* node = queue_.front();
32 : queue_.pop();
33 17718393 : if (node->IsDead()) continue;
34 17718329 : switch (node->opcode()) {
35 : case IrOpcode::kBranch:
36 1970177 : VisitBranch(node);
37 1970073 : break;
38 : default:
39 15748152 : VisitNode(node);
40 15748107 : break;
41 : }
42 : }
43 395303 : }
44 :
45 :
46 19984883 : void ControlFlowOptimizer::Enqueue(Node* node) {
47 : DCHECK_NOT_NULL(node);
48 79939470 : if (node->IsDead() || queued_.Get(node)) return;
49 : queued_.Set(node, true);
50 : queue_.push(node);
51 : }
52 :
53 :
54 17707560 : void ControlFlowOptimizer::VisitNode(Node* node) {
55 107398422 : for (Edge edge : node->use_edges()) {
56 44845431 : if (NodeProperties::IsControlEdge(edge)) {
57 19544765 : Enqueue(edge.from());
58 : }
59 : }
60 17707560 : }
61 :
62 :
63 1970176 : void ControlFlowOptimizer::VisitBranch(Node* node) {
64 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
65 3940348 : if (TryBuildSwitch(node)) return;
66 1959556 : VisitNode(node);
67 : }
68 :
69 :
70 2249600 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
71 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
72 :
73 1970178 : Node* branch = node;
74 1970178 : if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
75 1164956 : Node* cond = NodeProperties::GetValueInput(branch, 0);
76 1164956 : if (cond->opcode() != IrOpcode::kWord32Equal) return false;
77 227898 : Int32BinopMatcher m(cond);
78 : Node* index = m.left().node();
79 227898 : if (!m.right().HasValue()) return false;
80 224089 : 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 247580 : BranchMatcher matcher(branch);
88 : DCHECK(matcher.Matched());
89 :
90 247580 : if_true = matcher.IfTrue();
91 247580 : if_false = matcher.IfFalse();
92 :
93 : auto it = if_false->uses().begin();
94 247580 : if (it == if_false->uses().end()) break;
95 495160 : Node* branch1 = *it++;
96 247580 : if (branch1->opcode() != IrOpcode::kBranch) break;
97 25439 : if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
98 25164 : if (it != if_false->uses().end()) break;
99 24665 : Node* cond1 = branch1->InputAt(0);
100 24665 : if (cond1->opcode() != IrOpcode::kWord32Equal) break;
101 23590 : Int32BinopMatcher m1(cond1);
102 23590 : if (m1.left().node() != index) break;
103 23495 : if (!m1.right().HasValue()) break;
104 23493 : int32_t value1 = m1.right().Value();
105 23493 : if (values.find(value1) != values.end()) break;
106 : DCHECK_NE(value, value1);
107 :
108 23491 : if (branch != node) {
109 12877 : branch->NullAllInputs();
110 12877 : if_true->ReplaceInput(0, node);
111 : }
112 46982 : NodeProperties::ChangeOp(if_true, common()->IfValue(value));
113 23491 : if_false->NullAllInputs();
114 23491 : Enqueue(if_true);
115 :
116 : branch = branch1;
117 23491 : value = value1;
118 : values.insert(value);
119 : }
120 :
121 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
122 : DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
123 224089 : if (branch == node) {
124 : DCHECK_EQ(1u, values.size());
125 : return false;
126 : }
127 : DCHECK_LT(1u, values.size());
128 10614 : node->ReplaceInput(0, index);
129 21228 : NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
130 10614 : if_true->ReplaceInput(0, node);
131 21228 : NodeProperties::ChangeOp(if_true, common()->IfValue(value));
132 10614 : Enqueue(if_true);
133 10614 : if_false->ReplaceInput(0, node);
134 10614 : NodeProperties::ChangeOp(if_false, common()->IfDefault());
135 10614 : Enqueue(if_false);
136 10614 : branch->NullAllInputs();
137 10614 : return true;
138 : }
139 :
140 : } // namespace compiler
141 : } // namespace internal
142 : } // namespace v8
|