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