[kernel] [partial] Streaming of kernel binary without AST nodes

[kernel] [partial] Streaming of kernel binary without AST nodes

This CL allows for streaming big parts of the binary,
i.e. without using the AST nodes.
It is thus a stepping-stone in getting rid of the AST nodes in the VM.

Generally, all Expressions except "FunctionExpression",
and all Statements except "FunctionDeclaration" can be streamed.

There are currently not streamed because they create new functions,
which has a pointer to an AstNode (which we don't have when streaming).

Once we no longer need AstNodes at all these can be streamed as well.
This is, I think, mostly a matter of streaming the ScopeBuilder as well,
something that is not currently done.

The way the streaming is build, one has to stream an entire subtree.
That means, that if an expression (or statement), A, that is generally
streamable contains an expression or a statement, B, that is not streamable,
A cannot be streamed.
The way this is build is by marking AstNodes as streamable or not
("cannot_stream_" field). That way we know up front whether we can stream
a subtree or not.

The streaming is done via "kernel_binary_flowgraph".

In this file there are many obvious comments, e.g.
```
  TokenPosition position = ReadPosition();  // read position.
```
This has been done in an attempt to add a comment to everything that
reads from the binary to make it stand out more.

All changes from kernel_to_il up to and including May 2nd 2017
should be included.

R=kmillikin@google.com

Committed: https://github.com/dart-lang/sdk/commit/d26558b7be153f7544eb406b5d1e5cd01fac11bb

[jensj, 2017-05-03 13:04:26]

jensj@google.com changed reviewers:
+ kmillikin@google.com

[jensj, 2017-05-03 13:04:26]

Note that this includes the CL https://codereview.chromium.org/2790093002/ (with
comments addressed).

I have made small changes to the binary format, most noticeable:
- binary offset for variable declaration in VariableGet and VariableSet
- a few extra bytes here and there to make streaming easier (e.g. to avoid
reading many bytes twice - e.g. for TryCatch the kernel_to_il looks at whether
any catch wants a stacktrace. We can do that with streaming too, by looking
ahead, but instead I added a byte in the binary).

I've changed how the AstNodes handle switch slightly to be able to do the same
when streaming. The binary format doesn't change through. AstNodes no longer
reference SwitchCases, but just the absolute target-index as serialized in the
binary.

As written in the CL description, there are many obvious comments, e.g.
```
  TokenPosition position = ReadPosition();  // read position.
```

This has been done in an attempt to add a comment to everything that
reads from the binary to make it stand out more.
Everything should start with a "// read ", though I might have overlooked some.
Please point it out if you spot any.

Some things naturally needs to be read several places (e.g. we have  both the
flowgraph builder and the constant evaluator).
Some things are read quite a number of places through - e.g. Arguments. Any
ideas towards making that number smaller or moving methods around to make it
clear where to edit in the event of a binary change will be much appreciated.

I do realize that this is a big CL, and I apologize. I hope it is still
manageable. Most is just copy-paste from kernel_to_il.

[jensj, 2017-05-04 10:13:05]

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
File runtime/vm/kernel_binary_flowgraph.cc (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.cc:89: void
StreamingDartTypeTranslator::BuildFunctionType() {
BuildFunctionType and BuildSimpleFunctionType are basically the same. I have
locally rewritten to only have one (taking a "bool simple" argument).

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.cc:1675: ReadUInt();  // read string index
(name).
I've added the missing "SkipDartType();" locally...

[Kevin Millikin (Google), 2017-05-11 10:38:36]

LGTM when the comments below are addressed.

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/binary.md
File pkg/kernel/binary.md (right):

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/binary.md#newcod...
pkg/kernel/binary.md:788: type FileOffsetAndExpressionPair {
I'd just add at the top of the spec (maybe just before or after List):

// Untagged pairs.
type Pair<T0, T1> {
  T0 first;
  T1 second;
}

And below:

List<Pair<FileOffset, Expression>> expressions;

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/lib/binary/ast_t...
File pkg/kernel/lib/binary/ast_to_binary.dart (right):

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/lib/binary/ast_t...
pkg/kernel/lib/binary/ast_to_binary.dart:897: if (node.catches.map((c) =>
c.stackTrace != null).contains(true)) {
node.catches.any((Catch c) => c.stacktrace != null)

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h
File runtime/vm/kernel.h (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h#newcode232
runtime/vm/kernel.h:232: bool cannot_stream() {
This should be CanStream.  Capitalized because of the loop, and positive because
predicates should always be positive (`!CannotStream` is hard to think about).

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h#newcode...
runtime/vm/kernel.h:2421: explicit ReturnStatement(Expression* expression, bool
cannot_stream)
No need for explicit unless it takes only one argument.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary.cc
File runtime/vm/kernel_binary.cc (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary.cc...
runtime/vm/kernel_binary.cc:253: cannot_stream_ = fields_.cannot_stream() ||
constructors_.cannot_stream() ||
This is overwriting cannot_stream_ which might have been set in Class::ReadFrom.
 Don't we want

cannot_stream_ = cannot_stream_ || ...

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
File runtime/vm/kernel_binary_flowgraph.cc (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.cc:2448:
UpdateDirectDescendantPosition(TokenPosition::kNoSource);
How about an optional output parameter defaulting to NULL that you set if it's
non-NULL:

Fragment StreamingFlowGraphBuilder::BuildInvalidExpression(TokenPosition*
position) {
  (position != NULL) ? *position = TokenPosition::kNoSource;
  ...
}

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
File runtime/vm/kernel_binary_flowgraph.h (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:20: enum LogicalOperator { kAnd, kOr };
You should be able to use LogicalExpression::Operator instead of declaring a
copy.

This is a hazard if someone changes LogicalExpression::Operator and doesn't
realize that there is a corresponding change required here.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:21: enum VariableDeclarationFlags {
Similarly use VariableDeclaration::Flags instead.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:25: enum YieldFlags {
Similarly use YieldStatement::Flags instead.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:32:
StreamingDartTypeTranslator(StreamingFlowGraphBuilder* builder,
Unless we actually want to support the behavior of a type translator that uses a
different translation helper and active class than the builder that owns it,
don't make it possible.

It makes it hard to reason about invariants, and it makes it hard to put shared
state in the type translator (like the link table or string table) without
adding extra plumbing.

Instead:

StreamingDartTypeTranslator(StreamingFlowGraphBuilder* builder,
                            bool finalize = false)
    : builder_(builder),
      translation_helper_(builder->translation_helper()),
      active_class_(builder->active_class()),
      ...

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:59: // Can return a malformed type.
Technically, it can't return anything.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:105:
StreamingConstantEvaluator(StreamingFlowGraphBuilder* builder,
Same here, don't pass the zone, TranslationHelper, and
StreamingDartTypeTranslator separately, just get them from the builder.

[jensj, 2017-05-11 12:53:11]

Patchset #2 (id:20001) has been deleted

[jensj, 2017-05-11 12:59:25]

Comments addressed.

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/binary.md
File pkg/kernel/binary.md (right):

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/binary.md#newcod...
pkg/kernel/binary.md:788: type FileOffsetAndExpressionPair {
On 2017/05/11 10:38:35, Kevin Millikin (Google) wrote:
> I'd just add at the top of the spec (maybe just before or after List):
> 
> // Untagged pairs.
> type Pair<T0, T1> {
>   T0 first;
>   T1 second;
> }
> 
> And below:
> 
> List<Pair<FileOffset, Expression>> expressions;

Done.

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/lib/binary/ast_t...
File pkg/kernel/lib/binary/ast_to_binary.dart (right):

https://codereview.chromium.org/2854393002/diff/1/pkg/kernel/lib/binary/ast_t...
pkg/kernel/lib/binary/ast_to_binary.dart:897: if (node.catches.map((c) =>
c.stackTrace != null).contains(true)) {
On 2017/05/11 10:38:35, Kevin Millikin (Google) wrote:
> node.catches.any((Catch c) => c.stacktrace != null)

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h
File runtime/vm/kernel.h (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h#newcode232
runtime/vm/kernel.h:232: bool cannot_stream() {
On 2017/05/11 10:38:35, Kevin Millikin (Google) wrote:
> This should be CanStream.  Capitalized because of the loop, and positive
because
> predicates should always be positive (`!CannotStream` is hard to think about).

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel.h#newcode...
runtime/vm/kernel.h:2421: explicit ReturnStatement(Expression* expression, bool
cannot_stream)
On 2017/05/11 10:38:35, Kevin Millikin (Google) wrote:
> No need for explicit unless it takes only one argument.

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary.cc
File runtime/vm/kernel_binary.cc (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary.cc...
runtime/vm/kernel_binary.cc:253: cannot_stream_ = fields_.cannot_stream() ||
constructors_.cannot_stream() ||
On 2017/05/11 10:38:35, Kevin Millikin (Google) wrote:
> This is overwriting cannot_stream_ which might have been set in
Class::ReadFrom.
>  Don't we want
> 
> cannot_stream_ = cannot_stream_ || ...

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
File runtime/vm/kernel_binary_flowgraph.cc (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.cc:2448:
UpdateDirectDescendantPosition(TokenPosition::kNoSource);
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> How about an optional output parameter defaulting to NULL that you set if it's
> non-NULL:
> 
> Fragment StreamingFlowGraphBuilder::BuildInvalidExpression(TokenPosition*
> position) {
>   (position != NULL) ? *position = TokenPosition::kNoSource;
>   ...
> }

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
File runtime/vm/kernel_binary_flowgraph.h (right):

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:20: enum LogicalOperator { kAnd, kOr };
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> You should be able to use LogicalExpression::Operator instead of declaring a
> copy.
> 
> This is a hazard if someone changes LogicalExpression::Operator and doesn't
> realize that there is a corresponding change required here.

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:21: enum VariableDeclarationFlags {
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> Similarly use VariableDeclaration::Flags instead.

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:25: enum YieldFlags {
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> Similarly use YieldStatement::Flags instead.

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:32:
StreamingDartTypeTranslator(StreamingFlowGraphBuilder* builder,
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> Unless we actually want to support the behavior of a type translator that uses
a
> different translation helper and active class than the builder that owns it,
> don't make it possible.
> 
> It makes it hard to reason about invariants, and it makes it hard to put
shared
> state in the type translator (like the link table or string table) without
> adding extra plumbing.
> 
> Instead:
> 
> StreamingDartTypeTranslator(StreamingFlowGraphBuilder* builder,
>                             bool finalize = false)
>     : builder_(builder),
>       translation_helper_(builder->translation_helper()),
>       active_class_(builder->active_class()),
>       ...

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:59: // Can return a malformed type.
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> Technically, it can't return anything.

Done.

https://codereview.chromium.org/2854393002/diff/1/runtime/vm/kernel_binary_fl...
runtime/vm/kernel_binary_flowgraph.h:105:
StreamingConstantEvaluator(StreamingFlowGraphBuilder* builder,
On 2017/05/11 10:38:36, Kevin Millikin (Google) wrote:
> Same here, don't pass the zone, TranslationHelper, and
> StreamingDartTypeTranslator separately, just get them from the builder.

Done.

[jensj, 2017-05-15 07:01:28]

Description was changed from

==========
[kernel] [partial] Streaming of kernel binary without AST nodes

This CL allows for streaming big parts of the binary,
i.e. without using the AST nodes.
It is thus a stepping-stone in getting rid of the AST nodes in the VM.

Generally, all Expressions except "FunctionExpression",
and all Statements except "FunctionDeclaration" can be streamed.

There are currently not streamed because they create new functions,
which has a pointer to an AstNode (which we don't have when streaming).

Once we no longer need AstNodes at all these can be streamed as well.
This is, I think, mostly a matter of streaming the ScopeBuilder as well,
something that is not currently done.

The way the streaming is build, one has to stream an entire subtree.
That means, that if an expression (or statement), A, that is generally
streamable contains an expression or a statement, B, that is not streamable,
A cannot be streamed.
The way this is build is by marking AstNodes as streamable or not
("cannot_stream_" field). That way we know up front whether we can stream
a subtree or not.

The streaming is done via "kernel_binary_flowgraph".

In this file there are many obvious comments, e.g.
```
  TokenPosition position = ReadPosition();  // read position.
```
This has been done in an attempt to add a comment to everything that
reads from the binary to make it stand out more.

All changes from kernel_to_il up to and including May 2nd 2017
should be included.
==========

to

==========
[kernel] [partial] Streaming of kernel binary without AST nodes

This CL allows for streaming big parts of the binary,
i.e. without using the AST nodes.
It is thus a stepping-stone in getting rid of the AST nodes in the VM.

Generally, all Expressions except "FunctionExpression",
and all Statements except "FunctionDeclaration" can be streamed.

There are currently not streamed because they create new functions,
which has a pointer to an AstNode (which we don't have when streaming).

Once we no longer need AstNodes at all these can be streamed as well.
This is, I think, mostly a matter of streaming the ScopeBuilder as well,
something that is not currently done.

The way the streaming is build, one has to stream an entire subtree.
That means, that if an expression (or statement), A, that is generally
streamable contains an expression or a statement, B, that is not streamable,
A cannot be streamed.
The way this is build is by marking AstNodes as streamable or not
("cannot_stream_" field). That way we know up front whether we can stream
a subtree or not.

The streaming is done via "kernel_binary_flowgraph".

In this file there are many obvious comments, e.g.
```
  TokenPosition position = ReadPosition();  // read position.
```
This has been done in an attempt to add a comment to everything that
reads from the binary to make it stand out more.

All changes from kernel_to_il up to and including May 2nd 2017
should be included.

R=kmillikin@google.com

Committed:
https://github.com/dart-lang/sdk/commit/d26558b7be153f7544eb406b5d1e5cd01fac11bb
==========

[jensj, 2017-05-15 07:01:29]

Committed patchset #2 (id:40001) manually as
d26558b7be153f7544eb406b5d1e5cd01fac11bb (presubmit successful).