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