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/compiler/types.h"
8 
9 #include "src/handles-inl.h"
10 #include "src/ostreams.h"
11 
12 namespace v8 {
13 namespace internal {
14 namespace compiler {
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 * range,i::Object * val)59 bool Type::Contains(RangeType* range, i::Object* val) {
60   DisallowHeapAllocation no_allocation;
61   return IsInteger(val) && range->Min() <= val->Number() &&
62          val->Number() <= range->Max();
63 }
64 
65 // -----------------------------------------------------------------------------
66 // Min and Max computation.
67 
Min()68 double Type::Min() {
69   DCHECK(this->Is(Number()));
70   if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
71   if (this->IsUnion()) {
72     double min = +V8_INFINITY;
73     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
74       min = std::min(min, this->AsUnion()->Get(i)->Min());
75     }
76     return min;
77   }
78   if (this->IsRange()) return this->AsRange()->Min();
79   if (this->IsOtherNumberConstant())
80     return this->AsOtherNumberConstant()->Value();
81   UNREACHABLE();
82   return 0;
83 }
84 
Max()85 double Type::Max() {
86   DCHECK(this->Is(Number()));
87   if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
88   if (this->IsUnion()) {
89     double max = -V8_INFINITY;
90     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
91       max = std::max(max, this->AsUnion()->Get(i)->Max());
92     }
93     return max;
94   }
95   if (this->IsRange()) return this->AsRange()->Max();
96   if (this->IsOtherNumberConstant())
97     return this->AsOtherNumberConstant()->Value();
98   UNREACHABLE();
99   return 0;
100 }
101 
102 // -----------------------------------------------------------------------------
103 // Glb and lub computation.
104 
105 // The largest bitset subsumed by this type.
Glb(Type * type)106 Type::bitset BitsetType::Glb(Type* type) {
107   DisallowHeapAllocation no_allocation;
108   // Fast case.
109   if (IsBitset(type)) {
110     return type->AsBitset();
111   } else if (type->IsUnion()) {
112     SLOW_DCHECK(type->AsUnion()->Wellformed());
113     return type->AsUnion()->Get(0)->BitsetGlb() |
114            type->AsUnion()->Get(1)->BitsetGlb();  // Shortcut.
115   } else if (type->IsRange()) {
116     bitset glb =
117         BitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max());
118     return glb;
119   } else {
120     return kNone;
121   }
122 }
123 
124 // The smallest bitset subsuming this type, possibly not a proper one.
Lub(Type * type)125 Type::bitset BitsetType::Lub(Type* type) {
126   DisallowHeapAllocation no_allocation;
127   if (IsBitset(type)) return type->AsBitset();
128   if (type->IsUnion()) {
129     // Take the representation from the first element, which is always
130     // a bitset.
131     int bitset = type->AsUnion()->Get(0)->BitsetLub();
132     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
133       // Other elements only contribute their semantic part.
134       bitset |= type->AsUnion()->Get(i)->BitsetLub();
135     }
136     return bitset;
137   }
138   if (type->IsHeapConstant()) return type->AsHeapConstant()->Lub();
139   if (type->IsOtherNumberConstant())
140     return type->AsOtherNumberConstant()->Lub();
141   if (type->IsRange()) return type->AsRange()->Lub();
142   if (type->IsTuple()) return kOtherInternal;
143   UNREACHABLE();
144   return kNone;
145 }
146 
Lub(i::Map * map)147 Type::bitset BitsetType::Lub(i::Map* map) {
148   DisallowHeapAllocation no_allocation;
149   switch (map->instance_type()) {
150     case STRING_TYPE:
151     case ONE_BYTE_STRING_TYPE:
152     case CONS_STRING_TYPE:
153     case CONS_ONE_BYTE_STRING_TYPE:
154     case SLICED_STRING_TYPE:
155     case SLICED_ONE_BYTE_STRING_TYPE:
156     case EXTERNAL_STRING_TYPE:
157     case EXTERNAL_ONE_BYTE_STRING_TYPE:
158     case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
159     case SHORT_EXTERNAL_STRING_TYPE:
160     case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
161     case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
162       return kOtherString;
163     case INTERNALIZED_STRING_TYPE:
164     case ONE_BYTE_INTERNALIZED_STRING_TYPE:
165     case EXTERNAL_INTERNALIZED_STRING_TYPE:
166     case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
167     case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
168     case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
169     case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
170     case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
171       return kInternalizedString;
172     case SYMBOL_TYPE:
173       return kSymbol;
174     case ODDBALL_TYPE: {
175       Heap* heap = map->GetHeap();
176       if (map == heap->undefined_map()) return kUndefined;
177       if (map == heap->null_map()) return kNull;
178       if (map == heap->boolean_map()) return kBoolean;
179       if (map == heap->the_hole_map()) return kHole;
180       DCHECK(map == heap->uninitialized_map() ||
181              map == heap->no_interceptor_result_sentinel_map() ||
182              map == heap->termination_exception_map() ||
183              map == heap->arguments_marker_map() ||
184              map == heap->optimized_out_map() ||
185              map == heap->stale_register_map());
186       return kOtherInternal;
187     }
188     case HEAP_NUMBER_TYPE:
189       return kNumber;
190     case SIMD128_VALUE_TYPE:
191       return kSimd;
192     case JS_OBJECT_TYPE:
193     case JS_ARGUMENTS_TYPE:
194     case JS_ERROR_TYPE:
195     case JS_GLOBAL_OBJECT_TYPE:
196     case JS_GLOBAL_PROXY_TYPE:
197     case JS_API_OBJECT_TYPE:
198     case JS_SPECIAL_API_OBJECT_TYPE:
199       if (map->is_undetectable()) return kOtherUndetectable;
200       return kOtherObject;
201     case JS_VALUE_TYPE:
202     case JS_MESSAGE_OBJECT_TYPE:
203     case JS_DATE_TYPE:
204     case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
205     case JS_GENERATOR_OBJECT_TYPE:
206     case JS_MODULE_NAMESPACE_TYPE:
207     case JS_FIXED_ARRAY_ITERATOR_TYPE:
208     case JS_ARRAY_BUFFER_TYPE:
209     case JS_ARRAY_TYPE:
210     case JS_REGEXP_TYPE:  // TODO(rossberg): there should be a RegExp type.
211     case JS_TYPED_ARRAY_TYPE:
212     case JS_DATA_VIEW_TYPE:
213     case JS_SET_TYPE:
214     case JS_MAP_TYPE:
215     case JS_SET_ITERATOR_TYPE:
216     case JS_MAP_ITERATOR_TYPE:
217     case JS_STRING_ITERATOR_TYPE:
218 
219     case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
220     case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
221     case JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE:
222     case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
223     case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
224     case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
225     case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
226     case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
227     case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
228     case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
229     case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
230     case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
231     case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
232     case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
233     case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
234     case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
235     case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
236     case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
237     case JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE:
238     case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
239     case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
240     case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
241     case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
242     case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
243     case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
244     case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
245     case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
246     case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
247     case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
248     case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
249     case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
250     case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
251     case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
252     case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
253     case JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE:
254 
255     case JS_WEAK_MAP_TYPE:
256     case JS_WEAK_SET_TYPE:
257     case JS_PROMISE_TYPE:
258     case JS_BOUND_FUNCTION_TYPE:
259       DCHECK(!map->is_undetectable());
260       return kOtherObject;
261     case JS_FUNCTION_TYPE:
262       DCHECK(!map->is_undetectable());
263       return kFunction;
264     case JS_PROXY_TYPE:
265       DCHECK(!map->is_undetectable());
266       return kProxy;
267     case MAP_TYPE:
268     case ALLOCATION_SITE_TYPE:
269     case ACCESSOR_INFO_TYPE:
270     case SHARED_FUNCTION_INFO_TYPE:
271     case FUNCTION_TEMPLATE_INFO_TYPE:
272     case ACCESSOR_PAIR_TYPE:
273     case FIXED_ARRAY_TYPE:
274     case FIXED_DOUBLE_ARRAY_TYPE:
275     case BYTE_ARRAY_TYPE:
276     case BYTECODE_ARRAY_TYPE:
277     case TRANSITION_ARRAY_TYPE:
278     case FOREIGN_TYPE:
279     case SCRIPT_TYPE:
280     case CODE_TYPE:
281     case PROPERTY_CELL_TYPE:
282     case MODULE_TYPE:
283     case MODULE_INFO_ENTRY_TYPE:
284       return kOtherInternal;
285 
286     // Remaining instance types are unsupported for now. If any of them do
287     // require bit set types, they should get kOtherInternal.
288     case MUTABLE_HEAP_NUMBER_TYPE:
289     case FREE_SPACE_TYPE:
290 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
291   case FIXED_##TYPE##_ARRAY_TYPE:
292 
293       TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
294 #undef FIXED_TYPED_ARRAY_CASE
295     case FILLER_TYPE:
296     case ACCESS_CHECK_INFO_TYPE:
297     case INTERCEPTOR_INFO_TYPE:
298     case CALL_HANDLER_INFO_TYPE:
299     case OBJECT_TEMPLATE_INFO_TYPE:
300     case SIGNATURE_INFO_TYPE:
301     case TYPE_SWITCH_INFO_TYPE:
302     case ALLOCATION_MEMENTO_TYPE:
303     case TYPE_FEEDBACK_INFO_TYPE:
304     case ALIASED_ARGUMENTS_ENTRY_TYPE:
305     case BOX_TYPE:
306     case PROMISE_RESOLVE_THENABLE_JOB_INFO_TYPE:
307     case PROMISE_REACTION_JOB_INFO_TYPE:
308     case DEBUG_INFO_TYPE:
309     case BREAK_POINT_INFO_TYPE:
310     case CELL_TYPE:
311     case WEAK_CELL_TYPE:
312     case PROTOTYPE_INFO_TYPE:
313     case TUPLE3_TYPE:
314     case CONTEXT_EXTENSION_TYPE:
315       UNREACHABLE();
316       return kNone;
317   }
318   UNREACHABLE();
319   return kNone;
320 }
321 
Lub(i::Object * value)322 Type::bitset BitsetType::Lub(i::Object* value) {
323   DisallowHeapAllocation no_allocation;
324   if (value->IsNumber()) {
325     return Lub(value->Number());
326   }
327   return Lub(i::HeapObject::cast(value)->map());
328 }
329 
Lub(double value)330 Type::bitset BitsetType::Lub(double value) {
331   DisallowHeapAllocation no_allocation;
332   if (i::IsMinusZero(value)) return kMinusZero;
333   if (std::isnan(value)) return kNaN;
334   if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
335   return kOtherNumber;
336 }
337 
338 // Minimum values of plain numeric bitsets.
339 const BitsetType::Boundary BitsetType::BoundariesArray[] = {
340     {kOtherNumber, kPlainNumber, -V8_INFINITY},
341     {kOtherSigned32, kNegative32, kMinInt},
342     {kNegative31, kNegative31, -0x40000000},
343     {kUnsigned30, kUnsigned30, 0},
344     {kOtherUnsigned31, kUnsigned31, 0x40000000},
345     {kOtherUnsigned32, kUnsigned32, 0x80000000},
346     {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
347 
Boundaries()348 const BitsetType::Boundary* BitsetType::Boundaries() { return BoundariesArray; }
349 
BoundariesSize()350 size_t BitsetType::BoundariesSize() {
351   // Windows doesn't like arraysize here.
352   // return arraysize(BoundariesArray);
353   return 7;
354 }
355 
ExpandInternals(Type::bitset bits)356 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) {
357   DisallowHeapAllocation no_allocation;
358   if (!(bits & kPlainNumber)) return bits;  // Shortcut.
359   const Boundary* boundaries = Boundaries();
360   for (size_t i = 0; i < BoundariesSize(); ++i) {
361     DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external));
362     if (bits & boundaries[i].internal) bits |= boundaries[i].external;
363   }
364   return bits;
365 }
366 
Lub(double min,double max)367 Type::bitset BitsetType::Lub(double min, double max) {
368   DisallowHeapAllocation no_allocation;
369   int lub = kNone;
370   const Boundary* mins = Boundaries();
371 
372   for (size_t i = 1; i < BoundariesSize(); ++i) {
373     if (min < mins[i].min) {
374       lub |= mins[i - 1].internal;
375       if (max < mins[i].min) return lub;
376     }
377   }
378   return lub | mins[BoundariesSize() - 1].internal;
379 }
380 
NumberBits(bitset bits)381 Type::bitset BitsetType::NumberBits(bitset bits) { return bits & kPlainNumber; }
382 
Glb(double min,double max)383 Type::bitset BitsetType::Glb(double min, double max) {
384   DisallowHeapAllocation no_allocation;
385   int glb = kNone;
386   const Boundary* mins = Boundaries();
387 
388   // If the range does not touch 0, the bound is empty.
389   if (max < -1 || min > 0) return glb;
390 
391   for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
392     if (min <= mins[i].min) {
393       if (max + 1 < mins[i + 1].min) break;
394       glb |= mins[i].external;
395     }
396   }
397   // OtherNumber also contains float numbers, so it can never be
398   // in the greatest lower bound.
399   return glb & ~(kOtherNumber);
400 }
401 
Min(bitset bits)402 double BitsetType::Min(bitset bits) {
403   DisallowHeapAllocation no_allocation;
404   DCHECK(Is(bits, kNumber));
405   const Boundary* mins = Boundaries();
406   bool mz = bits & kMinusZero;
407   for (size_t i = 0; i < BoundariesSize(); ++i) {
408     if (Is(mins[i].internal, bits)) {
409       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
410     }
411   }
412   if (mz) return 0;
413   return std::numeric_limits<double>::quiet_NaN();
414 }
415 
Max(bitset bits)416 double BitsetType::Max(bitset bits) {
417   DisallowHeapAllocation no_allocation;
418   DCHECK(Is(bits, kNumber));
419   const Boundary* mins = Boundaries();
420   bool mz = bits & kMinusZero;
421   if (BitsetType::Is(mins[BoundariesSize() - 1].internal, bits)) {
422     return +V8_INFINITY;
423   }
424   for (size_t i = BoundariesSize() - 1; i-- > 0;) {
425     if (Is(mins[i].internal, bits)) {
426       return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
427     }
428   }
429   if (mz) return 0;
430   return std::numeric_limits<double>::quiet_NaN();
431 }
432 
433 // static
IsOtherNumberConstant(double value)434 bool OtherNumberConstantType::IsOtherNumberConstant(double value) {
435   // Not an integer, not NaN, and not -0.
436   return !std::isnan(value) && !Type::IsInteger(value) &&
437          !i::IsMinusZero(value);
438 }
439 
440 // static
IsOtherNumberConstant(Object * value)441 bool OtherNumberConstantType::IsOtherNumberConstant(Object* value) {
442   return value->IsHeapNumber() &&
443          IsOtherNumberConstant(HeapNumber::cast(value)->value());
444 }
445 
HeapConstantType(BitsetType::bitset bitset,i::Handle<i::HeapObject> object)446 HeapConstantType::HeapConstantType(BitsetType::bitset bitset,
447                                    i::Handle<i::HeapObject> object)
448     : TypeBase(kHeapConstant), bitset_(bitset), object_(object) {
449   DCHECK(!object->IsHeapNumber());
450   DCHECK(!object->IsString());
451 }
452 
453 // -----------------------------------------------------------------------------
454 // Predicates.
455 
SimplyEquals(Type * that)456 bool Type::SimplyEquals(Type* that) {
457   DisallowHeapAllocation no_allocation;
458   if (this->IsHeapConstant()) {
459     return that->IsHeapConstant() &&
460            this->AsHeapConstant()->Value().address() ==
461                that->AsHeapConstant()->Value().address();
462   }
463   if (this->IsOtherNumberConstant()) {
464     return that->IsOtherNumberConstant() &&
465            this->AsOtherNumberConstant()->Value() ==
466                that->AsOtherNumberConstant()->Value();
467   }
468   if (this->IsRange()) {
469     if (that->IsHeapConstant() || that->IsOtherNumberConstant()) return false;
470   }
471   if (this->IsTuple()) {
472     if (!that->IsTuple()) return false;
473     TupleType* this_tuple = this->AsTuple();
474     TupleType* that_tuple = that->AsTuple();
475     if (this_tuple->Arity() != that_tuple->Arity()) {
476       return false;
477     }
478     for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
479       if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false;
480     }
481     return true;
482   }
483   UNREACHABLE();
484   return false;
485 }
486 
487 // Check if [this] <= [that].
SlowIs(Type * that)488 bool Type::SlowIs(Type* that) {
489   DisallowHeapAllocation no_allocation;
490 
491   // Fast bitset cases
492   if (that->IsBitset()) {
493     return BitsetType::Is(this->BitsetLub(), that->AsBitset());
494   }
495 
496   if (this->IsBitset()) {
497     return BitsetType::Is(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)->Is(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->Is(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   }
520   if (this->IsRange()) return false;
521 
522   return this->SimplyEquals(that);
523 }
524 
525 // Check if [this] and [that] overlap.
Maybe(Type * that)526 bool Type::Maybe(Type* that) {
527   DisallowHeapAllocation no_allocation;
528 
529   if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
530     return false;
531 
532   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
533   if (this->IsUnion()) {
534     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
535       if (this->AsUnion()->Get(i)->Maybe(that)) return true;
536     }
537     return false;
538   }
539 
540   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
541   if (that->IsUnion()) {
542     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
543       if (this->Maybe(that->AsUnion()->Get(i))) return true;
544     }
545     return false;
546   }
547 
548   if (this->IsBitset() && that->IsBitset()) return true;
549 
550   if (this->IsRange()) {
551     if (that->IsRange()) {
552       return Overlap(this->AsRange(), that->AsRange());
553     }
554     if (that->IsBitset()) {
555       bitset number_bits = BitsetType::NumberBits(that->AsBitset());
556       if (number_bits == BitsetType::kNone) {
557         return false;
558       }
559       double min = std::max(BitsetType::Min(number_bits), this->Min());
560       double max = std::min(BitsetType::Max(number_bits), this->Max());
561       return min <= max;
562     }
563   }
564   if (that->IsRange()) {
565     return that->Maybe(this);  // This case is handled above.
566   }
567 
568   if (this->IsBitset() || that->IsBitset()) return true;
569 
570   return this->SimplyEquals(that);
571 }
572 
573 // Return the range in [this], or [NULL].
GetRange()574 Type* Type::GetRange() {
575   DisallowHeapAllocation no_allocation;
576   if (this->IsRange()) return this;
577   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
578     return this->AsUnion()->Get(1);
579   }
580   return NULL;
581 }
582 
Wellformed()583 bool UnionType::Wellformed() {
584   DisallowHeapAllocation no_allocation;
585   // This checks the invariants of the union representation:
586   // 1. There are at least two elements.
587   // 2. The first element is a bitset, no other element is a bitset.
588   // 3. At most one element is a range, and it must be the second one.
589   // 4. No element is itself a union.
590   // 5. No element (except the bitset) is a subtype of any other.
591   // 6. If there is a range, then the bitset type does not contain
592   //    plain number bits.
593   DCHECK(this->Length() >= 2);       // (1)
594   DCHECK(this->Get(0)->IsBitset());  // (2a)
595 
596   for (int i = 0; i < this->Length(); ++i) {
597     if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2b)
598     if (i != 1) DCHECK(!this->Get(i)->IsRange());   // (3)
599     DCHECK(!this->Get(i)->IsUnion());               // (4)
600     for (int j = 0; j < this->Length(); ++j) {
601       if (i != j && i != 0) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
602     }
603   }
604   DCHECK(!this->Get(1)->IsRange() ||
605          (BitsetType::NumberBits(this->Get(0)->AsBitset()) ==
606           BitsetType::kNone));  // (6)
607   return true;
608 }
609 
610 // -----------------------------------------------------------------------------
611 // Union and intersection
612 
AddIsSafe(int x,int y)613 static bool AddIsSafe(int x, int y) {
614   return x >= 0 ? y <= std::numeric_limits<int>::max() - x
615                 : y >= std::numeric_limits<int>::min() - x;
616 }
617 
Intersect(Type * type1,Type * type2,Zone * zone)618 Type* Type::Intersect(Type* type1, Type* type2, Zone* zone) {
619   // Fast case: bit sets.
620   if (type1->IsBitset() && type2->IsBitset()) {
621     return BitsetType::New(type1->AsBitset() & type2->AsBitset());
622   }
623 
624   // Fast case: top or bottom types.
625   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
626   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
627 
628   // Semi-fast case.
629   if (type1->Is(type2)) return type1;
630   if (type2->Is(type1)) return type2;
631 
632   // Slow case: create union.
633 
634   // Semantic subtyping check - this is needed for consistency with the
635   // semi-fast case above.
636   if (type1->Is(type2)) {
637     type2 = Any();
638   } else if (type2->Is(type1)) {
639     type1 = Any();
640   }
641 
642   bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
643   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
644   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
645   if (!AddIsSafe(size1, size2)) return Any();
646   int size = size1 + size2;
647   if (!AddIsSafe(size, 2)) return Any();
648   size += 2;
649   Type* result_type = UnionType::New(size, zone);
650   UnionType* result = result_type->AsUnion();
651   size = 0;
652 
653   // Deal with bitsets.
654   result->Set(size++, BitsetType::New(bits));
655 
656   RangeType::Limits lims = RangeType::Limits::Empty();
657   size = IntersectAux(type1, type2, result, size, &lims, zone);
658 
659   // If the range is not empty, then insert it into the union and
660   // remove the number bits from the bitset.
661   if (!lims.IsEmpty()) {
662     size = UpdateRange(RangeType::New(lims, zone), result, size, zone);
663 
664     // Remove the number bits.
665     bitset number_bits = BitsetType::NumberBits(bits);
666     bits &= ~number_bits;
667     result->Set(0, BitsetType::New(bits));
668   }
669   return NormalizeUnion(result_type, size, zone);
670 }
671 
UpdateRange(Type * range,UnionType * result,int size,Zone * zone)672 int Type::UpdateRange(Type* range, UnionType* result, int size, Zone* zone) {
673   if (size == 1) {
674     result->Set(size++, range);
675   } else {
676     // Make space for the range.
677     result->Set(size++, result->Get(1));
678     result->Set(1, range);
679   }
680 
681   // Remove any components that just got subsumed.
682   for (int i = 2; i < size;) {
683     if (result->Get(i)->Is(range)) {
684       result->Set(i, result->Get(--size));
685     } else {
686       ++i;
687     }
688   }
689   return size;
690 }
691 
ToLimits(bitset bits,Zone * zone)692 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) {
693   bitset number_bits = BitsetType::NumberBits(bits);
694 
695   if (number_bits == BitsetType::kNone) {
696     return RangeType::Limits::Empty();
697   }
698 
699   return RangeType::Limits(BitsetType::Min(number_bits),
700                            BitsetType::Max(number_bits));
701 }
702 
IntersectRangeAndBitset(Type * range,Type * bitset,Zone * zone)703 RangeType::Limits Type::IntersectRangeAndBitset(Type* range, Type* bitset,
704                                                 Zone* zone) {
705   RangeType::Limits range_lims(range->AsRange());
706   RangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone);
707   return RangeType::Limits::Intersect(range_lims, bitset_lims);
708 }
709 
IntersectAux(Type * lhs,Type * rhs,UnionType * result,int size,RangeType::Limits * lims,Zone * zone)710 int Type::IntersectAux(Type* lhs, Type* rhs, UnionType* result, int size,
711                        RangeType::Limits* lims, Zone* zone) {
712   if (lhs->IsUnion()) {
713     for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
714       size =
715           IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone);
716     }
717     return size;
718   }
719   if (rhs->IsUnion()) {
720     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
721       size =
722           IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone);
723     }
724     return size;
725   }
726 
727   if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
728     return size;
729   }
730 
731   if (lhs->IsRange()) {
732     if (rhs->IsBitset()) {
733       RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
734 
735       if (!lim.IsEmpty()) {
736         *lims = RangeType::Limits::Union(lim, *lims);
737       }
738       return size;
739     }
740     if (rhs->IsRange()) {
741       RangeType::Limits lim = RangeType::Limits::Intersect(
742           RangeType::Limits(lhs->AsRange()), RangeType::Limits(rhs->AsRange()));
743       if (!lim.IsEmpty()) {
744         *lims = RangeType::Limits::Union(lim, *lims);
745       }
746     }
747     return size;
748   }
749   if (rhs->IsRange()) {
750     // This case is handled symmetrically above.
751     return IntersectAux(rhs, lhs, result, size, lims, zone);
752   }
753   if (lhs->IsBitset() || rhs->IsBitset()) {
754     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone);
755   }
756   if (lhs->SimplyEquals(rhs)) {
757     return AddToUnion(lhs, result, size, zone);
758   }
759   return size;
760 }
761 
762 // Make sure that we produce a well-formed range and bitset:
763 // If the range is non-empty, the number bits in the bitset should be
764 // clear. Moreover, if we have a canonical range (such as Signed32),
765 // we want to produce a bitset rather than a range.
NormalizeRangeAndBitset(Type * range,bitset * bits,Zone * zone)766 Type* Type::NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone) {
767   // Fast path: If the bitset does not mention numbers, we can just keep the
768   // range.
769   bitset number_bits = BitsetType::NumberBits(*bits);
770   if (number_bits == 0) {
771     return range;
772   }
773 
774   // If the range is semantically contained within the bitset, return None and
775   // leave the bitset untouched.
776   bitset range_lub = range->BitsetLub();
777   if (BitsetType::Is(range_lub, *bits)) {
778     return None();
779   }
780 
781   // Slow path: reconcile the bitset range and the range.
782   double bitset_min = BitsetType::Min(number_bits);
783   double bitset_max = BitsetType::Max(number_bits);
784 
785   double range_min = range->Min();
786   double range_max = range->Max();
787 
788   // Remove the number bits from the bitset, they would just confuse us now.
789   // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
790   // case we already returned after the subtype check above.
791   *bits &= ~number_bits;
792 
793   if (range_min <= bitset_min && range_max >= bitset_max) {
794     // Bitset is contained within the range, just return the range.
795     return range;
796   }
797 
798   if (bitset_min < range_min) {
799     range_min = bitset_min;
800   }
801   if (bitset_max > range_max) {
802     range_max = bitset_max;
803   }
804   return RangeType::New(range_min, range_max, zone);
805 }
806 
NewConstant(double value,Zone * zone)807 Type* Type::NewConstant(double value, Zone* zone) {
808   if (IsInteger(value)) {
809     return Range(value, value, zone);
810   } else if (i::IsMinusZero(value)) {
811     return Type::MinusZero();
812   } else if (std::isnan(value)) {
813     return Type::NaN();
814   }
815 
816   DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));
817   return OtherNumberConstant(value, zone);
818 }
819 
NewConstant(i::Handle<i::Object> value,Zone * zone)820 Type* Type::NewConstant(i::Handle<i::Object> value, Zone* zone) {
821   if (IsInteger(*value)) {
822     double v = value->Number();
823     return Range(v, v, zone);
824   } else if (value->IsHeapNumber()) {
825     return NewConstant(value->Number(), zone);
826   } else if (value->IsString()) {
827     bitset b = BitsetType::Lub(*value);
828     DCHECK(b == BitsetType::kInternalizedString ||
829            b == BitsetType::kOtherString);
830     if (b == BitsetType::kInternalizedString) {
831       return Type::InternalizedString();
832     } else if (b == BitsetType::kOtherString) {
833       return Type::OtherString();
834     } else {
835       UNREACHABLE();
836     }
837   }
838   return HeapConstant(i::Handle<i::HeapObject>::cast(value), zone);
839 }
840 
Union(Type * type1,Type * type2,Zone * zone)841 Type* Type::Union(Type* type1, Type* type2, Zone* zone) {
842   // Fast case: bit sets.
843   if (type1->IsBitset() && type2->IsBitset()) {
844     return BitsetType::New(type1->AsBitset() | type2->AsBitset());
845   }
846 
847   // Fast case: top or bottom types.
848   if (type1->IsAny() || type2->IsNone()) return type1;
849   if (type2->IsAny() || type1->IsNone()) return type2;
850 
851   // Semi-fast case.
852   if (type1->Is(type2)) return type2;
853   if (type2->Is(type1)) return type1;
854 
855   // Slow case: create union.
856   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
857   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
858   if (!AddIsSafe(size1, size2)) return Any();
859   int size = size1 + size2;
860   if (!AddIsSafe(size, 2)) return Any();
861   size += 2;
862   Type* result_type = UnionType::New(size, zone);
863   UnionType* result = result_type->AsUnion();
864   size = 0;
865 
866   // Compute the new bitset.
867   bitset new_bitset = type1->BitsetGlb() | type2->BitsetGlb();
868 
869   // Deal with ranges.
870   Type* range = None();
871   Type* range1 = type1->GetRange();
872   Type* range2 = type2->GetRange();
873   if (range1 != NULL && range2 != NULL) {
874     RangeType::Limits lims =
875         RangeType::Limits::Union(RangeType::Limits(range1->AsRange()),
876                                  RangeType::Limits(range2->AsRange()));
877     Type* union_range = RangeType::New(lims, zone);
878     range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
879   } else if (range1 != NULL) {
880     range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
881   } else if (range2 != NULL) {
882     range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
883   }
884   Type* bits = BitsetType::New(new_bitset);
885   result->Set(size++, bits);
886   if (!range->IsNone()) result->Set(size++, range);
887 
888   size = AddToUnion(type1, result, size, zone);
889   size = AddToUnion(type2, result, size, zone);
890   return NormalizeUnion(result_type, size, zone);
891 }
892 
893 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
894 // Return new size of [result].
AddToUnion(Type * type,UnionType * result,int size,Zone * zone)895 int Type::AddToUnion(Type* type, UnionType* result, int size, Zone* zone) {
896   if (type->IsBitset() || type->IsRange()) return size;
897   if (type->IsUnion()) {
898     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
899       size = AddToUnion(type->AsUnion()->Get(i), result, size, zone);
900     }
901     return size;
902   }
903   for (int i = 0; i < size; ++i) {
904     if (type->Is(result->Get(i))) return size;
905   }
906   result->Set(size++, type);
907   return size;
908 }
909 
NormalizeUnion(Type * union_type,int size,Zone * zone)910 Type* Type::NormalizeUnion(Type* union_type, int size, Zone* zone) {
911   UnionType* unioned = union_type->AsUnion();
912   DCHECK(size >= 1);
913   DCHECK(unioned->Get(0)->IsBitset());
914   // If the union has just one element, return it.
915   if (size == 1) {
916     return unioned->Get(0);
917   }
918   bitset bits = unioned->Get(0)->AsBitset();
919   // If the union only consists of a range, we can get rid of the union.
920   if (size == 2 && bits == BitsetType::kNone) {
921     if (unioned->Get(1)->IsRange()) {
922       return RangeType::New(unioned->Get(1)->AsRange()->Min(),
923                             unioned->Get(1)->AsRange()->Max(), zone);
924     }
925   }
926   unioned->Shrink(size);
927   SLOW_DCHECK(unioned->Wellformed());
928   return union_type;
929 }
930 
NumConstants()931 int Type::NumConstants() {
932   DisallowHeapAllocation no_allocation;
933   if (this->IsHeapConstant() || this->IsOtherNumberConstant()) {
934     return 1;
935   } else if (this->IsUnion()) {
936     int result = 0;
937     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
938       if (this->AsUnion()->Get(i)->IsHeapConstant()) ++result;
939     }
940     return result;
941   } else {
942     return 0;
943   }
944 }
945 
946 // -----------------------------------------------------------------------------
947 // Printing.
948 
Name(bitset bits)949 const char* BitsetType::Name(bitset bits) {
950   switch (bits) {
951 #define RETURN_NAMED_TYPE(type, value) \
952   case k##type:                        \
953     return #type;
954     PROPER_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
955     INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_TYPE)
956 #undef RETURN_NAMED_TYPE
957 
958     default:
959       return NULL;
960   }
961 }
962 
Print(std::ostream & os,bitset bits)963 void BitsetType::Print(std::ostream& os,  // NOLINT
964                        bitset bits) {
965   DisallowHeapAllocation no_allocation;
966   const char* name = Name(bits);
967   if (name != NULL) {
968     os << name;
969     return;
970   }
971 
972   // clang-format off
973   static const bitset named_bitsets[] = {
974 #define BITSET_CONSTANT(type, value) k##type,
975     INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
976     PROPER_BITSET_TYPE_LIST(BITSET_CONSTANT)
977 #undef BITSET_CONSTANT
978   };
979   // clang-format on
980 
981   bool is_first = true;
982   os << "(";
983   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
984     bitset subset = named_bitsets[i];
985     if ((bits & subset) == subset) {
986       if (!is_first) os << " | ";
987       is_first = false;
988       os << Name(subset);
989       bits -= subset;
990     }
991   }
992   DCHECK(bits == 0);
993   os << ")";
994 }
995 
PrintTo(std::ostream & os)996 void Type::PrintTo(std::ostream& os) {
997   DisallowHeapAllocation no_allocation;
998   if (this->IsBitset()) {
999     BitsetType::Print(os, this->AsBitset());
1000   } else if (this->IsHeapConstant()) {
1001     os << "HeapConstant(" << Brief(*this->AsHeapConstant()->Value()) << ")";
1002   } else if (this->IsOtherNumberConstant()) {
1003     os << "OtherNumberConstant(" << this->AsOtherNumberConstant()->Value()
1004        << ")";
1005   } else if (this->IsRange()) {
1006     std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1007     std::streamsize saved_precision = os.precision(0);
1008     os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1009        << ")";
1010     os.flags(saved_flags);
1011     os.precision(saved_precision);
1012   } else if (this->IsUnion()) {
1013     os << "(";
1014     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1015       Type* type_i = this->AsUnion()->Get(i);
1016       if (i > 0) os << " | ";
1017       type_i->PrintTo(os);
1018     }
1019     os << ")";
1020   } else if (this->IsTuple()) {
1021     os << "<";
1022     for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
1023       Type* type_i = this->AsTuple()->Element(i);
1024       if (i > 0) os << ", ";
1025       type_i->PrintTo(os);
1026     }
1027     os << ">";
1028   } else {
1029     UNREACHABLE();
1030   }
1031 }
1032 
1033 #ifdef DEBUG
Print()1034 void Type::Print() {
1035   OFStream os(stdout);
1036   PrintTo(os);
1037   os << std::endl;
1038 }
Print(bitset bits)1039 void BitsetType::Print(bitset bits) {
1040   OFStream os(stdout);
1041   Print(os, bits);
1042   os << std::endl;
1043 }
1044 #endif
1045 
SignedSmall()1046 BitsetType::bitset BitsetType::SignedSmall() {
1047   return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1048 }
1049 
UnsignedSmall()1050 BitsetType::bitset BitsetType::UnsignedSmall() {
1051   return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1052 }
1053 
1054 }  // namespace compiler
1055 }  // namespace internal
1056 }  // namespace v8
1057