<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[204112] trunk/Source/JavaScriptCore</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/204112">204112</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2016-08-03 20:43:51 -0700 (Wed, 03 Aug 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[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:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3SparseCollectionh">trunk/Source/JavaScriptCore/b3/B3SparseCollection.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphcpp">trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGGraphh">trunk/Source/JavaScriptCore/dfg/DFGGraph.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStatecpp">trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh">trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGNodeh">trunk/Source/JavaScriptCore/dfg/DFGNode.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -1,3 +1,45 @@
</span><ins>+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:
+
</ins><span class="cx"> 2016-08-03 Caitlin Potter <caitp@igalia.com>
</span><span class="cx">
</span><span class="cx"> Clarify SyntaxErrors around yield and unskip tests
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3SparseCollectionh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3SparseCollection.h (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3SparseCollection.h 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/b3/B3SparseCollection.h 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -74,6 +74,42 @@
</span><span class="cx"> m_vector[value->m_index] = nullptr;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ 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);
+ }
+
</ins><span class="cx"> unsigned size() const { return m_vector.size(); }
</span><span class="cx"> bool isEmpty() const { return m_vector.isEmpty(); }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -578,6 +578,11 @@
</span><span class="cx"> m_nodes.remove(node);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void Graph::packNodeIndices()
+{
+ m_nodes.packIndices();
+}
+
</ins><span class="cx"> void Graph::dethread()
</span><span class="cx"> {
</span><span class="cx"> if (m_form == LoadStore || m_form == SSA)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGGraphh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGGraph.h (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGGraph.h 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -197,7 +197,10 @@
</span><span class="cx"> void deleteNode(Node*);
</span><span class="cx"> unsigned maxNodeCount() const { return m_nodes.size(); }
</span><span class="cx"> Node* nodeAt(unsigned index) const { return m_nodes[index]; }
</span><ins>+ void packNodeIndices();
</ins><span class="cx">
</span><ins>+ Vector<AbstractValue>& abstractValuesCache() { return m_abstractValuesCache; }
+
</ins><span class="cx"> void dethread();
</span><span class="cx">
</span><span class="cx"> FrozenValue* freeze(JSValue); // We use weak freezing by default.
</span><span class="lines">@@ -954,6 +957,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> B3::SparseCollection<Node> m_nodes;
</span><ins>+ Vector<AbstractValue> m_abstractValuesCache;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::DFG
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStatecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -41,6 +41,7 @@
</span><span class="cx">
</span><span class="cx"> InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
</span><span class="cx"> : m_graph(graph)
</span><ins>+ , m_abstractValues(graph.abstractValuesCache())
</ins><span class="cx"> , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
</span><span class="cx"> , m_block(0)
</span><span class="cx"> {
</span><span class="lines">@@ -55,6 +56,11 @@
</span><span class="cx"> ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
</span><span class="cx"> ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
</span><span class="cx"> ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
</span><ins>+
+ // 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());
</ins><span class="cx">
</span><span class="cx"> for (size_t i = 0; i < basicBlock->size(); i++)
</span><span class="cx"> forNode(basicBlock->at(i)).clear();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInPlaceAbstractStateh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -48,7 +48,7 @@
</span><span class="cx">
</span><span class="cx"> AbstractValue& forNode(Node* node)
</span><span class="cx"> {
</span><del>- return node->value;
</del><ins>+ return m_abstractValues[node->index()];
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> AbstractValue& forNode(Edge edge)
</span><span class="lines">@@ -132,7 +132,8 @@
</span><span class="cx"> static bool mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode);
</span><span class="cx">
</span><span class="cx"> Graph& m_graph;
</span><del>-
</del><ins>+
+ Vector<AbstractValue>& m_abstractValues;
</ins><span class="cx"> Operands<AbstractValue> m_variables;
</span><span class="cx"> BasicBlock* m_block;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGLivenessAnalysisPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -195,6 +195,8 @@
</span><span class="cx">
</span><span class="cx"> bool performLivenessAnalysis(Graph& graph)
</span><span class="cx"> {
</span><ins>+ graph.packNodeIndices();
+
</ins><span class="cx"> return runPhase<LivenessAnalysisPhase>(graph);
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGNodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGNode.h (204111 => 204112)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGNode.h 2016-08-04 02:36:28 UTC (rev 204111)
+++ trunk/Source/JavaScriptCore/dfg/DFGNode.h 2016-08-04 03:43:51 UTC (rev 204112)
</span><span class="lines">@@ -2362,10 +2362,6 @@
</span><span class="cx"> uintptr_t m_opInfo;
</span><span class="cx"> uintptr_t m_opInfo2;
</span><span class="cx">
</span><del>-public:
- // Fields used by various analyses.
- AbstractValue value;
-
</del><span class="cx"> // Miscellaneous data that is usually meaningless, but can hold some analysis results
</span><span class="cx"> // if you ask right. For example, if you do Graph::initializeNodeOwners(), Node::owner
</span><span class="cx"> // will tell you which basic block a node belongs to. You cannot rely on this persisting
</span></span></pre>
</div>
</div>
</body>
</html>