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