New issue
Advanced search Search tips

Issue 7178 link

Starred by 2 users

Issue metadata

Status: Fixed
Owner:
Closed: Mar 2018
Cc:
Components:
HW: ----
NextAction: ----
OS: ----
Priority: ----
Type: Bug



Sign in to add a comment

Remove AST numbering

Project Member Reported by leszeks@chromium.org, Dec 7 2017

Issue description

AST numbering is an AST post-processing pass that:

  * Assigns suspend ids and suspend counts to nodes inside generators
  * Does some Object/Array literal initialization
  * Collects eager compilation literals
  * Disables optimization of native function literals

These tasks could be done during parsing, avoiding the need for this AST walk.

 
Yes please! One thing to keep in mind - our current suspend id's need to be allocated in-order of the bytecode (or at least contiguous within loop boundaries), however the parser doesn't run through the code in-order, so this might end up being a bit tricky.

Also, I did previously try to do eager function compilation collection during parsing and it also ended up trying to compile functions which were actually nested in lazy functions (which broke things) so you will need to be careful to avoid that (particularly when scope analysis re-scopes things about :)).
How did you do the eager function collection? I was planning on passing a ZoneList<FunctionLiteral*> through ParseFunction, but it sounds like that might not work?

Comment 3 by caitp@chromium.org, Dec 7 2017

> Assigns suspend ids and suspend counts to nodes inside generators

> Yes please! One thing to keep in mind - our current suspend id's need to be allocated in-order of the bytecode (or at least contiguous within loop boundaries), however the parser doesn't run through the code in-order, so this might end up being a bit tricky.

Doesn't the register optimizer already re-arrange bytecodes to some degree? Inserting
jump tables for suspends during that pass over the bytecodes would avoid that problem,
_and_ avoid having to record suspend IDs in AST nodes.

*reading over it, I guess the optimizer still works in a single pass...* --- But still, a flat run through bytecodes may be faster than making the parser more complicated, and it would get rid of the annoying suspend ID tracking.
Cc: caitp@chromium.org
Just to check Caitlin, your suggestion is to generate bytecode first with empty jump tables for the suspend ids, and then do a second pass over the bytecode which fills those jump tables in? We couldn't do a pre-pass over the bytecode before generating the bytecode because, well, it's not generated yet.

Maybe another possibility is tracking suspend *counts* per node, and generating suspend ids in the bytecode? WDYT?
re #2: Yes that was roughly what I did (you would also need to pass it to ParseProgram and ParseOnBackground). The issue is more deciding whether to add a function literal to the list when it is marked as eager. If it is nested within a lazy function then it shouldn't actually be added to the eager compile list even if it's marked to be eagerly compiled (it will be eagerly compiled when the lazy function is compiled). The issue I think I was getting was that scope analysis sometimes re-parents things so the function appears to be within an eager function when marked, but then get's re-parented to a lazy function, and the compiler would crash when compiling the eager function since it's lazy parent wasn't compiled.

re #3: We don't actually re-arrange any bytecodes in the register optimizer, we just defer emitting some ldar / sdar instructions until they are actually needed (which happens during the same single pass of bytecode generation).

re #4: Tracking suspend counts per node (or at least per IterationStatement node) was the idea I had, however rewriting of the ast makes this a bit tricky.

Comment 6 by ca...@igalia.com, Dec 7 2017

> rewriting of the AST makes this a bit tricky

But, we can get rid of AST rewriting almost entirely (entirely if we do the eval rewriting in BytecodeGenerator)
#eager literals

I'm not sure I understand -- either we run PreParser::ParseFunction or Parser::ParseFunction, surely the latter is known to be eagerly parsed? Or is it the case that we might eagerly parse, but still can't eagerly compile? Would it be enough to sanity check the scopes of functions in the eagerly_parsed list, and check if they're eager all the way up?

# tracking suspend counts

AFAIR, the rewriter doesn't do much more than inserting a result variable assignment. I don't think suspend counts should change? Otherwise, maybe we can just keep track of a diff of suspend counts and bubble it up during the rewrite.
> Or is it the case that we might eagerly parse, but still can't eagerly compile

Yes, when I tried it this was exactly the issue - we had to eagerly compile some functions but couldn't eagerly compile (since parent functions were lazy compiled). Not sure if this is still the case.

> AFAIR, the rewriter doesn't do much more than inserting a result variable assignment

I'm talking about pattern-rewriter.cc, not rewriter.cc. As Caitlin says we can gradually move towards getting rid of the AST rewriting, but we might not get rid of it all so we should have a plan for how to do this if we still need ast-rewriting.
Project Member

Comment 9 by bugdroid1@chromium.org, Dec 18 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/c9d88eed628119f4e55e44cf3bb5ea2385f6356a

commit c9d88eed628119f4e55e44cf3bb5ea2385f6356a
Author: Leszek Swirski <leszeks@chromium.org>
Date: Mon Dec 18 16:14:47 2017

[parser] Move literal initialization to parser

Move literal initialization out of AST numbering and into the parser.
The initialization includes setting the depth and flags of Object and
Array literals, and calculating the emit store of object literals.

Bug:  v8:7178 
Change-Id: I9af59a2fea44f8a1adcc5a0261f29ce97fa8da92
Reviewed-on: https://chromium-review.googlesource.com/814634
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Reviewed-by: Marja Hölttä <marja@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50168}
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/ast/ast-numbering.cc
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/ast/ast.cc
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/ast/ast.h
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/parsing/parser-base.h
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/parsing/parser.h
[modify] https://crrev.com/c9d88eed628119f4e55e44cf3bb5ea2385f6356a/src/parsing/preparser.h

Project Member

Comment 10 by bugdroid1@chromium.org, Dec 18 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/06309e15a0a6e5c84a7f50b6af0b5ee2f558677d

commit 06309e15a0a6e5c84a7f50b6af0b5ee2f558677d
Author: Leszek Swirski <leszeks@chromium.org>
Date: Mon Dec 18 16:30:32 2017

[parser] Move optimization disabling to parser

Move the one remaining optimization disabling in AST numbering (native
function literals) to be in the parser.

Bug:  v8:7178 
Change-Id: Icd96020622cbe64afa11b42c5831618247e3e021
Reviewed-on: https://chromium-review.googlesource.com/814399
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Reviewed-by: Marja Hölttä <marja@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50170}
[modify] https://crrev.com/06309e15a0a6e5c84a7f50b6af0b5ee2f558677d/src/ast/ast-numbering.cc
[modify] https://crrev.com/06309e15a0a6e5c84a7f50b6af0b5ee2f558677d/src/parsing/parser-base.h

Project Member

Comment 11 by bugdroid1@chromium.org, Dec 19 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/9128e8bf1b01000552499ab7b2e2da161761281b

commit 9128e8bf1b01000552499ab7b2e2da161761281b
Author: Leszek Swirski <leszeks@chromium.org>
Date: Tue Dec 19 14:50:19 2017

[ignition] Move object/array literal init to bytecode gen

Move the object and array literal flag and depth initialization to when
they are visited by the bytecode generator. This avoids issues with
doing this initialization before we know whether the (syntactic) literal
is actually a literal value or a destructuring assignment.

Bug:  chromium:795922 
Bug:  v8:7178 
Change-Id: I022178ab4bc9e71f80560f3b78a759d95d4d0584
Reviewed-on: https://chromium-review.googlesource.com/833882
Reviewed-by: Ross McIlroy <rmcilroy@chromium.org>
Reviewed-by: Toon Verwaest <verwaest@chromium.org>
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50204}
[modify] https://crrev.com/9128e8bf1b01000552499ab7b2e2da161761281b/src/ast/ast.h
[modify] https://crrev.com/9128e8bf1b01000552499ab7b2e2da161761281b/src/interpreter/bytecode-generator.cc
[add] https://crrev.com/9128e8bf1b01000552499ab7b2e2da161761281b/test/mjsunit/regress/regress-crbug-795922.js

Progress so far, input on the non-Done is welcome.

Done:
  * Object/Array literal initialization moved to be done just-in-time when visiting them during bytecode generation
  * Disabling optimization of native function literals is now part of the function state

Almost done:
  * Suspends are now counted during parsing, and suspend ids are assigned during bytecode generation
    - We still need to count suspend counts during parsing because we have to pre-allocate switch jump tables for the switch over generator state. We can't have a growing switch jump table because the size is a bytecode operand and we don't know its width (similar to issues with patching jumps). I guess we could have an unbounded Switch bytecode that we could grow, which seems fine because unbounded array access _never_ causes issues.
    - This slightly over-counts suspends in some cases, e.g. a for-in loops with a suspending initializer
    - The suspend counting for iterators is a little fragile and tough to follow, since we don't have a suspend "scope stack", so we have to "preserve" the suspend_count before the loop and diff it with the end suspend_count. 
    - Suspend point (and jump table) management in the bytecode generator is a little ugly for now, though not much more than before to be fair.

Nope nope nope:
  * Collecting eager compilation literals is a pain
    - Collecting any inner literals is already a bit of a pain.
      * I was trying to avoid a straight-up top-level parser list of all eager literals, because wiring it through was a bit of a pain already and it wasn't clear who should own it (the top level FunctionLiteral? The parser? The ParseInfo?).
      * I tried collecting a tree of direct eager children by pushing child FunctionLiterals into a list on the current function's state, but that was thwarted by some rewrites, e.g. rewriting class literal field initializers into an initializer function (where the initializers are expressions that could have inner function literals)
    - I considered recursively compiling bytecode (or queueing it for compilation) when we visit a FunctionLiteral in the bytecode generator (similar logically to the just-in-time Object/ArrayLiteral initialization), but I got tripped up by inner asm functions
    - Exposing eager inner literals via the CompilationJob (post-Execute) is possible but feels like a layer violation.
    - Not sure where to go from here, I could force any of these approaches to work with a bit of effort but none feel quite right.
Re: comment 12; conceptually, putting the eager literals into ParseInfo doesn't sound too bad... or maybe I'm overlooking something?

I'd like to keep FunctionState simple, putting the literals there doesn't sound as good as the other options. (And it will go out out scope and we anyway need to move the list out...)

I also wouldn't object exposing the inner literals via a CompilationJob.

But when thinking about all these options I'm probably overlooking a bunch of ugly implementation details.
Project Member

Comment 14 by bugdroid1@chromium.org, Jan 24 2018

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/d7fda25256fd3e1e37191eaf17080b447e708993

commit d7fda25256fd3e1e37191eaf17080b447e708993
Author: Leszek Swirski <leszeks@chromium.org>
Date: Wed Jan 24 12:02:09 2018

[ignition] Move suspend_id assignment to bytecode generation

Instead of building suspend_ids in the AST numbering, collect suspend
counts in the parser and assigning suspend ids during bytecode
generation.

Bug:  v8:7178 
Change-Id: I53421442afddc894db789fb9d0d3e3cc10e32ff0
Reviewed-on: https://chromium-review.googlesource.com/817598
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Reviewed-by: Ross McIlroy <rmcilroy@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50830}
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/ast/ast-numbering.cc
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/ast/ast.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/ast/prettyprinter.cc
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/interpreter/bytecode-generator.cc
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/interpreter/bytecode-generator.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/interpreter/control-flow-builders.cc
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/interpreter/control-flow-builders.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/parsing/parser-base.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/parsing/parser.cc
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/parsing/parser.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/src/parsing/preparser.h
[modify] https://crrev.com/d7fda25256fd3e1e37191eaf17080b447e708993/test/cctest/interpreter/bytecode_expectations/AsyncGenerators.golden

Project Member

Comment 15 by bugdroid1@chromium.org, Jan 24 2018

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/6342828391fcb2282010bc3d109e6a17c18c6645

commit 6342828391fcb2282010bc3d109e6a17c18c6645
Author: Leszek Swirski <leszeks@chromium.org>
Date: Wed Jan 24 16:26:15 2018

[compiler] Collect eager inner functions in bytecode generation

Instead of collecting eagerly compilable inner function literals (IIFEs
etc.) during AST numbering, collect them during bytecode generation,
exposing them on the CompilationJob.

Bug:  v8:7178 
Change-Id: I47451f412d2796e5857b4bc38c4f29c80cb0745d
Reviewed-on: https://chromium-review.googlesource.com/873872
Commit-Queue: Leszek Swirski <leszeks@chromium.org>
Reviewed-by: Michael Starzinger <mstarzinger@chromium.org>
Reviewed-by: Ross McIlroy <rmcilroy@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50842}
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/ast/ast-numbering.cc
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/ast/ast-numbering.h
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/compiler-dispatcher/unoptimized-compile-job.cc
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/compiler.cc
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/compiler.h
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/interpreter/bytecode-generator.cc
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/interpreter/bytecode-generator.h
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/interpreter/interpreter.cc
[modify] https://crrev.com/6342828391fcb2282010bc3d109e6a17c18c6645/src/interpreter/interpreter.h

So awesome, nice one Leszek!
Status: Fixed (was: Assigned)
Forgot to mark as fixed.

Sign in to add a comment