[JSC] Make CSE's ImpureData faster when dealing with large blocks
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Mar 2016 04:06:59 +0000 (04:06 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Mar 2016 04:06:59 +0000 (04:06 +0000)
https://bugs.webkit.org/show_bug.cgi?id=155594

Patch by Benjamin Poulain <bpoulain@apple.com> on 2016-03-17
Reviewed by Filip Pizlo.

Source/JavaScriptCore:

In some tests with large blocks, the time spent in DFG's LocalCSE
can be over 10% of the total compile time.
In those cases, LocalCSE is completely dominated by handling large
blocks.

This patch addresses the most obvious hot spots ImpureData's handling.

Initially, most of the time was going into HashTable::rehash().
The reason is the buckets are <HeapLocation, LazyNode> gigantic.
The hash table would easily get into several kilobytes and the CPU
was spending more time dealing with memory than anything.

To solve that, I moved the pairs lazily to the heap. The table itself
just contains the unique_ptr to those values. This makes the table
reasonably small and the alloc/dealloc are paid for by the fast rehash().

Once addImpure() was better, the next big bottleneck was clobber().
For each clobber(), we need to go over the entire map and test each value.
That loop was where most of the time was going.

Most calls to clobber() come from two kinds: SideState and Stack.

SideState is easy: it is never def'ed so we can always skip it.

Stack is disjoint from Heap too so we can also put it separately.

Splitting the map into 2 helped reduce the overhead. The maps are:
-Stack
-Heap

Having Stack alone was not enough for many blocks. In some cases,
you have a ton of SetLocal/GetLocal and having Stack separately
makes no difference.

To solve that, I split Stack in two: a map addressed by AbstractHeap
+ unique HeapLocation and a fallback map for everything else.
Since most Stack are not TOP and are unique per AbstractHeap,
I get O(1) clobber in most cases.

I could achieve the same result with a custom hash structure.
I don't think it is worth the effort, in most cases, m_fallbackStackMap
has a size of zero or one.

This patch introduces a lot of coupling between CSE and AbstractHeap.
To reduce the risk of bugs, the old map is still maintained in debug
and each step checks that the results are the same as the new implementation.

A new validation step also verify the strong assumptions made by CSE:
-SideState and World are never def().
-We never write HEAP TOP, we only write specific heap location.

* dfg/DFGCSEPhase.cpp:
* dfg/DFGHeapLocation.h:
* dfg/DFGLazyNode.h:
(JSC::DFG::LazyNode::hash):

Source/WTF:

* wtf/HashSet.h:
(WTF::V>::removeIf):

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
Source/JavaScriptCore/dfg/DFGHeapLocation.h
Source/JavaScriptCore/dfg/DFGLazyNode.h
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/HashSet.h
Source/WTF/wtf/HashTraits.h

index 56b08b9..eb512b9 100644 (file)
@@ -1,3 +1,66 @@
+2016-03-17  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Make CSE's ImpureData faster when dealing with large blocks
+        https://bugs.webkit.org/show_bug.cgi?id=155594
+
+        Reviewed by Filip Pizlo.
+
+        In some tests with large blocks, the time spent in DFG's LocalCSE
+        can be over 10% of the total compile time.
+        In those cases, LocalCSE is completely dominated by handling large
+        blocks.
+
+        This patch addresses the most obvious hot spots ImpureData's handling.
+
+        Initially, most of the time was going into HashTable::rehash().
+        The reason is the buckets are <HeapLocation, LazyNode> gigantic.
+        The hash table would easily get into several kilobytes and the CPU
+        was spending more time dealing with memory than anything.
+
+        To solve that, I moved the pairs lazily to the heap. The table itself
+        just contains the unique_ptr to those values. This makes the table
+        reasonably small and the alloc/dealloc are paid for by the fast rehash().
+
+        Once addImpure() was better, the next big bottleneck was clobber().
+        For each clobber(), we need to go over the entire map and test each value.
+        That loop was where most of the time was going.
+
+        Most calls to clobber() come from two kinds: SideState and Stack.
+
+        SideState is easy: it is never def'ed so we can always skip it.
+
+        Stack is disjoint from Heap too so we can also put it separately.
+
+        Splitting the map into 2 helped reduce the overhead. The maps are:
+        -Stack
+        -Heap
+
+        Having Stack alone was not enough for many blocks. In some cases,
+        you have a ton of SetLocal/GetLocal and having Stack separately
+        makes no difference.
+
+        To solve that, I split Stack in two: a map addressed by AbstractHeap
+        + unique HeapLocation and a fallback map for everything else.
+        Since most Stack are not TOP and are unique per AbstractHeap,
+        I get O(1) clobber in most cases.
+
+        I could achieve the same result with a custom hash structure.
+        I don't think it is worth the effort, in most cases, m_fallbackStackMap
+        has a size of zero or one.
+
+        This patch introduces a lot of coupling between CSE and AbstractHeap.
+        To reduce the risk of bugs, the old map is still maintained in debug
+        and each step checks that the results are the same as the new implementation.
+
+        A new validation step also verify the strong assumptions made by CSE:
+        -SideState and World are never def().
+        -We never write HEAP TOP, we only write specific heap location.
+
+        * dfg/DFGCSEPhase.cpp:
+        * dfg/DFGHeapLocation.h:
+        * dfg/DFGLazyNode.h:
+        (JSC::DFG::LazyNode::hash):
+
 2016-03-17  Saam barati  <sbarati@apple.com>
 
         Implement SmallPtrSet and integrate it into the Parser
index b4ca774..4023f6b 100644 (file)
@@ -51,27 +51,230 @@ namespace {
 
 const bool verbose = false;
 
-class ClobberFilter {
+class ImpureDataSlot {
+    WTF_MAKE_NONCOPYABLE(ImpureDataSlot);
+    WTF_MAKE_FAST_ALLOCATED;
 public:
-    ClobberFilter(AbstractHeap heap)
-        : m_heap(heap)
+    HeapLocation key;
+    LazyNode value;
+    unsigned hash;
+};
+
+struct ImpureDataSlotHash : public DefaultHash<std::unique_ptr<ImpureDataSlot>>::Hash {
+    static unsigned hash(const std::unique_ptr<ImpureDataSlot>& key)
     {
+        return key->hash;
     }
-    
-    bool operator()(const ImpureMap::KeyValuePairType& pair) const
+
+    static bool equal(const std::unique_ptr<ImpureDataSlot>& a, const std::unique_ptr<ImpureDataSlot>& b)
     {
-        return m_heap.overlaps(pair.key.heap());
+        // The ImpureDataSlot are unique per table per HeapLocation. This lets us compare the key
+        // by just comparing the pointers of the unique ImpureDataSlots.
+        ASSERT(a != b || a->key == b->key);
+        return a == b;
     }
-    
-private:
-    AbstractHeap m_heap;
 };
 
-inline void clobber(ImpureMap& map, AbstractHeap heap)
-{
-    ClobberFilter filter(heap);
-    map.removeIf(filter);
-}
+struct ImpureDataTranslator {
+    static unsigned hash(const HeapLocation& key)
+    {
+        return key.hash();
+    }
+
+    static bool equal(const std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key)
+    {
+        if (!slot)
+            return false;
+        if (HashTraits<std::unique_ptr<ImpureDataSlot>>::isDeletedValue(slot))
+            return false;
+        return slot->key == key;
+    }
+
+    static void translate(std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key, unsigned hashCode)
+    {
+        new (NotNull, std::addressof(slot)) std::unique_ptr<ImpureDataSlot>(new ImpureDataSlot {key, LazyNode(), hashCode});
+    }
+};
+
+class ImpureMap {
+    WTF_MAKE_FAST_ALLOCATED;
+    WTF_MAKE_NONCOPYABLE(ImpureMap);
+public:
+    ImpureMap() = default;
+
+    ImpureMap(ImpureMap&& other)
+    {
+        m_heapMap.swap(other.m_heapMap);
+        m_abstractHeapStackMap.swap(other.m_abstractHeapStackMap);
+        m_fallbackStackMap.swap(other.m_fallbackStackMap);
+#if !defined(NDEBUG)
+        m_debugImpureData.swap(other.m_debugImpureData);
+#endif
+    }
+
+    const ImpureDataSlot* add(const HeapLocation& location, const LazyNode& node)
+    {
+        const ImpureDataSlot* result = addImpl(location, node);
+
+#if !defined(NDEBUG)
+        auto addResult = m_debugImpureData.add(location, node);
+        ASSERT(!!result == !addResult.isNewEntry);
+#endif
+        return result;
+    }
+
+    LazyNode get(const HeapLocation& location) const
+    {
+        LazyNode result = getImpl(location);
+#if !defined(NDEBUG)
+        ASSERT(result == m_debugImpureData.get(location));
+#endif
+        return result;
+    }
+
+    void clobber(AbstractHeap heap)
+    {
+        switch (heap.kind()) {
+        case World: {
+            clear();
+            break;
+        }
+        case SideState:
+            break;
+        case Stack: {
+            ASSERT(!heap.payload().isTop());
+            ASSERT(heap.payload().value() == heap.payload().value32());
+            m_abstractHeapStackMap.remove(heap.payload().value32());
+            clobber(m_fallbackStackMap, heap);
+            break;
+        }
+        default:
+            clobber(m_heapMap, heap);
+            break;
+        }
+#if !defined(NDEBUG)
+        m_debugImpureData.removeIf([heap](const HashMap<HeapLocation, LazyNode>::KeyValuePairType& pair) -> bool {
+            return heap.overlaps(pair.key.heap());
+        });
+        ASSERT(m_debugImpureData.size()
+            == (m_heapMap.size()
+                + m_abstractHeapStackMap.size()
+                + m_fallbackStackMap.size()));
+
+        const bool verifyClobber = false;
+        if (verifyClobber) {
+            for (auto& pair : m_debugImpureData)
+                ASSERT(!!get(pair.key));
+        }
+#endif
+    }
+
+    void clear()
+    {
+        m_heapMap.clear();
+        m_abstractHeapStackMap.clear();
+        m_fallbackStackMap.clear();
+#if !defined(NDEBUG)
+        m_debugImpureData.clear();
+#endif
+    }
+
+private:
+    typedef HashSet<std::unique_ptr<ImpureDataSlot>, ImpureDataSlotHash> Map;
+
+    const ImpureDataSlot* addImpl(const HeapLocation& location, const LazyNode& node)
+    {
+        switch (location.heap().kind()) {
+        case World:
+        case SideState:
+            RELEASE_ASSERT_NOT_REACHED();
+        case Stack: {
+            AbstractHeap abstractHeap = location.heap();
+            if (abstractHeap.payload().isTop())
+                return add(m_fallbackStackMap, location, node);
+            ASSERT(abstractHeap.payload().value() == abstractHeap.payload().value32());
+            auto addResult = m_abstractHeapStackMap.add(abstractHeap.payload().value32(), nullptr);
+            if (addResult.isNewEntry) {
+                addResult.iterator->value.reset(new ImpureDataSlot {location, node, 0});
+                return nullptr;
+            }
+            if (addResult.iterator->value->key == location)
+                return addResult.iterator->value.get();
+            return add(m_fallbackStackMap, location, node);
+        }
+        default:
+            return add(m_heapMap, location, node);
+        }
+        return nullptr;
+    }
+
+    LazyNode getImpl(const HeapLocation& location) const
+    {
+        switch (location.heap().kind()) {
+        case World:
+        case SideState:
+            RELEASE_ASSERT_NOT_REACHED();
+        case Stack: {
+            ASSERT(location.heap().payload().value() == location.heap().payload().value32());
+            auto iterator = m_abstractHeapStackMap.find(location.heap().payload().value32());
+            if (iterator != m_abstractHeapStackMap.end()
+                && iterator->value->key == location)
+                return iterator->value->value;
+            return get(m_fallbackStackMap, location);
+        }
+        default:
+            return get(m_heapMap, location);
+        }
+        return LazyNode();
+    }
+
+    static const ImpureDataSlot* add(Map& map, const HeapLocation& location, const LazyNode& node)
+    {
+        auto result = map.add<ImpureDataTranslator>(location);
+        if (result.isNewEntry) {
+            (*result.iterator)->value = node;
+            return nullptr;
+        }
+        return result.iterator->get();
+    }
+
+    static LazyNode get(const Map& map, const HeapLocation& location)
+    {
+        auto iterator = map.find<ImpureDataTranslator>(location);
+        if (iterator != map.end())
+            return (*iterator)->value;
+        return LazyNode();
+    }
+
+    static void clobber(Map& map, AbstractHeap heap)
+    {
+        map.removeIf([heap](const std::unique_ptr<ImpureDataSlot>& slot) -> bool {
+            return heap.overlaps(slot->key.heap());
+        });
+    }
+
+    Map m_worldMap;
+    Map m_heapMap;
+    Map m_sideStateMap;
+
+    // The majority of Impure Stack Slotsare unique per value.
+    // This is very useful for fast clobber(), we can just remove the slot addressed by AbstractHeap
+    // in O(1).
+    //
+    // When there are conflict, any additional HeapLocation is added in the fallback map.
+    // This works well because fallbackStackMap remains tiny.
+    //
+    // One cannot assume a unique ImpureData is in m_abstractHeapStackMap. It may have been
+    // a duplicate in the past and now only live in m_fallbackStackMap.
+    //
+    // Obviously, TOP always goes into m_fallbackStackMap since it does not have a unique value.
+    HashMap<int32_t, std::unique_ptr<ImpureDataSlot>, DefaultHash<int32_t>::Hash, WTF::SignedWithZeroKeyHashTraits<int32_t>> m_abstractHeapStackMap;
+    Map m_fallbackStackMap;
+
+#if !defined(NDEBUG)
+    HashMap<HeapLocation, LazyNode> m_debugImpureData;
+#endif
+};
 
 class LocalCSEPhase : public Phase {
 public:
@@ -131,6 +334,9 @@ private:
     
         void write(AbstractHeap heap)
         {
+            if (heap.kind() == SideState)
+                return;
+
             for (unsigned i = 0; i < m_impureLength; ++i) {
                 if (heap.overlaps(m_impureMap[i].key.heap()))
                     m_impureMap[i--] = m_impureMap[--m_impureLength];
@@ -192,7 +398,7 @@ private:
     
         void write(AbstractHeap heap)
         {
-            clobber(m_impureMap, heap);
+            m_impureMap.clobber(heap);
         }
     
         Node* addPure(PureValue value, Node* node)
@@ -208,17 +414,16 @@ private:
             return m_impureMap.get(location);
         }
     
-        LazyNode addImpure(HeapLocation location, LazyNode node)
+        LazyNode addImpure(const HeapLocation& location, const LazyNode& node)
         {
-            auto result = m_impureMap.add(location, node);
-            if (result.isNewEntry)
-                return nullptr;
-            return result.iterator->value;
+            if (const ImpureDataSlot* slot = m_impureMap.add(location, node))
+                return slot->value;
+            return LazyNode();
         }
 
     private:
         HashMap<PureValue, Node*> m_pureMap;
-        HashMap<HeapLocation, LazyNode> m_impureMap;
+        ImpureMap m_impureMap;
     };
 
     template<typename Maps>
@@ -327,7 +532,7 @@ private:
             m_changed = true;
         }
     
-        void def(HeapLocation location, LazyNode value)
+        void def(const HeapLocation& location, const LazyNode& value)
         {
             LazyNode match = m_maps.addImpure(location, value);
             if (!match)
@@ -461,10 +666,8 @@ public:
     
     void write(AbstractHeap heap)
     {
-        clobber(m_impureData->availableAtTail, heap);
+        m_impureData->availableAtTail.clobber(heap);
         m_writesSoFar.add(heap);
-        if (verbose)
-            dataLog("    Clobbered, new tail map: ", mapDump(m_impureData->availableAtTail), "\n");
     }
     
     void def(PureValue value)
@@ -579,8 +782,6 @@ public:
                     dataLog("        It strictly dominates.\n");
                 DFG_ASSERT(m_graph, m_node, data.didVisit);
                 DFG_ASSERT(m_graph, m_node, !match);
-                if (verbose)
-                    dataLog("        Availability map: ", mapDump(data.availableAtTail), "\n");
                 match = data.availableAtTail.get(location);
                 if (verbose)
                     dataLog("        Availability: ", match, "\n");
@@ -639,7 +840,7 @@ public:
             if (verbose)
                 dataLog("      Adding at-tail mapping: ", location, " -> ", value, "\n");
             auto result = m_impureData->availableAtTail.add(location, value);
-            ASSERT_UNUSED(result, result.isNewEntry);
+            ASSERT_UNUSED(result, !result);
             return;
         }
 
index ffeeabd..06bc0ae 100644 (file)
@@ -154,12 +154,6 @@ template<> struct HashTraits<JSC::DFG::HeapLocation> : SimpleClassHashTraits<JSC
 
 } // namespace WTF
 
-namespace JSC { namespace DFG {
-
-typedef HashMap<HeapLocation, LazyNode> ImpureMap;
-
-} } // namespace JSC::DFG
-
 #endif // ENABLE(DFG_JIT)
 
 #endif // DFGHeapLocation_h
index ffd572f..8d8f48d 100644 (file)
@@ -110,9 +110,10 @@ public:
 
     unsigned hash() const
     {
-        if (asValue())
-            return WTF::PtrHash<FrozenValue*>::hash(asValue());
-        return WTF::PtrHash<Node*>::hash(m_node);
+        void* toHash = m_node;
+        if (FrozenValue* value = asValue())
+            toHash = value;
+        return WTF::PtrHash<void*>::hash(toHash);
     }
 
     bool operator==(const LazyNode& other) const
index 3fe1da2..5c8dad9 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "CodeBlockWithJITType.h"
+#include "DFGClobberize.h"
 #include "DFGClobbersExitState.h"
 #include "DFGMayExit.h"
 #include "JSCInlines.h"
@@ -298,6 +299,47 @@ public:
             validateSSA();
             break;
         }
+
+        // Validate clobbered states.
+        struct DefLambdaAdaptor {
+            std::function<void(PureValue)> pureValue;
+            std::function<void(HeapLocation, LazyNode)> locationAndNode;
+
+            void operator()(PureValue value) const
+            {
+                pureValue(value);
+            }
+
+            void operator()(HeapLocation location, LazyNode node) const
+            {
+                locationAndNode(location, node);
+            }
+        };
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (Node* node : *block) {
+                clobberize(m_graph, node,
+                    [&] (AbstractHeap) { },
+                    [&] (AbstractHeap heap)
+                    {
+                        // CSE assumes that HEAP TOP is never written.
+                        // If this assumption is weakened, you need to update clobbering
+                        // in CSE accordingly.
+                        if (heap.kind() == Stack)
+                            VALIDATE((node), !heap.payload().isTop());
+                    },
+                    DefLambdaAdaptor {
+                        [&] (PureValue) { },
+                        [&] (HeapLocation location, LazyNode)
+                        {
+                            VALIDATE((node), location.heap().kind() != SideState);
+
+                            // More specific kinds should be used instead.
+                            VALIDATE((node), location.heap().kind() != World);
+                            VALIDATE((node), location.heap().kind() != Heap);
+                        }
+                });
+            }
+        }
     }
     
 private:
index c3e4f06..19376bb 100644 (file)
@@ -1,3 +1,13 @@
+2016-03-17  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Make CSE's ImpureData faster when dealing with large blocks
+        https://bugs.webkit.org/show_bug.cgi?id=155594
+
+        Reviewed by Filip Pizlo.
+
+        * wtf/HashSet.h:
+        (WTF::V>::removeIf):
+
 2016-03-17  Saam barati  <sbarati@apple.com>
 
         Implement SmallPtrSet and integrate it into the Parser
index 68f956c..c9a2fc1 100644 (file)
@@ -101,6 +101,8 @@ namespace WTF {
 
         bool remove(const ValueType&);
         bool remove(iterator);
+        template<typename Functor>
+        void removeIf(const Functor&);
         void clear();
 
         ValueType take(const ValueType&);
@@ -251,6 +253,13 @@ namespace WTF {
     }
 
     template<typename T, typename U, typename V>
+    template<typename Functor>
+    inline void HashSet<T, U, V>::removeIf(const Functor& functor)
+    {
+        m_impl.removeIf(functor);
+    }
+
+    template<typename T, typename U, typename V>
     inline void HashSet<T, U, V>::clear()
     {
         m_impl.clear(); 
index fca35f3..b886385 100644 (file)
@@ -85,6 +85,13 @@ template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T>
     static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
 };
 
+template<typename T> struct SignedWithZeroKeyHashTraits : GenericHashTraits<T> {
+    static const bool emptyValueIsZero = false;
+    static T emptyValue() { return std::numeric_limits<T>::min(); }
+    static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max(); }
+    static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max(); }
+};
+
 // Can be used with strong enums, allows zero as key.
 template<typename T> struct StrongEnumHashTraits : GenericHashTraits<T> {
     using UnderlyingType = typename std::underlying_type<T>::type;