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

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

Index: pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
diff --git a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
index b685c4582b9235c20c78583dc47cdbf5db06ba25..7a1850787ead40cbf62a296063868776deb7cf29 100644
--- a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
+++ b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
@@ -119,6 +119,40 @@ abstract class Definition<T extends Definition<T>> extends Node {
   }
 }
 
+class EffectiveUseIterator extends Iterator<Reference<Primitive>> {
+  Reference<Primitive> current;
+  Reference<Primitive> next;
+  final List<Primitive> stack = <Primitive>[];
+
+  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;
+        }
+      } else if (ref.parent is Refinement) {
+        stack.add(ref.parent);
+        ref = ref.next;
+      } else {
+        current = ref;
+        next = current.next;
+        return true;
+      }
+    }
+  }
+}
+
+class EffectiveUseIterable {
+  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.
@@ -153,6 +187,34 @@ abstract class Primitive extends Definition<Primitive> {
   /// 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.iterator.moveNext();

[sra1, 2015/09/02 18:24:52]

effectiveUses.isEmpty does the same.

[asgerf, 2015/09/02 18:46:58]

I originally couldn't bother to import dart:collection to make the iterable an
actual Iterable, but I guess there's no harm in doing that. It's now an
IterableBase and using .isEmpty.

+  }
 }
 
 /// Operands to invocations and primitives are always variables.  They point to
@@ -439,6 +501,28 @@ class InvokeConstructor extends CallExpression {
   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;

[sra1, 2015/09/02 18:24:52]

Is this adequate to keep it in order with respect to the 'witness' operation?

[asgerf, 2015/09/02 18:46:58]

Yes, but we might need the witness reference when we add more detailed side
effect information.

If the witness is an InvokeMethod that later gets rewritten to a pure expression
(e.g. constant-folded), then they might change places, but if that's the case,
then the original InvokeMethod could not throw, and therefore the refinement is
a no-op and is still safe.

+
+  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].
@@ -1201,6 +1285,7 @@ abstract class Visitor<T> {
   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);
@@ -1504,6 +1589,12 @@ class LeafVisitor implements Visitor {
     processReference(node.index);
     processReference(node.value);
   }
+
+  processRefinement(Refinement node) {}
+  visitRefinement(Refinement node) {
+    processRefinement(node);
+    processReference(node.value);
+  }
 }
 
 typedef void StackAction();