<!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>[197665] releases/WebKitGTK/webkit-2.12</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/197665">197665</a></dd>
<dt>Author</dt> <dd>carlosgc@webkit.org</dd>
<dt>Date</dt> <dd>2016-03-07 01:48:07 -0800 (Mon, 07 Mar 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>Merge <a href="http://trac.webkit.org/projects/webkit/changeset/197366">r197366</a> - B3 should have global store elimination
https://bugs.webkit.org/show_bug.cgi?id=154658
Reviewed by Benjamin Poulain.
Source/JavaScriptCore:
Implements fairly comprehensive global store elimination:
1) If you store the result of a load with no interference in between, remove the store.
2) If you store the same thing you stored previously, remove the store.
3) If you store something that you either loaded previously or stored previously along
arbitrarily many paths, remove the store.
4) If you store to something that is stored to again in the future with no interference in
between, remove the store.
Rule (4) is super relevant to FTL since the DFG does not eliminate redundant PutStructures.
A constructor that produces a large object will have many redundant stores to the same base
pointer, offset, and heap range, with no code to observe that heap raneg in between.
This doesn't have a decisive effect on major benchmarks, but it's an enormous win for
microbenchmarks:
- 30% faster to construct an object with many fields.
- 5x faster to do many stores to a global variable.
The compile time cost should be very small. Although the optimization is global, it aborts as
soon as it sees anything that would confound store elimination. For rules (1)-(3), we
piggy-back the existing load elimination, which gives up on interfering stores. For rule (4),
we search forward through the current block and then globally a block at a time (skipping
block contents thanks to summary data), which could be expensive. But rule (4) aborts as soon
as it sees a read, write, or end block (Return or Oops). Any Check will claim to read TOP. Any
Patchpoint that results from an InvalidationPoint will claim to read TOP, as will any
Patchpoints for ICs. Those are usually sprinkled all over the program.
In other words, this optimization rarely kicks in. When it does kick in, it makes programs run
faster. When it doesn't kick in, it's usually O(1) because there are reasons for aborting all
over a "normal" program so the search will halt almost immediately. This of course raises the
question: how much more in compile time do we pay when the optimization does kick in? The
optimization kicks in the most for the microbenchmarks I wrote for this patch. Amazingly, the
effect of the optimization a wash for compile time: whatever cost we pay doing the O(n^2)
searches is balanced by the massive reduction in work in the backend. On one of the two
microbenchmarks, overall compile time actually shrank with this optimization even though CSE
itself cost more. That's not too surprising - the backend costs much more per instruction, so
things that remove instructions before we get to the backend tend to be a good idea.
We could consider adding a more aggressive version of this in the future, which could sink
stores into checks. That could be crazy fun: https://bugs.webkit.org/show_bug.cgi?id=152162#c3
But mainly, I'm adding this optimization because it was super fun to implement during the
WebAssembly CG summit.
* b3/B3EliminateCommonSubexpressions.cpp:
* b3/B3MemoryValue.h:
* b3/B3SuccessorCollection.h:
(JSC::B3::SuccessorCollection::begin):
(JSC::B3::SuccessorCollection::end):
(JSC::B3::SuccessorCollection::const_iterator::const_iterator):
(JSC::B3::SuccessorCollection::const_iterator::operator*):
(JSC::B3::SuccessorCollection::const_iterator::operator++):
(JSC::B3::SuccessorCollection::const_iterator::operator==):
(JSC::B3::SuccessorCollection::const_iterator::operator!=):
LayoutTests:
These two benchmarks both speed up significantly with this change.
* js/regress/build-large-object-expected.txt: Added.
* js/regress/build-large-object.html: Added.
* js/regress/many-repeat-stores-expected.txt: Added.
* js/regress/many-repeat-stores.html: Added.
* js/regress/script-tests/build-large-object.js: Added.
* js/regress/script-tests/many-repeat-stores.js: Added.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsChangeLog">releases/WebKitGTK/webkit-2.12/LayoutTests/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit212SourceJavaScriptCoreChangeLog">releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3EliminateCommonSubexpressionscpp">releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp</a></li>
<li><a href="#releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3MemoryValueh">releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3MemoryValue.h</a></li>
<li><a href="#releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3SuccessorCollectionh">releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3SuccessorCollection.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressbuildlargeobjectexpectedtxt">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object-expected.txt</a></li>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressbuildlargeobjecthtml">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object.html</a></li>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressmanyrepeatstoresexpectedtxt">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores-expected.txt</a></li>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressmanyrepeatstoreshtml">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores.html</a></li>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressscripttestsbuildlargeobjectjs">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/build-large-object.js</a></li>
<li><a href="#releasesWebKitGTKwebkit212LayoutTestsjsregressscripttestsmanyrepeatstoresjs">releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/many-repeat-stores.js</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="releasesWebKitGTKwebkit212LayoutTestsChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.12/LayoutTests/ChangeLog (197664 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/ChangeLog 2016-03-07 09:39:03 UTC (rev 197664)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/ChangeLog 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -1,3 +1,19 @@
</span><ins>+2016-02-28 Filip Pizlo <fpizlo@apple.com>
+
+ B3 should have global store elimination
+ https://bugs.webkit.org/show_bug.cgi?id=154658
+
+ Reviewed by Benjamin Poulain.
+
+ These two benchmarks both speed up significantly with this change.
+
+ * js/regress/build-large-object-expected.txt: Added.
+ * js/regress/build-large-object.html: Added.
+ * js/regress/many-repeat-stores-expected.txt: Added.
+ * js/regress/many-repeat-stores.html: Added.
+ * js/regress/script-tests/build-large-object.js: Added.
+ * js/regress/script-tests/many-repeat-stores.js: Added.
+
</ins><span class="cx"> 2016-02-29 Adrien Plazas <aplazas@igalia.com>
</span><span class="cx">
</span><span class="cx"> [GTK] Touch slider test fails due to assertion in webkitWebViewBaseTouchEvent()
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit212LayoutTestsjsregressbuildlargeobjectexpectedtxt"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object-expected.txt (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object-expected.txt (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object-expected.txt 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/build-large-object
+
+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="releasesWebKitGTKwebkit212LayoutTestsjsregressbuildlargeobjecthtml"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object.html (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object.html (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/build-large-object.html 2016-03-07 09:48:07 UTC (rev 197665)
</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/build-large-object.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="releasesWebKitGTKwebkit212LayoutTestsjsregressmanyrepeatstoresexpectedtxt"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores-expected.txt (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores-expected.txt (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores-expected.txt 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -0,0 +1,10 @@
</span><ins>+JSRegress/many-repeat-stores
+
+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="releasesWebKitGTKwebkit212LayoutTestsjsregressmanyrepeatstoreshtml"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores.html (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores.html (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/many-repeat-stores.html 2016-03-07 09:48:07 UTC (rev 197665)
</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/many-repeat-stores.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="releasesWebKitGTKwebkit212LayoutTestsjsregressscripttestsbuildlargeobjectjs"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/build-large-object.js (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/build-large-object.js (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/build-large-object.js 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -0,0 +1,34 @@
</span><ins>+var g;
+(function() {
+ for (var i = 0; i < 1000000; ++i) {
+ var o = {}
+ o.a = 0;
+ o.b = 1;
+ o.c = 2;
+ o.d = 3;
+ o.e = 4;
+ o.f = 5;
+ o.g = 6;
+ o.h = 7;
+ o.i = 8;
+ o.j = 9;
+ o.k = 10;
+ o.l = 11;
+ o.m = 12;
+ o.n = 13;
+ o.o = 14;
+ o.p = 15;
+ o.q = 0;
+ o.r = 1;
+ o.s = 2;
+ o.t = 3;
+ o.u = 4;
+ o.v = 5;
+ o.w = 6;
+ o.x = 7;
+ o.y = 8;
+ o.z = 9;
+ g = o;
+ }
+ return g;
+})();
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit212LayoutTestsjsregressscripttestsmanyrepeatstoresjs"></a>
<div class="addfile"><h4>Added: releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/many-repeat-stores.js (0 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/many-repeat-stores.js (rev 0)
+++ releases/WebKitGTK/webkit-2.12/LayoutTests/js/regress/script-tests/many-repeat-stores.js 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -0,0 +1,38 @@
</span><ins>+var g;
+(function() {
+ for (var i = 0; i < 10000000; ++i) {
+ g = i + 0;
+ g = i + 1;
+ g = i + 2;
+ g = i + 3;
+ g = i + 4;
+ g = i + 5;
+ g = i + 6;
+ g = i + 7;
+ g = i + 8;
+ g = i + 9;
+ g = i + 10;
+ g = i + 11;
+ g = i + 12;
+ g = i + 13;
+ g = i + 14;
+ g = i + 15;
+ g = i + 0;
+ g = i + 1;
+ g = i + 2;
+ g = i + 3;
+ g = i + 4;
+ g = i + 5;
+ g = i + 6;
+ g = i + 7;
+ g = i + 8;
+ g = i + 9;
+ g = i + 10;
+ g = i + 11;
+ g = i + 12;
+ g = i + 13;
+ g = i + 14;
+ g = i + 15;
+ }
+ return g;
+})();
</ins></span></pre></div>
<a id="releasesWebKitGTKwebkit212SourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/ChangeLog (197664 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/ChangeLog 2016-03-07 09:39:03 UTC (rev 197664)
+++ releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/ChangeLog 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -1,3 +1,70 @@
</span><ins>+2016-02-28 Filip Pizlo <fpizlo@apple.com>
+
+ B3 should have global store elimination
+ https://bugs.webkit.org/show_bug.cgi?id=154658
+
+ Reviewed by Benjamin Poulain.
+
+ Implements fairly comprehensive global store elimination:
+
+ 1) If you store the result of a load with no interference in between, remove the store.
+
+ 2) If you store the same thing you stored previously, remove the store.
+
+ 3) If you store something that you either loaded previously or stored previously along
+ arbitrarily many paths, remove the store.
+
+ 4) If you store to something that is stored to again in the future with no interference in
+ between, remove the store.
+
+ Rule (4) is super relevant to FTL since the DFG does not eliminate redundant PutStructures.
+ A constructor that produces a large object will have many redundant stores to the same base
+ pointer, offset, and heap range, with no code to observe that heap raneg in between.
+
+ This doesn't have a decisive effect on major benchmarks, but it's an enormous win for
+ microbenchmarks:
+
+ - 30% faster to construct an object with many fields.
+
+ - 5x faster to do many stores to a global variable.
+
+ The compile time cost should be very small. Although the optimization is global, it aborts as
+ soon as it sees anything that would confound store elimination. For rules (1)-(3), we
+ piggy-back the existing load elimination, which gives up on interfering stores. For rule (4),
+ we search forward through the current block and then globally a block at a time (skipping
+ block contents thanks to summary data), which could be expensive. But rule (4) aborts as soon
+ as it sees a read, write, or end block (Return or Oops). Any Check will claim to read TOP. Any
+ Patchpoint that results from an InvalidationPoint will claim to read TOP, as will any
+ Patchpoints for ICs. Those are usually sprinkled all over the program.
+
+ In other words, this optimization rarely kicks in. When it does kick in, it makes programs run
+ faster. When it doesn't kick in, it's usually O(1) because there are reasons for aborting all
+ over a "normal" program so the search will halt almost immediately. This of course raises the
+ question: how much more in compile time do we pay when the optimization does kick in? The
+ optimization kicks in the most for the microbenchmarks I wrote for this patch. Amazingly, the
+ effect of the optimization a wash for compile time: whatever cost we pay doing the O(n^2)
+ searches is balanced by the massive reduction in work in the backend. On one of the two
+ microbenchmarks, overall compile time actually shrank with this optimization even though CSE
+ itself cost more. That's not too surprising - the backend costs much more per instruction, so
+ things that remove instructions before we get to the backend tend to be a good idea.
+
+ We could consider adding a more aggressive version of this in the future, which could sink
+ stores into checks. That could be crazy fun: https://bugs.webkit.org/show_bug.cgi?id=152162#c3
+
+ But mainly, I'm adding this optimization because it was super fun to implement during the
+ WebAssembly CG summit.
+
+ * b3/B3EliminateCommonSubexpressions.cpp:
+ * b3/B3MemoryValue.h:
+ * b3/B3SuccessorCollection.h:
+ (JSC::B3::SuccessorCollection::begin):
+ (JSC::B3::SuccessorCollection::end):
+ (JSC::B3::SuccessorCollection::const_iterator::const_iterator):
+ (JSC::B3::SuccessorCollection::const_iterator::operator*):
+ (JSC::B3::SuccessorCollection::const_iterator::operator++):
+ (JSC::B3::SuccessorCollection::const_iterator::operator==):
+ (JSC::B3::SuccessorCollection::const_iterator::operator!=):
+
</ins><span class="cx"> 2016-02-29 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Make it cheap to #include "JITOperations.h"
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3EliminateCommonSubexpressionscpp"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp (197664 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp 2016-03-07 09:39:03 UTC (rev 197664)
+++ releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -66,27 +66,87 @@
</span><span class="cx">
</span><span class="cx"> typedef Vector<MemoryValue*, 1> MemoryMatches;
</span><span class="cx">
</span><del>-struct ImpureBlockData {
</del><ins>+class MemoryValueMap {
+public:
+ MemoryValueMap() { }
+
+ void add(MemoryValue* memory)
+ {
+ Matches& matches = m_map.add(memory->lastChild(), Matches()).iterator->value;
+ if (matches.contains(memory))
+ return;
+ matches.append(memory);
+ }
+
+ template<typename Functor>
+ void removeIf(const Functor& functor)
+ {
+ m_map.removeIf(
+ [&] (HashMap<Value*, Matches>::KeyValuePairType& entry) -> bool {
+ entry.value.removeAllMatching(
+ [&] (Value* value) -> bool {
+ if (MemoryValue* memory = value->as<MemoryValue>())
+ return functor(memory);
+ return true;
+ });
+ return entry.value.isEmpty();
+ });
+ }
+
+ Matches* find(Value* ptr)
+ {
+ auto iter = m_map.find(ptr);
+ if (iter == m_map.end())
+ return nullptr;
+ return &iter->value;
+ }
+
+ template<typename Functor>
+ MemoryValue* find(Value* ptr, const Functor& functor)
+ {
+ if (Matches* matches = find(ptr)) {
+ for (Value* candidateValue : *matches) {
+ if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {
+ if (functor(candidateMemory))
+ return candidateMemory;
+ }
+ }
+ }
+ return nullptr;
+ }
+
</ins><span class="cx"> void dump(PrintStream& out) const
</span><span class="cx"> {
</span><del>- out.print("{writes = ", writes, ", memoryValues = {");
-
</del><ins>+ out.print("{");
</ins><span class="cx"> CommaPrinter comma;
</span><del>- for (auto& entry : memoryValues)
</del><ins>+ for (auto& entry : m_map)
</ins><span class="cx"> out.print(comma, pointerDump(entry.key), "=>", pointerListDump(entry.value));
</span><del>-
- out.print("}}");
</del><ins>+ out.print("}");
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- RangeSet<HeapRange> writes;
-
- // Maps an address base to all of the MemoryValues that do things to it. After we're done
- // processing a map, this tells us the values at tail. Note that we use a Matches array
- // because those MemoryValues could be turned into Identity's, and we need to check for this
- // as we go.
- HashMap<Value*, Matches> memoryValues;
</del><ins>+private:
+ // This uses Matches for two reasons:
+ // - It cannot be a MemoryValue* because the key is imprecise. Many MemoryValues could have the
+ // same key while being unaliased.
+ // - It can't be a MemoryMatches array because the MemoryValue*'s could be turned into Identity's.
+ HashMap<Value*, Matches> m_map;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+struct ImpureBlockData {
+ void dump(PrintStream& out) const
+ {
+ out.print(
+ "{reads = ", reads, ", writes = ", writes, ", storesAtHead = ", storesAtHead,
+ ", memoryValuesAtTail = ", memoryValuesAtTail, "}");
+ }
+
+ RangeSet<HeapRange> reads; // This only gets used for forward store elimination.
+ RangeSet<HeapRange> writes; // This gets used for both load and store elimination.
+
+ MemoryValueMap storesAtHead;
+ MemoryValueMap memoryValuesAtTail;
+};
+
</ins><span class="cx"> class CSE {
</span><span class="cx"> public:
</span><span class="cx"> CSE(Procedure& proc)
</span><span class="lines">@@ -104,20 +164,32 @@
</span><span class="cx">
</span><span class="cx"> m_proc.resetValueOwners();
</span><span class="cx">
</span><ins>+ // Summarize the impure effects of each block, and the impure values available at the end of
+ // each block. This doesn't edit code yet.
</ins><span class="cx"> for (BasicBlock* block : m_proc) {
</span><span class="cx"> ImpureBlockData& data = m_impureBlockData[block];
</span><span class="cx"> for (Value* value : *block) {
</span><del>- if (HeapRange writes = value->effects().writes)
</del><ins>+ Effects effects = value->effects();
+ MemoryValue* memory = value->as<MemoryValue>();
+
+ if (memory && memory->isStore()
+ && !data.reads.overlaps(memory->range())
+ && !data.writes.overlaps(memory->range()))
+ data.storesAtHead.add(memory);
+ data.reads.add(effects.reads);
+
+ if (HeapRange writes = effects.writes)
</ins><span class="cx"> clobber(data, writes);
</span><span class="cx">
</span><del>- if (MemoryValue* memory = value->as<MemoryValue>())
- addMemoryValue(data, memory);
</del><ins>+ if (memory)
+ data.memoryValuesAtTail.add(memory);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog("Block ", *block, ": ", data, "\n");
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Perform CSE. This edits code.
</ins><span class="cx"> Vector<BasicBlock*> postOrder = m_proc.blocksInPostOrder();
</span><span class="cx"> for (unsigned i = postOrder.size(); i--;) {
</span><span class="cx"> m_block = postOrder[i];
</span><span class="lines">@@ -133,6 +205,8 @@
</span><span class="cx"> m_impureBlockData[m_block] = m_data;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // The previous pass might have requested that we insert code in some basic block other than
+ // the one that it was looking at. This inserts them.
</ins><span class="cx"> for (BasicBlock* block : m_proc) {
</span><span class="cx"> for (unsigned valueIndex = 0; valueIndex < block->size(); ++valueIndex) {
</span><span class="cx"> auto iter = m_sets.find(block->at(valueIndex));
</span><span class="lines">@@ -162,30 +236,69 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ MemoryValue* memory = m_value->as<MemoryValue>();
+ if (memory && processMemoryBeforeClobber(memory))
+ return;
+
</ins><span class="cx"> if (HeapRange writes = m_value->effects().writes)
</span><span class="cx"> clobber(m_data, writes);
</span><span class="cx">
</span><del>- if (MemoryValue* memory = m_value->as<MemoryValue>())
- processMemory(memory);
</del><ins>+ if (memory)
+ processMemoryAfterClobber(memory);
</ins><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Return true if we got rid of the operation. If you changed IR in this function, you have to
+ // set m_changed even if you also return true.
+ bool processMemoryBeforeClobber(MemoryValue* memory)
+ {
+ Value* value = memory->child(0);
+ Value* ptr = memory->lastChild();
+ HeapRange range = memory->range();
+ int32_t offset = memory->offset();
+
+ switch (memory->opcode()) {
+ case Store8:
+ return handleStoreBeforeClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && ((candidate->opcode() == Store8 && candidate->child(0) == value)
+ || ((candidate->opcode() == Load8Z || candidate->opcode() == Load8S)
+ && candidate == value));
+ });
+ case Store16:
+ return handleStoreBeforeClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && ((candidate->opcode() == Store16 && candidate->child(0) == value)
+ || ((candidate->opcode() == Load16Z || candidate->opcode() == Load16S)
+ && candidate == value));
+ });
+ case Store:
+ return handleStoreBeforeClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->offset() == offset
+ && ((candidate->opcode() == Store && candidate->child(0) == value)
+ || (candidate->opcode() == Load && candidate == value));
+ });
+ default:
+ return false;
+ }
+ }
+
</ins><span class="cx"> void clobber(ImpureBlockData& data, HeapRange writes)
</span><span class="cx"> {
</span><span class="cx"> data.writes.add(writes);
</span><span class="cx">
</span><del>- data.memoryValues.removeIf(
- [&] (HashMap<Value*, Matches>::KeyValuePairType& entry) -> bool {
- entry.value.removeAllMatching(
- [&] (Value* value) -> bool {
- if (MemoryValue* memory = value->as<MemoryValue>())
- return memory->range().overlaps(writes);
- return true;
- });
- return entry.value.isEmpty();
</del><ins>+ data.memoryValuesAtTail.removeIf(
+ [&] (MemoryValue* memory) {
+ return memory->range().overlaps(writes);
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void processMemory(MemoryValue* memory)
</del><ins>+ void processMemoryAfterClobber(MemoryValue* memory)
</ins><span class="cx"> {
</span><span class="cx"> Value* ptr = memory->lastChild();
</span><span class="cx"> HeapRange range = memory->range();
</span><span class="lines">@@ -301,10 +414,33 @@
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- case Store8:
- case Store16:
</del><ins>+ case Store8: {
+ handleStoreAfterClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->opcode() == Store8
+ && candidate->offset() == offset;
+ });
+ break;
+ }
+
+ case Store16: {
+ handleStoreAfterClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->opcode() == Store16
+ && candidate->offset() == offset;
+ });
+ break;
+ }
+
</ins><span class="cx"> case Store: {
</span><del>- addMemoryValue(m_data, memory);
</del><ins>+ handleStoreAfterClobber(
+ ptr, range,
+ [&] (MemoryValue* candidate) -> bool {
+ return candidate->opcode() == Store
+ && candidate->offset() == offset;
+ });
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -316,6 +452,82 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename Filter>
</span><ins>+ bool handleStoreBeforeClobber(Value* ptr, HeapRange range, const Filter& filter)
+ {
+ MemoryMatches matches = findMemoryValue(ptr, range, filter);
+ if (matches.isEmpty())
+ return false;
+
+ m_value->replaceWithNop();
+ m_changed = true;
+ return true;
+ }
+
+ template<typename Filter>
+ void handleStoreAfterClobber(Value* ptr, HeapRange range, const Filter& filter)
+ {
+ if (findStoreAfterClobber(ptr, range, filter)) {
+ m_value->replaceWithNop();
+ m_changed = true;
+ return;
+ }
+
+ m_data.memoryValuesAtTail.add(m_value->as<MemoryValue>());
+ }
+
+ template<typename Filter>
+ bool findStoreAfterClobber(Value* ptr, HeapRange range, const Filter& filter)
+ {
+ // We can eliminate a store if every forward path hits a store to the same location before
+ // hitting any operation that observes the store. This search seems like it should be
+ // expensive, but in the overwhelming majority of cases it will almost immediately hit an
+ // operation that interferes.
+
+ if (verbose)
+ dataLog(*m_value, ": looking forward for stores to ", *ptr, "...\n");
+
+ // First search forward in this basic block.
+ // FIXME: It would be cool to get rid of this linear search. It's not super critical since
+ // we will probably bail out very quickly, but it *is* annoying.
+ for (unsigned index = m_index + 1; index < m_block->size(); ++index) {
+ Value* value = m_block->at(index);
+
+ if (MemoryValue* memoryValue = value->as<MemoryValue>()) {
+ if (memoryValue->lastChild() == ptr && filter(memoryValue))
+ return true;
+ }
+
+ Effects effects = value->effects();
+ if (effects.reads.overlaps(range) || effects.writes.overlaps(range))
+ return false;
+ }
+
+ if (!m_block->numSuccessors())
+ return false;
+
+ BlockWorklist worklist;
+ worklist.pushAll(m_block->successorBlocks());
+
+ while (BasicBlock* block = worklist.pop()) {
+ ImpureBlockData& data = m_impureBlockData[block];
+
+ MemoryValue* match = data.storesAtHead.find(ptr, filter);
+ if (match && match != m_value)
+ continue;
+
+ if (data.writes.overlaps(range) || data.reads.overlaps(range))
+ return false;
+
+ if (!block->numSuccessors())
+ return false;
+
+ worklist.pushAll(block->successorBlocks());
+ }
+
+ return true;
+ }
+
+ template<typename Filter>
</ins><span class="cx"> void handleMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
</span><span class="cx"> {
</span><span class="cx"> handleMemoryValue(
</span><span class="lines">@@ -332,7 +544,7 @@
</span><span class="cx"> MemoryMatches matches = findMemoryValue(ptr, range, filter);
</span><span class="cx"> if (replaceMemoryValue(matches, replace))
</span><span class="cx"> return;
</span><del>- addMemoryValue(m_data, m_value->as<MemoryValue>());
</del><ins>+ m_data.memoryValuesAtTail.add(m_value->as<MemoryValue>());
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<typename Replace>
</span><span class="lines">@@ -396,39 +608,13 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void addMemoryValue(ImpureBlockData& data, MemoryValue* memory)
- {
- if (verbose)
- dataLog("Adding memory: ", *memory, "\n");
-
- Matches& matches = data.memoryValues.add(memory->lastChild(), Matches()).iterator->value;
-
- if (matches.contains(memory))
- return;
-
- matches.append(memory);
- }
-
</del><span class="cx"> template<typename Filter>
</span><span class="cx"> MemoryMatches findMemoryValue(Value* ptr, HeapRange range, const Filter& filter)
</span><span class="cx"> {
</span><span class="cx"> if (verbose)
</span><del>- dataLog(*m_value, ": looking for ", *ptr, "...\n");
</del><ins>+ dataLog(*m_value, ": looking backward for ", *ptr, "...\n");
</ins><span class="cx">
</span><del>- auto find = [&] (ImpureBlockData& data) -> MemoryValue* {
- auto iter = data.memoryValues.find(ptr);
- if (iter != data.memoryValues.end()) {
- for (Value* candidateValue : iter->value) {
- if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {
- if (filter(candidateMemory))
- return candidateMemory;
- }
- }
- }
- return nullptr;
- };
-
- if (MemoryValue* match = find(m_data)) {
</del><ins>+ if (MemoryValue* match = m_data.memoryValuesAtTail.find(ptr, filter)) {
</ins><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Found ", *match, " locally.\n");
</span><span class="cx"> return { match };
</span><span class="lines">@@ -441,8 +627,6 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> BlockWorklist worklist;
</span><del>- Vector<BasicBlock*, 8> seenList;
-
</del><span class="cx"> worklist.pushAll(m_block->predecessors());
</span><span class="cx">
</span><span class="cx"> MemoryMatches matches;
</span><span class="lines">@@ -450,11 +634,10 @@
</span><span class="cx"> while (BasicBlock* block = worklist.pop()) {
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Looking at ", *block, "\n");
</span><del>- seenList.append(block);
</del><span class="cx">
</span><span class="cx"> ImpureBlockData& data = m_impureBlockData[block];
</span><span class="cx">
</span><del>- MemoryValue* match = find(data);
</del><ins>+ MemoryValue* match = data.memoryValuesAtTail.find(ptr, filter);
</ins><span class="cx"> if (match && match != m_value) {
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(" Found match: ", *match, "\n");
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3MemoryValueh"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3MemoryValue.h (197664 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3MemoryValue.h 2016-03-07 09:39:03 UTC (rev 197664)
+++ releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3MemoryValue.h 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -52,6 +52,23 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ static bool isStore(Opcode opcode)
+ {
+ switch (opcode) {
+ case Store8:
+ case Store16:
+ case Store:
+ return true;
+ default:
+ return false;
+ }
+ }
+
+ static bool isLoad(Opcode opcode)
+ {
+ return accepts(opcode) && !isStore(opcode);
+ }
+
</ins><span class="cx"> ~MemoryValue();
</span><span class="cx">
</span><span class="cx"> int32_t offset() const { return m_offset; }
</span></span></pre></div>
<a id="releasesWebKitGTKwebkit212SourceJavaScriptCoreb3B3SuccessorCollectionh"></a>
<div class="modfile"><h4>Modified: releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3SuccessorCollection.h (197664 => 197665)</h4>
<pre class="diff"><span>
<span class="info">--- releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3SuccessorCollection.h 2016-03-07 09:39:03 UTC (rev 197664)
+++ releases/WebKitGTK/webkit-2.12/Source/JavaScriptCore/b3/B3SuccessorCollection.h 2016-03-07 09:48:07 UTC (rev 197665)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -90,6 +90,50 @@
</span><span class="cx"> iterator begin() { return iterator(*this, 0); }
</span><span class="cx"> iterator end() { return iterator(*this, size()); }
</span><span class="cx">
</span><ins>+ class const_iterator {
+ public:
+ const_iterator()
+ : m_collection(nullptr)
+ , m_index(0)
+ {
+ }
+
+ const_iterator(const SuccessorCollection& collection, size_t index)
+ : m_collection(&collection)
+ , m_index(index)
+ {
+ }
+
+ BasicBlock* operator*() const
+ {
+ return m_collection->at(m_index);
+ }
+
+ const_iterator& operator++()
+ {
+ m_index++;
+ return *this;
+ }
+
+ bool operator==(const const_iterator& other) const
+ {
+ ASSERT(m_collection == other.m_collection);
+ return m_index == other.m_index;
+ }
+
+ bool operator!=(const const_iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ const SuccessorCollection* m_collection;
+ size_t m_index;
+ };
+
+ const_iterator begin() const { return const_iterator(*this, 0); }
+ const_iterator end() const { return const_iterator(*this, size()); }
+
</ins><span class="cx"> private:
</span><span class="cx"> SuccessorList& m_list;
</span><span class="cx"> };
</span></span></pre>
</div>
</div>
</body>
</html>