dart2js cps: Add instruction for bounds checks.

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

 // Copyright (c) 2015, 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.cps_ir.bounds_checker;
 
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart' show Pass;
 import 'octagon.dart';
 import '../constants/values.dart';
 import 'cps_fragment.dart';
 import 'type_mask_system.dart';
+import '../types/types.dart';
 import '../world.dart';
 import '../elements/elements.dart';
 import 'loop_effects.dart';
 
-
-
 /// Eliminates bounds checks when they can be proven safe.
 ///
 /// In general, this pass will try to eliminate any branch with arithmetic
 /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc.
 ///
 /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon
 /// analyzers, we do not use a closed matrix representation, but just maintain
 /// a bucket of constraints.  Constraints can therefore be added and removed
 /// on-the-fly without significant overhead.
 ///
@@ skipping 78 matching lines @@
     if (isUInt32(number)) {
       min = 0;
       max = MAX_UINT32;
     } else if (isNonNegativeInt(number)) {
       min = 0;
     }
     return valueOf.putIfAbsent(number, () => octagon.makeVariable(min, max));
   }
 
   /// Get a constraint variable representing the length of [indexableObject] at
-  /// program locations with the given [effectCounter].
-  SignedVariable getLength(Primitive indexableObject, int effectCounter) {
+  /// program locations with the given [effectNumber].
+  SignedVariable getLength(Primitive indexableObject, int effectNumber) {
     indexableObject = indexableObject.effectiveDefinition;
-    if (indexableObject.type != null &&
-        types.isDefinitelyFixedLengthIndexable(indexableObject.type)) {
-      // Always use the same effect counter if the length is immutable.
-      effectCounter = 0;
+    TypeMask type = indexableObject.type.nonNullable();
+    if (types.isDefinitelyFixedLengthIndexable(type)) {
+      // Always use the same effect number if the length is immutable.
+      effectNumber = 0;
     }
     return lengthOf
         .putIfAbsent(indexableObject, () => <int, SignedVariable>{})
-        .putIfAbsent(effectCounter, () => octagon.makeVariable(0, MAX_UINT32));
+        .putIfAbsent(effectNumber, () {
+            int length = types.getContainerLength(type);
+            if (length != null) {
+              return octagon.makeVariable(length, length);
+            } else {
+              return octagon.makeVariable(0, MAX_UINT32);
+            }
+        });
   }
 
   // ------------- CONSTRAINT HELPERS -----------------
 
   /// Puts the given constraint "in scope" by adding it to the octagon, and
   /// pushing a stack action that will remove it again.
   void applyConstraint(SignedVariable v1, SignedVariable v2, int k) {
     Constraint constraint = new Constraint(v1, v2, k);
     octagon.pushConstraint(constraint);
     pushAction(() => octagon.popConstraint(constraint));
@@ skipping 93 matching lines @@
     } else if (isDefinitelyGreaterThanOrEqualTo(v1, v2)) {
       makeGreaterThan(v1, v2);
     }
   }
 
   /// Return true if we can prove that `v1 <= v2`.
   bool isDefinitelyLessThanOrEqualTo(SignedVariable v1, SignedVariable v2) {
     return testConstraint(v1, v2.negated, 0);
   }
 
+  /// Return true if we can prove that `v1 < v2`.
+  bool isDefinitelyLessThan(SignedVariable v1, SignedVariable v2) {
+    return testConstraint(v1, v2.negated, -1);
+  }
+
   /// Return true if we can prove that `v1 >= v2`.
   bool isDefinitelyGreaterThanOrEqualTo(SignedVariable v1, SignedVariable v2) {
     return testConstraint(v2, v1.negated, 0);
   }
 
   bool isDefinitelyLessThanOrEqualToConstant(SignedVariable v1, int value) {
     // v1 <= value   <==>   v1 + v1 <= 2 * value
     return testConstraint(v1, v1, 2 * value);
   }
 
@@ skipping 208 matching lines @@
 
   int getIntConstant(Primitive prim) {
     if (prim is Constant && prim.value.isInt) {
       IntConstantValue constant = prim.value;
       return constant.primitiveValue;
     }
     return null;
   }
 
   @override
+  void visitRefinement(Refinement node) {
+    // In general we should get the container length of the refined type and
+    // add a constraint if we know the length after the refinement.
+    // However, our current type system removes container information when a
+    // type becomes part of a union, so this cannot happen.
+  }
+
+  @override
   void visitGetLength(GetLength node) {
     valueOf[node] = getLength(node.object.definition, currentEffectNumber);
   }
 
+  @override
+  void visitBoundsCheck(BoundsCheck node) {
+    if (node.checks == BoundsCheck.NONE) return;
+    assert(node.index != null); // Because there is at least one check.
+    Primitive object = node.object.definition;
+    SignedVariable length = node.length == null
+        ? null
+        : getValue(node.length.definition);
+    SignedVariable index = getValue(node.index.definition);
+    if (node.hasUpperBoundCheck) {
+      if (isDefinitelyLessThan(index, length)) {
+        node.checks &= ~BoundsCheck.UPPER_BOUND;
+      } else {
+        makeLessThan(index, length);
+      }
+    }
+    if (node.hasLowerBoundCheck) {
+      if (isDefinitelyGreaterThanOrEqualToConstant(index, 0)) {
+        node.checks &= ~BoundsCheck.LOWER_BOUND;
+      } else {
+        makeGreaterThanOrEqualToConstant(index, 0);
+      }
+    }
+    if (node.hasEmptinessCheck) {
+      if (isDefinitelyGreaterThanOrEqualToConstant(length, 1)) {
+        node.checks &= ~BoundsCheck.EMPTINESS;
+      } else {
+        makeGreaterThanOrEqualToConstant(length, 1);
+      }
+    }
+    if (!node.lengthUsedInCheck && node.length != null) {
+      node..length.unlink()..length = null;
+    }
+    if (node.checks == BoundsCheck.NONE) {
+      // We can't remove the bounds check node because it may still be used to
+      // restrict code motion.  But the index is no longer needed.
+      node..index.unlink()..index = null;
+    }
+  }
+
   void analyzeLoopEntry(InvokeContinuation node) {
     foundLoop = true;
     Continuation cont = node.continuation.definition;
     if (isStrongLoopPass) {
       for (int i = 0; i < node.arguments.length; ++i) {
         Parameter param = cont.parameters[i];
         if (!isInt(param)) continue;
         Primitive initialValue = node.arguments[i].definition;
         SignedVariable initialVariable = getValue(initialValue);
         Monotonicity mono = monotonicity[param];
@@ skipping 190 matching lines @@
     }
     return node.body;
   }
 }
 
 /// Lattice representing the known (weak) monotonicity of a loop variable.
 ///
 /// The lattice bottom is represented by `null` and represents the case where
 /// the loop variable never changes value during the loop.
 enum Monotonicity { NotMonotone, Increasing, Decreasing, }