Implement shrinking reductions in CPS IR

Implement shrinking reductions in CPS IR

Shrinking reductions consist of

* dead-cont:
  letprim x = V in K -> K (x not free in K),
* dead-val:
  letcont k x = L in K -> K (k not free in K),
* beta-cont-lin:
  letcont k x = K in C[k y] ->C[K[y/x]] (k not free in C), and
* eta-cont:
  letcont k x = j x in K -> K[j/k]

as described in 'Compiling with Continuations, Continued' by Andrew
Kennedy.

This also requires adding parent pointers to both Node and Reference
classes as well as setting them in a separate pass.

BUG=
R=kmillikin@google.com, sigurdm@google.com

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

[sigurdm, 2014-08-01 09:09:41]

lgtm

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart
(right):

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:63:
if (!_redexVisitor.isDeadVal(task.node)) {
Add comment why this can happen

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:117:
letCont.body.parent = parent;
You might be able to factor these two lines out.

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:428:
/// operator== since instatiations are used as Set elements.
typo: instatiations => instantiations

[jgruber1, 2014-08-07 09:07:36]

Fixed several issues exposed by later commits and tests, ptal.

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart
(right):

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:63:
if (!_redexVisitor.isDeadVal(task.node)) {
On 2014/08/01 09:09:41, sigurdm wrote:
> Add comment why this can happen

Done, and replaced by assert in dead-* reductions.

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:117:
letCont.body.parent = parent;
On 2014/08/01 09:09:41, sigurdm wrote:
> You might be able to factor these two lines out.

Done.

https://codereview.chromium.org/417043003/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:428:
/// operator== since instatiations are used as Set elements.
On 2014/08/01 09:09:41, sigurdm wrote:
> typo: instatiations => instantiations

Done.

[Kevin Millikin (Google), 2014-08-11 08:59:03]

This is promising.  Here's a first round of comments.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart
(right):

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:38:
void _removeNode(InteriorNode node) {
Could we make this a method on the InteriorNode class?  It seems generally
useful.  Is the problem that there's no generic way to mark them as deleted?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:73:
///   letprim x = V in K -> K (x not free in K).
Picky: I would not use K as a metavariable ranging over expressions.  E is
better?  M is also standard.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:86:
///   letcont k x = L in K -> K (k not free in K).
Picky: Instead of L and K, use E0 and E1 (or E1 and E2 if you prefer).

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:101:
// Might have been mutated, recheck if reduction is still valid.
Can we give a crisp characterization of how a BetaContLin redex could be
destroyed by another reduction?  Is it due to an overlapping EtaCont reduction?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:107:
LetCont letCont   = task.node;
No need to align the = on subsequent lines.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:112:
Reference ref             = cont.firstRef..unlink();
No need for this alignment of =.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:115:
assert(invoke != null && invokeParent != null);
It's a bit strange to assert invoke != null after invoking a getter on it
(.parent).  You could move assert(invoke != null) earlier (preferred) or else
move the whole thing assert(invoke != null && invoke.parent != null) earlier.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:122:
Reference argRef = invoke.arguments[i]..unlink();
Can't we achieve this unlinking (and above for cont.firstRef) by calling
_RemovalRedexVisitor.visit on the InvokeContinuation?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:129:
// blowup.
Hmmm.  Is it possible to scan the body after beta reduction only (and not
initially for BetaContLin redexes) instead?  Is it better?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:169:
void processLetCont(LetCont node) {
DeadCont and BetaContLin/EtaCont are mutually exclusive.  EtaCont and
BetaContLin can be overlapping --- in the overlapping case applying EtaCont is
simpler (I think).  So can we write this as:

if (isDeadCont...) {
} else if (isEtaCont...) {
} else if (isBetaContLin...) {
}

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:181:
void processReference(Reference reference) {
This seems fishy to me.  It finds a reference during visiting a term and asks if
the reference is to a definition with no references?

If we need such a function to process subterms that are being removed, I don't
think it should be part of this visitor.  Just move it into processReference for
the deleted visitor?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:197:
bool isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;
This predicate and the other three don't need access to the state of the
_RedexVisitor.  I suggest making them static methods or even better, just
top-level functions.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:207:
if (!(cont.firstRef.parent is InvokeContinuation)) {
Maybe simpler:

Reference use = cont.firstRef;
return use.parent is InvokeContinuation && use == use.parent.continuation;

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:223:
// these require a continuation that is used exactly once.
This comment should say why they require such a continuation --- that's the
important thing.

Is it because the DS translation assumes it?  I didn't think that was the case
for InvokeMethod (at least), but maybe it is.  If so, let's say that and add a
TODO(kmillikin) to modify the DS translation to handle multiply-used
continuations for Invoke.

Note also that eta reduction might also be possible in the case where we have:

let cont k(v) = k'(v) in ... InvokeMethod(v, f, args, k).

And k' has a single use (in the body of k).

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:249:
if (invoke.isRecursive) {
Is it possible to eta-reduce recursive invocations?  That seems like it would
be:

let cont k(v) = k'(v) in ...

where k'(v) is a recursive invocation, that is occurring in the body of k'.  The
uses of k can only be in the let cont body, so we ought to be able to figure out
a way to replace them with k'.

If it doesn't work, can you add a TODO explaining what breaks (even just the
test) and to investigate?

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:302:
void setParent(Node parent, Node child) {
The order of arguments seems wrong, I would expect setParent(child, parent).

I'm not sure why this isn't a method on Node anyway (i.e., the .parent setter).

[jgruber1, 2014-08-11 13:00:59]

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart
(right):

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:38:
void _removeNode(InteriorNode node) {
On 2014/08/11 08:59:02, kmillikin wrote:
> Could we make this a method on the InteriorNode class?  It seems generally
> useful.  Is the problem that there's no generic way to mark them as deleted?

Acknowledged.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:73:
///   letprim x = V in K -> K (x not free in K).
On 2014/08/11 08:59:03, kmillikin wrote:
> Picky: I would not use K as a metavariable ranging over expressions.  E is
> better?  M is also standard.

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:86:
///   letcont k x = L in K -> K (k not free in K).
On 2014/08/11 08:59:02, kmillikin wrote:
> Picky: Instead of L and K, use E0 and E1 (or E1 and E2 if you prefer).

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:101:
// Might have been mutated, recheck if reduction is still valid.
On 2014/08/11 08:59:02, kmillikin wrote:
> Can we give a crisp characterization of how a BetaContLin redex could be
> destroyed by another reduction?  Is it due to an overlapping EtaCont
reduction?

Done. A simple case is using dead-cont:

letcont k0 x0 = E0 in
  letcont k1 x1 = k0 x1 in
    return x2

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:107:
LetCont letCont   = task.node;
On 2014/08/11 08:59:02, kmillikin wrote:
> No need to align the = on subsequent lines.

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:112:
Reference ref             = cont.firstRef..unlink();
On 2014/08/11 08:59:02, kmillikin wrote:
> No need for this alignment of =.

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:115:
assert(invoke != null && invokeParent != null);
On 2014/08/11 08:59:02, kmillikin wrote:
> It's a bit strange to assert invoke != null after invoking a getter on it
> (.parent).  You could move assert(invoke != null) earlier (preferred) or else
> move the whole thing assert(invoke != null && invoke.parent != null) earlier.

Removed the assert since both invoke and invokeParent are dereferenced in
surrounding code.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:122:
Reference argRef = invoke.arguments[i]..unlink();
On 2014/08/11 08:59:02, kmillikin wrote:
> Can't we achieve this unlinking (and above for cont.firstRef) by calling
> _RemovalRedexVisitor.visit on the InvokeContinuation?

Good point, done. Added an additional check for deleted nodes in the visitor to
avoid generation of unnecessary dead-cont tasks here.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:129:
// blowup.
On 2014/08/11 08:59:02, kmillikin wrote:
> Hmmm.  Is it possible to scan the body after beta reduction only (and not
> initially for BetaContLin redexes) instead?  Is it better?

Acknowledged.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:169:
void processLetCont(LetCont node) {
On 2014/08/11 08:59:02, kmillikin wrote:
> DeadCont and BetaContLin/EtaCont are mutually exclusive.  EtaCont and
> BetaContLin can be overlapping --- in the overlapping case applying EtaCont is
> simpler (I think).  So can we write this as:
> 
> if (isDeadCont...) {
> } else if (isEtaCont...) {
> } else if (isBetaContLin...) {
> }

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:181:
void processReference(Reference reference) {
On 2014/08/11 08:59:02, kmillikin wrote:
> This seems fishy to me.  It finds a reference during visiting a term and asks
if
> the reference is to a definition with no references?
> 
> If we need such a function to process subterms that are being removed, I don't
> think it should be part of this visitor.  Just move it into processReference
for
> the deleted visitor?

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:197:
bool isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;
On 2014/08/11 08:59:02, kmillikin wrote:
> This predicate and the other three don't need access to the state of the
> _RedexVisitor.  I suggest making them static methods or even better, just
> top-level functions.

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:207:
if (!(cont.firstRef.parent is InvokeContinuation)) {
On 2014/08/11 08:59:02, kmillikin wrote:
> Maybe simpler:
> 
> Reference use = cont.firstRef;
> return use.parent is InvokeContinuation && use == use.parent.continuation;

Needs a cast of use.parent to InvokeContinuation in order to access
.continuation. Modified this to
avoid the negative conditional.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:223:
// these require a continuation that is used exactly once.
On 2014/08/11 08:59:03, kmillikin wrote:
> This comment should say why they require such a continuation --- that's the
> important thing.
> 
> Is it because the DS translation assumes it?  I didn't think that was the case
> for InvokeMethod (at least), but maybe it is.  If so, let's say that and add a
> TODO(kmillikin) to modify the DS translation to handle multiply-used
> continuations for Invoke.
> 
> Note also that eta reduction might also be possible in the case where we have:
> 
> let cont k(v) = k'(v) in ... InvokeMethod(v, f, args, k).
> 
> And k' has a single use (in the body of k).

Done.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:249:
if (invoke.isRecursive) {
On 2014/08/11 08:59:02, kmillikin wrote:
> Is it possible to eta-reduce recursive invocations?  That seems like it would
> be:
> 
> let cont k(v) = k'(v) in ...
> 
> where k'(v) is a recursive invocation, that is occurring in the body of k'. 
The
> uses of k can only be in the let cont body, so we ought to be able to figure
out
> a way to replace them with k'.
> 
> If it doesn't work, can you add a TODO explaining what breaks (even just the
> test) and to investigate?

At the moment, eta-cont should be applicable to recursive invokes with some
care;
but upcoming higher-order continuations will make this more complicated since we
will have to check whether the invoke is within the body of the continuation or
not.
Leaving as future work + explanatory comment.

https://codereview.chromium.org/417043003/diff/40001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/cps_ir/shrinking_reductions.dart:302:
void setParent(Node parent, Node child) {
On 2014/08/11 08:59:02, kmillikin wrote:
> The order of arguments seems wrong, I would expect setParent(child, parent).
> 
> I'm not sure why this isn't a method on Node anyway (i.e., the .parent
setter).

Done, inlined both methods.

[Kevin Millikin (Google), 2014-08-11 13:16:27]

Yes, LGTM.

[jgruber1, 2014-08-11 13:18:15]

Committed patchset #4 manually as 39087 (presubmit successful).