| // Copyright 2014 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef V8_TYPES_H_ |
| #define V8_TYPES_H_ |
| |
| #include "src/conversions.h" |
| #include "src/factory.h" |
| #include "src/handles.h" |
| #include "src/ostreams.h" |
| |
| namespace v8 { |
| namespace internal { |
| |
| // SUMMARY |
| // |
| // A simple type system for compiler-internal use. It is based entirely on |
| // union types, and all subtyping hence amounts to set inclusion. Besides the |
| // obvious primitive types and some predefined unions, the type language also |
| // can express class types (a.k.a. specific maps) and singleton types (i.e., |
| // concrete constants). |
| // |
| // Types consist of two dimensions: semantic (value range) and representation. |
| // Both are related through subtyping. |
| // |
| // |
| // SEMANTIC DIMENSION |
| // |
| // The following equations and inequations hold for the semantic axis: |
| // |
| // None <= T |
| // T <= Any |
| // |
| // Number = Signed32 \/ Unsigned32 \/ Double |
| // Smi <= Signed32 |
| // Name = String \/ Symbol |
| // UniqueName = InternalizedString \/ Symbol |
| // InternalizedString < String |
| // |
| // Receiver = Object \/ Proxy |
| // Array < Object |
| // Function < Object |
| // RegExp < Object |
| // Undetectable < Object |
| // Detectable = Receiver \/ Number \/ Name - Undetectable |
| // |
| // Class(map) < T iff instance_type(map) < T |
| // Constant(x) < T iff instance_type(map(x)) < T |
| // Array(T) < Array |
| // Function(R, S, T0, T1, ...) < Function |
| // Context(T) < Internal |
| // |
| // Both structural Array and Function types are invariant in all parameters; |
| // relaxing this would make Union and Intersect operations more involved. |
| // There is no subtyping relation between Array, Function, or Context types |
| // and respective Constant types, since these types cannot be reconstructed |
| // for arbitrary heap values. |
| // Note also that Constant(x) < Class(map(x)) does _not_ hold, since x's map can |
| // change! (Its instance type cannot, however.) |
| // TODO(rossberg): the latter is not currently true for proxies, because of fix, |
| // but will hold once we implement direct proxies. |
| // However, we also define a 'temporal' variant of the subtyping relation that |
| // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)). |
| // |
| // |
| // REPRESENTATIONAL DIMENSION |
| // |
| // For the representation axis, the following holds: |
| // |
| // None <= R |
| // R <= Any |
| // |
| // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ |
| // UntaggedInt16 \/ UntaggedInt32 |
| // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64 |
| // UntaggedNumber = UntaggedInt \/ UntaggedFloat |
| // Untagged = UntaggedNumber \/ UntaggedPtr |
| // Tagged = TaggedInt \/ TaggedPtr |
| // |
| // Subtyping relates the two dimensions, for example: |
| // |
| // Number <= Tagged \/ UntaggedNumber |
| // Object <= TaggedPtr \/ UntaggedPtr |
| // |
| // That holds because the semantic type constructors defined by the API create |
| // types that allow for all possible representations, and dually, the ones for |
| // representation types initially include all semantic ranges. Representations |
| // can then e.g. be narrowed for a given semantic type using intersection: |
| // |
| // SignedSmall /\ TaggedInt (a 'smi') |
| // Number /\ TaggedPtr (a heap number) |
| // |
| // |
| // RANGE TYPES |
| // |
| // A range type represents a continuous integer interval by its minimum and |
| // maximum value. Either value might be an infinity. |
| // |
| // Constant(v) is considered a subtype of Range(x..y) if v happens to be an |
| // integer between x and y. |
| // |
| // |
| // PREDICATES |
| // |
| // There are two main functions for testing types: |
| // |
| // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) |
| // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) |
| // |
| // Typically, the former is to be used to select representations (e.g., via |
| // T->Is(SignedSmall())), and the latter to check whether a specific case needs |
| // handling (e.g., via T->Maybe(Number())). |
| // |
| // There is no functionality to discover whether a type is a leaf in the |
| // lattice. That is intentional. It should always be possible to refine the |
| // lattice (e.g., splitting up number types further) without invalidating any |
| // existing assumptions or tests. |
| // Consequently, do not normally use Equals for type tests, always use Is! |
| // |
| // The NowIs operator implements state-sensitive subtying, as described above. |
| // Any compilation decision based on such temporary properties requires runtime |
| // guarding! |
| // |
| // |
| // PROPERTIES |
| // |
| // Various formal properties hold for constructors, operators, and predicates |
| // over types. For example, constructors are injective and subtyping is a |
| // complete partial order. |
| // |
| // See test/cctest/test-types.cc for a comprehensive executable specification, |
| // especially with respect to the properties of the more exotic 'temporal' |
| // constructors and predicates (those prefixed 'Now'). |
| // |
| // |
| // IMPLEMENTATION |
| // |
| // Internally, all 'primitive' types, and their unions, are represented as |
| // bitsets. Bit 0 is reserved for tagging. Class is a heap pointer to the |
| // respective map. Only structured types require allocation. |
| // Note that the bitset representation is closed under both Union and Intersect. |
| // |
| // There are two type representations, using different allocation: |
| // |
| // - class Type (zone-allocated, for compiler and concurrent compilation) |
| // - class HeapType (heap-allocated, for persistent types) |
| // |
| // Both provide the same API, and the Convert method can be used to interconvert |
| // them. For zone types, no query method touches the heap, only constructors do. |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Values for bitset types |
| |
| #define MASK_BITSET_TYPE_LIST(V) \ |
| V(Representation, 0xff800000u) \ |
| V(Semantic, 0x007ffffeu) |
| |
| #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) |
| #define SEMANTIC(k) ((k) & BitsetType::kSemantic) |
| |
| #define REPRESENTATION_BITSET_TYPE_LIST(V) \ |
| V(None, 0) \ |
| V(UntaggedInt1, 1u << 23 | kSemantic) \ |
| V(UntaggedInt8, 1u << 24 | kSemantic) \ |
| V(UntaggedInt16, 1u << 25 | kSemantic) \ |
| V(UntaggedInt32, 1u << 26 | kSemantic) \ |
| V(UntaggedFloat32, 1u << 27 | kSemantic) \ |
| V(UntaggedFloat64, 1u << 28 | kSemantic) \ |
| V(UntaggedPtr, 1u << 29 | kSemantic) \ |
| V(TaggedInt, 1u << 30 | kSemantic) \ |
| V(TaggedPtr, 1u << 31 | kSemantic) \ |
| \ |
| V(UntaggedInt, kUntaggedInt1 | kUntaggedInt8 | \ |
| kUntaggedInt16 | kUntaggedInt32) \ |
| V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ |
| V(UntaggedNumber, kUntaggedInt | kUntaggedFloat) \ |
| V(Untagged, kUntaggedNumber | kUntaggedPtr) \ |
| V(Tagged, kTaggedInt | kTaggedPtr) |
| |
| #define SEMANTIC_BITSET_TYPE_LIST(V) \ |
| V(Null, 1u << 1 | REPRESENTATION(kTaggedPtr)) \ |
| V(Undefined, 1u << 2 | REPRESENTATION(kTaggedPtr)) \ |
| V(Boolean, 1u << 3 | REPRESENTATION(kTaggedPtr)) \ |
| V(UnsignedSmall, 1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherSignedSmall, 1u << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherUnsigned31, 1u << 6 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherUnsigned32, 1u << 7 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherSigned32, 1u << 8 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(MinusZero, 1u << 9 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(NaN, 1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(OtherNumber, 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \ |
| V(Symbol, 1u << 12 | REPRESENTATION(kTaggedPtr)) \ |
| V(InternalizedString, 1u << 13 | REPRESENTATION(kTaggedPtr)) \ |
| V(OtherString, 1u << 14 | REPRESENTATION(kTaggedPtr)) \ |
| V(Undetectable, 1u << 15 | REPRESENTATION(kTaggedPtr)) \ |
| V(Array, 1u << 16 | REPRESENTATION(kTaggedPtr)) \ |
| V(Buffer, 1u << 17 | REPRESENTATION(kTaggedPtr)) \ |
| V(Function, 1u << 18 | REPRESENTATION(kTaggedPtr)) \ |
| V(RegExp, 1u << 19 | REPRESENTATION(kTaggedPtr)) \ |
| V(OtherObject, 1u << 20 | REPRESENTATION(kTaggedPtr)) \ |
| V(Proxy, 1u << 21 | REPRESENTATION(kTaggedPtr)) \ |
| V(Internal, 1u << 22 | REPRESENTATION(kTagged | kUntagged)) \ |
| \ |
| V(SignedSmall, kUnsignedSmall | kOtherSignedSmall) \ |
| V(Signed32, kSignedSmall | kOtherUnsigned31 | kOtherSigned32) \ |
| V(Unsigned32, kUnsignedSmall | kOtherUnsigned31 | kOtherUnsigned32) \ |
| V(Integral32, kSigned32 | kUnsigned32) \ |
| V(OrderedNumber, kIntegral32 | kMinusZero | kOtherNumber) \ |
| V(Number, kOrderedNumber | kNaN) \ |
| V(String, kInternalizedString | kOtherString) \ |
| V(UniqueName, kSymbol | kInternalizedString) \ |
| V(Name, kSymbol | kString) \ |
| V(NumberOrString, kNumber | kString) \ |
| V(Primitive, kNumber | kName | kBoolean | kNull | kUndefined) \ |
| V(DetectableObject, kArray | kFunction | kRegExp | kOtherObject) \ |
| V(DetectableReceiver, kDetectableObject | kProxy) \ |
| V(Detectable, kDetectableReceiver | kNumber | kName) \ |
| V(Object, kDetectableObject | kUndetectable) \ |
| V(Receiver, kObject | kProxy) \ |
| V(NonNumber, kBoolean | kName | kNull | kReceiver | \ |
| kUndefined | kInternal) \ |
| V(Any, 0xfffffffeu) |
| |
| /* |
| * The following diagrams show how integers (in the mathematical sense) are |
| * divided among the different atomic numerical types. |
| * |
| * If SmiValuesAre31Bits(): |
| * |
| * ON OS32 OSS US OU31 OU32 ON |
| * ______[_______[_______[_______[_______[_______[_______ |
| * -2^31 -2^30 0 2^30 2^31 2^32 |
| * |
| * Otherwise: |
| * |
| * ON OSS US OU32 ON |
| * ______[_______________[_______________[_______[_______ |
| * -2^31 0 2^31 2^32 |
| * |
| * |
| * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. |
| * |
| */ |
| |
| #define PROPER_BITSET_TYPE_LIST(V) \ |
| REPRESENTATION_BITSET_TYPE_LIST(V) \ |
| SEMANTIC_BITSET_TYPE_LIST(V) |
| |
| #define BITSET_TYPE_LIST(V) \ |
| MASK_BITSET_TYPE_LIST(V) \ |
| PROPER_BITSET_TYPE_LIST(V) |
| |
| |
| // ----------------------------------------------------------------------------- |
| // The abstract Type class, parameterized over the low-level representation. |
| |
| // struct Config { |
| // typedef TypeImpl<Config> Type; |
| // typedef Base; |
| // typedef Struct; |
| // typedef Region; |
| // template<class> struct Handle { typedef type; } // No template typedefs... |
| // template<class T> static Handle<T>::type handle(T* t); // !is_bitset(t) |
| // template<class T> static Handle<T>::type cast(Handle<Type>::type); |
| // static bool is_bitset(Type*); |
| // static bool is_class(Type*); |
| // static bool is_struct(Type*, int tag); |
| // static bitset as_bitset(Type*); |
| // static i::Handle<i::Map> as_class(Type*); |
| // static Handle<Struct>::type as_struct(Type*); |
| // static Type* from_bitset(bitset); |
| // static Handle<Type>::type from_bitset(bitset, Region*); |
| // static Handle<Type>::type from_class(i::Handle<Map>, Region*); |
| // static Handle<Type>::type from_struct(Handle<Struct>::type, int tag); |
| // static Handle<Struct>::type struct_create(int tag, int length, Region*); |
| // static void struct_shrink(Handle<Struct>::type, int length); |
| // static int struct_tag(Handle<Struct>::type); |
| // static int struct_length(Handle<Struct>::type); |
| // static Handle<Type>::type struct_get(Handle<Struct>::type, int); |
| // static void struct_set(Handle<Struct>::type, int, Handle<Type>::type); |
| // template<class V> |
| // static i::Handle<V> struct_get_value(Handle<Struct>::type, int); |
| // template<class V> |
| // static void struct_set_value(Handle<Struct>::type, int, i::Handle<V>); |
| // } |
| template<class Config> |
| class TypeImpl : public Config::Base { |
| public: |
| // Auxiliary types. |
| |
| typedef uint32_t bitset; // Internal |
| class BitsetType; // Internal |
| class StructuralType; // Internal |
| class UnionType; // Internal |
| |
| class ClassType; |
| class ConstantType; |
| class RangeType; |
| class ContextType; |
| class ArrayType; |
| class FunctionType; |
| |
| typedef typename Config::template Handle<TypeImpl>::type TypeHandle; |
| typedef typename Config::template Handle<ClassType>::type ClassHandle; |
| typedef typename Config::template Handle<ConstantType>::type ConstantHandle; |
| typedef typename Config::template Handle<RangeType>::type RangeHandle; |
| typedef typename Config::template Handle<ContextType>::type ContextHandle; |
| typedef typename Config::template Handle<ArrayType>::type ArrayHandle; |
| typedef typename Config::template Handle<FunctionType>::type FunctionHandle; |
| typedef typename Config::template Handle<UnionType>::type UnionHandle; |
| typedef typename Config::Region Region; |
| |
| // Constructors. |
| |
| #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ |
| static TypeImpl* type() { \ |
| return BitsetType::New(BitsetType::k##type); \ |
| } \ |
| static TypeHandle type(Region* region) { \ |
| return BitsetType::New(BitsetType::k##type, region); \ |
| } |
| PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) |
| #undef DEFINE_TYPE_CONSTRUCTOR |
| |
| static TypeHandle Class(i::Handle<i::Map> map, Region* region) { |
| return ClassType::New(map, region); |
| } |
| static TypeHandle Constant(i::Handle<i::Object> value, Region* region) { |
| return ConstantType::New(value, region); |
| } |
| static TypeHandle Range( |
| i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) { |
| return RangeType::New(min, max, region); |
| } |
| static TypeHandle Context(TypeHandle outer, Region* region) { |
| return ContextType::New(outer, region); |
| } |
| static TypeHandle Array(TypeHandle element, Region* region) { |
| return ArrayType::New(element, region); |
| } |
| static FunctionHandle Function( |
| TypeHandle result, TypeHandle receiver, int arity, Region* region) { |
| return FunctionType::New(result, receiver, arity, region); |
| } |
| static TypeHandle Function(TypeHandle result, Region* region) { |
| return Function(result, Any(region), 0, region); |
| } |
| static TypeHandle Function( |
| TypeHandle result, TypeHandle param0, Region* region) { |
| FunctionHandle function = Function(result, Any(region), 1, region); |
| function->InitParameter(0, param0); |
| return function; |
| } |
| static TypeHandle Function( |
| TypeHandle result, TypeHandle param0, TypeHandle param1, Region* region) { |
| FunctionHandle function = Function(result, Any(region), 2, region); |
| function->InitParameter(0, param0); |
| function->InitParameter(1, param1); |
| return function; |
| } |
| static TypeHandle Function( |
| TypeHandle result, TypeHandle param0, TypeHandle param1, |
| TypeHandle param2, Region* region) { |
| FunctionHandle function = Function(result, Any(region), 3, region); |
| function->InitParameter(0, param0); |
| function->InitParameter(1, param1); |
| function->InitParameter(2, param2); |
| return function; |
| } |
| |
| static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg); |
| static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg); |
| |
| static TypeHandle Of(double value, Region* region) { |
| return Config::from_bitset(BitsetType::Lub(value), region); |
| } |
| static TypeHandle Of(i::Object* value, Region* region) { |
| return Config::from_bitset(BitsetType::Lub(value), region); |
| } |
| static TypeHandle Of(i::Handle<i::Object> value, Region* region) { |
| return Of(*value, region); |
| } |
| |
| // Predicates. |
| |
| bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } |
| |
| bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); } |
| template<class TypeHandle> |
| bool Is(TypeHandle that) { return this->Is(*that); } |
| |
| bool Maybe(TypeImpl* that); |
| template<class TypeHandle> |
| bool Maybe(TypeHandle that) { return this->Maybe(*that); } |
| |
| bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); } |
| template<class TypeHandle> |
| bool Equals(TypeHandle that) { return this->Equals(*that); } |
| |
| // Equivalent to Constant(val)->Is(this), but avoiding allocation. |
| bool Contains(i::Object* val); |
| bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } |
| |
| // State-dependent versions of the above that consider subtyping between |
| // a constant and its map class. |
| inline static TypeHandle NowOf(i::Object* value, Region* region); |
| static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) { |
| return NowOf(*value, region); |
| } |
| bool NowIs(TypeImpl* that); |
| template<class TypeHandle> |
| bool NowIs(TypeHandle that) { return this->NowIs(*that); } |
| inline bool NowContains(i::Object* val); |
| bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } |
| |
| bool NowStable(); |
| |
| // Inspection. |
| |
| bool IsClass() { |
| return Config::is_class(this) |
| || Config::is_struct(this, StructuralType::kClassTag); |
| } |
| bool IsConstant() { |
| return Config::is_struct(this, StructuralType::kConstantTag); |
| } |
| bool IsRange() { |
| return Config::is_struct(this, StructuralType::kRangeTag); |
| } |
| bool IsContext() { |
| return Config::is_struct(this, StructuralType::kContextTag); |
| } |
| bool IsArray() { |
| return Config::is_struct(this, StructuralType::kArrayTag); |
| } |
| bool IsFunction() { |
| return Config::is_struct(this, StructuralType::kFunctionTag); |
| } |
| |
| ClassType* AsClass() { return ClassType::cast(this); } |
| ConstantType* AsConstant() { return ConstantType::cast(this); } |
| RangeType* AsRange() { return RangeType::cast(this); } |
| ContextType* AsContext() { return ContextType::cast(this); } |
| ArrayType* AsArray() { return ArrayType::cast(this); } |
| FunctionType* AsFunction() { return FunctionType::cast(this); } |
| |
| // Minimum and maximum of a numeric type. |
| // These functions do not distinguish between -0 and +0. If the type equals |
| // kNaN, they return NaN; otherwise kNaN is ignored. Only call these |
| // functions on subtypes of Number. |
| double Min(); |
| double Max(); |
| |
| int NumClasses(); |
| int NumConstants(); |
| |
| template<class T> class Iterator; |
| Iterator<i::Map> Classes() { |
| if (this->IsBitset()) return Iterator<i::Map>(); |
| return Iterator<i::Map>(Config::handle(this)); |
| } |
| Iterator<i::Object> Constants() { |
| if (this->IsBitset()) return Iterator<i::Object>(); |
| return Iterator<i::Object>(Config::handle(this)); |
| } |
| |
| // Casting and conversion. |
| |
| static inline TypeImpl* cast(typename Config::Base* object); |
| |
| template<class OtherTypeImpl> |
| static TypeHandle Convert( |
| typename OtherTypeImpl::TypeHandle type, Region* region); |
| |
| // Printing. |
| |
| enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; |
| |
| void PrintTo(OStream& os, PrintDimension dim = BOTH_DIMS); // NOLINT |
| |
| #ifdef DEBUG |
| void Print(); |
| #endif |
| |
| protected: |
| // Friends. |
| |
| template<class> friend class Iterator; |
| template<class> friend class TypeImpl; |
| |
| // Handle conversion. |
| |
| template<class T> |
| static typename Config::template Handle<T>::type handle(T* type) { |
| return Config::handle(type); |
| } |
| TypeImpl* unhandle() { return this; } |
| |
| // Internal inspection. |
| |
| bool IsNone() { return this == None(); } |
| bool IsAny() { return this == Any(); } |
| bool IsBitset() { return Config::is_bitset(this); } |
| bool IsUnion() { return Config::is_struct(this, StructuralType::kUnionTag); } |
| |
| bitset AsBitset() { |
| DCHECK(this->IsBitset()); |
| return static_cast<BitsetType*>(this)->Bitset(); |
| } |
| UnionType* AsUnion() { return UnionType::cast(this); } |
| |
| // Auxiliary functions. |
| |
| bitset BitsetGlb() { return BitsetType::Glb(this); } |
| bitset BitsetLub() { return BitsetType::Lub(this); } |
| |
| bool SlowIs(TypeImpl* that); |
| |
| static bool IsInteger(double x) { |
| return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. |
| } |
| static bool IsInteger(i::Object* x) { |
| return x->IsNumber() && IsInteger(x->Number()); |
| } |
| |
| struct Limits { |
| i::Handle<i::Object> min; |
| i::Handle<i::Object> max; |
| Limits(i::Handle<i::Object> min, i::Handle<i::Object> max) : |
| min(min), max(max) {} |
| explicit Limits(RangeType* range) : |
| min(range->Min()), max(range->Max()) {} |
| }; |
| |
| static Limits Intersect(Limits lhs, Limits rhs); |
| static Limits Union(Limits lhs, Limits rhs); |
| static bool Overlap(RangeType* lhs, RangeType* rhs); |
| static bool Contains(RangeType* lhs, RangeType* rhs); |
| static bool Contains(RangeType* range, i::Object* val); |
| |
| RangeType* GetRange(); |
| static int UpdateRange( |
| RangeHandle type, UnionHandle result, int size, Region* region); |
| |
| bool SimplyEquals(TypeImpl* that); |
| template<class TypeHandle> |
| bool SimplyEquals(TypeHandle that) { return this->SimplyEquals(*that); } |
| |
| static int AddToUnion( |
| TypeHandle type, UnionHandle result, int size, Region* region); |
| static int IntersectAux( |
| TypeHandle type, TypeHandle other, |
| UnionHandle result, int size, Region* region); |
| static TypeHandle NormalizeUnion(UnionHandle unioned, int size); |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Bitset types (internal). |
| |
| template<class Config> |
| class TypeImpl<Config>::BitsetType : public TypeImpl<Config> { |
| protected: |
| friend class TypeImpl<Config>; |
| |
| enum { |
| #define DECLARE_TYPE(type, value) k##type = (value), |
| BITSET_TYPE_LIST(DECLARE_TYPE) |
| #undef DECLARE_TYPE |
| kUnusedEOL = 0 |
| }; |
| |
| bitset Bitset() { return Config::as_bitset(this); } |
| |
| static TypeImpl* New(bitset bits) { |
| DCHECK(bits == kNone || IsInhabited(bits)); |
| return Config::from_bitset(bits); |
| } |
| static TypeHandle New(bitset bits, Region* region) { |
| DCHECK(bits == kNone || IsInhabited(bits)); |
| return Config::from_bitset(bits, region); |
| } |
| // TODO(neis): Eventually allow again for types with empty semantics |
| // part and modify intersection and possibly subtyping accordingly. |
| |
| static bool IsInhabited(bitset bits) { |
| return bits & kSemantic; |
| } |
| |
| static bool Is(bitset bits1, bitset bits2) { |
| return (bits1 | bits2) == bits2; |
| } |
| |
| static double Min(bitset); |
| static double Max(bitset); |
| |
| static bitset Glb(TypeImpl* type); // greatest lower bound that's a bitset |
| static bitset Lub(TypeImpl* type); // least upper bound that's a bitset |
| static bitset Lub(i::Object* value); |
| static bitset Lub(double value); |
| static bitset Lub(int32_t value); |
| static bitset Lub(uint32_t value); |
| static bitset Lub(i::Map* map); |
| static bitset Lub(Limits lim); |
| |
| static const char* Name(bitset); |
| static void Print(OStream& os, bitset); // NOLINT |
| #ifdef DEBUG |
| static void Print(bitset); |
| #endif |
| |
| private: |
| struct BitsetMin{ |
| bitset bits; |
| double min; |
| }; |
| static const BitsetMin BitsetMins31[]; |
| static const BitsetMin BitsetMins32[]; |
| static const BitsetMin* BitsetMins() { |
| return i::SmiValuesAre31Bits() ? BitsetMins31 : BitsetMins32; |
| } |
| static size_t BitsetMinsSize() { |
| return i::SmiValuesAre31Bits() ? 7 : 5; |
| /* arraysize(BitsetMins31) : arraysize(BitsetMins32); */ |
| // Using arraysize here doesn't compile on Windows. |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Superclass for non-bitset types (internal). |
| // Contains a tag and a variable number of type or value fields. |
| |
| template<class Config> |
| class TypeImpl<Config>::StructuralType : public TypeImpl<Config> { |
| protected: |
| template<class> friend class TypeImpl; |
| friend struct ZoneTypeConfig; // For tags. |
| friend struct HeapTypeConfig; |
| |
| enum Tag { |
| kClassTag, |
| kConstantTag, |
| kRangeTag, |
| kContextTag, |
| kArrayTag, |
| kFunctionTag, |
| kUnionTag |
| }; |
| |
| int Length() { |
| return Config::struct_length(Config::as_struct(this)); |
| } |
| TypeHandle Get(int i) { |
| DCHECK(0 <= i && i < this->Length()); |
| return Config::struct_get(Config::as_struct(this), i); |
| } |
| void Set(int i, TypeHandle type) { |
| DCHECK(0 <= i && i < this->Length()); |
| Config::struct_set(Config::as_struct(this), i, type); |
| } |
| void Shrink(int length) { |
| DCHECK(2 <= length && length <= this->Length()); |
| Config::struct_shrink(Config::as_struct(this), length); |
| } |
| template<class V> i::Handle<V> GetValue(int i) { |
| DCHECK(0 <= i && i < this->Length()); |
| return Config::template struct_get_value<V>(Config::as_struct(this), i); |
| } |
| template<class V> void SetValue(int i, i::Handle<V> x) { |
| DCHECK(0 <= i && i < this->Length()); |
| Config::struct_set_value(Config::as_struct(this), i, x); |
| } |
| |
| static TypeHandle New(Tag tag, int length, Region* region) { |
| DCHECK(1 <= length); |
| return Config::from_struct(Config::struct_create(tag, length, region)); |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Union types (internal). |
| // A union is a structured type with the following invariants: |
| // - its length is at least 2 |
| // - at most one field is a bitset, and it must go into index 0 |
| // - no field is a union |
| // - no field is a subtype of any other field |
| template<class Config> |
| class TypeImpl<Config>::UnionType : public StructuralType { |
| public: |
| static UnionHandle New(int length, Region* region) { |
| return Config::template cast<UnionType>( |
| StructuralType::New(StructuralType::kUnionTag, length, region)); |
| } |
| |
| static UnionType* cast(TypeImpl* type) { |
| DCHECK(type->IsUnion()); |
| return static_cast<UnionType*>(type); |
| } |
| |
| bool Wellformed(); |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Class types. |
| |
| template<class Config> |
| class TypeImpl<Config>::ClassType : public StructuralType { |
| public: |
| TypeHandle Bound(Region* region) { |
| return Config::is_class(this) ? |
| BitsetType::New(BitsetType::Lub(*Config::as_class(this)), region) : |
| this->Get(0); |
| } |
| i::Handle<i::Map> Map() { |
| return Config::is_class(this) ? Config::as_class(this) : |
| this->template GetValue<i::Map>(1); |
| } |
| |
| static ClassHandle New(i::Handle<i::Map> map, Region* region) { |
| ClassHandle type = |
| Config::template cast<ClassType>(Config::from_class(map, region)); |
| if (!type->IsClass()) { |
| type = Config::template cast<ClassType>( |
| StructuralType::New(StructuralType::kClassTag, 2, region)); |
| type->Set(0, BitsetType::New(BitsetType::Lub(*map), region)); |
| type->SetValue(1, map); |
| } |
| return type; |
| } |
| |
| static ClassType* cast(TypeImpl* type) { |
| DCHECK(type->IsClass()); |
| return static_cast<ClassType*>(type); |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Constant types. |
| |
| template<class Config> |
| class TypeImpl<Config>::ConstantType : public StructuralType { |
| public: |
| TypeHandle Bound() { return this->Get(0); } |
| i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); } |
| |
| static ConstantHandle New(i::Handle<i::Object> value, Region* region) { |
| ConstantHandle type = Config::template cast<ConstantType>( |
| StructuralType::New(StructuralType::kConstantTag, 2, region)); |
| type->Set(0, BitsetType::New(BitsetType::Lub(*value), region)); |
| type->SetValue(1, value); |
| return type; |
| } |
| |
| static ConstantType* cast(TypeImpl* type) { |
| DCHECK(type->IsConstant()); |
| return static_cast<ConstantType*>(type); |
| } |
| }; |
| // TODO(neis): Also cache value if numerical. |
| // TODO(neis): Allow restricting the representation. |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Range types. |
| |
| template<class Config> |
| class TypeImpl<Config>::RangeType : public StructuralType { |
| public: |
| int BitsetLub() { return this->Get(0)->AsBitset(); } |
| i::Handle<i::Object> Min() { return this->template GetValue<i::Object>(1); } |
| i::Handle<i::Object> Max() { return this->template GetValue<i::Object>(2); } |
| |
| static RangeHandle New( |
| i::Handle<i::Object> min, i::Handle<i::Object> max, Region* region) { |
| DCHECK(min->Number() <= max->Number()); |
| RangeHandle type = Config::template cast<RangeType>( |
| StructuralType::New(StructuralType::kRangeTag, 3, region)); |
| type->Set(0, BitsetType::New(BitsetType::Lub(Limits(min, max)), region)); |
| type->SetValue(1, min); |
| type->SetValue(2, max); |
| return type; |
| } |
| |
| static RangeHandle New(Limits lim, Region* region) { |
| return New(lim.min, lim.max, region); |
| } |
| |
| static RangeType* cast(TypeImpl* type) { |
| DCHECK(type->IsRange()); |
| return static_cast<RangeType*>(type); |
| } |
| }; |
| // TODO(neis): Also cache min and max values. |
| // TODO(neis): Allow restricting the representation. |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Context types. |
| |
| template<class Config> |
| class TypeImpl<Config>::ContextType : public StructuralType { |
| public: |
| TypeHandle Outer() { return this->Get(0); } |
| |
| static ContextHandle New(TypeHandle outer, Region* region) { |
| ContextHandle type = Config::template cast<ContextType>( |
| StructuralType::New(StructuralType::kContextTag, 1, region)); |
| type->Set(0, outer); |
| return type; |
| } |
| |
| static ContextType* cast(TypeImpl* type) { |
| DCHECK(type->IsContext()); |
| return static_cast<ContextType*>(type); |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Array types. |
| |
| template<class Config> |
| class TypeImpl<Config>::ArrayType : public StructuralType { |
| public: |
| TypeHandle Element() { return this->Get(0); } |
| |
| static ArrayHandle New(TypeHandle element, Region* region) { |
| ArrayHandle type = Config::template cast<ArrayType>( |
| StructuralType::New(StructuralType::kArrayTag, 1, region)); |
| type->Set(0, element); |
| return type; |
| } |
| |
| static ArrayType* cast(TypeImpl* type) { |
| DCHECK(type->IsArray()); |
| return static_cast<ArrayType*>(type); |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Function types. |
| |
| template<class Config> |
| class TypeImpl<Config>::FunctionType : public StructuralType { |
| public: |
| int Arity() { return this->Length() - 2; } |
| TypeHandle Result() { return this->Get(0); } |
| TypeHandle Receiver() { return this->Get(1); } |
| TypeHandle Parameter(int i) { return this->Get(2 + i); } |
| |
| void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); } |
| |
| static FunctionHandle New( |
| TypeHandle result, TypeHandle receiver, int arity, Region* region) { |
| FunctionHandle type = Config::template cast<FunctionType>( |
| StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region)); |
| type->Set(0, result); |
| type->Set(1, receiver); |
| return type; |
| } |
| |
| static FunctionType* cast(TypeImpl* type) { |
| DCHECK(type->IsFunction()); |
| return static_cast<FunctionType*>(type); |
| } |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Type iterators. |
| |
| template<class Config> template<class T> |
| class TypeImpl<Config>::Iterator { |
| public: |
| bool Done() const { return index_ < 0; } |
| i::Handle<T> Current(); |
| void Advance(); |
| |
| private: |
| template<class> friend class TypeImpl; |
| |
| Iterator() : index_(-1) {} |
| explicit Iterator(TypeHandle type) : type_(type), index_(-1) { |
| Advance(); |
| } |
| |
| inline bool matches(TypeHandle type); |
| inline TypeHandle get_type(); |
| |
| TypeHandle type_; |
| int index_; |
| }; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Zone-allocated types; they are either (odd) integers to represent bitsets, or |
| // (even) pointers to structures for everything else. |
| |
| struct ZoneTypeConfig { |
| typedef TypeImpl<ZoneTypeConfig> Type; |
| class Base {}; |
| typedef void* Struct; |
| typedef i::Zone Region; |
| template<class T> struct Handle { typedef T* type; }; |
| |
| template<class T> static inline T* handle(T* type); |
| template<class T> static inline T* cast(Type* type); |
| |
| static inline bool is_bitset(Type* type); |
| static inline bool is_class(Type* type); |
| static inline bool is_struct(Type* type, int tag); |
| |
| static inline Type::bitset as_bitset(Type* type); |
| static inline i::Handle<i::Map> as_class(Type* type); |
| static inline Struct* as_struct(Type* type); |
| |
| static inline Type* from_bitset(Type::bitset); |
| static inline Type* from_bitset(Type::bitset, Zone* zone); |
| static inline Type* from_class(i::Handle<i::Map> map, Zone* zone); |
| static inline Type* from_struct(Struct* structured); |
| |
| static inline Struct* struct_create(int tag, int length, Zone* zone); |
| static inline void struct_shrink(Struct* structure, int length); |
| static inline int struct_tag(Struct* structure); |
| static inline int struct_length(Struct* structure); |
| static inline Type* struct_get(Struct* structure, int i); |
| static inline void struct_set(Struct* structure, int i, Type* type); |
| template<class V> |
| static inline i::Handle<V> struct_get_value(Struct* structure, int i); |
| template<class V> static inline void struct_set_value( |
| Struct* structure, int i, i::Handle<V> x); |
| }; |
| |
| typedef TypeImpl<ZoneTypeConfig> Type; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Heap-allocated types; either smis for bitsets, maps for classes, boxes for |
| // constants, or fixed arrays for unions. |
| |
| struct HeapTypeConfig { |
| typedef TypeImpl<HeapTypeConfig> Type; |
| typedef i::Object Base; |
| typedef i::FixedArray Struct; |
| typedef i::Isolate Region; |
| template<class T> struct Handle { typedef i::Handle<T> type; }; |
| |
| template<class T> static inline i::Handle<T> handle(T* type); |
| template<class T> static inline i::Handle<T> cast(i::Handle<Type> type); |
| |
| static inline bool is_bitset(Type* type); |
| static inline bool is_class(Type* type); |
| static inline bool is_struct(Type* type, int tag); |
| |
| static inline Type::bitset as_bitset(Type* type); |
| static inline i::Handle<i::Map> as_class(Type* type); |
| static inline i::Handle<Struct> as_struct(Type* type); |
| |
| static inline Type* from_bitset(Type::bitset); |
| static inline i::Handle<Type> from_bitset(Type::bitset, Isolate* isolate); |
| static inline i::Handle<Type> from_class( |
| i::Handle<i::Map> map, Isolate* isolate); |
| static inline i::Handle<Type> from_struct(i::Handle<Struct> structure); |
| |
| static inline i::Handle<Struct> struct_create( |
| int tag, int length, Isolate* isolate); |
| static inline void struct_shrink(i::Handle<Struct> structure, int length); |
| static inline int struct_tag(i::Handle<Struct> structure); |
| static inline int struct_length(i::Handle<Struct> structure); |
| static inline i::Handle<Type> struct_get(i::Handle<Struct> structure, int i); |
| static inline void struct_set( |
| i::Handle<Struct> structure, int i, i::Handle<Type> type); |
| template<class V> |
| static inline i::Handle<V> struct_get_value( |
| i::Handle<Struct> structure, int i); |
| template<class V> |
| static inline void struct_set_value( |
| i::Handle<Struct> structure, int i, i::Handle<V> x); |
| }; |
| |
| typedef TypeImpl<HeapTypeConfig> HeapType; |
| |
| |
| // ----------------------------------------------------------------------------- |
| // Type bounds. A simple struct to represent a pair of lower/upper types. |
| |
| template<class Config> |
| struct BoundsImpl { |
| typedef TypeImpl<Config> Type; |
| typedef typename Type::TypeHandle TypeHandle; |
| typedef typename Type::Region Region; |
| |
| TypeHandle lower; |
| TypeHandle upper; |
| |
| BoundsImpl() {} |
| explicit BoundsImpl(TypeHandle t) : lower(t), upper(t) {} |
| BoundsImpl(TypeHandle l, TypeHandle u) : lower(l), upper(u) { |
| DCHECK(lower->Is(upper)); |
| } |
| |
| // Unrestricted bounds. |
| static BoundsImpl Unbounded(Region* region) { |
| return BoundsImpl(Type::None(region), Type::Any(region)); |
| } |
| |
| // Meet: both b1 and b2 are known to hold. |
| static BoundsImpl Both(BoundsImpl b1, BoundsImpl b2, Region* region) { |
| TypeHandle lower = Type::Union(b1.lower, b2.lower, region); |
| TypeHandle upper = Type::Intersect(b1.upper, b2.upper, region); |
| // Lower bounds are considered approximate, correct as necessary. |
| lower = Type::Intersect(lower, upper, region); |
| return BoundsImpl(lower, upper); |
| } |
| |
| // Join: either b1 or b2 is known to hold. |
| static BoundsImpl Either(BoundsImpl b1, BoundsImpl b2, Region* region) { |
| TypeHandle lower = Type::Intersect(b1.lower, b2.lower, region); |
| TypeHandle upper = Type::Union(b1.upper, b2.upper, region); |
| return BoundsImpl(lower, upper); |
| } |
| |
| static BoundsImpl NarrowLower(BoundsImpl b, TypeHandle t, Region* region) { |
| // Lower bounds are considered approximate, correct as necessary. |
| t = Type::Intersect(t, b.upper, region); |
| TypeHandle lower = Type::Union(b.lower, t, region); |
| return BoundsImpl(lower, b.upper); |
| } |
| static BoundsImpl NarrowUpper(BoundsImpl b, TypeHandle t, Region* region) { |
| TypeHandle lower = Type::Intersect(b.lower, t, region); |
| TypeHandle upper = Type::Intersect(b.upper, t, region); |
| return BoundsImpl(lower, upper); |
| } |
| |
| bool Narrows(BoundsImpl that) { |
| return that.lower->Is(this->lower) && this->upper->Is(that.upper); |
| } |
| }; |
| |
| typedef BoundsImpl<ZoneTypeConfig> Bounds; |
| |
| } } // namespace v8::internal |
| |
| #endif // V8_TYPES_H_ |