diff options
Diffstat (limited to 'deps/v8/src/builtins/builtins-string-gen.cc')
| -rw-r--r-- | deps/v8/src/builtins/builtins-string-gen.cc | 889 |
1 files changed, 530 insertions, 359 deletions
diff --git a/deps/v8/src/builtins/builtins-string-gen.cc b/deps/v8/src/builtins/builtins-string-gen.cc index ed559eadfd..ee85476401 100644 --- a/deps/v8/src/builtins/builtins-string-gen.cc +++ b/deps/v8/src/builtins/builtins-string-gen.cc @@ -2,149 +2,167 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include "src/builtins/builtins-string-gen.h" + #include "src/builtins/builtins-regexp-gen.h" #include "src/builtins/builtins-utils-gen.h" #include "src/builtins/builtins.h" #include "src/code-factory.h" -#include "src/code-stub-assembler.h" #include "src/objects.h" namespace v8 { namespace internal { typedef CodeStubAssembler::RelationalComparisonMode RelationalComparisonMode; +typedef compiler::Node Node; + +Node* StringBuiltinsAssembler::DirectStringData(Node* string, + Node* string_instance_type) { + // Compute the effective offset of the first character. + VARIABLE(var_data, MachineType::PointerRepresentation()); + Label if_sequential(this), if_external(this), if_join(this); + Branch(Word32Equal(Word32And(string_instance_type, + Int32Constant(kStringRepresentationMask)), + Int32Constant(kSeqStringTag)), + &if_sequential, &if_external); + + BIND(&if_sequential); + { + var_data.Bind(IntPtrAdd( + IntPtrConstant(SeqOneByteString::kHeaderSize - kHeapObjectTag), + BitcastTaggedToWord(string))); + Goto(&if_join); + } -class StringBuiltinsAssembler : public CodeStubAssembler { - public: - explicit StringBuiltinsAssembler(compiler::CodeAssemblerState* state) - : CodeStubAssembler(state) {} + BIND(&if_external); + { + // This is only valid for ExternalStrings where the resource data + // pointer is cached (i.e. no short external strings). + CSA_ASSERT( + this, Word32NotEqual(Word32And(string_instance_type, + Int32Constant(kShortExternalStringMask)), + Int32Constant(kShortExternalStringTag))); + var_data.Bind(LoadObjectField(string, ExternalString::kResourceDataOffset, + MachineType::Pointer())); + Goto(&if_join); + } - protected: - Node* DirectStringData(Node* string, Node* string_instance_type) { - // Compute the effective offset of the first character. - VARIABLE(var_data, MachineType::PointerRepresentation()); - Label if_sequential(this), if_external(this), if_join(this); - Branch(Word32Equal(Word32And(string_instance_type, - Int32Constant(kStringRepresentationMask)), - Int32Constant(kSeqStringTag)), - &if_sequential, &if_external); - - BIND(&if_sequential); - { - var_data.Bind(IntPtrAdd( - IntPtrConstant(SeqOneByteString::kHeaderSize - kHeapObjectTag), - BitcastTaggedToWord(string))); - Goto(&if_join); - } + BIND(&if_join); + return var_data.value(); +} - BIND(&if_external); - { - // This is only valid for ExternalStrings where the resource data - // pointer is cached (i.e. no short external strings). - CSA_ASSERT(this, Word32NotEqual( - Word32And(string_instance_type, - Int32Constant(kShortExternalStringMask)), - Int32Constant(kShortExternalStringTag))); - var_data.Bind(LoadObjectField(string, ExternalString::kResourceDataOffset, - MachineType::Pointer())); - Goto(&if_join); - } +void StringBuiltinsAssembler::DispatchOnStringEncodings( + Node* const lhs_instance_type, Node* const rhs_instance_type, + Label* if_one_one, Label* if_one_two, Label* if_two_one, + Label* if_two_two) { + STATIC_ASSERT(kStringEncodingMask == 0x8); + STATIC_ASSERT(kTwoByteStringTag == 0x0); + STATIC_ASSERT(kOneByteStringTag == 0x8); - BIND(&if_join); - return var_data.value(); - } + // First combine the encodings. - Node* LoadOneByteChar(Node* string, Node* index) { - return Load(MachineType::Uint8(), string, OneByteCharOffset(index)); - } + Node* const encoding_mask = Int32Constant(kStringEncodingMask); + Node* const lhs_encoding = Word32And(lhs_instance_type, encoding_mask); + Node* const rhs_encoding = Word32And(rhs_instance_type, encoding_mask); - Node* OneByteCharAddress(Node* string, Node* index) { - Node* offset = OneByteCharOffset(index); - return IntPtrAdd(string, offset); - } + Node* const combined_encodings = + Word32Or(lhs_encoding, Word32Shr(rhs_encoding, 1)); - Node* OneByteCharOffset(Node* index) { - return CharOffset(String::ONE_BYTE_ENCODING, index); - } + // Then dispatch on the combined encoding. - Node* CharOffset(String::Encoding encoding, Node* index) { - const int header = SeqOneByteString::kHeaderSize - kHeapObjectTag; - Node* offset = index; - if (encoding == String::TWO_BYTE_ENCODING) { - offset = IntPtrAdd(offset, offset); - } - offset = IntPtrAdd(offset, IntPtrConstant(header)); - return offset; - } + Label unreachable(this, Label::kDeferred); - void DispatchOnStringInstanceType(Node* const instance_type, - Label* if_onebyte_sequential, - Label* if_onebyte_external, - Label* if_otherwise) { - const int kMask = kStringRepresentationMask | kStringEncodingMask; - Node* const encoding_and_representation = - Word32And(instance_type, Int32Constant(kMask)); - - int32_t values[] = { - kOneByteStringTag | kSeqStringTag, - kOneByteStringTag | kExternalStringTag, - }; - Label* labels[] = { - if_onebyte_sequential, if_onebyte_external, - }; - STATIC_ASSERT(arraysize(values) == arraysize(labels)); - - Switch(encoding_and_representation, if_otherwise, values, labels, - arraysize(values)); - } + int32_t values[] = { + kOneByteStringTag | (kOneByteStringTag >> 1), + kOneByteStringTag | (kTwoByteStringTag >> 1), + kTwoByteStringTag | (kOneByteStringTag >> 1), + kTwoByteStringTag | (kTwoByteStringTag >> 1), + }; + Label* labels[] = { + if_one_one, if_one_two, if_two_one, if_two_two, + }; - void GenerateStringEqual(Node* context, Node* left, Node* right); - void GenerateStringRelationalComparison(Node* context, Node* left, - Node* right, - RelationalComparisonMode mode); + STATIC_ASSERT(arraysize(values) == arraysize(labels)); + Switch(combined_encodings, &unreachable, values, labels, arraysize(values)); - Node* ToSmiBetweenZeroAnd(Node* context, Node* value, Node* limit); + BIND(&unreachable); + Unreachable(); +} + +template <typename SubjectChar, typename PatternChar> +Node* StringBuiltinsAssembler::CallSearchStringRaw(Node* const subject_ptr, + Node* const subject_length, + Node* const search_ptr, + Node* const search_length, + Node* const start_position) { + Node* const function_addr = ExternalConstant( + ExternalReference::search_string_raw<SubjectChar, PatternChar>( + isolate())); + Node* const isolate_ptr = + ExternalConstant(ExternalReference::isolate_address(isolate())); + + MachineType type_ptr = MachineType::Pointer(); + MachineType type_intptr = MachineType::IntPtr(); + + Node* const result = CallCFunction6( + type_intptr, type_ptr, type_ptr, type_intptr, type_ptr, type_intptr, + type_intptr, function_addr, isolate_ptr, subject_ptr, subject_length, + search_ptr, search_length, start_position); + + return result; +} - Node* LoadSurrogatePairAt(Node* string, Node* length, Node* index, - UnicodeEncoding encoding); +Node* StringBuiltinsAssembler::PointerToStringDataAtIndex( + Node* const string_data, Node* const index, String::Encoding encoding) { + const ElementsKind kind = (encoding == String::ONE_BYTE_ENCODING) + ? UINT8_ELEMENTS + : UINT16_ELEMENTS; + Node* const offset_in_bytes = + ElementOffsetFromIndex(index, kind, INTPTR_PARAMETERS); + return IntPtrAdd(string_data, offset_in_bytes); +} - void StringIndexOf(Node* receiver, Node* instance_type, Node* search_string, - Node* search_string_instance_type, Node* position, - std::function<void(Node*)> f_return); +void StringBuiltinsAssembler::ConvertAndBoundsCheckStartArgument( + Node* context, Variable* var_start, Node* start, Node* string_length) { + Node* const start_int = + ToInteger(context, start, CodeStubAssembler::kTruncateMinusZero); + Node* const zero = SmiConstant(Smi::kZero); - Node* IsNullOrUndefined(Node* const value); - void RequireObjectCoercible(Node* const context, Node* const value, - const char* method_name); + Label done(this); + Label if_issmi(this), if_isheapnumber(this, Label::kDeferred); + Branch(TaggedIsSmi(start_int), &if_issmi, &if_isheapnumber); - Node* SmiIsNegative(Node* const value) { - return SmiLessThan(value, SmiConstant(0)); + BIND(&if_issmi); + { + var_start->Bind( + Select(SmiLessThan(start_int, zero), + [&] { return SmiMax(SmiAdd(string_length, start_int), zero); }, + [&] { return start_int; }, MachineRepresentation::kTagged)); + Goto(&done); } - // Implements boilerplate logic for {match, split, replace, search} of the - // form: - // - // if (!IS_NULL_OR_UNDEFINED(object)) { - // var maybe_function = object[symbol]; - // if (!IS_UNDEFINED(maybe_function)) { - // return %_Call(maybe_function, ...); - // } - // } - // - // Contains fast paths for Smi and RegExp objects. - typedef std::function<Node*()> NodeFunction0; - typedef std::function<Node*(Node* fn)> NodeFunction1; - void MaybeCallFunctionAtSymbol(Node* const context, Node* const object, - Handle<Symbol> symbol, - const NodeFunction0& regexp_call, - const NodeFunction1& generic_call); -}; + BIND(&if_isheapnumber); + { + // If {start} is a heap number, it is definitely out of bounds. If it is + // negative, {start} = max({string_length} + {start}),0) = 0'. If it is + // positive, set {start} to {string_length} which ultimately results in + // returning an empty string. + Node* const float_zero = Float64Constant(0.); + Node* const start_float = LoadHeapNumberValue(start_int); + var_start->Bind(SelectTaggedConstant( + Float64LessThan(start_float, float_zero), zero, string_length)); + Goto(&done); + } + BIND(&done); +} void StringBuiltinsAssembler::GenerateStringEqual(Node* context, Node* left, Node* right) { // Here's pseudo-code for the algorithm below: // - // if (lhs == rhs) return true; // if (lhs->length() != rhs->length()) return false; + // restart: + // if (lhs == rhs) return true; // if (lhs->IsInternalizedString() && rhs->IsInternalizedString()) { // return false; // } @@ -155,33 +173,61 @@ void StringBuiltinsAssembler::GenerateStringEqual(Node* context, Node* left, // return true; // } // if (lhs and/or rhs are indirect strings) { - // unwrap them and restart from the beginning; + // unwrap them and restart from the "restart:" label; // } // return %StringEqual(lhs, rhs); VARIABLE(var_left, MachineRepresentation::kTagged, left); VARIABLE(var_right, MachineRepresentation::kTagged, right); - Variable* input_vars[2] = {&var_left, &var_right}; - Label if_equal(this), if_notequal(this), restart(this, 2, input_vars); + Label if_equal(this), if_notequal(this), if_notbothdirectonebytestrings(this), + restart(this, 2, input_vars); + + Node* lhs_length = LoadStringLength(left); + Node* rhs_length = LoadStringLength(right); + + // Strings with different lengths cannot be equal. + GotoIf(WordNotEqual(lhs_length, rhs_length), &if_notequal); + Goto(&restart); BIND(&restart); Node* lhs = var_left.value(); Node* rhs = var_right.value(); - // Fast check to see if {lhs} and {rhs} refer to the same String object. - GotoIf(WordEqual(lhs, rhs), &if_equal); + Node* lhs_instance_type = LoadInstanceType(lhs); + Node* rhs_instance_type = LoadInstanceType(rhs); - // Load the length of {lhs} and {rhs}. - Node* lhs_length = LoadStringLength(lhs); - Node* rhs_length = LoadStringLength(rhs); + StringEqual_Core(context, lhs, lhs_instance_type, lhs_length, rhs, + rhs_instance_type, &if_equal, &if_notequal, + &if_notbothdirectonebytestrings); - // Strings with different lengths cannot be equal. - GotoIf(WordNotEqual(lhs_length, rhs_length), &if_notequal); + BIND(&if_notbothdirectonebytestrings); + { + // Try to unwrap indirect strings, restart the above attempt on success. + MaybeDerefIndirectStrings(&var_left, lhs_instance_type, &var_right, + rhs_instance_type, &restart); + // TODO(bmeurer): Add support for two byte string equality checks. - // Load instance types of {lhs} and {rhs}. - Node* lhs_instance_type = LoadInstanceType(lhs); - Node* rhs_instance_type = LoadInstanceType(rhs); + TailCallRuntime(Runtime::kStringEqual, context, lhs, rhs); + } + + BIND(&if_equal); + Return(TrueConstant()); + + BIND(&if_notequal); + Return(FalseConstant()); +} + +void StringBuiltinsAssembler::StringEqual_Core( + Node* context, Node* lhs, Node* lhs_instance_type, Node* lhs_length, + Node* rhs, Node* rhs_instance_type, Label* if_equal, Label* if_not_equal, + Label* if_notbothdirectonebyte) { + CSA_ASSERT(this, IsString(lhs)); + CSA_ASSERT(this, IsString(rhs)); + CSA_ASSERT(this, WordEqual(LoadStringLength(lhs), lhs_length)); + CSA_ASSERT(this, WordEqual(LoadStringLength(rhs), lhs_length)); + // Fast check to see if {lhs} and {rhs} refer to the same String object. + GotoIf(WordEqual(lhs, rhs), if_equal); // Combine the instance types into a single 16-bit value, so we can check // both of them at once. @@ -196,7 +242,7 @@ void StringBuiltinsAssembler::GenerateStringEqual(Node* context, Node* left, GotoIf(Word32Equal(Word32And(both_instance_types, Int32Constant(kBothInternalizedMask)), Int32Constant(kBothInternalizedTag)), - &if_notequal); + if_not_equal); // Check that both {lhs} and {rhs} are flat one-byte strings, and that // in case of ExternalStrings the data pointer is cached.. @@ -207,61 +253,43 @@ void StringBuiltinsAssembler::GenerateStringEqual(Node* context, Node* left, << 8); int const kBothDirectOneByteStringTag = kOneByteStringTag | (kOneByteStringTag << 8); - Label if_bothdirectonebytestrings(this), if_notbothdirectonebytestrings(this); - Branch(Word32Equal(Word32And(both_instance_types, - Int32Constant(kBothDirectOneByteStringMask)), - Int32Constant(kBothDirectOneByteStringTag)), - &if_bothdirectonebytestrings, &if_notbothdirectonebytestrings); - - BIND(&if_bothdirectonebytestrings); + GotoIfNot(Word32Equal(Word32And(both_instance_types, + Int32Constant(kBothDirectOneByteStringMask)), + Int32Constant(kBothDirectOneByteStringTag)), + if_notbothdirectonebyte); + + // At this point we know that we have two direct one-byte strings. + + // Compute the effective offset of the first character. + Node* lhs_data = DirectStringData(lhs, lhs_instance_type); + Node* rhs_data = DirectStringData(rhs, rhs_instance_type); + + // Compute the first offset after the string from the length. + Node* length = SmiUntag(lhs_length); + + // Loop over the {lhs} and {rhs} strings to see if they are equal. + VARIABLE(var_offset, MachineType::PointerRepresentation()); + Label loop(this, &var_offset); + var_offset.Bind(IntPtrConstant(0)); + Goto(&loop); + BIND(&loop); { - // Compute the effective offset of the first character. - Node* lhs_data = DirectStringData(lhs, lhs_instance_type); - Node* rhs_data = DirectStringData(rhs, rhs_instance_type); + // If {offset} equals {end}, no difference was found, so the + // strings are equal. + Node* offset = var_offset.value(); + GotoIf(WordEqual(offset, length), if_equal); - // Compute the first offset after the string from the length. - Node* length = SmiUntag(lhs_length); - - // Loop over the {lhs} and {rhs} strings to see if they are equal. - VARIABLE(var_offset, MachineType::PointerRepresentation()); - Label loop(this, &var_offset); - var_offset.Bind(IntPtrConstant(0)); - Goto(&loop); - BIND(&loop); - { - // If {offset} equals {end}, no difference was found, so the - // strings are equal. - Node* offset = var_offset.value(); - GotoIf(WordEqual(offset, length), &if_equal); - - // Load the next characters from {lhs} and {rhs}. - Node* lhs_value = Load(MachineType::Uint8(), lhs_data, offset); - Node* rhs_value = Load(MachineType::Uint8(), rhs_data, offset); - - // Check if the characters match. - GotoIf(Word32NotEqual(lhs_value, rhs_value), &if_notequal); - - // Advance to next character. - var_offset.Bind(IntPtrAdd(offset, IntPtrConstant(1))); - Goto(&loop); - } - } + // Load the next characters from {lhs} and {rhs}. + Node* lhs_value = Load(MachineType::Uint8(), lhs_data, offset); + Node* rhs_value = Load(MachineType::Uint8(), rhs_data, offset); - BIND(&if_notbothdirectonebytestrings); - { - // Try to unwrap indirect strings, restart the above attempt on success. - MaybeDerefIndirectStrings(&var_left, lhs_instance_type, &var_right, - rhs_instance_type, &restart); - // TODO(bmeurer): Add support for two byte string equality checks. + // Check if the characters match. + GotoIf(Word32NotEqual(lhs_value, rhs_value), if_not_equal); - TailCallRuntime(Runtime::kStringEqual, context, lhs, rhs); + // Advance to next character. + var_offset.Bind(IntPtrAdd(offset, IntPtrConstant(1))); + Goto(&loop); } - - BIND(&if_equal); - Return(TrueConstant()); - - BIND(&if_notequal); - Return(FalseConstant()); } void StringBuiltinsAssembler::GenerateStringRelationalComparison( @@ -697,7 +725,7 @@ TF_BUILTIN(StringPrototypeConcat, CodeStubAssembler) { arguments.ForEach( CodeStubAssembler::VariableList({&var_result}, zone()), [this, context, &var_result](Node* arg) { - arg = CallStub(CodeFactory::ToString(isolate()), context, arg); + arg = ToString_Inline(context, arg); var_result.Bind(CallStub(CodeFactory::StringAdd(isolate()), context, var_result.value(), arg)); }); @@ -705,103 +733,148 @@ TF_BUILTIN(StringPrototypeConcat, CodeStubAssembler) { } void StringBuiltinsAssembler::StringIndexOf( - Node* receiver, Node* instance_type, Node* search_string, - Node* search_string_instance_type, Node* position, - std::function<void(Node*)> f_return) { - CSA_ASSERT(this, IsString(receiver)); + Node* const subject_string, Node* const subject_instance_type, + Node* const search_string, Node* const search_instance_type, + Node* const position, std::function<void(Node*)> f_return) { + CSA_ASSERT(this, IsString(subject_string)); CSA_ASSERT(this, IsString(search_string)); CSA_ASSERT(this, TaggedIsSmi(position)); - Label zero_length_needle(this), - call_runtime_unchecked(this, Label::kDeferred), return_minus_1(this), - check_search_string(this), continue_fast_path(this); - Node* const int_zero = IntPtrConstant(0); + VARIABLE(var_needle_byte, MachineType::PointerRepresentation(), int_zero); VARIABLE(var_string_addr, MachineType::PointerRepresentation(), int_zero); - Node* needle_length = SmiUntag(LoadStringLength(search_string)); - // Use faster/complex runtime fallback for long search strings. - GotoIf(IntPtrLessThan(IntPtrConstant(1), needle_length), - &call_runtime_unchecked); - Node* string_length = SmiUntag(LoadStringLength(receiver)); - Node* start_position = IntPtrMax(SmiUntag(position), int_zero); + Node* const search_length = SmiUntag(LoadStringLength(search_string)); + Node* const subject_length = SmiUntag(LoadStringLength(subject_string)); + Node* const start_position = IntPtrMax(SmiUntag(position), int_zero); - GotoIf(IntPtrEqual(int_zero, needle_length), &zero_length_needle); - // Check that the needle fits in the start position. - GotoIfNot(IntPtrLessThanOrEqual(needle_length, - IntPtrSub(string_length, start_position)), - &return_minus_1); - - // Load the string address. + Label zero_length_needle(this), return_minus_1(this); { - Label if_onebyte_sequential(this); - Label if_onebyte_external(this, Label::kDeferred); + GotoIf(IntPtrEqual(int_zero, search_length), &zero_length_needle); - // Only support one-byte strings on the fast path. - DispatchOnStringInstanceType(instance_type, &if_onebyte_sequential, - &if_onebyte_external, &call_runtime_unchecked); + // Check that the needle fits in the start position. + GotoIfNot(IntPtrLessThanOrEqual(search_length, + IntPtrSub(subject_length, start_position)), + &return_minus_1); + } - BIND(&if_onebyte_sequential); - { - var_string_addr.Bind( - OneByteCharAddress(BitcastTaggedToWord(receiver), start_position)); - Goto(&check_search_string); - } + // Try to unpack subject and search strings. Bail to runtime if either needs + // to be flattened. + ToDirectStringAssembler subject_to_direct(state(), subject_string); + ToDirectStringAssembler search_to_direct(state(), search_string); - BIND(&if_onebyte_external); - { - Node* const unpacked = TryDerefExternalString(receiver, instance_type, - &call_runtime_unchecked); - var_string_addr.Bind(OneByteCharAddress(unpacked, start_position)); - Goto(&check_search_string); - } - } + Label call_runtime_unchecked(this, Label::kDeferred); - // Load the needle character. - BIND(&check_search_string); - { - Label if_onebyte_sequential(this); - Label if_onebyte_external(this, Label::kDeferred); + subject_to_direct.TryToDirect(&call_runtime_unchecked); + search_to_direct.TryToDirect(&call_runtime_unchecked); + + // Load pointers to string data. + Node* const subject_ptr = + subject_to_direct.PointerToData(&call_runtime_unchecked); + Node* const search_ptr = + search_to_direct.PointerToData(&call_runtime_unchecked); + + Node* const subject_offset = subject_to_direct.offset(); + Node* const search_offset = search_to_direct.offset(); + + // Like String::IndexOf, the actual matching is done by the optimized + // SearchString method in string-search.h. Dispatch based on string instance + // types, then call straight into C++ for matching. - DispatchOnStringInstanceType(search_string_instance_type, - &if_onebyte_sequential, &if_onebyte_external, - &call_runtime_unchecked); + CSA_ASSERT(this, IntPtrGreaterThan(search_length, int_zero)); + CSA_ASSERT(this, IntPtrGreaterThanOrEqual(start_position, int_zero)); + CSA_ASSERT(this, IntPtrGreaterThanOrEqual(subject_length, start_position)); + CSA_ASSERT(this, + IntPtrLessThanOrEqual(search_length, + IntPtrSub(subject_length, start_position))); - BIND(&if_onebyte_sequential); + Label one_one(this), one_two(this), two_one(this), two_two(this); + DispatchOnStringEncodings(subject_to_direct.instance_type(), + search_to_direct.instance_type(), &one_one, + &one_two, &two_one, &two_two); + + typedef const uint8_t onebyte_t; + typedef const uc16 twobyte_t; + + BIND(&one_one); + { + Node* const adjusted_subject_ptr = PointerToStringDataAtIndex( + subject_ptr, subject_offset, String::ONE_BYTE_ENCODING); + Node* const adjusted_search_ptr = PointerToStringDataAtIndex( + search_ptr, search_offset, String::ONE_BYTE_ENCODING); + + Label direct_memchr_call(this), generic_fast_path(this); + Branch(IntPtrEqual(search_length, IntPtrConstant(1)), &direct_memchr_call, + &generic_fast_path); + + // An additional fast path that calls directly into memchr for 1-length + // search strings. + BIND(&direct_memchr_call); { - var_needle_byte.Bind( - ChangeInt32ToIntPtr(LoadOneByteChar(search_string, int_zero))); - Goto(&continue_fast_path); + Node* const string_addr = IntPtrAdd(adjusted_subject_ptr, start_position); + Node* const search_length = IntPtrSub(subject_length, start_position); + Node* const search_byte = + ChangeInt32ToIntPtr(Load(MachineType::Uint8(), adjusted_search_ptr)); + + Node* const memchr = + ExternalConstant(ExternalReference::libc_memchr_function(isolate())); + Node* const result_address = + CallCFunction3(MachineType::Pointer(), MachineType::Pointer(), + MachineType::IntPtr(), MachineType::UintPtr(), memchr, + string_addr, search_byte, search_length); + GotoIf(WordEqual(result_address, int_zero), &return_minus_1); + Node* const result_index = + IntPtrAdd(IntPtrSub(result_address, string_addr), start_position); + f_return(SmiTag(result_index)); } - BIND(&if_onebyte_external); + BIND(&generic_fast_path); { - Node* const unpacked = TryDerefExternalString( - search_string, search_string_instance_type, &call_runtime_unchecked); - var_needle_byte.Bind( - ChangeInt32ToIntPtr(LoadOneByteChar(unpacked, int_zero))); - Goto(&continue_fast_path); + Node* const result = CallSearchStringRaw<onebyte_t, onebyte_t>( + adjusted_subject_ptr, subject_length, adjusted_search_ptr, + search_length, start_position); + f_return(SmiTag(result)); } } - BIND(&continue_fast_path); + BIND(&one_two); + { + Node* const adjusted_subject_ptr = PointerToStringDataAtIndex( + subject_ptr, subject_offset, String::ONE_BYTE_ENCODING); + Node* const adjusted_search_ptr = PointerToStringDataAtIndex( + search_ptr, search_offset, String::TWO_BYTE_ENCODING); + + Node* const result = CallSearchStringRaw<onebyte_t, twobyte_t>( + adjusted_subject_ptr, subject_length, adjusted_search_ptr, + search_length, start_position); + f_return(SmiTag(result)); + } + + BIND(&two_one); + { + Node* const adjusted_subject_ptr = PointerToStringDataAtIndex( + subject_ptr, subject_offset, String::TWO_BYTE_ENCODING); + Node* const adjusted_search_ptr = PointerToStringDataAtIndex( + search_ptr, search_offset, String::ONE_BYTE_ENCODING); + + Node* const result = CallSearchStringRaw<twobyte_t, onebyte_t>( + adjusted_subject_ptr, subject_length, adjusted_search_ptr, + search_length, start_position); + f_return(SmiTag(result)); + } + + BIND(&two_two); { - Node* needle_byte = var_needle_byte.value(); - Node* string_addr = var_string_addr.value(); - Node* search_length = IntPtrSub(string_length, start_position); - // Call out to the highly optimized memchr to perform the actual byte - // search. - Node* memchr = - ExternalConstant(ExternalReference::libc_memchr_function(isolate())); - Node* result_address = - CallCFunction3(MachineType::Pointer(), MachineType::Pointer(), - MachineType::IntPtr(), MachineType::UintPtr(), memchr, - string_addr, needle_byte, search_length); - GotoIf(WordEqual(result_address, int_zero), &return_minus_1); - Node* result_index = - IntPtrAdd(IntPtrSub(result_address, string_addr), start_position); - f_return(SmiTag(result_index)); + Node* const adjusted_subject_ptr = PointerToStringDataAtIndex( + subject_ptr, subject_offset, String::TWO_BYTE_ENCODING); + Node* const adjusted_search_ptr = PointerToStringDataAtIndex( + search_ptr, search_offset, String::TWO_BYTE_ENCODING); + + Node* const result = CallSearchStringRaw<twobyte_t, twobyte_t>( + adjusted_subject_ptr, subject_length, adjusted_search_ptr, + search_length, start_position); + f_return(SmiTag(result)); } BIND(&return_minus_1); @@ -810,7 +883,7 @@ void StringBuiltinsAssembler::StringIndexOf( BIND(&zero_length_needle); { Comment("0-length search_string"); - f_return(SmiTag(IntPtrMin(string_length, start_position))); + f_return(SmiTag(IntPtrMin(subject_length, start_position))); } BIND(&call_runtime_unchecked); @@ -819,7 +892,7 @@ void StringBuiltinsAssembler::StringIndexOf( // are already known due to type checks in this stub. Comment("Call Runtime Unchecked"); Node* result = CallRuntime(Runtime::kStringIndexOfUnchecked, SmiConstant(0), - receiver, search_string, position); + subject_string, search_string, position); f_return(result); } } @@ -979,18 +1052,78 @@ void StringBuiltinsAssembler::MaybeCallFunctionAtSymbol( GotoIf(IsNullOrUndefined(object), &out); // Fall back to a slow lookup of {object[symbol]}. + // + // The spec uses GetMethod({object}, {symbol}), which has a few quirks: + // * null values are turned into undefined, and + // * an exception is thrown if the value is not undefined, null, or callable. + // We handle the former by jumping to {out} for null values as well, while + // the latter is already handled by the Call({maybe_func}) operation. Node* const maybe_func = GetProperty(context, object, symbol); GotoIf(IsUndefined(maybe_func), &out); + GotoIf(IsNull(maybe_func), &out); // Attempt to call the function. - Node* const result = generic_call(maybe_func); Return(result); BIND(&out); } +compiler::Node* StringBuiltinsAssembler::IndexOfDollarChar(Node* const context, + Node* const string) { + CSA_ASSERT(this, IsString(string)); + + Node* const dollar_string = HeapConstant( + isolate()->factory()->LookupSingleCharacterStringFromCode('$')); + Node* const dollar_ix = CallBuiltin(Builtins::kStringIndexOf, context, string, + dollar_string, SmiConstant(0)); + + CSA_ASSERT(this, TaggedIsSmi(dollar_ix)); + return dollar_ix; +} + +compiler::Node* StringBuiltinsAssembler::GetSubstitution( + Node* context, Node* subject_string, Node* match_start_index, + Node* match_end_index, Node* replace_string) { + CSA_ASSERT(this, IsString(subject_string)); + CSA_ASSERT(this, IsString(replace_string)); + CSA_ASSERT(this, TaggedIsPositiveSmi(match_start_index)); + CSA_ASSERT(this, TaggedIsPositiveSmi(match_end_index)); + + VARIABLE(var_result, MachineRepresentation::kTagged, replace_string); + Label runtime(this), out(this); + + // In this primitive implementation we simply look for the next '$' char in + // {replace_string}. If it doesn't exist, we can simply return + // {replace_string} itself. If it does, then we delegate to + // String::GetSubstitution, passing in the index of the first '$' to avoid + // repeated scanning work. + // TODO(jgruber): Possibly extend this in the future to handle more complex + // cases without runtime calls. + + Node* const dollar_index = IndexOfDollarChar(context, replace_string); + Branch(SmiIsNegative(dollar_index), &out, &runtime); + + BIND(&runtime); + { + CSA_ASSERT(this, TaggedIsPositiveSmi(dollar_index)); + + Callable substring_callable = CodeFactory::SubString(isolate()); + Node* const matched = CallStub(substring_callable, context, subject_string, + match_start_index, match_end_index); + Node* const replacement_string = + CallRuntime(Runtime::kGetSubstitution, context, matched, subject_string, + match_start_index, replace_string, dollar_index); + var_result.Bind(replacement_string); + + Goto(&out); + } + + BIND(&out); + return var_result.value(); +} + // ES6 #sec-string.prototype.replace TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { Label out(this); @@ -1009,9 +1142,7 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { MaybeCallFunctionAtSymbol( context, search, isolate()->factory()->replace_symbol(), [=]() { - Callable tostring_callable = CodeFactory::ToString(isolate()); - Node* const subject_string = - CallStub(tostring_callable, context, receiver); + Node* const subject_string = ToString_Inline(context, receiver); Callable replace_callable = CodeFactory::RegExpReplace(isolate()); return CallStub(replace_callable, context, search, subject_string, @@ -1024,16 +1155,15 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { // Convert {receiver} and {search} to strings. - Callable tostring_callable = CodeFactory::ToString(isolate()); Callable indexof_callable = CodeFactory::StringIndexOf(isolate()); - Node* const subject_string = CallStub(tostring_callable, context, receiver); - Node* const search_string = CallStub(tostring_callable, context, search); + Node* const subject_string = ToString_Inline(context, receiver); + Node* const search_string = ToString_Inline(context, search); Node* const subject_length = LoadStringLength(subject_string); Node* const search_length = LoadStringLength(search_string); - // Fast-path single-char {search}, long {receiver}, and simple string + // Fast-path single-char {search}, long cons {receiver}, and simple string // {replace}. { Label next(this); @@ -1043,11 +1173,10 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { GotoIf(TaggedIsSmi(replace), &next); GotoIfNot(IsString(replace), &next); - Node* const dollar_string = HeapConstant( - isolate()->factory()->LookupSingleCharacterStringFromCode('$')); - Node* const dollar_ix = - CallStub(indexof_callable, context, replace, dollar_string, smi_zero); - GotoIfNot(SmiIsNegative(dollar_ix), &next); + Node* const subject_instance_type = LoadInstanceType(subject_string); + GotoIfNot(IsConsStringInstanceType(subject_instance_type), &next); + + GotoIf(TaggedIsPositiveSmi(IndexOfDollarChar(context, replace)), &next); // Searching by traversing a cons string tree and replace with cons of // slices works only when the replaced string is a single character, being @@ -1083,7 +1212,7 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { // TODO(jgruber): Could introduce ToStringSideeffectsStub which only // performs observable parts of ToString. - CallStub(tostring_callable, context, replace); + ToString_Inline(context, replace); Goto(&return_subject); BIND(&return_subject); @@ -1126,8 +1255,7 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { Node* const replacement = CallJS(call_callable, context, replace, UndefinedConstant(), search_string, match_start_index, subject_string); - Node* const replacement_string = - CallStub(tostring_callable, context, replacement); + Node* const replacement_string = ToString_Inline(context, replacement); var_result.Bind(CallStub(stringadd_callable, context, var_result.value(), replacement_string)); Goto(&out); @@ -1135,16 +1263,12 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { BIND(&if_notcallablereplace); { - Node* const replace_string = CallStub(tostring_callable, context, replace); - - // TODO(jgruber): Simplified GetSubstitution implementation in CSA. - Node* const matched = CallStub(substring_callable, context, subject_string, - match_start_index, match_end_index); - Node* const replacement_string = - CallRuntime(Runtime::kGetSubstitution, context, matched, subject_string, - match_start_index, replace_string); - var_result.Bind(CallStub(stringadd_callable, context, var_result.value(), - replacement_string)); + Node* const replace_string = ToString_Inline(context, replace); + Node* const replacement = + GetSubstitution(context, subject_string, match_start_index, + match_end_index, replace_string); + var_result.Bind( + CallStub(stringadd_callable, context, var_result.value(), replacement)); Goto(&out); } @@ -1158,6 +1282,89 @@ TF_BUILTIN(StringPrototypeReplace, StringBuiltinsAssembler) { } } +// ES6 section 21.1.3.18 String.prototype.slice ( start, end ) +TF_BUILTIN(StringPrototypeSlice, StringBuiltinsAssembler) { + Label out(this); + VARIABLE(var_start, MachineRepresentation::kTagged); + VARIABLE(var_end, MachineRepresentation::kTagged); + + const int kStart = 0; + const int kEnd = 1; + Node* argc = + ChangeInt32ToIntPtr(Parameter(BuiltinDescriptor::kArgumentsCount)); + CodeStubArguments args(this, argc); + Node* const receiver = args.GetReceiver(); + Node* const start = + args.GetOptionalArgumentValue(kStart, UndefinedConstant()); + Node* const end = args.GetOptionalArgumentValue(kEnd, UndefinedConstant()); + Node* const context = Parameter(BuiltinDescriptor::kContext); + + Node* const smi_zero = SmiConstant(0); + + // 1. Let O be ? RequireObjectCoercible(this value). + RequireObjectCoercible(context, receiver, "String.prototype.slice"); + + // 2. Let S be ? ToString(O). + Callable tostring_callable = CodeFactory::ToString(isolate()); + Node* const subject_string = CallStub(tostring_callable, context, receiver); + + // 3. Let len be the number of elements in S. + Node* const length = LoadStringLength(subject_string); + + // Conversions and bounds-checks for {start}. + ConvertAndBoundsCheckStartArgument(context, &var_start, start, length); + + // 5. If end is undefined, let intEnd be len; + var_end.Bind(length); + GotoIf(WordEqual(end, UndefinedConstant()), &out); + + // else let intEnd be ? ToInteger(end). + Node* const end_int = + ToInteger(context, end, CodeStubAssembler::kTruncateMinusZero); + + // 7. If intEnd < 0, let to be max(len + intEnd, 0); + // otherwise let to be min(intEnd, len). + Label if_issmi(this), if_isheapnumber(this, Label::kDeferred); + Branch(TaggedIsSmi(end_int), &if_issmi, &if_isheapnumber); + + BIND(&if_issmi); + { + Node* const length_plus_end = SmiAdd(length, end_int); + var_end.Bind(Select(SmiLessThan(end_int, smi_zero), + [&] { return SmiMax(length_plus_end, smi_zero); }, + [&] { return SmiMin(length, end_int); }, + MachineRepresentation::kTagged)); + Goto(&out); + } + + BIND(&if_isheapnumber); + { + // If {end} is a heap number, it is definitely out of bounds. If it is + // negative, {int_end} = max({length} + {int_end}),0) = 0'. If it is + // positive, set {int_end} to {length} which ultimately results in + // returning an empty string. + Node* const float_zero = Float64Constant(0.); + Node* const end_float = LoadHeapNumberValue(end_int); + var_end.Bind(SelectTaggedConstant(Float64LessThan(end_float, float_zero), + smi_zero, length)); + Goto(&out); + } + + Label return_emptystring(this); + BIND(&out); + { + GotoIf(SmiLessThanOrEqual(var_end.value(), var_start.value()), + &return_emptystring); + Node* const result = + SubString(context, subject_string, var_start.value(), var_end.value(), + SubStringFlags::FROM_TO_ARE_BOUNDED); + args.PopAndReturn(result); + } + + BIND(&return_emptystring); + args.PopAndReturn(EmptyStringConstant()); +} + // ES6 section 21.1.3.19 String.prototype.split ( separator, limit ) TF_BUILTIN(StringPrototypeSplit, StringBuiltinsAssembler) { Label out(this); @@ -1176,9 +1383,7 @@ TF_BUILTIN(StringPrototypeSplit, StringBuiltinsAssembler) { MaybeCallFunctionAtSymbol( context, separator, isolate()->factory()->split_symbol(), [=]() { - Callable tostring_callable = CodeFactory::ToString(isolate()); - Node* const subject_string = - CallStub(tostring_callable, context, receiver); + Node* const subject_string = ToString_Inline(context, receiver); Callable split_callable = CodeFactory::RegExpSplit(isolate()); return CallStub(split_callable, context, separator, subject_string, @@ -1191,14 +1396,12 @@ TF_BUILTIN(StringPrototypeSplit, StringBuiltinsAssembler) { // String and integer conversions. - Callable tostring_callable = CodeFactory::ToString(isolate()); - Node* const subject_string = CallStub(tostring_callable, context, receiver); + Node* const subject_string = ToString_Inline(context, receiver); Node* const limit_number = Select(IsUndefined(limit), [=]() { return NumberConstant(kMaxUInt32); }, [=]() { return ToUint32(context, limit); }, MachineRepresentation::kTagged); - Node* const separator_string = - CallStub(tostring_callable, context, separator); + Node* const separator_string = ToString_Inline(context, separator); // Shortcut for {limit} == 0. { @@ -1259,8 +1462,8 @@ TF_BUILTIN(StringPrototypeSplit, StringBuiltinsAssembler) { } // ES6 #sec-string.prototype.substr -TF_BUILTIN(StringPrototypeSubstr, CodeStubAssembler) { - Label out(this), handle_length(this); +TF_BUILTIN(StringPrototypeSubstr, StringBuiltinsAssembler) { + Label out(this); VARIABLE(var_start, MachineRepresentation::kTagged); VARIABLE(var_length, MachineRepresentation::kTagged); @@ -1279,94 +1482,62 @@ TF_BUILTIN(StringPrototypeSubstr, CodeStubAssembler) { Node* const string_length = LoadStringLength(string); // Conversions and bounds-checks for {start}. - { - Node* const start_int = - ToInteger(context, start, CodeStubAssembler::kTruncateMinusZero); - - Label if_issmi(this), if_isheapnumber(this, Label::kDeferred); - Branch(TaggedIsSmi(start_int), &if_issmi, &if_isheapnumber); - - BIND(&if_issmi); - { - Node* const length_plus_start = SmiAdd(string_length, start_int); - var_start.Bind(Select(SmiLessThan(start_int, zero), - [&] { return SmiMax(length_plus_start, zero); }, - [&] { return start_int; }, - MachineRepresentation::kTagged)); - Goto(&handle_length); - } - - BIND(&if_isheapnumber); - { - // If {start} is a heap number, it is definitely out of bounds. If it is - // negative, {start} = max({string_length} + {start}),0) = 0'. If it is - // positive, set {start} to {string_length} which ultimately results in - // returning an empty string. - Node* const float_zero = Float64Constant(0.); - Node* const start_float = LoadHeapNumberValue(start_int); - var_start.Bind(SelectTaggedConstant( - Float64LessThan(start_float, float_zero), zero, string_length)); - Goto(&handle_length); - } - } + ConvertAndBoundsCheckStartArgument(context, &var_start, start, string_length); // Conversions and bounds-checks for {length}. - BIND(&handle_length); + Label if_issmi(this), if_isheapnumber(this, Label::kDeferred); + + // Default to {string_length} if {length} is undefined. { - Label if_issmi(this), if_isheapnumber(this, Label::kDeferred); + Label if_isundefined(this, Label::kDeferred), if_isnotundefined(this); + Branch(WordEqual(length, UndefinedConstant()), &if_isundefined, + &if_isnotundefined); - // Default to {string_length} if {length} is undefined. - { - Label if_isundefined(this, Label::kDeferred), if_isnotundefined(this); - Branch(WordEqual(length, UndefinedConstant()), &if_isundefined, - &if_isnotundefined); + BIND(&if_isundefined); + var_length.Bind(string_length); + Goto(&if_issmi); - BIND(&if_isundefined); - var_length.Bind(string_length); - Goto(&if_issmi); + BIND(&if_isnotundefined); + var_length.Bind( + ToInteger(context, length, CodeStubAssembler::kTruncateMinusZero)); + } - BIND(&if_isnotundefined); - var_length.Bind( - ToInteger(context, length, CodeStubAssembler::kTruncateMinusZero)); - } + Branch(TaggedIsSmi(var_length.value()), &if_issmi, &if_isheapnumber); - Branch(TaggedIsSmi(var_length.value()), &if_issmi, &if_isheapnumber); + // Set {length} to min(max({length}, 0), {string_length} - {start} + BIND(&if_issmi); + { + Node* const positive_length = SmiMax(var_length.value(), zero); - // Set {length} to min(max({length}, 0), {string_length} - {start} - BIND(&if_issmi); - { - Node* const positive_length = SmiMax(var_length.value(), zero); + Node* const minimal_length = SmiSub(string_length, var_start.value()); + var_length.Bind(SmiMin(positive_length, minimal_length)); - Node* const minimal_length = SmiSub(string_length, var_start.value()); - var_length.Bind(SmiMin(positive_length, minimal_length)); + GotoIfNot(SmiLessThanOrEqual(var_length.value(), zero), &out); + Return(EmptyStringConstant()); + } - GotoIfNot(SmiLessThanOrEqual(var_length.value(), zero), &out); - Return(EmptyStringConstant()); - } + BIND(&if_isheapnumber); + { + // If {length} is a heap number, it is definitely out of bounds. There are + // two cases according to the spec: if it is negative, "" is returned; if + // it is positive, then length is set to {string_length} - {start}. - BIND(&if_isheapnumber); - { - // If {length} is a heap number, it is definitely out of bounds. There are - // two cases according to the spec: if it is negative, "" is returned; if - // it is positive, then length is set to {string_length} - {start}. + CSA_ASSERT(this, IsHeapNumberMap(LoadMap(var_length.value()))); - CSA_ASSERT(this, IsHeapNumberMap(LoadMap(var_length.value()))); + Label if_isnegative(this), if_ispositive(this); + Node* const float_zero = Float64Constant(0.); + Node* const length_float = LoadHeapNumberValue(var_length.value()); + Branch(Float64LessThan(length_float, float_zero), &if_isnegative, + &if_ispositive); - Label if_isnegative(this), if_ispositive(this); - Node* const float_zero = Float64Constant(0.); - Node* const length_float = LoadHeapNumberValue(var_length.value()); - Branch(Float64LessThan(length_float, float_zero), &if_isnegative, - &if_ispositive); + BIND(&if_isnegative); + Return(EmptyStringConstant()); - BIND(&if_isnegative); + BIND(&if_ispositive); + { + var_length.Bind(SmiSub(string_length, var_start.value())); + GotoIfNot(SmiLessThanOrEqual(var_length.value(), zero), &out); Return(EmptyStringConstant()); - - BIND(&if_ispositive); - { - var_length.Bind(SmiSub(string_length, var_start.value())); - GotoIfNot(SmiLessThanOrEqual(var_length.value(), zero), &out); - Return(EmptyStringConstant()); - } } } |