The Tor Browser: js/src/jit/TypeDescrSet.cpp@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/. */

     7 #include "jit/TypeDescrSet.h"

     9 #include "mozilla/HashFunctions.h"

    11 #include "builtin/TypedObject.h"

    12 #include "jit/IonBuilder.h"

    14 using namespace js;

    15 using namespace jit;

    17 ///////////////////////////////////////////////////////////////////////////

    18 // TypeDescrSet hasher

    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 }

    29 bool

    30 TypeDescrSetHasher::match(TypeDescrSet key1, TypeDescrSet key2)

    31 {

    32     if (key1.length() != key2.length())

    33         return false;

    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     }

    41     return true;

    42 }

    44 ///////////////////////////////////////////////////////////////////////////

    45 // TypeDescrSetBuilder

    47 TypeDescrSetBuilder::TypeDescrSetBuilder()

    48   : invalid_(false)

    49 {}

    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));

    59     if (invalid_)

    60         return true;

    62     if (entries_.empty())

    63         return entries_.append(descr);

    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     }

    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

    84         uintptr_t entryiaddr = (uintptr_t) entries_[i];

    85         if (entryiaddr == descrAddr)

    86             return true; // descr already present in the set

    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     }

    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     }

   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 }

   111 bool

   112 TypeDescrSetBuilder::build(IonBuilder &builder, TypeDescrSet *out)

   113 {

   114     if (invalid_) {

   115         *out = TypeDescrSet();

   116         return true;

   117     }

   119     TypeDescrSetHash *table = builder.getOrCreateDescrSetHash();

   120     if (!table)

   121         return false;

   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     }

   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;

   143     *out = permSet;

   144     return true;

   145 }

   147 ///////////////////////////////////////////////////////////////////////////

   148 // TypeDescrSet

   150 TypeDescrSet::TypeDescrSet(const TypeDescrSet &c)

   151   : length_(c.length_),

   152     entries_(c.entries_)

   153 {}

   155 TypeDescrSet::TypeDescrSet(size_t length,

   156                            TypeDescr **entries)

   157   : length_(length),

   158     entries_(entries)

   159 {}

   161 TypeDescrSet::TypeDescrSet()

   162   : length_(0),

   163     entries_(nullptr)

   164 {}

   166 bool

   167 TypeDescrSet::empty() const

   168 {

   169     return length_ == 0;

   170 }

   172 bool

   173 TypeDescrSet::allOfArrayKind()

   174 {

   175     if (empty())

   176         return false;

   178     switch (kind()) {

   179       case TypeDescr::SizedArray:

   180       case TypeDescr::UnsizedArray:

   181         return true;

   183       case TypeDescr::X4:

   184       case TypeDescr::Reference:

   185       case TypeDescr::Scalar:

   186       case TypeDescr::Struct:

   187         return false;

   188     }

   190     MOZ_ASSUME_UNREACHABLE("Invalid kind() in TypeDescrSet");

   191 }

   193 bool

   194 TypeDescrSet::allOfKind(TypeDescr::Kind aKind)

   195 {

   196     if (empty())

   197         return false;

   199     return kind() == aKind;

   200 }

   202 bool

   203 TypeDescrSet::allHaveSameSize(int32_t *out)

   204 {

   205     if (empty())

   206         return false;

   208     JS_ASSERT(TypeDescr::isSized(kind()));

   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     }

   216     *out = size;

   217     return true;

   218 }

   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 }

   229 TypeDescr::Kind

   230 TypeDescrSet::kind()

   231 {

   232     JS_ASSERT(!empty());

   233     return get(0)->kind();

   234 }

   236 template<typename T>

   237 bool

   238 TypeDescrSet::genericType(typename T::Type *out)

   239 {

   240     JS_ASSERT(allOfKind(TypeDescr::Scalar));

   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     }

   248     *out = type;

   249     return true;

   250 }

   252 bool

   253 TypeDescrSet::scalarType(ScalarTypeDescr::Type *out)

   254 {

   255     return genericType<ScalarTypeDescr>(out);

   256 }

   258 bool

   259 TypeDescrSet::referenceType(ReferenceTypeDescr::Type *out)

   260 {

   261     return genericType<ReferenceTypeDescr>(out);

   262 }

   264 bool

   265 TypeDescrSet::x4Type(X4TypeDescr::Type *out)

   266 {

   267     return genericType<X4TypeDescr>(out);

   268 }

   270 bool

   271 TypeDescrSet::hasKnownArrayLength(int32_t *l)

   272 {

   273     switch (kind()) {

   274       case TypeDescr::UnsizedArray:

   275         return false;

   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       }

   289       default:

   290         MOZ_ASSUME_UNREACHABLE("Invalid array size for call to arrayLength()");

   291     }

   292 }

   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;

   305           case TypeDescr::SizedArray:

   306             if (!elementTypes.insert(&get(i)->as<SizedArrayTypeDescr>().elementType()))

   307                 return false;

   308             break;

   310           default:

   311             MOZ_ASSUME_UNREACHABLE("Invalid kind for arrayElementType()");

   312         }

   313     }

   314     return elementTypes.build(builder, out);

   315 }

   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);

   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();

   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;

   341         offset0 = descr0.fieldOffset(index0);

   342         if (!fieldTypes.insert(&descr0.fieldDescr(index0)))

   343             return false;

   344     }

   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>();

   351         size_t indexi;

   352         if (!descri.fieldIndex(id, &indexi))

   353             return true;

   355         // Track whether all indices agree, but do not require it to be true

   356         if (indexi != index0)

   357             index0 = SIZE_MAX;

   359         // Require that all offsets agree

   360         if (descri.fieldOffset(indexi) != offset0)

   361             return true;

   363         if (!fieldTypes.insert(&descri.fieldDescr(indexi)))

   364             return false;

   365     }

   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 }

The Tor Browser / file revision

js/src/jit/TypeDescrSet.cpp@6474c204b198

js/src/jit/TypeDescrSet.cpp