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).
(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):
(JSC::DFG::checkAndSet): Deleted.
- dfg/DFGControlEquivalenceAnalysis.h: Added.
(JSC::DFG::ControlEquivalenceAnalysis::ControlEquivalenceAnalysis):
(JSC::DFG::ControlEquivalenceAnalysis::dominatesEquivalently):
(JSC::DFG::ControlEquivalenceAnalysis::areEquivalent):
(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):
(JSC::DFG::Graph::hasDebuggerEnabled):
- dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::operator bool):
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
(JSC::DFG::mayExit):
- dfg/DFGMayExit.h:
- dfg/DFGNode.h:
- dfg/DFGNodeOrigin.cpp:
(JSC::DFG::NodeOrigin::dump):
(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):
(JSC::DFG::OSRExit::OSRExit):
(JSC::DFG::OSRExitBase::considerAddingAsFrequentExitSiteSlow):
(JSC::DFG::OSRExitBase::OSRExitBase):
- dfg/DFGTypeCheckHoistingPhase.cpp:
(JSC::DFG::TypeCheckHoistingPhase::run):
(JSC::FTL::OSRExitDescriptor::prepareOSRExitHandle):
(JSC::FTL::OSRExit::OSRExit):
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::Dominators):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
(WTF::GraphNodeWith::GraphNodeWith):
(WTF::GraphNodeWith::operator bool):
(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):
