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 13 matching lines...) Expand all Loading... |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "types.h" | 28 #include "types.h" |
29 #include "string-stream.h" | 29 #include "string-stream.h" |
30 | 30 |
31 namespace v8 { | 31 namespace v8 { |
32 namespace internal { | 32 namespace internal { |
33 | 33 |
34 template<class Config> | 34 int Type::NumClasses() { |
35 int TypeImpl<Config>::NumClasses() { | 35 if (is_class()) { |
36 if (this->IsClass()) { | |
37 return 1; | 36 return 1; |
38 } else if (this->IsUnion()) { | 37 } else if (is_union()) { |
39 UnionedHandle unioned = this->AsUnion(); | 38 Handle<Unioned> unioned = as_union(); |
40 int result = 0; | 39 int result = 0; |
41 for (int i = 0; i < unioned->length(); ++i) { | 40 for (int i = 0; i < unioned->length(); ++i) { |
42 if (Config::union_get(unioned, i)->IsClass()) ++result; | 41 if (union_get(unioned, i)->is_class()) ++result; |
43 } | 42 } |
44 return result; | 43 return result; |
45 } else { | 44 } else { |
46 return 0; | 45 return 0; |
47 } | 46 } |
48 } | 47 } |
49 | 48 |
50 | 49 |
51 template<class Config> | 50 int Type::NumConstants() { |
52 int TypeImpl<Config>::NumConstants() { | 51 if (is_constant()) { |
53 if (this->IsConstant()) { | |
54 return 1; | 52 return 1; |
55 } else if (this->IsUnion()) { | 53 } else if (is_union()) { |
56 UnionedHandle unioned = this->AsUnion(); | 54 Handle<Unioned> unioned = as_union(); |
57 int result = 0; | 55 int result = 0; |
58 for (int i = 0; i < unioned->length(); ++i) { | 56 for (int i = 0; i < unioned->length(); ++i) { |
59 if (Config::union_get(unioned, i)->IsConstant()) ++result; | 57 if (union_get(unioned, i)->is_constant()) ++result; |
60 } | 58 } |
61 return result; | 59 return result; |
62 } else { | 60 } else { |
63 return 0; | 61 return 0; |
64 } | 62 } |
65 } | 63 } |
66 | 64 |
67 | 65 |
68 template<class Config> template<class T> | 66 template<class T> |
69 typename TypeImpl<Config>::TypeHandle | 67 Handle<Type> Type::Iterator<T>::get_type() { |
70 TypeImpl<Config>::Iterator<T>::get_type() { | |
71 ASSERT(!Done()); | 68 ASSERT(!Done()); |
72 return type_->IsUnion() ? Config::union_get(type_->AsUnion(), index_) : type_; | 69 return type_->is_union() ? union_get(type_->as_union(), index_) : type_; |
| 70 } |
| 71 |
| 72 template<> |
| 73 Handle<i::Map> Type::Iterator<i::Map>::Current() { |
| 74 return get_type()->as_class(); |
| 75 } |
| 76 |
| 77 template<> |
| 78 Handle<i::Object> Type::Iterator<i::Object>::Current() { |
| 79 return get_type()->as_constant(); |
73 } | 80 } |
74 | 81 |
75 | 82 |
76 // C++ cannot specialise nested templates, so we have to go through this | 83 template<> |
77 // contortion with an auxiliary template to simulate it. | 84 bool Type::Iterator<i::Map>::matches(Handle<Type> type) { |
78 template<class Config, class T> | 85 return type->is_class(); |
79 struct TypeImplIteratorAux { | |
80 static bool matches(typename TypeImpl<Config>::TypeHandle type); | |
81 static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type); | |
82 }; | |
83 | |
84 template<class Config> | |
85 struct TypeImplIteratorAux<Config, i::Map> { | |
86 static bool matches(typename TypeImpl<Config>::TypeHandle type) { | |
87 return type->IsClass(); | |
88 } | |
89 static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) { | |
90 return type->AsClass(); | |
91 } | |
92 }; | |
93 | |
94 template<class Config> | |
95 struct TypeImplIteratorAux<Config, i::Object> { | |
96 static bool matches(typename TypeImpl<Config>::TypeHandle type) { | |
97 return type->IsConstant(); | |
98 } | |
99 static i::Handle<i::Object> current( | |
100 typename TypeImpl<Config>::TypeHandle type) { | |
101 return type->AsConstant(); | |
102 } | |
103 }; | |
104 | |
105 template<class Config> template<class T> | |
106 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) { | |
107 return TypeImplIteratorAux<Config, T>::matches(type); | |
108 } | 86 } |
109 | 87 |
110 template<class Config> template<class T> | 88 template<> |
111 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() { | 89 bool Type::Iterator<i::Object>::matches(Handle<Type> type) { |
112 return TypeImplIteratorAux<Config, T>::current(get_type()); | 90 return type->is_constant(); |
113 } | 91 } |
114 | 92 |
115 | 93 |
116 template<class Config> template<class T> | 94 template<class T> |
117 void TypeImpl<Config>::Iterator<T>::Advance() { | 95 void Type::Iterator<T>::Advance() { |
118 ++index_; | 96 ++index_; |
119 if (type_->IsUnion()) { | 97 if (type_->is_union()) { |
120 UnionedHandle unioned = type_->AsUnion(); | 98 Handle<Unioned> unioned = type_->as_union(); |
121 for (; index_ < unioned->length(); ++index_) { | 99 for (; index_ < unioned->length(); ++index_) { |
122 if (matches(Config::union_get(unioned, index_))) return; | 100 if (matches(union_get(unioned, index_))) return; |
123 } | 101 } |
124 } else if (index_ == 0 && matches(type_)) { | 102 } else if (index_ == 0 && matches(type_)) { |
125 return; | 103 return; |
126 } | 104 } |
127 index_ = -1; | 105 index_ = -1; |
128 } | 106 } |
129 | 107 |
| 108 template class Type::Iterator<i::Map>; |
| 109 template class Type::Iterator<i::Object>; |
| 110 |
130 | 111 |
131 // Get the smallest bitset subsuming this type. | 112 // Get the smallest bitset subsuming this type. |
132 template<class Config> | 113 int Type::LubBitset() { |
133 int TypeImpl<Config>::LubBitset() { | 114 if (this->is_bitset()) { |
134 if (this->IsBitset()) { | 115 return this->as_bitset(); |
135 return this->AsBitset(); | 116 } else if (this->is_union()) { |
136 } else if (this->IsUnion()) { | 117 Handle<Unioned> unioned = this->as_union(); |
137 UnionedHandle unioned = this->AsUnion(); | |
138 int bitset = kNone; | 118 int bitset = kNone; |
139 for (int i = 0; i < unioned->length(); ++i) { | 119 for (int i = 0; i < unioned->length(); ++i) { |
140 bitset |= Config::union_get(unioned, i)->LubBitset(); | 120 bitset |= union_get(unioned, i)->LubBitset(); |
141 } | 121 } |
142 return bitset; | 122 return bitset; |
143 } else if (this->IsClass()) { | 123 } else if (this->is_class()) { |
144 return LubBitset(*this->AsClass()); | 124 return LubBitset(*this->as_class()); |
145 } else { | 125 } else { |
146 return LubBitset(*this->AsConstant()); | 126 return LubBitset(*this->as_constant()); |
147 } | 127 } |
148 } | 128 } |
149 | 129 |
150 | 130 |
151 template<class Config> | 131 int Type::LubBitset(i::Object* value) { |
152 int TypeImpl<Config>::LubBitset(i::Object* value) { | |
153 if (value->IsSmi()) return kSmi; | 132 if (value->IsSmi()) return kSmi; |
154 i::Map* map = i::HeapObject::cast(value)->map(); | 133 i::Map* map = i::HeapObject::cast(value)->map(); |
155 if (map->instance_type() == HEAP_NUMBER_TYPE) { | 134 if (map->instance_type() == HEAP_NUMBER_TYPE) { |
156 int32_t i; | 135 int32_t i; |
157 uint32_t u; | 136 uint32_t u; |
158 if (value->ToInt32(&i)) return Smi::IsValid(i) ? kSmi : kOtherSigned32; | 137 if (value->ToInt32(&i)) return Smi::IsValid(i) ? kSmi : kOtherSigned32; |
159 if (value->ToUint32(&u)) return kUnsigned32; | 138 if (value->ToUint32(&u)) return kUnsigned32; |
160 return kDouble; | 139 return kDouble; |
161 } | 140 } |
162 if (map->instance_type() == ODDBALL_TYPE) { | 141 if (map->instance_type() == ODDBALL_TYPE) { |
163 if (value->IsUndefined()) return kUndefined; | 142 if (value->IsUndefined()) return kUndefined; |
164 if (value->IsNull()) return kNull; | 143 if (value->IsNull()) return kNull; |
165 if (value->IsBoolean()) return kBoolean; | 144 if (value->IsBoolean()) return kBoolean; |
166 if (value->IsTheHole()) return kAny; // TODO(rossberg): kNone? | 145 if (value->IsTheHole()) return kAny; // TODO(rossberg): kNone? |
167 UNREACHABLE(); | 146 UNREACHABLE(); |
168 } | 147 } |
169 return LubBitset(map); | 148 return Type::LubBitset(map); |
170 } | 149 } |
171 | 150 |
172 | 151 |
173 template<class Config> | 152 int Type::LubBitset(i::Map* map) { |
174 int TypeImpl<Config>::LubBitset(i::Map* map) { | |
175 switch (map->instance_type()) { | 153 switch (map->instance_type()) { |
176 case STRING_TYPE: | 154 case STRING_TYPE: |
177 case ASCII_STRING_TYPE: | 155 case ASCII_STRING_TYPE: |
178 case CONS_STRING_TYPE: | 156 case CONS_STRING_TYPE: |
179 case CONS_ASCII_STRING_TYPE: | 157 case CONS_ASCII_STRING_TYPE: |
180 case SLICED_STRING_TYPE: | 158 case SLICED_STRING_TYPE: |
181 case SLICED_ASCII_STRING_TYPE: | 159 case SLICED_ASCII_STRING_TYPE: |
182 case EXTERNAL_STRING_TYPE: | 160 case EXTERNAL_STRING_TYPE: |
183 case EXTERNAL_ASCII_STRING_TYPE: | 161 case EXTERNAL_ASCII_STRING_TYPE: |
184 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: | 162 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
246 case FIXED_ARRAY_TYPE: | 224 case FIXED_ARRAY_TYPE: |
247 return kInternal; | 225 return kInternal; |
248 default: | 226 default: |
249 UNREACHABLE(); | 227 UNREACHABLE(); |
250 return kNone; | 228 return kNone; |
251 } | 229 } |
252 } | 230 } |
253 | 231 |
254 | 232 |
255 // Get the largest bitset subsumed by this type. | 233 // Get the largest bitset subsumed by this type. |
256 template<class Config> | 234 int Type::GlbBitset() { |
257 int TypeImpl<Config>::GlbBitset() { | 235 if (this->is_bitset()) { |
258 if (this->IsBitset()) { | 236 return this->as_bitset(); |
259 return this->AsBitset(); | 237 } else if (this->is_union()) { |
260 } else if (this->IsUnion()) { | |
261 // All but the first are non-bitsets and thus would yield kNone anyway. | 238 // All but the first are non-bitsets and thus would yield kNone anyway. |
262 return Config::union_get(this->AsUnion(), 0)->GlbBitset(); | 239 return union_get(this->as_union(), 0)->GlbBitset(); |
263 } else { | 240 } else { |
264 return kNone; | 241 return kNone; |
265 } | 242 } |
266 } | 243 } |
267 | 244 |
268 | 245 |
269 // Most precise _current_ type of a value (usually its class). | 246 // Most precise _current_ type of a value (usually its class). |
270 template<class Config> | 247 Type* Type::OfCurrently(Handle<i::Object> value) { |
271 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::OfCurrently( | 248 if (value->IsSmi()) return Smi(); |
272 i::Handle<i::Object> value, Region* region) { | |
273 if (value->IsSmi()) return Smi(region); | |
274 i::Map* map = i::HeapObject::cast(*value)->map(); | 249 i::Map* map = i::HeapObject::cast(*value)->map(); |
275 if (map->instance_type() == HEAP_NUMBER_TYPE || | 250 if (map->instance_type() == HEAP_NUMBER_TYPE || |
276 map->instance_type() == ODDBALL_TYPE) { | 251 map->instance_type() == ODDBALL_TYPE) { |
277 return Of(value, region); | 252 return Type::Of(value); |
278 } | 253 } |
279 return Class(i::handle(map), region); | 254 return Class(i::handle(map)); |
280 } | 255 } |
281 | 256 |
282 | 257 |
283 // Check this <= that. | 258 // Check this <= that. |
284 template<class Config> | 259 bool Type::SlowIs(Type* that) { |
285 bool TypeImpl<Config>::SlowIs(TypeImpl* that) { | |
286 // Fast path for bitsets. | 260 // Fast path for bitsets. |
287 if (this->IsNone()) return true; | 261 if (this->is_none()) return true; |
288 if (that->IsBitset()) { | 262 if (that->is_bitset()) { |
289 return (this->LubBitset() | that->AsBitset()) == that->AsBitset(); | 263 return (this->LubBitset() | that->as_bitset()) == that->as_bitset(); |
290 } | 264 } |
291 | 265 |
292 if (that->IsClass()) { | 266 if (that->is_class()) { |
293 return this->IsClass() && *this->AsClass() == *that->AsClass(); | 267 return this->is_class() && *this->as_class() == *that->as_class(); |
294 } | 268 } |
295 if (that->IsConstant()) { | 269 if (that->is_constant()) { |
296 return this->IsConstant() && *this->AsConstant() == *that->AsConstant(); | 270 return this->is_constant() && *this->as_constant() == *that->as_constant(); |
297 } | 271 } |
298 | 272 |
299 // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) | 273 // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) |
300 if (this->IsUnion()) { | 274 if (this->is_union()) { |
301 UnionedHandle unioned = this->AsUnion(); | 275 Handle<Unioned> unioned = this->as_union(); |
302 for (int i = 0; i < unioned->length(); ++i) { | 276 for (int i = 0; i < unioned->length(); ++i) { |
303 TypeHandle this_i = Config::union_get(unioned, i); | 277 Handle<Type> this_i = union_get(unioned, i); |
304 if (!this_i->Is(that)) return false; | 278 if (!this_i->Is(that)) return false; |
305 } | 279 } |
306 return true; | 280 return true; |
307 } | 281 } |
308 | 282 |
309 // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) | 283 // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) |
310 // (iff T is not a union) | 284 // (iff T is not a union) |
311 ASSERT(!this->IsUnion()); | 285 ASSERT(!this->is_union()); |
312 if (that->IsUnion()) { | 286 if (that->is_union()) { |
313 UnionedHandle unioned = that->AsUnion(); | 287 Handle<Unioned> unioned = that->as_union(); |
314 for (int i = 0; i < unioned->length(); ++i) { | 288 for (int i = 0; i < unioned->length(); ++i) { |
315 TypeHandle that_i = Config::union_get(unioned, i); | 289 Handle<Type> that_i = union_get(unioned, i); |
316 if (this->Is(that_i)) return true; | 290 if (this->Is(that_i)) return true; |
317 if (this->IsBitset()) break; // Fast fail, only first field is a bitset. | 291 if (this->is_bitset()) break; // Fast fail, no other field is a bitset. |
318 } | 292 } |
319 return false; | 293 return false; |
320 } | 294 } |
321 | 295 |
322 return false; | 296 return false; |
323 } | 297 } |
324 | 298 |
325 | 299 |
326 template<class Config> | 300 bool Type::IsCurrently(Type* that) { |
327 bool TypeImpl<Config>::IsCurrently(TypeImpl* that) { | |
328 return this->Is(that) || | 301 return this->Is(that) || |
329 (this->IsConstant() && that->IsClass() && | 302 (this->is_constant() && that->is_class() && |
330 this->AsConstant()->IsHeapObject() && | 303 this->as_constant()->IsHeapObject() && |
331 i::HeapObject::cast(*this->AsConstant())->map() == *that->AsClass()); | 304 i::HeapObject::cast(*this->as_constant())->map() == *that->as_class()); |
332 } | 305 } |
333 | 306 |
334 | 307 |
335 // Check this overlaps that. | 308 // Check this overlaps that. |
336 template<class Config> | 309 bool Type::Maybe(Type* that) { |
337 bool TypeImpl<Config>::Maybe(TypeImpl* that) { | |
338 // Fast path for bitsets. | 310 // Fast path for bitsets. |
339 if (this->IsBitset()) { | 311 if (this->is_bitset()) { |
340 return (this->AsBitset() & that->LubBitset()) != 0; | 312 return (this->as_bitset() & that->LubBitset()) != 0; |
341 } | 313 } |
342 if (that->IsBitset()) { | 314 if (that->is_bitset()) { |
343 return (this->LubBitset() & that->AsBitset()) != 0; | 315 return (this->LubBitset() & that->as_bitset()) != 0; |
344 } | 316 } |
345 | 317 |
346 // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) | 318 // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) |
347 if (this->IsUnion()) { | 319 if (this->is_union()) { |
348 UnionedHandle unioned = this->AsUnion(); | 320 Handle<Unioned> unioned = this->as_union(); |
349 for (int i = 0; i < unioned->length(); ++i) { | 321 for (int i = 0; i < unioned->length(); ++i) { |
350 TypeHandle this_i = Config::union_get(unioned, i); | 322 Handle<Type> this_i = union_get(unioned, i); |
351 if (this_i->Maybe(that)) return true; | 323 if (this_i->Maybe(that)) return true; |
352 } | 324 } |
353 return false; | 325 return false; |
354 } | 326 } |
355 | 327 |
356 // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) | 328 // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) |
357 if (that->IsUnion()) { | 329 if (that->is_union()) { |
358 UnionedHandle unioned = that->AsUnion(); | 330 Handle<Unioned> unioned = that->as_union(); |
359 for (int i = 0; i < unioned->length(); ++i) { | 331 for (int i = 0; i < unioned->length(); ++i) { |
360 TypeHandle that_i = Config::union_get(unioned, i); | 332 Handle<Type> that_i = union_get(unioned, i); |
361 if (this->Maybe(that_i)) return true; | 333 if (this->Maybe(that_i)) return true; |
362 } | 334 } |
363 return false; | 335 return false; |
364 } | 336 } |
365 | 337 |
366 ASSERT(!this->IsUnion() && !that->IsUnion()); | 338 ASSERT(!that->is_union()); |
367 if (this->IsClass()) { | 339 if (this->is_class()) { |
368 return that->IsClass() && *this->AsClass() == *that->AsClass(); | 340 return that->is_class() && *this->as_class() == *that->as_class(); |
369 } | 341 } |
370 if (this->IsConstant()) { | 342 if (this->is_constant()) { |
371 return that->IsConstant() && *this->AsConstant() == *that->AsConstant(); | 343 return that->is_constant() && *this->as_constant() == *that->as_constant(); |
372 } | 344 } |
373 | 345 |
374 return false; | 346 return false; |
375 } | 347 } |
376 | 348 |
377 | 349 |
378 template<class Config> | 350 bool Type::InUnion(Handle<Unioned> unioned, int current_size) { |
379 bool TypeImpl<Config>::InUnion(UnionedHandle unioned, int current_size) { | 351 ASSERT(!this->is_union()); |
380 ASSERT(!this->IsUnion()); | |
381 for (int i = 0; i < current_size; ++i) { | 352 for (int i = 0; i < current_size; ++i) { |
382 TypeHandle type = Config::union_get(unioned, i); | 353 Handle<Type> type = union_get(unioned, i); |
383 if (this->Is(type)) return true; | 354 if (this->Is(type)) return true; |
384 } | 355 } |
385 return false; | 356 return false; |
386 } | 357 } |
387 | 358 |
388 | 359 |
389 // Get non-bitsets from this which are not subsumed by union, store at unioned, | 360 // Get non-bitsets from this which are not subsumed by union, store at unioned, |
390 // starting at index. Returns updated index. | 361 // starting at index. Returns updated index. |
391 template<class Config> | 362 int Type::ExtendUnion(Handle<Unioned> result, int current_size) { |
392 int TypeImpl<Config>::ExtendUnion(UnionedHandle result, int current_size) { | |
393 int old_size = current_size; | 363 int old_size = current_size; |
394 if (this->IsClass() || this->IsConstant()) { | 364 if (this->is_class() || this->is_constant()) { |
395 if (!this->InUnion(result, old_size)) result->set(current_size++, this); | 365 if (!this->InUnion(result, old_size)) result->set(current_size++, this); |
396 } else if (this->IsUnion()) { | 366 } else if (this->is_union()) { |
397 UnionedHandle unioned = this->AsUnion(); | 367 Handle<Unioned> unioned = this->as_union(); |
398 for (int i = 0; i < unioned->length(); ++i) { | 368 for (int i = 0; i < unioned->length(); ++i) { |
399 TypeHandle type = Config::union_get(unioned, i); | 369 Handle<Type> type = union_get(unioned, i); |
400 ASSERT(i == 0 || | 370 ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); |
401 !(type->IsBitset() || type->Is(Config::union_get(unioned, 0)))); | 371 if (type->is_bitset()) continue; |
402 if (!type->IsBitset() && !type->InUnion(result, old_size)) { | 372 if (!type->InUnion(result, old_size)) result->set(current_size++, *type); |
403 result->set(current_size++, *type); | |
404 } | |
405 } | 373 } |
406 } | 374 } |
407 return current_size; | 375 return current_size; |
408 } | 376 } |
409 | 377 |
410 | 378 |
411 // Union is O(1) on simple bit unions, but O(n*m) on structured unions. | 379 // Union is O(1) on simple bit unions, but O(n*m) on structured unions. |
412 // TODO(rossberg): Should we use object sets somehow? Is it worth it? | 380 // TODO(rossberg): Should we use object sets somehow? Is it worth it? |
413 template<class Config> | 381 Type* Type::Union(Handle<Type> type1, Handle<Type> type2) { |
414 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union( | |
415 TypeHandle type1, TypeHandle type2, Region* region) { | |
416 // Fast case: bit sets. | 382 // Fast case: bit sets. |
417 if (type1->IsBitset() && type2->IsBitset()) { | 383 if (type1->is_bitset() && type2->is_bitset()) { |
418 return Config::from_bitset(type1->AsBitset() | type2->AsBitset(), region); | 384 return from_bitset(type1->as_bitset() | type2->as_bitset()); |
419 } | 385 } |
420 | 386 |
421 // Fast case: top or bottom types. | 387 // Fast case: top or bottom types. |
422 if (type1->IsAny()) return type1; | 388 if (type1->SameValue(Type::Any())) return *type1; |
423 if (type2->IsAny()) return type2; | 389 if (type2->SameValue(Type::Any())) return *type2; |
424 if (type1->IsNone()) return type2; | 390 if (type1->SameValue(Type::None())) return *type2; |
425 if (type2->IsNone()) return type1; | 391 if (type2->SameValue(Type::None())) return *type1; |
426 | 392 |
427 // Semi-fast case: Unioned objects are neither involved nor produced. | 393 // Semi-fast case: Unioned objects are neither involved nor produced. |
428 if (!(type1->IsUnion() || type2->IsUnion())) { | 394 if (!(type1->is_union() || type2->is_union())) { |
429 if (type1->Is(type2)) return type2; | 395 if (type1->Is(type2)) return *type2; |
430 if (type2->Is(type1)) return type1; | 396 if (type2->Is(type1)) return *type1; |
431 } | 397 } |
432 | 398 |
433 // Slow case: may need to produce a Unioned object. | 399 // Slow case: may need to produce a Unioned object. |
434 int size = type1->IsBitset() || type2->IsBitset() ? 1 : 0; | 400 Isolate* isolate = NULL; |
435 if (!type1->IsBitset()) { | 401 int size = type1->is_bitset() || type2->is_bitset() ? 1 : 0; |
436 size += (type1->IsUnion() ? type1->AsUnion()->length() : 1); | 402 if (!type1->is_bitset()) { |
| 403 isolate = i::HeapObject::cast(*type1)->GetIsolate(); |
| 404 size += (type1->is_union() ? type1->as_union()->length() : 1); |
437 } | 405 } |
438 if (!type2->IsBitset()) { | 406 if (!type2->is_bitset()) { |
439 size += (type2->IsUnion() ? type2->AsUnion()->length() : 1); | 407 isolate = i::HeapObject::cast(*type2)->GetIsolate(); |
| 408 size += (type2->is_union() ? type2->as_union()->length() : 1); |
440 } | 409 } |
| 410 ASSERT(isolate != NULL); |
441 ASSERT(size >= 2); | 411 ASSERT(size >= 2); |
442 UnionedHandle unioned = Config::union_create(size, region); | 412 Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); |
443 size = 0; | 413 size = 0; |
444 | 414 |
445 int bitset = type1->GlbBitset() | type2->GlbBitset(); | 415 int bitset = type1->GlbBitset() | type2->GlbBitset(); |
446 if (bitset != kNone) unioned->set(size++, Config::from_bitset(bitset)); | 416 if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); |
447 size = type1->ExtendUnion(unioned, size); | 417 size = type1->ExtendUnion(unioned, size); |
448 size = type2->ExtendUnion(unioned, size); | 418 size = type2->ExtendUnion(unioned, size); |
449 | 419 |
450 if (size == 1) { | 420 if (size == 1) { |
451 return Config::union_get(unioned, 0); | 421 return *union_get(unioned, 0); |
452 } else if (size == unioned->length()) { | 422 } else if (size == unioned->length()) { |
453 return Config::from_union(unioned); | 423 return from_handle(unioned); |
454 } | 424 } |
455 | 425 |
456 // There was an overlap. Copy to smaller union. | 426 // There was an overlap. Copy to smaller union. |
457 UnionedHandle result = Config::union_create(size, region); | 427 Handle<Unioned> result = isolate->factory()->NewFixedArray(size); |
458 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); | 428 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); |
459 return Config::from_union(result); | 429 return from_handle(result); |
460 } | 430 } |
461 | 431 |
462 | 432 |
463 // Get non-bitsets from this which are also in that, store at unioned, | 433 // Get non-bitsets from this which are also in that, store at unioned, |
464 // starting at index. Returns updated index. | 434 // starting at index. Returns updated index. |
465 template<class Config> | 435 int Type::ExtendIntersection( |
466 int TypeImpl<Config>::ExtendIntersection( | 436 Handle<Unioned> result, Handle<Type> that, int current_size) { |
467 UnionedHandle result, TypeHandle that, int current_size) { | |
468 int old_size = current_size; | 437 int old_size = current_size; |
469 if (this->IsClass() || this->IsConstant()) { | 438 if (this->is_class() || this->is_constant()) { |
470 if (this->Is(that) && !this->InUnion(result, old_size)) | 439 if (this->Is(that) && !this->InUnion(result, old_size)) |
471 result->set(current_size++, this); | 440 result->set(current_size++, this); |
472 } else if (this->IsUnion()) { | 441 } else if (this->is_union()) { |
473 UnionedHandle unioned = this->AsUnion(); | 442 Handle<Unioned> unioned = this->as_union(); |
474 for (int i = 0; i < unioned->length(); ++i) { | 443 for (int i = 0; i < unioned->length(); ++i) { |
475 TypeHandle type = Config::union_get(unioned, i); | 444 Handle<Type> type = union_get(unioned, i); |
476 ASSERT(i == 0 || | 445 ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); |
477 !(type->IsBitset() || type->Is(Config::union_get(unioned, 0)))); | 446 if (type->is_bitset()) continue; |
478 if (!type->IsBitset() && type->Is(that) && | 447 if (type->Is(that) && !type->InUnion(result, old_size)) |
479 !type->InUnion(result, old_size)) { | |
480 result->set(current_size++, *type); | 448 result->set(current_size++, *type); |
481 } | |
482 } | 449 } |
483 } | 450 } |
484 return current_size; | 451 return current_size; |
485 } | 452 } |
486 | 453 |
487 | 454 |
488 // Intersection is O(1) on simple bit unions, but O(n*m) on structured unions. | 455 // Intersection is O(1) on simple bit unions, but O(n*m) on structured unions. |
489 // TODO(rossberg): Should we use object sets somehow? Is it worth it? | 456 // TODO(rossberg): Should we use object sets somehow? Is it worth it? |
490 template<class Config> | 457 Type* Type::Intersect(Handle<Type> type1, Handle<Type> type2) { |
491 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect( | |
492 TypeHandle type1, TypeHandle type2, Region* region) { | |
493 // Fast case: bit sets. | 458 // Fast case: bit sets. |
494 if (type1->IsBitset() && type2->IsBitset()) { | 459 if (type1->is_bitset() && type2->is_bitset()) { |
495 return Config::from_bitset(type1->AsBitset() & type2->AsBitset(), region); | 460 return from_bitset(type1->as_bitset() & type2->as_bitset()); |
496 } | 461 } |
497 | 462 |
498 // Fast case: top or bottom types. | 463 // Fast case: top or bottom types. |
499 if (type1->IsNone()) return type1; | 464 if (type1->SameValue(Type::None())) return *type1; |
500 if (type2->IsNone()) return type2; | 465 if (type2->SameValue(Type::None())) return *type2; |
501 if (type1->IsAny()) return type2; | 466 if (type1->SameValue(Type::Any())) return *type2; |
502 if (type2->IsAny()) return type1; | 467 if (type2->SameValue(Type::Any())) return *type1; |
503 | 468 |
504 // Semi-fast case: Unioned objects are neither involved nor produced. | 469 // Semi-fast case: Unioned objects are neither involved nor produced. |
505 if (!(type1->IsUnion() || type2->IsUnion())) { | 470 if (!(type1->is_union() || type2->is_union())) { |
506 if (type1->Is(type2)) return type1; | 471 if (type1->Is(type2)) return *type1; |
507 if (type2->Is(type1)) return type2; | 472 if (type2->Is(type1)) return *type2; |
508 } | 473 } |
509 | 474 |
510 // Slow case: may need to produce a Unioned object. | 475 // Slow case: may need to produce a Unioned object. |
| 476 Isolate* isolate = NULL; |
511 int size = 0; | 477 int size = 0; |
512 if (!type1->IsBitset()) { | 478 if (!type1->is_bitset()) { |
513 size = (type1->IsUnion() ? type1->AsUnion()->length() : 2); | 479 isolate = i::HeapObject::cast(*type1)->GetIsolate(); |
| 480 size = (type1->is_union() ? type1->as_union()->length() : 2); |
514 } | 481 } |
515 if (!type2->IsBitset()) { | 482 if (!type2->is_bitset()) { |
516 int size2 = (type2->IsUnion() ? type2->AsUnion()->length() : 2); | 483 isolate = i::HeapObject::cast(*type2)->GetIsolate(); |
| 484 int size2 = (type2->is_union() ? type2->as_union()->length() : 2); |
517 size = (size == 0 ? size2 : Min(size, size2)); | 485 size = (size == 0 ? size2 : Min(size, size2)); |
518 } | 486 } |
| 487 ASSERT(isolate != NULL); |
519 ASSERT(size >= 2); | 488 ASSERT(size >= 2); |
520 UnionedHandle unioned = Config::union_create(size, region); | 489 Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); |
521 size = 0; | 490 size = 0; |
522 | 491 |
523 int bitset = type1->GlbBitset() & type2->GlbBitset(); | 492 int bitset = type1->GlbBitset() & type2->GlbBitset(); |
524 if (bitset != kNone) unioned->set(size++, Config::from_bitset(bitset)); | 493 if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); |
525 size = type1->ExtendIntersection(unioned, type2, size); | 494 size = type1->ExtendIntersection(unioned, type2, size); |
526 size = type2->ExtendIntersection(unioned, type1, size); | 495 size = type2->ExtendIntersection(unioned, type1, size); |
527 | 496 |
528 if (size == 0) { | 497 if (size == 0) { |
529 return None(region); | 498 return None(); |
530 } else if (size == 1) { | 499 } else if (size == 1) { |
531 return Config::union_get(unioned, 0); | 500 return *union_get(unioned, 0); |
532 } else if (size == unioned->length()) { | 501 } else if (size == unioned->length()) { |
533 return Config::from_union(unioned); | 502 return from_handle(unioned); |
534 } | 503 } |
535 | 504 |
536 // There were dropped cases. Copy to smaller union. | 505 // There were dropped cases. Copy to smaller union. |
537 UnionedHandle result = Config::union_create(size, region); | 506 Handle<Unioned> result = isolate->factory()->NewFixedArray(size); |
538 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); | 507 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); |
539 return Config::from_union(result); | 508 return from_handle(result); |
540 } | 509 } |
541 | 510 |
542 | 511 |
543 // TODO(rossberg): this does not belong here. | 512 Type* Type::Optional(Handle<Type> type) { |
| 513 return type->is_bitset() |
| 514 ? from_bitset(type->as_bitset() | kUndefined) |
| 515 : Union(type, Undefined()->handle_via_isolate_of(*type)); |
| 516 } |
| 517 |
| 518 |
544 Representation Representation::FromType(Handle<Type> type) { | 519 Representation Representation::FromType(Handle<Type> type) { |
545 if (type->Is(Type::None())) return Representation::None(); | 520 if (type->Is(Type::None())) return Representation::None(); |
546 if (type->Is(Type::Smi())) return Representation::Smi(); | 521 if (type->Is(Type::Smi())) return Representation::Smi(); |
547 if (type->Is(Type::Signed32())) return Representation::Integer32(); | 522 if (type->Is(Type::Signed32())) return Representation::Integer32(); |
548 if (type->Is(Type::Number())) return Representation::Double(); | 523 if (type->Is(Type::Number())) return Representation::Double(); |
549 return Representation::Tagged(); | 524 return Representation::Tagged(); |
550 } | 525 } |
551 | 526 |
552 | 527 |
553 #ifdef OBJECT_PRINT | 528 #ifdef OBJECT_PRINT |
554 template<class Config> | 529 void Type::TypePrint() { |
555 void TypeImpl<Config>::TypePrint() { | |
556 TypePrint(stdout); | 530 TypePrint(stdout); |
557 PrintF(stdout, "\n"); | 531 PrintF(stdout, "\n"); |
558 Flush(stdout); | 532 Flush(stdout); |
559 } | 533 } |
560 | 534 |
561 | 535 |
562 template<class Config> | 536 const char* Type::bitset_name(int bitset) { |
563 const char* TypeImpl<Config>::bitset_name(int bitset) { | |
564 switch (bitset) { | 537 switch (bitset) { |
565 #define PRINT_COMPOSED_TYPE(type, value) case k##type: return #type; | 538 #define PRINT_COMPOSED_TYPE(type, value) case k##type: return #type; |
566 BITSET_TYPE_LIST(PRINT_COMPOSED_TYPE) | 539 BITSET_TYPE_LIST(PRINT_COMPOSED_TYPE) |
567 #undef PRINT_COMPOSED_TYPE | 540 #undef PRINT_COMPOSED_TYPE |
568 default: | 541 default: |
569 return NULL; | 542 return NULL; |
570 } | 543 } |
571 } | 544 } |
572 | 545 |
573 | 546 |
574 template<class Config> | 547 void Type::TypePrint(FILE* out) { |
575 void TypeImpl<Config>::TypePrint(FILE* out) { | 548 if (is_bitset()) { |
576 if (this->IsBitset()) { | 549 int bitset = as_bitset(); |
577 int bitset = this->AsBitset(); | |
578 const char* name = bitset_name(bitset); | 550 const char* name = bitset_name(bitset); |
579 if (name != NULL) { | 551 if (name != NULL) { |
580 PrintF(out, "%s", name); | 552 PrintF(out, "%s", name); |
581 } else { | 553 } else { |
582 bool is_first = true; | 554 bool is_first = true; |
583 PrintF(out, "("); | 555 PrintF(out, "("); |
584 for (int mask = 1; mask != 0; mask = mask << 1) { | 556 for (int mask = 1; mask != 0; mask = mask << 1) { |
585 if ((bitset & mask) != 0) { | 557 if ((bitset & mask) != 0) { |
586 if (!is_first) PrintF(out, " | "); | 558 if (!is_first) PrintF(out, " | "); |
587 is_first = false; | 559 is_first = false; |
588 PrintF(out, "%s", bitset_name(mask)); | 560 PrintF(out, "%s", bitset_name(mask)); |
589 } | 561 } |
590 } | 562 } |
591 PrintF(out, ")"); | 563 PrintF(out, ")"); |
592 } | 564 } |
593 } else if (this->IsConstant()) { | 565 } else if (is_constant()) { |
594 PrintF(out, "Constant(%p : ", static_cast<void*>(*this->AsConstant())); | 566 PrintF(out, "Constant(%p : ", static_cast<void*>(*as_constant())); |
595 Config::from_bitset(this->LubBitset())->TypePrint(out); | 567 from_bitset(LubBitset())->TypePrint(out); |
596 PrintF(")"); | 568 PrintF(")"); |
597 } else if (this->IsClass()) { | 569 } else if (is_class()) { |
598 PrintF(out, "Class(%p < ", static_cast<void*>(*this->AsClass())); | 570 PrintF(out, "Class(%p < ", static_cast<void*>(*as_class())); |
599 Config::from_bitset(this->LubBitset())->TypePrint(out); | 571 from_bitset(LubBitset())->TypePrint(out); |
600 PrintF(")"); | 572 PrintF(")"); |
601 } else if (this->IsUnion()) { | 573 } else if (is_union()) { |
602 PrintF(out, "("); | 574 PrintF(out, "("); |
603 UnionedHandle unioned = this->AsUnion(); | 575 Handle<Unioned> unioned = as_union(); |
604 for (int i = 0; i < unioned->length(); ++i) { | 576 for (int i = 0; i < unioned->length(); ++i) { |
605 TypeHandle type_i = Config::union_get(unioned, i); | 577 Handle<Type> type_i = union_get(unioned, i); |
606 if (i > 0) PrintF(out, " | "); | 578 if (i > 0) PrintF(out, " | "); |
607 type_i->TypePrint(out); | 579 type_i->TypePrint(out); |
608 } | 580 } |
609 PrintF(out, ")"); | 581 PrintF(out, ")"); |
610 } | 582 } |
611 } | 583 } |
612 #endif | 584 #endif |
613 | 585 |
614 | 586 |
615 template class TypeImpl<HeapTypeConfig>; | |
616 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>; | |
617 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>; | |
618 | |
619 | |
620 } } // namespace v8::internal | 587 } } // namespace v8::internal |
OLD | NEW |