Introduce representation types

src/types.h

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 24 matching lines @@
 namespace v8 {
 namespace internal {
 
 
 // A simple type system for compiler-internal use. It is based entirely on
 // union types, and all subtyping hence amounts to set inclusion. Besides the
 // obvious primitive types and some predefined unions, the type language also
 // can express class types (a.k.a. specific maps) and singleton types (i.e.,
 // concrete constants).
 //
-// The following equations and inequations hold:
+// Types consist of two dimensions: semantic (value range) and representation.
+// Both are related through subtyping.
+//
+// The following equations and inequations hold for the semantic axis:
 //
 //   None <= T
 //   T <= Any
 //
 //   Oddball = Boolean \/ Null \/ Undefined
 //   Number = Signed32 \/ Unsigned32 \/ Double
 //   Smi <= Signed32
 //   Name = String \/ Symbol
 //   UniqueName = InternalizedString \/ Symbol
 //   InternalizedString < String
 //
 //   Allocated = Receiver \/ Number \/ Name
 //   Detectable = Allocated - Undetectable
 //   Undetectable < Object
 //   Receiver = Object \/ Proxy
 //   Array < Object
 //   Function < Object
 //   RegExp < Object
 //
 //   Class(map) < T   iff instance_type(map) < T
 //   Constant(x) < T  iff instance_type(map(x)) < T
 //
 // Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can
 // change! (Its instance type cannot, however.)
 // TODO(rossberg): the latter is not currently true for proxies, because of fix,
 // but will hold once we implement direct proxies.
 //
+// For the representation axis, the following holds:
+//
+//   None <= R
+//   R <= Representation
+//
+//   UntaggedInt <= UntaggedInt8 \/ UntaggedInt16 \/ UntaggedInt32)
+//   UntaggedFloat <= UntaggedFloat32 \/ UntaggedFloat64
+//   UntaggedNumber <= UntaggedInt \/ UntaggedFloat
+//   Untagged <= UntaggedNumber \/ UntaggedPtr
+//   Tagged <= TaggedInt \/ TaggedPtr
+//
+// Subtyping relates the two dimensions, for example:
+//
+//   Number <= Tagged \/ UntaggedNumber
+//   Object <= TaggedPtr \/ UntaggedPtr
+//
+// Representations can be narrowed for a given semantic type using intersection:
+//
+//   SignedSmall /\ TaggedInt       (a 'smi')
+//   Number /\ TaggedPtr            (a heap number)
+//
 // 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(Integer31())), and the to check whether a specific case needs handling
-// (e.g., via T->Maybe(Number())).
+// T->Is(SignedSmall())), and the to check whether a specific case needs

[Michael Starzinger, 2014/03/04 11:59:58]

nit: Seems to be a "latter" missing.

[rossberg, 2014/03/04 13:53:11]

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 use pointer equality for type tests, always use Is!
 //
 // Internally, all 'primitive' types, and their unions, are represented as
-// bitsets via smis. Class is a heap pointer to the respective map. Only
-// Constant's, or unions containing Class'es or Constant's, require allocation.
+// bitsets. Class is a heap pointer to the respective map. Only Constant's, or
+// unions containing Class'es or Constant's, currently require allocation.
 // Note that the bitset representation is closed under both Union and Intersect.
 //
-// The type representation is heap-allocated, so cannot (currently) be used in
-// a concurrent compilation context.
+// There are two type representations, using different allocation:
+//
+// - 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.
 
 
-#define BITSET_TYPE_LIST(V)              \
-  V(None,                0)              \
-  V(Null,                1 << 0)         \
-  V(Undefined,           1 << 1)         \
-  V(Boolean,             1 << 2)         \
-  V(Smi,                 1 << 3)         \
-  V(OtherSigned32,       1 << 4)         \
-  V(Unsigned32,          1 << 5)         \
-  V(Double,              1 << 6)         \
-  V(Symbol,              1 << 7)         \
-  V(InternalizedString,  1 << 8)         \
-  V(OtherString,         1 << 9)         \
-  V(Undetectable,        1 << 10)        \
-  V(Array,               1 << 11)        \
-  V(Function,            1 << 12)        \
-  V(RegExp,              1 << 13)        \
-  V(OtherObject,         1 << 14)        \
-  V(Proxy,               1 << 15)        \
-  V(Internal,            1 << 16)        \
+#define RAW_REPRESENTATION_BITSET_TYPE_LIST(V)  /* internal */ \
+  V(RUntaggedInt8,     1 << 29) \
+  V(RUntaggedInt16,    1 << 28) \
+  V(RUntaggedInt32,    1 << 27) \
+  V(RUntaggedFloat32,  1 << 26) \
+  V(RUntaggedFloat64,  1 << 25) \
+  V(RUntaggedPtr,      1 << 24) \
+  V(RTaggedInt,        1 << 23) \
+  V(RTaggedPtr,        1 << 22) \
   \
-  V(Oddball,         kBoolean | kNull | kUndefined)                 \
-  V(Signed32,        kSmi | kOtherSigned32)                         \
-  V(Number,          kSigned32 | kUnsigned32 | kDouble)             \
-  V(String,          kInternalizedString | kOtherString)            \
-  V(UniqueName,      kSymbol | kInternalizedString)                 \
-  V(Name,            kSymbol | kString)                             \
-  V(NumberOrString,  kNumber | kString)                             \
-  V(Object,          kUndetectable | kArray | kFunction |           \
-                     kRegExp | kOtherObject)                        \
-  V(Receiver,        kObject | kProxy)                              \
-  V(Allocated,       kDouble | kName | kReceiver)                   \
-  V(Any,             kOddball | kNumber | kAllocated | kInternal)   \
-  V(NonNumber,       kAny - kNumber)                                \
-  V(Detectable,      kAllocated - kUndetectable)
+  V(RUntaggedInt,      kRUntaggedInt8 | kRUntaggedInt16 | kRUntaggedInt32) \
+  V(RUntaggedFloat,    kRUntaggedFloat32 | kRUntaggedFloat64)              \
+  V(RUntaggedNumber,   kRUntaggedInt | kRUntaggedFloat)                    \
+  V(RUntagged,         kRUntaggedNumber | kRUntaggedPtr)                   \
+  V(RTagged,           kRTaggedInt | kRTaggedPtr)
+
+#define SEMANTIC_BITSET_TYPE_LIST(V) \
+  V(None,                0)          \
+  V(Null,                1 << 0  | kRTaggedPtr | kRUntaggedPtr) \
+  V(Undefined,           1 << 1  | kRTaggedPtr | kRUntaggedPtr) \
+  V(Boolean,             1 << 2  | kRTaggedPtr | kRUntaggedPtr) \
+  V(SignedSmall,         1 << 3  | kRTagged | kRUntaggedNumber) \
+  V(OtherSigned32,       1 << 4  | kRTagged | kRUntaggedNumber) \
+  V(Unsigned32,          1 << 5  | kRTagged | kRUntaggedNumber) \
+  V(Float,               1 << 6  | kRTagged | kRUntaggedNumber) \
+  V(Symbol,              1 << 7  | kRTaggedPtr | kRUntaggedPtr) \
+  V(InternalizedString,  1 << 8  | kRTaggedPtr | kRUntaggedPtr) \
+  V(OtherString,         1 << 9  | kRTaggedPtr | kRUntaggedPtr) \
+  V(Undetectable,        1 << 10 | kRTaggedPtr | kRUntaggedPtr) \
+  V(Array,               1 << 11 | kRTaggedPtr | kRUntaggedPtr) \
+  V(Function,            1 << 12 | kRTaggedPtr | kRUntaggedPtr) \
+  V(RegExp,              1 << 13 | kRTaggedPtr | kRUntaggedPtr) \
+  V(OtherObject,         1 << 14 | kRTaggedPtr | kRUntaggedPtr) \
+  V(Proxy,               1 << 15 | kRTaggedPtr | kRUntaggedPtr) \
+  V(Internal,            1 << 16 | kRTagged | kRUntagged) \
+  \
+  V(Oddball,             kBoolean | kNull | kUndefined)                 \
+  V(Signed32,            kSignedSmall | kOtherSigned32)                 \
+  V(Number,              kSigned32 | kUnsigned32 | kFloat)              \
+  V(String,              kInternalizedString | kOtherString)            \
+  V(UniqueName,          kSymbol | kInternalizedString)                 \
+  V(Name,                kSymbol | kString)                             \
+  V(NumberOrString,      kNumber | kString)                             \
+  V(DetectableObject,    kArray | kFunction | kRegExp | kOtherObject)   \
+  V(Object,              kDetectableObject | kUndetectable)             \
+  V(Receiver,            kObject | kProxy)                              \
+  V(Allocated,           kReceiver | kFloat | kName)                    \

[Michael Starzinger, 2014/03/04 11:59:58]

Why kFloat here?

[rossberg, 2014/03/04 13:53:11]

Good question. I removed this thing entirely, since it should now be subsumed by
proper representation types. 

+  V(DetectableReceiver,  kDetectableObject | kProxy)                    \
+  V(Detectable,          kDetectableReceiver | kFloat | kName)          \

[Michael Starzinger, 2014/03/04 11:59:58]

Why kFloat here?

[rossberg, 2014/03/04 13:53:11]

Changed to Number.

+  V(NonNumber,           kOddball | kAllocated | kInternal)             \

[Michael Starzinger, 2014/03/04 11:59:58]

This way kNonNumber contains kFloat, this seems wrong.

[rossberg, 2014/03/04 13:53:11]

Done.

+  V(Any,                 kNumber | kNonNumber)
+
+#define MASK_BITSET_TYPE_LIST(V) \
+  V(Representation, kRTagged | kRUntagged) \
+  V(Semantic,       kAny & ~kRepresentation)
+
+#define REPRESENTATION_BITSET_TYPE_LIST(V) \
+  V(UntaggedInt8,    kSemantic | kRUntaggedInt8)    \
+  V(UntaggedInt16,   kSemantic | kRUntaggedInt16)   \
+  V(UntaggedInt32,   kSemantic | kRUntaggedInt32)   \
+  V(UntaggedFloat32, kSemantic | kRUntaggedFloat32) \
+  V(UntaggedFloat64, kSemantic | kRUntaggedFloat64) \
+  V(UntaggedPtr,     kSemantic | kRUntaggedPtr)     \
+  V(TaggedInt,       kSemantic | kRTaggedInt)       \
+  V(TaggedPtr,       kSemantic | kRTaggedPtr)       \
+  \
+  V(UntaggedInt,     kSemantic | kRUntaggedInt)     \
+  V(UntaggedFloat,   kSemantic | kRUntaggedFloat)   \
+  V(UntaggedNumber,  kSemantic | kRUntaggedNumber)  \
+  V(Untagged,        kSemantic | kRUntagged)        \
+  V(Tagged,          kSemantic | kRTagged)
+
+#define BITSET_TYPE_LIST(V) \
+  SEMANTIC_BITSET_TYPE_LIST(V) \
+  MASK_BITSET_TYPE_LIST(V) \
+  REPRESENTATION_BITSET_TYPE_LIST(V)
 
 
 // struct Config {
 //   typedef Base;
 //   typedef Unioned;
 //   typedef Region;
 //   template<class> struct Handle { typedef type; }  // No template typedefs...
 //   static Handle<Type>::type handle(Type* type);    // !is_bitset(type)
 //   static bool is_bitset(Type*);
 //   static bool is_class(Type*);
@@ skipping 99 matching lines @@
     TypeImpl* t = static_cast<TypeImpl*>(object);
     ASSERT(t->IsBitset() || t->IsClass() || t->IsConstant() || t->IsUnion());
     return t;
   }
 
   template<class OtherTypeImpl>
   static TypeHandle Convert(
       typename OtherTypeImpl::TypeHandle type, Region* region);
 
 #ifdef OBJECT_PRINT
-  void TypePrint();
-  void TypePrint(FILE* out);
+  enum PrintDim { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };

[Michael Starzinger, 2014/03/04 11:59:58]

nit: Can we write out "PrintDimension" at least for the name of the enum type
(not the enum values)?

[rossberg, 2014/03/04 13:53:11]

Done.

+  void TypePrint(PrintDim = BOTH_DIMS);
+  void TypePrint(FILE* out, PrintDim = BOTH_DIMS);
 #endif
 
  private:
   template<class> friend class Iterator;
   template<class> friend class TypeImpl;
 
   // A union is a fixed array containing types. Invariants:
   // - its length is at least 2
   // - at most one field is a bitset, and it must go into index 0
   // - no field is a union
   typedef typename Config::Unioned Unioned;
   typedef typename Config::template Handle<Unioned>::type UnionedHandle;
 
   enum {
     #define DECLARE_TYPE(type, value) k##type = (value),
+    RAW_REPRESENTATION_BITSET_TYPE_LIST(DECLARE_TYPE)
     BITSET_TYPE_LIST(DECLARE_TYPE)
     #undef DECLARE_TYPE
     kUnusedEOL = 0
   };
 
   bool IsNone() { return this == None(); }
   bool IsAny() { return this == Any(); }
   bool IsBitset() { return Config::is_bitset(this); }
   bool IsUnion() { return Config::is_union(this); }
   int AsBitset() { return Config::as_bitset(this); }
   UnionedHandle AsUnion() { return Config::as_union(this); }
 
   static int UnionLength(UnionedHandle unioned) {
     return Config::union_length(unioned);
   }
   static TypeHandle UnionGet(UnionedHandle unioned, int i) {
     return Config::union_get(unioned, i);
   }
 
   bool SlowIs(TypeImpl* that);
 
+  static bool IsInhabited(int bitset) {
+    return (bitset & kRepresentation) && (bitset & kSemantic);
+  }
+
   int LubBitset();  // least upper bound that's a bitset
   int GlbBitset();  // greatest lower bound that's a bitset
 
   static int LubBitset(i::Object* value);
   static int LubBitset(i::Map* map);
 
   bool InUnion(UnionedHandle unioned, int current_size);
   static int ExtendUnion(
       UnionedHandle unioned, TypeHandle t, int current_size);
   static int ExtendIntersection(
       UnionedHandle unioned, TypeHandle t, TypeHandle other, int current_size);
 
 #ifdef OBJECT_PRINT
   static const char* bitset_name(int bitset);
+  static void BitsetTypePrint(FILE* out, int bitset);
 #endif
 };
 
 
 // Zone-allocated types are either (odd) integers to represent bitsets, or
 // (even) pointers to zone lists for everything else. The first slot of every
 // list is an explicit tag value to distinguish representation.
 struct ZoneTypeConfig {
  private:
   typedef i::ZoneList<void*> Tagged;
@@ skipping 252 matching lines @@
     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
   }
 };
 
 typedef BoundsImpl<ZoneTypeConfig> Bounds;
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TYPES_H_