[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..4fca369d2de09e4de9de607207a6bd907ffc9e0f 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -343,6 +343,128 @@ 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->Uint32LessThan(
+            assembler->Int32Constant(LAST_FAST_ELEMENTS_KIND), elements_kind),
+        &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));

[Benedikt Meurer, 2016/07/15 04:50:35]

ToInteger always returns a Smi if the value is in Smi range. So everything that
is not a Smi cannot be less than len anyways, so you can simplify this code.

[caitp, 2016/07/15 05:56:05]

The trouble is, for negative numbers that are less than -len, `k` is initialized
to 0. So I don't think I can just return false in the non-Smi case. Am I missing
something?

+
+    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
+    Label loop_body(assembler, &k);
+    assembler->Goto(&loop_body);
+    assembler->Bind(&loop_body);
+
+    assembler->GotoUnless(assembler->Uint32LessThan(k.value(), len.value()),

[Benedikt Meurer, 2016/07/15 04:50:35]

This should probably by Int32LessThan, although it might not matter in this
case.

+                          &return_false);
+
+    Callable call_get_property = CodeFactory::GetProperty(assembler->isolate());
+    Node* element_k = assembler->CallStub(call_get_property, context, array,

[Benedikt Meurer, 2016/07/15 04:50:35]

You shouldn't use GetPropertyStub here. You already know that you have fast
elements, so if you also check above that the array prototype protector is
intact (which guards that no one added elements in the Array prototype chain),
you can just load the element from the backing store and do the comparison
below.

+                                          assembler->SmiFromWord32(k.value()));
+
+    Callable call_same_value_zero =
+        CodeFactory::SameValueZero(assembler->isolate());
+    Node* result = assembler->CallStub(call_same_value_zero, context,

[Benedikt Meurer, 2016/07/15 04:50:35]

This also shouldn't call out to a stub, but you should implement something like

BranchIfSameValueZero(value, if_same, if_notsame)

on the CodeStubAssembler and use that instead, otherwise this might even be
slower than a naive C++ implementation.

+                                       search_element, element_k);
+    assembler->GotoIf(
+        assembler->WordEqual(result, assembler->BooleanConstant(true)),
+        &return_true);
+
+    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;