Redesign of the internal type system.

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"
 #include "src/ostreams.h"
 
 namespace v8 {
 namespace internal {
 
 // SUMMARY
 //
 // A simple type system for compiler-internal use. It is based entirely on
@@ skipping 87 matching lines @@
 // 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
 // guarding!
 //
 // PROPERTIES
 //
 // Various formal properties hold for constructors, operators, and predicates
-// over types. For example, constructors are injective, subtyping is a complete
-// partial order, union and intersection satisfy the usual algebraic properties.
+// over types. For example, constructors are injective and subtyping is a
+// complete partial order.
 //
 // See test/cctest/test-types.cc for a comprehensive executable specification,
 // especially with respect to the properties of the more exotic 'temporal'
 // constructors and predicates (those prefixed 'Now').
 //
 // IMPLEMENTATION
 //
 // Internally, all 'primitive' types, and their unions, are represented as
 // bitsets. Class is a heap pointer to the respective map. Only Constant's, or
 // unions containing Class'es or Constant's, currently require allocation.
@@ skipping 74 matching lines @@
   V(Primitive,           kNumber | kName | kBoolean | kNull | kUndefined) \
   V(DetectableObject,    kArray | kFunction | kRegExp | kOtherObject) \
   V(DetectableReceiver,  kDetectableObject | kProxy) \
   V(Detectable,          kDetectableReceiver | kNumber | kName) \
   V(Object,              kDetectableObject | kUndetectable) \
   V(Receiver,            kObject | kProxy) \
   V(NonNumber,           kBoolean | kName | kNull | kReceiver | \
                          kUndefined | kInternal) \
   V(Any,                 -1)
 
+/*
+ * 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
+ * ______[_______[_______[_______[_______[_______[_______
+ *     -2^31   -2^30     0      2^30    2^31    2^32
+ *
+  * Otherwise:

[rossberg, 2014/09/10 15:44:15]

Nit: indentation off

[neis1, 2014/09/11 12:58:12]

Done.

+ *
+ *   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.
+ *
+ */
+
+#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) \
-  SEMANTIC_BITSET_TYPE_LIST(V)
+  PROPER_BITSET_TYPE_LIST(V)
 
 
 // -----------------------------------------------------------------------------
 // The abstract Type class, parameterized over the low-level representation.
 
 // struct Config {
 //   typedef TypeImpl<Config> Type;
 //   typedef Base;
 //   typedef Struct;
 //   typedef Region;
@@ skipping 47 matching lines @@
   typedef typename Config::template Handle<UnionType>::type UnionHandle;
   typedef typename Config::Region Region;
 
   // Constructors.
 
   #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);                    \
     }
-  BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
+  PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
   #undef DEFINE_TYPE_CONSTRUCTOR
 
   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) {
-    // TODO(neis): Return RangeType for numerical values.
     return ConstantType::New(value, region);
   }
-  static TypeHandle Range(double min, double max, Region* region) {
+  static TypeHandle Range(
+      i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
     return RangeType::New(min, max, 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) {
@@ skipping 47 matching lines @@
   bool Is(TypeHandle that) { return this->Is(*that); }
 
   bool Maybe(TypeImpl* that);
   template<class TypeHandle>
   bool Maybe(TypeHandle that) { return this->Maybe(*that); }
 
   bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); }
   template<class TypeHandle>
   bool Equals(TypeHandle that) { return this->Equals(*that); }
 
-  // Equivalent to Constant(value)->Is(this), but avoiding allocation.
+  // Equivalent to Constant(val)->Is(this), but avoiding allocation.
   bool Contains(i::Object* val);
   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); }
 
   // State-dependent versions of the above that consider subtyping between
   // a constant and its map class.
   inline static TypeHandle NowOf(i::Object* value, Region* region);
   static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) {
     return NowOf(*value, region);
   }
   bool NowIs(TypeImpl* that);
@@ skipping 88 matching lines @@
   int AsBitset() {
     DCHECK(this->IsBitset());
     return static_cast<BitsetType*>(this)->Bitset();
   }
   UnionType* AsUnion() { return UnionType::cast(this); }
 
   // Auxiliary functions.
 
   int BitsetGlb() { return BitsetType::Glb(this); }
   int BitsetLub() { return BitsetType::Lub(this); }
-  int InherentBitsetLub() { return BitsetType::InherentLub(this); }
 
   bool SlowIs(TypeImpl* that);
 
-  TypeHandle Rebound(int bitset, Region* region);
-  int BoundBy(TypeImpl* that);
-  int IndexInUnion(int bound, UnionHandle unioned, int current_size);
-  static int ExtendUnion(
-      UnionHandle unioned, int current_size, TypeHandle t,
-      TypeHandle other, bool is_intersect, Region* region);
+  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->MinV()), max(range->MaxV()) {}
+  };
+
+  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, i::Object* val);
+
+  RangeType* GetRange();
+  static int UpdateRange(
+      RangeHandle type, UnionHandle result, int size, Region* region);
+
+  bool SimplyEquals(TypeImpl* 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 TypeHandle NormalizeUnion(UnionHandle unioned, int size);
 };
 
 
 // -----------------------------------------------------------------------------
 // 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
   };
 
   int Bitset() { return Config::as_bitset(this); }
 
   static TypeImpl* New(int bitset) {
+    DCHECK(bitset == kNone || IsInhabited(bitset));
     return static_cast<BitsetType*>(Config::from_bitset(bitset));
   }
   static TypeHandle New(int bitset, Region* region) {
+    DCHECK(bitset == kNone || IsInhabited(bitset));
     return Config::from_bitset(bitset, region);
   }
 
   static bool IsInhabited(int bitset) {
     return (bitset & kRepresentation) && (bitset & kSemantic);
   }
 
   static bool Is(int bitset1, int bitset2) {
     return (bitset1 | bitset2) == bitset2;
   }
 
   static int Glb(TypeImpl* type);  // greatest lower bound that's a bitset
   static int Lub(TypeImpl* type);  // least upper bound that's a bitset
   static int Lub(i::Object* value);
   static int Lub(double value);
   static int Lub(int32_t value);
   static int Lub(uint32_t value);
   static int Lub(i::Map* map);
-  static int Lub(double min, double max);
-  static int InherentLub(TypeImpl* type);
+  static int Lub(Limits lim);
+  static double Min(int bitset);
 
   static const char* Name(int bitset);
   static void Print(OStream& os, int bitset);  // NOLINT
-  using TypeImpl::PrintTo;
+#ifdef DEBUG
+  static void Print(int bitset);
+#endif
 };
 
 
 // -----------------------------------------------------------------------------
 // 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 65 matching lines @@
   bool Wellformed();
 };
 
 
 // -----------------------------------------------------------------------------
 // Class types.
 
 template<class Config>
 class TypeImpl<Config>::ClassType : public StructuralType {
  public:
-  TypeHandle Bound(Region* region) {
-    return Config::is_class(this)
-        ? BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region)
-        : this->Get(0);
-  }
   i::Handle<i::Map> Map() {
     return Config::is_class(this)
         ? Config::as_class(this)
-        : this->template GetValue<i::Map>(1);
-  }
-
-  static ClassHandle New(
-      i::Handle<i::Map> map, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*map)));
-    ClassHandle type = Config::template cast<ClassType>(
-        StructuralType::New(StructuralType::kClassTag, 2, region));
-    type->Set(0, bound);
-    type->SetValue(1, map);
-    return type;
+        : this->template GetValue<i::Map>(0);
   }
 
   static ClassHandle New(i::Handle<i::Map> map, Region* region) {
     ClassHandle type =
         Config::template cast<ClassType>(Config::from_class(map, region));
-    if (type->IsClass()) {
-      return type;
-    } else {
-      TypeHandle bound = BitsetType::New(BitsetType::Lub(*map), region);
-      return New(map, bound, region);
+    if (!type->IsClass()) {
+      type = Config::template cast<ClassType>(
+        StructuralType::New(StructuralType::kClassTag, 1, region));

[rossberg, 2014/09/10 15:44:15]

Nit: style guide wants +4 indentation for line continuations.

[neis1, 2014/09/11 12:58:12]

Done.

+      type->SetValue(0, map);
     }
+    return type;
   }
 
   static ClassType* cast(TypeImpl* type) {
     DCHECK(type->IsClass());
     return static_cast<ClassType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
 // Constant types.
 
 template<class Config>
 class TypeImpl<Config>::ConstantType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); }
+  i::Handle<i::Object> Value() {
+    return this->template GetValue<i::Object>(0);

[rossberg, 2014/09/10 15:44:15]

Nit: probably fits on previous line

[neis1, 2014/09/11 12:58:12]

Done.

+  }
 
-  static ConstantHandle New(
-      i::Handle<i::Object> value, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*value)));
+  static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
     ConstantHandle type = Config::template cast<ConstantType>(
-        StructuralType::New(StructuralType::kConstantTag, 2, region));
-    type->Set(0, bound);
-    type->SetValue(1, value);
+        StructuralType::New(StructuralType::kConstantTag, 1, region));
+    type->SetValue(0, value);
     return type;
   }
 
-  static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::Lub(*value), region);
-    return New(value, bound, region);
-  }
-
   static ConstantType* cast(TypeImpl* type) {
     DCHECK(type->IsConstant());
     return static_cast<ConstantType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
 // Range types.
+// They represent continuous integer intervals in the form of a minimum

[rossberg, 2014/09/10 15:44:15]

This should go to the top, along with the other explanations of the type system.

[neis1, 2014/09/11 12:58:12]

Done.

+// and a 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.
 
 template<class Config>
 class TypeImpl<Config>::RangeType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  double Min() { return this->template GetValue<i::HeapNumber>(1)->value(); }
-  double Max() { return this->template GetValue<i::HeapNumber>(2)->value(); }
+  i::Handle<i::Object> MinV() { return this->template GetValue<i::Object>(0); }
+  i::Handle<i::Object> MaxV() { return this->template GetValue<i::Object>(1); }
+  double Min() { return MinV()->Number(); }
+  double Max() { return MaxV()->Number(); }

[rossberg, 2014/09/10 15:44:15]

Since we call the method to get a numeric value from an object 'Value' in other
places, I think it would be more consistent to name these 4 methods Min, Max,
MinValue, MaxValue.

[neis1, 2014/09/11 12:58:12]

Not sure I'm following.  Are you suggesting to expand the V to Value (fine with
me), or to rename Max to MaxValue and MaxV to Max (not so fine with me).

[rossberg, 2014/09/15 15:58:29]

The latter. It's more consistent with our naming elsewhere.

[neis1, 2014/09/16 10:03:59]

But less consistent with the naming here, such as StructuralType::GetValue,
StructuralType::SetValue, Constant::Value, where Value means an Ojbect pointer.

[rossberg, 2014/09/16 14:04:40]

OK, fair enough. Actually, I'd say, just remove the 'double' wrappers from the
interface, and rename the other two to Min and Max.

[neis1, 2014/09/18 13:05:18]

Done.

 
   static RangeHandle New(
-      double min, double max, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(min, max)));
+      i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) {
+    DCHECK(min->Number() <= max->Number());
     RangeHandle type = Config::template cast<RangeType>(
-        StructuralType::New(StructuralType::kRangeTag, 3, region));
-    type->Set(0, bound);
-    Factory* factory = Config::isolate(region)->factory();
-    Handle<HeapNumber> minV = factory->NewHeapNumber(min);
-    Handle<HeapNumber> maxV = factory->NewHeapNumber(max);
-    type->SetValue(1, minV);
-    type->SetValue(2, maxV);
+        StructuralType::New(StructuralType::kRangeTag, 2, region));
+    type->SetValue(0, min);
+    type->SetValue(1, max);
+#ifdef DEBUG

[rossberg, 2014/09/10 15:44:15]

Debugging left-overs?

[neis1, 2014/09/11 12:58:12]

Done.

+    type->Print();
+#endif
     return type;
   }
 
-  static RangeHandle New(double min, double max, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::Lub(min, max), region);
-    return New(min, max, bound, region);
+  static RangeHandle New(Limits lim, Region* region) {
+    return New(lim.min, lim.max, region);
   }
 
   static RangeType* cast(TypeImpl* type) {
     DCHECK(type->IsRange());
     return static_cast<RangeType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
 // Context types.
 
 template<class Config>
 class TypeImpl<Config>::ContextType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Outer() { return this->Get(1); }
-
-  static ContextHandle New(TypeHandle outer, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(
-        bound->AsBitset(), BitsetType::kInternal & BitsetType::kTaggedPtr));
-    ContextHandle type = Config::template cast<ContextType>(
-        StructuralType::New(StructuralType::kContextTag, 2, region));
-    type->Set(0, bound);
-    type->Set(1, outer);
-    return type;
-  }
+  TypeHandle Outer() { return this->Get(0); }
 
   static ContextHandle New(TypeHandle outer, Region* region) {
-    TypeHandle bound = BitsetType::New(
-        BitsetType::kInternal & BitsetType::kTaggedPtr, region);
-    return New(outer, bound, region);
+    ContextHandle type = Config::template cast<ContextType>(
+        StructuralType::New(StructuralType::kContextTag, 1, region));
+    type->Set(0, outer);
+    return type;
   }
 
   static ContextType* cast(TypeImpl* type) {
     DCHECK(type->IsContext());
     return static_cast<ContextType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
 // Array types.
 
 template<class Config>
 class TypeImpl<Config>::ArrayType : public StructuralType {
  public:
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Element() { return this->Get(1); }
-
-  static ArrayHandle New(TypeHandle element, TypeHandle bound, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kArray));
-    ArrayHandle type = Config::template cast<ArrayType>(
-        StructuralType::New(StructuralType::kArrayTag, 2, region));
-    type->Set(0, bound);
-    type->Set(1, element);
-    return type;
-  }
+  TypeHandle Element() { return this->Get(0); }
 
   static ArrayHandle New(TypeHandle element, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::kArray, region);
-    return New(element, bound, region);
+    ArrayHandle type = Config::template cast<ArrayType>(
+        StructuralType::New(StructuralType::kArrayTag, 1, region));
+    type->Set(0, element);
+    return type;
   }
 
   static ArrayType* cast(TypeImpl* type) {
     DCHECK(type->IsArray());
     return static_cast<ArrayType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
 // Function types.
 
 template<class Config>
 class TypeImpl<Config>::FunctionType : public StructuralType {
  public:
-  int Arity() { return this->Length() - 3; }
-  TypeHandle Bound() { return this->Get(0); }
-  TypeHandle Result() { return this->Get(1); }
-  TypeHandle Receiver() { return this->Get(2); }
-  TypeHandle Parameter(int i) { return this->Get(3 + i); }
+  int Arity() { return this->Length() - 2; }
+  TypeHandle Result() { return this->Get(0); }
+  TypeHandle Receiver() { return this->Get(1); }
+  TypeHandle Parameter(int i) { return this->Get(2 + i); }
 
-  void InitParameter(int i, TypeHandle type) { this->Set(3 + i, type); }
-
-  static FunctionHandle New(
-      TypeHandle result, TypeHandle receiver, TypeHandle bound,
-      int arity, Region* region) {
-    DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kFunction));
-    FunctionHandle type = Config::template cast<FunctionType>(
-        StructuralType::New(StructuralType::kFunctionTag, 3 + arity, region));
-    type->Set(0, bound);
-    type->Set(1, result);
-    type->Set(2, receiver);
-    return type;
-  }
+  void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); }
 
   static FunctionHandle New(
       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
-    TypeHandle bound = BitsetType::New(BitsetType::kFunction, region);
-    return New(result, receiver, bound, arity, region);
+    FunctionHandle type = Config::template cast<FunctionType>(
+        StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region));
+    type->Set(0, result);
+    type->Set(1, receiver);
+    return type;
   }
 
   static FunctionType* cast(TypeImpl* type) {
     DCHECK(type->IsFunction());
     return static_cast<FunctionType*>(type);
   }
 };
 
 
 // -----------------------------------------------------------------------------
@@ skipping 26 matching lines @@
 // Zone-allocated types; they are either (odd) integers to represent bitsets, or
 // (even) pointers to structures for everything else.
 
 struct ZoneTypeConfig {
   typedef TypeImpl<ZoneTypeConfig> Type;
   class Base {};
   typedef void* Struct;
   typedef i::Zone Region;
   template<class T> struct Handle { typedef T* type; };
 
-  // TODO(neis): This will be removed again once we have struct_get_double().
-  static inline i::Isolate* isolate(Region* region) {
-    return region->isolate();
-  }
-
   template<class T> static inline T* handle(T* type);
   template<class T> static inline T* cast(Type* type);
 
   static inline bool is_bitset(Type* type);
   static inline bool is_class(Type* type);
   static inline bool is_struct(Type* type, int tag);
 
   static inline int as_bitset(Type* type);
   static inline i::Handle<i::Map> as_class(Type* type);
   static inline Struct* as_struct(Type* type);
@@ skipping 22 matching lines @@
 // Heap-allocated types; either smis for bitsets, maps for classes, boxes for
 // constants, or fixed arrays for unions.
 
 struct HeapTypeConfig {
   typedef TypeImpl<HeapTypeConfig> Type;
   typedef i::Object Base;
   typedef i::FixedArray Struct;
   typedef i::Isolate Region;
   template<class T> struct Handle { typedef i::Handle<T> type; };
 
-  // TODO(neis): This will be removed again once we have struct_get_double().
-  static inline i::Isolate* isolate(Region* region) {
-    return region;
-  }
-
   template<class T> static inline i::Handle<T> handle(T* type);
   template<class T> static inline i::Handle<T> cast(i::Handle<Type> type);
 
   static inline bool is_bitset(Type* type);
   static inline bool is_class(Type* type);
   static inline bool is_struct(Type* type, int tag);
 
   static inline int as_bitset(Type* type);
   static inline i::Handle<i::Map> as_class(Type* type);
   static inline i::Handle<Struct> as_struct(Type* type);
@@ skipping 77 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_