machine-operator-reducer.cc 90.1 KB
Newer Older
1 2 3 4 5
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/machine-operator-reducer.h"
6

7
#include <cmath>
8
#include <limits>
9

10
#include "src/base/bits.h"
11
#include "src/base/division-by-constant.h"
12
#include "src/base/ieee754.h"
13
#include "src/base/logging.h"
14
#include "src/base/overflowing-math.h"
15
#include "src/compiler/diamond.h"
16
#include "src/compiler/graph.h"
17
#include "src/compiler/js-operator.h"
18
#include "src/compiler/machine-graph.h"
19
#include "src/compiler/node-matchers.h"
20
#include "src/compiler/node-properties.h"
21
#include "src/compiler/opcodes.h"
22
#include "src/numbers/conversions-inl.h"
23 24 25 26 27

namespace v8 {
namespace internal {
namespace compiler {

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
// Some optimizations performed by the MachineOperatorReducer can be applied
// to both Word32 and Word64 operations. Those are implemented in a generic
// way to be reused for different word sizes.
// This class adapts a generic algorithm to Word32 operations.
class Word32Adapter {
 public:
  using IntNBinopMatcher = Int32BinopMatcher;
  using UintNBinopMatcher = Uint32BinopMatcher;
  using intN_t = int32_t;
  // WORD_SIZE refers to the N for which this adapter specializes.
  static constexpr std::size_t WORD_SIZE = 32;

  explicit Word32Adapter(MachineOperatorReducer* reducer) : r_(reducer) {}

  template <typename T>
  static bool IsWordNAnd(const T& x) {
    return x.IsWord32And();
  }
  template <typename T>
  static bool IsWordNShl(const T& x) {
    return x.IsWord32Shl();
  }
  template <typename T>
51 52 53 54 55 56 57 58
  static bool IsWordNShr(const T& x) {
    return x.IsWord32Shr();
  }
  template <typename T>
  static bool IsWordNSar(const T& x) {
    return x.IsWord32Sar();
  }
  template <typename T>
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
  static bool IsWordNXor(const T& x) {
    return x.IsWord32Xor();
  }
  template <typename T>
  static bool IsIntNAdd(const T& x) {
    return x.IsInt32Add();
  }
  template <typename T>
  static bool IsIntNMul(const T& x) {
    return x.IsInt32Mul();
  }

  const Operator* IntNAdd(MachineOperatorBuilder* machine) {
    return machine->Int32Add();
  }

  Reduction ReplaceIntN(int32_t value) { return r_->ReplaceInt32(value); }
  Reduction ReduceWordNAnd(Node* node) { return r_->ReduceWord32And(node); }
  Reduction ReduceIntNAdd(Node* node) { return r_->ReduceInt32Add(node); }
  Reduction TryMatchWordNRor(Node* node) { return r_->TryMatchWord32Ror(node); }

  Node* IntNConstant(int32_t value) { return r_->Int32Constant(value); }
81
  Node* UintNConstant(uint32_t value) { return r_->Uint32Constant(value); }
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
  Node* WordNAnd(Node* lhs, Node* rhs) { return r_->Word32And(lhs, rhs); }

 private:
  MachineOperatorReducer* r_;
};

// Some optimizations performed by the MachineOperatorReducer can be applied
// to both Word32 and Word64 operations. Those are implemented in a generic
// way to be reused for different word sizes.
// This class adapts a generic algorithm to Word64 operations.
class Word64Adapter {
 public:
  using IntNBinopMatcher = Int64BinopMatcher;
  using UintNBinopMatcher = Uint64BinopMatcher;
  using intN_t = int64_t;
  // WORD_SIZE refers to the N for which this adapter specializes.
  static constexpr std::size_t WORD_SIZE = 64;

  explicit Word64Adapter(MachineOperatorReducer* reducer) : r_(reducer) {}

  template <typename T>
  static bool IsWordNAnd(const T& x) {
    return x.IsWord64And();
  }
  template <typename T>
  static bool IsWordNShl(const T& x) {
    return x.IsWord64Shl();
  }
  template <typename T>
111 112 113 114 115 116 117 118
  static bool IsWordNShr(const T& x) {
    return x.IsWord64Shr();
  }
  template <typename T>
  static bool IsWordNSar(const T& x) {
    return x.IsWord64Sar();
  }
  template <typename T>
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
  static bool IsWordNXor(const T& x) {
    return x.IsWord64Xor();
  }
  template <typename T>
  static bool IsIntNAdd(const T& x) {
    return x.IsInt64Add();
  }
  template <typename T>
  static bool IsIntNMul(const T& x) {
    return x.IsInt64Mul();
  }

  static const Operator* IntNAdd(MachineOperatorBuilder* machine) {
    return machine->Int64Add();
  }

  Reduction ReplaceIntN(int64_t value) { return r_->ReplaceInt64(value); }
  Reduction ReduceWordNAnd(Node* node) { return r_->ReduceWord64And(node); }
  Reduction ReduceIntNAdd(Node* node) { return r_->ReduceInt64Add(node); }
  Reduction TryMatchWordNRor(Node* node) {
    // TODO(nicohartmann@): Add a MachineOperatorReducer::TryMatchWord64Ror.
    return r_->NoChange();
  }

  Node* IntNConstant(int64_t value) { return r_->Int64Constant(value); }
144
  Node* UintNConstant(uint64_t value) { return r_->Uint64Constant(value); }
145 146 147 148 149 150
  Node* WordNAnd(Node* lhs, Node* rhs) { return r_->Word64And(lhs, rhs); }

 private:
  MachineOperatorReducer* r_;
};

151 152 153 154 155 156 157 158 159 160 161 162 163
namespace {

// TODO(jgruber): Consider replacing all uses of this function by
// std::numeric_limits<T>::quiet_NaN().
template <class T>
T SilenceNaN(T x) {
  DCHECK(std::isnan(x));
  // Do some calculation to make a signalling NaN quiet.
  return x - x;
}

}  // namespace

164 165
MachineOperatorReducer::MachineOperatorReducer(Editor* editor,
                                               MachineGraph* mcgraph,
166
                                               bool allow_signalling_nan)
167 168 169
    : AdvancedReducer(editor),
      mcgraph_(mcgraph),
      allow_signalling_nan_(allow_signalling_nan) {}
170

171
MachineOperatorReducer::~MachineOperatorReducer() = default;
172 173


174
Node* MachineOperatorReducer::Float32Constant(float value) {
175 176 177
  return graph()->NewNode(common()->Float32Constant(value));
}

178
Node* MachineOperatorReducer::Float64Constant(double value) {
179
  return mcgraph()->Float64Constant(value);
180 181
}

182
Node* MachineOperatorReducer::Int32Constant(int32_t value) {
183
  return mcgraph()->Int32Constant(value);
184 185
}

186
Node* MachineOperatorReducer::Int64Constant(int64_t value) {
187
  return graph()->NewNode(common()->Int64Constant(value));
188 189
}

190 191 192 193 194 195 196
Node* MachineOperatorReducer::Float64Mul(Node* lhs, Node* rhs) {
  return graph()->NewNode(machine()->Float64Mul(), lhs, rhs);
}

Node* MachineOperatorReducer::Float64PowHalf(Node* value) {
  value =
      graph()->NewNode(machine()->Float64Add(), Float64Constant(0.0), value);
197 198 199 200 201 202
  Diamond d(graph(), common(),
            graph()->NewNode(machine()->Float64LessThanOrEqual(), value,
                             Float64Constant(-V8_INFINITY)),
            BranchHint::kFalse);
  return d.Phi(MachineRepresentation::kFloat64, Float64Constant(V8_INFINITY),
               graph()->NewNode(machine()->Float64Sqrt(), value));
203
}
204

205 206 207 208
Node* MachineOperatorReducer::Word32And(Node* lhs, Node* rhs) {
  Node* const node = graph()->NewNode(machine()->Word32And(), lhs, rhs);
  Reduction const reduction = ReduceWord32And(node);
  return reduction.Changed() ? reduction.replacement() : node;
209 210 211
}

Node* MachineOperatorReducer::Word32Sar(Node* lhs, uint32_t rhs) {
212
  if (rhs == 0) return lhs;
213 214 215 216
  return graph()->NewNode(machine()->Word32Sar(), lhs, Uint32Constant(rhs));
}

Node* MachineOperatorReducer::Word32Shr(Node* lhs, uint32_t rhs) {
217
  if (rhs == 0) return lhs;
218 219 220
  return graph()->NewNode(machine()->Word32Shr(), lhs, Uint32Constant(rhs));
}

221 222 223 224
Node* MachineOperatorReducer::Word32Equal(Node* lhs, Node* rhs) {
  return graph()->NewNode(machine()->Word32Equal(), lhs, rhs);
}

225 226 227 228 229 230
Node* MachineOperatorReducer::Word64And(Node* lhs, Node* rhs) {
  Node* const node = graph()->NewNode(machine()->Word64And(), lhs, rhs);
  Reduction const reduction = ReduceWord64And(node);
  return reduction.Changed() ? reduction.replacement() : node;
}

231
Node* MachineOperatorReducer::Int32Add(Node* lhs, Node* rhs) {
232 233 234
  Node* const node = graph()->NewNode(machine()->Int32Add(), lhs, rhs);
  Reduction const reduction = ReduceInt32Add(node);
  return reduction.Changed() ? reduction.replacement() : node;
235 236 237
}

Node* MachineOperatorReducer::Int32Sub(Node* lhs, Node* rhs) {
238 239 240
  Node* const node = graph()->NewNode(machine()->Int32Sub(), lhs, rhs);
  Reduction const reduction = ReduceInt32Sub(node);
  return reduction.Changed() ? reduction.replacement() : node;
241 242 243 244 245 246
}

Node* MachineOperatorReducer::Int32Mul(Node* lhs, Node* rhs) {
  return graph()->NewNode(machine()->Int32Mul(), lhs, rhs);
}

247 248
Node* MachineOperatorReducer::Int32Div(Node* dividend, int32_t divisor) {
  DCHECK_NE(0, divisor);
249 250
  DCHECK_NE(std::numeric_limits<int32_t>::min(), divisor);
  base::MagicNumbersForDivision<uint32_t> const mag =
251
      base::SignedDivisionByConstant(base::bit_cast<uint32_t>(divisor));
252 253
  Node* quotient = graph()->NewNode(machine()->Int32MulHigh(), dividend,
                                    Uint32Constant(mag.multiplier));
254
  if (divisor > 0 && base::bit_cast<int32_t>(mag.multiplier) < 0) {
255
    quotient = Int32Add(quotient, dividend);
256
  } else if (divisor < 0 && base::bit_cast<int32_t>(mag.multiplier) > 0) {
257 258
    quotient = Int32Sub(quotient, dividend);
  }
259 260 261 262
  return Int32Add(Word32Sar(quotient, mag.shift), Word32Shr(dividend, 31));
}

Node* MachineOperatorReducer::Uint32Div(Node* dividend, uint32_t divisor) {
263
  DCHECK_LT(0u, divisor);
264 265
  // If the divisor is even, we can avoid using the expensive fixup by shifting
  // the dividend upfront.
266
  unsigned const shift = base::bits::CountTrailingZeros(divisor);
267 268 269
  dividend = Word32Shr(dividend, shift);
  divisor >>= shift;
  // Compute the magic number for the (shifted) divisor.
270
  base::MagicNumbersForDivision<uint32_t> const mag =
271
      base::UnsignedDivisionByConstant(divisor, shift);
272 273 274
  Node* quotient = graph()->NewNode(machine()->Uint32MulHigh(), dividend,
                                    Uint32Constant(mag.multiplier));
  if (mag.add) {
275
    DCHECK_LE(1u, mag.shift);
276 277 278 279 280
    quotient = Word32Shr(
        Int32Add(Word32Shr(Int32Sub(dividend, quotient), 1), quotient),
        mag.shift - 1);
  } else {
    quotient = Word32Shr(quotient, mag.shift);
281
  }
282
  return quotient;
283 284
}

285 286 287 288 289 290
Node* MachineOperatorReducer::TruncateInt64ToInt32(Node* value) {
  Node* const node = graph()->NewNode(machine()->TruncateInt64ToInt32(), value);
  Reduction const reduction = ReduceTruncateInt64ToInt32(node);
  return reduction.Changed() ? reduction.replacement() : node;
}

291 292 293
// Perform constant folding and strength reduction on machine operators.
Reduction MachineOperatorReducer::Reduce(Node* node) {
  switch (node->opcode()) {
294
    case IrOpcode::kProjection:
295
      return ReduceProjection(ProjectionIndexOf(node->op()), node->InputAt(0));
296 297
    case IrOpcode::kWord32And:
      return ReduceWord32And(node);
298 299
    case IrOpcode::kWord64And:
      return ReduceWord64And(node);
300 301
    case IrOpcode::kWord32Or:
      return ReduceWord32Or(node);
302 303
    case IrOpcode::kWord64Or:
      return ReduceWord64Or(node);
304 305
    case IrOpcode::kWord32Xor:
      return ReduceWord32Xor(node);
306 307
    case IrOpcode::kWord64Xor:
      return ReduceWord64Xor(node);
308 309
    case IrOpcode::kWord32Shl:
      return ReduceWord32Shl(node);
310 311
    case IrOpcode::kWord64Shl:
      return ReduceWord64Shl(node);
312 313
    case IrOpcode::kWord32Shr:
      return ReduceWord32Shr(node);
314 315
    case IrOpcode::kWord64Shr:
      return ReduceWord64Shr(node);
316 317
    case IrOpcode::kWord32Sar:
      return ReduceWord32Sar(node);
318 319
    case IrOpcode::kWord64Sar:
      return ReduceWord64Sar(node);
320 321 322
    case IrOpcode::kWord32Ror: {
      Int32BinopMatcher m(node);
      if (m.right().Is(0)) return Replace(m.left().node());  // x ror 0 => x
323
      if (m.IsFoldable()) {  // K ror K => K  (K stands for arbitrary constants)
324 325
        return ReplaceInt32(base::bits::RotateRight32(
            m.left().ResolvedValue(), m.right().ResolvedValue() & 31));
326 327 328
      }
      break;
    }
329
    case IrOpcode::kWord32Equal: {
330
      return ReduceWord32Equal(node);
331 332 333
    }
    case IrOpcode::kWord64Equal: {
      Int64BinopMatcher m(node);
334
      if (m.IsFoldable()) {  // K == K => K  (K stands for arbitrary constants)
335 336
        return ReplaceBool(m.left().ResolvedValue() ==
                           m.right().ResolvedValue());
337 338 339 340 341
      }
      if (m.left().IsInt64Sub() && m.right().Is(0)) {  // x - y == 0 => x == y
        Int64BinopMatcher msub(m.left().node());
        node->ReplaceInput(0, msub.left().node());
        node->ReplaceInput(1, msub.right().node());
342 343 344 345 346 347
        return Changed(node);
      }
      // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
      if (m.LeftEqualsRight()) return ReplaceBool(true);  // x == x => true
      break;
    }
348 349
    case IrOpcode::kInt32Add:
      return ReduceInt32Add(node);
350 351
    case IrOpcode::kInt64Add:
      return ReduceInt64Add(node);
352 353
    case IrOpcode::kInt32Sub:
      return ReduceInt32Sub(node);
354 355
    case IrOpcode::kInt64Sub:
      return ReduceInt64Sub(node);
356 357 358 359
    case IrOpcode::kInt32Mul: {
      Int32BinopMatcher m(node);
      if (m.right().Is(0)) return Replace(m.right().node());  // x * 0 => 0
      if (m.right().Is(1)) return Replace(m.left().node());   // x * 1 => x
360
      if (m.IsFoldable()) {  // K * K => K  (K stands for arbitrary constants)
361 362
        return ReplaceInt32(base::MulWithWraparound(m.left().ResolvedValue(),
                                                    m.right().ResolvedValue()));
363 364 365 366
      }
      if (m.right().Is(-1)) {  // x * -1 => 0 - x
        node->ReplaceInput(0, Int32Constant(0));
        node->ReplaceInput(1, m.left().node());
367
        NodeProperties::ChangeOp(node, machine()->Int32Sub());
368 369 370
        return Changed(node);
      }
      if (m.right().IsPowerOf2()) {  // x * 2^n => x << n
371 372
        node->ReplaceInput(1, Int32Constant(base::bits::WhichPowerOfTwo(
                                  m.right().ResolvedValue())));
373
        NodeProperties::ChangeOp(node, machine()->Word32Shl());
374
        return Changed(node).FollowedBy(ReduceWord32Shl(node));
375
      }
376
      // (x * Int32Constant(a)) * Int32Constant(b)) => x * Int32Constant(a * b)
377
      if (m.right().HasResolvedValue() && m.left().IsInt32Mul()) {
378
        Int32BinopMatcher n(m.left().node());
379 380 381 382
        if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
          node->ReplaceInput(
              1, Int32Constant(base::MulWithWraparound(
                     m.right().ResolvedValue(), n.right().ResolvedValue())));
383 384 385 386
          node->ReplaceInput(0, n.left().node());
          return Changed(node);
        }
      }
387 388
      break;
    }
389 390 391 392 393 394 395 396 397 398 399 400 401 402 403
    case IrOpcode::kInt32MulWithOverflow: {
      Int32BinopMatcher m(node);
      if (m.right().Is(2)) {
        node->ReplaceInput(1, m.left().node());
        NodeProperties::ChangeOp(node, machine()->Int32AddWithOverflow());
        return Changed(node);
      }
      if (m.right().Is(-1)) {
        node->ReplaceInput(0, Int32Constant(0));
        node->ReplaceInput(1, m.left().node());
        NodeProperties::ChangeOp(node, machine()->Int32SubWithOverflow());
        return Changed(node);
      }
      break;
    }
404 405
    case IrOpcode::kInt64Mul:
      return ReduceInt64Mul(node);
406 407
    case IrOpcode::kInt32Div:
      return ReduceInt32Div(node);
408 409
    case IrOpcode::kUint32Div:
      return ReduceUint32Div(node);
410 411
    case IrOpcode::kInt32Mod:
      return ReduceInt32Mod(node);
412 413
    case IrOpcode::kUint32Mod:
      return ReduceUint32Mod(node);
414 415
    case IrOpcode::kInt32LessThan: {
      Int32BinopMatcher m(node);
416
      if (m.IsFoldable()) {  // K < K => K  (K stands for arbitrary constants)
417 418
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
419 420
      }
      if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
421 422 423 424 425 426 427 428
      if (m.left().IsWord32Or() && m.right().Is(0)) {
        // (x | K) < 0 => true or (K | x) < 0 => true iff K < 0
        Int32BinopMatcher mleftmatcher(m.left().node());
        if (mleftmatcher.left().IsNegative() ||
            mleftmatcher.right().IsNegative()) {
          return ReplaceBool(true);
        }
      }
429
      return ReduceWord32Comparisons(node);
430 431 432
    }
    case IrOpcode::kInt32LessThanOrEqual: {
      Int32BinopMatcher m(node);
433
      if (m.IsFoldable()) {  // K <= K => K  (K stands for arbitrary constants)
434 435
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
436 437
      }
      if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
438
      return ReduceWord32Comparisons(node);
439 440 441 442 443
    }
    case IrOpcode::kUint32LessThan: {
      Uint32BinopMatcher m(node);
      if (m.left().Is(kMaxUInt32)) return ReplaceBool(false);  // M < x => false
      if (m.right().Is(0)) return ReplaceBool(false);          // x < 0 => false
444
      if (m.IsFoldable()) {  // K < K => K  (K stands for arbitrary constants)
445 446
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
447 448
      }
      if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
449
      if (m.left().IsWord32Sar() && m.right().HasResolvedValue()) {
450
        Int32BinopMatcher mleft(m.left().node());
451
        if (mleft.right().HasResolvedValue()) {
452
          // (x >> K) < C => x < (C << K)
453
          // when C < (M >> K)
454 455
          const uint32_t c = m.right().ResolvedValue();
          const uint32_t k = mleft.right().ResolvedValue() & 0x1F;
456 457
          if (c < static_cast<uint32_t>(kMaxInt >> k)) {
            node->ReplaceInput(0, mleft.left().node());
458
            node->ReplaceInput(1, Uint32Constant(c << k));
459 460
            return Changed(node);
          }
461
          // TODO(turbofan): else the comparison is always true.
462 463
        }
      }
464
      return ReduceWord32Comparisons(node);
465 466 467 468 469
    }
    case IrOpcode::kUint32LessThanOrEqual: {
      Uint32BinopMatcher m(node);
      if (m.left().Is(0)) return ReplaceBool(true);            // 0 <= x => true
      if (m.right().Is(kMaxUInt32)) return ReplaceBool(true);  // x <= M => true
470
      if (m.IsFoldable()) {  // K <= K => K  (K stands for arbitrary constants)
471 472
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
473 474
      }
      if (m.LeftEqualsRight()) return ReplaceBool(true);  // x <= x => true
475
      return ReduceWord32Comparisons(node);
476
    }
477 478
    case IrOpcode::kFloat32Sub: {
      Float32BinopMatcher m(node);
479
      if (allow_signalling_nan_ && m.right().Is(0) &&
480
          (std::copysign(1.0, m.right().ResolvedValue()) > 0)) {
481 482
        return Replace(m.left().node());  // x - 0 => x
      }
483
      if (m.right().IsNaN()) {  // x - NaN => NaN
484
        return ReplaceFloat32(SilenceNaN(m.right().ResolvedValue()));
485 486
      }
      if (m.left().IsNaN()) {  // NaN - x => NaN
487
        return ReplaceFloat32(SilenceNaN(m.left().ResolvedValue()));
488 489
      }
      if (m.IsFoldable()) {  // L - R => (L - R)
490 491
        return ReplaceFloat32(m.left().ResolvedValue() -
                              m.right().ResolvedValue());
492
      }
493
      if (allow_signalling_nan_ && m.left().IsMinusZero()) {
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
        // -0.0 - round_down(-0.0 - R) => round_up(R)
        if (machine()->Float32RoundUp().IsSupported() &&
            m.right().IsFloat32RoundDown()) {
          if (m.right().InputAt(0)->opcode() == IrOpcode::kFloat32Sub) {
            Float32BinopMatcher mright0(m.right().InputAt(0));
            if (mright0.left().IsMinusZero()) {
              return Replace(graph()->NewNode(machine()->Float32RoundUp().op(),
                                              mright0.right().node()));
            }
          }
        }
        // -0.0 - R => -R
        node->RemoveInput(0);
        NodeProperties::ChangeOp(node, machine()->Float32Neg());
        return Changed(node);
      }
      break;
    }
512 513
    case IrOpcode::kFloat64Add: {
      Float64BinopMatcher m(node);
514 515 516 517 518 519
      if (m.right().IsNaN()) {  // x + NaN => NaN
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
      }
      if (m.left().IsNaN()) {  // NaN + x => NaN
        return ReplaceFloat64(SilenceNaN(m.left().ResolvedValue()));
      }
520
      if (m.IsFoldable()) {  // K + K => K  (K stands for arbitrary constants)
521 522
        return ReplaceFloat64(m.left().ResolvedValue() +
                              m.right().ResolvedValue());
523 524 525 526 527
      }
      break;
    }
    case IrOpcode::kFloat64Sub: {
      Float64BinopMatcher m(node);
528
      if (allow_signalling_nan_ && m.right().Is(0) &&
529
          (base::Double(m.right().ResolvedValue()).Sign() > 0)) {
530 531
        return Replace(m.left().node());  // x - 0 => x
      }
532
      if (m.right().IsNaN()) {  // x - NaN => NaN
533
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
534 535
      }
      if (m.left().IsNaN()) {  // NaN - x => NaN
536
        return ReplaceFloat64(SilenceNaN(m.left().ResolvedValue()));
537
      }
538
      if (m.IsFoldable()) {  // L - R => (L - R)
539 540
        return ReplaceFloat64(m.left().ResolvedValue() -
                              m.right().ResolvedValue());
541
      }
542
      if (allow_signalling_nan_ && m.left().IsMinusZero()) {
543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
        // -0.0 - round_down(-0.0 - R) => round_up(R)
        if (machine()->Float64RoundUp().IsSupported() &&
            m.right().IsFloat64RoundDown()) {
          if (m.right().InputAt(0)->opcode() == IrOpcode::kFloat64Sub) {
            Float64BinopMatcher mright0(m.right().InputAt(0));
            if (mright0.left().IsMinusZero()) {
              return Replace(graph()->NewNode(machine()->Float64RoundUp().op(),
                                              mright0.right().node()));
            }
          }
        }
        // -0.0 - R => -R
        node->RemoveInput(0);
        NodeProperties::ChangeOp(node, machine()->Float64Neg());
        return Changed(node);
      }
559 560 561 562
      break;
    }
    case IrOpcode::kFloat64Mul: {
      Float64BinopMatcher m(node);
563 564
      if (allow_signalling_nan_ && m.right().Is(1))
        return Replace(m.left().node());  // x * 1.0 => x
565 566 567
      if (m.right().Is(-1)) {  // x * -1.0 => -0.0 - x
        node->ReplaceInput(0, Float64Constant(-0.0));
        node->ReplaceInput(1, m.left().node());
568
        NodeProperties::ChangeOp(node, machine()->Float64Sub());
569 570
        return Changed(node);
      }
571
      if (m.right().IsNaN()) {                               // x * NaN => NaN
572
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
573
      }
574
      if (m.IsFoldable()) {  // K * K => K  (K stands for arbitrary constants)
575 576
        return ReplaceFloat64(m.left().ResolvedValue() *
                              m.right().ResolvedValue());
577
      }
578 579 580 581 582
      if (m.right().Is(2)) {  // x * 2.0 => x + x
        node->ReplaceInput(1, m.left().node());
        NodeProperties::ChangeOp(node, machine()->Float64Add());
        return Changed(node);
      }
583
      break;
584 585 586
    }
    case IrOpcode::kFloat64Div: {
      Float64BinopMatcher m(node);
587 588
      if (allow_signalling_nan_ && m.right().Is(1))
        return Replace(m.left().node());  // x / 1.0 => x
589
      // TODO(ahaas): We could do x / 1.0 = x if we knew that x is not an sNaN.
590
      if (m.right().IsNaN()) {                               // x / NaN => NaN
591
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
592 593
      }
      if (m.left().IsNaN()) {  // NaN / x => NaN
594
        return ReplaceFloat64(SilenceNaN(m.left().ResolvedValue()));
595
      }
596
      if (m.IsFoldable()) {  // K / K => K  (K stands for arbitrary constants)
597
        return ReplaceFloat64(
598
            base::Divide(m.left().ResolvedValue(), m.right().ResolvedValue()));
599
      }
600
      if (allow_signalling_nan_ && m.right().Is(-1)) {  // x / -1.0 => -x
601 602 603 604 605 606 607 608
        node->RemoveInput(1);
        NodeProperties::ChangeOp(node, machine()->Float64Neg());
        return Changed(node);
      }
      if (m.right().IsNormal() && m.right().IsPositiveOrNegativePowerOf2()) {
        // All reciprocals of non-denormal powers of two can be represented
        // exactly, so division by power of two can be reduced to
        // multiplication by reciprocal, with the same result.
609
        node->ReplaceInput(1, Float64Constant(1.0 / m.right().ResolvedValue()));
610 611 612
        NodeProperties::ChangeOp(node, machine()->Float64Mul());
        return Changed(node);
      }
613
      break;
614 615 616
    }
    case IrOpcode::kFloat64Mod: {
      Float64BinopMatcher m(node);
617
      if (m.right().Is(0)) {  // x % 0 => NaN
618
        return ReplaceFloat64(std::numeric_limits<double>::quiet_NaN());
619
      }
620
      if (m.right().IsNaN()) {  // x % NaN => NaN
621
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
622 623
      }
      if (m.left().IsNaN()) {  // NaN % x => NaN
624
        return ReplaceFloat64(SilenceNaN(m.left().ResolvedValue()));
625
      }
626
      if (m.IsFoldable()) {  // K % K => K  (K stands for arbitrary constants)
627 628
        return ReplaceFloat64(
            Modulo(m.left().ResolvedValue(), m.right().ResolvedValue()));
629 630 631
      }
      break;
    }
632 633
    case IrOpcode::kFloat64Acos: {
      Float64Matcher m(node->InputAt(0));
634 635
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::acos(m.ResolvedValue()));
636 637 638 639
      break;
    }
    case IrOpcode::kFloat64Acosh: {
      Float64Matcher m(node->InputAt(0));
640 641
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::acosh(m.ResolvedValue()));
642 643 644 645
      break;
    }
    case IrOpcode::kFloat64Asin: {
      Float64Matcher m(node->InputAt(0));
646 647
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::asin(m.ResolvedValue()));
648 649 650 651
      break;
    }
    case IrOpcode::kFloat64Asinh: {
      Float64Matcher m(node->InputAt(0));
652 653
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::asinh(m.ResolvedValue()));
654 655
      break;
    }
656 657
    case IrOpcode::kFloat64Atan: {
      Float64Matcher m(node->InputAt(0));
658 659
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::atan(m.ResolvedValue()));
660 661
      break;
    }
662 663
    case IrOpcode::kFloat64Atanh: {
      Float64Matcher m(node->InputAt(0));
664 665
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::atanh(m.ResolvedValue()));
666 667
      break;
    }
668 669 670
    case IrOpcode::kFloat64Atan2: {
      Float64BinopMatcher m(node);
      if (m.right().IsNaN()) {
671
        return ReplaceFloat64(SilenceNaN(m.right().ResolvedValue()));
672 673
      }
      if (m.left().IsNaN()) {
674
        return ReplaceFloat64(SilenceNaN(m.left().ResolvedValue()));
675 676
      }
      if (m.IsFoldable()) {
677 678
        return ReplaceFloat64(base::ieee754::atan2(m.left().ResolvedValue(),
                                                   m.right().ResolvedValue()));
679 680 681
      }
      break;
    }
682 683
    case IrOpcode::kFloat64Cbrt: {
      Float64Matcher m(node->InputAt(0));
684 685
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::cbrt(m.ResolvedValue()));
686 687
      break;
    }
688 689
    case IrOpcode::kFloat64Cos: {
      Float64Matcher m(node->InputAt(0));
690 691
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::cos(m.ResolvedValue()));
692 693
      break;
    }
694 695
    case IrOpcode::kFloat64Cosh: {
      Float64Matcher m(node->InputAt(0));
696 697
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::cosh(m.ResolvedValue()));
698 699
      break;
    }
700 701
    case IrOpcode::kFloat64Exp: {
      Float64Matcher m(node->InputAt(0));
702 703
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::exp(m.ResolvedValue()));
704 705
      break;
    }
706 707
    case IrOpcode::kFloat64Expm1: {
      Float64Matcher m(node->InputAt(0));
708 709
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::expm1(m.ResolvedValue()));
710 711
      break;
    }
712 713
    case IrOpcode::kFloat64Log: {
      Float64Matcher m(node->InputAt(0));
714 715
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::log(m.ResolvedValue()));
716 717
      break;
    }
718 719
    case IrOpcode::kFloat64Log1p: {
      Float64Matcher m(node->InputAt(0));
720 721
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::log1p(m.ResolvedValue()));
722 723
      break;
    }
724 725
    case IrOpcode::kFloat64Log10: {
      Float64Matcher m(node->InputAt(0));
726 727
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::log10(m.ResolvedValue()));
728 729
      break;
    }
730
    case IrOpcode::kFloat64Log2: {
731
      Float64Matcher m(node->InputAt(0));
732 733
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::log2(m.ResolvedValue()));
734 735 736 737
      break;
    }
    case IrOpcode::kFloat64Pow: {
      Float64BinopMatcher m(node);
738
      if (m.IsFoldable()) {
739 740
        return ReplaceFloat64(base::ieee754::pow(m.left().ResolvedValue(),
                                                 m.right().ResolvedValue()));
741
      } else if (m.right().Is(0.0)) {  // x ** +-0.0 => 1.0
742
        return ReplaceFloat64(1.0);
743 744 745 746 747 748 749
      } else if (m.right().Is(2.0)) {  // x ** 2.0 => x * x
        node->ReplaceInput(1, m.left().node());
        NodeProperties::ChangeOp(node, machine()->Float64Mul());
        return Changed(node);
      } else if (m.right().Is(0.5)) {
        // x ** 0.5 => if x <= -Infinity then Infinity else sqrt(0.0 + x)
        return Replace(Float64PowHalf(m.left().node()));
750
      }
751 752
      break;
    }
753 754
    case IrOpcode::kFloat64Sin: {
      Float64Matcher m(node->InputAt(0));
755 756
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::sin(m.ResolvedValue()));
757 758
      break;
    }
759 760
    case IrOpcode::kFloat64Sinh: {
      Float64Matcher m(node->InputAt(0));
761 762
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::sinh(m.ResolvedValue()));
763 764
      break;
    }
765 766
    case IrOpcode::kFloat64Tan: {
      Float64Matcher m(node->InputAt(0));
767 768
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::tan(m.ResolvedValue()));
769 770
      break;
    }
771 772
    case IrOpcode::kFloat64Tanh: {
      Float64Matcher m(node->InputAt(0));
773 774
      if (m.HasResolvedValue())
        return ReplaceFloat64(base::ieee754::tanh(m.ResolvedValue()));
775 776
      break;
    }
777 778
    case IrOpcode::kChangeFloat32ToFloat64: {
      Float32Matcher m(node->InputAt(0));
779 780
      if (m.HasResolvedValue()) {
        if (!allow_signalling_nan_ && std::isnan(m.ResolvedValue())) {
781
          return ReplaceFloat64(SilenceNaN(m.ResolvedValue()));
782
        }
783
        return ReplaceFloat64(m.ResolvedValue());
784
      }
785 786
      break;
    }
787 788
    case IrOpcode::kChangeFloat64ToInt32: {
      Float64Matcher m(node->InputAt(0));
789 790
      if (m.HasResolvedValue())
        return ReplaceInt32(FastD2IChecked(m.ResolvedValue()));
791 792 793
      if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
      break;
    }
794 795
    case IrOpcode::kChangeFloat64ToInt64: {
      Float64Matcher m(node->InputAt(0));
796 797
      if (m.HasResolvedValue())
        return ReplaceInt64(static_cast<int64_t>(m.ResolvedValue()));
798
      if (m.IsChangeInt64ToFloat64()) return Replace(m.node()->InputAt(0));
799 800
      break;
    }
801 802
    case IrOpcode::kChangeFloat64ToUint32: {
      Float64Matcher m(node->InputAt(0));
803 804
      if (m.HasResolvedValue())
        return ReplaceInt32(FastD2UI(m.ResolvedValue()));
805 806 807 808 809
      if (m.IsChangeUint32ToFloat64()) return Replace(m.node()->InputAt(0));
      break;
    }
    case IrOpcode::kChangeInt32ToFloat64: {
      Int32Matcher m(node->InputAt(0));
810 811
      if (m.HasResolvedValue())
        return ReplaceFloat64(FastI2D(m.ResolvedValue()));
812 813
      break;
    }
814 815
    case IrOpcode::kBitcastWord32ToWord64: {
      Int32Matcher m(node->InputAt(0));
816
      if (m.HasResolvedValue()) return ReplaceInt64(m.ResolvedValue());
817 818
      break;
    }
819 820
    case IrOpcode::kChangeInt32ToInt64: {
      Int32Matcher m(node->InputAt(0));
821
      if (m.HasResolvedValue()) return ReplaceInt64(m.ResolvedValue());
822 823
      break;
    }
824 825
    case IrOpcode::kChangeInt64ToFloat64: {
      Int64Matcher m(node->InputAt(0));
826 827
      if (m.HasResolvedValue())
        return ReplaceFloat64(static_cast<double>(m.ResolvedValue()));
828 829 830
      if (m.IsChangeFloat64ToInt64()) return Replace(m.node()->InputAt(0));
      break;
    }
831 832
    case IrOpcode::kChangeUint32ToFloat64: {
      Uint32Matcher m(node->InputAt(0));
833 834
      if (m.HasResolvedValue())
        return ReplaceFloat64(FastUI2D(m.ResolvedValue()));
835 836 837 838
      break;
    }
    case IrOpcode::kChangeUint32ToUint64: {
      Uint32Matcher m(node->InputAt(0));
839 840
      if (m.HasResolvedValue())
        return ReplaceInt64(static_cast<uint64_t>(m.ResolvedValue()));
841 842
      break;
    }
843 844
    case IrOpcode::kTruncateFloat64ToWord32: {
      Float64Matcher m(node->InputAt(0));
845 846
      if (m.HasResolvedValue())
        return ReplaceInt32(DoubleToInt32(m.ResolvedValue()));
847 848 849
      if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
      return NoChange();
    }
850 851
    case IrOpcode::kTruncateInt64ToInt32:
      return ReduceTruncateInt64ToInt32(node);
852 853
    case IrOpcode::kTruncateFloat64ToFloat32: {
      Float64Matcher m(node->InputAt(0));
854
      if (m.HasResolvedValue()) {
855 856
        if (!allow_signalling_nan_ && m.IsNaN()) {
          return ReplaceFloat32(DoubleToFloat32(SilenceNaN(m.ResolvedValue())));
857
        }
858
        return ReplaceFloat32(DoubleToFloat32(m.ResolvedValue()));
859 860 861
      }
      if (allow_signalling_nan_ && m.IsChangeFloat32ToFloat64())
        return Replace(m.node()->InputAt(0));
862 863
      break;
    }
864 865
    case IrOpcode::kRoundFloat64ToInt32: {
      Float64Matcher m(node->InputAt(0));
866 867
      if (m.HasResolvedValue()) {
        return ReplaceInt32(DoubleToInt32(m.ResolvedValue()));
868
      }
869 870 871
      if (m.IsChangeInt32ToFloat64()) return Replace(m.node()->InputAt(0));
      break;
    }
872 873 874 875
    case IrOpcode::kFloat64InsertLowWord32:
      return ReduceFloat64InsertLowWord32(node);
    case IrOpcode::kFloat64InsertHighWord32:
      return ReduceFloat64InsertHighWord32(node);
876
    case IrOpcode::kStore:
877
    case IrOpcode::kUnalignedStore:
878
      return ReduceStore(node);
879 880 881 882
    case IrOpcode::kFloat64Equal:
    case IrOpcode::kFloat64LessThan:
    case IrOpcode::kFloat64LessThanOrEqual:
      return ReduceFloat64Compare(node);
883 884
    case IrOpcode::kFloat64RoundDown:
      return ReduceFloat64RoundDown(node);
885
    case IrOpcode::kBitcastTaggedToWord:
886
    case IrOpcode::kBitcastTaggedToWordForTagAndSmiBits: {
887 888 889 890 891 892 893
      NodeMatcher m(node->InputAt(0));
      if (m.IsBitcastWordToTaggedSigned()) {
        RelaxEffectsAndControls(node);
        return Replace(m.InputAt(0));
      }
      break;
    }
894 895 896 897 898 899
    case IrOpcode::kBranch:
    case IrOpcode::kDeoptimizeIf:
    case IrOpcode::kDeoptimizeUnless:
    case IrOpcode::kTrapIf:
    case IrOpcode::kTrapUnless:
      return ReduceConditional(node);
900 901
    case IrOpcode::kInt64LessThan: {
      Int64BinopMatcher m(node);
902
      if (m.IsFoldable()) {  // K < K => K  (K stands for arbitrary constants)
903 904
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
905
      }
906
      return ReduceWord64Comparisons(node);
907 908 909
    }
    case IrOpcode::kInt64LessThanOrEqual: {
      Int64BinopMatcher m(node);
910
      if (m.IsFoldable()) {  // K <= K => K  (K stands for arbitrary constants)
911 912
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
913 914 915 916 917
      }
      return ReduceWord64Comparisons(node);
    }
    case IrOpcode::kUint64LessThan: {
      Uint64BinopMatcher m(node);
918
      if (m.IsFoldable()) {  // K < K => K  (K stands for arbitrary constants)
919 920
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
921 922 923 924 925
      }
      return ReduceWord64Comparisons(node);
    }
    case IrOpcode::kUint64LessThanOrEqual: {
      Uint64BinopMatcher m(node);
926
      if (m.IsFoldable()) {  // K <= K => K  (K stands for arbitrary constants)
927 928
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
929 930 931
      }
      return ReduceWord64Comparisons(node);
    }
932 933 934 935 936 937 938 939 940 941 942 943 944 945
    case IrOpcode::kFloat32Select:
    case IrOpcode::kFloat64Select:
    case IrOpcode::kWord32Select:
    case IrOpcode::kWord64Select: {
      Int32Matcher match(node->InputAt(0));
      if (match.HasResolvedValue()) {
        if (match.Is(0)) {
          return Replace(node->InputAt(2));
        } else {
          return Replace(node->InputAt(1));
        }
      }
      break;
    }
946 947 948 949 950
    default:
      break;
  }
  return NoChange();
}
951

952 953
Reduction MachineOperatorReducer::ReduceTruncateInt64ToInt32(Node* node) {
  Int64Matcher m(node->InputAt(0));
954 955
  if (m.HasResolvedValue())
    return ReplaceInt32(static_cast<int32_t>(m.ResolvedValue()));
956 957 958 959
  if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
  return NoChange();
}

960 961 962 963
Reduction MachineOperatorReducer::ReduceInt32Add(Node* node) {
  DCHECK_EQ(IrOpcode::kInt32Add, node->opcode());
  Int32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => x
964
  if (m.IsFoldable()) {  // K + K => K  (K stands for arbitrary constants)
965 966
    return ReplaceInt32(base::AddWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
967
  }
968 969 970 971 972
  if (m.left().IsInt32Sub()) {
    Int32BinopMatcher mleft(m.left().node());
    if (mleft.left().Is(0)) {  // (0 - x) + y => y - x
      node->ReplaceInput(0, m.right().node());
      node->ReplaceInput(1, mleft.right().node());
973
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
974
      return Changed(node).FollowedBy(ReduceInt32Sub(node));
975 976 977 978 979 980
    }
  }
  if (m.right().IsInt32Sub()) {
    Int32BinopMatcher mright(m.right().node());
    if (mright.left().Is(0)) {  // y + (0 - x) => y - x
      node->ReplaceInput(1, mright.right().node());
981
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
982
      return Changed(node).FollowedBy(ReduceInt32Sub(node));
983 984
    }
  }
985
  // (x + Int32Constant(a)) + Int32Constant(b)) => x + Int32Constant(a + b)
986
  if (m.right().HasResolvedValue() && m.left().IsInt32Add()) {
987
    Int32BinopMatcher n(m.left().node());
988 989 990 991
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int32Constant(base::AddWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
992 993 994 995
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
996

997 998 999
  return NoChange();
}

1000 1001 1002 1003 1004
Reduction MachineOperatorReducer::ReduceInt64Add(Node* node) {
  DCHECK_EQ(IrOpcode::kInt64Add, node->opcode());
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x + 0 => 0
  if (m.IsFoldable()) {
1005 1006
    return ReplaceInt64(base::AddWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1007
  }
1008
  // (x + Int64Constant(a)) + Int64Constant(b) => x + Int64Constant(a + b)
1009
  if (m.right().HasResolvedValue() && m.left().IsInt64Add()) {
1010
    Int64BinopMatcher n(m.left().node());
1011 1012 1013 1014
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int64Constant(base::AddWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
1015 1016 1017 1018
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
1019 1020
  return NoChange();
}
1021

1022 1023 1024 1025
Reduction MachineOperatorReducer::ReduceInt32Sub(Node* node) {
  DCHECK_EQ(IrOpcode::kInt32Sub, node->opcode());
  Int32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
1026
  if (m.IsFoldable()) {  // K - K => K  (K stands for arbitrary constants)
1027 1028
    return ReplaceInt32(base::SubWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1029 1030
  }
  if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x - x => 0
1031
  if (m.right().HasResolvedValue()) {               // x - K => x + -K
1032
    node->ReplaceInput(
1033 1034
        1,
        Int32Constant(base::NegateWithWraparound(m.right().ResolvedValue())));
1035
    NodeProperties::ChangeOp(node, machine()->Int32Add());
1036
    return Changed(node).FollowedBy(ReduceInt32Add(node));
1037 1038 1039 1040
  }
  return NoChange();
}

1041 1042 1043 1044
Reduction MachineOperatorReducer::ReduceInt64Sub(Node* node) {
  DCHECK_EQ(IrOpcode::kInt64Sub, node->opcode());
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x - 0 => x
1045
  if (m.IsFoldable()) {  // K - K => K  (K stands for arbitrary constants)
1046 1047
    return ReplaceInt64(base::SubWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1048 1049
  }
  if (m.LeftEqualsRight()) return Replace(Int64Constant(0));  // x - x => 0
1050
  if (m.right().HasResolvedValue()) {                         // x - K => x + -K
1051
    node->ReplaceInput(
1052 1053
        1,
        Int64Constant(base::NegateWithWraparound(m.right().ResolvedValue())));
1054
    NodeProperties::ChangeOp(node, machine()->Int64Add());
1055
    return Changed(node).FollowedBy(ReduceInt64Add(node));
1056 1057 1058
  }
  return NoChange();
}
1059

1060 1061 1062 1063 1064
Reduction MachineOperatorReducer::ReduceInt64Mul(Node* node) {
  DCHECK_EQ(IrOpcode::kInt64Mul, node->opcode());
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.right().node());  // x * 0 => 0
  if (m.right().Is(1)) return Replace(m.left().node());   // x * 1 => x
1065
  if (m.IsFoldable()) {  // K * K => K  (K stands for arbitrary constants)
1066 1067
    return ReplaceInt64(base::MulWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1068 1069 1070 1071 1072 1073 1074 1075 1076
  }
  if (m.right().Is(-1)) {  // x * -1 => 0 - x
    node->ReplaceInput(0, Int64Constant(0));
    node->ReplaceInput(1, m.left().node());
    NodeProperties::ChangeOp(node, machine()->Int64Sub());
    return Changed(node);
  }
  if (m.right().IsPowerOf2()) {  // x * 2^n => x << n
    node->ReplaceInput(
1077 1078
        1,
        Int64Constant(base::bits::WhichPowerOfTwo(m.right().ResolvedValue())));
1079
    NodeProperties::ChangeOp(node, machine()->Word64Shl());
1080
    return Changed(node).FollowedBy(ReduceWord64Shl(node));
1081
  }
1082
  // (x * Int64Constant(a)) * Int64Constant(b)) => x * Int64Constant(a * b)
1083
  if (m.right().HasResolvedValue() && m.left().IsInt64Mul()) {
1084
    Int64BinopMatcher n(m.left().node());
1085 1086 1087 1088
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int64Constant(base::MulWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
1089 1090 1091 1092
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
1093 1094 1095
  return NoChange();
}

1096 1097
Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
  Int32BinopMatcher m(node);
1098
  if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
1099 1100
  if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
  if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
1101
  if (m.IsFoldable()) {  // K / K => K  (K stands for arbitrary constants)
1102 1103
    return ReplaceInt32(base::bits::SignedDiv32(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1104 1105 1106 1107
  }
  if (m.LeftEqualsRight()) {  // x / x => x != 0
    Node* const zero = Int32Constant(0);
    return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
1108 1109 1110 1111
  }
  if (m.right().Is(-1)) {  // x / -1 => 0 - x
    node->ReplaceInput(0, Int32Constant(0));
    node->ReplaceInput(1, m.left().node());
1112
    node->TrimInputCount(2);
1113
    NodeProperties::ChangeOp(node, machine()->Int32Sub());
1114 1115
    return Changed(node);
  }
1116 1117
  if (m.right().HasResolvedValue()) {
    int32_t const divisor = m.right().ResolvedValue();
1118 1119
    Node* const dividend = m.left().node();
    Node* quotient = dividend;
1120
    if (base::bits::IsPowerOfTwo(Abs(divisor))) {
1121
      uint32_t const shift = base::bits::WhichPowerOfTwo(Abs(divisor));
1122
      DCHECK_NE(0u, shift);
1123 1124 1125 1126 1127 1128
      if (shift > 1) {
        quotient = Word32Sar(quotient, 31);
      }
      quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend);
      quotient = Word32Sar(quotient, shift);
    } else {
1129
      quotient = Int32Div(quotient, Abs(divisor));
1130 1131 1132 1133
    }
    if (divisor < 0) {
      node->ReplaceInput(0, Int32Constant(0));
      node->ReplaceInput(1, quotient);
1134
      node->TrimInputCount(2);
1135
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1136 1137 1138 1139 1140 1141 1142
      return Changed(node);
    }
    return Replace(quotient);
  }
  return NoChange();
}

1143 1144 1145 1146 1147
Reduction MachineOperatorReducer::ReduceUint32Div(Node* node) {
  Uint32BinopMatcher m(node);
  if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
  if (m.right().Is(0)) return Replace(m.right().node());  // x / 0 => 0
  if (m.right().Is(1)) return Replace(m.left().node());   // x / 1 => x
1148
  if (m.IsFoldable()) {  // K / K => K  (K stands for arbitrary constants)
1149 1150
    return ReplaceUint32(base::bits::UnsignedDiv32(m.left().ResolvedValue(),
                                                   m.right().ResolvedValue()));
1151 1152 1153 1154 1155
  }
  if (m.LeftEqualsRight()) {  // x / x => x != 0
    Node* const zero = Int32Constant(0);
    return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
  }
1156
  if (m.right().HasResolvedValue()) {
1157
    Node* const dividend = m.left().node();
1158
    uint32_t const divisor = m.right().ResolvedValue();
1159
    if (base::bits::IsPowerOfTwo(divisor)) {  // x / 2^n => x >> n
1160 1161
      node->ReplaceInput(1, Uint32Constant(base::bits::WhichPowerOfTwo(
                                m.right().ResolvedValue())));
1162
      node->TrimInputCount(2);
1163
      NodeProperties::ChangeOp(node, machine()->Word32Shr());
1164 1165 1166 1167
      return Changed(node);
    } else {
      return Replace(Uint32Div(dividend, divisor));
    }
1168 1169 1170 1171
  }
  return NoChange();
}

1172
Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
1173
  Int32BinopMatcher m(node);
1174 1175 1176 1177 1178
  if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x  => 0
  if (m.right().Is(0)) return Replace(m.right().node());  // x % 0  => 0
  if (m.right().Is(1)) return ReplaceInt32(0);            // x % 1  => 0
  if (m.right().Is(-1)) return ReplaceInt32(0);           // x % -1 => 0
  if (m.LeftEqualsRight()) return ReplaceInt32(0);        // x % x  => 0
1179
  if (m.IsFoldable()) {  // K % K => K  (K stands for arbitrary constants)
1180 1181
    return ReplaceInt32(base::bits::SignedMod32(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1182
  }
1183
  if (m.right().HasResolvedValue()) {
1184
    Node* const dividend = m.left().node();
1185
    uint32_t const divisor = Abs(m.right().ResolvedValue());
1186
    if (base::bits::IsPowerOfTwo(divisor)) {
1187 1188
      uint32_t const mask = divisor - 1;
      Node* const zero = Int32Constant(0);
1189 1190 1191 1192 1193 1194 1195
      Diamond d(graph(), common(),
                graph()->NewNode(machine()->Int32LessThan(), dividend, zero),
                BranchHint::kFalse);
      return Replace(
          d.Phi(MachineRepresentation::kWord32,
                Int32Sub(zero, Word32And(Int32Sub(zero, dividend), mask)),
                Word32And(dividend, mask)));
1196
    } else {
1197
      Node* quotient = Int32Div(dividend, divisor);
1198 1199
      DCHECK_EQ(dividend, node->InputAt(0));
      node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
1200
      node->TrimInputCount(2);
1201
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1202
    }
1203
    return Changed(node);
1204 1205 1206 1207
  }
  return NoChange();
}

1208 1209 1210 1211 1212 1213
Reduction MachineOperatorReducer::ReduceUint32Mod(Node* node) {
  Uint32BinopMatcher m(node);
  if (m.left().Is(0)) return Replace(m.left().node());    // 0 % x => 0
  if (m.right().Is(0)) return Replace(m.right().node());  // x % 0 => 0
  if (m.right().Is(1)) return ReplaceUint32(0);           // x % 1 => 0
  if (m.LeftEqualsRight()) return ReplaceInt32(0);        // x % x  => 0
1214
  if (m.IsFoldable()) {  // K % K => K  (K stands for arbitrary constants)
1215 1216
    return ReplaceUint32(base::bits::UnsignedMod32(m.left().ResolvedValue(),
                                                   m.right().ResolvedValue()));
1217
  }
1218
  if (m.right().HasResolvedValue()) {
1219
    Node* const dividend = m.left().node();
1220
    uint32_t const divisor = m.right().ResolvedValue();
1221
    if (base::bits::IsPowerOfTwo(divisor)) {  // x % 2^n => x & 2^n-1
1222
      node->ReplaceInput(1, Uint32Constant(m.right().ResolvedValue() - 1));
1223 1224
      node->TrimInputCount(2);
      NodeProperties::ChangeOp(node, machine()->Word32And());
1225 1226 1227 1228
    } else {
      Node* quotient = Uint32Div(dividend, divisor);
      DCHECK_EQ(dividend, node->InputAt(0));
      node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor)));
1229 1230
      node->TrimInputCount(2);
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1231
    }
1232 1233 1234 1235 1236
    return Changed(node);
  }
  return NoChange();
}

1237
Reduction MachineOperatorReducer::ReduceStore(Node* node) {
1238
  NodeMatcher nm(node);
1239 1240 1241 1242
  DCHECK(nm.IsStore() || nm.IsUnalignedStore());
  MachineRepresentation rep =
      nm.IsStore() ? StoreRepresentationOf(node->op()).representation()
                   : UnalignedStoreRepresentationOf(node->op());
1243

1244
  const int value_input = 2;
1245 1246
  Node* const value = node->InputAt(value_input);

1247 1248 1249
  switch (value->opcode()) {
    case IrOpcode::kWord32And: {
      Uint32BinopMatcher m(value);
1250 1251 1252 1253 1254
      if (m.right().HasResolvedValue() &&
          ((rep == MachineRepresentation::kWord8 &&
            (m.right().ResolvedValue() & 0xFF) == 0xFF) ||
           (rep == MachineRepresentation::kWord16 &&
            (m.right().ResolvedValue() & 0xFFFF) == 0xFFFF))) {
1255
        node->ReplaceInput(value_input, m.left().node());
1256 1257 1258 1259 1260 1261
        return Changed(node);
      }
      break;
    }
    case IrOpcode::kWord32Sar: {
      Int32BinopMatcher m(value);
1262 1263 1264 1265
      if (m.left().IsWord32Shl() && ((rep == MachineRepresentation::kWord8 &&
                                      m.right().IsInRange(1, 24)) ||
                                     (rep == MachineRepresentation::kWord16 &&
                                      m.right().IsInRange(1, 16)))) {
1266
        Int32BinopMatcher mleft(m.left().node());
1267
        if (mleft.right().Is(m.right().ResolvedValue())) {
1268
          node->ReplaceInput(value_input, mleft.left().node());
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279
          return Changed(node);
        }
      }
      break;
    }
    default:
      break;
  }
  return NoChange();
}

1280 1281 1282 1283 1284 1285 1286
Reduction MachineOperatorReducer::ReduceProjection(size_t index, Node* node) {
  switch (node->opcode()) {
    case IrOpcode::kInt32AddWithOverflow: {
      DCHECK(index == 0 || index == 1);
      Int32BinopMatcher m(node);
      if (m.IsFoldable()) {
        int32_t val;
1287 1288
        bool ovf = base::bits::SignedAddOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1289
        return ReplaceInt32(index == 0 ? val : ovf);
1290 1291
      }
      if (m.right().Is(0)) {
1292
        return Replace(index == 0 ? m.left().node() : m.right().node());
1293 1294 1295 1296 1297 1298 1299 1300
      }
      break;
    }
    case IrOpcode::kInt32SubWithOverflow: {
      DCHECK(index == 0 || index == 1);
      Int32BinopMatcher m(node);
      if (m.IsFoldable()) {
        int32_t val;
1301 1302
        bool ovf = base::bits::SignedSubOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314
        return ReplaceInt32(index == 0 ? val : ovf);
      }
      if (m.right().Is(0)) {
        return Replace(index == 0 ? m.left().node() : m.right().node());
      }
      break;
    }
    case IrOpcode::kInt32MulWithOverflow: {
      DCHECK(index == 0 || index == 1);
      Int32BinopMatcher m(node);
      if (m.IsFoldable()) {
        int32_t val;
1315 1316
        bool ovf = base::bits::SignedMulOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1317
        return ReplaceInt32(index == 0 ? val : ovf);
1318 1319
      }
      if (m.right().Is(0)) {
1320 1321 1322 1323
        return Replace(m.right().node());
      }
      if (m.right().Is(1)) {
        return index == 0 ? Replace(m.left().node()) : ReplaceInt32(0);
1324 1325 1326 1327 1328 1329 1330 1331 1332
      }
      break;
    }
    default:
      break;
  }
  return NoChange();
}

1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352
namespace {

// Returns true if "value << shift >> shift == value". This can be interpreted
// as "left shifting |value| by |shift| doesn't shift away significant bits".
// Or, equivalently, "left shifting |value| by |shift| doesn't have signed
// overflow".
bool CanRevertLeftShiftWithRightShift(int32_t value, int32_t shift) {
  if (shift < 0 || shift >= 32) {
    // This shift would be UB in C++
    return false;
  }
  if (static_cast<int32_t>(static_cast<uint32_t>(value) << shift) >> shift !=
      static_cast<int32_t>(value)) {
    return false;
  }
  return true;
}

}  // namespace

1353 1354 1355 1356 1357 1358
Reduction MachineOperatorReducer::ReduceWord32Comparisons(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kInt32LessThan ||
         node->opcode() == IrOpcode::kInt32LessThanOrEqual ||
         node->opcode() == IrOpcode::kUint32LessThan ||
         node->opcode() == IrOpcode::kUint32LessThanOrEqual);
  Int32BinopMatcher m(node);
1359
  // (x >> K) < (y >> K) => x < y   if only zeros shifted out
1360 1361 1362 1363
  if (m.left().op() == machine()->Word32SarShiftOutZeros() &&
      m.right().op() == machine()->Word32SarShiftOutZeros()) {
    Int32BinopMatcher mleft(m.left().node());
    Int32BinopMatcher mright(m.right().node());
1364 1365
    if (mleft.right().HasResolvedValue() &&
        mright.right().Is(mleft.right().ResolvedValue())) {
1366 1367 1368 1369 1370
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, mright.left().node());
      return Changed(node);
    }
  }
1371 1372 1373
  // Simplifying (x >> n) <= k into x <= (k << n), with "k << n" being
  // computed here at compile time.
  if (m.right().HasResolvedValue() &&
1374 1375
      m.left().op() == machine()->Word32SarShiftOutZeros() &&
      m.left().node()->UseCount() == 1) {
1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389
    uint32_t right = m.right().ResolvedValue();
    Int32BinopMatcher mleft(m.left().node());
    if (mleft.right().HasResolvedValue()) {
      auto shift = mleft.right().ResolvedValue();
      if (CanRevertLeftShiftWithRightShift(right, shift)) {
        node->ReplaceInput(0, mleft.left().node());
        node->ReplaceInput(1, Int32Constant(right << shift));
        return Changed(node);
      }
    }
  }
  // Simplifying k <= (x >> n) into (k << n) <= x, with "k << n" being
  // computed here at compile time.
  if (m.left().HasResolvedValue() &&
1390 1391
      m.right().op() == machine()->Word32SarShiftOutZeros() &&
      m.right().node()->UseCount() == 1) {
1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402
    uint32_t left = m.left().ResolvedValue();
    Int32BinopMatcher mright(m.right().node());
    if (mright.right().HasResolvedValue()) {
      auto shift = mright.right().ResolvedValue();
      if (CanRevertLeftShiftWithRightShift(left, shift)) {
        node->ReplaceInput(0, Int32Constant(left << shift));
        node->ReplaceInput(1, mright.left().node());
        return Changed(node);
      }
    }
  }
1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441
  return NoChange();
}

const Operator* MachineOperatorReducer::Map64To32Comparison(
    const Operator* op, bool sign_extended) {
  switch (op->opcode()) {
    case IrOpcode::kInt64LessThan:
      return sign_extended ? machine()->Int32LessThan()
                           : machine()->Uint32LessThan();
    case IrOpcode::kInt64LessThanOrEqual:
      return sign_extended ? machine()->Int32LessThanOrEqual()
                           : machine()->Uint32LessThanOrEqual();
    case IrOpcode::kUint64LessThan:
      return machine()->Uint32LessThan();
    case IrOpcode::kUint64LessThanOrEqual:
      return machine()->Uint32LessThanOrEqual();
    default:
      UNREACHABLE();
  }
}

Reduction MachineOperatorReducer::ReduceWord64Comparisons(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kInt64LessThan ||
         node->opcode() == IrOpcode::kInt64LessThanOrEqual ||
         node->opcode() == IrOpcode::kUint64LessThan ||
         node->opcode() == IrOpcode::kUint64LessThanOrEqual);
  Int64BinopMatcher m(node);

  bool sign_extended =
      m.left().IsChangeInt32ToInt64() && m.right().IsChangeInt32ToInt64();
  if (sign_extended || (m.left().IsChangeUint32ToUint64() &&
                        m.right().IsChangeUint32ToUint64())) {
    node->ReplaceInput(0, NodeProperties::GetValueInput(m.left().node(), 0));
    node->ReplaceInput(1, NodeProperties::GetValueInput(m.right().node(), 0));
    NodeProperties::ChangeOp(node,
                             Map64To32Comparison(node->op(), sign_extended));
    return Changed(node).FollowedBy(Reduce(node));
  }

1442
  // (x >> K) < (y >> K) => x < y   if only zeros shifted out
1443 1444 1445 1446 1447
  // This is useful for Smi untagging, which results in such a shift.
  if (m.left().op() == machine()->Word64SarShiftOutZeros() &&
      m.right().op() == machine()->Word64SarShiftOutZeros()) {
    Int64BinopMatcher mleft(m.left().node());
    Int64BinopMatcher mright(m.right().node());
1448 1449
    if (mleft.right().HasResolvedValue() &&
        mright.right().Is(mleft.right().ResolvedValue())) {
1450 1451 1452 1453 1454 1455 1456 1457 1458
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, mright.left().node());
      return Changed(node);
    }
  }

  return NoChange();
}

1459 1460 1461 1462 1463
Reduction MachineOperatorReducer::ReduceWord32Shifts(Node* node) {
  DCHECK((node->opcode() == IrOpcode::kWord32Shl) ||
         (node->opcode() == IrOpcode::kWord32Shr) ||
         (node->opcode() == IrOpcode::kWord32Sar));
  if (machine()->Word32ShiftIsSafe()) {
1464
    // Remove the explicit 'and' with 0x1F if the shift provided by the machine
1465 1466 1467 1468
    // instruction matches that required by JavaScript.
    Int32BinopMatcher m(node);
    if (m.right().IsWord32And()) {
      Int32BinopMatcher mright(m.right().node());
1469
      if (mright.right().Is(0x1F)) {
1470 1471 1472 1473 1474 1475 1476 1477
        node->ReplaceInput(1, mright.left().node());
        return Changed(node);
      }
    }
  }
  return NoChange();
}

1478 1479 1480 1481
Reduction MachineOperatorReducer::ReduceWord32Shl(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32Shl, node->opcode());
  Int32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
1482
  if (m.IsFoldable()) {  // K << K => K  (K stands for arbitrary constants)
1483 1484
    return ReplaceInt32(base::ShlWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1485 1486 1487 1488
  }
  if (m.right().IsInRange(1, 31)) {
    if (m.left().IsWord32Sar() || m.left().IsWord32Shr()) {
      Int32BinopMatcher mleft(m.left().node());
1489 1490 1491 1492 1493 1494 1495 1496 1497 1498

      // If x >> K only shifted out zeros:
      // (x >> K) << L => x           if K == L
      // (x >> K) << L => x >> (K-L) if K > L
      // (x >> K) << L => x << (L-K)  if K < L
      // Since this is used for Smi untagging, we currently only need it for
      // signed shifts.
      if (mleft.op() == machine()->Word32SarShiftOutZeros() &&
          mleft.right().IsInRange(1, 31)) {
        Node* x = mleft.left().node();
1499 1500
        int k = mleft.right().ResolvedValue();
        int l = m.right().ResolvedValue();
1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517
        if (k == l) {
          return Replace(x);
        } else if (k > l) {
          node->ReplaceInput(0, x);
          node->ReplaceInput(1, Uint32Constant(k - l));
          NodeProperties::ChangeOp(node, machine()->Word32Sar());
          return Changed(node).FollowedBy(ReduceWord32Sar(node));
        } else {
          DCHECK(k < l);
          node->ReplaceInput(0, x);
          node->ReplaceInput(1, Uint32Constant(l - k));
          return Changed(node);
        }
      }

      // (x >>> K) << K => x & ~(2^K - 1)
      // (x >> K) << K => x & ~(2^K - 1)
1518
      if (mleft.right().Is(m.right().ResolvedValue())) {
1519 1520
        node->ReplaceInput(0, mleft.left().node());
        node->ReplaceInput(1,
1521
                           Uint32Constant(std::numeric_limits<uint32_t>::max()
1522
                                          << m.right().ResolvedValue()));
1523
        NodeProperties::ChangeOp(node, machine()->Word32And());
1524
        return Changed(node).FollowedBy(ReduceWord32And(node));
1525 1526 1527 1528 1529 1530
      }
    }
  }
  return ReduceWord32Shifts(node);
}

1531 1532 1533 1534
Reduction MachineOperatorReducer::ReduceWord64Shl(Node* node) {
  DCHECK_EQ(IrOpcode::kWord64Shl, node->opcode());
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x << 0 => x
1535
  if (m.IsFoldable()) {  // K << K => K  (K stands for arbitrary constants)
1536 1537
    return ReplaceInt64(base::ShlWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1538
  }
1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551
  if (m.right().IsInRange(1, 63) &&
      (m.left().IsWord64Sar() || m.left().IsWord64Shr())) {
    Int64BinopMatcher mleft(m.left().node());

    // If x >> K only shifted out zeros:
    // (x >> K) << L => x           if K == L
    // (x >> K) << L => x >> (K-L) if K > L
    // (x >> K) << L => x << (L-K)  if K < L
    // Since this is used for Smi untagging, we currently only need it for
    // signed shifts.
    if (mleft.op() == machine()->Word64SarShiftOutZeros() &&
        mleft.right().IsInRange(1, 63)) {
      Node* x = mleft.left().node();
1552 1553
      int64_t k = mleft.right().ResolvedValue();
      int64_t l = m.right().ResolvedValue();
1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570
      if (k == l) {
        return Replace(x);
      } else if (k > l) {
        node->ReplaceInput(0, x);
        node->ReplaceInput(1, Uint64Constant(k - l));
        NodeProperties::ChangeOp(node, machine()->Word64Sar());
        return Changed(node).FollowedBy(ReduceWord64Sar(node));
      } else {
        DCHECK(k < l);
        node->ReplaceInput(0, x);
        node->ReplaceInput(1, Uint64Constant(l - k));
        return Changed(node);
      }
    }

    // (x >>> K) << K => x & ~(2^K - 1)
    // (x >> K) << K => x & ~(2^K - 1)
1571
    if (mleft.right().Is(m.right().ResolvedValue())) {
1572 1573
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, Uint64Constant(std::numeric_limits<uint64_t>::max()
1574
                                           << m.right().ResolvedValue()));
1575 1576 1577 1578
      NodeProperties::ChangeOp(node, machine()->Word64And());
      return Changed(node).FollowedBy(ReduceWord64And(node));
    }
  }
1579 1580 1581
  return NoChange();
}

1582 1583 1584
Reduction MachineOperatorReducer::ReduceWord32Shr(Node* node) {
  Uint32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
1585
  if (m.IsFoldable()) {  // K >>> K => K  (K stands for arbitrary constants)
1586 1587
    return ReplaceInt32(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 31));
1588
  }
1589
  if (m.left().IsWord32And() && m.right().HasResolvedValue()) {
1590
    Uint32BinopMatcher mleft(m.left().node());
1591 1592 1593
    if (mleft.right().HasResolvedValue()) {
      uint32_t shift = m.right().ResolvedValue() & 31;
      uint32_t mask = mleft.right().ResolvedValue();
1594 1595 1596 1597 1598 1599 1600 1601
      if ((mask >> shift) == 0) {
        // (m >>> s) == 0 implies ((x & m) >>> s) == 0
        return ReplaceInt32(0);
      }
    }
  }
  return ReduceWord32Shifts(node);
}
1602

1603 1604 1605 1606
Reduction MachineOperatorReducer::ReduceWord64Shr(Node* node) {
  DCHECK_EQ(IrOpcode::kWord64Shr, node->opcode());
  Uint64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >>> 0 => x
1607
  if (m.IsFoldable()) {  // K >> K => K  (K stands for arbitrary constants)
1608 1609
    return ReplaceInt64(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 63));
1610 1611 1612 1613
  }
  return NoChange();
}

1614 1615 1616
Reduction MachineOperatorReducer::ReduceWord32Sar(Node* node) {
  Int32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
1617
  if (m.IsFoldable()) {  // K >> K => K  (K stands for arbitrary constants)
1618 1619
    return ReplaceInt32(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 31));
1620 1621 1622 1623 1624 1625 1626 1627
  }
  if (m.left().IsWord32Shl()) {
    Int32BinopMatcher mleft(m.left().node());
    if (mleft.left().IsComparison()) {
      if (m.right().Is(31) && mleft.right().Is(31)) {
        // Comparison << 31 >> 31 => 0 - Comparison
        node->ReplaceInput(0, Int32Constant(0));
        node->ReplaceInput(1, mleft.left().node());
1628
        NodeProperties::ChangeOp(node, machine()->Int32Sub());
1629
        return Changed(node).FollowedBy(ReduceInt32Sub(node));
1630 1631 1632
      }
    } else if (mleft.left().IsLoad()) {
      LoadRepresentation const rep =
1633 1634 1635
          LoadRepresentationOf(mleft.left().node()->op());
      if (m.right().Is(24) && mleft.right().Is(24) &&
          rep == MachineType::Int8()) {
1636 1637 1638
        // Load[kMachInt8] << 24 >> 24 => Load[kMachInt8]
        return Replace(mleft.left().node());
      }
1639 1640
      if (m.right().Is(16) && mleft.right().Is(16) &&
          rep == MachineType::Int16()) {
1641 1642 1643 1644 1645 1646 1647 1648
        // Load[kMachInt16] << 16 >> 16 => Load[kMachInt8]
        return Replace(mleft.left().node());
      }
    }
  }
  return ReduceWord32Shifts(node);
}

1649 1650 1651 1652
Reduction MachineOperatorReducer::ReduceWord64Sar(Node* node) {
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
  if (m.IsFoldable()) {
1653 1654
    return ReplaceInt64(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 63));
1655 1656 1657
  }
  return NoChange();
}
1658

1659 1660 1661 1662 1663 1664
template <typename WordNAdapter>
Reduction MachineOperatorReducer::ReduceWordNAnd(Node* node) {
  using A = WordNAdapter;
  A a(this);

  typename A::IntNBinopMatcher m(node);
1665 1666
  if (m.right().Is(0)) return Replace(m.right().node());  // x & 0  => 0
  if (m.right().Is(-1)) return Replace(m.left().node());  // x & -1 => x
1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680
  if (m.right().Is(1)) {
    // (x + x) & 1 => 0
    Node* left = m.left().node();
    while (left->opcode() == IrOpcode::kTruncateInt64ToInt32 ||
           left->opcode() == IrOpcode::kChangeInt32ToInt64 ||
           left->opcode() == IrOpcode::kChangeUint32ToUint64) {
      left = left->InputAt(0);
    }
    if ((left->opcode() == IrOpcode::kInt32Add ||
         left->opcode() == IrOpcode::kInt64Add) &&
        left->InputAt(0) == left->InputAt(1)) {
      return a.ReplaceIntN(0);
    }
  }
1681 1682 1683
  if (m.left().IsComparison() && m.right().Is(1)) {       // CMP & 1 => CMP
    return Replace(m.left().node());
  }
1684
  if (m.IsFoldable()) {  // K & K  => K  (K stands for arbitrary constants)
1685
    return a.ReplaceIntN(m.left().ResolvedValue() & m.right().ResolvedValue());
1686 1687
  }
  if (m.LeftEqualsRight()) return Replace(m.left().node());  // x & x => x
1688
  if (A::IsWordNAnd(m.left()) && m.right().HasResolvedValue()) {
1689
    typename A::IntNBinopMatcher mleft(m.left().node());
1690
    if (mleft.right().HasResolvedValue()) {  // (x & K) & K => x & K
1691
      node->ReplaceInput(0, mleft.left().node());
1692 1693
      node->ReplaceInput(1, a.IntNConstant(m.right().ResolvedValue() &
                                           mleft.right().ResolvedValue()));
1694
      return Changed(node).FollowedBy(a.ReduceWordNAnd(node));
1695 1696
    }
  }
1697
  if (m.right().IsNegativePowerOf2()) {
1698
    typename A::intN_t const mask = m.right().ResolvedValue();
1699 1700 1701
    typename A::intN_t const neg_mask = base::NegateWithWraparound(mask);
    if (A::IsWordNShl(m.left())) {
      typename A::UintNBinopMatcher mleft(m.left().node());
1702 1703
      if (mleft.right().HasResolvedValue() &&
          (mleft.right().ResolvedValue() & (A::WORD_SIZE - 1)) >=
1704
              base::bits::CountTrailingZeros(mask)) {
1705
        // (x << L) & (-1 << K) => x << L iff L >= K
1706 1707
        return Replace(mleft.node());
      }
1708 1709
    } else if (A::IsIntNAdd(m.left())) {
      typename A::IntNBinopMatcher mleft(m.left().node());
1710 1711 1712
      if (mleft.right().HasResolvedValue() &&
          (mleft.right().ResolvedValue() & mask) ==
              mleft.right().ResolvedValue()) {
1713
        // (x + (K << L)) & (-1 << L) => (x & (-1 << L)) + (K << L)
1714 1715
        node->ReplaceInput(0,
                           a.WordNAnd(mleft.left().node(), m.right().node()));
1716
        node->ReplaceInput(1, mleft.right().node());
1717
        NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1718
        return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1719
      }
1720 1721
      if (A::IsIntNMul(mleft.left())) {
        typename A::IntNBinopMatcher mleftleft(mleft.left().node());
1722
        if (mleftleft.right().IsMultipleOf(neg_mask)) {
1723
          // (y * (K << L) + x) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1724 1725
          node->ReplaceInput(
              0, a.WordNAnd(mleft.right().node(), m.right().node()));
1726
          node->ReplaceInput(1, mleftleft.node());
1727
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1728
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1729
        }
1730
      }
1731 1732
      if (A::IsIntNMul(mleft.right())) {
        typename A::IntNBinopMatcher mleftright(mleft.right().node());
1733
        if (mleftright.right().IsMultipleOf(neg_mask)) {
1734 1735
          // (x + y * (K << L)) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
          node->ReplaceInput(0,
1736
                             a.WordNAnd(mleft.left().node(), m.right().node()));
1737
          node->ReplaceInput(1, mleftright.node());
1738
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1739
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1740 1741
        }
      }
1742 1743
      if (A::IsWordNShl(mleft.left())) {
        typename A::IntNBinopMatcher mleftleft(mleft.left().node());
1744
        if (mleftleft.right().Is(base::bits::CountTrailingZeros(mask))) {
1745
          // (y << L + x) & (-1 << L) => (x & (-1 << L)) + y << L
1746 1747
          node->ReplaceInput(
              0, a.WordNAnd(mleft.right().node(), m.right().node()));
1748
          node->ReplaceInput(1, mleftleft.node());
1749
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1750
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1751 1752
        }
      }
1753 1754
      if (A::IsWordNShl(mleft.right())) {
        typename A::IntNBinopMatcher mleftright(mleft.right().node());
1755
        if (mleftright.right().Is(base::bits::CountTrailingZeros(mask))) {
1756 1757
          // (x + y << L) & (-1 << L) => (x & (-1 << L)) + y << L
          node->ReplaceInput(0,
1758
                             a.WordNAnd(mleft.left().node(), m.right().node()));
1759
          node->ReplaceInput(1, mleftright.node());
1760
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1761
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1762
        }
1763
      }
1764 1765
    } else if (A::IsIntNMul(m.left())) {
      typename A::IntNBinopMatcher mleft(m.left().node());
1766
      if (mleft.right().IsMultipleOf(neg_mask)) {
1767 1768 1769
        // (x * (K << L)) & (-1 << L) => x * (K << L)
        return Replace(mleft.node());
      }
1770
    }
1771 1772 1773 1774
  }
  return NoChange();
}

1775 1776 1777
namespace {

// Represents an operation of the form `(source & mask) == masked_value`.
1778
// where each bit set in masked_value also has to be set in mask.
1779
struct BitfieldCheck {
1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792
  Node* const source;
  uint32_t const mask;
  uint32_t const masked_value;
  bool const truncate_from_64_bit;

  BitfieldCheck(Node* source, uint32_t mask, uint32_t masked_value,
                bool truncate_from_64_bit)
      : source(source),
        mask(mask),
        masked_value(masked_value),
        truncate_from_64_bit(truncate_from_64_bit) {
    CHECK_EQ(masked_value & ~mask, 0);
  }
1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805

  static base::Optional<BitfieldCheck> Detect(Node* node) {
    // There are two patterns to check for here:
    // 1. Single-bit checks: `(val >> shift) & 1`, where:
    //    - the shift may be omitted, and/or
    //    - the result may be truncated from 64 to 32
    // 2. Equality checks: `(val & mask) == expected`, where:
    //    - val may be truncated from 64 to 32 before masking (see
    //      ReduceWord32EqualForConstantRhs)
    if (node->opcode() == IrOpcode::kWord32Equal) {
      Uint32BinopMatcher eq(node);
      if (eq.left().IsWord32And()) {
        Uint32BinopMatcher mand(eq.left().node());
1806
        if (mand.right().HasResolvedValue() && eq.right().HasResolvedValue()) {
1807 1808 1809
          uint32_t mask = mand.right().ResolvedValue();
          uint32_t masked_value = eq.right().ResolvedValue();
          if ((masked_value & ~mask) != 0) return {};
1810
          if (mand.left().IsTruncateInt64ToInt32()) {
1811 1812 1813 1814 1815
            return BitfieldCheck(
                NodeProperties::GetValueInput(mand.left().node(), 0), mask,
                masked_value, true);
          } else {
            return BitfieldCheck(mand.left().node(), mask, masked_value, false);
1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851
          }
        }
      }
    } else {
      if (node->opcode() == IrOpcode::kTruncateInt64ToInt32) {
        return TryDetectShiftAndMaskOneBit<Word64Adapter>(
            NodeProperties::GetValueInput(node, 0));
      } else {
        return TryDetectShiftAndMaskOneBit<Word32Adapter>(node);
      }
    }
    return {};
  }

  base::Optional<BitfieldCheck> TryCombine(const BitfieldCheck& other) {
    if (source != other.source ||
        truncate_from_64_bit != other.truncate_from_64_bit)
      return {};
    uint32_t overlapping_bits = mask & other.mask;
    // It would be kind of strange to have any overlapping bits, but they can be
    // allowed as long as they don't require opposite values in the same
    // positions.
    if ((masked_value & overlapping_bits) !=
        (other.masked_value & overlapping_bits))
      return {};
    return BitfieldCheck{source, mask | other.mask,
                         masked_value | other.masked_value,
                         truncate_from_64_bit};
  }

 private:
  template <typename WordNAdapter>
  static base::Optional<BitfieldCheck> TryDetectShiftAndMaskOneBit(Node* node) {
    // Look for the pattern `(val >> shift) & 1`. The shift may be omitted.
    if (WordNAdapter::IsWordNAnd(NodeMatcher(node))) {
      typename WordNAdapter::IntNBinopMatcher mand(node);
1852 1853
      if (mand.right().HasResolvedValue() &&
          mand.right().ResolvedValue() == 1) {
1854 1855 1856
        if (WordNAdapter::IsWordNShr(mand.left()) ||
            WordNAdapter::IsWordNSar(mand.left())) {
          typename WordNAdapter::UintNBinopMatcher shift(mand.left().node());
1857 1858 1859
          if (shift.right().HasResolvedValue() &&
              shift.right().ResolvedValue() < 32u) {
            uint32_t mask = 1 << shift.right().ResolvedValue();
1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873
            return BitfieldCheck{shift.left().node(), mask, mask,
                                 WordNAdapter::WORD_SIZE == 64};
          }
        }
        return BitfieldCheck{mand.left().node(), 1, 1,
                             WordNAdapter::WORD_SIZE == 64};
      }
    }
    return {};
  }
};

}  // namespace

1874 1875
Reduction MachineOperatorReducer::ReduceWord32And(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32And, node->opcode());
1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899
  Reduction reduction = ReduceWordNAnd<Word32Adapter>(node);
  if (reduction.Changed()) {
    return reduction;
  }

  // Attempt to detect multiple bitfield checks from the same bitfield struct
  // and fold them into a single check.
  Int32BinopMatcher m(node);
  if (auto right_bitfield = BitfieldCheck::Detect(m.right().node())) {
    if (auto left_bitfield = BitfieldCheck::Detect(m.left().node())) {
      if (auto combined_bitfield = left_bitfield->TryCombine(*right_bitfield)) {
        Node* source = combined_bitfield->source;
        if (combined_bitfield->truncate_from_64_bit) {
          source = TruncateInt64ToInt32(source);
        }
        node->ReplaceInput(0, Word32And(source, combined_bitfield->mask));
        node->ReplaceInput(1, Int32Constant(combined_bitfield->masked_value));
        NodeProperties::ChangeOp(node, machine()->Word32Equal());
        return Changed(node).FollowedBy(ReduceWord32Equal(node));
      }
    }
  }

  return NoChange();
1900 1901 1902 1903 1904 1905 1906
}

Reduction MachineOperatorReducer::ReduceWord64And(Node* node) {
  DCHECK_EQ(IrOpcode::kWord64And, node->opcode());
  return ReduceWordNAnd<Word64Adapter>(node);
}

1907
Reduction MachineOperatorReducer::TryMatchWord32Ror(Node* node) {
1908 1909 1910 1911 1912 1913 1914 1915 1916
  // Recognize rotation, we are matching and transforming as follows:
  //   x << y         |  x >>> (32 - y)    =>  x ror (32 - y)
  //   x << (32 - y)  |  x >>> y           =>  x ror y
  //   x << y         ^  x >>> (32 - y)    =>  x ror (32 - y)   if y & 31 != 0
  //   x << (32 - y)  ^  x >>> y           =>  x ror y          if y & 31 != 0
  // (As well as the commuted forms.)
  // Note the side condition for XOR: the optimization doesn't hold for
  // multiples of 32.

1917 1918
  DCHECK(IrOpcode::kWord32Or == node->opcode() ||
         IrOpcode::kWord32Xor == node->opcode());
1919
  Int32BinopMatcher m(node);
1920 1921
  Node* shl = nullptr;
  Node* shr = nullptr;
1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935
  if (m.left().IsWord32Shl() && m.right().IsWord32Shr()) {
    shl = m.left().node();
    shr = m.right().node();
  } else if (m.left().IsWord32Shr() && m.right().IsWord32Shl()) {
    shl = m.right().node();
    shr = m.left().node();
  } else {
    return NoChange();
  }

  Int32BinopMatcher mshl(shl);
  Int32BinopMatcher mshr(shr);
  if (mshl.left().node() != mshr.left().node()) return NoChange();

1936
  if (mshl.right().HasResolvedValue() && mshr.right().HasResolvedValue()) {
1937
    // Case where y is a constant.
1938 1939 1940 1941 1942
    if (mshl.right().ResolvedValue() + mshr.right().ResolvedValue() != 32) {
      return NoChange();
    }
    if (node->opcode() == IrOpcode::kWord32Xor &&
        (mshl.right().ResolvedValue() & 31) == 0) {
1943
      return NoChange();
1944
    }
1945
  } else {
1946 1947
    Node* sub = nullptr;
    Node* y = nullptr;
1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959
    if (mshl.right().IsInt32Sub()) {
      sub = mshl.right().node();
      y = mshr.right().node();
    } else if (mshr.right().IsInt32Sub()) {
      sub = mshr.right().node();
      y = mshl.right().node();
    } else {
      return NoChange();
    }

    Int32BinopMatcher msub(sub);
    if (!msub.left().Is(32) || msub.right().node() != y) return NoChange();
1960 1961 1962
    if (node->opcode() == IrOpcode::kWord32Xor) {
      return NoChange();  // Can't guarantee y & 31 != 0.
    }
1963 1964 1965 1966
  }

  node->ReplaceInput(0, mshl.left().node());
  node->ReplaceInput(1, mshr.right().node());
1967
  NodeProperties::ChangeOp(node, machine()->Word32Ror());
1968 1969 1970
  return Changed(node);
}

1971 1972 1973 1974 1975 1976
template <typename WordNAdapter>
Reduction MachineOperatorReducer::ReduceWordNOr(Node* node) {
  using A = WordNAdapter;
  A a(this);

  typename A::IntNBinopMatcher m(node);
1977 1978
  if (m.right().Is(0)) return Replace(m.left().node());    // x | 0  => x
  if (m.right().Is(-1)) return Replace(m.right().node());  // x | -1 => -1
1979
  if (m.IsFoldable()) {  // K | K  => K  (K stands for arbitrary constants)
1980
    return a.ReplaceIntN(m.left().ResolvedValue() | m.right().ResolvedValue());
1981 1982 1983
  }
  if (m.LeftEqualsRight()) return Replace(m.left().node());  // x | x => x

1984 1985
  // (x & K1) | K2 => x | K2 if K2 has ones for every zero bit in K1.
  // This case can be constructed by UpdateWord and UpdateWord32 in CSA.
1986
  if (m.right().HasResolvedValue()) {
1987 1988
    if (A::IsWordNAnd(m.left())) {
      typename A::IntNBinopMatcher mand(m.left().node());
1989 1990
      if (mand.right().HasResolvedValue()) {
        if ((m.right().ResolvedValue() | mand.right().ResolvedValue()) == -1) {
1991 1992 1993 1994 1995 1996 1997
          node->ReplaceInput(0, mand.left().node());
          return Changed(node);
        }
      }
    }
  }

1998
  return a.TryMatchWordNRor(node);
1999 2000
}

2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016
Reduction MachineOperatorReducer::ReduceWord32Or(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32Or, node->opcode());
  return ReduceWordNOr<Word32Adapter>(node);
}

Reduction MachineOperatorReducer::ReduceWord64Or(Node* node) {
  DCHECK_EQ(IrOpcode::kWord64Or, node->opcode());
  return ReduceWordNOr<Word64Adapter>(node);
}

template <typename WordNAdapter>
Reduction MachineOperatorReducer::ReduceWordNXor(Node* node) {
  using A = WordNAdapter;
  A a(this);

  typename A::IntNBinopMatcher m(node);
2017
  if (m.right().Is(0)) return Replace(m.left().node());  // x ^ 0 => x
2018
  if (m.IsFoldable()) {  // K ^ K => K  (K stands for arbitrary constants)
2019
    return a.ReplaceIntN(m.left().ResolvedValue() ^ m.right().ResolvedValue());
2020 2021
  }
  if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x ^ x => 0
2022 2023
  if (A::IsWordNXor(m.left()) && m.right().Is(-1)) {
    typename A::IntNBinopMatcher mleft(m.left().node());
2024 2025 2026 2027 2028
    if (mleft.right().Is(-1)) {  // (x ^ -1) ^ -1 => x
      return Replace(mleft.left().node());
    }
  }

2029 2030 2031 2032 2033
  return a.TryMatchWordNRor(node);
}

Reduction MachineOperatorReducer::ReduceWord32Xor(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32Xor, node->opcode());
2034 2035 2036 2037
  Int32BinopMatcher m(node);
  if (m.right().IsWord32Equal() && m.left().Is(1)) {
    return Replace(Word32Equal(m.right().node(), Int32Constant(0)));
  }
2038 2039 2040 2041 2042 2043
  return ReduceWordNXor<Word32Adapter>(node);
}

Reduction MachineOperatorReducer::ReduceWord64Xor(Node* node) {
  DCHECK_EQ(IrOpcode::kWord64Xor, node->opcode());
  return ReduceWordNXor<Word64Adapter>(node);
2044
}
2045

2046 2047
Reduction MachineOperatorReducer::ReduceWord32Equal(Node* node) {
  Int32BinopMatcher m(node);
2048
  if (m.IsFoldable()) {  // K == K => K  (K stands for arbitrary constants)
2049
    return ReplaceBool(m.left().ResolvedValue() == m.right().ResolvedValue());
2050 2051 2052 2053 2054 2055 2056 2057 2058
  }
  if (m.left().IsInt32Sub() && m.right().Is(0)) {  // x - y == 0 => x == y
    Int32BinopMatcher msub(m.left().node());
    node->ReplaceInput(0, msub.left().node());
    node->ReplaceInput(1, msub.right().node());
    return Changed(node);
  }
  // TODO(turbofan): fold HeapConstant, ExternalReference, pointer compares
  if (m.LeftEqualsRight()) return ReplaceBool(true);  // x == x => true
2059
  if (m.right().HasResolvedValue()) {
2060 2061 2062 2063
    base::Optional<std::pair<Node*, uint32_t>> replacements;
    if (m.left().IsTruncateInt64ToInt32()) {
      replacements = ReduceWord32EqualForConstantRhs<Word64Adapter>(
          NodeProperties::GetValueInput(m.left().node(), 0),
2064
          static_cast<uint32_t>(m.right().ResolvedValue()));
2065 2066
    } else {
      replacements = ReduceWord32EqualForConstantRhs<Word32Adapter>(
2067
          m.left().node(), static_cast<uint32_t>(m.right().ResolvedValue()));
2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078
    }
    if (replacements) {
      node->ReplaceInput(0, replacements->first);
      node->ReplaceInput(1, Uint32Constant(replacements->second));
      return Changed(node);
    }
  }

  return NoChange();
}

2079 2080 2081 2082
Reduction MachineOperatorReducer::ReduceFloat64InsertLowWord32(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64InsertLowWord32, node->opcode());
  Float64Matcher mlhs(node->InputAt(0));
  Uint32Matcher mrhs(node->InputAt(1));
2083 2084
  if (mlhs.HasResolvedValue() && mrhs.HasResolvedValue()) {
    return ReplaceFloat64(
2085 2086 2087
        base::bit_cast<double>((base::bit_cast<uint64_t>(mlhs.ResolvedValue()) &
                                uint64_t{0xFFFFFFFF00000000}) |
                               mrhs.ResolvedValue()));
2088 2089 2090 2091 2092 2093 2094 2095
  }
  return NoChange();
}

Reduction MachineOperatorReducer::ReduceFloat64InsertHighWord32(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64InsertHighWord32, node->opcode());
  Float64Matcher mlhs(node->InputAt(0));
  Uint32Matcher mrhs(node->InputAt(1));
2096
  if (mlhs.HasResolvedValue() && mrhs.HasResolvedValue()) {
2097 2098 2099
    return ReplaceFloat64(base::bit_cast<double>(
        (base::bit_cast<uint64_t>(mlhs.ResolvedValue()) &
         uint64_t{0xFFFFFFFF}) |
2100
        (static_cast<uint64_t>(mrhs.ResolvedValue()) << 32)));
2101 2102 2103 2104
  }
  return NoChange();
}

2105 2106 2107
namespace {

bool IsFloat64RepresentableAsFloat32(const Float64Matcher& m) {
2108 2109
  if (m.HasResolvedValue()) {
    double v = m.ResolvedValue();
2110
    return DoubleToFloat32(v) == v;
2111 2112 2113 2114 2115 2116
  }
  return false;
}

}  // namespace

2117
Reduction MachineOperatorReducer::ReduceFloat64Compare(Node* node) {
2118 2119 2120
  DCHECK(IrOpcode::kFloat64Equal == node->opcode() ||
         IrOpcode::kFloat64LessThan == node->opcode() ||
         IrOpcode::kFloat64LessThanOrEqual == node->opcode());
2121
  Float64BinopMatcher m(node);
2122 2123 2124
  if (m.IsFoldable()) {
    switch (node->opcode()) {
      case IrOpcode::kFloat64Equal:
2125 2126
        return ReplaceBool(m.left().ResolvedValue() ==
                           m.right().ResolvedValue());
2127
      case IrOpcode::kFloat64LessThan:
2128 2129
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
2130
      case IrOpcode::kFloat64LessThanOrEqual:
2131 2132
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146
      default:
        UNREACHABLE();
    }
  } else if ((m.left().IsChangeFloat32ToFloat64() &&
              m.right().IsChangeFloat32ToFloat64()) ||
             (m.left().IsChangeFloat32ToFloat64() &&
              IsFloat64RepresentableAsFloat32(m.right())) ||
             (IsFloat64RepresentableAsFloat32(m.left()) &&
              m.right().IsChangeFloat32ToFloat64())) {
    // As all Float32 values have an exact representation in Float64, comparing
    // two Float64 values both converted from Float32 is equivalent to comparing
    // the original Float32s, so we can ignore the conversions. We can also
    // reduce comparisons of converted Float64 values against constants that
    // can be represented exactly as Float32.
2147 2148
    switch (node->opcode()) {
      case IrOpcode::kFloat64Equal:
2149
        NodeProperties::ChangeOp(node, machine()->Float32Equal());
2150 2151
        break;
      case IrOpcode::kFloat64LessThan:
2152
        NodeProperties::ChangeOp(node, machine()->Float32LessThan());
2153 2154
        break;
      case IrOpcode::kFloat64LessThanOrEqual:
2155
        NodeProperties::ChangeOp(node, machine()->Float32LessThanOrEqual());
2156 2157
        break;
      default:
2158
        UNREACHABLE();
2159
    }
2160
    node->ReplaceInput(
2161 2162
        0, m.left().HasResolvedValue()
               ? Float32Constant(static_cast<float>(m.left().ResolvedValue()))
2163 2164
               : m.left().InputAt(0));
    node->ReplaceInput(
2165 2166
        1, m.right().HasResolvedValue()
               ? Float32Constant(static_cast<float>(m.right().ResolvedValue()))
2167
               : m.right().InputAt(0));
2168 2169 2170 2171 2172
    return Changed(node);
  }
  return NoChange();
}

2173 2174 2175
Reduction MachineOperatorReducer::ReduceFloat64RoundDown(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64RoundDown, node->opcode());
  Float64Matcher m(node->InputAt(0));
2176 2177
  if (m.HasResolvedValue()) {
    return ReplaceFloat64(std::floor(m.ResolvedValue()));
2178 2179 2180
  }
  return NoChange();
}
2181

2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279
namespace {

// Returns true if |node| is a constant whose value is 0.
bool IsZero(Node* node) {
  switch (node->opcode()) {
#define CASE_IS_ZERO(opcode, matcher) \
  case IrOpcode::opcode: {            \
    matcher m(node);                  \
    return m.Is(0);                   \
  }
    CASE_IS_ZERO(kInt32Constant, Int32Matcher)
    CASE_IS_ZERO(kInt64Constant, Int64Matcher)
#undef CASE_IS_ZERO
    default:
      break;
  }
  return false;
}

// If |node| is of the form "x == 0", then return "x" (in order to remove the
// "== 0" part).
base::Optional<Node*> TryGetInvertedCondition(Node* cond) {
  if (cond->opcode() == IrOpcode::kWord32Equal) {
    Int32BinopMatcher m(cond);
    if (IsZero(m.right().node())) {
      return m.left().node();
    }
  }
  return base::nullopt;
}

struct SimplifiedCondition {
  Node* condition;
  bool is_inverted;
};

// Tries to simplifies |cond| by removing all top-level "== 0". Everytime such a
// construction is removed, the meaning of the comparison is inverted. This is
// recorded by the variable |is_inverted| throughout this function, and returned
// at the end. If |is_inverted| is true at the end, the caller should invert the
// if/else branches following the comparison.
base::Optional<SimplifiedCondition> TrySimplifyCompareZero(Node* cond) {
  bool is_inverted = false;
  bool changed = false;
  base::Optional<Node*> new_cond;
  while ((new_cond = TryGetInvertedCondition(cond)).has_value()) {
    cond = *new_cond;
    is_inverted = !is_inverted;
    changed = true;
  }
  if (changed) {
    return SimplifiedCondition{cond, is_inverted};
  } else {
    return {};
  }
}

}  // namespace

void MachineOperatorReducer::SwapBranches(Node* node) {
  DCHECK_EQ(node->opcode(), IrOpcode::kBranch);
  for (Node* const use : node->uses()) {
    switch (use->opcode()) {
      case IrOpcode::kIfTrue:
        NodeProperties::ChangeOp(use, common()->IfFalse());
        break;
      case IrOpcode::kIfFalse:
        NodeProperties::ChangeOp(use, common()->IfTrue());
        break;
      default:
        UNREACHABLE();
    }
  }
  NodeProperties::ChangeOp(
      node, common()->Branch(NegateBranchHint(BranchHintOf(node->op()))));
}

// If |node| is a branch, removes all top-level 32-bit "== 0" from |node|.
Reduction MachineOperatorReducer::SimplifyBranch(Node* node) {
  Node* cond = node->InputAt(0);
  if (auto simplified = TrySimplifyCompareZero(cond)) {
    node->ReplaceInput(0, simplified->condition);
    if (simplified->is_inverted) {
      switch (node->opcode()) {
        case IrOpcode::kBranch:
          SwapBranches(node);
          break;
        case IrOpcode::kTrapIf:
          NodeProperties::ChangeOp(node,
                                   common()->TrapUnless(TrapIdOf(node->op())));
          break;
        case IrOpcode::kTrapUnless:
          NodeProperties::ChangeOp(node,
                                   common()->TrapIf(TrapIdOf(node->op())));
          break;
        case IrOpcode::kDeoptimizeIf: {
          DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
          NodeProperties::ChangeOp(
2280
              node, common()->DeoptimizeUnless(p.reason(), p.feedback()));
2281 2282 2283 2284 2285
          break;
        }
        case IrOpcode::kDeoptimizeUnless: {
          DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
          NodeProperties::ChangeOp(
2286
              node, common()->DeoptimizeIf(p.reason(), p.feedback()));
2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298
          break;
        }
        default:

          UNREACHABLE();
      }
    }
    return Changed(node);
  }
  return NoChange();
}

2299 2300 2301 2302 2303 2304 2305 2306 2307 2308
Reduction MachineOperatorReducer::ReduceConditional(Node* node) {
  DCHECK(node->opcode() == IrOpcode::kBranch ||
         node->opcode() == IrOpcode::kDeoptimizeIf ||
         node->opcode() == IrOpcode::kDeoptimizeUnless ||
         node->opcode() == IrOpcode::kTrapIf ||
         node->opcode() == IrOpcode::kTrapUnless);
  // This reducer only applies operator reductions to the branch condition.
  // Reductions involving control flow happen elsewhere. Non-zero inputs are
  // considered true in all conditional ops.
  NodeMatcher condition(NodeProperties::GetValueInput(node, 0));
2309
  Reduction reduction = NoChange();
2310 2311 2312 2313
  if (condition.IsTruncateInt64ToInt32()) {
    if (auto replacement =
            ReduceConditionalN<Word64Adapter>(condition.node())) {
      NodeProperties::ReplaceValueInput(node, *replacement, 0);
2314
      reduction = Changed(node);
2315 2316 2317
    }
  } else if (auto replacement = ReduceConditionalN<Word32Adapter>(node)) {
    NodeProperties::ReplaceValueInput(node, *replacement, 0);
2318
    reduction = Changed(node);
2319
  }
2320
  return reduction.FollowedBy(SimplifyBranch(node));
2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343
}

template <typename WordNAdapter>
base::Optional<Node*> MachineOperatorReducer::ReduceConditionalN(Node* node) {
  NodeMatcher condition(NodeProperties::GetValueInput(node, 0));
  // Branch conditions are 32-bit comparisons against zero, so they are the
  // opposite of a 32-bit `x == 0` node. To avoid repetition, we can reuse logic
  // for Word32Equal: if `x == 0` can reduce to `y == 0`, then branch(x) can
  // reduce to branch(y).
  auto replacements =
      ReduceWord32EqualForConstantRhs<WordNAdapter>(condition.node(), 0);
  if (replacements && replacements->second == 0) return replacements->first;
  return {};
}

template <typename WordNAdapter>
base::Optional<std::pair<Node*, uint32_t>>
MachineOperatorReducer::ReduceWord32EqualForConstantRhs(Node* lhs,
                                                        uint32_t rhs) {
  if (WordNAdapter::IsWordNAnd(NodeMatcher(lhs))) {
    typename WordNAdapter::UintNBinopMatcher mand(lhs);
    if ((WordNAdapter::IsWordNShr(mand.left()) ||
         WordNAdapter::IsWordNSar(mand.left())) &&
2344
        mand.right().HasResolvedValue()) {
2345 2346
      typename WordNAdapter::UintNBinopMatcher mshift(mand.left().node());
      // ((x >> K1) & K2) == K3 => (x & (K2 << K1)) == (K3 << K1)
2347 2348 2349
      if (mshift.right().HasResolvedValue()) {
        auto shift_bits = mshift.right().ResolvedValue();
        auto mask = mand.right().ResolvedValue();
2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362
        // Make sure that we won't shift data off the end, and that all of the
        // data ends up in the lower 32 bits for 64-bit mode.
        if (shift_bits <= base::bits::CountLeadingZeros(mask) &&
            shift_bits <= base::bits::CountLeadingZeros(rhs) &&
            mask << shift_bits <= std::numeric_limits<uint32_t>::max()) {
          Node* new_input = mshift.left().node();
          uint32_t new_mask = static_cast<uint32_t>(mask << shift_bits);
          uint32_t new_rhs = rhs << shift_bits;
          if (WordNAdapter::WORD_SIZE == 64) {
            // We can truncate before performing the And.
            new_input = TruncateInt64ToInt32(new_input);
          }
          return std::make_pair(Word32And(new_input, new_mask), new_rhs);
2363 2364 2365 2366
        }
      }
    }
  }
2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378
  // Replaces (x >> n) == k with x == k << n, with "k << n" being computed
  // here at compile time.
  if (lhs->op() == machine()->Word32SarShiftOutZeros() &&
      lhs->UseCount() == 1) {
    typename WordNAdapter::UintNBinopMatcher mshift(lhs);
    if (mshift.right().HasResolvedValue()) {
      int32_t shift = static_cast<int32_t>(mshift.right().ResolvedValue());
      if (CanRevertLeftShiftWithRightShift(rhs, shift)) {
        return std::make_pair(mshift.left().node(), rhs << shift);
      }
    }
  }
2379
  return {};
2380 2381
}

2382
CommonOperatorBuilder* MachineOperatorReducer::common() const {
2383
  return mcgraph()->common();
2384
}
2385

2386
MachineOperatorBuilder* MachineOperatorReducer::machine() const {
2387
  return mcgraph()->machine();
2388 2389
}

2390
Graph* MachineOperatorReducer::graph() const { return mcgraph()->graph(); }
2391 2392 2393 2394

}  // namespace compiler
}  // namespace internal
}  // namespace v8