Line data Source code
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
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_AST_AST_TYPES_H_
6 : #define V8_AST_AST_TYPES_H_
7 :
8 : #include "src/conversions.h"
9 : #include "src/handles.h"
10 : #include "src/objects.h"
11 : #include "src/ostreams.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 : // SUMMARY
17 : //
18 : // A simple type system for compiler-internal use. It is based entirely on
19 : // union types, and all subtyping hence amounts to set inclusion. Besides the
20 : // obvious primitive types and some predefined unions, the type language also
21 : // can express class types (a.k.a. specific maps) and singleton types (i.e.,
22 : // concrete constants).
23 : //
24 : // Types consist of two dimensions: semantic (value range) and representation.
25 : // Both are related through subtyping.
26 : //
27 : //
28 : // SEMANTIC DIMENSION
29 : //
30 : // The following equations and inequations hold for the semantic axis:
31 : //
32 : // None <= T
33 : // T <= Any
34 : //
35 : // Number = Signed32 \/ Unsigned32 \/ Double
36 : // Smi <= Signed32
37 : // Name = String \/ Symbol
38 : // UniqueName = InternalizedString \/ Symbol
39 : // InternalizedString < String
40 : //
41 : // Receiver = Object \/ Proxy
42 : // Array < Object
43 : // Function < Object
44 : // RegExp < Object
45 : // OtherUndetectable < Object
46 : // DetectableReceiver = Receiver - OtherUndetectable
47 : //
48 : // Class(map) < T iff instance_type(map) < T
49 : // Constant(x) < T iff instance_type(map(x)) < T
50 : // Array(T) < Array
51 : // Function(R, S, T0, T1, ...) < Function
52 : // Context(T) < Internal
53 : //
54 : // Both structural Array and Function types are invariant in all parameters;
55 : // relaxing this would make Union and Intersect operations more involved.
56 : // There is no subtyping relation between Array, Function, or Context types
57 : // and respective Constant types, since these types cannot be reconstructed
58 : // 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 : //
66 : //
67 : // REPRESENTATIONAL DIMENSION
68 : //
69 : // For the representation axis, the following holds:
70 : //
71 : // None <= R
72 : // R <= Any
73 : //
74 : // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/
75 : // UntaggedInt16 \/ UntaggedInt32
76 : // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64
77 : // UntaggedNumber = UntaggedInt \/ UntaggedFloat
78 : // Untagged = UntaggedNumber \/ UntaggedPtr
79 : // Tagged = TaggedInt \/ TaggedPtr
80 : //
81 : // Subtyping relates the two dimensions, for example:
82 : //
83 : // Number <= Tagged \/ UntaggedNumber
84 : // Object <= TaggedPtr \/ UntaggedPtr
85 : //
86 : // That holds because the semantic type constructors defined by the API create
87 : // types that allow for all possible representations, and dually, the ones for
88 : // representation types initially include all semantic ranges. Representations
89 : // can then e.g. be narrowed for a given semantic type using intersection:
90 : //
91 : // SignedSmall /\ TaggedInt (a 'smi')
92 : // Number /\ TaggedPtr (a heap number)
93 : //
94 : //
95 : // RANGE TYPES
96 : //
97 : // A range type represents a continuous integer interval by its minimum and
98 : // maximum value. Either value may be an infinity, in which case that infinity
99 : // itself is also included in the range. A range never contains NaN or -0.
100 : //
101 : // If a value v happens to be an integer n, then Constant(v) is considered a
102 : // subtype of Range(n, n) (and therefore also a subtype of any larger range).
103 : // In order to avoid large unions, however, it is usually a good idea to use
104 : // Range rather than Constant.
105 : //
106 : //
107 : // PREDICATES
108 : //
109 : // There are two main functions for testing types:
110 : //
111 : // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2)
112 : // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0)
113 : //
114 : // Typically, the former is to be used to select representations (e.g., via
115 : // T->Is(SignedSmall())), and the latter to check whether a specific case needs
116 : // handling (e.g., via T->Maybe(Number())).
117 : //
118 : // There is no functionality to discover whether a type is a leaf in the
119 : // lattice. That is intentional. It should always be possible to refine the
120 : // lattice (e.g., splitting up number types further) without invalidating any
121 : // existing assumptions or tests.
122 : // Consequently, do not normally use Equals for type tests, always use Is!
123 : //
124 : // The NowIs operator implements state-sensitive subtying, as described above.
125 : // Any compilation decision based on such temporary properties requires runtime
126 : // guarding!
127 : //
128 : //
129 : // PROPERTIES
130 : //
131 : // Various formal properties hold for constructors, operators, and predicates
132 : // over types. For example, constructors are injective and subtyping is a
133 : // complete partial order.
134 : //
135 : // See test/cctest/test-types.cc for a comprehensive executable specification,
136 : // especially with respect to the properties of the more exotic 'temporal'
137 : // constructors and predicates (those prefixed 'Now').
138 : //
139 : //
140 : // IMPLEMENTATION
141 : //
142 : // 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
144 : // respective map. Only structured types require allocation.
145 : // Note that the bitset representation is closed under both Union and Intersect.
146 :
147 : // -----------------------------------------------------------------------------
148 : // Values for bitset types
149 :
150 : // clang-format off
151 :
152 : #define AST_MASK_BITSET_TYPE_LIST(V) \
153 : V(Representation, 0xffc00000u) \
154 : V(Semantic, 0x003ffffeu)
155 :
156 : #define AST_REPRESENTATION(k) ((k) & AstBitsetType::kRepresentation)
157 : #define AST_SEMANTIC(k) ((k) & AstBitsetType::kSemantic)
158 :
159 : // Bits 21-22 are available.
160 : #define AST_REPRESENTATION_BITSET_TYPE_LIST(V) \
161 : V(None, 0) \
162 : V(UntaggedBit, 1u << 23 | kSemantic) \
163 : V(UntaggedIntegral8, 1u << 24 | kSemantic) \
164 : V(UntaggedIntegral16, 1u << 25 | kSemantic) \
165 : V(UntaggedIntegral32, 1u << 26 | kSemantic) \
166 : V(UntaggedFloat32, 1u << 27 | kSemantic) \
167 : V(UntaggedFloat64, 1u << 28 | kSemantic) \
168 : V(UntaggedPointer, 1u << 29 | kSemantic) \
169 : V(TaggedSigned, 1u << 30 | kSemantic) \
170 : V(TaggedPointer, 1u << 31 | kSemantic) \
171 : \
172 : V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \
173 : kUntaggedIntegral16 | kUntaggedIntegral32) \
174 : V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \
175 : V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \
176 : V(Untagged, kUntaggedNumber | kUntaggedPointer) \
177 : V(Tagged, kTaggedSigned | kTaggedPointer)
178 :
179 : #define AST_INTERNAL_BITSET_TYPE_LIST(V) \
180 : V(OtherUnsigned31, 1u << 1 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
181 : V(OtherUnsigned32, 1u << 2 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
182 : V(OtherSigned32, 1u << 3 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
183 : V(OtherNumber, 1u << 4 | AST_REPRESENTATION(kTagged | kUntaggedNumber))
184 :
185 : #define AST_SEMANTIC_BITSET_TYPE_LIST(V) \
186 : V(Negative31, 1u << 5 | \
187 : AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
188 : V(Null, 1u << 6 | AST_REPRESENTATION(kTaggedPointer)) \
189 : V(Undefined, 1u << 7 | AST_REPRESENTATION(kTaggedPointer)) \
190 : V(Boolean, 1u << 8 | AST_REPRESENTATION(kTaggedPointer)) \
191 : V(Unsigned30, 1u << 9 | \
192 : AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
193 : V(MinusZero, 1u << 10 | \
194 : AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
195 : V(NaN, 1u << 11 | \
196 : AST_REPRESENTATION(kTagged | kUntaggedNumber)) \
197 : V(Symbol, 1u << 12 | AST_REPRESENTATION(kTaggedPointer)) \
198 : V(InternalizedString, 1u << 13 | AST_REPRESENTATION(kTaggedPointer)) \
199 : V(OtherString, 1u << 14 | AST_REPRESENTATION(kTaggedPointer)) \
200 : V(OtherObject, 1u << 15 | AST_REPRESENTATION(kTaggedPointer)) \
201 : V(OtherUndetectable, 1u << 16 | AST_REPRESENTATION(kTaggedPointer)) \
202 : V(Proxy, 1u << 17 | AST_REPRESENTATION(kTaggedPointer)) \
203 : V(Function, 1u << 18 | AST_REPRESENTATION(kTaggedPointer)) \
204 : V(Hole, 1u << 19 | AST_REPRESENTATION(kTaggedPointer)) \
205 : V(OtherInternal, 1u << 20 | \
206 : AST_REPRESENTATION(kTagged | kUntagged)) \
207 : \
208 : V(Signed31, kUnsigned30 | kNegative31) \
209 : V(Signed32, kSigned31 | kOtherUnsigned31 | \
210 : kOtherSigned32) \
211 : V(Signed32OrMinusZero, kSigned32 | kMinusZero) \
212 : V(Signed32OrMinusZeroOrNaN, kSigned32 | kMinusZero | kNaN) \
213 : V(Negative32, kNegative31 | kOtherSigned32) \
214 : V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \
215 : V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \
216 : kOtherUnsigned32) \
217 : V(Unsigned32OrMinusZero, kUnsigned32 | kMinusZero) \
218 : V(Unsigned32OrMinusZeroOrNaN, kUnsigned32 | kMinusZero | kNaN) \
219 : V(Integral32, kSigned32 | kUnsigned32) \
220 : V(PlainNumber, kIntegral32 | kOtherNumber) \
221 : V(OrderedNumber, kPlainNumber | kMinusZero) \
222 : V(MinusZeroOrNaN, kMinusZero | kNaN) \
223 : V(Number, kOrderedNumber | kNaN) \
224 : V(String, kInternalizedString | kOtherString) \
225 : V(UniqueName, kSymbol | kInternalizedString) \
226 : V(Name, kSymbol | kString) \
227 : V(BooleanOrNumber, kBoolean | kNumber) \
228 : V(BooleanOrNullOrNumber, kBooleanOrNumber | kNull) \
229 : V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \
230 : V(NullOrNumber, kNull | kNumber) \
231 : V(NullOrUndefined, kNull | kUndefined) \
232 : V(Undetectable, kNullOrUndefined | kOtherUndetectable) \
233 : V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean | kHole) \
234 : V(NumberOrString, kNumber | kString) \
235 : V(NumberOrUndefined, kNumber | kUndefined) \
236 : V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \
237 : V(Primitive, kSymbol | kPlainPrimitive) \
238 : V(DetectableReceiver, kFunction | kOtherObject | kProxy) \
239 : V(Object, kFunction | kOtherObject | kOtherUndetectable) \
240 : V(Receiver, kObject | kProxy) \
241 : V(StringOrReceiver, kString | kReceiver) \
242 : V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \
243 : kReceiver) \
244 : V(Internal, kHole | kOtherInternal) \
245 : V(NonInternal, kPrimitive | kReceiver) \
246 : V(NonNumber, kUnique | kString | kInternal) \
247 : V(Any, 0xfffffffeu)
248 :
249 : // clang-format on
250 :
251 : /*
252 : * The following diagrams show how integers (in the mathematical sense) are
253 : * divided among the different atomic numerical types.
254 : *
255 : * ON OS32 N31 U30 OU31 OU32 ON
256 : * ______[_______[_______[_______[_______[_______[_______
257 : * -2^31 -2^30 0 2^30 2^31 2^32
258 : *
259 : * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1.
260 : *
261 : * Some of the atomic numerical bitsets are internal only (see
262 : * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in
263 : * union with certain other bitsets. For instance, OtherNumber should only
264 : * occur as part of PlainNumber.
265 : */
266 :
267 : #define AST_PROPER_BITSET_TYPE_LIST(V) \
268 : AST_REPRESENTATION_BITSET_TYPE_LIST(V) \
269 : AST_SEMANTIC_BITSET_TYPE_LIST(V)
270 :
271 : #define AST_BITSET_TYPE_LIST(V) \
272 : AST_MASK_BITSET_TYPE_LIST(V) \
273 : AST_REPRESENTATION_BITSET_TYPE_LIST(V) \
274 : AST_INTERNAL_BITSET_TYPE_LIST(V) \
275 : AST_SEMANTIC_BITSET_TYPE_LIST(V)
276 :
277 : class AstType;
278 :
279 : // -----------------------------------------------------------------------------
280 : // Bitset types (internal).
281 :
282 : class AstBitsetType {
283 : public:
284 : typedef uint32_t bitset; // Internal
285 :
286 : enum : uint32_t {
287 : #define DECLARE_TYPE(type, value) k##type = (value),
288 : AST_BITSET_TYPE_LIST(DECLARE_TYPE)
289 : #undef DECLARE_TYPE
290 : kUnusedEOL = 0
291 : };
292 :
293 : static bitset SignedSmall();
294 : static bitset UnsignedSmall();
295 :
296 : bitset Bitset() {
297 72547997 : return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u);
298 : }
299 :
300 : static bool IsInhabited(bitset bits) {
301 2739709 : return AST_SEMANTIC(bits) != kNone && AST_REPRESENTATION(bits) != kNone;
302 : }
303 :
304 : static bool SemanticIsInhabited(bitset bits) {
305 804342 : return AST_SEMANTIC(bits) != kNone;
306 : }
307 :
308 : static bool Is(bitset bits1, bitset bits2) {
309 28890728 : return (bits1 | bits2) == bits2;
310 : }
311 :
312 : static double Min(bitset);
313 : static double Max(bitset);
314 :
315 : static bitset Glb(AstType* type); // greatest lower bound that's a bitset
316 : static bitset Glb(double min, double max);
317 : static bitset Lub(AstType* type); // least upper bound that's a bitset
318 : static bitset Lub(i::Map* map);
319 : static bitset Lub(i::Object* value);
320 : static bitset Lub(double value);
321 : static bitset Lub(double min, double max);
322 : static bitset ExpandInternals(bitset bits);
323 :
324 : static const char* Name(bitset);
325 : static void Print(std::ostream& os, bitset); // NOLINT
326 : #ifdef DEBUG
327 : static void Print(bitset);
328 : #endif
329 :
330 : static bitset NumberBits(bitset bits);
331 :
332 : static bool IsBitset(AstType* type) {
333 137880467 : return reinterpret_cast<uintptr_t>(type) & 1;
334 : }
335 :
336 : static AstType* NewForTesting(bitset bits) { return New(bits); }
337 :
338 : private:
339 : friend class AstType;
340 :
341 : static AstType* New(bitset bits) {
342 22526271 : return reinterpret_cast<AstType*>(static_cast<uintptr_t>(bits | 1u));
343 : }
344 :
345 : struct Boundary {
346 : bitset internal;
347 : bitset external;
348 : double min;
349 : };
350 : static const Boundary BoundariesArray[];
351 : static inline const Boundary* Boundaries();
352 : static inline size_t BoundariesSize();
353 : };
354 :
355 : // -----------------------------------------------------------------------------
356 : // Superclass for non-bitset types (internal).
357 : class AstTypeBase {
358 : protected:
359 : friend class AstType;
360 :
361 : enum Kind {
362 : kClass,
363 : kConstant,
364 : kContext,
365 : kArray,
366 : kFunction,
367 : kTuple,
368 : kUnion,
369 : kRange
370 : };
371 :
372 71863539 : Kind kind() const { return kind_; }
373 3562572 : explicit AstTypeBase(Kind kind) : kind_(kind) {}
374 :
375 : static bool IsKind(AstType* type, Kind kind) {
376 75882431 : if (AstBitsetType::IsBitset(type)) return false;
377 : AstTypeBase* base = reinterpret_cast<AstTypeBase*>(type);
378 71863539 : return base->kind() == kind;
379 : }
380 :
381 : // The hacky conversion to/from AstType*.
382 : static AstType* AsType(AstTypeBase* type) {
383 : return reinterpret_cast<AstType*>(type);
384 : }
385 : static AstTypeBase* FromType(AstType* type) {
386 : return reinterpret_cast<AstTypeBase*>(type);
387 : }
388 :
389 : private:
390 : Kind kind_;
391 : };
392 :
393 : // -----------------------------------------------------------------------------
394 : // Class types.
395 :
396 : class AstClassType : public AstTypeBase {
397 : public:
398 : i::Handle<i::Map> Map() { return map_; }
399 :
400 : private:
401 : friend class AstType;
402 : friend class AstBitsetType;
403 :
404 19502 : static AstType* New(i::Handle<i::Map> map, Zone* zone) {
405 : return AsType(new (zone->New(sizeof(AstClassType)))
406 39004 : AstClassType(AstBitsetType::Lub(*map), map));
407 : }
408 :
409 : static AstClassType* cast(AstType* type) {
410 : DCHECK(IsKind(type, kClass));
411 : return static_cast<AstClassType*>(FromType(type));
412 : }
413 :
414 : AstClassType(AstBitsetType::bitset bitset, i::Handle<i::Map> map)
415 19502 : : AstTypeBase(kClass), bitset_(bitset), map_(map) {}
416 :
417 : AstBitsetType::bitset Lub() { return bitset_; }
418 :
419 : AstBitsetType::bitset bitset_;
420 : Handle<i::Map> map_;
421 : };
422 :
423 : // -----------------------------------------------------------------------------
424 : // Constant types.
425 :
426 : class AstConstantType : public AstTypeBase {
427 : public:
428 : i::Handle<i::Object> Value() { return object_; }
429 :
430 : private:
431 : friend class AstType;
432 : friend class AstBitsetType;
433 :
434 2779361 : static AstType* New(i::Handle<i::Object> value, Zone* zone) {
435 2779361 : AstBitsetType::bitset bitset = AstBitsetType::Lub(*value);
436 : return AsType(new (zone->New(sizeof(AstConstantType)))
437 5558722 : AstConstantType(bitset, value));
438 : }
439 :
440 : static AstConstantType* cast(AstType* type) {
441 : DCHECK(IsKind(type, kConstant));
442 : return static_cast<AstConstantType*>(FromType(type));
443 : }
444 :
445 : AstConstantType(AstBitsetType::bitset bitset, i::Handle<i::Object> object)
446 2779361 : : AstTypeBase(kConstant), bitset_(bitset), object_(object) {}
447 :
448 : AstBitsetType::bitset Lub() { return bitset_; }
449 :
450 : AstBitsetType::bitset bitset_;
451 : Handle<i::Object> object_;
452 : };
453 : // TODO(neis): Also cache value if numerical.
454 : // TODO(neis): Allow restricting the representation.
455 :
456 : // -----------------------------------------------------------------------------
457 : // Range types.
458 :
459 : class AstRangeType : public AstTypeBase {
460 : public:
461 : struct Limits {
462 : double min;
463 : double max;
464 108 : Limits(double min, double max) : min(min), max(max) {}
465 27 : explicit Limits(AstRangeType* range)
466 : : min(range->Min()), max(range->Max()) {}
467 : bool IsEmpty();
468 : static Limits Empty() { return Limits(1, 0); }
469 : static Limits Intersect(Limits lhs, Limits rhs);
470 : static Limits Union(Limits lhs, Limits rhs);
471 : };
472 :
473 : double Min() { return limits_.min; }
474 : double Max() { return limits_.max; }
475 :
476 : private:
477 : friend class AstType;
478 : friend class AstBitsetType;
479 : friend class AstUnionType;
480 :
481 : static AstType* New(double min, double max,
482 : AstBitsetType::bitset representation, Zone* zone) {
483 108 : return New(Limits(min, max), representation, zone);
484 : }
485 :
486 : static bool IsInteger(double x) {
487 : return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities.
488 : }
489 :
490 135 : static AstType* New(Limits lim, AstBitsetType::bitset representation,
491 : Zone* zone) {
492 : DCHECK(IsInteger(lim.min) && IsInteger(lim.max));
493 : DCHECK(lim.min <= lim.max);
494 : DCHECK(AST_REPRESENTATION(representation) == representation);
495 : AstBitsetType::bitset bits =
496 135 : AST_SEMANTIC(AstBitsetType::Lub(lim.min, lim.max)) | representation;
497 :
498 : return AsType(new (zone->New(sizeof(AstRangeType)))
499 270 : AstRangeType(bits, lim));
500 : }
501 :
502 : static AstRangeType* cast(AstType* type) {
503 : DCHECK(IsKind(type, kRange));
504 : return static_cast<AstRangeType*>(FromType(type));
505 : }
506 :
507 : AstRangeType(AstBitsetType::bitset bitset, Limits limits)
508 135 : : AstTypeBase(kRange), bitset_(bitset), limits_(limits) {}
509 :
510 : AstBitsetType::bitset Lub() { return bitset_; }
511 :
512 : AstBitsetType::bitset bitset_;
513 : Limits limits_;
514 : };
515 :
516 : // -----------------------------------------------------------------------------
517 : // Context types.
518 :
519 : class AstContextType : public AstTypeBase {
520 : public:
521 : AstType* Outer() { return outer_; }
522 :
523 : private:
524 : friend class AstType;
525 :
526 : static AstType* New(AstType* outer, Zone* zone) {
527 : return AsType(new (zone->New(sizeof(AstContextType)))
528 : AstContextType(outer)); // NOLINT
529 : }
530 :
531 : static AstContextType* cast(AstType* type) {
532 : DCHECK(IsKind(type, kContext));
533 : return static_cast<AstContextType*>(FromType(type));
534 : }
535 :
536 : explicit AstContextType(AstType* outer)
537 : : AstTypeBase(kContext), outer_(outer) {}
538 :
539 : AstType* outer_;
540 : };
541 :
542 : // -----------------------------------------------------------------------------
543 : // Array types.
544 :
545 : class AstArrayType : public AstTypeBase {
546 : public:
547 : AstType* Element() { return element_; }
548 :
549 : private:
550 : friend class AstType;
551 :
552 : explicit AstArrayType(AstType* element)
553 : : AstTypeBase(kArray), element_(element) {}
554 :
555 : static AstType* New(AstType* element, Zone* zone) {
556 : return AsType(new (zone->New(sizeof(AstArrayType))) AstArrayType(element));
557 : }
558 :
559 : static AstArrayType* cast(AstType* type) {
560 : DCHECK(IsKind(type, kArray));
561 : return static_cast<AstArrayType*>(FromType(type));
562 : }
563 :
564 : AstType* element_;
565 : };
566 :
567 : // -----------------------------------------------------------------------------
568 : // Superclass for types with variable number of type fields.
569 : class AstStructuralType : public AstTypeBase {
570 : public:
571 : int LengthForTesting() { return Length(); }
572 :
573 : protected:
574 : friend class AstType;
575 :
576 : int Length() { return length_; }
577 :
578 : AstType* Get(int i) {
579 : DCHECK(0 <= i && i < this->Length());
580 6920214 : return elements_[i];
581 : }
582 :
583 : void Set(int i, AstType* type) {
584 : DCHECK(0 <= i && i < this->Length());
585 1171261 : elements_[i] = type;
586 : }
587 :
588 : void Shrink(int length) {
589 : DCHECK(2 <= length && length <= this->Length());
590 241731 : length_ = length;
591 : }
592 :
593 : AstStructuralType(Kind kind, int length, i::Zone* zone)
594 763574 : : AstTypeBase(kind), length_(length) {
595 : elements_ =
596 763574 : reinterpret_cast<AstType**>(zone->New(sizeof(AstType*) * length));
597 : }
598 :
599 : private:
600 : int length_;
601 : AstType** elements_;
602 : };
603 :
604 : // -----------------------------------------------------------------------------
605 : // Function types.
606 :
607 : class AstFunctionType : public AstStructuralType {
608 : public:
609 94880 : int Arity() { return this->Length() - 2; }
610 111310 : AstType* Result() { return this->Get(0); }
611 65984 : AstType* Receiver() { return this->Get(1); }
612 65620 : AstType* Parameter(int i) { return this->Get(2 + i); }
613 :
614 : void InitParameter(int i, AstType* type) { this->Set(2 + i, type); }
615 :
616 : private:
617 : friend class AstType;
618 :
619 : AstFunctionType(AstType* result, AstType* receiver, int arity, Zone* zone)
620 : : AstStructuralType(kFunction, 2 + arity, zone) {
621 : Set(0, result);
622 : Set(1, receiver);
623 : }
624 :
625 : static AstType* New(AstType* result, AstType* receiver, int arity,
626 : Zone* zone) {
627 : return AsType(new (zone->New(sizeof(AstFunctionType)))
628 : AstFunctionType(result, receiver, arity, zone));
629 : }
630 :
631 : static AstFunctionType* cast(AstType* type) {
632 : DCHECK(IsKind(type, kFunction));
633 : return static_cast<AstFunctionType*>(FromType(type));
634 : }
635 : };
636 :
637 : // -----------------------------------------------------------------------------
638 : // Tuple types.
639 :
640 : class AstTupleType : public AstStructuralType {
641 : public:
642 0 : int Arity() { return this->Length(); }
643 0 : AstType* Element(int i) { return this->Get(i); }
644 :
645 : void InitElement(int i, AstType* type) { this->Set(i, type); }
646 :
647 : private:
648 : friend class AstType;
649 :
650 : AstTupleType(int length, Zone* zone)
651 : : AstStructuralType(kTuple, length, zone) {}
652 :
653 : static AstType* New(int length, Zone* zone) {
654 : return AsType(new (zone->New(sizeof(AstTupleType)))
655 : AstTupleType(length, zone));
656 : }
657 :
658 : static AstTupleType* cast(AstType* type) {
659 : DCHECK(IsKind(type, kTuple));
660 : return static_cast<AstTupleType*>(FromType(type));
661 : }
662 : };
663 :
664 : // -----------------------------------------------------------------------------
665 : // Union types (internal).
666 : // A union is a structured type with the following invariants:
667 : // - its length is at least 2
668 : // - at most one field is a bitset, and it must go into index 0
669 : // - no field is a union
670 : // - no field is a subtype of any other field
671 : class AstUnionType : public AstStructuralType {
672 : private:
673 : friend AstType;
674 : friend AstBitsetType;
675 :
676 : AstUnionType(int length, Zone* zone)
677 : : AstStructuralType(kUnion, length, zone) {}
678 :
679 763574 : static AstType* New(int length, Zone* zone) {
680 : return AsType(new (zone->New(sizeof(AstUnionType)))
681 1527148 : AstUnionType(length, zone));
682 : }
683 :
684 : static AstUnionType* cast(AstType* type) {
685 : DCHECK(IsKind(type, kUnion));
686 : return static_cast<AstUnionType*>(FromType(type));
687 : }
688 :
689 : bool Wellformed();
690 : };
691 :
692 : class AstType {
693 : public:
694 : typedef AstBitsetType::bitset bitset; // Internal
695 :
696 : // Constructors.
697 : #define DEFINE_TYPE_CONSTRUCTOR(type, value) \
698 : static AstType* type() { return AstBitsetType::New(AstBitsetType::k##type); }
699 : AST_PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
700 : #undef DEFINE_TYPE_CONSTRUCTOR
701 :
702 : static AstType* SignedSmall() {
703 4261523 : return AstBitsetType::New(AstBitsetType::SignedSmall());
704 : }
705 : static AstType* UnsignedSmall() {
706 : return AstBitsetType::New(AstBitsetType::UnsignedSmall());
707 : }
708 :
709 : static AstType* Class(i::Handle<i::Map> map, Zone* zone) {
710 19502 : return AstClassType::New(map, zone);
711 : }
712 : static AstType* Constant(i::Handle<i::Object> value, Zone* zone) {
713 2779361 : return AstConstantType::New(value, zone);
714 : }
715 : static AstType* Range(double min, double max, Zone* zone) {
716 : return AstRangeType::New(min, max,
717 : AST_REPRESENTATION(AstBitsetType::kTagged |
718 : AstBitsetType::kUntaggedNumber),
719 : zone);
720 : }
721 : static AstType* Context(AstType* outer, Zone* zone) {
722 : return AstContextType::New(outer, zone);
723 : }
724 : static AstType* Array(AstType* element, Zone* zone) {
725 : return AstArrayType::New(element, zone);
726 : }
727 : static AstType* Function(AstType* result, AstType* receiver, int arity,
728 : Zone* zone) {
729 : return AstFunctionType::New(result, receiver, arity, zone);
730 : }
731 : static AstType* Function(AstType* result, Zone* zone) {
732 : return Function(result, Any(), 0, zone);
733 : }
734 : static AstType* Function(AstType* result, AstType* param0, Zone* zone) {
735 : AstType* function = Function(result, Any(), 1, zone);
736 : function->AsFunction()->InitParameter(0, param0);
737 : return function;
738 : }
739 : static AstType* Function(AstType* result, AstType* param0, AstType* param1,
740 : Zone* zone) {
741 : AstType* function = Function(result, Any(), 2, zone);
742 : function->AsFunction()->InitParameter(0, param0);
743 : function->AsFunction()->InitParameter(1, param1);
744 : return function;
745 : }
746 : static AstType* Function(AstType* result, AstType* param0, AstType* param1,
747 : AstType* param2, Zone* zone) {
748 : AstType* function = Function(result, Any(), 3, zone);
749 : function->AsFunction()->InitParameter(0, param0);
750 : function->AsFunction()->InitParameter(1, param1);
751 : function->AsFunction()->InitParameter(2, param2);
752 : return function;
753 : }
754 : static AstType* Function(AstType* result, int arity, AstType** params,
755 : Zone* zone) {
756 : AstType* function = Function(result, Any(), arity, zone);
757 : for (int i = 0; i < arity; ++i) {
758 : function->AsFunction()->InitParameter(i, params[i]);
759 : }
760 : return function;
761 : }
762 : static AstType* Tuple(AstType* first, AstType* second, AstType* third,
763 : Zone* zone) {
764 : AstType* tuple = AstTupleType::New(3, zone);
765 : tuple->AsTuple()->InitElement(0, first);
766 : tuple->AsTuple()->InitElement(1, second);
767 : tuple->AsTuple()->InitElement(2, third);
768 : return tuple;
769 : }
770 :
771 : static AstType* Union(AstType* type1, AstType* type2, Zone* zone);
772 : static AstType* Intersect(AstType* type1, AstType* type2, Zone* zone);
773 :
774 : static AstType* Of(double value, Zone* zone) {
775 : return AstBitsetType::New(
776 : AstBitsetType::ExpandInternals(AstBitsetType::Lub(value)));
777 : }
778 5418 : static AstType* Of(i::Object* value, Zone* zone) {
779 : return AstBitsetType::New(
780 10836 : AstBitsetType::ExpandInternals(AstBitsetType::Lub(value)));
781 : }
782 : static AstType* Of(i::Handle<i::Object> value, Zone* zone) {
783 : return Of(*value, zone);
784 : }
785 :
786 : static AstType* For(i::Map* map) {
787 : return AstBitsetType::New(
788 : AstBitsetType::ExpandInternals(AstBitsetType::Lub(map)));
789 : }
790 : static AstType* For(i::Handle<i::Map> map) { return For(*map); }
791 :
792 : // Extraction of components.
793 : static AstType* Representation(AstType* t, Zone* zone);
794 : static AstType* Semantic(AstType* t, Zone* zone);
795 :
796 : // Predicates.
797 4037038 : bool IsInhabited() { return AstBitsetType::IsInhabited(this->BitsetLub()); }
798 :
799 27730698 : bool Is(AstType* that) { return this == that || this->SlowIs(that); }
800 : bool Maybe(AstType* that);
801 466832 : bool Equals(AstType* that) { return this->Is(that) && that->Is(this); }
802 :
803 : // Equivalent to Constant(val)->Is(this), but avoiding allocation.
804 : bool Contains(i::Object* val);
805 : bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); }
806 :
807 : // State-dependent versions of the above that consider subtyping between
808 : // a constant and its map class.
809 : static AstType* NowOf(i::Object* value, Zone* zone);
810 : static AstType* NowOf(i::Handle<i::Object> value, Zone* zone) {
811 : return NowOf(*value, zone);
812 : }
813 : bool NowIs(AstType* that);
814 : bool NowContains(i::Object* val);
815 : bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); }
816 :
817 : bool NowStable();
818 :
819 : // Inspection.
820 : bool IsRange() { return IsKind(AstTypeBase::kRange); }
821 : bool IsClass() { return IsKind(AstTypeBase::kClass); }
822 : bool IsConstant() { return IsKind(AstTypeBase::kConstant); }
823 : bool IsContext() { return IsKind(AstTypeBase::kContext); }
824 : bool IsArray() { return IsKind(AstTypeBase::kArray); }
825 : bool IsFunction() { return IsKind(AstTypeBase::kFunction); }
826 : bool IsTuple() { return IsKind(AstTypeBase::kTuple); }
827 :
828 : AstClassType* AsClass() { return AstClassType::cast(this); }
829 : AstConstantType* AsConstant() { return AstConstantType::cast(this); }
830 : AstRangeType* AsRange() { return AstRangeType::cast(this); }
831 : AstContextType* AsContext() { return AstContextType::cast(this); }
832 : AstArrayType* AsArray() { return AstArrayType::cast(this); }
833 : AstFunctionType* AsFunction() { return AstFunctionType::cast(this); }
834 : AstTupleType* AsTuple() { return AstTupleType::cast(this); }
835 :
836 : // Minimum and maximum of a numeric type.
837 : // These functions do not distinguish between -0 and +0. If the type equals
838 : // kNaN, they return NaN; otherwise kNaN is ignored. Only call these
839 : // functions on subtypes of Number.
840 : double Min();
841 : double Max();
842 :
843 : // Extracts a range from the type: if the type is a range or a union
844 : // containing a range, that range is returned; otherwise, NULL is returned.
845 : AstType* GetRange();
846 :
847 : static bool IsInteger(i::Object* x);
848 : static bool IsInteger(double x) {
849 2450 : return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities.
850 : }
851 :
852 : int NumClasses();
853 : int NumConstants();
854 :
855 : template <class T>
856 : class Iterator {
857 : public:
858 85588 : bool Done() const { return index_ < 0; }
859 : i::Handle<T> Current();
860 : void Advance();
861 :
862 : private:
863 : friend class AstType;
864 :
865 0 : Iterator() : index_(-1) {}
866 15576 : explicit Iterator(AstType* type) : type_(type), index_(-1) { Advance(); }
867 :
868 : inline bool matches(AstType* type);
869 : inline AstType* get_type();
870 :
871 : AstType* type_;
872 : int index_;
873 : };
874 :
875 79034 : Iterator<i::Map> Classes() {
876 79034 : if (this->IsBitset()) return Iterator<i::Map>();
877 15185 : return Iterator<i::Map>(this);
878 : }
879 2173 : Iterator<i::Object> Constants() {
880 2173 : if (this->IsBitset()) return Iterator<i::Object>();
881 391 : return Iterator<i::Object>(this);
882 : }
883 :
884 : // Printing.
885 :
886 : enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
887 :
888 : void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT
889 :
890 : #ifdef DEBUG
891 : void Print();
892 : #endif
893 :
894 : // Helpers for testing.
895 : bool IsBitsetForTesting() { return IsBitset(); }
896 : bool IsUnionForTesting() { return IsUnion(); }
897 : bitset AsBitsetForTesting() { return AsBitset(); }
898 : AstUnionType* AsUnionForTesting() { return AsUnion(); }
899 :
900 : private:
901 : // Friends.
902 : template <class>
903 : friend class Iterator;
904 : friend AstBitsetType;
905 : friend AstUnionType;
906 :
907 : // Internal inspection.
908 : bool IsKind(AstTypeBase::Kind kind) {
909 : return AstTypeBase::IsKind(this, kind);
910 : }
911 :
912 : bool IsNone() { return this == None(); }
913 : bool IsAny() { return this == Any(); }
914 : bool IsBitset() { return AstBitsetType::IsBitset(this); }
915 : bool IsUnion() { return IsKind(AstTypeBase::kUnion); }
916 :
917 : bitset AsBitset() {
918 : DCHECK(this->IsBitset());
919 : return reinterpret_cast<AstBitsetType*>(this)->Bitset();
920 : }
921 : AstUnionType* AsUnion() { return AstUnionType::cast(this); }
922 :
923 : bitset Representation();
924 :
925 : // Auxiliary functions.
926 : bool SemanticMaybe(AstType* that);
927 :
928 4526512 : bitset BitsetGlb() { return AstBitsetType::Glb(this); }
929 38794850 : bitset BitsetLub() { return AstBitsetType::Lub(this); }
930 :
931 : bool SlowIs(AstType* that);
932 : bool SemanticIs(AstType* that);
933 :
934 : static bool Overlap(AstRangeType* lhs, AstRangeType* rhs);
935 : static bool Contains(AstRangeType* lhs, AstRangeType* rhs);
936 : static bool Contains(AstRangeType* range, AstConstantType* constant);
937 : static bool Contains(AstRangeType* range, i::Object* val);
938 :
939 : static int UpdateRange(AstType* type, AstUnionType* result, int size,
940 : Zone* zone);
941 :
942 : static AstRangeType::Limits IntersectRangeAndBitset(AstType* range,
943 : AstType* bits,
944 : Zone* zone);
945 : static AstRangeType::Limits ToLimits(bitset bits, Zone* zone);
946 :
947 : bool SimplyEquals(AstType* that);
948 :
949 : static int AddToUnion(AstType* type, AstUnionType* result, int size,
950 : Zone* zone);
951 : static int IntersectAux(AstType* type, AstType* other, AstUnionType* result,
952 : int size, AstRangeType::Limits* limits, Zone* zone);
953 : static AstType* NormalizeUnion(AstType* unioned, int size, Zone* zone);
954 : static AstType* NormalizeRangeAndBitset(AstType* range, bitset* bits,
955 : Zone* zone);
956 : };
957 :
958 : // -----------------------------------------------------------------------------
959 : // Type bounds. A simple struct to represent a pair of lower/upper types.
960 :
961 : struct AstBounds {
962 : AstType* lower;
963 : AstType* upper;
964 :
965 : AstBounds()
966 : : // Make sure accessing uninitialized bounds crashes big-time.
967 : lower(nullptr),
968 7809527 : upper(nullptr) {}
969 3708570 : explicit AstBounds(AstType* t) : lower(t), upper(t) {}
970 460185 : AstBounds(AstType* l, AstType* u) : lower(l), upper(u) {
971 : DCHECK(lower->Is(upper));
972 : }
973 :
974 : // Unrestricted bounds.
975 : static AstBounds Unbounded() {
976 : return AstBounds(AstType::None(), AstType::Any());
977 : }
978 :
979 : // Meet: both b1 and b2 are known to hold.
980 7527408 : static AstBounds Both(AstBounds b1, AstBounds b2, Zone* zone) {
981 7527408 : AstType* lower = AstType::Union(b1.lower, b2.lower, zone);
982 7527408 : AstType* upper = AstType::Intersect(b1.upper, b2.upper, zone);
983 : // Lower bounds are considered approximate, correct as necessary.
984 7527408 : if (!lower->Is(upper)) lower = upper;
985 7527408 : return AstBounds(lower, upper);
986 : }
987 :
988 : // Join: either b1 or b2 is known to hold.
989 224230 : static AstBounds Either(AstBounds b1, AstBounds b2, Zone* zone) {
990 224230 : AstType* lower = AstType::Intersect(b1.lower, b2.lower, zone);
991 224230 : AstType* upper = AstType::Union(b1.upper, b2.upper, zone);
992 224230 : return AstBounds(lower, upper);
993 : }
994 :
995 2605727 : static AstBounds NarrowLower(AstBounds b, AstType* t, Zone* zone) {
996 2605727 : AstType* lower = AstType::Union(b.lower, t, zone);
997 : // Lower bounds are considered approximate, correct as necessary.
998 2605727 : if (!lower->Is(b.upper)) lower = b.upper;
999 2605727 : return AstBounds(lower, b.upper);
1000 : }
1001 : static AstBounds NarrowUpper(AstBounds b, AstType* t, Zone* zone) {
1002 : AstType* lower = b.lower;
1003 : AstType* upper = AstType::Intersect(b.upper, t, zone);
1004 : // Lower bounds are considered approximate, correct as necessary.
1005 : if (!lower->Is(upper)) lower = upper;
1006 : return AstBounds(lower, upper);
1007 : }
1008 :
1009 : bool Narrows(AstBounds that) {
1010 : return that.lower->Is(this->lower) && this->upper->Is(that.upper);
1011 : }
1012 : };
1013 :
1014 : } // namespace internal
1015 : } // namespace v8
1016 :
1017 : #endif // V8_AST_AST_TYPES_H_
|
