DFG plays fast and loose with the shadow values of a Phi
https://bugs.webkit.org/show_bug.cgi?id=164309
Reviewed by Saam Barati.
JSTests:
This test demonstrates why the DFG needs to recognize the shadow value of a Phi.
* stress/dfg-ssa-swap.js: Added.
(foo):
Source/JavaScriptCore:
Oh boy, what an embarrassing mistake! The style of SSA I like to use avoids block/value
tuples as parameters of a Phi, thereby simplifying CFG transformations and making Phi largely
not a special case for most compiler transforms. It does this by introducing another value
called Upsilon, which stores a value into some Phi.
B3 uses this also. The easiest way to understand what Upsilon/Phi behave like is to look at
the B3->Air lowering. Air is not SSA - it has Tmps that you can assign to and use as many
times as you like. B3 allocates one Tmp per Value, and an extra "phiTmp" for Phis, so that
Phis get two Tmps total. Upsilon stores the value into the phiTmp of the Phi, while Phi moves
the value from its phiTmp to its tmp.
This is necessary to support scenarios like this:
a: Phi()
b: Upsilon(@x, ^a)
c: Use(@a)
Here, we want @c to see @a's value before @b. That's a very basic requirement of SSA: that
the a value (like @a) doesn't change during its lifetime.
Unfortunately, DFG's liveness analysis, abstract interpreter, and integer range optimization
all failed to correctly model Upsilon/Phi this way. They would assume that it's accurate to
model the Upsilon as storing into the Phi directly.
Because DFG does flow analysis over SSA, making it correct means enabling it to speak of the
shadow value. This change addresses this problem by introducing the concept of a
NodeFlowProjection. This is a key that lets us speak of both a Node's primary value and its
optional "shadow" value. Liveness, AI, and integer range are now keyed by NodeFlowProjection
rather than Node*. Conceptually this turns out to be a very simple change, but it does touch
a good amount of code.
This looks to be perf-neutral.
Rolled back in after fixing the debug build.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/air/AirLiveness.h:
(JSC::B3::Air::TmpLivenessAdapter::numIndices):
(JSC::B3::Air::StackSlotLivenessAdapter::numIndices):
(JSC::B3::Air::RegLivenessAdapter::numIndices):
(JSC::B3::Air::AbstractLiveness::AbstractLiveness):
(JSC::B3::Air::TmpLivenessAdapter::maxIndex): Deleted.
(JSC::B3::Air::StackSlotLivenessAdapter::maxIndex): Deleted.
(JSC::B3::Air::RegLivenessAdapter::maxIndex): Deleted.
* dfg/DFGAbstractInterpreter.h:
(JSC::DFG::AbstractInterpreter::forNode):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
(JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):
* dfg/DFGAtTailAbstractState.cpp:
(JSC::DFG::AtTailAbstractState::createValueForNode):
(JSC::DFG::AtTailAbstractState::forNode):
* dfg/DFGAtTailAbstractState.h:
* dfg/DFGBasicBlock.h:
* dfg/DFGCombinedLiveness.cpp:
(JSC::DFG::liveNodesAtHead):
* dfg/DFGCombinedLiveness.h:
* dfg/DFGFlowIndexing.cpp: Added.
(JSC::DFG::FlowIndexing::FlowIndexing):
(JSC::DFG::FlowIndexing::~FlowIndexing):
(JSC::DFG::FlowIndexing::recompute):
* dfg/DFGFlowIndexing.h: Added.
(JSC::DFG::FlowIndexing::graph):
(JSC::DFG::FlowIndexing::numIndices):
(JSC::DFG::FlowIndexing::index):
(JSC::DFG::FlowIndexing::shadowIndex):
(JSC::DFG::FlowIndexing::nodeProjection):
* dfg/DFGFlowMap.h: Added.
(JSC::DFG::FlowMap::FlowMap):
(JSC::DFG::FlowMap::resize):
(JSC::DFG::FlowMap::graph):
(JSC::DFG::FlowMap::at):
(JSC::DFG::FlowMap::atShadow):
(WTF::printInternal):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::Graph):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::abstractValuesCache): Deleted.
* dfg/DFGInPlaceAbstractState.cpp:
(JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):
(JSC::DFG::InPlaceAbstractState::beginBasicBlock):
(JSC::DFG::setLiveValues):
(JSC::DFG::InPlaceAbstractState::endBasicBlock):
(JSC::DFG::InPlaceAbstractState::merge):
* dfg/DFGInPlaceAbstractState.h:
(JSC::DFG::InPlaceAbstractState::createValueForNode):
(JSC::DFG::InPlaceAbstractState::forNode):
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* dfg/DFGLivenessAnalysisPhase.cpp:
(JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
(JSC::DFG::LivenessAnalysisPhase::run):
(JSC::DFG::LivenessAnalysisPhase::processBlock):
(JSC::DFG::LivenessAnalysisPhase::addChildUse): Deleted.
* dfg/DFGNode.h:
(JSC::DFG::NodeComparator::operator()):
(JSC::DFG::nodeListDump):
(JSC::DFG::nodeMapDump):
(JSC::DFG::nodeValuePairListDump):
(JSC::DFG::nodeComparator): Deleted.
* dfg/DFGNodeAbstractValuePair.cpp: Added.
(JSC::DFG::NodeAbstractValuePair::dump):
* dfg/DFGNodeAbstractValuePair.h: Added.
(JSC::DFG::NodeAbstractValuePair::NodeAbstractValuePair):
* dfg/DFGNodeFlowProjection.cpp: Added.
(JSC::DFG::NodeFlowProjection::dump):
* dfg/DFGNodeFlowProjection.h: Added.
(JSC::DFG::NodeFlowProjection::NodeFlowProjection):
(JSC::DFG::NodeFlowProjection::operator bool):
(JSC::DFG::NodeFlowProjection::kind):
(JSC::DFG::NodeFlowProjection::node):
(JSC::DFG::NodeFlowProjection::operator*):
(JSC::DFG::NodeFlowProjection::operator->):
(JSC::DFG::NodeFlowProjection::hash):
(JSC::DFG::NodeFlowProjection::operator==):
(JSC::DFG::NodeFlowProjection::operator!=):
(JSC::DFG::NodeFlowProjection::operator<):
(JSC::DFG::NodeFlowProjection::operator>):
(JSC::DFG::NodeFlowProjection::operator<=):
(JSC::DFG::NodeFlowProjection::operator>=):
(JSC::DFG::NodeFlowProjection::isHashTableDeletedValue):
(JSC::DFG::NodeFlowProjection::isStillValid):
(JSC::DFG::NodeFlowProjection::forEach):
(JSC::DFG::NodeFlowProjectionHash::hash):
(JSC::DFG::NodeFlowProjectionHash::equal):
* dfg/DFGStoreBarrierInsertionPhase.cpp:
Source/WTF:
Made this API use size rather than maxIndex as its initialization parameter, because that's
less confusing.
* wtf/IndexSparseSet.h:
(WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@208373 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
index 7adba71..e45ff5a 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
@@ -2817,6 +2817,7 @@
case Phi:
RELEASE_ASSERT(m_graph.m_form == SSA);
+ forNode(node) = forNode(NodeFlowProjection(node, NodeFlowProjection::Shadow));
// The state of this node would have already been decided, but it may have become a
// constant, in which case we'd like to know.
if (forNode(node).m_value)
@@ -2824,8 +2825,11 @@
break;
case Upsilon: {
- m_state.createValueForNode(node->phi());
- forNode(node->phi()) = forNode(node->child1());
+ NodeFlowProjection shadow(node->phi(), NodeFlowProjection::Shadow);
+ if (shadow.isStillValid()) {
+ m_state.createValueForNode(shadow);
+ forNode(shadow) = forNode(node->child1());
+ }
break;
}
@@ -2977,11 +2981,18 @@
else
clobberLimit++;
ASSERT(clobberLimit <= m_state.block()->size());
- for (size_t i = clobberLimit; i--;)
- functor(forNode(m_state.block()->at(i)));
+ for (size_t i = clobberLimit; i--;) {
+ NodeFlowProjection::forEach(
+ m_state.block()->at(i),
+ [&] (NodeFlowProjection nodeProjection) {
+ functor(forNode(nodeProjection));
+ });
+ }
if (m_graph.m_form == SSA) {
- for (Node* node : m_state.block()->ssa->liveAtHead)
- functor(forNode(node));
+ for (NodeFlowProjection node : m_state.block()->ssa->liveAtHead) {
+ if (node.isStillValid())
+ functor(forNode(node));
+ }
}
for (size_t i = m_state.variables().numberOfArguments(); i--;)
functor(m_state.variables().argument(i));
@@ -3037,9 +3048,9 @@
void AbstractInterpreter<AbstractStateType>::dump(PrintStream& out)
{
CommaPrinter comma(" ");
- HashSet<Node*> seen;
+ HashSet<NodeFlowProjection> seen;
if (m_graph.m_form == SSA) {
- for (Node* node : m_state.block()->ssa->liveAtHead) {
+ for (NodeFlowProjection node : m_state.block()->ssa->liveAtHead) {
seen.add(node);
AbstractValue& value = forNode(node);
if (value.isClear())
@@ -3048,15 +3059,17 @@
}
}
for (size_t i = 0; i < m_state.block()->size(); ++i) {
- Node* node = m_state.block()->at(i);
- seen.add(node);
- AbstractValue& value = forNode(node);
- if (value.isClear())
- continue;
- out.print(comma, node, ":", value);
+ NodeFlowProjection::forEach(
+ m_state.block()->at(i), [&] (NodeFlowProjection nodeProjection) {
+ seen.add(nodeProjection);
+ AbstractValue& value = forNode(nodeProjection);
+ if (value.isClear())
+ return;
+ out.print(comma, nodeProjection, ":", value);
+ });
}
if (m_graph.m_form == SSA) {
- for (Node* node : m_state.block()->ssa->liveAtTail) {
+ for (NodeFlowProjection node : m_state.block()->ssa->liveAtTail) {
if (seen.contains(node))
continue;
AbstractValue& value = forNode(node);
