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