Add a shrinking reduction for dead continuation parameters.

pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart

Index: pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
diff --git a/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart b/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
index 92bb00a6de7e307ba303633c94931308ee6edbd9..666e107da2bdb72a03f301b4cbbcff0333c621d9 100644
--- a/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
+++ b/pkg/compiler/lib/src/cps_ir/shrinking_reductions.dart
@@ -83,6 +83,9 @@ class ShrinkingReducer extends PassMixin {
       case _ReductionKind.ETA_CONT:
         _reduceEtaCont(task);
         break;
+      case _ReductionKind.DEAD_PARAMETER:
+        _reduceDeadParameter(task);
+        break;
       default:
         assert(false);
     }
@@ -176,6 +179,51 @@ class ShrinkingReducer extends PassMixin {
     // Perform bookkeeping on removed body and scan for new redexes.
     new _RemovalVisitor(_worklist).visit(cont);
   }
+
+  void _reduceDeadParameter(_ReductionTask task) {
+    assert(_isDeadParameter(task.node));
+
+    Parameter parameter = task.node;
+    Continuation continuation = parameter.parent;
+    int index = parameter.parent_index;
+
+    // Remove the index'th argument from each invocation.
+    Reference<Continuation> current = continuation.firstRef;
+    while (current != null) {
+      InvokeContinuation invoke = current.parent;
+      Reference<Primitive> argument = invoke.arguments[index];
+      argument.unlink();
+      // Removing an argument can create a dead parameter or dead value redex.
+      if (argument.definition is Parameter) {
+        if (_isDeadParameter(argument.definition)) {
+          _worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER,
+                                           argument.definition));
+        }
+      } else {
+        Node parent = argument.definition.parent;
+        if (parent is LetPrim) {
+          if (_isDeadVal(parent)) {
+            _worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent));
+          }
+        }
+      }
+      invoke.arguments.removeAt(index);
+      current = current.next;
+    }
+    // Copy the parameters above index down.
+    List<Parameter> parameters = continuation.parameters;
+    for (int i = index; i < parameters.length - 1; ++i) {
+      Parameter p = parameters[i + 1];
+      parameters[i] = p;
+      p.parent_index = i;
+    }
+    parameters.removeLast();
+
+    // Removing an unused parameter can create an eta-redex.
+    if (_isEtaCont(continuation)) {
+      _worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, continuation));
+    }
+  }
 }
 
 /// Returns true iff the bound primitive is unused.
@@ -183,14 +231,20 @@ bool _isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;
 
 /// Returns true iff the continuation is unused.
 bool _isDeadCont(Continuation cont) {
-  assert(!cont.isReturnContinuation);
-  return !cont.hasAtLeastOneUse;
+  return !cont.isReturnContinuation && !cont.hasAtLeastOneUse;
 }
 
-/// Returns true iff the continuation is used exactly once, and that
-/// use is as the continuation of a continuation invocation.
+/// Returns true iff the continuation has a body (i.e., it is not the return
+/// continuation), it is used exactly once, and that use is as the continuation
+/// of a continuation invocation.
 bool _isBetaContLin(Continuation cont) {
-  if (!cont.hasExactlyOneUse) {
+  // There is a restriction on continuation eta-redexes that the body is not an
+  // invocation of the return continuation, because that leads to worse code
+  // when translating back to direct style (it duplicates returns).  There is no
+  // such restriction here because continuation beta-reduction is only performed
+  // for singly referenced continuations. Thus, there is no possibility of code
+  // duplication.
+  if (cont.isReturnContinuation || !cont.hasExactlyOneUse) {
     return false;
   }
 
@@ -205,27 +259,44 @@ bool _isBetaContLin(Continuation cont) {
 /// Returns true iff the continuation consists of a continuation
 /// invocation, passing on all parameters. Special cases exist (see below).
 bool _isEtaCont(Continuation cont) {
-  if (cont.body is! InvokeContinuation) {
+  if (cont.isReturnContinuation || cont.body is! InvokeContinuation) {
     return false;
   }
 
   InvokeContinuation invoke = cont.body;
   Continuation invokedCont = invoke.continuation.definition;
 
-  // Do not eta-reduce return join-points since the resulting code is worse
+  // Do not eta-reduce return join-points since the direct-style code is worse
   // in the common case (i.e. returns are moved inside `if` branches).
   if (invokedCont.isReturnContinuation) {
     return false;
   }
 
   // Translation to direct style generates different statements for recursive
-  // and non-recursive invokes. It should be possible to apply eta-cont, but
-  // higher order continuations require escape analysis, left as a possibility
-  // for future improvements.
+  // and non-recursive invokes. It should be possible to apply eta-cont if this
+  // is not a self-invocation, but higher order continuations require escape
+  // analysis, left as a possibility for future improvements.

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

Update comment regarding higher order continuations?

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

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

   if (invoke.isRecursive) {
     return false;
   }
 
+  // If cont has more parameters than the invocation has arguments, the extra
+  // parameters will be dead and dead-parameter will eventually create the
+  // eta-redex if possible.
+  //
+  // If cont has fewer parameters than the invocation has arguments then a
+  // reduction is still possible, since the extra invocation arguments must be
+  // in scope at all the invocations of cont.  For example:
+  //
+  // let cont k1(x1) = k0(x0, x1) in E -eta-> E'
+  // where E' has k0(x0, v) substituted for each k1(v).
+  //
+  // If the invocation's arguments are simply a permutation of cont's
+  // parameters, then there is likewise still a possible reduction that involves
+  // rewriting the invocations of cont.
+  //
+  // TODO(kmillikin): find real occurrences of these patterns, and if they
+  // exist, implement the reductions.

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

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]

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.

   if (cont.parameters.length != invoke.arguments.length) {
     return false;
   }
@@ -241,6 +312,28 @@ bool _isEtaCont(Continuation cont) {
   return true;
 }
 
+bool _isDeadParameter(Parameter parameter) {
+  // We cannot remove function parameters as an intraprocedural optimization.
+  if (parameter.parent is! Continuation || parameter.hasAtLeastOneUse) {
+    return false;
+  }
+
+  // We cannot remove the parameter to a call continuation, because the
+  // resulting expression will not be well-formed (call continuations have
+  // exactly one argument).  The return continuation is a call continuation, so
+  // we cannot remove its dummy parameter.
+  Continuation continuation = parameter.parent;
+  if (continuation.isReturnContinuation) return false;
+  Reference<Continuation> current = continuation.firstRef;
+  while (current != null) {
+    if (current.parent is! InvokeContinuation) return false;
+    InvokeContinuation invoke = current.parent;
+    if (invoke.continuation.definition != continuation) return false;
+    current = current.next;
+  }
+  return true;
+}
+
 /// Traverses a term and adds any found redexes to the worklist.
 class _RedexVisitor extends RecursiveVisitor {
   final Set<_ReductionTask> worklist;
@@ -254,12 +347,25 @@ class _RedexVisitor extends RecursiveVisitor {
   }
 
   void processContinuation(Continuation node) {
+    // Continuation beta- and eta-redexes can overlap, namely when an eta-redex
+    // is invoked exactly once.  We prioritize continuation beta-redexes over
+    // eta-redexes because some reductions (e.g., dead parameter elimination)
+    // can destroy a continuation eta-redex.  If we prioritized eta- over
+    // beta-redexes, this would implicitly "create" the corresponding beta-redex
+    // (in the sense that it would still apply) and the algorithm would not
+    // detect it.
     if (_isDeadCont(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node));
-    } else if (_isEtaCont(node)) {
-      worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node));
     } else if (_isBetaContLin(node)){
       worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node));
+    } else if (_isEtaCont(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node));
+    }
+  }
+
+  void processParameter(Parameter node) {
+    if (_isDeadParameter(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, node));
     }
   }
 }
@@ -298,7 +404,7 @@ class _RemovalVisitor extends RecursiveVisitor {
       Continuation cont = reference.definition;
       Node parent = cont.parent;
       // The parent might be the deleted sentinel, or it might be a
-      // FunctionDefinition if the continuation is the return continuation.
+      // RunnableBody if the continuation is the return continuation.
       if (parent is LetCont) {
         if (cont.isRecursive && cont.hasAtMostOneUse) {
           // Convert recursive to nonrecursive continuations.  If the
@@ -308,6 +414,8 @@ class _RemovalVisitor extends RecursiveVisitor {
         }
         if (_isDeadCont(cont)) {
           worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, cont));
+        } else if (_isBetaContLin(cont)) {
+          worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, cont));
         }
       }
     }
@@ -318,16 +426,25 @@ class _RemovalVisitor extends RecursiveVisitor {
 class ParentVisitor extends RecursiveVisitor {
   processFunctionDefinition(FunctionDefinition node) {
     node.body.parent = node;
-    node.parameters.forEach((Definition p) => p.parent = node);
+    int index = 0;
+    node.parameters.forEach((Parameter parameter) {
+      parameter.parent = node;
+      parameter.parent_index = index++;
+    });
   }
 
   processRunnableBody(RunnableBody node) {
+    node.returnContinuation.parent = node;
     node.body.parent = node;
   }
 
   processConstructorDefinition(ConstructorDefinition node) {
     node.body.parent = node;
-    node.parameters.forEach((Definition p) => p.parent = node);
+    int index = 0;
+    node.parameters.forEach((Parameter parameter) {
+      parameter.parent = node;
+      parameter.parent_index = index++;
+    });
     node.initializers.forEach((Initializer i) => i.parent = node);
   }
 
@@ -348,11 +465,11 @@ class ParentVisitor extends RecursiveVisitor {
   }
 
   processLetCont(LetCont node) {
-    for (int i = 0; i < node.continuations.length; ++i) {
-      Continuation cont = node.continuations[i];
-      cont.parent = node;
-      cont.parent_index = i;
-    }
+    int index = 0;
+    node.continuations.forEach((Continuation continuation) {
+      continuation.parent = node;
+      continuation.parent_index = index++;
+    });
     node.body.parent = node;
   }
 
@@ -427,8 +544,12 @@ class ParentVisitor extends RecursiveVisitor {
   }
 
   processContinuation(Continuation node) {
-    node.body.parent = node;
-    node.parameters.forEach((Parameter param) => param.parent = node);
+    if (node.body != null) node.body.parent = node;
+    int index = 0;
+    node.parameters.forEach((Parameter parameter) {
+      parameter.parent = node;
+      parameter.parent_index = index++;
+    });
   }
 
   // Conditions.
@@ -477,6 +598,8 @@ class _ReductionKind {
   static const _ReductionKind BETA_CONT_LIN =
       const _ReductionKind('beta-cont-lin', 2);
   static const _ReductionKind ETA_CONT = const _ReductionKind('eta-cont', 3);
+  static const _ReductionKind DEAD_PARAMETER =
+      const _ReductionKind('dead-parameter', 4);
 
   String toString() => name;
 }
@@ -488,12 +611,12 @@ class _ReductionTask {
   final Node node;
 
   int get hashCode {
-    assert(kind.hashCode < (1 << 2));
-    return (node.hashCode << 2) | kind.hashCode;
+    assert(kind.hashCode < (1 << 3));
+    return (node.hashCode << 3) | kind.hashCode;
   }
 
   _ReductionTask(this.kind, this.node) {
-    assert(node is Continuation || node is LetPrim);
+    assert(node is Continuation || node is LetPrim || node is Parameter);
   }
 
   bool operator==(_ReductionTask that) {