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