[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);
+
+  Node* the_hole = assembler->TheHoleConstant();
+  Node* undefined = assembler->UndefinedConstant();
+  Node* heap_number_map = assembler->HeapNumberMapConstant();
+
+  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);
+
+  {
+    // Take slow path if not a JSArray, if retrieving elements requires
+    // traversing prototype, or if access checks are required.
+    Label init_len(assembler);
+    assembler->BranchIfFastJSArray(array, context, &init_len, &call_runtime);
+
+    assembler->Bind(&init_len);
+    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);
+  {
+    Label done(assembler), init_k_smi(assembler), init_k_heap_num(assembler),
+        init_k_zero(assembler), init_k_n(assembler);
+    Callable call_to_integer = CodeFactory::ToInteger(assembler->isolate());
+    Node* tagged_n = assembler->CallStub(call_to_integer, context, start_from);
+
+    assembler->Branch(assembler->WordIsSmi(tagged_n), &init_k_smi,
+                      &init_k_heap_num);
+
+    assembler->Bind(&init_k_smi);
+    {
+      n.Bind(assembler->SmiToWord32(tagged_n));
+      assembler->Goto(&init_k_n);
+    }
+
+    assembler->Bind(&init_k_heap_num);
+    {
+      Label abort(assembler);
+      Node* fp_len = assembler->ChangeInt32ToFloat64(len.value());
+      Node* fp_n = assembler->LoadHeapNumberValue(tagged_n);
+      assembler->GotoIf(assembler->Float64GreaterThanOrEqual(fp_n, fp_len),
+                        &abort);
+      n.Bind(assembler->TruncateFloat64ToWord32(fp_n));
+      assembler->Goto(&init_k_n);
+
+      assembler->Bind(&abort);
+      assembler->Return(assembler->BooleanConstant(false));
+    }
+
+    assembler->Bind(&init_k_n);
+    {
+      Label if_positive(assembler), if_negative(assembler), done(assembler);
+      assembler->Branch(assembler->Int32LessThan(n.value(), int32_zero),
+                        &if_negative, &if_positive);
+
+      assembler->Bind(&if_positive);
+      {
+        k.Bind(n.value());
+        assembler->Goto(&done);
+      }
+
+      assembler->Bind(&if_negative);
+      {
+        k.Bind(assembler->Int32Add(len.value(), n.value()));
+        assembler->Branch(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);
+    }
+  }
+
+  int32_t element_kinds[] = {
+      FAST_SMI_ELEMENTS,   FAST_HOLEY_SMI_ELEMENTS, FAST_ELEMENTS,
+      FAST_HOLEY_ELEMENTS, FAST_DOUBLE_ELEMENTS,    FAST_HOLEY_DOUBLE_ELEMENTS,
+  };
+
+  Label if_smiorobjects(assembler), if_packed_doubles(assembler),
+      if_holey_doubles(assembler);
+  Label* element_kind_handlers[] = {&if_smiorobjects,   &if_smiorobjects,
+                                    &if_smiorobjects,   &if_smiorobjects,
+                                    &if_packed_doubles, &if_holey_doubles};
+
+  Node* map = assembler->LoadMap(array);
+  Node* bit_field2 = assembler->LoadMapBitField2(map);
+  Node* elements_kind =
+      assembler->BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+  Node* elements = assembler->LoadElements(array);
+  assembler->Switch(elements_kind, &return_false, element_kinds,
+                    element_kind_handlers, arraysize(element_kinds));
+
+  assembler->Bind(&if_smiorobjects);

[caitp, 2016/07/17 03:26:47]

There are lots of different tight loops here, to but it doesn't seem to make a
significant difference (in the admittedly broken microbenchmark from the user)
--- still ends up roughly the same (with a ~30% longer runtime than
Array.prototype.indexOf() for arbitrary iteration counts with default options),
and it does make the code a lot bigger and harder to read.

[Benedikt Meurer, 2016/07/17 06:03:18]

Awesome, I think this is the maximum you can get out of this. I agree tho, that
we need some rearranging to make this easier to read (also some code sharing
could happen with a TurboFan'ed version of Array.prototype.indexOf).

Array.prototype.indexOf() is faster because there's special code in Crankshaft
to inline a really fast, specialized version into the caller. This doesn't exist
for includes, so being only ~30% slower with a general version is a pretty
amazing result.

To do a fair comparison, you could disable the kArrayIndexOf case for builtin
inlining in hydrogen.cc.

[caitp, 2016/07/18 22:10:23]

I had looked at adding a JSBuiltinReducer for ArrayIncludes, but it seems easier
to do this in Crankshaft via TryInlineBuiltinMethodCall(), unless I'm missing
something. It doesn't look like I can do anything other than rely on information
generated by the Typer in TF, which may not be enough to tell me about an
input's Map to make informed decisions in inlining.

That said, when kArrayIndexOf reduction is disabled in crankshaft, the
Array.prototype.includes test consistently does 3-5ms better than the indexOf
test in that naive micro-benchmark, so that's a good sign.

+  {
+    Label ident_loop(assembler, &k), heap_num_loop(assembler),
+        string_loop(assembler, &k), simd_loop(assembler),
+        undef_loop(assembler, &k);
+
+    assembler->GotoIf(assembler->WordIsSmi(search_element), &ident_loop);
+    assembler->GotoIf(assembler->WordEqual(search_element, undefined),
+                      &undef_loop);
+    Node* map = assembler->LoadMap(search_element);
+    assembler->GotoIf(assembler->WordEqual(map, heap_number_map),
+                      &heap_num_loop);
+    Node* search_type = assembler->LoadMapInstanceType(map);
+    assembler->GotoIf(
+        assembler->Int32LessThan(
+            search_type, assembler->Int32Constant(FIRST_NONSTRING_TYPE)),
+        &string_loop);
+    assembler->GotoIf(
+        assembler->WordEqual(search_type,
+                             assembler->Int32Constant(SIMD128_VALUE_TYPE)),
+        &simd_loop);
+    assembler->Goto(&ident_loop);
+
+    assembler->Bind(&ident_loop);
+    {
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+      Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+      assembler->GotoIf(assembler->WordEqual(element_k, search_element),
+                        &return_true);
+
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&ident_loop);
+    }
+
+    assembler->Bind(&undef_loop);
+    {
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+      Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+      assembler->GotoIf(assembler->WordEqual(element_k, undefined),
+                        &return_true);
+      assembler->GotoIf(assembler->WordEqual(element_k, the_hole),
+                        &return_true);
+
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&undef_loop);
+    }
+
+    assembler->Bind(&heap_num_loop);
+    {
+      Label nan_loop(assembler, &k), not_nan_loop(assembler, &k);
+      Node* search_num = assembler->LoadHeapNumberValue(search_element);
+      assembler->BranchIfFloat64IsNaN(search_num, &nan_loop, &not_nan_loop);
+
+      assembler->Bind(&not_nan_loop);
+      {
+        Label continue_loop(assembler);
+        assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                              &return_false);
+        Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+        assembler->GotoIf(assembler->WordIsSmi(element_k), &continue_loop);
+        assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
+                                                  heap_number_map),
+                          &continue_loop);
+        assembler->BranchIfFloat64Equal(
+            search_num, assembler->LoadHeapNumberValue(element_k), &return_true,
+            &continue_loop);
+
+        assembler->Bind(&continue_loop);
+        k.Bind(assembler->Int32Add(k.value(), int32_one));
+        assembler->Goto(&not_nan_loop);
+      }
+
+      assembler->Bind(&nan_loop);
+      {
+        Label continue_loop(assembler);
+        assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                              &return_false);
+        Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+        assembler->GotoIf(assembler->WordIsSmi(element_k), &continue_loop);
+        assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
+                                                  heap_number_map),
+                          &continue_loop);
+        assembler->BranchIfFloat64IsNaN(
+            assembler->LoadHeapNumberValue(element_k), &return_true,
+            &continue_loop);
+
+        assembler->Bind(&continue_loop);
+        k.Bind(assembler->Int32Add(k.value(), int32_one));
+        assembler->Goto(&nan_loop);
+      }
+    }
+
+    assembler->Bind(&string_loop);
+    {
+      Label continue_loop(assembler);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+      Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+      assembler->GotoIf(assembler->WordIsSmi(element_k), &continue_loop);
+      assembler->GotoUnless(assembler->Int32LessThan(
+                                assembler->LoadMapInstanceType(element_k),
+                                assembler->Int32Constant(FIRST_NONSTRING_TYPE)),
+                            &continue_loop);
+
+      Callable callable = CodeFactory::StringEqual(assembler->isolate());
+      Node* result =
+          assembler->CallStub(callable, context, search_element, element_k);
+      assembler->Branch(
+          assembler->WordEqual(assembler->BooleanConstant(true), result),
+          &return_true, &continue_loop);
+
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&string_loop);
+    }
+
+    assembler->Bind(&simd_loop);
+    {
+      Label continue_loop(assembler, &k), loop_body(assembler, &k);
+      Node* map = assembler->LoadMap(search_element);
+
+      assembler->Goto(&loop_body);
+      assembler->Bind(&loop_body);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+
+      Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+      assembler->GotoIf(assembler->WordIsSmi(element_k), &continue_loop);
+
+      Node* map_k = assembler->LoadMap(element_k);
+      assembler->BranchIfSimd128Equal(search_element, map, element_k, map_k,
+                                      &return_true, &continue_loop);
+
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&loop_body);
+    }
+  }
+
+  assembler->Bind(&if_packed_doubles);
+  {
+    Label nan_loop(assembler, &k), not_nan_loop(assembler, &k),
+        hole_loop(assembler, &k);
+    assembler->GotoIf(assembler->WordIsSmi(search_element), &return_false);
+    assembler->GotoIf(assembler->WordNotEqual(
+                          assembler->LoadMap(search_element), heap_number_map),
+                      &return_false);
+
+    Node* search_num = assembler->LoadHeapNumberValue(search_element);
+
+    assembler->BranchIfFloat64IsNaN(search_num, &nan_loop, &not_nan_loop);
+
+    // Search for HeapNumber
+    assembler->Bind(&not_nan_loop);
+    {
+      Label continue_loop(assembler);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+      Node* element_k = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      assembler->BranchIfFloat64Equal(element_k, search_num, &return_true,
+                                      &continue_loop);
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&not_nan_loop);
+    }
+
+    // Search for NaN
+    assembler->Bind(&nan_loop);
+    {
+      Label continue_loop(assembler);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+      Node* element_k = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      assembler->BranchIfFloat64IsNaN(element_k, &return_true, &continue_loop);
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&nan_loop);
+    }
+  }
+
+  assembler->Bind(&if_holey_doubles);
+  {
+    Label nan_loop(assembler, &k), not_nan_loop(assembler, &k),
+        hole_loop(assembler, &k);
+    assembler->GotoIf(assembler->WordIsSmi(search_element), &return_false);
+    assembler->GotoIf(assembler->WordEqual(search_element, undefined),
+                      &hole_loop);
+    assembler->GotoIf(assembler->WordNotEqual(
+                          assembler->LoadMap(search_element), heap_number_map),
+                      &return_false);
+
+    Node* search_num = assembler->LoadHeapNumberValue(search_element);
+
+    assembler->BranchIfFloat64IsNaN(search_num, &nan_loop, &not_nan_loop);
+
+    // Search for HeapNumber
+    assembler->Bind(&not_nan_loop);
+    {
+      Label continue_loop(assembler);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+
+      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),
+                          &continue_loop);
+      } else {
+        Node* element_upper = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint32(),
+            kIeeeDoubleExponentWordOffset);
+        assembler->GotoIf(
+            assembler->Word32Equal(element_upper,
+                                   assembler->Int32Constant(kHoleNanUpper32)),
+            &continue_loop);
+      }
+
+      Node* element_k = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      assembler->BranchIfFloat64Equal(element_k, search_num, &return_true,
+                                      &continue_loop);
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&not_nan_loop);
+    }
+
+    // Search for NaN
+    assembler->Bind(&nan_loop);
+    {
+      Label continue_loop(assembler);
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+
+      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),
+                          &continue_loop);
+      } else {
+        Node* element_upper = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint32(),
+            kIeeeDoubleExponentWordOffset);
+        assembler->GotoIf(
+            assembler->Word32Equal(element_upper,
+                                   assembler->Int32Constant(kHoleNanUpper32)),
+            &continue_loop);
+      }
+
+      Node* element_k = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      assembler->BranchIfFloat64IsNaN(element_k, &return_true, &continue_loop);
+      assembler->Bind(&continue_loop);
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&nan_loop);
+    }
+
+    // Search for the Hole
+    assembler->Bind(&hole_loop);
+    {
+      assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                            &return_false);
+
+      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),
+                          &return_true);
+      } else {
+        Node* element_upper = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint32(),
+            kIeeeDoubleExponentWordOffset);
+        assembler->GotoIf(
+            assembler->Word32Equal(element_upper,
+                                   assembler->Int32Constant(kHoleNanUpper32)),
+            &return_true);
+      }
+
+      k.Bind(assembler->Int32Add(k.value(), int32_one));
+      assembler->Goto(&hole_loop);
+    }
+  }
+
+  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 6567 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