dart2js cps: Add path-sensitive types by inserting refinement IR nodes.

dart2js cps: Add path-sensitive types by inserting refinement IR nodes.

Refinement nodes are inserted after an InvokeMethod, refining the type
of the receiver to those that can respond to the selector.

Refinements are also inserted in the arms of a branch with a condition
of form 'x is T' or 'x == null'.

R=kmillikin@google.com

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

[asgerf, 2015-09-02 17:08:40]

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

[asgerf, 2015-09-02 17:08:40]

There were so many fixes and rebasings of the original incarnation that I
started a fresh CL for this.

[sra1, 2015-09-02 18:24:52]

sra@google.com changed reviewers:
+ sra@google.com

[sra1, 2015-09-02 18:24:52]

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

https://codereview.chromium.org/1330503003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:216: return
!effectiveUses.iterator.moveNext();
effectiveUses.isEmpty does the same.

https://codereview.chromium.org/1330503003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:519: bool get isSafeForReordering
=> false;
Is this adequate to keep it in order with respect to the 'witness' operation?

[asgerf, 2015-09-02 18:41:17]

Patchset #2 (id:20001) has been deleted

[asgerf, 2015-09-02 18:46:58]

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

https://codereview.chromium.org/1330503003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:216: return
!effectiveUses.iterator.moveNext();
On 2015/09/02 18:24:52, sra1 wrote:
> effectiveUses.isEmpty does the same.

I originally couldn't bother to import dart:collection to make the iterable an
actual Iterable, but I guess there's no harm in doing that. It's now an
IterableBase and using .isEmpty.

https://codereview.chromium.org/1330503003/diff/1/pkg/compiler/lib/src/cps_ir...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:519: bool get isSafeForReordering
=> false;
On 2015/09/02 18:24:52, sra1 wrote:
> Is this adequate to keep it in order with respect to the 'witness' operation?

Yes, but we might need the witness reference when we add more detailed side
effect information.

If the witness is an InvokeMethod that later gets rewritten to a pure expression
(e.g. constant-folded), then they might change places, but if that's the case,
then the original InvokeMethod could not throw, and therefore the refinement is
a no-op and is still safe.

[Kevin Millikin (Google), 2015-09-03 10:21:06]

Refinements are more generally just copies or renamings, and refinement
elimination is copy propagation.  Even if we keep the name Refinement, I think
that the refinement elimination belongs in the same pass as shrinking
reductions.

Otherwise LGTM.

A broader comment is that I think we're far past the point where things would
all just work if call or branch continuations had more than one use.  Early on,
we wrote code that assumed that might happen --- we should probably remove that
code when we see it.

We should also consider how we could change branches to have a pair of
expressions as subterms, rather than continuations.

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:126: final List<Primitive> stack =
<Primitive>[];
Probably clearer to make this List<Refinement>.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:137: return false;
current should be null when the iterator has finished
(https://api.dartlang.org/1.12.0/dart-core/Iterator/current.html).

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:147: }
I think of this algorithm as a pair of nested loops:

while (ref == null && stack.isNotEmpty) {
  ref = stack.removeLast().firstRef;
  while (ref != null && ref.parent is Refinement) {
    stack.add(ref.parent);
    ref = ref.next;
  }
}
if (ref == null) {
  current = next = null;
  return false;
}
current = ref;
next = ref.next;
return true;

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes_sexpr.dart:368: return '(Refinement
$value (${node.type}))';
We were only using the extra parens for variable arity parts of the term as a
parsing aid.  I'd rather drop them here since there's only one type..

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:55: /// Moves the binding of
[cont] to before [use].
I'd reword this to use Sink instead of Move because the function won't do
hoisting.  And I'd probably write something other than before.  Maybe 'into the
same scope as [use]'.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:65: void
sinkContinuationToUse(Continuation cont, Expression use) {
Just a comment: there are already a pair of functions in the redundant phi
elimination that do something like this, except that in that case they are
sinking a continuation to just after a definition and not just before a use.

The are _makeUniqueBinding and _moveIntoScopeOf.  It would be nice to find a way
to create a library of such commonly needed utilities so we don't keep
reimplementing them.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:71: // Create a new LetCont
binding only this continuation.
Safe because there are no mutually recursive continuations.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:210: if
(cont.hasExactlyOneUse &&
This algorithm doesn't really work if the continuations of InvokeMethod or
Branch have more than one use, so I'd actually make that into an assert:

if (cont.hasAtLeastOneUse && (first ref is InvokeMethod || first ref is Branch))
{
  assert(cont.hasExactlyOneUse);
}

[asgerf, 2015-09-03 12:31:39]

I've assumed for a long time that only InvokeContinuation did not mandate
complete ownership over its continuation.

I tried briefly to change InvokeMethod et al. to bind their own continuation, so
they have a Continuation instead of a Reference<Continuation>. But the
trampoline code became a mess because there are too many CallExpressions.

If the single-use thing is a problem, I seriously think we should just change
all CallExpressions into Primitives. Inlining shouldn't be that much harder, we
just need to set the return continuation's body and then create a LetCont for
it.

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:126: final List<Primitive> stack =
<Primitive>[];
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> Probably clearer to make this List<Refinement>.

Done.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:137: return false;
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> current should be null when the iterator has finished
> (https://api.dartlang.org/1.12.0/dart-core/Iterator/current.html).

Thanks, nice catch.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:147: }
On 2015/09/03 10:21:05, Kevin Millikin (Google) wrote:
> I think of this algorithm as a pair of nested loops:
> 
> while (ref == null && stack.isNotEmpty) {
>   ref = stack.removeLast().firstRef;
>   while (ref != null && ref.parent is Refinement) {
>     stack.add(ref.parent);
>     ref = ref.next;
>   }
> }
> if (ref == null) {
>   current = next = null;
>   return false;
> }
> current = ref;
> next = ref.next;
> return true;

The problem is that 'next = ref.next' might be a Refinement, which then won't be
skipped in the next iteration because the relevant loop condition is hidden
behind irrelevant one.

I concede that the while(true) style is aesthetically grisly, but it's the only
robust, non-redundant implementation I can find.

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes_sexpr.dart:368: return '(Refinement
$value (${node.type}))';
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> We were only using the extra parens for variable arity parts of the term as a
> parsing aid.  I'd rather drop them here since there's only one type..

Done.

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

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:55: /// Moves the binding of
[cont] to before [use].
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> I'd reword this to use Sink instead of Move because the function won't do
> hoisting.  And I'd probably write something other than before.  Maybe 'into
the
> same scope as [use]'.

Changed to 'immediately above'.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:65: void
sinkContinuationToUse(Continuation cont, Expression use) {
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> Just a comment: there are already a pair of functions in the redundant phi
> elimination that do something like this, except that in that case they are
> sinking a continuation to just after a definition and not just before a use.
> 
> The are _makeUniqueBinding and _moveIntoScopeOf.  It would be nice to find a
way
> to create a library of such commonly needed utilities so we don't keep
> reimplementing them.

That would be great, but sadly I don't have high hopes for this approach.

There are so many slight variations on how to do something that we easily end up
with a helper that looks like it should work for some purpose, but actually
doesn't. In my experience, I need to mentally inline these utility to methods to
check that there isn't an orphaned node or a stale parent pointer in a local
variable or something.

For example, makeUniqueBinding will insert the new LetCont *below* the old
LetCont, but it could just as well insert it *above* it, and the caller may have
to know which one it is, since it may otherwise invalidate a parent pointers
held in a local variable.

And moveIntoScopeOf checks if the continuation is already in scope, which is
likely to be redundant from some potential call sites.

It will probably get even worse when we have to maintain the type of each
primitive, since this may change when moving it around.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:71: // Create a new LetCont
binding only this continuation.
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> Safe because there are no mutually recursive continuations.

There is only one use, so it can't be mutually recursive.

If the above is taken too literally, it could be a dead 
recursive continuation with a single recursive invocation.
Then we would wreak havoc by sinking it into its own body.
I'm now asserting that it's not recursive.

https://codereview.chromium.org/1330503003/diff/40001/pkg/compiler/lib/src/cp...
pkg/compiler/lib/src/cps_ir/insert_refinements.dart:210: if
(cont.hasExactlyOneUse &&
On 2015/09/03 10:21:06, Kevin Millikin (Google) wrote:
> This algorithm doesn't really work if the continuations of InvokeMethod or
> Branch have more than one use, so I'd actually make that into an assert:
> 
> if (cont.hasAtLeastOneUse && (first ref is InvokeMethod || first ref is
Branch))
> {
>   assert(cont.hasExactlyOneUse);
> }

It's being asserted when we sink them to their use site in visitInvokeMethod and
visitBranch.

Is that not enough?

The integrity checker should probably check for this too, it's an easy thing to
check.

[asgerf, 2015-09-03 14:41:55]

Committed patchset #3 (id:60001) manually as
998be61175eaa374c4a0596c2ba1e3391b388ac2 (presubmit successful).