dart/pkg/compiler/lib/src/tree_ir/optimization/statement_rewriter.dart - external/dart - Git at Google

 // 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;

 /**
  * Performs the following transformations on the tree:
  * - Assignment propagation
  * - If-to-conditional conversion
  * - Flatten nested ifs
  * - Break inlining
  * - Redirect breaks
  *
  * The above transformations all eliminate statements from the tree, and may
  * introduce redexes of each other.
  *
  *
  * ASSIGNMENT PROPAGATION:
  * Single-use definitions are propagated to their use site when possible.
  * For example:
  *
  *   { v0 = foo(); return v0; }
  *     ==>
  *   return foo()
  *
  * After translating out of CPS, all intermediate values are bound by [Assign].
  * This transformation propagates such definitions to their uses when it is
  * safe and profitable.  Bindings are processed "on demand" when their uses are
  * seen, but are only processed once to keep this transformation linear in
  * the size of the tree.
  *
  * The transformation builds an environment containing [Assign] bindings that
  * are in scope.  These bindings have yet-untranslated definitions.  When a use
  * is encountered the transformation determines if it is safe and profitable
  * to propagate the definition to its use.  If so, it is removed from the
  * environment and the definition is recursively processed (in the
  * new environment at the use site) before being propagated.
  *
  * See [visitVariableUse] for the implementation of the heuristic for
  * propagating a definition.
  *
  *
  * IF-TO-CONDITIONAL CONVERSION:
  * If-statement are converted to conditional expressions when possible.
  * For example:
  *
  *   if (v0) { v1 = foo(); break L } else { v1 = bar(); break L }
  *     ==>
  *   { v1 = v0 ? foo() : bar(); break L }
  *
  * This can lead to inlining of L, which in turn can lead to further propagation
  * of the variable v1.
  *
  * See [visitIf].
  *
  *
  * FLATTEN NESTED IFS:
  * An if inside an if is converted to an if with a logical operator.
  * For example:
  *
  *   if (E1) { if (E2) {S} else break L } else break L
  *     ==>
  *   if (E1 && E2) {S} else break L
  *
  * This may lead to inlining of L.
  *
  *
  * BREAK INLINING:
  * Single-use labels are inlined at [Break] statements.
  * For example:
  *
  *   L0: { v0 = foo(); break L0 }; return v0;
  *     ==>
  *   v0 = foo(); return v0;
  *
  * This can lead to propagation of v0.
  *
  * See [visitBreak] and [visitLabeledStatement].
  *
  *
  * REDIRECT BREAKS:
  * Labeled statements whose next is a break become flattened and all breaks
  * to their label are redirected.
  * For example, where 'jump' is either break or continue:
  *
  *   L0: {... break L0 ...}; jump L1
  *     ==>
  *   {... jump L1 ...}
  *
  * This may trigger a flattening of nested ifs in case the eliminated label
  * separated two ifs.
  */
 class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
   String get passName => 'Statement rewriter';

   // The binding environment.  The rightmost element of the list is the nearest
   // available enclosing binding.
   List<Assign> environment;

   /// Binding environment for variables that are assigned to effectively
   /// constant expressions (see [isEffectivelyConstant]).
   final Map<Variable, Expression> constantEnvironment;

   /// Substitution map for labels. Any break to a label L should be substituted
   /// for a break to L' if L maps to L'.
   Map<Label, Jump> labelRedirects = <Label, Jump>{};

   /// Rewriter for methods.
   StatementRewriter() : constantEnvironment = <Variable, Expression>{};

   /// Rewriter for nested functions.
   StatementRewriter.nested(StatementRewriter parent)
       : constantEnvironment = parent.constantEnvironment;

   /// A set of labels that can be safely inlined at their use.
   ///
   /// The successor statements for labeled statements that have only one break
   /// from them are normally rewritten inline at the site of the break.  This
   /// is not safe if the code would be moved inside the scope of an exception
   /// handler (i.e., if the code would be moved into a try from outside it).
   Set<Label> safeForInlining = new Set<Label>();

   /// Returns the redirect target of [jump] or [jump] itself if it should not
   /// be redirected.
   Jump redirect(Jump jump) {
     Jump newJump = labelRedirects[jump.target];
     return newJump != null ? newJump : jump;
   }

   rewriteExecutableDefinition(ExecutableDefinition definition) {
     inEmptyEnvironment(() {
       definition.body = visitStatement(definition.body);
     });
   }

   void rewriteConstructorDefinition(ConstructorDefinition definition) {
     if (definition.isAbstract) return;
     definition.initializers.forEach(visitExpression);
     rewriteExecutableDefinition(definition);
   }

   void inEmptyEnvironment(void action()) {
     List<Assign> oldEnvironment = environment;
     environment = <Assign>[];
     action();
     assert(environment.isEmpty);
     environment = oldEnvironment;
   }

   Expression visitFieldInitializer(FieldInitializer node) {
     inEmptyEnvironment(() {
       node.body = visitStatement(node.body);
     });
     return node;
   }

   Expression visitSuperInitializer(SuperInitializer node) {
     inEmptyEnvironment(() {
       for (int i = node.arguments.length - 1; i >= 0; --i) {
         node.arguments[i] = visitStatement(node.arguments[i]);
         assert(environment.isEmpty);
       }
     });
     return node;
   }

   Expression visitExpression(Expression e) => e.processed ? e : e.accept(this);

   @override
   Expression visitVariableUse(VariableUse node) {
     // Propagate constant to use site.
     Expression constant = constantEnvironment[node.variable];
     if (constant != null) {
       --node.variable.readCount;
       return constant;
     }

     // Propagate a variable's definition to its use site if:
     // 1.  It has a single use, to avoid code growth and potential duplication
     //     of side effects, AND
     // 2.  It was the most recent expression evaluated so that we do not
     //     reorder expressions with side effects.
     if (!environment.isEmpty &&
         environment.last.variable == node.variable &&
         node.variable.readCount == 1) {
       --node.variable.readCount;
       return visitExpression(environment.removeLast().value);
     }

     // If the definition could not be propagated, leave the variable use.
     return node;
   }

   /// Returns true if [exp] has no side effects and has a constant value within
   /// any given activation of the enclosing method.
   bool isEffectivelyConstant(Expression exp) {
     // TODO(asgerf): Can be made more aggressive e.g. by checking conditional
     // expressions recursively. Determine if that is a valuable optimization
     // and/or if it is better handled at the CPS level.
     return exp is Constant ||
            exp is This ||
            exp is ReifyTypeVar ||
            exp is VariableUse && constantEnvironment.containsKey(exp.variable);
   }

   Statement visitAssign(Assign node) {
     if (isEffectivelyConstant(node.value) &&
         node.variable.writeCount == 1) {
       // Handle constant assignments specially.
       // They are always safe to propagate (though we should avoid duplication).
       // Moreover, they should not prevent other expressions from propagating.
       if (node.variable.readCount <= 1) {
         // A single-use constant should always be propagted to its use site.
         constantEnvironment[node.variable] = visitExpression(node.value);
         --node.variable.writeCount;
         return visitStatement(node.next);
       } else {
         // With more than one use, we cannot propagate the constant.
         // Visit the following statement without polluting [environment] so
         // that any preceding non-constant assignments might still propagate.
         node.next = visitStatement(node.next);
         node.value = visitExpression(node.value);
         return node;
       }
     } else {
       // Try to propagate assignment, and block previous assignment until this
       // has propagated.
       environment.add(node);
       Statement next = visitStatement(node.next);
       if (!environment.isEmpty && environment.last == node) {
         // The definition could not be propagated. Residualize the let binding.
         node.next = next;
         environment.removeLast();
         node.value = visitExpression(node.value);
         return node;
       }
       assert(!environment.contains(node));
       --node.variable.writeCount; // This assignment was removed.
       return next;
     }
   }

   Expression visitInvokeStatic(InvokeStatic node) {
     // Process arguments right-to-left, the opposite of evaluation order.
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }

   Expression visitInvokeMethod(InvokeMethod node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     node.receiver = visitExpression(node.receiver);
     return node;
   }

   Expression visitInvokeMethodDirectly(InvokeMethodDirectly node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     node.receiver = visitExpression(node.receiver);
     return node;
   }

   Expression visitInvokeConstructor(InvokeConstructor node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }

   Expression visitConcatenateStrings(ConcatenateStrings node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }

   Expression visitConditional(Conditional node) {
     node.condition = visitExpression(node.condition);

     inEmptyEnvironment(() {
       node.thenExpression = visitExpression(node.thenExpression);
       node.elseExpression = visitExpression(node.elseExpression);
     });

     return node;
   }

   Expression visitLogicalOperator(LogicalOperator node) {
     node.left = visitExpression(node.left);

     // Impure expressions may not propagate across the branch.
     inEmptyEnvironment(() {
       node.right = visitExpression(node.right);
     });

     return node;
   }

   Expression visitNot(Not node) {
     node.operand = visitExpression(node.operand);
     return node;
   }

   Expression visitFunctionExpression(FunctionExpression node) {
     new StatementRewriter.nested(this).rewrite(node.definition);
     return node;
   }

   Statement visitFunctionDeclaration(FunctionDeclaration node) {
     new StatementRewriter.nested(this).rewrite(node.definition);
     node.next = visitStatement(node.next);
     return node;
   }

   Statement visitReturn(Return node) {
     node.value = visitExpression(node.value);
     return node;
   }


   Statement visitBreak(Break node) {
     // Redirect through chain of breaks.
     // Note that useCount was accounted for at visitLabeledStatement.
     // Note redirect may return either a Break or Continue statement.
     Jump jump = redirect(node);
     if (jump is Break &&
         jump.target.useCount == 1 &&
         safeForInlining.contains(jump.target)) {
       --jump.target.useCount;
       return visitStatement(jump.target.binding.next);
     }
     return jump;
   }

   Statement visitContinue(Continue node) {
     return node;
   }

   Statement visitLabeledStatement(LabeledStatement node) {
     if (node.next is Jump) {
       // Eliminate label if next is a break or continue statement
       // Breaks to this label are redirected to the outer label.
       // Note that breakCount for the two labels is updated proactively here
       // so breaks can reliably tell if they should inline their target.
       Jump next = node.next;
       Jump newJump = redirect(next);
       labelRedirects[node.label] = newJump;
       newJump.target.useCount += node.label.useCount - 1;
       node.label.useCount = 0;
       Statement result = visitStatement(node.body);
       labelRedirects.remove(node.label); // Save some space.
       return result;
     }

     safeForInlining.add(node.label);
     node.body = visitStatement(node.body);
     safeForInlining.remove(node.label);

     if (node.label.useCount == 0) {
       // Eliminate the label if next was inlined at a break
       return node.body;
     }

     // Do not propagate assignments into the successor statements, since they
     // may be overwritten by assignments in the body.
     inEmptyEnvironment(() {
       node.next = visitStatement(node.next);
     });

     return node;
   }

   Statement visitIf(If node) {
     node.condition = visitExpression(node.condition);

     // Do not propagate assignments into branches.  Doing so will lead to code
     // duplication.
     // TODO(kmillikin): Rethink this. Propagating some assignments
     // (e.g. variables) is benign.  If they can occur here, they should
     // be handled well.
     inEmptyEnvironment(() {
       node.thenStatement = visitStatement(node.thenStatement);
       node.elseStatement = visitStatement(node.elseStatement);
     });

     tryCollapseIf(node);

     Statement reduced = combineStatementsWithSubexpressions(
         node.thenStatement,
         node.elseStatement,
         (t,f) => new Conditional(node.condition, t, f)..processed = true);
     if (reduced != null) {
       if (reduced.next is Break) {
         // In case the break can now be inlined.
         reduced = visitStatement(reduced);
       }
       return reduced;
     }

     return node;
   }

   Statement visitWhileTrue(WhileTrue node) {
     // Do not propagate assignments into loops.  Doing so is not safe for
     // variables modified in the loop (the initial value will be propagated).
     inEmptyEnvironment(() {
       node.body = visitStatement(node.body);
     });
     return node;
   }

   Statement visitWhileCondition(WhileCondition node) {
     // Not introduced yet
     throw "Unexpected WhileCondition in StatementRewriter";
   }

   Statement visitTry(Try node) {
     inEmptyEnvironment(() {
       Set<Label> saved = safeForInlining;
       safeForInlining = new Set<Label>();
       node.tryBody = visitStatement(node.tryBody);
       safeForInlining = saved;
       node.catchBody = visitStatement(node.catchBody);
     });
     return node;
   }

   Expression visitConstant(Constant node) {
     return node;
   }

   Expression visitThis(This node) {
     return node;
   }

   Expression visitReifyTypeVar(ReifyTypeVar node) {
     return node;
   }

   Expression visitLiteralList(LiteralList node) {
     // Process values right-to-left, the opposite of evaluation order.
     for (int i = node.values.length - 1; i >= 0; --i) {
       node.values[i] = visitExpression(node.values[i]);
     }
     return node;
   }

   Expression visitLiteralMap(LiteralMap node) {
     // Process arguments right-to-left, the opposite of evaluation order.
     for (LiteralMapEntry entry in node.entries.reversed) {
       entry.value = visitExpression(entry.value);
       entry.key = visitExpression(entry.key);
     }
     return node;
   }

   Expression visitTypeOperator(TypeOperator node) {
     node.receiver = visitExpression(node.receiver);
     return node;
   }

   Statement visitExpressionStatement(ExpressionStatement node) {
     node.expression = visitExpression(node.expression);
     // Do not allow propagation of assignments past an expression evaluated
     // for its side effects because it risks reordering side effects.
     // TODO(kmillikin): Rethink this.  Some propagation is benign,
     // e.g. variables, or other pure values that are not destroyed by
     // the expression statement.  If they can occur here they should be
     // handled well.
     inEmptyEnvironment(() {
       node.next = visitStatement(node.next);
     });
     return node;
   }

   Statement visitSetField(SetField node) {
     node.next = visitStatement(node.next);
     node.value = visitExpression(node.value);
     node.object = visitExpression(node.object);
     return node;
   }

   Expression visitGetField(GetField node) {
     node.object = visitExpression(node.object);
     return node;
   }

   Expression visitCreateBox(CreateBox node) {
     return node;
   }

   Expression visitCreateInstance(CreateInstance node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     return node;
   }

   Expression visitReifyRuntimeType(ReifyRuntimeType node) {
     node.value = visitExpression(node.value);
     return node;
   }

   Expression visitReadTypeVariable(ReadTypeVariable node) {
     node.target = visitExpression(node.target);
     return node;
   }

   /// If [s] and [t] are similar statements we extract their subexpressions
   /// and returns a new statement of the same type using expressions combined
   /// with the [combine] callback. For example:
   ///
   ///   combineStatements(Return E1, Return E2) = Return combine(E1, E2)
   ///
   /// If [combine] returns E1 then the unified statement is equivalent to [s],
   /// and if [combine] returns E2 the unified statement is equivalence to [t].
   ///
   /// It is guaranteed that no side effects occur between the beginning of the
   /// statement and the position of the combined expression.
   ///
   /// Returns null if the statements are too different.
   ///
   /// If non-null is returned, the caller MUST discard [s] and [t] and use
   /// the returned statement instead.
   static Statement combineStatementsWithSubexpressions(
       Statement s,
       Statement t,
       Expression combine(Expression s, Expression t)) {
     if (s is Return && t is Return) {
       return new Return(combine(s.value, t.value));
     }
     if (s is Assign && t is Assign && s.variable == t.variable) {
       Statement next = combineStatements(s.next, t.next);
       if (next != null) {
         // Destroy both original assignments to the variable.
         --s.variable.writeCount;
         --t.variable.writeCount;
         // The Assign constructor will increment the reference count again.
         return new Assign(s.variable,
                           combine(s.value, t.value),
                           next);
       }
     }
     if (s is ExpressionStatement && t is ExpressionStatement) {
       Statement next = combineStatements(s.next, t.next);
       if (next != null) {
         return new ExpressionStatement(combine(s.expression, t.expression),
                                        next);
       }
     }
     return null;
   }

   /// Returns a statement equivalent to both [s] and [t], or null if [s] and
   /// [t] are incompatible.
   /// If non-null is returned, the caller MUST discard [s] and [t] and use
   /// the returned statement instead.
   /// If two breaks are combined, the label's break counter will be decremented.
   static Statement combineStatements(Statement s, Statement t) {
     if (s is Break && t is Break && s.target == t.target) {
       --t.target.useCount; // Two breaks become one.
       return s;
     }
     if (s is Continue && t is Continue && s.target == t.target) {
       --t.target.useCount; // Two continues become one.
       return s;
     }
     if (s is Return && t is Return) {
       Expression e = combineExpressions(s.value, t.value);
       if (e != null) {
         return new Return(e);
       }
     }
     return null;
   }

   /// Returns an expression equivalent to both [e1] and [e2].
   /// If non-null is returned, the caller must discard [e1] and [e2] and use
   /// the resulting expression in the tree.
   static Expression combineExpressions(Expression e1, Expression e2) {
     if (e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable) {
       --e1.variable.readCount; // Two references become one.
       return e1;
     }
     if (e1 is Constant && e2 is Constant && e1.value == e2.value) {
       return e1;
     }
     return null;
   }

   /// Try to collapse nested ifs using && and || expressions.
   /// For example:
   ///
   ///   if (E1) { if (E2) S else break L } else break L
   ///     ==>
   ///   if (E1 && E2) S else break L
   ///
   /// [branch1] and [branch2] control the position of the S statement.
   ///
   /// Returns true if another collapse redex might have been introduced.
   void tryCollapseIf(If node) {
     // Repeatedly try to collapse nested ifs.
     // The transformation is shrinking (destroys an if) so it remains linear.
     // Here is an example where more than one iteration is required:
     //
     //   if (E1)
     //     if (E2) break L2 else break L1
     //   else
     //     break L1
     //
     // L1.target ::=
     //   if (E3) S else break L2
     //
     // After first collapse:
     //
     //   if (E1 && E2)
     //     break L2
     //   else
     //     {if (E3) S else break L2}  (inlined from break L1)
     //
     // We can then do another collapse using the inlined nested if.
     bool changed = true;
     while (changed) {
       changed = false;
       if (tryCollapseIfAux(node, true, true)) {
         changed = true;
       }
       if (tryCollapseIfAux(node, true, false)) {
         changed = true;
       }
       if (tryCollapseIfAux(node, false, true)) {
         changed = true;
       }
       if (tryCollapseIfAux(node, false, false)) {
         changed = true;
       }
     }
   }

   bool tryCollapseIfAux(If outerIf, bool branch1, bool branch2) {
     // NOTE: We name variables here as if S is in the then-then position.
     Statement outerThen = getBranch(outerIf, branch1);
     Statement outerElse = getBranch(outerIf, !branch1);
     if (outerThen is If && outerElse is Break) {
       If innerIf = outerThen;
       Statement innerThen = getBranch(innerIf, branch2);
       Statement innerElse = getBranch(innerIf, !branch2);
       if (innerElse is Break && innerElse.target == outerElse.target) {
         // We always put S in the then branch of the result, and adjust the
         // condition expression if S was actually found in the else branch(es).
         outerIf.condition = new LogicalOperator.and(
             makeCondition(outerIf.condition, branch1),
             makeCondition(innerIf.condition, branch2));
         outerIf.thenStatement = innerThen;
         --innerElse.target.useCount;

         // Try to inline the remaining break.  Do not propagate assignments.
         inEmptyEnvironment(() {
           outerIf.elseStatement = visitStatement(outerElse);
         });

         return outerIf.elseStatement is If && innerThen is Break;
       }
     }
     return false;
   }

   Expression makeCondition(Expression e, bool polarity) {
     return polarity ? e : new Not(e);
   }

   Statement getBranch(If node, bool polarity) {
     return polarity ? node.thenStatement : node.elseStatement;
   }
 }
	// 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;

	/**
	* Performs the following transformations on the tree:
	* - Assignment propagation
	* - If-to-conditional conversion
	* - Flatten nested ifs
	* - Break inlining
	* - Redirect breaks
	*
	* The above transformations all eliminate statements from the tree, and may
	* introduce redexes of each other.
	*
	*
	* ASSIGNMENT PROPAGATION:
	* Single-use definitions are propagated to their use site when possible.
	* For example:
	*
	* { v0 = foo(); return v0; }
	* ==>
	* return foo()
	*
	* After translating out of CPS, all intermediate values are bound by [Assign].
	* This transformation propagates such definitions to their uses when it is
	* safe and profitable. Bindings are processed "on demand" when their uses are
	* seen, but are only processed once to keep this transformation linear in
	* the size of the tree.
	*
	* The transformation builds an environment containing [Assign] bindings that
	* are in scope. These bindings have yet-untranslated definitions. When a use
	* is encountered the transformation determines if it is safe and profitable
	* to propagate the definition to its use. If so, it is removed from the
	* environment and the definition is recursively processed (in the
	* new environment at the use site) before being propagated.
	*
	* See [visitVariableUse] for the implementation of the heuristic for
	* propagating a definition.
	*
	*
	* IF-TO-CONDITIONAL CONVERSION:
	* If-statement are converted to conditional expressions when possible.
	* For example:
	*
	* if (v0) { v1 = foo(); break L } else { v1 = bar(); break L }
	* ==>
	* { v1 = v0 ? foo() : bar(); break L }
	*
	* This can lead to inlining of L, which in turn can lead to further propagation
	* of the variable v1.
	*
	* See [visitIf].
	*
	*
	* FLATTEN NESTED IFS:
	* An if inside an if is converted to an if with a logical operator.
	* For example:
	*
	* if (E1) { if (E2) {S} else break L } else break L
	* ==>
	* if (E1 && E2) {S} else break L
	*
	* This may lead to inlining of L.
	*
	*
	* BREAK INLINING:
	* Single-use labels are inlined at [Break] statements.
	* For example:
	*
	* L0: { v0 = foo(); break L0 }; return v0;
	* ==>
	* v0 = foo(); return v0;
	*
	* This can lead to propagation of v0.
	*
	* See [visitBreak] and [visitLabeledStatement].
	*
	*
	* REDIRECT BREAKS:
	* Labeled statements whose next is a break become flattened and all breaks
	* to their label are redirected.
	* For example, where 'jump' is either break or continue:
	*
	* L0: {... break L0 ...}; jump L1
	* ==>
	* {... jump L1 ...}
	*
	* This may trigger a flattening of nested ifs in case the eliminated label
	* separated two ifs.
	*/
	class StatementRewriter extends Visitor<Statement, Expression> with PassMixin {
	String get passName => 'Statement rewriter';

	// The binding environment. The rightmost element of the list is the nearest
	// available enclosing binding.
	List<Assign> environment;

	/// Binding environment for variables that are assigned to effectively
	/// constant expressions (see [isEffectivelyConstant]).
	final Map<Variable, Expression> constantEnvironment;

	/// Substitution map for labels. Any break to a label L should be substituted
	/// for a break to L' if L maps to L'.
	Map<Label, Jump> labelRedirects = <Label, Jump>{};

	/// Rewriter for methods.
	StatementRewriter() : constantEnvironment = <Variable, Expression>{};

	/// Rewriter for nested functions.
	StatementRewriter.nested(StatementRewriter parent)
	: constantEnvironment = parent.constantEnvironment;

	/// A set of labels that can be safely inlined at their use.
	///
	/// The successor statements for labeled statements that have only one break
	/// from them are normally rewritten inline at the site of the break. This
	/// is not safe if the code would be moved inside the scope of an exception
	/// handler (i.e., if the code would be moved into a try from outside it).
	Set<Label> safeForInlining = new Set<Label>();

	/// Returns the redirect target of [jump] or [jump] itself if it should not
	/// be redirected.
	Jump redirect(Jump jump) {
	Jump newJump = labelRedirects[jump.target];
	return newJump != null ? newJump : jump;
	}

	rewriteExecutableDefinition(ExecutableDefinition definition) {
	inEmptyEnvironment(() {
	definition.body = visitStatement(definition.body);
	});
	}

	void rewriteConstructorDefinition(ConstructorDefinition definition) {
	if (definition.isAbstract) return;
	definition.initializers.forEach(visitExpression);
	rewriteExecutableDefinition(definition);
	}

	void inEmptyEnvironment(void action()) {
	List<Assign> oldEnvironment = environment;
	environment = <Assign>[];
	action();
	assert(environment.isEmpty);
	environment = oldEnvironment;
	}

	Expression visitFieldInitializer(FieldInitializer node) {
	inEmptyEnvironment(() {
	node.body = visitStatement(node.body);
	});
	return node;
	}

	Expression visitSuperInitializer(SuperInitializer node) {
	inEmptyEnvironment(() {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitStatement(node.arguments[i]);
	assert(environment.isEmpty);
	}
	});
	return node;
	}

	Expression visitExpression(Expression e) => e.processed ? e : e.accept(this);

	@override
	Expression visitVariableUse(VariableUse node) {
	// Propagate constant to use site.
	Expression constant = constantEnvironment[node.variable];
	if (constant != null) {
	--node.variable.readCount;
	return constant;
	}

	// Propagate a variable's definition to its use site if:
	// 1. It has a single use, to avoid code growth and potential duplication
	// of side effects, AND
	// 2. It was the most recent expression evaluated so that we do not
	// reorder expressions with side effects.
	if (!environment.isEmpty &&
	environment.last.variable == node.variable &&
	node.variable.readCount == 1) {
	--node.variable.readCount;
	return visitExpression(environment.removeLast().value);
	}

	// If the definition could not be propagated, leave the variable use.
	return node;
	}

	/// Returns true if [exp] has no side effects and has a constant value within
	/// any given activation of the enclosing method.
	bool isEffectivelyConstant(Expression exp) {
	// TODO(asgerf): Can be made more aggressive e.g. by checking conditional
	// expressions recursively. Determine if that is a valuable optimization
	// and/or if it is better handled at the CPS level.
	return exp is Constant \|\|
	exp is This \|\|
	exp is ReifyTypeVar \|\|
	exp is VariableUse && constantEnvironment.containsKey(exp.variable);
	}

	Statement visitAssign(Assign node) {
	if (isEffectivelyConstant(node.value) &&
	node.variable.writeCount == 1) {
	// Handle constant assignments specially.
	// They are always safe to propagate (though we should avoid duplication).
	// Moreover, they should not prevent other expressions from propagating.
	if (node.variable.readCount <= 1) {
	// A single-use constant should always be propagted to its use site.
	constantEnvironment[node.variable] = visitExpression(node.value);
	--node.variable.writeCount;
	return visitStatement(node.next);
	} else {
	// With more than one use, we cannot propagate the constant.
	// Visit the following statement without polluting [environment] so
	// that any preceding non-constant assignments might still propagate.
	node.next = visitStatement(node.next);
	node.value = visitExpression(node.value);
	return node;
	}
	} else {
	// Try to propagate assignment, and block previous assignment until this
	// has propagated.
	environment.add(node);
	Statement next = visitStatement(node.next);
	if (!environment.isEmpty && environment.last == node) {
	// The definition could not be propagated. Residualize the let binding.
	node.next = next;
	environment.removeLast();
	node.value = visitExpression(node.value);
	return node;
	}
	assert(!environment.contains(node));
	--node.variable.writeCount; // This assignment was removed.
	return next;
	}
	}

	Expression visitInvokeStatic(InvokeStatic node) {
	// Process arguments right-to-left, the opposite of evaluation order.
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	return node;
	}

	Expression visitInvokeMethod(InvokeMethod node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	node.receiver = visitExpression(node.receiver);
	return node;
	}

	Expression visitInvokeMethodDirectly(InvokeMethodDirectly node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	node.receiver = visitExpression(node.receiver);
	return node;
	}

	Expression visitInvokeConstructor(InvokeConstructor node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	return node;
	}

	Expression visitConcatenateStrings(ConcatenateStrings node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	return node;
	}

	Expression visitConditional(Conditional node) {
	node.condition = visitExpression(node.condition);

	inEmptyEnvironment(() {
	node.thenExpression = visitExpression(node.thenExpression);
	node.elseExpression = visitExpression(node.elseExpression);
	});

	return node;
	}

	Expression visitLogicalOperator(LogicalOperator node) {
	node.left = visitExpression(node.left);

	// Impure expressions may not propagate across the branch.
	inEmptyEnvironment(() {
	node.right = visitExpression(node.right);
	});

	return node;
	}

	Expression visitNot(Not node) {
	node.operand = visitExpression(node.operand);
	return node;
	}

	Expression visitFunctionExpression(FunctionExpression node) {
	new StatementRewriter.nested(this).rewrite(node.definition);
	return node;
	}

	Statement visitFunctionDeclaration(FunctionDeclaration node) {
	new StatementRewriter.nested(this).rewrite(node.definition);
	node.next = visitStatement(node.next);
	return node;
	}

	Statement visitReturn(Return node) {
	node.value = visitExpression(node.value);
	return node;
	}


	Statement visitBreak(Break node) {
	// Redirect through chain of breaks.
	// Note that useCount was accounted for at visitLabeledStatement.
	// Note redirect may return either a Break or Continue statement.
	Jump jump = redirect(node);
	if (jump is Break &&
	jump.target.useCount == 1 &&
	safeForInlining.contains(jump.target)) {
	--jump.target.useCount;
	return visitStatement(jump.target.binding.next);
	}
	return jump;
	}

	Statement visitContinue(Continue node) {
	return node;
	}

	Statement visitLabeledStatement(LabeledStatement node) {
	if (node.next is Jump) {
	// Eliminate label if next is a break or continue statement
	// Breaks to this label are redirected to the outer label.
	// Note that breakCount for the two labels is updated proactively here
	// so breaks can reliably tell if they should inline their target.
	Jump next = node.next;
	Jump newJump = redirect(next);
	labelRedirects[node.label] = newJump;
	newJump.target.useCount += node.label.useCount - 1;
	node.label.useCount = 0;
	Statement result = visitStatement(node.body);
	labelRedirects.remove(node.label); // Save some space.
	return result;
	}

	safeForInlining.add(node.label);
	node.body = visitStatement(node.body);
	safeForInlining.remove(node.label);

	if (node.label.useCount == 0) {
	// Eliminate the label if next was inlined at a break
	return node.body;
	}

	// Do not propagate assignments into the successor statements, since they
	// may be overwritten by assignments in the body.
	inEmptyEnvironment(() {
	node.next = visitStatement(node.next);
	});

	return node;
	}

	Statement visitIf(If node) {
	node.condition = visitExpression(node.condition);

	// Do not propagate assignments into branches. Doing so will lead to code
	// duplication.
	// TODO(kmillikin): Rethink this. Propagating some assignments
	// (e.g. variables) is benign. If they can occur here, they should
	// be handled well.
	inEmptyEnvironment(() {
	node.thenStatement = visitStatement(node.thenStatement);
	node.elseStatement = visitStatement(node.elseStatement);
	});

	tryCollapseIf(node);

	Statement reduced = combineStatementsWithSubexpressions(
	node.thenStatement,
	node.elseStatement,
	(t,f) => new Conditional(node.condition, t, f)..processed = true);
	if (reduced != null) {
	if (reduced.next is Break) {
	// In case the break can now be inlined.
	reduced = visitStatement(reduced);
	}
	return reduced;
	}

	return node;
	}

	Statement visitWhileTrue(WhileTrue node) {
	// Do not propagate assignments into loops. Doing so is not safe for
	// variables modified in the loop (the initial value will be propagated).
	inEmptyEnvironment(() {
	node.body = visitStatement(node.body);
	});
	return node;
	}

	Statement visitWhileCondition(WhileCondition node) {
	// Not introduced yet
	throw "Unexpected WhileCondition in StatementRewriter";
	}

	Statement visitTry(Try node) {
	inEmptyEnvironment(() {
	Set<Label> saved = safeForInlining;
	safeForInlining = new Set<Label>();
	node.tryBody = visitStatement(node.tryBody);
	safeForInlining = saved;
	node.catchBody = visitStatement(node.catchBody);
	});
	return node;
	}

	Expression visitConstant(Constant node) {
	return node;
	}

	Expression visitThis(This node) {
	return node;
	}

	Expression visitReifyTypeVar(ReifyTypeVar node) {
	return node;
	}

	Expression visitLiteralList(LiteralList node) {
	// Process values right-to-left, the opposite of evaluation order.
	for (int i = node.values.length - 1; i >= 0; --i) {
	node.values[i] = visitExpression(node.values[i]);
	}
	return node;
	}

	Expression visitLiteralMap(LiteralMap node) {
	// Process arguments right-to-left, the opposite of evaluation order.
	for (LiteralMapEntry entry in node.entries.reversed) {
	entry.value = visitExpression(entry.value);
	entry.key = visitExpression(entry.key);
	}
	return node;
	}

	Expression visitTypeOperator(TypeOperator node) {
	node.receiver = visitExpression(node.receiver);
	return node;
	}

	Statement visitExpressionStatement(ExpressionStatement node) {
	node.expression = visitExpression(node.expression);
	// Do not allow propagation of assignments past an expression evaluated
	// for its side effects because it risks reordering side effects.
	// TODO(kmillikin): Rethink this. Some propagation is benign,
	// e.g. variables, or other pure values that are not destroyed by
	// the expression statement. If they can occur here they should be
	// handled well.
	inEmptyEnvironment(() {
	node.next = visitStatement(node.next);
	});
	return node;
	}

	Statement visitSetField(SetField node) {
	node.next = visitStatement(node.next);
	node.value = visitExpression(node.value);
	node.object = visitExpression(node.object);
	return node;
	}

	Expression visitGetField(GetField node) {
	node.object = visitExpression(node.object);
	return node;
	}

	Expression visitCreateBox(CreateBox node) {
	return node;
	}

	Expression visitCreateInstance(CreateInstance node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	return node;
	}

	Expression visitReifyRuntimeType(ReifyRuntimeType node) {
	node.value = visitExpression(node.value);
	return node;
	}

	Expression visitReadTypeVariable(ReadTypeVariable node) {
	node.target = visitExpression(node.target);
	return node;
	}

	/// If [s] and [t] are similar statements we extract their subexpressions
	/// and returns a new statement of the same type using expressions combined
	/// with the [combine] callback. For example:
	///
	/// combineStatements(Return E1, Return E2) = Return combine(E1, E2)
	///
	/// If [combine] returns E1 then the unified statement is equivalent to [s],
	/// and if [combine] returns E2 the unified statement is equivalence to [t].
	///
	/// It is guaranteed that no side effects occur between the beginning of the
	/// statement and the position of the combined expression.
	///
	/// Returns null if the statements are too different.
	///
	/// If non-null is returned, the caller MUST discard [s] and [t] and use
	/// the returned statement instead.
	static Statement combineStatementsWithSubexpressions(
	Statement s,
	Statement t,
	Expression combine(Expression s, Expression t)) {
	if (s is Return && t is Return) {
	return new Return(combine(s.value, t.value));
	}
	if (s is Assign && t is Assign && s.variable == t.variable) {
	Statement next = combineStatements(s.next, t.next);
	if (next != null) {
	// Destroy both original assignments to the variable.
	--s.variable.writeCount;
	--t.variable.writeCount;
	// The Assign constructor will increment the reference count again.
	return new Assign(s.variable,
	combine(s.value, t.value),
	next);
	}
	}
	if (s is ExpressionStatement && t is ExpressionStatement) {
	Statement next = combineStatements(s.next, t.next);
	if (next != null) {
	return new ExpressionStatement(combine(s.expression, t.expression),
	next);
	}
	}
	return null;
	}

	/// Returns a statement equivalent to both [s] and [t], or null if [s] and
	/// [t] are incompatible.
	/// If non-null is returned, the caller MUST discard [s] and [t] and use
	/// the returned statement instead.
	/// If two breaks are combined, the label's break counter will be decremented.
	static Statement combineStatements(Statement s, Statement t) {
	if (s is Break && t is Break && s.target == t.target) {
	--t.target.useCount; // Two breaks become one.
	return s;
	}
	if (s is Continue && t is Continue && s.target == t.target) {
	--t.target.useCount; // Two continues become one.
	return s;
	}
	if (s is Return && t is Return) {
	Expression e = combineExpressions(s.value, t.value);
	if (e != null) {
	return new Return(e);
	}
	}
	return null;
	}

	/// Returns an expression equivalent to both [e1] and [e2].
	/// If non-null is returned, the caller must discard [e1] and [e2] and use
	/// the resulting expression in the tree.
	static Expression combineExpressions(Expression e1, Expression e2) {
	if (e1 is VariableUse && e2 is VariableUse && e1.variable == e2.variable) {
	--e1.variable.readCount; // Two references become one.
	return e1;
	}
	if (e1 is Constant && e2 is Constant && e1.value == e2.value) {
	return e1;
	}
	return null;
	}

	/// Try to collapse nested ifs using && and \|\| expressions.
	/// For example:
	///
	/// if (E1) { if (E2) S else break L } else break L
	/// ==>
	/// if (E1 && E2) S else break L
	///
	/// [branch1] and [branch2] control the position of the S statement.
	///
	/// Returns true if another collapse redex might have been introduced.
	void tryCollapseIf(If node) {
	// Repeatedly try to collapse nested ifs.
	// The transformation is shrinking (destroys an if) so it remains linear.
	// Here is an example where more than one iteration is required:
	//
	// if (E1)
	// if (E2) break L2 else break L1
	// else
	// break L1
	//
	// L1.target ::=
	// if (E3) S else break L2
	//
	// After first collapse:
	//
	// if (E1 && E2)
	// break L2
	// else
	// {if (E3) S else break L2} (inlined from break L1)
	//
	// We can then do another collapse using the inlined nested if.
	bool changed = true;
	while (changed) {
	changed = false;
	if (tryCollapseIfAux(node, true, true)) {
	changed = true;
	}
	if (tryCollapseIfAux(node, true, false)) {
	changed = true;
	}
	if (tryCollapseIfAux(node, false, true)) {
	changed = true;
	}
	if (tryCollapseIfAux(node, false, false)) {
	changed = true;
	}
	}
	}

	bool tryCollapseIfAux(If outerIf, bool branch1, bool branch2) {
	// NOTE: We name variables here as if S is in the then-then position.
	Statement outerThen = getBranch(outerIf, branch1);
	Statement outerElse = getBranch(outerIf, !branch1);
	if (outerThen is If && outerElse is Break) {
	If innerIf = outerThen;
	Statement innerThen = getBranch(innerIf, branch2);
	Statement innerElse = getBranch(innerIf, !branch2);
	if (innerElse is Break && innerElse.target == outerElse.target) {
	// We always put S in the then branch of the result, and adjust the
	// condition expression if S was actually found in the else branch(es).
	outerIf.condition = new LogicalOperator.and(
	makeCondition(outerIf.condition, branch1),
	makeCondition(innerIf.condition, branch2));
	outerIf.thenStatement = innerThen;
	--innerElse.target.useCount;

	// Try to inline the remaining break. Do not propagate assignments.
	inEmptyEnvironment(() {
	outerIf.elseStatement = visitStatement(outerElse);
	});

	return outerIf.elseStatement is If && innerThen is Break;
	}
	}
	return false;
	}

	Expression makeCondition(Expression e, bool polarity) {
	return polarity ? e : new Not(e);
	}

	Statement getBranch(If node, bool polarity) {
	return polarity ? node.thenStatement : node.elseStatement;
	}
	}