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_COMPILER_TYPES_H_
6 #define V8_COMPILER_TYPES_H_
7
8 #include "src/base/compiler-specific.h"
9 #include "src/common/globals.h"
10 #include "src/compiler/heap-refs.h"
11 #include "src/handles/handles.h"
12 #include "src/numbers/conversions.h"
13 #include "src/objects/objects.h"
14 #include "src/utils/ostreams.h"
15
16 namespace v8 {
17 namespace internal {
18 namespace compiler {
19
20 // SUMMARY
21 //
22 // A simple type system for compiler-internal use. It is based entirely on
23 // union types, and all subtyping hence amounts to set inclusion. Besides the
24 // obvious primitive types and some predefined unions, the type language also
25 // can express class types (a.k.a. specific maps) and singleton types (i.e.,
26 // concrete constants).
27 //
28 // The following equations and inequations hold:
29 //
30 // None <= T
31 // T <= Any
32 //
33 // Number = Signed32 \/ Unsigned32 \/ Double
34 // Smi <= Signed32
35 // Name = String \/ Symbol
36 // UniqueName = InternalizedString \/ Symbol
37 // InternalizedString < String
38 //
39 // Receiver = Object \/ Proxy
40 // OtherUndetectable < Object
41 // DetectableReceiver = Receiver - OtherUndetectable
42 //
43 // Constant(x) < T iff instance_type(map(x)) < T
44 //
45 //
46 // RANGE TYPES
47 //
48 // A range type represents a continuous integer interval by its minimum and
49 // maximum value. Either value may be an infinity, in which case that infinity
50 // itself is also included in the range. A range never contains NaN or -0.
51 //
52 // If a value v happens to be an integer n, then Constant(v) is considered a
53 // subtype of Range(n, n) (and therefore also a subtype of any larger range).
54 // In order to avoid large unions, however, it is usually a good idea to use
55 // Range rather than Constant.
56 //
57 //
58 // PREDICATES
59 //
60 // There are two main functions for testing types:
61 //
62 // T1.Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2)
63 // T1.Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0)
64 //
65 // Typically, the former is to be used to select representations (e.g., via
66 // T.Is(SignedSmall())), and the latter to check whether a specific case needs
67 // handling (e.g., via T.Maybe(Number())).
68 //
69 // There is no functionality to discover whether a type is a leaf in the
70 // lattice. That is intentional. It should always be possible to refine the
71 // lattice (e.g., splitting up number types further) without invalidating any
72 // existing assumptions or tests.
73 // Consequently, do not normally use Equals for type tests, always use Is!
74 //
75 //
76 // PROPERTIES
77 //
78 // Various formal properties hold for constructors, operators, and predicates
79 // over types. For example, constructors are injective and subtyping is a
80 // complete partial order.
81 //
82 // See test/cctest/test-types.cc for a comprehensive executable specification,
83 // especially with respect to the properties of the more exotic 'temporal'
84 // constructors and predicates (those prefixed 'Now').
85 //
86 //
87 // IMPLEMENTATION
88 //
89 // Internally, all 'primitive' types, and their unions, are represented as
90 // bitsets. Bit 0 is reserved for tagging. Only structured types require
91 // allocation.
92
93 // -----------------------------------------------------------------------------
94 // Values for bitset types
95
96 // clang-format off
97
98 #define INTERNAL_BITSET_TYPE_LIST(V) \
99 V(OtherUnsigned31, uint64_t{1} << 1) \
100 V(OtherUnsigned32, uint64_t{1} << 2) \
101 V(OtherSigned32, uint64_t{1} << 3) \
102 V(OtherNumber, uint64_t{1} << 4) \
103 V(OtherString, uint64_t{1} << 5) \
104
105 #define PROPER_ATOMIC_BITSET_TYPE_LOW_LIST(V) \
106 V(Negative31, uint64_t{1} << 6) \
107 V(Null, uint64_t{1} << 7) \
108 V(Undefined, uint64_t{1} << 8) \
109 V(Boolean, uint64_t{1} << 9) \
110 V(Unsigned30, uint64_t{1} << 10) \
111 V(MinusZero, uint64_t{1} << 11) \
112 V(NaN, uint64_t{1} << 12) \
113 V(Symbol, uint64_t{1} << 13) \
114 V(InternalizedString, uint64_t{1} << 14) \
115 V(OtherCallable, uint64_t{1} << 15) \
116 V(OtherObject, uint64_t{1} << 16) \
117 V(OtherUndetectable, uint64_t{1} << 17) \
118 V(CallableProxy, uint64_t{1} << 18) \
119 V(OtherProxy, uint64_t{1} << 19) \
120 V(CallableFunction, uint64_t{1} << 20) \
121 V(ClassConstructor, uint64_t{1} << 21) \
122 V(BoundFunction, uint64_t{1} << 22) \
123 V(Hole, uint64_t{1} << 23) \
124 V(OtherInternal, uint64_t{1} << 24) \
125 V(ExternalPointer, uint64_t{1} << 25) \
126 V(Array, uint64_t{1} << 26) \
127 V(UnsignedBigInt63, uint64_t{1} << 27) \
128 V(OtherUnsignedBigInt64, uint64_t{1} << 28) \
129 V(NegativeBigInt63, uint64_t{1} << 29) \
130 V(OtherBigInt, uint64_t{1} << 30) \
131 V(WasmObject, uint64_t{1} << 31)
132
133 // We split the macro list into two parts because the Torque equivalent in
134 // turbofan-types.tq uses two 32bit bitfield structs.
135 #define PROPER_ATOMIC_BITSET_TYPE_HIGH_LIST(V) \
136 V(SandboxedPointer, uint64_t{1} << 32)
137
138 #define PROPER_BITSET_TYPE_LIST(V) \
139 V(None, uint64_t{0}) \
140 PROPER_ATOMIC_BITSET_TYPE_LOW_LIST(V) \
141 PROPER_ATOMIC_BITSET_TYPE_HIGH_LIST(V) \
142 V(Signed31, kUnsigned30 | kNegative31) \
143 V(Signed32, kSigned31 | kOtherUnsigned31 | \
144 kOtherSigned32) \
145 V(Signed32OrMinusZero, kSigned32 | kMinusZero) \
146 V(Signed32OrMinusZeroOrNaN, kSigned32 | kMinusZero | kNaN) \
147 V(Negative32, kNegative31 | kOtherSigned32) \
148 V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \
149 V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \
150 kOtherUnsigned32) \
151 V(Unsigned32OrMinusZero, kUnsigned32 | kMinusZero) \
152 V(Unsigned32OrMinusZeroOrNaN, kUnsigned32 | kMinusZero | kNaN) \
153 V(Integral32, kSigned32 | kUnsigned32) \
154 V(Integral32OrMinusZero, kIntegral32 | kMinusZero) \
155 V(Integral32OrMinusZeroOrNaN, kIntegral32OrMinusZero | kNaN) \
156 V(PlainNumber, kIntegral32 | kOtherNumber) \
157 V(OrderedNumber, kPlainNumber | kMinusZero) \
158 V(MinusZeroOrNaN, kMinusZero | kNaN) \
159 V(Number, kOrderedNumber | kNaN) \
160 V(SignedBigInt64, kUnsignedBigInt63 | kNegativeBigInt63) \
161 V(UnsignedBigInt64, kUnsignedBigInt63 | kOtherUnsignedBigInt64) \
162 V(BigInt, kSignedBigInt64 | kOtherUnsignedBigInt64 | \
163 kOtherBigInt) \
164 V(Numeric, kNumber | kBigInt) \
165 V(String, kInternalizedString | kOtherString) \
166 V(UniqueName, kSymbol | kInternalizedString) \
167 V(Name, kSymbol | kString) \
168 V(InternalizedStringOrNull, kInternalizedString | kNull) \
169 V(BooleanOrNumber, kBoolean | kNumber) \
170 V(BooleanOrNullOrNumber, kBooleanOrNumber | kNull) \
171 V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \
172 V(Oddball, kBooleanOrNullOrUndefined | kHole) \
173 V(NullOrNumber, kNull | kNumber) \
174 V(NullOrUndefined, kNull | kUndefined) \
175 V(Undetectable, kNullOrUndefined | kOtherUndetectable) \
176 V(NumberOrHole, kNumber | kHole) \
177 V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean | \
178 kHole) \
179 V(NumericOrString, kNumeric | kString) \
180 V(NumberOrUndefined, kNumber | kUndefined) \
181 V(NumberOrUndefinedOrNullOrBoolean, \
182 kNumber | kNullOrUndefined | kBoolean) \
183 V(PlainPrimitive, kNumber | kString | kBoolean | \
184 kNullOrUndefined) \
185 V(NonBigIntPrimitive, kSymbol | kPlainPrimitive) \
186 V(Primitive, kBigInt | kNonBigIntPrimitive) \
187 V(OtherUndetectableOrUndefined, kOtherUndetectable | kUndefined) \
188 V(Proxy, kCallableProxy | kOtherProxy) \
189 V(ArrayOrOtherObject, kArray | kOtherObject) \
190 V(ArrayOrProxy, kArray | kProxy) \
191 V(Function, kCallableFunction | kClassConstructor) \
192 V(DetectableCallable, kFunction | kBoundFunction | \
193 kOtherCallable | kCallableProxy) \
194 V(Callable, kDetectableCallable | kOtherUndetectable) \
195 V(NonCallable, kArray | kOtherObject | kOtherProxy) \
196 V(NonCallableOrNull, kNonCallable | kNull) \
197 V(DetectableObject, kArray | kFunction | kBoundFunction | \
198 kOtherCallable | kOtherObject) \
199 V(DetectableReceiver, kDetectableObject | kProxy) \
200 V(DetectableReceiverOrNull, kDetectableReceiver | kNull) \
201 V(Object, kDetectableObject | kOtherUndetectable) \
202 V(Receiver, kObject | kProxy | kWasmObject) \
203 V(ReceiverOrUndefined, kReceiver | kUndefined) \
204 V(ReceiverOrNullOrUndefined, kReceiver | kNull | kUndefined) \
205 V(SymbolOrReceiver, kSymbol | kReceiver) \
206 V(StringOrReceiver, kString | kReceiver) \
207 V(Unique, kBoolean | kUniqueName | kNull | \
208 kUndefined | kHole | kReceiver) \
209 V(Internal, kHole | kExternalPointer | \
210 kSandboxedPointer | kOtherInternal) \
211 V(NonInternal, kPrimitive | kReceiver) \
212 V(NonBigInt, kNonBigIntPrimitive | kReceiver) \
213 V(NonNumber, kBigInt | kUnique | kString | kInternal) \
214 V(Any, uint64_t{0xfffffffffffffffe})
215
216 // clang-format on
217
218 /*
219 * The following diagrams show how integers (in the mathematical sense) are
220 * divided among the different atomic numerical types.
221 *
222 * ON OS32 N31 U30 OU31 OU32 ON
223 * ______[_______[_______[_______[_______[_______[_______
224 * -2^31 -2^30 0 2^30 2^31 2^32
225 *
226 * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1.
227 *
228 * Some of the atomic numerical bitsets are internal only (see
229 * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in
230 * union with certain other bitsets. For instance, OtherNumber should only
231 * occur as part of PlainNumber.
232 */
233
234 #define BITSET_TYPE_LIST(V) \
235 INTERNAL_BITSET_TYPE_LIST(V) \
236 PROPER_BITSET_TYPE_LIST(V)
237
238 class JSHeapBroker;
239 class HeapConstantType;
240 class OtherNumberConstantType;
241 class TupleType;
242 class Type;
243 class UnionType;
244
245 // -----------------------------------------------------------------------------
246 // Bitset types (internal).
247
248 class V8_EXPORT_PRIVATE BitsetType {
249 public:
250 using bitset = uint64_t; // Internal
251
252 enum : bitset {
253 #define DECLARE_TYPE(type, value) k##type = (value),
254 BITSET_TYPE_LIST(DECLARE_TYPE)
255 #undef DECLARE_TYPE
256 kUnusedEOL = 0
257 };
258
259 static bitset SignedSmall();
260 static bitset UnsignedSmall();
261
IsNone(bitset bits)262 static bool IsNone(bitset bits) { return bits == kNone; }
263
Is(bitset bits1,bitset bits2)264 static bool Is(bitset bits1, bitset bits2) {
265 return (bits1 | bits2) == bits2;
266 }
267
268 static double Min(bitset);
269 static double Max(bitset);
270
271 static bitset Glb(double min, double max);
Lub(HeapObjectType const & type)272 static bitset Lub(HeapObjectType const& type) {
273 return Lub<HeapObjectType>(type);
274 }
Lub(MapRef const & map)275 static bitset Lub(MapRef const& map) { return Lub<MapRef>(map); }
276 static bitset Lub(double value);
277 static bitset Lub(double min, double max);
278 static bitset ExpandInternals(bitset bits);
279
280 static const char* Name(bitset);
281 static void Print(std::ostream& os, bitset);
282 #ifdef DEBUG
283 static void Print(bitset);
284 #endif
285
286 static bitset NumberBits(bitset bits);
287
288 private:
289 struct Boundary {
290 bitset internal;
291 bitset external;
292 double min;
293 };
294 static const Boundary BoundariesArray[];
295 static inline const Boundary* Boundaries();
296 static inline size_t BoundariesSize();
297
298 template <typename MapRefLike>
299 static bitset Lub(MapRefLike const& map);
300 };
301
302 // -----------------------------------------------------------------------------
303 // Superclass for non-bitset types (internal).
304 class TypeBase {
305 protected:
306 friend class Type;
307
308 enum Kind { kHeapConstant, kOtherNumberConstant, kTuple, kUnion, kRange };
309
kind()310 Kind kind() const { return kind_; }
TypeBase(Kind kind)311 explicit TypeBase(Kind kind) : kind_(kind) {}
312
313 static bool IsKind(Type type, Kind kind);
314
315 private:
316 Kind kind_;
317 };
318
319 // -----------------------------------------------------------------------------
320 // Range types.
321
322 class RangeType : public TypeBase {
323 public:
324 struct Limits {
325 double min;
326 double max;
LimitsLimits327 Limits(double min, double max) : min(min), max(max) {}
LimitsLimits328 explicit Limits(const RangeType* range)
329 : min(range->Min()), max(range->Max()) {}
330 bool IsEmpty();
EmptyLimits331 static Limits Empty() { return Limits(1, 0); }
332 static Limits Intersect(Limits lhs, Limits rhs);
333 static Limits Union(Limits lhs, Limits rhs);
334 };
335
Min()336 double Min() const { return limits_.min; }
Max()337 double Max() const { return limits_.max; }
338
IsInteger(double x)339 static bool IsInteger(double x) {
340 return nearbyint(x) == x && !IsMinusZero(x); // Allows for infinities.
341 }
342
343 private:
344 friend class Type;
345 friend class BitsetType;
346 friend class UnionType;
347 friend Zone;
348
New(double min,double max,Zone * zone)349 static RangeType* New(double min, double max, Zone* zone) {
350 return New(Limits(min, max), zone);
351 }
352
New(Limits lim,Zone * zone)353 static RangeType* New(Limits lim, Zone* zone) {
354 DCHECK(IsInteger(lim.min) && IsInteger(lim.max));
355 DCHECK(lim.min <= lim.max);
356 BitsetType::bitset bits = BitsetType::Lub(lim.min, lim.max);
357
358 return zone->New<RangeType>(bits, lim);
359 }
360
RangeType(BitsetType::bitset bitset,Limits limits)361 RangeType(BitsetType::bitset bitset, Limits limits)
362 : TypeBase(kRange), bitset_(bitset), limits_(limits) {}
363
Lub()364 BitsetType::bitset Lub() const { return bitset_; }
365
366 BitsetType::bitset bitset_;
367 Limits limits_;
368 };
369
370 // -----------------------------------------------------------------------------
371 // The actual type.
372
373 class V8_EXPORT_PRIVATE Type {
374 public:
375 using bitset = BitsetType::bitset; // Internal
376
377 // Constructors.
378 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \
379 static Type type() { return NewBitset(BitsetType::k##type); }
380 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
381 #undef DEFINE_TYPE_CONSTRUCTOR
382
Type()383 Type() : payload_(uint64_t{0}) {}
384
SignedSmall()385 static Type SignedSmall() { return NewBitset(BitsetType::SignedSmall()); }
UnsignedSmall()386 static Type UnsignedSmall() { return NewBitset(BitsetType::UnsignedSmall()); }
387
388 static Type Constant(JSHeapBroker* broker, Handle<i::Object> value,
389 Zone* zone);
390 static Type Constant(double value, Zone* zone);
391 static Type Range(double min, double max, Zone* zone);
392 static Type Tuple(Type first, Type second, Type third, Zone* zone);
393
394 static Type Union(Type type1, Type type2, Zone* zone);
395 static Type Intersect(Type type1, Type type2, Zone* zone);
396
For(MapRef const & type)397 static Type For(MapRef const& type) {
398 return NewBitset(BitsetType::ExpandInternals(BitsetType::Lub(type)));
399 }
400
401 // Predicates.
IsNone()402 bool IsNone() const { return payload_ == None().payload_; }
IsInvalid()403 bool IsInvalid() const { return payload_ == uint64_t{0}; }
404
Is(Type that)405 bool Is(Type that) const {
406 return payload_ == that.payload_ || this->SlowIs(that);
407 }
408 bool Maybe(Type that) const;
Equals(Type that)409 bool Equals(Type that) const { return this->Is(that) && that.Is(*this); }
410
411 // Inspection.
IsBitset()412 bool IsBitset() const { return payload_ & uint64_t{1}; }
IsRange()413 bool IsRange() const { return IsKind(TypeBase::kRange); }
IsHeapConstant()414 bool IsHeapConstant() const { return IsKind(TypeBase::kHeapConstant); }
IsOtherNumberConstant()415 bool IsOtherNumberConstant() const {
416 return IsKind(TypeBase::kOtherNumberConstant);
417 }
IsTuple()418 bool IsTuple() const { return IsKind(TypeBase::kTuple); }
419
IsSingleton()420 bool IsSingleton() const {
421 if (IsNone()) return false;
422 return Is(Type::Null()) || Is(Type::Undefined()) || Is(Type::MinusZero()) ||
423 Is(Type::NaN()) || Is(Type::Hole()) || IsHeapConstant() ||
424 (Is(Type::PlainNumber()) && Min() == Max());
425 }
426
CanBeAsserted()427 bool CanBeAsserted() const { return Is(Type::NonInternal()); }
428 Handle<TurbofanType> AllocateOnHeap(Factory* factory);
429
430 const HeapConstantType* AsHeapConstant() const;
431 const OtherNumberConstantType* AsOtherNumberConstant() const;
432 const RangeType* AsRange() const;
433 const TupleType* AsTuple() const;
434
435 // Minimum and maximum of a numeric type.
436 // These functions do not distinguish between -0 and +0. NaN is ignored.
437 // Only call them on subtypes of Number whose intersection with OrderedNumber
438 // is not empty.
439 double Min() const;
440 double Max() const;
441
442 // Extracts a range from the type: if the type is a range or a union
443 // containing a range, that range is returned; otherwise, nullptr is returned.
444 Type GetRange() const;
445
446 int NumConstants() const;
447
Invalid()448 static Type Invalid() { return Type(); }
449
450 bool operator==(Type other) const { return payload_ == other.payload_; }
451 bool operator!=(Type other) const { return payload_ != other.payload_; }
452
453 // Printing.
454
455 void PrintTo(std::ostream& os) const;
456
457 #ifdef DEBUG
458 void Print() const;
459 #endif
460
461 // Helpers for testing.
IsUnionForTesting()462 bool IsUnionForTesting() { return IsUnion(); }
AsBitsetForTesting()463 bitset AsBitsetForTesting() { return AsBitset(); }
AsUnionForTesting()464 const UnionType* AsUnionForTesting() { return AsUnion(); }
BitsetGlbForTesting()465 Type BitsetGlbForTesting() { return NewBitset(BitsetGlb()); }
BitsetLubForTesting()466 Type BitsetLubForTesting() { return NewBitset(BitsetLub()); }
467
468 private:
469 // Friends.
470 template <class>
471 friend class Iterator;
472 friend BitsetType;
473 friend UnionType;
474 friend size_t hash_value(Type type);
475
Type(bitset bits)476 explicit Type(bitset bits) : payload_(bits | uint64_t{1}) {}
477
Type(TypeBase * type_base)478 Type(TypeBase* type_base) // NOLINT(runtime/explicit)
479 : payload_(reinterpret_cast<uint64_t>(type_base)) {}
480
481 // Internal inspection.
IsKind(TypeBase::Kind kind)482 bool IsKind(TypeBase::Kind kind) const {
483 if (IsBitset()) return false;
484 const TypeBase* base = ToTypeBase();
485 return base->kind() == kind;
486 }
487
ToTypeBase()488 const TypeBase* ToTypeBase() const {
489 return reinterpret_cast<TypeBase*>(payload_);
490 }
FromTypeBase(TypeBase * type)491 static Type FromTypeBase(TypeBase* type) { return Type(type); }
492
IsAny()493 bool IsAny() const { return payload_ == Any().payload_; }
IsUnion()494 bool IsUnion() const { return IsKind(TypeBase::kUnion); }
495
AsBitset()496 bitset AsBitset() const {
497 DCHECK(IsBitset());
498 return static_cast<bitset>(payload_) ^ uint64_t { 1 };
499 }
500
501 const UnionType* AsUnion() const;
502
503 bitset BitsetGlb() const; // greatest lower bound that's a bitset
504 bitset BitsetLub() const; // least upper bound that's a bitset
505
506 bool SlowIs(Type that) const;
507
NewBitset(bitset bits)508 static Type NewBitset(bitset bits) { return Type(bits); }
509
510 static Type Range(RangeType::Limits lims, Zone* zone);
511 static Type OtherNumberConstant(double value, Zone* zone);
512 static Type HeapConstant(const HeapObjectRef& value, Zone* zone);
513
514 static bool Overlap(const RangeType* lhs, const RangeType* rhs);
515 static bool Contains(const RangeType* lhs, const RangeType* rhs);
516
517 static int UpdateRange(Type type, UnionType* result, int size, Zone* zone);
518
519 static RangeType::Limits IntersectRangeAndBitset(Type range, Type bits,
520 Zone* zone);
521 static RangeType::Limits ToLimits(bitset bits, Zone* zone);
522
523 bool SimplyEquals(Type that) const;
524
525 static int AddToUnion(Type type, UnionType* result, int size, Zone* zone);
526 static int IntersectAux(Type type, Type other, UnionType* result, int size,
527 RangeType::Limits* limits, Zone* zone);
528 static Type NormalizeUnion(UnionType* unioned, int size, Zone* zone);
529 static Type NormalizeRangeAndBitset(Type range, bitset* bits, Zone* zone);
530
531 // If LSB is set, the payload is a bitset; if LSB is clear, the payload is
532 // a pointer to a subtype of the TypeBase class.
533 uint64_t payload_;
534 };
535
hash_value(Type type)536 inline size_t hash_value(Type type) { return type.payload_; }
537 V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os, Type type);
538
539 // -----------------------------------------------------------------------------
540 // Constant types.
541
542 class OtherNumberConstantType : public TypeBase {
543 public:
Value()544 double Value() const { return value_; }
545
546 static bool IsOtherNumberConstant(double value);
547
548 private:
549 friend class Type;
550 friend class BitsetType;
551 friend Zone;
552
New(double value,Zone * zone)553 static OtherNumberConstantType* New(double value, Zone* zone) {
554 return zone->New<OtherNumberConstantType>(value);
555 }
556
OtherNumberConstantType(double value)557 explicit OtherNumberConstantType(double value)
558 : TypeBase(kOtherNumberConstant), value_(value) {
559 CHECK(IsOtherNumberConstant(value));
560 }
561
Lub()562 BitsetType::bitset Lub() const { return BitsetType::kOtherNumber; }
563
564 double value_;
565 };
566
NON_EXPORTED_BASE(TypeBase)567 class V8_EXPORT_PRIVATE HeapConstantType : public NON_EXPORTED_BASE(TypeBase) {
568 public:
569 Handle<HeapObject> Value() const;
570 const HeapObjectRef& Ref() const { return heap_ref_; }
571
572 private:
573 friend class Type;
574 friend class BitsetType;
575 friend Zone;
576
577 static HeapConstantType* New(const HeapObjectRef& heap_ref,
578 BitsetType::bitset bitset, Zone* zone) {
579 return zone->New<HeapConstantType>(bitset, heap_ref);
580 }
581
582 HeapConstantType(BitsetType::bitset bitset, const HeapObjectRef& heap_ref);
583
584 BitsetType::bitset Lub() const { return bitset_; }
585
586 BitsetType::bitset bitset_;
587 HeapObjectRef heap_ref_;
588 };
589
590 // -----------------------------------------------------------------------------
591 // Superclass for types with variable number of type fields.
592 class StructuralType : public TypeBase {
593 public:
LengthForTesting()594 int LengthForTesting() const { return Length(); }
595
596 protected:
597 friend class Type;
598
Length()599 int Length() const { return length_; }
600
Get(int i)601 Type Get(int i) const {
602 DCHECK(0 <= i && i < this->Length());
603 return elements_[i];
604 }
605
Set(int i,Type type)606 void Set(int i, Type type) {
607 DCHECK(0 <= i && i < this->Length());
608 elements_[i] = type;
609 }
610
Shrink(int length)611 void Shrink(int length) {
612 DCHECK(2 <= length && length <= this->Length());
613 length_ = length;
614 }
615
StructuralType(Kind kind,int length,Zone * zone)616 StructuralType(Kind kind, int length, Zone* zone)
617 : TypeBase(kind), length_(length) {
618 elements_ = zone->NewArray<Type>(length);
619 }
620
621 private:
622 int length_;
623 Type* elements_;
624 };
625
626 // -----------------------------------------------------------------------------
627 // Tuple types.
628
629 class TupleType : public StructuralType {
630 public:
Arity()631 int Arity() const { return this->Length(); }
Element(int i)632 Type Element(int i) const { return this->Get(i); }
633
InitElement(int i,Type type)634 void InitElement(int i, Type type) { this->Set(i, type); }
635
636 private:
637 friend Type;
638 friend Zone;
639
TupleType(int length,Zone * zone)640 TupleType(int length, Zone* zone) : StructuralType(kTuple, length, zone) {}
641
New(int length,Zone * zone)642 static TupleType* New(int length, Zone* zone) {
643 return zone->New<TupleType>(length, zone);
644 }
645 };
646
647 // -----------------------------------------------------------------------------
648 // Union types (internal).
649 // A union is a structured type with the following invariants:
650 // - its length is at least 2
651 // - at most one field is a bitset, and it must go into index 0
652 // - no field is a union
653 // - no field is a subtype of any other field
654 class UnionType : public StructuralType {
655 private:
656 friend Type;
657 friend BitsetType;
658 friend Zone;
659
UnionType(int length,Zone * zone)660 UnionType(int length, Zone* zone) : StructuralType(kUnion, length, zone) {}
661
New(int length,Zone * zone)662 static UnionType* New(int length, Zone* zone) {
663 return zone->New<UnionType>(length, zone);
664 }
665
666 bool Wellformed() const;
667 };
668
669 } // namespace compiler
670 } // namespace internal
671 } // namespace v8
672
673 #endif // V8_COMPILER_TYPES_H_
674