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 8010977 : Decision DecideCondition(Node* const cond) {
23 8010977 : switch (cond->opcode()) {
24 : case IrOpcode::kInt32Constant: {
25 : Int32Matcher mcond(cond);
26 315795 : return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 : }
28 : case IrOpcode::kHeapConstant: {
29 : HeapObjectMatcher mcond(cond);
30 82356 : return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 : }
32 : default:
33 : return Decision::kUnknown;
34 : }
35 : }
36 :
37 : } // namespace
38 :
39 2672418 : 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 5344845 : dead_(graph->NewNode(common->Dead())) {
47 : NodeProperties::SetType(dead_, Type::None());
48 2672427 : }
49 :
50 224680510 : Reduction CommonOperatorReducer::Reduce(Node* node) {
51 224680510 : switch (node->opcode()) {
52 : case IrOpcode::kBranch:
53 7212266 : return ReduceBranch(node);
54 : case IrOpcode::kDeoptimizeIf:
55 : case IrOpcode::kDeoptimizeUnless:
56 689255 : return ReduceDeoptimizeConditional(node);
57 : case IrOpcode::kMerge:
58 5069555 : return ReduceMerge(node);
59 : case IrOpcode::kEffectPhi:
60 4980930 : return ReduceEffectPhi(node);
61 : case IrOpcode::kPhi:
62 3357061 : return ReducePhi(node);
63 : case IrOpcode::kReturn:
64 3496960 : return ReduceReturn(node);
65 : case IrOpcode::kSelect:
66 83855 : return ReduceSelect(node);
67 : default:
68 : break;
69 : }
70 : return NoChange();
71 : }
72 :
73 :
74 7983094 : Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
75 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
76 7212288 : 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 14424576 : if (cond->opcode() == IrOpcode::kBooleanNot ||
83 34353 : (cond->opcode() == IrOpcode::kSelect &&
84 39690 : DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
85 : DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 68585 : for (Node* const use : node->uses()) {
87 27434 : switch (use->opcode()) {
88 : case IrOpcode::kIfTrue:
89 13717 : NodeProperties::ChangeOp(use, common()->IfFalse());
90 13717 : break;
91 : case IrOpcode::kIfFalse:
92 13717 : NodeProperties::ChangeOp(use, common()->IfTrue());
93 13717 : 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 13717 : node->ReplaceInput(0, cond->InputAt(0));
102 : // Negate the hint for {branch}.
103 : NodeProperties::ChangeOp(
104 27434 : node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 : return Changed(node);
106 : }
107 7198571 : Decision const decision = DecideCondition(cond);
108 7198575 : if (decision == Decision::kUnknown) return NoChange();
109 : Node* const control = node->InputAt(1);
110 1789845 : for (Node* const use : node->uses()) {
111 715938 : switch (use->opcode()) {
112 : case IrOpcode::kIfTrue:
113 1073907 : Replace(use, (decision == Decision::kTrue) ? control : dead());
114 : break;
115 : case IrOpcode::kIfFalse:
116 357969 : Replace(use, (decision == Decision::kFalse) ? control : dead());
117 : break;
118 : default:
119 0 : UNREACHABLE();
120 : }
121 : }
122 : return Replace(dead());
123 : }
124 :
125 712465 : Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
126 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
127 : node->opcode() == IrOpcode::kDeoptimizeUnless);
128 689249 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129 689249 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
130 1378500 : Node* condition = NodeProperties::GetValueInput(node, 0);
131 689251 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
132 689251 : Node* effect = NodeProperties::GetEffectInput(node);
133 689248 : 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 689247 : 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 689247 : Decision const decision = DecideCondition(condition);
147 689243 : if (decision == Decision::kUnknown) return NoChange();
148 5068 : if (condition_is_true == (decision == Decision::kTrue)) {
149 5068 : ReplaceWithValue(node, dead(), effect, control);
150 : } else {
151 : control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
152 4360 : frame_state, effect, control);
153 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
154 4360 : NodeProperties::MergeControlToEnd(graph(), common(), control);
155 4360 : Revisit(graph()->end());
156 : }
157 : return Replace(dead());
158 : }
159 :
160 5074345 : 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 5069152 : if (node->InputCount() == 2) {
172 25354198 : for (Node* const use : node->uses()) {
173 12607714 : if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
174 : }
175 : Node* if_true = node->InputAt(0);
176 : Node* if_false = node->InputAt(1);
177 282770 : if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
178 225201 : if (if_true->opcode() == IrOpcode::kIfTrue &&
179 146287 : if_false->opcode() == IrOpcode::kIfFalse &&
180 149224 : if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
181 5224 : 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 5193 : branch->TrimInputCount(0);
188 5193 : NodeProperties::ChangeOp(branch, common()->Dead());
189 : return Replace(control);
190 : }
191 : }
192 : return NoChange();
193 : }
194 :
195 :
196 4980921 : Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
197 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
198 : Node::Inputs inputs = node->inputs();
199 4980921 : 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 5258453 : for (int i = 1; i < effect_input_count; ++i) {
207 : Node* const input = inputs[i];
208 5124072 : if (input == node) {
209 : // Ignore redundant inputs.
210 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
211 : continue;
212 : }
213 5124080 : if (input != effect) return NoChange();
214 : }
215 : // We might now be able to further reduce the {merge} node.
216 134381 : Revisit(merge);
217 : return Replace(effect);
218 : }
219 :
220 :
221 3357375 : Reduction CommonOperatorReducer::ReducePhi(Node* node) {
222 : DCHECK_EQ(IrOpcode::kPhi, node->opcode());
223 : Node::Inputs inputs = node->inputs();
224 3357373 : 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 3357373 : 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 6014124 : if (if_true->opcode() != IrOpcode::kIfTrue) {
236 : std::swap(if_true, if_false);
237 : std::swap(vtrue, vfalse);
238 : }
239 4781560 : if (if_true->opcode() == IrOpcode::kIfTrue &&
240 4132395 : if_false->opcode() == IrOpcode::kIfFalse &&
241 : if_true->InputAt(0) == if_false->InputAt(0)) {
242 1103596 : Node* const branch = if_true->InputAt(0);
243 : // Check that the branch is not dead already.
244 1103596 : if (branch->opcode() != IrOpcode::kBranch) return NoChange();
245 1103596 : Node* const cond = branch->InputAt(0);
246 1103596 : if (cond->opcode() == IrOpcode::kFloat32LessThan) {
247 421 : Float32BinopMatcher mcond(cond);
248 444 : if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
249 219 : 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 74754 : Revisit(merge);
254 1 : return Change(node, machine()->Float32Abs(), vtrue);
255 : }
256 : }
257 1103175 : } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
258 35870 : Float64BinopMatcher mcond(cond);
259 55307 : 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 3914422 : for (int i = 1; i < value_input_count; ++i) {
274 : Node* const input = inputs[i];
275 3839670 : if (input == node) {
276 : // Ignore redundant inputs.
277 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
278 : continue;
279 : }
280 3794303 : 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 7317743 : Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
288 : DCHECK_EQ(IrOpcode::kReturn, node->opcode());
289 3568257 : Node* effect = NodeProperties::GetEffectInput(node);
290 3530865 : 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 33902 : effect = NodeProperties::GetEffectInput(effect);
294 33902 : NodeProperties::ReplaceEffectInput(node, effect);
295 33902 : Reduction const reduction = ReduceReturn(node);
296 33902 : return reduction.Changed() ? reduction : Changed(node);
297 : }
298 : // TODO(ahaas): Extend the reduction below to multiple return values.
299 3496963 : if (ValueInputCountOfReturn(node->op()) != 1) {
300 : return NoChange();
301 : }
302 3489206 : Node* pop_count = NodeProperties::GetValueInput(node, 0);
303 6978414 : Node* value = NodeProperties::GetValueInput(node, 1);
304 3537303 : Node* control = NodeProperties::GetControlInput(node);
305 3588907 : if (value->opcode() == IrOpcode::kPhi &&
306 3537301 : 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 48093 : if (control->OwnedBy(node, value)) {
339 21502 : 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 21502 : NodeProperties::MergeControlToEnd(graph(), common(), ret);
347 : }
348 : // Mark the Merge {control} and Return {node} as {dead}.
349 47112 : Replace(control, dead());
350 : return Replace(dead());
351 73813 : } else if (effect->opcode() == IrOpcode::kEffectPhi &&
352 36416 : NodeProperties::GetControlInput(effect) == control) {
353 : Node::Inputs effect_inputs = effect->inputs();
354 : DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
355 112762 : 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 76346 : 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 83857 : Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
373 : DCHECK_EQ(IrOpcode::kSelect, node->opcode());
374 82903 : Node* const cond = node->InputAt(0);
375 : Node* const vtrue = node->InputAt(1);
376 314 : Node* const vfalse = node->InputAt(2);
377 83855 : if (vtrue == vfalse) return Replace(vtrue);
378 83661 : 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 82903 : 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 2763 : Float64BinopMatcher mcond(cond);
400 4509 : 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 2762 : 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
|
