src/v8/src/types.h

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_TYPES_H_
   6 #define V8_TYPES_H_
   7
   8 #include "src/factory.h"
   9 #include "src/handles.h"
  10 #include "src/ostreams.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14
  15 // SUMMARY
  16 //
  17 // A simple type system for compiler-internal use. It is based entirely on
  18 // union types, and all subtyping hence amounts to set inclusion. Besides the
  19 // obvious primitive types and some predefined unions, the type language also
  20 // can express class types (a.k.a. specific maps) and singleton types (i.e.,
  21 // concrete constants).
  22 //
  23 // Types consist of two dimensions: semantic (value range) and representation.
  24 // Both are related through subtyping.
  25 //
  26 // SEMANTIC DIMENSION
  27 //
  28 // The following equations and inequations hold for the semantic axis:
  29 //
  30 //   None <= T
  31 //   T <= Any
  32 //
  33 //   Number = Signed32 \/ Unsigned32 \/ Double
  34 //   Smi <= Signed32
  35 //   Name = String \/ Symbol
  36 //   UniqueName = InternalizedString \/ Symbol
  37 //   InternalizedString < String
  38 //
  39 //   Receiver = Object \/ Proxy
  40 //   Array < Object
  41 //   Function < Object
  42 //   RegExp < Object
  43 //   Undetectable < Object
  44 //   Detectable = Receiver \/ Number \/ Name - Undetectable
  45 //
  46 //   Class(map) < T   iff instance_type(map) < T
  47 //   Constant(x) < T  iff instance_type(map(x)) < T
  48 //   Array(T) < Array
  49 //   Function(R, S, T0, T1, ...) < Function
  50 //   Context(T) < Internal
  51 //
  52 // Both structural Array and Function types are invariant in all parameters;
  53 // relaxing this would make Union and Intersect operations more involved.
  54 // There is no subtyping relation between Array, Function, or Context types
  55 // and respective Constant types, since these types cannot be reconstructed
  56 // for arbitrary heap values.
  57 // Note also that Constant(x) < Class(map(x)) does _not_ hold, since x's map can
  58 // change! (Its instance type cannot, however.)
  59 // TODO(rossberg): the latter is not currently true for proxies, because of fix,
  60 // but will hold once we implement direct proxies.
  61 // However, we also define a 'temporal' variant of the subtyping relation that
  62 // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)).
  63 //
  64 // REPRESENTATIONAL DIMENSION
  65 //
  66 // For the representation axis, the following holds:
  67 //
  68 //   None <= R
  69 //   R <= Any
  70 //
  71 //   UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/
  72 //                 UntaggedInt16 \/ UntaggedInt32
  73 //   UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64
  74 //   UntaggedNumber = UntaggedInt \/ UntaggedFloat
  75 //   Untagged = UntaggedNumber \/ UntaggedPtr
  76 //   Tagged = TaggedInt \/ TaggedPtr
  77 //
  78 // Subtyping relates the two dimensions, for example:
  79 //
  80 //   Number <= Tagged \/ UntaggedNumber
  81 //   Object <= TaggedPtr \/ UntaggedPtr
  82 //
  83 // That holds because the semantic type constructors defined by the API create
  84 // types that allow for all possible representations, and dually, the ones for
  85 // representation types initially include all semantic ranges. Representations
  86 // can then e.g. be narrowed for a given semantic type using intersection:
  87 //
  88 //   SignedSmall /\ TaggedInt       (a 'smi')
  89 //   Number /\ TaggedPtr            (a heap number)
  90 //
  91 // PREDICATES
  92 //
  93 // There are two main functions for testing types:
  94 //
  95 //   T1->Is(T2)     -- tests whether T1 is included in T2 (i.e., T1 <= T2)
  96 //   T1->Maybe(T2)  -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0)
  97 //
  98 // Typically, the former is to be used to select representations (e.g., via
  99 // T->Is(SignedSmall())), and the latter to check whether a specific case needs
 100 // handling (e.g., via T->Maybe(Number())).
 101 //
 102 // There is no functionality to discover whether a type is a leaf in the
 103 // lattice. That is intentional. It should always be possible to refine the
 104 // lattice (e.g., splitting up number types further) without invalidating any
 105 // existing assumptions or tests.
 106 // Consequently, do not normally use Equals for type tests, always use Is!
 107 //
 108 // The NowIs operator implements state-sensitive subtying, as described above.
 109 // Any compilation decision based on such temporary properties requires runtime
 110 // guarding!
 111 //
 112 // PROPERTIES
 113 //
 114 // Various formal properties hold for constructors, operators, and predicates
 115 // over types. For example, constructors are injective, subtyping is a complete
 116 // partial order, union and intersection satisfy the usual algebraic properties.
 117 //
 118 // See test/cctest/test-types.cc for a comprehensive executable specification,
 119 // especially with respect to the properties of the more exotic 'temporal'
 120 // constructors and predicates (those prefixed 'Now').
 121 //
 122 // IMPLEMENTATION
 123 //
 124 // Internally, all 'primitive' types, and their unions, are represented as
 125 // bitsets. Class is a heap pointer to the respective map. Only Constant's, or
 126 // unions containing Class'es or Constant's, currently require allocation.
 127 // Note that the bitset representation is closed under both Union and Intersect.
 128 //
 129 // There are two type representations, using different allocation:
 130 //
 131 // - class Type (zone-allocated, for compiler and concurrent compilation)
 132 // - class HeapType (heap-allocated, for persistent types)
 133 //
 134 // Both provide the same API, and the Convert method can be used to interconvert
 135 // them. For zone types, no query method touches the heap, only constructors do.
 136
 137
 138 // -----------------------------------------------------------------------------
 139 // Values for bitset types
 140
 141 #define MASK_BITSET_TYPE_LIST(V) \
 142   V(Representation, static_cast<int>(0xffc00000)) \
 143   V(Semantic,       static_cast<int>(0x003fffff))
 144
 145 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation)
 146 #define SEMANTIC(k)       ((k) & BitsetType::kSemantic)
 147
 148 #define REPRESENTATION_BITSET_TYPE_LIST(V) \
 149   V(None,             0)                   \
 150   V(UntaggedInt1,     1 << 22 | kSemantic) \
 151   V(UntaggedInt8,     1 << 23 | kSemantic) \
 152   V(UntaggedInt16,    1 << 24 | kSemantic) \
 153   V(UntaggedInt32,    1 << 25 | kSemantic) \
 154   V(UntaggedFloat32,  1 << 26 | kSemantic) \
 155   V(UntaggedFloat64,  1 << 27 | kSemantic) \
 156   V(UntaggedPtr,      1 << 28 | kSemantic) \
 157   V(TaggedInt,        1 << 29 | kSemantic) \
 158   /* MSB has to be sign-extended */        \
 159   V(TaggedPtr,        static_cast<int>(~0u << 30) | kSemantic) \
 160   \
 161   V(UntaggedInt,      kUntaggedInt1 | kUntaggedInt8 |      \
 162                       kUntaggedInt16 | kUntaggedInt32)     \
 163   V(UntaggedFloat,    kUntaggedFloat32 | kUntaggedFloat64) \
 164   V(UntaggedNumber,   kUntaggedInt | kUntaggedFloat)       \
 165   V(Untagged,         kUntaggedNumber | kUntaggedPtr)      \
 166   V(Tagged,           kTaggedInt | kTaggedPtr)
 167
 168 #define SEMANTIC_BITSET_TYPE_LIST(V) \
 169   V(Null,                1 << 0  | REPRESENTATION(kTaggedPtr)) \
 170   V(Undefined,           1 << 1  | REPRESENTATION(kTaggedPtr)) \
 171   V(Boolean,             1 << 2  | REPRESENTATION(kTaggedPtr)) \
 172   V(UnsignedSmall,       1 << 3  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 173   V(OtherSignedSmall,    1 << 4  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 174   V(OtherUnsigned31,     1 << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 175   V(OtherUnsigned32,     1 << 6  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 176   V(OtherSigned32,       1 << 7  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 177   V(MinusZero,           1 << 8  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 178   V(NaN,                 1 << 9  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 179   V(OtherNumber,         1 << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \
 180   V(Symbol,              1 << 11 | REPRESENTATION(kTaggedPtr)) \
 181   V(InternalizedString,  1 << 12 | REPRESENTATION(kTaggedPtr)) \
 182   V(OtherString,         1 << 13 | REPRESENTATION(kTaggedPtr)) \
 183   V(Undetectable,        1 << 14 | REPRESENTATION(kTaggedPtr)) \
 184   V(Array,               1 << 15 | REPRESENTATION(kTaggedPtr)) \
 185   V(Buffer,              1 << 16 | REPRESENTATION(kTaggedPtr)) \
 186   V(Function,            1 << 17 | REPRESENTATION(kTaggedPtr)) \
 187   V(RegExp,              1 << 18 | REPRESENTATION(kTaggedPtr)) \
 188   V(OtherObject,         1 << 19 | REPRESENTATION(kTaggedPtr)) \
 189   V(Proxy,               1 << 20 | REPRESENTATION(kTaggedPtr)) \
 190   V(Internal,            1 << 21 | REPRESENTATION(kTagged | kUntagged)) \
 191   \
 192   V(SignedSmall,         kUnsignedSmall | kOtherSignedSmall) \
 193   V(Signed32,            kSignedSmall | kOtherUnsigned31 | kOtherSigned32) \
 194   V(Unsigned32,          kUnsignedSmall | kOtherUnsigned31 | kOtherUnsigned32) \
 195   V(Integral32,          kSigned32 | kUnsigned32) \
 196   V(Number,              kIntegral32 | kMinusZero | kNaN | kOtherNumber) \
 197   V(String,              kInternalizedString | kOtherString) \
 198   V(UniqueName,          kSymbol | kInternalizedString) \
 199   V(Name,                kSymbol | kString) \
 200   V(NumberOrString,      kNumber | kString) \
 201   V(Primitive,           kNumber | kName | kBoolean | kNull | kUndefined) \
 202   V(DetectableObject,    kArray | kFunction | kRegExp | kOtherObject) \
 203   V(DetectableReceiver,  kDetectableObject | kProxy) \
 204   V(Detectable,          kDetectableReceiver | kNumber | kName) \
 205   V(Object,              kDetectableObject | kUndetectable) \
 206   V(Receiver,            kObject | kProxy) \
 207   V(NonNumber,           kBoolean | kName | kNull | kReceiver | \
 208                          kUndefined | kInternal) \
 209   V(Any,                 -1)
 210
 211 #define BITSET_TYPE_LIST(V) \
 212   MASK_BITSET_TYPE_LIST(V) \
 213   REPRESENTATION_BITSET_TYPE_LIST(V) \
 214   SEMANTIC_BITSET_TYPE_LIST(V)
 215
 216
 217 // -----------------------------------------------------------------------------
 218 // The abstract Type class, parameterized over the low-level representation.
 219
 220 // struct Config {
 221 //   typedef TypeImpl<Config> Type;
 222 //   typedef Base;
 223 //   typedef Struct;
 224 //   typedef Region;
 225 //   template<class> struct Handle { typedef type; }  // No template typedefs...
 226 //   template<class T> static Handle<T>::type handle(T* t);  // !is_bitset(t)
 227 //   template<class T> static Handle<T>::type cast(Handle<Type>::type);
 228 //   static bool is_bitset(Type*);
 229 //   static bool is_class(Type*);
 230 //   static bool is_struct(Type*, int tag);
 231 //   static int as_bitset(Type*);
 232 //   static i::Handle<i::Map> as_class(Type*);
 233 //   static Handle<Struct>::type as_struct(Type*);
 234 //   static Type* from_bitset(int bitset);
 235 //   static Handle<Type>::type from_bitset(int bitset, Region*);
 236 //   static Handle<Type>::type from_class(i::Handle<Map>, Region*);
 237 //   static Handle<Type>::type from_struct(Handle<Struct>::type, int tag);
 238 //   static Handle<Struct>::type struct_create(int tag, int length, Region*);
 239 //   static void struct_shrink(Handle<Struct>::type, int length);
 240 //   static int struct_tag(Handle<Struct>::type);
 241 //   static int struct_length(Handle<Struct>::type);
 242 //   static Handle<Type>::type struct_get(Handle<Struct>::type, int);
 243 //   static void struct_set(Handle<Struct>::type, int, Handle<Type>::type);
 244 //   template<class V>
 245 //   static i::Handle<V> struct_get_value(Handle<Struct>::type, int);
 246 //   template<class V>
 247 //   static void struct_set_value(Handle<Struct>::type, int, i::Handle<V>);
 248 // }
 249 template<class Config>
 250 class TypeImpl : public Config::Base {
 251  public:
 252   // Auxiliary types.
 253
 254   class BitsetType;      // Internal
 255   class StructuralType;  // Internal
 256   class UnionType;       // Internal
 257
 258   class ClassType;
 259   class ConstantType;
 260   class RangeType;
 261   class ContextType;
 262   class ArrayType;
 263   class FunctionType;
 264
 265   typedef typename Config::template Handle<TypeImpl>::type TypeHandle;
 266   typedef typename Config::template Handle<ClassType>::type ClassHandle;
 267   typedef typename Config::template Handle<ConstantType>::type ConstantHandle;
 268   typedef typename Config::template Handle<RangeType>::type RangeHandle;
 269   typedef typename Config::template Handle<ContextType>::type ContextHandle;
 270   typedef typename Config::template Handle<ArrayType>::type ArrayHandle;
 271   typedef typename Config::template Handle<FunctionType>::type FunctionHandle;
 272   typedef typename Config::template Handle<UnionType>::type UnionHandle;
 273   typedef typename Config::Region Region;
 274
 275   // Constructors.
 276
 277   #define DEFINE_TYPE_CONSTRUCTOR(type, value)                                \
 278     static TypeImpl* type() { return BitsetType::New(BitsetType::k##type); }  \
 279     static TypeHandle type(Region* region) {                                  \
 280       return BitsetType::New(BitsetType::k##type, region);                    \
 281     }
 282   BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
 283   #undef DEFINE_TYPE_CONSTRUCTOR
 284
 285   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
 286     return ClassType::New(map, region);
 287   }
 288   static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
 289     // TODO(neis): Return RangeType for numerical values.
 290     return ConstantType::New(value, region);
 291   }
 292   static TypeHandle Range(double min, double max, Region* region) {
 293     return RangeType::New(min, max, region);
 294   }
 295   static TypeHandle Context(TypeHandle outer, Region* region) {
 296     return ContextType::New(outer, region);
 297   }
 298   static TypeHandle Array(TypeHandle element, Region* region) {
 299     return ArrayType::New(element, region);
 300   }
 301   static FunctionHandle Function(
 302       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
 303     return FunctionType::New(result, receiver, arity, region);
 304   }
 305   static TypeHandle Function(TypeHandle result, Region* region) {
 306     return Function(result, Any(region), 0, region);
 307   }
 308   static TypeHandle Function(
 309       TypeHandle result, TypeHandle param0, Region* region) {
 310     FunctionHandle function = Function(result, Any(region), 1, region);
 311     function->InitParameter(0, param0);
 312     return function;
 313   }
 314   static TypeHandle Function(
 315       TypeHandle result, TypeHandle param0, TypeHandle param1, Region* region) {
 316     FunctionHandle function = Function(result, Any(region), 2, region);
 317     function->InitParameter(0, param0);
 318     function->InitParameter(1, param1);
 319     return function;
 320   }
 321   static TypeHandle Function(
 322       TypeHandle result, TypeHandle param0, TypeHandle param1,
 323       TypeHandle param2, Region* region) {
 324     FunctionHandle function = Function(result, Any(region), 3, region);
 325     function->InitParameter(0, param0);
 326     function->InitParameter(1, param1);
 327     function->InitParameter(2, param2);
 328     return function;
 329   }
 330
 331   static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg);
 332   static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg);
 333
 334   static TypeHandle Of(double value, Region* region) {
 335     return Config::from_bitset(BitsetType::Lub(value), region);
 336   }
 337   static TypeHandle Of(i::Object* value, Region* region) {
 338     return Config::from_bitset(BitsetType::Lub(value), region);
 339   }
 340   static TypeHandle Of(i::Handle<i::Object> value, Region* region) {
 341     return Of(*value, region);
 342   }
 343
 344   // Predicates.
 345
 346   bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); }
 347
 348   bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); }
 349   template<class TypeHandle>
 350   bool Is(TypeHandle that) { return this->Is(*that); }
 351
 352   bool Maybe(TypeImpl* that);
 353   template<class TypeHandle>
 354   bool Maybe(TypeHandle that) { return this->Maybe(*that); }
 355
 356   bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); }
 357   template<class TypeHandle>
 358   bool Equals(TypeHandle that) { return this->Equals(*that); }
 359
 360   // Equivalent to Constant(value)->Is(this), but avoiding allocation.
 361   bool Contains(i::Object* val);
 362   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); }
 363
 364   // State-dependent versions of the above that consider subtyping between
 365   // a constant and its map class.
 366   inline static TypeHandle NowOf(i::Object* value, Region* region);
 367   static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) {
 368     return NowOf(*value, region);
 369   }
 370   bool NowIs(TypeImpl* that);
 371   template<class TypeHandle>
 372   bool NowIs(TypeHandle that)  { return this->NowIs(*that); }
 373   inline bool NowContains(i::Object* val);
 374   bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); }
 375
 376   bool NowStable();
 377
 378   // Inspection.
 379
 380   bool IsClass() {
 381     return Config::is_class(this)
 382         || Config::is_struct(this, StructuralType::kClassTag);
 383   }
 384   bool IsConstant() {
 385     return Config::is_struct(this, StructuralType::kConstantTag);
 386   }
 387   bool IsRange() {
 388     return Config::is_struct(this, StructuralType::kRangeTag);
 389   }
 390   bool IsContext() {
 391     return Config::is_struct(this, StructuralType::kContextTag);
 392   }
 393   bool IsArray() {
 394     return Config::is_struct(this, StructuralType::kArrayTag);
 395   }
 396   bool IsFunction() {
 397     return Config::is_struct(this, StructuralType::kFunctionTag);
 398   }
 399
 400   ClassType* AsClass() { return ClassType::cast(this); }
 401   ConstantType* AsConstant() { return ConstantType::cast(this); }
 402   RangeType* AsRange() { return RangeType::cast(this); }
 403   ContextType* AsContext() { return ContextType::cast(this); }
 404   ArrayType* AsArray() { return ArrayType::cast(this); }
 405   FunctionType* AsFunction() { return FunctionType::cast(this); }
 406
 407   int NumClasses();
 408   int NumConstants();
 409
 410   template<class T> class Iterator;
 411   Iterator<i::Map> Classes() {
 412     if (this->IsBitset()) return Iterator<i::Map>();
 413     return Iterator<i::Map>(Config::handle(this));
 414   }
 415   Iterator<i::Object> Constants() {
 416     if (this->IsBitset()) return Iterator<i::Object>();
 417     return Iterator<i::Object>(Config::handle(this));
 418   }
 419
 420   // Casting and conversion.
 421
 422   static inline TypeImpl* cast(typename Config::Base* object);
 423
 424   template<class OtherTypeImpl>
 425   static TypeHandle Convert(
 426       typename OtherTypeImpl::TypeHandle type, Region* region);
 427
 428   // Printing.
 429
 430   enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
 431
 432   void PrintTo(OStream& os, PrintDimension dim = BOTH_DIMS);  // NOLINT
 433
 434 #ifdef DEBUG
 435   void Print();
 436 #endif
 437
 438  protected:
 439   // Friends.
 440
 441   template<class> friend class Iterator;
 442   template<class> friend class TypeImpl;
 443
 444   // Handle conversion.
 445
 446   template<class T>
 447   static typename Config::template Handle<T>::type handle(T* type) {
 448     return Config::handle(type);
 449   }
 450   TypeImpl* unhandle() { return this; }
 451
 452   // Internal inspection.
 453
 454   bool IsNone() { return this == None(); }
 455   bool IsAny() { return this == Any(); }
 456   bool IsBitset() { return Config::is_bitset(this); }
 457   bool IsUnion() { return Config::is_struct(this, StructuralType::kUnionTag); }
 458
 459   int AsBitset() {
 460     DCHECK(this->IsBitset());
 461     return static_cast<BitsetType*>(this)->Bitset();
 462   }
 463   UnionType* AsUnion() { return UnionType::cast(this); }
 464
 465   // Auxiliary functions.
 466
 467   int BitsetGlb() { return BitsetType::Glb(this); }
 468   int BitsetLub() { return BitsetType::Lub(this); }
 469   int InherentBitsetLub() { return BitsetType::InherentLub(this); }
 470
 471   bool SlowIs(TypeImpl* that);
 472
 473   TypeHandle Rebound(int bitset, Region* region);
 474   int BoundBy(TypeImpl* that);
 475   int IndexInUnion(int bound, UnionHandle unioned, int current_size);
 476   static int ExtendUnion(
 477       UnionHandle unioned, int current_size, TypeHandle t,
 478       TypeHandle other, bool is_intersect, Region* region);
 479 };
 480
 481
 482 // -----------------------------------------------------------------------------
 483 // Bitset types (internal).
 484
 485 template<class Config>
 486 class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
 487  protected:
 488   friend class TypeImpl<Config>;
 489
 490   enum {
 491     #define DECLARE_TYPE(type, value) k##type = (value),
 492     BITSET_TYPE_LIST(DECLARE_TYPE)
 493     #undef DECLARE_TYPE
 494     kUnusedEOL = 0
 495   };
 496
 497   int Bitset() { return Config::as_bitset(this); }
 498
 499   static TypeImpl* New(int bitset) {
 500     return static_cast<BitsetType*>(Config::from_bitset(bitset));
 501   }
 502   static TypeHandle New(int bitset, Region* region) {
 503     return Config::from_bitset(bitset, region);
 504   }
 505
 506   static bool IsInhabited(int bitset) {
 507     return (bitset & kRepresentation) && (bitset & kSemantic);
 508   }
 509
 510   static bool Is(int bitset1, int bitset2) {
 511     return (bitset1 | bitset2) == bitset2;
 512   }
 513
 514   static int Glb(TypeImpl* type);  // greatest lower bound that's a bitset
 515   static int Lub(TypeImpl* type);  // least upper bound that's a bitset
 516   static int Lub(i::Object* value);
 517   static int Lub(double value);
 518   static int Lub(int32_t value);
 519   static int Lub(uint32_t value);
 520   static int Lub(i::Map* map);
 521   static int Lub(double min, double max);
 522   static int InherentLub(TypeImpl* type);
 523
 524   static const char* Name(int bitset);
 525   static void Print(OStream& os, int bitset);  // NOLINT
 526   using TypeImpl::PrintTo;
 527 };
 528
 529
 530 // -----------------------------------------------------------------------------
 531 // Superclass for non-bitset types (internal).
 532 // Contains a tag and a variable number of type or value fields.
 533
 534 template<class Config>
 535 class TypeImpl<Config>::StructuralType : public TypeImpl<Config> {
 536  protected:
 537   template<class> friend class TypeImpl;
 538   friend struct ZoneTypeConfig;  // For tags.
 539   friend struct HeapTypeConfig;
 540
 541   enum Tag {
 542     kClassTag,
 543     kConstantTag,
 544     kRangeTag,
 545     kContextTag,
 546     kArrayTag,
 547     kFunctionTag,
 548     kUnionTag
 549   };
 550
 551   int Length() {
 552     return Config::struct_length(Config::as_struct(this));
 553   }
 554   TypeHandle Get(int i) {
 555     DCHECK(0 <= i && i < this->Length());
 556     return Config::struct_get(Config::as_struct(this), i);
 557   }
 558   void Set(int i, TypeHandle type) {
 559     DCHECK(0 <= i && i < this->Length());
 560     Config::struct_set(Config::as_struct(this), i, type);
 561   }
 562   void Shrink(int length) {
 563     DCHECK(2 <= length && length <= this->Length());
 564     Config::struct_shrink(Config::as_struct(this), length);
 565   }
 566   template<class V> i::Handle<V> GetValue(int i) {
 567     DCHECK(0 <= i && i < this->Length());
 568     return Config::template struct_get_value<V>(Config::as_struct(this), i);
 569   }
 570   template<class V> void SetValue(int i, i::Handle<V> x) {
 571     DCHECK(0 <= i && i < this->Length());
 572     Config::struct_set_value(Config::as_struct(this), i, x);
 573   }
 574
 575   static TypeHandle New(Tag tag, int length, Region* region) {
 576     DCHECK(1 <= length);
 577     return Config::from_struct(Config::struct_create(tag, length, region));
 578   }
 579 };
 580
 581
 582 // -----------------------------------------------------------------------------
 583 // Union types (internal).
 584 // A union is a structured type with the following invariants:
 585 // - its length is at least 2
 586 // - at most one field is a bitset, and it must go into index 0
 587 // - no field is a union
 588 // - no field is a subtype of any other field
 589 template<class Config>
 590 class TypeImpl<Config>::UnionType : public StructuralType {
 591  public:
 592   static UnionHandle New(int length, Region* region) {
 593     return Config::template cast<UnionType>(
 594         StructuralType::New(StructuralType::kUnionTag, length, region));
 595   }
 596
 597   static UnionType* cast(TypeImpl* type) {
 598     DCHECK(type->IsUnion());
 599     return static_cast<UnionType*>(type);
 600   }
 601
 602   bool Wellformed();
 603 };
 604
 605
 606 // -----------------------------------------------------------------------------
 607 // Class types.
 608
 609 template<class Config>
 610 class TypeImpl<Config>::ClassType : public StructuralType {
 611  public:
 612   TypeHandle Bound(Region* region) {
 613     return Config::is_class(this)
 614         ? BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region)
 615         : this->Get(0);
 616   }
 617   i::Handle<i::Map> Map() {
 618     return Config::is_class(this)
 619         ? Config::as_class(this)
 620         : this->template GetValue<i::Map>(1);
 621   }
 622
 623   static ClassHandle New(
 624       i::Handle<i::Map> map, TypeHandle bound, Region* region) {
 625     DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*map)));
 626     ClassHandle type = Config::template cast<ClassType>(
 627         StructuralType::New(StructuralType::kClassTag, 2, region));
 628     type->Set(0, bound);
 629     type->SetValue(1, map);
 630     return type;
 631   }
 632
 633   static ClassHandle New(i::Handle<i::Map> map, Region* region) {
 634     ClassHandle type =
 635         Config::template cast<ClassType>(Config::from_class(map, region));
 636     if (type->IsClass()) {
 637       return type;
 638     } else {
 639       TypeHandle bound = BitsetType::New(BitsetType::Lub(*map), region);
 640       return New(map, bound, region);
 641     }
 642   }
 643
 644   static ClassType* cast(TypeImpl* type) {
 645     DCHECK(type->IsClass());
 646     return static_cast<ClassType*>(type);
 647   }
 648 };
 649
 650
 651 // -----------------------------------------------------------------------------
 652 // Constant types.
 653
 654 template<class Config>
 655 class TypeImpl<Config>::ConstantType : public StructuralType {
 656  public:
 657   TypeHandle Bound() { return this->Get(0); }
 658   i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); }
 659
 660   static ConstantHandle New(
 661       i::Handle<i::Object> value, TypeHandle bound, Region* region) {
 662     DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(*value)));
 663     ConstantHandle type = Config::template cast<ConstantType>(
 664         StructuralType::New(StructuralType::kConstantTag, 2, region));
 665     type->Set(0, bound);
 666     type->SetValue(1, value);
 667     return type;
 668   }
 669
 670   static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
 671     TypeHandle bound = BitsetType::New(BitsetType::Lub(*value), region);
 672     return New(value, bound, region);
 673   }
 674
 675   static ConstantType* cast(TypeImpl* type) {
 676     DCHECK(type->IsConstant());
 677     return static_cast<ConstantType*>(type);
 678   }
 679 };
 680
 681
 682 // -----------------------------------------------------------------------------
 683 // Range types.
 684
 685 template<class Config>
 686 class TypeImpl<Config>::RangeType : public StructuralType {
 687  public:
 688   TypeHandle Bound() { return this->Get(0); }
 689   double Min() { return this->template GetValue<i::HeapNumber>(1)->value(); }
 690   double Max() { return this->template GetValue<i::HeapNumber>(2)->value(); }
 691
 692   static RangeHandle New(
 693       double min, double max, TypeHandle bound, Region* region) {
 694     DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::Lub(min, max)));
 695     RangeHandle type = Config::template cast<RangeType>(
 696         StructuralType::New(StructuralType::kRangeTag, 3, region));
 697     type->Set(0, bound);
 698     Factory* factory = Config::isolate(region)->factory();
 699     Handle<HeapNumber> minV = factory->NewHeapNumber(min);
 700     Handle<HeapNumber> maxV = factory->NewHeapNumber(max);
 701     type->SetValue(1, minV);
 702     type->SetValue(2, maxV);
 703     return type;
 704   }
 705
 706   static RangeHandle New(double min, double max, Region* region) {
 707     TypeHandle bound = BitsetType::New(BitsetType::Lub(min, max), region);
 708     return New(min, max, bound, region);
 709   }
 710
 711   static RangeType* cast(TypeImpl* type) {
 712     DCHECK(type->IsRange());
 713     return static_cast<RangeType*>(type);
 714   }
 715 };
 716
 717
 718 // -----------------------------------------------------------------------------
 719 // Context types.
 720
 721 template<class Config>
 722 class TypeImpl<Config>::ContextType : public StructuralType {
 723  public:
 724   TypeHandle Bound() { return this->Get(0); }
 725   TypeHandle Outer() { return this->Get(1); }
 726
 727   static ContextHandle New(TypeHandle outer, TypeHandle bound, Region* region) {
 728     DCHECK(BitsetType::Is(
 729         bound->AsBitset(), BitsetType::kInternal & BitsetType::kTaggedPtr));
 730     ContextHandle type = Config::template cast<ContextType>(
 731         StructuralType::New(StructuralType::kContextTag, 2, region));
 732     type->Set(0, bound);
 733     type->Set(1, outer);
 734     return type;
 735   }
 736
 737   static ContextHandle New(TypeHandle outer, Region* region) {
 738     TypeHandle bound = BitsetType::New(
 739         BitsetType::kInternal & BitsetType::kTaggedPtr, region);
 740     return New(outer, bound, region);
 741   }
 742
 743   static ContextType* cast(TypeImpl* type) {
 744     DCHECK(type->IsContext());
 745     return static_cast<ContextType*>(type);
 746   }
 747 };
 748
 749
 750 // -----------------------------------------------------------------------------
 751 // Array types.
 752
 753 template<class Config>
 754 class TypeImpl<Config>::ArrayType : public StructuralType {
 755  public:
 756   TypeHandle Bound() { return this->Get(0); }
 757   TypeHandle Element() { return this->Get(1); }
 758
 759   static ArrayHandle New(TypeHandle element, TypeHandle bound, Region* region) {
 760     DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kArray));
 761     ArrayHandle type = Config::template cast<ArrayType>(
 762         StructuralType::New(StructuralType::kArrayTag, 2, region));
 763     type->Set(0, bound);
 764     type->Set(1, element);
 765     return type;
 766   }
 767
 768   static ArrayHandle New(TypeHandle element, Region* region) {
 769     TypeHandle bound = BitsetType::New(BitsetType::kArray, region);
 770     return New(element, bound, region);
 771   }
 772
 773   static ArrayType* cast(TypeImpl* type) {
 774     DCHECK(type->IsArray());
 775     return static_cast<ArrayType*>(type);
 776   }
 777 };
 778
 779
 780 // -----------------------------------------------------------------------------
 781 // Function types.
 782
 783 template<class Config>
 784 class TypeImpl<Config>::FunctionType : public StructuralType {
 785  public:
 786   int Arity() { return this->Length() - 3; }
 787   TypeHandle Bound() { return this->Get(0); }
 788   TypeHandle Result() { return this->Get(1); }
 789   TypeHandle Receiver() { return this->Get(2); }
 790   TypeHandle Parameter(int i) { return this->Get(3 + i); }
 791
 792   void InitParameter(int i, TypeHandle type) { this->Set(3 + i, type); }
 793
 794   static FunctionHandle New(
 795       TypeHandle result, TypeHandle receiver, TypeHandle bound,
 796       int arity, Region* region) {
 797     DCHECK(BitsetType::Is(bound->AsBitset(), BitsetType::kFunction));
 798     FunctionHandle type = Config::template cast<FunctionType>(
 799         StructuralType::New(StructuralType::kFunctionTag, 3 + arity, region));
 800     type->Set(0, bound);
 801     type->Set(1, result);
 802     type->Set(2, receiver);
 803     return type;
 804   }
 805
 806   static FunctionHandle New(
 807       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
 808     TypeHandle bound = BitsetType::New(BitsetType::kFunction, region);
 809     return New(result, receiver, bound, arity, region);
 810   }
 811
 812   static FunctionType* cast(TypeImpl* type) {
 813     DCHECK(type->IsFunction());
 814     return static_cast<FunctionType*>(type);
 815   }
 816 };
 817
 818
 819 // -----------------------------------------------------------------------------
 820 // Type iterators.
 821
 822 template<class Config> template<class T>
 823 class TypeImpl<Config>::Iterator {
 824  public:
 825   bool Done() const { return index_ < 0; }
 826   i::Handle<T> Current();
 827   void Advance();
 828
 829  private:
 830   template<class> friend class TypeImpl;
 831
 832   Iterator() : index_(-1) {}
 833   explicit Iterator(TypeHandle type) : type_(type), index_(-1) {
 834     Advance();
 835   }
 836
 837   inline bool matches(TypeHandle type);
 838   inline TypeHandle get_type();
 839
 840   TypeHandle type_;
 841   int index_;
 842 };
 843
 844
 845 // -----------------------------------------------------------------------------
 846 // Zone-allocated types; they are either (odd) integers to represent bitsets, or
 847 // (even) pointers to structures for everything else.
 848
 849 struct ZoneTypeConfig {
 850   typedef TypeImpl<ZoneTypeConfig> Type;
 851   class Base {};
 852   typedef void* Struct;
 853   typedef i::Zone Region;
 854   template<class T> struct Handle { typedef T* type; };
 855
 856   // TODO(neis): This will be removed again once we have struct_get_double().
 857   static inline i::Isolate* isolate(Region* region) {
 858     return region->isolate();
 859   }
 860
 861   template<class T> static inline T* handle(T* type);
 862   template<class T> static inline T* cast(Type* type);
 863
 864   static inline bool is_bitset(Type* type);
 865   static inline bool is_class(Type* type);
 866   static inline bool is_struct(Type* type, int tag);
 867
 868   static inline int as_bitset(Type* type);
 869   static inline i::Handle<i::Map> as_class(Type* type);
 870   static inline Struct* as_struct(Type* type);
 871
 872   static inline Type* from_bitset(int bitset);
 873   static inline Type* from_bitset(int bitset, Zone* zone);
 874   static inline Type* from_class(i::Handle<i::Map> map, Zone* zone);
 875   static inline Type* from_struct(Struct* structured);
 876
 877   static inline Struct* struct_create(int tag, int length, Zone* zone);
 878   static inline void struct_shrink(Struct* structure, int length);
 879   static inline int struct_tag(Struct* structure);
 880   static inline int struct_length(Struct* structure);
 881   static inline Type* struct_get(Struct* structure, int i);
 882   static inline void struct_set(Struct* structure, int i, Type* type);
 883   template<class V>
 884   static inline i::Handle<V> struct_get_value(Struct* structure, int i);
 885   template<class V> static inline void struct_set_value(
 886       Struct* structure, int i, i::Handle<V> x);
 887 };
 888
 889 typedef TypeImpl<ZoneTypeConfig> Type;
 890
 891
 892 // -----------------------------------------------------------------------------
 893 // Heap-allocated types; either smis for bitsets, maps for classes, boxes for
 894 // constants, or fixed arrays for unions.
 895
 896 struct HeapTypeConfig {
 897   typedef TypeImpl<HeapTypeConfig> Type;
 898   typedef i::Object Base;
 899   typedef i::FixedArray Struct;
 900   typedef i::Isolate Region;
 901   template<class T> struct Handle { typedef i::Handle<T> type; };
 902
 903   // TODO(neis): This will be removed again once we have struct_get_double().
 904   static inline i::Isolate* isolate(Region* region) {
 905     return region;
 906   }
 907
 908   template<class T> static inline i::Handle<T> handle(T* type);
 909   template<class T> static inline i::Handle<T> cast(i::Handle<Type> type);
 910
 911   static inline bool is_bitset(Type* type);
 912   static inline bool is_class(Type* type);
 913   static inline bool is_struct(Type* type, int tag);
 914
 915   static inline int as_bitset(Type* type);
 916   static inline i::Handle<i::Map> as_class(Type* type);
 917   static inline i::Handle<Struct> as_struct(Type* type);
 918
 919   static inline Type* from_bitset(int bitset);
 920   static inline i::Handle<Type> from_bitset(int bitset, Isolate* isolate);
 921   static inline i::Handle<Type> from_class(
 922       i::Handle<i::Map> map, Isolate* isolate);
 923   static inline i::Handle<Type> from_struct(i::Handle<Struct> structure);
 924
 925   static inline i::Handle<Struct> struct_create(
 926       int tag, int length, Isolate* isolate);
 927   static inline void struct_shrink(i::Handle<Struct> structure, int length);
 928   static inline int struct_tag(i::Handle<Struct> structure);
 929   static inline int struct_length(i::Handle<Struct> structure);
 930   static inline i::Handle<Type> struct_get(i::Handle<Struct> structure, int i);
 931   static inline void struct_set(
 932       i::Handle<Struct> structure, int i, i::Handle<Type> type);
 933   template<class V>
 934   static inline i::Handle<V> struct_get_value(
 935       i::Handle<Struct> structure, int i);
 936   template<class V>
 937   static inline void struct_set_value(
 938       i::Handle<Struct> structure, int i, i::Handle<V> x);
 939 };
 940
 941 typedef TypeImpl<HeapTypeConfig> HeapType;
 942
 943
 944 // -----------------------------------------------------------------------------
 945 // Type bounds. A simple struct to represent a pair of lower/upper types.
 946
 947 template<class Config>
 948 struct BoundsImpl {
 949   typedef TypeImpl<Config> Type;
 950   typedef typename Type::TypeHandle TypeHandle;
 951   typedef typename Type::Region Region;
 952
 953   TypeHandle lower;
 954   TypeHandle upper;
 955
 956   BoundsImpl() {}
 957   explicit BoundsImpl(TypeHandle t) : lower(t), upper(t) {}
 958   BoundsImpl(TypeHandle l, TypeHandle u) : lower(l), upper(u) {
 959     DCHECK(lower->Is(upper));
 960   }
 961
 962   // Unrestricted bounds.
 963   static BoundsImpl Unbounded(Region* region) {
 964     return BoundsImpl(Type::None(region), Type::Any(region));
 965   }
 966
 967   // Meet: both b1 and b2 are known to hold.
 968   static BoundsImpl Both(BoundsImpl b1, BoundsImpl b2, Region* region) {
 969     TypeHandle lower = Type::Union(b1.lower, b2.lower, region);
 970     TypeHandle upper = Type::Intersect(b1.upper, b2.upper, region);
 971     // Lower bounds are considered approximate, correct as necessary.
 972     lower = Type::Intersect(lower, upper, region);
 973     return BoundsImpl(lower, upper);
 974   }
 975
 976   // Join: either b1 or b2 is known to hold.
 977   static BoundsImpl Either(BoundsImpl b1, BoundsImpl b2, Region* region) {
 978     TypeHandle lower = Type::Intersect(b1.lower, b2.lower, region);
 979     TypeHandle upper = Type::Union(b1.upper, b2.upper, region);
 980     return BoundsImpl(lower, upper);
 981   }
 982
 983   static BoundsImpl NarrowLower(BoundsImpl b, TypeHandle t, Region* region) {
 984     // Lower bounds are considered approximate, correct as necessary.
 985     t = Type::Intersect(t, b.upper, region);
 986     TypeHandle lower = Type::Union(b.lower, t, region);
 987     return BoundsImpl(lower, b.upper);
 988   }
 989   static BoundsImpl NarrowUpper(BoundsImpl b, TypeHandle t, Region* region) {
 990     TypeHandle lower = Type::Intersect(b.lower, t, region);
 991     TypeHandle upper = Type::Intersect(b.upper, t, region);
 992     return BoundsImpl(lower, upper);
 993   }
 994
 995   bool Narrows(BoundsImpl that) {
 996     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
 997   }
 998 };
 999
1000 typedef BoundsImpl<ZoneTypeConfig> Bounds;
1001
1002 } }  // namespace v8::internal
1003
1004 #endif  // V8_TYPES_H_