1 // Copyright 2014 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/common-operator-reducer.h"
6
7 #include <algorithm>
8
9 #include "src/compiler/common-operator.h"
10 #include "src/compiler/graph.h"
11 #include "src/compiler/machine-operator.h"
12 #include "src/compiler/node.h"
13 #include "src/compiler/node-matchers.h"
14 #include "src/compiler/node-properties.h"
15
16 namespace v8 {
17 namespace internal {
18 namespace compiler {
19
20 namespace {
21
DecideCondition(Node * const cond)22 Decision DecideCondition(Node* const cond) {
23 switch (cond->opcode()) {
24 case IrOpcode::kInt32Constant: {
25 Int32Matcher mcond(cond);
26 return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 }
28 case IrOpcode::kHeapConstant: {
29 HeapObjectMatcher mcond(cond);
30 return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 }
32 default:
33 return Decision::kUnknown;
34 }
35 }
36
37 } // namespace
38
CommonOperatorReducer(Editor * editor,Graph * graph,CommonOperatorBuilder * common,MachineOperatorBuilder * machine)39 CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
40 CommonOperatorBuilder* common,
41 MachineOperatorBuilder* machine)
42 : AdvancedReducer(editor),
43 graph_(graph),
44 common_(common),
45 machine_(machine),
46 dead_(graph->NewNode(common->Dead())) {
47 NodeProperties::SetType(dead_, Type::None());
48 }
49
Reduce(Node * node)50 Reduction CommonOperatorReducer::Reduce(Node* node) {
51 switch (node->opcode()) {
52 case IrOpcode::kBranch:
53 return ReduceBranch(node);
54 case IrOpcode::kDeoptimizeIf:
55 case IrOpcode::kDeoptimizeUnless:
56 return ReduceDeoptimizeConditional(node);
57 case IrOpcode::kMerge:
58 return ReduceMerge(node);
59 case IrOpcode::kEffectPhi:
60 return ReduceEffectPhi(node);
61 case IrOpcode::kPhi:
62 return ReducePhi(node);
63 case IrOpcode::kReturn:
64 return ReduceReturn(node);
65 case IrOpcode::kSelect:
66 return ReduceSelect(node);
67 default:
68 break;
69 }
70 return NoChange();
71 }
72
73
ReduceBranch(Node * node)74 Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
75 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
76 Node* const cond = node->InputAt(0);
77 // Swap IfTrue/IfFalse on {branch} if {cond} is a BooleanNot and use the input
78 // to BooleanNot as new condition for {branch}. Note we assume that {cond} was
79 // already properly optimized before we get here (as guaranteed by the graph
80 // reduction logic). The same applies if {cond} is a Select acting as boolean
81 // not (i.e. true being returned in the false case and vice versa).
82 if (cond->opcode() == IrOpcode::kBooleanNot ||
83 (cond->opcode() == IrOpcode::kSelect &&
84 DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
85 DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 for (Node* const use : node->uses()) {
87 switch (use->opcode()) {
88 case IrOpcode::kIfTrue:
89 NodeProperties::ChangeOp(use, common()->IfFalse());
90 break;
91 case IrOpcode::kIfFalse:
92 NodeProperties::ChangeOp(use, common()->IfTrue());
93 break;
94 default:
95 UNREACHABLE();
96 }
97 }
98 // Update the condition of {branch}. No need to mark the uses for revisit,
99 // since we tell the graph reducer that the {branch} was changed and the
100 // graph reduction logic will ensure that the uses are revisited properly.
101 node->ReplaceInput(0, cond->InputAt(0));
102 // Negate the hint for {branch}.
103 NodeProperties::ChangeOp(
104 node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 return Changed(node);
106 }
107 Decision const decision = DecideCondition(cond);
108 if (decision == Decision::kUnknown) return NoChange();
109 Node* const control = node->InputAt(1);
110 for (Node* const use : node->uses()) {
111 switch (use->opcode()) {
112 case IrOpcode::kIfTrue:
113 Replace(use, (decision == Decision::kTrue) ? control : dead());
114 break;
115 case IrOpcode::kIfFalse:
116 Replace(use, (decision == Decision::kFalse) ? control : dead());
117 break;
118 default:
119 UNREACHABLE();
120 }
121 }
122 return Replace(dead());
123 }
124
ReduceDeoptimizeConditional(Node * node)125 Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
126 DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
127 node->opcode() == IrOpcode::kDeoptimizeUnless);
128 bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129 DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
130 Node* condition = NodeProperties::GetValueInput(node, 0);
131 Node* frame_state = NodeProperties::GetValueInput(node, 1);
132 Node* effect = NodeProperties::GetEffectInput(node);
133 Node* control = NodeProperties::GetControlInput(node);
134 // Swap DeoptimizeIf/DeoptimizeUnless on {node} if {cond} is a BooleaNot
135 // and use the input to BooleanNot as new condition for {node}. Note we
136 // assume that {cond} was already properly optimized before we get here
137 // (as guaranteed by the graph reduction logic).
138 if (condition->opcode() == IrOpcode::kBooleanNot) {
139 NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
140 NodeProperties::ChangeOp(
141 node, condition_is_true
142 ? common()->DeoptimizeIf(p.kind(), p.reason())
143 : common()->DeoptimizeUnless(p.kind(), p.reason()));
144 return Changed(node);
145 }
146 Decision const decision = DecideCondition(condition);
147 if (decision == Decision::kUnknown) return NoChange();
148 if (condition_is_true == (decision == Decision::kTrue)) {
149 ReplaceWithValue(node, dead(), effect, control);
150 } else {
151 control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
152 frame_state, effect, control);
153 // TODO(bmeurer): This should be on the AdvancedReducer somehow.
154 NodeProperties::MergeControlToEnd(graph(), common(), control);
155 Revisit(graph()->end());
156 }
157 return Replace(dead());
158 }
159
ReduceMerge(Node * node)160 Reduction CommonOperatorReducer::ReduceMerge(Node* node) {
161 DCHECK_EQ(IrOpcode::kMerge, node->opcode());
162 //
163 // Check if this is a merge that belongs to an unused diamond, which means
164 // that:
165 //
166 // a) the {Merge} has no {Phi} or {EffectPhi} uses, and
167 // b) the {Merge} has two inputs, one {IfTrue} and one {IfFalse}, which are
168 // both owned by the Merge, and
169 // c) and the {IfTrue} and {IfFalse} nodes point to the same {Branch}.
170 //
171 if (node->InputCount() == 2) {
172 for (Node* const use : node->uses()) {
173 if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
174 }
175 Node* if_true = node->InputAt(0);
176 Node* if_false = node->InputAt(1);
177 if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
178 if (if_true->opcode() == IrOpcode::kIfTrue &&
179 if_false->opcode() == IrOpcode::kIfFalse &&
180 if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
181 if_false->OwnedBy(node)) {
182 Node* const branch = if_true->InputAt(0);
183 DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
184 DCHECK(branch->OwnedBy(if_true, if_false));
185 Node* const control = branch->InputAt(1);
186 // Mark the {branch} as {Dead}.
187 branch->TrimInputCount(0);
188 NodeProperties::ChangeOp(branch, common()->Dead());
189 return Replace(control);
190 }
191 }
192 return NoChange();
193 }
194
195
ReduceEffectPhi(Node * node)196 Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
197 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
198 Node::Inputs inputs = node->inputs();
199 int const effect_input_count = inputs.count() - 1;
200 DCHECK_LE(1, effect_input_count);
201 Node* const merge = inputs[effect_input_count];
202 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
203 DCHECK_EQ(effect_input_count, merge->InputCount());
204 Node* const effect = inputs[0];
205 DCHECK_NE(node, effect);
206 for (int i = 1; i < effect_input_count; ++i) {
207 Node* const input = inputs[i];
208 if (input == node) {
209 // Ignore redundant inputs.
210 DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
211 continue;
212 }
213 if (input != effect) return NoChange();
214 }
215 // We might now be able to further reduce the {merge} node.
216 Revisit(merge);
217 return Replace(effect);
218 }
219
220
ReducePhi(Node * node)221 Reduction CommonOperatorReducer::ReducePhi(Node* node) {
222 DCHECK_EQ(IrOpcode::kPhi, node->opcode());
223 Node::Inputs inputs = node->inputs();
224 int const value_input_count = inputs.count() - 1;
225 DCHECK_LE(1, value_input_count);
226 Node* const merge = inputs[value_input_count];
227 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
228 DCHECK_EQ(value_input_count, merge->InputCount());
229 if (value_input_count == 2) {
230 Node* vtrue = inputs[0];
231 Node* vfalse = inputs[1];
232 Node::Inputs merge_inputs = merge->inputs();
233 Node* if_true = merge_inputs[0];
234 Node* if_false = merge_inputs[1];
235 if (if_true->opcode() != IrOpcode::kIfTrue) {
236 std::swap(if_true, if_false);
237 std::swap(vtrue, vfalse);
238 }
239 if (if_true->opcode() == IrOpcode::kIfTrue &&
240 if_false->opcode() == IrOpcode::kIfFalse &&
241 if_true->InputAt(0) == if_false->InputAt(0)) {
242 Node* const branch = if_true->InputAt(0);
243 // Check that the branch is not dead already.
244 if (branch->opcode() != IrOpcode::kBranch) return NoChange();
245 Node* const cond = branch->InputAt(0);
246 if (cond->opcode() == IrOpcode::kFloat32LessThan) {
247 Float32BinopMatcher mcond(cond);
248 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
249 vfalse->opcode() == IrOpcode::kFloat32Sub) {
250 Float32BinopMatcher mvfalse(vfalse);
251 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
252 // We might now be able to further reduce the {merge} node.
253 Revisit(merge);
254 return Change(node, machine()->Float32Abs(), vtrue);
255 }
256 }
257 } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
258 Float64BinopMatcher mcond(cond);
259 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
260 vfalse->opcode() == IrOpcode::kFloat64Sub) {
261 Float64BinopMatcher mvfalse(vfalse);
262 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
263 // We might now be able to further reduce the {merge} node.
264 Revisit(merge);
265 return Change(node, machine()->Float64Abs(), vtrue);
266 }
267 }
268 }
269 }
270 }
271 Node* const value = inputs[0];
272 DCHECK_NE(node, value);
273 for (int i = 1; i < value_input_count; ++i) {
274 Node* const input = inputs[i];
275 if (input == node) {
276 // Ignore redundant inputs.
277 DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
278 continue;
279 }
280 if (input != value) return NoChange();
281 }
282 // We might now be able to further reduce the {merge} node.
283 Revisit(merge);
284 return Replace(value);
285 }
286
ReduceReturn(Node * node)287 Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
288 DCHECK_EQ(IrOpcode::kReturn, node->opcode());
289 Node* effect = NodeProperties::GetEffectInput(node);
290 if (effect->opcode() == IrOpcode::kCheckpoint) {
291 // Any {Return} node can never be used to insert a deoptimization point,
292 // hence checkpoints can be cut out of the effect chain flowing into it.
293 effect = NodeProperties::GetEffectInput(effect);
294 NodeProperties::ReplaceEffectInput(node, effect);
295 Reduction const reduction = ReduceReturn(node);
296 return reduction.Changed() ? reduction : Changed(node);
297 }
298 // TODO(ahaas): Extend the reduction below to multiple return values.
299 if (ValueInputCountOfReturn(node->op()) != 1) {
300 return NoChange();
301 }
302 Node* pop_count = NodeProperties::GetValueInput(node, 0);
303 Node* value = NodeProperties::GetValueInput(node, 1);
304 Node* control = NodeProperties::GetControlInput(node);
305 if (value->opcode() == IrOpcode::kPhi &&
306 NodeProperties::GetControlInput(value) == control &&
307 control->opcode() == IrOpcode::kMerge) {
308 // This optimization pushes {Return} nodes through merges. It checks that
309 // the return value is actually a {Phi} and the return control dependency
310 // is the {Merge} to which the {Phi} belongs.
311
312 // Value1 ... ValueN Control1 ... ControlN
313 // ^ ^ ^ ^
314 // | | | |
315 // +----+-----+ +------+-----+
316 // | |
317 // Phi --------------> Merge
318 // ^ ^
319 // | |
320 // | +-----------------+
321 // | |
322 // Return -----> Effect
323 // ^
324 // |
325 // End
326
327 // Now the effect input to the {Return} node can be either an {EffectPhi}
328 // hanging off the same {Merge}, or the {Merge} node is only connected to
329 // the {Return} and the {Phi}, in which case we know that the effect input
330 // must somehow dominate all merged branches.
331
332 Node::Inputs control_inputs = control->inputs();
333 Node::Inputs value_inputs = value->inputs();
334 DCHECK_NE(0, control_inputs.count());
335 DCHECK_EQ(control_inputs.count(), value_inputs.count() - 1);
336 DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
337 DCHECK_NE(0, graph()->end()->InputCount());
338 if (control->OwnedBy(node, value)) {
339 for (int i = 0; i < control_inputs.count(); ++i) {
340 // Create a new {Return} and connect it to {end}. We don't need to mark
341 // {end} as revisit, because we mark {node} as {Dead} below, which was
342 // previously connected to {end}, so we know for sure that at some point
343 // the reducer logic will visit {end} again.
344 Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
345 effect, control_inputs[i]);
346 NodeProperties::MergeControlToEnd(graph(), common(), ret);
347 }
348 // Mark the Merge {control} and Return {node} as {dead}.
349 Replace(control, dead());
350 return Replace(dead());
351 } else if (effect->opcode() == IrOpcode::kEffectPhi &&
352 NodeProperties::GetControlInput(effect) == control) {
353 Node::Inputs effect_inputs = effect->inputs();
354 DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
355 for (int i = 0; i < control_inputs.count(); ++i) {
356 // Create a new {Return} and connect it to {end}. We don't need to mark
357 // {end} as revisit, because we mark {node} as {Dead} below, which was
358 // previously connected to {end}, so we know for sure that at some point
359 // the reducer logic will visit {end} again.
360 Node* ret = graph()->NewNode(node->op(), pop_count, value_inputs[i],
361 effect_inputs[i], control_inputs[i]);
362 NodeProperties::MergeControlToEnd(graph(), common(), ret);
363 }
364 // Mark the Merge {control} and Return {node} as {dead}.
365 Replace(control, dead());
366 return Replace(dead());
367 }
368 }
369 return NoChange();
370 }
371
ReduceSelect(Node * node)372 Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
373 DCHECK_EQ(IrOpcode::kSelect, node->opcode());
374 Node* const cond = node->InputAt(0);
375 Node* const vtrue = node->InputAt(1);
376 Node* const vfalse = node->InputAt(2);
377 if (vtrue == vfalse) return Replace(vtrue);
378 switch (DecideCondition(cond)) {
379 case Decision::kTrue:
380 return Replace(vtrue);
381 case Decision::kFalse:
382 return Replace(vfalse);
383 case Decision::kUnknown:
384 break;
385 }
386 switch (cond->opcode()) {
387 case IrOpcode::kFloat32LessThan: {
388 Float32BinopMatcher mcond(cond);
389 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
390 vfalse->opcode() == IrOpcode::kFloat32Sub) {
391 Float32BinopMatcher mvfalse(vfalse);
392 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
393 return Change(node, machine()->Float32Abs(), vtrue);
394 }
395 }
396 break;
397 }
398 case IrOpcode::kFloat64LessThan: {
399 Float64BinopMatcher mcond(cond);
400 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
401 vfalse->opcode() == IrOpcode::kFloat64Sub) {
402 Float64BinopMatcher mvfalse(vfalse);
403 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
404 return Change(node, machine()->Float64Abs(), vtrue);
405 }
406 }
407 break;
408 }
409 default:
410 break;
411 }
412 return NoChange();
413 }
414
415
Change(Node * node,Operator const * op,Node * a)416 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
417 Node* a) {
418 node->ReplaceInput(0, a);
419 node->TrimInputCount(1);
420 NodeProperties::ChangeOp(node, op);
421 return Changed(node);
422 }
423
424
Change(Node * node,Operator const * op,Node * a,Node * b)425 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
426 Node* b) {
427 node->ReplaceInput(0, a);
428 node->ReplaceInput(1, b);
429 node->TrimInputCount(2);
430 NodeProperties::ChangeOp(node, op);
431 return Changed(node);
432 }
433
434 } // namespace compiler
435 } // namespace internal
436 } // namespace v8
437