Changeset 128699 in webkit


Ignore:
Timestamp:
Sep 15, 2012 7:36:22 PM (12 years ago)
Author:
fpizlo@apple.com
Message:

Structure check hoisting fails to consider the possibility of conflicting checks on the source of the first assignment to the hoisted variable
​https://bugs.webkit.org/show_bug.cgi?id=96872

Reviewed by Oliver Hunt.

This does a few related things:

  • It turns off the use of ForceOSRExit for sure-to-fail CheckStructures, because I noticed that this would sometimes happen for a ForwardCheckStructure. The problem is that ForceOSRExit exits backwards, not forwards. Since the code that led to those ForceOSRExit's being inserted was written out of paranoia rather than need, I removed it. Specifically, I removed the m_isValid = false code for CheckStructure/StructureTransitionWatchpoint in AbstractState.


  • If a structure check causes a structure set to go empty, we don't want a PutStructure to revive the set. It should instead be smart enough to realize that an empty set implies that the code can't execute. This was the only "bug" that the use of m_isValid = false was preventing.


  • Finally, the main change: structure check hoisting looks at the source of the SetLocals on structure-check-hoistable variables and ensures that the source is not checked with a conflicting structure. This is O(n2) but it does not show up at all in performance tests.


The first two parts of this change were auxiliary bugs that were revealed by
the structure check hoister doing bad things.

  • dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::initialize):
(JSC::DFG::AbstractState::execute):

  • dfg/DFGStructureCheckHoistingPhase.cpp:

(JSC::DFG::StructureCheckHoistingPhase::run):

Location:
trunk/Source/JavaScriptCore
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r128680 r128699  
     12012-09-15  Filip Pizlo  <fpizlo@apple.com>
     2
     3        Structure check hoisting fails to consider the possibility of conflicting checks on the source of the first assignment to the hoisted variable
     4        https://bugs.webkit.org/show_bug.cgi?id=96872
     5
     6        Reviewed by Oliver Hunt.
     7
     8        This does a few related things:
     9       
     10        - It turns off the use of ForceOSRExit for sure-to-fail CheckStructures, because
     11          I noticed that this would sometimes happen for a ForwardCheckStructure. The
     12          problem is that ForceOSRExit exits backwards, not forwards. Since the code that
     13          led to those ForceOSRExit's being inserted was written out of paranoia rather
     14          than need, I removed it. Specifically, I removed the m_isValid = false code
     15          for CheckStructure/StructureTransitionWatchpoint in AbstractState.
     16       
     17        - If a structure check causes a structure set to go empty, we don't want a
     18          PutStructure to revive the set. It should instead be smart enough to realize
     19          that an empty set implies that the code can't execute. This was the only "bug"
     20          that the use of m_isValid = false was preventing.
     21       
     22        - Finally, the main change: structure check hoisting looks at the source of the
     23          SetLocals on structure-check-hoistable variables and ensures that the source
     24          is not checked with a conflicting structure. This is O(n^2) but it does not
     25          show up at all in performance tests.
     26       
     27        The first two parts of this change were auxiliary bugs that were revealed by
     28        the structure check hoister doing bad things.
     29
     30        * dfg/DFGAbstractState.cpp:
     31        (JSC::DFG::AbstractState::initialize):
     32        (JSC::DFG::AbstractState::execute):
     33        * dfg/DFGStructureCheckHoistingPhase.cpp:
     34        (JSC::DFG::StructureCheckHoistingPhase::run):
     35
    1362012-09-14  Filip Pizlo  <fpizlo@apple.com>
    237

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

    r128544 r128699  
    148148            AbstractValue value;
    149149            value.setMostSpecific(graph.m_mustHandleValues[i]);
    150             block->valuesAtHead.operand(graph.m_mustHandleValues.operandForIndex(i)).merge(value);
     150            int operand = graph.m_mustHandleValues.operandForIndex(i);
     151            block->valuesAtHead.operand(operand).merge(value);
     152#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
     153            dataLog("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
     154            block->valuesAtHead.operand(operand).dump(WTF::dataFile());
     155            dataLog("\n");
     156#endif
    151157        }
    152158        block->cfaShouldRevisit = true;
    … …  
    12941300            || !isCellSpeculation(value.m_type));
    12951301        value.filter(set);
    1296         // This is likely to be unnecessary, but it's conservative, and that's a good thing.
    1297         // This is trying to avoid situations where the CFA proves that this structure check
    1298         // must fail due to a future structure proof. We have two options at that point. We
    1299         // can either compile all subsequent code as we would otherwise, or we can ensure
    1300         // that the subsequent code is never reachable. The former is correct because the
    1301         // Proof Is Infallible (TM) -- hence even if we don't force the subsequent code to
    1302         // be unreachable, it must be unreachable nonetheless. But imagine what would happen
    1303         // if the proof was borked. In the former case, we'd get really bizarre bugs where
    1304         // we assumed that the structure of this object was known even though it wasn't. In
    1305         // the latter case, we'd have a slight performance pathology because this would be
    1306         // turned into an OSR exit unnecessarily. Which would you rather have?
    1307         if (value.m_currentKnownStructure.isClear()
    1308             || value.m_futurePossibleStructure.isClear())
    1309             m_isValid = false;
    13101302        m_haveStructures = true;
    13111303        break;
    … …  
    13261318        ASSERT(value.isClear() || isCellSpeculation(value.m_type)); // Value could be clear if we've proven must-exit due to a speculation statically known to be bad.
    13271319        value.filter(node.structure());
    1328         // See comment in CheckStructure for why this is here.
    1329         if (value.m_currentKnownStructure.isClear()
    1330             || value.m_futurePossibleStructure.isClear())
    1331             m_isValid = false;
    13321320        m_haveStructures = true;
    13331321        node.setCanExit(true);
    … …  
    13381326    case PhantomPutStructure:
    13391327        node.setCanExit(false);
    1340         clobberStructures(indexInBlock);
    1341         forNode(node.child1()).set(node.structureTransitionData().newStructure);
    1342         m_haveStructures = true;
     1328        if (!forNode(node.child1()).m_currentKnownStructure.isClear()) {
     1329            clobberStructures(indexInBlock);
     1330            forNode(node.child1()).set(node.structureTransitionData().newStructure);
     1331            m_haveStructures = true;
     1332        }
    13431333        break;
    13441334    case GetButterfly:

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

    r128400 r128699  
    6868                    continue;
    6969                switch (node.op()) {
    70                 case CheckStructure: {
     70                case CheckStructure:
     71                case StructureTransitionWatchpoint: {
    7172                    Node& child = m_graph[node.child1()];
    7273                    if (child.op() != GetLocal)
    … …  
    9293                case PutByOffset:
    9394                case PutStructure:
    94                 case StructureTransitionWatchpoint:
    9595                case AllocatePropertyStorage:
    9696                case ReallocatePropertyStorage:
    … …  
    105105                    // Don't count these uses.
    106106                    break;
     107                   
     108                case SetLocal: {
     109                    // Find all uses of the source of the SetLocal. If any of them are a
     110                    // kind of CheckStructure, then we should notice them to ensure that
     111                    // we're not hoisting a check that would contravene checks that are
     112                    // already being performed.
     113                    VariableAccessData* variable = node.variableAccessData();
     114                    if (variable->isCaptured() || variable->structureCheckHoistingFailed())
     115                        break;
     116                    if (!isCellSpeculation(variable->prediction()))
     117                        break;
     118                    NodeIndex source = node.child1().index();
     119                    for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) {
     120                        NodeIndex subNodeIndex = block->at(subIndexInBlock);
     121                        Node& subNode = m_graph[subNodeIndex];
     122                        if (!subNode.shouldGenerate())
     123                            continue;
     124                        switch (subNode.op()) {
     125                        case CheckStructure:
     126                        case StructureTransitionWatchpoint: {
     127                            if (subNode.child1().index() != source)
     128                                break;
     129                           
     130                            noticeStructureCheck(variable, subNode.structureSet());
     131                            break;
     132                        }
     133                        default:
     134                            break;
     135                        }
     136                    }
     137                   
     138                    m_graph.vote(node, VoteOther);
     139                    break;
     140                }
    107141                   
    108142                default:
Note: See TracChangeset for help on using the changeset viewer.