Changeset 179478 in webkit for trunk/Source/JavaScriptCore/bytecode/CallLinkStatus.cpp

Timestamp:

Feb 2, 2015, 10:38:08 AM (11 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.

Rolling this back in after fixing ​https://bugs.webkit.org/show_bug.cgi?id=141107.

• 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/bytecode/CallLinkStatus.cpp (modified) (8 diffs)

trunk/Source/JavaScriptCore/bytecode/CallLinkStatus.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2012, 2013, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -48 +48 @@
     }
     
-    m_edges.append(CallEdge(CallVariant(value.asCell()), 1));
+    m_variants.append(CallVariant(value.asCell()));
 }
 
@@ -130 +130 @@
     UNUSED_PARAM(profiledBlock);
     
-    if (Options::callStatusShouldUseCallEdgeProfile()) {
-        // Always trust the call edge profile over anything else since this has precise counts.
-        // It can make the best possible decision because it never "forgets" what happened for any
-        // call, with the exception of fading out the counts of old calls (for example if the
-        // counter type is 16-bit then calls that happened more than 2^16 calls ago are given half
-        // weight, and this compounds for every 2^15 [sic] calls after that). The combination of
-        // high fidelity for recent calls and fading for older calls makes this the most useful
-        // mechamism of choosing how to optimize future calls.
-        CallEdgeProfile* edgeProfile = callLinkInfo.callEdgeProfile.get();
-        WTF::loadLoadFence();
-        if (edgeProfile) {
-            CallLinkStatus result = computeFromCallEdgeProfile(edgeProfile);
-            if (!!result)
-                return result;
-        }
-    }
-    
     return computeFromCallLinkInfo(locker, callLinkInfo);
 }
@@ -166 +149 @@
     // is probably OK for now.
     
+    // PolymorphicCallStubRoutine is a GCAwareJITStubRoutine, so if non-null, it will stay alive
+    // until next GC even if the CallLinkInfo is concurrently cleared. Also, the variants list is
+    // never mutated after the PolymorphicCallStubRoutine is instantiated. We have some conservative
+    // fencing in place to make sure that we see the variants list after construction.
+    if (PolymorphicCallStubRoutine* stub = callLinkInfo.stub.get()) {
+        WTF::loadLoadFence();
+        
+        CallEdgeList edges = stub->edges();
+        
+        // Now that we've loaded the edges list, there are no further concurrency concerns. We will
+        // just manipulate and prune this list to our liking - mostly removing entries that are too
+        // infrequent and ensuring that it's sorted in descending order of frequency.
+        
+        RELEASE_ASSERT(edges.size());
+        
+        std::sort(
+            edges.begin(), edges.end(),
+            [] (CallEdge a, CallEdge b) {
+                return a.count() > b.count();
+            });
+        RELEASE_ASSERT(edges.first().count() >= edges.last().count());
+        
+        double totalCallsToKnown = 0;
+        double totalCallsToUnknown = callLinkInfo.slowPathCount;
+        CallVariantList variants;
+        for (size_t i = 0; i < edges.size(); ++i) {
+            CallEdge edge = edges[i];
+            // If the call is at the tail of the distribution, then we don't optimize it and we
+            // treat it as if it was a call to something unknown. We define the tail as being either
+            // a call that doesn't belong to the N most frequent callees (N =
+            // maxPolymorphicCallVariantsForInlining) or that has a total call count that is too
+            // small.
+            if (i >= Options::maxPolymorphicCallVariantsForInlining()
+                || edge.count() < Options::frequentCallThreshold())
+                totalCallsToUnknown += edge.count();
+            else {
+                totalCallsToKnown += edge.count();
+                variants.append(edge.callee());
+            }
+        }
+        
+        // Bail if we didn't find any calls that qualified.
+        RELEASE_ASSERT(!!totalCallsToKnown == !!variants.size());
+        if (variants.isEmpty())
+            return takesSlowPath();
+        
+        // We require that the distribution of callees is skewed towards a handful of common ones.
+        if (totalCallsToKnown / totalCallsToUnknown < Options::minimumCallToKnownRate())
+            return takesSlowPath();
+        
+        RELEASE_ASSERT(totalCallsToKnown);
+        RELEASE_ASSERT(variants.size());
+        
+        CallLinkStatus result;
+        result.m_variants = variants;
+        result.m_couldTakeSlowPath = !!totalCallsToUnknown;
+        return result;
+    }
+    
     if (callLinkInfo.slowPathCount >= Options::couldTakeSlowCaseMinimumCount())
         return takesSlowPath();
-    
-    if (ClosureCallStubRoutine* stub = callLinkInfo.stub.get())
-        return CallLinkStatus(stub->executable());
     
     JSFunction* target = callLinkInfo.lastSeenCallee.get();
@@ -180 +219 @@
 
     return CallLinkStatus(target);
-}
-
-CallLinkStatus CallLinkStatus::computeFromCallEdgeProfile(CallEdgeProfile* edgeProfile)
-{
-    // In cases where the call edge profile saw nothing, use the CallLinkInfo instead.
-    if (!edgeProfile->totalCalls())
-        return CallLinkStatus();
-    
-    // To do anything meaningful, we require that the majority of calls are to something we
-    // know how to handle.
-    unsigned numCallsToKnown = edgeProfile->numCallsToKnownCells();
-    unsigned numCallsToUnknown = edgeProfile->numCallsToNotCell() + edgeProfile->numCallsToUnknownCell();
-    
-    // We require that the majority of calls were to something that we could possibly inline.
-    if (numCallsToKnown <= numCallsToUnknown)
-        return takesSlowPath();
-    
-    // We require that the number of such calls is greater than some minimal threshold, so that we
-    // avoid inlining completely cold calls.
-    if (numCallsToKnown < Options::frequentCallThreshold())
-        return takesSlowPath();
-    
-    CallLinkStatus result;
-    result.m_edges = edgeProfile->callEdges();
-    result.m_couldTakeSlowPath = !!numCallsToUnknown;
-    result.m_canTrustCounts = true;
-    
-    return result;
 }
 
@@ -283 +294 @@
 bool CallLinkStatus::isClosureCall() const
 {
-    for (unsigned i = m_edges.size(); i--;) {
-        if (m_edges[i].callee().isClosureCall())
+    for (unsigned i = m_variants.size(); i--;) {
+        if (m_variants[i].isClosureCall())
             return true;
     }
@@ -292 +303 @@
 void CallLinkStatus::makeClosureCall()
 {
-    ASSERT(!m_isProved);
-    for (unsigned i = m_edges.size(); i--;)
-        m_edges[i] = m_edges[i].despecifiedClosure();
-    
-    if (!ASSERT_DISABLED) {
-        // Doing this should not have created duplicates, because the CallEdgeProfile
-        // should despecify closures if doing so would reduce the number of known callees.
-        for (unsigned i = 0; i < m_edges.size(); ++i) {
-            for (unsigned j = i + 1; j < m_edges.size(); ++j)
-                ASSERT(m_edges[i].callee() != m_edges[j].callee());
-        }
-    }
+    m_variants = despecifiedVariantList(m_variants);
 }
 
@@ -321 +321 @@
         out.print(comma, "Could Take Slow Path");
     
-    out.print(listDump(m_edges));
+    if (!m_variants.isEmpty())
+        out.print(comma, listDump(m_variants));
 }