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: http://svn.webkit.org/repository/webkit/trunk@153248 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/LayoutTests/fast/js/regress/script-tests/switch-string-big-length-tower-var.js b/LayoutTests/fast/js/regress/script-tests/switch-string-big-length-tower-var.js
new file mode 100644
index 0000000..b168ac9
--- /dev/null
+++ b/LayoutTests/fast/js/regress/script-tests/switch-string-big-length-tower-var.js
@@ -0,0 +1,30 @@
+function foo(x) {
+ switch (x) {
+ case "fooa": return 1;
+ case "fooab": return 2;
+ case "fooabc": return 3;
+ case "fooabcd": return 4;
+ case "fooabcde": return 5;
+ case "fooabcdef": return 6;
+ case "fooabcdefg": return 7;
+ case "fooabcdefgh": return 8;
+ case "fooabcdefghi": return 9;
+ case "fooabcdefghij": return 10;
+ case "fooabcdefghijk": return 11;
+ case "fooabcdefghijkl": return 12;
+ case "fooabcdefghijklm": return 13;
+ case "fooabcdefghijklmn": return 14;
+ default: return 15;
+ }
+}
+
+var strings = ["a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh", "abcdefghi", "abcdefghij", "abcdefghijk", "abcdefghijkl", "abcdefghijklm", "abcdefghijklmn", "abcdefghijklmno"];
+for (var i = 0; i < strings.length; ++i)
+ strings[i] = "foo" + strings[i];
+
+var result = 0;
+for (var i = 0; i < 1000000; ++i)
+ result += foo(strings[i % strings.length]);
+
+if (result != 7999975)
+ throw "Bad result: " + result;
