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 "handles.h"
   9
  10 namespace v8 {
  11 namespace internal {
  12
  13 // SUMMARY
  14 //
  15 // A simple type system for compiler-internal use. It is based entirely on
  16 // union types, and all subtyping hence amounts to set inclusion. Besides the
  17 // obvious primitive types and some predefined unions, the type language also
  18 // can express class types (a.k.a. specific maps) and singleton types (i.e.,
  19 // concrete constants).
  20 //
  21 // Types consist of two dimensions: semantic (value range) and representation.
  22 // Both are related through subtyping.
  23 //
  24 // SEMANTIC DIMENSION
  25 //
  26 // The following equations and inequations hold for the semantic axis:
  27 //
  28 //   None <= T
  29 //   T <= Any
  30 //
  31 //   Number = Signed32 \/ Unsigned32 \/ Double
  32 //   Smi <= Signed32
  33 //   Name = String \/ Symbol
  34 //   UniqueName = InternalizedString \/ Symbol
  35 //   InternalizedString < String
  36 //
  37 //   Receiver = Object \/ Proxy
  38 //   Array < Object
  39 //   Function < Object
  40 //   RegExp < Object
  41 //   Undetectable < Object
  42 //   Detectable = Receiver \/ Number \/ Name - Undetectable
  43 //
  44 //   Class(map) < T   iff instance_type(map) < T
  45 //   Constant(x) < T  iff instance_type(map(x)) < T
  46 //   Array(T) < Array
  47 //   Function(R, S, T0, T1, ...) < Function
  48 //
  49 // Both structural Array and Function types are invariant in all parameters.
  50 // Relaxing this would make Union and Intersect operations more involved.
  51 // Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can
  52 // change! (Its instance type cannot, however.)
  53 // TODO(rossberg): the latter is not currently true for proxies, because of fix,
  54 // but will hold once we implement direct proxies.
  55 // However, we also define a 'temporal' variant of the subtyping relation that
  56 // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)).
  57 //
  58 // REPRESENTATIONAL DIMENSION
  59 //
  60 // For the representation axis, the following holds:
  61 //
  62 //   None <= R
  63 //   R <= Any
  64 //
  65 //   UntaggedInt <= UntaggedInt8 \/ UntaggedInt16 \/ UntaggedInt32)
  66 //   UntaggedFloat <= UntaggedFloat32 \/ UntaggedFloat64
  67 //   UntaggedNumber <= UntaggedInt \/ UntaggedFloat
  68 //   Untagged <= UntaggedNumber \/ UntaggedPtr
  69 //   Tagged <= TaggedInt \/ TaggedPtr
  70 //
  71 // Subtyping relates the two dimensions, for example:
  72 //
  73 //   Number <= Tagged \/ UntaggedNumber
  74 //   Object <= TaggedPtr \/ UntaggedPtr
  75 //
  76 // That holds because the semantic type constructors defined by the API create
  77 // types that allow for all possible representations, and dually, the ones for
  78 // representation types initially include all semantic ranges. Representations
  79 // can then e.g. be narrowed for a given semantic type using intersection:
  80 //
  81 //   SignedSmall /\ TaggedInt       (a 'smi')
  82 //   Number /\ TaggedPtr            (a heap number)
  83 //
  84 // PREDICATES
  85 //
  86 // There are two main functions for testing types:
  87 //
  88 //   T1->Is(T2)     -- tests whether T1 is included in T2 (i.e., T1 <= T2)
  89 //   T1->Maybe(T2)  -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0)
  90 //
  91 // Typically, the former is to be used to select representations (e.g., via
  92 // T->Is(SignedSmall())), and the latter to check whether a specific case needs
  93 // handling (e.g., via T->Maybe(Number())).
  94 //
  95 // There is no functionality to discover whether a type is a leaf in the
  96 // lattice. That is intentional. It should always be possible to refine the
  97 // lattice (e.g., splitting up number types further) without invalidating any
  98 // existing assumptions or tests.
  99 // Consequently, do not normally use Equals for type tests, always use Is!
 100 //
 101 // The NowIs operator implements state-sensitive subtying, as described above.
 102 // Any compilation decision based on such temporary properties requires runtime
 103 // guarding!
 104 //
 105 // PROPERTIES
 106 //
 107 // Various formal properties hold for constructors, operators, and predicates
 108 // over types. For example, constructors are injective, subtyping is a complete
 109 // partial order, union and intersection satisfy the usual algebraic properties.
 110 //
 111 // See test/cctest/test-types.cc for a comprehensive executable specification,
 112 // especially with respect to the properties of the more exotic 'temporal'
 113 // constructors and predicates (those prefixed 'Now').
 114 //
 115 // IMPLEMENTATION
 116 //
 117 // Internally, all 'primitive' types, and their unions, are represented as
 118 // bitsets. Class is a heap pointer to the respective map. Only Constant's, or
 119 // unions containing Class'es or Constant's, currently require allocation.
 120 // Note that the bitset representation is closed under both Union and Intersect.
 121 //
 122 // There are two type representations, using different allocation:
 123 //
 124 // - class Type (zone-allocated, for compiler and concurrent compilation)
 125 // - class HeapType (heap-allocated, for persistent types)
 126 //
 127 // Both provide the same API, and the Convert method can be used to interconvert
 128 // them. For zone types, no query method touches the heap, only constructors do.
 129
 130
 131 #define MASK_BITSET_TYPE_LIST(V) \
 132   V(Representation, static_cast<int>(0xff800000)) \
 133   V(Semantic,       static_cast<int>(0x007fffff))
 134
 135 #define REPRESENTATION(k) ((k) & kRepresentation)
 136 #define SEMANTIC(k)       ((k) & kSemantic)
 137
 138 #define REPRESENTATION_BITSET_TYPE_LIST(V) \
 139   V(None,             0)                   \
 140   V(UntaggedInt8,     1 << 23 | kSemantic) \
 141   V(UntaggedInt16,    1 << 24 | kSemantic) \
 142   V(UntaggedInt32,    1 << 25 | kSemantic) \
 143   V(UntaggedFloat32,  1 << 26 | kSemantic) \
 144   V(UntaggedFloat64,  1 << 27 | kSemantic) \
 145   V(UntaggedPtr,      1 << 28 | kSemantic) \
 146   V(TaggedInt,        1 << 29 | kSemantic) \
 147   V(TaggedPtr,        -1 << 30 | kSemantic)  /* MSB has to be sign-extended */ \
 148   \
 149   V(UntaggedInt,      kUntaggedInt8 | kUntaggedInt16 | kUntaggedInt32) \
 150   V(UntaggedFloat,    kUntaggedFloat32 | kUntaggedFloat64)             \
 151   V(UntaggedNumber,   kUntaggedInt | kUntaggedFloat)                   \
 152   V(Untagged,         kUntaggedNumber | kUntaggedPtr)                  \
 153   V(Tagged,           kTaggedInt | kTaggedPtr)
 154
 155 #define SEMANTIC_BITSET_TYPE_LIST(V) \
 156   V(Null,                1 << 0  | REPRESENTATION(kTaggedPtr)) \
 157   V(Undefined,           1 << 1  | REPRESENTATION(kTaggedPtr)) \
 158   V(Boolean,             1 << 2  | REPRESENTATION(kTaggedPtr)) \
 159   V(SignedSmall,         1 << 3  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 160   V(OtherSigned32,       1 << 4  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 161   V(Unsigned32,          1 << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 162   V(Float,               1 << 6  | REPRESENTATION(kTagged | kUntaggedNumber)) \
 163   V(Float32x4,           1 << 7  | REPRESENTATION(kTaggedPtr)) \
 164   V(Float64x2,           1 << 8  | REPRESENTATION(kTaggedPtr)) \
 165   V(Int32x4,             1 << 9  | REPRESENTATION(kTaggedPtr)) \
 166   V(Symbol,              1 << 10  | REPRESENTATION(kTaggedPtr)) \
 167   V(InternalizedString,  1 << 11 | REPRESENTATION(kTaggedPtr)) \
 168   V(OtherString,         1 << 12  | REPRESENTATION(kTaggedPtr)) \
 169   V(Undetectable,        1 << 13 | REPRESENTATION(kTaggedPtr)) \
 170   V(Array,               1 << 14 | REPRESENTATION(kTaggedPtr)) \
 171   V(Function,            1 << 15 | REPRESENTATION(kTaggedPtr)) \
 172   V(RegExp,              1 << 16 | REPRESENTATION(kTaggedPtr)) \
 173   V(OtherObject,         1 << 17 | REPRESENTATION(kTaggedPtr)) \
 174   V(Proxy,               1 << 18 | REPRESENTATION(kTaggedPtr)) \
 175   V(Internal,            1 << 19 | REPRESENTATION(kTagged | kUntagged)) \
 176   \
 177   V(Signed32,            kSignedSmall | kOtherSigned32)                 \
 178   V(Number,              kSigned32 | kUnsigned32 | kFloat)              \
 179   V(String,              kInternalizedString | kOtherString)            \
 180   V(UniqueName,          kSymbol | kInternalizedString)                 \
 181   V(Name,                kSymbol | kString)                             \
 182   V(NumberOrString,      kNumber | kString)                             \
 183   V(DetectableObject,    kArray | kFunction | kRegExp | kOtherObject)   \
 184   V(DetectableReceiver,  kDetectableObject | kProxy)                    \
 185   V(Detectable,          kDetectableReceiver | kNumber | kName)         \
 186   V(Object,              kDetectableObject | kUndetectable)             \
 187   V(Receiver,            kObject | kProxy)                              \
 188   V(NonNumber,           kBoolean | kName | kNull | kReceiver |         \
 189                          kFloat32x4 | kFloat64x2 | kInt32x4 |           \
 190                          kUndefined | kInternal)                        \
 191   V(Any,                 -1)
 192
 193 #define BITSET_TYPE_LIST(V) \
 194   MASK_BITSET_TYPE_LIST(V) \
 195   REPRESENTATION_BITSET_TYPE_LIST(V) \
 196   SEMANTIC_BITSET_TYPE_LIST(V)
 197
 198 // struct Config {
 199 //   typedef TypeImpl<Config> Type;
 200 //   typedef Base;
 201 //   typedef Struct;
 202 //   typedef Region;
 203 //   template<class> struct Handle { typedef type; }  // No template typedefs...
 204 //   template<class T> static Handle<T>::type handle(T* t);  // !is_bitset(t)
 205 //   template<class T> static Handle<T>::type cast(Handle<Type>::type);
 206 //   static bool is_bitset(Type*);
 207 //   static bool is_class(Type*);
 208 //   static bool is_constant(Type*);
 209 //   static bool is_struct(Type*, int tag);
 210 //   static int as_bitset(Type*);
 211 //   static i::Handle<i::Map> as_class(Type*);
 212 //   static i::Handle<i::Object> as_constant(Type*);
 213 //   static Handle<Struct>::type as_struct(Type*);
 214 //   static Type* from_bitset(int bitset);
 215 //   static Handle<Type>::type from_bitset(int bitset, Region*);
 216 //   static Handle<Type>::type from_class(i::Handle<Map>, int lub, Region*);
 217 //   static Handle<Type>::type from_constant(i::Handle<Object>, int, Region*);
 218 //   static Handle<Type>::type from_struct(Handle<Struct>::type, int tag);
 219 //   static Handle<Struct>::type struct_create(int tag, int length, Region*);
 220 //   static void struct_shrink(Handle<Struct>::type, int length);
 221 //   static int struct_tag(Handle<Struct>::type);
 222 //   static int struct_length(Handle<Struct>::type);
 223 //   static Handle<Type>::type struct_get(Handle<Struct>::type, int);
 224 //   static void struct_set(Handle<Struct>::type, int, Handle<Type>::type);
 225 //   static int lub_bitset(Type*);
 226 // }
 227 template<class Config>
 228 class TypeImpl : public Config::Base {
 229  public:
 230   class BitsetType;      // Internal
 231   class StructuralType;  // Internal
 232   class UnionType;       // Internal
 233
 234   class ClassType;
 235   class ConstantType;
 236   class ArrayType;
 237   class FunctionType;
 238
 239   typedef typename Config::template Handle<TypeImpl>::type TypeHandle;
 240   typedef typename Config::template Handle<ClassType>::type ClassHandle;
 241   typedef typename Config::template Handle<ConstantType>::type ConstantHandle;
 242   typedef typename Config::template Handle<ArrayType>::type ArrayHandle;
 243   typedef typename Config::template Handle<FunctionType>::type FunctionHandle;
 244   typedef typename Config::template Handle<UnionType>::type UnionHandle;
 245   typedef typename Config::Region Region;
 246
 247   #define DEFINE_TYPE_CONSTRUCTOR(type, value)                                \
 248     static TypeImpl* type() { return BitsetType::New(BitsetType::k##type); }  \
 249     static TypeHandle type(Region* region) {                                  \
 250       return BitsetType::New(BitsetType::k##type, region);                    \
 251     }
 252   BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
 253   #undef DEFINE_TYPE_CONSTRUCTOR
 254
 255   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
 256     return ClassType::New(map, region);
 257   }
 258   static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
 259     return ConstantType::New(value, region);
 260   }
 261   static TypeHandle Array(TypeHandle element, Region* region) {
 262     return ArrayType::New(element, region);
 263   }
 264   static FunctionHandle Function(
 265       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
 266     return FunctionType::New(result, receiver, arity, region);
 267   }
 268   static TypeHandle Function(TypeHandle result, Region* region) {
 269     return Function(result, Any(region), 0, region);
 270   }
 271   static TypeHandle Function(
 272       TypeHandle result, TypeHandle param0, Region* region) {
 273     FunctionHandle function = Function(result, Any(region), 1, region);
 274     function->InitParameter(0, param0);
 275     return function;
 276   }
 277   static TypeHandle Function(
 278       TypeHandle result, TypeHandle param0, TypeHandle param1, Region* region) {
 279     FunctionHandle function = Function(result, Any(region), 2, region);
 280     function->InitParameter(0, param0);
 281     function->InitParameter(1, param1);
 282     return function;
 283   }
 284
 285   static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg);
 286   static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg);
 287
 288   static TypeHandle Of(i::Object* value, Region* region) {
 289     return Config::from_bitset(BitsetType::Lub(value), region);
 290   }
 291   static TypeHandle Of(i::Handle<i::Object> value, Region* region) {
 292     return Of(*value, region);
 293   }
 294
 295   bool IsInhabited() {
 296     return !this->IsBitset() || BitsetType::IsInhabited(this->AsBitset());
 297   }
 298
 299   bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); }
 300   template<class TypeHandle>
 301   bool Is(TypeHandle that) { return this->Is(*that); }
 302
 303   bool Maybe(TypeImpl* that);
 304   template<class TypeHandle>
 305   bool Maybe(TypeHandle that) { return this->Maybe(*that); }
 306
 307   bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); }
 308   template<class TypeHandle>
 309   bool Equals(TypeHandle that) { return this->Equals(*that); }
 310
 311   // Equivalent to Constant(value)->Is(this), but avoiding allocation.
 312   bool Contains(i::Object* val);
 313   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); }
 314
 315   // State-dependent versions of Of and Is that consider subtyping between
 316   // a constant and its map class.
 317   static TypeHandle NowOf(i::Object* value, Region* region);
 318   static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) {
 319     return NowOf(*value, region);
 320   }
 321   bool NowIs(TypeImpl* that);
 322   template<class TypeHandle>
 323   bool NowIs(TypeHandle that)  { return this->NowIs(*that); }
 324   inline bool NowContains(i::Object* val);
 325   bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); }
 326
 327   bool NowStable();
 328
 329   bool IsClass() { return Config::is_class(this); }
 330   bool IsConstant() { return Config::is_constant(this); }
 331   bool IsArray() { return Config::is_struct(this, StructuralType::kArrayTag); }
 332   bool IsFunction() {
 333     return Config::is_struct(this, StructuralType::kFunctionTag);
 334   }
 335
 336   ClassType* AsClass() { return ClassType::cast(this); }
 337   ConstantType* AsConstant() { return ConstantType::cast(this); }
 338   ArrayType* AsArray() { return ArrayType::cast(this); }
 339   FunctionType* AsFunction() { return FunctionType::cast(this); }
 340
 341   int NumClasses();
 342   int NumConstants();
 343
 344   template<class T> class Iterator;
 345   Iterator<i::Map> Classes() {
 346     if (this->IsBitset()) return Iterator<i::Map>();
 347     return Iterator<i::Map>(Config::handle(this));
 348   }
 349   Iterator<i::Object> Constants() {
 350     if (this->IsBitset()) return Iterator<i::Object>();
 351     return Iterator<i::Object>(Config::handle(this));
 352   }
 353
 354   static inline TypeImpl* cast(typename Config::Base* object);
 355
 356   template<class OtherTypeImpl>
 357   static TypeHandle Convert(
 358       typename OtherTypeImpl::TypeHandle type, Region* region);
 359
 360   enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
 361   void TypePrint(PrintDimension = BOTH_DIMS);
 362   void TypePrint(FILE* out, PrintDimension = BOTH_DIMS);
 363
 364  protected:
 365   template<class> friend class Iterator;
 366   template<class> friend class TypeImpl;
 367
 368   template<class T>
 369   static typename Config::template Handle<T>::type handle(T* type) {
 370     return Config::handle(type);
 371   }
 372
 373   bool IsNone() { return this == None(); }
 374   bool IsAny() { return this == Any(); }
 375   bool IsBitset() { return Config::is_bitset(this); }
 376   bool IsUnion() { return Config::is_struct(this, StructuralType::kUnionTag); }
 377
 378   int AsBitset() {
 379     ASSERT(this->IsBitset());
 380     return static_cast<BitsetType*>(this)->Bitset();
 381   }
 382   UnionType* AsUnion() { return UnionType::cast(this); }
 383
 384   bool SlowIs(TypeImpl* that);
 385
 386   bool InUnion(UnionHandle unioned, int current_size);
 387   static int ExtendUnion(
 388       UnionHandle unioned, TypeHandle t, int current_size);
 389   static int ExtendIntersection(
 390       UnionHandle unioned, TypeHandle t, TypeHandle other, int current_size);
 391
 392   int BitsetGlb() { return BitsetType::Glb(this); }
 393   int BitsetLub() { return BitsetType::Lub(this); }
 394 };
 395
 396
 397 template<class Config>
 398 class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
 399  private:
 400   friend class TypeImpl<Config>;
 401
 402   enum {
 403     #define DECLARE_TYPE(type, value) k##type = (value),
 404     BITSET_TYPE_LIST(DECLARE_TYPE)
 405     #undef DECLARE_TYPE
 406     kUnusedEOL = 0
 407   };
 408
 409   int Bitset() { return Config::as_bitset(this); }
 410
 411   static BitsetType* New(int bitset) {
 412     return static_cast<BitsetType*>(Config::from_bitset(bitset));
 413   }
 414   static TypeHandle New(int bitset, Region* region) {
 415     return Config::from_bitset(bitset, region);
 416   }
 417
 418   static bool IsInhabited(int bitset) {
 419     return (bitset & kRepresentation) && (bitset & kSemantic);
 420   }
 421
 422   static int Glb(TypeImpl* type);  // greatest lower bound that's a bitset
 423   static int Lub(TypeImpl* type);  // least upper bound that's a bitset
 424   static int Lub(i::Object* value);
 425   static int Lub(i::Map* map);
 426
 427   static const char* Name(int bitset);
 428   static void BitsetTypePrint(FILE* out, int bitset);
 429 };
 430
 431
 432 // Internal
 433 // A structured type contains a tag and a variable number of type fields.
 434 template<class Config>
 435 class TypeImpl<Config>::StructuralType : public TypeImpl<Config> {
 436  protected:
 437   template<class> friend class TypeImpl;
 438   friend struct ZoneTypeConfig;  // For tags.
 439   friend struct HeapTypeConfig;
 440
 441   enum Tag {
 442     kClassTag,
 443     kConstantTag,
 444     kArrayTag,
 445     kFunctionTag,
 446     kUnionTag
 447   };
 448
 449   int Length() {
 450     return Config::struct_length(Config::as_struct(this));
 451   }
 452   TypeHandle Get(int i) {
 453     return Config::struct_get(Config::as_struct(this), i);
 454   }
 455   void Set(int i, TypeHandle type) {
 456     Config::struct_set(Config::as_struct(this), i, type);
 457   }
 458   void Shrink(int length) {
 459     Config::struct_shrink(Config::as_struct(this), length);
 460   }
 461
 462   static TypeHandle New(Tag tag, int length, Region* region) {
 463     return Config::from_struct(Config::struct_create(tag, length, region));
 464   }
 465 };
 466
 467
 468 template<class Config>
 469 class TypeImpl<Config>::ClassType : public TypeImpl<Config> {
 470  public:
 471   i::Handle<i::Map> Map() { return Config::as_class(this); }
 472
 473   static ClassHandle New(i::Handle<i::Map> map, Region* region) {
 474     return Config::template cast<ClassType>(
 475         Config::from_class(map, BitsetType::Lub(*map), region));
 476   }
 477
 478   static ClassType* cast(TypeImpl* type) {
 479     ASSERT(type->IsClass());
 480     return static_cast<ClassType*>(type);
 481   }
 482 };
 483
 484
 485 template<class Config>
 486 class TypeImpl<Config>::ConstantType : public TypeImpl<Config> {
 487  public:
 488   i::Handle<i::Object> Value() { return Config::as_constant(this); }
 489
 490   static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
 491     return Config::template cast<ConstantType>(
 492         Config::from_constant(value, BitsetType::Lub(*value), region));
 493   }
 494
 495   static ConstantType* cast(TypeImpl* type) {
 496     ASSERT(type->IsConstant());
 497     return static_cast<ConstantType*>(type);
 498   }
 499 };
 500
 501
 502 // Internal
 503 // A union is a structured type with the following invariants:
 504 // - its length is at least 2
 505 // - at most one field is a bitset, and it must go into index 0
 506 // - no field is a union
 507 template<class Config>
 508 class TypeImpl<Config>::UnionType : public StructuralType {
 509  public:
 510   static UnionHandle New(int length, Region* region) {
 511     return Config::template cast<UnionType>(
 512         StructuralType::New(StructuralType::kUnionTag, length, region));
 513   }
 514
 515   static UnionType* cast(TypeImpl* type) {
 516     ASSERT(type->IsUnion());
 517     return static_cast<UnionType*>(type);
 518   }
 519 };
 520
 521
 522 template<class Config>
 523 class TypeImpl<Config>::ArrayType : public StructuralType {
 524  public:
 525   TypeHandle Element() { return this->Get(0); }
 526
 527   static ArrayHandle New(TypeHandle element, Region* region) {
 528     ArrayHandle type = Config::template cast<ArrayType>(
 529         StructuralType::New(StructuralType::kArrayTag, 1, region));
 530     type->Set(0, element);
 531     return type;
 532   }
 533
 534   static ArrayType* cast(TypeImpl* type) {
 535     ASSERT(type->IsArray());
 536     return static_cast<ArrayType*>(type);
 537   }
 538 };
 539
 540
 541 template<class Config>
 542 class TypeImpl<Config>::FunctionType : public StructuralType {
 543  public:
 544   int Arity() { return this->Length() - 2; }
 545   TypeHandle Result() { return this->Get(0); }
 546   TypeHandle Receiver() { return this->Get(1); }
 547   TypeHandle Parameter(int i) { return this->Get(2 + i); }
 548
 549   void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); }
 550
 551   static FunctionHandle New(
 552       TypeHandle result, TypeHandle receiver, int arity, Region* region) {
 553     FunctionHandle type = Config::template cast<FunctionType>(
 554         StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region));
 555     type->Set(0, result);
 556     type->Set(1, receiver);
 557     return type;
 558   }
 559
 560   static FunctionType* cast(TypeImpl* type) {
 561     ASSERT(type->IsFunction());
 562     return static_cast<FunctionType*>(type);
 563   }
 564 };
 565
 566
 567 template<class Config> template<class T>
 568 class TypeImpl<Config>::Iterator {
 569  public:
 570   bool Done() const { return index_ < 0; }
 571   i::Handle<T> Current();
 572   void Advance();
 573
 574  private:
 575   template<class> friend class TypeImpl;
 576
 577   Iterator() : index_(-1) {}
 578   explicit Iterator(TypeHandle type) : type_(type), index_(-1) {
 579     Advance();
 580   }
 581
 582   inline bool matches(TypeHandle type);
 583   inline TypeHandle get_type();
 584
 585   TypeHandle type_;
 586   int index_;
 587 };
 588
 589
 590 // Zone-allocated types are either (odd) integers to represent bitsets, or
 591 // (even) pointers to structures for everything else.
 592 struct ZoneTypeConfig {
 593   typedef TypeImpl<ZoneTypeConfig> Type;
 594   class Base {};
 595   typedef void* Struct;
 596   typedef i::Zone Region;
 597   template<class T> struct Handle { typedef T* type; };
 598
 599   template<class T> static inline T* handle(T* type);
 600   template<class T> static inline T* cast(Type* type);
 601
 602   static inline bool is_bitset(Type* type);
 603   static inline bool is_class(Type* type);
 604   static inline bool is_constant(Type* type);
 605   static inline bool is_struct(Type* type, int tag);
 606
 607   static inline int as_bitset(Type* type);
 608   static inline Struct* as_struct(Type* type);
 609   static inline i::Handle<i::Map> as_class(Type* type);
 610   static inline i::Handle<i::Object> as_constant(Type* type);
 611
 612   static inline Type* from_bitset(int bitset);
 613   static inline Type* from_bitset(int bitset, Zone* zone);
 614   static inline Type* from_struct(Struct* structured);
 615   static inline Type* from_class(i::Handle<i::Map> map, int lub, Zone* zone);
 616   static inline Type* from_constant(
 617       i::Handle<i::Object> value, int lub, Zone* zone);
 618
 619   static inline Struct* struct_create(int tag, int length, Zone* zone);
 620   static inline void struct_shrink(Struct* structured, int length);
 621   static inline int struct_tag(Struct* structured);
 622   static inline int struct_length(Struct* structured);
 623   static inline Type* struct_get(Struct* structured, int i);
 624   static inline void struct_set(Struct* structured, int i, Type* type);
 625
 626   static inline int lub_bitset(Type* type);
 627 };
 628
 629 typedef TypeImpl<ZoneTypeConfig> Type;
 630
 631
 632 // Heap-allocated types are either smis for bitsets, maps for classes, boxes for
 633 // constants, or fixed arrays for unions.
 634 struct HeapTypeConfig {
 635   typedef TypeImpl<HeapTypeConfig> Type;
 636   typedef i::Object Base;
 637   typedef i::FixedArray Struct;
 638   typedef i::Isolate Region;
 639   template<class T> struct Handle { typedef i::Handle<T> type; };
 640
 641   template<class T> static inline i::Handle<T> handle(T* type);
 642   template<class T> static inline i::Handle<T> cast(i::Handle<Type> type);
 643
 644   static inline bool is_bitset(Type* type);
 645   static inline bool is_class(Type* type);
 646   static inline bool is_constant(Type* type);
 647   static inline bool is_struct(Type* type, int tag);
 648
 649   static inline int as_bitset(Type* type);
 650   static inline i::Handle<i::Map> as_class(Type* type);
 651   static inline i::Handle<i::Object> as_constant(Type* type);
 652   static inline i::Handle<Struct> as_struct(Type* type);
 653
 654   static inline Type* from_bitset(int bitset);
 655   static inline i::Handle<Type> from_bitset(int bitset, Isolate* isolate);
 656   static inline i::Handle<Type> from_class(
 657       i::Handle<i::Map> map, int lub, Isolate* isolate);
 658   static inline i::Handle<Type> from_constant(
 659       i::Handle<i::Object> value, int lub, Isolate* isolate);
 660   static inline i::Handle<Type> from_struct(i::Handle<Struct> structured);
 661
 662   static inline i::Handle<Struct> struct_create(
 663       int tag, int length, Isolate* isolate);
 664   static inline void struct_shrink(i::Handle<Struct> structured, int length);
 665   static inline int struct_tag(i::Handle<Struct> structured);
 666   static inline int struct_length(i::Handle<Struct> structured);
 667   static inline i::Handle<Type> struct_get(i::Handle<Struct> structured, int i);
 668   static inline void struct_set(
 669       i::Handle<Struct> structured, int i, i::Handle<Type> type);
 670
 671   static inline int lub_bitset(Type* type);
 672 };
 673
 674 typedef TypeImpl<HeapTypeConfig> HeapType;
 675
 676
 677 // A simple struct to represent a pair of lower/upper type bounds.
 678 template<class Config>
 679 struct BoundsImpl {
 680   typedef TypeImpl<Config> Type;
 681   typedef typename Type::TypeHandle TypeHandle;
 682   typedef typename Type::Region Region;
 683
 684   TypeHandle lower;
 685   TypeHandle upper;
 686
 687   BoundsImpl() {}
 688   explicit BoundsImpl(TypeHandle t) : lower(t), upper(t) {}
 689   BoundsImpl(TypeHandle l, TypeHandle u) : lower(l), upper(u) {
 690     ASSERT(lower->Is(upper));
 691   }
 692
 693   // Unrestricted bounds.
 694   static BoundsImpl Unbounded(Region* region) {
 695     return BoundsImpl(Type::None(region), Type::Any(region));
 696   }
 697
 698   // Meet: both b1 and b2 are known to hold.
 699   static BoundsImpl Both(BoundsImpl b1, BoundsImpl b2, Region* region) {
 700     TypeHandle lower = Type::Union(b1.lower, b2.lower, region);
 701     TypeHandle upper = Type::Intersect(b1.upper, b2.upper, region);
 702     // Lower bounds are considered approximate, correct as necessary.
 703     lower = Type::Intersect(lower, upper, region);
 704     return BoundsImpl(lower, upper);
 705   }
 706
 707   // Join: either b1 or b2 is known to hold.
 708   static BoundsImpl Either(BoundsImpl b1, BoundsImpl b2, Region* region) {
 709     TypeHandle lower = Type::Intersect(b1.lower, b2.lower, region);
 710     TypeHandle upper = Type::Union(b1.upper, b2.upper, region);
 711     return BoundsImpl(lower, upper);
 712   }
 713
 714   static BoundsImpl NarrowLower(BoundsImpl b, TypeHandle t, Region* region) {
 715     // Lower bounds are considered approximate, correct as necessary.
 716     t = Type::Intersect(t, b.upper, region);
 717     TypeHandle lower = Type::Union(b.lower, t, region);
 718     return BoundsImpl(lower, b.upper);
 719   }
 720   static BoundsImpl NarrowUpper(BoundsImpl b, TypeHandle t, Region* region) {
 721     TypeHandle lower = Type::Intersect(b.lower, t, region);
 722     TypeHandle upper = Type::Intersect(b.upper, t, region);
 723     return BoundsImpl(lower, upper);
 724   }
 725
 726   bool Narrows(BoundsImpl that) {
 727     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
 728   }
 729 };
 730
 731 typedef BoundsImpl<ZoneTypeConfig> Bounds;
 732
 733 } }  // namespace v8::internal
 734
 735 #endif  // V8_TYPES_H_