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