The recursive tail call optimisation is wrong on closures
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Nov 2017 17:31:54 +0000 (17:31 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 29 Nov 2017 17:31:54 +0000 (17:31 +0000)
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:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@225270 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/closure-recursive-tail-call.js [new file with mode: 0644]
PerformanceTests/ChangeLog
PerformanceTests/TailBench9000/merge-sort-cps.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Tools/ChangeLog
Tools/Scripts/run-jsc-benchmarks

index a29dbae..b384c71 100644 (file)
@@ -1,3 +1,13 @@
+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):
+
 2017-11-27  JF Bastien  <jfbastien@apple.com>
 
         JavaScript rest function parameter with negative index leads to bad DFG abstract interpretation
diff --git a/JSTests/stress/closure-recursive-tail-call.js b/JSTests/stress/closure-recursive-tail-call.js
new file mode 100644 (file)
index 0000000..e70c9ae
--- /dev/null
@@ -0,0 +1,21 @@
+"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;
+}
index e26f744..c13efdf 100644 (file)
@@ -1,3 +1,24 @@
+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):
+
 2017-11-22  Antti Koivisto  <antti@apple.com>
 
         Add performance test for inlines and inline-blocks without text
diff --git a/PerformanceTests/TailBench9000/merge-sort-cps.js b/PerformanceTests/TailBench9000/merge-sort-cps.js
new file mode 100644 (file)
index 0000000..fff31a6
--- /dev/null
@@ -0,0 +1,150 @@
+"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);
index 9c2f910..e21a034 100644 (file)
@@ -1,3 +1,16 @@
+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):
+
 2017-11-28  Joseph Pecoraro  <pecoraro@apple.com>
 
         Web Inspector: Cleanup Inspector classes be more consistent about using fast malloc / noncopyable
index 5165489..ef00e42 100644 (file)
@@ -1427,6 +1427,11 @@ bool ByteCodeParser::handleRecursiveTailCall(CallVariant callVariant, int regist
     if (UNLIKELY(!Options::optimizeRecursiveTailCalls()))
         return false;
 
+    // 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;
+
     auto targetExecutable = callVariant.executable();
     InlineStackEntry* stackEntry = m_inlineStackTop;
     do {
@@ -1446,8 +1451,10 @@ bool ByteCodeParser::handleRecursiveTailCall(CallVariant callVariant, int regist
                 return false;
         }
 
-        // We must add some check that the profiling information was correct and the target of this call is what we thought
+        // We must add some check that the profiling information was correct and the target of this call is what we thought.
         emitFunctionCheckIfNeeded();
+        // We flush everything, as if we were in the backedge of a loop (see treatment of op_jmp in parseBlock).
+        flushForTerminal();
 
         // We must set the arguments to the right values
         int argIndex = 0;
@@ -1475,9 +1482,6 @@ bool ByteCodeParser::handleRecursiveTailCall(CallVariant callVariant, int regist
         m_inlineStackTop = oldStackTop;
         m_exitOK = false;
 
-        // We flush everything, as if we were in the backedge of a loop (see treatment of op_jmp in parseBlock).
-        flushForTerminal();
-
         BasicBlock** entryBlockPtr = tryBinarySearch<BasicBlock*, unsigned>(stackEntry->m_blockLinkingTargets, stackEntry->m_blockLinkingTargets.size(), OPCODE_LENGTH(op_enter), getBytecodeBeginForBlock);
         RELEASE_ASSERT(entryBlockPtr);
         addJumpTo(*entryBlockPtr);
index 158c1bb..97e0cbc 100644 (file)
@@ -1,3 +1,14 @@
+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:
+
 2017-11-28  Carlos Garcia Campos  <cgarcia@igalia.com>
 
         WebDriver: add an option to dump test results to a json file
index 0504a57..713ddcb 100755 (executable)
@@ -3038,7 +3038,7 @@ begin
   }
 
   TAILBENCH = BenchmarkSuite.new("TailBench", :geometricMean, 0)
-  ["n-body", "merge-sort", "bf-interpreter"].each {
+  ["n-body", "merge-sort", "merge-sort-cps", "bf-interpreter"].each {
     | name |
     TAILBENCH.add TailBenchBenchmark.new(name);
   }