dart2js cps: Add path-sensitive types by inserting refinement IR nodes.

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

+// Copyright (c) 2015, 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 cps_ir.optimization.insert_refinements;
+
+import 'optimizers.dart' show Pass;
+import 'shrinking_reductions.dart' show ParentVisitor;
+import 'cps_ir_nodes.dart';
+import '../types/types.dart';
+import '../types/constants.dart';
+import '../constants/values.dart';
+import '../world.dart';
+import '../common/names.dart';
+import '../universe/universe.dart';
+import '../elements/elements.dart';
+
+/// Inserts [Refinement] nodes in the IR to allow for sparse path-sensitive
+/// type analysis in the [TypePropagator] pass.
+///
+/// Refinement nodes are inserted at the arms of a [Branch] node with a
+/// condition of form `x is T` or `x == CONST`.
+///
+/// Refinement nodes are inserted after a method invocation to account for the
+/// fact that the receiver cannot be null afterwards (in most cases).
+///
+// TODO(asgerf): Generalize the non-null pattern to all selectors/classes?
+class InsertRefinements extends RecursiveVisitor implements Pass {
+  String get passName => 'Insert refinement nodes';
+
+  Parameter thisParameter;
+  final TypesTask types;
+  final World world;
+  final TypeMask nonNullType;
+  final TypeMask nullType;
+
+  /// Maps unrefined primitives to its refinement currently in scope (if any).
+  final Map<Primitive, Refinement> refinementFor = <Primitive, Refinement>{};
+
+  InsertRefinements(this.types, World world)
+    : this.world = world,
+      nonNullType = new TypeMask.nonNullSubtype(world.objectClass, world),
+      nullType = new TypeMask.empty();
+
+  void rewrite(FunctionDefinition node) {
+    new ParentVisitor().visit(node);
+    thisParameter = node.thisParameter;
+    visit(node.body);
+  }
+
+  /// Updates references to the refer to the refinement currently in scope.
+  void processReference(Reference node) {
+    Refinement refined = refinementFor[node.definition];
+    if (refined != null) {
+      node.changeTo(refined);
+    }
+  }
+
+  /// True if [prim] might evaluate to null.
+  ///
+  /// Used to avoid inserting refinement nodes that are obviously redundant.
+  bool maybeNull(Primitive prim) {
+    if (prim is Constant) return !prim.value.isNull;
+    if (prim is Interceptor) return maybeNull(prim.input.definition);
+    if (prim is Refinement) {
+      if (!prim.type.isNullable) return false;
+      return maybeNull(prim.value.definition);
+    }
+    if (prim == thisParameter) return false;
+    return true;
+  }
+
+  /// True if an exception is thrown when the given selector is invoked on null.
+  bool failsOnNull(Selector selector) {
+    if (selector.isGetter) {
+      return selector.name != 'toString' &&
+             selector.name != 'hashCode' &&
+             selector.name != 'noSuchMethod' &&
+             selector.name != 'runtimeType';
+    } else {
+      return selector != Selectors.toString_ &&
+             selector != Selectors.hashCode_ &&
+             selector != Selectors.equals;
+    }
+  }
+
+  /// Moves the binding of [cont] to before [use].
+  ///
+  /// This is used to ensure that everything in scope at [use] is also in scope
+  /// inside [cont], so refinements can be inserted inside [cont] without
+  /// accidentally referencing a primitive out of scope.
+  ///
+  /// It is always safe to do this for single-use continuations, because
+  /// strictly more things are in scope at the use site, and there can't be any
+  /// other use of [cont] that might fall out of scope since there is only
+  /// that single use.
+  void sinkContinuationToUse(Continuation cont, Expression use) {
+    assert(cont.hasExactlyOneUse && cont.firstRef.parent == use);
+    LetCont let = cont.parent;
+    InteriorNode useParent = use.parent;
+    if (useParent == let) return;
+    if (let.continuations.length > 1) {
+      // Create a new LetCont binding only this continuation.
+      let.continuations.remove(cont);
+      let = new LetCont(cont, null);
+      cont.parent = let;
+    } else {
+      // Remove LetCont from current position.
+      InteriorNode letParent = let.parent;
+      letParent.body = let.body;
+      let.body.parent = letParent;
+    }
+
+    // Insert LetCont before use.
+    useParent.body = let;
+    let.body = use;
+    use.parent = let;
+    let.parent = useParent;
+  }
+
+  Primitive unfoldInterceptor(Primitive prim) {
+    return prim is Interceptor ? prim.input.definition : prim;
+  }
+
+  /// Enqueues [cont] for processing in a context where [refined] is the
+  /// current refinement for its value.
+  void pushRefinement(Continuation cont, Refinement refined) {
+    Primitive value = refined.effectiveDefinition;
+    Primitive currentRefinement = refinementFor[value];
+    pushAction(() {
+      refinementFor[value] = currentRefinement;
+      if (refined.hasNoUses) {
+        // Clean up refinements that are not used.
+        refined.value.unlink();
+      } else {
+        cont.body = new LetPrim(refined, cont.body);
+        refined.parent = cont.body;
+        refined.value.parent = refined;
+      }
+    });
+    push(cont);
+    pushAction(() {
+      refinementFor[value] = refined;
+    });
+  }
+
+  void visitInvokeMethod(InvokeMethod node) {
+    Continuation cont = node.continuation.definition;
+
+    // Update references to their current refined values.
+    processReference(node.receiver);
+    node.arguments.forEach(processReference);
+
+    // If the call is intercepted, we want to refine the actual receiver,
+    // not the interceptor.
+    Primitive receiver = unfoldInterceptor(node.receiver.definition);
+
+    // Sink the continuation to the call to ensure everything in scope
+    // here is also in scope inside the continuations.
+    sinkContinuationToUse(cont, node);
+
+    if (node.selector.isClosureCall) {
+      // Do not try to refine the receiver of closure calls; the class world
+      // does not know about closure classes.
+      push(cont);
+    } else {
+      // Filter away receivers that throw on this selector.
+      TypeMask type = world.allFunctions.receiverType(node.selector, node.mask);
+      pushRefinement(cont, new Refinement(receiver, type));
+    }
+  }
+
+  CallExpression getCallWithResult(Primitive prim) {
+    if (prim is Parameter && prim.parent is Continuation) {
+      Continuation cont = prim.parent;
+      if (cont.hasExactlyOneUse && cont.firstRef.parent is CallExpression) {
+        return cont.firstRef.parent;
+      }
+    }
+    return null;
+  }
+
+  bool isTrue(Primitive prim) {
+    return prim is Constant && prim.value.isTrue;
+  }
+
+  TypeMask getTypeOf(ConstantValue constant) {
+    return computeTypeMask(types.compiler, constant);
+  }
+
+  void visitBranch(Branch node) {
+    processReference(node.condition);
+    Primitive condition = node.condition.definition;
+    CallExpression call = getCallWithResult(condition);
+
+    Continuation trueCont = node.trueContinuation.definition;
+    Continuation falseCont = node.falseContinuation.definition;
+
+    // Sink both continuations to the Branch to ensure everything in scope
+    // here is also in scope inside the continuations.
+    sinkContinuationToUse(trueCont, node);
+    sinkContinuationToUse(falseCont, node);
+
+    // If the condition is an 'is' check, promote the checked value.
+    if (condition is TypeTest && condition.type.element is ClassElement) {
+      Primitive value = condition.value.definition;
+      ClassElement classElement = condition.type.element;
+      TypeMask type = new TypeMask.nonNullSubtype(classElement, world);
+      Primitive refinedValue = new Refinement(value, type);
+      pushRefinement(trueCont, refinedValue);
+      push(falseCont);
+      return;
+    }
+
+    // If the condition is comparison with a constant, promote the other value.
+    if (call is InvokeMethod && call.selector == Selectors.equals) {
+      Primitive first = call.arguments[0].definition;
+      Primitive second = call.arguments[1].definition;
+      if (second is Constant && second.value.isNull) {
+        Refinement refinedTrue = new Refinement(first, nullType);
+        Refinement refinedFalse = new Refinement(first, nonNullType);
+        pushRefinement(trueCont, refinedTrue);
+        pushRefinement(falseCont, refinedFalse);
+        return;
+      }
+      if (first is Constant && first.value.isNull) {
+        Refinement refinedTrue = new Refinement(second, nullType);
+        Refinement refinedFalse = new Refinement(second, nonNullType);
+        pushRefinement(trueCont, refinedTrue);
+        pushRefinement(falseCont, refinedFalse);
+        return;
+      }
+      // For non-null constants, we can only refine in the true branch,
+      // since TypeMask has no complement type for other constants.
+      if (second is Constant) {
+        Refinement refinedTrue = new Refinement(first, getTypeOf(second.value));
+        pushRefinement(trueCont, refinedTrue);
+        push(falseCont);
+        return;
+      }
+      if (first is Constant) {
+        Refinement refinedTrue = new Refinement(second, getTypeOf(first.value));
+        pushRefinement(trueCont, refinedTrue);
+        push(falseCont);
+        return;
+      }
+    }
+
+    push(trueCont);
+    push(falseCont);
+  }
+
+  @override
+  Expression traverseLetCont(LetCont node) {
+    for (Continuation cont in node.continuations) {
+      if (cont.hasExactlyOneUse &&
+          (cont.firstRef.parent is InvokeMethod ||
+           cont.firstRef.parent is Branch)) {
+        // Do not push the continuation here.
+        // visitInvokeMethod and visitBranch will do that.
+      } else {
+        push(cont);
+      }
+    }
+    return node.body;
+  }
+}