Implement shrinking reductions in CPS IR

sdk/lib/_internal/compiler/implementation/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.optimizers;
+
+/**
+ * [[ShrinkingReducer]] applies shrinking reductions to CPS terms as described
+ * in 'Compiling with Continuations, Continued' by Andrew Kennedy.
+ */
+class ShrinkingReducer implements Pass {
+  _RedexVisitor _redexVisitor;
+  Set<_ReductionTask> _worklist;
+
+  static final _DeletedNode _DELETED = new _DeletedNode();
+
+  /// Applies shrinking reductions to root, mutating root in the process.
+  void rewrite(FunctionDefinition root) {
+    _worklist = new Set<_ReductionTask>();
+    _redexVisitor = new _RedexVisitor(_worklist);
+
+    // Set all parent pointers.
+    new _ParentVisitor().visit(root);
+
+    // Sweep over the term, collecting redexes into the worklist.
+    _redexVisitor.visitFunctionDefinition(root);
+
+    // Process the worklist.
+    while (_worklist.isNotEmpty) {
+      _ReductionTask task = _worklist.first;
+      _worklist.remove(task);
+      _processTask(task);
+    }
+  }
+
+  /// Removes the given node from the CPS graph, replacing it with its body
+  /// and marking it as deleted. The node's parent must be a [[InteriorNode]].
+  void _removeNode(InteriorNode node) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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?

[jgruber1, 2014/08/11 13:00:58]

Acknowledged.

+    Node body           = node.body;
+    InteriorNode parent = node.parent;
+    assert(parent.body == node);
+
+    body.parent = parent;
+    parent.body = body;
+    node.parent = _DELETED;
+  }
+
+  void _processTask(_ReductionTask task) {
+    // Lazily skip tasks for deleted nodes.
+    if (task.node.parent == _DELETED) {
+      return;
+    }
+
+    switch (task.kind) {
+      case _ReductionKind.DEAD_VAL:
+        _reduceDeadVal(task);
+        break;
+      case _ReductionKind.DEAD_CONT:
+        _reduceDeadCont(task);
+        break;
+      case _ReductionKind.BETA_CONT_LIN:
+        _reduceBetaContLin(task);
+        break;
+      case _ReductionKind.ETA_CONT:
+        _reduceEtaCont(task);
+        break;
+      default:
+        assert(false);
+    }
+  }
+
+  /// Applies the dead-val reduction:
+  ///   letprim x = V in K -> K (x not free in K).

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

Picky: I would not use K as a metavariable ranging over expressions.  E is
better?  M is also standard.

[jgruber1, 2014/08/11 13:00:58]

Done.

+  void _reduceDeadVal(_ReductionTask task) {
+    assert(_redexVisitor.isDeadVal(task.node));
+
+    // Remove dead primitive.
+    LetPrim letPrim = task.node;;
+    _removeNode(letPrim);
+
+    // Perform bookkeeping on removed body and scan for new redexes.
+    new _RemovalRedexVisitor(_worklist).visit(letPrim.primitive);
+  }
+
+  /// Applies the dead-cont reduction:
+  ///   letcont k x = L in K -> K (k not free in K).

[Kevin Millikin (Google), 2014/08/11 08:59:02]

Picky: Instead of L and K, use E0 and E1 (or E1 and E2 if you prefer).

[jgruber1, 2014/08/11 13:00:58]

Done.

+  void _reduceDeadCont(_ReductionTask task) {
+    assert(_redexVisitor.isDeadCont(task.node));
+
+    // Remove dead continuation.
+    LetCont letCont = task.node;
+    _removeNode(letCont);
+
+    // Perform bookkeeping on removed body and scan for new redexes.
+    new _RemovalRedexVisitor(_worklist).visit(letCont.continuation);
+  }
+
+  /// Applies the beta-cont-lin reduction:
+  ///   letcont k x = K in C[k y] -> C[K[y/x]] (k not free in C).
+  void _reduceBetaContLin(_ReductionTask task) {
+    // Might have been mutated, recheck if reduction is still valid.

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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?

[jgruber1, 2014/08/11 13:00:58]

Done. A simple case is using dead-cont:

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

+    if (!_redexVisitor.isBetaContLin(task.node)) {
+      return;
+    }
+
+    // Remove the continuation.
+    LetCont letCont   = task.node;

[Kevin Millikin (Google), 2014/08/11 08:59:02]

No need to align the = on subsequent lines.

[jgruber1, 2014/08/11 13:00:58]

Done.

+    Continuation cont = letCont.continuation;
+    _removeNode(letCont);
+
+    // Replace its invocation with the continuation body.
+    Reference ref             = cont.firstRef..unlink();

[Kevin Millikin (Google), 2014/08/11 08:59:02]

No need for this alignment of =.

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

Done.

+    InvokeContinuation invoke = ref.parent;
+    InteriorNode invokeParent = invoke.parent;
+    assert(invoke != null && invokeParent != null);

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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.

[jgruber1, 2014/08/11 13:00:58]

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

+
+    cont.body.parent = invokeParent;
+    invokeParent.body = cont.body;
+
+    // Substitute the invocation argument for the continuation parameter.
+    for (int i = 0; i < invoke.arguments.length; i++) {
+      Reference argRef = invoke.arguments[i]..unlink();

[Kevin Millikin (Google), 2014/08/11 08:59:02]

Can't we achieve this unlinking (and above for cont.firstRef) by calling
_RemovalRedexVisitor.visit on the InvokeContinuation?

[jgruber1, 2014/08/11 13:00:58]

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

+      argRef.definition.substituteFor(cont.parameters[i]);
+      // Scan for new redexes in substituted references.
+      _redexVisitor.processReference(argRef);
+    }
+
+    // Do not scan for new redexes in the continuation body to avoid quadratic
+    // blowup.

[Kevin Millikin (Google), 2014/08/11 08:59:02]

Hmmm.  Is it possible to scan the body after beta reduction only (and not
initially for BetaContLin redexes) instead?  Is it better?

[jgruber1, 2014/08/11 13:00:57]

Acknowledged.

+  }
+
+  /// Applies the eta-cont reduction:
+  ///   letcont k x = j x in K -> K[j/k].
+  /// If k is unused, degenerates to dead-cont.
+  void _reduceEtaCont(_ReductionTask task) {
+    // Might have been mutated, recheck if reduction is still valid.
+    if (!_redexVisitor.isEtaCont(task.node)) {
+      return;
+    }
+
+    // Remove the continuation.
+    LetCont letCont   = task.node;
+    Continuation cont = letCont.continuation;
+    _removeNode(letCont);
+
+    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 _RemovalRedexVisitor(_worklist).visit(cont);
+  }
+}
+
+/// 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 processLetCont(LetCont node) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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...) {
}

[jgruber1, 2014/08/11 13:00:57]

Done.

+    if (isDeadCont(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, node));
+    }
+    if (isBetaContLin(node)){
+      worklist.add(new _ReductionTask(_ReductionKind.BETA_CONT_LIN, node));
+    }
+    if (isEtaCont(node)) {
+      worklist.add(new _ReductionTask(_ReductionKind.ETA_CONT, node));
+    }
+  }
+
+  void processReference(Reference reference) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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?

[jgruber1, 2014/08/11 13:00:58]

Done.

+    if (reference.definition is Primitive) {
+      Primitive primitive = reference.definition;
+      Node parent = primitive.parent;
+      if (parent is LetPrim && isDeadVal(parent)) {
+        worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, parent));
+      }
+    } else if (reference.definition is Continuation) {
+      Continuation continuation = reference.definition;
+      Node parent = continuation.parent;
+      if (parent is LetCont && isDeadCont(parent)) {
+        worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent));
+      }
+    }
+  }
+
+  bool isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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.

[jgruber1, 2014/08/11 13:00:58]

Done.

+
+  bool isDeadCont(LetCont node) => !node.continuation.hasAtLeastOneUse;
+
+  bool isBetaContLin(LetCont node) {
+    Continuation cont = node.continuation;
+    if (!cont.hasExactlyOneUse) {
+      return false;
+    }
+
+    if (!(cont.firstRef.parent is InvokeContinuation)) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

Maybe simpler:

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

[jgruber1, 2014/08/11 13:00:57]

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

+      return false;
+    }
+
+    InvokeContinuation invoke = cont.firstRef.parent;
+    return (cont == invoke.continuation.definition);
+  }
+
+  bool isEtaCont(LetCont node) {
+    Continuation cont = node.continuation;
+    if (!(cont.body is InvokeContinuation)) {
+      return false;
+    }
+
+    // Special case for continuations passed into one of { InvokeConstructor,
+    // InvokeMethod, InvokeStatic, ConcatenateStrings }, since
+    // these require a continuation that is used exactly once.

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

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).

[jgruber1, 2014/08/11 13:00:58]

Done.

+    if (cont.hasExactlyOneUse) {
+      if (cont.firstRef.parent is InvokeConstructor) {
+        InvokeConstructor parent = cont.firstRef.parent;
+        if (parent.continuation == cont.firstRef) {
+          return false;
+        }
+      } else if (cont.firstRef.parent is InvokeMethod) {
+        InvokeMethod parent = cont.firstRef.parent;
+        if (parent.continuation == cont.firstRef) {
+          return false;
+        }
+      } else if (cont.firstRef.parent is InvokeStatic) {
+        InvokeStatic parent = cont.firstRef.parent;
+        if (parent.continuation == cont.firstRef) {
+          return false;
+        }
+      } else if (cont.firstRef.parent is ConcatenateStrings) {
+        ConcatenateStrings parent = cont.firstRef.parent;
+        if (parent.continuation == cont.firstRef) {
+          return false;
+        }
+      }
+    }
+
+    InvokeContinuation invoke = cont.body;
+    if (invoke.isRecursive) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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?

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

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.

+      return false;
+    }
+
+    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;
+  }
+}
+
+/// Traverses a deleted CPS term, marking existing tasks associated with a node
+/// within the term as deleted (which causes them to be skipped lazily when
+/// popped from the worklist), and adding newly created redexes to the worklist.
+class _RemovalRedexVisitor extends _RedexVisitor {
+  _RemovalRedexVisitor(Set<_ReductionTask> worklist) : super(worklist);
+
+  void processLetPrim(LetPrim node) {
+    node.parent = ShrinkingReducer._DELETED;
+  }
+
+  void processLetCont(LetCont node) {
+    node.parent = ShrinkingReducer._DELETED;
+  }
+
+  void processReference(Reference reference) {
+    reference.unlink();
+
+    // Convert recursive to nonrecursive continuations.
+    if (reference.definition is Continuation) {
+      Continuation cont = reference.definition;
+      if (cont.isRecursive && cont.hasAtMostOneUse) {
+        // 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;
+      }
+    }
+    super.processReference(reference); // Scan for new dead-* redexes.
+  }
+}
+
+/// Traverses the CPS term and sets node.parent for each visited node.
+class _ParentVisitor extends RecursiveVisitor {
+
+  void setParent(Node parent, Node child) {

[Kevin Millikin (Google), 2014/08/11 08:59:02]

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:58]

Done, inlined both methods.

+    child.parent = parent;
+  }
+
+  void setRefParent(Node parent, Reference child) {
+    child.parent = parent;
+  }
+
+  processFunctionDefinition(FunctionDefinition node) {
+    setParent(node, node.body);
+    node.parameters.forEach((Parameter p) => setParent(node, p));
+  }
+
+  // Expressions.
+
+  processLetPrim(LetPrim node) {
+    setParent(node, node.primitive);
+    setParent(node, node.body);
+  }
+
+  processLetCont(LetCont node) {
+    setParent(node, node.continuation);
+    setParent(node, node.body);
+  }
+
+  processInvokeStatic(InvokeStatic node) {
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processInvokeContinuation(InvokeContinuation node) {
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processInvokeMethod(InvokeMethod node) {
+    setRefParent(node, node.receiver);
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processInvokeSuperMethod(InvokeSuperMethod node) {
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processInvokeConstructor(InvokeConstructor node) {
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processConcatenateStrings(ConcatenateStrings node) {
+    setRefParent(node, node.continuation);
+    node.arguments.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processBranch(Branch node) {
+    setParent(node, node.condition);
+    setRefParent(node, node.trueContinuation);
+    setRefParent(node, node.falseContinuation);
+  }
+
+  processTypeOperator(TypeOperator node) {
+    setRefParent(node, node.continuation);
+    setRefParent(node, node.receiver);
+  }
+
+  processSetClosureVariable(SetClosureVariable node) {
+    setParent(node, node.body);
+    setRefParent(node, node.value);
+  }
+
+  processDeclareFunction(DeclareFunction node) {
+    setParent(node, node.definition);
+    setParent(node, node.body);
+  }
+
+  // Definitions.
+
+  processLiteralList(LiteralList node) {
+    node.values.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processLiteralMap(LiteralMap node) {
+    node.values.forEach((Reference ref) => setRefParent(node, ref));
+    node.keys.forEach((Reference ref) => setRefParent(node, ref));
+  }
+
+  processCreateFunction(CreateFunction node) {
+    setParent(node, node.definition);
+  }
+
+  processContinuation(Continuation node) {
+    setParent(node, node.body);
+    node.parameters.forEach((Parameter param) => setParent(node, param));
+  }
+
+  // Conditions.
+
+  processIsTrue(IsTrue node) {
+    setRefParent(node, node.value);
+  }
+}
+
+class _ReductionKind {
+  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);
+
+  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;
+  }
+
+  _ReductionTask(this.kind, this.node) {
+    // If new node types are added, they must be marked as deleted in
+    // [[_RemovalRedexVisitor]].
+    assert(node is LetCont || node is LetPrim);
+  }
+
+  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;
+}