Extend Range analysis to 64-bit range and mint operations

runtime/vm/intermediate_language.cc

 // 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.
 
 #include "vm/intermediate_language.h"
 
 #include "vm/bigint_operations.h"
 #include "vm/bit_vector.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 2447 matching lines @@
 
 RangeBoundary RangeBoundary::FromDefinition(Definition* defn, intptr_t offs) {
   if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) {
     return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs);
   }
   return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
 }
 
 
 RangeBoundary RangeBoundary::LowerBound() const {
-  if (IsNegativeInfinity()) return *this;
+  if (IsInfinity()) {
+    return NegativeInfinity();
+  }
   if (IsConstant()) return *this;
   return Add(Range::ConstantMin(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
              NegativeInfinity());
 }
 
 
 RangeBoundary RangeBoundary::UpperBound() const {
-  if (IsPositiveInfinity()) return *this;
+  if (IsInfinity()) {
+    return PositiveInfinity();
+  }
   if (IsConstant()) return *this;
   return Add(Range::ConstantMax(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
              PositiveInfinity());
 }
 
 
+RangeBoundary RangeBoundary::Add(const RangeBoundary& a,
+                                 const RangeBoundary& b,
+                                 const RangeBoundary& overflow) {
+  if (a.IsInfinity() || b.IsInfinity()) {
+    // In that case that a or b is +/- inf, return the overflow boundary.
+    return overflow;
+  }
+  ASSERT(a.IsConstant() && b.IsConstant());
+
+  intptr_t result = a.ConstantValue() + b.ConstantValue();
+  if (!Smi::IsValid(result)) {
+    return overflow;
+  }
+  return RangeBoundary::FromConstant(result);
+}
+
+
+RangeBoundary RangeBoundary::Sub(const RangeBoundary& a,
+                                 const RangeBoundary& b,
+                                 const RangeBoundary& overflow) {
+  if (a.IsInfinity() || b.IsInfinity()) {
+    // In that case that a or b is +/- inf, return the overflow boundary.
+    return overflow;
+  }
+  ASSERT(a.IsConstant() && b.IsConstant());
+
+  intptr_t result = a.ConstantValue() - b.ConstantValue();
+  if (!Smi::IsValid(result)) {
+    return overflow;
+  }
+  return RangeBoundary::FromConstant(result);
+}
+
+
+bool RangeBoundary::SymbolicAdd(const RangeBoundary& a,
+                                const RangeBoundary& b,
+                                RangeBoundary* result) {
+  if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
+    const intptr_t offset = a.offset() + b.ConstantValue();
+    if (!Smi::IsValid(offset)) return false;
+
+    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
+    return true;
+  } else if (b.IsSymbol() && a.IsConstant() && !a.Overflowed()) {
+    const intptr_t offset = b.offset() + a.ConstantValue();

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

return SymbolicAdd(b, a, result); to avoid duplicating code.

[Cutch, 2014/06/13 22:45:22]

Done.

+    if (!Smi::IsValid(offset)) return false;
+
+    *result = RangeBoundary::FromDefinition(b.symbol(), offset);
+    return true;
+  }
+  return false;
+}
+
+
+bool RangeBoundary::SymbolicSub(const RangeBoundary& a,
+                                const RangeBoundary& b,
+                                RangeBoundary* result) {
+  if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
+    const intptr_t offset = a.offset() - b.ConstantValue();
+    if (!Smi::IsValid(offset)) return false;
+
+    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
+    return true;
+  }
+  return false;
+}
+
+
 static Definition* UnwrapConstraint(Definition* defn) {
   while (defn->IsConstraint()) {
     defn = defn->AsConstraint()->value()->definition();
   }
   return defn;
 }
 
 
 static bool AreEqualDefinitions(Definition* a, Definition* b) {
   a = UnwrapConstraint(a);
   b = UnwrapConstraint(b);
   return (a == b) ||
       (a->AllowsCSE() &&
        a->Dependencies().IsNone() &&
        b->AllowsCSE() &&
        b->Dependencies().IsNone() &&
        a->Equals(b));
 }
 
 
 // Returns true if two range boundaries refer to the same symbol.
 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
   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));
-}
-
-
-// Returns true if range has a least specific maximium value.
-static bool IsMaxSmi(Range* range) {
-  return (range == NULL) ||
-      (range->max().IsConstant() &&
-       (range->max().value() >= Smi::kMaxValue));
-}
-
-
-// Returns true if two range boundaries can be proven to be equal.
-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;
+bool RangeBoundary::Equals(const RangeBoundary& other) const {
+  if (IsConstant() && other.IsConstant()) {
+    return ConstantValue() == other.ConstantValue();
+  } else if (IsInfinity() && other.IsInfinity()) {
+    return kind() == other.kind();
+  } else if (IsSymbol() && other.IsSymbol()) {
+    return (offset() == other.offset()) && DependOnSameSymbol(*this, other);
   }
+  return false;
 }
 
 
 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a,
                                           const RangeBoundary& overflow) {
-  if (a.IsConstant() || a.IsNegativeInfinity() || a.IsPositiveInfinity()) {
+  if (a.IsConstant() || a.IsInfinity()) {
     return a;
   }
 
   intptr_t offset = a.offset();
   Definition* symbol = a.symbol();
 
   bool changed;
   do {
     changed = false;
     if (symbol->IsConstraint()) {
@@ skipping 71 matching lines @@
 
   *a = CanonicalizeBoundary(
       RangeBoundary::FromDefinition(range->min().symbol(), offset),
       RangeBoundary::NegativeInfinity());
 
   return true;
 }
 
 
 RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b) {
+  // Infinity cases.
+  if (a.IsNegativeInfinity() || b.IsNegativeInfinity()) {
+    return NegativeInfinity();
+  }
+  if (a.IsPositiveInfinity()) {
+    return b;
+  }
+  if (b.IsPositiveInfinity()) {
+    return a;
+  }
+
+  // Equality case.
+  if (a.Equals(b)) {
+    return a;
+  }
+
   if (DependOnSameSymbol(a, b)) {
     return (a.offset() <= b.offset()) ? a : b;
   }
 
-  const intptr_t min_a = a.LowerBound().Clamp().value();
-  const intptr_t min_b = b.LowerBound().Clamp().value();
+  const intptr_t min_a = a.LowerBound().Clamp().ConstantValue();
+  const intptr_t min_b = b.LowerBound().Clamp().ConstantValue();
 
   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;
+  // Infinity cases.
+  if (a.IsPositiveInfinity() || b.IsPositiveInfinity()) {
+    return RangeBoundary::PositiveInfinity();
+  }
+  if (a.IsNegativeInfinity()) {
+    return b;
+  }
+  if (b.IsNegativeInfinity()) {
+    return a;
+  }
+  // Equality case.
+  if (a.Equals(b)) {
+    return a;
   }
 
-  const intptr_t max_a = a.UpperBound().Clamp().value();
-  const intptr_t max_b = b.UpperBound().Clamp().value();
+  if (DependOnSameSymbol(a, b)) {

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

I would move loop that tries to Canonicalize boundaries before comparing them
symbolically here.

+    return (a.offset() <= b.offset()) ? b : a;
+  }
+
+  const intptr_t max_a = a.UpperBound().Clamp().ConstantValue();
+  const intptr_t max_b = b.UpperBound().Clamp().ConstantValue();
 
   return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
 }
 
 
+intptr_t RangeBoundary::ConstantValue() const {
+  ASSERT(IsConstant());
+  return value_;
+}
+
+
 void Definition::InferRange() {
   ASSERT(Type()->ToCid() == 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();
 
   RangeBoundary min;
   RangeBoundary max;
 
-  if (IsMinSmi(value_range) && !IsMinSmi(constraint())) {
+  if (Range::IncludesNegativeInfinity(value_range) &&

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

I would expect this code to actually use RangeBoundary::Max() why is this not
the case?

+      !Range::IncludesNegativeInfinity(constraint())) {
     min = constraint()->min();
-  } else if (IsMinSmi(constraint()) && !IsMinSmi(value_range)) {
+  } else if (Range::IncludesNegativeInfinity(constraint()) &&
+             !Range::IncludesNegativeInfinity(value_range)) {
     min = value_range->min();
   } else if ((value_range != NULL) &&
-             IsEqual(constraint()->min(), value_range->min())) {
+             constraint()->min().Equals(value_range->min())) {
     min = constraint()->min();
   } else {
     if (value_range != NULL) {
       RangeBoundary canonical_a =
           CanonicalizeBoundary(constraint()->min(),
                                RangeBoundary::NegativeInfinity());
       RangeBoundary canonical_b =
           CanonicalizeBoundary(value_range->min(),
                                RangeBoundary::NegativeInfinity());
 
       do {
         if (DependOnSameSymbol(canonical_a, canonical_b)) {
           min = (canonical_a.offset() <= canonical_b.offset()) ? canonical_b
                                                                : canonical_a;

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

I agree this should have break.

         }
       } 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())) {
+  if (Range::IncludesPositiveInfinity(value_range) &&

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

I would expect this to be replaced by RangeBoundary::Min

[Cutch, 2014/06/13 22:45:22]

Done.

+      !Range::IncludesPositiveInfinity(constraint())) {
     max = constraint()->max();
-  } else if (IsMaxSmi(constraint()) && !IsMaxSmi(value_range)) {
+  } else if (Range::IncludesPositiveInfinity(constraint()) &&
+             !Range::IncludesPositiveInfinity(value_range)) {
     max = value_range->max();
   } else if ((value_range != NULL) &&
-             IsEqual(constraint()->max(), value_range->max())) {
+             constraint()->max().Equals(value_range->max())) {
     max = constraint()->max();
   } else {
     if (value_range != NULL) {
       RangeBoundary canonical_b =
           CanonicalizeBoundary(value_range->max(),
                                RangeBoundary::PositiveInfinity());
       RangeBoundary canonical_a =
           CanonicalizeBoundary(constraint()->max(),
                                RangeBoundary::PositiveInfinity());
 
@@ skipping 236 matching lines @@
   ASSERT(InputCount() > 1);
   Definition* first = InputAt(0)->definition();
   for (intptr_t i = 1; i < InputCount(); ++i) {
     Definition* def = InputAt(i)->definition();
     if (def != first) return false;
   }
   return true;
 }
 
 
-static bool SymbolicSub(const RangeBoundary& a,
-                        const RangeBoundary& b,
-                        RangeBoundary* result) {
-  if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
-    const intptr_t offset = a.offset() - b.value();
-    if (!Smi::IsValid(offset)) return false;
-
-    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
-    return true;
-  }
-  return false;
-}
-
-
-static bool SymbolicAdd(const RangeBoundary& a,
-                        const RangeBoundary& b,
-                        RangeBoundary* result) {
-  if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
-    const intptr_t offset = a.offset() + b.value();
-    if (!Smi::IsValid(offset)) return false;
-
-    *result = RangeBoundary::FromDefinition(a.symbol(), offset);
-    return true;
-  } else if (b.IsSymbol() && a.IsConstant() && !a.Overflowed()) {
-    const intptr_t offset = b.offset() + a.value();
-    if (!Smi::IsValid(offset)) return false;
-
-    *result = RangeBoundary::FromDefinition(b.symbol(), offset);
-    return true;
-  }
-  return false;
-}
-
-
 static bool IsArrayLength(Definition* defn) {
   LoadFieldInstr* load = defn->AsLoadField();
   return (load != NULL) && load->IsImmutableLengthLoad();
 }
 
 
-static int64_t ConstantAbsMax(const Range* range) {
-  if (range == NULL) return Smi::kMaxValue;
-  const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).value());
-  const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).value());
-  return abs_min > abs_max ? abs_min : abs_max;
-}
-
-
-static bool OnlyPositiveOrZero(const Range* a, const Range* b) {
-  if ((a == NULL) || (b == NULL)) return false;
-  if (Range::ConstantMin(a).value() < 0) return false;
-  if (Range::ConstantMin(b).value() < 0) return false;
-  return true;
-}
-
-
-static bool OnlyNegativeOrZero(const Range* a, const Range* b) {
-  if ((a == NULL) || (b == NULL)) return false;
-  if (Range::ConstantMax(a).value() > 0) return false;
-  if (Range::ConstantMax(b).value() > 0) return false;
-  return true;
-}
-
-
 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());
     return;
   }
 
   RangeBoundary left_min =
     IsArrayLength(left_defn) ?
         RangeBoundary::FromDefinition(left_defn) : left_range->min();
 
   RangeBoundary left_max =
     IsArrayLength(left_defn) ?
         RangeBoundary::FromDefinition(left_defn) : left_range->max();
 
-  RangeBoundary min;
-  RangeBoundary max;
-  switch (op_kind()) {
-    case Token::kADD:
-      if (!SymbolicAdd(left_min, right_range->min(), &min)) {
-        min =
-          RangeBoundary::Add(Range::ConstantMin(left_range),
-                             Range::ConstantMin(right_range),
-                             RangeBoundary::NegativeInfinity());
-      }
+  // Only update overflow state for +, -, and cases where we already have a
+  // range.
+  bool should_update_overflow = (op_kind() == Token::kADD) ||
+                                (op_kind() == Token::kSUB) ||
+                                (range_ != NULL);
 
-      if (!SymbolicAdd(left_max, right_range->max(), &max)) {
-        max =
-          RangeBoundary::Add(Range::ConstantMax(right_range),
-                             Range::ConstantMax(left_range),
-                             RangeBoundary::PositiveInfinity());
-      }
-      break;
-
-    case Token::kSUB:
-      if (!SymbolicSub(left_min, right_range->max(), &min)) {
-        min =
-          RangeBoundary::Sub(Range::ConstantMin(left_range),
-                             Range::ConstantMax(right_range),
-                             RangeBoundary::NegativeInfinity());
-      }
-
-      if (!SymbolicSub(left_max, right_range->min(), &max)) {
-        max =
-          RangeBoundary::Sub(Range::ConstantMax(left_range),
-                             Range::ConstantMin(right_range),
-                             RangeBoundary::PositiveInfinity());
-      }
-      break;
-
-    case Token::kMUL: {
-      const int64_t left_max = ConstantAbsMax(left_range);
-      const int64_t right_max = ConstantAbsMax(right_range);
-      if ((left_max < 0x7FFFFFFF) && (right_max < 0x7FFFFFFF)) {
-        // Product of left and right max values stays in 64 bit range.
-        const int64_t result_max = left_max * right_max;
-        if (Smi::IsValid64(result_max) && Smi::IsValid64(-result_max)) {
-          const intptr_t r_min =
-              OnlyPositiveOrZero(left_range, right_range) ? 0 : -result_max;
-          min = RangeBoundary::FromConstant(r_min);
-          const intptr_t r_max =
-              OnlyNegativeOrZero(left_range, right_range) ? 0 : result_max;
-          max = RangeBoundary::FromConstant(r_max);
-          break;
-        }
-      }
-      if (range_ == NULL) {
-        range_ = Range::Unknown();
-      }
-      return;
-    }
-    case Token::kBIT_AND:
-      if (Range::ConstantMin(right_range).value() >= 0) {
-        min = RangeBoundary::FromConstant(0);
-        max = Range::ConstantMax(right_range);
-        break;
-      }
-      if (Range::ConstantMin(left_range).value() >= 0) {
-        min = RangeBoundary::FromConstant(0);
-        max = Range::ConstantMax(left_range);
-        break;
-      }
-
-      if (range_ == NULL) {
-        range_ = Range::Unknown();
-      }
-      return;
-
-    default:
-      if (range_ == NULL) {
-        range_ = Range::Unknown();
-      }
-      return;
+  range_ = Range::BinaryOp(op_kind(),
+                           left_min,
+                           left_max,
+                           left_range,
+                           right_range,
+                           range_);
+  if (range_ == NULL) {
+    // No range information.
+    return;
   }
 
-  ASSERT(!min.IsUnknown() && !max.IsUnknown());
-  set_overflow(min.LowerBound().Overflowed() || max.UpperBound().Overflowed());
+  if (!should_update_overflow) {
+    return;
+  }
 
-  if (min.IsConstant()) min.Clamp();
-  if (max.IsConstant()) max.Clamp();
-
-  range_ = new Range(min, max);
+  ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
+  const bool overflowed = range_->min().LowerBound().Overflowed() ||
+                          range_->max().UpperBound().Overflowed();
+  set_overflow(overflowed);
 }
 
 
 bool Range::IsPositive() const {
   if (min().IsNegativeInfinity()) {
     return false;
   }
-  if (min().LowerBound().value() < 0) {
+  if (min().LowerBound().ConstantValue() < 0) {
     return false;
   }
   if (max().IsPositiveInfinity()) {
     return true;
   }
-  return max().UpperBound().value() >= 0;
+  return max().UpperBound().ConstantValue() >= 0;
 }
 
 
 bool Range::IsNegative() const {
   if (max().IsPositiveInfinity()) {
     return false;
   }
-  if (max().UpperBound().value() >= 0) {
+  if (max().UpperBound().ConstantValue() >= 0) {
     return false;
   }
   if (min().IsNegativeInfinity()) {
     return true;
   }
-  return min().LowerBound().value() < 0;
+  return min().LowerBound().ConstantValue() < 0;
 }
 
 
 bool Range::OnlyLessThanOrEqualTo(intptr_t val) const {
   if (max().IsPositiveInfinity()) {
     // Cannot be true.
     return false;
   }
-  if (max().UpperBound().value() > val) {
+  if (max().UpperBound().ConstantValue() > val) {
     // Not true.
     return false;
   }
   if (!min().IsNegativeInfinity()) {
-    if (min().LowerBound().value() > val) {
+    if (min().LowerBound().ConstantValue() > val) {
       // Lower bound is > value.
       return false;
     }
   }
   return true;
 }
 
 
+bool Range::OnlyGreaterThanOrEqualTo(intptr_t val) const {
+  if (min().IsNegativeInfinity()) {
+    return false;
+  }
+  if (min().LowerBound().ConstantValue() < val) {
+    return false;
+  }
+  if (!max().IsPositiveInfinity()) {
+    if (max().UpperBound().ConstantValue() < val) {

[Vyacheslav Egorov (Google), 2014/06/13 11:50:21]

min().LowerBound().ConstantValue() >= val && max().UpperBound().ConstantValue()
< val 

is an impossible (empty) range.

+      return false;
+    }
+  }
+  return true;
+}
+
+
 // Inclusive.
 bool Range::IsWithin(intptr_t min_int, intptr_t max_int) const {
   RangeBoundary lower_min = min().LowerBound();
-  if (lower_min.IsNegativeInfinity() || (lower_min.value() < min_int)) {
+  if (lower_min.IsNegativeInfinity() || (lower_min.ConstantValue() < min_int)) {
     return false;
   }
   RangeBoundary upper_max = max().UpperBound();
-  if (upper_max.IsPositiveInfinity() || (upper_max.value() > max_int)) {
+  if (upper_max.IsPositiveInfinity() || (upper_max.ConstantValue() > max_int)) {
     return false;
   }
   return true;
 }
 
 
 bool Range::Overlaps(intptr_t min_int, intptr_t max_int) const {
-  const intptr_t this_min = min().IsNegativeInfinity() ?
-      kIntptrMin : min().LowerBound().value();
-  const intptr_t this_max = max().IsPositiveInfinity() ?
-      kIntptrMax : max().UpperBound().value();
+  RangeBoundary lower = min().LowerBound();
+  RangeBoundary upper = max().UpperBound();
+  const intptr_t this_min = lower.IsNegativeInfinity() ?
+      RangeBoundary::kMin : lower.ConstantValue();
+  const intptr_t this_max = upper.IsPositiveInfinity() ?
+      RangeBoundary::kMax : upper.ConstantValue();
   if ((this_min <= min_int) && (min_int <= this_max)) return true;
   if ((this_min <= max_int) && (max_int <= this_max)) return true;
   if ((min_int < this_min) && (max_int > this_max)) return true;
   return false;
 }
 
 
 bool Range::IsUnsatisfiable() const {
   // Infinity case: [+inf, ...] || [..., -inf]
   if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) {
     return true;
   }
   // Constant case: For example [0, -1].
-  if (Range::ConstantMin(this).value() > Range::ConstantMax(this).value()) {
+  if (Range::ConstantMin(this).ConstantValue() >
+      Range::ConstantMax(this).ConstantValue()) {
     return true;
   }
   // Symbol case: For example [v+1, v].
   if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
     return true;
   }
   return false;
 }
 
 
+// Returns true if range is at or below the minimum smi value.
+bool Range::IncludesNegativeInfinity(const Range* range) {
+  return (range == NULL) || range->min().IsNegativeInfinity();
+}
+
+
+// Returns true if range is at or above the maximum smi value.
+bool Range::IncludesPositiveInfinity(const Range* range) {
+    return (range == NULL) || range->max().IsPositiveInfinity();
+}
+
+
+// Both the a and b ranges are >= 0.
+bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) {
+  return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0);
+}
+
+
+// Both the a and b ranges are <= 0.
+bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) {
+  return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0);
+}
+
+
+// Return the maximum absolute value included in range.
+int64_t Range::ConstantAbsMax(const Range* range) {
+  if (range == NULL) {
+    return RangeBoundary::kMax;
+  }
+  const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue());
+  const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue());
+  return Utils::Maximum(abs_min, abs_max);
+}
+
+
+Range* Range::BinaryOp(const Token::Kind op,
+                       const RangeBoundary& left_min,
+                       const RangeBoundary& left_max,
+                       const Range* left_range,
+                       const Range* right_range,
+                       const Range* original_range) {
+  ASSERT(left_range != NULL);
+  ASSERT(right_range != NULL);
+  RangeBoundary min;
+  RangeBoundary max;
+  switch (op) {
+    case Token::kADD:
+      if (!RangeBoundary::SymbolicAdd(left_min, right_range->min(), &min)) {
+        min = RangeBoundary::Add(left_range->min().LowerBound(),
+                                 right_range->min().LowerBound(),
+                                 RangeBoundary::NegativeInfinity());
+      }
+      if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), &max)) {
+        max = RangeBoundary::Add(right_range->max().UpperBound(),
+                                 left_range->max().UpperBound(),
+                                 RangeBoundary::PositiveInfinity());
+      }
+      break;
+    case Token::kSUB:
+      if (!RangeBoundary::SymbolicSub(left_min, right_range->max(), &min)) {
+        min = RangeBoundary::Sub(left_range->min().LowerBound(),
+                                 right_range->max().UpperBound(),
+                                 RangeBoundary::NegativeInfinity());
+      }
+      if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), &max)) {
+        max = RangeBoundary::Sub(left_range->max().UpperBound(),
+                                 right_range->min().LowerBound(),
+                                 RangeBoundary::PositiveInfinity());
+      }
+      break;
+    case Token::kMUL: {
+      const int64_t left_max = ConstantAbsMax(left_range);
+      const int64_t right_max = ConstantAbsMax(right_range);
+      if ((left_max < 0x7FFFFFFF) && (right_max < 0x7FFFFFFF)) {
+        // Product of left and right max values stays in 64 bit range.
+        const int64_t result_max = left_max * right_max;
+        if (Smi::IsValid64(result_max) && Smi::IsValid64(-result_max)) {
+          const intptr_t r_min =
+              OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -result_max;
+          min = RangeBoundary::FromConstant(r_min);
+          const intptr_t r_max =
+              OnlyNegativeOrZero(*left_range, *right_range) ? 0 : result_max;
+          max = RangeBoundary::FromConstant(r_max);
+          break;
+        }
+      }
+      if (original_range == NULL) {
+        return Range::Unknown();
+      }
+      break;
+    }
+    case Token::kBIT_AND:
+      if (Range::ConstantMin(right_range).ConstantValue() >= 0) {
+        min = RangeBoundary::FromConstant(0);
+        max = Range::ConstantMax(right_range);
+        break;
+      }
+      if (Range::ConstantMin(left_range).ConstantValue() >= 0) {
+        min = RangeBoundary::FromConstant(0);
+        max = Range::ConstantMax(left_range);
+        break;
+      }
+      if (original_range == NULL) {
+        return Range::Unknown();
+      }
+      break;
+    default:
+      if (original_range == NULL) {
+        return Range::Unknown();
+      }
+      return const_cast<Range*>(original_range);
+  }
+
+  ASSERT(!min.IsUnknown() && !max.IsUnknown());
+
+  return new Range(min, max);
+}
+
+
 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
   return LoadFieldInstr::IsFixedLengthArrayCid(cid);
 }
 
 
 bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
   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) {
+  if (Range::ConstantMin(index_range).ConstantValue() < 0) {
     return false;
   }
 
   RangeBoundary max = CanonicalizeBoundary(index_range->max(),
                                            RangeBoundary::PositiveInfinity());
 
   if (max.Overflowed()) {
     return false;
   }
 
 
   RangeBoundary max_upper = max.UpperBound();
   RangeBoundary length_lower = length.LowerBound();
 
   if (max_upper.Overflowed() || length_lower.Overflowed()) {
     return false;
   }
 
   // Try to compare constant boundaries.
-  if (max_upper.value() < length_lower.value()) {
+  if (max_upper.ConstantValue() < length_lower.ConstantValue()) {
     return true;
   }
 
   length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity());
   if (length.Overflowed()) {
     return false;
   }
 
   // Try symbolic comparison.
   do {
@@ skipping 277 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart