| OLD | NEW |
| 1 // Copyright 2014 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef V8_TYPES_H_ | 5 #ifndef V8_TYPES_H_ |
| 6 #define V8_TYPES_H_ | 6 #define V8_TYPES_H_ |
| 7 | 7 |
| 8 #include "src/conversions.h" | 8 #include "src/conversions.h" |
| 9 #include "src/handles.h" | 9 #include "src/handles.h" |
| 10 #include "src/objects.h" | 10 #include "src/objects.h" |
| (...skipping 27 matching lines...) Expand all Loading... |
| 38 // UniqueName = InternalizedString \/ Symbol | 38 // UniqueName = InternalizedString \/ Symbol |
| 39 // InternalizedString < String | 39 // InternalizedString < String |
| 40 // | 40 // |
| 41 // Receiver = Object \/ Proxy | 41 // Receiver = Object \/ Proxy |
| 42 // Array < Object | 42 // Array < Object |
| 43 // Function < Object | 43 // Function < Object |
| 44 // RegExp < Object | 44 // RegExp < Object |
| 45 // OtherUndetectable < Object | 45 // OtherUndetectable < Object |
| 46 // DetectableReceiver = Receiver - OtherUndetectable | 46 // DetectableReceiver = Receiver - OtherUndetectable |
| 47 // | 47 // |
| 48 // Class(map) < T iff instance_type(map) < T | |
| 49 // Constant(x) < T iff instance_type(map(x)) < T | 48 // Constant(x) < T iff instance_type(map(x)) < T |
| 50 // Array(T) < Array | 49 // Array(T) < Array |
| 51 // Function(R, S, T0, T1, ...) < Function | 50 // Function(R, S, T0, T1, ...) < Function |
| 52 // Context(T) < Internal | 51 // Context(T) < Internal |
| 53 // | 52 // |
| 54 // Both structural Array and Function types are invariant in all parameters; | 53 // Both structural Array and Function types are invariant in all parameters; |
| 55 // relaxing this would make Union and Intersect operations more involved. | 54 // relaxing this would make Union and Intersect operations more involved. |
| 56 // There is no subtyping relation between Array, Function, or Context types | 55 // There is no subtyping relation between Array, Function, or Context types |
| 57 // and respective Constant types, since these types cannot be reconstructed | 56 // and respective Constant types, since these types cannot be reconstructed |
| 58 // for arbitrary heap values. | 57 // 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 // | 58 // |
| 66 // | 59 // |
| 67 // REPRESENTATIONAL DIMENSION | 60 // REPRESENTATIONAL DIMENSION |
| 68 // | 61 // |
| 69 // For the representation axis, the following holds: | 62 // For the representation axis, the following holds: |
| 70 // | 63 // |
| 71 // None <= R | 64 // None <= R |
| 72 // R <= Any | 65 // R <= Any |
| 73 // | 66 // |
| 74 // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ | 67 // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 133 // complete partial order. | 126 // complete partial order. |
| 134 // | 127 // |
| 135 // See test/cctest/test-types.cc for a comprehensive executable specification, | 128 // See test/cctest/test-types.cc for a comprehensive executable specification, |
| 136 // especially with respect to the properties of the more exotic 'temporal' | 129 // especially with respect to the properties of the more exotic 'temporal' |
| 137 // constructors and predicates (those prefixed 'Now'). | 130 // constructors and predicates (those prefixed 'Now'). |
| 138 // | 131 // |
| 139 // | 132 // |
| 140 // IMPLEMENTATION | 133 // IMPLEMENTATION |
| 141 // | 134 // |
| 142 // Internally, all 'primitive' types, and their unions, are represented as | 135 // 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 | 136 // bitsets. Bit 0 is reserved for tagging. Only structured types require |
| 144 // respective map. Only structured types require allocation. | 137 // allocation. |
| 145 // Note that the bitset representation is closed under both Union and Intersect. | 138 // Note that the bitset representation is closed under both Union and Intersect. |
| 146 | 139 |
| 147 | |
| 148 // ----------------------------------------------------------------------------- | 140 // ----------------------------------------------------------------------------- |
| 149 // Values for bitset types | 141 // Values for bitset types |
| 150 | 142 |
| 151 // clang-format off | 143 // clang-format off |
| 152 | 144 |
| 153 #define MASK_BITSET_TYPE_LIST(V) \ | 145 #define MASK_BITSET_TYPE_LIST(V) \ |
| 154 V(Representation, 0xffc00000u) \ | 146 V(Representation, 0xffc00000u) \ |
| 155 V(Semantic, 0x003ffffeu) | 147 V(Semantic, 0x003ffffeu) |
| 156 | 148 |
| 157 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) | 149 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) |
| (...skipping 191 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 349 static inline size_t BoundariesSize(); | 341 static inline size_t BoundariesSize(); |
| 350 }; | 342 }; |
| 351 | 343 |
| 352 // ----------------------------------------------------------------------------- | 344 // ----------------------------------------------------------------------------- |
| 353 // Superclass for non-bitset types (internal). | 345 // Superclass for non-bitset types (internal). |
| 354 class TypeBase { | 346 class TypeBase { |
| 355 protected: | 347 protected: |
| 356 friend class Type; | 348 friend class Type; |
| 357 | 349 |
| 358 enum Kind { | 350 enum Kind { |
| 359 kClass, | |
| 360 kConstant, | 351 kConstant, |
| 361 kContext, | 352 kContext, |
| 362 kArray, | 353 kArray, |
| 363 kFunction, | 354 kFunction, |
| 364 kTuple, | 355 kTuple, |
| 365 kUnion, | 356 kUnion, |
| 366 kRange | 357 kRange |
| 367 }; | 358 }; |
| 368 | 359 |
| 369 Kind kind() const { return kind_; } | 360 Kind kind() const { return kind_; } |
| 370 explicit TypeBase(Kind kind) : kind_(kind) {} | 361 explicit TypeBase(Kind kind) : kind_(kind) {} |
| 371 | 362 |
| 372 static bool IsKind(Type* type, Kind kind) { | 363 static bool IsKind(Type* type, Kind kind) { |
| 373 if (BitsetType::IsBitset(type)) return false; | 364 if (BitsetType::IsBitset(type)) return false; |
| 374 TypeBase* base = reinterpret_cast<TypeBase*>(type); | 365 TypeBase* base = reinterpret_cast<TypeBase*>(type); |
| 375 return base->kind() == kind; | 366 return base->kind() == kind; |
| 376 } | 367 } |
| 377 | 368 |
| 378 // The hacky conversion to/from Type*. | 369 // The hacky conversion to/from Type*. |
| 379 static Type* AsType(TypeBase* type) { return reinterpret_cast<Type*>(type); } | 370 static Type* AsType(TypeBase* type) { return reinterpret_cast<Type*>(type); } |
| 380 static TypeBase* FromType(Type* type) { | 371 static TypeBase* FromType(Type* type) { |
| 381 return reinterpret_cast<TypeBase*>(type); | 372 return reinterpret_cast<TypeBase*>(type); |
| 382 } | 373 } |
| 383 | 374 |
| 384 private: | 375 private: |
| 385 Kind kind_; | 376 Kind kind_; |
| 386 }; | 377 }; |
| 387 | 378 |
| 388 // ----------------------------------------------------------------------------- | 379 // ----------------------------------------------------------------------------- |
| 389 // Class types. | |
| 390 | |
| 391 class ClassType : public TypeBase { | |
| 392 public: | |
| 393 i::Handle<i::Map> Map() { return map_; } | |
| 394 | |
| 395 private: | |
| 396 friend class Type; | |
| 397 friend class BitsetType; | |
| 398 | |
| 399 static Type* New(i::Handle<i::Map> map, Zone* zone) { | |
| 400 return AsType(new (zone->New(sizeof(ClassType))) | |
| 401 ClassType(BitsetType::Lub(*map), map)); | |
| 402 } | |
| 403 | |
| 404 static ClassType* cast(Type* type) { | |
| 405 DCHECK(IsKind(type, kClass)); | |
| 406 return static_cast<ClassType*>(FromType(type)); | |
| 407 } | |
| 408 | |
| 409 ClassType(BitsetType::bitset bitset, i::Handle<i::Map> map) | |
| 410 : TypeBase(kClass), bitset_(bitset), map_(map) {} | |
| 411 | |
| 412 BitsetType::bitset Lub() { return bitset_; } | |
| 413 | |
| 414 BitsetType::bitset bitset_; | |
| 415 Handle<i::Map> map_; | |
| 416 }; | |
| 417 | |
| 418 // ----------------------------------------------------------------------------- | |
| 419 // Constant types. | 380 // Constant types. |
| 420 | 381 |
| 421 class ConstantType : public TypeBase { | 382 class ConstantType : public TypeBase { |
| 422 public: | 383 public: |
| 423 i::Handle<i::Object> Value() { return object_; } | 384 i::Handle<i::Object> Value() { return object_; } |
| 424 | 385 |
| 425 private: | 386 private: |
| 426 friend class Type; | 387 friend class Type; |
| 427 friend class BitsetType; | 388 friend class BitsetType; |
| 428 | 389 |
| (...skipping 253 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 682 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) | 643 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) |
| 683 #undef DEFINE_TYPE_CONSTRUCTOR | 644 #undef DEFINE_TYPE_CONSTRUCTOR |
| 684 | 645 |
| 685 static Type* SignedSmall() { | 646 static Type* SignedSmall() { |
| 686 return BitsetType::New(BitsetType::SignedSmall()); | 647 return BitsetType::New(BitsetType::SignedSmall()); |
| 687 } | 648 } |
| 688 static Type* UnsignedSmall() { | 649 static Type* UnsignedSmall() { |
| 689 return BitsetType::New(BitsetType::UnsignedSmall()); | 650 return BitsetType::New(BitsetType::UnsignedSmall()); |
| 690 } | 651 } |
| 691 | 652 |
| 692 static Type* Class(i::Handle<i::Map> map, Zone* zone) { | |
| 693 return ClassType::New(map, zone); | |
| 694 } | |
| 695 static Type* Constant(i::Handle<i::Object> value, Zone* zone) { | 653 static Type* Constant(i::Handle<i::Object> value, Zone* zone) { |
| 696 return ConstantType::New(value, zone); | 654 return ConstantType::New(value, zone); |
| 697 } | 655 } |
| 698 static Type* Range(double min, double max, Zone* zone) { | 656 static Type* Range(double min, double max, Zone* zone) { |
| 699 return RangeType::New(min, max, REPRESENTATION(BitsetType::kTagged | | 657 return RangeType::New(min, max, REPRESENTATION(BitsetType::kTagged | |
| 700 BitsetType::kUntaggedNumber), | 658 BitsetType::kUntaggedNumber), |
| 701 zone); | 659 zone); |
| 702 } | 660 } |
| 703 static Type* Context(Type* outer, Zone* zone) { | 661 static Type* Context(Type* outer, Zone* zone) { |
| 704 return ContextType::New(outer, zone); | 662 return ContextType::New(outer, zone); |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 739 return function; | 697 return function; |
| 740 } | 698 } |
| 741 static Type* Tuple(Type* first, Type* second, Type* third, Zone* zone) { | 699 static Type* Tuple(Type* first, Type* second, Type* third, Zone* zone) { |
| 742 Type* tuple = TupleType::New(3, zone); | 700 Type* tuple = TupleType::New(3, zone); |
| 743 tuple->AsTuple()->InitElement(0, first); | 701 tuple->AsTuple()->InitElement(0, first); |
| 744 tuple->AsTuple()->InitElement(1, second); | 702 tuple->AsTuple()->InitElement(1, second); |
| 745 tuple->AsTuple()->InitElement(2, third); | 703 tuple->AsTuple()->InitElement(2, third); |
| 746 return tuple; | 704 return tuple; |
| 747 } | 705 } |
| 748 | 706 |
| 749 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \ | |
| 750 static Type* Name(Isolate* isolate, Zone* zone); | |
| 751 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE) | |
| 752 #undef CONSTRUCT_SIMD_TYPE | |
| 753 | |
| 754 static Type* Union(Type* type1, Type* type2, Zone* zone); | 707 static Type* Union(Type* type1, Type* type2, Zone* zone); |
| 755 static Type* Intersect(Type* type1, Type* type2, Zone* zone); | 708 static Type* Intersect(Type* type1, Type* type2, Zone* zone); |
| 756 | 709 |
| 757 static Type* Of(double value, Zone* zone) { | 710 static Type* Of(double value, Zone* zone) { |
| 758 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); | 711 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); |
| 759 } | 712 } |
| 760 static Type* Of(i::Object* value, Zone* zone) { | 713 static Type* Of(i::Object* value, Zone* zone) { |
| 761 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); | 714 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); |
| 762 } | 715 } |
| 763 static Type* Of(i::Handle<i::Object> value, Zone* zone) { | 716 static Type* Of(i::Handle<i::Object> value, Zone* zone) { |
| (...skipping 13 matching lines...) Expand all Loading... |
| 777 bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } | 730 bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } |
| 778 | 731 |
| 779 bool Is(Type* that) { return this == that || this->SlowIs(that); } | 732 bool Is(Type* that) { return this == that || this->SlowIs(that); } |
| 780 bool Maybe(Type* that); | 733 bool Maybe(Type* that); |
| 781 bool Equals(Type* that) { return this->Is(that) && that->Is(this); } | 734 bool Equals(Type* that) { return this->Is(that) && that->Is(this); } |
| 782 | 735 |
| 783 // Equivalent to Constant(val)->Is(this), but avoiding allocation. | 736 // Equivalent to Constant(val)->Is(this), but avoiding allocation. |
| 784 bool Contains(i::Object* val); | 737 bool Contains(i::Object* val); |
| 785 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } | 738 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } |
| 786 | 739 |
| 787 // State-dependent versions of the above that consider subtyping between | |
| 788 // a constant and its map class. | |
| 789 static Type* NowOf(i::Object* value, Zone* zone); | |
| 790 static Type* NowOf(i::Handle<i::Object> value, Zone* zone) { | |
| 791 return NowOf(*value, zone); | |
| 792 } | |
| 793 bool NowIs(Type* that); | |
| 794 bool NowContains(i::Object* val); | |
| 795 bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } | |
| 796 | |
| 797 bool NowStable(); | |
| 798 | |
| 799 // Inspection. | 740 // Inspection. |
| 800 bool IsRange() { return IsKind(TypeBase::kRange); } | 741 bool IsRange() { return IsKind(TypeBase::kRange); } |
| 801 bool IsClass() { return IsKind(TypeBase::kClass); } | |
| 802 bool IsConstant() { return IsKind(TypeBase::kConstant); } | 742 bool IsConstant() { return IsKind(TypeBase::kConstant); } |
| 803 bool IsContext() { return IsKind(TypeBase::kContext); } | 743 bool IsContext() { return IsKind(TypeBase::kContext); } |
| 804 bool IsArray() { return IsKind(TypeBase::kArray); } | 744 bool IsArray() { return IsKind(TypeBase::kArray); } |
| 805 bool IsFunction() { return IsKind(TypeBase::kFunction); } | 745 bool IsFunction() { return IsKind(TypeBase::kFunction); } |
| 806 bool IsTuple() { return IsKind(TypeBase::kTuple); } | 746 bool IsTuple() { return IsKind(TypeBase::kTuple); } |
| 807 | 747 |
| 808 ClassType* AsClass() { return ClassType::cast(this); } | |
| 809 ConstantType* AsConstant() { return ConstantType::cast(this); } | 748 ConstantType* AsConstant() { return ConstantType::cast(this); } |
| 810 RangeType* AsRange() { return RangeType::cast(this); } | 749 RangeType* AsRange() { return RangeType::cast(this); } |
| 811 ContextType* AsContext() { return ContextType::cast(this); } | 750 ContextType* AsContext() { return ContextType::cast(this); } |
| 812 ArrayType* AsArray() { return ArrayType::cast(this); } | 751 ArrayType* AsArray() { return ArrayType::cast(this); } |
| 813 FunctionType* AsFunction() { return FunctionType::cast(this); } | 752 FunctionType* AsFunction() { return FunctionType::cast(this); } |
| 814 TupleType* AsTuple() { return TupleType::cast(this); } | 753 TupleType* AsTuple() { return TupleType::cast(this); } |
| 815 | 754 |
| 816 // Minimum and maximum of a numeric type. | 755 // Minimum and maximum of a numeric type. |
| 817 // These functions do not distinguish between -0 and +0. If the type equals | 756 // These functions do not distinguish between -0 and +0. If the type equals |
| 818 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these | 757 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these |
| 819 // functions on subtypes of Number. | 758 // functions on subtypes of Number. |
| 820 double Min(); | 759 double Min(); |
| 821 double Max(); | 760 double Max(); |
| 822 | 761 |
| 823 // Extracts a range from the type: if the type is a range or a union | 762 // Extracts a range from the type: if the type is a range or a union |
| 824 // containing a range, that range is returned; otherwise, NULL is returned. | 763 // containing a range, that range is returned; otherwise, NULL is returned. |
| 825 Type* GetRange(); | 764 Type* GetRange(); |
| 826 | 765 |
| 827 static bool IsInteger(i::Object* x); | 766 static bool IsInteger(i::Object* x); |
| 828 static bool IsInteger(double x) { | 767 static bool IsInteger(double x) { |
| 829 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. | 768 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. |
| 830 } | 769 } |
| 831 | 770 |
| 832 int NumClasses(); | |
| 833 int NumConstants(); | 771 int NumConstants(); |
| 834 | 772 |
| 835 template <class T> | 773 template <class T> |
| 836 class Iterator { | 774 class Iterator { |
| 837 public: | 775 public: |
| 838 bool Done() const { return index_ < 0; } | 776 bool Done() const { return index_ < 0; } |
| 839 i::Handle<T> Current(); | 777 i::Handle<T> Current(); |
| 840 void Advance(); | 778 void Advance(); |
| 841 | 779 |
| 842 private: | 780 private: |
| 843 friend class Type; | 781 friend class Type; |
| 844 | 782 |
| 845 Iterator() : index_(-1) {} | 783 Iterator() : index_(-1) {} |
| 846 explicit Iterator(Type* type) : type_(type), index_(-1) { Advance(); } | 784 explicit Iterator(Type* type) : type_(type), index_(-1) { Advance(); } |
| 847 | 785 |
| 848 inline bool matches(Type* type); | 786 inline bool matches(Type* type); |
| 849 inline Type* get_type(); | 787 inline Type* get_type(); |
| 850 | 788 |
| 851 Type* type_; | 789 Type* type_; |
| 852 int index_; | 790 int index_; |
| 853 }; | 791 }; |
| 854 | 792 |
| 855 Iterator<i::Map> Classes() { | |
| 856 if (this->IsBitset()) return Iterator<i::Map>(); | |
| 857 return Iterator<i::Map>(this); | |
| 858 } | |
| 859 Iterator<i::Object> Constants() { | 793 Iterator<i::Object> Constants() { |
| 860 if (this->IsBitset()) return Iterator<i::Object>(); | 794 if (this->IsBitset()) return Iterator<i::Object>(); |
| 861 return Iterator<i::Object>(this); | 795 return Iterator<i::Object>(this); |
| 862 } | 796 } |
| 863 | 797 |
| 864 // Printing. | 798 // Printing. |
| 865 | 799 |
| 866 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; | 800 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; |
| 867 | 801 |
| 868 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT | 802 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT |
| (...skipping 108 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 977 } | 911 } |
| 978 | 912 |
| 979 bool Narrows(Bounds that) { | 913 bool Narrows(Bounds that) { |
| 980 return that.lower->Is(this->lower) && this->upper->Is(that.upper); | 914 return that.lower->Is(this->lower) && this->upper->Is(that.upper); |
| 981 } | 915 } |
| 982 }; | 916 }; |
| 983 } // namespace internal | 917 } // namespace internal |
| 984 } // namespace v8 | 918 } // namespace v8 |
| 985 | 919 |
| 986 #endif // V8_TYPES_H_ | 920 #endif // V8_TYPES_H_ |
| OLD | NEW |