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