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) {
    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 E -> E (x not free in E).
  void _reduceDeadVal(_ReductionTask task) {
    assert(_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 = E0 in E1 -> E1 (k not free in E1).
  void _reduceDeadCont(_ReductionTask task) {
    assert(_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 = E0 in E1[k y] -> E1[E0[y/x]] (k not free in E1).
  void _reduceBetaContLin(_ReductionTask task) {
    // Might have been mutated, recheck if reduction is still valid.
    // In the following example, the beta-cont-lin reduction of k0 could have
    // been invalidated by removal of the dead continuation k1:
    //
    //  letcont k0 x0 = E0 in
    //    letcont k1 x1 = k0 x1 in
    //      return x2
    if (!_isBetaContLin(task.node)) {
      return;
    }

    // Remove the continuation.
    LetCont letCont = task.node;
    Continuation cont = letCont.continuation;
    _removeNode(letCont);

    // Replace its invocation with the continuation body.
    InvokeContinuation invoke = cont.firstRef.parent;
    InteriorNode invokeParent = invoke.parent;

    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];
      argRef.definition.substituteFor(cont.parameters[i]);
    }

    // Perform bookkeeping on removed body and scan for new redexes.
    new _RemovalRedexVisitor(_worklist).visit(invoke);
  }

  /// Applies the eta-cont reduction:
  ///   letcont k x = j x in E -> E[j/k].
  /// If k is unused, degenerates to dead-cont.
  void _reduceEtaCont(_ReductionTask task) {
    // Might have been mutated, recheck if reduction is still valid.
    // In the following example, the eta-cont reduction of k1 could have been
    // invalidated by an earlier beta-cont-lin reduction of k0.
    //
    //  letcont k0 x0 = E0 in
    //    letcont k1 x1 = k0 x1 in E1
    if (!_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);
  }
}

/// Returns true iff the bound primitive is unused.
bool _isDeadVal(LetPrim node) => !node.primitive.hasAtLeastOneUse;

/// Returns true iff the bound continuation is unused.
bool _isDeadCont(LetCont node) => !node.continuation.hasAtLeastOneUse;

/// Returns true iff the bound continuation is used exactly once, and that
/// use is as the receiver of a continuation invocation.
bool _isBetaContLin(LetCont node) {
  Continuation cont = node.continuation;
  if (!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 bound continuation consists of a continuation
/// invocation, passing on all parameters. Special cases exist (see below).
bool _isEtaCont(LetCont node) {
  Continuation cont = node.continuation;
  if (!(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
  // 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.
  if (invoke.isRecursive) {
    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 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 (node.parent == ShrinkingReducer._DELETED) {
      return;
    } else if (_isDeadVal(node)) {
      worklist.add(new _ReductionTask(_ReductionKind.DEAD_VAL, node));
    }
  }

  void processLetCont(LetCont node) {
    if (node.parent == ShrinkingReducer._DELETED) {
      return;
    } else 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));
    }
  }
}

/// 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();

    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 cont = reference.definition;
      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;
      }
      Node parent = cont.parent;
      if (parent is LetCont && _isDeadCont(parent)) {
        worklist.add(new _ReductionTask(_ReductionKind.DEAD_CONT, parent));
      }
    }
  }
}

/// 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((Parameter p) => p.parent = node);
  }

  // Expressions.

  processLetPrim(LetPrim node) {
    node.primitive.parent = node;
    node.body.parent = node;
  }

  processLetCont(LetCont node) {
    node.continuation.parent = node;
    node.body.parent = node;
  }

  processInvokeStatic(InvokeStatic node) {
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processInvokeContinuation(InvokeContinuation node) {
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processInvokeMethod(InvokeMethod node) {
    node.receiver.parent = node;
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processInvokeSuperMethod(InvokeSuperMethod node) {
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processInvokeConstructor(InvokeConstructor node) {
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processConcatenateStrings(ConcatenateStrings node) {
    node.continuation.parent = node;
    node.arguments.forEach((Reference ref) => ref.parent = node);
  }

  processBranch(Branch node) {
    node.condition.parent = node;
    node.trueContinuation.parent = node;
    node.falseContinuation.parent = node;
  }

  processTypeOperator(TypeOperator node) {
    node.continuation.parent = node;
    node.receiver.parent = node;
  }

  processSetClosureVariable(SetClosureVariable node) {
    node.body.parent = node;
    node.value.parent = node;
  }

  processDeclareFunction(DeclareFunction node) {
    node.definition.parent = node;
    node.body.parent = node;
  }

  // Definitions.

  processLiteralList(LiteralList node) {
    node.values.forEach((Reference ref) => ref.parent = node);
  }

  processLiteralMap(LiteralMap node) {
    node.values.forEach((Reference ref) => ref.parent = node);
    node.keys.forEach((Reference ref) => ref.parent = node);
  }

  processCreateFunction(CreateFunction node) {
    node.definition.parent = node;
  }

  processContinuation(Continuation node) {
    node.body.parent = node;
    node.parameters.forEach((Parameter param) => param.parent = node);
  }

  // Conditions.

  processIsTrue(IsTrue node) {
    node.value.parent = node;
  }
}

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;
}