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 9284694 : Decision DecideCondition(Node* const cond) {
23 9284694 : switch (cond->opcode()) {
24 : case IrOpcode::kInt32Constant: {
25 : Int32Matcher mcond(cond);
26 420874 : return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 : }
28 : case IrOpcode::kHeapConstant: {
29 : HeapObjectMatcher mcond(cond);
30 71556 : return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 : }
32 : default:
33 : return Decision::kUnknown;
34 : }
35 : }
36 :
37 : } // namespace
38 :
39 2442402 : 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 4884848 : dead_(graph->NewNode(common->Dead())) {
47 : NodeProperties::SetType(dead_, Type::None());
48 2442446 : }
49 :
50 225842432 : Reduction CommonOperatorReducer::Reduce(Node* node) {
51 225842432 : switch (node->opcode()) {
52 : case IrOpcode::kBranch:
53 8543891 : return ReduceBranch(node);
54 : case IrOpcode::kDeoptimizeIf:
55 : case IrOpcode::kDeoptimizeUnless:
56 614298 : return ReduceDeoptimizeConditional(node);
57 : case IrOpcode::kMerge:
58 6314692 : return ReduceMerge(node);
59 : case IrOpcode::kEffectPhi:
60 6219367 : return ReduceEffectPhi(node);
61 : case IrOpcode::kPhi:
62 4720484 : return ReducePhi(node);
63 : case IrOpcode::kReturn:
64 3470834 : return ReduceReturn(node);
65 : case IrOpcode::kSelect:
66 72661 : return ReduceSelect(node);
67 : default:
68 : break;
69 : }
70 : return NoChange();
71 : }
72 :
73 :
74 9449474 : Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
75 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
76 8543870 : 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 17087740 : if (cond->opcode() == IrOpcode::kBooleanNot ||
83 58759 : (cond->opcode() == IrOpcode::kSelect &&
84 67511 : DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
85 : DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 66260 : for (Node* const use : node->uses()) {
87 26504 : switch (use->opcode()) {
88 : case IrOpcode::kIfTrue:
89 13252 : NodeProperties::ChangeOp(use, common()->IfFalse());
90 13252 : break;
91 : case IrOpcode::kIfFalse:
92 13252 : NodeProperties::ChangeOp(use, common()->IfTrue());
93 13252 : break;
94 : default:
95 0 : 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 13252 : node->ReplaceInput(0, cond->InputAt(0));
102 : // Negate the hint for {branch}.
103 : NodeProperties::ChangeOp(
104 26504 : node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 : return Changed(node);
106 : }
107 8530618 : Decision const decision = DecideCondition(cond);
108 8530591 : if (decision == Decision::kUnknown) return NoChange();
109 : Node* const control = node->InputAt(1);
110 2131490 : for (Node* const use : node->uses()) {
111 852596 : switch (use->opcode()) {
112 : case IrOpcode::kIfTrue:
113 1278894 : Replace(use, (decision == Decision::kTrue) ? control : dead());
114 : break;
115 : case IrOpcode::kIfFalse:
116 426298 : Replace(use, (decision == Decision::kFalse) ? control : dead());
117 : break;
118 : default:
119 0 : UNREACHABLE();
120 : }
121 : }
122 : return Replace(dead());
123 : }
124 :
125 641141 : Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
126 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
127 : node->opcode() == IrOpcode::kDeoptimizeUnless);
128 614298 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129 614298 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
130 1228591 : Node* condition = NodeProperties::GetValueInput(node, 0);
131 614297 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
132 614295 : Node* effect = NodeProperties::GetEffectInput(node);
133 614294 : 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 614292 : if (condition->opcode() == IrOpcode::kBooleanNot) {
139 0 : NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
140 : NodeProperties::ChangeOp(
141 : node, condition_is_true
142 : ? common()->DeoptimizeIf(p.kind(), p.reason())
143 0 : : common()->DeoptimizeUnless(p.kind(), p.reason()));
144 : return Changed(node);
145 : }
146 614292 : Decision const decision = DecideCondition(condition);
147 614293 : if (decision == Decision::kUnknown) return NoChange();
148 6475 : if (condition_is_true == (decision == Decision::kTrue)) {
149 6475 : ReplaceWithValue(node, dead(), effect, control);
150 : } else {
151 : control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
152 4631 : frame_state, effect, control);
153 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
154 4631 : NodeProperties::MergeControlToEnd(graph(), common(), control);
155 4631 : Revisit(graph()->end());
156 : }
157 : return Replace(dead());
158 : }
159 :
160 6316982 : 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 6314024 : if (node->InputCount() == 2) {
172 30476316 : for (Node* const use : node->uses()) {
173 15139664 : if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
174 : }
175 : Node* if_true = node->InputAt(0);
176 : Node* if_false = node->InputAt(1);
177 396963 : if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
178 311694 : if (if_true->opcode() == IrOpcode::kIfTrue &&
179 177517 : if_false->opcode() == IrOpcode::kIfFalse &&
180 202953 : if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
181 2978 : 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 2958 : branch->TrimInputCount(0);
188 2958 : NodeProperties::ChangeOp(branch, common()->Dead());
189 : return Replace(control);
190 : }
191 : }
192 : return NoChange();
193 : }
194 :
195 :
196 6219346 : Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
197 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
198 : Node::Inputs inputs = node->inputs();
199 6219346 : 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 6466951 : for (int i = 1; i < effect_input_count; ++i) {
207 : Node* const input = inputs[i];
208 6408088 : if (input == node) {
209 : // Ignore redundant inputs.
210 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
211 : continue;
212 : }
213 6408011 : if (input != effect) return NoChange();
214 : }
215 : // We might now be able to further reduce the {merge} node.
216 58863 : Revisit(merge);
217 : return Replace(effect);
218 : }
219 :
220 :
221 4720626 : Reduction CommonOperatorReducer::ReducePhi(Node* node) {
222 : DCHECK_EQ(IrOpcode::kPhi, node->opcode());
223 : Node::Inputs inputs = node->inputs();
224 4720624 : 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 4720624 : 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 8127498 : if (if_true->opcode() != IrOpcode::kIfTrue) {
236 : std::swap(if_true, if_false);
237 : std::swap(vtrue, vfalse);
238 : }
239 6339106 : if (if_true->opcode() == IrOpcode::kIfTrue &&
240 5150184 : if_false->opcode() == IrOpcode::kIfFalse &&
241 : if_true->InputAt(0) == if_false->InputAt(0)) {
242 1064197 : Node* const branch = if_true->InputAt(0);
243 : // Check that the branch is not dead already.
244 1064197 : if (branch->opcode() != IrOpcode::kBranch) return NoChange();
245 1064197 : Node* const cond = branch->InputAt(0);
246 1064197 : if (cond->opcode() == IrOpcode::kFloat32LessThan) {
247 603 : Float32BinopMatcher mcond(cond);
248 612 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
249 61 : vfalse->opcode() == IrOpcode::kFloat32Sub) {
250 1 : Float32BinopMatcher mvfalse(vfalse);
251 2 : if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
252 : // We might now be able to further reduce the {merge} node.
253 126069 : Revisit(merge);
254 1 : return Change(node, machine()->Float32Abs(), vtrue);
255 : }
256 : }
257 1063594 : } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
258 3958 : Float64BinopMatcher mcond(cond);
259 5583 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
260 : vfalse->opcode() == IrOpcode::kFloat64Sub) {
261 1 : Float64BinopMatcher mvfalse(vfalse);
262 2 : if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
263 : // We might now be able to further reduce the {merge} node.
264 : Revisit(merge);
265 1 : return Change(node, machine()->Float64Abs(), vtrue);
266 : }
267 : }
268 : }
269 : }
270 : }
271 : Node* const value = inputs[0];
272 : DCHECK_NE(node, value);
273 5408702 : for (int i = 1; i < value_input_count; ++i) {
274 : Node* const input = inputs[i];
275 5282635 : if (input == node) {
276 : // Ignore redundant inputs.
277 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
278 : continue;
279 : }
280 5208555 : 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 :
287 7312849 : Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
288 : DCHECK_EQ(IrOpcode::kReturn, node->opcode());
289 3561235 : Node* effect = NodeProperties::GetEffectInput(node);
290 3517040 : 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 46200 : effect = NodeProperties::GetEffectInput(effect);
294 46200 : NodeProperties::ReplaceEffectInput(node, effect);
295 46200 : Reduction const reduction = ReduceReturn(node);
296 46200 : return reduction.Changed() ? reduction : Changed(node);
297 : }
298 : // TODO(ahaas): Extend the reduction below to multiple return values.
299 3470840 : if (ValueInputCountOfReturn(node->op()) != 1) {
300 : return NoChange();
301 : }
302 3456153 : Node* pop_count = NodeProperties::GetValueInput(node, 0);
303 6912333 : Node* value = NodeProperties::GetValueInput(node, 1);
304 3508283 : Node* control = NodeProperties::GetControlInput(node);
305 3598263 : if (value->opcode() == IrOpcode::kPhi &&
306 3508289 : 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 52099 : if (control->OwnedBy(node, value)) {
339 15893 : 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 15893 : NodeProperties::MergeControlToEnd(graph(), common(), ret);
347 : }
348 : // Mark the Merge {control} and Return {node} as {dead}.
349 50714 : Replace(control, dead());
350 : return Replace(dead());
351 87125 : } else if (effect->opcode() == IrOpcode::kEffectPhi &&
352 42881 : NodeProperties::GetControlInput(effect) == control) {
353 : Node::Inputs effect_inputs = effect->inputs();
354 : DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
355 138761 : 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 95902 : 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 :
372 72663 : Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
373 : DCHECK_EQ(IrOpcode::kSelect, node->opcode());
374 72415 : Node* const cond = node->InputAt(0);
375 : Node* const vtrue = node->InputAt(1);
376 50 : Node* const vfalse = node->InputAt(2);
377 72661 : if (vtrue == vfalse) return Replace(vtrue);
378 72485 : 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 72415 : switch (cond->opcode()) {
387 : case IrOpcode::kFloat32LessThan: {
388 1 : Float32BinopMatcher mcond(cond);
389 3 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
390 : vfalse->opcode() == IrOpcode::kFloat32Sub) {
391 1 : Float32BinopMatcher mvfalse(vfalse);
392 2 : if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
393 1 : return Change(node, machine()->Float32Abs(), vtrue);
394 : }
395 : }
396 0 : break;
397 : }
398 : case IrOpcode::kFloat64LessThan: {
399 2305 : Float64BinopMatcher mcond(cond);
400 3441 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
401 : vfalse->opcode() == IrOpcode::kFloat64Sub) {
402 1 : Float64BinopMatcher mvfalse(vfalse);
403 2 : if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
404 1 : return Change(node, machine()->Float64Abs(), vtrue);
405 : }
406 : }
407 2304 : break;
408 : }
409 : default:
410 : break;
411 : }
412 : return NoChange();
413 : }
414 :
415 :
416 4 : Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
417 : Node* a) {
418 4 : node->ReplaceInput(0, a);
419 4 : node->TrimInputCount(1);
420 4 : NodeProperties::ChangeOp(node, op);
421 4 : return Changed(node);
422 : }
423 :
424 :
425 0 : Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
426 : Node* b) {
427 0 : node->ReplaceInput(0, a);
428 0 : node->ReplaceInput(1, b);
429 0 : node->TrimInputCount(2);
430 0 : NodeProperties::ChangeOp(node, op);
431 0 : return Changed(node);
432 : }
433 :
434 : } // namespace compiler
435 : } // namespace internal
436 : } // namespace v8
|
