dart2js cps: Avoid deep recursion using trampolines and basic blocks.

dart2js cps: Avoid deep recursion using trampolines and basic blocks.

The CPS RecursiveVisitor now uses an explicit stack of things to do
on the way out of a term. Every CPS pass has been hacked to fit the
new visitor paradigm.

The tree visitors now iterate over chains of ExpressionStatements.
This seems to do the trick, mostly because direct-style rewriting
significantly reduces the height of the tree.

The IR tracers still use deep recursion, but they are disabled by
default anyway so they are not critical.

BUG=
R=floitsch@google.com, karlklose@google.com

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

[asgerf, 2015-07-22 12:43:33]

asgerf@google.com changed reviewers:
+ floitsch@google.com, karlklose@google.com

[asgerf, 2015-07-22 12:43:39]

asgerf@google.com changed reviewers:
- floitsch@google.com, karlklose@google.com

[asgerf, 2015-07-22 12:46:44]

asgerf@google.com changed reviewers:
+ floitsch@google.com, karlklose@google.com

[asgerf, 2015-07-22 12:46:45]

Please start by reading the documentation for RecursiveVisitor in
cps_ir_nodes.dart. Some of the code won't make sense before reading that.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/type_propagation.dart (left):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/type_propagation.dart:1525:
node.continuations.forEach(visit);
The traversal order changed so this is how it works by default now.

[karlklose, 2015-07-22 14:08:06]

LGTM.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:1440: typedef dynamic
StackAction();
The return type should be void, the result seems not to be used (and it is
called an action).

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:47: class Builder implements
cps_ir.Visitor {
Maybe you add a comment of the form
  class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ { ...

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:272: // TODO(asgerf): Use a
function typedef.
A typedef different from NodeCallback?

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:279: for (NodeCallback fun in
stack.reversed) {
Maybe a Link<NodeCallback> would work better for the stack, because you do not
need to get a reversed view on it.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
File tests/language/larger_implicit_getter_test.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:1: // Copyright (c) 2013, the
Dart project authors.  Please see the AUTHORS file
2013 -> 2015.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:5: //
VMOptions=--optimization-counter-threshold=10
Remove VMOptions (or are they needed for the VM to pass the test?)

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:8:
[6853.940039224797,6050.837897021371]
Missing indentation.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:9:
,[6953.240039224797,6050.837897021371]
Place ',' after the entry (it is also allowed after the last entry of a list
literal).

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:4096: var y = panels.length;
This is fragile, because the compiler can realize that the length is a constant
and not even compile the list.

Use a function like this:
  @AssumeDynamic @NoInline
  confuse(x) => x;

  var l = confuse(panels);

to avoid this.

[floitsch, 2015-07-22 14:21:43]

LGTM.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:371: Statement
visitExpressionStatement(ExpressionStatement inputNode) {
Add comment, what this function does (and/or on analyzeExpressionStatement).

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:401: //
because it has an unsafe variable use (see [hasUnsafeVariableUse])
long line.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:326: // See
visitInvokeContinuation for the implementation.
make this a link.

[asgerf, 2015-07-22 14:32:25]

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:1440: typedef dynamic
StackAction();
On 2015/07/22 14:08:06, karlklose wrote:
> The return type should be void, the result seems not to be used (and it is
> called an action).

Done.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:371: Statement
visitExpressionStatement(ExpressionStatement inputNode) {
On 2015/07/22 14:21:42, floitsch wrote:
> Add comment, what this function does (and/or on analyzeExpressionStatement).

Done. Also renamed analyze->process since it has side effects.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart:401: //
because it has an unsafe variable use (see [hasUnsafeVariableUse])
On 2015/07/22 14:21:42, floitsch wrote:
> long line.

Done.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:47: class Builder implements
cps_ir.Visitor {
On 2015/07/22 14:08:06, karlklose wrote:
> Maybe you add a comment of the form
>   class Builder implements cps_ir.Visitor/*<NodeCallback|Node>*/ { ...

Done.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:272: // TODO(asgerf): Use a
function typedef.
On 2015/07/22 14:08:06, karlklose wrote:
> A typedef different from NodeCallback?

Oops, I forgot to remove this after resolving it.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:279: for (NodeCallback fun in
stack.reversed) {
On 2015/07/22 14:08:06, karlklose wrote:
> Maybe a Link<NodeCallback> would work better for the stack, because you do not
> need to get a reversed view on it.

I don't think linked lists are faster.

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:326: // See
visitInvokeContinuation for the implementation.
On 2015/07/22 14:21:42, floitsch wrote:
> make this a link.

Done.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
File tests/language/larger_implicit_getter_test.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:1: // Copyright (c) 2013, the
Dart project authors.  Please see the AUTHORS file
On 2015/07/22 14:08:06, karlklose wrote:
> 2013 -> 2015.

Done.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:5: //
VMOptions=--optimization-counter-threshold=10
On 2015/07/22 14:08:06, karlklose wrote:
> Remove VMOptions (or are they needed for the VM to pass the test?)

Done.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:8:
[6853.940039224797,6050.837897021371]
On 2015/07/22 14:08:06, karlklose wrote:
> Missing indentation.

Done.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:9:
,[6953.240039224797,6050.837897021371]
On 2015/07/22 14:08:06, karlklose wrote:
> Place ',' after the entry (it is also allowed after the last entry of a list
> literal).

Done.

https://codereview.chromium.org/1251083002/diff/40001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:4096: var y = panels.length;
On 2015/07/22 14:08:06, karlklose wrote:
> This is fragile, because the compiler can realize that the length is a
constant
> and not even compile the list.
> 
> Use a function like this:
>   @AssumeDynamic @NoInline
>   confuse(x) => x;
> 
>   var l = confuse(panels);
> 
> to avoid this.

Done. 

BTW this file is an existing test I copied and just made the list of panels
longer to stress the stack more.

[karlklose, 2015-07-23 06:44:45]

> BTW this file is an existing test I copied and just made the list of panels
> longer to stress the stack more.

Strange that the git copy detection did not pick this up as a modification then.

[karlklose, 2015-07-23 06:55:54]

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
File pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart (right):

https://codereview.chromium.org/1251083002/diff/40001/pkg/compiler/lib/src/tr...
pkg/compiler/lib/src/tree_ir/tree_ir_builder.dart:279: for (NodeCallback fun in
stack.reversed) {
On 2015/07/22 14:32:25, asgerf wrote:
> On 2015/07/22 14:08:06, karlklose wrote:
> > Maybe a Link<NodeCallback> would work better for the stack, because you do
not
> > need to get a reversed view on it.
> 
> I don't think linked lists are faster.

Not necessarily faster, but you can build the stack by prepending and then have
  for (NodeCallback fun in stack) {
    result = fun(result);
  }
here, which is a tiny bit easier to read.

But it is not that important.

[asgerf, 2015-07-23 09:32:47]

PTAL at type propagation in delta 5->4.

There was a problem with how new expressions were reprocessed after being
created. It now uses its own trampoline.

Also, the worklist in the type propagation analysis is incredibly slow which is
causing timeouts in some large co19 tests. I am working on fixing it.

https://codereview.chromium.org/1251083002/diff/80001/tests/co19/co19-dart2js...
File tests/co19/co19-dart2js.status (right):

https://codereview.chromium.org/1251083002/diff/80001/tests/co19/co19-dart2js...
tests/co19/co19-dart2js.status:9605:
+LibTest/collection/ListMixin/ListMixin_class_A01_t02: Timeout
This is a performance issue in type propagation. It's an existing problem that
was hidden by the stack overflow. I'm working on a fix.

[karlklose, 2015-07-23 10:55:07]

Still LGTM.

https://codereview.chromium.org/1251083002/diff/80001/tests/language/larger_i...
File tests/language/larger_implicit_getter_test.dart (right):

https://codereview.chromium.org/1251083002/diff/80001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:4099: confuse(panels);
Maybe print the length of confuse(panels) to ensure that it is used.

[asgerf, 2015-07-23 11:03:36]

https://codereview.chromium.org/1251083002/diff/80001/tests/language/larger_i...
File tests/language/larger_implicit_getter_test.dart (right):

https://codereview.chromium.org/1251083002/diff/80001/tests/language/larger_i...
tests/language/larger_implicit_getter_test.dart:4099: confuse(panels);
On 2015/07/23 10:55:07, karlklose wrote:
> Maybe print the length of confuse(panels) to ensure that it is used.

Done.

[asgerf, 2015-07-23 11:52:10]

Committed patchset #8 (id:130001) manually as
7d038fbc679fcbf17bccfc27562584d323c75de5 (presubmit successful).