michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "jit/TypeDescrSet.h"
michael@0: 
michael@0: #include "mozilla/HashFunctions.h"
michael@0: 
michael@0: #include "builtin/TypedObject.h"
michael@0: #include "jit/IonBuilder.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace jit;
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // TypeDescrSet hasher
michael@0: 
michael@0: HashNumber
michael@0: TypeDescrSetHasher::hash(TypeDescrSet key)
michael@0: {
michael@0:     HashNumber hn = mozilla::HashGeneric(key.length());
michael@0:     for (size_t i = 0; i < key.length(); i++)
michael@0:         hn = mozilla::AddToHash(hn, uintptr_t(key.get(i)));
michael@0:     return hn;
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSetHasher::match(TypeDescrSet key1, TypeDescrSet key2)
michael@0: {
michael@0:     if (key1.length() != key2.length())
michael@0:         return false;
michael@0: 
michael@0:     // Note: entries are always sorted
michael@0:     for (size_t i = 0; i < key1.length(); i++) {
michael@0:         if (key1.get(i) != key2.get(i))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // TypeDescrSetBuilder
michael@0: 
michael@0: TypeDescrSetBuilder::TypeDescrSetBuilder()
michael@0:   : invalid_(false)
michael@0: {}
michael@0: 
michael@0: bool
michael@0: TypeDescrSetBuilder::insert(TypeDescr *descr)
michael@0: {
michael@0:     // All type descriptors should be tenured, so it is safe to assume
michael@0:     // that the pointers do not change during compilation, since no
michael@0:     // major GC can overlap with compilation.
michael@0:     JS_ASSERT(!GetIonContext()->runtime->isInsideNursery(descr));
michael@0: 
michael@0:     if (invalid_)
michael@0:         return true;
michael@0: 
michael@0:     if (entries_.empty())
michael@0:         return entries_.append(descr);
michael@0: 
michael@0:     // Check that this new type repr is of the same basic kind as the
michael@0:     // ones we have seen thus far. If not, for example if we have an
michael@0:     // `int` and a `struct`, then convert this set to the invalid set.
michael@0:     TypeDescr *entry0 = entries_[0];
michael@0:     if (descr->kind() != entry0->kind()) {
michael@0:         invalid_ = true;
michael@0:         entries_.clear();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Otherwise, use binary search to find the right place to insert
michael@0:     // the TypeDescr. We keep the list sorted by the *address* of
michael@0:     // the TypeDescrs within.
michael@0:     uintptr_t descrAddr = (uintptr_t) descr;
michael@0:     size_t min = 0;
michael@0:     size_t max = entries_.length();
michael@0:     while (min != max) {
michael@0:         size_t i = min + ((max - min) >> 1); // average w/o fear of overflow
michael@0: 
michael@0:         uintptr_t entryiaddr = (uintptr_t) entries_[i];
michael@0:         if (entryiaddr == descrAddr)
michael@0:             return true; // descr already present in the set
michael@0: 
michael@0:         if (entryiaddr < descrAddr) {
michael@0:             // descr lies to the right of entry i
michael@0:             min = i + 1;
michael@0:         } else {
michael@0:             // descr lies to the left of entry i
michael@0:             max = i;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // As a sanity check, give up if the TypeDescrSet grows too large.
michael@0:     if (entries_.length() >= 512) {
michael@0:         invalid_ = true;
michael@0:         entries_.clear();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // Not present. Insert at position `min`.
michael@0:     if (min == entries_.length())
michael@0:         return entries_.append(descr);
michael@0:     TypeDescr **insertLoc = &entries_[min];
michael@0:     return entries_.insert(insertLoc, descr) != nullptr;
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSetBuilder::build(IonBuilder &builder, TypeDescrSet *out)
michael@0: {
michael@0:     if (invalid_) {
michael@0:         *out = TypeDescrSet();
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     TypeDescrSetHash *table = builder.getOrCreateDescrSetHash();
michael@0:     if (!table)
michael@0:         return false;
michael@0: 
michael@0:     // Check if there is already a copy in the hashtable.
michael@0:     size_t length = entries_.length();
michael@0:     TypeDescrSet tempSet(length, entries_.begin());
michael@0:     TypeDescrSetHash::AddPtr p = table->lookupForAdd(tempSet);
michael@0:     if (p) {
michael@0:         *out = *p;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // If not, allocate a permanent copy in Ion temp memory and add it.
michael@0:     size_t space = sizeof(TypeDescr*) * length;
michael@0:     TypeDescr **array = (TypeDescr**)
michael@0:         GetIonContext()->temp->allocate(space);
michael@0:     if (!array)
michael@0:         return false;
michael@0:     memcpy(array, entries_.begin(), space);
michael@0:     TypeDescrSet permSet(length, array);
michael@0:     if (!table->add(p, permSet))
michael@0:         return false;
michael@0: 
michael@0:     *out = permSet;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////
michael@0: // TypeDescrSet
michael@0: 
michael@0: TypeDescrSet::TypeDescrSet(const TypeDescrSet &c)
michael@0:   : length_(c.length_),
michael@0:     entries_(c.entries_)
michael@0: {}
michael@0: 
michael@0: TypeDescrSet::TypeDescrSet(size_t length,
michael@0:                            TypeDescr **entries)
michael@0:   : length_(length),
michael@0:     entries_(entries)
michael@0: {}
michael@0: 
michael@0: TypeDescrSet::TypeDescrSet()
michael@0:   : length_(0),
michael@0:     entries_(nullptr)
michael@0: {}
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::empty() const
michael@0: {
michael@0:     return length_ == 0;
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::allOfArrayKind()
michael@0: {
michael@0:     if (empty())
michael@0:         return false;
michael@0: 
michael@0:     switch (kind()) {
michael@0:       case TypeDescr::SizedArray:
michael@0:       case TypeDescr::UnsizedArray:
michael@0:         return true;
michael@0: 
michael@0:       case TypeDescr::X4:
michael@0:       case TypeDescr::Reference:
michael@0:       case TypeDescr::Scalar:
michael@0:       case TypeDescr::Struct:
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     MOZ_ASSUME_UNREACHABLE("Invalid kind() in TypeDescrSet");
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::allOfKind(TypeDescr::Kind aKind)
michael@0: {
michael@0:     if (empty())
michael@0:         return false;
michael@0: 
michael@0:     return kind() == aKind;
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::allHaveSameSize(int32_t *out)
michael@0: {
michael@0:     if (empty())
michael@0:         return false;
michael@0: 
michael@0:     JS_ASSERT(TypeDescr::isSized(kind()));
michael@0: 
michael@0:     int32_t size = get(0)->as<SizedTypeDescr>().size();
michael@0:     for (size_t i = 1; i < length(); i++) {
michael@0:         if (get(i)->as<SizedTypeDescr>().size() != size)
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     *out = size;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: JSObject *
michael@0: TypeDescrSet::knownPrototype() const
michael@0: {
michael@0:     JS_ASSERT(!empty());
michael@0:     if (length() > 1 || !get(0)->is<ComplexTypeDescr>())
michael@0:         return nullptr;
michael@0:     return &get(0)->as<ComplexTypeDescr>().instancePrototype();
michael@0: }
michael@0: 
michael@0: TypeDescr::Kind
michael@0: TypeDescrSet::kind()
michael@0: {
michael@0:     JS_ASSERT(!empty());
michael@0:     return get(0)->kind();
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: bool
michael@0: TypeDescrSet::genericType(typename T::Type *out)
michael@0: {
michael@0:     JS_ASSERT(allOfKind(TypeDescr::Scalar));
michael@0: 
michael@0:     typename T::Type type = get(0)->as<T>().type();
michael@0:     for (size_t i = 1; i < length(); i++) {
michael@0:         if (get(i)->as<T>().type() != type)
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     *out = type;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::scalarType(ScalarTypeDescr::Type *out)
michael@0: {
michael@0:     return genericType<ScalarTypeDescr>(out);
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::referenceType(ReferenceTypeDescr::Type *out)
michael@0: {
michael@0:     return genericType<ReferenceTypeDescr>(out);
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::x4Type(X4TypeDescr::Type *out)
michael@0: {
michael@0:     return genericType<X4TypeDescr>(out);
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::hasKnownArrayLength(int32_t *l)
michael@0: {
michael@0:     switch (kind()) {
michael@0:       case TypeDescr::UnsizedArray:
michael@0:         return false;
michael@0: 
michael@0:       case TypeDescr::SizedArray:
michael@0:       {
michael@0:         const size_t result = get(0)->as<SizedArrayTypeDescr>().length();
michael@0:         for (size_t i = 1; i < length(); i++) {
michael@0:             size_t l = get(i)->as<SizedArrayTypeDescr>().length();
michael@0:             if (l != result)
michael@0:                 return false;
michael@0:         }
michael@0:         *l = result;
michael@0:         return true;
michael@0:       }
michael@0: 
michael@0:       default:
michael@0:         MOZ_ASSUME_UNREACHABLE("Invalid array size for call to arrayLength()");
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::arrayElementType(IonBuilder &builder, TypeDescrSet *out)
michael@0: {
michael@0:     TypeDescrSetBuilder elementTypes;
michael@0:     for (size_t i = 0; i < length(); i++) {
michael@0:         switch (kind()) {
michael@0:           case TypeDescr::UnsizedArray:
michael@0:             if (!elementTypes.insert(&get(i)->as<UnsizedArrayTypeDescr>().elementType()))
michael@0:                 return false;
michael@0:             break;
michael@0: 
michael@0:           case TypeDescr::SizedArray:
michael@0:             if (!elementTypes.insert(&get(i)->as<SizedArrayTypeDescr>().elementType()))
michael@0:                 return false;
michael@0:             break;
michael@0: 
michael@0:           default:
michael@0:             MOZ_ASSUME_UNREACHABLE("Invalid kind for arrayElementType()");
michael@0:         }
michael@0:     }
michael@0:     return elementTypes.build(builder, out);
michael@0: }
michael@0: 
michael@0: bool
michael@0: TypeDescrSet::fieldNamed(IonBuilder &builder,
michael@0:                          jsid id,
michael@0:                          int32_t *offset,
michael@0:                          TypeDescrSet *out,
michael@0:                          size_t *index)
michael@0: {
michael@0:     JS_ASSERT(kind() == TypeDescr::Struct);
michael@0: 
michael@0:     // Initialize `*offset` and `*out` for the case where incompatible
michael@0:     // or absent fields are found.
michael@0:     *offset = -1;
michael@0:     *index = SIZE_MAX;
michael@0:     *out = TypeDescrSet();
michael@0: 
michael@0:     // Remember offset of the first field.
michael@0:     int32_t offset0;
michael@0:     size_t index0;
michael@0:     TypeDescrSetBuilder fieldTypes;
michael@0:     {
michael@0:         StructTypeDescr &descr0 = get(0)->as<StructTypeDescr>();
michael@0:         if (!descr0.fieldIndex(id, &index0))
michael@0:             return true;
michael@0: 
michael@0:         offset0 = descr0.fieldOffset(index0);
michael@0:         if (!fieldTypes.insert(&descr0.fieldDescr(index0)))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // Check that all subsequent fields are at the same offset
michael@0:     // and compute the union of their types.
michael@0:     for (size_t i = 1; i < length(); i++) {
michael@0:         StructTypeDescr &descri = get(i)->as<StructTypeDescr>();
michael@0: 
michael@0:         size_t indexi;
michael@0:         if (!descri.fieldIndex(id, &indexi))
michael@0:             return true;
michael@0: 
michael@0:         // Track whether all indices agree, but do not require it to be true
michael@0:         if (indexi != index0)
michael@0:             index0 = SIZE_MAX;
michael@0: 
michael@0:         // Require that all offsets agree
michael@0:         if (descri.fieldOffset(indexi) != offset0)
michael@0:             return true;
michael@0: 
michael@0:         if (!fieldTypes.insert(&descri.fieldDescr(indexi)))
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     // All struct types had a field named `id` at the same offset
michael@0:     // (though it's still possible that the types are incompatible and
michael@0:     // that the indices disagree).
michael@0:     *offset = offset0;
michael@0:     *index = index0;
michael@0:     return fieldTypes.build(builder, out);
michael@0: }