Reapply "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) {
+    // Continuation eta-reduction can destroy a dead parameter redex.  For
+    // example, in the term:
+    //
+    // let cont k0(v0) = /* v0 is not used */ in
+    //   let cont k1(v1) = k0(v1) in
+    //     call foo () k1
+    //
+    // Continuation eta-reduction of k1 gives:
+    //
+    // let cont k0(v0) = /* v0 is not used */ in
+    //   call foo () k0
+    //
+    // Where the dead parameter reduction is no longer valid because we do not
+    // allow removing the paramter of call continuations.  We disallow such eta
+    // reductions in [_isEtaCont].
+    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;
   }
 
+  // Do not perform reductions replace a function call continuation with a

[asgerf, 2015/01/26 12:56:57]

*that* replace or *replacing*

+  // non-call continuation.  The invoked continuation is definitely not a call
+  // continuation, because it has a direct invocation in this continuation's
+  // body.
+  bool isCallContinuation(Continuation continuation) {
+    Reference<Continuation> current = cont.firstRef;
+    while (current != null) {
+      if (current.parent is InvokeContinuation) {
+        InvokeContinuation invoke = current.parent;
+        if (invoke.continuation.definition == continuation) return false;
+      }
+      current = current.next;
+    }
+    return true;
+  }
+  if (isCallContinuation(cont)) {
+    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 still be possible to apply eta-cont if
+  // this is not a self-invocation.
+  //
+  // TODO(kmillikin): Remove this restriction if it makes sense to do so.
   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 the invocation's arguments are simply a permutation of cont's
+  // parameters, then there is likewise a possible reduction that involves
+  // rewriting the invocations of cont.  We are missing that reduction here.
+  //
+  // If cont has fewer parameters than the invocation has arguments then a
+  // reduction would 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).
+  //
+  // HOWEVER, adding continuation parameters is unlikely to be an optimization
+  // since it duplicates assignments used in direct-style to implement parameter
+  // passing.
+  //
+  // TODO(kmillikin): find real occurrences of these patterns, and see if they
+  // can be optimized.
   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((Definition parameter) {
+      parameter.parent = node;
+      if (parameter is Parameter) 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;
 }