ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 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 |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 51 | // Number = Signed32 \/ Unsigned32 \/ Double |
| 52 | // Smi <= Signed32 |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 53 | // Name = String \/ Symbol |
| 54 | // UniqueName = InternalizedString \/ Symbol |
| 55 | // InternalizedString < String |
| 56 | // |
danno@chromium.org | 4172848 | 2013-06-12 22:31:22 +0000 | [diff] [blame] | 57 | // Allocated = Receiver \/ Number \/ Name |
| 58 | // Detectable = Allocated - Undetectable |
| 59 | // Undetectable < Object |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 60 | // Receiver = Object \/ Proxy |
| 61 | // Array < Object |
| 62 | // Function < Object |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 63 | // RegExp < Object |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 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 | // |
danno@chromium.org | 4172848 | 2013-06-12 22:31:22 +0000 | [diff] [blame] | 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())). |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 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 | // |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 87 | // Consequently, do not use pointer equality for type tests, always use Is! |
| 88 | // |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 89 | // Internally, all 'primitive' types, and their unions, are represented as |
danno@chromium.org | 1fd77d5 | 2013-06-07 16:01:45 +0000 | [diff] [blame] | 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. |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 92 | // Note that the bitset representation is closed under both Union and Intersect. |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 93 | // |
| 94 | // The type representation is heap-allocated, so cannot (currently) be used in |
rossberg@chromium.org | 9259716 | 2013-08-23 13:28:00 +0000 | [diff] [blame] | 95 | // a concurrent compilation context. |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 96 | |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 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) \ |
machenbach@chromium.org | 528ce02 | 2013-09-23 14:09:36 +0000 | [diff] [blame] | 131 | V(NonNumber, kAny - kNumber) \ |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 132 | V(Detectable, kAllocated - kUndetectable) |
| 133 | |
| 134 | #define TYPE_LIST(V) \ |
| 135 | PRIMITIVE_TYPE_LIST(V) \ |
| 136 | COMPOSED_TYPE_LIST(V) |
| 137 | |
| 138 | |
| 139 | |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 140 | class Type : public Object { |
| 141 | public: |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 142 | #define DEFINE_TYPE_CONSTRUCTOR(type, value) \ |
| 143 | static Type* type() { return from_bitset(k##type); } |
| 144 | TYPE_LIST(DEFINE_TYPE_CONSTRUCTOR) |
| 145 | #undef DEFINE_TYPE_CONSTRUCTOR |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 146 | |
| 147 | static Type* Class(Handle<Map> map) { return from_handle(map); } |
| 148 | static Type* Constant(Handle<HeapObject> value) { |
danno@chromium.org | 1fd77d5 | 2013-06-07 16:01:45 +0000 | [diff] [blame] | 149 | return Constant(value, value->GetIsolate()); |
| 150 | } |
| 151 | static Type* Constant(Handle<v8::internal::Object> value, Isolate* isolate) { |
| 152 | return from_handle(isolate->factory()->NewBox(value)); |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 153 | } |
| 154 | |
| 155 | static Type* Union(Handle<Type> type1, Handle<Type> type2); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 156 | static Type* Intersect(Handle<Type> type1, Handle<Type> type2); |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 157 | static Type* Optional(Handle<Type> type); // type \/ Undefined |
| 158 | |
mvstanton@chromium.org | dd6d9ee | 2013-10-11 10:35:37 +0000 | [diff] [blame^] | 159 | bool Is(Type* that) { return (this == that) ? true : SlowIs(that); } |
danno@chromium.org | 4172848 | 2013-06-12 22:31:22 +0000 | [diff] [blame] | 160 | bool Is(Handle<Type> that) { return this->Is(*that); } |
| 161 | bool Maybe(Type* that); |
| 162 | bool Maybe(Handle<Type> that) { return this->Maybe(*that); } |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 163 | |
danno@chromium.org | 4172848 | 2013-06-12 22:31:22 +0000 | [diff] [blame] | 164 | bool IsClass() { return is_class(); } |
| 165 | bool IsConstant() { return is_constant(); } |
| 166 | Handle<Map> AsClass() { return as_class(); } |
| 167 | Handle<v8::internal::Object> AsConstant() { return as_constant(); } |
| 168 | |
| 169 | int NumClasses(); |
| 170 | int NumConstants(); |
| 171 | |
| 172 | template<class T> |
| 173 | class Iterator { |
| 174 | public: |
| 175 | bool Done() const { return index_ < 0; } |
| 176 | Handle<T> Current(); |
| 177 | void Advance(); |
| 178 | |
| 179 | private: |
| 180 | friend class Type; |
| 181 | |
| 182 | Iterator() : index_(-1) {} |
| 183 | explicit Iterator(Handle<Type> type) : type_(type), index_(-1) { |
| 184 | Advance(); |
| 185 | } |
| 186 | |
| 187 | inline bool matches(Handle<Type> type); |
| 188 | inline Handle<Type> get_type(); |
| 189 | |
| 190 | Handle<Type> type_; |
| 191 | int index_; |
| 192 | }; |
| 193 | |
| 194 | Iterator<Map> Classes() { |
| 195 | if (this->is_bitset()) return Iterator<Map>(); |
| 196 | return Iterator<Map>(this->handle()); |
| 197 | } |
| 198 | Iterator<v8::internal::Object> Constants() { |
| 199 | if (this->is_bitset()) return Iterator<v8::internal::Object>(); |
| 200 | return Iterator<v8::internal::Object>(this->handle()); |
| 201 | } |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 202 | |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 203 | static Type* cast(v8::internal::Object* object) { |
| 204 | Type* t = static_cast<Type*>(object); |
| 205 | ASSERT(t->is_bitset() || t->is_class() || |
| 206 | t->is_constant() || t->is_union()); |
| 207 | return t; |
| 208 | } |
| 209 | |
| 210 | #ifdef OBJECT_PRINT |
| 211 | void TypePrint(); |
| 212 | void TypePrint(FILE* out); |
| 213 | #endif |
| 214 | |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 215 | private: |
| 216 | // A union is a fixed array containing types. Invariants: |
| 217 | // - its length is at least 2 |
| 218 | // - at most one field is a bitset, and it must go into index 0 |
| 219 | // - no field is a union |
| 220 | typedef FixedArray Unioned; |
| 221 | |
| 222 | enum { |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 223 | #define DECLARE_TYPE(type, value) k##type = (value), |
| 224 | TYPE_LIST(DECLARE_TYPE) |
| 225 | #undef DECLARE_TYPE |
| 226 | kUnusedEOL = 0 |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 227 | }; |
| 228 | |
| 229 | bool is_bitset() { return this->IsSmi(); } |
| 230 | bool is_class() { return this->IsMap(); } |
danno@chromium.org | 1fd77d5 | 2013-06-07 16:01:45 +0000 | [diff] [blame] | 231 | bool is_constant() { return this->IsBox(); } |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 232 | bool is_union() { return this->IsFixedArray(); } |
| 233 | |
mvstanton@chromium.org | dd6d9ee | 2013-10-11 10:35:37 +0000 | [diff] [blame^] | 234 | bool SlowIs(Type* that); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 235 | |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 236 | int as_bitset() { return Smi::cast(this)->value(); } |
| 237 | Handle<Map> as_class() { return Handle<Map>::cast(handle()); } |
danno@chromium.org | 4172848 | 2013-06-12 22:31:22 +0000 | [diff] [blame] | 238 | Handle<v8::internal::Object> as_constant() { |
| 239 | Handle<Box> box = Handle<Box>::cast(handle()); |
| 240 | return v8::internal::handle(box->value(), box->GetIsolate()); |
| 241 | } |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 242 | Handle<Unioned> as_union() { return Handle<Unioned>::cast(handle()); } |
| 243 | |
| 244 | Handle<Type> handle() { return handle_via_isolate_of(this); } |
| 245 | Handle<Type> handle_via_isolate_of(Type* type) { |
| 246 | ASSERT(type->IsHeapObject()); |
| 247 | return v8::internal::handle(this, HeapObject::cast(type)->GetIsolate()); |
| 248 | } |
| 249 | |
| 250 | static Type* from_bitset(int bitset) { |
| 251 | return static_cast<Type*>(Object::cast(Smi::FromInt(bitset))); |
| 252 | } |
| 253 | static Type* from_handle(Handle<HeapObject> handle) { |
| 254 | return static_cast<Type*>(Object::cast(*handle)); |
| 255 | } |
| 256 | |
| 257 | static Handle<Type> union_get(Handle<Unioned> unioned, int i) { |
| 258 | Type* type = static_cast<Type*>(unioned->get(i)); |
| 259 | ASSERT(!type->is_union()); |
| 260 | return type->handle_via_isolate_of(from_handle(unioned)); |
| 261 | } |
| 262 | |
| 263 | int LubBitset(); // least upper bound that's a bitset |
| 264 | int GlbBitset(); // greatest lower bound that's a bitset |
| 265 | bool InUnion(Handle<Unioned> unioned, int current_size); |
| 266 | int ExtendUnion(Handle<Unioned> unioned, int current_size); |
mstarzinger@chromium.org | 1510d58 | 2013-06-28 14:00:48 +0000 | [diff] [blame] | 267 | int ExtendIntersection( |
| 268 | Handle<Unioned> unioned, Handle<Type> type, int current_size); |
danno@chromium.org | bee5199 | 2013-07-10 14:57:15 +0000 | [diff] [blame] | 269 | |
| 270 | static const char* GetComposedName(int type) { |
| 271 | switch (type) { |
| 272 | #define PRINT_COMPOSED_TYPE(type, value) \ |
| 273 | case k##type: \ |
| 274 | return # type; |
| 275 | COMPOSED_TYPE_LIST(PRINT_COMPOSED_TYPE) |
| 276 | #undef PRINT_COMPOSED_TYPE |
| 277 | } |
| 278 | return NULL; |
| 279 | } |
| 280 | |
| 281 | static const char* GetPrimitiveName(int type) { |
| 282 | switch (type) { |
| 283 | #define PRINT_PRIMITIVE_TYPE(type, value) \ |
| 284 | case k##type: \ |
| 285 | return # type; |
| 286 | PRIMITIVE_TYPE_LIST(PRINT_PRIMITIVE_TYPE) |
| 287 | #undef PRINT_PRIMITIVE_TYPE |
| 288 | default: |
| 289 | UNREACHABLE(); |
| 290 | return "InvalidType"; |
| 291 | } |
| 292 | } |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 293 | }; |
| 294 | |
danno@chromium.org | 169691d | 2013-07-15 08:01:13 +0000 | [diff] [blame] | 295 | |
| 296 | // A simple struct to represent a pair of lower/upper type bounds. |
| 297 | struct Bounds { |
| 298 | Handle<Type> lower; |
| 299 | Handle<Type> upper; |
| 300 | |
| 301 | Bounds() {} |
| 302 | Bounds(Handle<Type> l, Handle<Type> u) : lower(l), upper(u) {} |
| 303 | Bounds(Type* l, Type* u, Isolate* isl) : lower(l, isl), upper(u, isl) {} |
| 304 | explicit Bounds(Handle<Type> t) : lower(t), upper(t) {} |
| 305 | Bounds(Type* t, Isolate* isl) : lower(t, isl), upper(t, isl) {} |
| 306 | |
danno@chromium.org | 5940060 | 2013-08-13 17:09:37 +0000 | [diff] [blame] | 307 | // Unrestricted bounds. |
| 308 | static Bounds Unbounded(Isolate* isl) { |
| 309 | return Bounds(Type::None(), Type::Any(), isl); |
| 310 | } |
| 311 | |
danno@chromium.org | 169691d | 2013-07-15 08:01:13 +0000 | [diff] [blame] | 312 | // Meet: both b1 and b2 are known to hold. |
| 313 | static Bounds Both(Bounds b1, Bounds b2, Isolate* isl) { |
| 314 | return Bounds( |
| 315 | handle(Type::Union(b1.lower, b2.lower), isl), |
| 316 | handle(Type::Intersect(b1.upper, b2.upper), isl)); |
| 317 | } |
| 318 | |
| 319 | // Join: either b1 or b2 is known to hold. |
| 320 | static Bounds Either(Bounds b1, Bounds b2, Isolate* isl) { |
| 321 | return Bounds( |
| 322 | handle(Type::Intersect(b1.lower, b2.lower), isl), |
| 323 | handle(Type::Union(b1.upper, b2.upper), isl)); |
| 324 | } |
| 325 | |
| 326 | static Bounds NarrowLower(Bounds b, Handle<Type> t, Isolate* isl) { |
| 327 | return Bounds(handle(Type::Union(b.lower, t), isl), b.upper); |
| 328 | } |
| 329 | static Bounds NarrowUpper(Bounds b, Handle<Type> t, Isolate* isl) { |
| 330 | return Bounds(b.lower, handle(Type::Intersect(b.upper, t), isl)); |
| 331 | } |
| 332 | }; |
| 333 | |
ulan@chromium.org | dfe5307 | 2013-06-06 14:14:51 +0000 | [diff] [blame] | 334 | } } // namespace v8::internal |
| 335 | |
| 336 | #endif // V8_TYPES_H_ |