[builtins] implement Array.prototype.includes in TurboFan

src/builtins/builtins.cc

Index: src/builtins/builtins.cc
diff --git a/src/builtins/builtins.cc b/src/builtins/builtins.cc
index e57091311a77d97b090c10a92f334340e7915c4f..8c20d81ba18cfb16d1ffcbc2ec9fadf3e2f66c58 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -343,6 +343,219 @@ void Builtins::Generate_ArrayIsArray(CodeStubAssembler* assembler) {
       assembler->CallRuntime(Runtime::kArrayIsArray, context, object));
 }
 
+void Builtins::Generate_ArrayIncludes(CodeStubAssembler* assembler) {
+  typedef compiler::Node Node;
+  typedef CodeStubAssembler::Label Label;
+  typedef CodeStubAssembler::Variable Variable;
+
+  Node* array = assembler->Parameter(0);
+  Node* search_element = assembler->Parameter(1);
+  Node* start_from = assembler->Parameter(2);
+  Node* context = assembler->Parameter(3 + 2);
+
+  Node* int32_zero = assembler->Int32Constant(0);
+  Node* int32_one = assembler->Int32Constant(1);
+
+  Variable len(assembler, MachineRepresentation::kWord32),
+      k(assembler, MachineRepresentation::kWord32),
+      n(assembler, MachineRepresentation::kWord32);
+
+  Label init_k(assembler), return_true(assembler), return_false(assembler),
+      call_runtime(assembler);
+
+  {  // Prologue
+    //   1. Bailout to slow path if `array` is not a JSArray
+    assembler->GotoIf(assembler->WordIsSmi(array), &call_runtime);
+    Node* instance_type = assembler->LoadInstanceType(array);
+    assembler->GotoUnless(
+        assembler->Word32Equal(instance_type,
+                               assembler->Int32Constant(JS_ARRAY_TYPE)),
+        &call_runtime);
+
+    //   2. Bailout to slow path if elements kind is not fast
+    Node* map = assembler->LoadMap(array);
+    Node* bit_field2 = assembler->LoadMapBitField2(map);
+    Node* elements_kind =
+        assembler->BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+    assembler->GotoIf(
+        assembler->Int32GreaterThan(
+            elements_kind, assembler->Int32Constant(LAST_FAST_ELEMENTS_KIND)),
+        &call_runtime);
+
+    // 3. Bailout to slow path if array protector field invalid
+    assembler->GotoUnless(
+        assembler->WordEqual(
+            assembler->LoadObjectField(
+                assembler->LoadRoot(Heap::kArrayProtectorRootIndex),
+                PropertyCell::kValueOffset),
+            assembler->SmiConstant(
+                Smi::FromInt(Isolate::kArrayProtectorValid))),
+        &call_runtime);
+
+    len.Bind(assembler->SmiToWord(
+        assembler->LoadObjectField(array, JSArray::kLengthOffset)));
+    assembler->GotoUnless(assembler->Word32Equal(len.value(), int32_zero),
+                          &init_k);
+    assembler->Return(assembler->BooleanConstant(false));
+  }
+
+  assembler->Bind(&init_k);
+  {
+    Variable tagged_n(assembler, MachineRepresentation::kTagged);
+    Label done(assembler), if_neg(assembler), init_k_smi(assembler),
+        init_k_zero(assembler);
+    Callable call_to_integer = CodeFactory::ToInteger(assembler->isolate());
+    tagged_n.Bind(assembler->CallStub(call_to_integer, context, start_from));
+
+    assembler->GotoIf(assembler->WordIsSmi(tagged_n.value()), &init_k_smi);
+
+    Node* fp_len = assembler->ChangeInt32ToFloat64(len.value());
+    Node* fp_n = assembler->TruncateTaggedToFloat64(context, tagged_n.value());
+
+    assembler->GotoIf(assembler->Float64GreaterThanOrEqual(fp_n, fp_len),
+                      &return_false);
+
+    tagged_n.Bind(
+        assembler->SmiFromWord32(assembler->TruncateFloat64ToWord32(fp_n)));
+
+    assembler->Goto(&init_k_smi);
+    assembler->Bind(&init_k_smi);
+    n.Bind(assembler->SmiToWord32(tagged_n.value()));
+
+    assembler->GotoUnless(
+        assembler->Int32GreaterThanOrEqual(n.value(), int32_zero), &if_neg);
+    k.Bind(n.value());
+    assembler->Goto(&done);
+
+    assembler->Bind(&if_neg);
+    k.Bind(assembler->Int32Add(len.value(), n.value()));
+    assembler->BranchIf(assembler->Int32LessThan(k.value(), int32_zero),
+                        &init_k_zero, &done);
+
+    assembler->Bind(&init_k_zero);
+    k.Bind(int32_zero);
+
+    assembler->Goto(&done);
+    assembler->Bind(&done);
+  }
+
+  {  // Repeat while k < len
+    Variable element_k(assembler, MachineRepresentation::kTagged);
+    Variable stable(assembler, MachineRepresentation::kWord32);
+
+    Variable* loop_body_variables[] = {&k, &stable};
+
+    Label loop_body(assembler, 2,

[Benedikt Meurer, 2016/07/15 17:59:55]

You really want one really tight loop per elements kind here. The loop for Smi
elements will be super fast then, and same for non-holey double. For holey
arrays and object elements it's a bit more involved, but still not too bad.

Also I think you need to specialize depending on the type of searchElement,
i.e.:

1. If Type(searchElement) is not Number, but the array is double/holey double,
you can immediately return false.
2. If Type(searchElement) is Number and the array is double/holey double,
convert the searchElement to a float64, and just do a fast comparison on the
elements (in case of hole just skip, as undefined is not equal to any float64).

and so on.

[caitp, 2016/07/15 22:11:17]

This is a good idea, but currently this is not sound: as mentioned elsewhere,
even with the valid Array prototype protector, it's still possible to end up on
the fast path with elements on the prototype chain (subclasses of Array can do
this without breaking the protector). So, these objects are not limited to own
elements.

It seems like a bug that the protector isn't updated for subclasses of Array,
though

[Benedikt Meurer, 2016/07/16 12:40:27]

Ah indeed, you also need to check that the prototype of the receiver is the
Array prototype in addition to checking the protector, then it's sound.

For other JSArray receivers, you can walk up the prototype chain up until either
the Array prototype (if the protector is intact) or until null, and check for
each object, if

1.) it's a JSReceiver, and
2.) doesn't have any elements, and
3.) doesn't have any indexed interceptors or other specialities, i.e. requires
access checks, etc.

In that case you can use the fast path (and you don't need to check when you see
the hole). Note also that all of this is only necessary for holey arrays, i.e.
if elements kind is FAST_(|SMI_|DOUBLE_)HOLEY_ELEMENTS. Otherwise you don't need
to do any of this.

+                    static_cast<Variable **>(loop_body_variables)),
+        continue_loop(assembler), if_issmiorobject(assembler),
+        if_isdouble(assembler), if_slowpath(assembler), test_element(assembler);
+
+    stable.Bind(int32_one);
+    Node* map = assembler->LoadMap(array);
+    Node* bit_field2 = assembler->LoadMapBitField2(map);
+    Node* elements_kind =
+        assembler->BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+
+    assembler->Goto(&loop_body);
+    assembler->Bind(&loop_body);
+
+    assembler->GotoUnless(assembler->Uint32LessThan(k.value(), len.value()),
+                          &return_false);
+
+    assembler->GotoIf(assembler->WordEqual(stable.value(), int32_zero),
+                      &if_slowpath);
+
+    assembler->Branch(
+        assembler->Int32LessThan(
+            elements_kind, assembler->Int32Constant(FAST_DOUBLE_ELEMENTS)),
+        &if_issmiorobject, &if_isdouble);
+
+    assembler->Bind(&if_issmiorobject);
+    {  // Fast Smi/Object elements
+      Node* elements = assembler->LoadElements(array);
+      Node* length = assembler->LoadFixedArrayBaseLength(elements);
+
+      assembler->GotoUnless(
+          assembler->Int32LessThan(k.value(), assembler->SmiToWord32(length)),
+          &if_slowpath);
+
+      Node* element = assembler->LoadFixedArrayElement(elements, k.value());
+      Node* the_hole = assembler->TheHoleConstant();
+
+      assembler->GotoUnless(assembler->WordNotEqual(element, the_hole),
+                            &if_slowpath);

[Benedikt Meurer, 2016/07/15 17:59:55]

You can just turn the hole into undefined, since you checked the array
protector. So the prototype chain cannot contain any elements, so any hole
access always yields undefined.

[caitp, 2016/07/15 22:11:17]

I'm not sure, we still end up on the fast path with Array subclasses with
indexed accessors on SubClass.prototype.

[Benedikt Meurer, 2016/07/16 12:40:27]

As mentioned above, indexed accessors in the prototype chain cannot use the fast
path (if elements kind is holey).

+      element_k.Bind(element);
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&if_isdouble);
+    {  // Fast double elements
+      Node* elements = assembler->LoadElements(array);
+      Node* length = assembler->LoadFixedArrayBaseLength(elements);
+
+      assembler->GotoUnless(
+          assembler->Int32LessThan(k.value(), assembler->SmiToWord32(length)),
+          &if_slowpath);
+
+      if (kPointerSize == kDoubleSize) {
+        Node* element = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint64());
+        Node* the_hole = assembler->Int64Constant(kHoleNanInt64);
+        assembler->GotoIf(assembler->Word64Equal(element, the_hole),
+                          &if_slowpath);
+      } else {
+        Node* element_upper = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint32(),
+            kIeeeDoubleExponentWordOffset);
+        assembler->GotoIf(
+            assembler->Word32Equal(element_upper,
+                                   assembler->Int32Constant(kHoleNanUpper32)),
+            &if_slowpath);
+      }
+
+      Node* element = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      element_k.Bind(assembler->AllocateHeapNumberWithValue(element));
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&if_slowpath);
+    {
+      Node* element =
+          assembler->CallRuntime(Runtime::kGetProperty, context, array,
+                                 assembler->SmiFromWord32(k.value()));
+      element_k.Bind(element);
+
+      // Slow path may have modified elements backing store in some way.
+      assembler->GotoIf(assembler->WordEqual(stable.value(), int32_zero),
+                        &test_element);
+      Node* current_map = assembler->LoadMap(array);
+      assembler->GotoIf(assembler->WordEqual(map, current_map), &test_element);
+      stable.Bind(int32_zero);
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&test_element);
+    assembler->BranchIfSameValueZero(search_element, element_k.value(), context,
+                                     &return_true, &continue_loop);
+
+    assembler->Bind(&continue_loop);
+    k.Bind(assembler->Int32Add(k.value(), int32_one));
+    assembler->Goto(&loop_body);
+  }
+
+  assembler->Bind(&return_true);
+  assembler->Return(assembler->BooleanConstant(true));
+
+  assembler->Bind(&return_false);
+  assembler->Return(assembler->BooleanConstant(false));
+
+  assembler->Bind(&call_runtime);
+  assembler->Return(assembler->CallRuntime(Runtime::kArrayIncludes_Slow,
+                                           context, array, search_element,
+                                           start_from));
+}
+
 void Builtins::Generate_ObjectHasOwnProperty(CodeStubAssembler* assembler) {
   typedef compiler::Node Node;
   typedef CodeStubAssembler::Label Label;