1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <iomanip>
6
7 #include "src/types.h"
8
9 #include "src/ostreams.h"
10 #include "src/types-inl.h"
11
12 namespace v8 {
13 namespace internal {
14
15
16 // NOTE: If code is marked as being a "shortcut", this means that removing
17 // the code won't affect the semantics of the surrounding function definition.
18
19
20 // -----------------------------------------------------------------------------
21 // Range-related helper functions.
22
23 template <class Config>
IsEmpty()24 bool TypeImpl<Config>::Limits::IsEmpty() {
25 return this->min > this->max;
26 }
27
28
29 template<class Config>
Intersect(Limits lhs,Limits rhs)30 typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Intersect(
31 Limits lhs, Limits rhs) {
32 DisallowHeapAllocation no_allocation;
33 Limits result(lhs);
34 if (lhs.min < rhs.min) result.min = rhs.min;
35 if (lhs.max > rhs.max) result.max = rhs.max;
36 return result;
37 }
38
39
40 template <class Config>
Union(Limits lhs,Limits rhs)41 typename TypeImpl<Config>::Limits TypeImpl<Config>::Limits::Union(
42 Limits lhs, Limits rhs) {
43 DisallowHeapAllocation no_allocation;
44 if (lhs.IsEmpty()) return rhs;
45 if (rhs.IsEmpty()) return lhs;
46 Limits result(lhs);
47 if (lhs.min > rhs.min) result.min = rhs.min;
48 if (lhs.max < rhs.max) result.max = rhs.max;
49 return result;
50 }
51
52
53 template<class Config>
Overlap(typename TypeImpl<Config>::RangeType * lhs,typename TypeImpl<Config>::RangeType * rhs)54 bool TypeImpl<Config>::Overlap(
55 typename TypeImpl<Config>::RangeType* lhs,
56 typename TypeImpl<Config>::RangeType* rhs) {
57 DisallowHeapAllocation no_allocation;
58 return !Limits::Intersect(Limits(lhs), Limits(rhs)).IsEmpty();
59 }
60
61
62 template<class Config>
Contains(typename TypeImpl<Config>::RangeType * lhs,typename TypeImpl<Config>::RangeType * rhs)63 bool TypeImpl<Config>::Contains(
64 typename TypeImpl<Config>::RangeType* lhs,
65 typename TypeImpl<Config>::RangeType* rhs) {
66 DisallowHeapAllocation no_allocation;
67 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
68 }
69
70
71 template <class Config>
Contains(typename TypeImpl<Config>::RangeType * lhs,typename TypeImpl<Config>::ConstantType * rhs)72 bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs,
73 typename TypeImpl<Config>::ConstantType* rhs) {
74 DisallowHeapAllocation no_allocation;
75 return IsInteger(*rhs->Value()) &&
76 lhs->Min() <= rhs->Value()->Number() &&
77 rhs->Value()->Number() <= lhs->Max();
78 }
79
80
81 template<class Config>
Contains(typename TypeImpl<Config>::RangeType * range,i::Object * val)82 bool TypeImpl<Config>::Contains(
83 typename TypeImpl<Config>::RangeType* range, i::Object* val) {
84 DisallowHeapAllocation no_allocation;
85 return IsInteger(val) &&
86 range->Min() <= val->Number() && val->Number() <= range->Max();
87 }
88
89
90 // -----------------------------------------------------------------------------
91 // Min and Max computation.
92
93 template<class Config>
Min()94 double TypeImpl<Config>::Min() {
95 DCHECK(this->SemanticIs(Number()));
96 if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
97 if (this->IsUnion()) {
98 double min = +V8_INFINITY;
99 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
100 min = std::min(min, this->AsUnion()->Get(i)->Min());
101 }
102 return min;
103 }
104 if (this->IsRange()) return this->AsRange()->Min();
105 if (this->IsConstant()) return this->AsConstant()->Value()->Number();
106 UNREACHABLE();
107 return 0;
108 }
109
110
111 template<class Config>
Max()112 double TypeImpl<Config>::Max() {
113 DCHECK(this->SemanticIs(Number()));
114 if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
115 if (this->IsUnion()) {
116 double max = -V8_INFINITY;
117 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
118 max = std::max(max, this->AsUnion()->Get(i)->Max());
119 }
120 return max;
121 }
122 if (this->IsRange()) return this->AsRange()->Max();
123 if (this->IsConstant()) return this->AsConstant()->Value()->Number();
124 UNREACHABLE();
125 return 0;
126 }
127
128
129 // -----------------------------------------------------------------------------
130 // Glb and lub computation.
131
132
133 // The largest bitset subsumed by this type.
134 template<class Config>
135 typename TypeImpl<Config>::bitset
Glb(TypeImpl * type)136 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
137 DisallowHeapAllocation no_allocation;
138 // Fast case.
139 if (type->IsBitset()) {
140 return type->AsBitset();
141 } else if (type->IsUnion()) {
142 SLOW_DCHECK(type->AsUnion()->Wellformed());
143 return type->AsUnion()->Get(0)->BitsetGlb() |
144 SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut.
145 } else if (type->IsRange()) {
146 bitset glb = SEMANTIC(
147 BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
148 return glb | REPRESENTATION(type->BitsetLub());
149 } else {
150 return type->Representation();
151 }
152 }
153
154
155 // The smallest bitset subsuming this type, possibly not a proper one.
156 template<class Config>
157 typename TypeImpl<Config>::bitset
Lub(TypeImpl * type)158 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
159 DisallowHeapAllocation no_allocation;
160 if (type->IsBitset()) return type->AsBitset();
161 if (type->IsUnion()) {
162 // Take the representation from the first element, which is always
163 // a bitset.
164 int bitset = type->AsUnion()->Get(0)->BitsetLub();
165 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
166 // Other elements only contribute their semantic part.
167 bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
168 }
169 return bitset;
170 }
171 if (type->IsClass()) return type->AsClass()->Lub();
172 if (type->IsConstant()) return type->AsConstant()->Lub();
173 if (type->IsRange()) return type->AsRange()->Lub();
174 if (type->IsContext()) return kInternal & kTaggedPointer;
175 if (type->IsArray()) return kOtherObject;
176 if (type->IsFunction()) return kFunction;
177 UNREACHABLE();
178 return kNone;
179 }
180
181
182 template<class Config>
183 typename TypeImpl<Config>::bitset
Lub(i::Map * map)184 TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
185 DisallowHeapAllocation no_allocation;
186 switch (map->instance_type()) {
187 case STRING_TYPE:
188 case ONE_BYTE_STRING_TYPE:
189 case CONS_STRING_TYPE:
190 case CONS_ONE_BYTE_STRING_TYPE:
191 case SLICED_STRING_TYPE:
192 case SLICED_ONE_BYTE_STRING_TYPE:
193 case EXTERNAL_STRING_TYPE:
194 case EXTERNAL_ONE_BYTE_STRING_TYPE:
195 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
196 case SHORT_EXTERNAL_STRING_TYPE:
197 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
198 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
199 return kOtherString;
200 case INTERNALIZED_STRING_TYPE:
201 case ONE_BYTE_INTERNALIZED_STRING_TYPE:
202 case EXTERNAL_INTERNALIZED_STRING_TYPE:
203 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
204 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
205 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
206 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
207 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
208 return kInternalizedString;
209 case SYMBOL_TYPE:
210 return kSymbol;
211 case ODDBALL_TYPE: {
212 Heap* heap = map->GetHeap();
213 if (map == heap->undefined_map()) return kUndefined;
214 if (map == heap->null_map()) return kNull;
215 if (map == heap->boolean_map()) return kBoolean;
216 DCHECK(map == heap->the_hole_map() ||
217 map == heap->uninitialized_map() ||
218 map == heap->no_interceptor_result_sentinel_map() ||
219 map == heap->termination_exception_map() ||
220 map == heap->arguments_marker_map());
221 return kInternal & kTaggedPointer;
222 }
223 case HEAP_NUMBER_TYPE:
224 return kNumber & kTaggedPointer;
225 case SIMD128_VALUE_TYPE:
226 return kSimd;
227 case JS_VALUE_TYPE:
228 case JS_MESSAGE_OBJECT_TYPE:
229 case JS_DATE_TYPE:
230 case JS_OBJECT_TYPE:
231 case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
232 case JS_GENERATOR_OBJECT_TYPE:
233 case JS_MODULE_TYPE:
234 case JS_GLOBAL_OBJECT_TYPE:
235 case JS_GLOBAL_PROXY_TYPE:
236 case JS_ARRAY_BUFFER_TYPE:
237 case JS_ARRAY_TYPE:
238 case JS_TYPED_ARRAY_TYPE:
239 case JS_DATA_VIEW_TYPE:
240 case JS_SET_TYPE:
241 case JS_MAP_TYPE:
242 case JS_SET_ITERATOR_TYPE:
243 case JS_MAP_ITERATOR_TYPE:
244 case JS_ITERATOR_RESULT_TYPE:
245 case JS_WEAK_MAP_TYPE:
246 case JS_WEAK_SET_TYPE:
247 case JS_PROMISE_TYPE:
248 case JS_BOUND_FUNCTION_TYPE:
249 if (map->is_undetectable()) return kUndetectable;
250 return kOtherObject;
251 case JS_FUNCTION_TYPE:
252 if (map->is_undetectable()) return kUndetectable;
253 return kFunction;
254 case JS_REGEXP_TYPE:
255 return kOtherObject; // TODO(rossberg): there should be a RegExp type.
256 case JS_PROXY_TYPE:
257 return kProxy;
258 case MAP_TYPE:
259 // When compiling stub templates, the meta map is used as a place holder
260 // for the actual map with which the template is later instantiated.
261 // We treat it as a kind of type variable whose upper bound is Any.
262 // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
263 // we must exclude Undetectable here. This makes no sense, really,
264 // because it means that the template isn't actually parametric.
265 // Also, it doesn't apply elsewhere. 8-(
266 // We ought to find a cleaner solution for compiling stubs parameterised
267 // over type or class variables, esp ones with bounds...
268 return kDetectable & kTaggedPointer;
269 case ALLOCATION_SITE_TYPE:
270 case DECLARED_ACCESSOR_INFO_TYPE:
271 case EXECUTABLE_ACCESSOR_INFO_TYPE:
272 case SHARED_FUNCTION_INFO_TYPE:
273 case ACCESSOR_PAIR_TYPE:
274 case FIXED_ARRAY_TYPE:
275 case FIXED_DOUBLE_ARRAY_TYPE:
276 case BYTE_ARRAY_TYPE:
277 case BYTECODE_ARRAY_TYPE:
278 case TRANSITION_ARRAY_TYPE:
279 case FOREIGN_TYPE:
280 case SCRIPT_TYPE:
281 case CODE_TYPE:
282 case PROPERTY_CELL_TYPE:
283 return kInternal & kTaggedPointer;
284
285 // Remaining instance types are unsupported for now. If any of them do
286 // require bit set types, they should get kInternal & kTaggedPointer.
287 case MUTABLE_HEAP_NUMBER_TYPE:
288 case FREE_SPACE_TYPE:
289 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
290 case FIXED_##TYPE##_ARRAY_TYPE:
291
292 TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
293 #undef FIXED_TYPED_ARRAY_CASE
294 case FILLER_TYPE:
295 case DECLARED_ACCESSOR_DESCRIPTOR_TYPE:
296 case ACCESS_CHECK_INFO_TYPE:
297 case INTERCEPTOR_INFO_TYPE:
298 case CALL_HANDLER_INFO_TYPE:
299 case FUNCTION_TEMPLATE_INFO_TYPE:
300 case OBJECT_TEMPLATE_INFO_TYPE:
301 case SIGNATURE_INFO_TYPE:
302 case TYPE_SWITCH_INFO_TYPE:
303 case ALLOCATION_MEMENTO_TYPE:
304 case CODE_CACHE_TYPE:
305 case POLYMORPHIC_CODE_CACHE_TYPE:
306 case TYPE_FEEDBACK_INFO_TYPE:
307 case ALIASED_ARGUMENTS_ENTRY_TYPE:
308 case BOX_TYPE:
309 case DEBUG_INFO_TYPE:
310 case BREAK_POINT_INFO_TYPE:
311 case CELL_TYPE:
312 case WEAK_CELL_TYPE:
313 case PROTOTYPE_INFO_TYPE:
314 case SLOPPY_BLOCK_WITH_EVAL_CONTEXT_EXTENSION_TYPE:
315 UNREACHABLE();
316 return kNone;
317 }
318 UNREACHABLE();
319 return kNone;
320 }
321
322
323 template<class Config>
324 typename TypeImpl<Config>::bitset
Lub(i::Object * value)325 TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
326 DisallowHeapAllocation no_allocation;
327 if (value->IsNumber()) {
328 return Lub(value->Number()) &
329 (value->IsSmi() ? kTaggedSigned : kTaggedPointer);
330 }
331 return Lub(i::HeapObject::cast(value)->map());
332 }
333
334
335 template<class Config>
336 typename TypeImpl<Config>::bitset
Lub(double value)337 TypeImpl<Config>::BitsetType::Lub(double value) {
338 DisallowHeapAllocation no_allocation;
339 if (i::IsMinusZero(value)) return kMinusZero;
340 if (std::isnan(value)) return kNaN;
341 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
342 return kOtherNumber;
343 }
344
345
346 // Minimum values of plain numeric bitsets.
347 template <class Config>
348 const typename TypeImpl<Config>::BitsetType::Boundary
349 TypeImpl<Config>::BitsetType::BoundariesArray[] = {
350 {kOtherNumber, kPlainNumber, -V8_INFINITY},
351 {kOtherSigned32, kNegative32, kMinInt},
352 {kNegative31, kNegative31, -0x40000000},
353 {kUnsigned30, kUnsigned30, 0},
354 {kOtherUnsigned31, kUnsigned31, 0x40000000},
355 {kOtherUnsigned32, kUnsigned32, 0x80000000},
356 {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
357
358
359 template <class Config>
360 const typename TypeImpl<Config>::BitsetType::Boundary*
Boundaries()361 TypeImpl<Config>::BitsetType::Boundaries() {
362 return BoundariesArray;
363 }
364
365
366 template <class Config>
BoundariesSize()367 size_t TypeImpl<Config>::BitsetType::BoundariesSize() {
368 // Windows doesn't like arraysize here.
369 // return arraysize(BoundariesArray);
370 return 7;
371 }
372
373
374 template <class Config>
ExpandInternals(typename TypeImpl<Config>::bitset bits)375 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::ExpandInternals(
376 typename TypeImpl<Config>::bitset bits) {
377 DisallowHeapAllocation no_allocation;
378 if (!(bits & SEMANTIC(kPlainNumber))) return bits; // Shortcut.
379 const Boundary* boundaries = Boundaries();
380 for (size_t i = 0; i < BoundariesSize(); ++i) {
381 DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external));
382 if (bits & SEMANTIC(boundaries[i].internal))
383 bits |= SEMANTIC(boundaries[i].external);
384 }
385 return bits;
386 }
387
388
389 template<class Config>
390 typename TypeImpl<Config>::bitset
Lub(double min,double max)391 TypeImpl<Config>::BitsetType::Lub(double min, double max) {
392 DisallowHeapAllocation no_allocation;
393 int lub = kNone;
394 const Boundary* mins = Boundaries();
395
396 for (size_t i = 1; i < BoundariesSize(); ++i) {
397 if (min < mins[i].min) {
398 lub |= mins[i-1].internal;
399 if (max < mins[i].min) return lub;
400 }
401 }
402 return lub | mins[BoundariesSize() - 1].internal;
403 }
404
405
406 template <class Config>
NumberBits(bitset bits)407 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::NumberBits(
408 bitset bits) {
409 return SEMANTIC(bits & kPlainNumber);
410 }
411
412
413 template <class Config>
Glb(double min,double max)414 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::Glb(
415 double min, double max) {
416 DisallowHeapAllocation no_allocation;
417 int glb = kNone;
418 const Boundary* mins = Boundaries();
419
420 // If the range does not touch 0, the bound is empty.
421 if (max < -1 || min > 0) return glb;
422
423 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
424 if (min <= mins[i].min) {
425 if (max + 1 < mins[i + 1].min) break;
426 glb |= mins[i].external;
427 }
428 }
429 // OtherNumber also contains float numbers, so it can never be
430 // in the greatest lower bound.
431 return glb & ~(SEMANTIC(kOtherNumber));
432 }
433
434
435 template <class Config>
Min(bitset bits)436 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
437 DisallowHeapAllocation no_allocation;
438 DCHECK(Is(SEMANTIC(bits), kNumber));
439 const Boundary* mins = Boundaries();
440 bool mz = SEMANTIC(bits & kMinusZero);
441 for (size_t i = 0; i < BoundariesSize(); ++i) {
442 if (Is(SEMANTIC(mins[i].internal), bits)) {
443 return mz ? std::min(0.0, mins[i].min) : mins[i].min;
444 }
445 }
446 if (mz) return 0;
447 return std::numeric_limits<double>::quiet_NaN();
448 }
449
450
451 template<class Config>
Max(bitset bits)452 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
453 DisallowHeapAllocation no_allocation;
454 DCHECK(Is(SEMANTIC(bits), kNumber));
455 const Boundary* mins = Boundaries();
456 bool mz = SEMANTIC(bits & kMinusZero);
457 if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].internal), bits)) {
458 return +V8_INFINITY;
459 }
460 for (size_t i = BoundariesSize() - 1; i-- > 0;) {
461 if (Is(SEMANTIC(mins[i].internal), bits)) {
462 return mz ?
463 std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
464 }
465 }
466 if (mz) return 0;
467 return std::numeric_limits<double>::quiet_NaN();
468 }
469
470
471 // -----------------------------------------------------------------------------
472 // Predicates.
473
474
475 template<class Config>
SimplyEquals(TypeImpl * that)476 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) {
477 DisallowHeapAllocation no_allocation;
478 if (this->IsClass()) {
479 return that->IsClass()
480 && *this->AsClass()->Map() == *that->AsClass()->Map();
481 }
482 if (this->IsConstant()) {
483 return that->IsConstant()
484 && *this->AsConstant()->Value() == *that->AsConstant()->Value();
485 }
486 if (this->IsContext()) {
487 return that->IsContext()
488 && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
489 }
490 if (this->IsArray()) {
491 return that->IsArray()
492 && this->AsArray()->Element()->Equals(that->AsArray()->Element());
493 }
494 if (this->IsFunction()) {
495 if (!that->IsFunction()) return false;
496 FunctionType* this_fun = this->AsFunction();
497 FunctionType* that_fun = that->AsFunction();
498 if (this_fun->Arity() != that_fun->Arity() ||
499 !this_fun->Result()->Equals(that_fun->Result()) ||
500 !this_fun->Receiver()->Equals(that_fun->Receiver())) {
501 return false;
502 }
503 for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
504 if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
505 }
506 return true;
507 }
508 UNREACHABLE();
509 return false;
510 }
511
512
513 template <class Config>
Representation()514 typename TypeImpl<Config>::bitset TypeImpl<Config>::Representation() {
515 return REPRESENTATION(this->BitsetLub());
516 }
517
518
519 // Check if [this] <= [that].
520 template<class Config>
SlowIs(TypeImpl * that)521 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
522 DisallowHeapAllocation no_allocation;
523
524 // Fast bitset cases
525 if (that->IsBitset()) {
526 return BitsetType::Is(this->BitsetLub(), that->AsBitset());
527 }
528
529 if (this->IsBitset()) {
530 return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
531 }
532
533 // Check the representations.
534 if (!BitsetType::Is(Representation(), that->Representation())) {
535 return false;
536 }
537
538 // Check the semantic part.
539 return SemanticIs(that);
540 }
541
542
543 // Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method
544 // should be independent of the representation axis of the types.
545 template <class Config>
SemanticIs(TypeImpl * that)546 bool TypeImpl<Config>::SemanticIs(TypeImpl* that) {
547 DisallowHeapAllocation no_allocation;
548
549 if (this == that) return true;
550
551 if (that->IsBitset()) {
552 return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset());
553 }
554 if (this->IsBitset()) {
555 return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb());
556 }
557
558 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
559 if (this->IsUnion()) {
560 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
561 if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
562 }
563 return true;
564 }
565
566 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
567 if (that->IsUnion()) {
568 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
569 if (this->SemanticIs(that->AsUnion()->Get(i)->unhandle())) return true;
570 if (i > 1 && this->IsRange()) return false; // Shortcut.
571 }
572 return false;
573 }
574
575 if (that->IsRange()) {
576 return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
577 (this->IsConstant() &&
578 Contains(that->AsRange(), this->AsConstant()));
579 }
580 if (this->IsRange()) return false;
581
582 return this->SimplyEquals(that);
583 }
584
585
586 template<class Config>
NowIs(TypeImpl * that)587 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
588 DisallowHeapAllocation no_allocation;
589
590 // TODO(rossberg): this is incorrect for
591 // Union(Constant(V), T)->NowIs(Class(M))
592 // but fuzzing does not cover that!
593 if (this->IsConstant()) {
594 i::Object* object = *this->AsConstant()->Value();
595 if (object->IsHeapObject()) {
596 i::Map* map = i::HeapObject::cast(object)->map();
597 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
598 if (*it.Current() == map) return true;
599 }
600 }
601 }
602 return this->Is(that);
603 }
604
605
606 // Check if [this] contains only (currently) stable classes.
607 template<class Config>
NowStable()608 bool TypeImpl<Config>::NowStable() {
609 DisallowHeapAllocation no_allocation;
610 return !this->IsClass() || this->AsClass()->Map()->is_stable();
611 }
612
613
614 // Check if [this] and [that] overlap.
615 template<class Config>
Maybe(TypeImpl * that)616 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
617 DisallowHeapAllocation no_allocation;
618
619 // Take care of the representation part (and also approximate
620 // the semantic part).
621 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
622 return false;
623
624 return SemanticMaybe(that);
625 }
626
627 template <class Config>
SemanticMaybe(TypeImpl * that)628 bool TypeImpl<Config>::SemanticMaybe(TypeImpl* that) {
629 DisallowHeapAllocation no_allocation;
630
631 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
632 if (this->IsUnion()) {
633 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
634 if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
635 }
636 return false;
637 }
638
639 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
640 if (that->IsUnion()) {
641 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
642 if (this->SemanticMaybe(that->AsUnion()->Get(i)->unhandle())) return true;
643 }
644 return false;
645 }
646
647 if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub()))
648 return false;
649
650 if (this->IsBitset() && that->IsBitset()) return true;
651
652 if (this->IsClass() != that->IsClass()) return true;
653
654 if (this->IsRange()) {
655 if (that->IsConstant()) {
656 return Contains(this->AsRange(), that->AsConstant());
657 }
658 if (that->IsRange()) {
659 return Overlap(this->AsRange(), that->AsRange());
660 }
661 if (that->IsBitset()) {
662 bitset number_bits = BitsetType::NumberBits(that->AsBitset());
663 if (number_bits == BitsetType::kNone) {
664 return false;
665 }
666 double min = std::max(BitsetType::Min(number_bits), this->Min());
667 double max = std::min(BitsetType::Max(number_bits), this->Max());
668 return min <= max;
669 }
670 }
671 if (that->IsRange()) {
672 return that->SemanticMaybe(this); // This case is handled above.
673 }
674
675 if (this->IsBitset() || that->IsBitset()) return true;
676
677 return this->SimplyEquals(that);
678 }
679
680
681 // Return the range in [this], or [NULL].
682 template<class Config>
GetRange()683 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
684 DisallowHeapAllocation no_allocation;
685 if (this->IsRange()) return this->AsRange();
686 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
687 return this->AsUnion()->Get(1)->AsRange();
688 }
689 return NULL;
690 }
691
692
693 template<class Config>
Contains(i::Object * value)694 bool TypeImpl<Config>::Contains(i::Object* value) {
695 DisallowHeapAllocation no_allocation;
696 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
697 if (*it.Current() == value) return true;
698 }
699 if (IsInteger(value)) {
700 RangeType* range = this->GetRange();
701 if (range != NULL && Contains(range, value)) return true;
702 }
703 return BitsetType::New(BitsetType::Lub(value))->Is(this);
704 }
705
706
707 template<class Config>
Wellformed()708 bool TypeImpl<Config>::UnionType::Wellformed() {
709 DisallowHeapAllocation no_allocation;
710 // This checks the invariants of the union representation:
711 // 1. There are at least two elements.
712 // 2. The first element is a bitset, no other element is a bitset.
713 // 3. At most one element is a range, and it must be the second one.
714 // 4. No element is itself a union.
715 // 5. No element (except the bitset) is a subtype of any other.
716 // 6. If there is a range, then the bitset type does not contain
717 // plain number bits.
718 DCHECK(this->Length() >= 2); // (1)
719 DCHECK(this->Get(0)->IsBitset()); // (2a)
720
721 for (int i = 0; i < this->Length(); ++i) {
722 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b)
723 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
724 DCHECK(!this->Get(i)->IsUnion()); // (4)
725 for (int j = 0; j < this->Length(); ++j) {
726 if (i != j && i != 0)
727 DCHECK(!this->Get(i)->SemanticIs(this->Get(j)->unhandle())); // (5)
728 }
729 }
730 DCHECK(!this->Get(1)->IsRange() ||
731 (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
732 BitsetType::kNone)); // (6)
733 return true;
734 }
735
736
737 // -----------------------------------------------------------------------------
738 // Union and intersection
739
740
AddIsSafe(int x,int y)741 static bool AddIsSafe(int x, int y) {
742 return x >= 0 ?
743 y <= std::numeric_limits<int>::max() - x :
744 y >= std::numeric_limits<int>::min() - x;
745 }
746
747
748 template<class Config>
Intersect(TypeHandle type1,TypeHandle type2,Region * region)749 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
750 TypeHandle type1, TypeHandle type2, Region* region) {
751
752 // Fast case: bit sets.
753 if (type1->IsBitset() && type2->IsBitset()) {
754 return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
755 }
756
757 // Fast case: top or bottom types.
758 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut.
759 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut.
760
761 // Semi-fast case.
762 if (type1->Is(type2)) return type1;
763 if (type2->Is(type1)) return type2;
764
765 // Slow case: create union.
766
767 // Figure out the representation of the result first.
768 // The rest of the method should not change this representation and
769 // it should not make any decisions based on representations (i.e.,
770 // it should only use the semantic part of types).
771 const bitset representation =
772 type1->Representation() & type2->Representation();
773
774 // Semantic subtyping check - this is needed for consistency with the
775 // semi-fast case above - we should behave the same way regardless of
776 // representations. Intersection with a universal bitset should only update
777 // the representations.
778 if (type1->SemanticIs(type2->unhandle())) {
779 type2 = Any(region);
780 } else if (type2->SemanticIs(type1->unhandle())) {
781 type1 = Any(region);
782 }
783
784 bitset bits =
785 SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
786 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
787 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
788 if (!AddIsSafe(size1, size2)) return Any(region);
789 int size = size1 + size2;
790 if (!AddIsSafe(size, 2)) return Any(region);
791 size += 2;
792 UnionHandle result = UnionType::New(size, region);
793 size = 0;
794
795 // Deal with bitsets.
796 result->Set(size++, BitsetType::New(bits, region));
797
798 Limits lims = Limits::Empty();
799 size = IntersectAux(type1, type2, result, size, &lims, region);
800
801 // If the range is not empty, then insert it into the union and
802 // remove the number bits from the bitset.
803 if (!lims.IsEmpty()) {
804 size = UpdateRange(RangeType::New(lims, representation, region), result,
805 size, region);
806
807 // Remove the number bits.
808 bitset number_bits = BitsetType::NumberBits(bits);
809 bits &= ~number_bits;
810 result->Set(0, BitsetType::New(bits, region));
811 }
812 return NormalizeUnion(result, size, region);
813 }
814
815
816 template<class Config>
UpdateRange(RangeHandle range,UnionHandle result,int size,Region * region)817 int TypeImpl<Config>::UpdateRange(
818 RangeHandle range, UnionHandle result, int size, Region* region) {
819 if (size == 1) {
820 result->Set(size++, range);
821 } else {
822 // Make space for the range.
823 result->Set(size++, result->Get(1));
824 result->Set(1, range);
825 }
826
827 // Remove any components that just got subsumed.
828 for (int i = 2; i < size; ) {
829 if (result->Get(i)->SemanticIs(range->unhandle())) {
830 result->Set(i, result->Get(--size));
831 } else {
832 ++i;
833 }
834 }
835 return size;
836 }
837
838
839 template <class Config>
ToLimits(bitset bits,Region * region)840 typename TypeImpl<Config>::Limits TypeImpl<Config>::ToLimits(bitset bits,
841 Region* region) {
842 bitset number_bits = BitsetType::NumberBits(bits);
843
844 if (number_bits == BitsetType::kNone) {
845 return Limits::Empty();
846 }
847
848 return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits));
849 }
850
851
852 template <class Config>
IntersectRangeAndBitset(TypeHandle range,TypeHandle bitset,Region * region)853 typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset(
854 TypeHandle range, TypeHandle bitset, Region* region) {
855 Limits range_lims(range->AsRange());
856 Limits bitset_lims = ToLimits(bitset->AsBitset(), region);
857 return Limits::Intersect(range_lims, bitset_lims);
858 }
859
860
861 template <class Config>
IntersectAux(TypeHandle lhs,TypeHandle rhs,UnionHandle result,int size,Limits * lims,Region * region)862 int TypeImpl<Config>::IntersectAux(TypeHandle lhs, TypeHandle rhs,
863 UnionHandle result, int size, Limits* lims,
864 Region* region) {
865 if (lhs->IsUnion()) {
866 for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
867 size =
868 IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, region);
869 }
870 return size;
871 }
872 if (rhs->IsUnion()) {
873 for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
874 size =
875 IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region);
876 }
877 return size;
878 }
879
880 if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
881 return size;
882 }
883
884 if (lhs->IsRange()) {
885 if (rhs->IsBitset()) {
886 Limits lim = IntersectRangeAndBitset(lhs, rhs, region);
887
888 if (!lim.IsEmpty()) {
889 *lims = Limits::Union(lim, *lims);
890 }
891 return size;
892 }
893 if (rhs->IsClass()) {
894 *lims = Limits::Union(Limits(lhs->AsRange()), *lims);
895 }
896 if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
897 return AddToUnion(rhs, result, size, region);
898 }
899 if (rhs->IsRange()) {
900 Limits lim = Limits::Intersect(
901 Limits(lhs->AsRange()), Limits(rhs->AsRange()));
902 if (!lim.IsEmpty()) {
903 *lims = Limits::Union(lim, *lims);
904 }
905 }
906 return size;
907 }
908 if (rhs->IsRange()) {
909 // This case is handled symmetrically above.
910 return IntersectAux(rhs, lhs, result, size, lims, region);
911 }
912 if (lhs->IsBitset() || rhs->IsBitset()) {
913 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
914 }
915 if (lhs->IsClass() != rhs->IsClass()) {
916 return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region);
917 }
918 if (lhs->SimplyEquals(rhs->unhandle())) {
919 return AddToUnion(lhs, result, size, region);
920 }
921 return size;
922 }
923
924
925 // Make sure that we produce a well-formed range and bitset:
926 // If the range is non-empty, the number bits in the bitset should be
927 // clear. Moreover, if we have a canonical range (such as Signed32),
928 // we want to produce a bitset rather than a range.
929 template <class Config>
NormalizeRangeAndBitset(RangeHandle range,bitset * bits,Region * region)930 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeRangeAndBitset(
931 RangeHandle range, bitset* bits, Region* region) {
932 // Fast path: If the bitset does not mention numbers, we can just keep the
933 // range.
934 bitset number_bits = BitsetType::NumberBits(*bits);
935 if (number_bits == 0) {
936 return range;
937 }
938
939 // If the range is semantically contained within the bitset, return None and
940 // leave the bitset untouched.
941 bitset range_lub = SEMANTIC(range->BitsetLub());
942 if (BitsetType::Is(range_lub, *bits)) {
943 return None(region);
944 }
945
946 // Slow path: reconcile the bitset range and the range.
947 double bitset_min = BitsetType::Min(number_bits);
948 double bitset_max = BitsetType::Max(number_bits);
949
950 double range_min = range->Min();
951 double range_max = range->Max();
952
953 // Remove the number bits from the bitset, they would just confuse us now.
954 // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
955 // case we already returned after the subtype check above.
956 *bits &= ~number_bits;
957
958 if (range_min <= bitset_min && range_max >= bitset_max) {
959 // Bitset is contained within the range, just return the range.
960 return range;
961 }
962
963 if (bitset_min < range_min) {
964 range_min = bitset_min;
965 }
966 if (bitset_max > range_max) {
967 range_max = bitset_max;
968 }
969 return RangeType::New(range_min, range_max,
970 BitsetType::New(BitsetType::kNone, region), region);
971 }
972
973
974 template<class Config>
Union(TypeHandle type1,TypeHandle type2,Region * region)975 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
976 TypeHandle type1, TypeHandle type2, Region* region) {
977 // Fast case: bit sets.
978 if (type1->IsBitset() && type2->IsBitset()) {
979 return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
980 }
981
982 // Fast case: top or bottom types.
983 if (type1->IsAny() || type2->IsNone()) return type1;
984 if (type2->IsAny() || type1->IsNone()) return type2;
985
986 // Semi-fast case.
987 if (type1->Is(type2)) return type2;
988 if (type2->Is(type1)) return type1;
989
990 // Figure out the representation of the result.
991 // The rest of the method should not change this representation and
992 // it should not make any decisions based on representations (i.e.,
993 // it should only use the semantic part of types).
994 const bitset representation =
995 type1->Representation() | type2->Representation();
996
997 // Slow case: create union.
998 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
999 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
1000 if (!AddIsSafe(size1, size2)) return Any(region);
1001 int size = size1 + size2;
1002 if (!AddIsSafe(size, 2)) return Any(region);
1003 size += 2;
1004 UnionHandle result = UnionType::New(size, region);
1005 size = 0;
1006
1007 // Compute the new bitset.
1008 bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
1009
1010 // Deal with ranges.
1011 TypeHandle range = None(region);
1012 RangeType* range1 = type1->GetRange();
1013 RangeType* range2 = type2->GetRange();
1014 if (range1 != NULL && range2 != NULL) {
1015 Limits lims = Limits::Union(Limits(range1), Limits(range2));
1016 RangeHandle union_range = RangeType::New(lims, representation, region);
1017 range = NormalizeRangeAndBitset(union_range, &new_bitset, region);
1018 } else if (range1 != NULL) {
1019 range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region);
1020 } else if (range2 != NULL) {
1021 range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region);
1022 }
1023 new_bitset = SEMANTIC(new_bitset) | representation;
1024 TypeHandle bits = BitsetType::New(new_bitset, region);
1025 result->Set(size++, bits);
1026 if (!range->IsNone()) result->Set(size++, range);
1027
1028 size = AddToUnion(type1, result, size, region);
1029 size = AddToUnion(type2, result, size, region);
1030 return NormalizeUnion(result, size, region);
1031 }
1032
1033
1034 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
1035 // Return new size of [result].
1036 template<class Config>
AddToUnion(TypeHandle type,UnionHandle result,int size,Region * region)1037 int TypeImpl<Config>::AddToUnion(
1038 TypeHandle type, UnionHandle result, int size, Region* region) {
1039 if (type->IsBitset() || type->IsRange()) return size;
1040 if (type->IsUnion()) {
1041 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
1042 size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
1043 }
1044 return size;
1045 }
1046 for (int i = 0; i < size; ++i) {
1047 if (type->SemanticIs(result->Get(i)->unhandle())) return size;
1048 }
1049 result->Set(size++, type);
1050 return size;
1051 }
1052
1053
1054 template <class Config>
NormalizeUnion(UnionHandle unioned,int size,Region * region)1055 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
1056 UnionHandle unioned, int size, Region* region) {
1057 DCHECK(size >= 1);
1058 DCHECK(unioned->Get(0)->IsBitset());
1059 // If the union has just one element, return it.
1060 if (size == 1) {
1061 return unioned->Get(0);
1062 }
1063 bitset bits = unioned->Get(0)->AsBitset();
1064 // If the union only consists of a range, we can get rid of the union.
1065 if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) {
1066 bitset representation = REPRESENTATION(bits);
1067 if (representation == unioned->Get(1)->Representation()) {
1068 return unioned->Get(1);
1069 }
1070 if (unioned->Get(1)->IsRange()) {
1071 return RangeType::New(unioned->Get(1)->AsRange()->Min(),
1072 unioned->Get(1)->AsRange()->Max(), unioned->Get(0),
1073 region);
1074 }
1075 }
1076 unioned->Shrink(size);
1077 SLOW_DCHECK(unioned->Wellformed());
1078 return unioned;
1079 }
1080
1081
1082 // -----------------------------------------------------------------------------
1083 // Component extraction
1084
1085 // static
1086 template <class Config>
Representation(TypeHandle t,Region * region)1087 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Representation(
1088 TypeHandle t, Region* region) {
1089 return BitsetType::New(t->Representation(), region);
1090 }
1091
1092
1093 // static
1094 template <class Config>
Semantic(TypeHandle t,Region * region)1095 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Semantic(
1096 TypeHandle t, Region* region) {
1097 return Intersect(t, BitsetType::New(BitsetType::kSemantic, region), region);
1098 }
1099
1100
1101 // -----------------------------------------------------------------------------
1102 // Iteration.
1103
1104 template<class Config>
NumClasses()1105 int TypeImpl<Config>::NumClasses() {
1106 DisallowHeapAllocation no_allocation;
1107 if (this->IsClass()) {
1108 return 1;
1109 } else if (this->IsUnion()) {
1110 int result = 0;
1111 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1112 if (this->AsUnion()->Get(i)->IsClass()) ++result;
1113 }
1114 return result;
1115 } else {
1116 return 0;
1117 }
1118 }
1119
1120
1121 template<class Config>
NumConstants()1122 int TypeImpl<Config>::NumConstants() {
1123 DisallowHeapAllocation no_allocation;
1124 if (this->IsConstant()) {
1125 return 1;
1126 } else if (this->IsUnion()) {
1127 int result = 0;
1128 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1129 if (this->AsUnion()->Get(i)->IsConstant()) ++result;
1130 }
1131 return result;
1132 } else {
1133 return 0;
1134 }
1135 }
1136
1137
1138 template<class Config> template<class T>
1139 typename TypeImpl<Config>::TypeHandle
get_type()1140 TypeImpl<Config>::Iterator<T>::get_type() {
1141 DCHECK(!Done());
1142 return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
1143 }
1144
1145
1146 // C++ cannot specialise nested templates, so we have to go through this
1147 // contortion with an auxiliary template to simulate it.
1148 template<class Config, class T>
1149 struct TypeImplIteratorAux {
1150 static bool matches(typename TypeImpl<Config>::TypeHandle type);
1151 static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
1152 };
1153
1154 template<class Config>
1155 struct TypeImplIteratorAux<Config, i::Map> {
matchesv8::internal::TypeImplIteratorAux1156 static bool matches(typename TypeImpl<Config>::TypeHandle type) {
1157 return type->IsClass();
1158 }
currentv8::internal::TypeImplIteratorAux1159 static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
1160 return type->AsClass()->Map();
1161 }
1162 };
1163
1164 template<class Config>
1165 struct TypeImplIteratorAux<Config, i::Object> {
matchesv8::internal::TypeImplIteratorAux1166 static bool matches(typename TypeImpl<Config>::TypeHandle type) {
1167 return type->IsConstant();
1168 }
currentv8::internal::TypeImplIteratorAux1169 static i::Handle<i::Object> current(
1170 typename TypeImpl<Config>::TypeHandle type) {
1171 return type->AsConstant()->Value();
1172 }
1173 };
1174
1175 template<class Config> template<class T>
matches(TypeHandle type)1176 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
1177 return TypeImplIteratorAux<Config, T>::matches(type);
1178 }
1179
1180 template<class Config> template<class T>
Current()1181 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
1182 return TypeImplIteratorAux<Config, T>::current(get_type());
1183 }
1184
1185
1186 template<class Config> template<class T>
Advance()1187 void TypeImpl<Config>::Iterator<T>::Advance() {
1188 DisallowHeapAllocation no_allocation;
1189 ++index_;
1190 if (type_->IsUnion()) {
1191 for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
1192 if (matches(type_->AsUnion()->Get(index_))) return;
1193 }
1194 } else if (index_ == 0 && matches(type_)) {
1195 return;
1196 }
1197 index_ = -1;
1198 }
1199
1200
1201 // -----------------------------------------------------------------------------
1202 // Conversion between low-level representations.
1203
1204 template<class Config>
1205 template<class OtherType>
Convert(typename OtherType::TypeHandle type,Region * region)1206 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
1207 typename OtherType::TypeHandle type, Region* region) {
1208 if (type->IsBitset()) {
1209 return BitsetType::New(type->AsBitset(), region);
1210 } else if (type->IsClass()) {
1211 return ClassType::New(type->AsClass()->Map(), region);
1212 } else if (type->IsConstant()) {
1213 return ConstantType::New(type->AsConstant()->Value(), region);
1214 } else if (type->IsRange()) {
1215 return RangeType::New(
1216 type->AsRange()->Min(), type->AsRange()->Max(),
1217 BitsetType::New(REPRESENTATION(type->BitsetLub()), region), region);
1218 } else if (type->IsContext()) {
1219 TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
1220 return ContextType::New(outer, region);
1221 } else if (type->IsUnion()) {
1222 int length = type->AsUnion()->Length();
1223 UnionHandle unioned = UnionType::New(length, region);
1224 for (int i = 0; i < length; ++i) {
1225 TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
1226 unioned->Set(i, t);
1227 }
1228 return unioned;
1229 } else if (type->IsArray()) {
1230 TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
1231 return ArrayType::New(element, region);
1232 } else if (type->IsFunction()) {
1233 TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
1234 TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
1235 FunctionHandle function = FunctionType::New(
1236 res, rcv, type->AsFunction()->Arity(), region);
1237 for (int i = 0; i < function->Arity(); ++i) {
1238 TypeHandle param = Convert<OtherType>(
1239 type->AsFunction()->Parameter(i), region);
1240 function->InitParameter(i, param);
1241 }
1242 return function;
1243 } else {
1244 UNREACHABLE();
1245 return None(region);
1246 }
1247 }
1248
1249
1250 // -----------------------------------------------------------------------------
1251 // Printing.
1252
1253 template<class Config>
Name(bitset bits)1254 const char* TypeImpl<Config>::BitsetType::Name(bitset bits) {
1255 switch (bits) {
1256 case REPRESENTATION(kAny): return "Any";
1257 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
1258 case REPRESENTATION(k##type): return #type;
1259 REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
1260 #undef RETURN_NAMED_REPRESENTATION_TYPE
1261
1262 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
1263 case SEMANTIC(k##type): return #type;
1264 SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1265 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1266 #undef RETURN_NAMED_SEMANTIC_TYPE
1267
1268 default:
1269 return NULL;
1270 }
1271 }
1272
1273
1274 template <class Config>
Print(std::ostream & os,bitset bits)1275 void TypeImpl<Config>::BitsetType::Print(std::ostream& os, // NOLINT
1276 bitset bits) {
1277 DisallowHeapAllocation no_allocation;
1278 const char* name = Name(bits);
1279 if (name != NULL) {
1280 os << name;
1281 return;
1282 }
1283
1284 // clang-format off
1285 static const bitset named_bitsets[] = {
1286 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
1287 REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
1288 #undef BITSET_CONSTANT
1289
1290 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
1291 INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
1292 SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
1293 #undef BITSET_CONSTANT
1294 };
1295 // clang-format on
1296
1297 bool is_first = true;
1298 os << "(";
1299 for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1300 bitset subset = named_bitsets[i];
1301 if ((bits & subset) == subset) {
1302 if (!is_first) os << " | ";
1303 is_first = false;
1304 os << Name(subset);
1305 bits -= subset;
1306 }
1307 }
1308 DCHECK(bits == 0);
1309 os << ")";
1310 }
1311
1312
1313 template <class Config>
PrintTo(std::ostream & os,PrintDimension dim)1314 void TypeImpl<Config>::PrintTo(std::ostream& os, PrintDimension dim) {
1315 DisallowHeapAllocation no_allocation;
1316 if (dim != REPRESENTATION_DIM) {
1317 if (this->IsBitset()) {
1318 BitsetType::Print(os, SEMANTIC(this->AsBitset()));
1319 } else if (this->IsClass()) {
1320 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1321 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
1322 os << ")";
1323 } else if (this->IsConstant()) {
1324 os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
1325 } else if (this->IsRange()) {
1326 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1327 std::streamsize saved_precision = os.precision(0);
1328 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1329 << ")";
1330 os.flags(saved_flags);
1331 os.precision(saved_precision);
1332 } else if (this->IsContext()) {
1333 os << "Context(";
1334 this->AsContext()->Outer()->PrintTo(os, dim);
1335 os << ")";
1336 } else if (this->IsUnion()) {
1337 os << "(";
1338 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1339 TypeHandle type_i = this->AsUnion()->Get(i);
1340 if (i > 0) os << " | ";
1341 type_i->PrintTo(os, dim);
1342 }
1343 os << ")";
1344 } else if (this->IsArray()) {
1345 os << "Array(";
1346 AsArray()->Element()->PrintTo(os, dim);
1347 os << ")";
1348 } else if (this->IsFunction()) {
1349 if (!this->AsFunction()->Receiver()->IsAny()) {
1350 this->AsFunction()->Receiver()->PrintTo(os, dim);
1351 os << ".";
1352 }
1353 os << "(";
1354 for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1355 if (i > 0) os << ", ";
1356 this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1357 }
1358 os << ")->";
1359 this->AsFunction()->Result()->PrintTo(os, dim);
1360 } else {
1361 UNREACHABLE();
1362 }
1363 }
1364 if (dim == BOTH_DIMS) os << "/";
1365 if (dim != SEMANTIC_DIM) {
1366 BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
1367 }
1368 }
1369
1370
1371 #ifdef DEBUG
1372 template <class Config>
Print()1373 void TypeImpl<Config>::Print() {
1374 OFStream os(stdout);
1375 PrintTo(os);
1376 os << std::endl;
1377 }
1378 template <class Config>
Print(bitset bits)1379 void TypeImpl<Config>::BitsetType::Print(bitset bits) {
1380 OFStream os(stdout);
1381 Print(os, bits);
1382 os << std::endl;
1383 }
1384 #endif
1385
1386
1387 // -----------------------------------------------------------------------------
1388 // Instantiations.
1389
1390 template class TypeImpl<ZoneTypeConfig>;
1391 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
1392 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
1393
1394 template class TypeImpl<HeapTypeConfig>;
1395 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
1396 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
1397
1398 template TypeImpl<ZoneTypeConfig>::TypeHandle
1399 TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
1400 TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
1401 template TypeImpl<HeapTypeConfig>::TypeHandle
1402 TypeImpl<HeapTypeConfig>::Convert<Type>(
1403 TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
1404
1405 } // namespace internal
1406 } // namespace v8
1407