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