[JSC] When entering a CheckTierUp without OSREntry, force the CheckTierUp for the...
authorbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 May 2015 20:45:34 +0000 (20:45 +0000)
committerbenjamin@webkit.org <benjamin@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 18 May 2015 20:45:34 +0000 (20:45 +0000)
https://bugs.webkit.org/show_bug.cgi?id=145092

Reviewed by Filip Pizlo.

When we have a hot loop without OSR Entry inside a slower loop that support OSR Entry,
we get the inside loop driving the tierUpCounter and we have very little chance of
doing a CheckTierUp on the outer loop. In turn, this give almost no opportunity to tier
up in the outer loop and OSR Enter there.

This patches changes CheckTierUp to force its outer loops to do a CheckTierUp themselves.

To do that, CheckTierUp sets a flag "nestedTriggerIsSet" to force the outer loop to
enter their CheckTierUp regardless of the tier-up counter.

* bytecode/ExecutionCounter.cpp:
(JSC::ExecutionCounter<countingVariant>::setThreshold):
This is somewhat unrelated. This assertion is incorrect because it relies on
m_counter, which changes on an other thread.

I have hit it a couple of times with this patch because we are a bit more aggressive
on CheckTierUp. What happens is:
1) ExecutionCounter<countingVariant>::checkIfThresholdCrossedAndSet() first checks
   hasCrossedThreshold(), and it is false.
2) On the main thread, the hot loops keeps running and the counter becomes large
   enough to cross the threshold.
3) ExecutionCounter<countingVariant>::checkIfThresholdCrossedAndSet() runs the next
   test, setThreshold(), where the assertion is. Since the counter is now large enough,
   the assertion fails.

* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):

* dfg/DFGJITCode.h:
I used a uint8_t instead of a boolean to make the code generation clearer
in DFGSpeculativeJIT64.

* dfg/DFGNodeType.h:
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:

* dfg/DFGPredictionPropagationPhase.cpp:
(JSC::DFG::PredictionPropagationPhase::propagate):
This is a bit annoying: we have the NaturalLoops analysis that provides us
everything we need to know about loops, but the TierUpCheck are conservative
and set on LoopHint.

To make the two work together, we first find all the CheckTierUp that cannot
OSR enter and we keep a list of all the natural loops containing them.

Then we do a second pass over the LoopHints, get their NaturalLoop, and check
if it contains a loop that cannot OSR enter.

* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGTierUpCheckInjectionPhase.cpp:
(JSC::DFG::TierUpCheckInjectionPhase::run):
(JSC::DFG::TierUpCheckInjectionPhase::canOSREnterAtLoopHint):

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

15 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/bytecode/ExecutionCounter.cpp
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGJITCode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp

index 7778ba0..cad5266 100644 (file)
@@ -1,3 +1,74 @@
+2015-05-18  Benjamin Poulain  <benjamin@webkit.org>
+
+        [JSC] When entering a CheckTierUp without OSREntry, force the CheckTierUp for the outer loops with OSR Entry
+        https://bugs.webkit.org/show_bug.cgi?id=145092
+
+        Reviewed by Filip Pizlo.
+
+        When we have a hot loop without OSR Entry inside a slower loop that support OSR Entry,
+        we get the inside loop driving the tierUpCounter and we have very little chance of
+        doing a CheckTierUp on the outer loop. In turn, this give almost no opportunity to tier
+        up in the outer loop and OSR Enter there.
+
+        This patches changes CheckTierUp to force its outer loops to do a CheckTierUp themselves.
+
+        To do that, CheckTierUp sets a flag "nestedTriggerIsSet" to force the outer loop to
+        enter their CheckTierUp regardless of the tier-up counter.
+
+        * bytecode/ExecutionCounter.cpp:
+        (JSC::ExecutionCounter<countingVariant>::setThreshold):
+        This is somewhat unrelated. This assertion is incorrect because it relies on
+        m_counter, which changes on an other thread.
+
+        I have hit it a couple of times with this patch because we are a bit more aggressive
+        on CheckTierUp. What happens is:
+        1) ExecutionCounter<countingVariant>::checkIfThresholdCrossedAndSet() first checks
+           hasCrossedThreshold(), and it is false.
+        2) On the main thread, the hot loops keeps running and the counter becomes large
+           enough to cross the threshold.
+        3) ExecutionCounter<countingVariant>::checkIfThresholdCrossedAndSet() runs the next
+           test, setThreshold(), where the assertion is. Since the counter is now large enough,
+           the assertion fails.
+
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+
+        * dfg/DFGJITCode.h:
+        I used a uint8_t instead of a boolean to make the code generation clearer
+        in DFGSpeculativeJIT64.
+
+        * dfg/DFGNodeType.h:
+        * dfg/DFGOperations.cpp:
+        * dfg/DFGOperations.h:
+
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        (JSC::DFG::PredictionPropagationPhase::propagate):
+        This is a bit annoying: we have the NaturalLoops analysis that provides us
+        everything we need to know about loops, but the TierUpCheck are conservative
+        and set on LoopHint.
+
+        To make the two work together, we first find all the CheckTierUp that cannot
+        OSR enter and we keep a list of all the natural loops containing them.
+
+        Then we do a second pass over the LoopHints, get their NaturalLoop, and check
+        if it contains a loop that cannot OSR enter.
+
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGTierUpCheckInjectionPhase.cpp:
+        (JSC::DFG::TierUpCheckInjectionPhase::run):
+        (JSC::DFG::TierUpCheckInjectionPhase::canOSREnterAtLoopHint):
+
 2015-05-18  Filip Pizlo  <fpizlo@apple.com>
 
         Add a Int-or-Boolean speculation to Branch
index bacb49e..fe4e430 100644 (file)
@@ -136,8 +136,6 @@ bool ExecutionCounter<countingVariant>::setThreshold(CodeBlock* codeBlock)
         return false;
     }
         
-    ASSERT(!m_activeThreshold || !hasCrossedThreshold(codeBlock));
-        
     // Compute the true total count.
     double trueTotalCount = count();
     
index 311db83..22a9bb2 100644 (file)
@@ -2271,6 +2271,7 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
     }
 
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
     case LoopHint:
     case ZombieHint:
         break;
index b478eba..7a25506 100644 (file)
@@ -286,6 +286,7 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
     case LoopHint:
     case Breakpoint:
     case ProfileWillCall:
index 1237817..5946840 100644 (file)
@@ -159,6 +159,7 @@ bool doesGC(Graph& graph, Node* node)
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
     case LoopHint:
     case StoreBarrier:
     case InvalidationPoint:
index ecdeb7b..021f146 100644 (file)
@@ -1084,6 +1084,7 @@ private:
         case CheckTierUpInLoop:
         case CheckTierUpAtReturn:
         case CheckTierUpAndOSREnter:
+        case CheckTierUpWithNestedTriggerAndOSREnter:
         case InvalidationPoint:
         case CheckArray:
         case CheckInBounds:
index 4d3136f..945f55e 100644 (file)
@@ -120,6 +120,7 @@ public:
     DFG::VariableEventStream variableEventStream;
     DFG::MinifiedGraph minifiedDFG;
 #if ENABLE(FTL_JIT)
+    uint8_t nestedTriggerIsSet { 0 };
     UpperTierExecutionCounter tierUpCounter;
     RefPtr<CodeBlock> osrEntryBlock;
     unsigned osrEntryRetry;
index 725629e..69f6ae5 100644 (file)
@@ -91,6 +91,7 @@ namespace JSC { namespace DFG {
     /* Tier-up checks from the DFG to the FTL. */\
     macro(CheckTierUpInLoop, NodeMustGenerate) \
     macro(CheckTierUpAndOSREnter, NodeMustGenerate) \
+    macro(CheckTierUpWithNestedTriggerAndOSREnter, NodeMustGenerate) \
     macro(CheckTierUpAtReturn, NodeMustGenerate) \
     \
     /* Get the value of a local variable, without linking into the VariableAccessData */\
index 8bb2d8d..cf3a34b 100644 (file)
@@ -1351,7 +1351,7 @@ static void triggerFTLReplacementCompile(VM* vm, CodeBlock* codeBlock, JITCode*
         Operands<JSValue>(), ToFTLDeferredCompilationCallback::create(codeBlock));
 }
 
-void JIT_OPERATION triggerTierUpNow(ExecState* exec)
+static void triggerTierUpNowCommon(ExecState* exec, bool inLoop)
 {
     VM* vm = &exec->vm();
     NativeCallFrameTracer tracer(vm, exec);
@@ -1370,10 +1370,22 @@ void JIT_OPERATION triggerTierUpNow(ExecState* exec)
             *codeBlock, ": Entered triggerTierUpNow with executeCounter = ",
             jitCode->tierUpCounter, "\n");
     }
-    
+    if (inLoop)
+        jitCode->nestedTriggerIsSet = 1;
+
     triggerFTLReplacementCompile(vm, codeBlock, jitCode);
 }
 
+void JIT_OPERATION triggerTierUpNow(ExecState* exec)
+{
+    triggerTierUpNowCommon(exec, false);
+}
+
+void JIT_OPERATION triggerTierUpNowInLoop(ExecState* exec)
+{
+    triggerTierUpNowCommon(exec, true);
+}
+
 char* JIT_OPERATION triggerOSREntryNow(
     ExecState* exec, int32_t bytecodeIndex, int32_t streamIndex)
 {
@@ -1388,6 +1400,7 @@ char* JIT_OPERATION triggerOSREntryNow(
     }
     
     JITCode* jitCode = codeBlock->jitCode()->dfg();
+    jitCode->nestedTriggerIsSet = 0;
     
     if (Options::verboseOSR()) {
         dataLog(
index b966c8d..c102b87 100644 (file)
@@ -148,6 +148,7 @@ void JIT_OPERATION triggerReoptimizationNow(CodeBlock*, OSRExitBase*) WTF_INTERN
 
 #if ENABLE(FTL_JIT)
 void JIT_OPERATION triggerTierUpNow(ExecState*) WTF_INTERNAL;
+void JIT_OPERATION triggerTierUpNowInLoop(ExecState*) WTF_INTERNAL;
 char* JIT_OPERATION triggerOSREntryNow(ExecState*, int32_t bytecodeIndex, int32_t streamIndex) WTF_INTERNAL;
 #endif // ENABLE(FTL_JIT)
 
index 666626a..3df8812 100644 (file)
@@ -540,6 +540,7 @@ private:
         case CheckTierUpInLoop:
         case CheckTierUpAtReturn:
         case CheckTierUpAndOSREnter:
+        case CheckTierUpWithNestedTriggerAndOSREnter:
         case InvalidationPoint:
         case CheckInBounds:
         case ValueToInt32:
index 075b3df..a57ed2a 100644 (file)
@@ -246,6 +246,7 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
     case LoopHint:
     case StoreBarrier:
     case InvalidationPoint:
index 7f58f88..93b45fa 100644 (file)
@@ -4610,6 +4610,7 @@ void SpeculativeJIT::compile(Node* node)
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
     case Int52Rep:
     case FiatInt52:
     case Int52Constant:
index 3eb0cc9..55dca75 100644 (file)
@@ -4635,7 +4635,7 @@ void SpeculativeJIT::compile(Node* node)
         
         silentSpillAllRegisters(InvalidGPRReg);
         m_jit.setupArgumentsExecState();
-        appendCall(triggerTierUpNow);
+        appendCall(triggerTierUpNowInLoop);
         silentFillAllRegisters(InvalidGPRReg);
         
         done.link(&m_jit);
@@ -4657,17 +4657,24 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
         
-    case CheckTierUpAndOSREnter: {
+    case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter: {
         ASSERT(!node->origin.semantic.inlineCallFrame);
         
         GPRTemporary temp(this);
         GPRReg tempGPR = temp.gpr();
+
+        MacroAssembler::Jump forceOSREntry;
+        if (op == CheckTierUpWithNestedTriggerAndOSREnter)
+            forceOSREntry = m_jit.branchTest8(MacroAssembler::NonZero, MacroAssembler::AbsoluteAddress(&m_jit.jitCode()->nestedTriggerIsSet));
         
         MacroAssembler::Jump done = m_jit.branchAdd32(
             MacroAssembler::Signed,
             TrustedImm32(Options::ftlTierUpCounterIncrementForLoop()),
             MacroAssembler::AbsoluteAddress(&m_jit.jitCode()->tierUpCounter.m_counter));
-        
+
+        if (forceOSREntry.isSet())
+            forceOSREntry.link(&m_jit);
         silentSpillAllRegisters(tempGPR);
         m_jit.setupArgumentsWithExecState(
             TrustedImm32(node->origin.semantic.bytecodeIndex),
@@ -4685,6 +4692,7 @@ void SpeculativeJIT::compile(Node* node)
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
+    case CheckTierUpWithNestedTriggerAndOSREnter:
         DFG_CRASH(m_jit.graph(), node, "Unexpected tier-up node");
         break;
 #endif // ENABLE(FTL_JIT)
index c2533ef..5f509c4 100644 (file)
@@ -60,6 +60,13 @@ public:
         
         if (!Options::enableOSREntryToFTL())
             level = FTL::CanCompile;
+
+        // First we find all the loops that contain a LoopHint for which we cannot OSR enter.
+        // We use that information to decide if we need CheckTierUpAndOSREnter or CheckTierUpWithNestedTriggerAndOSREnter.
+        NaturalLoops& naturalLoops = m_graph.m_naturalLoops;
+        naturalLoops.computeIfNecessary(m_graph);
+
+        HashSet<const NaturalLoop*> loopsContainingLoopHintWithoutOSREnter = findLoopsContainingLoopHintWithoutOSREnter(naturalLoops, level);
         
         InsertionSet insertionSet(m_graph);
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
@@ -71,35 +78,16 @@ public:
                 Node* node = block->at(nodeIndex);
                 if (node->op() != LoopHint)
                     continue;
-                
-                // We only put OSR checks for the first LoopHint in the block. Note that
-                // more than one LoopHint could happen in cases where we did a lot of CFG
-                // simplification in the bytecode parser, but it should be very rare.
-                
+
                 NodeOrigin origin = node->origin;
-                
-                if (level != FTL::CanCompileAndOSREnter || origin.semantic.inlineCallFrame) {
-                    insertionSet.insertNode(
-                        nodeIndex + 1, SpecNone, CheckTierUpInLoop, origin);
-                    break;
-                }
-                
-                bool isAtTop = true;
-                for (unsigned subNodeIndex = nodeIndex; subNodeIndex--;) {
-                    if (!block->at(subNodeIndex)->isSemanticallySkippable()) {
-                        isAtTop = false;
-                        break;
-                    }
-                }
-                
-                if (!isAtTop) {
-                    insertionSet.insertNode(
-                        nodeIndex + 1, SpecNone, CheckTierUpInLoop, origin);
-                    break;
-                }
-                
-                insertionSet.insertNode(
-                    nodeIndex + 1, SpecNone, CheckTierUpAndOSREnter, origin);
+                if (canOSREnterAtLoopHint(level, block, nodeIndex)) {
+                    const NaturalLoop* loop = naturalLoops.innerMostLoopOf(block);
+                    if (loop && loopsContainingLoopHintWithoutOSREnter.contains(loop))
+                        insertionSet.insertNode(nodeIndex + 1, SpecNone, CheckTierUpWithNestedTriggerAndOSREnter, origin);
+                    else
+                        insertionSet.insertNode(nodeIndex + 1, SpecNone, CheckTierUpAndOSREnter, origin);
+                } else
+                    insertionSet.insertNode(nodeIndex + 1, SpecNone, CheckTierUpInLoop, origin);
                 break;
             }
             
@@ -119,6 +107,49 @@ public:
         return false;
 #endif // ENABLE(FTL_JIT)
     }
+
+private:
+#if ENABLE(FTL_JIT)
+    bool canOSREnterAtLoopHint(FTL::CapabilityLevel level, const BasicBlock* block, unsigned nodeIndex)
+    {
+        Node* node = block->at(nodeIndex);
+        ASSERT(node->op() == LoopHint);
+
+        NodeOrigin origin = node->origin;
+        if (level != FTL::CanCompileAndOSREnter || origin.semantic.inlineCallFrame)
+            return false;
+
+        // We only put OSR checks for the first LoopHint in the block. Note that
+        // more than one LoopHint could happen in cases where we did a lot of CFG
+        // simplification in the bytecode parser, but it should be very rare.
+        for (unsigned subNodeIndex = nodeIndex; subNodeIndex--;) {
+            if (!block->at(subNodeIndex)->isSemanticallySkippable())
+                return false;
+        }
+        return true;
+    }
+
+    HashSet<const NaturalLoop*> findLoopsContainingLoopHintWithoutOSREnter(const NaturalLoops& naturalLoops, FTL::CapabilityLevel level)
+    {
+        HashSet<const NaturalLoop*> loopsContainingLoopHintWithoutOSREnter;
+        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+                if (node->op() != LoopHint)
+                    continue;
+
+                if (!canOSREnterAtLoopHint(level, block, nodeIndex)) {
+                    const NaturalLoop* loop = naturalLoops.innerMostLoopOf(block);
+                    while (loop) {
+                        loopsContainingLoopHintWithoutOSREnter.add(loop);
+                        loop = naturalLoops.innerMostOuterLoop(*loop);
+                    }
+                }
+            }
+        }
+        return loopsContainingLoopHintWithoutOSREnter;
+    }
+#endif
 };
 
 bool performTierUpCheckInjection(Graph& graph)