LCOV - code coverage report
Current view: top level - src/ast - ast-types.h (source / functions) Hit Total Coverage
Test: app.info Lines: 70 73 95.9 %
Date: 2017-04-26 Functions: 14 20 70.0 %

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

Generated by: LCOV version 1.10