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