Overhaul tree IR visitor and rename IR classes.

Overhaul tree IR visitor and rename IR classes.

Changes in both IRs:
- ExecutableDefinition -> RootNode

- PassMixin has been removed and the Pass interface has been
  reduced to a single rewrite(RootNode) method.

- ConstructorDefinition no longer subclasses FunctionDefinition.

Changes in the cps IR:
- RunnableBody -> Body


Changes in tree IR:
- RootNodes have "forEachBody" and "replaceEachBody" helper methods that
  take care of the boilerplate for traversing roots and initializers.

- We now have visitors for initializers and root nodes. The RecursiveVisitor still
  just visits statements and expressions since forEachBody takes care of the root
  nodes and initializers.

- Initializers are no longer expressions. Why were they expressions?

- We now have a RecursiveTransformer class which behaves like RecursiveVisitor,
  except visitors are expected to return a transformed node.
  This removes a lot of boilerplate traversal from transformations.

R=kmillikin@google.com

Committed: https://code.google.com/p/dart/source/detail?r=45000

Reverted: https://code.google.com/p/dart/source/detail?r=45004

Committed: https://code.google.com/p/dart/source/detail?r=45006

[asgerf, 2015-04-08 13:47:02]

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

[Kevin Millikin (Google), 2015-04-08 15:10:16]

Nice.  LGTM with suggestions for further improvements (?).

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:734: bool get isEmpty;
This makes me wonder what it means to be an empty root node.  When I look at the
implementations and see that it exactly means that it doesn't have a body.  That
makes me wonder if it wouldn't be better to just go ahead and expose the field
body here in this class, and even to use x.body == null instead of x.isEmpty?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:735: List<Definition> get
parameters;
It looks like at the cost of a field per FieldDefinition this could just be a
field in this class.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:744: Body body;
Can this be final?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:768: Expression body;
This is still weird: Body has a field body which is not a Body.  I *would*
suggest that we call this the root, but that's taken.  How about expression?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:1016:
node.initializers.forEach(visit);
It might be better not to assume that (node.body == null) == (node.initializers
== null) here and write:

if (node.initializers != null) {
  node.initializers.forEach(visit);
}
if (node.body != null) {
  visit(node.body);
}

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/cps_ir_tracer.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_tracer.dart:28: visit(graph);
Maybe this can be disentangled a bit after this change.  Right now:

IRTracer.traceGraph(name, graph) calls
IRTracer.visit(graph) when graph.body is non-null, which just calls
IRTracer.printDefinition(graph), which calls
BlockCollector.visit(graph), which just calls
BlockCollector.visit(graph.body)

meanwhile IRTracer.visitBody is unexpected.

It seems simpler to switch so:

IRTracer.traceGraph(name, graph) calls IRTracer.visit(graph.body) when
graph.body is non-null and just move the definition of printDefinition into
IRTracer.visitBody.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/redundant_phi.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/redundant_phi.dart:21: void rewrite(final RootNode
root) {
final?  Really?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
File pkg/compiler/lib/src/dart_backend/backend.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:148: cps_ir.RootNode
cpsDefinition) {
cpsDefinition ==> cpsRoot?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:173: tree_ir.RootNode
treeDefinition = builder.build(cpsDefinition);
treeDefinition ==> treeRoot?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:223: cps_ir.RootNode definition =
definition ==> root or node.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
File pkg/compiler/lib/src/dart_backend/backend_ast_emitter.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend_ast_emitter.dart:18: RootNode
emit(tree.RootNode definition) {
definition ==> root

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:480: for (int
i=0; i < node.parameters.length; i++) {
Hmmm.  It was better before.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:631: bool get isEmpty;
If this really means it is missing the optional body, I'd rather just put the
body as a field in this class and expose it.  It seems like then we wouldn't
really need forEachBody because it's just an optional statement.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:699: void forEachBody(void
action(Statement node));
The body of an initializer is a little weird, it doesn't seem to be exactly a
body (it can be arguments, or constructor initializers)  I can't think of a
better word to mean top-level statement though.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:741: for (int i=0; i <
arguments.length; i++) {
There should be spaces around the assignment operator '='.  i++ is OK, I guess.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:1157: for (int i=0;
i<list.length; i++) {
int i = 0; i < list.length

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart:178: // TODO(asgerf): Fix
visitors so we don't have to use PassMixin here.
I think you can remove this TODO.

[asgerf, 2015-04-09 09:58:24]

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:734: bool get isEmpty;
On 2015/04/08 15:10:15, kmillikin wrote:
> This makes me wonder what it means to be an empty root node.  When I look at
the
> implementations and see that it exactly means that it doesn't have a body. 
That
> makes me wonder if it wouldn't be better to just go ahead and expose the field
> body here in this class, and even to use x.body == null instead of x.isEmpty?

I removed the body getter because constructors have more than one body, and
there is almost no legitimate use of the 'body' that does not look at the
initializer bodies (except emptiness-checking).

I copied the comment from the tree.RootNode in here.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:735: List<Definition> get
parameters;
On 2015/04/08 15:10:15, kmillikin wrote:
> It looks like at the cost of a field per FieldDefinition this could just be a
> field in this class.

But then we don't get to use an initializing formal `this.parameters` in the
subclasses, and the field can't be final unless we use a superconstructor call
to initialize it.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:744: Body body;
On 2015/04/08 15:10:15, kmillikin wrote:
> Can this be final?

Yes.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:768: Expression body;
On 2015/04/08 15:10:15, kmillikin wrote:
> This is still weird: Body has a field body which is not a Body.  I *would*
> suggest that we call this the root, but that's taken.  How about expression?

The field overrides InteriorNode.body so this would force us to also rename
LetCont.body, LetPrim.body, etc. It think we should hold on the 'body' field
name.

As for the class name, I wish something I could think of something better, but
nothing in my vocabulary describes something that has its own return
continuation but doesn't have its own parameter list. It's not even a
ClosedExpression because the parameters are free.

So I just defaulted to Body. I took out the Runnable prefix because it was just
noise. Plenty of others things are "bodies" and they are also runnable.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:1016:
node.initializers.forEach(visit);
On 2015/04/08 15:10:15, kmillikin wrote:
> It might be better not to assume that (node.body == null) ==
(node.initializers
> == null) here and write:
> 
> if (node.initializers != null) {
>   node.initializers.forEach(visit);
> }
> if (node.body != null) {
>   visit(node.body);
> }

Done.

There are other places where we depend on a constructor being either empty or
non-empty and nothing in-between.

But I guess the visitor should be a bit more conservative so it can be used for
tracing/sexpressions/integrity/etc.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/cps_ir_tracer.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_tracer.dart:28: visit(graph);
On 2015/04/08 15:10:15, kmillikin wrote:
> Maybe this can be disentangled a bit after this change.  Right now:
> 
> IRTracer.traceGraph(name, graph) calls
> IRTracer.visit(graph) when graph.body is non-null, which just calls
> IRTracer.printDefinition(graph), which calls
> BlockCollector.visit(graph), which just calls
> BlockCollector.visit(graph.body)
> 
> meanwhile IRTracer.visitBody is unexpected.
> 
> It seems simpler to switch so:
> 
> IRTracer.traceGraph(name, graph) calls IRTracer.visit(graph.body) when
> graph.body is non-null and just move the definition of printDefinition into
> IRTracer.visitBody.

I agree, this code has stagnated quite a bit.

I updated both IR tracers to properly handle the multiple bodies of constructors
and print an explicit 'Entry' statement in front of blocks that are entry
points. They also print the parameter list now, which is nice.

The many bodies of a constructor should be passed to the same block collector so
traversing the top-level nodes in the IRTracer did not work. So they are just
unexpected nodes.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/redundant_phi.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/redundant_phi.dart:21: void rewrite(final RootNode
root) {
On 2015/04/08 15:10:15, kmillikin wrote:
> final?  Really?

I guess someone wanted to be extra safe.

Removed it.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
File pkg/compiler/lib/src/dart_backend/backend.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:148: cps_ir.RootNode
cpsDefinition) {
On 2015/04/08 15:10:15, kmillikin wrote:
> cpsDefinition ==> cpsRoot?

Absolutely.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:173: tree_ir.RootNode
treeDefinition = builder.build(cpsDefinition);
On 2015/04/08 15:10:15, kmillikin wrote:
> treeDefinition ==> treeRoot?

Done.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend.dart:223: cps_ir.RootNode definition =
On 2015/04/08 15:10:15, kmillikin wrote:
> definition ==> root or node.

Went with irNode since there's also AST nodes flying around here.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
File pkg/compiler/lib/src/dart_backend/backend_ast_emitter.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/dart_b...
pkg/compiler/lib/src/dart_backend/backend_ast_emitter.dart:18: RootNode
emit(tree.RootNode definition) {
On 2015/04/08 15:10:15, kmillikin wrote:
> definition ==> root

Done.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:480: for (int
i=0; i < node.parameters.length; i++) {
On 2015/04/08 15:10:15, kmillikin wrote:
> Hmmm.  It was better before.

Well the diff is a bit misleading here.

I'm not sure what you're asking for. You want the for-loop in a method that
we're only calling once?

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:631: bool get isEmpty;
On 2015/04/08 15:10:15, kmillikin wrote:
> If this really means it is missing the optional body, I'd rather just put the
> body as a field in this class and expose it.  It seems like then we wouldn't
> really need forEachBody because it's just an optional statement.

Constructors have multiple bodies (because of initializers). That's why I
removed the 'body' field because there is no legitimate way to use it.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:699: void forEachBody(void
action(Statement node));
On 2015/04/08 15:10:15, kmillikin wrote:
> The body of an initializer is a little weird, it doesn't seem to be exactly a
> body (it can be arguments, or constructor initializers)  I can't think of a
> better word to mean top-level statement though.

Initializers are super awkward.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:741: for (int i=0; i <
arguments.length; i++) {
On 2015/04/08 15:10:15, kmillikin wrote:
> There should be spaces around the assignment operator '='.  i++ is OK, I
guess.

Done.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_nodes.dart:1157: for (int i=0;
i<list.length; i++) {
On 2015/04/08 15:10:16, kmillikin wrote:
> int i = 0; i < list.length

Done.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/tree_ir_tracer.dart:178: // TODO(asgerf): Fix
visitors so we don't have to use PassMixin here.
On 2015/04/08 15:10:16, kmillikin wrote:
> I think you can remove this TODO.

Done.

[Kevin Millikin (Google), 2015-04-09 10:56:32]

Changes LGTM.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:480: for (int
i=0; i < node.parameters.length; i++) {
On 2015/04/09 09:58:23, asgerf wrote:
> On 2015/04/08 15:10:15, kmillikin wrote:
> > Hmmm.  It was better before.
> 
> Well the diff is a bit misleading here.
> 
> I'm not sure what you're asking for. You want the for-loop in a method that
> we're only calling once?

No, there should be a space around the binary assignment operator.  And I much
prefer to read ++i instead of i++: it matches English word order ('increment
i'), it matches all the other unary operators (!,-,~), and I find it easier to
recognize extra characters at the start of an identifier than at the end of one.

[Kevin Millikin (Google), 2015-04-09 10:58:52]

Also in Dart, ++i is equivalent to

i += 1

and i++ is equivalent to

() { var r = v; v = r + 1; return r; }()

where r and v are distinct.  That suggests that the first one is somehow simpler
:)

[asgerf, 2015-04-09 11:01:18]

Old habits die hard I guess.

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
File pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart (right):

https://codereview.chromium.org/1068243002/diff/1/pkg/compiler/lib/src/tree_i...
pkg/compiler/lib/src/tree_ir/optimization/variable_merger.dart:480: for (int
i=0; i < node.parameters.length; i++) {
On 2015/04/09 10:56:32, kmillikin wrote:
> On 2015/04/09 09:58:23, asgerf wrote:
> > On 2015/04/08 15:10:15, kmillikin wrote:
> > > Hmmm.  It was better before.
> > 
> > Well the diff is a bit misleading here.
> > 
> > I'm not sure what you're asking for. You want the for-loop in a method that
> > we're only calling once?
> 
> No, there should be a space around the binary assignment operator.  And I much
> prefer to read ++i instead of i++: it matches English word order ('increment
> i'), it matches all the other unary operators (!,-,~), and I find it easier to
> recognize extra characters at the start of an identifier than at the end of
one.

Ah. Done.

[asgerf, 2015-04-09 12:05:21]

Committed patchset #3 (id:40001) manually as 45000 (presubmit successful).

[asgerf, 2015-04-09 13:01:34]

Committed patchset #4 (id:60001) manually as 45004 (presubmit successful).

[asgerf, 2015-04-09 13:04:38]

Patchset #4 (id:60001) has been deleted

[asgerf, 2015-04-09 13:19:30]

Committed patchset #5 (id:100001) manually as 45006 (presubmit successful).