Steps towards unification of number bitset and range types.

src/types.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <iomanip>
 
 #include "src/types.h"
 
 #include "src/ostreams.h"
 #include "src/types-inl.h"
@@ skipping 10 matching lines @@
 // Range-related helper functions.
 
 // The result may be invalid (max < min).
 template<class Config>
 typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect(
     Limits lhs, Limits rhs) {
   DisallowHeapAllocation no_allocation;
   Limits result(lhs);
   if (lhs.min->Number() < rhs.min->Number()) result.min = rhs.min;
   if (lhs.max->Number() > rhs.max->Number()) result.max = rhs.max;
+  result.representation = lhs.representation & rhs.representation;
   return result;
 }
 
 
-template<class Config>
-typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(
-    Limits lhs, Limits rhs) {
+template <class Config>
+bool TypeImpl<Config>::IsEmpty(Limits lim) {
+  return lim.representation == BitsetType::kNone ||
+         lim.min->Number() > lim.max->Number();
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(Limits lhs,
+                                                          Limits rhs) {
   DisallowHeapAllocation no_allocation;
+  // Handle the case of empty operand, so that we do not stretch

[rossberg, 2014/12/12 13:57:50]

So this seems to be a case of violating the point-wise interpretation.

[Jarin, 2015/01/08 14:30:27]

Yes, there is more of these - fixing this does not really belong to this change
list, I think.

+  // the limits/representations for them.
+  if (IsEmpty(lhs)) return rhs;
+  if (IsEmpty(rhs)) return lhs;
+
   Limits result(lhs);
   if (lhs.min->Number() > rhs.min->Number()) result.min = rhs.min;
   if (lhs.max->Number() < rhs.max->Number()) result.max = rhs.max;
+  result.representation = lhs.representation | rhs.representation;
   return result;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Overlap(
     typename TypeImpl<Config>::RangeType* lhs,
     typename TypeImpl<Config>::RangeType* rhs) {
   DisallowHeapAllocation no_allocation;
   typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs));
-  return lim.min->Number() <= lim.max->Number();
+  return lim.min->Number() <= lim.max->Number() &&
+         lim.representation != BitsetType::kNone;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Contains(
     typename TypeImpl<Config>::RangeType* lhs,
     typename TypeImpl<Config>::RangeType* rhs) {
   DisallowHeapAllocation no_allocation;
-  return lhs->Min()->Number() <= rhs->Min()->Number()
-      && rhs->Max()->Number() <= lhs->Max()->Number();
+  return lhs->Min()->Number() <= rhs->Min()->Number() &&
+         rhs->Max()->Number() <= lhs->Max()->Number() &&
+         BitsetType::Is(rhs->Representation(), lhs->Representation());
 }
 
 
+template <class Config>
+bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs,

[rossberg, 2014/12/12 13:57:50]

Actually, Contains is a misnomer here and above. The Contains below is used for
inhabitance. These functions are checking subtyping, so should be called
RangeType::Is.

[Jarin, 2015/01/08 14:30:27]

Maybe. Are you suggesting that Contains(RangeType*, RangeType*) should be moved
to RangeType::Is(RangeType*) (non-static) and Contains(ConstantType*,
RangeType*) tp ConstantType::Is(RangeType*)?

[rossberg, 2015/01/15 15:15:11]

Yes, that's perhaps best.

+                                typename TypeImpl<Config>::ConstantType* rhs) {
+  DisallowHeapAllocation no_allocation;
+  return IsInteger(*rhs->Value()) &&
+         lhs->Min()->Number() <= rhs->Value()->Number() &&
+         rhs->Value()->Number() <= lhs->Max()->Number() &&
+         BitsetType::Is(rhs->Representation(), lhs->Representation());
+}
+
+
 template<class Config>
 bool TypeImpl<Config>::Contains(
     typename TypeImpl<Config>::RangeType* range, i::Object* val) {
   DisallowHeapAllocation no_allocation;
-  return IsInteger(val)
-      && range->Min()->Number() <= val->Number()
-      && val->Number() <= range->Max()->Number();
+  bitset value_representation = REPRESENTATION(BitsetType::Lub(val));
+  return IsInteger(val) &&
+         BitsetType::Is(value_representation, range->Representation()) &&
+         range->Min()->Number() <= val->Number() &&
+         val->Number() <= range->Max()->Number();
 }
 
 
 // -----------------------------------------------------------------------------
 // Min and Max computation.
 
 template<class Config>
 double TypeImpl<Config>::Min() {
   DCHECK(this->Is(Number()));
   if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
@@ skipping 35 matching lines @@
 
 // The largest bitset subsumed by this type.
 template<class Config>
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
   DisallowHeapAllocation no_allocation;
   if (type->IsBitset()) {
     return type->AsBitset();
   } else if (type->IsUnion()) {
     SLOW_DCHECK(type->AsUnion()->Wellformed());
-    return type->AsUnion()->Get(0)->BitsetGlb();  // Shortcut.
+    return type->AsUnion()->Get(0)->BitsetGlb() |
+           type->AsUnion()->Get(1)->BitsetGlb();  // Shortcut.
+  } else if (type->IsRange()) {
+    bitset glb = SEMANTIC(BitsetType::Glb(type->AsRange()->Min()->Number(),
+                                          type->AsRange()->Max()->Number()));
+    if (glb == 0) {

[rossberg, 2014/12/12 13:57:50]

(This seems to be another violation of point-wise.)

[Jarin, 2015/01/08 14:30:27]

Unfortunately, I had tests failing because there was an empty type that was not
kNone.

+      return kNone;
+    } else {
+      return glb | type->AsRange()->Representation();
+    }
     // (The remaining BitsetGlb's are None anyway).

[rossberg, 2014/12/12 13:57:50]

Nit: While we're here, can you move this comment down one line?

[Jarin, 2015/01/08 14:30:27]

Done.

   } else {
     return kNone;
   }
 }
 
 
 // The smallest bitset subsuming this type.
 template<class Config>
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
@@ skipping 136 matching lines @@
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Lub(double value) {
   DisallowHeapAllocation no_allocation;
   if (i::IsMinusZero(value)) return kMinusZero;
   if (std::isnan(value)) return kNaN;
   if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
   return kPlainNumber;
 }
 
 
-// Minimum values of regular numeric bitsets when SmiValuesAre31Bits.
+// Minimum values of regular numeric bitsets.
 template <class Config>
 const typename TypeImpl<Config>::BitsetType::BitsetMin
-    TypeImpl<Config>::BitsetType::BitsetMins31[] = {
+    TypeImpl<Config>::BitsetType::BitsetMinsArray[] = {
         {kOtherNumber, -V8_INFINITY},
         {kOtherSigned32, kMinInt},
-        {kNegativeSignedSmall, -0x40000000},
-        {kUnsignedSmall, 0},
+        {kNegative31, -0x40000000},
+        {kUnsigned30, 0},
         {kOtherUnsigned31, 0x40000000},
         {kOtherUnsigned32, 0x80000000},
         {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}};
 
 
-// Minimum values of regular numeric bitsets when SmiValuesAre32Bits.
-// OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h).
-template <class Config>
-const typename TypeImpl<Config>::BitsetType::BitsetMin
-    TypeImpl<Config>::BitsetType::BitsetMins32[] = {
-        {kOtherNumber, -V8_INFINITY},
-        {kNegativeSignedSmall, kMinInt},
-        {kUnsignedSmall, 0},
-        {kOtherUnsigned32, 0x80000000},
-        {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}};
-
-
 template<class Config>
 typename TypeImpl<Config>::bitset
 TypeImpl<Config>::BitsetType::Lub(double min, double max) {
   DisallowHeapAllocation no_allocation;
   int lub = kNone;
   const BitsetMin* mins = BitsetMins();
 
   // Make sure the min-max range touches 0, so we are guaranteed no holes
   // in unions of valid bitsets.
   if (max < -1) max = -1;
   if (min > 0) min = 0;
 
   for (size_t i = 1; i < BitsetMinsSize(); ++i) {
     if (min < mins[i].min) {
       lub |= mins[i-1].bits;
       if (max < mins[i].min) return lub;
     }
   }
   return lub |= mins[BitsetMinsSize()-1].bits;
 }
 
 
-template<class Config>
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::Glb(
+    double min, double max) {
+  DisallowHeapAllocation no_allocation;
+  int glb = kNone;
+  const BitsetMin* mins = BitsetMins();
+
+  // If the range does not touch 0, the bound is empty.
+  if (max < -1) return glb;
+  if (min > 0) return glb;

[rossberg, 2014/12/12 13:57:51]

Nit: merge with previous line.

[Jarin, 2015/01/08 14:30:27]

Done.

+
+  for (size_t i = 1; i < BitsetMinsSize(); ++i) {
+    if (min <= mins[i].min) {
+      if (i + 1 < BitsetMinsSize() && max + 1 < mins[i + 1].min) break;
+      glb |= mins[i].bits;
+    }
+  }
+  // OtherNumber also contains float numbers, so it can never be
+  // in the greatest lower bound. (There is also the small trouble
+  // of kOtherNumber having a range hole, which we can conveniently
+  // ignore here.)
+  return glb & ~(SEMANTIC(kOtherNumber));
+}
+
+
+template <class Config>
 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
   DisallowHeapAllocation no_allocation;
   DCHECK(Is(bits, kNumber));
   const BitsetMin* mins = BitsetMins();
   bool mz = SEMANTIC(bits & kMinusZero);
   for (size_t i = 0; i < BitsetMinsSize(); ++i) {
     if (Is(SEMANTIC(mins[i].bits), bits)) {
       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
     }
   }
   if (mz) return 0;
   return base::OS::nan_value();
 }
 
 
 template<class Config>
 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
   DisallowHeapAllocation no_allocation;
   DCHECK(Is(bits, kNumber));
   const BitsetMin* mins = BitsetMins();
   bool mz = SEMANTIC(bits & kMinusZero);
-  if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) {
+  if (BitsetType::Is(SEMANTIC(mins[BitsetMinsSize() - 1].bits), bits)) {
     return +V8_INFINITY;
   }
   for (size_t i = BitsetMinsSize()-1; i-- > 0; ) {
     if (Is(SEMANTIC(mins[i].bits), bits)) {
       return mz ?
           std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
     }
   }
   if (mz) return 0;
   return base::OS::nan_value();
@@ skipping 35 matching lines @@
     for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
     }
     return true;
   }
   UNREACHABLE();
   return false;
 }
 
 
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::SignedSmallBits() {
+  return i::SmiValuesAre31Bits() ? BitsetType::kSigned31
+                                 : BitsetType::kSigned32;
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::bitset TypeImpl<Config>::UnsignedSmallBits() {
+  return i::SmiValuesAre31Bits() ? BitsetType::kUnsigned30
+                                 : BitsetType::kUnsigned31;
+}
+
+
 // Check if [this] <= [that].
 template<class Config>
 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
 
   if (that->IsBitset()) {
     return BitsetType::Is(this->BitsetLub(), that->AsBitset());
   }
   if (this->IsBitset()) {
     return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
@@ skipping 10 matching lines @@
   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
   if (that->IsUnion()) {
     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
       if (this->Is(that->AsUnion()->Get(i))) return true;
       if (i > 1 && this->IsRange()) return false;  // Shortcut.
     }
     return false;
   }
 
   if (that->IsRange()) {
-    return (this->IsRange() && Contains(that->AsRange(), this->AsRange()))
-        || (this->IsConstant() &&
-            Contains(that->AsRange(), *this->AsConstant()->Value()));
+    return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
+           (this->IsConstant() &&
+            Contains(that->AsRange(), this->AsConstant()));
   }
   if (this->IsRange()) return false;
 
   return this->SimplyEquals(that);
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
   DisallowHeapAllocation no_allocation;
@@ skipping 41 matching lines @@
   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
   if (that->IsUnion()) {
     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
       if (this->Maybe(that->AsUnion()->Get(i))) return true;
     }
     return false;
   }
 
   if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
     return false;
-  if (this->IsBitset() || that->IsBitset()) return true;

[rossberg, 2014/12/12 13:57:50]

I think you want to keep this short-cut to make the bitset case as fast as
possible. But it now has to be && not ||.

[Jarin, 2015/01/08 14:30:27]

Done.

-
   if (this->IsClass() != that->IsClass()) return true;
 
   if (this->IsRange()) {
     if (that->IsConstant()) {
-      return Contains(this->AsRange(), *that->AsConstant()->Value());
+      return Contains(this->AsRange(), that->AsConstant());
     }
-    return that->IsRange() && Overlap(this->AsRange(), that->AsRange());
+    if (that->IsRange()) {
+      return Overlap(this->AsRange(), that->AsRange());
+    }
+    if (that->IsBitset()) {
+      bitset number_bits = BitsetType::NumberBits(that->AsBitset());
+      if (number_bits == BitsetType::kNone) {
+        return false;
+      }
+      if ((REPRESENTATION(that->AsBitset()) &
+           this->AsRange()->Representation()) == BitsetType::kNone) {
+        return false;
+      }
+      double min = std::max(BitsetType::Min(number_bits), this->Min());
+      double max = std::min(BitsetType::Max(number_bits), this->Max());
+      return min <= max;
+    }
   }
   if (that->IsRange()) {
-    if (this->IsConstant()) {
-      return Contains(that->AsRange(), *this->AsConstant()->Value());
-    }
-    return this->IsRange() && Overlap(this->AsRange(), that->AsRange());
+    return that->Maybe(this);  // This case is handled above.
   }
 
+  if (this->IsBitset() || that->IsBitset()) return true;
+
   return this->SimplyEquals(that);
 }
 
 
 // Return the range in [this], or [NULL].
 template<class Config>
 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
   DisallowHeapAllocation no_allocation;
   if (this->IsRange()) return this->AsRange();
   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
     return this->AsUnion()->Get(1)->AsRange();
   }
   return NULL;
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::Contains(i::Object* value) {
   DisallowHeapAllocation no_allocation;
   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
     if (*it.Current() == value) return true;
   }
   if (IsInteger(value)) {
     RangeType* range = this->GetRange();
-    if (range != NULL && Contains(range, value)) return true;
+    if (range != NULL && Contains(range, value)) {
+      return true;

[rossberg, 2014/12/12 13:57:51]

Nit: any reason for this reformat? It's now inconsistent with 5 lines above.

[Jarin, 2015/01/08 14:30:27]

Done.

+    }
   }
   return BitsetType::New(BitsetType::Lub(value))->Is(this);
 }
 
 
 template<class Config>
 bool TypeImpl<Config>::UnionType::Wellformed() {
   DisallowHeapAllocation no_allocation;
   // This checks the invariants of the union representation:
   // 1. There are at least two elements.
-  // 2. At most one element is a bitset, and it must be the first one.
-  // 3. At most one element is a range, and it must be the second one
+  // 2. If there is a range, then the bitset type does not contain

[rossberg, 2014/12/12 13:57:50]

Nit: move this down two places (or to the end) for a more natural reading order.

[Jarin, 2015/01/08 14:30:27]

Done.

+  //    plain number bits.
+  // 3. At most one element is a bitset, and it must be the first one.
+  // 4. At most one element is a range, and it must be the second one
   //    (even when the first element is not a bitset).
-  // 4. No element is itself a union.
-  // 5. No element is a subtype of any other.
+  // 5. No element is itself a union.
+  // 6. No element is a subtype of any other.
   DCHECK(this->Length() >= 2);  // (1)
+
+  bitset number_bits = this->Get(0)->IsBitset()
+                           ? BitsetType::NumberBits(this->Get(0)->AsBitset())
+                           : 0;
+  DCHECK(!this->Get(1)->IsRange() || (number_bits == 0));  // (2)
+
   for (int i = 0; i < this->Length(); ++i) {
-    if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2)
-    if (i != 1) DCHECK(!this->Get(i)->IsRange());  // (3)
-    DCHECK(!this->Get(i)->IsUnion());  // (4)
+    if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (3)
+    if (i != 1) DCHECK(!this->Get(i)->IsRange());   // (4)
+    DCHECK(!this->Get(i)->IsUnion());               // (5)
     for (int j = 0; j < this->Length(); ++j) {
-      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
+      if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (6)
     }
   }
   return true;
 }
 
 
 // -----------------------------------------------------------------------------
 // Union and intersection
 
 
@@ skipping 28 matching lines @@
   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
   if (!AddIsSafe(size1, size2)) return Any(region);
   int size = size1 + size2;
   if (!AddIsSafe(size, 2)) return Any(region);
   size += 2;
   UnionHandle result = UnionType::New(size, region);
   size = 0;
 
   // Deal with bitsets.
   result->Set(size++, BitsetType::New(bits, region));
+  // Insert a placeholder for the range.
+  result->Set(size++, None(region));
 
-  // Deal with ranges.
-  TypeHandle range = None(region);
-  RangeType* range1 = type1->GetRange();
-  RangeType* range2 = type2->GetRange();
-  if (range1 != NULL && range2 != NULL) {
-    Limits lim = Intersect(Limits(range1), Limits(range2));
-    if (lim.min->Number() <= lim.max->Number()) {
-      range = RangeType::New(lim, region);
+  Limits lims = Limits::Empty(region);
+  size = IntersectAux(type1, type2, result, size, &lims, region);
+
+  // If the range is not empty, then insert it into the union and
+  // remove the number bits from the bitset.
+  if (!IsEmpty(lims)) {
+    UpdateRange(RangeType::New(lims, region), result, size, region);
+
+    // Remove the number bits.
+    bitset number_bits = BitsetType::NumberBits(bits);
+    bits &= ~number_bits;
+    if (SEMANTIC(bits) == BitsetType::kNone) {
+      bits = BitsetType::kNone;
     }
+    result->Set(0, BitsetType::New(bits, region));
   }
-  result->Set(size++, range);
-
-  size = IntersectAux(type1, type2, result, size, region);
   return NormalizeUnion(result, size);
 }
 
 
 template<class Config>
 int TypeImpl<Config>::UpdateRange(
     RangeHandle range, UnionHandle result, int size, Region* region) {
   TypeHandle old_range = result->Get(1);
   DCHECK(old_range->IsRange() || old_range->IsNone());
   if (range->Is(old_range)) return size;
   if (!old_range->Is(range->unhandle())) {
     range = RangeType::New(
         Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region);
   }
   result->Set(1, range);
 
   // Remove any components that just got subsumed.
   for (int i = 2; i < size; ) {
     if (result->Get(i)->Is(range->unhandle())) {
       result->Set(i, result->Get(--size));
     } else {
       ++i;
     }
   }
   return size;
 }
 
 
-template<class Config>
-int TypeImpl<Config>::IntersectAux(
-    TypeHandle lhs, TypeHandle rhs,
-    UnionHandle result, int size, Region* region) {
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::NumberBitsetToLimits(
+    bitset bits, Region* region) {
+  bitset representation = REPRESENTATION(bits);
+  bitset number_bits = BitsetType::NumberBits(bits);
+
+  if (representation == BitsetType::kNone && number_bits == BitsetType::kNone) {
+    return Limits::Empty(region);
+  }
+
+  double bitset_min = BitsetType::Min(number_bits);
+  double bitset_max = BitsetType::Max(number_bits);
+
+  // TODO(jarin) Get rid of the heap numbers.
+  i::Factory* f = Config::get_isolate(region)->factory();
+
+  return Limits(f->NewNumber(bitset_min), f->NewNumber(bitset_max),
+                representation);
+}
+
+
+template <class Config>
+typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset(
+    TypeHandle range, TypeHandle bitset, Region* region) {
+  Limits range_lims(range->AsRange());
+  Limits bitset_lims = NumberBitsetToLimits(bitset->AsBitset(), region);
+  return Intersect(range_lims, bitset_lims);
+}
+
+
+template <class Config>
+int TypeImpl<Config>::IntersectAux(TypeHandle lhs, TypeHandle rhs,
+                                   UnionHandle result, int size, Limits* lims,
+                                   Region* region) {
   if (lhs->IsUnion()) {
     for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
-      size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region);
+      size =
+          IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, region);
     }
     return size;
   }
   if (rhs->IsUnion()) {
     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
-      size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region);
+      size =
+          IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region);
     }
     return size;
   }
 
   if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
     return size;
   }
 
   if (lhs->IsRange()) {
-    if (rhs->IsBitset() || rhs->IsClass()) {
-      return UpdateRange(
-          Config::template cast<RangeType>(lhs), result, size, region);
+    if (rhs->IsBitset()) {
+      Limits lim = IntersectRangeAndBitset(lhs, rhs, region);
+
+      if (!IsEmpty(lim)) {
+        *lims = Union(lim, *lims);
+      }
+      return size;
     }
-    if (rhs->IsConstant() &&
-        Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) {
+    if (rhs->IsClass()) {
+      *lims = Union(Limits(rhs->AsRange()), *lims);
+    }
+    if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
       return AddToUnion(rhs, result, size, region);
     }
+    if (rhs->IsRange()) {
+      Limits lim = Intersect(Limits(lhs->AsRange()), Limits(rhs->AsRange()));
+      if (!IsEmpty(lim)) {
+        *lims = Union(lim, *lims);
+      }
+    }
     return size;
   }
   if (rhs->IsRange()) {
-    if (lhs->IsBitset() || lhs->IsClass()) {
-      return UpdateRange(
-          Config::template cast<RangeType>(rhs), result, size, region);
+    if (lhs->IsBitset()) {
+      Limits lim = IntersectRangeAndBitset(rhs, lhs, region);
+
+      if (!IsEmpty(lim)) {
+        *lims = Union(lim, *lims);
+      }
+      return size;
     }
-    if (lhs->IsConstant() &&
-        Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) {
+    if (lhs->IsClass()) {
+      *lims = Union(Limits(rhs->AsRange()), *lims);
+    }
+    if (lhs->IsConstant() && Contains(rhs->AsRange(), lhs->AsConstant())) {
       return AddToUnion(lhs, result, size, region);
     }
     return size;
   }
 
   if (lhs->IsBitset() || rhs->IsBitset()) {
     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
   }
   if (lhs->IsClass() != rhs->IsClass()) {
     return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region);
   }
   if (lhs->SimplyEquals(rhs->unhandle())) {
     return AddToUnion(lhs, result, size, region);
   }
   return size;
 }
 
 
+// Make sure that we produce a well-formed range and bitset:
+// If the range is non-empty, the number bits in the bitset should be
+// clear. Moreover, if we have a canonical range (such as Signed32(),
+// we want to produce a bitset rather than a range.
+template <class Config>
+typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeRangeAndBitset(
+    RangeHandle range, bitset* bits, Region* region) {
+  // Fast path: If the bitset does not mention numbers, we can just keep the
+  // range.
+  bitset number_bits = BitsetType::NumberBits(*bits);
+  if (number_bits == 0) {
+    return range;
+  }
+
+  // If the range is contained within the bitset, return an empty range
+  // (but make sure we take the representation).
+  bitset range_lub = range->BitsetLub();
+  if (BitsetType::Is(BitsetType::NumberBits(range_lub), *bits)) {
+    *bits |= range_lub;
+    return None(region);
+  }
+
+  // Slow path: reconcile the bitset range and the range.
+  double bitset_min = BitsetType::Min(number_bits);
+  double bitset_max = BitsetType::Max(number_bits);
+
+  i::Handle<i::Object> range_min_obj = range->Min();
+  i::Handle<i::Object> range_max_obj = range->Max();
+  double range_min = range_min_obj->Number();
+  double range_max = range_max_obj->Number();
+
+  bitset range_representation = REPRESENTATION(range->BitsetLub());
+  bitset bits_representation = REPRESENTATION(*bits);
+  bitset representation = bits_representation | range_representation;
+
+  // Remove the number bits from the bitset, they would just confuse us now.
+  *bits &= ~number_bits;
+  if (bits_representation == *bits) {
+    *bits = BitsetType::kNone;

[rossberg, 2014/12/12 13:57:51]

Hm, why do we clear bits here? Can't it still contain unrelated bits?

[Jarin, 2015/01/08 14:30:27]

I am not sure what you mean here. The kNone type is not really clearing bits, it
is just canonical form for empty type (which we do require in some places).

As for the "*bits &= ~number_bits" line, we are actually keeping the unrelated
bits, we are not clearing them.

[rossberg, 2015/01/15 15:15:11]

Yes, but I'm (still) confused why the empty type is set here if no semantic bits
are left. Can you add a comment? Is this to avoid an uninhabited type?

[Jarin, 2015/01/16 16:28:39]

This is because of the assertion at types.h:631 'DCHECK(bits == kNone ||
IsInhabited(bits));'. I do not think we should worry about this - as discussed,
we will have to re-design representations anyway.

+  }
+
+  if (representation == range_representation && range_min <= bitset_min &&
+      range_max >= bitset_max) {
+    // Bitset is contained within the range, just return the range.
+    return range;
+  }
+
+  if (bitset_min < range_min) {
+    range_min_obj =
+        Config::get_isolate(region)->factory()->NewNumber(bitset_min);
+  }
+  if (bitset_max > range_max) {
+    range_max_obj =
+        Config::get_isolate(region)->factory()->NewNumber(bitset_max);
+  }
+  return RangeType::New(range_min_obj, range_max_obj, representation, region);
+}
+
+
 template<class Config>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
     TypeHandle type1, TypeHandle type2, Region* region) {
 
   // Fast case: bit sets.
   if (type1->IsBitset() && type2->IsBitset()) {
     return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
   }
 
   // Fast case: top or bottom types.
   if (type1->IsAny() || type2->IsNone()) return type1;
   if (type2->IsAny() || type1->IsNone()) return type2;
 
   // Semi-fast case.
   if (type1->Is(type2)) return type2;
   if (type2->Is(type1)) return type1;
 
   // Slow case: create union.
   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
   if (!AddIsSafe(size1, size2)) return Any(region);
   int size = size1 + size2;
   if (!AddIsSafe(size, 2)) return Any(region);
   size += 2;
   UnionHandle result = UnionType::New(size, region);
   size = 0;
 
-  // Deal with bitsets.
-  TypeHandle bits = BitsetType::New(
-      type1->BitsetGlb() | type2->BitsetGlb(), region);
-  result->Set(size++, bits);
+  // Compute the new bitset.
+  bitset new_bitset = type1->BitsetGlb() | type2->BitsetGlb();
 
   // Deal with ranges.
   TypeHandle range = None(region);
   RangeType* range1 = type1->GetRange();
   RangeType* range2 = type2->GetRange();
   if (range1 != NULL && range2 != NULL) {
-    range = RangeType::New(Union(Limits(range1), Limits(range2)), region);
+    Limits lims = Union(Limits(range1), Limits(range2));
+    RangeHandle union_range = RangeType::New(lims, region);
+    range = NormalizeRangeAndBitset(union_range, &new_bitset, region);
   } else if (range1 != NULL) {
-    range = handle(range1);
+    range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region);
   } else if (range2 != NULL) {
-    range = handle(range2);
+    range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region);
   }
+  TypeHandle bits = BitsetType::New(new_bitset, region);
+  result->Set(size++, bits);

[rossberg, 2014/12/12 13:57:50]

Maybe only add bits and range here if non-empty?

[Jarin, 2015/01/08 14:30:27]

Let's do that later (if at all), once we figure out what to do with
representations.

   result->Set(size++, range);
 
   size = AddToUnion(type1, result, size, region);
   size = AddToUnion(type2, result, size, region);
   return NormalizeUnion(result, size);
 }
 
 
 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
 // Return new size of [result].
@@ skipping 141 matching lines @@
 template<class OtherType>
 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
     typename OtherType::TypeHandle type, Region* region) {
   if (type->IsBitset()) {
     return BitsetType::New(type->AsBitset(), region);
   } else if (type->IsClass()) {
     return ClassType::New(type->AsClass()->Map(), region);
   } else if (type->IsConstant()) {
     return ConstantType::New(type->AsConstant()->Value(), region);
   } else if (type->IsRange()) {
-    return RangeType::New(
-        type->AsRange()->Min(), type->AsRange()->Max(), region);
+    return RangeType::New(type->AsRange()->Min(), type->AsRange()->Max(),
+                          type->AsRange()->Representation(), region);
   } else if (type->IsContext()) {
     TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
     return ContextType::New(outer, region);
   } else if (type->IsUnion()) {
     int length = type->AsUnion()->Length();
     UnionHandle unioned = UnionType::New(length, region);
     for (int i = 0; i < length; ++i) {
       TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
       unioned->Set(i, t);
     }
@@ skipping 51 matching lines @@
     os << name;
     return;
   }
 
   static const bitset named_bitsets[] = {
 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
       REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
 #undef BITSET_CONSTANT
 
 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
-      INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
-      SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
+          INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
+              SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)

[rossberg, 2014/12/12 13:57:51]

Nit: indentation

[Jarin, 2015/01/08 14:30:27]

Done.

 #undef BITSET_CONSTANT
   };
 
   bool is_first = true;
   os << "(";
   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
     bitset subset = named_bitsets[i];
     if ((bits & subset) == subset) {
       if (!is_first) os << " | ";
       is_first = false;
@@ skipping 92 matching lines @@
 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
 
 template TypeImpl<ZoneTypeConfig>::TypeHandle
   TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
     TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
 template TypeImpl<HeapTypeConfig>::TypeHandle
   TypeImpl<HeapTypeConfig>::Convert<Type>(
     TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
 
 } }  // namespace v8::internal