Support compiling catch in the DFG
authorsbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 25 Aug 2017 18:26:15 +0000 (18:26 +0000)
committersbarati@apple.com <sbarati@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 25 Aug 2017 18:26:15 +0000 (18:26 +0000)
https://bugs.webkit.org/show_bug.cgi?id=174590
<rdar://problem/34047845>

Reviewed by Filip Pizlo.

JSTests:

* microbenchmarks/delta-blue-try-catch.js: Added.
(exception):
(value):
(OrderedCollection):
(OrderedCollection.prototype.add):
(OrderedCollection.prototype.at):
(OrderedCollection.prototype.size):
(OrderedCollection.prototype.removeFirst):
(OrderedCollection.prototype.remove):
(Strength):
(Strength.stronger):
(Strength.weaker):
(Strength.weakestOf):
(Strength.strongest):
(Strength.prototype.nextWeaker):
(Constraint):
(Constraint.prototype.addConstraint):
(Constraint.prototype.satisfy):
(Constraint.prototype.destroyConstraint):
(Constraint.prototype.isInput):
(UnaryConstraint):
(UnaryConstraint.prototype.addToGraph):
(UnaryConstraint.prototype.chooseMethod):
(UnaryConstraint.prototype.isSatisfied):
(UnaryConstraint.prototype.markInputs):
(UnaryConstraint.prototype.output):
(UnaryConstraint.prototype.recalculate):
(UnaryConstraint.prototype.markUnsatisfied):
(UnaryConstraint.prototype.inputsKnown):
(UnaryConstraint.prototype.removeFromGraph):
(StayConstraint):
(StayConstraint.prototype.execute):
(EditConstraint.prototype.isInput):
(EditConstraint.prototype.execute):
(BinaryConstraint):
(BinaryConstraint.prototype.chooseMethod):
(BinaryConstraint.prototype.addToGraph):
(BinaryConstraint.prototype.isSatisfied):
(BinaryConstraint.prototype.markInputs):
(BinaryConstraint.prototype.input):
(BinaryConstraint.prototype.output):
(BinaryConstraint.prototype.recalculate):
(BinaryConstraint.prototype.markUnsatisfied):
(BinaryConstraint.prototype.inputsKnown):
(BinaryConstraint.prototype.removeFromGraph):
(ScaleConstraint):
(ScaleConstraint.prototype.addToGraph):
(ScaleConstraint.prototype.removeFromGraph):
(ScaleConstraint.prototype.markInputs):
(ScaleConstraint.prototype.execute):
(ScaleConstraint.prototype.recalculate):
(EqualityConstraint):
(EqualityConstraint.prototype.execute):
(Variable):
(Variable.prototype.addConstraint):
(Variable.prototype.removeConstraint):
(Planner):
(Planner.prototype.incrementalAdd):
(Planner.prototype.incrementalRemove):
(Planner.prototype.newMark):
(Planner.prototype.makePlan):
(Planner.prototype.extractPlanFromConstraints):
(Planner.prototype.addPropagate):
(Planner.prototype.removePropagateFrom):
(Planner.prototype.addConstraintsConsumingTo):
(Plan):
(Plan.prototype.addConstraint):
(Plan.prototype.size):
(Plan.prototype.constraintAt):
(Plan.prototype.execute):
(chainTest):
(projectionTest):
(change):
(deltaBlue):
* microbenchmarks/fake-iterators-that-throw-when-finished.js: Added.
(assert):
(Numbers):
(Numbers.prototype.next):
(return.Transpose):
(return.Transpose.prototype.next):
(transpose):
(verifyEven):
(verifyString):
(foo):
(runIterators):
* microbenchmarks/try-catch-word-count.js: Added.
(let.assert):
(EOF):
(let.texts):
(let.o.apply):
(foo):
(bar):
(f):
(run):
(test1):
(test2):
(test3):
(fn):
(A):
(B):
(A.prototype.getValue):
(B.prototype.getParentValue):
(strlen):
(sum.0):
(test):
(result.test.o):
(set add.set add):
(set forEach):
(stringHash):
(set if):
(testFunction):
(set delete.set has.set add):
* stress/catch-set-argument-speculation-failure.js: Added.
(o):
(e):
(e2):
(escape):
(baz):
(noInline.run):
(noInline):
* stress/osr-enter-to-catch-with-set-local-type-check-failure.js: Added.
(foo):
(e):
(baz):
(bar):

Source/JavaScriptCore:

This patch implements OSR entry into op_catch in the DFG. We will support OSR entry
into the FTL in a followup: https://bugs.webkit.org/show_bug.cgi?id=175396

To implement catch in the DFG, this patch introduces the concept of multiple
entrypoints into CPS/LoadStore DFG IR. A lot of this patch is stringing this concept
through the DFG. Many phases used to assume that Graph::block(0) is the only root, and this
patch contains many straight forward changes generalizing the code to handle more than
one entrypoint.

A main building block of this is moving to two CFG types: SSACFG and CPSCFG. SSACFG
is the same CFG we used to have. CPSCFG is a new type that introduces a fake root
that has an outgoing edge to all the entrypoints. This allows our existing graph algorithms
to Just Work over CPSCFG. For example, there is now the concept of SSADominators vs CPSDominators,
and SSANaturalLoops vs CPSNaturalLoops.

The way we compile the catch entrypoint is by bootstrapping the state
of the program by loading all live bytecode locals from a buffer. The OSR
entry code will store all live values into that buffer before jumping to
the entrypoint. The OSR entry code is also responsible for performing type
proofs of the arguments before doing an OSR entry. If there is a type
mismatch, it's not legal to OSR enter into the DFG compilation. Currently,
each catch entrypoint knows the argument type proofs it must perform to enter
into the DFG. Currently, all entrypoints' arguments flush format are unified
via ArgumentPosition, but this is just an implementation detail. The code is
written more generally to assume that each entrypoint may perform its own distinct
proof.

op_catch now performs value profiling for all live bytecode locals in the
LLInt and baseline JIT. This information is then fed into the DFG via the
ExtractCatchLocal node in the prediction propagation phase.

This patch also changes how we generate op_catch in bytecode. All op_catches
are now split out at the end of the program in bytecode. This ensures that
no op_catch is inside a try block. This is needed to ensure correctness in
the DFGLiveCatchVariablePreservationPhase. That phase only inserts flushes
before SetLocals inside a try block. If an op_catch were in a try block, this
would cause the phase to insert a Flush before one of the state bootstrapping
SetLocals, which would generate invalid IR. Moving op_catch to be generated on
its own at the end of a bytecode stream seemed like the most elegant solution since
it better represents that we treat op_catch as an entrypoint. This is true
both in the DFG and in the baseline and LLInt: we don't reach an op_catch
via normal control flow. Because op_catch cannot throw, this will not break
any previous semantics of op_catch. Logically, it'd be valid to split try
blocks around any non-throwing bytecode operation.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/BytecodeDumper.cpp:
(JSC::BytecodeDumper<Block>::dumpBytecode):
* bytecode/BytecodeList.json:
* bytecode/BytecodeUseDef.h:
(JSC::computeUsesForBytecodeOffset):
* bytecode/CodeBlock.cpp:
(JSC::CodeBlock::finishCreation):
(JSC::CodeBlock::ensureCatchLivenessIsComputedForBytecodeOffset):
(JSC::CodeBlock::updateAllPredictionsAndCountLiveness):
(JSC::CodeBlock::validate):
* bytecode/CodeBlock.h:
* bytecode/ValueProfile.h:
(JSC::ValueProfile::ValueProfile):
(JSC::ValueProfileAndOperandBuffer::ValueProfileAndOperandBuffer):
(JSC::ValueProfileAndOperandBuffer::~ValueProfileAndOperandBuffer):
(JSC::ValueProfileAndOperandBuffer::forEach):
* bytecompiler/BytecodeGenerator.cpp:
(JSC::BytecodeGenerator::generate):
(JSC::BytecodeGenerator::BytecodeGenerator):
(JSC::BytecodeGenerator::emitCatch):
(JSC::BytecodeGenerator::emitEnumeration):
* bytecompiler/BytecodeGenerator.h:
* bytecompiler/NodesCodegen.cpp:
(JSC::TryNode::emitBytecode):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGBackwardsCFG.h:
(JSC::DFG::BackwardsCFG::BackwardsCFG):
* dfg/DFGBasicBlock.cpp:
(JSC::DFG::BasicBlock::BasicBlock):
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::findTerminal const):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::setDirect):
(JSC::DFG::ByteCodeParser::flush):
(JSC::DFG::ByteCodeParser::DelayedSetLocal::DelayedSetLocal):
(JSC::DFG::ByteCodeParser::DelayedSetLocal::execute):
(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::parseCodeBlock):
(JSC::DFG::ByteCodeParser::parse):
* dfg/DFGCFG.h:
(JSC::DFG::CFG::root):
(JSC::DFG::CFG::roots):
(JSC::DFG::CPSCFG::CPSCFG):
(JSC::DFG::selectCFG):
* dfg/DFGCPSRethreadingPhase.cpp:
(JSC::DFG::CPSRethreadingPhase::specialCaseArguments):
* dfg/DFGCSEPhase.cpp:
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGControlEquivalenceAnalysis.h:
(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
* dfg/DFGDCEPhase.cpp:
(JSC::DFG::DCEPhase::run):
* dfg/DFGDisassembler.cpp:
(JSC::DFG::Disassembler::createDumpList):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::Dominators):
(JSC::DFG::ensureDominatorsForCFG):
* dfg/DFGEdgeDominates.h:
(JSC::DFG::EdgeDominates::EdgeDominates):
(JSC::DFG::EdgeDominates::operator()):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::fixupChecksInBlock):
* dfg/DFGFlushFormat.h:
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::Graph):
(JSC::DFG::unboxLoopNode):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::determineReachability):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::blocksInPreOrder):
(JSC::DFG::Graph::blocksInPostOrder):
(JSC::DFG::Graph::ensureCPSDominators):
(JSC::DFG::Graph::ensureSSADominators):
(JSC::DFG::Graph::ensureCPSNaturalLoops):
(JSC::DFG::Graph::ensureSSANaturalLoops):
(JSC::DFG::Graph::ensureBackwardsCFG):
(JSC::DFG::Graph::ensureBackwardsDominators):
(JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
(JSC::DFG::Graph::methodOfGettingAValueProfileFor):
(JSC::DFG::Graph::clearCPSCFGData):
(JSC::DFG::Graph::ensureDominators): Deleted.
(JSC::DFG::Graph::ensurePrePostNumbering): Deleted.
(JSC::DFG::Graph::ensureNaturalLoops): Deleted.
* dfg/DFGGraph.h:
(JSC::DFG::Graph::willCatchExceptionInMachineFrame):
(JSC::DFG::Graph::isEntrypoint const):
* dfg/DFGInPlaceAbstractState.cpp:
(JSC::DFG::InPlaceAbstractState::initialize):
(JSC::DFG::InPlaceAbstractState::mergeToSuccessors):
* dfg/DFGJITCode.cpp:
(JSC::DFG::JITCode::shrinkToFit):
* dfg/DFGJITCode.h:
(JSC::DFG::JITCode::catchOSREntryDataForBytecodeIndex):
(JSC::DFG::JITCode::finalizeCatchOSREntrypoints):
(JSC::DFG::JITCode::appendCatchEntrypoint):
* dfg/DFGJITCompiler.cpp:
(JSC::DFG::JITCompiler::compile):
(JSC::DFG::JITCompiler::compileFunction):
(JSC::DFG::JITCompiler::noticeCatchEntrypoint):
(JSC::DFG::JITCompiler::noticeOSREntry):
(JSC::DFG::JITCompiler::makeCatchOSREntryBuffer):
* dfg/DFGJITCompiler.h:
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGLiveCatchVariablePreservationPhase.cpp:
(JSC::DFG::LiveCatchVariablePreservationPhase::run):
(JSC::DFG::LiveCatchVariablePreservationPhase::isValidFlushLocation):
(JSC::DFG::LiveCatchVariablePreservationPhase::handleBlockForTryCatch):
(JSC::DFG::LiveCatchVariablePreservationPhase::newVariableAccessData):
(JSC::DFG::LiveCatchVariablePreservationPhase::willCatchException): Deleted.
(JSC::DFG::LiveCatchVariablePreservationPhase::handleBlock): Deleted.
* dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
* dfg/DFGMaximalFlushInsertionPhase.cpp:
(JSC::DFG::MaximalFlushInsertionPhase::run):
(JSC::DFG::MaximalFlushInsertionPhase::treatRegularBlock):
(JSC::DFG::MaximalFlushInsertionPhase::treatRootBlock):
* dfg/DFGMayExit.cpp:
* dfg/DFGNaturalLoops.h:
(JSC::DFG::NaturalLoops::NaturalLoops):
* dfg/DFGNode.h:
(JSC::DFG::Node::isSwitch const):
(JSC::DFG::Node::successor):
(JSC::DFG::Node::catchOSREntryIndex const):
(JSC::DFG::Node::catchLocalPrediction):
(JSC::DFG::Node::isSwitch): Deleted.
* dfg/DFGNodeType.h:
* dfg/DFGOSREntry.cpp:
(JSC::DFG::prepareCatchOSREntry):
* dfg/DFGOSREntry.h:
* dfg/DFGOSREntrypointCreationPhase.cpp:
(JSC::DFG::OSREntrypointCreationPhase::run):
* dfg/DFGOSRExitCompilerCommon.cpp:
(JSC::DFG::handleExitCounts):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGPrePostNumbering.cpp:
(JSC::DFG::PrePostNumbering::PrePostNumbering): Deleted.
(JSC::DFG::PrePostNumbering::~PrePostNumbering): Deleted.
(WTF::printInternal): Deleted.
* dfg/DFGPrePostNumbering.h:
(): Deleted.
(JSC::DFG::PrePostNumbering::preNumber const): Deleted.
(JSC::DFG::PrePostNumbering::postNumber const): Deleted.
(JSC::DFG::PrePostNumbering::isStrictAncestorOf const): Deleted.
(JSC::DFG::PrePostNumbering::isAncestorOf const): Deleted.
(JSC::DFG::PrePostNumbering::isStrictDescendantOf const): Deleted.
(JSC::DFG::PrePostNumbering::isDescendantOf const): Deleted.
(JSC::DFG::PrePostNumbering::edgeKind const): Deleted.
* dfg/DFGPredictionInjectionPhase.cpp:
(JSC::DFG::PredictionInjectionPhase::run):
* dfg/DFGPredictionPropagationPhase.cpp:
* dfg/DFGPutStackSinkingPhase.cpp:
* dfg/DFGSSACalculator.cpp:
(JSC::DFG::SSACalculator::nonLocalReachingDef):
(JSC::DFG::SSACalculator::reachingDefAtTail):
* dfg/DFGSSACalculator.h:
(JSC::DFG::SSACalculator::computePhis):
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
(JSC::DFG::performSSAConversion):
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::compileCurrentBlock):
(JSC::DFG::SpeculativeJIT::checkArgumentTypes):
(JSC::DFG::SpeculativeJIT::createOSREntries):
(JSC::DFG::SpeculativeJIT::linkOSREntries):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStaticExecutionCountEstimationPhase.cpp:
(JSC::DFG::StaticExecutionCountEstimationPhase::run):
* dfg/DFGStrengthReductionPhase.cpp:
(JSC::DFG::StrengthReductionPhase::handleNode):
* dfg/DFGTierUpCheckInjectionPhase.cpp:
(JSC::DFG::TierUpCheckInjectionPhase::run):
(JSC::DFG::TierUpCheckInjectionPhase::buildNaturalLoopToLoopHintMap):
* dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::run):
* dfg/DFGValidate.cpp:
* ftl/FTLLink.cpp:
(JSC::FTL::link):
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::lower):
(JSC::FTL::DFG::LowerDFGToB3::safelyInvalidateAfterTermination):
(JSC::FTL::DFG::LowerDFGToB3::isValid):
* jit/JIT.h:
* jit/JITInlines.h:
(JSC::JIT::callOperation):
* jit/JITOpcodes.cpp:
(JSC::JIT::emit_op_catch):
* jit/JITOpcodes32_64.cpp:
(JSC::JIT::emit_op_catch):
* jit/JITOperations.cpp:
* jit/JITOperations.h:
* llint/LLIntSlowPaths.cpp:
(JSC::LLInt::LLINT_SLOW_PATH_DECL):
* llint/LLIntSlowPaths.h:
* llint/LowLevelInterpreter32_64.asm:
* llint/LowLevelInterpreter64.asm:

Source/WTF:

This patch generalizes the BackwardsGraph fake root into a more generalizable
class called SingleRootGraph. SingleRootGraph exposes the general graph interface
used in Dominators and NaturalLoops. SingleRootGraph takes as input a graph with
the normal graph interface, but also allows the input graph to contain more than
one root. SingleRootGraph then exposes a single root, which it creates, that has
an outgoing edge to all the roots in the original graph.

* WTF.xcodeproj/project.pbxproj:
* wtf/BackwardsGraph.h:
(WTF::BackwardsGraph::dump const):
(WTF::BackwardsGraph::rootName): Deleted.
(WTF::BackwardsGraph::Node::Node): Deleted.
(WTF::BackwardsGraph::Node::root): Deleted.
(WTF::BackwardsGraph::Node::operator== const): Deleted.
(WTF::BackwardsGraph::Node::operator!= const): Deleted.
(WTF::BackwardsGraph::Node::operator bool const): Deleted.
(WTF::BackwardsGraph::Node::isRoot const): Deleted.
(WTF::BackwardsGraph::Node::node const): Deleted.
(): Deleted.
(WTF::BackwardsGraph::Set::Set): Deleted.
(WTF::BackwardsGraph::Set::add): Deleted.
(WTF::BackwardsGraph::Set::remove): Deleted.
(WTF::BackwardsGraph::Set::contains): Deleted.
(WTF::BackwardsGraph::Set::dump const): Deleted.
(WTF::BackwardsGraph::Map::Map): Deleted.
(WTF::BackwardsGraph::Map::clear): Deleted.
(WTF::BackwardsGraph::Map::size const): Deleted.
(WTF::BackwardsGraph::Map::operator[]): Deleted.
(WTF::BackwardsGraph::Map::operator[] const): Deleted.
* wtf/Dominators.h:
(WTF::Dominators::Dominators):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
(WTF::Dominators::iteratedDominanceFrontierOf const):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl const):
* wtf/SingleRootGraph.h: Added.
(WTF::SingleRootGraphNode::rootName):
(WTF::SingleRootGraphNode::SingleRootGraphNode):
(WTF::SingleRootGraphNode::root):
(WTF::SingleRootGraphNode::operator== const):
(WTF::SingleRootGraphNode::operator!= const):
(WTF::SingleRootGraphNode::operator bool const):
(WTF::SingleRootGraphNode::isRoot const):
(WTF::SingleRootGraphNode::node const):
(WTF::SingleRootGraphSet::add):
(WTF::SingleRootGraphSet::remove):
(WTF::SingleRootGraphSet::contains):
(WTF::SingleRootGraphSet::dump const):
(WTF::SingleRootMap::SingleRootMap):
(WTF::SingleRootMap::clear):
(WTF::SingleRootMap::size const):
(WTF::SingleRootMap::operator[]):
(WTF::SingleRootMap::operator[] const):
(WTF::SingleRootGraph::SingleRootGraph):
(WTF::SingleRootGraph::root const):
(WTF::SingleRootGraph::newMap):
(WTF::SingleRootGraph::successors const):
(WTF::SingleRootGraph::predecessors const):
(WTF::SingleRootGraph::index const):
(WTF::SingleRootGraph::node const):
(WTF::SingleRootGraph::numNodes const):
(WTF::SingleRootGraph::dump const):
(WTF::SingleRootGraph::assertIsConsistent const):

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

90 files changed:
JSTests/ChangeLog
JSTests/microbenchmarks/delta-blue-try-catch.js [new file with mode: 0644]
JSTests/microbenchmarks/fake-iterators-that-throw-when-finished.js [new file with mode: 0644]
JSTests/microbenchmarks/try-catch-word-count.js [new file with mode: 0644]
JSTests/stress/catch-set-argument-speculation-failure.js [new file with mode: 0644]
JSTests/stress/osr-enter-to-catch-with-set-local-type-check-failure.js [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/BytecodeDumper.cpp
Source/JavaScriptCore/bytecode/BytecodeList.json
Source/JavaScriptCore/bytecode/BytecodeUseDef.h
Source/JavaScriptCore/bytecode/CodeBlock.cpp
Source/JavaScriptCore/bytecode/CodeBlock.h
Source/JavaScriptCore/bytecode/ValueProfile.h
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
Source/JavaScriptCore/bytecompiler/BytecodeGenerator.h
Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGBackwardsCFG.h
Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGCFG.h
Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h
Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
Source/JavaScriptCore/dfg/DFGDisassembler.cpp
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGDominators.h
Source/JavaScriptCore/dfg/DFGEdgeDominates.h
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGFlushFormat.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp
Source/JavaScriptCore/dfg/DFGJITCode.cpp
Source/JavaScriptCore/dfg/DFGJITCode.h
Source/JavaScriptCore/dfg/DFGJITCompiler.cpp
Source/JavaScriptCore/dfg/DFGJITCompiler.h
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/dfg/DFGLiveCatchVariablePreservationPhase.cpp
Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGMaximalFlushInsertionPhase.cpp
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGNaturalLoops.h
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGOSREntry.cpp
Source/JavaScriptCore/dfg/DFGOSREntry.h
Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGOSRExitCompilerCommon.cpp
Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp
Source/JavaScriptCore/dfg/DFGPrePostNumbering.h
Source/JavaScriptCore/dfg/DFGPredictionInjectionPhase.cpp
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGSSACalculator.cpp
Source/JavaScriptCore/dfg/DFGSSACalculator.h
Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
Source/JavaScriptCore/dfg/DFGSafeToExecute.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT32_64.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT64.cpp
Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp
Source/JavaScriptCore/dfg/DFGStrengthReductionPhase.cpp
Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp
Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/JavaScriptCore/ftl/FTLLink.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
Source/JavaScriptCore/jit/JIT.h
Source/JavaScriptCore/jit/JITInlines.h
Source/JavaScriptCore/jit/JITOpcodes.cpp
Source/JavaScriptCore/jit/JITOpcodes32_64.cpp
Source/JavaScriptCore/jit/JITOperations.cpp
Source/JavaScriptCore/jit/JITOperations.h
Source/JavaScriptCore/llint/LLIntSlowPaths.cpp
Source/JavaScriptCore/llint/LLIntSlowPaths.h
Source/JavaScriptCore/llint/LowLevelInterpreter32_64.asm
Source/JavaScriptCore/llint/LowLevelInterpreter64.asm
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BackwardsGraph.h
Source/WTF/wtf/Dominators.h
Source/WTF/wtf/SingleRootGraph.h [new file with mode: 0644]

index 88226ac..174808b 100644 (file)
@@ -1,3 +1,137 @@
+2017-08-25  Saam Barati  <sbarati@apple.com>
+
+        Support compiling catch in the DFG
+        https://bugs.webkit.org/show_bug.cgi?id=174590
+        <rdar://problem/34047845>
+
+        Reviewed by Filip Pizlo.
+
+        * microbenchmarks/delta-blue-try-catch.js: Added.
+        (exception):
+        (value):
+        (OrderedCollection):
+        (OrderedCollection.prototype.add):
+        (OrderedCollection.prototype.at):
+        (OrderedCollection.prototype.size):
+        (OrderedCollection.prototype.removeFirst):
+        (OrderedCollection.prototype.remove):
+        (Strength):
+        (Strength.stronger):
+        (Strength.weaker):
+        (Strength.weakestOf):
+        (Strength.strongest):
+        (Strength.prototype.nextWeaker):
+        (Constraint):
+        (Constraint.prototype.addConstraint):
+        (Constraint.prototype.satisfy):
+        (Constraint.prototype.destroyConstraint):
+        (Constraint.prototype.isInput):
+        (UnaryConstraint):
+        (UnaryConstraint.prototype.addToGraph):
+        (UnaryConstraint.prototype.chooseMethod):
+        (UnaryConstraint.prototype.isSatisfied):
+        (UnaryConstraint.prototype.markInputs):
+        (UnaryConstraint.prototype.output):
+        (UnaryConstraint.prototype.recalculate):
+        (UnaryConstraint.prototype.markUnsatisfied):
+        (UnaryConstraint.prototype.inputsKnown):
+        (UnaryConstraint.prototype.removeFromGraph):
+        (StayConstraint):
+        (StayConstraint.prototype.execute):
+        (EditConstraint.prototype.isInput):
+        (EditConstraint.prototype.execute):
+        (BinaryConstraint):
+        (BinaryConstraint.prototype.chooseMethod):
+        (BinaryConstraint.prototype.addToGraph):
+        (BinaryConstraint.prototype.isSatisfied):
+        (BinaryConstraint.prototype.markInputs):
+        (BinaryConstraint.prototype.input):
+        (BinaryConstraint.prototype.output):
+        (BinaryConstraint.prototype.recalculate):
+        (BinaryConstraint.prototype.markUnsatisfied):
+        (BinaryConstraint.prototype.inputsKnown):
+        (BinaryConstraint.prototype.removeFromGraph):
+        (ScaleConstraint):
+        (ScaleConstraint.prototype.addToGraph):
+        (ScaleConstraint.prototype.removeFromGraph):
+        (ScaleConstraint.prototype.markInputs):
+        (ScaleConstraint.prototype.execute):
+        (ScaleConstraint.prototype.recalculate):
+        (EqualityConstraint):
+        (EqualityConstraint.prototype.execute):
+        (Variable):
+        (Variable.prototype.addConstraint):
+        (Variable.prototype.removeConstraint):
+        (Planner):
+        (Planner.prototype.incrementalAdd):
+        (Planner.prototype.incrementalRemove):
+        (Planner.prototype.newMark):
+        (Planner.prototype.makePlan):
+        (Planner.prototype.extractPlanFromConstraints):
+        (Planner.prototype.addPropagate):
+        (Planner.prototype.removePropagateFrom):
+        (Planner.prototype.addConstraintsConsumingTo):
+        (Plan):
+        (Plan.prototype.addConstraint):
+        (Plan.prototype.size):
+        (Plan.prototype.constraintAt):
+        (Plan.prototype.execute):
+        (chainTest):
+        (projectionTest):
+        (change):
+        (deltaBlue):
+        * microbenchmarks/fake-iterators-that-throw-when-finished.js: Added.
+        (assert):
+        (Numbers):
+        (Numbers.prototype.next):
+        (return.Transpose):
+        (return.Transpose.prototype.next):
+        (transpose):
+        (verifyEven):
+        (verifyString):
+        (foo):
+        (runIterators):
+        * microbenchmarks/try-catch-word-count.js: Added.
+        (let.assert):
+        (EOF):
+        (let.texts):
+        (let.o.apply):
+        (foo):
+        (bar):
+        (f):
+        (run):
+        (test1):
+        (test2):
+        (test3):
+        (fn):
+        (A):
+        (B):
+        (A.prototype.getValue):
+        (B.prototype.getParentValue):
+        (strlen):
+        (sum.0):
+        (test):
+        (result.test.o):
+        (set add.set add):
+        (set forEach):
+        (stringHash):
+        (set if):
+        (testFunction):
+        (set delete.set has.set add):
+        * stress/catch-set-argument-speculation-failure.js: Added.
+        (o):
+        (e):
+        (e2):
+        (escape):
+        (baz):
+        (noInline.run):
+        (noInline):
+        * stress/osr-enter-to-catch-with-set-local-type-check-failure.js: Added.
+        (foo):
+        (e):
+        (baz):
+        (bar):
+
 2017-08-24  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r221119, r221124, and r221143.
diff --git a/JSTests/microbenchmarks/delta-blue-try-catch.js b/JSTests/microbenchmarks/delta-blue-try-catch.js
new file mode 100644 (file)
index 0000000..e391cfc
--- /dev/null
@@ -0,0 +1,905 @@
+// Copyright 2008 the V8 project authors. All rights reserved.
+// Copyright 1996 John Maloney and Mario Wolczko.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 2 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+// This implementation of the DeltaBlue benchmark is derived
+// from the Smalltalk implementation by John Maloney and Mario
+// Wolczko. Some parts have been translated directly, whereas
+// others have been modified more aggresively to make it feel
+// more like a JavaScript program.
+
+let __exceptionCounter = 0;
+function exception() {
+    if (__exceptionCounter++ % 35 === 0)
+        throw __exceptionCounter;
+}
+
+
+/**
+ * A JavaScript implementation of the DeltaBlue constraint-solving
+ * algorithm, as described in:
+ *
+ * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
+ *   Bjorn N. Freeman-Benson and John Maloney
+ *   January 1990 Communications of the ACM,
+ *   also available as University of Washington TR 89-08-06.
+ *
+ * Beware: this benchmark is written in a grotesque style where
+ * the constraint model is built by side-effects from constructors.
+ * I've kept it this way to avoid deviating too much from the original
+ * implementation.
+ */
+
+
+/* --- O b j e c t   M o d e l --- */
+
+Object.defineProperty(Object.prototype, "inheritsFrom", {
+  
+  value: function (shuper) {
+    function Inheriter() { }
+    Inheriter.prototype = shuper.prototype;
+    this.prototype = new Inheriter();
+    this.superConstructor = shuper;
+  }
+});
+
+function OrderedCollection() {
+  this.elms = new Array();
+}
+
+OrderedCollection.prototype.add = function (elm) {
+  this.elms.push(elm);
+}
+
+OrderedCollection.prototype.at = function (index) {
+  return this.elms[index];
+}
+
+OrderedCollection.prototype.size = function () {
+  return this.elms.length;
+}
+
+OrderedCollection.prototype.removeFirst = function () {
+  return this.elms.pop();
+}
+
+OrderedCollection.prototype.remove = function (elm) {
+  var index = 0, skipped = 0;
+  for (var i = 0; i < this.elms.length; i++) {
+    var value = this.elms[i];
+    if (value != elm) {
+      this.elms[index] = value;
+      index++;
+    } else {
+      skipped++;
+    }
+    try { exception(); } catch(e) { }
+  }
+  for (var i = 0; i < skipped; i++) {
+    this.elms.pop();
+    try { exception(); } catch(e) { }
+  }
+}
+
+/* --- *
+ * S t r e n g t h
+ * --- */
+
+/**
+ * Strengths are used to measure the relative importance of constraints.
+ * New strengths may be inserted in the strength hierarchy without
+ * disrupting current constraints.  Strengths cannot be created outside
+ * this class, so pointer comparison can be used for value comparison.
+ */
+function Strength(strengthValue, name) {
+  this.strengthValue = strengthValue;
+  this.name = name;
+}
+
+Strength.stronger = function (s1, s2) {
+  return s1.strengthValue < s2.strengthValue;
+}
+
+Strength.weaker = function (s1, s2) {
+  return s1.strengthValue > s2.strengthValue;
+}
+
+Strength.weakestOf = function (s1, s2) {
+  return this.weaker(s1, s2) ? s1 : s2;
+}
+
+Strength.strongest = function (s1, s2) {
+  return this.stronger(s1, s2) ? s1 : s2;
+}
+
+Strength.prototype.nextWeaker = function () {
+  switch (this.strengthValue) {
+    case 0: return Strength.WEAKEST;
+    case 1: return Strength.WEAK_DEFAULT;
+    case 2: return Strength.NORMAL;
+    case 3: return Strength.STRONG_DEFAULT;
+    case 4: return Strength.PREFERRED;
+    case 5: return Strength.REQUIRED;
+  }
+}
+
+// Strength constants.
+Strength.REQUIRED        = new Strength(0, "required");
+Strength.STONG_PREFERRED = new Strength(1, "strongPreferred");
+Strength.PREFERRED       = new Strength(2, "preferred");
+Strength.STRONG_DEFAULT  = new Strength(3, "strongDefault");
+Strength.NORMAL          = new Strength(4, "normal");
+Strength.WEAK_DEFAULT    = new Strength(5, "weakDefault");
+Strength.WEAKEST         = new Strength(6, "weakest");
+
+/* --- *
+ * C o n s t r a i n t
+ * --- */
+
+/**
+ * An abstract class representing a system-maintainable relationship
+ * (or "constraint") between a set of variables. A constraint supplies
+ * a strength instance variable; concrete subclasses provide a means
+ * of storing the constrained variables and other information required
+ * to represent a constraint.
+ */
+function Constraint(strength) {
+  this.strength = strength;
+}
+
+/**
+ * Activate this constraint and attempt to satisfy it.
+ */
+Constraint.prototype.addConstraint = function () {
+  this.addToGraph();
+  planner.incrementalAdd(this);
+}
+
+/**
+ * Attempt to find a way to enforce this constraint. If successful,
+ * record the solution, perhaps modifying the current dataflow
+ * graph. Answer the constraint that this constraint overrides, if
+ * there is one, or nil, if there isn't.
+ * Assume: I am not already satisfied.
+ */
+Constraint.prototype.satisfy = function (mark) {
+  this.chooseMethod(mark);
+  if (!this.isSatisfied()) {
+    if (this.strength == Strength.REQUIRED)
+      alert("Could not satisfy a required constraint!");
+    return null;
+  }
+  this.markInputs(mark);
+  var out = this.output();
+  var overridden = out.determinedBy;
+  if (overridden != null) overridden.markUnsatisfied();
+  out.determinedBy = this;
+  if (!planner.addPropagate(this, mark))
+    alert("Cycle encountered");
+  out.mark = mark;
+  return overridden;
+}
+
+Constraint.prototype.destroyConstraint = function () {
+  if (this.isSatisfied()) planner.incrementalRemove(this);
+  else this.removeFromGraph();
+}
+
+/**
+ * Normal constraints are not input constraints.  An input constraint
+ * is one that depends on external state, such as the mouse, the
+ * keybord, a clock, or some arbitraty piece of imperative code.
+ */
+Constraint.prototype.isInput = function () {
+  return false;
+}
+
+/* --- *
+ * U n a r y   C o n s t r a i n t
+ * --- */
+
+/**
+ * Abstract superclass for constraints having a single possible output
+ * variable.
+ */
+function UnaryConstraint(v, strength) {
+  UnaryConstraint.superConstructor.call(this, strength);
+  this.myOutput = v;
+  this.satisfied = false;
+  this.addConstraint();
+}
+
+UnaryConstraint.inheritsFrom(Constraint);
+
+/**
+ * Adds this constraint to the constraint graph
+ */
+UnaryConstraint.prototype.addToGraph = function () {
+  this.myOutput.addConstraint(this);
+  this.satisfied = false;
+}
+
+/**
+ * Decides if this constraint can be satisfied and records that
+ * decision.
+ */
+UnaryConstraint.prototype.chooseMethod = function (mark) {
+  this.satisfied = (this.myOutput.mark != mark)
+    && Strength.stronger(this.strength, this.myOutput.walkStrength);
+}
+
+/**
+ * Returns true if this constraint is satisfied in the current solution.
+ */
+UnaryConstraint.prototype.isSatisfied = function () {
+  return this.satisfied;
+}
+
+UnaryConstraint.prototype.markInputs = function (mark) {
+  // has no inputs
+}
+
+/**
+ * Returns the current output variable.
+ */
+UnaryConstraint.prototype.output = function () {
+  return this.myOutput;
+}
+
+/**
+ * Calculate the walkabout strength, the stay flag, and, if it is
+ * 'stay', the value for the current output of this constraint. Assume
+ * this constraint is satisfied.
+ */
+UnaryConstraint.prototype.recalculate = function () {
+  this.myOutput.walkStrength = this.strength;
+  this.myOutput.stay = !this.isInput();
+  if (this.myOutput.stay) this.execute(); // Stay optimization
+}
+
+/**
+ * Records that this constraint is unsatisfied
+ */
+UnaryConstraint.prototype.markUnsatisfied = function () {
+  this.satisfied = false;
+}
+
+UnaryConstraint.prototype.inputsKnown = function () {
+  return true;
+}
+
+UnaryConstraint.prototype.removeFromGraph = function () {
+  if (this.myOutput != null) this.myOutput.removeConstraint(this);
+  this.satisfied = false;
+}
+
+/* --- *
+ * S t a y   C o n s t r a i n t
+ * --- */
+
+/**
+ * Variables that should, with some level of preference, stay the same.
+ * Planners may exploit the fact that instances, if satisfied, will not
+ * change their output during plan execution.  This is called "stay
+ * optimization".
+ */
+function StayConstraint(v, str) {
+  StayConstraint.superConstructor.call(this, v, str);
+}
+
+StayConstraint.inheritsFrom(UnaryConstraint);
+
+StayConstraint.prototype.execute = function () {
+  // Stay constraints do nothing
+}
+
+/* --- *
+ * E d i t   C o n s t r a i n t
+ * --- */
+
+/**
+ * A unary input constraint used to mark a variable that the client
+ * wishes to change.
+ */
+function EditConstraint(v, str) {
+  EditConstraint.superConstructor.call(this, v, str);
+}
+
+EditConstraint.inheritsFrom(UnaryConstraint);
+
+/**
+ * Edits indicate that a variable is to be changed by imperative code.
+ */
+EditConstraint.prototype.isInput = function () {
+  return true;
+}
+
+EditConstraint.prototype.execute = function () {
+  // Edit constraints do nothing
+}
+
+/* --- *
+ * B i n a r y   C o n s t r a i n t
+ * --- */
+
+var Direction = new Object();
+Direction.NONE     = 0;
+Direction.FORWARD  = 1;
+Direction.BACKWARD = -1;
+
+/**
+ * Abstract superclass for constraints having two possible output
+ * variables.
+ */
+function BinaryConstraint(var1, var2, strength) {
+  BinaryConstraint.superConstructor.call(this, strength);
+  this.v1 = var1;
+  this.v2 = var2;
+  this.direction = Direction.NONE;
+  this.addConstraint();
+}
+
+BinaryConstraint.inheritsFrom(Constraint);
+
+/**
+ * Decides if this constraint can be satisfied and which way it
+ * should flow based on the relative strength of the variables related,
+ * and record that decision.
+ */
+BinaryConstraint.prototype.chooseMethod = function (mark) {
+  if (this.v1.mark == mark) {
+    this.direction = (this.v2.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength))
+      ? Direction.FORWARD
+      : Direction.NONE;
+  }
+  if (this.v2.mark == mark) {
+    this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength))
+      ? Direction.BACKWARD
+      : Direction.NONE;
+  }
+  if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) {
+    this.direction = Strength.stronger(this.strength, this.v1.walkStrength)
+      ? Direction.BACKWARD
+      : Direction.NONE;
+  } else {
+    this.direction = Strength.stronger(this.strength, this.v2.walkStrength)
+      ? Direction.FORWARD
+      : Direction.BACKWARD
+  }
+}
+
+/**
+ * Add this constraint to the constraint graph
+ */
+BinaryConstraint.prototype.addToGraph = function () {
+  this.v1.addConstraint(this);
+  this.v2.addConstraint(this);
+  this.direction = Direction.NONE;
+}
+
+/**
+ * Answer true if this constraint is satisfied in the current solution.
+ */
+BinaryConstraint.prototype.isSatisfied = function () {
+  return this.direction != Direction.NONE;
+}
+
+/**
+ * Mark the input variable with the given mark.
+ */
+BinaryConstraint.prototype.markInputs = function (mark) {
+  this.input().mark = mark;
+}
+
+/**
+ * Returns the current input variable
+ */
+BinaryConstraint.prototype.input = function () {
+  return (this.direction == Direction.FORWARD) ? this.v1 : this.v2;
+}
+
+/**
+ * Returns the current output variable
+ */
+BinaryConstraint.prototype.output = function () {
+  return (this.direction == Direction.FORWARD) ? this.v2 : this.v1;
+}
+
+/**
+ * Calculate the walkabout strength, the stay flag, and, if it is
+ * 'stay', the value for the current output of this
+ * constraint. Assume this constraint is satisfied.
+ */
+BinaryConstraint.prototype.recalculate = function () {
+  var ihn = this.input(), out = this.output();
+  out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
+  out.stay = ihn.stay;
+  if (out.stay) this.execute();
+}
+
+/**
+ * Record the fact that this constraint is unsatisfied.
+ */
+BinaryConstraint.prototype.markUnsatisfied = function () {
+  this.direction = Direction.NONE;
+}
+
+BinaryConstraint.prototype.inputsKnown = function (mark) {
+  var i = this.input();
+  return i.mark == mark || i.stay || i.determinedBy == null;
+}
+
+BinaryConstraint.prototype.removeFromGraph = function () {
+  if (this.v1 != null) this.v1.removeConstraint(this);
+  if (this.v2 != null) this.v2.removeConstraint(this);
+  this.direction = Direction.NONE;
+}
+
+/* --- *
+ * S c a l e   C o n s t r a i n t
+ * --- */
+
+/**
+ * Relates two variables by the linear scaling relationship: "v2 =
+ * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain
+ * this relationship but the scale factor and offset are considered
+ * read-only.
+ */
+function ScaleConstraint(src, scale, offset, dest, strength) {
+  this.direction = Direction.NONE;
+  this.scale = scale;
+  this.offset = offset;
+  ScaleConstraint.superConstructor.call(this, src, dest, strength);
+}
+
+ScaleConstraint.inheritsFrom(BinaryConstraint);
+
+/**
+ * Adds this constraint to the constraint graph.
+ */
+ScaleConstraint.prototype.addToGraph = function () {
+  ScaleConstraint.superConstructor.prototype.addToGraph.call(this);
+  this.scale.addConstraint(this);
+  this.offset.addConstraint(this);
+}
+
+ScaleConstraint.prototype.removeFromGraph = function () {
+  ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this);
+  if (this.scale != null) this.scale.removeConstraint(this);
+  if (this.offset != null) this.offset.removeConstraint(this);
+}
+
+ScaleConstraint.prototype.markInputs = function (mark) {
+  ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark);
+  this.scale.mark = this.offset.mark = mark;
+}
+
+/**
+ * Enforce this constraint. Assume that it is satisfied.
+ */
+ScaleConstraint.prototype.execute = function () {
+  if (this.direction == Direction.FORWARD) {
+    this.v2.value = this.v1.value * this.scale.value + this.offset.value;
+  } else {
+    this.v1.value = (this.v2.value - this.offset.value) / this.scale.value;
+  }
+}
+
+/**
+ * Calculate the walkabout strength, the stay flag, and, if it is
+ * 'stay', the value for the current output of this constraint. Assume
+ * this constraint is satisfied.
+ */
+ScaleConstraint.prototype.recalculate = function () {
+  var ihn = this.input(), out = this.output();
+  out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength);
+  out.stay = ihn.stay && this.scale.stay && this.offset.stay;
+  if (out.stay) this.execute();
+}
+
+/* --- *
+ * E q u a l i t  y   C o n s t r a i n t
+ * --- */
+
+/**
+ * Constrains two variables to have the same value.
+ */
+function EqualityConstraint(var1, var2, strength) {
+  EqualityConstraint.superConstructor.call(this, var1, var2, strength);
+}
+
+EqualityConstraint.inheritsFrom(BinaryConstraint);
+
+/**
+ * Enforce this constraint. Assume that it is satisfied.
+ */
+EqualityConstraint.prototype.execute = function () {
+  this.output().value = this.input().value;
+}
+
+/* --- *
+ * V a r i a b l e
+ * --- */
+
+/**
+ * A constrained variable. In addition to its value, it maintain the
+ * structure of the constraint graph, the current dataflow graph, and
+ * various parameters of interest to the DeltaBlue incremental
+ * constraint solver.
+ **/
+function Variable(name, initialValue) {
+  this.value = initialValue || 0;
+  this.constraints = new OrderedCollection();
+  this.determinedBy = null;
+  this.mark = 0;
+  this.walkStrength = Strength.WEAKEST;
+  this.stay = true;
+  this.name = name;
+}
+
+/**
+ * Add the given constraint to the set of all constraints that refer
+ * this variable.
+ */
+Variable.prototype.addConstraint = function (c) {
+  this.constraints.add(c);
+}
+
+/**
+ * Removes all traces of c from this variable.
+ */
+Variable.prototype.removeConstraint = function (c) {
+  this.constraints.remove(c);
+  if (this.determinedBy == c) this.determinedBy = null;
+}
+
+/* --- *
+ * P l a n n e r
+ * --- */
+
+/**
+ * The DeltaBlue planner
+ */
+function Planner() {
+  this.currentMark = 0;
+}
+
+/**
+ * Attempt to satisfy the given constraint and, if successful,
+ * incrementally update the dataflow graph.  Details: If satifying
+ * the constraint is successful, it may override a weaker constraint
+ * on its output. The algorithm attempts to resatisfy that
+ * constraint using some other method. This process is repeated
+ * until either a) it reaches a variable that was not previously
+ * determined by any constraint or b) it reaches a constraint that
+ * is too weak to be satisfied using any of its methods. The
+ * variables of constraints that have been processed are marked with
+ * a unique mark value so that we know where we've been. This allows
+ * the algorithm to avoid getting into an infinite loop even if the
+ * constraint graph has an inadvertent cycle.
+ */
+Planner.prototype.incrementalAdd = function (c) {
+  var mark = this.newMark();
+  var overridden = c.satisfy(mark);
+  while (overridden != null)
+    overridden = overridden.satisfy(mark);
+}
+
+/**
+ * Entry point for retracting a constraint. Remove the given
+ * constraint and incrementally update the dataflow graph.
+ * Details: Retracting the given constraint may allow some currently
+ * unsatisfiable downstream constraint to be satisfied. We therefore collect
+ * a list of unsatisfied downstream constraints and attempt to
+ * satisfy each one in turn. This list is traversed by constraint
+ * strength, strongest first, as a heuristic for avoiding
+ * unnecessarily adding and then overriding weak constraints.
+ * Assume: c is satisfied.
+ */
+Planner.prototype.incrementalRemove = function (c) {
+  var out = c.output();
+  c.markUnsatisfied();
+  c.removeFromGraph();
+  var unsatisfied = this.removePropagateFrom(out);
+  var strength = Strength.REQUIRED;
+  do {
+    for (var i = 0; i < unsatisfied.size(); i++) {
+      var u = unsatisfied.at(i);
+      if (u.strength == strength)
+        this.incrementalAdd(u);
+    }
+    strength = strength.nextWeaker();
+  } while (strength != Strength.WEAKEST);
+}
+
+/**
+ * Select a previously unused mark value.
+ */
+Planner.prototype.newMark = function () {
+  return ++this.currentMark;
+}
+
+/**
+ * Extract a plan for resatisfaction starting from the given source
+ * constraints, usually a set of input constraints. This method
+ * assumes that stay optimization is desired; the plan will contain
+ * only constraints whose output variables are not stay. Constraints
+ * that do no computation, such as stay and edit constraints, are
+ * not included in the plan.
+ * Details: The outputs of a constraint are marked when it is added
+ * to the plan under construction. A constraint may be appended to
+ * the plan when all its input variables are known. A variable is
+ * known if either a) the variable is marked (indicating that has
+ * been computed by a constraint appearing earlier in the plan), b)
+ * the variable is 'stay' (i.e. it is a constant at plan execution
+ * time), or c) the variable is not determined by any
+ * constraint. The last provision is for past states of history
+ * variables, which are not stay but which are also not computed by
+ * any constraint.
+ * Assume: sources are all satisfied.
+ */
+Planner.prototype.makePlan = function (sources) {
+  var mark = this.newMark();
+  var plan = new Plan();
+  var todo = sources;
+  while (todo.size() > 0) {
+    var c = todo.removeFirst();
+    if (c.output().mark != mark && c.inputsKnown(mark)) {
+      plan.addConstraint(c);
+      c.output().mark = mark;
+      this.addConstraintsConsumingTo(c.output(), todo);
+    }
+  }
+  return plan;
+}
+
+/**
+ * Extract a plan for resatisfying starting from the output of the
+ * given constraints, usually a set of input constraints.
+ */
+Planner.prototype.extractPlanFromConstraints = function (constraints) {
+  var sources = new OrderedCollection();
+  for (var i = 0; i < constraints.size(); i++) {
+    try { exception(); } catch(e) { }
+    var c = constraints.at(i);
+    try { exception(); } catch(e) { }
+    if (c.isInput() && c.isSatisfied())
+      // not in plan already and eligible for inclusion
+      sources.add(c);
+  }
+  return this.makePlan(sources);
+}
+
+/**
+ * Recompute the walkabout strengths and stay flags of all variables
+ * downstream of the given constraint and recompute the actual
+ * values of all variables whose stay flag is true. If a cycle is
+ * detected, remove the given constraint and answer
+ * false. Otherwise, answer true.
+ * Details: Cycles are detected when a marked variable is
+ * encountered downstream of the given constraint. The sender is
+ * assumed to have marked the inputs of the given constraint with
+ * the given mark. Thus, encountering a marked node downstream of
+ * the output constraint means that there is a path from the
+ * constraint's output to one of its inputs.
+ */
+Planner.prototype.addPropagate = function (c, mark) {
+  var todo = new OrderedCollection();
+  todo.add(c);
+  while (todo.size() > 0) {
+    var d = todo.removeFirst();
+    if (d.output().mark == mark) {
+      this.incrementalRemove(c);
+      return false;
+    }
+    d.recalculate();
+    this.addConstraintsConsumingTo(d.output(), todo);
+  }
+  return true;
+}
+
+
+/**
+ * Update the walkabout strengths and stay flags of all variables
+ * downstream of the given constraint. Answer a collection of
+ * unsatisfied constraints sorted in order of decreasing strength.
+ */
+Planner.prototype.removePropagateFrom = function (out) {
+  out.determinedBy = null;
+  out.walkStrength = Strength.WEAKEST;
+  out.stay = true;
+  var unsatisfied = new OrderedCollection();
+  var todo = new OrderedCollection();
+  todo.add(out);
+  while (todo.size() > 0) {
+    var v = todo.removeFirst();
+    for (var i = 0; i < v.constraints.size(); i++) {
+      var c = v.constraints.at(i);
+      try { exception(); } catch(e) { }
+      if (!c.isSatisfied())
+        unsatisfied.add(c);
+    }
+    var determining = v.determinedBy;
+    for (var i = 0; i < v.constraints.size(); i++) {
+      var next = v.constraints.at(i);
+      if (next != determining && next.isSatisfied()) {
+        next.recalculate();
+        todo.add(next.output());
+      }
+      try { exception(); } catch(e) { }
+    }
+  }
+  return unsatisfied;
+}
+
+Planner.prototype.addConstraintsConsumingTo = function (v, coll) {
+  var determining = v.determinedBy;
+  var cc = v.constraints;
+  for (var i = 0; i < cc.size(); i++) {
+    var c = cc.at(i);
+    try { exception(); } catch(e) { }
+    if (c != determining && c.isSatisfied())
+      coll.add(c);
+  }
+}
+
+/* --- *
+ * P l a n
+ * --- */
+
+/**
+ * A Plan is an ordered list of constraints to be executed in sequence
+ * to resatisfy all currently satisfiable constraints in the face of
+ * one or more changing inputs.
+ */
+function Plan() {
+  this.v = new OrderedCollection();
+}
+
+Plan.prototype.addConstraint = function (c) {
+  this.v.add(c);
+}
+
+Plan.prototype.size = function () {
+  return this.v.size();
+}
+
+Plan.prototype.constraintAt = function (index) {
+  return this.v.at(index);
+}
+
+Plan.prototype.execute = function () {
+  for (var i = 0; i < this.size(); i++) {
+    var c = this.constraintAt(i);
+    try { exception(); } catch(e) { }
+    c.execute();
+  }
+}
+
+/* --- *
+ * M a i n
+ * --- */
+
+/**
+ * This is the standard DeltaBlue benchmark. A long chain of equality
+ * constraints is constructed with a stay constraint on one end. An
+ * edit constraint is then added to the opposite end and the time is
+ * measured for adding and removing this constraint, and extracting
+ * and executing a constraint satisfaction plan. There are two cases.
+ * In case 1, the added constraint is stronger than the stay
+ * constraint and values must propagate down the entire length of the
+ * chain. In case 2, the added constraint is weaker than the stay
+ * constraint so it cannot be accomodated. The cost in this case is,
+ * of course, very low. Typical situations lie somewhere between these
+ * two extremes.
+ */
+function chainTest(n) {
+  planner = new Planner();
+  var prev = null, first = null, last = null;
+
+  // Build chain of n equality constraints
+  for (var i = 0; i <= n; i++) {
+    var name = "v" + i;
+    var v = new Variable(name);
+    if (prev != null)
+      new EqualityConstraint(prev, v, Strength.REQUIRED);
+    if (i == 0) first = v;
+    if (i == n) last = v;
+    try { exception(); } catch(e) { }
+    prev = v;
+  }
+
+  new StayConstraint(last, Strength.STRONG_DEFAULT);
+  var edit = new EditConstraint(first, Strength.PREFERRED);
+  var edits = new OrderedCollection();
+  edits.add(edit);
+  var plan = planner.extractPlanFromConstraints(edits);
+  for (var i = 0; i < 100; i++) {
+    first.value = i;
+    plan.execute();
+    if (last.value != i)
+      alert("Chain test failed.");
+    try { exception(); } catch(e) { }
+  }
+}
+
+/**
+ * This test constructs a two sets of variables related to each
+ * other by a simple linear transformation (scale and offset). The
+ * time is measured to change a variable on either side of the
+ * mapping and to change the scale and offset factors.
+ */
+function projectionTest(n) {
+  planner = new Planner();
+  var scale = new Variable("scale", 10);
+  var offset = new Variable("offset", 1000);
+  var src = null, dst = null;
+
+  var dests = new OrderedCollection();
+  for (var i = 0; i < n; i++) {
+    src = new Variable("src" + i, i);
+    dst = new Variable("dst" + i, i);
+    dests.add(dst);
+    try { exception(); } catch(e) { }
+    new StayConstraint(src, Strength.NORMAL);
+    new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED);
+  }
+
+  change(src, 17);
+  if (dst.value != 1170) alert("Projection 1 failed");
+  change(dst, 1050);
+  if (src.value != 5) alert("Projection 2 failed");
+  change(scale, 5);
+  for (var i = 0; i < n - 1; i++) {
+    if (dests.at(i).value != i * 5 + 1000)
+      alert("Projection 3 failed");
+    try { exception(); } catch(e) { }
+  }
+  change(offset, 2000);
+  for (var i = 0; i < n - 1; i++) {
+    if (dests.at(i).value != i * 5 + 2000)
+      alert("Projection 4 failed");
+    try { exception(); } catch(e) { }
+  }
+}
+
+function change(v, newValue) {
+  var edit = new EditConstraint(v, Strength.PREFERRED);
+  var edits = new OrderedCollection();
+  edits.add(edit);
+  var plan = planner.extractPlanFromConstraints(edits);
+  for (var i = 0; i < 10; i++) {
+    v.value = newValue;
+    plan.execute();
+  }
+  edit.destroyConstraint();
+}
+
+// Global variable holding the current planner.
+var planner = null;
+
+function deltaBlue() {
+  chainTest(100);
+  projectionTest(100);
+}
+
+{
+    let start = Date.now();
+    for (let i = 0; i < 50; ++i)
+        deltaBlue();
+}
+
diff --git a/JSTests/microbenchmarks/fake-iterators-that-throw-when-finished.js b/JSTests/microbenchmarks/fake-iterators-that-throw-when-finished.js
new file mode 100644 (file)
index 0000000..8525118
--- /dev/null
@@ -0,0 +1,78 @@
+function assert(b) {
+    if (!b)
+        throw new Error("Bad");
+}
+
+class Numbers {
+    constructor(limit = 100) {
+        this.limit = limit;
+        this.item = 0;
+    }
+
+    next() {
+        if (this.item >= this.limit)
+            throw "done";
+        return this.item++;
+    }
+}
+
+function transpose(I, f) {
+    return class Transpose {
+        constructor(...args) {
+            this.iterator = new I(...args);
+        }
+
+        next() {
+            return f(this.iterator.next());
+        }
+    };
+}
+
+let EvenNumbers = transpose(Numbers, (x)=>x*2);
+function verifyEven(prev, cur) {
+    assert(cur.value % 2 === 0);
+    assert(!prev.value || prev.value+2 === cur.value);
+}
+
+let StringNumbers = transpose(Numbers, (x)=>`${x}`);
+function verifyString(_, cur) {
+    assert(cur.value === `${cur.value}`);
+}
+
+let iterators = [
+    [Numbers, function() {}],
+    [Numbers, function() {}],
+    [StringNumbers, verifyString],
+    [EvenNumbers, verifyEven],
+    [EvenNumbers, verifyEven],
+];
+
+function foo(i) {}
+noInline(foo);
+
+function runIterators() {
+    for (let [iterator, verify] of iterators) {
+        let i = new iterator;
+        let prev = {};
+        while (true) {
+            let cur = {};
+            try {
+                cur.value = i.next();
+                verify(prev, cur);
+            } catch(e) {
+                if (e !== "done")
+                    throw new Error("Bad: " + e);
+                break;
+            }
+            prev = cur;
+        }
+    }
+}
+
+{
+    let start = Date.now();
+    for (let i = 0; i < 5000; ++i)
+        runIterators();
+    if (true)
+        print(Date.now() - start);
+}
diff --git a/JSTests/microbenchmarks/try-catch-word-count.js b/JSTests/microbenchmarks/try-catch-word-count.js
new file mode 100644 (file)
index 0000000..6ebe82c
--- /dev/null
@@ -0,0 +1,903 @@
+"use strict";
+
+let assert = (b, m) => {
+    if (!b)
+        throw new Error("Bad assertion: " + m);
+}
+
+class EOF extends Error { };
+
+let texts = [`function foo() {
+    var o = {};
+    o.a = 1;
+    o.b = 2;
+    o.c = 3;
+    o.d = 4;
+    o.e = 5;
+    o.f = 6;
+    o.g = 7;
+    return o;
+}
+
+var result = 0;
+for (var i = 0; i < 100000; ++i)
+    result += foo().a;
+
+if (result != 100000)
+    throw "Error, bad result: " + result;
+
+`,`"use strict";
+
+(function() {
+    let o = {
+        apply(a, b) {
+            return a + b;
+        }
+    };
+    
+    function foo() {
+        let result = 0;
+        for (let i = 0; i < 1000; ++i)
+            result = o.apply(result, 1);
+        return result;
+    }
+    
+    noInline(foo);
+    
+    let result = 0;
+    for (let i = 0; i < 10000; ++i)
+        result += foo();
+    
+    if (result != 10000000)
+        throw new "Bad result: " + result;
+})();
+
+`,`function foo(a, b) {
+    return arguments[0] + b;
+}
+
+noInline(foo);
+
+for (var i = 0; i < 1000000; ++i) {
+    var result = foo(i, 1);
+    if (result != i + 1)
+        throw "Error: bad result: " + result;
+}
+`,`function foo() { return arguments; }
+noInline(foo);
+
+function bar(o) {
+    var tmp = o[0];
+    var result = 0;
+    for (var i = 0; i < 1000; ++i) {
+        if (tmp)
+            result += tmp * i;
+    }
+    return result;
+}
+noInline(bar);
+
+var result = 0;
+var o = foo();
+for (var i = 0; i < 10000; ++i)
+    result += bar(o);
+
+if (result !== 0)
+    throw "Error: bad result: " + result;
+`,`function foo() {
+    "use strict";
+    return [...arguments];
+
+}
+
+noInline(foo);
+
+for (var i = 0; i < 200000; ++i) {
+    var result = foo(i);
+    if (result[0] != i)
+        throw "Error: bad result: " + result;
+}
+`,`function foo() {
+    return arguments[0];
+}
+
+noInline(foo);
+
+for (var i = 0; i < 1000000; ++i) {
+    var result = foo(i);
+    if (result != i)
+        throw "Error: bad result: " + result;
+}
+`,`function foo(a, b) {
+    return a + b;
+}
+
+for (var i = 0; i < 100000; ++i) {
+    var result = foo(1, 2, 3);
+    if (result != 3)
+        throw "Bad result: " + result;
+}
+
+`,`function foo(a) {
+    var result = a[0];
+    if (result)
+        result += a[1];
+    if (result)
+        result += a[2];
+    if (result)
+        result += a[3];
+    if (result)
+        result += a[4];
+    return result;
+}
+
+var result = 0;
+
+for (var i = 0; i < 100000; ++i) {
+    var array = [1, 2, 3, 4, 5];
+    if (i & 1)
+        array.f = 42;
+    result += foo(array);
+}
+
+if (result != 1500000)
+    throw "Error: bad result: " + result;
+`,`//@ runNoFTL
+
+var f = function(a) {
+    var sum = 0;
+    for (var i = 0; i < a.length; i++) {
+        sum += a[i];
+    }   
+    return sum;
+};
+
+var run = function() {
+    var o1 = []; 
+    for (var i = 0; i < 100; i++) {
+        o1[i] = i;
+    }
+    
+    var o2 = {}; 
+    for (var i = 0; i < o1.length; i++) {
+        o2[i] = o1[i];
+    }
+    o2.length = o1.length;
+
+    var sum = 0;
+    for (var i = 0; i < 100000; i++) {
+        if (i % 2 === 0)
+            sum += f(o1);
+        else
+            sum += f(o2);
+    }
+    return sum;
+};
+
+var result = run();
+if (result !== 495000000)
+    throw "Bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return true;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return true;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return true;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.every(test1);
+    array.every(test2);
+    array.every(test3);
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return true;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return true;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return true;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.forEach(test1);
+    array.forEach(test2);
+    array.forEach(test3);
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return true;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return true;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return true;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.map(test1);
+    array.map(test2);
+    array.map(test3);
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return true;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return true;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return true;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.reduce(test1, {});
+    array.reduce(test2, {});
+    array.reduce(test3, {});
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return true;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return true;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return true;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.reduceRight(test1, {});
+    array.reduceRight(test2, {});
+    array.reduceRight(test3, {});
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`var result = 0;
+function test1(a) {
+    result << 1;
+    result++;
+    return false;
+}
+function test2(a,b) {
+    result ^= 3;
+    result *= 3;
+    return false;
+}
+function test3(a,b,c) {
+    result ^= result >> 1;
+    return false;
+}
+
+var result = 0;
+var array = []
+for (var i = 0; i < 100000; ++i)
+    array[i] = 1;
+
+for (var i = 0; i < 10; i++) {
+    array.some(test1);
+    array.some(test2);
+    array.some(test3);
+}
+
+if (result != 1428810496)
+    throw "Error: bad result: " + result;
+`,`function foo() {
+    var a = new Array(1000);
+    for (var i = 0; i < 1000; ++i) {
+        if (i % 7 === 0)
+            continue;
+        a[i] = i;
+    }
+
+    var niters = 10000;
+    var remove = true;
+    var lastRemovedItem = null;
+    var lastRemovedIndex = null;
+    for (var i = 0; i < niters; ++i) {
+        if (remove) {
+            lastRemovedIndex = Math.floor(Math.random() * a.length);
+            lastRemovedItem = a[lastRemovedIndex];
+            a.splice(lastRemovedIndex, 1);
+        } else {
+            a.splice(lastRemovedIndex, 0, lastRemovedItem);
+        }
+        remove = !remove;
+    }
+    if (a.length !== 1000)
+        throw new Error("Incorrect length");
+};
+foo();
+`,`function foo() {
+    var a = [];
+    var b = [];
+    
+    for (var i = 0; i < 1000; ++i) {
+        a.push(i + 0.5);
+        b.push(i - 0.5);
+    }
+    
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < a.length; ++j)
+            a[j] += b[j];
+    }
+
+    var result = 0;
+    for (var i = 0; i < a.length; ++i)
+        result += a[i];
+    
+    return result;
+}
+
+var result = foo();
+if (result != 499500000)
+    throw "Bad result: " + result;
+
+`,`function foo() {
+    var array = [];
+    
+    for (var i = 0; i < 1000; ++i)
+        array.push(i + 0.5);
+    
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < array.length; ++j)
+            array[j]++;
+    }
+
+    var result = 0;
+    for (var i = 0; i < array.length; ++i)
+        result += array[i];
+    
+    return result;
+}
+
+var result = foo();
+if (result != 1500000)
+    throw "Bad result: " + result;
+
+
+`,`function foo() {
+    var a = [];
+    var b = [];
+    var c = [];
+    
+    for (var i = 0; i < 1000; ++i) {
+        a.push(i + 0.5);
+        b.push(i - 0.5);
+        c.push((i % 2) ? 0.5 : -0.25);
+    }
+    
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < a.length; ++j)
+            a[j] += b[j] * c[j];
+    }
+
+    var result = 0;
+    for (var i = 0; i < a.length; ++i)
+        result += a[i];
+    
+    return result;
+}
+
+var result = foo();
+if (result != 63062500)
+    throw "Bad result: " + result;
+
+
+`,`function foo() {
+    var array = [];
+    
+    for (var i = 0; i < 1000; ++i)
+        array.push(i + 0.5);
+    
+    var result = 0;
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < array.length; ++j)
+            result += array[j];
+    }
+    
+    return result;
+}
+
+if (foo() != 500000000)
+    throw "ERROR";
+
+`,`function foo() {
+    var a = [];
+    var b = [];
+    
+    for (var i = 0; i < 1000; ++i) {
+        a.push(i + 1);
+        b.push(i - 1);
+    }
+    
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < a.length; ++j)
+            a[j] += b[j];
+        for (var j = 0; j < a.length; ++j)
+            a[j] -= b[j];
+    }
+
+    var result = 0;
+    for (var i = 0; i < a.length; ++i)
+        result += a[i];
+    
+    return result;
+}
+
+if (foo() != 500500)
+    throw "ERROR";
+
+
+`,`function foo() {
+    var array = [];
+    
+    for (var i = 0; i < 1000; ++i)
+        array.push(i + ((i % 2) ? 0.5 : 0));
+    
+    var result = 0;
+    for (var i = 0; i < 1000; ++i) {
+        for (var j = 0; j < array.length; ++j)
+            result += array[j];
+    }
+    
+    return result;
+}
+
+var result = foo();
+if (result != 499750000)
+    throw "Bad result: " + result;
+
+`,`//@ skip
+
+var array = new Array(10000);
+
+for (var i = 0; i < 100000; ++i)
+    array[i % array.length] = new DataView(new ArrayBuffer(1000));
+
+for (var i = 0; i < array.length; ++i) {
+    if (array[i].byteLength != 1000)
+        throw "Error: bad length: " + array[i].byteLength;
+    if (array[i].buffer.byteLength != 1000)
+        throw "Error: bad buffer.byteLength: " + array[i].buffer.byteLength;
+}
+`,`//@ skip
+
+var array = new Array(10000);
+
+for (var i = 0; i < 70000; ++i)
+    array[i % array.length] = new DataView(new ArrayBuffer(10));
+
+for (var i = 0; i < array.length; ++i) {
+    if (array[i].byteLength != 10)
+        throw "Error: bad length: " + array[i].byteLength;
+    if (array[i].buffer.byteLength != 10)
+        throw "Error: bad buffer.byteLength: " + array[i].buffer.byteLength;
+}
+`,`//@ skip
+
+var result = 0;
+var buffer = new ArrayBuffer(10);
+var array1 = new Int32Array(buffer, 4, 1);
+var array2 = new Uint32Array(10);
+
+for (var i = 0; i < 1000000; ++i) {
+    result += array1.byteOffset;
+    result += array2.byteOffset;
+}
+
+if (result != 4000000)
+    throw "Error: wrong result: " + result;
+`,`//@ skip
+
+var array = new Array(10000);
+
+for (var i = 0; i < 100000; ++i)
+    array[i % array.length] = new Int8Array(new ArrayBuffer(1000));
+
+for (var i = 0; i < array.length; ++i) {
+    if (array[i].length != 1000)
+        throw "Error: bad length: " + array[i].length;
+    if (array[i].buffer.byteLength != 1000)
+        throw "Error: bad buffer.byteLength: " + array[i].buffer.byteLength;
+}
+`,`//@ skip
+
+var array = new Array(10000);
+
+for (var i = 0; i < 100000; ++i)
+    array[i % array.length] = new Int8Array(new ArrayBuffer(10)).buffer;
+
+for (var i = 0; i < array.length; ++i) {
+    if (array[i].byteLength != 10)
+        throw "Error: bad byteLength: " + array[i].byteLength;
+}
+`,`//@ skip
+
+var array = new Array(10000);
+
+for (var i = 0; i < 70000; ++i)
+    array[i % array.length] = new Int8Array(new ArrayBuffer(10));
+
+for (var i = 0; i < array.length; ++i) {
+    if (array[i].length != 10)
+        throw "Error: bad length: " + array[i].length;
+    if (array[i].buffer.byteLength != 10)
+        throw "Error: bad buffer.byteLength: " + array[i].buffer.byteLength;
+}
+`,`//@ skip
+
+for (var i = 0; i < 70000; ++i)
+    new Int8Array(new ArrayBuffer(10));
+
+`,`var fn = function() {
+    return () => arguments[0];
+}(1);
+
+for (var i = 0; i < 100000; i++) {
+    if(fn(2) !== 1) throw 0; 
+}
+`,`var testValue  = 'test-value';
+
+class A {
+    constructor() {
+        this.value = testValue;
+    }
+}
+
+class B extends A {
+    constructor() {
+        super();
+        var arrow  = () => testValue;
+        arrow();
+    }
+}
+
+noInline(B);
+
+for (let i = 0; i < 1000000; ++i) {
+    let b = new B();
+    if (b.value != testValue)
+        throw "Error: bad result: " + result;
+}
+`,`var testValue  = 'test-value';
+
+class A {
+    constructor() {
+        this.value = testValue;
+    }
+
+    getValue () {
+        return this.value;
+    }
+}
+
+class B extends A {
+    getParentValue() {
+        var arrow  = () => testValue;
+        return arrow();
+    }
+}
+
+for (let i = 0; i < 100000; ++i) {
+    let b = new B();
+    if (b.getParentValue() != testValue)
+        throw "Error: bad result: " + result;
+}
+`,`function bar(a, b) {
+    return ((_a, _b) => _a + _b)(a, b);
+}
+
+noInline(bar);
+
+for (let i = 0; i < 1000000; ++i) {
+    let result = bar(1, 2);
+    if (result != 3)
+        throw "Error: bad result: " + result;
+}
+`,`var af = (a, b) => a + b;
+
+noInline(af);
+
+function bar(a, b) {
+    return af(a, b);
+}
+
+noInline(bar);
+
+for (let i = 0; i < 1000000; ++i) {
+    let result = bar(1, 2);
+    if (result != 3)
+        throw "Error: bad result: " + result;
+}
+`,`// The strlen function is derived from here:
+// http://kripken.github.io/mloc_emscripten_talk/#/20
+
+var MEM8  = new Uint8Array(1024);
+
+// Calculate length of C string:
+function strlen(ptr) {
+  ptr = ptr|0;
+  var curr = 0;
+  curr = ptr;
+  while (MEM8[curr]|0 != 0) {
+    curr = (curr + 1)|0;
+  }
+  return (curr - ptr)|0;
+}
+
+//----- Test driver ----
+
+for (i = 0; i < 1024; i++) {
+ MEM8[i] = i%198;
+}
+
+MEM8[7] = 0;
+
+var sum = 0
+for (i = 0; i < 1000000; i++) {
+  sum += strlen(5);
+}
+
+if (sum != 2000000)
+    throw "Bad result: " + result;
+`,`
+o = RegExp;
+j = 0;
+l = 2;
+z = 0;
+function test(o, z) {
+    var k = arguments[(((j << 1 | l) >> 1) ^ 1) & (z *= 1)];
+    k.input = 0;
+    for (var i = 0; i < 25000; i++) {
+        k.input = "foo";
+    }
+
+    return k.input;
+}
+var result = test({__proto__: {bar:"wibble", input:"foo"}});
+var result = test({input:"foo"});
+var result = test(o)
+for (var k = 0; k < 6; k++) {
+    var start = new Date;
+    var newResult = test(o)
+    var end = new Date;
+    if (newResult != result)
+        throw "Failed at " + k + "with " + newResult + " vs. " + result
+    result = newResult;
+    o = {__proto__ : o }
+}
+`,`// RegExp.input is a handy setter
+
+var o = RegExp;
+function test(o) {
+    var k = 0;
+    o.input = "bar";
+    for (var i = 0; i < 30000; i++)
+        o.input = "foo";
+
+    return o.input;
+}
+
+var result = test(o);
+
+for (var k = 0; k < 9; k++) {
+    var start = new Date;
+    var newResult = test(o)
+    var end = new Date;
+    if (newResult != result)
+        throw "Failed at " + k + "with " +newResult + " vs. " + result
+    result = newResult; 
+    o = {__proto__ : o }
+}
+
+`,`//@ runNoFTL
+
+var set = new Set;
+for (var i = 0; i < 8000; ++i) {
+    set.add(i);
+    set.add("" + i)
+    set.add({})
+    set.add(i + .5)
+}
+
+var result = 0;
+
+set.forEach(function(k){ result += set.size; })
+for (var i = 8000; i >= 0; --i) {
+    set.delete(i)
+    set.has("" + i)
+    set.add(i + .5)
+}
+set.forEach(function(k){ result += set.size; })
+
+if (result != 1600048001)
+    throw "Bad result: " + result;
+
+
+`,`// Test the performance of integer multiplication by implementing a 16-bit
+// string hash.
+
+function stringHash(string)
+{
+    // source: http://en.wikipedia.org/wiki/Java_hashCode()#Sample_implementations_of_the_java.lang.String_algorithm
+    var h = 0;
+    var len = string.length;
+    for (var index = 0; index < len; index++) {
+        h = (((31 * h) | 0) + string.charCodeAt(index)) | 0;
+    }
+    return h;
+}
+
+for (var i = 0; i < 10000; ++i) {
+    var result =
+        (stringHash("The spirit is willing but the flesh is weak.") *
+         stringHash("The vodka is strong but the meat is rotten.")) | 0;
+    if (result != -1136304128)
+        throw "Bad result: " + result;
+}
+
+`,`
+Function.prototype.a = Function.prototype.apply;
+
+function testFunction(a, b)
+{
+    "use strict"
+    return this * 10000 + a * 1000 + b * 100 + arguments[2] * 10 + arguments.length;
+}
+
+var arrayArguments = [1, [2, 3, 4]]
+
+for (var i = 0; i < 10000; i++) {
+    var result1 = testFunction.apply(...arrayArguments);
+    var result2 = testFunction.a(...arrayArguments);
+    if (result1 != result2) 
+        throw "Call with spread array failed at iteration " + i + ": " + result1 + " vs " + result2;
+}
+
+for (var i = 0; i < 10000; i++) {
+    var result1 = testFunction.apply(...[1, [2, 3, 4]]);
+    var result2 = testFunction.a(...[1, [2, 3, 4]]);
+    if (result1 != result2) 
+        throw "Call with spread array failed at iteration " + i + ": " + result1 + " vs " + result2;
+}
+
+function test2() {
+    for (var i = 0; i < 10000; i++) {
+        var result1 = testFunction.apply(...arguments);
+        var result2 = testFunction.a(...arguments);
+        if (result1 != result2)
+           throw "Call with spread arguments failed at iteration " + i + ": " + result1 + " vs " + result2;
+    }
+}
+
+test2(1,[2,3,4])
+
+
+function test3() {
+    aliasedArguments = arguments;
+    for (var i = 0; i < 10000; i++) {
+        var result1 = testFunction.apply(...aliasedArguments);
+        var result2 = testFunction.a(...aliasedArguments);
+        if (result1 != result2)
+           throw "Call with spread arguments failed at iteration " + i + ": " + result1 + " vs " + result2;
+    }
+}
+
+test3(1,[2,3,4])`]
+
+let processTexts = (texts) => {
+    let wc = 0;
+    for (let text of texts) {
+        try {
+            let globalIndex = 0;
+            while (1) {
+                let index = globalIndex;
+                let word;
+                while (true) {
+                    let c = text[index];
+                    if (c.match(/\s/)) {
+                        word = text.substring(globalIndex, index);
+                        while (c.match(/\s/)) {
+                            ++index;
+                            if (index >= text.length) {
+                                globalIndex = index;
+                                break;
+                            }
+                            c = text[index];
+                        }
+
+                        globalIndex = index;
+                        break;
+                    }
+
+                    ++index;
+                    if (index >= text.length) {
+                        globalIndex = index;
+                        break;
+                    }
+                }
+
+                if (globalIndex < text.length)
+                    wc++;
+                else 
+                    throw new EOF;
+            }
+        } catch(e) {
+            assert(e instanceof EOF);
+        }
+    }
+    return wc;
+};
+
+for (let i = 0; i < 20; ++i)
+    processTexts(texts);
diff --git a/JSTests/stress/catch-set-argument-speculation-failure.js b/JSTests/stress/catch-set-argument-speculation-failure.js
new file mode 100644 (file)
index 0000000..12f939d
--- /dev/null
@@ -0,0 +1,53 @@
+"use strict";
+
+let flag = true;
+function o() {
+    if (flag)
+        return {x:20};
+    return {y:20, x:20};
+}
+noInline(o);
+
+let counter = 0;
+function e() {
+    if ((++counter) % 50 === 0)
+        throw new Error;
+}
+noInline(e);
+
+let counter2 = 0;
+function e2() {
+    if ((++counter2) % 2 === 0)
+        throw new Error;
+}
+noInline(e2);
+
+function escape(){ }
+noInline(escape);
+
+function baz(o) {
+    try {
+        e();
+        escape(o.x);
+    } catch(e) {
+        escape(o.x);
+        e2();
+    } finally {
+        o.x;
+    }
+}
+noInline(baz);
+
+{
+    let o = {x:20};
+    function run() {
+        for (let i = 0; i < 1000; ++i) {
+            try {
+                baz(o);
+            } catch { }
+        }
+    }
+    run();
+    o = {y:40, x:20};
+    run();
+}
diff --git a/JSTests/stress/osr-enter-to-catch-with-set-local-type-check-failure.js b/JSTests/stress/osr-enter-to-catch-with-set-local-type-check-failure.js
new file mode 100644 (file)
index 0000000..e357a2d
--- /dev/null
@@ -0,0 +1,38 @@
+let flag = true;
+function foo() {
+    if (flag)
+        return 20;
+    return {};
+}
+noInline(foo);
+
+let state = 0;
+function e() {
+    if ((++state) % 25 === 0)
+        throw new Error();
+}
+noInline(e);
+
+function baz() { }
+noInline(baz);
+
+function bar() {
+    let x = foo();
+    try {
+        e();
+        baz(++x);
+    } catch(e) {
+        baz(++x);
+    } finally {
+        baz(x);
+    }
+}
+noInline(bar);
+
+for (let i = 0; i < 2000; ++i) {
+    bar();
+}
+
+flag = false;
+for (let i = 0; i < 1000; ++i)
+    bar();
index 5d06295..6d08591 100644 (file)
@@ -391,7 +391,6 @@ set(JavaScriptCore_SOURCES
     dfg/DFGPhase.cpp
     dfg/DFGPhiChildren.cpp
     dfg/DFGPlan.cpp
-    dfg/DFGPrePostNumbering.cpp
     dfg/DFGPredictionInjectionPhase.cpp
     dfg/DFGPredictionPropagationPhase.cpp
     dfg/DFGPromotedHeapLocation.cpp
index 784b0a6..fe801bb 100644 (file)
@@ -1,3 +1,270 @@
+2017-08-25  Saam Barati  <sbarati@apple.com>
+
+        Support compiling catch in the DFG
+        https://bugs.webkit.org/show_bug.cgi?id=174590
+        <rdar://problem/34047845>
+
+        Reviewed by Filip Pizlo.
+
+        This patch implements OSR entry into op_catch in the DFG. We will support OSR entry
+        into the FTL in a followup: https://bugs.webkit.org/show_bug.cgi?id=175396
+        
+        To implement catch in the DFG, this patch introduces the concept of multiple
+        entrypoints into CPS/LoadStore DFG IR. A lot of this patch is stringing this concept
+        through the DFG. Many phases used to assume that Graph::block(0) is the only root, and this
+        patch contains many straight forward changes generalizing the code to handle more than
+        one entrypoint.
+        
+        A main building block of this is moving to two CFG types: SSACFG and CPSCFG. SSACFG
+        is the same CFG we used to have. CPSCFG is a new type that introduces a fake root
+        that has an outgoing edge to all the entrypoints. This allows our existing graph algorithms
+        to Just Work over CPSCFG. For example, there is now the concept of SSADominators vs CPSDominators,
+        and SSANaturalLoops vs CPSNaturalLoops.
+        
+        The way we compile the catch entrypoint is by bootstrapping the state
+        of the program by loading all live bytecode locals from a buffer. The OSR
+        entry code will store all live values into that buffer before jumping to
+        the entrypoint. The OSR entry code is also responsible for performing type
+        proofs of the arguments before doing an OSR entry. If there is a type
+        mismatch, it's not legal to OSR enter into the DFG compilation. Currently,
+        each catch entrypoint knows the argument type proofs it must perform to enter
+        into the DFG. Currently, all entrypoints' arguments flush format are unified
+        via ArgumentPosition, but this is just an implementation detail. The code is
+        written more generally to assume that each entrypoint may perform its own distinct
+        proof.
+        
+        op_catch now performs value profiling for all live bytecode locals in the
+        LLInt and baseline JIT. This information is then fed into the DFG via the
+        ExtractCatchLocal node in the prediction propagation phase.
+        
+        This patch also changes how we generate op_catch in bytecode. All op_catches
+        are now split out at the end of the program in bytecode. This ensures that
+        no op_catch is inside a try block. This is needed to ensure correctness in
+        the DFGLiveCatchVariablePreservationPhase. That phase only inserts flushes
+        before SetLocals inside a try block. If an op_catch were in a try block, this
+        would cause the phase to insert a Flush before one of the state bootstrapping
+        SetLocals, which would generate invalid IR. Moving op_catch to be generated on
+        its own at the end of a bytecode stream seemed like the most elegant solution since
+        it better represents that we treat op_catch as an entrypoint. This is true
+        both in the DFG and in the baseline and LLInt: we don't reach an op_catch
+        via normal control flow. Because op_catch cannot throw, this will not break
+        any previous semantics of op_catch. Logically, it'd be valid to split try
+        blocks around any non-throwing bytecode operation.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * bytecode/BytecodeDumper.cpp:
+        (JSC::BytecodeDumper<Block>::dumpBytecode):
+        * bytecode/BytecodeList.json:
+        * bytecode/BytecodeUseDef.h:
+        (JSC::computeUsesForBytecodeOffset):
+        * bytecode/CodeBlock.cpp:
+        (JSC::CodeBlock::finishCreation):
+        (JSC::CodeBlock::ensureCatchLivenessIsComputedForBytecodeOffset):
+        (JSC::CodeBlock::updateAllPredictionsAndCountLiveness):
+        (JSC::CodeBlock::validate):
+        * bytecode/CodeBlock.h:
+        * bytecode/ValueProfile.h:
+        (JSC::ValueProfile::ValueProfile):
+        (JSC::ValueProfileAndOperandBuffer::ValueProfileAndOperandBuffer):
+        (JSC::ValueProfileAndOperandBuffer::~ValueProfileAndOperandBuffer):
+        (JSC::ValueProfileAndOperandBuffer::forEach):
+        * bytecompiler/BytecodeGenerator.cpp:
+        (JSC::BytecodeGenerator::generate):
+        (JSC::BytecodeGenerator::BytecodeGenerator):
+        (JSC::BytecodeGenerator::emitCatch):
+        (JSC::BytecodeGenerator::emitEnumeration):
+        * bytecompiler/BytecodeGenerator.h:
+        * bytecompiler/NodesCodegen.cpp:
+        (JSC::TryNode::emitBytecode):
+        * dfg/DFGAbstractInterpreterInlines.h:
+        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
+        * dfg/DFGBackwardsCFG.h:
+        (JSC::DFG::BackwardsCFG::BackwardsCFG):
+        * dfg/DFGBasicBlock.cpp:
+        (JSC::DFG::BasicBlock::BasicBlock):
+        * dfg/DFGBasicBlock.h:
+        (JSC::DFG::BasicBlock::findTerminal const):
+        * dfg/DFGByteCodeParser.cpp:
+        (JSC::DFG::ByteCodeParser::setDirect):
+        (JSC::DFG::ByteCodeParser::flush):
+        (JSC::DFG::ByteCodeParser::DelayedSetLocal::DelayedSetLocal):
+        (JSC::DFG::ByteCodeParser::DelayedSetLocal::execute):
+        (JSC::DFG::ByteCodeParser::parseBlock):
+        (JSC::DFG::ByteCodeParser::parseCodeBlock):
+        (JSC::DFG::ByteCodeParser::parse):
+        * dfg/DFGCFG.h:
+        (JSC::DFG::CFG::root):
+        (JSC::DFG::CFG::roots):
+        (JSC::DFG::CPSCFG::CPSCFG):
+        (JSC::DFG::selectCFG):
+        * dfg/DFGCPSRethreadingPhase.cpp:
+        (JSC::DFG::CPSRethreadingPhase::specialCaseArguments):
+        * dfg/DFGCSEPhase.cpp:
+        * dfg/DFGClobberize.h:
+        (JSC::DFG::clobberize):
+        * dfg/DFGControlEquivalenceAnalysis.h:
+        (JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
+        * dfg/DFGDCEPhase.cpp:
+        (JSC::DFG::DCEPhase::run):
+        * dfg/DFGDisassembler.cpp:
+        (JSC::DFG::Disassembler::createDumpList):
+        * dfg/DFGDoesGC.cpp:
+        (JSC::DFG::doesGC):
+        * dfg/DFGDominators.h:
+        (JSC::DFG::Dominators::Dominators):
+        (JSC::DFG::ensureDominatorsForCFG):
+        * dfg/DFGEdgeDominates.h:
+        (JSC::DFG::EdgeDominates::EdgeDominates):
+        (JSC::DFG::EdgeDominates::operator()):
+        * dfg/DFGFixupPhase.cpp:
+        (JSC::DFG::FixupPhase::fixupNode):
+        (JSC::DFG::FixupPhase::fixupChecksInBlock):
+        * dfg/DFGFlushFormat.h:
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::Graph):
+        (JSC::DFG::unboxLoopNode):
+        (JSC::DFG::Graph::dumpBlockHeader):
+        (JSC::DFG::Graph::dump):
+        (JSC::DFG::Graph::determineReachability):
+        (JSC::DFG::Graph::invalidateCFG):
+        (JSC::DFG::Graph::blocksInPreOrder):
+        (JSC::DFG::Graph::blocksInPostOrder):
+        (JSC::DFG::Graph::ensureCPSDominators):
+        (JSC::DFG::Graph::ensureSSADominators):
+        (JSC::DFG::Graph::ensureCPSNaturalLoops):
+        (JSC::DFG::Graph::ensureSSANaturalLoops):
+        (JSC::DFG::Graph::ensureBackwardsCFG):
+        (JSC::DFG::Graph::ensureBackwardsDominators):
+        (JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
+        (JSC::DFG::Graph::methodOfGettingAValueProfileFor):
+        (JSC::DFG::Graph::clearCPSCFGData):
+        (JSC::DFG::Graph::ensureDominators): Deleted.
+        (JSC::DFG::Graph::ensurePrePostNumbering): Deleted.
+        (JSC::DFG::Graph::ensureNaturalLoops): Deleted.
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::willCatchExceptionInMachineFrame):
+        (JSC::DFG::Graph::isEntrypoint const):
+        * dfg/DFGInPlaceAbstractState.cpp:
+        (JSC::DFG::InPlaceAbstractState::initialize):
+        (JSC::DFG::InPlaceAbstractState::mergeToSuccessors):
+        * dfg/DFGJITCode.cpp:
+        (JSC::DFG::JITCode::shrinkToFit):
+        * dfg/DFGJITCode.h:
+        (JSC::DFG::JITCode::catchOSREntryDataForBytecodeIndex):
+        (JSC::DFG::JITCode::finalizeCatchOSREntrypoints):
+        (JSC::DFG::JITCode::appendCatchEntrypoint):
+        * dfg/DFGJITCompiler.cpp:
+        (JSC::DFG::JITCompiler::compile):
+        (JSC::DFG::JITCompiler::compileFunction):
+        (JSC::DFG::JITCompiler::noticeCatchEntrypoint):
+        (JSC::DFG::JITCompiler::noticeOSREntry):
+        (JSC::DFG::JITCompiler::makeCatchOSREntryBuffer):
+        * dfg/DFGJITCompiler.h:
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::run):
+        (JSC::DFG::LICMPhase::attemptHoist):
+        * dfg/DFGLiveCatchVariablePreservationPhase.cpp:
+        (JSC::DFG::LiveCatchVariablePreservationPhase::run):
+        (JSC::DFG::LiveCatchVariablePreservationPhase::isValidFlushLocation):
+        (JSC::DFG::LiveCatchVariablePreservationPhase::handleBlockForTryCatch):
+        (JSC::DFG::LiveCatchVariablePreservationPhase::newVariableAccessData):
+        (JSC::DFG::LiveCatchVariablePreservationPhase::willCatchException): Deleted.
+        (JSC::DFG::LiveCatchVariablePreservationPhase::handleBlock): Deleted.
+        * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+        (JSC::DFG::createPreHeader):
+        (JSC::DFG::LoopPreHeaderCreationPhase::run):
+        * dfg/DFGMaximalFlushInsertionPhase.cpp:
+        (JSC::DFG::MaximalFlushInsertionPhase::run):
+        (JSC::DFG::MaximalFlushInsertionPhase::treatRegularBlock):
+        (JSC::DFG::MaximalFlushInsertionPhase::treatRootBlock):
+        * dfg/DFGMayExit.cpp:
+        * dfg/DFGNaturalLoops.h:
+        (JSC::DFG::NaturalLoops::NaturalLoops):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::isSwitch const):
+        (JSC::DFG::Node::successor):
+        (JSC::DFG::Node::catchOSREntryIndex const):
+        (JSC::DFG::Node::catchLocalPrediction):
+        (JSC::DFG::Node::isSwitch): Deleted.
+        * dfg/DFGNodeType.h:
+        * dfg/DFGOSREntry.cpp:
+        (JSC::DFG::prepareCatchOSREntry):
+        * dfg/DFGOSREntry.h:
+        * dfg/DFGOSREntrypointCreationPhase.cpp:
+        (JSC::DFG::OSREntrypointCreationPhase::run):
+        * dfg/DFGOSRExitCompilerCommon.cpp:
+        (JSC::DFG::handleExitCounts):
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::compileInThreadImpl):
+        * dfg/DFGPrePostNumbering.cpp:
+        (JSC::DFG::PrePostNumbering::PrePostNumbering): Deleted.
+        (JSC::DFG::PrePostNumbering::~PrePostNumbering): Deleted.
+        (WTF::printInternal): Deleted.
+        * dfg/DFGPrePostNumbering.h:
+        (): Deleted.
+        (JSC::DFG::PrePostNumbering::preNumber const): Deleted.
+        (JSC::DFG::PrePostNumbering::postNumber const): Deleted.
+        (JSC::DFG::PrePostNumbering::isStrictAncestorOf const): Deleted.
+        (JSC::DFG::PrePostNumbering::isAncestorOf const): Deleted.
+        (JSC::DFG::PrePostNumbering::isStrictDescendantOf const): Deleted.
+        (JSC::DFG::PrePostNumbering::isDescendantOf const): Deleted.
+        (JSC::DFG::PrePostNumbering::edgeKind const): Deleted.
+        * dfg/DFGPredictionInjectionPhase.cpp:
+        (JSC::DFG::PredictionInjectionPhase::run):
+        * dfg/DFGPredictionPropagationPhase.cpp:
+        * dfg/DFGPutStackSinkingPhase.cpp:
+        * dfg/DFGSSACalculator.cpp:
+        (JSC::DFG::SSACalculator::nonLocalReachingDef):
+        (JSC::DFG::SSACalculator::reachingDefAtTail):
+        * dfg/DFGSSACalculator.h:
+        (JSC::DFG::SSACalculator::computePhis):
+        * dfg/DFGSSAConversionPhase.cpp:
+        (JSC::DFG::SSAConversionPhase::run):
+        (JSC::DFG::performSSAConversion):
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * dfg/DFGSpeculativeJIT.cpp:
+        (JSC::DFG::SpeculativeJIT::compileCurrentBlock):
+        (JSC::DFG::SpeculativeJIT::checkArgumentTypes):
+        (JSC::DFG::SpeculativeJIT::createOSREntries):
+        (JSC::DFG::SpeculativeJIT::linkOSREntries):
+        * dfg/DFGSpeculativeJIT32_64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGSpeculativeJIT64.cpp:
+        (JSC::DFG::SpeculativeJIT::compile):
+        * dfg/DFGStaticExecutionCountEstimationPhase.cpp:
+        (JSC::DFG::StaticExecutionCountEstimationPhase::run):
+        * dfg/DFGStrengthReductionPhase.cpp:
+        (JSC::DFG::StrengthReductionPhase::handleNode):
+        * dfg/DFGTierUpCheckInjectionPhase.cpp:
+        (JSC::DFG::TierUpCheckInjectionPhase::run):
+        (JSC::DFG::TierUpCheckInjectionPhase::buildNaturalLoopToLoopHintMap):
+        * dfg/DFGTypeCheckHoistingPhase.cpp:
+        (JSC::DFG::TypeCheckHoistingPhase::run):
+        * dfg/DFGValidate.cpp:
+        * ftl/FTLLink.cpp:
+        (JSC::FTL::link):
+        * ftl/FTLLowerDFGToB3.cpp:
+        (JSC::FTL::DFG::LowerDFGToB3::lower):
+        (JSC::FTL::DFG::LowerDFGToB3::safelyInvalidateAfterTermination):
+        (JSC::FTL::DFG::LowerDFGToB3::isValid):
+        * jit/JIT.h:
+        * jit/JITInlines.h:
+        (JSC::JIT::callOperation):
+        * jit/JITOpcodes.cpp:
+        (JSC::JIT::emit_op_catch):
+        * jit/JITOpcodes32_64.cpp:
+        (JSC::JIT::emit_op_catch):
+        * jit/JITOperations.cpp:
+        * jit/JITOperations.h:
+        * llint/LLIntSlowPaths.cpp:
+        (JSC::LLInt::LLINT_SLOW_PATH_DECL):
+        * llint/LLIntSlowPaths.h:
+        * llint/LowLevelInterpreter32_64.asm:
+        * llint/LowLevelInterpreter64.asm:
+
 2017-08-25  Keith Miller  <keith_miller@apple.com>
 
         Explore increasing max JSString::m_length to UINT_MAX.
index c7aa973..0a16ad5 100644 (file)
                0F3BD1B71B896A0700598AA6 /* DFGInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */; };
                0F3C1F1A1B868E7900ABB08B /* DFGClobbersExitState.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3C1F181B868E7900ABB08B /* DFGClobbersExitState.cpp */; };
                0F3C1F1B1B868E7900ABB08B /* DFGClobbersExitState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3C1F191B868E7900ABB08B /* DFGClobbersExitState.h */; };
-               0F3E01AA19D353A500F61B7F /* DFGPrePostNumbering.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F3E01A819D353A500F61B7F /* DFGPrePostNumbering.cpp */; };
-               0F3E01AB19D353A500F61B7F /* DFGPrePostNumbering.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3E01A919D353A500F61B7F /* DFGPrePostNumbering.h */; };
                0F40E4A71C497F7400A577FA /* AirOpcode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6183321C45F35C0072450B /* AirOpcode.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F40E4A81C497F7400A577FA /* AirOpcodeGenerated.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6183341C45F3B60072450B /* AirOpcodeGenerated.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F40E4A91C497F7400A577FA /* AirOpcodeUtils.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F6183351C45F3B60072450B /* AirOpcodeUtils.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F3BD1B61B896A0700598AA6 /* DFGInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGInsertionSet.cpp; path = dfg/DFGInsertionSet.cpp; sourceTree = "<group>"; };
                0F3C1F181B868E7900ABB08B /* DFGClobbersExitState.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGClobbersExitState.cpp; path = dfg/DFGClobbersExitState.cpp; sourceTree = "<group>"; };
                0F3C1F191B868E7900ABB08B /* DFGClobbersExitState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGClobbersExitState.h; path = dfg/DFGClobbersExitState.h; sourceTree = "<group>"; };
-               0F3E01A819D353A500F61B7F /* DFGPrePostNumbering.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPrePostNumbering.cpp; path = dfg/DFGPrePostNumbering.cpp; sourceTree = "<group>"; };
-               0F3E01A919D353A500F61B7F /* DFGPrePostNumbering.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPrePostNumbering.h; path = dfg/DFGPrePostNumbering.h; sourceTree = "<group>"; };
                0F426A451460CBAB00131F8F /* ValueRecovery.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ValueRecovery.h; sourceTree = "<group>"; };
                0F426A461460CBAB00131F8F /* VirtualRegister.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = VirtualRegister.h; sourceTree = "<group>"; };
                0F426A4A1460CD6B00131F8F /* DataFormat.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DataFormat.h; sourceTree = "<group>"; };
                                0FBE0F6E16C1DB010082C5E8 /* DFGPredictionInjectionPhase.h */,
                                0FFFC95114EF909500C72532 /* DFGPredictionPropagationPhase.cpp */,
                                0FFFC95214EF909500C72532 /* DFGPredictionPropagationPhase.h */,
-                               0F3E01A819D353A500F61B7F /* DFGPrePostNumbering.cpp */,
-                               0F3E01A919D353A500F61B7F /* DFGPrePostNumbering.h */,
                                0F2B9CE019D0BA7D00B1D1B5 /* DFGPromotedHeapLocation.cpp */,
                                0F2B9CE119D0BA7D00B1D1B5 /* DFGPromotedHeapLocation.h */,
                                0FFC92151B94FB3E0071DD66 /* DFGPropertyTypeKey.h */,
                                DC00039319D8BE6F00023EB0 /* DFGPreciseLocalClobberize.h in Headers */,
                                0FBE0F7516C1DB0B0082C5E8 /* DFGPredictionInjectionPhase.h in Headers */,
                                0FFFC95E14EF90B700C72532 /* DFGPredictionPropagationPhase.h in Headers */,
-                               0F3E01AB19D353A500F61B7F /* DFGPrePostNumbering.h in Headers */,
                                0F2B9CED19D0BA7D00B1D1B5 /* DFGPromotedHeapLocation.h in Headers */,
                                0FFC92161B94FB3E0071DD66 /* DFGPropertyTypeKey.h in Headers */,
                                0FB17663196B8F9E0091052A /* DFGPureValue.h in Headers */,
                                A78A977A179738B8009DF744 /* DFGPlan.cpp in Sources */,
                                0FBE0F7416C1DB090082C5E8 /* DFGPredictionInjectionPhase.cpp in Sources */,
                                0FFFC95D14EF90B300C72532 /* DFGPredictionPropagationPhase.cpp in Sources */,
-                               0F3E01AA19D353A500F61B7F /* DFGPrePostNumbering.cpp in Sources */,
                                0F2B9CEC19D0BA7D00B1D1B5 /* DFGPromotedHeapLocation.cpp in Sources */,
                                0FB17662196B8F9E0091052A /* DFGPureValue.cpp in Sources */,
                                0F3A1BF91A9ECB7D000DE01A /* DFGPutStackSinkingPhase.cpp in Sources */,
index 7407916..5ab7b81 100644 (file)
@@ -1556,8 +1556,9 @@ void BytecodeDumper<Block>::dumpBytecode(PrintStream& out, const typename Block:
     case op_catch: {
         int r0 = (++it)->u.operand;
         int r1 = (++it)->u.operand;
+        void* pointer = getPointer(*(++it));
         printLocationAndOp(out, location, it, "catch");
-        out.printf("%s, %s", registerName(r0).data(), registerName(r1).data());
+        out.printf("%s, %s, %p", registerName(r0).data(), registerName(r1).data(), pointer);
         break;
     }
     case op_throw: {
index 4e19f30..91270d6 100644 (file)
             { "name" : "op_push_with_scope", "length" : 4 },
             { "name" : "op_create_lexical_environment", "length" : 5 },
             { "name" : "op_get_parent_scope", "length" : 3 },
-            { "name" : "op_catch", "length" : 3 },
+            { "name" : "op_catch", "length" : 4 },
             { "name" : "op_throw", "length" : 2 },
             { "name" : "op_throw_static_error", "length" : 3 },
             { "name" : "op_debug", "length" : 3 },
index fdaa73f..603af3c 100644 (file)
@@ -32,7 +32,7 @@ namespace JSC {
 template<typename Block, typename Functor, typename Instruction>
 void computeUsesForBytecodeOffset(Block* codeBlock, OpcodeID opcodeID, Instruction* instruction, const Functor& functor)
 {
-    if (opcodeID != op_enter && codeBlock->wasCompiledWithDebuggingOpcodes() && codeBlock->scopeRegister().isValid())
+    if (opcodeID != op_enter && (codeBlock->wasCompiledWithDebuggingOpcodes() || codeBlock->usesEval()) && codeBlock->scopeRegister().isValid())
         functor(codeBlock, instruction, opcodeID, codeBlock->scopeRegister().offset());
 
     switch (opcodeID) {
index e9be6c2..d6844b0 100644 (file)
@@ -805,10 +805,11 @@ bool CodeBlock::finishCreation(VM& vm, ScriptExecutable* ownerExecutable, Unlink
             m_numberOfArgumentsToSkip = numberOfArgumentsToSkip;
             break;
         }
-
+        
         default:
             break;
         }
+
         i += opLength;
     }
 
@@ -830,10 +831,10 @@ bool CodeBlock::finishCreation(VM& vm, ScriptExecutable* ownerExecutable, Unlink
 
     if (Options::dumpGeneratedBytecodes())
         dumpBytecode();
-    
+
     heap()->m_codeBlocks->add(this);
     heap()->reportExtraMemoryAllocated(m_instructions.size() * sizeof(Instruction));
-    
+
     return true;
 }
 
@@ -1703,6 +1704,37 @@ CallSiteIndex CodeBlock::newExceptionHandlingCallSiteIndex(CallSiteIndex origina
 #endif
 }
 
+void CodeBlock::ensureCatchLivenessIsComputedForBytecodeOffsetSlow(unsigned bytecodeOffset)
+{
+    ASSERT(Interpreter::getOpcodeID(m_instructions[bytecodeOffset]) == op_catch);
+    BytecodeLivenessAnalysis& bytecodeLiveness = livenessAnalysis();
+
+    // We get the live-out set of variables at op_catch, not the live-in. This
+    // is because the variables that the op_catch defines might be dead, and
+    // we can avoid profiling them and extracting them when doing OSR entry
+    // into the DFG.
+    FastBitVector liveLocals = bytecodeLiveness.getLivenessInfoAtBytecodeOffset(bytecodeOffset + OPCODE_LENGTH(op_catch));
+    Vector<VirtualRegister> liveOperands;
+    liveOperands.reserveInitialCapacity(liveLocals.bitCount());
+    liveLocals.forEachSetBit([&] (unsigned liveLocal) {
+        liveOperands.append(virtualRegisterForLocal(liveLocal));
+    });
+
+    for (int i = 0; i < numParameters(); ++i)
+        liveOperands.append(virtualRegisterForArgument(i));
+
+    auto profiles = std::make_unique<ValueProfileAndOperandBuffer>(liveOperands.size());
+    RELEASE_ASSERT(profiles->m_size == liveOperands.size());
+    for (unsigned i = 0; i < profiles->m_size; ++i)
+        profiles->m_buffer.get()[i].m_operand = liveOperands[i].offset();
+    m_instructions[bytecodeOffset + 3].u.pointer = profiles.get();
+
+    {
+        ConcurrentJSLocker locker(m_lock);
+        m_catchProfiles.append(WTFMove(profiles));
+    }
+}
+
 void CodeBlock::removeExceptionHandlerForCallSite(CallSiteIndex callSiteIndex)
 {
     RELEASE_ASSERT(m_rareData);
@@ -2486,9 +2518,10 @@ const Identifier& CodeBlock::identifier(int index) const
 void CodeBlock::updateAllPredictionsAndCountLiveness(unsigned& numberOfLiveNonArgumentValueProfiles, unsigned& numberOfSamplesInProfiles)
 {
     ConcurrentJSLocker locker(m_lock);
-    
+
     numberOfLiveNonArgumentValueProfiles = 0;
     numberOfSamplesInProfiles = 0; // If this divided by ValueProfile::numberOfBuckets equals numberOfValueProfiles() then value profiles are full.
+
     for (unsigned i = 0; i < totalNumberOfValueProfiles(); ++i) {
         ValueProfile& profile = getFromAllValueProfiles(i);
         unsigned numSamples = profile.totalNumberOfSamples();
@@ -2503,6 +2536,12 @@ void CodeBlock::updateAllPredictionsAndCountLiveness(unsigned& numberOfLiveNonAr
             numberOfLiveNonArgumentValueProfiles++;
         profile.computeUpdatedPrediction(locker);
     }
+
+    for (auto& profileBucket : m_catchProfiles) {
+        profileBucket->forEach([&] (ValueProfileAndOperand& profile) {
+            profile.m_profile.computeUpdatedPrediction(locker);
+        });
+    }
     
 #if ENABLE(DFG_JIT)
     m_lazyOperandValueProfiles.computeUpdatedPredictions(locker);
@@ -2786,6 +2825,23 @@ void CodeBlock::validate()
             endValidationDidFail();
         }
     }
+     
+    for (unsigned bytecodeOffset = 0; bytecodeOffset < m_instructions.size(); ) {
+        OpcodeID opcode = Interpreter::getOpcodeID(m_instructions[bytecodeOffset]);
+        if (!!baselineAlternative()->handlerForBytecodeOffset(bytecodeOffset)) {
+            if (opcode == op_catch || opcode == op_enter) {
+                // op_catch/op_enter logically represent an entrypoint. Entrypoints are not allowed to be
+                // inside of a try block because they are responsible for bootstrapping state. And they
+                // are never allowed throw an exception because of this. We rely on this when compiling
+                // in the DFG. Because an entrypoint never throws, the bytecode generator will never
+                // allow once inside a try block.
+                beginValidationDidFail();
+                dataLog("    entrypoint not allowed inside a try block.");
+                endValidationDidFail();
+            }
+        }
+        bytecodeOffset += opcodeLength(opcode);
+    }
 }
 
 void CodeBlock::beginValidationDidFail()
index 729f6cf..aef138c 100644 (file)
@@ -891,6 +891,26 @@ public:
 
     CallSiteIndex newExceptionHandlingCallSiteIndex(CallSiteIndex originalCallSite);
 
+    void ensureCatchLivenessIsComputedForBytecodeOffset(unsigned bytecodeOffset)
+    {
+        if (!!m_instructions[bytecodeOffset + 3].u.pointer) {
+#if !ASSERT_DISABLED
+            ConcurrentJSLocker locker(m_lock);
+            bool found = false;
+            for (auto& profile : m_catchProfiles) {
+                if (profile.get() == m_instructions[bytecodeOffset + 3].u.pointer) {
+                    found = true;
+                    break;
+                }
+            }
+            ASSERT(found);
+#endif
+            return;
+        }
+
+        ensureCatchLivenessIsComputedForBytecodeOffsetSlow(bytecodeOffset);
+    }
+
 #if ENABLE(JIT)
     void setPCToCodeOriginMap(std::unique_ptr<PCToCodeOriginMap>&&);
     std::optional<CodeOrigin> findPC(void* pc);
@@ -953,6 +973,7 @@ private:
     }
 
     void insertBasicBlockBoundariesForControlFlowProfiler(RefCountedArray<Instruction>&);
+    void ensureCatchLivenessIsComputedForBytecodeOffsetSlow(unsigned);
 
     WriteBarrier<UnlinkedCodeBlock> m_unlinkedCode;
     int m_numParameters;
@@ -1003,6 +1024,7 @@ private:
 #endif
     RefCountedArray<ValueProfile> m_argumentValueProfiles;
     RefCountedArray<ValueProfile> m_valueProfiles;
+    Vector<std::unique_ptr<ValueProfileAndOperandBuffer>> m_catchProfiles;
     SegmentedVector<RareCaseProfile, 8> m_rareCaseProfiles;
     RefCountedArray<ArrayAllocationProfile> m_arrayAllocationProfiles;
     ArrayProfileVector m_arrayProfiles;
index ba4ffb7..c814300 100644 (file)
@@ -174,8 +174,8 @@ struct ValueProfileWithLogNumberOfBuckets : public ValueProfileBase<1 << logNumb
 };
 
 struct ValueProfile : public ValueProfileWithLogNumberOfBuckets<0> {
-    ValueProfile(): ValueProfileWithLogNumberOfBuckets<0>() { }
-    ValueProfile(int bytecodeOffset): ValueProfileWithLogNumberOfBuckets<0>(bytecodeOffset) { }
+    ValueProfile() : ValueProfileWithLogNumberOfBuckets<0>() { }
+    ValueProfile(int bytecodeOffset) : ValueProfileWithLogNumberOfBuckets<0>(bytecodeOffset) { }
 };
 
 template<typename T>
@@ -202,4 +202,38 @@ inline int getRareCaseProfileBytecodeOffset(RareCaseProfile* rareCaseProfile)
     return rareCaseProfile->m_bytecodeOffset;
 }
 
+struct ValueProfileAndOperand {
+    ValueProfile m_profile;
+    int m_operand;
+};
+
+struct ValueProfileAndOperandBuffer {
+    ValueProfileAndOperandBuffer(unsigned size)
+        : m_size(size)
+    {
+        // FIXME: ValueProfile has more stuff than we need. We could optimize these value profiles
+        // to be more space efficient.
+        // https://bugs.webkit.org/show_bug.cgi?id=175413
+        m_buffer = MallocPtr<ValueProfileAndOperand>::malloc(m_size * sizeof(ValueProfileAndOperand));
+        for (unsigned i = 0; i < m_size; ++i)
+            new (&m_buffer.get()[i]) ValueProfileAndOperand();
+    }
+
+    ~ValueProfileAndOperandBuffer()
+    {
+        for (unsigned i = 0; i < m_size; ++i)
+            m_buffer.get()[i].~ValueProfileAndOperand();
+    }
+
+    template <typename Function>
+    void forEach(Function function)
+    {
+        for (unsigned i = 0; i < m_size; ++i)
+            function(m_buffer.get()[i]);
+    }
+
+    unsigned m_size;
+    MallocPtr<ValueProfileAndOperand> m_buffer;
+};
+
 } // namespace JSC
index 62b5615..da5493e 100644 (file)
@@ -154,6 +154,18 @@ ParserError BytecodeGenerator::generate()
         emitUnreachable();
     }
 
+    for (auto& tuple : m_catchesToEmit) {
+        Ref<Label> realCatchTarget = newEmittedLabel();
+        emitOpcode(op_catch);
+        instructions().append(std::get<1>(tuple));
+        instructions().append(std::get<2>(tuple));
+        instructions().append(0);
+
+        TryData* tryData = std::get<0>(tuple);
+        emitJump(tryData->target.get());
+        tryData->target = WTFMove(realCatchTarget);
+    }
+
     m_staticPropertyAnalyzer.kill();
 
     for (auto& range : m_tryRanges) {
@@ -714,7 +726,7 @@ BytecodeGenerator::BytecodeGenerator(VM& vm, FunctionNode* functionNode, Unlinke
 
         RefPtr<RegisterID> thrownValue = newTemporary();
         RegisterID* unused = newTemporary();
-        emitCatch(unused, thrownValue.get());
+        emitCatch(unused, thrownValue.get(), tryFormalParametersData);
 
         // return promiseCapability.@reject(thrownValue)
         RefPtr<RegisterID> reject = emitGetById(newTemporary(), promiseCapabilityRegister(), m_vm->propertyNames->builtinNames().rejectPrivateName());
@@ -4009,11 +4021,9 @@ void BytecodeGenerator::popTry(TryData* tryData, Label& end)
     m_tryContextStack.removeLast();
 }
 
-void BytecodeGenerator::emitCatch(RegisterID* exceptionRegister, RegisterID* thrownValueRegister)
+void BytecodeGenerator::emitCatch(RegisterID* exceptionRegister, RegisterID* thrownValueRegister, TryData* data)
 {
-    emitOpcode(op_catch);
-    instructions().append(exceptionRegister->index());
-    instructions().append(thrownValueRegister->index());
+    m_catchesToEmit.append(CatchEntry { data, exceptionRegister->index(), thrownValueRegister->index() });
 }
 
 void BytecodeGenerator::restoreScopeRegister(int lexicalScopeIndex)
@@ -4345,7 +4355,7 @@ void BytecodeGenerator::emitEnumeration(ThrowableExpressionData* node, Expressio
             RefPtr<RegisterID> finallyExceptionRegister = newTemporary();
             RegisterID* unused = newTemporary();
 
-            emitCatch(completionValueRegister(), unused);
+            emitCatch(completionValueRegister(), unused, tryData);
             emitSetCompletionType(CompletionType::Throw);
             emitMove(finallyExceptionRegister.get(), completionValueRegister());
             emitJump(finallyBodyLabel.get());
@@ -4385,7 +4395,7 @@ void BytecodeGenerator::emitEnumeration(ThrowableExpressionData* node, Expressio
                 emitLabel(catchLabel.get());
                 RefPtr<RegisterID> exceptionRegister = newTemporary();
                 RegisterID* unused = newTemporary();
-                emitCatch(exceptionRegister.get(), unused);
+                emitCatch(exceptionRegister.get(), unused, returnCallTryData);
                 // Since this is a synthesized catch block and we're guaranteed to never need
                 // to resolve any symbols from the scope, we can skip restoring the scope
                 // register here.
index 17f65fe..894ad28 100644 (file)
@@ -792,7 +792,7 @@ namespace JSC {
         TryData* pushTry(Label& start, Label& handlerLabel, HandlerType);
         // End a try block. 'end' must have been emitted.
         void popTry(TryData*, Label& end);
-        void emitCatch(RegisterID* exceptionRegister, RegisterID* thrownValueRegister);
+        void emitCatch(RegisterID* exceptionRegister, RegisterID* thrownValueRegister, TryData*);
 
     private:
         static const int CurrentLexicalScopeIndex = -2;
@@ -1200,6 +1200,9 @@ namespace JSC {
         bool m_inTailPosition { false };
         bool m_needsToUpdateArrowFunctionContext;
         DerivedContextType m_derivedContextType { DerivedContextType::None };
+
+        using CatchEntry = std::tuple<TryData*, int, int>;
+        Vector<CatchEntry> m_catchesToEmit;
     };
 
 } // namespace JSC
index 14fb7a3..c61a9b9 100644 (file)
@@ -3408,6 +3408,9 @@ void TryNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
     Label& tryHandlerLabel = m_catchBlock ? *catchLabel : *finallyViaThrowLabel;
     HandlerType tryHandlerType = m_catchBlock ? HandlerType::Catch : HandlerType::Finally;
     TryData* tryData = generator.pushTry(tryStartLabel.get(), tryHandlerLabel, tryHandlerType);
+    TryData* finallyTryData = nullptr;
+    if (!m_catchBlock && m_finallyBlock)
+        finallyTryData = tryData;
 
     generator.emitNode(dst, m_tryBlock);
 
@@ -3424,14 +3427,13 @@ void TryNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
         generator.emitLabel(*catchLabel);
         RefPtr<RegisterID> thrownValueRegister = generator.newTemporary();
         RegisterID* unused = generator.newTemporary();
-        generator.emitCatch(unused, thrownValueRegister.get());
+        generator.emitCatch(unused, thrownValueRegister.get(), tryData);
         generator.restoreScopeRegister();
 
-        TryData* tryData = nullptr;
         if (m_finallyBlock) {
             // If the catch block throws an exception and we have a finally block, then the finally
             // block should "catch" that exception.
-            tryData = generator.pushTry(*catchLabel, *finallyViaThrowLabel, HandlerType::Finally);
+            finallyTryData = generator.pushTry(*catchLabel, *finallyViaThrowLabel, HandlerType::Finally);
         }
 
         if (m_catchPattern) {
@@ -3452,7 +3454,7 @@ void TryNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
         if (m_finallyBlock) {
             generator.emitSetCompletionType(CompletionType::Normal);
             generator.emitJump(*finallyLabel);
-            generator.popTry(tryData, *finallyViaThrowLabel);
+            generator.popTry(finallyTryData, *finallyViaThrowLabel);
         }
 
         generator.emitLabel(*catchEndLabel);
@@ -3465,7 +3467,7 @@ void TryNode::emitBytecode(BytecodeGenerator& generator, RegisterID* dst)
         // Entry to the finally block for CompletionType::Throw.
         generator.emitLabel(*finallyViaThrowLabel);
         RegisterID* unused = generator.newTemporary();
-        generator.emitCatch(generator.completionValueRegister(), unused);
+        generator.emitCatch(generator.completionValueRegister(), unused, finallyTryData);
         generator.emitSetCompletionType(CompletionType::Throw);
 
         // Entry to the finally block for CompletionTypes other than Throw.
index 40eea94..bba06da 100644 (file)
@@ -208,6 +208,7 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         break;
     }
         
+    case ExtractCatchLocal:
     case ExtractOSREntryLocal: {
         forNode(node).makeBytecodeTop();
         break;
@@ -1851,7 +1852,7 @@ bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimi
         // FIXME: Do sparse conditional things.
         break;
     }
-            
+
     case Return:
         m_state.setIsValid(false);
         break;
index 903685a..7a18950 100644 (file)
 
 namespace JSC { namespace DFG {
 
-class BackwardsCFG : public BackwardsGraph<CFG> {
+class BackwardsCFG : public BackwardsGraph<SSACFG> {
     WTF_MAKE_NONCOPYABLE(BackwardsCFG);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     BackwardsCFG(Graph& graph)
-        : BackwardsGraph<CFG>(*graph.m_cfg)
+        : BackwardsGraph<SSACFG>(selectCFG<SSACFG>(graph))
     {
     }
 };
index 383ee4b..c2ca9f3 100644 (file)
@@ -37,6 +37,7 @@ BasicBlock::BasicBlock(
     : bytecodeBegin(bytecodeBegin)
     , index(NoBlock)
     , isOSRTarget(false)
+    , isCatchEntrypoint(false)
     , cfaHasVisited(false)
     , cfaShouldRevisit(false)
     , cfaFoundConstants(false)
index 18773d0..de6abe8 100644 (file)
@@ -82,17 +82,9 @@ struct BasicBlock : RefCounted<BasicBlock> {
         size_t i = size();
         while (i--) {
             Node* node = at(i);
-            switch (node->op()) {
-            case Jump:
-            case Branch:
-            case Switch:
-            case Return:
-            case TailCall:
-            case DirectTailCall:
-            case TailCallVarargs:
-            case TailCallForwardVarargs:
-            case Unreachable:
+            if (node->isTerminal())
                 return NodeAndIndex(node, i);
+            switch (node->op()) {
             // The bitter end can contain Phantoms and the like. There will probably only be one or two nodes after the terminal. They are all no-ops and will not have any checked children.
             case Check: // This is here because it's our universal no-op.
             case Phantom:
@@ -185,6 +177,7 @@ struct BasicBlock : RefCounted<BasicBlock> {
     BlockIndex index;
     
     bool isOSRTarget;
+    bool isCatchEntrypoint;
     bool cfaHasVisited;
     bool cfaShouldRevisit;
     bool cfaFoundConstants;
index a3cbb20..e97b387 100644 (file)
@@ -37,6 +37,7 @@
 #include "CodeBlockWithJITType.h"
 #include "DFGAbstractHeap.h"
 #include "DFGArrayMode.h"
+#include "DFGCFG.h"
 #include "DFGCapabilities.h"
 #include "DFGClobberize.h"
 #include "DFGClobbersExitState.h"
@@ -401,14 +402,14 @@ private:
         // We can't exit anymore because our OSR exit state has changed.
         m_exitOK = false;
 
-        DelayedSetLocal delayed(currentCodeOrigin(), operand, value);
+        DelayedSetLocal delayed(currentCodeOrigin(), operand, value, setMode);
         
         if (setMode == NormalSet) {
             m_setLocalQueue.append(delayed);
-            return 0;
+            return nullptr;
         }
         
-        return delayed.execute(this, setMode);
+        return delayed.execute(this);
     }
     
     void processSetLocalQueue()
@@ -642,6 +643,7 @@ private:
             flushDirect(inlineStackEntry->remapOperand(virtualRegisterForArgument(argument)));
         if (!inlineStackEntry->m_inlineCallFrame && m_graph.needsFlushedThis())
             flushDirect(virtualRegisterForArgument(0));
+
         if (m_graph.needsScopeRegister())
             flushDirect(m_codeBlock->scopeRegister());
     }
@@ -1131,7 +1133,7 @@ private:
         // Potential block linking targets. Must be sorted by bytecodeBegin, and
         // cannot have two blocks that have the same bytecodeBegin.
         Vector<BasicBlock*> m_blockLinkingTargets;
-        
+
         // If the callsite's basic block was split into two, then this will be
         // the head of the callsite block. It needs its successors linked to the
         // m_unlinkedBlocks, but not the other way around: there's no way for
@@ -1200,21 +1202,23 @@ private:
         CodeOrigin m_origin;
         VirtualRegister m_operand;
         Node* m_value;
+        SetMode m_setMode;
         
         DelayedSetLocal() { }
-        DelayedSetLocal(const CodeOrigin& origin, VirtualRegister operand, Node* value)
+        DelayedSetLocal(const CodeOrigin& origin, VirtualRegister operand, Node* value, SetMode setMode)
             : m_origin(origin)
             , m_operand(operand)
             , m_value(value)
+            , m_setMode(setMode)
         {
             RELEASE_ASSERT(operand.isValid());
         }
         
-        Node* execute(ByteCodeParser* parser, SetMode setMode = NormalSet)
+        Node* execute(ByteCodeParser* parser)
         {
             if (m_operand.isArgument())
-                return parser->setArgument(m_origin, m_operand, m_value, setMode);
-            return parser->setLocal(m_origin, m_operand, m_value, setMode);
+                return parser->setArgument(m_origin, m_operand, m_value, m_setMode);
+            return parser->setLocal(m_origin, m_operand, m_value, m_setMode);
         }
     };
     
@@ -4135,7 +4139,11 @@ bool ByteCodeParser::parseBlock(unsigned limit)
     // us to track if a use of an argument may use the actual argument passed, as
     // opposed to using a value we set explicitly.
     if (m_currentBlock == m_graph.block(0) && !inlineCallFrame()) {
-        m_graph.m_arguments.resize(m_numArguments);
+        auto addResult = m_graph.m_entrypointToArguments.add(m_currentBlock, ArgumentsVector());
+        RELEASE_ASSERT(addResult.isNewEntry);
+        ArgumentsVector& entrypointArguments = addResult.iterator->value;
+        entrypointArguments.resize(m_numArguments);
+
         // We will emit SetArgument nodes. They don't exit, but we're at the top of an op_enter so
         // exitOK = true.
         m_exitOK = true;
@@ -4148,7 +4156,7 @@ bool ByteCodeParser::parseBlock(unsigned limit)
                 m_inlineStackTop->m_exitProfile.hasExitSite(m_currentIndex, BadIndexingType));
             
             Node* setArgument = addToGraph(SetArgument, OpInfo(variable));
-            m_graph.m_arguments[argument] = setArgument;
+            entrypointArguments[argument] = setArgument;
             m_currentBlock->variablesAtTail.setArgumentFirstTime(argument, setArgument);
         }
     }
@@ -5218,10 +5226,126 @@ bool ByteCodeParser::parseBlock(unsigned limit)
             addToGraph(Unreachable);
             LAST_OPCODE(op_throw_static_error);
 
-        case op_catch:
+        case op_catch: {
             m_graph.m_hasExceptionHandlers = true;
+
+            if (inlineCallFrame()) {
+                // We can't do OSR entry into an inlined frame.
+                NEXT_OPCODE(op_catch);
+            }
+
+            if (isFTL(m_graph.m_plan.mode)) {
+                // FIXME: Support catch in the FTL.
+                // https://bugs.webkit.org/show_bug.cgi?id=175396
+                NEXT_OPCODE(op_catch);
+            }
+
+            RELEASE_ASSERT(!m_currentBlock->size());
+
+            ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(currentInstruction[3].u.pointer);
+
+            if (!buffer) {
+                NEXT_OPCODE(op_catch); // This catch has yet to execute. Note: this load can be racy with the main thread.
+            }
+
+            // We're now committed to compiling this as an entrypoint.
+            m_currentBlock->isCatchEntrypoint = true;
+            m_graph.m_entrypoints.append(m_currentBlock);
+
+            Vector<SpeculatedType> argumentPredictions(m_numArguments);
+            Vector<SpeculatedType> localPredictions;
+            HashSet<unsigned, WTF::IntHash<unsigned>, WTF::UnsignedWithZeroKeyHashTraits<unsigned>> seenArguments;
+
+            {
+                ConcurrentJSLocker locker(m_inlineStackTop->m_profiledBlock->m_lock);
+
+                buffer->forEach([&] (ValueProfileAndOperand& profile) {
+                    VirtualRegister operand(profile.m_operand);
+                    SpeculatedType prediction = profile.m_profile.computeUpdatedPrediction(locker);
+                    if (operand.isLocal())
+                        localPredictions.append(prediction);
+                    else {
+                        RELEASE_ASSERT(operand.isArgument());
+                        RELEASE_ASSERT(static_cast<uint32_t>(operand.toArgument()) < argumentPredictions.size());
+                        if (validationEnabled())
+                            seenArguments.add(operand.toArgument());
+                        argumentPredictions[operand.toArgument()] = prediction;
+                    }
+                });
+
+                if (validationEnabled()) {
+                    for (unsigned argument = 0; argument < m_numArguments; ++argument)
+                        RELEASE_ASSERT(seenArguments.contains(argument));
+                }
+            }
+
+            Vector<std::pair<VirtualRegister, Node*>> localsToSet;
+            localsToSet.reserveInitialCapacity(buffer->m_size); // Note: This will reserve more than the number of locals we see below because the buffer includes arguments.
+
+            // We're not allowed to exit here since we would not properly recover values.
+            // We first need to bootstrap the catch entrypoint state.
+            m_exitOK = false; 
+
+            unsigned numberOfLocals = 0;
+            buffer->forEach([&] (ValueProfileAndOperand& profile) {
+                VirtualRegister operand(profile.m_operand);
+                if (operand.isArgument())
+                    return;
+                ASSERT(operand.isLocal());
+                Node* value = addToGraph(ExtractCatchLocal, OpInfo(numberOfLocals), OpInfo(localPredictions[numberOfLocals]));
+                ++numberOfLocals;
+                addToGraph(MovHint, OpInfo(profile.m_operand), value);
+                localsToSet.uncheckedAppend(std::make_pair(operand, value));
+            });
+
+            if (!m_graph.m_maxLocalsForCatchOSREntry)
+                m_graph.m_maxLocalsForCatchOSREntry = 0;
+            m_graph.m_maxLocalsForCatchOSREntry = std::max(numberOfLocals, *m_graph.m_maxLocalsForCatchOSREntry);
+
+            // We could not exit before this point in the program because we would not know how to do value
+            // recovery for live locals. The above IR sets up the necessary state so we can recover values
+            // during OSR exit. 
+            //
+            // The nodes that follow here all exit to the following bytecode instruction, not
+            // the op_catch. Exiting to op_catch is reserved for when an exception is thrown.
+            // The SetArgument nodes that follow below may exit because we may hoist type checks
+            // to them. The SetLocal nodes that follow below may exit because we may choose
+            // a flush format that speculates on the type of the local.
+            m_exitOK = true; 
+            addToGraph(ExitOK);
+
+            {
+                auto addResult = m_graph.m_entrypointToArguments.add(m_currentBlock, ArgumentsVector());
+                RELEASE_ASSERT(addResult.isNewEntry);
+                ArgumentsVector& entrypointArguments = addResult.iterator->value;
+                entrypointArguments.resize(m_numArguments);
+
+                unsigned exitBytecodeIndex = m_currentIndex + OPCODE_LENGTH(op_catch);
+
+                for (unsigned argument = 0; argument < argumentPredictions.size(); ++argument) {
+                    VariableAccessData* variable = newVariableAccessData(virtualRegisterForArgument(argument));
+                    variable->predict(argumentPredictions[argument]);
+
+                    variable->mergeStructureCheckHoistingFailed(
+                        m_inlineStackTop->m_exitProfile.hasExitSite(exitBytecodeIndex, BadCache));
+                    variable->mergeCheckArrayHoistingFailed(
+                        m_inlineStackTop->m_exitProfile.hasExitSite(exitBytecodeIndex, BadIndexingType));
+
+                    Node* setArgument = addToGraph(SetArgument, OpInfo(variable));
+                    setArgument->origin.forExit.bytecodeIndex = exitBytecodeIndex;
+                    m_currentBlock->variablesAtTail.setArgumentFirstTime(argument, setArgument);
+                    entrypointArguments[argument] = setArgument;
+                }
+            }
+
+            for (const std::pair<VirtualRegister, Node*>& pair : localsToSet) {
+                DelayedSetLocal delayed { currentCodeOrigin(), pair.first, pair.second, ImmediateNakedSet };
+                m_setLocalQueue.append(delayed);
+            }
+
             NEXT_OPCODE(op_catch);
-            
+        }
+
         case op_call:
             handleCall(currentInstruction, Call, CallMode::Regular);
             ASSERT_WITH_MESSAGE(m_currentInstruction == currentInstruction, "handleCall, which may have inlined the callee, trashed m_currentInstruction");
@@ -6246,8 +6370,10 @@ void ByteCodeParser::parseCodeBlock()
                     m_inlineStackTop->m_unlinkedBlocks.append(UnlinkedBlock(block.ptr()));
                     m_inlineStackTop->m_blockLinkingTargets.append(block.ptr());
                     // The first block is definitely an OSR target.
-                    if (!m_graph.numBlocks())
+                    if (!m_graph.numBlocks()) {
                         block->isOSRTarget = true;
+                        m_graph.m_entrypoints.append(block.ptr());
+                    }
                     m_graph.appendBlock(WTFMove(block));
                     prepareToParseBlock();
                 }
@@ -6304,10 +6430,12 @@ bool ByteCodeParser::parse()
         m_codeBlock->numParameters(), InlineCallFrame::Call);
     
     parseCodeBlock();
-
     linkBlocks(inlineStackEntry.m_unlinkedBlocks, inlineStackEntry.m_blockLinkingTargets);
+
     m_graph.determineReachability();
     m_graph.killUnreachableBlocks();
+
+    m_graph.m_cpsCFG = std::make_unique<CPSCFG>(m_graph);
     
     for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
         BasicBlock* block = m_graph.block(blockIndex);
@@ -6318,7 +6446,7 @@ bool ByteCodeParser::parse()
         ASSERT(block->variablesAtTail.numberOfLocals() == m_graph.block(0)->variablesAtHead.numberOfLocals());
         ASSERT(block->variablesAtTail.numberOfArguments() == m_graph.block(0)->variablesAtHead.numberOfArguments());
     }
-    
+
     m_graph.m_localVars = m_numLocals;
     m_graph.m_parameterSlots = m_parameterSlots;
 
index e9ed9e8..a85604a 100644 (file)
@@ -31,6 +31,7 @@
 #include "DFGBlockMapInlines.h"
 #include "DFGBlockSet.h"
 #include "DFGGraph.h"
+#include <wtf/SingleRootGraph.h>
 
 namespace JSC { namespace DFG {
 
@@ -48,7 +49,19 @@ public:
     {
     }
 
-    Node root() { return m_graph.block(0); }
+    Node root()
+    {
+        ASSERT(m_graph.m_form == SSA || m_graph.m_isInSSAConversion);
+        return m_graph.block(0);
+    }
+
+    List roots()
+    {
+        List result;
+        for (BasicBlock* root : m_graph.m_entrypoints)
+            result.append(root);
+        return result;
+    }
 
     template<typename T>
     Map<T> newMap() { return BlockMap<T>(m_graph); }
@@ -71,6 +84,31 @@ private:
     Graph& m_graph;
 };
 
+class CPSCFG : public SingleRootGraph<CFG> {
+public:
+    CPSCFG(Graph& graph)
+        : SingleRootGraph<CFG>(*graph.m_ssaCFG)
+    {
+        ASSERT(graph.m_entrypoints.size());
+    }
+};
+
+using SSACFG = CFG;
+
+template <typename T, typename = typename std::enable_if<std::is_same<T, CPSCFG>::value>::type>
+CPSCFG& selectCFG(Graph& graph)
+{
+    RELEASE_ASSERT(graph.m_cpsCFG);
+    return *graph.m_cpsCFG;
+}
+
+template <typename T, typename = typename std::enable_if<std::is_same<T, SSACFG>::value>::type>
+SSACFG& selectCFG(Graph& graph)
+{
+    RELEASE_ASSERT(graph.m_ssaCFG);
+    return *graph.m_ssaCFG;
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index fbc9c2d..61b920e 100644 (file)
@@ -369,8 +369,13 @@ private:
         // But those SetArguments used for the actual arguments to the machine CodeBlock get
         // special-cased. We could have instead used two different node types - one for the arguments
         // at the prologue case, and another for the other uses. But this seemed like IR overkill.
-        for (unsigned i = m_graph.m_arguments.size(); i--;)
-            m_graph.block(0)->variablesAtHead.setArgumentFirstTime(i, m_graph.m_arguments[i]);
+
+        for (auto& pair : m_graph.m_entrypointToArguments) {
+            BasicBlock* entrypoint = pair.key;
+            const ArgumentsVector& arguments = pair.value;
+            for (unsigned i = arguments.size(); i--;)
+                entrypoint->variablesAtHead.setArgumentFirstTime(i, arguments[i]);
+        }
     }
     
     template<OperandKind operandKind>
index 5968974..57ec4a8 100644 (file)
@@ -598,7 +598,7 @@ public:
         ASSERT(m_graph.m_form == SSA);
         
         m_graph.initializeNodeOwners();
-        m_graph.ensureDominators();
+        m_graph.ensureSSADominators();
         
         m_preOrder = m_graph.blocksInPreOrder();
         
@@ -690,7 +690,7 @@ public:
         
         for (unsigned i = result.iterator->value.size(); i--;) {
             Node* candidate = result.iterator->value[i];
-            if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
+            if (m_graph.m_ssaDominators->dominates(candidate->owner, m_block)) {
                 m_node->replaceWith(candidate);
                 m_changed = true;
                 return;
@@ -779,7 +779,7 @@ public:
             // We require strict domination because this would only see things in our own block if
             // they came *after* our position in the block. Clearly, while our block dominates
             // itself, the things in the block after us don't dominate us.
-            if (m_graph.m_dominators->strictlyDominates(block, m_block)) {
+            if (m_graph.m_ssaDominators->strictlyDominates(block, m_block)) {
                 if (verbose)
                     dataLog("        It strictly dominates.\n");
                 DFG_ASSERT(m_graph, m_node, data.didVisit);
@@ -856,7 +856,7 @@ public:
                 if (!result.isNewEntry) {
                     for (unsigned i = result.iterator->value.size(); i--;) {
                         Node* candidate = result.iterator->value[i];
-                        if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
+                        if (m_graph.m_ssaDominators->dominates(candidate->owner, m_block)) {
                             ASSERT(candidate);
                             match->replaceWith(candidate);
                             match.setNode(candidate);
index 9a4bd38..166e6af 100644 (file)
@@ -127,7 +127,6 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
         ASSERT(!node->origin.semantic.inlineCallFrame);
         read(AbstractHeap(Stack, graph.m_codeBlock->scopeRegister()));
     }
-        
     
     switch (node->op()) {
     case JSConstant:
@@ -141,6 +140,7 @@ void clobberize(Graph& graph, Node* node, const ReadFunctor& read, const WriteFu
     case Phantom:
     case Check:
     case ExtractOSREntryLocal:
+    case ExtractCatchLocal:
     case CheckStructureImmediate:
         return;
         
index ba39ff9..25aae47 100644 (file)
@@ -37,7 +37,7 @@ class ControlEquivalenceAnalysis {
     WTF_MAKE_FAST_ALLOCATED;
 public:
     ControlEquivalenceAnalysis(Graph& graph)
-        : m_dominators(graph.ensureDominators())
+        : m_dominators(graph.ensureSSADominators())
         , m_backwardsDominators(graph.ensureBackwardsDominators())
     {
     }
@@ -75,7 +75,7 @@ public:
     }
 
 private:
-    Dominators& m_dominators;
+    SSADominators& m_dominators;
     BackwardsDominators& m_backwardsDominators;
 };
 
index a70a869..fe57114 100644 (file)
@@ -53,7 +53,8 @@ public:
         for (BasicBlock* block : m_graph.blocksInPreOrder())
             fixupBlock(block);
         
-        cleanVariables(m_graph.m_arguments);
+        for (auto& argumentsVector : m_graph.m_entrypointToArguments.values())
+            cleanVariables(argumentsVector);
 
         // Just do a basic Phantom/Check clean-up.
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
index 06d1dac..05fded4 100644 (file)
@@ -95,8 +95,8 @@ Vector<Disassembler::DumpedOp> Disassembler::createDumpList(LinkBuffer& linkBuff
     dumpHeader(out, linkBuffer);
     append(result, out, previousOrigin);
     
-    m_graph.ensureDominators();
-    m_graph.ensureNaturalLoops();
+    m_graph.ensureCPSDominators();
+    m_graph.ensureCPSNaturalLoops();
     
     const char* prefix = "    ";
     const char* disassemblyPrefix = "        ";
index 07dca04..6d9d228 100644 (file)
@@ -199,6 +199,7 @@ bool doesGC(Graph& graph, Node* node)
     case LoadKeyFromMapBucket:
     case LoadValueFromMapBucket:
     case Unreachable:
+    case ExtractCatchLocal:
     case ExtractOSREntryLocal:
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
index 68b2d75..6ab8deb 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 namespace JSC { namespace DFG {
 
-class Dominators : public WTF::Dominators<CFG> {
+template <typename CFGKind>
+class Dominators : public WTF::Dominators<CFGKind> {
     WTF_MAKE_NONCOPYABLE(Dominators);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     Dominators(Graph& graph)
-        : WTF::Dominators<CFG>(*graph.m_cfg)
+        : WTF::Dominators<CFGKind>(selectCFG<CFGKind>(graph))
     {
     }
 };
 
+using SSADominators = Dominators<SSACFG>;
+using CPSDominators = Dominators<CPSCFG>;
+
+template <typename T, typename = typename std::enable_if<std::is_same<T, CPSCFG>::value>::type>
+CPSDominators& ensureDominatorsForCFG(Graph& graph)
+{
+    return graph.ensureCPSDominators();
+}
+
+template <typename T, typename = typename std::enable_if<std::is_same<T, SSACFG>::value>::type>
+SSADominators& ensureDominatorsForCFG(Graph& graph)
+{
+    return graph.ensureSSADominators();
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index aa50ede..85f037d 100644 (file)
@@ -40,11 +40,12 @@ public:
         , m_block(block)
         , m_result(true)
     {
+        ASSERT(graph.m_form == SSA);
     }
     
     void operator()(Node*, Edge edge)
     {
-        bool result = m_graph.m_dominators->dominates(edge.node()->owner, m_block);
+        bool result = m_graph.m_ssaDominators->dominates(edge.node()->owner, m_block);
         if (verbose) {
             dataLog(
                 "Checking if ", edge, " in ", *edge.node()->owner,
index daf0bd2..615999c 100644 (file)
@@ -2008,6 +2008,7 @@ private:
         case CheckTraps:
         case Unreachable:
         case ExtractOSREntryLocal:
+        case ExtractCatchLocal:
         case LoopHint:
         case MovHint:
         case ZombieHint:
@@ -3203,6 +3204,7 @@ private:
                         if (edge->hasDoubleResult())
                             break;
             
+                        ASSERT(indexForChecks != UINT_MAX);
                         if (edge->isNumberConstant()) {
                             result = m_insertionSet.insertNode(
                                 indexForChecks, SpecBytecodeDouble, DoubleConstant, originForChecks,
@@ -3233,6 +3235,7 @@ private:
                         if (edge->hasInt52Result())
                             break;
             
+                        ASSERT(indexForChecks != UINT_MAX);
                         if (edge->isAnyIntConstant()) {
                             result = m_insertionSet.insertNode(
                                 indexForChecks, SpecAnyInt, Int52Constant, originForChecks,
@@ -3259,6 +3262,7 @@ private:
                         if (!edge->hasDoubleResult() && !edge->hasInt52Result())
                             break;
             
+                        ASSERT(indexForChecks != UINT_MAX);
                         if (edge->hasDoubleResult()) {
                             result = m_insertionSet.insertNode(
                                 indexForChecks, SpecBytecodeDouble, ValueRep, originForChecks,
@@ -3300,6 +3304,7 @@ private:
                             break;
                         }
 
+                        ASSERT(indexForChecks != UINT_MAX);
                         m_insertionSet.insertNode(
                             indexForChecks, SpecNone, Check, originForChecks, edge);
 
index f7084fb..16673ea 100644 (file)
@@ -35,7 +35,7 @@
 
 namespace JSC { namespace DFG {
 
-enum FlushFormat {
+enum FlushFormat : uint8_t {
     DeadFlush,
     FlushedInt32,
     FlushedInt52,
index 8888afd..1d48f8c 100644 (file)
@@ -45,7 +45,6 @@
 #include "DFGJITCode.h"
 #include "DFGMayExit.h"
 #include "DFGNaturalLoops.h"
-#include "DFGPrePostNumbering.h"
 #include "DFGVariableAccessDataDump.h"
 #include "FullBytecodeLiveness.h"
 #include "FunctionExecutableDump.h"
@@ -73,7 +72,7 @@ Graph::Graph(VM& vm, Plan& plan)
     , m_plan(plan)
     , m_codeBlock(m_plan.codeBlock)
     , m_profiledBlock(m_codeBlock->alternative())
-    , m_cfg(std::make_unique<CFG>(*this))
+    , m_ssaCFG(std::make_unique<SSACFG>(*this))
     , m_nextMachineLocal(0)
     , m_fixpointState(BeforeFixpoint)
     , m_structureRegistrationState(HaveNotStartedRegistering)
@@ -409,9 +408,13 @@ bool Graph::terminalsAreValid()
     return true;
 }
 
+static BasicBlock* unboxLoopNode(const CPSCFG::Node& node) { return node.node(); }
+static BasicBlock* unboxLoopNode(BasicBlock* block) { return block; }
+
 void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* block, PhiNodeDumpMode phiNodeDumpMode, DumpContext* context)
 {
-    out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "):", block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "", "\n");
+    out.print(prefix, "Block ", *block, " (", inContext(block->at(0)->origin.semantic, context), "):",
+        block->isReachable ? "" : " (skipped)", block->isOSRTarget ? " (OSR target)" : "", block->isCatchEntrypoint ? " (Catch Entrypoint)" : "", "\n");
     if (block->executionCount == block->executionCount)
         out.print(prefix, "  Execution count: ", block->executionCount, "\n");
     out.print(prefix, "  Predecessors:");
@@ -422,18 +425,26 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
     if (block->terminal()) {
         for (BasicBlock* successor : block->successors()) {
             out.print(" ", *successor);
-            if (m_prePostNumbering)
-                out.print(" (", m_prePostNumbering->edgeKind(block, successor), ")");
         }
     } else
         out.print(" <invalid>");
     out.print("\n");
-    if (m_dominators && terminalsAreValid()) {
-        out.print(prefix, "  Dominated by: ", m_dominators->dominatorsOf(block), "\n");
-        out.print(prefix, "  Dominates: ", m_dominators->blocksDominatedBy(block), "\n");
-        out.print(prefix, "  Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
-        out.print(prefix, "  Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
+
+    auto printDominators = [&] (auto& dominators) {
+        out.print(prefix, "  Dominated by: ", dominators.dominatorsOf(block), "\n");
+        out.print(prefix, "  Dominates: ", dominators.blocksDominatedBy(block), "\n");
+        out.print(prefix, "  Dominance Frontier: ", dominators.dominanceFrontierOf(block), "\n");
+        out.print(prefix, "  Iterated Dominance Frontier: ",
+            dominators.iteratedDominanceFrontierOf(typename std::remove_reference<decltype(dominators)>::type::List { block }), "\n");
+    };
+
+    if (terminalsAreValid()) {
+        if (m_ssaDominators)
+            printDominators(*m_ssaDominators);
+        else if (m_cpsDominators)
+            printDominators(*m_cpsDominators);
     }
+
     if (m_backwardsDominators && terminalsAreValid()) {
         out.print(prefix, "  Backwards dominates by: ", m_backwardsDominators->dominatorsOf(block), "\n");
         out.print(prefix, "  Backwards dominates: ", m_backwardsDominators->blocksDominatedBy(block), "\n");
@@ -446,29 +457,33 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
         }
         out.print("\n");
     }
-    if (m_prePostNumbering)
-        out.print(prefix, "  Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
-    if (m_naturalLoops) {
-        if (const NaturalLoop* loop = m_naturalLoops->headerOf(block)) {
+
+    auto printNaturalLoops = [&] (auto& naturalLoops) {
+        if (const auto* loop = naturalLoops->headerOf(block)) {
             out.print(prefix, "  Loop header, contains:");
             Vector<BlockIndex> sortedBlockList;
             for (unsigned i = 0; i < loop->size(); ++i)
-                sortedBlockList.append(loop->at(i)->index);
+                sortedBlockList.append(unboxLoopNode(loop->at(i))->index);
             std::sort(sortedBlockList.begin(), sortedBlockList.end());
             for (unsigned i = 0; i < sortedBlockList.size(); ++i)
                 out.print(" #", sortedBlockList[i]);
             out.print("\n");
         }
         
-        Vector<const NaturalLoop*> containingLoops =
-            m_naturalLoops->loopsOf(block);
+        auto containingLoops = naturalLoops->loopsOf(block);
         if (!containingLoops.isEmpty()) {
             out.print(prefix, "  Containing loop headers:");
             for (unsigned i = 0; i < containingLoops.size(); ++i)
-                out.print(" ", *containingLoops[i]->header());
+                out.print(" ", *unboxLoopNode(containingLoops[i]->header()));
             out.print("\n");
         }
-    }
+    };
+
+    if (m_ssaNaturalLoops)
+        printNaturalLoops(m_ssaNaturalLoops);
+    else if (m_cpsNaturalLoops)
+        printNaturalLoops(m_cpsNaturalLoops);
+
     if (!block->phis.isEmpty()) {
         out.print(prefix, "  Phi Nodes:");
         for (size_t i = 0; i < block->phis.size(); ++i) {
@@ -502,8 +517,10 @@ void Graph::dump(PrintStream& out, DumpContext* context)
     out.print("  Fixpoint state: ", m_fixpointState, "; Form: ", m_form, "; Unification state: ", m_unificationState, "; Ref count state: ", m_refCountState, "\n");
     if (m_form == SSA)
         out.print("  Argument formats: ", listDump(m_argumentFormats), "\n");
-    else
-        out.print("  Arguments: ", listDump(m_arguments), "\n");
+    else {
+        for (auto pair : m_entrypointToArguments)
+            out.print("  Arguments for block#", pair.key->index, ": ", listDump(pair.value), "\n");
+    }
     out.print("\n");
     
     Node* lastNode = nullptr;
@@ -640,8 +657,10 @@ void Graph::handleSuccessor(Vector<BasicBlock*, 16>& worklist, BasicBlock* block
 void Graph::determineReachability()
 {
     Vector<BasicBlock*, 16> worklist;
-    worklist.append(block(0));
-    block(0)->isReachable = true;
+    for (BasicBlock* entrypoint : m_entrypoints) {
+        entrypoint->isReachable = true;
+        worklist.append(entrypoint);
+    }
     while (!worklist.isEmpty()) {
         BasicBlock* block = worklist.takeLast();
         for (unsigned i = block->numSuccessors(); i--;)
@@ -798,9 +817,10 @@ void Graph::killUnreachableBlocks()
 
 void Graph::invalidateCFG()
 {
-    m_dominators = nullptr;
-    m_naturalLoops = nullptr;
-    m_prePostNumbering = nullptr;
+    m_cpsDominators = nullptr;
+    m_ssaDominators = nullptr;
+    m_cpsNaturalLoops = nullptr;
+    m_ssaNaturalLoops = nullptr;
     m_controlEquivalenceAnalysis = nullptr;
     m_backwardsDominators = nullptr;
     m_backwardsCFG = nullptr;
@@ -850,12 +870,37 @@ BlockList Graph::blocksInPreOrder()
 {
     BlockList result;
     BlockWorklist worklist;
-    worklist.push(block(0));
+    for (BasicBlock* entrypoint : m_entrypoints)
+        worklist.push(entrypoint);
     while (BasicBlock* block = worklist.pop()) {
         result.append(block);
         for (unsigned i = block->numSuccessors(); i--;)
             worklist.push(block->successor(i));
     }
+
+    if (validationEnabled()) {
+        // When iterating over pre order, we should see dominators
+        // before things they dominate.
+        auto validateResults = [&] (auto& dominators) {
+            for (unsigned i = 0; i < result.size(); ++i) {
+                BasicBlock* a = result[i];
+                if (!a)
+                    continue;
+                for (unsigned j = 0; j < result.size(); ++j) {
+                    BasicBlock* b = result[j];
+                    if (!b || a == b)
+                        continue;
+                    if (dominators.dominates(a, b))
+                        RELEASE_ASSERT(i < j);
+                }
+            }
+        };
+
+        if (m_form == SSA || m_isInSSAConversion)
+            validateResults(ensureSSADominators());
+        else
+            validateResults(ensureCPSDominators());
+    }
     return result;
 }
 
@@ -863,7 +908,8 @@ BlockList Graph::blocksInPostOrder()
 {
     BlockList result;
     PostOrderBlockWorklist worklist;
-    worklist.push(block(0));
+    for (BasicBlock* entrypoint : m_entrypoints)
+        worklist.push(entrypoint);
     while (BlockWithOrder item = worklist.pop()) {
         switch (item.order) {
         case VisitOrder::Pre:
@@ -876,6 +922,31 @@ BlockList Graph::blocksInPostOrder()
             break;
         }
     }
+
+    if (validationEnabled()) {
+        auto validateResults = [&] (auto& dominators) {
+            // When iterating over reverse post order, we should see dominators
+            // before things they dominate.
+            for (unsigned i = 0; i < result.size(); ++i) {
+                BasicBlock* a = result[i];
+                if (!a)
+                    continue;
+                for (unsigned j = 0; j < result.size(); ++j) {
+                    BasicBlock* b = result[j];
+                    if (!b || a == b)
+                        continue;
+                    if (dominators.dominates(a, b))
+                        RELEASE_ASSERT(i > j);
+                }
+            }
+        };
+
+        if (m_form == SSA || m_isInSSAConversion)
+            validateResults(ensureSSADominators());
+        else
+            validateResults(ensureCPSDominators());
+    }
+
     return result;
 }
 
@@ -1472,30 +1543,44 @@ void Graph::logAssertionFailure(
     logDFGAssertionFailure(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
 }
 
-Dominators& Graph::ensureDominators()
+CPSDominators& Graph::ensureCPSDominators()
+{
+    RELEASE_ASSERT(m_form != SSA && !m_isInSSAConversion);
+    if (!m_cpsDominators)
+        m_cpsDominators = std::make_unique<CPSDominators>(*this);
+    return *m_cpsDominators;
+}
+
+SSADominators& Graph::ensureSSADominators()
 {
-    if (!m_dominators)
-        m_dominators = std::make_unique<Dominators>(*this);
-    return *m_dominators;
+    RELEASE_ASSERT(m_form == SSA || m_isInSSAConversion);
+    if (!m_ssaDominators)
+        m_ssaDominators = std::make_unique<SSADominators>(*this);
+    return *m_ssaDominators;
 }
 
-PrePostNumbering& Graph::ensurePrePostNumbering()
+CPSNaturalLoops& Graph::ensureCPSNaturalLoops()
 {
-    if (!m_prePostNumbering)
-        m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
-    return *m_prePostNumbering;
+    RELEASE_ASSERT(m_form != SSA && !m_isInSSAConversion);
+    ensureCPSDominators();
+    if (!m_cpsNaturalLoops)
+        m_cpsNaturalLoops = std::make_unique<CPSNaturalLoops>(*this);
+    return *m_cpsNaturalLoops;
 }
 
-NaturalLoops& Graph::ensureNaturalLoops()
+SSANaturalLoops& Graph::ensureSSANaturalLoops()
 {
-    ensureDominators();
-    if (!m_naturalLoops)
-        m_naturalLoops = std::make_unique<NaturalLoops>(*this);
-    return *m_naturalLoops;
+    RELEASE_ASSERT(m_form == SSA);
+    ensureSSADominators();
+    if (!m_ssaNaturalLoops)
+        m_ssaNaturalLoops = std::make_unique<SSANaturalLoops>(*this);
+    return *m_ssaNaturalLoops;
 }
 
 BackwardsCFG& Graph::ensureBackwardsCFG()
 {
+    // We could easily relax this in the future to work over CPS, but today, it's only used in SSA.
+    RELEASE_ASSERT(m_form == SSA); 
     if (!m_backwardsCFG)
         m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
     return *m_backwardsCFG;
@@ -1503,6 +1588,7 @@ BackwardsCFG& Graph::ensureBackwardsCFG()
 
 BackwardsDominators& Graph::ensureBackwardsDominators()
 {
+    RELEASE_ASSERT(m_form == SSA);
     if (!m_backwardsDominators)
         m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
     return *m_backwardsDominators;
@@ -1510,6 +1596,7 @@ BackwardsDominators& Graph::ensureBackwardsDominators()
 
 ControlEquivalenceAnalysis& Graph::ensureControlEquivalenceAnalysis()
 {
+    RELEASE_ASSERT(m_form == SSA);
     if (!m_controlEquivalenceAnalysis)
         m_controlEquivalenceAnalysis = std::make_unique<ControlEquivalenceAnalysis>(*this);
     return *m_controlEquivalenceAnalysis;
@@ -1527,7 +1614,9 @@ MethodOfGettingAValueProfile Graph::methodOfGettingAValueProfileFor(Node* curren
                     if (!node->local().isArgument())
                         return nullptr;
                     int argument = node->local().toArgument();
-                    Node* argumentNode = m_arguments[argument];
+                    // FIXME: We should match SetArgument nodes at other entrypoints as well:
+                    // https://bugs.webkit.org/show_bug.cgi?id=175841
+                    Node* argumentNode = m_entrypointToArguments.find(block(0))->value[argument];
                     if (!argumentNode)
                         return nullptr;
                     if (node->variableAccessData() != argumentNode->variableAccessData())
@@ -1698,6 +1787,13 @@ bool Graph::canDoFastSpread(Node* node, const AbstractValue& value)
     return allGood;
 }
 
+void Graph::clearCPSCFGData()
+{
+    m_cpsNaturalLoops = nullptr;
+    m_cpsDominators = nullptr;
+    m_cpsCFG = nullptr;
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index 66ca511..334ea97 100644 (file)
 #include <wtf/Vector.h>
 #include <wtf/StdLibExtras.h>
 
+namespace WTF {
+template <typename T> class SingleRootGraph;
+}
+
 namespace JSC {
 
 class CodeBlock;
@@ -55,14 +59,21 @@ namespace DFG {
 class BackwardsCFG;
 class BackwardsDominators;
 class CFG;
+class CPSCFG;
 class ControlEquivalenceAnalysis;
-class Dominators;
+template <typename T> class Dominators;
+template <typename T> class NaturalLoops;
 class FlowIndexing;
-class NaturalLoops;
-class PrePostNumbering;
-
 template<typename> class FlowMap;
 
+using ArgumentsVector = Vector<Node*, 8>;
+
+using SSACFG = CFG;
+using CPSDominators = Dominators<CPSCFG>;
+using SSADominators = Dominators<SSACFG>;
+using CPSNaturalLoops = NaturalLoops<CPSCFG>;
+using SSANaturalLoops = NaturalLoops<SSACFG>;
+
 #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
         Node* _node = (node);                                           \
         if (_node->flags() & NodeHasVarArgs) {                          \
@@ -901,27 +912,49 @@ public:
 
     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
 
-    Dominators& ensureDominators();
-    PrePostNumbering& ensurePrePostNumbering();
-    NaturalLoops& ensureNaturalLoops();
+    CPSDominators& ensureCPSDominators();
+    SSADominators& ensureSSADominators();
+    CPSNaturalLoops& ensureCPSNaturalLoops();
+    SSANaturalLoops& ensureSSANaturalLoops();
     BackwardsCFG& ensureBackwardsCFG();
     BackwardsDominators& ensureBackwardsDominators();
     ControlEquivalenceAnalysis& ensureControlEquivalenceAnalysis();
 
-    // This function only makes sense to call after bytecode parsing
+    // These functions only makes sense to call after bytecode parsing
     // because it queries the m_hasExceptionHandlers boolean whose value
     // is only fully determined after bytcode parsing.
+    bool willCatchExceptionInMachineFrame(CodeOrigin codeOrigin)
+    {
+        CodeOrigin ignored;
+        HandlerInfo* ignored2;
+        return willCatchExceptionInMachineFrame(codeOrigin, ignored, ignored2);
+    }
     bool willCatchExceptionInMachineFrame(CodeOrigin, CodeOrigin& opCatchOriginOut, HandlerInfo*& catchHandlerOut);
     
     bool needsScopeRegister() const { return m_hasDebuggerEnabled || m_codeBlock->usesEval(); }
     bool needsFlushedThis() const { return m_codeBlock->usesEval(); }
 
+    void clearCPSCFGData();
+
+    bool isEntrypoint(BasicBlock* block) const
+    {
+        if (m_entrypoints.size() <= 4) {
+            bool result = m_entrypoints.contains(block);
+            ASSERT(result == m_entrypointToArguments.contains(block));
+            return result;
+        }
+        bool result = m_entrypointToArguments.contains(block);
+        ASSERT(result == m_entrypoints.contains(block));
+        return result;
+    }
+
     VM& m_vm;
     Plan& m_plan;
     CodeBlock* m_codeBlock;
     CodeBlock* m_profiledBlock;
     
-    Vector< RefPtr<BasicBlock> , 8> m_blocks;
+    Vector<RefPtr<BasicBlock>, 8> m_blocks;
+    Vector<BasicBlock*, 1> m_entrypoints;
     Vector<Edge, 16> m_varArgChildren;
 
     HashMap<EncodedJSValue, FrozenValue*, EncodedJSValueHash, EncodedJSValueHashTraits> m_frozenValueMap;
@@ -956,11 +989,11 @@ public:
     //
     // If we DCE the ArithAdd and we remove the int check on x, then this won't do the side
     // effects.
-    Vector<Node*, 8> m_arguments;
+    HashMap<BasicBlock*, ArgumentsVector> m_entrypointToArguments;
     
     // In CPS, this is meaningless. In SSA, this is the argument speculation that we've locked in.
     Vector<FlushFormat> m_argumentFormats;
-    
+
     SegmentedVector<VariableAccessData, 16> m_variableAccessData;
     SegmentedVector<ArgumentPosition, 8> m_argumentPositions;
     Bag<Transition> m_transitions;
@@ -982,10 +1015,12 @@ public:
     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
     Vector<Ref<Snippet>> m_domJITSnippets;
-    std::unique_ptr<Dominators> m_dominators;
-    std::unique_ptr<PrePostNumbering> m_prePostNumbering;
-    std::unique_ptr<NaturalLoops> m_naturalLoops;
-    std::unique_ptr<CFG> m_cfg;
+    std::unique_ptr<CPSDominators> m_cpsDominators;
+    std::unique_ptr<SSADominators> m_ssaDominators;
+    std::unique_ptr<CPSNaturalLoops> m_cpsNaturalLoops;
+    std::unique_ptr<SSANaturalLoops> m_ssaNaturalLoops;
+    std::unique_ptr<SSACFG> m_ssaCFG;
+    std::unique_ptr<CPSCFG> m_cpsCFG;
     std::unique_ptr<BackwardsCFG> m_backwardsCFG;
     std::unique_ptr<BackwardsDominators> m_backwardsDominators;
     std::unique_ptr<ControlEquivalenceAnalysis> m_controlEquivalenceAnalysis;
@@ -1009,6 +1044,8 @@ public:
     RefCountState m_refCountState;
     bool m_hasDebuggerEnabled;
     bool m_hasExceptionHandlers { false };
+    bool m_isInSSAConversion { false };
+    std::optional<uint32_t> m_maxLocalsForCatchOSREntry;
     std::unique_ptr<FlowIndexing> m_indexingCache;
     std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
 
index 25b4a6b..c4a58ce 100644 (file)
@@ -93,54 +93,61 @@ static void setLiveValues(Vector<NodeAbstractValuePair>& values, const Vector<No
 
 void InPlaceAbstractState::initialize()
 {
-    BasicBlock* root = m_graph.block(0);
-    root->cfaShouldRevisit = true;
-    root->cfaHasVisited = false;
-    root->cfaFoundConstants = false;
-    root->cfaStructureClobberStateAtHead = StructuresAreWatched;
-    root->cfaStructureClobberStateAtTail = StructuresAreWatched;
-    for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
-        root->valuesAtTail.argument(i).clear();
-
-        FlushFormat format;
-        if (m_graph.m_form == SSA)
-            format = m_graph.m_argumentFormats[i];
-        else {
-            Node* node = m_graph.m_arguments[i];
-            if (!node)
-                format = FlushedJSValue;
-            else {
-                ASSERT(node->op() == SetArgument);
-                format = node->variableAccessData()->flushFormat();
+    for (BasicBlock* entrypoint : m_graph.m_entrypoints) {
+        entrypoint->cfaShouldRevisit = true;
+        entrypoint->cfaHasVisited = false;
+        entrypoint->cfaFoundConstants = false;
+        entrypoint->cfaStructureClobberStateAtHead = StructuresAreWatched;
+        entrypoint->cfaStructureClobberStateAtTail = StructuresAreWatched;
+
+        for (size_t i = 0; i < entrypoint->valuesAtHead.numberOfArguments(); ++i) {
+            entrypoint->valuesAtTail.argument(i).clear();
+
+            FlushFormat format;
+            if (m_graph.m_form == SSA) {
+                // FIXME: When supporting multiple entrypoints in the FTL, we need to change
+                // what we do here: https://bugs.webkit.org/show_bug.cgi?id=175396
+                format = m_graph.m_argumentFormats[i];
+            } else {
+                Node* node = m_graph.m_entrypointToArguments.find(entrypoint)->value[i];
+                if (!node)
+                    format = FlushedJSValue;
+                else {
+                    ASSERT(node->op() == SetArgument);
+                    format = node->variableAccessData()->flushFormat();
+                }
+            }
+            
+            switch (format) {
+            case FlushedInt32:
+                entrypoint->valuesAtHead.argument(i).setType(SpecInt32Only);
+                break;
+            case FlushedBoolean:
+                entrypoint->valuesAtHead.argument(i).setType(SpecBoolean);
+                break;
+            case FlushedCell:
+                entrypoint->valuesAtHead.argument(i).setType(m_graph, SpecCell);
+                break;
+            case FlushedJSValue:
+                entrypoint->valuesAtHead.argument(i).makeBytecodeTop();
+                break;
+            default:
+                DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
+                break;
             }
         }
-        
-        switch (format) {
-        case FlushedInt32:
-            root->valuesAtHead.argument(i).setType(SpecInt32Only);
-            break;
-        case FlushedBoolean:
-            root->valuesAtHead.argument(i).setType(SpecBoolean);
-            break;
-        case FlushedCell:
-            root->valuesAtHead.argument(i).setType(m_graph, SpecCell);
-            break;
-        case FlushedJSValue:
-            root->valuesAtHead.argument(i).makeBytecodeTop();
-            break;
-        default:
-            DFG_CRASH(m_graph, nullptr, "Bad flush format for argument");
-            break;
+        for (size_t i = 0; i < entrypoint->valuesAtHead.numberOfLocals(); ++i) {
+            entrypoint->valuesAtHead.local(i).clear();
+            entrypoint->valuesAtTail.local(i).clear();
         }
     }
-    for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
-        root->valuesAtHead.local(i).clear();
-        root->valuesAtTail.local(i).clear();
-    }
-    for (BlockIndex blockIndex = 1 ; blockIndex < m_graph.numBlocks(); ++blockIndex) {
-        BasicBlock* block = m_graph.block(blockIndex);
-        if (!block)
+
+    for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+        if (m_graph.isEntrypoint(block)) {
+            // We bootstrapped the entrypoints above.
             continue;
+        }
+
         ASSERT(block->isReachable);
         block->cfaShouldRevisit = false;
         block->cfaHasVisited = false;
@@ -364,7 +371,7 @@ inline bool InPlaceAbstractState::mergeToSuccessors(BasicBlock* basicBlock)
             changed |= merge(basicBlock, data->cases[i].target.block);
         return changed;
     }
-        
+
     case Return:
     case TailCall:
     case DirectTailCall:
index f384e44..380570b 100644 (file)
@@ -63,6 +63,7 @@ void JITCode::shrinkToFit()
     common.shrinkToFit();
     osrEntry.shrinkToFit();
     osrExit.shrinkToFit();
+    catchEntrypoints.shrinkToFit();
     speculationRecovery.shrinkToFit();
     minifiedDFG.prepareAndShrink();
     variableEventStream.shrinkToFit();
index 0244e27..2e2ae3b 100644 (file)
@@ -69,6 +69,32 @@ public:
             osrEntry, osrEntry.size(), bytecodeIndex,
             getOSREntryDataBytecodeIndex);
     }
+
+    CatchEntrypointData* catchOSREntryDataForBytecodeIndex(unsigned bytecodeIndex)
+    {
+        return tryBinarySearch<CatchEntrypointData, unsigned>(
+            catchEntrypoints, catchEntrypoints.size(), bytecodeIndex,
+            [] (const CatchEntrypointData* item) { return item->m_bytecodeIndex; });
+    }
+
+    void finalizeCatchOSREntrypoints()
+    {
+        std::sort(catchEntrypoints.begin(), catchEntrypoints.end(), [] (const CatchEntrypointData& a, const CatchEntrypointData& b) {
+            return a.m_bytecodeIndex < b.m_bytecodeIndex;
+        });
+#if !ASSERT_DISABLED
+        unsigned previousIndex = 0;
+        for (const CatchEntrypointData& entrypoint : catchEntrypoints) {
+            ASSERT(previousIndex < entrypoint.m_bytecodeIndex);
+            previousIndex = entrypoint.m_bytecodeIndex;
+        }
+#endif
+    }
+
+    void appendCatchEntrypoint(unsigned bytecodeIndex, unsigned machineCodeOffset, Vector<FlushFormat>&& argumentFormats)
+    {
+        catchEntrypoints.append(CatchEntrypointData { bytecodeIndex, machineCodeOffset, WTFMove(argumentFormats) });
+    }
     
     unsigned appendOSRExit(const OSRExit& exit)
     {
@@ -132,10 +158,13 @@ private:
 public:
     CommonData common;
     Vector<DFG::OSREntryData> osrEntry;
+    Vector<CatchEntrypointData> catchEntrypoints;
     SegmentedVector<DFG::OSRExit, 8> osrExit;
     Vector<DFG::SpeculationRecovery> speculationRecovery;
     DFG::VariableEventStream variableEventStream;
     DFG::MinifiedGraph minifiedDFG;
+    ScratchBuffer* catchOSREntryBuffer;
+
 #if ENABLE(FTL_JIT)
     uint8_t neverExecutedEntry { 1 };
 
index 6d2b187..eb0cbce 100644 (file)
@@ -367,6 +367,8 @@ static void emitStackOverflowCheck(JITCompiler& jit, MacroAssembler::JumpList& s
 
 void JITCompiler::compile()
 {
+    makeCatchOSREntryBuffer();
+
     setStartOfCode();
     compileEntry();
     m_speculative = std::make_unique<SpeculativeJIT>(*this);
@@ -426,6 +428,8 @@ void JITCompiler::compile()
 
 void JITCompiler::compileFunction()
 {
+    makeCatchOSREntryBuffer();
+
     setStartOfCode();
     compileEntry();
 
@@ -551,14 +555,23 @@ void* JITCompiler::addressOfDoubleConstant(Node* node)
 }
 #endif
 
+void JITCompiler::noticeCatchEntrypoint(BasicBlock& basicBlock, JITCompiler::Label blockHead, LinkBuffer& linkBuffer, Vector<FlushFormat>&& argumentFormats)
+{
+    RELEASE_ASSERT(basicBlock.isCatchEntrypoint);
+    RELEASE_ASSERT(basicBlock.intersectionOfCFAHasVisited); // An entrypoint is reachable by definition.
+    m_jitCode->appendCatchEntrypoint(basicBlock.bytecodeBegin, linkBuffer.offsetOf(blockHead), WTFMove(argumentFormats));
+}
+
 void JITCompiler::noticeOSREntry(BasicBlock& basicBlock, JITCompiler::Label blockHead, LinkBuffer& linkBuffer)
 {
+    RELEASE_ASSERT(!basicBlock.isCatchEntrypoint);
+
     // OSR entry is not allowed into blocks deemed unreachable by control flow analysis.
     if (!basicBlock.intersectionOfCFAHasVisited)
         return;
-        
+
     OSREntryData* entry = m_jitCode->appendOSREntryData(basicBlock.bytecodeBegin, linkBuffer.offsetOf(blockHead));
-    
+
     entry->m_expectedValues = basicBlock.intersectionOfPastValuesAtHead;
         
     // Fix the expected values: in our protocol, a dead variable will have an expected
@@ -670,6 +683,14 @@ void JITCompiler::setEndOfCode()
     m_disassembler->setEndOfCode(labelIgnoringWatchpoints());
 }
 
+void JITCompiler::makeCatchOSREntryBuffer()
+{
+    if (m_graph.m_maxLocalsForCatchOSREntry) {
+        uint32_t numberOfLiveLocals = std::max(*m_graph.m_maxLocalsForCatchOSREntry, 1u); // Make sure we always allocate a non-null catchOSREntryBuffer.
+        m_jitCode->catchOSREntryBuffer = vm()->scratchBufferForSize(sizeof(JSValue) * numberOfLiveLocals);
+    }
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index bd4929f..a3a22d6 100644 (file)
@@ -256,6 +256,7 @@ public:
     }
 
     void noticeOSREntry(BasicBlock&, JITCompiler::Label blockHead, LinkBuffer&);
+    void noticeCatchEntrypoint(BasicBlock&, JITCompiler::Label blockHead, LinkBuffer&, Vector<FlushFormat>&& argumentFormats);
     
     RefPtr<JITCode> jitCode() { return m_jitCode; }
     
@@ -284,6 +285,8 @@ private:
 
     void appendExceptionHandlingOSRExit(ExitKind, unsigned eventStreamIndex, CodeOrigin, HandlerInfo* exceptionHandler, CallSiteIndex, MacroAssembler::JumpList jumpsToFail = MacroAssembler::JumpList());
 
+    void makeCatchOSREntryBuffer();
+
     // The dataflow graph currently being generated.
     Graph& m_graph;
 
index f440491..48c4422 100644 (file)
@@ -47,6 +47,8 @@ namespace JSC { namespace DFG {
 
 namespace {
 
+using NaturalLoop = SSANaturalLoop;
+
 struct LoopData {
     LoopData()
         : preHeader(nullptr)
@@ -74,8 +76,8 @@ public:
     {
         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
         
-        m_graph.ensureDominators();
-        m_graph.ensureNaturalLoops();
+        m_graph.ensureSSADominators();
+        m_graph.ensureSSANaturalLoops();
         m_graph.ensureControlEquivalenceAnalysis();
 
         if (verbose) {
@@ -83,7 +85,7 @@ public:
             m_graph.dump();
         }
         
-        m_data.resize(m_graph.m_naturalLoops->numLoops());
+        m_data.resize(m_graph.m_ssaNaturalLoops->numLoops());
         
         // Figure out the set of things each loop writes to, not including blocks that
         // belong to inner loops. We fix this later.
@@ -98,7 +100,7 @@ public:
             if (!block->cfaHasVisited)
                 continue;
             
-            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
+            const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
             if (!loop)
                 continue;
             LoopData& data = m_data[loop->index()];
@@ -116,14 +118,14 @@ public:
         // For each loop:
         // - Identify its pre-header.
         // - Make sure its outer loops know what it clobbers.
-        for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
-            const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
+        for (unsigned loopIndex = m_graph.m_ssaNaturalLoops->numLoops(); loopIndex--;) {
+            const NaturalLoop& loop = m_graph.m_ssaNaturalLoops->loop(loopIndex);
             LoopData& data = m_data[loop.index()];
             
             for (
-                const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
+                const NaturalLoop* outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(loop);
                 outerLoop;
-                outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
+                outerLoop = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*outerLoop))
                 m_data[outerLoop->index()].writes.addAll(data.writes);
             
             BasicBlock* header = loop.header();
@@ -137,7 +139,7 @@ public:
             
             for (unsigned i = header->predecessors.size(); i--;) {
                 BasicBlock* predecessor = header->predecessors[i];
-                if (m_graph.m_dominators->dominates(header, predecessor))
+                if (m_graph.m_ssaDominators->dominates(header, predecessor))
                     continue;
 
                 preHeader = predecessor;
@@ -191,7 +193,7 @@ public:
         Vector<const NaturalLoop*> loopStack;
         bool changed = false;
         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
-            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
+            const NaturalLoop* loop = m_graph.m_ssaNaturalLoops->innerMostLoopOf(block);
             if (!loop)
                 continue;
             
@@ -199,7 +201,7 @@ public:
             for (
                 const NaturalLoop* current = loop;
                 current;
-                current = m_graph.m_naturalLoops->innerMostOuterLoop(*current))
+                current = m_graph.m_ssaNaturalLoops->innerMostOuterLoop(*current))
                 loopStack.append(current);
             
             // Remember: the loop stack has the inner-most loop at index 0, so if we want
@@ -318,7 +320,7 @@ private:
         // because most loops are small and most blocks belong to few loops.
         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
             BasicBlock* subBlock = loop->at(bodyIndex);
-            const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
+            const NaturalLoop* subLoop = m_graph.m_ssaNaturalLoops->headerOf(subBlock);
             if (!subLoop)
                 continue;
             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
index db36999..fa90c3f 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGBasicBlockInlines.h"
+#include "DFGBlockSet.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
 #include "DFGPhase.h"
@@ -46,109 +47,186 @@ public:
 
     bool run()
     {
-        if (!m_graph.m_hasExceptionHandlers)
-            return true;
-
         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == LoadStore);
 
-        m_currentBlockLiveness.resize(m_graph.block(0)->variablesAtTail.numberOfLocals());
+        if (!m_graph.m_hasExceptionHandlers)
+            return false;
 
         InsertionSet insertionSet(m_graph);
-        for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
-            handleBlock(block, insertionSet);
-            insertionSet.execute(block);
+        if (m_graph.m_hasExceptionHandlers) {
+            for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+                handleBlockForTryCatch(block, insertionSet);
+                insertionSet.execute(block);
+            }
         }
 
         return true;
     }
 
-    bool willCatchException(CodeOrigin origin)
+    bool isValidFlushLocation(BasicBlock* startingBlock, unsigned index, VirtualRegister operand)
     {
-        unsigned bytecodeIndexToCheck = origin.bytecodeIndex;
-        m_currentBlockLiveness.clearAll();
-
-        while (1) {
-            InlineCallFrame* inlineCallFrame = origin.inlineCallFrame;
-            CodeBlock* codeBlock = m_graph.baselineCodeBlockFor(inlineCallFrame);
-            if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeIndexToCheck)) {
-                unsigned catchBytecodeIndex = handler->target;
-                m_graph.forAllLocalsLiveInBytecode(CodeOrigin(catchBytecodeIndex, inlineCallFrame), [&] (VirtualRegister operand) {
-                    m_currentBlockLiveness[operand.toLocal()] = true;
-                });
-                return true;
+        // This code is not meant to be fast. We just use it for assertions. If we got liveness wrong,
+        // this function would return false for a Flush that we insert.
+        Vector<BasicBlock*, 4> worklist;
+        BlockSet seen;
+
+        auto addPredecessors = [&] (BasicBlock* block) {
+            for (BasicBlock* block : block->predecessors) {
+                bool isNewEntry = seen.add(block);
+                if (isNewEntry)
+                    worklist.append(block);
+            }
+        };
+
+        auto flushIsDefinitelyInvalid = [&] (BasicBlock* block, unsigned index) {
+            bool allGood = false;
+            for (unsigned i = index; i--; ) {
+                if (block->at(i)->accessesStack(m_graph) && block->at(i)->local() == operand) {
+                    allGood = true;
+                    break;
+                }
             }
 
-            if (!inlineCallFrame)
+            if (allGood)
                 return false;
 
-            bytecodeIndexToCheck = inlineCallFrame->directCaller.bytecodeIndex;
-            origin = inlineCallFrame->directCaller;
-        }
-    }
+            if (block->predecessors.isEmpty()) {
+                // This is a root block. We proved we reached here, therefore we can't Flush, as
+                // it'll make this local live at the start of a root block, which is invalid IR.
+                return true;
+            }
 
-    void handleBlock(BasicBlock* block, InsertionSet& insertionSet)
-    {
-        // Because precise jump targets ensures that the start of a "try" block is its
-        // own basic block, we will never have two "try" statements in the same DFG
-        // basic block. Therefore, checking the first node in the block is sufficient 
-        // to checking if we're in a try block.
-        if (!willCatchException(block->at(0)->origin.semantic))
-            return;
+            addPredecessors(block);
+            return false;
+        };
 
-        Operands<VariableAccessData*> currentBlockAccessData(block->variablesAtTail.numberOfArguments(), block->variablesAtTail.numberOfLocals(), nullptr);
-        HashSet<InlineCallFrame*> seenInlineCallFrames;
+        if (flushIsDefinitelyInvalid(startingBlock, index))
+            return false;
 
-        {
-            for (unsigned i = 0; i < block->size(); i++) {
-                Node* node = block->at(i);
-                bool isPrimordialSetArgument = node->op() == SetArgument && node->local().isArgument() && node == m_graph.m_arguments[node->local().toArgument()];
-                InlineCallFrame* inlineCallFrame = node->origin.semantic.inlineCallFrame;
-                if (inlineCallFrame)
-                    seenInlineCallFrames.add(inlineCallFrame);
-
-                if (node->op() == SetLocal || (node->op() == SetArgument && !isPrimordialSetArgument)) {
-                    VirtualRegister operand = node->local();
+        while (!worklist.isEmpty()) {
+            BasicBlock* block = worklist.takeLast();
+            if (flushIsDefinitelyInvalid(block, block->size()))
+                return false;
+        }
+        return true;
+    }
 
-                    int stackOffset = inlineCallFrame ? inlineCallFrame->stackOffset : 0;
-                    if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()])
-                        || (operand.offset() == stackOffset + CallFrame::thisArgumentOffset())) {
 
-                        VariableAccessData* variableAccessData = currentBlockAccessData.operand(operand);
-                        if (!variableAccessData)
-                            variableAccessData = newVariableAccessData(operand);
+    void handleBlockForTryCatch(BasicBlock* block, InsertionSet& insertionSet)
+    {
+        HandlerInfo* currentExceptionHandler = nullptr;
+        FastBitVector liveAtCatchHead;
+        liveAtCatchHead.resize(m_graph.block(0)->variablesAtTail.numberOfLocals());
+
+        HandlerInfo* cachedHandlerResult;
+        CodeOrigin cachedCodeOrigin;
+        auto catchHandler = [&] (CodeOrigin origin) -> HandlerInfo* {
+            ASSERT(origin);
+            if (origin == cachedCodeOrigin)
+                return cachedHandlerResult;
+
+            unsigned bytecodeIndexToCheck = origin.bytecodeIndex;
+
+            cachedCodeOrigin = origin;
+
+            while (1) {
+                InlineCallFrame* inlineCallFrame = origin.inlineCallFrame;
+                CodeBlock* codeBlock = m_graph.baselineCodeBlockFor(inlineCallFrame);
+                if (HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeIndexToCheck)) {
+                    liveAtCatchHead.clearAll();
+
+                    unsigned catchBytecodeIndex = handler->target;
+                    m_graph.forAllLocalsLiveInBytecode(CodeOrigin(catchBytecodeIndex, inlineCallFrame), [&] (VirtualRegister operand) {
+                        liveAtCatchHead[operand.toLocal()] = true;
+                    });
+
+                    cachedHandlerResult = handler;
+                    break;
+                }
 
-                        insertionSet.insertNode(i, SpecNone, 
-                            Flush, node->origin, OpInfo(variableAccessData));
-                    }
+                if (!inlineCallFrame) {
+                    cachedHandlerResult = nullptr;
+                    break;
                 }
 
-                if (node->accessesStack(m_graph))
-                    currentBlockAccessData.operand(node->local()) = node->variableAccessData();
+                bytecodeIndexToCheck = inlineCallFrame->directCaller.bytecodeIndex;
+                origin = inlineCallFrame->directCaller;
             }
-        }
 
-        // Insert Flush for everything at the end of the block.
-        {
-            NodeOrigin origin = block->at(block->size() - 1)->origin;
-            auto preserveLivenessAtEndOfBlock = [&] (VirtualRegister operand, bool alwaysInsert) {
-                if ((operand.isLocal() && m_currentBlockLiveness[operand.toLocal()]) 
+            return cachedHandlerResult;
+        };
+
+        Operands<VariableAccessData*> currentBlockAccessData(block->variablesAtTail.numberOfArguments(), block->variablesAtTail.numberOfLocals(), nullptr);
+        HashSet<InlineCallFrame*> seenInlineCallFrames;
+
+        auto flushEverything = [&] (NodeOrigin origin, unsigned index) {
+            RELEASE_ASSERT(currentExceptionHandler);
+            auto flush = [&] (VirtualRegister operand, bool alwaysInsert) {
+                if ((operand.isLocal() && liveAtCatchHead[operand.toLocal()]) 
                     || operand.isArgument()
                     || alwaysInsert) {
+
+                    ASSERT(isValidFlushLocation(block, index, operand));
+
                     VariableAccessData* accessData = currentBlockAccessData.operand(operand);
                     if (!accessData)
                         accessData = newVariableAccessData(operand);
 
                     currentBlockAccessData.operand(operand) = accessData;
 
-                    insertionSet.insertNode(block->size(), SpecNone, 
+                    insertionSet.insertNode(index, SpecNone, 
                         Flush, origin, OpInfo(accessData));
                 }
             };
+
             for (unsigned local = 0; local < block->variablesAtTail.numberOfLocals(); local++)
-                preserveLivenessAtEndOfBlock(virtualRegisterForLocal(local), false);
+                flush(virtualRegisterForLocal(local), false);
             for (InlineCallFrame* inlineCallFrame : seenInlineCallFrames)
-                preserveLivenessAtEndOfBlock(VirtualRegister(inlineCallFrame->stackOffset + CallFrame::thisArgumentOffset()), true);
-            preserveLivenessAtEndOfBlock(VirtualRegister(CallFrame::thisArgumentOffset()), true);
+                flush(VirtualRegister(inlineCallFrame->stackOffset + CallFrame::thisArgumentOffset()), true);
+            flush(VirtualRegister(CallFrame::thisArgumentOffset()), true);
+
+            seenInlineCallFrames.clear();
+        };
+
+        for (unsigned nodeIndex = 0; nodeIndex < block->size(); nodeIndex++) {
+            Node* node = block->at(nodeIndex);
+
+            {
+                HandlerInfo* newHandler = catchHandler(node->origin.semantic);
+                if (newHandler != currentExceptionHandler && currentExceptionHandler)
+                    flushEverything(node->origin, nodeIndex);
+                currentExceptionHandler = newHandler;
+            }
+
+            if (currentExceptionHandler && (node->op() == SetLocal || node->op() == SetArgument)) {
+                InlineCallFrame* inlineCallFrame = node->origin.semantic.inlineCallFrame;
+                if (inlineCallFrame)
+                    seenInlineCallFrames.add(inlineCallFrame);
+                VirtualRegister operand = node->local();
+
+                int stackOffset = inlineCallFrame ? inlineCallFrame->stackOffset : 0;
+                if ((operand.isLocal() && liveAtCatchHead[operand.toLocal()])
+                    || operand.isArgument()
+                    || (operand.offset() == stackOffset + CallFrame::thisArgumentOffset())) {
+
+                    ASSERT(isValidFlushLocation(block, nodeIndex, operand));
+
+                    VariableAccessData* variableAccessData = currentBlockAccessData.operand(operand);
+                    if (!variableAccessData)
+                        variableAccessData = newVariableAccessData(operand);
+
+                    insertionSet.insertNode(nodeIndex, SpecNone, 
+                        Flush, node->origin, OpInfo(variableAccessData));
+                }
+            }
+
+            if (node->accessesStack(m_graph))
+                currentBlockAccessData.operand(node->local()) = node->variableAccessData();
+        }
+
+        if (currentExceptionHandler) {
+            NodeOrigin origin = block->at(block->size() - 1)->origin;
+            flushEverything(origin, block->size());
         }
     }
 
@@ -159,8 +237,6 @@ public:
         m_graph.m_variableAccessData.append(VariableAccessData(operand));
         return &m_graph.m_variableAccessData.last();
     }
-
-    FastBitVector m_currentBlockLiveness;
 };
 
 bool performLiveCatchVariablePreservationPhase(Graph& graph)
index d0b3ad4..58b958e 100644 (file)
@@ -41,6 +41,8 @@ namespace JSC { namespace DFG {
 
 BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block)
 {
+    ASSERT_WITH_MESSAGE(!graph.isEntrypoint(block), "An entrypoint should not be in a loop");
+
     // FIXME: If we run this utility on SSA IR, then we may end up with a bizarre arrangement of
     // Upsilons and Phis, like:
     //
@@ -69,7 +71,8 @@ BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, Basic
     // Instead, we use the max of the frequencies of the loop body's non-loop predecessors.
     float frequency = 0;
     for (BasicBlock* predecessor : block->predecessors) {
-        if (graph.m_dominators->dominates(block, predecessor))
+        ASSERT(graph.m_form != SSA);
+        if (graph.m_cpsDominators->dominates(block, predecessor))
             continue;
         frequency = std::max(frequency, predecessor->executionCount);
     }
@@ -103,7 +106,7 @@ BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, Basic
     
     for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
         BasicBlock* predecessor = block->predecessors[predecessorIndex];
-        if (graph.m_dominators->dominates(block, predecessor))
+        if (graph.m_cpsDominators->dominates(block, predecessor))
             continue;
         block->predecessors[predecessorIndex--] = block->predecessors.last();
         block->predecessors.removeLast();
@@ -130,16 +133,16 @@ public:
     
     bool run()
     {
-        m_graph.ensureDominators();
-        m_graph.ensureNaturalLoops();
+        m_graph.ensureCPSDominators();
+        m_graph.ensureCPSNaturalLoops();
         
-        for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
-            const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
-            BasicBlock* existingPreHeader = 0;
+        for (unsigned loopIndex = m_graph.m_cpsNaturalLoops->numLoops(); loopIndex--;) {
+            const CPSNaturalLoop& loop = m_graph.m_cpsNaturalLoops->loop(loopIndex);
+            BasicBlock* existingPreHeader = nullptr;
             bool needsNewPreHeader = false;
-            for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
-                BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
-                if (m_graph.m_dominators->dominates(loop.header(), predecessor))
+            for (unsigned predecessorIndex = loop.header().node()->predecessors.size(); predecessorIndex--;) {
+                BasicBlock* predecessor = loop.header().node()->predecessors[predecessorIndex];
+                if (m_graph.m_cpsDominators->dominates(loop.header().node(), predecessor))
                     continue;
                 if (!existingPreHeader) {
                     existingPreHeader = predecessor;
@@ -165,14 +168,14 @@ public:
             // A pre-header is most useful if it's possible to exit from its terminal. Hence
             // if the terminal of the existing pre-header doesn't allow for exit, but the first
             // origin of the loop header does, then we should create a new pre-header.
-            if (!needsNewPreHeader && loop.header()->at(0)->origin.exitOK
+            if (!needsNewPreHeader && loop.header().node()->at(0)->origin.exitOK
                 && !existingPreHeader->terminal()->origin.exitOK)
                 needsNewPreHeader = true;
             
             if (!needsNewPreHeader)
                 continue;
             
-            createPreHeader(m_graph, m_insertionSet, loop.header());
+            createPreHeader(m_graph, m_insertionSet, loop.header().node());
         }
         
         return m_insertionSet.execute();
index 65e5186..f966e43 100644 (file)
@@ -53,8 +53,10 @@ public:
             insertionSet.execute(block);
         }
 
-        treatRootBlock(m_graph.block(0), insertionSet);
-        insertionSet.execute(m_graph.block(0));
+        for (BasicBlock* entrypoint : m_graph.m_entrypoints) {
+            treatRootBlock(entrypoint, insertionSet);
+            insertionSet.execute(entrypoint);
+        }
 
         return true;
     }
@@ -67,7 +69,13 @@ public:
         {
             for (unsigned i = 0; i < block->size(); i++) {
                 Node* node = block->at(i);
-                bool isPrimordialSetArgument = node->op() == SetArgument && node->local().isArgument() && node == m_graph.m_arguments[node->local().toArgument()];
+                bool isPrimordialSetArgument = false;
+                if (node->op() == SetArgument && node->local().isArgument()) {
+                    auto iter = m_graph.m_entrypointToArguments.find(block);
+                    if (iter != m_graph.m_entrypointToArguments.end())
+                        isPrimordialSetArgument = node == iter->value[node->local().toArgument()];
+                }
+
                 if (node->op() == SetLocal || (node->op() == SetArgument && !isPrimordialSetArgument)) {
                     VirtualRegister operand = node->local();
                     VariableAccessData* flushAccessData = currentBlockAccessData.operand(operand);
@@ -128,12 +136,12 @@ public:
 
         for (unsigned i = 0; i < block->variablesAtTail.numberOfLocals(); i++) {
             VirtualRegister operand = virtualRegisterForLocal(i);
-            VariableAccessData* accessData;
             DFG_ASSERT(m_graph, nullptr, initialAccessNodes.operand(operand)->op() == Flush); // We should have inserted a Flush before any SetLocal/SetArgument for the local that we are analyzing now.
-            accessData = initialAccessData.operand(operand);
+            VariableAccessData* accessData = initialAccessData.operand(operand);
             DFG_ASSERT(m_graph, nullptr, accessData);
             insertionSet.insertNode(0, SpecNone, 
                 SetLocal, origin, OpInfo(accessData), Edge(undefined));
+            accessData->mergeShouldNeverUnbox(true); // We don't know if we can exit here.
         }
     }
 
index 45a1ccb..6b299eb 100644 (file)
@@ -84,6 +84,7 @@ ExitMode mayExitImpl(Graph& graph, Node* node, StateType& state)
     case Int52Rep:
     case ValueRep:
     case ExtractOSREntryLocal:
+    case ExtractCatchLocal:
     case LogicalNot:
     case NotifyWrite:
     case PutStructure:
index f7c532a..1029918 100644 (file)
 
 namespace JSC { namespace DFG {
 
-typedef WTF::NaturalLoop<CFG> NaturalLoop;
-
-class NaturalLoops : public WTF::NaturalLoops<CFG> {
+template <typename CFGKind>
+class NaturalLoops : public WTF::NaturalLoops<CFGKind> {
     WTF_MAKE_NONCOPYABLE(NaturalLoops);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     NaturalLoops(Graph& graph)
-        : WTF::NaturalLoops<CFG>(*graph.m_cfg, graph.ensureDominators(), validationEnabled())
+        : WTF::NaturalLoops<CFGKind>(selectCFG<CFGKind>(graph), ensureDominatorsForCFG<CFGKind>(graph), validationEnabled())
     {
     }
 };
 
+using SSANaturalLoop = WTF::NaturalLoop<SSACFG>;
+using CPSNaturalLoop = WTF::NaturalLoop<CPSCFG>;
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index cf4cb04..e70db96 100644 (file)
@@ -1292,7 +1292,7 @@ public:
         return op() == Branch;
     }
     
-    bool isSwitch()
+    bool isSwitch() const
     {
         return op() == Switch;
     }
@@ -1387,6 +1387,7 @@ public:
             RELEASE_ASSERT(index == switchData()->cases.size());
             return switchData()->fallThrough.block;
         }
+
         switch (index) {
         case 0:
             if (isJump())
@@ -1558,6 +1559,18 @@ public:
         ASSERT(op() == IdentityWithProfile);
         return m_opInfo.as<SpeculatedType>();
     }
+
+    uint32_t catchOSREntryIndex() const
+    {
+        ASSERT(op() == ExtractCatchLocal);
+        return m_opInfo.as<uint32_t>();
+    }
+
+    SpeculatedType catchLocalPrediction()
+    {
+        ASSERT(op() == ExtractCatchLocal);
+        return m_opInfo2.as<SpeculatedType>();
+    }
     
     bool hasCellOperand()
     {
@@ -1957,7 +1970,7 @@ public:
     {
         return m_virtualRegister.isValid();
     }
-    
+
     VirtualRegister virtualRegister()
     {
         ASSERT(hasResult());
index 867a92c..68fd6f8 100644 (file)
@@ -92,6 +92,7 @@ namespace JSC { namespace DFG {
     /* Special node for OSR entry into the FTL. Indicates that we're loading a local */\
     /* variable from the scratch buffer. */\
     macro(ExtractOSREntryLocal, NodeResultJS) \
+    macro(ExtractCatchLocal, NodeResultJS) \
     \
     /* Tier-up checks from the DFG to the FTL. */\
     macro(CheckTierUpInLoop, NodeMustGenerate) \
index 1818b4d..00134d8 100644 (file)
@@ -32,6 +32,7 @@
 #include "CodeBlock.h"
 #include "DFGJITCode.h"
 #include "DFGNode.h"
+#include "InterpreterInlines.h"
 #include "JIT.h"
 #include "JSCInlines.h"
 #include "VMInlines.h"
@@ -336,6 +337,71 @@ void* prepareOSREntry(ExecState* exec, CodeBlock* codeBlock, unsigned bytecodeIn
     return scratch;
 }
 
+void* prepareCatchOSREntry(ExecState* exec, CodeBlock* codeBlock, unsigned bytecodeIndex)
+{
+    if (!Options::useOSREntryToDFG())
+        return nullptr;
+
+    VM& vm = exec->vm();
+    ASSERT(codeBlock->jitType() == JITCode::DFGJIT);
+    DFG::JITCode* jitCode = codeBlock->jitCode()->dfg();
+    RELEASE_ASSERT(jitCode);
+
+    DFG::CatchEntrypointData* catchEntrypoint = jitCode->catchOSREntryDataForBytecodeIndex(bytecodeIndex);
+    if (!catchEntrypoint) {
+        // This can be null under some circumstances. The most common is that we didn't
+        // compile this op_catch as an entrypoint since it had never executed when starting
+        // the compilation.
+        return nullptr;
+    }
+
+    // We're only allowed to OSR enter if we've proven we have compatible argument types.
+    for (unsigned argument = 0; argument < catchEntrypoint->m_argumentFormats.size(); ++argument) {
+        JSValue value = exec->uncheckedR(virtualRegisterForArgument(argument)).jsValue();
+        switch (catchEntrypoint->m_argumentFormats[argument]) {
+        case DFG::FlushedInt32:
+            if (!value.isInt32())
+                return nullptr;
+            break;
+        case DFG::FlushedCell:
+            if (!value.isCell())
+                return nullptr;
+            break;
+        case DFG::FlushedBoolean:
+            if (!value.isBoolean())
+                return nullptr;
+            break;
+        case DFG::DeadFlush:
+            // This means the argument is not alive. Therefore, it's allowed to be any type.
+            break;
+        case DFG::FlushedJSValue:
+            // An argument is trivially a JSValue.
+            break; 
+        default:
+            RELEASE_ASSERT_NOT_REACHED();
+        }
+    }
+
+    unsigned frameSizeForCheck = jitCode->common.requiredRegisterCountForExecutionAndExit();
+    if (UNLIKELY(!vm.ensureStackCapacityFor(&exec->registers()[virtualRegisterForLocal(frameSizeForCheck).offset()])))
+        return nullptr;
+
+    ASSERT(Interpreter::getOpcodeID(exec->codeBlock()->instructions()[exec->bytecodeOffset()].u.opcode) == op_catch);
+    ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(exec->codeBlock()->instructions()[exec->bytecodeOffset() + 3].u.pointer);
+    JSValue* dataBuffer = reinterpret_cast<JSValue*>(jitCode->catchOSREntryBuffer->dataBuffer());
+    unsigned index = 0;
+    buffer->forEach([&] (ValueProfileAndOperand& profile) {
+        if (!VirtualRegister(profile.m_operand).isLocal())
+            return;
+        dataBuffer[index] = exec->uncheckedR(profile.m_operand).jsValue();
+        ++index;
+    });
+
+    jitCode->catchOSREntryBuffer->setActiveLength(sizeof(JSValue) * index);
+
+    return jitCode->executableAddressAtOffset(catchEntrypoint->m_machineCodeOffset);
+}
+
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
index 41a9330..712592c 100644 (file)
@@ -26,6 +26,7 @@
 #pragma once
 
 #include "DFGAbstractValue.h"
+#include "DFGFlushFormat.h"
 #include "Operands.h"
 #include <wtf/BitVector.h>
 
@@ -69,9 +70,20 @@ inline unsigned getOSREntryDataBytecodeIndex(OSREntryData* osrEntryData)
     return osrEntryData->m_bytecodeIndex;
 }
 
+struct CatchEntrypointData {
+    unsigned m_bytecodeIndex;
+    unsigned m_machineCodeOffset;
+    // We use this when doing OSR entry at catch. We prove the arguments
+    // are of the expected type before entering at a catch block.
+    Vector<FlushFormat> m_argumentFormats;
+};
+
 // Returns a pointer to a data buffer that the OSR entry thunk will recognize and
 // parse. If this returns null, it means 
 void* prepareOSREntry(ExecState*, CodeBlock*, unsigned bytecodeIndex);
+
+// If null is returned, we can't OSR enter. If it's not null, it's the PC to jump to.
+void* prepareCatchOSREntry(ExecState*, CodeBlock*, unsigned bytecodeIndex);
 #else
 inline void* prepareOSREntry(ExecState*, CodeBlock*, unsigned) { return 0; }
 #endif
index 5d22edd..d16965b 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "DFGBasicBlockInlines.h"
 #include "DFGBlockInsertionSet.h"
+#include "DFGCFG.h"
 #include "DFGGraph.h"
 #include "DFGLoopPreHeaderCreationPhase.h"
 #include "DFGPhase.h"
@@ -54,7 +55,7 @@ public:
         RELEASE_ASSERT(bytecodeIndex != UINT_MAX);
         
         // Needed by createPreHeader().
-        m_graph.ensureDominators();
+        m_graph.ensureCPSDominators();
         
         CodeBlock* baseline = m_graph.m_profiledBlock;
         
@@ -112,16 +113,17 @@ public:
         // type checks to here.
         origin = target->at(0)->origin;
         
+        ArgumentsVector newArguments = m_graph.m_entrypointToArguments.find(m_graph.block(0))->value;
         for (int argument = 0; argument < baseline->numParameters(); ++argument) {
             Node* oldNode = target->variablesAtHead.argument(argument);
             if (!oldNode) {
                 // Just for sanity, always have a SetArgument even if it's not needed.
-                oldNode = m_graph.m_arguments[argument];
+                oldNode = newArguments[argument];
             }
             Node* node = newRoot->appendNode(
                 m_graph, SpecNone, SetArgument, origin,
                 OpInfo(oldNode->variableAccessData()));
-            m_graph.m_arguments[argument] = node;
+            newArguments[argument] = node;
         }
 
         for (int local = 0; local < baseline->m_numCalleeLocals; ++local) {
@@ -139,8 +141,17 @@ public:
             OpInfo(createPreHeader(m_graph, insertionSet, target)));
         
         insertionSet.execute();
+
+        RELEASE_ASSERT(m_graph.m_entrypoints.size() == 1);
+        m_graph.m_entrypoints[0] = newRoot;
+        m_graph.m_entrypointToArguments.clear();
+        m_graph.m_entrypointToArguments.add(newRoot, newArguments);
+
+        m_graph.m_cpsCFG = std::make_unique<CPSCFG>(m_graph);
+
         m_graph.resetReachability();
         m_graph.killUnreachableBlocks();
+
         return true;
     }
 };
index f76ccb8..6b94902 100644 (file)
@@ -39,10 +39,15 @@ namespace JSC { namespace DFG {
 
 void handleExitCounts(CCallHelpers& jit, const OSRExitBase& exit)
 {
-    jit.add32(AssemblyHelpers::TrustedImm32(1), AssemblyHelpers::AbsoluteAddress(&exit.m_count));
-
-    if (!exitKindMayJettison(exit.m_kind))
+    if (!exitKindMayJettison(exit.m_kind)) {
+        // FIXME: We may want to notice that we're frequently exiting
+        // at an op_catch that we didn't compile an entrypoint for, and
+        // then trigger a reoptimization of this CodeBlock:
+        // https://bugs.webkit.org/show_bug.cgi?id=175842
         return;
+    }
+
+    jit.add32(AssemblyHelpers::TrustedImm32(1), AssemblyHelpers::AbsoluteAddress(&exit.m_count));
     
     jit.move(AssemblyHelpers::TrustedImmPtr(jit.codeBlock()), GPRInfo::regT0);
     
index 3aad0e2..505597e 100644 (file)
@@ -730,7 +730,7 @@ private:
     {
         m_graph.computeRefCounts();
         m_graph.initializeNodeOwners();
-        m_graph.ensureDominators();
+        m_graph.ensureSSADominators();
         performLivenessAnalysis(m_graph);
         performOSRAvailabilityAnalysis(m_graph);
         m_combinedLiveness = CombinedLiveness(m_graph);
index a242998..f517fe9 100644 (file)
@@ -366,9 +366,8 @@ Plan::CompilationPath Plan::compileInThreadImpl()
     // If we're doing validation, then run some analyses, to give them an opportunity
     // to self-validate. Now is as good a time as any to do this.
     if (validationEnabled()) {
-        dfg.ensureDominators();
-        dfg.ensureNaturalLoops();
-        dfg.ensurePrePostNumbering();
+        dfg.ensureCPSDominators();
+        dfg.ensureCPSNaturalLoops();
     }
 
     switch (mode) {
index 4b79231..e69de29 100644 (file)
@@ -1,88 +0,0 @@
-/*
- * Copyright (C) 2014 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 "DFGPrePostNumbering.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBlockMapInlines.h"
-#include "DFGBlockWorklist.h"
-#include "DFGGraph.h"
-
-namespace JSC { namespace DFG {
-
-PrePostNumbering::PrePostNumbering(Graph& graph)
-{
-    m_map = BlockMap<Numbering>(graph);
-    
-    PostOrderBlockWorklist worklist;
-    worklist.push(graph.block(0));
-    unsigned nextPreNumber = 0;
-    unsigned nextPostNumber = 0;
-    while (BlockWithOrder item = worklist.pop()) {
-        switch (item.order) {
-        case VisitOrder::Pre:
-            m_map[item.node].m_preNumber = nextPreNumber++;
-            worklist.pushPost(item.node);
-            for (BasicBlock* successor : item.node->successors())
-                worklist.push(successor);
-            break;
-        case VisitOrder::Post:
-            m_map[item.node].m_postNumber = nextPostNumber++;
-            break;
-        }
-    }
-}
-
-PrePostNumbering::~PrePostNumbering() { }
-
-} } // namespace JSC::DFG
-
-namespace WTF {
-
-using namespace JSC::DFG;
-
-void printInternal(PrintStream& out, EdgeKind kind)
-{
-    switch (kind) {
-    case ForwardEdge:
-        out.print("ForwardEdge");
-        return;
-    case CrossEdge:
-        out.print("CrossEdge");
-        return;
-    case BackEdge:
-        out.print("BackEdge");
-        return;
-    }
-    
-    RELEASE_ASSERT_NOT_REACHED();
-}
-
-} // namespace WTF
-
-#endif // ENABLE(DFG_JIT)
-
index 64efdac..e69de29 100644 (file)
@@ -1,105 +0,0 @@
-/*
- * Copyright (C) 2014 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. 
- */
-
-#pragma once
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBasicBlock.h"
-#include "DFGBlockMap.h"
-#include <wtf/FastMalloc.h>
-#include <wtf/Noncopyable.h>
-
-namespace JSC { namespace DFG {
-
-enum EdgeKind {
-    ForwardEdge,
-    CrossEdge,
-    BackEdge
-};
-
-class PrePostNumbering {
-    WTF_MAKE_NONCOPYABLE(PrePostNumbering);
-    WTF_MAKE_FAST_ALLOCATED;
-public:
-    PrePostNumbering(Graph&);
-    ~PrePostNumbering();
-
-    unsigned preNumber(BasicBlock* block) const { return m_map[block].m_preNumber; }
-    unsigned postNumber(BasicBlock* block) const { return m_map[block].m_postNumber; }
-    
-    // Is from a strict ancestor of to?
-    bool isStrictAncestorOf(BasicBlock* from, BasicBlock* to) const
-    {
-        return preNumber(from) < preNumber(to)
-            && postNumber(from) > postNumber(to);
-    }
-    
-    bool isAncestorOf(BasicBlock* from, BasicBlock* to) const
-    {
-        return from == to || isStrictAncestorOf(from, to);
-    }
-    
-    bool isStrictDescendantOf(BasicBlock* from, BasicBlock* to) const
-    {
-        return isStrictAncestorOf(to, from);
-    }
-    
-    bool isDescendantOf(BasicBlock* from, BasicBlock* to) const
-    {
-        return isAncestorOf(to, from);
-    }
-    
-    // This will give a bogus answer if there is actually no such edge. If you want to determine
-    // if there is any such edge, you have to do it yourself.
-    EdgeKind edgeKind(BasicBlock* from, BasicBlock* to) const
-    {
-        if (isStrictDescendantOf(to, from))
-            return ForwardEdge;
-        
-        if (isAncestorOf(to, from))
-            return BackEdge;
-        
-        return CrossEdge;
-    }
-    
-private:
-    struct Numbering {
-        unsigned m_preNumber;
-        unsigned m_postNumber;
-    };
-
-    BlockMap<Numbering> m_map;
-};
-
-} } // namespace JSC::DFG
-
-namespace WTF {
-
-void printInternal(PrintStream&, JSC::DFG::EdgeKind);
-
-} // namespace WTF
-
-#endif // ENABLE(DFG_JIT)
index b00ad6d..811dec0 100644 (file)
@@ -51,9 +51,13 @@ public:
         {
             ConcurrentJSLocker locker(profiledBlock()->m_lock);
             
+            // We only do this for the arguments at the first block. The arguments from
+            // other entrypoints have already been populated with their predictions.
+            auto& arguments = m_graph.m_entrypointToArguments.find(m_graph.block(0))->value;
+
             for (size_t arg = 0; arg < static_cast<size_t>(codeBlock()->numParameters()); ++arg) {
                 ValueProfile& profile = profiledBlock()->valueProfileForArgument(arg);
-                m_graph.m_arguments[arg]->variableAccessData()->predict(
+                arguments[arg]->variableAccessData()->predict(
                     profile.computeUpdatedPrediction(locker));
             }
         }
index 891d5e0..5b0b9ef 100644 (file)
@@ -995,6 +995,11 @@ private:
             break;
         }
 
+        case ExtractCatchLocal: {
+            setPrediction(m_currentNode->catchLocalPrediction());
+            break;
+        }
+
         case GetLocal:
         case SetLocal:
         case UInt32ToNumber:
index ac37127..d3da552 100644 (file)
@@ -76,7 +76,7 @@ public:
             m_graph.dump();
         }
 
-        m_graph.ensureDominators();
+        m_graph.ensureSSADominators();
         
         SSACalculator ssaCalculator(m_graph);
         InsertionSet insertionSet(m_graph);
index 899fa15..34c427b 100644 (file)
@@ -95,12 +95,12 @@ SSACalculator::Def* SSACalculator::newDef(Variable* variable, BasicBlock* block,
 
 SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
 {
-    return reachingDefAtTail(m_graph.m_dominators->idom(block), variable);
+    return reachingDefAtTail(m_graph.m_ssaDominators->idom(block), variable);
 }
 
 SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
 {
-    for (; block; block = m_graph.m_dominators->idom(block)) {
+    for (; block; block = m_graph.m_ssaDominators->idom(block)) {
         if (Def* def = m_data[block].m_defs.get(variable))
             return def;
     }
index 1493b05..a25b001 100644 (file)
@@ -175,10 +175,10 @@ public:
     template<typename PhiInsertionFunctor>
     void computePhis(const PhiInsertionFunctor& functor)
     {
-        DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators);
+        DFG_ASSERT(m_graph, nullptr, m_graph.m_ssaDominators);
         
         for (Variable& variable : m_variables) {
-            m_graph.m_dominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
+            m_graph.m_ssaDominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
                 variable.m_blocksWithDefs,
                 [&] (BasicBlock* block) -> bool {
                     Node* phiNode = functor(&variable, block);
index cde0740..9dea858 100644 (file)
@@ -54,7 +54,8 @@ public:
         RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
         
         m_graph.clearReplacements();
-        m_graph.ensureDominators();
+        m_graph.clearCPSCFGData();
+        m_graph.ensureSSADominators();
         
         if (verbose) {
             dataLog("Graph before SSA transformation:\n");
@@ -110,7 +111,7 @@ public:
         }
         
         // Decide where Phis are to be inserted. This creates the Phi's but doesn't insert them
-        // yet. We will later know where to insert them because SSACalculator is such a bro.
+        // yet. We will later know where to insert based on where SSACalculator tells us to.
         m_calculator.computePhis(
             [&] (SSACalculator::Variable* ssaVariable, BasicBlock* block) -> Node* {
                 VariableAccessData* variable = m_variableForSSAIndex[ssaVariable->index()];
@@ -381,18 +382,22 @@ public:
             block->valuesAtHead.clear();
             block->ssa = std::make_unique<BasicBlock::SSAData>(block);
         }
-        
-        m_graph.m_argumentFormats.resize(m_graph.m_arguments.size());
-        for (unsigned i = m_graph.m_arguments.size(); i--;) {
+
+        // FIXME: Support multiple entrypoints in DFG SSA:
+        // https://bugs.webkit.org/show_bug.cgi?id=175396
+        RELEASE_ASSERT(m_graph.m_entrypoints.size() == 1);
+        auto& arguments = m_graph.m_entrypointToArguments.find(m_graph.block(0))->value;
+        m_graph.m_argumentFormats.resize(arguments.size());
+        for (unsigned i = arguments.size(); i--;) {
             FlushFormat format = FlushedJSValue;
 
-            Node* node = m_argumentMapping.get(m_graph.m_arguments[i]);
+            Node* node = m_argumentMapping.get(arguments[i]);
             
             RELEASE_ASSERT(node);
             format = node->stackAccessData()->format;
             
             m_graph.m_argumentFormats[i] = format;
-            m_graph.m_arguments[i] = node; // Record the load that loads the arguments for the benefit of exit profiling.
+            arguments[i] = node; // Record the load that loads the arguments for the benefit of exit profiling.
         }
         
         m_graph.m_form = SSA;
@@ -416,7 +421,12 @@ private:
 
 bool performSSAConversion(Graph& graph)
 {
-    return runPhase<SSAConversionPhase>(graph);
+    RELEASE_ASSERT(!graph.m_isInSSAConversion);
+    graph.m_isInSSAConversion = true;
+    bool result = runPhase<SSAConversionPhase>(graph);
+    RELEASE_ASSERT(graph.m_isInSSAConversion);
+    graph.m_isInSSAConversion = false;
+    return result;
 }
 
 } } // namespace JSC::DFG
index 1bdc59e..ad76b33 100644 (file)
@@ -326,6 +326,7 @@ bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
     case NewTypedArray:
     case Unreachable:
     case ExtractOSREntryLocal:
+    case ExtractCatchLocal:
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
     case CheckTierUpAndOSREnter:
index 7c2c86b..a157711 100644 (file)
@@ -1707,6 +1707,13 @@ void SpeculativeJIT::compileCurrentBlock()
         return;
     }
 
+    if (m_block->isCatchEntrypoint) {
+        m_jit.addPtr(CCallHelpers::TrustedImm32(m_jit.graph().stackPointerOffset() * sizeof(Register)), GPRInfo::callFrameRegister,  CCallHelpers::stackPointerRegister);
+        m_jit.emitSaveCalleeSaves();
+        m_jit.emitMaterializeTagCheckRegisters();
+        m_jit.emitPutToCallFrameHeader(m_jit.codeBlock(), CallFrameSlot::codeBlock);
+    }
+
     m_stream->appendAndLog(VariableEvent::reset());
     
     m_jit.jitAssertHasValidCallFrame();
@@ -1801,8 +1808,9 @@ void SpeculativeJIT::checkArgumentTypes()
     ASSERT(!m_currentNode);
     m_origin = NodeOrigin(CodeOrigin(0), CodeOrigin(0), true);
 
+    auto& arguments = m_jit.graph().m_entrypointToArguments.find(m_jit.graph().block(0))->value;
     for (int i = 0; i < m_jit.codeBlock()->numParameters(); ++i) {
-        Node* node = m_jit.graph().m_arguments[i];
+        Node* node = arguments[i];
         if (!node) {
             // The argument is dead. We don't do any checks for such arguments.
             continue;
@@ -1886,12 +1894,11 @@ void SpeculativeJIT::createOSREntries()
         BasicBlock* block = m_jit.graph().block(blockIndex);
         if (!block)
             continue;
-        if (!block->isOSRTarget)
-            continue;
-        
-        // Currently we don't have OSR entry trampolines. We could add them
-        // here if need be.
-        m_osrEntryHeads.append(m_jit.blockHeads()[blockIndex]);
+        if (block->isOSRTarget || block->isCatchEntrypoint) {
+            // Currently we don't have OSR entry trampolines. We could add them
+            // here if need be.
+            m_osrEntryHeads.append(m_jit.blockHeads()[blockIndex]);
+        }
     }
 }
 
@@ -1902,10 +1909,29 @@ void SpeculativeJIT::linkOSREntries(LinkBuffer& linkBuffer)
         BasicBlock* block = m_jit.graph().block(blockIndex);
         if (!block)
             continue;
-        if (!block->isOSRTarget)
+        if (!block->isOSRTarget && !block->isCatchEntrypoint)
             continue;
-        m_jit.noticeOSREntry(*block, m_osrEntryHeads[osrEntryIndex++], linkBuffer);
+        if (block->isCatchEntrypoint) {
+            auto& argumentsVector = m_jit.graph().m_entrypointToArguments.find(block)->value;
+            Vector<FlushFormat> argumentFormats;
+            argumentFormats.reserveInitialCapacity(argumentsVector.size());
+            for (Node* setArgument : argumentsVector) {
+                if (setArgument) {
+                    FlushFormat flushFormat = setArgument->variableAccessData()->flushFormat();
+                    ASSERT(flushFormat == FlushedInt32 || flushFormat == FlushedCell || flushFormat == FlushedBoolean || flushFormat == FlushedJSValue);
+                    argumentFormats.uncheckedAppend(flushFormat);
+                } else
+                    argumentFormats.uncheckedAppend(DeadFlush);
+            }
+            m_jit.noticeCatchEntrypoint(*block, m_osrEntryHeads[osrEntryIndex++], linkBuffer, WTFMove(argumentFormats));
+        } else {
+            ASSERT(block->isOSRTarget);
+            m_jit.noticeOSREntry(*block, m_osrEntryHeads[osrEntryIndex++], linkBuffer);
+        }
     }
+
+    m_jit.jitCode()->finalizeCatchOSREntrypoints();
+
     ASSERT(osrEntryIndex == m_osrEntryHeads.size());
     
     if (verboseCompilationEnabled()) {
index 1031652..35449e3 100644 (file)
@@ -5634,6 +5634,23 @@ void SpeculativeJIT::compile(Node* node)
         unreachable(node);
         break;
 
+    case ExtractCatchLocal: {
+        GPRTemporary temp(this);
+        GPRTemporary tag(this);
+        GPRTemporary payload(this);
+
+        GPRReg tempGPR = temp.gpr();
+        GPRReg tagGPR = tag.gpr();
+        GPRReg payloadGPR = payload.gpr();
+
+        JSValue* ptr = &reinterpret_cast<JSValue*>(m_jit.jitCode()->catchOSREntryBuffer->dataBuffer())[node->catchOSREntryIndex()];
+        m_jit.move(CCallHelpers::TrustedImmPtr(ptr), tempGPR);
+        m_jit.load32(CCallHelpers::Address(tempGPR, TagOffset), tagGPR);
+        m_jit.load32(CCallHelpers::Address(tempGPR, PayloadOffset), payloadGPR);
+        jsValueResult(tagGPR, payloadGPR, node);
+        break;
+    }
+
     case LastNodeType:
     case Phi:
     case Upsilon:
index 8326241..d4c3834 100644 (file)
@@ -5998,6 +5998,16 @@ void SpeculativeJIT::compile(Node* node)
         compileCheckSubClass(node);
         break;
 
+    case ExtractCatchLocal: {
+        JSValue* ptr = &reinterpret_cast<JSValue*>(m_jit.jitCode()->catchOSREntryBuffer->dataBuffer())[node->catchOSREntryIndex()];
+        GPRTemporary temp(this);
+        GPRReg tempGPR = temp.gpr();
+        m_jit.move(CCallHelpers::TrustedImmPtr(ptr), tempGPR);
+        m_jit.load64(CCallHelpers::Address(tempGPR), tempGPR);
+        jsValueResult(tempGPR, node);
+        break;
+    }
+
 #if ENABLE(FTL_JIT)        
     case CheckTierUpInLoop: {
         MacroAssembler::Jump callTierUp = m_jit.branchAdd32(
@@ -6086,6 +6096,7 @@ void SpeculativeJIT::compile(Node* node)
         });
         break;
     }
+
 #else // ENABLE(FTL_JIT)
     case CheckTierUpInLoop:
     case CheckTierUpAtReturn:
index b6e35cf..5a104af 100644 (file)
@@ -45,7 +45,7 @@ public:
     
     bool run()
     {
-        m_graph.ensureNaturalLoops();
+        m_graph.ensureCPSNaturalLoops();
         
         // Estimate basic block execution counts based on loop depth.
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
@@ -53,7 +53,7 @@ public:
             if (!block)
                 continue;
 
-            block->executionCount = pow(10, m_graph.m_naturalLoops->loopDepth(block));
+            block->executionCount = pow(10, m_graph.m_cpsNaturalLoops->loopDepth(block));
         }
         
         // Estimate branch weights based on execution counts. This isn't quite correct. It'll
@@ -80,7 +80,7 @@ public:
                 applyCounts(data->fallThrough);
                 break;
             }
-                
+
             default:
                 break;
             }
index 95ae19b..65afb4a 100644 (file)
@@ -268,18 +268,27 @@ private:
             
         case Flush: {
             ASSERT(m_graph.m_form != SSA);
+
+            if (m_graph.willCatchExceptionInMachineFrame(m_node->origin.semantic)) {
+                // FIXME: We should be able to relax this:
+                // https://bugs.webkit.org/show_bug.cgi?id=150824
+                break;
+            }
             
             Node* setLocal = nullptr;
             VirtualRegister local = m_node->local();
             
             for (unsigned i = m_nodeIndex; i--;) {
                 Node* node = m_block->at(i);
+
                 if (node->op() == SetLocal && node->local() == local) {
                     setLocal = node;
                     break;
                 }
+
                 if (accessesOverlap(m_graph, node, AbstractHeap(Stack, local)))
                     break;
+
             }
             
             if (!setLocal)
index 0a3cb9e..03af5d9 100644 (file)
@@ -50,6 +50,8 @@ static FunctionWhitelist& ensureGlobalFTLWhitelist()
     return ftlWhitelist;
 }
 
+using NaturalLoop = CPSNaturalLoop;
+
 class TierUpCheckInjectionPhase : public Phase {
 public:
     TierUpCheckInjectionPhase(Graph& graph)
@@ -81,8 +83,8 @@ public:
         if (!Options::useOSREntryToFTL())
             level = FTL::CanCompile;
         
-        m_graph.ensureNaturalLoops();
-        NaturalLoops& naturalLoops = *m_graph.m_naturalLoops;
+        m_graph.ensureCPSNaturalLoops();
+        CPSNaturalLoops& naturalLoops = *m_graph.m_cpsNaturalLoops;
         HashMap<const NaturalLoop*, unsigned> naturalLoopToLoopHint = buildNaturalLoopToLoopHintMap(naturalLoops);
 
         HashMap<unsigned, LoopHintDescriptor> tierUpHierarchy;
@@ -182,7 +184,7 @@ private:
         return true;
     }
 
-    HashMap<const NaturalLoop*, unsigned> buildNaturalLoopToLoopHintMap(const NaturalLoops& naturalLoops)
+    HashMap<const NaturalLoop*, unsigned> buildNaturalLoopToLoopHintMap(const CPSNaturalLoops& naturalLoops)
     {
         HashMap<const NaturalLoop*, unsigned> naturalLoopsToLoopHint;
 
index 39fe710..31f0dd5 100644 (file)
@@ -134,10 +134,11 @@ public:
                     if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid)
                         break;
 
-                    // Currently we should only be doing this hoisting for SetArguments at the prologue.
-                    ASSERT(!blockIndex);
+                    // Currently we should only be doing this hoisting for SetArguments at an entrypoint.
+                    ASSERT(m_graph.isEntrypoint(block));
 
                     NodeOrigin origin = node->origin;
+                    RELEASE_ASSERT(origin.exitOK);
                     
                     Node* getLocal = insertionSet.insertNode(
                         indexInBlock + 1, variable->prediction(), GetLocal, origin,
index 68afd24..1bc1da6 100644 (file)
@@ -83,10 +83,13 @@ public:
         // NB. This code is not written for performance, since it is not intended to run
         // in release builds.
 
-        // Validate that all local variables at the head of the root block are dead.
-        BasicBlock* root = m_graph.block(0);
-        for (unsigned i = 0; i < root->variablesAtHead.numberOfLocals(); ++i)
-            V_EQUAL((virtualRegisterForLocal(i), root), static_cast<Node*>(0), root->variablesAtHead.local(i));
+        VALIDATE((m_graph.block(0)), m_graph.isEntrypoint(m_graph.block(0)));
+
+        // Validate that all local variables at the head of all entrypoints are dead.
+        for (BasicBlock* entrypoint : m_graph.m_entrypoints) {
+            for (unsigned i = 0; i < entrypoint->variablesAtHead.numberOfLocals(); ++i)
+                V_EQUAL((virtualRegisterForLocal(i), entrypoint), static_cast<Node*>(nullptr), entrypoint->variablesAtHead.local(i));
+        }
         
         // Validate ref counts and uses.
         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
index ac8b5b3..676b390 100644 (file)
@@ -74,8 +74,8 @@ void link(State& state)
             Profiler::OriginStack(),
             toCString("Generated FTL JIT code for ", CodeBlockWithJITType(codeBlock, JITCode::FTLJIT), ", instruction count = ", graph.m_codeBlock->instructionCount(), ":\n"));
         
-        graph.ensureDominators();
-        graph.ensureNaturalLoops();
+        graph.ensureSSADominators();
+        graph.ensureSSANaturalLoops();
         
         const char* prefix = "    ";
         
index ebd7b5a..3ee2169 100644 (file)
@@ -150,7 +150,7 @@ public:
         } else
             name = "jsBody";
         
-        m_graph.ensureDominators();
+        m_graph.ensureSSADominators();
 
         if (verboseCompilationEnabled())
             dataLog("Function ready, beginning lowering.\n");
@@ -266,8 +266,9 @@ public:
         }
         m_node = nullptr;
         m_origin = NodeOrigin(CodeOrigin(0), CodeOrigin(0), true);
+        auto& arguments = m_graph.m_entrypointToArguments.find(m_graph.block(0))->value;
         for (unsigned i = codeBlock()->numParameters(); i--;) {
-            Node* node = m_graph.m_arguments[i];
+            Node* node = arguments[i];
             m_out.setOrigin(node);
             VirtualRegister operand = virtualRegisterForArgument(i);
             
@@ -443,7 +444,7 @@ private:
             DFG::BasicBlock* target = m_graph.block(blockIndex);
             if (!target)
                 continue;
-            if (m_graph.m_dominators->dominates(m_highBlock, target)) {
+            if (m_graph.m_ssaDominators->dominates(m_highBlock, target)) {
                 if (verboseCompilationEnabled())
                     dataLog("Block ", *target, " will bail also.\n");
                 target->cfaHasVisited = false;
@@ -14472,7 +14473,7 @@ private:
     {
         if (!value)
             return false;
-        if (!m_graph.m_dominators->dominates(value.block(), m_highBlock))
+        if (!m_graph.m_ssaDominators->dominates(value.block(), m_highBlock))
             return false;
         return true;
     }
index dd4594c..7cbae35 100644 (file)
@@ -798,6 +798,7 @@ namespace JSC {
         MacroAssembler::Call callOperation(J_JITOperation_EZZ, int, int32_t, int32_t);
         MacroAssembler::Call callOperation(P_JITOperation_E);
         MacroAssembler::Call callOperation(P_JITOperation_EJS, GPRReg, size_t);
+        MacroAssembler::Call callOperation(P_JITOperation_EUi, uint32_t);
         MacroAssembler::Call callOperation(S_JITOperation_ECC, RegisterID, RegisterID);
         MacroAssembler::Call callOperation(S_JITOperation_EJ, RegisterID);
         MacroAssembler::Call callOperation(S_JITOperation_EJI, GPRReg, UniquedStringImpl*);
index e19e393..335e767 100644 (file)
@@ -463,6 +463,13 @@ ALWAYS_INLINE MacroAssembler::Call JIT::callOperation(J_JITOperation_EJJMic oper
     return call;
 }
 
+ALWAYS_INLINE MacroAssembler::Call JIT::callOperation(P_JITOperation_EUi operation, uint32_t arg1)
+{
+    setupArgumentsWithExecState(TrustedImm32(arg1));
+    updateTopCallFrame();
+    return appendCall(operation);
+}
+
 #if USE(JSVALUE64)
 ALWAYS_INLINE MacroAssembler::Call JIT::callOperation(Z_JITOperation_EJZZ operation, GPRReg arg1, int32_t arg2, int32_t arg3)
 {
index e8419c0..9b4166a 100644 (file)
@@ -554,6 +554,29 @@ void JIT::emit_op_catch(Instruction* currentInstruction)
 
     load64(Address(regT0, Exception::valueOffset()), regT0);
     emitPutVirtualRegister(currentInstruction[2].u.operand);
+
+#if ENABLE(DFG_JIT)
+    // FIXME: consider inline caching the process of doing OSR entry, including
+    // argument type proofs, storing locals to the buffer, etc
+    // https://bugs.webkit.org/show_bug.cgi?id=175598
+
+    ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(currentInstruction[3].u.pointer);
+    if (buffer || !shouldEmitProfiling())
+        callOperation(operationTryOSREnterAtCatch, m_bytecodeOffset);
+    else
+        callOperation(operationTryOSREnterAtCatchAndValueProfile, m_bytecodeOffset);
+    auto skipOSREntry = branchTestPtr(Zero, returnValueGPR);
+    emitRestoreCalleeSaves();
+    jump(returnValueGPR);
+    skipOSREntry.link(this);
+    if (buffer && shouldEmitProfiling()) {
+        buffer->forEach([&] (ValueProfileAndOperand& profile) {
+            JSValueRegs regs(regT0);
+            emitGetVirtualRegister(profile.m_operand, regs);
+            emitValueProfilingSite(profile.m_profile);
+        });
+    }
+#endif // ENABLE(DFG_JIT)
 }
 
 void JIT::emit_op_assert(Instruction* currentInstruction)
index 204664d..7e49950 100644 (file)
@@ -856,6 +856,26 @@ void JIT::emit_op_catch(Instruction* currentInstruction)
 
     unsigned thrownValue = currentInstruction[2].u.operand;
     emitStore(thrownValue, regT1, regT0);
+
+#if ENABLE(DFG_JIT)
+    // FIXME: consider inline caching the process of doing OSR entry, including
+    // argument type proofs, storing locals to the buffer, etc
+    // https://bugs.webkit.org/show_bug.cgi?id=175598
+
+    callOperation(operationTryOSREnterAtCatch, m_bytecodeOffset);
+    auto skipOSREntry = branchTestPtr(Zero, returnValueGPR);
+    emitRestoreCalleeSaves();
+    jump(returnValueGPR);
+    skipOSREntry.link(this);
+    if (shouldEmitProfiling()) {
+        ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(currentInstruction[3].u.pointer);
+        buffer->forEach([&] (ValueProfileAndOperand& profile) {
+            JSValueRegs regs(regT1, regT0);
+            emitGetVirtualRegister(profile.m_operand, regs);
+            emitValueProfilingSite(profile.m_profile);
+        });
+    }
+#endif // ENABLE(DFG_JIT)
 }
 
 void JIT::emit_op_assert(Instruction* currentInstruction)
index ac3bd3f..d8e57a7 100644 (file)
@@ -1526,6 +1526,38 @@ SlowPathReturnType JIT_OPERATION operationOptimize(ExecState* exec, int32_t byte
     CODEBLOCK_LOG_EVENT(codeBlock, "delayOptimizeToDFG", ("OSR failed"));
     return encodeResult(0, 0);
 }
+
+char* JIT_OPERATION operationTryOSREnterAtCatch(ExecState* exec, uint32_t bytecodeIndex)
+{
+    VM& vm = exec->vm();
+    NativeCallFrameTracer tracer(&vm, exec);
+
+    CodeBlock* optimizedReplacement = exec->codeBlock()->replacement();
+    if (optimizedReplacement->jitType() != JITCode::DFGJIT)
+        return nullptr;
+
+    return static_cast<char*>(DFG::prepareCatchOSREntry(exec, optimizedReplacement, bytecodeIndex));
+}
+
+char* JIT_OPERATION operationTryOSREnterAtCatchAndValueProfile(ExecState* exec, uint32_t bytecodeIndex)
+{
+    VM& vm = exec->vm();
+    NativeCallFrameTracer tracer(&vm, exec);
+
+    CodeBlock* codeBlock = exec->codeBlock();
+    CodeBlock* optimizedReplacement = codeBlock->replacement();
+    if (optimizedReplacement->jitType() == JITCode::DFGJIT)
+        return static_cast<char*>(DFG::prepareCatchOSREntry(exec, optimizedReplacement, bytecodeIndex));
+
+    codeBlock->ensureCatchLivenessIsComputedForBytecodeOffset(bytecodeIndex);
+    ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(codeBlock->instructions()[bytecodeIndex + 3].u.pointer);
+    buffer->forEach([&] (ValueProfileAndOperand& profile) {
+        profile.m_profile.m_buckets[0] = JSValue::encode(exec->uncheckedR(profile.m_operand).jsValue());
+    });
+
+    return nullptr;
+}
+
 #endif
 
 void JIT_OPERATION operationPutByIndex(ExecState* exec, EncodedJSValue encodedArrayValue, int32_t index, EncodedJSValue encodedValue)
index 4c5a965..e6d1cd4 100644 (file)
@@ -318,6 +318,7 @@ typedef char* (JIT_OPERATION *P_JITOperation_EStZP)(ExecState*, Structure*, int3
 typedef char* (JIT_OPERATION *P_JITOperation_EZZ)(ExecState*, int32_t, int32_t);
 typedef char* (JIT_OPERATION *P_JITOperation_EQZ)(ExecState*, int64_t, int32_t);
 typedef char* (JIT_OPERATION *P_JITOperation_EDZ)(ExecState*, double, int32_t);
+typedef char* (JIT_OPERATION *P_JITOperation_EUi)(ExecState*, uint32_t);
 typedef SlowPathReturnType (JIT_OPERATION *Sprt_JITOperation_ECli)(ExecState*, CallLinkInfo*);
 typedef StringImpl* (JIT_OPERATION *T_JITOperation_EJss)(ExecState*, JSString*);
 typedef JSString* (JIT_OPERATION *Jss_JITOperation_EZ)(ExecState*, int32_t);
@@ -400,6 +401,8 @@ void JIT_OPERATION operationThrow(ExecState*, EncodedJSValue) WTF_INTERNAL;
 void JIT_OPERATION operationDebug(ExecState*, int32_t) WTF_INTERNAL;
 #if ENABLE(DFG_JIT)
 SlowPathReturnType JIT_OPERATION operationOptimize(ExecState*, int32_t) WTF_INTERNAL;
+char* JIT_OPERATION operationTryOSREnterAtCatch(ExecState*, uint32_t) WTF_INTERNAL;
+char* JIT_OPERATION operationTryOSREnterAtCatchAndValueProfile(ExecState*, uint32_t) WTF_INTERNAL;
 #endif
 void JIT_OPERATION operationPutByIndex(ExecState*, EncodedJSValue, int32_t, EncodedJSValue);
 void JIT_OPERATION operationPutGetterById(ExecState*, JSCell*, UniquedStringImpl*, int32_t options, JSCell*) WTF_INTERNAL;
index 4eea741..ea6899a 100644 (file)
@@ -1661,6 +1661,20 @@ LLINT_SLOW_PATH_DECL(slow_path_log_shadow_chicken_tail)
     LLINT_END();
 }
 
+LLINT_SLOW_PATH_DECL(slow_path_profile_catch)
+{
+    LLINT_BEGIN();
+
+    exec->codeBlock()->ensureCatchLivenessIsComputedForBytecodeOffset(exec->bytecodeOffset());
+
+    ValueProfileAndOperandBuffer* buffer = static_cast<ValueProfileAndOperandBuffer*>(pc[3].u.pointer);
+    buffer->forEach([&] (ValueProfileAndOperand& profile) {
+        profile.m_profile.m_buckets[0] = JSValue::encode(exec->uncheckedR(profile.m_operand).jsValue());
+    });
+
+    LLINT_END();
+}
+
 extern "C" SlowPathReturnType llint_throw_stack_overflow_error(VM* vm, ProtoCallFrame* protoFrame)
 {
     ExecState* exec = vm->topCallFrame;
index 93c89fb..d9954d2 100644 (file)
@@ -126,6 +126,7 @@ LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_handle_exception);
 LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_get_from_scope);
 LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_put_to_scope);
 LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_check_if_exception_is_uncatchable_and_notify_profiler);
+LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_profile_catch);
 LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_log_shadow_chicken_prologue);
 LLINT_SLOW_PATH_HIDDEN_DECL(slow_path_log_shadow_chicken_tail);
 extern "C" SlowPathReturnType llint_throw_stack_overflow_error(VM*, ProtoCallFrame*) WTF_INTERNAL;
index 70ae8bc..16ad002 100644 (file)
@@ -1997,7 +1997,10 @@ _llint_op_catch:
     storei t1, TagOffset[cfr, t2, 8]
 
     traceExecution()  # This needs to be here because we don't want to clobber t0, t1, t2, t3 above.
-    dispatch(3)
+
+    callOpcodeSlowPath(_llint_slow_path_profile_catch)
+
+    dispatch(constexpr op_catch_length)
 
 _llint_op_end:
     traceExecution()
index 8e5e457..8985ba4 100644 (file)
@@ -1974,6 +1974,9 @@ _llint_op_catch:
     storeq t3, [cfr, t2, 8]
 
     traceExecution()
+
+    callOpcodeSlowPath(_llint_slow_path_profile_catch)
+
     dispatch(constexpr op_catch_length)
 
 
index 44dba47..667f30f 100644 (file)
@@ -1,3 +1,75 @@
+2017-08-25  Saam Barati  <sbarati@apple.com>
+
+        Support compiling catch in the DFG
+        https://bugs.webkit.org/show_bug.cgi?id=174590
+        <rdar://problem/34047845>
+
+        Reviewed by Filip Pizlo.
+
+        This patch generalizes the BackwardsGraph fake root into a more generalizable
+        class called SingleRootGraph. SingleRootGraph exposes the general graph interface
+        used in Dominators and NaturalLoops. SingleRootGraph takes as input a graph with
+        the normal graph interface, but also allows the input graph to contain more than
+        one root. SingleRootGraph then exposes a single root, which it creates, that has
+        an outgoing edge to all the roots in the original graph.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/BackwardsGraph.h:
+        (WTF::BackwardsGraph::dump const):
+        (WTF::BackwardsGraph::rootName): Deleted.
+        (WTF::BackwardsGraph::Node::Node): Deleted.
+        (WTF::BackwardsGraph::Node::root): Deleted.
+        (WTF::BackwardsGraph::Node::operator== const): Deleted.
+        (WTF::BackwardsGraph::Node::operator!= const): Deleted.
+        (WTF::BackwardsGraph::Node::operator bool const): Deleted.
+        (WTF::BackwardsGraph::Node::isRoot const): Deleted.
+        (WTF::BackwardsGraph::Node::node const): Deleted.
+        (): Deleted.
+        (WTF::BackwardsGraph::Set::Set): Deleted.
+        (WTF::BackwardsGraph::Set::add): Deleted.
+        (WTF::BackwardsGraph::Set::remove): Deleted.
+        (WTF::BackwardsGraph::Set::contains): Deleted.
+        (WTF::BackwardsGraph::Set::dump const): Deleted.
+        (WTF::BackwardsGraph::Map::Map): Deleted.
+        (WTF::BackwardsGraph::Map::clear): Deleted.
+        (WTF::BackwardsGraph::Map::size const): Deleted.
+        (WTF::BackwardsGraph::Map::operator[]): Deleted.
+        (WTF::BackwardsGraph::Map::operator[] const): Deleted.
+        * wtf/Dominators.h:
+        (WTF::Dominators::Dominators):
+        (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
+        (WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
+        (WTF::Dominators::iteratedDominanceFrontierOf const):
+        (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl const):
+        * wtf/SingleRootGraph.h: Added.
+        (WTF::SingleRootGraphNode::rootName):
+        (WTF::SingleRootGraphNode::SingleRootGraphNode):
+        (WTF::SingleRootGraphNode::root):
+        (WTF::SingleRootGraphNode::operator== const):
+        (WTF::SingleRootGraphNode::operator!= const):
+        (WTF::SingleRootGraphNode::operator bool const):
+        (WTF::SingleRootGraphNode::isRoot const):
+        (WTF::SingleRootGraphNode::node const):
+        (WTF::SingleRootGraphSet::add):
+        (WTF::SingleRootGraphSet::remove):
+        (WTF::SingleRootGraphSet::contains):
+        (WTF::SingleRootGraphSet::dump const):
+        (WTF::SingleRootMap::SingleRootMap):
+        (WTF::SingleRootMap::clear):
+        (WTF::SingleRootMap::size const):
+        (WTF::SingleRootMap::operator[]):
+        (WTF::SingleRootMap::operator[] const):
+        (WTF::SingleRootGraph::SingleRootGraph):
+        (WTF::SingleRootGraph::root const):
+        (WTF::SingleRootGraph::newMap):
+        (WTF::SingleRootGraph::successors const):
+        (WTF::SingleRootGraph::predecessors const):
+        (WTF::SingleRootGraph::index const):
+        (WTF::SingleRootGraph::node const):
+        (WTF::SingleRootGraph::numNodes const):
+        (WTF::SingleRootGraph::dump const):
+        (WTF::SingleRootGraph::assertIsConsistent const):
+
 2017-08-24  Commit Queue  <commit-queue@webkit.org>
 
         Unreviewed, rolling out r221119, r221124, and r221143.
index 0526951..21563aa 100644 (file)
                70ECA60B1B02426800449739 /* SymbolImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SymbolImpl.h; sourceTree = "<group>"; };
                70ECA60C1B02426800449739 /* UniquedStringImpl.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UniquedStringImpl.h; sourceTree = "<group>"; };
                7936D6A91C99F8AE000D1AED /* SmallPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SmallPtrSet.h; sourceTree = "<group>"; };
+               795212021F42588800BD6421 /* SingleRootGraph.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SingleRootGraph.h; sourceTree = "<group>"; };
                7AFEC6AE1EB22AC600DADE36 /* UUID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UUID.h; sourceTree = "<group>"; };
                7AFEC6B01EB22B5900DADE36 /* UUID.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = UUID.cpp; sourceTree = "<group>"; };
                7C3F72391D78811900674E26 /* Brigand.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Brigand.h; sourceTree = "<group>"; };
                                1469419416EAAFF80024E146 /* SchedulePair.h */,
                                1469419816EAB0410024E146 /* SchedulePairCF.cpp */,
                                1469419516EAAFF80024E146 /* SchedulePairMac.mm */,
+                               795212021F42588800BD6421 /* SingleRootGraph.h */,
                                1A3524AA1D63A2FF0031729B /* Scope.h */,
                                0FEC84B01BDACD390080FF74 /* ScopedLambda.h */,
                                0F66B2841DC97BAB004A1D3F /* Seconds.cpp */,
index 65337ba..3ac702d 100644 (file)
@@ -29,6 +29,7 @@
 #include <wtf/FastMalloc.h>
 #include <wtf/GraphNodeWorklist.h>
 #include <wtf/Noncopyable.h>
+#include <wtf/SingleRootGraph.h>
 #include <wtf/StdLibExtras.h>
 
 namespace WTF {
@@ -38,133 +39,9 @@ class BackwardsGraph {
     WTF_MAKE_NONCOPYABLE(BackwardsGraph);
     WTF_MAKE_FAST_ALLOCATED;
 public:
-    // We use "#end" to refer to the synthetic root we have created.
-    static const char* rootName() { return "#end"; };
-
-    class Node {
-    public:
-        Node(typename Graph::Node node = typename Graph::Node())
-            : m_node(node)
-        {
-        }
-
-        static Node root()
-        {
-            Node result;
-            result.m_node = 0;
-            result.m_isRoot = true;
-            return result;
-        }
-
-        bool operator==(const Node& other) const
-        {
-            return m_node == other.m_node
-                && m_isRoot == other.m_isRoot;
-        }
-
-        bool operator!=(const Node& other) const
-        {
-            return !(*this == other);
-        }
-
-        explicit operator bool() const { return *this != Node(); }
-
-        bool isRoot() const
-        {
-            return m_isRoot;
-        }
-
-        typename Graph::Node node() const { return m_node; }
-
-    private:
-        typename Graph::Node m_node;
-        bool m_isRoot { false };
-    };
-
-    class Set {
-    public:
-        Set()
-        {
-        }
-        
-        bool add(const Node& node)
-        {
-            if (node.isRoot())
-                return checkAndSet(m_hasRoot, true);
-            return m_set.add(node.node());
-        }
-
-        bool remove(const Node& node)
-        {
-            if (node.isRoot())
-                return checkAndSet(m_hasRoot, false);
-            return m_set.remove(node.node());
-        }
-
-        bool contains(const Node& node)
-        {
-            if (node.isRoot())
-                return m_hasRoot;
-            return m_set.contains(node.node());
-        }
-
-        void dump(PrintStream& out) const
-        {
-            if (m_hasRoot)
-                out.print(rootName(), " ");
-            out.print(m_set);
-        }
-        
-    private:
-        typename Graph::Set m_set;
-        bool m_hasRoot { false };
-    };
-
-    template<typename T>
-    class Map {
-    public:
-        Map(Graph& graph)
-            : m_map(graph.template newMap<T>())
-        {
-        }
-
-        void clear()
-        {
-            m_map.clear();
-            m_root = T();
-        }
-
-        size_t size() const { return m_map.size() + 1; }
-
-        T& operator[](size_t index)
-        {
-            if (!index)
-                return m_root;
-            return m_map[index - 1];
-        }
-
-        const T& operator[](size_t index) const
-        {
-            return (*const_cast<Map*>(this))[index];
-        }
-
-        T& operator[](const Node& node)
-        {
-            if (node.isRoot())
-                return m_root;
-            return m_map[node.node()];
-        }
-
-        const T& operator[](const Node& node) const
-        {
-            return (*const_cast<Map*>(this))[node];
-        }
-        
-    private:
-        typename Graph::template Map<T> m_map;
-        T m_root;
-    };
-
+    using Node = SingleRootGraphNode<Graph>;
+    using Set = SingleRootGraphSet<Graph>;
+    template <typename T> using Map = SingleRootMap<T, Graph>;
     typedef Vector<Node, 4> List;
 
     BackwardsGraph(Graph& graph)
@@ -255,7 +132,7 @@ public:
         if (!node)
             out.print("<null>");
         else if (node.isRoot())
-            out.print(rootName());
+            out.print(Node::rootName());
         else
             out.print(m_graph.dump(node.node()));
         return out.toCString();
index 7c760dc..7bf2eae 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2014-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -40,6 +40,8 @@ namespace WTF {
 template<typename Graph>
 class Dominators {
 public:
+    using List = typename Graph::List;
+
     Dominators(Graph& graph, bool selfCheck = false)
         : m_graph(graph)
         , m_data(graph.template newMap<BlockData>())
@@ -47,8 +49,6 @@ public:
         LengauerTarjan lengauerTarjan(m_graph);
         lengauerTarjan.compute();
 
-        m_data = m_graph.template newMap<BlockData>();
-    
         // From here we want to build a spanning tree with both upward and downward links and we want
         // to do a search over this tree to compute pre and post numbers that can be used for dominance
         // tests.
@@ -240,7 +240,7 @@ public:
     }
     
     template<typename Functor>
-    void forAllBlocksInIteratedDominanceFrontierOf(const typename Graph::List& from, const Functor& functor)
+    void forAllBlocksInIteratedDominanceFrontierOf(const List& from, const Functor& functor)
     {
         forAllBlocksInPrunedIteratedDominanceFrontierOf(
             from,
@@ -255,7 +255,7 @@ public:
     // Useful for computing pruned SSA form.
     template<typename Functor>
     void forAllBlocksInPrunedIteratedDominanceFrontierOf(
-        const typename Graph::List& from, const Functor& functor)
+        const List& from, const Functor& functor)
     {
         typename Graph::Set set;
         forAllBlocksInIteratedDominanceFrontierOfImpl(
@@ -267,7 +267,7 @@ public:
             });
     }
     
-    typename Graph::Set iteratedDominanceFrontierOf(const typename Graph::List& from) const
+    typename Graph::Set iteratedDominanceFrontierOf(const List& from) const
     {
         typename Graph::Set result;
         forAllBlocksInIteratedDominanceFrontierOfImpl(
@@ -712,9 +712,9 @@ private:
     
     template<typename Functor>
     void forAllBlocksInIteratedDominanceFrontierOfImpl(
-        const typename Graph::List& from, const Functor& functor) const
+        const List& from, const Functor& functor) const
     {
-        typename Graph::List worklist = from;
+        List worklist = from;
         while (!worklist.isEmpty()) {
             typename Graph::Node block = worklist.takeLast();
             forAllBlocksInDominanceFrontierOfImpl(
diff --git a/Source/WTF/wtf/SingleRootGraph.h b/Source/WTF/wtf/SingleRootGraph.h
new file mode 100644 (file)
index 0000000..fdf1b65
--- /dev/null
@@ -0,0 +1,309 @@
+/*
+ * Copyright (C) 2017 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 WTF_SingleRootGraph_h
+#define WTF_SingleRootGraph_h
+
+#include <wtf/FastMalloc.h>
+#include <wtf/GraphNodeWorklist.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/StdLibExtras.h>
+
+namespace WTF {
+
+template <typename Graph>
+class SingleRootGraphNode {
+public:
+    // We use "#root" to refer to the synthetic root we have created.
+    static const char* rootName() { return "#root"; };
+
+    SingleRootGraphNode(typename Graph::Node node = typename Graph::Node())
+        : m_node(node)
+    {
+    }
+
+    static SingleRootGraphNode root()
+    {
+        SingleRootGraphNode result;
+        result.m_node = 0;
+        result.m_isRoot = true;
+        return result;
+    }
+
+    bool operator==(const SingleRootGraphNode& other) const
+    {
+        return m_node == other.m_node
+            && m_isRoot == other.m_isRoot;
+    }
+
+    bool operator!=(const SingleRootGraphNode& other) const
+    {
+        return !(*this == other);
+    }
+
+    explicit operator bool() const { return *this != SingleRootGraphNode(); }
+
+    bool isRoot() const
+    {
+        return m_isRoot;
+    }
+
+    typename Graph::Node node() const
+    {
+        ASSERT(!m_isRoot);
+        return m_node;
+    }
+
+private:
+    typename Graph::Node m_node;
+    bool m_isRoot { false };
+};
+
+template <typename Graph>
+class SingleRootGraphSet {
+    using Node = SingleRootGraphNode<Graph>;
+public:
+    SingleRootGraphSet() = default;
+    
+    bool add(const Node& node)
+    {
+        if (node.isRoot())
+            return checkAndSet(m_hasRoot, true);
+        return m_set.add(node.node());
+    }
+
+    bool remove(const Node& node)
+    {
+        if (node.isRoot())
+            return checkAndSet(m_hasRoot, false);
+        return m_set.remove(node.node());
+    }
+
+    bool contains(const Node& node)
+    {
+        if (node.isRoot())
+            return m_hasRoot;
+        return m_set.contains(node.node());
+    }
+
+    void dump(PrintStream& out) const
+    {
+        if (m_hasRoot)
+            out.print(Node::rootName(), " ");
+        out.print(m_set);
+    }
+    
+private:
+    typename Graph::Set m_set;
+    bool m_hasRoot { false };
+};
+
+template<typename T, typename Graph>
+class SingleRootMap {
+    using Node = SingleRootGraphNode<Graph>;
+public:
+    SingleRootMap(Graph& graph)
+        : m_map(graph.template newMap<T>())
+    {
+    }
+
+    SingleRootMap(SingleRootMap&& other)
+        : m_map(WTFMove(other.m_map))
+        , m_root(WTFMove(other.m_root))
+    {
+    }
+
+    void clear()
+    {
+        m_map.clear();
+        m_root = T();
+    }
+
+    size_t size() const { return m_map.size() + 1; }
+
+    T& operator[](size_t index)
+    {
+        if (!index)
+            return m_root;
+        return m_map[index - 1];
+    }
+
+    const T& operator[](size_t index) const
+    {
+        return (*const_cast<SingleRootMap*>(this))[index];
+    }
+
+    T& operator[](const Node& node)
+    {
+        if (node.isRoot())
+            return m_root;
+        return m_map[node.node()];
+    }
+
+    const T& operator[](const Node& node) const
+    {
+        return (*const_cast<SingleRootMap*>(this))[node];
+    }
+    
+private:
+    typename Graph::template Map<T> m_map;
+    T m_root;
+};
+
+template<typename Graph>
+class SingleRootGraph {
+    WTF_MAKE_NONCOPYABLE(SingleRootGraph);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+
+    using Node = SingleRootGraphNode<Graph>;
+    using Set = SingleRootGraphSet<Graph>;
+    template <typename T> using Map = SingleRootMap<T, Graph>;
+    using List = Vector<Node, 4>;
+
+    SingleRootGraph(Graph& graph)
+        : m_graph(graph)
+    {
+        for (typename Graph::Node realRoot : m_graph.roots()) {
+            ASSERT(m_graph.predecessors(realRoot).isEmpty());
+            m_rootSuccessorList.append(realRoot);
+            m_rootSuccessorSet.add(realRoot);
+        }
+        ASSERT(m_rootSuccessorList.size());
+    }
+
+    Node root() const { return Node::root(); }
+
+    template<typename T>
+    Map<T> newMap() { return Map<T>(m_graph); }
+
+    List successors(const Node& node) const
+    {
+        assertIsConsistent();
+
+        if (node.isRoot())
+            return m_rootSuccessorList;
+        List result;
+        for (typename Graph::Node successor : m_graph.successors(node.node()))
+            result.append(successor);
+        return result;
+    }
+
+    List predecessors(const Node& node) const
+    {
+        assertIsConsistent();
+
+        if (node.isRoot())
+            return List { };
+
+        if (m_rootSuccessorSet.contains(node.node())) {
+            ASSERT(m_graph.predecessors(node.node()).isEmpty());
+            return List { root() };
+        }
+
+        List result;
+        for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
+            result.append(predecessor);
+        return result;
+    }
+
+    unsigned index(const Node& node) const
+    {
+        if (node.isRoot())
+            return 0;
+        return m_graph.index(node.node()) + 1;
+    }
+
+    Node node(unsigned index) const
+    {
+        if (!index)
+            return root();
+        return m_graph.node(index - 1);
+    }
+
+    unsigned numNodes() const
+    {
+        return m_graph.numNodes() + 1;
+    }
+
+    CString dump(Node node) const
+    {
+        StringPrintStream out;
+        if (!node)
+            out.print("<null>");
+        else if (node.isRoot())
+            out.print(Node::rootName());
+        else
+            out.print(m_graph.dump(node.node()));
+        return out.toCString();
+    }
+
+    void dump(PrintStream& out) const
+    {
+        for (unsigned i = 0; i < numNodes(); ++i) {
+            Node node = this->node(i);
+            if (!node)
+                continue;
+            out.print(dump(node), ":\n");
+            out.print("    Preds: ");
+            CommaPrinter comma;
+            for (Node predecessor : predecessors(node))
+                out.print(comma, dump(predecessor));
+            out.print("\n");
+            out.print("    Succs: ");
+            comma = CommaPrinter();
+            for (Node successor : successors(node))
+                out.print(comma, dump(successor));
+            out.print("\n");
+        }
+    }
+
+private:
+    ALWAYS_INLINE void assertIsConsistent() const
+    {
+#if !ASSERT_DISABLED
+        // We expect the roots() function to be idempotent while we're alive so we can cache
+        // the result in the constructor. If a user of this changes the result of its roots()
+        // function, it's expected that the user will create a new instance of this class.
+        List rootSuccessorList;
+        for (typename Graph::Node realRoot : m_graph.roots()) {
+            ASSERT(m_graph.predecessors(realRoot).isEmpty());
+            rootSuccessorList.append(realRoot);
+        }
+        ASSERT(rootSuccessorList.size());
+        ASSERT(rootSuccessorList == m_rootSuccessorList);
+#endif
+    }
+
+    Graph& m_graph;
+    List m_rootSuccessorList;
+    typename Graph::Set m_rootSuccessorSet;
+};
+
+} // namespace WTF
+
+using WTF::SingleRootGraph;
+
+#endif // WTF_SingleRootGraph_h