| 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_COMPILER_TYPES_H_ | 5 #ifndef V8_COMPILER_TYPES_H_ | 
| 6 #define V8_COMPILER_TYPES_H_ | 6 #define V8_COMPILER_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" | 
| 11 #include "src/ostreams.h" | 11 #include "src/ostreams.h" | 
| 12 | 12 | 
| 13 namespace v8 { | 13 namespace v8 { | 
| 14 namespace internal { | 14 namespace internal { | 
| 15 namespace compiler { | 15 namespace compiler { | 
| 16 | 16 | 
| 17 // SUMMARY | 17 // SUMMARY | 
| 18 // | 18 // | 
| 19 // A simple type system for compiler-internal use. It is based entirely on | 19 // A simple type system for compiler-internal use. It is based entirely on | 
| 20 // union types, and all subtyping hence amounts to set inclusion. Besides the | 20 // union types, and all subtyping hence amounts to set inclusion. Besides the | 
| 21 // obvious primitive types and some predefined unions, the type language also | 21 // obvious primitive types and some predefined unions, the type language also | 
| 22 // can express class types (a.k.a. specific maps) and singleton types (i.e., | 22 // can express class types (a.k.a. specific maps) and singleton types (i.e., | 
| 23 // concrete constants). | 23 // concrete constants). | 
| 24 // | 24 // | 
| 25 // Types consist of two dimensions: semantic (value range) and representation. | 25 // The following equations and inequations hold: | 
| 26 // Both are related through subtyping. |  | 
| 27 // |  | 
| 28 // |  | 
| 29 // SEMANTIC DIMENSION |  | 
| 30 // |  | 
| 31 // The following equations and inequations hold for the semantic axis: |  | 
| 32 // | 26 // | 
| 33 //   None <= T | 27 //   None <= T | 
| 34 //   T <= Any | 28 //   T <= Any | 
| 35 // | 29 // | 
| 36 //   Number = Signed32 \/ Unsigned32 \/ Double | 30 //   Number = Signed32 \/ Unsigned32 \/ Double | 
| 37 //   Smi <= Signed32 | 31 //   Smi <= Signed32 | 
| 38 //   Name = String \/ Symbol | 32 //   Name = String \/ Symbol | 
| 39 //   UniqueName = InternalizedString \/ Symbol | 33 //   UniqueName = InternalizedString \/ Symbol | 
| 40 //   InternalizedString < String | 34 //   InternalizedString < String | 
| 41 // | 35 // | 
| 42 //   Receiver = Object \/ Proxy | 36 //   Receiver = Object \/ Proxy | 
| 43 //   RegExp < Object |  | 
| 44 //   OtherUndetectable < Object | 37 //   OtherUndetectable < Object | 
| 45 //   DetectableReceiver = Receiver - OtherUndetectable | 38 //   DetectableReceiver = Receiver - OtherUndetectable | 
| 46 // | 39 // | 
| 47 //   Constant(x) < T  iff instance_type(map(x)) < T | 40 //   Constant(x) < T  iff instance_type(map(x)) < T | 
| 48 // | 41 // | 
| 49 // | 42 // | 
| 50 // RANGE TYPES | 43 // RANGE TYPES | 
| 51 // | 44 // | 
| 52 // A range type represents a continuous integer interval by its minimum and | 45 // A range type represents a continuous integer interval by its minimum and | 
| 53 // maximum value.  Either value may be an infinity, in which case that infinity | 46 // maximum value.  Either value may be an infinity, in which case that infinity | 
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 96 // | 89 // | 
| 97 // Internally, all 'primitive' types, and their unions, are represented as | 90 // Internally, all 'primitive' types, and their unions, are represented as | 
| 98 // bitsets. Bit 0 is reserved for tagging. Only structured types require | 91 // bitsets. Bit 0 is reserved for tagging. Only structured types require | 
| 99 // allocation. | 92 // allocation. | 
| 100 | 93 | 
| 101 // ----------------------------------------------------------------------------- | 94 // ----------------------------------------------------------------------------- | 
| 102 // Values for bitset types | 95 // Values for bitset types | 
| 103 | 96 | 
| 104 // clang-format off | 97 // clang-format off | 
| 105 | 98 | 
| 106 #define MASK_BITSET_TYPE_LIST(V) \ |  | 
| 107   V(Semantic,       0xfffffffeu) |  | 
| 108 |  | 
| 109 #define SEMANTIC(k)       ((k) & BitsetType::kSemantic) |  | 
| 110 |  | 
| 111 #define INTERNAL_BITSET_TYPE_LIST(V)                                      \ | 99 #define INTERNAL_BITSET_TYPE_LIST(V)                                      \ | 
| 112   V(OtherUnsigned31, 1u << 1)  \ | 100   V(OtherUnsigned31, 1u << 1)  \ | 
| 113   V(OtherUnsigned32, 1u << 2)  \ | 101   V(OtherUnsigned32, 1u << 2)  \ | 
| 114   V(OtherSigned32,   1u << 3)  \ | 102   V(OtherSigned32,   1u << 3)  \ | 
| 115   V(OtherNumber,     1u << 4)  \ | 103   V(OtherNumber,     1u << 4)  \ | 
| 116 | 104 | 
| 117 #define SEMANTIC_BITSET_TYPE_LIST(V) \ | 105 #define PROPER_BITSET_TYPE_LIST(V) \ | 
| 118   V(None,                0u)        \ | 106   V(None,                0u)        \ | 
| 119   V(Negative31,          1u << 5)   \ | 107   V(Negative31,          1u << 5)   \ | 
| 120   V(Null,                1u << 6)   \ | 108   V(Null,                1u << 6)   \ | 
| 121   V(Undefined,           1u << 7)   \ | 109   V(Undefined,           1u << 7)   \ | 
| 122   V(Boolean,             1u << 8)   \ | 110   V(Boolean,             1u << 8)   \ | 
| 123   V(Unsigned30,          1u << 9)   \ | 111   V(Unsigned30,          1u << 9)   \ | 
| 124   V(MinusZero,           1u << 10)  \ | 112   V(MinusZero,           1u << 10)  \ | 
| 125   V(NaN,                 1u << 11)  \ | 113   V(NaN,                 1u << 11)  \ | 
| 126   V(Symbol,              1u << 12)  \ | 114   V(Symbol,              1u << 12)  \ | 
| 127   V(InternalizedString,  1u << 13)  \ | 115   V(InternalizedString,  1u << 13)  \ | 
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 186  *     -2^31   -2^30     0      2^30    2^31    2^32 | 174  *     -2^31   -2^30     0      2^30    2^31    2^32 | 
| 187  * | 175  * | 
| 188  * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. | 176  * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. | 
| 189  * | 177  * | 
| 190  * Some of the atomic numerical bitsets are internal only (see | 178  * Some of the atomic numerical bitsets are internal only (see | 
| 191  * INTERNAL_BITSET_TYPE_LIST).  To a types user, they should only occur in | 179  * INTERNAL_BITSET_TYPE_LIST).  To a types user, they should only occur in | 
| 192  * union with certain other bitsets.  For instance, OtherNumber should only | 180  * union with certain other bitsets.  For instance, OtherNumber should only | 
| 193  * occur as part of PlainNumber. | 181  * occur as part of PlainNumber. | 
| 194  */ | 182  */ | 
| 195 | 183 | 
| 196 #define PROPER_BITSET_TYPE_LIST(V)   \ | 184 #define BITSET_TYPE_LIST(V)    \ | 
| 197   SEMANTIC_BITSET_TYPE_LIST(V) | 185   INTERNAL_BITSET_TYPE_LIST(V) \ | 
| 198 | 186   PROPER_BITSET_TYPE_LIST(V) | 
| 199 #define BITSET_TYPE_LIST(V)          \ |  | 
| 200   MASK_BITSET_TYPE_LIST(V)           \ |  | 
| 201   INTERNAL_BITSET_TYPE_LIST(V)       \ |  | 
| 202   SEMANTIC_BITSET_TYPE_LIST(V) |  | 
| 203 | 187 | 
| 204 class Type; | 188 class Type; | 
| 205 | 189 | 
| 206 // ----------------------------------------------------------------------------- | 190 // ----------------------------------------------------------------------------- | 
| 207 // Bitset types (internal). | 191 // Bitset types (internal). | 
| 208 | 192 | 
| 209 class BitsetType { | 193 class BitsetType { | 
| 210  public: | 194  public: | 
| 211   typedef uint32_t bitset;  // Internal | 195   typedef uint32_t bitset;  // Internal | 
| 212 | 196 | 
| 213   enum : uint32_t { | 197   enum : uint32_t { | 
| 214 #define DECLARE_TYPE(type, value) k##type = (value), | 198 #define DECLARE_TYPE(type, value) k##type = (value), | 
| 215     BITSET_TYPE_LIST(DECLARE_TYPE) | 199     BITSET_TYPE_LIST(DECLARE_TYPE) | 
| 216 #undef DECLARE_TYPE | 200 #undef DECLARE_TYPE | 
| 217         kUnusedEOL = 0 | 201         kUnusedEOL = 0 | 
| 218   }; | 202   }; | 
| 219 | 203 | 
| 220   static bitset SignedSmall(); | 204   static bitset SignedSmall(); | 
| 221   static bitset UnsignedSmall(); | 205   static bitset UnsignedSmall(); | 
| 222 | 206 | 
| 223   bitset Bitset() { | 207   bitset Bitset() { | 
| 224     return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); | 208     return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); | 
| 225   } | 209   } | 
| 226 | 210 | 
| 227   static bool IsInhabited(bitset bits) { return SemanticIsInhabited(bits); } | 211   static bool IsInhabited(bitset bits) { return bits != kNone; } | 
| 228 |  | 
| 229   static bool SemanticIsInhabited(bitset bits) { |  | 
| 230     return SEMANTIC(bits) != kNone; |  | 
| 231   } |  | 
| 232 | 212 | 
| 233   static bool Is(bitset bits1, bitset bits2) { | 213   static bool Is(bitset bits1, bitset bits2) { | 
| 234     return (bits1 | bits2) == bits2; | 214     return (bits1 | bits2) == bits2; | 
| 235   } | 215   } | 
| 236 | 216 | 
| 237   static double Min(bitset); | 217   static double Min(bitset); | 
| 238   static double Max(bitset); | 218   static double Max(bitset); | 
| 239 | 219 | 
| 240   static bitset Glb(Type* type);  // greatest lower bound that's a bitset | 220   static bitset Glb(Type* type);  // greatest lower bound that's a bitset | 
| 241   static bitset Glb(double min, double max); | 221   static bitset Glb(double min, double max); | 
| (...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 364     return New(Limits(min, max), zone); | 344     return New(Limits(min, max), zone); | 
| 365   } | 345   } | 
| 366 | 346 | 
| 367   static bool IsInteger(double x) { | 347   static bool IsInteger(double x) { | 
| 368     return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities. | 348     return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities. | 
| 369   } | 349   } | 
| 370 | 350 | 
| 371   static Type* New(Limits lim, Zone* zone) { | 351   static Type* New(Limits lim, Zone* zone) { | 
| 372     DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); | 352     DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); | 
| 373     DCHECK(lim.min <= lim.max); | 353     DCHECK(lim.min <= lim.max); | 
| 374     BitsetType::bitset bits = SEMANTIC(BitsetType::Lub(lim.min, lim.max)); | 354     BitsetType::bitset bits = BitsetType::Lub(lim.min, lim.max); | 
| 375 | 355 | 
| 376     return AsType(new (zone->New(sizeof(RangeType))) RangeType(bits, lim)); | 356     return AsType(new (zone->New(sizeof(RangeType))) RangeType(bits, lim)); | 
| 377   } | 357   } | 
| 378 | 358 | 
| 379   static RangeType* cast(Type* type) { | 359   static RangeType* cast(Type* type) { | 
| 380     DCHECK(IsKind(type, kRange)); | 360     DCHECK(IsKind(type, kRange)); | 
| 381     return static_cast<RangeType*>(FromType(type)); | 361     return static_cast<RangeType*>(FromType(type)); | 
| 382   } | 362   } | 
| 383 | 363 | 
| 384   RangeType(BitsetType::bitset bitset, Limits limits) | 364   RangeType(BitsetType::bitset bitset, Limits limits) | 
| (...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 519   } | 499   } | 
| 520   static Type* Of(i::Handle<i::Object> value, Zone* zone) { | 500   static Type* Of(i::Handle<i::Object> value, Zone* zone) { | 
| 521     return Of(*value, zone); | 501     return Of(*value, zone); | 
| 522   } | 502   } | 
| 523 | 503 | 
| 524   static Type* For(i::Map* map) { | 504   static Type* For(i::Map* map) { | 
| 525     return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(map))); | 505     return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(map))); | 
| 526   } | 506   } | 
| 527   static Type* For(i::Handle<i::Map> map) { return For(*map); } | 507   static Type* For(i::Handle<i::Map> map) { return For(*map); } | 
| 528 | 508 | 
| 529   // Extraction of components. |  | 
| 530   static Type* Semantic(Type* t, Zone* zone); |  | 
| 531 |  | 
| 532   // Predicates. | 509   // Predicates. | 
| 533   bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } | 510   bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } | 
| 534 | 511 | 
| 535   bool Is(Type* that) { return this == that || this->SlowIs(that); } | 512   bool Is(Type* that) { return this == that || this->SlowIs(that); } | 
| 536   bool Maybe(Type* that); | 513   bool Maybe(Type* that); | 
| 537   bool Equals(Type* that) { return this->Is(that) && that->Is(this); } | 514   bool Equals(Type* that) { return this->Is(that) && that->Is(this); } | 
| 538 | 515 | 
| 539   // Equivalent to Constant(val)->Is(this), but avoiding allocation. | 516   // Equivalent to Constant(val)->Is(this), but avoiding allocation. | 
| 540   bool Contains(i::Object* val); | 517   bool Contains(i::Object* val); | 
| 541   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } | 518   bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } | 
| (...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 620   bool IsAny() { return this == Any(); } | 597   bool IsAny() { return this == Any(); } | 
| 621   bool IsBitset() { return BitsetType::IsBitset(this); } | 598   bool IsBitset() { return BitsetType::IsBitset(this); } | 
| 622   bool IsUnion() { return IsKind(TypeBase::kUnion); } | 599   bool IsUnion() { return IsKind(TypeBase::kUnion); } | 
| 623 | 600 | 
| 624   bitset AsBitset() { | 601   bitset AsBitset() { | 
| 625     DCHECK(this->IsBitset()); | 602     DCHECK(this->IsBitset()); | 
| 626     return reinterpret_cast<BitsetType*>(this)->Bitset(); | 603     return reinterpret_cast<BitsetType*>(this)->Bitset(); | 
| 627   } | 604   } | 
| 628   UnionType* AsUnion() { return UnionType::cast(this); } | 605   UnionType* AsUnion() { return UnionType::cast(this); } | 
| 629 | 606 | 
| 630   // Auxiliary functions. |  | 
| 631   bool SemanticMaybe(Type* that); |  | 
| 632 |  | 
| 633   bitset BitsetGlb() { return BitsetType::Glb(this); } | 607   bitset BitsetGlb() { return BitsetType::Glb(this); } | 
| 634   bitset BitsetLub() { return BitsetType::Lub(this); } | 608   bitset BitsetLub() { return BitsetType::Lub(this); } | 
| 635 | 609 | 
| 636   bool SlowIs(Type* that); | 610   bool SlowIs(Type* that); | 
| 637   bool SemanticIs(Type* that); |  | 
| 638 | 611 | 
| 639   static bool Overlap(RangeType* lhs, RangeType* rhs); | 612   static bool Overlap(RangeType* lhs, RangeType* rhs); | 
| 640   static bool Contains(RangeType* lhs, RangeType* rhs); | 613   static bool Contains(RangeType* lhs, RangeType* rhs); | 
| 641   static bool Contains(RangeType* range, ConstantType* constant); | 614   static bool Contains(RangeType* range, ConstantType* constant); | 
| 642   static bool Contains(RangeType* range, i::Object* val); | 615   static bool Contains(RangeType* range, i::Object* val); | 
| 643 | 616 | 
| 644   static int UpdateRange(Type* type, UnionType* result, int size, Zone* zone); | 617   static int UpdateRange(Type* type, UnionType* result, int size, Zone* zone); | 
| 645 | 618 | 
| 646   static RangeType::Limits IntersectRangeAndBitset(Type* range, Type* bits, | 619   static RangeType::Limits IntersectRangeAndBitset(Type* range, Type* bits, | 
| 647                                                    Zone* zone); | 620                                                    Zone* zone); | 
| 648   static RangeType::Limits ToLimits(bitset bits, Zone* zone); | 621   static RangeType::Limits ToLimits(bitset bits, Zone* zone); | 
| 649 | 622 | 
| 650   bool SimplyEquals(Type* that); | 623   bool SimplyEquals(Type* that); | 
| 651 | 624 | 
| 652   static int AddToUnion(Type* type, UnionType* result, int size, Zone* zone); | 625   static int AddToUnion(Type* type, UnionType* result, int size, Zone* zone); | 
| 653   static int IntersectAux(Type* type, Type* other, UnionType* result, int size, | 626   static int IntersectAux(Type* type, Type* other, UnionType* result, int size, | 
| 654                           RangeType::Limits* limits, Zone* zone); | 627                           RangeType::Limits* limits, Zone* zone); | 
| 655   static Type* NormalizeUnion(Type* unioned, int size, Zone* zone); | 628   static Type* NormalizeUnion(Type* unioned, int size, Zone* zone); | 
| 656   static Type* NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone); | 629   static Type* NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone); | 
| 657 }; | 630 }; | 
| 658 | 631 | 
| 659 }  // namespace compiler | 632 }  // namespace compiler | 
| 660 }  // namespace internal | 633 }  // namespace internal | 
| 661 }  // namespace v8 | 634 }  // namespace v8 | 
| 662 | 635 | 
| 663 #endif  // V8_COMPILER_TYPES_H_ | 636 #endif  // V8_COMPILER_TYPES_H_ | 
| OLD | NEW | 
|---|