[builtins] implement Array.prototype.includes in TurboFan

src/builtins/builtins-array.cc

Index: src/builtins/builtins-array.cc
diff --git a/src/builtins/builtins-array.cc b/src/builtins/builtins-array.cc
index ba6ec24304d817abb02589f2d202846833928c31..de532c92d5d13e29cbaa227a66f4925f2615355d 100644
--- a/src/builtins/builtins-array.cc
+++ b/src/builtins/builtins-array.cc
@@ -4,6 +4,8 @@
 
 #include "src/builtins/builtins.h"
 #include "src/builtins/builtins-utils.h"
+
+#include "src/code-factory.h"
 #include "src/elements.h"
 
 namespace v8 {
@@ -1271,5 +1273,452 @@ 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);
+
+  Node* the_hole = assembler->TheHoleConstant();
+  Node* undefined = assembler->UndefinedConstant();
+  Node* heap_number_map = assembler->HeapNumberMapConstant();
+
+  Variable len(assembler, MachineRepresentation::kWord32),

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

Nit: Can you rename those to len_var, k_var and n_var? To make it more obvious
for the reader in the code below that those are variables.

+      k(assembler, MachineRepresentation::kWord32),
+      n(assembler, MachineRepresentation::kWord32);

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

pretty please: use real variable names, k = key, n = ? :)

+
+  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);

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

Nit: Move this before the { } block, and start the block with the init_len, i.e.

Label init_len(assember);
assembler->BranchIfFastJSArray(...);

assembler->Bind(&init_len);
{
  ...
}

+
+    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);

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

again, I really like having readable variable names.

+    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);

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

Instead of the abort label, go to the shared return_false.

[caitp, 2016/07/19 19:59:21]

The issue with that is that the return_false label wants `k_var` to be bound,
even though return_false doesn't use it and has no successor blocks. If there's
a way around this that I've missed, I'd love to hear it.

Otherwise, I think all I can do is branch to a label, bind `k_var` to something,
and exit to return_false

[Benedikt Meurer, 2016/07/20 03:55:01]

That seems suspicious. Maybe a bug in the CodeAssembler. Can you try to declare
the Labels first, then the Variables?

[danno, 2016/07/25 13:53:55]

I don't think this is a bug (although I haven't debugged it). The
CodeStubAssembler is pretty dumb, it only knows how to merge variables in two
situations, either at a label where you explicitly said the merge is needed, or
at a label where all paths bind the value of the variables before
forward-jumping to the label. It has no flow analysis to know that a variable
that has been defined previously will never be used again, either.

So if you jump to an label where a in-scope variable is bound on a single path,
it must be bound on every path to that variable, regardless of wether the
variable is actually used again or not. So, since k_var is declared top level,
and snakes its way through the whole routine until any possible path to abort,
if it isn't bound on every path, you will get an assert.

One possible work around: immediately after the variable declaration you can
bind it to undefined.

+      n.Bind(assembler->TruncateFloat64ToWord32(fp_n));

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

The fp_n can be outside the valid word32 range. And the TruncateFloat64ToWord32
to mod 2^32 truncation, which is probably not what you want. I.e. if fp_n is
2^32 then you bind n to 0 here.

[caitp, 2016/07/19 19:59:21]

`len` is pulled directly from kLengthOffset of JSArray (an Smi), and the above
GotoIf bails out if `double(n) >= double(len)`. Does that not mean it's safe to
truncate to 32 bits, since it must fit within an Smi range?

[Benedikt Meurer, 2016/07/20 03:55:01]

It could still be negative, i.e. -2^32. Truncating that to word32 yields 0,
which would pass the test below.

[caitp, 2016/07/20 16:07:55]

well, here's the rationale for this I came up with:

1. `fp_len <= Smi::kMaxValue` --- This is always true
2. `fp_len >= 0` --- I believe this is always true, I don't believe the length
field of a JSArray is ever set to a negative value.
3. IF `fp_n >= fp_len`, we can return false as no iteration occurs and no items
are tested
4. IF `fp_n <= -fp_len`, then `(fp_len + fp_n) <= 0`, which will always result
in binding `k` to 0 in the algorithm

So, given all of those, I _think_ it's okay to truncate. I can't come up with an
example where this does the wrong thing.

In your example, assuming `fp_len == Smi::kMaxValue` and `fp_n == -(2^32)`, fp_n
+ fp_len would be negative and should result in binding k to 0.

+      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[] = {

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

Nit: Make this static const. And rename to kElementsKind.

[caitp, 2016/07/19 19:59:21]

Acknowledged. Requires a change to the Switch() prototype though (which may not
be worth it)

[Benedikt Meurer, 2016/07/20 03:55:01]

Acknowledged.

+      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,

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

Nice idea!

+                    element_kind_handlers, arraysize(element_kinds));
+
+  assembler->Bind(&if_smiorobjects);
+  {
+    Variable search_num(assembler, MachineRepresentation::kFloat64);
+    Label ident_loop(assembler, &k), heap_num_loop(assembler, &search_num),
+        string_loop(assembler, &k), simd_loop(assembler),
+        undef_loop(assembler, &k), not_smi(assembler), not_heap_num(assembler);
+
+    assembler->GotoUnless(assembler->WordIsSmi(search_element), &not_smi);
+    search_num.Bind(assembler->SmiToFloat64(search_element));
+    assembler->Goto(&heap_num_loop);
+
+    assembler->Bind(&not_smi);
+    assembler->GotoIf(assembler->WordEqual(search_element, undefined),
+                      &undef_loop);
+    Node* map = assembler->LoadMap(search_element);
+    assembler->GotoIf(assembler->WordNotEqual(map, heap_number_map),
+                      &not_heap_num);
+    search_num.Bind(assembler->LoadHeapNumberValue(search_element));
+    assembler->Goto(&heap_num_loop);
+
+    assembler->Bind(&not_heap_num);
+    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);
+      assembler->BranchIfFloat64IsNaN(search_num.value(), &nan_loop,
+                                      &not_nan_loop);
+
+      assembler->Bind(&not_nan_loop);
+      {
+        Label continue_loop(assembler), not_smi(assembler);
+        assembler->GotoUnless(assembler->Int32LessThan(k.value(), len.value()),
+                              &return_false);
+        Node* element_k = assembler->LoadFixedArrayElement(elements, k.value());
+        assembler->GotoUnless(assembler->WordIsSmi(element_k), &not_smi);
+        assembler->Branch(
+            assembler->Float64Equal(search_num.value(),
+                                    assembler->SmiToFloat64(element_k)),
+            &return_true, &continue_loop);
+
+        assembler->Bind(&not_smi);
+        assembler->GotoIf(assembler->WordNotEqual(assembler->LoadMap(element_k),
+                                                  heap_number_map),
+                          &continue_loop);
+        assembler->BranchIfFloat64Equal(
+            search_num.value(), 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());

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

Please add a TODO here, that at some point we want to inline the String equality
comparison here.

[caitp, 2016/07/19 19:59:21]

Acknowledged.

+      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), search_notnan(assembler);
+    Variable search_num(assembler, MachineRepresentation::kFloat64);
+
+    assembler->GotoUnless(assembler->WordIsSmi(search_element), &search_notnan);
+    search_num.Bind(assembler->SmiToFloat64(search_element));
+    assembler->Goto(&not_nan_loop);
+
+    assembler->Bind(&search_notnan);
+    assembler->GotoIf(assembler->WordNotEqual(
+                          assembler->LoadMap(search_element), heap_number_map),
+                      &return_false);
+
+    search_num.Bind(assembler->LoadHeapNumberValue(search_element));
+
+    assembler->BranchIfFloat64IsNaN(search_num.value(), &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.value(),
+                                      &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), search_notnan(assembler);
+    Variable search_num(assembler, MachineRepresentation::kFloat64);
+
+    assembler->GotoUnless(assembler->WordIsSmi(search_element), &search_notnan);
+    search_num.Bind(assembler->SmiToFloat64(search_element));
+    assembler->Goto(&not_nan_loop);
+
+    assembler->Bind(&search_notnan);
+    assembler->GotoIf(assembler->WordEqual(search_element, undefined),
+                      &hole_loop);
+    assembler->GotoIf(assembler->WordNotEqual(
+                          assembler->LoadMap(search_element), heap_number_map),
+                      &return_false);
+
+    search_num.Bind(assembler->LoadHeapNumberValue(search_element));
+
+    assembler->BranchIfFloat64IsNaN(search_num.value(), &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) {

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

You don't need this distinction. You can always compare just the upper bits. Or
even load the double and then extract the high word using
Float64ExtractHighWord32.

[caitp, 2016/07/19 19:59:21]

Acknowledged. This pattern is used elsewhere though (mainly
CodeStubAssembler::TryLookupElement)

[Benedikt Meurer, 2016/07/20 03:55:01]

Hm, ok, we could also simplify that.

+        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.value(),
+                                      &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) {

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

See above.

+        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));
+}
+
 }  // namespace internal
 }  // namespace v8