[JSC] Remove merging must handle values into proven types in CFA
authorysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 8 Mar 2019 02:54:17 +0000 (02:54 +0000)
committerysuzuki@apple.com <ysuzuki@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 8 Mar 2019 02:54:17 +0000 (02:54 +0000)
https://bugs.webkit.org/show_bug.cgi?id=195444

Reviewed by Saam Barati.

Previously, we are merging must handle values as a proven constant in CFA. This is OK as long as this proven AbstractValue is blurred by merging the other legit AbstractValues
from the successors. But let's consider the following code, this is actually generated DFG graph from the attached test in r242626.

    Block #2 (loop header) succ #3, #4
    ...
    1: ForceOSRExit
    ...
    2: JSConstant(0)
    3: SetLocal(@2, loc6)
    ...
    4: Branch(#3, #4)

    Block #3 (This is OSR entry target) pred #2, #3, must handle value for loc6 => JSConstant(Int32, 31)
    ...
    5: GetLocal(loc6)
    6: StringFromCharCode(@5)
    ...

Block #3 is OSR entry target. So we have must handle value for loc6 and it is Int32 constant 31. Then we merge this constant as a proven value in #3's loc6 AbstractValue.
If the value from #2 blurs the value, it is OK. However, #2 has ForceOSRExit. So must handle value suddenly becomes the only source of loc6 in #3. Then we use this constant
as a proven value. But this is not expected behavior since must handle value is just a snapshot of the locals when we kick off the concurrent compilation. In the above example,
we assume that loop index is an constant 31, but it is wrong, and OSR entry fails. Because there is no strong assumption that the must handle value is the proven type or value,
we should not merge it in CFA.

Since (1) this is just an optimization, (2) type information is already propagated in prediction injection phase, and (3) the must handle value does not show the performance
progression in r211461 and we no longer see type misprediction in marsaglia-osr-entry.js, this patch simply removes must handle value type widening in CFA.

* dfg/DFGCFAPhase.cpp:
(JSC::DFG::CFAPhase::run):
(JSC::DFG::CFAPhase::performBlockCFA):
(JSC::DFG::CFAPhase::injectOSR): Deleted.

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

Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/dfg/DFGCFAPhase.cpp

index 347a80a..194ed19 100644 (file)
@@ -1,5 +1,44 @@
 2019-03-07  Yusuke Suzuki  <ysuzuki@apple.com>
 
+        [JSC] Remove merging must handle values into proven types in CFA
+        https://bugs.webkit.org/show_bug.cgi?id=195444
+
+        Reviewed by Saam Barati.
+
+        Previously, we are merging must handle values as a proven constant in CFA. This is OK as long as this proven AbstractValue is blurred by merging the other legit AbstractValues
+        from the successors. But let's consider the following code, this is actually generated DFG graph from the attached test in r242626.
+
+            Block #2 (loop header) succ #3, #4
+            ...
+            1: ForceOSRExit
+            ...
+            2: JSConstant(0)
+            3: SetLocal(@2, loc6)
+            ...
+            4: Branch(#3, #4)
+
+            Block #3 (This is OSR entry target) pred #2, #3, must handle value for loc6 => JSConstant(Int32, 31)
+            ...
+            5: GetLocal(loc6)
+            6: StringFromCharCode(@5)
+            ...
+
+        Block #3 is OSR entry target. So we have must handle value for loc6 and it is Int32 constant 31. Then we merge this constant as a proven value in #3's loc6 AbstractValue.
+        If the value from #2 blurs the value, it is OK. However, #2 has ForceOSRExit. So must handle value suddenly becomes the only source of loc6 in #3. Then we use this constant
+        as a proven value. But this is not expected behavior since must handle value is just a snapshot of the locals when we kick off the concurrent compilation. In the above example,
+        we assume that loop index is an constant 31, but it is wrong, and OSR entry fails. Because there is no strong assumption that the must handle value is the proven type or value,
+        we should not merge it in CFA.
+
+        Since (1) this is just an optimization, (2) type information is already propagated in prediction injection phase, and (3) the must handle value does not show the performance
+        progression in r211461 and we no longer see type misprediction in marsaglia-osr-entry.js, this patch simply removes must handle value type widening in CFA.
+
+        * dfg/DFGCFAPhase.cpp:
+        (JSC::DFG::CFAPhase::run):
+        (JSC::DFG::CFAPhase::performBlockCFA):
+        (JSC::DFG::CFAPhase::injectOSR): Deleted.
+
+2019-03-07  Yusuke Suzuki  <ysuzuki@apple.com>
+
         [JSC] StringFromCharCode fast path should accept 0xff in DFG and FTL
         https://bugs.webkit.org/show_bug.cgi?id=195429
 
index f6f9506..a0a901d 100644 (file)
@@ -76,63 +76,12 @@ public:
         
         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;
             performForwardCFA();
         } while (m_changed);
         
         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.
             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
@@ -157,45 +106,6 @@ public:
     }
     
 private:
-    bool injectOSR(BasicBlock* block)
-    {
-        if (m_verbose)
-            dataLog("   Found must-handle block: ", *block, "\n");
-        
-        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)
     {
         if (!block)
@@ -205,9 +115,6 @@ private:
         if (m_verbose)
             dataLog("   Block ", *block, ":\n");
         
-        if (m_blocksWithOSR.remove(block))
-            injectOSR(block);
-        
         m_state.beginBasicBlock(block);
         if (m_verbose) {
             dataLog("      head vars: ", block->valuesAtHead, "\n");
@@ -263,7 +170,6 @@ private:
 private:
     InPlaceAbstractState m_state;
     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
-    BlockSet m_blocksWithOSR;
     
     bool m_verbose;