dart2js cps: Direct access on JS arrays.

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

Index: pkg/compiler/lib/src/cps_ir/type_propagation.dart
diff --git a/pkg/compiler/lib/src/cps_ir/type_propagation.dart b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
index 091ca5368398ae3efef88918d6842c78d09171a5..3d3b3e0d4bfe4dc3c237b8188124ec7247a1b6bd 100644
--- a/pkg/compiler/lib/src/cps_ir/type_propagation.dart
+++ b/pkg/compiler/lib/src/cps_ir/type_propagation.dart
@@ -17,6 +17,8 @@ import '../elements/elements.dart';
 import '../dart2jslib.dart' show ClassWorld, World;
 import '../universe/universe.dart';
 import '../js_backend/js_backend.dart' show JavaScriptBackend;
+import '../io/source_information.dart' show SourceInformation;
+import 'cps_fragment.dart';
 
 enum AbstractBool {
   True, False, Maybe, Nothing
@@ -25,6 +27,7 @@ enum AbstractBool {
 class TypeMaskSystem {
   final TypesTask inferrer;
   final World classWorld;
+  final JavaScriptBackend backend;
 
   TypeMask get dynamicType => inferrer.dynamicType;
   TypeMask get typeType => inferrer.typeType;
@@ -37,13 +40,15 @@ class TypeMaskSystem {
   TypeMask get listType => inferrer.listType;
   TypeMask get mapType => inferrer.mapType;
   TypeMask get nonNullType => inferrer.nonNullType;
+  TypeMask get mutableNativeListType => backend.mutableArrayType;
 
   TypeMask numStringBoolType;
 
   // TODO(karlklose): remove compiler here.
   TypeMaskSystem(dart2js.Compiler compiler)
     : inferrer = compiler.typesTask,
-      classWorld = compiler.world {
+      classWorld = compiler.world,
+      backend = compiler.backend {
     numStringBoolType =
       new TypeMask.unionOf(<TypeMask>[numType, stringType, boolType],
                            classWorld);
@@ -137,6 +142,31 @@ class TypeMaskSystem {
     return areDisjoint(t, doubleType);
   }
 
+  bool isDefinitelyInt(TypeMask t, {bool allowNull: false}) {
+    if (!allowNull && t.isNullable) return false;
+    return t.satisfies(backend.jsIntClass, classWorld);
+  }
+
+  bool isDefinitelyNativeList(TypeMask t, {bool allowNull: false}) {
+    if (!allowNull && t.isNullable) return false;
+    return t.satisfies(backend.jsArrayClass, classWorld);
+  }
+
+  bool isDefinitelyMutableNativeList(TypeMask t, {bool allowNull: false}) {
+    if (!allowNull && t.isNullable) return false;
+    return t.satisfies(backend.jsMutableArrayClass, classWorld);
+  }
+
+  bool isDefinitelyFixedNativeList(TypeMask t, {bool allowNull: false}) {
+    if (!allowNull && t.isNullable) return false;
+    return t.satisfies(backend.jsFixedArrayClass, classWorld);
+  }
+
+  bool isDefinitelyExtendableNativeList(TypeMask t, {bool allowNull: false}) {
+    if (!allowNull && t.isNullable) return false;
+    return t.satisfies(backend.jsExtendableArrayClass, classWorld);
+  }
+
   bool areDisjoint(TypeMask leftType, TypeMask rightType) {
     TypeMask intersection = leftType.intersection(rightType, classWorld);
     return intersection.isEmpty && !intersection.isNullable;
@@ -265,6 +295,39 @@ class ConstantPropagationLattice {
       typeSystem.isDefinitelyNotNonIntegerDouble(value.type);
   }
 
+  bool isDefinitelyInt(AbstractValue value,
+                       {bool allowNull: false}) {
+    return value.isNothing ||
+        typeSystem.isDefinitelyInt(value.type, allowNull: allowNull);
+  }
+
+  bool isDefinitelyNativeList(AbstractValue value,
+                              {bool allowNull: false}) {
+    return value.isNothing ||
+        typeSystem.isDefinitelyNativeList(value.type, allowNull: allowNull);
+  }
+
+  bool isDefinitelyMutableNativeList(AbstractValue value,
+                                     {bool allowNull: false}) {
+    return value.isNothing ||
+         typeSystem.isDefinitelyMutableNativeList(value.type,
+                                                  allowNull: allowNull);
+  }
+
+  bool isDefinitelyFixedNativeList(AbstractValue value,
+                                   {bool allowNull: false}) {
+    return value.isNothing ||
+        typeSystem.isDefinitelyFixedNativeList(value.type,
+                                               allowNull: allowNull);
+  }
+
+  bool isDefinitelyExtendableNativeList(AbstractValue value,
+                                        {bool allowNull: false}) {
+    return value.isNothing ||
+        typeSystem.isDefinitelyExtendableNativeList(value.type,
+                                                    allowNull: allowNull);
+  }
+
   /// Returns whether the given [value] is an instance of [type].
   ///
   /// Since [value] and [type] are not always known, [AbstractBool.Maybe] is
@@ -357,7 +420,19 @@ class ConstantPropagationLattice {
       if (result == null) return anything;
       return constant(result);
     }
-    return null; // TODO(asgerf): Look up type?
+    // TODO(asgerf): Handle remaining operators and the UIntXX types.
+    switch (operator.kind) {
+      case BinaryOperatorKind.ADD:
+      case BinaryOperatorKind.SUB:
+      case BinaryOperatorKind.MUL:
+        if (isDefinitelyInt(left) && isDefinitelyInt(right)) {
+          return nonConstant(typeSystem.intType);
+        }
+        return null;
+
+      default:
+        return null; // The caller will use return type from type inference.
+    }
   }
 
   AbstractValue stringConstant(String value) {
@@ -764,6 +839,182 @@ class TransformingVisitor extends RecursiveVisitor {
     }
   }
 
+  /// Create a check that throws if [index] is not a valid index on [list].
+  /// 
+  /// This function assumes that [index] is an integer.
+  ///
+  /// Returns a CPS fragment whose context is the branch where no error
+  /// was thrown.
+  CpsFragment makeBoundsCheck(Primitive list,
+                              Primitive index,
+                              SourceInformation sourceInfo) {
+    CpsFragment cps = new CpsFragment(sourceInfo);
+    Continuation fail = cps.letCont();
+    Primitive isTooSmall = cps.applyBuiltin(
+        BuiltinOperator.NumLt,
+        <Primitive>[index, cps.makeZero()]);
+    cps.ifTrue(isTooSmall).invokeContinuation(fail);
+    Primitive isTooLarge = cps.applyBuiltin(
+        BuiltinOperator.NumGe,
+        <Primitive>[index, cps.letPrim(new GetLength(list))]);
+    cps.ifTrue(isTooLarge).invokeContinuation(fail);
+    cps.insideContinuation(fail).invokeStaticThrower(
+        backend.getThrowIndexOutOfBoundsError(),
+        <Primitive>[list, index]);
+    return cps;
+  }
+
+  /// Create a check that throws if the length of [list] is not equal to
+  /// [originalLength].
+  ///
+  /// Returns a CPS fragment whose context is the branch where no error
+  /// was thrown.
+  CpsFragment makeConcurrentModificationCheck(Primitive list,
+                                              Primitive originalLength,
+                                              SourceInformation sourceInfo) {
+    CpsFragment cps = new CpsFragment(sourceInfo);
+    Primitive lengthChanged = cps.applyBuiltin(
+        BuiltinOperator.StrictNeq,
+        <Primitive>[originalLength, cps.letPrim(new GetLength(list))]);
+    cps.ifTrue(lengthChanged).invokeStaticThrower(
+        backend.getThrowConcurrentModificationError(),
+        <Primitive>[list]);
+    return cps;
+  }
+
+  /// Counts number of index accesses on [list] and determines based on
+  /// that number if we should try to inline them.
+  ///
+  /// This is a short-term solution to avoid inserting a lot of bounds checks,
+  /// since there is currently no optimization for eliminating them.
+  bool hasTooManyIndexAccesses(Primitive list) {
+    int count = 0;
+    for (Reference ref = list.firstRef; ref != null; ref = ref.next) {
+      Node use = ref.parent;
+      if (use is InvokeMethod) {
+        if ((use.selector.isIndex || use.selector.isIndexSet) &&

[karlklose, 2015/07/08 08:39:24]

Merge the two if statements.

[asgerf, 2015/07/08 10:28:37]

Done.

+            getDartReceiver(use) == list) {
+          ++count;
+        }
+      } else if (use is GetIndex && use.object.definition == list) {

[karlklose, 2015/07/08 08:39:24]

Merge these two conditions?

 if ((use is GetIndex || use is SetIndex) && use.object.definition == list) {
... }

Maybe these two classes should implement an interface like:
  abstract class IndexArrayOperation {
    final Reference<Primitive> object;
  }

[asgerf, 2015/07/08 10:28:37]

As you foresaw it creates a static type warning because type promotion cannot
promote the type of 'use' to something with an 'object' getter.

I'm not too keen on adding another "union supertype" (for lack of a better word)
unless there is a strong case for adding it. They are very useful, but it tends
to go badly when there are many of them.

+        ++count;
+      } else if (use is SetIndex && use.object.definition == list) {
+        ++count;
+      }
+      if (count > 2) return true;
+    }
+    return false;
+  }
+
+  bool specializeArrayAccess(InvokeMethod node) {

[karlklose, 2015/07/08 08:39:24]

Please document the meaning of the returned value.

[asgerf, 2015/07/08 10:28:37]

Done.

+    Primitive list = getDartReceiver(node);
+    AbstractValue listValue = getValue(list);
+    // Ensure that the object is a native list or null.
+    if (!lattice.isDefinitelyNativeList(listValue, allowNull: true)) {
+      return false;
+    }
+    bool isFixedLength = 
+        lattice.isDefinitelyFixedNativeList(listValue, allowNull: true);
+    bool isMutable =
+        lattice.isDefinitelyMutableNativeList(listValue, allowNull: true);
+    SourceInformation sourceInfo = node.sourceInformation;
+    Continuation cont = node.continuation.definition;
+    switch (node.selector.name) {
+      case 'length':
+        if (!node.selector.isGetter) return false;
+        CpsFragment cps = new CpsFragment(sourceInfo);
+        cps.invokeContinuation(cont, [cps.letPrim(new GetLength(list))]);
+        replaceSubtree(node, cps.result);
+        visit(cps.result);
+        return true;
+
+      case '[]':
+        if (listValue.isNullable) return false;
+        if (hasTooManyIndexAccesses(list)) return false;
+        Primitive index = getDartArgument(node, 0);
+        if (!lattice.isDefinitelyInt(getValue(index))) return false;
+        CpsFragment cps = makeBoundsCheck(list, index, sourceInfo);
+        GetIndex get = cps.letPrim(new GetIndex(list, index));
+        cps.invokeContinuation(cont, [get]);
+        replaceSubtree(node, cps.result);
+        visit(cps.result);
+        return true;
+
+      case '[]=':
+        if (listValue.isNullable) return false;
+        if (hasTooManyIndexAccesses(list)) return false;
+        Primitive index = getDartArgument(node, 0);
+        Primitive value = getDartArgument(node, 1);
+        if (!isMutable) return false;
+        if (!lattice.isDefinitelyInt(getValue(index))) return false;
+        CpsFragment cps = makeBoundsCheck(list, index, sourceInfo);
+        cps.letPrim(new SetIndex(list, index, value));
+        assert(cont.parameters.single.hasNoUses);
+        cont.parameters.clear();
+        cps.invokeContinuation(cont, []);
+        replaceSubtree(node, cps.result);
+        visit(cps.result);
+        return true;
+
+      case 'forEach':
+        if (!node.selector.isCall ||
+            node.selector.positionalArgumentCount != 1 ||
+            node.selector.namedArgumentCount != 0) {
+          return false;
+        }
+        Primitive callback = getDartArgument(node, 0);
+        // Rewrite to:
+        //   var originalLength = array.length, i = 0;
+        //   while (i < array.length) {
+        //     callback(array[i]);
+        //     if (array.length !== originalLength) throw;
+        //     i = i + 1;
+        //   }
+        CpsFragment cps = new CpsFragment(sourceInfo);
+        Primitive originalLength = cps.letPrim(new GetLength(list));
+        originalLength.hint = new OriginalLengthEntity();
+
+        // Build a loop.
+        Primitive loopIndex = new Parameter(new LoopIndexEntity());
+        Continuation loop = cps.beginLoop([loopIndex], [cps.makeZero()]);
+
+        // Check for loop exit.
+        Primitive loopCondition = cps.applyBuiltin(
+            BuiltinOperator.NumLt,
+            [loopIndex, cps.letPrim(new GetLength(list))]);
+        CpsFragment exitBranch = cps.ifFalse(loopCondition);
+        exitBranch.invokeContinuation(cont, [exitBranch.makeNull()]);
+
+        // Invoke the callback.
+        Primitive arrayItem = cps.letPrim(new GetIndex(list, loopIndex));
+        cps.invokeMethod(callback,
+                         new Selector.callClosure(1),
+                         getValue(callback).type,
+                         [arrayItem]);
+
+        // Check for concurrent modification, unless the list is fixed-length.
+        if (!isFixedLength) {
+          cps.append(
+            makeConcurrentModificationCheck(list, originalLength, sourceInfo));
+        }
+
+        // Increment i and continue the loop.
+        Primitive addOne = cps.applyBuiltin(
+            BuiltinOperator.NumAdd,
+            [loopIndex, cps.makeOne()]);
+        cps.continueLoop(loop, [addOne]);
+
+        replaceSubtree(node, cps.result);
+        visit(cps.result);
+        return true;
+
+      // TODO(asgerf): Rewrite 'iterator', 'add', 'removeLast', ...
+
+      default:
+        return false;
+    }
+  }
+
   /// If [prim] is the parameter to a call continuation, returns the
   /// corresponding call.
   Invoke getInvocationWithResult(Primitive prim) {
@@ -847,6 +1098,10 @@ class TransformingVisitor extends RecursiveVisitor {
     Invoke tearOffInvoke = getInvocationWithResult(tearOff);
     if (tearOffInvoke is InvokeMethod && tearOffInvoke.selector.isGetter) {
       Selector getter = tearOffInvoke.selector;
+
+      // TODO(asgerf): Support torn-off intercepted methods.
+      if (isInterceptedSelector(getter)) return false;
+
       Continuation getterCont = tearOffInvoke.continuation.definition;
 
       // TODO(asgerf): Support torn-off intercepted methods.
@@ -905,6 +1160,7 @@ class TransformingVisitor extends RecursiveVisitor {
     if (constifyExpression(node)) return;

[karlklose, 2015/07/08 08:39:24]

Maybe make this one if statement and add a comment that we generated specialized
code for that method call.

[asgerf, 2015/07/08 10:28:37]

I feel it's misleading to use the || operator here.

     if (specializeOperatorCall(node)) return;
     if (specializeFieldAccess(node)) return;
+    if (specializeArrayAccess(node)) return;
     if (specializeClosureCall(node)) return;
 
     AbstractValue receiver = getValue(node.receiver.definition);
@@ -1075,6 +1331,10 @@ class TransformingVisitor extends RecursiveVisitor {
     node.objectIsNotNull = getValue(node.object.definition).isDefinitelyNotNull;
   }
 
+  void visitGetLength(GetLength node) {
+    node.objectIsNotNull = getValue(node.object.definition).isDefinitelyNotNull;
+  }
+
   void visitLetPrim(LetPrim node) {
     AbstractValue value = getValue(node.primitive);
     if (node.primitive is! Constant && value.isConstant) {
@@ -1127,6 +1387,7 @@ class TransformingVisitor extends RecursiveVisitor {
         !cont.isRecursive &&
         !node.isEscapingTry) {
       for (int i = 0; i < node.arguments.length; ++i) {
+        node.arguments[i].definition.useElementAsHint(cont.parameters[i].hint);
         node.arguments[i].definition.substituteFor(cont.parameters[i]);
         node.arguments[i].unlink();
       }
@@ -1471,7 +1732,13 @@ class TypePropagationVisitor implements Visitor {
       case BuiltinOperator.NumAnd:
       case BuiltinOperator.NumOr:
       case BuiltinOperator.NumXor:
-        setValue(node, nonConstant(typeSystem.numType));
+        AbstractValue left = getValue(node.arguments[0].definition);
+        AbstractValue right = getValue(node.arguments[1].definition);
+        if (lattice.isDefinitelyInt(left) && lattice.isDefinitelyInt(right)) {
+          setValue(node, nonConstant(typeSystem.intType));
+        } else {
+          setValue(node, nonConstant(typeSystem.numType));
+        }
         break;
 
       case BuiltinOperator.NumLt:
@@ -1599,7 +1866,7 @@ class TypePropagationVisitor implements Visitor {
   void visitLiteralList(LiteralList node) {
     // Constant lists are translated into (Constant ListConstant(...)) IR nodes,
     // and thus LiteralList nodes are NonConst.
-    setValue(node, nonConstant(typeSystem.listType));
+    setValue(node, nonConstant(typeSystem.mutableNativeListType));
   }
 
   void visitLiteralMap(LiteralMap node) {
@@ -1756,6 +2023,21 @@ class TypePropagationVisitor implements Visitor {
       setValue(returnValue, nonConstant(node.type));
     }
   }
+
+  @override
+  void visitGetLength(GetLength node) {
+    setValue(node, nonConstant(typeSystem.intType));
+  }
+
+  @override
+  void visitGetIndex(GetIndex node) {
+    setValue(node, nonConstant());
+  }
+
+  @override
+  void visitSetIndex(SetIndex node) {
+    setValue(node, nonConstant());
+  }
 }
 
 /// Represents the abstract value of a primitive value at some point in the
@@ -1787,8 +2069,16 @@ class AbstractValue {
   AbstractValue.constantValue(ConstantValue constant, TypeMask type)
       : this._internal(CONSTANT, constant, type);
 
-  AbstractValue.nonConstant(TypeMask type)
-      : this._internal(NONCONST, null, type);
+  factory AbstractValue.nonConstant(TypeMask type) {
+    if (type.isEmpty) {
+      if (type.isNullable)
+        return new AbstractValue.constantValue(new NullConstantValue(), type);
+      else
+        return new AbstractValue.nothing();
+    } else {
+      return new AbstractValue._internal(NONCONST, null, type);
+    }
+  }
 
   bool get isNothing  => (kind == NOTHING);
   bool get isConstant => (kind == CONSTANT);
@@ -1825,6 +2115,22 @@ abstract class InternalMethod {
   static const String Stringify = 'S';
 }
 
+/// Suggested name for a synthesized loop index.
+class LoopIndexEntity extends Entity {
+  String get name => 'i';
+}
+
+/// Suggested name for the current element of a list being iterated.
+class LoopItemEntity extends Entity {
+  String get name => 'current';
+}
+
+/// Suggested name for the original length of a list, for use in checks
+/// for concurrent modification.
+class OriginalLengthEntity extends Entity {
+  String get name => 'length';
+}
+
 class ResetAnalysisInfo extends RecursiveVisitor {
   Set<Node> reachableNodes;
   Map<Definition, AbstractValue> values;