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