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
+//   Undetectable < Object
+//   Detectable = Receiver \/ Number \/ Name - Undetectable
 //
 //   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 <= 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.
+// 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 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(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(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,            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 {
 //   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 PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
+  void TypePrint(PrintDimension = BOTH_DIMS);
+  void TypePrint(FILE* out, PrintDimension = 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
@@ skipping 16 matching lines @@
 
   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_