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