FTL should be able to do polymorphic call inlining
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Aug 2014 19:09:48 +0000 (19:09 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Aug 2014 19:09:48 +0000 (19:09 +0000)
commit2143b6dcd4bb09aff5f3dc7783aec26072102b88
tree504edf1a2c43282fff098471bf61027d526342a2
parent0accadd8dbafb70f2df07235db71f5ad84659acf
FTL should be able to do polymorphic call inlining
https://bugs.webkit.org/show_bug.cgi?id=135145

Reviewed by Geoffrey Garen.
Source/JavaScriptCore:

Added a log-based high-fidelity call edge profiler that runs in DFG JIT (and optionally
baseline JIT) code. Used it to do precise polymorphic inlining in the FTL. Potential
inlining sites use the call edge profile if it is available, but they will still fall back
on the call inline cache and rare case counts if it's not. Polymorphic inlining means that
multiple possible callees can be inlined with a switch to guard them. The slow path may
either be an OSR exit or a virtual call.

The call edge profiling added in this patch is very precise - it will tell you about every
call that has ever happened. It took some effort to reduce the overhead of this profiling.
This mostly involved ensuring that we don't do it unnecessarily. For example, we avoid it
in the baseline JIT (you can conditionally enable it but it's off by default) and we only do
it in the DFG JIT if we know that the regular inline cache profiling wasn't precise enough.
I also experimented with reducing the precision of the profiling. This led to a significant
reduction in the speed-up, so I avoided this approach. I also explored making log processing
concurrent, but that didn't help. Also, I tested the overhead of the log processing and
found that most of the overhead of this profiling is actually in putting things into the log
rather than in processing the log - that part appears to be surprisingly cheap.

Polymorphic inlining could be enabled in the DFG if we enabled baseline call edge profiling,
and if we guarded such inlining sites with some profiling mechanism to detect
polyvariant monomorphisation opportunities (where the callsite being inlined reveals that
it's actually monomorphic).

This is a ~28% speed-up on deltablue and a ~7% speed-up on richards, with small speed-ups on
other programs as well. It's about a 2% speed-up on Octane version 2, and never a regression
on anything we care about. Some aggregates, like V8Spider, see a regression. This is
highlighting the increase in profiling overhead. But since this doesn't show up on any major
score (code-load or SunSpider), it's probably not relevant.

Relanding after fixing debug assertions in fast/storage/serialized-script-value.html.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/CallEdge.cpp: Added.
(JSC::CallEdge::dump):
* bytecode/CallEdge.h: Added.
(JSC::CallEdge::operator!):
(JSC::CallEdge::callee):
(JSC::CallEdge::count):
(JSC::CallEdge::despecifiedClosure):
(JSC::CallEdge::CallEdge):
* bytecode/CallEdgeProfile.cpp: Added.
(JSC::CallEdgeProfile::callEdges):
(JSC::CallEdgeProfile::numCallsToKnownCells):
(JSC::worthDespecifying):
(JSC::CallEdgeProfile::worthDespecifying):
(JSC::CallEdgeProfile::visitWeak):
(JSC::CallEdgeProfile::addSlow):
(JSC::CallEdgeProfile::mergeBack):
(JSC::CallEdgeProfile::fadeByHalf):
(JSC::CallEdgeLog::CallEdgeLog):
(JSC::CallEdgeLog::~CallEdgeLog):
(JSC::CallEdgeLog::isEnabled):
(JSC::operationProcessCallEdgeLog):
(JSC::CallEdgeLog::emitLogCode):
(JSC::CallEdgeLog::processLog):
* bytecode/CallEdgeProfile.h: Added.
(JSC::CallEdgeProfile::numCallsToNotCell):
(JSC::CallEdgeProfile::numCallsToUnknownCell):
(JSC::CallEdgeProfile::totalCalls):
* bytecode/CallEdgeProfileInlines.h: Added.
(JSC::CallEdgeProfile::CallEdgeProfile):
(JSC::CallEdgeProfile::add):
* bytecode/CallLinkInfo.cpp:
(JSC::CallLinkInfo::visitWeak):
* bytecode/CallLinkInfo.h:
* bytecode/CallLinkStatus.cpp:
(JSC::CallLinkStatus::CallLinkStatus):
(JSC::CallLinkStatus::computeFromLLInt):
(JSC::CallLinkStatus::computeFor):
(JSC::CallLinkStatus::computeExitSiteData):
(JSC::CallLinkStatus::computeFromCallLinkInfo):
(JSC::CallLinkStatus::computeFromCallEdgeProfile):
(JSC::CallLinkStatus::computeDFGStatuses):
(JSC::CallLinkStatus::isClosureCall):
(JSC::CallLinkStatus::makeClosureCall):
(JSC::CallLinkStatus::dump):
(JSC::CallLinkStatus::function): Deleted.
(JSC::CallLinkStatus::internalFunction): Deleted.
(JSC::CallLinkStatus::intrinsicFor): Deleted.
* bytecode/CallLinkStatus.h:
(JSC::CallLinkStatus::CallLinkStatus):
(JSC::CallLinkStatus::isSet):
(JSC::CallLinkStatus::couldTakeSlowPath):
(JSC::CallLinkStatus::edges):
(JSC::CallLinkStatus::size):
(JSC::CallLinkStatus::at):
(JSC::CallLinkStatus::operator[]):
(JSC::CallLinkStatus::canOptimize):
(JSC::CallLinkStatus::canTrustCounts):
(JSC::CallLinkStatus::isClosureCall): Deleted.
(JSC::CallLinkStatus::callTarget): Deleted.
(JSC::CallLinkStatus::executable): Deleted.
(JSC::CallLinkStatus::makeClosureCall): Deleted.
* bytecode/CallVariant.cpp: Added.
(JSC::CallVariant::dump):
* bytecode/CallVariant.h: Added.
(JSC::CallVariant::CallVariant):
(JSC::CallVariant::operator!):
(JSC::CallVariant::despecifiedClosure):
(JSC::CallVariant::rawCalleeCell):
(JSC::CallVariant::internalFunction):
(JSC::CallVariant::function):
(JSC::CallVariant::isClosureCall):
(JSC::CallVariant::executable):
(JSC::CallVariant::nonExecutableCallee):
(JSC::CallVariant::intrinsicFor):
(JSC::CallVariant::functionExecutable):
(JSC::CallVariant::isHashTableDeletedValue):
(JSC::CallVariant::operator==):
(JSC::CallVariant::operator!=):
(JSC::CallVariant::operator<):
(JSC::CallVariant::operator>):
(JSC::CallVariant::operator<=):
(JSC::CallVariant::operator>=):
(JSC::CallVariant::hash):
(JSC::CallVariant::deletedToken):
(JSC::CallVariantHash::hash):
(JSC::CallVariantHash::equal):
* bytecode/CodeOrigin.h:
(JSC::InlineCallFrame::isNormalCall):
* bytecode/ExitKind.cpp:
(JSC::exitKindToString):
* bytecode/ExitKind.h:
* bytecode/GetByIdStatus.cpp:
(JSC::GetByIdStatus::computeForStubInfo):
* bytecode/PutByIdStatus.cpp:
(JSC::PutByIdStatus::computeForStubInfo):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
* dfg/DFGBackwardsPropagationPhase.cpp:
(JSC::DFG::BackwardsPropagationPhase::propagate):
* dfg/DFGBasicBlock.cpp:
(JSC::DFG::BasicBlock::~BasicBlock):
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::takeLast):
(JSC::DFG::BasicBlock::didLink):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::processSetLocalQueue):
(JSC::DFG::ByteCodeParser::removeLastNodeFromGraph):
(JSC::DFG::ByteCodeParser::addCallWithoutSettingResult):
(JSC::DFG::ByteCodeParser::addCall):
(JSC::DFG::ByteCodeParser::handleCall):
(JSC::DFG::ByteCodeParser::emitFunctionChecks):
(JSC::DFG::ByteCodeParser::undoFunctionChecks):
(JSC::DFG::ByteCodeParser::inliningCost):
(JSC::DFG::ByteCodeParser::inlineCall):
(JSC::DFG::ByteCodeParser::cancelLinkingForBlock):
(JSC::DFG::ByteCodeParser::attemptToInlineCall):
(JSC::DFG::ByteCodeParser::handleInlining):
(JSC::DFG::ByteCodeParser::handleConstantInternalFunction):
(JSC::DFG::ByteCodeParser::prepareToParseBlock):
(JSC::DFG::ByteCodeParser::clearCaches):
(JSC::DFG::ByteCodeParser::parseBlock):
(JSC::DFG::ByteCodeParser::linkBlock):
(JSC::DFG::ByteCodeParser::linkBlocks):
(JSC::DFG::ByteCodeParser::parseCodeBlock):
* dfg/DFGCPSRethreadingPhase.cpp:
(JSC::DFG::CPSRethreadingPhase::freeUnnecessaryNodes):
* dfg/DFGClobberize.h:
(JSC::DFG::clobberize):
* dfg/DFGCommon.h:
* dfg/DFGConstantFoldingPhase.cpp:
(JSC::DFG::ConstantFoldingPhase::foldConstants):
* dfg/DFGDoesGC.cpp:
(JSC::DFG::doesGC):
* dfg/DFGDriver.cpp:
(JSC::DFG::compileImpl):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::getBlocksInPreOrder):
(JSC::DFG::Graph::visitChildren):
* dfg/DFGJITCompiler.cpp:
(JSC::DFG::JITCompiler::link):
* dfg/DFGLazyJSValue.cpp:
(JSC::DFG::LazyJSValue::switchLookupValue):
* dfg/DFGLazyJSValue.h:
(JSC::DFG::LazyJSValue::switchLookupValue): Deleted.
* dfg/DFGNode.cpp:
(WTF::printInternal):
* dfg/DFGNode.h:
(JSC::DFG::OpInfo::OpInfo):
(JSC::DFG::Node::hasHeapPrediction):
(JSC::DFG::Node::hasCellOperand):
(JSC::DFG::Node::cellOperand):
(JSC::DFG::Node::setCellOperand):
(JSC::DFG::Node::canBeKnownFunction): Deleted.
(JSC::DFG::Node::hasKnownFunction): Deleted.
(JSC::DFG::Node::knownFunction): Deleted.
(JSC::DFG::Node::giveKnownFunction): Deleted.
(JSC::DFG::Node::hasFunction): Deleted.
(JSC::DFG::Node::function): Deleted.
(JSC::DFG::Node::hasExecutable): Deleted.
(JSC::DFG::Node::executable): Deleted.
* dfg/DFGNodeType.h:
* dfg/DFGPhantomCanonicalizationPhase.cpp:
(JSC::DFG::PhantomCanonicalizationPhase::run):
* dfg/DFGPhantomRemovalPhase.cpp:
(JSC::DFG::PhantomRemovalPhase::run):
* dfg/DFGPredictionPropagationPhase.cpp:
(JSC::DFG::PredictionPropagationPhase::propagate):
* dfg/DFGSafeToExecute.h:
(JSC::DFG::safeToExecute):
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::emitSwitch):
* dfg/DFGSpeculativeJIT32_64.cpp:
(JSC::DFG::SpeculativeJIT::emitCall):
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGSpeculativeJIT64.cpp:
(JSC::DFG::SpeculativeJIT::emitCall):
(JSC::DFG::SpeculativeJIT::compile):
* dfg/DFGStructureRegistrationPhase.cpp:
(JSC::DFG::StructureRegistrationPhase::run):
* dfg/DFGTierUpCheckInjectionPhase.cpp:
(JSC::DFG::TierUpCheckInjectionPhase::run):
(JSC::DFG::TierUpCheckInjectionPhase::removeFTLProfiling):
* dfg/DFGValidate.cpp:
(JSC::DFG::Validate::validate):
* dfg/DFGWatchpointCollectionPhase.cpp:
(JSC::DFG::WatchpointCollectionPhase::handle):
* ftl/FTLCapabilities.cpp:
(JSC::FTL::canCompile):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::ftlUnreachable):
(JSC::FTL::LowerDFGToLLVM::lower):
(JSC::FTL::LowerDFGToLLVM::compileNode):
(JSC::FTL::LowerDFGToLLVM::compileCheckCell):
(JSC::FTL::LowerDFGToLLVM::compileCheckBadCell):
(JSC::FTL::LowerDFGToLLVM::compileGetExecutable):
(JSC::FTL::LowerDFGToLLVM::compileNativeCallOrConstruct):
(JSC::FTL::LowerDFGToLLVM::compileSwitch):
(JSC::FTL::LowerDFGToLLVM::buildSwitch):
(JSC::FTL::LowerDFGToLLVM::compileCheckFunction): Deleted.
(JSC::FTL::LowerDFGToLLVM::compileCheckExecutable): Deleted.
* heap/Heap.cpp:
(JSC::Heap::collect):
* jit/AssemblyHelpers.h:
(JSC::AssemblyHelpers::storeValue):
(JSC::AssemblyHelpers::loadValue):
* jit/CCallHelpers.h:
(JSC::CCallHelpers::setupArguments):
* jit/GPRInfo.h:
(JSC::JSValueRegs::uses):
* jit/JITCall.cpp:
(JSC::JIT::compileOpCall):
* jit/JITCall32_64.cpp:
(JSC::JIT::compileOpCall):
* runtime/Options.h:
* runtime/VM.cpp:
(JSC::VM::ensureCallEdgeLog):
* runtime/VM.h:
* tests/stress/fold-profiled-call-to-call.js: Added. This test pinpoints the problem we saw in fast/storage/serialized-script-value.html.
* tests/stress/new-array-then-exit.js: Added.
* tests/stress/poly-call-exit-this.js: Added.
* tests/stress/poly-call-exit.js: Added.

Source/WTF:

Add some power that I need for call edge profiling.

* wtf/OwnPtr.h:
(WTF::OwnPtr<T>::createTransactionally):
* wtf/Spectrum.h:
(WTF::Spectrum::add):
(WTF::Spectrum::addAll):
(WTF::Spectrum::get):
(WTF::Spectrum::size):
(WTF::Spectrum::KeyAndCount::KeyAndCount):
(WTF::Spectrum::clear):
(WTF::Spectrum::removeIf):

LayoutTests:

* js/regress/script-tests/simple-poly-call-nested.js: Added.
* js/regress/script-tests/simple-poly-call.js: Added.
* js/regress/simple-poly-call-expected.txt: Added.
* js/regress/simple-poly-call-nested-expected.txt: Added.
* js/regress/simple-poly-call-nested.html: Added.
* js/regress/simple-poly-call.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173069 268f45cc-cd09-0410-ab3c-d52691b4dbfc
75 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/script-tests/simple-poly-call-nested.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/simple-poly-call.js [new file with mode: 0644]
LayoutTests/js/regress/simple-poly-call-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/simple-poly-call-nested-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/simple-poly-call-nested.html [new file with mode: 0644]
LayoutTests/js/regress/simple-poly-call.html [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/CallEdge.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallEdge.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallEdgeProfile.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallEdgeProfile.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallEdgeProfileInlines.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallLinkInfo.cpp
Source/JavaScriptCore/bytecode/CallLinkInfo.h
Source/JavaScriptCore/bytecode/CallLinkStatus.cpp
Source/JavaScriptCore/bytecode/CallLinkStatus.h
Source/JavaScriptCore/bytecode/CallVariant.cpp [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CallVariant.h [new file with mode: 0644]
Source/JavaScriptCore/bytecode/CodeOrigin.h
Source/JavaScriptCore/bytecode/ExitKind.cpp
Source/JavaScriptCore/bytecode/ExitKind.h
Source/JavaScriptCore/bytecode/GetByIdStatus.cpp
Source/JavaScriptCore/bytecode/PutByIdStatus.cpp
Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGCPSRethreadingPhase.cpp
Source/JavaScriptCore/dfg/DFGClobberize.h
Source/JavaScriptCore/dfg/DFGCommon.h
Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp
Source/JavaScriptCore/dfg/DFGDoesGC.cpp
Source/JavaScriptCore/dfg/DFGDriver.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGJITCompiler.cpp
Source/JavaScriptCore/dfg/DFGLazyJSValue.cpp
Source/JavaScriptCore/dfg/DFGLazyJSValue.h
Source/JavaScriptCore/dfg/DFGNode.cpp
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeType.h
Source/JavaScriptCore/dfg/DFGPhantomCanonicalizationPhase.cpp
Source/JavaScriptCore/dfg/DFGPhantomRemovalPhase.cpp
Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.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/DFGStructureRegistrationPhase.cpp
Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp
Source/JavaScriptCore/dfg/DFGValidate.cpp
Source/JavaScriptCore/dfg/DFGWatchpointCollectionPhase.cpp
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/jit/AssemblyHelpers.h
Source/JavaScriptCore/jit/CCallHelpers.h
Source/JavaScriptCore/jit/GPRInfo.h
Source/JavaScriptCore/jit/JITCall.cpp
Source/JavaScriptCore/jit/JITCall32_64.cpp
Source/JavaScriptCore/runtime/Options.h
Source/JavaScriptCore/runtime/VM.cpp
Source/JavaScriptCore/runtime/VM.h
Source/JavaScriptCore/tests/stress/fold-profiled-call-to-call.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/new-array-then-exit.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/poly-call-exit-this.js [new file with mode: 0644]
Source/JavaScriptCore/tests/stress/poly-call-exit.js [new file with mode: 0644]
Source/WTF/ChangeLog
Source/WTF/wtf/OwnPtr.h
Source/WTF/wtf/Spectrum.h