src/v8/src/compiler/js-typed-lowering.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/access-builder.h"
   6 #include "src/compiler/graph-inl.h"
   7 #include "src/compiler/js-builtin-reducer.h"
   8 #include "src/compiler/js-typed-lowering.h"
   9 #include "src/compiler/node-aux-data-inl.h"
  10 #include "src/compiler/node-properties-inl.h"
  11 #include "src/types.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15 namespace compiler {
  16
  17 // TODO(turbofan): js-typed-lowering improvements possible
  18 // - immediately put in type bounds for all new nodes
  19 // - relax effects from generic but not-side-effecting operations
  20 // - relax effects for ToNumber(mixed)
  21
  22
  23 // Relax the effects of {node} by immediately replacing effect uses of {node}
  24 // with the effect input to {node}.
  25 // TODO(turbofan): replace the effect input to {node} with {graph->start()}.
  26 // TODO(titzer): move into a GraphEditor?
  27 static void RelaxEffects(Node* node) {
  28   NodeProperties::ReplaceWithValue(node, node, NULL);
  29 }
  30
  31
  32 JSTypedLowering::~JSTypedLowering() {}
  33
  34
  35 Reduction JSTypedLowering::ReplaceEagerly(Node* old, Node* node) {
  36   NodeProperties::ReplaceWithValue(old, node, node);
  37   return Changed(node);
  38 }
  39
  40
  41 // A helper class to simplify the process of reducing a single binop node with a
  42 // JSOperator. This class manages the rewriting of context, control, and effect
  43 // dependencies during lowering of a binop and contains numerous helper
  44 // functions for matching the types of inputs to an operation.
  45 class JSBinopReduction {
  46  public:
  47   JSBinopReduction(JSTypedLowering* lowering, Node* node)
  48       : lowering_(lowering),
  49         node_(node),
  50         left_type_(NodeProperties::GetBounds(node->InputAt(0)).upper),
  51         right_type_(NodeProperties::GetBounds(node->InputAt(1)).upper) {}
  52
  53   void ConvertInputsToNumber() {
  54     node_->ReplaceInput(0, ConvertToNumber(left()));
  55     node_->ReplaceInput(1, ConvertToNumber(right()));
  56   }
  57
  58   void ConvertInputsToInt32(bool left_signed, bool right_signed) {
  59     node_->ReplaceInput(0, ConvertToI32(left_signed, left()));
  60     node_->ReplaceInput(1, ConvertToI32(right_signed, right()));
  61   }
  62
  63   void ConvertInputsToString() {
  64     node_->ReplaceInput(0, ConvertToString(left()));
  65     node_->ReplaceInput(1, ConvertToString(right()));
  66   }
  67
  68   // Convert inputs for bitwise shift operation (ES5 spec 11.7).
  69   void ConvertInputsForShift(bool left_signed) {
  70     node_->ReplaceInput(0, ConvertToI32(left_signed, left()));
  71     Node* rnum = ConvertToI32(false, right());
  72     node_->ReplaceInput(1, graph()->NewNode(machine()->Word32And(), rnum,
  73                                             jsgraph()->Int32Constant(0x1F)));
  74   }
  75
  76   void SwapInputs() {
  77     Node* l = left();
  78     Node* r = right();
  79     node_->ReplaceInput(0, r);
  80     node_->ReplaceInput(1, l);
  81     std::swap(left_type_, right_type_);
  82   }
  83
  84   // Remove all effect and control inputs and outputs to this node and change
  85   // to the pure operator {op}, possibly inserting a boolean inversion.
  86   Reduction ChangeToPureOperator(const Operator* op, bool invert = false) {
  87     DCHECK_EQ(0, op->EffectInputCount());
  88     DCHECK_EQ(false, OperatorProperties::HasContextInput(op));
  89     DCHECK_EQ(0, op->ControlInputCount());
  90     DCHECK_EQ(2, op->ValueInputCount());
  91
  92     // Remove the effects from the node, if any, and update its effect usages.
  93     if (node_->op()->EffectInputCount() > 0) {
  94       RelaxEffects(node_);
  95     }
  96     // Remove the inputs corresponding to context, effect, and control.
  97     NodeProperties::RemoveNonValueInputs(node_);
  98     // Finally, update the operator to the new one.
  99     node_->set_op(op);
 100
 101     if (invert) {
 102       // Insert an boolean not to invert the value.
 103       Node* value = graph()->NewNode(simplified()->BooleanNot(), node_);
 104       node_->ReplaceUses(value);
 105       // Note: ReplaceUses() smashes all uses, so smash it back here.
 106       value->ReplaceInput(0, node_);
 107       return lowering_->ReplaceWith(value);
 108     }
 109     return lowering_->Changed(node_);
 110   }
 111
 112   bool OneInputIs(Type* t) { return left_type_->Is(t) || right_type_->Is(t); }
 113
 114   bool BothInputsAre(Type* t) {
 115     return left_type_->Is(t) && right_type_->Is(t);
 116   }
 117
 118   bool OneInputCannotBe(Type* t) {
 119     return !left_type_->Maybe(t) || !right_type_->Maybe(t);
 120   }
 121
 122   bool NeitherInputCanBe(Type* t) {
 123     return !left_type_->Maybe(t) && !right_type_->Maybe(t);
 124   }
 125
 126   Node* effect() { return NodeProperties::GetEffectInput(node_); }
 127   Node* control() { return NodeProperties::GetControlInput(node_); }
 128   Node* context() { return NodeProperties::GetContextInput(node_); }
 129   Node* left() { return NodeProperties::GetValueInput(node_, 0); }
 130   Node* right() { return NodeProperties::GetValueInput(node_, 1); }
 131   Type* left_type() { return left_type_; }
 132   Type* right_type() { return right_type_; }
 133
 134   SimplifiedOperatorBuilder* simplified() { return lowering_->simplified(); }
 135   Graph* graph() { return lowering_->graph(); }
 136   JSGraph* jsgraph() { return lowering_->jsgraph(); }
 137   JSOperatorBuilder* javascript() { return lowering_->javascript(); }
 138   MachineOperatorBuilder* machine() { return lowering_->machine(); }
 139
 140  private:
 141   JSTypedLowering* lowering_;  // The containing lowering instance.
 142   Node* node_;                 // The original node.
 143   Type* left_type_;            // Cache of the left input's type.
 144   Type* right_type_;           // Cache of the right input's type.
 145
 146   Node* ConvertToString(Node* node) {
 147     // Avoid introducing too many eager ToString() operations.
 148     Reduction reduced = lowering_->ReduceJSToStringInput(node);
 149     if (reduced.Changed()) return reduced.replacement();
 150     Node* n = graph()->NewNode(javascript()->ToString(), node, context(),
 151                                effect(), control());
 152     update_effect(n);
 153     return n;
 154   }
 155
 156   Node* ConvertToNumber(Node* node) {
 157     // Avoid introducing too many eager ToNumber() operations.
 158     Reduction reduced = lowering_->ReduceJSToNumberInput(node);
 159     if (reduced.Changed()) return reduced.replacement();
 160     Node* n = graph()->NewNode(javascript()->ToNumber(), node, context(),
 161                                effect(), control());
 162     update_effect(n);
 163     return n;
 164   }
 165
 166   // Try narrowing a double or number operation to an Int32 operation.
 167   bool TryNarrowingToI32(Type* type, Node* node) {
 168     switch (node->opcode()) {
 169       case IrOpcode::kFloat64Add:
 170       case IrOpcode::kNumberAdd: {
 171         JSBinopReduction r(lowering_, node);
 172         if (r.BothInputsAre(Type::Integral32())) {
 173           node->set_op(lowering_->machine()->Int32Add());
 174           // TODO(titzer): narrow bounds instead of overwriting.
 175           NodeProperties::SetBounds(node, Bounds(type));
 176           return true;
 177         }
 178       }
 179       case IrOpcode::kFloat64Sub:
 180       case IrOpcode::kNumberSubtract: {
 181         JSBinopReduction r(lowering_, node);
 182         if (r.BothInputsAre(Type::Integral32())) {
 183           node->set_op(lowering_->machine()->Int32Sub());
 184           // TODO(titzer): narrow bounds instead of overwriting.
 185           NodeProperties::SetBounds(node, Bounds(type));
 186           return true;
 187         }
 188       }
 189       default:
 190         return false;
 191     }
 192   }
 193
 194   Node* ConvertToI32(bool is_signed, Node* node) {
 195     Type* type = is_signed ? Type::Signed32() : Type::Unsigned32();
 196     if (node->OwnedBy(node_)) {
 197       // If this node {node_} has the only edge to {node}, then try narrowing
 198       // its operation to an Int32 add or subtract.
 199       if (TryNarrowingToI32(type, node)) return node;
 200     } else {
 201       // Otherwise, {node} has multiple uses. Leave it as is and let the
 202       // further lowering passes deal with it, which use a full backwards
 203       // fixpoint.
 204     }
 205
 206     // Avoid introducing too many eager NumberToXXnt32() operations.
 207     node = ConvertToNumber(node);
 208     Type* input_type = NodeProperties::GetBounds(node).upper;
 209
 210     if (input_type->Is(type)) return node;  // already in the value range.
 211
 212     const Operator* op = is_signed ? simplified()->NumberToInt32()
 213                                    : simplified()->NumberToUint32();
 214     Node* n = graph()->NewNode(op, node);
 215     return n;
 216   }
 217
 218   void update_effect(Node* effect) {
 219     NodeProperties::ReplaceEffectInput(node_, effect);
 220   }
 221 };
 222
 223
 224 Reduction JSTypedLowering::ReduceJSAdd(Node* node) {
 225   JSBinopReduction r(this, node);
 226   if (r.BothInputsAre(Type::Number())) {
 227     // JSAdd(x:number, y:number) => NumberAdd(x, y)
 228     return r.ChangeToPureOperator(simplified()->NumberAdd());
 229   }
 230   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 231   if (r.BothInputsAre(Type::Primitive()) && r.NeitherInputCanBe(maybe_string)) {
 232     // JSAdd(x:-string, y:-string) => NumberAdd(ToNumber(x), ToNumber(y))
 233     r.ConvertInputsToNumber();
 234     return r.ChangeToPureOperator(simplified()->NumberAdd());
 235   }
 236 #if 0
 237   // TODO(turbofan): General ToNumber disabled for now because:
 238   //   a) The inserted ToNumber operation screws up observability of valueOf.
 239   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 240   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 241   if (r.NeitherInputCanBe(maybe_string)) {
 242     ...
 243   }
 244 #endif
 245 #if 0
 246   // TODO(turbofan): Lowering of StringAdd is disabled for now because:
 247   //   a) The inserted ToString operation screws up valueOf vs. toString order.
 248   //   b) Deoptimization at ToString doesn't have corresponding bailout id.
 249   //   c) Our current StringAddStub is actually non-pure and requires context.
 250   if (r.OneInputIs(Type::String())) {
 251     // JSAdd(x:string, y:string) => StringAdd(x, y)
 252     // JSAdd(x:string, y) => StringAdd(x, ToString(y))
 253     // JSAdd(x, y:string) => StringAdd(ToString(x), y)
 254     r.ConvertInputsToString();
 255     return r.ChangeToPureOperator(simplified()->StringAdd());
 256   }
 257 #endif
 258   return NoChange();
 259 }
 260
 261
 262 Reduction JSTypedLowering::ReduceNumberBinop(Node* node,
 263                                              const Operator* numberOp) {
 264   JSBinopReduction r(this, node);
 265   if (r.BothInputsAre(Type::Primitive())) {
 266     r.ConvertInputsToNumber();
 267     return r.ChangeToPureOperator(numberOp);
 268   }
 269 #if 0
 270   // TODO(turbofan): General ToNumber disabled for now because:
 271   //   a) The inserted ToNumber operation screws up observability of valueOf.
 272   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 273   if (r.OneInputIs(Type::Primitive())) {
 274     // If at least one input is a primitive, then insert appropriate conversions
 275     // to number and reduce this operator to the given numeric one.
 276     // TODO(turbofan): make this heuristic configurable for code size.
 277     r.ConvertInputsToNumber();
 278     return r.ChangeToPureOperator(numberOp);
 279   }
 280 #endif
 281   // TODO(turbofan): relax/remove the effects of this operator in other cases.
 282   return NoChange();
 283 }
 284
 285
 286 Reduction JSTypedLowering::ReduceI32Binop(Node* node, bool left_signed,
 287                                           bool right_signed,
 288                                           const Operator* intOp) {
 289   JSBinopReduction r(this, node);
 290   if (r.BothInputsAre(Type::Primitive())) {
 291     // TODO(titzer): some Smi bitwise operations don't really require going
 292     // all the way to int32, which can save tagging/untagging for some
 293     // operations
 294     // on some platforms.
 295     // TODO(turbofan): make this heuristic configurable for code size.
 296     r.ConvertInputsToInt32(left_signed, right_signed);
 297     return r.ChangeToPureOperator(intOp);
 298   }
 299   return NoChange();
 300 }
 301
 302
 303 Reduction JSTypedLowering::ReduceI32Shift(Node* node, bool left_signed,
 304                                           const Operator* shift_op) {
 305   JSBinopReduction r(this, node);
 306   if (r.BothInputsAre(Type::Primitive())) {
 307     r.ConvertInputsForShift(left_signed);
 308     return r.ChangeToPureOperator(shift_op);
 309   }
 310   return NoChange();
 311 }
 312
 313
 314 Reduction JSTypedLowering::ReduceJSComparison(Node* node) {
 315   JSBinopReduction r(this, node);
 316   if (r.BothInputsAre(Type::String())) {
 317     // If both inputs are definitely strings, perform a string comparison.
 318     const Operator* stringOp;
 319     switch (node->opcode()) {
 320       case IrOpcode::kJSLessThan:
 321         stringOp = simplified()->StringLessThan();
 322         break;
 323       case IrOpcode::kJSGreaterThan:
 324         stringOp = simplified()->StringLessThan();
 325         r.SwapInputs();  // a > b => b < a
 326         break;
 327       case IrOpcode::kJSLessThanOrEqual:
 328         stringOp = simplified()->StringLessThanOrEqual();
 329         break;
 330       case IrOpcode::kJSGreaterThanOrEqual:
 331         stringOp = simplified()->StringLessThanOrEqual();
 332         r.SwapInputs();  // a >= b => b <= a
 333         break;
 334       default:
 335         return NoChange();
 336     }
 337     return r.ChangeToPureOperator(stringOp);
 338   }
 339 #if 0
 340   // TODO(turbofan): General ToNumber disabled for now because:
 341   //   a) The inserted ToNumber operation screws up observability of valueOf.
 342   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 343   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 344   if (r.OneInputCannotBe(maybe_string)) {
 345     // If one input cannot be a string, then emit a number comparison.
 346     ...
 347   }
 348 #endif
 349   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 350   if (r.BothInputsAre(Type::Primitive()) && r.OneInputCannotBe(maybe_string)) {
 351     const Operator* less_than;
 352     const Operator* less_than_or_equal;
 353     if (r.BothInputsAre(Type::Unsigned32())) {
 354       less_than = machine()->Uint32LessThan();
 355       less_than_or_equal = machine()->Uint32LessThanOrEqual();
 356     } else if (r.BothInputsAre(Type::Signed32())) {
 357       less_than = machine()->Int32LessThan();
 358       less_than_or_equal = machine()->Int32LessThanOrEqual();
 359     } else {
 360       // TODO(turbofan): mixed signed/unsigned int32 comparisons.
 361       r.ConvertInputsToNumber();
 362       less_than = simplified()->NumberLessThan();
 363       less_than_or_equal = simplified()->NumberLessThanOrEqual();
 364     }
 365     const Operator* comparison;
 366     switch (node->opcode()) {
 367       case IrOpcode::kJSLessThan:
 368         comparison = less_than;
 369         break;
 370       case IrOpcode::kJSGreaterThan:
 371         comparison = less_than;
 372         r.SwapInputs();  // a > b => b < a
 373         break;
 374       case IrOpcode::kJSLessThanOrEqual:
 375         comparison = less_than_or_equal;
 376         break;
 377       case IrOpcode::kJSGreaterThanOrEqual:
 378         comparison = less_than_or_equal;
 379         r.SwapInputs();  // a >= b => b <= a
 380         break;
 381       default:
 382         return NoChange();
 383     }
 384     return r.ChangeToPureOperator(comparison);
 385   }
 386   // TODO(turbofan): relax/remove effects of this operator in other cases.
 387   return NoChange();  // Keep a generic comparison.
 388 }
 389
 390
 391 Reduction JSTypedLowering::ReduceJSEqual(Node* node, bool invert) {
 392   JSBinopReduction r(this, node);
 393
 394   if (r.BothInputsAre(Type::Number())) {
 395     return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
 396   }
 397   if (r.BothInputsAre(Type::String())) {
 398     return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
 399   }
 400   if (r.BothInputsAre(Type::Receiver())) {
 401     return r.ChangeToPureOperator(
 402         simplified()->ReferenceEqual(Type::Receiver()), invert);
 403   }
 404   // TODO(turbofan): js-typed-lowering of Equal(undefined)
 405   // TODO(turbofan): js-typed-lowering of Equal(null)
 406   // TODO(turbofan): js-typed-lowering of Equal(boolean)
 407   return NoChange();
 408 }
 409
 410
 411 Reduction JSTypedLowering::ReduceJSStrictEqual(Node* node, bool invert) {
 412   JSBinopReduction r(this, node);
 413   if (r.left() == r.right()) {
 414     // x === x is always true if x != NaN
 415     if (!r.left_type()->Maybe(Type::NaN())) {
 416       return ReplaceEagerly(node, invert ? jsgraph()->FalseConstant()
 417                                          : jsgraph()->TrueConstant());
 418     }
 419   }
 420   if (r.OneInputIs(Type::Undefined())) {
 421     return r.ChangeToPureOperator(
 422         simplified()->ReferenceEqual(Type::Undefined()), invert);
 423   }
 424   if (r.OneInputIs(Type::Null())) {
 425     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Null()),
 426                                   invert);
 427   }
 428   if (r.OneInputIs(Type::Boolean())) {
 429     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Boolean()),
 430                                   invert);
 431   }
 432   if (r.OneInputIs(Type::Object())) {
 433     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Object()),
 434                                   invert);
 435   }
 436   if (r.OneInputIs(Type::Receiver())) {
 437     return r.ChangeToPureOperator(
 438         simplified()->ReferenceEqual(Type::Receiver()), invert);
 439   }
 440   if (r.BothInputsAre(Type::String())) {
 441     return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
 442   }
 443   if (r.BothInputsAre(Type::Number())) {
 444     return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
 445   }
 446   // TODO(turbofan): js-typed-lowering of StrictEqual(mixed types)
 447   return NoChange();
 448 }
 449
 450
 451 Reduction JSTypedLowering::ReduceJSToNumberInput(Node* input) {
 452   if (input->opcode() == IrOpcode::kJSToNumber) {
 453     // Recursively try to reduce the input first.
 454     Reduction result = ReduceJSToNumberInput(input->InputAt(0));
 455     if (result.Changed()) {
 456       RelaxEffects(input);
 457       return result;
 458     }
 459     return Changed(input);  // JSToNumber(JSToNumber(x)) => JSToNumber(x)
 460   }
 461   Type* input_type = NodeProperties::GetBounds(input).upper;
 462   if (input_type->Is(Type::Number())) {
 463     // JSToNumber(x:number) => x
 464     return Changed(input);
 465   }
 466   if (input_type->Is(Type::Undefined())) {
 467     // JSToNumber(undefined) => #NaN
 468     return ReplaceWith(jsgraph()->NaNConstant());
 469   }
 470   if (input_type->Is(Type::Null())) {
 471     // JSToNumber(null) => #0
 472     return ReplaceWith(jsgraph()->ZeroConstant());
 473   }
 474   if (input_type->Is(Type::Boolean())) {
 475     // JSToNumber(x:boolean) => BooleanToNumber(x)
 476     return ReplaceWith(
 477         graph()->NewNode(simplified()->BooleanToNumber(), input));
 478   }
 479   // TODO(turbofan): js-typed-lowering of ToNumber(x:string)
 480   return NoChange();
 481 }
 482
 483
 484 Reduction JSTypedLowering::ReduceJSToStringInput(Node* input) {
 485   if (input->opcode() == IrOpcode::kJSToString) {
 486     // Recursively try to reduce the input first.
 487     Reduction result = ReduceJSToStringInput(input->InputAt(0));
 488     if (result.Changed()) {
 489       RelaxEffects(input);
 490       return result;
 491     }
 492     return Changed(input);  // JSToString(JSToString(x)) => JSToString(x)
 493   }
 494   Type* input_type = NodeProperties::GetBounds(input).upper;
 495   if (input_type->Is(Type::String())) {
 496     return Changed(input);  // JSToString(x:string) => x
 497   }
 498   if (input_type->Is(Type::Undefined())) {
 499     return ReplaceWith(jsgraph()->HeapConstant(
 500         graph()->zone()->isolate()->factory()->undefined_string()));
 501   }
 502   if (input_type->Is(Type::Null())) {
 503     return ReplaceWith(jsgraph()->HeapConstant(
 504         graph()->zone()->isolate()->factory()->null_string()));
 505   }
 506   // TODO(turbofan): js-typed-lowering of ToString(x:boolean)
 507   // TODO(turbofan): js-typed-lowering of ToString(x:number)
 508   return NoChange();
 509 }
 510
 511
 512 Reduction JSTypedLowering::ReduceJSToBooleanInput(Node* input) {
 513   if (input->opcode() == IrOpcode::kJSToBoolean) {
 514     // Recursively try to reduce the input first.
 515     Reduction result = ReduceJSToBooleanInput(input->InputAt(0));
 516     if (result.Changed()) {
 517       RelaxEffects(input);
 518       return result;
 519     }
 520     return Changed(input);  // JSToBoolean(JSToBoolean(x)) => JSToBoolean(x)
 521   }
 522   Type* input_type = NodeProperties::GetBounds(input).upper;
 523   if (input_type->Is(Type::Boolean())) {
 524     return Changed(input);  // JSToBoolean(x:boolean) => x
 525   }
 526   if (input_type->Is(Type::Undefined())) {
 527     // JSToBoolean(undefined) => #false
 528     return ReplaceWith(jsgraph()->FalseConstant());
 529   }
 530   if (input_type->Is(Type::Null())) {
 531     // JSToBoolean(null) => #false
 532     return ReplaceWith(jsgraph()->FalseConstant());
 533   }
 534   if (input_type->Is(Type::DetectableReceiver())) {
 535     // JSToBoolean(x:detectable) => #true
 536     return ReplaceWith(jsgraph()->TrueConstant());
 537   }
 538   if (input_type->Is(Type::Undetectable())) {
 539     // JSToBoolean(x:undetectable) => #false
 540     return ReplaceWith(jsgraph()->FalseConstant());
 541   }
 542   if (input_type->Is(Type::OrderedNumber())) {
 543     // JSToBoolean(x:ordered-number) => BooleanNot(NumberEqual(x, #0))
 544     Node* cmp = graph()->NewNode(simplified()->NumberEqual(), input,
 545                                  jsgraph()->ZeroConstant());
 546     Node* inv = graph()->NewNode(simplified()->BooleanNot(), cmp);
 547     return ReplaceWith(inv);
 548   }
 549   if (input_type->Is(Type::String())) {
 550     // JSToBoolean(x:string) => BooleanNot(NumberEqual(x.length, #0))
 551     FieldAccess access = AccessBuilder::ForStringLength();
 552     Node* length = graph()->NewNode(simplified()->LoadField(access), input,
 553                                     graph()->start(), graph()->start());
 554     Node* cmp = graph()->NewNode(simplified()->NumberEqual(), length,
 555                                  jsgraph()->ZeroConstant());
 556     Node* inv = graph()->NewNode(simplified()->BooleanNot(), cmp);
 557     return ReplaceWith(inv);
 558   }
 559   // TODO(turbofan): We need some kinda of PrimitiveToBoolean simplified
 560   // operator, then we can do the pushing in the SimplifiedOperatorReducer
 561   // and do not need to protect against stack overflow (because of backedges
 562   // in phis) below.
 563   if (input->opcode() == IrOpcode::kPhi &&
 564       input_type->Is(
 565           Type::Union(Type::Boolean(), Type::OrderedNumber(), zone()))) {
 566     // JSToBoolean(phi(x1,...,xn):ordered-number|boolean)
 567     //   => phi(JSToBoolean(x1),...,JSToBoolean(xn))
 568     int input_count = input->InputCount() - 1;
 569     Node** inputs = zone()->NewArray<Node*>(input_count + 1);
 570     for (int i = 0; i < input_count; ++i) {
 571       Node* value = input->InputAt(i);
 572       Type* value_type = NodeProperties::GetBounds(value).upper;
 573       // Recursively try to reduce the value first.
 574       Reduction result = (value_type->Is(Type::Boolean()) ||
 575                           value_type->Is(Type::OrderedNumber()))
 576                              ? ReduceJSToBooleanInput(value)
 577                              : NoChange();
 578       if (result.Changed()) {
 579         inputs[i] = result.replacement();
 580       } else {
 581         inputs[i] = graph()->NewNode(javascript()->ToBoolean(), value,
 582                                      jsgraph()->ZeroConstant(),
 583                                      graph()->start(), graph()->start());
 584       }
 585     }
 586     inputs[input_count] = input->InputAt(input_count);
 587     Node* phi = graph()->NewNode(common()->Phi(kMachAnyTagged, input_count),
 588                                  input_count + 1, inputs);
 589     return ReplaceWith(phi);
 590   }
 591   return NoChange();
 592 }
 593
 594
 595 Reduction JSTypedLowering::ReduceJSLoadProperty(Node* node) {
 596   Node* key = NodeProperties::GetValueInput(node, 1);
 597   Node* base = NodeProperties::GetValueInput(node, 0);
 598   Type* key_type = NodeProperties::GetBounds(key).upper;
 599   Type* base_type = NodeProperties::GetBounds(base).upper;
 600   // TODO(mstarzinger): This lowering is not correct if:
 601   //   a) The typed array or it's buffer is neutered.
 602   if (base_type->IsConstant() && key_type->Is(Type::Integral32()) &&
 603       base_type->AsConstant()->Value()->IsJSTypedArray()) {
 604     // JSLoadProperty(typed-array, int32)
 605     Handle<JSTypedArray> array =
 606         Handle<JSTypedArray>::cast(base_type->AsConstant()->Value());
 607     if (IsExternalArrayElementsKind(array->map()->elements_kind())) {
 608       ExternalArrayType type = array->type();
 609       double byte_length = array->byte_length()->Number();
 610       if (byte_length <= kMaxInt) {
 611         Handle<ExternalArray> elements =
 612             Handle<ExternalArray>::cast(handle(array->elements()));
 613         Node* pointer = jsgraph()->IntPtrConstant(
 614             bit_cast<intptr_t>(elements->external_pointer()));
 615         Node* length = jsgraph()->Constant(array->length()->Number());
 616         Node* effect = NodeProperties::GetEffectInput(node);
 617         Node* load = graph()->NewNode(
 618             simplified()->LoadElement(
 619                 AccessBuilder::ForTypedArrayElement(type, true)),
 620             pointer, key, length, effect);
 621         return ReplaceEagerly(node, load);
 622       }
 623     }
 624   }
 625   return NoChange();
 626 }
 627
 628
 629 Reduction JSTypedLowering::ReduceJSStoreProperty(Node* node) {
 630   Node* key = NodeProperties::GetValueInput(node, 1);
 631   Node* base = NodeProperties::GetValueInput(node, 0);
 632   Node* value = NodeProperties::GetValueInput(node, 2);
 633   Type* key_type = NodeProperties::GetBounds(key).upper;
 634   Type* base_type = NodeProperties::GetBounds(base).upper;
 635   // TODO(mstarzinger): This lowering is not correct if:
 636   //   a) The typed array or its buffer is neutered.
 637   if (key_type->Is(Type::Integral32()) && base_type->IsConstant() &&
 638       base_type->AsConstant()->Value()->IsJSTypedArray()) {
 639     // JSStoreProperty(typed-array, int32, value)
 640     Handle<JSTypedArray> array =
 641         Handle<JSTypedArray>::cast(base_type->AsConstant()->Value());
 642     if (IsExternalArrayElementsKind(array->map()->elements_kind())) {
 643       ExternalArrayType type = array->type();
 644       double byte_length = array->byte_length()->Number();
 645       if (byte_length <= kMaxInt) {
 646         Handle<ExternalArray> elements =
 647             Handle<ExternalArray>::cast(handle(array->elements()));
 648         Node* pointer = jsgraph()->IntPtrConstant(
 649             bit_cast<intptr_t>(elements->external_pointer()));
 650         Node* length = jsgraph()->Constant(array->length()->Number());
 651         Node* effect = NodeProperties::GetEffectInput(node);
 652         Node* control = NodeProperties::GetControlInput(node);
 653         Node* store = graph()->NewNode(
 654             simplified()->StoreElement(
 655                 AccessBuilder::ForTypedArrayElement(type, true)),
 656             pointer, key, length, value, effect, control);
 657         return ReplaceEagerly(node, store);
 658       }
 659     }
 660   }
 661   return NoChange();
 662 }
 663
 664
 665 static Reduction ReplaceWithReduction(Node* node, Reduction reduction) {
 666   if (reduction.Changed()) {
 667     NodeProperties::ReplaceWithValue(node, reduction.replacement());
 668     return reduction;
 669   }
 670   return Reducer::NoChange();
 671 }
 672
 673
 674 Reduction JSTypedLowering::Reduce(Node* node) {
 675   // Check if the output type is a singleton.  In that case we already know the
 676   // result value and can simply replace the node unless there are effects.
 677   if (NodeProperties::IsTyped(node) &&
 678       NodeProperties::GetBounds(node).upper->IsConstant() &&
 679       !IrOpcode::IsLeafOpcode(node->opcode()) &&
 680       node->op()->EffectOutputCount() == 0) {
 681     return ReplaceEagerly(node, jsgraph()->Constant(
 682         NodeProperties::GetBounds(node).upper->AsConstant()->Value()));
 683     // TODO(neis): Extend this to Range(x,x), NaN, MinusZero, ...?
 684   }
 685   switch (node->opcode()) {
 686     case IrOpcode::kJSEqual:
 687       return ReduceJSEqual(node, false);
 688     case IrOpcode::kJSNotEqual:
 689       return ReduceJSEqual(node, true);
 690     case IrOpcode::kJSStrictEqual:
 691       return ReduceJSStrictEqual(node, false);
 692     case IrOpcode::kJSStrictNotEqual:
 693       return ReduceJSStrictEqual(node, true);
 694     case IrOpcode::kJSLessThan:         // fall through
 695     case IrOpcode::kJSGreaterThan:      // fall through
 696     case IrOpcode::kJSLessThanOrEqual:  // fall through
 697     case IrOpcode::kJSGreaterThanOrEqual:
 698       return ReduceJSComparison(node);
 699     case IrOpcode::kJSBitwiseOr:
 700       return ReduceI32Binop(node, true, true, machine()->Word32Or());
 701     case IrOpcode::kJSBitwiseXor:
 702       return ReduceI32Binop(node, true, true, machine()->Word32Xor());
 703     case IrOpcode::kJSBitwiseAnd:
 704       return ReduceI32Binop(node, true, true, machine()->Word32And());
 705     case IrOpcode::kJSShiftLeft:
 706       return ReduceI32Shift(node, true, machine()->Word32Shl());
 707     case IrOpcode::kJSShiftRight:
 708       return ReduceI32Shift(node, true, machine()->Word32Sar());
 709     case IrOpcode::kJSShiftRightLogical:
 710       return ReduceI32Shift(node, false, machine()->Word32Shr());
 711     case IrOpcode::kJSAdd:
 712       return ReduceJSAdd(node);
 713     case IrOpcode::kJSSubtract:
 714       return ReduceNumberBinop(node, simplified()->NumberSubtract());
 715     case IrOpcode::kJSMultiply:
 716       return ReduceNumberBinop(node, simplified()->NumberMultiply());
 717     case IrOpcode::kJSDivide:
 718       return ReduceNumberBinop(node, simplified()->NumberDivide());
 719     case IrOpcode::kJSModulus:
 720       return ReduceNumberBinop(node, simplified()->NumberModulus());
 721     case IrOpcode::kJSUnaryNot: {
 722       Reduction result = ReduceJSToBooleanInput(node->InputAt(0));
 723       Node* value;
 724       if (result.Changed()) {
 725         // JSUnaryNot(x:boolean) => BooleanNot(x)
 726         value =
 727             graph()->NewNode(simplified()->BooleanNot(), result.replacement());
 728         NodeProperties::ReplaceWithValue(node, value);
 729         return Changed(value);
 730       } else {
 731         // JSUnaryNot(x) => BooleanNot(JSToBoolean(x))
 732         value = graph()->NewNode(simplified()->BooleanNot(), node);
 733         node->set_op(javascript()->ToBoolean());
 734         NodeProperties::ReplaceWithValue(node, value, node);
 735         // Note: ReplaceUses() smashes all uses, so smash it back here.
 736         value->ReplaceInput(0, node);
 737         return Changed(node);
 738       }
 739     }
 740     case IrOpcode::kJSToBoolean:
 741       return ReplaceWithReduction(node,
 742                                   ReduceJSToBooleanInput(node->InputAt(0)));
 743     case IrOpcode::kJSToNumber:
 744       return ReplaceWithReduction(node,
 745                                   ReduceJSToNumberInput(node->InputAt(0)));
 746     case IrOpcode::kJSToString:
 747       return ReplaceWithReduction(node,
 748                                   ReduceJSToStringInput(node->InputAt(0)));
 749     case IrOpcode::kJSLoadProperty:
 750       return ReduceJSLoadProperty(node);
 751     case IrOpcode::kJSStoreProperty:
 752       return ReduceJSStoreProperty(node);
 753     case IrOpcode::kJSCallFunction:
 754       return JSBuiltinReducer(jsgraph()).Reduce(node);
 755     default:
 756       break;
 757   }
 758   return NoChange();
 759 }
 760
 761 }  // namespace compiler
 762 }  // namespace internal
 763 }  // namespace v8