2011-06-09 Geoffrey Garen <ggaren@apple.com>
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 10 Jun 2011 00:02:23 +0000 (00:02 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 10 Jun 2011 00:02:23 +0000 (00:02 +0000)
        Reviewed by Oliver Hunt.

        Factored MarkedBlock set management into a helper class with a fast case Bloom filter
        https://bugs.webkit.org/show_bug.cgi?id=62413

        SunSpider reports a small speedup.

        This is in preparation for having ConservativeSet operate on arbitrary
        sets of MarkedBlocks, and in preparation for conservative scanning
        becoming proportionally more important than other GC activities.

        * GNUmakefile.list.am:
        * JavaScriptCore.gypi:
        * JavaScriptCore.xcodeproj/project.pbxproj: Build-o.

        * heap/ConservativeRoots.cpp:
        (JSC::ConservativeRoots::add):
        * heap/ConservativeRoots.h:
        (JSC::ConservativeRoots::ConservativeRoots): Operate on a MarkedBlockSet
        directly, instead of a Heap, so we can operate on subsets of the Heap
        instead.

        Use a TinyBloomFilter for single-cycle exclusion of most pointers. This
        is particularly important since we expect not to find our subject pointer
        in the MarkedBlock hash, and hash misses are more expensive than typical
        hash lookups because they have high collision rates.

        No need for single-pointer add() to be public anymore, since nobody uses it.

        * heap/Heap.cpp:
        (JSC::Heap::markRoots):
        * heap/Heap.h:
        (JSC::Heap::forEachCell):
        (JSC::Heap::forEachBlock): Use MarkedBlockSet since that's what
        ConservativeRoots relies on.

        Nixed contains(), since nobody uses it anymore.

        * heap/MarkedBlock.h:
        (WTF::MarkedBlockHash::hash): Added a faster hash taking advantage of
        the VM layout properties of MarkedBlocks.

        * heap/MarkedBlockSet.h: Added.
        (JSC::MarkedBlockSet::add):
        (JSC::MarkedBlockSet::remove):
        (JSC::MarkedBlockSet::recomputeFilter):
        (JSC::MarkedBlockSet::filter):
        (JSC::MarkedBlockSet::set):
        * heap/TinyBloomFilter.h: Added.
        (JSC::TinyBloomFilter::TinyBloomFilter):
        (JSC::TinyBloomFilter::add):
        (JSC::TinyBloomFilter::ruleOut): New helper class, used above.

        * interpreter/RegisterFile.cpp:
        (JSC::RegisterFile::gatherConservativeRoots): No need to specifically
        exclude values by tag -- the tiny bloom filter is already a register-register
        compare, so adding another "rule out" factor just slows things down.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@88504 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/GNUmakefile.list.am
Source/JavaScriptCore/JavaScriptCore.gypi
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/heap/ConservativeRoots.cpp
Source/JavaScriptCore/heap/ConservativeRoots.h
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/Heap.h
Source/JavaScriptCore/heap/MarkedBlock.h
Source/JavaScriptCore/heap/MarkedBlockSet.h [new file with mode: 0644]
Source/JavaScriptCore/heap/TinyBloomFilter.h [new file with mode: 0644]
Source/JavaScriptCore/interpreter/RegisterFile.cpp

index 730c03b..cea079e 100644 (file)
@@ -1,3 +1,63 @@
+2011-06-09  Geoffrey Garen  <ggaren@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        Factored MarkedBlock set management into a helper class with a fast case Bloom filter
+        https://bugs.webkit.org/show_bug.cgi?id=62413
+        
+        SunSpider reports a small speedup.
+        
+        This is in preparation for having ConservativeSet operate on arbitrary
+        sets of MarkedBlocks, and in preparation for conservative scanning
+        becoming proportionally more important than other GC activities.
+
+        * GNUmakefile.list.am:
+        * JavaScriptCore.gypi:
+        * JavaScriptCore.xcodeproj/project.pbxproj: Build-o.
+
+        * heap/ConservativeRoots.cpp:
+        (JSC::ConservativeRoots::add):
+        * heap/ConservativeRoots.h:
+        (JSC::ConservativeRoots::ConservativeRoots): Operate on a MarkedBlockSet
+        directly, instead of a Heap, so we can operate on subsets of the Heap
+        instead.
+        
+        Use a TinyBloomFilter for single-cycle exclusion of most pointers. This
+        is particularly important since we expect not to find our subject pointer
+        in the MarkedBlock hash, and hash misses are more expensive than typical
+        hash lookups because they have high collision rates.
+        
+        No need for single-pointer add() to be public anymore, since nobody uses it.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::markRoots):
+        * heap/Heap.h:
+        (JSC::Heap::forEachCell):
+        (JSC::Heap::forEachBlock): Use MarkedBlockSet since that's what
+        ConservativeRoots relies on.
+        
+        Nixed contains(), since nobody uses it anymore.
+
+        * heap/MarkedBlock.h:
+        (WTF::MarkedBlockHash::hash): Added a faster hash taking advantage of
+        the VM layout properties of MarkedBlocks.
+
+        * heap/MarkedBlockSet.h: Added.
+        (JSC::MarkedBlockSet::add):
+        (JSC::MarkedBlockSet::remove):
+        (JSC::MarkedBlockSet::recomputeFilter):
+        (JSC::MarkedBlockSet::filter):
+        (JSC::MarkedBlockSet::set):
+        * heap/TinyBloomFilter.h: Added.
+        (JSC::TinyBloomFilter::TinyBloomFilter):
+        (JSC::TinyBloomFilter::add):
+        (JSC::TinyBloomFilter::ruleOut): New helper class, used above.
+
+        * interpreter/RegisterFile.cpp:
+        (JSC::RegisterFile::gatherConservativeRoots): No need to specifically
+        exclude values by tag -- the tiny bloom filter is already a register-register
+        compare, so adding another "rule out" factor just slows things down.
+
 2011-06-09  Gavin Barraclough  <barraclough@apple.com>
 
         Reviewed by Oliver Hunt.
index 5f95032..baa3ae2 100644 (file)
@@ -117,6 +117,8 @@ javascriptcore_sources += \
        Source/JavaScriptCore/heap/HeapRootVisitor.h \
        Source/JavaScriptCore/heap/MarkedBlock.cpp \
        Source/JavaScriptCore/heap/MarkedBlock.h \
+       Source/JavaScriptCore/heap/MarkedBlockSet.h \
+       Source/JavaScriptCore/heap/TinyBloomFilter.h \
        Source/JavaScriptCore/heap/NewSpace.cpp \
        Source/JavaScriptCore/heap/NewSpace.h \
        Source/JavaScriptCore/heap/Strong.h \
index 560221c..3435f3c 100644 (file)
             'heap/HeapRootVisitor.h',
             'heap/MarkedBlock.cpp',
             'heap/MarkedBlock.h',
+            'heap/MarkedBlockSet.h',
+            'heap/TinyBloomFilter.h',
             'heap/NewSpace.cpp',
             'heap/NewSpace.h',
             'debugger/Debugger.cpp',
index 3f2022d..cb44efa 100644 (file)
@@ -57,6 +57,8 @@
                140D17D70E8AD4A9000CD17D /* JSBasePrivate.h in Headers */ = {isa = PBXBuildFile; fileRef = 140D17D60E8AD4A9000CD17D /* JSBasePrivate.h */; settings = {ATTRIBUTES = (Private, ); }; };
                141211310A48794D00480255 /* JavaScriptCore.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 932F5BD90822A1C700736975 /* JavaScriptCore.framework */; };
                141211340A48795800480255 /* minidom.c in Sources */ = {isa = PBXBuildFile; fileRef = 141211020A48780900480255 /* minidom.c */; };
+               141448CB13A176EC00F5BA1A /* MarkedBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 141448CA13A176EC00F5BA1A /* MarkedBlockSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */ = {isa = PBXBuildFile; fileRef = 141448CC13A1783700F5BA1A /* TinyBloomFilter.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1420BE7B10AA6DDB00F455D2 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 1420BE7A10AA6DDB00F455D2 /* WeakRandom.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1421359B0A677F4F00A8195E /* JSBase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1421359A0A677F4F00A8195E /* JSBase.cpp */; };
                14280823107EC02C0013E7B2 /* Debugger.cpp in Sources */ = {isa = PBXBuildFile; fileRef = F692A8580255597D01FF60F7 /* Debugger.cpp */; };
                141211020A48780900480255 /* minidom.c */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.c; name = minidom.c; path = tests/minidom.c; sourceTree = "<group>"; };
                1412110D0A48788700480255 /* minidom.js */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.javascript; name = minidom.js; path = tests/minidom.js; sourceTree = "<group>"; };
                141211200A48793C00480255 /* minidom */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.executable"; includeInIndex = 0; path = minidom; sourceTree = BUILT_PRODUCTS_DIR; };
+               141448CA13A176EC00F5BA1A /* MarkedBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MarkedBlockSet.h; sourceTree = "<group>"; };
+               141448CC13A1783700F5BA1A /* TinyBloomFilter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyBloomFilter.h; sourceTree = "<group>"; };
                1419D32C0CEA7CDE00FF507A /* RefCounted.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RefCounted.h; sourceTree = "<group>"; };
                1420BE7A10AA6DDB00F455D2 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
                1421359A0A677F4F00A8195E /* JSBase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSBase.cpp; sourceTree = "<group>"; };
                                14D2F3D9139F4BE200491031 /* NewSpace.h */,
                                142E3132134FF0A600AFADB5 /* Strong.h */,
                                142E3133134FF0A600AFADB5 /* Weak.h */,
+                               141448CA13A176EC00F5BA1A /* MarkedBlockSet.h */,
+                               141448CC13A1783700F5BA1A /* TinyBloomFilter.h */,
                        );
                        path = heap;
                        sourceTree = "<group>";
                                86BB09C1138E381B0056702F /* DFGRepatch.h in Headers */,
                                A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */,
                                14D2F3DB139F4BE200491031 /* NewSpace.h in Headers */,
+                               141448CB13A176EC00F5BA1A /* MarkedBlockSet.h in Headers */,
+                               141448CD13A1783700F5BA1A /* TinyBloomFilter.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
index 1aad779..33c695d 100644 (file)
@@ -44,6 +44,32 @@ void ConservativeRoots::grow()
     m_roots = newRoots;
 }
 
+inline void ConservativeRoots::add(void* p, TinyBloomFilter filter)
+{
+    MarkedBlock* candidate = MarkedBlock::blockFor(p);
+    if (filter.ruleOut(reinterpret_cast<Bits>(candidate))) {
+        ASSERT(!candidate || !m_blocks->set().contains(candidate));
+        return;
+    }
+
+    if (!MarkedBlock::isAtomAligned(p))
+        return;
+
+    if (!m_blocks->set().contains(candidate))
+        return;
+
+    // The conservative set inverts the typical meaning of mark bits: We only
+    // visit marked pointers, and our visit clears the mark bit. This efficiently
+    // sifts out pointers to dead objects and duplicate pointers.
+    if (!candidate->testAndClearMarked(p))
+        return;
+
+    if (m_size == m_capacity)
+        grow();
+
+    m_roots[m_size++] = static_cast<JSCell*>(p);
+}
+
 void ConservativeRoots::add(void* begin, void* end)
 {
     ASSERT(begin <= end);
@@ -51,8 +77,9 @@ void ConservativeRoots::add(void* begin, void* end)
     ASSERT(isPointerAligned(begin));
     ASSERT(isPointerAligned(end));
 
+    TinyBloomFilter filter = m_blocks->filter(); // Make a local copy of filter to show the compiler it won't alias, and can be register-allocated.
     for (char** it = static_cast<char**>(begin); it != static_cast<char**>(end); ++it)
-        add(*it);
+        add(*it, filter);
 }
 
 } // namespace JSC
index df45b79..e10050d 100644 (file)
@@ -37,10 +37,9 @@ class Heap;
 
 class ConservativeRoots {
 public:
-    ConservativeRoots(Heap*);
+    ConservativeRoots(const MarkedBlockSet*);
     ~ConservativeRoots();
 
-    void add(void*);
     void add(void* begin, void* end);
     
     size_t size();
@@ -50,20 +49,21 @@ private:
     static const size_t inlineCapacity = 128;
     static const size_t nonInlineCapacity = 8192 / sizeof(JSCell*);
     
+    void add(void*, TinyBloomFilter);
     void grow();
 
-    Heap* m_heap;
     JSCell** m_roots;
     size_t m_size;
     size_t m_capacity;
+    const MarkedBlockSet* m_blocks;
     JSCell* m_inlineRoots[inlineCapacity];
 };
 
-inline ConservativeRoots::ConservativeRoots(Heap* heap)
-    : m_heap(heap)
-    , m_roots(m_inlineRoots)
+inline ConservativeRoots::ConservativeRoots(const MarkedBlockSet* blocks)
+    : m_roots(m_inlineRoots)
     , m_size(0)
     , m_capacity(inlineCapacity)
+    , m_blocks(blocks)
 {
 }
 
@@ -73,23 +73,6 @@ inline ConservativeRoots::~ConservativeRoots()
         OSAllocator::decommitAndRelease(m_roots, m_capacity * sizeof(JSCell*));
 }
 
-inline void ConservativeRoots::add(void* p)
-{
-    if (!m_heap->contains(p))
-        return;
-
-    // The conservative set inverts the typical meaning of mark bits: We only
-    // visit marked pointers, and our visit clears the mark bit. This efficiently
-    // sifts out pointers to dead objects and duplicate pointers.
-    if (!m_heap->testAndClearMarked(p))
-        return;
-
-    if (m_size == m_capacity)
-        grow();
-
-    m_roots[m_size++] = static_cast<JSCell*>(p);
-}
-
 inline size_t ConservativeRoots::size()
 {
     return m_size;
index 1546c75..fe867ff 100644 (file)
@@ -404,19 +404,19 @@ void Heap::markRoots()
 
     void* dummy;
 
-    MarkStack& visitor = m_markStack;
-    HeapRootVisitor heapRootVisitor(visitor);
-
     // We gather conservative roots before clearing mark bits because conservative
     // gathering uses the mark bits to determine whether a reference is valid.
-    ConservativeRoots machineThreadRoots(this);
+    ConservativeRoots machineThreadRoots(&m_blocks);
     m_machineThreads.gatherConservativeRoots(machineThreadRoots, &dummy);
 
-    ConservativeRoots registerFileRoots(this);
+    ConservativeRoots registerFileRoots(&m_blocks);
     registerFile().gatherConservativeRoots(registerFileRoots);
 
     clearMarks();
 
+    MarkStack& visitor = m_markStack;
+    HeapRootVisitor heapRootVisitor(visitor);
+
     visitor.append(machineThreadRoots);
     visitor.drain();
 
index ed9715d..cf5ba44 100644 (file)
@@ -25,6 +25,7 @@
 #include "HandleHeap.h"
 #include "HandleStack.h"
 #include "MarkStack.h"
+#include "MarkedBlockSet.h"
 #include "NewSpace.h"
 #include <wtf/Forward.h>
 #include <wtf/HashCountedSet.h>
@@ -89,8 +90,6 @@ namespace JSC {
         void protect(JSValue);
         bool unprotect(JSValue); // True when the protect count drops to 0.
 
-        bool contains(const void*);
-
         size_t size();
         size_t capacity();
         size_t objectCount();
@@ -145,7 +144,7 @@ namespace JSC {
 
         OperationInProgress m_operationInProgress;
         NewSpace m_newSpace;
-        HashSet<MarkedBlock*> m_blocks;
+        MarkedBlockSet m_blocks;
 
         size_t m_extraCost;
 
@@ -208,18 +207,6 @@ namespace JSC {
     {
     }
 
-    inline bool Heap::contains(const void* x)
-    {
-        if (!MarkedBlock::isAtomAligned(x))
-            return false;
-
-        MarkedBlock* block = MarkedBlock::blockFor(x);
-        if (!block || !m_blocks.contains(block))
-            return false;
-            
-        return true;
-    }
-
     inline void Heap::reportExtraMemoryCost(size_t cost)
     {
         if (cost > minExtraCost) 
@@ -244,8 +231,8 @@ namespace JSC {
 
     template<typename Functor> inline typename Functor::ReturnType Heap::forEachCell(Functor& functor)
     {
-        BlockIterator end = m_blocks.end();
-        for (BlockIterator it = m_blocks.begin(); it != end; ++it)
+        BlockIterator end = m_blocks.set().end();
+        for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
             (*it)->forEachCell(functor);
         return functor.returnValue();
     }
@@ -258,8 +245,8 @@ namespace JSC {
 
     template<typename Functor> inline typename Functor::ReturnType Heap::forEachBlock(Functor& functor)
     {
-        BlockIterator end = m_blocks.end();
-        for (BlockIterator it = m_blocks.begin(); it != end; ++it)
+        BlockIterator end = m_blocks.set().end();
+        for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
             functor(*it);
         return functor.returnValue();
     }
index e104002..7653883 100644 (file)
@@ -24,6 +24,7 @@
 
 #include <wtf/Bitmap.h>
 #include <wtf/DoublyLinkedList.h>
+#include <wtf/HashFunctions.h>
 #include <wtf/PageAllocationAligned.h>
 #include <wtf/StdLibExtras.h>
 
@@ -47,6 +48,7 @@ namespace JSC {
         };
 
         static const size_t atomSize = sizeof(double); // Ensures natural alignment for all built-in types.
+        static const size_t blockSize = 16 * KB;
 
         static MarkedBlock* create(Heap*, size_t cellSize);
         static void destroy(MarkedBlock*);
@@ -80,7 +82,6 @@ namespace JSC {
         template <typename Functor> void forEachCell(Functor&);
 
     private:
-        static const size_t blockSize = 16 * KB;
         static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
 
         static const size_t atomMask = ~(atomSize - 1); // atomSize must be a power of two.
@@ -215,4 +216,22 @@ namespace JSC {
     
 } // namespace JSC
 
+namespace WTF {
+
+    struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
+        static unsigned hash(JSC::MarkedBlock* const& key)
+        {
+            // Aligned VM regions tend to be monotonically increasing integers,
+            // which is a great hash function, but we have to remove the low bits,
+            // since they're always zero, which is a terrible hash function!
+            return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
+        }
+    };
+
+    template<> struct DefaultHash<JSC::MarkedBlock*> {
+        typedef MarkedBlockHash Hash;
+    };
+
+} // namespace WTF
+
 #endif // MarkedBlock_h
diff --git a/Source/JavaScriptCore/heap/MarkedBlockSet.h b/Source/JavaScriptCore/heap/MarkedBlockSet.h
new file mode 100644 (file)
index 0000000..939575f
--- /dev/null
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2011 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. AND ITS CONTRIBUTORS ``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 ITS 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 MarkedBlockSet_h
+#define MarkedBlockSet_h
+
+#include "MarkedBlock.h"
+#include "TinyBloomFilter.h"
+
+namespace JSC {
+
+class MarkedBlock;
+
+class MarkedBlockSet {
+public:
+    void add(MarkedBlock*);
+    void remove(MarkedBlock*);
+
+    TinyBloomFilter filter() const;
+    const HashSet<MarkedBlock*>& set() const;
+
+private:
+    void recomputeFilter();
+
+    TinyBloomFilter m_filter;
+    HashSet<MarkedBlock*> m_set;
+};
+
+inline void MarkedBlockSet::add(MarkedBlock* block)
+{
+    m_filter.add(reinterpret_cast<Bits>(block));
+    m_set.add(block);
+}
+
+inline void MarkedBlockSet::remove(MarkedBlock* block)
+{
+    int oldCapacity = m_set.capacity();
+    m_set.remove(block);
+    if (m_set.capacity() != oldCapacity) // Indicates we've removed a lot of blocks.
+        recomputeFilter();
+}
+
+inline void MarkedBlockSet::recomputeFilter()
+{
+    TinyBloomFilter filter;
+    for (HashSet<MarkedBlock*>::iterator it = m_set.begin(); it != m_set.end(); ++it)
+        filter.add(reinterpret_cast<Bits>(*it));
+    m_filter = filter;
+}
+
+inline TinyBloomFilter MarkedBlockSet::filter() const
+{
+    return m_filter;
+}
+
+inline const HashSet<MarkedBlock*>& MarkedBlockSet::set() const
+{
+    return m_set;
+}
+
+} // namespace JSC
+
+#endif // MarkedBlockSet_h
diff --git a/Source/JavaScriptCore/heap/TinyBloomFilter.h b/Source/JavaScriptCore/heap/TinyBloomFilter.h
new file mode 100644 (file)
index 0000000..82b5863
--- /dev/null
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2011 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. AND ITS CONTRIBUTORS ``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 ITS 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 TinyBloomFilter_h
+#define TinyBloomFilter_h
+
+namespace JSC {
+
+typedef uintptr_t Bits;
+
+class TinyBloomFilter {
+public:
+    TinyBloomFilter();
+
+    void add(Bits);
+    bool ruleOut(Bits) const; // True for 0.
+
+private:
+    Bits m_bits;
+};
+
+inline TinyBloomFilter::TinyBloomFilter()
+    : m_bits(0)
+{
+}
+
+inline void TinyBloomFilter::add(Bits bits)
+{
+    m_bits |= bits;
+}
+
+inline bool TinyBloomFilter::ruleOut(Bits bits) const
+{
+    if (!bits)
+        return true;
+
+    if ((bits & m_bits) != bits)
+        return true;
+
+    return false;
+}
+
+} // namespace JSC
+
+#endif // TinyBloomFilter_h
index e3b34bb..3684903 100644 (file)
@@ -54,12 +54,7 @@ RegisterFile::~RegisterFile()
 
 void RegisterFile::gatherConservativeRoots(ConservativeRoots& conservativeRoots)
 {
-    for (Register* it = start(); it != end(); ++it) {
-        JSValue v = it->jsValue();
-        if (!v.isCell())
-            continue;
-        conservativeRoots.add(v.asCell());
-    }
+    conservativeRoots.add(start(), end());
 }
 
 void RegisterFile::releaseExcessCapacity()