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/machine-operator-reducer.h"
6
7 #include "src/base/bits.h"
8 #include "src/base/division-by-constant.h"
9 #include "src/base/ieee754.h"
10 #include "src/codegen.h"
11 #include "src/compiler/diamond.h"
12 #include "src/compiler/graph.h"
13 #include "src/compiler/js-graph.h"
14 #include "src/compiler/node-matchers.h"
15 #include "src/objects-inl.h"
16
17 namespace v8 {
18 namespace internal {
19 namespace compiler {
20
MachineOperatorReducer(JSGraph * jsgraph,bool allow_signalling_nan)21 MachineOperatorReducer::MachineOperatorReducer(JSGraph* jsgraph,
22 bool allow_signalling_nan)
23 : jsgraph_(jsgraph), allow_signalling_nan_(allow_signalling_nan) {}
24
~MachineOperatorReducer()25 MachineOperatorReducer::~MachineOperatorReducer() {}
26
27
Float32Constant(volatile float value)28 Node* MachineOperatorReducer::Float32Constant(volatile float value) {
29 return graph()->NewNode(common()->Float32Constant(value));
30 }
31
32
Float64Constant(volatile double value)33 Node* MachineOperatorReducer::Float64Constant(volatile double value) {
34 return jsgraph()->Float64Constant(value);
35 }
36
37
Int32Constant(int32_t value)38 Node* MachineOperatorReducer::Int32Constant(int32_t value) {
39 return jsgraph()->Int32Constant(value);
40 }
41
42
Int64Constant(int64_t value)43 Node* MachineOperatorReducer::Int64Constant(int64_t value) {
44 return graph()->NewNode(common()->Int64Constant(value));
45 }
46
Float64Mul(Node * lhs,Node * rhs)47 Node* MachineOperatorReducer::Float64Mul(Node* lhs, Node* rhs) {
48 return graph()->NewNode(machine()->Float64Mul(), lhs, rhs);
49 }
50
Float64PowHalf(Node * value)51 Node* MachineOperatorReducer::Float64PowHalf(Node* value) {
52 value =
53 graph()->NewNode(machine()->Float64Add(), Float64Constant(0.0), value);
54 Diamond d(graph(), common(),
55 graph()->NewNode(machine()->Float64LessThanOrEqual(), value,
56 Float64Constant(-V8_INFINITY)),
57 BranchHint::kFalse);
58 return d.Phi(MachineRepresentation::kFloat64, Float64Constant(V8_INFINITY),
59 graph()->NewNode(machine()->Float64Sqrt(), value));
60 }
61
Word32And(Node * lhs,Node * rhs)62 Node* MachineOperatorReducer::Word32And(Node* lhs, Node* rhs) {
63 Node* const node = graph()->NewNode(machine()->Word32And(), lhs, rhs);
64 Reduction const reduction = ReduceWord32And(node);
65 return reduction.Changed() ? reduction.replacement() : node;
66 }
67
68
Word32Sar(Node * lhs,uint32_t rhs)69 Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) {
70 if (rhs == 0) return lhs;
71 return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs));
72 }
73
74
Word32Shr(Node * lhs,uint32_t rhs)75 Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) {
76 if (rhs == 0) return lhs;
77 return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs));
78 }
79
80
Word32Equal(Node * lhs,Node * rhs)81 Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) {
82 return graph()->NewNode(machine()->Word32Equal(), lhs, rhs);
83 }
84
85
Int32Add(Node * lhs,Node * rhs)86 Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) {
87 Node* const node = graph()->NewNode(machine()->Int32Add(), lhs, rhs);
88 Reduction const reduction = ReduceInt32Add(node);
89 return reduction.Changed() ? reduction.replacement() : node;
90 }
91
92
Int32Sub(Node * lhs,Node * rhs)93 Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) {
94 Node* const node = graph()->NewNode(machine()->Int32Sub(), lhs, rhs);
95 Reduction const reduction = ReduceInt32Sub(node);
96 return reduction.Changed() ? reduction.replacement() : node;
97 }
98
99
Int32Mul(Node * lhs,Node * rhs)100 Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) {
101 return graph()->NewNode(machine()->Int32Mul(), lhs, rhs);
102 }
103
104
Int32Div(Node * dividend,int32_t divisor)105 Node* MachineOperatorReducer::Int32Div(Node* dividend, int32_t divisor) {
106 DCHECK_NE(0, divisor);
107 DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor);
108 base::MagicNumbersForDivision<uint32_t> const mag =
109 base::SignedDivisionByConstant(bit_cast<uint32_t>(divisor));
110 Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend,
111 Uint32Constant(mag.multiplier));
112 if (divisor > 0 && bit_cast<int32_t>(mag.multiplier) < 0) {
113 quotient = Int32Add(quotient, dividend);
114 } else if (divisor < 0 && bit_cast<int32_t>(mag.multiplier) > 0) {
115 quotient = Int32Sub(quotient, dividend);
116 }
117 return Int32Add(Word32Sar(quotient, mag.shift), Word32Shr(dividend, 31));
118 }
119
120
Uint32Div(Node * dividend,uint32_t divisor)121 Node* MachineOperatorReducer::Uint32Div(Node* dividend, uint32_t divisor) {
122 DCHECK_LT(0u, divisor);
123 // If the divisor is even, we can avoid using the expensive fixup by shifting
124 // the dividend upfront.
125 unsigned const shift = base::bits::CountTrailingZeros32(divisor);
126 dividend = Word32Shr(dividend, shift);
127 divisor >>= shift;
128 // Compute the magic number for the (shifted) divisor.
129 base::MagicNumbersForDivision<uint32_t> const mag =
130 base::UnsignedDivisionByConstant(divisor, shift);
131 Node* quotient = graph()->NewNode(machine()->Uint32MulHigh(), dividend,
132 Uint32Constant(mag.multiplier));
133 if (mag.add) {
134 DCHECK_LE(1u, mag.shift);
135 quotient = Word32Shr(
136 Int32Add(Word32Shr(Int32Sub(dividend, quotient), 1), quotient),
137 mag.shift - 1);
138 } else {
139 quotient = Word32Shr(quotient, mag.shift);
140 }
141 return quotient;
142 }
143
144
145 // Perform constant folding and strength reduction on machine operators.
Reduce(Node * node)146 Reduction MachineOperatorReducer::Reduce(Node* node) {
147 switch (node->opcode()) {
148 case IrOpcode::kProjection:
149 return ReduceProjection(ProjectionIndexOf(node->op()), node->InputAt(0));
150 case IrOpcode::kWord32And:
151 return ReduceWord32And(node);
152 case IrOpcode::kWord32Or:
153 return ReduceWord32Or(node);
154 case IrOpcode::kWord32Xor:
155 return ReduceWord32Xor(node);
156 case IrOpcode::kWord32Shl:
157 return ReduceWord32Shl(node);
158 case IrOpcode::kWord64Shl:
159 return ReduceWord64Shl(node);
160 case IrOpcode::kWord32Shr:
161 return ReduceWord32Shr(node);
162 case IrOpcode::kWord64Shr:
163 return ReduceWord64Shr(node);
164 case IrOpcode::kWord32Sar:
165 return ReduceWord32Sar(node);
166 case IrOpcode::kWord64Sar:
167 return ReduceWord64Sar(node);
168 case IrOpcode::kWord32Ror: {
169 Int32BinopMatcher m(node);
170 if (m.right().Is(0)) return Replace(m.left().node()); // x ror 0 => x
171 if (m.IsFoldable()) { // K ror K => K
172 return ReplaceInt32(
173 base::bits::RotateRight32(m.left().Value(), m.right().Value()));
174 }
175 break;
176 }
177 case IrOpcode::kWord32Equal: {
178 Int32BinopMatcher m(node);
179 if (m.IsFoldable()) { // K == K => K
180 return ReplaceBool(m.left().Value() == m.right().Value());
181 }
182 if (m.left().IsInt32Sub() && m.right().Is(0)) { // x - y == 0 => x == y
183 Int32BinopMatcher msub(m.left().node());
184 node->ReplaceInput(0, msub.left().node());
185 node->ReplaceInput(1, msub.right().node());
186 return Changed(node);
187 }
188 // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
189 if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
190 break;
191 }
192 case IrOpcode::kWord64Equal: {
193 Int64BinopMatcher m(node);
194 if (m.IsFoldable()) { // K == K => K
195 return ReplaceBool(m.left().Value() == m.right().Value());
196 }
197 if (m.left().IsInt64Sub() && m.right().Is(0)) { // x - y == 0 => x == y
198 Int64BinopMatcher msub(m.left().node());
199 node->ReplaceInput(0, msub.left().node());
200 node->ReplaceInput(1, msub.right().node());
201 return Changed(node);
202 }
203 // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
204 if (m.LeftEqualsRight()) return ReplaceBool(true); // x == x => true
205 break;
206 }
207 case IrOpcode::kInt32Add:
208 return ReduceInt32Add(node);
209 case IrOpcode::kInt64Add:
210 return ReduceInt64Add(node);
211 case IrOpcode::kInt32Sub:
212 return ReduceInt32Sub(node);
213 case IrOpcode::kInt64Sub:
214 return ReduceInt64Sub(node);
215 case IrOpcode::kInt32Mul: {
216 Int32BinopMatcher m(node);
217 if (m.right().Is(0)) return Replace(m.right().node()); // x * 0 => 0
218 if (m.right().Is(1)) return Replace(m.left().node()); // x * 1 => x
219 if (m.IsFoldable()) { // K * K => K
220 return ReplaceInt32(m.left().Value() * m.right().Value());
221 }
222 if (m.right().Is(-1)) { // x * -1 => 0 - x
223 node->ReplaceInput(0, Int32Constant(0));
224 node->ReplaceInput(1, m.left().node());
225 NodeProperties::ChangeOp(node, machine()->Int32Sub());
226 return Changed(node);
227 }
228 if (m.right().IsPowerOf2()) { // x * 2^n => x << n
229 node->ReplaceInput(1, Int32Constant(WhichPowerOf2(m.right().Value())));
230 NodeProperties::ChangeOp(node, machine()->Word32Shl());
231 Reduction reduction = ReduceWord32Shl(node);
232 return reduction.Changed() ? reduction : Changed(node);
233 }
234 break;
235 }
236 case IrOpcode::kInt32MulWithOverflow: {
237 Int32BinopMatcher m(node);
238 if (m.right().Is(2)) {
239 node->ReplaceInput(1, m.left().node());
240 NodeProperties::ChangeOp(node, machine()->Int32AddWithOverflow());
241 return Changed(node);
242 }
243 if (m.right().Is(-1)) {
244 node->ReplaceInput(0, Int32Constant(0));
245 node->ReplaceInput(1, m.left().node());
246 NodeProperties::ChangeOp(node, machine()->Int32SubWithOverflow());
247 return Changed(node);
248 }
249 break;
250 }
251 case IrOpcode::kInt32Div:
252 return ReduceInt32Div(node);
253 case IrOpcode::kUint32Div:
254 return ReduceUint32Div(node);
255 case IrOpcode::kInt32Mod:
256 return ReduceInt32Mod(node);
257 case IrOpcode::kUint32Mod:
258 return ReduceUint32Mod(node);
259 case IrOpcode::kInt32LessThan: {
260 Int32BinopMatcher m(node);
261 if (m.IsFoldable()) { // K < K => K
262 return ReplaceBool(m.left().Value() < m.right().Value());
263 }
264 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
265 if (m.left().IsWord32Or() && m.right().Is(0)) {
266 // (x | K) < 0 => true or (K | x) < 0 => true iff K < 0
267 Int32BinopMatcher mleftmatcher(m.left().node());
268 if (mleftmatcher.left().IsNegative() ||
269 mleftmatcher.right().IsNegative()) {
270 return ReplaceBool(true);
271 }
272 }
273 break;
274 }
275 case IrOpcode::kInt32LessThanOrEqual: {
276 Int32BinopMatcher m(node);
277 if (m.IsFoldable()) { // K <= K => K
278 return ReplaceBool(m.left().Value() <= m.right().Value());
279 }
280 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
281 break;
282 }
283 case IrOpcode::kUint32LessThan: {
284 Uint32BinopMatcher m(node);
285 if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => false
286 if (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false
287 if (m.IsFoldable()) { // K < K => K
288 return ReplaceBool(m.left().Value() < m.right().Value());
289 }
290 if (m.LeftEqualsRight()) return ReplaceBool(false); // x < x => false
291 if (m.left().IsWord32Sar() && m.right().HasValue()) {
292 Int32BinopMatcher mleft(m.left().node());
293 if (mleft.right().HasValue()) {
294 // (x >> K) < C => x < (C << K)
295 // when C < (M >> K)
296 const uint32_t c = m.right().Value();
297 const uint32_t k = mleft.right().Value() & 0x1f;
298 if (c < static_cast<uint32_t>(kMaxInt >> k)) {
299 node->ReplaceInput(0, mleft.left().node());
300 node->ReplaceInput(1, Uint32Constant(c << k));
301 return Changed(node);
302 }
303 // TODO(turbofan): else the comparison is always true.
304 }
305 }
306 break;
307 }
308 case IrOpcode::kUint32LessThanOrEqual: {
309 Uint32BinopMatcher m(node);
310 if (m.left().Is(0)) return ReplaceBool(true); // 0 <= x => true
311 if (m.right().Is(kMaxUInt32)) return ReplaceBool(true); // x <= M => true
312 if (m.IsFoldable()) { // K <= K => K
313 return ReplaceBool(m.left().Value() <= m.right().Value());
314 }
315 if (m.LeftEqualsRight()) return ReplaceBool(true); // x <= x => true
316 break;
317 }
318 case IrOpcode::kFloat32Sub: {
319 Float32BinopMatcher m(node);
320 if (allow_signalling_nan_ && m.right().Is(0) &&
321 (copysign(1.0, m.right().Value()) > 0)) {
322 return Replace(m.left().node()); // x - 0 => x
323 }
324 if (m.right().IsNaN()) { // x - NaN => NaN
325 // Do some calculation to make a signalling NaN quiet.
326 return ReplaceFloat32(m.right().Value() - m.right().Value());
327 }
328 if (m.left().IsNaN()) { // NaN - x => NaN
329 // Do some calculation to make a signalling NaN quiet.
330 return ReplaceFloat32(m.left().Value() - m.left().Value());
331 }
332 if (m.IsFoldable()) { // L - R => (L - R)
333 return ReplaceFloat32(m.left().Value() - m.right().Value());
334 }
335 if (allow_signalling_nan_ && m.left().IsMinusZero()) {
336 // -0.0 - round_down(-0.0 - R) => round_up(R)
337 if (machine()->Float32RoundUp().IsSupported() &&
338 m.right().IsFloat32RoundDown()) {
339 if (m.right().InputAt(0)->opcode() == IrOpcode::kFloat32Sub) {
340 Float32BinopMatcher mright0(m.right().InputAt(0));
341 if (mright0.left().IsMinusZero()) {
342 return Replace(graph()->NewNode(machine()->Float32RoundUp().op(),
343 mright0.right().node()));
344 }
345 }
346 }
347 // -0.0 - R => -R
348 node->RemoveInput(0);
349 NodeProperties::ChangeOp(node, machine()->Float32Neg());
350 return Changed(node);
351 }
352 break;
353 }
354 case IrOpcode::kFloat64Add: {
355 Float64BinopMatcher m(node);
356 if (m.right().IsNaN()) { // x + NaN => NaN
357 // Do some calculation to make a signalling NaN quiet.
358 return ReplaceFloat64(m.right().Value() - m.right().Value());
359 }
360 if (m.IsFoldable()) { // K + K => K
361 return ReplaceFloat64(m.left().Value() + m.right().Value());
362 }
363 break;
364 }
365 case IrOpcode::kFloat64Sub: {
366 Float64BinopMatcher m(node);
367 if (allow_signalling_nan_ && m.right().Is(0) &&
368 (Double(m.right().Value()).Sign() > 0)) {
369 return Replace(m.left().node()); // x - 0 => x
370 }
371 if (m.right().IsNaN()) { // x - NaN => NaN
372 // Do some calculation to make a signalling NaN quiet.
373 return ReplaceFloat64(m.right().Value() - m.right().Value());
374 }
375 if (m.left().IsNaN()) { // NaN - x => NaN
376 // Do some calculation to make a signalling NaN quiet.
377 return ReplaceFloat64(m.left().Value() - m.left().Value());
378 }
379 if (m.IsFoldable()) { // L - R => (L - R)
380 return ReplaceFloat64(m.left().Value() - m.right().Value());
381 }
382 if (allow_signalling_nan_ && m.left().IsMinusZero()) {
383 // -0.0 - round_down(-0.0 - R) => round_up(R)
384 if (machine()->Float64RoundUp().IsSupported() &&
385 m.right().IsFloat64RoundDown()) {
386 if (m.right().InputAt(0)->opcode() == IrOpcode::kFloat64Sub) {
387 Float64BinopMatcher mright0(m.right().InputAt(0));
388 if (mright0.left().IsMinusZero()) {
389 return Replace(graph()->NewNode(machine()->Float64RoundUp().op(),
390 mright0.right().node()));
391 }
392 }
393 }
394 // -0.0 - R => -R
395 node->RemoveInput(0);
396 NodeProperties::ChangeOp(node, machine()->Float64Neg());
397 return Changed(node);
398 }
399 break;
400 }
401 case IrOpcode::kFloat64Mul: {
402 Float64BinopMatcher m(node);
403 if (allow_signalling_nan_ && m.right().Is(1))
404 return Replace(m.left().node()); // x * 1.0 => x
405 if (m.right().Is(-1)) { // x * -1.0 => -0.0 - x
406 node->ReplaceInput(0, Float64Constant(-0.0));
407 node->ReplaceInput(1, m.left().node());
408 NodeProperties::ChangeOp(node, machine()->Float64Sub());
409 return Changed(node);
410 }
411 if (m.right().IsNaN()) { // x * NaN => NaN
412 // Do some calculation to make a signalling NaN quiet.
413 return ReplaceFloat64(m.right().Value() - m.right().Value());
414 }
415 if (m.IsFoldable()) { // K * K => K
416 return ReplaceFloat64(m.left().Value() * m.right().Value());
417 }
418 if (m.right().Is(2)) { // x * 2.0 => x + x
419 node->ReplaceInput(1, m.left().node());
420 NodeProperties::ChangeOp(node, machine()->Float64Add());
421 return Changed(node);
422 }
423 break;
424 }
425 case IrOpcode::kFloat64Div: {
426 Float64BinopMatcher m(node);
427 if (allow_signalling_nan_ && m.right().Is(1))
428 return Replace(m.left().node()); // x / 1.0 => x
429 // TODO(ahaas): We could do x / 1.0 = x if we knew that x is not an sNaN.
430 if (m.right().IsNaN()) { // x / NaN => NaN
431 // Do some calculation to make a signalling NaN quiet.
432 return ReplaceFloat64(m.right().Value() - m.right().Value());
433 }
434 if (m.left().IsNaN()) { // NaN / x => NaN
435 // Do some calculation to make a signalling NaN quiet.
436 return ReplaceFloat64(m.left().Value() - m.left().Value());
437 }
438 if (m.IsFoldable()) { // K / K => K
439 return ReplaceFloat64(m.left().Value() / m.right().Value());
440 }
441 if (allow_signalling_nan_ && m.right().Is(-1)) { // x / -1.0 => -x
442 node->RemoveInput(1);
443 NodeProperties::ChangeOp(node, machine()->Float64Neg());
444 return Changed(node);
445 }
446 if (m.right().IsNormal() && m.right().IsPositiveOrNegativePowerOf2()) {
447 // All reciprocals of non-denormal powers of two can be represented
448 // exactly, so division by power of two can be reduced to
449 // multiplication by reciprocal, with the same result.
450 node->ReplaceInput(1, Float64Constant(1.0 / m.right().Value()));
451 NodeProperties::ChangeOp(node, machine()->Float64Mul());
452 return Changed(node);
453 }
454 break;
455 }
456 case IrOpcode::kFloat64Mod: {
457 Float64BinopMatcher m(node);
458 if (m.right().Is(0)) { // x % 0 => NaN
459 return ReplaceFloat64(std::numeric_limits<double>::quiet_NaN());
460 }
461 if (m.right().IsNaN()) { // x % NaN => NaN
462 return Replace(m.right().node());
463 }
464 if (m.left().IsNaN()) { // NaN % x => NaN
465 return Replace(m.left().node());
466 }
467 if (m.IsFoldable()) { // K % K => K
468 return ReplaceFloat64(modulo(m.left().Value(), m.right().Value()));
469 }
470 break;
471 }
472 case IrOpcode::kFloat64Acos: {
473 Float64Matcher m(node->InputAt(0));
474 if (m.HasValue()) return ReplaceFloat64(base::ieee754::acos(m.Value()));
475 break;
476 }
477 case IrOpcode::kFloat64Acosh: {
478 Float64Matcher m(node->InputAt(0));
479 if (m.HasValue()) return ReplaceFloat64(base::ieee754::acosh(m.Value()));
480 break;
481 }
482 case IrOpcode::kFloat64Asin: {
483 Float64Matcher m(node->InputAt(0));
484 if (m.HasValue()) return ReplaceFloat64(base::ieee754::asin(m.Value()));
485 break;
486 }
487 case IrOpcode::kFloat64Asinh: {
488 Float64Matcher m(node->InputAt(0));
489 if (m.HasValue()) return ReplaceFloat64(base::ieee754::asinh(m.Value()));
490 break;
491 }
492 case IrOpcode::kFloat64Atan: {
493 Float64Matcher m(node->InputAt(0));
494 if (m.HasValue()) return ReplaceFloat64(base::ieee754::atan(m.Value()));
495 break;
496 }
497 case IrOpcode::kFloat64Atanh: {
498 Float64Matcher m(node->InputAt(0));
499 if (m.HasValue()) return ReplaceFloat64(base::ieee754::atanh(m.Value()));
500 break;
501 }
502 case IrOpcode::kFloat64Atan2: {
503 Float64BinopMatcher m(node);
504 if (m.right().IsNaN()) {
505 return Replace(m.right().node());
506 }
507 if (m.left().IsNaN()) {
508 return Replace(m.left().node());
509 }
510 if (m.IsFoldable()) {
511 return ReplaceFloat64(
512 base::ieee754::atan2(m.left().Value(), m.right().Value()));
513 }
514 break;
515 }
516 case IrOpcode::kFloat64Cbrt: {
517 Float64Matcher m(node->InputAt(0));
518 if (m.HasValue()) return ReplaceFloat64(base::ieee754::cbrt(m.Value()));
519 break;
520 }
521 case IrOpcode::kFloat64Cos: {
522 Float64Matcher m(node->InputAt(0));
523 if (m.HasValue()) return ReplaceFloat64(base::ieee754::cos(m.Value()));
524 break;
525 }
526 case IrOpcode::kFloat64Cosh: {
527 Float64Matcher m(node->InputAt(0));
528 if (m.HasValue()) return ReplaceFloat64(base::ieee754::cosh(m.Value()));
529 break;
530 }
531 case IrOpcode::kFloat64Exp: {
532 Float64Matcher m(node->InputAt(0));
533 if (m.HasValue()) return ReplaceFloat64(base::ieee754::exp(m.Value()));
534 break;
535 }
536 case IrOpcode::kFloat64Expm1: {
537 Float64Matcher m(node->InputAt(0));
538 if (m.HasValue()) return ReplaceFloat64(base::ieee754::expm1(m.Value()));
539 break;
540 }
541 case IrOpcode::kFloat64Log: {
542 Float64Matcher m(node->InputAt(0));
543 if (m.HasValue()) return ReplaceFloat64(base::ieee754::log(m.Value()));
544 break;
545 }
546 case IrOpcode::kFloat64Log1p: {
547 Float64Matcher m(node->InputAt(0));
548 if (m.HasValue()) return ReplaceFloat64(base::ieee754::log1p(m.Value()));
549 break;
550 }
551 case IrOpcode::kFloat64Log10: {
552 Float64Matcher m(node->InputAt(0));
553 if (m.HasValue()) return ReplaceFloat64(base::ieee754::log10(m.Value()));
554 break;
555 }
556 case IrOpcode::kFloat64Log2: {
557 Float64Matcher m(node->InputAt(0));
558 if (m.HasValue()) return ReplaceFloat64(base::ieee754::log2(m.Value()));
559 break;
560 }
561 case IrOpcode::kFloat64Pow: {
562 Float64BinopMatcher m(node);
563 if (m.IsFoldable()) {
564 return ReplaceFloat64(Pow(m.left().Value(), m.right().Value()));
565 } else if (m.right().Is(0.0)) { // x ** +-0.0 => 1.0
566 return ReplaceFloat64(1.0);
567 } else if (m.right().Is(-2.0)) { // x ** -2.0 => 1 / (x * x)
568 node->ReplaceInput(0, Float64Constant(1.0));
569 node->ReplaceInput(1, Float64Mul(m.left().node(), m.left().node()));
570 NodeProperties::ChangeOp(node, machine()->Float64Div());
571 return Changed(node);
572 } else if (m.right().Is(2.0)) { // x ** 2.0 => x * x
573 node->ReplaceInput(1, m.left().node());
574 NodeProperties::ChangeOp(node, machine()->Float64Mul());
575 return Changed(node);
576 } else if (m.right().Is(-0.5)) {
577 // x ** 0.5 => 1 / (if x <= -Infinity then Infinity else sqrt(0.0 + x))
578 node->ReplaceInput(0, Float64Constant(1.0));
579 node->ReplaceInput(1, Float64PowHalf(m.left().node()));
580 NodeProperties::ChangeOp(node, machine()->Float64Div());
581 return Changed(node);
582 } else if (m.right().Is(0.5)) {
583 // x ** 0.5 => if x <= -Infinity then Infinity else sqrt(0.0 + x)
584 return Replace(Float64PowHalf(m.left().node()));
585 }
586 break;
587 }
588 case IrOpcode::kFloat64Sin: {
589 Float64Matcher m(node->InputAt(0));
590 if (m.HasValue()) return ReplaceFloat64(base::ieee754::sin(m.Value()));
591 break;
592 }
593 case IrOpcode::kFloat64Sinh: {
594 Float64Matcher m(node->InputAt(0));
595 if (m.HasValue()) return ReplaceFloat64(base::ieee754::sinh(m.Value()));
596 break;
597 }
598 case IrOpcode::kFloat64Tan: {
599 Float64Matcher m(node->InputAt(0));
600 if (m.HasValue()) return ReplaceFloat64(base::ieee754::tan(m.Value()));
601 break;
602 }
603 case IrOpcode::kFloat64Tanh: {
604 Float64Matcher m(node->InputAt(0));
605 if (m.HasValue()) return ReplaceFloat64(base::ieee754::tanh(m.Value()));
606 break;
607 }
608 case IrOpcode::kChangeFloat32ToFloat64: {
609 Float32Matcher m(node->InputAt(0));
610 if (m.HasValue()) {
611 if (!allow_signalling_nan_ && std::isnan(m.Value())) {
612 // Do some calculation to make guarantee the value is a quiet NaN.
613 return ReplaceFloat64(m.Value() + m.Value());
614 }
615 return ReplaceFloat64(m.Value());
616 }
617 break;
618 }
619 case IrOpcode::kChangeFloat64ToInt32: {
620 Float64Matcher m(node->InputAt(0));
621 if (m.HasValue()) return ReplaceInt32(FastD2I(m.Value()));
622 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
623 break;
624 }
625 case IrOpcode::kChangeFloat64ToUint32: {
626 Float64Matcher m(node->InputAt(0));
627 if (m.HasValue()) return ReplaceInt32(FastD2UI(m.Value()));
628 if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0));
629 break;
630 }
631 case IrOpcode::kChangeInt32ToFloat64: {
632 Int32Matcher m(node->InputAt(0));
633 if (m.HasValue()) return ReplaceFloat64(FastI2D(m.Value()));
634 break;
635 }
636 case IrOpcode::kChangeInt32ToInt64: {
637 Int32Matcher m(node->InputAt(0));
638 if (m.HasValue()) return ReplaceInt64(m.Value());
639 break;
640 }
641 case IrOpcode::kChangeUint32ToFloat64: {
642 Uint32Matcher m(node->InputAt(0));
643 if (m.HasValue()) return ReplaceFloat64(FastUI2D(m.Value()));
644 break;
645 }
646 case IrOpcode::kChangeUint32ToUint64: {
647 Uint32Matcher m(node->InputAt(0));
648 if (m.HasValue()) return ReplaceInt64(static_cast<uint64_t>(m.Value()));
649 break;
650 }
651 case IrOpcode::kTruncateFloat64ToWord32: {
652 Float64Matcher m(node->InputAt(0));
653 if (m.HasValue()) return ReplaceInt32(DoubleToInt32(m.Value()));
654 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
655 return NoChange();
656 }
657 case IrOpcode::kTruncateInt64ToInt32: {
658 Int64Matcher m(node->InputAt(0));
659 if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value()));
660 if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
661 break;
662 }
663 case IrOpcode::kTruncateFloat64ToFloat32: {
664 Float64Matcher m(node->InputAt(0));
665 if (m.HasValue()) {
666 if (!allow_signalling_nan_ && std::isnan(m.Value())) {
667 // Do some calculation to make guarantee the value is a quiet NaN.
668 return ReplaceFloat32(DoubleToFloat32(m.Value() + m.Value()));
669 }
670 return ReplaceFloat32(DoubleToFloat32(m.Value()));
671 }
672 if (allow_signalling_nan_ && m.IsChangeFloat32ToFloat64())
673 return Replace(m.node()->InputAt(0));
674 break;
675 }
676 case IrOpcode::kRoundFloat64ToInt32: {
677 Float64Matcher m(node->InputAt(0));
678 if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value()));
679 if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
680 break;
681 }
682 case IrOpcode::kFloat64InsertLowWord32:
683 return ReduceFloat64InsertLowWord32(node);
684 case IrOpcode::kFloat64InsertHighWord32:
685 return ReduceFloat64InsertHighWord32(node);
686 case IrOpcode::kStore:
687 case IrOpcode::kUnalignedStore:
688 case IrOpcode::kCheckedStore:
689 return ReduceStore(node);
690 case IrOpcode::kFloat64Equal:
691 case IrOpcode::kFloat64LessThan:
692 case IrOpcode::kFloat64LessThanOrEqual:
693 return ReduceFloat64Compare(node);
694 case IrOpcode::kFloat64RoundDown:
695 return ReduceFloat64RoundDown(node);
696 default:
697 break;
698 }
699 return NoChange();
700 }
701
ReduceInt32Add(Node * node)702 Reduction MachineOperatorReducer::ReduceInt32Add(Node* node) {
703 DCHECK_EQ(IrOpcode::kInt32Add, node->opcode());
704 Int32BinopMatcher m(node);
705 if (m.right().Is(0)) return Replace(m.left().node()); // x + 0 => x
706 if (m.IsFoldable()) { // K + K => K
707 return ReplaceUint32(bit_cast<uint32_t>(m.left().Value()) +
708 bit_cast<uint32_t>(m.right().Value()));
709 }
710 if (m.left().IsInt32Sub()) {
711 Int32BinopMatcher mleft(m.left().node());
712 if (mleft.left().Is(0)) { // (0 - x) + y => y - x
713 node->ReplaceInput(0, m.right().node());
714 node->ReplaceInput(1, mleft.right().node());
715 NodeProperties::ChangeOp(node, machine()->Int32Sub());
716 Reduction const reduction = ReduceInt32Sub(node);
717 return reduction.Changed() ? reduction : Changed(node);
718 }
719 }
720 if (m.right().IsInt32Sub()) {
721 Int32BinopMatcher mright(m.right().node());
722 if (mright.left().Is(0)) { // y + (0 - x) => y - x
723 node->ReplaceInput(1, mright.right().node());
724 NodeProperties::ChangeOp(node, machine()->Int32Sub());
725 Reduction const reduction = ReduceInt32Sub(node);
726 return reduction.Changed() ? reduction : Changed(node);
727 }
728 }
729 return NoChange();
730 }
731
ReduceInt64Add(Node * node)732 Reduction MachineOperatorReducer::ReduceInt64Add(Node* node) {
733 DCHECK_EQ(IrOpcode::kInt64Add, node->opcode());
734 Int64BinopMatcher m(node);
735 if (m.right().Is(0)) return Replace(m.left().node()); // x + 0 => 0
736 if (m.IsFoldable()) {
737 return Replace(Uint64Constant(bit_cast<uint64_t>(m.left().Value()) +
738 bit_cast<uint64_t>(m.right().Value())));
739 }
740 return NoChange();
741 }
742
ReduceInt32Sub(Node * node)743 Reduction MachineOperatorReducer::ReduceInt32Sub(Node* node) {
744 DCHECK_EQ(IrOpcode::kInt32Sub, node->opcode());
745 Int32BinopMatcher m(node);
746 if (m.right().Is(0)) return Replace(m.left().node()); // x - 0 => x
747 if (m.IsFoldable()) { // K - K => K
748 return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) -
749 static_cast<uint32_t>(m.right().Value()));
750 }
751 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x - x => 0
752 if (m.right().HasValue()) { // x - K => x + -K
753 node->ReplaceInput(1, Int32Constant(-m.right().Value()));
754 NodeProperties::ChangeOp(node, machine()->Int32Add());
755 Reduction const reduction = ReduceInt32Add(node);
756 return reduction.Changed() ? reduction : Changed(node);
757 }
758 return NoChange();
759 }
760
ReduceInt64Sub(Node * node)761 Reduction MachineOperatorReducer::ReduceInt64Sub(Node* node) {
762 DCHECK_EQ(IrOpcode::kInt64Sub, node->opcode());
763 Int64BinopMatcher m(node);
764 if (m.right().Is(0)) return Replace(m.left().node()); // x - 0 => x
765 if (m.IsFoldable()) { // K - K => K
766 return Replace(Uint64Constant(bit_cast<uint64_t>(m.left().Value()) -
767 bit_cast<uint64_t>(m.right().Value())));
768 }
769 if (m.LeftEqualsRight()) return Replace(Int64Constant(0)); // x - x => 0
770 if (m.right().HasValue()) { // x - K => x + -K
771 node->ReplaceInput(1, Int64Constant(-m.right().Value()));
772 NodeProperties::ChangeOp(node, machine()->Int64Add());
773 Reduction const reduction = ReduceInt64Add(node);
774 return reduction.Changed() ? reduction : Changed(node);
775 }
776 return NoChange();
777 }
778
ReduceInt32Div(Node * node)779 Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
780 Int32BinopMatcher m(node);
781 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0
782 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0
783 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x
784 if (m.IsFoldable()) { // K / K => K
785 return ReplaceInt32(
786 base::bits::SignedDiv32(m.left().Value(), m.right().Value()));
787 }
788 if (m.LeftEqualsRight()) { // x / x => x != 0
789 Node* const zero = Int32Constant(0);
790 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
791 }
792 if (m.right().Is(-1)) { // x / -1 => 0 - x
793 node->ReplaceInput(0, Int32Constant(0));
794 node->ReplaceInput(1, m.left().node());
795 node->TrimInputCount(2);
796 NodeProperties::ChangeOp(node, machine()->Int32Sub());
797 return Changed(node);
798 }
799 if (m.right().HasValue()) {
800 int32_t const divisor = m.right().Value();
801 Node* const dividend = m.left().node();
802 Node* quotient = dividend;
803 if (base::bits::IsPowerOfTwo32(Abs(divisor))) {
804 uint32_t const shift = WhichPowerOf2Abs(divisor);
805 DCHECK_NE(0u, shift);
806 if (shift > 1) {
807 quotient = Word32Sar(quotient, 31);
808 }
809 quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend);
810 quotient = Word32Sar(quotient, shift);
811 } else {
812 quotient = Int32Div(quotient, Abs(divisor));
813 }
814 if (divisor < 0) {
815 node->ReplaceInput(0, Int32Constant(0));
816 node->ReplaceInput(1, quotient);
817 node->TrimInputCount(2);
818 NodeProperties::ChangeOp(node, machine()->Int32Sub());
819 return Changed(node);
820 }
821 return Replace(quotient);
822 }
823 return NoChange();
824 }
825
826
ReduceUint32Div(Node * node)827 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) {
828 Uint32BinopMatcher m(node);
829 if (m.left().Is(0)) return Replace(m.left().node()); // 0 / x => 0
830 if (m.right().Is(0)) return Replace(m.right().node()); // x / 0 => 0
831 if (m.right().Is(1)) return Replace(m.left().node()); // x / 1 => x
832 if (m.IsFoldable()) { // K / K => K
833 return ReplaceUint32(
834 base::bits::UnsignedDiv32(m.left().Value(), m.right().Value()));
835 }
836 if (m.LeftEqualsRight()) { // x / x => x != 0
837 Node* const zero = Int32Constant(0);
838 return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
839 }
840 if (m.right().HasValue()) {
841 Node* const dividend = m.left().node();
842 uint32_t const divisor = m.right().Value();
843 if (base::bits::IsPowerOfTwo32(divisor)) { // x / 2^n => x >> n
844 node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value())));
845 node->TrimInputCount(2);
846 NodeProperties::ChangeOp(node, machine()->Word32Shr());
847 return Changed(node);
848 } else {
849 return Replace(Uint32Div(dividend, divisor));
850 }
851 }
852 return NoChange();
853 }
854
855
ReduceInt32Mod(Node * node)856 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
857 Int32BinopMatcher m(node);
858 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0
859 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0
860 if (m.right().Is(1)) return ReplaceInt32(0); // x % 1 => 0
861 if (m.right().Is(-1)) return ReplaceInt32(0); // x % -1 => 0
862 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0
863 if (m.IsFoldable()) { // K % K => K
864 return ReplaceInt32(
865 base::bits::SignedMod32(m.left().Value(), m.right().Value()));
866 }
867 if (m.right().HasValue()) {
868 Node* const dividend = m.left().node();
869 int32_t const divisor = Abs(m.right().Value());
870 if (base::bits::IsPowerOfTwo32(divisor)) {
871 uint32_t const mask = divisor - 1;
872 Node* const zero = Int32Constant(0);
873 Diamond d(graph(), common(),
874 graph()->NewNode(machine()->Int32LessThan(), dividend, zero),
875 BranchHint::kFalse);
876 return Replace(
877 d.Phi(MachineRepresentation::kWord32,
878 Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)),
879 Word32And(dividend, mask)));
880 } else {
881 Node* quotient = Int32Div(dividend, divisor);
882 DCHECK_EQ(dividend, node->InputAt(0));
883 node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
884 node->TrimInputCount(2);
885 NodeProperties::ChangeOp(node, machine()->Int32Sub());
886 }
887 return Changed(node);
888 }
889 return NoChange();
890 }
891
892
ReduceUint32Mod(Node * node)893 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) {
894 Uint32BinopMatcher m(node);
895 if (m.left().Is(0)) return Replace(m.left().node()); // 0 % x => 0
896 if (m.right().Is(0)) return Replace(m.right().node()); // x % 0 => 0
897 if (m.right().Is(1)) return ReplaceUint32(0); // x % 1 => 0
898 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x % x => 0
899 if (m.IsFoldable()) { // K % K => K
900 return ReplaceUint32(
901 base::bits::UnsignedMod32(m.left().Value(), m.right().Value()));
902 }
903 if (m.right().HasValue()) {
904 Node* const dividend = m.left().node();
905 uint32_t const divisor = m.right().Value();
906 if (base::bits::IsPowerOfTwo32(divisor)) { // x % 2^n => x & 2^n-1
907 node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1));
908 node->TrimInputCount(2);
909 NodeProperties::ChangeOp(node, machine()->Word32And());
910 } else {
911 Node* quotient = Uint32Div(dividend, divisor);
912 DCHECK_EQ(dividend, node->InputAt(0));
913 node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor)));
914 node->TrimInputCount(2);
915 NodeProperties::ChangeOp(node, machine()->Int32Sub());
916 }
917 return Changed(node);
918 }
919 return NoChange();
920 }
921
922
ReduceStore(Node * node)923 Reduction MachineOperatorReducer::ReduceStore(Node* node) {
924 NodeMatcher nm(node);
925 MachineRepresentation rep;
926 int value_input;
927 if (nm.IsCheckedStore()) {
928 rep = CheckedStoreRepresentationOf(node->op());
929 value_input = 3;
930 } else if (nm.IsStore()) {
931 rep = StoreRepresentationOf(node->op()).representation();
932 value_input = 2;
933 } else {
934 DCHECK(nm.IsUnalignedStore());
935 rep = UnalignedStoreRepresentationOf(node->op());
936 value_input = 2;
937 }
938
939 Node* const value = node->InputAt(value_input);
940
941 switch (value->opcode()) {
942 case IrOpcode::kWord32And: {
943 Uint32BinopMatcher m(value);
944 if (m.right().HasValue() && ((rep == MachineRepresentation::kWord8 &&
945 (m.right().Value() & 0xff) == 0xff) ||
946 (rep == MachineRepresentation::kWord16 &&
947 (m.right().Value() & 0xffff) == 0xffff))) {
948 node->ReplaceInput(value_input, m.left().node());
949 return Changed(node);
950 }
951 break;
952 }
953 case IrOpcode::kWord32Sar: {
954 Int32BinopMatcher m(value);
955 if (m.left().IsWord32Shl() && ((rep == MachineRepresentation::kWord8 &&
956 m.right().IsInRange(1, 24)) ||
957 (rep == MachineRepresentation::kWord16 &&
958 m.right().IsInRange(1, 16)))) {
959 Int32BinopMatcher mleft(m.left().node());
960 if (mleft.right().Is(m.right().Value())) {
961 node->ReplaceInput(value_input, mleft.left().node());
962 return Changed(node);
963 }
964 }
965 break;
966 }
967 default:
968 break;
969 }
970 return NoChange();
971 }
972
973
ReduceProjection(size_t index,Node * node)974 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
975 switch (node->opcode()) {
976 case IrOpcode::kInt32AddWithOverflow: {
977 DCHECK(index == 0 || index == 1);
978 Int32BinopMatcher m(node);
979 if (m.IsFoldable()) {
980 int32_t val;
981 bool ovf = base::bits::SignedAddOverflow32(m.left().Value(),
982 m.right().Value(), &val);
983 return ReplaceInt32(index == 0 ? val : ovf);
984 }
985 if (m.right().Is(0)) {
986 return Replace(index == 0 ? m.left().node() : m.right().node());
987 }
988 break;
989 }
990 case IrOpcode::kInt32SubWithOverflow: {
991 DCHECK(index == 0 || index == 1);
992 Int32BinopMatcher m(node);
993 if (m.IsFoldable()) {
994 int32_t val;
995 bool ovf = base::bits::SignedSubOverflow32(m.left().Value(),
996 m.right().Value(), &val);
997 return ReplaceInt32(index == 0 ? val : ovf);
998 }
999 if (m.right().Is(0)) {
1000 return Replace(index == 0 ? m.left().node() : m.right().node());
1001 }
1002 break;
1003 }
1004 case IrOpcode::kInt32MulWithOverflow: {
1005 DCHECK(index == 0 || index == 1);
1006 Int32BinopMatcher m(node);
1007 if (m.IsFoldable()) {
1008 int32_t val;
1009 bool ovf = base::bits::SignedMulOverflow32(m.left().Value(),
1010 m.right().Value(), &val);
1011 return ReplaceInt32(index == 0 ? val : ovf);
1012 }
1013 if (m.right().Is(0)) {
1014 return Replace(m.right().node());
1015 }
1016 if (m.right().Is(1)) {
1017 return index == 0 ? Replace(m.left().node()) : ReplaceInt32(0);
1018 }
1019 break;
1020 }
1021 default:
1022 break;
1023 }
1024 return NoChange();
1025 }
1026
1027
ReduceWord32Shifts(Node * node)1028 Reduction MachineOperatorReducer::ReduceWord32Shifts(Node* node) {
1029 DCHECK((node->opcode() == IrOpcode::kWord32Shl) ||
1030 (node->opcode() == IrOpcode::kWord32Shr) ||
1031 (node->opcode() == IrOpcode::kWord32Sar));
1032 if (machine()->Word32ShiftIsSafe()) {
1033 // Remove the explicit 'and' with 0x1f if the shift provided by the machine
1034 // instruction matches that required by JavaScript.
1035 Int32BinopMatcher m(node);
1036 if (m.right().IsWord32And()) {
1037 Int32BinopMatcher mright(m.right().node());
1038 if (mright.right().Is(0x1f)) {
1039 node->ReplaceInput(1, mright.left().node());
1040 return Changed(node);
1041 }
1042 }
1043 }
1044 return NoChange();
1045 }
1046
1047
ReduceWord32Shl(Node * node)1048 Reduction MachineOperatorReducer::ReduceWord32Shl(Node* node) {
1049 DCHECK_EQ(IrOpcode::kWord32Shl, node->opcode());
1050 Int32BinopMatcher m(node);
1051 if (m.right().Is(0)) return Replace(m.left().node()); // x << 0 => x
1052 if (m.IsFoldable()) { // K << K => K
1053 return ReplaceInt32(m.left().Value() << m.right().Value());
1054 }
1055 if (m.right().IsInRange(1, 31)) {
1056 // (x >>> K) << K => x & ~(2^K - 1)
1057 // (x >> K) << K => x & ~(2^K - 1)
1058 if (m.left().IsWord32Sar() || m.left().IsWord32Shr()) {
1059 Int32BinopMatcher mleft(m.left().node());
1060 if (mleft.right().Is(m.right().Value())) {
1061 node->ReplaceInput(0, mleft.left().node());
1062 node->ReplaceInput(1,
1063 Uint32Constant(~((1U << m.right().Value()) - 1U)));
1064 NodeProperties::ChangeOp(node, machine()->Word32And());
1065 Reduction reduction = ReduceWord32And(node);
1066 return reduction.Changed() ? reduction : Changed(node);
1067 }
1068 }
1069 }
1070 return ReduceWord32Shifts(node);
1071 }
1072
ReduceWord64Shl(Node * node)1073 Reduction MachineOperatorReducer::ReduceWord64Shl(Node* node) {
1074 DCHECK_EQ(IrOpcode::kWord64Shl, node->opcode());
1075 Int64BinopMatcher m(node);
1076 if (m.right().Is(0)) return Replace(m.left().node()); // x << 0 => x
1077 if (m.IsFoldable()) { // K << K => K
1078 return ReplaceInt64(m.left().Value() << m.right().Value());
1079 }
1080 return NoChange();
1081 }
1082
ReduceWord32Shr(Node * node)1083 Reduction MachineOperatorReducer::ReduceWord32Shr(Node* node) {
1084 Uint32BinopMatcher m(node);
1085 if (m.right().Is(0)) return Replace(m.left().node()); // x >>> 0 => x
1086 if (m.IsFoldable()) { // K >>> K => K
1087 return ReplaceInt32(m.left().Value() >> m.right().Value());
1088 }
1089 if (m.left().IsWord32And() && m.right().HasValue()) {
1090 Uint32BinopMatcher mleft(m.left().node());
1091 if (mleft.right().HasValue()) {
1092 uint32_t shift = m.right().Value() & 0x1f;
1093 uint32_t mask = mleft.right().Value();
1094 if ((mask >> shift) == 0) {
1095 // (m >>> s) == 0 implies ((x & m) >>> s) == 0
1096 return ReplaceInt32(0);
1097 }
1098 }
1099 }
1100 return ReduceWord32Shifts(node);
1101 }
1102
ReduceWord64Shr(Node * node)1103 Reduction MachineOperatorReducer::ReduceWord64Shr(Node* node) {
1104 DCHECK_EQ(IrOpcode::kWord64Shr, node->opcode());
1105 Uint64BinopMatcher m(node);
1106 if (m.right().Is(0)) return Replace(m.left().node()); // x >>> 0 => x
1107 if (m.IsFoldable()) { // K >> K => K
1108 return ReplaceInt64(m.left().Value() >> m.right().Value());
1109 }
1110 return NoChange();
1111 }
1112
ReduceWord32Sar(Node * node)1113 Reduction MachineOperatorReducer::ReduceWord32Sar(Node* node) {
1114 Int32BinopMatcher m(node);
1115 if (m.right().Is(0)) return Replace(m.left().node()); // x >> 0 => x
1116 if (m.IsFoldable()) { // K >> K => K
1117 return ReplaceInt32(m.left().Value() >> m.right().Value());
1118 }
1119 if (m.left().IsWord32Shl()) {
1120 Int32BinopMatcher mleft(m.left().node());
1121 if (mleft.left().IsComparison()) {
1122 if (m.right().Is(31) && mleft.right().Is(31)) {
1123 // Comparison << 31 >> 31 => 0 - Comparison
1124 node->ReplaceInput(0, Int32Constant(0));
1125 node->ReplaceInput(1, mleft.left().node());
1126 NodeProperties::ChangeOp(node, machine()->Int32Sub());
1127 Reduction const reduction = ReduceInt32Sub(node);
1128 return reduction.Changed() ? reduction : Changed(node);
1129 }
1130 } else if (mleft.left().IsLoad()) {
1131 LoadRepresentation const rep =
1132 LoadRepresentationOf(mleft.left().node()->op());
1133 if (m.right().Is(24) && mleft.right().Is(24) &&
1134 rep == MachineType::Int8()) {
1135 // Load[kMachInt8] << 24 >> 24 => Load[kMachInt8]
1136 return Replace(mleft.left().node());
1137 }
1138 if (m.right().Is(16) && mleft.right().Is(16) &&
1139 rep == MachineType::Int16()) {
1140 // Load[kMachInt16] << 16 >> 16 => Load[kMachInt8]
1141 return Replace(mleft.left().node());
1142 }
1143 }
1144 }
1145 return ReduceWord32Shifts(node);
1146 }
1147
ReduceWord64Sar(Node * node)1148 Reduction MachineOperatorReducer::ReduceWord64Sar(Node* node) {
1149 Int64BinopMatcher m(node);
1150 if (m.right().Is(0)) return Replace(m.left().node()); // x >> 0 => x
1151 if (m.IsFoldable()) {
1152 return ReplaceInt64(m.left().Value() >> m.right().Value());
1153 }
1154 return NoChange();
1155 }
1156
ReduceWord32And(Node * node)1157 Reduction MachineOperatorReducer::ReduceWord32And(Node* node) {
1158 DCHECK_EQ(IrOpcode::kWord32And, node->opcode());
1159 Int32BinopMatcher m(node);
1160 if (m.right().Is(0)) return Replace(m.right().node()); // x & 0 => 0
1161 if (m.right().Is(-1)) return Replace(m.left().node()); // x & -1 => x
1162 if (m.left().IsComparison() && m.right().Is(1)) { // CMP & 1 => CMP
1163 return Replace(m.left().node());
1164 }
1165 if (m.IsFoldable()) { // K & K => K
1166 return ReplaceInt32(m.left().Value() & m.right().Value());
1167 }
1168 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x & x => x
1169 if (m.left().IsWord32And() && m.right().HasValue()) {
1170 Int32BinopMatcher mleft(m.left().node());
1171 if (mleft.right().HasValue()) { // (x & K) & K => x & K
1172 node->ReplaceInput(0, mleft.left().node());
1173 node->ReplaceInput(
1174 1, Int32Constant(m.right().Value() & mleft.right().Value()));
1175 Reduction const reduction = ReduceWord32And(node);
1176 return reduction.Changed() ? reduction : Changed(node);
1177 }
1178 }
1179 if (m.right().IsNegativePowerOf2()) {
1180 int32_t const mask = m.right().Value();
1181 if (m.left().IsWord32Shl()) {
1182 Uint32BinopMatcher mleft(m.left().node());
1183 if (mleft.right().HasValue() &&
1184 (mleft.right().Value() & 0x1f) >=
1185 base::bits::CountTrailingZeros32(mask)) {
1186 // (x << L) & (-1 << K) => x << L iff L >= K
1187 return Replace(mleft.node());
1188 }
1189 } else if (m.left().IsInt32Add()) {
1190 Int32BinopMatcher mleft(m.left().node());
1191 if (mleft.right().HasValue() &&
1192 (mleft.right().Value() & mask) == mleft.right().Value()) {
1193 // (x + (K << L)) & (-1 << L) => (x & (-1 << L)) + (K << L)
1194 node->ReplaceInput(0, Word32And(mleft.left().node(), m.right().node()));
1195 node->ReplaceInput(1, mleft.right().node());
1196 NodeProperties::ChangeOp(node, machine()->Int32Add());
1197 Reduction const reduction = ReduceInt32Add(node);
1198 return reduction.Changed() ? reduction : Changed(node);
1199 }
1200 if (mleft.left().IsInt32Mul()) {
1201 Int32BinopMatcher mleftleft(mleft.left().node());
1202 if (mleftleft.right().IsMultipleOf(-mask)) {
1203 // (y * (K << L) + x) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1204 node->ReplaceInput(0,
1205 Word32And(mleft.right().node(), m.right().node()));
1206 node->ReplaceInput(1, mleftleft.node());
1207 NodeProperties::ChangeOp(node, machine()->Int32Add());
1208 Reduction const reduction = ReduceInt32Add(node);
1209 return reduction.Changed() ? reduction : Changed(node);
1210 }
1211 }
1212 if (mleft.right().IsInt32Mul()) {
1213 Int32BinopMatcher mleftright(mleft.right().node());
1214 if (mleftright.right().IsMultipleOf(-mask)) {
1215 // (x + y * (K << L)) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1216 node->ReplaceInput(0,
1217 Word32And(mleft.left().node(), m.right().node()));
1218 node->ReplaceInput(1, mleftright.node());
1219 NodeProperties::ChangeOp(node, machine()->Int32Add());
1220 Reduction const reduction = ReduceInt32Add(node);
1221 return reduction.Changed() ? reduction : Changed(node);
1222 }
1223 }
1224 if (mleft.left().IsWord32Shl()) {
1225 Int32BinopMatcher mleftleft(mleft.left().node());
1226 if (mleftleft.right().Is(base::bits::CountTrailingZeros32(mask))) {
1227 // (y << L + x) & (-1 << L) => (x & (-1 << L)) + y << L
1228 node->ReplaceInput(0,
1229 Word32And(mleft.right().node(), m.right().node()));
1230 node->ReplaceInput(1, mleftleft.node());
1231 NodeProperties::ChangeOp(node, machine()->Int32Add());
1232 Reduction const reduction = ReduceInt32Add(node);
1233 return reduction.Changed() ? reduction : Changed(node);
1234 }
1235 }
1236 if (mleft.right().IsWord32Shl()) {
1237 Int32BinopMatcher mleftright(mleft.right().node());
1238 if (mleftright.right().Is(base::bits::CountTrailingZeros32(mask))) {
1239 // (x + y << L) & (-1 << L) => (x & (-1 << L)) + y << L
1240 node->ReplaceInput(0,
1241 Word32And(mleft.left().node(), m.right().node()));
1242 node->ReplaceInput(1, mleftright.node());
1243 NodeProperties::ChangeOp(node, machine()->Int32Add());
1244 Reduction const reduction = ReduceInt32Add(node);
1245 return reduction.Changed() ? reduction : Changed(node);
1246 }
1247 }
1248 } else if (m.left().IsInt32Mul()) {
1249 Int32BinopMatcher mleft(m.left().node());
1250 if (mleft.right().IsMultipleOf(-mask)) {
1251 // (x * (K << L)) & (-1 << L) => x * (K << L)
1252 return Replace(mleft.node());
1253 }
1254 }
1255 }
1256 return NoChange();
1257 }
1258
TryMatchWord32Ror(Node * node)1259 Reduction MachineOperatorReducer::TryMatchWord32Ror(Node* node) {
1260 DCHECK(IrOpcode::kWord32Or == node->opcode() ||
1261 IrOpcode::kWord32Xor == node->opcode());
1262 Int32BinopMatcher m(node);
1263 Node* shl = nullptr;
1264 Node* shr = nullptr;
1265 // Recognize rotation, we are matching:
1266 // * x << y | x >>> (32 - y) => x ror (32 - y), i.e x rol y
1267 // * x << (32 - y) | x >>> y => x ror y
1268 // * x << y ^ x >>> (32 - y) => x ror (32 - y), i.e. x rol y
1269 // * x << (32 - y) ^ x >>> y => x ror y
1270 // as well as their commuted form.
1271 if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) {
1272 shl = m.left().node();
1273 shr = m.right().node();
1274 } else if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) {
1275 shl = m.right().node();
1276 shr = m.left().node();
1277 } else {
1278 return NoChange();
1279 }
1280
1281 Int32BinopMatcher mshl(shl);
1282 Int32BinopMatcher mshr(shr);
1283 if (mshl.left().node() != mshr.left().node()) return NoChange();
1284
1285 if (mshl.right().HasValue() && mshr.right().HasValue()) {
1286 // Case where y is a constant.
1287 if (mshl.right().Value() + mshr.right().Value() != 32) return NoChange();
1288 } else {
1289 Node* sub = nullptr;
1290 Node* y = nullptr;
1291 if (mshl.right().IsInt32Sub()) {
1292 sub = mshl.right().node();
1293 y = mshr.right().node();
1294 } else if (mshr.right().IsInt32Sub()) {
1295 sub = mshr.right().node();
1296 y = mshl.right().node();
1297 } else {
1298 return NoChange();
1299 }
1300
1301 Int32BinopMatcher msub(sub);
1302 if (!msub.left().Is(32) || msub.right().node() != y) return NoChange();
1303 }
1304
1305 node->ReplaceInput(0, mshl.left().node());
1306 node->ReplaceInput(1, mshr.right().node());
1307 NodeProperties::ChangeOp(node, machine()->Word32Ror());
1308 return Changed(node);
1309 }
1310
ReduceWord32Or(Node * node)1311 Reduction MachineOperatorReducer::ReduceWord32Or(Node* node) {
1312 DCHECK_EQ(IrOpcode::kWord32Or, node->opcode());
1313 Int32BinopMatcher m(node);
1314 if (m.right().Is(0)) return Replace(m.left().node()); // x | 0 => x
1315 if (m.right().Is(-1)) return Replace(m.right().node()); // x | -1 => -1
1316 if (m.IsFoldable()) { // K | K => K
1317 return ReplaceInt32(m.left().Value() | m.right().Value());
1318 }
1319 if (m.LeftEqualsRight()) return Replace(m.left().node()); // x | x => x
1320
1321 return TryMatchWord32Ror(node);
1322 }
1323
ReduceWord32Xor(Node * node)1324 Reduction MachineOperatorReducer::ReduceWord32Xor(Node* node) {
1325 DCHECK_EQ(IrOpcode::kWord32Xor, node->opcode());
1326 Int32BinopMatcher m(node);
1327 if (m.right().Is(0)) return Replace(m.left().node()); // x ^ 0 => x
1328 if (m.IsFoldable()) { // K ^ K => K
1329 return ReplaceInt32(m.left().Value() ^ m.right().Value());
1330 }
1331 if (m.LeftEqualsRight()) return ReplaceInt32(0); // x ^ x => 0
1332 if (m.left().IsWord32Xor() && m.right().Is(-1)) {
1333 Int32BinopMatcher mleft(m.left().node());
1334 if (mleft.right().Is(-1)) { // (x ^ -1) ^ -1 => x
1335 return Replace(mleft.left().node());
1336 }
1337 }
1338
1339 return TryMatchWord32Ror(node);
1340 }
1341
ReduceFloat64InsertLowWord32(Node * node)1342 Reduction MachineOperatorReducer::ReduceFloat64InsertLowWord32(Node* node) {
1343 DCHECK_EQ(IrOpcode::kFloat64InsertLowWord32, node->opcode());
1344 Float64Matcher mlhs(node->InputAt(0));
1345 Uint32Matcher mrhs(node->InputAt(1));
1346 if (mlhs.HasValue() && mrhs.HasValue()) {
1347 return ReplaceFloat64(bit_cast<double>(
1348 (bit_cast<uint64_t>(mlhs.Value()) & V8_UINT64_C(0xFFFFFFFF00000000)) |
1349 mrhs.Value()));
1350 }
1351 return NoChange();
1352 }
1353
1354
ReduceFloat64InsertHighWord32(Node * node)1355 Reduction MachineOperatorReducer::ReduceFloat64InsertHighWord32(Node* node) {
1356 DCHECK_EQ(IrOpcode::kFloat64InsertHighWord32, node->opcode());
1357 Float64Matcher mlhs(node->InputAt(0));
1358 Uint32Matcher mrhs(node->InputAt(1));
1359 if (mlhs.HasValue() && mrhs.HasValue()) {
1360 return ReplaceFloat64(bit_cast<double>(
1361 (bit_cast<uint64_t>(mlhs.Value()) & V8_UINT64_C(0xFFFFFFFF)) |
1362 (static_cast<uint64_t>(mrhs.Value()) << 32)));
1363 }
1364 return NoChange();
1365 }
1366
1367
1368 namespace {
1369
IsFloat64RepresentableAsFloat32(const Float64Matcher & m)1370 bool IsFloat64RepresentableAsFloat32(const Float64Matcher& m) {
1371 if (m.HasValue()) {
1372 double v = m.Value();
1373 float fv = static_cast<float>(v);
1374 return static_cast<double>(fv) == v;
1375 }
1376 return false;
1377 }
1378
1379 } // namespace
1380
1381
ReduceFloat64Compare(Node * node)1382 Reduction MachineOperatorReducer::ReduceFloat64Compare(Node* node) {
1383 DCHECK((IrOpcode::kFloat64Equal == node->opcode()) ||
1384 (IrOpcode::kFloat64LessThan == node->opcode()) ||
1385 (IrOpcode::kFloat64LessThanOrEqual == node->opcode()));
1386 // As all Float32 values have an exact representation in Float64, comparing
1387 // two Float64 values both converted from Float32 is equivalent to comparing
1388 // the original Float32s, so we can ignore the conversions. We can also reduce
1389 // comparisons of converted Float64 values against constants that can be
1390 // represented exactly as Float32.
1391 Float64BinopMatcher m(node);
1392 if ((m.left().IsChangeFloat32ToFloat64() &&
1393 m.right().IsChangeFloat32ToFloat64()) ||
1394 (m.left().IsChangeFloat32ToFloat64() &&
1395 IsFloat64RepresentableAsFloat32(m.right())) ||
1396 (IsFloat64RepresentableAsFloat32(m.left()) &&
1397 m.right().IsChangeFloat32ToFloat64())) {
1398 switch (node->opcode()) {
1399 case IrOpcode::kFloat64Equal:
1400 NodeProperties::ChangeOp(node, machine()->Float32Equal());
1401 break;
1402 case IrOpcode::kFloat64LessThan:
1403 NodeProperties::ChangeOp(node, machine()->Float32LessThan());
1404 break;
1405 case IrOpcode::kFloat64LessThanOrEqual:
1406 NodeProperties::ChangeOp(node, machine()->Float32LessThanOrEqual());
1407 break;
1408 default:
1409 return NoChange();
1410 }
1411 node->ReplaceInput(
1412 0, m.left().HasValue()
1413 ? Float32Constant(static_cast<float>(m.left().Value()))
1414 : m.left().InputAt(0));
1415 node->ReplaceInput(
1416 1, m.right().HasValue()
1417 ? Float32Constant(static_cast<float>(m.right().Value()))
1418 : m.right().InputAt(0));
1419 return Changed(node);
1420 }
1421 return NoChange();
1422 }
1423
ReduceFloat64RoundDown(Node * node)1424 Reduction MachineOperatorReducer::ReduceFloat64RoundDown(Node* node) {
1425 DCHECK_EQ(IrOpcode::kFloat64RoundDown, node->opcode());
1426 Float64Matcher m(node->InputAt(0));
1427 if (m.HasValue()) {
1428 return ReplaceFloat64(Floor(m.Value()));
1429 }
1430 return NoChange();
1431 }
1432
common() const1433 CommonOperatorBuilder* MachineOperatorReducer::common() const {
1434 return jsgraph()->common();
1435 }
1436
1437
machine() const1438 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
1439 return jsgraph()->machine();
1440 }
1441
1442
graph() const1443 Graph* MachineOperatorReducer::graph() const { return jsgraph()->graph(); }
1444
1445 } // namespace compiler
1446 } // namespace internal
1447 } // namespace v8
1448