Switching on symbols should be fast
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jul 2016 06:23:10 +0000 (06:23 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 21 Jul 2016 06:23:10 +0000 (06:23 +0000)
commit0379b016dd9661fed9fcf7a8e374402f5a57d3c1
tree58f7da13e1bc47cc050ec896717da1a8cd92bcd3
parentf8358bd183f59d065079379a9ea57189a5a3f75c
Switching on symbols should be fast
https://bugs.webkit.org/show_bug.cgi?id=158892

Reviewed by Keith Miller.
Source/JavaScriptCore:

This does two things: fixes some goofs in our lowering of symbol equality and adds a new phase
to B3 to infer switch statements from linear chains of branches.

This changes how we compile equality to Symbols to constant-fold the load of the Symbol's UID.
This is necessary for making switches on Symbols inferrable. This also gives us the ability to
efficiently compile strict equality comparisons of SymbolUse and UntypedUse.

This adds a new phase to B3, which finds chains of branches that test for (in)equality on the
same value and constants, and turns them into a Switch. This can turn O(n) code into
O(log n) code, or even O(1) code if the switch cases are dense.

This can make a big difference in JS. Say you write a switch in which the case statements are
variable resolutions. The bytecode generator cannot use a bytecode switch in this case, since
we're required to evaluate the resolutions in order. But in DFG IR, we will often turn those
variable resolutions into constants, since we do that for any immutable singleton. This means
that B3 will see a chain of Branches: the else case of one Branch will point to a basic block
that does nothing but Branch on equality on the same value as the first Branch.

The inference algorithm is quite simple. The basic building block is the ability to summarize
a block's switch behavior. For a block that ends in a switch, this is just the collection of
switch cases. For a block that ends in a branch, we recognize Branch(Equal(value, const)),
Branch(NotEqual(value, const)), and Branch(value). Each of these are summarized as if they
were one-case switches. We infer a new switch if both some block and its sole predecessor
can be described as switches on the same value, nothing shady is going on (like loops), and
the block in question does no work other than this switch. In that case, the block is killed
and its cases (which we get from the summary) are added to the predecessor's switch. This
algorithm runs to fixpoint.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3InferSwitches.cpp: Added.
(JSC::B3::inferSwitches):
* b3/B3InferSwitches.h: Added.
* b3/B3Procedure.h:
(JSC::B3::Procedure::cfg):
* b3/B3ReduceStrength.cpp:
* b3/B3Value.cpp:
(JSC::B3::Value::performSubstitution):
(JSC::B3::Value::isFree):
(JSC::B3::Value::dumpMeta):
* b3/B3Value.h:
* ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileCheckIdent):
(JSC::FTL::DFG::LowerDFGToB3::compileCompareStrictEq):
(JSC::FTL::DFG::LowerDFGToB3::lowSymbol):
(JSC::FTL::DFG::LowerDFGToB3::lowSymbolUID):
(JSC::FTL::DFG::LowerDFGToB3::lowNonNullObject):

LayoutTests:

* js/regress/bigswitch-indirect-expected.txt: Added.
* js/regress/bigswitch-indirect-symbol-expected.txt: Added.
* js/regress/bigswitch-indirect-symbol-or-undefined-expected.txt: Added.
* js/regress/bigswitch-indirect-symbol-or-undefined.html: Added.
* js/regress/bigswitch-indirect-symbol.html: Added.
* js/regress/bigswitch-indirect.html: Added.
* js/regress/implicit-bigswitch-indirect-symbol-expected.txt: Added.
* js/regress/implicit-bigswitch-indirect-symbol.html: Added.
* js/regress/script-tests/bigswitch-indirect-symbol-or-undefined.js: Added.
(foo):
* js/regress/script-tests/bigswitch-indirect-symbol.js: Added.
(foo):
* js/regress/script-tests/bigswitch-indirect.js: Added.
(foo):
* js/regress/script-tests/implicit-bigswitch-indirect-symbol.js: Added.
(foo):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@203491 268f45cc-cd09-0410-ab3c-d52691b4dbfc
28 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/bigswitch-indirect-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/bigswitch-indirect-symbol-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/bigswitch-indirect-symbol-or-undefined-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/bigswitch-indirect-symbol-or-undefined.html [new file with mode: 0644]
LayoutTests/js/regress/bigswitch-indirect-symbol.html [new file with mode: 0644]
LayoutTests/js/regress/bigswitch-indirect.html [new file with mode: 0644]
LayoutTests/js/regress/implicit-bigswitch-indirect-symbol-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/implicit-bigswitch-indirect-symbol.html [new file with mode: 0644]
LayoutTests/js/regress/script-tests/bigswitch-indirect-symbol-or-undefined.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/bigswitch-indirect-symbol.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/bigswitch-indirect.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/implicit-bigswitch-indirect-symbol.js [new file with mode: 0644]
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3IndexMap.h
Source/JavaScriptCore/b3/B3InferSwitches.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3InferSwitches.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/B3Value.cpp
Source/JavaScriptCore/b3/B3Value.h
Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
Source/JavaScriptCore/dfg/DFGSpeculativeJIT.h
Source/JavaScriptCore/ftl/FTLCapabilities.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp