dart2js cps: Share interceptors by default and propagate to use later.

pkg/compiler/lib/src/cps_ir/letsinking.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, see
+/// [LoopHierarchy].

[floitsch, 2015/07/17 17:19:45]

I think it's always nice to have an example. (doesn't matter in which language:
pure Dart, CPS nodes, pseudo, ...)

[asgerf, 2015/07/20 09:10:56]

Added an example based on the one from LoopHierarchy.

+class LetSinker extends RecursiveVisitor implements Pass {
+  String get passName => 'Let sinking';
+
+  LoopHierarchy loopHierarchy;
+  List<Continuation> stack = <Continuation>[];
+  Set<LetPrim> sunkNodes = new Set<LetPrim>();
+
+  void rewrite(FunctionDefinition node) {
+    new ParentVisitor().visit(node);
+    loopHierarchy = new LoopHierarchy(node);

[floitsch, 2015/07/17 17:19:45]

I'm ok this way, but have a *slight* preference to calling a function to do
work.
That is: new LoopHierarchy(node)..compute()

[asgerf, 2015/07/20 09:10:56]

Acknowledged.

I usually do that if the class is called SomethingVisitor or SomethingBuilder or
in general Something<Verb>.

+    visit(node.body);
+  }
+
+  void visitLetPrim(LetPrim node) {
+    // Visit the body, wherein this primitive may be sunk to its use site.
+    visit(node.body);
+
+    if (node.primitive != null) {
+      // The primitive could not be sunk. Sink dependencies to this location.
+      visit(node.primitive);
+    } else {
+      // The primitive was sunk. Destroy the old LetPrim.
+      InteriorNode parent = node.parent;
+      parent.body = node.body;
+      node.body.parent = parent;
+    }
+  }
+
+  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.
+      LetPrim binding = definition.parent;
+      Continuation bindingLoop = loopHierarchy.getLoopHeader(binding);
+      Expression use = getEnclosingExpression(ref.parent);
+      Continuation useLoop = loopHierarchy.getLoopHeader(use);
+      if (bindingLoop == useLoop || definition is Constant) {
+        // Sink the definition.
+
+        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 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 [node] is effectively part of.
+  Continuation getLoopHeader(Expression exp) {
+    Node node = exp.parent;
+    while (node != null && node is! Continuation) {
+      node = node.parent;
+    }
+    if (node is Continuation) {
+      if (node.isRecursive) 

[floitsch, 2015/07/17 17:19:45]

multi-line ifs should have {}

[asgerf, 2015/07/20 09:10:56]

Done.

+        return node;
+      else
+        return loopTarget[node];
+    }
+    return null;
+  }
+
+  /// Returns the innermost of two loops and marks its as being 
+  /// a subloop in the other 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 _determineInnerLoop(Continuation c1, Continuation c2) {

[floitsch, 2015/07/17 17:19:45]

The main-goal of this function is to mark nesting, and not the determining of
which one is nested. (that could be done by a simple loopDepth check).
I would turn it around:

/// 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 ...
Contination markNestedLoop(.... {
...
}

note: in general I try to reference the arguments in the description, so that a
good editor could highlight the corresponding dart-doc section when I write a
call to the function.

[asgerf, 2015/07/20 09:10:56]

Done.

+    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] = _determineInnerLoop(loopTarget[c1], c2);
+      return c1;
+    } else {
+      loopTarget[c2] = _determineInnerLoop(loopTarget[c2], c1);
+      return c2;
+    }
+  }
+
+  /// Analyzes the body of [cont] and returns the innermost loop
+  /// that can be invoked recursively can be invoked from [cont]

[floitsch, 2015/07/17 17:19:45]

-can be invoked-

[asgerf, 2015/07/20 09:10:56]

Done.

+  /// (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);
+      _determineInnerLoop(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) {
+          // Do not process call continuations at the binding site.
+          // We step into call continuations as part of the same basic block.

[floitsch, 2015/07/17 17:19:45]

I don't understand this comment.

[asgerf, 2015/07/20 09:10:56]

Refactored code and comment.

The "is CallExpression" branch has been merged with "is LetCont".

+          if (!_isCallContinuation(cont)) {
+            _processContinuation(cont, catchLoop);
+          }
+        }
+      } else if (node is CallExpression) {
+        callContinuations.add(node.continuation.definition);
+      } 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 = _determineInnerLoop(
+          loopTarget[node.trueContinuation.definition],
+          loopTarget[node.falseContinuation.definition]);
+    } else {
+      assert(node is Unreachable || node is Throw);
+    }
+    target = _determineInnerLoop(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 by otherwise.

[floitsch, 2015/07/17 17:19:45]

-by-

[asgerf, 2015/07/20 09:10:56]

Done.

+      loopTarget[cont] = target;
+    }
+    return target;
+  }
+}