Changeset 204112 in webkit

Timestamp:

Aug 3, 2016, 8:43:51 PM (10 years ago)

Author:

commit-queue@webkit.org

Message:

[JSC] Improve the memory locality of DFG Node's AbstractValues
​https://bugs.webkit.org/show_bug.cgi?id=160443

Patch by Benjamin Poulain <​bpoulain@apple.com> on 2016-08-03
Reviewed by Mark Lam.

The AbstractInterpreter spends a lot of time on memory operations
for AbstractValues. This patch attempts to improve the situation
by putting the values closer together in memory.

First, AbstractValue is moved out of DFG::Node and it kept in
a vector addressed by node indices.

I initially moved them to InPlaceAbstractState but I quickly discovered
initializing the values in the vector was costly.
I moved the vector to Graph as a cache shared by every instantiation of
InPlaceAbstractState. It is mainly there to avoid constructors and destructors
of AbstractValue. The patch of ​https://bugs.webkit.org/show_bug.cgi?id=160370
should also help eventually.

I instrumented CFA to find how packed is SparseCollection.
The answer is it can be very sparse, which is bad for CFA.
I added packIndices() to repack the collection before running
liveness since that's where we start using the memory intensively.
This is a measurable improvement but it implies we can no longer
keep indices on a side channel between phases since they may change.

• b3/B3SparseCollection.h:

(JSC::B3::SparseCollection::packIndices):

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::packNodeIndices):

• dfg/DFGGraph.h:

(JSC::DFG::Graph::abstractValuesCache):

• dfg/DFGInPlaceAbstractState.cpp:

(JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):

• dfg/DFGInPlaceAbstractState.h:

(JSC::DFG::InPlaceAbstractState::forNode):

• dfg/DFGLivenessAnalysisPhase.cpp:

(JSC::DFG::performLivenessAnalysis):

• dfg/DFGNode.h:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• b3/B3SparseCollection.h (modified) (1 diff)
• dfg/DFGGraph.cpp (modified) (1 diff)
• dfg/DFGGraph.h (modified) (2 diffs)
• dfg/DFGInPlaceAbstractState.cpp (modified) (2 diffs)
• dfg/DFGInPlaceAbstractState.h (modified) (2 diffs)
• dfg/DFGLivenessAnalysisPhase.cpp (modified) (1 diff)
• dfg/DFGNode.h (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-08-03  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Improve the memory locality of DFG Node's AbstractValues
+        https://bugs.webkit.org/show_bug.cgi?id=160443
+
+        Reviewed by Mark Lam.
+
+        The AbstractInterpreter spends a lot of time on memory operations
+        for AbstractValues. This patch attempts to improve the situation
+        by putting the values closer together in memory.
+
+        First, AbstractValue is moved out of DFG::Node and it kept in
+        a vector addressed by node indices.
+
+        I initially moved them to InPlaceAbstractState but I quickly discovered
+        initializing the values in the vector was costly.
+        I moved the vector to Graph as a cache shared by every instantiation of
+        InPlaceAbstractState. It is mainly there to avoid constructors and destructors
+        of AbstractValue. The patch of https://bugs.webkit.org/show_bug.cgi?id=160370
+        should also help eventually.
+
+        I instrumented CFA to find how packed is SparseCollection.
+        The answer is it can be very sparse, which is bad for CFA.
+        I added packIndices() to repack the collection before running
+        liveness since that's where we start using the memory intensively.
+        This is a measurable improvement but it implies we can no longer
+        keep indices on a side channel between phases since they may change.
+
+        * b3/B3SparseCollection.h:
+        (JSC::B3::SparseCollection::packIndices):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::packNodeIndices):
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::abstractValuesCache):
+        * dfg/DFGInPlaceAbstractState.cpp:
+        (JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):
+        * dfg/DFGInPlaceAbstractState.h:
+        (JSC::DFG::InPlaceAbstractState::forNode):
+        * dfg/DFGLivenessAnalysisPhase.cpp:
+        (JSC::DFG::performLivenessAnalysis):
+        * dfg/DFGNode.h:
+
 2016-08-03  Caitlin Potter  <caitp@igalia.com>
 

trunk/Source/JavaScriptCore/b3/B3SparseCollection.h

@@ -75 +75 @@
     }
 
+    void packIndices()
+    {
+        if (m_indexFreeList.isEmpty())
+            return;
+
+        unsigned holeIndex = 0;
+        unsigned endIndex = m_vector.size();
+
+        while (true) {
+            while (holeIndex < endIndex && m_vector[holeIndex])
+                ++holeIndex;
+
+            if (holeIndex == endIndex)
+                break;
+            ASSERT(holeIndex < m_vector.size());
+            ASSERT(!m_vector[holeIndex]);
+
+            do {
+                --endIndex;
+            } while (!m_vector[endIndex] && endIndex > holeIndex);
+
+            if (holeIndex == endIndex)
+                break;
+            ASSERT(endIndex > holeIndex);
+            ASSERT(m_vector[endIndex]);
+
+            auto& value = m_vector[endIndex];
+            value->m_index = holeIndex;
+            m_vector[holeIndex] = WTFMove(value);
+            ++holeIndex;
+        }
+
+        m_indexFreeList.resize(0);
+        m_vector.resize(endIndex);
+    }
+
     unsigned size() const { return m_vector.size(); }
     bool isEmpty() const { return m_vector.isEmpty(); }

trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp

@@ -577 +577 @@
     }
     m_nodes.remove(node);
+}
+
+void Graph::packNodeIndices()
+{
+    m_nodes.packIndices();
 }
 

trunk/Source/JavaScriptCore/dfg/DFGGraph.h

@@ -198 +198 @@
     unsigned maxNodeCount() const { return m_nodes.size(); }
     Node* nodeAt(unsigned index) const { return m_nodes[index]; }
+    void packNodeIndices();
+
+    Vector<AbstractValue>& abstractValuesCache() { return m_abstractValuesCache; }
 
     void dethread();
@@ -955 +958 @@
 
     B3::SparseCollection<Node> m_nodes;
+    Vector<AbstractValue> m_abstractValuesCache;
 };
 

trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

@@ -42 +42 @@
 InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
     : m_graph(graph)
+    , m_abstractValues(graph.abstractValuesCache())
     , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
     , m_block(0)
@@ -56 +57 @@
     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
+
+    // Certain phases insert nodes in a block after running through it.
+    // We cannot reserve the space for AbstractValues when initializing AbstractState because the number of values
+    // can increase as we execute. Instead, we increase the size as needed before processing each block.
+    m_abstractValues.resize(m_graph.maxNodeCount());
     
     for (size_t i = 0; i < basicBlock->size(); i++)

trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h

@@ -49 +49 @@
     AbstractValue& forNode(Node* node)
     {
-        return node->value;
+        return m_abstractValues[node->index()];
     }
     
@@ -133 +133 @@
     
     Graph& m_graph;
-    
+
+    Vector<AbstractValue>& m_abstractValues;
     Operands<AbstractValue> m_variables;
     BasicBlock* m_block;

trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp

@@ -196 +196 @@
 bool performLivenessAnalysis(Graph& graph)
 {
+    graph.packNodeIndices();
+
     return runPhase<LivenessAnalysisPhase>(graph);
 }

trunk/Source/JavaScriptCore/dfg/DFGNode.h

@@ -2363 +2363 @@
     uintptr_t m_opInfo2;
 
-public:
-    // Fields used by various analyses.
-    AbstractValue value;
-    
     // Miscellaneous data that is usually meaningless, but can hold some analysis results
     // if you ask right. For example, if you do Graph::initializeNodeOwners(), Node::owner