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..7f0d67e4b2e0e8b185f72d4ca7e7c41cbcc0c668 100644
--- a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
+++ b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
@@ -3,6 +3,7 @@
 // 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';
@@ -119,6 +120,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>[];

[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.
@@ -153,6 +188,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.isEmpty;
+  }
 }
 
 /// Operands to invocations and primitives are always variables.  They point to
@@ -439,6 +502,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;
+
+  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 +1286,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 +1590,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();