#ifndef V8_TYPES_H_
#define V8_TYPES_H_
-#include "handles.h"
+#include "src/conversions.h"
+#include "src/factory.h"
+#include "src/handles.h"
+#include "src/ostreams.h"
namespace v8 {
namespace internal {
// 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:
// 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.
-// Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can
+// 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 <= UntaggedInt8 \/ UntaggedInt16 \/ UntaggedInt32)
-// UntaggedFloat <= UntaggedFloat32 \/ UntaggedFloat64
-// UntaggedNumber <= UntaggedInt \/ UntaggedFloat
-// Untagged <= UntaggedNumber \/ UntaggedPtr
-// Tagged <= TaggedInt \/ TaggedPtr
+// UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/
+// UntaggedInt16 \/ UntaggedInt32
+// UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64
+// UntaggedNumber = UntaggedInt \/ UntaggedFloat
+// Untagged = UntaggedNumber \/ UntaggedPtr
+// Tagged = TaggedInt \/ TaggedPtr
//
// Subtyping relates the two dimensions, for example:
//
// 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:
// 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, subtyping is a complete
-// partial order, union and intersection satisfy the usual algebraic properties.
+// 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. Class is a heap pointer to the respective map. Only Constant's, or
-// unions containing Class'es or Constant's, currently require allocation.
+// 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:
// 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, static_cast<int>(0xff800000)) \
- V(Semantic, static_cast<int>(0x007fffff))
+ V(Representation, 0xff800000u) \
+ V(Semantic, 0x007ffffeu)
-#define REPRESENTATION(k) ((k) & kRepresentation)
-#define SEMANTIC(k) ((k) & kSemantic)
+#define REPRESENTATION(k) ((k) & BitsetType::kRepresentation)
+#define SEMANTIC(k) ((k) & BitsetType::kSemantic)
#define REPRESENTATION_BITSET_TYPE_LIST(V) \
V(None, 0) \
- V(UntaggedInt8, 1 << 23 | kSemantic) \
- V(UntaggedInt16, 1 << 24 | kSemantic) \
- V(UntaggedInt32, 1 << 25 | kSemantic) \
- V(UntaggedFloat32, 1 << 26 | kSemantic) \
- V(UntaggedFloat64, 1 << 27 | kSemantic) \
- V(UntaggedPtr, 1 << 28 | kSemantic) \
- V(TaggedInt, 1 << 29 | kSemantic) \
- V(TaggedPtr, -1 << 30 | kSemantic) /* MSB has to be sign-extended */ \
+ 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, kUntaggedInt8 | kUntaggedInt16 | kUntaggedInt32) \
- V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \
- V(UntaggedNumber, kUntaggedInt | kUntaggedFloat) \
- V(Untagged, kUntaggedNumber | kUntaggedPtr) \
+ 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, 1 << 0 | REPRESENTATION(kTaggedPtr)) \
- V(Undefined, 1 << 1 | REPRESENTATION(kTaggedPtr)) \
- V(Boolean, 1 << 2 | REPRESENTATION(kTaggedPtr)) \
- V(SignedSmall, 1 << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \
- V(OtherSigned32, 1 << 4 | REPRESENTATION(kTagged | kUntaggedNumber)) \
- V(Unsigned32, 1 << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \
- V(Float, 1 << 6 | REPRESENTATION(kTagged | kUntaggedNumber)) \
- V(Float32x4, 1 << 7 | REPRESENTATION(kTaggedPtr)) \
- V(Float64x2, 1 << 8 | REPRESENTATION(kTaggedPtr)) \
- V(Int32x4, 1 << 9 | REPRESENTATION(kTaggedPtr)) \
- V(Symbol, 1 << 10 | REPRESENTATION(kTaggedPtr)) \
- V(InternalizedString, 1 << 11 | REPRESENTATION(kTaggedPtr)) \
- V(OtherString, 1 << 12 | REPRESENTATION(kTaggedPtr)) \
- V(Undetectable, 1 << 13 | REPRESENTATION(kTaggedPtr)) \
- V(Array, 1 << 14 | REPRESENTATION(kTaggedPtr)) \
- V(Function, 1 << 15 | REPRESENTATION(kTaggedPtr)) \
- V(RegExp, 1 << 16 | REPRESENTATION(kTaggedPtr)) \
- V(OtherObject, 1 << 17 | REPRESENTATION(kTaggedPtr)) \
- V(Proxy, 1 << 18 | REPRESENTATION(kTaggedPtr)) \
- V(Internal, 1 << 19 | REPRESENTATION(kTagged | kUntagged)) \
+ 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(Signed32, kSignedSmall | kOtherSigned32) \
- V(Number, kSigned32 | kUnsigned32 | kFloat) \
- V(String, kInternalizedString | kOtherString) \
- V(UniqueName, kSymbol | kInternalizedString) \
- V(Name, kSymbol | kString) \
- V(NumberOrString, kNumber | kString) \
- 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 | \
- kFloat32x4 | kFloat64x2 | kInt32x4 | \
- kUndefined | kInternal) \
- V(Any, -1)
+ 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) \
- REPRESENTATION_BITSET_TYPE_LIST(V) \
- SEMANTIC_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;
// template<class T> static Handle<T>::type cast(Handle<Type>::type);
// static bool is_bitset(Type*);
// static bool is_class(Type*);
-// static bool is_constant(Type*);
// static bool is_struct(Type*, int tag);
-// static int as_bitset(Type*);
+// static bitset as_bitset(Type*);
// static i::Handle<i::Map> as_class(Type*);
-// static i::Handle<i::Object> as_constant(Type*);
// static Handle<Struct>::type as_struct(Type*);
-// static Type* from_bitset(int bitset);
-// static Handle<Type>::type from_bitset(int bitset, Region*);
-// static Handle<Type>::type from_class(i::Handle<Map>, int lub, Region*);
-// static Handle<Type>::type from_constant(i::Handle<Object>, int, Region*);
+// 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_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);
-// static int lub_bitset(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:
- class BitsetType; // Internal
- class StructuralType; // Internal
- class UnionType; // Internal
+ // 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 TypeImpl* type() { \
+ return BitsetType::New(BitsetType::k##type); \
+ } \
static TypeHandle type(Region* region) { \
return BitsetType::New(BitsetType::k##type, region); \
}
- BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
+ PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
#undef DEFINE_TYPE_CONSTRUCTOR
static TypeHandle Class(i::Handle<i::Map> map, Region* 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);
}
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);
}
return Of(*value, region);
}
- bool IsInhabited() {
- return !this->IsBitset() || BitsetType::IsInhabited(this->AsBitset());
- }
+ // Predicates.
+
+ bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); }
bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); }
template<class TypeHandle>
template<class TypeHandle>
bool Equals(TypeHandle that) { return this->Equals(*that); }
- // Equivalent to Constant(value)->Is(this), but avoiding allocation.
+ // 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 Of and Is that consider subtyping between
+ // State-dependent versions of the above that consider subtyping between
// a constant and its map class.
- static TypeHandle NowOf(i::Object* value, Region* region);
+ inline static TypeHandle NowOf(i::Object* value, Region* region);
static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) {
return NowOf(*value, region);
}
bool NowStable();
- bool IsClass() { return Config::is_class(this); }
- bool IsConstant() { return Config::is_constant(this); }
- bool IsArray() { return Config::is_struct(this, StructuralType::kArrayTag); }
+ // 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();
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 TypePrint(PrintDimension = BOTH_DIMS);
- void TypePrint(FILE* out, PrintDimension = BOTH_DIMS);
+
+ 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); }
- int AsBitset() {
- ASSERT(this->IsBitset());
+ 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);
- bool InUnion(UnionHandle unioned, int current_size);
- static int ExtendUnion(
- UnionHandle unioned, TypeHandle t, int current_size);
- static int ExtendIntersection(
- UnionHandle unioned, TypeHandle t, TypeHandle other, int current_size);
+ 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);
- int BitsetGlb() { return BitsetType::Glb(this); }
- int BitsetLub() { return BitsetType::Lub(this); }
+ 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> {
- private:
+ protected:
friend class TypeImpl<Config>;
enum {
kUnusedEOL = 0
};
- int Bitset() { return Config::as_bitset(this); }
+ bitset Bitset() { return Config::as_bitset(this); }
- static BitsetType* New(int bitset) {
- return static_cast<BitsetType*>(Config::from_bitset(bitset));
+ 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);
}
- static TypeHandle New(int bitset, Region* region) {
- return Config::from_bitset(bitset, 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 IsInhabited(int bitset) {
- return (bitset & kRepresentation) && (bitset & kSemantic);
+ static bool Is(bitset bits1, bitset bits2) {
+ return (bits1 | bits2) == bits2;
}
- static int Glb(TypeImpl* type); // greatest lower bound that's a bitset
- static int Lub(TypeImpl* type); // least upper bound that's a bitset
- static int Lub(i::Object* value);
- static int Lub(i::Map* map);
+ 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(int bitset);
- static void BitsetTypePrint(FILE* out, int bitset);
+ 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.
+ }
};
-// Internal
-// A structured type contains a tag and a variable number of type fields.
+// -----------------------------------------------------------------------------
+// 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:
enum Tag {
kClassTag,
kConstantTag,
+ kRangeTag,
+ kContextTag,
kArrayTag,
kFunctionTag,
kUnionTag
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 TypeImpl<Config> {
+class TypeImpl<Config>::ClassType : public StructuralType {
public:
- i::Handle<i::Map> Map() { return Config::as_class(this); }
+ 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) {
- return Config::template cast<ClassType>(
- Config::from_class(map, BitsetType::Lub(*map), 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) {
- ASSERT(type->IsClass());
+ DCHECK(type->IsClass());
return static_cast<ClassType*>(type);
}
};
+// -----------------------------------------------------------------------------
+// Constant types.
+
template<class Config>
-class TypeImpl<Config>::ConstantType : public TypeImpl<Config> {
+class TypeImpl<Config>::ConstantType : public StructuralType {
public:
- i::Handle<i::Object> Value() { return Config::as_constant(this); }
+ 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) {
- return Config::template cast<ConstantType>(
- Config::from_constant(value, BitsetType::Lub(*value), 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) {
- ASSERT(type->IsConstant());
+ DCHECK(type->IsConstant());
return static_cast<ConstantType*>(type);
}
};
+// TODO(neis): Also cache value if numerical.
+// TODO(neis): Allow restricting the representation.
-// 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
+// -----------------------------------------------------------------------------
+// Range types.
+
template<class Config>
-class TypeImpl<Config>::UnionType : public StructuralType {
+class TypeImpl<Config>::RangeType : public StructuralType {
public:
- static UnionHandle New(int length, Region* region) {
- return Config::template cast<UnionType>(
- StructuralType::New(StructuralType::kUnionTag, length, region));
+ 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 UnionType* cast(TypeImpl* type) {
- ASSERT(type->IsUnion());
- return static_cast<UnionType*>(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:
}
static ArrayType* cast(TypeImpl* type) {
- ASSERT(type->IsArray());
+ DCHECK(type->IsArray());
return static_cast<ArrayType*>(type);
}
};
+// -----------------------------------------------------------------------------
+// Function types.
+
template<class Config>
class TypeImpl<Config>::FunctionType : public StructuralType {
public:
}
static FunctionType* cast(TypeImpl* type) {
- ASSERT(type->IsFunction());
+ DCHECK(type->IsFunction());
return static_cast<FunctionType*>(type);
}
};
+// -----------------------------------------------------------------------------
+// Type iterators.
+
template<class Config> template<class T>
class TypeImpl<Config>::Iterator {
public:
};
-// Zone-allocated types are either (odd) integers to represent bitsets, or
+// -----------------------------------------------------------------------------
+// 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 {};
static inline bool is_bitset(Type* type);
static inline bool is_class(Type* type);
- static inline bool is_constant(Type* type);
static inline bool is_struct(Type* type, int tag);
- static inline int as_bitset(Type* type);
- static inline Struct* as_struct(Type* type);
+ static inline Type::bitset as_bitset(Type* type);
static inline i::Handle<i::Map> as_class(Type* type);
- static inline i::Handle<i::Object> as_constant(Type* type);
+ static inline Struct* as_struct(Type* type);
- static inline Type* from_bitset(int bitset);
- static inline Type* from_bitset(int bitset, Zone* zone);
+ 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 Type* from_class(i::Handle<i::Map> map, int lub, Zone* zone);
- static inline Type* from_constant(
- i::Handle<i::Object> value, int lub, Zone* zone);
static inline Struct* struct_create(int tag, int length, Zone* zone);
- static inline void struct_shrink(Struct* structured, int length);
- static inline int struct_tag(Struct* structured);
- static inline int struct_length(Struct* structured);
- static inline Type* struct_get(Struct* structured, int i);
- static inline void struct_set(Struct* structured, int i, Type* type);
-
- static inline int lub_bitset(Type* type);
+ 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 are either smis for bitsets, maps for classes, boxes for
+// -----------------------------------------------------------------------------
+// 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;
static inline bool is_bitset(Type* type);
static inline bool is_class(Type* type);
- static inline bool is_constant(Type* type);
static inline bool is_struct(Type* type, int tag);
- static inline int as_bitset(Type* type);
+ static inline Type::bitset as_bitset(Type* type);
static inline i::Handle<i::Map> as_class(Type* type);
- static inline i::Handle<i::Object> as_constant(Type* type);
static inline i::Handle<Struct> as_struct(Type* type);
- static inline Type* from_bitset(int bitset);
- static inline i::Handle<Type> from_bitset(int bitset, Isolate* isolate);
+ 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, int lub, Isolate* isolate);
- static inline i::Handle<Type> from_constant(
- i::Handle<i::Object> value, int lub, Isolate* isolate);
- static inline i::Handle<Type> from_struct(i::Handle<Struct> structured);
+ 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> structured, int length);
- static inline int struct_tag(i::Handle<Struct> structured);
- static inline int struct_length(i::Handle<Struct> structured);
- static inline i::Handle<Type> struct_get(i::Handle<Struct> structured, int i);
+ 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> structured, int i, i::Handle<Type> type);
-
- static inline int lub_bitset(Type* type);
+ 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;
-// A simple struct to represent a pair of lower/upper type bounds.
+// -----------------------------------------------------------------------------
+// Type bounds. A simple struct to represent a pair of lower/upper types.
+
template<class Config>
struct BoundsImpl {
typedef TypeImpl<Config> Type;
BoundsImpl() {}
explicit BoundsImpl(TypeHandle t) : lower(t), upper(t) {}
BoundsImpl(TypeHandle l, TypeHandle u) : lower(l), upper(u) {
- ASSERT(lower->Is(upper));
+ DCHECK(lower->Is(upper));
}
// Unrestricted bounds.
projects / platform / framework / web / crosswalk.git / blobdiff