pkg/compiler/lib/src/tree_ir/optimization/logical_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 tree_ir.optimization.logical_rewriter;

 import '../tree_ir_nodes.dart';
 import 'optimization.dart' show Pass;
 import '../../constants/values.dart' as values;

 /// Rewrites logical expressions to be more compact in the Tree IR.
 ///
 /// In this class an expression is said to occur in "boolean context" if
 /// its result is immediately applied to boolean conversion.
 ///
 /// IF STATEMENTS:
 ///
 /// We apply the following two rules to [If] statements (see [visitIf]).
 ///
 ///   if (E) {} else S  ==>  if (!E) S else {}    (else can be omitted)
 ///   if (!E) S1 else S2  ==>  if (E) S2 else S1  (unless previous rule applied)
 ///
 /// NEGATION:
 ///
 /// De Morgan's Laws are used to rewrite negations of logical operators so
 /// negations are closer to the root:
 ///
 ///   !x && !y  -->  !(x || y)
 ///
 /// This is to enable other rewrites, such as branch swapping in an if. In some
 /// contexts, the rule is reversed because we do not expect to apply a rewrite
 /// rule to the result. For example:
 ///
 ///   z = !(x || y)  ==>  z = !x && !y;
 ///
 /// CONDITIONALS:
 ///
 /// Conditionals with boolean constant operands occur frequently in the input.
 /// They can often the re-written to logical operators, for instance:
 ///
 ///   if (x ? y : false) S1 else S2
 ///     ==>
 ///   if (x && y) S1 else S2
 ///
 /// Conditionals are tricky to rewrite when they occur out of boolean context.
 /// Here we must apply more conservative rules, such as:
 ///
 ///   x ? true : false  ==>  !!x
 ///
 /// If the possible falsy values of the condition are known, we can sometimes
 /// introduce a logical operator:
 ///
 ///   !x ? y : false  ==>  !x && y
 ///
 class LogicalRewriter extends RecursiveTransformer
                       implements Pass {
   String get passName => 'Logical rewriter';

   @override
   void rewrite(FunctionDefinition node) {
     node.body = visitStatement(node.body);
   }

   final FallthroughStack fallthrough = new FallthroughStack();

   @override
   void visitInnerFunction(FunctionDefinition node) {
     new LogicalRewriter().rewrite(node);
   }

   /// True if the given statement is equivalent to its fallthrough semantics.
   ///
   /// This means it will ultimately translate to an empty statement.
   bool isFallthrough(Statement node) {
     return node is Break && isFallthroughBreak(node) ||
            node is Continue && isFallthroughContinue(node) ||
            node is Return && isFallthroughReturn(node);
   }

   bool isFallthroughBreak(Break node) {
     Statement target = fallthrough.target;
     return node.target.binding.next == target ||
            target is Break && target.target == node.target;
   }

   bool isFallthroughContinue(Continue node) {
     Statement target = fallthrough.target;
     return node.target.binding == target ||
            target is Continue && target.target == node.target;
   }

   bool isFallthroughReturn(Return node) {
     return isNull(node.value) && fallthrough.target == null;
   }

   bool isTerminator(Statement node) {
     return (node is Jump || node is Return) && !isFallthrough(node) ||
            (node is ExpressionStatement && node.next is Unreachable);
   }

   Statement visitIf(If node) {
     // If one of the branches is empty (i.e. just a fallthrough), then that
     // branch should preferably be the 'else' so we won't have to print it.
     // In other words, we wish to perform this rewrite:
     //   if (E) {} else {S}
     //     ==>
     //   if (!E) {S}
     // In the tree language, empty statements do not exist yet, so we must check
     // if one branch contains a break that can be eliminated by fallthrough.

     // Rewrite each branch and keep track of which ones might fall through.
     int usesBefore = fallthrough.useCount;
     node.thenStatement = visitStatement(node.thenStatement);
     int usesAfterThen = fallthrough.useCount;
     node.elseStatement = visitStatement(node.elseStatement);
     bool thenHasFallthrough = (fallthrough.useCount > usesBefore);
     bool elseHasFallthrough = (fallthrough.useCount > usesAfterThen);

     // Determine which branch is most beneficial as 'then' branch.
     const int THEN = 1;
     const int NEITHER = 0;
     const int ELSE = -1;
     int bestThenBranch = NEITHER;
     if (isFallthrough(node.thenStatement) &&
         !isFallthrough(node.elseStatement)) {
       // Put the empty statement in the 'else' branch.
       // if (E) {} else {S} ==> if (!E) {S}
       bestThenBranch = ELSE;
     } else if (isFallthrough(node.elseStatement) &&
                !isFallthrough(node.thenStatement)) {
       // Keep the empty statement in the 'else' branch.
       // if (E) {S} else {}
       bestThenBranch = THEN;
     } else if (thenHasFallthrough && !elseHasFallthrough) {
       // Put abrupt termination in the 'then' branch to omit 'else'.
       // if (E) {S1} else {S2; return v} ==> if (!E) {S2; return v}; S1
       bestThenBranch = ELSE;
     } else if (!thenHasFallthrough && elseHasFallthrough) {
       // Keep abrupt termination in the 'then' branch to omit 'else'.
       // if (E) {S1; return v}; S2
       bestThenBranch = THEN;
     } else if (isTerminator(node.elseStatement) &&
                !isTerminator(node.thenStatement)) {
       // Put early termination in the 'then' branch to reduce nesting depth.
       // if (E) {S}; return v ==> if (!E) return v; S
       bestThenBranch = ELSE;
     } else if (isTerminator(node.thenStatement) &&
                !isTerminator(node.elseStatement)) {
       // Keep early termination in the 'then' branch to reduce nesting depth.
       // if (E) {return v;} S
       bestThenBranch = THEN;
     }

     // Swap branches if 'else' is better as 'then'
     if (bestThenBranch == ELSE) {
       node.condition = new Not(node.condition);
       Statement tmp = node.thenStatement;
       node.thenStatement = node.elseStatement;
       node.elseStatement = tmp;
     }

     // If neither branch is better, eliminate a negation in the condition
     // if (!E) S1 else S2
     //   ==>
     // if (E) S2 else S1
     node.condition = makeCondition(node.condition, true,
                                    liftNots: bestThenBranch == NEITHER);
     if (bestThenBranch == NEITHER && node.condition is Not) {
       node.condition = (node.condition as Not).operand;
       Statement tmp = node.thenStatement;
       node.thenStatement = node.elseStatement;
       node.elseStatement = tmp;
     }

     return node;
   }

   Statement visitLabeledStatement(LabeledStatement node) {
     fallthrough.push(node.next);
     node.body = visitStatement(node.body);
     fallthrough.pop();
     node.next = visitStatement(node.next);
     return node;
   }

   Statement visitWhileTrue(WhileTrue node) {
     fallthrough.push(node);
     node.body = visitStatement(node.body);
     fallthrough.pop();
     return node;
   }

   Statement visitFor(For node) {
     fallthrough.push(node);
     node.condition = makeCondition(node.condition, true, liftNots: false);
     node.body = visitStatement(node.body);
     fallthrough.pop();
     node.next = visitStatement(node.next);
     return node;
   }

   Statement visitBreak(Break node) {
     if (isFallthroughBreak(node)) {
       fallthrough.use();
     }
     return node;
   }

   Statement visitContinue(Continue node) {
     if (isFallthroughContinue(node)) {
       fallthrough.use();
     }
     return node;
   }

   Statement visitReturn(Return node) {
     node.value = visitExpression(node.value);
     if (isFallthroughReturn(node)) {
       fallthrough.use();
     }
     return node;
   }

   Expression visitNot(Not node) {
     return toBoolean(makeCondition(node.operand, false, liftNots: false));
   }

   /// True if the only possible falsy return value of [condition] is [value].
   ///
   /// If [value] is `null` or a truthy value, false is returned. This is to make
   /// pattern matching more convenient.
   bool matchesFalsyValue(Expression condition, values.ConstantValue value) {
     if (value == null) return false;
     // TODO(asgerf): Here we could really use some more type information,
     //               this is just the best we can do at the moment.
     return isBooleanValued(condition) && value.isFalse;
   }

   /// True if the only possible truthy return value of [condition] is [value].
   ///
   /// If [value] is `null` or a falsy value, false is returned. This is to make
   /// pattern matching more convenient.
   bool matchesTruthyValue(Expression condition, values.ConstantValue value) {
     if (value == null) return false;
     // TODO(asgerf): Again, more type information could really beef this up.
     return isBooleanValued(condition) && value.isTrue;
   }

   values.ConstantValue getConstant(Expression exp) {
     return exp is Constant ? exp.value : null;
   }

   Expression visitConditional(Conditional node) {
     // node.condition will be visited after the then and else parts, because its
     // polarity depends on what rewrite we use.
     node.thenExpression = visitExpression(node.thenExpression);
     node.elseExpression = visitExpression(node.elseExpression);

     // In the following, we must take care not to eliminate or introduce a
     // boolean conversion.

     // x ? true : false --> !!x
     if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) {
       return toBoolean(makeCondition(node.condition, true, liftNots: false));
     }
     // x ? false : true --> !x
     if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) {
       return toBoolean(makeCondition(node.condition, false, liftNots: false));
     }

     // x ? y : false ==> x && y  (if x is truthy or false)
     // x ? y : null  ==> x && y  (if x is truthy or null)
     // x ? y : 0     ==> x && y  (if x is truthy or zero) (and so on...)
     if (matchesFalsyValue(node.condition, getConstant(node.elseExpression))) {
       return new LogicalOperator.and(
           visitExpression(node.condition),
           node.thenExpression);
     }
     // x ? true : y ==> x || y  (if x is falsy or true)
     // x ? 1    : y ==> x || y  (if x is falsy or one) (and so on...)
     if (matchesTruthyValue(node.condition, getConstant(node.thenExpression))) {
       return new LogicalOperator.or(
           visitExpression(node.condition),
           node.elseExpression);
     }
     // x ? y : true ==> !x || y
     if (isTrue(node.elseExpression)) {
       return new LogicalOperator.or(
           toBoolean(makeCondition(node.condition, false, liftNots: false)),
           node.thenExpression);
     }
     // x ? false : y ==> !x && y
     if (isFalse(node.thenExpression)) {
       return new LogicalOperator.and(
           toBoolean(makeCondition(node.condition, false, liftNots: false)),
           node.elseExpression);
     }

     node.condition = makeCondition(node.condition, true);

     // !x ? y : z ==> x ? z : y
     if (node.condition is Not) {
       node.condition = (node.condition as Not).operand;
       Expression tmp = node.thenExpression;
       node.thenExpression = node.elseExpression;
       node.elseExpression = tmp;
     }

     // x ? y : x ==> x && y
     if (isSameVariable(node.condition, node.elseExpression)) {
       destroyVariableUse(node.elseExpression);
       return new LogicalOperator.and(node.condition, node.thenExpression);
     }
     // x ? x : y ==> x || y
     if (isSameVariable(node.condition, node.thenExpression)) {
       destroyVariableUse(node.thenExpression);
       return new LogicalOperator.or(node.condition, node.elseExpression);
     }

     return node;
   }

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

   /// True if the given expression is known to evaluate to a boolean.
   /// This will not recursively traverse [Conditional] expressions, but if
   /// applied to the result of [visitExpression] conditionals will have been
   /// rewritten anyway.
   bool isBooleanValued(Expression e) {
     return isTrue(e) ||
            isFalse(e) ||
            e is Not ||
            e is LogicalOperator ||
            e is ApplyBuiltinOperator && operatorReturnsBool(e.operator);
   }

   /// True if the given operator always returns `true` or `false`.
   bool operatorReturnsBool(BuiltinOperator operator) {
     switch (operator) {
       case BuiltinOperator.StrictEq:
       case BuiltinOperator.StrictNeq:
       case BuiltinOperator.LooseEq:
       case BuiltinOperator.LooseNeq:
       case BuiltinOperator.NumLt:
       case BuiltinOperator.NumLe:
       case BuiltinOperator.NumGt:
       case BuiltinOperator.NumGe:
       case BuiltinOperator.IsNumber:
       case BuiltinOperator.IsNotNumber:
       case BuiltinOperator.IsFloor:
       case BuiltinOperator.IsNumberAndFloor:
       case BuiltinOperator.Identical:
         return true;
       default:
         return false;
     }
   }

   BuiltinOperator negateBuiltin(BuiltinOperator operator) {
     switch (operator) {
       case BuiltinOperator.StrictEq: return BuiltinOperator.StrictNeq;
       case BuiltinOperator.StrictNeq: return BuiltinOperator.StrictEq;
       case BuiltinOperator.LooseEq: return BuiltinOperator.LooseNeq;
       case BuiltinOperator.LooseNeq: return BuiltinOperator.LooseEq;
       case BuiltinOperator.IsNumber: return BuiltinOperator.IsNotNumber;
       case BuiltinOperator.IsNotNumber: return BuiltinOperator.IsNumber;

       // Because of NaN, these do not have a negated form.
       case BuiltinOperator.NumLt:
       case BuiltinOperator.NumLe:
       case BuiltinOperator.NumGt:
       case BuiltinOperator.NumGe:
         return null;

       default:
         return null;
     }
   }

   /// Forces a boolean conversion of the given expression.
   Expression toBoolean(Expression e) {
     if (isBooleanValued(e))
       return e;
     else
       return new Not(new Not(e));
   }

   /// Creates an equivalent boolean expression. The expression must occur in a
   /// context where its result is immediately subject to boolean conversion.
   /// If [polarity] if false, the negated condition will be created instead.
   /// If [liftNots] is true (default) then Not expressions will be lifted toward
   /// the root of the condition so they can be eliminated by the caller.
   Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) {
     if (e is Not) {
       // !!E ==> E
       return makeCondition(e.operand, !polarity, liftNots: liftNots);
     }
     if (e is LogicalOperator) {
       // If polarity=false, then apply the rewrite !(x && y) ==> !x || !y
       e.left = makeCondition(e.left, polarity);
       e.right = makeCondition(e.right, polarity);
       if (!polarity) {
         e.isAnd = !e.isAnd;
       }
       // !x && !y ==> !(x || y)  (only if lifting nots)
       if (e.left is Not && e.right is Not && liftNots) {
         e.left = (e.left as Not).operand;
         e.right = (e.right as Not).operand;
         e.isAnd = !e.isAnd;
         return new Not(e);
       }
       return e;
     }
     if (e is ApplyBuiltinOperator && polarity == false) {
       BuiltinOperator negated = negateBuiltin(e.operator);
       if (negated != null) {
         e.operator = negated;
         return visitExpression(e);
       } else {
         return new Not(visitExpression(e));
       }
     }
     if (e is Conditional) {
       // Handle polarity by: !(x ? y : z) ==> x ? !y : !z
       // Rewrite individual branches now. The condition will be rewritten
       // when we know what polarity to use (depends on which rewrite is used).
       e.thenExpression = makeCondition(e.thenExpression, polarity);
       e.elseExpression = makeCondition(e.elseExpression, polarity);

       // x ? true : false ==> x
       if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) {
         return makeCondition(e.condition, true, liftNots: liftNots);
       }
       // x ? false : true ==> !x
       if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) {
         return makeCondition(e.condition, false, liftNots: liftNots);
       }
       // x ? true : y  ==> x || y
       if (isTrue(e.thenExpression)) {
         return makeOr(makeCondition(e.condition, true),
                       e.elseExpression,
                       liftNots: liftNots);
       }
       // x ? false : y  ==> !x && y
       if (isFalse(e.thenExpression)) {
         return makeAnd(makeCondition(e.condition, false),
                        e.elseExpression,
                        liftNots: liftNots);
       }
       // x ? y : true  ==> !x || y
       if (isTrue(e.elseExpression)) {
         return makeOr(makeCondition(e.condition, false),
                       e.thenExpression,
                       liftNots: liftNots);
       }
       // x ? y : false  ==> x && y
       if (isFalse(e.elseExpression)) {
         return makeAnd(makeCondition(e.condition, true),
                        e.thenExpression,
                        liftNots: liftNots);
       }

       e.condition = makeCondition(e.condition, true);

       // !x ? y : z ==> x ? z : y
       if (e.condition is Not) {
         e.condition = (e.condition as Not).operand;
         Expression tmp = e.thenExpression;
         e.thenExpression = e.elseExpression;
         e.elseExpression = tmp;
       }
       // x ? !y : !z ==> !(x ? y : z)  (only if lifting nots)
       if (e.thenExpression is Not && e.elseExpression is Not && liftNots) {
         e.thenExpression = (e.thenExpression as Not).operand;
         e.elseExpression = (e.elseExpression as Not).operand;
         return new Not(e);
       }

       // x ? y : x ==> x && y
       if (isSameVariable(e.condition, e.elseExpression)) {
         destroyVariableUse(e.elseExpression);
         return new LogicalOperator.and(e.condition, e.thenExpression);
       }
       // x ? x : y ==> x || y
       if (isSameVariable(e.condition, e.thenExpression)) {
         destroyVariableUse(e.thenExpression);
         return new LogicalOperator.or(e.condition, e.elseExpression);
       }

       return e;
     }
     if (e is Constant && e.value.isBool) {
       // !true ==> false
       if (!polarity) {
         values.BoolConstantValue value = e.value;
         return new Constant.bool(value.negate());
       }
       return e;
     }
     e = visitExpression(e);
     return polarity ? e : new Not(e);
   }

   bool isNull(Expression e) {
     return e is Constant && e.value.isNull;
   }

   bool isTrue(Expression e) {
     return e is Constant && e.value.isTrue;
   }

   bool isFalse(Expression e) {
     return e is Constant && e.value.isFalse;
   }

   Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) {
     if (e1 is Not && e2 is Not && liftNots) {
       return new Not(new LogicalOperator.or(e1.operand, e2.operand));
     } else {
       return new LogicalOperator.and(e1, e2);
     }
   }

   Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) {
     if (e1 is Not && e2 is Not && liftNots) {
       return new Not(new LogicalOperator.and(e1.operand, e2.operand));
     } else {
       return new LogicalOperator.or(e1, e2);
     }
   }

   /// True if [e2] is known to return the same value as [e1]
   /// (with no additional side effects) if evaluated immediately after [e1].
   ///
   /// Concretely, this is true if [e1] and [e2] are uses of the same variable,
   /// or if [e2] is a use of a variable assigned by [e1].
   bool isSameVariable(Expression e1, Expression e2) {
     if (e1 is VariableUse) {
       return e2 is VariableUse && e1.variable == e2.variable;
     } else if (e1 is Assign) {
       return e2 is VariableUse && e1.variable == e2.variable;
     }
     return false;
   }

   void destroyVariableUse(VariableUse node) {
     --node.variable.readCount;
   }
 }
	// 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 tree_ir.optimization.logical_rewriter;

	import '../tree_ir_nodes.dart';
	import 'optimization.dart' show Pass;
	import '../../constants/values.dart' as values;

	/// Rewrites logical expressions to be more compact in the Tree IR.
	///
	/// In this class an expression is said to occur in "boolean context" if
	/// its result is immediately applied to boolean conversion.
	///
	/// IF STATEMENTS:
	///
	/// We apply the following two rules to [If] statements (see [visitIf]).
	///
	/// if (E) {} else S ==> if (!E) S else {} (else can be omitted)
	/// if (!E) S1 else S2 ==> if (E) S2 else S1 (unless previous rule applied)
	///
	/// NEGATION:
	///
	/// De Morgan's Laws are used to rewrite negations of logical operators so
	/// negations are closer to the root:
	///
	/// !x && !y --> !(x \|\| y)
	///
	/// This is to enable other rewrites, such as branch swapping in an if. In some
	/// contexts, the rule is reversed because we do not expect to apply a rewrite
	/// rule to the result. For example:
	///
	/// z = !(x \|\| y) ==> z = !x && !y;
	///
	/// CONDITIONALS:
	///
	/// Conditionals with boolean constant operands occur frequently in the input.
	/// They can often the re-written to logical operators, for instance:
	///
	/// if (x ? y : false) S1 else S2
	/// ==>
	/// if (x && y) S1 else S2
	///
	/// Conditionals are tricky to rewrite when they occur out of boolean context.
	/// Here we must apply more conservative rules, such as:
	///
	/// x ? true : false ==> !!x
	///
	/// If the possible falsy values of the condition are known, we can sometimes
	/// introduce a logical operator:
	///
	/// !x ? y : false ==> !x && y
	///
	class LogicalRewriter extends RecursiveTransformer
	implements Pass {
	String get passName => 'Logical rewriter';

	@override
	void rewrite(FunctionDefinition node) {
	node.body = visitStatement(node.body);
	}

	final FallthroughStack fallthrough = new FallthroughStack();

	@override
	void visitInnerFunction(FunctionDefinition node) {
	new LogicalRewriter().rewrite(node);
	}

	/// True if the given statement is equivalent to its fallthrough semantics.
	///
	/// This means it will ultimately translate to an empty statement.
	bool isFallthrough(Statement node) {
	return node is Break && isFallthroughBreak(node) \|\|
	node is Continue && isFallthroughContinue(node) \|\|
	node is Return && isFallthroughReturn(node);
	}

	bool isFallthroughBreak(Break node) {
	Statement target = fallthrough.target;
	return node.target.binding.next == target \|\|
	target is Break && target.target == node.target;
	}

	bool isFallthroughContinue(Continue node) {
	Statement target = fallthrough.target;
	return node.target.binding == target \|\|
	target is Continue && target.target == node.target;
	}

	bool isFallthroughReturn(Return node) {
	return isNull(node.value) && fallthrough.target == null;
	}

	bool isTerminator(Statement node) {
	return (node is Jump \|\| node is Return) && !isFallthrough(node) \|\|
	(node is ExpressionStatement && node.next is Unreachable);
	}

	Statement visitIf(If node) {
	// If one of the branches is empty (i.e. just a fallthrough), then that
	// branch should preferably be the 'else' so we won't have to print it.
	// In other words, we wish to perform this rewrite:
	// if (E) {} else {S}
	// ==>
	// if (!E) {S}
	// In the tree language, empty statements do not exist yet, so we must check
	// if one branch contains a break that can be eliminated by fallthrough.

	// Rewrite each branch and keep track of which ones might fall through.
	int usesBefore = fallthrough.useCount;
	node.thenStatement = visitStatement(node.thenStatement);
	int usesAfterThen = fallthrough.useCount;
	node.elseStatement = visitStatement(node.elseStatement);
	bool thenHasFallthrough = (fallthrough.useCount > usesBefore);
	bool elseHasFallthrough = (fallthrough.useCount > usesAfterThen);

	// Determine which branch is most beneficial as 'then' branch.
	const int THEN = 1;
	const int NEITHER = 0;
	const int ELSE = -1;
	int bestThenBranch = NEITHER;
	if (isFallthrough(node.thenStatement) &&
	!isFallthrough(node.elseStatement)) {
	// Put the empty statement in the 'else' branch.
	// if (E) {} else {S} ==> if (!E) {S}
	bestThenBranch = ELSE;
	} else if (isFallthrough(node.elseStatement) &&
	!isFallthrough(node.thenStatement)) {
	// Keep the empty statement in the 'else' branch.
	// if (E) {S} else {}
	bestThenBranch = THEN;
	} else if (thenHasFallthrough && !elseHasFallthrough) {
	// Put abrupt termination in the 'then' branch to omit 'else'.
	// if (E) {S1} else {S2; return v} ==> if (!E) {S2; return v}; S1
	bestThenBranch = ELSE;
	} else if (!thenHasFallthrough && elseHasFallthrough) {
	// Keep abrupt termination in the 'then' branch to omit 'else'.
	// if (E) {S1; return v}; S2
	bestThenBranch = THEN;
	} else if (isTerminator(node.elseStatement) &&
	!isTerminator(node.thenStatement)) {
	// Put early termination in the 'then' branch to reduce nesting depth.
	// if (E) {S}; return v ==> if (!E) return v; S
	bestThenBranch = ELSE;
	} else if (isTerminator(node.thenStatement) &&
	!isTerminator(node.elseStatement)) {
	// Keep early termination in the 'then' branch to reduce nesting depth.
	// if (E) {return v;} S
	bestThenBranch = THEN;
	}

	// Swap branches if 'else' is better as 'then'
	if (bestThenBranch == ELSE) {
	node.condition = new Not(node.condition);
	Statement tmp = node.thenStatement;
	node.thenStatement = node.elseStatement;
	node.elseStatement = tmp;
	}

	// If neither branch is better, eliminate a negation in the condition
	// if (!E) S1 else S2
	// ==>
	// if (E) S2 else S1
	node.condition = makeCondition(node.condition, true,
	liftNots: bestThenBranch == NEITHER);
	if (bestThenBranch == NEITHER && node.condition is Not) {
	node.condition = (node.condition as Not).operand;
	Statement tmp = node.thenStatement;
	node.thenStatement = node.elseStatement;
	node.elseStatement = tmp;
	}

	return node;
	}

	Statement visitLabeledStatement(LabeledStatement node) {
	fallthrough.push(node.next);
	node.body = visitStatement(node.body);
	fallthrough.pop();
	node.next = visitStatement(node.next);
	return node;
	}

	Statement visitWhileTrue(WhileTrue node) {
	fallthrough.push(node);
	node.body = visitStatement(node.body);
	fallthrough.pop();
	return node;
	}

	Statement visitFor(For node) {
	fallthrough.push(node);
	node.condition = makeCondition(node.condition, true, liftNots: false);
	node.body = visitStatement(node.body);
	fallthrough.pop();
	node.next = visitStatement(node.next);
	return node;
	}

	Statement visitBreak(Break node) {
	if (isFallthroughBreak(node)) {
	fallthrough.use();
	}
	return node;
	}

	Statement visitContinue(Continue node) {
	if (isFallthroughContinue(node)) {
	fallthrough.use();
	}
	return node;
	}

	Statement visitReturn(Return node) {
	node.value = visitExpression(node.value);
	if (isFallthroughReturn(node)) {
	fallthrough.use();
	}
	return node;
	}

	Expression visitNot(Not node) {
	return toBoolean(makeCondition(node.operand, false, liftNots: false));
	}

	/// True if the only possible falsy return value of [condition] is [value].
	///
	/// If [value] is `null` or a truthy value, false is returned. This is to make
	/// pattern matching more convenient.
	bool matchesFalsyValue(Expression condition, values.ConstantValue value) {
	if (value == null) return false;
	// TODO(asgerf): Here we could really use some more type information,
	// this is just the best we can do at the moment.
	return isBooleanValued(condition) && value.isFalse;
	}

	/// True if the only possible truthy return value of [condition] is [value].
	///
	/// If [value] is `null` or a falsy value, false is returned. This is to make
	/// pattern matching more convenient.
	bool matchesTruthyValue(Expression condition, values.ConstantValue value) {
	if (value == null) return false;
	// TODO(asgerf): Again, more type information could really beef this up.
	return isBooleanValued(condition) && value.isTrue;
	}

	values.ConstantValue getConstant(Expression exp) {
	return exp is Constant ? exp.value : null;
	}

	Expression visitConditional(Conditional node) {
	// node.condition will be visited after the then and else parts, because its
	// polarity depends on what rewrite we use.
	node.thenExpression = visitExpression(node.thenExpression);
	node.elseExpression = visitExpression(node.elseExpression);

	// In the following, we must take care not to eliminate or introduce a
	// boolean conversion.

	// x ? true : false --> !!x
	if (isTrue(node.thenExpression) && isFalse(node.elseExpression)) {
	return toBoolean(makeCondition(node.condition, true, liftNots: false));
	}
	// x ? false : true --> !x
	if (isFalse(node.thenExpression) && isTrue(node.elseExpression)) {
	return toBoolean(makeCondition(node.condition, false, liftNots: false));
	}

	// x ? y : false ==> x && y (if x is truthy or false)
	// x ? y : null ==> x && y (if x is truthy or null)
	// x ? y : 0 ==> x && y (if x is truthy or zero) (and so on...)
	if (matchesFalsyValue(node.condition, getConstant(node.elseExpression))) {
	return new LogicalOperator.and(
	visitExpression(node.condition),
	node.thenExpression);
	}
	// x ? true : y ==> x \|\| y (if x is falsy or true)
	// x ? 1 : y ==> x \|\| y (if x is falsy or one) (and so on...)
	if (matchesTruthyValue(node.condition, getConstant(node.thenExpression))) {
	return new LogicalOperator.or(
	visitExpression(node.condition),
	node.elseExpression);
	}
	// x ? y : true ==> !x \|\| y
	if (isTrue(node.elseExpression)) {
	return new LogicalOperator.or(
	toBoolean(makeCondition(node.condition, false, liftNots: false)),
	node.thenExpression);
	}
	// x ? false : y ==> !x && y
	if (isFalse(node.thenExpression)) {
	return new LogicalOperator.and(
	toBoolean(makeCondition(node.condition, false, liftNots: false)),
	node.elseExpression);
	}

	node.condition = makeCondition(node.condition, true);

	// !x ? y : z ==> x ? z : y
	if (node.condition is Not) {
	node.condition = (node.condition as Not).operand;
	Expression tmp = node.thenExpression;
	node.thenExpression = node.elseExpression;
	node.elseExpression = tmp;
	}

	// x ? y : x ==> x && y
	if (isSameVariable(node.condition, node.elseExpression)) {
	destroyVariableUse(node.elseExpression);
	return new LogicalOperator.and(node.condition, node.thenExpression);
	}
	// x ? x : y ==> x \|\| y
	if (isSameVariable(node.condition, node.thenExpression)) {
	destroyVariableUse(node.thenExpression);
	return new LogicalOperator.or(node.condition, node.elseExpression);
	}

	return node;
	}

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

	/// True if the given expression is known to evaluate to a boolean.
	/// This will not recursively traverse [Conditional] expressions, but if
	/// applied to the result of [visitExpression] conditionals will have been
	/// rewritten anyway.
	bool isBooleanValued(Expression e) {
	return isTrue(e) \|\|
	isFalse(e) \|\|
	e is Not \|\|
	e is LogicalOperator \|\|
	e is ApplyBuiltinOperator && operatorReturnsBool(e.operator);
	}

	/// True if the given operator always returns `true` or `false`.
	bool operatorReturnsBool(BuiltinOperator operator) {
	switch (operator) {
	case BuiltinOperator.StrictEq:
	case BuiltinOperator.StrictNeq:
	case BuiltinOperator.LooseEq:
	case BuiltinOperator.LooseNeq:
	case BuiltinOperator.NumLt:
	case BuiltinOperator.NumLe:
	case BuiltinOperator.NumGt:
	case BuiltinOperator.NumGe:
	case BuiltinOperator.IsNumber:
	case BuiltinOperator.IsNotNumber:
	case BuiltinOperator.IsFloor:
	case BuiltinOperator.IsNumberAndFloor:
	case BuiltinOperator.Identical:
	return true;
	default:
	return false;
	}
	}

	BuiltinOperator negateBuiltin(BuiltinOperator operator) {
	switch (operator) {
	case BuiltinOperator.StrictEq: return BuiltinOperator.StrictNeq;
	case BuiltinOperator.StrictNeq: return BuiltinOperator.StrictEq;
	case BuiltinOperator.LooseEq: return BuiltinOperator.LooseNeq;
	case BuiltinOperator.LooseNeq: return BuiltinOperator.LooseEq;
	case BuiltinOperator.IsNumber: return BuiltinOperator.IsNotNumber;
	case BuiltinOperator.IsNotNumber: return BuiltinOperator.IsNumber;

	// Because of NaN, these do not have a negated form.
	case BuiltinOperator.NumLt:
	case BuiltinOperator.NumLe:
	case BuiltinOperator.NumGt:
	case BuiltinOperator.NumGe:
	return null;

	default:
	return null;
	}
	}

	/// Forces a boolean conversion of the given expression.
	Expression toBoolean(Expression e) {
	if (isBooleanValued(e))
	return e;
	else
	return new Not(new Not(e));
	}

	/// Creates an equivalent boolean expression. The expression must occur in a
	/// context where its result is immediately subject to boolean conversion.
	/// If [polarity] if false, the negated condition will be created instead.
	/// If [liftNots] is true (default) then Not expressions will be lifted toward
	/// the root of the condition so they can be eliminated by the caller.
	Expression makeCondition(Expression e, bool polarity, {bool liftNots:true}) {
	if (e is Not) {
	// !!E ==> E
	return makeCondition(e.operand, !polarity, liftNots: liftNots);
	}
	if (e is LogicalOperator) {
	// If polarity=false, then apply the rewrite !(x && y) ==> !x \|\| !y
	e.left = makeCondition(e.left, polarity);
	e.right = makeCondition(e.right, polarity);
	if (!polarity) {
	e.isAnd = !e.isAnd;
	}
	// !x && !y ==> !(x \|\| y) (only if lifting nots)
	if (e.left is Not && e.right is Not && liftNots) {
	e.left = (e.left as Not).operand;
	e.right = (e.right as Not).operand;
	e.isAnd = !e.isAnd;
	return new Not(e);
	}
	return e;
	}
	if (e is ApplyBuiltinOperator && polarity == false) {
	BuiltinOperator negated = negateBuiltin(e.operator);
	if (negated != null) {
	e.operator = negated;
	return visitExpression(e);
	} else {
	return new Not(visitExpression(e));
	}
	}
	if (e is Conditional) {
	// Handle polarity by: !(x ? y : z) ==> x ? !y : !z
	// Rewrite individual branches now. The condition will be rewritten
	// when we know what polarity to use (depends on which rewrite is used).
	e.thenExpression = makeCondition(e.thenExpression, polarity);
	e.elseExpression = makeCondition(e.elseExpression, polarity);

	// x ? true : false ==> x
	if (isTrue(e.thenExpression) && isFalse(e.elseExpression)) {
	return makeCondition(e.condition, true, liftNots: liftNots);
	}
	// x ? false : true ==> !x
	if (isFalse(e.thenExpression) && isTrue(e.elseExpression)) {
	return makeCondition(e.condition, false, liftNots: liftNots);
	}
	// x ? true : y ==> x \|\| y
	if (isTrue(e.thenExpression)) {
	return makeOr(makeCondition(e.condition, true),
	e.elseExpression,
	liftNots: liftNots);
	}
	// x ? false : y ==> !x && y
	if (isFalse(e.thenExpression)) {
	return makeAnd(makeCondition(e.condition, false),
	e.elseExpression,
	liftNots: liftNots);
	}
	// x ? y : true ==> !x \|\| y
	if (isTrue(e.elseExpression)) {
	return makeOr(makeCondition(e.condition, false),
	e.thenExpression,
	liftNots: liftNots);
	}
	// x ? y : false ==> x && y
	if (isFalse(e.elseExpression)) {
	return makeAnd(makeCondition(e.condition, true),
	e.thenExpression,
	liftNots: liftNots);
	}

	e.condition = makeCondition(e.condition, true);

	// !x ? y : z ==> x ? z : y
	if (e.condition is Not) {
	e.condition = (e.condition as Not).operand;
	Expression tmp = e.thenExpression;
	e.thenExpression = e.elseExpression;
	e.elseExpression = tmp;
	}
	// x ? !y : !z ==> !(x ? y : z) (only if lifting nots)
	if (e.thenExpression is Not && e.elseExpression is Not && liftNots) {
	e.thenExpression = (e.thenExpression as Not).operand;
	e.elseExpression = (e.elseExpression as Not).operand;
	return new Not(e);
	}

	// x ? y : x ==> x && y
	if (isSameVariable(e.condition, e.elseExpression)) {
	destroyVariableUse(e.elseExpression);
	return new LogicalOperator.and(e.condition, e.thenExpression);
	}
	// x ? x : y ==> x \|\| y
	if (isSameVariable(e.condition, e.thenExpression)) {
	destroyVariableUse(e.thenExpression);
	return new LogicalOperator.or(e.condition, e.elseExpression);
	}

	return e;
	}
	if (e is Constant && e.value.isBool) {
	// !true ==> false
	if (!polarity) {
	values.BoolConstantValue value = e.value;
	return new Constant.bool(value.negate());
	}
	return e;
	}
	e = visitExpression(e);
	return polarity ? e : new Not(e);
	}

	bool isNull(Expression e) {
	return e is Constant && e.value.isNull;
	}

	bool isTrue(Expression e) {
	return e is Constant && e.value.isTrue;
	}

	bool isFalse(Expression e) {
	return e is Constant && e.value.isFalse;
	}

	Expression makeAnd(Expression e1, Expression e2, {bool liftNots: true}) {
	if (e1 is Not && e2 is Not && liftNots) {
	return new Not(new LogicalOperator.or(e1.operand, e2.operand));
	} else {
	return new LogicalOperator.and(e1, e2);
	}
	}

	Expression makeOr(Expression e1, Expression e2, {bool liftNots: true}) {
	if (e1 is Not && e2 is Not && liftNots) {
	return new Not(new LogicalOperator.and(e1.operand, e2.operand));
	} else {
	return new LogicalOperator.or(e1, e2);
	}
	}

	/// True if [e2] is known to return the same value as [e1]
	/// (with no additional side effects) if evaluated immediately after [e1].
	///
	/// Concretely, this is true if [e1] and [e2] are uses of the same variable,
	/// or if [e2] is a use of a variable assigned by [e1].
	bool isSameVariable(Expression e1, Expression e2) {
	if (e1 is VariableUse) {
	return e2 is VariableUse && e1.variable == e2.variable;
	} else if (e1 is Assign) {
	return e2 is VariableUse && e1.variable == e2.variable;
	}
	return false;
	}

	void destroyVariableUse(VariableUse node) {
	--node.variable.readCount;
	}
	}