<!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>[225270] 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/225270">225270</a></dd>
<dt>Author</dt> <dd>rmorisset@apple.com</dd>
<dt>Date</dt> <dd>2017-11-29 09:31:54 -0800 (Wed, 29 Nov 2017)</dd>
</dl>

<h3>Log Message</h3>
<pre>The recursive tail call optimisation is wrong on closures
https://bugs.webkit.org/show_bug.cgi?id=179835

Reviewed by Saam Barati.

JSTests:

* stress/closure-recursive-tail-call.js: Added.
(makeClosure):

PerformanceTests:

This new benchmark is a very close variant of the merge-sort benchmark, that writes mergeSorted in a kinda CPS style,
to stress the use of closures, and of polymorphic calls.

* TailBench9000/merge-sort-cps.js: Added.
(createRNG):
(mergeSorted):
(checkSorted.check):
(add):
(build):
(compare):
(checkSpectrum):
(buildArray):
(test):

Source/JavaScriptCore:

The problem is that we only check the executable of the callee, not whatever variables might have been captured.
As a stopgap measure this patch just does not do the optimisation for closures.

* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::handleRecursiveTailCall):

Tools:

This just includes merge-sort-cps.js to the list of benchmarks ran by run-jsc-benchmarks --tail-bench

* Scripts/run-jsc-benchmarks:</pre>

<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkJSTestsChangeLog">trunk/JSTests/ChangeLog</a></li>
<li><a href="#trunkPerformanceTestsChangeLog">trunk/PerformanceTests/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoredfgDFGByteCodeParsercpp">trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsScriptsrunjscbenchmarks">trunk/Tools/Scripts/run-jsc-benchmarks</a></li>
</ul>

<h3>Added Paths</h3>
<ul>
<li><a href="#trunkJSTestsstressclosurerecursivetailcalljs">trunk/JSTests/stress/closure-recursive-tail-call.js</a></li>
<li><a href="#trunkPerformanceTestsTailBench9000mergesortcpsjs">trunk/PerformanceTests/TailBench9000/merge-sort-cps.js</a></li>
</ul>

</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkJSTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/JSTests/ChangeLog (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/ChangeLog  2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/JSTests/ChangeLog     2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -1,3 +1,13 @@
</span><ins>+2017-11-29  Robin Morisset  <rmorisset@apple.com>
+
+        The recursive tail call optimisation is wrong on closures
+        https://bugs.webkit.org/show_bug.cgi?id=179835
+
+        Reviewed by Saam Barati.
+
+        * stress/closure-recursive-tail-call.js: Added.
+        (makeClosure):
+
</ins><span class="cx"> 2017-11-27  JF Bastien  <jfbastien@apple.com>
</span><span class="cx"> 
</span><span class="cx">         JavaScript rest function parameter with negative index leads to bad DFG abstract interpretation
</span></span></pre></div>
<a id="trunkJSTestsstressclosurerecursivetailcalljs"></a>
<div class="addfile"><h4>Added: trunk/JSTests/stress/closure-recursive-tail-call.js (0 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/JSTests/stress/closure-recursive-tail-call.js                              (rev 0)
+++ trunk/JSTests/stress/closure-recursive-tail-call.js 2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -0,0 +1,21 @@
</span><ins>+"use strict";
+
+function makeClosure(x)
+{
+    return (f) => {
+        if (x == 42) {
+            x = 0;
+            return f(f);
+        }
+        else
+            return x;
+    }
+}
+
+for (var i = 0; i < 1000; ++i) {
+    var g = makeClosure(42);
+    var h = makeClosure(41);
+    var value = g(h);
+    if (value != 41)
+        throw "Wrong result, got: " + value;
+}
</ins></span></pre></div>
<a id="trunkPerformanceTestsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/PerformanceTests/ChangeLog (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/ChangeLog 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/PerformanceTests/ChangeLog    2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -1,3 +1,24 @@
</span><ins>+2017-11-29  Robin Morisset  <rmorisset@apple.com>
+
+        The recursive tail call optimisation is wrong on closures
+        https://bugs.webkit.org/show_bug.cgi?id=179835
+
+        Reviewed by Saam Barati.
+
+        This new benchmark is a very close variant of the merge-sort benchmark, that writes mergeSorted in a kinda CPS style,
+        to stress the use of closures, and of polymorphic calls.
+
+        * TailBench9000/merge-sort-cps.js: Added.
+        (createRNG):
+        (mergeSorted):
+        (checkSorted.check):
+        (add):
+        (build):
+        (compare):
+        (checkSpectrum):
+        (buildArray):
+        (test):
+
</ins><span class="cx"> 2017-11-22  Antti Koivisto  <antti@apple.com>
</span><span class="cx"> 
</span><span class="cx">         Add performance test for inlines and inline-blocks without text
</span></span></pre></div>
<a id="trunkPerformanceTestsTailBench9000mergesortcpsjs"></a>
<div class="addfile"><h4>Added: trunk/PerformanceTests/TailBench9000/merge-sort-cps.js (0 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/PerformanceTests/TailBench9000/merge-sort-cps.js                           (rev 0)
+++ trunk/PerformanceTests/TailBench9000/merge-sort-cps.js      2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -0,0 +1,150 @@
</span><ins>+"use strict";
+
+function createRNG(seed)
+{
+    return function() {
+        // Robert Jenkins' 32 bit integer hash function.
+        seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
+        seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
+        seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
+        seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
+        seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
+        seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
+        return (seed & 0xfffffff) / 0x10000000;
+    };
+}
+
+let random = createRNG(0x7a11bec8);
+
+function mergeSorted(array, cont)
+{
+    if (array.length <= 1)
+        return cont(array);
+    
+    let midIndex = Math.floor(array.length / 2);
+    return mergeSorted(array.slice(0, midIndex), (left) => {
+    return mergeSorted(array.slice(midIndex), (right) => {
+    
+    let result = [];
+    
+    function finish(source, index)
+    {
+        if (index >= source.length)
+            return;
+        result.push(source[index]);
+        return finish(source, index + 1);
+    }
+    
+    function merge(leftIndex, rightIndex)
+    {
+        if (leftIndex >= left.length)
+            return finish(right, rightIndex);
+        if (rightIndex >= right.length)
+            return finish(left, leftIndex);
+        
+        let leftValue = left[leftIndex];
+        let rightValue = right[rightIndex];
+        if (leftValue < rightValue) {
+            result.push(leftValue);
+            return merge(leftIndex + 1, rightIndex);
+        }
+        result.push(rightValue);
+        return merge(leftIndex, rightIndex + 1);
+    }
+    
+    merge(0, 0);
+    
+    return cont(result);
+}); }); }
+
+function checkSorted(array)
+{
+    function check(index)
+    {
+        if (index >= array.length - 1)
+            return;
+        
+        if (array[index] > array[index + 1])
+            throw new Error("array not sorted at index " + index + ": " + array);
+        
+        return check(index + 1);
+    }
+    
+    check(0);
+}
+
+function checkSpectrum(a, b)
+{
+    var aMap = new Map();
+    var bMap = new Map();
+    
+    function add(map, value)
+    {
+        let existing = map.get(value);
+        if (existing == null)
+            existing = 0;
+        map.set(value, existing + 1);
+    }
+    
+    function build(map, array, index)
+    {
+        if (index >= array.length)
+            return;
+        
+        add(map, array[index]);
+        return build(map, array, index + 1);
+    }
+    
+    build(aMap, a, 0);
+    build(bMap, b, 0);
+    
+    function compare(keys)
+    {
+        let entry = keys.next();
+        if (entry.done)
+            return;
+        if (aMap.get(entry.value) != bMap.get(entry.value))
+            throw new Error("arrays don't have the same number of: " + entry.value + " (a = " + a + ", b = " + b + ")");
+        return compare(keys);
+    }
+    
+    compare(aMap.keys());
+}
+
+function buildArray(length, value)
+{
+    let array = [];
+    
+    function build()
+    {
+        if (array.length >= length)
+            return;
+        array.push(value(array.length));
+        return build();
+    }
+    
+    build();
+    
+    return array;
+}
+
+let arrays = [
+    buildArray(10, x => x),
+    buildArray(10, x => -x),
+    buildArray(1000, x => random())
+];
+
+function test(index)
+{
+    if (index >= arrays.length)
+        return;
+    
+    let array = arrays[index];
+    mergeSorted(array, (sorted) => {
+    checkSorted(sorted);
+    checkSpectrum(array, sorted);
+    test(index + 1);
+}); }
+
+for (var i = 0; i < 100; ++i)
+    test(0);
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog    2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Source/JavaScriptCore/ChangeLog       2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+2017-11-29  Robin Morisset  <rmorisset@apple.com>
+
+        The recursive tail call optimisation is wrong on closures
+        https://bugs.webkit.org/show_bug.cgi?id=179835
+
+        Reviewed by Saam Barati.
+
+        The problem is that we only check the executable of the callee, not whatever variables might have been captured.
+        As a stopgap measure this patch just does not do the optimisation for closures.
+
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::handleRecursiveTailCall):
+
</ins><span class="cx"> 2017-11-28  Joseph Pecoraro  <pecoraro@apple.com>
</span><span class="cx"> 
</span><span class="cx">         Web Inspector: Cleanup Inspector classes be more consistent about using fast malloc / noncopyable
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoredfgDFGByteCodeParsercpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp    2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp       2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -1427,6 +1427,11 @@
</span><span class="cx">     if (UNLIKELY(!Options::optimizeRecursiveTailCalls()))
</span><span class="cx">         return false;
</span><span class="cx"> 
</span><ins>+    // Currently we cannot do this optimisation for closures. The problem is that "emitFunctionChecks" which we use later is too coarse, only checking the executable
+    // and not the value of captured variables.
+    if (callVariant.isClosureCall())
+        return false;
+
</ins><span class="cx">     auto targetExecutable = callVariant.executable();
</span><span class="cx">     InlineStackEntry* stackEntry = m_inlineStackTop;
</span><span class="cx">     do {
</span><span class="lines">@@ -1446,8 +1451,10 @@
</span><span class="cx">                 return false;
</span><span class="cx">         }
</span><span class="cx"> 
</span><del>-        // We must add some check that the profiling information was correct and the target of this call is what we thought
</del><ins>+        // We must add some check that the profiling information was correct and the target of this call is what we thought.
</ins><span class="cx">         emitFunctionCheckIfNeeded();
</span><ins>+        // We flush everything, as if we were in the backedge of a loop (see treatment of op_jmp in parseBlock).
+        flushForTerminal();
</ins><span class="cx"> 
</span><span class="cx">         // We must set the arguments to the right values
</span><span class="cx">         int argIndex = 0;
</span><span class="lines">@@ -1475,9 +1482,6 @@
</span><span class="cx">         m_inlineStackTop = oldStackTop;
</span><span class="cx">         m_exitOK = false;
</span><span class="cx"> 
</span><del>-        // We flush everything, as if we were in the backedge of a loop (see treatment of op_jmp in parseBlock).
-        flushForTerminal();
-
</del><span class="cx">         BasicBlock** entryBlockPtr = tryBinarySearch<BasicBlock*, unsigned>(stackEntry->m_blockLinkingTargets, stackEntry->m_blockLinkingTargets.size(), OPCODE_LENGTH(op_enter), getBytecodeBeginForBlock);
</span><span class="cx">         RELEASE_ASSERT(entryBlockPtr);
</span><span class="cx">         addJumpTo(*entryBlockPtr);
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog    2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Tools/ChangeLog       2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -1,3 +1,14 @@
</span><ins>+2017-11-29  Robin Morisset  <rmorisset@apple.com>
+
+        The recursive tail call optimisation is wrong on closures
+        https://bugs.webkit.org/show_bug.cgi?id=179835
+
+        Reviewed by Saam Barati.
+
+        This just includes merge-sort-cps.js to the list of benchmarks ran by run-jsc-benchmarks --tail-bench
+
+        * Scripts/run-jsc-benchmarks:
+
</ins><span class="cx"> 2017-11-28  Carlos Garcia Campos  <cgarcia@igalia.com>
</span><span class="cx"> 
</span><span class="cx">         WebDriver: add an option to dump test results to a json file
</span></span></pre></div>
<a id="trunkToolsScriptsrunjscbenchmarks"></a>
<div class="modfile"><h4>Modified: trunk/Tools/Scripts/run-jsc-benchmarks (225269 => 225270)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/Scripts/run-jsc-benchmarks   2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Tools/Scripts/run-jsc-benchmarks      2017-11-29 17:31:54 UTC (rev 225270)
</span><span class="lines">@@ -3038,7 +3038,7 @@
</span><span class="cx">   }
</span><span class="cx"> 
</span><span class="cx">   TAILBENCH = BenchmarkSuite.new("TailBench", :geometricMean, 0)
</span><del>-  ["n-body", "merge-sort", "bf-interpreter"].each {
</del><ins>+  ["n-body", "merge-sort", "merge-sort-cps", "bf-interpreter"].each {
</ins><span class="cx">     | name |
</span><span class="cx">     TAILBENCH.add TailBenchBenchmark.new(name);
</span><span class="cx">   }
</span></span></pre>
</div>
</div>

</body>
</html>