dart2js cps: Rewrite mutable variables to continuation parameters.

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

Index: pkg/compiler/lib/src/cps_ir/mutable_ssa.dart
diff --git a/pkg/compiler/lib/src/cps_ir/mutable_ssa.dart b/pkg/compiler/lib/src/cps_ir/mutable_ssa.dart
new file mode 100644
index 0000000000000000000000000000000000000000..daf19e18df80de34d03dd4518397b53661307846
--- /dev/null
+++ b/pkg/compiler/lib/src/cps_ir/mutable_ssa.dart
@@ -0,0 +1,255 @@
+// 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.mutable_ssa;
+
+import 'cps_ir_nodes.dart';
+import 'optimizers.dart';
+
+/// Determines which mutable variables should be rewritten to phi assignments
+/// in this pass.
+///
+/// We do not rewrite variables that have an assignment inside a try block that
+/// does not contain its declaration.
+class MutableVariablePreanalysis extends RecursiveVisitor {
+  // Number of try blocks enclosing the current position.
+  int currentDepth = 0;
+
+  /// Number of try blocks enclosing the declaration of a given mutable
+  /// variable.
+  ///
+  /// All mutable variables seen will be present in the map after the analysis.
+  Map<MutableVariable, int> variableDepth = <MutableVariable, int>{};
+
+  /// Variables with an assignment inside a try block that does not contain
+  /// its declaration.
+  Set<MutableVariable> hasAssignmentInTry = new Set<MutableVariable>();
+
+  void visitLetHandler(LetHandler node) {
+    ++currentDepth;
+    visit(node.body);
+    --currentDepth;
+    visit(node.handler);
+  }
+
+  void processLetMutable(LetMutable node) {
+    variableDepth[node.variable] = currentDepth;
+  }
+
+  void processSetMutableVariable(SetMutableVariable node) {
+    MutableVariable variable = node.variable.definition;
+    if (currentDepth > variableDepth[variable]) {
+      hasAssignmentInTry.add(variable);
+    }
+  }
+
+  /// True if there are no mutable variables or they are all assigned inside
+  /// a try block. In this case, there is nothing to do and the pass should
+  /// be skipped.
+  bool get allMutablesAreAssignedInTryBlocks {
+    return hasAssignmentInTry.length == variableDepth.length;
+  }
+}
+
+/// Replaces mutable variables with continuation parameters, effectively
+/// bringing them into SSA form.
+///
+/// This pass is intended to clean up mutable variables that were introduced
+/// by an optimization in the type propagation pass.
+///
+/// This implementation potentially creates a lot of redundant and dead phi
+/// parameters. These will be cleaned up by redundant phi elimination and
+/// shrinking reductions.
+///
+/// Discussion:
+/// For methods with a lot of mutable variables, creating all the spurious
+/// parameters might be too expensive. If this is the case, we should
+/// improve this pass to avoid most spurious parameters in practice.
+class MutableVariableEliminator implements Pass {
+  String get passName => 'Mutable variable elimination';
+
+  /// Mutable variables currently in scope, in order of declaration.
+  /// This list determines the order of the corresponding phi parameters.
+  final List<MutableVariable> mutableVariables = <MutableVariable>[];
+
+  /// Number of phi parameters added to the given continuation.
+  final Map<Continuation, int> continuationPhiCount = <Continuation, int>{};
+
+  /// Stack of yet unprocessed continuations interleaved with the
+  /// mutable variables currently in scope.
+  ///
+  /// Continuations are processed when taken off the stack and mutable
+  /// variables fall out of scope (i.e. removed from [mutableVariables]) when
+  /// taken off the stack.
+  final List<StackItem> stack = <StackItem>[];
+
+  MutableVariablePreanalysis analysis;
+
+  void rewrite(FunctionDefinition node) {
+    analysis = new MutableVariablePreanalysis()..visit(node);
+    if (analysis.allMutablesAreAssignedInTryBlocks) {
+      // Skip the pass if there is nothing to do.
+      return;
+    }
+    processBlock(node.body, <MutableVariable, Primitive>{});
+    while (stack.isNotEmpty) {
+      StackItem item = stack.removeLast();
+      if (item is ContinuationItem) {
+        processBlock(item.continuation.body, item.environment);
+      } else {
+        assert(item is VariableItem);
+        mutableVariables.removeLast();
+      }
+    }
+  }
+
+  bool shouldRewrite(MutableVariable variable) {
+    return !analysis.hasAssignmentInTry.contains(variable);
+  }
+
+  bool isJoinContinuation(Continuation cont) {
+    return !cont.hasExactlyOneUse ||
+           cont.firstRef.parent is InvokeContinuation;
+  }
+
+  void removeNode(InteriorNode node) {
+    InteriorNode parent = node.parent;
+    parent.body = node.body;
+    node.body.parent = parent;
+  }
+
+  /// If some useful source information is attached to exactly one of the
+  /// two definitions, the information is copied onto the other.
+  void merge(MutableVariable variable, Primitive value) {

[karlklose, 2015/07/14 08:39:44]

Maybe call this 'mergeHints.'

[asgerf, 2015/07/14 09:00:22]

Done.

+    if (variable.hint == null) {
+      variable.hint = value.hint;
+    } else if (value.hint == null) {
+      value.hint = variable.hint;
+    }
+  }
+
+  /// Processes a basic block, replacing mutable variable uses with direct
+  /// references to their values.
+  ///
+  /// [environment] is the current value of each mutable variable. The map
+  /// will be mutated during the processing.
+  ///
+  /// Continuations to be processed are put on the stack for later processing.
+  void processBlock(Expression node,
+                    Map<MutableVariable, Primitive> environment) {
+    while (node is! TailExpression) {

[karlklose, 2015/07/14 08:39:44]

Consider using a for-loop instead to make the traversal step easier to spot.

[asgerf, 2015/07/14 09:00:22]

Nice idea! Done.

+      if (node is LetMutable && shouldRewrite(node.variable)) {
+        // Put the new mutable variable on the stack while processing the body.

[karlklose, 2015/07/14 08:39:44]

Merge comment with comment below.

[asgerf, 2015/07/14 09:00:22]

Done.

+        mutableVariables.add(node.variable);
+
+        // Pop it off again when done with the body.
+        stack.add(new VariableItem());
+
+        // Put the initial value into the environment.
+        Primitive value = node.value.definition;
+        environment[node.variable] = value;
+
+        // Preserve variable names.
+        merge(node.variable, value);
+
+        // Remove the mutable variable binding.
+        node.value.unlink();
+        removeNode(node);
+      } else if (node is SetMutableVariable &&
+                 shouldRewrite(node.variable.definition)) {
+        // As above, update the environment, preserve variables and remove
+        // the mutable variable assignment.
+        MutableVariable variable = node.variable.definition;
+        environment[variable] = node.value.definition;
+        merge(variable, node.value.definition);
+        node.value.unlink();
+        removeNode(node);
+      } else if (node is LetPrim && node.primitive is GetMutableVariable) {
+        GetMutableVariable getter = node.primitive;
+        MutableVariable variable = getter.variable.definition;
+        if (shouldRewrite(variable)) {
+          // Replace with the reaching definition from the environment.
+          Primitive value = environment[variable];
+          value.substituteFor(getter);
+          merge(variable, value);
+          removeNode(node);
+        }
+      } else if (node is LetCont) {
+        // Create phi parameters for each join continuation bound here, and put
+        // them on the stack for later processing.
+        // Note that non-join continuations are handled at the use-site.
+        for (Continuation cont in node.continuations) {
+          if (!isJoinContinuation(cont)) continue;
+          // Create a phi parameter for every mutable variable in scope.
+          // At the same time, build the environment to use for processing
+          // the continuation (mapping mutables to phi parameters).
+          continuationPhiCount[cont] = mutableVariables.length;
+          Map<MutableVariable, Primitive> environment =
+              <MutableVariable, Primitive>{};
+          for (MutableVariable variable in mutableVariables) {
+            Parameter phi = new Parameter(variable.hint);
+            cont.parameters.add(phi);
+            phi.parent = cont;
+            environment[variable] = phi;
+          }
+          stack.add(new ContinuationItem(cont, environment));
+        }
+      } else if (node is LetHandler) {
+        // Process the catch block later and continue into the try block.
+        // We can use the same environment object for the try and catch blocks.
+        // The current environment bindings cannot change inside the try block
+        // because we exclude all variables assigned inside a try block.
+        // The environment might be extended with more bindings before we
+        // analyze the catch block, but that's ok.
+        stack.add(new ContinuationItem(node.handler, environment));
+      }
+
+      node = node.next;
+    }
+
+    // Analyze the terminal node.
+    if (node is InvokeContinuation) {
+      Continuation cont = node.continuation.definition;
+      if (cont.isReturnContinuation) return;
+      // This is a call to a join continuation. Add arguments for the phi
+      // parameters that were added to this continuation.
+      int phiCount = continuationPhiCount[cont];
+      for (int i = 0; i < phiCount; ++i) {
+        Primitive value = environment[mutableVariables[i]];
+        Reference<Primitive> arg = new Reference<Primitive>(value);
+        node.arguments.add(arg);
+        arg.parent = node;
+      }
+    } else if (node is Branch) {
+      // Enqueue both branches with the current environment.
+      // Clone the environments once so the processing of one branch does not
+      // mutate the environment needed to process the other branch.
+      stack.add(new ContinuationItem(
+          node.trueContinuation.definition,
+          new Map<MutableVariable, Primitive>.from(environment)));
+      stack.add(new ContinuationItem(
+          node.falseContinuation.definition,
+          environment));
+    } else {
+      assert(node is Throw || node is Unreachable);
+    }
+  }
+}
+
+abstract class StackItem {}
+
+/// Represents a mutable variable that is in scope.
+///
+/// The top-level mutable variable falls out of scope when this item is
+/// taken off the stack.
+class VariableItem extends StackItem {}
+
+/// Represents a yet unprocessed continuation together with the
+/// environment in which to process it.
+class ContinuationItem extends StackItem {
+  final Continuation continuation;
+  final Map<MutableVariable, Primitive> environment;
+
+  ContinuationItem(this.continuation, this.environment);
+}