FTL B3 should be able to flag the tag constants as being super important so that...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Dec 2015 02:46:22 +0000 (02:46 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 8 Dec 2015 02:46:22 +0000 (02:46 +0000)
commit94d3f0f18f35a918f91e05d54f761b454a2984ae
treec18d91165e6c2f434bb278a4fe1ffc2e7cc2aebe
parente2917bf5dcabd37eeb207f24cbf096b5f2139d14
FTL B3 should be able to flag the tag constants as being super important so that B3 can hoist them and Air can force them into registers
https://bugs.webkit.org/show_bug.cgi?id=151955

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

Taught B3 about the concept of "fast constants". A client of B3 can now tell B3 which
constants are super important. B3 will not spill the constant in that case and will ensure
that the constant is materialized only once: statically once, and dynamically once per
procedure execution. The hoistFastConstants() algorithm in B3MoveConstants.cpp achieves this
by first picking the lowest common dominator of all uses of each fast constant, and then
picking the materialization point by finding the lowest dominator of that dominator that is
tied for lowest block frequency. In practice, the second step ensures that this is the lowest
point in the program that is not in a loop (i.e. executes no more than once dynamically per
procedure invocation).

Taught Air about the concept of "fast tmps". B3 tells Air that a tmp is fast if it is used to
hold the materialization of a fast constant. IRC will use the lowest possible spill score for
fast tmps. In practice, this ensures that fast constants are never spilled.

Added a small snippet of code to FTL::LowerDFGToLLVM that makes both of the tag constants
into fast constants.

My hope is that this very brute-force heuristic is good enough that we don't have to think
about constants for a while. Based on my experience with how LLVM's constant hoisting works
out, the heuristic in this patch is going to be tough to beat. LLVM's constant hoisting does
good things when it hoists the tags, and usually causes nothing but problems when it hoists
anything else. This is because there is no way a low-level compiler to really understand how
a constant materialization impacts some operation's contribution to the overall execution
time of a procedure. But, in the FTL we know that constant materializations for type checks
are a bummer because we are super comfortable placing type checks on the hottest of paths. So
those are the last paths where extra instructions should be added by the compiler. On the
other hand, all other large constant uses are on relatively cold paths, or paths that are
already expensive for other reasons. For example, global variable accesses have to
materialize a pointer to the global. But that's not really a big deal, since a load from a
global involves first the load itself and then type checks on the result - so probably the
constant materialization is just not interesting. A store to a global often involves a store
barrier, so the constant materialization is really not interesting. This patch codifies this
heuristic in a pact between Air, B3, and the FTL: FTL demands that B3 pin the two tags in
registers, and B3 relays the demand to Air.

* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3CFG.h: Added.
(JSC::B3::CFG::CFG):
(JSC::B3::CFG::root):
(JSC::B3::CFG::newMap):
(JSC::B3::CFG::successors):
(JSC::B3::CFG::predecessors):
(JSC::B3::CFG::index):
(JSC::B3::CFG::node):
(JSC::B3::CFG::numNodes):
(JSC::B3::CFG::dump):
* b3/B3Dominators.h: Added.
(JSC::B3::Dominators::Dominators):
* b3/B3IndexMap.h:
(JSC::B3::IndexMap::resize):
(JSC::B3::IndexMap::size):
(JSC::B3::IndexMap::operator[]):
* b3/B3LowerMacros.cpp:
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::tmp):
* b3/B3MoveConstants.cpp:
* b3/B3Opcode.h:
(JSC::B3::constPtrOpcode):
(JSC::B3::isConstant):
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::Procedure):
(JSC::B3::Procedure::resetReachability):
(JSC::B3::Procedure::invalidateCFG):
(JSC::B3::Procedure::dump):
(JSC::B3::Procedure::deleteValue):
(JSC::B3::Procedure::dominators):
(JSC::B3::Procedure::addFastConstant):
(JSC::B3::Procedure::isFastConstant):
(JSC::B3::Procedure::addDataSection):
* b3/B3Procedure.h:
(JSC::B3::Procedure::size):
(JSC::B3::Procedure::cfg):
(JSC::B3::Procedure::setLastPhaseName):
* b3/B3ReduceStrength.cpp:
* b3/B3ValueInlines.h:
(JSC::B3::Value::isConstant):
(JSC::B3::Value::isInteger):
* b3/B3ValueKey.h:
(JSC::B3::ValueKey::canMaterialize):
(JSC::B3::ValueKey::isConstant):
* b3/air/AirCode.cpp:
(JSC::B3::Air::Code::findNextBlock):
(JSC::B3::Air::Code::addFastTmp):
* b3/air/AirCode.h:
(JSC::B3::Air::Code::specials):
(JSC::B3::Air::Code::isFastTmp):
(JSC::B3::Air::Code::setLastPhaseName):
* b3/air/AirIteratedRegisterCoalescing.cpp:
* dfg/DFGDominators.h:
* dfg/DFGSSACalculator.cpp:
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):

Source/WTF:

Remove some remaining DFG-specific snippets from Dominators. This used to be a non-template
DFG class, and some time ago I hoisted it into WTF and made it generic. But since the only
user of the class was the DFG, this class still had a handful of DFG-specific snippets that
didn't compile when I started using it from B3.

Also renamed immediateDominatorOf() to idom(). This is the sort of abbreviation that we
wouldn't ordinarily want to have in WebKit. But WebKit does allow for abbreviations that are
"more canonical". The term "idom" is definitely more canonical than "immediateDominatorOf".

* wtf/Dominators.h:
(WTF::Dominators::dominates):
(WTF::Dominators::idom):
(WTF::Dominators::forAllStrictDominatorsOf):
(WTF::Dominators::NaiveDominators::dominates):
(WTF::Dominators::NaiveDominators::dump):
(WTF::Dominators::ValidationContext::handleErrors):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@193682 268f45cc-cd09-0410-ab3c-d52691b4dbfc
23 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3CFG.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3Dominators.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3IndexMap.h
Source/JavaScriptCore/b3/B3LowerMacros.cpp
Source/JavaScriptCore/b3/B3LowerToAir.cpp
Source/JavaScriptCore/b3/B3MoveConstants.cpp
Source/JavaScriptCore/b3/B3Opcode.h
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/B3ReduceStrength.cpp
Source/JavaScriptCore/b3/B3ValueInlines.h
Source/JavaScriptCore/b3/B3ValueKey.h
Source/JavaScriptCore/b3/air/AirCode.cpp
Source/JavaScriptCore/b3/air/AirCode.h
Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp
Source/JavaScriptCore/dfg/DFGCFG.h
Source/JavaScriptCore/dfg/DFGDominators.h
Source/JavaScriptCore/dfg/DFGSSACalculator.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/Dominators.h