Changeset 189126 in webkit


Ignore:
Timestamp:
Aug 28, 2015 3:38:41 PM (9 years ago)
Author:
fpizlo@apple.com
Message:

LICM should be sound even if the CFG has changed
https://bugs.webkit.org/show_bug.cgi?id=148259

Reviewed by Benjamin Poulain.

Source/JavaScriptCore:

Prior to this change, LICM expected a certain CFG shape around a loop: broken critical edges,
a pre-header, and the pre-header's terminal has exitOK. LICM would either crash on an
assertion, or generate code that fails validation, if these conditions weren't met.

The broken critical edge assumption is fine; so far we are assuming that SSA means broken
critical edges. We may revisit this, but we don't have to right now.

The other assumptions are not fine, because it's hard to guarantee that every phase will
preserve the presence of pre-headers. Even if we required that pre-headers are regenerated
before LICM, that regeneration wouldn't be guaranteed to create pre-headers that have exitOK at
the terminal. That's because once in SSA, the loop header probably has exitOK=false at the
head because of Phi's. Pre-header creation has no choice but to use the Node::origin from the
loop header, which means creating a pre-header that has exitOK=false. Regardless of whether
that's a fixable problem, it seems that our best short-term approach is just to be defensive
and turn undesirable pathologies into performance bugs and not crashes.

For the foreseeable future, once pre-headers are created they will probably not be removed. Our
current CFG simplification phase doesn't have a rule for removing pre-headers (since it doesn't
have any jump threading). So, it wouldn't be profitable to put effort towards reneration of
pre-headers for LICM's benefit.

Also, we cannot guarantee that some sequence of CFG transformations will not create a loop that
doesn't have a pre-header. This would be super rare. But you could imagine that some program
has control flow encoded using relooping (like
https://github.com/kripken/Relooper/blob/master/paper.pdf). If that happens, our compiler will
probably incrementally discover the "original" CFG. That may happen only after SSA conversion,
and so after pre-header generation. This is super unlikely for a bunch of reasons, but it
*could* happen.

So, this patch just makes sure that if pre-headers are missing or cannot be exited from, LICM
will simply avoid hoisting out of that block. At some point later, we can worry about a more
comprehensive solution to the pre-header problem. That's covered by this bug:
https://bugs.webkit.org/show_bug.cgi?id=148586

  • dfg/DFGLICMPhase.cpp:

(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):

  • dfg/DFGPlan.cpp:

(JSC::DFG::Plan::compileInThreadImpl):

  • runtime/Options.h:
  • tests/stress/licm-no-pre-header.js: Added.

(foo):

  • tests/stress/licm-pre-header-cannot-exit.js: Added.

(foo):

Tools:

Add a utility for creating tests that set some uncommon option.

  • Scripts/run-jsc-stress-tests:
Location:
trunk
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/ChangeLog

    r189124 r189126  
     12015-08-28  Filip Pizlo  <fpizlo@apple.com>
     2
     3        LICM should be sound even if the CFG has changed
     4        https://bugs.webkit.org/show_bug.cgi?id=148259
     5
     6        Reviewed by Benjamin Poulain.
     7
     8        Prior to this change, LICM expected a certain CFG shape around a loop: broken critical edges,
     9        a pre-header, and the pre-header's terminal has exitOK. LICM would either crash on an
     10        assertion, or generate code that fails validation, if these conditions weren't met.
     11
     12        The broken critical edge assumption is fine; so far we are assuming that SSA means broken
     13        critical edges. We may revisit this, but we don't have to right now.
     14
     15        The other assumptions are not fine, because it's hard to guarantee that every phase will
     16        preserve the presence of pre-headers. Even if we required that pre-headers are regenerated
     17        before LICM, that regeneration wouldn't be guaranteed to create pre-headers that have exitOK at
     18        the terminal. That's because once in SSA, the loop header probably has exitOK=false at the
     19        head because of Phi's. Pre-header creation has no choice but to use the Node::origin from the
     20        loop header, which means creating a pre-header that has exitOK=false. Regardless of whether
     21        that's a fixable problem, it seems that our best short-term approach is just to be defensive
     22        and turn undesirable pathologies into performance bugs and not crashes.
     23
     24        For the foreseeable future, once pre-headers are created they will probably not be removed. Our
     25        current CFG simplification phase doesn't have a rule for removing pre-headers (since it doesn't
     26        have any jump threading). So, it wouldn't be profitable to put effort towards reneration of
     27        pre-headers for LICM's benefit.
     28
     29        Also, we cannot guarantee that some sequence of CFG transformations will not create a loop that
     30        doesn't have a pre-header. This would be super rare. But you could imagine that some program
     31        has control flow encoded using relooping (like
     32        https://github.com/kripken/Relooper/blob/master/paper.pdf). If that happens, our compiler will
     33        probably incrementally discover the "original" CFG. That may happen only after SSA conversion,
     34        and so after pre-header generation. This is super unlikely for a bunch of reasons, but it
     35        *could* happen.
     36
     37        So, this patch just makes sure that if pre-headers are missing or cannot be exited from, LICM
     38        will simply avoid hoisting out of that block. At some point later, we can worry about a more
     39        comprehensive solution to the pre-header problem. That's covered by this bug:
     40        https://bugs.webkit.org/show_bug.cgi?id=148586
     41
     42        * dfg/DFGLICMPhase.cpp:
     43        (JSC::DFG::LICMPhase::run):
     44        (JSC::DFG::LICMPhase::attemptHoist):
     45        * dfg/DFGPlan.cpp:
     46        (JSC::DFG::Plan::compileInThreadImpl):
     47        * runtime/Options.h:
     48        * tests/stress/licm-no-pre-header.js: Added.
     49        (foo):
     50        * tests/stress/licm-pre-header-cannot-exit.js: Added.
     51        (foo):
     52
    1532015-08-28  Yusuke Suzuki  <utatane.tea@gmail.com>
    254
  • trunk/Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp

    r188979 r189126  
    4747    bool run()
    4848    {
     49        // FIXME: We should make this work in SSA. https://bugs.webkit.org/show_bug.cgi?id=148260
     50        DFG_ASSERT(m_graph, nullptr, m_graph.m_form != SSA);
     51       
    4952        const bool extremeLogging = false;
    5053
  • trunk/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp

    r189070 r189126  
    4747struct LoopData {
    4848    LoopData()
    49         : preHeader(0)
     49        : preHeader(nullptr)
    5050    {
    5151    }
     
    113113            const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
    114114            LoopData& data = m_data[loop.index()];
     115           
    115116            for (
    116117                const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
     
    120121           
    121122            BasicBlock* header = loop.header();
    122             BasicBlock* preHeader = 0;
     123            BasicBlock* preHeader = nullptr;
     124            unsigned numberOfPreHeaders = 0; // We're cool if this is 1.
     125
     126            // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a
     127            // loop header must have a predecessor. (Also, we don't allow the root block to be a loop,
     128            // which cuts out the one other way of having a loop header with only one predecessor.)
     129            DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1);
     130           
    123131            for (unsigned i = header->predecessors.size(); i--;) {
    124132                BasicBlock* predecessor = header->predecessors[i];
    125133                if (m_graph.m_dominators.dominates(header, predecessor))
    126134                    continue;
    127                 DFG_ASSERT(m_graph, nullptr, !preHeader || preHeader == predecessor);
     135
    128136                preHeader = predecessor;
    129             }
    130            
     137                ++numberOfPreHeaders;
     138            }
     139
     140            // We need to validate the pre-header. There are a bunch of things that could be wrong
     141            // about it:
     142            //
     143            // - There might be more than one. This means that pre-header creation either did not run,
     144            //   or some CFG transformation destroyed the pre-headers.
     145            //
     146            // - It may not be legal to exit at the pre-header. That would be a real bummer. Currently,
     147            //   LICM assumes that it can always hoist checks. See
     148            //   https://bugs.webkit.org/show_bug.cgi?id=148545. Though even with that fixed, we anyway
     149            //   would need to check if it's OK to exit at the pre-header since if we can't then we
     150            //   would have to restrict hoisting to non-exiting nodes.
     151
     152            if (numberOfPreHeaders != 1)
     153                continue;
     154
     155            // This is guaranteed because the header has multiple predecessors and critical edges are
     156            // broken. Therefore the predecessors must all have one successor, which implies that they
     157            // must end in a Jump.
    131158            DFG_ASSERT(m_graph, preHeader->terminal(), preHeader->terminal()->op() == Jump);
    132            
    133             // We should validate the pre-header. This currently assumes that it's valid to OSR exit at
    134             // the Jump of the pre-header. That may not always be the case, like if we lowered a Node
    135             // that was ExitInvalid to a loop. This phase should somehow defend against this - at the
    136             // very least with assertions, if not with something better (like only hoisting things that
    137             // cannot exit).
    138             // FIXME: https://bugs.webkit.org/show_bug.cgi?id=148259
     159
     160            if (!preHeader->terminal()->origin.exitOK)
     161                continue;
    139162           
    140163            data.preHeader = preHeader;
     
    147170        // - The node doesn't write anything.
    148171        // - The node doesn't read anything that the loop writes.
     172        // - The preHeader is valid (i.e. it passed the validation above).
    149173        // - The preHeader's state at tail makes the node safe to execute.
    150174        // - The loop's children all belong to nodes that strictly dominate the loop header.
     
    206230        Node* node = nodeRef;
    207231        LoopData& data = m_data[loop->index()];
     232
     233        if (!data.preHeader) {
     234            if (verbose)
     235                dataLog("    Not hoisting ", node, " because the pre-header is invalid.\n");
     236            return false;
     237        }
    208238       
    209239        if (!data.preHeader->cfaDidFinish) {
  • trunk/Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp

    r189013 r189126  
    4040BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block)
    4141{
     42    // FIXME: If we run this utility on SSA IR, then we may end up with a bizarre arrangement of
     43    // Upsilons and Phis, like:
     44    //
     45    // BB#1:
     46    //     Upsilon(@a, ^p)
     47    //     Jump(#3)
     48    //
     49    // BB#2:
     50    //     Upsilon(@b, ^p)
     51    //     Jump(#3)
     52    //
     53    // BB#3:
     54    //     Jump(#4)
     55    //
     56    // BB#4:
     57    //     p: Phi()
     58    //
     59    // Notice how the Upsilons are not in the predecessor of the Phi anymore. It's not clear if this
     60    // would be bad. Probably not, but it's weird anyway. We should add a validation rule, and we
     61    // should implement a Upsilon/Phi canonicalization that handles this by calling into the
     62    // SSACalculator and treating the Upsilons as Defs and rebuilding the Phis from scratch.
     63    //
     64    // https://bugs.webkit.org/show_bug.cgi?id=148587
     65   
    4266    // Don't bother to preserve execution frequencies for now.
    4367    BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN);
     68
     69    // FIXME: It would be great if we put some effort into enabling exitOK at this origin, if it
     70    // happens to be unset. It might not be set because the loop header (i.e. "block") has Phis in it.
     71    // Phis have to have exitOK=false. There are a few ways to try to set exitOK:
     72    //
     73    // - Regenerate an exit origin by proving that we are at an exit origin boundary. If all of the
     74    //   predecessors' terminals have different exit origins than the exit origin of head of block,
     75    //   then we can leverage the assumption that exit origin boundaries can always exit. We could
     76    //   extend this further, and say that we will set exitOK even if a predecessor's terminal has the
     77    //   same exit origin, but so long it hadn't done anything that clobbers exit since the start of
     78    //   the origin.
     79    //
     80    // - Analyze the Phi's and MovHint's at the head of block. If prior to the ExitOK there are only
     81    //   Phi's and MovHint's, we could "roll them back" by proving that for each of the MovHints, the
     82    //   referenced Phi has a child that dominates the pre-header, and that child is the node that is
     83    //   OSR-available at the local being MovHinted.
     84    //
     85    // Note that there are some obviously wrong ways to try to set exitOK. For example, we cannot
     86    // simply use the origin of our predecessors, since in bytecode that could be *any* kind of
     87    // instruction. It may not even be a control flow construct, if we had lowered some non-control
     88    // bytecode operation into DFG IR that has control flow. Hence, we really do need to try to use the
     89    // origin of the head of the loop header.
     90    //
     91    // https://bugs.webkit.org/show_bug.cgi?id=148586
    4492    preHeader->appendNode(
    4593        graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block));
  • trunk/Source/JavaScriptCore/dfg/DFGPlan.cpp

    r186985 r189126  
    375375        performCleanUp(dfg); // Reduce the graph size a bit.
    376376        performCriticalEdgeBreaking(dfg);
    377         performLoopPreHeaderCreation(dfg);
     377        if (Options::createPreHeaders())
     378            performLoopPreHeaderCreation(dfg);
    378379        performCPSRethreading(dfg);
    379380        performSSAConversion(dfg);
  • trunk/Source/JavaScriptCore/runtime/Options.h

    r188752 r189126  
    196196    v(unsigned, frequentCallThreshold, 2, nullptr) \
    197197    v(double, minimumCallToKnownRate, 0.51, nullptr) \
     198    v(bool, createPreHeaders, true, nullptr) \
    198199    v(bool, enableMovHintRemoval, true, nullptr) \
    199200    v(bool, enableObjectAllocationSinking, true, nullptr) \
  • trunk/Tools/ChangeLog

    r189125 r189126  
     12015-08-28  Filip Pizlo  <fpizlo@apple.com>
     2
     3        LICM should be sound even if the CFG has changed
     4        https://bugs.webkit.org/show_bug.cgi?id=148259
     5
     6        Reviewed by Benjamin Poulain.
     7
     8        Add a utility for creating tests that set some uncommon option.
     9
     10        * Scripts/run-jsc-stress-tests:
     11
    1122015-08-28  Brent Fulgham  <bfulgham@apple.com>
    213
  • trunk/Tools/Scripts/run-jsc-stress-tests

    r188767 r189126  
    763763end
    764764
     765def runMiscNoCJITTest(*options)
     766    run("misc-no-cjit", *(NO_CJIT_OPTIONS + options))
     767end
     768
     769def runMiscFTLNoCJITTest(*options)
     770    run("misc-ftl-no-cjit", *(FTL_OPTIONS + NO_CJIT_OPTIONS + options))
     771end
     772
    765773def defaultRun
    766774    runDefault
Note: See TracChangeset for help on using the changeset viewer.