Introduce representation types

src/types.h

Index: src/types.h
diff --git a/src/types.h b/src/types.h
index 48b39335b63dcd5c4da0f468f30afd4efaa409d4..d9dc1e915c691e438361b598a340c62fc600a881 100644
--- a/src/types.h
+++ b/src/types.h
@@ -42,7 +42,10 @@ namespace internal {
 // 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
@@ -54,13 +57,12 @@ namespace internal {
 //   UniqueName = InternalizedString \/ Symbol
 //   InternalizedString < String
 //
-//   Allocated = Receiver \/ Number \/ Name
-//   Detectable = Allocated - Undetectable
-//   Undetectable < Object
 //   Receiver = Object \/ Proxy
 //   Array < Object
 //   Function < Object
 //   RegExp < Object
+//   Undetectable < Object
+//   Detectable = Receiver \/ Number \/ Name - Undetectable
 //
 //   Class(map) < T   iff instance_type(map) < T
 //   Constant(x) < T  iff instance_type(map(x)) < T
@@ -70,65 +72,121 @@ namespace internal {
 // 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 <= Any
+//
+//   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
+//
+// 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')
+//   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 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
 // 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.
-
-
-#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)        \
+// 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 MASK_BITSET_TYPE_LIST(V) \
+  V(Representation, static_cast<int>(0xff800000)) \
+  V(Semantic,       static_cast<int>(0x007fffff))
+
+#define REPRESENTATION(k) ((k) & kRepresentation)
+#define SEMANTIC(k)       ((k) & kSemantic)
+
+#define REPRESENTATION_BITSET_TYPE_LIST(V) \
+  V(None,             0)                   \
+  V(UntaggedInt8,     1 << 23 | kSemantic) \
+  V(UntaggedInt16,    1 << 24 | kSemantic) \
+  V(UntaggedInt32,    1 << 25 | kSemantic) \
+  V(UntaggedFloat32,  1 << 26 | kSemantic) \
+  V(UntaggedFloat64,  1 << 27 | kSemantic) \
+  V(UntaggedPtr,      1 << 28 | kSemantic) \
+  V(TaggedInt,        1 << 29 | kSemantic) \
+  V(TaggedPtr,        -1 << 30 | kSemantic)  /* MSB has to be sign-extended */ \

[Michael Starzinger, 2014/03/04 15:02:25]

I would be fine with this. If either Benedikt or Sven want this to be handled
differently, then I defer to alternative suggestions from their end.

[Sven Panne, 2014/03/05 07:22:36]

As already discussed yesterday, I consider this sign-extension here an extremely
ugly and confusing hack. We just want to stuff something which the GC shouldn't
care about into some kind of JavaScript value (a Smi, but that't purely
accidental here). We do similar things e.g. in the exterrnal API, and I don't
see why something similar to DecodeSmiToAligned/EncodeAlignedAsSmi shouldn't
work with the bit set at hand. As it is, the current CL is mixing unrelated
things together.

[Benedikt Meurer, 2014/03/05 07:28:07]

I agree. We should not introduce hacks like this unless there's absolutely no
way to avoid that.

[rossberg, 2014/03/14 10:37:37]

Michael yesterday (after you had left) expressed very strong disagreement with
your suggestion, and the more I think about the more I agree with him.

There are two ways to implement your suggestion: direct bit fiddling with smi
tags and shift offsets, which is platform dependent and pierces the little
abstraction barrier we have. I hope we can agree that that's a no-go (even
though that's what DecodeSmiToAligned is using, which I consider the real
mistake around here).

Or you extend the Smi class interface to support encoding/decoding unsigneds.
That, however, severely weakens the Smi class, which Michael is strongly opposed
to. In particular, the 'value' method, which currently is the only and always
correct way to extract the value, would cease to have this property. You would
have to start relying on global knowledge to know which projection method to
use, and we have enough of such ambient "invariants" already. So this is also
bad.

The above solution, on the other hand, is entirely local. All it does is solving
a simple isolated problem: how to encode an 31-bit bitfield into an 31-bit
signed integer. This is completely independent of their later injection into
smis and their low-level encoding details (which is all the more relevant since
smis are just one possible backing store for these integers, in zone types it's
a different one). Separation of concerns, pal!

[Michael Starzinger, 2014/03/14 10:49:36]

So just to clarify: My strong disagreement is against having something like
Smi::FromUsigned() or Smi::unsigned_value() because that weakens a Smi to
basically be either a "Smsi" or "Smui" depending on which methods are used. And
I think that is a bad direction to be heading.

I know that we already use trickery to cast to and from Smi (e.g.
EncodeAlignedAsSmi and DecodeSmiToAligned), but at least those methods are not
part of the "Smi API". Performance forces us to use these hacks, so I won't
start arguing against them. But where I draw the line and will start arguing is
at extending the Smi class in a way that invites everyone to use hacks like
these. Such an API would invite accidental misuse (e.g. creating a Smi with
Smi::FromUnsigned, reading back the value with Smi::value).

+  \
+  V(UntaggedInt,      kUntaggedInt8 | kUntaggedInt16 | kUntaggedInt32) \
+  V(UntaggedFloat,    kUntaggedFloat32 | kUntaggedFloat64)             \
+  V(UntaggedNumber,   kUntaggedInt | kUntaggedFloat)                   \
+  V(Untagged,         kUntaggedNumber | kUntaggedPtr)                  \
+  V(Tagged,           kTaggedInt | kTaggedPtr)
+
+#define SEMANTIC_BITSET_TYPE_LIST(V) \
+  V(Null,                1 << 0  | REPRESENTATION(kTaggedPtr)) \
+  V(Undefined,           1 << 1  | REPRESENTATION(kTaggedPtr)) \
+  V(Boolean,             1 << 2  | REPRESENTATION(kTaggedPtr)) \
+  V(SignedSmall,         1 << 3  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(OtherSigned32,       1 << 4  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Unsigned32,          1 << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Float,               1 << 6  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Symbol,              1 << 7  | REPRESENTATION(kTaggedPtr)) \
+  V(InternalizedString,  1 << 8  | REPRESENTATION(kTaggedPtr)) \
+  V(OtherString,         1 << 9  | REPRESENTATION(kTaggedPtr)) \
+  V(Undetectable,        1 << 10 | REPRESENTATION(kTaggedPtr)) \
+  V(Array,               1 << 11 | REPRESENTATION(kTaggedPtr)) \
+  V(Function,            1 << 12 | REPRESENTATION(kTaggedPtr)) \
+  V(RegExp,              1 << 13 | REPRESENTATION(kTaggedPtr)) \
+  V(OtherObject,         1 << 14 | REPRESENTATION(kTaggedPtr)) \
+  V(Proxy,               1 << 15 | REPRESENTATION(kTaggedPtr)) \
+  V(Internal,            1 << 16 | REPRESENTATION(kTagged | kUntagged)) \
   \
-  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(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(DetectableReceiver,  kDetectableObject | kProxy)                    \
+  V(Detectable,          kDetectableReceiver | kNumber | kName)         \
+  V(Object,              kDetectableObject | kUndetectable)             \
+  V(Receiver,            kObject | kProxy)                              \
+  V(NonNumber,           kOddball | kName | kReceiver | kInternal)      \
+  V(Any,                 kNumber | kNonNumber)
+
+#define BITSET_TYPE_LIST(V) \
+  MASK_BITSET_TYPE_LIST(V) \
+  REPRESENTATION_BITSET_TYPE_LIST(V) \
+  SEMANTIC_BITSET_TYPE_LIST(V)
 
 
 // struct Config {
@@ -248,8 +306,9 @@ class TypeImpl : public Config::Base {
       typename OtherTypeImpl::TypeHandle type, Region* region);
 
 #ifdef OBJECT_PRINT
-  void TypePrint();
-  void TypePrint(FILE* out);
+  enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
+  void TypePrint(PrintDimension = BOTH_DIMS);
+  void TypePrint(FILE* out, PrintDimension = BOTH_DIMS);
 #endif
 
  private:
@@ -286,6 +345,10 @@ class TypeImpl : public Config::Base {
 
   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
 
@@ -300,6 +363,7 @@ class TypeImpl : public Config::Base {
 
 #ifdef OBJECT_PRINT
   static const char* bitset_name(int bitset);
+  static void BitsetTypePrint(FILE* out, int bitset);
 #endif
 };