<!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>[177270] 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/177270">177270</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2014-12-14 19:49:27 -0800 (Sun, 14 Dec 2014)</dd>
</dl>
<h3>Log Message</h3>
<pre>PutLocalSinkingPhase has an invalid assertion about incoming values, because both liveness and deferral analyses are conservative
https://bugs.webkit.org/show_bug.cgi?id=139630
Reviewed by Oliver Hunt.
Replaces a faulty assertion with code to handle an awesome special case. Also adds a lot of
comments that reconstruct my reasoning about this code. I had to work hard to remember how
deferral worked so I wrote my discoveries down.
* dfg/DFGInsertionSet.h:
(JSC::DFG::InsertionSet::insertBottomConstantForUse):
* dfg/DFGPutLocalSinkingPhase.cpp:
* tests/stress/put-local-conservative.js: Added.
(foo):
(.result):
(bar):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGInsertionSeth">trunk/Source/JavaScriptCore/dfg/DFGInsertionSet.h</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGPutLocalSinkingPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstressputlocalconservativejs">trunk/Source/JavaScriptCore/tests/stress/put-local-conservative.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (177269 => 177270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2014-12-15 02:50:22 UTC (rev 177269)
+++ trunk/Source/JavaScriptCore/ChangeLog 2014-12-15 03:49:27 UTC (rev 177270)
</span><span class="lines">@@ -1,3 +1,22 @@
</span><ins>+2014-12-14 Filip Pizlo <fpizlo@apple.com>
+
+ PutLocalSinkingPhase has an invalid assertion about incoming values, because both liveness and deferral analyses are conservative
+ https://bugs.webkit.org/show_bug.cgi?id=139630
+
+ Reviewed by Oliver Hunt.
+
+ Replaces a faulty assertion with code to handle an awesome special case. Also adds a lot of
+ comments that reconstruct my reasoning about this code. I had to work hard to remember how
+ deferral worked so I wrote my discoveries down.
+
+ * dfg/DFGInsertionSet.h:
+ (JSC::DFG::InsertionSet::insertBottomConstantForUse):
+ * dfg/DFGPutLocalSinkingPhase.cpp:
+ * tests/stress/put-local-conservative.js: Added.
+ (foo):
+ (.result):
+ (bar):
+
</ins><span class="cx"> 2014-12-14 Andreas Kling <akling@apple.com>
</span><span class="cx">
</span><span class="cx"> Replace PassRef with Ref/Ref&& across the board.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGInsertionSeth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGInsertionSet.h (177269 => 177270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGInsertionSet.h 2014-12-15 02:50:22 UTC (rev 177269)
+++ trunk/Source/JavaScriptCore/dfg/DFGInsertionSet.h 2014-12-15 03:49:27 UTC (rev 177270)
</span><span class="lines">@@ -115,7 +115,16 @@
</span><span class="cx"> {
</span><span class="cx"> return insertConstantForUse(index, NodeOrigin(origin), value, useKind);
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ Edge insertBottomConstantForUse(size_t index, NodeOrigin origin, UseKind useKind)
+ {
+ if (isDouble(useKind))
+ return insertConstantForUse(index, origin, jsNumber(PNaN), useKind);
+ if (useKind == Int52RepUse)
+ return insertConstantForUse(index, origin, jsNumber(0), useKind);
+ return insertConstantForUse(index, origin, jsUndefined(), useKind);
+ }
+
</ins><span class="cx"> Node* insertOutOfOrder(const Insertion& insertion)
</span><span class="cx"> {
</span><span class="cx"> size_t targetIndex = insertion.index();
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGPutLocalSinkingPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp (177269 => 177270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp 2014-12-15 02:50:22 UTC (rev 177269)
+++ trunk/Source/JavaScriptCore/dfg/DFGPutLocalSinkingPhase.cpp 2014-12-15 03:49:27 UTC (rev 177270)
</span><span class="lines">@@ -214,7 +214,50 @@
</span><span class="cx">
</span><span class="cx"> // Next identify where we would want to sink PutLocals to. We say that there is a deferred
</span><span class="cx"> // flush if we had a PutLocal with a given VariableAccessData* but it hasn't been
</span><del>- // materialized yet.
</del><ins>+ // materialized yet. Deferrals have the following lattice; but it's worth noting that the
+ // TOP part of the lattice serves an entirely different purpose than the rest of the lattice:
+ // it just means that we're in a region of code where nobody should have been relying on the
+ // value. The rest of the lattice means that we either have a PutLocal that is deferred (i.e.
+ // still needs to be executed) or there isn't one (because we've alraedy executed it).
+ //
+ // Bottom:
+ // Instantiated as VariableDeferral().
+ // Means that all previous PutLocals have been executed so there is nothing deferred.
+ // During merging this is subordinate to the other kinds of deferrals, because it
+ // represents the fact that we've already executed all necessary PutLocals. This implies
+ // that there *had* been some PutLocals that we should have executed.
+ //
+ // Top:
+ // Instantiated as VariableDeferral::conflict().
+ // Represents the fact that we know, via forward flow, that there isn't any value in the
+ // given local that anyone should have been relying on. This comes into play at the
+ // prologue (because in SSA form at the prologue no local has any value) or when we merge
+ // deferrals for different VariableAccessData*'s. A VAD encompasses a lexical scope in
+ // which the local has some semantic meaning; if we had stores from different lexical
+ // scopes that got merged together then we know that we're not in either scope anymore.
+ // Note that this is all approximate and only precise enough to later answer questions
+ // pertinent to sinking. For example, this doesn't always detect when a local is no
+ // longer semantically relevant - we may well have a deferral from inside some inlined
+ // call survive outside of that inlined code, and this is generally OK. In the worst case
+ // it means that we might think that a deferral that is actually dead must still be
+ // executed. But we usually catch that with liveness. Liveness doesn't always catch it
+ // because liveness is conservative.
+ //
+ // What Top does give us is detects situations where we both don't need to care about a
+ // deferral and there is no way that we could reason about it anyway. If we merged
+ // deferrals for different variables then we wouldn't know the format to use. So, we
+ // use Top in that case because that's also a case where we know that we can ignore the
+ // deferral.
+ //
+ // Deferral with a concrete VariableAccessData*:
+ // Instantiated as VariableDeferral(someVariableAccessData)
+ // Represents the fact that the original code would have done a PutLocal but we haven't
+ // identified an operation that would have observed that PutLocal.
+ //
+ // This code has some interesting quirks because of the fact that neither liveness nor
+ // deferrals are very precise. They are only precise enough to be able to correctly tell us
+ // when we may [sic] need to execute PutLocals. This means that they may report the need to
+ // execute a PutLocal in cases where we actually don't really need it, and that's totally OK.
</ins><span class="cx"> BlockMap<Operands<VariableDeferral>> deferredAtHead(m_graph);
</span><span class="cx"> BlockMap<Operands<VariableDeferral>> deferredAtTail(m_graph);
</span><span class="cx">
</span><span class="lines">@@ -465,7 +508,34 @@
</span><span class="cx"> FlushFormat format = variableDeferral.variable()->flushFormat();
</span><span class="cx"> UseKind useKind = useKindFor(format);
</span><span class="cx"> Node* incoming = mapping.operand(operand);
</span><del>- DFG_ASSERT(m_graph, nullptr, incoming);
</del><ins>+ 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)
+ // PutLocal(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 PutLocal.
+
+ // 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();
+ }
</ins><span class="cx">
</span><span class="cx"> insertionSet.insertNode(
</span><span class="cx"> upsilonInsertionPoint, SpecNone, Upsilon, upsilonOrigin,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressputlocalconservativejs"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/put-local-conservative.js (0 => 177270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/put-local-conservative.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/put-local-conservative.js 2014-12-15 03:49:27 UTC (rev 177270)
</span><span class="lines">@@ -0,0 +1,47 @@
</span><ins>+function foo(o, a, b, c) {
+ // Don't do anything real but have some control flow. This causes the PutLocals for a,
+ // b, and c to survive into SSA form. But we don't have any effects, so sinking will be
+ // successful.
+ if (o.f)
+ return 42;
+ else
+ return 0;
+}
+
+function bar(o, y) {
+ var a = y;
+ var b = y + 1;
+ var c = y + 2;
+ var d = y + 3;
+ var e = y + 4;
+ var f = y + 5;
+ var g = y + 6;
+ var h = y + 7;
+ var i = y + 8;
+ var j = y + 9;
+ var k = y + 10;
+ var result = function(p, q) {
+ var x = a + b + c + d + e + f + g + h + i + j + k;
+ if (q) {
+ // Make it appear that it's possible to clobber those closure variables, so that we
+ // load from them again down below.
+ a = b = c = d = e = f = g = h = i = j = k = 42;
+ }
+ if (p)
+ x = foo(o, 1, 2, 3)
+ else
+ x = 5;
+ return x + a + b + c + d + e + f + g + h + i + j + k;
+ };
+ noInline(result);
+ return result;
+}
+
+var o = {f: 42};
+
+for (var i = 0; i < 100000; ++i) {
+ var result = bar(o, i)(true, false);
+ if (result != 42 + 11 * i + 55)
+ throw "Error: bad result: " + result;
+}
+
</ins></span></pre>
</div>
</div>
</body>
</html>