cps-ir: Merge variables based on set-based liveness and graph coloring.

pkg/compiler/lib/src/tree_ir/optimization/copy_propagator.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 tree_ir.optimization;
-
-/// Eliminates moving assignments, such as w := v, by assigning directly to w
-/// at the definition of v.
-///
-/// This compensates for suboptimal register allocation, and merges closure
-/// variables with local temporaries that were left behind when translating
-/// out of CPS (where closure variables live in a separate space).
-class CopyPropagator extends RecursiveVisitor with PassMixin {
-  String get passName => 'Copy propagation';
-
-  /// After visitStatement returns, [move] maps a variable v to an
-  /// assignment A of form w := v, under the following conditions:
-  /// - there are no reads or writes of w before A
-  /// - A is the only use of v
-  Map<Variable, Assign> move = <Variable, Assign>{};
-
-  /// Like [move], except w is the key instead of v.
-  Map<Variable, Assign> inverseMove = <Variable, Assign>{};
-
-  ExecutableElement currentElement;
-
-  /// Number of try blocks enclosing the currently visited node.
-  int enclosingTrys = 0;
-
-  void rewriteExecutableDefinition(ExecutableDefinition root) {
-    currentElement = root.element;
-    root.body = visitStatement(root.body);
-  }
-
-  rewriteFunctionDefinition(FunctionDefinition node) {
-    if (node.isAbstract) return;
-    rewriteExecutableDefinition(node);
-
-    // Try to propagate moving assignments into function parameters.
-    // For example:
-    // foo(x) {
-    //   var v1 = x;
-    //   BODY
-    // }
-    //   ==>
-    // foo(v1) {
-    //   BODY
-    // }
-
-    // Variables must not occur more than once in the parameter list, so
-    // invalidate all moving assignments that would propagate a parameter
-    // into another parameter. For example:
-    // foo(x,y) {
-    //   y = x;
-    //   BODY
-    // }
-    // Cannot declare function as foo(x,x)!
-    node.parameters.forEach(invalidateMovingAssignment);
-
-    // Now do the propagation.
-    for (int i = 0; i < node.parameters.length; i++) {
-      Variable param = node.parameters[i];
-      Variable replacement = copyPropagateVariable(param);
-      replacement.element = param.element; // Preserve parameter name.
-      node.parameters[i] = replacement;
-    }
-  }
-
-  rewriteConstructorDefinition(ConstructorDefinition node) {
-    if (node.isAbstract) return;
-    node.initializers.forEach(visitExpression);
-    rewriteExecutableDefinition(node);
-
-
-    // Try to propagate moving assignments into function parameters.
-    // For example:
-    // foo(x) {
-    //   var v1 = x;
-    //   BODY
-    // }
-    //   ==>
-    // foo(v1) {
-    //   BODY
-    // }
-
-    // Variables must not occur more than once in the parameter list, so
-    // invalidate all moving assignments that would propagate a parameter
-    // into another parameter. For example:
-    // foo(x,y) {
-    //   y = x;
-    //   BODY
-    // }
-    // Cannot declare function as foo(x,x)!
-    node.parameters.forEach(invalidateMovingAssignment);
-
-    // Now do the propagation.
-    for (int i = 0; i < node.parameters.length; i++) {
-      Variable param = node.parameters[i];
-      Variable replacement = copyPropagateVariable(param);
-      replacement.element = param.element; // Preserve parameter name.
-      node.parameters[i] = replacement;
-    }
-
-  }
-
-
-  Statement visitBasicBlock(Statement node) {
-    node = visitStatement(node);
-    move.clear();
-    inverseMove.clear();
-    return node;
-  }
-
-  /// Remove an assignment of form [w] := v from the move maps.
-  void invalidateMovingAssignment(Variable w) {
-    Assign movingAssignment = inverseMove.remove(w);
-    if (movingAssignment != null) {
-      VariableUse value = movingAssignment.value;
-      move.remove(value.variable);
-    }
-  }
-
-  visitVariableUse(VariableUse node) {
-    // We found a use of w; we can't propagate assignments across this use.
-    invalidateMovingAssignment(node.variable);
-  }
-
-  /**
-   * Called when a definition of [v] is encountered.
-   * Attempts to propagate the assignment through a moving assignment.
-   * Returns the variable to be assigned into, defaulting to [v] itself if
-   * no optimization could be performed.
-   */
-  Variable copyPropagateVariable(Variable v) {
-    Assign movingAssign = move[v];
-    if (movingAssign != null) {
-      // We found the pattern:
-      //   v := EXPR
-      //   BLOCK   (does not use w)
-      //   w := v  (only use of v)
-      //
-      // Rewrite to:
-      //   w := EXPR
-      //   BLOCK
-      //   w := w  (to be removed later)
-      Variable w = movingAssign.variable;
-
-      // Make w := w.
-      // We can't remove the statement from here because we don't have
-      // parent pointers. So just make it a no-op so it can be removed later.
-      movingAssign.value = new VariableUse(w);
-
-      // The intermediate variable 'v' should now be orphaned, so don't bother
-      // updating its read/write counters.
-
-      // Make w := EXPR
-      ++w.writeCount;
-      return w;
-    }
-    return v;
-  }
-
-  Statement visitAssign(Assign node) {
-    node.next = visitStatement(node.next);
-    node.variable = copyPropagateVariable(node.variable);
-
-    // If a moving assignment w := v exists later, and we assign to w here,
-    // the moving assignment is no longer a candidate for copy propagation.
-    invalidateMovingAssignment(node.variable);
-
-    visitExpression(node.value);
-
-    // If this is a moving assignment w := v, with this being the only use of v,
-    // try to propagate it backwards.
-    // Do not propagate assignments where w is captured or if where are inside a
-    // try block, because then we can't isolate the uses of w to a single block.
-    // We currently do not support propagation if the assignment is a
-    // declaration. To support this we would need to ensure that the target
-    // assignment is turned into a declaration as well.
-    if (node.value is VariableUse &&
-        !node.variable.isCaptured &&
-        enclosingTrys == 0 &&
-        !node.isDeclaration) {
-      VariableUse value = node.value;
-      if (value.variable.readCount == 1) {
-        move[value.variable] = node;
-        inverseMove[node.variable] = node;
-      }
-    }
-
-    return node;
-  }
-
-  Statement visitLabeledStatement(LabeledStatement node) {
-    node.next = visitBasicBlock(node.next);
-    node.body = visitStatement(node.body);
-    return node;
-  }
-
-  Statement visitReturn(Return node) {
-    visitExpression(node.value);
-    return node;
-  }
-
-  Statement visitBreak(Break node) {
-    return node;
-  }
-
-  Statement visitContinue(Continue node) {
-    return node;
-  }
-
-  Statement visitIf(If node) {
-    visitExpression(node.condition);
-    node.thenStatement = visitBasicBlock(node.thenStatement);
-    node.elseStatement = visitBasicBlock(node.elseStatement);
-    return node;
-  }
-
-  Statement visitWhileTrue(WhileTrue node) {
-    node.body = visitBasicBlock(node.body);
-    return node;
-  }
-
-  Statement visitWhileCondition(WhileCondition node) {
-    throw "WhileCondition before LoopRewriter";
-  }
-
-  Statement visitTry(Try node) {
-    enclosingTrys++;
-    node.tryBody = visitBasicBlock(node.tryBody);
-    enclosingTrys--;
-    node.catchBody = visitBasicBlock(node.catchBody);
-    return node;
-  }
-
-  Statement visitFunctionDeclaration(FunctionDeclaration node) {
-    // Unlike var declarations, function declarations are not hoisted, so we
-    // can't do copy propagation of the variable.
-    new CopyPropagator().rewrite(node.definition);
-    node.next = visitStatement(node.next);
-    return node;
-  }
-
-  Statement visitExpressionStatement(ExpressionStatement node) {
-    node.next = visitStatement(node.next);
-    visitExpression(node.expression);
-    return node;
-  }
-
-  Statement visitSetField(SetField node) {
-    node.next = visitStatement(node.next);
-    visitExpression(node.value);
-    visitExpression(node.object);
-    return node;
-  }
-
-  void visitFunctionExpression(FunctionExpression node) {
-    new CopyPropagator().rewrite(node.definition);
-  }
-
-  void visitFieldInitializer(FieldInitializer node) {
-    visitStatement(node.body);
-  }
-
-}