<!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>[188720] trunk</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/188720">188720</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-08-20 17:26:41 -0700 (Thu, 20 Aug 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Overflow check elimination fails for a simple test case
https://bugs.webkit.org/show_bug.cgi?id=147387
Reviewed by Benjamin Poulain.
Source/JavaScriptCore:
Overflow check elimination was having issues when things got constant-folded, because whereas an
Add or LessThan operation teaches us about relationships between the things being added or
compared, we don't do that when we see a JSConstant. We don't create a relationship between every
JSConstant and every other JSConstant. So, if we constant-fold an Add, we forget the relationships
that it would have had with its inputs.
One solution would be to have every JSConstant create a relationship with every other JSConstant.
This is dangerous, since it would create O(n^2) explosion of relationships.
Instead, this patch teaches filtration and merging how to behave "as if" there were inter-constant
relationships. Normally those operations only work on two relationships involving the same node
pair. But now, if we have @x op @c and @x op @d, where @c and @d are different nodes but both are
constants, we will do merging or filtering by grokking the constant values.
This speeds up lots of tests in JSRegress, because it enables overflow check elimination on things
like:
for (var i = 0; i < 100; ++i)
Previously, the fact that this was all constants would throw off the analysis because the analysis
wouldn't "know" that 0 < 100.
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
LayoutTests:
Added two test cases that previously would have an unnecessary overflow check on an induction
variable. These tests speed up by 10-15% thanks to this change.
Also added .html/expected files for some regress test that didn't have them.
* js/regress/function-call-expected.txt: Added.
* js/regress/function-call.html: Added.
* js/regress/hard-overflow-check-equal-expected.txt: Added.
* js/regress/hard-overflow-check-equal.html: Added.
* js/regress/hard-overflow-check-expected.txt: Added.
* js/regress/hard-overflow-check.html: Added.
* js/regress/script-tests/hard-overflow-check-equal.js: Added.
(foo):
* js/regress/script-tests/hard-overflow-check.js: Added.
(foo):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkLayoutTestsChangeLog">trunk/LayoutTests/ChangeLog</a></li>
<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="#trunkLayoutTestsjsregressfunctioncallexpectedtxt">trunk/LayoutTests/js/regress/function-call-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregressfunctioncallhtml">trunk/LayoutTests/js/regress/function-call.html</a></li>
<li><a href="#trunkLayoutTestsjsregresshardoverflowcheckequalexpectedtxt">trunk/LayoutTests/js/regress/hard-overflow-check-equal-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregresshardoverflowcheckequalhtml">trunk/LayoutTests/js/regress/hard-overflow-check-equal.html</a></li>
<li><a href="#trunkLayoutTestsjsregresshardoverflowcheckexpectedtxt">trunk/LayoutTests/js/regress/hard-overflow-check-expected.txt</a></li>
<li><a href="#trunkLayoutTestsjsregresshardoverflowcheckhtml">trunk/LayoutTests/js/regress/hard-overflow-check.html</a></li>
<li><a href="#trunkLayoutTestsjsregressscripttestshardoverflowcheckequaljs">trunk/LayoutTests/js/regress/script-tests/hard-overflow-check-equal.js</a></li>
<li><a href="#trunkLayoutTestsjsregressscripttestshardoverflowcheckjs">trunk/LayoutTests/js/regress/script-tests/hard-overflow-check.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkLayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/LayoutTests/ChangeLog (188719 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/ChangeLog 2015-08-21 00:11:10 UTC (rev 188719)
+++ trunk/LayoutTests/ChangeLog 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -1,3 +1,26 @@
</span><ins>+2015-08-20 Filip Pizlo <fpizlo@apple.com>
+
+ Overflow check elimination fails for a simple test case
+ https://bugs.webkit.org/show_bug.cgi?id=147387
+
+ Reviewed by Benjamin Poulain.
+
+ Added two test cases that previously would have an unnecessary overflow check on an induction
+ variable. These tests speed up by 10-15% thanks to this change.
+
+ Also added .html/expected files for some regress test that didn't have them.
+
+ * js/regress/function-call-expected.txt: Added.
+ * js/regress/function-call.html: Added.
+ * js/regress/hard-overflow-check-equal-expected.txt: Added.
+ * js/regress/hard-overflow-check-equal.html: Added.
+ * js/regress/hard-overflow-check-expected.txt: Added.
+ * js/regress/hard-overflow-check.html: Added.
+ * js/regress/script-tests/hard-overflow-check-equal.js: Added.
+ (foo):
+ * js/regress/script-tests/hard-overflow-check.js: Added.
+ (foo):
+
</ins><span class="cx"> 2015-08-20 Nan Wang <n_wang@apple.com>
</span><span class="cx">
</span><span class="cx"> AX: Fix accessibility/mac/selection-value-changes-for-aria-textbox.html test
</span></span></pre></div>
<a id="trunkLayoutTestsjsregressfunctioncallexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/function-call-expected.txt (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/function-call-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/function-call-expected.txt 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/function-call
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressfunctioncallhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/function-call.html (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/function-call.html (rev 0)
+++ trunk/LayoutTests/js/regress/function-call.html 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/function-call.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresshardoverflowcheckequalexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/hard-overflow-check-equal-expected.txt (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/hard-overflow-check-equal-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/hard-overflow-check-equal-expected.txt 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/hard-overflow-check-equal
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresshardoverflowcheckequalhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/hard-overflow-check-equal.html (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/hard-overflow-check-equal.html (rev 0)
+++ trunk/LayoutTests/js/regress/hard-overflow-check-equal.html 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/hard-overflow-check-equal.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresshardoverflowcheckexpectedtxt"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/hard-overflow-check-expected.txt (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/hard-overflow-check-expected.txt (rev 0)
+++ trunk/LayoutTests/js/regress/hard-overflow-check-expected.txt 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/hard-overflow-check
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS no exception thrown
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregresshardoverflowcheckhtml"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/hard-overflow-check.html (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/hard-overflow-check.html (rev 0)
+++ trunk/LayoutTests/js/regress/hard-overflow-check.html 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,12 @@
</span><ins>+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src="../../resources/js-test-pre.js"></script>
+</head>
+<body>
+<script src="../../resources/regress-pre.js"></script>
+<script src="script-tests/hard-overflow-check.js"></script>
+<script src="../../resources/regress-post.js"></script>
+<script src="../../resources/js-test-post.js"></script>
+</body>
+</html>
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressscripttestshardoverflowcheckequaljs"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/script-tests/hard-overflow-check-equal.js (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/script-tests/hard-overflow-check-equal.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/hard-overflow-check-equal.js 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,17 @@
</span><ins>+function foo(o) {
+ var result = 0;
+ for (var i = 0; i != 100; ++i) // ++i still has an overflow check in the emitted code
+ result += o.f;
+ return result;
+}
+
+noInline(foo);
+
+var p = {f:42};
+var o = Object.create(p);
+
+for (var i = 0; i < 500000; ++i) {
+ p.f = i;
+ foo(o);
+}
+
</ins></span></pre></div>
<a id="trunkLayoutTestsjsregressscripttestshardoverflowcheckjs"></a>
<div class="addfile"><h4>Added: trunk/LayoutTests/js/regress/script-tests/hard-overflow-check.js (0 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/LayoutTests/js/regress/script-tests/hard-overflow-check.js (rev 0)
+++ trunk/LayoutTests/js/regress/script-tests/hard-overflow-check.js 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -0,0 +1,17 @@
</span><ins>+function foo(o) {
+ var result = 0;
+ for (var i = 0; i < 100; ++i) // ++i still has an overflow check in the emitted code
+ result += o.f;
+ return result;
+}
+
+noInline(foo);
+
+var p = {f:42};
+var o = Object.create(p);
+
+for (var i = 0; i < 500000; ++i) {
+ p.f = i;
+ foo(o);
+}
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (188719 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-08-21 00:11:10 UTC (rev 188719)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -1,3 +1,34 @@
</span><ins>+2015-08-20 Filip Pizlo <fpizlo@apple.com>
+
+ Overflow check elimination fails for a simple test case
+ https://bugs.webkit.org/show_bug.cgi?id=147387
+
+ Reviewed by Benjamin Poulain.
+
+ Overflow check elimination was having issues when things got constant-folded, because whereas an
+ Add or LessThan operation teaches us about relationships between the things being added or
+ compared, we don't do that when we see a JSConstant. We don't create a relationship between every
+ JSConstant and every other JSConstant. So, if we constant-fold an Add, we forget the relationships
+ that it would have had with its inputs.
+
+ One solution would be to have every JSConstant create a relationship with every other JSConstant.
+ This is dangerous, since it would create O(n^2) explosion of relationships.
+
+ Instead, this patch teaches filtration and merging how to behave "as if" there were inter-constant
+ relationships. Normally those operations only work on two relationships involving the same node
+ pair. But now, if we have @x op @c and @x op @d, where @c and @d are different nodes but both are
+ constants, we will do merging or filtering by grokking the constant values.
+
+ This speeds up lots of tests in JSRegress, because it enables overflow check elimination on things
+ like:
+
+ for (var i = 0; i < 100; ++i)
+
+ Previously, the fact that this was all constants would throw off the analysis because the analysis
+ wouldn't "know" that 0 < 100.
+
+ * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+
</ins><span class="cx"> 2015-08-20 Geoffrey Garen <ggaren@apple.com>
</span><span class="cx">
</span><span class="cx"> forEachCodeBlock should wait for all CodeBlocks automatically
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGIntegerRangeOptimizationPhasecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp (188719 => 188720)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2015-08-21 00:11:10 UTC (rev 188719)
+++ trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp 2015-08-21 00:26:41 UTC (rev 188720)
</span><span class="lines">@@ -61,6 +61,11 @@
</span><span class="cx"> result)));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+bool isGeneralOffset(int offset)
+{
+ return offset >= -1 && offset <= 1;
+}
+
</ins><span class="cx"> class Relationship {
</span><span class="cx"> public:
</span><span class="cx"> enum Kind {
</span><span class="lines">@@ -69,6 +74,26 @@
</span><span class="cx"> NotEqual,
</span><span class="cx"> GreaterThan
</span><span class="cx"> };
</span><ins>+
+ // Some relationships provide more information than others. When a relationship provides more
+ // information, it is less vague.
+ static unsigned vagueness(Kind kind)
+ {
+ switch (kind) {
+ case Equal:
+ return 0;
+ case LessThan:
+ case GreaterThan:
+ return 1;
+ case NotEqual:
+ return 2;
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return 0;
+ }
+
+ static const unsigned minVagueness = 0;
+ static const unsigned maxVagueness = 2;
</ins><span class="cx">
</span><span class="cx"> static Kind flipped(Kind kind)
</span><span class="cx"> {
</span><span class="lines">@@ -118,6 +143,8 @@
</span><span class="cx"> Node* right() const { return m_right; }
</span><span class="cx"> Kind kind() const { return m_kind; }
</span><span class="cx"> int offset() const { return m_offset; }
</span><ins>+
+ unsigned vagueness() const { return vagueness(kind()); }
</ins><span class="cx">
</span><span class="cx"> Relationship flipped() const
</span><span class="cx"> {
</span><span class="lines">@@ -238,15 +265,16 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // Attempts to create a relationship that summarizes the union of this relationship and
- // the other relationship. The null relationship is returned to indicate TOP. This is used
</del><ins>+ // Attempts to create relationships that summarize the union of this relationship and
+ // the other relationship. Relationships are returned by calling the functor with the newly
+ // created relationships. No relationships are created to indicate TOP. This is used
</ins><span class="cx"> // for merging the current relationship-at-head for some pair of nodes and a new
</span><span class="cx"> // relationship-at-head being proposed by a predecessor. We wish to create a new
</span><span class="cx"> // relationship that is true whenever either of them are true, which ensuring that we don't
</span><span class="cx"> // do this forever. Anytime we create a relationship that is not equal to either of the
</span><span class="cx"> // previous ones, we will cause the analysis fixpoint to reexecute.
</span><span class="cx"> //
</span><del>- // If *this and other are identical, we just return it.
</del><ins>+ // If *this and other are identical, we just pass it to the functor.
</ins><span class="cx"> //
</span><span class="cx"> // If they are different, we pick from a finite set of "general" relationships:
</span><span class="cx"> //
</span><span class="lines">@@ -277,13 +305,12 @@
</span><span class="cx"> // that's how "deep" the general relationship lattice is.
</span><span class="cx"> //
</span><span class="cx"> // Note that C being constrained to -1,0,1 also ensures that we never have to return a
</span><del>- // combination of Lt and Gt, as in for example this<other+C && this>other-D. That's why
- // this function can return zero or one relationships rather than a list of relationships.
- // The only possible values of C and D where this would work are -1 and 1, but in that case
- // we just say this==other. That said, the logic for merging two == relationships, like
- // this==other+C || this==other+D is to attempt to create these two relationships:
- // this>other+min(C,D)-1 && this<other+max(C,D)+1. But only one of these relationships will
- // belong to the set of general relationships.
</del><ins>+ // combination of Lt and Gt, as in for example this<other+C && this>other-D. The only possible
+ // values of C and D where this would work are -1 and 1, but in that case we just say
+ // this==other. That said, the logic for merging two == relationships, like this==other+C ||
+ // this==other+D is to attempt to create these two relationships: this>other+min(C,D)-1 &&
+ // this<other+max(C,D)+1. But only one of these relationships will belong to the set of general
+ // relationships.
</ins><span class="cx"> //
</span><span class="cx"> // Here's an example of this in action:
</span><span class="cx"> //
</span><span class="lines">@@ -295,15 +322,41 @@
</span><span class="cx"> // iteration and i==a+1 from the second iteration, we create i>a-1 and i<a+2 but then
</span><span class="cx"> // realize that only i>a-1 is a valid general relationship. This gives us exactly what we
</span><span class="cx"> // want: a statement that i>=a.
</span><del>- Relationship merge(const Relationship& other) const
</del><ins>+ //
+ // However, this may return a pair of relationships when merging relationships involving
+ // constants. For example, if given:
+ //
+ // @x == @c
+ // @x == @d
+ //
+ // where @c and @d are constants, then this may pass two relationships to the functor:
+ //
+ // @x > min(@c, @d) - 1
+ // @x < max(@c, @d) + 1
+ //
+ // This still allows for convergence, because just as when merging relationships over
+ // variables, this always picks from a set of general relationships. Hence although this may
+ // produce two relationships as a result of the merge, the total number of relationships that
+ // can be present at head of block is limited by O(graph.size^2).
+ template<typename Functor>
+ void merge(const Relationship& other, const Functor& functor) const
</ins><span class="cx"> {
</span><del>- if (!sameNodesAs(other))
- return Relationship();
-
</del><span class="cx"> // Handle the super obvious case first.
</span><del>- if (*this == other)
- return *this;
</del><ins>+ if (*this == other) {
+ functor(*this);
+ return;
+ }
</ins><span class="cx">
</span><ins>+ if (m_left != other.m_left)
+ return;
+
+ if (m_right != other.m_right) {
+ mergeConstantsImpl(other, functor);
+ return;
+ }
+
+ ASSERT(sameNodesAs(other));
+
</ins><span class="cx"> // This does some interesting permutations to reduce the amount of duplicate code. For
</span><span class="cx"> // example:
</span><span class="cx"> //
</span><span class="lines">@@ -329,7 +382,7 @@
</span><span class="cx"> // In rare cases, we might not be able to flip. Just give up on life in those
</span><span class="cx"> // cases.
</span><span class="cx"> if (!a || !b)
</span><del>- return Relationship();
</del><ins>+ return;
</ins><span class="cx">
</span><span class="cx"> needFlip = true;
</span><span class="cx">
</span><span class="lines">@@ -337,7 +390,7 @@
</span><span class="cx"> // @a > @b. That's pretty much always a tautology; we don't attempt to do smart
</span><span class="cx"> // things for that case for now.
</span><span class="cx"> if (a.m_kind == GreaterThan || b.m_kind == GreaterThan)
</span><del>- return Relationship();
</del><ins>+ return;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Make sure that if we have a LessThan, then it's first.
</span><span class="lines">@@ -349,11 +402,13 @@
</span><span class="cx"> std::swap(a, b);
</span><span class="cx">
</span><span class="cx"> Relationship result = a.mergeImpl(b);
</span><ins>+ if (!result)
+ return;
</ins><span class="cx">
</span><span class="cx"> if (needFlip)
</span><del>- return result.flipped();
</del><ins>+ result = result.flipped();
</ins><span class="cx">
</span><del>- return result;
</del><ins>+ functor(result);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Attempts to construct one Relationship that adequately summarizes the intersection of
</span><span class="lines">@@ -456,6 +511,52 @@
</span><span class="cx"> ASSERT(m_kind == GreaterThan);
</span><span class="cx"> return filterFlipped();
</span><span class="cx"> }
</span><ins>+
+ // Come up with a relationship that is the best description of this && other, provided that left() is
+ // the same and right() is a constant. Also requires that this is at least as vague as other. It may
+ // return this or it may return something else, but whatever it returns, it will have the same nodes as
+ // this. This is not automatically done by filter() because it currently only makes sense to call this
+ // during a very particular part of setOneSide().
+ Relationship filterConstant(const Relationship& other) const
+ {
+ ASSERT(m_left == other.m_left);
+ ASSERT(m_right->isInt32Constant());
+ ASSERT(other.m_right->isInt32Constant());
+ ASSERT(vagueness() >= other.vagueness());
+
+ if (vagueness() == other.vagueness())
+ return *this;
+
+ int thisRight = m_right->asInt32();
+ int otherRight = other.m_right->asInt32();
+
+ // Ignore funny business.
+ if (sumOverflows<int>(otherRight, other.m_offset))
+ return *this;
+
+ int otherEffectiveRight = otherRight + other.m_offset;
+
+ switch (other.m_kind) {
+ case Equal:
+ // Return a version of *this that is Equal to other's constant.
+ return Relationship(m_left, m_right, Equal, otherEffectiveRight - thisRight);
+
+ case LessThan:
+ case GreaterThan:
+ ASSERT(m_kind == NotEqual);
+ // We could do smart things here. But we don't currently have an example of when it would be
+ // valuable. Note that you have to be careful. We could refine NotEqual to LessThan, but only
+ // if the LessThan subsumes the NotEqual.
+ return *this;
+
+ case NotEqual:
+ RELEASE_ASSERT_NOT_REACHED();
+ return Relationship();
+ }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return Relationship();
+ }
</ins><span class="cx">
</span><span class="cx"> int minValueOfLeft() const
</span><span class="cx"> {
</span><span class="lines">@@ -593,7 +694,7 @@
</span><span class="cx">
</span><span class="cx"> // We have something like @a < @b + 2. We can't represent this under the
</span><span class="cx"> // -1,0,1 rule.
</span><del>- if (bestOffset <= 1)
</del><ins>+ if (isGeneralOffset(bestOffset))
</ins><span class="cx"> return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
</span><span class="cx">
</span><span class="cx"> return Relationship();
</span><span class="lines">@@ -618,7 +719,7 @@
</span><span class="cx"> int bestOffset = std::max(m_offset, other.m_offset + 1);
</span><span class="cx">
</span><span class="cx"> // We have something like @a < @b + 2. We can't do it.
</span><del>- if (bestOffset <= 1)
</del><ins>+ if (isGeneralOffset(bestOffset))
</ins><span class="cx"> return Relationship(m_left, m_right, LessThan, std::max(bestOffset, -1));
</span><span class="cx">
</span><span class="cx"> return Relationship();
</span><span class="lines">@@ -646,7 +747,7 @@
</span><span class="cx"> lessThan = Relationship(
</span><span class="cx"> m_left, other.m_right, LessThan, lessThanEqOffset + 1);
</span><span class="cx">
</span><del>- ASSERT(lessThan.offset() >= -1 && lessThan.offset() <= 1);
</del><ins>+ ASSERT(isGeneralOffset(lessThan.offset()));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> int greaterThanEqOffset = std::min(m_offset, other.m_offset);
</span><span class="lines">@@ -654,7 +755,7 @@
</span><span class="cx"> greaterThan = Relationship(
</span><span class="cx"> m_left, other.m_right, GreaterThan, greaterThanEqOffset - 1);
</span><span class="cx">
</span><del>- ASSERT(greaterThan.offset() >= -1 && greaterThan.offset() <= 1);
</del><ins>+ ASSERT(isGeneralOffset(greaterThan.offset()));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (lessThan) {
</span><span class="lines">@@ -666,6 +767,207 @@
</span><span class="cx">
</span><span class="cx"> return greaterThan;
</span><span class="cx"> }
</span><ins>+
+ template<typename Functor>
+ void mergeConstantsImpl(const Relationship& other, const Functor& functor) const
+ {
+ ASSERT(m_left == other.m_left);
+
+ // Only deal with constant right.
+ if (!m_right->isInt32Constant() || !other.m_right->isInt32Constant())
+ return;
+
+ // What follows is a fairly conservative merge. We could tune this phase to come up with
+ // all possible inequalities between variables and constants, but we focus mainly on cheap
+ // cases for now.
+
+ // Here are some of the the arrangements we can merge usefully assuming @c < @d:
+ //
+ // @x == @c || @x == @d => @x >= c && @x <= @d
+ // @x >= @c || @x <= @d => TOP
+ // @x == @c || @x != @d => @x != @d
+
+ int thisRight = m_right->asInt32();
+ int otherRight = other.m_right->asInt32();
+
+ // Ignore funny business.
+ if (sumOverflows<int>(thisRight, m_offset))
+ return;
+ if (sumOverflows<int>(otherRight, other.m_offset))
+ return;
+
+ int thisEffectiveRight = thisRight + m_offset;
+ int otherEffectiveRight = otherRight + other.m_offset;
+
+ auto makeUpper = [&] (int64_t upper) {
+ if (upper <= thisRight) {
+ // We want m_right + offset to be equal to upper. Hence we want offset to cancel
+ // with m_right. But there's more to it, since we want +1 to turn the LessThan into
+ // a LessThanOrEqual, and we want to make sure we don't end up with non-general
+ // offsets.
+ int offset = static_cast<int>(std::max(
+ static_cast<int64_t>(1) + upper - static_cast<int64_t>(thisRight),
+ static_cast<int64_t>(-1)));
+ functor(Relationship(m_left, m_right, LessThan, offset));
+ }
+ if (upper <= otherRight) {
+ int offset = static_cast<int>(std::max(
+ static_cast<int64_t>(1) + upper - static_cast<int64_t>(otherRight),
+ static_cast<int64_t>(-1)));
+ functor(Relationship(m_left, other.m_right, LessThan, offset));
+ }
+ };
+ auto makeLower = [&] (int64_t lower) {
+ if (lower >= thisRight) {
+ // We want m_right + offset to be equal to lower. Hence we want offset to cancel with
+ // m_right. But there's more to it, since we want -1 to turn the GreaterThan into a
+ // GreaterThanOrEqual, and we want to make sure we don't end up with non-general
+ // offsets.
+ int offset = static_cast<int>(std::min(
+ static_cast<int64_t>(-1) + lower - static_cast<int64_t>(thisRight),
+ static_cast<int64_t>(1)));
+ functor(Relationship(m_left, m_right, GreaterThan, offset));
+ }
+ if (lower >= otherRight) {
+ int offset = static_cast<int>(std::min(
+ static_cast<int64_t>(-1) + lower - static_cast<int64_t>(otherRight),
+ static_cast<int64_t>(1)));
+ functor(Relationship(m_left, other.m_right, GreaterThan, offset));
+ }
+ };
+
+ switch (m_kind) {
+ case Equal: {
+ switch (other.m_kind) {
+ case Equal: {
+ if (thisEffectiveRight == otherEffectiveRight) {
+ // This probably won't arise often. We can keep whichever relationship is general.
+ if (isGeneralOffset(m_offset))
+ functor(*this);
+ if (isGeneralOffset(other.m_offset))
+ functor(other);
+ return;
+ }
+
+ // What follows is the only case where a merge will create more rules than what it
+ // started with. This is fine for convergence because the LessThan/GreaterThan
+ // rules that this creates are general (i.e. have small offsets) and they never
+ // spawn more rules upon subsequent merging.
+
+ makeUpper(std::max(thisEffectiveRight, otherEffectiveRight));
+ makeLower(std::min(thisEffectiveRight, otherEffectiveRight));
+ return;
+ }
+
+ case LessThan: {
+ // Either the LessThan condition subsumes the equality, or the LessThan condition
+ // and equality merge together to create a looser LessThan condition.
+
+ // This is @x == thisEffectiveRight
+ // Other is: @x < otherEffectiveRight
+
+ // We want to create @x <= upper. Figure out the value of upper.
+ makeUpper(std::max(
+ static_cast<int64_t>(thisEffectiveRight),
+ static_cast<int64_t>(otherEffectiveRight) - 1));
+ return;
+ }
+
+ case GreaterThan: {
+ // Opposite of the LessThan case, above.
+
+ // This is: @x == thisEffectiveRight
+ // Other is: @x > otherEffectiveRight
+
+ makeLower(std::min(
+ static_cast<int64_t>(thisEffectiveRight),
+ static_cast<int64_t>(otherEffectiveRight) + 1));
+ return;
+ }
+
+ case NotEqual: {
+ // We keep the NotEqual so long as it doesn't contradict our Equal.
+ if (otherEffectiveRight == thisEffectiveRight)
+ return;
+
+ // But, we only keep the NotEqual if it is general. This simplifies reasoning about
+ // convergence: merging never introduces a new rule unless that rule is general.
+ if (!isGeneralOffset(other.m_offset))
+ return;
+
+ functor(other);
+ return;
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return;
+ }
+
+ case LessThan: {
+ switch (other.m_kind) {
+ case Equal: {
+ other.mergeConstantsImpl(*this, functor);
+ return;
+ }
+
+ case LessThan: {
+ makeUpper(std::max(
+ static_cast<int64_t>(thisEffectiveRight) - 1,
+ static_cast<int64_t>(otherEffectiveRight) - 1));
+ return;
+ }
+
+ case GreaterThan: {
+ // We have a claim that @x > @c || @x < @d. If @d > @c, this is the tautology. If
+ // @d <= @c, it's sort of uninteresting. Just ignore this.
+ return;
+ }
+
+ case NotEqual: {
+ // We have a claim that @x < @c || @x != @d. This isn't interesting.
+ return;
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return;
+ }
+
+ case GreaterThan: {
+ switch (other.m_kind) {
+ case Equal: {
+ other.mergeConstantsImpl(*this, functor);
+ return;
+ }
+
+ case LessThan: {
+ // Not interesting, see above.
+ return;
+ }
+
+ case GreaterThan: {
+ makeLower(std::min(
+ static_cast<int64_t>(thisEffectiveRight) + 1,
+ static_cast<int64_t>(otherEffectiveRight) + 1));
+ return;
+ }
+
+ case NotEqual: {
+ // Not interesting, see above.
+ return;
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ return;
+ }
+
+ case NotEqual: {
+ if (other.m_kind == Equal)
+ other.mergeConstantsImpl(*this, functor);
+ return;
+ } }
+
+ RELEASE_ASSERT_NOT_REACHED();
+ }
</ins><span class="cx">
</span><span class="cx"> Node* m_left;
</span><span class="cx"> Node* m_right;
</span><span class="lines">@@ -1159,6 +1461,76 @@
</span><span class="cx"> auto result = relationshipMap.add(
</span><span class="cx"> relationship.left(), Vector<Relationship>());
</span><span class="cx"> Vector<Relationship>& relationships = result.iterator->value;
</span><ins>+
+ if (relationship.right()->isInt32Constant()) {
+ // We want to do some work to refine relationships over constants. This is necessary because
+ // when we introduce a constant into the IR, we don't automatically create relationships
+ // between that constant and the other constants. That means that when we do introduce
+ // relationships between a non-constant and a constant, we need to check the other
+ // relationships between that non-constant and other constants to see if we can make some
+ // refinements. Possible constant statement filtrations:
+ //
+ // - @x == @c and @x != @d, where @c > @d:
+ // @x == @c and @x > @d
+ //
+ // but actually we are more aggressive:
+ //
+ // - @x == @c and @x op @d where @c == @d + k
+ // @x == @c and @x == @d + k
+ //
+ // And this is also possible:
+ //
+ // - @x > @c and @x != @d where @c == @d + k and k >= 0
+ //
+ // @x > @c and @x > @d + k
+ //
+ // So, here's what we should do depending on the kind of relationship we're introducing:
+ //
+ // Equal constant: Find all LessThan, NotEqual, and GreaterThan constant operations and refine
+ // them to be Equal constant. Don't worry about contradictions.
+ //
+ // LessThan, GreaterThan constant: See if there is any Equal constant, and if so, refine to
+ // that. Otherwise, find all NotEqual constant operations and refine them to be LessThan or
+ // GreaterThan constant if possible.
+ //
+ // NotEqual constant: See if there is any Equal constant, and if so, refine to that. Otherwise,
+ // see if there is any LessThan or GreaterThan constant operation, and if so, attempt to
+ // refine to that.
+ //
+ // Seems that the key thing is to have a filterConstant() operation that returns a refined
+ // version of *this based on other. The code here accomplishes this by using the vagueness
+ // index (Relationship::vagueness()) to first find less vague relationships and refine this one
+ // using them, and then find more vague relationships and refine those to this.
+
+ if (relationship.vagueness() != Relationship::minVagueness) {
+ // We're not minimally vague (maximally specific), so try to refine ourselves based on what
+ // we already know.
+ for (Relationship& otherRelationship : relationships) {
+ if (otherRelationship.vagueness() < relationship.vagueness()
+ && otherRelationship.right()->isInt32Constant()) {
+ Relationship newRelationship = relationship.filterConstant(otherRelationship);
+ if (verbose && newRelationship != relationship)
+ dataLog(" Refined to: ", newRelationship, " based on ", otherRelationship, "\n");
+ relationship = newRelationship;
+ }
+ }
+ }
+
+ if (relationship.vagueness() != Relationship::maxVagueness) {
+ // We're not maximally value (minimally specific), so try to refine other relationships
+ // based on this one.
+ for (Relationship& otherRelationship : relationships) {
+ if (otherRelationship.vagueness() > relationship.vagueness()
+ && otherRelationship.right()->isInt32Constant()) {
+ Relationship newRelationship = otherRelationship.filterConstant(relationship);
+ if (verbose && newRelationship != otherRelationship)
+ dataLog(" Refined ", otherRelationship, " to: ", newRelationship, "\n");
+ otherRelationship = newRelationship;
+ }
+ }
+ }
+ }
+
</ins><span class="cx"> Vector<Relationship> toAdd;
</span><span class="cx"> bool found = false;
</span><span class="cx"> for (Relationship& otherRelationship : relationships) {
</span><span class="lines">@@ -1169,6 +1541,9 @@
</span><span class="cx"> found = true;
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+
+ // FIXME: Also add filtration over statements about constants. For example, if we have
+ // @x == @c and @x != @d, where @d > @c, then we want to turn @x != @d into @x < @d.
</ins><span class="cx">
</span><span class="cx"> if (timeToLive && otherRelationship.kind() == Relationship::Equal) {
</span><span class="cx"> if (verbose)
</span><span class="lines">@@ -1262,50 +1637,48 @@
</span><span class="cx"> for (Relationship sourceRelationship : iter->value) {
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Merging ", targetRelationship, " and ", sourceRelationship, ":\n");
</span><del>- Relationship newRelationship =
- targetRelationship.merge(sourceRelationship);
-
- if (verbose)
- dataLog(" Got ", newRelationship, "\n");
-
- if (!newRelationship)
- continue;
-
- // We need to filter() to avoid exponential explosion of identical
- // relationships. We do this here to avoid making setOneSide() do
- // more work, since we expect setOneSide() will be called more
- // frequently. Here's an example. At some point someone might start
- // with two relationships like @a > @b - C and @a < @b + D. Then
- // someone does a setRelationship() passing something that turns
- // both of these into @a == @b. Now we have @a == @b duplicated.
- // Let's say that this duplicate @a == @b ends up at the head of a
- // loop. If we didn't have this rule, then the loop would propagate
- // duplicate @a == @b's onto the existing duplicate @a == @b's.
- // There would be four pairs of @a == @b, each of which would
- // create a new @a == @b. Now we'd have four of these duplicates
- // and the next time around we'd have 8, then 16, etc. We avoid
- // this here by doing this filtration. That might be a bit of
- // overkill, since it's probably just the identical duplicate
- // relationship case we want' to avoid. But, I'll keep this until
- // we have evidence that this is a performance problem. Remember -
- // we are already dealing with a list that is pruned down to
- // relationships with identical left operand. It shouldn't be a
- // large list.
- bool found = false;
- for (Relationship& existingRelationship : mergedRelationships) {
- if (existingRelationship.sameNodesAs(newRelationship)) {
- Relationship filtered =
- existingRelationship.filter(newRelationship);
- if (filtered) {
- existingRelationship = filtered;
- found = true;
- break;
</del><ins>+ targetRelationship.merge(
+ sourceRelationship,
+ [&] (Relationship newRelationship) {
+ if (verbose)
+ dataLog(" Got ", newRelationship, "\n");
+
+ // We need to filter() to avoid exponential explosion of identical
+ // relationships. We do this here to avoid making setOneSide() do
+ // more work, since we expect setOneSide() will be called more
+ // frequently. Here's an example. At some point someone might start
+ // with two relationships like @a > @b - C and @a < @b + D. Then
+ // someone does a setRelationship() passing something that turns
+ // both of these into @a == @b. Now we have @a == @b duplicated.
+ // Let's say that this duplicate @a == @b ends up at the head of a
+ // loop. If we didn't have this rule, then the loop would propagate
+ // duplicate @a == @b's onto the existing duplicate @a == @b's.
+ // There would be four pairs of @a == @b, each of which would
+ // create a new @a == @b. Now we'd have four of these duplicates
+ // and the next time around we'd have 8, then 16, etc. We avoid
+ // this here by doing this filtration. That might be a bit of
+ // overkill, since it's probably just the identical duplicate
+ // relationship case we want' to avoid. But, I'll keep this until
+ // we have evidence that this is a performance problem. Remember -
+ // we are already dealing with a list that is pruned down to
+ // relationships with identical left operand. It shouldn't be a
+ // large list.
+ bool found = false;
+ for (Relationship& existingRelationship : mergedRelationships) {
+ if (existingRelationship.sameNodesAs(newRelationship)) {
+ Relationship filtered =
+ existingRelationship.filter(newRelationship);
+ if (filtered) {
+ existingRelationship = filtered;
+ found = true;
+ break;
+ }
+ }
</ins><span class="cx"> }
</span><del>- }
- }
-
- if (!found)
- mergedRelationships.append(newRelationship);
</del><ins>+
+ if (!found)
+ mergedRelationships.append(newRelationship);
+ });
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx"> std::sort(mergedRelationships.begin(), mergedRelationships.end());
</span></span></pre>
</div>
</div>
</body>
</html>