<!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>[198621] 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/198621">198621</a></dd>
<dt>Author</dt> <dd>commit-queue@webkit.org</dd>
<dt>Date</dt> <dd>2016-03-24 02:02:55 -0700 (Thu, 24 Mar 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] In some cases, the integer range optimization phase never converges
https://bugs.webkit.org/show_bug.cgi?id=155828
rdar://problem/25155460
Patch by Benjamin Poulain <bpoulain@apple.com> on 2016-03-24
Reviewed by Filip Pizlo.
In certain conditions, the integer range optimization phase continuously
changes the representation of the same truth, preventing it from
converging to a stable state.
The bug starts by having the same ground truth incomming into a block
in different valid forms. For example, you can have x < 42 coming as:
1) x < 42
2) x < 41 + 1
3) x < 43 - 1
Having those 3 alone coming from predecessors would be okay, we would
just accumulate them. The problem is when you have a combination
of rule that filter out the previously obtained truth, then add a new
form of the same truth.
Let's use the test case as an example. We have two incoming blocks:
Block #1:
-i < 42
-i != 41
Block #2:
-i < 41
-i == 42 - 42 (i == 0 refining the rule above).
Let say that our conditions at head are now [i < 41, i < 42 - 1].
If we merge block #2:
-i < 42 and i < 41 -> i < 42
-i < 42 and i < 42 - 1 -> i < 42
-i != 41 and i < 41 -> i < 41
-i != 41 and i < 42 - 1 -> nothing
The new head is: [i < 41, i < 42]
If we merge block #1:
-i < 41 and i < 41 -> i < 41
-i < 41 and i < 42 -> i < 42
-i == 42 - 42 and i < 41 -> (i < 41 and i < 42 - 1)
-i == 42 - 42 and i < 42 -> i < 42
After filter, we are back to [i < 41, i < 42 - 1].
There are several variations of this idea where the same truth
rotate different forms with each merge().
One possible solution is to make filter() more aggressive
to avoid the better form occuring at merge(). I'll probably
do that at some point but that seems fragile since the same
problem could reappear if merge() is later improved.
For this patch, I went with a more generic solution after
merge(): if the generated form is equivalent to one that
previously existed at head, pick the existing form.
In the previous example, what happens is we only have
either [i < 41] or [i < 42 - 1] but never both simultaneously.
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* tests/stress/integer-range-optimization-constant-representation-1.js: Added.
* tests/stress/integer-range-optimization-constant-representation-2.js: Added.
Two variation. One timeout in release because of the additional flags.
The other is gets more type of run but only assert in debug.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp">trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoretestsstressintegerrangeoptimizationconstantrepresentation1js">trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-1.js</a></li>
<li><a href="#trunkSourceJavaScriptCoretestsstressintegerrangeoptimizationconstantrepresentation2js">trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-2.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (198620 => 198621)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2016-03-24 08:10:01 UTC (rev 198620)
+++ trunk/Source/JavaScriptCore/ChangeLog 2016-03-24 09:02:55 UTC (rev 198621)
</span><span class="lines">@@ -1,3 +1,73 @@
</span><ins>+2016-03-24 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] In some cases, the integer range optimization phase never converges
+ https://bugs.webkit.org/show_bug.cgi?id=155828
+ rdar://problem/25155460
+
+ Reviewed by Filip Pizlo.
+
+ In certain conditions, the integer range optimization phase continuously
+ changes the representation of the same truth, preventing it from
+ converging to a stable state.
+
+ The bug starts by having the same ground truth incomming into a block
+ in different valid forms. For example, you can have x < 42 coming as:
+ 1) x < 42
+ 2) x < 41 + 1
+ 3) x < 43 - 1
+
+ Having those 3 alone coming from predecessors would be okay, we would
+ just accumulate them. The problem is when you have a combination
+ of rule that filter out the previously obtained truth, then add a new
+ form of the same truth.
+
+ Let's use the test case as an example. We have two incoming blocks:
+ Block #1:
+ -i < 42
+ -i != 41
+ Block #2:
+ -i < 41
+ -i == 42 - 42 (i == 0 refining the rule above).
+
+ Let say that our conditions at head are now [i < 41, i < 42 - 1].
+
+ If we merge block #2:
+ -i < 42 and i < 41 -> i < 42
+ -i < 42 and i < 42 - 1 -> i < 42
+ -i != 41 and i < 41 -> i < 41
+ -i != 41 and i < 42 - 1 -> nothing
+
+ The new head is: [i < 41, i < 42]
+
+ If we merge block #1:
+ -i < 41 and i < 41 -> i < 41
+ -i < 41 and i < 42 -> i < 42
+ -i == 42 - 42 and i < 41 -> (i < 41 and i < 42 - 1)
+ -i == 42 - 42 and i < 42 -> i < 42
+
+ After filter, we are back to [i < 41, i < 42 - 1].
+
+ There are several variations of this idea where the same truth
+ rotate different forms with each merge().
+
+ One possible solution is to make filter() more aggressive
+ to avoid the better form occuring at merge(). I'll probably
+ do that at some point but that seems fragile since the same
+ problem could reappear if merge() is later improved.
+
+ For this patch, I went with a more generic solution after
+ merge(): if the generated form is equivalent to one that
+ previously existed at head, pick the existing form.
+
+ In the previous example, what happens is we only have
+ either [i < 41] or [i < 42 - 1] but never both simultaneously.
+
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+ * tests/stress/integer-range-optimization-constant-representation-1.js: Added.
+ * tests/stress/integer-range-optimization-constant-representation-2.js: Added.
+ Two variation. One timeout in release because of the additional flags.
+ The other is gets more type of run but only assert in debug.
+
</ins><span class="cx"> 2016-03-23 Commit Queue <commit-queue@webkit.org>
</span><span class="cx">
</span><span class="cx"> Unreviewed, rolling out r198582.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp (198620 => 198621)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-03-24 08:10:01 UTC (rev 198620)
+++ trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-03-24 09:02:55 UTC (rev 198621)
</span><span class="lines">@@ -42,6 +42,7 @@
</span><span class="cx"> namespace {
</span><span class="cx">
</span><span class="cx"> const bool verbose = false;
</span><ins>+const unsigned giveUpThreshold = 50;
</ins><span class="cx">
</span><span class="cx"> int64_t clampedSumImpl() { return 0; }
</span><span class="cx">
</span><span class="lines">@@ -217,6 +218,19 @@
</span><span class="cx"> return m_left == other.m_left
</span><span class="cx"> && m_right == other.m_right;
</span><span class="cx"> }
</span><ins>+
+ bool isEquivalentTo(const Relationship& other) const
+ {
+ if (m_left != other.m_left || m_kind != other.m_kind)
+ return false;
+
+ if (*this == other)
+ return true;
+
+ if (m_right->isInt32Constant() && other.m_right->isInt32Constant())
+ return (m_right->asInt32() + m_offset) == (other.m_right->asInt32() + other.m_offset);
+ return false;
+ }
</ins><span class="cx">
</span><span class="cx"> bool operator==(const Relationship& other) const
</span><span class="cx"> {
</span><span class="lines">@@ -1072,6 +1086,19 @@
</span><span class="cx"> // the comment above Relationship::merge() for details.
</span><span class="cx"> bool changed = true;
</span><span class="cx"> while (changed) {
</span><ins>+ ++m_iterations;
+ if (m_iterations >= giveUpThreshold) {
+ // This case is not necessarily wrong but it can be a sign that this phase
+ // does not converge.
+ // If you hit this assertion for a legitimate case, update the giveUpThreshold
+ // to the smallest values that converges.
+ ASSERT_NOT_REACHED();
+
+ // In release, do not risk holding the thread for too long since this phase
+ // is really slow.
+ return false;
+ }
+
</ins><span class="cx"> changed = false;
</span><span class="cx"> for (unsigned postOrderIndex = postOrder.size(); postOrderIndex--;) {
</span><span class="cx"> BasicBlock* block = postOrder[postOrderIndex];
</span><span class="lines">@@ -1682,7 +1709,13 @@
</span><span class="cx"> changed = true;
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><del>-
</del><ins>+
+ Vector<Relationship> constantRelationshipsAtHead;
+ for (Relationship& relationshipAtHead : entry.value) {
+ if (relationshipAtHead.right()->isInt32Constant())
+ constantRelationshipsAtHead.append(relationshipAtHead);
+ }
+
</ins><span class="cx"> Vector<Relationship> mergedRelationships;
</span><span class="cx"> for (Relationship targetRelationship : entry.value) {
</span><span class="cx"> for (Relationship sourceRelationship : iter->value) {
</span><span class="lines">@@ -1693,6 +1726,24 @@
</span><span class="cx"> [&] (Relationship newRelationship) {
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Got ", newRelationship, "\n");
</span><ins>+
+ if (newRelationship.right()->isInt32Constant()) {
+ // We can produce a relationship with a constant equivalent to
+ // an existing relationship yet of a different form. For example:
+ //
+ // @a == @b(42) + 0
+ // @a == @c(41) + 1
+ //
+ // We do not want to perpetually switch between those two forms,
+ // so we always prefer the one already at head.
+
+ for (Relationship& existingRelationshipAtHead : constantRelationshipsAtHead) {
+ if (existingRelationshipAtHead.isEquivalentTo(newRelationship)) {
+ newRelationship = existingRelationshipAtHead;
+ break;
+ }
+ }
+ }
</ins><span class="cx">
</span><span class="cx"> // We need to filter() to avoid exponential explosion of identical
</span><span class="cx"> // relationships. We do this here to avoid making setOneSide() do
</span><span class="lines">@@ -1764,6 +1815,8 @@
</span><span class="cx"> BlockSet m_seenBlocks;
</span><span class="cx"> BlockMap<RelationshipMap> m_relationshipsAtHead;
</span><span class="cx"> InsertionSet m_insertionSet;
</span><ins>+
+ unsigned m_iterations { 0 };
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } // anonymous namespace
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressintegerrangeoptimizationconstantrepresentation1js"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-1.js (0 => 198621)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-1.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-1.js 2016-03-24 09:02:55 UTC (rev 198621)
</span><span class="lines">@@ -0,0 +1,46 @@
</span><ins>+//@ run("integer-range-optimization-constant-representation", *NO_CJIT_OPTIONS, "--useConcurrentJIT=false")
+//@ run("integer-range-optimization-constant-representation", *FTL_OPTIONS, "--useConcurrentJIT=false")
+
+function opaque()
+{
+ // This exists to hide side effects to the optimizer.
+}
+noInline(opaque);
+
+function test(i, opaqueCondition) {
+ do {
+ if (opaqueCondition == 1) {
+ if (i < 42) {
+ opaque(i);
+ if (i != 41) {
+ break;
+ }
+ }
+ } else if (opaqueCondition == 2) {
+ if (i < 42) {
+ opaque(i);
+ if (i < 41) {
+ opaque(i);
+ if (i == 0) {
+ break;
+ }
+ }
+ }
+ }
+ } while (true);
+
+ opaque(i);
+ opaque(42);
+ opaque(41);
+ return i;
+}
+noInline(test);
+
+function loop() {
+ for (let i = 0; i < 1e6; ++i)
+ test(1, 1);
+}
+noInline(loop);
+noDFG(loop);
+
+loop();
</ins><span class="cx">\ No newline at end of file
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoretestsstressintegerrangeoptimizationconstantrepresentation2js"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-2.js (0 => 198621)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-2.js (rev 0)
+++ trunk/Source/JavaScriptCore/tests/stress/integer-range-optimization-constant-representation-2.js 2016-03-24 09:02:55 UTC (rev 198621)
</span><span class="lines">@@ -0,0 +1,43 @@
</span><ins>+function opaque()
+{
+ // This exists to hide side effects to the optimizer.
+}
+noInline(opaque);
+
+function test(i, opaqueCondition) {
+ do {
+ if (opaqueCondition == 1) {
+ if (i < 42) {
+ opaque(i);
+ if (i != 41) {
+ break;
+ }
+ }
+ } else if (opaqueCondition == 2) {
+ if (i < 42) {
+ opaque(i);
+ if (i < 41) {
+ opaque(i);
+ if (i == 0) {
+ break;
+ }
+ }
+ }
+ }
+ } while (true);
+
+ opaque(i);
+ opaque(42);
+ opaque(41);
+ return i;
+}
+noInline(test);
+
+function loop() {
+ for (let i = 0; i < 1e6; ++i)
+ test(1, 1);
+}
+noInline(loop);
+noDFG(loop);
+
+loop();
</ins></span></pre>
</div>
</div>
</body>
</html>