Changeset 155023 in webkit for trunk/Source/JavaScriptCore/dfg/DFGOperations.cpp

Timestamp:

Sep 3, 2013, 11:26:04 PM (12 years ago)

Author:

[email protected]

Message:

The DFG should be able to tier-up and OSR enter into the FTL
​https://bugs.webkit.org/show_bug.cgi?id=112838

Source/JavaScriptCore:

Reviewed by Mark Hahnenberg.

This adds the ability for the DFG to tier-up into the FTL. This works in both
of the expected tier-up modes:

Replacement: frequently called functions eventually have their entrypoint
replaced with one that goes into FTL-compiled code. Note, this will be a
slow-down for now since we don't yet have LLVM calling convention integration.

OSR entry: code stuck in hot loops gets OSR'd into the FTL from the DFG.

This means that if the DFG detects that a function is an FTL candidate, it
inserts execution counting code similar to the kind that the baseline JIT
would use. If you trip on a loop count in a loop header that is an OSR
candidate (it's not an inlined loop), we do OSR; otherwise we do replacement.
OSR almost always also implies future replacement.

OSR entry into the FTL is really cool. It uses a specialized FTL compile of
the code, where early in the DFG pipeline we replace the original root block
with an OSR entrypoint block that jumps to the pre-header of the hot loop.
The OSR entrypoint loads all live state at the loop pre-header using loads
from a scratch buffer, which gets populated by the runtime's OSR entry
preparation code (FTL::prepareOSREntry()). This approach appears to work well
with all of our subsequent optimizations, including prediction propagation,
CFA, and LICM. LLVM seems happy with it, too. Best of all, it works naturally
with concurrent compilation: when we hit the tier-up trigger we spawn a
compilation plan at the bytecode index from which we triggered; once the
compilation finishes the next trigger will try to enter, at that bytecode
index. If it can't - for example because the code has moved on to another
loop - then we just try again. Loops that get hot enough for OSR entry (about
25,000 iterations) will probably still be running when a concurrent compile
finishes, so this doesn't appear to be a big problem.

This immediately gives us a 70% speed-up on imaging-gaussian-blur. We could
get a bigger speed-up by adding some more intelligence and tweaking LLVM to
compile code faster. Those things will happen eventually but this is a good
start. Probably this code will see more tuning as we get more coverage in the
FTL JIT, but I'll worry about that in future patches.

• CMakeLists.txt:
• GNUmakefile.list.am:
• JavaScriptCore.xcodeproj/project.pbxproj:
• Target.pri:
• bytecode/CodeBlock.cpp:

(JSC::CodeBlock::CodeBlock):
(JSC::CodeBlock::hasOptimizedReplacement):
(JSC::CodeBlock::setOptimizationThresholdBasedOnCompilationResult):

• bytecode/CodeBlock.h:
• dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::::executeEffects):

• dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::parse):

• dfg/DFGCFGSimplificationPhase.cpp:

(JSC::DFG::CFGSimplificationPhase::run):

• dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

• dfg/DFGDriver.cpp:

(JSC::DFG::compileImpl):
(JSC::DFG::compile):

• dfg/DFGDriver.h:
• dfg/DFGFixupPhase.cpp:

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

• dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::killBlockAndItsContents):
(JSC::DFG::Graph::killUnreachableBlocks):

• dfg/DFGGraph.h:
• dfg/DFGInPlaceAbstractState.cpp:

(JSC::DFG::InPlaceAbstractState::initialize):

• dfg/DFGJITCode.cpp:

(JSC::DFG::JITCode::reconstruct):
(JSC::DFG::JITCode::checkIfOptimizationThresholdReached):
(JSC::DFG::JITCode::optimizeNextInvocation):
(JSC::DFG::JITCode::dontOptimizeAnytimeSoon):
(JSC::DFG::JITCode::optimizeAfterWarmUp):
(JSC::DFG::JITCode::optimizeSoon):
(JSC::DFG::JITCode::forceOptimizationSlowPathConcurrently):
(JSC::DFG::JITCode::setOptimizationThresholdBasedOnCompilationResult):

• dfg/DFGJITCode.h:
• dfg/DFGJITFinalizer.cpp:

(JSC::DFG::JITFinalizer::finalize):
(JSC::DFG::JITFinalizer::finalizeFunction):
(JSC::DFG::JITFinalizer::finalizeCommon):

• dfg/DFGLoopPreHeaderCreationPhase.cpp:

(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):

• dfg/DFGLoopPreHeaderCreationPhase.h:
• dfg/DFGNode.h:

(JSC::DFG::Node::hasUnlinkedLocal):
(JSC::DFG::Node::unlinkedLocal):

• dfg/DFGNodeType.h:
• dfg/DFGOSREntry.cpp:

(JSC::DFG::prepareOSREntry):

• dfg/DFGOSREntrypointCreationPhase.cpp: Added.

(JSC::DFG::OSREntrypointCreationPhase::OSREntrypointCreationPhase):
(JSC::DFG::OSREntrypointCreationPhase::run):
(JSC::DFG::performOSREntrypointCreation):

• dfg/DFGOSREntrypointCreationPhase.h: Added.
• dfg/DFGOperations.cpp:
• dfg/DFGOperations.h:
• dfg/DFGPlan.cpp:

(JSC::DFG::Plan::Plan):
(JSC::DFG::Plan::compileInThread):
(JSC::DFG::Plan::compileInThreadImpl):

• dfg/DFGPlan.h:
• dfg/DFGPredictionInjectionPhase.cpp:

(JSC::DFG::PredictionInjectionPhase::run):

• dfg/DFGPredictionPropagationPhase.cpp:

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

• dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

• dfg/DFGSpeculativeJIT32_64.cpp:

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

• dfg/DFGSpeculativeJIT64.cpp:

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

• dfg/DFGTierUpCheckInjectionPhase.cpp: Added.

(JSC::DFG::TierUpCheckInjectionPhase::TierUpCheckInjectionPhase):
(JSC::DFG::TierUpCheckInjectionPhase::run):
(JSC::DFG::performTierUpCheckInjection):

• dfg/DFGTierUpCheckInjectionPhase.h: Added.
• dfg/DFGToFTLDeferredCompilationCallback.cpp: Added.

(JSC::DFG::ToFTLDeferredCompilationCallback::ToFTLDeferredCompilationCallback):
(JSC::DFG::ToFTLDeferredCompilationCallback::~ToFTLDeferredCompilationCallback):
(JSC::DFG::ToFTLDeferredCompilationCallback::create):
(JSC::DFG::ToFTLDeferredCompilationCallback::compilationDidBecomeReadyAsynchronously):
(JSC::DFG::ToFTLDeferredCompilationCallback::compilationDidComplete):

• dfg/DFGToFTLDeferredCompilationCallback.h: Added.
• dfg/DFGToFTLForOSREntryDeferredCompilationCallback.cpp: Added.

(JSC::DFG::ToFTLForOSREntryDeferredCompilationCallback::ToFTLForOSREntryDeferredCompilationCallback):
(JSC::DFG::ToFTLForOSREntryDeferredCompilationCallback::~ToFTLForOSREntryDeferredCompilationCallback):
(JSC::DFG::ToFTLForOSREntryDeferredCompilationCallback::create):
(JSC::DFG::ToFTLForOSREntryDeferredCompilationCallback::compilationDidBecomeReadyAsynchronously):
(JSC::DFG::ToFTLForOSREntryDeferredCompilationCallback::compilationDidComplete):

• dfg/DFGToFTLForOSREntryDeferredCompilationCallback.h: Added.
• dfg/DFGWorklist.cpp:

(JSC::DFG::globalWorklist):

• dfg/DFGWorklist.h:
• ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

• ftl/FTLCapabilities.h:
• ftl/FTLForOSREntryJITCode.cpp: Added.

(JSC::FTL::ForOSREntryJITCode::ForOSREntryJITCode):
(JSC::FTL::ForOSREntryJITCode::~ForOSREntryJITCode):
(JSC::FTL::ForOSREntryJITCode::ftlForOSREntry):
(JSC::FTL::ForOSREntryJITCode::initializeEntryBuffer):

• ftl/FTLForOSREntryJITCode.h: Added.

(JSC::FTL::ForOSREntryJITCode::entryBuffer):
(JSC::FTL::ForOSREntryJITCode::setBytecodeIndex):
(JSC::FTL::ForOSREntryJITCode::bytecodeIndex):
(JSC::FTL::ForOSREntryJITCode::countEntryFailure):
(JSC::FTL::ForOSREntryJITCode::entryFailureCount):

• ftl/FTLJITFinalizer.cpp:

(JSC::FTL::JITFinalizer::finalizeFunction):

• ftl/FTLLink.cpp:

(JSC::FTL::link):

• ftl/FTLLowerDFGToLLVM.cpp:

(JSC::FTL::LowerDFGToLLVM::compileBlock):
(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::compileExtractOSREntryLocal):
(JSC::FTL::LowerDFGToLLVM::compileGetLocal):
(JSC::FTL::LowerDFGToLLVM::addWeakReference):

• ftl/FTLOSREntry.cpp: Added.

(JSC::FTL::prepareOSREntry):

• ftl/FTLOSREntry.h: Added.
• ftl/FTLOutput.h:

(JSC::FTL::Output::crashNonTerminal):
(JSC::FTL::Output::crash):

• ftl/FTLState.cpp:

(JSC::FTL::State::State):

• interpreter/Register.h:

(JSC::Register::unboxedDouble):

• jit/JIT.cpp:

(JSC::JIT::emitEnterOptimizationCheck):

• jit/JITCode.cpp:

(JSC::JITCode::ftlForOSREntry):

• jit/JITCode.h:
• jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

• runtime/Executable.cpp:

(JSC::ScriptExecutable::newReplacementCodeBlockFor):

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

(JSC::VM::ensureWorklist):

• runtime/VM.h:

LayoutTests:

Reviewed by Mark Hahnenberg.

Fix marsaglia to check the result instead of printing, and add a second
version that relies on OSR entry.

• fast/js/regress/marsaglia-osr-entry-expected.txt: Added.
• fast/js/regress/marsaglia-osr-entry.html: Added.
• fast/js/regress/script-tests/marsaglia-osr-entry.js: Added.

(marsaglia):

• fast/js/regress/script-tests/marsaglia.js:

File:

• trunk/Source/JavaScriptCore/dfg/DFGOperations.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/dfg/DFGOperations.cpp

@@ -32 +32 @@
 #include "CommonSlowPaths.h"
 #include "CopiedSpaceInlines.h"
+#include "DFGDriver.h"
 #include "DFGOSRExit.h"
 #include "DFGRepatch.h"
 #include "DFGThunks.h"
+#include "DFGToFTLDeferredCompilationCallback.h"
+#include "DFGToFTLForOSREntryDeferredCompilationCallback.h"
+#include "DFGWorklist.h"
+#include "FTLForOSREntryJITCode.h"
+#include "FTLOSREntry.h"
 #include "HostCallReturnValue.h"
 #include "GetterSetter.h"
@@ -2015 +2021 @@
     codeBlock->reoptimize();
 }
+
+#if ENABLE(FTL_JIT)
+void DFG_OPERATION triggerTierUpNow(ExecState* exec)
+{
+    VM* vm = &exec->vm();
+    NativeCallFrameTracer tracer(vm, exec);
+    DeferGC deferGC(vm->heap);
+    CodeBlock* codeBlock = exec->codeBlock();
+    
+    JITCode* jitCode = codeBlock->jitCode()->dfg();
+    
+    if (Options::verboseOSR()) {
+        dataLog(
+            *codeBlock, ": Entered triggerTierUpNow with executeCounter = ",
+            jitCode->tierUpCounter, "\n");
+    }
+    
+    if (codeBlock->baselineVersion()->m_didFailFTLCompilation) {
+        if (Options::verboseOSR())
+            dataLog("Deferring FTL-optimization of ", *codeBlock, " indefinitely because there was an FTL failure.\n");
+        jitCode->dontOptimizeAnytimeSoon(codeBlock);
+        return;
+    }
+    
+    if (!jitCode->checkIfOptimizationThresholdReached(codeBlock)) {
+        if (Options::verboseOSR())
+            dataLog("Choosing not to FTL-optimize ", *codeBlock, " yet.\n");
+        return;
+    }
+    
+    Worklist::State worklistState;
+    if (Worklist* worklist = vm->worklist.get()) {
+        worklistState = worklist->completeAllReadyPlansForVM(
+            *vm, CompilationKey(codeBlock->baselineVersion(), FTLMode));
+    } else
+        worklistState = Worklist::NotKnown;
+    
+    if (worklistState == Worklist::Compiling) {
+        jitCode->setOptimizationThresholdBasedOnCompilationResult(
+            codeBlock, CompilationDeferred);
+        return;
+    }
+    
+    if (codeBlock->hasOptimizedReplacement()) {
+        // That's great, we've compiled the code - next time we call this function,
+        // we'll enter that replacement.
+        jitCode->optimizeSoon(codeBlock);
+        return;
+    }
+    
+    if (worklistState == Worklist::Compiled) {
+        // This means that we finished compiling, but failed somehow; in that case the
+        // thresholds will be set appropriately.
+        if (Options::verboseOSR())
+            dataLog("Code block ", *codeBlock, " was compiled but it doesn't have an optimized replacement.\n");
+        return;
+    }
+
+    // We need to compile the code.
+    compile(
+        *vm, codeBlock->newReplacement().get(), FTLMode, UINT_MAX, Operands<JSValue>(),
+        ToFTLDeferredCompilationCallback::create(codeBlock), vm->ensureWorklist());
+}
+
+char* DFG_OPERATION triggerOSREntryNow(
+    ExecState* exec, int32_t bytecodeIndex, int32_t streamIndex)
+{
+    VM* vm = &exec->vm();
+    NativeCallFrameTracer tracer(vm, exec);
+    DeferGC deferGC(vm->heap);
+    CodeBlock* codeBlock = exec->codeBlock();
+    
+    JITCode* jitCode = codeBlock->jitCode()->dfg();
+    
+    if (Options::verboseOSR()) {
+        dataLog(
+            *codeBlock, ": Entered triggerTierUpNow with executeCounter = ",
+            jitCode->tierUpCounter, "\n");
+    }
+    
+    if (codeBlock->baselineVersion()->m_didFailFTLCompilation) {
+        if (Options::verboseOSR())
+            dataLog("Deferring FTL-optimization of ", *codeBlock, " indefinitely because there was an FTL failure.\n");
+        jitCode->dontOptimizeAnytimeSoon(codeBlock);
+        return 0;
+    }
+    
+    if (!jitCode->checkIfOptimizationThresholdReached(codeBlock)) {
+        if (Options::verboseOSR())
+            dataLog("Choosing not to FTL-optimize ", *codeBlock, " yet.\n");
+        return 0;
+    }
+    
+    Worklist::State worklistState;
+    if (Worklist* worklist = vm->worklist.get()) {
+        worklistState = worklist->completeAllReadyPlansForVM(
+            *vm, CompilationKey(codeBlock->baselineVersion(), FTLForOSREntryMode));
+    } else
+        worklistState = Worklist::NotKnown;
+    
+    if (worklistState == Worklist::Compiling) {
+        ASSERT(!jitCode->osrEntryBlock);
+        jitCode->setOptimizationThresholdBasedOnCompilationResult(
+            codeBlock, CompilationDeferred);
+        return 0;
+    }
+    
+    if (CodeBlock* entryBlock = jitCode->osrEntryBlock.get()) {
+        void* address = FTL::prepareOSREntry(
+            exec, codeBlock, entryBlock, bytecodeIndex, streamIndex);
+        if (address) {
+            jitCode->optimizeSoon(codeBlock);
+            return static_cast<char*>(address);
+        }
+        
+        FTL::ForOSREntryJITCode* entryCode = entryBlock->jitCode()->ftlForOSREntry();
+        entryCode->countEntryFailure();
+        if (entryCode->entryFailureCount() <
+            Options::ftlOSREntryFailureCountForReoptimization()) {
+            
+            jitCode->optimizeSoon(codeBlock);
+            return 0;
+        }
+        
+        // OSR entry failed. Oh no! This implies that we need to retry. We retry
+        // without exponential backoff and we only do this for the entry code block.
+        jitCode->osrEntryBlock.clear();
+        
+        jitCode->optimizeAfterWarmUp(codeBlock);
+        return 0;
+    }
+    
+    if (worklistState == Worklist::Compiled) {
+        // This means that compilation failed and we already set the thresholds.
+        if (Options::verboseOSR())
+            dataLog("Code block ", *codeBlock, " was compiled but it doesn't have an optimized replacement.\n");
+        return 0;
+    }
+
+    // The first order of business is to trigger a for-entry compile.
+    Operands<JSValue> mustHandleValues;
+    jitCode->reconstruct(
+        exec, codeBlock, CodeOrigin(bytecodeIndex), streamIndex, mustHandleValues);
+    CompilationResult forEntryResult = DFG::compile(
+        *vm, codeBlock->newReplacement().get(), FTLForOSREntryMode, bytecodeIndex,
+        mustHandleValues, ToFTLForOSREntryDeferredCompilationCallback::create(codeBlock),
+        vm->ensureWorklist());
+    
+    // But we also want to trigger a replacement compile. Of course, we don't want to
+    // trigger it if we don't need to. Note that this is kind of weird because we might
+    // have just finished an FTL compile and that compile failed or was invalidated.
+    // But this seems uncommon enough that we sort of don't care. It's certainly sound
+    // to fire off another compile right now so long as we're not already compiling and
+    // we don't already have an optimized replacement. Note, we don't do this for
+    // obviously bad cases like global code, where we know that there is a slim chance
+    // of this code being invoked ever again.
+    CompilationKey keyForReplacement(codeBlock->baselineVersion(), FTLMode);
+    if (codeBlock->codeType() != GlobalCode
+        && !codeBlock->hasOptimizedReplacement()
+        && (!vm->worklist.get()
+            || vm->worklist->compilationState(keyForReplacement) == Worklist::NotKnown)) {
+        compile(
+            *vm, codeBlock->newReplacement().get(), FTLMode, UINT_MAX, Operands<JSValue>(),
+            ToFTLDeferredCompilationCallback::create(codeBlock), vm->ensureWorklist());
+    }
+    
+    if (forEntryResult != CompilationSuccessful)
+        return 0;
+    
+    // It's possible that the for-entry compile already succeeded. In that case OSR
+    // entry will succeed unless we ran out of stack. It's not clear what we should do.
+    // We signal to try again after a while if that happens.
+    void* address = FTL::prepareOSREntry(
+        exec, codeBlock, jitCode->osrEntryBlock.get(), bytecodeIndex, streamIndex);
+    if (address)
+        jitCode->optimizeSoon(codeBlock);
+    else
+        jitCode->optimizeAfterWarmUp(codeBlock);
+    return static_cast<char*>(address);
+}
+#endif // ENABLE(FTL_JIT)
 
 } // extern "C"