Make DFG to FTL OSR entry code more sane by removing bad RELEASE_ASSERTS and making...
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 7 Jun 2018 08:44:59 +0000 (08:44 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 7 Jun 2018 08:44:59 +0000 (08:44 +0000)
https://bugs.webkit.org/show_bug.cgi?id=186218
<rdar://problem/38449540>

Reviewed by Filip Pizlo.

JSTests:

* stress/dont-crash-ftl-osr-entry.js: Added.

Source/JavaScriptCore:

This patch makes tierUpCommon a tad bit more sane. There are a few things
that I did:
- There were a few release asserts that were crashing. Those release asserts
were incorrect. They were making assumptions about how the code and data
structures were ordered that were wrong. This patch removes them. The code
was using the loop hierarchy vector to make assumptions about which loop we
were currently executing in, which is incorrect. The only information that
can be used about where we're currently executing is the bytecode index we're
at.
- This makes it so that we go back to trying to compile outer loops before
inner loops. JF accidentally reverted this behavior that Ben implemented.
JF made it so that we just compiled the inner most loop. I make this
functionality work by first triggering a compile for the outer most loop
that the code is currently executing in and that can perform OSR entry.
However, some programs can get stuck in inner loops. The code works by
progressively asking inner loops to compile if program execution has not
yet reached an outer loop.

* dfg/DFGOperations.cpp:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@232578 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JSTests/ChangeLog
JSTests/stress/dont-crash-ftl-osr-entry.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGOperations.cpp

index 2179069..64119c9 100644 (file)
@@ -1,3 +1,13 @@
+2018-06-07  Saam Barati  <sbarati@apple.com>
+
+        Make DFG to FTL OSR entry code more sane by removing bad RELEASE_ASSERTS and making it trigger compiles in outer loops before inner ones
+        https://bugs.webkit.org/show_bug.cgi?id=186218
+        <rdar://problem/38449540>
+
+        Reviewed by Filip Pizlo.
+
+        * stress/dont-crash-ftl-osr-entry.js: Added.
+
 2018-06-06  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [DFG] Compare operations do not respect negative zeros
diff --git a/JSTests/stress/dont-crash-ftl-osr-entry.js b/JSTests/stress/dont-crash-ftl-osr-entry.js
new file mode 100644 (file)
index 0000000..50b29c8
--- /dev/null
@@ -0,0 +1,26 @@
+//@ runDefault("--jitPolicyScale=0--jitPolicyScale=0")
+
+// This test should not crash.
+
+function f_0() {
+    var v_4 = 1;
+    var v_5 = 'a';
+    while (v_4 < 256) {
+        v_4 <<= 1;
+    }
+    return v_4;
+}
+function f_1(v_1) {
+    var sum = 0;
+    for (var i = 0; i < 1000; i++) {
+        for (var j = 0; j < 4; j++) {
+            sum += v_1();
+        }
+    }
+    return sum;
+}
+
+let hello;
+for (var i=0; i<1000; i++) {
+    hello = f_1(f_0);
+}
index 80a6089..eb38071 100644 (file)
@@ -1,3 +1,31 @@
+2018-06-07  Saam Barati  <sbarati@apple.com>
+
+        Make DFG to FTL OSR entry code more sane by removing bad RELEASE_ASSERTS and making it trigger compiles in outer loops before inner ones
+        https://bugs.webkit.org/show_bug.cgi?id=186218
+        <rdar://problem/38449540>
+
+        Reviewed by Filip Pizlo.
+
+        This patch makes tierUpCommon a tad bit more sane. There are a few things
+        that I did:
+        - There were a few release asserts that were crashing. Those release asserts
+        were incorrect. They were making assumptions about how the code and data
+        structures were ordered that were wrong. This patch removes them. The code
+        was using the loop hierarchy vector to make assumptions about which loop we
+        were currently executing in, which is incorrect. The only information that
+        can be used about where we're currently executing is the bytecode index we're
+        at.
+        - This makes it so that we go back to trying to compile outer loops before
+        inner loops. JF accidentally reverted this behavior that Ben implemented.
+        JF made it so that we just compiled the inner most loop. I make this
+        functionality work by first triggering a compile for the outer most loop
+        that the code is currently executing in and that can perform OSR entry.
+        However, some programs can get stuck in inner loops. The code works by
+        progressively asking inner loops to compile if program execution has not
+        yet reached an outer loop.
+
+        * dfg/DFGOperations.cpp:
+
 2018-06-06  Guillaume Emont  <guijemont@igalia.com>
 
         ArityFixup should adjust SP first on 32-bit platforms too
index 26de111..7c9e70b 100644 (file)
@@ -3018,7 +3018,7 @@ void JIT_OPERATION triggerTierUpNow(ExecState* exec)
     }
 }
 
-static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigned osrEntryBytecodeIndex)
+static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, bool canOSREnterHere)
 {
     VM* vm = &exec->vm();
     CodeBlock* codeBlock = exec->codeBlock();
@@ -3032,10 +3032,6 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
         worklistState = Worklist::NotKnown;
 
     JITCode* jitCode = codeBlock->jitCode()->dfg();
-
-    // The following is only true for triggerTierUpNowInLoop, which can never
-    // be an OSR entry.
-    bool canOSRFromHere = originBytecodeIndex == osrEntryBytecodeIndex;
     
     bool triggeredSlowPathToStartCompilation = false;
     auto tierUpEntryTriggers = jitCode->tierUpEntryTriggers.find(originBytecodeIndex);
@@ -3048,15 +3044,13 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
 
         case JITCode::TriggerReason::CompilationDone:
             // The trigger was set because compilation completed. Don't unset it
-            // so that further DFG executions OSR enters as well.
-            RELEASE_ASSERT(canOSRFromHere);
+            // so that further DFG executions OSR enter as well.
             break;
 
         case JITCode::TriggerReason::StartCompilation:
             // We were asked to enter as soon as possible and start compiling an
             // entry for the current bytecode location. Unset this trigger so we
             // don't continually enter.
-            RELEASE_ASSERT(canOSRFromHere);
             tierUpEntryTriggers->value = JITCode::TriggerReason::DontTrigger;
             triggeredSlowPathToStartCompilation = true;
             break;
@@ -3065,11 +3059,26 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
 
     if (worklistState == Worklist::Compiling) {
         CODEBLOCK_LOG_EVENT(codeBlock, "delayFTLCompile", ("still compiling"));
-        jitCode->setOptimizationThresholdBasedOnCompilationResult(
-            codeBlock, CompilationDeferred);
+        jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
         return nullptr;
     }
 
+    // If we can OSR Enter, do it right away.
+    if (canOSREnterHere) {
+        auto iter = jitCode->bytecodeIndexToStreamIndex.find(originBytecodeIndex);
+        if (iter != jitCode->bytecodeIndexToStreamIndex.end()) {
+            unsigned streamIndex = iter->value;
+            if (CodeBlock* entryBlock = jitCode->osrEntryBlock()) {
+                if (Options::verboseOSR())
+                    dataLog("OSR entry: From ", RawPointer(jitCode), " got entry block ", RawPointer(entryBlock), "\n");
+                if (void* address = FTL::prepareOSREntry(exec, codeBlock, entryBlock, originBytecodeIndex, streamIndex)) {
+                    CODEBLOCK_LOG_EVENT(entryBlock, "osrEntry", ("at bc#", originBytecodeIndex));
+                    return retagCodePtr<char*>(address, JSEntryPtrTag, bitwise_cast<PtrTag>(exec));
+                }
+            }
+        }
+    }
+
     if (worklistState == Worklist::Compiled) {
         CODEBLOCK_LOG_EVENT(codeBlock, "delayFTLCompile", ("compiled and failed"));
         // This means that compilation failed and we already set the thresholds.
@@ -3078,19 +3087,6 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
         return nullptr;
     }
 
-    // If we can OSR Enter, do it right away.
-    if (canOSRFromHere) {
-        unsigned streamIndex = jitCode->bytecodeIndexToStreamIndex.get(originBytecodeIndex);
-        if (CodeBlock* entryBlock = jitCode->osrEntryBlock()) {
-            if (Options::verboseOSR())
-                dataLog("OSR entry: From ", RawPointer(jitCode), " got entry block ", RawPointer(entryBlock), "\n");
-            if (void* address = FTL::prepareOSREntry(exec, codeBlock, entryBlock, originBytecodeIndex, streamIndex)) {
-                CODEBLOCK_LOG_EVENT(entryBlock, "osrEntry", ("at bc#", originBytecodeIndex));
-                return retagCodePtr<char*>(address, JSEntryPtrTag, bitwise_cast<PtrTag>(exec));
-            }
-        }
-    }
-
     // - If we don't have an FTL code block, then try to compile one.
     // - If we do have an FTL code block, then try to enter for a while.
     // - If we couldn't enter for a while, then trigger OSR entry.
@@ -3112,7 +3108,6 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
     } else
         CODEBLOCK_LOG_EVENT(codeBlock, "delayFTLCompile", ("avoiding replacement compile"));
 
-    // It's time to try to compile code for OSR entry.
     if (CodeBlock* entryBlock = jitCode->osrEntryBlock()) {
         if (jitCode->osrEntryRetry < Options::ftlOSREntryRetryThreshold()) {
             CODEBLOCK_LOG_EVENT(codeBlock, "delayFTLCompile", ("OSR entry failed, OSR entry threshold not met"));
@@ -3144,48 +3139,80 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
         return nullptr;
     }
 
-    if (!canOSRFromHere) {
-        // We can't OSR from here, or even start a compilation because doing so
-        // calls jitCode->reconstruct which would get the wrong state.
-        if (Options::verboseOSR())
-            dataLog("Non-OSR-able bc#", originBytecodeIndex, " in ", *codeBlock, " setting parent loop bc#", osrEntryBytecodeIndex, "'s trigger and backing off.\n");
-        jitCode->tierUpEntryTriggers.set(osrEntryBytecodeIndex, JITCode::TriggerReason::StartCompilation);
-        jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
-        return nullptr;
-    }
-
-    unsigned streamIndex = jitCode->bytecodeIndexToStreamIndex.get(osrEntryBytecodeIndex);
+    // It's time to try to compile code for OSR entry.
 
     if (!triggeredSlowPathToStartCompilation) {
-        auto tierUpHierarchyEntry = jitCode->tierUpInLoopHierarchy.find(osrEntryBytecodeIndex);
-        if (tierUpHierarchyEntry != jitCode->tierUpInLoopHierarchy.end()) {
-            for (unsigned osrEntryCandidate : tierUpHierarchyEntry->value) {
-                if (jitCode->tierUpEntrySeen.contains(osrEntryCandidate)) {
-                    // Ask an enclosing loop to compile, instead of doing so here.
-                    if (Options::verboseOSR())
-                        dataLog("Inner-loop bc#", originBytecodeIndex, " in ", *codeBlock, " setting parent loop bc#", osrEntryCandidate, "'s trigger and backing off.\n");
-                    jitCode->tierUpEntryTriggers.set(osrEntryCandidate, JITCode::TriggerReason::StartCompilation);
-                    jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
-                    return nullptr;
+
+        // An inner loop didn't specifically ask for us to kick off a compilation. This means the counter
+        // crossed its threshold. We either fall through and kick off a compile for originBytecodeIndex,
+        // or we flag an outer loop to immediately try to compile itself. If there are outer loops,
+        // we first try to make them compile themselves. But we will eventually fall back to compiling
+        // a progressively inner loop if it takes too long for control to reach an outer loop.
+
+        auto tryTriggerOuterLoopToCompile = [&] {
+            auto tierUpHierarchyEntry = jitCode->tierUpInLoopHierarchy.find(originBytecodeIndex);
+            if (tierUpHierarchyEntry == jitCode->tierUpInLoopHierarchy.end())
+                return false;
+
+            // This vector is ordered from innermost to outermost loop. Every bytecode entry in this vector is
+            // allowed to do OSR entry. We start with the outermost loop and make our way inwards (hence why we
+            // iterate the vector in reverse). Our policy is that we will trigger an outer loop to compile
+            // immediately when program control reaches it. If program control is taking too long to reach that
+            // outer loop, we progressively move inwards, meaning, we'll eventually trigger some loop that is
+            // executing to compile. We start with trying to compile outer loops since we believe outer loop
+            // compilations reveal the best opportunities for optimizing code.
+            for (auto iter = tierUpHierarchyEntry->value.rbegin(), end = tierUpHierarchyEntry->value.rend(); iter != end; ++iter) {
+                unsigned osrEntryCandidate = *iter;
+
+                if (jitCode->tierUpEntryTriggers.get(osrEntryCandidate) == JITCode::TriggerReason::StartCompilation) {
+                    // This means that we already asked this loop to compile. If we've reached here, it
+                    // means program control has not yet reached that loop. So it's taking too long to compile.
+                    // So we move on to asking the inner loop of this loop to compile itself.
+                    continue;
                 }
+
+                // This is where we ask the outer to loop to immediately compile itself if program
+                // control reaches it.
+                if (Options::verboseOSR())
+                    dataLog("Inner-loop bc#", originBytecodeIndex, " in ", *codeBlock, " setting parent loop bc#", osrEntryCandidate, "'s trigger and backing off.\n");
+                jitCode->tierUpEntryTriggers.set(osrEntryCandidate, JITCode::TriggerReason::StartCompilation);
+                return true;
             }
+
+            return false;
+        };
+
+        if (tryTriggerOuterLoopToCompile()) {
+            jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
+            return nullptr;
         }
     }
 
+    if (!canOSREnterHere) {
+        jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
+        return nullptr;
+    }
+
     // We aren't compiling and haven't compiled anything for OSR entry. So, try to compile
     // something.
-    auto triggerIterator = jitCode->tierUpEntryTriggers.find(osrEntryBytecodeIndex);
-    RELEASE_ASSERT(triggerIterator != jitCode->tierUpEntryTriggers.end());
+
+    auto triggerIterator = jitCode->tierUpEntryTriggers.find(originBytecodeIndex);
+    if (triggerIterator == jitCode->tierUpEntryTriggers.end()) {
+        jitCode->setOptimizationThresholdBasedOnCompilationResult(codeBlock, CompilationDeferred);
+        return nullptr;
+    }
+
     JITCode::TriggerReason* triggerAddress = &(triggerIterator->value);
 
     Operands<JSValue> mustHandleValues;
+    unsigned streamIndex = jitCode->bytecodeIndexToStreamIndex.get(originBytecodeIndex);
     jitCode->reconstruct(
-        exec, codeBlock, CodeOrigin(osrEntryBytecodeIndex), streamIndex, mustHandleValues);
+        exec, codeBlock, CodeOrigin(originBytecodeIndex), streamIndex, mustHandleValues);
     CodeBlock* replacementCodeBlock = codeBlock->newReplacement();
 
     CODEBLOCK_LOG_EVENT(codeBlock, "triggerFTLOSR", ());
     CompilationResult forEntryResult = compile(
-        *vm, replacementCodeBlock, codeBlock, FTLForOSREntryMode, osrEntryBytecodeIndex,
+        *vm, replacementCodeBlock, codeBlock, FTLForOSREntryMode, originBytecodeIndex,
         mustHandleValues, ToFTLForOSREntryDeferredCompilationCallback::create(triggerAddress));
 
     if (jitCode->neverExecutedEntry)
@@ -3204,6 +3231,7 @@ static char* tierUpCommon(ExecState* exec, unsigned originBytecodeIndex, unsigne
     // We signal to try again after a while if that happens.
     if (Options::verboseOSR())
         dataLog("Immediate OSR entry: From ", RawPointer(jitCode), " got entry block ", RawPointer(jitCode->osrEntryBlock()), "\n");
+
     void* address = FTL::prepareOSREntry(
         exec, codeBlock, jitCode->osrEntryBlock(), originBytecodeIndex, streamIndex);
     if (!address)
@@ -3221,7 +3249,7 @@ void JIT_OPERATION triggerTierUpNowInLoop(ExecState* exec, unsigned bytecodeInde
     sanitizeStackForVM(vm);
 
     if (codeBlock->jitType() != JITCode::DFGJIT) {
-        dataLog("Unexpected code block in DFG->FTL tier-up: ", *codeBlock, "\n");
+        dataLog("Unexpected code block in DFG->FTL trigger tier up now in loop: ", *codeBlock, "\n");
         RELEASE_ASSERT_NOT_REACHED();
     }
 
@@ -3233,11 +3261,9 @@ void JIT_OPERATION triggerTierUpNowInLoop(ExecState* exec, unsigned bytecodeInde
             jitCode->tierUpCounter, "\n");
     }
 
-    auto tierUpHierarchyEntry = jitCode->tierUpInLoopHierarchy.find(bytecodeIndex);
-    if (tierUpHierarchyEntry != jitCode->tierUpInLoopHierarchy.end()
-        && !tierUpHierarchyEntry->value.isEmpty()) {
-        tierUpCommon(exec, bytecodeIndex, tierUpHierarchyEntry->value.first());
-    } else if (shouldTriggerFTLCompile(codeBlock, jitCode))
+    if (jitCode->tierUpInLoopHierarchy.contains(bytecodeIndex))
+        tierUpCommon(exec, bytecodeIndex, false);
+    else if (shouldTriggerFTLCompile(codeBlock, jitCode))
         triggerFTLReplacementCompile(vm, codeBlock, jitCode);
 
     // Since we cannot OSR Enter here, the default "optimizeSoon()" is not useful.
@@ -3270,7 +3296,7 @@ char* JIT_OPERATION triggerOSREntryNow(ExecState* exec, unsigned bytecodeIndex)
             jitCode->tierUpCounter, "\n");
     }
 
-    return tierUpCommon(exec, bytecodeIndex, bytecodeIndex);
+    return tierUpCommon(exec, bytecodeIndex, true);
 }
 
 #endif // ENABLE(FTL_JIT)