The tiny set magic in StructureSet should be available in WTF
https://bugs.webkit.org/show_bug.cgi?id=145722
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
I moved the generic logic of small sets of pointers and moved it into WTF. Now,
StructureSet is a subclass of TinyPtrSet<Structure*>. There shouldn't be any functional
change.
* bytecode/StructureSet.cpp:
(JSC::StructureSet::filter):
(JSC::StructureSet::filterArrayModes):
(JSC::StructureSet::speculationFromStructures):
(JSC::StructureSet::arrayModesFromStructures):
(JSC::StructureSet::dumpInContext):
(JSC::StructureSet::dump):
(JSC::StructureSet::clear): Deleted.
(JSC::StructureSet::add): Deleted.
(JSC::StructureSet::remove): Deleted.
(JSC::StructureSet::contains): Deleted.
(JSC::StructureSet::merge): Deleted.
(JSC::StructureSet::exclude): Deleted.
(JSC::StructureSet::isSubsetOf): Deleted.
(JSC::StructureSet::overlaps): Deleted.
(JSC::StructureSet::operator==): Deleted.
(JSC::StructureSet::addOutOfLine): Deleted.
(JSC::StructureSet::containsOutOfLine): Deleted.
(JSC::StructureSet::copyFromOutOfLine): Deleted.
(JSC::StructureSet::OutOfLineList::create): Deleted.
(JSC::StructureSet::OutOfLineList::destroy): Deleted.
* bytecode/StructureSet.h:
(JSC::StructureSet::onlyStructure):
(JSC::StructureSet::StructureSet): Deleted.
(JSC::StructureSet::operator=): Deleted.
(JSC::StructureSet::~StructureSet): Deleted.
(JSC::StructureSet::isEmpty): Deleted.
(JSC::StructureSet::genericFilter): Deleted.
(JSC::StructureSet::isSupersetOf): Deleted.
(JSC::StructureSet::size): Deleted.
(JSC::StructureSet::at): Deleted.
(JSC::StructureSet::operator[]): Deleted.
(JSC::StructureSet::last): Deleted.
(JSC::StructureSet::iterator::iterator): Deleted.
(JSC::StructureSet::iterator::operator*): Deleted.
(JSC::StructureSet::iterator::operator++): Deleted.
(JSC::StructureSet::iterator::operator==): Deleted.
(JSC::StructureSet::iterator::operator!=): Deleted.
(JSC::StructureSet::begin): Deleted.
(JSC::StructureSet::end): Deleted.
(JSC::StructureSet::ContainsOutOfLine::ContainsOutOfLine): Deleted.
(JSC::StructureSet::ContainsOutOfLine::operator()): Deleted.
(JSC::StructureSet::copyFrom): Deleted.
(JSC::StructureSet::OutOfLineList::list): Deleted.
(JSC::StructureSet::OutOfLineList::OutOfLineList): Deleted.
(JSC::StructureSet::deleteStructureListIfNecessary): Deleted.
(JSC::StructureSet::isThin): Deleted.
(JSC::StructureSet::pointer): Deleted.
(JSC::StructureSet::singleStructure): Deleted.
(JSC::StructureSet::structureList): Deleted.
(JSC::StructureSet::set): Deleted.
(JSC::StructureSet::setEmpty): Deleted.
(JSC::StructureSet::getReservedFlag): Deleted.
(JSC::StructureSet::setReservedFlag): Deleted.
* dfg/DFGStructureAbstractValue.cpp:
(JSC::DFG::StructureAbstractValue::clobber):
(JSC::DFG::StructureAbstractValue::filter):
(JSC::DFG::StructureAbstractValue::filterSlow):
(JSC::DFG::StructureAbstractValue::contains):
* dfg/DFGStructureAbstractValue.h:
(JSC::DFG::StructureAbstractValue::makeTop):
Source/WTF:
As the management of structure sets evolved in JSC, the StructureSet data structure grew
increasingly smart. It's got some smart stuff for managing small sets of pointers. I
wanted to take the generic logic out of JSC and put it into a reusable templatized class
in WTF.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/TinyPtrSet.h: Added.
(WTF::TinyPtrSet::TinyPtrSet):
(WTF::TinyPtrSet::operator=):
(WTF::TinyPtrSet::~TinyPtrSet):
(WTF::TinyPtrSet::clear):
(WTF::TinyPtrSet::onlyEntry):
(WTF::TinyPtrSet::isEmpty):
(WTF::TinyPtrSet::add):
(WTF::TinyPtrSet::remove):
(WTF::TinyPtrSet::contains):
(WTF::TinyPtrSet::merge):
(WTF::TinyPtrSet::forEach):
(WTF::TinyPtrSet::genericFilter):
(WTF::TinyPtrSet::filter):
(WTF::TinyPtrSet::exclude):
(WTF::TinyPtrSet::isSubsetOf):
(WTF::TinyPtrSet::isSupersetOf):
(WTF::TinyPtrSet::overlaps):
(WTF::TinyPtrSet::size):
(WTF::TinyPtrSet::at):
(WTF::TinyPtrSet::operator[]):
(WTF::TinyPtrSet::last):
(WTF::TinyPtrSet::iterator::iterator):
(WTF::TinyPtrSet::iterator::operator*):
(WTF::TinyPtrSet::iterator::operator++):
(WTF::TinyPtrSet::iterator::operator==):
(WTF::TinyPtrSet::iterator::operator!=):
(WTF::TinyPtrSet::begin):
(WTF::TinyPtrSet::end):
(WTF::TinyPtrSet::operator==):
(WTF::TinyPtrSet::addOutOfLine):
(WTF::TinyPtrSet::containsOutOfLine):
(WTF::TinyPtrSet::copyFrom):
(WTF::TinyPtrSet::copyFromOutOfLine):
(WTF::TinyPtrSet::OutOfLineList::create):
(WTF::TinyPtrSet::OutOfLineList::destroy):
(WTF::TinyPtrSet::OutOfLineList::list):
(WTF::TinyPtrSet::OutOfLineList::OutOfLineList):
(WTF::TinyPtrSet::deleteListIfNecessary):
(WTF::TinyPtrSet::isThin):
(WTF::TinyPtrSet::pointer):
(WTF::TinyPtrSet::singleEntry):
(WTF::TinyPtrSet::list):
(WTF::TinyPtrSet::set):
(WTF::TinyPtrSet::setEmpty):
(WTF::TinyPtrSet::getReservedFlag):
(WTF::TinyPtrSet::setReservedFlag):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@185324 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/bytecode/StructureSet.cpp b/Source/JavaScriptCore/bytecode/StructureSet.cpp
index 3d2c109..55fdb7d 100644
--- a/Source/JavaScriptCore/bytecode/StructureSet.cpp
+++ b/Source/JavaScriptCore/bytecode/StructureSet.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -31,203 +31,27 @@
namespace JSC {
-void StructureSet::clear()
-{
- deleteStructureListIfNecessary();
- setEmpty();
-}
-
-bool StructureSet::add(Structure* structure)
-{
- ASSERT(structure);
- if (isThin()) {
- if (singleStructure() == structure)
- return false;
- if (!singleStructure()) {
- set(structure);
- return true;
- }
- OutOfLineList* list = OutOfLineList::create(defaultStartingSize);
- list->m_length = 2;
- list->list()[0] = singleStructure();
- list->list()[1] = structure;
- set(list);
- return true;
- }
-
- return addOutOfLine(structure);
-}
-
-bool StructureSet::remove(Structure* structure)
-{
- if (isThin()) {
- if (singleStructure() == structure) {
- setEmpty();
- return true;
- }
- return false;
- }
-
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (list->list()[i] != structure)
- continue;
- list->list()[i] = list->list()[--list->m_length];
- if (!list->m_length) {
- OutOfLineList::destroy(list);
- setEmpty();
- }
- return true;
- }
- return false;
-}
-
-bool StructureSet::contains(Structure* structure) const
-{
- if (isThin())
- return singleStructure() == structure;
-
- return containsOutOfLine(structure);
-}
-
-bool StructureSet::merge(const StructureSet& other)
-{
- if (other.isThin()) {
- if (other.singleStructure())
- return add(other.singleStructure());
- return false;
- }
-
- OutOfLineList* list = other.structureList();
- if (list->m_length >= 2) {
- if (isThin()) {
- OutOfLineList* myNewList = OutOfLineList::create(
- list->m_length + !!singleStructure());
- if (singleStructure()) {
- myNewList->m_length = 1;
- myNewList->list()[0] = singleStructure();
- }
- 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]);
-}
-
-void StructureSet::filter(const StructureSet& other)
-{
- if (other.isThin()) {
- if (!other.singleStructure() || !contains(other.singleStructure()))
- clear();
- else {
- clear();
- set(other.singleStructure());
- }
- return;
- }
-
- ContainsOutOfLine containsOutOfLine(other);
- genericFilter(containsOutOfLine);
-}
-
-void StructureSet::exclude(const StructureSet& other)
-{
- if (other.isThin()) {
- if (other.singleStructure())
- remove(other.singleStructure());
- return;
- }
-
- if (isThin()) {
- if (!singleStructure())
- return;
- if (other.contains(singleStructure()))
- clear();
- return;
- }
-
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (!other.containsOutOfLine(list->list()[i]))
- continue;
- list->list()[i--] = list->list()[--list->m_length];
- }
- if (!list->m_length)
- clear();
-}
-
#if ENABLE(DFG_JIT)
-namespace {
-
-class StructureAbstractValueContains {
-public:
- StructureAbstractValueContains(const DFG::StructureAbstractValue& value)
- : m_value(value)
- {
- }
-
- bool operator()(Structure* structure)
- {
- return m_value.contains(structure);
- }
-private:
- const DFG::StructureAbstractValue& m_value;
-};
-
-class SpeculatedTypeContains {
-public:
- SpeculatedTypeContains(SpeculatedType type)
- : m_type(type)
- {
- }
-
- bool operator()(Structure* structure)
- {
- return m_type & speculationFromStructure(structure);
- }
-private:
- SpeculatedType m_type;
-};
-
-class ArrayModesContains {
-public:
- ArrayModesContains(ArrayModes arrayModes)
- : m_arrayModes(arrayModes)
- {
- }
-
- bool operator()(Structure* structure)
- {
- return m_arrayModes & arrayModeFromStructure(structure);
- }
-private:
- ArrayModes m_arrayModes;
-};
-
-} // anonymous namespace
-
void StructureSet::filter(const DFG::StructureAbstractValue& other)
{
- StructureAbstractValueContains functor(other);
- genericFilter(functor);
+ genericFilter([&] (Structure* structure) -> bool { return other.contains(structure); });
}
void StructureSet::filter(SpeculatedType type)
{
- SpeculatedTypeContains functor(type);
- genericFilter(functor);
+ genericFilter(
+ [&] (Structure* structure) -> bool {
+ return type & speculationFromStructure(structure);
+ });
}
void StructureSet::filterArrayModes(ArrayModes arrayModes)
{
- ArrayModesContains functor(arrayModes);
- genericFilter(functor);
+ genericFilter(
+ [&] (Structure* structure) -> bool {
+ return arrayModes & arrayModeFromStructure(structure);
+ });
}
void StructureSet::filter(const DFG::AbstractValue& other)
@@ -239,89 +63,23 @@
#endif // ENABLE(DFG_JIT)
-bool StructureSet::isSubsetOf(const StructureSet& other) const
-{
- if (isThin()) {
- if (!singleStructure())
- return true;
- return other.contains(singleStructure());
- }
-
- if (other.isThin()) {
- if (!other.singleStructure())
- return false;
- OutOfLineList* list = structureList();
- if (list->m_length >= 2)
- return false;
- if (list->list()[0] == other.singleStructure())
- return true;
- return false;
- }
-
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (!other.containsOutOfLine(list->list()[i]))
- return false;
- }
- return true;
-}
-
-bool StructureSet::overlaps(const StructureSet& other) const
-{
- if (isThin()) {
- if (!singleStructure())
- return false;
- return other.contains(singleStructure());
- }
-
- if (other.isThin()) {
- if (!other.singleStructure())
- return false;
- return containsOutOfLine(other.singleStructure());
- }
-
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (other.containsOutOfLine(list->list()[i]))
- return true;
- }
- return false;
-}
-
-bool StructureSet::operator==(const StructureSet& other) const
-{
- if (size() != other.size())
- return false;
- return isSubsetOf(other);
-}
-
SpeculatedType StructureSet::speculationFromStructures() const
{
- if (isThin()) {
- if (!singleStructure())
- return SpecNone;
- return speculationFromStructure(singleStructure());
- }
-
SpeculatedType result = SpecNone;
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i)
- mergeSpeculation(result, speculationFromStructure(list->list()[i]));
+ forEach(
+ [&] (Structure* structure) {
+ mergeSpeculation(result, speculationFromStructure(structure));
+ });
return result;
}
ArrayModes StructureSet::arrayModesFromStructures() const
{
- if (isThin()) {
- if (!singleStructure())
- return 0;
- return asArrayModes(singleStructure()->indexingType());
- }
-
ArrayModes result = 0;
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i)
- mergeArrayModes(result, asArrayModes(list->list()[i]->indexingType()));
+ forEach(
+ [&] (Structure* structure) {
+ mergeArrayModes(result, asArrayModes(structure->indexingType()));
+ });
return result;
}
@@ -329,8 +87,7 @@
{
CommaPrinter comma;
out.print("[");
- for (size_t i = 0; i < size(); ++i)
- out.print(comma, inContext(*at(i), context));
+ forEach([&] (Structure* structure) { out.print(comma, inContext(*structure, context)); });
out.print("]");
}
@@ -339,59 +96,5 @@
dumpInContext(out, nullptr);
}
-bool StructureSet::addOutOfLine(Structure* structure)
-{
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (list->list()[i] == structure)
- return false;
- }
-
- if (list->m_length < list->m_capacity) {
- list->list()[list->m_length++] = structure;
- 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] = structure;
- OutOfLineList::destroy(list);
- set(newList);
- return true;
-}
-
-bool StructureSet::containsOutOfLine(Structure* structure) const
-{
- OutOfLineList* list = structureList();
- for (unsigned i = 0; i < list->m_length; ++i) {
- if (list->list()[i] == structure)
- return true;
- }
- return false;
-}
-
-void StructureSet::copyFromOutOfLine(const StructureSet& other)
-{
- ASSERT(!other.isThin() && other.m_pointer != reservedValue);
- OutOfLineList* otherList = other.structureList();
- 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);
-}
-
-StructureSet::OutOfLineList* StructureSet::OutOfLineList::create(unsigned capacity)
-{
- return new (NotNull, fastMalloc(sizeof(OutOfLineList) + capacity * sizeof(Structure*))) OutOfLineList(0, capacity);
-}
-
-void StructureSet::OutOfLineList::destroy(OutOfLineList* list)
-{
- fastFree(list);
-}
-
} // namespace JSC
