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