7 #include "src/compiler/types.h" 9 #include "src/handles-inl.h" 10 #include "src/objects-inl.h" 11 #include "src/ostreams.h" 20 bool RangeType::Limits::IsEmpty() {
return this->min > this->max; }
22 RangeType::Limits RangeType::Limits::Intersect(Limits lhs, Limits rhs) {
23 DisallowHeapAllocation no_allocation;
25 if (lhs.min < rhs.min) result.min = rhs.min;
26 if (lhs.max > rhs.max) result.max = rhs.max;
30 RangeType::Limits RangeType::Limits::Union(Limits lhs, Limits rhs) {
31 DisallowHeapAllocation no_allocation;
32 if (lhs.IsEmpty())
return rhs;
33 if (rhs.IsEmpty())
return lhs;
35 if (lhs.min > rhs.min) result.min = rhs.min;
36 if (lhs.max < rhs.max) result.max = rhs.max;
40 bool Type::Overlap(
const RangeType* lhs,
const RangeType* rhs) {
41 DisallowHeapAllocation no_allocation;
42 return !RangeType::Limits::Intersect(RangeType::Limits(lhs),
43 RangeType::Limits(rhs))
47 bool Type::Contains(
const RangeType* lhs,
const RangeType* rhs) {
48 DisallowHeapAllocation no_allocation;
49 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
55 double Type::Min()
const {
56 DCHECK(this->Is(Number()));
57 DCHECK(!this->Is(NaN()));
58 if (this->IsBitset())
return BitsetType::Min(this->AsBitset());
59 if (this->IsUnion()) {
60 double min = +V8_INFINITY;
61 for (
int i = 1, n = AsUnion()->Length();
i < n; ++
i) {
62 min = std::min(min, AsUnion()->Get(
i).Min());
64 Type bitset = AsUnion()->Get(0);
65 if (!bitset.Is(NaN())) min = std::min(min, bitset.Min());
68 if (this->IsRange())
return this->AsRange()->Min();
69 DCHECK(this->IsOtherNumberConstant());
70 return this->AsOtherNumberConstant()->Value();
73 double Type::Max()
const {
74 DCHECK(this->Is(Number()));
75 DCHECK(!this->Is(NaN()));
76 if (this->IsBitset())
return BitsetType::Max(this->AsBitset());
77 if (this->IsUnion()) {
78 double max = -V8_INFINITY;
79 for (
int i = 1, n = this->AsUnion()->Length();
i < n; ++
i) {
80 max = std::max(max, this->AsUnion()->Get(
i).Max());
82 Type bitset = this->AsUnion()->Get(0);
83 if (!bitset.Is(NaN())) max = std::max(max, bitset.Max());
86 if (this->IsRange())
return this->AsRange()->Max();
87 DCHECK(this->IsOtherNumberConstant());
88 return this->AsOtherNumberConstant()->Value();
95 Type::bitset Type::BitsetGlb()
const {
96 DisallowHeapAllocation no_allocation;
100 }
else if (IsUnion()) {
101 SLOW_DCHECK(AsUnion()->Wellformed());
102 return AsUnion()->Get(0).BitsetGlb() |
103 AsUnion()->Get(1).BitsetGlb();
104 }
else if (IsRange()) {
105 bitset glb = BitsetType::Glb(AsRange()->Min(), AsRange()->Max());
108 return BitsetType::kNone;
113 Type::bitset Type::BitsetLub()
const {
114 DisallowHeapAllocation no_allocation;
115 if (IsBitset())
return AsBitset();
119 int bitset = AsUnion()->Get(0).BitsetLub();
120 for (
int i = 0, n = AsUnion()->Length();
i < n; ++
i) {
122 bitset |= AsUnion()->Get(
i).BitsetLub();
126 if (IsHeapConstant())
return AsHeapConstant()->Lub();
127 if (IsOtherNumberConstant()) {
128 return AsOtherNumberConstant()->Lub();
130 if (IsRange())
return AsRange()->Lub();
131 if (IsTuple())
return BitsetType::kOtherInternal;
137 template <
typename MapRefLike>
138 Type::bitset BitsetType::Lub(
const MapRefLike& map) {
139 switch (map.instance_type()) {
140 case CONS_STRING_TYPE:
141 case CONS_ONE_BYTE_STRING_TYPE:
142 case THIN_STRING_TYPE:
143 case THIN_ONE_BYTE_STRING_TYPE:
144 case SLICED_STRING_TYPE:
145 case SLICED_ONE_BYTE_STRING_TYPE:
146 case EXTERNAL_STRING_TYPE:
147 case EXTERNAL_ONE_BYTE_STRING_TYPE:
148 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
149 case UNCACHED_EXTERNAL_STRING_TYPE:
150 case UNCACHED_EXTERNAL_ONE_BYTE_STRING_TYPE:
151 case UNCACHED_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
153 case ONE_BYTE_STRING_TYPE:
155 case EXTERNAL_INTERNALIZED_STRING_TYPE:
156 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
157 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
158 case UNCACHED_EXTERNAL_INTERNALIZED_STRING_TYPE:
159 case UNCACHED_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
160 case UNCACHED_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
161 case INTERNALIZED_STRING_TYPE:
162 case ONE_BYTE_INTERNALIZED_STRING_TYPE:
163 return kInternalizedString;
169 switch (map.oddball_type()) {
170 case OddballType::kNone:
172 case OddballType::kHole:
174 case OddballType::kBoolean:
176 case OddballType::kNull:
178 case OddballType::kUndefined:
180 case OddballType::kUninitialized:
181 case OddballType::kOther:
183 return kOtherInternal;
186 case HEAP_NUMBER_TYPE:
189 case JS_ARGUMENTS_TYPE:
191 case JS_GLOBAL_OBJECT_TYPE:
192 case JS_GLOBAL_PROXY_TYPE:
193 case JS_API_OBJECT_TYPE:
194 case JS_SPECIAL_API_OBJECT_TYPE:
195 if (map.is_undetectable()) {
200 DCHECK(map.is_callable());
201 return kOtherUndetectable;
203 if (map.is_callable()) {
204 return kOtherCallable;
210 case JS_MESSAGE_OBJECT_TYPE:
212 #ifdef V8_INTL_SUPPORT 213 case JS_INTL_V8_BREAK_ITERATOR_TYPE:
214 case JS_INTL_COLLATOR_TYPE:
215 case JS_INTL_DATE_TIME_FORMAT_TYPE:
216 case JS_INTL_LIST_FORMAT_TYPE:
217 case JS_INTL_LOCALE_TYPE:
218 case JS_INTL_NUMBER_FORMAT_TYPE:
219 case JS_INTL_PLURAL_RULES_TYPE:
220 case JS_INTL_RELATIVE_TIME_FORMAT_TYPE:
221 case JS_INTL_SEGMENT_ITERATOR_TYPE:
222 case JS_INTL_SEGMENTER_TYPE:
223 #endif // V8_INTL_SUPPORT 224 case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
225 case JS_GENERATOR_OBJECT_TYPE:
226 case JS_ASYNC_FUNCTION_OBJECT_TYPE:
227 case JS_ASYNC_GENERATOR_OBJECT_TYPE:
228 case JS_MODULE_NAMESPACE_TYPE:
229 case JS_ARRAY_BUFFER_TYPE:
230 case JS_ARRAY_ITERATOR_TYPE:
232 case JS_REGEXP_STRING_ITERATOR_TYPE:
233 case JS_TYPED_ARRAY_TYPE:
234 case JS_DATA_VIEW_TYPE:
237 case JS_SET_KEY_VALUE_ITERATOR_TYPE:
238 case JS_SET_VALUE_ITERATOR_TYPE:
239 case JS_MAP_KEY_ITERATOR_TYPE:
240 case JS_MAP_KEY_VALUE_ITERATOR_TYPE:
241 case JS_MAP_VALUE_ITERATOR_TYPE:
242 case JS_STRING_ITERATOR_TYPE:
243 case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE:
244 case JS_WEAK_CELL_TYPE:
245 case JS_WEAK_FACTORY_TYPE:
246 case JS_WEAK_FACTORY_CLEANUP_ITERATOR_TYPE:
247 case JS_WEAK_MAP_TYPE:
248 case JS_WEAK_REF_TYPE:
249 case JS_WEAK_SET_TYPE:
250 case JS_PROMISE_TYPE:
251 case WASM_EXCEPTION_TYPE:
252 case WASM_GLOBAL_TYPE:
253 case WASM_INSTANCE_TYPE:
254 case WASM_MEMORY_TYPE:
255 case WASM_MODULE_TYPE:
256 case WASM_TABLE_TYPE:
257 DCHECK(!map.is_callable());
258 DCHECK(!map.is_undetectable());
260 case JS_BOUND_FUNCTION_TYPE:
261 DCHECK(!map.is_undetectable());
262 return kBoundFunction;
263 case JS_FUNCTION_TYPE:
264 DCHECK(!map.is_undetectable());
267 DCHECK(!map.is_undetectable());
268 if (map.is_callable())
return kCallableProxy;
271 case ALLOCATION_SITE_TYPE:
272 case ACCESSOR_INFO_TYPE:
273 case SHARED_FUNCTION_INFO_TYPE:
274 case FUNCTION_TEMPLATE_INFO_TYPE:
275 case FUNCTION_TEMPLATE_RARE_DATA_TYPE:
276 case ACCESSOR_PAIR_TYPE:
277 case EMBEDDER_DATA_ARRAY_TYPE:
278 case FIXED_ARRAY_TYPE:
279 case HASH_TABLE_TYPE:
280 case ORDERED_HASH_MAP_TYPE:
281 case ORDERED_HASH_SET_TYPE:
282 case ORDERED_NAME_DICTIONARY_TYPE:
283 case NAME_DICTIONARY_TYPE:
284 case GLOBAL_DICTIONARY_TYPE:
285 case NUMBER_DICTIONARY_TYPE:
286 case SIMPLE_NUMBER_DICTIONARY_TYPE:
287 case STRING_TABLE_TYPE:
288 case EPHEMERON_HASH_TABLE_TYPE:
289 case WEAK_FIXED_ARRAY_TYPE:
290 case WEAK_ARRAY_LIST_TYPE:
291 case FIXED_DOUBLE_ARRAY_TYPE:
292 case FEEDBACK_METADATA_TYPE:
293 case BYTE_ARRAY_TYPE:
294 case BYTECODE_ARRAY_TYPE:
295 case OBJECT_BOILERPLATE_DESCRIPTION_TYPE:
296 case ARRAY_BOILERPLATE_DESCRIPTION_TYPE:
297 case DESCRIPTOR_ARRAY_TYPE:
298 case TRANSITION_ARRAY_TYPE:
299 case FEEDBACK_CELL_TYPE:
300 case FEEDBACK_VECTOR_TYPE:
301 case PROPERTY_ARRAY_TYPE:
303 case SCOPE_INFO_TYPE:
304 case SCRIPT_CONTEXT_TABLE_TYPE:
305 case AWAIT_CONTEXT_TYPE:
306 case BLOCK_CONTEXT_TYPE:
307 case CATCH_CONTEXT_TYPE:
308 case DEBUG_EVALUATE_CONTEXT_TYPE:
309 case EVAL_CONTEXT_TYPE:
310 case FUNCTION_CONTEXT_TYPE:
311 case MODULE_CONTEXT_TYPE:
312 case NATIVE_CONTEXT_TYPE:
313 case SCRIPT_CONTEXT_TYPE:
314 case WITH_CONTEXT_TYPE:
317 case PROPERTY_CELL_TYPE:
319 case MODULE_INFO_ENTRY_TYPE:
321 case PRE_PARSED_SCOPE_DATA_TYPE:
322 case UNCOMPILED_DATA_WITHOUT_PRE_PARSED_SCOPE_TYPE:
323 case UNCOMPILED_DATA_WITH_PRE_PARSED_SCOPE_TYPE:
324 return kOtherInternal;
328 case MUTABLE_HEAP_NUMBER_TYPE:
329 case FREE_SPACE_TYPE:
330 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype) \ 331 case FIXED_##TYPE##_ARRAY_TYPE: 333 TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
334 #undef FIXED_TYPED_ARRAY_CASE 336 case ACCESS_CHECK_INFO_TYPE:
337 case ASM_WASM_DATA_TYPE:
338 case CALL_HANDLER_INFO_TYPE:
339 case INTERCEPTOR_INFO_TYPE:
340 case OBJECT_TEMPLATE_INFO_TYPE:
341 case ALLOCATION_MEMENTO_TYPE:
342 case ALIASED_ARGUMENTS_ENTRY_TYPE:
343 case PROMISE_CAPABILITY_TYPE:
344 case PROMISE_REACTION_TYPE:
345 case DEBUG_INFO_TYPE:
346 case STACK_FRAME_INFO_TYPE:
347 case SMALL_ORDERED_HASH_MAP_TYPE:
348 case SMALL_ORDERED_HASH_SET_TYPE:
349 case SMALL_ORDERED_NAME_DICTIONARY_TYPE:
350 case PROTOTYPE_INFO_TYPE:
351 case INTERPRETER_DATA_TYPE:
354 case WASM_DEBUG_INFO_TYPE:
355 case WASM_EXPORTED_FUNCTION_DATA_TYPE:
356 case LOAD_HANDLER_TYPE:
357 case STORE_HANDLER_TYPE:
358 case ASYNC_GENERATOR_REQUEST_TYPE:
359 case CODE_DATA_CONTAINER_TYPE:
360 case CALLBACK_TASK_TYPE:
361 case CALLABLE_TASK_TYPE:
362 case PROMISE_FULFILL_REACTION_JOB_TASK_TYPE:
363 case PROMISE_REJECT_REACTION_JOB_TASK_TYPE:
364 case PROMISE_RESOLVE_THENABLE_JOB_TASK_TYPE:
365 case WEAK_FACTORY_CLEANUP_JOB_TASK_TYPE:
372 template Type::bitset BitsetType::Lub<MapRef>(
const MapRef& map);
374 Type::bitset BitsetType::Lub(
double value) {
375 DisallowHeapAllocation no_allocation;
376 if (IsMinusZero(value))
return kMinusZero;
377 if (std::isnan(value))
return kNaN;
378 if (IsUint32Double(value) || IsInt32Double(value))
return Lub(value, value);
383 const BitsetType::Boundary BitsetType::BoundariesArray[] = {
384 {kOtherNumber, kPlainNumber, -V8_INFINITY},
385 {kOtherSigned32, kNegative32, kMinInt},
386 {kNegative31, kNegative31, -0x40000000},
387 {kUnsigned30, kUnsigned30, 0},
388 {kOtherUnsigned31, kUnsigned31, 0x40000000},
389 {kOtherUnsigned32, kUnsigned32, 0x80000000},
390 {kOtherNumber, kPlainNumber,
static_cast<double>(kMaxUInt32) + 1}};
392 const BitsetType::Boundary* BitsetType::Boundaries() {
return BoundariesArray; }
394 size_t BitsetType::BoundariesSize() {
400 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) {
401 DCHECK_IMPLIES(bits & kOtherString, (bits & kString) == kString);
402 DisallowHeapAllocation no_allocation;
403 if (!(bits & kPlainNumber))
return bits;
404 const Boundary* boundaries = Boundaries();
405 for (
size_t i = 0;
i < BoundariesSize(); ++
i) {
406 DCHECK(BitsetType::Is(boundaries[
i].
internal, boundaries[
i].external));
407 if (bits & boundaries[
i].
internal) bits |= boundaries[
i].external;
412 Type::bitset BitsetType::Lub(
double min,
double max) {
413 DisallowHeapAllocation no_allocation;
415 const Boundary* mins = Boundaries();
417 for (
size_t i = 1;
i < BoundariesSize(); ++
i) {
418 if (min < mins[
i].min) {
419 lub |= mins[
i - 1].internal;
420 if (max < mins[
i].min)
return lub;
423 return lub | mins[BoundariesSize() - 1].internal;
426 Type::bitset BitsetType::NumberBits(bitset bits) {
return bits & kPlainNumber; }
428 Type::bitset BitsetType::Glb(
double min,
double max) {
429 DisallowHeapAllocation no_allocation;
431 const Boundary* mins = Boundaries();
434 if (max < -1 || min > 0)
return glb;
436 for (
size_t i = 1;
i + 1 < BoundariesSize(); ++
i) {
437 if (min <= mins[
i].min) {
438 if (max + 1 < mins[
i + 1].min)
break;
439 glb |= mins[
i].external;
444 return glb & ~(kOtherNumber);
447 double BitsetType::Min(bitset bits) {
448 DisallowHeapAllocation no_allocation;
449 DCHECK(Is(bits, kNumber));
450 DCHECK(!Is(bits, kNaN));
451 const Boundary* mins = Boundaries();
452 bool mz = bits & kMinusZero;
453 for (
size_t i = 0;
i < BoundariesSize(); ++
i) {
454 if (Is(mins[
i].
internal, bits)) {
455 return mz ? std::min(0.0, mins[
i].min) : mins[
i].min;
462 double BitsetType::Max(bitset bits) {
463 DisallowHeapAllocation no_allocation;
464 DCHECK(Is(bits, kNumber));
465 DCHECK(!Is(bits, kNaN));
466 const Boundary* mins = Boundaries();
467 bool mz = bits & kMinusZero;
468 if (BitsetType::Is(mins[BoundariesSize() - 1].
internal, bits)) {
471 for (
size_t i = BoundariesSize() - 1;
i-- > 0;) {
472 if (Is(mins[
i].
internal, bits)) {
473 return mz ? std::max(0.0, mins[
i + 1].min - 1) : mins[
i + 1].min - 1;
481 bool OtherNumberConstantType::IsOtherNumberConstant(
double value) {
483 return !std::isnan(value) && !RangeType::IsInteger(value) &&
487 HeapConstantType::HeapConstantType(BitsetType::bitset bitset,
488 const HeapObjectRef& heap_ref)
489 : TypeBase(kHeapConstant), bitset_(bitset), heap_ref_(heap_ref) {}
491 Handle<HeapObject> HeapConstantType::Value()
const {
492 return heap_ref_.object();
498 bool Type::SimplyEquals(
Type that)
const {
499 DisallowHeapAllocation no_allocation;
500 if (this->IsHeapConstant()) {
501 return that.IsHeapConstant() &&
502 this->AsHeapConstant()->Value().address() ==
503 that.AsHeapConstant()->Value().address();
505 if (this->IsOtherNumberConstant()) {
506 return that.IsOtherNumberConstant() &&
507 this->AsOtherNumberConstant()->Value() ==
508 that.AsOtherNumberConstant()->Value();
510 if (this->IsRange()) {
511 if (that.IsHeapConstant() || that.IsOtherNumberConstant())
return false;
513 if (this->IsTuple()) {
514 if (!that.IsTuple())
return false;
515 const TupleType* this_tuple = this->AsTuple();
516 const TupleType* that_tuple = that.AsTuple();
517 if (this_tuple->Arity() != that_tuple->Arity()) {
520 for (
int i = 0, n = this_tuple->Arity();
i < n; ++
i) {
521 if (!this_tuple->Element(
i).Equals(that_tuple->Element(
i)))
return false;
529 bool Type::SlowIs(
Type that)
const {
530 DisallowHeapAllocation no_allocation;
533 if (that.IsBitset()) {
534 return BitsetType::Is(this->BitsetLub(), that.AsBitset());
537 if (this->IsBitset()) {
538 return BitsetType::Is(this->AsBitset(), that.BitsetGlb());
542 if (this->IsUnion()) {
543 for (
int i = 0, n = this->AsUnion()->Length();
i < n; ++
i) {
544 if (!this->AsUnion()->Get(
i).Is(that))
return false;
550 if (that.IsUnion()) {
551 for (
int i = 0, n = that.AsUnion()->Length();
i < n; ++
i) {
552 if (this->Is(that.AsUnion()->Get(
i)))
return true;
553 if (
i > 1 && this->IsRange())
return false;
558 if (that.IsRange()) {
559 return (this->IsRange() && Contains(that.AsRange(), this->AsRange()));
561 if (this->IsRange())
return false;
563 return this->SimplyEquals(that);
567 bool Type::Maybe(
Type that)
const {
568 DisallowHeapAllocation no_allocation;
570 if (BitsetType::IsNone(this->BitsetLub() & that.BitsetLub()))
return false;
573 if (this->IsUnion()) {
574 for (
int i = 0, n = this->AsUnion()->Length();
i < n; ++
i) {
575 if (this->AsUnion()->Get(
i).Maybe(that))
return true;
581 if (that.IsUnion()) {
582 for (
int i = 0, n = that.AsUnion()->Length();
i < n; ++
i) {
583 if (this->Maybe(that.AsUnion()->Get(
i)))
return true;
588 if (this->IsBitset() && that.IsBitset())
return true;
590 if (this->IsRange()) {
591 if (that.IsRange()) {
592 return Overlap(this->AsRange(), that.AsRange());
594 if (that.IsBitset()) {
595 bitset number_bits = BitsetType::NumberBits(that.AsBitset());
596 if (number_bits == BitsetType::kNone) {
599 double min = std::max(BitsetType::Min(number_bits), this->Min());
600 double max = std::min(BitsetType::Max(number_bits), this->Max());
604 if (that.IsRange()) {
605 return that.Maybe(*
this);
608 if (this->IsBitset() || that.IsBitset())
return true;
610 return this->SimplyEquals(that);
614 Type Type::GetRange()
const {
615 DisallowHeapAllocation no_allocation;
616 if (this->IsRange())
return *
this;
617 if (this->IsUnion() && this->AsUnion()->Get(1).IsRange()) {
618 return this->AsUnion()->Get(1);
623 bool UnionType::Wellformed()
const {
624 DisallowHeapAllocation no_allocation;
633 DCHECK_LE(2, this->Length());
634 DCHECK(this->Get(0).IsBitset());
636 for (
int i = 0;
i < this->Length(); ++
i) {
637 if (
i != 0) DCHECK(!this->Get(
i).IsBitset());
638 if (
i != 1) DCHECK(!this->Get(
i).IsRange());
639 DCHECK(!this->Get(
i).IsUnion());
640 for (
int j = 0; j < this->Length(); ++j) {
641 if (
i != j &&
i != 0) DCHECK(!this->Get(
i).Is(this->Get(j)));
644 DCHECK(!this->Get(1).IsRange() ||
645 (BitsetType::NumberBits(this->Get(0).AsBitset()) ==
653 Type Type::Intersect(
Type type1,
Type type2, Zone* zone) {
655 if (type1.IsBitset() && type2.IsBitset()) {
656 return NewBitset(type1.AsBitset() & type2.AsBitset());
660 if (type1.IsNone() || type2.IsAny())
return type1;
661 if (type2.IsNone() || type1.IsAny())
return type2;
664 if (type1.Is(type2))
return type1;
665 if (type2.Is(type1))
return type2;
671 if (type1.Is(type2)) {
673 }
else if (type2.Is(type1)) {
677 bitset bits = type1.BitsetGlb() & type2.BitsetGlb();
678 int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1;
679 int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1;
681 if (base::bits::SignedAddOverflow32(size1, size2, &size))
return Any();
682 if (base::bits::SignedAddOverflow32(size, 2, &size))
return Any();
683 UnionType* result = UnionType::New(size, zone);
687 result->Set(size++, NewBitset(bits));
689 RangeType::Limits lims = RangeType::Limits::Empty();
690 size = IntersectAux(type1, type2, result, size, &lims, zone);
694 if (!lims.IsEmpty()) {
695 size = UpdateRange(Type::Range(lims, zone), result, size, zone);
698 bitset number_bits = BitsetType::NumberBits(bits);
699 bits &= ~number_bits;
700 result->Set(0, NewBitset(bits));
702 return NormalizeUnion(result, size, zone);
705 int Type::UpdateRange(
Type range, UnionType* result,
int size, Zone* zone) {
707 result->Set(size++, range);
710 result->Set(size++, result->Get(1));
711 result->Set(1, range);
715 for (
int i = 2;
i < size;) {
716 if (result->Get(
i).Is(range)) {
717 result->Set(
i, result->Get(--size));
725 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) {
726 bitset number_bits = BitsetType::NumberBits(bits);
728 if (number_bits == BitsetType::kNone) {
729 return RangeType::Limits::Empty();
732 return RangeType::Limits(BitsetType::Min(number_bits),
733 BitsetType::Max(number_bits));
736 RangeType::Limits Type::IntersectRangeAndBitset(
Type range,
Type bitset,
738 RangeType::Limits range_lims(range.AsRange());
739 RangeType::Limits bitset_lims = ToLimits(bitset.AsBitset(), zone);
740 return RangeType::Limits::Intersect(range_lims, bitset_lims);
743 int Type::IntersectAux(
Type lhs,
Type rhs, UnionType* result,
int size,
744 RangeType::Limits* lims, Zone* zone) {
746 for (
int i = 0, n = lhs.AsUnion()->Length();
i < n; ++
i) {
747 size = IntersectAux(lhs.AsUnion()->Get(
i), rhs, result, size, lims, zone);
752 for (
int i = 0, n = rhs.AsUnion()->Length();
i < n; ++
i) {
753 size = IntersectAux(lhs, rhs.AsUnion()->Get(
i), result, size, lims, zone);
758 if (BitsetType::IsNone(lhs.BitsetLub() & rhs.BitsetLub()))
return size;
761 if (rhs.IsBitset()) {
762 RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
764 if (!lim.IsEmpty()) {
765 *lims = RangeType::Limits::Union(lim, *lims);
770 RangeType::Limits lim = RangeType::Limits::Intersect(
771 RangeType::Limits(lhs.AsRange()), RangeType::Limits(rhs.AsRange()));
772 if (!lim.IsEmpty()) {
773 *lims = RangeType::Limits::Union(lim, *lims);
780 return IntersectAux(rhs, lhs, result, size, lims, zone);
782 if (lhs.IsBitset() || rhs.IsBitset()) {
783 return AddToUnion(lhs.IsBitset() ? rhs : lhs, result, size, zone);
785 if (lhs.SimplyEquals(rhs)) {
786 return AddToUnion(lhs, result, size, zone);
795 Type Type::NormalizeRangeAndBitset(
Type range, bitset* bits, Zone* zone) {
798 bitset number_bits = BitsetType::NumberBits(*bits);
799 if (number_bits == 0) {
805 bitset range_lub = range.BitsetLub();
806 if (BitsetType::Is(range_lub, *bits)) {
811 double bitset_min = BitsetType::Min(number_bits);
812 double bitset_max = BitsetType::Max(number_bits);
814 double range_min = range.Min();
815 double range_max = range.Max();
820 *bits &= ~number_bits;
822 if (range_min <= bitset_min && range_max >= bitset_max) {
827 if (bitset_min < range_min) {
828 range_min = bitset_min;
830 if (bitset_max > range_max) {
831 range_max = bitset_max;
833 return Type::Range(range_min, range_max, zone);
836 Type Type::NewConstant(
double value, Zone* zone) {
837 if (RangeType::IsInteger(value)) {
838 return Range(value, value, zone);
839 }
else if (IsMinusZero(value)) {
840 return Type::MinusZero();
841 }
else if (std::isnan(value)) {
845 DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));
846 return OtherNumberConstant(value, zone);
849 Type Type::NewConstant(JSHeapBroker* broker, Handle<i::Object> value,
851 ObjectRef ref(broker, value);
853 return NewConstant(static_cast<double>(ref.AsSmi()), zone);
855 if (ref.IsHeapNumber()) {
856 return NewConstant(ref.AsHeapNumber().value(), zone);
858 if (ref.IsString() && !ref.IsInternalizedString()) {
859 return Type::String();
861 return HeapConstant(ref.AsHeapObject(), zone);
866 if (type1.IsBitset() && type2.IsBitset()) {
867 return NewBitset(type1.AsBitset() | type2.AsBitset());
871 if (type1.IsAny() || type2.IsNone())
return type1;
872 if (type2.IsAny() || type1.IsNone())
return type2;
875 if (type1.Is(type2))
return type2;
876 if (type2.Is(type1))
return type1;
879 int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1;
880 int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1;
882 if (base::bits::SignedAddOverflow32(size1, size2, &size))
return Any();
883 if (base::bits::SignedAddOverflow32(size, 2, &size))
return Any();
884 UnionType* result = UnionType::New(size, zone);
888 bitset new_bitset = type1.BitsetGlb() | type2.BitsetGlb();
892 Type range1 = type1.GetRange();
893 Type range2 = type2.GetRange();
894 if (range1 !=
nullptr && range2 !=
nullptr) {
895 RangeType::Limits lims =
896 RangeType::Limits::Union(RangeType::Limits(range1.AsRange()),
897 RangeType::Limits(range2.AsRange()));
898 Type union_range = Type::Range(lims, zone);
899 range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
900 }
else if (range1 !=
nullptr) {
901 range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
902 }
else if (range2 !=
nullptr) {
903 range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
905 Type bits = NewBitset(new_bitset);
906 result->Set(size++, bits);
907 if (!range.IsNone()) result->Set(size++, range);
909 size = AddToUnion(type1, result, size, zone);
910 size = AddToUnion(type2, result, size, zone);
911 return NormalizeUnion(result, size, zone);
916 int Type::AddToUnion(
Type type, UnionType* result,
int size, Zone* zone) {
917 if (type.IsBitset() || type.IsRange())
return size;
918 if (type.IsUnion()) {
919 for (
int i = 0, n = type.AsUnion()->Length();
i < n; ++
i) {
920 size = AddToUnion(type.AsUnion()->Get(
i), result, size, zone);
924 for (
int i = 0;
i < size; ++
i) {
925 if (type.Is(result->Get(
i)))
return size;
927 result->Set(size++, type);
931 Type Type::NormalizeUnion(UnionType* unioned,
int size, Zone* zone) {
933 DCHECK(unioned->Get(0).IsBitset());
936 return unioned->Get(0);
938 bitset bits = unioned->Get(0).AsBitset();
940 if (size == 2 && bits == BitsetType::kNone) {
941 if (unioned->Get(1).IsRange()) {
942 return Type::Range(unioned->Get(1).AsRange()->Min(),
943 unioned->Get(1).AsRange()->Max(), zone);
946 unioned->Shrink(size);
947 SLOW_DCHECK(unioned->Wellformed());
948 return Type(unioned);
951 int Type::NumConstants()
const {
952 DisallowHeapAllocation no_allocation;
953 if (this->IsHeapConstant() || this->IsOtherNumberConstant()) {
955 }
else if (this->IsUnion()) {
957 for (
int i = 0, n = this->AsUnion()->Length();
i < n; ++
i) {
958 if (this->AsUnion()->Get(
i).IsHeapConstant()) ++result;
969 const char* BitsetType::Name(bitset bits) {
971 #define RETURN_NAMED_TYPE(type, value) \ 974 PROPER_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
975 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
976 #undef RETURN_NAMED_TYPE 983 void BitsetType::Print(std::ostream& os,
985 DisallowHeapAllocation no_allocation;
986 const char* name = Name(bits);
987 if (name !=
nullptr) {
993 static const bitset named_bitsets[] = {
994 #define BITSET_CONSTANT(type, value) k##type, 995 INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
996 PROPER_BITSET_TYPE_LIST(BITSET_CONSTANT)
997 #undef BITSET_CONSTANT 1001 bool is_first =
true;
1003 for (
int i(arraysize(named_bitsets) - 1); bits != 0 &&
i >= 0; --
i) {
1004 bitset subset = named_bitsets[
i];
1005 if ((bits & subset) == subset) {
1006 if (!is_first) os <<
" | ";
1016 void Type::PrintTo(std::ostream& os)
const {
1017 DisallowHeapAllocation no_allocation;
1018 if (this->IsBitset()) {
1019 BitsetType::Print(os, this->AsBitset());
1020 }
else if (this->IsHeapConstant()) {
1021 os <<
"HeapConstant(" << Brief(*this->AsHeapConstant()->
Value()) <<
")";
1022 }
else if (this->IsOtherNumberConstant()) {
1023 os <<
"OtherNumberConstant(" << this->AsOtherNumberConstant()->Value()
1025 }
else if (this->IsRange()) {
1026 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1027 std::streamsize saved_precision = os.precision(0);
1028 os <<
"Range(" << this->AsRange()->Min() <<
", " << this->AsRange()->Max()
1030 os.flags(saved_flags);
1031 os.precision(saved_precision);
1032 }
else if (this->IsUnion()) {
1034 for (
int i = 0, n = this->AsUnion()->Length();
i < n; ++
i) {
1035 Type type_i = this->AsUnion()->Get(
i);
1036 if (
i > 0) os <<
" | ";
1040 }
else if (this->IsTuple()) {
1042 for (
int i = 0, n = this->AsTuple()->Arity();
i < n; ++
i) {
1043 Type type_i = this->AsTuple()->Element(
i);
1044 if (
i > 0) os <<
", ";
1054 void Type::Print()
const {
1059 void BitsetType::Print(bitset bits) {
1066 BitsetType::bitset BitsetType::SignedSmall() {
1067 return SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1070 BitsetType::bitset BitsetType::UnsignedSmall() {
1071 return SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1076 TupleType* tuple = TupleType::New(3, zone);
1077 tuple->InitElement(0, first);
1078 tuple->InitElement(1, second);
1079 tuple->InitElement(2, third);
1080 return FromTypeBase(tuple);
1084 Type Type::OtherNumberConstant(
double value, Zone* zone) {
1085 return FromTypeBase(OtherNumberConstantType::New(value, zone));
1089 Type Type::HeapConstant(JSHeapBroker* broker, Handle<i::Object> value,
1091 return FromTypeBase(
1092 HeapConstantType::New(HeapObjectRef(broker, value), zone));
1096 Type Type::HeapConstant(
const HeapObjectRef& value, Zone* zone) {
1097 return HeapConstantType::New(value, zone);
1101 Type Type::Range(
double min,
double max, Zone* zone) {
1102 return FromTypeBase(RangeType::New(min, max, zone));
1106 Type Type::Range(RangeType::Limits lims, Zone* zone) {
1107 return FromTypeBase(RangeType::New(lims, zone));
1111 Type Type::Union(
int length, Zone* zone) {
1112 return FromTypeBase(UnionType::New(length, zone));
1115 const HeapConstantType* Type::AsHeapConstant()
const {
1116 DCHECK(IsKind(TypeBase::kHeapConstant));
1117 return static_cast<const HeapConstantType*
>(ToTypeBase());
1120 const OtherNumberConstantType* Type::AsOtherNumberConstant()
const {
1121 DCHECK(IsKind(TypeBase::kOtherNumberConstant));
1122 return static_cast<const OtherNumberConstantType*
>(ToTypeBase());
1125 const RangeType* Type::AsRange()
const {
1126 DCHECK(IsKind(TypeBase::kRange));
1127 return static_cast<const RangeType*
>(ToTypeBase());
1130 const TupleType* Type::AsTuple()
const {
1131 DCHECK(IsKind(TypeBase::kTuple));
1132 return static_cast<const TupleType*
>(ToTypeBase());
1135 const UnionType* Type::AsUnion()
const {
1136 DCHECK(IsKind(TypeBase::kUnion));
1137 return static_cast<const UnionType*
>(ToTypeBase());
1140 std::ostream& operator<<(std::ostream& os,
Type type) {