| 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 |