dart2js cps: Add instruction for bounds checks.

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 53a1a98b7f5c118b732ee793c3eb30e338ef2594..1c60c5a66ecd8128b5018b460478cf8a8c81b54c 100644
--- a/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
+++ b/pkg/compiler/lib/src/cps_ir/cps_ir_nodes.dart
@@ -234,7 +234,13 @@ abstract class Primitive extends Variable<Primitive> {
   // TODO(johnniwinther): Require source information for all primitives.
   SourceInformation get sourceInformation => null;
 
-  /// If this is a [Refinement] node, returns the value being refined.
+  /// If this is a [Refinement] or [BoundsCheck] returns the value being refined
+  /// or the indexable object being checked.
+  ///
+  /// Those instructions all return the corresponding operand directly, and
+  /// this getter can be used to get (closer to) where the value came from.
+  //
+  // TODO(asgerf): Also do this for [TypeCast]?
   Primitive get effectiveDefinition => this;
 
   /// True if the two primitives are (refinements of) the same value.
@@ -704,6 +710,101 @@ class Refinement extends Primitive {
   }
 }
 
+/// Checks that [index] is a valid index on a given indexable [object].
+///
+/// [index] must be an integer, and [object] must refer to null or an indexable
+/// object, and [length] must be the length of [object] at the time of the
+/// check.
+///
+/// Returns [object] so the bounds check can be used to restrict code motion.
+/// It is possible to have a bounds check node that performs no checks but
+/// is retained to restrict code motion.
+///
+/// The [index] reference may be null if there are no checks to perform,
+/// and the [length] reference may be null if there is no upper bound or
+/// emptiness check.
+///
+/// If a separate code motion guard for the index is required, e.g. because it
+/// must be known to be non-negative in an operator that does not involve
+/// [object], a [Refinement] can be created for it with the non-negative integer
+/// type.
+class BoundsCheck extends Primitive {
+  final Reference<Primitive> object;
+  Reference<Primitive> index;
+  Reference<Primitive> length; // FIXME write docs for length
+  int checks;
+  final SourceInformation sourceInformation;
+
+  /// If true, check that `index >= 0`.
+  bool get hasLowerBoundCheck => checks & LOWER_BOUND != 0;
+
+  /// If true, check that `index < object.length`.
+  bool get hasUpperBoundCheck => checks & UPPER_BOUND != 0;
+
+  /// If true, check that `object.length !== 0`.
+  ///
+  /// Equivalent to a lower bound check with `object.length - 1` as the index,
+  /// but this check is faster.
+  ///
+  /// Although [index] is not used in the condition, it is used to generate
+  /// the thrown error.  Currently it is always `-1` for emptiness checks,
+  /// because that corresponds to `object.length - 1` in the error case.
+  bool get hasEmptinessCheck => checks & EMPTINESS != 0;
+
+  /// True of the [length] is needed.

[sra1, 2015/12/10 19:09:40]

... is needed to perform the check.

Maybe call it 'lengthUsedInCheck'.

EMPTINESS uses node.length.definition in Finalize.

[asgerf, 2015/12/11 12:16:31]

Done.

+  bool get checkNeedsLength => checks & (UPPER_BOUND | EMPTINESS) != 0;
+
+  bool get hasNoChecks => checks == NONE;
+
+  static const int UPPER_BOUND = 1 << 0;
+  static const int LOWER_BOUND = 1 << 1;
+  static const int EMPTINESS = 1 << 2;

[sra1, 2015/12/10 19:09:39]

What is EMPTINESS?

[asgerf, 2015/12/11 12:16:31]

I thought it would be clear from hasEmptinessCheck. I added a comment
redirecting there, and made it more clear in the doc for BoundsCheck that there
is a third kind of bounds check.

It is used to generate pop():

y = xs.removeLast()

==>

if (xs.length === 0) return ioore(xs, -1);
var y = xs.pop()

+  static const int BOTH_BOUNDS = UPPER_BOUND | LOWER_BOUND;
+  static const int NONE = 0;
+
+  BoundsCheck(Primitive object, Primitive index, Primitive length,
+      [this.checks = BOTH_BOUNDS, this.sourceInformation])
+      : this.object = new Reference<Primitive>(object),
+        this.index = new Reference<Primitive>(index),
+        this.length = new Reference<Primitive>(length);
+
+  BoundsCheck.noCheck(Primitive object, [this.sourceInformation])
+      : this.object = new Reference<Primitive>(object),
+        this.checks = NONE;
+
+  accept(Visitor visitor) => visitor.visitBoundsCheck(this);
+
+  void setParentPointers() {
+    object.parent = this;
+    if (index != null) {
+      index.parent = this;
+    }
+    if (length != null) {
+      length.parent = this;
+    }
+  }
+
+  String get checkString {
+    if (hasUpperBoundCheck && hasLowerBoundCheck) {
+      return 'upper-lower-checks';
+    } else if (hasUpperBoundCheck) {
+      return 'upper-check';
+    } else if (hasLowerBoundCheck) {
+      return 'lower-check';
+    } else if (hasEmptinessCheck) {
+      return 'emptiness-check';
+    } else {
+      return 'no-check';
+    }
+  }
+
+  bool get isSafeForElimination => checks == NONE;
+  bool get isSafeForReordering => false;
+  bool get hasValue => true; // Can be referenced to restrict code motion.
+
+  Primitive get effectiveDefinition => object.definition.effectiveDefinition;
+}
+
 /// An "is" type test.
 ///
 /// Returns `true` if [value] is an instance of [type].
@@ -1093,9 +1194,9 @@ class GetLength extends Primitive {
   }
 }
 
-/// Read an entry from a string or native list.
+/// Read an entry from an indexable object.
 ///
-/// [object] must be null or a native list or a string, and [index] must be
+/// [object] must be null or an indexable object, and [index] must be
 /// an integer.
 class GetIndex extends Primitive {
   final Reference<Primitive> object;
@@ -1732,6 +1833,7 @@ abstract class Visitor<T> {
   T visitGetIndex(GetIndex node);
   T visitSetIndex(SetIndex node);
   T visitRefinement(Refinement node);
+  T visitBoundsCheck(BoundsCheck node);
 
   // Support for literal foreign code.
   T visitForeignCode(ForeignCode node);
@@ -2050,6 +2152,18 @@ class DeepRecursiveVisitor implements Visitor {
     processRefinement(node);
     processReference(node.value);
   }
+
+  processBoundsCheck(BoundsCheck node) {}
+  visitBoundsCheck(BoundsCheck node) {
+    processBoundsCheck(node);
+    processReference(node.object);
+    if (node.index != null) {
+      processReference(node.index);
+    }
+    if (node.length != null) {
+      processReference(node.length);
+    }
+  }
 }
 
 typedef void StackAction();