Timestamp:
Jul 20, 2016, 11:23:10 PM (9 years ago)
Author:
[email protected]
Message:

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):

File:
1 added

Note: See TracChangeset for help on using the changeset viewer.