Delete CPS IR

pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.dart

Index: pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.dart
diff --git a/pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.dart b/pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.dart
deleted file mode 100644
index bdfadae4e77b9536acc15e31c8aad42402dcaf9b..0000000000000000000000000000000000000000
--- a/pkg/compiler/lib/src/tree_ir/optimization/logical_rewriter.dart
+++ /dev/null
@@ -1,566 +0,0 @@
-// 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 '../../constants/values.dart' as values;
-import '../tree_ir_nodes.dart';
-import 'optimization.dart' show Pass;
-
-/// 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();
-
-  /// 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) ||
-        node is Throw;
-  }
-
-  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 && isBooleanValuedLogicalOperator(e) ||
-        e is ApplyBuiltinOperator && operatorReturnsBool(e.operator) ||
-        e is TypeOperator && isBooleanValuedTypeOperator(e);
-  }
-
-  bool isBooleanValuedLogicalOperator(LogicalOperator e) {
-    return isBooleanValued(e.left) && isBooleanValued(e.right);
-  }
-
-  /// 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.IsInteger:
-      case BuiltinOperator.IsNotInteger:
-      case BuiltinOperator.Identical:
-        return true;
-      default:
-        return false;
-    }
-  }
-
-  bool isBooleanValuedTypeOperator(TypeOperator e) {
-    return e.isTypeTest;
-  }
-
-  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;
-      case BuiltinOperator.IsInteger:
-        return BuiltinOperator.IsNotInteger;
-      case BuiltinOperator.IsNotInteger:
-        return BuiltinOperator.IsInteger;
-      case BuiltinOperator.IsUnsigned32BitInteger:
-        return BuiltinOperator.IsNotUnsigned32BitInteger;
-      case BuiltinOperator.IsNotUnsigned32BitInteger:
-        return BuiltinOperator.IsUnsigned32BitInteger;
-
-      // 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;
-  }
-}