src/types.h

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