[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..f34faaac151a71e3b63f4bb867fdfe6aed05f4fb 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -343,6 +343,120 @@ 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);
+  {
+    Label done(assembler), if_neg(assembler), init_k_smi(assembler),
+        init_k_zero(assembler);
+    Callable call_to_integer = CodeFactory::ToInteger(assembler->isolate());
+    Node* tagged_n = assembler->CallStub(call_to_integer, context, start_from);
+
+    assembler->GotoIf(assembler->Float64Equal(

[caitp, 2016/07/14 18:01:18]

This init_k block is based on the understanding that Smis are the maximum length
of JSArrays, and they can hold 29/30 bit signed integers (bit count might be off
a bit) --- I __think__ this means any non-+Infinity HeapNumber at this point
should result in setting `k` to 0 (per spec), but I'm not positive.

I think it's possible to observe getting this wrong if indexed getters are
installed on Array.prototype. I have some doubts about the way this is being
done here, but I'm not sure what's the right way to go.

+                          tagged_n, assembler->Float64Constant(V8_INFINITY)),
+                      &return_false);
+
+    assembler->GotoUnless(assembler->WordIsSmi(tagged_n), &init_k_zero);
+
+    n.Bind(assembler->SmiToWord32(tagged_n));
+
+    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()),
+                          &return_false);
+
+    Callable call_get_property = CodeFactory::GetProperty(assembler->isolate());
+    Node* element_k = assembler->CallStub(call_get_property, context, array,
+                                          assembler->SmiFromWord32(k.value()));
+
+    Callable call_same_value_zero =
+        CodeFactory::SameValueZero(assembler->isolate());
+    Node* result = assembler->CallStub(call_same_value_zero, context,
+                                       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;