Types: cache lub bitset to avoid heap access

src/types.h

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 69 matching lines @@
 // (e.g., via T->Maybe(Number())).
 //
 // There is no functionality to discover whether a type is a leaf in the
 // lattice. That is intentional. It should always be possible to refine the
 // lattice (e.g., splitting up number types further) without invalidating any
 // existing assumptions or tests.
 //
 // Consequently, do not use pointer equality for type tests, always use Is!
 //
 // Internally, all 'primitive' types, and their unions, are represented as
-// bitsets via smis. Class is a heap pointer to the respective map. Only
-// Constant's, or unions containing Class'es or Constant's, require allocation.
+// bitsets. Class is a heap pointer to the respective map. Only Constant's, or
+// unions containing Class'es or Constant's, currently require allocation.
 // Note that the bitset representation is closed under both Union and Intersect.
 //
-// The type representation is heap-allocated, so cannot (currently) be used in
-// a concurrent compilation context.
+// There are two type representations, using different allocation:
+//
+// - class Type (zone-allocated, for compiler and concurrent compilation)
+// - class HeapType (heap-allocated, for persistent types)
+//
+// Both provide the same API, and the Convert method can be used to interconvert
+// them. For zone types, no query method touches the heap, only constructors do.
 
 
 #define BITSET_TYPE_LIST(V)              \
   V(None,                0)              \
   V(Null,                1 << 0)         \
   V(Undefined,           1 << 1)         \
   V(Boolean,             1 << 2)         \
   V(Smi,                 1 << 3)         \
   V(OtherSigned32,       1 << 4)         \
   V(Unsigned32,          1 << 5)         \
@@ skipping 34 matching lines @@
 //   static bool is_bitset(Type*);
 //   static bool is_class(Type*);
 //   static bool is_constant(Type*);
 //   static bool is_union(Type*);
 //   static int as_bitset(Type*);
 //   static i::Handle<i::Map> as_class(Type*);
 //   static i::Handle<i::Object> as_constant(Type*);
 //   static Handle<Unioned>::type as_union(Type*);
 //   static Type* from_bitset(int bitset);
 //   static Handle<Type>::type from_bitset(int bitset, Region*);
-//   static Handle<Type>::type from_class(i::Handle<i::Map>, Region*)
-//   static Handle<Type>::type from_constant(i::Handle<i::Object>, Region*);
+//   static Handle<Type>::type from_class(i::Handle<Map>, int lub, Region*);
+//   static Handle<Type>::type from_constant(i::Handle<Object>, int, Region*);
 //   static Handle<Type>::type from_union(Handle<Unioned>::type);
 //   static Handle<Unioned>::type union_create(int size, Region*);
 //   static void union_shrink(Handle<Unioned>::type, int size);
 //   static Handle<Type>::type union_get(Handle<Unioned>::type, int);
 //   static void union_set(Handle<Unioned>::type, int, Handle<Type>::type);
 //   static int union_length(Handle<Unioned>::type);
+//   static int lub_bitset(Type*);
 // }
 template<class Config>
 class TypeImpl : public Config::Base {
  public:
   typedef typename Config::template Handle<TypeImpl>::type TypeHandle;
   typedef typename Config::Region Region;
 
   #define DEFINE_TYPE_CONSTRUCTOR(type, value)                        \
     static TypeImpl* type() { return Config::from_bitset(k##type); }  \
     static TypeHandle type(Region* region) {                          \
       return Config::from_bitset(k##type, region);                    \
     }
   BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR)
   #undef DEFINE_TYPE_CONSTRUCTOR
 
   static TypeHandle Class(i::Handle<i::Map> map, Region* region) {
-    return Config::from_class(map, region);
+    return Config::from_class(map, LubBitset(*map), region);
   }
   static TypeHandle Constant(i::Handle<i::Object> value, Region* region) {
-    return Config::from_constant(value, region);
+    return Config::from_constant(value, LubBitset(*value), region);
   }
 
   static TypeHandle Union(TypeHandle type1, TypeHandle type2, Region* reg);
   static TypeHandle Intersect(TypeHandle type1, TypeHandle type2, Region* reg);
 
   static TypeHandle Of(i::Handle<i::Object> value, Region* region) {
     return Config::from_bitset(LubBitset(*value), region);
   }
 
   bool Is(TypeImpl* that) { return this == that || this->SlowIs(that); }
@@ skipping 140 matching lines @@
   }
   static Tag tagged_tag(Tagged* tagged) {
     return static_cast<Tag>(reinterpret_cast<intptr_t>(tagged->at(0)));
   }
   template<class T>
   static T tagged_get(Tagged* tagged, int i) {
     return reinterpret_cast<T>(tagged->at(i + 1));
   }
   template<class T>
   static void tagged_set(Tagged* tagged, int i, T value) {
-    tagged->at(i + 1) = reinterpret_cast<T>(value);
+    tagged->at(i + 1) = reinterpret_cast<void*>(value);
   }
   static int tagged_length(Tagged* tagged) {
     return tagged->length() - 1;
   }
 
  public:
   typedef TypeImpl<ZoneTypeConfig> Type;
   class Base {};
   typedef i::ZoneList<Type*> Unioned;
   typedef i::Zone Region;
@@ skipping 19 matching lines @@
   static int as_bitset(Type* type) {
     ASSERT(is_bitset(type));
     return static_cast<int>(reinterpret_cast<intptr_t>(type) >> 1);
   }
   static Tagged* as_tagged(Type* type) {
     ASSERT(is_tagged(type));
     return reinterpret_cast<Tagged*>(type);
   }
   static i::Handle<i::Map> as_class(Type* type) {
     ASSERT(is_class(type));
-    return i::Handle<i::Map>(tagged_get<i::Map**>(as_tagged(type), 0));
+    return i::Handle<i::Map>(tagged_get<i::Map**>(as_tagged(type), 1));
   }
   static i::Handle<i::Object> as_constant(Type* type) {
     ASSERT(is_constant(type));
-    return i::Handle<i::Object>(tagged_get<i::Object**>(as_tagged(type), 0));
+    return i::Handle<i::Object>(tagged_get<i::Object**>(as_tagged(type), 1));
   }
   static Unioned* as_union(Type* type) {
     ASSERT(is_union(type));
     return tagged_as_union(as_tagged(type));
   }
   static Unioned* tagged_as_union(Tagged* tagged) {
     ASSERT(tagged_is_union(tagged));
     return reinterpret_cast<Unioned*>(tagged);
   }
 
   static Type* from_bitset(int bitset) {
     return reinterpret_cast<Type*>((bitset << 1) | 1);
   }
   static Type* from_bitset(int bitset, Zone* Zone) {
     return from_bitset(bitset);
   }
   static Type* from_tagged(Tagged* tagged) {
     return reinterpret_cast<Type*>(tagged);
   }
-  static Type* from_class(i::Handle<i::Map> map, Zone* zone) {
-    Tagged* tagged = tagged_create(kClassTag, 1, zone);
-    tagged_set(tagged, 0, map.location());
+  static Type* from_class(i::Handle<i::Map> map, int lub, Zone* zone) {
+    Tagged* tagged = tagged_create(kClassTag, 2, zone);
+    tagged_set(tagged, 0, lub);
+    tagged_set(tagged, 1, map.location());
     return from_tagged(tagged);
   }
-  static Type* from_constant(i::Handle<i::Object> value, Zone* zone) {
-    Tagged* tagged = tagged_create(kConstantTag, 1, zone);
-    tagged_set(tagged, 0, value.location());
+  static Type* from_constant(i::Handle<i::Object> value, int lub, Zone* zone) {
+    Tagged* tagged = tagged_create(kConstantTag, 2, zone);
+    tagged_set(tagged, 0, lub);
+    tagged_set(tagged, 1, value.location());
     return from_tagged(tagged);
   }
   static Type* from_union(Unioned* unioned) {
     return from_tagged(tagged_from_union(unioned));
   }
   static Tagged* tagged_from_union(Unioned* unioned) {
     return reinterpret_cast<Tagged*>(unioned);
   }
 
   static Unioned* union_create(int size, Zone* zone) {
     return tagged_as_union(tagged_create(kUnionTag, size, zone));
   }
   static void union_shrink(Unioned* unioned, int size) {
     tagged_shrink(tagged_from_union(unioned), size);
   }
   static Type* union_get(Unioned* unioned, int i) {
     Type* type = tagged_get<Type*>(tagged_from_union(unioned), i);
     ASSERT(!is_union(type));
     return type;
   }
   static void union_set(Unioned* unioned, int i, Type* type) {
     ASSERT(!is_union(type));
     tagged_set(tagged_from_union(unioned), i, type);
   }
   static int union_length(Unioned* unioned) {
     return tagged_length(tagged_from_union(unioned));
   }
+  static int lub_bitset(Type* type) {
+    ASSERT(is_class(type) || is_constant(type));
+    return tagged_get<int>(as_tagged(type), 0);
+  }
 };
 
 
 // Heap-allocated types are either smis for bitsets, maps for classes, boxes for
 // constants, or fixed arrays for unions.
 struct HeapTypeConfig {
   typedef TypeImpl<HeapTypeConfig> Type;
   typedef i::Object Base;
   typedef i::FixedArray Unioned;
   typedef i::Isolate Region;
@@ skipping 21 matching lines @@
   static i::Handle<Unioned> as_union(Type* type) {
     return i::handle(i::FixedArray::cast(type));
   }
 
   static Type* from_bitset(int bitset) {
     return Type::cast(i::Smi::FromInt(bitset));
   }
   static i::Handle<Type> from_bitset(int bitset, Isolate* isolate) {
     return i::handle(from_bitset(bitset), isolate);
   }
-  static i::Handle<Type> from_class(i::Handle<i::Map> map, Isolate* isolate) {
+  static i::Handle<Type> from_class(
+      i::Handle<i::Map> map, int lub, Isolate* isolate) {
     return i::Handle<Type>::cast(i::Handle<Object>::cast(map));
   }
   static i::Handle<Type> from_constant(
-      i::Handle<i::Object> value, Isolate* isolate) {
+      i::Handle<i::Object> value, int lub, Isolate* isolate) {
     i::Handle<Box> box = isolate->factory()->NewBox(value);
     return i::Handle<Type>::cast(i::Handle<Object>::cast(box));
   }
   static i::Handle<Type> from_union(i::Handle<Unioned> unioned) {
     return i::Handle<Type>::cast(i::Handle<Object>::cast(unioned));
   }
 
   static i::Handle<Unioned> union_create(int size, Isolate* isolate) {
     return isolate->factory()->NewFixedArray(size);
   }
   static void union_shrink(i::Handle<Unioned> unioned, int size) {
     unioned->Shrink(size);
   }
   static i::Handle<Type> union_get(i::Handle<Unioned> unioned, int i) {
     Type* type = static_cast<Type*>(unioned->get(i));
     ASSERT(!is_union(type));
     return i::handle(type, unioned->GetIsolate());
   }
   static void union_set(
       i::Handle<Unioned> unioned, int i, i::Handle<Type> type) {
     ASSERT(!is_union(*type));
     unioned->set(i, *type);
   }
   static int union_length(i::Handle<Unioned> unioned) {
     return unioned->length();
   }
+  static int lub_bitset(Type* type) {
+    return 0;

[Toon Verwaest, 2014/03/10 12:52:18]

I presume this is because of the "bitset ? bitset : <compute bitset>"? Please
add a comment at least if that's the case. Or maybe give that 0 a name, eg,
kComputeBitset and compare to it, eg bitset == kComputeBitset ? <compute> :
bitset;

[rossberg, 2014/03/11 10:11:39]

Done.

+  }
 };
 
 typedef TypeImpl<ZoneTypeConfig> Type;
 typedef TypeImpl<HeapTypeConfig> HeapType;
 
 
 // A simple struct to represent a pair of lower/upper type bounds.
 template<class Config>
 struct BoundsImpl {
   typedef TypeImpl<Config> Type;
@@ skipping 46 matching lines @@
     return that.lower->Is(this->lower) && this->upper->Is(that.upper);
   }
 };
 
 typedef BoundsImpl<ZoneTypeConfig> Bounds;
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TYPES_H_