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
DecideCondition(Node * const cond)22 Decision DecideCondition(Node* const cond) {
23 switch (cond->opcode()) {
24 case IrOpcode::kInt32Constant: {
25 Int32Matcher mcond(cond);
26 return mcond.Value() ? Decision::kTrue : Decision::kFalse;
27 }
28 case IrOpcode::kHeapConstant: {
29 HeapObjectMatcher mcond(cond);
30 return mcond.Value()->BooleanValue() ? Decision::kTrue : Decision::kFalse;
31 }
32 default:
33 return Decision::kUnknown;
34 }
35 }
36
37 } // namespace
38
39
CommonOperatorReducer(Editor * editor,Graph * graph,CommonOperatorBuilder * common,MachineOperatorBuilder * machine)40 CommonOperatorReducer::CommonOperatorReducer(Editor* editor, Graph* graph,
41 CommonOperatorBuilder* common,
42 MachineOperatorBuilder* machine)
43 : AdvancedReducer(editor),
44 graph_(graph),
45 common_(common),
46 machine_(machine),
47 dead_(graph->NewNode(common->Dead())) {}
48
49
Reduce(Node * node)50 Reduction CommonOperatorReducer::Reduce(Node* node) {
51 switch (node->opcode()) {
52 case IrOpcode::kBranch:
53 return ReduceBranch(node);
54 case IrOpcode::kDeoptimizeIf:
55 case IrOpcode::kDeoptimizeUnless:
56 return ReduceDeoptimizeConditional(node);
57 case IrOpcode::kMerge:
58 return ReduceMerge(node);
59 case IrOpcode::kEffectPhi:
60 return ReduceEffectPhi(node);
61 case IrOpcode::kPhi:
62 return ReducePhi(node);
63 case IrOpcode::kReturn:
64 return ReduceReturn(node);
65 case IrOpcode::kSelect:
66 return ReduceSelect(node);
67 default:
68 break;
69 }
70 return NoChange();
71 }
72
73
ReduceBranch(Node * node)74 Reduction CommonOperatorReducer::ReduceBranch(Node* node) {
75 DCHECK_EQ(IrOpcode::kBranch, node->opcode());
76 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 if (cond->opcode() == IrOpcode::kBooleanNot ||
83 (cond->opcode() == IrOpcode::kSelect &&
84 DecideCondition(cond->InputAt(1)) == Decision::kFalse &&
85 DecideCondition(cond->InputAt(2)) == Decision::kTrue)) {
86 for (Node* const use : node->uses()) {
87 switch (use->opcode()) {
88 case IrOpcode::kIfTrue:
89 NodeProperties::ChangeOp(use, common()->IfFalse());
90 break;
91 case IrOpcode::kIfFalse:
92 NodeProperties::ChangeOp(use, common()->IfTrue());
93 break;
94 default:
95 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 node->ReplaceInput(0, cond->InputAt(0));
102 // Negate the hint for {branch}.
103 NodeProperties::ChangeOp(
104 node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
105 return Changed(node);
106 }
107 Decision const decision = DecideCondition(cond);
108 if (decision == Decision::kUnknown) return NoChange();
109 Node* const control = node->InputAt(1);
110 for (Node* const use : node->uses()) {
111 switch (use->opcode()) {
112 case IrOpcode::kIfTrue:
113 Replace(use, (decision == Decision::kTrue) ? control : dead());
114 break;
115 case IrOpcode::kIfFalse:
116 Replace(use, (decision == Decision::kFalse) ? control : dead());
117 break;
118 default:
119 UNREACHABLE();
120 }
121 }
122 return Replace(dead());
123 }
124
ReduceDeoptimizeConditional(Node * node)125 Reduction CommonOperatorReducer::ReduceDeoptimizeConditional(Node* node) {
126 DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
127 node->opcode() == IrOpcode::kDeoptimizeUnless);
128 bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
129 DeoptimizeReason reason = DeoptimizeReasonOf(node->op());
130 Node* condition = NodeProperties::GetValueInput(node, 0);
131 Node* frame_state = NodeProperties::GetValueInput(node, 1);
132 Node* effect = NodeProperties::GetEffectInput(node);
133 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 if (condition->opcode() == IrOpcode::kBooleanNot) {
139 NodeProperties::ReplaceValueInput(node, condition->InputAt(0), 0);
140 NodeProperties::ChangeOp(node, condition_is_true
141 ? common()->DeoptimizeIf(reason)
142 : common()->DeoptimizeUnless(reason));
143 return Changed(node);
144 }
145 Decision const decision = DecideCondition(condition);
146 if (decision == Decision::kUnknown) return NoChange();
147 if (condition_is_true == (decision == Decision::kTrue)) {
148 ReplaceWithValue(node, dead(), effect, control);
149 } else {
150 control =
151 graph()->NewNode(common()->Deoptimize(DeoptimizeKind::kEager, reason),
152 frame_state, effect, control);
153 // TODO(bmeurer): This should be on the AdvancedReducer somehow.
154 NodeProperties::MergeControlToEnd(graph(), common(), control);
155 Revisit(graph()->end());
156 }
157 return Replace(dead());
158 }
159
ReduceMerge(Node * node)160 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 if (node->InputCount() == 2) {
172 for (Node* const use : node->uses()) {
173 if (IrOpcode::IsPhiOpcode(use->opcode())) return NoChange();
174 }
175 Node* if_true = node->InputAt(0);
176 Node* if_false = node->InputAt(1);
177 if (if_true->opcode() != IrOpcode::kIfTrue) std::swap(if_true, if_false);
178 if (if_true->opcode() == IrOpcode::kIfTrue &&
179 if_false->opcode() == IrOpcode::kIfFalse &&
180 if_true->InputAt(0) == if_false->InputAt(0) && if_true->OwnedBy(node) &&
181 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 branch->TrimInputCount(0);
188 NodeProperties::ChangeOp(branch, common()->Dead());
189 return Replace(control);
190 }
191 }
192 return NoChange();
193 }
194
195
ReduceEffectPhi(Node * node)196 Reduction CommonOperatorReducer::ReduceEffectPhi(Node* node) {
197 DCHECK_EQ(IrOpcode::kEffectPhi, node->opcode());
198 int const input_count = node->InputCount() - 1;
199 DCHECK_LE(1, input_count);
200 Node* const merge = node->InputAt(input_count);
201 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
202 DCHECK_EQ(input_count, merge->InputCount());
203 Node* const effect = node->InputAt(0);
204 DCHECK_NE(node, effect);
205 for (int i = 1; i < input_count; ++i) {
206 Node* const input = node->InputAt(i);
207 if (input == node) {
208 // Ignore redundant inputs.
209 DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
210 continue;
211 }
212 if (input != effect) return NoChange();
213 }
214 // We might now be able to further reduce the {merge} node.
215 Revisit(merge);
216 return Replace(effect);
217 }
218
219
ReducePhi(Node * node)220 Reduction CommonOperatorReducer::ReducePhi(Node* node) {
221 DCHECK_EQ(IrOpcode::kPhi, node->opcode());
222 int const input_count = node->InputCount() - 1;
223 DCHECK_LE(1, input_count);
224 Node* const merge = node->InputAt(input_count);
225 DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
226 DCHECK_EQ(input_count, merge->InputCount());
227 if (input_count == 2) {
228 Node* vtrue = node->InputAt(0);
229 Node* vfalse = node->InputAt(1);
230 Node* if_true = merge->InputAt(0);
231 Node* if_false = merge->InputAt(1);
232 if (if_true->opcode() != IrOpcode::kIfTrue) {
233 std::swap(if_true, if_false);
234 std::swap(vtrue, vfalse);
235 }
236 if (if_true->opcode() == IrOpcode::kIfTrue &&
237 if_false->opcode() == IrOpcode::kIfFalse &&
238 if_true->InputAt(0) == if_false->InputAt(0)) {
239 Node* const branch = if_true->InputAt(0);
240 // Check that the branch is not dead already.
241 if (branch->opcode() != IrOpcode::kBranch) return NoChange();
242 Node* const cond = branch->InputAt(0);
243 if (cond->opcode() == IrOpcode::kFloat32LessThan) {
244 Float32BinopMatcher mcond(cond);
245 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
246 vfalse->opcode() == IrOpcode::kFloat32Sub) {
247 Float32BinopMatcher mvfalse(vfalse);
248 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
249 // We might now be able to further reduce the {merge} node.
250 Revisit(merge);
251 return Change(node, machine()->Float32Abs(), vtrue);
252 }
253 }
254 } else if (cond->opcode() == IrOpcode::kFloat64LessThan) {
255 Float64BinopMatcher mcond(cond);
256 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
257 vfalse->opcode() == IrOpcode::kFloat64Sub) {
258 Float64BinopMatcher mvfalse(vfalse);
259 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
260 // We might now be able to further reduce the {merge} node.
261 Revisit(merge);
262 return Change(node, machine()->Float64Abs(), vtrue);
263 }
264 }
265 }
266 }
267 }
268 Node* const value = node->InputAt(0);
269 DCHECK_NE(node, value);
270 for (int i = 1; i < input_count; ++i) {
271 Node* const input = node->InputAt(i);
272 if (input == node) {
273 // Ignore redundant inputs.
274 DCHECK_EQ(IrOpcode::kLoop, merge->opcode());
275 continue;
276 }
277 if (input != value) return NoChange();
278 }
279 // We might now be able to further reduce the {merge} node.
280 Revisit(merge);
281 return Replace(value);
282 }
283
284
ReduceReturn(Node * node)285 Reduction CommonOperatorReducer::ReduceReturn(Node* node) {
286 DCHECK_EQ(IrOpcode::kReturn, node->opcode());
287 Node* const value = node->InputAt(1);
288 Node* effect = NodeProperties::GetEffectInput(node);
289 Node* const control = NodeProperties::GetControlInput(node);
290 bool changed = false;
291 if (effect->opcode() == IrOpcode::kCheckpoint) {
292 // Any {Return} node can never be used to insert a deoptimization point,
293 // hence checkpoints can be cut out of the effect chain flowing into it.
294 effect = NodeProperties::GetEffectInput(effect);
295 NodeProperties::ReplaceEffectInput(node, effect);
296 changed = true;
297 }
298 if (value->opcode() == IrOpcode::kPhi &&
299 NodeProperties::GetControlInput(value) == control &&
300 effect->opcode() == IrOpcode::kEffectPhi &&
301 NodeProperties::GetControlInput(effect) == control &&
302 control->opcode() == IrOpcode::kMerge) {
303 int const control_input_count = control->InputCount();
304 DCHECK_NE(0, control_input_count);
305 DCHECK_EQ(control_input_count, value->InputCount() - 1);
306 DCHECK_EQ(control_input_count, effect->InputCount() - 1);
307 DCHECK_EQ(IrOpcode::kEnd, graph()->end()->opcode());
308 DCHECK_NE(0, graph()->end()->InputCount());
309 for (int i = 0; i < control_input_count; ++i) {
310 // Create a new {Return} and connect it to {end}. We don't need to mark
311 // {end} as revisit, because we mark {node} as {Dead} below, which was
312 // previously connected to {end}, so we know for sure that at some point
313 // the reducer logic will visit {end} again.
314 Node* ret = graph()->NewNode(common()->Return(), node->InputAt(0),
315 value->InputAt(i), effect->InputAt(i),
316 control->InputAt(i));
317 NodeProperties::MergeControlToEnd(graph(), common(), ret);
318 }
319 // Mark the merge {control} and return {node} as {dead}.
320 Replace(control, dead());
321 return Replace(dead());
322 }
323 return changed ? Changed(node) : NoChange();
324 }
325
326
ReduceSelect(Node * node)327 Reduction CommonOperatorReducer::ReduceSelect(Node* node) {
328 DCHECK_EQ(IrOpcode::kSelect, node->opcode());
329 Node* const cond = node->InputAt(0);
330 Node* const vtrue = node->InputAt(1);
331 Node* const vfalse = node->InputAt(2);
332 if (vtrue == vfalse) return Replace(vtrue);
333 switch (DecideCondition(cond)) {
334 case Decision::kTrue:
335 return Replace(vtrue);
336 case Decision::kFalse:
337 return Replace(vfalse);
338 case Decision::kUnknown:
339 break;
340 }
341 switch (cond->opcode()) {
342 case IrOpcode::kFloat32LessThan: {
343 Float32BinopMatcher mcond(cond);
344 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
345 vfalse->opcode() == IrOpcode::kFloat32Sub) {
346 Float32BinopMatcher mvfalse(vfalse);
347 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
348 return Change(node, machine()->Float32Abs(), vtrue);
349 }
350 }
351 break;
352 }
353 case IrOpcode::kFloat64LessThan: {
354 Float64BinopMatcher mcond(cond);
355 if (mcond.left().Is(0.0) && mcond.right().Equals(vtrue) &&
356 vfalse->opcode() == IrOpcode::kFloat64Sub) {
357 Float64BinopMatcher mvfalse(vfalse);
358 if (mvfalse.left().IsZero() && mvfalse.right().Equals(vtrue)) {
359 return Change(node, machine()->Float64Abs(), vtrue);
360 }
361 }
362 break;
363 }
364 default:
365 break;
366 }
367 return NoChange();
368 }
369
370
Change(Node * node,Operator const * op,Node * a)371 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op,
372 Node* a) {
373 node->ReplaceInput(0, a);
374 node->TrimInputCount(1);
375 NodeProperties::ChangeOp(node, op);
376 return Changed(node);
377 }
378
379
Change(Node * node,Operator const * op,Node * a,Node * b)380 Reduction CommonOperatorReducer::Change(Node* node, Operator const* op, Node* a,
381 Node* b) {
382 node->ReplaceInput(0, a);
383 node->ReplaceInput(1, b);
384 node->TrimInputCount(2);
385 NodeProperties::ChangeOp(node, op);
386 return Changed(node);
387 }
388
389 } // namespace compiler
390 } // namespace internal
391 } // namespace v8
392