-// Copyright 2013 the V8 project authors. All rights reserved.
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are
-// met:
-//
-// * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-// * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following
-// disclaimer in the documentation and/or other materials provided
-// with the distribution.
-// * Neither the name of Google Inc. nor the names of its
-// contributors may be used to endorse or promote products derived
-// from this software without specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+// 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 "v8.h"
-
-#include "objects.h"
+#include "handles.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
// 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
//
-// Oddball = Boolean \/ Null \/ Undefined
// Number = Signed32 \/ Unsigned32 \/ Double
// Smi <= Signed32
// Name = String \/ Symbol
//
// 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
//
+// 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
// 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:
//
// SignedSmall /\ TaggedInt (a 'smi')
// Number /\ TaggedPtr (a heap number)
//
+// PREDICATES
+//
// There are two main functions for testing types:
//
// T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2)
// 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 use pointer equality for type tests, always use Is!
+// 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, subtyping is a complete
+// partial order, union and intersection satisfy the usual algebraic properties.
+//
+// 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
V(Unsigned32, 1 << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \
V(Float, 1 << 6 | REPRESENTATION(kTagged | kUntaggedNumber)) \
V(Float32x4, 1 << 7 | REPRESENTATION(kTaggedPtr)) \
- V(Int32x4, 1 << 8 | REPRESENTATION(kTaggedPtr)) \
- V(Symbol, 1 << 9 | REPRESENTATION(kTaggedPtr)) \
- V(InternalizedString, 1 << 10 | REPRESENTATION(kTaggedPtr)) \
- V(OtherString, 1 << 11 | REPRESENTATION(kTaggedPtr)) \
- V(Undetectable, 1 << 12 | REPRESENTATION(kTaggedPtr)) \
- V(Array, 1 << 13 | REPRESENTATION(kTaggedPtr)) \
- V(Function, 1 << 14 | REPRESENTATION(kTaggedPtr)) \
- V(RegExp, 1 << 15 | REPRESENTATION(kTaggedPtr)) \
- V(OtherObject, 1 << 16 | REPRESENTATION(kTaggedPtr)) \
- V(Proxy, 1 << 17 | REPRESENTATION(kTaggedPtr)) \
- V(Internal, 1 << 18 | REPRESENTATION(kTagged | kUntagged)) \
+ 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(Oddball, kBoolean | kNull | kUndefined) \
V(Signed32, kSignedSmall | kOtherSigned32) \
V(Number, kSigned32 | kUnsigned32 | kFloat) \
V(String, kInternalizedString | kOtherString) \
V(Detectable, kDetectableReceiver | kNumber | kName) \
V(Object, kDetectableObject | kUndetectable) \
V(Receiver, kObject | kProxy) \
- V(NonNumber, kOddball | kName | kFloat32x4 | kInt32x4 | \
- kReceiver | kInternal) \
+ V(NonNumber, kBoolean | kName | kNull | kReceiver | \
+ kFloat32x4 | kFloat64x2 | kInt32x4 | \
+ kUndefined | kInternal) \
V(Any, -1)
#define BITSET_TYPE_LIST(V) \
SEMANTIC_BITSET_TYPE_LIST(V)
// struct Config {
+// typedef TypeImpl<Config> Type;
// typedef Base;
-// typedef Unioned;
+// typedef Struct;
// typedef Region;
// template<class> struct Handle { typedef type; } // No template typedefs...
-// static Handle<Type>::type handle(Type* type); // !is_bitset(type)
+// 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_constant(Type*);
-// static bool is_union(Type*);
+// static bool is_struct(Type*, int tag);
// static int as_bitset(Type*);
// static i::Handle<i::Map> as_class(Type*);
// static i::Handle<i::Object> as_constant(Type*);
-// static Handle<Unioned>::type as_union(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 Handle<Type>::type from_union(Handle<Unioned>::type);
-// static Handle<Unioned>::type union_create(int size, Region*);
-// static void union_shrink(Handle<Unioned>::type, int size);
-// static Handle<Type>::type union_get(Handle<Unioned>::type, int);
-// static void union_set(Handle<Unioned>::type, int, Handle<Type>::type);
-// static int union_length(Handle<Unioned>::type);
+// 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);
// static int lub_bitset(Type*);
// }
template<class Config>
class TypeImpl : public Config::Base {
public:
+ class BitsetType; // Internal
+ class StructuralType; // Internal
+ class UnionType; // Internal
+
+ class ClassType;
+ class ConstantType;
+ 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<ArrayType>::type ArrayHandle;
+ typedef typename Config::template Handle<FunctionType>::type FunctionHandle;
+ typedef typename Config::template Handle<UnionType>::type UnionHandle;
typedef typename Config::Region Region;
- #define DEFINE_TYPE_CONSTRUCTOR(type, value) \
- static TypeImpl* type() { return Config::from_bitset(k##type); } \
- static TypeHandle type(Region* region) { \
- return Config::from_bitset(k##type, region); \
+ #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); \
}
BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
#undef DEFINE_TYPE_CONSTRUCTOR
static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
- return Config::from_class(map, LubBitset(*map), region);
+ return ClassType::New(map, region);
}
static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
- return Config::from_constant(value, LubBitset(*value), region);
+ return ConstantType::New(value, 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 Union(TypeHandle type1, TypeHandle type2, Region* reg);
static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg);
+ 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 Config::from_bitset(LubBitset(*value), region);
+ return Of(*value, region);
+ }
+
+ bool IsInhabited() {
+ return !this->IsBitset() || BitsetType::IsInhabited(this->AsBitset());
}
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(value)->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
// a constant and its map class.
- static TypeHandle OfCurrently(i::Handle<i::Object> value, Region* region);
- bool IsCurrently(TypeImpl* that);
+ 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 IsCurrently(TypeHandle that) { return this->IsCurrently(*that); }
+ 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();
bool IsClass() { return Config::is_class(this); }
bool IsConstant() { return Config::is_constant(this); }
- i::Handle<i::Map> AsClass() { return Config::as_class(this); }
- i::Handle<i::Object> AsConstant() { return Config::as_constant(this); }
+ 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); }
+ ArrayType* AsArray() { return ArrayType::cast(this); }
+ FunctionType* AsFunction() { return FunctionType::cast(this); }
int NumClasses();
int NumConstants();
- template<class T>
- class 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_;
- };
-
+ template<class T> class Iterator;
Iterator<i::Map> Classes() {
if (this->IsBitset()) return Iterator<i::Map>();
return Iterator<i::Map>(Config::handle(this));
return Iterator<i::Object>(Config::handle(this));
}
- static TypeImpl* cast(typename Config::Base* object) {
- TypeImpl* t = static_cast<TypeImpl*>(object);
- ASSERT(t->IsBitset() || t->IsClass() || t->IsConstant() || t->IsUnion());
- return t;
- }
+ static inline TypeImpl* cast(typename Config::Base* object);
template<class OtherTypeImpl>
static TypeHandle Convert(
typename OtherTypeImpl::TypeHandle type, Region* region);
-#ifdef OBJECT_PRINT
enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
void TypePrint(PrintDimension = BOTH_DIMS);
void TypePrint(FILE* out, PrintDimension = BOTH_DIMS);
-#endif
- private:
+ protected:
template<class> friend class Iterator;
template<class> friend class TypeImpl;
- // A union is a fixed array containing types. 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
- typedef typename Config::Unioned Unioned;
- typedef typename Config::template Handle<Unioned>::type UnionedHandle;
+ template<class T>
+ static typename Config::template Handle<T>::type handle(T* type) {
+ return Config::handle(type);
+ }
+
+ 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());
+ return static_cast<BitsetType*>(this)->Bitset();
+ }
+ UnionType* AsUnion() { return UnionType::cast(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);
+
+ int BitsetGlb() { return BitsetType::Glb(this); }
+ int BitsetLub() { return BitsetType::Lub(this); }
+};
+
+
+template<class Config>
+class TypeImpl<Config>::BitsetType : public TypeImpl<Config> {
+ private:
+ friend class TypeImpl<Config>;
enum {
#define DECLARE_TYPE(type, value) k##type = (value),
kUnusedEOL = 0
};
- bool IsNone() { return this == None(); }
- bool IsAny() { return this == Any(); }
- bool IsBitset() { return Config::is_bitset(this); }
- bool IsUnion() { return Config::is_union(this); }
- int AsBitset() { return Config::as_bitset(this); }
- UnionedHandle AsUnion() { return Config::as_union(this); }
+ int Bitset() { return Config::as_bitset(this); }
- static int UnionLength(UnionedHandle unioned) {
- return Config::union_length(unioned);
+ static BitsetType* New(int bitset) {
+ return static_cast<BitsetType*>(Config::from_bitset(bitset));
}
- static TypeHandle UnionGet(UnionedHandle unioned, int i) {
- return Config::union_get(unioned, i);
+ static TypeHandle New(int bitset, Region* region) {
+ return Config::from_bitset(bitset, region);
}
- bool SlowIs(TypeImpl* that);
-
static bool IsInhabited(int bitset) {
return (bitset & kRepresentation) && (bitset & kSemantic);
}
- int LubBitset(); // least upper bound that's a bitset
- int GlbBitset(); // greatest lower bound that's a bitset
-
- static int LubBitset(i::Object* value);
- static int LubBitset(i::Map* map);
-
- bool InUnion(UnionedHandle unioned, int current_size);
- static int ExtendUnion(
- UnionedHandle unioned, TypeHandle t, int current_size);
- static int ExtendIntersection(
- UnionedHandle unioned, TypeHandle t, TypeHandle other, int current_size);
+ 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);
-#ifdef OBJECT_PRINT
- static const char* bitset_name(int bitset);
+ static const char* Name(int bitset);
static void BitsetTypePrint(FILE* out, int bitset);
-#endif
};
-// Zone-allocated types are either (odd) integers to represent bitsets, or
-// (even) pointers to zone lists for everything else. The first slot of every
-// list is an explicit tag value to distinguish representation.
-struct ZoneTypeConfig {
- private:
- typedef i::ZoneList<void*> Tagged;
+// Internal
+// A structured type contains a tag and a variable number of type 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,
+ kArrayTag,
+ kFunctionTag,
kUnionTag
};
- static Tagged* tagged_create(Tag tag, int size, Zone* zone) {
- Tagged* tagged = new(zone) Tagged(size + 1, zone);
- tagged->Add(reinterpret_cast<void*>(tag), zone);
- tagged->AddBlock(NULL, size, zone);
- return tagged;
+ int Length() {
+ return Config::struct_length(Config::as_struct(this));
}
- static void tagged_shrink(Tagged* tagged, int size) {
- tagged->Rewind(size + 1);
+ TypeHandle Get(int i) {
+ return Config::struct_get(Config::as_struct(this), i);
}
- static Tag tagged_tag(Tagged* tagged) {
- return static_cast<Tag>(reinterpret_cast<intptr_t>(tagged->at(0)));
+ void Set(int i, TypeHandle type) {
+ Config::struct_set(Config::as_struct(this), i, type);
}
- template<class T>
- static T tagged_get(Tagged* tagged, int i) {
- return reinterpret_cast<T>(tagged->at(i + 1));
- }
- template<class T>
- static void tagged_set(Tagged* tagged, int i, T value) {
- tagged->at(i + 1) = reinterpret_cast<void*>(value);
+ void Shrink(int length) {
+ Config::struct_shrink(Config::as_struct(this), length);
}
- static int tagged_length(Tagged* tagged) {
- return tagged->length() - 1;
+
+ static TypeHandle New(Tag tag, int length, Region* region) {
+ return Config::from_struct(Config::struct_create(tag, length, region));
}
+};
- public:
- typedef TypeImpl<ZoneTypeConfig> Type;
- class Base {};
- typedef i::ZoneList<Type*> Unioned;
- typedef i::Zone Region;
- template<class T> struct Handle { typedef T* type; };
- static Type* handle(Type* type) { return type; }
+template<class Config>
+class TypeImpl<Config>::ClassType : public TypeImpl<Config> {
+ public:
+ i::Handle<i::Map> Map() { return Config::as_class(this); }
- static bool is(Type* type, Tag tag) {
- return is_tagged(type) && tagged_tag(as_tagged(type)) == tag;
+ static ClassHandle New(i::Handle<i::Map> map, Region* region) {
+ return Config::template cast<ClassType>(
+ Config::from_class(map, BitsetType::Lub(*map), region));
}
- static bool is_bitset(Type* type) {
- return reinterpret_cast<intptr_t>(type) & 1;
- }
- static bool is_tagged(Type* type) { return !is_bitset(type); }
- static bool is_class(Type* type) { return is(type, kClassTag); }
- static bool is_constant(Type* type) { return is(type, kConstantTag); }
- static bool is_union(Type* type) { return is(type, kUnionTag); }
- static bool tagged_is_union(Tagged* tagged) {
- return is(from_tagged(tagged), kUnionTag);
+ static ClassType* cast(TypeImpl* type) {
+ ASSERT(type->IsClass());
+ return static_cast<ClassType*>(type);
}
+};
- static int as_bitset(Type* type) {
- ASSERT(is_bitset(type));
- return static_cast<int>(reinterpret_cast<intptr_t>(type) >> 1);
- }
- static Tagged* as_tagged(Type* type) {
- ASSERT(is_tagged(type));
- return reinterpret_cast<Tagged*>(type);
- }
- static i::Handle<i::Map> as_class(Type* type) {
- ASSERT(is_class(type));
- return i::Handle<i::Map>(tagged_get<i::Map**>(as_tagged(type), 1));
- }
- static i::Handle<i::Object> as_constant(Type* type) {
- ASSERT(is_constant(type));
- return i::Handle<i::Object>(tagged_get<i::Object**>(as_tagged(type), 1));
- }
- static Unioned* as_union(Type* type) {
- ASSERT(is_union(type));
- return tagged_as_union(as_tagged(type));
- }
- static Unioned* tagged_as_union(Tagged* tagged) {
- ASSERT(tagged_is_union(tagged));
- return reinterpret_cast<Unioned*>(tagged);
- }
- static Type* from_bitset(int bitset) {
- return reinterpret_cast<Type*>((bitset << 1) | 1);
- }
- static Type* from_bitset(int bitset, Zone* Zone) {
- return from_bitset(bitset);
- }
- static Type* from_tagged(Tagged* tagged) {
- return reinterpret_cast<Type*>(tagged);
- }
- static Type* from_class(i::Handle<i::Map> map, int lub, Zone* zone) {
- Tagged* tagged = tagged_create(kClassTag, 2, zone);
- tagged_set(tagged, 0, lub);
- tagged_set(tagged, 1, map.location());
- return from_tagged(tagged);
+template<class Config>
+class TypeImpl<Config>::ConstantType : public TypeImpl<Config> {
+ public:
+ i::Handle<i::Object> Value() { return Config::as_constant(this); }
+
+ static ConstantHandle New(i::Handle<i::Object> value, Region* region) {
+ return Config::template cast<ConstantType>(
+ Config::from_constant(value, BitsetType::Lub(*value), region));
}
- static Type* from_constant(i::Handle<i::Object> value, int lub, Zone* zone) {
- Tagged* tagged = tagged_create(kConstantTag, 2, zone);
- tagged_set(tagged, 0, lub);
- tagged_set(tagged, 1, value.location());
- return from_tagged(tagged);
+
+ static ConstantType* cast(TypeImpl* type) {
+ ASSERT(type->IsConstant());
+ return static_cast<ConstantType*>(type);
}
- static Type* from_union(Unioned* unioned) {
- return from_tagged(tagged_from_union(unioned));
+};
+
+
+// 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
+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 Tagged* tagged_from_union(Unioned* unioned) {
- return reinterpret_cast<Tagged*>(unioned);
+
+ static UnionType* cast(TypeImpl* type) {
+ ASSERT(type->IsUnion());
+ return static_cast<UnionType*>(type);
}
+};
+
+
+template<class Config>
+class TypeImpl<Config>::ArrayType : public StructuralType {
+ public:
+ TypeHandle Element() { return this->Get(0); }
- static Unioned* union_create(int size, Zone* zone) {
- return tagged_as_union(tagged_create(kUnionTag, size, zone));
+ 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 void union_shrink(Unioned* unioned, int size) {
- tagged_shrink(tagged_from_union(unioned), size);
+
+ static ArrayType* cast(TypeImpl* type) {
+ ASSERT(type->IsArray());
+ return static_cast<ArrayType*>(type);
}
- static Type* union_get(Unioned* unioned, int i) {
- Type* type = tagged_get<Type*>(tagged_from_union(unioned), i);
- ASSERT(!is_union(type));
+};
+
+
+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 void union_set(Unioned* unioned, int i, Type* type) {
- ASSERT(!is_union(type));
- tagged_set(tagged_from_union(unioned), i, type);
- }
- static int union_length(Unioned* unioned) {
- return tagged_length(tagged_from_union(unioned));
+
+ static FunctionType* cast(TypeImpl* type) {
+ ASSERT(type->IsFunction());
+ return static_cast<FunctionType*>(type);
}
- static int lub_bitset(Type* type) {
- ASSERT(is_class(type) || is_constant(type));
- return static_cast<int>(tagged_get<intptr_t>(as_tagged(type), 0));
+};
+
+
+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 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_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 i::Handle<i::Map> as_class(Type* type);
+ static inline i::Handle<i::Object> as_constant(Type* type);
+
+ static inline Type* from_bitset(int bitset);
+ static inline Type* from_bitset(int bitset, 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);
};
+typedef TypeImpl<ZoneTypeConfig> Type;
+
// Heap-allocated types are 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 Unioned;
+ typedef i::FixedArray Struct;
typedef i::Isolate Region;
template<class T> struct Handle { typedef i::Handle<T> type; };
- static i::Handle<Type> handle(Type* type) {
- return i::handle(type, i::HeapObject::cast(type)->GetIsolate());
- }
-
- static bool is_bitset(Type* type) { return type->IsSmi(); }
- static bool is_class(Type* type) { return type->IsMap(); }
- static bool is_constant(Type* type) { return type->IsBox(); }
- static bool is_union(Type* type) { return type->IsFixedArray(); }
-
- static int as_bitset(Type* type) {
- return Smi::cast(type)->value();
- }
- static i::Handle<i::Map> as_class(Type* type) {
- return i::handle(i::Map::cast(type));
- }
- static i::Handle<i::Object> as_constant(Type* type) {
- i::Box* box = i::Box::cast(type);
- return i::handle(box->value(), box->GetIsolate());
- }
- static i::Handle<Unioned> as_union(Type* type) {
- return i::handle(i::FixedArray::cast(type));
- }
-
- static Type* from_bitset(int bitset) {
- return Type::cast(i::Smi::FromInt(bitset));
- }
- static i::Handle<Type> from_bitset(int bitset, Isolate* isolate) {
- return i::handle(from_bitset(bitset), isolate);
- }
- static i::Handle<Type> from_class(
- i::Handle<i::Map> map, int lub, Isolate* isolate) {
- return i::Handle<Type>::cast(i::Handle<Object>::cast(map));
- }
- static i::Handle<Type> from_constant(
- i::Handle<i::Object> value, int lub, Isolate* isolate) {
- i::Handle<Box> box = isolate->factory()->NewBox(value);
- return i::Handle<Type>::cast(i::Handle<Object>::cast(box));
- }
- static i::Handle<Type> from_union(i::Handle<Unioned> unioned) {
- return i::Handle<Type>::cast(i::Handle<Object>::cast(unioned));
- }
-
- static i::Handle<Unioned> union_create(int size, Isolate* isolate) {
- return isolate->factory()->NewFixedArray(size);
- }
- static void union_shrink(i::Handle<Unioned> unioned, int size) {
- unioned->Shrink(size);
- }
- static i::Handle<Type> union_get(i::Handle<Unioned> unioned, int i) {
- Type* type = static_cast<Type*>(unioned->get(i));
- ASSERT(!is_union(type));
- return i::handle(type, unioned->GetIsolate());
- }
- static void union_set(
- i::Handle<Unioned> unioned, int i, i::Handle<Type> type) {
- ASSERT(!is_union(*type));
- unioned->set(i, *type);
- }
- static int union_length(i::Handle<Unioned> unioned) {
- return unioned->length();
- }
- static int lub_bitset(Type* type) {
- return 0; // kNone, which causes recomputation.
- }
+ 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_constant(Type* type);
+ static inline bool is_struct(Type* type, int tag);
+
+ static inline int 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 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);
+
+ 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_set(
+ i::Handle<Struct> structured, int i, i::Handle<Type> type);
+
+ static inline int lub_bitset(Type* type);
};
-typedef TypeImpl<ZoneTypeConfig> Type;
typedef TypeImpl<HeapTypeConfig> HeapType;
typedef BoundsImpl<ZoneTypeConfig> Bounds;
-
} } // namespace v8::internal
#endif // V8_TYPES_H_