DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succee...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 May 2016 21:25:29 +0000 (21:25 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 19 May 2016 21:25:29 +0000 (21:25 +0000)
commit525aad624f664ee56357b05aaed5530c2e9936e4
treed191f39410fbef3b3399f41975d5c3bb41990da0
parent84df0fc6eae21dbdc14911b3ba7e4f38516369db
DFG::LICMPhase shouldn't hoist type checks unless it knows that the check will succeed at the loop pre-header
https://bugs.webkit.org/show_bug.cgi?id=144527

Reviewed by Saam Barati.

Source/JavaScriptCore:

This adds a control flow equivalence analysis (called ControlEquivalenceAnalysis) based on
dominator analysis over the backwards CFG. Two basic blocks are control flow equivalent if
the execution of one implies that the other one must also execute. It means that the two
blocks' forward and backward dominance are reciprocated: (A dom B and B backdom A) or (B dom
A and A backdom B). LICM now uses it to become more conservative about hoisting checks, if
this has caused problems in the past. If we hoist something that may exit from a block that
was not control equivalent to the pre-header then it's possible that the node's speculation
will fail even though it wouldn't have if it wasn't hoisted. So, we flag these nodes'
origins as being "wasHoisted" and we track all of their exits as "HoistingFailed". LICM will
turn off such speculative hoisting if the CodeBlock from which we are hoisting had the
HoistingFailed exit kind.

Note that this deliberately still allows us to hoist things that may exit even if they are
not control equivalent to the pre-header. This is necessary because the profitability of
hoisting is so huge in all of the cases that we're aware of that it's worth giving it a
shot.

This is neutral on macrobenchmarks since none of the benchmarks we track have a hoistable
operation that would exit only if hoisted. I added microbenchmarks to illustrate the problem
and two of them speed up by ~40% while one of them is neutral (Int52 saves us from having
problems on that program even though LICM previously did the wrong thing).

* JavaScriptCore.xcodeproj/project.pbxproj:
* bytecode/ExitKind.cpp:
(JSC::exitKindToString):
* bytecode/ExitKind.h:
* dfg/DFGAtTailAbstractState.h:
(JSC::DFG::AtTailAbstractState::operator bool):
(JSC::DFG::AtTailAbstractState::initializeTo):
* dfg/DFGBackwardsCFG.h: Added.
(JSC::DFG::BackwardsCFG::BackwardsCFG):
* dfg/DFGBackwardsDominators.h: Added.
(JSC::DFG::BackwardsDominators::BackwardsDominators):
* dfg/DFGCommon.h:
(JSC::DFG::checkAndSet): Deleted.
* dfg/DFGControlEquivalenceAnalysis.h: Added.
(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
(JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
(JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dump):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::ensureBackwardsCFG):
(JSC::DFG::Graph::ensureBackwardsDominators):
(JSC::DFG::Graph::ensureControlEquivalenceAnalysis):
(JSC::DFG::Graph::methodOfGettingAValueProfileFor):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::hasDebuggerEnabled):
* dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::operator bool):
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGMayExit.cpp:
(JSC::DFG::mayExit):
* dfg/DFGMayExit.h:
* dfg/DFGNode.h:
* dfg/DFGNodeOrigin.cpp:
(JSC::DFG::NodeOrigin::dump):
* dfg/DFGNodeOrigin.h:
(JSC::DFG::NodeOrigin::takeValidExit):
(JSC::DFG::NodeOrigin::withWasHoisted):
(JSC::DFG::NodeOrigin::forInsertingAfter):
* dfg/DFGNullAbstractState.h: Added.
(JSC::DFG::NullAbstractState::NullAbstractState):
(JSC::DFG::NullAbstractState::operator bool):
(JSC::DFG::NullAbstractState::forNode):
* dfg/DFGOSRExit.cpp:
(JSC::DFG::OSRExit::OSRExit):
* dfg/DFGOSRExitBase.cpp:
(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
* dfg/DFGOSRExitBase.h:
(JSC::DFG::OSRExitBase::OSRExitBase):
* dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::run):
* ftl/FTLOSRExit.cpp:
(JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
(JSC::FTL::OSRExit::OSRExit):
* ftl/FTLOSRExit.h:

Source/WTF:

This adds an adaptor for graphs called BackwardsGraph. The WTF graph framework is based on
passing around a Graph template argument that follows the protocol shared by DFG::CFG,
B3::CFG, and Air::CFG. These graphs always have a single root node but may have many leaf
nodes. This new BackwardsGraph adaptor reverses the graph by creating a synthetic return
node that it uses as the root in the inverted graph. This currently may resort to some
heuristics in programs that have an infinite loop, but other than that, it'll work well in
the general case.

This allows us to say Dominators<BackwardsGraph<some graph type>> as a way of computing
backwards dominators, which then allows us to easily answer control flow equivalence
queries.

* CMakeLists.txt:
* WTF.xcodeproj/project.pbxproj:
* wtf/BackwardsGraph.h: Added.
(WTF::BackwardsGraph::Node::Node):
(WTF::BackwardsGraph::Node::root):
(WTF::BackwardsGraph::Node::operator==):
(WTF::BackwardsGraph::Node::operator!=):
(WTF::BackwardsGraph::Node::operator bool):
(WTF::BackwardsGraph::Node::isRoot):
(WTF::BackwardsGraph::Node::node):
(WTF::BackwardsGraph::Set::Set):
(WTF::BackwardsGraph::Set::add):
(WTF::BackwardsGraph::Set::remove):
(WTF::BackwardsGraph::Set::contains):
(WTF::BackwardsGraph::Set::dump):
(WTF::BackwardsGraph::Map::Map):
(WTF::BackwardsGraph::Map::clear):
(WTF::BackwardsGraph::Map::size):
(WTF::BackwardsGraph::Map::operator[]):
(WTF::BackwardsGraph::BackwardsGraph):
(WTF::BackwardsGraph::root):
(WTF::BackwardsGraph::newMap):
(WTF::BackwardsGraph::successors):
(WTF::BackwardsGraph::predecessors):
(WTF::BackwardsGraph::index):
(WTF::BackwardsGraph::node):
(WTF::BackwardsGraph::numNodes):
(WTF::BackwardsGraph::dump):
* wtf/Dominators.h:
(WTF::Dominators::Dominators):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
* wtf/GraphNodeWorklist.h:
(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):
* wtf/StdLibExtras.h:
(WTF::callStatelessLambda):
(WTF::checkAndSet):

LayoutTests:

Add tests for LICM hoisting things that would only exit if hoisted.

* js/regress/licm-dragons-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds-expected.txt: Added.
* js/regress/licm-dragons-out-of-bounds.html: Added.
* js/regress/licm-dragons-overflow-expected.txt: Added.
* js/regress/licm-dragons-overflow.html: Added.
* js/regress/licm-dragons.html: Added.
* js/regress/script-tests/licm-dragons-out-of-bounds.js: Added.
(foo):
* js/regress/script-tests/licm-dragons-overflow.js: Added.
(foo):
* js/regress/script-tests/licm-dragons.js: Added.
(foo):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@201182 268f45cc-cd09-0410-ab3c-d52691b4dbfc
42 files changed:
LayoutTests/ChangeLog
LayoutTests/js/regress/licm-dragons-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-out-of-bounds-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-out-of-bounds.html [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-overflow-expected.txt [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons-overflow.html [new file with mode: 0644]
LayoutTests/js/regress/licm-dragons.html [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons-out-of-bounds.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons-overflow.js [new file with mode: 0644]
LayoutTests/js/regress/script-tests/licm-dragons.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/bytecode/ExitKind.cpp
Source/JavaScriptCore/bytecode/ExitKind.h
Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h
Source/JavaScriptCore/dfg/DFGBackwardsCFG.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBackwardsDominators.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCommon.h
Source/JavaScriptCore/dfg/DFGControlEquivalenceAnalysis.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/dfg/DFGMayExit.cpp
Source/JavaScriptCore/dfg/DFGMayExit.h
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGNodeOrigin.cpp
Source/JavaScriptCore/dfg/DFGNodeOrigin.h
Source/JavaScriptCore/dfg/DFGNullAbstractState.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGOSRExit.cpp
Source/JavaScriptCore/dfg/DFGOSRExitBase.cpp
Source/JavaScriptCore/dfg/DFGOSRExitBase.h
Source/JavaScriptCore/dfg/DFGTypeCheckHoistingPhase.cpp
Source/JavaScriptCore/ftl/FTLOSRExit.cpp
Source/JavaScriptCore/ftl/FTLOSRExit.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/BackwardsGraph.h [new file with mode: 0644]
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Dominators.h
Source/WTF/wtf/GraphNodeWorklist.h
Source/WTF/wtf/StdLibExtras.h