Implement loop for global regexps in regexp assembler.

Implement loop for global regexps in regexp assembler.

BUG=
TEST=

Committed: https://code.google.com/p/v8/source/detail?r=11623

[Yang, 2012-05-11 09:57:17]

PTAL.

This CL is far from being completed since platform ports and tests are missing.
I still want to get a second opinion on this before I continue.

I implemented the loop inside GetCode() that deals with setting up local
variables and returning results. I initially thought about doing it in a higher
level way, representing the loop as a RegExpNode, but then changes to Fail() and
Succeed() were also necessary, so I chose doing it in low-level assembly
instead. Suggestions on that are very welcome.

[Erik Corry, 2012-05-11 11:01:00]

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
File src/ia32/regexp-macro-assembler-ia32.h (right):

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
src/ia32/regexp-macro-assembler-ia32.h:139: // For the case of global regular
expression, we have room to store more
more than one -> at least one
?

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
src/ia32/regexp-macro-assembler-ia32.h:160: // The highest bit on the output
registers count signals success.  This
lowest bit?

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc
File src/jsregexp.cc (right):

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode200
src/jsregexp.cc:200: if (parse_result.simple &&
It would be interesting to remove this stuff so we never AtomCompile, but always
use the regexp engine.  With these changes it might be faster, and it would
simplify things a lot.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode904
src/jsregexp.cc:904: RegExpCompiler(int capture_count,
You don't need this change.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode981
src/jsregexp.cc:981: bool ignore_case,
You don't need this change.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode5796
src/jsregexp.cc:5796: RegExpCompiler compiler(data->capture_count,
Or this.

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h
File src/regexp-macro-assembler.h (right):

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h#n...
src/regexp-macro-assembler.h:186: // Set wether the regular expression has the
global flag.  Failures in a
A wether is a castrated billy-goat :-)

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h#n...
src/regexp-macro-assembler.h:187: // global regexp may still mean success
overal.
overall.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3798
src/runtime.cc:3798: static int SearchRegExpNoCaptureMultiple(
I wonder if we can unify this and SearchRegExpMultiple without a performance
hit.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3818
src/runtime.cc:3818: int result =
How about giving this variable a name like number_of_matches, and getting rid of
RE_SUCCESS and RE_FAILURE.  Just comparing == 0 and > 0 makes sense if the
variable has the right name.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3851
src/runtime.cc:3851: if (match_start != match_end) {
I don't see this logic replicated in the regexp-macro-assembler.  This suggests
to me that we are missing good tests for it.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3855
src/runtime.cc:3855: if (pos > subject_length) {
unneeded edit

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3940
src/runtime.cc:3940: match = isolate->factory()->NewProperSubString(subject,
Not sure why we need NewProperSubString here.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3949
src/runtime.cc:3949: for (int i = 1; i <= capture_count; i++) {
I think you could just start this loop at 0 and remove some code duplication.

[Yang, 2012-05-16 14:58:46]

Addressed comments and ported to x64 and arm. Please take another look.

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
File src/ia32/regexp-macro-assembler-ia32.h (right):

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
src/ia32/regexp-macro-assembler-ia32.h:139: // For the case of global regular
expression, we have room to store more
On 2012/05/11 11:01:00, Erik Corry wrote:
> more than one -> at least one
> ?

Done.

http://codereview.chromium.org/10386090/diff/1/src/ia32/regexp-macro-assemble...
src/ia32/regexp-macro-assembler-ia32.h:160: // The highest bit on the output
registers count signals success.  This
On 2012/05/11 11:01:00, Erik Corry wrote:
> lowest bit?

Not even necessary anymore. Removed.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc
File src/jsregexp.cc (right):

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode904
src/jsregexp.cc:904: RegExpCompiler(int capture_count,
On 2012/05/11 11:01:00, Erik Corry wrote:
> You don't need this change.

Done.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode981
src/jsregexp.cc:981: bool ignore_case,
On 2012/05/11 11:01:00, Erik Corry wrote:
> You don't need this change.

Done.

http://codereview.chromium.org/10386090/diff/1/src/jsregexp.cc#newcode5796
src/jsregexp.cc:5796: RegExpCompiler compiler(data->capture_count,
On 2012/05/11 11:01:00, Erik Corry wrote:
> Or this.

Done.

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h
File src/regexp-macro-assembler.h (right):

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h#n...
src/regexp-macro-assembler.h:186: // Set wether the regular expression has the
global flag.  Failures in a
On 2012/05/11 11:01:00, Erik Corry wrote:
> A wether is a castrated billy-goat :-)

Done. I never knew that. Learned something new today :)

http://codereview.chromium.org/10386090/diff/1/src/regexp-macro-assembler.h#n...
src/regexp-macro-assembler.h:187: // global regexp may still mean success
overal.
On 2012/05/11 11:01:00, Erik Corry wrote:
> overall.

Done.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3798
src/runtime.cc:3798: static int SearchRegExpNoCaptureMultiple(
On 2012/05/11 11:01:00, Erik Corry wrote:
> I wonder if we can unify this and SearchRegExpMultiple without a performance
> hit.

I'll try this in another CL.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3818
src/runtime.cc:3818: int result =
On 2012/05/11 11:01:00, Erik Corry wrote:
> How about giving this variable a name like number_of_matches, and getting rid
of
> RE_SUCCESS and RE_FAILURE.  Just comparing == 0 and > 0 makes sense if the
> variable has the right name.

Done.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3940
src/runtime.cc:3940: match = isolate->factory()->NewProperSubString(subject,
On 2012/05/11 11:01:00, Erik Corry wrote:
> Not sure why we need NewProperSubString here.

For every substring save for the first one we know that it's a real substring,
so we can omit the length- and start-check using NewProperSubString.
Unfortunately, this does make a performance difference.

http://codereview.chromium.org/10386090/diff/1/src/runtime.cc#newcode3949
src/runtime.cc:3949: for (int i = 1; i <= capture_count; i++) {
On 2012/05/11 11:01:00, Erik Corry wrote:
> I think you could just start this loop at 0 and remove some code duplication.

After removing the call to NewSubString here (first is false in any case), I
think it makes sense to have the first loop stand out: we don't do a check for
-1 for undefined there and can be sure not to use NewSubString.

[Erik Corry, 2012-05-22 08:32:46]

There seems to be an issue with what happens if there is a GC and the string
moves while we are matching.  This can happen if the regexp is interrupted by
the stack check (eg if the user breaks using the debugger).

Most of the arch-specific comments I have only written in the ARM files, but
they apply to all architectures.

Otherwise LGTM

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc
File src/arm/code-stubs-arm.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc#n...
src/arm/code-stubs-arm.cc:4850: // Argument 6: Clear the number of capture
registers for non-global capture.
I don't understand this comment.  Is argument 6 a boolean argument that
indicates whether we should clear the number of capture registers when the
capture is non-global?  Does it have any meaning if the regexp is non-global?

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc#n...
src/arm/code-stubs-arm.cc:4901: // We do not expect multiple results.
This comment does not clarify much.  Why do we not expect multiple results here.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
File src/arm/regexp-macro-assembler-arm.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:45: * This assembler uses the following
register assignment convention
This needs updating to include r4

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:78: *  - fp[-12] start index       
(character index of start).
Inconsistent capitalization, not started by you.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:80: *  - fp[-20] success counter    (only
useful for global regexp to count matches)
Does this lint?

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:745: __ mov(current_character(),
Operand('\n'), LeaveCC, eq);
Having conditional instructions here after non-conditional instructions that do
not affect the flags - that is too tricky.  Please refactor to use conventional
if-then-else branching.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:755: LoadCurrentCharacterUnchecked(-1, 1);
In the global case the generated code isn't making much sense.  It's doing:

Load CurrentChar
jmp loaded
Load CurrentChar
bind loaded

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:894: // String might have moved: Reload
end of string from frame.
If this happens will r4 be updated with the correct position?

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:1378: offset = ip;
This is setting a trap for a future programmer.  There are lots of instructions
that implicitly overwrite ip, so we should not use ip unless we have to, and if
we do it should be over 1-2 lines so you don't overlook that it is taken.

http://codereview.chromium.org/10386090/diff/3002/src/jsregexp.cc
File src/jsregexp.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/jsregexp.cc#newcode5808
src/jsregexp.cc:5808: RegExpCompiler compiler(data->capture_count, ignore_case,
is_ascii);
Optimization idea (probably for the next patch): At this point you can use
data->tree->min_match() to see whether the regexp can do a zero length match. 
You can pass that as a flag to the compiler and it can tell the macro assembler
to avoid testing for zero length matches in the repeat code on global regexps.

http://codereview.chromium.org/10386090/diff/3002/src/regexp-macro-assembler-...
File src/regexp-macro-assembler-tracer.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/regexp-macro-assembler-...
src/regexp-macro-assembler-tracer.cc:107: assembler_->global() ? " [restart for
global match]" : "");
It's a bit ugly that this will print "restart..." for global regexps in the
interpreter, but it won't actually restart.  Instead you could make this
function return a bool that tells you whether it actually emitted code to
restart.

http://codereview.chromium.org/10386090/diff/3002/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/runtime.cc#newcode3863
src/runtime.cc:3863: return num_matches;
Perhaps it is clearer to write "return RegExpImpl::RE_EXCEPTION here since there
is no number of matches to return.

http://codereview.chromium.org/10386090/diff/3002/test/mjsunit/regexp-global.js
File test/mjsunit/regexp-global.js (right):

http://codereview.chromium.org/10386090/diff/3002/test/mjsunit/regexp-global....
test/mjsunit/regexp-global.js:50: assertEquals("2It 3was 1a 8pleasure 2to
4burn.", str);
Nice test :-)

[Yang, 2012-05-22 14:48:02]

Comments addressed and landed.

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc
File src/arm/code-stubs-arm.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc#n...
src/arm/code-stubs-arm.cc:4850: // Argument 6: Clear the number of capture
registers for non-global capture.
On 2012/05/22 08:32:46, Erik Corry wrote:
> I don't understand this comment.  Is argument 6 a boolean argument that
> indicates whether we should clear the number of capture registers when the
> capture is non-global?  Does it have any meaning if the regexp is non-global?

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/code-stubs-arm.cc#n...
src/arm/code-stubs-arm.cc:4901: // We do not expect multiple results.
On 2012/05/22 08:32:46, Erik Corry wrote:
> This comment does not clarify much.  Why do we not expect multiple results
here.

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
File src/arm/regexp-macro-assembler-arm.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:45: * This assembler uses the following
register assignment convention
On 2012/05/22 08:32:46, Erik Corry wrote:
> This needs updating to include r4

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:78: *  - fp[-12] start index       
(character index of start).
On 2012/05/22 08:32:46, Erik Corry wrote:
> Inconsistent capitalization, not started by you.

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:80: *  - fp[-20] success counter    (only
useful for global regexp to count matches)
On 2012/05/22 08:32:46, Erik Corry wrote:
> Does this lint?

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:745: __ mov(current_character(),
Operand('\n'), LeaveCC, eq);
On 2012/05/22 08:32:46, Erik Corry wrote:
> Having conditional instructions here after non-conditional instructions that
do
> not affect the flags - that is too tricky.  Please refactor to use
conventional
> if-then-else branching.

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:755: LoadCurrentCharacterUnchecked(-1, 1);
On 2012/05/22 08:32:46, Erik Corry wrote:
> In the global case the generated code isn't making much sense.  It's doing:
> 
> Load CurrentChar
> jmp loaded
> Load CurrentChar
> bind loaded

Done.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:894: // String might have moved: Reload
end of string from frame.
On 2012/05/22 08:32:46, Erik Corry wrote:
> If this happens will r4 be updated with the correct position?

r4 is a relative index from the end of string, therefore should not be affected
from moving the string.

http://codereview.chromium.org/10386090/diff/3002/src/arm/regexp-macro-assemb...
src/arm/regexp-macro-assembler-arm.cc:1378: offset = ip;
On 2012/05/22 08:32:46, Erik Corry wrote:
> This is setting a trap for a future programmer.  There are lots of
instructions
> that implicitly overwrite ip, so we should not use ip unless we have to, and
if
> we do it should be over 1-2 lines so you don't overlook that it is taken.

Using r4 now since it's not being used at this point.

http://codereview.chromium.org/10386090/diff/3002/src/jsregexp.cc
File src/jsregexp.cc (right):

http://codereview.chromium.org/10386090/diff/3002/src/jsregexp.cc#newcode5808
src/jsregexp.cc:5808: RegExpCompiler compiler(data->capture_count, ignore_case,
is_ascii);
On 2012/05/22 08:32:46, Erik Corry wrote:
> Optimization idea (probably for the next patch): At this point you can use
> data->tree->min_match() to see whether the regexp can do a zero length match. 
> You can pass that as a flag to the compiler and it can tell the macro
assembler
> to avoid testing for zero length matches in the repeat code on global regexps.

This is exactly what I've been looking for! I tried my luck with EatsAtLeast,
but that wouldn't work for non-capturing matches (e.g. lookahead). Thanks!

http://codereview.chromium.org/10386090/diff/3002/test/mjsunit/regexp-global.js
File test/mjsunit/regexp-global.js (right):

http://codereview.chromium.org/10386090/diff/3002/test/mjsunit/regexp-global....
test/mjsunit/regexp-global.js:50: assertEquals("2It 3was 1a 8pleasure 2to
4burn.", str);
On 2012/05/22 08:32:46, Erik Corry wrote:
> Nice test :-)

:)