Reland of "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 135 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 65 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(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);
   }
   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 186 matching lines @@
   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) {
+      // 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);
 };
 
 
 // -----------------------------------------------------------------------------
 // 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
   };
 
+  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
   // 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
 
+  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);
 };
 
 
 // -----------------------------------------------------------------------------
 // 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 246 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_