Use finite-length end-anchored regexps to reduce part of regexp that is searched.

Use finite-length end-anchored regexps to reduce part of regexp that is searched.

[Erik Corry, 2010-10-19 08:56:19]

LGTM with better test.

http://codereview.chromium.org/3850005/diff/1/2
File src/arm/regexp-macro-assembler-arm.cc (right):

http://codereview.chromium.org/3850005/diff/1/2#newcode145
src/arm/regexp-macro-assembler-arm.cc:145: Label inside_string;
Looks superfluous!

http://codereview.chromium.org/3850005/diff/1/2#newcode931
src/arm/regexp-macro-assembler-arm.cc:931: Label after_position;
This could be a NearLabel.

There are more places like this, so it might be worth going through the file to
find them in a separate change.

http://codereview.chromium.org/3850005/diff/1/2#newcode935
src/arm/regexp-macro-assembler-arm.cc:935: LoadCurrentCharacterUnchecked(-1, 1);
The 'Unchecked' part deserves a comment.

http://codereview.chromium.org/3850005/diff/1/6
File src/bytecodes-irregexp.h (right):

http://codereview.chromium.org/3850005/diff/1/6#newcode92
src/bytecodes-irregexp.h:92: V(SET_CURRENT_POSITION_FROM_END, 48, 4) /* bc8
offset24 uint32              */
Something wrong here.  If it has an offset24 and a uint32 then it must be 8
bytes long, not 4.

http://codereview.chromium.org/3850005/diff/1/7
File src/ia32/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/3850005/diff/1/7#newcode968
src/ia32/regexp-macro-assembler-ia32.cc:968: Label after_position;
NearLabel

http://codereview.chromium.org/3850005/diff/1/7#newcode972
src/ia32/regexp-macro-assembler-ia32.cc:972: LoadCurrentCharacterUnchecked(-1,
1);
Comment.

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

http://codereview.chromium.org/3850005/diff/1/10#newcode5247
src/jsregexp.cc:5247: max_length < kMaxBacksearchLimit) {
Why not just compare against kInfinity?

http://codereview.chromium.org/3850005/diff/1/16
File src/x64/regexp-macro-assembler-x64.cc (right):

http://codereview.chromium.org/3850005/diff/1/16#newcode1057
src/x64/regexp-macro-assembler-x64.cc:1057: Label after_position;
NearLabel

http://codereview.chromium.org/3850005/diff/1/16#newcode1061
src/x64/regexp-macro-assembler-x64.cc:1061: LoadCurrentCharacterUnchecked(-1,
1);
Comment.

http://codereview.chromium.org/3850005/diff/1/18
File test/mjsunit/regexp.js (right):

http://codereview.chromium.org/3850005/diff/1/18#newcode594
test/mjsunit/regexp.js:594: // Check that end-anchored regexps are optimized
correctly.
I'd like to see an example with a very long regexp and a short string.  And an
other example where the startIndex is near the end of the string.

How about $ inside a disjunction and regexps that are anchored in both ends?

[Lasse Reichstein, 2010-10-19 09:41:30]

http://codereview.chromium.org/3850005/diff/1/2
File src/arm/regexp-macro-assembler-arm.cc (right):

http://codereview.chromium.org/3850005/diff/1/2#newcode145
src/arm/regexp-macro-assembler-arm.cc:145: Label inside_string;
Removed.

http://codereview.chromium.org/3850005/diff/1/2#newcode931
src/arm/regexp-macro-assembler-arm.cc:931: Label after_position;
Changed here.

http://codereview.chromium.org/3850005/diff/1/2#newcode935
src/arm/regexp-macro-assembler-arm.cc:935: LoadCurrentCharacterUnchecked(-1, 1);
Comment added.

http://codereview.chromium.org/3850005/diff/1/6
File src/bytecodes-irregexp.h (right):

http://codereview.chromium.org/3850005/diff/1/6#newcode92
src/bytecodes-irregexp.h:92: V(SET_CURRENT_POSITION_FROM_END, 48, 4) /* bc8
offset24 uint32              */
Changed to /* bc8 idx24 */
I changed the representation at some point but forgot the comment.

http://codereview.chromium.org/3850005/diff/1/7
File src/ia32/regexp-macro-assembler-ia32.cc (right):

http://codereview.chromium.org/3850005/diff/1/7#newcode968
src/ia32/regexp-macro-assembler-ia32.cc:968: Label after_position;
On 2010/10/19 08:56:19, Erik Corry wrote:
> NearLabel

Done.

http://codereview.chromium.org/3850005/diff/1/7#newcode972
src/ia32/regexp-macro-assembler-ia32.cc:972: LoadCurrentCharacterUnchecked(-1,
1);
On 2010/10/19 08:56:19, Erik Corry wrote:
> Comment.

Done.

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

http://codereview.chromium.org/3850005/diff/1/10#newcode5247
src/jsregexp.cc:5247: max_length < kMaxBacksearchLimit) {
The extra check at the start introduces a slight overhead, independently of the
input string.
For all input strings shorter than the max_length, the overhead is wasted (we
won't do anything). 
I.e., if the max_length is large, it's likely that the extra code is pure
overhead.
Also, making the max less than 24 bits allows me to use only one word for the
bytecode.

I expect regexps with a very long, but finite, max_length to be very rare (it
doesn't contain any * or + quantifiers, but yet it allows very large matches).

http://codereview.chromium.org/3850005/diff/1/16
File src/x64/regexp-macro-assembler-x64.cc (right):

http://codereview.chromium.org/3850005/diff/1/16#newcode1057
src/x64/regexp-macro-assembler-x64.cc:1057: Label after_position;
On 2010/10/19 08:56:19, Erik Corry wrote:
> NearLabel

Done.

http://codereview.chromium.org/3850005/diff/1/16#newcode1061
src/x64/regexp-macro-assembler-x64.cc:1061: LoadCurrentCharacterUnchecked(-1,
1);
On 2010/10/19 08:56:19, Erik Corry wrote:
> Comment.

Done.

http://codereview.chromium.org/3850005/diff/1/18
File test/mjsunit/regexp.js (right):

http://codereview.chromium.org/3850005/diff/1/18#newcode594
test/mjsunit/regexp.js:594: // Check that end-anchored regexps are optimized
correctly.
Adding long-regexp/short-string and $ inside disjunction.
Other cases are already accounted for.

http://codereview.chromium.org/3850005/diff/1/18#newcode607
test/mjsunit/regexp.js:607: re.lastIndex = 5;
Start-index close to end is here.

http://codereview.chromium.org/3850005/diff/1/18#newcode612
test/mjsunit/regexp.js:612: var re = /^(?:a|bc)g$/g;
Anchored at both ends is here.