dart2js cps: Type casts and related changes to type propagation.

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.
 
 import 'optimizers.dart' show Pass, ParentVisitor;
 
 import '../constants/constant_system.dart';
 import '../constants/expressions.dart';
 import '../resolution/operators.dart';
 import '../constants/values.dart';
 import '../dart_types.dart' as types;
 import '../dart2jslib.dart' as dart2js;
 import '../tree/tree.dart' show LiteralDartString;
 import 'cps_ir_nodes.dart';
 import '../types/types.dart' show TypeMask, TypesTask;
 import '../types/constants.dart' show computeTypeMask;
 import '../elements/elements.dart' show ClassElement, Element, Entity,
     FieldElement, FunctionElement, ParameterElement;
 import '../dart2jslib.dart' show ClassWorld;
 import '../universe/universe.dart';
 
 abstract class TypeSystem<T> {
   T get dynamicType;
   T get typeType;
   T get functionType;
   T get boolType;
   T get intType;
+  T get numType;
   T get stringType;
   T get listType;
   T get mapType;
   T get nonNullType;
 
   T getReturnType(FunctionElement element);
   T getSelectorReturnType(Selector selector);
   T getParameterType(ParameterElement element);
   T getFieldType(FieldElement element);
   T join(T a, T b);
   T exact(ClassElement element);
   T getTypeOf(ConstantValue constant);
 
   bool areDisjoint(T leftType, T rightType);
 
   /// True if all values satisfying [type] are booleans (null is not a boolean).
   bool isDefinitelyBool(T type);
 
   bool isDefinitelyNotNull(T type);
+
+  AbstractBool isSubtypeOf(T value, types.DartType type, {bool allowNull});
 }
 
 class UnitTypeSystem implements TypeSystem<String> {
   static const String UNIT = 'unit';
 
   get boolType => UNIT;
   get dynamicType => UNIT;
   get functionType => UNIT;
   get intType => UNIT;
+  get numType => UNIT;
   get listType => UNIT;
   get mapType => UNIT;
   get stringType => UNIT;
   get typeType => UNIT;
   get nonNullType => UNIT;
 
   getParameterType(_) => UNIT;
   getReturnType(_) => UNIT;
   getSelectorReturnType(_) => UNIT;
   getFieldType(_) => UNIT;
   join(a, b) => UNIT;
   exact(_) => UNIT;
   getTypeOf(_) => UNIT;
 
+  bool areDisjoint(String leftType, String rightType) {
+    return false;
+  }
+
   bool isDefinitelyBool(_) => false;
 
   bool isDefinitelyNotNull(_) => false;
 
-  bool areDisjoint(String leftType, String rightType) {
-    return false;
+  AbstractBool isSubtypeOf(value, type, {bool allowNull}) {
+    return AbstractBool.Maybe;
   }
 }
 
+enum AbstractBool {
+  True, False, Maybe, Nothing
+}
+
 class TypeMaskSystem implements TypeSystem<TypeMask> {
   final TypesTask inferrer;
   final ClassWorld classWorld;
 
   TypeMask get dynamicType => inferrer.dynamicType;
   TypeMask get typeType => inferrer.typeType;
   TypeMask get functionType => inferrer.functionType;
   TypeMask get boolType => inferrer.boolType;
   TypeMask get intType => inferrer.intType;
+  TypeMask get numType => inferrer.numType;
   TypeMask get stringType => inferrer.stringType;
   TypeMask get listType => inferrer.listType;
   TypeMask get mapType => inferrer.mapType;
   TypeMask get nonNullType => inferrer.nonNullType;
 
   // TODO(karlklose): remove compiler here.
   TypeMaskSystem(dart2js.Compiler compiler)
     : inferrer = compiler.typesTask,
       classWorld = compiler.world;
 
@@ skipping 35 matching lines @@
     return t.containsOnlyBool(classWorld) && !t.isNullable;
   }
 
   bool isDefinitelyNotNull(TypeMask t) => !t.isNullable;
 
   @override
   bool areDisjoint(TypeMask leftType, TypeMask rightType) {
     TypeMask intersection = leftType.intersection(rightType, classWorld);
     return intersection.isEmpty && !intersection.isNullable;
   }
+
+  AbstractBool isSubtypeOf(TypeMask value,
+                           types.DartType type,
+                           {bool allowNull}) {
+    assert(allowNull != null);
+    if (type is types.DynamicType) {
+      if (!allowNull && value.isNullable) return AbstractBool.Maybe;
+      return AbstractBool.True;
+    }
+    if (type is types.InterfaceType) {
+      TypeMask typeAsMask = allowNull
+          ? new TypeMask.subtype(type.element, classWorld)
+          : new TypeMask.nonNullSubtype(type.element, classWorld);
+      if (areDisjoint(value, typeAsMask)) {
+        // Disprove the subtype relation based on the class alone.
+        return AbstractBool.False;
+      }
+      if (!type.treatAsRaw) {
+        // If there are type arguments, we cannot prove the subtype relation,
+        // because the type arguments are unknown on both the value and type.
+        return AbstractBool.Maybe;
+      }
+      if (typeAsMask.containsMask(value, classWorld)) {
+        // All possible values are contained in the set of allowed values.
+        // Note that we exploit the fact that [typeAsMask] is an exact
+        // representation of [type], not an approximation.
+        return AbstractBool.True;
+      }
+      // The value is neither contained in the type, nor disjoint from the type.
+      return AbstractBool.Maybe;
+    }
+    // TODO(asgerf): Support function types, and what else might be missing.
+    return AbstractBool.Maybe;
+  }
+}
+
+class ConstantPropagationLattice<T> {
+  final TypeSystem<T> typeSystem;
+  final ConstantSystem constantSystem;
+  final types.DartTypes dartTypes;
+
+  ConstantPropagationLattice(this.typeSystem,
+                             this.constantSystem,
+                             this.dartTypes);
+
+  final _AbstractValue<T> nothing = new _AbstractValue<T>.nothing();
+
+  _AbstractValue<T> constant(ConstantValue value) {
+    return new _AbstractValue<T>.constantValue(value,
+                                               typeSystem.getTypeOf(value));
+  }
+
+  _AbstractValue<T> nonConstant(T type) {
+    return new _AbstractValue<T>.nonConstant(type);
+  }
+
+  _AbstractValue<T> get anything {
+    return new _AbstractValue<T>.nonConstant(typeSystem.dynamicType);
+  }
+
+  /// 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 to an instance of anything,
+  /// otherwise it is only considered an instance of [Object], [dynamic], and
+  /// [Null].
+  AbstractBool isSubtypeOf(_AbstractValue<T> 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;
+      }
+      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.
+  _AbstractValue<T> unaryOp(UnaryOperator operator,
+                            _AbstractValue<T> 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 anything; // 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.
+  _AbstractValue<T> binaryOp(BinaryOperator operator,
+                             _AbstractValue<T> left,
+                             _AbstractValue<T> 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);
+    }
+    return anything; // TODO(asgerf): Look up type.
+  }
 }
 
 /**
  * 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<T> extends Pass {
   String get passName => 'Sparse constant propagation';
 
   final types.DartTypes _dartTypes;
 
   // The constant system is used for evaluation of expressions with constant
   // arguments.
   final ConstantSystem _constantSystem;
   final TypeSystem _typeSystem;
   final dart2js.InternalErrorFunction _internalError;
-  final Map<Node, _AbstractValue> _types;
+  final Map<Primitive, _AbstractValue> _types = <Primitive, _AbstractValue>{};
 
   TypePropagator(this._dartTypes,
                  this._constantSystem,
                  this._typeSystem,
-                 this._internalError)
-      : _types = <Node, _AbstractValue>{};
+                 this._internalError);
 
   @override
   void rewrite(FunctionDefinition root) {
     // Set all parent pointers.
     new ParentVisitor().visit(root);
 
+    ConstantPropagationLattice<T> lattice = new ConstantPropagationLattice<T>(
+      _typeSystem, _constantSystem, _dartTypes);
+    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<T> analyzer = new _TypePropagationVisitor<T>(
-        _constantSystem,
-        _typeSystem,
+        lattice,
         _types,
-        _internalError,
-        _dartTypes);
+        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.
+    // with constant results or existing values that are in scope.
     _TransformingVisitor<T> transformer = new _TransformingVisitor<T>(
-        analyzer.reachableNodes, analyzer.values, _internalError, _typeSystem);
+        lattice,
+        analyzer.reachableNodes,
+        analyzer.values,
+        replacements,
+        _internalError);
     transformer.transform(root);
   }
 
   getType(Node node) => _types[node];
 }
 
 /**
  * Uses the information from a preceding analysis pass in order to perform the
  * actual transformations on the CPS graph.
  */
 class _TransformingVisitor<T> extends RecursiveVisitor {
   final Set<Node> reachable;
   final Map<Node, _AbstractValue> values;
-  final TypeSystem<T> typeSystem;
+  final Map<Expression, ConstantValue> replacements;
+  final ConstantPropagationLattice<T> valueLattice;
+
+  TypeSystem<T> get typeSystem => valueLattice.typeSystem;
 
   final dart2js.InternalErrorFunction internalError;
 
-  _TransformingVisitor(this.reachable,
+  _TransformingVisitor(this.valueLattice,
+                       this.reachable,
                        this.values,
-                       this.internalError,
-                       this.typeSystem);
+                       this.replacements,
+                       this.internalError);
 
   void transform(FunctionDefinition root) {
     visit(root);
   }
 
+  Constant makeConstantPrimitive(ConstantValue constant) {
+    ConstantExpression constExp =
+        const ConstantExpressionCreator().convert(constant);
+    Constant primitive = new Constant(constExp, constant);
+    values[primitive] = new _AbstractValue.constantValue(constant,
+        typeSystem.getTypeOf(constant));
+    return primitive;
+  }
+
   /// Given an expression with a known constant result and a continuation,
   /// replaces the expression by a new LetPrim / InvokeContinuation construct.
   /// `unlink` is a closure responsible for unlinking all removed references.
   LetPrim constifyExpression(Expression node,
                              Continuation continuation,
                              void unlink()) {
-    _AbstractValue value = values[node];
-    if (value == null || !value.isConstant) {
-      return null;
-    }
+    ConstantValue constant = replacements[node];
+    if (constant == null) return null;
 
     assert(continuation.parameters.length == 1);
+    InteriorNode parent = node.parent;
+    Constant primitive = makeConstantPrimitive(constant);
+    LetPrim letPrim = new LetPrim(primitive);
 
-    // Set up the replacement structure.
-    PrimitiveConstantValue primitiveConstant = value.constant;
-    ConstantExpression constExp =
-        const ConstantExpressionCreator().convert(primitiveConstant);
-    Constant constant = new Constant(constExp, primitiveConstant);
-    LetPrim letPrim = new LetPrim(constant);
     InvokeContinuation invoke =
-        new InvokeContinuation(continuation, <Primitive>[constant]);
-
-    invoke.parent = constant.parent = letPrim;
+        new InvokeContinuation(continuation, <Primitive>[primitive]);
+    parent.body = letPrim;
     letPrim.body = invoke;
-
-    // Replace the method invocation.
-
-    InteriorNode parent = node.parent;
+    invoke.parent = letPrim;
     letPrim.parent = parent;
-    parent.body = letPrim;
 
     unlink();
 
     return letPrim;
   }
 
   // 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.
@@ skipping 67 matching lines @@
       node.arguments.forEach((Reference ref) => ref.unlink());
     });
 
     if (letPrim == null) {
       super.visitConcatenateStrings(node);
     } else {
       visitLetPrim(letPrim);
     }
   }
 
-  // See [visitInvokeMethod].
-  void visitTypeOperator(TypeOperator node) {
+  void visitTypeCast(TypeCast node) {
     Continuation cont = node.continuation.definition;
-    LetPrim letPrim = constifyExpression(node, cont, () {
-      node.value.unlink();
-      node.typeArguments.forEach((Reference ref) => ref.unlink());
-      node.continuation.unlink();
-    });
+    InteriorNode parent = node.parent;
 
-    if (letPrim == null) {
-      super.visitTypeOperator(node);
-    } else {
-      visitLetPrim(letPrim);
+    _AbstractValue<T> value = getValue(node.value.definition);
+    switch (valueLattice.isSubtypeOf(value, node.type, allowNull: true)) {
+      case AbstractBool.Maybe:
+      case AbstractBool.Nothing:
+        break;
+
+      case AbstractBool.True:
+        // Cast always succeeds, replace it with InvokeContinuation.
+        InvokeContinuation invoke =
+            new InvokeContinuation.fromCall(node.continuation, node.value);
+        parent.body = invoke;
+        invoke.parent = parent;
+        super.visitInvokeContinuation(invoke);
+        return;
+
+      case AbstractBool.False:
+        // Cast always fails, remove unreachable continuation body.
+        assert(!reachable.contains(cont));
+        RemovalVisitor.remove(cont.body);
+        cont.body = new Unreachable()..parent = cont;
+        break;
     }
+
+    super.visitTypeCast(node);
   }
 
   _AbstractValue<T> getValue(Primitive primitive) {
     _AbstractValue<T> value = values[primitive];
     return value == null ? new _AbstractValue.nothing() : value;
   }
 
   void visitIdentical(Identical node) {
     Primitive left = node.left.definition;
     Primitive right = node.right.definition;
     _AbstractValue<T> leftValue = getValue(left);
     _AbstractValue<T> rightValue = getValue(right);
     // Replace identical(x, true) by x when x is known to be a boolean.
     if (leftValue.isDefinitelyBool(typeSystem) &&
         rightValue.isConstant &&
         rightValue.constant.isTrue) {
       left.substituteFor(node);
     }
   }
+
+  void visitLetPrim(LetPrim node) {
+    _AbstractValue<T> value = getValue(node.primitive);
+    if (node.primitive is! Constant && value.isConstant) {
+      // If the value is a known constant, compile it as a constant.
+      Constant newPrim = makeConstantPrimitive(value.constant);
+      LetPrim newLet = new LetPrim(newPrim);
+      node.parent.body = newLet;
+      newLet.body = node.body;
+      node.body.parent = newLet;
+      newLet.parent = node.parent;
+      newPrim.substituteFor(node.primitive);
+      RemovalVisitor.remove(node.primitive);
+      visit(newLet.body);
+    } else {
+      super.visitLetPrim(node);
+    }
+  }
 }
 
 /**
  * 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<T> 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<Node> reachableNodes = new Set<Node>();
 
   // The definition workset stores all definitions which need to be reprocessed
   // since their lattice value has changed.
   final Set<Definition> defWorkset = new Set<Definition>();
 
-  final ConstantSystem constantSystem;
-  final TypeSystem<T> typeSystem;
+  final ConstantPropagationLattice<T> valueLattice;
   final dart2js.InternalErrorFunction internalError;
-  final types.DartTypes _dartTypes;
+
+  TypeSystem get typeSystem => valueLattice.typeSystem;
 
   _AbstractValue<T> nothing = new _AbstractValue.nothing();
 
   _AbstractValue<T> nonConstant([T type]) {
     if (type == null) {
       type = typeSystem.dynamicType;
     }
     return new _AbstractValue<T>.nonConstant(type);
   }
 
   _AbstractValue<T> constantValue(ConstantValue constant, T type) {
     return new _AbstractValue<T>.constantValue(constant, type);
   }
 
   // Stores the current lattice value for nodes. Note that it contains not only
   // definitions as keys, but also expressions such as method invokes.
   // Access through [getValue] and [setValue].
-  final Map<Node, _AbstractValue<T>> values;
+  final Map<Primitive, _AbstractValue<T>> values;
 
-  _TypePropagationVisitor(this.constantSystem,
-                          TypeSystem typeSystem,
+  /// 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.valueLattice,
                           this.values,
-                          this.internalError,
-                          this._dartTypes)
-      : this.typeSystem = typeSystem;
+                          this.replacements,
+                          this.internalError);
 
   void analyze(FunctionDefinition root) {
     reachableNodes.clear();
     defWorkset.clear();
     nodeWorklist.clear();
 
     // Initially, only the root node is reachable.
     setReachable(root);
 
     while (true) {
@@ skipping 120 matching lines @@
       Definition def = node.arguments[i].definition;
       _AbstractValue<T> cell = getValue(def);
       setValue(cont.parameters[i], cell);
     }
   }
 
   void visitInvokeMethod(InvokeMethod node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
-    /// Sets the value of both the current node and the target continuation
-    /// parameter.
-    void setValues(_AbstractValue<T> updateValue) {
-      setValue(node, updateValue);
+    /// Sets the value of the target continuation parameter, and possibly
+    /// try to replace the whole invocation with a constant.
+    void setResult(_AbstractValue<T> updateValue, {bool canReplace: false}) {
       Parameter returnValue = cont.parameters[0];
       setValue(returnValue, updateValue);
+      if (canReplace && updateValue.isConstant) {
+        replacements[node] = updateValue.constant;
+      } else {
+        // A previous iteration might have tried to replace this.
+        replacements.remove(node);
+      }
     }
 
     _AbstractValue<T> lhs = getValue(node.receiver.definition);
     if (lhs.isNothing) {
       return;  // And come back later.
-    } else if (lhs.isNonConst) {
-      setValues(nonConstant(typeSystem.getSelectorReturnType(node.selector)));
-      return;
-    } else if (!node.selector.isOperator) {
+    }
+    if (!node.selector.isOperator) {
       // TODO(jgruber): Handle known methods on constants such as String.length.
-      setValues(nonConstant());
+      setResult(nonConstant(typeSystem.getSelectorReturnType(node.selector)));
       return;
     }
 
+    // TODO(asgerf): Support constant folding on intercepted calls!
+
     // Calculate the resulting constant if possible.
-    ConstantValue result;
+    _AbstractValue<T> result;
     String opname = node.selector.name;
     if (node.selector.argumentCount == 0) {
       // Unary operator.
-
       if (opname == "unary-") {
         opname = "-";
       }
-      UnaryOperation operation = constantSystem.lookupUnary(
-          UnaryOperator.parse(opname));
-      if (operation != null) {
-        result = operation.fold(lhs.constant);
-      }
+      UnaryOperator operator = UnaryOperator.parse(opname);
+      result = valueLattice.unaryOp(operator, lhs);
     } else if (node.selector.argumentCount == 1) {
       // Binary operator.
-
       _AbstractValue<T> rhs = getValue(node.arguments[0].definition);
-      if (!rhs.isConstant) {
-        setValues(nonConstant());
-        return;
-      }
-
-      BinaryOperation operation = constantSystem.lookupBinary(
-          BinaryOperator.parse(opname));
-      if (operation != null) {
-        result = operation.fold(lhs.constant, rhs.constant);
-      }
+      BinaryOperator operator = BinaryOperator.parse(opname);
+      result = valueLattice.binaryOp(operator, lhs, rhs);
     }
 
     // Update value of the continuation parameter. Again, this is effectively
     // a phi.
     if (result == null) {
-      setValues(nonConstant());
+      setResult(nonConstant());
     } else {
-      T type = typeSystem.getTypeOf(result);
-      setValues(constantValue(result, type));
+      setResult(result, canReplace: true);
     }
    }
 
   void visitInvokeMethodDirectly(InvokeMethodDirectly node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
     assert(cont.parameters.length == 1);
     Parameter returnValue = cont.parameters[0];
     // TODO(karlklose): lookup the function and get ites return type.
     setValue(returnValue, nonConstant());
   }
 
   void visitInvokeConstructor(InvokeConstructor node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
     assert(cont.parameters.length == 1);
     Parameter returnValue = cont.parameters[0];
     setValue(returnValue, nonConstant(typeSystem.getReturnType(node.target)));
   }
 
   void visitConcatenateStrings(ConcatenateStrings node) {
     Continuation cont = node.continuation.definition;
     setReachable(cont);
 
-    void setValues(_AbstractValue<T> updateValue) {
-      setValue(node, updateValue);
+    /// Sets the value of the target continuation parameter, and possibly
+    /// try to replace the whole invocation with a constant.
+    void setResult(_AbstractValue<T> updateValue, {bool canReplace: false}) {
       Parameter returnValue = cont.parameters[0];
       setValue(returnValue, updateValue);
+      if (canReplace && updateValue.isConstant) {
+        replacements[node] = updateValue.constant;
+      } else {
+        // A previous iteration might have tried to replace this.
+        replacements.remove(node);
+      }
     }
 
     // TODO(jgruber): Currently we only optimize if all arguments are string
     // constants, but we could also handle cases such as "foo${42}".
     bool allStringConstants = node.arguments.every((Reference ref) {
       if (!(ref.definition is Constant)) {
         return false;
       }
       Constant constant = ref.definition;
       return constant != null && constant.value.isString;
     });
 
     T type = typeSystem.stringType;
     assert(cont.parameters.length == 1);
     if (allStringConstants) {
       // All constant, we can concatenate ourselves.
       Iterable<String> allStrings = node.arguments.map((Reference ref) {
         Constant constant = ref.definition;
         StringConstantValue stringConstant = constant.value;
         return stringConstant.primitiveValue.slowToString();
       });
       LiteralDartString dartString = new LiteralDartString(allStrings.join());
       ConstantValue constant = new StringConstantValue(dartString);
-      setValues(constantValue(constant, type));
+      setResult(constantValue(constant, type), canReplace: true);
     } else {
-      setValues(nonConstant(type));
+      setResult(nonConstant(type));
     }
   }
 
   void visitThrow(Throw node) {
   }
 
   void visitRethrow(Rethrow node) {
   }
 
+  void visitUnreachable(Unreachable node) {
+  }
+
   void visitNonTailThrow(NonTailThrow node) {
     internalError(null, 'found non-tail throw after they were eliminated');
   }
 
   void visitBranch(Branch node) {
     IsTrue isTrue = node.condition;
     _AbstractValue<T> conditionCell = getValue(isTrue.value.definition);
 
     if (conditionCell.isNothing) {
       return;  // And come back later.
     } else if (conditionCell.isNonConst) {
       setReachable(node.trueContinuation.definition);
       setReachable(node.falseContinuation.definition);
     } else if (conditionCell.isConstant && !conditionCell.constant.isBool) {
       // Treat non-bool constants in condition as non-const since they result
       // in type errors in checked mode.
       // TODO(jgruber): Default to false in unchecked mode.
       setReachable(node.trueContinuation.definition);
       setReachable(node.falseContinuation.definition);
       setValue(isTrue.value.definition, nonConstant(typeSystem.boolType));
     } else if (conditionCell.isConstant && conditionCell.constant.isBool) {
       BoolConstantValue boolConstant = conditionCell.constant;
       setReachable((boolConstant.isTrue) ?
           node.trueContinuation.definition : node.falseContinuation.definition);
     }
   }
 
-  void visitTypeOperator(TypeOperator node) {
-    Continuation cont = node.continuation.definition;
-    setReachable(cont);
+  void visitTypeTest(TypeTest node) {
+    _AbstractValue<T> input = getValue(node.value.definition);
+    T boolType = typeSystem.boolType;
+    switch(valueLattice.isSubtypeOf(input, node.type, allowNull: false)) {
+      case AbstractBool.Nothing:
+        break; // And come back later.
 
-    void setValues(_AbstractValue<T> updateValue) {
-      setValue(node, updateValue);
-      Parameter returnValue = cont.parameters[0];
-      setValue(returnValue, updateValue);
-    }
+      case AbstractBool.True:
+        setValue(node, constantValue(new TrueConstantValue(), boolType));
+        break;
 
-    if (node.isTypeCast) {
-      // TODO(jgruber): Add support for `as` casts.
-      setValues(nonConstant());
-      return;
-    }
+      case AbstractBool.False:
+        setValue(node, constantValue(new FalseConstantValue(), boolType));
+        break;
 
-    _AbstractValue<T> cell = getValue(node.value.definition);
-    if (cell.isNothing) {
-      return;  // And come back later.
-    } else if (cell.isConstant && node.type.kind == types.TypeKind.INTERFACE) {
-      // Receiver is a constant, perform is-checks at compile-time.
-
-      types.InterfaceType checkedType = node.type;
-      ConstantValue constant = cell.constant;
-      types.DartType constantType = constant.getType(_dartTypes.coreTypes);
-
-      T type = typeSystem.boolType;
-      _AbstractValue<T> result;
-      if (constant.isNull &&
-          checkedType != _dartTypes.coreTypes.nullType &&
-          checkedType != _dartTypes.coreTypes.objectType) {
-        // `(null is Type)` is true iff Type is in { Null, Object }.
-        result = constantValue(new FalseConstantValue(), type);
-      } else {
-        // Otherwise, perform a standard subtype check.
-        result = constantValue(
-            constantSystem.isSubtype(_dartTypes, constantType, checkedType)
-            ? new TrueConstantValue()
-            : new FalseConstantValue(),
-            type);
-      }
-      setValues(result);
-    } else {
-      setValues(nonConstant(typeSystem.boolType));
+      case AbstractBool.Maybe:
+        setValue(node, nonConstant(boolType));
+        break;
     }
   }
 
+  void visitTypeCast(TypeCast node) {
+    Continuation cont = node.continuation.definition;
+    _AbstractValue<T> input = getValue(node.value.definition);
+    switch (valueLattice.isSubtypeOf(input, node.type, 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:
+        // TODO(asgerf): Narrow type of output to those that survive the cast.
+        setReachable(cont);
+        setValue(cont.parameters.single, input);
+        break;
+    }
+  }
+
   void visitSetMutableVariable(SetMutableVariable node) {
     setValue(node.variable.definition, getValue(node.value.definition));
     setReachable(node.body);
   }
 
   void visitLiteralList(LiteralList node) {
     // Constant lists are translated into (Constant ListConstant(...)) IR nodes,
     // and thus LiteralList nodes are NonConst.
     setValue(node, nonConstant(typeSystem.listType));
   }
@@ skipping 316 matching lines @@
   ConstantExpression visitString(StringConstantValue constant, arg) {
     return new StringConstantExpression(
         constant.primitiveValue.slowToString());
   }
 
   @override
   ConstantExpression visitType(TypeConstantValue constant, arg) {
     throw new UnsupportedError("ConstantExpressionCreator.visitType");
   }
 }