Changeset 223691 in webkit

Timestamp:

Oct 19, 2017 9:27:44 AM (7 years ago)

Author:

rmorisset@apple.com

Message:

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):

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/inline-call-to-recursive-tail-call.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/bytecode/CodeBlock.h (modified) (2 diffs)
• Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp (modified) (2 diffs)
• Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp (modified) (1 diff)
• Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h (modified) (2 diffs)
• Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp (modified) (2 diffs)
• Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp (modified) (10 diffs)

trunk/JSTests/ChangeLog

@@ +1 @@
+2017-10-19  Robin Morisset  <rmorisset@apple.com>
+
+        Turn recursive tail calls into loops
+        https://bugs.webkit.org/show_bug.cgi?id=176601
+
+        Reviewed by Saam Barati.
+
+        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):
+
 2017-10-18  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2017-10-19  Robin Morisset  <rmorisset@apple.com>
+
+        Turn recursive tail calls into loops
+        https://bugs.webkit.org/show_bug.cgi?id=176601
+
+        Reviewed by Saam Barati.
+
+        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):
+
 2017-10-18  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/bytecode/CodeBlock.h

@@ -743 +743 @@
     // Call this to cause an optimization trigger to fire soon, but
     // not necessarily the next one. This makes sense if optimization
-    // succeeds. Successfuly optimization means that all calls are
+    // succeeds. Successful optimization means that all calls are
     // relinked to the optimized code, so this only affects call
     // frames that are still executing this CodeBlock. The value here
@@ -925 +925 @@
     std::optional<CodeOrigin> findPC(void* pc);
 #endif
+
+    bool hasTailCalls() const { return m_unlinkedCode->hasTailCalls(); }
 
 protected:

trunk/Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp

@@ -43 +43 @@
     if (opcodeID == op_loop_hint)
         out.append(bytecodeOffset);
+    else if (opcodeID == op_enter && codeBlock->hasTailCalls()) {
+        // We need to insert a jump after op_enter, so recursive tail calls have somewhere to jump to.
+        // But we only want to pay that price for functions that have at least one tail call.
+        out.append(bytecodeOffset + opcodeLengths[op_enter]);
+    }
 }
 
@@ -54 +59 @@
 {
     ASSERT(out.isEmpty());
-    
-    // We will derive a superset of the jump targets that the code block thinks it has.
-    // So, if the code block claims there are none, then we are done.
+
+    // The code block has a superset of the jump targets. So if it claims to have none, we are done.
     if (Mode == ComputePreciseJumpTargetsMode::FollowCodeBlockClaim && !codeBlock->numberOfJumpTargets())
         return;

trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp

@@ -71 +71 @@
     , m_derivedContextType(static_cast<unsigned>(info.derivedContextType()))
     , m_evalContextType(static_cast<unsigned>(info.evalContextType()))
+    , m_hasTailCalls(false)
     , m_lineCount(0)
     , m_endColumn(UINT_MAX)

trunk/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.h

@@ -130 +130 @@
     bool isArrowFunctionContext() const { return m_isArrowFunctionContext; }
     bool isClassContext() const { return m_isClassContext; }
+    bool hasTailCalls() const { return m_hasTailCalls; }
+    void setHasTailCalls() { m_hasTailCalls = true; }
 
     void addExpressionInfo(unsigned instructionOffset, int divot,
@@ -443 +445 @@
     unsigned m_derivedContextType : 2;
     unsigned m_evalContextType : 2;
+    unsigned m_hasTailCalls : 1;
     unsigned m_lineCount;
     unsigned m_endColumn;

trunk/Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp

@@ -1314 +1314 @@
 {
     emitOpcode(op_enter);
+
+    // We must add the end of op_enter as a potential jump target, because the bytecode parser may decide to split its basic block
+    // to have somewhere to jump to if there is a recursive tail-call that points to this function.
+    m_codeBlock->addJumpTarget(instructions().size());
+    // This disables peephole optimizations when an instruction is a jump target
+    m_lastOpcodeID = op_end;
 }
 
@@ -3348 +3354 @@
 RegisterID* BytecodeGenerator::emitCallInTailPosition(RegisterID* dst, RegisterID* func, ExpectedFunction expectedFunction, CallArguments& callArguments, const JSTextPosition& divot, const JSTextPosition& divotStart, const JSTextPosition& divotEnd, DebuggableCall debuggableCall)
 {
-    return emitCall(m_inTailPosition ? op_tail_call : op_call, dst, func, expectedFunction, callArguments, divot, divotStart, divotEnd, debuggableCall);
+    if (m_inTailPosition) {
+        m_codeBlock->setHasTailCalls();
+        return emitCall(op_tail_call, dst, func, expectedFunction, callArguments, divot, divotStart, divotEnd, debuggableCall);
+    }
+    return emitCall(op_call, dst, func, expectedFunction, callArguments, divot, divotStart, divotEnd, debuggableCall);
 }
 

trunk/Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp

@@ -225 +225 @@
     void emitArgumentPhantoms(int registerOffset, int argumentCountIncludingThis);
     Node* getArgumentCount();
+    bool handleRecursiveTailCall(Node* callTargetNode, const CallLinkStatus&, int registerOffset, VirtualRegister thisArgument, int argumentCountIncludingThis);
     unsigned inliningCost(CallVariant, int argumentCountIncludingThis, InlineCallFrame::Kind); // Return UINT_MAX if it's not an inlining candidate. By convention, intrinsics have a cost of 1.
     // Handle inlining. Return true if it succeeded, false if we need to plant a call.
@@ -232 +233 @@
     template<typename ChecksFunctor>
     void inlineCall(Node* callTargetNode, int resultOperand, CallVariant, int registerOffset, int argumentCountIncludingThis, unsigned nextOffset, InlineCallFrame::Kind, BasicBlock* continuationBlock, const ChecksFunctor& insertChecks);
-    void cancelLinkingForBlock(InlineStackEntry*, BasicBlock*); // Only works when the given block is the last one to have been added for that inline stack entry.
     // Handle intrinsic functions. Return true if it succeeded, false if we need to plant a call.
     template<typename ChecksFunctor>
@@ -1128 +1128 @@
         Vector<BasicBlock*> m_blockLinkingTargets;
 
-        // This is set by op_enter in parseBlock(), and indicates the first block of the function.
-        BasicBlock* m_entryBlock;
-
         // Optional: a continuation block for returns to jump to. It is set by early returns if it does not exist.
         BasicBlock* m_continuationBlock;
@@ -1218 +1215 @@
     Ref<BasicBlock> block = adoptRef(*new BasicBlock(bytecodeIndex, m_numArguments, m_numLocals, 1));
     BasicBlock* blockPtr = block.ptr();
+    // m_blockLinkingTargets must always be sorted in increasing order of bytecodeBegin
+    if (m_inlineStackTop->m_blockLinkingTargets.size())
+        ASSERT(m_inlineStackTop->m_blockLinkingTargets.last()->bytecodeBegin < bytecodeIndex);
     m_inlineStackTop->m_blockLinkingTargets.append(blockPtr);
     m_graph.appendBlock(WTFMove(block));
@@ -1235 +1235 @@
     ASSERT(block->bytecodeBegin == UINT_MAX);
     block->bytecodeBegin = bytecodeIndex;
+    // m_blockLinkingTargets must always be sorted in increasing order of bytecodeBegin
+    if (m_inlineStackTop->m_blockLinkingTargets.size())
+        ASSERT(m_inlineStackTop->m_blockLinkingTargets.last()->bytecodeBegin < bytecodeIndex);
     m_inlineStackTop->m_blockLinkingTargets.append(block);
 }
@@ -1295 +1298 @@
     if (callLinkStatus.canOptimize()) {
         VirtualRegister thisArgument = virtualRegisterForArgument(0, registerOffset);
+
+        if (op == TailCall && handleRecursiveTailCall(callTarget, callLinkStatus, registerOffset, thisArgument, argumentCountIncludingThis))
+            return Terminal;
 
         // Inlining is quite complex, and managed by a pipeline of functions:
@@ -1411 +1417 @@
     for (int i = 0; i < argumentCountIncludingThis; ++i)
         addToGraph(Phantom, get(virtualRegisterForArgument(i, registerOffset)));
+}
+
+bool ByteCodeParser::handleRecursiveTailCall(Node* callTargetNode, const CallLinkStatus& callLinkStatus, int registerOffset, VirtualRegister thisArgument, int argumentCountIncludingThis)
+{
+    // FIXME: We currently only do this optimisation in the simple, non-polymorphic case.
+    // https://bugs.webkit.org/show_bug.cgi?id=178390
+    if (callLinkStatus.couldTakeSlowPath() || callLinkStatus.size() != 1)
+        return false;
+
+    auto targetExecutable = callLinkStatus[0].executable();
+    InlineStackEntry* stackEntry = m_inlineStackTop;
+    do {
+        if (targetExecutable != stackEntry->executable())
+            continue;
+        VERBOSE_LOG("   We found a recursive tail call, trying to optimize it into a jump.\n");
+
+        if (auto* callFrame = stackEntry->m_inlineCallFrame) {
+            // Some code may statically use the argument count from the InlineCallFrame, so it would be invalid to loop back if it does not match.
+            // We "continue" instead of returning false in case another stack entry further on the stack has the right number of arguments.
+            if (argumentCountIncludingThis != static_cast<int>(callFrame->argumentCountIncludingThis))
+                continue;
+        } else {
+            // We are in the machine code entry (i.e. the original caller).
+            // If we have more arguments than the number of parameters to the function, it is not clear where we could put them on the stack.
+            if (argumentCountIncludingThis > m_codeBlock->numParameters())
+                return false;
+        }
+
+        // We must add some check that the profiling information was correct and the target of this call is what we thought
+        emitFunctionChecks(callLinkStatus[0], callTargetNode, thisArgument);
+        // 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;
+        for (; argIndex < argumentCountIncludingThis; ++argIndex) {
+            Node* value = get(virtualRegisterForArgument(argIndex, registerOffset));
+            setDirect(stackEntry->remapOperand(virtualRegisterForArgument(argIndex)), value, NormalSet);
+        }
+        Node* undefined = addToGraph(JSConstant, OpInfo(m_constantUndefined));
+        for (; argIndex < stackEntry->m_codeBlock->numParameters(); ++argIndex)
+            setDirect(stackEntry->remapOperand(virtualRegisterForArgument(argIndex)), undefined, NormalSet);
+
+        // We must repeat the work of op_enter here as we will jump right after it.
+        // We jump right after it and not before it, because of some invariant saying that a CFG root cannot have predecessors in the IR.
+        for (int i = 0; i < stackEntry->m_codeBlock->m_numVars; ++i)
+            setDirect(stackEntry->remapOperand(virtualRegisterForLocal(i)), undefined, NormalSet);
+
+        // We want to emit the SetLocals with an exit origin that points to the place we are jumping to.
+        unsigned oldIndex = m_currentIndex;
+        auto oldStackTop = m_inlineStackTop;
+        m_inlineStackTop = stackEntry;
+        m_currentIndex = OPCODE_LENGTH(op_enter);
+        m_exitOK = true;
+        processSetLocalQueue();
+        m_currentIndex = oldIndex;
+        m_inlineStackTop = oldStackTop;
+        m_exitOK = false;
+
+        BasicBlock** entryBlockPtr = tryBinarySearch<BasicBlock*, unsigned>(stackEntry->m_blockLinkingTargets, stackEntry->m_blockLinkingTargets.size(), OPCODE_LENGTH(op_enter), getBytecodeBeginForBlock);
+        RELEASE_ASSERT(entryBlockPtr);
+        addJumpTo(*entryBlockPtr);
+        return true;
+        // It would be unsound to jump over a non-tail call: the "tail" call is not really a tail call in that case.
+    } while (stackEntry->m_inlineCallFrame && stackEntry->m_inlineCallFrame->kind == TailCall && (stackEntry = stackEntry->m_caller));
+
+    // The tail call was not recursive
+    return false;
 }
 
@@ -4215 +4289 @@
                 set(virtualRegisterForLocal(i), undefined, ImmediateNakedSet);
 
-            m_inlineStackTop->m_entryBlock = m_currentBlock;
-
             NEXT_OPCODE(op_enter);
         }
@@ -5403 +5475 @@
                 NEXT_OPCODE(op_tail_call);
             else
-                LAST_OPCODE(op_tail_call);
+                LAST_OPCODE_LINKED(op_tail_call);
+            // We use LAST_OPCODE_LINKED instead of LAST_OPCODE because if the tail call was optimized, it may now be a jump to a bytecode index in a different InlineStackEntry.
         }
 
@@ -6431 +6504 @@
 
     m_graph.determineReachability();
-    if (Options::verboseDFGBytecodeParsing())
-        m_graph.dump();
     m_graph.killUnreachableBlocks();