Reland of "Steps towards unification of number bitset and range types."

src/types.h

Index: src/types.h
diff --git a/src/types.h b/src/types.h
index 4b7d8ba9795b9919a6733a299a82d66cb6a11165..0f59c0c8394402d185e8e1207424a99b28ad5e18 100644
--- a/src/types.h
+++ b/src/types.h
@@ -153,6 +153,8 @@ namespace internal {
 // -----------------------------------------------------------------------------
 // Values for bitset types
 
+// clang-format off
+
 #define MASK_BITSET_TYPE_LIST(V) \
   V(Representation, 0xfff00000u) \
   V(Semantic,       0x000ffffeu)
@@ -195,11 +197,11 @@ namespace internal {
   V(OtherNumber,     1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber))
 
 #define SEMANTIC_BITSET_TYPE_LIST(V) \
-  V(NegativeSignedSmall, 1u << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Negative31,          1u << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(Null,                1u << 6  | REPRESENTATION(kTaggedPointer)) \
   V(Undefined,           1u << 7  | REPRESENTATION(kTaggedPointer)) \
   V(Boolean,             1u << 8  | REPRESENTATION(kTaggedPointer)) \
-  V(UnsignedSmall,       1u << 9  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Unsigned30,          1u << 9  | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(MinusZero,           1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(NaN,                 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(Symbol,              1u << 12 | REPRESENTATION(kTaggedPointer)) \
@@ -211,11 +213,11 @@ namespace internal {
   V(Proxy,               1u << 18 | REPRESENTATION(kTaggedPointer)) \
   V(Internal,            1u << 19 | REPRESENTATION(kTagged | kUntagged)) \
   \
-  V(SignedSmall,         kUnsignedSmall | kNegativeSignedSmall) \
-  V(Signed32,            kSignedSmall | kOtherUnsigned31 | kOtherSigned32) \
-  V(NegativeSigned32,    kNegativeSignedSmall | kOtherSigned32) \
-  V(NonNegativeSigned32, kUnsignedSmall | kOtherUnsigned31) \
-  V(Unsigned32,          kUnsignedSmall | kOtherUnsigned31 | kOtherUnsigned32) \
+  V(Signed31,            kUnsigned30 | kNegative31) \
+  V(Signed32,            kSigned31 | kOtherUnsigned31 | kOtherSigned32) \
+  V(Negative32,          kNegative31 | kOtherSigned32) \
+  V(Unsigned31,          kUnsigned30 | kOtherUnsigned31) \
+  V(Unsigned32,          kUnsigned30 | kOtherUnsigned31 | kOtherUnsigned32) \
   V(Integral32,          kSigned32 | kUnsigned32) \
   V(PlainNumber,         kIntegral32 | kOtherNumber) \
   V(OrderedNumber,       kPlainNumber | kMinusZero) \
@@ -237,29 +239,17 @@ namespace internal {
   V(NonNumber,           kUnique | kString | kInternal) \
   V(Any,                 0xfffffffeu)
 
+// clang-format on
 
 /*
  * The following diagrams show how integers (in the mathematical sense) are
  * divided among the different atomic numerical types.
  *
- * If SmiValuesAre31Bits():
- *
- *   ON    OS32     OSS     US     OU31    OU32     ON
+ *   ON    OS32     N31     U30     OU31    OU32     ON
  * ______[_______[_______[_______[_______[_______[_______
  *     -2^31   -2^30     0      2^30    2^31    2^32
  *
- * Otherwise:
- *
- *   ON         OSS             US         OU32     ON
- * ______[_______________[_______________[_______[_______
- *     -2^31             0              2^31    2^32
- *
- *
  * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1.
- *
- * NOTE: OtherSigned32 (OS32) and OU31 (OtherUnsigned31) are empty if Smis are
- *       32-bit wide.  They should thus never be used directly, only indirectly
- *       via e.g. Number.
  */
 
 #define PROPER_BITSET_TYPE_LIST(V) \
@@ -345,6 +335,19 @@ class TypeImpl : public Config::Base {
   PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
   #undef DEFINE_TYPE_CONSTRUCTOR
 
+  static TypeImpl* SignedSmall() {
+    return BitsetType::New(BitsetType::SignedSmall());
+  }
+  static TypeHandle SignedSmall(Region* region) {
+    return BitsetType::New(BitsetType::SignedSmall(), region);
+  }
+  static TypeImpl* UnsignedSmall() {
+    return BitsetType::New(BitsetType::UnsignedSmall());
+  }
+  static TypeHandle UnsignedSmall(Region* region) {
+    return BitsetType::New(BitsetType::UnsignedSmall(), region);
+  }
+
   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
     return ClassType::New(map, region);
   }
@@ -353,7 +356,11 @@ class TypeImpl : public Config::Base {
   }
   static TypeHandle Range(
       i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
-    return RangeType::New(min, max, region);
+    return RangeType::New(
+        min, max, BitsetType::New(REPRESENTATION(BitsetType::kTagged |
+                                                 BitsetType::kUntaggedNumber),
+                                  region),
+        region);
   }
   static TypeHandle Context(TypeHandle outer, Region* region) {
     return ContextType::New(outer, region);
@@ -560,31 +567,49 @@ class TypeImpl : public Config::Base {
   struct Limits {
     i::Handle<i::Object> min;
     i::Handle<i::Object> max;
-    Limits(i::Handle<i::Object> min, i::Handle<i::Object> max) :
-      min(min), max(max) {}
-    explicit Limits(RangeType* range) :
-      min(range->Min()), max(range->Max()) {}
+    bitset representation;
+    Limits(i::Handle<i::Object> min, i::Handle<i::Object> max,
+           bitset representation)
+        : min(min), max(max), representation(representation) {}
+    explicit Limits(RangeType* range)
+        : min(range->Min()),
+          max(range->Max()),
+          representation(REPRESENTATION(range->Bound()->AsBitset())) {}
+    static Limits Empty(Region* region) {
+      // TODO(jarin) Get rid of the heap numbers.
+      i::Factory* f = i::Isolate::Current()->factory();
+      i::Handle<i::Object> min = f->NewNumber(1);
+      i::Handle<i::Object> max = f->NewNumber(0);
+      return Limits(min, max, BitsetType::kNone);
+    }
   };
 
+  static bool IsEmpty(Limits lim);
   static Limits Intersect(Limits lhs, Limits rhs);
   static Limits Union(Limits lhs, Limits rhs);
   static bool Overlap(RangeType* lhs, RangeType* rhs);
   static bool Contains(RangeType* lhs, RangeType* rhs);
+  static bool Contains(RangeType* range, ConstantType* constant);
   static bool Contains(RangeType* range, i::Object* val);
 
   static int UpdateRange(
       RangeHandle type, UnionHandle result, int size, Region* region);
 
+  static Limits IntersectRangeAndBitset(TypeHandle range, TypeHandle bits,
+                                        Region* region);
+  static Limits ToLimits(bitset bits, Region* region);
+
   bool SimplyEquals(TypeImpl* that);
   template<class TypeHandle>
   bool SimplyEquals(TypeHandle that) { return this->SimplyEquals(*that); }
 
   static int AddToUnion(
       TypeHandle type, UnionHandle result, int size, Region* region);
-  static int IntersectAux(
-      TypeHandle type, TypeHandle other,
-      UnionHandle result, int size, Region* region);
+  static int IntersectAux(TypeHandle type, TypeHandle other, UnionHandle result,
+                          int size, Limits* limits, Region* region);
   static TypeHandle NormalizeUnion(UnionHandle unioned, int size);
+  static TypeHandle NormalizeRangeAndBitset(RangeHandle range, bitset* bits,
+                                            Region* region);
 };
 
 
@@ -603,28 +628,17 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
     kUnusedEOL = 0
   };
 
+  static bitset SignedSmall();
+  static bitset UnsignedSmall();
+
   bitset Bitset() { return Config::as_bitset(this); }
 
   static TypeImpl* New(bitset bits) {
-    DCHECK(bits == kNone || IsInhabited(bits));
-
-    if (FLAG_enable_slow_asserts) {
-      // Check that the bitset does not contain any holes in number ranges.
-      bitset mask = kSemantic;
-      if (!i::SmiValuesAre31Bits()) {
-        mask &= ~(kOtherUnsigned31 | kOtherSigned32);
-      }
-      bitset number_bits = bits & kPlainNumber & mask;
-      if (number_bits != 0) {
-        bitset lub = Lub(Min(number_bits), Max(number_bits)) & mask;
-        CHECK(lub == number_bits);
-      }
-    }
-
+    if (FLAG_enable_slow_asserts) CheckNumberBits(bits);
     return Config::from_bitset(bits);
   }
   static TypeHandle New(bitset bits, Region* region) {
-    DCHECK(bits == kNone || IsInhabited(bits));
+    if (FLAG_enable_slow_asserts) CheckNumberBits(bits);
     return Config::from_bitset(bits, region);
   }
   // TODO(neis): Eventually allow again for types with empty semantics
@@ -642,6 +656,7 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
   static double Max(bitset);
 
   static bitset Glb(TypeImpl* type);  // greatest lower bound that's a bitset
+  static bitset Glb(double min, double max);
   static bitset Lub(TypeImpl* type);  // least upper bound that's a bitset
   static bitset Lub(i::Map* map);
   static bitset Lub(i::Object* value);
@@ -654,21 +669,18 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
   static void Print(bitset);
 #endif
 
+  static bitset NumberBits(bitset bits);
+
  private:
-  struct BitsetMin{
+  struct Boundary {
     bitset bits;
     double min;
   };
-  static const BitsetMin BitsetMins31[];
-  static const BitsetMin BitsetMins32[];
-  static const BitsetMin* BitsetMins() {
-    return i::SmiValuesAre31Bits() ? BitsetMins31 : BitsetMins32;
-  }
-  static size_t BitsetMinsSize() {
-    return i::SmiValuesAre31Bits() ? 7 : 5;
-    /* arraysize(BitsetMins31) : arraysize(BitsetMins32); */
-    // Using arraysize here doesn't compile on Windows.
-  }
+  static const Boundary BoundariesArray[];
+  static inline const Boundary* Boundaries();
+  static inline size_t BoundariesSize();
+
+  static void CheckNumberBits(bitset bits);
 };
 
 
@@ -815,25 +827,31 @@ class TypeImpl<Config>::ConstantType : public StructuralType {
 template<class Config>
 class TypeImpl<Config>::RangeType : public StructuralType {
  public:
-  int BitsetLub() { return this->Get(0)->AsBitset(); }
+  TypeHandle Bound() { return this->Get(0); }
   i::Handle<i::Object> Min() { return this->template GetValue<i::Object>(1); }
   i::Handle<i::Object> Max() { return this->template GetValue<i::Object>(2); }
 
-  static RangeHandle New(
-      i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
+  static RangeHandle New(i::Handle<i::Object> min, i::Handle<i::Object> max,
+                         TypeHandle representation, Region* region) {
     DCHECK(IsInteger(min->Number()) && IsInteger(max->Number()));
     DCHECK(min->Number() <= max->Number());
+    bitset representation_bits = representation->AsBitset();
+    DCHECK(REPRESENTATION(representation_bits) == representation_bits);
+
     RangeHandle type = Config::template cast<RangeType>(
         StructuralType::New(StructuralType::kRangeTag, 3, region));
-    type->Set(0, BitsetType::New(
-        BitsetType::Lub(min->Number(), max->Number()), region));
+
+    bitset bits = SEMANTIC(BitsetType::Lub(min->Number(), max->Number())) |
+                  representation_bits;
+    type->Set(0, BitsetType::New(bits, region));
     type->SetValue(1, min);
     type->SetValue(2, max);
     return type;
   }
 
   static RangeHandle New(Limits lim, Region* region) {
-    return New(lim.min, lim.max, region);
+    return New(lim.min, lim.max, BitsetType::New(lim.representation, region),
+               region);
   }
 
   static RangeType* cast(TypeImpl* type) {