Ignore:
Timestamp:
Nov 3, 2016, 7:37:45 PM (9 years ago)
Author:
[email protected]
Message:

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.

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.cpp

    r207475 r208364  
    4242InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
    4343    : m_graph(graph)
    44     , m_abstractValues(graph.abstractValuesCache())
     44    , m_abstractValues(*graph.m_abstractValuesCache)
    4545    , m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
    4646    , m_block(0)
     
    5858    ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
    5959
    60     // Certain phases insert nodes in a block after running through it.
    61     // We cannot reserve the space for AbstractValues when initializing AbstractState because the number of values
    62     // can increase as we execute. Instead, we increase the size as needed before processing each block.
    63     m_abstractValues.resize(m_graph.maxNodeCount());
    64    
    65     for (size_t i = 0; i < basicBlock->size(); i++)
    66         forNode(basicBlock->at(i)).clear();
     60    m_abstractValues.resize();
     61   
     62    for (size_t i = 0; i < basicBlock->size(); i++) {
     63        NodeFlowProjection::forEach(
     64            basicBlock->at(i), [&] (NodeFlowProjection nodeProjection) {
     65                forNode(nodeProjection).clear();
     66            });
     67    }
    6768
    6869    m_variables = basicBlock->valuesAtHead;
    6970   
    7071    if (m_graph.m_form == SSA) {
    71         for (auto& entry : basicBlock->ssa->valuesAtHead)
    72             forNode(entry.node) = entry.value;
     72        for (NodeAbstractValuePair& entry : basicBlock->ssa->valuesAtHead) {
     73            if (entry.node.isStillValid())
     74                forNode(entry.node) = entry.value;
     75        }
    7376    }
    7477    basicBlock->cfaShouldRevisit = false;
     
    8184}
    8285
    83 static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, const Vector<Node*>& live)
     86static void setLiveValues(Vector<NodeAbstractValuePair>& values, const Vector<NodeFlowProjection>& live)
    8487{
    8588    values.resize(0);
    8689    values.reserveCapacity(live.size());
    87     for (Node* node : live)
    88         values.uncheckedAppend(BasicBlock::SSAData::NodeAbstractValuePair { node, AbstractValue() });
     90    for (NodeFlowProjection node : live)
     91        values.uncheckedAppend(NodeAbstractValuePair { node, AbstractValue() });
    8992}
    9093
     
    200203            block->valuesAtTail[i].merge(m_variables[i]);
    201204
    202         for (auto& valueAtTail : block->ssa->valuesAtTail) {
     205        for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail) {
    203206            AbstractValue& valueAtNode = forNode(valueAtTail.node);
    204207            valueAtTail.value.merge(valueAtNode);
     
    292295            changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
    293296
    294         for (auto& entry : to->ssa->valuesAtHead) {
    295             Node* node = entry.node;
     297        for (NodeAbstractValuePair& entry : to->ssa->valuesAtHead) {
     298            NodeFlowProjection node = entry.node;
    296299            if (verbose)
    297300                dataLog("      Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
    298301#ifndef NDEBUG
    299302            unsigned valueCountInFromBlock = 0;
    300             for (auto& fromBlockValueAtTail : from->ssa->valuesAtTail) {
     303            for (NodeAbstractValuePair& fromBlockValueAtTail : from->ssa->valuesAtTail) {
    301304                if (fromBlockValueAtTail.node == node) {
    302305                    ASSERT(fromBlockValueAtTail.value == forNode(node));
Note: See TracChangeset for help on using the changeset viewer.