Bug 179835 - The recursive tail call optimisation is wrong on closures
Summary: The recursive tail call optimisation is wrong on closures
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Robin Morisset
URL:
Keywords: InRadar
Depends on:
Blocks: 180044
  Show dependency treegraph
 
Reported: 2017-11-17 12:32 PST by Robin Morisset
Modified: 2017-11-29 09:33 PST (History)
9 users (show)

See Also:


Attachments
testcase: merge-sort-cps.js (3.46 KB, application/x-javascript)
2017-11-17 12:32 PST, Robin Morisset
no flags Details
Patch (9.20 KB, patch)
2017-11-27 10:36 PST, Robin Morisset
no flags Details | Formatted Diff | Diff
Patch (10.54 KB, patch)
2017-11-29 07:37 PST, Robin Morisset
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Robin Morisset 2017-11-17 12:32:22 PST
Created attachment 327215 [details]
testcase: merge-sort-cps.js

We speculate on the executable of the callee, instead of the callee itself. And two different instances of a closure share the same executable even when they have different captured variables.
This bug manifests as a non-deterministic infinite loop in merge-sort-cps.js (attached).
This happens when the only value that has been seen for cont in "cont(result)" is the "(right) => {..}" closure, because it is then turned into an infinite loop.

The problem is in the use of emitFunctionChecks: that function only checks the executable of the callee. If we checked for the callee itself in the case of closures, there would be no such problems.
Comment 1 Robin Morisset 2017-11-27 10:36:17 PST
Created attachment 327645 [details]
Patch
Comment 2 Saam Barati 2017-11-28 11:30:13 PST
Comment on attachment 327645 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=327645&action=review

> Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp:1436
> +    // 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 (callLinkStatus[0].isClosureCall())
> +        return false;

How is this only a problem with this code an not all of inlining? Can you elaborate? Is the bug if we constant fold loading a closure variable?

Can you add a semantic test for this and not just a benchmark?
Comment 3 Robin Morisset 2017-11-29 07:37:29 PST
Created attachment 327852 [details]
Patch
Comment 4 Robin Morisset 2017-11-29 07:47:16 PST
I have rebased the patch so it applies cleanly, and added a small stress test as requested.

How inlining avoids this problem is interesting and quite subtle:
- The variable is taken from a GetScope which in turn comes from a GetCallee.
- From DFGSpeculativeJIT, we see that GetCallee takes its value from origin.inlineCallFrame->calleeRecovery.virtualRegister() in the case where origin.inlineCallFrame->isClosureCall.
- inlineCallFrame->isClosureCall is set in the constructor of inlineStackEntry, called by inlineCall()
- inlineCallFrame->calleeRecovery is set in DFGStackLayoutPhase, from InlineVariableData::calleeVariable
- Finally, InlineVariableData::calleeVariable is set in inlineCall() in the DFGByteCodeParser.cpp

It is not clear at all how any of this machinery may be reused for this optimization.
So my current plan is to disable the optimization for closures altogether as a stopgap (this patch), and then try in https://bugs.webkit.org/show_bug.cgi?id=180044 to add it back a lot more carefully, probably with some explicit branch on the callee.
Comment 5 WebKit Commit Bot 2017-11-29 09:31:57 PST
Comment on attachment 327852 [details]
Patch

Clearing flags on attachment: 327852

Committed r225270: <https://trac.webkit.org/changeset/225270>
Comment 6 WebKit Commit Bot 2017-11-29 09:31:59 PST
All reviewed patches have been landed.  Closing bug.
Comment 7 Radar WebKit Bug Importer 2017-11-29 09:33:35 PST
<rdar://problem/35749564>