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 #ifndef V8_AST_AST_TYPES_H_ 6 #define V8_AST_AST_TYPES_H_ 7 8 #include "src/conversions.h" 9 #include "src/handles.h" 10 #include "src/objects.h" 11 #include "src/ostreams.h" 12 13 namespace v8 { 14 namespace internal { 15 16 // SUMMARY 17 // 18 // A simple type system for compiler-internal use. It is based entirely on 19 // union types, and all subtyping hence amounts to set inclusion. Besides the 20 // obvious primitive types and some predefined unions, the type language also 21 // can express class types (a.k.a. specific maps) and singleton types (i.e., 22 // concrete constants). 23 // 24 // Types consist of two dimensions: semantic (value range) and representation. 25 // Both are related through subtyping. 26 // 27 // 28 // SEMANTIC DIMENSION 29 // 30 // The following equations and inequations hold for the semantic axis: 31 // 32 // None <= T 33 // T <= Any 34 // 35 // Number = Signed32 \/ Unsigned32 \/ Double 36 // Smi <= Signed32 37 // Name = String \/ Symbol 38 // UniqueName = InternalizedString \/ Symbol 39 // InternalizedString < String 40 // 41 // Receiver = Object \/ Proxy 42 // Array < Object 43 // Function < Object 44 // RegExp < Object 45 // OtherUndetectable < Object 46 // DetectableReceiver = Receiver - OtherUndetectable 47 // 48 // Class(map) < T iff instance_type(map) < T 49 // Constant(x) < T iff instance_type(map(x)) < T 50 // Array(T) < Array 51 // Function(R, S, T0, T1, ...) < Function 52 // Context(T) < Internal 53 // 54 // Both structural Array and Function types are invariant in all parameters; 55 // relaxing this would make Union and Intersect operations more involved. 56 // There is no subtyping relation between Array, Function, or Context types 57 // and respective Constant types, since these types cannot be reconstructed 58 // for arbitrary heap values. 59 // Note also that Constant(x) < Class(map(x)) does _not_ hold, since x's map can 60 // change! (Its instance type cannot, however.) 61 // TODO(rossberg): the latter is not currently true for proxies, because of fix, 62 // but will hold once we implement direct proxies. 63 // However, we also define a 'temporal' variant of the subtyping relation that 64 // considers the _current_ state only, i.e., Constant(x) <_now Class(map(x)). 65 // 66 // 67 // REPRESENTATIONAL DIMENSION 68 // 69 // For the representation axis, the following holds: 70 // 71 // None <= R 72 // R <= Any 73 // 74 // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ 75 // UntaggedInt16 \/ UntaggedInt32 76 // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64 77 // UntaggedNumber = UntaggedInt \/ UntaggedFloat 78 // Untagged = UntaggedNumber \/ UntaggedPtr 79 // Tagged = TaggedInt \/ TaggedPtr 80 // 81 // Subtyping relates the two dimensions, for example: 82 // 83 // Number <= Tagged \/ UntaggedNumber 84 // Object <= TaggedPtr \/ UntaggedPtr 85 // 86 // That holds because the semantic type constructors defined by the API create 87 // types that allow for all possible representations, and dually, the ones for 88 // representation types initially include all semantic ranges. Representations 89 // can then e.g. be narrowed for a given semantic type using intersection: 90 // 91 // SignedSmall /\ TaggedInt (a 'smi') 92 // Number /\ TaggedPtr (a heap number) 93 // 94 // 95 // RANGE TYPES 96 // 97 // A range type represents a continuous integer interval by its minimum and 98 // maximum value. Either value may be an infinity, in which case that infinity 99 // itself is also included in the range. A range never contains NaN or -0. 100 // 101 // If a value v happens to be an integer n, then Constant(v) is considered a 102 // subtype of Range(n, n) (and therefore also a subtype of any larger range). 103 // In order to avoid large unions, however, it is usually a good idea to use 104 // Range rather than Constant. 105 // 106 // 107 // PREDICATES 108 // 109 // There are two main functions for testing types: 110 // 111 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) 112 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) 113 // 114 // Typically, the former is to be used to select representations (e.g., via 115 // T->Is(SignedSmall())), and the latter to check whether a specific case needs 116 // handling (e.g., via T->Maybe(Number())). 117 // 118 // There is no functionality to discover whether a type is a leaf in the 119 // lattice. That is intentional. It should always be possible to refine the 120 // lattice (e.g., splitting up number types further) without invalidating any 121 // existing assumptions or tests. 122 // Consequently, do not normally use Equals for type tests, always use Is! 123 // 124 // The NowIs operator implements state-sensitive subtying, as described above. 125 // Any compilation decision based on such temporary properties requires runtime 126 // guarding! 127 // 128 // 129 // PROPERTIES 130 // 131 // Various formal properties hold for constructors, operators, and predicates 132 // over types. For example, constructors are injective and subtyping is a 133 // complete partial order. 134 // 135 // See test/cctest/test-types.cc for a comprehensive executable specification, 136 // especially with respect to the properties of the more exotic 'temporal' 137 // constructors and predicates (those prefixed 'Now'). 138 // 139 // 140 // IMPLEMENTATION 141 // 142 // Internally, all 'primitive' types, and their unions, are represented as 143 // bitsets. Bit 0 is reserved for tagging. Class is a heap pointer to the 144 // respective map. Only structured types require allocation. 145 // Note that the bitset representation is closed under both Union and Intersect. 146 147 // ----------------------------------------------------------------------------- 148 // Values for bitset types 149 150 // clang-format off 151 152 #define AST_MASK_BITSET_TYPE_LIST(V) \ 153 V(Representation, 0xffc00000u) \ 154 V(Semantic, 0x003ffffeu) 155 156 #define AST_REPRESENTATION(k) ((k) & AstBitsetType::kRepresentation) 157 #define AST_SEMANTIC(k) ((k) & AstBitsetType::kSemantic) 158 159 #define AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ 160 V(None, 0) \ 161 V(UntaggedBit, 1u << 22 | kSemantic) \ 162 V(UntaggedIntegral8, 1u << 23 | kSemantic) \ 163 V(UntaggedIntegral16, 1u << 24 | kSemantic) \ 164 V(UntaggedIntegral32, 1u << 25 | kSemantic) \ 165 V(UntaggedFloat32, 1u << 26 | kSemantic) \ 166 V(UntaggedFloat64, 1u << 27 | kSemantic) \ 167 V(UntaggedSimd128, 1u << 28 | kSemantic) \ 168 V(UntaggedPointer, 1u << 29 | kSemantic) \ 169 V(TaggedSigned, 1u << 30 | kSemantic) \ 170 V(TaggedPointer, 1u << 31 | kSemantic) \ 171 \ 172 V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \ 173 kUntaggedIntegral16 | kUntaggedIntegral32) \ 174 V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ 175 V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \ 176 V(Untagged, kUntaggedNumber | kUntaggedPointer) \ 177 V(Tagged, kTaggedSigned | kTaggedPointer) 178 179 #define AST_INTERNAL_BITSET_TYPE_LIST(V) \ 180 V(OtherUnsigned31, 1u << 1 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 181 V(OtherUnsigned32, 1u << 2 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 182 V(OtherSigned32, 1u << 3 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 183 V(OtherNumber, 1u << 4 | AST_REPRESENTATION(kTagged | kUntaggedNumber)) 184 185 #define AST_SEMANTIC_BITSET_TYPE_LIST(V) \ 186 V(Negative31, 1u << 5 | \ 187 AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 188 V(Null, 1u << 6 | AST_REPRESENTATION(kTaggedPointer)) \ 189 V(Undefined, 1u << 7 | AST_REPRESENTATION(kTaggedPointer)) \ 190 V(Boolean, 1u << 8 | AST_REPRESENTATION(kTaggedPointer)) \ 191 V(Unsigned30, 1u << 9 | \ 192 AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 193 V(MinusZero, 1u << 10 | \ 194 AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 195 V(NaN, 1u << 11 | \ 196 AST_REPRESENTATION(kTagged | kUntaggedNumber)) \ 197 V(Symbol, 1u << 12 | AST_REPRESENTATION(kTaggedPointer)) \ 198 V(InternalizedString, 1u << 13 | AST_REPRESENTATION(kTaggedPointer)) \ 199 V(OtherString, 1u << 14 | AST_REPRESENTATION(kTaggedPointer)) \ 200 V(Simd, 1u << 15 | AST_REPRESENTATION(kTaggedPointer)) \ 201 V(OtherObject, 1u << 17 | AST_REPRESENTATION(kTaggedPointer)) \ 202 V(OtherUndetectable, 1u << 16 | AST_REPRESENTATION(kTaggedPointer)) \ 203 V(Proxy, 1u << 18 | AST_REPRESENTATION(kTaggedPointer)) \ 204 V(Function, 1u << 19 | AST_REPRESENTATION(kTaggedPointer)) \ 205 V(Hole, 1u << 20 | AST_REPRESENTATION(kTaggedPointer)) \ 206 V(OtherInternal, 1u << 21 | \ 207 AST_REPRESENTATION(kTagged | kUntagged)) \ 208 \ 209 V(Signed31, kUnsigned30 | kNegative31) \ 210 V(Signed32, kSigned31 | kOtherUnsigned31 | \ 211 kOtherSigned32) \ 212 V(Signed32OrMinusZero, kSigned32 | kMinusZero) \ 213 V(Signed32OrMinusZeroOrNaN, kSigned32 | kMinusZero | kNaN) \ 214 V(Negative32, kNegative31 | kOtherSigned32) \ 215 V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \ 216 V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \ 217 kOtherUnsigned32) \ 218 V(Unsigned32OrMinusZero, kUnsigned32 | kMinusZero) \ 219 V(Unsigned32OrMinusZeroOrNaN, kUnsigned32 | kMinusZero | kNaN) \ 220 V(Integral32, kSigned32 | kUnsigned32) \ 221 V(PlainNumber, kIntegral32 | kOtherNumber) \ 222 V(OrderedNumber, kPlainNumber | kMinusZero) \ 223 V(MinusZeroOrNaN, kMinusZero | kNaN) \ 224 V(Number, kOrderedNumber | kNaN) \ 225 V(String, kInternalizedString | kOtherString) \ 226 V(UniqueName, kSymbol | kInternalizedString) \ 227 V(Name, kSymbol | kString) \ 228 V(BooleanOrNumber, kBoolean | kNumber) \ 229 V(BooleanOrNullOrNumber, kBooleanOrNumber | kNull) \ 230 V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \ 231 V(NullOrNumber, kNull | kNumber) \ 232 V(NullOrUndefined, kNull | kUndefined) \ 233 V(Undetectable, kNullOrUndefined | kOtherUndetectable) \ 234 V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean | kHole) \ 235 V(NumberOrSimdOrString, kNumber | kSimd | kString) \ 236 V(NumberOrString, kNumber | kString) \ 237 V(NumberOrUndefined, kNumber | kUndefined) \ 238 V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \ 239 V(Primitive, kSymbol | kSimd | kPlainPrimitive) \ 240 V(DetectableReceiver, kFunction | kOtherObject | kProxy) \ 241 V(Object, kFunction | kOtherObject | kOtherUndetectable) \ 242 V(Receiver, kObject | kProxy) \ 243 V(StringOrReceiver, kString | kReceiver) \ 244 V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \ 245 kReceiver) \ 246 V(Internal, kHole | kOtherInternal) \ 247 V(NonInternal, kPrimitive | kReceiver) \ 248 V(NonNumber, kUnique | kString | kInternal) \ 249 V(Any, 0xfffffffeu) 250 251 // clang-format on 252 253 /* 254 * The following diagrams show how integers (in the mathematical sense) are 255 * divided among the different atomic numerical types. 256 * 257 * ON OS32 N31 U30 OU31 OU32 ON 258 * ______[_______[_______[_______[_______[_______[_______ 259 * -2^31 -2^30 0 2^30 2^31 2^32 260 * 261 * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. 262 * 263 * Some of the atomic numerical bitsets are internal only (see 264 * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in 265 * union with certain other bitsets. For instance, OtherNumber should only 266 * occur as part of PlainNumber. 267 */ 268 269 #define AST_PROPER_BITSET_TYPE_LIST(V) \ 270 AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ 271 AST_SEMANTIC_BITSET_TYPE_LIST(V) 272 273 #define AST_BITSET_TYPE_LIST(V) \ 274 AST_MASK_BITSET_TYPE_LIST(V) \ 275 AST_REPRESENTATION_BITSET_TYPE_LIST(V) \ 276 AST_INTERNAL_BITSET_TYPE_LIST(V) \ 277 AST_SEMANTIC_BITSET_TYPE_LIST(V) 278 279 class AstType; 280 281 // ----------------------------------------------------------------------------- 282 // Bitset types (internal). 283 284 class AstBitsetType { 285 public: 286 typedef uint32_t bitset; // Internal 287 288 enum : uint32_t { 289 #define DECLARE_TYPE(type, value) k##type = (value), 290 AST_BITSET_TYPE_LIST(DECLARE_TYPE) 291 #undef DECLARE_TYPE 292 kUnusedEOL = 0 293 }; 294 295 static bitset SignedSmall(); 296 static bitset UnsignedSmall(); 297 298 bitset Bitset() { 299 return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); 300 } 301 302 static bool IsInhabited(bitset bits) { 303 return AST_SEMANTIC(bits) != kNone && AST_REPRESENTATION(bits) != kNone; 304 } 305 306 static bool SemanticIsInhabited(bitset bits) { 307 return AST_SEMANTIC(bits) != kNone; 308 } 309 310 static bool Is(bitset bits1, bitset bits2) { 311 return (bits1 | bits2) == bits2; 312 } 313 314 static double Min(bitset); 315 static double Max(bitset); 316 317 static bitset Glb(AstType* type); // greatest lower bound that's a bitset 318 static bitset Glb(double min, double max); 319 static bitset Lub(AstType* type); // least upper bound that's a bitset 320 static bitset Lub(i::Map* map); 321 static bitset Lub(i::Object* value); 322 static bitset Lub(double value); 323 static bitset Lub(double min, double max); 324 static bitset ExpandInternals(bitset bits); 325 326 static const char* Name(bitset); 327 static void Print(std::ostream& os, bitset); // NOLINT 328 #ifdef DEBUG 329 static void Print(bitset); 330 #endif 331 332 static bitset NumberBits(bitset bits); 333 334 static bool IsBitset(AstType* type) { 335 return reinterpret_cast<uintptr_t>(type) & 1; 336 } 337 338 static AstType* NewForTesting(bitset bits) { return New(bits); } 339 340 private: 341 friend class AstType; 342 343 static AstType* New(bitset bits) { 344 return reinterpret_cast<AstType*>(static_cast<uintptr_t>(bits | 1u)); 345 } 346 347 struct Boundary { 348 bitset internal; 349 bitset external; 350 double min; 351 }; 352 static const Boundary BoundariesArray[]; 353 static inline const Boundary* Boundaries(); 354 static inline size_t BoundariesSize(); 355 }; 356 357 // ----------------------------------------------------------------------------- 358 // Superclass for non-bitset types (internal). 359 class AstTypeBase { 360 protected: 361 friend class AstType; 362 363 enum Kind { 364 kClass, 365 kConstant, 366 kContext, 367 kArray, 368 kFunction, 369 kTuple, 370 kUnion, 371 kRange 372 }; 373 374 Kind kind() const { return kind_; } 375 explicit AstTypeBase(Kind kind) : kind_(kind) {} 376 377 static bool IsKind(AstType* type, Kind kind) { 378 if (AstBitsetType::IsBitset(type)) return false; 379 AstTypeBase* base = reinterpret_cast<AstTypeBase*>(type); 380 return base->kind() == kind; 381 } 382 383 // The hacky conversion to/from AstType*. 384 static AstType* AsType(AstTypeBase* type) { 385 return reinterpret_cast<AstType*>(type); 386 } 387 static AstTypeBase* FromType(AstType* type) { 388 return reinterpret_cast<AstTypeBase*>(type); 389 } 390 391 private: 392 Kind kind_; 393 }; 394 395 // ----------------------------------------------------------------------------- 396 // Class types. 397 398 class AstClassType : public AstTypeBase { 399 public: 400 i::Handle<i::Map> Map() { return map_; } 401 402 private: 403 friend class AstType; 404 friend class AstBitsetType; 405 406 static AstType* New(i::Handle<i::Map> map, Zone* zone) { 407 return AsType(new (zone->New(sizeof(AstClassType))) 408 AstClassType(AstBitsetType::Lub(*map), map)); 409 } 410 411 static AstClassType* cast(AstType* type) { 412 DCHECK(IsKind(type, kClass)); 413 return static_cast<AstClassType*>(FromType(type)); 414 } 415 416 AstClassType(AstBitsetType::bitset bitset, i::Handle<i::Map> map) 417 : AstTypeBase(kClass), bitset_(bitset), map_(map) {} 418 419 AstBitsetType::bitset Lub() { return bitset_; } 420 421 AstBitsetType::bitset bitset_; 422 Handle<i::Map> map_; 423 }; 424 425 // ----------------------------------------------------------------------------- 426 // Constant types. 427 428 class AstConstantType : public AstTypeBase { 429 public: 430 i::Handle<i::Object> Value() { return object_; } 431 432 private: 433 friend class AstType; 434 friend class AstBitsetType; 435 436 static AstType* New(i::Handle<i::Object> value, Zone* zone) { 437 AstBitsetType::bitset bitset = AstBitsetType::Lub(*value); 438 return AsType(new (zone->New(sizeof(AstConstantType))) 439 AstConstantType(bitset, value)); 440 } 441 442 static AstConstantType* cast(AstType* type) { 443 DCHECK(IsKind(type, kConstant)); 444 return static_cast<AstConstantType*>(FromType(type)); 445 } 446 447 AstConstantType(AstBitsetType::bitset bitset, i::Handle<i::Object> object) 448 : AstTypeBase(kConstant), bitset_(bitset), object_(object) {} 449 450 AstBitsetType::bitset Lub() { return bitset_; } 451 452 AstBitsetType::bitset bitset_; 453 Handle<i::Object> object_; 454 }; 455 // TODO(neis): Also cache value if numerical. 456 // TODO(neis): Allow restricting the representation. 457 458 // ----------------------------------------------------------------------------- 459 // Range types. 460 461 class AstRangeType : public AstTypeBase { 462 public: 463 struct Limits { 464 double min; 465 double max; 466 Limits(double min, double max) : min(min), max(max) {} 467 explicit Limits(AstRangeType* range) 468 : min(range->Min()), max(range->Max()) {} 469 bool IsEmpty(); 470 static Limits Empty() { return Limits(1, 0); } 471 static Limits Intersect(Limits lhs, Limits rhs); 472 static Limits Union(Limits lhs, Limits rhs); 473 }; 474 475 double Min() { return limits_.min; } 476 double Max() { return limits_.max; } 477 478 private: 479 friend class AstType; 480 friend class AstBitsetType; 481 friend class AstUnionType; 482 483 static AstType* New(double min, double max, 484 AstBitsetType::bitset representation, Zone* zone) { 485 return New(Limits(min, max), representation, zone); 486 } 487 488 static bool IsInteger(double x) { 489 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. 490 } 491 492 static AstType* New(Limits lim, AstBitsetType::bitset representation, 493 Zone* zone) { 494 DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); 495 DCHECK(lim.min <= lim.max); 496 DCHECK(AST_REPRESENTATION(representation) == representation); 497 AstBitsetType::bitset bits = 498 AST_SEMANTIC(AstBitsetType::Lub(lim.min, lim.max)) | representation; 499 500 return AsType(new (zone->New(sizeof(AstRangeType))) 501 AstRangeType(bits, lim)); 502 } 503 504 static AstRangeType* cast(AstType* type) { 505 DCHECK(IsKind(type, kRange)); 506 return static_cast<AstRangeType*>(FromType(type)); 507 } 508 509 AstRangeType(AstBitsetType::bitset bitset, Limits limits) 510 : AstTypeBase(kRange), bitset_(bitset), limits_(limits) {} 511 512 AstBitsetType::bitset Lub() { return bitset_; } 513 514 AstBitsetType::bitset bitset_; 515 Limits limits_; 516 }; 517 518 // ----------------------------------------------------------------------------- 519 // Context types. 520 521 class AstContextType : public AstTypeBase { 522 public: 523 AstType* Outer() { return outer_; } 524 525 private: 526 friend class AstType; 527 528 static AstType* New(AstType* outer, Zone* zone) { 529 return AsType(new (zone->New(sizeof(AstContextType))) 530 AstContextType(outer)); // NOLINT 531 } 532 533 static AstContextType* cast(AstType* type) { 534 DCHECK(IsKind(type, kContext)); 535 return static_cast<AstContextType*>(FromType(type)); 536 } 537 538 explicit AstContextType(AstType* outer) 539 : AstTypeBase(kContext), outer_(outer) {} 540 541 AstType* outer_; 542 }; 543 544 // ----------------------------------------------------------------------------- 545 // Array types. 546 547 class AstArrayType : public AstTypeBase { 548 public: 549 AstType* Element() { return element_; } 550 551 private: 552 friend class AstType; 553 554 explicit AstArrayType(AstType* element) 555 : AstTypeBase(kArray), element_(element) {} 556 557 static AstType* New(AstType* element, Zone* zone) { 558 return AsType(new (zone->New(sizeof(AstArrayType))) AstArrayType(element)); 559 } 560 561 static AstArrayType* cast(AstType* type) { 562 DCHECK(IsKind(type, kArray)); 563 return static_cast<AstArrayType*>(FromType(type)); 564 } 565 566 AstType* element_; 567 }; 568 569 // ----------------------------------------------------------------------------- 570 // Superclass for types with variable number of type fields. 571 class AstStructuralType : public AstTypeBase { 572 public: 573 int LengthForTesting() { return Length(); } 574 575 protected: 576 friend class AstType; 577 578 int Length() { return length_; } 579 580 AstType* Get(int i) { 581 DCHECK(0 <= i && i < this->Length()); 582 return elements_[i]; 583 } 584 585 void Set(int i, AstType* type) { 586 DCHECK(0 <= i && i < this->Length()); 587 elements_[i] = type; 588 } 589 590 void Shrink(int length) { 591 DCHECK(2 <= length && length <= this->Length()); 592 length_ = length; 593 } 594 595 AstStructuralType(Kind kind, int length, i::Zone* zone) 596 : AstTypeBase(kind), length_(length) { 597 elements_ = 598 reinterpret_cast<AstType**>(zone->New(sizeof(AstType*) * length)); 599 } 600 601 private: 602 int length_; 603 AstType** elements_; 604 }; 605 606 // ----------------------------------------------------------------------------- 607 // Function types. 608 609 class AstFunctionType : public AstStructuralType { 610 public: 611 int Arity() { return this->Length() - 2; } 612 AstType* Result() { return this->Get(0); } 613 AstType* Receiver() { return this->Get(1); } 614 AstType* Parameter(int i) { return this->Get(2 + i); } 615 616 void InitParameter(int i, AstType* type) { this->Set(2 + i, type); } 617 618 private: 619 friend class AstType; 620 621 AstFunctionType(AstType* result, AstType* receiver, int arity, Zone* zone) 622 : AstStructuralType(kFunction, 2 + arity, zone) { 623 Set(0, result); 624 Set(1, receiver); 625 } 626 627 static AstType* New(AstType* result, AstType* receiver, int arity, 628 Zone* zone) { 629 return AsType(new (zone->New(sizeof(AstFunctionType))) 630 AstFunctionType(result, receiver, arity, zone)); 631 } 632 633 static AstFunctionType* cast(AstType* type) { 634 DCHECK(IsKind(type, kFunction)); 635 return static_cast<AstFunctionType*>(FromType(type)); 636 } 637 }; 638 639 // ----------------------------------------------------------------------------- 640 // Tuple types. 641 642 class AstTupleType : public AstStructuralType { 643 public: 644 int Arity() { return this->Length(); } 645 AstType* Element(int i) { return this->Get(i); } 646 647 void InitElement(int i, AstType* type) { this->Set(i, type); } 648 649 private: 650 friend class AstType; 651 652 AstTupleType(int length, Zone* zone) 653 : AstStructuralType(kTuple, length, zone) {} 654 655 static AstType* New(int length, Zone* zone) { 656 return AsType(new (zone->New(sizeof(AstTupleType))) 657 AstTupleType(length, zone)); 658 } 659 660 static AstTupleType* cast(AstType* type) { 661 DCHECK(IsKind(type, kTuple)); 662 return static_cast<AstTupleType*>(FromType(type)); 663 } 664 }; 665 666 // ----------------------------------------------------------------------------- 667 // Union types (internal). 668 // A union is a structured type with the following invariants: 669 // - its length is at least 2 670 // - at most one field is a bitset, and it must go into index 0 671 // - no field is a union 672 // - no field is a subtype of any other field 673 class AstUnionType : public AstStructuralType { 674 private: 675 friend AstType; 676 friend AstBitsetType; 677 678 AstUnionType(int length, Zone* zone) 679 : AstStructuralType(kUnion, length, zone) {} 680 681 static AstType* New(int length, Zone* zone) { 682 return AsType(new (zone->New(sizeof(AstUnionType))) 683 AstUnionType(length, zone)); 684 } 685 686 static AstUnionType* cast(AstType* type) { 687 DCHECK(IsKind(type, kUnion)); 688 return static_cast<AstUnionType*>(FromType(type)); 689 } 690 691 bool Wellformed(); 692 }; 693 694 class AstType { 695 public: 696 typedef AstBitsetType::bitset bitset; // Internal 697 698 // Constructors. 699 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ 700 static AstType* type() { return AstBitsetType::New(AstBitsetType::k##type); } 701 AST_PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) 702 #undef DEFINE_TYPE_CONSTRUCTOR 703 704 static AstType* SignedSmall() { 705 return AstBitsetType::New(AstBitsetType::SignedSmall()); 706 } 707 static AstType* UnsignedSmall() { 708 return AstBitsetType::New(AstBitsetType::UnsignedSmall()); 709 } 710 711 static AstType* Class(i::Handle<i::Map> map, Zone* zone) { 712 return AstClassType::New(map, zone); 713 } 714 static AstType* Constant(i::Handle<i::Object> value, Zone* zone) { 715 return AstConstantType::New(value, zone); 716 } 717 static AstType* Range(double min, double max, Zone* zone) { 718 return AstRangeType::New(min, max, 719 AST_REPRESENTATION(AstBitsetType::kTagged | 720 AstBitsetType::kUntaggedNumber), 721 zone); 722 } 723 static AstType* Context(AstType* outer, Zone* zone) { 724 return AstContextType::New(outer, zone); 725 } 726 static AstType* Array(AstType* element, Zone* zone) { 727 return AstArrayType::New(element, zone); 728 } 729 static AstType* Function(AstType* result, AstType* receiver, int arity, 730 Zone* zone) { 731 return AstFunctionType::New(result, receiver, arity, zone); 732 } 733 static AstType* Function(AstType* result, Zone* zone) { 734 return Function(result, Any(), 0, zone); 735 } 736 static AstType* Function(AstType* result, AstType* param0, Zone* zone) { 737 AstType* function = Function(result, Any(), 1, zone); 738 function->AsFunction()->InitParameter(0, param0); 739 return function; 740 } 741 static AstType* Function(AstType* result, AstType* param0, AstType* param1, 742 Zone* zone) { 743 AstType* function = Function(result, Any(), 2, zone); 744 function->AsFunction()->InitParameter(0, param0); 745 function->AsFunction()->InitParameter(1, param1); 746 return function; 747 } 748 static AstType* Function(AstType* result, AstType* param0, AstType* param1, 749 AstType* param2, Zone* zone) { 750 AstType* function = Function(result, Any(), 3, zone); 751 function->AsFunction()->InitParameter(0, param0); 752 function->AsFunction()->InitParameter(1, param1); 753 function->AsFunction()->InitParameter(2, param2); 754 return function; 755 } 756 static AstType* Function(AstType* result, int arity, AstType** params, 757 Zone* zone) { 758 AstType* function = Function(result, Any(), arity, zone); 759 for (int i = 0; i < arity; ++i) { 760 function->AsFunction()->InitParameter(i, params[i]); 761 } 762 return function; 763 } 764 static AstType* Tuple(AstType* first, AstType* second, AstType* third, 765 Zone* zone) { 766 AstType* tuple = AstTupleType::New(3, zone); 767 tuple->AsTuple()->InitElement(0, first); 768 tuple->AsTuple()->InitElement(1, second); 769 tuple->AsTuple()->InitElement(2, third); 770 return tuple; 771 } 772 773 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \ 774 static AstType* Name(Isolate* isolate, Zone* zone); 775 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE) 776 #undef CONSTRUCT_SIMD_TYPE 777 778 static AstType* Union(AstType* type1, AstType* type2, Zone* zone); 779 static AstType* Intersect(AstType* type1, AstType* type2, Zone* zone); 780 781 static AstType* Of(double value, Zone* zone) { 782 return AstBitsetType::New( 783 AstBitsetType::ExpandInternals(AstBitsetType::Lub(value))); 784 } 785 static AstType* Of(i::Object* value, Zone* zone) { 786 return AstBitsetType::New( 787 AstBitsetType::ExpandInternals(AstBitsetType::Lub(value))); 788 } 789 static AstType* Of(i::Handle<i::Object> value, Zone* zone) { 790 return Of(*value, zone); 791 } 792 793 static AstType* For(i::Map* map) { 794 return AstBitsetType::New( 795 AstBitsetType::ExpandInternals(AstBitsetType::Lub(map))); 796 } 797 static AstType* For(i::Handle<i::Map> map) { return For(*map); } 798 799 // Extraction of components. 800 static AstType* Representation(AstType* t, Zone* zone); 801 static AstType* Semantic(AstType* t, Zone* zone); 802 803 // Predicates. 804 bool IsInhabited() { return AstBitsetType::IsInhabited(this->BitsetLub()); } 805 806 bool Is(AstType* that) { return this == that || this->SlowIs(that); } 807 bool Maybe(AstType* that); 808 bool Equals(AstType* that) { return this->Is(that) && that->Is(this); } 809 810 // Equivalent to Constant(val)->Is(this), but avoiding allocation. 811 bool Contains(i::Object* val); 812 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } 813 814 // State-dependent versions of the above that consider subtyping between 815 // a constant and its map class. 816 static AstType* NowOf(i::Object* value, Zone* zone); 817 static AstType* NowOf(i::Handle<i::Object> value, Zone* zone) { 818 return NowOf(*value, zone); 819 } 820 bool NowIs(AstType* that); 821 bool NowContains(i::Object* val); 822 bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } 823 824 bool NowStable(); 825 826 // Inspection. 827 bool IsRange() { return IsKind(AstTypeBase::kRange); } 828 bool IsClass() { return IsKind(AstTypeBase::kClass); } 829 bool IsConstant() { return IsKind(AstTypeBase::kConstant); } 830 bool IsContext() { return IsKind(AstTypeBase::kContext); } 831 bool IsArray() { return IsKind(AstTypeBase::kArray); } 832 bool IsFunction() { return IsKind(AstTypeBase::kFunction); } 833 bool IsTuple() { return IsKind(AstTypeBase::kTuple); } 834 835 AstClassType* AsClass() { return AstClassType::cast(this); } 836 AstConstantType* AsConstant() { return AstConstantType::cast(this); } 837 AstRangeType* AsRange() { return AstRangeType::cast(this); } 838 AstContextType* AsContext() { return AstContextType::cast(this); } 839 AstArrayType* AsArray() { return AstArrayType::cast(this); } 840 AstFunctionType* AsFunction() { return AstFunctionType::cast(this); } 841 AstTupleType* AsTuple() { return AstTupleType::cast(this); } 842 843 // Minimum and maximum of a numeric type. 844 // These functions do not distinguish between -0 and +0. If the type equals 845 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these 846 // functions on subtypes of Number. 847 double Min(); 848 double Max(); 849 850 // Extracts a range from the type: if the type is a range or a union 851 // containing a range, that range is returned; otherwise, NULL is returned. 852 AstType* GetRange(); 853 854 static bool IsInteger(i::Object* x); 855 static bool IsInteger(double x) { 856 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. 857 } 858 859 int NumClasses(); 860 int NumConstants(); 861 862 template <class T> 863 class Iterator { 864 public: 865 bool Done() const { return index_ < 0; } 866 i::Handle<T> Current(); 867 void Advance(); 868 869 private: 870 friend class AstType; 871 872 Iterator() : index_(-1) {} 873 explicit Iterator(AstType* type) : type_(type), index_(-1) { Advance(); } 874 875 inline bool matches(AstType* type); 876 inline AstType* get_type(); 877 878 AstType* type_; 879 int index_; 880 }; 881 882 Iterator<i::Map> Classes() { 883 if (this->IsBitset()) return Iterator<i::Map>(); 884 return Iterator<i::Map>(this); 885 } 886 Iterator<i::Object> Constants() { 887 if (this->IsBitset()) return Iterator<i::Object>(); 888 return Iterator<i::Object>(this); 889 } 890 891 // Printing. 892 893 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; 894 895 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT 896 897 #ifdef DEBUG 898 void Print(); 899 #endif 900 901 // Helpers for testing. 902 bool IsBitsetForTesting() { return IsBitset(); } 903 bool IsUnionForTesting() { return IsUnion(); } 904 bitset AsBitsetForTesting() { return AsBitset(); } 905 AstUnionType* AsUnionForTesting() { return AsUnion(); } 906 907 private: 908 // Friends. 909 template <class> 910 friend class Iterator; 911 friend AstBitsetType; 912 friend AstUnionType; 913 914 // Internal inspection. 915 bool IsKind(AstTypeBase::Kind kind) { 916 return AstTypeBase::IsKind(this, kind); 917 } 918 919 bool IsNone() { return this == None(); } 920 bool IsAny() { return this == Any(); } 921 bool IsBitset() { return AstBitsetType::IsBitset(this); } 922 bool IsUnion() { return IsKind(AstTypeBase::kUnion); } 923 924 bitset AsBitset() { 925 DCHECK(this->IsBitset()); 926 return reinterpret_cast<AstBitsetType*>(this)->Bitset(); 927 } 928 AstUnionType* AsUnion() { return AstUnionType::cast(this); } 929 930 bitset Representation(); 931 932 // Auxiliary functions. 933 bool SemanticMaybe(AstType* that); 934 935 bitset BitsetGlb() { return AstBitsetType::Glb(this); } 936 bitset BitsetLub() { return AstBitsetType::Lub(this); } 937 938 bool SlowIs(AstType* that); 939 bool SemanticIs(AstType* that); 940 941 static bool Overlap(AstRangeType* lhs, AstRangeType* rhs); 942 static bool Contains(AstRangeType* lhs, AstRangeType* rhs); 943 static bool Contains(AstRangeType* range, AstConstantType* constant); 944 static bool Contains(AstRangeType* range, i::Object* val); 945 946 static int UpdateRange(AstType* type, AstUnionType* result, int size, 947 Zone* zone); 948 949 static AstRangeType::Limits IntersectRangeAndBitset(AstType* range, 950 AstType* bits, 951 Zone* zone); 952 static AstRangeType::Limits ToLimits(bitset bits, Zone* zone); 953 954 bool SimplyEquals(AstType* that); 955 956 static int AddToUnion(AstType* type, AstUnionType* result, int size, 957 Zone* zone); 958 static int IntersectAux(AstType* type, AstType* other, AstUnionType* result, 959 int size, AstRangeType::Limits* limits, Zone* zone); 960 static AstType* NormalizeUnion(AstType* unioned, int size, Zone* zone); 961 static AstType* NormalizeRangeAndBitset(AstType* range, bitset* bits, 962 Zone* zone); 963 }; 964 965 // ----------------------------------------------------------------------------- 966 // Type bounds. A simple struct to represent a pair of lower/upper types. 967 968 struct AstBounds { 969 AstType* lower; 970 AstType* upper; 971 972 AstBounds() 973 : // Make sure accessing uninitialized bounds crashes big-time. 974 lower(nullptr), 975 upper(nullptr) {} 976 explicit AstBounds(AstType* t) : lower(t), upper(t) {} 977 AstBounds(AstType* l, AstType* u) : lower(l), upper(u) { 978 DCHECK(lower->Is(upper)); 979 } 980 981 // Unrestricted bounds. 982 static AstBounds Unbounded() { 983 return AstBounds(AstType::None(), AstType::Any()); 984 } 985 986 // Meet: both b1 and b2 are known to hold. 987 static AstBounds Both(AstBounds b1, AstBounds b2, Zone* zone) { 988 AstType* lower = AstType::Union(b1.lower, b2.lower, zone); 989 AstType* upper = AstType::Intersect(b1.upper, b2.upper, zone); 990 // Lower bounds are considered approximate, correct as necessary. 991 if (!lower->Is(upper)) lower = upper; 992 return AstBounds(lower, upper); 993 } 994 995 // Join: either b1 or b2 is known to hold. 996 static AstBounds Either(AstBounds b1, AstBounds b2, Zone* zone) { 997 AstType* lower = AstType::Intersect(b1.lower, b2.lower, zone); 998 AstType* upper = AstType::Union(b1.upper, b2.upper, zone); 999 return AstBounds(lower, upper); 1000 } 1001 1002 static AstBounds NarrowLower(AstBounds b, AstType* t, Zone* zone) { 1003 AstType* lower = AstType::Union(b.lower, t, zone); 1004 // Lower bounds are considered approximate, correct as necessary. 1005 if (!lower->Is(b.upper)) lower = b.upper; 1006 return AstBounds(lower, b.upper); 1007 } 1008 static AstBounds NarrowUpper(AstBounds b, AstType* t, Zone* zone) { 1009 AstType* lower = b.lower; 1010 AstType* upper = AstType::Intersect(b.upper, t, zone); 1011 // Lower bounds are considered approximate, correct as necessary. 1012 if (!lower->Is(upper)) lower = upper; 1013 return AstBounds(lower, upper); 1014 } 1015 1016 bool Narrows(AstBounds that) { 1017 return that.lower->Is(this->lower) && this->upper->Is(that.upper); 1018 } 1019 }; 1020 1021 } // namespace internal 1022 } // namespace v8 1023 1024 #endif // V8_AST_AST_TYPES_H_ 1025
