pkg/compiler/lib/src/dart_backend/statement_rewriter.dart - sdk.git - 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.

 library statement_rewriter;

 import 'tree_ir_nodes.dart';

 /**
  * 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 [visitVariable] 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> {
   // The binding environment.  The rightmost element of the list is the nearest
   // available enclosing binding.
   List<Assign> environment;

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

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

   void rewrite(FunctionDefinition definition) {
     if (definition.isAbstract) return;

     environment = <Assign>[];
     definition.body = visitStatement(definition.body);

     // TODO(kmillikin):  Allow definitions that are not propagated.  Here,
     // this means rebuilding the binding with a recursively unnamed definition,
     // or else introducing a variable definition and an assignment.
     assert(environment.isEmpty);
   }

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

   Expression visitVariable(Variable node) {
     // 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 &&
         environment.last.hasExactlyOneUse) {
       return visitExpression(environment.removeLast().definition);
     }
     // If the definition could not be propagated, leave the variable use.
     return node;
   }


   Statement visitAssign(Assign node) {
     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.definition = visitExpression(node.definition);
       return node;
     }
     assert(!environment.contains(node));
     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 visitInvokeSuperMethod(InvokeSuperMethod node) {
     for (int i = node.arguments.length - 1; i >= 0; --i) {
       node.arguments[i] = visitExpression(node.arguments[i]);
     }
     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);

     List<Assign> savedEnvironment = environment;
     environment = <Assign>[];
     node.thenExpression = visitExpression(node.thenExpression);
     assert(environment.isEmpty);
     node.elseExpression = visitExpression(node.elseExpression);
     assert(environment.isEmpty);
     environment = savedEnvironment;

     return node;
   }

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

     environment.add(null); // impure expressions may not propagate across branch
     node.right = visitExpression(node.right);
     environment.removeLast();

     return node;
   }

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

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

   Statement visitFunctionDeclaration(FunctionDeclaration node) {
     new StatementRewriter().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) {
       --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;
     }

     node.body = visitStatement(node.body);

     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.
     List<Assign> savedEnvironment = environment;
     environment = <Assign>[];
     node.next = visitStatement(node.next);
     environment = savedEnvironment;

     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.,
     // constants or variables) is benign.  If they can occur here, they should
     // be handled well.
     List<Assign> savedEnvironment = environment;
     environment = <Assign>[];
     node.thenStatement = visitStatement(node.thenStatement);
     assert(environment.isEmpty);
     node.elseStatement = visitStatement(node.elseStatement);
     assert(environment.isEmpty);
     environment = savedEnvironment;

     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).
     List<Assign> savedEnvironment = environment;
     environment = <Assign>[];
     node.body = visitStatement(node.body);
     assert(environment.isEmpty);
     environment = savedEnvironment;
     return node;
   }

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

   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.,
     // constants, variables, or other pure values that are not destroyed by
     // the expression statement.  If they can occur here they should be
     // handled well.
     List<Assign> savedEnvironment = environment;
     environment = <Assign>[];
     node.next = visitStatement(node.next);
     assert(environment.isEmpty);
     environment = savedEnvironment;
     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) {
         --t.variable.writeCount; // Two assignments become one.
         return new Assign(s.variable,
                           combine(s.definition, t.definition),
                           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 Variable && e1 == e2) {
       --e1.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.
         List<Assign> savedEnvironment = environment;
         environment = <Assign>[];
         outerIf.elseStatement = visitStatement(outerElse);
         assert(environment.isEmpty);
         environment = savedEnvironment;

         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.

	library statement_rewriter;

	import 'tree_ir_nodes.dart';

	/**
	* 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 [visitVariable] 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> {
	// The binding environment. The rightmost element of the list is the nearest
	// available enclosing binding.
	List<Assign> environment;

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

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

	void rewrite(FunctionDefinition definition) {
	if (definition.isAbstract) return;

	environment = <Assign>[];
	definition.body = visitStatement(definition.body);

	// TODO(kmillikin): Allow definitions that are not propagated. Here,
	// this means rebuilding the binding with a recursively unnamed definition,
	// or else introducing a variable definition and an assignment.
	assert(environment.isEmpty);
	}

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

	Expression visitVariable(Variable node) {
	// 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 &&
	environment.last.hasExactlyOneUse) {
	return visitExpression(environment.removeLast().definition);
	}
	// If the definition could not be propagated, leave the variable use.
	return node;
	}


	Statement visitAssign(Assign node) {
	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.definition = visitExpression(node.definition);
	return node;
	}
	assert(!environment.contains(node));
	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 visitInvokeSuperMethod(InvokeSuperMethod node) {
	for (int i = node.arguments.length - 1; i >= 0; --i) {
	node.arguments[i] = visitExpression(node.arguments[i]);
	}
	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);

	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	node.thenExpression = visitExpression(node.thenExpression);
	assert(environment.isEmpty);
	node.elseExpression = visitExpression(node.elseExpression);
	assert(environment.isEmpty);
	environment = savedEnvironment;

	return node;
	}

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

	environment.add(null); // impure expressions may not propagate across branch
	node.right = visitExpression(node.right);
	environment.removeLast();

	return node;
	}

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

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

	Statement visitFunctionDeclaration(FunctionDeclaration node) {
	new StatementRewriter().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) {
	--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;
	}

	node.body = visitStatement(node.body);

	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.
	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	node.next = visitStatement(node.next);
	environment = savedEnvironment;

	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.,
	// constants or variables) is benign. If they can occur here, they should
	// be handled well.
	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	node.thenStatement = visitStatement(node.thenStatement);
	assert(environment.isEmpty);
	node.elseStatement = visitStatement(node.elseStatement);
	assert(environment.isEmpty);
	environment = savedEnvironment;

	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).
	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	node.body = visitStatement(node.body);
	assert(environment.isEmpty);
	environment = savedEnvironment;
	return node;
	}

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

	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.,
	// constants, variables, or other pure values that are not destroyed by
	// the expression statement. If they can occur here they should be
	// handled well.
	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	node.next = visitStatement(node.next);
	assert(environment.isEmpty);
	environment = savedEnvironment;
	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) {
	--t.variable.writeCount; // Two assignments become one.
	return new Assign(s.variable,
	combine(s.definition, t.definition),
	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 Variable && e1 == e2) {
	--e1.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.
	List<Assign> savedEnvironment = environment;
	environment = <Assign>[];
	outerIf.elseStatement = visitStatement(outerElse);
	assert(environment.isEmpty);
	environment = savedEnvironment;

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