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/ast/ast-types.h"
8 
9 #include "src/handles-inl.h"
10 #include "src/ostreams.h"
11 
12 namespace v8 {
13 namespace internal {
14 
15 // NOTE: If code is marked as being a "shortcut", this means that removing
16 // the code won't affect the semantics of the surrounding function definition.
17 
18 // static
IsInteger(i::Object * x)19 bool AstType::IsInteger(i::Object* x) {
20   return x->IsNumber() && AstType::IsInteger(x->Number());
21 }
22 
23 // -----------------------------------------------------------------------------
24 // Range-related helper functions.
25 
IsEmpty()26 bool AstRangeType::Limits::IsEmpty() { return this->min > this->max; }
27 
Intersect(Limits lhs,Limits rhs)28 AstRangeType::Limits AstRangeType::Limits::Intersect(Limits lhs, Limits rhs) {
29   DisallowHeapAllocation no_allocation;
30   Limits result(lhs);
31   if (lhs.min < rhs.min) result.min = rhs.min;
32   if (lhs.max > rhs.max) result.max = rhs.max;
33   return result;
34 }
35 
Union(Limits lhs,Limits rhs)36 AstRangeType::Limits AstRangeType::Limits::Union(Limits lhs, Limits rhs) {
37   DisallowHeapAllocation no_allocation;
38   if (lhs.IsEmpty()) return rhs;
39   if (rhs.IsEmpty()) return lhs;
40   Limits result(lhs);
41   if (lhs.min > rhs.min) result.min = rhs.min;
42   if (lhs.max < rhs.max) result.max = rhs.max;
43   return result;
44 }
45 
Overlap(AstRangeType * lhs,AstRangeType * rhs)46 bool AstType::Overlap(AstRangeType* lhs, AstRangeType* rhs) {
47   DisallowHeapAllocation no_allocation;
48   return !AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs),
49                                           AstRangeType::Limits(rhs))
50               .IsEmpty();
51 }
52 
Contains(AstRangeType * lhs,AstRangeType * rhs)53 bool AstType::Contains(AstRangeType* lhs, AstRangeType* rhs) {
54   DisallowHeapAllocation no_allocation;
55   return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
56 }
57 
Contains(AstRangeType * lhs,AstConstantType * rhs)58 bool AstType::Contains(AstRangeType* lhs, AstConstantType* rhs) {
59   DisallowHeapAllocation no_allocation;
60   return IsInteger(*rhs->Value()) && lhs->Min() <= rhs->Value()->Number() &&
61          rhs->Value()->Number() <= lhs->Max();
62 }
63 
Contains(AstRangeType * range,i::Object * val)64 bool AstType::Contains(AstRangeType* range, i::Object* val) {
65   DisallowHeapAllocation no_allocation;
66   return IsInteger(val) && range->Min() <= val->Number() &&
67          val->Number() <= range->Max();
68 }
69 
70 // -----------------------------------------------------------------------------
71 // Min and Max computation.
72 
Min()73 double AstType::Min() {
74   DCHECK(this->SemanticIs(Number()));
75   if (this->IsBitset()) return AstBitsetType::Min(this->AsBitset());
76   if (this->IsUnion()) {
77     double min = +V8_INFINITY;
78     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
79       min = std::min(min, this->AsUnion()->Get(i)->Min());
80     }
81     return min;
82   }
83   if (this->IsRange()) return this->AsRange()->Min();
84   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
85   UNREACHABLE();
86   return 0;
87 }
88 
Max()89 double AstType::Max() {
90   DCHECK(this->SemanticIs(Number()));
91   if (this->IsBitset()) return AstBitsetType::Max(this->AsBitset());
92   if (this->IsUnion()) {
93     double max = -V8_INFINITY;
94     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
95       max = std::max(max, this->AsUnion()->Get(i)->Max());
96     }
97     return max;
98   }
99   if (this->IsRange()) return this->AsRange()->Max();
100   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
101   UNREACHABLE();
102   return 0;
103 }
104 
105 // -----------------------------------------------------------------------------
106 // Glb and lub computation.
107 
108 // The largest bitset subsumed by this type.
Glb(AstType * type)109 AstType::bitset AstBitsetType::Glb(AstType* type) {
110   DisallowHeapAllocation no_allocation;
111   // Fast case.
112   if (IsBitset(type)) {
113     return type->AsBitset();
114   } else if (type->IsUnion()) {
115     SLOW_DCHECK(type->AsUnion()->Wellformed());
116     return type->AsUnion()->Get(0)->BitsetGlb() |
117            AST_SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb());  // Shortcut.
118   } else if (type->IsRange()) {
119     bitset glb = AST_SEMANTIC(
120         AstBitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
121     return glb | AST_REPRESENTATION(type->BitsetLub());
122   } else {
123     return type->Representation();
124   }
125 }
126 
127 // The smallest bitset subsuming this type, possibly not a proper one.
Lub(AstType * type)128 AstType::bitset AstBitsetType::Lub(AstType* type) {
129   DisallowHeapAllocation no_allocation;
130   if (IsBitset(type)) return type->AsBitset();
131   if (type->IsUnion()) {
132     // Take the representation from the first element, which is always
133     // a bitset.
134     int bitset = type->AsUnion()->Get(0)->BitsetLub();
135     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
136       // Other elements only contribute their semantic part.
137       bitset |= AST_SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
138     }
139     return bitset;
140   }
141   if (type->IsClass()) return type->AsClass()->Lub();
142   if (type->IsConstant()) return type->AsConstant()->Lub();
143   if (type->IsRange()) return type->AsRange()->Lub();
144   if (type->IsContext()) return kOtherInternal & kTaggedPointer;
145   if (type->IsArray()) return kOtherObject;
146   if (type->IsFunction()) return kFunction;
147   if (type->IsTuple()) return kOtherInternal;
148   UNREACHABLE();
149   return kNone;
150 }
151 
Lub(i::Map * map)152 AstType::bitset AstBitsetType::Lub(i::Map* map) {
153   DisallowHeapAllocation no_allocation;
154   switch (map->instance_type()) {
155     case STRING_TYPE:
156     case ONE_BYTE_STRING_TYPE:
157     case CONS_STRING_TYPE:
158     case CONS_ONE_BYTE_STRING_TYPE:
159     case SLICED_STRING_TYPE:
160     case SLICED_ONE_BYTE_STRING_TYPE:
161     case EXTERNAL_STRING_TYPE:
162     case EXTERNAL_ONE_BYTE_STRING_TYPE:
163     case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
164     case SHORT_EXTERNAL_STRING_TYPE:
165     case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
166     case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
167       return kOtherString;
168     case INTERNALIZED_STRING_TYPE:
169     case ONE_BYTE_INTERNALIZED_STRING_TYPE:
170     case EXTERNAL_INTERNALIZED_STRING_TYPE:
171     case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
172     case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
173     case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
174     case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
175     case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
176       return kInternalizedString;
177     case SYMBOL_TYPE:
178       return kSymbol;
179     case ODDBALL_TYPE: {
180       Heap* heap = map->GetHeap();
181       if (map == heap->undefined_map()) return kUndefined;
182       if (map == heap->null_map()) return kNull;
183       if (map == heap->boolean_map()) return kBoolean;
184       if (map == heap->the_hole_map()) return kHole;
185       DCHECK(map == heap->uninitialized_map() ||
186              map == heap->no_interceptor_result_sentinel_map() ||
187              map == heap->termination_exception_map() ||
188              map == heap->arguments_marker_map() ||
189              map == heap->optimized_out_map() ||
190              map == heap->stale_register_map());
191       return kOtherInternal & kTaggedPointer;
192     }
193     case HEAP_NUMBER_TYPE:
194       return kNumber & kTaggedPointer;
195     case SIMD128_VALUE_TYPE:
196       return kSimd;
197     case JS_OBJECT_TYPE:
198     case JS_ARGUMENTS_TYPE:
199     case JS_ERROR_TYPE:
200     case JS_GLOBAL_OBJECT_TYPE:
201     case JS_GLOBAL_PROXY_TYPE:
202     case JS_API_OBJECT_TYPE:
203     case JS_SPECIAL_API_OBJECT_TYPE:
204       if (map->is_undetectable()) return kOtherUndetectable;
205       return kOtherObject;
206     case JS_VALUE_TYPE:
207     case JS_MESSAGE_OBJECT_TYPE:
208     case JS_DATE_TYPE:
209     case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
210     case JS_GENERATOR_OBJECT_TYPE:
211     case JS_MODULE_NAMESPACE_TYPE:
212     case JS_FIXED_ARRAY_ITERATOR_TYPE:
213     case JS_ARRAY_BUFFER_TYPE:
214     case JS_ARRAY_TYPE:
215     case JS_REGEXP_TYPE:  // TODO(rossberg): there should be a RegExp type.
216     case JS_TYPED_ARRAY_TYPE:
217     case JS_DATA_VIEW_TYPE:
218     case JS_SET_TYPE:
219     case JS_MAP_TYPE:
220     case JS_SET_ITERATOR_TYPE:
221     case JS_MAP_ITERATOR_TYPE:
222     case JS_STRING_ITERATOR_TYPE:
223 
224     case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
225     case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
226     case JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE:
227     case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
228     case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
229     case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
230     case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
231     case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
232     case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
233     case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
234     case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
235     case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
236     case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
237     case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
238     case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
239     case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
240     case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
241     case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
242     case JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE:
243     case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
244     case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
245     case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
246     case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
247     case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
248     case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
249     case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
250     case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
251     case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
252     case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
253     case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
254     case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
255     case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
256     case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
257     case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
258     case JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE:
259 
260     case JS_WEAK_MAP_TYPE:
261     case JS_WEAK_SET_TYPE:
262     case JS_PROMISE_TYPE:
263     case JS_BOUND_FUNCTION_TYPE:
264       DCHECK(!map->is_undetectable());
265       return kOtherObject;
266     case JS_FUNCTION_TYPE:
267       DCHECK(!map->is_undetectable());
268       return kFunction;
269     case JS_PROXY_TYPE:
270       DCHECK(!map->is_undetectable());
271       return kProxy;
272     case MAP_TYPE:
273     case ALLOCATION_SITE_TYPE:
274     case ACCESSOR_INFO_TYPE:
275     case SHARED_FUNCTION_INFO_TYPE:
276     case ACCESSOR_PAIR_TYPE:
277     case FIXED_ARRAY_TYPE:
278     case FIXED_DOUBLE_ARRAY_TYPE:
279     case BYTE_ARRAY_TYPE:
280     case BYTECODE_ARRAY_TYPE:
281     case TRANSITION_ARRAY_TYPE:
282     case FOREIGN_TYPE:
283     case SCRIPT_TYPE:
284     case CODE_TYPE:
285     case PROPERTY_CELL_TYPE:
286     case MODULE_TYPE:
287     case MODULE_INFO_ENTRY_TYPE:
288       return kOtherInternal & kTaggedPointer;
289 
290     // Remaining instance types are unsupported for now. If any of them do
291     // require bit set types, they should get kOtherInternal & kTaggedPointer.
292     case MUTABLE_HEAP_NUMBER_TYPE:
293     case FREE_SPACE_TYPE:
294 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
295   case FIXED_##TYPE##_ARRAY_TYPE:
296 
297       TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
298 #undef FIXED_TYPED_ARRAY_CASE
299     case FILLER_TYPE:
300     case ACCESS_CHECK_INFO_TYPE:
301     case INTERCEPTOR_INFO_TYPE:
302     case CALL_HANDLER_INFO_TYPE:
303     case PROMISE_RESOLVE_THENABLE_JOB_INFO_TYPE:
304     case PROMISE_REACTION_JOB_INFO_TYPE:
305     case FUNCTION_TEMPLATE_INFO_TYPE:
306     case OBJECT_TEMPLATE_INFO_TYPE:
307     case SIGNATURE_INFO_TYPE:
308     case TYPE_SWITCH_INFO_TYPE:
309     case ALLOCATION_MEMENTO_TYPE:
310     case TYPE_FEEDBACK_INFO_TYPE:
311     case ALIASED_ARGUMENTS_ENTRY_TYPE:
312     case BOX_TYPE:
313     case DEBUG_INFO_TYPE:
314     case BREAK_POINT_INFO_TYPE:
315     case CELL_TYPE:
316     case WEAK_CELL_TYPE:
317     case PROTOTYPE_INFO_TYPE:
318     case TUPLE3_TYPE:
319     case CONTEXT_EXTENSION_TYPE:
320       UNREACHABLE();
321       return kNone;
322   }
323   UNREACHABLE();
324   return kNone;
325 }
326 
Lub(i::Object * value)327 AstType::bitset AstBitsetType::Lub(i::Object* value) {
328   DisallowHeapAllocation no_allocation;
329   if (value->IsNumber()) {
330     return Lub(value->Number()) &
331            (value->IsSmi() ? kTaggedSigned : kTaggedPointer);
332   }
333   return Lub(i::HeapObject::cast(value)->map());
334 }
335 
Lub(double value)336 AstType::bitset AstBitsetType::Lub(double value) {
337   DisallowHeapAllocation no_allocation;
338   if (i::IsMinusZero(value)) return kMinusZero;
339   if (std::isnan(value)) return kNaN;
340   if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
341   return kOtherNumber;
342 }
343 
344 // Minimum values of plain numeric bitsets.
345 const AstBitsetType::Boundary AstBitsetType::BoundariesArray[] = {
346     {kOtherNumber, kPlainNumber, -V8_INFINITY},
347     {kOtherSigned32, kNegative32, kMinInt},
348     {kNegative31, kNegative31, -0x40000000},
349     {kUnsigned30, kUnsigned30, 0},
350     {kOtherUnsigned31, kUnsigned31, 0x40000000},
351     {kOtherUnsigned32, kUnsigned32, 0x80000000},
352     {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
353 
Boundaries()354 const AstBitsetType::Boundary* AstBitsetType::Boundaries() {
355   return BoundariesArray;
356 }
357 
BoundariesSize()358 size_t AstBitsetType::BoundariesSize() {
359   // Windows doesn't like arraysize here.
360   // return arraysize(BoundariesArray);
361   return 7;
362 }
363 
ExpandInternals(AstType::bitset bits)364 AstType::bitset AstBitsetType::ExpandInternals(AstType::bitset bits) {
365   DisallowHeapAllocation no_allocation;
366   if (!(bits & AST_SEMANTIC(kPlainNumber))) return bits;  // Shortcut.
367   const Boundary* boundaries = Boundaries();
368   for (size_t i = 0; i < BoundariesSize(); ++i) {
369     DCHECK(AstBitsetType::Is(boundaries[i].internal, boundaries[i].external));
370     if (bits & AST_SEMANTIC(boundaries[i].internal))
371       bits |= AST_SEMANTIC(boundaries[i].external);
372   }
373   return bits;
374 }
375 
Lub(double min,double max)376 AstType::bitset AstBitsetType::Lub(double min, double max) {
377   DisallowHeapAllocation no_allocation;
378   int lub = kNone;
379   const Boundary* mins = Boundaries();
380 
381   for (size_t i = 1; i < BoundariesSize(); ++i) {
382     if (min < mins[i].min) {
383       lub |= mins[i - 1].internal;
384       if (max < mins[i].min) return lub;
385     }
386   }
387   return lub | mins[BoundariesSize() - 1].internal;
388 }
389 
NumberBits(bitset bits)390 AstType::bitset AstBitsetType::NumberBits(bitset bits) {
391   return AST_SEMANTIC(bits & kPlainNumber);
392 }
393 
Glb(double min,double max)394 AstType::bitset AstBitsetType::Glb(double min, double max) {
395   DisallowHeapAllocation no_allocation;
396   int glb = kNone;
397   const Boundary* mins = Boundaries();
398 
399   // If the range does not touch 0, the bound is empty.
400   if (max < -1 || min > 0) return glb;
401 
402   for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
403     if (min <= mins[i].min) {
404       if (max + 1 < mins[i + 1].min) break;
405       glb |= mins[i].external;
406     }
407   }
408   // OtherNumber also contains float numbers, so it can never be
409   // in the greatest lower bound.
410   return glb & ~(AST_SEMANTIC(kOtherNumber));
411 }
412 
Min(bitset bits)413 double AstBitsetType::Min(bitset bits) {
414   DisallowHeapAllocation no_allocation;
415   DCHECK(Is(AST_SEMANTIC(bits), kNumber));
416   const Boundary* mins = Boundaries();
417   bool mz = AST_SEMANTIC(bits & kMinusZero);
418   for (size_t i = 0; i < BoundariesSize(); ++i) {
419     if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
420       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
421     }
422   }
423   if (mz) return 0;
424   return std::numeric_limits<double>::quiet_NaN();
425 }
426 
Max(bitset bits)427 double AstBitsetType::Max(bitset bits) {
428   DisallowHeapAllocation no_allocation;
429   DCHECK(Is(AST_SEMANTIC(bits), kNumber));
430   const Boundary* mins = Boundaries();
431   bool mz = AST_SEMANTIC(bits & kMinusZero);
432   if (AstBitsetType::Is(AST_SEMANTIC(mins[BoundariesSize() - 1].internal),
433                         bits)) {
434     return +V8_INFINITY;
435   }
436   for (size_t i = BoundariesSize() - 1; i-- > 0;) {
437     if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
438       return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
439     }
440   }
441   if (mz) return 0;
442   return std::numeric_limits<double>::quiet_NaN();
443 }
444 
445 // -----------------------------------------------------------------------------
446 // Predicates.
447 
SimplyEquals(AstType * that)448 bool AstType::SimplyEquals(AstType* that) {
449   DisallowHeapAllocation no_allocation;
450   if (this->IsClass()) {
451     return that->IsClass() &&
452            *this->AsClass()->Map() == *that->AsClass()->Map();
453   }
454   if (this->IsConstant()) {
455     return that->IsConstant() &&
456            *this->AsConstant()->Value() == *that->AsConstant()->Value();
457   }
458   if (this->IsContext()) {
459     return that->IsContext() &&
460            this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
461   }
462   if (this->IsArray()) {
463     return that->IsArray() &&
464            this->AsArray()->Element()->Equals(that->AsArray()->Element());
465   }
466   if (this->IsFunction()) {
467     if (!that->IsFunction()) return false;
468     AstFunctionType* this_fun = this->AsFunction();
469     AstFunctionType* that_fun = that->AsFunction();
470     if (this_fun->Arity() != that_fun->Arity() ||
471         !this_fun->Result()->Equals(that_fun->Result()) ||
472         !this_fun->Receiver()->Equals(that_fun->Receiver())) {
473       return false;
474     }
475     for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
476       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
477     }
478     return true;
479   }
480   if (this->IsTuple()) {
481     if (!that->IsTuple()) return false;
482     AstTupleType* this_tuple = this->AsTuple();
483     AstTupleType* that_tuple = that->AsTuple();
484     if (this_tuple->Arity() != that_tuple->Arity()) {
485       return false;
486     }
487     for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
488       if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false;
489     }
490     return true;
491   }
492   UNREACHABLE();
493   return false;
494 }
495 
Representation()496 AstType::bitset AstType::Representation() {
497   return AST_REPRESENTATION(this->BitsetLub());
498 }
499 
500 // Check if [this] <= [that].
SlowIs(AstType * that)501 bool AstType::SlowIs(AstType* that) {
502   DisallowHeapAllocation no_allocation;
503 
504   // Fast bitset cases
505   if (that->IsBitset()) {
506     return AstBitsetType::Is(this->BitsetLub(), that->AsBitset());
507   }
508 
509   if (this->IsBitset()) {
510     return AstBitsetType::Is(this->AsBitset(), that->BitsetGlb());
511   }
512 
513   // Check the representations.
514   if (!AstBitsetType::Is(Representation(), that->Representation())) {
515     return false;
516   }
517 
518   // Check the semantic part.
519   return SemanticIs(that);
520 }
521 
522 // Check if AST_SEMANTIC([this]) <= AST_SEMANTIC([that]). The result of the
523 // method
524 // should be independent of the representation axis of the types.
SemanticIs(AstType * that)525 bool AstType::SemanticIs(AstType* that) {
526   DisallowHeapAllocation no_allocation;
527 
528   if (this == that) return true;
529 
530   if (that->IsBitset()) {
531     return AstBitsetType::Is(AST_SEMANTIC(this->BitsetLub()), that->AsBitset());
532   }
533   if (this->IsBitset()) {
534     return AstBitsetType::Is(AST_SEMANTIC(this->AsBitset()), that->BitsetGlb());
535   }
536 
537   // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
538   if (this->IsUnion()) {
539     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
540       if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
541     }
542     return true;
543   }
544 
545   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
546   if (that->IsUnion()) {
547     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
548       if (this->SemanticIs(that->AsUnion()->Get(i))) return true;
549       if (i > 1 && this->IsRange()) return false;  // Shortcut.
550     }
551     return false;
552   }
553 
554   if (that->IsRange()) {
555     return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
556            (this->IsConstant() &&
557             Contains(that->AsRange(), this->AsConstant()));
558   }
559   if (this->IsRange()) return false;
560 
561   return this->SimplyEquals(that);
562 }
563 
564 // Most precise _current_ type of a value (usually its class).
NowOf(i::Object * value,Zone * zone)565 AstType* AstType::NowOf(i::Object* value, Zone* zone) {
566   if (value->IsSmi() ||
567       i::HeapObject::cast(value)->map()->instance_type() == HEAP_NUMBER_TYPE) {
568     return Of(value, zone);
569   }
570   return Class(i::handle(i::HeapObject::cast(value)->map()), zone);
571 }
572 
NowContains(i::Object * value)573 bool AstType::NowContains(i::Object* value) {
574   DisallowHeapAllocation no_allocation;
575   if (this->IsAny()) return true;
576   if (value->IsHeapObject()) {
577     i::Map* map = i::HeapObject::cast(value)->map();
578     for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
579       if (*it.Current() == map) return true;
580     }
581   }
582   return this->Contains(value);
583 }
584 
NowIs(AstType * that)585 bool AstType::NowIs(AstType* that) {
586   DisallowHeapAllocation no_allocation;
587 
588   // TODO(rossberg): this is incorrect for
589   //   Union(Constant(V), T)->NowIs(Class(M))
590   // but fuzzing does not cover that!
591   if (this->IsConstant()) {
592     i::Object* object = *this->AsConstant()->Value();
593     if (object->IsHeapObject()) {
594       i::Map* map = i::HeapObject::cast(object)->map();
595       for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
596         if (*it.Current() == map) return true;
597       }
598     }
599   }
600   return this->Is(that);
601 }
602 
603 // Check if [this] contains only (currently) stable classes.
NowStable()604 bool AstType::NowStable() {
605   DisallowHeapAllocation no_allocation;
606   return !this->IsClass() || this->AsClass()->Map()->is_stable();
607 }
608 
609 // Check if [this] and [that] overlap.
Maybe(AstType * that)610 bool AstType::Maybe(AstType* that) {
611   DisallowHeapAllocation no_allocation;
612 
613   // Take care of the representation part (and also approximate
614   // the semantic part).
615   if (!AstBitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
616     return false;
617 
618   return SemanticMaybe(that);
619 }
620 
SemanticMaybe(AstType * that)621 bool AstType::SemanticMaybe(AstType* that) {
622   DisallowHeapAllocation no_allocation;
623 
624   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
625   if (this->IsUnion()) {
626     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
627       if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
628     }
629     return false;
630   }
631 
632   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
633   if (that->IsUnion()) {
634     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
635       if (this->SemanticMaybe(that->AsUnion()->Get(i))) return true;
636     }
637     return false;
638   }
639 
640   if (!AstBitsetType::SemanticIsInhabited(this->BitsetLub() &
641                                           that->BitsetLub()))
642     return false;
643 
644   if (this->IsBitset() && that->IsBitset()) return true;
645 
646   if (this->IsClass() != that->IsClass()) return true;
647 
648   if (this->IsRange()) {
649     if (that->IsConstant()) {
650       return Contains(this->AsRange(), that->AsConstant());
651     }
652     if (that->IsRange()) {
653       return Overlap(this->AsRange(), that->AsRange());
654     }
655     if (that->IsBitset()) {
656       bitset number_bits = AstBitsetType::NumberBits(that->AsBitset());
657       if (number_bits == AstBitsetType::kNone) {
658         return false;
659       }
660       double min = std::max(AstBitsetType::Min(number_bits), this->Min());
661       double max = std::min(AstBitsetType::Max(number_bits), this->Max());
662       return min <= max;
663     }
664   }
665   if (that->IsRange()) {
666     return that->SemanticMaybe(this);  // This case is handled above.
667   }
668 
669   if (this->IsBitset() || that->IsBitset()) return true;
670 
671   return this->SimplyEquals(that);
672 }
673 
674 // Return the range in [this], or [NULL].
GetRange()675 AstType* AstType::GetRange() {
676   DisallowHeapAllocation no_allocation;
677   if (this->IsRange()) return this;
678   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
679     return this->AsUnion()->Get(1);
680   }
681   return NULL;
682 }
683 
Contains(i::Object * value)684 bool AstType::Contains(i::Object* value) {
685   DisallowHeapAllocation no_allocation;
686   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
687     if (*it.Current() == value) return true;
688   }
689   if (IsInteger(value)) {
690     AstType* range = this->GetRange();
691     if (range != NULL && Contains(range->AsRange(), value)) return true;
692   }
693   return AstBitsetType::New(AstBitsetType::Lub(value))->Is(this);
694 }
695 
Wellformed()696 bool AstUnionType::Wellformed() {
697   DisallowHeapAllocation no_allocation;
698   // This checks the invariants of the union representation:
699   // 1. There are at least two elements.
700   // 2. The first element is a bitset, no other element is a bitset.
701   // 3. At most one element is a range, and it must be the second one.
702   // 4. No element is itself a union.
703   // 5. No element (except the bitset) is a subtype of any other.
704   // 6. If there is a range, then the bitset type does not contain
705   //    plain number bits.
706   DCHECK(this->Length() >= 2);       // (1)
707   DCHECK(this->Get(0)->IsBitset());  // (2a)
708 
709   for (int i = 0; i < this->Length(); ++i) {
710     if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2b)
711     if (i != 1) DCHECK(!this->Get(i)->IsRange());   // (3)
712     DCHECK(!this->Get(i)->IsUnion());               // (4)
713     for (int j = 0; j < this->Length(); ++j) {
714       if (i != j && i != 0)
715         DCHECK(!this->Get(i)->SemanticIs(this->Get(j)));  // (5)
716     }
717   }
718   DCHECK(!this->Get(1)->IsRange() ||
719          (AstBitsetType::NumberBits(this->Get(0)->AsBitset()) ==
720           AstBitsetType::kNone));  // (6)
721   return true;
722 }
723 
724 // -----------------------------------------------------------------------------
725 // Union and intersection
726 
AddIsSafe(int x,int y)727 static bool AddIsSafe(int x, int y) {
728   return x >= 0 ? y <= std::numeric_limits<int>::max() - x
729                 : y >= std::numeric_limits<int>::min() - x;
730 }
731 
Intersect(AstType * type1,AstType * type2,Zone * zone)732 AstType* AstType::Intersect(AstType* type1, AstType* type2, Zone* zone) {
733   // Fast case: bit sets.
734   if (type1->IsBitset() && type2->IsBitset()) {
735     return AstBitsetType::New(type1->AsBitset() & type2->AsBitset());
736   }
737 
738   // Fast case: top or bottom types.
739   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
740   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
741 
742   // Semi-fast case.
743   if (type1->Is(type2)) return type1;
744   if (type2->Is(type1)) return type2;
745 
746   // Slow case: create union.
747 
748   // Figure out the representation of the result first.
749   // The rest of the method should not change this representation and
750   // it should not make any decisions based on representations (i.e.,
751   // it should only use the semantic part of types).
752   const bitset representation =
753       type1->Representation() & type2->Representation();
754 
755   // Semantic subtyping check - this is needed for consistency with the
756   // semi-fast case above - we should behave the same way regardless of
757   // representations. Intersection with a universal bitset should only update
758   // the representations.
759   if (type1->SemanticIs(type2)) {
760     type2 = Any();
761   } else if (type2->SemanticIs(type1)) {
762     type1 = Any();
763   }
764 
765   bitset bits =
766       AST_SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
767   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
768   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
769   if (!AddIsSafe(size1, size2)) return Any();
770   int size = size1 + size2;
771   if (!AddIsSafe(size, 2)) return Any();
772   size += 2;
773   AstType* result_type = AstUnionType::New(size, zone);
774   AstUnionType* result = result_type->AsUnion();
775   size = 0;
776 
777   // Deal with bitsets.
778   result->Set(size++, AstBitsetType::New(bits));
779 
780   AstRangeType::Limits lims = AstRangeType::Limits::Empty();
781   size = IntersectAux(type1, type2, result, size, &lims, zone);
782 
783   // If the range is not empty, then insert it into the union and
784   // remove the number bits from the bitset.
785   if (!lims.IsEmpty()) {
786     size = UpdateRange(AstRangeType::New(lims, representation, zone), result,
787                        size, zone);
788 
789     // Remove the number bits.
790     bitset number_bits = AstBitsetType::NumberBits(bits);
791     bits &= ~number_bits;
792     result->Set(0, AstBitsetType::New(bits));
793   }
794   return NormalizeUnion(result_type, size, zone);
795 }
796 
UpdateRange(AstType * range,AstUnionType * result,int size,Zone * zone)797 int AstType::UpdateRange(AstType* range, AstUnionType* result, int size,
798                          Zone* zone) {
799   if (size == 1) {
800     result->Set(size++, range);
801   } else {
802     // Make space for the range.
803     result->Set(size++, result->Get(1));
804     result->Set(1, range);
805   }
806 
807   // Remove any components that just got subsumed.
808   for (int i = 2; i < size;) {
809     if (result->Get(i)->SemanticIs(range)) {
810       result->Set(i, result->Get(--size));
811     } else {
812       ++i;
813     }
814   }
815   return size;
816 }
817 
ToLimits(bitset bits,Zone * zone)818 AstRangeType::Limits AstType::ToLimits(bitset bits, Zone* zone) {
819   bitset number_bits = AstBitsetType::NumberBits(bits);
820 
821   if (number_bits == AstBitsetType::kNone) {
822     return AstRangeType::Limits::Empty();
823   }
824 
825   return AstRangeType::Limits(AstBitsetType::Min(number_bits),
826                               AstBitsetType::Max(number_bits));
827 }
828 
IntersectRangeAndBitset(AstType * range,AstType * bitset,Zone * zone)829 AstRangeType::Limits AstType::IntersectRangeAndBitset(AstType* range,
830                                                       AstType* bitset,
831                                                       Zone* zone) {
832   AstRangeType::Limits range_lims(range->AsRange());
833   AstRangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone);
834   return AstRangeType::Limits::Intersect(range_lims, bitset_lims);
835 }
836 
IntersectAux(AstType * lhs,AstType * rhs,AstUnionType * result,int size,AstRangeType::Limits * lims,Zone * zone)837 int AstType::IntersectAux(AstType* lhs, AstType* rhs, AstUnionType* result,
838                           int size, AstRangeType::Limits* lims, Zone* zone) {
839   if (lhs->IsUnion()) {
840     for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
841       size =
842           IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone);
843     }
844     return size;
845   }
846   if (rhs->IsUnion()) {
847     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
848       size =
849           IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone);
850     }
851     return size;
852   }
853 
854   if (!AstBitsetType::SemanticIsInhabited(lhs->BitsetLub() &
855                                           rhs->BitsetLub())) {
856     return size;
857   }
858 
859   if (lhs->IsRange()) {
860     if (rhs->IsBitset()) {
861       AstRangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
862 
863       if (!lim.IsEmpty()) {
864         *lims = AstRangeType::Limits::Union(lim, *lims);
865       }
866       return size;
867     }
868     if (rhs->IsClass()) {
869       *lims = AstRangeType::Limits::Union(AstRangeType::Limits(lhs->AsRange()),
870                                           *lims);
871     }
872     if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
873       return AddToUnion(rhs, result, size, zone);
874     }
875     if (rhs->IsRange()) {
876       AstRangeType::Limits lim =
877           AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs->AsRange()),
878                                           AstRangeType::Limits(rhs->AsRange()));
879       if (!lim.IsEmpty()) {
880         *lims = AstRangeType::Limits::Union(lim, *lims);
881       }
882     }
883     return size;
884   }
885   if (rhs->IsRange()) {
886     // This case is handled symmetrically above.
887     return IntersectAux(rhs, lhs, result, size, lims, zone);
888   }
889   if (lhs->IsBitset() || rhs->IsBitset()) {
890     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone);
891   }
892   if (lhs->IsClass() != rhs->IsClass()) {
893     return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, zone);
894   }
895   if (lhs->SimplyEquals(rhs)) {
896     return AddToUnion(lhs, result, size, zone);
897   }
898   return size;
899 }
900 
901 // Make sure that we produce a well-formed range and bitset:
902 // If the range is non-empty, the number bits in the bitset should be
903 // clear. Moreover, if we have a canonical range (such as Signed32),
904 // we want to produce a bitset rather than a range.
NormalizeRangeAndBitset(AstType * range,bitset * bits,Zone * zone)905 AstType* AstType::NormalizeRangeAndBitset(AstType* range, bitset* bits,
906                                           Zone* zone) {
907   // Fast path: If the bitset does not mention numbers, we can just keep the
908   // range.
909   bitset number_bits = AstBitsetType::NumberBits(*bits);
910   if (number_bits == 0) {
911     return range;
912   }
913 
914   // If the range is semantically contained within the bitset, return None and
915   // leave the bitset untouched.
916   bitset range_lub = AST_SEMANTIC(range->BitsetLub());
917   if (AstBitsetType::Is(range_lub, *bits)) {
918     return None();
919   }
920 
921   // Slow path: reconcile the bitset range and the range.
922   double bitset_min = AstBitsetType::Min(number_bits);
923   double bitset_max = AstBitsetType::Max(number_bits);
924 
925   double range_min = range->Min();
926   double range_max = range->Max();
927 
928   // Remove the number bits from the bitset, they would just confuse us now.
929   // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
930   // case we already returned after the subtype check above.
931   *bits &= ~number_bits;
932 
933   if (range_min <= bitset_min && range_max >= bitset_max) {
934     // Bitset is contained within the range, just return the range.
935     return range;
936   }
937 
938   if (bitset_min < range_min) {
939     range_min = bitset_min;
940   }
941   if (bitset_max > range_max) {
942     range_max = bitset_max;
943   }
944   return AstRangeType::New(range_min, range_max, AstBitsetType::kNone, zone);
945 }
946 
Union(AstType * type1,AstType * type2,Zone * zone)947 AstType* AstType::Union(AstType* type1, AstType* type2, Zone* zone) {
948   // Fast case: bit sets.
949   if (type1->IsBitset() && type2->IsBitset()) {
950     return AstBitsetType::New(type1->AsBitset() | type2->AsBitset());
951   }
952 
953   // Fast case: top or bottom types.
954   if (type1->IsAny() || type2->IsNone()) return type1;
955   if (type2->IsAny() || type1->IsNone()) return type2;
956 
957   // Semi-fast case.
958   if (type1->Is(type2)) return type2;
959   if (type2->Is(type1)) return type1;
960 
961   // Figure out the representation of the result.
962   // The rest of the method should not change this representation and
963   // it should not make any decisions based on representations (i.e.,
964   // it should only use the semantic part of types).
965   const bitset representation =
966       type1->Representation() | type2->Representation();
967 
968   // Slow case: create union.
969   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
970   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
971   if (!AddIsSafe(size1, size2)) return Any();
972   int size = size1 + size2;
973   if (!AddIsSafe(size, 2)) return Any();
974   size += 2;
975   AstType* result_type = AstUnionType::New(size, zone);
976   AstUnionType* result = result_type->AsUnion();
977   size = 0;
978 
979   // Compute the new bitset.
980   bitset new_bitset = AST_SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
981 
982   // Deal with ranges.
983   AstType* range = None();
984   AstType* range1 = type1->GetRange();
985   AstType* range2 = type2->GetRange();
986   if (range1 != NULL && range2 != NULL) {
987     AstRangeType::Limits lims =
988         AstRangeType::Limits::Union(AstRangeType::Limits(range1->AsRange()),
989                                     AstRangeType::Limits(range2->AsRange()));
990     AstType* union_range = AstRangeType::New(lims, representation, zone);
991     range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
992   } else if (range1 != NULL) {
993     range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
994   } else if (range2 != NULL) {
995     range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
996   }
997   new_bitset = AST_SEMANTIC(new_bitset) | representation;
998   AstType* bits = AstBitsetType::New(new_bitset);
999   result->Set(size++, bits);
1000   if (!range->IsNone()) result->Set(size++, range);
1001 
1002   size = AddToUnion(type1, result, size, zone);
1003   size = AddToUnion(type2, result, size, zone);
1004   return NormalizeUnion(result_type, size, zone);
1005 }
1006 
1007 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
1008 // Return new size of [result].
AddToUnion(AstType * type,AstUnionType * result,int size,Zone * zone)1009 int AstType::AddToUnion(AstType* type, AstUnionType* result, int size,
1010                         Zone* zone) {
1011   if (type->IsBitset() || type->IsRange()) return size;
1012   if (type->IsUnion()) {
1013     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
1014       size = AddToUnion(type->AsUnion()->Get(i), result, size, zone);
1015     }
1016     return size;
1017   }
1018   for (int i = 0; i < size; ++i) {
1019     if (type->SemanticIs(result->Get(i))) return size;
1020   }
1021   result->Set(size++, type);
1022   return size;
1023 }
1024 
NormalizeUnion(AstType * union_type,int size,Zone * zone)1025 AstType* AstType::NormalizeUnion(AstType* union_type, int size, Zone* zone) {
1026   AstUnionType* unioned = union_type->AsUnion();
1027   DCHECK(size >= 1);
1028   DCHECK(unioned->Get(0)->IsBitset());
1029   // If the union has just one element, return it.
1030   if (size == 1) {
1031     return unioned->Get(0);
1032   }
1033   bitset bits = unioned->Get(0)->AsBitset();
1034   // If the union only consists of a range, we can get rid of the union.
1035   if (size == 2 && AST_SEMANTIC(bits) == AstBitsetType::kNone) {
1036     bitset representation = AST_REPRESENTATION(bits);
1037     if (representation == unioned->Get(1)->Representation()) {
1038       return unioned->Get(1);
1039     }
1040     if (unioned->Get(1)->IsRange()) {
1041       return AstRangeType::New(unioned->Get(1)->AsRange()->Min(),
1042                                unioned->Get(1)->AsRange()->Max(),
1043                                unioned->Get(0)->AsBitset(), zone);
1044     }
1045   }
1046   unioned->Shrink(size);
1047   SLOW_DCHECK(unioned->Wellformed());
1048   return union_type;
1049 }
1050 
1051 // -----------------------------------------------------------------------------
1052 // Component extraction
1053 
1054 // static
Representation(AstType * t,Zone * zone)1055 AstType* AstType::Representation(AstType* t, Zone* zone) {
1056   return AstBitsetType::New(t->Representation());
1057 }
1058 
1059 // static
Semantic(AstType * t,Zone * zone)1060 AstType* AstType::Semantic(AstType* t, Zone* zone) {
1061   return Intersect(t, AstBitsetType::New(AstBitsetType::kSemantic), zone);
1062 }
1063 
1064 // -----------------------------------------------------------------------------
1065 // Iteration.
1066 
NumClasses()1067 int AstType::NumClasses() {
1068   DisallowHeapAllocation no_allocation;
1069   if (this->IsClass()) {
1070     return 1;
1071   } else if (this->IsUnion()) {
1072     int result = 0;
1073     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1074       if (this->AsUnion()->Get(i)->IsClass()) ++result;
1075     }
1076     return result;
1077   } else {
1078     return 0;
1079   }
1080 }
1081 
NumConstants()1082 int AstType::NumConstants() {
1083   DisallowHeapAllocation no_allocation;
1084   if (this->IsConstant()) {
1085     return 1;
1086   } else if (this->IsUnion()) {
1087     int result = 0;
1088     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1089       if (this->AsUnion()->Get(i)->IsConstant()) ++result;
1090     }
1091     return result;
1092   } else {
1093     return 0;
1094   }
1095 }
1096 
1097 template <class T>
get_type()1098 AstType* AstType::Iterator<T>::get_type() {
1099   DCHECK(!Done());
1100   return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
1101 }
1102 
1103 // C++ cannot specialise nested templates, so we have to go through this
1104 // contortion with an auxiliary template to simulate it.
1105 template <class T>
1106 struct TypeImplIteratorAux {
1107   static bool matches(AstType* type);
1108   static i::Handle<T> current(AstType* type);
1109 };
1110 
1111 template <>
1112 struct TypeImplIteratorAux<i::Map> {
matchesv8::internal::TypeImplIteratorAux1113   static bool matches(AstType* type) { return type->IsClass(); }
currentv8::internal::TypeImplIteratorAux1114   static i::Handle<i::Map> current(AstType* type) {
1115     return type->AsClass()->Map();
1116   }
1117 };
1118 
1119 template <>
1120 struct TypeImplIteratorAux<i::Object> {
matchesv8::internal::TypeImplIteratorAux1121   static bool matches(AstType* type) { return type->IsConstant(); }
currentv8::internal::TypeImplIteratorAux1122   static i::Handle<i::Object> current(AstType* type) {
1123     return type->AsConstant()->Value();
1124   }
1125 };
1126 
1127 template <class T>
matches(AstType * type)1128 bool AstType::Iterator<T>::matches(AstType* type) {
1129   return TypeImplIteratorAux<T>::matches(type);
1130 }
1131 
1132 template <class T>
Current()1133 i::Handle<T> AstType::Iterator<T>::Current() {
1134   return TypeImplIteratorAux<T>::current(get_type());
1135 }
1136 
1137 template <class T>
Advance()1138 void AstType::Iterator<T>::Advance() {
1139   DisallowHeapAllocation no_allocation;
1140   ++index_;
1141   if (type_->IsUnion()) {
1142     for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
1143       if (matches(type_->AsUnion()->Get(index_))) return;
1144     }
1145   } else if (index_ == 0 && matches(type_)) {
1146     return;
1147   }
1148   index_ = -1;
1149 }
1150 
1151 // -----------------------------------------------------------------------------
1152 // Printing.
1153 
Name(bitset bits)1154 const char* AstBitsetType::Name(bitset bits) {
1155   switch (bits) {
1156     case AST_REPRESENTATION(kAny):
1157       return "Any";
1158 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
1159   case AST_REPRESENTATION(k##type):                   \
1160     return #type;
1161       AST_REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
1162 #undef RETURN_NAMED_REPRESENTATION_TYPE
1163 
1164 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
1165   case AST_SEMANTIC(k##type):                   \
1166     return #type;
1167       AST_SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1168       AST_INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
1169 #undef RETURN_NAMED_SEMANTIC_TYPE
1170 
1171     default:
1172       return NULL;
1173   }
1174 }
1175 
Print(std::ostream & os,bitset bits)1176 void AstBitsetType::Print(std::ostream& os,  // NOLINT
1177                           bitset bits) {
1178   DisallowHeapAllocation no_allocation;
1179   const char* name = Name(bits);
1180   if (name != NULL) {
1181     os << name;
1182     return;
1183   }
1184 
1185   // clang-format off
1186   static const bitset named_bitsets[] = {
1187 #define BITSET_CONSTANT(type, value) AST_REPRESENTATION(k##type),
1188     AST_REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
1189 #undef BITSET_CONSTANT
1190 
1191 #define BITSET_CONSTANT(type, value) AST_SEMANTIC(k##type),
1192     AST_INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
1193     AST_SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
1194 #undef BITSET_CONSTANT
1195   };
1196   // clang-format on
1197 
1198   bool is_first = true;
1199   os << "(";
1200   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
1201     bitset subset = named_bitsets[i];
1202     if ((bits & subset) == subset) {
1203       if (!is_first) os << " | ";
1204       is_first = false;
1205       os << Name(subset);
1206       bits -= subset;
1207     }
1208   }
1209   DCHECK(bits == 0);
1210   os << ")";
1211 }
1212 
PrintTo(std::ostream & os,PrintDimension dim)1213 void AstType::PrintTo(std::ostream& os, PrintDimension dim) {
1214   DisallowHeapAllocation no_allocation;
1215   if (dim != REPRESENTATION_DIM) {
1216     if (this->IsBitset()) {
1217       AstBitsetType::Print(os, AST_SEMANTIC(this->AsBitset()));
1218     } else if (this->IsClass()) {
1219       os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1220       AstBitsetType::New(AstBitsetType::Lub(this))->PrintTo(os, dim);
1221       os << ")";
1222     } else if (this->IsConstant()) {
1223       os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
1224     } else if (this->IsRange()) {
1225       std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
1226       std::streamsize saved_precision = os.precision(0);
1227       os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
1228          << ")";
1229       os.flags(saved_flags);
1230       os.precision(saved_precision);
1231     } else if (this->IsContext()) {
1232       os << "Context(";
1233       this->AsContext()->Outer()->PrintTo(os, dim);
1234       os << ")";
1235     } else if (this->IsUnion()) {
1236       os << "(";
1237       for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1238         AstType* type_i = this->AsUnion()->Get(i);
1239         if (i > 0) os << " | ";
1240         type_i->PrintTo(os, dim);
1241       }
1242       os << ")";
1243     } else if (this->IsArray()) {
1244       os << "Array(";
1245       AsArray()->Element()->PrintTo(os, dim);
1246       os << ")";
1247     } else if (this->IsFunction()) {
1248       if (!this->AsFunction()->Receiver()->IsAny()) {
1249         this->AsFunction()->Receiver()->PrintTo(os, dim);
1250         os << ".";
1251       }
1252       os << "(";
1253       for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1254         if (i > 0) os << ", ";
1255         this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1256       }
1257       os << ")->";
1258       this->AsFunction()->Result()->PrintTo(os, dim);
1259     } else if (this->IsTuple()) {
1260       os << "<";
1261       for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
1262         AstType* type_i = this->AsTuple()->Element(i);
1263         if (i > 0) os << ", ";
1264         type_i->PrintTo(os, dim);
1265       }
1266       os << ">";
1267     } else {
1268       UNREACHABLE();
1269     }
1270   }
1271   if (dim == BOTH_DIMS) os << "/";
1272   if (dim != SEMANTIC_DIM) {
1273     AstBitsetType::Print(os, AST_REPRESENTATION(this->BitsetLub()));
1274   }
1275 }
1276 
1277 #ifdef DEBUG
Print()1278 void AstType::Print() {
1279   OFStream os(stdout);
1280   PrintTo(os);
1281   os << std::endl;
1282 }
Print(bitset bits)1283 void AstBitsetType::Print(bitset bits) {
1284   OFStream os(stdout);
1285   Print(os, bits);
1286   os << std::endl;
1287 }
1288 #endif
1289 
SignedSmall()1290 AstBitsetType::bitset AstBitsetType::SignedSmall() {
1291   return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1292 }
1293 
UnsignedSmall()1294 AstBitsetType::bitset AstBitsetType::UnsignedSmall() {
1295   return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
1296 }
1297 
1298 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \
1299   AstType* AstType::Name(Isolate* isolate, Zone* zone) {             \
1300     return Class(i::handle(isolate->heap()->name##_map()), zone);    \
1301   }
1302 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE)
1303 #undef CONSTRUCT_SIMD_TYPE
1304 
1305 // -----------------------------------------------------------------------------
1306 // Instantiations.
1307 
1308 template class AstType::Iterator<i::Map>;
1309 template class AstType::Iterator<i::Object>;
1310 
1311 }  // namespace internal
1312 }  // namespace v8
1313