Allow bound check elimination to eliminate checks when both array length and index boundaries are e…

runtime/vm/intermediate_language.cc

 // Copyright (c) 2012, 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 2103 matching lines @@
 
 RangeBoundary RangeBoundary::UpperBound() const {
   if (IsConstant()) return *this;
   if (symbol()->range() == NULL) return MaxSmi();
   return Add(symbol()->range()->max().UpperBound(),
              RangeBoundary::FromConstant(offset_),
              MaxSmi());
 }
 
 
+static bool AreEqualDefinitions(Definition* a, Definition* b) {
+  return (a == b) || (!a->AffectedBySideEffect() && a->Equals(b));
+}
+
+
 // Returns true if two range boundaries refer to the same symbol.
 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
-  if (!a.IsSymbol() || !b.IsSymbol()) return false;
-  if (a.symbol() == b.symbol()) return true;
-
-  return !a.symbol()->AffectedBySideEffect() &&
-      a.symbol()->Equals(b.symbol());
+  return a.IsSymbol() && b.IsSymbol() &&
+      AreEqualDefinitions(a.symbol(), b.symbol());
 }
 
 
 // Returns true if range has a least specific minimum value.
 static bool IsMinSmi(Range* range) {
   return (range == NULL) ||
       (range->min().IsConstant() &&
        (range->min().value() <= Smi::kMinValue));
 }
 
@@ skipping 305 matching lines @@
 
 
 static bool IsArrayLength(Definition* defn) {
   LoadFieldInstr* load = defn->AsLoadField();
   return (load != NULL) &&
       ((load->recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
        (load->recognized_kind() == MethodRecognizer::kImmutableArrayLength));
 }
 
 
-static bool IsLengthOf(Definition* defn, Definition* array) {
-  return IsArrayLength(defn) &&
-      (defn->AsLoadField()->value()->definition() == array);
-}
-
-
 void BinarySmiOpInstr::InferRange() {
   // TODO(vegorov): canonicalize BinarySmiOp to always have constant on the
   // right and a non-constant on the left.
   Definition* left_defn = left()->definition();
 
   Range* left_range = left_defn->range();
   Range* right_range = right()->definition()->range();
 
   if ((left_range == NULL) || (right_range == NULL)) {
     range_ = new Range(RangeBoundary::MinSmi(), RangeBoundary::MaxSmi());
@@ skipping 55 matching lines @@
   ASSERT(!min.IsUnknown() && !max.IsUnknown());
   set_overflow(min.LowerBound().Overflowed() || max.UpperBound().Overflowed());
 
   if (min.IsConstant()) min.Clamp();
   if (max.IsConstant()) max.Clamp();
 
   range_ = new Range(min, max);
 }
 
 
-bool CheckArrayBoundInstr::IsRedundant() {
+bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
   // Check that array has an immutable length.
   if ((array_type() != kArrayCid) && (array_type() != kImmutableArrayCid)) {
     return false;
   }
 
   Range* index_range = index()->definition()->range();
 
   // Range of the index is unknown can't decide if the check is redundant.
   if (index_range == NULL) return false;
 
   // Range of the index is not positive. Check can't be redundant.
   if (Range::ConstantMin(index_range).value() < 0) return false;
 
   RangeBoundary max = CanonicalizeBoundary(index_range->max(),
                                            RangeBoundary::OverflowedMaxSmi());
+
+  if (max.Overflowed()) return false;
+
+  // Try to compare constant boundaries.
+  if (max.UpperBound().value() < length.LowerBound().value()) {
+    return true;
+  }
+
+  length = CanonicalizeBoundary(length, RangeBoundary::OverflowedMaxSmi());
+  if (length.Overflowed()) return false;
+
+  // Try symbolic comparison.
   do {
-    if (max.IsSymbol() &&
-        (max.offset() < 0) &&
-        IsLengthOf(max.symbol(), array()->definition())) {
-      return true;
-    }
-  } while (CanonicalizeMaxBoundary(&max));
+    if (DependOnSameSymbol(max, length)) return max.offset() < length.offset();
+  } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length));
 
   // Failed to prove that maximum is bounded with array length.
   return false;
 }
 
 
 #undef __
 
 }  // namespace dart