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