Changeset 242990 in webkit

Timestamp:

Mar 14, 2019, 10:45:07 PM (7 years ago)

Author:

ysuzuki@apple.com

Message:

REGRESSION(r242841): Fix conservative DFG OSR entry validation to accept values which will be stored in AnyInt / Double flush formats
​https://bugs.webkit.org/show_bug.cgi?id=195752

Reviewed by Saam Barati.

We fixed the bug skipping AbstractValue validations when the flush format is Double or AnyInt. But it
was too conservative. While validating inputs with AbstractValue is mandatory (without it, whole CFA
falls into wrong condition), our validation does not care AnyInt and Double representations in lower
tiers. For example, if a value is stored in Double flush format in DFG, its AbstractValue becomes
SpecFullDouble. However, it does not include Int32 and OSR entry is rejected if Int32 comes for DoubleRep
OSR entry value. This is wrong since we later convert these numbers into DoubleRep representation
before entering DFG code.

This patch performs AbstractValue validation onto the correctly converted value with flush format hint.

And it still does not fix OSR entry failures in navier-stokes. This is because AbstractValue representation
in navier-stokes's lin_solve was too strict. Then, this patch reverts r242627. Instead of removing must handle
value handling in CFA, DFG OSR entry now correctly validates inputs with AbstractValues even if the flush format
is Double or AnyInt. As long as DFG OSR entry validates inputs, merging must handle values as proven constants is OK.

We can see that # of OSR entry failures in navier-stokes.js becomes the same to the previous count. And we can see
AnyInt OSR entry actually works in microbenchmarks/large-int.js. However, AnyInt effect is hard to observe because this
is super rare. Since we inject type prediction based on must handle value, the flush format tends to be SpecAnyIntAsDouble
and it accepts JSValues simply.

• bytecode/SpeculatedType.cpp:

(JSC::dumpSpeculation):

• dfg/DFGAbstractValue.cpp:

(JSC::DFG::AbstractValue::filterValueByType):

• dfg/DFGAbstractValue.h:

(JSC::DFG::AbstractValue::validateOSREntryValue const):
(JSC::DFG::AbstractValue::validateTypeAcceptingBoxedInt52 const):
(JSC::DFG::AbstractValue::validate const): Deleted.
(JSC::DFG::AbstractValue::validateType const): Deleted.

• dfg/DFGCFAPhase.cpp:

(JSC::DFG::CFAPhase::run):
(JSC::DFG::CFAPhase::injectOSR):
(JSC::DFG::CFAPhase::performBlockCFA):

• dfg/DFGOSREntry.cpp:

(JSC::DFG::prepareOSREntry):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• bytecode/SpeculatedType.cpp (modified) (1 diff)
• dfg/DFGAbstractValue.cpp (modified) (2 diffs)
• dfg/DFGAbstractValue.h (modified) (4 diffs)
• dfg/DFGCFAPhase.cpp (modified) (5 diffs)
• dfg/DFGOSREntry.cpp (modified) (8 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2019-03-14  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        REGRESSION(r242841): Fix conservative DFG OSR entry validation to accept values which will be stored in AnyInt / Double flush formats
+        https://bugs.webkit.org/show_bug.cgi?id=195752
+
+        Reviewed by Saam Barati.
+
+        We fixed the bug skipping AbstractValue validations when the flush format is Double or AnyInt. But it
+        was too conservative. While validating inputs with AbstractValue is mandatory (without it, whole CFA
+        falls into wrong condition), our validation does not care AnyInt and Double representations in lower
+        tiers. For example, if a value is stored in Double flush format in DFG, its AbstractValue becomes
+        SpecFullDouble. However, it does not include Int32 and OSR entry is rejected if Int32 comes for DoubleRep
+        OSR entry value. This is wrong since we later convert these numbers into DoubleRep representation
+        before entering DFG code.
+
+        This patch performs AbstractValue validation onto the correctly converted value with flush format hint.
+
+        And it still does not fix OSR entry failures in navier-stokes. This is because AbstractValue representation
+        in navier-stokes's lin_solve was too strict. Then, this patch reverts r242627. Instead of removing must handle
+        value handling in CFA, DFG OSR entry now correctly validates inputs with AbstractValues even if the flush format
+        is Double or AnyInt. As long as DFG OSR entry validates inputs, merging must handle values as proven constants is OK.
+
+        We can see that # of OSR entry failures in navier-stokes.js becomes the same to the previous count. And we can see
+        AnyInt OSR entry actually works in microbenchmarks/large-int.js. However, AnyInt effect is hard to observe because this
+        is super rare. Since we inject type prediction based on must handle value, the flush format tends to be SpecAnyIntAsDouble
+        and it accepts JSValues simply.
+
+        * bytecode/SpeculatedType.cpp:
+        (JSC::dumpSpeculation):
+        * dfg/DFGAbstractValue.cpp:
+        (JSC::DFG::AbstractValue::filterValueByType):
+        * dfg/DFGAbstractValue.h:
+        (JSC::DFG::AbstractValue::validateOSREntryValue const):
+        (JSC::DFG::AbstractValue::validateTypeAcceptingBoxedInt52 const):
+        (JSC::DFG::AbstractValue::validate const): Deleted.
+        (JSC::DFG::AbstractValue::validateType const): Deleted.
+        * dfg/DFGCFAPhase.cpp:
+        (JSC::DFG::CFAPhase::run):
+        (JSC::DFG::CFAPhase::injectOSR):
+        (JSC::DFG::CFAPhase::performBlockCFA):
+        * dfg/DFGOSREntry.cpp:
+        (JSC::DFG::prepareOSREntry):
+
 2019-03-14  Saam barati  <sbarati@apple.com>
 

trunk/Source/JavaScriptCore/bytecode/SpeculatedType.cpp

@@ -262 +262 @@
         
         if (value & SpecNonIntAsDouble)
-            strOut.print("NonIntAsdouble");
+            strOut.print("NonIntAsDouble");
         else
             isTop = false;

trunk/Source/JavaScriptCore/dfg/DFGAbstractValue.cpp

@@ -345 +345 @@
         // The type is still non-empty. It may be that the new type renders
         // the value empty because it contravenes the constant value we had.
-        if (m_value && !validateType(m_value))
+        if (m_value && !validateTypeAcceptingBoxedInt52(m_value))
             clear();
         return;
@@ -352 +352 @@
     // The type has been rendered empty. That means that the value must now be invalid,
     // as well.
-    ASSERT(!m_value || !validateType(m_value));
+    ASSERT(!m_value || !validateTypeAcceptingBoxedInt52(m_value));
     m_value = JSValue();
 }

trunk/Source/JavaScriptCore/dfg/DFGAbstractValue.h

@@ -31 +31 @@
 #include "DFGAbstractValueClobberEpoch.h"
 #include "DFGFiltrationResult.h"
+#include "DFGFlushFormat.h"
 #include "DFGFrozenValue.h"
 #include "DFGNodeFlags.h"
@@ -370 +371 @@
     bool contains(RegisteredStructure) const;
 
-    bool validate(JSValue value) const
+    bool validateOSREntryValue(JSValue value, FlushFormat format) const
     {
         if (isHeapTop())
@@ -378 +379 @@
             return false;
         
-        if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
-            return false;
-        
-        if (value.isEmpty()) {
-            ASSERT(m_type & SpecEmpty);
-            return true;
+        if (format == FlushedInt52) {
+            if (!validateTypeAcceptingBoxedInt52(value))
+                return false;
+        } else {
+            if (mergeSpeculations(m_type, speculationFromValue(value)) != m_type)
+                return false;
+            
+            if (value.isEmpty()) {
+                ASSERT(m_type & SpecEmpty);
+                return true;
+            }
         }
         
@@ -491 +497 @@
     }
     
-    bool validateType(JSValue value) const
+    bool validateTypeAcceptingBoxedInt52(JSValue value) const
     {
         if (isHeapTop())

trunk/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp

@@ -77 +77 @@
         m_state.initialize();
         
+        if (m_graph.m_form != SSA) {
+            if (m_verbose)
+                dataLog("   Widening state at OSR entry block.\n");
+            
+            // Widen the abstract values at the block that serves as the must-handle OSR entry.
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                
+                if (!block->isOSRTarget)
+                    continue;
+                if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
+                    continue;
+                
+                // We record that the block needs some OSR stuff, but we don't do that yet. We want to
+                // handle OSR entry data at the right time in order to get the best compile times. If we
+                // simply injected OSR data right now, then we'd potentially cause a loop body to be
+                // interpreted with just the constants we feed it, which is more expensive than if we
+                // interpreted it with non-constant values. If we always injected this data after the
+                // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
+                // after convergence. So, we try very hard to inject OSR data for a block when we first
+                // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
+                // way, we:
+                //
+                // - Reduce the likelihood of interpreting the block with constants, since we will inject
+                //   the OSR entry constants on top of whatever abstract values we got for that block on
+                //   the first pass. The mix of those two things is likely to not be constant.
+                //
+                // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
+                //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
+                //   to do a second fixpoint if we don't even reach the OSR entry block during the main
+                //   run of CFA, but in that case at least we're not being redundant.
+                m_blocksWithOSR.add(block);
+            }
+        }
+
         do {
             m_changed = false;
@@ -83 +120 @@
         
         if (m_graph.m_form != SSA) {
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                
+                if (m_blocksWithOSR.remove(block))
+                    m_changed |= injectOSR(block);
+            }
+            
+            while (m_changed) {
+                m_changed = false;
+                performForwardCFA();
+            }
+        
             // Make sure we record the intersection of all proofs that we ever allowed the
             // compiler to rely upon.
@@ -107 +158 @@
     
 private:
+    bool injectOSR(BasicBlock* block)
+    {
+        if (m_verbose)
+            dataLog("   Found must-handle block: ", *block, "\n");
+        
+        // This merges snapshot of stack values while CFA phase want to have proven types and values. This is somewhat tricky.
+        // But this is OK as long as DFG OSR entry validates the inputs with *proven* AbstracValue values. And it turns out that this
+        // type widening is critical to navier-stokes. Without it, navier-stokes has more strict constraint on OSR entry and
+        // fails OSR entry repeatedly.
+        bool changed = false;
+        const Operands<Optional<JSValue>>& mustHandleValues = m_graph.m_plan.mustHandleValues();
+        for (size_t i = mustHandleValues.size(); i--;) {
+            int operand = mustHandleValues.operandForIndex(i);
+            Optional<JSValue> value = mustHandleValues[i];
+            if (!value) {
+                if (m_verbose)
+                    dataLog("   Not live in bytecode: ", VirtualRegister(operand), "\n");
+                continue;
+            }
+            Node* node = block->variablesAtHead.operand(operand);
+            if (!node) {
+                if (m_verbose)
+                    dataLog("   Not live: ", VirtualRegister(operand), "\n");
+                continue;
+            }
+            
+            if (m_verbose)
+                dataLog("   Widening ", VirtualRegister(operand), " with ", value.value(), "\n");
+            
+            AbstractValue& target = block->valuesAtHead.operand(operand);
+            changed |= target.mergeOSREntryValue(m_graph, value.value());
+            target.fixTypeForRepresentation(
+                m_graph, resultFor(node->variableAccessData()->flushFormat()), node);
+        }
+        
+        if (changed || !block->cfaHasVisited) {
+            block->cfaShouldRevisit = true;
+            return true;
+        }
+        
+        return false;
+    }
+    
     void performBlockCFA(BasicBlock* block)
     {
@@ -116 +210 @@
             dataLog("   Block ", *block, ":\n");
         
+        if (m_blocksWithOSR.remove(block))
+            injectOSR(block);
+        
         m_state.beginBasicBlock(block);
         if (m_verbose) {
@@ -171 +268 @@
     InPlaceAbstractState m_state;
     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
+    BlockSet m_blocksWithOSR;
     
     bool m_verbose;

trunk/Source/JavaScriptCore/dfg/DFGOSREntry.cpp

@@ -101 +101 @@
 
     if (!Options::useOSREntryToDFG())
-        return 0;
+        return nullptr;
 
     if (Options::verboseOSR()) {
@@ -138 +138 @@
         if (Options::verboseOSR())
             dataLog("    OSR failed because the target code block is not DFG.\n");
-        return 0;
+        return nullptr;
     }
     
@@ -147 +147 @@
         if (Options::verboseOSR())
             dataLogF("    OSR failed because the entrypoint was optimized out.\n");
-        return 0;
+        return nullptr;
     }
     
@@ -183 +183 @@
                 dataLogF(".\n");
             }
-            return 0;
+            return nullptr;
         }
         
@@ -192 +192 @@
             value = exec->argument(argument - 1);
         
-        if (!entry->m_expectedValues.argument(argument).validate(value)) {
+        if (!entry->m_expectedValues.argument(argument).validateOSREntryValue(value, FlushedJSValue)) {
             if (Options::verboseOSR()) {
                 dataLog(
@@ -198 +198 @@
                     ", expected ", entry->m_expectedValues.argument(argument), ".\n");
             }
-            return 0;
+            return nullptr;
         }
     }
@@ -205 +205 @@
         int localOffset = virtualRegisterForLocal(local).offset();
         JSValue value = exec->registers()[localOffset].asanUnsafeJSValue();
-        if (!entry->m_expectedValues.local(local).validate(value)) {
-            if (Options::verboseOSR()) {
-                dataLog(
-                    "    OSR failed because variable ", VirtualRegister(localOffset), " is ",
+        FlushFormat format = FlushedJSValue;
+
+        if (entry->m_localsForcedAnyInt.get(local)) {
+            if (!value.isAnyInt()) {
+                dataLogLnIf(Options::verboseOSR(),
+                    "    OSR failed because variable ", localOffset, " is ",
                     value, ", expected ",
-                    entry->m_expectedValues.local(local), ".\n");
-            }
-            return 0;
-        }
+                    "machine int.");
+                return nullptr;
+            }
+            // Constant AnyInt value is stored as usual boxed value in AbstractValue.
+            format = FlushedInt52;
+        }
+
         if (entry->m_localsForcedDouble.get(local)) {
             if (!value.isNumber()) {
-                if (Options::verboseOSR()) {
-                    dataLog(
-                        "    OSR failed because variable ", localOffset, " is ",
-                        value, ", expected number.\n");
-                }
-                return 0;
-            }
-            continue;
-        }
-        if (entry->m_localsForcedAnyInt.get(local)) {
-            if (!value) {
-                if (Options::verboseOSR()) {
-                    dataLog(
-                        "    OSR failed because variable ", localOffset, " is ",
-                        value, ", expected ",
-                        "machine int.\n");
-                }
-                return 0;
-            }
-            continue;
+                dataLogLnIf(Options::verboseOSR(),
+                    "    OSR failed because variable ", localOffset, " is ",
+                    value, ", expected number.");
+                return nullptr;
+            }
+            value = jsDoubleNumber(value.asNumber());
+            format = FlushedDouble;
+        }
+
+        if (!entry->m_expectedValues.local(local).validateOSREntryValue(value, format)) {
+            dataLogLnIf(Options::verboseOSR(),
+                "    OSR failed because variable ", VirtualRegister(localOffset), " is ",
+                value, ", expected ",
+                entry->m_expectedValues.local(local), ".");
+            return nullptr;
         }
     }
@@ -250 +250 @@
         if (Options::verboseOSR())
             dataLogF("    OSR failed because stack growth failed.\n");
-        return 0;
+        return nullptr;
     }