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/compiler/diamond.h"
11 #include "src/compiler/graph.h"
12 #include "src/compiler/machine-graph.h"
13 #include "src/compiler/node-matchers.h"
14 #include "src/compiler/node-properties.h"
15 #include "src/conversions-inl.h"
16 
17 namespace v8 {
18 namespace internal {
19 namespace compiler {
20 
MachineOperatorReducer(MachineGraph * mcgraph,bool allow_signalling_nan)21 MachineOperatorReducer::MachineOperatorReducer(MachineGraph* mcgraph,
22                                                bool allow_signalling_nan)
23     : mcgraph_(mcgraph), 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 mcgraph()->Float64Constant(value);
35 }
36 
37 
Int32Constant(int32_t value)38 Node* MachineOperatorReducer::Int32Constant(int32_t value) {
39   return mcgraph()->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::CountTrailingZeros(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.IsFoldable()) {  // K + K => K
357         return ReplaceFloat64(m.left().Value() + m.right().Value());
358       }
359       break;
360     }
361     case IrOpcode::kFloat64Sub: {
362       Float64BinopMatcher m(node);
363       if (allow_signalling_nan_ && m.right().Is(0) &&
364           (Double(m.right().Value()).Sign() > 0)) {
365         return Replace(m.left().node());  // x - 0 => x
366       }
367       if (m.right().IsNaN()) {  // x - NaN => NaN
368         // Do some calculation to make a signalling NaN quiet.
369         return ReplaceFloat64(m.right().Value() - m.right().Value());
370       }
371       if (m.left().IsNaN()) {  // NaN - x => NaN
372         // Do some calculation to make a signalling NaN quiet.
373         return ReplaceFloat64(m.left().Value() - m.left().Value());
374       }
375       if (m.IsFoldable()) {  // L - R => (L - R)
376         return ReplaceFloat64(m.left().Value() - m.right().Value());
377       }
378       if (allow_signalling_nan_ && m.left().IsMinusZero()) {
379         // -0.0 - round_down(-0.0 - R) => round_up(R)
380         if (machine()->Float64RoundUp().IsSupported() &&
381             m.right().IsFloat64RoundDown()) {
382           if (m.right().InputAt(0)->opcode() == IrOpcode::kFloat64Sub) {
383             Float64BinopMatcher mright0(m.right().InputAt(0));
384             if (mright0.left().IsMinusZero()) {
385               return Replace(graph()->NewNode(machine()->Float64RoundUp().op(),
386                                               mright0.right().node()));
387             }
388           }
389         }
390         // -0.0 - R => -R
391         node->RemoveInput(0);
392         NodeProperties::ChangeOp(node, machine()->Float64Neg());
393         return Changed(node);
394       }
395       break;
396     }
397     case IrOpcode::kFloat64Mul: {
398       Float64BinopMatcher m(node);
399       if (allow_signalling_nan_ && m.right().Is(1))
400         return Replace(m.left().node());  // x * 1.0 => x
401       if (m.right().Is(-1)) {  // x * -1.0 => -0.0 - x
402         node->ReplaceInput(0, Float64Constant(-0.0));
403         node->ReplaceInput(1, m.left().node());
404         NodeProperties::ChangeOp(node, machine()->Float64Sub());
405         return Changed(node);
406       }
407       if (m.right().IsNaN()) {                               // x * NaN => NaN
408         // Do some calculation to make a signalling NaN quiet.
409         return ReplaceFloat64(m.right().Value() - m.right().Value());
410       }
411       if (m.IsFoldable()) {  // K * K => K
412         return ReplaceFloat64(m.left().Value() * m.right().Value());
413       }
414       if (m.right().Is(2)) {  // x * 2.0 => x + x
415         node->ReplaceInput(1, m.left().node());
416         NodeProperties::ChangeOp(node, machine()->Float64Add());
417         return Changed(node);
418       }
419       break;
420     }
421     case IrOpcode::kFloat64Div: {
422       Float64BinopMatcher m(node);
423       if (allow_signalling_nan_ && m.right().Is(1))
424         return Replace(m.left().node());  // x / 1.0 => x
425       // TODO(ahaas): We could do x / 1.0 = x if we knew that x is not an sNaN.
426       if (m.right().IsNaN()) {                               // x / NaN => NaN
427         // Do some calculation to make a signalling NaN quiet.
428         return ReplaceFloat64(m.right().Value() - m.right().Value());
429       }
430       if (m.left().IsNaN()) {  // NaN / x => NaN
431         // Do some calculation to make a signalling NaN quiet.
432         return ReplaceFloat64(m.left().Value() - m.left().Value());
433       }
434       if (m.IsFoldable()) {  // K / K => K
435         return ReplaceFloat64(m.left().Value() / m.right().Value());
436       }
437       if (allow_signalling_nan_ && m.right().Is(-1)) {  // x / -1.0 => -x
438         node->RemoveInput(1);
439         NodeProperties::ChangeOp(node, machine()->Float64Neg());
440         return Changed(node);
441       }
442       if (m.right().IsNormal() && m.right().IsPositiveOrNegativePowerOf2()) {
443         // All reciprocals of non-denormal powers of two can be represented
444         // exactly, so division by power of two can be reduced to
445         // multiplication by reciprocal, with the same result.
446         node->ReplaceInput(1, Float64Constant(1.0 / m.right().Value()));
447         NodeProperties::ChangeOp(node, machine()->Float64Mul());
448         return Changed(node);
449       }
450       break;
451     }
452     case IrOpcode::kFloat64Mod: {
453       Float64BinopMatcher m(node);
454       if (m.right().Is(0)) {  // x % 0 => NaN
455         return ReplaceFloat64(std::numeric_limits<double>::quiet_NaN());
456       }
457       if (m.right().IsNaN()) {  // x % NaN => NaN
458         return Replace(m.right().node());
459       }
460       if (m.left().IsNaN()) {  // NaN % x => NaN
461         return Replace(m.left().node());
462       }
463       if (m.IsFoldable()) {  // K % K => K
464         return ReplaceFloat64(Modulo(m.left().Value(), m.right().Value()));
465       }
466       break;
467     }
468     case IrOpcode::kFloat64Acos: {
469       Float64Matcher m(node->InputAt(0));
470       if (m.HasValue()) return ReplaceFloat64(base::ieee754::acos(m.Value()));
471       break;
472     }
473     case IrOpcode::kFloat64Acosh: {
474       Float64Matcher m(node->InputAt(0));
475       if (m.HasValue()) return ReplaceFloat64(base::ieee754::acosh(m.Value()));
476       break;
477     }
478     case IrOpcode::kFloat64Asin: {
479       Float64Matcher m(node->InputAt(0));
480       if (m.HasValue()) return ReplaceFloat64(base::ieee754::asin(m.Value()));
481       break;
482     }
483     case IrOpcode::kFloat64Asinh: {
484       Float64Matcher m(node->InputAt(0));
485       if (m.HasValue()) return ReplaceFloat64(base::ieee754::asinh(m.Value()));
486       break;
487     }
488     case IrOpcode::kFloat64Atan: {
489       Float64Matcher m(node->InputAt(0));
490       if (m.HasValue()) return ReplaceFloat64(base::ieee754::atan(m.Value()));
491       break;
492     }
493     case IrOpcode::kFloat64Atanh: {
494       Float64Matcher m(node->InputAt(0));
495       if (m.HasValue()) return ReplaceFloat64(base::ieee754::atanh(m.Value()));
496       break;
497     }
498     case IrOpcode::kFloat64Atan2: {
499       Float64BinopMatcher m(node);
500       if (m.right().IsNaN()) {
501         return Replace(m.right().node());
502       }
503       if (m.left().IsNaN()) {
504         return Replace(m.left().node());
505       }
506       if (m.IsFoldable()) {
507         return ReplaceFloat64(
508             base::ieee754::atan2(m.left().Value(), m.right().Value()));
509       }
510       break;
511     }
512     case IrOpcode::kFloat64Cbrt: {
513       Float64Matcher m(node->InputAt(0));
514       if (m.HasValue()) return ReplaceFloat64(base::ieee754::cbrt(m.Value()));
515       break;
516     }
517     case IrOpcode::kFloat64Cos: {
518       Float64Matcher m(node->InputAt(0));
519       if (m.HasValue()) return ReplaceFloat64(base::ieee754::cos(m.Value()));
520       break;
521     }
522     case IrOpcode::kFloat64Cosh: {
523       Float64Matcher m(node->InputAt(0));
524       if (m.HasValue()) return ReplaceFloat64(base::ieee754::cosh(m.Value()));
525       break;
526     }
527     case IrOpcode::kFloat64Exp: {
528       Float64Matcher m(node->InputAt(0));
529       if (m.HasValue()) return ReplaceFloat64(base::ieee754::exp(m.Value()));
530       break;
531     }
532     case IrOpcode::kFloat64Expm1: {
533       Float64Matcher m(node->InputAt(0));
534       if (m.HasValue()) return ReplaceFloat64(base::ieee754::expm1(m.Value()));
535       break;
536     }
537     case IrOpcode::kFloat64Log: {
538       Float64Matcher m(node->InputAt(0));
539       if (m.HasValue()) return ReplaceFloat64(base::ieee754::log(m.Value()));
540       break;
541     }
542     case IrOpcode::kFloat64Log1p: {
543       Float64Matcher m(node->InputAt(0));
544       if (m.HasValue()) return ReplaceFloat64(base::ieee754::log1p(m.Value()));
545       break;
546     }
547     case IrOpcode::kFloat64Log10: {
548       Float64Matcher m(node->InputAt(0));
549       if (m.HasValue()) return ReplaceFloat64(base::ieee754::log10(m.Value()));
550       break;
551     }
552     case IrOpcode::kFloat64Log2: {
553       Float64Matcher m(node->InputAt(0));
554       if (m.HasValue()) return ReplaceFloat64(base::ieee754::log2(m.Value()));
555       break;
556     }
557     case IrOpcode::kFloat64Pow: {
558       Float64BinopMatcher m(node);
559       if (m.IsFoldable()) {
560         return ReplaceFloat64(Pow(m.left().Value(), m.right().Value()));
561       } else if (m.right().Is(0.0)) {  // x ** +-0.0 => 1.0
562         return ReplaceFloat64(1.0);
563       } else if (m.right().Is(-2.0)) {  // x ** -2.0 => 1 / (x * x)
564         node->ReplaceInput(0, Float64Constant(1.0));
565         node->ReplaceInput(1, Float64Mul(m.left().node(), m.left().node()));
566         NodeProperties::ChangeOp(node, machine()->Float64Div());
567         return Changed(node);
568       } else if (m.right().Is(2.0)) {  // x ** 2.0 => x * x
569         node->ReplaceInput(1, m.left().node());
570         NodeProperties::ChangeOp(node, machine()->Float64Mul());
571         return Changed(node);
572       } else if (m.right().Is(-0.5)) {
573         // x ** 0.5 => 1 / (if x <= -Infinity then Infinity else sqrt(0.0 + x))
574         node->ReplaceInput(0, Float64Constant(1.0));
575         node->ReplaceInput(1, Float64PowHalf(m.left().node()));
576         NodeProperties::ChangeOp(node, machine()->Float64Div());
577         return Changed(node);
578       } else if (m.right().Is(0.5)) {
579         // x ** 0.5 => if x <= -Infinity then Infinity else sqrt(0.0 + x)
580         return Replace(Float64PowHalf(m.left().node()));
581       }
582       break;
583     }
584     case IrOpcode::kFloat64Sin: {
585       Float64Matcher m(node->InputAt(0));
586       if (m.HasValue()) return ReplaceFloat64(base::ieee754::sin(m.Value()));
587       break;
588     }
589     case IrOpcode::kFloat64Sinh: {
590       Float64Matcher m(node->InputAt(0));
591       if (m.HasValue()) return ReplaceFloat64(base::ieee754::sinh(m.Value()));
592       break;
593     }
594     case IrOpcode::kFloat64Tan: {
595       Float64Matcher m(node->InputAt(0));
596       if (m.HasValue()) return ReplaceFloat64(base::ieee754::tan(m.Value()));
597       break;
598     }
599     case IrOpcode::kFloat64Tanh: {
600       Float64Matcher m(node->InputAt(0));
601       if (m.HasValue()) return ReplaceFloat64(base::ieee754::tanh(m.Value()));
602       break;
603     }
604     case IrOpcode::kChangeFloat32ToFloat64: {
605       Float32Matcher m(node->InputAt(0));
606       if (m.HasValue()) {
607         if (!allow_signalling_nan_ && std::isnan(m.Value())) {
608           // Do some calculation to make guarantee the value is a quiet NaN.
609           return ReplaceFloat64(m.Value() + m.Value());
610         }
611         return ReplaceFloat64(m.Value());
612       }
613       break;
614     }
615     case IrOpcode::kChangeFloat64ToInt32: {
616       Float64Matcher m(node->InputAt(0));
617       if (m.HasValue()) return ReplaceInt32(FastD2IChecked(m.Value()));
618       if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
619       break;
620     }
621     case IrOpcode::kChangeFloat64ToUint32: {
622       Float64Matcher m(node->InputAt(0));
623       if (m.HasValue()) return ReplaceInt32(FastD2UI(m.Value()));
624       if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0));
625       break;
626     }
627     case IrOpcode::kChangeInt32ToFloat64: {
628       Int32Matcher m(node->InputAt(0));
629       if (m.HasValue()) return ReplaceFloat64(FastI2D(m.Value()));
630       break;
631     }
632     case IrOpcode::kChangeInt32ToInt64: {
633       Int32Matcher m(node->InputAt(0));
634       if (m.HasValue()) return ReplaceInt64(m.Value());
635       break;
636     }
637     case IrOpcode::kChangeUint32ToFloat64: {
638       Uint32Matcher m(node->InputAt(0));
639       if (m.HasValue()) return ReplaceFloat64(FastUI2D(m.Value()));
640       break;
641     }
642     case IrOpcode::kChangeUint32ToUint64: {
643       Uint32Matcher m(node->InputAt(0));
644       if (m.HasValue()) return ReplaceInt64(static_cast<uint64_t>(m.Value()));
645       break;
646     }
647     case IrOpcode::kTruncateFloat64ToWord32: {
648       Float64Matcher m(node->InputAt(0));
649       if (m.HasValue()) return ReplaceInt32(DoubleToInt32(m.Value()));
650       if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
651       return NoChange();
652     }
653     case IrOpcode::kTruncateInt64ToInt32: {
654       Int64Matcher m(node->InputAt(0));
655       if (m.HasValue()) return ReplaceInt32(static_cast<int32_t>(m.Value()));
656       if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
657       break;
658     }
659     case IrOpcode::kTruncateFloat64ToFloat32: {
660       Float64Matcher m(node->InputAt(0));
661       if (m.HasValue()) {
662         if (!allow_signalling_nan_ && std::isnan(m.Value())) {
663           // Do some calculation to make guarantee the value is a quiet NaN.
664           return ReplaceFloat32(DoubleToFloat32(m.Value() + m.Value()));
665         }
666         return ReplaceFloat32(DoubleToFloat32(m.Value()));
667       }
668       if (allow_signalling_nan_ && m.IsChangeFloat32ToFloat64())
669         return Replace(m.node()->InputAt(0));
670       break;
671     }
672     case IrOpcode::kRoundFloat64ToInt32: {
673       Float64Matcher m(node->InputAt(0));
674       if (m.HasValue()) {
675         return ReplaceInt32(DoubleToInt32(m.Value()));
676       }
677       if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
678       break;
679     }
680     case IrOpcode::kFloat64InsertLowWord32:
681       return ReduceFloat64InsertLowWord32(node);
682     case IrOpcode::kFloat64InsertHighWord32:
683       return ReduceFloat64InsertHighWord32(node);
684     case IrOpcode::kStore:
685     case IrOpcode::kUnalignedStore:
686       return ReduceStore(node);
687     case IrOpcode::kFloat64Equal:
688     case IrOpcode::kFloat64LessThan:
689     case IrOpcode::kFloat64LessThanOrEqual:
690       return ReduceFloat64Compare(node);
691     case IrOpcode::kFloat64RoundDown:
692       return ReduceFloat64RoundDown(node);
693     default:
694       break;
695   }
696   return NoChange();
697 }
698 
ReduceInt32Add(Node * node)699 Reduction MachineOperatorReducer::ReduceInt32Add(Node* node) {
700   DCHECK_EQ(IrOpcode::kInt32Add, node->opcode());
701   Int32BinopMatcher m(node);
702   if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => x
703   if (m.IsFoldable()) {                                  // K + K => K
704     return ReplaceUint32(bit_cast<uint32_t>(m.left().Value()) +
705                          bit_cast<uint32_t>(m.right().Value()));
706   }
707   if (m.left().IsInt32Sub()) {
708     Int32BinopMatcher mleft(m.left().node());
709     if (mleft.left().Is(0)) {  // (0 - x) + y => y - x
710       node->ReplaceInput(0, m.right().node());
711       node->ReplaceInput(1, mleft.right().node());
712       NodeProperties::ChangeOp(node, machine()->Int32Sub());
713       Reduction const reduction = ReduceInt32Sub(node);
714       return reduction.Changed() ? reduction : Changed(node);
715     }
716   }
717   if (m.right().IsInt32Sub()) {
718     Int32BinopMatcher mright(m.right().node());
719     if (mright.left().Is(0)) {  // y + (0 - x) => y - x
720       node->ReplaceInput(1, mright.right().node());
721       NodeProperties::ChangeOp(node, machine()->Int32Sub());
722       Reduction const reduction = ReduceInt32Sub(node);
723       return reduction.Changed() ? reduction : Changed(node);
724     }
725   }
726   return NoChange();
727 }
728 
ReduceInt64Add(Node * node)729 Reduction MachineOperatorReducer::ReduceInt64Add(Node* node) {
730   DCHECK_EQ(IrOpcode::kInt64Add, node->opcode());
731   Int64BinopMatcher m(node);
732   if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => 0
733   if (m.IsFoldable()) {
734     return Replace(Uint64Constant(bit_cast<uint64_t>(m.left().Value()) +
735                                   bit_cast<uint64_t>(m.right().Value())));
736   }
737   return NoChange();
738 }
739 
ReduceInt32Sub(Node * node)740 Reduction MachineOperatorReducer::ReduceInt32Sub(Node* node) {
741   DCHECK_EQ(IrOpcode::kInt32Sub, node->opcode());
742   Int32BinopMatcher m(node);
743   if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
744   if (m.IsFoldable()) {                                  // K - K => K
745     return ReplaceInt32(static_cast<uint32_t>(m.left().Value()) -
746                         static_cast<uint32_t>(m.right().Value()));
747   }
748   if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x - x => 0
749   if (m.right().HasValue()) {                       // x - K => x + -K
750     node->ReplaceInput(1, Int32Constant(-m.right().Value()));
751     NodeProperties::ChangeOp(node, machine()->Int32Add());
752     Reduction const reduction = ReduceInt32Add(node);
753     return reduction.Changed() ? reduction : Changed(node);
754   }
755   return NoChange();
756 }
757 
ReduceInt64Sub(Node * node)758 Reduction MachineOperatorReducer::ReduceInt64Sub(Node* node) {
759   DCHECK_EQ(IrOpcode::kInt64Sub, node->opcode());
760   Int64BinopMatcher m(node);
761   if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
762   if (m.IsFoldable()) {                                  // K - K => K
763     return Replace(Uint64Constant(bit_cast<uint64_t>(m.left().Value()) -
764                                   bit_cast<uint64_t>(m.right().Value())));
765   }
766   if (m.LeftEqualsRight()) return Replace(Int64Constant(0));  // x - x => 0
767   if (m.right().HasValue()) {                                 // x - K => x + -K
768     node->ReplaceInput(1, Int64Constant(-m.right().Value()));
769     NodeProperties::ChangeOp(node, machine()->Int64Add());
770     Reduction const reduction = ReduceInt64Add(node);
771     return reduction.Changed() ? reduction : Changed(node);
772   }
773   return NoChange();
774 }
775 
ReduceInt32Div(Node * node)776 Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
777   Int32BinopMatcher m(node);
778   if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
779   if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
780   if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
781   if (m.IsFoldable()) {                                   // K / K => K
782     return ReplaceInt32(
783         base::bits::SignedDiv32(m.left().Value(), m.right().Value()));
784   }
785   if (m.LeftEqualsRight()) {  // x / x => x != 0
786     Node* const zero = Int32Constant(0);
787     return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
788   }
789   if (m.right().Is(-1)) {  // x / -1 => 0 - x
790     node->ReplaceInput(0, Int32Constant(0));
791     node->ReplaceInput(1, m.left().node());
792     node->TrimInputCount(2);
793     NodeProperties::ChangeOp(node, machine()->Int32Sub());
794     return Changed(node);
795   }
796   if (m.right().HasValue()) {
797     int32_t const divisor = m.right().Value();
798     Node* const dividend = m.left().node();
799     Node* quotient = dividend;
800     if (base::bits::IsPowerOfTwo(Abs(divisor))) {
801       uint32_t const shift = WhichPowerOf2(Abs(divisor));
802       DCHECK_NE(0u, shift);
803       if (shift > 1) {
804         quotient = Word32Sar(quotient, 31);
805       }
806       quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend);
807       quotient = Word32Sar(quotient, shift);
808     } else {
809       quotient = Int32Div(quotient, Abs(divisor));
810     }
811     if (divisor < 0) {
812       node->ReplaceInput(0, Int32Constant(0));
813       node->ReplaceInput(1, quotient);
814       node->TrimInputCount(2);
815       NodeProperties::ChangeOp(node, machine()->Int32Sub());
816       return Changed(node);
817     }
818     return Replace(quotient);
819   }
820   return NoChange();
821 }
822 
823 
ReduceUint32Div(Node * node)824 Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) {
825   Uint32BinopMatcher m(node);
826   if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
827   if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
828   if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
829   if (m.IsFoldable()) {                                   // K / K => K
830     return ReplaceUint32(
831         base::bits::UnsignedDiv32(m.left().Value(), m.right().Value()));
832   }
833   if (m.LeftEqualsRight()) {  // x / x => x != 0
834     Node* const zero = Int32Constant(0);
835     return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
836   }
837   if (m.right().HasValue()) {
838     Node* const dividend = m.left().node();
839     uint32_t const divisor = m.right().Value();
840     if (base::bits::IsPowerOfTwo(divisor)) {  // x / 2^n => x >> n
841       node->ReplaceInput(1, Uint32Constant(WhichPowerOf2(m.right().Value())));
842       node->TrimInputCount(2);
843       NodeProperties::ChangeOp(node, machine()->Word32Shr());
844       return Changed(node);
845     } else {
846       return Replace(Uint32Div(dividend, divisor));
847     }
848   }
849   return NoChange();
850 }
851 
852 
ReduceInt32Mod(Node * node)853 Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
854   Int32BinopMatcher m(node);
855   if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x  => 0
856   if (m.right().Is(0)) return Replace(m.right().node());  // x % 0  => 0
857   if (m.right().Is(1)) return ReplaceInt32(0);            // x % 1  => 0
858   if (m.right().Is(-1)) return ReplaceInt32(0);           // x % -1 => 0
859   if (m.LeftEqualsRight()) return ReplaceInt32(0);        // x % x  => 0
860   if (m.IsFoldable()) {                                   // K % K => K
861     return ReplaceInt32(
862         base::bits::SignedMod32(m.left().Value(), m.right().Value()));
863   }
864   if (m.right().HasValue()) {
865     Node* const dividend = m.left().node();
866     uint32_t const divisor = Abs(m.right().Value());
867     if (base::bits::IsPowerOfTwo(divisor)) {
868       uint32_t const mask = divisor - 1;
869       Node* const zero = Int32Constant(0);
870       Diamond d(graph(), common(),
871                 graph()->NewNode(machine()->Int32LessThan(), dividend, zero),
872                 BranchHint::kFalse);
873       return Replace(
874           d.Phi(MachineRepresentation::kWord32,
875                 Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)),
876                 Word32And(dividend, mask)));
877     } else {
878       Node* quotient = Int32Div(dividend, divisor);
879       DCHECK_EQ(dividend, node->InputAt(0));
880       node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
881       node->TrimInputCount(2);
882       NodeProperties::ChangeOp(node, machine()->Int32Sub());
883     }
884     return Changed(node);
885   }
886   return NoChange();
887 }
888 
889 
ReduceUint32Mod(Node * node)890 Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) {
891   Uint32BinopMatcher m(node);
892   if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x => 0
893   if (m.right().Is(0)) return Replace(m.right().node());  // x % 0 => 0
894   if (m.right().Is(1)) return ReplaceUint32(0);           // x % 1 => 0
895   if (m.LeftEqualsRight()) return ReplaceInt32(0);        // x % x  => 0
896   if (m.IsFoldable()) {                                   // K % K => K
897     return ReplaceUint32(
898         base::bits::UnsignedMod32(m.left().Value(), m.right().Value()));
899   }
900   if (m.right().HasValue()) {
901     Node* const dividend = m.left().node();
902     uint32_t const divisor = m.right().Value();
903     if (base::bits::IsPowerOfTwo(divisor)) {  // x % 2^n => x & 2^n-1
904       node->ReplaceInput(1, Uint32Constant(m.right().Value() - 1));
905       node->TrimInputCount(2);
906       NodeProperties::ChangeOp(node, machine()->Word32And());
907     } else {
908       Node* quotient = Uint32Div(dividend, divisor);
909       DCHECK_EQ(dividend, node->InputAt(0));
910       node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor)));
911       node->TrimInputCount(2);
912       NodeProperties::ChangeOp(node, machine()->Int32Sub());
913     }
914     return Changed(node);
915   }
916   return NoChange();
917 }
918 
919 
ReduceStore(Node * node)920 Reduction MachineOperatorReducer::ReduceStore(Node* node) {
921   NodeMatcher nm(node);
922   MachineRepresentation rep;
923   int value_input;
924   if (nm.IsStore()) {
925     rep = StoreRepresentationOf(node->op()).representation();
926     value_input = 2;
927   } else {
928     DCHECK(nm.IsUnalignedStore());
929     rep = UnalignedStoreRepresentationOf(node->op());
930     value_input = 2;
931   }
932 
933   Node* const value = node->InputAt(value_input);
934 
935   switch (value->opcode()) {
936     case IrOpcode::kWord32And: {
937       Uint32BinopMatcher m(value);
938       if (m.right().HasValue() && ((rep == MachineRepresentation::kWord8 &&
939                                     (m.right().Value() & 0xFF) == 0xFF) ||
940                                    (rep == MachineRepresentation::kWord16 &&
941                                     (m.right().Value() & 0xFFFF) == 0xFFFF))) {
942         node->ReplaceInput(value_input, m.left().node());
943         return Changed(node);
944       }
945       break;
946     }
947     case IrOpcode::kWord32Sar: {
948       Int32BinopMatcher m(value);
949       if (m.left().IsWord32Shl() && ((rep == MachineRepresentation::kWord8 &&
950                                       m.right().IsInRange(1, 24)) ||
951                                      (rep == MachineRepresentation::kWord16 &&
952                                       m.right().IsInRange(1, 16)))) {
953         Int32BinopMatcher mleft(m.left().node());
954         if (mleft.right().Is(m.right().Value())) {
955           node->ReplaceInput(value_input, mleft.left().node());
956           return Changed(node);
957         }
958       }
959       break;
960     }
961     default:
962       break;
963   }
964   return NoChange();
965 }
966 
967 
ReduceProjection(size_t index,Node * node)968 Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
969   switch (node->opcode()) {
970     case IrOpcode::kInt32AddWithOverflow: {
971       DCHECK(index == 0 || index == 1);
972       Int32BinopMatcher m(node);
973       if (m.IsFoldable()) {
974         int32_t val;
975         bool ovf = base::bits::SignedAddOverflow32(m.left().Value(),
976                                                    m.right().Value(), &val);
977         return ReplaceInt32(index == 0 ? val : ovf);
978       }
979       if (m.right().Is(0)) {
980         return Replace(index == 0 ? m.left().node() : m.right().node());
981       }
982       break;
983     }
984     case IrOpcode::kInt32SubWithOverflow: {
985       DCHECK(index == 0 || index == 1);
986       Int32BinopMatcher m(node);
987       if (m.IsFoldable()) {
988         int32_t val;
989         bool ovf = base::bits::SignedSubOverflow32(m.left().Value(),
990                                                    m.right().Value(), &val);
991         return ReplaceInt32(index == 0 ? val : ovf);
992       }
993       if (m.right().Is(0)) {
994         return Replace(index == 0 ? m.left().node() : m.right().node());
995       }
996       break;
997     }
998     case IrOpcode::kInt32MulWithOverflow: {
999       DCHECK(index == 0 || index == 1);
1000       Int32BinopMatcher m(node);
1001       if (m.IsFoldable()) {
1002         int32_t val;
1003         bool ovf = base::bits::SignedMulOverflow32(m.left().Value(),
1004                                                    m.right().Value(), &val);
1005         return ReplaceInt32(index == 0 ? val : ovf);
1006       }
1007       if (m.right().Is(0)) {
1008         return Replace(m.right().node());
1009       }
1010       if (m.right().Is(1)) {
1011         return index == 0 ? Replace(m.left().node()) : ReplaceInt32(0);
1012       }
1013       break;
1014     }
1015     default:
1016       break;
1017   }
1018   return NoChange();
1019 }
1020 
1021 
ReduceWord32Shifts(Node * node)1022 Reduction MachineOperatorReducer::ReduceWord32Shifts(Node* node) {
1023   DCHECK((node->opcode() == IrOpcode::kWord32Shl) ||
1024          (node->opcode() == IrOpcode::kWord32Shr) ||
1025          (node->opcode() == IrOpcode::kWord32Sar));
1026   if (machine()->Word32ShiftIsSafe()) {
1027     // Remove the explicit 'and' with 0x1F if the shift provided by the machine
1028     // instruction matches that required by JavaScript.
1029     Int32BinopMatcher m(node);
1030     if (m.right().IsWord32And()) {
1031       Int32BinopMatcher mright(m.right().node());
1032       if (mright.right().Is(0x1F)) {
1033         node->ReplaceInput(1, mright.left().node());
1034         return Changed(node);
1035       }
1036     }
1037   }
1038   return NoChange();
1039 }
1040 
1041 
ReduceWord32Shl(Node * node)1042 Reduction MachineOperatorReducer::ReduceWord32Shl(Node* node) {
1043   DCHECK_EQ(IrOpcode::kWord32Shl, node->opcode());
1044   Int32BinopMatcher m(node);
1045   if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
1046   if (m.IsFoldable()) {                                  // K << K => K
1047     return ReplaceInt32(m.left().Value() << m.right().Value());
1048   }
1049   if (m.right().IsInRange(1, 31)) {
1050     // (x >>> K) << K => x & ~(2^K - 1)
1051     // (x >> K) << K => x & ~(2^K - 1)
1052     if (m.left().IsWord32Sar() || m.left().IsWord32Shr()) {
1053       Int32BinopMatcher mleft(m.left().node());
1054       if (mleft.right().Is(m.right().Value())) {
1055         node->ReplaceInput(0, mleft.left().node());
1056         node->ReplaceInput(1,
1057                            Uint32Constant(~((1U << m.right().Value()) - 1U)));
1058         NodeProperties::ChangeOp(node, machine()->Word32And());
1059         Reduction reduction = ReduceWord32And(node);
1060         return reduction.Changed() ? reduction : Changed(node);
1061       }
1062     }
1063   }
1064   return ReduceWord32Shifts(node);
1065 }
1066 
ReduceWord64Shl(Node * node)1067 Reduction MachineOperatorReducer::ReduceWord64Shl(Node* node) {
1068   DCHECK_EQ(IrOpcode::kWord64Shl, node->opcode());
1069   Int64BinopMatcher m(node);
1070   if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
1071   if (m.IsFoldable()) {                                  // K << K => K
1072     return ReplaceInt64(m.left().Value() << m.right().Value());
1073   }
1074   return NoChange();
1075 }
1076 
ReduceWord32Shr(Node * node)1077 Reduction MachineOperatorReducer::ReduceWord32Shr(Node* node) {
1078   Uint32BinopMatcher m(node);
1079   if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
1080   if (m.IsFoldable()) {                                  // K >>> K => K
1081     return ReplaceInt32(m.left().Value() >> m.right().Value());
1082   }
1083   if (m.left().IsWord32And() && m.right().HasValue()) {
1084     Uint32BinopMatcher mleft(m.left().node());
1085     if (mleft.right().HasValue()) {
1086       uint32_t shift = m.right().Value() & 0x1F;
1087       uint32_t mask = mleft.right().Value();
1088       if ((mask >> shift) == 0) {
1089         // (m >>> s) == 0 implies ((x & m) >>> s) == 0
1090         return ReplaceInt32(0);
1091       }
1092     }
1093   }
1094   return ReduceWord32Shifts(node);
1095 }
1096 
ReduceWord64Shr(Node * node)1097 Reduction MachineOperatorReducer::ReduceWord64Shr(Node* node) {
1098   DCHECK_EQ(IrOpcode::kWord64Shr, node->opcode());
1099   Uint64BinopMatcher m(node);
1100   if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
1101   if (m.IsFoldable()) {                                  // K >> K => K
1102     return ReplaceInt64(m.left().Value() >> m.right().Value());
1103   }
1104   return NoChange();
1105 }
1106 
ReduceWord32Sar(Node * node)1107 Reduction MachineOperatorReducer::ReduceWord32Sar(Node* node) {
1108   Int32BinopMatcher m(node);
1109   if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
1110   if (m.IsFoldable()) {                                  // K >> K => K
1111     return ReplaceInt32(m.left().Value() >> m.right().Value());
1112   }
1113   if (m.left().IsWord32Shl()) {
1114     Int32BinopMatcher mleft(m.left().node());
1115     if (mleft.left().IsComparison()) {
1116       if (m.right().Is(31) && mleft.right().Is(31)) {
1117         // Comparison << 31 >> 31 => 0 - Comparison
1118         node->ReplaceInput(0, Int32Constant(0));
1119         node->ReplaceInput(1, mleft.left().node());
1120         NodeProperties::ChangeOp(node, machine()->Int32Sub());
1121         Reduction const reduction = ReduceInt32Sub(node);
1122         return reduction.Changed() ? reduction : Changed(node);
1123       }
1124     } else if (mleft.left().IsLoad()) {
1125       LoadRepresentation const rep =
1126           LoadRepresentationOf(mleft.left().node()->op());
1127       if (m.right().Is(24) && mleft.right().Is(24) &&
1128           rep == MachineType::Int8()) {
1129         // Load[kMachInt8] << 24 >> 24 => Load[kMachInt8]
1130         return Replace(mleft.left().node());
1131       }
1132       if (m.right().Is(16) && mleft.right().Is(16) &&
1133           rep == MachineType::Int16()) {
1134         // Load[kMachInt16] << 16 >> 16 => Load[kMachInt8]
1135         return Replace(mleft.left().node());
1136       }
1137     }
1138   }
1139   return ReduceWord32Shifts(node);
1140 }
1141 
ReduceWord64Sar(Node * node)1142 Reduction MachineOperatorReducer::ReduceWord64Sar(Node* node) {
1143   Int64BinopMatcher m(node);
1144   if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
1145   if (m.IsFoldable()) {
1146     return ReplaceInt64(m.left().Value() >> m.right().Value());
1147   }
1148   return NoChange();
1149 }
1150 
ReduceWord32And(Node * node)1151 Reduction MachineOperatorReducer::ReduceWord32And(Node* node) {
1152   DCHECK_EQ(IrOpcode::kWord32And, node->opcode());
1153   Int32BinopMatcher m(node);
1154   if (m.right().Is(0)) return Replace(m.right().node());  // x & 0  => 0
1155   if (m.right().Is(-1)) return Replace(m.left().node());  // x & -1 => x
1156   if (m.left().IsComparison() && m.right().Is(1)) {       // CMP & 1 => CMP
1157     return Replace(m.left().node());
1158   }
1159   if (m.IsFoldable()) {                                   // K & K  => K
1160     return ReplaceInt32(m.left().Value() & m.right().Value());
1161   }
1162   if (m.LeftEqualsRight()) return Replace(m.left().node());  // x & x => x
1163   if (m.left().IsWord32And() && m.right().HasValue()) {
1164     Int32BinopMatcher mleft(m.left().node());
1165     if (mleft.right().HasValue()) {  // (x & K) & K => x & K
1166       node->ReplaceInput(0, mleft.left().node());
1167       node->ReplaceInput(
1168           1, Int32Constant(m.right().Value() & mleft.right().Value()));
1169       Reduction const reduction = ReduceWord32And(node);
1170       return reduction.Changed() ? reduction : Changed(node);
1171     }
1172   }
1173   if (m.right().IsNegativePowerOf2()) {
1174     int32_t const mask = m.right().Value();
1175     if (m.left().IsWord32Shl()) {
1176       Uint32BinopMatcher mleft(m.left().node());
1177       if (mleft.right().HasValue() &&
1178           (mleft.right().Value() & 0x1F) >=
1179               base::bits::CountTrailingZeros(mask)) {
1180         // (x << L) & (-1 << K) => x << L iff L >= K
1181         return Replace(mleft.node());
1182       }
1183     } else if (m.left().IsInt32Add()) {
1184       Int32BinopMatcher mleft(m.left().node());
1185       if (mleft.right().HasValue() &&
1186           (mleft.right().Value() & mask) == mleft.right().Value()) {
1187         // (x + (K << L)) & (-1 << L) => (x & (-1 << L)) + (K << L)
1188         node->ReplaceInput(0, Word32And(mleft.left().node(), m.right().node()));
1189         node->ReplaceInput(1, mleft.right().node());
1190         NodeProperties::ChangeOp(node, machine()->Int32Add());
1191         Reduction const reduction = ReduceInt32Add(node);
1192         return reduction.Changed() ? reduction : Changed(node);
1193       }
1194       if (mleft.left().IsInt32Mul()) {
1195         Int32BinopMatcher mleftleft(mleft.left().node());
1196         if (mleftleft.right().IsMultipleOf(-mask)) {
1197           // (y * (K << L) + x) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1198           node->ReplaceInput(0,
1199                              Word32And(mleft.right().node(), m.right().node()));
1200           node->ReplaceInput(1, mleftleft.node());
1201           NodeProperties::ChangeOp(node, machine()->Int32Add());
1202           Reduction const reduction = ReduceInt32Add(node);
1203           return reduction.Changed() ? reduction : Changed(node);
1204         }
1205       }
1206       if (mleft.right().IsInt32Mul()) {
1207         Int32BinopMatcher mleftright(mleft.right().node());
1208         if (mleftright.right().IsMultipleOf(-mask)) {
1209           // (x + y * (K << L)) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1210           node->ReplaceInput(0,
1211                              Word32And(mleft.left().node(), m.right().node()));
1212           node->ReplaceInput(1, mleftright.node());
1213           NodeProperties::ChangeOp(node, machine()->Int32Add());
1214           Reduction const reduction = ReduceInt32Add(node);
1215           return reduction.Changed() ? reduction : Changed(node);
1216         }
1217       }
1218       if (mleft.left().IsWord32Shl()) {
1219         Int32BinopMatcher mleftleft(mleft.left().node());
1220         if (mleftleft.right().Is(base::bits::CountTrailingZeros(mask))) {
1221           // (y << L + x) & (-1 << L) => (x & (-1 << L)) + y << L
1222           node->ReplaceInput(0,
1223                              Word32And(mleft.right().node(), m.right().node()));
1224           node->ReplaceInput(1, mleftleft.node());
1225           NodeProperties::ChangeOp(node, machine()->Int32Add());
1226           Reduction const reduction = ReduceInt32Add(node);
1227           return reduction.Changed() ? reduction : Changed(node);
1228         }
1229       }
1230       if (mleft.right().IsWord32Shl()) {
1231         Int32BinopMatcher mleftright(mleft.right().node());
1232         if (mleftright.right().Is(base::bits::CountTrailingZeros(mask))) {
1233           // (x + y << L) & (-1 << L) => (x & (-1 << L)) + y << L
1234           node->ReplaceInput(0,
1235                              Word32And(mleft.left().node(), m.right().node()));
1236           node->ReplaceInput(1, mleftright.node());
1237           NodeProperties::ChangeOp(node, machine()->Int32Add());
1238           Reduction const reduction = ReduceInt32Add(node);
1239           return reduction.Changed() ? reduction : Changed(node);
1240         }
1241       }
1242     } else if (m.left().IsInt32Mul()) {
1243       Int32BinopMatcher mleft(m.left().node());
1244       if (mleft.right().IsMultipleOf(-mask)) {
1245         // (x * (K << L)) & (-1 << L) => x * (K << L)
1246         return Replace(mleft.node());
1247       }
1248     }
1249   }
1250   return NoChange();
1251 }
1252 
TryMatchWord32Ror(Node * node)1253 Reduction MachineOperatorReducer::TryMatchWord32Ror(Node* node) {
1254   DCHECK(IrOpcode::kWord32Or == node->opcode() ||
1255          IrOpcode::kWord32Xor == node->opcode());
1256   Int32BinopMatcher m(node);
1257   Node* shl = nullptr;
1258   Node* shr = nullptr;
1259   // Recognize rotation, we are matching:
1260   //  * x << y | x >>> (32 - y) => x ror (32 - y), i.e  x rol y
1261   //  * x << (32 - y) | x >>> y => x ror y
1262   //  * x << y ^ x >>> (32 - y) => x ror (32 - y), i.e. x rol y
1263   //  * x << (32 - y) ^ x >>> y => x ror y
1264   // as well as their commuted form.
1265   if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) {
1266     shl = m.left().node();
1267     shr = m.right().node();
1268   } else if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) {
1269     shl = m.right().node();
1270     shr = m.left().node();
1271   } else {
1272     return NoChange();
1273   }
1274 
1275   Int32BinopMatcher mshl(shl);
1276   Int32BinopMatcher mshr(shr);
1277   if (mshl.left().node() != mshr.left().node()) return NoChange();
1278 
1279   if (mshl.right().HasValue() && mshr.right().HasValue()) {
1280     // Case where y is a constant.
1281     if (mshl.right().Value() + mshr.right().Value() != 32) return NoChange();
1282   } else {
1283     Node* sub = nullptr;
1284     Node* y = nullptr;
1285     if (mshl.right().IsInt32Sub()) {
1286       sub = mshl.right().node();
1287       y = mshr.right().node();
1288     } else if (mshr.right().IsInt32Sub()) {
1289       sub = mshr.right().node();
1290       y = mshl.right().node();
1291     } else {
1292       return NoChange();
1293     }
1294 
1295     Int32BinopMatcher msub(sub);
1296     if (!msub.left().Is(32) || msub.right().node() != y) return NoChange();
1297   }
1298 
1299   node->ReplaceInput(0, mshl.left().node());
1300   node->ReplaceInput(1, mshr.right().node());
1301   NodeProperties::ChangeOp(node, machine()->Word32Ror());
1302   return Changed(node);
1303 }
1304 
ReduceWord32Or(Node * node)1305 Reduction MachineOperatorReducer::ReduceWord32Or(Node* node) {
1306   DCHECK_EQ(IrOpcode::kWord32Or, node->opcode());
1307   Int32BinopMatcher m(node);
1308   if (m.right().Is(0)) return Replace(m.left().node());    // x | 0  => x
1309   if (m.right().Is(-1)) return Replace(m.right().node());  // x | -1 => -1
1310   if (m.IsFoldable()) {                                    // K | K  => K
1311     return ReplaceInt32(m.left().Value() | m.right().Value());
1312   }
1313   if (m.LeftEqualsRight()) return Replace(m.left().node());  // x | x => x
1314 
1315   return TryMatchWord32Ror(node);
1316 }
1317 
ReduceWord32Xor(Node * node)1318 Reduction MachineOperatorReducer::ReduceWord32Xor(Node* node) {
1319   DCHECK_EQ(IrOpcode::kWord32Xor, node->opcode());
1320   Int32BinopMatcher m(node);
1321   if (m.right().Is(0)) return Replace(m.left().node());  // x ^ 0 => x
1322   if (m.IsFoldable()) {                                  // K ^ K => K
1323     return ReplaceInt32(m.left().Value() ^ m.right().Value());
1324   }
1325   if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x ^ x => 0
1326   if (m.left().IsWord32Xor() && m.right().Is(-1)) {
1327     Int32BinopMatcher mleft(m.left().node());
1328     if (mleft.right().Is(-1)) {  // (x ^ -1) ^ -1 => x
1329       return Replace(mleft.left().node());
1330     }
1331   }
1332 
1333   return TryMatchWord32Ror(node);
1334 }
1335 
ReduceFloat64InsertLowWord32(Node * node)1336 Reduction MachineOperatorReducer::ReduceFloat64InsertLowWord32(Node* node) {
1337   DCHECK_EQ(IrOpcode::kFloat64InsertLowWord32, node->opcode());
1338   Float64Matcher mlhs(node->InputAt(0));
1339   Uint32Matcher mrhs(node->InputAt(1));
1340   if (mlhs.HasValue() && mrhs.HasValue()) {
1341     return ReplaceFloat64(bit_cast<double>(
1342         (bit_cast<uint64_t>(mlhs.Value()) & uint64_t{0xFFFFFFFF00000000}) |
1343         mrhs.Value()));
1344   }
1345   return NoChange();
1346 }
1347 
1348 
ReduceFloat64InsertHighWord32(Node * node)1349 Reduction MachineOperatorReducer::ReduceFloat64InsertHighWord32(Node* node) {
1350   DCHECK_EQ(IrOpcode::kFloat64InsertHighWord32, node->opcode());
1351   Float64Matcher mlhs(node->InputAt(0));
1352   Uint32Matcher mrhs(node->InputAt(1));
1353   if (mlhs.HasValue() && mrhs.HasValue()) {
1354     return ReplaceFloat64(bit_cast<double>(
1355         (bit_cast<uint64_t>(mlhs.Value()) & uint64_t{0xFFFFFFFF}) |
1356         (static_cast<uint64_t>(mrhs.Value()) << 32)));
1357   }
1358   return NoChange();
1359 }
1360 
1361 
1362 namespace {
1363 
IsFloat64RepresentableAsFloat32(const Float64Matcher & m)1364 bool IsFloat64RepresentableAsFloat32(const Float64Matcher& m) {
1365   if (m.HasValue()) {
1366     double v = m.Value();
1367     float fv = static_cast<float>(v);
1368     return static_cast<double>(fv) == v;
1369   }
1370   return false;
1371 }
1372 
1373 }  // namespace
1374 
1375 
ReduceFloat64Compare(Node * node)1376 Reduction MachineOperatorReducer::ReduceFloat64Compare(Node* node) {
1377   DCHECK((IrOpcode::kFloat64Equal == node->opcode()) ||
1378          (IrOpcode::kFloat64LessThan == node->opcode()) ||
1379          (IrOpcode::kFloat64LessThanOrEqual == node->opcode()));
1380   // As all Float32 values have an exact representation in Float64, comparing
1381   // two Float64 values both converted from Float32 is equivalent to comparing
1382   // the original Float32s, so we can ignore the conversions. We can also reduce
1383   // comparisons of converted Float64 values against constants that can be
1384   // represented exactly as Float32.
1385   Float64BinopMatcher m(node);
1386   if ((m.left().IsChangeFloat32ToFloat64() &&
1387        m.right().IsChangeFloat32ToFloat64()) ||
1388       (m.left().IsChangeFloat32ToFloat64() &&
1389        IsFloat64RepresentableAsFloat32(m.right())) ||
1390       (IsFloat64RepresentableAsFloat32(m.left()) &&
1391        m.right().IsChangeFloat32ToFloat64())) {
1392     switch (node->opcode()) {
1393       case IrOpcode::kFloat64Equal:
1394         NodeProperties::ChangeOp(node, machine()->Float32Equal());
1395         break;
1396       case IrOpcode::kFloat64LessThan:
1397         NodeProperties::ChangeOp(node, machine()->Float32LessThan());
1398         break;
1399       case IrOpcode::kFloat64LessThanOrEqual:
1400         NodeProperties::ChangeOp(node, machine()->Float32LessThanOrEqual());
1401         break;
1402       default:
1403         return NoChange();
1404     }
1405     node->ReplaceInput(
1406         0, m.left().HasValue()
1407                ? Float32Constant(static_cast<float>(m.left().Value()))
1408                : m.left().InputAt(0));
1409     node->ReplaceInput(
1410         1, m.right().HasValue()
1411                ? Float32Constant(static_cast<float>(m.right().Value()))
1412                : m.right().InputAt(0));
1413     return Changed(node);
1414   }
1415   return NoChange();
1416 }
1417 
ReduceFloat64RoundDown(Node * node)1418 Reduction MachineOperatorReducer::ReduceFloat64RoundDown(Node* node) {
1419   DCHECK_EQ(IrOpcode::kFloat64RoundDown, node->opcode());
1420   Float64Matcher m(node->InputAt(0));
1421   if (m.HasValue()) {
1422     return ReplaceFloat64(Floor(m.Value()));
1423   }
1424   return NoChange();
1425 }
1426 
common() const1427 CommonOperatorBuilder* MachineOperatorReducer::common() const {
1428   return mcgraph()->common();
1429 }
1430 
1431 
machine() const1432 MachineOperatorBuilder* MachineOperatorReducer::machine() const {
1433   return mcgraph()->machine();
1434 }
1435 
graph() const1436 Graph* MachineOperatorReducer::graph() const { return mcgraph()->graph(); }
1437 
1438 }  // namespace compiler
1439 }  // namespace internal
1440 }  // namespace v8
1441