dart2js cps: Maintain parent pointers instead of recomputing them.

dart2js cps: Maintain parent pointers instead of recomputing them.

All passes must now preserve valid parent pointers. Several passes
already did this (or tried to do it).

The IR integrity checker can now check that parent pointers are valid.
This has caught a number of missing parent pointers assignments in
passes that otherwise tried to preserve them.

All node constructors now set parent pointers. This is very convenient
for simple transformations, but also a bit of a trap since updating a
field on an existing node does not update the parent pointer.

This is a pretty heavy-handed change. The main rationale for it are:

- The helpers methods require parent pointers, so they are more useful
  when parent pointers are always set.

- The integrity checker can catch bogus parent pointers after passes
  that have to maintain them anyway.

- The integrity checker is super slow, but this can finally be fixed
  if it can assume parent pointers are valid (not part of this CL).

The IR visitors have been changed a bit to support a generic parent
visitor that does not have to implement every visit method.

The 'parent index' fields have been removed.

BUG=
R=kmillikin@google.com

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

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

[asgerf, 2015-10-01 10:54:45]

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

[asgerf, 2015-10-01 10:54:46]

https://codereview.chromium.org/1375213003/diff/1/pkg/compiler/lib/src/cps_ir...
File pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart (left):

https://codereview.chromium.org/1375213003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:66:
continuations.removeLast();
The array shift kind of defeats the purpose of the parent index. Or at least,
the performance issue it tries to fix is still there.

This could also be fixed by moving the last continuation into the free slot,
assuming it's ok to change the order.

But performance-wise not much has changed anyway, so I'd rather just revisit
later if it becomes an issue.

https://codereview.chromium.org/1375213003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:239:
parameters.removeLast();
Same as above.

[Kevin Millikin (Google), 2015-10-05 12:04:37]

I'd go farther and make the parent points be set properly immediately after
construction, if possible.

But LGTM.

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/cps_fragment.dart (right):

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_fragment.dart:57: InteriorNode context;
It's probably not worth changing, but this name is a bit off.  'Context' is
usually just a term with a hole somewhere.  'Frame' is sometimes used for a term
which has a hole as an immediate subterm (so a context can be represented as a
stack of frames).  Of course, frame is overloaded but so is context.  I used
'current' in the IR builder.

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

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:324: Expression plug(Expression
expr) {
It seems better to also set the parent pointer here and in the other plug
functions:

Expression plug(Expression expr) {
  assert(body == null);
  expr.parent = this;
  return body = expr;
}

Unless I'm missing something, that should make the parent visitor unnecessary.

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/insert_refinements.dart (right):

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:81: refined.value.parent =
refined;
Is this necessary here?  It looks like the constructor for Refinement sets
value.parent appropriately and pushRefinement is always passed a newly
constructed Refinement.

[asgerf, 2015-10-12 13:18:32]

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/cps_fragment.dart (right):

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_fragment.dart:57: InteriorNode context;
On 2015/10/05 12:04:37, Kevin Millikin (Google) wrote:
> It's probably not worth changing, but this name is a bit off.  'Context' is
> usually just a term with a hole somewhere.  'Frame' is sometimes used for a
term
> which has a hole as an immediate subterm (so a context can be represented as a
> stack of frames).  Of course, frame is overloaded but so is context.  I used
> 'current' in the IR builder.

I can't find a name I really like. I also considered 'head' and 'tail'.

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

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:324: Expression plug(Expression
expr) {
On 2015/10/05 12:04:37, Kevin Millikin (Google) wrote:
> It seems better to also set the parent pointer here and in the other plug
> functions:
> 
> Expression plug(Expression expr) {
>   assert(body == null);
>   expr.parent = this;
>   return body = expr;
> }
> 
> Unless I'm missing something, that should make the parent visitor unnecessary.

There are too many explicit setter calls in the builders.

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
File pkg/compiler/lib/src/cps_ir/insert_refinements.dart (right):

https://codereview.chromium.org/1375213003/diff/20001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:81: refined.value.parent =
refined;
On 2015/10/05 12:04:37, Kevin Millikin (Google) wrote:
> Is this necessary here?  It looks like the constructor for Refinement sets
> value.parent appropriately and pushRefinement is always passed a newly
> constructed Refinement.

You're right, done.

[asgerf, 2015-10-12 14:26:37]

Committed patchset #5 (id:80001) manually as
6cc9b435354ea4fe3796437e3cc7091f6a11de19 (presubmit successful).

[asgerf, 2015-10-13 08:50:46]

Committed patchset #9 (id:160001) manually as
d43d95aaa3a347fe51c78130c72cbc8ce93238f8 (presubmit successful).