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 if (TryCloneBranch(node)) return;
67 VisitNode(node);
68 }
69
70
TryCloneBranch(Node * node)71 bool ControlFlowOptimizer::TryCloneBranch(Node* node) {
72 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
73
74 // This optimization is a special case of (super)block cloning. It takes an
75 // input graph as shown below and clones the Branch node for every predecessor
76 // to the Merge, essentially removing the Merge completely. This avoids
77 // materializing the bit for the Phi and may offer potential for further
78 // branch folding optimizations (i.e. because one or more inputs to the Phi is
79 // a constant). Note that there may be more Phi nodes hanging off the Merge,
80 // but we can only a certain subset of them currently (actually only Phi and
81 // EffectPhi nodes whose uses have either the IfTrue or IfFalse as control
82 // input).
83
84 // Control1 ... ControlN
85 // ^ ^
86 // | | Cond1 ... CondN
87 // +----+ +----+ ^ ^
88 // | | | |
89 // | | +----+ |
90 // Merge<--+ | +------------+
91 // ^ \|/
92 // | Phi
93 // | |
94 // Branch----+
95 // ^
96 // |
97 // +-----+-----+
98 // | |
99 // IfTrue IfFalse
100 // ^ ^
101 // | |
102
103 // The resulting graph (modulo the Phi and EffectPhi nodes) looks like this:
104
105 // Control1 Cond1 ... ControlN CondN
106 // ^ ^ ^ ^
107 // \ / \ /
108 // Branch ... Branch
109 // ^ ^
110 // | |
111 // +---+---+ +---+----+
112 // | | | |
113 // IfTrue IfFalse ... IfTrue IfFalse
114 // ^ ^ ^ ^
115 // | | | |
116 // +--+ +-------------+ |
117 // | | +--------------+ +--+
118 // | | | |
119 // Merge Merge
120 // ^ ^
121 // | |
122
123 Node* branch = node;
124 Node* cond = NodeProperties::GetValueInput(branch, 0);
125 if (!cond->OwnedBy(branch) || cond->opcode() != IrOpcode::kPhi) return false;
126 Node* merge = NodeProperties::GetControlInput(branch);
127 if (merge->opcode() != IrOpcode::kMerge ||
128 NodeProperties::GetControlInput(cond) != merge) {
129 return false;
130 }
131 // Grab the IfTrue/IfFalse projections of the Branch.
132 BranchMatcher matcher(branch);
133 // Check/collect other Phi/EffectPhi nodes hanging off the Merge.
134 NodeVector phis(zone());
135 for (Node* const use : merge->uses()) {
136 if (use == branch || use == cond) continue;
137 // We cannot currently deal with non-Phi/EffectPhi nodes hanging off the
138 // Merge. Ideally, we would just clone the nodes (and everything that
139 // depends on it to some distant join point), but that requires knowledge
140 // about dominance/post-dominance.
141 if (!NodeProperties::IsPhi(use)) return false;
142 for (Edge edge : use->use_edges()) {
143 // Right now we can only handle Phi/EffectPhi nodes whose uses are
144 // directly control-dependend on either the IfTrue or the IfFalse
145 // successor, because we know exactly how to update those uses.
146 // TODO(turbofan): Generalize this to all Phi/EffectPhi nodes using
147 // dominance/post-dominance on the sea of nodes.
148 if (edge.from()->op()->ControlInputCount() != 1) return false;
149 Node* control = NodeProperties::GetControlInput(edge.from());
150 if (NodeProperties::IsPhi(edge.from())) {
151 control = NodeProperties::GetControlInput(control, edge.index());
152 }
153 if (control != matcher.IfTrue() && control != matcher.IfFalse())
154 return false;
155 }
156 phis.push_back(use);
157 }
158 BranchHint const hint = BranchHintOf(branch->op());
159 int const input_count = merge->op()->ControlInputCount();
160 DCHECK_LE(1, input_count);
161 Node** const inputs = zone()->NewArray<Node*>(2 * input_count);
162 Node** const merge_true_inputs = &inputs[0];
163 Node** const merge_false_inputs = &inputs[input_count];
164 for (int index = 0; index < input_count; ++index) {
165 Node* cond1 = NodeProperties::GetValueInput(cond, index);
166 Node* control1 = NodeProperties::GetControlInput(merge, index);
167 Node* branch1 = graph()->NewNode(common()->Branch(hint), cond1, control1);
168 merge_true_inputs[index] = graph()->NewNode(common()->IfTrue(), branch1);
169 merge_false_inputs[index] = graph()->NewNode(common()->IfFalse(), branch1);
170 Enqueue(branch1);
171 }
172 Node* const merge_true = graph()->NewNode(common()->Merge(input_count),
173 input_count, merge_true_inputs);
174 Node* const merge_false = graph()->NewNode(common()->Merge(input_count),
175 input_count, merge_false_inputs);
176 for (Node* const phi : phis) {
177 for (int index = 0; index < input_count; ++index) {
178 inputs[index] = phi->InputAt(index);
179 }
180 inputs[input_count] = merge_true;
181 Node* phi_true = graph()->NewNode(phi->op(), input_count + 1, inputs);
182 inputs[input_count] = merge_false;
183 Node* phi_false = graph()->NewNode(phi->op(), input_count + 1, inputs);
184 for (Edge edge : phi->use_edges()) {
185 Node* control = NodeProperties::GetControlInput(edge.from());
186 if (NodeProperties::IsPhi(edge.from())) {
187 control = NodeProperties::GetControlInput(control, edge.index());
188 }
189 DCHECK(control == matcher.IfTrue() || control == matcher.IfFalse());
190 edge.UpdateTo((control == matcher.IfTrue()) ? phi_true : phi_false);
191 }
192 phi->Kill();
193 }
194 // Fix up IfTrue and IfFalse and kill all dead nodes.
195 matcher.IfFalse()->ReplaceUses(merge_false);
196 matcher.IfTrue()->ReplaceUses(merge_true);
197 matcher.IfFalse()->Kill();
198 matcher.IfTrue()->Kill();
199 branch->Kill();
200 cond->Kill();
201 merge->Kill();
202 return true;
203 }
204
205
TryBuildSwitch(Node * node)206 bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
207 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
208
209 Node* branch = node;
210 if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
211 Node* cond = NodeProperties::GetValueInput(branch, 0);
212 if (cond->opcode() != IrOpcode::kWord32Equal) return false;
213 Int32BinopMatcher m(cond);
214 Node* index = m.left().node();
215 if (!m.right().HasValue()) return false;
216 int32_t value = m.right().Value();
217 ZoneSet<int32_t> values(zone());
218 values.insert(value);
219
220 Node* if_false;
221 Node* if_true;
222 while (true) {
223 BranchMatcher matcher(branch);
224 DCHECK(matcher.Matched());
225
226 if_true = matcher.IfTrue();
227 if_false = matcher.IfFalse();
228
229 auto it = if_false->uses().begin();
230 if (it == if_false->uses().end()) break;
231 Node* branch1 = *it++;
232 if (branch1->opcode() != IrOpcode::kBranch) break;
233 if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
234 if (it != if_false->uses().end()) break;
235 Node* cond1 = branch1->InputAt(0);
236 if (cond1->opcode() != IrOpcode::kWord32Equal) break;
237 Int32BinopMatcher m1(cond1);
238 if (m1.left().node() != index) break;
239 if (!m1.right().HasValue()) break;
240 int32_t value1 = m1.right().Value();
241 if (values.find(value1) != values.end()) break;
242 DCHECK_NE(value, value1);
243
244 if (branch != node) {
245 branch->NullAllInputs();
246 if_true->ReplaceInput(0, node);
247 }
248 NodeProperties::ChangeOp(if_true, common()->IfValue(value));
249 if_false->NullAllInputs();
250 Enqueue(if_true);
251
252 branch = branch1;
253 value = value1;
254 values.insert(value);
255 }
256
257 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
258 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
259 if (branch == node) {
260 DCHECK_EQ(1u, values.size());
261 return false;
262 }
263 DCHECK_LT(1u, values.size());
264 node->ReplaceInput(0, index);
265 NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
266 if_true->ReplaceInput(0, node);
267 NodeProperties::ChangeOp(if_true, common()->IfValue(value));
268 Enqueue(if_true);
269 if_false->ReplaceInput(0, node);
270 NodeProperties::ChangeOp(if_false, common()->IfDefault());
271 Enqueue(if_false);
272 branch->NullAllInputs();
273 return true;
274 }
275
276 } // namespace compiler
277 } // namespace internal
278 } // namespace v8
279