From 962d7019aa8bd25de7194fde7cb4cad614b3e6f4 Mon Sep 17 00:00:00 2001 From: "whesse@chromium.org" Date: Fri, 14 Jan 2011 10:57:49 +0000 Subject: [PATCH] Speed up FastAsciiArrayJoin on ia32 by improving hand-written assembly code. Review URL: http://codereview.chromium.org/6148007 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@6310 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/ia32/codegen-ia32.cc | 335 +++++++++++++++++++++++++-------------- src/ia32/full-codegen-ia32.cc | 334 +++++++++++++++++++++++--------------- src/ia32/macro-assembler-ia32.cc | 96 ++++++----- src/ia32/macro-assembler-ia32.h | 23 +-- 4 files changed, 475 insertions(+), 313 deletions(-) diff --git a/src/ia32/codegen-ia32.cc b/src/ia32/codegen-ia32.cc index e3b0dfc..1ecfd39 100644 --- a/src/ia32/codegen-ia32.cc +++ b/src/ia32/codegen-ia32.cc @@ -6649,38 +6649,41 @@ void CodeGenerator::GenerateIsArray(ZoneList* args) { void CodeGenerator::GenerateFastAsciiArrayJoin(ZoneList* args) { + Label bailout, done, one_char_separator, long_separator, + non_trivial_array, not_size_one_array, loop, loop_condition, + loop_1, loop_1_condition, loop_2, loop_2_entry, loop_3, loop_3_entry; + ASSERT(args->length() == 2); + // We will leave the separator on the stack until the end of the function. Load(args->at(1)); + // Load this to eax (= array) Load(args->at(0)); Result array_result = frame_->Pop(); array_result.ToRegister(eax); frame_->SpillAll(); - Label bailout; - Label done; // All aliases of the same register have disjoint lifetimes. Register array = eax; - Register result_pos = no_reg; + Register elements = no_reg; // Will be eax. - Register index = edi; + Register index = edx; - Register current_string_length = ecx; // Will be ecx when live. + Register string_length = ecx; - Register current_string = edx; + Register string = esi; Register scratch = ebx; - Register scratch_2 = esi; - Register new_padding_chars = scratch_2; - - Operand separator = Operand(esp, 4 * kPointerSize); // Already pushed. - Operand elements = Operand(esp, 3 * kPointerSize); - Operand result = Operand(esp, 2 * kPointerSize); - Operand padding_chars = Operand(esp, 1 * kPointerSize); - Operand array_length = Operand(esp, 0); - __ sub(Operand(esp), Immediate(4 * kPointerSize)); + Register array_length = edi; + Register result_pos = no_reg; // Will be edi. - // Check that eax is a JSArray + // Separator operand is already pushed. + Operand separator_operand = Operand(esp, 2 * kPointerSize); + Operand result_operand = Operand(esp, 1 * kPointerSize); + Operand array_length_operand = Operand(esp, 0); + __ sub(Operand(esp), Immediate(2 * kPointerSize)); + __ cld(); + // Check that the array is a JSArray __ test(array, Immediate(kSmiTagMask)); __ j(zero, &bailout); __ CmpObjectType(array, JS_ARRAY_TYPE, scratch); @@ -6691,140 +6694,226 @@ void CodeGenerator::GenerateFastAsciiArrayJoin(ZoneList* args) { 1 << Map::kHasFastElements); __ j(zero, &bailout); - // If the array is empty, return the empty string. - __ mov(scratch, FieldOperand(array, JSArray::kLengthOffset)); - __ sar(scratch, 1); - Label non_trivial; - __ j(not_zero, &non_trivial); - __ mov(result, Factory::empty_string()); + // If the array has length zero, return the empty string. + __ mov(array_length, FieldOperand(array, JSArray::kLengthOffset)); + __ sar(array_length, 1); + __ j(not_zero, &non_trivial_array); + __ mov(result_operand, Factory::empty_string()); __ jmp(&done); - __ bind(&non_trivial); - __ mov(array_length, scratch); - - __ mov(scratch, FieldOperand(array, JSArray::kElementsOffset)); - __ mov(elements, scratch); + // Save the array length. + __ bind(&non_trivial_array); + __ mov(array_length_operand, array_length); + // Save the FixedArray containing array's elements. // End of array's live range. - result_pos = array; + elements = array; + __ mov(elements, FieldOperand(array, JSArray::kElementsOffset)); array = no_reg; - // Check that the separator is a flat ascii string. - __ mov(current_string, separator); - __ test(current_string, Immediate(kSmiTagMask)); + // Check that all array elements are sequential ASCII strings, and + // accumulate the sum of their lengths, as a smi-encoded value. + __ Set(index, Immediate(0)); + __ Set(string_length, Immediate(0)); + // Loop condition: while (index < length). + // Live loop registers: index, array_length, string, + // scratch, string_length, elements. + __ jmp(&loop_condition); + __ bind(&loop); + __ cmp(index, Operand(array_length)); + __ j(greater_equal, &done); + + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ test(string, Immediate(kSmiTagMask)); __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); + __ mov(scratch, FieldOperand(string, HeapObject::kMapOffset)); + __ movzx_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); __ and_(scratch, Immediate( kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); __ j(not_equal, &bailout); - // If the separator is the empty string, replace it with NULL. - // The test for NULL is quicker than the empty string test, in a loop. - __ cmp(FieldOperand(current_string, SeqAsciiString::kLengthOffset), - Immediate(0)); - Label separator_checked; - __ j(not_zero, &separator_checked); - __ mov(separator, Immediate(0)); - __ bind(&separator_checked); - - // Check that elements[0] is a flat ascii string, and copy it in new space. - __ mov(scratch, elements); - __ mov(current_string, FieldOperand(scratch, FixedArray::kHeaderSize)); - __ test(current_string, Immediate(kSmiTagMask)); + __ add(string_length, + FieldOperand(string, SeqAsciiString::kLengthOffset)); + __ j(overflow, &bailout); + __ add(Operand(index), Immediate(1)); + __ bind(&loop_condition); + __ cmp(index, Operand(array_length)); + __ j(less, &loop); + + // If array_length is 1, return elements[0], a string. + __ cmp(array_length, 1); + __ j(not_equal, ¬_size_one_array); + __ mov(scratch, FieldOperand(elements, FixedArray::kHeaderSize)); + __ mov(result_operand, scratch); + __ jmp(&done); + + __ bind(¬_size_one_array); + + // End of array_length live range. + result_pos = array_length; + array_length = no_reg; + + // Live registers: + // string_length: Sum of string lengths, as a smi. + // elements: FixedArray of strings. + + // Check that the separator is a flat ASCII string. + __ mov(string, separator_operand); + __ test(string, Immediate(kSmiTagMask)); __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); + __ mov(scratch, FieldOperand(string, HeapObject::kMapOffset)); + __ movzx_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); __ and_(scratch, Immediate( kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); __ j(not_equal, &bailout); - // Allocate space to copy it. Round up the size to the alignment granularity. - __ mov(current_string_length, - FieldOperand(current_string, String::kLengthOffset)); - __ shr(current_string_length, 1); - + // Add (separator length times array_length) - separator length + // to string_length. + __ mov(scratch, separator_operand); + __ mov(scratch, FieldOperand(scratch, SeqAsciiString::kLengthOffset)); + __ sub(string_length, Operand(scratch)); // May be negative, temporarily. + __ imul(scratch, array_length_operand); + __ j(overflow, &bailout); + __ add(string_length, Operand(scratch)); + __ j(overflow, &bailout); + + __ shr(string_length, 1); // Live registers and stack values: - // current_string_length: length of elements[0]. - - // New string result in new space = elements[0] - __ AllocateAsciiString(result_pos, current_string_length, scratch_2, - index, no_reg, &bailout); - __ mov(result, result_pos); - - // Adjust current_string_length to include padding bytes at end of string. - // Keep track of the number of padding bytes. - __ mov(new_padding_chars, current_string_length); - __ add(Operand(current_string_length), Immediate(kObjectAlignmentMask)); - __ and_(Operand(current_string_length), Immediate(~kObjectAlignmentMask)); - __ sub(new_padding_chars, Operand(current_string_length)); - __ neg(new_padding_chars); - __ mov(padding_chars, new_padding_chars); - - Label copy_loop_1_done; - Label copy_loop_1; - __ test(current_string_length, Operand(current_string_length)); - __ j(zero, ©_loop_1_done); - __ bind(©_loop_1); - __ sub(Operand(current_string_length), Immediate(kPointerSize)); - __ mov(scratch, FieldOperand(current_string, current_string_length, - times_1, SeqAsciiString::kHeaderSize)); - __ mov(FieldOperand(result_pos, current_string_length, - times_1, SeqAsciiString::kHeaderSize), - scratch); - __ j(not_zero, ©_loop_1); - __ bind(©_loop_1_done); - - __ mov(index, Immediate(1)); + // string_length + // elements + __ AllocateAsciiString(result_pos, string_length, scratch, + index, string, &bailout); + __ mov(result_operand, result_pos); + __ lea(result_pos, FieldOperand(result_pos, SeqAsciiString::kHeaderSize)); + + + __ mov(string, separator_operand); + __ cmp(FieldOperand(string, SeqAsciiString::kLengthOffset), + Immediate(Smi::FromInt(1))); + __ j(equal, &one_char_separator); + __ j(greater, &long_separator); + + + // Empty separator case + __ mov(index, Immediate(0)); + __ jmp(&loop_1_condition); // Loop condition: while (index < length). - Label loop; - __ bind(&loop); - __ cmp(index, array_length); - __ j(greater_equal, &done); + __ bind(&loop_1); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + // elements: the FixedArray of strings we are joining. + + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + __ add(Operand(index), Immediate(1)); + __ bind(&loop_1_condition); + __ cmp(index, array_length_operand); + __ j(less, &loop_1); // End while (index < length). + __ jmp(&done); - // If the separator is the empty string, signalled by NULL, skip it. - Label separator_done; - __ mov(current_string, separator); - __ test(current_string, Operand(current_string)); - __ j(zero, &separator_done); - - // Append separator to result. It is known to be a flat ascii string. - __ AppendStringToTopOfNewSpace(current_string, current_string_length, - result_pos, scratch, scratch_2, result, - padding_chars, &bailout); - __ bind(&separator_done); - - // Add next element of array to the end of the result. - // Get current_string = array[index]. - __ mov(scratch, elements); - __ mov(current_string, FieldOperand(scratch, index, - times_pointer_size, - FixedArray::kHeaderSize)); - // If current != flat ascii string drop result, return undefined. - __ test(current_string, Immediate(kSmiTagMask)); - __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); - __ and_(scratch, Immediate( - kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); - __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); - __ j(not_equal, &bailout); - // Append current to the result. - __ AppendStringToTopOfNewSpace(current_string, current_string_length, - result_pos, scratch, scratch_2, result, - padding_chars, &bailout); + + // One-character separator case + __ bind(&one_char_separator); + // Replace separator with its ascii character value. + __ mov_b(scratch, FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ mov_b(separator_operand, scratch); + + __ Set(index, Immediate(0)); + // Jump into the loop after the code that copies the separator, so the first + // element is not preceded by a separator + __ jmp(&loop_2_entry); + // Loop condition: while (index < length). + __ bind(&loop_2); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + + // Copy the separator character to the result. + __ mov_b(scratch, separator_operand); + __ mov_b(Operand(result_pos, 0), scratch); + __ inc(result_pos); + + __ bind(&loop_2_entry); + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); __ add(Operand(index), Immediate(1)); - __ jmp(&loop); // End while (index < length). + + __ cmp(index, array_length_operand); + __ j(less, &loop_2); // End while (index < length). + __ jmp(&done); + + + // Long separator case (separator is more than one character). + __ bind(&long_separator); + + __ Set(index, Immediate(0)); + // Jump into the loop after the code that copies the separator, so the first + // element is not preceded by a separator + __ jmp(&loop_3_entry); + // Loop condition: while (index < length). + __ bind(&loop_3); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + + // Copy the separator to the result. + __ mov(string, separator_operand); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + + __ bind(&loop_3_entry); + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + __ add(Operand(index), Immediate(1)); + + __ cmp(index, array_length_operand); + __ j(less, &loop_3); // End while (index < length). + __ jmp(&done); + __ bind(&bailout); - __ mov(result, Factory::undefined_value()); + __ mov(result_operand, Factory::undefined_value()); __ bind(&done); - __ mov(eax, result); + __ mov(eax, result_operand); // Drop temp values from the stack, and restore context register. - __ add(Operand(esp), Immediate(4 * kPointerSize)); + __ add(Operand(esp), Immediate(2 * kPointerSize)); __ mov(esi, Operand(ebp, StandardFrameConstants::kContextOffset)); frame_->Drop(1); diff --git a/src/ia32/full-codegen-ia32.cc b/src/ia32/full-codegen-ia32.cc index 5f30858..2622b5e 100644 --- a/src/ia32/full-codegen-ia32.cc +++ b/src/ia32/full-codegen-ia32.cc @@ -3351,39 +3351,37 @@ void FullCodeGenerator::EmitGetCachedArrayIndex(ZoneList* args) { void FullCodeGenerator::EmitFastAsciiArrayJoin(ZoneList* args) { - Label bailout; - Label done; + Label bailout, done, one_char_separator, long_separator, + non_trivial_array, not_size_one_array, loop, loop_condition, + loop_1, loop_1_condition, loop_2, loop_2_entry, loop_3, loop_3_entry; ASSERT(args->length() == 2); // We will leave the separator on the stack until the end of the function. VisitForStackValue(args->at(1)); // Load this to eax (= array) VisitForAccumulatorValue(args->at(0)); - // All aliases of the same register have disjoint lifetimes. Register array = eax; - Register result_pos = no_reg; + Register elements = no_reg; // Will be eax. - Register index = edi; + Register index = edx; - Register current_string_length = ecx; // Will be ecx when live. + Register string_length = ecx; - Register current_string = edx; + Register string = esi; Register scratch = ebx; - Register scratch_2 = esi; - Register new_padding_chars = scratch_2; - - Operand separator = Operand(esp, 4 * kPointerSize); // Already pushed. - Operand elements = Operand(esp, 3 * kPointerSize); - Operand result = Operand(esp, 2 * kPointerSize); - Operand padding_chars = Operand(esp, 1 * kPointerSize); - Operand array_length = Operand(esp, 0); - __ sub(Operand(esp), Immediate(4 * kPointerSize)); + Register array_length = edi; + Register result_pos = no_reg; // Will be edi. - - // Check that eax is a JSArray + // Separator operand is already pushed. + Operand separator_operand = Operand(esp, 2 * kPointerSize); + Operand result_operand = Operand(esp, 1 * kPointerSize); + Operand array_length_operand = Operand(esp, 0); + __ sub(Operand(esp), Immediate(2 * kPointerSize)); + __ cld(); + // Check that the array is a JSArray __ test(array, Immediate(kSmiTagMask)); __ j(zero, &bailout); __ CmpObjectType(array, JS_ARRAY_TYPE, scratch); @@ -3394,140 +3392,226 @@ void FullCodeGenerator::EmitFastAsciiArrayJoin(ZoneList* args) { 1 << Map::kHasFastElements); __ j(zero, &bailout); - // If the array is empty, return the empty string. - __ mov(scratch, FieldOperand(array, JSArray::kLengthOffset)); - __ sar(scratch, 1); - Label non_trivial; - __ j(not_zero, &non_trivial); - __ mov(result, Factory::empty_string()); + // If the array has length zero, return the empty string. + __ mov(array_length, FieldOperand(array, JSArray::kLengthOffset)); + __ sar(array_length, 1); + __ j(not_zero, &non_trivial_array); + __ mov(result_operand, Factory::empty_string()); __ jmp(&done); - __ bind(&non_trivial); - __ mov(array_length, scratch); - - __ mov(scratch, FieldOperand(array, JSArray::kElementsOffset)); - __ mov(elements, scratch); + // Save the array length. + __ bind(&non_trivial_array); + __ mov(array_length_operand, array_length); + // Save the FixedArray containing array's elements. // End of array's live range. - result_pos = array; + elements = array; + __ mov(elements, FieldOperand(array, JSArray::kElementsOffset)); array = no_reg; - // Check that the separator is a flat ascii string. - __ mov(current_string, separator); - __ test(current_string, Immediate(kSmiTagMask)); + // Check that all array elements are sequential ASCII strings, and + // accumulate the sum of their lengths, as a smi-encoded value. + __ Set(index, Immediate(0)); + __ Set(string_length, Immediate(0)); + // Loop condition: while (index < length). + // Live loop registers: index, array_length, string, + // scratch, string_length, elements. + __ jmp(&loop_condition); + __ bind(&loop); + __ cmp(index, Operand(array_length)); + __ j(greater_equal, &done); + + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ test(string, Immediate(kSmiTagMask)); __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); + __ mov(scratch, FieldOperand(string, HeapObject::kMapOffset)); + __ movzx_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); __ and_(scratch, Immediate( kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); __ j(not_equal, &bailout); - // If the separator is the empty string, replace it with NULL. - // The test for NULL is quicker than the empty string test, in a loop. - __ cmp(FieldOperand(current_string, SeqAsciiString::kLengthOffset), - Immediate(0)); - Label separator_checked; - __ j(not_zero, &separator_checked); - __ mov(separator, Immediate(0)); - __ bind(&separator_checked); - - // Check that elements[0] is a flat ascii string, and copy it in new space. - __ mov(scratch, elements); - __ mov(current_string, FieldOperand(scratch, FixedArray::kHeaderSize)); - __ test(current_string, Immediate(kSmiTagMask)); + __ add(string_length, + FieldOperand(string, SeqAsciiString::kLengthOffset)); + __ j(overflow, &bailout); + __ add(Operand(index), Immediate(1)); + __ bind(&loop_condition); + __ cmp(index, Operand(array_length)); + __ j(less, &loop); + + // If array_length is 1, return elements[0], a string. + __ cmp(array_length, 1); + __ j(not_equal, ¬_size_one_array); + __ mov(scratch, FieldOperand(elements, FixedArray::kHeaderSize)); + __ mov(result_operand, scratch); + __ jmp(&done); + + __ bind(¬_size_one_array); + + // End of array_length live range. + result_pos = array_length; + array_length = no_reg; + + // Live registers: + // string_length: Sum of string lengths, as a smi. + // elements: FixedArray of strings. + + // Check that the separator is a flat ASCII string. + __ mov(string, separator_operand); + __ test(string, Immediate(kSmiTagMask)); __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); + __ mov(scratch, FieldOperand(string, HeapObject::kMapOffset)); + __ movzx_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); __ and_(scratch, Immediate( kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); __ j(not_equal, &bailout); - // Allocate space to copy it. Round up the size to the alignment granularity. - __ mov(current_string_length, - FieldOperand(current_string, String::kLengthOffset)); - __ shr(current_string_length, 1); - + // Add (separator length times array_length) - separator length + // to string_length. + __ mov(scratch, separator_operand); + __ mov(scratch, FieldOperand(scratch, SeqAsciiString::kLengthOffset)); + __ sub(string_length, Operand(scratch)); // May be negative, temporarily. + __ imul(scratch, array_length_operand); + __ j(overflow, &bailout); + __ add(string_length, Operand(scratch)); + __ j(overflow, &bailout); + + __ shr(string_length, 1); // Live registers and stack values: - // current_string_length: length of elements[0]. - - // New string result in new space = elements[0] - __ AllocateAsciiString(result_pos, current_string_length, scratch_2, - index, no_reg, &bailout); - __ mov(result, result_pos); - - // Adjust current_string_length to include padding bytes at end of string. - // Keep track of the number of padding bytes. - __ mov(new_padding_chars, current_string_length); - __ add(Operand(current_string_length), Immediate(kObjectAlignmentMask)); - __ and_(Operand(current_string_length), Immediate(~kObjectAlignmentMask)); - __ sub(new_padding_chars, Operand(current_string_length)); - __ neg(new_padding_chars); - __ mov(padding_chars, new_padding_chars); - - Label copy_loop_1_done; - Label copy_loop_1; - __ test(current_string_length, Operand(current_string_length)); - __ j(zero, ©_loop_1_done); - __ bind(©_loop_1); - __ sub(Operand(current_string_length), Immediate(kPointerSize)); - __ mov(scratch, FieldOperand(current_string, current_string_length, - times_1, SeqAsciiString::kHeaderSize)); - __ mov(FieldOperand(result_pos, current_string_length, - times_1, SeqAsciiString::kHeaderSize), - scratch); - __ j(not_zero, ©_loop_1); - __ bind(©_loop_1_done); - - __ mov(index, Immediate(1)); + // string_length + // elements + __ AllocateAsciiString(result_pos, string_length, scratch, + index, string, &bailout); + __ mov(result_operand, result_pos); + __ lea(result_pos, FieldOperand(result_pos, SeqAsciiString::kHeaderSize)); + + + __ mov(string, separator_operand); + __ cmp(FieldOperand(string, SeqAsciiString::kLengthOffset), + Immediate(Smi::FromInt(1))); + __ j(equal, &one_char_separator); + __ j(greater, &long_separator); + + + // Empty separator case + __ mov(index, Immediate(0)); + __ jmp(&loop_1_condition); // Loop condition: while (index < length). - Label loop; - __ bind(&loop); - __ cmp(index, array_length); - __ j(greater_equal, &done); + __ bind(&loop_1); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + // elements: the FixedArray of strings we are joining. + + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + __ add(Operand(index), Immediate(1)); + __ bind(&loop_1_condition); + __ cmp(index, array_length_operand); + __ j(less, &loop_1); // End while (index < length). + __ jmp(&done); - // If the separator is the empty string, signalled by NULL, skip it. - Label separator_done; - __ mov(current_string, separator); - __ test(current_string, Operand(current_string)); - __ j(zero, &separator_done); - - // Append separator to result. It is known to be a flat ascii string. - __ AppendStringToTopOfNewSpace(current_string, current_string_length, - result_pos, scratch, scratch_2, result, - padding_chars, &bailout); - __ bind(&separator_done); - - // Add next element of array to the end of the result. - // Get current_string = array[index]. - __ mov(scratch, elements); - __ mov(current_string, FieldOperand(scratch, index, - times_pointer_size, - FixedArray::kHeaderSize)); - // If current != flat ascii string drop result, return undefined. - __ test(current_string, Immediate(kSmiTagMask)); - __ j(zero, &bailout); - __ mov(scratch, FieldOperand(current_string, HeapObject::kMapOffset)); - __ mov_b(scratch, FieldOperand(scratch, Map::kInstanceTypeOffset)); - __ and_(scratch, Immediate( - kIsNotStringMask | kStringEncodingMask | kStringRepresentationMask)); - __ cmp(scratch, kStringTag | kAsciiStringTag | kSeqStringTag); - __ j(not_equal, &bailout); - // Append current to the result. - __ AppendStringToTopOfNewSpace(current_string, current_string_length, - result_pos, scratch, scratch_2, result, - padding_chars, &bailout); + + // One-character separator case + __ bind(&one_char_separator); + // Replace separator with its ascii character value. + __ mov_b(scratch, FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ mov_b(separator_operand, scratch); + + __ Set(index, Immediate(0)); + // Jump into the loop after the code that copies the separator, so the first + // element is not preceded by a separator + __ jmp(&loop_2_entry); + // Loop condition: while (index < length). + __ bind(&loop_2); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + + // Copy the separator character to the result. + __ mov_b(scratch, separator_operand); + __ mov_b(Operand(result_pos, 0), scratch); + __ inc(result_pos); + + __ bind(&loop_2_entry); + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + __ add(Operand(index), Immediate(1)); + + __ cmp(index, array_length_operand); + __ j(less, &loop_2); // End while (index < length). + __ jmp(&done); + + + // Long separator case (separator is more than one character). + __ bind(&long_separator); + + __ Set(index, Immediate(0)); + // Jump into the loop after the code that copies the separator, so the first + // element is not preceded by a separator + __ jmp(&loop_3_entry); + // Loop condition: while (index < length). + __ bind(&loop_3); + // Each iteration of the loop concatenates one string to the result. + // Live values in registers: + // index: which element of the elements array we are adding to the result. + // result_pos: the position to which we are currently copying characters. + + // Copy the separator to the result. + __ mov(string, separator_operand); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); + + __ bind(&loop_3_entry); + // Get string = array[index]. + __ mov(string, FieldOperand(elements, index, + times_pointer_size, + FixedArray::kHeaderSize)); + __ mov(string_length, + FieldOperand(string, String::kLengthOffset)); + __ shr(string_length, 1); + __ lea(string, + FieldOperand(string, SeqAsciiString::kHeaderSize)); + __ CopyBytes(string, result_pos, string_length, scratch); __ add(Operand(index), Immediate(1)); - __ jmp(&loop); // End while (index < length). + + __ cmp(index, array_length_operand); + __ j(less, &loop_3); // End while (index < length). + __ jmp(&done); + __ bind(&bailout); - __ mov(result, Factory::undefined_value()); + __ mov(result_operand, Factory::undefined_value()); __ bind(&done); - __ mov(eax, result); + __ mov(eax, result_operand); // Drop temp values from the stack, and restore context register. - __ add(Operand(esp), Immediate(5 * kPointerSize)); + __ add(Operand(esp), Immediate(3 * kPointerSize)); __ mov(esi, Operand(ebp, StandardFrameConstants::kContextOffset)); context()->Plug(eax); diff --git a/src/ia32/macro-assembler-ia32.cc b/src/ia32/macro-assembler-ia32.cc index a6f4679..10c942a 100644 --- a/src/ia32/macro-assembler-ia32.cc +++ b/src/ia32/macro-assembler-ia32.cc @@ -877,55 +877,53 @@ void MacroAssembler::AllocateAsciiConsString(Register result, Immediate(Factory::cons_ascii_string_map())); } -// All registers must be distinct. Only current_string needs valid contents -// on entry. All registers may be invalid on exit. result_operand is -// unchanged, padding_chars is updated correctly. -void MacroAssembler::AppendStringToTopOfNewSpace( - Register current_string, // Tagged pointer to string to copy. - Register current_string_length, - Register result_pos, - Register scratch, - Register new_padding_chars, - Operand operand_result, - Operand operand_padding_chars, - Label* bailout) { - mov(current_string_length, - FieldOperand(current_string, String::kLengthOffset)); - shr(current_string_length, 1); - sub(current_string_length, operand_padding_chars); - mov(new_padding_chars, current_string_length); - add(Operand(current_string_length), Immediate(kObjectAlignmentMask)); - and_(Operand(current_string_length), Immediate(~kObjectAlignmentMask)); - sub(new_padding_chars, Operand(current_string_length)); - neg(new_padding_chars); - // We need an allocation even if current_string_length is 0, to fetch - // result_pos. Consider using a faster fetch of result_pos in that case. - AllocateInNewSpace(current_string_length, result_pos, scratch, no_reg, - bailout, NO_ALLOCATION_FLAGS); - sub(result_pos, operand_padding_chars); - mov(operand_padding_chars, new_padding_chars); - - Register scratch_2 = new_padding_chars; // Used to compute total length. - // Copy string to the end of result. - mov(current_string_length, - FieldOperand(current_string, String::kLengthOffset)); - mov(scratch, operand_result); - mov(scratch_2, current_string_length); - add(scratch_2, FieldOperand(scratch, String::kLengthOffset)); - mov(FieldOperand(scratch, String::kLengthOffset), scratch_2); - shr(current_string_length, 1); - lea(current_string, - FieldOperand(current_string, SeqAsciiString::kHeaderSize)); - // Loop condition: while (--current_string_length >= 0). - Label copy_loop; - Label copy_loop_entry; - jmp(©_loop_entry); - bind(©_loop); - mov_b(scratch, Operand(current_string, current_string_length, times_1, 0)); - mov_b(Operand(result_pos, current_string_length, times_1, 0), scratch); - bind(©_loop_entry); - sub(Operand(current_string_length), Immediate(1)); - j(greater_equal, ©_loop); + +// Copy memory, byte-by-byte, from source to destination. Not optimized for +// long or aligned copies. The contents of scratch and length are destroyed. +// Source and destination are incremented by length. +// Many variants of movsb, loop unrolling, word moves, and indexed operands +// have been tried here already, and this is fastest. +// A simpler loop is faster on small copies, but 30% slower on large ones. +// The cld() instruction must have been emitted, to set the direction flag(), +// before calling this function. +void MacroAssembler::CopyBytes(Register source, + Register destination, + Register length, + Register scratch) { + Label loop, done, short_string, short_loop; + // Experimentation shows that the short string loop is faster if length < 10. + cmp(Operand(length), Immediate(10)); + j(less_equal, &short_string); + + ASSERT(source.is(esi)); + ASSERT(destination.is(edi)); + ASSERT(length.is(ecx)); + + // Because source is 4-byte aligned in our uses of this function, + // we keep source aligned for the rep_movs call by copying the odd bytes + // at the end of the ranges. + mov(scratch, Operand(source, length, times_1, -4)); + mov(Operand(destination, length, times_1, -4), scratch); + mov(scratch, ecx); + shr(ecx, 2); + rep_movs(); + and_(Operand(scratch), Immediate(0x3)); + add(destination, Operand(scratch)); + jmp(&done); + + bind(&short_string); + test(length, Operand(length)); + j(zero, &done); + + bind(&short_loop); + mov_b(scratch, Operand(source, 0)); + mov_b(Operand(destination, 0), scratch); + inc(source); + inc(destination); + dec(length); + j(not_zero, &short_loop); + + bind(&done); } diff --git a/src/ia32/macro-assembler-ia32.h b/src/ia32/macro-assembler-ia32.h index 6f5fa87..6f180c6 100644 --- a/src/ia32/macro-assembler-ia32.h +++ b/src/ia32/macro-assembler-ia32.h @@ -386,22 +386,13 @@ class MacroAssembler: public Assembler { Register scratch2, Label* gc_required); - // All registers must be distinct. Only current_string needs valid contents - // on entry. All registers may be invalid on exit. result_operand is - // unchanged, padding_chars is updated correctly. - // The top of new space must contain a sequential ascii string with - // padding_chars bytes free in its top word. The sequential ascii string - // current_string is concatenated to it, allocating the necessary amount - // of new memory. - void AppendStringToTopOfNewSpace( - Register current_string, // Tagged pointer to string to copy. - Register current_string_length, - Register result_pos, - Register scratch, - Register new_padding_chars, - Operand operand_result, - Operand operand_padding_chars, - Label* bailout); + // Copy memory, byte-by-byte, from source to destination. Not optimized for + // long or aligned copies. + // The contents of index and scratch are destroyed. + void CopyBytes(Register source, + Register destination, + Register length, + Register scratch); // --------------------------------------------------------------------------- // Support functions. -- 2.7.4