Turn recursive tail calls into loops
authorrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Oct 2017 16:27:44 +0000 (16:27 +0000)
committerrmorisset@apple.com <rmorisset@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 Oct 2017 16:27:44 +0000 (16:27 +0000)
commit565ad2527939503983d009b5c7bf6418a8fa5e11
tree61ccbc5b86516f76ad200759d4f1b07a0766750d
parent410632f41df2d4305272b5c26ceb0100fc91571a
Turn recursive tail calls into loops
https://bugs.webkit.org/show_bug.cgi?id=176601

Reviewed by Saam Barati.

JSTests:

Add some simple test that computes factorial in several ways, and other trivial computations.
They all tests the case where foo calls bar (in an inlineable way) that then does a tail call.
Depending on the nature of both calls, it is possible or not to turn the tail call into a loop.
I have no clear way of checking that the call was indeed transformed, but I can check that the code computes the right result
(which it doesn't if that tail call is transformed into a loop in the unsound cases).

* stress/inline-call-to-recursive-tail-call.js: Added.
(factorial.aux):
(factorial):
(factorial2.aux):
(factorial2.id):
(factorial2):
(factorial3.aux):
(factorial3):
(aux):
(factorial4):
(test):

Source/JavaScriptCore:

We want to turn recursive tail calls into loops early in the pipeline, so that the loops can then be optimized.
One difficulty is that we need to split the entry block of the function we are jumping to in order to have somewhere to jump to.
Worse: it is not necessarily the first block of the codeBlock, because of inlining! So we must do the splitting in the DFGByteCodeParser, at the same time as inlining.
We do this part through modifying the computation of the jump targets.
Importantly, we only do this splitting for functions that have tail calls.
It is the only case where the optimisation is sound, and doing the splitting unconditionnaly destroys performance on Octane/raytrace.

We must then do the actual transformation also in DFGByteCodeParser, to avoid code motion moving code out of the body of what will become a loop.
The transformation is entirely contained in handleRecursiveTailCall, which is hooked to the inlining machinery.

* bytecode/CodeBlock.h:
(JSC::CodeBlock::hasTailCalls const):
* bytecode/PreciseJumpTargets.cpp:
(JSC::getJumpTargetsForBytecodeOffset):
(JSC::computePreciseJumpTargetsInternal):
* bytecode/UnlinkedCodeBlock.cpp:
(JSC::UnlinkedCodeBlock::UnlinkedCodeBlock):
* bytecode/UnlinkedCodeBlock.h:
(JSC::UnlinkedCodeBlock::hasTailCalls const):
(JSC::UnlinkedCodeBlock::setHasTailCalls):
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::emitEnter):
(JSC::BytecodeGenerator::emitCallInTailPosition):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::allocateTargetableBlock):
(JSC::DFG::ByteCodeParser::makeBlockTargetable):
(JSC::DFG::ByteCodeParser::handleCall):
(JSC::DFG::ByteCodeParser::handleRecursiveTailCall):
(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::parse):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@223691 268f45cc-cd09-0410-ab3c-d52691b4dbfc
JSTests/ChangeLog
JSTests/stress/inline-call-to-recursive-tail-call.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/CodeBlock.h
Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp
Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp