Steps towards unification of number bitset and range types.

src/types.h

 // 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.
 
 #ifndef V8_TYPES_H_
 #define V8_TYPES_H_
 
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/handles.h"
@@ skipping 70 matching lines @@
 // Subtyping relates the two dimensions, for example:
 //
 //   Number <= Tagged \/ UntaggedNumber
 //   Object <= TaggedPtr \/ UntaggedPtr
 //
 // That holds because the semantic type constructors defined by the API create
 // types that allow for all possible representations, and dually, the ones for
 // 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')

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

This doesn't make sense on 64 bit. The original comment still seems correct.

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

Done.

 //   Number /\ TaggedPtr            (a heap number)
 //
 //
 // RANGE TYPES
 //
 // A range type represents a continuous integer interval by its minimum and
 // maximum value.  Either value might be an infinity.
 //
 // Constant(v) is considered a subtype of Range(x..y) if v happens to be an
 // integer between x and y.
 //
 //
 // PREDICATES
 //
 // There are two main functions for testing types:
 //
 //   T1->Is(T2)     -- tests whether T1 is included in T2 (i.e., T1 <= T2)
 //   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

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

Similarly here. Please don't encourage use of Signed31.

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

Done.

 // handling (e.g., via T->Maybe(Number())).
 //
 // There is no functionality to discover whether a type is a leaf in the
 // lattice. That is intentional. It should always be possible to refine the
 // lattice (e.g., splitting up number types further) without invalidating any
 // existing assumptions or tests.
 // Consequently, do not normally use Equals for type tests, always use Is!
 //
 // The NowIs operator implements state-sensitive subtying, as described above.
 // Any compilation decision based on such temporary properties requires runtime
@@ skipping 23 matching lines @@
 // - class Type (zone-allocated, for compiler and concurrent compilation)
 // - class HeapType (heap-allocated, for persistent types)
 //
 // Both provide the same API, and the Convert method can be used to interconvert
 // them. For zone types, no query method touches the heap, only constructors do.
 
 
 // -----------------------------------------------------------------------------
 // Values for bitset types
 
+// clang-format off
+
 #define MASK_BITSET_TYPE_LIST(V) \
   V(Representation, 0xfff00000u) \
   V(Semantic,       0x000ffffeu)
 
 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation)
 #define SEMANTIC(k)       ((k) & BitsetType::kSemantic)
 
 #define REPRESENTATION_BITSET_TYPE_LIST(V)    \
   V(None,               0)                    \
   V(UntaggedBit,        1u << 20 | kSemantic) \
@@ skipping 22 matching lines @@
   V(Untagged,           kUntaggedNumber | kUntaggedPointer)                 \
   V(Tagged,             kTaggedSigned | kTaggedPointer)
 
 #define INTERNAL_BITSET_TYPE_LIST(V)                                      \
   V(OtherUnsigned31, 1u << 1 | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(OtherUnsigned32, 1u << 2 | REPRESENTATION(kTagged | kUntaggedNumber)) \
   V(OtherSigned32,   1u << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \
   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)) \
   V(InternalizedString,  1u << 13 | REPRESENTATION(kTaggedPointer)) \
   V(OtherString,         1u << 14 | REPRESENTATION(kTaggedPointer)) \
   V(Undetectable,        1u << 15 | REPRESENTATION(kTaggedPointer)) \
   V(Array,               1u << 16 | REPRESENTATION(kTaggedPointer)) \
   V(OtherObject,         1u << 17 | REPRESENTATION(kTaggedPointer)) \
   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) \
   V(Number,              kOrderedNumber | kNaN) \
   V(String,              kInternalizedString | kOtherString) \
   V(UniqueName,          kSymbol | kInternalizedString) \
   V(Name,                kSymbol | kString) \
   V(NumberOrString,      kNumber | kString) \
   V(PlainPrimitive,      kNumberOrString | kBoolean | kNull | kUndefined) \
   V(Primitive,           kSymbol | kPlainPrimitive) \
   V(DetectableObject,    kArray | kOtherObject) \
   V(DetectableReceiver,  kDetectableObject | kProxy) \
   V(Detectable,          kDetectableReceiver | kNumber | kName) \
   V(Object,              kDetectableObject | kUndetectable) \
   V(Receiver,            kObject | kProxy) \
   V(StringOrReceiver,    kString | kReceiver) \
   V(Unique,              kBoolean | kUniqueName | kNull | kUndefined | \
                          kReceiver) \
   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) \
   REPRESENTATION_BITSET_TYPE_LIST(V) \
   SEMANTIC_BITSET_TYPE_LIST(V)
 
 #define BITSET_TYPE_LIST(V)          \
   MASK_BITSET_TYPE_LIST(V)           \
   REPRESENTATION_BITSET_TYPE_LIST(V) \
   INTERNAL_BITSET_TYPE_LIST(V)       \
@@ skipping 25 matching lines @@
 //   static Handle<Struct>::type struct_create(int tag, int length, Region*);
 //   static void struct_shrink(Handle<Struct>::type, int length);
 //   static int struct_tag(Handle<Struct>::type);
 //   static int struct_length(Handle<Struct>::type);
 //   static Handle<Type>::type struct_get(Handle<Struct>::type, int);
 //   static void struct_set(Handle<Struct>::type, int, Handle<Type>::type);
 //   template<class V>
 //   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* isolate(Region* region);
 // }
 template<class Config>
 class TypeImpl : public Config::Base {
  public:
   // Auxiliary types.
 
   typedef uint32_t bitset;  // Internal
   class BitsetType;         // Internal
   class StructuralType;     // Internal
   class UnionType;          // Internal
@@ skipping 20 matching lines @@
   #define DEFINE_TYPE_CONSTRUCTOR(type, value)                                \
     static TypeImpl* type() {                                                 \
       return BitsetType::New(BitsetType::k##type);                            \
     }                                                                         \
     static TypeHandle type(Region* region) {                                  \
       return BitsetType::New(BitsetType::k##type, region);                    \
     }
   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);
   }
   static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
     return ConstantType::New(value, region);
   }
   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);
   }
   static TypeHandle Array(TypeHandle element, Region* region) {
     return ArrayType::New(element, region);
   }
   static FunctionHandle Function(
       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
     return FunctionType::New(result, receiver, arity, region);
@@ skipping 174 matching lines @@
     DCHECK(this->IsBitset());
     return static_cast<BitsetType*>(this)->Bitset();
   }
   UnionType* AsUnion() { return UnionType::cast(this); }
 
   // Auxiliary functions.
 
   bitset BitsetGlb() { return BitsetType::Glb(this); }
   bitset BitsetLub() { return BitsetType::Lub(this); }
 
+  static bitset SignedSmallBits();

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

Nit: I think these belong to the Bitset class as BitsetType::SignedSmall etc.

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

Done.

+  static bitset UnsignedSmallBits();
+  static bitset NumberBits(bitset bits);
+
   bool SlowIs(TypeImpl* that);
 
   static bool IsInteger(double x) {
     return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities.
   }
   static bool IsInteger(i::Object* x) {
     return x->IsNumber() && IsInteger(x->Number());
   }
 
   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) {
+      i::Factory* f = Config::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 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);
 };
 
 
 // -----------------------------------------------------------------------------
 // Bitset types (internal).
 
 template<class Config>
 class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
  protected:
   friend class TypeImpl<Config>;
 
   enum {
     #define DECLARE_TYPE(type, value) k##type = (value),
     BITSET_TYPE_LIST(DECLARE_TYPE)
     #undef DECLARE_TYPE
     kUnusedEOL = 0
   };
 
   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
   // part and modify intersection and possibly subtyping accordingly.
 
   static bool IsInhabited(bitset bits) {
     return bits & kSemantic;
   }
 
   static bool Is(bitset bits1, bitset bits2) {
     return (bits1 | bits2) == bits2;
   }
 
   static double Min(bitset);
   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);
   static bitset Lub(double value);
   static bitset Lub(double min, double max);
 
   static const char* Name(bitset);
   static void Print(std::ostream& os, bitset);  // NOLINT
 #ifdef DEBUG
   static void Print(bitset);
 #endif
 
  private:
-  struct BitsetMin{
+  struct BitsetBoundary {
     bitset bits;
     double min;
   };
-  static const BitsetMin BitsetMins31[];
-  static const BitsetMin BitsetMins32[];
-  static const BitsetMin* BitsetMins() {
-    return i::SmiValuesAre31Bits() ? BitsetMins31 : BitsetMins32;
+  static const BitsetBoundary BitsetBoundariesArray[];
+  static const BitsetBoundary* BitsetBoundaries() {
+    return BitsetBoundariesArray;
   }
-  static size_t BitsetMinsSize() {
-    return i::SmiValuesAre31Bits() ? 7 : 5;
-    /* arraysize(BitsetMins31) : arraysize(BitsetMins32); */
+  static size_t BitsetBoundariesSize() {
+    return 7;

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

Nit: maybe declare this 'inline' but move it to the .cc file, so that it isn't
disconnected from the definition of the array. (Maybe you can even use arraysize
then.)

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

Done.

+    /* arraysize(BitsetBoundariesArray); */
     // Using arraysize here doesn't compile on Windows.
   }
+
+  static void CheckNumberBits(bitset bits);
 };
 
 
 // -----------------------------------------------------------------------------
 // Superclass for non-bitset types (internal).
 // Contains a tag and a variable number of type or value fields.
 
 template<class Config>
 class TypeImpl<Config>::StructuralType : public TypeImpl<Config> {
  protected:
@@ skipping 126 matching lines @@
 // TODO(neis): Also cache value if numerical.
 // TODO(neis): Allow restricting the representation.
 
 
 // -----------------------------------------------------------------------------
 // Range types.
 
 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) {
     DCHECK(type->IsRange());
     return static_cast<RangeType*>(type);
   }
 };
 // TODO(neis): Also cache min and max values.
 // TODO(neis): Allow restricting the representation.
 
@@ skipping 128 matching lines @@
   static inline Struct* struct_create(int tag, int length, Zone* zone);
   static inline void struct_shrink(Struct* structure, int length);
   static inline int struct_tag(Struct* structure);
   static inline int struct_length(Struct* structure);
   static inline Type* struct_get(Struct* structure, int i);
   static inline void struct_set(Struct* structure, int i, Type* type);
   template<class V>
   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* isolate(Zone* zone);
 };
 
 typedef TypeImpl<ZoneTypeConfig> Type;
 
 
 // -----------------------------------------------------------------------------
 // Heap-allocated types; either smis for bitsets, maps for classes, boxes for
 // constants, or fixed arrays for unions.
 
 struct HeapTypeConfig {
@@ skipping 28 matching lines @@
   static inline int struct_length(i::Handle<Struct> structure);
   static inline i::Handle<Type> struct_get(i::Handle<Struct> structure, int i);
   static inline void struct_set(
       i::Handle<Struct> structure, int i, i::Handle<Type> type);
   template<class V>
   static inline i::Handle<V> struct_get_value(
       i::Handle<Struct> structure, int i);
   template<class V>
   static inline void struct_set_value(
       i::Handle<Struct> structure, int i, i::Handle<V> x);
+  static inline i::Isolate* isolate(Isolate* isolate);
 };
 
 typedef TypeImpl<HeapTypeConfig> HeapType;
 
 
 // -----------------------------------------------------------------------------
 // Type bounds. A simple struct to represent a pair of lower/upper types.
 
 template<class Config>
 struct BoundsImpl {
@@ skipping 50 matching lines @@
   bool Narrows(BoundsImpl that) {
     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
   }
 };
 
 typedef BoundsImpl<ZoneTypeConfig> Bounds;
 
 } }  // namespace v8::internal
 
 #endif  // V8_TYPES_H_