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 10693598 : Decision DecideCondition(JSHeapBroker* broker, Node* const cond) {
23 10693598 : switch (cond->opcode()) {
24 : case IrOpcode::kInt32Constant: {
25 : Int32Matcher mcond(cond);
26 293447 : return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 : }
28 : case IrOpcode::kHeapConstant: {
29 : HeapObjectMatcher mcond(cond);
30 239606 : return mcond.Ref(broker).BooleanValue() ? Decision::kTrue
31 119803 : : Decision::kFalse;
32 : }
33 : default:
34 : return Decision::kUnknown;
35 : }
36 : }
37 :
38 : } // namespace
39 :
40 2815439 : 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 2815439 : dead_(graph->NewNode(common->Dead())),
51 5630893 : zone_(temp_zone) {
52 : NodeProperties::SetType(dead_, Type::None());
53 2815454 : }
54 :
55 272180640 : Reduction CommonOperatorReducer::Reduce(Node* node) {
56 : DisallowHeapAccess no_heap_access;
57 272180640 : switch (node->opcode()) {
58 : case IrOpcode::kBranch:
59 9817931 : return ReduceBranch(node);
60 : case IrOpcode::kDeoptimizeIf:
61 : case IrOpcode::kDeoptimizeUnless:
62 742977 : return ReduceDeoptimizeConditional(node);
63 : case IrOpcode::kMerge:
64 6606706 : return ReduceMerge(node);
65 : case IrOpcode::kEffectPhi:
66 6300831 : return ReduceEffectPhi(node);
67 : case IrOpcode::kPhi:
68 3998909 : return ReducePhi(node);
69 : case IrOpcode::kReturn:
70 3696572 : return ReduceReturn(node);
71 : case IrOpcode::kSelect:
72 95877 : return ReduceSelect(node);
73 : case IrOpcode::kSwitch:
74 63752 : return ReduceSwitch(node);
75 : default:
76 : break;
77 : }
78 : return NoChange();
79 : }
80 :
81 :
82 20438472 : Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
83 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
84 9817992 : 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 19635984 : if (cond->opcode() == IrOpcode::kBooleanNot ||
91 38589 : (cond->opcode() == IrOpcode::kSelect &&
92 44059 : DecideCondition(broker(), cond->InputAt(1)) == Decision::kFalse &&
93 5470 : DecideCondition(broker(), cond->InputAt(2)) == Decision::kTrue)) {
94 40626 : for (Node* const use : node->uses()) {
95 13542 : switch (use->opcode()) {
96 : case IrOpcode::kIfTrue:
97 6771 : NodeProperties::ChangeOp(use, common()->IfFalse());
98 6771 : break;
99 : case IrOpcode::kIfFalse:
100 6771 : NodeProperties::ChangeOp(use, common()->IfTrue());
101 6771 : 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 6771 : node->ReplaceInput(0, cond->InputAt(0));
110 : // Negate the hint for {branch}.
111 : NodeProperties::ChangeOp(
112 13542 : node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
113 : return Changed(node);
114 : }
115 9811221 : Decision const decision = DecideCondition(broker(), cond);
116 9811225 : if (decision == Decision::kUnknown) return NoChange();
117 : Node* const control = node->InputAt(1);
118 2214345 : for (Node* const use : node->uses()) {
119 738115 : switch (use->opcode()) {
120 : case IrOpcode::kIfTrue:
121 1107174 : Replace(use, (decision == Decision::kTrue) ? control : dead());
122 : break;
123 : case IrOpcode::kIfFalse:
124 369058 : Replace(use, (decision == Decision::kFalse) ? control : dead());
125 : break;
126 : default:
127 0 : UNREACHABLE();
128 : }
129 : }
130 : return Replace(dead());
131 : }
132 :
133 1503242 : Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
134 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
135 : node->opcode() == IrOpcode::kDeoptimizeUnless);
136 742973 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
137 742973 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
138 1485956 : Node* condition = NodeProperties::GetValueInput(node, 0);
139 742971 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
140 742974 : Node* effect = NodeProperties::GetEffectInput(node);
141 742984 : 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 742984 : if (condition->opcode() == IrOpcode::kBooleanNot) {
147 0 : NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
148 : NodeProperties::ChangeOp(
149 : node,
150 : condition_is_true
151 0 : ? common()->DeoptimizeIf(p.kind(), p.reason(), p.feedback())
152 0 : : common()->DeoptimizeUnless(p.kind(), p.reason(), p.feedback()));
153 : return Changed(node);
154 : }
155 742984 : Decision const decision = DecideCondition(broker(), condition);
156 742973 : if (decision == Decision::kUnknown) return NoChange();
157 3868 : if (condition_is_true == (decision == Decision::kTrue)) {
158 3868 : ReplaceWithValue(node, dead(), effect, control);
159 : } else {
160 : control = graph()->NewNode(
161 : common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
162 6366 : effect, control);
163 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
164 3183 : NodeProperties::MergeControlToEnd(graph(), common(), control);
165 3183 : Revisit(graph()->end());
166 : }
167 : return Replace(dead());
168 : }
169 :
170 6608943 : 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 6606041 : if (node->InputCount() == 2) {
182 40528188 : for (Node* const use : node->uses()) {
183 17413758 : if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
184 : }
185 : Node* if_true = node->InputAt(0);
186 : Node* if_false = node->InputAt(1);
187 523337 : if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
188 418089 : if (if_true->opcode() == IrOpcode::kIfTrue &&
189 264666 : if_false->opcode() == IrOpcode::kIfFalse &&
190 266171 : if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
191 2942 : 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 2902 : branch->TrimInputCount(0);
198 2902 : NodeProperties::ChangeOp(branch, common()->Dead());
199 : return Replace(control);
200 : }
201 : }
202 : return NoChange();
203 : }
204 :
205 :
206 6300816 : Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
207 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
208 : Node::Inputs inputs = node->inputs();
209 6300816 : 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 6718197 : for (int i = 1; i < effect_input_count; ++i) {
217 : Node* const input = inputs[i];
218 6475629 : if (input == node) {
219 : // Ignore redundant inputs.
220 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
221 : continue;
222 : }
223 6475635 : if (input != effect) return NoChange();
224 : }
225 : // We might now be able to further reduce the {merge} node.
226 242568 : Revisit(merge);
227 : return Replace(effect);
228 : }
229 :
230 :
231 3999093 : Reduction CommonOperatorReducer::ReducePhi(Node* node) {
232 : DCHECK_EQ(IrOpcode::kPhi, node->opcode());
233 : Node::Inputs inputs = node->inputs();
234 3999091 : 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 3999091 : 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 6724284 : if (if_true->opcode() != IrOpcode::kIfTrue) {
246 : std::swap(if_true, if_false);
247 : std::swap(vtrue, vfalse);
248 : }
249 5281588 : if (if_true->opcode() == IrOpcode::kIfTrue &&
250 4788593 : if_false->opcode() == IrOpcode::kIfFalse &&
251 : if_true->InputAt(0) == if_false->InputAt(0)) {
252 1287031 : Node* const branch = if_true->InputAt(0);
253 : // Check that the branch is not dead already.
254 1287031 : if (branch->opcode() != IrOpcode::kBranch) return NoChange();
255 1287010 : Node* const cond = branch->InputAt(0);
256 1287010 : if (cond->opcode() == IrOpcode::kFloat32LessThan) {
257 286 : Float32BinopMatcher mcond(cond);
258 288 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
259 9 : 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 61543 : Revisit(merge);
264 1 : return Change(node, machine()->Float32Abs(), vtrue);
265 : }
266 : }
267 1286724 : } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
268 1637 : Float64BinopMatcher mcond(cond);
269 2137 : 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 4523852 : for (int i = 1; i < value_input_count; ++i) {
284 : Node* const input = inputs[i];
285 4462311 : if (input == node) {
286 : // Ignore redundant inputs.
287 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
288 : continue;
289 : }
290 4418858 : 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 7892120 : Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
298 : DCHECK_EQ(IrOpcode::kReturn, node->opcode());
299 3782322 : Node* effect = NodeProperties::GetEffectInput(node);
300 3715417 : 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 18842 : effect = NodeProperties::GetEffectInput(effect);
304 18843 : NodeProperties::ReplaceEffectInput(node, effect);
305 18843 : Reduction const reduction = ReduceReturn(node);
306 18843 : return reduction.Changed() ? reduction : Changed(node);
307 : }
308 : // TODO(ahaas): Extend the reduction below to multiple return values.
309 3696575 : if (ValueInputCountOfReturn(node->op()) != 1) {
310 : return NoChange();
311 : }
312 3690958 : Node* pop_count = NodeProperties::GetValueInput(node, 0);
313 7381921 : Node* value = NodeProperties::GetValueInput(node, 1);
314 3766406 : Node* control = NodeProperties::GetControlInput(node);
315 3812635 : if (value->opcode() == IrOpcode::kPhi &&
316 3766412 : 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 75412 : if (control->OwnedBy(node, value)) {
349 17195 : 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 17195 : NodeProperties::MergeControlToEnd(graph(), common(), ret);
357 : }
358 : // Mark the Merge {control} and Return {node} as {dead}.
359 74174 : Replace(control, dead());
360 : return Replace(dead());
361 132592 : } else if (effect->opcode() == IrOpcode::kEffectPhi &&
362 65681 : NodeProperties::GetControlInput(effect) == control) {
363 : Node::Inputs effect_inputs = effect->inputs();
364 : DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
365 214370 : 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 148698 : 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 191394 : Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
383 : DCHECK_EQ(IrOpcode::kSelect, node->opcode());
384 93783 : Node* const cond = node->InputAt(0);
385 : Node* const vtrue = node->InputAt(1);
386 2 : Node* const vfalse = node->InputAt(2);
387 95877 : if (vtrue == vfalse) return Replace(vtrue);
388 95515 : 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 93783 : 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 447 : Float64BinopMatcher mcond(cond);
410 672 : 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 446 : break;
418 : }
419 : default:
420 : break;
421 : }
422 : return NoChange();
423 : }
424 :
425 64230 : 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 63752 : if (mswitched.HasValue()) {
436 : bool matched = false;
437 :
438 478 : size_t const projection_count = node->op()->ControlOutputCount();
439 239 : Node** projections = zone_->NewArray<Node*>(projection_count);
440 : NodeProperties::CollectControlProjections(node, projections,
441 239 : projection_count);
442 305 : for (size_t i = 0; i < projection_count - 1; i++) {
443 296 : Node* if_value = projections[i];
444 : DCHECK_EQ(IrOpcode::kIfValue, if_value->opcode());
445 296 : const IfValueParameters& p = IfValueParametersOf(if_value->op());
446 296 : if (p.value() == mswitched.Value()) {
447 : matched = true;
448 239 : Replace(if_value, control);
449 : break;
450 : }
451 : }
452 239 : 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 178779 : } // namespace v8
|
