Changeset 266242 in webkit for trunk/Source/JavaScriptCore


Ignore:
Timestamp:
Aug 27, 2020, 10:10:18 AM (5 years ago)
Author:
[email protected]
Message:

OSR availability validation should run for any node with exitOK
​https://bugs.webkit.org/show_bug.cgi?id=215672

Reviewed by Saam Barati.

Currently we only validate OSR exit availability if a node would
say mayExit(graph, node) != DoesNotExit and the node is marked
as exitOK. However, it would be perfectly valid to insert a node
that exits anywhere we have a node marked exitOK. So with this
patch we now validate all places where it would ever be possible
to OSR exit.

Relaxing our criteria revealed a number of bugs however. Which I
will describe below in, IMO, increasing complexity/subtly.

First, we currently don't mark arity fixup during inlining as not
exitOK. However, since our arity code says its code origin is
OpEnter, we assume arity fixup has already happened.

Second, OpGetScope, should not mark its first argument as used
since it's not actually used. This is problematic because we could
have a loop where OpGetScope is the first bytecode, namely when
doing tail recursive inlining. If we were in that position, there
could be a local that was used at a merge point at the loop
backedge that had two MovHint defs from both predecessors. In DFG
IR this would look like:

BB#1:
@1: MovHint(Undefined, loc1)
...
Jump(#2)

BB#2:
... loc1 is live here in bytecode
@2: MovHint(@scopeObject, loc1)
@3: SetLocal(@scopeObject, loc1)
Branch(#3, #4) #4 is the successor of the tail call loop

BB#3:
@4 MovHint(Undefined, loc1)
...
Jump(#2)

When we do CPS conversion the MovHints at @1 and @4 will be seen
as different variables (there's no GetLocal). Then, after, during
SSA conversion we won't insert a phi connecting them, making the
argument to OpGetScope, in this case loc1, unrecoverable there are
conflicting nodes and the value isn't saved on the stack.

There were also issues with MovHintRemoval Phase but rather than
fix them we opted to just remove the phase as it didn't show any
performance impact. I'll describe the issues I found below for
completeness, however.

Third, MovHint removal phase had a bug where it would not mark
sections where a zombied MovHint has yet to be killed as not
exitOK. So in theory another phase could come along and insert an
exiting node there.

Fourth, MovHint removal phase had a second bug where a MovHint
that was not killed in the current block would be zombied, which
is wrong for SSA. It's wrong because the MovHinted value could
still be live for OSR exit in a successor block.

Lastly, this patch adds some new verbose options as well as the ability to
dump a DFG::BasicBlock without dereferencing it.

  • bytecode/BytecodeUseDef.cpp:

(JSC::computeUsesForBytecodeIndexImpl):

  • dfg/DFGBasicBlock.cpp:

(WTF::printInternal):

  • dfg/DFGBasicBlock.h:
  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::inlineCall):

  • dfg/DFGCPSRethreadingPhase.cpp:

(JSC::DFG::CPSRethreadingPhase::propagatePhis):

  • dfg/DFGEpoch.h:

(JSC::DFG::Epoch::operator bool const):

  • dfg/DFGOSRAvailabilityAnalysisPhase.cpp:

(JSC::DFG::OSRAvailabilityAnalysisPhase::run):

  • dfg/DFGSSACalculator.cpp:

(JSC::DFG::SSACalculator::dump const):

Location:
trunk/Source/JavaScriptCore
Files:
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r266236 r266242  
     12020-08-27  Keith Miller  <[email protected]>
     2
     3        OSR availability validation should run for any node with exitOK
     4        https://bugs.webkit.org/show_bug.cgi?id=215672
     5
     6        Reviewed by Saam Barati.
     7
     8        Currently we only validate OSR exit availability if a node would
     9        say `mayExit(graph, node) != DoesNotExit` and the node is marked
     10        as exitOK. However, it would be perfectly valid to insert a node
     11        that exits anywhere we have a node marked exitOK. So with this
     12        patch we now validate all places where it would ever be possible
     13        to OSR exit.
     14
     15        Relaxing our criteria revealed a number of bugs however. Which I
     16        will describe below in, IMO, increasing complexity/subtly.
     17
     18        First, we currently don't mark arity fixup during inlining as not
     19        exitOK. However, since our arity code says its code origin is
     20        OpEnter, we assume arity fixup has already happened.
     21
     22        Second, OpGetScope, should not mark its first argument as used
     23        since it's not actually used. This is problematic because we could
     24        have a loop where OpGetScope is the first bytecode, namely when
     25        doing tail recursive inlining. If we were in that position, there
     26        could be a local that was used at a merge point at the loop
     27        backedge that had two MovHint defs from both predecessors. In DFG
     28        IR this would look like:
     29
     30        BB#1:
     31        @1: MovHint(Undefined, loc1)
     32        ...
     33        Jump(#2)
     34
     35        BB#2:
     36        ... // loc1 is live here in bytecode
     37        @2: MovHint(@scopeObject, loc1)
     38        @3: SetLocal(@scopeObject, loc1)
     39        Branch(#3, #4) // #4 is the successor of the tail call loop
     40
     41        BB#3:
     42        @4 MovHint(Undefined, loc1)
     43        ...
     44        Jump(#2)
     45
     46        When we do CPS conversion the MovHints at @1 and @4 will be seen
     47        as different variables (there's no GetLocal). Then, after, during
     48        SSA conversion we won't insert a phi connecting them, making the
     49        argument to OpGetScope, in this case loc1, unrecoverable there are
     50        conflicting nodes and the value isn't saved on the stack.
     51
     52        There were also issues with MovHintRemoval Phase but rather than
     53        fix them we opted to just remove the phase as it didn't show any
     54        performance impact. I'll describe the issues I found below for
     55        completeness, however.
     56
     57        Third, MovHint removal phase had a bug where it would not mark
     58        sections where a zombied MovHint has yet to be killed as not
     59        exitOK. So in theory another phase could come along and insert an
     60        exiting node there.
     61
     62        Fourth, MovHint removal phase had a second bug where a MovHint
     63        that was not killed in the current block would be zombied, which
     64        is wrong for SSA. It's wrong because the MovHinted value could
     65        still be live for OSR exit in a successor block.
     66
     67        Lastly, this patch adds some new verbose options as well as the ability to
     68        dump a DFG::BasicBlock without dereferencing it.
     69
     70        * bytecode/BytecodeUseDef.cpp:
     71        (JSC::computeUsesForBytecodeIndexImpl):
     72        * dfg/DFGBasicBlock.cpp:
     73        (WTF::printInternal):
     74        * dfg/DFGBasicBlock.h:
     75        * dfg/DFGByteCodeParser.cpp:
     76        (JSC::DFG::ByteCodeParser::inlineCall):
     77        * dfg/DFGCPSRethreadingPhase.cpp:
     78        (JSC::DFG::CPSRethreadingPhase::propagatePhis):
     79        * dfg/DFGEpoch.h:
     80        (JSC::DFG::Epoch::operator bool const):
     81        * dfg/DFGOSRAvailabilityAnalysisPhase.cpp:
     82        (JSC::DFG::OSRAvailabilityAnalysisPhase::run):
     83        * dfg/DFGSSACalculator.cpp:
     84        (JSC::DFG::SSACalculator::dump const):
     85
    1862020-08-27  Keith Miller  <[email protected]>
    287

  • trunk/Source/JavaScriptCore/bytecode/BytecodeUseDef.cpp

    r265907 r266242  
    101101    case op_super_sampler_begin:
    102102    case op_super_sampler_end:
    103         return;
    104 
    105     USES(OpGetScope, dst)
     103    case op_get_scope:
     104        return;
     105
    106106    USES(OpToThis, srcDst)
    107107    USES(OpCheckTdz, targetVirtualRegister)

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

    r261895 r266242  
    151151} } // namespace JSC::DFG
    152152
     153namespace WTF {
     154
     155void printInternal(PrintStream& out, JSC::DFG::BasicBlock* block)
     156{
     157    out.print(*block);
     158}
     159
     160}
     161
    153162#endif // ENABLE(DFG_JIT)
    154163

  • trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h

    r254735 r266242  
    276276} } // namespace JSC::DFG
    277277
     278namespace WTF {
     279void printInternal(PrintStream&, JSC::DFG::BasicBlock*);
     280}
     281
    278282#endif // ENABLE(DFG_JIT)

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

    r265934 r266242  
    17221722    BytecodeIndex oldIndex = m_currentIndex;
    17231723    m_currentIndex = BytecodeIndex(0);
     1724
     1725    // We don't want to exit here since we could do things like arity fixup which complicates OSR exit availability.
     1726    m_exitOK = false;
    17241727
    17251728    switch (kind) {

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

    r261895 r266242  
    3636
    3737class CPSRethreadingPhase : public Phase {
     38    static constexpr bool verbose = false;
    3839public:
    3940    CPSRethreadingPhase(Graph& graph)
    … …  
    426427            size_t index = entry.m_index;
    427428           
     429            if (verbose) {
     430                dataLog(" Iterating on phi from block ", block, " ");
     431                m_graph.dump(WTF::dataFile(), "", currentPhi);
     432            }
     433
    428434            for (size_t i = predecessors.size(); i--;) {
    429435                BasicBlock* predecessorBlock = predecessors[i];
    … …  
    434440                    predecessorBlock->variablesAtTail.atFor<operandKind>(index) = variableInPrevious;
    435441                    predecessorBlock->variablesAtHead.atFor<operandKind>(index) = variableInPrevious;
     442                    dataLogLnIf(verbose, "    No variable in predecessor ", predecessorBlock, " creating a new phi: ", variableInPrevious);
    436443                } else {
    437444                    switch (variableInPrevious->op()) {
    … …  
    439446                    case PhantomLocal:
    440447                    case Flush:
     448                        dataLogLnIf(verbose, "    Variable in predecessor ", predecessorBlock, " ", variableInPrevious, " needs to be forwarded to first child ", variableInPrevious->child1().node());
    441449                        ASSERT(variableInPrevious->variableAccessData() == variableInPrevious->child1()->variableAccessData());
    442450                        variableInPrevious = variableInPrevious->child1().node();
    … …  
    453461                    || variableInPrevious->op() == SetArgumentMaybe);
    454462         
     463                if (verbose)
     464                    m_graph.dump(WTF::dataFile(), "    Adding new variable from predecessor ", variableInPrevious);
     465
    455466                if (!currentPhi->child1()) {
    456467                    currentPhi->children.setChild1(Edge(variableInPrevious));

  • trunk/Source/JavaScriptCore/dfg/DFGEpoch.h

    r250005 r266242  
    6565    }
    6666   
     67    explicit operator bool() const
     68    {
     69        return !!*this;
     70    }
     71   
    6772    Epoch next() const
    6873    {

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

    r266095 r266242  
    135135                for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
    136136                    Node* node = block->at(nodeIndex);
    137                     // FIXME: The mayExit status of a node doesn't seem like it should mean we don't need to have everything available.
    138                     if (mayExit(m_graph, node) != DoesNotExit && node->origin.exitOK) {
     137                    if (node->origin.exitOK) {
    139138                        // If we're allowed to exit here, the heap must be in a state
    140139                        // where exiting wouldn't crash. These particular fields are
    … …  
    144143
    145144                        CodeOrigin exitOrigin = node->origin.forExit;
    146                         AvailabilityMap& availabilityMap = calculator.m_availability;
     145                        // FIXME: availabilityMap seems like it should be able to be a reference to the calculator's map. https://bugs.webkit.org/show_bug.cgi?id=215675
     146                        AvailabilityMap availabilityMap = calculator.m_availability;
    147147                        availabilityMap.pruneByLiveness(m_graph, exitOrigin);
    148148

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

    r261895 r266242  
    116116        m_variables[i].dumpVerbose(out);
    117117    }
    118     out.print("], Defs: [");
     118    out.print("], \nDefs: [");
    119119    comma = CommaPrinter();
    120120    for (Def* def : const_cast<SSACalculator*>(this)->m_defs)
    121121        out.print(comma, *def);
    122     out.print("], Phis: [");
     122    out.print("], \nPhis: [");
    123123    comma = CommaPrinter();
    124124    for (Def* def : const_cast<SSACalculator*>(this)->m_phis)
    125125        out.print(comma, *def);
    126     out.print("], Block data: [");
    127     comma = CommaPrinter();
     126    out.print("], \nBlock data: [");
     127    comma = CommaPrinter(",\n");
    128128    for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
    129129        BasicBlock* block = m_graph.block(blockIndex);
Note: See TracChangeset for help on using the changeset viewer.