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