OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 30 matching lines...) Expand all Loading... |
41 // obvious primitive types and some predefined unions, the type language also | 41 // obvious primitive types and some predefined unions, the type language also |
42 // can express class types (a.k.a. specific maps) and singleton types (i.e., | 42 // can express class types (a.k.a. specific maps) and singleton types (i.e., |
43 // concrete constants). | 43 // concrete constants). |
44 // | 44 // |
45 // The following equations and inequations hold: | 45 // The following equations and inequations hold: |
46 // | 46 // |
47 // None <= T | 47 // None <= T |
48 // T <= Any | 48 // T <= Any |
49 // | 49 // |
50 // Oddball = Boolean \/ Null \/ Undefined | 50 // Oddball = Boolean \/ Null \/ Undefined |
51 // Number = Smi \/ Double | 51 // Number = Integer32 \/ Double |
| 52 // Integer31 < Integer32 |
52 // Name = String \/ Symbol | 53 // Name = String \/ Symbol |
53 // UniqueName = InternalizedString \/ Symbol | 54 // UniqueName = InternalizedString \/ Symbol |
54 // InternalizedString < String | 55 // InternalizedString < String |
55 // | 56 // |
| 57 // Allocated = Receiver \/ Number \/ Name |
| 58 // Detectable = Allocated - Undetectable |
| 59 // Undetectable < Object |
56 // Receiver = Object \/ Proxy | 60 // Receiver = Object \/ Proxy |
57 // Array < Object | 61 // Array < Object |
58 // Function < Object | 62 // Function < Object |
59 // | 63 // |
60 // Class(map) < T iff instance_type(map) < T | 64 // Class(map) < T iff instance_type(map) < T |
61 // Constant(x) < T iff instance_type(map(x)) < T | 65 // Constant(x) < T iff instance_type(map(x)) < T |
62 // | 66 // |
63 // Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can | 67 // Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can |
64 // change! (Its instance type cannot, however.) | 68 // change! (Its instance type cannot, however.) |
65 // TODO(rossberg): the latter is not currently true for proxies, because of fix, | 69 // TODO(rossberg): the latter is not currently true for proxies, because of fix, |
66 // but will hold once we implement direct proxies. | 70 // but will hold once we implement direct proxies. |
67 // | 71 // |
68 // There are two main functions for testing types: | 72 // There are two main functions for testing types: |
69 // | 73 // |
70 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) | 74 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) |
71 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) | 75 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) |
72 // | 76 // |
73 // Typically, the latter should be used to check whether a specific case needs | 77 // Typically, the former is to be used to select representations (e.g., via |
74 // handling (e.g., via T->Maybe(Number)). | 78 // T->Is(Integer31())), and the to check whether a specific case needs handling |
| 79 // (e.g., via T->Maybe(Number())). |
75 // | 80 // |
76 // There is no functionality to discover whether a type is a leaf in the | 81 // There is no functionality to discover whether a type is a leaf in the |
77 // lattice. That is intentional. It should always be possible to refine the | 82 // lattice. That is intentional. It should always be possible to refine the |
78 // lattice (e.g., splitting up number types further) without invalidating any | 83 // lattice (e.g., splitting up number types further) without invalidating any |
79 // existing assumptions or tests. | 84 // existing assumptions or tests. |
80 // | 85 // |
81 // Internally, all 'primitive' types, and their unions, are represented as | 86 // Internally, all 'primitive' types, and their unions, are represented as |
82 // bitsets via smis. Class is a heap pointer to the respective map. Only | 87 // bitsets via smis. Class is a heap pointer to the respective map. Only |
83 // Constant's, or unions containing Class'es or Constant's, require allocation. | 88 // Constant's, or unions containing Class'es or Constant's, require allocation. |
84 // | 89 // |
85 // The type representation is heap-allocated, so cannot (currently) be used in | 90 // The type representation is heap-allocated, so cannot (currently) be used in |
86 // a parallel compilation context. | 91 // a parallel compilation context. |
87 | 92 |
88 class Type : public Object { | 93 class Type : public Object { |
89 public: | 94 public: |
90 static Type* None() { return from_bitset(kNone); } | 95 static Type* None() { return from_bitset(kNone); } |
91 static Type* Any() { return from_bitset(kAny); } | 96 static Type* Any() { return from_bitset(kAny); } |
| 97 static Type* Allocated() { return from_bitset(kAllocated); } |
| 98 static Type* Detectable() { return from_bitset(kDetectable); } |
92 | 99 |
93 static Type* Oddball() { return from_bitset(kOddball); } | 100 static Type* Oddball() { return from_bitset(kOddball); } |
94 static Type* Boolean() { return from_bitset(kBoolean); } | 101 static Type* Boolean() { return from_bitset(kBoolean); } |
95 static Type* Null() { return from_bitset(kNull); } | 102 static Type* Null() { return from_bitset(kNull); } |
96 static Type* Undefined() { return from_bitset(kUndefined); } | 103 static Type* Undefined() { return from_bitset(kUndefined); } |
97 | 104 |
98 static Type* Number() { return from_bitset(kNumber); } | 105 static Type* Number() { return from_bitset(kNumber); } |
99 static Type* Smi() { return from_bitset(kSmi); } | 106 static Type* Integer31() { return from_bitset(kInteger31); } |
| 107 static Type* Integer32() { return from_bitset(kInteger32); } |
100 static Type* Double() { return from_bitset(kDouble); } | 108 static Type* Double() { return from_bitset(kDouble); } |
101 | 109 |
102 static Type* Name() { return from_bitset(kName); } | 110 static Type* Name() { return from_bitset(kName); } |
103 static Type* UniqueName() { return from_bitset(kUniqueName); } | 111 static Type* UniqueName() { return from_bitset(kUniqueName); } |
104 static Type* String() { return from_bitset(kString); } | 112 static Type* String() { return from_bitset(kString); } |
105 static Type* InternalizedString() { return from_bitset(kInternalizedString); } | 113 static Type* InternalizedString() { return from_bitset(kInternalizedString); } |
106 static Type* Symbol() { return from_bitset(kSymbol); } | 114 static Type* Symbol() { return from_bitset(kSymbol); } |
107 | 115 |
108 static Type* Receiver() { return from_bitset(kReceiver); } | 116 static Type* Receiver() { return from_bitset(kReceiver); } |
109 static Type* Object() { return from_bitset(kObject); } | 117 static Type* Object() { return from_bitset(kObject); } |
| 118 static Type* Undetectable() { return from_bitset(kUndetectable); } |
110 static Type* Array() { return from_bitset(kArray); } | 119 static Type* Array() { return from_bitset(kArray); } |
111 static Type* Function() { return from_bitset(kFunction); } | 120 static Type* Function() { return from_bitset(kFunction); } |
112 static Type* Proxy() { return from_bitset(kProxy); } | 121 static Type* Proxy() { return from_bitset(kProxy); } |
113 | 122 |
114 static Type* Class(Handle<Map> map) { return from_handle(map); } | 123 static Type* Class(Handle<Map> map) { return from_handle(map); } |
115 static Type* Constant(Handle<HeapObject> value) { | 124 static Type* Constant(Handle<HeapObject> value) { |
116 return Constant(value, value->GetIsolate()); | 125 return Constant(value, value->GetIsolate()); |
117 } | 126 } |
118 static Type* Constant(Handle<v8::internal::Object> value, Isolate* isolate) { | 127 static Type* Constant(Handle<v8::internal::Object> value, Isolate* isolate) { |
119 return from_handle(isolate->factory()->NewBox(value)); | 128 return from_handle(isolate->factory()->NewBox(value)); |
120 } | 129 } |
121 | 130 |
122 static Type* Union(Handle<Type> type1, Handle<Type> type2); | 131 static Type* Union(Handle<Type> type1, Handle<Type> type2); |
123 static Type* Optional(Handle<Type> type); // type \/ Undefined | 132 static Type* Optional(Handle<Type> type); // type \/ Undefined |
124 | 133 |
125 bool Is(Handle<Type> that); | 134 bool Is(Type* that); |
126 bool Maybe(Handle<Type> that); | 135 bool Is(Handle<Type> that) { return this->Is(*that); } |
| 136 bool Maybe(Type* that); |
| 137 bool Maybe(Handle<Type> that) { return this->Maybe(*that); } |
127 | 138 |
128 // TODO(rossberg): method to iterate unions? | 139 bool IsClass() { return is_class(); } |
| 140 bool IsConstant() { return is_constant(); } |
| 141 Handle<Map> AsClass() { return as_class(); } |
| 142 Handle<v8::internal::Object> AsConstant() { return as_constant(); } |
| 143 |
| 144 int NumClasses(); |
| 145 int NumConstants(); |
| 146 |
| 147 template<class T> |
| 148 class Iterator { |
| 149 public: |
| 150 bool Done() const { return index_ < 0; } |
| 151 Handle<T> Current(); |
| 152 void Advance(); |
| 153 |
| 154 private: |
| 155 friend class Type; |
| 156 |
| 157 Iterator() : index_(-1) {} |
| 158 explicit Iterator(Handle<Type> type) : type_(type), index_(-1) { |
| 159 Advance(); |
| 160 } |
| 161 |
| 162 inline bool matches(Handle<Type> type); |
| 163 inline Handle<Type> get_type(); |
| 164 |
| 165 Handle<Type> type_; |
| 166 int index_; |
| 167 }; |
| 168 |
| 169 Iterator<Map> Classes() { |
| 170 if (this->is_bitset()) return Iterator<Map>(); |
| 171 return Iterator<Map>(this->handle()); |
| 172 } |
| 173 Iterator<v8::internal::Object> Constants() { |
| 174 if (this->is_bitset()) return Iterator<v8::internal::Object>(); |
| 175 return Iterator<v8::internal::Object>(this->handle()); |
| 176 } |
129 | 177 |
130 private: | 178 private: |
131 // A union is a fixed array containing types. Invariants: | 179 // A union is a fixed array containing types. Invariants: |
132 // - its length is at least 2 | 180 // - its length is at least 2 |
133 // - at most one field is a bitset, and it must go into index 0 | 181 // - at most one field is a bitset, and it must go into index 0 |
134 // - no field is a union | 182 // - no field is a union |
135 typedef FixedArray Unioned; | 183 typedef FixedArray Unioned; |
136 | 184 |
137 enum { | 185 enum { |
138 kNull = 1 << 0, | 186 kNull = 1 << 0, |
139 kUndefined = 1 << 1, | 187 kUndefined = 1 << 1, |
140 kBoolean = 1 << 2, | 188 kBoolean = 1 << 2, |
141 kSmi = 1 << 3, | 189 kInteger31 = 1 << 3, |
142 kDouble = 1 << 4, | 190 kOtherInteger = 1 << 4, |
143 kSymbol = 1 << 5, | 191 kDouble = 1 << 5, |
144 kInternalizedString = 1 << 6, | 192 kSymbol = 1 << 6, |
145 kOtherString = 1 << 7, | 193 kInternalizedString = 1 << 7, |
146 kArray = 1 << 8, | 194 kOtherString = 1 << 8, |
147 kFunction = 1 << 9, | 195 kUndetectable = 1 << 9, |
148 kOtherObject = 1 << 10, | 196 kArray = 1 << 10, |
149 kProxy = 1 << 11, | 197 kFunction = 1 << 11, |
| 198 kOtherObject = 1 << 12, |
| 199 kProxy = 1 << 13, |
150 | 200 |
151 kOddball = kBoolean | kNull | kUndefined, | 201 kOddball = kBoolean | kNull | kUndefined, |
152 kNumber = kSmi | kDouble, | 202 kInteger32 = kInteger31 | kOtherInteger, |
| 203 kNumber = kInteger32 | kDouble, |
153 kString = kInternalizedString | kOtherString, | 204 kString = kInternalizedString | kOtherString, |
154 kUniqueName = kSymbol | kInternalizedString, | 205 kUniqueName = kSymbol | kInternalizedString, |
155 kName = kSymbol | kString, | 206 kName = kSymbol | kString, |
156 kObject = kArray | kFunction | kOtherObject, | 207 kObject = kUndetectable | kArray | kFunction | kOtherObject, |
157 kReceiver = kObject | kProxy, | 208 kReceiver = kObject | kProxy, |
158 kAny = kOddball | kNumber | kName | kReceiver, | 209 kAllocated = kDouble | kName | kReceiver, |
| 210 kAny = kOddball | kNumber | kAllocated, |
| 211 kDetectable = kAllocated - kUndetectable, |
159 kNone = 0 | 212 kNone = 0 |
160 }; | 213 }; |
161 | 214 |
162 bool is_bitset() { return this->IsSmi(); } | 215 bool is_bitset() { return this->IsSmi(); } |
163 bool is_class() { return this->IsMap(); } | 216 bool is_class() { return this->IsMap(); } |
164 bool is_constant() { return this->IsBox(); } | 217 bool is_constant() { return this->IsBox(); } |
165 bool is_union() { return this->IsFixedArray(); } | 218 bool is_union() { return this->IsFixedArray(); } |
166 | 219 |
167 int as_bitset() { return Smi::cast(this)->value(); } | 220 int as_bitset() { return Smi::cast(this)->value(); } |
168 Handle<Map> as_class() { return Handle<Map>::cast(handle()); } | 221 Handle<Map> as_class() { return Handle<Map>::cast(handle()); } |
169 Handle<Box> as_constant() { return Handle<Box>::cast(handle()); } | 222 Handle<v8::internal::Object> as_constant() { |
| 223 Handle<Box> box = Handle<Box>::cast(handle()); |
| 224 return v8::internal::handle(box->value(), box->GetIsolate()); |
| 225 } |
170 Handle<Unioned> as_union() { return Handle<Unioned>::cast(handle()); } | 226 Handle<Unioned> as_union() { return Handle<Unioned>::cast(handle()); } |
171 | 227 |
172 Handle<Type> handle() { return handle_via_isolate_of(this); } | 228 Handle<Type> handle() { return handle_via_isolate_of(this); } |
173 Handle<Type> handle_via_isolate_of(Type* type) { | 229 Handle<Type> handle_via_isolate_of(Type* type) { |
174 ASSERT(type->IsHeapObject()); | 230 ASSERT(type->IsHeapObject()); |
175 return v8::internal::handle(this, HeapObject::cast(type)->GetIsolate()); | 231 return v8::internal::handle(this, HeapObject::cast(type)->GetIsolate()); |
176 } | 232 } |
177 | 233 |
178 static Type* from_bitset(int bitset) { | 234 static Type* from_bitset(int bitset) { |
179 return static_cast<Type*>(Object::cast(Smi::FromInt(bitset))); | 235 return static_cast<Type*>(Object::cast(Smi::FromInt(bitset))); |
(...skipping 10 matching lines...) Expand all Loading... |
190 | 246 |
191 int LubBitset(); // least upper bound that's a bitset | 247 int LubBitset(); // least upper bound that's a bitset |
192 int GlbBitset(); // greatest lower bound that's a bitset | 248 int GlbBitset(); // greatest lower bound that's a bitset |
193 bool InUnion(Handle<Unioned> unioned, int current_size); | 249 bool InUnion(Handle<Unioned> unioned, int current_size); |
194 int ExtendUnion(Handle<Unioned> unioned, int current_size); | 250 int ExtendUnion(Handle<Unioned> unioned, int current_size); |
195 }; | 251 }; |
196 | 252 |
197 } } // namespace v8::internal | 253 } } // namespace v8::internal |
198 | 254 |
199 #endif // V8_TYPES_H_ | 255 #endif // V8_TYPES_H_ |
OLD | NEW |