From 91cfb3730a7634b7d4070cb66756ee99e0da9f2b Mon Sep 17 00:00:00 2001 From: "sgjesse@chromium.org" Date: Fri, 8 Jan 2010 11:58:15 +0000 Subject: [PATCH] Add generated code for ascii string comparison Careted a stub for string comparison and used part of the code from that to inline string comparison in the compare stub. Review URL: http://codereview.chromium.org/525115 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@3569 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/arm/codegen-arm.cc | 11 +++ src/arm/codegen-arm.h | 3 + src/code-stubs.h | 1 + src/codegen.cc | 1 + src/ia32/assembler-ia32.cc | 20 +++++ src/ia32/assembler-ia32.h | 6 +- src/ia32/codegen-ia32.cc | 193 ++++++++++++++++++++++++++++++++++++++++++++- src/ia32/codegen-ia32.h | 28 +++++++ src/runtime.cc | 3 + src/runtime.js | 4 +- src/v8-counters.h | 2 + src/x64/codegen-x64.cc | 11 +++ src/x64/codegen-x64.h | 3 + 13 files changed, 281 insertions(+), 5 deletions(-) diff --git a/src/arm/codegen-arm.cc b/src/arm/codegen-arm.cc index 20ccff8..6c64148 100644 --- a/src/arm/codegen-arm.cc +++ b/src/arm/codegen-arm.cc @@ -3464,6 +3464,17 @@ void CodeGenerator::GenerateSubString(ZoneList* args) { } +void CodeGenerator::GenerateStringCompare(ZoneList* args) { + ASSERT_EQ(2, args->length()); + + Load(args->at(0)); + Load(args->at(1)); + + frame_->CallRuntime(Runtime::kStringCompare, 2); + frame_->EmitPush(r0); +} + + void CodeGenerator::GenerateRegExpExec(ZoneList* args) { ASSERT_EQ(4, args->length()); diff --git a/src/arm/codegen-arm.h b/src/arm/codegen-arm.h index 4281aa3..0b8d67a 100644 --- a/src/arm/codegen-arm.h +++ b/src/arm/codegen-arm.h @@ -366,6 +366,9 @@ class CodeGenerator: public AstVisitor { // Fast support for SubString. void GenerateSubString(ZoneList* args); + // Fast support for StringCompare. + void GenerateStringCompare(ZoneList* args); + // Support for direct calls from JavaScript to native RegExp code. void GenerateRegExpExec(ZoneList* args); diff --git a/src/code-stubs.h b/src/code-stubs.h index fc8b0fb..052c1ca 100644 --- a/src/code-stubs.h +++ b/src/code-stubs.h @@ -38,6 +38,7 @@ namespace internal { V(GenericBinaryOp) \ V(StringAdd) \ V(SubString) \ + V(StringCompare) \ V(SmiOp) \ V(Compare) \ V(RecordWrite) \ diff --git a/src/codegen.cc b/src/codegen.cc index a61aea0..fd7e0e8 100644 --- a/src/codegen.cc +++ b/src/codegen.cc @@ -346,6 +346,7 @@ CodeGenerator::InlineRuntimeLUT CodeGenerator::kInlineRuntimeLUT[] = { {&CodeGenerator::GenerateIsFunction, "_IsFunction"}, {&CodeGenerator::GenerateStringAdd, "_StringAdd"}, {&CodeGenerator::GenerateSubString, "_SubString"}, + {&CodeGenerator::GenerateStringCompare, "_StringCompare"}, {&CodeGenerator::GenerateRegExpExec, "_RegExpExec"}, }; diff --git a/src/ia32/assembler-ia32.cc b/src/ia32/assembler-ia32.cc index b42c859..c6f4c1d 100644 --- a/src/ia32/assembler-ia32.cc +++ b/src/ia32/assembler-ia32.cc @@ -1207,6 +1207,14 @@ void Assembler::sub(Register dst, const Operand& src) { } +void Assembler::subb(Register dst, const Operand& src) { + EnsureSpace ensure_space(this); + last_pc_ = pc_; + EMIT(0x2A); + emit_operand(dst, src); +} + + void Assembler::sub(const Operand& dst, Register src) { EnsureSpace ensure_space(this); last_pc_ = pc_; @@ -1592,6 +1600,18 @@ void Assembler::j(Condition cc, Handle code, Hint hint) { } +void Assembler::loope(Label* L) { + EnsureSpace ensure_space(this); + last_pc_ = pc_; + // Only short backward jumps. + ASSERT(L->is_bound()); + int offs = L->pos() - pc_offset(); + const int kLoopInstructionSize = 2; + ASSERT(is_int8(offs - kLoopInstructionSize)); + EMIT(0xE1); + EMIT((offs - kLoopInstructionSize) & 0xFF); +} + // FPU instructions diff --git a/src/ia32/assembler-ia32.h b/src/ia32/assembler-ia32.h index ef3d9f5..738b8b6 100644 --- a/src/ia32/assembler-ia32.h +++ b/src/ia32/assembler-ia32.h @@ -540,7 +540,7 @@ class Assembler : public Malloced { void cmov(Condition cc, Register dst, Handle handle); void cmov(Condition cc, Register dst, const Operand& src); - // Repetitive moves. + // Repetitive string instructions. void rep_movs(); // Exchange two registers @@ -617,6 +617,7 @@ class Assembler : public Malloced { void shr_cl(Register dst); void subb(const Operand& dst, int8_t imm8); + void subb(Register dst, const Operand& src); void sub(const Operand& dst, const Immediate& x); void sub(Register dst, const Operand& src); void sub(const Operand& dst, Register src); @@ -675,6 +676,9 @@ class Assembler : public Malloced { void j(Condition cc, byte* entry, RelocInfo::Mode rmode, Hint hint = no_hint); void j(Condition cc, Handle code, Hint hint = no_hint); + // Loop instruction using ecx as counter. + void loope(Label* L); + // Floating-point operations void fld(int i); diff --git a/src/ia32/codegen-ia32.cc b/src/ia32/codegen-ia32.cc index f03a2c0..b1e8501 100644 --- a/src/ia32/codegen-ia32.cc +++ b/src/ia32/codegen-ia32.cc @@ -5447,6 +5447,18 @@ void CodeGenerator::GenerateSubString(ZoneList* args) { } +void CodeGenerator::GenerateStringCompare(ZoneList* args) { + ASSERT_EQ(2, args->length()); + + Load(args->at(0)); + Load(args->at(1)); + + StringCompareStub stub; + Result answer = frame_->CallStub(&stub, 2); + frame_->Push(&answer); +} + + void CodeGenerator::GenerateRegExpExec(ZoneList* args) { ASSERT_EQ(args->length(), 4); @@ -8562,9 +8574,10 @@ void CompareStub::Generate(MacroAssembler* masm) { // Fast negative check for symbol-to-symbol equality. __ bind(&check_for_symbols); + Label check_for_strings; if (cc_ == equal) { - BranchIfNonSymbol(masm, &call_builtin, eax, ecx); - BranchIfNonSymbol(masm, &call_builtin, edx, ecx); + BranchIfNonSymbol(masm, &check_for_strings, eax, ecx); + BranchIfNonSymbol(masm, &check_for_strings, edx, ecx); // We've already checked for object identity, so if both operands // are symbols they aren't equal. Register eax already holds a @@ -8572,6 +8585,44 @@ void CompareStub::Generate(MacroAssembler* masm) { __ ret(2 * kPointerSize); } + __ bind(&check_for_strings); + + // Check that both objects are not smis. + ASSERT_EQ(0, kSmiTag); + __ mov(ebx, Operand(edx)); + __ and_(ebx, Operand(eax)); + __ test(ebx, Immediate(kSmiTagMask)); + __ j(zero, &call_builtin); + + // Load instance type for both objects. + __ mov(ecx, FieldOperand(edx, HeapObject::kMapOffset)); + __ mov(ebx, FieldOperand(eax, HeapObject::kMapOffset)); + __ movzx_b(ecx, FieldOperand(ecx, Map::kInstanceTypeOffset)); + __ movzx_b(ebx, FieldOperand(ebx, Map::kInstanceTypeOffset)); + + // Check that both are flat ascii strings. + Label non_ascii_flat; + ASSERT(kNotStringTag != 0); + const int kFlatAsciiString = + kIsNotStringMask | kStringRepresentationMask | kStringEncodingMask; + __ and_(ecx, kFlatAsciiString); + __ cmp(ecx, kStringTag | kSeqStringTag | kAsciiStringTag); + __ j(not_equal, &call_builtin); + __ and_(ebx, kFlatAsciiString); + __ cmp(ebx, kStringTag | kSeqStringTag | kAsciiStringTag); + __ j(not_equal, &call_builtin); + + // Inline comparison of ascii strings. + StringCompareStub::GenerateCompareFlatAsciiStrings(masm, + edx, + eax, + ecx, + ebx, + edi); +#ifdef DEBUG + __ Abort("Unexpected fall-through from string comparison"); +#endif + __ bind(&call_builtin); // must swap argument order __ pop(ecx); @@ -9579,6 +9630,144 @@ void SubStringStub::Generate(MacroAssembler* masm) { __ TailCallRuntime(ExternalReference(Runtime::kSubString), 3, 1); } + +void StringCompareStub::GenerateCompareFlatAsciiStrings(MacroAssembler* masm, + Register left, + Register right, + Register counter, + Register scratch1, + Register scratch2) { + ASSERT(counter.is(ecx)); + Label compare_lengths, compare_lengths_1; + + // Find minimum length. If either length is zero just compare lengths. + __ mov(counter, FieldOperand(left, String::kLengthOffset)); + __ test(counter, Operand(counter)); + __ j(zero, &compare_lengths_1); + __ mov(scratch1, FieldOperand(right, String::kLengthOffset)); + __ test(scratch1, Operand(scratch1)); + __ j(zero, &compare_lengths_1); + __ cmp(counter, Operand(scratch1)); + if (CpuFeatures::IsSupported(CMOV)) { + CpuFeatures::Scope use_cmov(CMOV); + __ cmov(less, counter, Operand(scratch1)); + } else { + Label l; + __ j(less, &l); + __ mov(counter, scratch1); + __ bind(&l); + } + + Label result_greater, result_less; + Label loop; + // Compare next character. + __ mov(scratch2, Immediate(-1)); // Index into strings. + __ bind(&loop); + // Compare characters. + __ add(Operand(scratch2), Immediate(1)); + __ mov_b(scratch1, Operand(left, + scratch2, + times_1, + SeqAsciiString::kHeaderSize - kHeapObjectTag)); + __ subb(scratch1, Operand(right, + scratch2, + times_1, + SeqAsciiString::kHeaderSize - kHeapObjectTag)); + __ loope(&loop); + // If min length characters match compare lengths otherwise last character + // compare is the result. + __ j(equal, &compare_lengths); + __ j(less, &result_less); + __ jmp(&result_greater); + + // Compare lengths. + Label result_not_equal; + __ bind(&compare_lengths); + __ mov(counter, FieldOperand(left, String::kLengthOffset)); + __ bind(&compare_lengths_1); + __ sub(counter, FieldOperand(right, String::kLengthOffset)); + __ j(not_zero, &result_not_equal); + + // Result is EQUAL. + ASSERT_EQ(0, EQUAL); + ASSERT_EQ(0, kSmiTag); + __ xor_(eax, Operand(eax)); + __ IncrementCounter(&Counters::string_compare_native, 1); + __ ret(2 * kPointerSize); + __ bind(&result_not_equal); + __ j(greater, &result_greater); + + // Result is LESS. + __ bind(&result_less); + __ mov(eax, Immediate(Smi::FromInt(LESS)->value())); + __ IncrementCounter(&Counters::string_compare_native, 1); + __ ret(2 * kPointerSize); + + // Result is GREATER. + __ bind(&result_greater); + __ mov(eax, Immediate(Smi::FromInt(GREATER)->value())); + __ IncrementCounter(&Counters::string_compare_native, 1); + __ ret(2 * kPointerSize); +} + + +void StringCompareStub::Generate(MacroAssembler* masm) { + Label runtime; + + // Stack frame on entry. + // esp[0]: return address + // esp[4]: right string + // esp[8]: left string + + __ mov(edx, Operand(esp, 2 * kPointerSize)); // left + __ mov(eax, Operand(esp, 1 * kPointerSize)); // right + + Label not_same; + __ cmp(edx, Operand(eax)); + __ j(not_equal, ¬_same); + ASSERT_EQ(0, EQUAL); + ASSERT_EQ(0, kSmiTag); + __ xor_(eax, Operand(eax)); + __ IncrementCounter(&Counters::string_compare_native, 1); + __ ret(2 * kPointerSize); + + __ bind(¬_same); + + // Check that both objects are not smis. + ASSERT_EQ(0, kSmiTag); + __ mov(ebx, Operand(edx)); + __ and_(ebx, Operand(eax)); + __ test(ebx, Immediate(kSmiTagMask)); + __ j(zero, &runtime); + + // Load instance type for both strings. + __ mov(ecx, FieldOperand(edx, HeapObject::kMapOffset)); + __ mov(ebx, FieldOperand(eax, HeapObject::kMapOffset)); + __ movzx_b(ecx, FieldOperand(ecx, Map::kInstanceTypeOffset)); + __ movzx_b(ebx, FieldOperand(ebx, Map::kInstanceTypeOffset)); + + // Check that both are flat ascii strings. + Label non_ascii_flat; + __ and_(ecx, kStringRepresentationMask | kStringEncodingMask); + __ cmp(ecx, kSeqStringTag | kAsciiStringTag); + __ j(not_equal, &non_ascii_flat); + const int kFlatAsciiString = + kIsNotStringMask | kStringRepresentationMask | kStringEncodingMask; + __ and_(ebx, kFlatAsciiString); + __ cmp(ebx, kStringTag | kSeqStringTag | kAsciiStringTag); + __ j(not_equal, &non_ascii_flat); + + // Compare flat ascii strings. + GenerateCompareFlatAsciiStrings(masm, edx, eax, ecx, ebx, edi); + + __ bind(&non_ascii_flat); + + // Call the runtime; it returns -1 (less), 0 (equal), or 1 (greater) + // tagged as a small integer. + __ bind(&runtime); + __ TailCallRuntime(ExternalReference(Runtime::kStringCompare), 2, 1); +} + #undef __ } } // namespace v8::internal diff --git a/src/ia32/codegen-ia32.h b/src/ia32/codegen-ia32.h index fcf3f30..2e98d05 100644 --- a/src/ia32/codegen-ia32.h +++ b/src/ia32/codegen-ia32.h @@ -547,6 +547,9 @@ class CodeGenerator: public AstVisitor { // Fast support for SubString. void GenerateSubString(ZoneList* args); + // Fast support for StringCompare. + void GenerateStringCompare(ZoneList* args); + // Support for direct calls from JavaScript to native RegExp code. void GenerateRegExpExec(ZoneList* args); @@ -804,6 +807,31 @@ class SubStringStub: public StringStubBase { }; +class StringCompareStub: public StringStubBase { + public: + explicit StringCompareStub() { + } + + // Compare two flat ascii strings and returns result in eax after popping two + // arguments from the stack. Due to the instructions used there are certain + // constraints on the registers that can be passed. + // counter must be ecx + // scratch1 most be one of eax, ebx or edx + static void GenerateCompareFlatAsciiStrings(MacroAssembler* masm, + Register left, + Register right, + Register counter, + Register scratch1, + Register scratch2); + + private: + Major MajorKey() { return StringCompare; } + int MinorKey() { return 0; } + + void Generate(MacroAssembler* masm); +}; + + } } // namespace v8::internal #endif // V8_IA32_CODEGEN_IA32_H_ diff --git a/src/runtime.cc b/src/runtime.cc index 43d07c1..a24ea7c 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -1158,6 +1158,7 @@ static Object* Runtime_RegExpExec(Arguments args) { RUNTIME_ASSERT(last_match_info->HasFastElements()); RUNTIME_ASSERT(index >= 0); RUNTIME_ASSERT(index <= subject->length()); + Counters::regexp_entry_runtime.Increment(); Handle result = RegExpImpl::Exec(regexp, subject, index, @@ -4216,6 +4217,8 @@ static Object* Runtime_StringCompare(Arguments args) { CONVERT_CHECKED(String, x, args[0]); CONVERT_CHECKED(String, y, args[1]); + Counters::string_compare_runtime.Increment(); + // A few fast case tests before we flatten. if (x == y) return Smi::FromInt(EQUAL); if (y->length() == 0) { diff --git a/src/runtime.js b/src/runtime.js index 9351a23..ce2f197 100644 --- a/src/runtime.js +++ b/src/runtime.js @@ -118,7 +118,7 @@ function COMPARE(x, ncr) { // Fast cases for string, numbers and undefined compares. if (IS_STRING(this)) { - if (IS_STRING(x)) return %StringCompare(this, x); + if (IS_STRING(x)) return %_StringCompare(this, x); if (IS_UNDEFINED(x)) return ncr; left = this; } else if (IS_NUMBER(this)) { @@ -135,7 +135,7 @@ function COMPARE(x, ncr) { // Default implementation. var right = %ToPrimitive(x, NUMBER_HINT); if (IS_STRING(left) && IS_STRING(right)) { - return %StringCompare(left, right); + return %_StringCompare(left, right); } else { var left_number = %ToNumber(left); var right_number = %ToNumber(right); diff --git a/src/v8-counters.h b/src/v8-counters.h index 08bbcaf..fb1e926 100644 --- a/src/v8-counters.h +++ b/src/v8-counters.h @@ -156,6 +156,8 @@ namespace internal { SC(string_add_native, V8.StringAddNative) \ SC(sub_string_runtime, V8.SubStringRuntime) \ SC(sub_string_native, V8.SubStringNative) \ + SC(string_compare_native, V8.StringCompareNative) \ + SC(string_compare_runtime, V8.StringCompareRuntime) \ SC(regexp_entry_runtime, V8.RegExpEntryRuntime) \ SC(regexp_entry_native, V8.RegExpEntryNative) diff --git a/src/x64/codegen-x64.cc b/src/x64/codegen-x64.cc index e99ecc7..2e961af 100644 --- a/src/x64/codegen-x64.cc +++ b/src/x64/codegen-x64.cc @@ -3913,6 +3913,17 @@ void CodeGenerator::GenerateSubString(ZoneList* args) { } +void CodeGenerator::GenerateStringCompare(ZoneList* args) { + ASSERT_EQ(2, args->length()); + + Load(args->at(0)); + Load(args->at(1)); + + Result answer = frame_->CallRuntime(Runtime::kStringCompare, 2); + frame_->Push(&answer); +} + + void CodeGenerator::GenerateClassOf(ZoneList* args) { ASSERT(args->length() == 1); JumpTarget leave, null, function, non_function_constructor; diff --git a/src/x64/codegen-x64.h b/src/x64/codegen-x64.h index 8e3dabe..fa90f02 100644 --- a/src/x64/codegen-x64.h +++ b/src/x64/codegen-x64.h @@ -544,6 +544,9 @@ class CodeGenerator: public AstVisitor { // Fast support for SubString. void GenerateSubString(ZoneList* args); + // Fast support for StringCompare. + void GenerateStringCompare(ZoneList* args); + // Support for direct calls from JavaScript to native RegExp code. void GenerateRegExpExec(ZoneList* args); -- 2.7.4