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 9282908 : Decision DecideCondition(Node* const cond) {
23 9282908 : switch (cond->opcode()) {
24 : case IrOpcode::kInt32Constant: {
25 : Int32Matcher mcond(cond);
26 421680 : return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 : }
28 : case IrOpcode::kHeapConstant: {
29 : HeapObjectMatcher mcond(cond);
30 71282 : return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 : }
32 : default:
33 : return Decision::kUnknown;
34 : }
35 : }
36 :
37 : } // namespace
38 :
39 2446735 : 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 4893478 : dead_(graph->NewNode(common->Dead())) {
47 : NodeProperties::SetType(dead_, Type::None());
48 2446743 : }
49 :
50 225930747 : Reduction CommonOperatorReducer::Reduce(Node* node) {
51 225930747 : switch (node->opcode()) {
52 : case IrOpcode::kBranch:
53 8540551 : return ReduceBranch(node);
54 : case IrOpcode::kDeoptimizeIf:
55 : case IrOpcode::kDeoptimizeUnless:
56 616020 : return ReduceDeoptimizeConditional(node);
57 : case IrOpcode::kMerge:
58 6313169 : return ReduceMerge(node);
59 : case IrOpcode::kEffectPhi:
60 6217824 : return ReduceEffectPhi(node);
61 : case IrOpcode::kPhi:
62 4710406 : return ReducePhi(node);
63 : case IrOpcode::kReturn:
64 3472694 : return ReduceReturn(node);
65 : case IrOpcode::kSelect:
66 72581 : return ReduceSelect(node);
67 : default:
68 : break;
69 : }
70 : return NoChange();
71 : }
72 :
73 :
74 9447307 : Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
75 : DCHECK_EQ(IrOpcode::kBranch, node->opcode());
76 8540533 : 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 17081066 : if (cond->opcode() == IrOpcode::kBooleanNot ||
83 58624 : (cond->opcode() == IrOpcode::kSelect &&
84 67347 : DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
85 : DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 66140 : for (Node* const use : node->uses()) {
87 26456 : switch (use->opcode()) {
88 : case IrOpcode::kIfTrue:
89 13228 : NodeProperties::ChangeOp(use, common()->IfFalse());
90 13228 : break;
91 : case IrOpcode::kIfFalse:
92 13228 : NodeProperties::ChangeOp(use, common()->IfTrue());
93 13228 : 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 13228 : node->ReplaceInput(0, cond->InputAt(0));
102 : // Negate the hint for {branch}.
103 : NodeProperties::ChangeOp(
104 26456 : node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 : return Changed(node);
106 : }
107 8527305 : Decision const decision = DecideCondition(cond);
108 8527296 : if (decision == Decision::kUnknown) return NoChange();
109 : Node* const control = node->InputAt(1);
110 2134655 : for (Node* const use : node->uses()) {
111 853862 : switch (use->opcode()) {
112 : case IrOpcode::kIfTrue:
113 1280793 : Replace(use, (decision == Decision::kTrue) ? control : dead());
114 : break;
115 : case IrOpcode::kIfFalse:
116 426931 : Replace(use, (decision == Decision::kFalse) ? control : dead());
117 : break;
118 : default:
119 0 : UNREACHABLE();
120 : }
121 : }
122 : return Replace(dead());
123 : }
124 :
125 642852 : Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
126 : DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
127 : node->opcode() == IrOpcode::kDeoptimizeUnless);
128 616018 : bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129 616018 : DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
130 1232034 : Node* condition = NodeProperties::GetValueInput(node, 0);
131 616020 : Node* frame_state = NodeProperties::GetValueInput(node, 1);
132 616018 : Node* effect = NodeProperties::GetEffectInput(node);
133 616016 : 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 616015 : 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 616015 : Decision const decision = DecideCondition(condition);
147 616015 : if (decision == Decision::kUnknown) return NoChange();
148 6463 : if (condition_is_true == (decision == Decision::kTrue)) {
149 6463 : ReplaceWithValue(node, dead(), effect, control);
150 : } else {
151 : control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
152 4636 : frame_state, effect, control);
153 : // TODO(bmeurer): This should be on the AdvancedReducer somehow.
154 4636 : NodeProperties::MergeControlToEnd(graph(), common(), control);
155 4636 : Revisit(graph()->end());
156 : }
157 : return Replace(dead());
158 : }
159 :
160 6315616 : 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 6312664 : if (node->InputCount() == 2) {
172 30454183 : for (Node* const use : node->uses()) {
173 15128947 : if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
174 : }
175 : Node* if_true = node->InputAt(0);
176 : Node* if_false = node->InputAt(1);
177 395559 : if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
178 310589 : if (if_true->opcode() == IrOpcode::kIfTrue &&
179 176817 : if_false->opcode() == IrOpcode::kIfFalse &&
180 202242 : if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
181 2972 : 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 2952 : branch->TrimInputCount(0);
188 2952 : NodeProperties::ChangeOp(branch, common()->Dead());
189 : return Replace(control);
190 : }
191 : }
192 : return NoChange();
193 : }
194 :
195 :
196 6217822 : Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
197 : DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
198 : Node::Inputs inputs = node->inputs();
199 6217822 : 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 6465826 : for (int i = 1; i < effect_input_count; ++i) {
207 : Node* const input = inputs[i];
208 6407040 : if (input == node) {
209 : // Ignore redundant inputs.
210 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
211 : continue;
212 : }
213 6406967 : if (input != effect) return NoChange();
214 : }
215 : // We might now be able to further reduce the {merge} node.
216 58786 : Revisit(merge);
217 : return Replace(effect);
218 : }
219 :
220 :
221 4710532 : Reduction CommonOperatorReducer::ReducePhi(Node* node) {
222 : DCHECK_EQ(IrOpcode::kPhi, node->opcode());
223 : Node::Inputs inputs = node->inputs();
224 4710530 : 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 4710530 : 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 8114090 : if (if_true->opcode() != IrOpcode::kIfTrue) {
236 : std::swap(if_true, if_false);
237 : std::swap(vtrue, vfalse);
238 : }
239 6325767 : if (if_true->opcode() == IrOpcode::kIfTrue &&
240 5143142 : if_false->opcode() == IrOpcode::kIfFalse &&
241 : if_true->InputAt(0) == if_false->InputAt(0)) {
242 1063718 : Node* const branch = if_true->InputAt(0);
243 : // Check that the branch is not dead already.
244 1063718 : if (branch->opcode() != IrOpcode::kBranch) return NoChange();
245 1063718 : Node* const cond = branch->InputAt(0);
246 1063718 : 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 125671 : Revisit(merge);
254 1 : return Change(node, machine()->Float32Abs(), vtrue);
255 : }
256 : }
257 1063115 : } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
258 3964 : Float64BinopMatcher mcond(cond);
259 5589 : 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 5396922 : for (int i = 1; i < value_input_count; ++i) {
274 : Node* const input = inputs[i];
275 5271253 : if (input == node) {
276 : // Ignore redundant inputs.
277 : DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
278 : continue;
279 : }
280 5197610 : 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 7315937 : Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
288 : DCHECK_EQ(IrOpcode::kReturn, node->opcode());
289 3562605 : Node* effect = NodeProperties::GetEffectInput(node);
290 3518411 : 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 45724 : effect = NodeProperties::GetEffectInput(effect);
294 45724 : NodeProperties::ReplaceEffectInput(node, effect);
295 45724 : Reduction const reduction = ReduceReturn(node);
296 45724 : return reduction.Changed() ? reduction : Changed(node);
297 : }
298 : // TODO(ahaas): Extend the reduction below to multiple return values.
299 3472687 : if (ValueInputCountOfReturn(node->op()) != 1) {
300 : return NoChange();
301 : }
302 3457969 : Node* pop_count = NodeProperties::GetValueInput(node, 0);
303 6916028 : Node* value = NodeProperties::GetValueInput(node, 1);
304 3510072 : Node* control = NodeProperties::GetControlInput(node);
305 3597869 : if (value->opcode() == IrOpcode::kPhi &&
306 3510086 : 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 52063 : if (control->OwnedBy(node, value)) {
339 15913 : 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 15913 : NodeProperties::MergeControlToEnd(graph(), common(), ret);
347 : }
348 : // Mark the Merge {control} and Return {node} as {dead}.
349 50678 : Replace(control, dead());
350 : return Replace(dead());
351 87031 : } else if (effect->opcode() == IrOpcode::kEffectPhi &&
352 42834 : NodeProperties::GetControlInput(effect) == control) {
353 : Node::Inputs effect_inputs = effect->inputs();
354 : DCHECK_EQ(control_inputs.count(), effect_inputs.count() - 1);
355 138642 : 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 95830 : 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 72583 : Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
373 : DCHECK_EQ(IrOpcode::kSelect, node->opcode());
374 72280 : Node* const cond = node->InputAt(0);
375 : Node* const vtrue = node->InputAt(1);
376 50 : Node* const vfalse = node->InputAt(2);
377 72581 : if (vtrue == vfalse) return Replace(vtrue);
378 72405 : 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 72280 : 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
|
