Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (204919 => 204920)
--- trunk/Source/_javascript_Core/ChangeLog 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-08-24 19:35:41 UTC (rev 204920)
@@ -1,3 +1,70 @@
+2016-08-24 Yusuke Suzuki <[email protected]>
+
+ [JSC] Move generic data structures out of B3
+ https://bugs.webkit.org/show_bug.cgi?id=161155
+
+ Reviewed by Saam Barati.
+
+ Move B3's good generic data structures to WTF.
+ They can be used for the other kind of basic blocks and nodes.
+ For example, the generator patch[1] will make BytecodeBasicBlock usable with these structures.
+
+ [1]: https://bugs.webkit.org/show_bug.cgi?id=152723
+
+ * _javascript_Core.xcodeproj/project.pbxproj:
+ * b3/B3BasicBlockUtils.h:
+ * b3/B3BlockWorklist.h:
+ * b3/B3CFG.h:
+ * b3/B3DuplicateTails.cpp:
+ * b3/B3FixSSA.cpp:
+ * b3/B3FixSSA.h:
+ * b3/B3IndexMap.h:
+ (JSC::B3::IndexMap::IndexMap): Deleted.
+ (JSC::B3::IndexMap::resize): Deleted.
+ (JSC::B3::IndexMap::clear): Deleted.
+ (JSC::B3::IndexMap::size): Deleted.
+ (JSC::B3::IndexMap::operator[]): Deleted.
+ * b3/B3IndexSet.h:
+ (JSC::B3::IndexSet::IndexSet): Deleted.
+ (JSC::B3::IndexSet::add): Deleted.
+ (JSC::B3::IndexSet::addAll): Deleted.
+ (JSC::B3::IndexSet::remove): Deleted.
+ (JSC::B3::IndexSet::contains): Deleted.
+ (JSC::B3::IndexSet::size): Deleted.
+ (JSC::B3::IndexSet::isEmpty): Deleted.
+ (JSC::B3::IndexSet::Iterable::Iterable): Deleted.
+ (JSC::B3::IndexSet::Iterable::iterator::iterator): Deleted.
+ (JSC::B3::IndexSet::Iterable::iterator::operator*): Deleted.
+ (JSC::B3::IndexSet::Iterable::iterator::operator++): Deleted.
+ (JSC::B3::IndexSet::Iterable::iterator::operator==): Deleted.
+ (JSC::B3::IndexSet::Iterable::iterator::operator!=): Deleted.
+ (JSC::B3::IndexSet::Iterable::begin): Deleted.
+ (JSC::B3::IndexSet::Iterable::end): Deleted.
+ (JSC::B3::IndexSet::values): Deleted.
+ (JSC::B3::IndexSet::indices): Deleted.
+ (JSC::B3::IndexSet::dump): Deleted.
+ * b3/B3LowerToAir.cpp:
+ * b3/B3PhiChildren.h:
+ * b3/B3Procedure.h:
+ (JSC::B3::Procedure::iterator::iterator): Deleted.
+ (JSC::B3::Procedure::iterator::operator*): Deleted.
+ (JSC::B3::Procedure::iterator::operator++): Deleted.
+ (JSC::B3::Procedure::iterator::operator==): Deleted.
+ (JSC::B3::Procedure::iterator::operator!=): Deleted.
+ (JSC::B3::Procedure::iterator::findNext): Deleted.
+ * b3/B3ReduceDoubleToFloat.cpp:
+ * b3/B3ReduceStrength.cpp:
+ * b3/B3SSACalculator.h:
+ * b3/B3UseCounts.h:
+ * b3/air/AirCode.h:
+ * b3/air/AirEliminateDeadCode.cpp:
+ * b3/air/AirFixObviousSpills.cpp:
+ * b3/air/AirFixPartialRegisterStalls.cpp:
+ * b3/air/AirGenerate.cpp:
+ * b3/air/AirGenerationContext.h:
+ * b3/air/AirLiveness.h:
+ * b3/air/AirSpillEverything.cpp:
+
2016-08-24 Filip Pizlo <[email protected]>
Unreviewed, roll out r204901, r204897, r204866, r204856, r204854.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (204919 => 204920)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-08-24 19:35:41 UTC (rev 204920)
@@ -786,8 +786,6 @@
0FEC85181BDACDAC0080FF74 /* B3Generate.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC84CE1BDACDAC0080FF74 /* B3Generate.cpp */; };
0FEC85191BDACDAC0080FF74 /* B3Generate.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84CF1BDACDAC0080FF74 /* B3Generate.h */; };
0FEC851A1BDACDAC0080FF74 /* B3GenericFrequentedBlock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */; };
- 0FEC851B1BDACDAC0080FF74 /* B3IndexMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84D11BDACDAC0080FF74 /* B3IndexMap.h */; };
- 0FEC851C1BDACDAC0080FF74 /* B3IndexSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84D21BDACDAC0080FF74 /* B3IndexSet.h */; };
0FEC851D1BDACDAC0080FF74 /* B3LowerToAir.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC84D31BDACDAC0080FF74 /* B3LowerToAir.cpp */; };
0FEC851E1BDACDAC0080FF74 /* B3LowerToAir.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84D41BDACDAC0080FF74 /* B3LowerToAir.h */; };
0FEC851F1BDACDAC0080FF74 /* B3MemoryValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEC84D51BDACDAC0080FF74 /* B3MemoryValue.cpp */; };
@@ -3013,8 +3011,6 @@
0FEC84CE1BDACDAC0080FF74 /* B3Generate.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3Generate.cpp; path = b3/B3Generate.cpp; sourceTree = "<group>"; };
0FEC84CF1BDACDAC0080FF74 /* B3Generate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Generate.h; path = b3/B3Generate.h; sourceTree = "<group>"; };
0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3GenericFrequentedBlock.h; path = b3/B3GenericFrequentedBlock.h; sourceTree = "<group>"; };
- 0FEC84D11BDACDAC0080FF74 /* B3IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3IndexMap.h; path = b3/B3IndexMap.h; sourceTree = "<group>"; };
- 0FEC84D21BDACDAC0080FF74 /* B3IndexSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3IndexSet.h; path = b3/B3IndexSet.h; sourceTree = "<group>"; };
0FEC84D31BDACDAC0080FF74 /* B3LowerToAir.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3LowerToAir.cpp; path = b3/B3LowerToAir.cpp; sourceTree = "<group>"; };
0FEC84D41BDACDAC0080FF74 /* B3LowerToAir.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3LowerToAir.h; path = b3/B3LowerToAir.h; sourceTree = "<group>"; };
0FEC84D51BDACDAC0080FF74 /* B3MemoryValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3MemoryValue.cpp; path = b3/B3MemoryValue.cpp; sourceTree = "<group>"; };
@@ -4812,8 +4808,6 @@
0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */,
0FEC85BF1BE167A00080FF74 /* B3HeapRange.cpp */,
0FEC85C01BE167A00080FF74 /* B3HeapRange.h */,
- 0FEC84D11BDACDAC0080FF74 /* B3IndexMap.h */,
- 0FEC84D21BDACDAC0080FF74 /* B3IndexSet.h */,
DC69B99A1D15F90F002E3C00 /* B3InferSwitches.cpp */,
DC69B99B1D15F90F002E3C00 /* B3InferSwitches.h */,
0FEC85B41BE1462F0080FF74 /* B3InsertionSet.cpp */,
@@ -7177,8 +7171,6 @@
0FEC85C31BE167A00080FF74 /* B3HeapRange.h in Headers */,
26718BA51BE99F780052017B /* AirIteratedRegisterCoalescing.h in Headers */,
0F96303C1D4192CD005609D9 /* DestructionMode.h in Headers */,
- 0FEC851B1BDACDAC0080FF74 /* B3IndexMap.h in Headers */,
- 0FEC851C1BDACDAC0080FF74 /* B3IndexSet.h in Headers */,
0FEC85BA1BE1462F0080FF74 /* B3InsertionSet.h in Headers */,
0FEC85BB1BE1462F0080FF74 /* B3InsertionSetInlines.h in Headers */,
0FEC851E1BDACDAC0080FF74 /* B3LowerToAir.h in Headers */,
Modified: trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3BasicBlockUtils.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -28,8 +28,8 @@
#if ENABLE(B3_JIT)
-#include "B3IndexSet.h"
#include <wtf/GraphNodeWorklist.h>
+#include <wtf/IndexSet.h>
#include <wtf/Vector.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3BlockWorklist.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3BlockWorklist.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3BlockWorklist.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -28,13 +28,14 @@
#if ENABLE(B3_JIT)
-#include "B3BasicBlock.h"
-#include "B3IndexSet.h"
#include <wtf/GraphNodeWorklist.h>
+#include <wtf/IndexSet.h>
#include <wtf/Vector.h>
namespace JSC { namespace B3 {
+class BasicBlock;
+
typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist;
// When you say BlockWith<int> you should read it as "block with an int".
Modified: trunk/Source/_javascript_Core/b3/B3CFG.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3CFG.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3CFG.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -29,9 +29,9 @@
#if ENABLE(B3_JIT)
#include "B3BasicBlock.h"
-#include "B3IndexMap.h"
-#include "B3IndexSet.h"
#include "B3Procedure.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3DuplicateTails.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3DuplicateTails.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3DuplicateTails.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -32,7 +32,6 @@
#include "B3BreakCriticalEdges.h"
#include "B3Dominators.h"
#include "B3FixSSA.h"
-#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
@@ -39,6 +38,7 @@
#include "B3SwitchValue.h"
#include "B3UpsilonValue.h"
#include "B3ValueInlines.h"
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -31,7 +31,6 @@
#include "B3BasicBlockInlines.h"
#include "B3BreakCriticalEdges.h"
#include "B3Dominators.h"
-#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3ProcedureInlines.h"
@@ -41,6 +40,7 @@
#include "B3Variable.h"
#include "B3VariableValue.h"
#include <wtf/CommaPrinter.h>
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3FixSSA.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3FixSSA.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3FixSSA.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -28,8 +28,9 @@
#if ENABLE(B3_JIT)
-#include "B3IndexSet.h"
#include "B3Value.h"
+#include <wtf/IndexSet.h>
+#include <wtf/Vector.h>
namespace JSC { namespace B3 {
Deleted: trunk/Source/_javascript_Core/b3/B3IndexMap.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3IndexMap.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3IndexMap.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -1,87 +0,0 @@
-/*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
- *
- * 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.
- */
-
-#ifndef B3IndexMap_h
-#define B3IndexMap_h
-
-#if ENABLE(B3_JIT)
-
-#include <wtf/Vector.h>
-
-namespace JSC { namespace B3 {
-
-// This is a map for keys that have an index(). It's super efficient for BasicBlocks. It's only
-// efficient for Values if you don't create too many of these maps, since Values can have very
-// sparse indices and there are a lot of Values.
-
-template<typename Key, typename Value>
-class IndexMap {
-public:
- explicit IndexMap(size_t size = 0)
- {
- m_vector.fill(Value(), size);
- }
-
- void resize(size_t size)
- {
- m_vector.fill(Value(), size);
- }
-
- void clear()
- {
- m_vector.fill(Value(), m_vector.size());
- }
-
- size_t size() const { return m_vector.size(); }
-
- Value& operator[](size_t index)
- {
- return m_vector[index];
- }
-
- const Value& operator[](size_t index) const
- {
- return m_vector[index];
- }
-
- Value& operator[](Key* key)
- {
- return m_vector[key->index()];
- }
-
- const Value& operator[](Key* key) const
- {
- return m_vector[key->index()];
- }
-
-private:
- Vector<Value> m_vector;
-};
-
-} } // namespace JSC::B3
-
-#endif // ENABLE(B3_JIT)
-
-#endif // B3IndexMap_h
Deleted: trunk/Source/_javascript_Core/b3/B3IndexSet.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3IndexSet.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3IndexSet.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -1,165 +0,0 @@
-/*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
- *
- * 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.
- */
-
-#ifndef B3IndexSet_h
-#define B3IndexSet_h
-
-#include <wtf/BitVector.h>
-#include <wtf/CommaPrinter.h>
-
-namespace JSC { namespace B3 {
-
-// This is a set for things that have an index(). It's super efficient for BasicBlocks. It's only
-// efficient for Values if you don't create too many of these sets, since Values can have very sparse
-// indices and there are a lot of Values.
-
-// If you want a set of BasicBlocks, you do IndexSet<BasicBlock>. So, T = BasicBlock.
-template<typename T>
-class IndexSet {
-public:
- IndexSet()
- {
- }
-
- bool add(T* value)
- {
- return !m_set.set(value->index());
- }
-
- template<typename Iterable>
- bool addAll(const Iterable& iterable)
- {
- bool result = false;
- for (T* value : iterable)
- result |= add(value);
- return result;
- }
-
- bool remove(T* value)
- {
- return m_set.clear(value->index());
- }
-
- bool contains(T* value) const
- {
- if (!value)
- return false;
- return m_set.get(value->index());
- }
-
- size_t size() const
- {
- return m_set.bitCount();
- }
-
- bool isEmpty() const
- {
- return !size();
- }
-
- template<typename CollectionType>
- class Iterable {
- public:
- Iterable(const CollectionType& collection, const BitVector& set)
- : m_collection(collection)
- , m_set(set)
- {
- }
-
- class iterator {
- public:
- iterator()
- : m_collection(nullptr)
- {
- }
-
- iterator(const CollectionType& collection, BitVector::iterator iter)
- : m_collection(&collection)
- , m_iter(iter)
- {
- }
-
- T* operator*()
- {
- return m_collection->at(*m_iter);
- }
-
- iterator& operator++()
- {
- ++m_iter;
- return *this;
- }
-
- bool operator==(const iterator& other) const
- {
- return m_iter == other.m_iter;
- }
-
- bool operator!=(const iterator& other) const
- {
- return !(*this == other);
- }
-
- private:
- const CollectionType* m_collection;
- BitVector::iterator m_iter;
- };
-
- iterator begin() const { return iterator(m_collection, m_set.begin()); }
- iterator end() const { return iterator(m_collection, m_set.end()); }
-
- private:
- const CollectionType& m_collection;
- const BitVector& m_set;
- };
-
- // For basic blocks, you do:
- // indexSet.values(procedure);
- //
- // For values, you do:
- // indexSet.values(procedure.values());
- template<typename CollectionType>
- Iterable<CollectionType> values(const CollectionType& collection) const
- {
- return Iterable<CollectionType>(collection, indices());
- }
-
- const BitVector& indices() const { return m_set; }
-
- void dump(PrintStream& out) const
- {
- CommaPrinter comma;
- for (size_t index : indices())
- out.print(comma, T::dumpPrefix, index);
- }
-
-private:
- BitVector m_set;
-};
-
-} } // namespace JSC::B3
-
-#endif // B3IndexSet_h
-
Modified: trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3LowerToAir.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -40,8 +40,6 @@
#include "B3CheckSpecial.h"
#include "B3Commutativity.h"
#include "B3Dominators.h"
-#include "B3IndexMap.h"
-#include "B3IndexSet.h"
#include "B3MemoryValue.h"
#include "B3PatchpointSpecial.h"
#include "B3PatchpointValue.h"
@@ -55,6 +53,8 @@
#include "B3ValueInlines.h"
#include "B3Variable.h"
#include "B3VariableValue.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
#include <wtf/ListDump.h>
#if COMPILER(GCC) && ASSERT_DISABLED
Modified: trunk/Source/_javascript_Core/b3/B3PhiChildren.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3PhiChildren.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3PhiChildren.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -28,10 +28,10 @@
#if ENABLE(B3_JIT)
-#include "B3IndexMap.h"
#include "B3Procedure.h"
#include "B3UpsilonValue.h"
#include <wtf/GraphNodeWorklist.h>
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3Procedure.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -40,6 +40,7 @@
#include <wtf/Bag.h>
#include <wtf/FastMalloc.h>
#include <wtf/HashSet.h>
+#include <wtf/IndexedContainerIterator.h>
#include <wtf/Noncopyable.h>
#include <wtf/PrintStream.h>
#include <wtf/SharedTask.h>
@@ -133,54 +134,8 @@
BasicBlock* at(unsigned index) const { return m_blocks[index].get(); }
BasicBlock* operator[](unsigned index) const { return at(index); }
- class iterator {
- public:
- iterator()
- : m_procedure(nullptr)
- , m_index(0)
- {
- }
+ typedef WTF::IndexedContainerIterator<Procedure> iterator;
- iterator(const Procedure& procedure, unsigned index)
- : m_procedure(&procedure)
- , m_index(findNext(index))
- {
- }
-
- BasicBlock* operator*()
- {
- return m_procedure->at(m_index);
- }
-
- iterator& operator++()
- {
- m_index = findNext(m_index + 1);
- return *this;
- }
-
- bool operator==(const iterator& other) const
- {
- ASSERT(m_procedure == other.m_procedure);
- return m_index == other.m_index;
- }
-
- bool operator!=(const iterator& other) const
- {
- return !(*this == other);
- }
-
- private:
- unsigned findNext(unsigned index)
- {
- while (index < m_procedure->size() && !m_procedure->at(index))
- index++;
- return index;
- }
-
- const Procedure* m_procedure;
- unsigned m_index;
- };
-
iterator begin() const { return iterator(*this, 0); }
iterator end() const { return iterator(*this, size()); }
Modified: trunk/Source/_javascript_Core/b3/B3ReduceDoubleToFloat.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3ReduceDoubleToFloat.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3ReduceDoubleToFloat.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -29,11 +29,11 @@
#if ENABLE(B3_JIT)
#include "B3BasicBlock.h"
-#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
#include "B3PhaseScope.h"
#include "B3UseCounts.h"
#include "B3ValueInlines.h"
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3ReduceStrength.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -32,7 +32,6 @@
#include "B3BlockInsertionSet.h"
#include "B3ComputeDivisionMagic.h"
#include "B3Dominators.h"
-#include "B3IndexSet.h"
#include "B3InsertionSetInlines.h"
#include "B3MemoryValue.h"
#include "B3PhaseScope.h"
@@ -48,6 +47,7 @@
#include "B3VariableValue.h"
#include <wtf/GraphNodeWorklist.h>
#include <wtf/HashMap.h>
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3SSACalculator.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3SSACalculator.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3SSACalculator.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -29,9 +29,9 @@
#if ENABLE(B3_JIT)
#include "B3Dominators.h"
-#include "B3IndexMap.h"
#include "B3ProcedureInlines.h"
#include <wtf/Bag.h>
+#include <wtf/IndexMap.h>
#include <wtf/SegmentedVector.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/B3UseCounts.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/B3UseCounts.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/B3UseCounts.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -28,8 +28,8 @@
#if ENABLE(B3_JIT)
-#include "B3IndexMap.h"
#include "B3Value.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/air/AirCode.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirCode.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirCode.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -33,11 +33,11 @@
#include "AirSpecial.h"
#include "AirStackSlot.h"
#include "AirTmp.h"
-#include "B3IndexMap.h"
#include "B3SparseCollection.h"
#include "CCallHelpers.h"
#include "RegisterAtOffsetList.h"
#include "StackAlignment.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 {
Modified: trunk/Source/_javascript_Core/b3/air/AirEliminateDeadCode.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirEliminateDeadCode.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirEliminateDeadCode.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -31,7 +31,7 @@
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirPhaseScope.h"
-#include "B3IndexSet.h"
+#include <wtf/IndexSet.h>
namespace JSC { namespace B3 { namespace Air {
Modified: trunk/Source/_javascript_Core/b3/air/AirFixObviousSpills.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirFixObviousSpills.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirFixObviousSpills.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -32,7 +32,7 @@
#include "AirCode.h"
#include "AirInstInlines.h"
#include "AirPhaseScope.h"
-#include "B3IndexMap.h"
+#include <wtf/IndexMap.h>
#include <wtf/ListDump.h>
namespace JSC { namespace B3 { namespace Air {
Modified: trunk/Source/_javascript_Core/b3/air/AirFixPartialRegisterStalls.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirFixPartialRegisterStalls.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirFixPartialRegisterStalls.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -34,9 +34,9 @@
#include "AirInst.h"
#include "AirInstInlines.h"
#include "AirPhaseScope.h"
-#include "B3IndexMap.h"
-#include "B3IndexSet.h"
#include "MacroAssembler.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
#include <wtf/Vector.h>
namespace JSC { namespace B3 { namespace Air {
Modified: trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -48,7 +48,6 @@
#include "AirSpillEverything.h"
#include "AirValidate.h"
#include "B3Common.h"
-#include "B3IndexMap.h"
#include "B3Procedure.h"
#include "B3TimingScope.h"
#include "B3ValueInlines.h"
@@ -55,6 +54,7 @@
#include "CCallHelpers.h"
#include "DisallowMacroScratchRegisterUsage.h"
#include "LinkBuffer.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 { namespace Air {
Modified: trunk/Source/_javascript_Core/b3/air/AirGenerationContext.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirGenerationContext.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirGenerationContext.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -29,9 +29,9 @@
#if ENABLE(B3_JIT)
#include "AirBasicBlock.h"
-#include "B3IndexMap.h"
#include "CCallHelpers.h"
#include <wtf/Box.h>
+#include <wtf/IndexMap.h>
#include <wtf/SharedTask.h>
#include <wtf/Vector.h>
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -33,8 +33,8 @@
#include "AirInstInlines.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
-#include "B3IndexMap.h"
-#include "B3IndexSet.h"
+#include <wtf/IndexMap.h>
+#include <wtf/IndexSet.h>
#include <wtf/IndexSparseSet.h>
#include <wtf/ListDump.h>
Modified: trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp (204919 => 204920)
--- trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/_javascript_Core/b3/air/AirSpillEverything.cpp 2016-08-24 19:35:41 UTC (rev 204920)
@@ -35,7 +35,7 @@
#include "AirLiveness.h"
#include "AirPhaseScope.h"
#include "AirRegisterPriority.h"
-#include "B3IndexMap.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 { namespace Air {
Modified: trunk/Source/WTF/ChangeLog (204919 => 204920)
--- trunk/Source/WTF/ChangeLog 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/WTF/ChangeLog 2016-08-24 19:35:41 UTC (rev 204920)
@@ -1,3 +1,46 @@
+2016-08-24 Yusuke Suzuki <[email protected]>
+
+ [JSC] Move generic data structures out of B3
+ https://bugs.webkit.org/show_bug.cgi?id=161155
+
+ Reviewed by Saam Barati.
+
+ Add IndexSet, IndexMap, and IndexedContainerIterator.
+
+ * WTF.xcodeproj/project.pbxproj:
+ * wtf/CMakeLists.txt:
+ * wtf/IndexMap.h: Copied from Source/_javascript_Core/b3/B3IndexMap.h.
+ (WTF::IndexMap::IndexMap):
+ (WTF::IndexMap::resize):
+ (WTF::IndexMap::clear):
+ (WTF::IndexMap::size):
+ (WTF::IndexMap::operator[]):
+ * wtf/IndexSet.h: Renamed from Source/_javascript_Core/b3/B3IndexSet.h.
+ (WTF::IndexSet::IndexSet):
+ (WTF::IndexSet::add):
+ (WTF::IndexSet::addAll):
+ (WTF::IndexSet::remove):
+ (WTF::IndexSet::contains):
+ (WTF::IndexSet::size):
+ (WTF::IndexSet::isEmpty):
+ (WTF::IndexSet::Iterable::Iterable):
+ (WTF::IndexSet::Iterable::iterator::iterator):
+ (WTF::IndexSet::Iterable::iterator::operator*):
+ (WTF::IndexSet::Iterable::iterator::operator++):
+ (WTF::IndexSet::Iterable::iterator::operator==):
+ (WTF::IndexSet::Iterable::iterator::operator!=):
+ (WTF::IndexSet::Iterable::begin):
+ (WTF::IndexSet::Iterable::end):
+ (WTF::IndexSet::values):
+ (WTF::IndexSet::indices):
+ (WTF::IndexSet::dump):
+ * wtf/IndexedContainerIterator.h: Renamed from Source/_javascript_Core/b3/B3IndexMap.h.
+ (WTF::IndexedContainerIterator::IndexedContainerIterator):
+ (WTF::IndexedContainerIterator::operator++):
+ (WTF::IndexedContainerIterator::operator==):
+ (WTF::IndexedContainerIterator::operator!=):
+ (WTF::IndexedContainerIterator::findNext):
+
2016-08-24 Andreas Kling <[email protected]>
Add WTF::isFastMallocEnabled().
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (204919 => 204920)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2016-08-24 19:35:41 UTC (rev 204920)
@@ -336,6 +336,9 @@
FE8925B01D00DAEC0046907E /* Indenter.h in Headers */ = {isa = PBXBuildFile; fileRef = FE8925AF1D00DAEC0046907E /* Indenter.h */; };
FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEDACD3B1630F83F00C69634 /* StackStats.cpp */; };
FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */ = {isa = PBXBuildFile; fileRef = FEDACD3C1630F83F00C69634 /* StackStats.h */; };
+ C8B0E1A1E01A486EB95E0D11 /* IndexSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */; };
+ C916B975F02F4F7E8B4AB12D /* IndexMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 5B43383A5D0B463C9433D933 /* IndexMap.h */; };
+ 4B2680DD9B974402899ED572 /* IndexedContainerIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 9C67C542589348E285B49699 /* IndexedContainerIterator.h */; };
/* End PBXBuildFile section */
/* Begin PBXContainerItemProxy section */
@@ -684,6 +687,9 @@
FE8925AF1D00DAEC0046907E /* Indenter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Indenter.h; sourceTree = "<group>"; };
FEDACD3B1630F83F00C69634 /* StackStats.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StackStats.cpp; sourceTree = "<group>"; };
FEDACD3C1630F83F00C69634 /* StackStats.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StackStats.h; sourceTree = "<group>"; };
+ 3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexSet.h; path = IndexSet.h; sourceTree = "<group>"; };
+ 5B43383A5D0B463C9433D933 /* IndexMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexMap.h; path = IndexMap.h; sourceTree = "<group>"; };
+ 9C67C542589348E285B49699 /* IndexedContainerIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = IndexedContainerIterator.h; path = IndexedContainerIterator.h; sourceTree = "<group>"; };
/* End PBXFileReference section */
/* Begin PBXFrameworksBuildPhase section */
@@ -1044,6 +1050,9 @@
E4A0AD381A96245500536DF6 /* WorkQueue.h */,
A8A4737A151A825B004123FF /* WTFThreadData.cpp */,
A8A4737B151A825B004123FF /* WTFThreadData.h */,
+ 3137E1D7DBD84AC38FAE4D34 /* IndexSet.h */,
+ 5B43383A5D0B463C9433D933 /* IndexMap.h */,
+ 9C67C542589348E285B49699 /* IndexedContainerIterator.h */,
);
path = wtf;
sourceTree = "<group>";
@@ -1443,6 +1452,9 @@
A8A47446151A825B004123FF /* WTFString.h in Headers */,
A8A47487151A825B004123FF /* WTFThreadData.h in Headers */,
CE73E02519DCB7AB00580D5C /* XPCSPI.h in Headers */,
+ C8B0E1A1E01A486EB95E0D11 /* IndexSet.h in Headers */,
+ C916B975F02F4F7E8B4AB12D /* IndexMap.h in Headers */,
+ 4B2680DD9B974402899ED572 /* IndexedContainerIterator.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (204919 => 204920)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2016-08-24 19:29:52 UTC (rev 204919)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2016-08-24 19:35:41 UTC (rev 204920)
@@ -45,6 +45,10 @@
HashTable.h
HashTraits.h
HexNumber.h
+ IndexMap.h
+ IndexSet.h
+ IndexSparseSet.h
+ IndexedContainerIterator.h
IteratorAdaptors.h
IteratorRange.h
ListHashSet.h
Copied: trunk/Source/WTF/wtf/IndexMap.h (from rev 204919, trunk/Source/_javascript_Core/b3/B3IndexMap.h) (0 => 204920)
--- trunk/Source/WTF/wtf/IndexMap.h (rev 0)
+++ trunk/Source/WTF/wtf/IndexMap.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <wtf/Vector.h>
+
+namespace WTF {
+
+// This is a map for keys that have an index(). It's super efficient for BasicBlocks. It's only
+// efficient for Values if you don't create too many of these maps, since Values can have very
+// sparse indices and there are a lot of Values.
+
+template<typename Key, typename Value>
+class IndexMap {
+public:
+ explicit IndexMap(size_t size = 0)
+ {
+ m_vector.fill(Value(), size);
+ }
+
+ void resize(size_t size)
+ {
+ m_vector.fill(Value(), size);
+ }
+
+ void clear()
+ {
+ m_vector.fill(Value(), m_vector.size());
+ }
+
+ size_t size() const { return m_vector.size(); }
+
+ Value& operator[](size_t index)
+ {
+ return m_vector[index];
+ }
+
+ const Value& operator[](size_t index) const
+ {
+ return m_vector[index];
+ }
+
+ Value& operator[](Key* key)
+ {
+ return m_vector[key->index()];
+ }
+
+ const Value& operator[](Key* key) const
+ {
+ return m_vector[key->index()];
+ }
+
+private:
+ Vector<Value> m_vector;
+};
+
+} // namespace WTF
+
+using WTF::IndexMap;
Copied: trunk/Source/WTF/wtf/IndexSet.h (from rev 204919, trunk/Source/_javascript_Core/b3/B3IndexSet.h) (0 => 204920)
--- trunk/Source/WTF/wtf/IndexSet.h (rev 0)
+++ trunk/Source/WTF/wtf/IndexSet.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -0,0 +1,163 @@
+/*
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <wtf/BitVector.h>
+#include <wtf/CommaPrinter.h>
+
+namespace WTF {
+
+// This is a set for things that have an index(). It's super efficient for BasicBlocks. It's only
+// efficient for Values if you don't create too many of these sets, since Values can have very sparse
+// indices and there are a lot of Values.
+
+// If you want a set of BasicBlocks, you do IndexSet<BasicBlock>. So, T = BasicBlock.
+template<typename T>
+class IndexSet {
+public:
+ IndexSet()
+ {
+ }
+
+ bool add(T* value)
+ {
+ return !m_set.set(value->index());
+ }
+
+ template<typename Iterable>
+ bool addAll(const Iterable& iterable)
+ {
+ bool result = false;
+ for (T* value : iterable)
+ result |= add(value);
+ return result;
+ }
+
+ bool remove(T* value)
+ {
+ return m_set.clear(value->index());
+ }
+
+ bool contains(T* value) const
+ {
+ if (!value)
+ return false;
+ return m_set.get(value->index());
+ }
+
+ size_t size() const
+ {
+ return m_set.bitCount();
+ }
+
+ bool isEmpty() const
+ {
+ return !size();
+ }
+
+ template<typename CollectionType>
+ class Iterable {
+ public:
+ Iterable(const CollectionType& collection, const BitVector& set)
+ : m_collection(collection)
+ , m_set(set)
+ {
+ }
+
+ class iterator {
+ public:
+ iterator()
+ : m_collection(nullptr)
+ {
+ }
+
+ iterator(const CollectionType& collection, BitVector::iterator iter)
+ : m_collection(&collection)
+ , m_iter(iter)
+ {
+ }
+
+ T* operator*()
+ {
+ return m_collection->at(*m_iter);
+ }
+
+ iterator& operator++()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const
+ {
+ return m_iter == other.m_iter;
+ }
+
+ bool operator!=(const iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ const CollectionType* m_collection;
+ BitVector::iterator m_iter;
+ };
+
+ iterator begin() const { return iterator(m_collection, m_set.begin()); }
+ iterator end() const { return iterator(m_collection, m_set.end()); }
+
+ private:
+ const CollectionType& m_collection;
+ const BitVector& m_set;
+ };
+
+ // For basic blocks, you do:
+ // indexSet.values(procedure);
+ //
+ // For values, you do:
+ // indexSet.values(procedure.values());
+ template<typename CollectionType>
+ Iterable<CollectionType> values(const CollectionType& collection) const
+ {
+ return Iterable<CollectionType>(collection, indices());
+ }
+
+ const BitVector& indices() const { return m_set; }
+
+ void dump(PrintStream& out) const
+ {
+ CommaPrinter comma;
+ for (size_t index : indices())
+ out.print(comma, T::dumpPrefix, index);
+ }
+
+private:
+ BitVector m_set;
+};
+
+} // namespace WTF
+
+using WTF::IndexSet;
Copied: trunk/Source/WTF/wtf/IndexedContainerIterator.h (from rev 204919, trunk/Source/_javascript_Core/b3/B3IndexMap.h) (0 => 204920)
--- trunk/Source/WTF/wtf/IndexedContainerIterator.h (rev 0)
+++ trunk/Source/WTF/wtf/IndexedContainerIterator.h 2016-08-24 19:35:41 UTC (rev 204920)
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <type_traits>
+
+namespace WTF {
+
+template<class Container>
+class IndexedContainerIterator {
+public:
+ IndexedContainerIterator()
+ : m_container(nullptr)
+ , m_index(0)
+ {
+ }
+
+ IndexedContainerIterator(const Container& container, unsigned index)
+ : m_container(&container)
+ , m_index(findNext(index))
+ {
+ }
+
+ auto operator*() -> typename std::result_of<decltype(&Container::at)(const Container, unsigned)>::type
+ {
+ return m_container->at(m_index);
+ }
+
+ IndexedContainerIterator& operator++()
+ {
+ m_index = findNext(m_index + 1);
+ return *this;
+ }
+
+ bool operator==(const IndexedContainerIterator& other) const
+ {
+ ASSERT(m_container == other.m_container);
+ return m_index == other.m_index;
+ }
+
+ bool operator!=(const IndexedContainerIterator& other) const
+ {
+ return !(*this == other);
+ }
+
+private:
+ unsigned findNext(unsigned index)
+ {
+ while (index < m_container->size() && !m_container->at(index))
+ index++;
+ return index;
+ }
+
+ const Container* m_container;
+ unsigned m_index;
+};
+
+} // namespace WTF
