⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 242627 in webkit


Ignore:
Timestamp:
Mar 7, 2019, 6:54:17 PM (7 years ago)
Author:
ysuzuki@apple.com
Message:

[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.

Location:
trunk/Source/JavaScriptCore
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r242626 r242627  
     12019-03-07  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [JSC] Remove merging must handle values into proven types in CFA
     4        https://bugs.webkit.org/show_bug.cgi?id=195444
     5
     6        Reviewed by Saam Barati.
     7
     8        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
     9        from the successors. But let's consider the following code, this is actually generated DFG graph from the attached test in r242626.
     10
     11            Block #2 (loop header) succ #3, #4
     12            ...
     13            1: ForceOSRExit
     14            ...
     15            2: JSConstant(0)
     16            3: SetLocal(@2, loc6)
     17            ...
     18            4: Branch(#3, #4)
     19
     20            Block #3 (This is OSR entry target) pred #2, #3, must handle value for loc6 => JSConstant(Int32, 31)
     21            ...
     22            5: GetLocal(loc6)
     23            6: StringFromCharCode(@5)
     24            ...
     25
     26        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.
     27        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
     28        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,
     29        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,
     30        we should not merge it in CFA.
     31
     32        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
     33        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.
     34
     35        * dfg/DFGCFAPhase.cpp:
     36        (JSC::DFG::CFAPhase::run):
     37        (JSC::DFG::CFAPhase::performBlockCFA):
     38        (JSC::DFG::CFAPhase::injectOSR): Deleted.
     39
    1402019-03-07  Yusuke Suzuki  <ysuzuki@apple.com>
    241

  • trunk/Source/JavaScriptCore/dfg/DFGCFAPhase.cpp

    r242192 r242627  
    7777        m_state.initialize();
    7878       
    79         if (m_graph.m_form != SSA) {
    80             if (m_verbose)
    81                 dataLog("   Widening state at OSR entry block.\n");
    82            
    83             // Widen the abstract values at the block that serves as the must-handle OSR entry.
    84             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
    85                 BasicBlock* block = m_graph.block(blockIndex);
    86                 if (!block)
    87                     continue;
    88                
    89                 if (!block->isOSRTarget)
    90                     continue;
    91                 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex())
    92                     continue;
    93                
    94                 // We record that the block needs some OSR stuff, but we don't do that yet. We want to
    95                 // handle OSR entry data at the right time in order to get the best compile times. If we
    96                 // simply injected OSR data right now, then we'd potentially cause a loop body to be
    97                 // interpreted with just the constants we feed it, which is more expensive than if we
    98                 // interpreted it with non-constant values. If we always injected this data after the
    99                 // main pass of CFA ran, then we would potentially spend a bunch of time rerunning CFA
    100                 // after convergence. So, we try very hard to inject OSR data for a block when we first
    101                 // naturally come to see it - see the m_blocksWithOSR check in performBlockCFA(). This
    102                 // way, we:
    103                 //
    104                 // - Reduce the likelihood of interpreting the block with constants, since we will inject
    105                 //   the OSR entry constants on top of whatever abstract values we got for that block on
    106                 //   the first pass. The mix of those two things is likely to not be constant.
    107                 //
    108                 // - Reduce the total number of CFA reexecutions since we inject the OSR data as part of
    109                 //   the normal flow of CFA instead of having to do a second fixpoint. We may still have
    110                 //   to do a second fixpoint if we don't even reach the OSR entry block during the main
    111                 //   run of CFA, but in that case at least we're not being redundant.
    112                 m_blocksWithOSR.add(block);
    113             }
    114         }
    115 
    11679        do {
    11780            m_changed = false;
    … …  
    12083       
    12184        if (m_graph.m_form != SSA) {
    122             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
    123                 BasicBlock* block = m_graph.block(blockIndex);
    124                 if (!block)
    125                     continue;
    126                
    127                 if (m_blocksWithOSR.remove(block))
    128                     m_changed |= injectOSR(block);
    129             }
    130            
    131             while (m_changed) {
    132                 m_changed = false;
    133                 performForwardCFA();
    134             }
    135        
    13685            // Make sure we record the intersection of all proofs that we ever allowed the
    13786            // compiler to rely upon.
    … …  
    158107   
    159108private:
    160     bool injectOSR(BasicBlock* block)
    161     {
    162         if (m_verbose)
    163             dataLog("   Found must-handle block: ", *block, "\n");
    164        
    165         bool changed = false;
    166         const Operands<Optional<JSValue>>& mustHandleValues = m_graph.m_plan.mustHandleValues();
    167         for (size_t i = mustHandleValues.size(); i--;) {
    168             int operand = mustHandleValues.operandForIndex(i);
    169             Optional<JSValue> value = mustHandleValues[i];
    170             if (!value) {
    171                 if (m_verbose)
    172                     dataLog("   Not live in bytecode: ", VirtualRegister(operand), "\n");
    173                 continue;
    174             }
    175             Node* node = block->variablesAtHead.operand(operand);
    176             if (!node) {
    177                 if (m_verbose)
    178                     dataLog("   Not live: ", VirtualRegister(operand), "\n");
    179                 continue;
    180             }
    181            
    182             if (m_verbose)
    183                 dataLog("   Widening ", VirtualRegister(operand), " with ", value.value(), "\n");
    184            
    185             AbstractValue& target = block->valuesAtHead.operand(operand);
    186             changed |= target.mergeOSREntryValue(m_graph, value.value());
    187             target.fixTypeForRepresentation(
    188                 m_graph, resultFor(node->variableAccessData()->flushFormat()), node);
    189         }
    190        
    191         if (changed || !block->cfaHasVisited) {
    192             block->cfaShouldRevisit = true;
    193             return true;
    194         }
    195        
    196         return false;
    197     }
    198    
    199109    void performBlockCFA(BasicBlock* block)
    200110    {
    … …  
    205115        if (m_verbose)
    206116            dataLog("   Block ", *block, ":\n");
    207        
    208         if (m_blocksWithOSR.remove(block))
    209             injectOSR(block);
    210117       
    211118        m_state.beginBasicBlock(block);
    … …  
    264171    InPlaceAbstractState m_state;
    265172    AbstractInterpreter<InPlaceAbstractState> m_interpreter;
    266     BlockSet m_blocksWithOSR;
    267173   
    268174    bool m_verbose;
Note: See TracChangeset for help on using the changeset viewer.