Implement a 'trial parse' step, that will abort pre-parsing excessively

Implement a 'trial parse' step, that will abort pre-parsing excessively
long and trivial functions, so that they can be eagerly compiled after all.
This essentially allows the parser to renege on its earlier decision to
lazy-parse, if additional information suggests it was a bad decision.

BUG=chromium:470930
LOG=Y

Committed: https://crrev.com/be9570027f34f8dbf60a7b530fe2499ff52c1a3d
Cr-Commit-Position: refs/heads/master@{#28252}

[vogelheim, 2015-04-22 15:07:16]

vogelheim@chromium.org changed reviewers:
+ jochen@chromium.org, marja@chromium.org

[vogelheim, 2015-04-22 15:07:19]

I'm not quite done, but this should be close to its final form. I'd be happy if
you could have a look, now-ish.

I tried hard to make this look pretty and minimally intrusive; please let me
know in case I wasn't successful.

@jochen: For general opinion.
@marja: Since this tramples all over the parser, please have a look.
@both: How should I test this?

[marja, 2015-04-22 16:40:56]

Generally LG, but I think this can be simpler - either that or I'm missing
something (pls tell me what I'm missing). :)

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc
File src/parser.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc#newcode4057
src/parser.cc:4057: //   condition: is_lazily_parsed (but none of the conditions
below)
... is this the same as "couldn't trial parse because cannot set bookmark" or
are there some othere reasons why we "have not tried trial parsing"?

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc#newcode4064
src/parser.cc:4064: //   action: eager parse.
The logic sounds correct, but... isn't there a simpler way to express it? I'm
assuming we can know early that we cannot trial parse (and that the only reason
for that is not being able to set the bookmark).

So after we have trial parsed (and we know we can successfully do it),
HasBeenReset and HasBeenSet are complements, right, the first means "trial
aborted" and the latter "trial finished"?

How about:

if (is_lazily_parsed) {
  if (bookmark.Set()) { // can set bookmarks
    Skip(..); // trial
    if (trial parsing aborted) {
      is_lazily_parsed = false;
    } // else: trial parsing finished, we're done
  } else {
    Skip(...); // normal lazy parsing without bookmark
  }
}
if (!is_lazily_parsed) {
  ParseEager(..);
}

That puts the trial parsing logic into the same control flow, so we don't need
to try to figure out in retrospect whether we even tried trial parsing or not.

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc#newcode4068
src/parser.cc:4068: //     But this will cause the compiler to actually compile
it.
... we might want to use the non-hacky way of saying "please compile this"
already in this CL...

https://codereview.chromium.org/1102523003/diff/1/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/preparser.cc#newcode246
src/preparser.cc:246: if (count_lines++ > 200 && bookmark->CanReset()) {
Hmm, I find this is quite a late point to check whether we can reset the
bookmark... (and my other comments were also assuming we can know it pretty
early). The code might get cleaner if we can know that early. Is there some
reason why we couldn't? So here we'd only have the bookmark in those cases where
we can reset.

https://codereview.chromium.org/1102523003/diff/1/src/scanner-character-strea...
File src/scanner-character-streams.h (right):

https://codereview.chromium.org/1102523003/diff/1/src/scanner-character-strea...
src/scanner-character-streams.h:85: class ExternalStreamingStream : public
BufferedUtf16CharacterStream {
Pls add a todo here to implement bookmarking for this stream too; it should be
easy, since we can just ask the embedder to give us data from a given position.
(That might require transmitting the position in the API..)

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc
File src/scanner.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc#newcode34
src/scanner.cc:34: bool Utf16CharacterStream::CanResetToBookmark() { return
false; }
I don't get why we need CanResetToBookmark; if SetBookmark returns true, we can
assume that it successfully set the bookmark and can later successfully reset to
it, no?

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc#newcode35
src/scanner.cc:35: bool Utf16CharacterStream::ResetToBookmark() { return false;
}
Also here, if we successfully set a bookmark, I'd assume we can reset to it, and
this function has no way of saying "ha ha, we actually cannot" and returning
false.

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc#newcode37
src/scanner.cc:37: 
... or is there some logic here like "this bookmark has already been set to
something and thus we cannot set it to something else"?

(But that could be expressed in a more direct way.)

https://codereview.chromium.org/1102523003/diff/1/src/scanner.h
File src/scanner.h (right):

https://codereview.chromium.org/1102523003/diff/1/src/scanner.h#newcode765
src/scanner.h:765: LiteralBuffer bookmark_raw_literal_;
Hmm, why can't we just retroactively recover all these once we have set the
stream into the right position?

[vogelheim, 2015-04-22 17:08:35]

Thanks for the quick review.

Not a full answer here, just a quick reply on some of the issues you raised:

- I assumed a ResetToBookmark may fail. If I drop that assumption, the code
becomes easier.
- I'm not sure about the scanner state. That /should/ be easy, but it didn't
look that way to me, so I took an admittedly brute-force-ish route of just
saving all the state. If there's a better way, I'd need a hint... :)

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc
File src/parser.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc#newcode4057
src/parser.cc:4057: //   condition: is_lazily_parsed (but none of the conditions
below)
On 2015/04/22 16:40:55, marja wrote:
> ... is this the same as "couldn't trial parse because cannot set bookmark" or
> are there some othere reasons why we "have not tried trial parsing"?

Yes. Cannot bookmark, or !is_lazily_parsed

https://codereview.chromium.org/1102523003/diff/1/src/parser.cc#newcode4064
src/parser.cc:4064: //   action: eager parse.
On 2015/04/22 16:40:55, marja wrote:
> The logic sounds correct, but... isn't there a simpler way to express it? I'm
> assuming we can know early that we cannot trial parse (and that the only
reason
> for that is not being able to set the bookmark).
> 
> So after we have trial parsed (and we know we can successfully do it),
> HasBeenReset and HasBeenSet are complements, right, the first means "trial
> aborted" and the latter "trial finished"?
> 
> How about:
> 
> if (is_lazily_parsed) {
>   if (bookmark.Set()) { // can set bookmarks
>     Skip(..); // trial
>     if (trial parsing aborted) {
>       is_lazily_parsed = false;
>     } // else: trial parsing finished, we're done
>   } else {
>     Skip(...); // normal lazy parsing without bookmark
>   }
> }
> if (!is_lazily_parsed) {
>   ParseEager(..);
> }
> 
> That puts the trial parsing logic into the same control flow, so we don't need
> to try to figure out in retrospect whether we even tried trial parsing or not.

That'd work as well. I'll change it.

https://codereview.chromium.org/1102523003/diff/1/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/preparser.cc#newcode246
src/preparser.cc:246: if (count_lines++ > 200 && bookmark->CanReset()) {
On 2015/04/22 16:40:55, marja wrote:
> Hmm, I find this is quite a late point to check whether we can reset the
> bookmark... (and my other comments were also assuming we can know it pretty
> early). The code might get cleaner if we can know that early. Is there some
> reason why we couldn't? So here we'd only have the bookmark in those cases
where
> we can reset.

The code certainly gets a lot cleaner if we can predict whether we can reset or
not.

I did this on purpose, to support streaming parsing: When you have an
implementation that looks at the source block-by-block, then it's fully well
possible that you can reset while you're still in the same block, but you can't
if you've progressed to a new block in the mean time.

If we don't want to support this, we can make both API & implementation simpler
by assuming we can always reset if we have successfully set a bookmark.

Not sure which way we'd want to go...

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc
File src/scanner.cc (right):

https://codereview.chromium.org/1102523003/diff/1/src/scanner.cc#newcode37
src/scanner.cc:37: 
On 2015/04/22 16:40:56, marja wrote:
> ... or is there some logic here like "this bookmark has already been set to
> something and thus we cannot set it to something else"?
> 
> (But that could be expressed in a more direct way.)

(answered elsewhere:) The idea is to support a stream implementation that truly
streams, where you can reset while you're still in the same block, but not when
you're on a new one.

Maybe we simply shouldn't do this, and make any 'streaming' implementation hold
on to past blocks, at least while they have a bookmark set?

https://codereview.chromium.org/1102523003/diff/1/src/scanner.h
File src/scanner.h (right):

https://codereview.chromium.org/1102523003/diff/1/src/scanner.h#newcode765
src/scanner.h:765: LiteralBuffer bookmark_raw_literal_;
On 2015/04/22 16:40:56, marja wrote:
> Hmm, why can't we just retroactively recover all these once we have set the
> stream into the right position?

Yeah... I went a bit trial-and-error here and didn't see an /obvious/ way to do
this. I didn't see a hard-and-fast rule when content goes into which literal
buffer. Also, using the stream's push back functionality can create a state that
may not be recoverable by merely going to the old position.

Are there any invariants about the content of the literal buffers? Can I skip
back a bit more, and then read forward until I'm at the right position?

[marja, 2015-04-22 17:51:00]

I'll have a closer look at your comments tomorrow, just two quick replies.

Re: streaming; we have all the data on the Blink side ResourceBuffer, it's not a
problem to reset to an earlier data point even if it's not in the same buffer.
So I think you can drop the assumption that resetting to a bookmark can fail. If
none of the current impls has that property, let's just keep it simple :)

Re: scanner state; I'd assume we always set the bookmark into a place that is
between tokens, so, not inside a string or an identifier. And can't we just then
do the same thing which Scanner does when it begins scanning (so, Next() or
something to read the next token and the possible associated literal data)?

And can't we forget all potentially pushed back stuff when we reset?

[marja, 2015-04-22 17:52:34]

... and when we reset we'd basically ask the stream to fill the buffer fresh
(from whatever position)...

I might be undercomplicating this. :)

[vogelheim, 2015-04-23 13:30:15]

[from more offline discussion / debugging:]

The scanner/stream state at the point of bookmarking looks something like this:

characters: ... function bla() { var x = blubb; ...
            ...................C.NNNc|...............
with:  C: current_, token LBRACE
       N: next_, token VAR
       c: c0_, the space after N
       | : the position in the underlying stream.

In other words, current_, next_, c0_ cache the state *before* the current stream
position. So I either need to copy all of them, or I need to be able to rewind
the stream behind its current position and then re-parse those last two tokens.
While both are certainly doable, doing the latter isn't going to be particularly
pretty.


On fail-able ResetToBookmark: This shouldn't be necessary. None of the current
implementations needs it. The streaming implementation will need to change the
blink-side API to be able to reset, though.

[marja, 2015-04-23 13:52:06]

To continue: as discussed offline, IMO it's OK to store the current and next
token so, since we now know why exactly it's needed (the stream below the
scanner has advanced past them).

[vogelheim, 2015-04-23 15:08:29]

Addressed:
- ResetToBookmark cannot fail.
- Some simplification (... I hope ...) around setting
  the bookmark, the reset condition, and the token copy
  mechanics.

More changes are coming, particularly removal of the "parenthesized" hack.

[vogelheim, 2015-04-24 11:50:53]

PTAL. I changed things quite a bit...

[marja, 2015-04-24 12:08:13]

lgtm, much clearer now!

Pls run perf tryjobs before landing.

https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
src/preparser.cc:211: int count_lines = 0;
Nit: Not really lines, but statements

https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
src/preparser.cc:258: // Our current definition of 'long and trivial) is:
Nit: ) -> '

https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
src/preparser.cc:261: if (maybe_reset && (!starts_with_identifier ||
++count_lines > 200)) {
IMO clearer:

if (!starts_with_identifier) maybe_reset = false;

if (maybe_reset && ++count_lines > 200) {
  bookmark->Reset();
  return;
}

https://codereview.chromium.org/1102523003/diff/40001/src/scanner.h
File src/scanner.h (right):

https://codereview.chromium.org/1102523003/diff/40001/src/scanner.h#newcode769
src/scanner.h:769: uc32 bookmark_c0_;
Pls add a comment here about why we need to store the literals (at the point
where we set a bookmark, scanning has already advanced, and we need to recover
the literals, etc.)

[vogelheim, 2015-04-30 13:02:57]

On 2015/04/24 12:08:13, marja (ooo - no reviews) wrote:
> lgtm, much clearer now!
> 
> Pls run perf tryjobs before landing.
> 
> https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc
> File src/preparser.cc (right):
> 
>
https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
> src/preparser.cc:211: int count_lines = 0;
> Nit: Not really lines, but statements

Done.

>
https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
> src/preparser.cc:258: // Our current definition of 'long and trivial) is:
> Nit: ) -> '

Done.

>
https://codereview.chromium.org/1102523003/diff/40001/src/preparser.cc#newcod...
> src/preparser.cc:261: if (maybe_reset && (!starts_with_identifier ||
> ++count_lines > 200)) {
> IMO clearer:
> 
> if (!starts_with_identifier) maybe_reset = false;
> 
> if (maybe_reset && ++count_lines > 200) {
>   bookmark->Reset();
>   return;
> }

Hmm. This was a bit of a micro-optimization, in that I expect this logic to be
'approximately never' to be executed, and so I wanted to have it all inside a
single if to keep its runtime impact minimal. Admittedly, this is a
micro-optimization that I'm not entirely sure about its worthwhile.

> https://codereview.chromium.org/1102523003/diff/40001/src/scanner.h
> File src/scanner.h (right):
> 
> https://codereview.chromium.org/1102523003/diff/40001/src/scanner.h#newcode769
> src/scanner.h:769: uc32 bookmark_c0_;
> Pls add a comment here about why we need to store the literals (at the point
> where we set a bookmark, scanning has already advanced, and we need to recover
> the literals, etc.)

Done.

[jochen (gone - plz use gerrit), 2015-04-30 13:20:18]

lgtm with a bunch of nits

https://codereview.chromium.org/1102523003/diff/140001/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/1102523003/diff/140001/src/preparser.cc#newco...
src/preparser.cc:261: if (maybe_reset && (!starts_with_identifier ||
++count_statements > 200)) {
can we define 200 has a const?

https://codereview.chromium.org/1102523003/diff/140001/src/scanner-character-...
File src/scanner-character-streams.cc (right):

https://codereview.chromium.org/1102523003/diff/140001/src/scanner-character-...
src/scanner-character-streams.cc:149: pos_ = bookmark_;
why no DCHECK here?

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h
File src/scanner.h (right):

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h#newcode374
src/scanner.h:374: };
disallow copy/assign

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h#newcode758
src/scanner.h:758: // - bookmark_c0_ == -1: No bookmark has been set.
how about defining an enum for -1 and -2?

[vogelheim, 2015-04-30 15:35:06]

https://codereview.chromium.org/1102523003/diff/140001/src/preparser.cc
File src/preparser.cc (right):

https://codereview.chromium.org/1102523003/diff/140001/src/preparser.cc#newco...
src/preparser.cc:261: if (maybe_reset && (!starts_with_identifier ||
++count_statements > 200)) {
On 2015/04/30 13:20:18, jochen wrote:
> can we define 200 has a const?

Done.

https://codereview.chromium.org/1102523003/diff/140001/src/scanner-character-...
File src/scanner-character-streams.cc (right):

https://codereview.chromium.org/1102523003/diff/140001/src/scanner-character-...
src/scanner-character-streams.cc:149: pos_ = bookmark_;
On 2015/04/30 13:20:18, jochen wrote:
> why no DCHECK here?

Done.

No big reason, really. For whatever reason I here decided to initialize the
bookmark with 'start_position', so there was never an 'illegal' value in it.
This way, it puts more effort into checking the contract.

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h
File src/scanner.h (right):

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h#newcode374
src/scanner.h:374: };
On 2015/04/30 13:20:18, jochen wrote:
> disallow copy/assign

Done.

https://codereview.chromium.org/1102523003/diff/140001/src/scanner.h#newcode758
src/scanner.h:758: // - bookmark_c0_ == -1: No bookmark has been set.
On 2015/04/30 13:20:18, jochen wrote:
> how about defining an enum for -1 and -2?

Done.

[vogelheim, 2015-05-05 16:32:20]

vogelheim@chromium.org changed reviewers:
- marja@chromium.org

[vogelheim, 2015-05-05 16:32:20]

PTAL.

The previous implementation would inadvertently 'set_should_eager_compile()' a
lot more functions than merely the discovered initialization-like functions.
This latest change fixes that at the cost of an additional single-use flag in
FunctionLiteral. Not pretty, but it fixes the splay-latency regression.

(Side note: Looking back, that was actually a rather big mistake. I'm surprised
only spay-latency caught this.)

[vogelheim, 2015-05-05 16:32:24]

PTAL.

The previous implementation would inadvertently 'set_should_eager_compile()' a
lot more functions than merely the discovered initialization-like functions.
This latest change fixes that at the cost of an additional single-use flag in
FunctionLiteral. Not pretty, but it fixes the splay-latency regression.

(Side note: Looking back, that was actually a rather big mistake. I'm surprised
only spay-latency caught this.)

[jochen (gone - plz use gerrit), 2015-05-05 18:17:59]

Still lgtm

[vogelheim, 2015-05-06 10:19:30]

The CQ bit was checked by vogelheim@chromium.org

[vogelheim, 2015-05-06 10:19:30]

The patchset sent to the CQ was uploaded after l-g-t-m from marja@chromium.org
Link to the patchset: https://codereview.chromium.org/1102523003/#ps180001
(title: "Use a seperate 'hint' bit for "to be executed once" code aging.")

[commit-bot: I haz the power, 2015-05-06 10:19:39]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1102523003/180001

[commit-bot: I haz the power, 2015-05-06 10:21:25]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2015-05-06 10:21:40]

Patchset 10 (id:??) landed as
https://crrev.com/be9570027f34f8dbf60a7b530fe2499ff52c1a3d
Cr-Commit-Position: refs/heads/master@{#28252}