dart2js cps: Hoist loop-invariant branches from loop entry.

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

+library dart2js.cps_ir.loop_invariant_branch;
+
+import 'cps_ir_nodes.dart';
+import 'optimizers.dart';
+import 'loop_hierarchy.dart';
+import 'cps_fragment.dart';
+import 'redundant_join.dart' show AlphaRenamer;
+
+/// Hoists branches out of loops, where:
+/// - the branch is at the entry point of a loop
+/// - the branch condition is loop-invariant
+/// - one arm of the branch is not effectively part of the loop
+///
+/// Schematically:
+///
+///     b = COND
+///     while (true) {
+///       if (b)
+///         BRANCH (contains no continue to loop)
+///       else
+///         LOOP
+///     }
+///
+///     ==>
+///
+///     b = COND
+///     if (b)
+///       BRANCH
+///     else
+///       while (true)
+///         LOOP
+///
+/// As in [RedundantJoinEliminator], parameters are treated as names with
+/// lexical scoping during this pass, and a given parameter "name" may be
+/// declared by more than one continuation. The reference chains for parameters
+/// are therefore meaningless during this pass, until repaired by [AlphaRenamer]
+/// at the end.
+class LoopInvariantBranchMotion extends BlockVisitor implements Pass {
+  String get passName => 'Loop invariant branch motion';
+
+  LoopHierarchy loopHierarchy;
+  final Map<Primitive, Continuation> loopHeaderFor =
+      <Primitive, Continuation>{};
+  final Map<Continuation, Continuation> catchLoopFor =
+      <Continuation, Continuation>{};
+  Continuation currentLoopHeader;
+  Continuation currentCatchLoop;
+  List<Continuation> loops = <Continuation>[];
+  bool wasHoisted = false;
+
+  void rewrite(FunctionDefinition node) {
+    loopHierarchy = new LoopHierarchy(node);
+    BlockVisitor.traverseInPreOrder(node, this);
+    // Process loops bottom-up so a branch can be hoisted multiple times.
+    loops.reversed.forEach(hoistEntryCheck);
+    if (wasHoisted) {
+      new AlphaRenamer().visit(node);
+    }
+  }
+
+  void visitLetHandler(LetHandler node) {
+    currentCatchLoop = loopHierarchy.getLoopHeader(node.handler);
+  }
+
+  void visitContinuation(Continuation node) {
+    currentLoopHeader = loopHierarchy.getLoopHeader(node);
+    for (Parameter param in node.parameters) {
+      loopHeaderFor[param] = currentLoopHeader;
+    }
+    catchLoopFor[node] = currentCatchLoop;
+    if (node.isRecursive) {
+      loops.add(node);
+    }
+  }
+
+  void visitLetPrim(LetPrim node) {
+    loopHeaderFor[node.primitive] = currentLoopHeader;
+  }
+
+  void hoistEntryCheck(Continuation loop) {
+    // Keep hoisting branches out of the loop, there can be more than one.
+    while (tryHoistEntryCheck(loop));
+  }
+
+  Expression getEffectiveBody(Expression exp) {
+    // TODO(asgerf): We could also bypass constants here but constant pooling
+    //               is likely to be a better solution for that.
+    while (exp is LetCont) {
+      exp = exp.next;
+    }
+    return exp;
+  }
+
+  /// Adds [parameters] to [cont] and updates every invocation to pass the
+  /// corresponding parameter values as arguments. Thus, the parameters are
+  /// passed in explicitly instead of being captured.
+  ///
+  /// This only works because [AlphaRenamer] cleans up after this pass.

[sra1, 2016/01/09 01:07:14]

'after this pass' -> 'at the end of this pass'.

[asgerf, 2016/01/11 19:07:07]

Sorry, I thought I fixed this. I'll put up another CL for it.

+  ///
+  /// Schematically:
+  ///
+  ///     let outer(x1, x2, x3) =
+  ///       let inner(y) = BODY
+  ///       [ .. inner(y') .. ]
+  ///
+  ///   ==> (append parameters)
+  ///
+  ///     let outer(x1, x2, x3) =
+  ///       let inner(y, x1, x2, x3) = BODY
+  ///       [ .. inner(y', x1, x2, x3) .. ]
+  ///
+  ///   ==> (hoist, not performed by this method)
+  ///
+  ///     let inner(y, x1, x2, x3) = BODY
+  ///     let outer(x1, x2, x3) =
+  ///       [ .. inner(y', x1, x2, x3) .. ]
+  ///
+  void appendParameters(Continuation cont, List<Parameter> parameters) {
+    cont.parameters.addAll(parameters);
+    for (Reference ref = cont.firstRef; ref != null; ref = ref.next) {
+      Node use = ref.parent;
+      if (use is InvokeContinuation) {
+        for (Parameter loopParam in parameters) {
+          use.arguments.add(new Reference<Primitive>(loopParam)..parent = use);
+        }
+      }
+    }
+  }
+
+  bool tryHoistEntryCheck(Continuation loop) {
+    // Check if this is a loop starting with a branch.

[sra1, 2016/01/09 01:07:14]

It would be nice if there was a quick way to test this before computing
loopHierarchy.

[asgerf, 2016/01/11 19:07:07]

Acknowledged.

+    Expression body = getEffectiveBody(loop.body);
+    if (body is! Branch) return false;
+    Branch branch = body;
+
+    // Is the condition loop invariant?
+    Primitive condition = branch.condition.definition;
+    if (loopHeaderFor[condition] == loop) return false;
+
+    Continuation trueCont = branch.trueContinuation.definition;
+    Continuation falseCont = branch.falseContinuation.definition;
+    Continuation hoistedCase; // The branch to hoist.
+    Continuation loopCase; // The branch that is part of the loop.
+
+    // Check that one branch is part of the loop, and the other is an exit.
+    if (loopHierarchy.getLoopHeader(trueCont) != loop &&
+        loopHierarchy.getLoopHeader(falseCont) == loop) {
+      hoistedCase = trueCont;
+      loopCase = falseCont;
+    } else if (loopHierarchy.getLoopHeader(falseCont) != loop &&
+               loopHierarchy.getLoopHeader(trueCont) == loop) {
+      hoistedCase = falseCont;
+      loopCase = trueCont;
+    } else {
+      return false;
+    }
+
+    // Hoist non-loop continuations out of the loop.
+    // The hoisted branch can reference other continuations bound in the loop,
+    // so to stay in scope, those need to be hoisted as well.
+    //
+    //     let b = COND
+    //     let loop(x) =
+    //       let join(y) = JOIN
+    //       let hoistCase() = HOIST
+    //       let loopCase() = LOOP
+    //       branch b hoistCase loopCase
+    //     in loop(i)
+    //
+    //    ==>
+    //
+    //     let b = COND
+    //     let join(y,x) = JOIN
+    //     let hoistCase(x) = HOIST
+    //     let loop(x) =
+    //       let loopCase() = LOOP
+    //       branch b hoistCase loopCase
+    //     in loop(i)
+    //
+    LetCont loopBinding = loop.parent;
+    Expression it = loop.body;
+    while (it is LetCont) {
+      LetCont let = it;
+      it = let.body;
+      for (Continuation cont in let.continuations) {
+        if (loopHierarchy.getEnclosingLoop(cont) != loop) {
+          appendParameters(cont, loop.parameters);
+          new LetCont(cont, null).insertAbove(loopBinding);
+        }
+      }
+      let.continuations.removeWhere((cont) => cont.parent != let);
+      if (let.continuations.isEmpty) {
+        let.remove();
+      }
+    }
+
+    // Create a new branch to call the hoisted continuation or the loop:
+    //
+    //     let loop(x) =
+    //       let loopCase() = LOOP
+    //       branch b hoistCase loopCase
+    //     in loop(i)
+    //
+    //    ==>
+    //
+    //     let newTrue() = hoistCase(i)
+    //     let newFalse() =
+    //       let loop(x) =
+    //         let loopCase() = LOOP
+    //         branch b hoistCase loopCase
+    //     branch b newTrue newFalse
+    //
+    InvokeContinuation loopEntry = loopBinding.body;
+    List<Primitive> loopArgs =
+        loopEntry.arguments.map((ref) => ref.definition).toList();
+    CpsFragment cps = new CpsFragment();
+    cps.branch(condition,
+          strict: branch.isStrictCheck,
+          negate: hoistedCase == falseCont)
+       .invokeContinuation(hoistedCase, loopArgs);
+
+    // The continuations created in the fragment need to have their loop header
+    // set so the loop hierarchy remains intact
+    loopHierarchy.update(cps,
+        exitLoop: loopHierarchy.getEnclosingLoop(loop),
+        catchLoop: catchLoopFor[loop]);
+
+    // Insert above the loop. This will put the loop itself in a branch.
+    cps.insertAbove(loopBinding);
+
+    // Replace the old branch with the loopCase, still bound inside the loop:
+    //
+    //   let loop(x) =
+    //     let loopCase() = LOOP
+    //     branch b hoistCase loopCase
+    //   in loop(i)
+    //
+    //  ==>
+    //
+    //   let loop(x) =
+    //     let loopCase() = LOOP
+    //     loopCase()
+    //   in loop(i)
+    //
+    destroyAndReplace(branch, new InvokeContinuation(loopCase, []));
+
+    // Record that at least one branch was hoisted to trigger alpha renaming.
+    wasHoisted = true;
+
+    return true;
+  }
+}