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

// Copyright (c) 2015, 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.

library dart2js.cps_ir.let_sinking;

import 'cps_ir_nodes.dart';
import 'optimizers.dart';

/// Sinks single-use primitives to the use when this is safe and profitable.
///
/// To avoid sinking non-constant primitives into loops, this pass performs a
/// control-flow analysis to determine the effective nesting of loops.
///
/// In the example below, the value 'p' can be sunk to its use site in the
/// 'else' branch because that branch is not effectively part of a loop,
/// despite being lexically nested in a recursive continuation.
///
///   let prim p = getInterceptor(<something>)
///   let rec kont x =
///     if (<loop condition>)
///       <loop body>
///       InvokeContinuation kont x'
///     else
///       <after loop>
///       return p.foo()
///
class LetSinker extends RecursiveVisitor implements Pass {
  String get passName => 'Let sinking';

  LoopHierarchy loopHierarchy;
  List<Continuation> stack = <Continuation>[];

  /// Maps a sinkable primitive to its loop header.
  Map<Primitive, Continuation> loopHeaderForPrimitive =
      <Primitive, Continuation>{};

  Continuation currentLoopHeader;

  void rewrite(FunctionDefinition node) {
    new ParentVisitor().visit(node);
    loopHierarchy = new LoopHierarchy(node);
    visit(node.body);
  }

  @override
  Expression traverseLetPrim(LetPrim node) {
    Primitive prim = node.primitive;
    if (prim.hasExactlyOneUse && prim.isSafeForReordering) {
      // This can potentially be sunk. Register the loop header, so when we
      // find the use site, we can check if they are in the same loop.
      loopHeaderForPrimitive[prim] = currentLoopHeader;
      pushAction(() {
        if (node.primitive != null) {
          // The primitive could not be sunk. Try to sink dependencies here.
          visit(node.primitive);
        } else {
          // The primitive was sunk. Destroy the old LetPrim.
          InteriorNode parent = node.parent;
          parent.body = node.body;
          node.body.parent = parent;
        }
      });
    } else {
      visit(node.primitive);
    }

    // Visit the body, wherein this primitive may be sunk to its use site.
    return node.body;
  }

  @override
  Expression traverseContinuation(Continuation cont) {
    Continuation oldLoopHeader = currentLoopHeader;
    pushAction(() {
      currentLoopHeader = oldLoopHeader;
    });
    currentLoopHeader = loopHierarchy.getLoopHeader(cont);
    return cont.body;
  }

  void processReference(Reference ref) {
    Definition definition = ref.definition;
    if (definition is Primitive && 
        definition is! Parameter &&
        definition.hasExactlyOneUse &&
        definition.isSafeForReordering) {
      // Check if use is in the same loop.
      Continuation bindingLoop = loopHeaderForPrimitive.remove(definition);
      if (bindingLoop == currentLoopHeader || definition is Constant) {
        // Sink the definition.

        Expression use = getEnclosingExpression(ref.parent);
        LetPrim binding = definition.parent;
        binding.primitive = null;  // Mark old binding for deletion.
        LetPrim newBinding = new LetPrim(definition);
        definition.parent = newBinding;
        InteriorNode useParent = use.parent;
        useParent.body = newBinding;
        newBinding.body = use;
        use.parent = newBinding;
        newBinding.parent = useParent;

        // Now that the final binding location has been found, sink the
        // dependencies of the definition down here as well.
        visit(definition); 
      }
    }
  }

  Expression getEnclosingExpression(Node node) {
    while (node is! Expression) {
      node = node.parent;
    }
    return node;
  }
}

/// Determines the effective nesting of loops.
/// 
/// The effective nesting of loops is different from the lexical nesting, since
/// recursive continuations can generally contain all the code following 
/// after the loop in addition to the looping code itself.
/// 
/// For example, the 'else' branch below is not effectively part of the loop:
/// 
///   let rec kont x = 
///     if (<loop condition>) 
///       <loop body>
///       InvokeContinuation kont x'
///     else 
///       <after loop>
///       return p.foo()
/// 
/// We use the term "loop" to mean recursive continuation.
/// The `null` value is used to represent a context not part of any loop.
class LoopHierarchy {
  /// Nesting depth of the given loop.
  Map<Continuation, int> loopDepth = <Continuation, int>{};

  /// The innermost loop (other than itself) that may be invoked recursively
  /// as a result of invoking the given continuation.
  Map<Continuation, Continuation> loopTarget = <Continuation, Continuation>{};

  /// Current nesting depth.
  int currentDepth = 0;

  /// Computes the loop hierarchy for the given function.
  /// 
  /// Parent pointers must be computed for [node].
  LoopHierarchy(FunctionDefinition node) {
    _processBlock(node.body, null);
  }

  /// Returns the innermost loop which [cont] is effectively part of.
  Continuation getLoopHeader(Continuation cont) {
    return cont.isRecursive ? cont : loopTarget[cont];
  }

  /// Marks the innermost loop as a subloop of the other loop.
  /// 
  /// Returns the innermost loop.
  /// 
  /// Both continuations, [c1] and [c2] may be null (i.e. no loop).
  /// 
  /// A loop is said to be a subloop of an enclosing loop if it can invoke
  /// that loop recursively. This information is stored in [loopTarget].
  /// 
  /// This method is only invoked with two distinct loops if there is a
  /// point that can reach a recursive invocation of both loops.
  /// This implies that one loop is nested in the other, because they must
  /// both be in scope at that point.
  Continuation _markInnerLoop(Continuation c1, Continuation c2) {
    assert(c1 == null || c1.isRecursive);
    assert(c2 == null || c2.isRecursive);
    if (c1 == null) return c2;
    if (c2 == null) return c1;
    if (c1 == c2) return c1;
    if (loopDepth[c1] > loopDepth[c2]) {
      loopTarget[c1] = _markInnerLoop(loopTarget[c1], c2);
      return c1;
    } else {
      loopTarget[c2] = _markInnerLoop(loopTarget[c2], c1);
      return c2;
    }
  }

  /// Analyzes the body of [cont] and returns the innermost loop
  /// that can be invoked recursively from [cont] (other than [cont] itself).
  /// 
  /// [catchLoop] is the innermost loop that can be invoked recursively
  /// from the current exception handler.
  Continuation _processContinuation(Continuation cont, Continuation catchLoop) {
    if (cont.isRecursive) {
      ++currentDepth;
      loopDepth[cont] = currentDepth;
      Continuation target = _processBlock(cont.body, catchLoop);
      _markInnerLoop(loopTarget[cont], target);
      --currentDepth;
    } else {
      loopTarget[cont] = _processBlock(cont.body, catchLoop);
    }
    return loopTarget[cont];
  }

  bool _isCallContinuation(Continuation cont) {
    return cont.hasExactlyOneUse && cont.firstRef.parent is CallExpression;
  }

  /// Analyzes a basic block and returns the innermost loop that
  /// can be invoked recursively from that block.
  Continuation _processBlock(Expression node, Continuation catchLoop) {
    List<Continuation> callContinuations = <Continuation>[];
    for (; node is! TailExpression; node = node.next) {
      if (node is LetCont) {
        for (Continuation cont in node.continuations) {
          if (!_isCallContinuation(cont)) {
            // Process non-call continuations at the binding site, so they
            // their loop target is known at all use sites.
            _processContinuation(cont, catchLoop);
          } else {
            // To avoid deep recursion, do not analyze call continuations
            // recursively. This basic block traversal steps into the
            // call contiunation after visiting its use site. We store the
            // continuations in a list so we can set the loop target once
            // it is known.
            callContinuations.add(cont);
          }
        }
      } else if (node is LetHandler) {
        catchLoop = _processContinuation(node.handler, catchLoop);
      }
    }
    Continuation target;
    if (node is InvokeContinuation) {
      if (node.isRecursive) {
        target = node.continuation.definition;
      } else {
        target = loopTarget[node.continuation.definition];
      }
    } else if (node is Branch) {
      target = _markInnerLoop(
          loopTarget[node.trueContinuation.definition],
          loopTarget[node.falseContinuation.definition]);
    } else {
      assert(node is Unreachable || node is Throw);
    }
    target = _markInnerLoop(target, catchLoop);
    for (Continuation cont in callContinuations) {
      // Store the loop target on each call continuation in the basic block.
      // Because we walk over call continuations as part of the basic block
      // traversal, these do not get their loop target set otherwise.
      loopTarget[cont] = target;
    }
    return target;
  }
}