pkg/compiler/lib/src/cps_ir/type_propagation.dart

// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
library dart2js.cps_ir.type_propagation;

import 'optimizers.dart';

import '../closure.dart' show
    ClosureClassElement;
import '../common/names.dart' show
    Identifiers,
    Selectors;
import '../compiler.dart' as dart2js show
    Compiler;
import '../constants/constant_system.dart';
import '../constants/values.dart';
import '../dart_types.dart' as types;
import '../diagnostics/invariant.dart' as dart2js show
    InternalErrorFunction;
import '../elements/elements.dart';
import '../io/source_information.dart' show
    SourceInformation;
import '../js_backend/js_backend.dart' show
    JavaScriptBackend;
import '../js_backend/codegen/task.dart' show
    CpsFunctionCompiler;
import '../resolution/access_semantics.dart';
import '../resolution/operators.dart';
import '../resolution/send_structure.dart';
import '../tree/tree.dart' as ast;
import '../types/types.dart';
import '../types/constants.dart' show
    computeTypeMask;
import '../universe/selector.dart' show
    Selector;
import '../world.dart' show World;
import 'cps_fragment.dart';
import 'cps_ir_nodes.dart';
import 'type_mask_system.dart';

class ConstantPropagationLattice {
  final TypeMaskSystem typeSystem;
  final ConstantSystem constantSystem;
  final types.DartTypes dartTypes;
  final AbstractValue anything;

  ConstantPropagationLattice(TypeMaskSystem typeSystem,
                             this.constantSystem,
                             this.dartTypes)
    : this.typeSystem = typeSystem,
      anything = new AbstractValue.nonConstant(typeSystem.dynamicType);

  final AbstractValue nothing = new AbstractValue.nothing();

  AbstractValue constant(ConstantValue value, [TypeMask type]) {
    if (type == null) type = typeSystem.getTypeOf(value);
    return new AbstractValue.constantValue(value, type);
  }

  AbstractValue nonConstant([TypeMask type]) {
    if (type == null) type = typeSystem.dynamicType;
    return new AbstractValue.nonConstant(type);
  }

  /// Compute the join of two values in the lattice.
  AbstractValue join(AbstractValue x, AbstractValue y) {
    assert(x != null);
    assert(y != null);

    if (x.isNothing) {
      return y;
    } else if (y.isNothing) {
      return x;
    } else if (x.isConstant && y.isConstant && x.constant == y.constant) {
      return x;
    } else {
      return new AbstractValue.nonConstant(typeSystem.join(x.type, y.type));
    }
  }

  /// True if all members of this value are booleans.
  bool isDefinitelyBool(AbstractValue value, {bool allowNull: false}) {
    return value.isNothing ||
      typeSystem.isDefinitelyBool(value.type, allowNull: allowNull);
  }

  /// True if all members of this value are numbers.
  bool isDefinitelyNum(AbstractValue value, {bool allowNull: false}) {
    return value.isNothing ||
      typeSystem.isDefinitelyNum(value.type, allowNull: allowNull);
  }

  /// True if all members of this value are strings.
  bool isDefinitelyString(AbstractValue value, {bool allowNull: false}) {
    return value.isNothing ||
      typeSystem.isDefinitelyString(value.type, allowNull: allowNull);
  }

  /// True if all members of this value are numbers, strings, or booleans.
  bool isDefinitelyNumStringBool(AbstractValue value, {bool allowNull: false}) {
    return value.isNothing ||
      typeSystem.isDefinitelyNumStringBool(value.type, allowNull: allowNull);
  }

  /// True if this value cannot be a string, number, or boolean.
  bool isDefinitelyNotNumStringBool(AbstractValue value) {
    return value.isNothing ||
      typeSystem.isDefinitelyNotNumStringBool(value.type);
  }

  /// True if this value cannot be a non-integer double.
  ///
  /// In other words, if true is returned, and the value is a number, then
  /// it is a whole number and is not NaN, Infinity, or minus Infinity.
  bool isDefinitelyNotNonIntegerDouble(AbstractValue value) {
    return value.isNothing ||
      value.isConstant && !value.constant.isDouble ||
      typeSystem.isDefinitelyNotNonIntegerDouble(value.type);
  }

  bool isDefinitelyInt(AbstractValue value,
                       {bool allowNull: false}) {
    return value.isNothing ||
        typeSystem.isDefinitelyInt(value.type, allowNull: allowNull);
  }

  bool isDefinitelyNativeList(AbstractValue value,
                              {bool allowNull: false}) {
    return value.isNothing ||
        typeSystem.isDefinitelyNativeList(value.type, allowNull: allowNull);
  }

  bool isDefinitelyMutableNativeList(AbstractValue value,
                                     {bool allowNull: false}) {
    return value.isNothing ||
         typeSystem.isDefinitelyMutableNativeList(value.type,
                                                  allowNull: allowNull);
  }

  bool isDefinitelyFixedNativeList(AbstractValue value,
                                   {bool allowNull: false}) {
    return value.isNothing ||
        typeSystem.isDefinitelyFixedNativeList(value.type,
                                               allowNull: allowNull);
  }

  bool isDefinitelyExtendableNativeList(AbstractValue value,
                                        {bool allowNull: false}) {
    return value.isNothing ||
        typeSystem.isDefinitelyExtendableNativeList(value.type,
                                                    allowNull: allowNull);
  }

  bool isDefinitelyIndexable(AbstractValue value, {bool allowNull: false}) {
    return value.isNothing ||
        typeSystem.isDefinitelyIndexable(value.type, allowNull: allowNull);
  }

  /// Returns whether the given [value] is an instance of [type].
  ///
  /// Since [value] and [type] are not always known, [AbstractBool.Maybe] is
  /// returned if the answer is not known.
  ///
  /// [AbstractBool.Nothing] is returned if [value] is nothing.
  ///
  /// If [allowNull] is true, `null` is considered an instance of anything,
  /// otherwise it is only considered an instance of [Object], [dynamic], and
  /// [Null].
  AbstractBool isSubtypeOf(AbstractValue value,
                           types.DartType type,
                           {bool allowNull}) {
    assert(allowNull != null);
    if (value.isNothing) {
      return AbstractBool.Nothing;
    }
    if (value.isConstant) {
      if (value.constant.isNull) {
        if (allowNull ||
            type.isObject ||
            type.isDynamic ||
            type == dartTypes.coreTypes.nullType) {
          return AbstractBool.True;
        }
        if (type is types.TypeVariableType) {
          return AbstractBool.Maybe;
        }
        return AbstractBool.False;
      }
      if (type == dartTypes.coreTypes.intType) {
        return constantSystem.isInt(value.constant)
          ? AbstractBool.True
          : AbstractBool.False;
      }
      types.DartType valueType = value.constant.getType(dartTypes.coreTypes);
      if (constantSystem.isSubtype(dartTypes, valueType, type)) {
        return AbstractBool.True;
      }
      if (!dartTypes.isPotentialSubtype(valueType, type)) {
        return AbstractBool.False;
      }
      return AbstractBool.Maybe;
    }
    return typeSystem.isSubtypeOf(value.type, type, allowNull: allowNull);
  }

  /// Returns the possible results of applying [operator] to [value],
  /// assuming the operation does not throw.
  ///
  /// Because we do not explicitly track thrown values, we currently use the
  /// convention that constant values are returned from this method only
  /// if the operation is known not to throw.
  ///
  /// This method returns `null` if a good result could not be found. In that
  /// case, it is best to fall back on interprocedural type information.
  AbstractValue unaryOp(UnaryOperator operator,
                        AbstractValue value) {
    // TODO(asgerf): Also return information about whether this can throw?
    if (value.isNothing) {
      return nothing;
    }
    if (value.isConstant) {
      UnaryOperation operation = constantSystem.lookupUnary(operator);
      ConstantValue result = operation.fold(value.constant);
      if (result == null) return anything;
      return constant(result);
    }
    return null; // TODO(asgerf): Look up type?
  }

  /// Returns the possible results of applying [operator] to [left], [right],
  /// assuming the operation does not throw.
  ///
  /// Because we do not explicitly track thrown values, we currently use the
  /// convention that constant values are returned from this method only
  /// if the operation is known not to throw.
  ///
  /// This method returns `null` if a good result could not be found. In that
  /// case, it is best to fall back on interprocedural type information.
  AbstractValue binaryOp(BinaryOperator operator,
                         AbstractValue left,
                         AbstractValue right) {
    if (left.isNothing || right.isNothing) {
      return nothing;
    }
    if (left.isConstant && right.isConstant) {
      BinaryOperation operation = constantSystem.lookupBinary(operator);
      ConstantValue result = operation.fold(left.constant, right.constant);
      if (result == null) return anything;
      return constant(result);
    }
    // TODO(asgerf): Handle remaining operators and the UIntXX types.
    switch (operator.kind) {
      case BinaryOperatorKind.ADD:
      case BinaryOperatorKind.SUB:
      case BinaryOperatorKind.MUL:
        if (isDefinitelyInt(left) && isDefinitelyInt(right)) {
          return nonConstant(typeSystem.intType);
        }
        return null;

      case BinaryOperatorKind.EQ:
        bool behavesLikeIdentity =
          isDefinitelyNumStringBool(left, allowNull: true) ||
          right.isNullConstant;
        if (behavesLikeIdentity &&
            typeSystem.areDisjoint(left.type, right.type)) {
          return constant(new FalseConstantValue());
        }
        return null;

      default:
        return null; // The caller will use return type from type inference.
    }
  }

  AbstractValue stringConstant(String value) {
    return constant(new StringConstantValue(new ast.DartString.literal(value)));
  }

  AbstractValue stringify(AbstractValue value) {
    if (value.isNothing) return nothing;
    if (value.isNonConst) return nonConstant(typeSystem.stringType);
    ConstantValue constantValue = value.constant;
    if (constantValue is StringConstantValue) {
      return value;
    } else if (constantValue is PrimitiveConstantValue) {
      // Note: The primitiveValue for a StringConstantValue is not suitable
      // for toString() use since it is a DartString. But the other subclasses
      // returns an unwrapped Dart value we can safely convert to a string.
      return stringConstant(constantValue.primitiveValue.toString());
    } else {
      return nonConstant(typeSystem.stringType);
    }
  }

  /// Returns whether [value] is one of the falsy values: false, 0, -0, NaN,
  /// the empty string, or null.
  AbstractBool boolify(AbstractValue value) {
    if (value.isNothing) return AbstractBool.Nothing;
    if (value.isConstant) {
      ConstantValue constantValue = value.constant;
      if (isFalsyConstant(constantValue)) {
        return AbstractBool.False;
      } else {
        return AbstractBool.True;
      }
    }
    return typeSystem.boolify(value.type);
  }

  /// Returns whether [value] is the value `true`.
  AbstractBool strictBoolify(AbstractValue value) {
    if (value.isNothing) return AbstractBool.Nothing;
    if (value.isConstant) {
      return value.constant.isTrue ? AbstractBool.True : AbstractBool.False;
    }
    return typeSystem.strictBoolify(value.type);
  }

  /// The possible return types of a method that may be targeted by
  /// [typedSelector]. If the given selector is not a [TypedSelector], any
  /// reachable method matching the selector may be targeted.
  AbstractValue getInvokeReturnType(Selector selector, TypeMask mask) {
    return fromMask(typeSystem.getInvokeReturnType(selector, mask));
  }

  AbstractValue fromMask(TypeMask mask) {
    ConstantValue constantValue = typeSystem.getConstantOf(mask);
    if (constantValue != null) return constant(constantValue, mask);
    return nonConstant(mask);
  }
}

/**
 * Propagates types (including value types for constants) throughout the IR, and
 * replaces branches with fixed jumps as well as side-effect free expressions
 * with known constant results.
 *
 * Should be followed by the [ShrinkingReducer] pass.
 *
 * Implemented according to 'Constant Propagation with Conditional Branches'
 * by Wegman, Zadeck.
 */
class TypePropagator extends Pass {
  String get passName => 'Sparse constant propagation';

  final dart2js.Compiler _compiler;
  final CpsFunctionCompiler _functionCompiler;
  final ConstantPropagationLattice _lattice;
  final dart2js.InternalErrorFunction _internalError;
  final Map<Variable, ConstantValue> _values = <Variable, ConstantValue>{};
  final TypeMaskSystem _typeSystem;

  TypePropagator(dart2js.Compiler compiler,
                 TypeMaskSystem typeSystem,
                 this._functionCompiler)
      : _compiler = compiler,
        _internalError = compiler.internalError,
        _typeSystem = typeSystem,
        _lattice = new ConstantPropagationLattice(
            typeSystem,
            compiler.backend.constantSystem,
            compiler.types);

  @override
  void rewrite(FunctionDefinition root) {
    // Set all parent pointers.
    new ParentVisitor().visit(root);

    Map<Expression, ConstantValue> replacements = <Expression, ConstantValue>{};

    // Analyze. In this phase, the entire term is analyzed for reachability
    // and the abstract value of each expression.
    TypePropagationVisitor analyzer = new TypePropagationVisitor(
        _lattice,
        _values,
        replacements,
        _internalError);

    analyzer.analyze(root);

    // Transform. Uses the data acquired in the previous analysis phase to
    // replace branches with fixed targets and side-effect-free expressions
    // with constant results or existing values that are in scope.
    TransformingVisitor transformer = new TransformingVisitor(
        _compiler,
        _functionCompiler,
        _lattice,
        analyzer,
        replacements,
        _internalError);
    transformer.transform(root);
  }
}

final Map<String, BuiltinOperator> NumBinaryBuiltins =
  const <String, BuiltinOperator>{
    '+':  BuiltinOperator.NumAdd,
    '-':  BuiltinOperator.NumSubtract,
    '*':  BuiltinOperator.NumMultiply,
    '&':  BuiltinOperator.NumAnd,
    '|':  BuiltinOperator.NumOr,
    '^':  BuiltinOperator.NumXor,
    '<':  BuiltinOperator.NumLt,
    '<=': BuiltinOperator.NumLe,
    '>':  BuiltinOperator.NumGt,
    '>=': BuiltinOperator.NumGe
};

/**
 * Uses the information from a preceding analysis pass in order to perform the
 * actual transformations on the CPS graph.
 */
class TransformingVisitor extends LeafVisitor {
  final TypePropagationVisitor analyzer;
  final Map<Expression, ConstantValue> replacements;
  final ConstantPropagationLattice lattice;
  final dart2js.Compiler compiler;
  final CpsFunctionCompiler functionCompiler;

  JavaScriptBackend get backend => compiler.backend;
  TypeMaskSystem get typeSystem => lattice.typeSystem;
  types.DartTypes get dartTypes => lattice.dartTypes;
  Map<Variable, ConstantValue> get values => analyzer.values;

  final dart2js.InternalErrorFunction internalError;

  final List<Node> stack = <Node>[];

  TransformingVisitor(this.compiler,
                      this.functionCompiler,
                      this.lattice,
                      this.analyzer,
                      this.replacements,
                      this.internalError);

  void transform(FunctionDefinition root) {
    push(root.body);
    while (stack.isNotEmpty) {
      visit(stack.removeLast());
    }
  }

  void push(Node node) {
    assert(node != null);
    stack.add(node);
  }

  void pushAll(Iterable<Node> nodes) {
    nodes.forEach(push);
  }

  /************************* INTERIOR EXPRESSIONS *************************/
  //
  // These return nothing, and must push recursive children on the stack.

  void visitLetCont(LetCont node) {
    pushAll(node.continuations);
    push(node.body);
  }

  void visitLetHandler(LetHandler node) {
    push(node.handler);
    push(node.body);
  }

  void visitLetMutable(LetMutable node) {
    visit(node.variable);
    push(node.body);
  }

  void visitLetPrim(LetPrim node) {
    AbstractValue value = getValue(node.primitive);
    if (node.primitive is! Constant &&
        node.primitive is! Refinement &&
        node.primitive.isSafeForElimination &&
        value.isConstant) {
      // If the value is a known constant, compile it as a constant.
      Constant newPrim = makeConstantPrimitive(value.constant);
      newPrim.substituteFor(node.primitive);
      RemovalVisitor.remove(node.primitive);
      node.primitive = newPrim;
      newPrim.parent = node;
    } else {
      Primitive newPrim = visit(node.primitive);
      if (newPrim != null) {
        newPrim.substituteFor(node.primitive);
        RemovalVisitor.remove(node.primitive);
        node.primitive = newPrim;
        newPrim.parent = node;
        reanalyze(newPrim);
      }
      if (node.primitive.hasNoUses && node.primitive.isSafeForElimination) {
        // Remove unused primitives before entering the body.
        // This would also be done by shrinking reductions, but usage analyses
        // such as isAlwaysBoolified are more precise without the dead uses, so
        // we prefer to remove them early.
        RemovalVisitor.remove(node.primitive);
        node.parent.body = node.body;
        node.body.parent = node.parent;
      }
    }
    push(node.body);
  }

  void visitContinuation(Continuation node) {
    if (node.isReturnContinuation) return;
    if (!analyzer.reachableContinuations.contains(node)) {
      replaceSubtree(node.body, new Unreachable());
    }
    // Process the continuation body.
    // Note that the continuation body may have changed since the continuation
    // was put on the stack (e.g. [visitInvokeContinuation] may do this).
    push(node.body);
  }

  /************************* TRANSFORMATION HELPERS *************************/

  /// Sets parent pointers and computes types for the given subtree.
  void reanalyze(Node node) {
    new ParentVisitor().visit(node);
    analyzer.reanalyzeSubtree(node);
  }

  /// Removes the entire subtree of [node] and inserts [replacement].
  ///
  /// By default, all references in the [node] subtree are unlinked, and parent
  /// pointers in [replacement] are initialized and its types recomputed.
  ///
  /// If the caller needs to manually unlink the node, because some references
  /// were adopted by other nodes, it can be disabled by passing `false`
  /// as the [unlink] parameter.
  ///
  /// [replacement] must be "fresh", i.e. it must not contain significant parts
  /// of the original IR inside of it since the [ParentVisitor] will
  /// redundantly reprocess it.
  void replaceSubtree(Expression node, Expression replacement,
                      {bool unlink: true}) {
    InteriorNode parent = node.parent;
    parent.body = replacement;
    replacement.parent = parent;
    node.parent = null;
    if (unlink) {
      RemovalVisitor.remove(node);
    }
    reanalyze(replacement);
  }

  /// Inserts [insertedCode] before [node].
  ///
  /// [node] will end up in the hole of [insertedCode], and [insertedCode]
  /// will become rooted where [node] was.
  void insertBefore(Expression node, CpsFragment insertedCode) {
    if (insertedCode.isEmpty) return; // Nothing to do.
    assert(insertedCode.isOpen);
    InteriorNode parent = node.parent;
    InteriorNode context = insertedCode.context;

    parent.body = insertedCode.root;
    insertedCode.root.parent = parent;

    // We want to recompute the types for [insertedCode] without
    // traversing the entire subtree of [node]. Temporarily close the
    // term with a dummy node while recomputing types.
    context.body = new Unreachable();
    new ParentVisitor().visit(insertedCode.root);
    reanalyze(insertedCode.root);

    context.body = node;
    node.parent = context;
  }

  /// Binds [prim] before [node].
  void insertLetPrim(Expression node, Primitive prim) {
    InteriorNode parent = node.parent;
    LetPrim let = new LetPrim(prim);
    parent.body = let;
    let.body = node;
    node.parent = let;
    let.parent = parent;
  }

  /// Make a constant primitive for [constant] and set its entry in [values].
  Constant makeConstantPrimitive(ConstantValue constant) {
    Constant primitive = new Constant(constant);
    primitive.type = typeSystem.getTypeOf(constant);
    values[primitive] = constant;
    return primitive;
  }

  /// Builds `(LetPrim p (InvokeContinuation k p))`.
  ///
  /// No parent pointers are set.
  LetPrim makeLetPrimInvoke(Primitive primitive, Continuation continuation) {
    assert(continuation.parameters.length == 1);

    LetPrim letPrim = new LetPrim(primitive);
    InvokeContinuation invoke =
        new InvokeContinuation(continuation, <Primitive>[primitive]);
    letPrim.body = invoke;
    values[primitive] = values[continuation.parameters.single];
    primitive.hint = continuation.parameters.single.hint;

    return letPrim;
  }

  /************************* TAIL EXPRESSIONS *************************/

  // A branch can be eliminated and replaced by an invocation if only one of
  // the possible continuations is reachable. Removal often leads to both dead
  // primitives (the condition variable) and dead continuations (the unreachable
  // branch), which are both removed by the shrinking reductions pass.
  //
  // (Branch (IsTrue true) k0 k1) -> (InvokeContinuation k0)
  void visitBranch(Branch node) {
    Continuation trueCont = node.trueContinuation.definition;
    Continuation falseCont = node.falseContinuation.definition;
    Primitive condition = node.condition.definition;
    AbstractValue conditionValue = getValue(condition);

    // Change to non-strict check if the condition is a boolean or null.
    if (lattice.isDefinitelyBool(conditionValue, allowNull: true)) {
      node.isStrictCheck = false;
    }

    AbstractBool boolifiedValue = node.isStrictCheck
        ? lattice.strictBoolify(conditionValue)
        : lattice.boolify(conditionValue);

    if (boolifiedValue == AbstractBool.True) {
      replaceSubtree(falseCont.body, new Unreachable());
      InvokeContinuation invoke = new InvokeContinuation(trueCont, []);
      replaceSubtree(node, invoke);
      push(invoke);
      return;
    }
    if (boolifiedValue == AbstractBool.False) {
      replaceSubtree(trueCont.body, new Unreachable());
      InvokeContinuation invoke = new InvokeContinuation(falseCont, []);
      replaceSubtree(node, invoke);
      push(invoke);
      return;
    }

    if (condition is ApplyBuiltinOperator &&
        (condition.operator == BuiltinOperator.LooseEq ||
         condition.operator == BuiltinOperator.StrictEq)) {
      Primitive leftArg = condition.arguments[0].definition;
      Primitive rightArg = condition.arguments[1].definition;
      AbstractValue left = getValue(leftArg);
      AbstractValue right = getValue(rightArg);
      if (right.isNullConstant &&
          lattice.isDefinitelyNotNumStringBool(left)) {
        // Rewrite:
        //   if (x == null) S1 else S2
        //     =>
        //   if (x) S2 else S1   (note the swapped branches)
        Branch branch = new Branch.loose(leftArg, falseCont, trueCont);
        replaceSubtree(node, branch);
        return;
      } else if (left.isNullConstant &&
                 lattice.isDefinitelyNotNumStringBool(right)) {
        Branch branch = new Branch.loose(rightArg, falseCont, trueCont);
        replaceSubtree(node, branch);
        return;
      } else if (right.isTrueConstant &&
                 lattice.isDefinitelyBool(left, allowNull: true)) {
        // Rewrite:
        //   if (x == true) S1 else S2
        //     =>
        //   if (x) S1 else S2
        Branch branch = new Branch.loose(leftArg, trueCont, falseCont);
        replaceSubtree(node, branch);
        return;
      } else if (left.isTrueConstant &&
                 lattice.isDefinitelyBool(right, allowNull: true)) {
        Branch branch = new Branch.loose(rightArg, trueCont, falseCont);
        replaceSubtree(node, branch);
        return;
      }
    }
  }

  void visitInvokeContinuation(InvokeContinuation node) {
    // Inline the single-use continuations. These are often introduced when
    // specializing an invocation node. These would also be inlined by a later
    // pass, but doing it here helps simplify pattern matching code, since the
    // effective definition of a primitive can then be found without going
    // through redundant InvokeContinuations.
    Continuation cont = node.continuation.definition;
    if (cont.hasExactlyOneUse &&
        !cont.isReturnContinuation &&
        !cont.isRecursive &&
        !node.isEscapingTry) {
      for (int i = 0; i < node.arguments.length; ++i) {
        node.arguments[i].definition.useElementAsHint(cont.parameters[i].hint);
        node.arguments[i].definition.substituteFor(cont.parameters[i]);
        node.arguments[i].unlink();
      }
      node.continuation.unlink();
      InteriorNode parent = node.parent;
      Expression body = cont.body;
      parent.body = body;
      body.parent = parent;
      cont.body = new Unreachable();
      cont.body.parent = cont;
      push(body);
    }
  }

  /// Returns the possible targets of [selector] when invoked on a receiver
  /// of type [receiverType].
  Iterable<Element> getAllTargets(TypeMask receiverType, Selector selector) {
    return compiler.world.allFunctions.filter(selector, receiverType);
  }

  /************************* CALL EXPRESSIONS *************************/

  /// Replaces [node] with a more specialized instruction, if possible.
  ///
  /// Returns `true` if the node was replaced.
  bool specializeOperatorCall(InvokeMethod node) {
    Continuation cont = node.continuation.definition;
    bool replaceWithBinary(BuiltinOperator operator,
                           Primitive left,
                           Primitive right) {
      Primitive prim =
          new ApplyBuiltinOperator(operator, <Primitive>[left, right],
                                   node.sourceInformation);
      LetPrim let = makeLetPrimInvoke(prim, cont);
      replaceSubtree(node, let);
      push(let);
      return true; // So returning early is more convenient.
    }

    if (node.selector.isOperator && node.arguments.length == 2) {
      Primitive leftArg = getDartReceiver(node);
      Primitive rightArg = getDartArgument(node, 0);
      AbstractValue left = getValue(leftArg);
      AbstractValue right = getValue(rightArg);

      String opname = node.selector.name;
      if (opname == '==') {
        // Equality is special due to its treatment of null values and the
        // fact that Dart-null corresponds to both JS-null and JS-undefined.
        // Please see documentation for IsFalsy, StrictEq, and LooseEq.
        if (left.isNullConstant || right.isNullConstant) {
          return replaceWithBinary(BuiltinOperator.Identical,
                                   leftArg, rightArg);
        }
        // There are several implementations of == that behave like identical.
        // Specialize it if we definitely call one of those.
        bool behavesLikeIdentical = true;
        for (Element target in getAllTargets(left.type, node.selector)) {
          ClassElement clazz = target.enclosingClass.declaration;
          if (clazz != compiler.world.objectClass &&
              clazz != backend.jsInterceptorClass &&
              clazz != backend.jsNullClass) {
            behavesLikeIdentical = false;
            break;
          }
        }
        if (behavesLikeIdentical) {
          return replaceWithBinary(BuiltinOperator.Identical,
                                   leftArg, rightArg);
        }
      } else {
        if (lattice.isDefinitelyNum(left, allowNull: false) &&
            lattice.isDefinitelyNum(right, allowNull: false)) {
          // Try to insert a numeric operator.
          BuiltinOperator operator = NumBinaryBuiltins[opname];
          if (operator != null) {
            return replaceWithBinary(operator, leftArg, rightArg);
          }
          // Try to insert a shift-left operator.
          // Shift operators are not in [NumBinaryBuiltins] because Dart shifts
          // behave different than JS shifts.
          // We do not introduce shift-right operators yet because the operator
          // to use depends on whether the left-hand operand is negative.
          // See js_number.dart in js_runtime for details.
          PrimitiveConstantValue rightConstant = right.constant;
          if (opname == '<<' &&
              lattice.isDefinitelyInt(left) &&
              rightConstant != null &&
              rightConstant.isInt &&
              rightConstant.primitiveValue >= 0 &&
              rightConstant.primitiveValue <= 31) {
            return replaceWithBinary(BuiltinOperator.NumShl,
                                     leftArg, rightArg);
          }
        }
        if (lattice.isDefinitelyString(left, allowNull: false) &&
            lattice.isDefinitelyString(right, allowNull: false) &&
            opname == '+') {
          return replaceWithBinary(BuiltinOperator.StringConcatenate,
                                   leftArg, rightArg);
        }
      }
    }
    // We should only get here if the node was not specialized.
    assert(node.parent != null);
    return false;
  }

  bool isInterceptedSelector(Selector selector) {
    return backend.isInterceptedSelector(selector);
  }

  Primitive getDartReceiver(InvokeMethod node) {
    if (node.receiverIsIntercepted) {
      return node.arguments[0].definition;
    } else {
      return node.receiver.definition;
    }
  }

  Primitive getDartArgument(InvokeMethod node, int n) {
    if (isInterceptedSelector(node.selector)) {
      return node.arguments[n+1].definition;
    } else {
      return node.arguments[n].definition;
    }
  }

  /// If [node] is a getter or setter invocation, tries to replace the
  /// invocation with a direct access to a field.
  ///
  /// Returns `true` if the node was replaced.
  bool specializeFieldAccess(InvokeMethod node) {
    if (!node.selector.isGetter && !node.selector.isSetter) return false;
    AbstractValue receiver = getValue(getDartReceiver(node));
    Element target =
        typeSystem.locateSingleElement(receiver.type, node.selector);
    if (target is! FieldElement) return false;
    // TODO(asgerf): Inlining native fields will make some tests pass for the
    // wrong reason, so for testing reasons avoid inlining them.
    if (target.isNative) return false;
    Continuation cont = node.continuation.definition;
    if (node.selector.isGetter) {
      GetField get = new GetField(getDartReceiver(node), target);
      LetPrim let = makeLetPrimInvoke(get, cont);
      replaceSubtree(node, let);
      push(let);
      return true;
    } else {
      if (target.isFinal) return false;
      assert(cont.parameters.single.hasNoUses);
      cont.parameters.clear();
      CpsFragment cps = new CpsFragment(node.sourceInformation);
      cps.letPrim(new SetField(getDartReceiver(node),
                               target,
                               getDartArgument(node, 0)));
      cps.invokeContinuation(cont);
      replaceSubtree(node, cps.result);
      push(cps.result);
      return true;
    }
  }

  /// Create a check that throws if [index] is not a valid index on [list].
  ///
  /// This function assumes that [index] is an integer.
  ///
  /// Returns a CPS fragment whose context is the branch where no error
  /// was thrown.
  CpsFragment makeBoundsCheck(Primitive list,
                              Primitive index,
                              SourceInformation sourceInfo) {
    CpsFragment cps = new CpsFragment(sourceInfo);
    Continuation fail = cps.letCont();
    Primitive isTooSmall = cps.applyBuiltin(
        BuiltinOperator.NumLt,
        <Primitive>[index, cps.makeZero()]);
    cps.ifTruthy(isTooSmall).invokeContinuation(fail);
    Primitive isTooLarge = cps.applyBuiltin(
        BuiltinOperator.NumGe,
        <Primitive>[index, cps.letPrim(new GetLength(list))]);
    cps.ifTruthy(isTooLarge).invokeContinuation(fail);
    cps.insideContinuation(fail).invokeStaticThrower(
        backend.getThrowIndexOutOfBoundsError(),
        <Primitive>[list, index]);
    return cps;
  }

  /// Create a check that throws if the length of [list] is not equal to
  /// [originalLength].
  ///
  /// Returns a CPS fragment whose context is the branch where no error
  /// was thrown.
  CpsFragment makeConcurrentModificationCheck(Primitive list,
                                              Primitive originalLength,
                                              SourceInformation sourceInfo) {
    CpsFragment cps = new CpsFragment(sourceInfo);
    Primitive lengthChanged = cps.applyBuiltin(
        BuiltinOperator.StrictNeq,
        <Primitive>[originalLength, cps.letPrim(new GetLength(list))]);
    cps.ifTruthy(lengthChanged).invokeStaticThrower(
        backend.getThrowConcurrentModificationError(),
        <Primitive>[list]);
    return cps;
  }

  /// Counts number of index accesses on [receiver] and determines based on
  /// that number if we should try to inline them.
  ///
  /// This is a short-term solution to avoid inserting a lot of bounds checks,
  /// since there is currently no optimization for eliminating them.
  bool hasTooManyIndexAccesses(Primitive receiver) {
    receiver = receiver.effectiveDefinition;
    int count = 0;
    for (Reference ref in receiver.effectiveUses) {
      Node use = ref.parent;
      if (use is InvokeMethod &&
          (use.selector.isIndex || use.selector.isIndexSet) &&
          getDartReceiver(use).sameValue(receiver)) {
        ++count;
      } else if (use is GetIndex && use.object.definition.sameValue(receiver)) {
        ++count;
      } else if (use is SetIndex && use.object.definition.sameValue(receiver)) {
        ++count;
      }
      if (count > 2) return true;
    }
    return false;
  }

  /// Tries to replace [node] with a direct `length` or index access.
  ///
  /// Returns `true` if the node was replaced.
  bool specializeIndexableAccess(InvokeMethod node) {
    Primitive receiver = getDartReceiver(node);
    AbstractValue receiverValue = getValue(receiver);
    if (!lattice.isDefinitelyIndexable(receiverValue)) return false;
    SourceInformation sourceInfo = node.sourceInformation;
    Continuation cont = node.continuation.definition;
    switch (node.selector.name) {
      case 'length':
        if (!node.selector.isGetter) return false;
        CpsFragment cps = new CpsFragment(sourceInfo);
        cps.invokeContinuation(cont, [cps.letPrim(new GetLength(receiver))]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case '[]':
        if (hasTooManyIndexAccesses(receiver)) return false;
        Primitive index = getDartArgument(node, 0);
        if (!lattice.isDefinitelyInt(getValue(index))) return false;
        CpsFragment cps = makeBoundsCheck(receiver, index, sourceInfo);
        GetIndex get = cps.letPrim(new GetIndex(receiver, index));
        cps.invokeContinuation(cont, [get]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      default:
        return false;
    }
  }

  /// Tries to replace [node] with one or more direct array access operations.
  ///
  /// Returns `true` if the node was replaced.
  bool specializeArrayAccess(InvokeMethod node) {
    Primitive list = getDartReceiver(node);
    AbstractValue listValue = getValue(list);
    // Ensure that the object is a native list or null.
    if (!lattice.isDefinitelyNativeList(listValue, allowNull: true)) {
      return false;
    }
    bool isFixedLength =
        lattice.isDefinitelyFixedNativeList(listValue, allowNull: true);
    bool isMutable =
        lattice.isDefinitelyMutableNativeList(listValue, allowNull: true);
    bool isExtendable =
        lattice.isDefinitelyExtendableNativeList(listValue, allowNull: true);
    SourceInformation sourceInfo = node.sourceInformation;
    Continuation cont = node.continuation.definition;
    switch (node.selector.name) {
      case 'add':
        if (!node.selector.isCall ||
            node.selector.positionalArgumentCount != 1 ||
            node.selector.namedArgumentCount != 0) {
          return false;
        }
        if (!isExtendable) return false;
        Primitive addedItem = getDartArgument(node, 0);
        CpsFragment cps = new CpsFragment(sourceInfo);
        cps.invokeBuiltin(BuiltinMethod.Push,
            list,
            <Primitive>[addedItem]);
        cps.invokeContinuation(cont, [cps.makeNull()]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case 'removeLast':
        if (!node.selector.isCall ||
            node.selector.argumentCount != 0) {
          return false;
        }
        if (!isExtendable) return false;
        CpsFragment cps = new CpsFragment(sourceInfo);
        Primitive length = cps.letPrim(new GetLength(list));
        Primitive isEmpty = cps.applyBuiltin(
            BuiltinOperator.StrictEq,
            [length, cps.makeZero()]);
        CpsFragment fail = cps.ifTruthy(isEmpty);
        fail.invokeStaticThrower(
            backend.getThrowIndexOutOfBoundsError(),
            [list, fail.makeConstant(new IntConstantValue(-1))]);
        Primitive removedItem = cps.invokeBuiltin(BuiltinMethod.Pop,
            list,
            <Primitive>[]);
        cps.invokeContinuation(cont, [removedItem]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case 'addAll':
        if (!node.selector.isCall ||
            node.selector.argumentCount != 1) {
          return false;
        }
        if (!isExtendable) return false;
        Primitive addedList = getDartArgument(node, 0);
        // Rewrite addAll([x1, ..., xN]) to push(x1, ..., xN).
        // Ensure that the list is not mutated between creation and use.
        // We aim for the common case where this is the only use of the list,
        // which also guarantees that this list is not mutated before use.
        if (addedList is! LiteralList || !addedList.hasExactlyOneUse) {
          return false;
        }
        LiteralList addedLiteral = addedList;
        CpsFragment cps = new CpsFragment(sourceInfo);
        cps.invokeBuiltin(BuiltinMethod.Push,
            list,
            addedLiteral.values.map((ref) => ref.definition).toList());
        cps.invokeContinuation(cont, [cps.makeNull()]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case 'elementAt':
        if (!node.selector.isCall ||
            node.selector.positionalArgumentCount != 1 ||
            node.selector.namedArgumentCount != 0) {
          return false;
        }
        if (listValue.isNullable) return false;
        if (hasTooManyIndexAccesses(list)) return false;
        Primitive index = getDartArgument(node, 0);
        if (!lattice.isDefinitelyInt(getValue(index))) return false;
        CpsFragment cps = makeBoundsCheck(list, index, sourceInfo);
        GetIndex get = cps.letPrim(new GetIndex(list, index));
        cps.invokeContinuation(cont, [get]);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case '[]=':
        if (listValue.isNullable) return false;
        if (hasTooManyIndexAccesses(list)) return false;
        Primitive index = getDartArgument(node, 0);
        Primitive value = getDartArgument(node, 1);
        if (!isMutable) return false;
        if (!lattice.isDefinitelyInt(getValue(index))) return false;
        CpsFragment cps = makeBoundsCheck(list, index, sourceInfo);
        cps.letPrim(new SetIndex(list, index, value));
        assert(cont.parameters.single.hasNoUses);
        cont.parameters.clear();
        cps.invokeContinuation(cont, []);
        replaceSubtree(node, cps.result);
        push(cps.result);
        return true;

      case 'forEach':
        Element element =
            compiler.world.locateSingleElement(node.selector, listValue.type);
        if (element == null ||
            !element.isFunction ||
            !node.selector.isCall) return false;
        assert(node.selector.positionalArgumentCount == 1);
        assert(node.selector.namedArgumentCount == 0);
        FunctionDefinition target = functionCompiler.compileToCpsIr(element);

        node.receiver.definition.substituteFor(target.thisParameter);
        for (int i = 0; i < node.arguments.length; ++i) {
          node.arguments[i].definition.substituteFor(target.parameters[i]);
        }
        node.continuation.definition.substituteFor(target.returnContinuation);

        replaceSubtree(node, target.body);
        push(target.body);
        return true;

      case 'iterator':
        if (!node.selector.isGetter) return false;
        Primitive iterator = cont.parameters.single;
        Continuation iteratorCont = cont;

        // Check that all uses of the iterator are 'moveNext' and 'current'.
        assert(!isInterceptedSelector(Selectors.moveNext));
        assert(!isInterceptedSelector(Selectors.current));
        for (Reference ref in iterator.effectiveUses) {
          if (ref.parent is! InvokeMethod) return false;
          InvokeMethod use = ref.parent;
          if (ref != use.receiver) return false;
          if (use.selector != Selectors.moveNext &&
              use.selector != Selectors.current) {
            return false;
          }
        }

        // Rewrite the iterator variable to 'current' and 'index' variables.
        Primitive originalLength = new GetLength(list);
        originalLength.hint = new OriginalLengthEntity();
        MutableVariable index = new MutableVariable(new LoopIndexEntity());
        MutableVariable current = new MutableVariable(new LoopItemEntity());

        // Rewrite all uses of the iterator.
        for (Reference ref in iterator.effectiveUses) {
          InvokeMethod use = ref.parent;
          Continuation useCont = use.continuation.definition;
          if (use.selector == Selectors.current) {
            // Rewrite iterator.current to a use of the 'current' variable.
            Parameter result = useCont.parameters.single;
            if (result.hint != null) {
              // If 'current' was originally moved into a named variable, use
              // that variable name for the mutable variable.
              current.hint = result.hint;
            }
            LetPrim let = makeLetPrimInvoke(new GetMutable(current), useCont);
            replaceSubtree(use, let);
          } else {
            assert (use.selector == Selectors.moveNext);
            // Rewrite iterator.moveNext() to:
            //
            //   if (index < list.length) {
            //     current = null;
            //     continuation(false);
            //   } else {
            //     current = list[index];
            //     index = index + 1;
            //     continuation(true);
            //   }
            //
            // (The above does not show concurrent modification checks)

            // [cps] contains the code we insert instead of moveNext().
            CpsFragment cps = new CpsFragment(node.sourceInformation);

            // We must check for concurrent modification when calling moveNext.
            // When moveNext is used as a loop condition, the check prevents
            // `index < list.length` from becoming the loop condition, and we
            // get code like this:
            //
            //    while (true) {
            //      if (originalLength !== list.length) throw;
            //      if (index < list.length) {
            //        ...
            //      } else {
            //        ...
            //        break;
            //      }
            //    }
            //
            // For loops, we therefore check for concurrent modification before
            // invoking the recursive continuation, so the loop becomes:
            //
            //    if (originalLength !== list.length) throw;
            //    while (index < list.length) {
            //      ...
            //      if (originalLength !== list.length) throw;
            //    }
            //
            // The check before the loop can often be eliminated because it
            // follows immediately after the 'iterator' call.
            InteriorNode parent = getEffectiveParent(use);
            if (!isFixedLength) {
              if (parent is Continuation && parent.isRecursive) {
                // Check for concurrent modification before every invocation
                // of the continuation.
                // TODO(asgerf): Do this in a continuation so multiple
                //               continues can share the same code.
                for (Reference ref = parent.firstRef;
                     ref != null;
                     ref = ref.next) {
                  Expression invocationCaller = ref.parent;
                  if (getEffectiveParent(invocationCaller) == iteratorCont) {
                    // No need to check for concurrent modification immediately
                    // after the call to 'iterator'.
                    continue;
                  }
                  CpsFragment check = makeConcurrentModificationCheck(
                      list, originalLength, sourceInfo);
                  insertBefore(invocationCaller, check);
                }
              } else {
                cps.append(makeConcurrentModificationCheck(
                    list, originalLength, sourceInfo));
              }
            }

            // Check if there are more elements.
            Primitive hasMore = cps.applyBuiltin(
                BuiltinOperator.NumLt,
                [cps.getMutable(index), cps.letPrim(new GetLength(list))]);

            // Return false if there are no more.
            CpsFragment falseBranch = cps.ifFalsy(hasMore);
            falseBranch
              ..setMutable(current, falseBranch.makeNull())
              ..invokeContinuation(useCont, [falseBranch.makeFalse()]);

            // Return true if there are more element.
            cps.setMutable(current,
                cps.letPrim(new GetIndex(list, cps.getMutable(index))));
            cps.setMutable(index, cps.applyBuiltin(
                BuiltinOperator.NumAdd,
                [cps.getMutable(index), cps.makeOne()]));
            cps.invokeContinuation(useCont, [cps.makeTrue()]);

            // Replace the moveNext() call. It will be visited later.
            replaceSubtree(use, cps.result);
          }
        }

        // All effective uses have been rewritten.
        destroyRefinementsOfDeadPrimitive(iterator);

        // Rewrite the iterator call to initializers for 'index' and 'current'.
        CpsFragment cps = new CpsFragment();
        cps.letMutable(index, cps.makeZero());
        cps.letMutable(current, cps.makeNull());
        cps.letPrim(originalLength);

        // Insert this fragment before the continuation body and replace the
        // iterator call with a call to the continuation without arguments.
        // For scoping reasons, the variables must be bound inside the
        // continuation, not at the invocation-site.
        iteratorCont.parameters.clear();
        insertBefore(iteratorCont.body, cps);
        InvokeContinuation invoke = new InvokeContinuation(iteratorCont, []);
        replaceSubtree(node, invoke);
        push(invoke);
        return true;

      default:
        return false;
    }
  }

  /// If [prim] is the parameter to a call continuation, returns the
  /// corresponding call.
  CallExpression getCallWithResult(Primitive prim) {
    if (prim is Parameter && prim.parent is Continuation) {
      Continuation cont = prim.parent;
      if (cont.hasExactlyOneUse) {
        Node use = cont.firstRef.parent;
        if (use is CallExpression) {
          return use;
        }
      }
    }
    return null;
  }

  /// Returns the first parent of [node] that is not a pure expression.
  InteriorNode getEffectiveParent(Expression node) {
    while (true) {
      Node parent = node.parent;
      if (parent is LetCont ||
          parent is LetPrim && parent.primitive.isSafeForReordering ||
          parent is LetPrim && parent.primitive is Refinement) {
        node = parent;
      } else {
        return parent;
      }
    }
  }

  /// Rewrites an invocation of a torn-off method into a method call directly
  /// on the receiver. For example:
  ///
  ///     obj.get$foo().call$<n>(<args>)
  ///       =>
  ///     obj.foo$<n>(<args>)
  ///
  bool specializeClosureCall(InvokeMethod node) {
    Selector call = node.selector;
    if (!call.isClosureCall) return false;

    assert(!isInterceptedSelector(call));
    assert(call.argumentCount == node.arguments.length);

    Primitive tearOff = node.receiver.definition.effectiveDefinition;
    // Note: We don't know if [tearOff] is actually a tear-off.
    // We name variables based on the pattern we are trying to match.

    if (tearOff is GetStatic && tearOff.element.isFunction) {
      FunctionElement target = tearOff.element;
      FunctionSignature signature = target.functionSignature;

      // If the selector does not apply, don't bother (will throw at runtime).
      if (!call.signatureApplies(target)) return false;

      // If some optional arguments are missing, give up.
      // TODO(asgerf): Improve optimization by inserting default arguments.
      if (call.argumentCount != signature.parameterCount) return false;

      InvokeStatic invoke = new InvokeStatic.byReference(
          target,
          new Selector.fromElement(target),
          node.arguments,
          node.continuation,
          node.sourceInformation);
      node.receiver.unlink();
      replaceSubtree(node, invoke, unlink: false);
      push(invoke);
      return true;
    }
    CallExpression tearOffInvoke = getCallWithResult(tearOff);
    if (tearOffInvoke is InvokeMethod && tearOffInvoke.selector.isGetter) {
      Selector getter = tearOffInvoke.selector;

      // TODO(asgerf): Support torn-off intercepted methods.
      if (isInterceptedSelector(getter)) return false;

      Continuation getterCont = tearOffInvoke.continuation.definition;

      Primitive object = tearOffInvoke.receiver.definition;

      // Ensure that the object actually has a foo member, since we might
      // otherwise alter a noSuchMethod call.
      TypeMask type = getValue(object).type;
      if (typeSystem.needsNoSuchMethodHandling(type, getter)) return false;

      // Determine if the getter invocation can have side-effects.
      Element element = typeSystem.locateSingleElement(type, getter);
      bool isPure = element != null && !element.isGetter;

      // If there are multiple uses, we cannot eliminate the getter call and
      // therefore risk duplicating its side effects.
      if (!isPure && tearOff.hasMultipleEffectiveUses) return false;

      // If the getter call is impure, we risk reordering side effects.
      if (!isPure && getEffectiveParent(node) != getterCont) {
        return false;
      }

      InvokeMethod invoke = new InvokeMethod.byReference(
        new Reference<Primitive>(object),
        new Selector.call(getter.memberName, call.callStructure),
        type,
        node.arguments,
        node.continuation,
        node.sourceInformation);
      node.receiver.unlink();
      replaceSubtree(node, invoke, unlink: false);

      if (tearOff.hasNoEffectiveUses) {
        // Eliminate the getter call if it has no more uses.
        // This cannot be delegated to other optimizations because we need to
        // avoid duplication of side effects.
        destroyRefinementsOfDeadPrimitive(tearOff);
        getterCont.parameters.clear();
        replaceSubtree(tearOffInvoke, new InvokeContinuation(getterCont, []));
      } else {
        // There are more uses, so we cannot eliminate the getter call. This
        // means we duplicated the effects of the getter call, but we should
        // only get here if the getter has no side effects.
        assert(isPure);
      }

      push(invoke);
      return true;
    }
    return false;
  }

  void destroyRefinementsOfDeadPrimitive(Primitive prim) {
    while (prim.firstRef != null) {
      Refinement refine = prim.firstRef.parent;
      destroyRefinementsOfDeadPrimitive(refine);
      LetPrim letPrim = refine.parent;
      InteriorNode parent = letPrim.parent;
      parent.body = letPrim.body;
      letPrim.body.parent = parent;
      prim.firstRef.unlink();
    }
  }

  /// Inlines a single-use closure if it leaves the closure object with only
  /// field accesses.  This is optimized later by [ScalarReplacer].
  bool specializeSingleUseClosureCall(InvokeMethod node) {
    Selector call = node.selector;
    if (!call.isClosureCall) return false;

    assert(!isInterceptedSelector(call));
    assert(call.argumentCount == node.arguments.length);

    Primitive receiver = node.receiver.definition;
    if (receiver is !CreateInstance) return false;
    CreateInstance createInstance = receiver;
    if (!createInstance.hasExactlyOneUse) return false;

    // Inline only closures. This avoids inlining the 'call' method of a class
    // that has many allocation sites.
    if (createInstance.classElement is !ClosureClassElement) return false;

    ClosureClassElement closureClassElement = createInstance.classElement;
    Element element = closureClassElement.localLookup(Identifiers.call);

    if (element == null || !element.isFunction) return false;
    FunctionElement functionElement = element;
    if (functionElement.asyncMarker != AsyncMarker.SYNC) return false;

    if (!call.signatureApplies(functionElement)) return false;
    // Inline only for exact match.
    // TODO(sra): Handle call with defaulted arguments.
    Selector targetSelector = new Selector.fromElement(functionElement);
    if (call.callStructure != targetSelector.callStructure) return false;

    // Don't inline if [target] contains try-catch or try-finally. JavaScript
    // engines typically do poor optimization of the entire function containing
    // the 'try'.
    if (functionElement.resolvedAst.elements.containsTryStatement) return false;

    FunctionDefinition target =
        functionCompiler.compileToCpsIr(functionElement);

    // Accesses to closed-over values are field access primitives.  We we don't
    // inline if there are other uses of 'this' since that could be an escape or
    // a recursive call.
    for (Reference ref = target.thisParameter.firstRef;
         ref != null;
         ref = ref.next) {
      Node use = ref.parent;
      if (use is GetField) continue;
      // Closures do not currently have writable fields, but closure conversion
      // could esily be changed to allocate some cells in a closure object.
      if (use is SetField && ref == use.object) continue;
      return false;
    }

    node.receiver.definition.substituteFor(target.thisParameter);
    for (int i = 0; i < node.arguments.length; ++i) {
      node.arguments[i].definition.substituteFor(target.parameters[i]);
    }
    node.continuation.definition.substituteFor(target.returnContinuation);

    replaceSubtree(node, target.body);
    push(target.body);
    return true;
  }

  /// Side-effect free expressions with constant results are be replaced by:
  ///
  ///    (LetPrim p = constant (InvokeContinuation k p)).
  ///
  /// The new expression will be visited.
  ///
  /// Returns true if the node was replaced.
  bool constifyExpression(CallExpression node) {
    Continuation continuation = node.continuation.definition;
    ConstantValue constant = replacements[node];
    if (constant == null) return false;
    Constant primitive = makeConstantPrimitive(constant);
    LetPrim letPrim = makeLetPrimInvoke(primitive, continuation);
    replaceSubtree(node, letPrim);
    push(letPrim);
    return true;
  }

  void visitInvokeMethod(InvokeMethod node) {
    if (constifyExpression(node)) return;
    if (specializeOperatorCall(node)) return;
    if (specializeFieldAccess(node)) return;
    if (specializeIndexableAccess(node)) return;
    if (specializeArrayAccess(node)) return;
    if (specializeSingleUseClosureCall(node)) return;
    if (specializeClosureCall(node)) return;

    AbstractValue receiver = getValue(node.receiver.definition);

    if (node.receiverIsIntercepted &&
        node.receiver.definition.sameValue(node.arguments[0].definition)) {
      // The receiver and first argument are the same; that means we already
      // determined in visitInterceptor that we are targeting a non-interceptor.

      // Check if any of the possible targets depend on the extra receiver
      // argument. Mixins do this, and tear-offs always needs the extra receiver
      // argument because BoundClosure uses it for equality and hash code.
      // TODO(15933): Make automatically generated property extraction
      // closures work with the dummy receiver optimization.
      bool needsReceiver(Element target) {
        if (target is! FunctionElement) return false;
        FunctionElement function = target;
        return typeSystem.methodUsesReceiverArgument(function) ||
               node.selector.isGetter && !function.isGetter;
      }
      if (!getAllTargets(receiver.type, node.selector).any(needsReceiver)) {
        // Replace the extra receiver argument with a dummy value if the
        // target definitely does not use it.
        Constant dummy = makeConstantPrimitive(new IntConstantValue(0));
        insertLetPrim(node, dummy);
        node.arguments[0].unlink();
        node.arguments[0] = new Reference<Primitive>(dummy);
        node.receiverIsIntercepted = false;
      }
    }
  }

  void visitTypeCast(TypeCast node) {
    Continuation cont = node.continuation.definition;

    AbstractValue value = getValue(node.value.definition);
    switch (lattice.isSubtypeOf(value, node.dartType, allowNull: true)) {
      case AbstractBool.Maybe:
      case AbstractBool.Nothing:
        break;

      case AbstractBool.True:
        // Cast always succeeds, replace it with InvokeContinuation.
        InvokeContinuation invoke =
            new InvokeContinuation(cont, <Primitive>[node.value.definition]);
        replaceSubtree(node, invoke);
        push(invoke);
        return;

      case AbstractBool.False:
        // Cast always fails, remove unreachable continuation body.
        replaceSubtree(cont.body, new Unreachable());
        break;
    }
  }

  /// Specialize calls to internal static methods.
  ///
  /// Returns true if the call was replaced.
  bool specializeInternalMethodCall(InvokeStatic node) {
    // TODO(asgerf): This is written to easily scale to more cases,
    //               either add more cases or clean up.
    Continuation cont = node.continuation.definition;
    Primitive arg(int n) => node.arguments[n].definition;
    AbstractValue argType(int n) => getValue(arg(n));

    bool replaceWithBinary(BuiltinOperator operator,
                           Primitive left,
                           Primitive right) {
      Primitive prim =
          new ApplyBuiltinOperator(operator, <Primitive>[left, right],
                                   node.sourceInformation);
      LetPrim let = makeLetPrimInvoke(prim, cont);
      replaceSubtree(node, let);
      push(let);
      return true; // So returning early is more convenient.
    }

    if (node.target.library.isInternalLibrary) {
      switch(node.target.name) {
        case InternalMethod.Stringify:
          if (lattice.isDefinitelyString(argType(0))) {
            InvokeContinuation invoke =
                new InvokeContinuation(cont, <Primitive>[arg(0)]);
            replaceSubtree(node, invoke);
            push(invoke);
            return true;
          }
          break;
      }
    } else if (node.target.library.isDartCore) {
      switch(node.target.name) {
        case CorelibMethod.Identical:
          if (node.arguments.length == 2) {
            return replaceWithBinary(BuiltinOperator.Identical, arg(0), arg(1));
          }
          break;
      }
    }
    return false;
  }

  /// Try to inline static invocations.
  ///
  /// Performs the inlining and returns true if the call was inlined.  Inlining
  /// uses a fixed heuristic:
  ///
  /// * Inline functions with a single expression statement or return statement
  /// provided that the subexpression is an invocation of foreign code.
  bool inlineInvokeStatic(InvokeStatic node) {
    // The target might not have an AST, for example if it deferred.
    if (!node.target.hasNode) return false;

    // True if an expression is non-expansive, in the sense defined by this
    // predicate.
    bool isNonExpansive(ast.Expression expr) {
      if (expr is ast.LiteralNull ||
          expr is ast.LiteralBool ||
          expr is ast.LiteralInt ||
          expr is ast.LiteralDouble) {
        return true;
      }
      if (expr is ast.Send) {
        SendStructure structure =
            node.target.treeElements.getSendStructure(expr);
        if (structure is InvokeStructure) {
          // Calls to foreign functions.
          return structure.semantics.kind == AccessKind.TOPLEVEL_METHOD &&
              backend.isForeign(structure.semantics.element);
        } else if (structure is IsStructure || structure is IsNotStructure) {
          // is and is! checks on nonexpansive expressions.
          return isNonExpansive(expr.receiver);
        } else if (structure is EqualsStructure ||
            structure is NotEqualsStructure) {
          // == and != on nonexpansive expressions.
          return isNonExpansive(expr.receiver) &&
              isNonExpansive(expr.argumentsNode.nodes.head);
        } else if (structure is GetStructure) {
          // Parameters.
          return structure.semantics.kind == AccessKind.PARAMETER;
        }
      }
      return false;
    }

    ast.Statement body = node.target.node.body;
    bool shouldInline() {
      if (backend.annotations.noInline(node.target)) return false;
      if (node.target.resolvedAst.elements.containsTryStatement) return false;

      // Inline functions that are a single return statement, expression
      // statement, or block containing a return statement or expression
      // statement.
      if (body is ast.Return) {
        return isNonExpansive(body.expression);
      } else if (body is ast.ExpressionStatement) {
        return isNonExpansive(body.expression);
      } else if (body is ast.Block) {
        var link = body.statements.nodes;
        if (link.isNotEmpty && link.tail.isEmpty) {
          if (link.head is ast.Return) {
            return isNonExpansive(link.head.expression);
          } else if (link.head is ast.ExpressionStatement) {
            return isNonExpansive(link.head.expression);
          }
        }
      }
      return false;
    }

    if (!shouldInline()) return false;

    FunctionDefinition target = functionCompiler.compileToCpsIr(node.target);
    for (int i = 0; i < node.arguments.length; ++i) {
      node.arguments[i].definition.substituteFor(target.parameters[i]);
    }
    node.continuation.definition.substituteFor(target.returnContinuation);

    replaceSubtree(node, target.body);
    push(target.body);
    return true;
  }

  void visitInvokeStatic(InvokeStatic node) {
    if (constifyExpression(node)) return;
    if (specializeInternalMethodCall(node)) return;
    if (inlineInvokeStatic(node)) return;
  }

  AbstractValue getValue(Variable node) {
    ConstantValue constant = values[node];
    if (constant != null) {
      return new AbstractValue.constantValue(constant, node.type);
    }
    if (node.type != null) {
      return new AbstractValue.nonConstant(node.type);
    }
    return lattice.nothing;
  }


  /*************************** PRIMITIVES **************************/
  //
  // The visit method for a primitive may optionally return a new
  // primitive. If non-null, the surrounding LetPrim will substitute it
  // and bind the new primitive instead.
  //

  void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
    ast.DartString getString(AbstractValue value) {
      StringConstantValue constant = value.constant;
      return constant.primitiveValue;
    }
    switch (node.operator) {
      case BuiltinOperator.StringConcatenate:
        // Concatenate consecutive constants.
        bool argumentsWereRemoved = false;
        int i = 0;
        while (i < node.arguments.length - 1) {
          int startOfSequence = i;
          AbstractValue firstValue = getValue(node.arguments[i++].definition);
          if (!firstValue.isConstant) continue;
          AbstractValue secondValue = getValue(node.arguments[i++].definition);
          if (!secondValue.isConstant) continue;

          ast.DartString string =
              new ast.ConsDartString(getString(firstValue),
                                     getString(secondValue));

          // We found a sequence of at least two constants.
          // Look for the end of the sequence.
          while (i < node.arguments.length) {
            AbstractValue value = getValue(node.arguments[i].definition);
            if (!value.isConstant) break;
            string = new ast.ConsDartString(string, getString(value));
            ++i;
          }
          Constant prim =
              makeConstantPrimitive(new StringConstantValue(string));
          insertLetPrim(node.parent, prim);
          for (int k = startOfSequence; k < i; ++k) {
            node.arguments[k].unlink();
            node.arguments[k] = null; // Remove the argument after the loop.
          }
          node.arguments[startOfSequence] = new Reference<Primitive>(prim);
          node.arguments[startOfSequence].parent = node;
          argumentsWereRemoved = true;
        }
        if (argumentsWereRemoved) {
          node.arguments.removeWhere((ref) => ref == null);
        }
        // TODO(asgerf): Rebalance nested StringConcats that arise from
        //               rewriting the + operator to StringConcat.
        break;

      case BuiltinOperator.Identical:
        Primitive leftArg = node.arguments[0].definition;
        Primitive rightArg = node.arguments[1].definition;
        AbstractValue left = getValue(leftArg);
        AbstractValue right = getValue(rightArg);
        if (lattice.isDefinitelyBool(left) &&
            right.isConstant &&
            right.constant.isTrue) {
          // Replace identical(x, true) by x when x is known to be a boolean.
          // Note that this is not safe if x is null, because the value might
          // not be used as a condition. A rule for [IsTrue] handles that case.
          leftArg.substituteFor(node);
        } else if (lattice.isDefinitelyBool(right) &&
            left.isConstant &&
            left.constant.isTrue) {
          rightArg.substituteFor(node);
        } else if (left.isNullConstant || right.isNullConstant) {
          // Use `==` for comparing against null, so JS undefined and JS null
          // are considered equal.
          node.operator = BuiltinOperator.LooseEq;
        } else if (!left.isNullable || !right.isNullable) {
          // If at most one operand can be Dart null, we can use `===`.
          // This is not safe when we might compare JS null and JS undefined.
          node.operator = BuiltinOperator.StrictEq;
        } else if (lattice.isDefinitelyNum(left, allowNull: true) &&
                   lattice.isDefinitelyNum(right, allowNull: true)) {
          // If both operands can be null, but otherwise are of the same type,
          // we can use `==` for comparison.
          // This is not safe e.g. for comparing strings against numbers.
          node.operator = BuiltinOperator.LooseEq;
        } else if (lattice.isDefinitelyString(left, allowNull: true) &&
                   lattice.isDefinitelyString(right, allowNull: true)) {
          node.operator = BuiltinOperator.LooseEq;
        } else if (lattice.isDefinitelyBool(left, allowNull: true) &&
                   lattice.isDefinitelyBool(right, allowNull: true)) {
          node.operator = BuiltinOperator.LooseEq;
        }
        break;

      default:
    }
  }

  void visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
    if (node.method == BuiltinMethod.Push) {
      // Convert consecutive pushes into a single push.
      InteriorNode parent = getEffectiveParent(node.parent);
      if (parent is LetPrim && parent.primitive is ApplyBuiltinMethod) {
        ApplyBuiltinMethod previous = parent.primitive;
        if (previous.method == BuiltinMethod.Push &&
            previous.receiver.definition.sameValue(node.receiver.definition)) {
          // We found two consecutive pushes.
          // Move all arguments from the first push onto the second one.
          List<Reference<Primitive>> arguments = previous.arguments;
          for (Reference ref in arguments) {
            ref.parent = node;
          }
          arguments.addAll(node.arguments);
          node.arguments = arguments;
          // Elimnate the old push.
          previous.receiver.unlink();
          assert(previous.hasNoUses);
          parent.parent.body = parent.body;
          parent.body.parent = parent.parent;
        }
      }
    }
  }

  Primitive visitTypeTest(TypeTest node) {
    Primitive prim = node.value.definition;
    AbstractValue value = getValue(prim);
    if (node.dartType == dartTypes.coreTypes.intType) {
      // Compile as typeof x === 'number' && Math.floor(x) === x
      if (lattice.isDefinitelyNum(value, allowNull: true)) {
        // If value is null or a number, we can skip the typeof test.
        return new ApplyBuiltinOperator(
            BuiltinOperator.IsFloor,
            <Primitive>[prim, prim],
            node.sourceInformation);
      }
      if (lattice.isDefinitelyNotNonIntegerDouble(value)) {
        // If the value cannot be a non-integer double, but might not be a
        // number at all, we can skip the Math.floor test.
        return new ApplyBuiltinOperator(
            BuiltinOperator.IsNumber,
            <Primitive>[prim],
            node.sourceInformation);
      }
      return new ApplyBuiltinOperator(
          BuiltinOperator.IsNumberAndFloor,
          <Primitive>[prim, prim, prim],
          node.sourceInformation);
    }
    if (node.dartType == dartTypes.coreTypes.numType ||
        node.dartType == dartTypes.coreTypes.doubleType) {
      return new ApplyBuiltinOperator(
          BuiltinOperator.IsNumber,
          <Primitive>[prim],
          node.sourceInformation);
    }
    return null;
  }

  Primitive visitInterceptor(Interceptor node) {
    AbstractValue value = getValue(node.input.definition);
    // If the exact class of the input is known, replace with a constant
    // or the input itself.
    ClassElement singleClass;
    if (lattice.isDefinitelyInt(value)) {
      // Classes like JSUInt31 and JSUInt32 do not exist at runtime, so ensure
      // all the int classes get mapped tor their runtime class.
      singleClass = backend.jsIntClass;
    } else if (lattice.isDefinitelyNativeList(value)) {
      // Ensure all the array subclasses get mapped to the array class.
      singleClass = backend.jsArrayClass;
    } else {
      singleClass = typeSystem.singleClass(value.type);
    }
    if (singleClass != null &&
        singleClass.isSubclassOf(backend.jsInterceptorClass)) {
      node.constantValue = new InterceptorConstantValue(singleClass.rawType);
    }
    // Filter out intercepted classes that do not match the input type.
    node.interceptedClasses.retainWhere((ClassElement clazz) {
      if (clazz == typeSystem.jsNullClass) {
        return value.isNullable;
      } else {
        TypeMask classMask = typeSystem.nonNullSubclass(clazz);
        return !typeSystem.areDisjoint(value.type, classMask);
      }
    });
    // Remove the interceptor call if it can only return its input.
    if (node.interceptedClasses.isEmpty) {
      node.input.definition.substituteFor(node);
    }
    return null;
  }
}

/**
 * Runs an analysis pass on the given function definition in order to detect
 * const-ness as well as reachability, both of which are used in the subsequent
 * transformation pass.
 */
class TypePropagationVisitor implements Visitor {
  // The node worklist stores nodes that are both reachable and need to be
  // processed, but have not been processed yet. Using a worklist avoids deep
  // recursion.
  // The node worklist and the reachable set operate in concert: nodes are
  // only ever added to the worklist when they have not yet been marked as
  // reachable, and adding a node to the worklist is always followed by marking
  // it reachable.
  // TODO(jgruber): Storing reachability per-edge instead of per-node would
  // allow for further optimizations.
  final List<Node> nodeWorklist = <Node>[];
  final Set<Continuation> reachableContinuations = new Set<Continuation>();

  // The definition workset stores all definitions which need to be reprocessed
  // since their lattice value has changed.
  final List<Definition> defWorklist = <Definition>[];

  final ConstantPropagationLattice lattice;
  final dart2js.InternalErrorFunction internalError;

  TypeMaskSystem get typeSystem => lattice.typeSystem;

  JavaScriptBackend get backend => typeSystem.backend;

  World get classWorld => typeSystem.classWorld;

  AbstractValue get nothing => lattice.nothing;

  AbstractValue nonConstant([TypeMask type]) => lattice.nonConstant(type);

  AbstractValue constantValue(ConstantValue constant, [TypeMask type]) {
    return lattice.constant(constant, type);
  }

  // Stores the current lattice value for primitives and mutable variables.
  // Access through [getValue] and [setValue].
  final Map<Variable, ConstantValue> values;

  /// Expressions that invoke their call continuation with a constant value
  /// and without any side effects. These can be replaced by the constant.
  final Map<Expression, ConstantValue> replacements;

  TypePropagationVisitor(this.lattice,
                         this.values,
                         this.replacements,
                         this.internalError);

  void analyze(FunctionDefinition root) {
    reachableContinuations.clear();

    // Initially, only the root node is reachable.
    push(root);

    iterateWorklist();
  }

  void reanalyzeSubtree(Node node) {
    new ResetAnalysisInfo(reachableContinuations, values).visit(node);
    push(node);
    iterateWorklist();
  }

  void iterateWorklist() {
    while (true) {
      if (nodeWorklist.isNotEmpty) {
        // Process a new reachable expression.
        Node node = nodeWorklist.removeLast();
        visit(node);
      } else if (defWorklist.isNotEmpty) {
        // Process all usages of a changed definition.
        Definition def = defWorklist.removeLast();

        // Visit all uses of this definition. This might add new entries to
        // [nodeWorklist], for example by visiting a newly-constant usage within
        // a branch node.
        for (Reference ref = def.firstRef; ref != null; ref = ref.next) {
          visit(ref.parent);
        }
      } else {
        break;  // Both worklists empty.
      }
    }
  }

  /// Adds [node] to the worklist.
  void push(Node node) {
    nodeWorklist.add(node);
  }

  /// If the passed node is not yet reachable, mark it reachable and add it
  /// to the work list.
  void setReachable(Continuation cont) {
    if (reachableContinuations.add(cont)) {
      push(cont);
    }
  }

  /// Returns the lattice value corresponding to [node], defaulting to nothing.
  ///
  /// Never returns null.
  AbstractValue getValue(Variable node) {
    ConstantValue constant = values[node];
    if (constant != null) {
      return new AbstractValue.constantValue(constant, node.type);
    }
    if (node.type != null) {
      return new AbstractValue.nonConstant(node.type);
    }
    return lattice.nothing;
  }

  /// Joins the passed lattice [updateValue] to the current value of [node],
  /// and adds it to the definition work set if it has changed and [node] is
  /// a definition.
  void setValue(Variable node, AbstractValue updateValue) {
    AbstractValue oldValue = getValue(node);
    AbstractValue newValue = lattice.join(oldValue, updateValue);
    node.type = newValue.type; // Ensure type is initialized even if bottom.
    if (oldValue == newValue) {
      return;
    }

    // Values may only move in the direction NOTHING -> CONSTANT -> NONCONST.
    assert(newValue.kind >= oldValue.kind);

    values[node] = newValue.isConstant ? newValue.constant : null;
    defWorklist.add(node);
  }

  /// Updates the value of a [CallExpression]'s continuation parameter.
  void setResult(CallExpression call,
                 AbstractValue updateValue,
                 {bool canReplace: false}) {
    Continuation cont = call.continuation.definition;
    setValue(cont.parameters.single, updateValue);
    if (!updateValue.isNothing) {
      setReachable(cont);

      if (updateValue.isConstant && canReplace) {
        replacements[call] = updateValue.constant;
      } else {
        // A replacement might have been set in a previous iteration.
        replacements.remove(call);
      }
    }
  }

  bool isInterceptedSelector(Selector selector) {
    return backend.isInterceptedSelector(selector);
  }

  Primitive getDartReceiver(InvokeMethod node) {
    if (node.receiverIsIntercepted) {
      return node.arguments[0].definition;
    } else {
      return node.receiver.definition;
    }
  }

  Primitive getDartArgument(InvokeMethod node, int n) {
    if (isInterceptedSelector(node.selector)) {
      return node.arguments[n+1].definition;
    } else {
      return node.arguments[n].definition;
    }
  }

  // -------------------------- Visitor overrides ------------------------------
  void visit(Node node) { node.accept(this); }

  void visitFunctionDefinition(FunctionDefinition node) {
    int firstActualParameter = 0;
    if (backend.isInterceptedMethod(node.element)) {
      if (typeSystem.methodUsesReceiverArgument(node.element)) {
        setValue(node.thisParameter, nonConstant(typeSystem.nonNullType));
        setValue(node.parameters[0],
                 nonConstant(typeSystem.getReceiverType(node.element)));
      } else {
        setValue(node.thisParameter,
              nonConstant(typeSystem.getReceiverType(node.element)));
        setValue(node.parameters[0], nonConstant());
      }
      firstActualParameter = 1;
    } else if (node.thisParameter != null) {
      setValue(node.thisParameter,
               nonConstant(typeSystem.getReceiverType(node.element)));
    }
    for (Parameter param in node.parameters.skip(firstActualParameter)) {
      // TODO(karlklose): remove reference to the element model.
      TypeMask type = param.hint is ParameterElement
          ? typeSystem.getParameterType(param.hint)
          : typeSystem.dynamicType;
      setValue(param, lattice.fromMask(type));
    }
    push(node.body);
  }

  void visitLetPrim(LetPrim node) {
    visit(node.primitive); // No reason to delay visits to primitives.
    push(node.body);
  }

  void visitLetCont(LetCont node) {
    // The continuation is only marked as reachable on use.
    push(node.body);
  }

  void visitLetHandler(LetHandler node) {
    push(node.body);
    // The handler is assumed to be reachable (we could instead treat it as
    // unreachable unless we find something reachable that might throw in the
    // body --- it's not clear if we want to do that here or in some other
    // pass).  The handler parameters are assumed to be unknown.
    //
    // TODO(kmillikin): we should set the type of the exception and stack
    // trace here.  The way we do that depends on how we handle 'on T' catch
    // clauses.
    setReachable(node.handler);
    for (Parameter param in node.handler.parameters) {
      setValue(param, nonConstant());
    }
  }

  void visitLetMutable(LetMutable node) {
    setValue(node.variable, getValue(node.value.definition));
    push(node.body);
  }

  void visitInvokeStatic(InvokeStatic node) {
    if (node.target.library != null && node.target.library.isInternalLibrary) {
      switch (node.target.name) {
        case InternalMethod.Stringify:
          AbstractValue argValue = getValue(node.arguments[0].definition);
          setResult(node, lattice.stringify(argValue), canReplace: true);
          return;
      }
    }

    TypeMask returnType = typeSystem.getReturnType(node.target);
    setResult(node, lattice.fromMask(returnType));
  }

  void visitInvokeContinuation(InvokeContinuation node) {
    Continuation cont = node.continuation.definition;
    setReachable(cont);

    // Forward the constant status of all continuation invokes to the
    // continuation. Note that this is effectively a phi node in SSA terms.
    for (int i = 0; i < node.arguments.length; i++) {
      Primitive def = node.arguments[i].definition;
      AbstractValue cell = getValue(def);
      setValue(cont.parameters[i], cell);
    }
  }

  void visitInvokeMethod(InvokeMethod node) {
    AbstractValue receiver = getValue(node.receiver.definition);
    node.receiverIsNotNull = receiver.isDefinitelyNotNull;
    if (receiver.isNothing) {
      return;  // And come back later.
    }
    if (!node.selector.isOperator) {
      // TODO(jgruber): Handle known methods on constants such as String.length.
      setResult(node, lattice.getInvokeReturnType(node.selector, node.mask));
      return;
    }

    // Calculate the resulting constant if possible.
    AbstractValue result;
    String opname = node.selector.name;
    if (node.arguments.length == 1) {
      AbstractValue argument = getValue(getDartReceiver(node));
      // Unary operator.
      if (opname == "unary-") {
        opname = "-";
      }
      UnaryOperator operator = UnaryOperator.parse(opname);
      result = lattice.unaryOp(operator, argument);
    } else if (node.arguments.length == 2) {
      // Binary operator.
      AbstractValue left = getValue(getDartReceiver(node));
      AbstractValue right = getValue(getDartArgument(node, 0));
      BinaryOperator operator = BinaryOperator.parse(opname);
      result = lattice.binaryOp(operator, left, right);
    }

    // Update value of the continuation parameter. Again, this is effectively
    // a phi.
    if (result == null) {
      setResult(node, lattice.getInvokeReturnType(node.selector, node.mask));
    } else {
      setResult(node, result, canReplace: true);
    }
  }

  void visitApplyBuiltinOperator(ApplyBuiltinOperator node) {
    switch (node.operator) {
      case BuiltinOperator.StringConcatenate:
        ast.DartString stringValue = const ast.LiteralDartString('');
        for (Reference<Primitive> arg in node.arguments) {
          AbstractValue value = getValue(arg.definition);
          if (value.isNothing) {
            return; // And come back later
          } else if (value.isConstant &&
                     value.constant.isString &&
                     stringValue != null) {
            StringConstantValue constant = value.constant;
            stringValue =
                new ast.ConsDartString(stringValue, constant.primitiveValue);
          } else {
            stringValue = null;
            break;
          }
        }
        if (stringValue == null) {
          setValue(node, nonConstant(typeSystem.stringType));
        } else {
          setValue(node, constantValue(new StringConstantValue(stringValue)));
        }
        break;

      case BuiltinOperator.Identical:
      case BuiltinOperator.StrictEq:
      case BuiltinOperator.LooseEq:
        AbstractValue leftConst = getValue(node.arguments[0].definition);
        AbstractValue rightConst = getValue(node.arguments[1].definition);
        ConstantValue leftValue = leftConst.constant;
        ConstantValue rightValue = rightConst.constant;
        if (leftConst.isNothing || rightConst.isNothing) {
          // Come back later.
          return;
        } else if (!leftConst.isConstant || !rightConst.isConstant) {
          TypeMask leftType = leftConst.type;
          TypeMask rightType = rightConst.type;
          if (typeSystem.areDisjoint(leftType, rightType)) {
            setValue(node,
                constantValue(new FalseConstantValue(), typeSystem.boolType));
          } else {
            setValue(node, nonConstant(typeSystem.boolType));
          }
          return;
        } else if (leftValue.isPrimitive && rightValue.isPrimitive) {
          assert(leftConst.isConstant && rightConst.isConstant);
          PrimitiveConstantValue left = leftValue;
          PrimitiveConstantValue right = rightValue;
          ConstantValue result =
            new BoolConstantValue(left.primitiveValue == right.primitiveValue);
          setValue(node, constantValue(result, typeSystem.boolType));
        } else {
          setValue(node, nonConstant(typeSystem.boolType));
        }
        break;

      // TODO(asgerf): Implement constant propagation for builtins.
      case BuiltinOperator.NumAdd:
      case BuiltinOperator.NumSubtract:
      case BuiltinOperator.NumMultiply:
      case BuiltinOperator.NumAnd:
      case BuiltinOperator.NumOr:
      case BuiltinOperator.NumXor:
      case BuiltinOperator.NumShl:
        AbstractValue left = getValue(node.arguments[0].definition);
        AbstractValue right = getValue(node.arguments[1].definition);
        if (lattice.isDefinitelyInt(left) && lattice.isDefinitelyInt(right)) {
          setValue(node, nonConstant(typeSystem.intType));
        } else {
          setValue(node, nonConstant(typeSystem.numType));
        }
        break;

      case BuiltinOperator.NumLt:
      case BuiltinOperator.NumLe:
      case BuiltinOperator.NumGt:
      case BuiltinOperator.NumGe:
      case BuiltinOperator.StrictNeq:
      case BuiltinOperator.LooseNeq:
      case BuiltinOperator.IsFalsy:
      case BuiltinOperator.IsNumber:
      case BuiltinOperator.IsNotNumber:
      case BuiltinOperator.IsFloor:
      case BuiltinOperator.IsNumberAndFloor:
        setValue(node, nonConstant(typeSystem.boolType));
        break;
    }
  }

  void visitApplyBuiltinMethod(ApplyBuiltinMethod node) {
    AbstractValue receiver = getValue(node.receiver.definition);
    if (node.method == BuiltinMethod.Pop) {
      setValue(node, nonConstant(
          typeSystem.elementTypeOfIndexable(receiver.type)));
    } else {
      setValue(node, nonConstant());
    }
  }

  void visitInvokeMethodDirectly(InvokeMethodDirectly node) {
    // TODO(karlklose): lookup the function and get ites return type.
    setResult(node, nonConstant());
  }

  void visitInvokeConstructor(InvokeConstructor node) {
    setResult(node, nonConstant(typeSystem.getReturnType(node.target)));
  }

  void visitThrow(Throw node) {
  }

  void visitRethrow(Rethrow node) {
  }

  void visitUnreachable(Unreachable node) {
  }

  void visitBranch(Branch node) {
    AbstractValue conditionCell = getValue(node.condition.definition);
    AbstractBool boolifiedValue = node.isStrictCheck
        ? lattice.strictBoolify(conditionCell)
        : lattice.boolify(conditionCell);
    switch (boolifiedValue) {
      case AbstractBool.Nothing:
        break;
      case AbstractBool.True:
        setReachable(node.trueContinuation.definition);
        break;
      case AbstractBool.False:
        setReachable(node.falseContinuation.definition);
        break;
      case AbstractBool.Maybe:
        setReachable(node.trueContinuation.definition);
        setReachable(node.falseContinuation.definition);
        break;
    }
  }

  void visitTypeTest(TypeTest node) {
    AbstractValue input = getValue(node.value.definition);
    TypeMask boolType = typeSystem.boolType;
    switch(lattice.isSubtypeOf(input, node.dartType, allowNull: false)) {
      case AbstractBool.Nothing:
        break; // And come back later.

      case AbstractBool.True:
        setValue(node, constantValue(new TrueConstantValue(), boolType));
        break;

      case AbstractBool.False:
        setValue(node, constantValue(new FalseConstantValue(), boolType));
        break;

      case AbstractBool.Maybe:
        setValue(node, nonConstant(boolType));
        break;
    }
  }

  void visitTypeCast(TypeCast node) {
    Continuation cont = node.continuation.definition;
    AbstractValue input = getValue(node.value.definition);
    switch (lattice.isSubtypeOf(input, node.dartType, allowNull: true)) {
      case AbstractBool.Nothing:
        break; // And come back later.

      case AbstractBool.True:
        setReachable(cont);
        setValue(cont.parameters.single, input);
        break;

      case AbstractBool.False:
        break; // Cast fails. Continuation should remain unreachable.

      case AbstractBool.Maybe:
        setReachable(cont);
        // Narrow type of output to those that survive the cast.
        TypeMask type = input.type.intersection(
            typeSystem.subtypesOf(node.dartType),
            classWorld);
        setValue(cont.parameters.single, nonConstant(type));
        break;
    }
  }

  void visitSetMutable(SetMutable node) {
    setValue(node.variable.definition, getValue(node.value.definition));
  }

  void visitLiteralList(LiteralList node) {
    // Constant lists are translated into (Constant ListConstant(...)) IR nodes,
    // and thus LiteralList nodes are NonConst.
    setValue(node, nonConstant(typeSystem.extendableNativeListType));
  }

  void visitLiteralMap(LiteralMap node) {
    // Constant maps are translated into (Constant MapConstant(...)) IR nodes,
    // and thus LiteralMap nodes are NonConst.
    setValue(node, nonConstant(typeSystem.mapType));
  }

  void visitConstant(Constant node) {
    ConstantValue value = node.value;
    if (value.isDummy || !value.isConstant) {
      // TODO(asgerf): Explain how this happens and why we don't want them.
      setValue(node, nonConstant(typeSystem.getTypeOf(value)));
    } else {
      setValue(node, constantValue(value, typeSystem.getTypeOf(value)));
    }
  }

  void visitCreateFunction(CreateFunction node) {
    throw 'CreateFunction is not used';
  }

  void visitGetMutable(GetMutable node) {
    setValue(node, getValue(node.variable.definition));
  }

  void visitMutableVariable(MutableVariable node) {
  }

  void visitParameter(Parameter node) {
  }

  void visitContinuation(Continuation node) {
    node.parameters.forEach(visit);

    if (node.body != null) {
      push(node.body);
    }
  }

  void visitGetStatic(GetStatic node) {
    if (node.element.isFunction) {
      setValue(node, nonConstant(typeSystem.functionType));
    } else {
      setValue(node, nonConstant(typeSystem.getFieldType(node.element)));
    }
  }

  void visitSetStatic(SetStatic node) {}

  void visitGetLazyStatic(GetLazyStatic node) {
    setResult(node, nonConstant(typeSystem.getFieldType(node.element)));
  }

  void visitInterceptor(Interceptor node) {
    push(node.input.definition);
    AbstractValue value = getValue(node.input.definition);
    if (value.isNothing) {
      setValue(node, nothing);
    } else if (value.isNullable &&
        !node.interceptedClasses.contains(backend.jsNullClass)) {
      // If the input is null and null is not mapped to an interceptor then
      // null gets returned.
      // TODO(asgerf): Add the NullInterceptor when it enables us to
      //               propagate an assignment.
      setValue(node, nonConstant());
    } else {
      setValue(node, nonConstant(typeSystem.nonNullType));
    }
  }

  void visitGetField(GetField node) {
    node.objectIsNotNull = getValue(node.object.definition).isDefinitelyNotNull;
    setValue(node, nonConstant(typeSystem.getFieldType(node.field)));
  }

  void visitSetField(SetField node) {}

  void visitCreateBox(CreateBox node) {
    setValue(node, nonConstant(typeSystem.nonNullType));
  }

  void visitCreateInstance(CreateInstance node) {
    setValue(node, nonConstant(typeSystem.nonNullExact(node.classElement.declaration)));
  }

  void visitReifyRuntimeType(ReifyRuntimeType node) {
    setValue(node, nonConstant(typeSystem.typeType));
  }

  void visitReadTypeVariable(ReadTypeVariable node) {
    // TODO(karlklose): come up with a type marker for JS entities or switch to
    // real constants of type [Type].
    setValue(node, nonConstant());
  }

  @override
  void visitTypeExpression(TypeExpression node) {
    // TODO(karlklose): come up with a type marker for JS entities or switch to
    // real constants of type [Type].
    setValue(node, nonConstant());
  }

  void visitCreateInvocationMirror(CreateInvocationMirror node) {
    // TODO(asgerf): Expose [Invocation] type.
    setValue(node, nonConstant(typeSystem.nonNullType));
  }

  @override
  void visitForeignCode(ForeignCode node) {
    if (node.continuation != null) {
      setResult(node, nonConstant(node.type));
    }
  }

  @override
  void visitGetLength(GetLength node) {
    AbstractValue input = getValue(node.object.definition);
    node.objectIsNotNull = getValue(node.object.definition).isDefinitelyNotNull;
    int length = typeSystem.getContainerLength(input.type);
    if (length != null) {
      // TODO(asgerf): Constant-folding the length might degrade the VM's
      // own bounds-check elimination?
      setValue(node, constantValue(new IntConstantValue(length)));
    } else {
      setValue(node, nonConstant(typeSystem.intType));
    }
  }

  @override
  void visitGetIndex(GetIndex node) {
    AbstractValue input = getValue(node.object.definition);
    setValue(node, nonConstant(typeSystem.elementTypeOfIndexable(input.type)));
  }

  @override
  void visitSetIndex(SetIndex node) {
    setValue(node, nonConstant());
  }

  @override
  void visitAwait(Await node) {
    setResult(node, nonConstant());
  }

  @override
  visitYield(Yield node) {
    setReachable(node.continuation.definition);
  }

  @override
  void visitRefinement(Refinement node) {
    AbstractValue value = getValue(node.value.definition);
    if (value.isNothing ||
        typeSystem.areDisjoint(value.type, node.refineType)) {
      setValue(node, nothing);
    } else if (value.isConstant) {
      setValue(node, value);
    } else {
      setValue(node,
          nonConstant(value.type.intersection(node.refineType, classWorld)));
    }
  }
}

/// Represents the abstract value of a primitive value at some point in the
/// program. Abstract values of all kinds have a type [T].
///
/// The different kinds of abstract values represents the knowledge about the
/// constness of the value:
///   NOTHING:  cannot have any value
///   CONSTANT: is a constant. The value is stored in the [constant] field,
///             and the type of the constant is in the [type] field.
///   NONCONST: not a constant, but [type] may hold some information.
class AbstractValue {
  static const int NOTHING  = 0;
  static const int CONSTANT = 1;
  static const int NONCONST = 2;

  final int kind;
  final ConstantValue constant;
  final TypeMask type;

  AbstractValue._internal(this.kind, this.constant, this.type) {
    assert(kind != CONSTANT || constant != null);
    assert(constant is! SyntheticConstantValue);
  }

  AbstractValue.nothing()
      : this._internal(NOTHING, null, new TypeMask.nonNullEmpty());

  AbstractValue.constantValue(ConstantValue constant, TypeMask type)
      : this._internal(CONSTANT, constant, type);

  factory AbstractValue.nonConstant(TypeMask type) {
    if (type.isEmpty) {
      if (type.isNullable)
        return new AbstractValue.constantValue(new NullConstantValue(), type);
      else
        return new AbstractValue.nothing();
    } else {
      return new AbstractValue._internal(NONCONST, null, type);
    }
  }

  bool get isNothing  => (kind == NOTHING);
  bool get isConstant => (kind == CONSTANT);
  bool get isNonConst => (kind == NONCONST);
  bool get isNullConstant => kind == CONSTANT && constant.isNull;
  bool get isTrueConstant => kind == CONSTANT && constant.isTrue;

  bool get isNullable => kind != NOTHING && type.isNullable;
  bool get isDefinitelyNotNull => kind == NOTHING || !type.isNullable;

  int get hashCode {
    int hash = kind * 31 + constant.hashCode * 59 + type.hashCode * 67;
    return hash & 0x3fffffff;
  }

  bool operator ==(AbstractValue that) {
    return that.kind == this.kind &&
           that.constant == this.constant &&
           that.type == this.type;
  }

  String toString() {
    switch (kind) {
      case NOTHING: return "Nothing";
      case CONSTANT: return "Constant: ${constant.unparse()}: $type";
      case NONCONST: return "Non-constant: $type";
      default: assert(false);
    }
    return null;
  }
}

/// Enum-like class with the names of internal methods we care about.
abstract class InternalMethod {
  static const String Stringify = 'S';
}

/// Enum-like class with the names of dart:core methods we care about.
abstract class CorelibMethod {
  static const String Identical = 'identical';
}

/// Suggested name for a synthesized loop index.
class LoopIndexEntity extends Entity {
  String get name => 'i';
}

/// Suggested name for the current element of a list being iterated.
class LoopItemEntity extends Entity {
  String get name => 'current';
}

/// Suggested name for the original length of a list, for use in checks
/// for concurrent modification.
class OriginalLengthEntity extends Entity {
  String get name => 'length';
}

class ResetAnalysisInfo extends RecursiveVisitor {
  Set<Continuation> reachableContinuations;
  Map<Variable, ConstantValue> values;

  ResetAnalysisInfo(this.reachableContinuations, this.values);

  processContinuation(Continuation cont) {
    reachableContinuations.remove(cont);
    cont.parameters.forEach(values.remove);
  }

  processLetPrim(LetPrim node) {
    node.primitive.type = null;
    values[node.primitive] = null;
  }

  processLetMutable(LetMutable node) {
    node.variable.type = null;
    values[node.variable] = null;
  }
}