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 2445 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 {

[Vyacheslav Egorov (Google), 2014/06/11 17:36:37]

I don't think having PositiveInfinity.LowerBound() == PositiveInfinity makes
sense. It should be ether undefined (assert?) or be safely equal to
NegativeInfinity.

-  if (IsNegativeInfinity()) return *this;
-  if (IsConstant()) return *this;
+  if (IsConstantOrInfinity()) return *this;
   return Add(Range::ConstantMin(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
              NegativeInfinity());
 }
 
 
 RangeBoundary RangeBoundary::UpperBound() const {
-  if (IsPositiveInfinity()) return *this;
-  if (IsConstant()) return *this;
+  if (IsConstantOrInfinity()) return *this;

[Vyacheslav Egorov (Google), 2014/06/11 17:36:37]

Ditto.

   return Add(Range::ConstantMax(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
              PositiveInfinity());
 }
 
 
+RangeBoundary RangeBoundary::Add(const RangeBoundary& a,
+                                 const RangeBoundary& b,
+                                 const RangeBoundary& overflow) {
+  ASSERT(a.IsConstantOrInfinity() && b.IsConstantOrInfinity());
+
+  intptr_t result = a.Value() + b.Value();
+  if (!Smi::IsValid(result)) {
+    return overflow;
+  }
+  return RangeBoundary::FromConstant(result);
+}
+
+
+RangeBoundary RangeBoundary::Sub(const RangeBoundary& a,
+                                 const RangeBoundary& b,
+                                 const RangeBoundary& overflow) {
+  ASSERT(a.IsConstantOrInfinity() && b.IsConstantOrInfinity());
+
+  intptr_t result = a.Value() - b.Value();
+  if (!Smi::IsValid(result)) {
+    return overflow;
+  }
+  return RangeBoundary::FromConstant(result);
+}
+
+
 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 Value() == other.Value();
+  } else if (IsInfinity() && other.IsInfinity()) {
+    return Value() == other.Value();
+  } 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 75 matching lines @@
 
   return true;
 }
 
 
 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().Clamp().value();
-  const intptr_t min_b = b.LowerBound().Clamp().value();
+  const intptr_t min_a = a.LowerBound().Clamp().Value();
+  const intptr_t min_b = b.LowerBound().Clamp().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().Clamp().value();
-  const intptr_t max_b = b.UpperBound().Clamp().value();
+  const intptr_t max_a = a.UpperBound().Clamp().Value();
+  const intptr_t max_b = b.UpperBound().Clamp().Value();
 
   return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
 }
 
 
+intptr_t RangeBoundary::Value() const {

[Florian Schneider, 2014/06/11 10:41:00]

maybe add ASSERT(kind_ == kConstant);

[Cutch, 2014/06/13 04:24:25]

Done.

+  if (IsNegativeInfinity()) {
+    return kMin;

[Florian Schneider, 2014/06/11 10:41:00]

I'm not sure this is ideal to return kMin/kMax. A constant range may also have
the same boundary value, since we want to represent constant range boundaries
with the min-int and max-int values, and therefore the value returned here can't
be used to compare two range boundaries.

Maybe better add UNREACHABLE() here?

[Vyacheslav Egorov (Google), 2014/06/11 17:36:37]

I second Florian here. Let's prohibit asking a value of unclamped infinity.

On 2014/06/11 10:41:00, Florian Schneider wrote:

[Cutch, 2014/06/13 04:24:26]

Done.

+  }
+  if (IsPositiveInfinity()) {
+    return kMax;

[Florian Schneider, 2014/06/11 10:41:00]

UNREACHABLE()?

[Cutch, 2014/06/13 04:24:25]

Done.

+  }
+  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::IsSmiMinimumOrUnderflow(value_range) &&

[Vyacheslav Egorov (Google), 2014/06/11 17:36:37]

for simplicity I suggest we make this code different: just check for infinities,
don't check for `OrUnderflow`. 

Those ranges should never be underflowing, they should be clamped to the
effective value range (smi).

[Vyacheslav Egorov (Google), 2014/06/11 20:06:37]

I wonder if this code will become better if we introduce 

RangeBoundary::Max() and RangeBoundary::Min() that can work both on symbols,
infinities and constants. Then you just use that to compute RangeBoundary for
min and max of the range.

On 2014/06/11 17:36:37, Vyacheslav Egorov (Google) wrote:

[Cutch, 2014/06/13 04:24:25]

I've extended Min and Max to handle infinities but I'm not sure about putting
the else code paths into Min and Max- there is canonicalization going on with
opposite boundaries.

[Cutch, 2014/06/13 04:24:25]

Done.

+      !Range::IsSmiMinimumOrUnderflow(constraint())) {
     min = constraint()->min();
-  } else if (IsMinSmi(constraint()) && !IsMinSmi(value_range)) {
+  } else if (Range::IsSmiMinimumOrUnderflow(constraint()) &&
+             !Range::IsSmiMinimumOrUnderflow(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;
         }
       } 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::IsSmiMaximumOrOverflow(value_range) &&
+      !Range::IsSmiMaximumOrOverflow(constraint())) {
     max = constraint()->max();
-  } else if (IsMaxSmi(constraint()) && !IsMaxSmi(value_range)) {
+  } else if (Range::IsSmiMaximumOrOverflow(constraint()) &&
+             !Range::IsSmiMaximumOrOverflow(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,

[Vyacheslav Egorov (Google), 2014/06/11 20:06:36]

This funciton should be moved to RangeBoundary?

[Cutch, 2014/06/13 04:24:25]

Done.

                         const RangeBoundary& b,
                         RangeBoundary* result) {
   if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
-    const intptr_t offset = a.offset() - b.value();
+    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();
+    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();
+    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());
-      }
+  // If we had no range information before, we do not update the overflow state.
+  bool should_update_overflow = range_ != NULL;

[Vyacheslav Egorov (Google), 2014/06/11 20:06:37]

I don't understand the reasoning behind this lack of update on the first call.
We will get out of sync. The old code did not have this behavior.

[Cutch, 2014/06/13 04:24:26]

I've updated the predicate to include the + and - case.

 
-      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().Value() < 0) {
     return false;
   }
   if (max().IsPositiveInfinity()) {
     return true;
   }
-  return max().UpperBound().value() >= 0;
+  return max().UpperBound().Value() >= 0;
 }
 
 
 bool Range::IsNegative() const {
   if (max().IsPositiveInfinity()) {
     return false;
   }
-  if (max().UpperBound().value() >= 0) {
+  if (max().UpperBound().Value() >= 0) {
     return false;
   }
   if (min().IsNegativeInfinity()) {
     return true;
   }
-  return min().LowerBound().value() < 0;
+  return min().LowerBound().Value() < 0;
 }
 
 
 bool Range::OnlyLessThanOrEqualTo(intptr_t val) const {
   if (max().IsPositiveInfinity()) {
     // Cannot be true.
     return false;
   }
-  if (max().UpperBound().value() > val) {
+  if (max().UpperBound().Value() > val) {
     // Not true.
     return false;
   }
   if (!min().IsNegativeInfinity()) {
-    if (min().LowerBound().value() > val) {
+    if (min().LowerBound().Value() > val) {
       // Lower bound is > value.
       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.Value() < min_int)) {
     return false;
   }
   RangeBoundary upper_max = max().UpperBound();
-  if (upper_max.IsPositiveInfinity() || (upper_max.value() > max_int)) {
+  if (upper_max.IsPositiveInfinity() || (upper_max.Value() > 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();
+  const intptr_t this_min =  min().LowerBound().Value();
+  const intptr_t this_max = max().UpperBound().Value();
   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).Value() > Range::ConstantMax(this).Value()) {
     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::IsSmiMinimumOrUnderflow(const Range* range) {
+  return (range == NULL) ||
+         ((range->min().IsConstant() || range->min().IsInfinity()) &&

[Florian Schneider, 2014/06/11 10:41:00]

IsNegativeInfinity()?

+          (range->min().Value() <= Smi::kMinValue));

[Florian Schneider, 2014/06/11 10:41:00]

Same comment as below.

+}
+
+// Returns true if range is at or above the maximum smi value.
+bool Range::IsSmiMaximumOrOverflow(const Range* range) {
+    return (range == NULL) ||
+            ((range->max().IsConstant() || range->max().IsInfinity()) &&

[Florian Schneider, 2014/06/11 10:41:00]

IsPositiveInfinity?

+            (range->max().Value() >= Smi::kMaxValue));

[Florian Schneider, 2014/06/11 10:41:00]

This is a piece of code that gets hard to read because of parenthesiszation... a
case where imo our 'style-guide' gets in the way.

Value() is not a valid boundary if the RangeBoundary is +/- infinity. I think
the condition rather should be:

range == NULL ||
range->max().IsPositiveInfinity() ||
(range->max().IsConstant() && range.max().Value >= Smi::kMaxValue)

+}
+
+
+// Both the a and b ranges are >= 0.
+bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) {

[Vyacheslav Egorov (Google), 2014/06/11 20:06:36]

It feels like we have some kind of duplication here. We already have similar
check for range boundaries. Can that be used instead?

[Cutch, 2014/06/13 04:24:25]

Done.

+  if (Range::ConstantMin(&a).Value() < 0) {
+    return false;
+  }
+  if (Range::ConstantMin(&b).Value() < 0) {
+    return false;
+  }
+  return true;
+}
+
+
+// Both the a and b ranges are <= 0.
+bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) {
+  if (Range::ConstantMax(&a).Value() > 0) {
+    return false;
+  }
+  if (Range::ConstantMax(&b).Value() > 0) {
+    return false;
+  }
+  return true;
+}
+
+
+// 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).Value());
+  const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).Value());
+  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 (!SymbolicAdd(left_min, right_range->min(), &min)) {
+        min = RangeBoundary::Add(Range::ConstantMin(left_range),
+                                 Range::ConstantMin(right_range),
+                                 RangeBoundary::NegativeInfinity());
+      }
+      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 (original_range == NULL) {
+        return Range::Unknown();
+      }
+      break;
+    }
+    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 (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).Value() < 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.Value() < length_lower.Value()) {
     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