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