LCOV - code coverage report
Current view: top level - src/ast - ast-types.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 327 480 68.1 %
Date: 2017-04-26 Functions: 40 60 66.7 %

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

Generated by: LCOV version 1.10