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 concurrent compilation context. 96 97 98 #define BITSET_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 V(Oddball, kBoolean | kNull | kUndefined) \ 119 V(Signed32, kSmi | kOtherSigned32) \ 120 V(Number, kSigned32 | kUnsigned32 | kDouble) \ 121 V(String, kInternalizedString | kOtherString) \ 122 V(UniqueName, kSymbol | kInternalizedString) \ 123 V(Name, kSymbol | kString) \ 124 V(NumberOrString, kNumber | kString) \ 125 V(Object, kUndetectable | kArray | kFunction | \ 126 kRegExp | kOtherObject) \ 127 V(Receiver, kObject | kProxy) \ 128 V(Allocated, kDouble | kName | kReceiver) \ 129 V(Any, kOddball | kNumber | kAllocated | kInternal) \ 130 V(NonNumber, kAny - kNumber) \ 131 V(Detectable, kAllocated - kUndetectable) 132 133 134 class Type : public Object { 135 public: 136 #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ 137 static Type* type() { return from_bitset(k##type); } 138 BITSET_TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) 139 #undef DEFINE_TYPE_CONSTRUCTOR 140 141 static Type* Class(Handle<i::Map> map) { return from_handle(map); } 142 static Type* Constant(Handle<i::HeapObject> value) { 143 return Constant(value, value->GetIsolate()); 144 } 145 static Type* Constant(Handle<i::Object> value, Isolate* isolate) { 146 return from_handle(isolate->factory()->NewBox(value)); 147 } 148 149 static Type* Union(Handle<Type> type1, Handle<Type> type2); 150 static Type* Intersect(Handle<Type> type1, Handle<Type> type2); 151 static Type* Optional(Handle<Type> type); // type \/ Undefined 152 153 static Type* Of(Handle<i::Object> value) { 154 return from_bitset(LubBitset(*value)); 155 } 156 157 bool Is(Type* that) { return this == that || SlowIs(that); } 158 bool Is(Handle<Type> that) { return this->Is(*that); } 159 bool Maybe(Type* that); 160 bool Maybe(Handle<Type> that) { return this->Maybe(*that); } 161 162 // State-dependent versions of Of and Is that consider subtyping between 163 // a constant and its map class. 164 static Type* OfCurrently(Handle<i::Object> value); 165 bool IsCurrently(Type* that); 166 bool IsCurrently(Handle<Type> that) { return this->IsCurrently(*that); } 167 168 bool IsClass() { return is_class(); } 169 bool IsConstant() { return is_constant(); } 170 Handle<i::Map> AsClass() { return as_class(); } 171 Handle<i::Object> AsConstant() { return as_constant(); } 172 173 int NumClasses(); 174 int NumConstants(); 175 176 template<class T> 177 class Iterator { 178 public: 179 bool Done() const { return index_ < 0; } 180 Handle<T> Current(); 181 void Advance(); 182 183 private: 184 friend class Type; 185 186 Iterator() : index_(-1) {} 187 explicit Iterator(Handle<Type> type) : type_(type), index_(-1) { 188 Advance(); 189 } 190 191 inline bool matches(Handle<Type> type); 192 inline Handle<Type> get_type(); 193 194 Handle<Type> type_; 195 int index_; 196 }; 197 198 Iterator<i::Map> Classes() { 199 if (this->is_bitset()) return Iterator<i::Map>(); 200 return Iterator<i::Map>(this->handle()); 201 } 202 Iterator<i::Object> Constants() { 203 if (this->is_bitset()) return Iterator<i::Object>(); 204 return Iterator<i::Object>(this->handle()); 205 } 206 207 static Type* cast(i::Object* object) { 208 Type* t = static_cast<Type*>(object); 209 ASSERT(t->is_bitset() || t->is_class() || 210 t->is_constant() || t->is_union()); 211 return t; 212 } 213 214 #ifdef OBJECT_PRINT 215 void TypePrint(); 216 void TypePrint(FILE* out); 217 #endif 218 219 private: 220 // A union is a fixed array containing types. Invariants: 221 // - its length is at least 2 222 // - at most one field is a bitset, and it must go into index 0 223 // - no field is a union 224 typedef FixedArray Unioned; 225 226 enum { 227 #define DECLARE_TYPE(type, value) k##type = (value), 228 BITSET_TYPE_LIST(DECLARE_TYPE) 229 #undef DECLARE_TYPE 230 kUnusedEOL = 0 231 }; 232 233 bool is_none() { return this == None(); } 234 bool is_bitset() { return this->IsSmi(); } 235 bool is_class() { return this->IsMap(); } 236 bool is_constant() { return this->IsBox(); } 237 bool is_union() { return this->IsFixedArray(); } 238 239 bool SlowIs(Type* that); 240 241 int as_bitset() { return Smi::cast(this)->value(); } 242 Handle<i::Map> as_class() { return Handle<i::Map>::cast(handle()); } 243 Handle<i::Object> as_constant() { 244 Handle<i::Box> box = Handle<i::Box>::cast(handle()); 245 return i::handle(box->value(), box->GetIsolate()); 246 } 247 Handle<Unioned> as_union() { return Handle<Unioned>::cast(handle()); } 248 249 Handle<Type> handle() { return handle_via_isolate_of(this); } 250 Handle<Type> handle_via_isolate_of(Type* type) { 251 ASSERT(type->IsHeapObject()); 252 return i::handle(this, i::HeapObject::cast(type)->GetIsolate()); 253 } 254 255 static Type* from_bitset(int bitset) { 256 return static_cast<Type*>(i::Object::cast(i::Smi::FromInt(bitset))); 257 } 258 static Type* from_handle(Handle<i::HeapObject> handle) { 259 return static_cast<Type*>(i::Object::cast(*handle)); 260 } 261 262 static Handle<Type> union_get(Handle<Unioned> unioned, int i) { 263 Type* type = static_cast<Type*>(unioned->get(i)); 264 ASSERT(!type->is_union()); 265 return type->handle_via_isolate_of(from_handle(unioned)); 266 } 267 268 int LubBitset(); // least upper bound that's a bitset 269 int GlbBitset(); // greatest lower bound that's a bitset 270 271 static int LubBitset(i::Object* value); 272 static int LubBitset(i::Map* map); 273 274 bool InUnion(Handle<Unioned> unioned, int current_size); 275 int ExtendUnion(Handle<Unioned> unioned, int current_size); 276 int ExtendIntersection( 277 Handle<Unioned> unioned, Handle<Type> type, int current_size); 278 279 static const char* bitset_name(int bitset); 280 }; 281 282 283 // A simple struct to represent a pair of lower/upper type bounds. 284 struct Bounds { 285 Handle<Type> lower; 286 Handle<Type> upper; 287 288 Bounds() {} 289 Bounds(Handle<Type> l, Handle<Type> u) : lower(l), upper(u) { 290 ASSERT(lower->Is(upper)); 291 } 292 Bounds(Type* l, Type* u, Isolate* isl) : lower(l, isl), upper(u, isl) { 293 ASSERT(lower->Is(upper)); 294 } 295 explicit Bounds(Handle<Type> t) : lower(t), upper(t) { 296 ASSERT(lower->Is(upper)); 297 } 298 Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) { 299 ASSERT(lower->Is(upper)); 300 } 301 302 // Unrestricted bounds. 303 static Bounds Unbounded(Isolate* isl) { 304 return Bounds(Type::None(), Type::Any(), isl); 305 } 306 307 // Meet: both b1 and b2 are known to hold. 308 static Bounds Both(Bounds b1, Bounds b2, Isolate* isl) { 309 Handle<Type> lower(Type::Union(b1.lower, b2.lower), isl); 310 Handle<Type> upper(Type::Intersect(b1.upper, b2.upper), isl); 311 // Lower bounds are considered approximate, correct as necessary. 312 lower = handle(Type::Intersect(lower, upper), isl); 313 return Bounds(lower, upper); 314 } 315 316 // Join: either b1 or b2 is known to hold. 317 static Bounds Either(Bounds b1, Bounds b2, Isolate* isl) { 318 return Bounds( 319 handle(Type::Intersect(b1.lower, b2.lower), isl), 320 handle(Type::Union(b1.upper, b2.upper), isl)); 321 } 322 323 static Bounds NarrowLower(Bounds b, Handle<Type> t, Isolate* isl) { 324 // Lower bounds are considered approximate, correct as necessary. 325 t = handle(Type::Intersect(t, b.upper), 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( 330 handle(Type::Intersect(b.lower, t), isl), 331 handle(Type::Intersect(b.upper, t), isl)); 332 } 333 }; 334 335 } } // namespace v8::internal 336 337 #endif // V8_TYPES_H_ 338
