Add a shrinking reduction for dead continuation parameters.

Add a shrinking reduction for dead continuation parameters.

Continuation parameters that have no uses can be eliminated.  This is
similar to the reduction for dead values except that that continuation
invocations need to be adjusted.

Performing a dead parameter reduction can create other dead parameter
redexes, dead value redexes, or continuation eta-redexes.  Detection
of these redexes does not fit the existing model, where an entire
deleted subterm is visited after being eliminated from the whole term.
Instead, they are detected explicit as part of the reduction
implementation.

R=asgerf@google.com
BUG=

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

[asgerf, 2015-01-22 16:02:08]

LGTM.

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

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:635: // bound by the parent.  This
gives constant-time access to the continuation from
long line

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

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:278: // analysis, left as
a possibility for future improvements.
Update comment regarding higher order continuations?

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:299: // exist, implement
the reductions.
Can such code trigger other reductions? Otherwise I speculate that it will only
make the code worse by duplicating phi-assignments, e.g:

Before:

    if (E) {
        S1;
    } else {
        S2;
    }
    x = x1; // phi assignment

After:

    if (E) {
        S1;
        x = x1; // phi assignment
    } else {
        S2;
        x = x1; // phi assignment
    }

Sort of the same problem that was observed when inlining return.

Jumps are often free in the output because of fallthrough, whereas
parameter-passing is expensive.

If the reduction can trigger other reductions then it might be worthwhile if we
have a later phase (maybe on tree IR so fallthrough is visible) where we merge
identical statements preceding a join.

</speculation>

[Kevin Millikin (Google), 2015-01-22 16:16:29]

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

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart:635: // bound by the parent.  This
gives constant-time access to the continuation from
On 2015/01/22 16:02:07, asgerf wrote:
> long line

You are right.  Fixed.

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

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:278: // analysis, left as
a possibility for future improvements.
On 2015/01/22 16:02:08, asgerf wrote:
> Update comment regarding higher order continuations?

Yeah, I'll just get ride of that part.

https://codereview.chromium.org/864293004/diff/1/pkg/compiler/lib/src/cps_ir/...
pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart:299: // exist, implement
the reductions.
On 2015/01/22 16:02:08, asgerf wrote:
> Can such code trigger other reductions? Otherwise I speculate that it will
only
> make the code worse by duplicating phi-assignments, e.g:

No, I don't think it enables other reductions --- it does not decrease the use
count of anything other than the continuation it is eliminating.

Your point about the cost of jumping vs. parameter passing is a good one.  But
that suggests that we might consider eta expansion for continuations, to share
common arguments.

I'll fix the comment to explicitly say that increasing the number of
continuation parameters is not an optimization.

[Kevin Millikin (Google), 2015-01-23 10:27:55]

Committed patchset #2 (id:20001) manually as 43093 (presubmit successful).