deps/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/js-graph.h"
   7 #include "src/compiler/js-typed-lowering.h"
   8 #include "src/compiler/node-matchers.h"
   9 #include "src/compiler/node-properties.h"
  10 #include "src/compiler/operator-properties.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
  21
  22 // Relax the effects of {node} by immediately replacing effect uses of {node}
  23 // with the effect input to {node}.
  24 // TODO(turbofan): replace the effect input to {node} with {graph->start()}.
  25 // TODO(titzer): move into a GraphEditor?
  26 static void RelaxEffects(Node* node) {
  27   NodeProperties::ReplaceWithValue(node, node, NULL);
  28 }
  29
  30
  31 JSTypedLowering::JSTypedLowering(JSGraph* jsgraph, Zone* zone)
  32     : jsgraph_(jsgraph), simplified_(graph()->zone()), conversions_(zone) {
  33   zero_range_ = Type::Range(0.0, 1.0, graph()->zone());
  34   one_range_ = Type::Range(1.0, 1.0, graph()->zone());
  35   zero_thirtyone_range_ = Type::Range(0.0, 31.0, graph()->zone());
  36   // TODO(jarin): Can we have a correctification of the stupid type system?
  37   // These stupid work-arounds are just stupid!
  38   shifted_int32_ranges_[0] = Type::Signed32();
  39   if (SmiValuesAre31Bits()) {
  40     shifted_int32_ranges_[1] = Type::SignedSmall();
  41     for (size_t k = 2; k < arraysize(shifted_int32_ranges_); ++k) {
  42       double min = kMinInt / (1 << k);
  43       double max = kMaxInt / (1 << k);
  44       shifted_int32_ranges_[k] = Type::Range(min, max, graph()->zone());
  45     }
  46   } else {
  47     for (size_t k = 1; k < arraysize(shifted_int32_ranges_); ++k) {
  48       double min = kMinInt / (1 << k);
  49       double max = kMaxInt / (1 << k);
  50       shifted_int32_ranges_[k] = Type::Range(min, max, graph()->zone());
  51     }
  52   }
  53 }
  54
  55
  56 Reduction JSTypedLowering::ReplaceEagerly(Node* old, Node* node) {
  57   NodeProperties::ReplaceWithValue(old, node, node);
  58   return Changed(node);
  59 }
  60
  61
  62 // A helper class to simplify the process of reducing a single binop node with a
  63 // JSOperator. This class manages the rewriting of context, control, and effect
  64 // dependencies during lowering of a binop and contains numerous helper
  65 // functions for matching the types of inputs to an operation.
  66 class JSBinopReduction FINAL {
  67  public:
  68   JSBinopReduction(JSTypedLowering* lowering, Node* node)
  69       : lowering_(lowering),
  70         node_(node),
  71         left_type_(NodeProperties::GetBounds(node->InputAt(0)).upper),
  72         right_type_(NodeProperties::GetBounds(node->InputAt(1)).upper) {}
  73
  74   void ConvertInputsToNumber() {
  75     node_->ReplaceInput(0, ConvertToNumber(left()));
  76     node_->ReplaceInput(1, ConvertToNumber(right()));
  77   }
  78
  79   void ConvertInputsToUI32(Signedness left_signedness,
  80                            Signedness right_signedness) {
  81     node_->ReplaceInput(0, ConvertToUI32(left(), left_signedness));
  82     node_->ReplaceInput(1, ConvertToUI32(right(), right_signedness));
  83   }
  84
  85   void ConvertInputsToString() {
  86     node_->ReplaceInput(0, ConvertToString(left()));
  87     node_->ReplaceInput(1, ConvertToString(right()));
  88   }
  89
  90   // Convert inputs for bitwise shift operation (ES5 spec 11.7).
  91   void ConvertInputsForShift(Signedness left_signedness) {
  92     node_->ReplaceInput(0, ConvertToUI32(left(), left_signedness));
  93     Node* rnum = ConvertToUI32(right(), kUnsigned);
  94     Type* rnum_type = NodeProperties::GetBounds(rnum).upper;
  95     if (!rnum_type->Is(lowering_->zero_thirtyone_range_)) {
  96       rnum = graph()->NewNode(machine()->Word32And(), rnum,
  97                               jsgraph()->Int32Constant(0x1F));
  98     }
  99     node_->ReplaceInput(1, rnum);
 100   }
 101
 102   void SwapInputs() {
 103     Node* l = left();
 104     Node* r = right();
 105     node_->ReplaceInput(0, r);
 106     node_->ReplaceInput(1, l);
 107     std::swap(left_type_, right_type_);
 108   }
 109
 110   // Remove all effect and control inputs and outputs to this node and change
 111   // to the pure operator {op}, possibly inserting a boolean inversion.
 112   Reduction ChangeToPureOperator(const Operator* op, bool invert = false,
 113                                  Type* type = Type::Any()) {
 114     DCHECK_EQ(0, op->EffectInputCount());
 115     DCHECK_EQ(false, OperatorProperties::HasContextInput(op));
 116     DCHECK_EQ(0, op->ControlInputCount());
 117     DCHECK_EQ(2, op->ValueInputCount());
 118
 119     // Remove the effects from the node, if any, and update its effect usages.
 120     if (node_->op()->EffectInputCount() > 0) {
 121       RelaxEffects(node_);
 122     }
 123     // Remove the inputs corresponding to context, effect, and control.
 124     NodeProperties::RemoveNonValueInputs(node_);
 125     // Finally, update the operator to the new one.
 126     node_->set_op(op);
 127
 128     // TODO(jarin): Replace the explicit typing hack with a call to some method
 129     // that encapsulates changing the operator and re-typing.
 130     Bounds const bounds = NodeProperties::GetBounds(node_);
 131     NodeProperties::SetBounds(node_, Bounds::NarrowUpper(bounds, type, zone()));
 132
 133     if (invert) {
 134       // Insert an boolean not to invert the value.
 135       Node* value = graph()->NewNode(simplified()->BooleanNot(), node_);
 136       node_->ReplaceUses(value);
 137       // Note: ReplaceUses() smashes all uses, so smash it back here.
 138       value->ReplaceInput(0, node_);
 139       return lowering_->Replace(value);
 140     }
 141     return lowering_->Changed(node_);
 142   }
 143
 144   Reduction ChangeToPureOperator(const Operator* op, Type* type) {
 145     return ChangeToPureOperator(op, false, type);
 146   }
 147
 148   bool OneInputIs(Type* t) { return left_type_->Is(t) || right_type_->Is(t); }
 149
 150   bool BothInputsAre(Type* t) {
 151     return left_type_->Is(t) && right_type_->Is(t);
 152   }
 153
 154   bool OneInputCannotBe(Type* t) {
 155     return !left_type_->Maybe(t) || !right_type_->Maybe(t);
 156   }
 157
 158   bool NeitherInputCanBe(Type* t) {
 159     return !left_type_->Maybe(t) && !right_type_->Maybe(t);
 160   }
 161
 162   Node* effect() { return NodeProperties::GetEffectInput(node_); }
 163   Node* control() { return NodeProperties::GetControlInput(node_); }
 164   Node* context() { return NodeProperties::GetContextInput(node_); }
 165   Node* left() { return NodeProperties::GetValueInput(node_, 0); }
 166   Node* right() { return NodeProperties::GetValueInput(node_, 1); }
 167   Type* left_type() { return left_type_; }
 168   Type* right_type() { return right_type_; }
 169
 170   SimplifiedOperatorBuilder* simplified() { return lowering_->simplified(); }
 171   Graph* graph() const { return lowering_->graph(); }
 172   JSGraph* jsgraph() { return lowering_->jsgraph(); }
 173   JSOperatorBuilder* javascript() { return lowering_->javascript(); }
 174   MachineOperatorBuilder* machine() { return lowering_->machine(); }
 175   Zone* zone() const { return graph()->zone(); }
 176
 177  private:
 178   JSTypedLowering* lowering_;  // The containing lowering instance.
 179   Node* node_;                 // The original node.
 180   Type* left_type_;            // Cache of the left input's type.
 181   Type* right_type_;           // Cache of the right input's type.
 182
 183   Node* ConvertToString(Node* node) {
 184     // Avoid introducing too many eager ToString() operations.
 185     Reduction reduced = lowering_->ReduceJSToStringInput(node);
 186     if (reduced.Changed()) return reduced.replacement();
 187     Node* n = graph()->NewNode(javascript()->ToString(), node, context(),
 188                                effect(), control());
 189     update_effect(n);
 190     return n;
 191   }
 192
 193   Node* ConvertToNumber(Node* node) {
 194     if (NodeProperties::GetBounds(node).upper->Is(Type::PlainPrimitive())) {
 195       return lowering_->ConvertToNumber(node);
 196     }
 197     // TODO(jarin) This ToNumber conversion can deoptimize, but we do not really
 198     // have a frame state to deoptimize to. Either we provide such a frame state
 199     // or we exclude the values that could lead to deoptimization (e.g., by
 200     // triggering eager deopt if the value is not plain).
 201     Node* const n = FLAG_turbo_deoptimization
 202                         ? graph()->NewNode(
 203                               javascript()->ToNumber(), node, context(),
 204                               jsgraph()->EmptyFrameState(), effect(), control())
 205                         : graph()->NewNode(javascript()->ToNumber(), node,
 206                                            context(), effect(), control());
 207     update_effect(n);
 208     return n;
 209   }
 210
 211   Node* ConvertToUI32(Node* node, Signedness signedness) {
 212     // Avoid introducing too many eager NumberToXXnt32() operations.
 213     node = ConvertToNumber(node);
 214     Type* type = NodeProperties::GetBounds(node).upper;
 215     if (signedness == kSigned) {
 216       if (!type->Is(Type::Signed32())) {
 217         node = graph()->NewNode(simplified()->NumberToInt32(), node);
 218       }
 219     } else {
 220       DCHECK_EQ(kUnsigned, signedness);
 221       if (!type->Is(Type::Unsigned32())) {
 222         node = graph()->NewNode(simplified()->NumberToUint32(), node);
 223       }
 224     }
 225     return node;
 226   }
 227
 228   void update_effect(Node* effect) {
 229     NodeProperties::ReplaceEffectInput(node_, effect);
 230   }
 231 };
 232
 233
 234 Reduction JSTypedLowering::ReduceJSAdd(Node* node) {
 235   JSBinopReduction r(this, node);
 236   if (r.BothInputsAre(Type::Number())) {
 237     // JSAdd(x:number, y:number) => NumberAdd(x, y)
 238     return r.ChangeToPureOperator(simplified()->NumberAdd(), Type::Number());
 239   }
 240   if (r.BothInputsAre(Type::Primitive()) &&
 241       r.NeitherInputCanBe(Type::StringOrReceiver())) {
 242     // JSAdd(x:-string, y:-string) => NumberAdd(ToNumber(x), ToNumber(y))
 243     r.ConvertInputsToNumber();
 244     return r.ChangeToPureOperator(simplified()->NumberAdd(), Type::Number());
 245   }
 246 #if 0
 247   // TODO(turbofan): General ToNumber disabled for now because:
 248   //   a) The inserted ToNumber operation screws up observability of valueOf.
 249   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 250   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 251   if (r.NeitherInputCanBe(maybe_string)) {
 252     ...
 253   }
 254 #endif
 255 #if 0
 256   // TODO(turbofan): Lowering of StringAdd is disabled for now because:
 257   //   a) The inserted ToString operation screws up valueOf vs. toString order.
 258   //   b) Deoptimization at ToString doesn't have corresponding bailout id.
 259   //   c) Our current StringAddStub is actually non-pure and requires context.
 260   if (r.OneInputIs(Type::String())) {
 261     // JSAdd(x:string, y:string) => StringAdd(x, y)
 262     // JSAdd(x:string, y) => StringAdd(x, ToString(y))
 263     // JSAdd(x, y:string) => StringAdd(ToString(x), y)
 264     r.ConvertInputsToString();
 265     return r.ChangeToPureOperator(simplified()->StringAdd());
 266   }
 267 #endif
 268   return NoChange();
 269 }
 270
 271
 272 Reduction JSTypedLowering::ReduceJSBitwiseOr(Node* node) {
 273   JSBinopReduction r(this, node);
 274
 275   // We can only reduce to Word32Or if we are sure the to-number conversions
 276   // cannot lazily deoptimize.
 277   bool shortcut_or_zero =
 278       !FLAG_turbo_deoptimization && r.OneInputIs(zero_range_);
 279   if (r.BothInputsAre(Type::Primitive()) || shortcut_or_zero) {
 280     // TODO(titzer): some Smi bitwise operations don't really require going
 281     // all the way to int32, which can save tagging/untagging for some
 282     // operations on some platforms.
 283     // TODO(turbofan): make this heuristic configurable for code size.
 284     r.ConvertInputsToUI32(kSigned, kSigned);
 285     return r.ChangeToPureOperator(machine()->Word32Or(), Type::Integral32());
 286   }
 287   return NoChange();
 288 }
 289
 290
 291 Reduction JSTypedLowering::ReduceJSMultiply(Node* node) {
 292   JSBinopReduction r(this, node);
 293
 294   // We can only reduce to NumberMultiply if we are sure the to-number
 295   // conversions cannot lazily deoptimize.
 296   bool shortcut_multiply_one =
 297       !FLAG_turbo_deoptimization && r.OneInputIs(one_range_);
 298
 299   if (r.BothInputsAre(Type::Primitive()) || shortcut_multiply_one) {
 300     r.ConvertInputsToNumber();
 301     return r.ChangeToPureOperator(simplified()->NumberMultiply(),
 302                                   Type::Number());
 303   }
 304   // TODO(turbofan): relax/remove the effects of this operator in other cases.
 305   return NoChange();
 306 }
 307
 308
 309 Reduction JSTypedLowering::ReduceNumberBinop(Node* node,
 310                                              const Operator* numberOp) {
 311   JSBinopReduction r(this, node);
 312   if (r.BothInputsAre(Type::Primitive())) {
 313     r.ConvertInputsToNumber();
 314     return r.ChangeToPureOperator(numberOp, Type::Number());
 315   }
 316 #if 0
 317   // TODO(turbofan): General ToNumber disabled for now because:
 318   //   a) The inserted ToNumber operation screws up observability of valueOf.
 319   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 320   if (r.OneInputIs(Type::Primitive())) {
 321     // If at least one input is a primitive, then insert appropriate conversions
 322     // to number and reduce this operator to the given numeric one.
 323     // TODO(turbofan): make this heuristic configurable for code size.
 324     r.ConvertInputsToNumber();
 325     return r.ChangeToPureOperator(numberOp);
 326   }
 327 #endif
 328   // TODO(turbofan): relax/remove the effects of this operator in other cases.
 329   return NoChange();
 330 }
 331
 332
 333 Reduction JSTypedLowering::ReduceInt32Binop(Node* node, const Operator* intOp) {
 334   JSBinopReduction r(this, node);
 335   if (r.BothInputsAre(Type::Primitive())) {
 336     // TODO(titzer): some Smi bitwise operations don't really require going
 337     // all the way to int32, which can save tagging/untagging for some
 338     // operations
 339     // on some platforms.
 340     // TODO(turbofan): make this heuristic configurable for code size.
 341     r.ConvertInputsToUI32(kSigned, kSigned);
 342     return r.ChangeToPureOperator(intOp, Type::Integral32());
 343   }
 344   return NoChange();
 345 }
 346
 347
 348 Reduction JSTypedLowering::ReduceUI32Shift(Node* node,
 349                                            Signedness left_signedness,
 350                                            const Operator* shift_op) {
 351   JSBinopReduction r(this, node);
 352   if (r.BothInputsAre(Type::Primitive())) {
 353     r.ConvertInputsForShift(left_signedness);
 354     return r.ChangeToPureOperator(shift_op, Type::Integral32());
 355   }
 356   return NoChange();
 357 }
 358
 359
 360 Reduction JSTypedLowering::ReduceJSComparison(Node* node) {
 361   JSBinopReduction r(this, node);
 362   if (r.BothInputsAre(Type::String())) {
 363     // If both inputs are definitely strings, perform a string comparison.
 364     const Operator* stringOp;
 365     switch (node->opcode()) {
 366       case IrOpcode::kJSLessThan:
 367         stringOp = simplified()->StringLessThan();
 368         break;
 369       case IrOpcode::kJSGreaterThan:
 370         stringOp = simplified()->StringLessThan();
 371         r.SwapInputs();  // a > b => b < a
 372         break;
 373       case IrOpcode::kJSLessThanOrEqual:
 374         stringOp = simplified()->StringLessThanOrEqual();
 375         break;
 376       case IrOpcode::kJSGreaterThanOrEqual:
 377         stringOp = simplified()->StringLessThanOrEqual();
 378         r.SwapInputs();  // a >= b => b <= a
 379         break;
 380       default:
 381         return NoChange();
 382     }
 383     return r.ChangeToPureOperator(stringOp);
 384   }
 385 #if 0
 386   // TODO(turbofan): General ToNumber disabled for now because:
 387   //   a) The inserted ToNumber operation screws up observability of valueOf.
 388   //   b) Deoptimization at ToNumber doesn't have corresponding bailout id.
 389   Type* maybe_string = Type::Union(Type::String(), Type::Receiver(), zone());
 390   if (r.OneInputCannotBe(maybe_string)) {
 391     // If one input cannot be a string, then emit a number comparison.
 392     ...
 393   }
 394 #endif
 395   if (r.BothInputsAre(Type::Primitive()) &&
 396       r.OneInputCannotBe(Type::StringOrReceiver())) {
 397     const Operator* less_than;
 398     const Operator* less_than_or_equal;
 399     if (r.BothInputsAre(Type::Unsigned32())) {
 400       less_than = machine()->Uint32LessThan();
 401       less_than_or_equal = machine()->Uint32LessThanOrEqual();
 402     } else if (r.BothInputsAre(Type::Signed32())) {
 403       less_than = machine()->Int32LessThan();
 404       less_than_or_equal = machine()->Int32LessThanOrEqual();
 405     } else {
 406       // TODO(turbofan): mixed signed/unsigned int32 comparisons.
 407       r.ConvertInputsToNumber();
 408       less_than = simplified()->NumberLessThan();
 409       less_than_or_equal = simplified()->NumberLessThanOrEqual();
 410     }
 411     const Operator* comparison;
 412     switch (node->opcode()) {
 413       case IrOpcode::kJSLessThan:
 414         comparison = less_than;
 415         break;
 416       case IrOpcode::kJSGreaterThan:
 417         comparison = less_than;
 418         r.SwapInputs();  // a > b => b < a
 419         break;
 420       case IrOpcode::kJSLessThanOrEqual:
 421         comparison = less_than_or_equal;
 422         break;
 423       case IrOpcode::kJSGreaterThanOrEqual:
 424         comparison = less_than_or_equal;
 425         r.SwapInputs();  // a >= b => b <= a
 426         break;
 427       default:
 428         return NoChange();
 429     }
 430     return r.ChangeToPureOperator(comparison);
 431   }
 432   // TODO(turbofan): relax/remove effects of this operator in other cases.
 433   return NoChange();  // Keep a generic comparison.
 434 }
 435
 436
 437 Reduction JSTypedLowering::ReduceJSEqual(Node* node, bool invert) {
 438   JSBinopReduction r(this, node);
 439
 440   if (r.BothInputsAre(Type::Number())) {
 441     return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
 442   }
 443   if (r.BothInputsAre(Type::String())) {
 444     return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
 445   }
 446   if (r.BothInputsAre(Type::Receiver())) {
 447     return r.ChangeToPureOperator(
 448         simplified()->ReferenceEqual(Type::Receiver()), invert);
 449   }
 450   // TODO(turbofan): js-typed-lowering of Equal(undefined)
 451   // TODO(turbofan): js-typed-lowering of Equal(null)
 452   // TODO(turbofan): js-typed-lowering of Equal(boolean)
 453   return NoChange();
 454 }
 455
 456
 457 Reduction JSTypedLowering::ReduceJSStrictEqual(Node* node, bool invert) {
 458   JSBinopReduction r(this, node);
 459   if (r.left() == r.right()) {
 460     // x === x is always true if x != NaN
 461     if (!r.left_type()->Maybe(Type::NaN())) {
 462       return ReplaceEagerly(node, jsgraph()->BooleanConstant(!invert));
 463     }
 464   }
 465   if (r.OneInputCannotBe(Type::NumberOrString())) {
 466     // For values with canonical representation (i.e. not string nor number) an
 467     // empty type intersection means the values cannot be strictly equal.
 468     if (!r.left_type()->Maybe(r.right_type())) {
 469       return ReplaceEagerly(node, jsgraph()->BooleanConstant(invert));
 470     }
 471   }
 472   if (r.OneInputIs(Type::Undefined())) {
 473     return r.ChangeToPureOperator(
 474         simplified()->ReferenceEqual(Type::Undefined()), invert);
 475   }
 476   if (r.OneInputIs(Type::Null())) {
 477     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Null()),
 478                                   invert);
 479   }
 480   if (r.OneInputIs(Type::Boolean())) {
 481     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Boolean()),
 482                                   invert);
 483   }
 484   if (r.OneInputIs(Type::Object())) {
 485     return r.ChangeToPureOperator(simplified()->ReferenceEqual(Type::Object()),
 486                                   invert);
 487   }
 488   if (r.OneInputIs(Type::Receiver())) {
 489     return r.ChangeToPureOperator(
 490         simplified()->ReferenceEqual(Type::Receiver()), invert);
 491   }
 492   if (r.BothInputsAre(Type::String())) {
 493     return r.ChangeToPureOperator(simplified()->StringEqual(), invert);
 494   }
 495   if (r.BothInputsAre(Type::Number())) {
 496     return r.ChangeToPureOperator(simplified()->NumberEqual(), invert);
 497   }
 498   // TODO(turbofan): js-typed-lowering of StrictEqual(mixed types)
 499   return NoChange();
 500 }
 501
 502
 503 Reduction JSTypedLowering::ReduceJSUnaryNot(Node* node) {
 504   Node* input = node->InputAt(0);
 505   Type* input_type = NodeProperties::GetBounds(input).upper;
 506   if (input_type->Is(Type::Boolean())) {
 507     // JSUnaryNot(x:boolean,context) => BooleanNot(x)
 508     node->set_op(simplified()->BooleanNot());
 509     node->TrimInputCount(1);
 510     return Changed(node);
 511   }
 512   // JSUnaryNot(x,context) => BooleanNot(AnyToBoolean(x))
 513   node->set_op(simplified()->BooleanNot());
 514   node->ReplaceInput(0, graph()->NewNode(simplified()->AnyToBoolean(), input));
 515   node->TrimInputCount(1);
 516   return Changed(node);
 517 }
 518
 519
 520 Reduction JSTypedLowering::ReduceJSToBoolean(Node* node) {
 521   Node* input = node->InputAt(0);
 522   Type* input_type = NodeProperties::GetBounds(input).upper;
 523   if (input_type->Is(Type::Boolean())) {
 524     // JSToBoolean(x:boolean,context) => x
 525     return Replace(input);
 526   }
 527   // JSToBoolean(x,context) => AnyToBoolean(x)
 528   node->set_op(simplified()->AnyToBoolean());
 529   node->TrimInputCount(1);
 530   return Changed(node);
 531 }
 532
 533
 534 Reduction JSTypedLowering::ReduceJSToNumberInput(Node* input) {
 535   if (input->opcode() == IrOpcode::kJSToNumber) {
 536     // Recursively try to reduce the input first.
 537     Reduction result = ReduceJSToNumber(input);
 538     if (result.Changed()) return result;
 539     return Changed(input);  // JSToNumber(JSToNumber(x)) => JSToNumber(x)
 540   }
 541   // Check if we have a cached conversion.
 542   Node* conversion = FindConversion<IrOpcode::kJSToNumber>(input);
 543   if (conversion) return Replace(conversion);
 544   Type* input_type = NodeProperties::GetBounds(input).upper;
 545   if (input_type->Is(Type::Number())) {
 546     // JSToNumber(x:number) => x
 547     return Changed(input);
 548   }
 549   if (input_type->Is(Type::Undefined())) {
 550     // JSToNumber(undefined) => #NaN
 551     return Replace(jsgraph()->NaNConstant());
 552   }
 553   if (input_type->Is(Type::Null())) {
 554     // JSToNumber(null) => #0
 555     return Replace(jsgraph()->ZeroConstant());
 556   }
 557   if (input_type->Is(Type::Boolean())) {
 558     // JSToNumber(x:boolean) => BooleanToNumber(x)
 559     return Replace(graph()->NewNode(simplified()->BooleanToNumber(), input));
 560   }
 561   // TODO(turbofan): js-typed-lowering of ToNumber(x:string)
 562   return NoChange();
 563 }
 564
 565
 566 Reduction JSTypedLowering::ReduceJSToNumber(Node* node) {
 567   // Try to reduce the input first.
 568   Node* const input = node->InputAt(0);
 569   Reduction reduction = ReduceJSToNumberInput(input);
 570   if (reduction.Changed()) {
 571     NodeProperties::ReplaceWithValue(node, reduction.replacement());
 572     return reduction;
 573   }
 574   Type* const input_type = NodeProperties::GetBounds(input).upper;
 575   if (input_type->Is(Type::PlainPrimitive())) {
 576     if (input->opcode() == IrOpcode::kPhi) {
 577       // JSToNumber(phi(x1,...,xn,control):plain-primitive,context)
 578       //   => phi(JSToNumber(x1,no-context),
 579       //          ...,
 580       //          JSToNumber(xn,no-context),control)
 581       int const input_count = input->InputCount() - 1;
 582       Node* const control = input->InputAt(input_count);
 583       DCHECK_LE(0, input_count);
 584       DCHECK(NodeProperties::IsControl(control));
 585       DCHECK(NodeProperties::GetBounds(node).upper->Is(Type::Number()));
 586       DCHECK(!NodeProperties::GetBounds(input).upper->Is(Type::Number()));
 587       RelaxEffects(node);
 588       node->set_op(common()->Phi(kMachAnyTagged, input_count));
 589       for (int i = 0; i < input_count; ++i) {
 590         // We must be very careful not to introduce cycles when pushing
 591         // operations into phis. It is safe for {value}, since it appears
 592         // as input to the phi that we are replacing, but it's not safe
 593         // to simply reuse the context of the {node}. However, ToNumber()
 594         // does not require a context anyways, so it's safe to discard it
 595         // here and pass the dummy context.
 596         Node* const value = ConvertToNumber(input->InputAt(i));
 597         if (i < node->InputCount()) {
 598           node->ReplaceInput(i, value);
 599         } else {
 600           node->AppendInput(graph()->zone(), value);
 601         }
 602       }
 603       if (input_count < node->InputCount()) {
 604         node->ReplaceInput(input_count, control);
 605       } else {
 606         node->AppendInput(graph()->zone(), control);
 607       }
 608       node->TrimInputCount(input_count + 1);
 609       return Changed(node);
 610     }
 611     if (input->opcode() == IrOpcode::kSelect) {
 612       // JSToNumber(select(c,x1,x2):plain-primitive,context)
 613       //   => select(c,JSToNumber(x1,no-context),JSToNumber(x2,no-context))
 614       int const input_count = input->InputCount();
 615       BranchHint const input_hint = SelectParametersOf(input->op()).hint();
 616       DCHECK_EQ(3, input_count);
 617       DCHECK(NodeProperties::GetBounds(node).upper->Is(Type::Number()));
 618       DCHECK(!NodeProperties::GetBounds(input).upper->Is(Type::Number()));
 619       RelaxEffects(node);
 620       node->set_op(common()->Select(kMachAnyTagged, input_hint));
 621       node->ReplaceInput(0, input->InputAt(0));
 622       for (int i = 1; i < input_count; ++i) {
 623         // We must be very careful not to introduce cycles when pushing
 624         // operations into selects. It is safe for {value}, since it appears
 625         // as input to the select that we are replacing, but it's not safe
 626         // to simply reuse the context of the {node}. However, ToNumber()
 627         // does not require a context anyways, so it's safe to discard it
 628         // here and pass the dummy context.
 629         Node* const value = ConvertToNumber(input->InputAt(i));
 630         node->ReplaceInput(i, value);
 631       }
 632       node->TrimInputCount(input_count);
 633       return Changed(node);
 634     }
 635     // Remember this conversion.
 636     InsertConversion(node);
 637     if (NodeProperties::GetContextInput(node) !=
 638             jsgraph()->NoContextConstant() ||
 639         NodeProperties::GetEffectInput(node) != graph()->start() ||
 640         NodeProperties::GetControlInput(node) != graph()->start()) {
 641       // JSToNumber(x:plain-primitive,context,effect,control)
 642       //   => JSToNumber(x,no-context,start,start)
 643       RelaxEffects(node);
 644       NodeProperties::ReplaceContextInput(node, jsgraph()->NoContextConstant());
 645       NodeProperties::ReplaceControlInput(node, graph()->start());
 646       NodeProperties::ReplaceEffectInput(node, graph()->start());
 647       if (OperatorProperties::HasFrameStateInput(node->op())) {
 648         NodeProperties::ReplaceFrameStateInput(node,
 649                                                jsgraph()->EmptyFrameState());
 650       }
 651       return Changed(node);
 652     }
 653   }
 654   return NoChange();
 655 }
 656
 657
 658 Reduction JSTypedLowering::ReduceJSToStringInput(Node* input) {
 659   if (input->opcode() == IrOpcode::kJSToString) {
 660     // Recursively try to reduce the input first.
 661     Reduction result = ReduceJSToString(input);
 662     if (result.Changed()) return result;
 663     return Changed(input);  // JSToString(JSToString(x)) => JSToString(x)
 664   }
 665   Type* input_type = NodeProperties::GetBounds(input).upper;
 666   if (input_type->Is(Type::String())) {
 667     return Changed(input);  // JSToString(x:string) => x
 668   }
 669   if (input_type->Is(Type::Undefined())) {
 670     return Replace(jsgraph()->HeapConstant(factory()->undefined_string()));
 671   }
 672   if (input_type->Is(Type::Null())) {
 673     return Replace(jsgraph()->HeapConstant(factory()->null_string()));
 674   }
 675   // TODO(turbofan): js-typed-lowering of ToString(x:boolean)
 676   // TODO(turbofan): js-typed-lowering of ToString(x:number)
 677   return NoChange();
 678 }
 679
 680
 681 Reduction JSTypedLowering::ReduceJSToString(Node* node) {
 682   // Try to reduce the input first.
 683   Node* const input = node->InputAt(0);
 684   Reduction reduction = ReduceJSToStringInput(input);
 685   if (reduction.Changed()) {
 686     NodeProperties::ReplaceWithValue(node, reduction.replacement());
 687     return reduction;
 688   }
 689   return NoChange();
 690 }
 691
 692
 693 Reduction JSTypedLowering::ReduceJSLoadProperty(Node* node) {
 694   Node* key = NodeProperties::GetValueInput(node, 1);
 695   Node* base = NodeProperties::GetValueInput(node, 0);
 696   Type* key_type = NodeProperties::GetBounds(key).upper;
 697   // TODO(mstarzinger): This lowering is not correct if:
 698   //   a) The typed array or it's buffer is neutered.
 699   HeapObjectMatcher<Object> mbase(base);
 700   if (mbase.HasValue() && mbase.Value().handle()->IsJSTypedArray()) {
 701     Handle<JSTypedArray> const array =
 702         Handle<JSTypedArray>::cast(mbase.Value().handle());
 703     array->GetBuffer()->set_is_neuterable(false);
 704     BufferAccess const access(array->type());
 705     size_t const k = ElementSizeLog2Of(access.machine_type());
 706     double const byte_length = array->byte_length()->Number();
 707     CHECK_LT(k, arraysize(shifted_int32_ranges_));
 708     if (IsExternalArrayElementsKind(array->map()->elements_kind()) &&
 709         key_type->Is(shifted_int32_ranges_[k]) && byte_length <= kMaxInt) {
 710       // JSLoadProperty(typed-array, int32)
 711       Handle<ExternalArray> elements =
 712           Handle<ExternalArray>::cast(handle(array->elements()));
 713       Node* buffer = jsgraph()->PointerConstant(elements->external_pointer());
 714       Node* length = jsgraph()->Constant(byte_length);
 715       Node* effect = NodeProperties::GetEffectInput(node);
 716       Node* control = NodeProperties::GetControlInput(node);
 717       // Check if we can avoid the bounds check.
 718       if (key_type->Min() >= 0 && key_type->Max() < array->length()->Number()) {
 719         Node* load = graph()->NewNode(
 720             simplified()->LoadElement(
 721                 AccessBuilder::ForTypedArrayElement(array->type(), true)),
 722             buffer, key, effect, control);
 723         return ReplaceEagerly(node, load);
 724       }
 725       // Compute byte offset.
 726       Node* offset = Word32Shl(key, static_cast<int>(k));
 727       Node* load = graph()->NewNode(simplified()->LoadBuffer(access), buffer,
 728                                     offset, length, effect, control);
 729       return ReplaceEagerly(node, load);
 730     }
 731   }
 732   return NoChange();
 733 }
 734
 735
 736 Reduction JSTypedLowering::ReduceJSStoreProperty(Node* node) {
 737   Node* key = NodeProperties::GetValueInput(node, 1);
 738   Node* base = NodeProperties::GetValueInput(node, 0);
 739   Node* value = NodeProperties::GetValueInput(node, 2);
 740   Type* key_type = NodeProperties::GetBounds(key).upper;
 741   Type* value_type = NodeProperties::GetBounds(value).upper;
 742   // TODO(mstarzinger): This lowering is not correct if:
 743   //   a) The typed array or its buffer is neutered.
 744   HeapObjectMatcher<Object> mbase(base);
 745   if (mbase.HasValue() && mbase.Value().handle()->IsJSTypedArray()) {
 746     Handle<JSTypedArray> const array =
 747         Handle<JSTypedArray>::cast(mbase.Value().handle());
 748     array->GetBuffer()->set_is_neuterable(false);
 749     BufferAccess const access(array->type());
 750     size_t const k = ElementSizeLog2Of(access.machine_type());
 751     double const byte_length = array->byte_length()->Number();
 752     CHECK_LT(k, arraysize(shifted_int32_ranges_));
 753     if (IsExternalArrayElementsKind(array->map()->elements_kind()) &&
 754         access.external_array_type() != kExternalUint8ClampedArray &&
 755         key_type->Is(shifted_int32_ranges_[k]) && byte_length <= kMaxInt) {
 756       // JSLoadProperty(typed-array, int32)
 757       Handle<ExternalArray> elements =
 758           Handle<ExternalArray>::cast(handle(array->elements()));
 759       Node* buffer = jsgraph()->PointerConstant(elements->external_pointer());
 760       Node* length = jsgraph()->Constant(byte_length);
 761       Node* context = NodeProperties::GetContextInput(node);
 762       Node* effect = NodeProperties::GetEffectInput(node);
 763       Node* control = NodeProperties::GetControlInput(node);
 764       // Convert to a number first.
 765       if (!value_type->Is(Type::Number())) {
 766         Reduction number_reduction = ReduceJSToNumberInput(value);
 767         if (number_reduction.Changed()) {
 768           value = number_reduction.replacement();
 769         } else {
 770           if (OperatorProperties::HasFrameStateInput(
 771                   javascript()->ToNumber())) {
 772             value = effect =
 773                 graph()->NewNode(javascript()->ToNumber(), value, context,
 774                                  jsgraph()->EmptyFrameState(), effect, control);
 775           } else {
 776             value = effect = graph()->NewNode(javascript()->ToNumber(), value,
 777                                               context, effect, control);
 778           }
 779         }
 780       }
 781       // For integer-typed arrays, convert to the integer type.
 782       if (TypeOf(access.machine_type()) == kTypeInt32 &&
 783           !value_type->Is(Type::Signed32())) {
 784         value = graph()->NewNode(simplified()->NumberToInt32(), value);
 785       } else if (TypeOf(access.machine_type()) == kTypeUint32 &&
 786                  !value_type->Is(Type::Unsigned32())) {
 787         value = graph()->NewNode(simplified()->NumberToUint32(), value);
 788       }
 789       // Check if we can avoid the bounds check.
 790       if (key_type->Min() >= 0 && key_type->Max() < array->length()->Number()) {
 791         node->set_op(simplified()->StoreElement(
 792             AccessBuilder::ForTypedArrayElement(array->type(), true)));
 793         node->ReplaceInput(0, buffer);
 794         DCHECK_EQ(key, node->InputAt(1));
 795         node->ReplaceInput(2, value);
 796         node->ReplaceInput(3, effect);
 797         node->ReplaceInput(4, control);
 798         node->TrimInputCount(5);
 799         return Changed(node);
 800       }
 801       // Compute byte offset.
 802       Node* offset = Word32Shl(key, static_cast<int>(k));
 803       // Turn into a StoreBuffer operation.
 804       node->set_op(simplified()->StoreBuffer(access));
 805       node->ReplaceInput(0, buffer);
 806       node->ReplaceInput(1, offset);
 807       node->ReplaceInput(2, length);
 808       node->ReplaceInput(3, value);
 809       node->ReplaceInput(4, effect);
 810       node->ReplaceInput(5, control);
 811       node->TrimInputCount(6);
 812       return Changed(node);
 813     }
 814   }
 815   return NoChange();
 816 }
 817
 818
 819 Reduction JSTypedLowering::ReduceJSLoadContext(Node* node) {
 820   DCHECK_EQ(IrOpcode::kJSLoadContext, node->opcode());
 821   ContextAccess const& access = ContextAccessOf(node->op());
 822   Node* const effect = NodeProperties::GetEffectInput(node);
 823   Node* const control = graph()->start();
 824   for (size_t i = 0; i < access.depth(); ++i) {
 825     node->ReplaceInput(
 826         0, graph()->NewNode(
 827                simplified()->LoadField(
 828                    AccessBuilder::ForContextSlot(Context::PREVIOUS_INDEX)),
 829                NodeProperties::GetValueInput(node, 0), effect, control));
 830   }
 831   node->set_op(
 832       simplified()->LoadField(AccessBuilder::ForContextSlot(access.index())));
 833   node->ReplaceInput(1, effect);
 834   node->ReplaceInput(2, control);
 835   DCHECK_EQ(3, node->InputCount());
 836   return Changed(node);
 837 }
 838
 839
 840 Reduction JSTypedLowering::ReduceJSStoreContext(Node* node) {
 841   DCHECK_EQ(IrOpcode::kJSStoreContext, node->opcode());
 842   ContextAccess const& access = ContextAccessOf(node->op());
 843   Node* const effect = NodeProperties::GetEffectInput(node);
 844   Node* const control = graph()->start();
 845   for (size_t i = 0; i < access.depth(); ++i) {
 846     node->ReplaceInput(
 847         0, graph()->NewNode(
 848                simplified()->LoadField(
 849                    AccessBuilder::ForContextSlot(Context::PREVIOUS_INDEX)),
 850                NodeProperties::GetValueInput(node, 0), effect, control));
 851   }
 852   node->set_op(
 853       simplified()->StoreField(AccessBuilder::ForContextSlot(access.index())));
 854   node->RemoveInput(2);
 855   DCHECK_EQ(4, node->InputCount());
 856   return Changed(node);
 857 }
 858
 859
 860 Reduction JSTypedLowering::Reduce(Node* node) {
 861   // Check if the output type is a singleton.  In that case we already know the
 862   // result value and can simply replace the node if it's eliminable.
 863   if (!NodeProperties::IsConstant(node) && NodeProperties::IsTyped(node) &&
 864       node->op()->HasProperty(Operator::kEliminatable)) {
 865     Type* upper = NodeProperties::GetBounds(node).upper;
 866     if (upper->IsConstant()) {
 867       Node* replacement = jsgraph()->Constant(upper->AsConstant()->Value());
 868       NodeProperties::ReplaceWithValue(node, replacement);
 869       return Changed(replacement);
 870     } else if (upper->Is(Type::MinusZero())) {
 871       Node* replacement = jsgraph()->Constant(factory()->minus_zero_value());
 872       NodeProperties::ReplaceWithValue(node, replacement);
 873       return Changed(replacement);
 874     } else if (upper->Is(Type::NaN())) {
 875       Node* replacement = jsgraph()->NaNConstant();
 876       NodeProperties::ReplaceWithValue(node, replacement);
 877       return Changed(replacement);
 878     } else if (upper->Is(Type::Null())) {
 879       Node* replacement = jsgraph()->NullConstant();
 880       NodeProperties::ReplaceWithValue(node, replacement);
 881       return Changed(replacement);
 882     } else if (upper->Is(Type::PlainNumber()) && upper->Min() == upper->Max()) {
 883       Node* replacement = jsgraph()->Constant(upper->Min());
 884       NodeProperties::ReplaceWithValue(node, replacement);
 885       return Changed(replacement);
 886     } else if (upper->Is(Type::Undefined())) {
 887       Node* replacement = jsgraph()->UndefinedConstant();
 888       NodeProperties::ReplaceWithValue(node, replacement);
 889       return Changed(replacement);
 890     }
 891   }
 892   switch (node->opcode()) {
 893     case IrOpcode::kJSEqual:
 894       return ReduceJSEqual(node, false);
 895     case IrOpcode::kJSNotEqual:
 896       return ReduceJSEqual(node, true);
 897     case IrOpcode::kJSStrictEqual:
 898       return ReduceJSStrictEqual(node, false);
 899     case IrOpcode::kJSStrictNotEqual:
 900       return ReduceJSStrictEqual(node, true);
 901     case IrOpcode::kJSLessThan:         // fall through
 902     case IrOpcode::kJSGreaterThan:      // fall through
 903     case IrOpcode::kJSLessThanOrEqual:  // fall through
 904     case IrOpcode::kJSGreaterThanOrEqual:
 905       return ReduceJSComparison(node);
 906     case IrOpcode::kJSBitwiseOr:
 907       return ReduceJSBitwiseOr(node);
 908     case IrOpcode::kJSBitwiseXor:
 909       return ReduceInt32Binop(node, machine()->Word32Xor());
 910     case IrOpcode::kJSBitwiseAnd:
 911       return ReduceInt32Binop(node, machine()->Word32And());
 912     case IrOpcode::kJSShiftLeft:
 913       return ReduceUI32Shift(node, kSigned, machine()->Word32Shl());
 914     case IrOpcode::kJSShiftRight:
 915       return ReduceUI32Shift(node, kSigned, machine()->Word32Sar());
 916     case IrOpcode::kJSShiftRightLogical:
 917       return ReduceUI32Shift(node, kUnsigned, machine()->Word32Shr());
 918     case IrOpcode::kJSAdd:
 919       return ReduceJSAdd(node);
 920     case IrOpcode::kJSSubtract:
 921       return ReduceNumberBinop(node, simplified()->NumberSubtract());
 922     case IrOpcode::kJSMultiply:
 923       return ReduceJSMultiply(node);
 924     case IrOpcode::kJSDivide:
 925       return ReduceNumberBinop(node, simplified()->NumberDivide());
 926     case IrOpcode::kJSModulus:
 927       return ReduceNumberBinop(node, simplified()->NumberModulus());
 928     case IrOpcode::kJSUnaryNot:
 929       return ReduceJSUnaryNot(node);
 930     case IrOpcode::kJSToBoolean:
 931       return ReduceJSToBoolean(node);
 932     case IrOpcode::kJSToNumber:
 933       return ReduceJSToNumber(node);
 934     case IrOpcode::kJSToString:
 935       return ReduceJSToString(node);
 936     case IrOpcode::kJSLoadProperty:
 937       return ReduceJSLoadProperty(node);
 938     case IrOpcode::kJSStoreProperty:
 939       return ReduceJSStoreProperty(node);
 940     case IrOpcode::kJSLoadContext:
 941       return ReduceJSLoadContext(node);
 942     case IrOpcode::kJSStoreContext:
 943       return ReduceJSStoreContext(node);
 944     default:
 945       break;
 946   }
 947   return NoChange();
 948 }
 949
 950
 951 Node* JSTypedLowering::ConvertToNumber(Node* input) {
 952   DCHECK(NodeProperties::GetBounds(input).upper->Is(Type::PlainPrimitive()));
 953   // Avoid inserting too many eager ToNumber() operations.
 954   Reduction const reduction = ReduceJSToNumberInput(input);
 955   if (reduction.Changed()) return reduction.replacement();
 956   // TODO(jarin) Use PlainPrimitiveToNumber once we have it.
 957   Node* const conversion =
 958       FLAG_turbo_deoptimization
 959           ? graph()->NewNode(javascript()->ToNumber(), input,
 960                              jsgraph()->NoContextConstant(),
 961                              jsgraph()->EmptyFrameState(), graph()->start(),
 962                              graph()->start())
 963           : graph()->NewNode(javascript()->ToNumber(), input,
 964                              jsgraph()->NoContextConstant(), graph()->start(),
 965                              graph()->start());
 966   InsertConversion(conversion);
 967   return conversion;
 968 }
 969
 970
 971 template <IrOpcode::Value kOpcode>
 972 Node* JSTypedLowering::FindConversion(Node* input) {
 973   size_t const input_id = input->id();
 974   if (input_id < conversions_.size()) {
 975     Node* const conversion = conversions_[input_id];
 976     if (conversion && conversion->opcode() == kOpcode) {
 977       return conversion;
 978     }
 979   }
 980   return nullptr;
 981 }
 982
 983
 984 void JSTypedLowering::InsertConversion(Node* conversion) {
 985   DCHECK(conversion->opcode() == IrOpcode::kJSToNumber);
 986   size_t const input_id = conversion->InputAt(0)->id();
 987   if (input_id >= conversions_.size()) {
 988     conversions_.resize(2 * input_id + 1);
 989   }
 990   conversions_[input_id] = conversion;
 991 }
 992
 993
 994 Node* JSTypedLowering::Word32Shl(Node* const lhs, int32_t const rhs) {
 995   if (rhs == 0) return lhs;
 996   return graph()->NewNode(machine()->Word32Shl(), lhs,
 997                           jsgraph()->Int32Constant(rhs));
 998 }
 999
1000
1001 Factory* JSTypedLowering::factory() const { return jsgraph()->factory(); }
1002
1003
1004 Graph* JSTypedLowering::graph() const { return jsgraph()->graph(); }
1005
1006
1007 JSOperatorBuilder* JSTypedLowering::javascript() const {
1008   return jsgraph()->javascript();
1009 }
1010
1011
1012 CommonOperatorBuilder* JSTypedLowering::common() const {
1013   return jsgraph()->common();
1014 }
1015
1016
1017 MachineOperatorBuilder* JSTypedLowering::machine() const {
1018   return jsgraph()->machine();
1019 }
1020
1021 }  // namespace compiler
1022 }  // namespace internal
1023 }  // namespace v8