1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/TypeDescrSet.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,373 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jit/TypeDescrSet.h"
1.11 +
1.12 +#include "mozilla/HashFunctions.h"
1.13 +
1.14 +#include "builtin/TypedObject.h"
1.15 +#include "jit/IonBuilder.h"
1.16 +
1.17 +using namespace js;
1.18 +using namespace jit;
1.19 +
1.20 +///////////////////////////////////////////////////////////////////////////
1.21 +// TypeDescrSet hasher
1.22 +
1.23 +HashNumber
1.24 +TypeDescrSetHasher::hash(TypeDescrSet key)
1.25 +{
1.26 + HashNumber hn = mozilla::HashGeneric(key.length());
1.27 + for (size_t i = 0; i < key.length(); i++)
1.28 + hn = mozilla::AddToHash(hn, uintptr_t(key.get(i)));
1.29 + return hn;
1.30 +}
1.31 +
1.32 +bool
1.33 +TypeDescrSetHasher::match(TypeDescrSet key1, TypeDescrSet key2)
1.34 +{
1.35 + if (key1.length() != key2.length())
1.36 + return false;
1.37 +
1.38 + // Note: entries are always sorted
1.39 + for (size_t i = 0; i < key1.length(); i++) {
1.40 + if (key1.get(i) != key2.get(i))
1.41 + return false;
1.42 + }
1.43 +
1.44 + return true;
1.45 +}
1.46 +
1.47 +///////////////////////////////////////////////////////////////////////////
1.48 +// TypeDescrSetBuilder
1.49 +
1.50 +TypeDescrSetBuilder::TypeDescrSetBuilder()
1.51 + : invalid_(false)
1.52 +{}
1.53 +
1.54 +bool
1.55 +TypeDescrSetBuilder::insert(TypeDescr *descr)
1.56 +{
1.57 + // All type descriptors should be tenured, so it is safe to assume
1.58 + // that the pointers do not change during compilation, since no
1.59 + // major GC can overlap with compilation.
1.60 + JS_ASSERT(!GetIonContext()->runtime->isInsideNursery(descr));
1.61 +
1.62 + if (invalid_)
1.63 + return true;
1.64 +
1.65 + if (entries_.empty())
1.66 + return entries_.append(descr);
1.67 +
1.68 + // Check that this new type repr is of the same basic kind as the
1.69 + // ones we have seen thus far. If not, for example if we have an
1.70 + // `int` and a `struct`, then convert this set to the invalid set.
1.71 + TypeDescr *entry0 = entries_[0];
1.72 + if (descr->kind() != entry0->kind()) {
1.73 + invalid_ = true;
1.74 + entries_.clear();
1.75 + return true;
1.76 + }
1.77 +
1.78 + // Otherwise, use binary search to find the right place to insert
1.79 + // the TypeDescr. We keep the list sorted by the *address* of
1.80 + // the TypeDescrs within.
1.81 + uintptr_t descrAddr = (uintptr_t) descr;
1.82 + size_t min = 0;
1.83 + size_t max = entries_.length();
1.84 + while (min != max) {
1.85 + size_t i = min + ((max - min) >> 1); // average w/o fear of overflow
1.86 +
1.87 + uintptr_t entryiaddr = (uintptr_t) entries_[i];
1.88 + if (entryiaddr == descrAddr)
1.89 + return true; // descr already present in the set
1.90 +
1.91 + if (entryiaddr < descrAddr) {
1.92 + // descr lies to the right of entry i
1.93 + min = i + 1;
1.94 + } else {
1.95 + // descr lies to the left of entry i
1.96 + max = i;
1.97 + }
1.98 + }
1.99 +
1.100 + // As a sanity check, give up if the TypeDescrSet grows too large.
1.101 + if (entries_.length() >= 512) {
1.102 + invalid_ = true;
1.103 + entries_.clear();
1.104 + return true;
1.105 + }
1.106 +
1.107 + // Not present. Insert at position `min`.
1.108 + if (min == entries_.length())
1.109 + return entries_.append(descr);
1.110 + TypeDescr **insertLoc = &entries_[min];
1.111 + return entries_.insert(insertLoc, descr) != nullptr;
1.112 +}
1.113 +
1.114 +bool
1.115 +TypeDescrSetBuilder::build(IonBuilder &builder, TypeDescrSet *out)
1.116 +{
1.117 + if (invalid_) {
1.118 + *out = TypeDescrSet();
1.119 + return true;
1.120 + }
1.121 +
1.122 + TypeDescrSetHash *table = builder.getOrCreateDescrSetHash();
1.123 + if (!table)
1.124 + return false;
1.125 +
1.126 + // Check if there is already a copy in the hashtable.
1.127 + size_t length = entries_.length();
1.128 + TypeDescrSet tempSet(length, entries_.begin());
1.129 + TypeDescrSetHash::AddPtr p = table->lookupForAdd(tempSet);
1.130 + if (p) {
1.131 + *out = *p;
1.132 + return true;
1.133 + }
1.134 +
1.135 + // If not, allocate a permanent copy in Ion temp memory and add it.
1.136 + size_t space = sizeof(TypeDescr*) * length;
1.137 + TypeDescr **array = (TypeDescr**)
1.138 + GetIonContext()->temp->allocate(space);
1.139 + if (!array)
1.140 + return false;
1.141 + memcpy(array, entries_.begin(), space);
1.142 + TypeDescrSet permSet(length, array);
1.143 + if (!table->add(p, permSet))
1.144 + return false;
1.145 +
1.146 + *out = permSet;
1.147 + return true;
1.148 +}
1.149 +
1.150 +///////////////////////////////////////////////////////////////////////////
1.151 +// TypeDescrSet
1.152 +
1.153 +TypeDescrSet::TypeDescrSet(const TypeDescrSet &c)
1.154 + : length_(c.length_),
1.155 + entries_(c.entries_)
1.156 +{}
1.157 +
1.158 +TypeDescrSet::TypeDescrSet(size_t length,
1.159 + TypeDescr **entries)
1.160 + : length_(length),
1.161 + entries_(entries)
1.162 +{}
1.163 +
1.164 +TypeDescrSet::TypeDescrSet()
1.165 + : length_(0),
1.166 + entries_(nullptr)
1.167 +{}
1.168 +
1.169 +bool
1.170 +TypeDescrSet::empty() const
1.171 +{
1.172 + return length_ == 0;
1.173 +}
1.174 +
1.175 +bool
1.176 +TypeDescrSet::allOfArrayKind()
1.177 +{
1.178 + if (empty())
1.179 + return false;
1.180 +
1.181 + switch (kind()) {
1.182 + case TypeDescr::SizedArray:
1.183 + case TypeDescr::UnsizedArray:
1.184 + return true;
1.185 +
1.186 + case TypeDescr::X4:
1.187 + case TypeDescr::Reference:
1.188 + case TypeDescr::Scalar:
1.189 + case TypeDescr::Struct:
1.190 + return false;
1.191 + }
1.192 +
1.193 + MOZ_ASSUME_UNREACHABLE("Invalid kind() in TypeDescrSet");
1.194 +}
1.195 +
1.196 +bool
1.197 +TypeDescrSet::allOfKind(TypeDescr::Kind aKind)
1.198 +{
1.199 + if (empty())
1.200 + return false;
1.201 +
1.202 + return kind() == aKind;
1.203 +}
1.204 +
1.205 +bool
1.206 +TypeDescrSet::allHaveSameSize(int32_t *out)
1.207 +{
1.208 + if (empty())
1.209 + return false;
1.210 +
1.211 + JS_ASSERT(TypeDescr::isSized(kind()));
1.212 +
1.213 + int32_t size = get(0)->as<SizedTypeDescr>().size();
1.214 + for (size_t i = 1; i < length(); i++) {
1.215 + if (get(i)->as<SizedTypeDescr>().size() != size)
1.216 + return false;
1.217 + }
1.218 +
1.219 + *out = size;
1.220 + return true;
1.221 +}
1.222 +
1.223 +JSObject *
1.224 +TypeDescrSet::knownPrototype() const
1.225 +{
1.226 + JS_ASSERT(!empty());
1.227 + if (length() > 1 || !get(0)->is<ComplexTypeDescr>())
1.228 + return nullptr;
1.229 + return &get(0)->as<ComplexTypeDescr>().instancePrototype();
1.230 +}
1.231 +
1.232 +TypeDescr::Kind
1.233 +TypeDescrSet::kind()
1.234 +{
1.235 + JS_ASSERT(!empty());
1.236 + return get(0)->kind();
1.237 +}
1.238 +
1.239 +template<typename T>
1.240 +bool
1.241 +TypeDescrSet::genericType(typename T::Type *out)
1.242 +{
1.243 + JS_ASSERT(allOfKind(TypeDescr::Scalar));
1.244 +
1.245 + typename T::Type type = get(0)->as<T>().type();
1.246 + for (size_t i = 1; i < length(); i++) {
1.247 + if (get(i)->as<T>().type() != type)
1.248 + return false;
1.249 + }
1.250 +
1.251 + *out = type;
1.252 + return true;
1.253 +}
1.254 +
1.255 +bool
1.256 +TypeDescrSet::scalarType(ScalarTypeDescr::Type *out)
1.257 +{
1.258 + return genericType<ScalarTypeDescr>(out);
1.259 +}
1.260 +
1.261 +bool
1.262 +TypeDescrSet::referenceType(ReferenceTypeDescr::Type *out)
1.263 +{
1.264 + return genericType<ReferenceTypeDescr>(out);
1.265 +}
1.266 +
1.267 +bool
1.268 +TypeDescrSet::x4Type(X4TypeDescr::Type *out)
1.269 +{
1.270 + return genericType<X4TypeDescr>(out);
1.271 +}
1.272 +
1.273 +bool
1.274 +TypeDescrSet::hasKnownArrayLength(int32_t *l)
1.275 +{
1.276 + switch (kind()) {
1.277 + case TypeDescr::UnsizedArray:
1.278 + return false;
1.279 +
1.280 + case TypeDescr::SizedArray:
1.281 + {
1.282 + const size_t result = get(0)->as<SizedArrayTypeDescr>().length();
1.283 + for (size_t i = 1; i < length(); i++) {
1.284 + size_t l = get(i)->as<SizedArrayTypeDescr>().length();
1.285 + if (l != result)
1.286 + return false;
1.287 + }
1.288 + *l = result;
1.289 + return true;
1.290 + }
1.291 +
1.292 + default:
1.293 + MOZ_ASSUME_UNREACHABLE("Invalid array size for call to arrayLength()");
1.294 + }
1.295 +}
1.296 +
1.297 +bool
1.298 +TypeDescrSet::arrayElementType(IonBuilder &builder, TypeDescrSet *out)
1.299 +{
1.300 + TypeDescrSetBuilder elementTypes;
1.301 + for (size_t i = 0; i < length(); i++) {
1.302 + switch (kind()) {
1.303 + case TypeDescr::UnsizedArray:
1.304 + if (!elementTypes.insert(&get(i)->as<UnsizedArrayTypeDescr>().elementType()))
1.305 + return false;
1.306 + break;
1.307 +
1.308 + case TypeDescr::SizedArray:
1.309 + if (!elementTypes.insert(&get(i)->as<SizedArrayTypeDescr>().elementType()))
1.310 + return false;
1.311 + break;
1.312 +
1.313 + default:
1.314 + MOZ_ASSUME_UNREACHABLE("Invalid kind for arrayElementType()");
1.315 + }
1.316 + }
1.317 + return elementTypes.build(builder, out);
1.318 +}
1.319 +
1.320 +bool
1.321 +TypeDescrSet::fieldNamed(IonBuilder &builder,
1.322 + jsid id,
1.323 + int32_t *offset,
1.324 + TypeDescrSet *out,
1.325 + size_t *index)
1.326 +{
1.327 + JS_ASSERT(kind() == TypeDescr::Struct);
1.328 +
1.329 + // Initialize `*offset` and `*out` for the case where incompatible
1.330 + // or absent fields are found.
1.331 + *offset = -1;
1.332 + *index = SIZE_MAX;
1.333 + *out = TypeDescrSet();
1.334 +
1.335 + // Remember offset of the first field.
1.336 + int32_t offset0;
1.337 + size_t index0;
1.338 + TypeDescrSetBuilder fieldTypes;
1.339 + {
1.340 + StructTypeDescr &descr0 = get(0)->as<StructTypeDescr>();
1.341 + if (!descr0.fieldIndex(id, &index0))
1.342 + return true;
1.343 +
1.344 + offset0 = descr0.fieldOffset(index0);
1.345 + if (!fieldTypes.insert(&descr0.fieldDescr(index0)))
1.346 + return false;
1.347 + }
1.348 +
1.349 + // Check that all subsequent fields are at the same offset
1.350 + // and compute the union of their types.
1.351 + for (size_t i = 1; i < length(); i++) {
1.352 + StructTypeDescr &descri = get(i)->as<StructTypeDescr>();
1.353 +
1.354 + size_t indexi;
1.355 + if (!descri.fieldIndex(id, &indexi))
1.356 + return true;
1.357 +
1.358 + // Track whether all indices agree, but do not require it to be true
1.359 + if (indexi != index0)
1.360 + index0 = SIZE_MAX;
1.361 +
1.362 + // Require that all offsets agree
1.363 + if (descri.fieldOffset(indexi) != offset0)
1.364 + return true;
1.365 +
1.366 + if (!fieldTypes.insert(&descri.fieldDescr(indexi)))
1.367 + return false;
1.368 + }
1.369 +
1.370 + // All struct types had a field named `id` at the same offset
1.371 + // (though it's still possible that the types are incompatible and
1.372 + // that the indices disagree).
1.373 + *offset = offset0;
1.374 + *index = index0;
1.375 + return fieldTypes.build(builder, out);
1.376 +}
