<!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>[181563] 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/181563">181563</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-03-16 10:39:07 -0700 (Mon, 16 Mar 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>DFG::PutStackSinkingPhase should eliminate GetStacks that have an obviously known source, and emit GetStacks when the stack's value is needed and none is deferred
https://bugs.webkit.org/show_bug.cgi?id=141624
Reviewed by Geoffrey Garen.
Not eliminating GetStacks was an obvious omission from the original PutStackSinkingPhase.
Previously, we would treat GetStacks conservatively and assume that the stack slot
escaped. That's pretty dumb, since a GetStack is a local load of the stack. This change
makes GetStack a no-op from the standpoint of this phase's deferral analysis. At the end
we either keep the GetStack (if there was no concrete deferral) or we replace it with an
identity over the value that would have been stored by the deferred PutStack. Note that
this might be a Phi that the phase creates, so this is strictly stronger than what GCSE
could do.
But this change revealed the fact that this phase never correctly handled side effects in
case that we had done a GetStack, then a side-effect, and then found ourselves wanting the
value on the stack due to (for example) a Phi on a deferred PutStack and that GetStack.
Basically, it's only correct to use the SSA converter's incoming value mapping if we have
a concrete deferral - since anything but a concrete deferral may imply that the value has
been clobbered.
This has no performance change. I believe that the bug was previously benign because we
have so few operations that clobber the stack anymore, and most of those get used in a
very idiomatic way. The GetStack elimination will be very useful for the varargs
simplification that is part of bug 141174.
This includes a test for the case that Speedometer hit, plus tests for the other cases I
thought of once I realized the deeper issue.
* dfg/DFGPutStackSinkingPhase.cpp:
* tests/stress/get-stack-identity-due-to-sinking.js: Added.
(foo):
(bar):
* tests/stress/get-stack-mapping-with-dead-get-stack.js: Added.
(bar):
(foo):
* tests/stress/get-stack-mapping.js: Added.
(bar):
(foo):
* tests/stress/weird-put-stack-varargs.js: Added.
(baz):
(foo):
(fuzz):
(bar):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPutStackSinkingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstressgetstackidentityduetosinkingjs">trunk/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstressgetstackmappingwithdeadgetstackjs">trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstressgetstackmappingjs">trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping.js</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstressweirdputstackvarargsjs">trunk/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (181562 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-03-16 17:13:04 UTC (rev 181562)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -1,3 +1,50 @@
</span><ins>+2015-03-15 Filip Pizlo <fpizlo@apple.com>
+
+ DFG::PutStackSinkingPhase should eliminate GetStacks that have an obviously known source, and emit GetStacks when the stack's value is needed and none is deferred
+ https://bugs.webkit.org/show_bug.cgi?id=141624
+
+ Reviewed by Geoffrey Garen.
+
+ Not eliminating GetStacks was an obvious omission from the original PutStackSinkingPhase.
+ Previously, we would treat GetStacks conservatively and assume that the stack slot
+ escaped. That's pretty dumb, since a GetStack is a local load of the stack. This change
+ makes GetStack a no-op from the standpoint of this phase's deferral analysis. At the end
+ we either keep the GetStack (if there was no concrete deferral) or we replace it with an
+ identity over the value that would have been stored by the deferred PutStack. Note that
+ this might be a Phi that the phase creates, so this is strictly stronger than what GCSE
+ could do.
+
+ But this change revealed the fact that this phase never correctly handled side effects in
+ case that we had done a GetStack, then a side-effect, and then found ourselves wanting the
+ value on the stack due to (for example) a Phi on a deferred PutStack and that GetStack.
+ Basically, it's only correct to use the SSA converter's incoming value mapping if we have
+ a concrete deferral - since anything but a concrete deferral may imply that the value has
+ been clobbered.
+
+ This has no performance change. I believe that the bug was previously benign because we
+ have so few operations that clobber the stack anymore, and most of those get used in a
+ very idiomatic way. The GetStack elimination will be very useful for the varargs
+ simplification that is part of bug 141174.
+
+ This includes a test for the case that Speedometer hit, plus tests for the other cases I
+ thought of once I realized the deeper issue.
+
+ * dfg/DFGPutStackSinkingPhase.cpp:
+ * tests/stress/get-stack-identity-due-to-sinking.js: Added.
+ (foo):
+ (bar):
+ * tests/stress/get-stack-mapping-with-dead-get-stack.js: Added.
+ (bar):
+ (foo):
+ * tests/stress/get-stack-mapping.js: Added.
+ (bar):
+ (foo):
+ * tests/stress/weird-put-stack-varargs.js: Added.
+ (baz):
+ (foo):
+ (fuzz):
+ (bar):
+
</ins><span class="cx"> 2015-03-16 Joseph Pecoraro <pecoraro@apple.com>
</span><span class="cx">
</span><span class="cx"> Update Map/Set to treat -0 and 0 as the same value
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPutStackSinkingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp (181562 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp 2015-03-16 17:13:04 UTC (rev 181562)
+++ trunk/Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -221,6 +221,12 @@
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ if (node->op() == GetStack) {
+ // A GetStack doesn't affect anything, since we know which local we are reading
+ // from.
+ continue;
+ }
+
</ins><span class="cx"> auto escapeHandler = [&] (VirtualRegister operand) {
</span><span class="cx"> if (operand.isHeader())
</span><span class="cx"> return;
</span><span class="lines">@@ -390,6 +396,29 @@
</span><span class="cx"> deferred.operand(node->unlinkedLocal()) = ConflictingFlush;
</span><span class="cx"> break;
</span><span class="cx"> }
</span><ins>+
+ case GetStack: {
+ StackAccessData* data = node->stackAccessData();
+ FlushFormat format = deferred.operand(data->local);
+ if (!isConcrete(format)) {
+ // This means there is no deferral. No deferral means that the most
+ // authoritative value for this stack slot is what is stored in the stack. So,
+ // keep the GetStack.
+ mapping.operand(data->local) = node;
+ break;
+ }
+
+ // We have a concrete deferral, which means a PutStack that hasn't executed yet. It
+ // would have stored a value with a certain format. That format must match our
+ // format. But more importantly, we can simply use the value that the PutStack would
+ // have stored and get rid of the GetStack.
+ DFG_ASSERT(m_graph, node, format == data->format);
+
+ Node* incoming = mapping.operand(data->local);
+ node->child1() = incoming->defaultEdge();
+ node->convertToIdentity();
+ break;
+ }
</ins><span class="cx">
</span><span class="cx"> default: {
</span><span class="cx"> auto escapeHandler = [&] (VirtualRegister operand) {
</span><span class="lines">@@ -418,16 +447,6 @@
</span><span class="cx"> preciseLocalClobberize(
</span><span class="cx"> m_graph, node, escapeHandler, escapeHandler,
</span><span class="cx"> [&] (VirtualRegister, Node*) { });
</span><del>-
- // If we're a GetStack, then we also create a mapping.
- // FIXME: We should be able to just eliminate such GetLocals, when we know
- // what their incoming value will be.
- // https://bugs.webkit.org/show_bug.cgi?id=141624
- if (node->op() == GetStack) {
- StackAccessData* data = node->stackAccessData();
- VirtualRegister operand = data->local;
- mapping.operand(operand) = node;
- }
</del><span class="cx"> break;
</span><span class="cx"> } }
</span><span class="cx"> }
</span><span class="lines">@@ -444,34 +463,24 @@
</span><span class="cx"> FlushFormat format = deferredAtHead[successorBlock].operand(operand);
</span><span class="cx"> DFG_ASSERT(m_graph, nullptr, isConcrete(format));
</span><span class="cx"> UseKind useKind = useKindFor(format);
</span><del>- Node* incoming = mapping.operand(operand);
- if (!incoming) {
- // This can totally happen, see tests/stress/put-local-conservative.js.
- // This arises because deferral and liveness are both conservative.
- // Conservative liveness means that a load from a *different* closure
- // variable may lead us to believe that our local is live. Conservative
- // deferral may lead us to believe that the local doesn't have a top deferral
- // because someone has done something that would have forced it to be
- // materialized. The basic pattern is:
- //
- // GetClosureVar(loc42) // loc42's deferral is now bottom
- // if (predicate1)
- // PutClosureVar(loc42) // prevent GCSE of our GetClosureVar's
- // if (predicate2)
- // PutStack(loc42) // we now have a concrete deferral
- // // we still have the concrete deferral because we merged with bottom
- // GetClosureVar(loc42) // force materialization
- //
- // We will have a Phi with no incoming value form the basic block that
- // bypassed the PutStack.
-
- // Note: we sort of could have used the equivalent of LLVM's undef here. The
- // point is that it's OK to just leave random bits in the local if we're
- // coming down this path. But, we don't have a way of saying that in our IR
- // right now and anyway it probably doesn't matter that much.
-
- incoming = insertionSet.insertBottomConstantForUse(
- upsilonInsertionPoint, upsilonOrigin, useKind).node();
</del><ins>+
+ // We need to get a value for the stack slot. This phase doesn't really have a
+ // good way of determining if a stack location got clobbered. It just knows if
+ // there is a deferral. The lack of a deferral might mean that a PutStack or
+ // GetStack had never happened, or it might mean that the value was read, or
+ // that it was written. It's OK for us to make some bad decisions here, since
+ // GCSE will clean it up anyway.
+ Node* incoming;
+ if (isConcrete(deferred.operand(operand))) {
+ incoming = mapping.operand(operand);
+ DFG_ASSERT(m_graph, phiNode, incoming);
+ } else {
+ // Issue a GetStack to get the value. This might introduce some redundancy
+ // into the code, but if it's bad enough, GCSE will clean it up.
+ incoming = insertionSet.insertNode(
+ upsilonInsertionPoint, SpecNone, GetStack, upsilonOrigin,
+ OpInfo(m_graph.m_stackAccessData.add(operand, format)));
+ incoming->setResult(resultFor(format));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> insertionSet.insertNode(
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressgetstackidentityduetosinkingjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js (0 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/get-stack-identity-due-to-sinking.js 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -0,0 +1,18 @@
</span><ins>+function foo(p, a) {
+ if (p) {
+ var tmp = arguments;
+ }
+ return a;
+}
+
+function bar(p, a) {
+ return foo(p, a);
+}
+
+noInline(bar);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = bar(false, 42);
+ if (result != 42)
+ throw "Error: bad result: " + result;
+}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressgetstackmappingwithdeadgetstackjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js (0 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping-with-dead-get-stack.js 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -0,0 +1,27 @@
</span><ins>+function bar() {
+ if (foo.arguments[0] === void 0)
+ throw "Error: foo.arguments[0] should not be undefined but is."
+}
+
+noInline(bar);
+
+function foo(a, p) {
+ var tmp = a;
+ effectful42();
+ for (var i = 0; i < 10; ++i) {
+ bar();
+ a = i;
+ }
+ if (p) {
+ var tmp = arguments;
+ }
+ return a;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(0, false);
+ if (result != 9)
+ throw "Error: bad result: " + result;
+}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressgetstackmappingjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping.js (0 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/get-stack-mapping.js 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -0,0 +1,26 @@
</span><ins>+function bar() {
+ if (foo.arguments[0] === void 0)
+ throw "Error: foo.arguments[0] should not be undefined but is."
+}
+
+noInline(bar);
+
+function foo(a, p) {
+ effectful42();
+ for (var i = 0; i < 10; ++i) {
+ bar();
+ a = i;
+ }
+ if (p) {
+ var tmp = arguments;
+ }
+ return a;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 10000; ++i) {
+ var result = foo(0, false);
+ if (result != 9)
+ throw "Error: bad result: " + result;
+}
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressweirdputstackvarargsjs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js (0 => 181563)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/weird-put-stack-varargs.js 2015-03-16 17:39:07 UTC (rev 181563)
</span><span class="lines">@@ -0,0 +1,26 @@
</span><ins>+function baz() {
+ if (!foo.arguments[1])
+ throw "Error: foo.arguments[1] should be truthy but is falsy: " + foo.arguments[1];
+}
+
+noInline(baz);
+
+function foo(a, b) {
+ if (a)
+ b = 42;
+ baz();
+}
+
+function fuzz(a, b) {
+ return a + b;
+}
+
+function bar(array1, array2) {
+ fuzz.apply(this, array1);
+ foo.apply(this, array2);
+}
+
+noInline(bar);
+
+for (var i = 0; i < 100000; ++i)
+ bar([false, false], [false, true]);
</ins></span></pre>
</div>
</div>
</body>
</html>