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 "src/types.h"
6 
7 #include "src/ostreams.h"
8 #include "src/types-inl.h"
9 
10 namespace v8 {
11 namespace internal {
12 
13 
14 // NOTE: If code is marked as being a "shortcut", this means that removing
15 // the code won't affect the semantics of the surrounding function definition.
16 
17 
18 // -----------------------------------------------------------------------------
19 // Range-related helper functions.
20 
21 // The result may be invalid (max < min).
22 template<class Config>
Intersect(Limits lhs,Limits rhs)23 typename TypeImpl<Config>::Limits TypeImpl<Config>::Intersect(
24     Limits lhs, Limits rhs) {
25   DisallowHeapAllocation no_allocation;
26   Limits result(lhs);
27   if (lhs.min->Number() < rhs.min->Number()) result.min = rhs.min;
28   if (lhs.max->Number() > rhs.max->Number()) result.max = rhs.max;
29   return result;
30 }
31 
32 
33 template<class Config>
Union(Limits lhs,Limits rhs)34 typename TypeImpl<Config>::Limits TypeImpl<Config>::Union(
35     Limits lhs, Limits rhs) {
36   DisallowHeapAllocation no_allocation;
37   Limits result(lhs);
38   if (lhs.min->Number() > rhs.min->Number()) result.min = rhs.min;
39   if (lhs.max->Number() < rhs.max->Number()) result.max = rhs.max;
40   return result;
41 }
42 
43 
44 template<class Config>
Overlap(typename TypeImpl<Config>::RangeType * lhs,typename TypeImpl<Config>::RangeType * rhs)45 bool TypeImpl<Config>::Overlap(
46     typename TypeImpl<Config>::RangeType* lhs,
47     typename TypeImpl<Config>::RangeType* rhs) {
48   DisallowHeapAllocation no_allocation;
49   typename TypeImpl<Config>::Limits lim = Intersect(Limits(lhs), Limits(rhs));
50   return lim.min->Number() <= lim.max->Number();
51 }
52 
53 
54 template<class Config>
Contains(typename TypeImpl<Config>::RangeType * lhs,typename TypeImpl<Config>::RangeType * rhs)55 bool TypeImpl<Config>::Contains(
56     typename TypeImpl<Config>::RangeType* lhs,
57     typename TypeImpl<Config>::RangeType* rhs) {
58   DisallowHeapAllocation no_allocation;
59   return lhs->Min()->Number() <= rhs->Min()->Number()
60       && rhs->Max()->Number() <= lhs->Max()->Number();
61 }
62 
63 
64 template<class Config>
Contains(typename TypeImpl<Config>::RangeType * range,i::Object * val)65 bool TypeImpl<Config>::Contains(
66     typename TypeImpl<Config>::RangeType* range, i::Object* val) {
67   DisallowHeapAllocation no_allocation;
68   return IsInteger(val)
69       && range->Min()->Number() <= val->Number()
70       && val->Number() <= range->Max()->Number();
71 }
72 
73 
74 // -----------------------------------------------------------------------------
75 // Min and Max computation.
76 
77 template<class Config>
Min()78 double TypeImpl<Config>::Min() {
79   DCHECK(this->Is(Number()));
80   if (this->IsBitset()) return BitsetType::Min(this->AsBitset());
81   if (this->IsUnion()) {
82     double min = +V8_INFINITY;
83     for (int i = 0; i < this->AsUnion()->Length(); ++i) {
84       min = std::min(min, this->AsUnion()->Get(i)->Min());
85     }
86     return min;
87   }
88   if (this->IsRange()) return this->AsRange()->Min()->Number();
89   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
90   UNREACHABLE();
91   return 0;
92 }
93 
94 
95 template<class Config>
Max()96 double TypeImpl<Config>::Max() {
97   DCHECK(this->Is(Number()));
98   if (this->IsBitset()) return BitsetType::Max(this->AsBitset());
99   if (this->IsUnion()) {
100     double max = -V8_INFINITY;
101     for (int i = 0; i < this->AsUnion()->Length(); ++i) {
102       max = std::max(max, this->AsUnion()->Get(i)->Max());
103     }
104     return max;
105   }
106   if (this->IsRange()) return this->AsRange()->Max()->Number();
107   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
108   UNREACHABLE();
109   return 0;
110 }
111 
112 
113 // -----------------------------------------------------------------------------
114 // Glb and lub computation.
115 
116 
117 // The largest bitset subsumed by this type.
118 template<class Config>
119 typename TypeImpl<Config>::bitset
Glb(TypeImpl * type)120 TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
121   DisallowHeapAllocation no_allocation;
122   if (type->IsBitset()) {
123     return type->AsBitset();
124   } else if (type->IsUnion()) {
125     SLOW_DCHECK(type->AsUnion()->Wellformed());
126     return type->AsUnion()->Get(0)->BitsetGlb();  // Shortcut.
127     // (The remaining BitsetGlb's are None anyway).
128   } else {
129     return kNone;
130   }
131 }
132 
133 
134 // The smallest bitset subsuming this type.
135 template<class Config>
136 typename TypeImpl<Config>::bitset
Lub(TypeImpl * type)137 TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
138   DisallowHeapAllocation no_allocation;
139   if (type->IsBitset()) return type->AsBitset();
140   if (type->IsUnion()) {
141     int bitset = kNone;
142     for (int i = 0; i < type->AsUnion()->Length(); ++i) {
143       bitset |= type->AsUnion()->Get(i)->BitsetLub();
144     }
145     return bitset;
146   }
147   if (type->IsClass()) {
148     // Little hack to avoid the need for a region for handlification here...
149     return Config::is_class(type) ? Lub(*Config::as_class(type)) :
150         type->AsClass()->Bound(NULL)->AsBitset();
151   }
152   if (type->IsConstant()) return type->AsConstant()->Bound()->AsBitset();
153   if (type->IsRange()) return type->AsRange()->BitsetLub();
154   if (type->IsContext()) return kInternal & kTaggedPtr;
155   if (type->IsArray()) return kArray;
156   if (type->IsFunction()) return kFunction;
157   UNREACHABLE();
158   return kNone;
159 }
160 
161 
162 template<class Config>
163 typename TypeImpl<Config>::bitset
Lub(i::Map * map)164 TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
165   DisallowHeapAllocation no_allocation;
166   switch (map->instance_type()) {
167     case STRING_TYPE:
168     case ONE_BYTE_STRING_TYPE:
169     case CONS_STRING_TYPE:
170     case CONS_ONE_BYTE_STRING_TYPE:
171     case SLICED_STRING_TYPE:
172     case SLICED_ONE_BYTE_STRING_TYPE:
173     case EXTERNAL_STRING_TYPE:
174     case EXTERNAL_ONE_BYTE_STRING_TYPE:
175     case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
176     case SHORT_EXTERNAL_STRING_TYPE:
177     case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
178     case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
179       return kOtherString;
180     case INTERNALIZED_STRING_TYPE:
181     case ONE_BYTE_INTERNALIZED_STRING_TYPE:
182     case EXTERNAL_INTERNALIZED_STRING_TYPE:
183     case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
184     case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
185     case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
186     case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
187     case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
188       return kInternalizedString;
189     case SYMBOL_TYPE:
190       return kSymbol;
191     case ODDBALL_TYPE: {
192       Heap* heap = map->GetHeap();
193       if (map == heap->undefined_map()) return kUndefined;
194       if (map == heap->null_map()) return kNull;
195       if (map == heap->boolean_map()) return kBoolean;
196       DCHECK(map == heap->the_hole_map() ||
197              map == heap->uninitialized_map() ||
198              map == heap->no_interceptor_result_sentinel_map() ||
199              map == heap->termination_exception_map() ||
200              map == heap->arguments_marker_map());
201       return kInternal & kTaggedPtr;
202     }
203     case HEAP_NUMBER_TYPE:
204       return kNumber & kTaggedPtr;
205     case JS_VALUE_TYPE:
206     case JS_DATE_TYPE:
207     case JS_OBJECT_TYPE:
208     case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
209     case JS_GENERATOR_OBJECT_TYPE:
210     case JS_MODULE_TYPE:
211     case JS_GLOBAL_OBJECT_TYPE:
212     case JS_BUILTINS_OBJECT_TYPE:
213     case JS_GLOBAL_PROXY_TYPE:
214     case JS_ARRAY_BUFFER_TYPE:
215     case JS_TYPED_ARRAY_TYPE:
216     case JS_DATA_VIEW_TYPE:
217     case JS_SET_TYPE:
218     case JS_MAP_TYPE:
219     case JS_SET_ITERATOR_TYPE:
220     case JS_MAP_ITERATOR_TYPE:
221     case JS_WEAK_MAP_TYPE:
222     case JS_WEAK_SET_TYPE:
223       if (map->is_undetectable()) return kUndetectable;
224       return kOtherObject;
225     case JS_ARRAY_TYPE:
226       return kArray;
227     case JS_FUNCTION_TYPE:
228       return kFunction;
229     case JS_REGEXP_TYPE:
230       return kRegExp;
231     case JS_PROXY_TYPE:
232     case JS_FUNCTION_PROXY_TYPE:
233       return kProxy;
234     case MAP_TYPE:
235       // When compiling stub templates, the meta map is used as a place holder
236       // for the actual map with which the template is later instantiated.
237       // We treat it as a kind of type variable whose upper bound is Any.
238       // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
239       // we must exclude Undetectable here. This makes no sense, really,
240       // because it means that the template isn't actually parametric.
241       // Also, it doesn't apply elsewhere. 8-(
242       // We ought to find a cleaner solution for compiling stubs parameterised
243       // over type or class variables, esp ones with bounds...
244       return kDetectable;
245     case DECLARED_ACCESSOR_INFO_TYPE:
246     case EXECUTABLE_ACCESSOR_INFO_TYPE:
247     case SHARED_FUNCTION_INFO_TYPE:
248     case ACCESSOR_PAIR_TYPE:
249     case FIXED_ARRAY_TYPE:
250     case FOREIGN_TYPE:
251     case CODE_TYPE:
252       return kInternal & kTaggedPtr;
253     default:
254       UNREACHABLE();
255       return kNone;
256   }
257 }
258 
259 
260 template<class Config>
261 typename TypeImpl<Config>::bitset
Lub(i::Object * value)262 TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
263   DisallowHeapAllocation no_allocation;
264   if (value->IsNumber()) {
265     return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
266   }
267   return Lub(i::HeapObject::cast(value)->map());
268 }
269 
270 
271 template<class Config>
272 typename TypeImpl<Config>::bitset
Lub(double value)273 TypeImpl<Config>::BitsetType::Lub(double value) {
274   DisallowHeapAllocation no_allocation;
275   if (i::IsMinusZero(value)) return kMinusZero;
276   if (std::isnan(value)) return kNaN;
277   if (IsUint32Double(value)) return Lub(FastD2UI(value));
278   if (IsInt32Double(value)) return Lub(FastD2I(value));
279   return kOtherNumber;
280 }
281 
282 
283 template<class Config>
284 typename TypeImpl<Config>::bitset
Lub(int32_t value)285 TypeImpl<Config>::BitsetType::Lub(int32_t value) {
286   DisallowHeapAllocation no_allocation;
287   if (value >= 0x40000000) {
288     return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
289   }
290   if (value >= 0) return kUnsignedSmall;
291   if (value >= -0x40000000) return kOtherSignedSmall;
292   return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall;
293 }
294 
295 
296 template<class Config>
297 typename TypeImpl<Config>::bitset
Lub(uint32_t value)298 TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
299   DisallowHeapAllocation no_allocation;
300   if (value >= 0x80000000u) return kOtherUnsigned32;
301   if (value >= 0x40000000u) {
302     return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
303   }
304   return kUnsignedSmall;
305 }
306 
307 
308 // Minimum values of regular numeric bitsets when SmiValuesAre31Bits.
309 template<class Config>
310 const typename TypeImpl<Config>::BitsetType::BitsetMin
311 TypeImpl<Config>::BitsetType::BitsetMins31[] = {
312     {kOtherNumber, -V8_INFINITY},
313     {kOtherSigned32, kMinInt},
314     {kOtherSignedSmall, -0x40000000},
315     {kUnsignedSmall, 0},
316     {kOtherUnsigned31, 0x40000000},
317     {kOtherUnsigned32, 0x80000000},
318     {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}
319 };
320 
321 
322 // Minimum values of regular numeric bitsets when SmiValuesAre32Bits.
323 // OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h).
324 template<class Config>
325 const typename TypeImpl<Config>::BitsetType::BitsetMin
326 TypeImpl<Config>::BitsetType::BitsetMins32[] = {
327     {kOtherNumber, -V8_INFINITY},
328     {kOtherSignedSmall, kMinInt},
329     {kUnsignedSmall, 0},
330     {kOtherUnsigned32, 0x80000000},
331     {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}
332 };
333 
334 
335 template<class Config>
336 typename TypeImpl<Config>::bitset
Lub(Limits lim)337 TypeImpl<Config>::BitsetType::Lub(Limits lim) {
338   DisallowHeapAllocation no_allocation;
339   double min = lim.min->Number();
340   double max = lim.max->Number();
341   int lub = kNone;
342   const BitsetMin* mins = BitsetMins();
343 
344   for (size_t i = 1; i < BitsetMinsSize(); ++i) {
345     if (min < mins[i].min) {
346       lub |= mins[i-1].bits;
347       if (max < mins[i].min) return lub;
348     }
349   }
350   return lub |= mins[BitsetMinsSize()-1].bits;
351 }
352 
353 
354 template<class Config>
Min(bitset bits)355 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
356   DisallowHeapAllocation no_allocation;
357   DCHECK(Is(bits, kNumber));
358   const BitsetMin* mins = BitsetMins();
359   bool mz = SEMANTIC(bits & kMinusZero);
360   for (size_t i = 0; i < BitsetMinsSize(); ++i) {
361     if (Is(SEMANTIC(mins[i].bits), bits)) {
362       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
363     }
364   }
365   if (mz) return 0;
366   return base::OS::nan_value();
367 }
368 
369 
370 template<class Config>
Max(bitset bits)371 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
372   DisallowHeapAllocation no_allocation;
373   DCHECK(Is(bits, kNumber));
374   const BitsetMin* mins = BitsetMins();
375   bool mz = bits & kMinusZero;
376   if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) {
377     return +V8_INFINITY;
378   }
379   for (size_t i = BitsetMinsSize()-1; i-- > 0; ) {
380     if (Is(SEMANTIC(mins[i].bits), bits)) {
381       return mz ?
382           std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
383     }
384   }
385   if (mz) return 0;
386   return base::OS::nan_value();
387 }
388 
389 
390 // -----------------------------------------------------------------------------
391 // Predicates.
392 
393 
394 template<class Config>
SimplyEquals(TypeImpl * that)395 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) {
396   DisallowHeapAllocation no_allocation;
397   if (this->IsClass()) {
398     return that->IsClass()
399         && *this->AsClass()->Map() == *that->AsClass()->Map();
400   }
401   if (this->IsConstant()) {
402     return that->IsConstant()
403         && *this->AsConstant()->Value() == *that->AsConstant()->Value();
404   }
405   if (this->IsContext()) {
406     return that->IsContext()
407         && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
408   }
409   if (this->IsArray()) {
410     return that->IsArray()
411         && this->AsArray()->Element()->Equals(that->AsArray()->Element());
412   }
413   if (this->IsFunction()) {
414     if (!that->IsFunction()) return false;
415     FunctionType* this_fun = this->AsFunction();
416     FunctionType* that_fun = that->AsFunction();
417     if (this_fun->Arity() != that_fun->Arity() ||
418         !this_fun->Result()->Equals(that_fun->Result()) ||
419         !this_fun->Receiver()->Equals(that_fun->Receiver())) {
420       return false;
421     }
422     for (int i = 0; i < this_fun->Arity(); ++i) {
423       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
424     }
425     return true;
426   }
427   UNREACHABLE();
428   return false;
429 }
430 
431 
432 // Check if [this] <= [that].
433 template<class Config>
SlowIs(TypeImpl * that)434 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
435   DisallowHeapAllocation no_allocation;
436 
437   if (that->IsBitset()) {
438     return BitsetType::Is(this->BitsetLub(), that->AsBitset());
439   }
440   if (this->IsBitset()) {
441     return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
442   }
443 
444   // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
445   if (this->IsUnion()) {
446     UnionHandle unioned = handle(this->AsUnion());
447     for (int i = 0; i < unioned->Length(); ++i) {
448       if (!unioned->Get(i)->Is(that)) return false;
449     }
450     return true;
451   }
452 
453   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
454   if (that->IsUnion()) {
455     for (int i = 0; i < that->AsUnion()->Length(); ++i) {
456       if (this->Is(that->AsUnion()->Get(i))) return true;
457       if (i > 1 && this->IsRange()) return false;  // Shortcut.
458     }
459     return false;
460   }
461 
462   if (that->IsRange()) {
463     return (this->IsRange() && Contains(that->AsRange(), this->AsRange()))
464         || (this->IsConstant() &&
465             Contains(that->AsRange(), *this->AsConstant()->Value()));
466   }
467   if (this->IsRange()) return false;
468   return this->SimplyEquals(that);
469 }
470 
471 
472 template<class Config>
NowIs(TypeImpl * that)473 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
474   DisallowHeapAllocation no_allocation;
475 
476   // TODO(rossberg): this is incorrect for
477   //   Union(Constant(V), T)->NowIs(Class(M))
478   // but fuzzing does not cover that!
479   if (this->IsConstant()) {
480     i::Object* object = *this->AsConstant()->Value();
481     if (object->IsHeapObject()) {
482       i::Map* map = i::HeapObject::cast(object)->map();
483       for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
484         if (*it.Current() == map) return true;
485       }
486     }
487   }
488   return this->Is(that);
489 }
490 
491 
492 // Check if [this] contains only (currently) stable classes.
493 template<class Config>
NowStable()494 bool TypeImpl<Config>::NowStable() {
495   DisallowHeapAllocation no_allocation;
496   for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
497     if (!it.Current()->is_stable()) return false;
498   }
499   return true;
500 }
501 
502 
503 // Check if [this] and [that] overlap.
504 template<class Config>
Maybe(TypeImpl * that)505 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
506   DisallowHeapAllocation no_allocation;
507 
508   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
509   if (this->IsUnion()) {
510     UnionHandle unioned = handle(this->AsUnion());
511     for (int i = 0; i < unioned->Length(); ++i) {
512       if (unioned->Get(i)->Maybe(that)) return true;
513     }
514     return false;
515   }
516 
517   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
518   if (that->IsUnion()) {
519     for (int i = 0; i < that->AsUnion()->Length(); ++i) {
520       if (this->Maybe(that->AsUnion()->Get(i))) return true;
521     }
522     return false;
523   }
524 
525   if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
526     return false;
527   if (this->IsBitset() || that->IsBitset()) return true;
528 
529   if (this->IsClass() != that->IsClass()) return true;
530 
531   if (this->IsRange()) {
532     if (that->IsConstant()) {
533       return Contains(this->AsRange(), *that->AsConstant()->Value());
534     }
535     return that->IsRange() && Overlap(this->AsRange(), that->AsRange());
536   }
537   if (that->IsRange()) {
538     if (this->IsConstant()) {
539       return Contains(that->AsRange(), *this->AsConstant()->Value());
540     }
541     return this->IsRange() && Overlap(this->AsRange(), that->AsRange());
542   }
543 
544   return this->SimplyEquals(that);
545 }
546 
547 
548 // Return the range in [this], or [NULL].
549 template<class Config>
GetRange()550 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
551   DisallowHeapAllocation no_allocation;
552   if (this->IsRange()) return this->AsRange();
553   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
554     return this->AsUnion()->Get(1)->AsRange();
555   }
556   return NULL;
557 }
558 
559 
560 template<class Config>
Contains(i::Object * value)561 bool TypeImpl<Config>::Contains(i::Object* value) {
562   DisallowHeapAllocation no_allocation;
563   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
564     if (*it.Current() == value) return true;
565   }
566   if (IsInteger(value)) {
567     RangeType* range = this->GetRange();
568     if (range != NULL && Contains(range, value)) return true;
569   }
570   return BitsetType::New(BitsetType::Lub(value))->Is(this);
571 }
572 
573 
574 template<class Config>
Wellformed()575 bool TypeImpl<Config>::UnionType::Wellformed() {
576   DisallowHeapAllocation no_allocation;
577   // This checks the invariants of the union representation:
578   // 1. There are at least two elements.
579   // 2. At most one element is a bitset, and it must be the first one.
580   // 3. At most one element is a range, and it must be the second one
581   //    (even when the first element is not a bitset).
582   // 4. No element is itself a union.
583   // 5. No element is a subtype of any other.
584   DCHECK(this->Length() >= 2);  // (1)
585   for (int i = 0; i < this->Length(); ++i) {
586     if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2)
587     if (i != 1) DCHECK(!this->Get(i)->IsRange());  // (3)
588     DCHECK(!this->Get(i)->IsUnion());  // (4)
589     for (int j = 0; j < this->Length(); ++j) {
590       if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
591     }
592   }
593   return true;
594 }
595 
596 
597 // -----------------------------------------------------------------------------
598 // Union and intersection
599 
600 
AddIsSafe(int x,int y)601 static bool AddIsSafe(int x, int y) {
602   return x >= 0 ?
603       y <= std::numeric_limits<int>::max() - x :
604       y >= std::numeric_limits<int>::min() - x;
605 }
606 
607 
608 template<class Config>
Intersect(TypeHandle type1,TypeHandle type2,Region * region)609 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
610     TypeHandle type1, TypeHandle type2, Region* region) {
611   bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
612   if (!BitsetType::IsInhabited(bits)) bits = BitsetType::kNone;
613 
614   // Fast case: bit sets.
615   if (type1->IsBitset() && type2->IsBitset()) {
616     return BitsetType::New(bits, region);
617   }
618 
619   // Fast case: top or bottom types.
620   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
621   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
622 
623   // Semi-fast case.
624   if (type1->Is(type2)) return type1;
625   if (type2->Is(type1)) return type2;
626 
627   // Slow case: create union.
628   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
629   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
630   if (!AddIsSafe(size1, size2)) return Any(region);
631   int size = size1 + size2;
632   if (!AddIsSafe(size, 2)) return Any(region);
633   size += 2;
634   UnionHandle result = UnionType::New(size, region);
635   size = 0;
636 
637   // Deal with bitsets.
638   result->Set(size++, BitsetType::New(bits, region));
639 
640   // Deal with ranges.
641   TypeHandle range = None(region);
642   RangeType* range1 = type1->GetRange();
643   RangeType* range2 = type2->GetRange();
644   if (range1 != NULL && range2 != NULL) {
645     Limits lim = Intersect(Limits(range1), Limits(range2));
646     if (lim.min->Number() <= lim.max->Number()) {
647       range = RangeType::New(lim, region);
648     }
649   }
650   result->Set(size++, range);
651 
652   size = IntersectAux(type1, type2, result, size, region);
653   return NormalizeUnion(result, size);
654 }
655 
656 
657 template<class Config>
UpdateRange(RangeHandle range,UnionHandle result,int size,Region * region)658 int TypeImpl<Config>::UpdateRange(
659     RangeHandle range, UnionHandle result, int size, Region* region) {
660   TypeHandle old_range = result->Get(1);
661   DCHECK(old_range->IsRange() || old_range->IsNone());
662   if (range->Is(old_range)) return size;
663   if (!old_range->Is(range->unhandle())) {
664     range = RangeType::New(
665         Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region);
666   }
667   result->Set(1, range);
668 
669   // Remove any components that just got subsumed.
670   for (int i = 2; i < size; ) {
671     if (result->Get(i)->Is(range->unhandle())) {
672       result->Set(i, result->Get(--size));
673     } else {
674       ++i;
675     }
676   }
677   return size;
678 }
679 
680 
681 template<class Config>
IntersectAux(TypeHandle lhs,TypeHandle rhs,UnionHandle result,int size,Region * region)682 int TypeImpl<Config>::IntersectAux(
683     TypeHandle lhs, TypeHandle rhs,
684     UnionHandle result, int size, Region* region) {
685   if (lhs->IsUnion()) {
686     for (int i = 0; i < lhs->AsUnion()->Length(); ++i) {
687       size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region);
688     }
689     return size;
690   }
691   if (rhs->IsUnion()) {
692     for (int i = 0; i < rhs->AsUnion()->Length(); ++i) {
693       size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region);
694     }
695     return size;
696   }
697 
698   if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
699     return size;
700   }
701 
702   if (lhs->IsRange()) {
703     if (rhs->IsBitset() || rhs->IsClass()) {
704       return UpdateRange(
705           Config::template cast<RangeType>(lhs), result, size, region);
706     }
707     if (rhs->IsConstant() &&
708         Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) {
709       return AddToUnion(rhs, result, size, region);
710     }
711     return size;
712   }
713   if (rhs->IsRange()) {
714     if (lhs->IsBitset() || lhs->IsClass()) {
715       return UpdateRange(
716           Config::template cast<RangeType>(rhs), result, size, region);
717     }
718     if (lhs->IsConstant() &&
719         Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) {
720       return AddToUnion(lhs, result, size, region);
721     }
722     return size;
723   }
724 
725   if (lhs->IsBitset() || rhs->IsBitset()) {
726     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
727   }
728   if (lhs->IsClass() != rhs->IsClass()) {
729     return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region);
730   }
731   if (lhs->SimplyEquals(rhs->unhandle())) {
732     return AddToUnion(lhs, result, size, region);
733   }
734   return size;
735 }
736 
737 
738 template<class Config>
Union(TypeHandle type1,TypeHandle type2,Region * region)739 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
740     TypeHandle type1, TypeHandle type2, Region* region) {
741 
742   // Fast case: bit sets.
743   if (type1->IsBitset() && type2->IsBitset()) {
744     return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
745   }
746 
747   // Fast case: top or bottom types.
748   if (type1->IsAny() || type2->IsNone()) return type1;
749   if (type2->IsAny() || type1->IsNone()) return type2;
750 
751   // Semi-fast case.
752   if (type1->Is(type2)) return type2;
753   if (type2->Is(type1)) return type1;
754 
755   // Slow case: create union.
756   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
757   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
758   if (!AddIsSafe(size1, size2)) return Any(region);
759   int size = size1 + size2;
760   if (!AddIsSafe(size, 2)) return Any(region);
761   size += 2;
762   UnionHandle result = UnionType::New(size, region);
763   size = 0;
764 
765   // Deal with bitsets.
766   TypeHandle bits = BitsetType::New(
767       type1->BitsetGlb() | type2->BitsetGlb(), region);
768   result->Set(size++, bits);
769 
770   // Deal with ranges.
771   TypeHandle range = None(region);
772   RangeType* range1 = type1->GetRange();
773   RangeType* range2 = type2->GetRange();
774   if (range1 != NULL && range2 != NULL) {
775     range = RangeType::New(Union(Limits(range1), Limits(range2)), region);
776   } else if (range1 != NULL) {
777     range = handle(range1);
778   } else if (range2 != NULL) {
779     range = handle(range2);
780   }
781   result->Set(size++, range);
782 
783   size = AddToUnion(type1, result, size, region);
784   size = AddToUnion(type2, result, size, region);
785   return NormalizeUnion(result, size);
786 }
787 
788 
789 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
790 // Return new size of [result].
791 template<class Config>
AddToUnion(TypeHandle type,UnionHandle result,int size,Region * region)792 int TypeImpl<Config>::AddToUnion(
793     TypeHandle type, UnionHandle result, int size, Region* region) {
794   if (type->IsBitset() || type->IsRange()) return size;
795   if (type->IsUnion()) {
796     for (int i = 0; i < type->AsUnion()->Length(); ++i) {
797       size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
798     }
799     return size;
800   }
801   for (int i = 0; i < size; ++i) {
802     if (type->Is(result->Get(i))) return size;
803   }
804   result->Set(size++, type);
805   return size;
806 }
807 
808 
809 template<class Config>
NormalizeUnion(UnionHandle unioned,int size)810 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
811     UnionHandle unioned, int size) {
812   DCHECK(size >= 2);
813   // If range is subsumed by bitset, use its place for a different type.
814   if (unioned->Get(1)->Is(unioned->Get(0))) {
815     unioned->Set(1, unioned->Get(--size));
816   }
817   // If bitset is None, use its place for a different type.
818   if (size >= 2 && unioned->Get(0)->IsNone()) {
819     unioned->Set(0, unioned->Get(--size));
820   }
821   if (size == 1) return unioned->Get(0);
822   unioned->Shrink(size);
823   SLOW_DCHECK(unioned->Wellformed());
824   return unioned;
825 }
826 
827 
828 // -----------------------------------------------------------------------------
829 // Iteration.
830 
831 template<class Config>
NumClasses()832 int TypeImpl<Config>::NumClasses() {
833   DisallowHeapAllocation no_allocation;
834   if (this->IsClass()) {
835     return 1;
836   } else if (this->IsUnion()) {
837     UnionHandle unioned = handle(this->AsUnion());
838     int result = 0;
839     for (int i = 0; i < unioned->Length(); ++i) {
840       if (unioned->Get(i)->IsClass()) ++result;
841     }
842     return result;
843   } else {
844     return 0;
845   }
846 }
847 
848 
849 template<class Config>
NumConstants()850 int TypeImpl<Config>::NumConstants() {
851   DisallowHeapAllocation no_allocation;
852   if (this->IsConstant()) {
853     return 1;
854   } else if (this->IsUnion()) {
855     UnionHandle unioned = handle(this->AsUnion());
856     int result = 0;
857     for (int i = 0; i < unioned->Length(); ++i) {
858       if (unioned->Get(i)->IsConstant()) ++result;
859     }
860     return result;
861   } else {
862     return 0;
863   }
864 }
865 
866 
867 template<class Config> template<class T>
868 typename TypeImpl<Config>::TypeHandle
get_type()869 TypeImpl<Config>::Iterator<T>::get_type() {
870   DCHECK(!Done());
871   return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
872 }
873 
874 
875 // C++ cannot specialise nested templates, so we have to go through this
876 // contortion with an auxiliary template to simulate it.
877 template<class Config, class T>
878 struct TypeImplIteratorAux {
879   static bool matches(typename TypeImpl<Config>::TypeHandle type);
880   static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
881 };
882 
883 template<class Config>
884 struct TypeImplIteratorAux<Config, i::Map> {
matchesv8::internal::TypeImplIteratorAux885   static bool matches(typename TypeImpl<Config>::TypeHandle type) {
886     return type->IsClass();
887   }
currentv8::internal::TypeImplIteratorAux888   static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
889     return type->AsClass()->Map();
890   }
891 };
892 
893 template<class Config>
894 struct TypeImplIteratorAux<Config, i::Object> {
matchesv8::internal::TypeImplIteratorAux895   static bool matches(typename TypeImpl<Config>::TypeHandle type) {
896     return type->IsConstant();
897   }
currentv8::internal::TypeImplIteratorAux898   static i::Handle<i::Object> current(
899       typename TypeImpl<Config>::TypeHandle type) {
900     return type->AsConstant()->Value();
901   }
902 };
903 
904 template<class Config> template<class T>
matches(TypeHandle type)905 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
906   return TypeImplIteratorAux<Config, T>::matches(type);
907 }
908 
909 template<class Config> template<class T>
Current()910 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
911   return TypeImplIteratorAux<Config, T>::current(get_type());
912 }
913 
914 
915 template<class Config> template<class T>
Advance()916 void TypeImpl<Config>::Iterator<T>::Advance() {
917   DisallowHeapAllocation no_allocation;
918   ++index_;
919   if (type_->IsUnion()) {
920     UnionHandle unioned = Config::template cast<UnionType>(type_);
921     for (; index_ < unioned->Length(); ++index_) {
922       if (matches(unioned->Get(index_))) return;
923     }
924   } else if (index_ == 0 && matches(type_)) {
925     return;
926   }
927   index_ = -1;
928 }
929 
930 
931 // -----------------------------------------------------------------------------
932 // Conversion between low-level representations.
933 
934 template<class Config>
935 template<class OtherType>
Convert(typename OtherType::TypeHandle type,Region * region)936 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
937     typename OtherType::TypeHandle type, Region* region) {
938   if (type->IsBitset()) {
939     return BitsetType::New(type->AsBitset(), region);
940   } else if (type->IsClass()) {
941     return ClassType::New(type->AsClass()->Map(), region);
942   } else if (type->IsConstant()) {
943     return ConstantType::New(type->AsConstant()->Value(), region);
944   } else if (type->IsRange()) {
945     return RangeType::New(
946         type->AsRange()->Min(), type->AsRange()->Max(), region);
947   } else if (type->IsContext()) {
948     TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
949     return ContextType::New(outer, region);
950   } else if (type->IsUnion()) {
951     int length = type->AsUnion()->Length();
952     UnionHandle unioned = UnionType::New(length, region);
953     for (int i = 0; i < length; ++i) {
954       TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
955       unioned->Set(i, t);
956     }
957     return unioned;
958   } else if (type->IsArray()) {
959     TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
960     return ArrayType::New(element, region);
961   } else if (type->IsFunction()) {
962     TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
963     TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
964     FunctionHandle function = FunctionType::New(
965         res, rcv, type->AsFunction()->Arity(), region);
966     for (int i = 0; i < function->Arity(); ++i) {
967       TypeHandle param = Convert<OtherType>(
968           type->AsFunction()->Parameter(i), region);
969       function->InitParameter(i, param);
970     }
971     return function;
972   } else {
973     UNREACHABLE();
974     return None(region);
975   }
976 }
977 
978 
979 // -----------------------------------------------------------------------------
980 // Printing.
981 
982 template<class Config>
Name(bitset bits)983 const char* TypeImpl<Config>::BitsetType::Name(bitset bits) {
984   switch (bits) {
985     case REPRESENTATION(kAny): return "Any";
986     #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
987     case REPRESENTATION(k##type): return #type;
988     REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
989     #undef RETURN_NAMED_REPRESENTATION_TYPE
990 
991     #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
992     case SEMANTIC(k##type): return #type;
993     SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
994     #undef RETURN_NAMED_SEMANTIC_TYPE
995 
996     default:
997       return NULL;
998   }
999 }
1000 
1001 
1002 template <class Config>
Print(OStream & os,bitset bits)1003 void TypeImpl<Config>::BitsetType::Print(OStream& os,  // NOLINT
1004                                          bitset bits) {
1005   DisallowHeapAllocation no_allocation;
1006   const char* name = Name(bits);
1007   if (name != NULL) {
1008     os << name;
1009     return;
1010   }
1011 
1012   static const bitset named_bitsets[] = {
1013 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
1014       REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
1015 #undef BITSET_CONSTANT
1016 
1017 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
1018       SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
1019 #undef BITSET_CONSTANT
1020   };
1021 
1022   bool is_first = true;
1023   os << "(";
1024   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1025     bitset subset = named_bitsets[i];
1026     if ((bits & subset) == subset) {
1027       if (!is_first) os << " | ";
1028       is_first = false;
1029       os << Name(subset);
1030       bits -= subset;
1031     }
1032   }
1033   DCHECK(bits == 0);
1034   os << ")";
1035 }
1036 
1037 
1038 template <class Config>
PrintTo(OStream & os,PrintDimension dim)1039 void TypeImpl<Config>::PrintTo(OStream& os, PrintDimension dim) {  // NOLINT
1040   DisallowHeapAllocation no_allocation;
1041   if (dim != REPRESENTATION_DIM) {
1042     if (this->IsBitset()) {
1043       BitsetType::Print(os, SEMANTIC(this->AsBitset()));
1044     } else if (this->IsClass()) {
1045       os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1046       BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
1047       os << ")";
1048     } else if (this->IsConstant()) {
1049       os << "Constant(" << static_cast<void*>(*this->AsConstant()->Value())
1050          << ")";
1051     } else if (this->IsRange()) {
1052       os << "Range(" << this->AsRange()->Min()->Number()
1053          << ", " << this->AsRange()->Max()->Number() << ")";
1054     } else if (this->IsContext()) {
1055       os << "Context(";
1056       this->AsContext()->Outer()->PrintTo(os, dim);
1057       os << ")";
1058     } else if (this->IsUnion()) {
1059       os << "(";
1060       UnionHandle unioned = handle(this->AsUnion());
1061       for (int i = 0; i < unioned->Length(); ++i) {
1062         TypeHandle type_i = unioned->Get(i);
1063         if (i > 0) os << " | ";
1064         type_i->PrintTo(os, dim);
1065       }
1066       os << ")";
1067     } else if (this->IsArray()) {
1068       os << "Array(";
1069       AsArray()->Element()->PrintTo(os, dim);
1070       os << ")";
1071     } else if (this->IsFunction()) {
1072       if (!this->AsFunction()->Receiver()->IsAny()) {
1073         this->AsFunction()->Receiver()->PrintTo(os, dim);
1074         os << ".";
1075       }
1076       os << "(";
1077       for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1078         if (i > 0) os << ", ";
1079         this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1080       }
1081       os << ")->";
1082       this->AsFunction()->Result()->PrintTo(os, dim);
1083     } else {
1084       UNREACHABLE();
1085     }
1086   }
1087   if (dim == BOTH_DIMS) os << "/";
1088   if (dim != SEMANTIC_DIM) {
1089     BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
1090   }
1091 }
1092 
1093 
1094 #ifdef DEBUG
1095 template <class Config>
Print()1096 void TypeImpl<Config>::Print() {
1097   OFStream os(stdout);
1098   PrintTo(os);
1099   os << endl;
1100 }
1101 template <class Config>
Print(bitset bits)1102 void TypeImpl<Config>::BitsetType::Print(bitset bits) {
1103   OFStream os(stdout);
1104   Print(os, bits);
1105   os << endl;
1106 }
1107 #endif
1108 
1109 
1110 // -----------------------------------------------------------------------------
1111 // Instantiations.
1112 
1113 template class TypeImpl<ZoneTypeConfig>;
1114 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
1115 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
1116 
1117 template class TypeImpl<HeapTypeConfig>;
1118 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
1119 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
1120 
1121 template TypeImpl<ZoneTypeConfig>::TypeHandle
1122   TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
1123     TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
1124 template TypeImpl<HeapTypeConfig>::TypeHandle
1125   TypeImpl<HeapTypeConfig>::Convert<Type>(
1126     TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
1127 
1128 } }  // namespace v8::internal
1129