Add a fast case to Array.join when all the elements and the separator are fla...

src/ia32/codegen-ia32.cc

Index: src/ia32/codegen-ia32.cc
===================================================================
--- src/ia32/codegen-ia32.cc	(revision 5848)
+++ src/ia32/codegen-ia32.cc	(working copy)
@@ -6642,6 +6642,268 @@
 }
 
 
+void CodeGenerator::GenerateFastAsciiArrayJoin(ZoneList<Expression*>* args) {
+  ASSERT(args->length() == 2);
+  Load(args->at(1));
+  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 index = edi;
+
+  Register current_string_length = ecx;  // Will be ecx when live.
+
+  Register current_string = edx;
+
+  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);
+  __ push(scratch);
+
+  Operand result = Operand(esp, 2 * kPointerSize);
+  __ push(scratch);
+
+  Operand padding_chars = Operand(esp, 1 * kPointerSize);
+  __ push(scratch);
+
+  Operand array_length = Operand(esp, 0);
+  __ push(scratch);

[Lasse Reichstein, 2010/11/18 13:26:54]

You do four pushes of an unknown value. You might as well subtract 4 *
kPointerSize from esp. 
At least it'll be 5 bytes shorter.

[William Hesse, 2010/11/18 17:13:04]

Done.

+
+
+  // Check that eax is a JSArray
+  __ test(array, Immediate(kSmiTagMask));
+  __ j(zero, &bailout);
+  __ CmpObjectType(array, JS_ARRAY_TYPE, scratch);
+  __ j(not_equal, &bailout);
+
+  // Check that the array has fast elements.
+  __ cmpb(FieldOperand(scratch, Map::kBitField2Offset),
+          1 << Map::kHasFastElements);

[Lasse Reichstein, 2010/11/18 13:26:54]

Should this be "testb" and should there be a jump if it's zero?

[William Hesse, 2010/11/18 17:13:04]

Done.

+  // If the array is empty, return the empty string.
+  __ mov(scratch, FieldOperand(array, JSArray::kLengthOffset));
+  __ sar(scratch, 1);

[Lasse Reichstein, 2010/11/18 13:26:54]

You use sar here, but shr later, to convert from Smi to int.
Pick either one.

[William Hesse, 2010/11/18 17:13:04]

Done.

+  Label non_trivial;
+  __ j(not_zero, &non_trivial);
+  __ mov(result, Factory::empty_string());
+  __ jmp(&done);
+
+  __ bind(&non_trivial);
+  __ mov(array_length, scratch);

[Lasse Reichstein, 2010/11/18 13:26:54]

It's impossible to distinguish named registers from named Operands. Could you
name the operands somehow to make it easier to see that this is a
mov(Operand,Register)?

[William Hesse, 2010/11/18 17:13:04]

If an assembly operation compiles, it means the same thing whether it is a
memory operand or a register.  So the type is not important.  And prefixes would
make the variable names more confusing.

[Lasse Reichstein, 2010/11/18 17:49:09]

But they are not equivalent. I was about to suggest that you used array_length
in the calculations above, instead of using scratch and then moving scratch to
array_length ... until I realized that array_length was an Operand.

Reading what's written doesn't need distinguishing, but understanding why it's
written as it is, does.

[William Hesse, 2010/11/19 08:53:43]

That is if you are reading it with a plan to change it or improve it, in which
case you should be aware of the register shortage, and the need to put specific
things in registers.

But this can be changed when it is rewritten with a separate checking and
counting loop, an allocation, and a copying loop.  Taking the allocation out of
the loops frees up a lot of variables.

On 2010/11/18 17:49:09, Lasse Reichstein wrote:

+
+  __ mov(scratch, FieldOperand(array, JSArray::kElementsOffset));
+  __ mov(elements, scratch);
+
+  // End of array's live range.
+  result_pos = array;
+  array = no_reg;
+
+
+  // Check that the separator is a flat ascii string.

[Lasse Reichstein, 2010/11/18 13:26:54]

ASCII is an acronym :)

[William Hesse, 2010/11/18 17:13:04]

We use both ASCII and ascii in comments.  ascii is used more often.

+  __ mov(current_string, separator);
+  __ 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);
+  // 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));
+  __ 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);
+
+  // 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);
+
+  // 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_entry;
+  Label copy_loop_1;
+  __ test(current_string_length, Operand(current_string_length));
+  __ jmp(&copy_loop_1_entry);

[Lasse Reichstein, 2010/11/18 13:26:54]

How about a conditional jump here, if zero: jump to line 6779?
It only happens when the first string of the array is empty.

[William Hesse, 2010/11/18 17:13:04]

That would require another label.  The current behavior is correct, if not
optimal.

[Lasse Reichstein, 2010/11/18 17:49:09]

You wouldn't need the entry label then, so the label count is the same.
Go for optimal! Great isn't good enough! :)

[William Hesse, 2010/11/19 08:53:43]

Done.

+  __ bind(&copy_loop_1);
+  __ sub(Operand(current_string_length), Immediate(kPointerSize));
+  __ mov(scratch, FieldOperand(current_string, current_string_length,
+                                 times_1, SeqAsciiString::kHeaderSize));

[Lasse Reichstein, 2010/11/18 13:26:54]

Indentation.

[William Hesse, 2010/11/18 17:13:04]

Done.

+  __ mov(FieldOperand(result_pos, current_string_length,
+                      times_1, SeqAsciiString::kHeaderSize),
+         scratch);
+  __ bind(&copy_loop_1_entry);
+  __ j(not_zero, &copy_loop_1);
+
+  __ mov(index, Immediate(1));
+  // Loop condition: while (index < length).
+  Label loop;
+  __ bind(&loop);
+  __ cmp(index, array_length);
+  __ j(greater_equal, &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.
+  // Extend the result by the length of the separator.
+  __ mov(current_string_length,

[Lasse Reichstein, 2010/11/18 13:26:54]

You should definitly extract the "append seq-ASCII string to existing seq-ASCII
string at NewSpace-end" macro and use that for both separator and array
elements.

[William Hesse, 2010/11/18 17:13:04]

Done.

+         FieldOperand(current_string, String::kLengthOffset));
+  __ shr(current_string_length, 1);
+  __ sub(current_string_length, 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);

[Lasse Reichstein, 2010/11/18 13:26:54]

You negate new_padding_chars, and then use them in a subtraction. If you stored
their negated value, and added it instead, you would save the negation.
Instead of "padding", you could call it something with "offset from end" :)

[William Hesse, 2010/11/18 17:13:04]

I would like to do this fix in a separate change.

+  // 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, padding_chars);
+  __ mov(padding_chars, new_padding_chars);
+
+  // Copy separator to the end of result.
+  __ mov(current_string_length,
+         FieldOperand(current_string, String::kLengthOffset));
+  __ mov(scratch, 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_2;
+  Label copy_loop_2_entry;
+  __ jmp(&copy_loop_2_entry);
+  __ bind(&copy_loop_2);
+  __ mov_b(scratch,
+          Operand(current_string, current_string_length, times_1, 0));

[Lasse Reichstein, 2010/11/18 13:26:54]

Indentation.

[William Hesse, 2010/11/18 17:13:04]

Done.

+  __ mov_b(Operand(result_pos, current_string_length, times_1, 0),
+          scratch);

[Lasse Reichstein, 2010/11/18 13:26:54]

Indentation.

[William Hesse, 2010/11/18 17:13:04]

Done.

+  __ bind(&copy_loop_2_entry);
+  __ sub(Operand(current_string_length), Immediate(1));
+  __ j(greater_equal, &copy_loop_2);
+
+  __ 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);
+
+  //   extend result by length(current)

[Lasse Reichstein, 2010/11/18 13:26:54]

Capitalize "E" in "extend". Comments are/should be sentences.

[William Hesse, 2010/11/18 17:13:04]

Done.

+  __ mov(current_string_length,
+         FieldOperand(current_string, String::kLengthOffset));
+  __ shr(current_string_length, 1);
+  __ sub(current_string_length, 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);
+  __ AllocateInNewSpace(current_string_length, result_pos, scratch, no_reg,
+                        &bailout, NO_ALLOCATION_FLAGS);
+  __ sub(result_pos, padding_chars);
+  __ mov(padding_chars, new_padding_chars);
+
+  //   copy current to end of result
+  __ mov(current_string_length,
+         FieldOperand(current_string, String::kLengthOffset));
+  __ mov(scratch, 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));
+  Label copy_loop_3;
+  Label copy_loop_3_entry;
+  __ jmp(&copy_loop_3_entry);
+  __ bind(&copy_loop_3);
+  __ 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(&copy_loop_3_entry);
+  __ sub(Operand(current_string_length), Immediate(1));
+  __ j(greater_equal, &copy_loop_3);
+
+  __ add(Operand(index), Immediate(1));
+  //  end while
+  __ jmp(&loop);
+  //  return current
+
+  __ bind(&bailout);

[Lasse Reichstein, 2010/11/18 13:26:54]

If you bail out to here after having allocated the first time, you leak the
allocated memory. You could undo the allocation by rolling the newspace-top back
to the allocation. 
E.g., have a bailout_and_free before the bailout label, and call that after the
first allocation.

[William Hesse, 2010/11/18 17:13:04]

This would be a good fix for a later improved version.  I also think that
computing the length, and checking the types of all the strings first, would be
a good idea, and make the code simpler.

+  __ mov(result, Factory::undefined_value());
+  __ bind(&done);
+  __ mov(eax, result);
+  // Drop temp values from the stack, and restore context register.
+  __ add(Operand(esp), Immediate(4 * kPointerSize));
+
+  __ mov(esi, Operand(ebp, StandardFrameConstants::kContextOffset));
+  frame_->Drop(1);
+  frame_->Push(&array_result);
+}
+
+
 void CodeGenerator::GenerateIsRegExp(ZoneList<Expression*>* args) {
   ASSERT(args->length() == 1);
   Load(args->at(0));