fourthTier: DFG should support switch_string
authoroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:03:51 +0000 (04:03 +0000)
committeroliver@apple.com <oliver@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Jul 2013 04:03:51 +0000 (04:03 +0000)
commitc147f5bcd441ec93520bb013a5c72955a0a58709
treeea764c214b23c087e17943ac2173bc8dcdbef32d
parent8a6c0134635cd6cd2a09dc18d1f2a388f872c306
fourthTier: DFG should support switch_string
https://bugs.webkit.org/show_bug.cgi?id=117967

Source/JavaScriptCore:

Reviewed by Sam Weinig.

Add a reusable binary switch creator.

Implement switch on string using three modes:

- Binary switch on StringImpl* in the case of identifiers.

- Trie of binary switches on characters in the case of a not-too-big
  switch over not-too-big 8-bit strings.

- Hash lookup if all else fails.

Anywhere from a 2x to 3x speed-up on microbenchmarks that stress
string switches. 25-35% speed-up on HashMap tests. 4% speed-up on
pdfjs.

* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/JumpTable.h:
(StringJumpTable):
(JSC::StringJumpTable::clear):
* dfg/DFGBackwardsPropagationPhase.cpp:
(JSC::DFG::BackwardsPropagationPhase::propagate):
* dfg/DFGBinarySwitch.cpp: Added.
(DFG):
(JSC::DFG::BinarySwitch::BinarySwitch):
(JSC::DFG::BinarySwitch::advance):
(JSC::DFG::BinarySwitch::build):
* dfg/DFGBinarySwitch.h: Added.
(DFG):
(BinarySwitch):
(JSC::DFG::BinarySwitch::caseIndex):
(JSC::DFG::BinarySwitch::caseValue):
(JSC::DFG::BinarySwitch::fallThrough):
(JSC::DFG::BinarySwitch::Case::Case):
(Case):
(JSC::DFG::BinarySwitch::Case::operator<):
(JSC::DFG::BinarySwitch::BranchCode::BranchCode):
(BranchCode):
* dfg/DFGByteCodeParser.cpp:
(JSC::DFG::ByteCodeParser::parseBlock):
* dfg/DFGCapabilities.cpp:
(JSC::DFG::capabilityLevel):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
* dfg/DFGJITCompiler.cpp:
(JSC::DFG::JITCompiler::link):
* dfg/DFGLazyJSValue.cpp:
(JSC::DFG::LazyJSValue::getValue):
(JSC::DFG::equalToStringImpl):
(DFG):
(JSC::DFG::LazyJSValue::strictEqual):
(JSC::DFG::LazyJSValue::dump):
* dfg/DFGLazyJSValue.h:
(JSC::DFG::LazyJSValue::knownStringImpl):
(LazyJSValue):
(JSC::DFG::LazyJSValue::stringImpl):
(JSC::DFG::LazyJSValue::switchLookupValue):
* dfg/DFGNode.cpp:
(WTF::printInternal):
* dfg/DFGNode.h:
* dfg/DFGOperations.cpp:
* dfg/DFGOperations.h:
* dfg/DFGSpeculativeJIT.cpp:
(JSC::DFG::SpeculativeJIT::emitSwitchChar):
(JSC::DFG::SpeculativeJIT::StringSwitchCase::operator<):
(DFG):
(JSC::DFG::SpeculativeJIT::emitBinarySwitchStringRecurse):
(JSC::DFG::SpeculativeJIT::emitSwitchStringOnString):
(JSC::DFG::SpeculativeJIT::emitSwitchString):
(JSC::DFG::SpeculativeJIT::emitSwitch):
(JSC::DFG::SpeculativeJIT::addBranch):
* dfg/DFGSpeculativeJIT.h:
(JSC::DFG::SpeculativeJIT::callOperation):
(JSC::DFG::SpeculativeJIT::branch8):
(SpeculativeJIT):
(JSC::DFG::SpeculativeJIT::StringSwitchCase::StringSwitchCase):
(StringSwitchCase):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::LowerDFGToLLVM::compileSwitch):
* runtime/Options.h:
(JSC):

Source/WTF:

Reviewed by Sam Weinig.

Make it possible to compare a RefPtr<StringImpl> and a StringImpl* without
having to ref the StringImpl.

* wtf/text/StringHash.h:
(WTF::StringHash::equal):

LayoutTests:

Reviewed by Sam Weinig.

* fast/js/regress/script-tests/switch-string-basic-big-var.js: Added.
(foo):
(make):
* fast/js/regress/script-tests/switch-string-basic-big.js: Added.
(foo):
(make):
* fast/js/regress/script-tests/switch-string-basic-var.js: Added.
(foo):
(make):
* fast/js/regress/script-tests/switch-string-basic.js: Added.
(foo):
* fast/js/regress/script-tests/switch-string-big-length-tower-var.js: Added.
(foo):
* fast/js/regress/script-tests/switch-string-length-tower-var.js: Added.
(foo):
* fast/js/regress/script-tests/switch-string-length-tower.js: Added.
(foo):
* fast/js/regress/script-tests/switch-string-short.js: Added.
(foo):
* fast/js/regress/switch-string-basic-big-expected.txt: Added.
* fast/js/regress/switch-string-basic-big-var-expected.txt: Added.
* fast/js/regress/switch-string-basic-big-var.html: Added.
* fast/js/regress/switch-string-basic-big.html: Added.
* fast/js/regress/switch-string-basic-expected.txt: Added.
* fast/js/regress/switch-string-basic-var-expected.txt: Added.
* fast/js/regress/switch-string-basic-var.html: Added.
* fast/js/regress/switch-string-basic.html: Added.
* fast/js/regress/switch-string-big-length-tower-var-expected.txt: Added.
* fast/js/regress/switch-string-big-length-tower-var.html: Added.
* fast/js/regress/switch-string-length-tower-expected.txt: Added.
* fast/js/regress/switch-string-length-tower-var-expected.txt: Added.
* fast/js/regress/switch-string-length-tower-var.html: Added.
* fast/js/regress/switch-string-length-tower.html: Added.
* fast/js/regress/switch-string-short-expected.txt: Added.
* fast/js/regress/switch-string-short.html: Added.

Conflicts:
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@153248 268f45cc-cd09-0410-ab3c-d52691b4dbfc
47 files changed:
LayoutTests/ChangeLog
LayoutTests/fast/js/regress/script-tests/switch-string-basic-big-var.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-basic-big.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-basic-var.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-basic.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-big-length-tower-var.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-length-tower-var.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-length-tower.js [new file with mode: 0644]
LayoutTests/fast/js/regress/script-tests/switch-string-short.js [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-big-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-big-var-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-big-var.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-big.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-var-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic-var.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-basic.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-big-length-tower-var-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-big-length-tower-var.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-length-tower-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-length-tower-var-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-length-tower-var.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-length-tower.html [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-short-expected.txt [new file with mode: 0644]
LayoutTests/fast/js/regress/switch-string-short.html [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/JumpTable.h
Source/JavaScriptCore/dfg/DFGBackwardsPropagationPhase.cpp
Source/JavaScriptCore/dfg/DFGBinarySwitch.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBinarySwitch.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGByteCodeParser.cpp
Source/JavaScriptCore/dfg/DFGCapabilities.cpp
Source/JavaScriptCore/dfg/DFGFixupPhase.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/DFGOperations.cpp
Source/JavaScriptCore/dfg/DFGOperations.h
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/JavaScriptCore/runtime/Options.h
Source/WTF/ChangeLog
Source/WTF/wtf/text/StringHash.h