Ignore:
Timestamp:
Mar 5, 2013, 6:27:16 PM (12 years ago)
Author:
[email protected]
Message:

DFG DCE might eliminate checks unsoundly
https://bugs.webkit.org/show_bug.cgi?id=109389

Source/JavaScriptCore:

Reviewed by Oliver Hunt.

This gets rid of all eager reference counting, and does all dead code elimination
in one phase - the DCEPhase. This phase also sets up the node reference counts,
which are then used not just for DCE but also register allocation and stack slot
allocation.

Doing this required a number of surgical changes in places that previously relied
on always having liveness information. For example, the structure check hoisting
phase must now consult whether a VariableAccessData is profitable for unboxing to
make sure that it doesn't try to do hoisting on set SetLocals. The arguments
simplification phase employs its own light-weight liveness analysis. Both phases
previously just used reference counts.

The largest change is that now, dead nodes get turned into Phantoms. Those
Phantoms will retain those child edges that are not proven. This ensures that any
type checks performed by a dead node remain even after the node is killed. On the
other hand, this Phantom conversion means that we need special handling for
SetLocal. I decided to make the four forms of SetLocal explicit:

MovHint(@a, rK): Just indicates that node @a contains the value that would have

now been placed into virtual register rK. Does not actually cause @a to be
stored into rK. This would have previously been a dead SetLocal with @a
being live. MovHints are always dead.


ZombieHint(rK): Indicates that at this point, register rK will contain a dead

value and OSR should put Undefined into it. This would have previously been
a dead SetLocal with @a being dead also. ZombieHints are always dead.


MovHintAndCheck(@a, rK): Identical to MovHint except @a is also type checked,

according to whatever UseKind the edge to @a has. The type check is always a
forward exit. MovHintAndChecks are always live, since they are
NodeMustGenerate. Previously this would have been a dead SetLocal with a
live @a, and the check would have disappeared. This is one of the bugs that
this patch solves.


SetLocal(@a, rK): This still does exactly what it does now, if the SetLocal is

live.


Basically this patch makes it so that dead SetLocals eventually decay to MovHint,
ZombieHint, or MovHintAndCheck depending on the situation. If the child @a is
also dead, then you get a ZombieHint. If the child @a is live but the SetLocal
has a type check and @a's type hasn't been proven to have that type then you get
a MovHintAndCheck. Otherwise you get a MovHint.

This is performance neutral.

  • CMakeLists.txt:
  • GNUmakefile.list.am:
  • JavaScriptCore.xcodeproj/project.pbxproj:
  • Target.pri:
  • dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::executeEffects):
(JSC::DFG::AbstractState::mergeStateAtTail):

  • dfg/DFGArgumentsSimplificationPhase.cpp:

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

  • dfg/DFGBasicBlock.h:

(BasicBlock):

  • dfg/DFGBasicBlockInlines.h:

(DFG):

  • dfg/DFGByteCodeParser.cpp:

(JSC::DFG::ByteCodeParser::addToGraph):
(JSC::DFG::ByteCodeParser::insertPhiNode):
(JSC::DFG::ByteCodeParser::emitFunctionChecks):

  • dfg/DFGCFAPhase.cpp:

(JSC::DFG::CFAPhase::run):

  • dfg/DFGCFGSimplificationPhase.cpp:

(JSC::DFG::CFGSimplificationPhase::run):
(JSC::DFG::CFGSimplificationPhase::keepOperandAlive):

  • dfg/DFGCPSRethreadingPhase.cpp:

(JSC::DFG::CPSRethreadingPhase::run):
(JSC::DFG::CPSRethreadingPhase::addPhiSilently):

  • dfg/DFGCSEPhase.cpp:

(JSC::DFG::CSEPhase::eliminateIrrelevantPhantomChildren):
(JSC::DFG::CSEPhase::setReplacement):
(JSC::DFG::CSEPhase::performNodeCSE):

  • dfg/DFGCommon.cpp:

(WTF::printInternal):
(WTF):

  • dfg/DFGCommon.h:

(WTF):

  • dfg/DFGConstantFoldingPhase.cpp:

(JSC::DFG::ConstantFoldingPhase::foldConstants):
(JSC::DFG::ConstantFoldingPhase::addStructureTransitionCheck):
(JSC::DFG::ConstantFoldingPhase::paintUnreachableCode):

  • dfg/DFGDCEPhase.cpp: Added.

(DFG):
(DCEPhase):
(JSC::DFG::DCEPhase::DCEPhase):
(JSC::DFG::DCEPhase::run):
(JSC::DFG::DCEPhase::findTypeCheckRoot):
(JSC::DFG::DCEPhase::countEdge):
(JSC::DFG::DCEPhase::eliminateIrrelevantPhantomChildren):
(JSC::DFG::performDCE):

  • dfg/DFGDCEPhase.h: Added.

(DFG):

  • dfg/DFGDriver.cpp:

(JSC::DFG::compile):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::checkArray):
(JSC::DFG::FixupPhase::blessArrayOperation):
(JSC::DFG::FixupPhase::fixIntEdge):
(JSC::DFG::FixupPhase::injectInt32ToDoubleNode):
(JSC::DFG::FixupPhase::truncateConstantToInt32):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::Graph):
(JSC::DFG::Graph::dump):
(DFG):

  • dfg/DFGGraph.h:

(JSC::DFG::Graph::changeChild):
(JSC::DFG::Graph::changeEdge):
(JSC::DFG::Graph::compareAndSwap):
(JSC::DFG::Graph::clearAndDerefChild):
(JSC::DFG::Graph::performSubstitution):
(JSC::DFG::Graph::performSubstitutionForEdge):
(Graph):
(JSC::DFG::Graph::substitute):

  • dfg/DFGInsertionSet.h:

(InsertionSet):

  • dfg/DFGNode.h:

(JSC::DFG::Node::Node):
(JSC::DFG::Node::convertToConstant):
(JSC::DFG::Node::convertToGetLocalUnlinked):
(JSC::DFG::Node::containsMovHint):
(Node):
(JSC::DFG::Node::hasVariableAccessData):
(JSC::DFG::Node::willHaveCodeGenOrOSR):

  • dfg/DFGNodeType.h:

(DFG):

  • dfg/DFGPredictionPropagationPhase.cpp:

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

  • dfg/DFGSpeculativeJIT.cpp:

(JSC::DFG::SpeculativeJIT::convertLastOSRExitToForward):
(JSC::DFG::SpeculativeJIT::compileMovHint):
(JSC::DFG::SpeculativeJIT::compileMovHintAndCheck):
(DFG):
(JSC::DFG::SpeculativeJIT::compileInlineStart):
(JSC::DFG::SpeculativeJIT::compile):

  • dfg/DFGSpeculativeJIT.h:

(SpeculativeJIT):

  • dfg/DFGSpeculativeJIT32_64.cpp:

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

  • dfg/DFGSpeculativeJIT64.cpp:

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

  • dfg/DFGStructureCheckHoistingPhase.cpp:

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

  • dfg/DFGValidate.cpp:

(JSC::DFG::Validate::validate):

LayoutTests:

Reviewed by Oliver Hunt.

  • fast/js/dfg-arguments-osr-exit-multiple-blocks-before-exit-expected.txt: Added.
  • fast/js/dfg-arguments-osr-exit-multiple-blocks-before-exit.html: Added.
  • fast/js/dfg-arguments-osr-exit-multiple-blocks-expected.txt: Added.
  • fast/js/dfg-arguments-osr-exit-multiple-blocks.html: Added.
  • fast/js/jsc-test-list:
  • fast/js/script-tests/dfg-arguments-osr-exit-multiple-blocks-before-exit.js: Added.

(baz):
(foo):
(bar):

  • fast/js/script-tests/dfg-arguments-osr-exit-multiple-blocks.js: Added.

(baz):
(foo):
(bar):

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp

    r143654 r144862  
    5757    , m_form(LoadStore)
    5858    , m_unificationState(LocallyUnified)
     59    , m_refCountState(EverythingIsLive)
    5960{
    6061    ASSERT(m_profiledBlock);
     
    313314{
    314315    dataLog("DFG for ", CodeBlockWithJITType(m_codeBlock, JITCode::DFGJIT), ":\n");
    315     dataLog("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "\n");
     316    dataLog("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
    316317   
    317318    Node* lastNode = 0;
     
    347348}
    348349
    349 void Graph::refChildren(Node* op)
    350 {
    351     DFG_NODE_DO_TO_CHILDREN(*this, op, ref);
    352 }
    353 
    354 void Graph::derefChildren(Node* op)
    355 {
    356     DFG_NODE_DO_TO_CHILDREN(*this, op, deref);
    357 }
    358 
    359350void Graph::dethread()
    360351{
     
    389380   
    390381    successor->m_predecessors.append(blockIndex);
    391 }
    392 
    393 void Graph::collectGarbage()
    394 {
    395     SamplingRegion samplingRegion("DFG Garbage Collection");
    396    
    397     // First reset the counts to 0 for all nodes.
    398     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
    399         BasicBlock* block = m_blocks[blockIndex].get();
    400         if (!block)
    401             continue;
    402         for (unsigned indexInBlock = block->size(); indexInBlock--;)
    403             block->at(indexInBlock)->setRefCount(0);
    404         for (unsigned phiIndex = block->phis.size(); phiIndex--;)
    405             block->phis[phiIndex]->setRefCount(0);
    406     }
    407    
    408     // Now find the roots: the nodes that are must-generate. Set their ref counts to
    409     // 1 and put them on the worklist.
    410     Vector<Node*, 128> worklist;
    411     for (BlockIndex blockIndex = 0; blockIndex < m_blocks.size(); ++blockIndex) {
    412         BasicBlock* block = m_blocks[blockIndex].get();
    413         if (!block)
    414             continue;
    415         for (unsigned indexInBlock = block->size(); indexInBlock--;) {
    416             Node* node = block->at(indexInBlock);
    417             if (!(node->flags() & NodeMustGenerate))
    418                 continue;
    419             node->setRefCount(1);
    420             worklist.append(node);
    421         }
    422     }
    423    
    424     while (!worklist.isEmpty()) {
    425         Node* node = worklist.last();
    426         worklist.removeLast();
    427         ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
    428         if (node->flags() & NodeHasVarArgs) {
    429             for (unsigned childIdx = node->firstChild();
    430                 childIdx < node->firstChild() + node->numChildren();
    431                 ++childIdx) {
    432                 if (!m_varArgChildren[childIdx])
    433                     continue;
    434                 Node* childNode = m_varArgChildren[childIdx].node();
    435                 if (childNode->postfixRef())
    436                     continue;
    437                 worklist.append(childNode);
    438             }
    439         } else if (node->child1()) {
    440             if (!node->child1()->postfixRef())
    441                 worklist.append(node->child1().node());
    442             if (node->child2()) {
    443                 if (!node->child2()->postfixRef())
    444                     worklist.append(node->child2().node());
    445                 if (node->child3()) {
    446                     if (!node->child3()->postfixRef())
    447                         worklist.append(node->child3().node());
    448                 }
    449             }
    450         }
    451     }
    452382}
    453383
Note: See TracChangeset for help on using the changeset viewer.