[JSC] Make DFG Local CSE and AI conservative for huge basic block
authorysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Jul 2019 23:07:11 +0000 (23:07 +0000)
committerysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 22 Jul 2019 23:07:11 +0000 (23:07 +0000)
https://bugs.webkit.org/show_bug.cgi?id=199929
<rdar://problem/49309924>

Reviewed by Filip Pizlo.

In CNN page, the main thread hangs several seconds. On less-powerful devices (like iPhone7), it hangs for ~11 seconds. This is not an acceptable behavior.
The reason of this is that the DFG compiler takes too long time in the compilation for a particular function. It takes 8765 ms even in powerful x64 machine!
DFG compiler is concurrent one. However, when GC requires all the peripheral threads to be stopped, the main thread needs to wait for the DFG compiler's stop.
DFG compiler stops at GC safepoints, and they are inserted between DFG phases. So, if some of DFG phases take very long time, the main thread is blocked during that.
As a result, the main thread is blocked due to this pathological compilation.

By measuring the time taken in each DFG phase, we found that our AI and CSE phase have a problem having quadratic complexity for # of DFG nodes in a basic block.
In this patch, we add a threshold for # of DFG nodes in a basic block. If a basic block exceeds this threshold, we use conservative but O(1) algorithm for AI and Local CSE phase.
We did not add this threshold for Global CSE since FTL has another bytecode cost threshold which prevents us from compiling the large functions. But on the other hand,
DFG should compile them because DFG is intended to be a fast compiler even for a bit larger CodeBlock.

We first attempted to reduce the threshold for DFG compilation. We are using 100000 bytecode cost for DFG compilation and it is very large. However, we found that bytecode cost
is not the problem in CNN page. The problematic function has 67904 cost, and it takes 8765 ms in x64 machine. However, JetStream2/octane-zlib has 61949 function and it only takes
~400 ms. This difference comes from the # of DFG nodes in a basic block. The problematic function has 43297 DFG nodes in one basic block and it makes AI and Local CSE super time-consuming.
Rather than relying on the bytecode cost which a bit indirectly related to this pathological compile-time, we should look into # of DFG nodes in a basic block which is more directly
related to this problem. And we also found that 61949's Octane-zlib function is very critical for performance. This fact makes a bit hard to pick a right threshold: 67904 causes the problem,
and 61949 must be compiled. This is why this patch is introducing conservative analysis instead of adjusting the threshold for DFG.

This patch has two changes.

1. DFG AI has structure transition tracking which has quadratic complexity

Structure transition tracking takes very long time since its complexity is O(N^2) where N is # of DFG nodes in a basic block.
CNN has very pathological script and it shows 43297 DFG nodes. We should reduce the complexity of this algorithm.
For now, we just say "structures are clobbered" if # of DFG nodes in a basic block exceeds the threshold (20000).
We could improve the current algorithm from O(N^2) to O(2N) without being conservative, and I'm tracking this in [1].

2. DFG Local CSE has quadratic complexity

Local CSE's clobbering iterates all the impure heap values to remove the clobbered one. Since # of impure heap values tend to be proportional to # of DFG nodes we visited,
each CSE for a basic block gets O(N^2) complexity. To avoid this, we introduce HugeMap. This has the same interface to LargeMap and SmallMap in CSE, but its clobbering
implementation just clears the map completely. We can further make this O(N) without introducing conservative behavior by using epochs. For now, we do not see such a huge basic block in
JetStream2 and Speedometer2 so I'll track it in a separate bug[2].

This patch reduces the compilation time from ~11 seconds to ~200 ms.

[1]: https://bugs.webkit.org/show_bug.cgi?id=199959
[2]: https://bugs.webkit.org/show_bug.cgi?id=200014

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::observeTransition):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::observeTransitions):
* dfg/DFGCSEPhase.cpp:
* runtime/Options.h:

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
Source/JavaScriptCore/runtime/Options.h
Tools/Scripts/run-jsc-stress-tests

index 3a33e2c..54c9192 100644 (file)
@@ -1,3 +1,56 @@
+2019-07-20  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] Make DFG Local CSE and AI conservative for huge basic block
+        https://bugs.webkit.org/show_bug.cgi?id=199929
+        <rdar://problem/49309924>
+
+        Reviewed by Filip Pizlo.
+
+        In CNN page, the main thread hangs several seconds. On less-powerful devices (like iPhone7), it hangs for ~11 seconds. This is not an acceptable behavior.
+        The reason of this is that the DFG compiler takes too long time in the compilation for a particular function. It takes 8765 ms even in powerful x64 machine!
+        DFG compiler is concurrent one. However, when GC requires all the peripheral threads to be stopped, the main thread needs to wait for the DFG compiler's stop.
+        DFG compiler stops at GC safepoints, and they are inserted between DFG phases. So, if some of DFG phases take very long time, the main thread is blocked during that.
+        As a result, the main thread is blocked due to this pathological compilation.
+
+        By measuring the time taken in each DFG phase, we found that our AI and CSE phase have a problem having quadratic complexity for # of DFG nodes in a basic block.
+        In this patch, we add a threshold for # of DFG nodes in a basic block. If a basic block exceeds this threshold, we use conservative but O(1) algorithm for AI and Local CSE phase.
+        We did not add this threshold for Global CSE since FTL has another bytecode cost threshold which prevents us from compiling the large functions. But on the other hand,
+        DFG should compile them because DFG is intended to be a fast compiler even for a bit larger CodeBlock.
+
+        We first attempted to reduce the threshold for DFG compilation. We are using 100000 bytecode cost for DFG compilation and it is very large. However, we found that bytecode cost
+        is not the problem in CNN page. The problematic function has 67904 cost, and it takes 8765 ms in x64 machine. However, JetStream2/octane-zlib has 61949 function and it only takes
+        ~400 ms. This difference comes from the # of DFG nodes in a basic block. The problematic function has 43297 DFG nodes in one basic block and it makes AI and Local CSE super time-consuming.
+        Rather than relying on the bytecode cost which a bit indirectly related to this pathological compile-time, we should look into # of DFG nodes in a basic block which is more directly
+        related to this problem. And we also found that 61949's Octane-zlib function is very critical for performance. This fact makes a bit hard to pick a right threshold: 67904 causes the problem,
+        and 61949 must be compiled. This is why this patch is introducing conservative analysis instead of adjusting the threshold for DFG.
+
+        This patch has two changes.
+
+        1. DFG AI has structure transition tracking which has quadratic complexity
+
+        Structure transition tracking takes very long time since its complexity is O(N^2) where N is # of DFG nodes in a basic block.
+        CNN has very pathological script and it shows 43297 DFG nodes. We should reduce the complexity of this algorithm.
+        For now, we just say "structures are clobbered" if # of DFG nodes in a basic block exceeds the threshold (20000).
+        We could improve the current algorithm from O(N^2) to O(2N) without being conservative, and I'm tracking this in [1].
+
+        2. DFG Local CSE has quadratic complexity
+
+        Local CSE's clobbering iterates all the impure heap values to remove the clobbered one. Since # of impure heap values tend to be proportional to # of DFG nodes we visited,
+        each CSE for a basic block gets O(N^2) complexity. To avoid this, we introduce HugeMap. This has the same interface to LargeMap and SmallMap in CSE, but its clobbering
+        implementation just clears the map completely. We can further make this O(N) without introducing conservative behavior by using epochs. For now, we do not see such a huge basic block in
+        JetStream2 and Speedometer2 so I'll track it in a separate bug[2].
+
+        This patch reduces the compilation time from ~11 seconds to ~200 ms.
+
+        [1]: https://bugs.webkit.org/show_bug.cgi?id=199959
+        [2]: https://bugs.webkit.org/show_bug.cgi?id=200014
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::observeTransition):
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::observeTransitions):
+        * dfg/DFGCSEPhase.cpp:
+        * runtime/Options.h:
+
 2019-07-22  Zhifei Fang  <zhifei_fang@apple.com>
 
         Need to skip test cache directory data vault for non internal build
index 89daeb9..8b84592 100644 (file)
@@ -4093,6 +4093,14 @@ template<typename AbstractStateType>
 void AbstractInterpreter<AbstractStateType>::observeTransition(
     unsigned clobberLimit, RegisteredStructure from, RegisteredStructure to)
 {
+    // Stop performing precise structure transition tracking.
+    // Precise structure transition tracking shows quadratic complexity for # of nodes in a basic block.
+    // If it is too large, we conservatively clobber all the structures.
+    if (m_state.block()->size() > Options::maxDFGNodesInBasicBlockForPreciseAnalysis()) {
+        clobberStructures();
+        return;
+    }
+
     AbstractValue::TransitionObserver transitionObserver(from, to);
     forAllValues(clobberLimit, transitionObserver);
     
@@ -4108,6 +4116,14 @@ void AbstractInterpreter<AbstractStateType>::observeTransitions(
     if (vector.isEmpty())
         return;
     
+    // Stop performing precise structure transition tracking.
+    // Precise structure transition tracking shows quadratic complexity for # of nodes in a basic block.
+    // If it is too large, we conservatively clobber all the structures.
+    if (m_state.block()->size() > Options::maxDFGNodesInBasicBlockForPreciseAnalysis()) {
+        clobberStructures();
+        return;
+    }
+
     AbstractValue::TransitionsObserver transitionsObserver(vector);
     forAllValues(clobberLimit, transitionsObserver);
     
index e89daae..9d9ae31 100644 (file)
@@ -136,7 +136,7 @@ public:
         return result;
     }
 
-    void clobber(AbstractHeap heap)
+    void clobber(AbstractHeap heap, bool clobberConservatively)
     {
         switch (heap.kind()) {
         case World: {
@@ -149,15 +149,45 @@ public:
             ASSERT(!heap.payload().isTop());
             ASSERT(heap.payload().value() == heap.payload().value32());
             m_abstractHeapStackMap.remove(heap.payload().value32());
-            clobber(m_fallbackStackMap, heap);
+            if (clobberConservatively)
+                m_fallbackStackMap.clear();
+            else
+                clobber(m_fallbackStackMap, heap);
             break;
         }
         default:
-            clobber(m_heapMap, heap);
+            if (clobberConservatively)
+                m_heapMap.clear();
+            else
+                clobber(m_heapMap, heap);
             break;
         }
 #if !defined(NDEBUG)
-        m_debugImpureData.removeIf([heap](const HashMap<HeapLocation, LazyNode>::KeyValuePairType& pair) -> bool {
+        m_debugImpureData.removeIf([heap, clobberConservatively, this](const HashMap<HeapLocation, LazyNode>::KeyValuePairType& pair) -> bool {
+            switch (heap.kind()) {
+            case World:
+            case SideState:
+                break;
+            case Stack: {
+                if (!clobberConservatively)
+                    break;
+                if (pair.key.heap().kind() == Stack) {
+                    auto iterator = m_abstractHeapStackMap.find(pair.key.heap().payload().value32());
+                    if (iterator != m_abstractHeapStackMap.end() && iterator->value->key == pair.key)
+                        return false;
+                    return true;
+                }
+                break;
+            }
+            default: {
+                if (!clobberConservatively)
+                    break;
+                AbstractHeapKind kind = pair.key.heap().kind();
+                if (kind != World && kind != SideState && kind != Stack)
+                    return true;
+                break;
+            }
+            }
             return heap.overlaps(pair.key.heap());
         });
         ASSERT(m_debugImpureData.size()
@@ -284,6 +314,7 @@ public:
         : Phase(graph, "local common subexpression elimination")
         , m_smallBlock(graph)
         , m_largeBlock(graph)
+        , m_hugeBlock(graph)
     {
     }
     
@@ -303,8 +334,10 @@ public:
             
             if (block->size() <= SmallMaps::capacity)
                 changed |= m_smallBlock.run(block);
-            else
+            else if (block->size() <= Options::maxDFGNodesInBasicBlockForPreciseAnalysis())
                 changed |= m_largeBlock.run(block);
+            else
+                changed |= m_hugeBlock.run(block);
         }
         
         return changed;
@@ -400,7 +433,8 @@ private:
     
         void write(AbstractHeap heap)
         {
-            m_impureMap.clobber(heap);
+            bool clobberConservatively = false;
+            m_impureMap.clobber(heap, clobberConservatively);
         }
     
         Node* addPure(PureValue value, Node* node)
@@ -428,6 +462,52 @@ private:
         ImpureMap m_impureMap;
     };
 
+    // This is used only for huge basic blocks. Our usual CSE is quadratic complexity for # of DFG nodes in a basic block.
+    // HugeMaps model results conservatively to avoid an O(N^2) algorithm. In particular, we clear all the slots of the specified heap kind
+    // in ImpureMap instead of iterating slots and removing a matched slot. This change makes the complexity O(N).
+    // FIXME: We can make LargeMap O(N) without introducing conservative behavior if we track clobbering by hierarchical epochs.
+    // https://bugs.webkit.org/show_bug.cgi?id=200014
+    class HugeMaps {
+    public:
+        HugeMaps() = default;
+
+        void clear()
+        {
+            m_pureMap.clear();
+            m_impureMap.clear();
+        }
+
+        void write(AbstractHeap heap)
+        {
+            bool clobberConservatively = true;
+            m_impureMap.clobber(heap, clobberConservatively);
+        }
+
+        Node* addPure(PureValue value, Node* node)
+        {
+            auto result = m_pureMap.add(value, node);
+            if (result.isNewEntry)
+                return nullptr;
+            return result.iterator->value;
+        }
+
+        LazyNode findReplacement(HeapLocation location)
+        {
+            return m_impureMap.get(location);
+        }
+
+        LazyNode addImpure(const HeapLocation& location, const LazyNode& node)
+        {
+            if (const ImpureDataSlot* slot = m_impureMap.add(location, node))
+                return slot->value;
+            return LazyNode();
+        }
+
+    private:
+        HashMap<PureValue, Node*> m_pureMap;
+        ImpureMap m_impureMap;
+    };
+
     template<typename Maps>
     class BlockCSE {
     public:
@@ -581,6 +661,7 @@ private:
 
     BlockCSE<SmallMaps> m_smallBlock;
     BlockCSE<LargeMaps> m_largeBlock;
+    BlockCSE<HugeMaps> m_hugeBlock;
 };
 
 class GlobalCSEPhase : public Phase {
@@ -668,7 +749,8 @@ public:
     
     void write(AbstractHeap heap)
     {
-        m_impureData->availableAtTail.clobber(heap);
+        bool clobberConservatively = false;
+        m_impureData->availableAtTail.clobber(heap, clobberConservatively);
         m_writesSoFar.add(heap);
     }
     
index 03a6c2d..8e73d1b 100644 (file)
@@ -273,6 +273,7 @@ constexpr bool enableWebAssemblyStreamingApi = false;
     v(bool, useValueRepElimination, true, Normal, nullptr) \
     v(bool, useArityFixupInlining, true, Normal, nullptr) \
     v(bool, logExecutableAllocation, false, Normal, nullptr) \
+    v(unsigned, maxDFGNodesInBasicBlockForPreciseAnalysis, 20000, Normal, "Disable precise but costly analysis and give conservative results if the number of DFG nodes in a block exceeds this threshold") \
     \
     v(bool, useConcurrentJIT, true, Normal, "allows the DFG / FTL compilation in threads other than the executing JS thread") \
     v(unsigned, numberOfDFGCompilerThreads, computeNumberOfWorkerThreads(3, 2) - 1, Normal, nullptr) \
index eea17fb..9d77f58 100755 (executable)
@@ -492,7 +492,7 @@ EAGER_OPTIONS = ["--thresholdForJITAfterWarmUp=10", "--thresholdForJITSoon=10",
 # NOTE: Tests rely on this using scribbleFreeCells.
 NO_CJIT_OPTIONS = ["--useConcurrentJIT=false", "--thresholdForJITAfterWarmUp=100", "--scribbleFreeCells=true"]
 B3O1_OPTIONS = ["--defaultB3OptLevel=1"]
-B3O0_OPTIONS = ["--defaultB3OptLevel=0"]
+B3O0_OPTIONS = ["--maxDFGNodesInBasicBlockForPreciseAnalysis=100", "--defaultB3OptLevel=0"]
 FTL_OPTIONS = ["--useFTLJIT=true"]
 PROBE_OSR_EXIT_OPTION = ["--useProbeOSRExit=true"]