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