src/v8/src/types.cc

   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, n = this->AsUnion()->Length(); i < n; ++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, n = this->AsUnion()->Length(); i < n; ++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, n = type->AsUnion()->Length(); i < n; ++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     case FLOAT32x4_TYPE:
 224     case FLOAT64x2_TYPE:
 225     case INT32x4_TYPE:
 226       if (map->is_undetectable()) return kUndetectable;
 227       return kOtherObject;
 228     case JS_ARRAY_TYPE:
 229       return kArray;
 230     case JS_FUNCTION_TYPE:
 231       return kFunction;
 232     case JS_REGEXP_TYPE:
 233       return kRegExp;
 234     case JS_PROXY_TYPE:
 235     case JS_FUNCTION_PROXY_TYPE:
 236       return kProxy;
 237     case MAP_TYPE:
 238       // When compiling stub templates, the meta map is used as a place holder
 239       // for the actual map with which the template is later instantiated.
 240       // We treat it as a kind of type variable whose upper bound is Any.
 241       // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
 242       // we must exclude Undetectable here. This makes no sense, really,
 243       // because it means that the template isn't actually parametric.
 244       // Also, it doesn't apply elsewhere. 8-(
 245       // We ought to find a cleaner solution for compiling stubs parameterised
 246       // over type or class variables, esp ones with bounds...
 247       return kDetectable;
 248     case DECLARED_ACCESSOR_INFO_TYPE:
 249     case EXECUTABLE_ACCESSOR_INFO_TYPE:
 250     case SHARED_FUNCTION_INFO_TYPE:
 251     case ACCESSOR_PAIR_TYPE:
 252     case FIXED_ARRAY_TYPE:
 253     case BYTE_ARRAY_TYPE:
 254     case FOREIGN_TYPE:
 255     case CODE_TYPE:
 256       return kInternal & kTaggedPtr;
 257     default:
 258       UNREACHABLE();
 259       return kNone;
 260   }
 261 }
 262
 263
 264 template<class Config>
 265 typename TypeImpl<Config>::bitset
 266 TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
 267   DisallowHeapAllocation no_allocation;
 268   if (value->IsNumber()) {
 269     return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
 270   }
 271   return Lub(i::HeapObject::cast(value)->map());
 272 }
 273
 274
 275 template<class Config>
 276 typename TypeImpl<Config>::bitset
 277 TypeImpl<Config>::BitsetType::Lub(double value) {
 278   DisallowHeapAllocation no_allocation;
 279   if (i::IsMinusZero(value)) return kMinusZero;
 280   if (std::isnan(value)) return kNaN;
 281   if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
 282   return kOtherNumber;
 283 }
 284
 285
 286 // Minimum values of regular numeric bitsets when SmiValuesAre31Bits.
 287 template<class Config>
 288 const typename TypeImpl<Config>::BitsetType::BitsetMin
 289 TypeImpl<Config>::BitsetType::BitsetMins31[] = {
 290     {kOtherNumber, -V8_INFINITY},
 291     {kOtherSigned32, kMinInt},
 292     {kOtherSignedSmall, -0x40000000},
 293     {kUnsignedSmall, 0},
 294     {kOtherUnsigned31, 0x40000000},
 295     {kOtherUnsigned32, 0x80000000},
 296     {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}
 297 };
 298
 299
 300 // Minimum values of regular numeric bitsets when SmiValuesAre32Bits.
 301 // OtherSigned32 and OtherUnsigned31 are empty (see the diagrams in types.h).
 302 template<class Config>
 303 const typename TypeImpl<Config>::BitsetType::BitsetMin
 304 TypeImpl<Config>::BitsetType::BitsetMins32[] = {
 305     {kOtherNumber, -V8_INFINITY},
 306     {kOtherSignedSmall, kMinInt},
 307     {kUnsignedSmall, 0},
 308     {kOtherUnsigned32, 0x80000000},
 309     {kOtherNumber, static_cast<double>(kMaxUInt32) + 1}
 310 };
 311
 312
 313 template<class Config>
 314 typename TypeImpl<Config>::bitset
 315 TypeImpl<Config>::BitsetType::Lub(double min, double max) {
 316   DisallowHeapAllocation no_allocation;
 317   int lub = kNone;
 318   const BitsetMin* mins = BitsetMins();
 319
 320   for (size_t i = 1; i < BitsetMinsSize(); ++i) {
 321     if (min < mins[i].min) {
 322       lub |= mins[i-1].bits;
 323       if (max < mins[i].min) return lub;
 324     }
 325   }
 326   return lub |= mins[BitsetMinsSize()-1].bits;
 327 }
 328
 329
 330 template<class Config>
 331 double TypeImpl<Config>::BitsetType::Min(bitset bits) {
 332   DisallowHeapAllocation no_allocation;
 333   DCHECK(Is(bits, kNumber));
 334   const BitsetMin* mins = BitsetMins();
 335   bool mz = SEMANTIC(bits & kMinusZero);
 336   for (size_t i = 0; i < BitsetMinsSize(); ++i) {
 337     if (Is(SEMANTIC(mins[i].bits), bits)) {
 338       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
 339     }
 340   }
 341   if (mz) return 0;
 342   return base::OS::nan_value();
 343 }
 344
 345
 346 template<class Config>
 347 double TypeImpl<Config>::BitsetType::Max(bitset bits) {
 348   DisallowHeapAllocation no_allocation;
 349   DCHECK(Is(bits, kNumber));
 350   const BitsetMin* mins = BitsetMins();
 351   bool mz = SEMANTIC(bits & kMinusZero);
 352   if (BitsetType::Is(mins[BitsetMinsSize()-1].bits, bits)) {
 353     return +V8_INFINITY;
 354   }
 355   for (size_t i = BitsetMinsSize()-1; i-- > 0; ) {
 356     if (Is(SEMANTIC(mins[i].bits), bits)) {
 357       return mz ?
 358           std::max(0.0, mins[i+1].min - 1) : mins[i+1].min - 1;
 359     }
 360   }
 361   if (mz) return 0;
 362   return base::OS::nan_value();
 363 }
 364
 365
 366 // -----------------------------------------------------------------------------
 367 // Predicates.
 368
 369
 370 template<class Config>
 371 bool TypeImpl<Config>::SimplyEquals(TypeImpl* that) {
 372   DisallowHeapAllocation no_allocation;
 373   if (this->IsClass()) {
 374     return that->IsClass()
 375         && *this->AsClass()->Map() == *that->AsClass()->Map();
 376   }
 377   if (this->IsConstant()) {
 378     return that->IsConstant()
 379         && *this->AsConstant()->Value() == *that->AsConstant()->Value();
 380   }
 381   if (this->IsContext()) {
 382     return that->IsContext()
 383         && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
 384   }
 385   if (this->IsArray()) {
 386     return that->IsArray()
 387         && this->AsArray()->Element()->Equals(that->AsArray()->Element());
 388   }
 389   if (this->IsFunction()) {
 390     if (!that->IsFunction()) return false;
 391     FunctionType* this_fun = this->AsFunction();
 392     FunctionType* that_fun = that->AsFunction();
 393     if (this_fun->Arity() != that_fun->Arity() ||
 394         !this_fun->Result()->Equals(that_fun->Result()) ||
 395         !this_fun->Receiver()->Equals(that_fun->Receiver())) {
 396       return false;
 397     }
 398     for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
 399       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
 400     }
 401     return true;
 402   }
 403   UNREACHABLE();
 404   return false;
 405 }
 406
 407
 408 // Check if [this] <= [that].
 409 template<class Config>
 410 bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
 411   DisallowHeapAllocation no_allocation;
 412
 413   if (that->IsBitset()) {
 414     return BitsetType::Is(this->BitsetLub(), that->AsBitset());
 415   }
 416   if (this->IsBitset()) {
 417     return BitsetType::Is(this->AsBitset(), that->BitsetGlb());
 418   }
 419
 420   // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
 421   if (this->IsUnion()) {
 422     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
 423       if (!this->AsUnion()->Get(i)->Is(that)) return false;
 424     }
 425     return true;
 426   }
 427
 428   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
 429   if (that->IsUnion()) {
 430     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
 431       if (this->Is(that->AsUnion()->Get(i))) return true;
 432       if (i > 1 && this->IsRange()) return false;  // Shortcut.
 433     }
 434     return false;
 435   }
 436
 437   if (that->IsRange()) {
 438     return (this->IsRange() && Contains(that->AsRange(), this->AsRange()))
 439         || (this->IsConstant() &&
 440             Contains(that->AsRange(), *this->AsConstant()->Value()));
 441   }
 442   if (this->IsRange()) return false;
 443
 444   return this->SimplyEquals(that);
 445 }
 446
 447
 448 template<class Config>
 449 bool TypeImpl<Config>::NowIs(TypeImpl* that) {
 450   DisallowHeapAllocation no_allocation;
 451
 452   // TODO(rossberg): this is incorrect for
 453   //   Union(Constant(V), T)->NowIs(Class(M))
 454   // but fuzzing does not cover that!
 455   if (this->IsConstant()) {
 456     i::Object* object = *this->AsConstant()->Value();
 457     if (object->IsHeapObject()) {
 458       i::Map* map = i::HeapObject::cast(object)->map();
 459       for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
 460         if (*it.Current() == map) return true;
 461       }
 462     }
 463   }
 464   return this->Is(that);
 465 }
 466
 467
 468 // Check if [this] contains only (currently) stable classes.
 469 template<class Config>
 470 bool TypeImpl<Config>::NowStable() {
 471   DisallowHeapAllocation no_allocation;
 472   for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
 473     if (!it.Current()->is_stable()) return false;
 474   }
 475   return true;
 476 }
 477
 478
 479 // Check if [this] and [that] overlap.
 480 template<class Config>
 481 bool TypeImpl<Config>::Maybe(TypeImpl* that) {
 482   DisallowHeapAllocation no_allocation;
 483
 484   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
 485   if (this->IsUnion()) {
 486     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
 487       if (this->AsUnion()->Get(i)->Maybe(that)) return true;
 488     }
 489     return false;
 490   }
 491
 492   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
 493   if (that->IsUnion()) {
 494     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
 495       if (this->Maybe(that->AsUnion()->Get(i))) return true;
 496     }
 497     return false;
 498   }
 499
 500   if (!BitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
 501     return false;
 502   if (this->IsBitset() || that->IsBitset()) return true;
 503
 504   if (this->IsClass() != that->IsClass()) return true;
 505
 506   if (this->IsRange()) {
 507     if (that->IsConstant()) {
 508       return Contains(this->AsRange(), *that->AsConstant()->Value());
 509     }
 510     return that->IsRange() && Overlap(this->AsRange(), that->AsRange());
 511   }
 512   if (that->IsRange()) {
 513     if (this->IsConstant()) {
 514       return Contains(that->AsRange(), *this->AsConstant()->Value());
 515     }
 516     return this->IsRange() && Overlap(this->AsRange(), that->AsRange());
 517   }
 518
 519   return this->SimplyEquals(that);
 520 }
 521
 522
 523 // Return the range in [this], or [NULL].
 524 template<class Config>
 525 typename TypeImpl<Config>::RangeType* TypeImpl<Config>::GetRange() {
 526   DisallowHeapAllocation no_allocation;
 527   if (this->IsRange()) return this->AsRange();
 528   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
 529     return this->AsUnion()->Get(1)->AsRange();
 530   }
 531   return NULL;
 532 }
 533
 534
 535 template<class Config>
 536 bool TypeImpl<Config>::Contains(i::Object* value) {
 537   DisallowHeapAllocation no_allocation;
 538   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
 539     if (*it.Current() == value) return true;
 540   }
 541   if (IsInteger(value)) {
 542     RangeType* range = this->GetRange();
 543     if (range != NULL && Contains(range, value)) return true;
 544   }
 545   return BitsetType::New(BitsetType::Lub(value))->Is(this);
 546 }
 547
 548
 549 template<class Config>
 550 bool TypeImpl<Config>::UnionType::Wellformed() {
 551   DisallowHeapAllocation no_allocation;
 552   // This checks the invariants of the union representation:
 553   // 1. There are at least two elements.
 554   // 2. At most one element is a bitset, and it must be the first one.
 555   // 3. At most one element is a range, and it must be the second one
 556   //    (even when the first element is not a bitset).
 557   // 4. No element is itself a union.
 558   // 5. No element is a subtype of any other.
 559   DCHECK(this->Length() >= 2);  // (1)
 560   for (int i = 0; i < this->Length(); ++i) {
 561     if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2)
 562     if (i != 1) DCHECK(!this->Get(i)->IsRange());  // (3)
 563     DCHECK(!this->Get(i)->IsUnion());  // (4)
 564     for (int j = 0; j < this->Length(); ++j) {
 565       if (i != j) DCHECK(!this->Get(i)->Is(this->Get(j)));  // (5)
 566     }
 567   }
 568   return true;
 569 }
 570
 571
 572 // -----------------------------------------------------------------------------
 573 // Union and intersection
 574
 575
 576 static bool AddIsSafe(int x, int y) {
 577   return x >= 0 ?
 578       y <= std::numeric_limits<int>::max() - x :
 579       y >= std::numeric_limits<int>::min() - x;
 580 }
 581
 582
 583 template<class Config>
 584 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
 585     TypeHandle type1, TypeHandle type2, Region* region) {
 586   bitset bits = type1->BitsetGlb() & type2->BitsetGlb();
 587   if (!BitsetType::IsInhabited(bits)) bits = BitsetType::kNone;
 588
 589   // Fast case: bit sets.
 590   if (type1->IsBitset() && type2->IsBitset()) {
 591     return BitsetType::New(bits, region);
 592   }
 593
 594   // Fast case: top or bottom types.
 595   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
 596   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
 597
 598   // Semi-fast case.
 599   if (type1->Is(type2)) return type1;
 600   if (type2->Is(type1)) return type2;
 601
 602   // Slow case: create union.
 603   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
 604   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
 605   if (!AddIsSafe(size1, size2)) return Any(region);
 606   int size = size1 + size2;
 607   if (!AddIsSafe(size, 2)) return Any(region);
 608   size += 2;
 609   UnionHandle result = UnionType::New(size, region);
 610   size = 0;
 611
 612   // Deal with bitsets.
 613   result->Set(size++, BitsetType::New(bits, region));
 614
 615   // Deal with ranges.
 616   TypeHandle range = None(region);
 617   RangeType* range1 = type1->GetRange();
 618   RangeType* range2 = type2->GetRange();
 619   if (range1 != NULL && range2 != NULL) {
 620     Limits lim = Intersect(Limits(range1), Limits(range2));
 621     if (lim.min->Number() <= lim.max->Number()) {
 622       range = RangeType::New(lim, region);
 623     }
 624   }
 625   result->Set(size++, range);
 626
 627   size = IntersectAux(type1, type2, result, size, region);
 628   return NormalizeUnion(result, size);
 629 }
 630
 631
 632 template<class Config>
 633 int TypeImpl<Config>::UpdateRange(
 634     RangeHandle range, UnionHandle result, int size, Region* region) {
 635   TypeHandle old_range = result->Get(1);
 636   DCHECK(old_range->IsRange() || old_range->IsNone());
 637   if (range->Is(old_range)) return size;
 638   if (!old_range->Is(range->unhandle())) {
 639     range = RangeType::New(
 640         Union(Limits(range->AsRange()), Limits(old_range->AsRange())), region);
 641   }
 642   result->Set(1, range);
 643
 644   // Remove any components that just got subsumed.
 645   for (int i = 2; i < size; ) {
 646     if (result->Get(i)->Is(range->unhandle())) {
 647       result->Set(i, result->Get(--size));
 648     } else {
 649       ++i;
 650     }
 651   }
 652   return size;
 653 }
 654
 655
 656 template<class Config>
 657 int TypeImpl<Config>::IntersectAux(
 658     TypeHandle lhs, TypeHandle rhs,
 659     UnionHandle result, int size, Region* region) {
 660   if (lhs->IsUnion()) {
 661     for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
 662       size = IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, region);
 663     }
 664     return size;
 665   }
 666   if (rhs->IsUnion()) {
 667     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
 668       size = IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, region);
 669     }
 670     return size;
 671   }
 672
 673   if (!BitsetType::IsInhabited(lhs->BitsetLub() & rhs->BitsetLub())) {
 674     return size;
 675   }
 676
 677   if (lhs->IsRange()) {
 678     if (rhs->IsBitset() || rhs->IsClass()) {
 679       return UpdateRange(
 680           Config::template cast<RangeType>(lhs), result, size, region);
 681     }
 682     if (rhs->IsConstant() &&
 683         Contains(lhs->AsRange(), *rhs->AsConstant()->Value())) {
 684       return AddToUnion(rhs, result, size, region);
 685     }
 686     return size;
 687   }
 688   if (rhs->IsRange()) {
 689     if (lhs->IsBitset() || lhs->IsClass()) {
 690       return UpdateRange(
 691           Config::template cast<RangeType>(rhs), result, size, region);
 692     }
 693     if (lhs->IsConstant() &&
 694         Contains(rhs->AsRange(), *lhs->AsConstant()->Value())) {
 695       return AddToUnion(lhs, result, size, region);
 696     }
 697     return size;
 698   }
 699
 700   if (lhs->IsBitset() || rhs->IsBitset()) {
 701     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, region);
 702   }
 703   if (lhs->IsClass() != rhs->IsClass()) {
 704     return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, region);
 705   }
 706   if (lhs->SimplyEquals(rhs->unhandle())) {
 707     return AddToUnion(lhs, result, size, region);
 708   }
 709   return size;
 710 }
 711
 712
 713 template<class Config>
 714 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
 715     TypeHandle type1, TypeHandle type2, Region* region) {
 716
 717   // Fast case: bit sets.
 718   if (type1->IsBitset() && type2->IsBitset()) {
 719     return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
 720   }
 721
 722   // Fast case: top or bottom types.
 723   if (type1->IsAny() || type2->IsNone()) return type1;
 724   if (type2->IsAny() || type1->IsNone()) return type2;
 725
 726   // Semi-fast case.
 727   if (type1->Is(type2)) return type2;
 728   if (type2->Is(type1)) return type1;
 729
 730   // Slow case: create union.
 731   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
 732   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
 733   if (!AddIsSafe(size1, size2)) return Any(region);
 734   int size = size1 + size2;
 735   if (!AddIsSafe(size, 2)) return Any(region);
 736   size += 2;
 737   UnionHandle result = UnionType::New(size, region);
 738   size = 0;
 739
 740   // Deal with bitsets.
 741   TypeHandle bits = BitsetType::New(
 742       type1->BitsetGlb() | type2->BitsetGlb(), region);
 743   result->Set(size++, bits);
 744
 745   // Deal with ranges.
 746   TypeHandle range = None(region);
 747   RangeType* range1 = type1->GetRange();
 748   RangeType* range2 = type2->GetRange();
 749   if (range1 != NULL && range2 != NULL) {
 750     range = RangeType::New(Union(Limits(range1), Limits(range2)), region);
 751   } else if (range1 != NULL) {
 752     range = handle(range1);
 753   } else if (range2 != NULL) {
 754     range = handle(range2);
 755   }
 756   result->Set(size++, range);
 757
 758   size = AddToUnion(type1, result, size, region);
 759   size = AddToUnion(type2, result, size, region);
 760   return NormalizeUnion(result, size);
 761 }
 762
 763
 764 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
 765 // Return new size of [result].
 766 template<class Config>
 767 int TypeImpl<Config>::AddToUnion(
 768     TypeHandle type, UnionHandle result, int size, Region* region) {
 769   if (type->IsBitset() || type->IsRange()) return size;
 770   if (type->IsUnion()) {
 771     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
 772       size = AddToUnion(type->AsUnion()->Get(i), result, size, region);
 773     }
 774     return size;
 775   }
 776   for (int i = 0; i < size; ++i) {
 777     if (type->Is(result->Get(i))) return size;
 778   }
 779   result->Set(size++, type);
 780   return size;
 781 }
 782
 783
 784 template<class Config>
 785 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::NormalizeUnion(
 786     UnionHandle unioned, int size) {
 787   DCHECK(size >= 2);
 788   // If range is subsumed by bitset, use its place for a different type.
 789   if (unioned->Get(1)->Is(unioned->Get(0))) {
 790     unioned->Set(1, unioned->Get(--size));
 791   }
 792   // If bitset is None, use its place for a different type.
 793   if (size >= 2 && unioned->Get(0)->IsNone()) {
 794     unioned->Set(0, unioned->Get(--size));
 795   }
 796   if (size == 1) return unioned->Get(0);
 797   unioned->Shrink(size);
 798   SLOW_DCHECK(unioned->Wellformed());
 799   return unioned;
 800 }
 801
 802
 803 // -----------------------------------------------------------------------------
 804 // Iteration.
 805
 806 template<class Config>
 807 int TypeImpl<Config>::NumClasses() {
 808   DisallowHeapAllocation no_allocation;
 809   if (this->IsClass()) {
 810     return 1;
 811   } else if (this->IsUnion()) {
 812     int result = 0;
 813     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
 814       if (this->AsUnion()->Get(i)->IsClass()) ++result;
 815     }
 816     return result;
 817   } else {
 818     return 0;
 819   }
 820 }
 821
 822
 823 template<class Config>
 824 int TypeImpl<Config>::NumConstants() {
 825   DisallowHeapAllocation no_allocation;
 826   if (this->IsConstant()) {
 827     return 1;
 828   } else if (this->IsUnion()) {
 829     int result = 0;
 830     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
 831       if (this->AsUnion()->Get(i)->IsConstant()) ++result;
 832     }
 833     return result;
 834   } else {
 835     return 0;
 836   }
 837 }
 838
 839
 840 template<class Config> template<class T>
 841 typename TypeImpl<Config>::TypeHandle
 842 TypeImpl<Config>::Iterator<T>::get_type() {
 843   DCHECK(!Done());
 844   return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
 845 }
 846
 847
 848 // C++ cannot specialise nested templates, so we have to go through this
 849 // contortion with an auxiliary template to simulate it.
 850 template<class Config, class T>
 851 struct TypeImplIteratorAux {
 852   static bool matches(typename TypeImpl<Config>::TypeHandle type);
 853   static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
 854 };
 855
 856 template<class Config>
 857 struct TypeImplIteratorAux<Config, i::Map> {
 858   static bool matches(typename TypeImpl<Config>::TypeHandle type) {
 859     return type->IsClass();
 860   }
 861   static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
 862     return type->AsClass()->Map();
 863   }
 864 };
 865
 866 template<class Config>
 867 struct TypeImplIteratorAux<Config, i::Object> {
 868   static bool matches(typename TypeImpl<Config>::TypeHandle type) {
 869     return type->IsConstant();
 870   }
 871   static i::Handle<i::Object> current(
 872       typename TypeImpl<Config>::TypeHandle type) {
 873     return type->AsConstant()->Value();
 874   }
 875 };
 876
 877 template<class Config> template<class T>
 878 bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
 879   return TypeImplIteratorAux<Config, T>::matches(type);
 880 }
 881
 882 template<class Config> template<class T>
 883 i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
 884   return TypeImplIteratorAux<Config, T>::current(get_type());
 885 }
 886
 887
 888 template<class Config> template<class T>
 889 void TypeImpl<Config>::Iterator<T>::Advance() {
 890   DisallowHeapAllocation no_allocation;
 891   ++index_;
 892   if (type_->IsUnion()) {
 893     for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
 894       if (matches(type_->AsUnion()->Get(index_))) return;
 895     }
 896   } else if (index_ == 0 && matches(type_)) {
 897     return;
 898   }
 899   index_ = -1;
 900 }
 901
 902
 903 // -----------------------------------------------------------------------------
 904 // Conversion between low-level representations.
 905
 906 template<class Config>
 907 template<class OtherType>
 908 typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
 909     typename OtherType::TypeHandle type, Region* region) {
 910   if (type->IsBitset()) {
 911     return BitsetType::New(type->AsBitset(), region);
 912   } else if (type->IsClass()) {
 913     return ClassType::New(type->AsClass()->Map(), region);
 914   } else if (type->IsConstant()) {
 915     return ConstantType::New(type->AsConstant()->Value(), region);
 916   } else if (type->IsRange()) {
 917     return RangeType::New(
 918         type->AsRange()->Min(), type->AsRange()->Max(), region);
 919   } else if (type->IsContext()) {
 920     TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
 921     return ContextType::New(outer, region);
 922   } else if (type->IsUnion()) {
 923     int length = type->AsUnion()->Length();
 924     UnionHandle unioned = UnionType::New(length, region);
 925     for (int i = 0; i < length; ++i) {
 926       TypeHandle t = Convert<OtherType>(type->AsUnion()->Get(i), region);
 927       unioned->Set(i, t);
 928     }
 929     return unioned;
 930   } else if (type->IsArray()) {
 931     TypeHandle element = Convert<OtherType>(type->AsArray()->Element(), region);
 932     return ArrayType::New(element, region);
 933   } else if (type->IsFunction()) {
 934     TypeHandle res = Convert<OtherType>(type->AsFunction()->Result(), region);
 935     TypeHandle rcv = Convert<OtherType>(type->AsFunction()->Receiver(), region);
 936     FunctionHandle function = FunctionType::New(
 937         res, rcv, type->AsFunction()->Arity(), region);
 938     for (int i = 0; i < function->Arity(); ++i) {
 939       TypeHandle param = Convert<OtherType>(
 940           type->AsFunction()->Parameter(i), region);
 941       function->InitParameter(i, param);
 942     }
 943     return function;
 944   } else {
 945     UNREACHABLE();
 946     return None(region);
 947   }
 948 }
 949
 950
 951 // -----------------------------------------------------------------------------
 952 // Printing.
 953
 954 template<class Config>
 955 const char* TypeImpl<Config>::BitsetType::Name(bitset bits) {
 956   switch (bits) {
 957     case REPRESENTATION(kAny): return "Any";
 958     #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
 959     case REPRESENTATION(k##type): return #type;
 960     REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
 961     #undef RETURN_NAMED_REPRESENTATION_TYPE
 962
 963     #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
 964     case SEMANTIC(k##type): return #type;
 965     SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
 966     #undef RETURN_NAMED_SEMANTIC_TYPE
 967
 968     default:
 969       return NULL;
 970   }
 971 }
 972
 973
 974 template <class Config>
 975 void TypeImpl<Config>::BitsetType::Print(std::ostream& os,  // NOLINT
 976                                          bitset bits) {
 977   DisallowHeapAllocation no_allocation;
 978   const char* name = Name(bits);
 979   if (name != NULL) {
 980     os << name;
 981     return;
 982   }
 983
 984   static const bitset named_bitsets[] = {
 985 #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
 986       REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
 987 #undef BITSET_CONSTANT
 988
 989 #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
 990       SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
 991 #undef BITSET_CONSTANT
 992   };
 993
 994   bool is_first = true;
 995   os << "(";
 996   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
 997     bitset subset = named_bitsets[i];
 998     if ((bits & subset) == subset) {
 999       if (!is_first) os << " | ";
1000       is_first = false;
1001       os << Name(subset);
1002       bits -= subset;
1003     }
1004   }
1005   DCHECK(bits == 0);
1006   os << ")";
1007 }
1008
1009
1010 template <class Config>
1011 void TypeImpl<Config>::PrintTo(std::ostream& os, PrintDimension dim) {
1012   DisallowHeapAllocation no_allocation;
1013   if (dim != REPRESENTATION_DIM) {
1014     if (this->IsBitset()) {
1015       BitsetType::Print(os, SEMANTIC(this->AsBitset()));
1016     } else if (this->IsClass()) {
1017       os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
1018       BitsetType::New(BitsetType::Lub(this))->PrintTo(os, dim);
1019       os << ")";
1020     } else if (this->IsConstant()) {
1021       os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
1022     } else if (this->IsRange()) {
1023       os << "Range(" << this->AsRange()->Min()->Number()
1024          << ", " << this->AsRange()->Max()->Number() << ")";
1025     } else if (this->IsContext()) {
1026       os << "Context(";
1027       this->AsContext()->Outer()->PrintTo(os, dim);
1028       os << ")";
1029     } else if (this->IsUnion()) {
1030       os << "(";
1031       for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
1032         TypeHandle type_i = this->AsUnion()->Get(i);
1033         if (i > 0) os << " | ";
1034         type_i->PrintTo(os, dim);
1035       }
1036       os << ")";
1037     } else if (this->IsArray()) {
1038       os << "Array(";
1039       AsArray()->Element()->PrintTo(os, dim);
1040       os << ")";
1041     } else if (this->IsFunction()) {
1042       if (!this->AsFunction()->Receiver()->IsAny()) {
1043         this->AsFunction()->Receiver()->PrintTo(os, dim);
1044         os << ".";
1045       }
1046       os << "(";
1047       for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
1048         if (i > 0) os << ", ";
1049         this->AsFunction()->Parameter(i)->PrintTo(os, dim);
1050       }
1051       os << ")->";
1052       this->AsFunction()->Result()->PrintTo(os, dim);
1053     } else {
1054       UNREACHABLE();
1055     }
1056   }
1057   if (dim == BOTH_DIMS) os << "/";
1058   if (dim != SEMANTIC_DIM) {
1059     BitsetType::Print(os, REPRESENTATION(this->BitsetLub()));
1060   }
1061 }
1062
1063
1064 #ifdef DEBUG
1065 template <class Config>
1066 void TypeImpl<Config>::Print() {
1067   OFStream os(stdout);
1068   PrintTo(os);
1069   os << std::endl;
1070 }
1071 template <class Config>
1072 void TypeImpl<Config>::BitsetType::Print(bitset bits) {
1073   OFStream os(stdout);
1074   Print(os, bits);
1075   os << std::endl;
1076 }
1077 #endif
1078
1079
1080 // -----------------------------------------------------------------------------
1081 // Instantiations.
1082
1083 template class TypeImpl<ZoneTypeConfig>;
1084 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
1085 template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
1086
1087 template class TypeImpl<HeapTypeConfig>;
1088 template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
1089 template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
1090
1091 template TypeImpl<ZoneTypeConfig>::TypeHandle
1092   TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
1093     TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
1094 template TypeImpl<HeapTypeConfig>::TypeHandle
1095   TypeImpl<HeapTypeConfig>::Convert<Type>(
1096     TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
1097
1098 } }  // namespace v8::internal