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

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

 // Copyright (c) 2013, 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.ir_nodes;
 
+import 'dart:collection';
 import '../constants/values.dart' as values show ConstantValue;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
 import '../io/source_information.dart' show SourceInformation;
 import '../types/types.dart' show TypeMask;
 import '../universe/universe.dart' show Selector;
 
 import 'builtin_operator.dart';
 export 'builtin_operator.dart';
 
@@ skipping 96 matching lines @@
       previous = current;
       current = current.next;
     } while (current != null);
     previous.next = firstRef;
     if (firstRef != null) firstRef.previous = previous;
     firstRef = other.firstRef;
     other.firstRef = null;
   }
 }
 
+class EffectiveUseIterator extends Iterator<Reference<Primitive>> {
+  Reference<Primitive> current;
+  Reference<Primitive> next;
+  final List<Primitive> stack = <Primitive>[];

[Kevin Millikin (Google), 2015/09/03 10:21:06]

Probably clearer to make this List<Refinement>.

[asgerf, 2015/09/03 12:31:39]

Done.

+
+  EffectiveUseIterator(Primitive prim) : next = prim.firstRef;
+
+  bool moveNext() {
+    Reference<Primitive> ref = next;
+    while (true) {
+      if (ref == null) {
+        if (stack.isNotEmpty) {
+          ref = stack.removeLast().firstRef;
+        } else {
+          return false;

[Kevin Millikin (Google), 2015/09/03 10:21:06]

current should be null when the iterator has finished
(https://api.dartlang.org/1.12.0/dart-core/Iterator/current.html).

[asgerf, 2015/09/03 12:31:39]

Thanks, nice catch.

+        }
+      } else if (ref.parent is Refinement) {
+        stack.add(ref.parent);
+        ref = ref.next;
+      } else {
+        current = ref;
+        next = current.next;
+        return true;
+      }
+    }

[Kevin Millikin (Google), 2015/09/03 10:21:05]

I think of this algorithm as a pair of nested loops:

while (ref == null && stack.isNotEmpty) {
  ref = stack.removeLast().firstRef;
  while (ref != null && ref.parent is Refinement) {
    stack.add(ref.parent);
    ref = ref.next;
  }
}
if (ref == null) {
  current = next = null;
  return false;
}
current = ref;
next = ref.next;
return true;

[asgerf, 2015/09/03 12:31:39]

The problem is that 'next = ref.next' might be a Refinement, which then won't be
skipped in the next iteration because the relevant loop condition is hidden
behind irrelevant one.

I concede that the while(true) style is aesthetically grisly, but it's the only
robust, non-redundant implementation I can find.

+  }
+}
+
+class EffectiveUseIterable extends IterableBase<Reference<Primitive>> {
+  Primitive primitive;
+  EffectiveUseIterable(this.primitive);
+  EffectiveUseIterator get iterator => new EffectiveUseIterator(primitive);
+}
+
 /// A named value.
 ///
 /// The identity of the [Primitive] object is the name of the value.
 /// The subclass describes how to compute the value.
 ///
 /// All primitives except [Parameter] must be bound by a [LetPrim].
 abstract class Primitive extends Definition<Primitive> {
   /// The [VariableElement] or [ParameterElement] from which the primitive
   /// binding originated.
   Entity hint;
@@ skipping 14 matching lines @@
   /// observable side-effects.
   bool get isSafeForElimination;
 
   /// True if time-of-evaluation is irrelevant for the given primitive,
   /// assuming its inputs are the same values.
   bool get isSafeForReordering;
 
   /// The source information associated with this primitive.
   // TODO(johnniwinther): Require source information for all primitives.
   SourceInformation get sourceInformation => null;
+
+  /// If this is a [Refinement] node, returns the value being refined.
+  Primitive get effectiveDefinition => this;
+
+  /// True if the two primitives are (refinements of) the same value.
+  bool sameValue(Primitive other) {
+    return effectiveDefinition == other.effectiveDefinition;
+  }
+
+  /// Iterates all non-refinement uses of the primitive and all uses of
+  /// a [Refinement] of this primitive (transitively).
+  ///
+  /// Notes regarding concurrent modification:
+  /// - The current reference may safely be unlinked.
+  /// - Yet unvisited references may not be unlinked.
+  /// - References to this primitive created during iteration will not be seen.
+  /// - References to a refinement of this primitive may not be created during
+  ///   iteration.
+  EffectiveUseIterable get effectiveUses => new EffectiveUseIterable(this);
+
+  bool get hasMultipleEffectiveUses {
+    Iterator it = effectiveUses.iterator;
+    return it.moveNext() && it.moveNext();
+  }
+
+  bool get hasNoEffectiveUses {
+    return effectiveUses.isEmpty;
+  }
 }
 
 /// Operands to invocations and primitives are always variables.  They point to
 /// their definition and are doubly-linked into a list of occurrences.
 class Reference<T extends Definition<T>> {
   T definition;
   Reference<T> previous;
   Reference<T> next;
 
   /// A pointer to the parent node. Is null until set by optimization passes.
@@ skipping 266 matching lines @@
                     this.selector,
                     List<Primitive> args,
                     Continuation cont,
                     this.sourceInformation)
       : arguments = _referenceList(args),
         continuation = new Reference<Continuation>(cont);
 
   accept(Visitor visitor) => visitor.visitInvokeConstructor(this);
 }
 
+/// An alias for [value] in a context where the value is known to satisfy
+/// [type].
+///
+/// Refinement nodes are inserted before the type propagator pass and removed
+/// afterwards, so as not to complicate passes that don't reason about types,
+/// but need to reason about value references being identical (i.e. referring
+/// to the same primitive).
+class Refinement extends Primitive {
+  Reference<Primitive> value;
+  final TypeMask type;
+
+  Refinement(Primitive value, this.type)
+    : value = new Reference<Primitive>(value);
+
+  bool get isSafeForElimination => true;
+  bool get isSafeForReordering => false;
+
+  accept(Visitor visitor) => visitor.visitRefinement(this);
+
+  Primitive get effectiveDefinition => value.definition.effectiveDefinition;
+}
+
 /// An "is" type test.
 ///
 /// Returns `true` if [value] is an instance of [type].
 ///
 /// [type] must not be the [Object], `dynamic` or [Null] types (though it might
 /// be a type variable containing one of these types). This design is chosen
 /// to simplify code generation for type tests.
 class TypeTest extends Primitive {
   Reference<Primitive> value;
   final DartType type;
@@ skipping 742 matching lines @@
   T visitReifyRuntimeType(ReifyRuntimeType node);
   T visitReadTypeVariable(ReadTypeVariable node);
   T visitTypeExpression(TypeExpression node);
   T visitCreateInvocationMirror(CreateInvocationMirror node);
   T visitTypeTest(TypeTest node);
   T visitApplyBuiltinOperator(ApplyBuiltinOperator node);
   T visitApplyBuiltinMethod(ApplyBuiltinMethod node);
   T visitGetLength(GetLength node);
   T visitGetIndex(GetIndex node);
   T visitSetIndex(SetIndex node);
+  T visitRefinement(Refinement node);
 
   // Support for literal foreign code.
   T visitForeignCode(ForeignCode node);
 }
 
 /// Visits all non-recursive children of a CPS term, i.e. anything
 /// not of type [Expression] or [Continuation].
 ///
 /// The `process*` methods are called in pre-order for every node visited.
 /// These can be overridden without disrupting the visitor traversal.
@@ skipping 283 matching lines @@
     processReference(node.index);
   }
 
   processSetIndex(SetIndex node) {}
   visitSetIndex(SetIndex node) {
     processSetIndex(node);
     processReference(node.object);
     processReference(node.index);
     processReference(node.value);
   }
+
+  processRefinement(Refinement node) {}
+  visitRefinement(Refinement node) {
+    processRefinement(node);
+    processReference(node.value);
+  }
 }
 
 typedef void StackAction();
 
 /// Calls `process*` for all nodes in a tree.
 /// For simple usage, only override the `process*` methods.
 ///
 /// To avoid deep recursion, this class uses an "action stack" containing
 /// callbacks to be invoked after the processing of some term has finished.
 ///
@@ skipping 111 matching lines @@
 /// Visit a just-deleted subterm and unlink all [Reference]s in it.
 class RemovalVisitor extends RecursiveVisitor {
   processReference(Reference reference) {
     reference.unlink();
   }
 
   static void remove(Node node) {
     (new RemovalVisitor()).visit(node);
   }
 }