- Revision
- 225270
- Author
- rmoris...@apple.com
- Date
- 2017-11-29 09:31:54 -0800 (Wed, 29 Nov 2017)
Log Message
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/_javascript_Core:
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:
Modified Paths
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (225269 => 225270)
--- trunk/JSTests/ChangeLog 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/JSTests/ChangeLog 2017-11-29 17:31:54 UTC (rev 225270)
@@ -1,3 +1,13 @@
+2017-11-29 Robin Morisset <rmoris...@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 <jfbast...@apple.com>
_javascript_ rest function parameter with negative index leads to bad DFG abstract interpretation
Added: trunk/JSTests/stress/closure-recursive-tail-call.js (0 => 225270)
--- 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)
@@ -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;
+}
Modified: trunk/PerformanceTests/ChangeLog (225269 => 225270)
--- trunk/PerformanceTests/ChangeLog 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/PerformanceTests/ChangeLog 2017-11-29 17:31:54 UTC (rev 225270)
@@ -1,3 +1,24 @@
+2017-11-29 Robin Morisset <rmoris...@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 <an...@apple.com>
Add performance test for inlines and inline-blocks without text
Added: trunk/PerformanceTests/TailBench9000/merge-sort-cps.js (0 => 225270)
--- 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)
@@ -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);
Modified: trunk/Source/_javascript_Core/ChangeLog (225269 => 225270)
--- trunk/Source/_javascript_Core/ChangeLog 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-11-29 17:31:54 UTC (rev 225270)
@@ -1,3 +1,16 @@
+2017-11-29 Robin Morisset <rmoris...@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 <pecor...@apple.com>
Web Inspector: Cleanup Inspector classes be more consistent about using fast malloc / noncopyable
Modified: trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp (225269 => 225270)
--- trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Source/_javascript_Core/dfg/DFGByteCodeParser.cpp 2017-11-29 17:31:54 UTC (rev 225270)
@@ -1427,6 +1427,11 @@
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 @@
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 @@
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);
Modified: trunk/Tools/ChangeLog (225269 => 225270)
--- trunk/Tools/ChangeLog 2017-11-29 17:11:36 UTC (rev 225269)
+++ trunk/Tools/ChangeLog 2017-11-29 17:31:54 UTC (rev 225270)
@@ -1,3 +1,14 @@
+2017-11-29 Robin Morisset <rmoris...@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 <cgar...@igalia.com>
WebDriver: add an option to dump test results to a json file
Modified: trunk/Tools/Scripts/run-jsc-benchmarks (225269 => 225270)
--- 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)
@@ -3038,7 +3038,7 @@
}
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);
}
