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 |