Irregexp: Added derived knowledge of whether we are at the start of input.

Trace contains information about whether we know that we are at the start of input.
Choice nodes may know that they are never not at the start of input.
This can remove start_of_input assertions in cases where they are statically known to fail.
The initial loop is unrolled once if the regexp might check for the start of input. Only the first iteration may be at the start, the following loop knows that it isn't.

[Lasse Reichstein, 2009-02-02 14:53:05]

Semi-tricky review.

[Erik Corry, 2009-02-02 21:22:01]

Excellent stuff.  I assume there are no regressions of performance or
correctness and that it lints.

Does the not at start flag need to be on all RegExpNodes or could we just put it
on the ChoiceNodes and their children?

http://codereview.chromium.org/19539/diff/1/2
File src/ast.cc (right):

http://codereview.chromium.org/19539/diff/1/2#newcode257
Line 257: if (node->max_match() > 0) { return false; }
It's unlikely to make any difference, but this should probably be min_match.  I
think there should be a comment explaining why it makes any sense at all to look
at nodes other than the first one (the first ones could be lookaheads or other
zero-length nodes followed by a ^).

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

http://codereview.chromium.org/19539/diff/1/5#newcode3156
Line 3156: bool all_omitted = true;
I think you can omit this if you implement the suggestions below.

http://codereview.chromium.org/19539/diff/1/5#newcode3196
Line 3196: } else if (alt_gen->quick_check_details.cannot_match()) {
You can emit the goto fail here if i == choice_count - 1

http://codereview.chromium.org/19539/diff/1/5#newcode3971
Line 3971: 0, new_max, is_greedy, body, compiler, on_success, not_at_start);
not_at_start can be true here since we know that min > 0 and body can't be
empty.

http://codereview.chromium.org/19539/diff/1/5#newcode4839
Line 4839: // Unroll once, and tell the loop that it's not at the start of the
input.
we just told the loop it wasn't at the start

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

http://codereview.chromium.org/19539/diff/1/6#newcode1199
Line 1199: cp_offset_ == 0 &&
A trace is not trivial unless at_start_ is UNKNOWN.

http://codereview.chromium.org/19539/diff/1/7
File src/parser.cc (right):

http://codereview.chromium.org/19539/diff/1/7#newcode3611
Line 3611: new RegExpAssertion(RegExpAssertion::START_OF_LINE));
I think you should set_contains_anchor here too.  The code generation for
START_OF_LINE can benefit from knowing whether or not we can be at the start
too.

[Lasse Reichstein, 2009-02-03 11:18:19]

No expected performance regressions. 
The not_at_start field is only on ChoiceNode

http://codereview.chromium.org/19539/diff/1/2
File src/ast.cc (right):

http://codereview.chromium.org/19539/diff/1/2#newcode257
Line 257: if (node->max_match() > 0) { return false; }
It will actually work for min_match too.
We currently compute whether the expression contain an initial anchor.  If we
change our goal to computing whether the expression contains an unguarded anchor
(i.e., one that must definitly be matched for the expression to match), then it
will be effectively the same, and we can even ignore the min_match check
entirely - however, on non-stupid expressions, this check will likely save some
time.

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

http://codereview.chromium.org/19539/diff/1/5#newcode3156
Line 3156: bool all_omitted = true;
On 2009/02/02 21:22:01, Erik Corry wrote:
> I think you can omit this if you implement the suggestions below.

Done.

http://codereview.chromium.org/19539/diff/1/5#newcode3196
Line 3196: } else if (alt_gen->quick_check_details.cannot_match()) {
And I should. I think it's a bug that it doesn't do anything special if the last
case is omitted.

http://codereview.chromium.org/19539/diff/1/5#newcode3971
Line 3971: 0, new_max, is_greedy, body, compiler, on_success, not_at_start);
On 2009/02/02 21:22:01, Erik Corry wrote:
> not_at_start can be true here since we know that min > 0 and body can't be
> empty.

Done.

http://codereview.chromium.org/19539/diff/1/5#newcode4839
Line 4839: // Unroll once, and tell the loop that it's not at the start of the
input.
Ah, yes. Refactoring breaks comments.

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

http://codereview.chromium.org/19539/diff/1/6#newcode1199
Line 1199: cp_offset_ == 0 &&
On 2009/02/02 21:22:01, Erik Corry wrote:
> A trace is not trivial unless at_start_ is UNKNOWN.

Done.

http://codereview.chromium.org/19539/diff/1/7
File src/parser.cc (right):

http://codereview.chromium.org/19539/diff/1/7#newcode3611
Line 3611: new RegExpAssertion(RegExpAssertion::START_OF_LINE));
I'm not sure the extra overhead of unrolling the initial loop is worth avoiding
one extra CheckNotAtStart.
Unless there is a good reason to optimize "start of line" assertions, I prefer
to keep the concepts separate.