1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <iomanip> 6 7 #include "src/compiler/types.h" 8 9 #include "src/handles-inl.h" 10 #include "src/objects-inl.h" 11 #include "src/ostreams.h" 12 13 namespace v8 { 14 namespace internal { 15 namespace compiler { 16 17 // ----------------------------------------------------------------------------- 18 // Range-related helper functions. 19 20 bool RangeType::Limits::IsEmpty() { return this->min > this->max; } 21 22 RangeType::Limits RangeType::Limits::Intersect(Limits lhs, Limits rhs) { 23 DisallowHeapAllocation no_allocation; 24 Limits result(lhs); 25 if (lhs.min < rhs.min) result.min = rhs.min; 26 if (lhs.max > rhs.max) result.max = rhs.max; 27 return result; 28 } 29 30 RangeType::Limits RangeType::Limits::Union(Limits lhs, Limits rhs) { 31 DisallowHeapAllocation no_allocation; 32 if (lhs.IsEmpty()) return rhs; 33 if (rhs.IsEmpty()) return lhs; 34 Limits result(lhs); 35 if (lhs.min > rhs.min) result.min = rhs.min; 36 if (lhs.max < rhs.max) result.max = rhs.max; 37 return result; 38 } 39 40 bool Type::Overlap(const RangeType* lhs, const RangeType* rhs) { 41 DisallowHeapAllocation no_allocation; 42 return !RangeType::Limits::Intersect(RangeType::Limits(lhs), 43 RangeType::Limits(rhs)) 44 .IsEmpty(); 45 } 46 47 bool Type::Contains(const RangeType* lhs, const RangeType* rhs) { 48 DisallowHeapAllocation no_allocation; 49 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max(); 50 } 51 52 // ----------------------------------------------------------------------------- 53 // Min and Max computation. 54 55 double Type::Min() const { 56 DCHECK(this->Is(Number())); 57 DCHECK(!this->Is(NaN())); 58 if (this->IsBitset()) return BitsetType::Min(this->AsBitset()); 59 if (this->IsUnion()) { 60 double min = +V8_INFINITY; 61 for (int i = 1, n = AsUnion()->Length(); i < n; ++i) { 62 min = std::min(min, AsUnion()->Get(i).Min()); 63 } 64 Type bitset = AsUnion()->Get(0); 65 if (!bitset.Is(NaN())) min = std::min(min, bitset.Min()); 66 return min; 67 } 68 if (this->IsRange()) return this->AsRange()->Min(); 69 DCHECK(this->IsOtherNumberConstant()); 70 return this->AsOtherNumberConstant()->Value(); 71 } 72 73 double Type::Max() const { 74 DCHECK(this->Is(Number())); 75 DCHECK(!this->Is(NaN())); 76 if (this->IsBitset()) return BitsetType::Max(this->AsBitset()); 77 if (this->IsUnion()) { 78 double max = -V8_INFINITY; 79 for (int i = 1, n = this->AsUnion()->Length(); i < n; ++i) { 80 max = std::max(max, this->AsUnion()->Get(i).Max()); 81 } 82 Type bitset = this->AsUnion()->Get(0); 83 if (!bitset.Is(NaN())) max = std::max(max, bitset.Max()); 84 return max; 85 } 86 if (this->IsRange()) return this->AsRange()->Max(); 87 DCHECK(this->IsOtherNumberConstant()); 88 return this->AsOtherNumberConstant()->Value(); 89 } 90 91 // ----------------------------------------------------------------------------- 92 // Glb and lub computation. 93 94 // The largest bitset subsumed by this type. 95 Type::bitset Type::BitsetGlb() const { 96 DisallowHeapAllocation no_allocation; 97 // Fast case. 98 if (IsBitset()) { 99 return AsBitset(); 100 } else if (IsUnion()) { 101 SLOW_DCHECK(AsUnion()->Wellformed()); 102 return AsUnion()->Get(0).BitsetGlb() | 103 AsUnion()->Get(1).BitsetGlb(); // Shortcut. 104 } else if (IsRange()) { 105 bitset glb = BitsetType::Glb(AsRange()->Min(), AsRange()->Max()); 106 return glb; 107 } else { 108 return BitsetType::kNone; 109 } 110 } 111 112 // The smallest bitset subsuming this type, possibly not a proper one. 113 Type::bitset Type::BitsetLub() const { 114 DisallowHeapAllocation no_allocation; 115 if (IsBitset()) return AsBitset(); 116 if (IsUnion()) { 117 // Take the representation from the first element, which is always 118 // a bitset. 119 int bitset = AsUnion()->Get(0).BitsetLub(); 120 for (int i = 0, n = AsUnion()->Length(); i < n; ++i) { 121 // Other elements only contribute their semantic part. 122 bitset |= AsUnion()->Get(i).BitsetLub(); 123 } 124 return bitset; 125 } 126 if (IsHeapConstant()) return AsHeapConstant()->Lub(); 127 if (IsOtherNumberConstant()) { 128 return AsOtherNumberConstant()->Lub(); 129 } 130 if (IsRange()) return AsRange()->Lub(); 131 if (IsTuple()) return BitsetType::kOtherInternal; 132 UNREACHABLE(); 133 } 134 135 Type::bitset BitsetType::Lub(HeapObjectType const& type) { 136 switch (type.instance_type()) { 137 case CONS_STRING_TYPE: 138 case CONS_ONE_BYTE_STRING_TYPE: 139 case THIN_STRING_TYPE: 140 case THIN_ONE_BYTE_STRING_TYPE: 141 case SLICED_STRING_TYPE: 142 case SLICED_ONE_BYTE_STRING_TYPE: 143 case EXTERNAL_STRING_TYPE: 144 case EXTERNAL_ONE_BYTE_STRING_TYPE: 145 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: 146 case SHORT_EXTERNAL_STRING_TYPE: 147 case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE: 148 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: 149 case STRING_TYPE: 150 case ONE_BYTE_STRING_TYPE: 151 return kString; 152 case EXTERNAL_INTERNALIZED_STRING_TYPE: 153 case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: 154 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: 155 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE: 156 case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE: 157 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: 158 case INTERNALIZED_STRING_TYPE: 159 case ONE_BYTE_INTERNALIZED_STRING_TYPE: 160 return kInternalizedString; 161 case SYMBOL_TYPE: 162 return kSymbol; 163 case BIGINT_TYPE: 164 return kBigInt; 165 case ODDBALL_TYPE: 166 switch (type.oddball_type()) { 167 case OddballType::kNone: 168 break; 169 case OddballType::kHole: 170 return kHole; 171 case OddballType::kBoolean: 172 return kBoolean; 173 case OddballType::kNull: 174 return kNull; 175 case OddballType::kUndefined: 176 return kUndefined; 177 case OddballType::kUninitialized: 178 case OddballType::kOther: 179 // TODO(neis): We should add a kOtherOddball type. 180 return kOtherInternal; 181 } 182 UNREACHABLE(); 183 case HEAP_NUMBER_TYPE: 184 return kNumber; 185 case JS_OBJECT_TYPE: 186 case JS_ARGUMENTS_TYPE: 187 case JS_ERROR_TYPE: 188 case JS_GLOBAL_OBJECT_TYPE: 189 case JS_GLOBAL_PROXY_TYPE: 190 case JS_API_OBJECT_TYPE: 191 case JS_SPECIAL_API_OBJECT_TYPE: 192 if (type.is_undetectable()) { 193 // Currently we assume that every undetectable receiver is also 194 // callable, which is what we need to support document.all. We 195 // could add another Type bit to support other use cases in the 196 // future if necessary. 197 DCHECK(type.is_callable()); 198 return kOtherUndetectable; 199 } 200 if (type.is_callable()) { 201 return kOtherCallable; 202 } 203 return kOtherObject; 204 case JS_ARRAY_TYPE: 205 return kArray; 206 case JS_VALUE_TYPE: 207 case JS_MESSAGE_OBJECT_TYPE: 208 case JS_DATE_TYPE: 209 #ifdef V8_INTL_SUPPORT 210 case JS_INTL_COLLATOR_TYPE: 211 case JS_INTL_LIST_FORMAT_TYPE: 212 case JS_INTL_LOCALE_TYPE: 213 case JS_INTL_PLURAL_RULES_TYPE: 214 case JS_INTL_RELATIVE_TIME_FORMAT_TYPE: 215 #endif // V8_INTL_SUPPORT 216 case JS_CONTEXT_EXTENSION_OBJECT_TYPE: 217 case JS_GENERATOR_OBJECT_TYPE: 218 case JS_ASYNC_GENERATOR_OBJECT_TYPE: 219 case JS_MODULE_NAMESPACE_TYPE: 220 case JS_ARRAY_BUFFER_TYPE: 221 case JS_ARRAY_ITERATOR_TYPE: 222 case JS_REGEXP_TYPE: // TODO(rossberg): there should be a RegExp type. 223 case JS_REGEXP_STRING_ITERATOR_TYPE: 224 case JS_TYPED_ARRAY_TYPE: 225 case JS_DATA_VIEW_TYPE: 226 case JS_SET_TYPE: 227 case JS_MAP_TYPE: 228 case JS_SET_KEY_VALUE_ITERATOR_TYPE: 229 case JS_SET_VALUE_ITERATOR_TYPE: 230 case JS_MAP_KEY_ITERATOR_TYPE: 231 case JS_MAP_KEY_VALUE_ITERATOR_TYPE: 232 case JS_MAP_VALUE_ITERATOR_TYPE: 233 case JS_STRING_ITERATOR_TYPE: 234 case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE: 235 case JS_WEAK_MAP_TYPE: 236 case JS_WEAK_SET_TYPE: 237 case JS_PROMISE_TYPE: 238 case WASM_MODULE_TYPE: 239 case WASM_GLOBAL_TYPE: 240 case WASM_INSTANCE_TYPE: 241 case WASM_MEMORY_TYPE: 242 case WASM_TABLE_TYPE: 243 DCHECK(!type.is_callable()); 244 DCHECK(!type.is_undetectable()); 245 return kOtherObject; 246 case JS_BOUND_FUNCTION_TYPE: 247 DCHECK(!type.is_undetectable()); 248 return kBoundFunction; 249 case JS_FUNCTION_TYPE: 250 DCHECK(!type.is_undetectable()); 251 return kFunction; 252 case JS_PROXY_TYPE: 253 DCHECK(!type.is_undetectable()); 254 if (type.is_callable()) return kCallableProxy; 255 return kOtherProxy; 256 case MAP_TYPE: 257 case ALLOCATION_SITE_TYPE: 258 case ACCESSOR_INFO_TYPE: 259 case SHARED_FUNCTION_INFO_TYPE: 260 case FUNCTION_TEMPLATE_INFO_TYPE: 261 case ACCESSOR_PAIR_TYPE: 262 case FIXED_ARRAY_TYPE: 263 case HASH_TABLE_TYPE: 264 case ORDERED_HASH_MAP_TYPE: 265 case ORDERED_HASH_SET_TYPE: 266 case NAME_DICTIONARY_TYPE: 267 case GLOBAL_DICTIONARY_TYPE: 268 case NUMBER_DICTIONARY_TYPE: 269 case SIMPLE_NUMBER_DICTIONARY_TYPE: 270 case STRING_TABLE_TYPE: 271 case EPHEMERON_HASH_TABLE_TYPE: 272 case WEAK_FIXED_ARRAY_TYPE: 273 case WEAK_ARRAY_LIST_TYPE: 274 case FIXED_DOUBLE_ARRAY_TYPE: 275 case FEEDBACK_METADATA_TYPE: 276 case BYTE_ARRAY_TYPE: 277 case BYTECODE_ARRAY_TYPE: 278 case OBJECT_BOILERPLATE_DESCRIPTION_TYPE: 279 case ARRAY_BOILERPLATE_DESCRIPTION_TYPE: 280 case DESCRIPTOR_ARRAY_TYPE: 281 case TRANSITION_ARRAY_TYPE: 282 case FEEDBACK_CELL_TYPE: 283 case FEEDBACK_VECTOR_TYPE: 284 case PROPERTY_ARRAY_TYPE: 285 case FOREIGN_TYPE: 286 case SCOPE_INFO_TYPE: 287 case SCRIPT_CONTEXT_TABLE_TYPE: 288 case BLOCK_CONTEXT_TYPE: 289 case CATCH_CONTEXT_TYPE: 290 case DEBUG_EVALUATE_CONTEXT_TYPE: 291 case EVAL_CONTEXT_TYPE: 292 case FUNCTION_CONTEXT_TYPE: 293 case MODULE_CONTEXT_TYPE: 294 case NATIVE_CONTEXT_TYPE: 295 case SCRIPT_CONTEXT_TYPE: 296 case WITH_CONTEXT_TYPE: 297 case SCRIPT_TYPE: 298 case CODE_TYPE: 299 case PROPERTY_CELL_TYPE: 300 case MODULE_TYPE: 301 case MODULE_INFO_ENTRY_TYPE: 302 case CELL_TYPE: 303 case PRE_PARSED_SCOPE_DATA_TYPE: 304 case UNCOMPILED_DATA_WITHOUT_PRE_PARSED_SCOPE_TYPE: 305 case UNCOMPILED_DATA_WITH_PRE_PARSED_SCOPE_TYPE: 306 return kOtherInternal; 307 308 // Remaining instance types are unsupported for now. If any of them do 309 // require bit set types, they should get kOtherInternal. 310 case MUTABLE_HEAP_NUMBER_TYPE: 311 case FREE_SPACE_TYPE: 312 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype) \ 313 case FIXED_##TYPE##_ARRAY_TYPE: 314 315 TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE) 316 #undef FIXED_TYPED_ARRAY_CASE 317 case FILLER_TYPE: 318 case ACCESS_CHECK_INFO_TYPE: 319 case CALL_HANDLER_INFO_TYPE: 320 case INTERCEPTOR_INFO_TYPE: 321 case OBJECT_TEMPLATE_INFO_TYPE: 322 case ALLOCATION_MEMENTO_TYPE: 323 case ALIASED_ARGUMENTS_ENTRY_TYPE: 324 case PROMISE_CAPABILITY_TYPE: 325 case PROMISE_REACTION_TYPE: 326 case DEBUG_INFO_TYPE: 327 case STACK_FRAME_INFO_TYPE: 328 case SMALL_ORDERED_HASH_MAP_TYPE: 329 case SMALL_ORDERED_HASH_SET_TYPE: 330 case PROTOTYPE_INFO_TYPE: 331 case INTERPRETER_DATA_TYPE: 332 case TUPLE2_TYPE: 333 case TUPLE3_TYPE: 334 case WASM_DEBUG_INFO_TYPE: 335 case WASM_EXPORTED_FUNCTION_DATA_TYPE: 336 case LOAD_HANDLER_TYPE: 337 case STORE_HANDLER_TYPE: 338 case ASYNC_GENERATOR_REQUEST_TYPE: 339 case CODE_DATA_CONTAINER_TYPE: 340 case CALLBACK_TASK_TYPE: 341 case CALLABLE_TASK_TYPE: 342 case PROMISE_FULFILL_REACTION_JOB_TASK_TYPE: 343 case PROMISE_REJECT_REACTION_JOB_TASK_TYPE: 344 case PROMISE_RESOLVE_THENABLE_JOB_TASK_TYPE: 345 UNREACHABLE(); 346 } 347 UNREACHABLE(); 348 } 349 350 Type::bitset BitsetType::Lub(double value) { 351 DisallowHeapAllocation no_allocation; 352 if (IsMinusZero(value)) return kMinusZero; 353 if (std::isnan(value)) return kNaN; 354 if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value); 355 return kOtherNumber; 356 } 357 358 // Minimum values of plain numeric bitsets. 359 const BitsetType::Boundary BitsetType::BoundariesArray[] = { 360 {kOtherNumber, kPlainNumber, -V8_INFINITY}, 361 {kOtherSigned32, kNegative32, kMinInt}, 362 {kNegative31, kNegative31, -0x40000000}, 363 {kUnsigned30, kUnsigned30, 0}, 364 {kOtherUnsigned31, kUnsigned31, 0x40000000}, 365 {kOtherUnsigned32, kUnsigned32, 0x80000000}, 366 {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}}; 367 368 const BitsetType::Boundary* BitsetType::Boundaries() { return BoundariesArray; } 369 370 size_t BitsetType::BoundariesSize() { 371 // Windows doesn't like arraysize here. 372 // return arraysize(BoundariesArray); 373 return 7; 374 } 375 376 Type::bitset BitsetType::ExpandInternals(Type::bitset bits) { 377 DCHECK_IMPLIES(bits & kOtherString, (bits & kString) == kString); 378 DisallowHeapAllocation no_allocation; 379 if (!(bits & kPlainNumber)) return bits; // Shortcut. 380 const Boundary* boundaries = Boundaries(); 381 for (size_t i = 0; i < BoundariesSize(); ++i) { 382 DCHECK(BitsetType::Is(boundaries[i].internal, boundaries[i].external)); 383 if (bits & boundaries[i].internal) bits |= boundaries[i].external; 384 } 385 return bits; 386 } 387 388 Type::bitset BitsetType::Lub(double min, double max) { 389 DisallowHeapAllocation no_allocation; 390 int lub = kNone; 391 const Boundary* mins = Boundaries(); 392 393 for (size_t i = 1; i < BoundariesSize(); ++i) { 394 if (min < mins[i].min) { 395 lub |= mins[i - 1].internal; 396 if (max < mins[i].min) return lub; 397 } 398 } 399 return lub | mins[BoundariesSize() - 1].internal; 400 } 401 402 Type::bitset BitsetType::NumberBits(bitset bits) { return bits & kPlainNumber; } 403 404 Type::bitset BitsetType::Glb(double min, double max) { 405 DisallowHeapAllocation no_allocation; 406 int glb = kNone; 407 const Boundary* mins = Boundaries(); 408 409 // If the range does not touch 0, the bound is empty. 410 if (max < -1 || min > 0) return glb; 411 412 for (size_t i = 1; i + 1 < BoundariesSize(); ++i) { 413 if (min <= mins[i].min) { 414 if (max + 1 < mins[i + 1].min) break; 415 glb |= mins[i].external; 416 } 417 } 418 // OtherNumber also contains float numbers, so it can never be 419 // in the greatest lower bound. 420 return glb & ~(kOtherNumber); 421 } 422 423 double BitsetType::Min(bitset bits) { 424 DisallowHeapAllocation no_allocation; 425 DCHECK(Is(bits, kNumber)); 426 DCHECK(!Is(bits, kNaN)); 427 const Boundary* mins = Boundaries(); 428 bool mz = bits & kMinusZero; 429 for (size_t i = 0; i < BoundariesSize(); ++i) { 430 if (Is(mins[i].internal, bits)) { 431 return mz ? std::min(0.0, mins[i].min) : mins[i].min; 432 } 433 } 434 DCHECK(mz); 435 return 0; 436 } 437 438 double BitsetType::Max(bitset bits) { 439 DisallowHeapAllocation no_allocation; 440 DCHECK(Is(bits, kNumber)); 441 DCHECK(!Is(bits, kNaN)); 442 const Boundary* mins = Boundaries(); 443 bool mz = bits & kMinusZero; 444 if (BitsetType::Is(mins[BoundariesSize() - 1].internal, bits)) { 445 return +V8_INFINITY; 446 } 447 for (size_t i = BoundariesSize() - 1; i-- > 0;) { 448 if (Is(mins[i].internal, bits)) { 449 return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1; 450 } 451 } 452 DCHECK(mz); 453 return 0; 454 } 455 456 // static 457 bool OtherNumberConstantType::IsOtherNumberConstant(double value) { 458 // Not an integer, not NaN, and not -0. 459 return !std::isnan(value) && !RangeType::IsInteger(value) && 460 !IsMinusZero(value); 461 } 462 463 HeapConstantType::HeapConstantType(BitsetType::bitset bitset, 464 const HeapObjectRef& heap_ref) 465 : TypeBase(kHeapConstant), bitset_(bitset), heap_ref_(heap_ref) {} 466 467 Handle<HeapObject> HeapConstantType::Value() const { 468 return heap_ref_.object<HeapObject>(); 469 } 470 471 // ----------------------------------------------------------------------------- 472 // Predicates. 473 474 bool Type::SimplyEquals(Type that) const { 475 DisallowHeapAllocation no_allocation; 476 if (this->IsHeapConstant()) { 477 return that.IsHeapConstant() && 478 this->AsHeapConstant()->Value().address() == 479 that.AsHeapConstant()->Value().address(); 480 } 481 if (this->IsOtherNumberConstant()) { 482 return that.IsOtherNumberConstant() && 483 this->AsOtherNumberConstant()->Value() == 484 that.AsOtherNumberConstant()->Value(); 485 } 486 if (this->IsRange()) { 487 if (that.IsHeapConstant() || that.IsOtherNumberConstant()) return false; 488 } 489 if (this->IsTuple()) { 490 if (!that.IsTuple()) return false; 491 const TupleType* this_tuple = this->AsTuple(); 492 const TupleType* that_tuple = that.AsTuple(); 493 if (this_tuple->Arity() != that_tuple->Arity()) { 494 return false; 495 } 496 for (int i = 0, n = this_tuple->Arity(); i < n; ++i) { 497 if (!this_tuple->Element(i).Equals(that_tuple->Element(i))) return false; 498 } 499 return true; 500 } 501 UNREACHABLE(); 502 } 503 504 // Check if [this] <= [that]. 505 bool Type::SlowIs(Type that) const { 506 DisallowHeapAllocation no_allocation; 507 508 // Fast bitset cases 509 if (that.IsBitset()) { 510 return BitsetType::Is(this->BitsetLub(), that.AsBitset()); 511 } 512 513 if (this->IsBitset()) { 514 return BitsetType::Is(this->AsBitset(), that.BitsetGlb()); 515 } 516 517 // (T1 \/ ... \/ Tn) <= T if (T1 <= T) /\ ... /\ (Tn <= T) 518 if (this->IsUnion()) { 519 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { 520 if (!this->AsUnion()->Get(i).Is(that)) return false; 521 } 522 return true; 523 } 524 525 // T <= (T1 \/ ... \/ Tn) if (T <= T1) \/ ... \/ (T <= Tn) 526 if (that.IsUnion()) { 527 for (int i = 0, n = that.AsUnion()->Length(); i < n; ++i) { 528 if (this->Is(that.AsUnion()->Get(i))) return true; 529 if (i > 1 && this->IsRange()) return false; // Shortcut. 530 } 531 return false; 532 } 533 534 if (that.IsRange()) { 535 return (this->IsRange() && Contains(that.AsRange(), this->AsRange())); 536 } 537 if (this->IsRange()) return false; 538 539 return this->SimplyEquals(that); 540 } 541 542 // Check if [this] and [that] overlap. 543 bool Type::Maybe(Type that) const { 544 DisallowHeapAllocation no_allocation; 545 546 if (BitsetType::IsNone(this->BitsetLub() & that.BitsetLub())) return false; 547 548 // (T1 \/ ... \/ Tn) overlaps T if (T1 overlaps T) \/ ... \/ (Tn overlaps T) 549 if (this->IsUnion()) { 550 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { 551 if (this->AsUnion()->Get(i).Maybe(that)) return true; 552 } 553 return false; 554 } 555 556 // T overlaps (T1 \/ ... \/ Tn) if (T overlaps T1) \/ ... \/ (T overlaps Tn) 557 if (that.IsUnion()) { 558 for (int i = 0, n = that.AsUnion()->Length(); i < n; ++i) { 559 if (this->Maybe(that.AsUnion()->Get(i))) return true; 560 } 561 return false; 562 } 563 564 if (this->IsBitset() && that.IsBitset()) return true; 565 566 if (this->IsRange()) { 567 if (that.IsRange()) { 568 return Overlap(this->AsRange(), that.AsRange()); 569 } 570 if (that.IsBitset()) { 571 bitset number_bits = BitsetType::NumberBits(that.AsBitset()); 572 if (number_bits == BitsetType::kNone) { 573 return false; 574 } 575 double min = std::max(BitsetType::Min(number_bits), this->Min()); 576 double max = std::min(BitsetType::Max(number_bits), this->Max()); 577 return min <= max; 578 } 579 } 580 if (that.IsRange()) { 581 return that.Maybe(*this); // This case is handled above. 582 } 583 584 if (this->IsBitset() || that.IsBitset()) return true; 585 586 return this->SimplyEquals(that); 587 } 588 589 // Return the range in [this], or [nullptr]. 590 Type Type::GetRange() const { 591 DisallowHeapAllocation no_allocation; 592 if (this->IsRange()) return *this; 593 if (this->IsUnion() && this->AsUnion()->Get(1).IsRange()) { 594 return this->AsUnion()->Get(1); 595 } 596 return nullptr; 597 } 598 599 bool UnionType::Wellformed() const { 600 DisallowHeapAllocation no_allocation; 601 // This checks the invariants of the union representation: 602 // 1. There are at least two elements. 603 // 2. The first element is a bitset, no other element is a bitset. 604 // 3. At most one element is a range, and it must be the second one. 605 // 4. No element is itself a union. 606 // 5. No element (except the bitset) is a subtype of any other. 607 // 6. If there is a range, then the bitset type does not contain 608 // plain number bits. 609 DCHECK_LE(2, this->Length()); // (1) 610 DCHECK(this->Get(0).IsBitset()); // (2a) 611 612 for (int i = 0; i < this->Length(); ++i) { 613 if (i != 0) DCHECK(!this->Get(i).IsBitset()); // (2b) 614 if (i != 1) DCHECK(!this->Get(i).IsRange()); // (3) 615 DCHECK(!this->Get(i).IsUnion()); // (4) 616 for (int j = 0; j < this->Length(); ++j) { 617 if (i != j && i != 0) DCHECK(!this->Get(i).Is(this->Get(j))); // (5) 618 } 619 } 620 DCHECK(!this->Get(1).IsRange() || 621 (BitsetType::NumberBits(this->Get(0).AsBitset()) == 622 BitsetType::kNone)); // (6) 623 return true; 624 } 625 626 // ----------------------------------------------------------------------------- 627 // Union and intersection 628 629 Type Type::Intersect(Type type1, Type type2, Zone* zone) { 630 // Fast case: bit sets. 631 if (type1.IsBitset() && type2.IsBitset()) { 632 return NewBitset(type1.AsBitset() & type2.AsBitset()); 633 } 634 635 // Fast case: top or bottom types. 636 if (type1.IsNone() || type2.IsAny()) return type1; // Shortcut. 637 if (type2.IsNone() || type1.IsAny()) return type2; // Shortcut. 638 639 // Semi-fast case. 640 if (type1.Is(type2)) return type1; 641 if (type2.Is(type1)) return type2; 642 643 // Slow case: create union. 644 645 // Semantic subtyping check - this is needed for consistency with the 646 // semi-fast case above. 647 if (type1.Is(type2)) { 648 type2 = Any(); 649 } else if (type2.Is(type1)) { 650 type1 = Any(); 651 } 652 653 bitset bits = type1.BitsetGlb() & type2.BitsetGlb(); 654 int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1; 655 int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1; 656 int size; 657 if (base::bits::SignedAddOverflow32(size1, size2, &size)) return Any(); 658 if (base::bits::SignedAddOverflow32(size, 2, &size)) return Any(); 659 UnionType* result = UnionType::New(size, zone); 660 size = 0; 661 662 // Deal with bitsets. 663 result->Set(size++, NewBitset(bits)); 664 665 RangeType::Limits lims = RangeType::Limits::Empty(); 666 size = IntersectAux(type1, type2, result, size, &lims, zone); 667 668 // If the range is not empty, then insert it into the union and 669 // remove the number bits from the bitset. 670 if (!lims.IsEmpty()) { 671 size = UpdateRange(Type::Range(lims, zone), result, size, zone); 672 673 // Remove the number bits. 674 bitset number_bits = BitsetType::NumberBits(bits); 675 bits &= ~number_bits; 676 result->Set(0, NewBitset(bits)); 677 } 678 return NormalizeUnion(result, size, zone); 679 } 680 681 int Type::UpdateRange(Type range, UnionType* result, int size, Zone* zone) { 682 if (size == 1) { 683 result->Set(size++, range); 684 } else { 685 // Make space for the range. 686 result->Set(size++, result->Get(1)); 687 result->Set(1, range); 688 } 689 690 // Remove any components that just got subsumed. 691 for (int i = 2; i < size;) { 692 if (result->Get(i).Is(range)) { 693 result->Set(i, result->Get(--size)); 694 } else { 695 ++i; 696 } 697 } 698 return size; 699 } 700 701 RangeType::Limits Type::ToLimits(bitset bits, Zone* zone) { 702 bitset number_bits = BitsetType::NumberBits(bits); 703 704 if (number_bits == BitsetType::kNone) { 705 return RangeType::Limits::Empty(); 706 } 707 708 return RangeType::Limits(BitsetType::Min(number_bits), 709 BitsetType::Max(number_bits)); 710 } 711 712 RangeType::Limits Type::IntersectRangeAndBitset(Type range, Type bitset, 713 Zone* zone) { 714 RangeType::Limits range_lims(range.AsRange()); 715 RangeType::Limits bitset_lims = ToLimits(bitset.AsBitset(), zone); 716 return RangeType::Limits::Intersect(range_lims, bitset_lims); 717 } 718 719 int Type::IntersectAux(Type lhs, Type rhs, UnionType* result, int size, 720 RangeType::Limits* lims, Zone* zone) { 721 if (lhs.IsUnion()) { 722 for (int i = 0, n = lhs.AsUnion()->Length(); i < n; ++i) { 723 size = IntersectAux(lhs.AsUnion()->Get(i), rhs, result, size, lims, zone); 724 } 725 return size; 726 } 727 if (rhs.IsUnion()) { 728 for (int i = 0, n = rhs.AsUnion()->Length(); i < n; ++i) { 729 size = IntersectAux(lhs, rhs.AsUnion()->Get(i), result, size, lims, zone); 730 } 731 return size; 732 } 733 734 if (BitsetType::IsNone(lhs.BitsetLub() & rhs.BitsetLub())) return size; 735 736 if (lhs.IsRange()) { 737 if (rhs.IsBitset()) { 738 RangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone); 739 740 if (!lim.IsEmpty()) { 741 *lims = RangeType::Limits::Union(lim, *lims); 742 } 743 return size; 744 } 745 if (rhs.IsRange()) { 746 RangeType::Limits lim = RangeType::Limits::Intersect( 747 RangeType::Limits(lhs.AsRange()), RangeType::Limits(rhs.AsRange())); 748 if (!lim.IsEmpty()) { 749 *lims = RangeType::Limits::Union(lim, *lims); 750 } 751 } 752 return size; 753 } 754 if (rhs.IsRange()) { 755 // This case is handled symmetrically above. 756 return IntersectAux(rhs, lhs, result, size, lims, zone); 757 } 758 if (lhs.IsBitset() || rhs.IsBitset()) { 759 return AddToUnion(lhs.IsBitset() ? rhs : lhs, result, size, zone); 760 } 761 if (lhs.SimplyEquals(rhs)) { 762 return AddToUnion(lhs, result, size, zone); 763 } 764 return size; 765 } 766 767 // Make sure that we produce a well-formed range and bitset: 768 // If the range is non-empty, the number bits in the bitset should be 769 // clear. Moreover, if we have a canonical range (such as Signed32), 770 // we want to produce a bitset rather than a range. 771 Type Type::NormalizeRangeAndBitset(Type range, bitset* bits, Zone* zone) { 772 // Fast path: If the bitset does not mention numbers, we can just keep the 773 // range. 774 bitset number_bits = BitsetType::NumberBits(*bits); 775 if (number_bits == 0) { 776 return range; 777 } 778 779 // If the range is semantically contained within the bitset, return None and 780 // leave the bitset untouched. 781 bitset range_lub = range.BitsetLub(); 782 if (BitsetType::Is(range_lub, *bits)) { 783 return None(); 784 } 785 786 // Slow path: reconcile the bitset range and the range. 787 double bitset_min = BitsetType::Min(number_bits); 788 double bitset_max = BitsetType::Max(number_bits); 789 790 double range_min = range.Min(); 791 double range_max = range.Max(); 792 793 // Remove the number bits from the bitset, they would just confuse us now. 794 // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which 795 // case we already returned after the subtype check above. 796 *bits &= ~number_bits; 797 798 if (range_min <= bitset_min && range_max >= bitset_max) { 799 // Bitset is contained within the range, just return the range. 800 return range; 801 } 802 803 if (bitset_min < range_min) { 804 range_min = bitset_min; 805 } 806 if (bitset_max > range_max) { 807 range_max = bitset_max; 808 } 809 return Type::Range(range_min, range_max, zone); 810 } 811 812 Type Type::NewConstant(double value, Zone* zone) { 813 if (RangeType::IsInteger(value)) { 814 return Range(value, value, zone); 815 } else if (IsMinusZero(value)) { 816 return Type::MinusZero(); 817 } else if (std::isnan(value)) { 818 return Type::NaN(); 819 } 820 821 DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value)); 822 return OtherNumberConstant(value, zone); 823 } 824 825 Type Type::NewConstant(JSHeapBroker* js_heap_broker, Handle<i::Object> value, 826 Zone* zone) { 827 ObjectRef ref(js_heap_broker, value); 828 if (ref.IsSmi()) { 829 return NewConstant(static_cast<double>(ref.AsSmi()), zone); 830 } 831 if (ref.IsHeapNumber()) { 832 return NewConstant(ref.AsHeapNumber().value(), zone); 833 } 834 if (ref.IsString() && !ref.IsInternalizedString()) { 835 return Type::String(); 836 } 837 return HeapConstant(ref.AsHeapObject(), zone); 838 } 839 840 Type Type::Union(Type type1, Type type2, Zone* zone) { 841 // Fast case: bit sets. 842 if (type1.IsBitset() && type2.IsBitset()) { 843 return NewBitset(type1.AsBitset() | type2.AsBitset()); 844 } 845 846 // Fast case: top or bottom types. 847 if (type1.IsAny() || type2.IsNone()) return type1; 848 if (type2.IsAny() || type1.IsNone()) return type2; 849 850 // Semi-fast case. 851 if (type1.Is(type2)) return type2; 852 if (type2.Is(type1)) return type1; 853 854 // Slow case: create union. 855 int size1 = type1.IsUnion() ? type1.AsUnion()->Length() : 1; 856 int size2 = type2.IsUnion() ? type2.AsUnion()->Length() : 1; 857 int size; 858 if (base::bits::SignedAddOverflow32(size1, size2, &size)) return Any(); 859 if (base::bits::SignedAddOverflow32(size, 2, &size)) return Any(); 860 UnionType* result = UnionType::New(size, zone); 861 size = 0; 862 863 // Compute the new bitset. 864 bitset new_bitset = type1.BitsetGlb() | type2.BitsetGlb(); 865 866 // Deal with ranges. 867 Type range = None(); 868 Type range1 = type1.GetRange(); 869 Type range2 = type2.GetRange(); 870 if (range1 != nullptr && range2 != nullptr) { 871 RangeType::Limits lims = 872 RangeType::Limits::Union(RangeType::Limits(range1.AsRange()), 873 RangeType::Limits(range2.AsRange())); 874 Type union_range = Type::Range(lims, zone); 875 range = NormalizeRangeAndBitset(union_range, &new_bitset, zone); 876 } else if (range1 != nullptr) { 877 range = NormalizeRangeAndBitset(range1, &new_bitset, zone); 878 } else if (range2 != nullptr) { 879 range = NormalizeRangeAndBitset(range2, &new_bitset, zone); 880 } 881 Type bits = NewBitset(new_bitset); 882 result->Set(size++, bits); 883 if (!range.IsNone()) result->Set(size++, range); 884 885 size = AddToUnion(type1, result, size, zone); 886 size = AddToUnion(type2, result, size, zone); 887 return NormalizeUnion(result, size, zone); 888 } 889 890 // Add [type] to [result] unless [type] is bitset, range, or already subsumed. 891 // Return new size of [result]. 892 int Type::AddToUnion(Type type, UnionType* result, int size, Zone* zone) { 893 if (type.IsBitset() || type.IsRange()) return size; 894 if (type.IsUnion()) { 895 for (int i = 0, n = type.AsUnion()->Length(); i < n; ++i) { 896 size = AddToUnion(type.AsUnion()->Get(i), result, size, zone); 897 } 898 return size; 899 } 900 for (int i = 0; i < size; ++i) { 901 if (type.Is(result->Get(i))) return size; 902 } 903 result->Set(size++, type); 904 return size; 905 } 906 907 Type Type::NormalizeUnion(UnionType* unioned, int size, Zone* zone) { 908 DCHECK_LE(1, size); 909 DCHECK(unioned->Get(0).IsBitset()); 910 // If the union has just one element, return it. 911 if (size == 1) { 912 return unioned->Get(0); 913 } 914 bitset bits = unioned->Get(0).AsBitset(); 915 // If the union only consists of a range, we can get rid of the union. 916 if (size == 2 && bits == BitsetType::kNone) { 917 if (unioned->Get(1).IsRange()) { 918 return Type::Range(unioned->Get(1).AsRange()->Min(), 919 unioned->Get(1).AsRange()->Max(), zone); 920 } 921 } 922 unioned->Shrink(size); 923 SLOW_DCHECK(unioned->Wellformed()); 924 return Type(unioned); 925 } 926 927 int Type::NumConstants() const { 928 DisallowHeapAllocation no_allocation; 929 if (this->IsHeapConstant() || this->IsOtherNumberConstant()) { 930 return 1; 931 } else if (this->IsUnion()) { 932 int result = 0; 933 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { 934 if (this->AsUnion()->Get(i).IsHeapConstant()) ++result; 935 } 936 return result; 937 } else { 938 return 0; 939 } 940 } 941 942 // ----------------------------------------------------------------------------- 943 // Printing. 944 945 const char* BitsetType::Name(bitset bits) { 946 switch (bits) { 947 #define RETURN_NAMED_TYPE(type, value) \ 948 case k##type: \ 949 return #type; 950 PROPER_BITSET_TYPE_LIST(RETURN_NAMED_TYPE) 951 INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_TYPE) 952 #undef RETURN_NAMED_TYPE 953 954 default: 955 return nullptr; 956 } 957 } 958 959 void BitsetType::Print(std::ostream& os, // NOLINT 960 bitset bits) { 961 DisallowHeapAllocation no_allocation; 962 const char* name = Name(bits); 963 if (name != nullptr) { 964 os << name; 965 return; 966 } 967 968 // clang-format off 969 static const bitset named_bitsets[] = { 970 #define BITSET_CONSTANT(type, value) k##type, 971 INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT) 972 PROPER_BITSET_TYPE_LIST(BITSET_CONSTANT) 973 #undef BITSET_CONSTANT 974 }; 975 // clang-format on 976 977 bool is_first = true; 978 os << "("; 979 for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) { 980 bitset subset = named_bitsets[i]; 981 if ((bits & subset) == subset) { 982 if (!is_first) os << " | "; 983 is_first = false; 984 os << Name(subset); 985 bits -= subset; 986 } 987 } 988 DCHECK_EQ(0, bits); 989 os << ")"; 990 } 991 992 void Type::PrintTo(std::ostream& os) const { 993 DisallowHeapAllocation no_allocation; 994 if (this->IsBitset()) { 995 BitsetType::Print(os, this->AsBitset()); 996 } else if (this->IsHeapConstant()) { 997 os << "HeapConstant(" << Brief(*this->AsHeapConstant()->Value()) << ")"; 998 } else if (this->IsOtherNumberConstant()) { 999 os << "OtherNumberConstant(" << this->AsOtherNumberConstant()->Value() 1000 << ")"; 1001 } else if (this->IsRange()) { 1002 std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed); 1003 std::streamsize saved_precision = os.precision(0); 1004 os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max() 1005 << ")"; 1006 os.flags(saved_flags); 1007 os.precision(saved_precision); 1008 } else if (this->IsUnion()) { 1009 os << "("; 1010 for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) { 1011 Type type_i = this->AsUnion()->Get(i); 1012 if (i > 0) os << " | " << type_i; 1013 } 1014 os << ")"; 1015 } else if (this->IsTuple()) { 1016 os << "<"; 1017 for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) { 1018 Type type_i = this->AsTuple()->Element(i); 1019 if (i > 0) os << ", " << type_i; 1020 } 1021 os << ">"; 1022 } else { 1023 UNREACHABLE(); 1024 } 1025 } 1026 1027 #ifdef DEBUG 1028 void Type::Print() const { 1029 StdoutStream os; 1030 PrintTo(os); 1031 os << std::endl; 1032 } 1033 void BitsetType::Print(bitset bits) { 1034 StdoutStream os; 1035 Print(os, bits); 1036 os << std::endl; 1037 } 1038 #endif 1039 1040 BitsetType::bitset BitsetType::SignedSmall() { 1041 return SmiValuesAre31Bits() ? kSigned31 : kSigned32; 1042 } 1043 1044 BitsetType::bitset BitsetType::UnsignedSmall() { 1045 return SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31; 1046 } 1047 1048 // static 1049 Type Type::Tuple(Type first, Type second, Type third, Zone* zone) { 1050 TupleType* tuple = TupleType::New(3, zone); 1051 tuple->InitElement(0, first); 1052 tuple->InitElement(1, second); 1053 tuple->InitElement(2, third); 1054 return FromTypeBase(tuple); 1055 } 1056 1057 // static 1058 Type Type::OtherNumberConstant(double value, Zone* zone) { 1059 return FromTypeBase(OtherNumberConstantType::New(value, zone)); 1060 } 1061 1062 // static 1063 Type Type::HeapConstant(JSHeapBroker* js_heap_broker, Handle<i::Object> value, 1064 Zone* zone) { 1065 return FromTypeBase( 1066 HeapConstantType::New(HeapObjectRef(js_heap_broker, value), zone)); 1067 } 1068 1069 // static 1070 Type Type::HeapConstant(const HeapObjectRef& value, Zone* zone) { 1071 return HeapConstantType::New(value, zone); 1072 } 1073 1074 // static 1075 Type Type::Range(double min, double max, Zone* zone) { 1076 return FromTypeBase(RangeType::New(min, max, zone)); 1077 } 1078 1079 // static 1080 Type Type::Range(RangeType::Limits lims, Zone* zone) { 1081 return FromTypeBase(RangeType::New(lims, zone)); 1082 } 1083 1084 // static 1085 Type Type::Union(int length, Zone* zone) { 1086 return FromTypeBase(UnionType::New(length, zone)); 1087 } 1088 1089 const HeapConstantType* Type::AsHeapConstant() const { 1090 DCHECK(IsKind(TypeBase::kHeapConstant)); 1091 return static_cast<const HeapConstantType*>(ToTypeBase()); 1092 } 1093 1094 const OtherNumberConstantType* Type::AsOtherNumberConstant() const { 1095 DCHECK(IsKind(TypeBase::kOtherNumberConstant)); 1096 return static_cast<const OtherNumberConstantType*>(ToTypeBase()); 1097 } 1098 1099 const RangeType* Type::AsRange() const { 1100 DCHECK(IsKind(TypeBase::kRange)); 1101 return static_cast<const RangeType*>(ToTypeBase()); 1102 } 1103 1104 const TupleType* Type::AsTuple() const { 1105 DCHECK(IsKind(TypeBase::kTuple)); 1106 return static_cast<const TupleType*>(ToTypeBase()); 1107 } 1108 1109 const UnionType* Type::AsUnion() const { 1110 DCHECK(IsKind(TypeBase::kUnion)); 1111 return static_cast<const UnionType*>(ToTypeBase()); 1112 } 1113 1114 std::ostream& operator<<(std::ostream& os, Type type) { 1115 type.PrintTo(os); 1116 return os; 1117 } 1118 1119 } // namespace compiler 1120 } // namespace internal 1121 } // namespace v8 1122