Refactor RangeBoundary +/- infinity to be distinct RangeBoundary kinds.

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 1215 matching lines @@
     return true;
   }
   switch (op_kind()) {
     case Token::kBIT_AND:
     case Token::kBIT_OR:
     case Token::kBIT_XOR:
       return false;
     case Token::kSHR: {
       // Can't deopt if shift-count is known positive.
       Range* right_range = this->right()->definition()->range();
-      return (right_range == NULL)
-          || !right_range->IsWithin(0, RangeBoundary::kPlusInfinity);
+      return (right_range == NULL) || right_range->IsNegative();
     }
     case Token::kSHL: {
       Range* right_range = this->right()->definition()->range();
       if ((right_range != NULL) && is_truncating()) {
         // Can deoptimize if right can be negative.
-        return !right_range->IsWithin(0, RangeBoundary::kPlusInfinity);
+        return right_range->IsNegative();
       }
       return true;
     }
     case Token::kMOD: {
       Range* right_range = this->right()->definition()->range();
       return (right_range == NULL) || right_range->Overlaps(0, 0);
     }
     default:
       return overflow_;
   }
@@ skipping 1183 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 (IsConstant()) return *this;
   return Add(Range::ConstantMin(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
-             OverflowedMinSmi());
+             NegativeInfinity());
 }
 
 
 RangeBoundary RangeBoundary::UpperBound() const {
+  if (IsPositiveInfinity()) return *this;
   if (IsConstant()) return *this;
   return Add(Range::ConstantMax(symbol()->range()),
              RangeBoundary::FromConstant(offset_),
-             OverflowedMaxSmi());
+             PositiveInfinity());
 }
 
 
 static Definition* UnwrapConstraint(Definition* defn) {
   while (defn->IsConstraint()) {
     defn = defn->AsConstraint()->value()->definition();
   }
   return defn;
 }
 
@@ skipping 40 matching lines @@
   } else if (a.IsSymbol() && b.IsSymbol()) {
     return (a.offset() == b.offset()) && DependOnSameSymbol(a, b);
   } else {
     return false;
   }
 }
 
 
 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a,
                                           const RangeBoundary& overflow) {
-  if (a.IsConstant()) return a;
+  if (a.IsConstant() || a.IsNegativeInfinity() || a.IsPositiveInfinity()) {
+    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;
@@ skipping 36 matching lines @@
 
 static bool CanonicalizeMaxBoundary(RangeBoundary* a) {
   if (!a->IsSymbol()) return false;
 
   Range* range = a->symbol()->range();
   if ((range == NULL) || !range->max().IsSymbol()) return false;
 
   const intptr_t offset = range->max().offset() + a->offset();
 
   if (!Smi::IsValid(offset)) {
-    *a = RangeBoundary::OverflowedMaxSmi();
+    *a = RangeBoundary::PositiveInfinity();
     return true;
   }
 
   *a = CanonicalizeBoundary(
       RangeBoundary::FromDefinition(range->max().symbol(), offset),
-      RangeBoundary::OverflowedMaxSmi());
+      RangeBoundary::PositiveInfinity());
 
   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;
 
   const intptr_t offset = range->min().offset() + a->offset();
   if (!Smi::IsValid(offset)) {
-    *a = RangeBoundary::OverflowedMinSmi();
+    *a = RangeBoundary::NegativeInfinity();
     return true;
   }
 
   *a = CanonicalizeBoundary(
       RangeBoundary::FromDefinition(range->min().symbol(), offset),
-      RangeBoundary::OverflowedMinSmi());
+      RangeBoundary::NegativeInfinity());
 
   return true;
 }
 
 
 RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b) {
   if (DependOnSameSymbol(a, b)) {
     return (a.offset() <= b.offset()) ? a : b;
   }
 
@@ skipping 44 matching lines @@
     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::OverflowedMinSmi());
+                               RangeBoundary::NegativeInfinity());
       RangeBoundary canonical_b =
           CanonicalizeBoundary(value_range->min(),
-                               RangeBoundary::OverflowedMinSmi());
+                               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())) {
     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::OverflowedMaxSmi());
+                               RangeBoundary::PositiveInfinity());
       RangeBoundary canonical_a =
           CanonicalizeBoundary(constraint()->max(),
-                               RangeBoundary::OverflowedMaxSmi());
+                               RangeBoundary::PositiveInfinity());
 
       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));
     }
@@ skipping 320 matching lines @@
         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::OverflowedMinSmi());
+                             RangeBoundary::NegativeInfinity());
       }
 
       if (!SymbolicAdd(left_max, right_range->max(), &max)) {
         max =
           RangeBoundary::Add(Range::ConstantMax(right_range),
                              Range::ConstantMax(left_range),
-                             RangeBoundary::OverflowedMaxSmi());
+                             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::OverflowedMinSmi());
+                             RangeBoundary::NegativeInfinity());
       }
 
       if (!SymbolicSub(left_max, right_range->min(), &max)) {
         max =
           RangeBoundary::Sub(Range::ConstantMax(left_range),
                              Range::ConstantMin(right_range),
-                             RangeBoundary::OverflowedMaxSmi());
+                             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)) {
@@ skipping 38 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 Range::IsPositive() const {
+  if (min().IsNegativeInfinity()) {
+    return false;
+  }
+  if (min().LowerBound().value() < 0) {
+    return false;
+  }
+  if (max().IsPositiveInfinity()) {
+    return true;
+  }
+  return max().UpperBound().value() >= 0;
+}
+
+
+bool Range::IsNegative() const {
+  if (max().IsPositiveInfinity()) {
+    return false;
+  }
+  if (max().UpperBound().value() >= 0) {
+    return false;
+  }
+  if (min().IsNegativeInfinity()) {
+    return true;
+  }
+  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) {
+    // Not true.
+    return false;
+  }
+  if (!min().IsNegativeInfinity()) {
+    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 {
-  if (min().LowerBound().value() < min_int) return false;
-  if (max().UpperBound().value() > max_int) return false;
+  if (min().IsNegativeInfinity() || (min().LowerBound().value() < min_int)) {
+    return false;
+  }
+  if (max().IsPositiveInfinity() || (max().UpperBound().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().LowerBound().value();
-  const intptr_t this_max = max().UpperBound().value();
+  const intptr_t this_min = min().IsNegativeInfinity() ?
+      kIntptrMin : min().LowerBound().value();
+  const intptr_t this_max = max().IsPositiveInfinity() ?
+      kIntptrMax : 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()) {
     return true;
   }
   // Symbol case: For example [v+1, v].
   if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
     return true;
   }
   return false;
 }
@@ skipping 11 matching lines @@
   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());
+                                           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.UpperBound().value() < length.LowerBound().value()) {
+  if (max_upper.value() < length_lower.value()) {
     return true;
   }
 
-  length = CanonicalizeBoundary(length, RangeBoundary::OverflowedMaxSmi());
+  length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity());
   if (length.Overflowed()) {
     return false;
   }
 
   // Try symbolic comparison.
   do {
     if (DependOnSameSymbol(max, length)) return max.offset() < length.offset();
   } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length));
 
   // Failed to prove that maximum is bounded with array length.
@@ skipping 273 matching lines @@
     case Token::kTRUNCDIV: return 0;
     case Token::kMOD: return 1;
     default: UNIMPLEMENTED(); return -1;
   }
 }
 
 
 #undef __
 
 }  // namespace dart