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/conversions.h" 9 #include "src/handles.h" 10 #include "src/objects.h" 11 #include "src/ostreams.h" 12 13 namespace v8 { 14 namespace internal { 15 16 // SUMMARY 17 // 18 // A simple type system for compiler-internal use. It is based entirely on 19 // union types, and all subtyping hence amounts to set inclusion. Besides the 20 // obvious primitive types and some predefined unions, the type language also 21 // can express class types (a.k.a. specific maps) and singleton types (i.e., 22 // concrete constants). 23 // 24 // Types consist of two dimensions: semantic (value range) and representation. 25 // Both are related through subtyping. 26 // 27 // 28 // SEMANTIC DIMENSION 29 // 30 // The following equations and inequations hold for the semantic axis: 31 // 32 // None <= T 33 // T <= Any 34 // 35 // Number = Signed32 \/ Unsigned32 \/ Double 36 // Smi <= Signed32 37 // Name = String \/ Symbol 38 // UniqueName = InternalizedString \/ Symbol 39 // InternalizedString < String 40 // 41 // Receiver = Object \/ Proxy 42 // Array < Object 43 // Function < Object 44 // RegExp < Object 45 // OtherUndetectable < Object 46 // DetectableReceiver = Receiver - OtherUndetectable 47 // 48 // Class(map) < T iff instance_type(map) < T 49 // Constant(x) < T iff instance_type(map(x)) < T 50 // Array(T) < Array 51 // Function(R, S, T0, T1, ...) < Function 52 // Context(T) < Internal 53 // 54 // Both structural Array and Function types are invariant in all parameters; 55 // relaxing this would make Union and Intersect operations more involved. 56 // There is no subtyping relation between Array, Function, or Context types 57 // and respective Constant types, since these types cannot be reconstructed 58 // for arbitrary heap values. 59 // Note also that Constant(x) < Class(map(x)) does _not_ hold, since x's map can 60 // change! (Its instance type cannot, however.) 61 // TODO(rossberg): the latter is not currently true for proxies, because of fix, 62 // but will hold once we implement direct proxies. 63 // However, we also define a 'temporal' variant of the subtyping relation that 64 // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)). 65 // 66 // 67 // REPRESENTATIONAL DIMENSION 68 // 69 // For the representation axis, the following holds: 70 // 71 // None <= R 72 // R <= Any 73 // 74 // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ 75 // UntaggedInt16 \/ UntaggedInt32 76 // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64 77 // UntaggedNumber = UntaggedInt \/ UntaggedFloat 78 // Untagged = UntaggedNumber \/ UntaggedPtr 79 // Tagged = TaggedInt \/ TaggedPtr 80 // 81 // Subtyping relates the two dimensions, for example: 82 // 83 // Number <= Tagged \/ UntaggedNumber 84 // Object <= TaggedPtr \/ UntaggedPtr 85 // 86 // That holds because the semantic type constructors defined by the API create 87 // types that allow for all possible representations, and dually, the ones for 88 // representation types initially include all semantic ranges. Representations 89 // can then e.g. be narrowed for a given semantic type using intersection: 90 // 91 // SignedSmall /\ TaggedInt (a 'smi') 92 // Number /\ TaggedPtr (a heap number) 93 // 94 // 95 // RANGE TYPES 96 // 97 // A range type represents a continuous integer interval by its minimum and 98 // maximum value. Either value may be an infinity, in which case that infinity 99 // itself is also included in the range. A range never contains NaN or -0. 100 // 101 // If a value v happens to be an integer n, then Constant(v) is considered a 102 // subtype of Range(n, n) (and therefore also a subtype of any larger range). 103 // In order to avoid large unions, however, it is usually a good idea to use 104 // Range rather than Constant. 105 // 106 // 107 // PREDICATES 108 // 109 // There are two main functions for testing types: 110 // 111 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) 112 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) 113 // 114 // Typically, the former is to be used to select representations (e.g., via 115 // T->Is(SignedSmall())), and the latter to check whether a specific case needs 116 // handling (e.g., via T->Maybe(Number())). 117 // 118 // There is no functionality to discover whether a type is a leaf in the 119 // lattice. That is intentional. It should always be possible to refine the 120 // lattice (e.g., splitting up number types further) without invalidating any 121 // existing assumptions or tests. 122 // Consequently, do not normally use Equals for type tests, always use Is! 123 // 124 // The NowIs operator implements state-sensitive subtying, as described above. 125 // Any compilation decision based on such temporary properties requires runtime 126 // guarding! 127 // 128 // 129 // PROPERTIES 130 // 131 // Various formal properties hold for constructors, operators, and predicates 132 // over types. For example, constructors are injective and subtyping is a 133 // complete partial order. 134 // 135 // See test/cctest/test-types.cc for a comprehensive executable specification, 136 // especially with respect to the properties of the more exotic 'temporal' 137 // constructors and predicates (those prefixed 'Now'). 138 // 139 // 140 // IMPLEMENTATION 141 // 142 // Internally, all 'primitive' types, and their unions, are represented as 143 // bitsets. Bit 0 is reserved for tagging. Class is a heap pointer to the 144 // respective map. Only structured types require allocation. 145 // Note that the bitset representation is closed under both Union and Intersect. 146 147 148 // ----------------------------------------------------------------------------- 149 // Values for bitset types 150 151 // clang-format off 152 153 #define MASK_BITSET_TYPE_LIST(V) \ 154 V(Representation, 0xffc00000u) \ 155 V(Semantic, 0x003ffffeu) 156 157 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) 158 #define SEMANTIC(k) ((k) & BitsetType::kSemantic) 159 160 #define REPRESENTATION_BITSET_TYPE_LIST(V) \ 161 V(None, 0) \ 162 V(UntaggedBit, 1u << 22 | kSemantic) \ 163 V(UntaggedIntegral8, 1u << 23 | kSemantic) \ 164 V(UntaggedIntegral16, 1u << 24 | kSemantic) \ 165 V(UntaggedIntegral32, 1u << 25 | kSemantic) \ 166 V(UntaggedFloat32, 1u << 26 | kSemantic) \ 167 V(UntaggedFloat64, 1u << 27 | kSemantic) \ 168 V(UntaggedSimd128, 1u << 28 | kSemantic) \ 169 V(UntaggedPointer, 1u << 29 | kSemantic) \ 170 V(TaggedSigned, 1u << 30 | kSemantic) \ 171 V(TaggedPointer, 1u << 31 | kSemantic) \ 172 \ 173 V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \ 174 kUntaggedIntegral16 | kUntaggedIntegral32) \ 175 V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ 176 V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \ 177 V(Untagged, kUntaggedNumber | kUntaggedPointer) \ 178 V(Tagged, kTaggedSigned | kTaggedPointer) 179 180 #define INTERNAL_BITSET_TYPE_LIST(V) \ 181 V(OtherUnsigned31, 1u << 1 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 182 V(OtherUnsigned32, 1u << 2 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 183 V(OtherSigned32, 1u << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 184 V(OtherNumber, 1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber)) 185 186 #define SEMANTIC_BITSET_TYPE_LIST(V) \ 187 V(Negative31, 1u << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 188 V(Null, 1u << 6 | REPRESENTATION(kTaggedPointer)) \ 189 V(Undefined, 1u << 7 | REPRESENTATION(kTaggedPointer)) \ 190 V(Boolean, 1u << 8 | REPRESENTATION(kTaggedPointer)) \ 191 V(Unsigned30, 1u << 9 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 192 V(MinusZero, 1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 193 V(NaN, 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 194 V(Symbol, 1u << 12 | REPRESENTATION(kTaggedPointer)) \ 195 V(InternalizedString, 1u << 13 | REPRESENTATION(kTaggedPointer)) \ 196 V(OtherString, 1u << 14 | REPRESENTATION(kTaggedPointer)) \ 197 V(Simd, 1u << 15 | REPRESENTATION(kTaggedPointer)) \ 198 V(OtherObject, 1u << 17 | REPRESENTATION(kTaggedPointer)) \ 199 V(OtherUndetectable, 1u << 16 | REPRESENTATION(kTaggedPointer)) \ 200 V(Proxy, 1u << 18 | REPRESENTATION(kTaggedPointer)) \ 201 V(Function, 1u << 19 | REPRESENTATION(kTaggedPointer)) \ 202 V(Internal, 1u << 20 | REPRESENTATION(kTagged | kUntagged)) \ 203 \ 204 V(Signed31, kUnsigned30 | kNegative31) \ 205 V(Signed32, kSigned31 | kOtherUnsigned31 | kOtherSigned32) \ 206 V(Negative32, kNegative31 | kOtherSigned32) \ 207 V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \ 208 V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \ 209 kOtherUnsigned32) \ 210 V(Integral32, kSigned32 | kUnsigned32) \ 211 V(PlainNumber, kIntegral32 | kOtherNumber) \ 212 V(OrderedNumber, kPlainNumber | kMinusZero) \ 213 V(MinusZeroOrNaN, kMinusZero | kNaN) \ 214 V(Number, kOrderedNumber | kNaN) \ 215 V(String, kInternalizedString | kOtherString) \ 216 V(UniqueName, kSymbol | kInternalizedString) \ 217 V(Name, kSymbol | kString) \ 218 V(BooleanOrNumber, kBoolean | kNumber) \ 219 V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \ 220 V(NullOrUndefined, kNull | kUndefined) \ 221 V(Undetectable, kNullOrUndefined | kOtherUndetectable) \ 222 V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean) \ 223 V(NumberOrSimdOrString, kNumber | kSimd | kString) \ 224 V(NumberOrString, kNumber | kString) \ 225 V(NumberOrUndefined, kNumber | kUndefined) \ 226 V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \ 227 V(Primitive, kSymbol | kSimd | kPlainPrimitive) \ 228 V(DetectableReceiver, kFunction | kOtherObject | kProxy) \ 229 V(Object, kFunction | kOtherObject | kOtherUndetectable) \ 230 V(Receiver, kObject | kProxy) \ 231 V(StringOrReceiver, kString | kReceiver) \ 232 V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \ 233 kReceiver) \ 234 V(NonInternal, kPrimitive | kReceiver) \ 235 V(NonNumber, kUnique | kString | kInternal) \ 236 V(Any, 0xfffffffeu) 237 238 // clang-format on 239 240 /* 241 * The following diagrams show how integers (in the mathematical sense) are 242 * divided among the different atomic numerical types. 243 * 244 * ON OS32 N31 U30 OU31 OU32 ON 245 * ______[_______[_______[_______[_______[_______[_______ 246 * -2^31 -2^30 0 2^30 2^31 2^32 247 * 248 * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. 249 * 250 * Some of the atomic numerical bitsets are internal only (see 251 * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in 252 * union with certain other bitsets. For instance, OtherNumber should only 253 * occur as part of PlainNumber. 254 */ 255 256 #define PROPER_BITSET_TYPE_LIST(V) \ 257 REPRESENTATION_BITSET_TYPE_LIST(V) \ 258 SEMANTIC_BITSET_TYPE_LIST(V) 259 260 #define BITSET_TYPE_LIST(V) \ 261 MASK_BITSET_TYPE_LIST(V) \ 262 REPRESENTATION_BITSET_TYPE_LIST(V) \ 263 INTERNAL_BITSET_TYPE_LIST(V) \ 264 SEMANTIC_BITSET_TYPE_LIST(V) 265 266 class Type; 267 268 // ----------------------------------------------------------------------------- 269 // Bitset types (internal). 270 271 class BitsetType { 272 public: 273 typedef uint32_t bitset; // Internal 274 275 enum : uint32_t { 276 #define DECLARE_TYPE(type, value) k##type = (value), 277 BITSET_TYPE_LIST(DECLARE_TYPE) 278 #undef DECLARE_TYPE 279 kUnusedEOL = 0 280 }; 281 282 static bitset SignedSmall(); 283 static bitset UnsignedSmall(); 284 285 bitset Bitset() { 286 return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); 287 } 288 289 static bool IsInhabited(bitset bits) { 290 return SEMANTIC(bits) != kNone && REPRESENTATION(bits) != kNone; 291 } 292 293 static bool SemanticIsInhabited(bitset bits) { 294 return SEMANTIC(bits) != kNone; 295 } 296 297 static bool Is(bitset bits1, bitset bits2) { 298 return (bits1 | bits2) == bits2; 299 } 300 301 static double Min(bitset); 302 static double Max(bitset); 303 304 static bitset Glb(Type* type); // greatest lower bound that's a bitset 305 static bitset Glb(double min, double max); 306 static bitset Lub(Type* type); // least upper bound that's a bitset 307 static bitset Lub(i::Map* map); 308 static bitset Lub(i::Object* value); 309 static bitset Lub(double value); 310 static bitset Lub(double min, double max); 311 static bitset ExpandInternals(bitset bits); 312 313 static const char* Name(bitset); 314 static void Print(std::ostream& os, bitset); // NOLINT 315 #ifdef DEBUG 316 static void Print(bitset); 317 #endif 318 319 static bitset NumberBits(bitset bits); 320 321 static bool IsBitset(Type* type) { 322 return reinterpret_cast<uintptr_t>(type) & 1; 323 } 324 325 static Type* NewForTesting(bitset bits) { return New(bits); } 326 327 private: 328 friend class Type; 329 330 static Type* New(bitset bits) { 331 return reinterpret_cast<Type*>(static_cast<uintptr_t>(bits | 1u)); 332 } 333 334 struct Boundary { 335 bitset internal; 336 bitset external; 337 double min; 338 }; 339 static const Boundary BoundariesArray[]; 340 static inline const Boundary* Boundaries(); 341 static inline size_t BoundariesSize(); 342 }; 343 344 // ----------------------------------------------------------------------------- 345 // Superclass for non-bitset types (internal). 346 class TypeBase { 347 protected: 348 friend class Type; 349 350 enum Kind { 351 kClass, 352 kConstant, 353 kContext, 354 kArray, 355 kFunction, 356 kTuple, 357 kUnion, 358 kRange 359 }; 360 361 Kind kind() const { return kind_; } 362 explicit TypeBase(Kind kind) : kind_(kind) {} 363 364 static bool IsKind(Type* type, Kind kind) { 365 if (BitsetType::IsBitset(type)) return false; 366 TypeBase* base = reinterpret_cast<TypeBase*>(type); 367 return base->kind() == kind; 368 } 369 370 // The hacky conversion to/from Type*. 371 static Type* AsType(TypeBase* type) { return reinterpret_cast<Type*>(type); } 372 static TypeBase* FromType(Type* type) { 373 return reinterpret_cast<TypeBase*>(type); 374 } 375 376 private: 377 Kind kind_; 378 }; 379 380 // ----------------------------------------------------------------------------- 381 // Class types. 382 383 class ClassType : public TypeBase { 384 public: 385 i::Handle<i::Map> Map() { return map_; } 386 387 private: 388 friend class Type; 389 friend class BitsetType; 390 391 static Type* New(i::Handle<i::Map> map, Zone* zone) { 392 return AsType(new (zone->New(sizeof(ClassType))) 393 ClassType(BitsetType::Lub(*map), map)); 394 } 395 396 static ClassType* cast(Type* type) { 397 DCHECK(IsKind(type, kClass)); 398 return static_cast<ClassType*>(FromType(type)); 399 } 400 401 ClassType(BitsetType::bitset bitset, i::Handle<i::Map> map) 402 : TypeBase(kClass), bitset_(bitset), map_(map) {} 403 404 BitsetType::bitset Lub() { return bitset_; } 405 406 BitsetType::bitset bitset_; 407 Handle<i::Map> map_; 408 }; 409 410 // ----------------------------------------------------------------------------- 411 // Constant types. 412 413 class ConstantType : public TypeBase { 414 public: 415 i::Handle<i::Object> Value() { return object_; } 416 417 private: 418 friend class Type; 419 friend class BitsetType; 420 421 static Type* New(i::Handle<i::Object> value, Zone* zone) { 422 BitsetType::bitset bitset = BitsetType::Lub(*value); 423 return AsType(new (zone->New(sizeof(ConstantType))) 424 ConstantType(bitset, value)); 425 } 426 427 static ConstantType* cast(Type* type) { 428 DCHECK(IsKind(type, kConstant)); 429 return static_cast<ConstantType*>(FromType(type)); 430 } 431 432 ConstantType(BitsetType::bitset bitset, i::Handle<i::Object> object) 433 : TypeBase(kConstant), bitset_(bitset), object_(object) {} 434 435 BitsetType::bitset Lub() { return bitset_; } 436 437 BitsetType::bitset bitset_; 438 Handle<i::Object> object_; 439 }; 440 // TODO(neis): Also cache value if numerical. 441 // TODO(neis): Allow restricting the representation. 442 443 // ----------------------------------------------------------------------------- 444 // Range types. 445 446 class RangeType : public TypeBase { 447 public: 448 struct Limits { 449 double min; 450 double max; 451 Limits(double min, double max) : min(min), max(max) {} 452 explicit Limits(RangeType* range) : min(range->Min()), max(range->Max()) {} 453 bool IsEmpty(); 454 static Limits Empty() { return Limits(1, 0); } 455 static Limits Intersect(Limits lhs, Limits rhs); 456 static Limits Union(Limits lhs, Limits rhs); 457 }; 458 459 double Min() { return limits_.min; } 460 double Max() { return limits_.max; } 461 462 private: 463 friend class Type; 464 friend class BitsetType; 465 friend class UnionType; 466 467 static Type* New(double min, double max, BitsetType::bitset representation, 468 Zone* zone) { 469 return New(Limits(min, max), representation, zone); 470 } 471 472 static bool IsInteger(double x) { 473 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. 474 } 475 476 static Type* New(Limits lim, BitsetType::bitset representation, Zone* zone) { 477 DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); 478 DCHECK(lim.min <= lim.max); 479 DCHECK(REPRESENTATION(representation) == representation); 480 BitsetType::bitset bits = 481 SEMANTIC(BitsetType::Lub(lim.min, lim.max)) | representation; 482 483 return AsType(new (zone->New(sizeof(RangeType))) RangeType(bits, lim)); 484 } 485 486 static RangeType* cast(Type* type) { 487 DCHECK(IsKind(type, kRange)); 488 return static_cast<RangeType*>(FromType(type)); 489 } 490 491 RangeType(BitsetType::bitset bitset, Limits limits) 492 : TypeBase(kRange), bitset_(bitset), limits_(limits) {} 493 494 BitsetType::bitset Lub() { return bitset_; } 495 496 BitsetType::bitset bitset_; 497 Limits limits_; 498 }; 499 500 // ----------------------------------------------------------------------------- 501 // Context types. 502 503 class ContextType : public TypeBase { 504 public: 505 Type* Outer() { return outer_; } 506 507 private: 508 friend class Type; 509 510 static Type* New(Type* outer, Zone* zone) { 511 return AsType(new (zone->New(sizeof(ContextType))) ContextType(outer)); 512 } 513 514 static ContextType* cast(Type* type) { 515 DCHECK(IsKind(type, kContext)); 516 return static_cast<ContextType*>(FromType(type)); 517 } 518 519 explicit ContextType(Type* outer) : TypeBase(kContext), outer_(outer) {} 520 521 Type* outer_; 522 }; 523 524 // ----------------------------------------------------------------------------- 525 // Array types. 526 527 class ArrayType : public TypeBase { 528 public: 529 Type* Element() { return element_; } 530 531 private: 532 friend class Type; 533 534 explicit ArrayType(Type* element) : TypeBase(kArray), element_(element) {} 535 536 static Type* New(Type* element, Zone* zone) { 537 return AsType(new (zone->New(sizeof(ArrayType))) ArrayType(element)); 538 } 539 540 static ArrayType* cast(Type* type) { 541 DCHECK(IsKind(type, kArray)); 542 return static_cast<ArrayType*>(FromType(type)); 543 } 544 545 Type* element_; 546 }; 547 548 // ----------------------------------------------------------------------------- 549 // Superclass for types with variable number of type fields. 550 class StructuralType : public TypeBase { 551 public: 552 int LengthForTesting() { return Length(); } 553 554 protected: 555 friend class Type; 556 557 int Length() { return length_; } 558 559 Type* Get(int i) { 560 DCHECK(0 <= i && i < this->Length()); 561 return elements_[i]; 562 } 563 564 void Set(int i, Type* type) { 565 DCHECK(0 <= i && i < this->Length()); 566 elements_[i] = type; 567 } 568 569 void Shrink(int length) { 570 DCHECK(2 <= length && length <= this->Length()); 571 length_ = length; 572 } 573 574 StructuralType(Kind kind, int length, i::Zone* zone) 575 : TypeBase(kind), length_(length) { 576 elements_ = reinterpret_cast<Type**>(zone->New(sizeof(Type*) * length)); 577 } 578 579 private: 580 int length_; 581 Type** elements_; 582 }; 583 584 // ----------------------------------------------------------------------------- 585 // Function types. 586 587 class FunctionType : public StructuralType { 588 public: 589 int Arity() { return this->Length() - 2; } 590 Type* Result() { return this->Get(0); } 591 Type* Receiver() { return this->Get(1); } 592 Type* Parameter(int i) { return this->Get(2 + i); } 593 594 void InitParameter(int i, Type* type) { this->Set(2 + i, type); } 595 596 private: 597 friend class Type; 598 599 FunctionType(Type* result, Type* receiver, int arity, Zone* zone) 600 : StructuralType(kFunction, 2 + arity, zone) { 601 Set(0, result); 602 Set(1, receiver); 603 } 604 605 static Type* New(Type* result, Type* receiver, int arity, Zone* zone) { 606 return AsType(new (zone->New(sizeof(FunctionType))) 607 FunctionType(result, receiver, arity, zone)); 608 } 609 610 static FunctionType* cast(Type* type) { 611 DCHECK(IsKind(type, kFunction)); 612 return static_cast<FunctionType*>(FromType(type)); 613 } 614 }; 615 616 // ----------------------------------------------------------------------------- 617 // Tuple types. 618 619 class TupleType : public StructuralType { 620 public: 621 int Arity() { return this->Length(); } 622 Type* Element(int i) { return this->Get(i); } 623 624 void InitElement(int i, Type* type) { this->Set(i, type); } 625 626 private: 627 friend class Type; 628 629 TupleType(int length, Zone* zone) : StructuralType(kTuple, length, zone) {} 630 631 static Type* New(int length, Zone* zone) { 632 return AsType(new (zone->New(sizeof(TupleType))) TupleType(length, zone)); 633 } 634 635 static TupleType* cast(Type* type) { 636 DCHECK(IsKind(type, kTuple)); 637 return static_cast<TupleType*>(FromType(type)); 638 } 639 }; 640 641 // ----------------------------------------------------------------------------- 642 // Union types (internal). 643 // A union is a structured type with the following invariants: 644 // - its length is at least 2 645 // - at most one field is a bitset, and it must go into index 0 646 // - no field is a union 647 // - no field is a subtype of any other field 648 class UnionType : public StructuralType { 649 private: 650 friend Type; 651 friend BitsetType; 652 653 UnionType(int length, Zone* zone) : StructuralType(kUnion, length, zone) {} 654 655 static Type* New(int length, Zone* zone) { 656 return AsType(new (zone->New(sizeof(UnionType))) UnionType(length, zone)); 657 } 658 659 static UnionType* cast(Type* type) { 660 DCHECK(IsKind(type, kUnion)); 661 return static_cast<UnionType*>(FromType(type)); 662 } 663 664 bool Wellformed(); 665 }; 666 667 class Type { 668 public: 669 typedef BitsetType::bitset bitset; // Internal 670 671 // Constructors. 672 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ 673 static Type* type() { return BitsetType::New(BitsetType::k##type); } 674 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) 675 #undef DEFINE_TYPE_CONSTRUCTOR 676 677 static Type* SignedSmall() { 678 return BitsetType::New(BitsetType::SignedSmall()); 679 } 680 static Type* UnsignedSmall() { 681 return BitsetType::New(BitsetType::UnsignedSmall()); 682 } 683 684 static Type* Class(i::Handle<i::Map> map, Zone* zone) { 685 return ClassType::New(map, zone); 686 } 687 static Type* Constant(i::Handle<i::Object> value, Zone* zone) { 688 return ConstantType::New(value, zone); 689 } 690 static Type* Range(double min, double max, Zone* zone) { 691 return RangeType::New(min, max, REPRESENTATION(BitsetType::kTagged | 692 BitsetType::kUntaggedNumber), 693 zone); 694 } 695 static Type* Context(Type* outer, Zone* zone) { 696 return ContextType::New(outer, zone); 697 } 698 static Type* Array(Type* element, Zone* zone) { 699 return ArrayType::New(element, zone); 700 } 701 static Type* Function(Type* result, Type* receiver, int arity, Zone* zone) { 702 return FunctionType::New(result, receiver, arity, zone); 703 } 704 static Type* Function(Type* result, Zone* zone) { 705 return Function(result, Any(), 0, zone); 706 } 707 static Type* Function(Type* result, Type* param0, Zone* zone) { 708 Type* function = Function(result, Any(), 1, zone); 709 function->AsFunction()->InitParameter(0, param0); 710 return function; 711 } 712 static Type* Function(Type* result, Type* param0, Type* param1, Zone* zone) { 713 Type* function = Function(result, Any(), 2, zone); 714 function->AsFunction()->InitParameter(0, param0); 715 function->AsFunction()->InitParameter(1, param1); 716 return function; 717 } 718 static Type* Function(Type* result, Type* param0, Type* param1, Type* param2, 719 Zone* zone) { 720 Type* function = Function(result, Any(), 3, zone); 721 function->AsFunction()->InitParameter(0, param0); 722 function->AsFunction()->InitParameter(1, param1); 723 function->AsFunction()->InitParameter(2, param2); 724 return function; 725 } 726 static Type* Function(Type* result, int arity, Type** params, Zone* zone) { 727 Type* function = Function(result, Any(), arity, zone); 728 for (int i = 0; i < arity; ++i) { 729 function->AsFunction()->InitParameter(i, params[i]); 730 } 731 return function; 732 } 733 static Type* Tuple(Type* first, Type* second, Type* third, Zone* zone) { 734 Type* tuple = TupleType::New(3, zone); 735 tuple->AsTuple()->InitElement(0, first); 736 tuple->AsTuple()->InitElement(1, second); 737 tuple->AsTuple()->InitElement(2, third); 738 return tuple; 739 } 740 741 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \ 742 static Type* Name(Isolate* isolate, Zone* zone); 743 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE) 744 #undef CONSTRUCT_SIMD_TYPE 745 746 static Type* Union(Type* type1, Type* type2, Zone* zone); 747 static Type* Intersect(Type* type1, Type* type2, Zone* zone); 748 749 static Type* Of(double value, Zone* zone) { 750 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); 751 } 752 static Type* Of(i::Object* value, Zone* zone) { 753 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); 754 } 755 static Type* Of(i::Handle<i::Object> value, Zone* zone) { 756 return Of(*value, zone); 757 } 758 759 // Extraction of components. 760 static Type* Representation(Type* t, Zone* zone); 761 static Type* Semantic(Type* t, Zone* zone); 762 763 // Predicates. 764 bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } 765 766 bool Is(Type* that) { return this == that || this->SlowIs(that); } 767 bool Maybe(Type* that); 768 bool Equals(Type* that) { return this->Is(that) && that->Is(this); } 769 770 // Equivalent to Constant(val)->Is(this), but avoiding allocation. 771 bool Contains(i::Object* val); 772 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } 773 774 // State-dependent versions of the above that consider subtyping between 775 // a constant and its map class. 776 static Type* NowOf(i::Object* value, Zone* zone); 777 static Type* NowOf(i::Handle<i::Object> value, Zone* zone) { 778 return NowOf(*value, zone); 779 } 780 bool NowIs(Type* that); 781 bool NowContains(i::Object* val); 782 bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } 783 784 bool NowStable(); 785 786 // Inspection. 787 bool IsRange() { return IsKind(TypeBase::kRange); } 788 bool IsClass() { return IsKind(TypeBase::kClass); } 789 bool IsConstant() { return IsKind(TypeBase::kConstant); } 790 bool IsContext() { return IsKind(TypeBase::kContext); } 791 bool IsArray() { return IsKind(TypeBase::kArray); } 792 bool IsFunction() { return IsKind(TypeBase::kFunction); } 793 bool IsTuple() { return IsKind(TypeBase::kTuple); } 794 795 ClassType* AsClass() { return ClassType::cast(this); } 796 ConstantType* AsConstant() { return ConstantType::cast(this); } 797 RangeType* AsRange() { return RangeType::cast(this); } 798 ContextType* AsContext() { return ContextType::cast(this); } 799 ArrayType* AsArray() { return ArrayType::cast(this); } 800 FunctionType* AsFunction() { return FunctionType::cast(this); } 801 TupleType* AsTuple() { return TupleType::cast(this); } 802 803 // Minimum and maximum of a numeric type. 804 // These functions do not distinguish between -0 and +0. If the type equals 805 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these 806 // functions on subtypes of Number. 807 double Min(); 808 double Max(); 809 810 // Extracts a range from the type: if the type is a range or a union 811 // containing a range, that range is returned; otherwise, NULL is returned. 812 Type* GetRange(); 813 814 static bool IsInteger(i::Object* x); 815 static bool IsInteger(double x) { 816 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. 817 } 818 819 int NumClasses(); 820 int NumConstants(); 821 822 template <class T> 823 class Iterator { 824 public: 825 bool Done() const { return index_ < 0; } 826 i::Handle<T> Current(); 827 void Advance(); 828 829 private: 830 friend class Type; 831 832 Iterator() : index_(-1) {} 833 explicit Iterator(Type* type) : type_(type), index_(-1) { Advance(); } 834 835 inline bool matches(Type* type); 836 inline Type* get_type(); 837 838 Type* type_; 839 int index_; 840 }; 841 842 Iterator<i::Map> Classes() { 843 if (this->IsBitset()) return Iterator<i::Map>(); 844 return Iterator<i::Map>(this); 845 } 846 Iterator<i::Object> Constants() { 847 if (this->IsBitset()) return Iterator<i::Object>(); 848 return Iterator<i::Object>(this); 849 } 850 851 // Printing. 852 853 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; 854 855 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT 856 857 #ifdef DEBUG 858 void Print(); 859 #endif 860 861 // Helpers for testing. 862 bool IsBitsetForTesting() { return IsBitset(); } 863 bool IsUnionForTesting() { return IsUnion(); } 864 bitset AsBitsetForTesting() { return AsBitset(); } 865 UnionType* AsUnionForTesting() { return AsUnion(); } 866 867 private: 868 // Friends. 869 template <class> 870 friend class Iterator; 871 friend BitsetType; 872 friend UnionType; 873 874 // Internal inspection. 875 bool IsKind(TypeBase::Kind kind) { return TypeBase::IsKind(this, kind); } 876 877 bool IsNone() { return this == None(); } 878 bool IsAny() { return this == Any(); } 879 bool IsBitset() { return BitsetType::IsBitset(this); } 880 bool IsUnion() { return IsKind(TypeBase::kUnion); } 881 882 bitset AsBitset() { 883 DCHECK(this->IsBitset()); 884 return reinterpret_cast<BitsetType*>(this)->Bitset(); 885 } 886 UnionType* AsUnion() { return UnionType::cast(this); } 887 888 bitset Representation(); 889 890 // Auxiliary functions. 891 bool SemanticMaybe(Type* that); 892 893 bitset BitsetGlb() { return BitsetType::Glb(this); } 894 bitset BitsetLub() { return BitsetType::Lub(this); } 895 896 bool SlowIs(Type* that); 897 bool SemanticIs(Type* that); 898 899 static bool Overlap(RangeType* lhs, RangeType* rhs); 900 static bool Contains(RangeType* lhs, RangeType* rhs); 901 static bool Contains(RangeType* range, ConstantType* constant); 902 static bool Contains(RangeType* range, i::Object* val); 903 904 static int UpdateRange(Type* type, UnionType* result, int size, Zone* zone); 905 906 static RangeType::Limits IntersectRangeAndBitset(Type* range, Type* bits, 907 Zone* zone); 908 static RangeType::Limits ToLimits(bitset bits, Zone* zone); 909 910 bool SimplyEquals(Type* that); 911 912 static int AddToUnion(Type* type, UnionType* result, int size, Zone* zone); 913 static int IntersectAux(Type* type, Type* other, UnionType* result, int size, 914 RangeType::Limits* limits, Zone* zone); 915 static Type* NormalizeUnion(Type* unioned, int size, Zone* zone); 916 static Type* NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone); 917 }; 918 919 // ----------------------------------------------------------------------------- 920 // Type bounds. A simple struct to represent a pair of lower/upper types. 921 922 struct Bounds { 923 Type* lower; 924 Type* upper; 925 926 Bounds() 927 : // Make sure accessing uninitialized bounds crashes big-time. 928 lower(nullptr), 929 upper(nullptr) {} 930 explicit Bounds(Type* t) : lower(t), upper(t) {} 931 Bounds(Type* l, Type* u) : lower(l), upper(u) { DCHECK(lower->Is(upper)); } 932 933 // Unrestricted bounds. 934 static Bounds Unbounded() { return Bounds(Type::None(), Type::Any()); } 935 936 // Meet: both b1 and b2 are known to hold. 937 static Bounds Both(Bounds b1, Bounds b2, Zone* zone) { 938 Type* lower = Type::Union(b1.lower, b2.lower, zone); 939 Type* upper = Type::Intersect(b1.upper, b2.upper, zone); 940 // Lower bounds are considered approximate, correct as necessary. 941 if (!lower->Is(upper)) lower = upper; 942 return Bounds(lower, upper); 943 } 944 945 // Join: either b1 or b2 is known to hold. 946 static Bounds Either(Bounds b1, Bounds b2, Zone* zone) { 947 Type* lower = Type::Intersect(b1.lower, b2.lower, zone); 948 Type* upper = Type::Union(b1.upper, b2.upper, zone); 949 return Bounds(lower, upper); 950 } 951 952 static Bounds NarrowLower(Bounds b, Type* t, Zone* zone) { 953 Type* lower = Type::Union(b.lower, t, zone); 954 // Lower bounds are considered approximate, correct as necessary. 955 if (!lower->Is(b.upper)) lower = b.upper; 956 return Bounds(lower, b.upper); 957 } 958 static Bounds NarrowUpper(Bounds b, Type* t, Zone* zone) { 959 Type* lower = b.lower; 960 Type* upper = Type::Intersect(b.upper, t, zone); 961 // Lower bounds are considered approximate, correct as necessary. 962 if (!lower->Is(upper)) lower = upper; 963 return Bounds(lower, upper); 964 } 965 966 bool Narrows(Bounds that) { 967 return that.lower->Is(this->lower) && this->upper->Is(that.upper); 968 } 969 }; 970 971 } // namespace internal 972 } // namespace v8 973 974 #endif // V8_TYPES_H_ 975
