Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(64)

Unified Diff: src/builtins/builtins-array.cc

Issue 2232063002: [builtins] WIP: Array indexOf in TurboFan/Runtime (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: Move fast path FastElements -> FastSmiOrObjectElements Created 4 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/builtins/builtins.h ('k') | src/elements.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/builtins/builtins-array.cc
diff --git a/src/builtins/builtins-array.cc b/src/builtins/builtins-array.cc
index 479d08c583f4a302daa262290c4ae8fdcbe87e84..09ee4cc2e2d741cd1fc22f0187552fa189cb7cd6 100644
--- a/src/builtins/builtins-array.cc
+++ b/src/builtins/builtins-array.cc
@@ -1739,5 +1739,381 @@ void Builtins::Generate_ArrayIncludes(CodeStubAssembler* assembler) {
start_from));
}
+void Builtins::Generate_ArrayIndexOf(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* undefined = assembler->UndefinedConstant();
+ Node* heap_number_map = assembler->HeapNumberMapConstant();
+
+ Variable len_var(assembler, MachineRepresentation::kWord32),
+ index_var(assembler, MachineRepresentation::kWord32),
+ start_from_var(assembler, MachineRepresentation::kWord32);
+
+ Label init_k(assembler), return_found(assembler), return_not_found(assembler),
+ call_runtime(assembler);
+
+ Label init_len(assembler);
+
+ index_var.Bind(int32_zero);
+ len_var.Bind(int32_zero);
+
+ // Take slow path if not a JSArray, if retrieving elements requires
+ // traversing prototype, or if access checks are required.
+ assembler->BranchIfFastJSArray(array, context, &init_len, &call_runtime);
+
+ assembler->Bind(&init_len);
+ {
+ // Handle case where JSArray length is not an Smi in the runtime
+ Node* len = assembler->LoadObjectField(array, JSArray::kLengthOffset);
+ assembler->GotoUnless(assembler->WordIsSmi(len), &call_runtime);
+
+ len_var.Bind(assembler->SmiToWord(len));
+ assembler->Branch(assembler->Word32Equal(len_var.value(), int32_zero),
+ &return_not_found, &init_k);
+ }
+
+ 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);
+ {
+ start_from_var.Bind(assembler->SmiToWord32(tagged_n));
+ assembler->Goto(&init_k_n);
+ }
+
+ assembler->Bind(&init_k_heap_num);
+ {
+ Label do_return_not_found(assembler);
+ Node* fp_len = assembler->ChangeInt32ToFloat64(len_var.value());
+ Node* fp_n = assembler->LoadHeapNumberValue(tagged_n);
+ assembler->GotoIf(assembler->Float64GreaterThanOrEqual(fp_n, fp_len),
+ &do_return_not_found);
+ start_from_var.Bind(assembler->TruncateFloat64ToWord32(fp_n));
+ assembler->Goto(&init_k_n);
+
+ assembler->Bind(&do_return_not_found);
+ {
+ index_var.Bind(int32_zero);
+ assembler->Goto(&return_not_found);
+ }
+ }
+
+ assembler->Bind(&init_k_n);
+ {
+ Label if_positive(assembler), if_negative(assembler), done(assembler);
+ assembler->Branch(
+ assembler->Int32LessThan(start_from_var.value(), int32_zero),
+ &if_negative, &if_positive);
+
+ assembler->Bind(&if_positive);
+ {
+ index_var.Bind(start_from_var.value());
+ assembler->Goto(&done);
+ }
+
+ assembler->Bind(&if_negative);
+ {
+ index_var.Bind(
+ assembler->Int32Add(len_var.value(), start_from_var.value()));
+ assembler->Branch(
+ assembler->Int32LessThan(index_var.value(), int32_zero),
+ &init_k_zero, &done);
+ }
+
+ assembler->Bind(&init_k_zero);
+ {
+ index_var.Bind(int32_zero);
+ assembler->Goto(&done);
+ }
+
+ assembler->Bind(&done);
+ }
+ }
+
+ static int32_t kElementsKind[] = {
+ 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_not_found, kElementsKind,
+ element_kind_handlers, arraysize(kElementsKind));
+
+ assembler->Bind(&if_smiorobjects);
+ {
+ Variable search_num(assembler, MachineRepresentation::kFloat64);
+ Label ident_loop(assembler, &index_var),
+ heap_num_loop(assembler, &search_num),
+ string_loop(assembler, &index_var), simd_loop(assembler),
+ undef_loop(assembler, &index_var), 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(index_var.value(), len_var.value()),
+ &return_not_found);
+ Node* element_k =
+ assembler->LoadFixedArrayElement(elements, index_var.value());
+ assembler->GotoIf(assembler->WordEqual(element_k, search_element),
+ &return_found);
+
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&ident_loop);
+ }
+
+ assembler->Bind(&undef_loop);
+ {
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+ Node* element_k =
+ assembler->LoadFixedArrayElement(elements, index_var.value());
+ assembler->GotoIf(assembler->WordEqual(element_k, undefined),
+ &return_found);
+
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&undef_loop);
+ }
+
+ assembler->Bind(&heap_num_loop);
+ {
+ Label not_nan_loop(assembler, &index_var);
+ assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
+ &not_nan_loop);
+
+ assembler->Bind(&not_nan_loop);
+ {
+ Label continue_loop(assembler), not_smi(assembler);
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+ Node* element_k =
+ assembler->LoadFixedArrayElement(elements, index_var.value());
+ assembler->GotoUnless(assembler->WordIsSmi(element_k), &not_smi);
+ assembler->Branch(
+ assembler->Float64Equal(search_num.value(),
+ assembler->SmiToFloat64(element_k)),
+ &return_found, &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_found, &continue_loop);
+
+ assembler->Bind(&continue_loop);
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&not_nan_loop);
+ }
+ }
+
+ assembler->Bind(&string_loop);
+ {
+ Label continue_loop(assembler);
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+ Node* element_k =
+ assembler->LoadFixedArrayElement(elements, index_var.value());
+ assembler->GotoIf(assembler->WordIsSmi(element_k), &continue_loop);
+ assembler->GotoUnless(assembler->Int32LessThan(
+ assembler->LoadInstanceType(element_k),
+ assembler->Int32Constant(FIRST_NONSTRING_TYPE)),
+ &continue_loop);
+
+ // TODO(bmeurer): Consider inlining the StringEqual logic here.
+ 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_found, &continue_loop);
+
+ assembler->Bind(&continue_loop);
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&string_loop);
+ }
+
+ assembler->Bind(&simd_loop);
+ {
+ Label continue_loop(assembler, &index_var),
+ loop_body(assembler, &index_var);
+ Node* map = assembler->LoadMap(search_element);
+
+ assembler->Goto(&loop_body);
+ assembler->Bind(&loop_body);
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+
+ Node* element_k =
+ assembler->LoadFixedArrayElement(elements, index_var.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_found, &continue_loop);
+
+ assembler->Bind(&continue_loop);
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&loop_body);
+ }
+ }
+
+ assembler->Bind(&if_packed_doubles);
+ {
+ Label not_nan_loop(assembler, &index_var), 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_not_found);
+
+ search_num.Bind(assembler->LoadHeapNumberValue(search_element));
+
+ assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
+ &not_nan_loop);
+
+ // Search for HeapNumber
+ assembler->Bind(&not_nan_loop);
+ {
+ Label continue_loop(assembler);
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+ Node* element_k = assembler->LoadFixedDoubleArrayElement(
+ elements, index_var.value(), MachineType::Float64());
+ assembler->BranchIfFloat64Equal(element_k, search_num.value(),
+ &return_found, &continue_loop);
+ assembler->Bind(&continue_loop);
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&not_nan_loop);
+ }
+ }
+
+ assembler->Bind(&if_holey_doubles);
+ {
+ Label not_nan_loop(assembler, &index_var), 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_not_found);
+
+ search_num.Bind(assembler->LoadHeapNumberValue(search_element));
+
+ assembler->BranchIfFloat64IsNaN(search_num.value(), &return_not_found,
+ &not_nan_loop);
+
+ // Search for HeapNumber
+ assembler->Bind(&not_nan_loop);
+ {
+ Label continue_loop(assembler);
+ assembler->GotoUnless(
+ assembler->Int32LessThan(index_var.value(), len_var.value()),
+ &return_not_found);
+
+ if (kPointerSize == kDoubleSize) {
+ Node* element = assembler->LoadFixedDoubleArrayElement(
+ elements, index_var.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, index_var.value(), MachineType::Uint32(),
+ kIeeeDoubleExponentWordOffset);
+ assembler->GotoIf(
+ assembler->Word32Equal(element_upper,
+ assembler->Int32Constant(kHoleNanUpper32)),
+ &continue_loop);
+ }
+
+ Node* element_k = assembler->LoadFixedDoubleArrayElement(
+ elements, index_var.value(), MachineType::Float64());
+ assembler->BranchIfFloat64Equal(element_k, search_num.value(),
+ &return_found, &continue_loop);
+ assembler->Bind(&continue_loop);
+ index_var.Bind(assembler->Int32Add(index_var.value(), int32_one));
+ assembler->Goto(&not_nan_loop);
+ }
+ }
+
+ assembler->Bind(&return_found);
+ assembler->Return(assembler->ChangeInt32ToTagged(index_var.value()));
+
+ assembler->Bind(&return_not_found);
+ assembler->Return(assembler->NumberConstant(-1));
+
+ assembler->Bind(&call_runtime);
+ assembler->Return(assembler->CallRuntime(Runtime::kArrayIndexOf, context,
+ array, search_element, start_from));
+}
+
} // namespace internal
} // namespace v8
« no previous file with comments | « src/builtins/builtins.h ('k') | src/elements.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698