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 // Array < Object 43 // Function < Object 44 // RegExp < Object 45 // Undetectable < Object 46 // Detectable = Receiver \/ Number \/ Name - Undetectable 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 // There are two type representations, using different allocation: 148 // 149 // - class Type (zone-allocated, for compiler and concurrent compilation) 150 // - class HeapType (heap-allocated, for persistent types) 151 // 152 // Both provide the same API, and the Convert method can be used to interconvert 153 // them. For zone types, no query method touches the heap, only constructors do. 154 155 156 // ----------------------------------------------------------------------------- 157 // Values for bitset types 158 159 // clang-format off 160 161 #define MASK_BITSET_TYPE_LIST(V) \ 162 V(Representation, 0xff800000u) \ 163 V(Semantic, 0x007ffffeu) 164 165 #define REPRESENTATION(k) ((k) & BitsetType::kRepresentation) 166 #define SEMANTIC(k) ((k) & BitsetType::kSemantic) 167 168 #define REPRESENTATION_BITSET_TYPE_LIST(V) \ 169 V(None, 0) \ 170 V(UntaggedBit, 1u << 23 | kSemantic) \ 171 V(UntaggedIntegral8, 1u << 24 | kSemantic) \ 172 V(UntaggedIntegral16, 1u << 25 | kSemantic) \ 173 V(UntaggedIntegral32, 1u << 26 | kSemantic) \ 174 V(UntaggedFloat32, 1u << 27 | kSemantic) \ 175 V(UntaggedFloat64, 1u << 28 | kSemantic) \ 176 V(UntaggedPointer, 1u << 29 | kSemantic) \ 177 V(TaggedSigned, 1u << 30 | kSemantic) \ 178 V(TaggedPointer, 1u << 31 | kSemantic) \ 179 \ 180 V(UntaggedIntegral, kUntaggedBit | kUntaggedIntegral8 | \ 181 kUntaggedIntegral16 | kUntaggedIntegral32) \ 182 V(UntaggedFloat, kUntaggedFloat32 | kUntaggedFloat64) \ 183 V(UntaggedNumber, kUntaggedIntegral | kUntaggedFloat) \ 184 V(Untagged, kUntaggedNumber | kUntaggedPointer) \ 185 V(Tagged, kTaggedSigned | kTaggedPointer) 186 187 #define INTERNAL_BITSET_TYPE_LIST(V) \ 188 V(OtherUnsigned31, 1u << 1 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 189 V(OtherUnsigned32, 1u << 2 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 190 V(OtherSigned32, 1u << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 191 V(OtherNumber, 1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber)) 192 193 #define SEMANTIC_BITSET_TYPE_LIST(V) \ 194 V(Negative31, 1u << 5 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 195 V(Null, 1u << 6 | REPRESENTATION(kTaggedPointer)) \ 196 V(Undefined, 1u << 7 | REPRESENTATION(kTaggedPointer)) \ 197 V(Boolean, 1u << 8 | REPRESENTATION(kTaggedPointer)) \ 198 V(Unsigned30, 1u << 9 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 199 V(MinusZero, 1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 200 V(NaN, 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \ 201 V(Symbol, 1u << 12 | REPRESENTATION(kTaggedPointer)) \ 202 V(InternalizedString, 1u << 13 | REPRESENTATION(kTaggedPointer)) \ 203 V(OtherString, 1u << 14 | REPRESENTATION(kTaggedPointer)) \ 204 V(Simd, 1u << 15 | REPRESENTATION(kTaggedPointer)) \ 205 V(Undetectable, 1u << 16 | REPRESENTATION(kTaggedPointer)) \ 206 V(OtherObject, 1u << 17 | REPRESENTATION(kTaggedPointer)) \ 207 V(Proxy, 1u << 18 | REPRESENTATION(kTaggedPointer)) \ 208 V(Function, 1u << 19 | REPRESENTATION(kTaggedPointer)) \ 209 V(Internal, 1u << 20 | REPRESENTATION(kTagged | kUntagged)) \ 210 \ 211 V(Signed31, kUnsigned30 | kNegative31) \ 212 V(Signed32, kSigned31 | kOtherUnsigned31 | kOtherSigned32) \ 213 V(Negative32, kNegative31 | kOtherSigned32) \ 214 V(Unsigned31, kUnsigned30 | kOtherUnsigned31) \ 215 V(Unsigned32, kUnsigned30 | kOtherUnsigned31 | \ 216 kOtherUnsigned32) \ 217 V(Integral32, kSigned32 | kUnsigned32) \ 218 V(PlainNumber, kIntegral32 | kOtherNumber) \ 219 V(OrderedNumber, kPlainNumber | kMinusZero) \ 220 V(MinusZeroOrNaN, kMinusZero | kNaN) \ 221 V(Number, kOrderedNumber | kNaN) \ 222 V(String, kInternalizedString | kOtherString) \ 223 V(UniqueName, kSymbol | kInternalizedString) \ 224 V(Name, kSymbol | kString) \ 225 V(BooleanOrNumber, kBoolean | kNumber) \ 226 V(BooleanOrNullOrUndefined, kBoolean | kNull | kUndefined) \ 227 V(NullOrUndefined, kNull | kUndefined) \ 228 V(NumberOrString, kNumber | kString) \ 229 V(NumberOrUndefined, kNumber | kUndefined) \ 230 V(PlainPrimitive, kNumberOrString | kBoolean | kNullOrUndefined) \ 231 V(Primitive, kSymbol | kSimd | kPlainPrimitive) \ 232 V(DetectableReceiver, kFunction | kOtherObject | kProxy) \ 233 V(Detectable, kDetectableReceiver | kNumber | kName) \ 234 V(Object, kFunction | kOtherObject | kUndetectable) \ 235 V(Receiver, kObject | kProxy) \ 236 V(StringOrReceiver, kString | kReceiver) \ 237 V(Unique, kBoolean | kUniqueName | kNull | kUndefined | \ 238 kReceiver) \ 239 V(NonNumber, kUnique | kString | kInternal) \ 240 V(Any, 0xfffffffeu) 241 242 // clang-format on 243 244 /* 245 * The following diagrams show how integers (in the mathematical sense) are 246 * divided among the different atomic numerical types. 247 * 248 * ON OS32 N31 U30 OU31 OU32 ON 249 * ______[_______[_______[_______[_______[_______[_______ 250 * -2^31 -2^30 0 2^30 2^31 2^32 251 * 252 * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1. 253 * 254 * Some of the atomic numerical bitsets are internal only (see 255 * INTERNAL_BITSET_TYPE_LIST). To a types user, they should only occur in 256 * union with certain other bitsets. For instance, OtherNumber should only 257 * occur as part of PlainNumber. 258 */ 259 260 #define PROPER_BITSET_TYPE_LIST(V) \ 261 REPRESENTATION_BITSET_TYPE_LIST(V) \ 262 SEMANTIC_BITSET_TYPE_LIST(V) 263 264 #define BITSET_TYPE_LIST(V) \ 265 MASK_BITSET_TYPE_LIST(V) \ 266 REPRESENTATION_BITSET_TYPE_LIST(V) \ 267 INTERNAL_BITSET_TYPE_LIST(V) \ 268 SEMANTIC_BITSET_TYPE_LIST(V) 269 270 271 // ----------------------------------------------------------------------------- 272 // The abstract Type class, parameterized over the low-level representation. 273 274 // struct Config { 275 // typedef TypeImpl<Config> Type; 276 // typedef Base; 277 // typedef Struct; 278 // typedef Range; 279 // typedef Region; 280 // template<class> struct Handle { typedef type; } // No template typedefs... 281 // 282 // template<class T> static Handle<T>::type null_handle(); 283 // template<class T> static Handle<T>::type handle(T* t); // !is_bitset(t) 284 // template<class T> static Handle<T>::type cast(Handle<Type>::type); 285 // 286 // static bool is_bitset(Type*); 287 // static bool is_class(Type*); 288 // static bool is_struct(Type*, int tag); 289 // static bool is_range(Type*); 290 // 291 // static bitset as_bitset(Type*); 292 // static i::Handle<i::Map> as_class(Type*); 293 // static Handle<Struct>::type as_struct(Type*); 294 // static Handle<Range>::type as_range(Type*); 295 // 296 // static Type* from_bitset(bitset); 297 // static Handle<Type>::type from_bitset(bitset, Region*); 298 // static Handle<Type>::type from_class(i::Handle<Map>, Region*); 299 // static Handle<Type>::type from_struct(Handle<Struct>::type, int tag); 300 // static Handle<Type>::type from_range(Handle<Range>::type); 301 // 302 // static Handle<Struct>::type struct_create(int tag, int length, Region*); 303 // static void struct_shrink(Handle<Struct>::type, int length); 304 // static int struct_tag(Handle<Struct>::type); 305 // static int struct_length(Handle<Struct>::type); 306 // static Handle<Type>::type struct_get(Handle<Struct>::type, int); 307 // static void struct_set(Handle<Struct>::type, int, Handle<Type>::type); 308 // template<class V> 309 // static i::Handle<V> struct_get_value(Handle<Struct>::type, int); 310 // template<class V> 311 // static void struct_set_value(Handle<Struct>::type, int, i::Handle<V>); 312 // 313 // static Handle<Range>::type range_create(Region*); 314 // static int range_get_bitset(Handle<Range>::type); 315 // static void range_set_bitset(Handle<Range>::type, int); 316 // static double range_get_double(Handle<Range>::type, int); 317 // static void range_set_double(Handle<Range>::type, int, double, Region*); 318 // } 319 template<class Config> 320 class TypeImpl : public Config::Base { 321 public: 322 // Auxiliary types. 323 324 typedef uint32_t bitset; // Internal 325 class BitsetType; // Internal 326 class StructuralType; // Internal 327 class UnionType; // Internal 328 329 class ClassType; 330 class ConstantType; 331 class RangeType; 332 class ContextType; 333 class ArrayType; 334 class FunctionType; 335 336 typedef typename Config::template Handle<TypeImpl>::type TypeHandle; 337 typedef typename Config::template Handle<ClassType>::type ClassHandle; 338 typedef typename Config::template Handle<ConstantType>::type ConstantHandle; 339 typedef typename Config::template Handle<RangeType>::type RangeHandle; 340 typedef typename Config::template Handle<ContextType>::type ContextHandle; 341 typedef typename Config::template Handle<ArrayType>::type ArrayHandle; 342 typedef typename Config::template Handle<FunctionType>::type FunctionHandle; 343 typedef typename Config::template Handle<UnionType>::type UnionHandle; 344 typedef typename Config::Region Region; 345 346 // Constructors. 347 348 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ 349 static TypeImpl* type() { \ 350 return BitsetType::New(BitsetType::k##type); \ 351 } \ 352 static TypeHandle type(Region* region) { \ 353 return BitsetType::New(BitsetType::k##type, region); \ 354 } PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)355 PROPER_BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) 356 #undef DEFINE_TYPE_CONSTRUCTOR 357 358 static TypeImpl* SignedSmall() { 359 return BitsetType::New(BitsetType::SignedSmall()); 360 } SignedSmall(Region * region)361 static TypeHandle SignedSmall(Region* region) { 362 return BitsetType::New(BitsetType::SignedSmall(), region); 363 } UnsignedSmall()364 static TypeImpl* UnsignedSmall() { 365 return BitsetType::New(BitsetType::UnsignedSmall()); 366 } UnsignedSmall(Region * region)367 static TypeHandle UnsignedSmall(Region* region) { 368 return BitsetType::New(BitsetType::UnsignedSmall(), region); 369 } 370 Class(i::Handle<i::Map> map,Region * region)371 static TypeHandle Class(i::Handle<i::Map> map, Region* region) { 372 return ClassType::New(map, region); 373 } Constant(i::Handle<i::Object> value,Region * region)374 static TypeHandle Constant(i::Handle<i::Object> value, Region* region) { 375 return ConstantType::New(value, region); 376 } Range(double min,double max,Region * region)377 static TypeHandle Range(double min, double max, Region* region) { 378 return RangeType::New( 379 min, max, BitsetType::New(REPRESENTATION(BitsetType::kTagged | 380 BitsetType::kUntaggedNumber), 381 region), 382 region); 383 } Context(TypeHandle outer,Region * region)384 static TypeHandle Context(TypeHandle outer, Region* region) { 385 return ContextType::New(outer, region); 386 } Array(TypeHandle element,Region * region)387 static TypeHandle Array(TypeHandle element, Region* region) { 388 return ArrayType::New(element, region); 389 } Function(TypeHandle result,TypeHandle receiver,int arity,Region * region)390 static FunctionHandle Function( 391 TypeHandle result, TypeHandle receiver, int arity, Region* region) { 392 return FunctionType::New(result, receiver, arity, region); 393 } Function(TypeHandle result,Region * region)394 static TypeHandle Function(TypeHandle result, Region* region) { 395 return Function(result, Any(region), 0, region); 396 } Function(TypeHandle result,TypeHandle param0,Region * region)397 static TypeHandle Function( 398 TypeHandle result, TypeHandle param0, Region* region) { 399 FunctionHandle function = Function(result, Any(region), 1, region); 400 function->InitParameter(0, param0); 401 return function; 402 } Function(TypeHandle result,TypeHandle param0,TypeHandle param1,Region * region)403 static TypeHandle Function( 404 TypeHandle result, TypeHandle param0, TypeHandle param1, Region* region) { 405 FunctionHandle function = Function(result, Any(region), 2, region); 406 function->InitParameter(0, param0); 407 function->InitParameter(1, param1); 408 return function; 409 } Function(TypeHandle result,TypeHandle param0,TypeHandle param1,TypeHandle param2,Region * region)410 static TypeHandle Function( 411 TypeHandle result, TypeHandle param0, TypeHandle param1, 412 TypeHandle param2, Region* region) { 413 FunctionHandle function = Function(result, Any(region), 3, region); 414 function->InitParameter(0, param0); 415 function->InitParameter(1, param1); 416 function->InitParameter(2, param2); 417 return function; 418 } Function(TypeHandle result,int arity,TypeHandle * params,Region * region)419 static TypeHandle Function(TypeHandle result, int arity, TypeHandle* params, 420 Region* region) { 421 FunctionHandle function = Function(result, Any(region), arity, region); 422 for (int i = 0; i < arity; ++i) { 423 function->InitParameter(i, params[i]); 424 } 425 return function; 426 } 427 428 #define CONSTRUCT_SIMD_TYPE(NAME, Name, name, lane_count, lane_type) \ 429 static TypeHandle Name(Isolate* isolate, Region* region); 430 SIMD128_TYPES(CONSTRUCT_SIMD_TYPE) 431 #undef CONSTRUCT_SIMD_TYPE 432 433 static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg); 434 static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg); 435 Of(double value,Region * region)436 static TypeHandle Of(double value, Region* region) { 437 return Config::from_bitset(BitsetType::ExpandInternals( 438 BitsetType::Lub(value)), region); 439 } Of(i::Object * value,Region * region)440 static TypeHandle Of(i::Object* value, Region* region) { 441 return Config::from_bitset(BitsetType::ExpandInternals( 442 BitsetType::Lub(value)), region); 443 } Of(i::Handle<i::Object> value,Region * region)444 static TypeHandle Of(i::Handle<i::Object> value, Region* region) { 445 return Of(*value, region); 446 } 447 448 // Extraction of components. 449 static TypeHandle Representation(TypeHandle t, Region* region); 450 static TypeHandle Semantic(TypeHandle t, Region* region); 451 452 // Predicates. IsInhabited()453 bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); } 454 Is(TypeImpl * that)455 bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); } 456 template<class TypeHandle> Is(TypeHandle that)457 bool Is(TypeHandle that) { return this->Is(*that); } 458 459 bool Maybe(TypeImpl* that); 460 template<class TypeHandle> Maybe(TypeHandle that)461 bool Maybe(TypeHandle that) { return this->Maybe(*that); } 462 Equals(TypeImpl * that)463 bool Equals(TypeImpl* that) { return this->Is(that) && that->Is(this); } 464 template<class TypeHandle> Equals(TypeHandle that)465 bool Equals(TypeHandle that) { return this->Equals(*that); } 466 467 // Equivalent to Constant(val)->Is(this), but avoiding allocation. 468 bool Contains(i::Object* val); Contains(i::Handle<i::Object> val)469 bool Contains(i::Handle<i::Object> val) { return this->Contains(*val); } 470 471 // State-dependent versions of the above that consider subtyping between 472 // a constant and its map class. 473 inline static TypeHandle NowOf(i::Object* value, Region* region); NowOf(i::Handle<i::Object> value,Region * region)474 static TypeHandle NowOf(i::Handle<i::Object> value, Region* region) { 475 return NowOf(*value, region); 476 } 477 bool NowIs(TypeImpl* that); 478 template<class TypeHandle> NowIs(TypeHandle that)479 bool NowIs(TypeHandle that) { return this->NowIs(*that); } 480 inline bool NowContains(i::Object* val); NowContains(i::Handle<i::Object> val)481 bool NowContains(i::Handle<i::Object> val) { return this->NowContains(*val); } 482 483 bool NowStable(); 484 485 // Inspection. 486 IsRange()487 bool IsRange() { return Config::is_range(this); } IsClass()488 bool IsClass() { 489 return Config::is_class(this) 490 || Config::is_struct(this, StructuralType::kClassTag); 491 } IsConstant()492 bool IsConstant() { 493 return Config::is_struct(this, StructuralType::kConstantTag); 494 } IsContext()495 bool IsContext() { 496 return Config::is_struct(this, StructuralType::kContextTag); 497 } IsArray()498 bool IsArray() { 499 return Config::is_struct(this, StructuralType::kArrayTag); 500 } IsFunction()501 bool IsFunction() { 502 return Config::is_struct(this, StructuralType::kFunctionTag); 503 } 504 AsClass()505 ClassType* AsClass() { return ClassType::cast(this); } AsConstant()506 ConstantType* AsConstant() { return ConstantType::cast(this); } AsRange()507 RangeType* AsRange() { return RangeType::cast(this); } AsContext()508 ContextType* AsContext() { return ContextType::cast(this); } AsArray()509 ArrayType* AsArray() { return ArrayType::cast(this); } AsFunction()510 FunctionType* AsFunction() { return FunctionType::cast(this); } 511 512 // Minimum and maximum of a numeric type. 513 // These functions do not distinguish between -0 and +0. If the type equals 514 // kNaN, they return NaN; otherwise kNaN is ignored. Only call these 515 // functions on subtypes of Number. 516 double Min(); 517 double Max(); 518 519 // Extracts a range from the type: if the type is a range or a union 520 // containing a range, that range is returned; otherwise, NULL is returned. 521 RangeType* GetRange(); 522 IsInteger(double x)523 static bool IsInteger(double x) { 524 return nearbyint(x) == x && !i::IsMinusZero(x); // Allows for infinities. 525 } IsInteger(i::Object * x)526 static bool IsInteger(i::Object* x) { 527 return x->IsNumber() && IsInteger(x->Number()); 528 } 529 530 int NumClasses(); 531 int NumConstants(); 532 533 template<class T> class Iterator; Classes()534 Iterator<i::Map> Classes() { 535 if (this->IsBitset()) return Iterator<i::Map>(); 536 return Iterator<i::Map>(Config::handle(this)); 537 } Constants()538 Iterator<i::Object> Constants() { 539 if (this->IsBitset()) return Iterator<i::Object>(); 540 return Iterator<i::Object>(Config::handle(this)); 541 } 542 543 // Casting and conversion. 544 545 static inline TypeImpl* cast(typename Config::Base* object); 546 547 template<class OtherTypeImpl> 548 static TypeHandle Convert( 549 typename OtherTypeImpl::TypeHandle type, Region* region); 550 551 // Printing. 552 553 enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM }; 554 555 void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS); // NOLINT 556 557 #ifdef DEBUG 558 void Print(); 559 #endif 560 IsUnionForTesting()561 bool IsUnionForTesting() { return IsUnion(); } 562 563 protected: 564 // Friends. 565 566 template<class> friend class Iterator; 567 template<class> friend class TypeImpl; 568 569 // Handle conversion. 570 571 template<class T> handle(T * type)572 static typename Config::template Handle<T>::type handle(T* type) { 573 return Config::handle(type); 574 } unhandle()575 TypeImpl* unhandle() { return this; } 576 577 // Internal inspection. 578 IsNone()579 bool IsNone() { return this == None(); } IsAny()580 bool IsAny() { return this == Any(); } IsBitset()581 bool IsBitset() { return Config::is_bitset(this); } IsUnion()582 bool IsUnion() { return Config::is_struct(this, StructuralType::kUnionTag); } 583 AsBitset()584 bitset AsBitset() { 585 DCHECK(this->IsBitset()); 586 return static_cast<BitsetType*>(this)->Bitset(); 587 } AsUnion()588 UnionType* AsUnion() { return UnionType::cast(this); } 589 590 bitset Representation(); 591 592 // Auxiliary functions. 593 bool SemanticMaybe(TypeImpl* that); 594 BitsetGlb()595 bitset BitsetGlb() { return BitsetType::Glb(this); } BitsetLub()596 bitset BitsetLub() { return BitsetType::Lub(this); } 597 598 bool SlowIs(TypeImpl* that); 599 bool SemanticIs(TypeImpl* that); 600 601 struct Limits { 602 double min; 603 double max; LimitsLimits604 Limits(double min, double max) : min(min), max(max) {} LimitsLimits605 explicit Limits(RangeType* range) : min(range->Min()), max(range->Max()) {} 606 bool IsEmpty(); EmptyLimits607 static Limits Empty() { return Limits(1, 0); } 608 static Limits Intersect(Limits lhs, Limits rhs); 609 static Limits Union(Limits lhs, Limits rhs); 610 }; 611 612 static bool Overlap(RangeType* lhs, RangeType* rhs); 613 static bool Contains(RangeType* lhs, RangeType* rhs); 614 static bool Contains(RangeType* range, ConstantType* constant); 615 static bool Contains(RangeType* range, i::Object* val); 616 617 static int UpdateRange( 618 RangeHandle type, UnionHandle result, int size, Region* region); 619 620 static Limits IntersectRangeAndBitset(TypeHandle range, TypeHandle bits, 621 Region* region); 622 static Limits ToLimits(bitset bits, Region* region); 623 624 bool SimplyEquals(TypeImpl* that); 625 template<class TypeHandle> SimplyEquals(TypeHandle that)626 bool SimplyEquals(TypeHandle that) { return this->SimplyEquals(*that); } 627 628 static int AddToUnion( 629 TypeHandle type, UnionHandle result, int size, Region* region); 630 static int IntersectAux(TypeHandle type, TypeHandle other, UnionHandle result, 631 int size, Limits* limits, Region* region); 632 static TypeHandle NormalizeUnion(UnionHandle unioned, int size, 633 Region* region); 634 static TypeHandle NormalizeRangeAndBitset(RangeHandle range, bitset* bits, 635 Region* region); 636 }; 637 638 639 // ----------------------------------------------------------------------------- 640 // Bitset types (internal). 641 642 template<class Config> 643 class TypeImpl<Config>::BitsetType : public TypeImpl<Config> { 644 protected: 645 friend class TypeImpl<Config>; 646 647 enum : uint32_t { 648 #define DECLARE_TYPE(type, value) k##type = (value), 649 BITSET_TYPE_LIST(DECLARE_TYPE) 650 #undef DECLARE_TYPE 651 kUnusedEOL = 0 652 }; 653 654 static bitset SignedSmall(); 655 static bitset UnsignedSmall(); 656 Bitset()657 bitset Bitset() { return Config::as_bitset(this); } 658 New(bitset bits)659 static TypeImpl* New(bitset bits) { 660 return Config::from_bitset(bits); 661 } New(bitset bits,Region * region)662 static TypeHandle New(bitset bits, Region* region) { 663 return Config::from_bitset(bits, region); 664 } 665 IsInhabited(bitset bits)666 static bool IsInhabited(bitset bits) { 667 return SEMANTIC(bits) != kNone && REPRESENTATION(bits) != kNone; 668 } 669 SemanticIsInhabited(bitset bits)670 static bool SemanticIsInhabited(bitset bits) { 671 return SEMANTIC(bits) != kNone; 672 } 673 Is(bitset bits1,bitset bits2)674 static bool Is(bitset bits1, bitset bits2) { 675 return (bits1 | bits2) == bits2; 676 } 677 678 static double Min(bitset); 679 static double Max(bitset); 680 681 static bitset Glb(TypeImpl* type); // greatest lower bound that's a bitset 682 static bitset Glb(double min, double max); 683 static bitset Lub(TypeImpl* type); // least upper bound that's a bitset 684 static bitset Lub(i::Map* map); 685 static bitset Lub(i::Object* value); 686 static bitset Lub(double value); 687 static bitset Lub(double min, double max); 688 static bitset ExpandInternals(bitset bits); 689 690 static const char* Name(bitset); 691 static void Print(std::ostream& os, bitset); // NOLINT 692 #ifdef DEBUG 693 static void Print(bitset); 694 #endif 695 696 static bitset NumberBits(bitset bits); 697 698 private: 699 struct Boundary { 700 bitset internal; 701 bitset external; 702 double min; 703 }; 704 static const Boundary BoundariesArray[]; 705 static inline const Boundary* Boundaries(); 706 static inline size_t BoundariesSize(); 707 }; 708 709 710 // ----------------------------------------------------------------------------- 711 // Superclass for non-bitset types (internal). 712 // Contains a tag and a variable number of type or value fields. 713 714 template<class Config> 715 class TypeImpl<Config>::StructuralType : public TypeImpl<Config> { 716 protected: 717 template<class> friend class TypeImpl; 718 friend struct ZoneTypeConfig; // For tags. 719 friend struct HeapTypeConfig; 720 721 enum Tag { 722 kClassTag, 723 kConstantTag, 724 kContextTag, 725 kArrayTag, 726 kFunctionTag, 727 kUnionTag 728 }; 729 Length()730 int Length() { 731 return Config::struct_length(Config::as_struct(this)); 732 } Get(int i)733 TypeHandle Get(int i) { 734 DCHECK(0 <= i && i < this->Length()); 735 return Config::struct_get(Config::as_struct(this), i); 736 } Set(int i,TypeHandle type)737 void Set(int i, TypeHandle type) { 738 DCHECK(0 <= i && i < this->Length()); 739 Config::struct_set(Config::as_struct(this), i, type); 740 } Shrink(int length)741 void Shrink(int length) { 742 DCHECK(2 <= length && length <= this->Length()); 743 Config::struct_shrink(Config::as_struct(this), length); 744 } GetValue(int i)745 template<class V> i::Handle<V> GetValue(int i) { 746 DCHECK(0 <= i && i < this->Length()); 747 return Config::template struct_get_value<V>(Config::as_struct(this), i); 748 } SetValue(int i,i::Handle<V> x)749 template<class V> void SetValue(int i, i::Handle<V> x) { 750 DCHECK(0 <= i && i < this->Length()); 751 Config::struct_set_value(Config::as_struct(this), i, x); 752 } 753 New(Tag tag,int length,Region * region)754 static TypeHandle New(Tag tag, int length, Region* region) { 755 DCHECK(1 <= length); 756 return Config::from_struct(Config::struct_create(tag, length, region)); 757 } 758 }; 759 760 761 // ----------------------------------------------------------------------------- 762 // Union types (internal). 763 // A union is a structured type with the following invariants: 764 // - its length is at least 2 765 // - at most one field is a bitset, and it must go into index 0 766 // - no field is a union 767 // - no field is a subtype of any other field 768 template<class Config> 769 class TypeImpl<Config>::UnionType : public StructuralType { 770 public: New(int length,Region * region)771 static UnionHandle New(int length, Region* region) { 772 return Config::template cast<UnionType>( 773 StructuralType::New(StructuralType::kUnionTag, length, region)); 774 } 775 cast(TypeImpl * type)776 static UnionType* cast(TypeImpl* type) { 777 DCHECK(type->IsUnion()); 778 return static_cast<UnionType*>(type); 779 } 780 781 bool Wellformed(); 782 }; 783 784 785 // ----------------------------------------------------------------------------- 786 // Class types. 787 788 template<class Config> 789 class TypeImpl<Config>::ClassType : public StructuralType { 790 public: Map()791 i::Handle<i::Map> Map() { 792 return Config::is_class(this) ? Config::as_class(this) : 793 this->template GetValue<i::Map>(1); 794 } 795 New(i::Handle<i::Map> map,Region * region)796 static ClassHandle New(i::Handle<i::Map> map, Region* region) { 797 ClassHandle type = 798 Config::template cast<ClassType>(Config::from_class(map, region)); 799 if (!type->IsClass()) { 800 type = Config::template cast<ClassType>( 801 StructuralType::New(StructuralType::kClassTag, 2, region)); 802 type->Set(0, BitsetType::New(BitsetType::Lub(*map), region)); 803 type->SetValue(1, map); 804 } 805 return type; 806 } 807 cast(TypeImpl * type)808 static ClassType* cast(TypeImpl* type) { 809 DCHECK(type->IsClass()); 810 return static_cast<ClassType*>(type); 811 } 812 813 private: 814 template<class> friend class TypeImpl; Lub()815 bitset Lub() { 816 return Config::is_class(this) ? 817 BitsetType::Lub(*Config::as_class(this)) : 818 this->Get(0)->AsBitset(); 819 } 820 }; 821 822 823 // ----------------------------------------------------------------------------- 824 // Constant types. 825 826 template<class Config> 827 class TypeImpl<Config>::ConstantType : public StructuralType { 828 public: Value()829 i::Handle<i::Object> Value() { return this->template GetValue<i::Object>(1); } 830 New(i::Handle<i::Object> value,Region * region)831 static ConstantHandle New(i::Handle<i::Object> value, Region* region) { 832 ConstantHandle type = Config::template cast<ConstantType>( 833 StructuralType::New(StructuralType::kConstantTag, 2, region)); 834 type->Set(0, BitsetType::New(BitsetType::Lub(*value), region)); 835 type->SetValue(1, value); 836 return type; 837 } 838 cast(TypeImpl * type)839 static ConstantType* cast(TypeImpl* type) { 840 DCHECK(type->IsConstant()); 841 return static_cast<ConstantType*>(type); 842 } 843 844 private: 845 template<class> friend class TypeImpl; Lub()846 bitset Lub() { return this->Get(0)->AsBitset(); } 847 }; 848 // TODO(neis): Also cache value if numerical. 849 // TODO(neis): Allow restricting the representation. 850 851 852 // ----------------------------------------------------------------------------- 853 // Range types. 854 855 template <class Config> 856 class TypeImpl<Config>::RangeType : public TypeImpl<Config> { 857 public: Min()858 double Min() { return Config::range_get_double(Config::as_range(this), 0); } Max()859 double Max() { return Config::range_get_double(Config::as_range(this), 1); } 860 New(double min,double max,TypeHandle representation,Region * region)861 static RangeHandle New(double min, double max, TypeHandle representation, 862 Region* region) { 863 DCHECK(IsInteger(min) && IsInteger(max)); 864 DCHECK(min <= max); 865 bitset representation_bits = representation->AsBitset(); 866 DCHECK(REPRESENTATION(representation_bits) == representation_bits); 867 868 typename Config::template Handle<typename Config::Range>::type range = 869 Config::range_create(region); 870 871 bitset bits = SEMANTIC(BitsetType::Lub(min, max)) | representation_bits; 872 Config::range_set_bitset(range, bits); 873 Config::range_set_double(range, 0, min, region); 874 Config::range_set_double(range, 1, max, region); 875 return Config::template cast<RangeType>(Config::from_range(range)); 876 } 877 New(Limits lim,bitset representation,Region * region)878 static RangeHandle New(Limits lim, bitset representation, Region* region) { 879 return New(lim.min, lim.max, BitsetType::New(representation, region), 880 region); 881 } 882 cast(TypeImpl * type)883 static RangeType* cast(TypeImpl* type) { 884 DCHECK(type->IsRange()); 885 return static_cast<RangeType*>(type); 886 } 887 888 private: 889 template<class> friend class TypeImpl; Lub()890 bitset Lub() { 891 return Config::range_get_bitset(Config::as_range(this)); 892 } 893 }; 894 895 896 // ----------------------------------------------------------------------------- 897 // Context types. 898 899 template<class Config> 900 class TypeImpl<Config>::ContextType : public StructuralType { 901 public: Outer()902 TypeHandle Outer() { return this->Get(0); } 903 New(TypeHandle outer,Region * region)904 static ContextHandle New(TypeHandle outer, Region* region) { 905 ContextHandle type = Config::template cast<ContextType>( 906 StructuralType::New(StructuralType::kContextTag, 1, region)); 907 type->Set(0, outer); 908 return type; 909 } 910 cast(TypeImpl * type)911 static ContextType* cast(TypeImpl* type) { 912 DCHECK(type->IsContext()); 913 return static_cast<ContextType*>(type); 914 } 915 }; 916 917 918 // ----------------------------------------------------------------------------- 919 // Array types. 920 921 template<class Config> 922 class TypeImpl<Config>::ArrayType : public StructuralType { 923 public: Element()924 TypeHandle Element() { return this->Get(0); } 925 New(TypeHandle element,Region * region)926 static ArrayHandle New(TypeHandle element, Region* region) { 927 ArrayHandle type = Config::template cast<ArrayType>( 928 StructuralType::New(StructuralType::kArrayTag, 1, region)); 929 type->Set(0, element); 930 return type; 931 } 932 cast(TypeImpl * type)933 static ArrayType* cast(TypeImpl* type) { 934 DCHECK(type->IsArray()); 935 return static_cast<ArrayType*>(type); 936 } 937 }; 938 939 940 // ----------------------------------------------------------------------------- 941 // Function types. 942 943 template<class Config> 944 class TypeImpl<Config>::FunctionType : public StructuralType { 945 public: Arity()946 int Arity() { return this->Length() - 2; } Result()947 TypeHandle Result() { return this->Get(0); } Receiver()948 TypeHandle Receiver() { return this->Get(1); } Parameter(int i)949 TypeHandle Parameter(int i) { return this->Get(2 + i); } 950 InitParameter(int i,TypeHandle type)951 void InitParameter(int i, TypeHandle type) { this->Set(2 + i, type); } 952 New(TypeHandle result,TypeHandle receiver,int arity,Region * region)953 static FunctionHandle New( 954 TypeHandle result, TypeHandle receiver, int arity, Region* region) { 955 FunctionHandle type = Config::template cast<FunctionType>( 956 StructuralType::New(StructuralType::kFunctionTag, 2 + arity, region)); 957 type->Set(0, result); 958 type->Set(1, receiver); 959 return type; 960 } 961 cast(TypeImpl * type)962 static FunctionType* cast(TypeImpl* type) { 963 DCHECK(type->IsFunction()); 964 return static_cast<FunctionType*>(type); 965 } 966 }; 967 968 969 // ----------------------------------------------------------------------------- 970 // Type iterators. 971 972 template<class Config> template<class T> 973 class TypeImpl<Config>::Iterator { 974 public: Done()975 bool Done() const { return index_ < 0; } 976 i::Handle<T> Current(); 977 void Advance(); 978 979 private: 980 template<class> friend class TypeImpl; 981 Iterator()982 Iterator() : index_(-1) {} Iterator(TypeHandle type)983 explicit Iterator(TypeHandle type) : type_(type), index_(-1) { 984 Advance(); 985 } 986 987 inline bool matches(TypeHandle type); 988 inline TypeHandle get_type(); 989 990 TypeHandle type_; 991 int index_; 992 }; 993 994 995 // ----------------------------------------------------------------------------- 996 // Zone-allocated types; they are either (odd) integers to represent bitsets, or 997 // (even) pointers to structures for everything else. 998 999 struct ZoneTypeConfig { 1000 typedef TypeImpl<ZoneTypeConfig> Type; 1001 class Base {}; 1002 typedef void* Struct; 1003 // Hack: the Struct and Range types can be aliased in memory, the first 1004 // pointer word of each both must be the tag (kRangeStructTag for Range, 1005 // anything else for Struct) so that we can differentiate them. 1006 struct Range { 1007 void* tag; 1008 int bitset; 1009 double limits[2]; 1010 }; 1011 typedef i::Zone Region; 1012 template<class T> struct Handle { typedef T* type; }; 1013 1014 static const int kRangeStructTag = 0x1000; 1015 null_handleZoneTypeConfig1016 template<class T> static inline T* null_handle() { return nullptr; } 1017 template<class T> static inline T* handle(T* type); 1018 template<class T> static inline T* cast(Type* type); 1019 1020 static inline bool is_bitset(Type* type); 1021 static inline bool is_class(Type* type); 1022 static inline bool is_struct(Type* type, int tag); 1023 static inline bool is_range(Type* type); 1024 1025 static inline Type::bitset as_bitset(Type* type); 1026 static inline i::Handle<i::Map> as_class(Type* type); 1027 static inline Struct* as_struct(Type* type); 1028 static inline Range* as_range(Type* type); 1029 1030 static inline Type* from_bitset(Type::bitset); 1031 static inline Type* from_bitset(Type::bitset, Zone* zone); 1032 static inline Type* from_class(i::Handle<i::Map> map, Zone* zone); 1033 static inline Type* from_struct(Struct* structured); 1034 static inline Type* from_range(Range* range); 1035 1036 static inline Struct* struct_create(int tag, int length, Zone* zone); 1037 static inline void struct_shrink(Struct* structure, int length); 1038 static inline int struct_tag(Struct* structure); 1039 static inline int struct_length(Struct* structure); 1040 static inline Type* struct_get(Struct* structure, int i); 1041 static inline void struct_set(Struct* structure, int i, Type* type); 1042 template<class V> 1043 static inline i::Handle<V> struct_get_value(Struct* structure, int i); 1044 template<class V> static inline void struct_set_value( 1045 Struct* structure, int i, i::Handle<V> x); 1046 1047 static inline Range* range_create(Zone* zone); 1048 static inline int range_get_bitset(Range* range); 1049 static inline void range_set_bitset(Range* range, int); 1050 static inline double range_get_double(Range*, int index); 1051 static inline void range_set_double(Range*, int index, double value, Zone*); 1052 }; 1053 1054 typedef TypeImpl<ZoneTypeConfig> Type; 1055 1056 1057 // ----------------------------------------------------------------------------- 1058 // Heap-allocated types; either smis for bitsets, maps for classes, boxes for 1059 // constants, or fixed arrays for unions. 1060 1061 struct HeapTypeConfig { 1062 typedef TypeImpl<HeapTypeConfig> Type; 1063 typedef i::Object Base; 1064 typedef i::FixedArray Struct; 1065 typedef i::FixedArray Range; 1066 typedef i::Isolate Region; 1067 template<class T> struct Handle { typedef i::Handle<T> type; }; 1068 1069 static const int kRangeStructTag = 0xffff; 1070 null_handleHeapTypeConfig1071 template<class T> static inline i::Handle<T> null_handle() { 1072 return i::Handle<T>(); 1073 } 1074 template<class T> static inline i::Handle<T> handle(T* type); 1075 template<class T> static inline i::Handle<T> cast(i::Handle<Type> type); 1076 1077 static inline bool is_bitset(Type* type); 1078 static inline bool is_class(Type* type); 1079 static inline bool is_struct(Type* type, int tag); 1080 static inline bool is_range(Type* type); 1081 1082 static inline Type::bitset as_bitset(Type* type); 1083 static inline i::Handle<i::Map> as_class(Type* type); 1084 static inline i::Handle<Struct> as_struct(Type* type); 1085 static inline i::Handle<Range> as_range(Type* type); 1086 1087 static inline Type* from_bitset(Type::bitset); 1088 static inline i::Handle<Type> from_bitset(Type::bitset, Isolate* isolate); 1089 static inline i::Handle<Type> from_class( 1090 i::Handle<i::Map> map, Isolate* isolate); 1091 static inline i::Handle<Type> from_struct(i::Handle<Struct> structure); 1092 static inline i::Handle<Type> from_range(i::Handle<Range> range); 1093 1094 static inline i::Handle<Struct> struct_create( 1095 int tag, int length, Isolate* isolate); 1096 static inline void struct_shrink(i::Handle<Struct> structure, int length); 1097 static inline int struct_tag(i::Handle<Struct> structure); 1098 static inline int struct_length(i::Handle<Struct> structure); 1099 static inline i::Handle<Type> struct_get(i::Handle<Struct> structure, int i); 1100 static inline void struct_set( 1101 i::Handle<Struct> structure, int i, i::Handle<Type> type); 1102 template<class V> 1103 static inline i::Handle<V> struct_get_value( 1104 i::Handle<Struct> structure, int i); 1105 template<class V> 1106 static inline void struct_set_value( 1107 i::Handle<Struct> structure, int i, i::Handle<V> x); 1108 1109 static inline i::Handle<Range> range_create(Isolate* isolate); 1110 static inline int range_get_bitset(i::Handle<Range> range); 1111 static inline void range_set_bitset(i::Handle<Range> range, int value); 1112 static inline double range_get_double(i::Handle<Range> range, int index); 1113 static inline void range_set_double(i::Handle<Range> range, int index, 1114 double value, Isolate* isolate); 1115 }; 1116 1117 typedef TypeImpl<HeapTypeConfig> HeapType; 1118 1119 1120 // ----------------------------------------------------------------------------- 1121 // Type bounds. A simple struct to represent a pair of lower/upper types. 1122 1123 template<class Config> 1124 struct BoundsImpl { 1125 typedef TypeImpl<Config> Type; 1126 typedef typename Type::TypeHandle TypeHandle; 1127 typedef typename Type::Region Region; 1128 1129 TypeHandle lower; 1130 TypeHandle upper; 1131 BoundsImplBoundsImpl1132 BoundsImpl() : // Make sure accessing uninitialized bounds crashes big-time. 1133 lower(Config::template null_handle<Type>()), 1134 upper(Config::template null_handle<Type>()) {} BoundsImplBoundsImpl1135 explicit BoundsImpl(TypeHandle t) : lower(t), upper(t) {} BoundsImplBoundsImpl1136 BoundsImpl(TypeHandle l, TypeHandle u) : lower(l), upper(u) { 1137 DCHECK(lower->Is(upper)); 1138 } 1139 1140 // Unrestricted bounds. UnboundedBoundsImpl1141 static BoundsImpl Unbounded() { 1142 return BoundsImpl(Type::None(), Type::Any()); 1143 } 1144 1145 // Meet: both b1 and b2 are known to hold. BothBoundsImpl1146 static BoundsImpl Both(BoundsImpl b1, BoundsImpl b2, Region* region) { 1147 TypeHandle lower = Type::Union(b1.lower, b2.lower, region); 1148 TypeHandle upper = Type::Intersect(b1.upper, b2.upper, region); 1149 // Lower bounds are considered approximate, correct as necessary. 1150 if (!lower->Is(upper)) lower = upper; 1151 return BoundsImpl(lower, upper); 1152 } 1153 1154 // Join: either b1 or b2 is known to hold. EitherBoundsImpl1155 static BoundsImpl Either(BoundsImpl b1, BoundsImpl b2, Region* region) { 1156 TypeHandle lower = Type::Intersect(b1.lower, b2.lower, region); 1157 TypeHandle upper = Type::Union(b1.upper, b2.upper, region); 1158 return BoundsImpl(lower, upper); 1159 } 1160 NarrowLowerBoundsImpl1161 static BoundsImpl NarrowLower(BoundsImpl b, TypeHandle t, Region* region) { 1162 TypeHandle lower = Type::Union(b.lower, t, region); 1163 // Lower bounds are considered approximate, correct as necessary. 1164 if (!lower->Is(b.upper)) lower = b.upper; 1165 return BoundsImpl(lower, b.upper); 1166 } NarrowUpperBoundsImpl1167 static BoundsImpl NarrowUpper(BoundsImpl b, TypeHandle t, Region* region) { 1168 TypeHandle lower = b.lower; 1169 TypeHandle upper = Type::Intersect(b.upper, t, region); 1170 // Lower bounds are considered approximate, correct as necessary. 1171 if (!lower->Is(upper)) lower = upper; 1172 return BoundsImpl(lower, upper); 1173 } 1174 NarrowsBoundsImpl1175 bool Narrows(BoundsImpl that) { 1176 return that.lower->Is(this->lower) && this->upper->Is(that.upper); 1177 } 1178 }; 1179 1180 typedef BoundsImpl<ZoneTypeConfig> Bounds; 1181 1182 } // namespace internal 1183 } // namespace v8 1184 1185 #endif // V8_TYPES_H_ 1186