Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(668)

Side by Side Diff: src/compiler/types.h

Issue 2366433003: [turbofan] Cleanup: Type only has a semantic dimension. (Closed)
Patch Set: REBASE. Created 4 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/compiler/representation-change.cc ('k') | src/compiler/types.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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_
OLDNEW
« no previous file with comments | « src/compiler/representation-change.cc ('k') | src/compiler/types.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698