[builtins] implement Array.prototype.includes in TurboFan

src/builtins/builtins.cc

 // Copyright 2012 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/builtins/builtins.h"
 
 #include "src/api-arguments.h"
 #include "src/api-natives.h"
 #include "src/api.h"
 #include "src/base/ieee754.h"
@@ skipping 325 matching lines @@
   assembler->Return(assembler->BooleanConstant(true));
 
   assembler->Bind(&return_false);
   assembler->Return(assembler->BooleanConstant(false));
 
   assembler->Bind(&call_runtime);
   assembler->Return(
       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;
   typedef CodeStubAssembler::Variable Variable;
 
   Node* object = assembler->Parameter(0);
   Node* key = assembler->Parameter(1);
   Node* context = assembler->Parameter(4);
 
   Label call_runtime(assembler), return_true(assembler),
@@ skipping 6469 matching lines @@
 #define DEFINE_BUILTIN_ACCESSOR(Name, ...)                                    \
   Handle<Code> Builtins::Name() {                                             \
     Code** code_address = reinterpret_cast<Code**>(builtin_address(k##Name)); \
     return Handle<Code>(code_address);                                        \
   }
 BUILTIN_LIST_ALL(DEFINE_BUILTIN_ACCESSOR)
 #undef DEFINE_BUILTIN_ACCESSOR
 
 }  // namespace internal
 }  // namespace v8