src/compiler/js-typed-lowering.cc

// 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/access-builder.h"
#include "src/compiler/graph-inl.h"
#include "src/compiler/js-builtin-reducer.h"
#include "src/compiler/js-typed-lowering.h"
#include "src/compiler/node-aux-data-inl.h"
#include "src/compiler/node-properties-inl.h"
#include "src/types.h"

namespace v8 {
namespace internal {
namespace compiler {

// TODO(turbofan): js-typed-lowering improvements possible
// - immediately put in type bounds for all new nodes
// - relax effects from generic but not-side-effecting operations
// - relax effects for ToNumber(mixed)


// Relax the effects of {node} by immediately replacing effect uses of {node}
// with the effect input to {node}.
// TODO(turbofan): replace the effect input to {node} with {graph->start()}.
// TODO(titzer): move into a GraphEditor?
static void RelaxEffects(Node* node) {
  NodeProperties::ReplaceWithValue(node, node, NULL);
}


JSTypedLowering::~JSTypedLowering() {}


Reduction JSTypedLowering::ReplaceEagerly(Node* old, Node* node) {
  NodeProperties::ReplaceWithValue(old, node, node);
  return Changed(node);
}


// A helper class to simplify the process of reducing a single binop node with a
// JSOperator. This class manages the rewriting of context, control, and effect
// dependencies during lowering of a binop and contains numerous helper
// functions for matching the types of inputs to an operation.
class JSBinopReduction {
 public:
  JSBinopReduction(JSTypedLowering* lowering, Node* node)
      : lowering_(lowering),
        node_(node),
        left_type_(NodeProperties::GetBounds(node->InputAt(0)).upper),
        right_type_(NodeProperties::GetBounds(node->InputAt(1)).upper) {}

  void ConvertInputsToNumber() {
    node_->ReplaceInput(0, ConvertToNumber(left()));
    node_->ReplaceInput(1, ConvertToNumber(right()));
  }

  void ConvertInputsToInt32(bool left_signed, bool right_signed) {
    node_->ReplaceInput(0, ConvertToI32(left_signed, left()));
    node_->ReplaceInput(1, ConvertToI32(right_signed, right()));
  }

  void ConvertInputsToString() {
    node_->ReplaceInput(0, ConvertToString(left()));
    node_->ReplaceInput(1, ConvertToString(right()));
  }

  // Convert inputs for bitwise shift operation (ES5 spec 11.7).
  void ConvertInputsForShift(bool left_signed) {
    node_->ReplaceInput(0, ConvertToI32(left_signed, left()));
    Node* rnum = ConvertToI32(false, right());
    node_->ReplaceInput(1, graph()->NewNode(machine()->Word32And(), rnum,
                                            jsgraph()->Int32Constant(0x1F)));
  }

  void SwapInputs() {
    Node* l = left();
    Node* r = right();
    node_->ReplaceInput(0, r);
    node_->ReplaceInput(1, l);
    std::swap(left_type_, right_type_);
  }

  // Remove all effect and control inputs and outputs to this node and change
  // to the pure operator {op}, possibly inserting a boolean inversion.
  Reduction ChangeToPureOperator(const Operator* op, bool invert = false) {
    DCHECK_EQ(0, OperatorProperties::GetEffectInputCount(op));
    DCHECK_EQ(false, OperatorProperties::HasContextInput(op));
    DCHECK_EQ(0, OperatorProperties::GetControlInputCount(op));
    DCHECK_EQ(2, OperatorProperties::GetValueInputCount(op));

    // Remove the effects from the node, if any, and update its effect usages.
    if (OperatorProperties::GetEffectInputCount(node_->op()) > 0) {
      RelaxEffects(node_);
    }
    // Remove the inputs corresponding to context, effect, and control.
    NodeProperties::RemoveNonValueInputs(node_);
    // Finally, update the operator to the new one.
    node_->set_op(op);

    if (invert) {
      // Insert an boolean not to invert the value.
      Node* value = graph()->NewNode(simplified()->BooleanNot(), node_);
      node_->ReplaceUses(value);
      // Note: ReplaceUses() smashes all uses, so smash it back here.
      value->ReplaceInput(0, node_);
      return lowering_->ReplaceWith(value);
    }
    return lowering_->Changed(node_);
  }

  bool OneInputIs(Type* t) { return left_type_->Is(t) || right_type_->Is(t); }

  bool BothInputsAre(Type* t) {
    return left_type_->Is(t) && right_type_->Is(t);
  }

  bool OneInputCannotBe(Type* t) {
    return !left_type_->Maybe(t) || !right_type_->Maybe(t);
  }

  bool NeitherInputCanBe(Type* t) {
    return !left_type_->Maybe(t) && !right_type_->Maybe(t);
  }

  Node* effect() { return NodeProperties::GetEffectInput(node_); }
  Node* control() { return NodeProperties::GetControlInput(node_); }
  Node* context() { return NodeProperties::GetContextInput(node_); }
  Node* left() { return NodeProperties::GetValueInput(node_, 0); }
  Node* right() { return NodeProperties::GetValueInput(node_, 1); }
  Type* left_type() { return left_type_; }
  Type* right_type() { return right_type_; }

  SimplifiedOperatorBuilder* simplified() { return lowering_->simplified(); }
  Graph* graph() { return lowering_->graph(); }
  JSGraph* jsgraph() { return lowering_->jsgraph(); }
  JSOperatorBuilder* javascript() { return lowering_->javascript(); }
  MachineOperatorBuilder* machine() { return lowering_->machine(); }

 private:
  JSTypedLowering* lowering_;  // The containing lowering instance.
  Node* node_;                 // The original node.
  Type* left_type_;            // Cache of the left input's type.
  Type* right_type_;           // Cache of the right input's type.

  Node* ConvertToString(Node* node) {
    // Avoid introducing too many eager ToString() operations.
    Reduction reduced = lowering_->ReduceJSToStringInput(node);
    if (reduced.Changed()) return reduced.replacement();
    Node* n = graph()->NewNode(javascript()->ToString(), node, context(),
                               effect(), control());
    update_effect(n);
    return n;
  }

  Node* ConvertToNumber(Node* node) {
    // Avoid introducing too many eager ToNumber() operations.
    Reduction reduced = lowering_->ReduceJSToNumberInput(node);
    if (reduced.Changed()) return reduced.replacement();
    Node* n = graph()->NewNode(javascript()->ToNumber(), node, context(),
                               effect(), control());
    update_effect(n);
    return n;
  }

  // Try to narrowing a double or number operation to an Int32 operation.
  bool TryNarrowingToI32(Type* type, Node* node) {
    switch (node->opcode()) {
      case IrOpcode::kFloat64Add:
      case IrOpcode::kNumberAdd: {
        JSBinopReduction r(lowering_, node);
        if (r.BothInputsAre(Type::Integral32())) {
          node->set_op(lowering_->machine()->Int32Add());
          // TODO(titzer): narrow bounds instead of overwriting.
          NodeProperties::SetBounds(node, Bounds(type));
          return true;
        }
      }
      case IrOpcode::kFloat64Sub:
      case IrOpcode::kNumberSubtract: {
        JSBinopReduction r(lowering_, node);
        if (r.BothInputsAre(Type::Integral32())) {
          node->set_op(lowering_->machine()->Int32Sub());
          // TODO(titzer): narrow bounds instead of overwriting.
          NodeProperties::SetBounds(node, Bounds(type));
          return true;
        }
      }
      default:
        return false;
    }
  }

  Node* ConvertToI32(bool is_signed, Node* node) {
    Type* type = is_signed ? Type::Signed32() : Type::Unsigned32();
    if (node->OwnedBy(node_)) {
      // If this node {node_} has the only edge to {node}, then try narrowing
      // its operation to an Int32 add or subtract.
      if (TryNarrowingToI32(type, node)) return node;
    } else {
      // Otherwise, {node} has multiple uses. Leave it as is and let the
      // further lowering passes deal with it, which use a full backwards
      // fixpoint.
    }

    // Avoid introducing too many eager NumberToXXnt32() operations.
    node = ConvertToNumber(node);
    Type* input_type = NodeProperties::GetBounds(node).upper;

    if (input_type->Is(type)) return node;  // already in the value range.

    const Operator* op = is_signed ? simplified()->NumberToInt32()
                                   : simplified()->NumberToUint32();
    Node* n = graph()->NewNode(op, node);
    return n;
  }

  void update_effect(Node* effect) {
    NodeProperties::ReplaceEffectInput(node_, effect);
  }
};


Reduction JSTypedLowering::ReduceJSAdd(Node* node) {
  JSBinopReduction r(this, node);
  if (r.BothInputsAre(Type::Number())) {
    // JSAdd(x:number, y:number) => NumberAdd(x, y)
    return r.ChangeToPureOperator(simplified()->NumberAdd());
  }
  Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
  if (r.NeitherInputCanBe(maybe_string)) {
    // JSAdd(x:-string, y:-string) => NumberAdd(ToNumber(x), ToNumber(y))
    r.ConvertInputsToNumber();
    return r.ChangeToPureOperator(simplified()->NumberAdd());
  }
#if 0
  // TODO(turbofan): Lowering of StringAdd is disabled for now because:
  //   a) The inserted ToString operation screws up valueOf vs. toString order.
  //   b) Deoptimization at ToString doesn't have corresponding bailout id.
  //   c) Our current StringAddStub is actually non-pure and requires context.
  if (r.OneInputIs(Type::String())) {
    // JSAdd(x:string, y:string) => StringAdd(x, y)
    // JSAdd(x:string, y) => StringAdd(x, ToString(y))
    // JSAdd(x, y:string) => StringAdd(ToString(x), y)
    r.ConvertInputsToString();
    return r.ChangeToPureOperator(simplified()->StringAdd());
  }
#endif
  return NoChange();
}


Reduction JSTypedLowering::ReduceNumberBinop(Node* node,
                                             const Operator* numberOp) {
  JSBinopReduction r(this, node);
  if (r.OneInputIs(Type::Primitive())) {
    // If at least one input is a primitive, then insert appropriate conversions
    // to number and reduce this operator to the given numeric one.
    // TODO(turbofan): make this heuristic configurable for code size.
    r.ConvertInputsToNumber();
    return r.ChangeToPureOperator(numberOp);
  }
  // TODO(turbofan): relax/remove the effects of this operator in other cases.
  return NoChange();
}


Reduction JSTypedLowering::ReduceI32Binop(Node* node, bool left_signed,
                                          bool right_signed,
                                          const Operator* intOp) {
  JSBinopReduction r(this, node);
  // TODO(titzer): some Smi bitwise operations don't really require going
  // all the way to int32, which can save tagging/untagging for some operations
  // on some platforms.
  // TODO(turbofan): make this heuristic configurable for code size.
  r.ConvertInputsToInt32(left_signed, right_signed);
  return r.ChangeToPureOperator(intOp);
}


Reduction JSTypedLowering::ReduceI32Shift(Node* node, bool left_signed,
                                          const Operator* shift_op) {
  JSBinopReduction r(this, node);
  r.ConvertInputsForShift(left_signed);
  return r.ChangeToPureOperator(shift_op);
}


Reduction JSTypedLowering::ReduceJSComparison(Node* node) {
  JSBinopReduction r(this, node);
  if (r.BothInputsAre(Type::String())) {
    // If both inputs are definitely strings, perform a string comparison.
    const Operator* stringOp;
    switch (node->opcode()) {
      case IrOpcode::kJSLessThan:
        stringOp = simplified()->StringLessThan();
        break;
      case IrOpcode::kJSGreaterThan:
        stringOp = simplified()->StringLessThan();
        r.SwapInputs();  // a > b => b < a
        break;
      case IrOpcode::kJSLessThanOrEqual:
        stringOp = simplified()->StringLessThanOrEqual();
        break;
      case IrOpcode::kJSGreaterThanOrEqual:
        stringOp = simplified()->StringLessThanOrEqual();
        r.SwapInputs();  // a >= b => b <= a
        break;
      default:
        return NoChange();
    }
    return r.ChangeToPureOperator(stringOp);
  }
  Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
  if (r.OneInputCannotBe(maybe_string)) {
    // If one input cannot be a string, then emit a number comparison.
    const Operator* less_than;
    const Operator* less_than_or_equal;
    if (r.BothInputsAre(Type::Unsigned32())) {
      less_than = machine()->Uint32LessThan();
      less_than_or_equal = machine()->Uint32LessThanOrEqual();
    } else if (r.BothInputsAre(Type::Signed32())) {
      less_than = machine()->Int32LessThan();
      less_than_or_equal = machine()->Int32LessThanOrEqual();
    } else {
      // TODO(turbofan): mixed signed/unsigned int32 comparisons.
      r.ConvertInputsToNumber();
      less_than = simplified()->NumberLessThan();
      less_than_or_equal = simplified()->NumberLessThanOrEqual();
    }
    const Operator* comparison;
    switch (node->opcode()) {
      case IrOpcode::kJSLessThan:
        comparison = less_than;
        break;
      case IrOpcode::kJSGreaterThan:
        comparison = less_than;
        r.SwapInputs();  // a > b => b < a
        break;
      case IrOpcode::kJSLessThanOrEqual:
        comparison = less_than_or_equal;
        break;
      case IrOpcode::kJSGreaterThanOrEqual:
        comparison = less_than_or_equal;
        r.SwapInputs();  // a >= b => b <= a
        break;
      default:
        return NoChange();
    }
    return r.ChangeToPureOperator(comparison);
  }
  // TODO(turbofan): relax/remove effects of this operator in other cases.
  return NoChange();  // Keep a generic comparison.
}


Reduction JSTypedLowering::ReduceJSEqual(Node* node, bool invert) {
  JSBinopReduction r(this, node);

  if (r.BothInputsAre(Type::Number())) {
    return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
  }
  if (r.BothInputsAre(Type::String())) {
    return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
  }
  if (r.BothInputsAre(Type::Receiver())) {
    return r.ChangeToPureOperator(
        simplified()->ReferenceEqual(Type::Receiver()), invert);
  }
  // TODO(turbofan): js-typed-lowering of Equal(undefined)
  // TODO(turbofan): js-typed-lowering of Equal(null)
  // TODO(turbofan): js-typed-lowering of Equal(boolean)
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSStrictEqual(Node* node, bool invert) {
  JSBinopReduction r(this, node);
  if (r.left() == r.right()) {
    // x === x is always true if x != NaN
    if (!r.left_type()->Maybe(Type::NaN())) {
      return ReplaceEagerly(node, invert ? jsgraph()->FalseConstant()
                                         : jsgraph()->TrueConstant());
    }
  }
  if (!r.left_type()->Maybe(r.right_type())) {
    // Type intersection is empty; === is always false unless both
    // inputs could be strings (one internalized and one not).
    if (r.OneInputCannotBe(Type::String())) {
      return ReplaceEagerly(node, invert ? jsgraph()->TrueConstant()
                                         : jsgraph()->FalseConstant());
    }
  }
  if (r.OneInputIs(Type::Undefined())) {
    return r.ChangeToPureOperator(
        simplified()->ReferenceEqual(Type::Undefined()), invert);
  }
  if (r.OneInputIs(Type::Null())) {
    return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Null()),
                                  invert);
  }
  if (r.OneInputIs(Type::Boolean())) {
    return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Boolean()),
                                  invert);
  }
  if (r.OneInputIs(Type::Object())) {
    return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Object()),
                                  invert);
  }
  if (r.OneInputIs(Type::Receiver())) {
    return r.ChangeToPureOperator(
        simplified()->ReferenceEqual(Type::Receiver()), invert);
  }
  if (r.BothInputsAre(Type::String())) {
    return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
  }
  if (r.BothInputsAre(Type::Number())) {
    return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
  }
  // TODO(turbofan): js-typed-lowering of StrictEqual(mixed types)
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSToNumberInput(Node* input) {
  if (input->opcode() == IrOpcode::kJSToNumber) {
    // Recursively try to reduce the input first.
    Reduction result = ReduceJSToNumberInput(input->InputAt(0));
    if (result.Changed()) {
      RelaxEffects(input);
      return result;
    }
    return Changed(input);  // JSToNumber(JSToNumber(x)) => JSToNumber(x)
  }
  Type* input_type = NodeProperties::GetBounds(input).upper;
  if (input_type->Is(Type::Number())) {
    // JSToNumber(x:number) => x
    return Changed(input);
  }
  if (input_type->Is(Type::Undefined())) {
    // JSToNumber(undefined) => #NaN
    return ReplaceWith(jsgraph()->NaNConstant());
  }
  if (input_type->Is(Type::Null())) {
    // JSToNumber(null) => #0
    return ReplaceWith(jsgraph()->ZeroConstant());
  }
  if (input_type->Is(Type::Boolean())) {
    // JSToNumber(x:boolean) => BooleanToNumber(x)
    return ReplaceWith(
        graph()->NewNode(simplified()->BooleanToNumber(), input));
  }
  // TODO(turbofan): js-typed-lowering of ToNumber(x:string)
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSToStringInput(Node* input) {
  if (input->opcode() == IrOpcode::kJSToString) {
    // Recursively try to reduce the input first.
    Reduction result = ReduceJSToStringInput(input->InputAt(0));
    if (result.Changed()) {
      RelaxEffects(input);
      return result;
    }
    return Changed(input);  // JSToString(JSToString(x)) => JSToString(x)
  }
  Type* input_type = NodeProperties::GetBounds(input).upper;
  if (input_type->Is(Type::String())) {
    return Changed(input);  // JSToString(x:string) => x
  }
  if (input_type->Is(Type::Undefined())) {
    return ReplaceWith(jsgraph()->HeapConstant(
        graph()->zone()->isolate()->factory()->undefined_string()));
  }
  if (input_type->Is(Type::Null())) {
    return ReplaceWith(jsgraph()->HeapConstant(
        graph()->zone()->isolate()->factory()->null_string()));
  }
  // TODO(turbofan): js-typed-lowering of ToString(x:boolean)
  // TODO(turbofan): js-typed-lowering of ToString(x:number)
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSToBooleanInput(Node* input) {
  if (input->opcode() == IrOpcode::kJSToBoolean) {
    // Recursively try to reduce the input first.
    Reduction result = ReduceJSToBooleanInput(input->InputAt(0));
    if (result.Changed()) {
      RelaxEffects(input);
      return result;
    }
    return Changed(input);  // JSToBoolean(JSToBoolean(x)) => JSToBoolean(x)
  }
  Type* input_type = NodeProperties::GetBounds(input).upper;
  if (input_type->Is(Type::Boolean())) {
    return Changed(input);  // JSToBoolean(x:boolean) => x
  }
  if (input_type->Is(Type::Undefined())) {
    // JSToBoolean(undefined) => #false
    return ReplaceWith(jsgraph()->FalseConstant());
  }
  if (input_type->Is(Type::Null())) {
    // JSToBoolean(null) => #false
    return ReplaceWith(jsgraph()->FalseConstant());
  }
  if (input_type->Is(Type::DetectableReceiver())) {
    // JSToBoolean(x:detectable) => #true
    return ReplaceWith(jsgraph()->TrueConstant());
  }
  if (input_type->Is(Type::Undetectable())) {
    // JSToBoolean(x:undetectable) => #false
    return ReplaceWith(jsgraph()->FalseConstant());
  }
  if (input_type->Is(Type::OrderedNumber())) {
    // JSToBoolean(x:ordered-number) => BooleanNot(NumberEqual(x, #0))
    Node* cmp = graph()->NewNode(simplified()->NumberEqual(), input,
                                 jsgraph()->ZeroConstant());
    Node* inv = graph()->NewNode(simplified()->BooleanNot(), cmp);
    return ReplaceWith(inv);
  }
  // TODO(turbofan): js-typed-lowering of ToBoolean(string)
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSLoadProperty(Node* node) {
  Node* key = NodeProperties::GetValueInput(node, 1);
  Node* base = NodeProperties::GetValueInput(node, 0);
  Type* key_type = NodeProperties::GetBounds(key).upper;
  Type* base_type = NodeProperties::GetBounds(base).upper;
  // TODO(mstarzinger): This lowering is not correct if:
  //   a) The typed array turns external (i.e. MaterializeArrayBuffer)
  //   b) The typed array or it's buffer is neutered.
  //   c) The index is out of bounds.
  if (base_type->IsConstant() && key_type->Is(Type::Integral32()) &&
      base_type->AsConstant()->Value()->IsJSTypedArray()) {
    // JSLoadProperty(typed-array, int32)
    JSTypedArray* array = JSTypedArray::cast(*base_type->AsConstant()->Value());
    ElementsKind elements_kind = array->map()->elements_kind();
    ExternalArrayType type = array->type();
    uint32_t length;
    CHECK(array->length()->ToUint32(&length));
    ElementAccess element_access;
    Node* elements = graph()->NewNode(
        simplified()->LoadField(AccessBuilder::ForJSObjectElements()), base,
        NodeProperties::GetEffectInput(node));
    if (IsExternalArrayElementsKind(elements_kind)) {
      elements = graph()->NewNode(
          simplified()->LoadField(AccessBuilder::ForExternalArrayPointer()),
          elements, NodeProperties::GetEffectInput(node));
      element_access = AccessBuilder::ForTypedArrayElement(type, true);
    } else {
      DCHECK(IsFixedTypedArrayElementsKind(elements_kind));
      element_access = AccessBuilder::ForTypedArrayElement(type, false);
    }
    Node* value =
        graph()->NewNode(simplified()->LoadElement(element_access), elements,
                         key, jsgraph()->Uint32Constant(length),
                         NodeProperties::GetEffectInput(node));
    return ReplaceEagerly(node, value);
  }
  return NoChange();
}


Reduction JSTypedLowering::ReduceJSStoreProperty(Node* node) {
  Node* key = NodeProperties::GetValueInput(node, 1);
  Node* base = NodeProperties::GetValueInput(node, 0);
  Node* value = NodeProperties::GetValueInput(node, 2);
  Type* key_type = NodeProperties::GetBounds(key).upper;
  Type* base_type = NodeProperties::GetBounds(base).upper;
  // TODO(mstarzinger): This lowering is not correct if:
  //   a) The typed array turns external (i.e. MaterializeArrayBuffer)
  //   b) The typed array or it's buffer is neutered.
  if (key_type->Is(Type::Integral32()) && base_type->IsConstant() &&
      base_type->AsConstant()->Value()->IsJSTypedArray()) {
    // JSStoreProperty(typed-array, int32, value)
    JSTypedArray* array = JSTypedArray::cast(*base_type->AsConstant()->Value());
    ElementsKind elements_kind = array->map()->elements_kind();
    ExternalArrayType type = array->type();
    uint32_t length;
    CHECK(array->length()->ToUint32(&length));
    ElementAccess element_access;
    Node* elements = graph()->NewNode(
        simplified()->LoadField(AccessBuilder::ForJSObjectElements()), base,
        NodeProperties::GetEffectInput(node));
    if (IsExternalArrayElementsKind(elements_kind)) {
      elements = graph()->NewNode(
          simplified()->LoadField(AccessBuilder::ForExternalArrayPointer()),
          elements, NodeProperties::GetEffectInput(node));
      element_access = AccessBuilder::ForTypedArrayElement(type, true);
    } else {
      DCHECK(IsFixedTypedArrayElementsKind(elements_kind));
      element_access = AccessBuilder::ForTypedArrayElement(type, false);
    }

    Node* check = graph()->NewNode(machine()->Uint32LessThan(), key,
                                   jsgraph()->Uint32Constant(length));
    Node* branch = graph()->NewNode(common()->Branch(), check,
                                    NodeProperties::GetControlInput(node));

    Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
    Node* store =
        graph()->NewNode(simplified()->StoreElement(element_access), elements,
                         key, jsgraph()->Uint32Constant(length), value,
                         NodeProperties::GetEffectInput(node), if_true);

    Node* if_false = graph()->NewNode(common()->IfFalse(), branch);

    Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
    Node* phi = graph()->NewNode(common()->EffectPhi(2), store,
                                 NodeProperties::GetEffectInput(node), merge);

    return ReplaceWith(phi);
  }
  return NoChange();
}


static Reduction ReplaceWithReduction(Node* node, Reduction reduction) {
  if (reduction.Changed()) {
    NodeProperties::ReplaceWithValue(node, reduction.replacement());
    return reduction;
  }
  return Reducer::NoChange();
}


Reduction JSTypedLowering::Reduce(Node* node) {
  switch (node->opcode()) {
    case IrOpcode::kJSEqual:
      return ReduceJSEqual(node, false);
    case IrOpcode::kJSNotEqual:
      return ReduceJSEqual(node, true);
    case IrOpcode::kJSStrictEqual:
      return ReduceJSStrictEqual(node, false);
    case IrOpcode::kJSStrictNotEqual:
      return ReduceJSStrictEqual(node, true);
    case IrOpcode::kJSLessThan:         // fall through
    case IrOpcode::kJSGreaterThan:      // fall through
    case IrOpcode::kJSLessThanOrEqual:  // fall through
    case IrOpcode::kJSGreaterThanOrEqual:
      return ReduceJSComparison(node);
    case IrOpcode::kJSBitwiseOr:
      return ReduceI32Binop(node, true, true, machine()->Word32Or());
    case IrOpcode::kJSBitwiseXor:
      return ReduceI32Binop(node, true, true, machine()->Word32Xor());
    case IrOpcode::kJSBitwiseAnd:
      return ReduceI32Binop(node, true, true, machine()->Word32And());
    case IrOpcode::kJSShiftLeft:
      return ReduceI32Shift(node, true, machine()->Word32Shl());
    case IrOpcode::kJSShiftRight:
      return ReduceI32Shift(node, true, machine()->Word32Sar());
    case IrOpcode::kJSShiftRightLogical:
      return ReduceI32Shift(node, false, machine()->Word32Shr());
    case IrOpcode::kJSAdd:
      return ReduceJSAdd(node);
    case IrOpcode::kJSSubtract:
      return ReduceNumberBinop(node, simplified()->NumberSubtract());
    case IrOpcode::kJSMultiply:
      return ReduceNumberBinop(node, simplified()->NumberMultiply());
    case IrOpcode::kJSDivide:
      return ReduceNumberBinop(node, simplified()->NumberDivide());
    case IrOpcode::kJSModulus:
      return ReduceNumberBinop(node, simplified()->NumberModulus());
    case IrOpcode::kJSUnaryNot: {
      Reduction result = ReduceJSToBooleanInput(node->InputAt(0));
      Node* value;
      if (result.Changed()) {
        // JSUnaryNot(x:boolean) => BooleanNot(x)
        value =
            graph()->NewNode(simplified()->BooleanNot(), result.replacement());
        NodeProperties::ReplaceWithValue(node, value);
        return Changed(value);
      } else {
        // JSUnaryNot(x) => BooleanNot(JSToBoolean(x))
        value = graph()->NewNode(simplified()->BooleanNot(), node);
        node->set_op(javascript()->ToBoolean());
        NodeProperties::ReplaceWithValue(node, value, node);
        // Note: ReplaceUses() smashes all uses, so smash it back here.
        value->ReplaceInput(0, node);
        return Changed(node);
      }
    }
    case IrOpcode::kJSToBoolean:
      return ReplaceWithReduction(node,
                                  ReduceJSToBooleanInput(node->InputAt(0)));
    case IrOpcode::kJSToNumber:
      return ReplaceWithReduction(node,
                                  ReduceJSToNumberInput(node->InputAt(0)));
    case IrOpcode::kJSToString:
      return ReplaceWithReduction(node,
                                  ReduceJSToStringInput(node->InputAt(0)));
    case IrOpcode::kJSLoadProperty:
      return ReduceJSLoadProperty(node);
    case IrOpcode::kJSStoreProperty:
      return ReduceJSStoreProperty(node);
    case IrOpcode::kJSCallFunction:
      return JSBuiltinReducer(jsgraph()).Reduce(node);
    default:
      break;
  }
  return NoChange();
}

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