[webkit-changes] [204112] trunk/Source/JavaScriptCore

Wed, 03 Aug 2016 20:44:23 -0700

Title: [204112] trunk/Source/_javascript_Core
Revision
204112
Author
[email protected]
Date
2016-08-03 20:43:51 -0700 (Wed, 03 Aug 2016)

Log Message

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

Patch by Benjamin Poulain <[email protected]> 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:

Modified Paths

Diff

Modified: trunk/Source/_javascript_Core/ChangeLog (204111 => 204112)


--- trunk/Source/_javascript_Core/ChangeLog	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/ChangeLog	2016-08-04 03:43:51 UTC (rev 204112)
@@ -1,3 +1,45 @@
+2016-08-03  Benjamin Poulain  <[email protected]>
+
+        [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  <[email protected]>
 
         Clarify SyntaxErrors around yield and unskip tests

Modified: trunk/Source/_javascript_Core/b3/B3SparseCollection.h (204111 => 204112)


--- trunk/Source/_javascript_Core/b3/B3SparseCollection.h	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/b3/B3SparseCollection.h	2016-08-04 03:43:51 UTC (rev 204112)
@@ -74,6 +74,42 @@
         m_vector[value->m_index] = nullptr;
     }
 
+    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(); }

Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp	2016-08-04 03:43:51 UTC (rev 204112)
@@ -578,6 +578,11 @@
     m_nodes.remove(node);
 }
 
+void Graph::packNodeIndices()
+{
+    m_nodes.packIndices();
+}
+
 void Graph::dethread()
 {
     if (m_form == LoadStore || m_form == SSA)

Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGGraph.h	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h	2016-08-04 03:43:51 UTC (rev 204112)
@@ -197,7 +197,10 @@
     void deleteNode(Node*);
     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();
     
     FrozenValue* freeze(JSValue); // We use weak freezing by default.
@@ -954,6 +957,7 @@
     }
 
     B3::SparseCollection<Node> m_nodes;
+    Vector<AbstractValue> m_abstractValuesCache;
 };
 
 } } // namespace JSC::DFG

Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp	2016-08-04 03:43:51 UTC (rev 204112)
@@ -41,6 +41,7 @@
 
 InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
     : m_graph(graph)
+    , m_abstractValues(graph.abstractValuesCache())
     , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
     , m_block(0)
 {
@@ -55,6 +56,11 @@
     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
     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++)
         forNode(basicBlock->at(i)).clear();

Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h	2016-08-04 03:43:51 UTC (rev 204112)
@@ -48,7 +48,7 @@
     
     AbstractValue& forNode(Node* node)
     {
-        return node->value;
+        return m_abstractValues[node->index()];
     }
     
     AbstractValue& forNode(Edge edge)
@@ -132,7 +132,8 @@
     static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
     
     Graph& m_graph;
-    
+
+    Vector<AbstractValue>& m_abstractValues;
     Operands<AbstractValue> m_variables;
     BasicBlock* m_block;

Modified: trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp	2016-08-04 03:43:51 UTC (rev 204112)
@@ -195,6 +195,8 @@
 
 bool performLivenessAnalysis(Graph& graph)
 {
+    graph.packNodeIndices();
+
     return runPhase<LivenessAnalysisPhase>(graph);
 }

Modified: trunk/Source/_javascript_Core/dfg/DFGNode.h (204111 => 204112)


--- trunk/Source/_javascript_Core/dfg/DFGNode.h	2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/_javascript_Core/dfg/DFGNode.h	2016-08-04 03:43:51 UTC (rev 204112)
@@ -2362,10 +2362,6 @@
     uintptr_t m_opInfo;
     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
     // will tell you which basic block a node belongs to. You cannot rely on this persisting

_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to