fourthTier: DFG should have an SSA form for use by FTL
authoroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:04:45 +0000 (04:04 +0000)
committeroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:04:45 +0000 (04:04 +0000)
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!

* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/Operands.h:
(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

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@153274 268f45cc-cd09-0410-ab3c-d52691b4dbfc

63 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/Operands.h
Source/JavaScriptCore/dfg/DFGAbstractState.cpp
Source/JavaScriptCore/dfg/DFGAbstractState.h
Source/JavaScriptCore/dfg/DFGAdjacencyList.h
Source/JavaScriptCore/dfg/DFGBasicBlock.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h
Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockInsertionSet.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCFAPhase.cpp
Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp
Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
Source/JavaScriptCore/dfg/DFGCommon.cpp
Source/JavaScriptCore/dfg/DFGCommon.h
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
Source/JavaScriptCore/dfg/DFGEdge.cpp
Source/JavaScriptCore/dfg/DFGEdge.h
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGFlushFormat.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGFlushFormat.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGInsertionSet.h
Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGNode.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeFlags.cpp
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/dfg/DFGPredictionInjectionPhase.cpp
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/JavaScriptCore/dfg/DFGVariableAccessData.h
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/ftl/FTLLoweredNodeValue.h [new file with mode: 0644]
Source/JavaScriptCore/ftl/FTLValueFromBlock.h
Source/JavaScriptCore/ftl/FTLValueSource.cpp
Source/JavaScriptCore/ftl/FTLValueSource.h
Source/JavaScriptCore/runtime/Options.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/DataLog.h
Source/WTF/wtf/HashSet.h
Source/WTF/wtf/HashTable.h
Source/WTF/wtf/Insertion.h [new file with mode: 0644]
Source/WTF/wtf/ListDump.h [new file with mode: 0644]
Source/WTF/wtf/PrintStream.h
Source/WTF/wtf/StringPrintStream.h

index c4651fd..fe8b7fe 100644 (file)
@@ -1,3 +1,349 @@
+2013-07-12  Filip Pizlo  <fpizlo@apple.com>
+
+        fourthTier: DFG should have an SSA form for use by FTL
+        https://bugs.webkit.org/show_bug.cgi?id=118338
+
+        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!
+
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * bytecode/Operands.h:
+        (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:
+
 2013-07-11  Mark Lam  <mark.lam@apple.com>
 
         Resurrect the CLoop LLINT on the FTL branch.
index 9111baf..1dcb3dc 100644 (file)
                A7C1EAF117987AB600299DB2 /* StackIterator.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7C1EAEC17987AB600299DB2 /* StackIterator.cpp */; };
                A7C1EAF217987AB600299DB2 /* StackIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C1EAED17987AB600299DB2 /* StackIterator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A7C1EAF317987AB600299DB2 /* StackIteratorPrivate.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C1EAEE17987AB600299DB2 /* StackIteratorPrivate.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */; };
+               A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CE417A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp */; };
+               A7D89CF417A0B8CC00773AD8 /* DFGBlockInsertionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CE517A0B8CC00773AD8 /* DFGBlockInsertionSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CF517A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */; };
+               A7D89CF617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CE717A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CF717A0B8CC00773AD8 /* DFGFlushFormat.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CE817A0B8CC00773AD8 /* DFGFlushFormat.cpp */; };
+               A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CE917A0B8CC00773AD8 /* DFGFlushFormat.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CF917A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CEA17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp */; };
+               A7D89CFA17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CEB17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CFB17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CEC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp */; };
+               A7D89CFC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CED17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CFD17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CEE17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.cpp */; };
+               A7D89CFE17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CEF17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89CFF17A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */; };
+               A7D89D0017A0B8CC00773AD8 /* DFGSSAConversionPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               A7D89D0217A0B90400773AD8 /* FTLLoweredNodeValue.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89D0117A0B90400773AD8 /* FTLLoweredNodeValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A7DCB97312E5193F00911940 /* WriteBarrier.h in Headers */ = {isa = PBXBuildFile; fileRef = A7DCB77912E3D90500911940 /* WriteBarrier.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A7E2EA6B0FB460CF00601F06 /* LiteralParser.h in Headers */ = {isa = PBXBuildFile; fileRef = A7E2EA690FB460CF00601F06 /* LiteralParser.h */; };
                A7E2EA6C0FB460CF00601F06 /* LiteralParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7E2EA6A0FB460CF00601F06 /* LiteralParser.cpp */; };
                A7C1EAEE17987AB600299DB2 /* StackIteratorPrivate.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StackIteratorPrivate.h; sourceTree = "<group>"; };
                A7C225CC139981F100FF1662 /* KeywordLookupGenerator.py */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.python; path = KeywordLookupGenerator.py; sourceTree = "<group>"; };
                A7C225CD1399849C00FF1662 /* KeywordLookup.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = KeywordLookup.h; sourceTree = "<group>"; };
+               A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBasicBlock.cpp; path = dfg/DFGBasicBlock.cpp; sourceTree = "<group>"; };
+               A7D89CE417A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockInsertionSet.cpp; path = dfg/DFGBlockInsertionSet.cpp; sourceTree = "<group>"; };
+               A7D89CE517A0B8CC00773AD8 /* DFGBlockInsertionSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockInsertionSet.h; path = dfg/DFGBlockInsertionSet.h; sourceTree = "<group>"; };
+               A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCriticalEdgeBreakingPhase.cpp; path = dfg/DFGCriticalEdgeBreakingPhase.cpp; sourceTree = "<group>"; };
+               A7D89CE717A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCriticalEdgeBreakingPhase.h; path = dfg/DFGCriticalEdgeBreakingPhase.h; sourceTree = "<group>"; };
+               A7D89CE817A0B8CC00773AD8 /* DFGFlushFormat.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlushFormat.cpp; path = dfg/DFGFlushFormat.cpp; sourceTree = "<group>"; };
+               A7D89CE917A0B8CC00773AD8 /* DFGFlushFormat.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlushFormat.h; path = dfg/DFGFlushFormat.h; sourceTree = "<group>"; };
+               A7D89CEA17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlushLivenessAnalysisPhase.cpp; path = dfg/DFGFlushLivenessAnalysisPhase.cpp; sourceTree = "<group>"; };
+               A7D89CEB17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlushLivenessAnalysisPhase.h; path = dfg/DFGFlushLivenessAnalysisPhase.h; sourceTree = "<group>"; };
+               A7D89CEC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGLivenessAnalysisPhase.cpp; path = dfg/DFGLivenessAnalysisPhase.cpp; sourceTree = "<group>"; };
+               A7D89CED17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGLivenessAnalysisPhase.h; path = dfg/DFGLivenessAnalysisPhase.h; sourceTree = "<group>"; };
+               A7D89CEE17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGOSRAvailabilityAnalysisPhase.cpp; path = dfg/DFGOSRAvailabilityAnalysisPhase.cpp; sourceTree = "<group>"; };
+               A7D89CEF17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGOSRAvailabilityAnalysisPhase.h; path = dfg/DFGOSRAvailabilityAnalysisPhase.h; sourceTree = "<group>"; };
+               A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGSSAConversionPhase.cpp; path = dfg/DFGSSAConversionPhase.cpp; sourceTree = "<group>"; };
+               A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSSAConversionPhase.h; path = dfg/DFGSSAConversionPhase.h; sourceTree = "<group>"; };
+               A7D89D0117A0B90400773AD8 /* FTLLoweredNodeValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLLoweredNodeValue.h; path = ftl/FTLLoweredNodeValue.h; sourceTree = "<group>"; };
                A7DCB77912E3D90500911940 /* WriteBarrier.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WriteBarrier.h; sourceTree = "<group>"; };
                A7E2EA690FB460CF00601F06 /* LiteralParser.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LiteralParser.h; sourceTree = "<group>"; };
                A7E2EA6A0FB460CF00601F06 /* LiteralParser.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LiteralParser.cpp; sourceTree = "<group>"; };
                034768DFFF38A50411DB9C8B /* Products */ = {
                        isa = PBXGroup;
                        children = (
+                               932F5BD90822A1C700736975 /* JavaScriptCore.framework */,
                                932F5BE10822A1C700736975 /* jsc */,
                                0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
-                               932F5BD90822A1C700736975 /* JavaScriptCore.framework */,
                                141211200A48793C00480255 /* minidom */,
                                14BD59BF0A3E8F9000BAF59C /* testapi */,
                                6511230514046A4C002B101D /* testRegExp */,
                                0F8F2B94172E049E007DBDA5 /* FTLLink.h */,
                                0FEA0A04170513DB00BB722C /* FTLLowerDFGToLLVM.cpp */,
                                0FEA0A05170513DB00BB722C /* FTLLowerDFGToLLVM.h */,
+                               A7D89D0117A0B90400773AD8 /* FTLLoweredNodeValue.h */,
                                0F235BC617178E1C00690C7F /* FTLOSRExit.cpp */,
                                0F235BC717178E1C00690C7F /* FTLOSRExit.h */,
                                0F235BC817178E1C00690C7F /* FTLOSRExitCompilationInfo.h */,
                                0FC0976C1468AB4A00CF2442 /* DFGAssemblyHelpers.h */,
                                0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
                                0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
+                               A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */,
                                0F620170143FCD2F0068B77C /* DFGBasicBlock.h */,
                                0FD5652216AB780A00197653 /* DFGBasicBlockInlines.h */,
                                A70B083017A0B79B00DAF14B /* DFGBinarySwitch.cpp */,
                                A70B083117A0B79B00DAF14B /* DFGBinarySwitch.h */,
+                               A7D89CE417A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp */,
+                               A7D89CE517A0B8CC00773AD8 /* DFGBlockInsertionSet.h */,
                                0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
                                86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
                                86EC9DB51328DF82002B2AD7 /* DFGByteCodeParser.h */,
                                0F3B3A18153E68EF003ED0FF /* DFGConstantFoldingPhase.h */,
                                0FBE0F6B16C1DB010082C5E8 /* DFGCPSRethreadingPhase.cpp */,
                                0FBE0F6C16C1DB010082C5E8 /* DFGCPSRethreadingPhase.h */,
+                               A7D89CE617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp */,
+                               A7D89CE717A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.h */,
                                0FFFC94D14EF909500C72532 /* DFGCSEPhase.cpp */,
                                0FFFC94E14EF909500C72532 /* DFGCSEPhase.h */,
                                0F2FC77016E12F6F0038D976 /* DFGDCEPhase.cpp */,
                                A78A976F179738B8009DF744 /* DFGFinalizer.h */,
                                0F2BDC12151C5D4A00CD8910 /* DFGFixupPhase.cpp */,
                                0F2BDC13151C5D4A00CD8910 /* DFGFixupPhase.h */,
+                               A7D89CE817A0B8CC00773AD8 /* DFGFlushFormat.cpp */,
+                               A7D89CE917A0B8CC00773AD8 /* DFGFlushFormat.h */,
+                               A7D89CEA17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp */,
+                               A7D89CEB17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.h */,
                                86AE6C4B136A11E400963012 /* DFGFPRInfo.h */,
                                86EC9DB61328DF82002B2AD7 /* DFGGenerationInfo.h */,
                                86AE6C4C136A11E400963012 /* DFGGPRInfo.h */,
                                A78A9771179738B8009DF744 /* DFGJITFinalizer.h */,
                                A73A53581799CD5D00170C19 /* DFGLazyJSValue.cpp */,
                                A73A53591799CD5D00170C19 /* DFGLazyJSValue.h */,
+                               A7D89CEC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp */,
+                               A7D89CED17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h */,
                                0FB4B51C16B62772003F696B /* DFGLongLivedState.cpp */,
                                0FB4B51D16B62772003F696B /* DFGLongLivedState.h */,
                                0F2BDC3D1522801700CD8910 /* DFGMinifiedGraph.h */,
                                0FA581B9150E952A00B9A2D9 /* DFGNodeType.h */,
                                86EC9DBF1328DF82002B2AD7 /* DFGOperations.cpp */,
                                86EC9DC01328DF82002B2AD7 /* DFGOperations.h */,
+                               A7D89CEE17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.cpp */,
+                               A7D89CEF17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.h */,
                                0FD82E52141DAEDE00179C94 /* DFGOSREntry.cpp */,
                                0FD82E53141DAEDE00179C94 /* DFGOSREntry.h */,
                                0FC0978E146A6F6300CF2442 /* DFGOSRExit.cpp */,
                                86EC9DC31328DF82002B2AD7 /* DFGSpeculativeJIT.h */,
                                86880F1B14328BB900B08D42 /* DFGSpeculativeJIT32_64.cpp */,
                                86880F4C14353B2100B08D42 /* DFGSpeculativeJIT64.cpp */,
+                               A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */,
+                               A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */,
                                0F63947615DCE347006A597C /* DFGStructureAbstractValue.h */,
                                0FC0979F146B28C700CF2442 /* DFGThunks.cpp */,
                                0FC097A0146B28C700CF2442 /* DFGThunks.h */,
                                0F620176143FCD3B0068B77C /* DFGBasicBlock.h in Headers */,
                                0FFB921A16D02EC50055A5DB /* DFGBasicBlockInlines.h in Headers */,
                                A70B083317A0B79B00DAF14B /* DFGBinarySwitch.h in Headers */,
+                               A7D89CF417A0B8CC00773AD8 /* DFGBlockInsertionSet.h in Headers */,
                                0F8364B7164B0C110053329A /* DFGBranchDirection.h in Headers */,
                                86EC9DC51328DF82002B2AD7 /* DFGByteCodeParser.h in Headers */,
                                0F256C361627B0AD007F2783 /* DFGCallArrayAllocatorSlowPathGenerator.h in Headers */,
                                0FEA0A32170D40BF00BB722C /* DFGCommonData.h in Headers */,
                                0F3B3A1B153E68F4003ED0FF /* DFGConstantFoldingPhase.h in Headers */,
                                0FBE0F7316C1DB050082C5E8 /* DFGCPSRethreadingPhase.h in Headers */,
+                               A7D89CF617A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.h in Headers */,
                                0FFFC95A14EF90A900C72532 /* DFGCSEPhase.h in Headers */,
                                0F2FC77316E12F740038D976 /* DFGDCEPhase.h in Headers */,
                                0F8F2B9A172F0501007DBDA5 /* DFGDesiredIdentifiers.h in Headers */,
                                A7BFF3C0179868940002F462 /* DFGFiltrationResult.h in Headers */,
                                A78A9777179738B8009DF744 /* DFGFinalizer.h in Headers */,
                                0F2BDC16151C5D4F00CD8910 /* DFGFixupPhase.h in Headers */,
+                               A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
+                               A7D89CFA17A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.h in Headers */,
                                86AE6C4D136A11E400963012 /* DFGFPRInfo.h in Headers */,
                                86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
                                86AE6C4E136A11E400963012 /* DFGGPRInfo.h in Headers */,
                                86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
                                A78A9779179738B8009DF744 /* DFGJITFinalizer.h in Headers */,
                                A73A535B1799CD5D00170C19 /* DFGLazyJSValue.h in Headers */,
+                               A7D89CFC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h in Headers */,
                                0FF0F19B16B729FA005DF95B /* DFGLongLivedState.h in Headers */,
                                0F2BDC451522801B00CD8910 /* DFGMinifiedGraph.h in Headers */,
                                0F2E892D16D02BAF009E4FD2 /* DFGMinifiedID.h in Headers */,
                                0FA581BB150E953000B9A2D9 /* DFGNodeFlags.h in Headers */,
                                0FA581BC150E953000B9A2D9 /* DFGNodeType.h in Headers */,
                                86EC9DD01328DF82002B2AD7 /* DFGOperations.h in Headers */,
+                               A7D89CFE17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.h in Headers */,
                                0FD82E57141DAF1000179C94 /* DFGOSREntry.h in Headers */,
                                0FC0976A1468A6F700CF2442 /* DFGOSRExit.h in Headers */,
                                0F235BEC17178E7300690C7F /* DFGOSRExitBase.h in Headers */,
                                0F1E3A67153A21E2000F9456 /* DFGSilentRegisterSavePlan.h in Headers */,
                                0FFB921D16D02F300055A5DB /* DFGSlowPathGenerator.h in Headers */,
                                86EC9DD31328DF82002B2AD7 /* DFGSpeculativeJIT.h in Headers */,
+                               A7D89D0017A0B8CC00773AD8 /* DFGSSAConversionPhase.h in Headers */,
                                0F63947815DCE34B006A597C /* DFGStructureAbstractValue.h in Headers */,
                                0FC097A2146B28CC00CF2442 /* DFGThunks.h in Headers */,
                                0F63943F15C75F19006A597C /* DFGTypeCheckHoistingPhase.h in Headers */,
                                A78A9781179738D5009DF744 /* FTLJITFinalizer.h in Headers */,
                                0F8F2B96172E04A3007DBDA5 /* FTLLink.h in Headers */,
                                0FEA0A10170513DB00BB722C /* FTLLowerDFGToLLVM.h in Headers */,
+                               A7D89D0217A0B90400773AD8 /* FTLLoweredNodeValue.h in Headers */,
                                0F235BDD17178E1C00690C7F /* FTLOSRExit.h in Headers */,
                                0F235BDE17178E1C00690C7F /* FTLOSRExitCompilationInfo.h in Headers */,
                                0F235BE017178E1C00690C7F /* FTLOSRExitCompiler.h in Headers */,
                                0F63948415E48118006A597C /* DFGArrayMode.cpp in Sources */,
                                0FC0976E1468AB5100CF2442 /* DFGAssemblyHelpers.cpp in Sources */,
                                0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
+                               A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
                                A70B083217A0B79B00DAF14B /* DFGBinarySwitch.cpp in Sources */,
+                               A7D89CF317A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp in Sources */,
                                86EC9DC41328DF82002B2AD7 /* DFGByteCodeParser.cpp in Sources */,
                                0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */,
                                0FFFC95714EF90A000C72532 /* DFGCFAPhase.cpp in Sources */,
                                0FEA0A31170D40BF00BB722C /* DFGCommonData.cpp in Sources */,
                                0F3B3A1A153E68F2003ED0FF /* DFGConstantFoldingPhase.cpp in Sources */,
                                0FBE0F7216C1DB030082C5E8 /* DFGCPSRethreadingPhase.cpp in Sources */,
+                               A7D89CF517A0B8CC00773AD8 /* DFGCriticalEdgeBreakingPhase.cpp in Sources */,
                                0FFFC95914EF90A600C72532 /* DFGCSEPhase.cpp in Sources */,
                                0F2FC77216E12F710038D976 /* DFGDCEPhase.cpp in Sources */,
                                0F8F2B99172F04FF007DBDA5 /* DFGDesiredIdentifiers.cpp in Sources */,
                                A78A9774179738B8009DF744 /* DFGFailedFinalizer.cpp in Sources */,
                                A78A9776179738B8009DF744 /* DFGFinalizer.cpp in Sources */,
                                0F2BDC15151C5D4D00CD8910 /* DFGFixupPhase.cpp in Sources */,
+                               A7D89CF717A0B8CC00773AD8 /* DFGFlushFormat.cpp in Sources */,
+                               A7D89CF917A0B8CC00773AD8 /* DFGFlushLivenessAnalysisPhase.cpp in Sources */,
                                86EC9DC71328DF82002B2AD7 /* DFGGraph.cpp in Sources */,
                                0FEA0A33170D40BF00BB722C /* DFGJITCode.cpp in Sources */,
                                86EC9DCB1328DF82002B2AD7 /* DFGJITCompiler.cpp in Sources */,
                                A78A9778179738B8009DF744 /* DFGJITFinalizer.cpp in Sources */,
                                A73A535A1799CD5D00170C19 /* DFGLazyJSValue.cpp in Sources */,
+                               A7D89CFB17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp in Sources */,
                                0FF0F19916B729F6005DF95B /* DFGLongLivedState.cpp in Sources */,
                                0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
                                A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
                                0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
                                0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
                                86EC9DCF1328DF82002B2AD7 /* DFGOperations.cpp in Sources */,
+                               A7D89CFD17A0B8CC00773AD8 /* DFGOSRAvailabilityAnalysisPhase.cpp in Sources */,
                                0FD82E56141DAF0800179C94 /* DFGOSREntry.cpp in Sources */,
                                0FC09791146A6F7100CF2442 /* DFGOSRExit.cpp in Sources */,
                                0F235BEB17178E7300690C7F /* DFGOSRExitBase.cpp in Sources */,
                                86EC9DD21328DF82002B2AD7 /* DFGSpeculativeJIT.cpp in Sources */,
                                86880F1F14328BB900B08D42 /* DFGSpeculativeJIT32_64.cpp in Sources */,
                                86880F4D14353B2100B08D42 /* DFGSpeculativeJIT64.cpp in Sources */,
+                               A7D89CFF17A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp in Sources */,
                                0FC097A1146B28CA00CF2442 /* DFGThunks.cpp in Sources */,
                                0F63944015C75F1D006A597C /* DFGTypeCheckHoistingPhase.cpp in Sources */,
                                0FBE0F7616C1DB0F0082C5E8 /* DFGUnificationPhase.cpp in Sources */,
index ae54ca3..c209db2 100644 (file)
@@ -43,7 +43,7 @@ template<typename T> struct OperandValueTraits;
 template<typename T>
 struct OperandValueTraits {
     static T defaultValue() { return T(); }
-    static void dump(const T& value, PrintStream& out) { value.dump(out); }
+    static void dump(const T& value, PrintStream& out) { out.print(value); }
 };
 
 enum OperandKind { ArgumentOperand, LocalOperand };
@@ -209,12 +209,25 @@ public:
         setLocalFirstTime(operand, value);
     }
     
-    void clear()
+    void fill(T value)
     {
         for (size_t i = 0; i < m_arguments.size(); ++i)
-            m_arguments[i] = Traits::defaultValue();
+            m_arguments[i] = value;
         for (size_t i = 0; i < m_locals.size(); ++i)
-            m_locals[i] = Traits::defaultValue();
+            m_locals[i] = value;
+    }
+    
+    void clear()
+    {
+        fill(Traits::defaultValue());
+    }
+    
+    bool operator==(const Operands& other) const
+    {
+        ASSERT(numberOfArguments() == other.numberOfArguments());
+        ASSERT(numberOfLocals() == other.numberOfLocals());
+        
+        return m_arguments == other.m_arguments && m_locals == other.m_locals;
     }
     
     void dump(PrintStream& out) const;
index c01ea07..7cf6099 100644 (file)
@@ -74,6 +74,16 @@ void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
         }
     }
     
+    if (m_graph.m_form == SSA) {
+        HashMap<Node*, AbstractValue>::iterator iter = basicBlock->ssa->valuesAtHead.begin();
+        HashMap<Node*, AbstractValue>::iterator end = basicBlock->ssa->valuesAtHead.end();
+        for (; iter != end; ++iter) {
+            forNode(iter->key) = iter->value;
+            if (iter->value.hasClobberableState())
+                m_haveStructures = true;
+        }
+    }
+    
     basicBlock->cfaShouldRevisit = false;
     basicBlock->cfaHasVisited = true;
     m_block = basicBlock;
@@ -83,13 +93,28 @@ void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
     m_currentNode = 0;
 }
 
-void AbstractState::initialize(Graph& graph)
+static void setLiveValues(HashMap<Node*, AbstractValue>& values, HashSet<Node*>& live)
+{
+    values.clear();
+    
+    HashSet<Node*>::iterator iter = live.begin();
+    HashSet<Node*>::iterator end = live.end();
+    for (; iter != end; ++iter)
+        values.add(*iter, AbstractValue());
+}
+
+void AbstractState::initialize()
 {
-    BasicBlock* root = graph.block(0);
+    BasicBlock* root = m_graph.block(0);
     root->cfaShouldRevisit = true;
     root->cfaHasVisited = false;
     root->cfaFoundConstants = false;
     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
+        if (m_graph.m_form == SSA) {
+            root->valuesAtHead.argument(i).makeTop();
+            continue;
+        }
+        
         Node* node = root->variablesAtHead.argument(i);
         ASSERT(node->op() == SetArgument);
         if (!node->variableAccessData()->shouldUnboxIfPossible()) {
@@ -118,12 +143,11 @@ void AbstractState::initialize(Graph& graph)
             root->valuesAtHead.local(i).clear();
         root->valuesAtTail.local(i).clear();
     }
-    for (BlockIndex blockIndex = 1 ; blockIndex < graph.numBlocks(); ++blockIndex) {
-        BasicBlock* block = graph.block(blockIndex);
+    for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+        BasicBlock* block = m_graph.block(blockIndex);
         if (!block)
             continue;
-        if (!block->isReachable)
-            continue;
+        ASSERT(block->isReachable);
         block->cfaShouldRevisit = false;
         block->cfaHasVisited = false;
         block->cfaFoundConstants = false;
@@ -137,12 +161,12 @@ void AbstractState::initialize(Graph& graph)
         }
         if (!block->isOSRTarget)
             continue;
-        if (block->bytecodeBegin != graph.m_plan.osrEntryBytecodeIndex)
+        if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex)
             continue;
-        for (size_t i = 0; i < graph.m_plan.mustHandleValues.size(); ++i) {
+        for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) {
             AbstractValue value;
-            value.setMostSpecific(graph, graph.m_plan.mustHandleValues[i]);
-            int operand = graph.m_plan.mustHandleValues.operandForIndex(i);
+            value.setMostSpecific(m_graph, m_graph.m_plan.mustHandleValues[i]);
+            int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i);
             block->valuesAtHead.operand(operand).merge(value);
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
             dataLogF("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
@@ -152,6 +176,15 @@ void AbstractState::initialize(Graph& graph)
         }
         block->cfaShouldRevisit = true;
     }
+    if (m_graph.m_form == SSA) {
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            setLiveValues(block->ssa->valuesAtHead, block->ssa->liveAtHead);
+            setLiveValues(block->ssa->valuesAtTail, block->ssa->liveAtTail);
+        }
+    }
 }
 
 bool AbstractState::endBasicBlock(MergeMode mergeMode)
@@ -172,20 +205,41 @@ bool AbstractState::endBasicBlock(MergeMode mergeMode)
     bool changed = false;
     
     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
-        for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
+        switch (m_graph.m_form) {
+        case ThreadedCPS: {
+            for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("        Merging state for argument %zu.\n", argument);
+                dataLogF("        Merging state for argument %zu.\n", argument);
 #endif
-            AbstractValue& destination = block->valuesAtTail.argument(argument);
-            changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
-        }
-        
-        for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
+                AbstractValue& destination = block->valuesAtTail.argument(argument);
+                changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
+            }
+            
+            for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
-            dataLogF("        Merging state for local %zu.\n", local);
+                dataLogF("        Merging state for local %zu.\n", local);
 #endif
-            AbstractValue& destination = block->valuesAtTail.local(local);
-            changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
+                AbstractValue& destination = block->valuesAtTail.local(local);
+                changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
+            }
+            break;
+        }
+            
+        case SSA: {
+            for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
+                changed |= block->valuesAtTail[i].merge(m_variables[i]);
+            
+            HashSet<Node*>::iterator iter = block->ssa->liveAtTail.begin();
+            HashSet<Node*>::iterator end = block->ssa->liveAtTail.end();
+            for (; iter != end; ++iter) {
+                Node* node = *iter;
+                changed |= block->ssa->valuesAtTail.find(node)->value.merge(forNode(node));
+            }
+            break;
+        }
+            
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
         }
     }
     
@@ -292,6 +346,18 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         forNode(node) = forNode(node->child1());
         break;
     }
+        
+    case GetArgument: {
+        ASSERT(m_graph.m_form == SSA);
+        VariableAccessData* variable = node->variableAccessData();
+        AbstractValue& value = m_variables.operand(variable->local());
+        ASSERT(value.isTop());
+        FiltrationResult result =
+            value.filter(typeFilterFor(useKindFor(variable->flushFormat())));
+        ASSERT_UNUSED(result, result == FiltrationOK);
+        forNode(node) = value;
+        break;
+    }
             
     case GetLocal: {
         VariableAccessData* variableAccessData = node->variableAccessData();
@@ -323,13 +389,13 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         break;
     }
         
+    case MovHint:
     case MovHintAndCheck: {
         // Don't need to do anything. A MovHint is effectively a promise that the SetLocal
         // was dead.
         break;
     }
         
-    case MovHint:
     case ZombieHint: {
         RELEASE_ASSERT_NOT_REACHED();
         break;
@@ -1610,6 +1676,17 @@ bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
         break;
             
     case Phi:
+        RELEASE_ASSERT(m_graph.m_form == SSA);
+        // The state of this node would have already been decided.
+        break;
+        
+    case Upsilon: {
+        AbstractValue& value = forNode(node->child1());
+        forNode(node) = value;
+        forNode(node->phi()) = value;
+        break;
+    }
+        
     case Flush:
     case PhantomLocal:
     case Breakpoint:
@@ -1702,7 +1779,7 @@ inline void AbstractState::clobberStructures(unsigned indexInBlock)
     m_didClobber = true;
 }
 
-inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
+bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
 {
     if (!node)
         return false;
@@ -1790,21 +1867,44 @@ inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, Abstract
     return true;
 }
 
-inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
+bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
 {
     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
     
     bool changed = false;
     
-    for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
-        AbstractValue& destination = to->valuesAtHead.argument(argument);
-        changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
+    switch (m_graph.m_form) {
+    case ThreadedCPS: {
+        for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
+            AbstractValue& destination = to->valuesAtHead.argument(argument);
+            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
+        }
+        
+        for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
+            AbstractValue& destination = to->valuesAtHead.local(local);
+            changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
+        }
+        break;
     }
-    
-    for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
-        AbstractValue& destination = to->valuesAtHead.local(local);
-        changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
+        
+    case SSA: {
+        for (size_t i = from->valuesAtTail.size(); i--;)
+            changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
+        
+        HashSet<Node*>::iterator iter = to->ssa->liveAtHead.begin();
+        HashSet<Node*>::iterator end = to->ssa->liveAtHead.end();
+        for (; iter != end; ++iter) {
+            Node* node = *iter;
+            changed |= to->ssa->valuesAtHead.find(node)->value.merge(
+                from->ssa->valuesAtTail.find(node)->value);
+        }
+        break;
+    }
+        
+    default:
+        RELEASE_ASSERT_NOT_REACHED();
+        break;
     }
 
     if (!to->cfaHasVisited)
index 4dec4c9..239b12e 100644 (file)
@@ -130,7 +130,7 @@ public:
     // Call this before beginning CFA to initialize the abstract values of
     // arguments, and to indicate which blocks should be listed for CFA
     // execution.
-    static void initialize(Graph&);
+    void initialize();
 
     // Start abstractly executing the given basic block. Initializes the
     // notion of abstract state to what we believe it to be at the head
index d3f925d..dc3cccb 100644 (file)
@@ -99,6 +99,15 @@ public:
     
     Edge child1Unchecked() const { return m_words[0]; }
     
+    Edge justOneChild() const
+    {
+        if (!!child1() && !child2()) {
+            ASSERT(!child3());
+            return child1();
+        }
+        return Edge();
+    }
+    
     void initialize(Edge child1, Edge child2, Edge child3)
     {
         child(0) = child1;
diff --git a/Source/JavaScriptCore/dfg/DFGBasicBlock.cpp b/Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
new file mode 100644 (file)
index 0000000..5c5c778
--- /dev/null
@@ -0,0 +1,124 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGBasicBlock.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+BasicBlock::BasicBlock(unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals)
+    : bytecodeBegin(bytecodeBegin)
+    , index(NoBlock)
+    , isOSRTarget(false)
+    , cfaHasVisited(false)
+    , cfaShouldRevisit(false)
+    , cfaFoundConstants(false)
+    , cfaDidFinish(true)
+    , cfaBranchDirection(InvalidBranchDirection)
+#if !ASSERT_DISABLED
+    , isLinked(false)
+#endif
+    , isReachable(false)
+    , variablesAtHead(numArguments, numLocals)
+    , variablesAtTail(numArguments, numLocals)
+    , valuesAtHead(numArguments, numLocals)
+    , valuesAtTail(numArguments, numLocals)
+{
+}
+
+BasicBlock::~BasicBlock() { }
+
+void BasicBlock::ensureLocals(unsigned newNumLocals)
+{
+    variablesAtHead.ensureLocals(newNumLocals);
+    variablesAtTail.ensureLocals(newNumLocals);
+    valuesAtHead.ensureLocals(newNumLocals);
+    valuesAtTail.ensureLocals(newNumLocals);
+}
+
+bool BasicBlock::isInPhis(Node* node) const
+{
+    for (size_t i = 0; i < phis.size(); ++i) {
+        if (phis[i] == node)
+            return true;
+    }
+    return false;
+}
+
+bool BasicBlock::isInBlock(Node* myNode) const
+{
+    for (size_t i = 0; i < numNodes(); ++i) {
+        if (node(i) == myNode)
+            return true;
+    }
+    return false;
+}
+
+void BasicBlock::removePredecessor(BasicBlock* block)
+{
+    for (unsigned i = 0; i < predecessors.size(); ++i) {
+        if (predecessors[i] != block)
+            continue;
+        predecessors[i] = predecessors.last();
+        predecessors.removeLast();
+        return;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+void BasicBlock::replacePredecessor(BasicBlock* from, BasicBlock* to)
+{
+    for (unsigned i = predecessors.size(); i--;) {
+        if (predecessors[i] != from)
+            continue;
+        predecessors[i] = to;
+        return;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+void BasicBlock::dump(PrintStream& out) const
+{
+    out.print("#", index);
+}
+
+BasicBlock::SSAData::SSAData(BasicBlock* block)
+    : flushFormatAtHead(OperandsLike, block->variablesAtHead)
+    , flushFormatAtTail(OperandsLike, block->variablesAtHead)
+    , availabilityAtHead(OperandsLike, block->variablesAtHead)
+    , availabilityAtTail(OperandsLike, block->variablesAtHead)
+{
+}
+
+BasicBlock::SSAData::~SSAData() { }
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
index da52354..94be495 100644 (file)
@@ -33,6 +33,8 @@
 #include "DFGNode.h"
 #include "DFGVariadicFunction.h"
 #include "Operands.h"
+#include <wtf/HashMap.h>
+#include <wtf/HashSet.h>
 #include <wtf/OwnPtr.h>
 #include <wtf/Vector.h>
 
@@ -44,42 +46,16 @@ class InsertionSet;
 typedef Vector<BasicBlock*, 2> PredecessorList;
 
 struct BasicBlock : RefCounted<BasicBlock> {
-    BasicBlock(unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals)
-        : bytecodeBegin(bytecodeBegin)
-        , index(NoBlock)
-        , isOSRTarget(false)
-        , cfaHasVisited(false)
-        , cfaShouldRevisit(false)
-        , cfaFoundConstants(false)
-        , cfaDidFinish(true)
-        , cfaBranchDirection(InvalidBranchDirection)
-#if !ASSERT_DISABLED
-        , isLinked(false)
-#endif
-        , isReachable(false)
-        , variablesAtHead(numArguments, numLocals)
-        , variablesAtTail(numArguments, numLocals)
-        , valuesAtHead(numArguments, numLocals)
-        , valuesAtTail(numArguments, numLocals)
-    {
-    }
+    BasicBlock(unsigned bytecodeBegin, unsigned numArguments, unsigned numLocals);
+    ~BasicBlock();
     
-    ~BasicBlock()
-    {
-    }
-    
-    void ensureLocals(unsigned newNumLocals)
-    {
-        variablesAtHead.ensureLocals(newNumLocals);
-        variablesAtTail.ensureLocals(newNumLocals);
-        valuesAtHead.ensureLocals(newNumLocals);
-        valuesAtTail.ensureLocals(newNumLocals);
-    }
+    void ensureLocals(unsigned newNumLocals);
     
     size_t size() const { return m_nodes.size(); }
     bool isEmpty() const { return !size(); }
     Node*& at(size_t i) { return m_nodes[i]; }
     Node* at(size_t i) const { return m_nodes[i]; }
+    Node*& operator[](size_t i) { return at(i); }
     Node* operator[](size_t i) const { return at(i); }
     Node* last() const { return at(size() - 1); }
     void resize(size_t size) { m_nodes.resize(size); }
@@ -96,44 +72,34 @@ struct BasicBlock : RefCounted<BasicBlock> {
     }
     bool isPhiIndex(size_t i) const { return i < phis.size(); }
     
-    bool isInPhis(Node* node) const
-    {
-        for (size_t i = 0; i < phis.size(); ++i) {
-            if (phis[i] == node)
-                return true;
-        }
-        return false;
-    }
-    
-    bool isInBlock(Node* myNode) const
-    {
-        for (size_t i = 0; i < numNodes(); ++i) {
-            if (node(i) == myNode)
-                return true;
-        }
-        return false;
-    }
+    bool isInPhis(Node* node) const;
+    bool isInBlock(Node* myNode) const;
     
     unsigned numSuccessors() { return last()->numSuccessors(); }
     
-    BasicBlock* successor(unsigned index)
+    BasicBlock*& successor(unsigned index)
     {
         return last()->successor(index);
     }
-    BasicBlock* successorForCondition(bool condition)
+    BasicBlock*& successorForCondition(bool condition)
     {
         return last()->successorForCondition(condition);
     }
+    
+    void removePredecessor(BasicBlock* block);
+    void replacePredecessor(BasicBlock* from, BasicBlock* to);
 
 #define DFG_DEFINE_APPEND_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
     templatePre typeParams templatePost Node* appendNode(Graph&, SpeculatedType valueParamsComma valueParams);
     DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
 #undef DFG_DEFINE_APPEND_NODE
     
-    void dump(PrintStream& out) const
-    {
-        out.print("#", index);
-    }
+#define DFG_DEFINE_APPEND_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
+    templatePre typeParams templatePost Node* appendNonTerminal(Graph&, SpeculatedType valueParamsComma valueParams);
+    DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
+#undef DFG_DEFINE_APPEND_NODE
+    
+    void dump(PrintStream& out) const;
     
     // This value is used internally for block linking and OSR entry. It is mostly meaningless
     // for other purposes due to inlining.
@@ -160,6 +126,21 @@ struct BasicBlock : RefCounted<BasicBlock> {
     
     Operands<AbstractValue> valuesAtHead;
     Operands<AbstractValue> valuesAtTail;
+    
+    struct SSAData {
+        Operands<FlushFormat> flushFormatAtHead;
+        Operands<FlushFormat> flushFormatAtTail;
+        Operands<Node*> availabilityAtHead;
+        Operands<Node*> availabilityAtTail;
+        HashSet<Node*> liveAtHead;
+        HashSet<Node*> liveAtTail;
+        HashMap<Node*, AbstractValue> valuesAtHead;
+        HashMap<Node*, AbstractValue> valuesAtTail;
+        
+        SSAData(BasicBlock*);
+        ~SSAData();
+    };
+    OwnPtr<SSAData> ssa;
 
 private:
     friend class InsertionSet;
index 06eb393..3671a2a 100644 (file)
@@ -43,6 +43,17 @@ namespace JSC { namespace DFG {
     DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
 #undef DFG_DEFINE_APPEND_NODE
 
+#define DFG_DEFINE_APPEND_NODE(templatePre, templatePost, typeParams, valueParamsComma, valueParams, valueArgs) \
+    templatePre typeParams templatePost inline Node* BasicBlock::appendNonTerminal(Graph& graph, SpeculatedType type valueParamsComma valueParams) \
+    { \
+        Node* result = graph.addNode(type valueParamsComma valueArgs); \
+        append(last()); \
+        at(size() - 2) = result; \
+        return result; \
+    }
+    DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
+#undef DFG_DEFINE_APPEND_NODE
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
diff --git a/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp b/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.cpp
new file mode 100644 (file)
index 0000000..26aeda0
--- /dev/null
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGBlockInsertionSet.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+BlockInsertionSet::BlockInsertionSet(Graph& graph)
+    : m_graph(graph)
+{
+}
+
+BlockInsertionSet::~BlockInsertionSet() { }
+
+void BlockInsertionSet::insert(const BlockInsertion& insertion)
+{
+    m_insertions.append(insertion);
+}
+
+void BlockInsertionSet::insert(size_t index, PassRefPtr<BasicBlock> block)
+{
+    insert(BlockInsertion(index, block));
+}
+
+BasicBlock* BlockInsertionSet::insert(size_t index)
+{
+    RefPtr<BasicBlock> block = adoptRef(new BasicBlock(
+        UINT_MAX,
+        m_graph.block(0)->variablesAtHead.numberOfArguments(),
+        m_graph.block(0)->variablesAtHead.numberOfLocals()));
+    block->isReachable = true;
+    insert(index, block);
+    return block.get();
+}
+
+BasicBlock* BlockInsertionSet::insertBefore(BasicBlock* before)
+{
+    return insert(before->index);
+}
+
+bool BlockInsertionSet::execute()
+{
+    if (m_insertions.isEmpty())
+        return false;
+    
+    // We allow insertions to be given to us in any order. So, we need to
+    // sort them before running WTF::executeInsertions.
+    std::sort(m_insertions.begin(), m_insertions.end());
+
+    executeInsertions(m_graph.m_blocks, m_insertions);
+    
+    // Prune out empty entries. This isn't strictly necessary but it's
+    // healthy to keep the block list from growing.
+    unsigned targetIndex = 0;
+    for (unsigned sourceIndex = 0; sourceIndex < m_graph.m_blocks.size();) {
+        RefPtr<BasicBlock> block = m_graph.m_blocks[sourceIndex++];
+        if (!block)
+            continue;
+        m_graph.m_blocks[targetIndex++] = block;
+    }
+    m_graph.m_blocks.resize(targetIndex);
+    
+    // Make sure that the blocks know their new indices.
+    for (unsigned i = 0; i < m_graph.m_blocks.size(); ++i)
+        m_graph.m_blocks[i]->index = i;
+    
+    // And finally, invalidate all analyses that rely on the CFG.
+    m_graph.invalidateCFG();
+    
+    return true;
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.h b/Source/JavaScriptCore/dfg/DFGBlockInsertionSet.h
new file mode 100644 (file)
index 0000000..133170c
--- /dev/null
@@ -0,0 +1,63 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGBlockInsertionSet_h
+#define DFGBlockInsertionSet_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include <wtf/Insertion.h>
+#include <wtf/Vector.h>
+
+namespace JSC { namespace DFG {
+
+typedef WTF::Insertion<RefPtr<BasicBlock> > BlockInsertion;
+
+class BlockInsertionSet {
+public:
+    BlockInsertionSet(Graph& graph);
+    ~BlockInsertionSet();
+    
+    void insert(const BlockInsertion& insertion);
+    void insert(size_t index, PassRefPtr<BasicBlock> block);
+    BasicBlock* insert(size_t index);
+    BasicBlock* insertBefore(BasicBlock* before);
+    
+    bool execute();
+
+private:
+    Graph& m_graph;
+    Vector<BlockInsertion, 8> m_insertions;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockInsertionSet_h
+
index 095c0d0..ee97442 100644 (file)
@@ -51,7 +51,7 @@ public:
     
     bool run()
     {
-        ASSERT(m_graph.m_form == ThreadedCPS);
+        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
         ASSERT(m_graph.m_unificationState == GloballyUnified);
         ASSERT(m_graph.m_refCountState == EverythingIsLive);
         
@@ -68,7 +68,7 @@ public:
         // after all predecessors have been visited. Only loops will cause this analysis to
         // revisit blocks, and the amount of revisiting is proportional to loop depth.
         
-        AbstractState::initialize(m_graph);
+        m_state.initialize();
         
         do {
             m_changed = false;
index 6473f1c..11af9c6 100644 (file)
@@ -361,15 +361,9 @@ private:
 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
         dataLog(
             "Fixing predecessors and phis due to jettison of Block ", *jettisonedBlock,
-            " from Block ", *block, ".\n",
+            " from Block ", *block, ".\n");
 #endif
-        for (unsigned i = 0; i < jettisonedBlock->predecessors.size(); ++i) {
-            if (jettisonedBlock->predecessors[i] != block)
-                continue;
-            jettisonedBlock->predecessors[i] = jettisonedBlock->predecessors.last();
-            jettisonedBlock->predecessors.removeLast();
-            break;
-        }
+        jettisonedBlock->removePredecessor(block);
     }
 
     Vector<BasicBlock*, 1> noBlocks()
index 9b2b0a5..97adf9b 100644 (file)
@@ -327,12 +327,14 @@ private:
             // SetArgument may only appear in the root block.
             //
             // Tail variable: the last thing that happened to the variable in the block.
-            // It may be a Flush, PhantomLocal, GetLocal, SetLocal, or SetArgument.
+            // It may be a Flush, PhantomLocal, GetLocal, SetLocal, SetArgument, or Phi.
             // SetArgument may only appear in the root block. Note that if there ever
             // was a GetLocal to the variable, and it was followed by PhantomLocals and
             // Flushes but not SetLocals, then the tail variable will be the GetLocal.
             // This reflects the fact that you only care that the tail variable is a
-            // Flush or PhantomLocal if nothing else interesting happened.
+            // Flush or PhantomLocal if nothing else interesting happened. Likewise, if
+            // there ever was a SetLocal and it was followed by Flushes, then the tail
+            // variable will be a SetLocal and not those subsequent Flushes.
             //
             // Child of GetLocal: the operation that the GetLocal keeps alive. For
             // uncaptured locals, it may be a Phi from the current block. For arguments,
index 502a95e..811a43c 100644 (file)
@@ -48,17 +48,15 @@ void printInternal(PrintStream& out, OptimizationFixpointState state)
     switch (state) {
     case BeforeFixpoint:
         out.print("BeforeFixpoint");
-        break;
+        return;
     case FixpointNotConverged:
         out.print("FixpointNotConverged");
-        break;
+        return;
     case FixpointConverged:
         out.print("FixpointConverged");
-        break;
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
+        return;
     }
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 void printInternal(PrintStream& out, GraphForm form)
@@ -66,14 +64,15 @@ void printInternal(PrintStream& out, GraphForm form)
     switch (form) {
     case LoadStore:
         out.print("LoadStore");
-        break;
+        return;
     case ThreadedCPS:
         out.print("ThreadedCPS");
-        break;
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
+        return;
+    case SSA:
+        out.print("SSA");
+        return;
     }
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 void printInternal(PrintStream& out, UnificationState state)
@@ -81,14 +80,12 @@ void printInternal(PrintStream& out, UnificationState state)
     switch (state) {
     case LocallyUnified:
         out.print("LocallyUnified");
-        break;
+        return;
     case GloballyUnified:
         out.print("GloballyUnified");
-        break;
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
+        return;
     }
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 void printInternal(PrintStream& out, RefCountState state)
@@ -96,14 +93,12 @@ void printInternal(PrintStream& out, RefCountState state)
     switch (state) {
     case EverythingIsLive:
         out.print("EverythingIsLive");
-        break;
+        return;
     case ExactRefCount:
         out.print("ExactRefCount");
-        break;
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
+        return;
     }
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 void printInternal(PrintStream& out, ProofStatus status)
@@ -111,14 +106,12 @@ void printInternal(PrintStream& out, ProofStatus status)
     switch (status) {
     case IsProved:
         out.print("IsProved");
-        break;
+        return;
     case NeedsCheck:
         out.print("NeedsCheck");
-        break;
-    default:
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
+        return;
     }
+    RELEASE_ASSERT_NOT_REACHED();
 }
 
 } // namespace WTF
index cf2c907..dd20ed8 100644 (file)
@@ -194,7 +194,10 @@ enum GraphForm {
     //
     // ThreadedCPS form is suitable for data flow analysis (CFA, prediction
     // propagation), register allocation, and code generation.
-    ThreadedCPS
+    ThreadedCPS,
+    
+    // SSA form. See DFGSSAConversionPhase.h for a description.
+    SSA
 };
 
 // Describes the state of the UnionFind structure of VariableAccessData's.
@@ -232,6 +235,19 @@ inline ProofStatus proofStatusForIsProved(bool isProved)
     return isProved ? IsProved : NeedsCheck;
 }
 
+enum KillStatus { DoesNotKill, DoesKill };
+
+inline bool doesKill(KillStatus killStatus)
+{
+    ASSERT(killStatus == DoesNotKill || killStatus == DoesKill);
+    return killStatus == DoesKill;
+}
+
+inline KillStatus killStatusForDoesKill(bool doesKill)
+{
+    return doesKill ? DoesKill : DoesNotKill;
+}
+
 template<typename T, typename U>
 bool checkAndSet(T& left, U right)
 {
index 229b588..1d88fda 100644 (file)
@@ -372,7 +372,7 @@ private:
                     m_graph.dethread();
                 }
             } else
-                ASSERT(!node->hasVariableAccessData());
+                ASSERT(!node->hasVariableAccessData(m_graph));
             
             m_graph.convertToConstant(node, value);
             m_insertionSet.insertNode(
@@ -391,7 +391,7 @@ private:
     {
         for (; indexInBlock < block->size(); ++indexInBlock) {
             Node* node = block->at(indexInBlock);
-            if (!node->hasLocal())
+            if (!node->hasLocal(m_graph))
                 continue;
             if (node->local() != operand)
                 continue;
diff --git a/Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.cpp b/Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.cpp
new file mode 100644 (file)
index 0000000..0e7717e
--- /dev/null
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGCriticalEdgeBreakingPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGBlockInsertionSet.h"
+#include "DFGGraph.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+#include <wtf/HashMap.h>
+
+namespace JSC { namespace DFG {
+
+class CriticalEdgeBreakingPhase : public Phase {
+public:
+    CriticalEdgeBreakingPhase(Graph& graph)
+        : Phase(graph, "critical edge breaking")
+        , m_insertionSet(graph)
+    {
+    }
+    
+    bool run()
+    {
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            
+            // An edge A->B is critical if A has multiple successor and B has multiple
+            // predecessors. Thus we fail early if we don't have multiple successors.
+            
+            if (block->numSuccessors() <= 1)
+                continue;
+            
+            for (unsigned i = block->numSuccessors(); i--;) {
+                BasicBlock** successor = &block->successor(i);
+                if ((*successor)->predecessors.size() <= 1)
+                    continue;
+                
+                breakCriticalEdge(block, successor); 
+            }
+        }
+        
+        return m_insertionSet.execute();
+    }
+
+private:
+    void breakCriticalEdge(BasicBlock* predecessor, BasicBlock** successor)
+    {
+        m_graph.dethread();
+        
+        BasicBlock* pad = m_insertionSet.insertBefore(*successor);
+        pad->appendNode(
+            m_graph, SpecNone, Jump, (*successor)->at(0)->codeOrigin, OpInfo(*successor));
+        pad->predecessors.append(predecessor);
+        (*successor)->replacePredecessor(predecessor, pad);
+        
+        *successor = pad;
+    }
+    
+    BlockInsertionSet m_insertionSet;
+};
+
+bool performCriticalEdgeBreaking(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Critical Edge Breaking Phase");
+    return runPhase<CriticalEdgeBreakingPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+
diff --git a/Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.h b/Source/JavaScriptCore/dfg/DFGCriticalEdgeBreakingPhase.h
new file mode 100644 (file)
index 0000000..d801c12
--- /dev/null
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGCriticalEdgeBreakingPhase_h
+#define DFGCriticalEdgeBreakingPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Inserts dummy basic blocks to break critical edges. An edge A->B is
+// critical if A has multiple successors and B has multiple predessors.
+
+bool performCriticalEdgeBreaking(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGCriticalEdgeBreakingPhase_h
+
index 4527980..162f631 100644 (file)
@@ -45,6 +45,8 @@ public:
     
     bool run()
     {
+        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == SSA);
+        
         // First reset the counts to 0 for all nodes.
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
             BasicBlock* block = m_graph.block(blockIndex);
@@ -75,10 +77,31 @@ public:
         }
         
         while (!m_worklist.isEmpty()) {
-            Node* node = m_worklist.last();
-            m_worklist.removeLast();
-            ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
-            DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
+            while (!m_worklist.isEmpty()) {
+                Node* node = m_worklist.last();
+                m_worklist.removeLast();
+                ASSERT(node->shouldGenerate()); // It should not be on the worklist unless it's ref'ed.
+                DFG_NODE_DO_TO_CHILDREN(m_graph, node, countEdge);
+            }
+            
+            if (m_graph.m_form == SSA) {
+                // Find Phi->Upsilon edges, which are represented as meta-data in the
+                // Upsilon.
+                for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                    BasicBlock* block = m_graph.block(blockIndex);
+                    if (!block)
+                        continue;
+                    for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+                        Node* node = block->at(nodeIndex);
+                        if (node->op() != Upsilon)
+                            continue;
+                        if (node->shouldGenerate())
+                            continue;
+                        if (node->phi()->shouldGenerate())
+                            countNode(node);
+                    }
+                }
+            }
         }
         
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
@@ -94,8 +117,10 @@ public:
                     continue;
                 
                 switch (node->op()) {
-                case SetLocal: {
-                    if (node->child1().isProved() || node->child1().useKind() == UntypedUse) {
+                case SetLocal:
+                case MovHint: {
+                    ASSERT((node->op() == SetLocal) == (m_graph.m_form == ThreadedCPS));
+                    if (node->child1().willNotHaveCheck()) {
                         // Consider the possibility that UInt32ToNumber is dead but its
                         // child isn't; if so then we should MovHint the child.
                         if (!node->child1()->shouldGenerate()
@@ -117,8 +142,10 @@ public:
                     
                 case GetLocal:
                 case SetArgument: {
-                    // Leave them as not shouldGenerate.
-                    break;
+                    if (m_graph.m_form == ThreadedCPS) {
+                        // Leave them as not shouldGenerate.
+                        break;
+                    }
                 }
 
                 default: {
@@ -126,7 +153,7 @@ public:
                         for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
                             Edge edge = m_graph.m_varArgChildren[childIdx];
 
-                            if (!edge || edge.isProved() || edge.useKind() == UntypedUse)
+                            if (!edge || edge.willNotHaveCheck())
                                 continue;
 
                             insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge);
@@ -158,21 +185,25 @@ private:
     {
         // We may have an "unproved" untyped use for code that is unreachable. The CFA
         // will just not have gotten around to it.
-        if (edge.isProved() || edge.useKind() == UntypedUse)
+        if (edge.willNotHaveCheck())
             return;
         if (!edge->postfixRef())
             m_worklist.append(edge.node());
     }
     
+    void countNode(Node* node)
+    {
+        if (node->postfixRef())
+            return;
+        m_worklist.append(node);
+    }
+    
     void countEdge(Node*, Edge edge)
     {
         // Don't count edges that are already counted for their type checks.
-        if (!(edge.isProved() || edge.useKind() == UntypedUse))
-            return;
-        
-        if (edge->postfixRef())
+        if (edge.willHaveCheck())
             return;
-        m_worklist.append(edge.node());
+        countNode(edge.node());
     }
     
     void eliminateIrrelevantPhantomChildren(Node* node)
@@ -181,7 +212,7 @@ private:
             Edge edge = node->children.child(i);
             if (!edge)
                 continue;
-            if (edge.isProved() || edge.useKind() == UntypedUse)
+            if (edge.willNotHaveCheck())
                 node->children.removeEdge(i--);
         }
     }
index 35d78f8..eafe31f 100644 (file)
@@ -39,6 +39,8 @@ void Edge::dump(PrintStream& out) const
             out.print("Check:");
         out.print(useKind(), ":");
     }
+    if (doesKill())
+        out.print("Kill:");
     out.print(node());
 }
 
index eb835b0..e641b65 100644 (file)
@@ -39,12 +39,12 @@ class AdjacencyList;
 
 class Edge {
 public:
-    explicit Edge(Node* node = 0, UseKind useKind = UntypedUse, ProofStatus proofStatus = NeedsCheck)
+    explicit Edge(Node* node = 0, UseKind useKind = UntypedUse, ProofStatus proofStatus = NeedsCheck, KillStatus killStatus = DoesNotKill)
 #if USE(JSVALUE64)
-        : m_encodedWord(makeWord(node, useKind, proofStatus))
+        : m_encodedWord(makeWord(node, useKind, proofStatus, killStatus))
 #else
         : m_node(node)
-        , m_encodedWord(makeWord(useKind, proofStatus))
+        , m_encodedWord(makeWord(useKind, proofStatus, killStatus))
 #endif
     {
     }
@@ -61,7 +61,7 @@ public:
     void setNode(Node* node)
     {
 #if USE(JSVALUE64)
-        m_encodedWord = makeWord(node, useKind(), proofStatus());
+        m_encodedWord = makeWord(node, useKind(), proofStatus(), killStatus());
 #else
         m_node = node;
 #endif
@@ -71,9 +71,9 @@ public:
     {
 #if USE(JSVALUE64)
         unsigned masked = m_encodedWord & (((1 << shift()) - 1));
-        unsigned shifted = masked >> 1;
+        unsigned shifted = masked >> 2;
 #else
-        unsigned shifted = static_cast<UseKind>(m_encodedWord) >> 1;
+        unsigned shifted = static_cast<UseKind>(m_encodedWord) >> 2;
 #endif
         ASSERT(shifted < static_cast<unsigned>(LastUseKind));
         UseKind result = static_cast<UseKind>(shifted);
@@ -89,9 +89,9 @@ public:
     {
         ASSERT(node());
 #if USE(JSVALUE64)
-        m_encodedWord = makeWord(node(), useKind, proofStatus());
+        m_encodedWord = makeWord(node(), useKind, proofStatus(), killStatus());
 #else
-        m_encodedWord = makeWord(useKind, proofStatus());
+        m_encodedWord = makeWord(useKind, proofStatus(), killStatus());
 #endif
     }
     
@@ -108,9 +108,9 @@ public:
     {
         ASSERT(node());
 #if USE(JSVALUE64)
-        m_encodedWord = makeWord(node(), useKind(), proofStatus);
+        m_encodedWord = makeWord(node(), useKind(), proofStatus, killStatus());
 #else
-        m_encodedWord = makeWord(useKind(), proofStatus);
+        m_encodedWord = makeWord(useKind(), proofStatus, killStatus());
 #endif
     }
     bool isProved() const
@@ -122,6 +122,36 @@ public:
         return proofStatus() == NeedsCheck;
     }
     
+    bool willNotHaveCheck() const
+    {
+        return isProved() || useKind() == UntypedUse;
+    }
+    bool willHaveCheck() const
+    {
+        return !willNotHaveCheck();
+    }
+    
+    KillStatus killStatusUnchecked() const
+    {
+        return killStatusForDoesKill(m_encodedWord & 2);
+    }
+    KillStatus killStatus() const
+    {
+        ASSERT(node());
+        return killStatusUnchecked();
+    }
+    void setKillStatus(KillStatus killStatus)
+    {
+        ASSERT(node());
+#if USE(JSVALUE64)
+        m_encodedWord = makeWord(node(), useKind(), proofStatus(), killStatus);
+#else
+        m_encodedWord = makeWord(useKind(), proofStatus(), killStatus);
+#endif
+    }
+    bool doesKill() const { return DFG::doesKill(killStatus()); }
+    bool doesNotKill() const { return !doesKill(); }
+    
     bool isSet() const { return !!node(); }
     
     typedef void* Edge::*UnspecifiedBoolType;
@@ -148,22 +178,22 @@ private:
     friend class AdjacencyList;
     
 #if USE(JSVALUE64)
-    static uint32_t shift() { return 6; }
+    static uint32_t shift() { return 7; }
     
-    static uintptr_t makeWord(Node* node, UseKind useKind, ProofStatus proofStatus)
+    static uintptr_t makeWord(Node* node, UseKind useKind, ProofStatus proofStatus, KillStatus killStatus)
     {
         ASSERT(sizeof(node) == 8);
         uintptr_t shiftedValue = bitwise_cast<uintptr_t>(node) << shift();
         ASSERT((shiftedValue >> shift()) == bitwise_cast<uintptr_t>(node));
         ASSERT(useKind >= 0 && useKind < LastUseKind);
-        ASSERT((static_cast<uintptr_t>(LastUseKind) << 1) <= (static_cast<uintptr_t>(1) << shift()));
-        return shiftedValue | (static_cast<uintptr_t>(useKind) << 1) | DFG::isProved(proofStatus);
+        ASSERT((static_cast<uintptr_t>(LastUseKind) << 2) <= (static_cast<uintptr_t>(2) << shift()));
+        return shiftedValue | (static_cast<uintptr_t>(useKind) << 2) | (DFG::doesKill(killStatus) << 1) | DFG::isProved(proofStatus);
     }
     
 #else
-    static uintptr_t makeWord(UseKind useKind, ProofStatus proofStatus)
+    static uintptr_t makeWord(UseKind useKind, ProofStatus proofStatus, KillStatus killStatus)
     {
-        return (static_cast<uintptr_t>(useKind) << 1) | DFG::isProved(proofStatus);
+        return (static_cast<uintptr_t>(useKind) << 2) | (DFG::doesKill(killStatus) << 1) | DFG::isProved(proofStatus);
     }
     
     Node* m_node;
index eccec9b..24e29f4 100644 (file)
@@ -120,6 +120,7 @@ private:
         case ValueToInt32: {
             if (node->child1()->shouldSpeculateInteger()) {
                 setUseKindAndUnboxIfProfitable<Int32Use>(node->child1());
+                node->setOpAndDefaultFlags(Identity);
                 break;
             }
             
@@ -868,6 +869,8 @@ private:
 
         case GetArrayLength:
         case Phi:
+        case Upsilon:
+        case GetArgument:
         case ForwardInt32ToDouble:
         case PhantomPutStructure:
         case GetIndexedPropertyStorage:
diff --git a/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp b/Source/JavaScriptCore/dfg/DFGFlushFormat.cpp
new file mode 100644 (file)
index 0000000..54d8e6b
--- /dev/null
@@ -0,0 +1,63 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGFlushFormat.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace WTF {
+
+using namespace JSC::DFG;
+
+void printInternal(PrintStream& out, FlushFormat format)
+{
+    switch (format) {
+    case DeadFlush:
+        out.print("DeadFlush");
+        return;
+    case FlushedInt32:
+        out.print("FlushedInt32");
+        return;
+    case FlushedDouble:
+        out.print("FlushedDouble");
+        return;
+    case FlushedCell:
+        out.print("FlushedCell");
+        return;
+    case FlushedBoolean:
+        out.print("FlushedBoolean");
+        return;
+    case FlushedJSValue:
+        out.print("FlushedJSValue");
+        return;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+} // namespace WTF
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGFlushFormat.h b/Source/JavaScriptCore/dfg/DFGFlushFormat.h
new file mode 100644 (file)
index 0000000..25a8748
--- /dev/null
@@ -0,0 +1,96 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGFlushFormat_h
+#define DFGFlushFormat_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGNodeFlags.h"
+#include "DFGUseKind.h"
+#include <wtf/PrintStream.h>
+
+namespace JSC { namespace DFG {
+
+enum FlushFormat {
+    DeadFlush,
+    FlushedInt32,
+    FlushedDouble,
+    FlushedCell,
+    FlushedBoolean,
+    FlushedJSValue
+};
+
+inline NodeFlags resultFor(FlushFormat format)
+{
+    switch (format) {
+    case DeadFlush:
+    case FlushedJSValue:
+    case FlushedCell:
+        return NodeResultJS;
+    case FlushedInt32:
+        return NodeResultInt32;
+    case FlushedDouble:
+        return NodeResultNumber;
+    case FlushedBoolean:
+        return NodeResultBoolean;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return 0;
+}
+
+inline UseKind useKindFor(FlushFormat format)
+{
+    switch (format) {
+    case DeadFlush:
+    case FlushedJSValue:
+        return UntypedUse;
+    case FlushedCell:
+        return CellUse;
+    case FlushedInt32:
+        return Int32Use;
+    case FlushedDouble:
+        return NumberUse;
+    case FlushedBoolean:
+        return BooleanUse;
+    }
+    RELEASE_ASSERT_NOT_REACHED();
+    return UntypedUse;
+}
+
+} } // namespace JSC::DFG
+
+namespace WTF {
+
+void printInternal(PrintStream&, JSC::DFG::FlushFormat);
+
+} // namespace WTF
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGFlushFormat_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.cpp b/Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.cpp
new file mode 100644 (file)
index 0000000..c9bc6d3
--- /dev/null
@@ -0,0 +1,209 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGFlushLivenessAnalysisPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class FlushLivenessAnalysisPhase : public Phase {
+public:
+    FlushLivenessAnalysisPhase(Graph& graph)
+        : Phase(graph, "flush-liveness analysis")
+    {
+    }
+    
+    bool run()
+    {
+        ASSERT(m_graph.m_form == SSA);
+        
+        // Liveness is a backwards analysis; the roots are the blocks that
+        // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
+        // use a fixpoint formulation since liveness is a rapid analysis with
+        // convergence guaranteed after O(connectivity).
+        
+        // Start by assuming that everything is dead.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            block->ssa->flushFormatAtHead.fill(DeadFlush);
+            block->ssa->flushFormatAtTail.fill(DeadFlush);
+        }
+        
+        do {
+            m_changed = false;
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
+                process(blockIndex);
+        } while (m_changed);
+        
+        Operands<FlushFormat>& root = m_graph.block(0)->ssa->flushFormatAtHead;
+        for (unsigned i = root.size(); i--;) {
+            if (root.isArgument(i)) {
+                if (root[i] == DeadFlush || root[i] == FlushedJSValue)
+                    continue;
+            } else {
+                if (root[i] == DeadFlush)
+                    continue;
+            }
+            dataLog(
+                "Bad flush liveness analysis result: bad flush liveness at root: ",
+                root, "\n");
+            dataLog("IR at time of error:\n");
+            m_graph.dump();
+            CRASH();
+        }
+        
+        return true;
+    }
+
+private:
+    void process(BlockIndex blockIndex)
+    {
+        BasicBlock* block = m_graph.block(blockIndex);
+        if (!block)
+            return;
+        
+        m_live = block->ssa->flushFormatAtTail;
+        
+        for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+            Node* node = block->at(nodeIndex);
+            
+            switch (node->op()) {
+            case SetLocal: {
+                VariableAccessData* variable = node->variableAccessData();
+                setForNode(node, variable->local(), variable->flushFormat(), DeadFlush);
+                break;
+            }
+                
+            case GetArgument: {
+                VariableAccessData* variable = node->variableAccessData();
+                setForNode(node, variable->local(), variable->flushFormat(), FlushedJSValue);
+                break;
+            }
+                
+            case Flush:
+            case GetLocal: {
+                VariableAccessData* variable = node->variableAccessData();
+                FlushFormat format = variable->flushFormat();
+                setForNode(node, variable->local(), format, format);
+                break;
+            }
+                
+            default:
+                break;
+            }
+        }
+        
+        if (m_live == block->ssa->flushFormatAtHead)
+            return;
+        
+        m_changed = true;
+        block->ssa->flushFormatAtHead = m_live;
+        for (unsigned i = block->predecessors.size(); i--;) {
+            BasicBlock* predecessor = block->predecessors[i];
+            for (unsigned j = m_live.size(); j--;) {
+                FlushFormat& predecessorFormat = predecessor->ssa->flushFormatAtTail[j];
+                FlushFormat myFormat = m_live[j];
+                
+                // Three possibilities:
+                // 1) Predecessor format is Dead, in which case it acquires our format.
+                // 2) Predecessor format is identical to our format, in which case we
+                //    do nothing.
+                // 3) Predecessor format is different from our format and it's not Dead,
+                //    in which case we have an erroneous set of Flushes and SetLocals.
+                
+                // FIXME: What if the predecessor was already processed by the fixpoint
+                // and says "not Dead" and the current block says "Dead"? We may want to
+                // revisit this, and say that this is is acceptable.
+                
+                if (predecessorFormat == DeadFlush) {
+                    predecessorFormat = myFormat;
+                    continue;
+                }
+                
+                if (predecessorFormat == myFormat)
+                    continue;
+                
+                dataLog(
+                    "Bad Flush merge at edge ", *predecessor, " -> ", *block,
+                    ", local variable r", m_live.operandForIndex(j), ": ", *predecessor,
+                    " has ", predecessorFormat, " and ", *block, " has ", myFormat, ".\n");
+                dataLog("IR at time of error:\n");
+                m_graph.dump();
+                CRASH();
+            }
+        }
+    }
+    
+    void setForNode(Node* node, int operand, FlushFormat nodeFormat, FlushFormat newFormat)
+    {
+        FlushFormat& currentFormat = m_live.operand(operand);
+        
+        // Do some useful verification here. It's OK if we think that the
+        // flush format is dead at the time that we see the node. But it's
+        // not OK if both the node and m_live see a FlushFormat and they do
+        // not agree on it.
+        
+        if (currentFormat == DeadFlush || currentFormat == nodeFormat) {
+            currentFormat = newFormat;
+            return;
+        }
+        
+        dataLog(
+            "Bad Flush merge at node ", node, ", r", operand, ": node claims ", nodeFormat,
+            " but backwards flow claims ", currentFormat, ".\n");
+        dataLog("IR at time of error:\n");
+        m_graph.dump();
+        CRASH();
+    }
+    
+    FlushFormat flushFormat(Node* node)
+    {
+        return node->variableAccessData()->flushFormat();
+    }
+    
+    bool m_changed;
+    Operands<FlushFormat> m_live;
+};
+
+bool performFlushLivenessAnalysis(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Flush-Liveness Analysis Phase");
+    return runPhase<FlushLivenessAnalysisPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.h b/Source/JavaScriptCore/dfg/DFGFlushLivenessAnalysisPhase.h
new file mode 100644 (file)
index 0000000..4d7b3c4
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGFlushLivenessAnalysisPhase_h
+#define DFGFlushLivenessAnalysisPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Computes BasicBlock::ssa->flushFormatAtHead
+
+bool performFlushLivenessAnalysis(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGFlushLivenessAnalysisPhase_h
+
index 36da8f5..4ab4d11 100644 (file)
@@ -32,6 +32,7 @@
 #include "FunctionExecutableDump.h"
 #include "Operations.h"
 #include <wtf/CommaPrinter.h>
+#include <wtf/ListDump.h>
 
 #if ENABLE(DFG_JIT)
 
@@ -224,8 +225,8 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node)
         out.print(comma, "id", storageAccessData.identifierNumber, "{", identifiers()[storageAccessData.identifierNumber], "}");
         out.print(", ", static_cast<ptrdiff_t>(storageAccessData.offset));
     }
-    ASSERT(node->hasVariableAccessData() == node->hasLocal());
-    if (node->hasVariableAccessData()) {
+    ASSERT(node->hasVariableAccessData(*this) == node->hasLocal(*this));
+    if (node->hasVariableAccessData(*this)) {
         VariableAccessData* variableAccessData = node->variableAccessData();
         int operand = variableAccessData->operand();
         if (operandIsArgument(operand))
@@ -243,6 +244,8 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node)
     }
     if (node->hasIndexingType())
         out.print(comma, IndexingTypeDump(node->indexingType()));
+    if (node->hasPhi())
+        out.print(comma, "^", node->phi()->index());
     if (node->hasExecutionCounter())
         out.print(comma, RawPointer(node->executionCounter()));
     if (op == JSConstant) {
@@ -268,7 +271,7 @@ void Graph::dump(PrintStream& out, const char* prefix, Node* node)
     out.print(")");
 
     if (!skipped) {
-        if (node->hasVariableAccessData())
+        if (node->hasVariableAccessData(*this))
             out.print("  predicting ", SpeculationDump(node->variableAccessData()->prediction()), node->variableAccessData()->shouldUseDoubleFormat() ? ", forcing double" : "");
         else if (node->hasHeapPrediction())
             out.print("  predicting ", SpeculationDump(node->getHeapPrediction()));
@@ -321,23 +324,25 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
             out.print("\n");
         }
     }
-    out.print(prefix, "  Phi Nodes:");
-    for (size_t i = 0; i < block->phis.size(); ++i) {
-        Node* phiNode = block->phis[i];
-        if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
-            continue;
-        out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->(");
-        if (phiNode->child1()) {
-            out.print("@", phiNode->child1()->index());
-            if (phiNode->child2()) {
-                out.print(", @", phiNode->child2()->index());
-                if (phiNode->child3())
-                    out.print(", @", phiNode->child3()->index());
+    if (!block->phis.isEmpty()) {
+        out.print(prefix, "  Phi Nodes:");
+        for (size_t i = 0; i < block->phis.size(); ++i) {
+            Node* phiNode = block->phis[i];
+            if (!phiNode->shouldGenerate() && phiNodeDumpMode == DumpLivePhisOnly)
+                continue;
+            out.print(" @", phiNode->index(), "<", phiNode->refCount(), ">->(");
+            if (phiNode->child1()) {
+                out.print("@", phiNode->child1()->index());
+                if (phiNode->child2()) {
+                    out.print(", @", phiNode->child2()->index());
+                    if (phiNode->child3())
+                        out.print(", @", phiNode->child3()->index());
+                }
             }
+            out.print(")", i + 1 < block->phis.size() ? "," : "");
         }
-        out.print(")", i + 1 < block->phis.size() ? "," : "");
+        out.print("\n");
     }
-    out.print("\n");
 }
 
 void Graph::dump(PrintStream& out)
@@ -358,29 +363,57 @@ void Graph::dump(PrintStream& out)
         if (!block)
             continue;
         dumpBlockHeader(out, "", block, DumpAllPhis);
-        out.print("  vars before: ");
-        if (block->cfaHasVisited)
-            dumpOperands(block->valuesAtHead, out);
-        else
-            out.print("<empty>");
-        out.print("\n");
-        out.print("  var links: ");
-        dumpOperands(block->variablesAtHead, out);
-        out.print("\n");
+        switch (m_form) {
+        case LoadStore:
+        case ThreadedCPS: {
+            out.print("  vars before: ");
+            if (block->cfaHasVisited)
+                out.print(block->valuesAtHead);
+            else
+                out.print("<empty>");
+            out.print("\n");
+            out.print("  var links: ");
+            dumpOperands(block->variablesAtHead, out);
+            out.print("\n");
+            break;
+        }
+            
+        case SSA: {
+            RELEASE_ASSERT(block->ssa);
+            out.print("  Flush format: ", block->ssa->flushFormatAtHead, "\n");
+            out.print("  Availability: ", block->ssa->availabilityAtHead, "\n");
+            out.print("  Live: ", nodeListDump(block->ssa->liveAtHead), "\n");
+            out.print("  Values: ", nodeMapDump(block->ssa->valuesAtHead), "\n");
+            break;
+        } }
         for (size_t i = 0; i < block->size(); ++i) {
             dumpCodeOrigin(out, "", lastNode, block->at(i));
             dump(out, "", block->at(i));
             lastNode = block->at(i);
         }
-        out.print("  vars after: ");
-        if (block->cfaHasVisited)
-            dumpOperands(block->valuesAtTail, out);
-        else
-            out.print("<empty>");
-        out.print("\n");
-        out.print("  var links: ");
-        dumpOperands(block->variablesAtTail, out);
-        out.print("\n");
+        switch (m_form) {
+        case LoadStore:
+        case ThreadedCPS: {
+            out.print("  vars after: ");
+            if (block->cfaHasVisited)
+                out.print(block->valuesAtTail);
+            else
+                out.print("<empty>");
+            out.print("\n");
+            out.print("  var links: ");
+            dumpOperands(block->variablesAtTail, out);
+            out.print("\n");
+            break;
+        }
+            
+        case SSA: {
+            RELEASE_ASSERT(block->ssa);
+            out.print("  Flush format: ", block->ssa->flushFormatAtTail, "\n");
+            out.print("  Availability: ", block->ssa->availabilityAtTail, "\n");
+            out.print("  Live: ", nodeListDump(block->ssa->liveAtTail), "\n");
+            out.print("  Values: ", nodeMapDump(block->ssa->valuesAtTail), "\n");
+            break;
+        } }
     }
 }
 
@@ -493,6 +526,28 @@ void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, Va
             break;
     }
 }
+
+void Graph::addForDepthFirstSort(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, HashSet<BasicBlock*>& seen, BasicBlock* block)
+{
+    if (seen.contains(block))
+        return;
+    
+    result.append(block);
+    worklist.append(block);
+    seen.add(block);
+}
+
+void Graph::getBlocksInDepthFirstOrder(Vector<BasicBlock*>& result)
+{
+    Vector<BasicBlock*, 16> worklist;
+    HashSet<BasicBlock*> seen;
+    addForDepthFirstSort(result, worklist, seen, block(0));
+    while (!worklist.isEmpty()) {
+        BasicBlock* block = worklist.takeLast();
+        for (unsigned i = block->numSuccessors(); i--;)
+            addForDepthFirstSort(result, worklist, seen, block->successor(i));
+    }
+}
     
 } } // namespace JSC::DFG
 
index 7b0d85c..b627a44 100644 (file)
@@ -147,7 +147,7 @@ public:
         if (node->op() == GetLocal)
             dethread();
         else
-            ASSERT(!node->hasVariableAccessData());
+            ASSERT(!node->hasVariableAccessData(*this));
         node->convertToConstant(constantNumber);
     }
     
@@ -406,7 +406,12 @@ public:
         
         CodeBlock* profiledBlock = baselineCodeBlockFor(node->codeOrigin);
         
-        if (node->hasLocal()) {
+        if (node->op() == GetArgument)
+            return profiledBlock->valueProfileForArgument(operandToArgument(node->local()));
+        
+        if (node->hasLocal(*this)) {
+            if (m_form == SSA)
+                return 0;
             if (!operandIsArgument(node->local()))
                 return 0;
             int argument = operandToArgument(node->local());
@@ -646,6 +651,8 @@ public:
     
     void invalidateCFG();
     
+    void getBlocksInDepthFirstOrder(Vector<BasicBlock*>& result);
+    
     Profiler::Compilation* compilation() { return m_plan.compilation.get(); }
     
     DesiredIdentifiers& identifiers() { return m_plan.identifiers; }
@@ -684,6 +691,7 @@ public:
 private:
     
     void handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock*, BasicBlock* successor);
+    void addForDepthFirstSort(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, HashSet<BasicBlock*>& seen, BasicBlock*);
     
     AddSpeculationMode addImmediateShouldSpeculateInteger(Node* add, bool variableShouldSpeculateInteger, Node* immediate)
     {
index 19c1da4..8d76c45 100644 (file)
 #if ENABLE(DFG_JIT)
 
 #include "DFGGraph.h"
+#include <wtf/Insertion.h>
 #include <wtf/Vector.h>
 
 namespace JSC { namespace DFG {
 
-class Insertion {
-public:
-    Insertion() { }
-    
-    Insertion(size_t index, Node* element)
-        : m_index(index)
-        , m_element(element)
-    {
-    }
-    
-    size_t index() const { return m_index; }
-    Node* element() const { return m_element; }
-private:
-    size_t m_index;
-    Node* m_element;
-};
+typedef WTF::Insertion<Node*> Insertion;
 
 class InsertionSet {
 public:
@@ -81,20 +67,7 @@ public:
     
     void execute(BasicBlock* block)
     {
-        if (!m_insertions.size())
-            return;
-        block->grow(block->size() + m_insertions.size());
-        size_t lastIndex = block->size();
-        for (size_t indexInInsertions = m_insertions.size(); indexInInsertions--;) {
-            Insertion& insertion = m_insertions[indexInInsertions];
-            size_t firstIndex = insertion.index() + indexInInsertions;
-            size_t indexOffset = indexInInsertions + 1;
-            for (size_t i = lastIndex; --i > firstIndex;)
-                block->at(i) = block->at(i - indexOffset);
-            block->at(firstIndex) = insertion.element();
-            lastIndex = firstIndex;
-        }
-        m_insertions.resize(0);
+        executeInsertions(*block, m_insertions);
     }
 private:
     Graph& m_graph;
diff --git a/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp b/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.cpp
new file mode 100644 (file)
index 0000000..65c4105
--- /dev/null
@@ -0,0 +1,166 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGLivenessAnalysisPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class LivenessAnalysisPhase : public Phase {
+public:
+    LivenessAnalysisPhase(Graph& graph)
+        : Phase(graph, "liveness analysis")
+    {
+    }
+    
+    bool run()
+    {
+        ASSERT(m_graph.m_form == SSA);
+        
+        // Liveness is a backwards analysis; the roots are the blocks that
+        // end in a terminal (Return/Throw/ThrowReferenceError). For now, we
+        // use a fixpoint formulation since liveness is a rapid analysis with
+        // convergence guaranteed after O(connectivity).
+        
+        // Start by assuming that everything is dead.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            block->ssa->liveAtHead.clear();
+            block->ssa->liveAtTail.clear();
+        }
+        
+        do {
+            m_changed = false;
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;)
+                process(blockIndex);
+        } while (m_changed);
+        
+        if (!m_graph.block(0)->ssa->liveAtHead.isEmpty()) {
+            dataLog(
+                "Bad liveness analysis result: live at root is not empty: ",
+                nodeListDump(m_graph.block(0)->ssa->liveAtHead), "\n");
+            dataLog("IR at time of error:\n");
+            m_graph.dump();
+            CRASH();
+        }
+        
+        return true;
+    }
+
+private:
+    void process(BlockIndex blockIndex)
+    {
+        BasicBlock* block = m_graph.block(blockIndex);
+        if (!block)
+            return;
+        
+        // FIXME: It's likely that this can be improved, for static analyses that use
+        // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
+        m_live = block->ssa->liveAtTail;
+        
+        for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+            Node* node = block->at(nodeIndex);
+            
+            // Given an Upsilon:
+            //
+            //    n: Upsilon(@x, ^p)
+            //
+            // We say that it def's @p and @n and uses @x.
+            //
+            // Given a Phi:
+            //
+            //    p: Phi()
+            //
+            // We say nothing. It's neither a use nor a def.
+            //
+            // Given a node:
+            //
+            //    n: Thingy(@a, @b, @c)
+            //
+            // We say that it def's @n and uses @a, @b, @c.
+            
+            switch (node->op()) {
+            case Upsilon: {
+                Node* phi = node->phi();
+                m_live.remove(phi);
+                m_live.remove(node);
+                m_live.add(node->child1().node());
+                break;
+            }
+                
+            case Phi: {
+                break;
+            }
+                
+            default:
+                m_live.remove(node);
+                DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
+                break;
+            }
+        }
+        
+        if (m_live == block->ssa->liveAtHead)
+            return;
+        
+        m_changed = true;
+        block->ssa->liveAtHead = m_live;
+        for (unsigned i = block->predecessors.size(); i--;)
+            block->predecessors[i]->ssa->liveAtTail.add(m_live.begin(), m_live.end());
+    }
+    
+    void addChildUse(Node*, Edge& edge)
+    {
+        addChildUse(edge);
+    }
+    
+    void addChildUse(Edge& edge)
+    {
+        edge.setKillStatus(m_live.add(edge.node()).isNewEntry ? DoesKill : DoesNotKill);
+    }
+    
+    bool m_changed;
+    HashSet<Node*> m_live;
+};
+
+bool performLivenessAnalysis(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG Liveness Analysis Phase");
+    return runPhase<LivenessAnalysisPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.h b/Source/JavaScriptCore/dfg/DFGLivenessAnalysisPhase.h
new file mode 100644 (file)
index 0000000..8066112
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGLivenessAnalysisPhase_h
+#define DFGLivenessAnalysisPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Computes BasicBlock::ssa->liveAtHead/liveAtTail.
+
+bool performLivenessAnalysis(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGLivenessAnalysisPhase_h
+
index 56eb921..12e7a67 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGGraph.h"
 #include "DFGNodeAllocator.h"
 
 namespace JSC { namespace DFG {
@@ -37,6 +38,26 @@ unsigned Node::index() const
     return NodeAllocator::allocatorOf(this)->indexOf(this);
 }
 
+bool Node::hasVariableAccessData(Graph& graph)
+{
+    switch (op()) {
+    case Phi:
+        return graph.m_form != SSA;
+    case GetLocal:
+    case GetArgument:
+    case SetLocal:
+    case MovHint:
+    case MovHintAndCheck:
+    case ZombieHint:
+    case SetArgument:
+    case Flush:
+    case PhantomLocal:
+        return true;
+    default:
+        return false;
+    }
+}
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index be80fb7..171d754 100644 (file)
 #include "SpeculatedType.h"
 #include "StructureSet.h"
 #include "ValueProfile.h"
+#include <wtf/ListDump.h>
 
 namespace JSC { namespace DFG {
 
+class Graph;
 struct BasicBlock;
 
 struct StructureTransitionData {
@@ -500,32 +502,14 @@ struct Node {
         }
     }
     
-    bool hasVariableAccessData()
+    bool hasVariableAccessData(Graph&);
+    bool hasLocal(Graph& graph)
     {
-        switch (op()) {
-        case GetLocal:
-        case SetLocal:
-        case MovHint:
-        case MovHintAndCheck:
-        case ZombieHint:
-        case Phi:
-        case SetArgument:
-        case Flush:
-        case PhantomLocal:
-            return true;
-        default:
-            return false;
-        }
-    }
-    
-    bool hasLocal()
-    {
-        return hasVariableAccessData();
+        return hasVariableAccessData(graph);
     }
     
     VariableAccessData* variableAccessData()
     {
-        ASSERT(hasVariableAccessData());
         return reinterpret_cast<VariableAccessData*>(m_opInfo)->find();
     }
     
@@ -540,6 +524,17 @@ struct Node {
         return static_cast<VirtualRegister>(m_opInfo);
     }
     
+    bool hasPhi()
+    {
+        return op() == Upsilon;
+    }
+    
+    Node* phi()
+    {
+        ASSERT(hasPhi());
+        return bitwise_cast<Node*>(m_opInfo);
+    }
+    
     bool hasIdentifier()
     {
         switch (op()) {
@@ -775,16 +770,16 @@ struct Node {
         m_opInfo2 = bitwise_cast<uintptr_t>(block);
     }
     
-    BasicBlock* takenBlock()
+    BasicBlock*& takenBlock()
     {
         ASSERT(isBranch() || isJump());
-        return bitwise_cast<BasicBlock*>(m_opInfo);
+        return *bitwise_cast<BasicBlock**>(&m_opInfo);
     }
     
-    BasicBlock* notTakenBlock()
+    BasicBlock*& notTakenBlock()
     {
         ASSERT(isBranch());
-        return bitwise_cast<BasicBlock*>(m_opInfo2);
+        return *bitwise_cast<BasicBlock**>(&m_opInfo2);
     }
     
     SwitchData* switchData()
@@ -807,7 +802,7 @@ struct Node {
         }
     }
     
-    BasicBlock* successor(unsigned index)
+    BasicBlock*& successor(unsigned index)
     {
         if (isSwitch()) {
             if (index < switchData()->cases.size())
@@ -822,11 +817,11 @@ struct Node {
             return notTakenBlock();
         default:
             RELEASE_ASSERT_NOT_REACHED();
-            return 0;
+            return takenBlock();
         }
     }
     
-    BasicBlock* successorForCondition(bool condition)
+    BasicBlock*& successorForCondition(bool condition)
     {
         ASSERT(isBranch());
         return condition ? takenBlock() : notTakenBlock();
@@ -1406,6 +1401,23 @@ public:
     Node* replacement;
 };
 
+inline bool nodeComparator(Node* a, Node* b)
+{
+    return a->index() < b->index();
+}
+
+template<typename T>
+CString nodeListDump(const T& nodeList)
+{
+    return sortedListDump(nodeList, nodeComparator);
+}
+
+template<typename T>
+CString nodeMapDump(const T& nodeMap)
+{
+    return sortedMapDump(nodeMap, nodeComparator);
+}
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index c5753d2..714675e 100644 (file)
@@ -34,7 +34,7 @@ namespace JSC { namespace DFG {
 
 void dumpNodeFlags(PrintStream& out, NodeFlags flags)
 {
-    if (!(flags ^ NodeDoesNotExit)) {
+    if (!((flags & ~NodeRelevantToOSR) ^ NodeDoesNotExit)) {
         out.print("<empty>");
         return;
     }
index 98a6bb9..b67f535 100644 (file)
@@ -62,7 +62,9 @@ namespace JSC { namespace DFG {
     macro(MovHintAndCheck, NodeMustGenerate | NodeExitsForward) \
     macro(MovHint, NodeDoesNotExit) \
     macro(ZombieHint, NodeDoesNotExit) \
+    macro(GetArgument, NodeResultJS | NodeMustGenerate) \
     macro(Phantom, NodeMustGenerate) \
+    macro(Upsilon, NodeDoesNotExit | NodeRelevantToOSR) \
     macro(Phi, NodeDoesNotExit | NodeRelevantToOSR) \
     macro(Flush, NodeMustGenerate | NodeDoesNotExit) \
     macro(PhantomLocal, NodeMustGenerate | NodeDoesNotExit) \
diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.cpp
new file mode 100644 (file)
index 0000000..5227b80
--- /dev/null
@@ -0,0 +1,135 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGOSRAvailabilityAnalysisPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class OSRAvailabilityAnalysisPhase : public Phase {
+public:
+    OSRAvailabilityAnalysisPhase(Graph& graph)
+        : Phase(graph, "OSR availability analysis")
+    {
+    }
+    
+    bool run()
+    {
+        ASSERT(m_graph.m_form == SSA);
+        
+        Vector<BasicBlock*> depthFirst;
+        m_graph.getBlocksInDepthFirstOrder(depthFirst);
+        
+        for (unsigned i = 0; i < depthFirst.size(); ++i) {
+            BasicBlock* block = depthFirst[i];
+            block->ssa->availabilityAtHead.fill(0);
+            block->ssa->availabilityAtTail.fill(0);
+        }
+        
+        for (unsigned i = 0; i < depthFirst.size(); ++i) {
+            BasicBlock* block = depthFirst[i];
+            
+            // We edit availabilityAtTail in-place, but first initialize it to
+            // availabilityAtHead.
+            Operands<Node*>& availability = block->ssa->availabilityAtTail;
+            availability = block->ssa->availabilityAtHead;
+            
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+                switch (node->op()) {
+                case SetLocal:
+                case MovHint:
+                case MovHintAndCheck: {
+                    availability.operand(node->local()) = node->child1().node();
+                    break;
+                }
+                    
+                case ZombieHint: {
+                    availability.operand(node->local()) = 0;
+                    break;
+                }
+                    
+                case GetArgument: {
+                    availability.operand(node->local()) = node;
+                    break;
+                }
+                    
+                default:
+                    break;
+                }
+            }
+            
+            for (unsigned j = block->numSuccessors(); j--;) {
+                BasicBlock* successor = block->successor(j);
+                Operands<Node*>& successorAvailability = successor->ssa->availabilityAtHead;
+                for (unsigned k = availability.size(); k--;) {
+                    Node* myNode = availability[k];
+                    if (!myNode)
+                        continue;
+                    
+                    if (!successor->ssa->liveAtHead.contains(myNode))
+                        continue;
+                    
+                    // Note that this may overwrite availability with a bogus node
+                    // at merge points. This is fine, since merge points have
+                    // MovHint(Phi)'s to work around this. The outcome of this is
+                    // you might have a program in which a node happens to remain
+                    // live into some block B, and separately (due to copy
+                    // propagation) just one of the predecessors of B issued a
+                    // MovHint putting that node into some local. Then in B we might
+                    // think that that node is a valid value for that local. Of
+                    // course if that local was actually live in B, B would have a
+                    // Phi for it. So essentially we'll have OSR exit dropping this
+                    // node's value into the local when we otherwise (in the DFG)
+                    // would have dropped undefined into the local. This seems
+                    // harmless.
+                    
+                    successorAvailability[k] = myNode;
+                }
+            }
+        }
+        
+        return true;
+    }
+};
+
+bool performOSRAvailabilityAnalysis(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG OSR Availability Analysis Phase");
+    return runPhase<OSRAvailabilityAnalysisPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h b/Source/JavaScriptCore/dfg/DFGOSRAvailabilityAnalysisPhase.h
new file mode 100644 (file)
index 0000000..6c37a9d
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGOSRAvailabilityAnalysisPhase_h
+#define DFGOSRAvailabilityAnalysisPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGCommon.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Computes BasicBlock::ssa->availabiltiyAtHead/Tail. This relies on liveness
+// analysis phase having been run and the graph not having been transformed
+// after that.
+
+bool performOSRAvailabilityAnalysis(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGOSRAvailabilityAnalysisPhase_h
+
index 46b3197..328f262 100644 (file)
 #include "DFGCPSRethreadingPhase.h"
 #include "DFGCSEPhase.h"
 #include "DFGConstantFoldingPhase.h"
+#include "DFGCriticalEdgeBreakingPhase.h"
 #include "DFGDCEPhase.h"
 #include "DFGFailedFinalizer.h"
+#include "DFGFlushLivenessAnalysisPhase.h"
 #include "DFGFixupPhase.h"
 #include "DFGJITCompiler.h"
+#include "DFGLivenessAnalysisPhase.h"
+#include "DFGOSRAvailabilityAnalysisPhase.h"
 #include "DFGPredictionInjectionPhase.h"
 #include "DFGPredictionPropagationPhase.h"
+#include "DFGSSAConversionPhase.h"
 #include "DFGTypeCheckHoistingPhase.h"
 #include "DFGUnificationPhase.h"
 #include "DFGValidate.h"
@@ -182,22 +187,22 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
     dfg.m_fixpointState = FixpointConverged;
 
     performStoreElimination(dfg);
-    performCPSRethreading(dfg);
-    
-    // Note that DCE is necessary even in the FTL, because only we know what is
-    // live-in-bytecode. The FTL uses this information to determine when OSR exit
-    // values should be wired to LValues, versus being wired to ExitValue::dead().
-    // This is distinct from what ZombieHint gives us: ZombieHint says that the
-    // value in the given bytecode local is always dead; the reference counts that
-    // DCE produces tell us that the value is live for a while but eventually
-    // dies, and it tells us exactly when the death point is.
-    performDCE(dfg);
 
 #if ENABLE(FTL_JIT)
     if (Options::useExperimentalFTL()
         && compileMode == CompileFunction
         && FTL::canCompile(dfg)) {
         
+        performCriticalEdgeBreaking(dfg);
+        performCPSRethreading(dfg);
+        performSSAConversion(dfg);
+        performLivenessAnalysis(dfg);
+        performCFA(dfg);
+        performDCE(dfg); // We rely on this to convert dead SetLocals into the appropriate hint, and to kill dead code that won't be recognized as dead by LLVM.
+        performLivenessAnalysis(dfg);
+        performFlushLivenessAnalysis(dfg);
+        performOSRAvailabilityAnalysis(dfg);
+        
         dumpAndVerifyGraph(dfg, "Graph just before FTL lowering:");
         
         // FIXME: Support OSR entry.
@@ -215,6 +220,8 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
     }
 #endif // ENABLE(FTL_JIT)
     
+    performCPSRethreading(dfg);
+    performDCE(dfg);
     performVirtualRegisterAllocation(dfg);
     dumpAndVerifyGraph(dfg, "Graph after optimization:");
 
index 91d2193..c116ef9 100644 (file)
@@ -81,7 +81,7 @@ public:
                     m_graph.m_plan.mustHandleValues.operandForIndex(i));
                 if (!node)
                     continue;
-                ASSERT(node->hasLocal());
+                ASSERT(node->hasLocal(m_graph));
                 node->variableAccessData()->predict(
                     speculationFromValue(m_graph.m_plan.mustHandleValues[i]));
             }
index 7ea73c2..460b9eb 100644 (file)
@@ -483,14 +483,20 @@ private:
         case ZombieHint: {
             // This node should never be visible at this stage of compilation. It is
             // inserted by fixup(), which follows this phase.
-            CRASH();
+            RELEASE_ASSERT_NOT_REACHED();
             break;
         }
         
         case Phi:
             // Phis should not be visible here since we're iterating the all-but-Phi's
             // part of basic blocks.
-            CRASH();
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+            
+        case Upsilon:
+        case GetArgument:
+            // These don't get inserted until we go into SSA.
+            RELEASE_ASSERT_NOT_REACHED();
             break;
 
         case GetScope:
@@ -551,7 +557,7 @@ private:
             break;
             
         case LastNodeType:
-            CRASH();
+            RELEASE_ASSERT_NOT_REACHED();
             break;
 #else
         default:
diff --git a/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp b/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
new file mode 100644 (file)
index 0000000..c6f1f28
--- /dev/null
@@ -0,0 +1,461 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "DFGSSAConversionPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlockInlines.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+class SSAConversionPhase : public Phase {
+    static const bool verbose = false;
+    
+public:
+    SSAConversionPhase(Graph& graph)
+        : Phase(graph, "SSA conversion")
+        , m_insertionSet(graph)
+        , m_changed(false)
+    {
+    }
+    
+    bool run()
+    {
+        RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
+        
+        // Figure out which SetLocal's need flushing. Need to do this while the
+        // Phi graph is still intact.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+                Node* node = block->at(nodeIndex);
+                if (node->op() != Flush)
+                    continue;
+                addFlushedLocalOp(node);
+            }
+        }
+        while (!m_flushedLocalOpWorklist.isEmpty()) {
+            Node* node = m_flushedLocalOpWorklist.takeLast();
+            ASSERT(m_flushedLocalOps.contains(node));
+            DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
+        }
+        
+        // Eliminate all duplicate or self-pointing Phi edges. This means that
+        // we transform:
+        //
+        // p: Phi(@n1, @n2, @n3)
+        //
+        // into:
+        //
+        // p: Phi(@x)
+        //
+        // if each @ni in {@n1, @n2, @n3} is either equal to @p to is equal
+        // to @x, for exactly one other @x. Additionally, trivial Phis (i.e.
+        // p: Phi(@x)) are forwarded, so that if have an edge to such @p, we
+        // replace it with @x. This loop does this for Phis only; later we do
+        // such forwarding for Phi references found in other nodes.
+        //
+        // See Aycock and Horspool in CC'00 for a better description of what
+        // we're doing here.
+        do {
+            m_changed = false;
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+                    Node* phi = block->phis[phiIndex];
+                    if (phi->variableAccessData()->isCaptured())
+                        continue;
+                    forwardPhiChildren(phi);
+                    deduplicateChildren(phi);
+                }
+            }
+        } while (m_changed);
+        
+        // For each basic block, for each local live at the head of that block,
+        // figure out what node we should be referring to instead of that local.
+        // If it turns out to be a non-trivial Phi, make sure that we create an
+        // SSA Phi and Upsilons in predecessor blocks. We reuse
+        // BasicBlock::variablesAtHead for tracking which nodes to refer to.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            
+            for (unsigned i = block->variablesAtHead.size(); i--;) {
+                Node* node = block->variablesAtHead[i];
+                if (!node)
+                    continue;
+                
+                VariableAccessData* variable = node->variableAccessData();
+                if (variable->isCaptured()) {
+                    // Poison this entry in variablesAtHead because we don't
+                    // want anyone to try to refer to it, if the variable is
+                    // captured.
+                    block->variablesAtHead[i] = 0;
+                    continue;
+                }
+                
+                switch (node->op()) {
+                case Phi:
+                case SetArgument:
+                    break;
+                case Flush:
+                case GetLocal:
+                case PhantomLocal:
+                    node = node->child1().node();
+                    break;
+                default:
+                    RELEASE_ASSERT_NOT_REACHED();
+                }
+                RELEASE_ASSERT(node->op() == Phi || node->op() == SetArgument);
+                
+                if (node->op() == Phi) {
+                    Edge edge = node->children.justOneChild();
+                    if (edge)
+                        node = edge.node(); // It's something from a different basic block.
+                    else {
+                        // It's a non-trivial Phi.
+                        FlushFormat format = variable->flushFormat();
+                        NodeFlags result = resultFor(format);
+                        UseKind useKind = useKindFor(format);
+                        
+                        node = m_insertionSet.insertNode(0, SpecNone, Phi, node->codeOrigin);
+                        node->mergeFlags(result);
+                        RELEASE_ASSERT((node->flags() & NodeResultMask) == result);
+                        
+                        for (unsigned j = block->predecessors.size(); j--;) {
+                            BasicBlock* predecessor = block->predecessors[j];
+                            predecessor->appendNonTerminal(
+                                m_graph, SpecNone, Upsilon, block->last()->codeOrigin,
+                                OpInfo(node), Edge(predecessor->variablesAtTail[i], useKind));
+                        }
+                        
+                        m_insertionSet.insertNode(
+                            0, SpecNone, MovHint, node->codeOrigin, OpInfo(variable),
+                            Edge(node));
+                    }
+                }
+                
+                block->variablesAtHead[i] = node;
+            }
+
+            m_insertionSet.execute(block);
+        }
+        
+        if (verbose) {
+            dataLog("Variables at head after SSA Phi insertion:\n");
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
+            }
+        }
+        
+        // At this point variablesAtHead in each block refers to either:
+        //
+        // 1) A new SSA phi in the current block.
+        // 2) A SetArgument, which will soon get converted into a GetArgument.
+        // 3) An old CPS phi in a different block.
+        //
+        // We don't have to do anything for (1) and (2), but we do need to
+        // do a replacement for (3).
+        
+        // Clear all replacements, since other phases may have used them.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
+                block->phis[phiIndex]->replacement = 0;
+            for (unsigned nodeIndex = block->size(); nodeIndex--;)
+                block->at(nodeIndex)->replacement = 0;
+        }
+        
+        // For all of the old CPS Phis, figure out what they correspond to in SSA.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+                Node* phi = block->phis[phiIndex];
+                if (verbose) {
+                    dataLog(
+                        "Considering ", phi, ", for r", phi->local(),
+                        ", and its replacement in ", *block, ", ",
+                        block->variablesAtHead.operand(phi->local()), "\n");
+                }
+                phi->replacement = block->variablesAtHead.operand(phi->local());
+            }
+        }
+        
+        // Now make sure that all variablesAtHead in each block points to the
+        // canonical SSA value. Prior to this, variablesAtHead[local] may point to
+        // an old CPS Phi in a different block.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            for (size_t i = block->variablesAtHead.size(); i--;) {
+                Node* node = block->variablesAtHead[i];
+                if (!node)
+                    continue;
+                while (node->replacement)
+                    node = node->replacement;
+                block->variablesAtHead[i] = node;
+            }
+        }
+        
+        if (verbose) {
+            dataLog("Variables at head after convergence:\n");
+            for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+                BasicBlock* block = m_graph.block(blockIndex);
+                if (!block)
+                    continue;
+                dataLog("    ", *block, ": ", block->variablesAtHead, "\n");
+            }
+        }
+        
+        // Convert operations over locals into operations over SSA nodes.
+        // - GetLocal over captured variables lose their phis.
+        // - GetLocal over uncaptured variables die and get replaced with references
+        //   to the node specified by variablesAtHead.
+        // - SetLocal gets NodeMustGenerate if it's flushed, or turns into a
+        //   MovHint otherwise.
+        // - Flush loses its children but remains, because we want to know when a
+        //   flushed SetLocal's value is no longer needed. This also makes it simpler
+        //   to reason about the format of a local, since we can just do a backwards
+        //   analysis (see FlushLivenessAnalysisPhase). As part of the backwards
+        //   analysis, we say that the type of a local can be either int32, double,
+        //   value, or dead.
+        // - PhantomLocal becomes Phantom, and its child is whatever is specified
+        //   by variablesAtHead.
+        // - SetArgument turns into GetArgument unless it's a captured variable.
+        // - Upsilons get their children fixed to refer to the true value of that local
+        //   at the end of the block. Prior to this loop, Upsilons will refer to
+        //   variableAtTail[operand], which may be any of Flush, PhantomLocal, GetLocal,
+        //   SetLocal, SetArgument, or Phi. We accomplish this by setting the
+        //   replacement pointers of all of those nodes to refer to either
+        //   variablesAtHead[operand], or the child of the SetLocal.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            
+            for (unsigned phiIndex = block->phis.size(); phiIndex--;) {
+                block->phis[phiIndex]->replacement =
+                    block->variablesAtHead.operand(block->phis[phiIndex]->local());
+            }
+            for (unsigned nodeIndex = block->size(); nodeIndex--;)
+                ASSERT(!block->at(nodeIndex)->replacement);
+            
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                Node* node = block->at(nodeIndex);
+                
+                m_graph.performSubstitution(node);
+                
+                switch (node->op()) {
+                case SetLocal: {
+                    VariableAccessData* variable = node->variableAccessData();
+                    if (variable->isCaptured() || m_flushedLocalOps.contains(node))
+                        node->mergeFlags(NodeMustGenerate);
+                    else
+                        node->setOpAndDefaultFlags(MovHint);
+                    node->replacement = node->child1().node(); // Only for Upsilons.
+                    break;
+                }
+                    
+                case GetLocal: {
+                    // It seems tempting to just do forwardPhi(GetLocal), except that we
+                    // could have created a new (SSA) Phi, and the GetLocal could still be
+                    // referring to an old (CPS) Phi. Uses variablesAtHead to tell us what
+                    // to refer to.
+                    node->children.reset();
+                    VariableAccessData* variable = node->variableAccessData();
+                    if (variable->isCaptured())
+                        break;
+                    node->convertToPhantom();
+                    node->replacement = block->variablesAtHead.operand(variable->local());
+                    break;
+                }
+                    
+                case Flush: {
+                    node->children.reset();
+                    // This is only for Upsilons. An Upsilon will only refer to a Flush if
+                    // there were no SetLocals or GetLocals in the block.
+                    node->replacement = block->variablesAtHead.operand(node->local());
+                    break;
+                }
+                    
+                case PhantomLocal: {
+                    VariableAccessData* variable = node->variableAccessData();
+                    if (variable->isCaptured())
+                        break;
+                    node->child1().setNode(block->variablesAtHead.operand(variable->local()));
+                    node->convertToPhantom();
+                    // This is only for Upsilons. An Upsilon will only refer to a
+                    // PhantomLocal if there were no SetLocals or GetLocals in the block.
+                    node->replacement = block->variablesAtHead.operand(variable->local());
+                    break;
+                }
+                    
+                case SetArgument: {
+                    VariableAccessData* variable = node->variableAccessData();
+                    if (variable->isCaptured())
+                        break;
+                    node->setOpAndDefaultFlags(GetArgument);
+                    node->mergeFlags(resultFor(node->variableAccessData()->flushFormat()));
+                    break;
+                }
+
+                default:
+                    break;
+                }
+            }
+        }
+        
+        // Free all CPS phis and reset variables vectors.
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            for (unsigned phiIndex = block->phis.size(); phiIndex--;)
+                m_graph.m_allocator.free(block->phis[phiIndex]);
+            block->phis.clear();
+            block->variablesAtHead.clear();
+            block->variablesAtTail.clear();
+            block->valuesAtHead.clear();
+            block->valuesAtHead.clear();
+            block->ssa = adoptPtr(new BasicBlock::SSAData(block));
+        }
+        
+        m_graph.m_arguments.clear();
+        
+        m_graph.m_form = SSA;
+        return true;
+    }
+
+private:
+    void forwardPhiChildren(Node* node)
+    {
+        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
+            Edge& edge = node->children.child(i);
+            if (!edge)
+                break;
+            m_changed |= forwardPhiEdge(edge);
+        }
+    }
+    
+    Node* forwardPhi(Node* node)
+    {
+        for (;;) {
+            switch (node->op()) {
+            case Phi: {
+                Edge edge = node->children.justOneChild();
+                if (!edge)
+                    return node;
+                node = edge.node();
+                break;
+            }
+            case GetLocal:
+            case SetLocal:
+                if (node->variableAccessData()->isCaptured())
+                    return node;
+                node = node->child1().node();
+                break;
+            default:
+                return node;
+            }
+        }
+    }
+    
+    bool forwardPhiEdge(Edge& edge)
+    {
+        Node* newNode = forwardPhi(edge.node());
+        if (newNode == edge.node())
+            return false;
+        edge.setNode(newNode);
+        return true;
+    }
+    
+    void deduplicateChildren(Node* node)
+    {
+        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
+            Edge edge = node->children.child(i);
+            if (!edge)
+                break;
+            if (edge == node) {
+                node->children.removeEdge(i--);
+                m_changed = true;
+                continue;
+            }
+            for (unsigned j = i + 1; j < AdjacencyList::Size; ++j) {
+                if (node->children.child(j) == edge) {
+                    node->children.removeEdge(j--);
+                    m_changed = true;
+                }
+            }
+        }
+    }
+    
+    void addFlushedLocalOp(Node* node)
+    {
+        if (m_flushedLocalOps.contains(node))
+            return;
+        m_flushedLocalOps.add(node);
+        m_flushedLocalOpWorklist.append(node);
+    }
+
+    void addFlushedLocalEdge(Node*, Edge edge)
+    {
+        addFlushedLocalOp(edge.node());
+    }
+    
+    InsertionSet m_insertionSet;
+    HashSet<Node*> m_flushedLocalOps;
+    Vector<Node*> m_flushedLocalOpWorklist;
+    bool m_changed;
+};
+
+bool performSSAConversion(Graph& graph)
+{
+    SamplingRegion samplingRegion("DFG SSA Conversion Phase");
+    return runPhase<SSAConversionPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h b/Source/JavaScriptCore/dfg/DFGSSAConversionPhase.h
new file mode 100644 (file)
index 0000000..2fa5ff4
--- /dev/null
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef DFGSSAConversionPhase_h
+#define DFGSSAConversionPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Convert ThreadedCPS form into SSA form. This results in a form that has:
+//
+// - Roughly minimal Phi's. We use the Aycock & Horspool fixpoint for
+//   converting the CPS maximal Phis into SSA minimal Phis, with the caveat
+//   that irreducible control flow may result in some missed opportunities
+//   for Phi reduction.
+//
+// - No uses of GetLocal/SetLocal except for captured variables and flushes.
+//   After this, any remaining SetLocal means Flush. PhantomLocals become
+//   Phantoms. Nodes may have children that are in another basic block.
+//
+// - MovHints are used for OSR information, and are themselves minimal.
+//   A MovHint will occur at some point after the assigning, and at Phi
+//   points.
+//
+// - Unlike conventional SSA in which Phi functions refer to predecessors
+//   and values, our SSA uses Upsilon functions to indicate values in
+//   predecessors. A merge will look like:
+//
+//   labelA:
+//       a: Thingy(...)
+//       b: Upsilon(^e, @a)
+//       Jump(labelC)
+//
+//   labelB:
+//       c: OtherThingy(...)
+//       d: Upsilon(^e, @c)
+//       Jump(labelC)
+//
+//   labelC:
+//       e: Phi()
+//
+//   Note that the Phi has no children, but the predecessors have Upsilons
+//   that have a weak reference to the Phi (^e instead of @e; we store it
+//   in the OpInfo rather than the AdjacencyList). Think of the Upsilon
+//   as "assigning" to the "variable" associated with the Phi, and that
+//   this is the one place in SSA form where you can have multiple
+//   assignments.
+//
+//   This implies some other loosenings of SSA. For example, an Upsilon
+//   may precede a Phi in the same basic block; this may arise after CFG
+//   simplification. Although it's profitable for CFG simplification (or
+//   some other phase) to remove these, it's not strictly necessary. As
+//   well, this form allows the Upsilon to be in any block that dominates
+//   the predecessor block of the Phi, which allows for block splitting to
+//   ignore the possibility of introducing an extra edge between the Phi
+//   and the predecessor (though normal SSA would allow this, also, with
+//   the caveat that the Phi predecessor block lists would have to be
+//   updated).
+//
+//   The easiest way to convert from this SSA form into a different SSA
+//   form is to redo SSA conversion for Phi functions. That is, treat each
+//   Phi in our IR as a non-SSA variable in the foreign IR (so, as an
+//   alloca in LLVM IR, for example); the Upsilons that refer to the Phi
+//   become stores and the Phis themselves become loads.
+//
+//   Fun fact: Upsilon is so named because it comes before Phi in the
+//   alphabet. It can be written as "Y".
+
+bool performSSAConversion(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGSSAConversionPhase_h
+
index 4f8519f..d164e09 100644 (file)
@@ -4404,7 +4404,6 @@ void SpeculativeJIT::compile(Node* node)
         break;
     }
 
-    case Phi:
     case Flush:
         break;
 
@@ -4841,6 +4840,9 @@ void SpeculativeJIT::compile(Node* node)
         break;
 
     case LastNodeType:
+    case Phi:
+    case Upsilon:
+    case GetArgument:
         RELEASE_ASSERT_NOT_REACHED();
         break;
     }
index 6caa2a6..a6408e9 100644 (file)
@@ -4305,7 +4305,6 @@ void SpeculativeJIT::compile(Node* node)
     }
 
     case Flush:
-    case Phi:
         break;
 
     case Breakpoint:
@@ -4699,6 +4698,9 @@ void SpeculativeJIT::compile(Node* node)
         break;
         
     case LastNodeType:
+    case Phi:
+    case Upsilon:
+    case GetArgument:
         RELEASE_ASSERT_NOT_REACHED();
         break;
     }
index e4cf6ed..cd76e70 100644 (file)
@@ -81,24 +81,28 @@ public:
             V_EQUAL((static_cast<VirtualRegister>(i), 0), static_cast<Node*>(0), root->variablesAtHead.local(i));
         
         // Validate ref counts and uses.
-        HashMap<Node*, unsigned> myRefCounts;
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
             BasicBlock* block = m_graph.block(blockIndex);
-            if (!block || !block->isReachable)
+            if (!block)
                 continue;
+            VALIDATE((block), block->isReachable);
             for (size_t i = 0; i < block->numNodes(); ++i)
-                myRefCounts.add(block->node(i), 0);
+                m_myRefCounts.add(block->node(i), 0);
         }
-        HashSet<Node*> acceptableNodes;
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
             BasicBlock* block = m_graph.block(blockIndex);
-            if (!block || !block->isReachable)
+            if (!block)
                 continue;
             for (size_t i = 0; i < block->numNodes(); ++i) {
                 Node* node = block->node(i);
-                acceptableNodes.add(node);
+                m_acceptableNodes.add(node);
                 if (!node->shouldGenerate())
                     continue;
+                if (node->op() == Upsilon) {
+                    VALIDATE((node), m_graph.m_form == SSA);
+                    if (node->phi()->shouldGenerate())
+                        m_myRefCounts.find(node)->value++;
+                }
                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                     // Phi children in LoadStore form are invalid.
                     if (m_graph.m_form == LoadStore && block->isPhiIndex(i))
@@ -108,22 +112,28 @@ public:
                     if (!edge)
                         continue;
                     
-                    myRefCounts.find(edge.node())->value++;
+                    m_myRefCounts.find(edge.node())->value++;
+                    
+                    if (m_graph.m_form == SSA) {
+                        // In SSA, all edges must hasResult().
+                        VALIDATE((node, edge), edge->hasResult());
+                        continue;
+                    }
                     
                     // Unless I'm a Flush, Phantom, GetLocal, or Phi, my children should hasResult().
                     switch (node->op()) {
                     case Flush:
                     case GetLocal:
-                        VALIDATE((node, edge), edge->hasVariableAccessData());
+                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                         break;
                     case PhantomLocal:
-                        VALIDATE((node, edge), edge->hasVariableAccessData());
+                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
                         VALIDATE((node, edge), edge->op() != SetLocal);
                         break;
                     case Phi:
-                        VALIDATE((node, edge), edge->hasVariableAccessData());
+                        VALIDATE((node, edge), edge->hasVariableAccessData(m_graph));
                         if (m_graph.m_unificationState == LocallyUnified)
                             break;
                         VALIDATE((node, edge), edge->variableAccessData() == node->variableAccessData());
@@ -148,6 +158,9 @@ public:
                         case ThreadedCPS:
                             VALIDATE((node, edge), edge->hasResult());
                             break;
+                        case SSA:
+                            RELEASE_ASSERT_NOT_REACHED();
+                            break;
                         }
                         break;
                     default:
@@ -157,9 +170,44 @@ public:
                 }
             }
         }
+        
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
             BasicBlock* block = m_graph.block(blockIndex);
-            if (!block || !block->isReachable)
+            if (!block)
+                continue;
+            for (size_t i = 0; i < block->numNodes(); ++i) {
+                Node* node = block->node(i);
+                if (m_graph.m_refCountState == ExactRefCount)
+                    V_EQUAL((node), m_myRefCounts.get(node), node->adjustedRefCount());
+                else
+                    V_EQUAL((node), node->refCount(), 1);
+            }
+        }
+        
+        switch (m_graph.m_form) {
+        case LoadStore:
+        case ThreadedCPS:
+            validateCPS();
+            break;
+            
+        case SSA:
+            // FIXME: Implement SSA verification.
+            break;
+        }
+    }
+    
+private:
+    Graph& m_graph;
+    GraphDumpMode m_graphDumpMode;
+    
+    HashMap<Node*, unsigned> m_myRefCounts;
+    HashSet<Node*> m_acceptableNodes;
+    
+    void validateCPS()
+    {
+        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
                 continue;
             
             HashSet<Node*> phisInThisBlock;
@@ -170,15 +218,11 @@ public:
                 nodesInThisBlock.add(node);
                 if (block->isPhiIndex(i))
                     phisInThisBlock.add(node);
-                if (m_graph.m_refCountState == ExactRefCount)
-                    V_EQUAL((node), myRefCounts.get(node), node->adjustedRefCount());
-                else
-                    V_EQUAL((node), node->refCount(), 1);
                 for (unsigned j = 0; j < m_graph.numChildren(node); ++j) {
                     Edge edge = m_graph.child(node, j);
                     if (!edge)
                         continue;
-                    VALIDATE((node, edge), acceptableNodes.contains(edge.node()));
+                    VALIDATE((node, edge), m_acceptableNodes.contains(edge.node()));
                 }
             }
             
@@ -228,7 +272,6 @@ public:
                     for (unsigned k = 0; k < block->predecessors.size(); ++k) {
                         BasicBlock* prevBlock = block->predecessors[k];
                         VALIDATE((block->predecessors[k]), prevBlock);
-                        VALIDATE((block->predecessors[k]), prevBlock->isReachable);
                         Node* prevNode = prevBlock->variablesAtTail.operand(local);
                         // If we have a Phi that is not referring to *this* block then all predecessors
                         // must have that local available.
@@ -274,17 +317,17 @@ public:
                 block->variablesAtHead.numberOfLocals());
             
             for (size_t i = 0; i < block->variablesAtHead.numberOfArguments(); ++i) {
-                VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData());
+                VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), block), !block->variablesAtHead.argument(i) || block->variablesAtHead.argument(i)->hasVariableAccessData(m_graph));
                 if (m_graph.m_form == ThreadedCPS)
-                    VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData());
+                    VALIDATE((static_cast<VirtualRegister>(argumentToOperand(i)), block), !block->variablesAtTail.argument(i) || block->variablesAtTail.argument(i)->hasVariableAccessData(m_graph));
                 
                 getLocalPositions.argument(i) = notSet;
                 setLocalPositions.argument(i) = notSet;
             }
             for (size_t i = 0; i < block->variablesAtHead.numberOfLocals(); ++i) {
-                VALIDATE((static_cast<VirtualRegister>(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData());
+                VALIDATE((static_cast<VirtualRegister>(i), block), !block->variablesAtHead.local(i) || block->variablesAtHead.local(i)->hasVariableAccessData(m_graph));
                 if (m_graph.m_form == ThreadedCPS)
-                    VALIDATE((static_cast<VirtualRegister>(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData());
+                    VALIDATE((static_cast<VirtualRegister>(i), block), !block->variablesAtTail.local(i) || block->variablesAtTail.local(i)->hasVariableAccessData(m_graph));
 
                 getLocalPositions.local(i) = notSet;
                 setLocalPositions.local(i) = notSet;
@@ -321,7 +364,7 @@ public:
                         break;
                     // Ignore GetLocal's that we know to be dead, but that the graph
                     // doesn't yet know to be dead.
-                    if (!myRefCounts.get(node))
+                    if (!m_myRefCounts.get(node))
                         break;
                     if (m_graph.m_form == ThreadedCPS)
                         VALIDATE((node, block), getLocalPositions.operand(node->local()) == notSet);
@@ -355,10 +398,6 @@ public:
         }
     }
     
-private:
-    Graph& m_graph;
-    GraphDumpMode m_graphDumpMode;
-    
     void checkOperand(
         BasicBlock* block, Operands<size_t>& getLocalPositions,
         Operands<size_t>& setLocalPositions, int operand)
index 1d39e60..5900804 100644 (file)
@@ -27,6 +27,7 @@
 #define DFGVariableAccessData_h
 
 #include "DFGDoubleFormatState.h"
+#include "DFGFlushFormat.h"
 #include "DFGNodeFlags.h"
 #include "Operands.h"
 #include "SpeculatedType.h"
@@ -318,6 +319,29 @@ public:
         return checkAndSet(m_flags, m_flags | newFlags);
     }
     
+    FlushFormat flushFormat()
+    {
+        ASSERT(find() == this);
+        
+        if (!shouldUnboxIfPossible())
+            return FlushedJSValue;
+        
+        if (shouldUseDoubleFormat())
+            return FlushedDouble;
+        
+        SpeculatedType prediction = argumentAwarePrediction();
+        if (isInt32Speculation(prediction))
+            return FlushedInt32;
+        
+        if (isCellSpeculation(prediction))
+            return FlushedCell;
+        
+        if (isBooleanSpeculation(prediction))
+            return FlushedBoolean;
+        
+        return FlushedJSValue;
+    }
+    
 private:
     // This is slightly space-inefficient, since anything we're unified with
     // will have the same operand and should have the same prediction. But
index 2fa80c0..e7d7cb9 100644 (file)
@@ -82,6 +82,8 @@ inline bool canCompile(Node* node)
     case Jump:
     case ForceOSRExit:
     case ForwardForceOSRExit:
+    case Phi:
+    case Upsilon:
         // These are OK.
         break;
     case GetArrayLength:
index 557ebc0..c5ee509 100644 (file)
 #include "FTLAbstractHeapRepository.h"
 #include "FTLExitThunkGenerator.h"
 #include "FTLFormattedValue.h"
+#include "FTLLoweredNodeValue.h"
 #include "FTLOutput.h"
 #include "FTLThunks.h"
 #include "FTLValueSource.h"
 #include "LinkBuffer.h"
 #include "Operations.h"
+#include <wtf/ProcessID.h>
 
 namespace JSC { namespace FTL {
 
 using namespace DFG;
 
+static int compileCounter;
+
 // Using this instead of typeCheck() helps to reduce the load on LLVM, by creating
 // significantly less dead code.
 #define FTL_TYPE_CHECK(lowValue, highValue, typesPassedThrough, failCondition) do { \
@@ -61,10 +65,6 @@ public:
         , m_ftlState(state)
         , m_heaps(state.context)
         , m_out(state.context)
-        , m_localsBoolean(OperandsLike, state.graph.block(0)->variablesAtHead)
-        , m_locals32(OperandsLike, state.graph.block(0)->variablesAtHead)
-        , m_locals64(OperandsLike, state.graph.block(0)->variablesAtHead)
-        , m_localsDouble(OperandsLike, state.graph.block(0)->variablesAtHead)
         , m_valueSources(OperandsLike, state.graph.block(0)->variablesAtHead)
         , m_lastSetOperand(std::numeric_limits<int>::max())
         , m_exitThunkGenerator(state)
@@ -74,26 +74,30 @@ public:
     
     void lower()
     {
+        CString name;
+        if (verboseCompilationEnabled()) {
+            name = toCString(
+                "jsBody_", atomicIncrement(&compileCounter), "_", codeBlock()->inferredName(),
+                "_", codeBlock()->hash());
+        } else
+            name = "jsBody";
+        
+        m_graph.m_dominators.computeIfNecessary(m_graph);
+        
         m_ftlState.module =
-            LLVMModuleCreateWithNameInContext("jsBody", m_ftlState.context);
+            LLVMModuleCreateWithNameInContext(name.data(), m_ftlState.context);
         
         m_ftlState.function = addFunction(
-            m_ftlState.module, "jsBody", functionType(m_out.int64, m_out.intPtr));
+            m_ftlState.module, name.data(), functionType(m_out.int64, m_out.intPtr));
         setFunctionCallingConv(m_ftlState.function, LLVMCCallConv);
         
         m_out.initialize(m_ftlState.module, m_ftlState.function, m_heaps);
         
         m_prologue = appendBasicBlock(m_ftlState.context, m_ftlState.function);
         m_out.appendTo(m_prologue);
-        for (unsigned index = m_localsBoolean.size(); index--;) {
-            m_localsBoolean[index] = buildAlloca(m_out.m_builder, m_out.boolean);
-            m_locals32[index] = buildAlloca(m_out.m_builder, m_out.int32);
-            m_locals64[index] = buildAlloca(m_out.m_builder, m_out.int64);
-            m_localsDouble[index] = buildAlloca(m_out.m_builder, m_out.doubleType);
-        }
+        createPhiVariables();
         
         m_initialization = appendBasicBlock(m_ftlState.context, m_ftlState.function);
-        m_argumentChecks = appendBasicBlock(m_ftlState.context, m_ftlState.function);
 
         m_callFrame = m_out.param(0);
         m_tagTypeNumber = m_out.constInt64(TagTypeNumber);
@@ -104,23 +108,19 @@ public:
             if (!m_highBlock)
                 continue;
             m_blocks.add(m_highBlock, FTL_NEW_BLOCK(m_out, ("Block ", *m_highBlock)));
-            addFlushedLocalOpRoots();
         }
         
-        closeOverFlushedLocalOps();
-        
-        m_out.appendTo(m_argumentChecks, lowBlock(m_graph.block(0)));
-
-        transferAndCheckArguments();
-        
-        m_out.jump(lowBlock(m_graph.block(0)));
-        
-        for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
-            compileBlock(blockIndex);
+        Vector<BasicBlock*> depthFirst;
+        m_graph.getBlocksInDepthFirstOrder(depthFirst);
+        for (unsigned i = 0; i < depthFirst.size(); ++i)
+            compileBlock(depthFirst[i]);
         
         // And now complete the initialization block.
         linkOSRExitsAndCompleteInitializationBlocks();
 
+        if (Options::dumpLLVMIR())
+            dumpModule(m_ftlState.module);
+        
         if (verboseCompilationEnabled())
             m_ftlState.dumpState("after lowering");
         if (validationEnabled())
@@ -129,99 +129,53 @@ public:
 
 private:
     
-    void addFlushedLocalOpRoots()
+    void createPhiVariables()
     {
-        for (unsigned nodeIndex = m_highBlock->size(); nodeIndex--;) {
-            Node* node = m_highBlock->at(nodeIndex);
-            if (node->op() != Flush)
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
                 continue;
-            addFlushedLocalOp(node);
-        }
-    }
-    
-    void closeOverFlushedLocalOps()
-    {
-        while (!m_flushedLocalOpWorklist.isEmpty()) {
-            Node* node = m_flushedLocalOpWorklist.last();
-            m_flushedLocalOpWorklist.removeLast();
-            
-            ASSERT(m_flushedLocalOps.contains(node));
-            
-            DFG_NODE_DO_TO_CHILDREN(m_graph, node, addFlushedLocalEdge);
-        }
-    }
-    
-    void addFlushedLocalOp(Node* node)
-    {
-        if (m_flushedLocalOps.contains(node))
-            return;
-        m_flushedLocalOps.add(node);
-        m_flushedLocalOpWorklist.append(node);
-    }
-    void addFlushedLocalEdge(Node*, Edge edge)
-    {
-        addFlushedLocalOp(edge.node());
-    }
-    
-    void transferAndCheckArguments()
-    {
-        // While checking arguments, everything is in the stack.
-        for (unsigned i = m_valueSources.size(); i--;)
-            m_valueSources[i] = ValueSource(ValueInJSStack);
-        
-        m_codeOrigin = CodeOrigin(0);
-        m_node = 0;
-        
-        for (int i = 0; i < m_graph.m_codeBlock->numParameters(); ++i) {
-            Node* node = m_graph.m_arguments[i];
-            if (!node->shouldGenerate())
-                continue;
-            
-            VariableAccessData* variable = node->variableAccessData();
-            // If it's captured then we'll be accessing it through loads and stores
-            // anyway - there's no point in transfering it out.
-            if (variable->isCaptured())
-                continue;
-            
-            LValue jsValue = m_out.load64(addressFor(variable->local()));
-            
-            if (variable->shouldUnboxIfPossible()) {
-                RELEASE_ASSERT(!variable->shouldUseDoubleFormat());
-                
-                SpeculatedType prediction = variable->argumentAwarePrediction();
-                
-                if (isInt32Speculation(prediction)) {
-                    speculateBackward(BadType, jsValueValue(jsValue), node, isNotInt32(jsValue));
-                    m_out.set(unboxInt32(jsValue), m_locals32.operand(variable->local()));
-                    continue;
-                }
-                
-                if (isCellSpeculation(prediction)) {
-                    speculateBackward(BadType, jsValueValue(jsValue), node, isNotCell(jsValue));
-                    m_out.set(jsValue, m_locals64.operand(variable->local()));
-                    continue;
-                }
-                if (isBooleanSpeculation(prediction)) {
-                    speculateBackward(BadType, jsValueValue(jsValue), node, isNotBoolean(jsValue));
-                    m_out.set(unboxBoolean(jsValue), m_localsBoolean.operand(variable->local()));
+            for (unsigned nodeIndex = block->size(); nodeIndex--;) {
+                Node* node = block->at(nodeIndex);
+                if (node->op() != Phi)
                     continue;
+                LType type;
+                switch (node->flags() & NodeResultMask) {
+                case NodeResultNumber:
+                    type = m_out.doubleType;
+                    break;
+                case NodeResultInt32:
+                    type = m_out.int32;
+                    break;
+                case NodeResultBoolean:
+                    type = m_out.boolean;
+                    break;
+                case NodeResultJS:
+                    type = m_out.int64;
+                    break;
+                default:
+                    RELEASE_ASSERT_NOT_REACHED();
+                    break;
                 }
+                m_phis.add(node, buildAlloca(m_out.m_builder, type));
             }
-            
-            m_out.set(jsValue, m_locals64.operand(variable->local()));
         }
     }
     
-    void compileBlock(BlockIndex blockIndex)
+    void compileBlock(BasicBlock* block)
     {
-        m_highBlock = m_graph.block(blockIndex);
-        if (!m_highBlock)
+        if (!block)
             return;
         
+        if (verboseCompilationEnabled())
+            dataLog("Compiling block ", *block, "\n");
+        
+        m_highBlock = block;
+        
         LBasicBlock lowBlock = m_blocks.get(m_highBlock);
         
         m_nextHighBlock = 0;
-        for (BlockIndex nextBlockIndex = blockIndex + 1; nextBlockIndex < m_graph.numBlocks(); ++nextBlockIndex) {
+        for (BlockIndex nextBlockIndex = m_highBlock->index + 1; nextBlockIndex < m_graph.numBlocks(); ++nextBlockIndex) {
             m_nextHighBlock = m_graph.block(nextBlockIndex);
             if (m_nextHighBlock)
                 break;
@@ -241,11 +195,7 @@ private:
         
         initializeOSRExitStateForBlock();
         
-        m_int32Values.clear();
-        m_jsValueValues.clear();
-        m_booleanValues.clear();
-        m_storageValues.clear();
-        m_timeToLive.clear();
+        m_live = block->ssa->liveAtHead;
         
         m_state.reset();
         m_state.beginBasicBlock(m_highBlock);
@@ -274,12 +224,21 @@ private:
         m_direction = (m_node->flags() & NodeExitsForward) ? ForwardSpeculation : BackwardSpeculation;
         
         switch (m_node->op()) {
+        case Upsilon:
+            compileUpsilon();
+            break;
+        case Phi:
+            compilePhi();
+            break;
         case JSConstant:
             compileJSConstant();
             break;
         case WeakJSConstant:
             compileWeakJSConstant();
             break;
+        case GetArgument:
+            compileGetArgument();
+            break;
         case GetLocal:
             compileGetLocal();
             break;
@@ -445,8 +404,8 @@ private:
         if (m_node->shouldGenerate())
             DFG_NODE_DO_TO_CHILDREN(m_graph, m_node, use);
         
-        if (m_node->hasResult())
-            m_timeToLive.add(m_node, m_node->adjustedRefCount());
+        if (m_node->adjustedRefCount())
+            m_live.add(m_node);
         
         if (shouldExecuteEffects)
             m_state.executeEffects(nodeIndex);
@@ -454,73 +413,111 @@ private:
         return true;
     }
     
+    void compileUpsilon()
+    {
+        LValue destination = m_phis.get(m_node->phi());
+        
+        switch (m_node->child1().useKind()) {
+        case NumberUse:
+            m_out.set(lowDouble(m_node->child1()), destination);
+            break;
+        case Int32Use:
+            m_out.set(lowInt32(m_node->child1()), destination);
+            break;
+        case BooleanUse:
+            m_out.set(lowBoolean(m_node->child1()), destination);
+            break;
+        case CellUse:
+            m_out.set(lowCell(m_node->child1()), destination);
+            break;
+        case UntypedUse:
+            m_out.set(lowJSValue(m_node->child1()), destination);
+            break;
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
+    }
+    
+    void compilePhi()
+    {
+        LValue source = m_phis.get(m_node);
+        
+        switch (m_node->flags() & NodeResultMask) {
+        case NodeResultNumber:
+            setDouble(m_out.get(source));
+            break;
+        case NodeResultInt32:
+            setInt32(m_out.get(source));
+            break;
+        case NodeResultBoolean:
+            setBoolean(m_out.get(source));
+            break;
+        case NodeResultJS:
+            setJSValue(m_out.get(source));
+            break;
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
+    }
+    
     void compileJSConstant()
     {
         JSValue value = m_graph.valueOfJSConstant(m_node);
         if (value.isDouble())
-            m_doubleValues.add(m_node, m_out.constDouble(value.asDouble()));
+            setDouble(m_out.constDouble(value.asDouble()));
         else
-            m_jsValueValues.add(m_node, m_out.constInt64(JSValue::encode(value)));
+            setJSValue(m_out.constInt64(JSValue::encode(value)));
     }
     
     void compileWeakJSConstant()
     {
-        m_jsValueValues.add(m_node, weakPointer(m_node->weakConstant()));
+        setJSValue(weakPointer(m_node->weakConstant()));
+    }
+    
+    void compileGetArgument()
+    {
+        VariableAccessData* variable = m_node->variableAccessData();
+        int operand = variable->operand();
+
+        LValue jsValue = m_out.load64(addressFor(operand));
+
+        switch (useKindFor(variable->flushFormat())) {
+        case Int32Use:
+            speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotInt32(jsValue));
+            setInt32(unboxInt32(jsValue));
+            break;
+        case CellUse:
+            speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotCell(jsValue));
+            setJSValue(jsValue);
+            break;
+        case BooleanUse:
+            speculateBackward(BadType, jsValueValue(jsValue), m_node, isNotBoolean(jsValue));
+            setBoolean(unboxBoolean(jsValue));
+            break;
+        case UntypedUse:
+            setJSValue(jsValue);
+            break;
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+            break;
+        }
     }
     
     void compileGetLocal()
     {
-        // GetLocal is one of the few nodes that may be left behind, with !shouldGenerate().
-        if (!m_node->shouldGenerate())
-            return;
+        // GetLocals arise only for captured variables.
         
         VariableAccessData* variable = m_node->variableAccessData();
-        SpeculatedType prediction = variable->argumentAwarePrediction();
         AbstractValue& value = m_state.variables().operand(variable->local());
         
-        if (prediction == SpecNone) {
-            terminate(InadequateCoverage);
-            return;
-        }
-        
-        if (value.isClear()) {
-            // FIXME: We should trap instead.
-            // https://bugs.webkit.org/show_bug.cgi?id=110383
-            terminate(InadequateCoverage);
-            return;
-        }
-        
-        if (variable->isCaptured()) {
-            if (isInt32Speculation(value.m_value))
-                m_int32Values.add(m_node, m_out.load32(payloadFor(variable->local())));
-            else
-                m_jsValueValues.add(m_node, m_out.load64(addressFor(variable->local())));
-            return;
-        }
+        RELEASE_ASSERT(variable->isCaptured());
         
-        if (variable->shouldUnboxIfPossible()) {
-            if (variable->shouldUseDoubleFormat()) {
-                m_doubleValues.add(m_node, m_out.get(m_localsDouble.operand(variable->local())));
-                return;
-            }
-            
-            // Locals that are marked shouldUnboxIfPossible() that aren't also forced to
-            // use double format, and that have the right prediction, will always be
-            // speculated on SetLocal and will always be stored into an appropriately
-            // typed reference LValue.
-            if (isInt32Speculation(prediction)) {
-                m_int32Values.add(m_node, m_out.get(m_locals32.operand(variable->local())));
-                return;
-            }
-            if (isBooleanSpeculation(prediction)) {
-                m_booleanValues.add(m_node, m_out.get(m_localsBoolean.operand(variable->local())));
-                return;
-            }
-            // We skip the Cell case here because that gets treated identically to
-            // JSValues, since cells are stored untagged.
-        }
-        
-        m_jsValueValues.add(m_node, m_out.get(m_locals64.operand(variable->local())));
+        if (isInt32Speculation(value.m_value))
+            setInt32(m_out.load32(payloadFor(variable->local())));
+        else
+            setJSValue(m_out.load64(addressFor(variable->local())));
     }
     
     void compileSetLocal()
@@ -529,64 +526,40 @@ private:
         
         VariableAccessData* variable = m_node->variableAccessData();
         SpeculatedType prediction = variable->argumentAwarePrediction();
-        bool needsFlushing = m_flushedLocalOps.contains(m_node);
         
         if (variable->shouldUnboxIfPossible()) {
             if (variable->shouldUseDoubleFormat()) {
                 LValue value = lowDouble(m_node->child1());
-                m_out.set(value, m_localsDouble.operand(variable->local()));
-                if (needsFlushing) {
-                    m_out.storeDouble(value, addressFor(variable->local()));
-                    m_valueSources.operand(variable->local()) = ValueSource(DoubleInJSStack);
-                } else
-                    m_valueSources.operand(variable->local()) = ValueSource(DoubleInLocals);
+                m_out.storeDouble(value, addressFor(variable->local()));
+                m_valueSources.operand(variable->local()) = ValueSource(DoubleInJSStack);
                 return;
             }
             
             if (isInt32Speculation(prediction)) {
                 LValue value = lowInt32(m_node->child1());
-                m_out.set(value, m_locals32.operand(variable->local()));
-                if (needsFlushing) {
-                    m_out.store32(value, payloadFor(variable->local()));
-                    m_valueSources.operand(variable->local()) = ValueSource(Int32InJSStack);
-                } else
-                    m_valueSources.operand(variable->local()) = ValueSource(Int32InLocals);
+                m_out.store32(value, payloadFor(variable->local()));
+                m_valueSources.operand(variable->local()) = ValueSource(Int32InJSStack);
                 return;
             }
             if (isCellSpeculation(prediction)) {
                 LValue value = lowCell(m_node->child1());
-                m_out.set(value, m_locals64.operand(variable->local()));
-                if (needsFlushing) {
-                    m_out.store64(value, addressFor(variable->local()));
-                    m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
-                } else
-                    m_valueSources.operand(variable->local()) = ValueSource(ValueInLocals);
+                m_out.store64(value, addressFor(variable->local()));
+                m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
                 return;
             }
             if (isBooleanSpeculation(prediction)) {
-                m_out.set(lowBoolean(m_node->child1()), m_localsBoolean.operand(variable->local()));
-                if (needsFlushing) {
-                    m_out.store64(lowJSValue(m_node->child1()), addressFor(variable->local()));
-                    m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
-                } else
-                    m_valueSources.operand(variable->local()) = ValueSource(ValueInLocals);
+                speculateBoolean(m_node->child1());
+                m_out.store64(
+                    lowJSValue(m_node->child1(), ManualOperandSpeculation),
+                    addressFor(variable->local()));
+                m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
                 return;
             }
         }
         
         LValue value = lowJSValue(m_node->child1());
-        if (variable->isCaptured()) {
-            m_out.store64(value, addressFor(variable->local()));
-            m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
-            return;
-        }
-        
-        m_out.set(value, m_locals64.operand(variable->local()));
-        if (needsFlushing) {
-            m_out.store64(value, addressFor(variable->local()));
-            m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
-        } else
-            m_valueSources.operand(variable->local()) = ValueSource(ValueInLocals);
+        m_out.store64(value, addressFor(variable->local()));
+        m_valueSources.operand(variable->local()) = ValueSource(ValueInJSStack);
     }
     
     void compileMovHint()
@@ -620,19 +593,18 @@ private:
             LValue right = lowInt32(m_node->child2());
             
             if (nodeCanTruncateInteger(m_node->arithNodeFlags())) {
-                m_int32Values.add(m_node, m_out.add(left, right));
+                setInt32(m_out.add(left, right));
                 break;
             }
             
             LValue result = m_out.addWithOverflow32(left, right);
             speculate(Overflow, noValue(), 0, m_out.extractValue(result, 1));
-            m_int32Values.add(m_node, m_out.extractValue(result, 0));
+            setInt32(m_out.extractValue(result, 0));
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(
-                m_node,
+            setDouble(
                 m_out.doubleAdd(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             break;
         }
@@ -651,19 +623,18 @@ private:
             LValue right = lowInt32(m_node->child2());
             
             if (nodeCanTruncateInteger(m_node->arithNodeFlags())) {
-                m_int32Values.add(m_node, m_out.sub(left, right));
+                setInt32(m_out.sub(left, right));
                 break;
             }
             
             LValue result = m_out.subWithOverflow32(left, right);
             speculate(Overflow, noValue(), 0, m_out.extractValue(result, 1));
-            m_int32Values.add(m_node, m_out.extractValue(result, 0));
+            setInt32(m_out.extractValue(result, 0));
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(
-                m_node,
+            setDouble(
                 m_out.doubleSub(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             break;
         }
@@ -703,13 +674,12 @@ private:
                 m_out.appendTo(continuation, lastNext);
             }
             
-            m_int32Values.add(m_node, result);
+            setInt32(result);
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(
-                m_node,
+            setDouble(
                 m_out.doubleMul(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             break;
         }
@@ -800,13 +770,12 @@ private:
             
             m_out.appendTo(done, lastNext);
             
-            m_int32Values.add(m_node, m_out.phi(m_out.int32, results));
+            setInt32(m_out.phi(m_out.int32, results));
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(
-                m_node,
+            setDouble(
                 m_out.doubleDiv(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             break;
         }
@@ -891,13 +860,12 @@ private:
             
             m_out.appendTo(done, lastNext);
             
-            m_int32Values.add(m_node, m_out.phi(m_out.int32, results));
+            setInt32(m_out.phi(m_out.int32, results));
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(
-                m_node,
+            setDouble(
                 m_out.doubleRem(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             break;
         }
@@ -915,8 +883,7 @@ private:
             LValue left = lowInt32(m_node->child1());
             LValue right = lowInt32(m_node->child2());
             
-            m_int32Values.add(
-                m_node,
+            setInt32(
                 m_out.select(
                     m_node->op() == ArithMin
                         ? m_out.lessThan(left, right)
@@ -950,7 +917,7 @@ private:
             m_out.jump(continuation);
             
             m_out.appendTo(continuation, lastNext);
-            m_doubleValues.add(m_node, m_out.phi(m_out.doubleType, results));
+            setDouble(m_out.phi(m_out.doubleType, results));
             break;
         }
             
@@ -971,12 +938,12 @@ private:
             
             speculate(Overflow, noValue(), 0, m_out.equal(result, m_out.constInt32(1 << 31)));
             
-            m_int32Values.add(m_node, result);
+            setInt32(result);
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(m_node, m_out.doubleAbs(lowDouble(m_node->child1())));
+            setDouble(m_out.doubleAbs(lowDouble(m_node->child1())));
             break;
         }
             
@@ -1003,12 +970,12 @@ private:
                 result = m_out.extractValue(overflowResult, 0);
             }
             
-            m_int32Values.add(m_node, result);
+            setInt32(result);
             break;
         }
             
         case NumberUse: {
-            m_doubleValues.add(m_node, m_out.doubleNeg(lowDouble(m_node->child1())));
+            setDouble(m_out.doubleNeg(lowDouble(m_node->child1())));
             break;
         }
             
@@ -1020,47 +987,38 @@ private:
     
     void compileBitAnd()
     {
-        m_int32Values.add(
-            m_node, m_out.bitAnd(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
+        setInt32(m_out.bitAnd(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
     }
     
     void compileBitOr()
     {
-        m_int32Values.add(
-            m_node, m_out.bitOr(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
+        setInt32(m_out.bitOr(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
     }
     
     void compileBitXor()
     {
-        m_int32Values.add(
-            m_node, m_out.bitXor(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
+        setInt32(m_out.bitXor(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
     }
     
     void compileBitRShift()
     {
-        m_int32Values.add(
-            m_node,
-            m_out.aShr(
-                lowInt32(m_node->child1()),
-                m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
+        setInt32(m_out.aShr(
+            lowInt32(m_node->child1()),
+            m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
     }
     
     void compileBitLShift()
     {
-        m_int32Values.add(
-            m_node,
-            m_out.shl(
-                lowInt32(m_node->child1()),
-                m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
+        setInt32(m_out.shl(
+            lowInt32(m_node->child1()),
+            m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
     }
     
     void compileBitURShift()
     {
-        m_int32Values.add(
-            m_node,
-            m_out.lShr(
-                lowInt32(m_node->child1()),
-                m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
+        setInt32(m_out.lShr(
+            lowInt32(m_node->child1()),
+            m_out.bitAnd(lowInt32(m_node->child2()), m_out.constInt32(31))));
     }
     
     void compileUInt32ToNumber()
@@ -1068,14 +1026,14 @@ private:
         LValue value = lowInt32(m_node->child1());
 
         if (!nodeCanSpeculateInteger(m_node->arithNodeFlags())) {
-            m_doubleValues.add(m_node, m_out.unsignedToDouble(value));
+            setDouble(m_out.unsignedToDouble(value));
             return;
         }
         
         speculateForward(
             Overflow, noValue(), 0, m_out.lessThan(value, m_out.int32Zero),
             FormattedValue(ValueFormatUInt32, value));
-        m_int32Values.add(m_node, value);
+        setInt32(value);
     }
     
     void compileInt32ToDouble()
@@ -1087,7 +1045,7 @@ private:
         // contemporaneous low-level representations. So, this gives child1 a double
         // representation and then forwards that representation to m_node.
         
-        m_doubleValues.add(m_node, lowDouble(m_node->child1()));
+        setDouble(lowDouble(m_node->child1()));
     }
     
     void compileCheckStructure()
@@ -1215,8 +1173,7 @@ private:
     
     void compileGetButterfly()
     {
-        m_storageValues.add(
-            m_node, m_out.loadPtr(lowCell(m_node->child1()), m_heaps.JSObject_butterfly));
+        setStorage(m_out.loadPtr(lowCell(m_node->child1()), m_heaps.JSObject_butterfly));
     }
     
     void compileGetArrayLength()
@@ -1225,8 +1182,7 @@ private:
         case Array::Int32:
         case Array::Double:
         case Array::Contiguous: {
-            m_int32Values.add(
-                m_node, m_out.load32(lowStorage(m_node->child2()), m_heaps.Butterfly_publicLength));
+            setInt32(m_out.load32(lowStorage(m_node->child2()), m_heaps.Butterfly_publicLength));
             break;
         }
             
@@ -1256,7 +1212,7 @@ private:
                     storage, m_out.zeroExt(index, m_out.intPtr),
                     m_state.forNode(m_node->child2()).m_value));
                 speculate(LoadFromHole, noValue(), 0, m_out.isZero64(result));
-                m_jsValueValues.add(m_node, result);
+                setJSValue(result);
                 return;
             }
             
@@ -1288,7 +1244,7 @@ private:
                         LoadFromHole, noValue(), 0,
                         m_out.doubleNotEqualOrUnordered(result, result));
                 }
-                m_doubleValues.add(m_node, result);
+                setDouble(result);
                 break;
             }
             
@@ -1388,8 +1344,7 @@ private:
         StorageAccessData& data =
             m_graph.m_storageAccessData[m_node->storageAccessDataIndex()];
         
-        m_jsValueValues.add(
-            m_node,
+        setJSValue(
             m_out.load64(
                 m_out.address(
                     m_heaps.properties[data.identifierNumber],
@@ -1412,7 +1367,7 @@ private:
     
     void compileGetGlobalVar()
     {
-        m_jsValueValues.add(m_node, m_out.load64(m_out.absolute(m_node->registerPointer())));
+        setJSValue(m_out.load64(m_out.absolute(m_node->registerPointer())));
     }
     
     void compilePutGlobalVar()
@@ -1437,30 +1392,27 @@ private:
     {
         ASSERT(m_graph.valueOfJSConstant(m_node->child2().node()).isNull());
         masqueradesAsUndefinedWatchpointIfIsStillValid();
-        m_booleanValues.add(
-            m_node, equalNullOrUndefined(
+        setBoolean(
+            equalNullOrUndefined(
                 m_node->child1(), AllCellsAreFalse, EqualNullOrUndefined));
     }
     
     void compileCompareStrictEq()
     {
         if (m_node->isBinaryUseKind(Int32Use)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.equal(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
             return;
         }
         
         if (m_node->isBinaryUseKind(NumberUse)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.doubleEqual(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
         }
         
         if (m_node->isBinaryUseKind(ObjectUse)) {
             masqueradesAsUndefinedWatchpointIfIsStillValid();
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.equal(
                     lowNonNullObject(m_node->child1()),
                     lowNonNullObject(m_node->child2())));
@@ -1477,19 +1429,16 @@ private:
         if (constant.isUndefinedOrNull()
             && !masqueradesAsUndefinedWatchpointIfIsStillValid()) {
             if (constant.isNull()) {
-                m_booleanValues.add(
-                    m_node, equalNullOrUndefined(m_node->child1(), AllCellsAreFalse, EqualNull));
+                setBoolean(equalNullOrUndefined(m_node->child1(), AllCellsAreFalse, EqualNull));
                 return;
             }
         
             ASSERT(constant.isUndefined());
-            m_booleanValues.add(
-                m_node, equalNullOrUndefined(m_node->child1(), AllCellsAreFalse, EqualUndefined));
+            setBoolean(equalNullOrUndefined(m_node->child1(), AllCellsAreFalse, EqualUndefined));
             return;
         }
         
-        m_booleanValues.add(
-            m_node,
+        setBoolean(
             m_out.equal(
                 lowJSValue(m_node->child1()),
                 m_out.constInt64(JSValue::encode(constant))));
@@ -1498,15 +1447,13 @@ private:
     void compileCompareLess()
     {
         if (m_node->isBinaryUseKind(Int32Use)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.lessThan(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
             return;
         }
         
         if (m_node->isBinaryUseKind(NumberUse)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.doubleLessThan(lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             return;
         }
@@ -1517,15 +1464,13 @@ private:
     void compileCompareLessEq()
     {
         if (m_node->isBinaryUseKind(Int32Use)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.lessThanOrEqual(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
             return;
         }
         
         if (m_node->isBinaryUseKind(NumberUse)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.doubleLessThanOrEqual(
                     lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             return;
@@ -1537,15 +1482,13 @@ private:
     void compileCompareGreater()
     {
         if (m_node->isBinaryUseKind(Int32Use)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.greaterThan(lowInt32(m_node->child1()), lowInt32(m_node->child2())));
             return;
         }
         
         if (m_node->isBinaryUseKind(NumberUse)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.doubleGreaterThan(
                     lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             return;
@@ -1557,16 +1500,14 @@ private:
     void compileCompareGreaterEq()
     {
         if (m_node->isBinaryUseKind(Int32Use)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.greaterThanOrEqual(
                     lowInt32(m_node->child1()), lowInt32(m_node->child2())));
             return;
         }
         
         if (m_node->isBinaryUseKind(NumberUse)) {
-            m_booleanValues.add(
-                m_node,
+            setBoolean(
                 m_out.doubleGreaterThanOrEqual(
                     lowDouble(m_node->child1()), lowDouble(m_node->child2())));
             return;
@@ -1577,7 +1518,7 @@ private:
     
     void compileLogicalNot()
     {
-        m_booleanValues.add(m_node, m_out.bitNot(boolify(m_node->child1())));
+        setBoolean(m_out.bitNot(boolify(m_node->child1())));
     }
     
     void compileJump()
@@ -1999,14 +1940,17 @@ private:
     {
         ASSERT_UNUSED(mode, mode == ManualOperandSpeculation || (edge.useKind() == Int32Use || edge.useKind() == KnownInt32Use));
         
-        if (LValue result = m_int32Values.get(edge.node()))
-            return result;
+        LoweredNodeValue value = m_int32Values.get(edge.node());
+        if (isValid(value))
+            return value.value();
         
-        if (LValue boxedResult = m_jsValueValues.get(edge.node())) {
+        value = m_jsValueValues.get(edge.node());
+        if (isValid(value)) {
+            LValue boxedResult = value.value();
             FTL_TYPE_CHECK(
                 jsValueValue(boxedResult), edge, SpecInt32, isNotInt32(boxedResult));
             LValue result = unboxInt32(boxedResult);
-            m_int32Values.add(edge.node(), result);
+            setInt32(edge.node(), result);
             return result;
         }
 
@@ -2019,10 +1963,12 @@ private:
     {
         ASSERT_UNUSED(mode, mode == ManualOperandSpeculation || isCell(edge.useKind()));
         
-        if (LValue uncheckedResult = m_jsValueValues.get(edge.node())) {
+        LoweredNodeValue value = m_jsValueValues.get(edge.node());
+        if (isValid(value)) {
+            LValue uncheckedValue = value.value();
             FTL_TYPE_CHECK(
-                jsValueValue(uncheckedResult), edge, SpecCell, isNotCell(uncheckedResult));
-            return uncheckedResult;
+                jsValueValue(uncheckedValue), edge, SpecCell, isNotCell(uncheckedValue));
+            return uncheckedValue;
         }
         
         RELEASE_ASSERT(!(m_state.forNode(edge).m_type & SpecCell));
@@ -2061,14 +2007,17 @@ private:
     {
         ASSERT_UNUSED(mode, mode == ManualOperandSpeculation || edge.useKind() == BooleanUse);
         
-        if (LValue result = m_booleanValues.get(edge.node()))
-            return result;
+        LoweredNodeValue value = m_booleanValues.get(edge.node());
+        if (isValid(value))
+            return value.value();
         
-        if (LValue unboxedResult = m_jsValueValues.get(edge.node())) {
+        value = m_jsValueValues.get(edge.node());
+        if (isValid(value)) {
+            LValue unboxedResult = value.value();
             FTL_TYPE_CHECK(
                 jsValueValue(unboxedResult), edge, SpecBoolean, isNotBoolean(unboxedResult));
             LValue result = unboxBoolean(unboxedResult);
-            m_booleanValues.add(edge.node(), result);
+            setBoolean(edge.node(), result);
             return result;
         }
         
@@ -2081,16 +2030,21 @@ private:
     {
         ASSERT_UNUSED(mode, mode == ManualOperandSpeculation || isDouble(edge.useKind()));
         
-        if (LValue result = m_doubleValues.get(edge.node()))
-            return result;
+        LoweredNodeValue value = m_doubleValues.get(edge.node());
+        if (isValid(value))
+            return value.value();
         
-        if (LValue intResult = m_int32Values.get(edge.node())) {
-            LValue result = m_out.intToDouble(intResult);
-            m_doubleValues.add(edge.node(), result);
+        value = m_int32Values.get(edge.node());
+        if (isValid(value)) {
+            LValue result = m_out.intToDouble(value.value());
+            setDouble(edge.node(), result);
             return result;
         }
         
-        if (LValue boxedResult = m_jsValueValues.get(edge.node())) {
+        value = m_jsValueValues.get(edge.node());
+        if (isValid(value)) {
+            LValue boxedResult = value.value();
+            
             LBasicBlock intCase = FTL_NEW_BLOCK(m_out, ("Double unboxing int case"));
             LBasicBlock doubleCase = FTL_NEW_BLOCK(m_out, ("Double unboxing double case"));
             LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("Double unboxing continuation"));
@@ -2115,7 +2069,7 @@ private:
             
             LValue result = m_out.phi(m_out.doubleType, intToDouble, unboxedDouble);
             
-            m_doubleValues.add(edge.node(), result);
+            setDouble(edge.node(), result);
             return result;
         }
         
@@ -2128,24 +2082,28 @@ private:
     {
         ASSERT_UNUSED(mode, mode == ManualOperandSpeculation || edge.useKind() == UntypedUse);
         
-        if (LValue result = m_jsValueValues.get(edge.node()))
-            return result;
+        LoweredNodeValue value = m_jsValueValues.get(edge.node());
+        if (isValid(value))
+            return value.value();
         
-        if (LValue unboxedResult = m_int32Values.get(edge.node())) {
-            LValue result = boxInt32(unboxedResult);
-            m_jsValueValues.add(edge.node(), result);
+        value = m_int32Values.get(edge.node());
+        if (isValid(value)) {
+            LValue result = boxInt32(value.value());
+            setJSValue(edge.node(), result);
             return result;
         }
         
-        if (LValue unboxedResult = m_booleanValues.get(edge.node())) {
-            LValue result = boxBoolean(unboxedResult);
-            m_jsValueValues.add(edge.node(), result);
+        value = m_booleanValues.get(edge.node());
+        if (isValid(value)) {
+            LValue result = boxBoolean(value.value());
+            setJSValue(edge.node(), result);
             return result;
         }
         
-        if (LValue unboxedResult = m_doubleValues.get(edge.node())) {
-            LValue result = boxDouble(unboxedResult);
-            m_jsValueValues.add(edge.node(), result);
+        value = m_doubleValues.get(edge.node());
+        if (isValid(value)) {
+            LValue result = boxDouble(value.value());
+            setJSValue(edge.node(), result);
             return result;
         }
         
@@ -2155,11 +2113,12 @@ private:
     
     LValue lowStorage(Edge edge)
     {
-        if (LValue result = m_storageValues.get(edge.node()))
-            return result;
+        LoweredNodeValue value = m_storageValues.get(edge.node());
+        if (isValid(value))
+            return value.value();
         
         LValue result = lowCell(edge);
-        m_storageValues.add(edge.node(), result);
+        setStorage(edge.node(), result);
         return result;
     }
     
@@ -2242,6 +2201,9 @@ private:
         case NumberUse:
             speculateNumber(edge);
             break;
+        case BooleanUse:
+            speculateBoolean(edge);
+            break;
         default:
             RELEASE_ASSERT_NOT_REACHED();
         }
@@ -2342,6 +2304,11 @@ private:
             doubleValue(value), edge, SpecRealNumber,
             m_out.doubleNotEqualOrUnordered(value, value));
     }
+    
+    void speculateBoolean(Edge edge)
+    {
+        lowBoolean(edge);
+    }
 
     bool masqueradesAsUndefinedWatchpointIsStillValid()
     {
@@ -2430,22 +2397,15 @@ private:
     
     bool isLive(Node* node)
     {
-        HashMap<Node*, unsigned>::iterator iter = m_timeToLive.find(node);
-        ASSERT(iter != m_timeToLive.end());
-        return !!iter->value;
+        return m_live.contains(node);
     }
     
     void use(Edge edge)
     {
-        if (!edge->hasResult()) {
-            ASSERT(edge->hasVariableAccessData());
+        ASSERT(edge->hasResult());
+        if (!edge.doesKill())
             return;
-        }
-        
-        HashMap<Node*, unsigned>::iterator iter = m_timeToLive.find(edge.node());
-        ASSERT(iter != m_timeToLive.end());
-        ASSERT(iter->value);
-        iter->value--;
+        m_live.remove(edge.node());
     }
     
     // Wrapper used only for DFG_NODE_DO_TO_CHILDREN
@@ -2462,63 +2422,34 @@ private:
     void initializeOSRExitStateForBlock()
     {
         for (unsigned i = m_valueSources.size(); i--;) {
-            Node* node = m_highBlock->variablesAtHead[i];
-            if (!node) {
-                m_valueSources[i] = ValueSource(SourceIsDead);
-                continue;
-            }
-            
-            VariableAccessData* variable = node->variableAccessData();
-            SpeculatedType prediction = variable->argumentAwarePrediction();
-            
-            if (variable->isArgumentsAlias()) {
-                m_valueSources[i] = ValueSource(ArgumentsSource);
-                continue;
-            }
-            
-            if (!node->shouldGenerate()) {
-                m_valueSources[i] = ValueSource(SourceIsDead);
-                continue;
-            }
-            
-            if (m_flushedLocalOps.contains(node)) {
-                // This value will have been flushed to the JSStack in some form or
-                // another.
-                
-                if (variable->shouldUnboxIfPossible()) {
-                    if (variable->shouldUseDoubleFormat()) {
-                        m_valueSources[i] = ValueSource(DoubleInJSStack);
-                        continue;
-                    }
-                    
-                    if (isInt32Speculation(prediction)) {
-                        m_valueSources[i] = ValueSource(Int32InJSStack);
-                        continue;
-                    }
+            FlushFormat format = m_highBlock->ssa->flushFormatAtHead[i];
+            switch (format) {
+            case DeadFlush: {
+                // Must consider available nodes instead.
+                Node* node = m_highBlock->ssa->availabilityAtHead[i];
+                if (!node) {
+                    m_valueSources[i] = ValueSource(SourceIsDead);
+                    break;
                 }
                 
-                m_valueSources[i] = ValueSource(ValueInJSStack);
-                continue;
+                m_valueSources[i] = ValueSource(node);
+                break;
             }
-            
-            if (variable->shouldUnboxIfPossible()) {
-                if (variable->shouldUseDoubleFormat()) {
-                    m_valueSources[i] = ValueSource(DoubleInLocals);
-                    continue;
-                }
                 
-                if (isInt32Speculation(prediction)) {
-                    m_valueSources[i] = ValueSource(Int32InLocals);
-                    continue;
-                }
+            case FlushedInt32:
+                m_valueSources[i] = ValueSource(Int32InJSStack);
+                break;
                 
-                if (isBooleanSpeculation(prediction)) {
-                    m_valueSources[i] = ValueSource(BooleanInLocals);
-                    continue;
-                }
+            case FlushedDouble:
+                m_valueSources[i] = ValueSource(DoubleInJSStack);
+                break;
+                
+            case FlushedCell:
+            case FlushedBoolean:
+            case FlushedJSValue:
+                m_valueSources[i] = ValueSource(ValueInJSStack);
+                break;
             }
-            
-            m_valueSources[i] = ValueSource(ValueInLocals);
         }
     }
     
@@ -2546,11 +2477,10 @@ private:
         ASSERT(m_ftlState.jitCode->osrExit.size() == m_ftlState.osrExit.size());
         unsigned index = m_ftlState.osrExit.size();
         
-        m_ftlState.jitCode->osrExit.append(
-            OSRExit(
-                kind, lowValue.format(), m_graph.methodOfGettingAValueProfileFor(highValue),
-                m_codeOrigin, m_lastSetOperand, m_valueSources.numberOfArguments(),
-                m_valueSources.numberOfLocals()));
+        m_ftlState.jitCode->osrExit.append(OSRExit(
+            kind, lowValue.format(), m_graph.methodOfGettingAValueProfileFor(highValue),
+            m_codeOrigin, m_lastSetOperand, m_valueSources.numberOfArguments(),
+            m_valueSources.numberOfLocals()));
         m_ftlState.osrExit.append(OSRExitCompilationInfo());
         
         OSRExit& exit = m_ftlState.jitCode->osrExit.last();
@@ -2602,27 +2532,6 @@ private:
             case DoubleInJSStack:
                 exit.m_values[i] = ExitValue::inJSStackAsDouble();
                 break;
-            case ValueInLocals:
-                addExitArgument(
-                    exit, arguments, i, ValueFormatJSValue, m_out.get(m_locals64[i]));
-                break;
-            case Int32InLocals:
-                addExitArgument(
-                    exit, arguments, i, ValueFormatInt32, m_out.get(m_locals32[i]));
-                break;
-            case BooleanInLocals:
-                addExitArgument(
-                    exit, arguments, i, ValueFormatBoolean, m_out.get(m_localsBoolean[i]));
-                break;
-            case DoubleInLocals:
-                addExitArgument(
-                    exit, arguments, i, ValueFormatDouble, m_out.get(m_localsDouble[i]));
-                break;
-            case ArgumentsSource:
-                // FIXME: implement PhantomArguments.
-                // https://bugs.webkit.org/show_bug.cgi?id=113986
-                RELEASE_ASSERT_NOT_REACHED();
-                break;
             case SourceIsDead:
                 exit.m_values[i] = ExitValue::dead();
                 break;
@@ -2682,12 +2591,10 @@ private:
                 Node* uint32ToNumber = 0;
                 Node* doubleAsInt32 = 0;
                 
-                HashMap<Node*, unsigned>::iterator iter = m_timeToLive.begin();
-                HashMap<Node*, unsigned>::iterator end = m_timeToLive.end();
+                HashSet<Node*>::iterator iter = m_live.begin();
+                HashSet<Node*>::iterator end = m_live.end();
                 for (; iter != end; ++iter) {
-                    if (!iter->value)
-                        continue;
-                    Node* candidate = iter->key;
+                    Node* candidate = *iter;
                     if (!candidate->child1())
                         continue;
                     if (candidate->child1() != node)
@@ -2732,24 +2639,28 @@ private:
         }
         
         ASSERT(isLive(node));
-        
-        if (LValue result = m_int32Values.get(node)) {
-            addExitArgument(exit, arguments, index, ValueFormatInt32, result);
+
+        LoweredNodeValue value = m_int32Values.get(node);
+        if (isValid(value)) {
+            addExitArgument(exit, arguments, index, ValueFormatInt32, value.value());
             return;
         }
         
-        if (LValue result = m_booleanValues.get(node)) {
-            addExitArgument(exit, arguments, index, ValueFormatBoolean, result);
+        value = m_booleanValues.get(node);
+        if (isValid(value)) {
+            addExitArgument(exit, arguments, index, ValueFormatBoolean, value.value());
             return;
         }
         
-        if (LValue result = m_jsValueValues.get(node)) {
-            addExitArgument(exit, arguments, index, ValueFormatJSValue, result);
+        value = m_jsValueValues.get(node);
+        if (isValid(value)) {
+            addExitArgument(exit, arguments, index, ValueFormatJSValue, value.value());
             return;
         }
         
-        if (LValue result = m_doubleValues.get(node)) {
-            addExitArgument(exit, arguments, index, ValueFormatDouble, result);
+        value = m_doubleValues.get(node);
+        if (isValid(value)) {
+            addExitArgument(exit, arguments, index, ValueFormatDouble, value.value());
             return;
         }
 
@@ -2820,7 +2731,7 @@ private:
             m_ftlState.finalizer->initializeExitThunksLinkBuffer(linkBuffer.release());
         }
 
-        m_out.jump(m_argumentChecks);
+        m_out.jump(lowBlock(m_graph.block(0)));
     }
     
     void observeMovHint(Node* node)
@@ -2834,6 +2745,57 @@ private:
         m_valueSources.operand(operand) = ValueSource(node->child1().node());
     }
     
+    void setInt32(Node* node, LValue value)
+    {
+        m_int32Values.set(node, LoweredNodeValue(value, m_highBlock));
+    }
+    void setJSValue(Node* node, LValue value)
+    {
+        m_jsValueValues.set(node, LoweredNodeValue(value, m_highBlock));
+    }
+    void setBoolean(Node* node, LValue value)
+    {
+        m_booleanValues.set(node, LoweredNodeValue(value, m_highBlock));
+    }
+    void setStorage(Node* node, LValue value)
+    {
+        m_storageValues.set(node, LoweredNodeValue(value, m_highBlock));
+    }
+    void setDouble(Node* node, LValue value)
+    {
+        m_doubleValues.set(node, LoweredNodeValue(value, m_highBlock));
+    }
+
+    void setInt32(LValue value)
+    {
+        setInt32(m_node, value);
+    }
+    void setJSValue(LValue value)
+    {
+        setJSValue(m_node, value);
+    }
+    void setBoolean(LValue value)
+    {
+        setBoolean(m_node, value);
+    }
+    void setStorage(LValue value)
+    {
+        setStorage(m_node, value);
+    }
+    void setDouble(LValue value)
+    {
+        setDouble(m_node, value);
+    }
+    
+    bool isValid(const LoweredNodeValue& value)
+    {
+        if (!value)
+            return false;
+        if (!m_graph.m_dominators.dominates(value.block(), m_highBlock))
+            return false;
+        return true;
+    }
+    
     void addWeakReference(JSCell* target)
     {
         m_ftlState.jitCode->common.weakReferences.append(
@@ -2881,27 +2843,20 @@ private:
     
     LBasicBlock m_prologue;
     LBasicBlock m_initialization;
-    LBasicBlock m_argumentChecks;
     HashMap<BasicBlock*, LBasicBlock> m_blocks;
     
     LValue m_callFrame;
     LValue m_tagTypeNumber;
     LValue m_tagMask;
     
-    HashSet<Node*> m_flushedLocalOps;
-    Vector<Node*> m_flushedLocalOpWorklist;
-    
-    HashMap<Node*, LValue> m_int32Values;
-    HashMap<Node*, LValue> m_jsValueValues;
-    HashMap<Node*, LValue> m_booleanValues;
-    HashMap<Node*, LValue> m_storageValues;
-    HashMap<Node*, LValue> m_doubleValues;
-    HashMap<Node*, unsigned> m_timeToLive;
+    HashMap<Node*, LoweredNodeValue> m_int32Values;
+    HashMap<Node*, LoweredNodeValue> m_jsValueValues;
+    HashMap<Node*, LoweredNodeValue> m_booleanValues;
+    HashMap<Node*, LoweredNodeValue> m_storageValues;
+    HashMap<Node*, LoweredNodeValue> m_doubleValues;
+    HashSet<Node*> m_live;
     
-    Operands<LValue> m_localsBoolean;
-    Operands<LValue> m_locals32;
-    Operands<LValue> m_locals64;
-    Operands<LValue> m_localsDouble;
+    HashMap<Node*, LValue> m_phis;
     
     Operands<ValueSource> m_valueSources;
     int m_lastSetOperand;
diff --git a/Source/JavaScriptCore/ftl/FTLLoweredNodeValue.h b/Source/JavaScriptCore/ftl/FTLLoweredNodeValue.h
new file mode 100644 (file)
index 0000000..93e6c4d
--- /dev/null
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef FTLLoweredNodeValue_h
+#define FTLLoweredNodeValue_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(FTL_JIT)
+
+#include "DFGBasicBlock.h"
+#include "FTLAbbreviatedTypes.h"
+
+namespace JSC { namespace FTL {
+
+// Represents the act of having lowered a DFG::Node to an LValue, and records the
+// DFG::BasicBlock that did the lowering. The LValue is what we use most often, but
+// we need to verify that we're in a block that is dominated by the one that did
+// the lowering. We're guaranteed that for each DFG::Node, there will be one
+// LoweredNodeValue that always dominates all uses of the DFG::Node; but there may
+// be others that don't dominate and we're effectively doing opportunistic GVN on
+// the lowering code.
+
+class LoweredNodeValue {
+public:
+    LoweredNodeValue()
+        : m_value(0)
+        , m_block(0)
+    {
+    }
+    
+    LoweredNodeValue(LValue value, DFG::BasicBlock* block)
+        : m_value(value)
+        , m_block(block)
+    {
+        ASSERT(m_value);
+        ASSERT(m_block);
+    }
+    
+    bool isSet() const { return !!m_value; }
+    bool operator!() const { return !isSet(); }
+    
+    LValue value() const { return m_value; }
+    DFG::BasicBlock* block() const { return m_block; }
+    
+private:
+    LValue m_value;
+    DFG::BasicBlock* m_block;
+};
+
+} } // namespace JSC::FTL
+
+#endif // ENABLE(FTL_JIT)
+
+#endif // FTLLoweredNodeValue_h
+
index 537fca9..fec0a1b 100644 (file)
@@ -36,6 +36,12 @@ namespace JSC { namespace FTL {
 
 class ValueFromBlock {
 public:
+    ValueFromBlock()
+        : m_value(0)
+        , m_block(0)
+    {
+    }
+    
     ValueFromBlock(LValue value, LBasicBlock block)
         : m_value(value)
         , m_block(block)
index 4b7eeb0..cad0261 100644 (file)
@@ -45,21 +45,6 @@ void ValueSource::dump(PrintStream& out) const
     case DoubleInJSStack:
         out.print("DoubleInJSStack");
         return;
-    case ValueInLocals:
-        out.print("ValueInLocals");
-        return;
-    case Int32InLocals:
-        out.print("Int32InLocals");
-        return;
-    case BooleanInLocals:
-        out.print("BooleanInLocals");
-        return;
-    case DoubleInLocals:
-        out.print("DoubleInLocals");
-        return;
-    case ArgumentsSource:
-        out.print("ArgumentsSource");
-        return;
     case SourceIsDead:
         out.print("SourceIsDead");
         return;
index 965d3df..a0bd705 100644 (file)
@@ -41,11 +41,6 @@ enum ValueSourceKind {
     ValueInJSStack,
     Int32InJSStack,
     DoubleInJSStack,
-    ValueInLocals,
-    Int32InLocals,
-    BooleanInLocals,
-    DoubleInLocals,
-    ArgumentsSource,
     SourceIsDead,
     HaveNode
 };
index b3ff3e1..931b99a 100644 (file)
@@ -122,6 +122,7 @@ typedef OptionRange optionRange;
     v(bool, useLLVMSmallCodeModel, false) \
     v(bool, ftlTrapsOnOSRExit, false) \
     v(bool, ftlOSRExitOmitsMarshalling, false) \
+    v(bool, dumpLLVMIR, false) \
     v(unsigned, llvmBackendOptimizationLevel, 2) \
     v(unsigned, llvmOptimizationLevel, 2) \
     v(unsigned, llvmSizeLevel, 0) \
index a6f328b..9901959 100644 (file)
@@ -1,3 +1,61 @@
+2013-07-12  Filip Pizlo  <fpizlo@apple.com>
+
+        fourthTier: DFG should have an SSA form for use by FTL
+        https://bugs.webkit.org/show_bug.cgi?id=118338
+
+        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):
+
 2013-07-02  Filip Pizlo  <fpizlo@apple.com>
 
         Unreviewed, fix 32-bit build.
index ece5278..71494ca 100644 (file)
@@ -60,6 +60,8 @@
                974CFC8E16A4F327006D5404 /* WeakPtr.h in Headers */ = {isa = PBXBuildFile; fileRef = 974CFC8D16A4F327006D5404 /* WeakPtr.h */; };
                9BC70F05176C379D00101DEC /* AtomicStringTable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */; };
                9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */; };
+               A70DA0841799F04D00529A9B /* Insertion.h in Headers */ = {isa = PBXBuildFile; fileRef = A70DA0821799F04D00529A9B /* Insertion.h */; };
+               A70DA0851799F04D00529A9B /* ListDump.h in Headers */ = {isa = PBXBuildFile; fileRef = A70DA0831799F04D00529A9B /* ListDump.h */; };
                A876DBD8151816E500DADB95 /* Platform.h in Headers */ = {isa = PBXBuildFile; fileRef = A876DBD7151816E500DADB95 /* Platform.h */; };
                A8A4737F151A825B004123FF /* Alignment.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47254151A825A004123FF /* Alignment.h */; };
                A8A47381151A825B004123FF /* ArrayBuffer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A47256151A825A004123FF /* ArrayBuffer.cpp */; };
                974CFC8D16A4F327006D5404 /* WeakPtr.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakPtr.h; sourceTree = "<group>"; };
                9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringTable.cpp; sourceTree = "<group>"; };
                9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AtomicStringTable.h; sourceTree = "<group>"; };
+               A70DA0821799F04D00529A9B /* Insertion.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Insertion.h; sourceTree = "<group>"; };
+               A70DA0831799F04D00529A9B /* ListDump.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ListDump.h; sourceTree = "<group>"; };
                A736B3581799E11A00C6F05E /* LLVMHeaders.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = LLVMHeaders.h; sourceTree = "<group>"; };
                A876DBD7151816E500DADB95 /* Platform.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Platform.h; sourceTree = "<group>"; };
                A8A47254151A825A004123FF /* Alignment.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Alignment.h; sourceTree = "<group>"; };
                                A8A472BA151A825A004123FF /* HashTraits.h */,
                                A8A472BB151A825A004123FF /* HexNumber.h */,
                                A8A472BC151A825A004123FF /* InlineASM.h */,
+                               A70DA0821799F04D00529A9B /* Insertion.h */,
                                A8A472BE151A825A004123FF /* Int16Array.h */,
                                A8A472BF151A825A004123FF /* Int32Array.h */,
                                A8A472BD151A825A004123FF /* Int8Array.h */,
                                A8A472C0151A825A004123FF /* IntegralTypedArrayBase.h */,
+                               A70DA0831799F04D00529A9B /* ListDump.h */,
                                A8A472C1151A825A004123FF /* ListHashSet.h */,
                                A736B3581799E11A00C6F05E /* LLVMHeaders.h */,
                                A8A472C3151A825A004123FF /* Locker.h */,
                                A8A473DA151A825B004123FF /* HashTraits.h in Headers */,
                                A8A473DB151A825B004123FF /* HexNumber.h in Headers */,
                                A8A473DC151A825B004123FF /* InlineASM.h in Headers */,
+                               A70DA0841799F04D00529A9B /* Insertion.h in Headers */,
                                A8A473DE151A825B004123FF /* Int16Array.h in Headers */,
                                A8A473DF151A825B004123FF /* Int32Array.h in Headers */,
                                A8A473DD151A825B004123FF /* Int8Array.h in Headers */,
                                26147B0A15DDCCDC00DDB907 /* IntegerToStringConversion.h in Headers */,
                                A8A473E0151A825B004123FF /* IntegralTypedArrayBase.h in Headers */,
+                               A70DA0851799F04D00529A9B /* ListDump.h in Headers */,
                                A8A473E1151A825B004123FF /* ListHashSet.h in Headers */,
                                A8A473E3151A825B004123FF /* Locker.h in Headers */,
                                A8A473E6151A825B004123FF /* MainThread.h in Headers */,
index 0bd8efe..33cd9f5 100644 (file)
@@ -118,6 +118,18 @@ void dataLog(const T1& value1, const T2& value2, const T3& value3, const T4& val
     dataFile().print(value1, value2, value3, value4, value5, value6, value7, value8, value9, value10, value11, value12, value13);
 }
 
+template<typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10, typename T11, typename T12, typename T13, typename T14>
+void dataLog(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5, const T6& value6, const T7& value7, const T8& value8, const T9& value9, const T10& value10, const T11& value11, const T12& value12, const T13& value13, const T14& value14)
+{
+    dataFile().print(value1, value2, value3, value4, value5, value6, value7, value8, value9, value10, value11, value12, value13, value14);
+}
+
+template<typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10, typename T11, typename T12, typename T13, typename T14, typename T15>
+void dataLog(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5, const T6& value6, const T7& value7, const T8& value8, const T9& value9, const T10& value10, const T11& value11, const T12& value12, const T13& value13, const T14& value14, const T15& value15)
+{
+    dataFile().print(value1, value2, value3, value4, value5, value6, value7, value8, value9, value10, value11, value12, value13, value14, value15);
+}
+
 } // namespace WTF
 
 using WTF::dataLog;
index c89d40f..208552d 100644 (file)
@@ -82,12 +82,19 @@ namespace WTF {
         //   static bool equal(const ValueType&, const T&);
         //   static translate(ValueType&, const T&, unsigned hashCode);
         template<typename HashTranslator, typename T> AddResult add(const T&);
+        
+        // Attempts to add a list of things to the set. Returns true if any of
+        // them are new to the set. Returns false if the set is unchanged.
+        template<typename IteratorType>
+        bool add(IteratorType begin, IteratorType end);
 
         void remove(const ValueType&);
         void remove(iterator);
         void clear();
 
         static bool isValidValue(const ValueType&);
+        
+        bool operator==(const HashSet&) const;
 
     private:
         friend void deleteAllValues<>(const HashSet&);
@@ -187,6 +194,16 @@ namespace WTF {
     }
 
     template<typename T, typename U, typename V>
+    template<typename IteratorType>
+    inline bool HashSet<T, U, V>::add(IteratorType begin, IteratorType end)
+    {
+        bool changed = false;
+        for (IteratorType iter = begin; iter != end; ++iter)
+            changed |= add(*iter).isNewEntry;
+        return changed;
+    }
+
+    template<typename T, typename U, typename V>
     inline void HashSet<T, U, V>::remove(iterator it)
     {
         if (it.m_impl == m_impl.end())
@@ -252,6 +269,18 @@ namespace WTF {
             vector[i] = *it;
     }  
 
+    template<typename T, typename U, typename V>
+    inline bool HashSet<T, U, V>::operator==(const HashSet& other) const
+    {
+        if (size() != other.size())
+            return false;
+        for (const_iterator iter = begin(); iter != end(); ++iter) {
+            if (!other.contains(*iter))
+                return false;
+        }
+        return true;
+    }
+
 } // namespace WTF
 
 using WTF::HashSet;
index 46ba790..579f534 100644 (file)
@@ -1173,6 +1173,8 @@ namespace WTF {
     {
         // Copy the hash table the dumb way, by adding each element to the new table.
         // It might be more efficient to copy the table slots, but it's not clear that efficiency is needed.
+        // FIXME: It's likely that this can be improved, for static analyses that use
+        // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
         const_iterator end = other.end();
         for (const_iterator it = other.begin(); it != end; ++it)
             add(*it);
@@ -1212,6 +1214,8 @@ namespace WTF {
     template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
     HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
     {
+        // FIXME: It's likely that this can be improved, for static analyses that use
+        // HashSets. https://bugs.webkit.org/show_bug.cgi?id=118455
         HashTable tmp(other);
         swap(tmp);
         return *this;
diff --git a/Source/WTF/wtf/Insertion.h b/Source/WTF/wtf/Insertion.h
new file mode 100644 (file)
index 0000000..9c4bccf
--- /dev/null
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef Insertion_h
+#define Insertion_h
+
+namespace WTF {
+
+template<typename T>
+class Insertion {
+public:
+    Insertion() { }
+    
+    Insertion(size_t index, T element)
+        : m_index(index)
+        , m_element(element)
+    {
+    }
+    
+    size_t index() const { return m_index; }
+    T element() const { return m_element; }
+    
+    bool operator<(const Insertion& other) const
+    {
+        return m_index < other.m_index;
+    }
+    
+private:
+    size_t m_index;
+    T m_element;
+};
+
+template<typename TargetVectorType, typename InsertionVectorType>
+void executeInsertions(TargetVectorType& target, InsertionVectorType& insertions)
+{
+    if (!insertions.size())
+        return;
+    target.grow(target.size() + insertions.size());
+    size_t lastIndex = target.size();
+    for (size_t indexInInsertions = insertions.size(); indexInInsertions--;) {
+        size_t firstIndex = insertions[indexInInsertions].index() + indexInInsertions;
+        size_t indexOffset = indexInInsertions + 1;
+        for (size_t i = lastIndex; --i > firstIndex;)
+            target[i] = target[i - indexOffset];
+        target[firstIndex] = insertions[indexInInsertions].element();
+        lastIndex = firstIndex;
+    }
+    insertions.resize(0);
+}
+
+} // namespace WTF
+
+using WTF::Insertion;
+using WTF::executeInsertions;
+
+#endif // Insertion_h
diff --git a/Source/WTF/wtf/ListDump.h b/Source/WTF/wtf/ListDump.h
new file mode 100644 (file)
index 0000000..7289ad0
--- /dev/null
@@ -0,0 +1,136 @@
+/*
+ * Copyright (C) 2013 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#ifndef ListDump_h
+#define ListDump_h
+
+#include "CommaPrinter.h"
+#include "PrintStream.h"
+#include "StringPrintStream.h"
+
+namespace WTF {
+
+template<typename T>
+class ListDump {
+public:
+    ListDump(const T& list, const char* comma)
+        : m_list(list)
+        , m_comma(comma)
+    {
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        for (typename T::const_iterator iter = m_list.begin(); iter != m_list.end(); ++iter)
+            out.print(m_comma, *iter);
+    }
+
+private:
+    const T& m_list;
+    CommaPrinter m_comma;
+};
+
+template<typename T>
+class MapDump {
+public:
+    MapDump(const T& map, const char* arrow, const char* comma)
+        : m_map(map)
+        , m_arrow(arrow)
+        , m_comma(comma)
+    {
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        for (typename T::const_iterator iter = m_map.begin(); iter != m_map.end(); ++iter)
+            out.print(m_comma, iter->key, m_arrow, iter->value);
+    }
+    
+private:
+    const T& m_map;
+    const char* m_arrow;
+    CommaPrinter m_comma;
+};
+
+template<typename T>
+ListDump<T> listDump(const T& list, const char* comma = ", ")
+{
+    return ListDump<T>(list, comma);
+}
+
+template<typename T, typename Comparator>
+CString sortedListDump(const T& list, const Comparator& comparator, const char* comma = ", ")
+{
+    Vector<typename T::ValueType> myList;
+    myList.appendRange(list.begin(), list.end());
+    std::sort(myList.begin(), myList.end(), comparator);
+    StringPrintStream out;
+    CommaPrinter commaPrinter(comma);
+    for (unsigned i = 0; i < myList.size(); ++i)
+        out.print(commaPrinter, myList[i]);
+    return out.toCString();
+}
+
+template<typename T>
+inline bool lessThan(const T& a, const T& b)
+{
+    return a < b;
+}
+
+template<typename T>
+CString sortedListDump(const T& list, const char* comma = ", ")
+{
+    return sortedListDump(list, lessThan<T::ValueType>, comma);
+}
+
+template<typename T>
+MapDump<T> mapDump(const T& map, const char* arrow = "=>", const char* comma = ", ")
+{
+    return MapDump<T>(map, arrow, comma);
+}
+
+template<typename T, typename Comparator>
+CString sortedMapDump(const T& map, const Comparator& comparator, const char* arrow = "=>", const char* comma = ", ")
+{
+    Vector<typename T::KeyType> keys;
+    for (typename T::const_iterator iter = map.begin(); iter != map.end(); ++iter)
+        keys.append(iter->key);
+    std::sort(keys.begin(), keys.end(), comparator);
+    StringPrintStream out;
+    CommaPrinter commaPrinter(comma);
+    for (unsigned i = 0; i < keys.size(); ++i)
+        out.print(commaPrinter, keys[i], arrow, map.get(keys[i]));
+    return out.toCString();
+}
+
+} // namespace WTF
+
+using WTF::listDump;
+using WTF::sortedListDump;
+using WTF::mapDump;
+using WTF::sortedMapDump;
+
+#endif // ListDump_h
+
index a14fb83..7b539ce 100644 (file)
@@ -207,6 +207,45 @@ public:
         print(value12);
         print(value13);
     }
+    
+    template<typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10, typename T11, typename T12, typename T13, typename T14>
+    void print(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5, const T6& value6, const T7& value7, const T8& value8, const T9& value9, const T10& value10, const T11& value11, const T12& value12, const T13& value13, const T14& value14)
+    {
+        print(value1);
+        print(value2);
+        print(value3);
+        print(value4);
+        print(value5);
+        print(value6);
+        print(value7);
+        print(value8);
+        print(value9);
+        print(value10);
+        print(value11);
+        print(value12);
+        print(value13);
+        print(value14);
+    }
+    
+    template<typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9, typename T10, typename T11, typename T12, typename T13, typename T14, typename T15>
+    void print(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5, const T6& value6, const T7& value7, const T8& value8, const T9& value9, const T10& value10, const T11& value11, const T12& value12, const T13& value13, const T14& value14, const T15& value15)
+    {
+        print(value1);
+        print(value2);
+        print(value3);
+        print(value4);
+        print(value5);
+        print(value6);
+        print(value7);
+        print(value8);
+        print(value9);
+        print(value10);
+        print(value11);
+        print(value12);
+        print(value13);
+        print(value14);
+        print(value15);
+    }
 };
 
 WTF_EXPORT_PRIVATE void printInternal(PrintStream&, const char*);
index b5373e3..ac47d01 100644 (file)
@@ -83,6 +83,22 @@ CString toCString(const T1& value1, const T2& value2, const T3& value3, const T4
     return stream.toCString();
 }
 
+template<typename T1, typename T2, typename T3, typename T4, typename T5>
+CString toCString(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5)
+{
+    StringPrintStream stream;
+    stream.print(value1, value2, value3, value4, value5);
+    return stream.toCString();
+}
+
+template<typename T1, typename T2, typename T3, typename T4, typename T5, typename T6>
+CString toCString(const T1& value1, const T2& value2, const T3& value3, const T4& value4, const T5& value5, const T6& value6)
+{
+    StringPrintStream stream;
+    stream.print(value1, value2, value3, value4, value5, value6);
+    return stream.toCString();
+}
+
 template<typename T>
 String toString(const T& value)
 {