Simple array bounds check elimination on top of range analysis framework.

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 2059 matching lines @@
   for (Environment::DeepIterator it(copy); !it.Done(); it.Advance()) {
     Value* value = it.CurrentValue();
     value->set_instruction(instr);
     value->set_use_index(use_index++);
     value->AddToEnvUseList();
   }
   instr->env()->outer_ = copy;
 }
 
 
+RangeBoundary RangeBoundary::FromDefinition(Definition* defn, intptr_t offs) {
+  if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) {
+    return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value());
+  }
+  return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
+}
+
+
 RangeBoundary RangeBoundary::LowerBound() const {
   if (IsConstant()) return *this;
   if (symbol()->range() == NULL) return MinSmi();
   return Add(symbol()->range()->min().LowerBound(),
              RangeBoundary::FromConstant(offset_),
              MinSmi());
 }
 
 
 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 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() &&
+      !b.symbol()->AffectedBySideEffect() &&
+      a.symbol()->Equals(b.symbol());

[Florian Schneider, 2012/10/26 11:10:07]

I think !a->AffecteedBySideEffect() &&a->Equals(b) implies
!b->AffecteedBySideEffect().

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+}
+
+
+static bool IsMinSmi(Range* range) {
+  return (range == NULL) ||
+      (range->min().IsConstant() &&
+       (range->min().value() <= Smi::kMinValue));
+}
+
+
+static bool IsMaxSmi(Range* range) {
+  return (range == NULL) ||
+      (range->max().IsConstant() &&
+       (range->max().value() >= Smi::kMaxValue));
+}
+
+
+static bool IsEqual(const RangeBoundary& a, const RangeBoundary& b) {
+  if (a.IsConstant() && b.IsConstant()) {
+    return a.value() == b.value();
+  } else if (a.IsSymbol() && b.IsSymbol()) {
+    return (a.offset() == b.offset()) && DependOnSameSymbol(a, b);
+  } else {
+    return false;
+  }
+}
+
+static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a) {
+  if (a.IsConstant()) return a;
+
+  intptr_t offset = a.offset();
+  Definition* symbol = a.symbol();
+
+  bool changed;
+  do {
+    changed = false;
+    if (symbol->IsConstraint()) {
+      symbol = symbol->AsConstraint()->value()->definition();
+      changed = true;
+    } else if (symbol->IsBinarySmiOp()) {
+      BinarySmiOpInstr* op = symbol->AsBinarySmiOp();
+      Definition* left = op->left()->definition();
+      Definition* right = op->right()->definition();
+      switch (op->op_kind()) {
+        case Token::kADD:
+          if (right->IsConstant()) {
+            offset += Smi::Cast(right->AsConstant()->value()).Value();
+            symbol = left;
+            changed = true;
+          } else if (left->IsConstant()) {
+            offset += Smi::Cast(left->AsConstant()->value()).Value();
+            symbol = right;
+            changed = true;
+          }
+          break;
+
+

[srdjan, 2012/10/25 20:51:36]

Remove one empty line

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+        case Token::kSUB:
+          if (right->IsConstant()) {
+            offset -= Smi::Cast(right->AsConstant()->value()).Value();
+            symbol = left;
+            changed = true;
+          }
+          break;
+
+        default:
+          break;
+      }
+    }
+  } while (changed);
+
+  return RangeBoundary::FromDefinition(symbol, offset);
+}
+
+
+static bool CanonicalizeMaxBoundary(RangeBoundary* a) {
+  if (!a->IsSymbol()) return false;
+
+  Range* range = a->symbol()->range();
+  if ((range == NULL) || !range->max().IsSymbol()) return false;
+
+  *a = CanonicalizeBoundary(
+      RangeBoundary::FromDefinition(range->max().symbol(),
+                                    range->max().offset() + a->offset()));
+
+  return true;
+}
+
+
+static bool CanonicalizeMinBoundary(RangeBoundary* a) {
+  if (!a->IsSymbol()) return false;
+
+  Range* range = a->symbol()->range();
+  if ((range == NULL) || !range->min().IsSymbol()) return false;
+
+  *a = CanonicalizeBoundary(
+      RangeBoundary::FromDefinition(range->min().symbol(),
+                                    range->min().offset() + a->offset()));
+
+  return true;
+}
+
+
+#if 0
+static bool KnownToBeLessEqual(const RangeBoundary& a, const RangeBoundary& b) {
+  RangeBoundary canonical_a = CanonicalizeBoundary(a);
+  RangeBoundary canonical_b = CanonicalizeBoundary(b);
+
+  do {
+    if (DependOnSameSymbol(canonical_a, canonical_b)) {
+      return (canonical_a.offset() <= canonical_b.offset());
+    }
+  } while (CanonicalizeMaxBoundary(&canonical_a) ||
+           CanonicalizeMinBoundary(&canonical_b));
+
+  return a.UpperBound().value() <= b.LowerBound().value();
+}

[srdjan, 2012/10/25 20:51:36]

Remove the code above

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+#endif
+
+
+RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b) {
+  if (DependOnSameSymbol(a, b)) {
+    return (a.offset() <= b.offset()) ? a : b;
+  }
+
+  const intptr_t min_a = a.LowerBound().value();
+  const intptr_t min_b = b.LowerBound().value();
+
+  return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
+}
+
+
+RangeBoundary RangeBoundary::Max(RangeBoundary a, RangeBoundary b) {
+  if (DependOnSameSymbol(a, b)) {
+    return (a.offset() >= b.offset()) ? a : b;
+  }
+
+  const intptr_t max_a = a.UpperBound().value();
+  const intptr_t max_b = b.UpperBound().value();
+
+  return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
+}
+
+
 void Definition::InferRange() {
   ASSERT(GetPropagatedCid() == kSmiCid);  // Has meaning only for smis.
   if (range_ == NULL) {
     range_ = Range::Unknown();
   }
 }
 
 
 void ConstantInstr::InferRange() {
   ASSERT(value_.IsSmi());
   if (range_ == NULL) {
     intptr_t value = Smi::Cast(value_).Value();
     range_ = new Range(RangeBoundary::FromConstant(value),
                        RangeBoundary::FromConstant(value));
   }
 }
 
 
 void ConstraintInstr::InferRange() {
   Range* value_range = value()->definition()->range();
 
-  // Compute intersection of constraint and value ranges.
-  range_ = new Range(
-      RangeBoundary::Max(Range::ConstantMin(value_range),
-                         Range::ConstantMin(constraint())),
-      RangeBoundary::Min(Range::ConstantMax(value_range),
-                         Range::ConstantMax(constraint())));
+  RangeBoundary min;
+  RangeBoundary max;
+
+  if (IsMinSmi(value_range) && !IsMinSmi(constraint())) {
+    min = constraint()->min();
+  } else if (IsMinSmi(constraint()) && !IsMinSmi(value_range)) {
+    min = value_range->min();
+  } else if ((value_range != NULL) &&
+             IsEqual(constraint()->min(), value_range->min())) {
+    min = constraint()->min();
+  } else {
+    if (value_range != NULL) {
+      RangeBoundary canonical_a = CanonicalizeBoundary(constraint()->min());
+      RangeBoundary canonical_b = CanonicalizeBoundary(value_range->min());
+
+      do {
+        if (DependOnSameSymbol(canonical_a, canonical_b)) {
+          min = (canonical_a.offset() <= canonical_b.offset()) ? canonical_b
+                                                               : canonical_a;
+        }
+      } while (CanonicalizeMinBoundary(&canonical_a) ||
+               CanonicalizeMinBoundary(&canonical_b));
+    }
+
+    if (min.IsUnknown()) {
+      min = RangeBoundary::Max(Range::ConstantMin(value_range),
+                               Range::ConstantMin(constraint()));
+    }
+  }
+
+  if (IsMaxSmi(value_range) && !IsMaxSmi(constraint())) {
+    max = constraint()->max();
+  } else if (IsMaxSmi(constraint()) && !IsMaxSmi(value_range)) {
+    max = value_range->max();
+  } else if ((value_range != NULL) &&
+             IsEqual(constraint()->max(), value_range->max())) {
+    max = constraint()->max();
+  } else {
+    if (value_range != NULL) {
+      RangeBoundary canonical_b = CanonicalizeBoundary(value_range->max());
+      RangeBoundary canonical_a = CanonicalizeBoundary(constraint()->max());
+
+      do {
+        if (DependOnSameSymbol(canonical_a, canonical_b)) {
+          max = (canonical_a.offset() <= canonical_b.offset()) ? canonical_a
+                                                               : canonical_b;
+          break;
+        }
+      } while (CanonicalizeMaxBoundary(&canonical_a) ||
+               CanonicalizeMaxBoundary(&canonical_b));
+    }
+
+    if (max.IsUnknown()) {
+      max = RangeBoundary::Min(Range::ConstantMax(value_range),
+                                   Range::ConstantMax(constraint()));

[Florian Schneider, 2012/10/26 11:10:07]

Indentation.

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+    }
+  }
+
+  range_ = new Range(min, max);
 }
 
 
+void LoadFieldInstr::InferRange() {
+  if ((range_ == NULL) &&
+      ((recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
+       (recognized_kind() == MethodRecognizer::kImmutableArrayLength))) {
+    range_ = new Range(RangeBoundary::FromConstant(0),
+                       RangeBoundary::FromConstant(Array::kMaxElements));
+    return;
+  }
+  Definition::InferRange();
+}
+
+
 void PhiInstr::InferRange() {
   RangeBoundary new_min;
   RangeBoundary new_max;
 
   for (intptr_t i = 0; i < InputCount(); i++) {
     Range* input_range = InputAt(i)->definition()->range();
     if (input_range == NULL) {
       range_ = Range::Unknown();
       return;
     }
@@ skipping 14 matching lines @@
   ASSERT(new_min.IsUnknown() == new_max.IsUnknown());
   if (new_min.IsUnknown()) {
     range_ = Range::Unknown();
     return;
   }
 
   range_ = new Range(new_min, new_max);
 }
 
 
+static bool SymbolicSub(const RangeBoundary& a,
+                        const RangeBoundary& b,
+                        RangeBoundary* result) {
+  if (a.IsSymbol() &&
+      b.IsConstant() &&
+      ((b.value() > Smi::kMinValue) && (b.value() < Smi::kMaxValue))) {
+    *result = RangeBoundary::FromDefinition(a.symbol(), a.offset() - b.value());

[Florian Schneider, 2012/10/26 11:10:07]

Guard against smi-overflow here.

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+    return true;
+  }
+  return false;
+}
+
+
+static bool SymbolicAdd(const RangeBoundary& a,
+                        const RangeBoundary& b,
+                        RangeBoundary* result) {
+  if (a.IsSymbol() &&
+      b.IsConstant() &&
+      ((b.value() > Smi::kMinValue) && (b.value() < Smi::kMaxValue))) {
+    *result = RangeBoundary::FromDefinition(a.symbol(), a.offset() + b.value());

[Florian Schneider, 2012/10/26 11:10:07]

Guard against overflow here, so that the result offset is always a smi.

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+    return true;
+  } else if (b.IsSymbol() &&
+      a.IsConstant() &&
+      ((a.value() > Smi::kMinValue) && (a.value() < Smi::kMaxValue))) {
+    *result = RangeBoundary::FromDefinition(b.symbol(), b.offset() + a.value());

[Florian Schneider, 2012/10/26 11:10:07]

Guard against smi-overflow here as well.

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+    return true;
+  }
+  return false;
+}
+
+
 void BinarySmiOpInstr::InferRange() {
-  Range* left_range = left()->definition()->range();
+  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());
     return;
   }
 
-  RangeBoundary new_min;
-  RangeBoundary new_max;
+  RangeBoundary left_min =
+    left_defn->IsLoadField() ?

[Florian Schneider, 2012/10/26 11:10:07]

Does this need to be for every LoadField, or only array-length LoadField?

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Narrowed symbolic computation to length.

+        RangeBoundary::FromDefinition(left_defn) : left_range->min();
+
+  RangeBoundary left_max =
+    left_defn->IsLoadField() ?
+        RangeBoundary::FromDefinition(left_defn) : left_range->max();

[Florian Schneider, 2012/10/26 11:10:07]

Maybe add a TODO to support the case where right()->definition() is a LoadField.

Should we have a canonicalization of commutative smi-ops like + and * so that if
there is a constant operand, there is always one on the right side?

[Vyacheslav Egorov (Google), 2012/10/26 14:23:29]

Done.

+
+  RangeBoundary min;
+  RangeBoundary max;
   switch (op_kind()) {
     case Token::kADD:
-      new_min =
-        RangeBoundary::Add(Range::ConstantMin(left_range),
-                           Range::ConstantMin(right_range),
-                           RangeBoundary::OverflowedMinSmi());
-      new_max =
-        RangeBoundary::Add(Range::ConstantMax(left_range),
-                           Range::ConstantMax(right_range),
-                           RangeBoundary::OverflowedMaxSmi());
+      if (!SymbolicAdd(left_min, right_range->min(), &min)) {
+        min =
+          RangeBoundary::Add(Range::ConstantMin(left_range),
+                             Range::ConstantMin(right_range),
+                             RangeBoundary::OverflowedMinSmi());
+      }
+
+      if (!SymbolicAdd(left_max, right_range->max(), &max)) {
+        max =
+          RangeBoundary::Add(Range::ConstantMax(right_range),
+                             Range::ConstantMax(left_range),
+                             RangeBoundary::OverflowedMaxSmi());
+      }
       break;
 
     case Token::kSUB:
-      new_min =
-        RangeBoundary::Sub(Range::ConstantMin(left_range),
-                           Range::ConstantMax(right_range),
-                           RangeBoundary::OverflowedMinSmi());
-      new_max =
-        RangeBoundary::Sub(Range::ConstantMax(left_range),
-                           Range::ConstantMin(right_range),
-                           RangeBoundary::OverflowedMaxSmi());
+      if (!SymbolicSub(left_min, right_range->max(), &min)) {
+        min =
+          RangeBoundary::Sub(Range::ConstantMin(left_range),
+                             Range::ConstantMax(right_range),
+                             RangeBoundary::OverflowedMinSmi());
+      }
+
+      if (!SymbolicSub(left_max, right_range->min(), &max)) {
+        max =
+          RangeBoundary::Sub(Range::ConstantMax(left_range),
+                             Range::ConstantMin(right_range),
+                             RangeBoundary::OverflowedMaxSmi());
+      }
       break;
 
     default:
       if (range_ == NULL) {
         range_ = Range::Unknown();
       }
       return;
   }
 
-  ASSERT(!new_min.IsUnknown() && !new_max.IsUnknown());
-  set_overflow(new_min.Overflowed() || new_max.Overflowed());
+  ASSERT(!min.IsUnknown() && !max.IsUnknown());
+  set_overflow(min.LowerBound().Overflowed() || max.UpperBound().Overflowed());
 
-  range_ = new Range(new_min.Clamp(), new_max.Clamp());
+  if (min.IsConstant()) min.Clamp();
+  if (max.IsConstant()) max.Clamp();
+
+  range_ = new Range(min, max);
 }
 
 
+static bool IsArrayLength(Definition* defn, Definition* array) {
+  LoadFieldInstr* load = defn->AsLoadField();
+  return (load != NULL) && (load->value()->definition() == array) &&
+    ((load->recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
+     (load->recognized_kind() == MethodRecognizer::kImmutableArrayLength));
+}
+
+
+bool CheckArrayBoundInstr::IsRedundant() {
+  // 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());
+  do {
+    if (max.IsSymbol() &&
+        (max.offset() < 0) &&
+        IsArrayLength(max.symbol(), array()->definition())) {
+      return true;
+    }
+  } while (CanonicalizeMaxBoundary(&max));
+
+  // Failed to prove that maximum is bounded with array length.
+  return false;
+}
+
+
 #undef __
 
 }  // namespace dart