Revision: 3569
Author: [email protected]
Date: Fri Jan 8 03:58:15 2010
Log: 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
http://code.google.com/p/v8/source/detail?r=3569
Modified:
/branches/bleeding_edge/src/arm/codegen-arm.cc
/branches/bleeding_edge/src/arm/codegen-arm.h
/branches/bleeding_edge/src/code-stubs.h
/branches/bleeding_edge/src/codegen.cc
/branches/bleeding_edge/src/ia32/assembler-ia32.cc
/branches/bleeding_edge/src/ia32/assembler-ia32.h
/branches/bleeding_edge/src/ia32/codegen-ia32.cc
/branches/bleeding_edge/src/ia32/codegen-ia32.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.js
/branches/bleeding_edge/src/v8-counters.h
/branches/bleeding_edge/src/x64/codegen-x64.cc
/branches/bleeding_edge/src/x64/codegen-x64.h
=======================================
--- /branches/bleeding_edge/src/arm/codegen-arm.cc Fri Jan 8 02:41:25 2010
+++ /branches/bleeding_edge/src/arm/codegen-arm.cc Fri Jan 8 03:58:15 2010
@@ -3462,6 +3462,17 @@
frame_->CallRuntime(Runtime::kSubString, 3);
frame_->EmitPush(r0);
}
+
+
+void CodeGenerator::GenerateStringCompare(ZoneList<Expression*>* 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<Expression*>* args) {
=======================================
--- /branches/bleeding_edge/src/arm/codegen-arm.h Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/arm/codegen-arm.h Fri Jan 8 03:58:15 2010
@@ -366,6 +366,9 @@
// Fast support for SubString.
void GenerateSubString(ZoneList<Expression*>* args);
+ // Fast support for StringCompare.
+ void GenerateStringCompare(ZoneList<Expression*>* args);
+
// Support for direct calls from JavaScript to native RegExp code.
void GenerateRegExpExec(ZoneList<Expression*>* args);
=======================================
--- /branches/bleeding_edge/src/code-stubs.h Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/code-stubs.h Fri Jan 8 03:58:15 2010
@@ -38,6 +38,7 @@
V(GenericBinaryOp) \
V(StringAdd) \
V(SubString) \
+ V(StringCompare) \
V(SmiOp) \
V(Compare) \
V(RecordWrite) \
=======================================
--- /branches/bleeding_edge/src/codegen.cc Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/codegen.cc Fri Jan 8 03:58:15 2010
@@ -346,6 +346,7 @@
{&CodeGenerator::GenerateIsFunction, "_IsFunction"},
{&CodeGenerator::GenerateStringAdd, "_StringAdd"},
{&CodeGenerator::GenerateSubString, "_SubString"},
+ {&CodeGenerator::GenerateStringCompare, "_StringCompare"},
{&CodeGenerator::GenerateRegExpExec, "_RegExpExec"},
};
=======================================
--- /branches/bleeding_edge/src/ia32/assembler-ia32.cc Thu Jan 7 01:59:37
2010
+++ /branches/bleeding_edge/src/ia32/assembler-ia32.cc Fri Jan 8 03:58:15
2010
@@ -1205,6 +1205,14 @@
EMIT(0x2B);
emit_operand(dst, 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) {
@@ -1592,6 +1600,18 @@
}
+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
=======================================
--- /branches/bleeding_edge/src/ia32/assembler-ia32.h Thu Jan 7 01:59:37
2010
+++ /branches/bleeding_edge/src/ia32/assembler-ia32.h Fri Jan 8 03:58:15
2010
@@ -540,7 +540,7 @@
void cmov(Condition cc, Register dst, Handle<Object> 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 @@
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 @@
void j(Condition cc, byte* entry, RelocInfo::Mode rmode, Hint hint =
no_hint);
void j(Condition cc, Handle<Code> code, Hint hint = no_hint);
+ // Loop instruction using ecx as counter.
+ void loope(Label* L);
+
// Floating-point operations
void fld(int i);
=======================================
--- /branches/bleeding_edge/src/ia32/codegen-ia32.cc Fri Jan 8 02:41:25
2010
+++ /branches/bleeding_edge/src/ia32/codegen-ia32.cc Fri Jan 8 03:58:15
2010
@@ -5445,6 +5445,18 @@
Result answer = frame_->CallStub(&stub, 3);
frame_->Push(&answer);
}
+
+
+void CodeGenerator::GenerateStringCompare(ZoneList<Expression*>* 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<Expression*>* args) {
@@ -8562,15 +8574,54 @@
// 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
// non-zero value, which indicates not equal, so just return.
__ 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
@@ -9578,6 +9629,144 @@
__ bind(&runtime);
__ 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 __
=======================================
--- /branches/bleeding_edge/src/ia32/codegen-ia32.h Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/ia32/codegen-ia32.h Fri Jan 8 03:58:15 2010
@@ -547,6 +547,9 @@
// Fast support for SubString.
void GenerateSubString(ZoneList<Expression*>* args);
+ // Fast support for StringCompare.
+ void GenerateStringCompare(ZoneList<Expression*>* args);
+
// Support for direct calls from JavaScript to native RegExp code.
void GenerateRegExpExec(ZoneList<Expression*>* args);
@@ -799,6 +802,31 @@
private:
Major MajorKey() { return SubString; }
int MinorKey() { return 0; }
+
+ void Generate(MacroAssembler* masm);
+};
+
+
+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);
};
=======================================
--- /branches/bleeding_edge/src/runtime.cc Fri Jan 8 03:27:37 2010
+++ /branches/bleeding_edge/src/runtime.cc Fri Jan 8 03:58:15 2010
@@ -1158,6 +1158,7 @@
RUNTIME_ASSERT(last_match_info->HasFastElements());
RUNTIME_ASSERT(index >= 0);
RUNTIME_ASSERT(index <= subject->length());
+ Counters::regexp_entry_runtime.Increment();
Handle<Object> result = RegExpImpl::Exec(regexp,
subject,
index,
@@ -4216,6 +4217,8 @@
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) {
=======================================
--- /branches/bleeding_edge/src/runtime.js Thu Jan 7 02:25:20 2010
+++ /branches/bleeding_edge/src/runtime.js Fri Jan 8 03:58:15 2010
@@ -118,7 +118,7 @@
// 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 @@
// 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);
=======================================
--- /branches/bleeding_edge/src/v8-counters.h Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/v8-counters.h Fri Jan 8 03:58:15 2010
@@ -156,6 +156,8 @@
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)
=======================================
--- /branches/bleeding_edge/src/x64/codegen-x64.cc Fri Jan 8 02:41:25 2010
+++ /branches/bleeding_edge/src/x64/codegen-x64.cc Fri Jan 8 03:58:15 2010
@@ -3911,6 +3911,17 @@
Result answer = frame_->CallRuntime(Runtime::kSubString, 3);
frame_->Push(&answer);
}
+
+
+void CodeGenerator::GenerateStringCompare(ZoneList<Expression*>* 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<Expression*>* args) {
=======================================
--- /branches/bleeding_edge/src/x64/codegen-x64.h Thu Jan 7 01:59:37 2010
+++ /branches/bleeding_edge/src/x64/codegen-x64.h Fri Jan 8 03:58:15 2010
@@ -544,6 +544,9 @@
// Fast support for SubString.
void GenerateSubString(ZoneList<Expression*>* args);
+ // Fast support for StringCompare.
+ void GenerateStringCompare(ZoneList<Expression*>* args);
+
// Support for direct calls from JavaScript to native RegExp code.
void GenerateRegExpExec(ZoneList<Expression*>* args);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
