Ignore:
Timestamp:
Dec 29, 2013, 1:50:55 PM (11 years ago)
Author:
[email protected]
Message:

Get rid of DFG forward exiting
​https://bugs.webkit.org/show_bug.cgi?id=125531

Reviewed by Oliver Hunt.

This finally gets rid of forward exiting. Forward exiting was always a fragile concept
since it involved the compiler trying to figure out how to "roll forward" the
execution from some DFG node to the next bytecode index. It was always easy to find
counterexamples where it broke, and it has always served as an obstacle to adding
compiler improvements - the latest being ​http://webkit.org/b/125523, which tried to
make DCE work for more things.

This change finishes the work of removing forward exiting. A lot of forward exiting
was already removed in some other bugs, but SetLocal still did forward exits. SetLocal
is in many ways the hardest to remove, since the forward exiting of SetLocal also
implied that any conversion nodes inserted before the SetLocal would then also be
marked as forward-exiting. Hence SetLocal's forward-exiting made a bunch of other
things also forward-exiting, and this was always a source of weirdo bugs.

SetLocal must be able to exit in case it performs a hoisted type speculation. Nodes
inserted just before SetLocal must also be able to exit - for example type check
hoisting may insert a CheckStructure, or fixup phase may insert something like
Int32ToDouble. But if any of those nodes tried to backward exit, then this could lead
to the reexecution of a side-effecting operation, for example:

a: Call(...)
b: SetLocal(@a, r1)


For a long time it seemed like SetLocal *had* to exit forward because of this. But
this change side-steps the problem by changing the ByteCodeParser to always emit a
kind of "two-phase commit" for stores to local variables. Now when the ByteCodeParser
wishes to store to a local, it first emits a MovHint and then enqueues a SetLocal.
The SetLocal isn't actually emitted until the beginning of the next bytecode
instruction (which the exception of op_enter and op_ret, which emit theirs immediately
since it's always safe to reexecute those bytecode instructions and since deferring
SetLocals would be weird there - op_enter has many SetLocals and op_ret is a set
followed by a jump in case of inlining, so we'd have to emit the SetLocal "after" the
jump and that would be awkward). This means that the above IR snippet would look
something like:

a: Call(..., bc#42)
b: MovHint(@a, r1, bc#42)
c: SetLocal(@a, r1, bc#47)


Where the SetLocal exits "backwards" but appears at the beginning of the next bytecode
instruction. This means that by the time we get to that SetLocal, the OSR exit
analysis already knows that r1 is associated with @a, and it means that the SetLocal
or anything hoisted above it can exit backwards as normal.

This change also means that the "forward rewiring" can be killed. Previously, we might
have inserted a conversion node on SetLocal and then the SetLocal died (i.e. turned
into a MovHint) and the conversion node either died completely or had its lifetime
truncated to be less than the actual value's bytecode lifetime. This no longer happens
since conversion nodes are only inserted at SetLocals.

More precisely, this change introduces two laws that we were basically already
following anyway:

1) A MovHint's child should never be changed except if all other uses of that child

are also replaced. Specifically, this prohibits insertion of conversion nodes at
MovHints.


2) Anytime any child is replaced with something else, and all other uses aren't also

replaced, we must insert a Phantom use of the original child.

This is a slight compile-time regression but has no effect on code-gen. It unlocks a
bunch of optimization opportunities so I think it's worth it.

  • bytecode/CodeBlock.cpp:

(JSC::CodeBlock::dumpAssumingJITType):

  • bytecode/CodeBlock.h:

(JSC::CodeBlock::instructionCount):

  • dfg/DFGAbstractInterpreterInlines.h:

(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):

  • dfg/DFGArgumentsSimplificationPhase.cpp:

(JSC::DFG::ArgumentsSimplificationPhase::run):

  • dfg/DFGArrayifySlowPathGenerator.h:

(JSC::DFG::ArrayifySlowPathGenerator::ArrayifySlowPathGenerator):

  • dfg/DFGBackwardsPropagationPhase.cpp:

(JSC::DFG::BackwardsPropagationPhase::propagate):

  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::setDirect):
(JSC::DFG::ByteCodeParser::DelayedSetLocal::DelayedSetLocal):
(JSC::DFG::ByteCodeParser::DelayedSetLocal::execute):
(JSC::DFG::ByteCodeParser::handleInlining):
(JSC::DFG::ByteCodeParser::parseBlock):

  • dfg/DFGCSEPhase.cpp:

(JSC::DFG::CSEPhase::eliminate):

  • dfg/DFGClobberize.h:

(JSC::DFG::clobberize):

  • dfg/DFGCommon.h:
  • dfg/DFGConstantFoldingPhase.cpp:

(JSC::DFG::ConstantFoldingPhase::foldConstants):

  • dfg/DFGDCEPhase.cpp:

(JSC::DFG::DCEPhase::run):
(JSC::DFG::DCEPhase::fixupBlock):
(JSC::DFG::DCEPhase::cleanVariables):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::fixEdge):
(JSC::DFG::FixupPhase::injectInt32ToDoubleNode):

  • dfg/DFGLICMPhase.cpp:

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

  • dfg/DFGMinifiedNode.cpp:

(JSC::DFG::MinifiedNode::fromNode):

  • dfg/DFGMinifiedNode.h:

(JSC::DFG::belongsInMinifiedGraph):
(JSC::DFG::MinifiedNode::constantNumber):
(JSC::DFG::MinifiedNode::weakConstant):

  • dfg/DFGNode.cpp:

(JSC::DFG::Node::hasVariableAccessData):

  • dfg/DFGNode.h:

(JSC::DFG::Node::convertToPhantom):
(JSC::DFG::Node::convertToPhantomUnchecked):
(JSC::DFG::Node::convertToIdentity):
(JSC::DFG::Node::containsMovHint):
(JSC::DFG::Node::hasUnlinkedLocal):
(JSC::DFG::Node::willHaveCodeGenOrOSR):

  • dfg/DFGNodeFlags.cpp:

(JSC::DFG::dumpNodeFlags):

  • dfg/DFGNodeFlags.h:
  • dfg/DFGNodeType.h:
  • dfg/DFGOSRAvailabilityAnalysisPhase.cpp:

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

  • dfg/DFGOSREntrypointCreationPhase.cpp:

(JSC::DFG::OSREntrypointCreationPhase::run):

  • dfg/DFGOSRExit.cpp:
  • dfg/DFGOSRExit.h:
  • dfg/DFGOSRExitBase.cpp:
  • dfg/DFGOSRExitBase.h:

(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSite):

  • dfg/DFGPredictionPropagationPhase.cpp:

(JSC::DFG::PredictionPropagationPhase::propagate):
(JSC::DFG::PredictionPropagationPhase::doDoubleVoting):

  • dfg/DFGSSAConversionPhase.cpp:

(JSC::DFG::SSAConversionPhase::run):

  • dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::speculationCheck):
(JSC::DFG::SpeculativeJIT::emitInvalidationPoint):
(JSC::DFG::SpeculativeJIT::typeCheck):
(JSC::DFG::SpeculativeJIT::compileMovHint):
(JSC::DFG::SpeculativeJIT::compileCurrentBlock):
(JSC::DFG::SpeculativeJIT::checkArgumentTypes):
(JSC::DFG::SpeculativeJIT::compileInt32ToDouble):

  • dfg/DFGSpeculativeJIT.h:

(JSC::DFG::SpeculativeJIT::detectPeepHoleBranch):
(JSC::DFG::SpeculativeJIT::needsTypeCheck):

  • dfg/DFGSpeculativeJIT32_64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT64.cpp:

(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGTypeCheckHoistingPhase.cpp:

(JSC::DFG::TypeCheckHoistingPhase::run):
(JSC::DFG::TypeCheckHoistingPhase::identifyRedundantStructureChecks):
(JSC::DFG::TypeCheckHoistingPhase::identifyRedundantArrayChecks):

  • dfg/DFGValidate.cpp:

(JSC::DFG::Validate::validateCPS):

  • dfg/DFGVariableAccessData.h:

(JSC::DFG::VariableAccessData::VariableAccessData):

  • dfg/DFGVariableEventStream.cpp:

(JSC::DFG::VariableEventStream::reconstruct):

  • ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

  • ftl/FTLLowerDFGToLLVM.cpp:

(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::compileGetArgument):
(JSC::FTL::LowerDFGToLLVM::compileSetLocal):
(JSC::FTL::LowerDFGToLLVM::compileMovHint):
(JSC::FTL::LowerDFGToLLVM::compileZombieHint):
(JSC::FTL::LowerDFGToLLVM::compileInt32ToDouble):
(JSC::FTL::LowerDFGToLLVM::speculate):
(JSC::FTL::LowerDFGToLLVM::typeCheck):
(JSC::FTL::LowerDFGToLLVM::appendTypeCheck):
(JSC::FTL::LowerDFGToLLVM::appendOSRExit):
(JSC::FTL::LowerDFGToLLVM::emitOSRExitCall):

  • ftl/FTLOSRExit.cpp:
  • ftl/FTLOSRExit.h:
  • tests/stress/dead-int32-to-double.js: Added.

(foo):

  • tests/stress/dead-uint32-to-number.js: Added.

(foo):

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp

    r161072 r161126  
    229229        bool shouldExecuteEffects = m_interpreter.startExecuting(m_node);
    230230       
    231         m_direction = (m_node->flags() & NodeExitsForward) ? ForwardSpeculation : BackwardSpeculation;
    232        
    233231        switch (m_node->op()) {
    234232        case Upsilon:
    … …  
    260258        case ZombieHint:
    261259            compileZombieHint();
    262             break;
    263         case MovHintAndCheck:
    264             compileMovHintAndCheck();
    265260            break;
    266261        case Phantom:
    … …  
    658653        switch (useKindFor(variable->flushFormat())) {
    659654        case Int32Use:
    660             speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotInt32(jsValue));
     655            speculate(BadType, jsValueValue(jsValue), m_node, isNotInt32(jsValue));
    661656            setInt32(unboxInt32(jsValue));
    662657            break;
    663658        case CellUse:
    664             speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotCell(jsValue));
     659            speculate(BadType, jsValueValue(jsValue), m_node, isNotCell(jsValue));
    665660            setJSValue(jsValue);
    666661            break;
    667662        case BooleanUse:
    668             speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotBoolean(jsValue));
     663            speculate(BadType, jsValueValue(jsValue), m_node, isNotBoolean(jsValue));
    669664            setBoolean(unboxBoolean(jsValue));
    670665            break;
    … …  
    702697    void compileSetLocal()
    703698    {
    704         observeMovHint(m_node);
    705        
    706699        VariableAccessData* variable = m_node->variableAccessData();
    707700        switch (variable->flushFormat()) {
    … …  
    754747    void compileMovHint()
    755748    {
    756         observeMovHint(m_node);
     749        ASSERT(m_node->containsMovHint());
     750        ASSERT(m_node->op() != ZombieHint);
     751       
     752        VirtualRegister operand = m_node->unlinkedLocal();
     753        m_availability.operand(operand) = Availability(m_node->child1().node());
    757754    }
    758755   
    759756    void compileZombieHint()
    760757    {
    761         VariableAccessData* data = m_node->variableAccessData();
    762         m_availability.operand(data->local()) = Availability::unavailable();
    763     }
    764    
    765     void compileMovHintAndCheck()
    766     {
    767         observeMovHint(m_node);
    768         speculate(m_node->child1());
     758        m_availability.operand(m_node->unlinkedLocal()) = Availability::unavailable();
    769759    }
    770760   
    … …  
    11781168    void compileInt32ToDouble()
    11791169    {
    1180         if (!m_interpreter.needsTypeCheck(m_node->child1(), SpecFullNumber)
    1181             || m_node->speculationDirection() == BackwardSpeculation) {
    1182             setDouble(lowDouble(m_node->child1()));
    1183             return;
    1184         }
    1185        
    1186         LValue boxedValue = lowJSValue(m_node->child1(), ManualOperandSpeculation);
    1187        
    1188         LBasicBlock intCase = FTL_NEW_BLOCK(m_out, ("Double unboxing int case"));
    1189         LBasicBlock doubleCase = FTL_NEW_BLOCK(m_out, ("Double unboxing double case"));
    1190         LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("Double unboxing continuation"));
    1191        
    1192         m_out.branch(isNotInt32(boxedValue), doubleCase, intCase);
    1193        
    1194         LBasicBlock lastNext = m_out.appendTo(intCase, doubleCase);
    1195        
    1196         ValueFromBlock intToDouble = m_out.anchor(
    1197             m_out.intToDouble(unboxInt32(boxedValue)));
    1198         m_out.jump(continuation);
    1199        
    1200         m_out.appendTo(doubleCase, continuation);
    1201 
    1202         forwardTypeCheck(
    1203             jsValueValue(boxedValue), m_node->child1(), SpecFullNumber,
    1204             isCellOrMisc(boxedValue), jsValueValue(boxedValue));
    1205        
    1206         ValueFromBlock unboxedDouble = m_out.anchor(unboxDouble(boxedValue));
    1207         m_out.jump(continuation);
    1208        
    1209         m_out.appendTo(continuation, lastNext);
    1210        
    1211         LValue result = m_out.phi(m_out.doubleType, intToDouble, unboxedDouble);
    1212        
    1213         setDouble(result);
     1170        setDouble(lowDouble(m_node->child1()));
    12141171    }
    12151172   
    … …  
    31973154    }
    31983155   
    3199     void speculateBackward(
    3200         ExitKind kind, FormattedValue lowValue, Node* highValue, LValue failCondition)
    3201     {
    3202         appendOSRExit(
    3203             kind, lowValue, highValue, failCondition, BackwardSpeculation, FormattedValue());
    3204     }
    3205    
    3206     void speculateForward(
    3207         ExitKind kind, FormattedValue lowValue, Node* highValue, LValue failCondition,
    3208         const FormattedValue& recovery)
    3209     {
    3210         appendOSRExit(
    3211             kind, lowValue, highValue, failCondition, ForwardSpeculation, recovery);
    3212     }
    3213    
    32143156    void speculate(
    32153157        ExitKind kind, FormattedValue lowValue, Node* highValue, LValue failCondition)
    32163158    {
    3217         appendOSRExit(
    3218             kind, lowValue, highValue, failCondition, m_direction, FormattedValue());
     3159        appendOSRExit(kind, lowValue, highValue, failCondition);
    32193160    }
    32203161   
    … …  
    32223163    {
    32233164        speculate(kind, noValue(), 0, m_out.booleanTrue);
    3224     }
    3225    
    3226     void backwardTypeCheck(
    3227         FormattedValue lowValue, Edge highValue, SpeculatedType typesPassedThrough,
    3228         LValue failCondition)
    3229     {
    3230         appendTypeCheck(
    3231             lowValue, highValue, typesPassedThrough, failCondition, BackwardSpeculation,
    3232             FormattedValue());
    3233     }
    3234    
    3235     void forwardTypeCheck(
    3236         FormattedValue lowValue, Edge highValue, SpeculatedType typesPassedThrough,
    3237         LValue failCondition, const FormattedValue& recovery)
    3238     {
    3239         appendTypeCheck(
    3240             lowValue, highValue, typesPassedThrough, failCondition, ForwardSpeculation,
    3241             recovery);
    32423165    }
    32433166   
    … …  
    32463169        LValue failCondition)
    32473170    {
    3248         appendTypeCheck(
    3249             lowValue, highValue, typesPassedThrough, failCondition, m_direction,
    3250             FormattedValue());
     3171        appendTypeCheck(lowValue, highValue, typesPassedThrough, failCondition);
    32513172    }
    32523173   
    32533174    void appendTypeCheck(
    32543175        FormattedValue lowValue, Edge highValue, SpeculatedType typesPassedThrough,
    3255         LValue failCondition, SpeculationDirection direction, FormattedValue recovery)
     3176        LValue failCondition)
    32563177    {
    32573178        if (!m_interpreter.needsTypeCheck(highValue, typesPassedThrough))
    32583179            return;
    32593180        ASSERT(mayHaveTypeCheck(highValue.useKind()));
    3260         appendOSRExit(BadType, lowValue, highValue.node(), failCondition, direction, recovery);
     3181        appendOSRExit(BadType, lowValue, highValue.node(), failCondition);
    32613182        m_interpreter.filter(highValue, typesPassedThrough);
    32623183    }
    … …  
    40934014   
    40944015    void appendOSRExit(
    4095         ExitKind kind, FormattedValue lowValue, Node* highValue, LValue failCondition,
    4096         SpeculationDirection direction, FormattedValue recovery)
     4016        ExitKind kind, FormattedValue lowValue, Node* highValue, LValue failCondition)
    40974017    {
    40984018        if (verboseCompilationEnabled())
    … …  
    41194039        lastNext = m_out.appendTo(failCase, continuation);
    41204040       
    4121         emitOSRExitCall(exit, lowValue, direction, recovery);
     4041        emitOSRExitCall(exit, lowValue);
    41224042       
    41234043        m_out.unreachable();
    … …  
    41264046    }
    41274047   
    4128     void emitOSRExitCall(
    4129         OSRExit& exit, FormattedValue lowValue, SpeculationDirection direction,
    4130         FormattedValue recovery)
     4048    void emitOSRExitCall(OSRExit& exit, FormattedValue lowValue)
    41314049    {
    41324050        ExitArgumentList arguments;
    … …  
    41344052        CodeOrigin codeOrigin = exit.m_codeOrigin;
    41354053       
    4136         if (direction == BackwardSpeculation)
    4137             buildExitArguments(exit, arguments, lowValue, codeOrigin);
    4138         else {
    4139             ASSERT(direction == ForwardSpeculation);
    4140             if (!recovery) {
    4141                 for (unsigned nodeIndex = m_nodeIndex; nodeIndex < m_highBlock->size(); ++nodeIndex) {
    4142                     Node* node = m_highBlock->at(nodeIndex);
    4143                     if (node->codeOriginForExitTarget == codeOrigin)
    4144                         continue;
    4145                     codeOrigin = node->codeOriginForExitTarget;
    4146                     break;
    4147                 }
    4148             }
    4149            
    4150             buildExitArguments(exit, arguments, lowValue, codeOrigin);
    4151             exit.convertToForward(m_highBlock, m_node, m_nodeIndex, recovery, arguments);
    4152         }
     4054        buildExitArguments(exit, arguments, lowValue, codeOrigin);
    41534055       
    41544056        callStackmap(exit, arguments);
    … …  
    43104212    }
    43114213   
    4312     void observeMovHint(Node* node)
    4313     {
    4314         ASSERT(node->containsMovHint());
    4315         ASSERT(node->op() != ZombieHint);
    4316        
    4317         VirtualRegister operand = node->local();
    4318        
    4319         m_availability.operand(operand) = Availability(node->child1().node());
    4320     }
    4321    
    43224214    void setInt32(Node* node, LValue value)
    43234215    {
    … …  
    44904382    unsigned m_nodeIndex;
    44914383    Node* m_node;
    4492     SpeculationDirection m_direction;
    44934384   
    44944385    uint32_t m_stackmapIDs;
Note: See TracChangeset for help on using the changeset viewer.