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 e9fc5d6b799b4f088a4cd3d2e249e53b74140f7a..1723ccaf27774859f4aa3e246fc87a2a13136c32 100644
--- a/src/types.h
+++ b/src/types.h
@@ -88,7 +88,7 @@ namespace internal {
 // representation types initially include all semantic ranges. Representations
 // can then e.g. be narrowed for a given semantic type using intersection:
 //
-//   SignedSmall /\ TaggedInt       (a 'smi')
+//   Signed31 /\ TaggedInt       (a 'smi')
 //   Number /\ TaggedPtr            (a heap number)
 //
 //
@@ -109,7 +109,7 @@ namespace internal {
 //   T1->Maybe(T2)  -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0)
 //
 // Typically, the former is to be used to select representations (e.g., via
-// T->Is(SignedSmall())), and the latter to check whether a specific case needs
+// T->Is(Signed31())), and the latter to check whether a specific case needs
 // handling (e.g., via T->Maybe(Number())).
 //
 // There is no functionality to discover whether a type is a leaf in the
@@ -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)) \

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

Hm, I'd really prefer to make any bits referring to odd sizes internal. Would
that work?

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

I am not entirely sure why are these types bad. Eventually, they should be
equivalent to the appropriate ranges.

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

Mainly to prevent misuse --- for portability, nobody should ever use the odd
width types directly, but always the *Small types. That this CL changes all the
tests to use the odd types sends an even stronger signal in the wrong direction,
IMHO. (I don't understand why the tests needed changing either way.)

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

I changed the tests back (where it made sense). 

I agree that we should eventually move more bitsets to be private, but let's do
it later. I can easily see how the discussion of what should or should not be
private delays the CL by weeks.

   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) \
@@ -236,29 +238,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) \
@@ -304,6 +294,7 @@ namespace internal {
 //   static i::Handle<V> struct_get_value(Handle<Struct>::type, int);
 //   template<class V>
 //   static void struct_set_value(Handle<Struct>::type, int, i::Handle<V>);
+//   static i::Isolate* get_isolate(Region* region);

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

Nit: remove the get_ prefix

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

Done.

 // }
 template<class Config>
 class TypeImpl : public Config::Base {
@@ -344,6 +335,17 @@ class TypeImpl : public Config::Base {
   PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
   #undef DEFINE_TYPE_CONSTRUCTOR
 
+  static TypeImpl* SignedSmall() { return BitsetType::New(SignedSmallBits()); }
+  static TypeHandle SignedSmall(Region* region) {
+    return BitsetType::New(SignedSmallBits(), region);
+  }
+  static TypeImpl* UnsignedSmall() {
+    return BitsetType::New(UnsignedSmallBits());
+  }
+  static TypeHandle UnsignedSmall(Region* region) {
+    return BitsetType::New(UnsignedSmallBits(), region);
+  }
+
   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
     return ClassType::New(map, region);
   }
@@ -352,7 +354,9 @@ 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, REPRESENTATION(BitsetType::kTagged |
+                                                   BitsetType::kUntaggedNumber),
+                          region);
   }
   static TypeHandle Context(TypeHandle outer, Region* region) {
     return ContextType::New(outer, region);
@@ -547,6 +551,9 @@ class TypeImpl : public Config::Base {
   bitset BitsetGlb() { return BitsetType::Glb(this); }
   bitset BitsetLub() { return BitsetType::Lub(this); }
 
+  static bitset SignedSmallBits();
+  static bitset UnsignedSmallBits();
+
   bool SlowIs(TypeImpl* that);
 
   static bool IsInteger(double x) {
@@ -559,31 +566,48 @@ 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(range->Representation()) {}
+    static Limits Empty(Region* region) {
+      i::Factory* f = Config::get_isolate(region)->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 NumberBitsetToLimits(bitset bits, Region* region);

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

Nit: ToLimits would seem good enough a name

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

Done.

+
   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);
 };
 
 
@@ -609,13 +633,9 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
 
     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;
+      bitset number_bits = NumberBits(bits);
       if (number_bits != 0) {
-        bitset lub = Lub(Min(number_bits), Max(number_bits)) & mask;
+        bitset lub = SEMANTIC(Lub(Min(number_bits), Max(number_bits)));
         CHECK(lub == number_bits);
       }
     }
@@ -633,6 +653,10 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
     return bits & kSemantic;
   }
 
+  static bitset NumberBits(bitset bits) {

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

Move to same place as (Un)signedSmallBits.

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

Done.

+    return bits & kPlainNumber & kSemantic;
+  }
+
   static bool Is(bitset bits1, bitset bits2) {
     return (bits1 | bits2) == bits2;
   }
@@ -641,6 +665,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);
@@ -658,14 +683,11 @@ class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
     bitset bits;
     double min;
   };
-  static const BitsetMin BitsetMins31[];
-  static const BitsetMin BitsetMins32[];
-  static const BitsetMin* BitsetMins() {
-    return i::SmiValuesAre31Bits() ? BitsetMins31 : BitsetMins32;
-  }
+  static const BitsetMin BitsetMinsArray[];
+  static const BitsetMin* BitsetMins() { return BitsetMinsArray; }
   static size_t BitsetMinsSize() {
-    return i::SmiValuesAre31Bits() ? 7 : 5;
-    /* arraysize(BitsetMins31) : arraysize(BitsetMins32); */
+    return 7;
+    /* arraysize(BitsetMinsArray); */
     // Using arraysize here doesn't compile on Windows.
   }
 };
@@ -789,6 +811,7 @@ template<class Config>
 class TypeImpl<Config>::ConstantType : public StructuralType {
  public:
   TypeHandle Bound() { return this->Get(0); }
+  bitset Representation() { return REPRESENTATION(this->Get(0)->AsBitset()); }

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

Please don't expose bitset functionality in this interfaces. Perhaps we should
simply have a protected method Representation in class Type.

[rossberg, 2014/12/12 15:30:41]

s/in this interfaces/in these public interfaces/

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

Done.

   i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); }
 
   static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
@@ -815,24 +838,33 @@ template<class Config>
 class TypeImpl<Config>::RangeType : public StructuralType {
  public:
   int BitsetLub() { return this->Get(0)->AsBitset(); }
+  bitset Representation() { return REPRESENTATION(BitsetLub()); }

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

Same here.

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

Done.

   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,
+                         bitset representation, Region* region) {

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

For the same reason, make representation a Type here.

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

Done.

     DCHECK(IsInteger(min->Number()) && IsInteger(max->Number()));
     DCHECK(min->Number() <= max->Number());
+    DCHECK(REPRESENTATION(representation) == representation);
+
+    // Make sure the representation does not contain non-number stuff.

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

Shouldn't this better be an assertion?

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

Removed this code. (If we want the point-wise representation interpretation, we
should not look there anyway.)

+    representation &=
+        REPRESENTATION(BitsetType::kTagged | BitsetType::kUntaggedNumber);
+
     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;
+    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, lim.representation, region);
   }
 
   static RangeType* cast(TypeImpl* type) {
@@ -981,6 +1013,7 @@ struct ZoneTypeConfig {
   static inline i::Handle<V> struct_get_value(Struct* structure, int i);
   template<class V> static inline void struct_set_value(
       Struct* structure, int i, i::Handle<V> x);
+  static inline i::Isolate* get_isolate(Zone* zone);
 };
 
 typedef TypeImpl<ZoneTypeConfig> Type;
@@ -1029,6 +1062,7 @@ struct HeapTypeConfig {
   template<class V>
   static inline void struct_set_value(
       i::Handle<Struct> structure, int i, i::Handle<V> x);
+  static inline i::Isolate* get_isolate(Isolate* isolate);
 };
 
 typedef TypeImpl<HeapTypeConfig> HeapType;