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.
9 #include "src/ostreams.h"
10 #include "src/types-inl.h"
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.
20 // -----------------------------------------------------------------------------
21 // Range-related helper functions.
23 // The result may be invalid (max < min).
24 template<class Config>
25 typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect(
26 Limits lhs, Limits rhs) {
27 DisallowHeapAllocation no_allocation;
29 if (lhs.min < rhs.min) result.min = rhs.min;
30 if (lhs.max > rhs.max) result.max = rhs.max;
35 template <class Config>
36 bool TypeImpl<Config>::IsEmpty(Limits lim) {
37 return lim.min > lim.max;
41 template <class Config>
42 typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(Limits lhs,
44 DisallowHeapAllocation no_allocation;
45 if (IsEmpty(lhs)) return rhs;
46 if (IsEmpty(rhs)) return lhs;
48 if (lhs.min > rhs.min) result.min = rhs.min;
49 if (lhs.max < rhs.max) result.max = rhs.max;
54 template<class Config>
55 bool TypeImpl<Config>::Overlap(
56 typename TypeImpl<Config>::RangeType* lhs,
57 typename TypeImpl<Config>::RangeType* rhs) {
58 DisallowHeapAllocation no_allocation;
59 typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs));
60 return lim.min <= lim.max;
64 template<class Config>
65 bool TypeImpl<Config>::Contains(
66 typename TypeImpl<Config>::RangeType* lhs,
67 typename TypeImpl<Config>::RangeType* rhs) {
68 DisallowHeapAllocation no_allocation;
69 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
73 template <class Config>
74 bool TypeImpl<Config>::Contains(typename TypeImpl<Config>::RangeType* lhs,
75 typename TypeImpl<Config>::ConstantType* rhs) {
76 DisallowHeapAllocation no_allocation;
77 return IsInteger(*rhs->Value()) &&
78 lhs->Min() <= rhs->Value()->Number() &&
79 rhs->Value()->Number() <= lhs->Max();
83 template<class Config>
84 bool TypeImpl<Config>::Contains(
85 typename TypeImpl<Config>::RangeType* range, i::Object* val) {
86 DisallowHeapAllocation no_allocation;
87 return IsInteger(val) &&
88 range->Min() <= val->Number() && val->Number() <= range->Max();
92 // -----------------------------------------------------------------------------
93 // Min and Max computation.
95 template<class Config>
96 double TypeImpl<Config>::Min() {
97 DCHECK(this->SemanticIs(Number()));
98 if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
99 if (this->IsUnion()) {
100 double min = +V8_INFINITY;
101 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
102 min = std::min(min, this->AsUnion()->Get(i)->Min());
106 if (this->IsRange()) return this->AsRange()->Min();
107 if (this->IsConstant()) return this->AsConstant()->Value()->Number();
113 template<class Config>
114 double TypeImpl<Config>::Max() {
115 DCHECK(this->SemanticIs(Number()));
116 if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
117 if (this->IsUnion()) {
118 double max = -V8_INFINITY;
119 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
120 max = std::max(max, this->AsUnion()->Get(i)->Max());
124 if (this->IsRange()) return this->AsRange()->Max();
125 if (this->IsConstant()) return this->AsConstant()->Value()->Number();
131 // -----------------------------------------------------------------------------
132 // Glb and lub computation.
135 // The largest bitset subsumed by this type.
136 template<class Config>
137 typename TypeImpl<Config>::bitset
138 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
139 DisallowHeapAllocation no_allocation;
141 if (type->IsBitset()) {
142 return type->AsBitset();
143 } else if (type->IsUnion()) {
144 SLOW_DCHECK(type->AsUnion()->Wellformed());
145 return type->AsUnion()->Get(0)->BitsetGlb() |
146 SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb()); // Shortcut.
147 } else if (type->IsRange()) {
148 bitset glb = SEMANTIC(
149 BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
150 return glb | REPRESENTATION(type->BitsetLub());
152 return type->Representation();
157 // The smallest bitset subsuming this type.
158 template<class Config>
159 typename TypeImpl<Config>::bitset
160 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
161 DisallowHeapAllocation no_allocation;
162 if (type->IsBitset()) return type->AsBitset();
163 if (type->IsUnion()) {
164 // Take the representation from the first element, which is always
166 int bitset = type->AsUnion()->Get(0)->BitsetLub();
167 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
168 // Other elements only contribute their semantic part.
169 bitset |= SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
173 if (type->IsClass()) {
174 // Little hack to avoid the need for a region for handlification here...
175 return Config::is_class(type) ? Lub(*Config::as_class(type)) :
176 type->AsClass()->Bound(NULL)->AsBitset();
178 if (type->IsConstant()) return type->AsConstant()->Bound()->AsBitset();
179 if (type->IsRange()) return type->AsRange()->Bound();
180 if (type->IsContext()) return kInternal & kTaggedPointer;
181 if (type->IsArray()) return kArray;
182 if (type->IsFunction()) return kOtherObject; // TODO(rossberg): kFunction
188 template<class Config>
189 typename TypeImpl<Config>::bitset
190 TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
191 DisallowHeapAllocation no_allocation;
192 switch (map->instance_type()) {
194 case ONE_BYTE_STRING_TYPE:
195 case CONS_STRING_TYPE:
196 case CONS_ONE_BYTE_STRING_TYPE:
197 case SLICED_STRING_TYPE:
198 case SLICED_ONE_BYTE_STRING_TYPE:
199 case EXTERNAL_STRING_TYPE:
200 case EXTERNAL_ONE_BYTE_STRING_TYPE:
201 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
202 case SHORT_EXTERNAL_STRING_TYPE:
203 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
204 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
206 case INTERNALIZED_STRING_TYPE:
207 case ONE_BYTE_INTERNALIZED_STRING_TYPE:
208 case EXTERNAL_INTERNALIZED_STRING_TYPE:
209 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
210 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
211 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
212 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
213 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
214 return kInternalizedString;
218 Heap* heap = map->GetHeap();
219 if (map == heap->undefined_map()) return kUndefined;
220 if (map == heap->null_map()) return kNull;
221 if (map == heap->boolean_map()) return kBoolean;
222 DCHECK(map == heap->the_hole_map() ||
223 map == heap->uninitialized_map() ||
224 map == heap->no_interceptor_result_sentinel_map() ||
225 map == heap->termination_exception_map() ||
226 map == heap->arguments_marker_map());
227 return kInternal & kTaggedPointer;
229 case HEAP_NUMBER_TYPE:
230 return kNumber & kTaggedPointer;
234 case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
235 case JS_GENERATOR_OBJECT_TYPE:
237 case JS_GLOBAL_OBJECT_TYPE:
238 case JS_BUILTINS_OBJECT_TYPE:
239 case JS_GLOBAL_PROXY_TYPE:
240 case JS_ARRAY_BUFFER_TYPE:
241 case JS_TYPED_ARRAY_TYPE:
242 case JS_DATA_VIEW_TYPE:
245 case JS_SET_ITERATOR_TYPE:
246 case JS_MAP_ITERATOR_TYPE:
247 case JS_WEAK_MAP_TYPE:
248 case JS_WEAK_SET_TYPE:
249 if (map->is_undetectable()) return kUndetectable;
253 case JS_FUNCTION_TYPE:
254 return kOtherObject; // TODO(rossberg): there should be a Function type.
256 return kOtherObject; // TODO(rossberg): there should be a RegExp type.
258 case JS_FUNCTION_PROXY_TYPE:
261 // When compiling stub templates, the meta map is used as a place holder
262 // for the actual map with which the template is later instantiated.
263 // We treat it as a kind of type variable whose upper bound is Any.
264 // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
265 // we must exclude Undetectable here. This makes no sense, really,
266 // because it means that the template isn't actually parametric.
267 // Also, it doesn't apply elsewhere. 8-(
268 // We ought to find a cleaner solution for compiling stubs parameterised
269 // over type or class variables, esp ones with bounds...
271 case DECLARED_ACCESSOR_INFO_TYPE:
272 case EXECUTABLE_ACCESSOR_INFO_TYPE:
273 case SHARED_FUNCTION_INFO_TYPE:
274 case ACCESSOR_PAIR_TYPE:
275 case FIXED_ARRAY_TYPE:
276 case BYTE_ARRAY_TYPE:
280 return kInternal & kTaggedPointer;
288 template<class Config>
289 typename TypeImpl<Config>::bitset
290 TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
291 DisallowHeapAllocation no_allocation;
292 if (value->IsNumber()) {
293 return Lub(value->Number()) &
294 (value->IsSmi() ? kTaggedSigned : kTaggedPointer);
296 return Lub(i::HeapObject::cast(value)->map());
300 template<class Config>
301 typename TypeImpl<Config>::bitset
302 TypeImpl<Config>::BitsetType::Lub(double value) {
303 DisallowHeapAllocation no_allocation;
304 if (i::IsMinusZero(value)) return kMinusZero;
305 if (std::isnan(value)) return kNaN;
306 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
311 // Minimum values of regular numeric bitsets.
312 template <class Config>
313 const typename TypeImpl<Config>::BitsetType::Boundary
314 TypeImpl<Config>::BitsetType::BoundariesArray[] = {
315 {kPlainNumber, -V8_INFINITY},
316 {kNegative32, kMinInt},
317 {kNegative31, -0x40000000},
319 {kUnsigned31, 0x40000000},
320 {kUnsigned32, 0x80000000},
321 {kPlainNumber, static_cast<double>(kMaxUInt32) + 1}
325 template <class Config>
326 const typename TypeImpl<Config>::BitsetType::Boundary*
327 TypeImpl<Config>::BitsetType::Boundaries() {
328 return BoundariesArray;
332 template <class Config>
333 size_t TypeImpl<Config>::BitsetType::BoundariesSize() {
334 // Windows doesn't like arraysize here.
335 // return arraysize(BoundariesArray);
340 template<class Config>
341 typename TypeImpl<Config>::bitset
342 TypeImpl<Config>::BitsetType::Lub(double min, double max) {
343 DisallowHeapAllocation no_allocation;
345 const Boundary* mins = Boundaries();
347 // Make sure the min-max range touches 0, so we are guaranteed no holes
348 // in unions of valid bitsets.
349 if (max < -1) max = -1;
350 if (min > 0) min = 0;
352 for (size_t i = 1; i < BoundariesSize(); ++i) {
353 if (min < mins[i].min) {
354 lub |= mins[i-1].bits;
355 if (max < mins[i].min) return lub;
358 return lub |= mins[BoundariesSize() - 1].bits;
362 template <class Config>
363 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::NumberBits(
365 return SEMANTIC(bits & kPlainNumber);
369 template <class Config>
370 void TypeImpl<Config>::BitsetType::CheckNumberBits(bitset bits) {
371 // Check that the bitset does not contain any holes in number ranges.
372 bitset number_bits = NumberBits(bits);
373 if (number_bits != 0) {
374 bitset lub = SEMANTIC(Lub(Min(number_bits), Max(number_bits)));
375 CHECK(lub == number_bits);
379 template <class Config>
380 typename TypeImpl<Config>::bitset TypeImpl<Config>::BitsetType::Glb(
381 double min, double max) {
382 DisallowHeapAllocation no_allocation;
384 const Boundary* mins = Boundaries();
386 // If the range does not touch 0, the bound is empty.
387 if (max < -1 || min > 0) return glb;
389 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
390 if (min <= mins[i].min) {
391 if (max + 1 < mins[i + 1].min) break;
395 // OtherNumber also contains float numbers, so it can never be
396 // in the greatest lower bound. (There is also the small trouble
397 // of kOtherNumber having a range hole, which we can conveniently
399 return glb & ~(SEMANTIC(kOtherNumber));
403 template <class Config>
404 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
405 DisallowHeapAllocation no_allocation;
406 DCHECK(Is(SEMANTIC(bits), kNumber));
407 const Boundary* mins = Boundaries();
408 bool mz = SEMANTIC(bits & kMinusZero);
409 for (size_t i = 0; i < BoundariesSize(); ++i) {
410 if (Is(SEMANTIC(mins[i].bits), bits)) {
411 return mz ? std::min(0.0, mins[i].min) : mins[i].min;
415 return std::numeric_limits<double>::quiet_NaN();
419 template<class Config>
420 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
421 DisallowHeapAllocation no_allocation;
422 DCHECK(Is(SEMANTIC(bits), kNumber));
423 const Boundary* mins = Boundaries();
424 bool mz = SEMANTIC(bits & kMinusZero);
425 if (BitsetType::Is(SEMANTIC(mins[BoundariesSize() - 1].bits), bits)) {
428 for (size_t i = BoundariesSize() - 1; i-- > 0;) {
429 if (Is(SEMANTIC(mins[i].bits), bits)) {
431 std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
435 return std::numeric_limits<double>::quiet_NaN();
439 // -----------------------------------------------------------------------------
443 template<class Config>
444 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) {
445 DisallowHeapAllocation no_allocation;
446 if (this->IsClass()) {
447 return that->IsClass()
448 && *this->AsClass()->Map() == *that->AsClass()->Map();
450 if (this->IsConstant()) {
451 return that->IsConstant()
452 && *this->AsConstant()->Value() == *that->AsConstant()->Value();
454 if (this->IsContext()) {
455 return that->IsContext()
456 && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
458 if (this->IsArray()) {
459 return that->IsArray()
460 && this->AsArray()->Element()->Equals(that->AsArray()->Element());
462 if (this->IsFunction()) {
463 if (!that->IsFunction()) return false;
464 FunctionType* this_fun = this->AsFunction();
465 FunctionType* that_fun = that->AsFunction();
466 if (this_fun->Arity() != that_fun->Arity() ||
467 !this_fun->Result()->Equals(that_fun->Result()) ||
468 !this_fun->Receiver()->Equals(that_fun->Receiver())) {
471 for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
472 if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
481 template <class Config>
482 typename TypeImpl<Config>::bitset TypeImpl<Config>::Representation() {
483 return REPRESENTATION(this->BitsetLub());
487 // Check if [this] <= [that].
488 template<class Config>
489 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
490 DisallowHeapAllocation no_allocation;
493 if (that->IsBitset()) {
494 return BitsetType::Is(this->BitsetLub(), that->AsBitset());
497 if (this->IsBitset()) {
498 return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
501 // Check the representations.
502 if (!BitsetType::Is(Representation(), that->Representation())) {
506 // Check the semantic part.
507 return SemanticIs(that);
511 // Check if SEMANTIC([this]) <= SEMANTIC([that]). The result of the method
512 // should be independent of the representation axis of the types.
513 template <class Config>
514 bool TypeImpl<Config>::SemanticIs(TypeImpl* that) {
515 DisallowHeapAllocation no_allocation;
517 if (this == that) return true;
519 if (that->IsBitset()) {
520 return BitsetType::Is(SEMANTIC(this->BitsetLub()), that->AsBitset());
522 if (this->IsBitset()) {
523 return BitsetType::Is(SEMANTIC(this->AsBitset()), that->BitsetGlb());
526 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T)
527 if (this->IsUnion()) {
528 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
529 if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
534 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn)
535 if (that->IsUnion()) {
536 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
537 if (this->SemanticIs(that->AsUnion()->Get(i)->unhandle())) return true;
538 if (i > 1 && this->IsRange()) return false; // Shortcut.
543 if (that->IsRange()) {
544 return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
545 (this->IsConstant() &&
546 Contains(that->AsRange(), this->AsConstant()));
548 if (this->IsRange()) return false;
550 return this->SimplyEquals(that);
554 template<class Config>
555 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
556 DisallowHeapAllocation no_allocation;
558 // TODO(rossberg): this is incorrect for
559 // Union(Constant(V), T)->NowIs(Class(M))
560 // but fuzzing does not cover that!
561 if (this->IsConstant()) {
562 i::Object* object = *this->AsConstant()->Value();
563 if (object->IsHeapObject()) {
564 i::Map* map = i::HeapObject::cast(object)->map();
565 for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
566 if (*it.Current() == map) return true;
570 return this->Is(that);
574 // Check if [this] contains only (currently) stable classes.
575 template<class Config>
576 bool TypeImpl<Config>::NowStable() {
577 DisallowHeapAllocation no_allocation;
578 return !this->IsClass() || this->AsClass()->Map()->is_stable();
582 // Check if [this] and [that] overlap.
583 template<class Config>
584 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
585 DisallowHeapAllocation no_allocation;
587 // Take care of the representation part (and also approximate
588 // the semantic part).
589 if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
592 return SemanticMaybe(that);
595 template <class Config>
596 bool TypeImpl<Config>::SemanticMaybe(TypeImpl* that) {
597 DisallowHeapAllocation no_allocation;
599 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T)
600 if (this->IsUnion()) {
601 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
602 if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
607 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn)
608 if (that->IsUnion()) {
609 for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
610 if (this->SemanticMaybe(that->AsUnion()->Get(i)->unhandle())) return true;
615 if (!BitsetType::SemanticIsInhabited(this->BitsetLub() & that->BitsetLub()))
618 if (this->IsBitset() && that->IsBitset()) return true;
620 if (this->IsClass() != that->IsClass()) return true;
622 if (this->IsRange()) {
623 if (that->IsConstant()) {
624 return Contains(this->AsRange(), that->AsConstant());
626 if (that->IsRange()) {
627 return Overlap(this->AsRange(), that->AsRange());
629 if (that->IsBitset()) {
630 bitset number_bits = BitsetType::NumberBits(that->AsBitset());
631 if (number_bits == BitsetType::kNone) {
634 double min = std::max(BitsetType::Min(number_bits), this->Min());
635 double max = std::min(BitsetType::Max(number_bits), this->Max());
639 if (that->IsRange()) {
640 return that->SemanticMaybe(this); // This case is handled above.
643 if (this->IsBitset() || that->IsBitset()) return true;
645 return this->SimplyEquals(that);
649 // Return the range in [this], or [NULL].
650 template<class Config>
651 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
652 DisallowHeapAllocation no_allocation;
653 if (this->IsRange()) return this->AsRange();
654 if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
655 return this->AsUnion()->Get(1)->AsRange();
661 template<class Config>
662 bool TypeImpl<Config>::Contains(i::Object* value) {
663 DisallowHeapAllocation no_allocation;
664 for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
665 if (*it.Current() == value) return true;
667 if (IsInteger(value)) {
668 RangeType* range = this->GetRange();
669 if (range != NULL && Contains(range, value)) return true;
671 return BitsetType::New(BitsetType::Lub(value))->Is(this);
675 template<class Config>
676 bool TypeImpl<Config>::UnionType::Wellformed() {
677 DisallowHeapAllocation no_allocation;
678 // This checks the invariants of the union representation:
679 // 1. There are at least two elements.
680 // 2. The first element is a bitset, no other element is a bitset.
681 // 3. At most one element is a range, and it must be the second one.
682 // 4. No element is itself a union.
683 // 5. No element (except the bitset) is a subtype of any other.
684 // 6. If there is a range, then the bitset type does not contain
685 // plain number bits.
686 DCHECK(this->Length() >= 2); // (1)
687 DCHECK(this->Get(0)->IsBitset()); // (2a)
689 for (int i = 0; i < this->Length(); ++i) {
690 if (i != 0) DCHECK(!this->Get(i)->IsBitset()); // (2b)
691 if (i != 1) DCHECK(!this->Get(i)->IsRange()); // (3)
692 DCHECK(!this->Get(i)->IsUnion()); // (4)
693 for (int j = 0; j < this->Length(); ++j) {
694 if (i != j && i != 0)
695 DCHECK(!this->Get(i)->SemanticIs(this->Get(j)->unhandle())); // (5)
698 DCHECK(!this->Get(1)->IsRange() ||
699 (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
700 BitsetType::kNone)); // (6)
705 // -----------------------------------------------------------------------------
706 // Union and intersection
709 static bool AddIsSafe(int x, int y) {
711 y <= std::numeric_limits<int>::max() - x :
712 y >= std::numeric_limits<int>::min() - x;
716 template<class Config>
717 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
718 TypeHandle type1, TypeHandle type2, Region* region) {
720 // Fast case: bit sets.
721 if (type1->IsBitset() && type2->IsBitset()) {
722 return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
725 // Fast case: top or bottom types.
726 if (type1->IsNone() || type2->IsAny()) return type1; // Shortcut.
727 if (type2->IsNone() || type1->IsAny()) return type2; // Shortcut.
730 if (type1->Is(type2)) return type1;
731 if (type2->Is(type1)) return type2;
733 // Slow case: create union.
735 // Figure out the representation of the result first.
736 // The rest of the method should not change this representation and
737 // it should not make any decisions based on representations (i.e.,
738 // it should only use the semantic part of types).
739 const bitset representation =
740 type1->Representation() & type2->Representation();
742 // Semantic subtyping check - this is needed for consistency with the
743 // semi-fast case above - we should behave the same way regardless of
744 // representations. Intersection with a universal bitset should only update
745 // the representations.
746 if (type1->SemanticIs(type2->unhandle())) {
748 } else if (type2->SemanticIs(type1->unhandle())) {
753 SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
754 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
755 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
756 if (!AddIsSafe(size1, size2)) return Any(region);
757 int size = size1 + size2;
758 if (!AddIsSafe(size, 2)) return Any(region);
760 UnionHandle result = UnionType::New(size, region);
763 // Deal with bitsets.
764 result->Set(size++, BitsetType::New(bits, region));
766 Limits lims = Limits::Empty(region);
767 size = IntersectAux(type1, type2, result, size, &lims, region);
769 // If the range is not empty, then insert it into the union and
770 // remove the number bits from the bitset.
771 if (!IsEmpty(lims)) {
772 size = UpdateRange(RangeType::New(lims, representation, region), result,
775 // Remove the number bits.
776 bitset number_bits = BitsetType::NumberBits(bits);
777 bits &= ~number_bits;
778 result->Set(0, BitsetType::New(bits, region));
780 return NormalizeUnion(result, size);
784 template<class Config>
785 int TypeImpl<Config>::UpdateRange(
786 RangeHandle range, UnionHandle result, int size, Region* region) {
788 result->Set(size++, range);
790 // Make space for the range.
791 result->Set(size++, result->Get(1));
792 result->Set(1, range);
795 // Remove any components that just got subsumed.
796 for (int i = 2; i < size; ) {
797 if (result->Get(i)->SemanticIs(range->unhandle())) {
798 result->Set(i, result->Get(--size));
807 template <class Config>
808 typename TypeImpl<Config>::Limits TypeImpl<Config>::ToLimits(bitset bits,
810 bitset number_bits = BitsetType::NumberBits(bits);
812 if (number_bits == BitsetType::kNone) {
813 return Limits::Empty(region);
816 return Limits(BitsetType::Min(number_bits), BitsetType::Max(number_bits));
820 template <class Config>
821 typename TypeImpl<Config>::Limits TypeImpl<Config>::IntersectRangeAndBitset(
822 TypeHandle range, TypeHandle bitset, Region* region) {
823 Limits range_lims(range->AsRange());
824 Limits bitset_lims = ToLimits(bitset->AsBitset(), region);
825 return Intersect(range_lims, bitset_lims);
829 template <class Config>
830 int TypeImpl<Config>::IntersectAux(TypeHandle lhs, TypeHandle rhs,
831 UnionHandle result, int size, Limits* lims,
833 if (lhs->IsUnion()) {
834 for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
836 IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, region);
840 if (rhs->IsUnion()) {
841 for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
843 IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, region);
848 if (!BitsetType::SemanticIsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
852 if (lhs->IsRange()) {
853 if (rhs->IsBitset()) {
854 Limits lim = IntersectRangeAndBitset(lhs, rhs, region);
857 *lims = Union(lim, *lims);
861 if (rhs->IsClass()) {
862 *lims = Union(Limits(lhs->AsRange()), *lims);
864 if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
865 return AddToUnion(rhs, result, size, region);
867 if (rhs->IsRange()) {
868 Limits lim = Intersect(Limits(lhs->AsRange()), Limits(rhs->AsRange()));
870 *lims = Union(lim, *lims);
875 if (rhs->IsRange()) {
876 // This case is handled symmetrically above.
877 return IntersectAux(rhs, lhs, result, size, lims, region);
879 if (lhs->IsBitset() || rhs->IsBitset()) {
880 return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
882 if (lhs->IsClass() != rhs->IsClass()) {
883 return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region);
885 if (lhs->SimplyEquals(rhs->unhandle())) {
886 return AddToUnion(lhs, result, size, region);
892 // Make sure that we produce a well-formed range and bitset:
893 // If the range is non-empty, the number bits in the bitset should be
894 // clear. Moreover, if we have a canonical range (such as Signed32(),
895 // we want to produce a bitset rather than a range.
896 template <class Config>
897 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeRangeAndBitset(
898 RangeHandle range, bitset* bits, Region* region) {
899 // Fast path: If the bitset does not mention numbers, we can just keep the
901 bitset number_bits = BitsetType::NumberBits(*bits);
902 if (number_bits == 0) {
906 // If the range is contained within the bitset, return an empty range
907 // (but make sure we take the representation).
908 bitset range_lub = SEMANTIC(range->BitsetLub());
909 if (BitsetType::Is(BitsetType::NumberBits(range_lub), *bits)) {
913 // Slow path: reconcile the bitset range and the range.
914 double bitset_min = BitsetType::Min(number_bits);
915 double bitset_max = BitsetType::Max(number_bits);
917 double range_min = range->Min();
918 double range_max = range->Max();
920 // Remove the number bits from the bitset, they would just confuse us now.
921 *bits &= ~number_bits;
923 if (range_min <= bitset_min && range_max >= bitset_max) {
924 // Bitset is contained within the range, just return the range.
928 if (bitset_min < range_min) {
929 range_min = bitset_min;
931 if (bitset_max > range_max) {
932 range_max = bitset_max;
934 return RangeType::New(range_min, range_max,
935 BitsetType::New(BitsetType::kNone, region), region);
939 template<class Config>
940 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
941 TypeHandle type1, TypeHandle type2, Region* region) {
942 // Fast case: bit sets.
943 if (type1->IsBitset() && type2->IsBitset()) {
944 return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
947 // Fast case: top or bottom types.
948 if (type1->IsAny() || type2->IsNone()) return type1;
949 if (type2->IsAny() || type1->IsNone()) return type2;
952 if (type1->Is(type2)) return type2;
953 if (type2->Is(type1)) return type1;
955 // Figure out the representation of the result.
956 // The rest of the method should not change this representation and
957 // it should make any decisions based on representations (i.e.,
958 // it should only use the semantic part of types).
959 const bitset representation =
960 type1->Representation() | type2->Representation();
962 // Slow case: create union.
963 int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
964 int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
965 if (!AddIsSafe(size1, size2)) return Any(region);
966 int size = size1 + size2;
967 if (!AddIsSafe(size, 2)) return Any(region);
969 UnionHandle result = UnionType::New(size, region);
972 // Compute the new bitset.
973 bitset new_bitset = SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
976 TypeHandle range = None(region);
977 RangeType* range1 = type1->GetRange();
978 RangeType* range2 = type2->GetRange();
979 if (range1 != NULL && range2 != NULL) {
980 Limits lims = Union(Limits(range1), Limits(range2));
981 RangeHandle union_range = RangeType::New(lims, representation, region);
982 range = NormalizeRangeAndBitset(union_range, &new_bitset, region);
983 } else if (range1 != NULL) {
984 range = NormalizeRangeAndBitset(handle(range1), &new_bitset, region);
985 } else if (range2 != NULL) {
986 range = NormalizeRangeAndBitset(handle(range2), &new_bitset, region);
988 new_bitset = SEMANTIC(new_bitset) | representation;
989 TypeHandle bits = BitsetType::New(new_bitset, region);
990 result->Set(size++, bits);
991 if (!range->IsNone()) result->Set(size++, range);
993 size = AddToUnion(type1, result, size, region);
994 size = AddToUnion(type2, result, size, region);
995 return NormalizeUnion(result, size);
999 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
1000 // Return new size of [result].
1001 template<class Config>
1002 int TypeImpl<Config>::AddToUnion(
1003 TypeHandle type, UnionHandle result, int size, Region* region) {
1004 if (type->IsBitset() || type->IsRange()) return size;
1005 if (type->IsUnion()) {
1006 for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
1007 size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
1011 for (int i = 0; i < size; ++i) {
1012 if (type->SemanticIs(result->Get(i)->unhandle())) return size;
1014 result->Set(size++, type);
1019 template<class Config>
1020 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
1021 UnionHandle unioned, int size) {
1023 DCHECK(unioned->Get(0)->IsBitset());
1024 // If the union has just one element, return it.
1026 return unioned->Get(0);
1028 bitset bits = unioned->Get(0)->AsBitset();
1029 // If the union only consists of a range, we can get rid of the union.
1030 if (size == 2 && SEMANTIC(bits) == BitsetType::kNone) {
1031 bitset representation = REPRESENTATION(bits);
1032 if (representation == unioned->Get(1)->Representation()) {
1033 return unioned->Get(1);
1035 // TODO(jarin) If the element at 1 is range of constant, slap
1036 // the representation on it and return that.
1038 unioned->Shrink(size);
1039 SLOW_DCHECK(unioned->Wellformed());
1044 // -----------------------------------------------------------------------------
1045 // Component extraction
1048 template <class Config>
1049 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Representation(
1050 TypeHandle t, Region* region) {
1051 return BitsetType::New(t->Representation(), region);
1056 template <class Config>
1057 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Semantic(
1058 TypeHandle t, Region* region) {
1059 return Intersect(t, BitsetType::New(BitsetType::kSemantic, region), region);
1063 // -----------------------------------------------------------------------------
1066 template<class Config>
1067 int TypeImpl<Config>::NumClasses() {
1068 DisallowHeapAllocation no_allocation;
1069 if (this->IsClass()) {
1071 } else if (this->IsUnion()) {
1073 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1074 if (this->AsUnion()->Get(i)->IsClass()) ++result;
1083 template<class Config>
1084 int TypeImpl<Config>::NumConstants() {
1085 DisallowHeapAllocation no_allocation;
1086 if (this->IsConstant()) {
1088 } else if (this->IsUnion()) {
1090 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1091 if (this->AsUnion()->Get(i)->IsConstant()) ++result;
1100 template<class Config> template<class T>
1101 typename TypeImpl<Config>::TypeHandle
1102 TypeImpl<Config>::Iterator<T>::get_type() {
1104 return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
1108 // C++ cannot specialise nested templates, so we have to go through this
1109 // contortion with an auxiliary template to simulate it.
1110 template<class Config, class T>
1111 struct TypeImplIteratorAux {
1112 static bool matches(typename TypeImpl<Config>::TypeHandle type);
1113 static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
1116 template<class Config>
1117 struct TypeImplIteratorAux<Config, i::Map> {
1118 static bool matches(typename TypeImpl<Config>::TypeHandle type) {
1119 return type->IsClass();
1121 static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
1122 return type->AsClass()->Map();
1126 template<class Config>
1127 struct TypeImplIteratorAux<Config, i::Object> {
1128 static bool matches(typename TypeImpl<Config>::TypeHandle type) {
1129 return type->IsConstant();
1131 static i::Handle<i::Object> current(
1132 typename TypeImpl<Config>::TypeHandle type) {
1133 return type->AsConstant()->Value();
1137 template<class Config> template<class T>
1138 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
1139 return TypeImplIteratorAux<Config, T>::matches(type);
1142 template<class Config> template<class T>
1143 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
1144 return TypeImplIteratorAux<Config, T>::current(get_type());
1148 template<class Config> template<class T>
1149 void TypeImpl<Config>::Iterator<T>::Advance() {
1150 DisallowHeapAllocation no_allocation;
1152 if (type_->IsUnion()) {
1153 for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
1154 if (matches(type_->AsUnion()->Get(index_))) return;
1156 } else if (index_ == 0 && matches(type_)) {
1163 // -----------------------------------------------------------------------------
1164 // Conversion between low-level representations.
1166 template<class Config>
1167 template<class OtherType>
1168 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
1169 typename OtherType::TypeHandle type, Region* region) {
1170 if (type->IsBitset()) {
1171 return BitsetType::New(type->AsBitset(), region);
1172 } else if (type->IsClass()) {
1173 return ClassType::New(type->AsClass()->Map(), region);
1174 } else if (type->IsConstant()) {
1175 return ConstantType::New(type->AsConstant()->Value(), region);
1176 } else if (type->IsRange()) {
1177 return RangeType::New(
1178 type->AsRange()->Min(), type->AsRange()->Max(),
1179 BitsetType::New(REPRESENTATION(type->BitsetLub()), region), region);
1180 } else if (type->IsContext()) {
1181 TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
1182 return ContextType::New(outer, region);
1183 } else if (type->IsUnion()) {
1184 int length = type->AsUnion()->Length();
1185 UnionHandle unioned = UnionType::New(length, region);
1186 for (int i = 0; i < length; ++i) {
1187 TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
1191 } else if (type->IsArray()) {
1192 TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
1193 return ArrayType::New(element, region);
1194 } else if (type->IsFunction()) {
1195 TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
1196 TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
1197 FunctionHandle function = FunctionType::New(
1198 res, rcv, type->AsFunction()->Arity(), region);
1199 for (int i = 0; i < function->Arity(); ++i) {
1200 TypeHandle param = Convert<OtherType>(
1201 type->AsFunction()->Parameter(i), region);
1202 function->InitParameter(i, param);
1207 return None(region);
1212 // -----------------------------------------------------------------------------
1215 template<class Config>
1216 const char* TypeImpl<Config>::BitsetType::Name(bitset bits) {
1218 case REPRESENTATION(kAny): return "Any";
1219 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
1220 case REPRESENTATION(k##type): return #type;
1221 REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
1222 #undef RETURN_NAMED_REPRESENTATION_TYPE
1224 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
1225 case SEMANTIC(k##type): return #type;
1226 SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1227 #undef RETURN_NAMED_SEMANTIC_TYPE
1235 template <class Config>
1236 void TypeImpl<Config>::BitsetType::Print(std::ostream& os, // NOLINT
1238 DisallowHeapAllocation no_allocation;
1239 const char* name = Name(bits);
1246 static const bitset named_bitsets[] = {
1247 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
1248 REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
1249 #undef BITSET_CONSTANT
1251 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
1252 INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
1253 SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
1254 #undef BITSET_CONSTANT
1258 bool is_first = true;
1260 for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1261 bitset subset = named_bitsets[i];
1262 if ((bits & subset) == subset) {
1263 if (!is_first) os << " | ";
1274 template <class Config>
1275 void TypeImpl<Config>::PrintTo(std::ostream& os, PrintDimension dim) {
1276 DisallowHeapAllocation no_allocation;
1277 if (dim != REPRESENTATION_DIM) {
1278 if (this->IsBitset()) {
1279 BitsetType::Print(os, SEMANTIC(this->AsBitset()));
1280 } else if (this->IsClass()) {
1281 os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1282 BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
1284 } else if (this->IsConstant()) {
1285 os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
1286 } else if (this->IsRange()) {
1287 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1288 std::streamsize saved_precision = os.precision(0);
1289 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1291 os.flags(saved_flags);
1292 os.precision(saved_precision);
1293 } else if (this->IsContext()) {
1295 this->AsContext()->Outer()->PrintTo(os, dim);
1297 } else if (this->IsUnion()) {
1299 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1300 TypeHandle type_i = this->AsUnion()->Get(i);
1301 if (i > 0) os << " | ";
1302 type_i->PrintTo(os, dim);
1305 } else if (this->IsArray()) {
1307 AsArray()->Element()->PrintTo(os, dim);
1309 } else if (this->IsFunction()) {
1310 if (!this->AsFunction()->Receiver()->IsAny()) {
1311 this->AsFunction()->Receiver()->PrintTo(os, dim);
1315 for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1316 if (i > 0) os << ", ";
1317 this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1320 this->AsFunction()->Result()->PrintTo(os, dim);
1325 if (dim == BOTH_DIMS) os << "/";
1326 if (dim != SEMANTIC_DIM) {
1327 BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
1333 template <class Config>
1334 void TypeImpl<Config>::Print() {
1335 OFStream os(stdout);
1339 template <class Config>
1340 void TypeImpl<Config>::BitsetType::Print(bitset bits) {
1341 OFStream os(stdout);
1348 // -----------------------------------------------------------------------------
1351 template class TypeImpl<ZoneTypeConfig>;
1352 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
1353 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
1355 template class TypeImpl<HeapTypeConfig>;
1356 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
1357 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
1359 template TypeImpl<ZoneTypeConfig>::TypeHandle
1360 TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
1361 TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
1362 template TypeImpl<HeapTypeConfig>::TypeHandle
1363 TypeImpl<HeapTypeConfig>::Convert<Type>(
1364 TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
1366 } } // namespace v8::internal