1 // Copyright 2013 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_TYPES_H_ 29 #define V8_TYPES_H_ 30 31 #include "v8.h" 32 33 #include "objects.h" 34 35 namespace v8 { 36 namespace internal { 37 38 39 // A simple type system for compiler-internal use. It is based entirely on 40 // union types, and all subtyping hence amounts to set inclusion. Besides the 41 // obvious primitive types and some predefined unions, the type language also 42 // can express class types (a.k.a. specific maps) and singleton types (i.e., 43 // concrete constants). 44 // 45 // The following equations and inequations hold: 46 // 47 // None <= T 48 // T <= Any 49 // 50 // Oddball = Boolean \/ Null \/ Undefined 51 // Number = Signed32 \/ Unsigned32 \/ Double 52 // Smi <= Signed32 53 // Name = String \/ Symbol 54 // UniqueName = InternalizedString \/ Symbol 55 // InternalizedString < String 56 // 57 // Allocated = Receiver \/ Number \/ Name 58 // Detectable = Allocated - Undetectable 59 // Undetectable < Object 60 // Receiver = Object \/ Proxy 61 // Array < Object 62 // Function < Object 63 // RegExp < Object 64 // 65 // Class(map) < T iff instance_type(map) < T 66 // Constant(x) < T iff instance_type(map(x)) < T 67 // 68 // Note that Constant(x) < Class(map(x)) does _not_ hold, since x's map can 69 // change! (Its instance type cannot, however.) 70 // TODO(rossberg): the latter is not currently true for proxies, because of fix, 71 // but will hold once we implement direct proxies. 72 // 73 // There are two main functions for testing types: 74 // 75 // T1->Is(T2) -- tests whether T1 is included in T2 (i.e., T1 <= T2) 76 // T1->Maybe(T2) -- tests whether T1 and T2 overlap (i.e., T1 /\ T2 =/= 0) 77 // 78 // Typically, the former is to be used to select representations (e.g., via 79 // T->Is(Integer31())), and the to check whether a specific case needs handling 80 // (e.g., via T->Maybe(Number())). 81 // 82 // There is no functionality to discover whether a type is a leaf in the 83 // lattice. That is intentional. It should always be possible to refine the 84 // lattice (e.g., splitting up number types further) without invalidating any 85 // existing assumptions or tests. 86 // 87 // Consequently, do not use pointer equality for type tests, always use Is! 88 // 89 // Internally, all 'primitive' types, and their unions, are represented as 90 // bitsets via smis. Class is a heap pointer to the respective map. Only 91 // Constant's, or unions containing Class'es or Constant's, require allocation. 92 // Note that the bitset representation is closed under both Union and Intersect. 93 // 94 // The type representation is heap-allocated, so cannot (currently) be used in 95 // a parallel compilation context. 96 97 98 #define PRIMITIVE_TYPE_LIST(V) \ 99 V(None, 0) \ 100 V(Null, 1 << 0) \ 101 V(Undefined, 1 << 1) \ 102 V(Boolean, 1 << 2) \ 103 V(Smi, 1 << 3) \ 104 V(OtherSigned32, 1 << 4) \ 105 V(Unsigned32, 1 << 5) \ 106 V(Double, 1 << 6) \ 107 V(Symbol, 1 << 7) \ 108 V(InternalizedString, 1 << 8) \ 109 V(OtherString, 1 << 9) \ 110 V(Undetectable, 1 << 10) \ 111 V(Array, 1 << 11) \ 112 V(Function, 1 << 12) \ 113 V(RegExp, 1 << 13) \ 114 V(OtherObject, 1 << 14) \ 115 V(Proxy, 1 << 15) \ 116 V(Internal, 1 << 16) 117 118 #define COMPOSED_TYPE_LIST(V) \ 119 V(Oddball, kBoolean | kNull | kUndefined) \ 120 V(Signed32, kSmi | kOtherSigned32) \ 121 V(Number, kSigned32 | kUnsigned32 | kDouble) \ 122 V(String, kInternalizedString | kOtherString) \ 123 V(UniqueName, kSymbol | kInternalizedString) \ 124 V(Name, kSymbol | kString) \ 125 V(NumberOrString, kNumber | kString) \ 126 V(Object, kUndetectable | kArray | kFunction | \ 127 kRegExp | kOtherObject) \ 128 V(Receiver, kObject | kProxy) \ 129 V(Allocated, kDouble | kName | kReceiver) \ 130 V(Any, kOddball | kNumber | kAllocated | kInternal) \ 131 V(Detectable, kAllocated - kUndetectable) 132 133 #define TYPE_LIST(V) \ 134 PRIMITIVE_TYPE_LIST(V) \ 135 COMPOSED_TYPE_LIST(V) 136 137 138 139 class Type : public Object { 140 public: 141 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ 142 static Type* type() { return from_bitset(k##type); } 143 TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) 144 #undef DEFINE_TYPE_CONSTRUCTOR 145 146 static Type* Class(Handle<Map> map) { return from_handle(map); } 147 static Type* Constant(Handle<HeapObject> value) { 148 return Constant(value, value->GetIsolate()); 149 } 150 static Type* Constant(Handle<v8::internal::Object> value, Isolate* isolate) { 151 return from_handle(isolate->factory()->NewBox(value)); 152 } 153 154 static Type* Union(Handle<Type> type1, Handle<Type> type2); 155 static Type* Intersect(Handle<Type> type1, Handle<Type> type2); 156 static Type* Optional(Handle<Type> type); // type \/ Undefined 157 158 bool Is(Type* that) { return (this == that) ? true : IsSlowCase(that); } 159 bool Is(Handle<Type> that) { return this->Is(*that); } 160 bool Maybe(Type* that); 161 bool Maybe(Handle<Type> that) { return this->Maybe(*that); } 162 163 bool IsClass() { return is_class(); } 164 bool IsConstant() { return is_constant(); } 165 Handle<Map> AsClass() { return as_class(); } 166 Handle<v8::internal::Object> AsConstant() { return as_constant(); } 167 168 int NumClasses(); 169 int NumConstants(); 170 171 template<class T> 172 class Iterator { 173 public: 174 bool Done() const { return index_ < 0; } 175 Handle<T> Current(); 176 void Advance(); 177 178 private: 179 friend class Type; 180 181 Iterator() : index_(-1) {} 182 explicit Iterator(Handle<Type> type) : type_(type), index_(-1) { 183 Advance(); 184 } 185 186 inline bool matches(Handle<Type> type); 187 inline Handle<Type> get_type(); 188 189 Handle<Type> type_; 190 int index_; 191 }; 192 193 Iterator<Map> Classes() { 194 if (this->is_bitset()) return Iterator<Map>(); 195 return Iterator<Map>(this->handle()); 196 } 197 Iterator<v8::internal::Object> Constants() { 198 if (this->is_bitset()) return Iterator<v8::internal::Object>(); 199 return Iterator<v8::internal::Object>(this->handle()); 200 } 201 202 static Type* cast(v8::internal::Object* object) { 203 Type* t = static_cast<Type*>(object); 204 ASSERT(t->is_bitset() || t->is_class() || 205 t->is_constant() || t->is_union()); 206 return t; 207 } 208 209 #ifdef OBJECT_PRINT 210 void TypePrint(); 211 void TypePrint(FILE* out); 212 #endif 213 214 private: 215 // A union is a fixed array containing types. Invariants: 216 // - its length is at least 2 217 // - at most one field is a bitset, and it must go into index 0 218 // - no field is a union 219 typedef FixedArray Unioned; 220 221 enum { 222 #define DECLARE_TYPE(type, value) k##type = (value), 223 TYPE_LIST(DECLARE_TYPE) 224 #undef DECLARE_TYPE 225 kUnusedEOL = 0 226 }; 227 228 bool is_bitset() { return this->IsSmi(); } 229 bool is_class() { return this->IsMap(); } 230 bool is_constant() { return this->IsBox(); } 231 bool is_union() { return this->IsFixedArray(); } 232 233 bool IsSlowCase(Type* that); 234 235 int as_bitset() { return Smi::cast(this)->value(); } 236 Handle<Map> as_class() { return Handle<Map>::cast(handle()); } 237 Handle<v8::internal::Object> as_constant() { 238 Handle<Box> box = Handle<Box>::cast(handle()); 239 return v8::internal::handle(box->value(), box->GetIsolate()); 240 } 241 Handle<Unioned> as_union() { return Handle<Unioned>::cast(handle()); } 242 243 Handle<Type> handle() { return handle_via_isolate_of(this); } 244 Handle<Type> handle_via_isolate_of(Type* type) { 245 ASSERT(type->IsHeapObject()); 246 return v8::internal::handle(this, HeapObject::cast(type)->GetIsolate()); 247 } 248 249 static Type* from_bitset(int bitset) { 250 return static_cast<Type*>(Object::cast(Smi::FromInt(bitset))); 251 } 252 static Type* from_handle(Handle<HeapObject> handle) { 253 return static_cast<Type*>(Object::cast(*handle)); 254 } 255 256 static Handle<Type> union_get(Handle<Unioned> unioned, int i) { 257 Type* type = static_cast<Type*>(unioned->get(i)); 258 ASSERT(!type->is_union()); 259 return type->handle_via_isolate_of(from_handle(unioned)); 260 } 261 262 int LubBitset(); // least upper bound that's a bitset 263 int GlbBitset(); // greatest lower bound that's a bitset 264 bool InUnion(Handle<Unioned> unioned, int current_size); 265 int ExtendUnion(Handle<Unioned> unioned, int current_size); 266 int ExtendIntersection( 267 Handle<Unioned> unioned, Handle<Type> type, int current_size); 268 269 static const char* GetComposedName(int type) { 270 switch (type) { 271 #define PRINT_COMPOSED_TYPE(type, value) \ 272 case k##type: \ 273 return # type; 274 COMPOSED_TYPE_LIST(PRINT_COMPOSED_TYPE) 275 #undef PRINT_COMPOSED_TYPE 276 } 277 return NULL; 278 } 279 280 static const char* GetPrimitiveName(int type) { 281 switch (type) { 282 #define PRINT_PRIMITIVE_TYPE(type, value) \ 283 case k##type: \ 284 return # type; 285 PRIMITIVE_TYPE_LIST(PRINT_PRIMITIVE_TYPE) 286 #undef PRINT_PRIMITIVE_TYPE 287 default: 288 UNREACHABLE(); 289 return "InvalidType"; 290 } 291 } 292 }; 293 294 295 // A simple struct to represent a pair of lower/upper type bounds. 296 struct Bounds { 297 Handle<Type> lower; 298 Handle<Type> upper; 299 300 Bounds() {} 301 Bounds(Handle<Type> l, Handle<Type> u) : lower(l), upper(u) {} 302 Bounds(Type* l, Type* u, Isolate* isl) : lower(l, isl), upper(u, isl) {} 303 explicit Bounds(Handle<Type> t) : lower(t), upper(t) {} 304 Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) {} 305 306 // Unrestricted bounds. 307 static Bounds Unbounded(Isolate* isl) { 308 return Bounds(Type::None(), Type::Any(), isl); 309 } 310 311 // Meet: both b1 and b2 are known to hold. 312 static Bounds Both(Bounds b1, Bounds b2, Isolate* isl) { 313 return Bounds( 314 handle(Type::Union(b1.lower, b2.lower), isl), 315 handle(Type::Intersect(b1.upper, b2.upper), isl)); 316 } 317 318 // Join: either b1 or b2 is known to hold. 319 static Bounds Either(Bounds b1, Bounds b2, Isolate* isl) { 320 return Bounds( 321 handle(Type::Intersect(b1.lower, b2.lower), isl), 322 handle(Type::Union(b1.upper, b2.upper), isl)); 323 } 324 325 static Bounds NarrowLower(Bounds b, Handle<Type> t, Isolate* isl) { 326 return Bounds(handle(Type::Union(b.lower, t), isl), b.upper); 327 } 328 static Bounds NarrowUpper(Bounds b, Handle<Type> t, Isolate* isl) { 329 return Bounds(b.lower, handle(Type::Intersect(b.upper, t), isl)); 330 } 331 }; 332 333 } } // namespace v8::internal 334 335 #endif // V8_TYPES_H_ 336
