[builtins] implement Array.prototype.includes in TurboFan

src/code-stub-assembler.cc

 // Copyright 2016 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/code-stub-assembler.h"
 #include "src/code-factory.h"
 #include "src/frames-inl.h"
 #include "src/frames.h"
 #include "src/ic/stub-cache.h"
 
@@ skipping 453 matching lines @@
 
 Node* CodeStubAssembler::WordIsSmi(Node* a) {
   return WordEqual(WordAnd(a, IntPtrConstant(kSmiTagMask)), IntPtrConstant(0));
 }
 
 Node* CodeStubAssembler::WordIsPositiveSmi(Node* a) {
   return WordEqual(WordAnd(a, IntPtrConstant(kSmiTagMask | kSmiSignMask)),
                    IntPtrConstant(0));
 }
 
+void CodeStubAssembler::BranchIfSameValueZero(Node* a, Node* b, Node* context,
+                                              Label* if_true, Label* if_false) {
+  Node* number_map = HeapNumberMapConstant();
+  Label a_isnumber(this), a_isnotnumber(this), b_isnumber(this), a_isnan(this),
+      float_not_equal(this);
+  // If register A and register B are identical, goto `if_true`
+  GotoIf(WordEqual(a, b), if_true);
+  // If either register A or B are Smis, goto `if_false`
+  GotoIf(Word32Or(WordIsSmi(a), WordIsSmi(b)), if_false);
+  // GotoIf(WordIsSmi(b), if_false);
+
+  Node* a_map = LoadMap(a);
+  Node* b_map = LoadMap(b);
+  Branch(WordEqual(a_map, number_map), &a_isnumber, &a_isnotnumber);
+
+  // If both register A and B are HeapNumbers, return true if they are equal,
+  // or if both are NaN
+  Bind(&a_isnumber);
+  {
+    Branch(WordEqual(b_map, number_map), &b_isnumber, if_false);
+
+    Bind(&b_isnumber);
+    Node* a_value = LoadHeapNumberValue(a);
+    Node* b_value = LoadHeapNumberValue(b);
+    BranchIfFloat64Equal(a_value, b_value, if_true, &float_not_equal);
+
+    Bind(&float_not_equal);
+    BranchIfFloat64IsNaN(a_value, &a_isnan, if_false);
+
+    Bind(&a_isnan);
+    BranchIfFloat64IsNaN(a_value, if_true, if_false);
+  }
+
+  Bind(&a_isnotnumber);
+  {
+    Label a_isstring(this), a_isnotstring(this);
+    Node* a_instance_type = LoadMapInstanceType(a_map);
+
+    Branch(Int32LessThan(a_instance_type, Int32Constant(FIRST_NONSTRING_TYPE)),
+           &a_isstring, &a_isnotstring);
+
+    Bind(&a_isstring);
+    {
+      Label b_isstring(this), b_isnotstring(this);
+      Node* b_instance_type = LoadInstanceType(b_map);
+
+      Branch(
+          Int32LessThan(b_instance_type, Int32Constant(FIRST_NONSTRING_TYPE)),
+          &b_isstring, if_false);
+
+      Bind(&b_isstring);
+      {
+        Callable callable = CodeFactory::StringEqual(isolate());
+        Node* result = CallStub(callable, context, a, b);
+        Branch(WordEqual(BooleanConstant(true), result), if_true, if_false);
+      }
+    }
+
+    Bind(&a_isnotstring);
+    {
+      // Check if {lhs} is a Simd128Value.
+      Label a_issimd128value(this);
+      Branch(Word32Equal(a_instance_type, Int32Constant(SIMD128_VALUE_TYPE)),
+             &a_issimd128value, if_false);
+
+      Bind(&a_issimd128value);
+      {
+        // Load the map of {rhs}.
+        BranchIfSimd128Equal(a, a_map, b, b_map, if_true, if_false);
+      }
+    }
+  }
+}
+
+void CodeStubAssembler::BranchIfSimd128Equal(Node* a, Node* a_map, Node* b,
+                                             Node* b_map, Label* if_true,
+                                             Label* if_false) {
+  Label if_mapsame(this);
+
+  Node* simd128_value_type = Int32Constant(SIMD128_VALUE_TYPE);
+  Assert(Word32Equal(LoadMapInstanceType(a_map), simd128_value_type));
+
+  Branch(Word32Equal(LoadMapInstanceType(b_map), simd128_value_type),
+         &if_mapsame, if_false);
+
+  Bind(&if_mapsame);
+  {
+    Label if_float32x4(this), if_notfloat32x4(this);
+    Node* float32x4_map = HeapConstant(factory()->float32x4_map());
+    Branch(WordEqual(a_map, float32x4_map), &if_float32x4, &if_notfloat32x4);
+
+    Bind(&if_float32x4);
+    {
+      for (int offset = Float32x4::kValueOffset - kHeapObjectTag;
+           offset < Float32x4::kSize - kHeapObjectTag;
+           offset += sizeof(float)) {
+        // Load the floating point values for {lhs} and {rhs}.
+        Node* a_value = Load(MachineType::Float32(), a, IntPtrConstant(offset));
+        Node* b_value = Load(MachineType::Float32(), b, IntPtrConstant(offset));
+
+        // Perform a floating point comparison.
+        Label if_valueequal(this);
+        Branch(Float32Equal(a_value, b_value), &if_valueequal, if_false);
+        Bind(&if_valueequal);
+      }
+      Goto(if_true);
+    }
+
+    Bind(&if_notfloat32x4);
+    {
+      // For other Simd128Values we just perform a bitwise comparison.
+      for (int offset = Simd128Value::kValueOffset - kHeapObjectTag;
+           offset < Simd128Value::kSize - kHeapObjectTag;
+           offset += kPointerSize) {
+        // Load the word values for {lhs} and {rhs}.
+        Node* a_value = Load(MachineType::Pointer(), a, IntPtrConstant(offset));
+        Node* b_value = Load(MachineType::Pointer(), b, IntPtrConstant(offset));
+
+        // Perform a bitwise word-comparison.
+        Label if_valueequal(this);
+        Branch(WordEqual(a_value, b_value), &if_valueequal, if_false);
+        Bind(&if_valueequal);
+      }
+
+      // Bitwise comparison succeeded, {lhs} and {rhs} considered equal.
+      Goto(if_true);
+    }
+  }
+}
+
+void CodeStubAssembler::BranchIfFastJSArray(Node* object, Node* context,
+                                            Label* if_true, Label* if_false) {
+  Node* int32_zero = Int32Constant(0);
+  Node* int32_one = Int32Constant(1);
+
+  Node* native_context = LoadNativeContext(context);
+  Node* array_prototype = LoadFixedArrayElement(
+      native_context, Int32Constant(Context::INITIAL_ARRAY_PROTOTYPE_INDEX));
+
+  Variable last_map(this, MachineRepresentation::kTagged);

[Benedikt Meurer, 2016/07/19 03:53:19]

Move this into the check_prototype { } block below.

+  Label check_prototype(this);
+
+  // Bailout if Smi
+  GotoIf(WordIsSmi(object), if_false);
+
+  Node* map = LoadMap(object);
+  last_map.Bind(map);

[Benedikt Meurer, 2016/07/19 03:53:19]

Move this into the check_prototype { } block below.

+
+  // Bailout if instance type is not JS_ARRAY_TYPE
+  GotoIf(WordNotEqual(LoadMapInstanceType(map), Int32Constant(JS_ARRAY_TYPE)),
+         if_false);
+
+  // Bailout if either receiver requires access checks, or has indexed
+  // interceptors access checks required
+  Node* bit_field = LoadMapBitField(map);
+  const int kNeedAccessCheckOrInterceptors =
+      (1 << Map::kIsAccessCheckNeeded) | (1 << Map::kHasIndexedInterceptor);
+  GotoIf(
+      Word32NotEqual(
+          Word32And(bit_field, Int32Constant(kNeedAccessCheckOrInterceptors)),
+          int32_zero),
+      if_false);

[Camillo Bruni, 2016/07/19 12:08:38]

see below, this check can be folded into a single instance type check.

+
+  Node* bit_field2 = LoadMapBitField2(map);
+  Node* elements_kind = BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+
+  // Bailout if slow receiver elements
+  GotoIf(
+      Int32GreaterThan(elements_kind, Int32Constant(LAST_FAST_ELEMENTS_KIND)),
+      if_false);
+
+  STATIC_ASSERT(FAST_HOLEY_SMI_ELEMENTS == (FAST_SMI_ELEMENTS | 1));
+  STATIC_ASSERT(FAST_HOLEY_ELEMENTS == (FAST_ELEMENTS | 1));
+  STATIC_ASSERT(FAST_HOLEY_DOUBLE_ELEMENTS == (FAST_DOUBLE_ELEMENTS | 1));
+
+  // Check prototype chain if receiver does not have packed elements
+  Node* holey_elements = Word32And(elements_kind, int32_one);
+  Branch(Word32Equal(holey_elements, int32_zero), if_true, &check_prototype);

[Benedikt Meurer, 2016/07/19 03:53:19]

Nice!

+
+  Bind(&check_prototype);
+  {
+    Label prototype_checks(this), loop_body(this, &last_map);
+    Goto(&loop_body);
+    Bind(&loop_body);
+    Node* current_map = last_map.value();
+    Node* proto = LoadObjectField(current_map, Map::kPrototypeOffset);
+
+    // End loop
+    GotoIf(WordEqual(proto, NullConstant()), if_true);
+    GotoIf(WordNotEqual(array_prototype, proto), &prototype_checks);
+    Node* array_protector = LoadObjectField(
+        LoadRoot(Heap::kArrayProtectorRootIndex), PropertyCell::kValueOffset);
+    Branch(WordEqual(array_protector,
+                     SmiConstant(Smi::FromInt(Isolate::kArrayProtectorValid))),
+           if_true, &prototype_checks);
+
+    Bind(&prototype_checks);
+    Node* proto_map = LoadMap(proto);
+
+    // Bailout if a Proxy found on the prototype chain
+    GotoIf(Word32Equal(LoadMapInstanceType(proto_map),
+                       Int32Constant(JS_PROXY_TYPE)),
+           if_false);
+
+    // Bailout if access checks or indexed interceptors are needed on the
+    // prototype
+    Node* bit_field = LoadMapBitField(proto_map);
+    GotoIf(
+        Word32NotEqual(
+            Word32And(bit_field, Int32Constant(kNeedAccessCheckOrInterceptors)),
+            int32_zero),
+        if_false);

[Camillo Bruni, 2016/07/19 12:08:38]

The interceptor checks can be folded into the instance type check above.
Only API objects can have interceptors or would need access checks: 

   GotoIf(Word32EqualOrLessThan(LoadMapInstanceType(proto_map),
                       Int32Constant(LAST_CUSTOM_ELEMENTS_RECEIVER)),
           if_false);

see PrototypeHasNoElements in builtins-array.cc

+
+    // Bailout if contains elements
+    Node* bit_field2 = LoadMapBitField2(proto_map);
+    Node* elements_kind = BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+    GotoUnless(Word32Equal(elements_kind, Int32Constant(NO_ELEMENTS)),
+               if_false);

[Camillo Bruni, 2016/07/19 12:08:37]

NO_ELEMENTS is not used yet, you have to compare the elements() FixedArray
against the empty_array (again see PrototypeHasNoElements).

+
+    last_map.Bind(proto_map);
+    Goto(&loop_body);
+  }
+}
+
 Node* CodeStubAssembler::AllocateRawUnaligned(Node* size_in_bytes,
                                               AllocationFlags flags,
                                               Node* top_address,
                                               Node* limit_address) {
   Node* top = Load(MachineType::Pointer(), top_address);
   Node* limit = Load(MachineType::Pointer(), limit_address);
 
   // If there's not enough space, call the runtime.
   Variable result(this, MachineRepresentation::kTagged);
   Label runtime_call(this, Label::kDeferred), no_runtime_call(this);
@@ skipping 2575 matching lines @@
   }
   Bind(&miss);
   {
     TailCallRuntime(Runtime::kLoadGlobalIC_Miss, p->context, p->slot,
                     p->vector);
   }
 }
 
 }  // namespace internal
 }  // namespace v8