Add a shrinking reduction for dead continuation parameters.

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

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart2js.cps_ir.optimizers;
 
 /**
  * [ShrinkingReducer] applies shrinking reductions to CPS terms as described
  * in 'Compiling with Continuations, Continued' by Andrew Kennedy.
  */
@@ skipping 65 matching lines @@
         break;
       case _ReductionKind.DEAD_CONT:
         _reduceDeadCont(task);
         break;
       case _ReductionKind.BETA_CONT_LIN:
         _reduceBetaContLin(task);
         break;
       case _ReductionKind.ETA_CONT:
         _reduceEtaCont(task);
         break;
+      case _ReductionKind.DEAD_PARAMETER:
+        _reduceDeadParameter(task);
+        break;
       default:
         assert(false);
     }
   }
 
   /// Applies the dead-val reduction:
   ///   letprim x = V in E -> E (x not free in E).
   void _reduceDeadVal(_ReductionTask task) {
     assert(_isDeadVal(task.node));
 
@@ skipping 73 matching lines @@
 
     InvokeContinuation invoke = cont.body;
     Continuation wrappedCont = invoke.continuation.definition;
 
     // Replace all occurrences with the wrapped continuation.
     wrappedCont.substituteFor(cont);
 
     // 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.
 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;
   }
 
   if (cont.firstRef.parent is InvokeContinuation) {
     InvokeContinuation invoke = cont.firstRef.parent;
     return (cont == invoke.continuation.definition);
   }
 
   return false;
 }
 
 /// 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;
   }
 
   // TODO(jgruber): Linear in the parameter count. Can be improved to near
   // constant time by using union-find data structure.
   for (int i = 0; i < cont.parameters.length; i++) {
     if (invoke.arguments[i].definition != cont.parameters[i]) {
       return false;
     }
   }
 
   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;
 
   _RedexVisitor(this.worklist);
 
   void processLetPrim(LetPrim node) {
     if (_isDeadVal(node)) {
       worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node));
     }
   }
 
   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 (_isBetaContLin(node)){
+      worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, 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));
+    }
+  }
+
+  void processParameter(Parameter node) {
+    if (_isDeadParameter(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.DEAD_PARAMETER, node));
     }
   }
 }
 
 /// Traverses a deleted CPS term, marking nodes that might participate in a
 /// redex as deleted and adding newly created redexes to the worklist.
 ///
 /// Deleted nodes that might participate in a reduction task are marked so that
 /// any corresponding tasks can be skipped.  Nodes are marked so by setting
 /// their parent to the deleted sentinel.
@@ skipping 18 matching lines @@
       Node parent = primitive.parent;
       // The parent might be the deleted sentinel, or it might be a
       // Continuation or FunctionDefinition if the primitive is an argument.
       if (parent is LetPrim && _isDeadVal(parent)) {
         worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent));
       }
     } else if (reference.definition is Continuation) {
       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
           // continuation is still in use, it is either dead and will be
           // removed, or it is called nonrecursively outside its body.
           cont.isRecursive = false;
         }
         if (_isDeadCont(cont)) {
           worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, cont));
+        } else if (_isBetaContLin(cont)) {
+          worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, cont));
         }
       }
     }
   }
 }
 
 /// Traverses the CPS term and sets node.parent for each visited node.
 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);
   }
 
   // Expressions.
 
   processFieldInitializer(FieldInitializer node) {
     node.body.body.parent = node;
   }
 
   processSuperInitializer(SuperInitializer node) {
     node.arguments.forEach(
         (RunnableBody argument) => argument.body.parent = node);
   }
 
   processLetPrim(LetPrim node) {
     node.primitive.parent = node;
     node.body.parent = node;
   }
 
   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;
   }
 
   processInvokeStatic(InvokeStatic node) {
     node.arguments.forEach((Reference ref) => ref.parent = node);
     node.continuation.parent = node;
   }
 
   processInvokeContinuation(InvokeContinuation node) {
     node.continuation.parent = node;
@@ skipping 54 matching lines @@
       entry.key.parent = node;
       entry.value.parent = node;
     });
   }
 
   processCreateFunction(CreateFunction node) {
     node.definition.parent = node;
   }
 
   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.
 
   processIsTrue(IsTrue node) {
     node.value.parent = node;
   }
 
   // JavaScript specific nodes.
 
@@ skipping 28 matching lines @@
   final String name;
   final int hashCode;
 
   const _ReductionKind(this.name, this.hashCode);
 
   static const _ReductionKind DEAD_VAL = const _ReductionKind('dead-val', 0);
   static const _ReductionKind DEAD_CONT = const _ReductionKind('dead-cont', 1);
   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;
 }
 
 /// Represents a reduction task on the worklist. Implements both hashCode and
 /// operator== since instantiations are used as Set elements.
 class _ReductionTask {
   final _ReductionKind kind;
   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) {
     return (that.kind == this.kind && that.node == this.node);
   }
 
   String toString() => "$kind: $node";
 }
 
 /// A dummy class used solely to mark nodes as deleted once they are removed
 /// from a term.
 class _DeletedNode extends Node {
   accept(_) => null;
 }