[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..9a31adcc1d1fb6bebcc7ba8467a284ef3f067b23 100644
--- a/src/builtins/builtins.cc
+++ b/src/builtins/builtins.cc
@@ -343,6 +343,220 @@ 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->DebugBreak();
+    assembler->GotoIf(
+        assembler->Int32GreaterThan(
+            elements_kind, assembler->Int32Constant(LAST_FAST_ELEMENTS_KIND)),
+        &call_runtime);
+
+    // 3. Bailout to slow path if array protector field invalid
+    assembler->GotoUnless(
+        assembler->WordEqual(
+            assembler->LoadObjectField(
+                assembler->LoadRoot(Heap::kArrayProtectorRootIndex),
+                PropertyCell::kValueOffset),
+            assembler->SmiConstant(
+                Smi::FromInt(Isolate::kArrayProtectorValid))),
+        &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));
+
+    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
+    Variable element_k(assembler, MachineRepresentation::kTagged);
+    Variable stable(assembler, MachineRepresentation::kWord32);
+
+    Variable* loop_body_variables[] = {&k, &stable};
+
+    Label loop_body(assembler, 2,
+                    static_cast<Variable **>(loop_body_variables)),
+        continue_loop(assembler), if_issmiorobject(assembler),
+        if_isdouble(assembler), if_slowpath(assembler), test_element(assembler);
+
+    stable.Bind(int32_one);
+    Node* map = assembler->LoadMap(array);
+    Node* bit_field2 = assembler->LoadMapBitField2(map);
+    Node* elements_kind =
+        assembler->BitFieldDecode<Map::ElementsKindBits>(bit_field2);
+
+    assembler->Goto(&loop_body);
+    assembler->Bind(&loop_body);
+
+    assembler->GotoUnless(assembler->Uint32LessThan(k.value(), len.value()),
+                          &return_false);
+
+    assembler->GotoIf(assembler->WordEqual(stable.value(), int32_zero),
+                      &if_slowpath);
+
+    assembler->Branch(
+        assembler->Int32LessThan(
+            elements_kind, assembler->Int32Constant(FAST_DOUBLE_ELEMENTS)),
+        &if_issmiorobject, &if_isdouble);
+
+    assembler->Bind(&if_issmiorobject);
+    {  // Fast Smi/Object elements
+      Node* elements = assembler->LoadElements(array);
+      Node* length = assembler->LoadFixedArrayBaseLength(elements);
+
+      assembler->GotoUnless(
+          assembler->Int32LessThan(k.value(), assembler->SmiToWord32(length)),
+          &if_slowpath);
+
+      Node* element = assembler->LoadFixedArrayElement(elements, k.value());
+      Node* the_hole = assembler->TheHoleConstant();
+
+      assembler->GotoUnless(assembler->WordNotEqual(element, the_hole),
+                            &if_slowpath);
+      element_k.Bind(element);
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&if_isdouble);
+    {  // Fast double elements
+      Node* elements = assembler->LoadElements(array);
+      Node* length = assembler->LoadFixedArrayBaseLength(elements);
+
+      assembler->GotoUnless(
+          assembler->Int32LessThan(k.value(), assembler->SmiToWord32(length)),
+          &if_slowpath);
+
+      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),
+                          &if_slowpath);
+      } else {
+        Node* element_upper = assembler->LoadFixedDoubleArrayElement(
+            elements, k.value(), MachineType::Uint32(),
+            kIeeeDoubleExponentWordOffset);
+        assembler->GotoIf(
+            assembler->Word32Equal(element_upper,
+                                   assembler->Int32Constant(kHoleNanUpper32)),
+            &if_slowpath);
+      }
+
+      Node* element = assembler->LoadFixedDoubleArrayElement(
+          elements, k.value(), MachineType::Float64());
+      element_k.Bind(assembler->AllocateHeapNumberWithValue(element));
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&if_slowpath);
+    {
+      Node* element =
+          assembler->CallRuntime(Runtime::kGetProperty, context, array,
+                                 assembler->SmiFromWord32(k.value()));
+      element_k.Bind(element);
+
+      // Slow path may have modified elements backing store in some way.
+      assembler->GotoIf(assembler->WordEqual(stable.value(), int32_zero),
+                        &test_element);
+      Node* current_map = assembler->LoadMap(array);
+      assembler->GotoIf(assembler->WordEqual(map, current_map), &test_element);
+      stable.Bind(int32_zero);
+      assembler->Goto(&test_element);
+    }
+
+    assembler->Bind(&test_element);
+    assembler->BranchIfSameValueZero(search_element, element_k.value(), context,
+                                     &return_true, &continue_loop);
+
+    assembler->Bind(&continue_loop);
+    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;