* Generate quick checks based on mask and compare for...

* Generate quick checks based on mask and compare for
  the alternatives in a choice node.  The quick checks
  are conservative in the sense that they only detect
  failure with certainty.  Checks can do 2 or 4 characters
  at a time.
* Inline the quick checks to allow the alternatives to
  be checked without branching in the common case where
  they fail.

Committed: http://code.google.com/p/v8/source/detail?r=1005

[Christian Plesner Hansen, 2008-12-18 09:52:26]

My poor head!  This could would benefit from some more documentation -- there's
a lot of bit fiddling, flags and conditions and it's very hard to understand the
details of what's going on, even when you understand the big picture.

http://codereview.chromium.org/14194/diff/1/7
File src/interpreter-irregexp.cc (right):

http://codereview.chromium.org/14194/diff/1/7#newcode89
Line 89: PrintF("pc = %02x, sp = %d, curpos = %d, curchar = %08x%s%c%c, bc =
%s",
How about using two different format strings, one for printable and one for
non-printable.  This is fairly hard to read.

http://codereview.chromium.org/14194/diff/1/7#newcode249
Line 249: current_char = (subject[pos] | (next << (8 * sizeof(Char))));
You could use kBitsPerByte to make it obvious what this '8' signifies.  Also,
the name current_char is becoming misleading.

http://codereview.chromium.org/14194/diff/1/7#newcode279
Line 279: ASSERT(sizeof(Char) == 1);
Could be a static check.

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

http://codereview.chromium.org/14194/diff/1/11#newcode864
Line 864: } else {
Could be folded into 'else if (matches->...)'

http://codereview.chromium.org/14194/diff/1/11#newcode1949
Line 1949: v |= v >> 1;
I'm terribly annoyed that I can't think of a simpler way to do this.  In any
case it needs a 'v |= v >> 16' to work.

http://codereview.chromium.org/14194/diff/1/11#newcode2056
Line 2056: for (int k = 0; k < elms_->length(); k++) {
Some more documentation of what's going on might be good -- in the interest of
decreasing our truck count.

http://codereview.chromium.org/14194/diff/1/11#newcode2101
Line 2101: &(details->positions[characters_filled_in]);
Accessor?

http://codereview.chromium.org/14194/diff/1/11#newcode2197
Line 2197: for (int j = preloaded ? 0 : quarks.length() - 1; j >= 0; j--) {
These loops make my brain hurt ("It'll have to come out!").  Maybe a comment
about what 'preloaded' signifies and why we only have to process j=0 if it is
set?

http://codereview.chromium.org/14194/diff/1/11#newcode2267
Line 2267: TextElement elm = elms_->at(element_count - 1);
You could just use ->last().

http://codereview.chromium.org/14194/diff/1/11#newcode2537
Line 2537: AlternativeGeneration a_few_alt_gens[kAFew];
Missing trailing underscore.

http://codereview.chromium.org/14194/diff/1/11#newcode2586
Line 2586: *   \    F    |
Does it lint?

http://codereview.chromium.org/14194/diff/1/11#newcode2718
Line 2718: goto inline_full_check;
How about setting a variable instead, ending the 'else' part before the label
and then making the full check generation conditional on the variable?  I dinnae
like goto.

http://codereview.chromium.org/14194/diff/1/5
File src/jsregexp.h (right):

http://codereview.chromium.org/14194/diff/1/5#newcode631
Line 631: for (int i = 0; i < 4; i++) {
Why not just give Position a constructor, then the array will be initialized
automatically.

http://codereview.chromium.org/14194/diff/1/5#newcode745
Line 745: virtual int EatsAtLeast(int recursion_depth);
This should probably remain pure virtual so we're sure to consider for each
subclasses how to calculate this.  That goes for GetQuickCheckDetails too.

http://codereview.chromium.org/14194/diff/1/5#newcode845
Line 845: enum TextEmitPassType {
Enum values should be upper underscore case.  Also, what's that '}' doing on the
same line as the last enum value?

http://codereview.chromium.org/14194/diff/1/5#newcode1020
Line 1020: virtual int EatsAtLeast(int recursion_depth);  // Returns 0.
Since loop choice nodes now know which alternative is their continue node maybe
we can get a less conservative estimate than this.

[Erik Corry, 2008-12-19 10:17:15]

Here's a new upload.  I cleaned up some stuff putting the details of the quick
check that has been performed into the GenerationVariant object instead of
having a pointer.  Since GenerationVariants are copied shallowly with the
expectation that the copies are independent afterwards this seemed more healthy.
 Also addressed review comments and added more explanation in the code.

http://codereview.chromium.org/14194/diff/1/7
File src/interpreter-irregexp.cc (right):

http://codereview.chromium.org/14194/diff/1/7#newcode279
Line 279: ASSERT(sizeof(Char) == 1);
On 2008/12/18 09:52:26, Christian Plesner Hansen wrote:
> Could be a static check.

I think that would provoke the template implementation of the compilers a little
too much.

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

http://codereview.chromium.org/14194/diff/1/11#newcode1949
Line 1949: v |= v >> 1;
On 2008/12/18 09:52:26, Christian Plesner Hansen wrote:
> I'm terribly annoyed that I can't think of a simpler way to do this.  In any
> case it needs a 'v |= v >> 16' to work.

It's only intended for use with 16 bit characters but it's easier to add the
extra or operation than to think of a name that indicates that.

http://codereview.chromium.org/14194/diff/1/11#newcode2586
Line 2586: *   \    F    |
On 2008/12/18 09:52:26, Christian Plesner Hansen wrote:
> Does it lint?

Funnily enough it does, yes.

http://codereview.chromium.org/14194/diff/1/5
File src/jsregexp.h (right):

http://codereview.chromium.org/14194/diff/1/5#newcode1020
Line 1020: virtual int EatsAtLeast(int recursion_depth);  // Returns 0.
On 2008/12/18 09:52:26, Christian Plesner Hansen wrote:
> Since loop choice nodes now know which alternative is their continue node
maybe
> we can get a less conservative estimate than this.

I think this has to wait until we know the minimum number of characters a loop
body can match.

[Christian Plesner Hansen, 2008-12-19 11:51:49]

Lgtm!