The Tor Browser / file comparison
comparison: js/src/jit/TypeDescrSet.cpp
js/src/jit/TypeDescrSet.cpp
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d067ba67f594 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | |
| 2 * vim: set ts=8 sts=4 et sw=4 tw=99: | |
| 3 * This Source Code Form is subject to the terms of the Mozilla Public | |
| 4 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 6 | |
| 7 #include "jit/TypeDescrSet.h" | |
| 8 | |
| 9 #include "mozilla/HashFunctions.h" | |
| 10 | |
| 11 #include "builtin/TypedObject.h" | |
| 12 #include "jit/IonBuilder.h" | |
| 13 | |
| 14 using namespace js; | |
| 15 using namespace jit; | |
| 16 | |
| 17 /////////////////////////////////////////////////////////////////////////// | |
| 18 // TypeDescrSet hasher | |
| 19 | |
| 20 HashNumber | |
| 21 TypeDescrSetHasher::hash(TypeDescrSet key) | |
| 22 { | |
| 23 HashNumber hn = mozilla::HashGeneric(key.length()); | |
| 24 for (size_t i = 0; i < key.length(); i++) | |
| 25 hn = mozilla::AddToHash(hn, uintptr_t(key.get(i))); | |
| 26 return hn; | |
| 27 } | |
| 28 | |
| 29 bool | |
| 30 TypeDescrSetHasher::match(TypeDescrSet key1, TypeDescrSet key2) | |
| 31 { | |
| 32 if (key1.length() != key2.length()) | |
| 33 return false; | |
| 34 | |
| 35 // Note: entries are always sorted | |
| 36 for (size_t i = 0; i < key1.length(); i++) { | |
| 37 if (key1.get(i) != key2.get(i)) | |
| 38 return false; | |
| 39 } | |
| 40 | |
| 41 return true; | |
| 42 } | |
| 43 | |
| 44 /////////////////////////////////////////////////////////////////////////// | |
| 45 // TypeDescrSetBuilder | |
| 46 | |
| 47 TypeDescrSetBuilder::TypeDescrSetBuilder() | |
| 48 : invalid_(false) | |
| 49 {} | |
| 50 | |
| 51 bool | |
| 52 TypeDescrSetBuilder::insert(TypeDescr *descr) | |
| 53 { | |
| 54 // All type descriptors should be tenured, so it is safe to assume | |
| 55 // that the pointers do not change during compilation, since no | |
| 56 // major GC can overlap with compilation. | |
| 57 JS_ASSERT(!GetIonContext()->runtime->isInsideNursery(descr)); | |
| 58 | |
| 59 if (invalid_) | |
| 60 return true; | |
| 61 | |
| 62 if (entries_.empty()) | |
| 63 return entries_.append(descr); | |
| 64 | |
| 65 // Check that this new type repr is of the same basic kind as the | |
| 66 // ones we have seen thus far. If not, for example if we have an | |
| 67 // `int` and a `struct`, then convert this set to the invalid set. | |
| 68 TypeDescr *entry0 = entries_[0]; | |
| 69 if (descr->kind() != entry0->kind()) { | |
| 70 invalid_ = true; | |
| 71 entries_.clear(); | |
| 72 return true; | |
| 73 } | |
| 74 | |
| 75 // Otherwise, use binary search to find the right place to insert | |
| 76 // the TypeDescr. We keep the list sorted by the *address* of | |
| 77 // the TypeDescrs within. | |
| 78 uintptr_t descrAddr = (uintptr_t) descr; | |
| 79 size_t min = 0; | |
| 80 size_t max = entries_.length(); | |
| 81 while (min != max) { | |
| 82 size_t i = min + ((max - min) >> 1); // average w/o fear of overflow | |
| 83 | |
| 84 uintptr_t entryiaddr = (uintptr_t) entries_[i]; | |
| 85 if (entryiaddr == descrAddr) | |
| 86 return true; // descr already present in the set | |
| 87 | |
| 88 if (entryiaddr < descrAddr) { | |
| 89 // descr lies to the right of entry i | |
| 90 min = i + 1; | |
| 91 } else { | |
| 92 // descr lies to the left of entry i | |
| 93 max = i; | |
| 94 } | |
| 95 } | |
| 96 | |
| 97 // As a sanity check, give up if the TypeDescrSet grows too large. | |
| 98 if (entries_.length() >= 512) { | |
| 99 invalid_ = true; | |
| 100 entries_.clear(); | |
| 101 return true; | |
| 102 } | |
| 103 | |
| 104 // Not present. Insert at position `min`. | |
| 105 if (min == entries_.length()) | |
| 106 return entries_.append(descr); | |
| 107 TypeDescr **insertLoc = &entries_[min]; | |
| 108 return entries_.insert(insertLoc, descr) != nullptr; | |
| 109 } | |
| 110 | |
| 111 bool | |
| 112 TypeDescrSetBuilder::build(IonBuilder &builder, TypeDescrSet *out) | |
| 113 { | |
| 114 if (invalid_) { | |
| 115 *out = TypeDescrSet(); | |
| 116 return true; | |
| 117 } | |
| 118 | |
| 119 TypeDescrSetHash *table = builder.getOrCreateDescrSetHash(); | |
| 120 if (!table) | |
| 121 return false; | |
| 122 | |
| 123 // Check if there is already a copy in the hashtable. | |
| 124 size_t length = entries_.length(); | |
| 125 TypeDescrSet tempSet(length, entries_.begin()); | |
| 126 TypeDescrSetHash::AddPtr p = table->lookupForAdd(tempSet); | |
| 127 if (p) { | |
| 128 *out = *p; | |
| 129 return true; | |
| 130 } | |
| 131 | |
| 132 // If not, allocate a permanent copy in Ion temp memory and add it. | |
| 133 size_t space = sizeof(TypeDescr*) * length; | |
| 134 TypeDescr **array = (TypeDescr**) | |
| 135 GetIonContext()->temp->allocate(space); | |
| 136 if (!array) | |
| 137 return false; | |
| 138 memcpy(array, entries_.begin(), space); | |
| 139 TypeDescrSet permSet(length, array); | |
| 140 if (!table->add(p, permSet)) | |
| 141 return false; | |
| 142 | |
| 143 *out = permSet; | |
| 144 return true; | |
| 145 } | |
| 146 | |
| 147 /////////////////////////////////////////////////////////////////////////// | |
| 148 // TypeDescrSet | |
| 149 | |
| 150 TypeDescrSet::TypeDescrSet(const TypeDescrSet &c) | |
| 151 : length_(c.length_), | |
| 152 entries_(c.entries_) | |
| 153 {} | |
| 154 | |
| 155 TypeDescrSet::TypeDescrSet(size_t length, | |
| 156 TypeDescr **entries) | |
| 157 : length_(length), | |
| 158 entries_(entries) | |
| 159 {} | |
| 160 | |
| 161 TypeDescrSet::TypeDescrSet() | |
| 162 : length_(0), | |
| 163 entries_(nullptr) | |
| 164 {} | |
| 165 | |
| 166 bool | |
| 167 TypeDescrSet::empty() const | |
| 168 { | |
| 169 return length_ == 0; | |
| 170 } | |
| 171 | |
| 172 bool | |
| 173 TypeDescrSet::allOfArrayKind() | |
| 174 { | |
| 175 if (empty()) | |
| 176 return false; | |
| 177 | |
| 178 switch (kind()) { | |
| 179 case TypeDescr::SizedArray: | |
| 180 case TypeDescr::UnsizedArray: | |
| 181 return true; | |
| 182 | |
| 183 case TypeDescr::X4: | |
| 184 case TypeDescr::Reference: | |
| 185 case TypeDescr::Scalar: | |
| 186 case TypeDescr::Struct: | |
| 187 return false; | |
| 188 } | |
| 189 | |
| 190 MOZ_ASSUME_UNREACHABLE("Invalid kind() in TypeDescrSet"); | |
| 191 } | |
| 192 | |
| 193 bool | |
| 194 TypeDescrSet::allOfKind(TypeDescr::Kind aKind) | |
| 195 { | |
| 196 if (empty()) | |
| 197 return false; | |
| 198 | |
| 199 return kind() == aKind; | |
| 200 } | |
| 201 | |
| 202 bool | |
| 203 TypeDescrSet::allHaveSameSize(int32_t *out) | |
| 204 { | |
| 205 if (empty()) | |
| 206 return false; | |
| 207 | |
| 208 JS_ASSERT(TypeDescr::isSized(kind())); | |
| 209 | |
| 210 int32_t size = get(0)->as<SizedTypeDescr>().size(); | |
| 211 for (size_t i = 1; i < length(); i++) { | |
| 212 if (get(i)->as<SizedTypeDescr>().size() != size) | |
| 213 return false; | |
| 214 } | |
| 215 | |
| 216 *out = size; | |
| 217 return true; | |
| 218 } | |
| 219 | |
| 220 JSObject * | |
| 221 TypeDescrSet::knownPrototype() const | |
| 222 { | |
| 223 JS_ASSERT(!empty()); | |
| 224 if (length() > 1 || !get(0)->is<ComplexTypeDescr>()) | |
| 225 return nullptr; | |
| 226 return &get(0)->as<ComplexTypeDescr>().instancePrototype(); | |
| 227 } | |
| 228 | |
| 229 TypeDescr::Kind | |
| 230 TypeDescrSet::kind() | |
| 231 { | |
| 232 JS_ASSERT(!empty()); | |
| 233 return get(0)->kind(); | |
| 234 } | |
| 235 | |
| 236 template<typename T> | |
| 237 bool | |
| 238 TypeDescrSet::genericType(typename T::Type *out) | |
| 239 { | |
| 240 JS_ASSERT(allOfKind(TypeDescr::Scalar)); | |
| 241 | |
| 242 typename T::Type type = get(0)->as<T>().type(); | |
| 243 for (size_t i = 1; i < length(); i++) { | |
| 244 if (get(i)->as<T>().type() != type) | |
| 245 return false; | |
| 246 } | |
| 247 | |
| 248 *out = type; | |
| 249 return true; | |
| 250 } | |
| 251 | |
| 252 bool | |
| 253 TypeDescrSet::scalarType(ScalarTypeDescr::Type *out) | |
| 254 { | |
| 255 return genericType<ScalarTypeDescr>(out); | |
| 256 } | |
| 257 | |
| 258 bool | |
| 259 TypeDescrSet::referenceType(ReferenceTypeDescr::Type *out) | |
| 260 { | |
| 261 return genericType<ReferenceTypeDescr>(out); | |
| 262 } | |
| 263 | |
| 264 bool | |
| 265 TypeDescrSet::x4Type(X4TypeDescr::Type *out) | |
| 266 { | |
| 267 return genericType<X4TypeDescr>(out); | |
| 268 } | |
| 269 | |
| 270 bool | |
| 271 TypeDescrSet::hasKnownArrayLength(int32_t *l) | |
| 272 { | |
| 273 switch (kind()) { | |
| 274 case TypeDescr::UnsizedArray: | |
| 275 return false; | |
| 276 | |
| 277 case TypeDescr::SizedArray: | |
| 278 { | |
| 279 const size_t result = get(0)->as<SizedArrayTypeDescr>().length(); | |
| 280 for (size_t i = 1; i < length(); i++) { | |
| 281 size_t l = get(i)->as<SizedArrayTypeDescr>().length(); | |
| 282 if (l != result) | |
| 283 return false; | |
| 284 } | |
| 285 *l = result; | |
| 286 return true; | |
| 287 } | |
| 288 | |
| 289 default: | |
| 290 MOZ_ASSUME_UNREACHABLE("Invalid array size for call to arrayLength()"); | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 bool | |
| 295 TypeDescrSet::arrayElementType(IonBuilder &builder, TypeDescrSet *out) | |
| 296 { | |
| 297 TypeDescrSetBuilder elementTypes; | |
| 298 for (size_t i = 0; i < length(); i++) { | |
| 299 switch (kind()) { | |
| 300 case TypeDescr::UnsizedArray: | |
| 301 if (!elementTypes.insert(&get(i)->as<UnsizedArrayTypeDescr>().elementType())) | |
| 302 return false; | |
| 303 break; | |
| 304 | |
| 305 case TypeDescr::SizedArray: | |
| 306 if (!elementTypes.insert(&get(i)->as<SizedArrayTypeDescr>().elementType())) | |
| 307 return false; | |
| 308 break; | |
| 309 | |
| 310 default: | |
| 311 MOZ_ASSUME_UNREACHABLE("Invalid kind for arrayElementType()"); | |
| 312 } | |
| 313 } | |
| 314 return elementTypes.build(builder, out); | |
| 315 } | |
| 316 | |
| 317 bool | |
| 318 TypeDescrSet::fieldNamed(IonBuilder &builder, | |
| 319 jsid id, | |
| 320 int32_t *offset, | |
| 321 TypeDescrSet *out, | |
| 322 size_t *index) | |
| 323 { | |
| 324 JS_ASSERT(kind() == TypeDescr::Struct); | |
| 325 | |
| 326 // Initialize `*offset` and `*out` for the case where incompatible | |
| 327 // or absent fields are found. | |
| 328 *offset = -1; | |
| 329 *index = SIZE_MAX; | |
| 330 *out = TypeDescrSet(); | |
| 331 | |
| 332 // Remember offset of the first field. | |
| 333 int32_t offset0; | |
| 334 size_t index0; | |
| 335 TypeDescrSetBuilder fieldTypes; | |
| 336 { | |
| 337 StructTypeDescr &descr0 = get(0)->as<StructTypeDescr>(); | |
| 338 if (!descr0.fieldIndex(id, &index0)) | |
| 339 return true; | |
| 340 | |
| 341 offset0 = descr0.fieldOffset(index0); | |
| 342 if (!fieldTypes.insert(&descr0.fieldDescr(index0))) | |
| 343 return false; | |
| 344 } | |
| 345 | |
| 346 // Check that all subsequent fields are at the same offset | |
| 347 // and compute the union of their types. | |
| 348 for (size_t i = 1; i < length(); i++) { | |
| 349 StructTypeDescr &descri = get(i)->as<StructTypeDescr>(); | |
| 350 | |
| 351 size_t indexi; | |
| 352 if (!descri.fieldIndex(id, &indexi)) | |
| 353 return true; | |
| 354 | |
| 355 // Track whether all indices agree, but do not require it to be true | |
| 356 if (indexi != index0) | |
| 357 index0 = SIZE_MAX; | |
| 358 | |
| 359 // Require that all offsets agree | |
| 360 if (descri.fieldOffset(indexi) != offset0) | |
| 361 return true; | |
| 362 | |
| 363 if (!fieldTypes.insert(&descri.fieldDescr(indexi))) | |
| 364 return false; | |
| 365 } | |
| 366 | |
| 367 // All struct types had a field named `id` at the same offset | |
| 368 // (though it's still possible that the types are incompatible and | |
| 369 // that the indices disagree). | |
| 370 *offset = offset0; | |
| 371 *index = index0; | |
| 372 return fieldTypes.build(builder, out); | |
| 373 } |
