Ignore:
Timestamp:
Jul 24, 2013, 9:04:45 PM (12 years ago)
Author:
[email protected]
Message:

fourthTier: DFG should have an SSA form for use by FTL
​https://bugs.webkit.org/show_bug.cgi?id=118338

Source/JavaScriptCore:

Reviewed by Mark Hahnenberg.

Adds an SSA form to the DFG. We can convert ThreadedCPS form into SSA form
after breaking critical edges. The conversion algorithm follows Aycock and
Horspool, and the SSA form itself follows something I've done before, where
instead of having Phi functions specify input nodes corresponding to block
predecessors, we instead have Upsilon functions in the predecessors that
specify which value in that block goes into which subsequent Phi. Upsilons
don't have to dominate Phis (usually they don't) and they correspond to a
non-SSA "mov" into the Phi's "variable". This gives all of the good
properties of SSA, while ensuring that a bunch of CFG transformations don't
have to be SSA-aware.

So far the only DFG phases that are SSA-aware are DCE and CFA. CFG
simplification is probably SSA-aware by default, though I haven't tried it.
Constant folding probably needs a few tweaks, but is likely ready. Ditto
for CSE, though it's not clear that we'd want to use block-local CSE when
we could be doing GVN.

Currently only the FTL can generate code from the SSA form, and there is no
way to convert from SSA to ThreadedCPS or LoadStore. There probably will
never be such a capability.

In order to handle OSR exit state in the SSA, we place MovHints at Phi
points. Other than that, you can reconstruct state-at-exit by forward
propagating MovHints. Note that MovHint is the new SetLocal in SSA.
SetLocal and GetLocal only survive into SSA if they are on captured
variables, or in the case of flushes. A "live SetLocal" will be
NodeMustGenerate and will always correspond to a flush. Computing the
state-at-exit requires running SSA liveness analysis, OSR availability
analysis, and flush liveness analysis. The FTL runs all of these prior to
generating code. While OSR exit continues to be tricky, much of the logic
is now factored into separate phases and the backend has to do less work
to reason about what happened outside of the basic block that is being
lowered.

Conversion from DFG SSA to LLVM SSA is done by ensuring that we generate
code in depth-first order, thus guaranteeing that a node will always be
lowered (and hence have a LValue) before any of the blocks dominated by
that node's block have code generated. For Upsilon/Phi, we just use
alloca's. We could do something more clever there, but it's probably not
worth it, at least not now.

Finally, while the SSA form is currently only being converted to LLVM IR,
there is nothing that prevents us from considering other backends in the
future - with the caveat that this form is designed to be first lowered to
a lower-level SSA before actual machine code generation commences. So we
ought to either use LLVM (the intended path) or we will have to write our
own SSA low-level backend.

This runs all of the code that the FTL was known to run previously. No
change in performance for now. But it does open some exciting
possibilities!

(JSC::OperandValueTraits::dump):
(JSC::Operands::fill):
(Operands):
(JSC::Operands::clear):
(JSC::Operands::operator==):

  • dfg/DFGAbstractState.cpp:

(JSC::DFG::AbstractState::beginBasicBlock):
(JSC::DFG::setLiveValues):
(DFG):
(JSC::DFG::AbstractState::initialize):
(JSC::DFG::AbstractState::endBasicBlock):
(JSC::DFG::AbstractState::executeEffects):
(JSC::DFG::AbstractState::mergeStateAtTail):
(JSC::DFG::AbstractState::merge):

  • dfg/DFGAbstractState.h:

(AbstractState):

  • dfg/DFGAdjacencyList.h:

(JSC::DFG::AdjacencyList::justOneChild):
(AdjacencyList):

  • dfg/DFGBasicBlock.cpp: Added.

(DFG):
(JSC::DFG::BasicBlock::BasicBlock):
(JSC::DFG::BasicBlock::~BasicBlock):
(JSC::DFG::BasicBlock::ensureLocals):
(JSC::DFG::BasicBlock::isInPhis):
(JSC::DFG::BasicBlock::isInBlock):
(JSC::DFG::BasicBlock::removePredecessor):
(JSC::DFG::BasicBlock::replacePredecessor):
(JSC::DFG::BasicBlock::dump):
(JSC::DFG::BasicBlock::SSAData::SSAData):
(JSC::DFG::BasicBlock::SSAData::~SSAData):

  • dfg/DFGBasicBlock.h:

(BasicBlock):
(JSC::DFG::BasicBlock::operator[]):
(JSC::DFG::BasicBlock::successor):
(JSC::DFG::BasicBlock::successorForCondition):
(SSAData):

  • dfg/DFGBasicBlockInlines.h:

(DFG):

  • dfg/DFGBlockInsertionSet.cpp: Added.

(DFG):
(JSC::DFG::BlockInsertionSet::BlockInsertionSet):
(JSC::DFG::BlockInsertionSet::~BlockInsertionSet):
(JSC::DFG::BlockInsertionSet::insert):
(JSC::DFG::BlockInsertionSet::insertBefore):
(JSC::DFG::BlockInsertionSet::execute):

  • dfg/DFGBlockInsertionSet.h: Added.

(DFG):
(BlockInsertionSet):

  • dfg/DFGCFAPhase.cpp:

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

  • dfg/DFGCFGSimplificationPhase.cpp:
  • dfg/DFGCPSRethreadingPhase.cpp:

(JSC::DFG::CPSRethreadingPhase::canonicalizeLocalsInBlock):

  • dfg/DFGCommon.cpp:

(WTF::printInternal):

  • dfg/DFGCommon.h:

(JSC::DFG::doesKill):
(DFG):
(JSC::DFG::killStatusForDoesKill):

  • dfg/DFGConstantFoldingPhase.cpp:

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

  • dfg/DFGCriticalEdgeBreakingPhase.cpp: Added.

(DFG):
(CriticalEdgeBreakingPhase):
(JSC::DFG::CriticalEdgeBreakingPhase::CriticalEdgeBreakingPhase):
(JSC::DFG::CriticalEdgeBreakingPhase::run):
(JSC::DFG::CriticalEdgeBreakingPhase::breakCriticalEdge):
(JSC::DFG::performCriticalEdgeBreaking):

  • dfg/DFGCriticalEdgeBreakingPhase.h: Added.

(DFG):

  • dfg/DFGDCEPhase.cpp:

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

  • dfg/DFGDriver.cpp:

(JSC::DFG::compile):

  • dfg/DFGEdge.cpp:

(JSC::DFG::Edge::dump):

  • dfg/DFGEdge.h:

(JSC::DFG::Edge::Edge):
(JSC::DFG::Edge::setNode):
(JSC::DFG::Edge::useKindUnchecked):
(JSC::DFG::Edge::setUseKind):
(JSC::DFG::Edge::setProofStatus):
(JSC::DFG::Edge::willNotHaveCheck):
(JSC::DFG::Edge::willHaveCheck):
(Edge):
(JSC::DFG::Edge::killStatusUnchecked):
(JSC::DFG::Edge::killStatus):
(JSC::DFG::Edge::setKillStatus):
(JSC::DFG::Edge::doesKill):
(JSC::DFG::Edge::doesNotKill):
(JSC::DFG::Edge::shift):
(JSC::DFG::Edge::makeWord):

  • dfg/DFGFixupPhase.cpp:

(JSC::DFG::FixupPhase::fixupNode):

  • dfg/DFGFlushFormat.cpp: Added.

(WTF):
(WTF::printInternal):

  • dfg/DFGFlushFormat.h: Added.

(DFG):
(JSC::DFG::resultFor):
(JSC::DFG::useKindFor):
(WTF):

  • dfg/DFGFlushLivenessAnalysisPhase.cpp: Added.

(DFG):
(FlushLivenessAnalysisPhase):
(JSC::DFG::FlushLivenessAnalysisPhase::FlushLivenessAnalysisPhase):
(JSC::DFG::FlushLivenessAnalysisPhase::run):
(JSC::DFG::FlushLivenessAnalysisPhase::process):
(JSC::DFG::FlushLivenessAnalysisPhase::setForNode):
(JSC::DFG::FlushLivenessAnalysisPhase::flushFormat):
(JSC::DFG::performFlushLivenessAnalysis):

  • dfg/DFGFlushLivenessAnalysisPhase.h: Added.

(DFG):

  • dfg/DFGGraph.cpp:

(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::dumpBlockHeader):
(DFG):
(JSC::DFG::Graph::addForDepthFirstSort):
(JSC::DFG::Graph::getBlocksInDepthFirstOrder):

  • dfg/DFGGraph.h:

(JSC::DFG::Graph::convertToConstant):
(JSC::DFG::Graph::valueProfileFor):
(Graph):

  • dfg/DFGInsertionSet.h:

(DFG):
(JSC::DFG::InsertionSet::execute):

  • dfg/DFGLivenessAnalysisPhase.cpp: Added.

(DFG):
(LivenessAnalysisPhase):
(JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
(JSC::DFG::LivenessAnalysisPhase::run):
(JSC::DFG::LivenessAnalysisPhase::process):
(JSC::DFG::LivenessAnalysisPhase::addChildUse):
(JSC::DFG::performLivenessAnalysis):

  • dfg/DFGLivenessAnalysisPhase.h: Added.

(DFG):

  • dfg/DFGNode.cpp:

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

  • dfg/DFGNode.h:

(DFG):
(Node):
(JSC::DFG::Node::hasLocal):
(JSC::DFG::Node::variableAccessData):
(JSC::DFG::Node::hasPhi):
(JSC::DFG::Node::phi):
(JSC::DFG::Node::takenBlock):
(JSC::DFG::Node::notTakenBlock):
(JSC::DFG::Node::successor):
(JSC::DFG::Node::successorForCondition):
(JSC::DFG::nodeComparator):
(JSC::DFG::nodeListDump):
(JSC::DFG::nodeMapDump):

  • dfg/DFGNodeFlags.cpp:

(JSC::DFG::dumpNodeFlags):

  • dfg/DFGNodeType.h:

(DFG):

  • dfg/DFGOSRAvailabilityAnalysisPhase.cpp: Added.

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

  • dfg/DFGOSRAvailabilityAnalysisPhase.h: Added.

(DFG):

  • dfg/DFGPlan.cpp:

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

  • dfg/DFGPredictionInjectionPhase.cpp:

(JSC::DFG::PredictionInjectionPhase::run):

  • dfg/DFGPredictionPropagationPhase.cpp:

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

  • dfg/DFGSSAConversionPhase.cpp: Added.

(DFG):
(SSAConversionPhase):
(JSC::DFG::SSAConversionPhase::SSAConversionPhase):
(JSC::DFG::SSAConversionPhase::run):
(JSC::DFG::SSAConversionPhase::forwardPhiChildren):
(JSC::DFG::SSAConversionPhase::forwardPhi):
(JSC::DFG::SSAConversionPhase::forwardPhiEdge):
(JSC::DFG::SSAConversionPhase::deduplicateChildren):
(JSC::DFG::SSAConversionPhase::addFlushedLocalOp):
(JSC::DFG::SSAConversionPhase::addFlushedLocalEdge):
(JSC::DFG::performSSAConversion):

  • dfg/DFGSSAConversionPhase.h: Added.

(DFG):

  • dfg/DFGSpeculativeJIT32_64.cpp:

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

  • dfg/DFGSpeculativeJIT64.cpp:

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

  • dfg/DFGValidate.cpp:

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

  • dfg/DFGVariableAccessData.h:

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

  • ftl/FTLCapabilities.cpp:

(JSC::FTL::canCompile):

  • ftl/FTLLowerDFGToLLVM.cpp:

(JSC::FTL::LowerDFGToLLVM::LowerDFGToLLVM):
(JSC::FTL::LowerDFGToLLVM::lower):
(JSC::FTL::LowerDFGToLLVM::createPhiVariables):
(JSC::FTL::LowerDFGToLLVM::compileBlock):
(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::compileUpsilon):
(LowerDFGToLLVM):
(JSC::FTL::LowerDFGToLLVM::compilePhi):
(JSC::FTL::LowerDFGToLLVM::compileJSConstant):
(JSC::FTL::LowerDFGToLLVM::compileWeakJSConstant):
(JSC::FTL::LowerDFGToLLVM::compileGetArgument):
(JSC::FTL::LowerDFGToLLVM::compileGetLocal):
(JSC::FTL::LowerDFGToLLVM::compileSetLocal):
(JSC::FTL::LowerDFGToLLVM::compileAdd):
(JSC::FTL::LowerDFGToLLVM::compileArithSub):
(JSC::FTL::LowerDFGToLLVM::compileArithMul):
(JSC::FTL::LowerDFGToLLVM::compileArithDiv):
(JSC::FTL::LowerDFGToLLVM::compileArithMod):
(JSC::FTL::LowerDFGToLLVM::compileArithMinOrMax):
(JSC::FTL::LowerDFGToLLVM::compileArithAbs):
(JSC::FTL::LowerDFGToLLVM::compileArithNegate):
(JSC::FTL::LowerDFGToLLVM::compileBitAnd):
(JSC::FTL::LowerDFGToLLVM::compileBitOr):
(JSC::FTL::LowerDFGToLLVM::compileBitXor):
(JSC::FTL::LowerDFGToLLVM::compileBitRShift):
(JSC::FTL::LowerDFGToLLVM::compileBitLShift):
(JSC::FTL::LowerDFGToLLVM::compileBitURShift):
(JSC::FTL::LowerDFGToLLVM::compileUInt32ToNumber):
(JSC::FTL::LowerDFGToLLVM::compileInt32ToDouble):
(JSC::FTL::LowerDFGToLLVM::compileGetButterfly):
(JSC::FTL::LowerDFGToLLVM::compileGetArrayLength):
(JSC::FTL::LowerDFGToLLVM::compileGetByVal):
(JSC::FTL::LowerDFGToLLVM::compileGetByOffset):
(JSC::FTL::LowerDFGToLLVM::compileGetGlobalVar):
(JSC::FTL::LowerDFGToLLVM::compileCompareEqConstant):
(JSC::FTL::LowerDFGToLLVM::compileCompareStrictEq):
(JSC::FTL::LowerDFGToLLVM::compileCompareStrictEqConstant):
(JSC::FTL::LowerDFGToLLVM::compileCompareLess):
(JSC::FTL::LowerDFGToLLVM::compileCompareLessEq):
(JSC::FTL::LowerDFGToLLVM::compileCompareGreater):
(JSC::FTL::LowerDFGToLLVM::compileCompareGreaterEq):
(JSC::FTL::LowerDFGToLLVM::compileLogicalNot):
(JSC::FTL::LowerDFGToLLVM::speculateBackward):
(JSC::FTL::LowerDFGToLLVM::lowInt32):
(JSC::FTL::LowerDFGToLLVM::lowCell):
(JSC::FTL::LowerDFGToLLVM::lowBoolean):
(JSC::FTL::LowerDFGToLLVM::lowDouble):
(JSC::FTL::LowerDFGToLLVM::lowJSValue):
(JSC::FTL::LowerDFGToLLVM::lowStorage):
(JSC::FTL::LowerDFGToLLVM::speculate):
(JSC::FTL::LowerDFGToLLVM::speculateBoolean):
(JSC::FTL::LowerDFGToLLVM::isLive):
(JSC::FTL::LowerDFGToLLVM::use):
(JSC::FTL::LowerDFGToLLVM::initializeOSRExitStateForBlock):
(JSC::FTL::LowerDFGToLLVM::appendOSRExit):
(JSC::FTL::LowerDFGToLLVM::emitOSRExitCall):
(JSC::FTL::LowerDFGToLLVM::addExitArgumentForNode):
(JSC::FTL::LowerDFGToLLVM::linkOSRExitsAndCompleteInitializationBlocks):
(JSC::FTL::LowerDFGToLLVM::setInt32):
(JSC::FTL::LowerDFGToLLVM::setJSValue):
(JSC::FTL::LowerDFGToLLVM::setBoolean):
(JSC::FTL::LowerDFGToLLVM::setStorage):
(JSC::FTL::LowerDFGToLLVM::setDouble):
(JSC::FTL::LowerDFGToLLVM::isValid):

  • ftl/FTLLoweredNodeValue.h: Added.

(FTL):
(LoweredNodeValue):
(JSC::FTL::LoweredNodeValue::LoweredNodeValue):
(JSC::FTL::LoweredNodeValue::isSet):
(JSC::FTL::LoweredNodeValue::operator!):
(JSC::FTL::LoweredNodeValue::value):
(JSC::FTL::LoweredNodeValue::block):

  • ftl/FTLValueFromBlock.h:

(JSC::FTL::ValueFromBlock::ValueFromBlock):
(ValueFromBlock):

  • ftl/FTLValueSource.cpp:

(JSC::FTL::ValueSource::dump):

  • ftl/FTLValueSource.h:

Source/WTF:

Reviewed by Mark Hahnenberg.

  • Extend variadicity of PrintStream and dataLog.
  • Give HashSet the ability to add a span of things.
  • Give HashSet the ability to == another HashSet.
  • Note FIXME's in HashTable concerning copying performance, that affects the way that the DFG now uses HashSets and HashMaps.
  • Factor out the bulk-insertion logic of JSC::DFG::InsertionSet into WTF::Insertion, so that it can be used in more places.
  • Create a dumper for lists and maps.
  • WTF.xcodeproj/project.pbxproj:
  • wtf/DataLog.h:

(WTF):
(WTF::dataLog):

  • wtf/HashSet.h:

(HashSet):
(WTF):
(WTF::::add):
(WTF::=):

  • wtf/HashTable.h:

(WTF::::HashTable):
(WTF::=):

  • wtf/Insertion.h: Added.

(WTF):
(Insertion):
(WTF::Insertion::Insertion):
(WTF::Insertion::index):
(WTF::Insertion::element):
(WTF::Insertion::operator<):
(WTF::executeInsertions):

  • wtf/ListDump.h: Added.

(WTF):
(ListDump):
(WTF::ListDump::ListDump):
(WTF::ListDump::dump):
(MapDump):
(WTF::MapDump::MapDump):
(WTF::MapDump::dump):
(WTF::listDump):
(WTF::sortedListDump):
(WTF::lessThan):
(WTF::mapDump):
(WTF::sortedMapDump):

  • wtf/PrintStream.h:

(PrintStream):
(WTF::PrintStream::print):

Conflicts:

Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r153267 r153274  
    4646    bool run()
    4747    {
     48        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
     49       
    4850        // First reset the counts to 0 for all nodes.
    4951        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
    … …  
    7678       
    7779        while (!m_worklist.isEmpty()) {
    78             Node* node = m_worklist.last();
    79             m_worklist.removeLast();
    80             ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
    81             DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
     80            while (!m_worklist.isEmpty()) {
     81                Node* node = m_worklist.last();
     82                m_worklist.removeLast();
     83                ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
     84                DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
     85            }
     86           
     87            if (m_graph.m_form == SSA) {
     88                // Find Phi->Upsilon edges, which are represented as meta-data in the
     89                // Upsilon.
     90                for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
     91                    BasicBlock* block = m_graph.block(blockIndex);
     92                    if (!block)
     93                        continue;
     94                    for (unsigned nodeIndex = block->size(); nodeIndex--;) {
     95                        Node* node = block->at(nodeIndex);
     96                        if (node->op() != Upsilon)
     97                            continue;
     98                        if (node->shouldGenerate())
     99                            continue;
     100                        if (node->phi()->shouldGenerate())
     101                            countNode(node);
     102                    }
     103                }
     104            }
    82105        }
    83106       
    … …  
    95118               
    96119                switch (node->op()) {
    97                 case SetLocal: {
    98                     if (node->child1().isProved() || node->child1().useKind() == UntypedUse) {
     120                case SetLocal:
     121                case MovHint: {
     122                    ASSERT((node->op() == SetLocal) == (m_graph.m_form == ThreadedCPS));
     123                    if (node->child1().willNotHaveCheck()) {
    99124                        // Consider the possibility that UInt32ToNumber is dead but its
    100125                        // child isn't; if so then we should MovHint the child.
    … …  
    118143                case GetLocal:
    119144                case SetArgument: {
    120                     // Leave them as not shouldGenerate.
    121                     break;
     145                    if (m_graph.m_form == ThreadedCPS) {
     146                        // Leave them as not shouldGenerate.
     147                        break;
     148                    }
    122149                }
    123150
    … …  
    127154                            Edge edge = m_graph.m_varArgChildren[childIdx];
    128155
    129                             if (!edge || edge.isProved() || edge.useKind() == UntypedUse)
     156                            if (!edge || edge.willNotHaveCheck())
    130157                                continue;
    131158
    … …  
    159186        // We may have an "unproved" untyped use for code that is unreachable. The CFA
    160187        // will just not have gotten around to it.
    161         if (edge.isProved() || edge.useKind() == UntypedUse)
     188        if (edge.willNotHaveCheck())
    162189            return;
    163190        if (!edge->postfixRef())
    … …  
    165192    }
    166193   
     194    void countNode(Node* node)
     195    {
     196        if (node->postfixRef())
     197            return;
     198        m_worklist.append(node);
     199    }
     200   
    167201    void countEdge(Node*, Edge edge)
    168202    {
    169203        // Don't count edges that are already counted for their type checks.
    170         if (!(edge.isProved() || edge.useKind() == UntypedUse))
     204        if (edge.willHaveCheck())
    171205            return;
    172        
    173         if (edge->postfixRef())
    174             return;
    175         m_worklist.append(edge.node());
     206        countNode(edge.node());
    176207    }
    177208   
    … …  
    182213            if (!edge)
    183214                continue;
    184             if (edge.isProved() || edge.useKind() == UntypedUse)
     215            if (edge.willNotHaveCheck())
    185216                node->children.removeEdge(i--);
    186217        }
Note: See TracChangeset for help on using the changeset viewer.