Revert "[turbofan] Remove the representation dimension from Type."

src/compiler/types.h

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_COMPILER_TYPES_H_
 #define V8_COMPILER_TYPES_H_
 
 #include "src/conversions.h"
 #include "src/handles.h"
 #include "src/objects.h"
@@ skipping 29 matching lines @@
 //   InternalizedString < String
 //
 //   Receiver = Object \/ Proxy
 //   RegExp < Object
 //   OtherUndetectable < Object
 //   DetectableReceiver = Receiver - OtherUndetectable
 //
 //   Constant(x) < T  iff instance_type(map(x)) < T
 //
 //
+// REPRESENTATIONAL DIMENSION
+//
+// For the representation axis, the following holds:
+//
+//   None <= R
+//   R <= Any
+//
+//   UntaggedInt = UntaggedInt1 \/ UntaggedInt8 \/
+//                 UntaggedInt16 \/ UntaggedInt32
+//   UntaggedFloat = UntaggedFloat32 \/ UntaggedFloat64
+//   UntaggedNumber = UntaggedInt \/ UntaggedFloat
+//   Untagged = UntaggedNumber \/ UntaggedPtr
+//   Tagged = TaggedInt \/ TaggedPtr
+//
+// Subtyping relates the two dimensions, for example:
+//
+//   Number <= Tagged \/ UntaggedNumber
+//   Object <= TaggedPtr \/ UntaggedPtr
+//
+// That holds because the semantic type constructors defined by the API create
+// types that allow for all possible representations, and dually, the ones for
+// representation types initially include all semantic ranges. Representations
+// can then e.g. be narrowed for a given semantic type using intersection:
+//
+//   SignedSmall /\ TaggedInt       (a 'smi')
+//   Number /\ TaggedPtr            (a heap number)
+//
+//
 // RANGE TYPES
 //
 // A range type represents a continuous integer interval by its minimum and
 // maximum value.  Either value may be an infinity, in which case that infinity
 // itself is also included in the range.   A range never contains NaN or -0.
 //
 // If a value v happens to be an integer n, then Constant(v) is considered a
 // subtype of Range(n, n) (and therefore also a subtype of any larger range).
 // In order to avoid large unions, however, it is usually a good idea to use
 // Range rather than Constant.
@@ skipping 30 matching lines @@
 // See test/cctest/test-types.cc for a comprehensive executable specification,
 // especially with respect to the properties of the more exotic 'temporal'
 // constructors and predicates (those prefixed 'Now').
 //
 //
 // IMPLEMENTATION
 //
 // Internally, all 'primitive' types, and their unions, are represented as
 // bitsets. Bit 0 is reserved for tagging. Only structured types require
 // allocation.
+// Note that the bitset representation is closed under both Union and Intersect.
 
 // -----------------------------------------------------------------------------
 // Values for bitset types
 
 // clang-format off
 
 #define MASK_BITSET_TYPE_LIST(V) \
-  V(Semantic,       0xfffffffeu)
+  V(Representation, 0xffc00000u) \
+  V(Semantic,       0x003ffffeu)
 
+#define REPRESENTATION(k) ((k) & BitsetType::kRepresentation)
 #define SEMANTIC(k)       ((k) & BitsetType::kSemantic)
 
+#define REPRESENTATION_BITSET_TYPE_LIST(V)    \
+  V(None,               0)                    \
+  V(UntaggedBit,        1u << 22 | kSemantic) \
+  V(UntaggedIntegral8,  1u << 23 | kSemantic) \
+  V(UntaggedIntegral16, 1u << 24 | kSemantic) \
+  V(UntaggedIntegral32, 1u << 25 | kSemantic) \
+  V(UntaggedFloat32,    1u << 26 | kSemantic) \
+  V(UntaggedFloat64,    1u << 27 | kSemantic) \
+  V(UntaggedSimd128,    1u << 28 | kSemantic) \
+  V(UntaggedPointer,    1u << 29 | kSemantic) \
+  V(TaggedSigned,       1u << 30 | kSemantic) \
+  V(TaggedPointer,      1u << 31 | kSemantic) \
+  \
+  V(UntaggedIntegral,   kUntaggedBit | kUntaggedIntegral8 |        \
+                        kUntaggedIntegral16 | kUntaggedIntegral32) \
+  V(UntaggedFloat,      kUntaggedFloat32 | kUntaggedFloat64)       \
+  V(UntaggedNumber,     kUntaggedIntegral | kUntaggedFloat)        \
+  V(Untagged,           kUntaggedNumber | kUntaggedPointer)        \
+  V(Tagged,             kTaggedSigned | kTaggedPointer)
+
 #define INTERNAL_BITSET_TYPE_LIST(V)                                      \
-  V(OtherUnsigned31, 1u << 1)  \
-  V(OtherUnsigned32, 1u << 2)  \
-  V(OtherSigned32,   1u << 3)  \
-  V(OtherNumber,     1u << 4)  \
+  V(OtherUnsigned31, 1u << 1 | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(OtherUnsigned32, 1u << 2 | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(OtherSigned32,   1u << 3 | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(OtherNumber,     1u << 4 | REPRESENTATION(kTagged | kUntaggedNumber))
 
 #define SEMANTIC_BITSET_TYPE_LIST(V) \
-  V(None,                0u)        \
-  V(Negative31,          1u << 5)   \
-  V(Null,                1u << 6)   \
-  V(Undefined,           1u << 7)   \
-  V(Boolean,             1u << 8)   \
-  V(Unsigned30,          1u << 9)   \
-  V(MinusZero,           1u << 10)  \
-  V(NaN,                 1u << 11)  \
-  V(Symbol,              1u << 12)  \
-  V(InternalizedString,  1u << 13)  \
-  V(OtherString,         1u << 14)  \
-  V(Simd,                1u << 15)  \
-  V(OtherObject,         1u << 17)  \
-  V(OtherUndetectable,   1u << 16)  \
-  V(Proxy,               1u << 18)  \
-  V(Function,            1u << 19)  \
-  V(Hole,                1u << 20)  \
-  V(OtherInternal,       1u << 21)  \
+  V(Negative31,          1u << 5  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Null,                1u << 6  | REPRESENTATION(kTaggedPointer)) \
+  V(Undefined,           1u << 7  | REPRESENTATION(kTaggedPointer)) \
+  V(Boolean,             1u << 8  | REPRESENTATION(kTaggedPointer)) \
+  V(Unsigned30,          1u << 9  | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(MinusZero,           1u << 10 | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(NaN,                 1u << 11 | REPRESENTATION(kTagged | kUntaggedNumber)) \
+  V(Symbol,              1u << 12 | REPRESENTATION(kTaggedPointer)) \
+  V(InternalizedString,  1u << 13 | REPRESENTATION(kTaggedPointer)) \
+  V(OtherString,         1u << 14 | REPRESENTATION(kTaggedPointer)) \
+  V(Simd,                1u << 15 | REPRESENTATION(kTaggedPointer)) \
+  V(OtherObject,         1u << 17 | REPRESENTATION(kTaggedPointer)) \
+  V(OtherUndetectable,   1u << 16 | REPRESENTATION(kTaggedPointer)) \
+  V(Proxy,               1u << 18 | REPRESENTATION(kTaggedPointer)) \
+  V(Function,            1u << 19 | REPRESENTATION(kTaggedPointer)) \
+  V(Hole,                1u << 20 | REPRESENTATION(kTaggedPointer)) \
+  V(OtherInternal,       1u << 21 | REPRESENTATION(kTagged | kUntagged)) \
   \
   V(Signed31,                   kUnsigned30 | kNegative31) \
   V(Signed32,                   kSigned31 | kOtherUnsigned31 | kOtherSigned32) \
   V(Signed32OrMinusZero,        kSigned32 | kMinusZero) \
   V(Signed32OrMinusZeroOrNaN,   kSigned32 | kMinusZero | kNaN) \
   V(Negative32,                 kNegative31 | kOtherSigned32) \
   V(Unsigned31,                 kUnsigned30 | kOtherUnsigned31) \
   V(Unsigned32,                 kUnsigned30 | kOtherUnsigned31 | \
                                 kOtherUnsigned32) \
   V(Unsigned32OrMinusZero,      kUnsigned32 | kMinusZero) \
@@ skipping 40 matching lines @@
  *     -2^31   -2^30     0      2^30    2^31    2^32
  *
  * E.g., OtherUnsigned32 (OU32) covers all integers from 2^31 to 2^32-1.
  *
  * Some of the atomic numerical bitsets are internal only (see
  * INTERNAL_BITSET_TYPE_LIST).  To a types user, they should only occur in
  * union with certain other bitsets.  For instance, OtherNumber should only
  * occur as part of PlainNumber.
  */
 
-#define PROPER_BITSET_TYPE_LIST(V) SEMANTIC_BITSET_TYPE_LIST(V)
+#define PROPER_BITSET_TYPE_LIST(V)   \
+  REPRESENTATION_BITSET_TYPE_LIST(V) \
+  SEMANTIC_BITSET_TYPE_LIST(V)
 
-#define BITSET_TYPE_LIST(V)    \
-  MASK_BITSET_TYPE_LIST(V)     \
-  INTERNAL_BITSET_TYPE_LIST(V) \
+#define BITSET_TYPE_LIST(V)          \
+  MASK_BITSET_TYPE_LIST(V)           \
+  REPRESENTATION_BITSET_TYPE_LIST(V) \
+  INTERNAL_BITSET_TYPE_LIST(V)       \
   SEMANTIC_BITSET_TYPE_LIST(V)
 
 class Type;
 
 // -----------------------------------------------------------------------------
 // Bitset types (internal).
 
 class BitsetType {
  public:
   typedef uint32_t bitset;  // Internal
 
   enum : uint32_t {
 #define DECLARE_TYPE(type, value) k##type = (value),
     BITSET_TYPE_LIST(DECLARE_TYPE)
 #undef DECLARE_TYPE
         kUnusedEOL = 0
   };
 
   static bitset SignedSmall();
   static bitset UnsignedSmall();
 
   bitset Bitset() {
     return static_cast<bitset>(reinterpret_cast<uintptr_t>(this) ^ 1u);
   }
 
-  static bool IsInhabited(bitset bits) { return SemanticIsInhabited(bits); }
+  static bool IsInhabited(bitset bits) {
+    return SEMANTIC(bits) != kNone && REPRESENTATION(bits) != kNone;
+  }
 
   static bool SemanticIsInhabited(bitset bits) {
     return SEMANTIC(bits) != kNone;
   }
 
   static bool Is(bitset bits1, bitset bits2) {
     return (bits1 | bits2) == bits2;
   }
 
   static double Min(bitset);
@@ skipping 90 matching lines @@
 
   ConstantType(BitsetType::bitset bitset, i::Handle<i::Object> object)
       : TypeBase(kConstant), bitset_(bitset), object_(object) {}
 
   BitsetType::bitset Lub() { return bitset_; }
 
   BitsetType::bitset bitset_;
   Handle<i::Object> object_;
 };
 // TODO(neis): Also cache value if numerical.
+// TODO(neis): Allow restricting the representation.
 
 // -----------------------------------------------------------------------------
 // Range types.
 
 class RangeType : public TypeBase {
  public:
   struct Limits {
     double min;
     double max;
     Limits(double min, double max) : min(min), max(max) {}
     explicit Limits(RangeType* range) : min(range->Min()), max(range->Max()) {}
     bool IsEmpty();
     static Limits Empty() { return Limits(1, 0); }
     static Limits Intersect(Limits lhs, Limits rhs);
     static Limits Union(Limits lhs, Limits rhs);
   };
 
   double Min() { return limits_.min; }
   double Max() { return limits_.max; }
 
  private:
   friend class Type;
   friend class BitsetType;
   friend class UnionType;
 
-  static Type* New(double min, double max, Zone* zone) {
-    return New(Limits(min, max), zone);
+  static Type* New(double min, double max, BitsetType::bitset representation,
+                   Zone* zone) {
+    return New(Limits(min, max), representation, zone);
   }
 
   static bool IsInteger(double x) {
     return nearbyint(x) == x && !i::IsMinusZero(x);  // Allows for infinities.
   }
 
-  static Type* New(Limits lim, Zone* zone) {
+  static Type* New(Limits lim, BitsetType::bitset representation, Zone* zone) {
     DCHECK(IsInteger(lim.min) && IsInteger(lim.max));
     DCHECK(lim.min <= lim.max);
-    BitsetType::bitset bits = SEMANTIC(BitsetType::Lub(lim.min, lim.max));
+    DCHECK(REPRESENTATION(representation) == representation);
+    BitsetType::bitset bits =
+        SEMANTIC(BitsetType::Lub(lim.min, lim.max)) | representation;
 
     return AsType(new (zone->New(sizeof(RangeType))) RangeType(bits, lim));
   }
 
   static RangeType* cast(Type* type) {
     DCHECK(IsKind(type, kRange));
     return static_cast<RangeType*>(FromType(type));
   }
 
   RangeType(BitsetType::bitset bitset, Limits limits)
@@ skipping 106 matching lines @@
     return BitsetType::New(BitsetType::SignedSmall());
   }
   static Type* UnsignedSmall() {
     return BitsetType::New(BitsetType::UnsignedSmall());
   }
 
   static Type* Constant(i::Handle<i::Object> value, Zone* zone) {
     return ConstantType::New(value, zone);
   }
   static Type* Range(double min, double max, Zone* zone) {
-    return RangeType::New(min, max, zone);
+    return RangeType::New(min, max, REPRESENTATION(BitsetType::kTagged |
+                                                   BitsetType::kUntaggedNumber),
+                          zone);
   }
   static Type* Tuple(Type* first, Type* second, Type* third, Zone* zone) {
     Type* tuple = TupleType::New(3, zone);
     tuple->AsTuple()->InitElement(0, first);
     tuple->AsTuple()->InitElement(1, second);
     tuple->AsTuple()->InitElement(2, third);
     return tuple;
   }
 
   static Type* Union(Type* type1, Type* type2, Zone* zone);
   static Type* Intersect(Type* type1, Type* type2, Zone* zone);
 
   static Type* Of(double value, Zone* zone) {
     return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value)));
   }
   static Type* Of(i::Object* value, Zone* zone) {
     return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(value)));
   }
   static Type* Of(i::Handle<i::Object> value, Zone* zone) {
     return Of(*value, zone);
   }
 
   static Type* For(i::Map* map) {
     return BitsetType::New(BitsetType::ExpandInternals(BitsetType::Lub(map)));
   }
   static Type* For(i::Handle<i::Map> map) { return For(*map); }
 
   // Extraction of components.
+  static Type* Representation(Type* t, Zone* zone);
   static Type* Semantic(Type* t, Zone* zone);
 
   // Predicates.
   bool IsInhabited() { return BitsetType::IsInhabited(this->BitsetLub()); }
 
   bool Is(Type* that) { return this == that || this->SlowIs(that); }
   bool Maybe(Type* that);
   bool Equals(Type* that) { return this->Is(that) && that->Is(this); }
 
   // Equivalent to Constant(val)->Is(this), but avoiding allocation.
@@ skipping 47 matching lines @@
     int index_;
   };
 
   Iterator<i::Object> Constants() {
     if (this->IsBitset()) return Iterator<i::Object>();
     return Iterator<i::Object>(this);
   }
 
   // Printing.
 
-  void PrintTo(std::ostream& os);
+  enum PrintDimension { BOTH_DIMS, SEMANTIC_DIM, REPRESENTATION_DIM };
+
+  void PrintTo(std::ostream& os, PrintDimension dim = BOTH_DIMS);  // NOLINT
 
 #ifdef DEBUG
   void Print();
 #endif
 
   // Helpers for testing.
   bool IsBitsetForTesting() { return IsBitset(); }
   bool IsUnionForTesting() { return IsUnion(); }
   bitset AsBitsetForTesting() { return AsBitset(); }
   UnionType* AsUnionForTesting() { return AsUnion(); }
@@ skipping 12 matching lines @@
   bool IsAny() { return this == Any(); }
   bool IsBitset() { return BitsetType::IsBitset(this); }
   bool IsUnion() { return IsKind(TypeBase::kUnion); }
 
   bitset AsBitset() {
     DCHECK(this->IsBitset());
     return reinterpret_cast<BitsetType*>(this)->Bitset();
   }
   UnionType* AsUnion() { return UnionType::cast(this); }
 
+  bitset Representation();
+
   // Auxiliary functions.
   bool SemanticMaybe(Type* that);
 
   bitset BitsetGlb() { return BitsetType::Glb(this); }
   bitset BitsetLub() { return BitsetType::Lub(this); }
 
   bool SlowIs(Type* that);
   bool SemanticIs(Type* that);
 
   static bool Overlap(RangeType* lhs, RangeType* rhs);
@@ skipping 14 matching lines @@
                           RangeType::Limits* limits, Zone* zone);
   static Type* NormalizeUnion(Type* unioned, int size, Zone* zone);
   static Type* NormalizeRangeAndBitset(Type* range, bitset* bits, Zone* zone);
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_TYPES_H_