Changeset 179357 in webkit for trunk/Source/JavaScriptCore/jit/Repatch.cpp

Timestamp:

Jan 29, 2015, 12:33:45 PM (10 years ago)

Author:

[email protected]

Message:

Polymorphic call inlining should be based on polymorphic call inline caching rather than logging
​https://bugs.webkit.org/show_bug.cgi?id=140660

Reviewed by Geoffrey Garen.

When we first implemented polymorphic call inlining, we did the profiling based on a call
edge log. The idea was to store each call edge (a tuple of call site and callee) into a
global log that was processed lazily. Processing the log would give precise counts of call
edges, and could be used to drive well-informed inlining decisions - polymorphic or not.
This was a speed-up on throughput tests but a slow-down for latency tests. It was a net win
nonetheless.

Experience with this code shows three things. First, the call edge profiler is buggy and
complex. It would take work to fix the bugs. Second, the call edge profiler incurs lots of
overhead for latency code that we care deeply about. Third, it's not at all clear that
having call edge counts for every possible callee is any better than just having call edge
counts for the limited number of callees that an inline cache would catch.

So, this patch removes the call edge profiler and replaces it with a polymorphic call inline
cache. If we miss the basic call inline cache, we inflate the cache to be a jump to an
out-of-line stub that cases on the previously known callees. If that misses again, then we
rewrite that stub to include the new callee. We do this up to some number of callees. If we
hit the limit then we switch to using a plain virtual call.

Substantial speed-up on V8Spider; undoes the slow-down that the original call edge profiler
caused. Might be a SunSpider speed-up (below 1%), depending on hardware.

• CMakeLists.txt:
• JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
• JavaScriptCore.xcodeproj/project.pbxproj:
• bytecode/CallEdge.h:

(JSC::CallEdge::count):
(JSC::CallEdge::CallEdge):

• bytecode/CallEdgeProfile.cpp: Removed.
• bytecode/CallEdgeProfile.h: Removed.
• bytecode/CallEdgeProfileInlines.h: Removed.
• bytecode/CallLinkInfo.cpp:

(JSC::CallLinkInfo::unlink):
(JSC::CallLinkInfo::visitWeak):

• bytecode/CallLinkInfo.h:
• bytecode/CallLinkStatus.cpp:

(JSC::CallLinkStatus::CallLinkStatus):
(JSC::CallLinkStatus::computeFor):
(JSC::CallLinkStatus::computeFromCallLinkInfo):
(JSC::CallLinkStatus::isClosureCall):
(JSC::CallLinkStatus::makeClosureCall):
(JSC::CallLinkStatus::dump):
(JSC::CallLinkStatus::computeFromCallEdgeProfile): Deleted.

• bytecode/CallLinkStatus.h:

(JSC::CallLinkStatus::CallLinkStatus):
(JSC::CallLinkStatus::isSet):
(JSC::CallLinkStatus::variants):
(JSC::CallLinkStatus::size):
(JSC::CallLinkStatus::at):
(JSC::CallLinkStatus::operator[]):
(JSC::CallLinkStatus::canOptimize):
(JSC::CallLinkStatus::edges): Deleted.
(JSC::CallLinkStatus::canTrustCounts): Deleted.

• bytecode/CallVariant.cpp:

(JSC::variantListWithVariant):
(JSC::despecifiedVariantList):

• bytecode/CallVariant.h:
• bytecode/CodeBlock.cpp:

(JSC::CodeBlock::~CodeBlock):
(JSC::CodeBlock::linkIncomingPolymorphicCall):
(JSC::CodeBlock::unlinkIncomingCalls):
(JSC::CodeBlock::noticeIncomingCall):

• bytecode/CodeBlock.h:

(JSC::CodeBlock::isIncomingCallAlreadyLinked): Deleted.

• dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::addCallWithoutSettingResult):
(JSC::DFG::ByteCodeParser::handleCall):
(JSC::DFG::ByteCodeParser::handleInlining):

• dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

• dfg/DFGConstantFoldingPhase.cpp:

(JSC::DFG::ConstantFoldingPhase::foldConstants):

• dfg/DFGDoesGC.cpp:

(JSC::DFG::doesGC):

• dfg/DFGDriver.cpp:

(JSC::DFG::compileImpl):

• dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):

• dfg/DFGNode.h:

(JSC::DFG::Node::hasHeapPrediction):

• dfg/DFGNodeType.h:
• dfg/DFGOperations.cpp:
• dfg/DFGPredictionPropagationPhase.cpp:

(JSC::DFG::PredictionPropagationPhase::propagate):

• dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

• dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::emitCall):
(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::emitCall):
(JSC::DFG::SpeculativeJIT::compile):

• dfg/DFGTierUpCheckInjectionPhase.cpp:

(JSC::DFG::TierUpCheckInjectionPhase::run):
(JSC::DFG::TierUpCheckInjectionPhase::removeFTLProfiling): Deleted.

• ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

• heap/Heap.cpp:

(JSC::Heap::collect):

• jit/BinarySwitch.h:
• jit/ClosureCallStubRoutine.cpp: Removed.
• jit/ClosureCallStubRoutine.h: Removed.
• jit/JITCall.cpp:

(JSC::JIT::compileOpCall):

• jit/JITCall32_64.cpp:

(JSC::JIT::compileOpCall):

• jit/JITOperations.cpp:
• jit/JITOperations.h:

(JSC::operationLinkPolymorphicCallFor):
(JSC::operationLinkClosureCallFor): Deleted.

• jit/JITStubRoutine.h:
• jit/JITWriteBarrier.h:
• jit/PolymorphicCallStubRoutine.cpp: Added.

(JSC::PolymorphicCallNode::~PolymorphicCallNode):
(JSC::PolymorphicCallNode::unlink):
(JSC::PolymorphicCallCase::dump):
(JSC::PolymorphicCallStubRoutine::PolymorphicCallStubRoutine):
(JSC::PolymorphicCallStubRoutine::~PolymorphicCallStubRoutine):
(JSC::PolymorphicCallStubRoutine::variants):
(JSC::PolymorphicCallStubRoutine::edges):
(JSC::PolymorphicCallStubRoutine::visitWeak):
(JSC::PolymorphicCallStubRoutine::markRequiredObjectsInternal):

• jit/PolymorphicCallStubRoutine.h: Added.

(JSC::PolymorphicCallNode::PolymorphicCallNode):
(JSC::PolymorphicCallCase::PolymorphicCallCase):
(JSC::PolymorphicCallCase::variant):
(JSC::PolymorphicCallCase::codeBlock):

• jit/Repatch.cpp:

(JSC::linkSlowFor):
(JSC::linkFor):
(JSC::revertCall):
(JSC::unlinkFor):
(JSC::linkVirtualFor):
(JSC::linkPolymorphicCall):
(JSC::linkClosureCall): Deleted.

• jit/Repatch.h:
• jit/ThunkGenerators.cpp:

(JSC::linkPolymorphicCallForThunkGenerator):
(JSC::linkPolymorphicCallThunkGenerator):
(JSC::linkPolymorphicCallThatPreservesRegsThunkGenerator):
(JSC::linkClosureCallForThunkGenerator): Deleted.
(JSC::linkClosureCallThunkGenerator): Deleted.
(JSC::linkClosureCallThatPreservesRegsThunkGenerator): Deleted.

• jit/ThunkGenerators.h:

(JSC::linkPolymorphicCallThunkGeneratorFor):
(JSC::linkClosureCallThunkGeneratorFor): Deleted.

• llint/LLIntSlowPaths.cpp:

(JSC::LLInt::jitCompileAndSetHeuristics):

• runtime/Options.h:
• runtime/VM.cpp:

(JSC::VM::prepareToDiscardCode):
(JSC::VM::ensureCallEdgeLog): Deleted.

• runtime/VM.h:

File:

• trunk/Source/JavaScriptCore/jit/Repatch.cpp (modified) (8 diffs)

trunk/Source/JavaScriptCore/jit/Repatch.cpp

@@ -30 +30 @@
 
 #include "AccessorCallJITStubRoutine.h"
+#include "BinarySwitch.h"
 #include "CCallHelpers.h"
 #include "DFGOperations.h"
@@ -1576 +1577 @@
 
 static void linkSlowFor(
+    RepatchBuffer& repatchBuffer, VM* vm, CallLinkInfo& callLinkInfo, ThunkGenerator generator)
+{
+    repatchBuffer.relink(
+        callLinkInfo.callReturnLocation, vm->getCTIStub(generator).code());
+}
+
+static void linkSlowFor(
     RepatchBuffer& repatchBuffer, VM* vm, CallLinkInfo& callLinkInfo,
     CodeSpecializationKind kind, RegisterPreservationMode registers)
 {
-    repatchBuffer.relink(
-        callLinkInfo.callReturnLocation,
-        vm->getCTIStub(virtualThunkGeneratorFor(kind, registers)).code());
+    linkSlowFor(repatchBuffer, vm, callLinkInfo, virtualThunkGeneratorFor(kind, registers));
 }
 
@@ -1593 +1599 @@
     CodeBlock* callerCodeBlock = exec->callerFrame()->codeBlock();
 
-    // If you're being call-linked from a DFG caller then you obviously didn't get inlined.
-    if (calleeCodeBlock && JITCode::isOptimizingJIT(callerCodeBlock->jitType()))
-        calleeCodeBlock->m_shouldAlwaysBeInlined = false;
-    
     VM* vm = callerCodeBlock->vm();
     
@@ -1612 +1614 @@
     
     if (kind == CodeForCall) {
-        repatchBuffer.relink(callLinkInfo.callReturnLocation, vm->getCTIStub(linkClosureCallThunkGeneratorFor(registers)).code());
+        linkSlowFor(
+            repatchBuffer, vm, callLinkInfo, linkPolymorphicCallThunkGeneratorFor(registers));
         return;
     }
@@ -1632 +1635 @@
 }
 
-void linkClosureCall(
-    ExecState* exec, CallLinkInfo& callLinkInfo, CodeBlock* calleeCodeBlock, 
-    ExecutableBase* executable, MacroAssemblerCodePtr codePtr,
-    RegisterPreservationMode registers)
-{
-    ASSERT(!callLinkInfo.stub);
+static void revertCall(
+    RepatchBuffer& repatchBuffer, VM* vm, CallLinkInfo& callLinkInfo, ThunkGenerator generator)
+{
+    repatchBuffer.revertJumpReplacementToBranchPtrWithPatch(
+        RepatchBuffer::startOfBranchPtrWithPatchOnRegister(callLinkInfo.hotPathBegin),
+        static_cast<MacroAssembler::RegisterID>(callLinkInfo.calleeGPR), 0);
+    linkSlowFor(repatchBuffer, vm, callLinkInfo, generator);
+    callLinkInfo.hasSeenShouldRepatch = false;
+    callLinkInfo.callee.clear();
+    callLinkInfo.stub.clear();
+    if (callLinkInfo.isOnList())
+        callLinkInfo.remove();
+}
+
+void unlinkFor(
+    RepatchBuffer& repatchBuffer, CallLinkInfo& callLinkInfo,
+    CodeSpecializationKind kind, RegisterPreservationMode registers)
+{
+    if (Options::showDisassembly())
+        dataLog("Unlinking call from ", callLinkInfo.callReturnLocation, " in request from ", pointerDump(repatchBuffer.codeBlock()), "\n");
+    
+    revertCall(
+        repatchBuffer, repatchBuffer.codeBlock()->vm(), callLinkInfo,
+        linkThunkGeneratorFor(kind, registers));
+}
+
+void linkVirtualFor(
+    ExecState* exec, CallLinkInfo& callLinkInfo,
+    CodeSpecializationKind kind, RegisterPreservationMode registers)
+{
+    // FIXME: We could generate a virtual call stub here. This would lead to faster virtual calls
+    // by eliminating the branch prediction bottleneck inside the shared virtual call thunk.
     
     CodeBlock* callerCodeBlock = exec->callerFrame()->codeBlock();
     VM* vm = callerCodeBlock->vm();
+    
+    if (shouldShowDisassemblyFor(callerCodeBlock))
+        dataLog("Linking virtual call at ", *callerCodeBlock, " ", exec->callerFrame()->codeOrigin(), "\n");
+    
+    RepatchBuffer repatchBuffer(callerCodeBlock);
+    revertCall(repatchBuffer, vm, callLinkInfo, virtualThunkGeneratorFor(kind, registers));
+}
+
+namespace {
+struct CallToCodePtr {
+    CCallHelpers::Call call;
+    MacroAssemblerCodePtr codePtr;
+};
+} // annonymous namespace
+
+void linkPolymorphicCall(
+    ExecState* exec, CallLinkInfo& callLinkInfo, CallVariant newVariant,
+    RegisterPreservationMode registers)
+{
+    // Currently we can't do anything for non-function callees.
+    // https://bugs.webkit.org/show_bug.cgi?id=140685
+    if (!newVariant || !newVariant.executable()) {
+        linkVirtualFor(exec, callLinkInfo, CodeForCall, registers);
+        return;
+    }
+    
+    CodeBlock* callerCodeBlock = exec->callerFrame()->codeBlock();
+    VM* vm = callerCodeBlock->vm();
+    
+    CallVariantList list;
+    if (PolymorphicCallStubRoutine* stub = callLinkInfo.stub.get())
+        list = stub->variants();
+    else if (JSFunction* oldCallee = callLinkInfo.callee.get())
+        list = CallVariantList{ CallVariant(oldCallee) };
+    
+    list = variantListWithVariant(list, newVariant);
+
+    // If there are any closure calls then it makes sense to treat all of them as closure calls.
+    // This makes switching on callee cheaper. It also produces profiling that's easier on the DFG;
+    // the DFG doesn't really want to deal with a combination of closure and non-closure callees.
+    bool isClosureCall = false;
+    for (CallVariant variant : list)  {
+        if (variant.isClosureCall()) {
+            list = despecifiedVariantList(list);
+            isClosureCall = true;
+            break;
+        }
+    }
+    
+    Vector<PolymorphicCallCase> callCases;
+    
+    // Figure out what our cases are.
+    for (CallVariant variant : list) {
+        CodeBlock* codeBlock;
+        if (variant.executable()->isHostFunction())
+            codeBlock = nullptr;
+        else {
+            codeBlock = jsCast<FunctionExecutable*>(variant.executable())->codeBlockForCall();
+            
+            // If we cannot handle a callee, assume that it's better for this whole thing to be a
+            // virtual call.
+            if (exec->argumentCountIncludingThis() < static_cast<size_t>(codeBlock->numParameters()) || callLinkInfo.callType == CallLinkInfo::CallVarargs || callLinkInfo.callType == CallLinkInfo::ConstructVarargs) {
+                linkVirtualFor(exec, callLinkInfo, CodeForCall, registers);
+                return;
+            }
+        }
+        
+        callCases.append(PolymorphicCallCase(variant, codeBlock));
+    }
+    
+    // If we are over the limit, just use a normal virtual call.
+    unsigned maxPolymorphicCallVariantListSize;
+    if (callerCodeBlock->jitType() == JITCode::topTierJIT())
+        maxPolymorphicCallVariantListSize = Options::maxPolymorphicCallVariantListSizeForTopTier();
+    else
+        maxPolymorphicCallVariantListSize = Options::maxPolymorphicCallVariantListSize();
+    if (list.size() > maxPolymorphicCallVariantListSize) {
+        linkVirtualFor(exec, callLinkInfo, CodeForCall, registers);
+        return;
+    }
     
     GPRReg calleeGPR = static_cast<GPRReg>(callLinkInfo.calleeGPR);
@@ -1656 +1765 @@
         okArgumentCount.link(&stubJit);
     }
+    
+    GPRReg scratch = AssemblyHelpers::selectScratchGPR(calleeGPR);
+    GPRReg comparisonValueGPR;
+    
+    if (isClosureCall) {
+        // Verify that we have a function and stash the executable in scratch.
 
 #if USE(JSVALUE64)
-    // We can safely clobber everything except the calleeGPR. We can't rely on tagMaskRegister
-    // being set. So we do this the hard way.
-    GPRReg scratch = AssemblyHelpers::selectScratchGPR(calleeGPR);
-    stubJit.move(MacroAssembler::TrustedImm64(TagMask), scratch);
-    slowPath.append(stubJit.branchTest64(CCallHelpers::NonZero, calleeGPR, scratch));
+        // We can safely clobber everything except the calleeGPR. We can't rely on tagMaskRegister
+        // being set. So we do this the hard way.
+        stubJit.move(MacroAssembler::TrustedImm64(TagMask), scratch);
+        slowPath.append(stubJit.branchTest64(CCallHelpers::NonZero, calleeGPR, scratch));
 #else
-    // We would have already checked that the callee is a cell.
-#endif
-    
-    slowPath.append(
-        stubJit.branch8(
-            CCallHelpers::NotEqual,
-            CCallHelpers::Address(calleeGPR, JSCell::typeInfoTypeOffset()),
-            CCallHelpers::TrustedImm32(JSFunctionType)));
-    
-    slowPath.append(
-        stubJit.branchPtr(
-            CCallHelpers::NotEqual,
+        // We would have already checked that the callee is a cell.
+#endif
+    
+        slowPath.append(
+            stubJit.branch8(
+                CCallHelpers::NotEqual,
+                CCallHelpers::Address(calleeGPR, JSCell::typeInfoTypeOffset()),
+                CCallHelpers::TrustedImm32(JSFunctionType)));
+    
+        stubJit.loadPtr(
             CCallHelpers::Address(calleeGPR, JSFunction::offsetOfExecutable()),
-            CCallHelpers::TrustedImmPtr(executable)));
-    
-    AssemblyHelpers::Call call = stubJit.nearCall();
-    AssemblyHelpers::Jump done = stubJit.jump();
+            scratch);
+        
+        comparisonValueGPR = scratch;
+    } else
+        comparisonValueGPR = calleeGPR;
+    
+    Vector<int64_t> caseValues(callCases.size());
+    Vector<CallToCodePtr> calls(callCases.size());
+    std::unique_ptr<uint32_t[]> fastCounts;
+    
+    if (callerCodeBlock->jitType() != JITCode::topTierJIT())
+        fastCounts = std::make_unique<uint32_t[]>(callCases.size());
+    
+    for (size_t i = callCases.size(); i--;) {
+        if (fastCounts)
+            fastCounts[i] = 0;
+        
+        CallVariant variant = callCases[i].variant();
+        if (isClosureCall)
+            caseValues[i] = bitwise_cast<intptr_t>(variant.executable());
+        else
+            caseValues[i] = bitwise_cast<intptr_t>(variant.function());
+    }
+    
+    GPRReg fastCountsBaseGPR =
+        AssemblyHelpers::selectScratchGPR(calleeGPR, comparisonValueGPR, GPRInfo::regT3);
+    stubJit.move(CCallHelpers::TrustedImmPtr(fastCounts.get()), fastCountsBaseGPR);
+    
+    BinarySwitch binarySwitch(comparisonValueGPR, caseValues, BinarySwitch::IntPtr);
+    CCallHelpers::JumpList done;
+    while (binarySwitch.advance(stubJit)) {
+        size_t caseIndex = binarySwitch.caseIndex();
+        
+        CallVariant variant = callCases[caseIndex].variant();
+        
+        ASSERT(variant.executable()->hasJITCodeForCall());
+        MacroAssemblerCodePtr codePtr =
+            variant.executable()->generatedJITCodeForCall()->addressForCall(
+                *vm, variant.executable(), ArityCheckNotRequired, registers);
+        
+        if (fastCounts) {
+            stubJit.add32(
+                CCallHelpers::TrustedImm32(1),
+                CCallHelpers::Address(fastCountsBaseGPR, caseIndex * sizeof(uint32_t)));
+        }
+        calls[caseIndex].call = stubJit.nearCall();
+        calls[caseIndex].codePtr = codePtr;
+        done.append(stubJit.jump());
+    }
     
     slowPath.link(&stubJit);
+    binarySwitch.fallThrough().link(&stubJit);
     stubJit.move(calleeGPR, GPRInfo::regT0);
 #if USE(JSVALUE32_64)
@@ -1692 +1850 @@
     stubJit.restoreReturnAddressBeforeReturn(GPRInfo::regT4);
     AssemblyHelpers::Jump slow = stubJit.jump();
-    
+        
     LinkBuffer patchBuffer(*vm, stubJit, callerCodeBlock);
     
-    patchBuffer.link(call, FunctionPtr(codePtr.executableAddress()));
+    RELEASE_ASSERT(callCases.size() == calls.size());
+    for (CallToCodePtr callToCodePtr : calls) {
+        patchBuffer.link(
+            callToCodePtr.call, FunctionPtr(callToCodePtr.codePtr.executableAddress()));
+    }
     if (JITCode::isOptimizingJIT(callerCodeBlock->jitType()))
         patchBuffer.link(done, callLinkInfo.callReturnLocation.labelAtOffset(0));
     else
         patchBuffer.link(done, callLinkInfo.hotPathOther.labelAtOffset(0));
-    patchBuffer.link(slow, CodeLocationLabel(vm->getCTIStub(virtualThunkGeneratorFor(CodeForCall, registers)).code()));
-    
-    RefPtr<ClosureCallStubRoutine> stubRoutine = adoptRef(new ClosureCallStubRoutine(
+    patchBuffer.link(slow, CodeLocationLabel(vm->getCTIStub(linkPolymorphicCallThunkGeneratorFor(registers)).code()));
+    
+    RefPtr<PolymorphicCallStubRoutine> stubRoutine = adoptRef(new PolymorphicCallStubRoutine(
         FINALIZE_CODE_FOR(
             callerCodeBlock, patchBuffer,
-            ("Closure call stub for %s, return point %p, target %p (%s)",
+            ("Polymorphic call stub for %s, return point %p, targets %s",
                 toCString(*callerCodeBlock).data(), callLinkInfo.callReturnLocation.labelAtOffset(0).executableAddress(),
-                codePtr.executableAddress(), toCString(pointerDump(calleeCodeBlock)).data())),
-        *vm, callerCodeBlock->ownerExecutable(), executable));
+                toCString(listDump(callCases)).data())),
+        *vm, callerCodeBlock->ownerExecutable(), exec->callerFrame(), callLinkInfo, callCases,
+        WTF::move(fastCounts)));
     
     RepatchBuffer repatchBuffer(callerCodeBlock);
@@ -1715 +1878 @@
         RepatchBuffer::startOfBranchPtrWithPatchOnRegister(callLinkInfo.hotPathBegin),
         CodeLocationLabel(stubRoutine->code().code()));
+    // This is weird. The original slow path should no longer be reachable.
     linkSlowFor(repatchBuffer, vm, callLinkInfo, CodeForCall, registers);
     
+    // If there had been a previous stub routine, that one will die as soon as the GC runs and sees
+    // that it's no longer on stack.
     callLinkInfo.stub = stubRoutine.release();
     
-    ASSERT(!calleeCodeBlock || calleeCodeBlock->isIncomingCallAlreadyLinked(&callLinkInfo));
+    // The call link info no longer has a call cache apart from the jump to the polymorphic call
+    // stub.
+    if (callLinkInfo.isOnList())
+        callLinkInfo.remove();
 }