machine-operator-reducer.cc 90.5 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/codegen/tnode.h"
16
#include "src/compiler/diamond.h"
17
#include "src/compiler/graph.h"
18
#include "src/compiler/js-operator.h"
19
#include "src/compiler/machine-graph.h"
20
#include "src/compiler/node-matchers.h"
21
#include "src/compiler/node-properties.h"
22
#include "src/compiler/opcodes.h"
23
#include "src/numbers/conversions-inl.h"
24 25 26 27 28

namespace v8 {
namespace internal {
namespace compiler {

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
// 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>
52 53 54 55 56 57 58 59
  static bool IsWordNShr(const T& x) {
    return x.IsWord32Shr();
  }
  template <typename T>
  static bool IsWordNSar(const T& x) {
    return x.IsWord32Sar();
  }
  template <typename T>
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
  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); }
82
  Node* UintNConstant(uint32_t value) { return r_->Uint32Constant(value); }
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 111
  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>
112 113 114 115 116 117 118 119
  static bool IsWordNShr(const T& x) {
    return x.IsWord64Shr();
  }
  template <typename T>
  static bool IsWordNSar(const T& x) {
    return x.IsWord64Sar();
  }
  template <typename T>
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
  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); }
145
  Node* UintNConstant(uint64_t value) { return r_->Uint64Constant(value); }
146 147 148 149 150 151
  Node* WordNAnd(Node* lhs, Node* rhs) { return r_->Word64And(lhs, rhs); }

 private:
  MachineOperatorReducer* r_;
};

152 153 154 155 156 157 158 159 160 161 162 163 164
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

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

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


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

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

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

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

191 192 193 194 195 196 197
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);
198 199 200 201 202 203
  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));
204
}
205

206 207 208 209
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;
210 211 212
}

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

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

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

226 227 228 229 230 231
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;
}

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

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

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

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

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

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

292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307
namespace {
bool ObjectsMayAlias(Node* a, Node* b) {
  if (a != b) {
    if (NodeProperties::IsFreshObject(b)) std::swap(a, b);
    if (NodeProperties::IsFreshObject(a) &&
        (NodeProperties::IsFreshObject(b) ||
         b->opcode() == IrOpcode::kParameter ||
         b->opcode() == IrOpcode::kLoadImmutable ||
         IrOpcode::IsConstantOpcode(b->opcode()))) {
      return false;
    }
  }
  return true;
}
}  // namespace

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

974 975
Reduction MachineOperatorReducer::ReduceTruncateInt64ToInt32(Node* node) {
  Int64Matcher m(node->InputAt(0));
976 977
  if (m.HasResolvedValue())
    return ReplaceInt32(static_cast<int32_t>(m.ResolvedValue()));
978 979 980 981
  if (m.IsChangeInt32ToInt64()) return Replace(m.node()->InputAt(0));
  return NoChange();
}

982 983 984 985
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
986
  if (m.IsFoldable()) {  // K + K => K  (K stands for arbitrary constants)
987 988
    return ReplaceInt32(base::AddWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
989
  }
990 991 992 993 994
  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());
995
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
996
      return Changed(node).FollowedBy(ReduceInt32Sub(node));
997 998 999 1000 1001 1002
    }
  }
  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());
1003
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1004
      return Changed(node).FollowedBy(ReduceInt32Sub(node));
1005 1006
    }
  }
1007
  // (x + Int32Constant(a)) + Int32Constant(b)) => x + Int32Constant(a + b)
1008
  if (m.right().HasResolvedValue() && m.left().IsInt32Add()) {
1009
    Int32BinopMatcher n(m.left().node());
1010 1011 1012 1013
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int32Constant(base::AddWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
1014 1015 1016 1017
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
1018

1019 1020 1021
  return NoChange();
}

1022 1023 1024 1025 1026
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()) {
1027 1028
    return ReplaceInt64(base::AddWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1029
  }
1030
  // (x + Int64Constant(a)) + Int64Constant(b) => x + Int64Constant(a + b)
1031
  if (m.right().HasResolvedValue() && m.left().IsInt64Add()) {
1032
    Int64BinopMatcher n(m.left().node());
1033 1034 1035 1036
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int64Constant(base::AddWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
1037 1038 1039 1040
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
1041 1042
  return NoChange();
}
1043

1044 1045 1046 1047
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
1048
  if (m.IsFoldable()) {  // K - K => K  (K stands for arbitrary constants)
1049 1050
    return ReplaceInt32(base::SubWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1051 1052
  }
  if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x - x => 0
1053
  if (m.right().HasResolvedValue()) {               // x - K => x + -K
1054
    node->ReplaceInput(
1055 1056
        1,
        Int32Constant(base::NegateWithWraparound(m.right().ResolvedValue())));
1057
    NodeProperties::ChangeOp(node, machine()->Int32Add());
1058
    return Changed(node).FollowedBy(ReduceInt32Add(node));
1059 1060 1061 1062
  }
  return NoChange();
}

1063 1064 1065 1066
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
1067
  if (m.IsFoldable()) {  // K - K => K  (K stands for arbitrary constants)
1068 1069
    return ReplaceInt64(base::SubWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1070 1071
  }
  if (m.LeftEqualsRight()) return Replace(Int64Constant(0));  // x - x => 0
1072
  if (m.right().HasResolvedValue()) {                         // x - K => x + -K
1073
    node->ReplaceInput(
1074 1075
        1,
        Int64Constant(base::NegateWithWraparound(m.right().ResolvedValue())));
1076
    NodeProperties::ChangeOp(node, machine()->Int64Add());
1077
    return Changed(node).FollowedBy(ReduceInt64Add(node));
1078 1079 1080
  }
  return NoChange();
}
1081

1082 1083 1084 1085 1086
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
1087
  if (m.IsFoldable()) {  // K * K => K  (K stands for arbitrary constants)
1088 1089
    return ReplaceInt64(base::MulWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1090 1091 1092 1093 1094 1095 1096 1097 1098
  }
  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(
1099 1100
        1,
        Int64Constant(base::bits::WhichPowerOfTwo(m.right().ResolvedValue())));
1101
    NodeProperties::ChangeOp(node, machine()->Word64Shl());
1102
    return Changed(node).FollowedBy(ReduceWord64Shl(node));
1103
  }
1104
  // (x * Int64Constant(a)) * Int64Constant(b)) => x * Int64Constant(a * b)
1105
  if (m.right().HasResolvedValue() && m.left().IsInt64Mul()) {
1106
    Int64BinopMatcher n(m.left().node());
1107 1108 1109 1110
    if (n.right().HasResolvedValue() && m.OwnsInput(m.left().node())) {
      node->ReplaceInput(
          1, Int64Constant(base::MulWithWraparound(m.right().ResolvedValue(),
                                                   n.right().ResolvedValue())));
1111 1112 1113 1114
      node->ReplaceInput(0, n.left().node());
      return Changed(node);
    }
  }
1115 1116 1117
  return NoChange();
}

1118 1119
Reduction MachineOperatorReducer::ReduceInt32Div(Node* node) {
  Int32BinopMatcher m(node);
1120
  if (m.left().Is(0)) return Replace(m.left().node());    // 0 / x => 0
1121 1122
  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
1123
  if (m.IsFoldable()) {  // K / K => K  (K stands for arbitrary constants)
1124 1125
    return ReplaceInt32(base::bits::SignedDiv32(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1126 1127 1128 1129
  }
  if (m.LeftEqualsRight()) {  // x / x => x != 0
    Node* const zero = Int32Constant(0);
    return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
1130 1131 1132 1133
  }
  if (m.right().Is(-1)) {  // x / -1 => 0 - x
    node->ReplaceInput(0, Int32Constant(0));
    node->ReplaceInput(1, m.left().node());
1134
    node->TrimInputCount(2);
1135
    NodeProperties::ChangeOp(node, machine()->Int32Sub());
1136 1137
    return Changed(node);
  }
1138 1139
  if (m.right().HasResolvedValue()) {
    int32_t const divisor = m.right().ResolvedValue();
1140 1141
    Node* const dividend = m.left().node();
    Node* quotient = dividend;
1142
    if (base::bits::IsPowerOfTwo(Abs(divisor))) {
1143
      uint32_t const shift = base::bits::WhichPowerOfTwo(Abs(divisor));
1144
      DCHECK_NE(0u, shift);
1145 1146 1147 1148 1149 1150
      if (shift > 1) {
        quotient = Word32Sar(quotient, 31);
      }
      quotient = Int32Add(Word32Shr(quotient, 32u - shift), dividend);
      quotient = Word32Sar(quotient, shift);
    } else {
1151
      quotient = Int32Div(quotient, Abs(divisor));
1152 1153 1154 1155
    }
    if (divisor < 0) {
      node->ReplaceInput(0, Int32Constant(0));
      node->ReplaceInput(1, quotient);
1156
      node->TrimInputCount(2);
1157
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1158 1159 1160 1161 1162 1163 1164
      return Changed(node);
    }
    return Replace(quotient);
  }
  return NoChange();
}

1165 1166 1167 1168 1169
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
1170
  if (m.IsFoldable()) {  // K / K => K  (K stands for arbitrary constants)
1171 1172
    return ReplaceUint32(base::bits::UnsignedDiv32(m.left().ResolvedValue(),
                                                   m.right().ResolvedValue()));
1173 1174 1175 1176 1177
  }
  if (m.LeftEqualsRight()) {  // x / x => x != 0
    Node* const zero = Int32Constant(0);
    return Replace(Word32Equal(Word32Equal(m.left().node(), zero), zero));
  }
1178
  if (m.right().HasResolvedValue()) {
1179
    Node* const dividend = m.left().node();
1180
    uint32_t const divisor = m.right().ResolvedValue();
1181
    if (base::bits::IsPowerOfTwo(divisor)) {  // x / 2^n => x >> n
1182 1183
      node->ReplaceInput(1, Uint32Constant(base::bits::WhichPowerOfTwo(
                                m.right().ResolvedValue())));
1184
      node->TrimInputCount(2);
1185
      NodeProperties::ChangeOp(node, machine()->Word32Shr());
1186 1187 1188 1189
      return Changed(node);
    } else {
      return Replace(Uint32Div(dividend, divisor));
    }
1190 1191 1192 1193
  }
  return NoChange();
}

1194
Reduction MachineOperatorReducer::ReduceInt32Mod(Node* node) {
1195
  Int32BinopMatcher m(node);
1196 1197 1198 1199 1200
  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
1201
  if (m.IsFoldable()) {  // K % K => K  (K stands for arbitrary constants)
1202 1203
    return ReplaceInt32(base::bits::SignedMod32(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1204
  }
1205
  if (m.right().HasResolvedValue()) {
1206
    Node* const dividend = m.left().node();
1207
    uint32_t const divisor = Abs(m.right().ResolvedValue());
1208
    if (base::bits::IsPowerOfTwo(divisor)) {
1209 1210
      uint32_t const mask = divisor - 1;
      Node* const zero = Int32Constant(0);
1211 1212 1213 1214 1215 1216 1217
      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)));
1218
    } else {
1219
      Node* quotient = Int32Div(dividend, divisor);
1220 1221
      DCHECK_EQ(dividend, node->InputAt(0));
      node->ReplaceInput(1, Int32Mul(quotient, Int32Constant(divisor)));
1222
      node->TrimInputCount(2);
1223
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1224
    }
1225
    return Changed(node);
1226 1227 1228 1229
  }
  return NoChange();
}

1230 1231 1232 1233 1234 1235
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
1236
  if (m.IsFoldable()) {  // K % K => K  (K stands for arbitrary constants)
1237 1238
    return ReplaceUint32(base::bits::UnsignedMod32(m.left().ResolvedValue(),
                                                   m.right().ResolvedValue()));
1239
  }
1240
  if (m.right().HasResolvedValue()) {
1241
    Node* const dividend = m.left().node();
1242
    uint32_t const divisor = m.right().ResolvedValue();
1243
    if (base::bits::IsPowerOfTwo(divisor)) {  // x % 2^n => x & 2^n-1
1244
      node->ReplaceInput(1, Uint32Constant(m.right().ResolvedValue() - 1));
1245 1246
      node->TrimInputCount(2);
      NodeProperties::ChangeOp(node, machine()->Word32And());
1247 1248 1249 1250
    } else {
      Node* quotient = Uint32Div(dividend, divisor);
      DCHECK_EQ(dividend, node->InputAt(0));
      node->ReplaceInput(1, Int32Mul(quotient, Uint32Constant(divisor)));
1251 1252
      node->TrimInputCount(2);
      NodeProperties::ChangeOp(node, machine()->Int32Sub());
1253
    }
1254 1255 1256 1257 1258
    return Changed(node);
  }
  return NoChange();
}

1259
Reduction MachineOperatorReducer::ReduceStore(Node* node) {
1260
  NodeMatcher nm(node);
1261 1262 1263 1264
  DCHECK(nm.IsStore() || nm.IsUnalignedStore());
  MachineRepresentation rep =
      nm.IsStore() ? StoreRepresentationOf(node->op()).representation()
                   : UnalignedStoreRepresentationOf(node->op());
1265

1266
  const int value_input = 2;
1267 1268
  Node* const value = node->InputAt(value_input);

1269 1270 1271
  switch (value->opcode()) {
    case IrOpcode::kWord32And: {
      Uint32BinopMatcher m(value);
1272 1273 1274 1275 1276
      if (m.right().HasResolvedValue() &&
          ((rep == MachineRepresentation::kWord8 &&
            (m.right().ResolvedValue() & 0xFF) == 0xFF) ||
           (rep == MachineRepresentation::kWord16 &&
            (m.right().ResolvedValue() & 0xFFFF) == 0xFFFF))) {
1277
        node->ReplaceInput(value_input, m.left().node());
1278 1279 1280 1281 1282 1283
        return Changed(node);
      }
      break;
    }
    case IrOpcode::kWord32Sar: {
      Int32BinopMatcher m(value);
1284 1285 1286 1287
      if (m.left().IsWord32Shl() && ((rep == MachineRepresentation::kWord8 &&
                                      m.right().IsInRange(1, 24)) ||
                                     (rep == MachineRepresentation::kWord16 &&
                                      m.right().IsInRange(1, 16)))) {
1288
        Int32BinopMatcher mleft(m.left().node());
1289
        if (mleft.right().Is(m.right().ResolvedValue())) {
1290
          node->ReplaceInput(value_input, mleft.left().node());
1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301
          return Changed(node);
        }
      }
      break;
    }
    default:
      break;
  }
  return NoChange();
}

1302 1303 1304 1305 1306 1307 1308
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;
1309 1310
        bool ovf = base::bits::SignedAddOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1311
        return ReplaceInt32(index == 0 ? val : ovf);
1312 1313
      }
      if (m.right().Is(0)) {
1314
        return Replace(index == 0 ? m.left().node() : m.right().node());
1315 1316 1317 1318 1319 1320 1321 1322
      }
      break;
    }
    case IrOpcode::kInt32SubWithOverflow: {
      DCHECK(index == 0 || index == 1);
      Int32BinopMatcher m(node);
      if (m.IsFoldable()) {
        int32_t val;
1323 1324
        bool ovf = base::bits::SignedSubOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336
        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;
1337 1338
        bool ovf = base::bits::SignedMulOverflow32(
            m.left().ResolvedValue(), m.right().ResolvedValue(), &val);
1339
        return ReplaceInt32(index == 0 ? val : ovf);
1340 1341
      }
      if (m.right().Is(0)) {
1342 1343 1344 1345
        return Replace(m.right().node());
      }
      if (m.right().Is(1)) {
        return index == 0 ? Replace(m.left().node()) : ReplaceInt32(0);
1346 1347 1348 1349 1350 1351 1352 1353 1354
      }
      break;
    }
    default:
      break;
  }
  return NoChange();
}

1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374
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

1375 1376 1377 1378 1379 1380
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);
1381
  // (x >> K) < (y >> K) => x < y   if only zeros shifted out
1382 1383 1384 1385
  if (m.left().op() == machine()->Word32SarShiftOutZeros() &&
      m.right().op() == machine()->Word32SarShiftOutZeros()) {
    Int32BinopMatcher mleft(m.left().node());
    Int32BinopMatcher mright(m.right().node());
1386 1387
    if (mleft.right().HasResolvedValue() &&
        mright.right().Is(mleft.right().ResolvedValue())) {
1388 1389 1390 1391 1392
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, mright.left().node());
      return Changed(node);
    }
  }
1393 1394 1395
  // Simplifying (x >> n) <= k into x <= (k << n), with "k << n" being
  // computed here at compile time.
  if (m.right().HasResolvedValue() &&
1396 1397
      m.left().op() == machine()->Word32SarShiftOutZeros() &&
      m.left().node()->UseCount() == 1) {
1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411
    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() &&
1412 1413
      m.right().op() == machine()->Word32SarShiftOutZeros() &&
      m.right().node()->UseCount() == 1) {
1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424
    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);
      }
    }
  }
1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463
  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));
  }

1464
  // (x >> K) < (y >> K) => x < y   if only zeros shifted out
1465 1466 1467 1468 1469
  // 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());
1470 1471
    if (mleft.right().HasResolvedValue() &&
        mright.right().Is(mleft.right().ResolvedValue())) {
1472 1473 1474 1475 1476 1477 1478 1479 1480
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, mright.left().node());
      return Changed(node);
    }
  }

  return NoChange();
}

1481 1482 1483 1484 1485
Reduction MachineOperatorReducer::ReduceWord32Shifts(Node* node) {
  DCHECK((node->opcode() == IrOpcode::kWord32Shl) ||
         (node->opcode() == IrOpcode::kWord32Shr) ||
         (node->opcode() == IrOpcode::kWord32Sar));
  if (machine()->Word32ShiftIsSafe()) {
1486
    // Remove the explicit 'and' with 0x1F if the shift provided by the machine
1487 1488 1489 1490
    // instruction matches that required by JavaScript.
    Int32BinopMatcher m(node);
    if (m.right().IsWord32And()) {
      Int32BinopMatcher mright(m.right().node());
1491
      if (mright.right().Is(0x1F)) {
1492 1493 1494 1495 1496 1497 1498 1499
        node->ReplaceInput(1, mright.left().node());
        return Changed(node);
      }
    }
  }
  return NoChange();
}

1500 1501 1502 1503
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
1504
  if (m.IsFoldable()) {  // K << K => K  (K stands for arbitrary constants)
1505 1506
    return ReplaceInt32(base::ShlWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1507 1508 1509 1510
  }
  if (m.right().IsInRange(1, 31)) {
    if (m.left().IsWord32Sar() || m.left().IsWord32Shr()) {
      Int32BinopMatcher mleft(m.left().node());
1511 1512 1513 1514 1515 1516 1517 1518 1519 1520

      // 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();
1521 1522
        int k = mleft.right().ResolvedValue();
        int l = m.right().ResolvedValue();
1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539
        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)
1540
      if (mleft.right().Is(m.right().ResolvedValue())) {
1541 1542
        node->ReplaceInput(0, mleft.left().node());
        node->ReplaceInput(1,
1543
                           Uint32Constant(std::numeric_limits<uint32_t>::max()
1544
                                          << m.right().ResolvedValue()));
1545
        NodeProperties::ChangeOp(node, machine()->Word32And());
1546
        return Changed(node).FollowedBy(ReduceWord32And(node));
1547 1548 1549 1550 1551 1552
      }
    }
  }
  return ReduceWord32Shifts(node);
}

1553 1554 1555 1556
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
1557
  if (m.IsFoldable()) {  // K << K => K  (K stands for arbitrary constants)
1558 1559
    return ReplaceInt64(base::ShlWithWraparound(m.left().ResolvedValue(),
                                                m.right().ResolvedValue()));
1560
  }
1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573
  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();
1574 1575
      int64_t k = mleft.right().ResolvedValue();
      int64_t l = m.right().ResolvedValue();
1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592
      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)
1593
    if (mleft.right().Is(m.right().ResolvedValue())) {
1594 1595
      node->ReplaceInput(0, mleft.left().node());
      node->ReplaceInput(1, Uint64Constant(std::numeric_limits<uint64_t>::max()
1596
                                           << m.right().ResolvedValue()));
1597 1598 1599 1600
      NodeProperties::ChangeOp(node, machine()->Word64And());
      return Changed(node).FollowedBy(ReduceWord64And(node));
    }
  }
1601 1602 1603
  return NoChange();
}

1604 1605 1606
Reduction MachineOperatorReducer::ReduceWord32Shr(Node* node) {
  Uint32BinopMatcher 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 ReplaceInt32(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 31));
1610
  }
1611
  if (m.left().IsWord32And() && m.right().HasResolvedValue()) {
1612
    Uint32BinopMatcher mleft(m.left().node());
1613 1614 1615
    if (mleft.right().HasResolvedValue()) {
      uint32_t shift = m.right().ResolvedValue() & 31;
      uint32_t mask = mleft.right().ResolvedValue();
1616 1617 1618 1619 1620 1621 1622 1623
      if ((mask >> shift) == 0) {
        // (m >>> s) == 0 implies ((x & m) >>> s) == 0
        return ReplaceInt32(0);
      }
    }
  }
  return ReduceWord32Shifts(node);
}
1624

1625 1626 1627 1628
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
1629
  if (m.IsFoldable()) {  // K >> K => K  (K stands for arbitrary constants)
1630 1631
    return ReplaceInt64(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 63));
1632 1633 1634 1635
  }
  return NoChange();
}

1636 1637 1638
Reduction MachineOperatorReducer::ReduceWord32Sar(Node* node) {
  Int32BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
1639
  if (m.IsFoldable()) {  // K >> K => K  (K stands for arbitrary constants)
1640 1641
    return ReplaceInt32(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 31));
1642 1643 1644 1645 1646 1647 1648 1649
  }
  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());
1650
        NodeProperties::ChangeOp(node, machine()->Int32Sub());
1651
        return Changed(node).FollowedBy(ReduceInt32Sub(node));
1652 1653 1654
      }
    } else if (mleft.left().IsLoad()) {
      LoadRepresentation const rep =
1655 1656 1657
          LoadRepresentationOf(mleft.left().node()->op());
      if (m.right().Is(24) && mleft.right().Is(24) &&
          rep == MachineType::Int8()) {
1658 1659 1660
        // Load[kMachInt8] << 24 >> 24 => Load[kMachInt8]
        return Replace(mleft.left().node());
      }
1661 1662
      if (m.right().Is(16) && mleft.right().Is(16) &&
          rep == MachineType::Int16()) {
1663 1664 1665 1666 1667 1668 1669 1670
        // Load[kMachInt16] << 16 >> 16 => Load[kMachInt8]
        return Replace(mleft.left().node());
      }
    }
  }
  return ReduceWord32Shifts(node);
}

1671 1672 1673 1674
Reduction MachineOperatorReducer::ReduceWord64Sar(Node* node) {
  Int64BinopMatcher m(node);
  if (m.right().Is(0)) return Replace(m.left().node());  // x >> 0 => x
  if (m.IsFoldable()) {
1675 1676
    return ReplaceInt64(m.left().ResolvedValue() >>
                        (m.right().ResolvedValue() & 63));
1677 1678 1679
  }
  return NoChange();
}
1680

1681 1682 1683 1684 1685 1686
template <typename WordNAdapter>
Reduction MachineOperatorReducer::ReduceWordNAnd(Node* node) {
  using A = WordNAdapter;
  A a(this);

  typename A::IntNBinopMatcher m(node);
1687 1688
  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
1689 1690 1691
  if (m.left().IsComparison() && m.right().Is(1)) {       // CMP & 1 => CMP
    return Replace(m.left().node());
  }
1692
  if (m.IsFoldable()) {  // K & K  => K  (K stands for arbitrary constants)
1693
    return a.ReplaceIntN(m.left().ResolvedValue() & m.right().ResolvedValue());
1694 1695
  }
  if (m.LeftEqualsRight()) return Replace(m.left().node());  // x & x => x
1696
  if (A::IsWordNAnd(m.left()) && m.right().HasResolvedValue()) {
1697
    typename A::IntNBinopMatcher mleft(m.left().node());
1698
    if (mleft.right().HasResolvedValue()) {  // (x & K) & K => x & K
1699
      node->ReplaceInput(0, mleft.left().node());
1700 1701
      node->ReplaceInput(1, a.IntNConstant(m.right().ResolvedValue() &
                                           mleft.right().ResolvedValue()));
1702
      return Changed(node).FollowedBy(a.ReduceWordNAnd(node));
1703 1704
    }
  }
1705
  if (m.right().IsNegativePowerOf2()) {
1706
    typename A::intN_t const mask = m.right().ResolvedValue();
1707 1708 1709
    typename A::intN_t const neg_mask = base::NegateWithWraparound(mask);
    if (A::IsWordNShl(m.left())) {
      typename A::UintNBinopMatcher mleft(m.left().node());
1710 1711
      if (mleft.right().HasResolvedValue() &&
          (mleft.right().ResolvedValue() & (A::WORD_SIZE - 1)) >=
1712
              base::bits::CountTrailingZeros(mask)) {
1713
        // (x << L) & (-1 << K) => x << L iff L >= K
1714 1715
        return Replace(mleft.node());
      }
1716 1717
    } else if (A::IsIntNAdd(m.left())) {
      typename A::IntNBinopMatcher mleft(m.left().node());
1718 1719 1720
      if (mleft.right().HasResolvedValue() &&
          (mleft.right().ResolvedValue() & mask) ==
              mleft.right().ResolvedValue()) {
1721
        // (x + (K << L)) & (-1 << L) => (x & (-1 << L)) + (K << L)
1722 1723
        node->ReplaceInput(0,
                           a.WordNAnd(mleft.left().node(), m.right().node()));
1724
        node->ReplaceInput(1, mleft.right().node());
1725
        NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1726
        return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1727
      }
1728 1729
      if (A::IsIntNMul(mleft.left())) {
        typename A::IntNBinopMatcher mleftleft(mleft.left().node());
1730
        if (mleftleft.right().IsMultipleOf(neg_mask)) {
1731
          // (y * (K << L) + x) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
1732 1733
          node->ReplaceInput(
              0, a.WordNAnd(mleft.right().node(), m.right().node()));
1734
          node->ReplaceInput(1, mleftleft.node());
1735
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1736
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1737
        }
1738
      }
1739 1740
      if (A::IsIntNMul(mleft.right())) {
        typename A::IntNBinopMatcher mleftright(mleft.right().node());
1741
        if (mleftright.right().IsMultipleOf(neg_mask)) {
1742 1743
          // (x + y * (K << L)) & (-1 << L) => (x & (-1 << L)) + y * (K << L)
          node->ReplaceInput(0,
1744
                             a.WordNAnd(mleft.left().node(), m.right().node()));
1745
          node->ReplaceInput(1, mleftright.node());
1746
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1747
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1748 1749
        }
      }
1750 1751
      if (A::IsWordNShl(mleft.left())) {
        typename A::IntNBinopMatcher mleftleft(mleft.left().node());
1752
        if (mleftleft.right().Is(base::bits::CountTrailingZeros(mask))) {
1753
          // (y << L + x) & (-1 << L) => (x & (-1 << L)) + y << L
1754 1755
          node->ReplaceInput(
              0, a.WordNAnd(mleft.right().node(), m.right().node()));
1756
          node->ReplaceInput(1, mleftleft.node());
1757
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1758
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1759 1760
        }
      }
1761 1762
      if (A::IsWordNShl(mleft.right())) {
        typename A::IntNBinopMatcher mleftright(mleft.right().node());
1763
        if (mleftright.right().Is(base::bits::CountTrailingZeros(mask))) {
1764 1765
          // (x + y << L) & (-1 << L) => (x & (-1 << L)) + y << L
          node->ReplaceInput(0,
1766
                             a.WordNAnd(mleft.left().node(), m.right().node()));
1767
          node->ReplaceInput(1, mleftright.node());
1768
          NodeProperties::ChangeOp(node, a.IntNAdd(machine()));
1769
          return Changed(node).FollowedBy(a.ReduceIntNAdd(node));
1770
        }
1771
      }
1772 1773
    } else if (A::IsIntNMul(m.left())) {
      typename A::IntNBinopMatcher mleft(m.left().node());
1774
      if (mleft.right().IsMultipleOf(neg_mask)) {
1775 1776 1777
        // (x * (K << L)) & (-1 << L) => x * (K << L)
        return Replace(mleft.node());
      }
1778
    }
1779 1780 1781 1782
  }
  return NoChange();
}

1783 1784 1785
namespace {

// Represents an operation of the form `(source & mask) == masked_value`.
1786
// where each bit set in masked_value also has to be set in mask.
1787
struct BitfieldCheck {
1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800
  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);
  }
1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813

  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());
1814
        if (mand.right().HasResolvedValue() && eq.right().HasResolvedValue()) {
1815 1816 1817
          uint32_t mask = mand.right().ResolvedValue();
          uint32_t masked_value = eq.right().ResolvedValue();
          if ((masked_value & ~mask) != 0) return {};
1818
          if (mand.left().IsTruncateInt64ToInt32()) {
1819 1820 1821 1822 1823
            return BitfieldCheck(
                NodeProperties::GetValueInput(mand.left().node(), 0), mask,
                masked_value, true);
          } else {
            return BitfieldCheck(mand.left().node(), mask, masked_value, false);
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 1852 1853 1854 1855 1856 1857 1858 1859
          }
        }
      }
    } 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);
1860 1861
      if (mand.right().HasResolvedValue() &&
          mand.right().ResolvedValue() == 1) {
1862 1863 1864
        if (WordNAdapter::IsWordNShr(mand.left()) ||
            WordNAdapter::IsWordNSar(mand.left())) {
          typename WordNAdapter::UintNBinopMatcher shift(mand.left().node());
1865 1866 1867
          if (shift.right().HasResolvedValue() &&
              shift.right().ResolvedValue() < 32u) {
            uint32_t mask = 1 << shift.right().ResolvedValue();
1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881
            return BitfieldCheck{shift.left().node(), mask, mask,
                                 WordNAdapter::WORD_SIZE == 64};
          }
        }
        return BitfieldCheck{mand.left().node(), 1, 1,
                             WordNAdapter::WORD_SIZE == 64};
      }
    }
    return {};
  }
};

}  // namespace

1882 1883
Reduction MachineOperatorReducer::ReduceWord32And(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32And, node->opcode());
1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907
  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();
1908 1909 1910 1911 1912 1913 1914
}

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

1915
Reduction MachineOperatorReducer::TryMatchWord32Ror(Node* node) {
1916 1917 1918 1919 1920 1921 1922 1923 1924
  // 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.

1925 1926
  DCHECK(IrOpcode::kWord32Or == node->opcode() ||
         IrOpcode::kWord32Xor == node->opcode());
1927
  Int32BinopMatcher m(node);
1928 1929
  Node* shl = nullptr;
  Node* shr = nullptr;
1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943
  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();

1944
  if (mshl.right().HasResolvedValue() && mshr.right().HasResolvedValue()) {
1945
    // Case where y is a constant.
1946 1947 1948 1949 1950
    if (mshl.right().ResolvedValue() + mshr.right().ResolvedValue() != 32) {
      return NoChange();
    }
    if (node->opcode() == IrOpcode::kWord32Xor &&
        (mshl.right().ResolvedValue() & 31) == 0) {
1951
      return NoChange();
1952
    }
1953
  } else {
1954 1955
    Node* sub = nullptr;
    Node* y = nullptr;
1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967
    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();
1968 1969 1970
    if (node->opcode() == IrOpcode::kWord32Xor) {
      return NoChange();  // Can't guarantee y & 31 != 0.
    }
1971 1972 1973 1974
  }

  node->ReplaceInput(0, mshl.left().node());
  node->ReplaceInput(1, mshr.right().node());
1975
  NodeProperties::ChangeOp(node, machine()->Word32Ror());
1976 1977 1978
  return Changed(node);
}

1979 1980 1981 1982 1983 1984
template <typename WordNAdapter>
Reduction MachineOperatorReducer::ReduceWordNOr(Node* node) {
  using A = WordNAdapter;
  A a(this);

  typename A::IntNBinopMatcher m(node);
1985 1986
  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
1987
  if (m.IsFoldable()) {  // K | K  => K  (K stands for arbitrary constants)
1988
    return a.ReplaceIntN(m.left().ResolvedValue() | m.right().ResolvedValue());
1989 1990 1991
  }
  if (m.LeftEqualsRight()) return Replace(m.left().node());  // x | x => x

1992 1993
  // (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.
1994
  if (m.right().HasResolvedValue()) {
1995 1996
    if (A::IsWordNAnd(m.left())) {
      typename A::IntNBinopMatcher mand(m.left().node());
1997 1998
      if (mand.right().HasResolvedValue()) {
        if ((m.right().ResolvedValue() | mand.right().ResolvedValue()) == -1) {
1999 2000 2001 2002 2003 2004 2005
          node->ReplaceInput(0, mand.left().node());
          return Changed(node);
        }
      }
    }
  }

2006
  return a.TryMatchWordNRor(node);
2007 2008
}

2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024
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);
2025
  if (m.right().Is(0)) return Replace(m.left().node());  // x ^ 0 => x
2026
  if (m.IsFoldable()) {  // K ^ K => K  (K stands for arbitrary constants)
2027
    return a.ReplaceIntN(m.left().ResolvedValue() ^ m.right().ResolvedValue());
2028 2029
  }
  if (m.LeftEqualsRight()) return ReplaceInt32(0);  // x ^ x => 0
2030 2031
  if (A::IsWordNXor(m.left()) && m.right().Is(-1)) {
    typename A::IntNBinopMatcher mleft(m.left().node());
2032 2033 2034 2035 2036
    if (mleft.right().Is(-1)) {  // (x ^ -1) ^ -1 => x
      return Replace(mleft.left().node());
    }
  }

2037 2038 2039 2040 2041
  return a.TryMatchWordNRor(node);
}

Reduction MachineOperatorReducer::ReduceWord32Xor(Node* node) {
  DCHECK_EQ(IrOpcode::kWord32Xor, node->opcode());
2042 2043 2044 2045
  Int32BinopMatcher m(node);
  if (m.right().IsWord32Equal() && m.left().Is(1)) {
    return Replace(Word32Equal(m.right().node(), Int32Constant(0)));
  }
2046 2047 2048 2049 2050 2051
  return ReduceWordNXor<Word32Adapter>(node);
}

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

2054 2055
Reduction MachineOperatorReducer::ReduceWord32Equal(Node* node) {
  Int32BinopMatcher m(node);
2056
  if (m.IsFoldable()) {  // K == K => K  (K stands for arbitrary constants)
2057
    return ReplaceBool(m.left().ResolvedValue() == m.right().ResolvedValue());
2058 2059 2060 2061 2062 2063 2064 2065 2066
  }
  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
2067
  if (m.right().HasResolvedValue()) {
2068 2069 2070 2071
    base::Optional<std::pair<Node*, uint32_t>> replacements;
    if (m.left().IsTruncateInt64ToInt32()) {
      replacements = ReduceWord32EqualForConstantRhs<Word64Adapter>(
          NodeProperties::GetValueInput(m.left().node(), 0),
2072
          static_cast<uint32_t>(m.right().ResolvedValue()));
2073 2074
    } else {
      replacements = ReduceWord32EqualForConstantRhs<Word32Adapter>(
2075
          m.left().node(), static_cast<uint32_t>(m.right().ResolvedValue()));
2076 2077 2078 2079 2080 2081 2082
    }
    if (replacements) {
      node->ReplaceInput(0, replacements->first);
      node->ReplaceInput(1, Uint32Constant(replacements->second));
      return Changed(node);
    }
  }
2083 2084 2085 2086 2087
  // This is a workaround for not having escape analysis for wasm
  // (machine-level) turbofan graphs.
  if (!ObjectsMayAlias(m.left().node(), m.right().node())) {
    return ReplaceBool(false);
  }
2088 2089 2090 2091

  return NoChange();
}

2092 2093 2094 2095
Reduction MachineOperatorReducer::ReduceFloat64InsertLowWord32(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64InsertLowWord32, node->opcode());
  Float64Matcher mlhs(node->InputAt(0));
  Uint32Matcher mrhs(node->InputAt(1));
2096 2097
  if (mlhs.HasResolvedValue() && mrhs.HasResolvedValue()) {
    return ReplaceFloat64(
2098 2099 2100
        base::bit_cast<double>((base::bit_cast<uint64_t>(mlhs.ResolvedValue()) &
                                uint64_t{0xFFFFFFFF00000000}) |
                               mrhs.ResolvedValue()));
2101 2102 2103 2104 2105 2106 2107 2108
  }
  return NoChange();
}

Reduction MachineOperatorReducer::ReduceFloat64InsertHighWord32(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64InsertHighWord32, node->opcode());
  Float64Matcher mlhs(node->InputAt(0));
  Uint32Matcher mrhs(node->InputAt(1));
2109
  if (mlhs.HasResolvedValue() && mrhs.HasResolvedValue()) {
2110 2111 2112
    return ReplaceFloat64(base::bit_cast<double>(
        (base::bit_cast<uint64_t>(mlhs.ResolvedValue()) &
         uint64_t{0xFFFFFFFF}) |
2113
        (static_cast<uint64_t>(mrhs.ResolvedValue()) << 32)));
2114 2115 2116 2117
  }
  return NoChange();
}

2118 2119 2120
namespace {

bool IsFloat64RepresentableAsFloat32(const Float64Matcher& m) {
2121 2122
  if (m.HasResolvedValue()) {
    double v = m.ResolvedValue();
2123
    return DoubleToFloat32(v) == v;
2124 2125 2126 2127 2128 2129
  }
  return false;
}

}  // namespace

2130
Reduction MachineOperatorReducer::ReduceFloat64Compare(Node* node) {
2131 2132 2133
  DCHECK(IrOpcode::kFloat64Equal == node->opcode() ||
         IrOpcode::kFloat64LessThan == node->opcode() ||
         IrOpcode::kFloat64LessThanOrEqual == node->opcode());
2134
  Float64BinopMatcher m(node);
2135 2136 2137
  if (m.IsFoldable()) {
    switch (node->opcode()) {
      case IrOpcode::kFloat64Equal:
2138 2139
        return ReplaceBool(m.left().ResolvedValue() ==
                           m.right().ResolvedValue());
2140
      case IrOpcode::kFloat64LessThan:
2141 2142
        return ReplaceBool(m.left().ResolvedValue() <
                           m.right().ResolvedValue());
2143
      case IrOpcode::kFloat64LessThanOrEqual:
2144 2145
        return ReplaceBool(m.left().ResolvedValue() <=
                           m.right().ResolvedValue());
2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159
      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.
2160 2161
    switch (node->opcode()) {
      case IrOpcode::kFloat64Equal:
2162
        NodeProperties::ChangeOp(node, machine()->Float32Equal());
2163 2164
        break;
      case IrOpcode::kFloat64LessThan:
2165
        NodeProperties::ChangeOp(node, machine()->Float32LessThan());
2166 2167
        break;
      case IrOpcode::kFloat64LessThanOrEqual:
2168
        NodeProperties::ChangeOp(node, machine()->Float32LessThanOrEqual());
2169 2170
        break;
      default:
2171
        UNREACHABLE();
2172
    }
2173
    node->ReplaceInput(
2174 2175
        0, m.left().HasResolvedValue()
               ? Float32Constant(static_cast<float>(m.left().ResolvedValue()))
2176 2177
               : m.left().InputAt(0));
    node->ReplaceInput(
2178 2179
        1, m.right().HasResolvedValue()
               ? Float32Constant(static_cast<float>(m.right().ResolvedValue()))
2180
               : m.right().InputAt(0));
2181 2182 2183 2184 2185
    return Changed(node);
  }
  return NoChange();
}

2186 2187 2188
Reduction MachineOperatorReducer::ReduceFloat64RoundDown(Node* node) {
  DCHECK_EQ(IrOpcode::kFloat64RoundDown, node->opcode());
  Float64Matcher m(node->InputAt(0));
2189 2190
  if (m.HasResolvedValue()) {
    return ReplaceFloat64(std::floor(m.ResolvedValue()));
2191 2192 2193
  }
  return NoChange();
}
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 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292
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(
2293
              node, common()->DeoptimizeUnless(p.reason(), p.feedback()));
2294 2295 2296 2297 2298
          break;
        }
        case IrOpcode::kDeoptimizeUnless: {
          DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
          NodeProperties::ChangeOp(
2299
              node, common()->DeoptimizeIf(p.reason(), p.feedback()));
2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311
          break;
        }
        default:

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

2312 2313 2314 2315 2316 2317 2318 2319 2320 2321
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));
2322
  Reduction reduction = NoChange();
2323 2324 2325 2326
  if (condition.IsTruncateInt64ToInt32()) {
    if (auto replacement =
            ReduceConditionalN<Word64Adapter>(condition.node())) {
      NodeProperties::ReplaceValueInput(node, *replacement, 0);
2327
      reduction = Changed(node);
2328 2329 2330
    }
  } else if (auto replacement = ReduceConditionalN<Word32Adapter>(node)) {
    NodeProperties::ReplaceValueInput(node, *replacement, 0);
2331
    reduction = Changed(node);
2332
  }
2333
  return reduction.FollowedBy(SimplifyBranch(node));
2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356
}

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())) &&
2357
        mand.right().HasResolvedValue()) {
2358 2359
      typename WordNAdapter::UintNBinopMatcher mshift(mand.left().node());
      // ((x >> K1) & K2) == K3 => (x & (K2 << K1)) == (K3 << K1)
2360 2361 2362
      if (mshift.right().HasResolvedValue()) {
        auto shift_bits = mshift.right().ResolvedValue();
        auto mask = mand.right().ResolvedValue();
2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375
        // 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);
2376 2377 2378 2379
        }
      }
    }
  }
2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391
  // 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);
      }
    }
  }
2392
  return {};
2393 2394
}

2395
CommonOperatorBuilder* MachineOperatorReducer::common() const {
2396
  return mcgraph()->common();
2397
}
2398

2399
MachineOperatorBuilder* MachineOperatorReducer::machine() const {
2400
  return mcgraph()->machine();
2401 2402
}

2403
Graph* MachineOperatorReducer::graph() const { return mcgraph()->graph(); }
2404 2405 2406 2407

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