<!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>[184206] 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/184206">184206</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-05-12 11:01:28 -0700 (Tue, 12 May 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>OSR availability analysis would be more scalable (and correct) if it did more liveness pruning
https://bugs.webkit.org/show_bug.cgi?id=143078
Reviewed by Andreas Kling.
In https://bugs.webkit.org/show_bug.cgi?id=144883, we found an example of where liveness
pruning is actually necessary. Well, not quite: we just need to prune out keys from the
heap availability map where the base node doesn't dominate the point where we are asking
for availability. If we don't do this, then eventually the IR gets corrupt because we'll
insert PutHints that reference the base node in places where the base node doesn't
dominate. But if we're going to do any pruning, then it makes sense to prune by bytecode
liveness. This is the strongest possible pruning we can do, and it should be sound. We
shouldn't have a node available for a virtual register if that register is live and the
node doesn't dominate.
Making this work meant reusing the prune-to-liveness algorithm from the FTL backend. So, I
abstracted this a bit better. You can now availabilityMap.pruneByLiveness(graph, origin).
* dfg/DFGAvailabilityMap.cpp:
(JSC::DFG::AvailabilityMap::pruneHeap):
(JSC::DFG::AvailabilityMap::pruneByLiveness):
(JSC::DFG::AvailabilityMap::prune): Deleted.
* dfg/DFGAvailabilityMap.h:
* dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
(JSC::DFG::OSRAvailabilityAnalysisPhase::run):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::buildExitArguments):
* tests/stress/liveness-pruning-needed-for-osr-availability.js: Added. This is a proper regression test.
* tests/stress/liveness-pruning-needed-for-osr-availability-eager.js: Added. This is the original reduced test case, requires eager-no-cjit to fail prior to this changeset.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAvailabilityMapcpp">trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGAvailabilityMaph">trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGOSRAvailabilityAnalysisPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp">trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstresslivenesspruningneededforosravailabilityeagerjs">trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstresslivenesspruningneededforosravailabilityjs">trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (184205 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+2015-05-11 Filip Pizlo <fpizlo@apple.com>
+
+ OSR availability analysis would be more scalable (and correct) if it did more liveness pruning
+ https://bugs.webkit.org/show_bug.cgi?id=143078
+
+ Reviewed by Andreas Kling.
+
+ In https://bugs.webkit.org/show_bug.cgi?id=144883, we found an example of where liveness
+ pruning is actually necessary. Well, not quite: we just need to prune out keys from the
+ heap availability map where the base node doesn't dominate the point where we are asking
+ for availability. If we don't do this, then eventually the IR gets corrupt because we'll
+ insert PutHints that reference the base node in places where the base node doesn't
+ dominate. But if we're going to do any pruning, then it makes sense to prune by bytecode
+ liveness. This is the strongest possible pruning we can do, and it should be sound. We
+ shouldn't have a node available for a virtual register if that register is live and the
+ node doesn't dominate.
+
+ Making this work meant reusing the prune-to-liveness algorithm from the FTL backend. So, I
+ abstracted this a bit better. You can now availabilityMap.pruneByLiveness(graph, origin).
+
+ * dfg/DFGAvailabilityMap.cpp:
+ (JSC::DFG::AvailabilityMap::pruneHeap):
+ (JSC::DFG::AvailabilityMap::pruneByLiveness):
+ (JSC::DFG::AvailabilityMap::prune): Deleted.
+ * dfg/DFGAvailabilityMap.h:
+ * dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
+ (JSC::DFG::OSRAvailabilityAnalysisPhase::run):
+ * ftl/FTLLowerDFGToLLVM.cpp:
+ (JSC::FTL::LowerDFGToLLVM::buildExitArguments):
+ * tests/stress/liveness-pruning-needed-for-osr-availability.js: Added. This is a proper regression test.
+ * tests/stress/liveness-pruning-needed-for-osr-availability-eager.js: Added. This is the original reduced test case, requires eager-no-cjit to fail prior to this changeset.
+
</ins><span class="cx"> 2015-05-12 Gabor Loki <loki@webkit.org>
</span><span class="cx">
</span><span class="cx"> Workaround for Cortex-A53 erratum 843419
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAvailabilityMapcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp (184205 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.cpp 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -28,12 +28,14 @@
</span><span class="cx">
</span><span class="cx"> #if ENABLE(DFG_JIT)
</span><span class="cx">
</span><ins>+#include "DFGGraph.h"
+#include "JSCInlines.h"
</ins><span class="cx"> #include "OperandsInlines.h"
</span><span class="cx"> #include <wtf/ListDump.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><del>-void AvailabilityMap::prune()
</del><ins>+void AvailabilityMap::pruneHeap()
</ins><span class="cx"> {
</span><span class="cx"> if (m_heap.isEmpty())
</span><span class="cx"> return;
</span><span class="lines">@@ -61,6 +63,18 @@
</span><span class="cx"> m_heap = newHeap;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+void AvailabilityMap::pruneByLiveness(Graph& graph, CodeOrigin where)
+{
+ Operands<Availability> localsCopy(OperandsLike, m_locals);
+ graph.forAllLiveInBytecode(
+ where,
+ [&] (VirtualRegister reg) {
+ localsCopy.operand(reg) = m_locals.operand(reg);
+ });
+ m_locals = localsCopy;
+ pruneHeap();
+}
+
</ins><span class="cx"> void AvailabilityMap::clear()
</span><span class="cx"> {
</span><span class="cx"> m_locals.fill(Availability());
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGAvailabilityMaph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.h (184205 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.h 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/JavaScriptCore/dfg/DFGAvailabilityMap.h 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2014 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -34,7 +34,8 @@
</span><span class="cx"> namespace JSC { namespace DFG {
</span><span class="cx">
</span><span class="cx"> struct AvailabilityMap {
</span><del>- void prune();
</del><ins>+ void pruneHeap();
+ void pruneByLiveness(Graph&, CodeOrigin);
</ins><span class="cx"> void clear();
</span><span class="cx">
</span><span class="cx"> void dump(PrintStream& out) const;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGOSRAvailabilityAnalysisPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp (184205 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -82,10 +82,6 @@
</span><span class="cx"> for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex)
</span><span class="cx"> calculator.executeNode(block->at(nodeIndex));
</span><span class="cx">
</span><del>- // FIXME: we should probably prune by liveness here.
- // https://bugs.webkit.org/show_bug.cgi?id=143078
- calculator.m_availability.prune();
-
</del><span class="cx"> if (calculator.m_availability == block->ssa->availabilityAtTail)
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="lines">@@ -95,6 +91,8 @@
</span><span class="cx"> for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
</span><span class="cx"> BasicBlock* successor = block->successor(successorIndex);
</span><span class="cx"> successor->ssa->availabilityAtHead.merge(calculator.m_availability);
</span><ins>+ successor->ssa->availabilityAtHead.pruneByLiveness(
+ m_graph, successor->firstOrigin().forExit);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> } while (changed);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreftlFTLLowerDFGToLLVMcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp (184205 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-05-12 17:30:56 UTC (rev 184205)
+++ trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -8006,17 +8006,8 @@
</span><span class="cx"> arguments.append(lowValue.value());
</span><span class="cx">
</span><span class="cx"> AvailabilityMap availabilityMap = this->availabilityMap();
</span><del>- availabilityMap.m_locals.fill(Availability());
</del><ins>+ availabilityMap.pruneByLiveness(m_graph, codeOrigin);
</ins><span class="cx">
</span><del>- m_graph.forAllLiveInBytecode(
- codeOrigin,
- [&] (VirtualRegister reg) {
- availabilityMap.m_locals.operand(reg) =
- this->availabilityMap().m_locals.operand(reg);
- });
-
- availabilityMap.prune();
-
</del><span class="cx"> HashMap<Node*, ExitTimeObjectMaterialization*> map;
</span><span class="cx"> availabilityMap.forEachAvailability(
</span><span class="cx"> [&] (Availability availability) {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstresslivenesspruningneededforosravailabilityeagerjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js (0 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability-eager.js 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -0,0 +1,16 @@
</span><ins>+// Note that this only fails in eager compilation.
+
+function each(ary, func) {
+ if (ary)
+ for (var i = 0; i < ary.length && (!ary[i] ||!func(ary[i], i, ary)); i += 1);
+}
+
+var blah = function () {
+ var func = function() {
+ return (function () { }).apply(Object, arguments);
+ };
+ each([ {}, {} ], func);
+};
+
+for (var i = 0; i < 1000; i++)
+ blah();
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstresslivenesspruningneededforosravailabilityjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability.js (0 => 184206)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/liveness-pruning-needed-for-osr-availability.js 2015-05-12 18:01:28 UTC (rev 184206)
</span><span class="lines">@@ -0,0 +1,15 @@
</span><ins>+function each(ary, func) {
+ for (var i = 0; i < ary.length && (!ary[i] ||!func(ary[i], i, ary)); i += 1);
+}
+
+function foo() {
+ each(
+ [ {}, {} ],
+ function () {
+ return (function (x) { })(arguments);
+ });
+};
+noInline(foo);
+
+for (var i = 0; i < 100000; i++)
+ foo();
</ins></span></pre>
</div>
</div>
</body>
</html>