dart2js cps: Add instruction for bounds checks.

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;
 import '../dart_types.dart' show DartType, InterfaceType, TypeVariableType;
 import '../elements/elements.dart';
 import '../io/source_information.dart' show SourceInformation;
@@ skipping 216 matching lines @@
   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.
+  /// 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.
   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).
   ///
@@ skipping 449 matching lines @@
 
   accept(Visitor visitor) => visitor.visitRefinement(this);
 
   Primitive get effectiveDefinition => value.definition.effectiveDefinition;
 
   void setParentPointers() {
     value.parent = this;
   }
 }
 
+/// 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].
 ///
 /// [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 dartType;
@@ skipping 369 matching lines @@
   bool get isSafeForElimination => objectIsNotNull;
   bool get isSafeForReordering => false;
 
   accept(Visitor v) => v.visitGetLength(this);
 
   void setParentPointers() {
     object.parent = this;
   }
 }
 
-/// 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;
   final Reference<Primitive> index;
 
   /// True if the object is known not to be null.
   bool objectIsNotNull = false;
 
   GetIndex(Primitive object, Primitive index)
       : this.object = new Reference<Primitive>(object),
@@ skipping 616 matching lines @@
   T visitTypeExpression(TypeExpression node);
   T visitCreateInvocationMirror(CreateInvocationMirror node);
   T visitTypeTest(TypeTest node);
   T visitTypeTestViaFlag(TypeTestViaFlag 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);
+  T visitBoundsCheck(BoundsCheck node);
 
   // Support for literal foreign code.
   T visitForeignCode(ForeignCode node);
 }
 
 /// Recursively visits all children of a CPS term.
 ///
 /// The user of the class is responsible for avoiding stack overflows from
 /// deep recursion, e.g. by overriding methods to cut off recursion at certain
 /// points.
@@ skipping 298 matching lines @@
     processReference(node.object);
     processReference(node.index);
     processReference(node.value);
   }
 
   processRefinement(Refinement node) {}
   visitRefinement(Refinement node) {
     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();
 
 /// 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 113 matching lines @@
 /// Visit a just-deleted subterm and unlink all [Reference]s in it.
 class RemovalVisitor extends TrampolineRecursiveVisitor {
   processReference(Reference reference) {
     reference.unlink();
   }
 
   static void remove(Node node) {
     (new RemovalVisitor()).visit(node);
   }
 }