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