2015-06-08 19:41:47 +00:00
|
|
|
/*
|
2019-09-18 00:36:19 +00:00
|
|
|
* Copyright (C) 2015-2019 Apple Inc. All rights reserved.
|
2015-06-08 19:41:47 +00:00
|
|
|
*
|
|
|
|
* Redistribution and use in source and binary forms, with or without
|
|
|
|
* modification, are permitted provided that the following conditions
|
|
|
|
* are met:
|
|
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer.
|
|
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
|
|
* documentation and/or other materials provided with the distribution.
|
|
|
|
*
|
|
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
|
|
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
|
|
|
|
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
|
|
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
|
|
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
|
|
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
|
|
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
|
|
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
|
|
*/
|
|
|
|
|
2018-10-15 14:24:49 +00:00
|
|
|
#pragma once
|
2015-06-08 19:41:47 +00:00
|
|
|
|
|
|
|
#include <wtf/Assertions.h>
|
|
|
|
#include <wtf/FastMalloc.h>
|
|
|
|
|
|
|
|
namespace JSC { namespace DFG {
|
|
|
|
class StructureAbstractValue;
|
|
|
|
} } // namespace JSC::DFG
|
|
|
|
|
|
|
|
namespace WTF {
|
|
|
|
|
|
|
|
// FIXME: This currently only works for types that are pointer-like: they should have the size
|
|
|
|
// of a pointer and like a pointer they should not have assignment operators, copy constructors,
|
|
|
|
// non-trivial default constructors, and non-trivial destructors. It may be possible to lift all
|
|
|
|
// of these restrictions. If we succeeded then this should be renamed to just TinySet.
|
|
|
|
// https://bugs.webkit.org/show_bug.cgi?id=145741
|
|
|
|
|
|
|
|
template<typename T>
|
|
|
|
class TinyPtrSet {
|
2019-08-12 20:57:15 +00:00
|
|
|
WTF_MAKE_FAST_ALLOCATED;
|
2017-01-26 23:50:58 +00:00
|
|
|
static_assert(sizeof(T) == sizeof(void*), "It's in the title of the class.");
|
2015-06-08 19:41:47 +00:00
|
|
|
public:
|
|
|
|
TinyPtrSet()
|
|
|
|
: m_pointer(0)
|
|
|
|
{
|
|
|
|
setEmpty();
|
|
|
|
}
|
|
|
|
|
|
|
|
TinyPtrSet(T element)
|
|
|
|
: m_pointer(0)
|
|
|
|
{
|
|
|
|
set(element);
|
|
|
|
}
|
|
|
|
|
|
|
|
ALWAYS_INLINE TinyPtrSet(const TinyPtrSet& other)
|
|
|
|
: m_pointer(0)
|
|
|
|
{
|
|
|
|
copyFrom(other);
|
|
|
|
}
|
|
|
|
|
|
|
|
ALWAYS_INLINE TinyPtrSet& operator=(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
if (this == &other)
|
|
|
|
return *this;
|
|
|
|
deleteListIfNecessary();
|
|
|
|
copyFrom(other);
|
|
|
|
return *this;
|
|
|
|
}
|
|
|
|
|
|
|
|
~TinyPtrSet()
|
|
|
|
{
|
|
|
|
deleteListIfNecessary();
|
|
|
|
}
|
|
|
|
|
|
|
|
void clear()
|
|
|
|
{
|
|
|
|
deleteListIfNecessary();
|
|
|
|
setEmpty();
|
|
|
|
}
|
|
|
|
|
|
|
|
// Returns the only entry if the array has exactly one entry.
|
|
|
|
T onlyEntry() const
|
|
|
|
{
|
|
|
|
if (isThin())
|
|
|
|
return singleEntry();
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
if (list->m_length != 1)
|
|
|
|
return T();
|
|
|
|
return list->list()[0];
|
|
|
|
}
|
|
|
|
|
|
|
|
bool isEmpty() const
|
|
|
|
{
|
|
|
|
bool result = isThin() && !singleEntry();
|
|
|
|
if (result)
|
2015-06-08 19:47:57 +00:00
|
|
|
ASSERT(m_pointer != reservedValue);
|
2015-06-08 19:41:47 +00:00
|
|
|
return result;
|
|
|
|
}
|
|
|
|
|
PolymorphicAccess should buffer AccessCases before regenerating
https://bugs.webkit.org/show_bug.cgi?id=156457
Reviewed by Benjamin Poulain.
Source/JavaScriptCore:
Prior to this change, whenever we added an AccessCase to a PolymorphicAccess, we would
regenerate the whole stub. That meant that we'd do O(N^2) work for N access cases.
One way to fix this is to have each AccessCase generate a stub just for itself, which
cascades down to the already-generated cases. But that removes the binary switch
optimization, which makes the IC perform great even when there are many cases.
This change fixes the issue by buffering access cases. When we take slow path and try to add
a new case, the StructureStubInfo will usually just buffer the new case without generating
new code. We simply guarantee that after we buffer a case, we will take at most
Options::repatchBufferingCountdown() slow path calls before generating code for it. That
option is currently 7. Taking 7 more slow paths means that we have 7 more opportunities to
gather more access cases, or to realize that this IC is too crazy to bother with.
This change ensures that the DFG still gets the same kind of profiling. This is because the
buffered AccessCases are still part of PolymorphicAccess and so are still scanned by
GetByIdStatus and PutByIdStatus. The fact that the AccessCases hadn't been generated and so
hadn't executed doesn't change much. Mainly, it increases the likelihood that the DFG will
see an access case that !couldStillSucceed(). The DFG's existing profile parsing logic can
handle this just fine.
There are a bunch of algorithmic changes here. StructureStubInfo now caches the set of
structures that it has seen as a guard to prevent adding lots of redundant cases, in case
we see the same 7 cases after buffering the first one. This cache means we won't wastefully
allocate 7 identical AccessCase instances. PolymorphicAccess is now restructured around
having separate addCase() and regenerate() calls. That means a bit more moving data around.
So far that seems OK for performance, probably since it's O(N) work rather than O(N^2) work.
There is room for improvement for future patches, to be sure.
This is benchmarking as slightly positive or neutral on JS benchmarks. It's meant to reduce
pathologies I saw in page loads.
* bytecode/GetByIdStatus.cpp:
(JSC::GetByIdStatus::computeForStubInfoWithoutExitSiteFeedback):
* bytecode/PolymorphicAccess.cpp:
(JSC::PolymorphicAccess::PolymorphicAccess):
(JSC::PolymorphicAccess::~PolymorphicAccess):
(JSC::PolymorphicAccess::addCases):
(JSC::PolymorphicAccess::addCase):
(JSC::PolymorphicAccess::visitWeak):
(JSC::PolymorphicAccess::dump):
(JSC::PolymorphicAccess::commit):
(JSC::PolymorphicAccess::regenerate):
(JSC::PolymorphicAccess::aboutToDie):
(WTF::printInternal):
(JSC::PolymorphicAccess::regenerateWithCases): Deleted.
(JSC::PolymorphicAccess::regenerateWithCase): Deleted.
* bytecode/PolymorphicAccess.h:
(JSC::AccessCase::isGetter):
(JSC::AccessCase::callLinkInfo):
(JSC::AccessGenerationResult::AccessGenerationResult):
(JSC::AccessGenerationResult::madeNoChanges):
(JSC::AccessGenerationResult::gaveUp):
(JSC::AccessGenerationResult::buffered):
(JSC::AccessGenerationResult::generatedNewCode):
(JSC::AccessGenerationResult::generatedFinalCode):
(JSC::AccessGenerationResult::shouldGiveUpNow):
(JSC::AccessGenerationResult::generatedSomeCode):
(JSC::PolymorphicAccess::isEmpty):
(JSC::PolymorphicAccess::size):
(JSC::PolymorphicAccess::at):
* bytecode/PutByIdStatus.cpp:
(JSC::PutByIdStatus::computeForStubInfo):
* bytecode/StructureStubInfo.cpp:
(JSC::StructureStubInfo::StructureStubInfo):
(JSC::StructureStubInfo::addAccessCase):
(JSC::StructureStubInfo::reset):
(JSC::StructureStubInfo::visitWeakReferences):
* bytecode/StructureStubInfo.h:
(JSC::StructureStubInfo::considerCaching):
(JSC::StructureStubInfo::willRepatch): Deleted.
(JSC::StructureStubInfo::willCoolDown): Deleted.
* jit/JITOperations.cpp:
* jit/Repatch.cpp:
(JSC::tryCacheGetByID):
(JSC::repatchGetByID):
(JSC::tryCachePutByID):
(JSC::repatchPutByID):
(JSC::tryRepatchIn):
(JSC::repatchIn):
* runtime/JSCJSValue.h:
* runtime/JSCJSValueInlines.h:
(JSC::JSValue::putByIndex):
(JSC::JSValue::structureOrNull):
(JSC::JSValue::structureOrUndefined):
* runtime/Options.h:
Source/WTF:
* wtf/TinyPtrSet.h:
(WTF::TinyPtrSet::add): Add a helpful comment because I had forgotten what the bool return meant.
Canonical link: https://commits.webkit.org/174616@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@199382 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2016-04-12 20:06:26 +00:00
|
|
|
// Returns true if the value was added, or false if the value was already there.
|
2018-05-08 21:49:09 +00:00
|
|
|
ALWAYS_INLINE bool add(T value)
|
2015-06-08 19:41:47 +00:00
|
|
|
{
|
|
|
|
ASSERT(value);
|
|
|
|
if (isThin()) {
|
|
|
|
if (singleEntry() == value)
|
|
|
|
return false;
|
|
|
|
if (!singleEntry()) {
|
|
|
|
set(value);
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
|
|
|
|
list->m_length = 2;
|
|
|
|
list->list()[0] = singleEntry();
|
|
|
|
list->list()[1] = value;
|
|
|
|
set(list);
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
|
|
|
|
return addOutOfLine(value);
|
|
|
|
}
|
|
|
|
|
|
|
|
bool remove(T value)
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
if (singleEntry() == value) {
|
|
|
|
setEmpty();
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (list->list()[i] != value)
|
|
|
|
continue;
|
|
|
|
list->list()[i] = list->list()[--list->m_length];
|
|
|
|
if (!list->m_length) {
|
|
|
|
OutOfLineList::destroy(list);
|
|
|
|
setEmpty();
|
|
|
|
}
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
bool contains(T value) const
|
|
|
|
{
|
|
|
|
if (isThin())
|
|
|
|
return singleEntry() == value;
|
|
|
|
return containsOutOfLine(value);
|
|
|
|
}
|
|
|
|
|
2018-05-08 21:49:09 +00:00
|
|
|
ALWAYS_INLINE bool merge(const TinyPtrSet& other)
|
2015-06-08 19:41:47 +00:00
|
|
|
{
|
|
|
|
if (other.isThin()) {
|
|
|
|
if (other.singleEntry())
|
|
|
|
return add(other.singleEntry());
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
2018-05-08 21:49:09 +00:00
|
|
|
return mergeOtherOutOfLine(other);
|
2015-06-08 19:41:47 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
template<typename Functor>
|
|
|
|
void forEach(const Functor& functor) const
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
if (!singleEntry())
|
|
|
|
return;
|
|
|
|
functor(singleEntry());
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i)
|
|
|
|
functor(list->list()[i]);
|
|
|
|
}
|
|
|
|
|
|
|
|
template<typename Functor>
|
|
|
|
void genericFilter(const Functor& functor)
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
if (!singleEntry())
|
|
|
|
return;
|
|
|
|
if (functor(singleEntry()))
|
|
|
|
return;
|
|
|
|
clear();
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (functor(list->list()[i]))
|
|
|
|
continue;
|
|
|
|
list->list()[i--] = list->list()[--list->m_length];
|
|
|
|
}
|
|
|
|
if (!list->m_length)
|
|
|
|
clear();
|
|
|
|
}
|
|
|
|
|
|
|
|
void filter(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
if (other.isThin()) {
|
|
|
|
if (!other.singleEntry() || !contains(other.singleEntry()))
|
|
|
|
clear();
|
|
|
|
else {
|
|
|
|
clear();
|
|
|
|
set(other.singleEntry());
|
|
|
|
}
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
genericFilter([&] (T value) { return other.containsOutOfLine(value); });
|
|
|
|
}
|
|
|
|
|
|
|
|
void exclude(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
if (other.isThin()) {
|
|
|
|
if (other.singleEntry())
|
|
|
|
remove(other.singleEntry());
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
|
|
|
|
genericFilter([&] (T value) { return !other.containsOutOfLine(value); });
|
|
|
|
}
|
|
|
|
|
|
|
|
bool isSubsetOf(const TinyPtrSet& other) const
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
if (!singleEntry())
|
|
|
|
return true;
|
|
|
|
return other.contains(singleEntry());
|
|
|
|
}
|
|
|
|
|
|
|
|
if (other.isThin()) {
|
|
|
|
if (!other.singleEntry())
|
|
|
|
return false;
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
if (list->m_length >= 2)
|
|
|
|
return false;
|
|
|
|
if (list->list()[0] == other.singleEntry())
|
|
|
|
return true;
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (!other.containsOutOfLine(list->list()[i]))
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
|
|
|
|
bool isSupersetOf(const TinyPtrSet& other) const
|
|
|
|
{
|
|
|
|
return other.isSubsetOf(*this);
|
|
|
|
}
|
|
|
|
|
|
|
|
bool overlaps(const TinyPtrSet& other) const
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
if (!singleEntry())
|
|
|
|
return false;
|
|
|
|
return other.contains(singleEntry());
|
|
|
|
}
|
|
|
|
|
|
|
|
if (other.isThin()) {
|
|
|
|
if (!other.singleEntry())
|
|
|
|
return false;
|
|
|
|
return containsOutOfLine(other.singleEntry());
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (other.containsOutOfLine(list->list()[i]))
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
size_t size() const
|
|
|
|
{
|
|
|
|
if (isThin())
|
|
|
|
return !!singleEntry();
|
|
|
|
return list()->m_length;
|
|
|
|
}
|
|
|
|
|
|
|
|
T at(size_t i) const
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
ASSERT(!i);
|
|
|
|
ASSERT(singleEntry());
|
|
|
|
return singleEntry();
|
|
|
|
}
|
|
|
|
ASSERT(i < list()->m_length);
|
|
|
|
return list()->list()[i];
|
|
|
|
}
|
|
|
|
|
|
|
|
T operator[](size_t i) const { return at(i); }
|
|
|
|
|
|
|
|
T last() const
|
|
|
|
{
|
|
|
|
if (isThin()) {
|
|
|
|
ASSERT(singleEntry());
|
|
|
|
return singleEntry();
|
|
|
|
}
|
|
|
|
return list()->list()[list()->m_length - 1];
|
|
|
|
}
|
|
|
|
|
|
|
|
class iterator {
|
|
|
|
public:
|
|
|
|
iterator()
|
|
|
|
: m_set(nullptr)
|
|
|
|
, m_index(0)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
iterator(const TinyPtrSet* set, size_t index)
|
|
|
|
: m_set(set)
|
|
|
|
, m_index(index)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
2015-06-10 22:44:12 +00:00
|
|
|
T operator*() const { return m_set->at(m_index); }
|
2015-06-08 19:41:47 +00:00
|
|
|
iterator& operator++()
|
|
|
|
{
|
|
|
|
m_index++;
|
|
|
|
return *this;
|
|
|
|
}
|
|
|
|
bool operator==(const iterator& other) const { return m_index == other.m_index; }
|
|
|
|
bool operator!=(const iterator& other) const { return !(*this == other); }
|
|
|
|
|
|
|
|
private:
|
|
|
|
const TinyPtrSet* m_set;
|
|
|
|
size_t m_index;
|
|
|
|
};
|
|
|
|
|
|
|
|
iterator begin() const { return iterator(this, 0); }
|
|
|
|
iterator end() const { return iterator(this, size()); }
|
|
|
|
|
|
|
|
bool operator==(const TinyPtrSet& other) const
|
|
|
|
{
|
|
|
|
if (size() != other.size())
|
|
|
|
return false;
|
|
|
|
return isSubsetOf(other);
|
|
|
|
}
|
|
|
|
|
We should support CreateThis in the FTL
https://bugs.webkit.org/show_bug.cgi?id=164904
Reviewed by Yusuke Suzuki.
JSTests:
* microbenchmarks/polyvariant-get-by-id-shorter-tower.js: Added.
(polyvariant):
(Foo.prototype.func):
(Foo):
(foo):
(Bar.prototype.func):
(Bar):
(bar):
* microbenchmarks/polyvariant-get-by-id-tower.js: Added.
(polyvariant):
(Foo.prototype.func):
(Foo):
(foo):
(Bar.prototype.func):
(Bar):
(bar):
(Baz.prototype.func):
(Baz):
(baz):
Source/JavaScriptCore:
This started with Saam's patch to implement CreateThis in the FTL, but turned into a type
inference adventure.
CreateThis in the FTL was a massive regression in raytrace because it disturbed that
benchmark's extremely perverse way of winning at type inference:
- The benchmark wanted polyvariant devirtualization of an object construction helper. But,
the polyvariant profiler wasn't powerful enough to reliably devirtualize that code. So, the
benchmark was falling back to other mechanisms...
- The construction helper could not tier up into the FTL. When the DFG compiled it, it would
see that the IC had 4 cases. That's too polymorphic for the DFG. So, the DFG would emit a
GetById. Shortly after the DFG compile, that get_by_id would see many more cases, but now
that the helper was compiled by the DFG, the baseline get_by_id would not see those cases.
The DFG's GetById would "hide" those cases. The number of cases the DFG's GetById would see
is larger than our polymorphic list limit (limit = 8, case count = 13, I think).
Note that if the FTL compiles that construction helper, it sees the 4 cases, turns them
into a MultiGetByOffset, then suffers from exits when the new cases hit, and then exits to
baseline, which then sees those cases. Luckily, the FTL was not compiling the construction
helper because it had a CreateThis.
- Compilations that inlined the construction helper would have gotten super lucky with
parse-time constant folding, so they knew what structure the input to the get_by_id would
have at parse time. This is only profitable if the get_by_id parsing computed a
GetByIdStatus that had a finite number of cases. Because the 13 cases were being hidden by
the DFG GetById and GetByIdStatus would only look at the baseline get_by_id, which had 4
cases, we would indeed get a finite number of cases. The parser would then prune those
cases to just one - based on its knowledge of the structure - and that would result in that
get_by_id being folded at parse time to a constant.
- The subsequent op_call would inline based on parse-time knowledge of that constant.
This patch comprehensively fixes these issues, as well as other issues that come up along the
way. The short version is that raytrace was revealing sloppiness in our use of profiling for
type inference. This patch fixes the sloppiness by vastly expanding *polyvariant* profiling,
i.e. the profiling that considers call context. I was encouraged to do this by the fact that
even the old version of polyvariant profiling was a speed-up on JetStream, ARES-6, and
Speedometer 2 (it's easy to measure since it's a runtime flag). So, it seemed worthwhile to
attack raytrace's problem as a shortcoming of polyvariant profiling.
- Polyvariant profiling now consults every DFG or FTL code block that participated in any
subset of the inline stack that includes the IC we're profiling. For example, if we have
an inline stack like foo->bar->baz, with baz on top, then we will consult DFG or FTL
compilations for foo, bar, and baz. In foo, we'll look up foo->bar->baz; in bar we'll look
up bar->baz; etc. This fixes two problems encountered in raytrace. First, it ensures that
a DFG GetById cannot hide anything from the profiling of that get_by_id, since the
polyvariant profiling code will always consult it. Second, it enables raytrace to benefit
from polyvariant profling. Previously, the polyvariant profiler would only look at the
previous DFG compilation of foo and look up foo->bar->baz. But that only works if DFG-foo
had inlined bar and then baz. It may not have done that, because those calls could have
required polyvariant profiling that was only available in the FTL.
- A particularly interesting case is when some IC in foo-baseline is also available in
foo-DFG. This case is encountered by the polyvariant profiler as it walks the inline stack.
In the case of gathering profiling for foo-FTL, the polyvariant profiler finds foo-DFG via
the trivial case of no inline stack. This also means that if foo ever gets inlined, we will
find foo-DFG or foo-FTL in the final case of polyvariant profiling. In those cases, we now
merge the IC of foo-baseline and foo-DFG. This avoids lots of unnecessary recompilations,
because it warns us of historical polymorphism. Historical polymorphism usually means
future polymorphism. IC status code already had some merging functionality, but I needed to
beef it up a lot to make this work right.
- Inlining an inline cache now preserves as much information as profiling. One challenge of
polyvariant profiling is that the FTL compile for bar (that includes bar->baz) could have
inlined an inline cache based on polyvariant profiling. So, when the FTL compile for foo
(that includes foo->bar->baz) asks bar what it knows about that IC inside bar->baz, it will
say "I don't have such an IC". At this point the DFG compilation that included that IC that
gave us the information that we used to inline the IC is no longer alive. To keep us from
losing the information we learned about the IC, there is now a RecordedStatuses data
structure that preserves the statuses we use for inlining ICs. We also filter those
statuses according to things we learn from AI. This further reduces the risk of information
about an IC being forgotten.
- Exit profiling now considers whether or not an exit happened from inline code. This
protects us in the case where the not-inlined version of an IC exited a lot because of
polymorphism that doesn't exist in the inlined version. So, when using polyvariant
profiling data, we consider only inlined exits.
- CallLinkInfo now records when it's repatched to the virtual call thunk. Previously, this
would clear the CallLinkInfo, so CallLinkStatus would fall back to the lastSeenCallee. It's
surprising that we've had this bug.
Altogether this patch is performance-neutral in run-jsc-benchmarks, except for speed-ups in
microbenchmarks and a compile time regression. Octane/deltablue speeds up by ~5%.
Octane/raytrace is regressed by a minuscule amount, which we could make up by implementing
prototype access folding in the bytecode parser and constant folder. That would require some
significant new logic in GetByIdStatus. That would also require a new benchmark - we want to
have a test that captures raytrace's behavior in the case that the parser cannot fold the
get_by_id.
This change is a 1.2% regression on V8Spider-CompileTime. That's a smaller regression than
recent compile time progressions, so I think that's an OK trade-off. Also, I would expect a
compile time regression anytime we fill in FTL coverage.
This is neutral on JetStream, ARES-6, and Speedometer2. JetStream agrees that deltablue
speeds up and that raytrace slows down, but these changes balance out and don't affect the
overall score. In ARES-6, it looks like individual tests have some significant 1-2% speed-ups
or slow-downs. Air-steady is definitely ~1.5% faster. Basic-worst is probably 2% slower (p ~
0.1, so it's not very certain). The JetStream, ARES-6, and Speedometer2 overall scores don't
see a significant difference. In all three cases the difference is <0.5% with a high p value,
with JetStream and Speedometer2 being insignificant infinitesimal speed-ups and ARES-6 being
an insignificant infinitesimal slow-down.
Oh, and this change means that the FTL now has 100% coverage of JavaScript. You could do an
eval in a for-in loop in a for-of loop inside a with block that uses try/catch for control
flow in a polymorphic constructor while having a bad time, and we'll still compile it.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* Sources.txt:
* bytecode/ByValInfo.h:
* bytecode/BytecodeDumper.cpp:
(JSC::BytecodeDumper<Block>::printGetByIdCacheStatus):
(JSC::BytecodeDumper<Block>::printPutByIdCacheStatus):
(JSC::BytecodeDumper<Block>::printInByIdCacheStatus):
(JSC::BytecodeDumper<Block>::dumpCallLinkStatus):
(JSC::BytecodeDumper<CodeBlock>::dumpCallLinkStatus):
(JSC::BytecodeDumper<Block>::printCallOp):
(JSC::BytecodeDumper<Block>::dumpBytecode):
(JSC::BytecodeDumper<Block>::dumpBlock):
* bytecode/BytecodeDumper.h:
* bytecode/CallLinkInfo.h:
* bytecode/CallLinkStatus.cpp:
(JSC::CallLinkStatus::computeFor):
(JSC::CallLinkStatus::computeExitSiteData):
(JSC::CallLinkStatus::computeFromCallLinkInfo):
(JSC::CallLinkStatus::accountForExits):
(JSC::CallLinkStatus::finalize):
(JSC::CallLinkStatus::filter):
(JSC::CallLinkStatus::computeDFGStatuses): Deleted.
* bytecode/CallLinkStatus.h:
(JSC::CallLinkStatus::operator bool const):
(JSC::CallLinkStatus::operator! const): Deleted.
* bytecode/CallVariant.cpp:
(JSC::CallVariant::finalize):
(JSC::CallVariant::filter):
* bytecode/CallVariant.h:
(JSC::CallVariant::operator bool const):
(JSC::CallVariant::operator! const): Deleted.
* bytecode/CodeBlock.cpp:
(JSC::CodeBlock::dumpBytecode):
(JSC::CodeBlock::propagateTransitions):
(JSC::CodeBlock::finalizeUnconditionally):
(JSC::CodeBlock::getICStatusMap):
(JSC::CodeBlock::resetJITData):
(JSC::CodeBlock::getStubInfoMap): Deleted.
(JSC::CodeBlock::getCallLinkInfoMap): Deleted.
(JSC::CodeBlock::getByValInfoMap): Deleted.
* bytecode/CodeBlock.h:
* bytecode/CodeOrigin.cpp:
(JSC::CodeOrigin::isApproximatelyEqualTo const):
(JSC::CodeOrigin::approximateHash const):
* bytecode/CodeOrigin.h:
(JSC::CodeOrigin::exitingInlineKind const):
* bytecode/DFGExitProfile.cpp:
(JSC::DFG::FrequentExitSite::dump const):
(JSC::DFG::ExitProfile::add):
* bytecode/DFGExitProfile.h:
(JSC::DFG::FrequentExitSite::FrequentExitSite):
(JSC::DFG::FrequentExitSite::operator== const):
(JSC::DFG::FrequentExitSite::subsumes const):
(JSC::DFG::FrequentExitSite::hash const):
(JSC::DFG::FrequentExitSite::inlineKind const):
(JSC::DFG::FrequentExitSite::withInlineKind const):
(JSC::DFG::QueryableExitProfile::hasExitSite const):
(JSC::DFG::QueryableExitProfile::hasExitSiteWithSpecificJITType const):
(JSC::DFG::QueryableExitProfile::hasExitSiteWithSpecificInlineKind const):
* bytecode/ExitFlag.cpp: Added.
(JSC::ExitFlag::dump const):
* bytecode/ExitFlag.h: Added.
(JSC::ExitFlag::ExitFlag):
(JSC::ExitFlag::operator| const):
(JSC::ExitFlag::operator|=):
(JSC::ExitFlag::operator& const):
(JSC::ExitFlag::operator&=):
(JSC::ExitFlag::operator bool const):
(JSC::ExitFlag::isSet const):
* bytecode/ExitingInlineKind.cpp: Added.
(WTF::printInternal):
* bytecode/ExitingInlineKind.h: Added.
* bytecode/GetByIdStatus.cpp:
(JSC::GetByIdStatus::computeFor):
(JSC::GetByIdStatus::computeForStubInfo):
(JSC::GetByIdStatus::slowVersion const):
(JSC::GetByIdStatus::markIfCheap):
(JSC::GetByIdStatus::finalize):
(JSC::GetByIdStatus::hasExitSite): Deleted.
* bytecode/GetByIdStatus.h:
* bytecode/GetByIdVariant.cpp:
(JSC::GetByIdVariant::markIfCheap):
(JSC::GetByIdVariant::finalize):
* bytecode/GetByIdVariant.h:
* bytecode/ICStatusMap.cpp: Added.
(JSC::ICStatusContext::get const):
(JSC::ICStatusContext::isInlined const):
(JSC::ICStatusContext::inlineKind const):
* bytecode/ICStatusMap.h: Added.
* bytecode/ICStatusUtils.cpp: Added.
(JSC::hasBadCacheExitSite):
* bytecode/ICStatusUtils.h:
* bytecode/InstanceOfStatus.cpp:
(JSC::InstanceOfStatus::computeFor):
* bytecode/InstanceOfStatus.h:
* bytecode/PolyProtoAccessChain.h:
* bytecode/PutByIdStatus.cpp:
(JSC::PutByIdStatus::hasExitSite):
(JSC::PutByIdStatus::computeFor):
(JSC::PutByIdStatus::slowVersion const):
(JSC::PutByIdStatus::markIfCheap):
(JSC::PutByIdStatus::finalize):
(JSC::PutByIdStatus::filter):
* bytecode/PutByIdStatus.h:
* bytecode/PutByIdVariant.cpp:
(JSC::PutByIdVariant::markIfCheap):
(JSC::PutByIdVariant::finalize):
* bytecode/PutByIdVariant.h:
(JSC::PutByIdVariant::structureSet const):
* bytecode/RecordedStatuses.cpp: Added.
(JSC::RecordedStatuses::operator=):
(JSC::RecordedStatuses::RecordedStatuses):
(JSC::RecordedStatuses::addCallLinkStatus):
(JSC::RecordedStatuses::addGetByIdStatus):
(JSC::RecordedStatuses::addPutByIdStatus):
(JSC::RecordedStatuses::markIfCheap):
(JSC::RecordedStatuses::finalizeWithoutDeleting):
(JSC::RecordedStatuses::finalize):
(JSC::RecordedStatuses::shrinkToFit):
* bytecode/RecordedStatuses.h: Added.
(JSC::RecordedStatuses::RecordedStatuses):
(JSC::RecordedStatuses::forEachVector):
* bytecode/StructureSet.cpp:
(JSC::StructureSet::markIfCheap const):
(JSC::StructureSet::isStillAlive const):
* bytecode/StructureSet.h:
* bytecode/TerminatedCodeOrigin.h: Added.
(JSC::TerminatedCodeOrigin::TerminatedCodeOrigin):
(JSC::TerminatedCodeOriginHashTranslator::hash):
(JSC::TerminatedCodeOriginHashTranslator::equal):
* bytecode/Watchpoint.cpp:
(WTF::printInternal):
* bytecode/Watchpoint.h:
* dfg/DFGAbstractInterpreter.h:
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::filterICStatus):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleCall):
(JSC::DFG::ByteCodeParser::handleVarargsCall):
(JSC::DFG::ByteCodeParser::handleDOMJITGetter):
(JSC::DFG::ByteCodeParser::handleModuleNamespaceLoad):
(JSC::DFG::ByteCodeParser::handleGetById):
(JSC::DFG::ByteCodeParser::handlePutById):
(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::InlineStackEntry::InlineStackEntry):
(JSC::DFG::ByteCodeParser::InlineStackEntry::~InlineStackEntry):
(JSC::DFG::ByteCodeParser::parse):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGClobbersExitState.cpp:
(JSC::DFG::clobbersExitState):
* dfg/DFGCommonData.h:
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::foldConstants):
* dfg/DFGDesiredWatchpoints.h:
(JSC::DFG::SetPointerAdaptor::hasBeenInvalidated):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
* dfg/DFGMayExit.cpp:
* dfg/DFGNode.h:
(JSC::DFG::Node::hasCallLinkStatus):
(JSC::DFG::Node::callLinkStatus):
(JSC::DFG::Node::hasGetByIdStatus):
(JSC::DFG::Node::getByIdStatus):
(JSC::DFG::Node::hasPutByIdStatus):
(JSC::DFG::Node::putByIdStatus):
* dfg/DFGNodeType.h:
* dfg/DFGOSRExitBase.cpp:
(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::reallyAdd):
(JSC::DFG::Plan::checkLivenessAndVisitChildren):
(JSC::DFG::Plan::finalizeInGC):
* dfg/DFGPlan.h:
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStrengthReductionPhase.cpp:
(JSC::DFG::StrengthReductionPhase::handleNode):
* dfg/DFGWorklist.cpp:
(JSC::DFG::Worklist::removeDeadPlans):
* ftl/FTLAbstractHeapRepository.h:
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileNode):
(JSC::FTL::DFG::LowerDFGToB3::compileCreateThis):
(JSC::FTL::DFG::LowerDFGToB3::compileFilterICStatus):
* jit/PolymorphicCallStubRoutine.cpp:
(JSC::PolymorphicCallStubRoutine::hasEdges const):
(JSC::PolymorphicCallStubRoutine::edges const):
* jit/PolymorphicCallStubRoutine.h:
* profiler/ProfilerBytecodeSequence.cpp:
(JSC::Profiler::BytecodeSequence::BytecodeSequence):
* runtime/FunctionRareData.cpp:
(JSC::FunctionRareData::initializeObjectAllocationProfile):
* runtime/Options.h:
Source/WTF:
* wtf/TinyPtrSet.h:
(WTF::TinyPtrSet::operator!= const):
Canonical link: https://commits.webkit.org/203069@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@234086 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2018-07-22 02:48:16 +00:00
|
|
|
bool operator!=(const TinyPtrSet& other) const
|
|
|
|
{
|
|
|
|
return !(*this == other);
|
|
|
|
}
|
|
|
|
|
2015-06-08 19:41:47 +00:00
|
|
|
private:
|
|
|
|
friend class JSC::DFG::StructureAbstractValue;
|
|
|
|
|
2019-09-18 00:36:19 +00:00
|
|
|
static constexpr uintptr_t fatFlag = 1;
|
|
|
|
static constexpr uintptr_t reservedFlag = 2;
|
|
|
|
static constexpr uintptr_t flags = fatFlag | reservedFlag;
|
|
|
|
static constexpr uintptr_t reservedValue = 4;
|
2015-06-08 19:41:47 +00:00
|
|
|
|
2019-09-18 00:36:19 +00:00
|
|
|
static constexpr unsigned defaultStartingSize = 4;
|
2015-06-08 19:41:47 +00:00
|
|
|
|
2018-05-08 21:49:09 +00:00
|
|
|
NEVER_INLINE bool addOutOfLine(T value)
|
2015-06-08 19:41:47 +00:00
|
|
|
{
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (list->list()[i] == value)
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (list->m_length < list->m_capacity) {
|
|
|
|
list->list()[list->m_length++] = value;
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* newList = OutOfLineList::create(list->m_capacity * 2);
|
|
|
|
newList->m_length = list->m_length + 1;
|
|
|
|
for (unsigned i = list->m_length; i--;)
|
|
|
|
newList->list()[i] = list->list()[i];
|
|
|
|
newList->list()[list->m_length] = value;
|
|
|
|
OutOfLineList::destroy(list);
|
|
|
|
set(newList);
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
|
2018-05-08 21:49:09 +00:00
|
|
|
NEVER_INLINE bool mergeOtherOutOfLine(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
OutOfLineList* list = other.list();
|
|
|
|
if (list->m_length >= 2) {
|
|
|
|
if (isThin()) {
|
|
|
|
OutOfLineList* myNewList = OutOfLineList::create(
|
|
|
|
list->m_length + !!singleEntry());
|
|
|
|
if (singleEntry()) {
|
|
|
|
myNewList->m_length = 1;
|
|
|
|
myNewList->list()[0] = singleEntry();
|
|
|
|
}
|
|
|
|
set(myNewList);
|
|
|
|
}
|
|
|
|
bool changed = false;
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i)
|
|
|
|
changed |= addOutOfLine(list->list()[i]);
|
|
|
|
return changed;
|
|
|
|
}
|
|
|
|
|
|
|
|
ASSERT(list->m_length);
|
|
|
|
return add(list->list()[0]);
|
|
|
|
}
|
|
|
|
|
2015-06-08 19:41:47 +00:00
|
|
|
bool containsOutOfLine(T value) const
|
|
|
|
{
|
|
|
|
OutOfLineList* list = this->list();
|
|
|
|
for (unsigned i = 0; i < list->m_length; ++i) {
|
|
|
|
if (list->list()[i] == value)
|
|
|
|
return true;
|
|
|
|
}
|
|
|
|
return false;
|
|
|
|
}
|
|
|
|
|
|
|
|
ALWAYS_INLINE void copyFrom(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
if (other.isThin() || other.m_pointer == reservedValue) {
|
|
|
|
bool value = getReservedFlag();
|
|
|
|
m_pointer = other.m_pointer;
|
|
|
|
setReservedFlag(value);
|
|
|
|
return;
|
|
|
|
}
|
|
|
|
copyFromOutOfLine(other);
|
|
|
|
}
|
|
|
|
|
|
|
|
NEVER_INLINE void copyFromOutOfLine(const TinyPtrSet& other)
|
|
|
|
{
|
|
|
|
ASSERT(!other.isThin() && other.m_pointer != reservedValue);
|
|
|
|
OutOfLineList* otherList = other.list();
|
|
|
|
OutOfLineList* myList = OutOfLineList::create(otherList->m_length);
|
|
|
|
myList->m_length = otherList->m_length;
|
|
|
|
for (unsigned i = otherList->m_length; i--;)
|
|
|
|
myList->list()[i] = otherList->list()[i];
|
|
|
|
set(myList);
|
|
|
|
}
|
|
|
|
|
|
|
|
class OutOfLineList {
|
|
|
|
public:
|
|
|
|
static OutOfLineList* create(unsigned capacity)
|
|
|
|
{
|
|
|
|
return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(T))) OutOfLineList(0, capacity);
|
|
|
|
}
|
|
|
|
|
|
|
|
static void destroy(OutOfLineList* list)
|
|
|
|
{
|
|
|
|
fastFree(list);
|
|
|
|
}
|
|
|
|
|
|
|
|
T* list() { return bitwise_cast<T*>(this + 1); }
|
|
|
|
|
|
|
|
OutOfLineList(unsigned length, unsigned capacity)
|
|
|
|
: m_length(length)
|
|
|
|
, m_capacity(capacity)
|
|
|
|
{
|
|
|
|
}
|
|
|
|
|
|
|
|
unsigned m_length;
|
|
|
|
unsigned m_capacity;
|
|
|
|
};
|
|
|
|
|
|
|
|
ALWAYS_INLINE void deleteListIfNecessary()
|
|
|
|
{
|
2016-08-10 21:23:20 +00:00
|
|
|
if (!isThin()) {
|
|
|
|
ASSERT(m_pointer != reservedValue);
|
2015-06-08 19:41:47 +00:00
|
|
|
OutOfLineList::destroy(list());
|
2016-08-10 21:23:20 +00:00
|
|
|
}
|
2015-06-08 19:41:47 +00:00
|
|
|
}
|
|
|
|
|
2016-08-03 03:45:07 +00:00
|
|
|
bool isThin() const { return !(m_pointer & fatFlag); }
|
2015-06-08 19:41:47 +00:00
|
|
|
|
|
|
|
void* pointer() const
|
|
|
|
{
|
|
|
|
return bitwise_cast<void*>(m_pointer & ~flags);
|
|
|
|
}
|
|
|
|
|
|
|
|
T singleEntry() const
|
|
|
|
{
|
|
|
|
ASSERT(isThin());
|
2017-01-26 23:50:58 +00:00
|
|
|
return bitwise_cast<T>(pointer());
|
2015-06-08 19:41:47 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
OutOfLineList* list() const
|
|
|
|
{
|
|
|
|
ASSERT(!isThin());
|
|
|
|
return static_cast<OutOfLineList*>(pointer());
|
|
|
|
}
|
|
|
|
|
|
|
|
void set(T value)
|
|
|
|
{
|
|
|
|
set(bitwise_cast<uintptr_t>(value), true);
|
|
|
|
}
|
|
|
|
void set(OutOfLineList* list)
|
|
|
|
{
|
|
|
|
set(bitwise_cast<uintptr_t>(list), false);
|
|
|
|
}
|
|
|
|
void setEmpty()
|
|
|
|
{
|
|
|
|
set(0, true);
|
|
|
|
}
|
|
|
|
void set(uintptr_t pointer, bool singleEntry)
|
|
|
|
{
|
2016-08-03 03:45:07 +00:00
|
|
|
m_pointer = pointer | (singleEntry ? 0 : fatFlag) | (m_pointer & reservedFlag);
|
2015-06-08 19:41:47 +00:00
|
|
|
}
|
|
|
|
bool getReservedFlag() const { return m_pointer & reservedFlag; }
|
|
|
|
void setReservedFlag(bool value)
|
|
|
|
{
|
|
|
|
if (value)
|
|
|
|
m_pointer |= reservedFlag;
|
|
|
|
else
|
|
|
|
m_pointer &= ~reservedFlag;
|
|
|
|
}
|
|
|
|
|
|
|
|
uintptr_t m_pointer;
|
|
|
|
};
|
|
|
|
|
|
|
|
} // namespace WTF
|
|
|
|
|
|
|
|
using WTF::TinyPtrSet;
|