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 464079 : 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 928163 : zone_(zone) {}
26 :
27 :
28 464077 : void ControlFlowOptimizer::Optimize() {
29 464077 : Enqueue(graph()->start());
30 19642477 : while (!queue_.empty()) {
31 19178394 : Node* node = queue_.front();
32 : queue_.pop();
33 19179330 : if (node->IsDead()) continue;
34 19179330 : switch (node->opcode()) {
35 : case IrOpcode::kBranch:
36 1865745 : VisitBranch(node);
37 1865746 : break;
38 : default:
39 17313585 : VisitNode(node);
40 17313464 : break;
41 : }
42 : }
43 464083 : }
44 :
45 :
46 21307683 : void ControlFlowOptimizer::Enqueue(Node* node) {
47 : DCHECK_NOT_NULL(node);
48 63922964 : if (node->IsDead() || queued_.Get(node)) return;
49 : queued_.Set(node, true);
50 : queue_.push(node);
51 : }
52 :
53 :
54 19177379 : void ControlFlowOptimizer::VisitNode(Node* node) {
55 123496706 : for (Edge edge : node->use_edges()) {
56 52160121 : if (NodeProperties::IsControlEdge(edge)) {
57 20831022 : Enqueue(edge.from());
58 : }
59 : }
60 19176464 : }
61 :
62 :
63 1865744 : void ControlFlowOptimizer::VisitBranch(Node* node) {
64 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
65 1865744 : if (TryBuildSwitch(node)) return;
66 1863196 : VisitNode(node);
67 : }
68 :
69 :
70 1865746 : bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
71 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
72 :
73 : Node* branch = node;
74 1865746 : if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
75 957039 : Node* cond = NodeProperties::GetValueInput(branch, 0);
76 957040 : if (cond->opcode() != IrOpcode::kWord32Equal) return false;
77 177243 : Int32BinopMatcher m(cond);
78 : Node* index = m.left().node();
79 177243 : if (!m.right().HasValue()) return false;
80 174676 : 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 7396 : while (true) {
88 182072 : BranchMatcher matcher(branch);
89 : DCHECK(matcher.Matched());
90 :
91 : if_true = matcher.IfTrue();
92 : if_false = matcher.IfFalse();
93 :
94 182072 : auto it = if_false->uses().begin();
95 182072 : if (it == if_false->uses().end()) break;
96 364144 : Node* branch1 = *it++;
97 182072 : if (branch1->opcode() != IrOpcode::kBranch) break;
98 11121 : if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
99 8514 : if (it != if_false->uses().end()) break;
100 : Node* cond1 = branch1->InputAt(0);
101 8372 : if (cond1->opcode() != IrOpcode::kWord32Equal) break;
102 7908 : Int32BinopMatcher m1(cond1);
103 7908 : if (m1.left().node() != index) break;
104 7828 : if (!m1.right().HasValue()) break;
105 7828 : int32_t value1 = m1.right().Value();
106 7828 : if (values.find(value1) != values.end()) break;
107 : DCHECK_NE(value, value1);
108 :
109 7396 : if (branch != node) {
110 4845 : branch->NullAllInputs();
111 4845 : if_true->ReplaceInput(0, node);
112 : }
113 7396 : NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
114 7396 : if_false->NullAllInputs();
115 7396 : Enqueue(if_true);
116 :
117 : branch = branch1;
118 7396 : value = value1;
119 : values.insert(value);
120 : }
121 :
122 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
123 : DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
124 174676 : if (branch == node) {
125 : DCHECK_EQ(1u, values.size());
126 : return false;
127 : }
128 : DCHECK_LT(1u, values.size());
129 2551 : node->ReplaceInput(0, index);
130 2551 : NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
131 2551 : if_true->ReplaceInput(0, node);
132 2551 : NodeProperties::ChangeOp(if_true, common()->IfValue(value, order++));
133 2551 : Enqueue(if_true);
134 2551 : if_false->ReplaceInput(0, node);
135 2551 : NodeProperties::ChangeOp(if_false, common()->IfDefault());
136 2551 : Enqueue(if_false);
137 2551 : branch->NullAllInputs();
138 2551 : return true;
139 : }
140 :
141 : } // namespace compiler
142 : } // namespace internal
143 121996 : } // namespace v8
|