| 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 #ifndef V8_TYPES_H_ | |
| 6 #define V8_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 // RegExp < Object | |
| 43 // OtherUndetectable < Object | |
| 44 // DetectableReceiver = Receiver - OtherUndetectable | |
| 45 // | |
| 46 // Constant(x) < T iff instance_type(map(x)) < T | |
| 47 // | |
| 48 // | |
| 49 // REPRESENTATIONAL DIMENSION | |
| 50 // | |
| 51 // For the representation axis, the following holds: | |
| 52 // | |
| 53 // None <= R | |
| 54 // R <= Any | |
| 55 // | |
| 56 // UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/ | |
| 57 // UntaggedInt16 \/ UntaggedInt32 | |
| 58 // UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64 | |
| 59 // UntaggedNumber = UntaggedInt \/ UntaggedFloat | |
| 60 // Untagged = UntaggedNumber \/ UntaggedPtr | |
| 61 // Tagged = TaggedInt \/ TaggedPtr | |
| 62 // | |
| 63 // Subtyping relates the two dimensions, for example: | |
| 64 // | |
| 65 // Number <= Tagged \/ UntaggedNumber | |
| 66 // Object <= TaggedPtr \/ UntaggedPtr | |
| 67 // | |
| 68 // That holds because the semantic type constructors defined by the API create | |
| 69 // types that allow for all possible representations, and dually, the ones for | |
| 70 // representation types initially include all semantic ranges. Representations | |
| 71 // can then e.g. be narrowed for a given semantic type using intersection: | |
| 72 // | |
| 73 // SignedSmall /\ TaggedInt (a 'smi') | |
| 74 // Number /\ TaggedPtr (a heap number) | |
| 75 // | |
| 76 // | |
| 77 // RANGE TYPES | |
| 78 // | |
| 79 // A range type represents a continuous integer interval by its minimum and | |
| 80 // maximum value. Either value may be an infinity, in which case that infinity | |
| 81 // itself is also included in the range. A range never contains NaN or -0. | |
| 82 // | |
| 83 // If a value v happens to be an integer n, then Constant(v) is considered a | |
| 84 // subtype of Range(n, n) (and therefore also a subtype of any larger range). | |
| 85 // In order to avoid large unions, however, it is usually a good idea to use | |
| 86 // Range rather than Constant. | |
| 87 // | |
| 88 // | |
| 89 // PREDICATES | |
| 90 // | |
| 91 // There are two main functions for testing types: | |
| 92 // | |
| 93 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) | |
| 94 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) | |
| 95 // | |
| 96 // Typically, the former is to be used to select representations (e.g., via | |
| 97 // T->Is(SignedSmall())), and the latter to check whether a specific case needs | |
| 98 // handling (e.g., via T->Maybe(Number())). | |
| 99 // | |
| 100 // There is no functionality to discover whether a type is a leaf in the | |
| 101 // lattice. That is intentional. It should always be possible to refine the | |
| 102 // lattice (e.g., splitting up number types further) without invalidating any | |
| 103 // existing assumptions or tests. | |
| 104 // Consequently, do not normally use Equals for type tests, always use Is! | |
| 105 // | |
| 106 // The NowIs operator implements state-sensitive subtying, as described above. | |
| 107 // Any compilation decision based on such temporary properties requires runtime | |
| 108 // guarding! | |
| 109 // | |
| 110 // | |
| 111 // PROPERTIES | |
| 112 // | |
| 113 // Various formal properties hold for constructors, operators, and predicates | |
| 114 // over types. For example, constructors are injective and subtyping is a | |
| 115 // complete partial order. | |
| 116 // | |
| 117 // See test/cctest/test-types.cc for a comprehensive executable specification, | |
| 118 // especially with respect to the properties of the more exotic 'temporal' | |
| 119 // constructors and predicates (those prefixed 'Now'). | |
| 120 // | |
| 121 // | |
| 122 // IMPLEMENTATION | |
| 123 // | |
| 124 // Internally, all 'primitive' types, and their unions, are represented as | |
| 125 // bitsets. Bit 0 is reserved for tagging. Only structured types require | |
| 126 // allocation. | |
| 127 // Note that the bitset representation is closed under both Union and Intersect. | |
| 128 | |
| 129 // ----------------------------------------------------------------------------- | |
| 130 // Values for bitset types | |
| 131 | |
| 132 // clang-format off | |
| 133 | |
| 134 #define MASK_BITSET_TYPE_LIST(V) \ | |
| 135 V(Representation, 0xffc00000u) \ | |
| 136 V(Semantic, 0x003ffffeu) | |
| 137 | |
| 138 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) | |
| 139 #define SEMANTIC(k) ((k) & BitsetType::kSemantic) | |
| 140 | |
| 141 #define REPRESENTATION_BITSET_TYPE_LIST(V) \ | |
| 142 V(None, 0) \ | |
| 143 V(UntaggedBit, 1u << 22 | kSemantic) \ | |
| 144 V(UntaggedIntegral8, 1u << 23 | kSemantic) \ | |
| 145 V(UntaggedIntegral16, 1u << 24 | kSemantic) \ | |
| 146 V(UntaggedIntegral32, 1u << 25 | kSemantic) \ | |
| 147 V(UntaggedFloat32, 1u << 26 | kSemantic) \ | |
| 148 V(UntaggedFloat64, 1u << 27 | kSemantic) \ | |
| 149 V(UntaggedSimd128, 1u << 28 | kSemantic) \ | |
| 150 V(UntaggedPointer, 1u << 29 | kSemantic) \ | |
| 151 V(TaggedSigned, 1u << 30 | kSemantic) \ | |
| 152 V(TaggedPointer, 1u << 31 | kSemantic) \ | |
| 153 \ | |
| 154 V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \ | |
| 155 kUntaggedIntegral16 | kUntaggedIntegral32) \ | |
| 156 V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ | |
| 157 V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \ | |
| 158 V(Untagged, kUntaggedNumber | kUntaggedPointer) \ | |
| 159 V(Tagged, kTaggedSigned | kTaggedPointer) | |
| 160 | |
| 161 #define INTERNAL_BITSET_TYPE_LIST(V) \ | |
| 162 V(OtherUnsigned31, 1u << 1 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 163 V(OtherUnsigned32, 1u << 2 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 164 V(OtherSigned32, 1u << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 165 V(OtherNumber, 1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber)) | |
| 166 | |
| 167 #define SEMANTIC_BITSET_TYPE_LIST(V) \ | |
| 168 V(Negative31, 1u << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 169 V(Null, 1u << 6 | REPRESENTATION(kTaggedPointer)) \ | |
| 170 V(Undefined, 1u << 7 | REPRESENTATION(kTaggedPointer)) \ | |
| 171 V(Boolean, 1u << 8 | REPRESENTATION(kTaggedPointer)) \ | |
| 172 V(Unsigned30, 1u << 9 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 173 V(MinusZero, 1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 174 V(NaN, 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \ | |
| 175 V(Symbol, 1u << 12 | REPRESENTATION(kTaggedPointer)) \ | |
| 176 V(InternalizedString, 1u << 13 | REPRESENTATION(kTaggedPointer)) \ | |
| 177 V(OtherString, 1u << 14 | REPRESENTATION(kTaggedPointer)) \ | |
| 178 V(Simd, 1u << 15 | REPRESENTATION(kTaggedPointer)) \ | |
| 179 V(OtherObject, 1u << 17 | REPRESENTATION(kTaggedPointer)) \ | |
| 180 V(OtherUndetectable, 1u << 16 | REPRESENTATION(kTaggedPointer)) \ | |
| 181 V(Proxy, 1u << 18 | REPRESENTATION(kTaggedPointer)) \ | |
| 182 V(Function, 1u << 19 | REPRESENTATION(kTaggedPointer)) \ | |
| 183 V(Hole, 1u << 20 | REPRESENTATION(kTaggedPointer)) \ | |
| 184 V(OtherInternal, 1u << 21 | REPRESENTATION(kTagged | kUntagged)) \ | |
| 185 \ | |
| 186 V(Signed31, kUnsigned30 | kNegative31) \ | |
| 187 V(Signed32, kSigned31 | kOtherUnsigned31 | kOtherSigned32) \ | |
| 188 V(Signed32OrMinusZero, kSigned32 | kMinusZero) \ | |
| 189 V(Signed32OrMinusZeroOrNaN, kSigned32 | kMinusZero | kNaN) \ | |
| 190 V(Negative32, kNegative31 | kOtherSigned32) \ | |
| 191 V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \ | |
| 192 V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \ | |
| 193 kOtherUnsigned32) \ | |
| 194 V(Unsigned32OrMinusZero, kUnsigned32 | kMinusZero) \ | |
| 195 V(Unsigned32OrMinusZeroOrNaN, kUnsigned32 | kMinusZero | kNaN) \ | |
| 196 V(Integral32, kSigned32 | kUnsigned32) \ | |
| 197 V(PlainNumber, kIntegral32 | kOtherNumber) \ | |
| 198 V(OrderedNumber, kPlainNumber | kMinusZero) \ | |
| 199 V(MinusZeroOrNaN, kMinusZero | kNaN) \ | |
| 200 V(Number, kOrderedNumber | kNaN) \ | |
| 201 V(String, kInternalizedString | kOtherString) \ | |
| 202 V(UniqueName, kSymbol | kInternalizedString) \ | |
| 203 V(Name, kSymbol | kString) \ | |
| 204 V(BooleanOrNumber, kBoolean | kNumber) \ | |
| 205 V(BooleanOrNullOrNumber, kBooleanOrNumber | kNull) \ | |
| 206 V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \ | |
| 207 V(NullOrNumber, kNull | kNumber) \ | |
| 208 V(NullOrUndefined, kNull | kUndefined) \ | |
| 209 V(Undetectable, kNullOrUndefined | kOtherUndetectable) \ | |
| 210 V(NumberOrOddball, kNumber | kNullOrUndefined | kBoolean | kHole) \ | |
| 211 V(NumberOrSimdOrString, kNumber | kSimd | kString) \ | |
| 212 V(NumberOrString, kNumber | kString) \ | |
| 213 V(NumberOrUndefined, kNumber | kUndefined) \ | |
| 214 V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \ | |
| 215 V(Primitive, kSymbol | kSimd | kPlainPrimitive) \ | |
| 216 V(DetectableReceiver, kFunction | kOtherObject | kProxy) \ | |
| 217 V(Object, kFunction | kOtherObject | kOtherUndetectable) \ | |
| 218 V(Receiver, kObject | kProxy) \ | |
| 219 V(StringOrReceiver, kString | kReceiver) \ | |
| 220 V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \ | |
| 221 kReceiver) \ | |
| 222 V(Internal, kHole | kOtherInternal) \ | |
| 223 V(NonInternal, kPrimitive | kReceiver) \ | |
| 224 V(NonNumber, kUnique | kString | kInternal) \ | |
| 225 V(Any, 0xfffffffeu) | |
| 226 | |
| 227 // clang-format on | |
| 228 | |
| 229 /* | |
| 230 * The following diagrams show how integers (in the mathematical sense) are | |
| 231 * divided among the different atomic numerical types. | |
| 232 * | |
| 233 * ON OS32 N31 U30 OU31 OU32 ON | |
| 234 * ______[_______[_______[_______[_______[_______[_______ | |
| 235 * -2^31 -2^30 0 2^30 2^31 2^32 | |
| 236 * | |
| 237 * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. | |
| 238 * | |
| 239 * Some of the atomic numerical bitsets are internal only (see | |
| 240 * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in | |
| 241 * union with certain other bitsets. For instance, OtherNumber should only | |
| 242 * occur as part of PlainNumber. | |
| 243 */ | |
| 244 | |
| 245 #define PROPER_BITSET_TYPE_LIST(V) \ | |
| 246 REPRESENTATION_BITSET_TYPE_LIST(V) \ | |
| 247 SEMANTIC_BITSET_TYPE_LIST(V) | |
| 248 | |
| 249 #define BITSET_TYPE_LIST(V) \ | |
| 250 MASK_BITSET_TYPE_LIST(V) \ | |
| 251 REPRESENTATION_BITSET_TYPE_LIST(V) \ | |
| 252 INTERNAL_BITSET_TYPE_LIST(V) \ | |
| 253 SEMANTIC_BITSET_TYPE_LIST(V) | |
| 254 | |
| 255 class Type; | |
| 256 | |
| 257 // ----------------------------------------------------------------------------- | |
| 258 // Bitset types (internal). | |
| 259 | |
| 260 class BitsetType { | |
| 261 public: | |
| 262 typedef uint32_t bitset; // Internal | |
| 263 | |
| 264 enum : uint32_t { | |
| 265 #define DECLARE_TYPE(type, value) k##type = (value), | |
| 266 BITSET_TYPE_LIST(DECLARE_TYPE) | |
| 267 #undef DECLARE_TYPE | |
| 268 kUnusedEOL = 0 | |
| 269 }; | |
| 270 | |
| 271 static bitset SignedSmall(); | |
| 272 static bitset UnsignedSmall(); | |
| 273 | |
| 274 bitset Bitset() { | |
| 275 return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u); | |
| 276 } | |
| 277 | |
| 278 static bool IsInhabited(bitset bits) { | |
| 279 return SEMANTIC(bits) != kNone && REPRESENTATION(bits) != kNone; | |
| 280 } | |
| 281 | |
| 282 static bool SemanticIsInhabited(bitset bits) { | |
| 283 return SEMANTIC(bits) != kNone; | |
| 284 } | |
| 285 | |
| 286 static bool Is(bitset bits1, bitset bits2) { | |
| 287 return (bits1 | bits2) == bits2; | |
| 288 } | |
| 289 | |
| 290 static double Min(bitset); | |
| 291 static double Max(bitset); | |
| 292 | |
| 293 static bitset Glb(Type* type); // greatest lower bound that's a bitset | |
| 294 static bitset Glb(double min, double max); | |
| 295 static bitset Lub(Type* type); // least upper bound that's a bitset | |
| 296 static bitset Lub(i::Map* map); | |
| 297 static bitset Lub(i::Object* value); | |
| 298 static bitset Lub(double value); | |
| 299 static bitset Lub(double min, double max); | |
| 300 static bitset ExpandInternals(bitset bits); | |
| 301 | |
| 302 static const char* Name(bitset); | |
| 303 static void Print(std::ostream& os, bitset); // NOLINT | |
| 304 #ifdef DEBUG | |
| 305 static void Print(bitset); | |
| 306 #endif | |
| 307 | |
| 308 static bitset NumberBits(bitset bits); | |
| 309 | |
| 310 static bool IsBitset(Type* type) { | |
| 311 return reinterpret_cast<uintptr_t>(type) & 1; | |
| 312 } | |
| 313 | |
| 314 static Type* NewForTesting(bitset bits) { return New(bits); } | |
| 315 | |
| 316 private: | |
| 317 friend class Type; | |
| 318 | |
| 319 static Type* New(bitset bits) { | |
| 320 return reinterpret_cast<Type*>(static_cast<uintptr_t>(bits | 1u)); | |
| 321 } | |
| 322 | |
| 323 struct Boundary { | |
| 324 bitset internal; | |
| 325 bitset external; | |
| 326 double min; | |
| 327 }; | |
| 328 static const Boundary BoundariesArray[]; | |
| 329 static inline const Boundary* Boundaries(); | |
| 330 static inline size_t BoundariesSize(); | |
| 331 }; | |
| 332 | |
| 333 // ----------------------------------------------------------------------------- | |
| 334 // Superclass for non-bitset types (internal). | |
| 335 class TypeBase { | |
| 336 protected: | |
| 337 friend class Type; | |
| 338 | |
| 339 enum Kind { | |
| 340 kConstant, | |
| 341 kTuple, | |
| 342 kUnion, | |
| 343 kRange | |
| 344 }; | |
| 345 | |
| 346 Kind kind() const { return kind_; } | |
| 347 explicit TypeBase(Kind kind) : kind_(kind) {} | |
| 348 | |
| 349 static bool IsKind(Type* type, Kind kind) { | |
| 350 if (BitsetType::IsBitset(type)) return false; | |
| 351 TypeBase* base = reinterpret_cast<TypeBase*>(type); | |
| 352 return base->kind() == kind; | |
| 353 } | |
| 354 | |
| 355 // The hacky conversion to/from Type*. | |
| 356 static Type* AsType(TypeBase* type) { return reinterpret_cast<Type*>(type); } | |
| 357 static TypeBase* FromType(Type* type) { | |
| 358 return reinterpret_cast<TypeBase*>(type); | |
| 359 } | |
| 360 | |
| 361 private: | |
| 362 Kind kind_; | |
| 363 }; | |
| 364 | |
| 365 // ----------------------------------------------------------------------------- | |
| 366 // Constant types. | |
| 367 | |
| 368 class ConstantType : public TypeBase { | |
| 369 public: | |
| 370 i::Handle<i::Object> Value() { return object_; } | |
| 371 | |
| 372 private: | |
| 373 friend class Type; | |
| 374 friend class BitsetType; | |
| 375 | |
| 376 static Type* New(i::Handle<i::Object> value, Zone* zone) { | |
| 377 BitsetType::bitset bitset = BitsetType::Lub(*value); | |
| 378 return AsType(new (zone->New(sizeof(ConstantType))) | |
| 379 ConstantType(bitset, value)); | |
| 380 } | |
| 381 | |
| 382 static ConstantType* cast(Type* type) { | |
| 383 DCHECK(IsKind(type, kConstant)); | |
| 384 return static_cast<ConstantType*>(FromType(type)); | |
| 385 } | |
| 386 | |
| 387 ConstantType(BitsetType::bitset bitset, i::Handle<i::Object> object) | |
| 388 : TypeBase(kConstant), bitset_(bitset), object_(object) {} | |
| 389 | |
| 390 BitsetType::bitset Lub() { return bitset_; } | |
| 391 | |
| 392 BitsetType::bitset bitset_; | |
| 393 Handle<i::Object> object_; | |
| 394 }; | |
| 395 // TODO(neis): Also cache value if numerical. | |
| 396 // TODO(neis): Allow restricting the representation. | |
| 397 | |
| 398 // ----------------------------------------------------------------------------- | |
| 399 // Range types. | |
| 400 | |
| 401 class RangeType : public TypeBase { | |
| 402 public: | |
| 403 struct Limits { | |
| 404 double min; | |
| 405 double max; | |
| 406 Limits(double min, double max) : min(min), max(max) {} | |
| 407 explicit Limits(RangeType* range) : min(range->Min()), max(range->Max()) {} | |
| 408 bool IsEmpty(); | |
| 409 static Limits Empty() { return Limits(1, 0); } | |
| 410 static Limits Intersect(Limits lhs, Limits rhs); | |
| 411 static Limits Union(Limits lhs, Limits rhs); | |
| 412 }; | |
| 413 | |
| 414 double Min() { return limits_.min; } | |
| 415 double Max() { return limits_.max; } | |
| 416 | |
| 417 private: | |
| 418 friend class Type; | |
| 419 friend class BitsetType; | |
| 420 friend class UnionType; | |
| 421 | |
| 422 static Type* New(double min, double max, BitsetType::bitset representation, | |
| 423 Zone* zone) { | |
| 424 return New(Limits(min, max), representation, zone); | |
| 425 } | |
| 426 | |
| 427 static bool IsInteger(double x) { | |
| 428 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. | |
| 429 } | |
| 430 | |
| 431 static Type* New(Limits lim, BitsetType::bitset representation, Zone* zone) { | |
| 432 DCHECK(IsInteger(lim.min) && IsInteger(lim.max)); | |
| 433 DCHECK(lim.min <= lim.max); | |
| 434 DCHECK(REPRESENTATION(representation) == representation); | |
| 435 BitsetType::bitset bits = | |
| 436 SEMANTIC(BitsetType::Lub(lim.min, lim.max)) | representation; | |
| 437 | |
| 438 return AsType(new (zone->New(sizeof(RangeType))) RangeType(bits, lim)); | |
| 439 } | |
| 440 | |
| 441 static RangeType* cast(Type* type) { | |
| 442 DCHECK(IsKind(type, kRange)); | |
| 443 return static_cast<RangeType*>(FromType(type)); | |
| 444 } | |
| 445 | |
| 446 RangeType(BitsetType::bitset bitset, Limits limits) | |
| 447 : TypeBase(kRange), bitset_(bitset), limits_(limits) {} | |
| 448 | |
| 449 BitsetType::bitset Lub() { return bitset_; } | |
| 450 | |
| 451 BitsetType::bitset bitset_; | |
| 452 Limits limits_; | |
| 453 }; | |
| 454 | |
| 455 // ----------------------------------------------------------------------------- | |
| 456 // Superclass for types with variable number of type fields. | |
| 457 class StructuralType : public TypeBase { | |
| 458 public: | |
| 459 int LengthForTesting() { return Length(); } | |
| 460 | |
| 461 protected: | |
| 462 friend class Type; | |
| 463 | |
| 464 int Length() { return length_; } | |
| 465 | |
| 466 Type* Get(int i) { | |
| 467 DCHECK(0 <= i && i < this->Length()); | |
| 468 return elements_[i]; | |
| 469 } | |
| 470 | |
| 471 void Set(int i, Type* type) { | |
| 472 DCHECK(0 <= i && i < this->Length()); | |
| 473 elements_[i] = type; | |
| 474 } | |
| 475 | |
| 476 void Shrink(int length) { | |
| 477 DCHECK(2 <= length && length <= this->Length()); | |
| 478 length_ = length; | |
| 479 } | |
| 480 | |
| 481 StructuralType(Kind kind, int length, i::Zone* zone) | |
| 482 : TypeBase(kind), length_(length) { | |
| 483 elements_ = reinterpret_cast<Type**>(zone->New(sizeof(Type*) * length)); | |
| 484 } | |
| 485 | |
| 486 private: | |
| 487 int length_; | |
| 488 Type** elements_; | |
| 489 }; | |
| 490 | |
| 491 // ----------------------------------------------------------------------------- | |
| 492 // Tuple types. | |
| 493 | |
| 494 class TupleType : public StructuralType { | |
| 495 public: | |
| 496 int Arity() { return this->Length(); } | |
| 497 Type* Element(int i) { return this->Get(i); } | |
| 498 | |
| 499 void InitElement(int i, Type* type) { this->Set(i, type); } | |
| 500 | |
| 501 private: | |
| 502 friend class Type; | |
| 503 | |
| 504 TupleType(int length, Zone* zone) : StructuralType(kTuple, length, zone) {} | |
| 505 | |
| 506 static Type* New(int length, Zone* zone) { | |
| 507 return AsType(new (zone->New(sizeof(TupleType))) TupleType(length, zone)); | |
| 508 } | |
| 509 | |
| 510 static TupleType* cast(Type* type) { | |
| 511 DCHECK(IsKind(type, kTuple)); | |
| 512 return static_cast<TupleType*>(FromType(type)); | |
| 513 } | |
| 514 }; | |
| 515 | |
| 516 // ----------------------------------------------------------------------------- | |
| 517 // Union types (internal). | |
| 518 // A union is a structured type with the following invariants: | |
| 519 // - its length is at least 2 | |
| 520 // - at most one field is a bitset, and it must go into index 0 | |
| 521 // - no field is a union | |
| 522 // - no field is a subtype of any other field | |
| 523 class UnionType : public StructuralType { | |
| 524 private: | |
| 525 friend Type; | |
| 526 friend BitsetType; | |
| 527 | |
| 528 UnionType(int length, Zone* zone) : StructuralType(kUnion, length, zone) {} | |
| 529 | |
| 530 static Type* New(int length, Zone* zone) { | |
| 531 return AsType(new (zone->New(sizeof(UnionType))) UnionType(length, zone)); | |
| 532 } | |
| 533 | |
| 534 static UnionType* cast(Type* type) { | |
| 535 DCHECK(IsKind(type, kUnion)); | |
| 536 return static_cast<UnionType*>(FromType(type)); | |
| 537 } | |
| 538 | |
| 539 bool Wellformed(); | |
| 540 }; | |
| 541 | |
| 542 class Type { | |
| 543 public: | |
| 544 typedef BitsetType::bitset bitset; // Internal | |
| 545 | |
| 546 // Constructors. | |
| 547 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ | |
| 548 static Type* type() { return BitsetType::New(BitsetType::k##type); } | |
| 549 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) | |
| 550 #undef DEFINE_TYPE_CONSTRUCTOR | |
| 551 | |
| 552 static Type* SignedSmall() { | |
| 553 return BitsetType::New(BitsetType::SignedSmall()); | |
| 554 } | |
| 555 static Type* UnsignedSmall() { | |
| 556 return BitsetType::New(BitsetType::UnsignedSmall()); | |
| 557 } | |
| 558 | |
| 559 static Type* Constant(i::Handle<i::Object> value, Zone* zone) { | |
| 560 return ConstantType::New(value, zone); | |
| 561 } | |
| 562 static Type* Range(double min, double max, Zone* zone) { | |
| 563 return RangeType::New(min, max, REPRESENTATION(BitsetType::kTagged | | |
| 564 BitsetType::kUntaggedNumber), | |
| 565 zone); | |
| 566 } | |
| 567 static Type* Tuple(Type* first, Type* second, Type* third, Zone* zone) { | |
| 568 Type* tuple = TupleType::New(3, zone); | |
| 569 tuple->AsTuple()->InitElement(0, first); | |
| 570 tuple->AsTuple()->InitElement(1, second); | |
| 571 tuple->AsTuple()->InitElement(2, third); | |
| 572 return tuple; | |
| 573 } | |
| 574 | |
| 575 static Type* Union(Type* type1, Type* type2, Zone* zone); | |
| 576 static Type* Intersect(Type* type1, Type* type2, Zone* zone); | |
| 577 | |
| 578 static Type* Of(double value, Zone* zone) { | |
| 579 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); | |
| 580 } | |
| 581 static Type* Of(i::Object* value, Zone* zone) { | |
| 582 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value))); | |
| 583 } | |
| 584 static Type* Of(i::Handle<i::Object> value, Zone* zone) { | |
| 585 return Of(*value, zone); | |
| 586 } | |
| 587 | |
| 588 static Type* For(i::Map* map) { | |
| 589 return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(map))); | |
| 590 } | |
| 591 static Type* For(i::Handle<i::Map> map) { return For(*map); } | |
| 592 | |
| 593 // Extraction of components. | |
| 594 static Type* Representation(Type* t, Zone* zone); | |
| 595 static Type* Semantic(Type* t, Zone* zone); | |
| 596 | |
| 597 // Predicates. | |
| 598 bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } | |
| 599 | |
| 600 bool Is(Type* that) { return this == that || this->SlowIs(that); } | |
| 601 bool Maybe(Type* that); | |
| 602 bool Equals(Type* that) { return this->Is(that) && that->Is(this); } | |
| 603 | |
| 604 // Equivalent to Constant(val)->Is(this), but avoiding allocation. | |
| 605 bool Contains(i::Object* val); | |
| 606 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } | |
| 607 | |
| 608 // Inspection. | |
| 609 bool IsRange() { return IsKind(TypeBase::kRange); } | |
| 610 bool IsConstant() { return IsKind(TypeBase::kConstant); } | |
| 611 bool IsTuple() { return IsKind(TypeBase::kTuple); } | |
| 612 | |
| 613 ConstantType* AsConstant() { return ConstantType::cast(this); } | |
| 614 RangeType* AsRange() { return RangeType::cast(this); } | |
| 615 TupleType* AsTuple() { return TupleType::cast(this); } | |
| 616 | |
| 617 // Minimum and maximum of a numeric type. | |
| 618 // These functions do not distinguish between -0 and +0. If the type equals | |
| 619 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these | |
| 620 // functions on subtypes of Number. | |
| 621 double Min(); | |
| 622 double Max(); | |
| 623 | |
| 624 // Extracts a range from the type: if the type is a range or a union | |
| 625 // containing a range, that range is returned; otherwise, NULL is returned. | |
| 626 Type* GetRange(); | |
| 627 | |
| 628 static bool IsInteger(i::Object* x); | |
| 629 static bool IsInteger(double x) { | |
| 630 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. | |
| 631 } | |
| 632 | |
| 633 int NumConstants(); | |
| 634 | |
| 635 template <class T> | |
| 636 class Iterator { | |
| 637 public: | |
| 638 bool Done() const { return index_ < 0; } | |
| 639 i::Handle<T> Current(); | |
| 640 void Advance(); | |
| 641 | |
| 642 private: | |
| 643 friend class Type; | |
| 644 | |
| 645 Iterator() : index_(-1) {} | |
| 646 explicit Iterator(Type* type) : type_(type), index_(-1) { Advance(); } | |
| 647 | |
| 648 inline bool matches(Type* type); | |
| 649 inline Type* get_type(); | |
| 650 | |
| 651 Type* type_; | |
| 652 int index_; | |
| 653 }; | |
| 654 | |
| 655 Iterator<i::Object> Constants() { | |
| 656 if (this->IsBitset()) return Iterator<i::Object>(); | |
| 657 return Iterator<i::Object>(this); | |
| 658 } | |
| 659 | |
| 660 // Printing. | |
| 661 | |
| 662 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; | |
| 663 | |
| 664 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT | |
| 665 | |
| 666 #ifdef DEBUG | |
| 667 void Print(); | |
| 668 #endif | |
| 669 | |
| 670 // Helpers for testing. | |
| 671 bool IsBitsetForTesting() { return IsBitset(); } | |
| 672 bool IsUnionForTesting() { return IsUnion(); } | |
| 673 bitset AsBitsetForTesting() { return AsBitset(); } | |
| 674 UnionType* AsUnionForTesting() { return AsUnion(); } | |
| 675 | |
| 676 private: | |
| 677 // Friends. | |
| 678 template <class> | |
| 679 friend class Iterator; | |
| 680 friend BitsetType; | |
| 681 friend UnionType; | |
| 682 | |
| 683 // Internal inspection. | |
| 684 bool IsKind(TypeBase::Kind kind) { return TypeBase::IsKind(this, kind); } | |
| 685 | |
| 686 bool IsNone() { return this == None(); } | |
| 687 bool IsAny() { return this == Any(); } | |
| 688 bool IsBitset() { return BitsetType::IsBitset(this); } | |
| 689 bool IsUnion() { return IsKind(TypeBase::kUnion); } | |
| 690 | |
| 691 bitset AsBitset() { | |
| 692 DCHECK(this->IsBitset()); | |
| 693 return reinterpret_cast<BitsetType*>(this)->Bitset(); | |
| 694 } | |
| 695 UnionType* AsUnion() { return UnionType::cast(this); } | |
| 696 | |
| 697 bitset Representation(); | |
| 698 | |
| 699 // Auxiliary functions. | |
| 700 bool SemanticMaybe(Type* that); | |
| 701 | |
| 702 bitset BitsetGlb() { return BitsetType::Glb(this); } | |
| 703 bitset BitsetLub() { return BitsetType::Lub(this); } | |
| 704 | |
| 705 bool SlowIs(Type* that); | |
| 706 bool SemanticIs(Type* that); | |
| 707 | |
| 708 static bool Overlap(RangeType* lhs, RangeType* rhs); | |
| 709 static bool Contains(RangeType* lhs, RangeType* rhs); | |
| 710 static bool Contains(RangeType* range, ConstantType* constant); | |
| 711 static bool Contains(RangeType* range, i::Object* val); | |
| 712 | |
| 713 static int UpdateRange(Type* type, UnionType* result, int size, Zone* zone); | |
| 714 | |
| 715 static RangeType::Limits IntersectRangeAndBitset(Type* range, Type* bits, | |
| 716 Zone* zone); | |
| 717 static RangeType::Limits ToLimits(bitset bits, Zone* zone); | |
| 718 | |
| 719 bool SimplyEquals(Type* that); | |
| 720 | |
| 721 static int AddToUnion(Type* type, UnionType* result, int size, Zone* zone); | |
| 722 static int IntersectAux(Type* type, Type* other, UnionType* result, int size, | |
| 723 RangeType::Limits* limits, Zone* zone); | |
| 724 static Type* NormalizeUnion(Type* unioned, int size, Zone* zone); | |
| 725 static Type* NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone); | |
| 726 }; | |
| 727 | |
| 728 // ----------------------------------------------------------------------------- | |
| 729 // Type bounds. A simple struct to represent a pair of lower/upper types. | |
| 730 | |
| 731 struct Bounds { | |
| 732 Type* lower; | |
| 733 Type* upper; | |
| 734 | |
| 735 Bounds() | |
| 736 : // Make sure accessing uninitialized bounds crashes big-time. | |
| 737 lower(nullptr), | |
| 738 upper(nullptr) {} | |
| 739 explicit Bounds(Type* t) : lower(t), upper(t) {} | |
| 740 Bounds(Type* l, Type* u) : lower(l), upper(u) { DCHECK(lower->Is(upper)); } | |
| 741 | |
| 742 // Unrestricted bounds. | |
| 743 static Bounds Unbounded() { return Bounds(Type::None(), Type::Any()); } | |
| 744 | |
| 745 // Meet: both b1 and b2 are known to hold. | |
| 746 static Bounds Both(Bounds b1, Bounds b2, Zone* zone) { | |
| 747 Type* lower = Type::Union(b1.lower, b2.lower, zone); | |
| 748 Type* upper = Type::Intersect(b1.upper, b2.upper, zone); | |
| 749 // Lower bounds are considered approximate, correct as necessary. | |
| 750 if (!lower->Is(upper)) lower = upper; | |
| 751 return Bounds(lower, upper); | |
| 752 } | |
| 753 | |
| 754 // Join: either b1 or b2 is known to hold. | |
| 755 static Bounds Either(Bounds b1, Bounds b2, Zone* zone) { | |
| 756 Type* lower = Type::Intersect(b1.lower, b2.lower, zone); | |
| 757 Type* upper = Type::Union(b1.upper, b2.upper, zone); | |
| 758 return Bounds(lower, upper); | |
| 759 } | |
| 760 | |
| 761 static Bounds NarrowLower(Bounds b, Type* t, Zone* zone) { | |
| 762 Type* lower = Type::Union(b.lower, t, zone); | |
| 763 // Lower bounds are considered approximate, correct as necessary. | |
| 764 if (!lower->Is(b.upper)) lower = b.upper; | |
| 765 return Bounds(lower, b.upper); | |
| 766 } | |
| 767 static Bounds NarrowUpper(Bounds b, Type* t, Zone* zone) { | |
| 768 Type* lower = b.lower; | |
| 769 Type* upper = Type::Intersect(b.upper, t, zone); | |
| 770 // Lower bounds are considered approximate, correct as necessary. | |
| 771 if (!lower->Is(upper)) lower = upper; | |
| 772 return Bounds(lower, upper); | |
| 773 } | |
| 774 | |
| 775 bool Narrows(Bounds that) { | |
| 776 return that.lower->Is(this->lower) && this->upper->Is(that.upper); | |
| 777 } | |
| 778 }; | |
| 779 } // namespace internal | |
| 780 } // namespace v8 | |
| 781 | |
| 782 #endif // V8_TYPES_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2309823002:
[turbofan] put src/types.[h/cc] into src/compiler/types.[h/cc] (Closed)
