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/DFGLivenessAnalysisPhase.cpp

    r204112 r208364  
    3131#include "DFGBasicBlockInlines.h"
    3232#include "DFGBlockMapInlines.h"
     33#include "DFGFlowIndexing.h"
    3334#include "DFGGraph.h"
    3435#include "DFGInsertionSet.h"
     
    4546        : Phase(graph, "liveness analysis")
    4647        , m_dirtyBlocks(m_graph.numBlocks())
     48        , m_indexing(*m_graph.m_indexingCache)
    4749        , m_liveAtHead(m_graph)
    4850        , m_liveAtTail(m_graph)
    49         , m_workset(graph.maxNodeCount() - 1)
    5051    {
     52        m_graph.m_indexingCache->recompute();
     53        m_workset = std::make_unique<IndexSparseSet<UnsafeVectorOverflow>>(m_graph.m_indexingCache->numIndices());
    5154    }
    5255
     
    8184
    8285            {
    83                 const auto& liveAtHeadIndices = m_liveAtHead[blockIndex];
    84                 Vector<Node*>& liveAtHead = block->ssa->liveAtHead;
     86                const Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHeadIndices = m_liveAtHead[blockIndex];
     87                Vector<NodeFlowProjection>& liveAtHead = block->ssa->liveAtHead;
    8588                liveAtHead.resize(0);
    8689                liveAtHead.reserveCapacity(liveAtHeadIndices.size());
    8790                for (unsigned index : liveAtHeadIndices)
    88                     liveAtHead.uncheckedAppend(m_graph.nodeAt(index));
     91                    liveAtHead.uncheckedAppend(m_indexing.nodeProjection(index));
    8992            }
    9093            {
    91                 const auto& liveAtTailIndices = m_liveAtTail[blockIndex];
    92                 Vector<Node*>& liveAtTail = block->ssa->liveAtTail;
     94                const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>& liveAtTailIndices = m_liveAtTail[blockIndex];
     95                Vector<NodeFlowProjection>& liveAtTail = block->ssa->liveAtTail;
    9396                liveAtTail.resize(0);
    9497                liveAtTail.reserveCapacity(liveAtTailIndices.size());
    9598                for (unsigned index : m_liveAtTail[blockIndex])
    96                     liveAtTail.uncheckedAppend(m_graph.nodeAt(index));
     99                    liveAtTail.uncheckedAppend(m_indexing.nodeProjection(index));
    97100            }
    98101        }
     
    107110        ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
    108111
    109         m_workset.clear();
     112        m_workset->clear();
    110113        for (unsigned index : m_liveAtTail[blockIndex])
    111             m_workset.add(index);
     114            m_workset->add(index);
    112115
    113116        for (unsigned nodeIndex = block->size(); nodeIndex--;) {
    114117            Node* node = block->at(nodeIndex);
    115118
    116             // Given an Upsilon:
    117             //
    118             //    n: Upsilon(@x, ^p)
    119             //
    120             // We say that it def's @p and @n and uses @x.
    121             //
    122             // Given a Phi:
    123             //
    124             //    p: Phi()
    125             //
    126             // We say nothing. It's neither a use nor a def.
    127             //
    128             // Given a node:
    129             //
    130             //    n: Thingy(@a, @b, @c)
    131             //
    132             // We say that it def's @n and uses @a, @b, @c.
     119            auto handleEdge = [&] (Edge& edge) {
     120                bool newEntry = m_workset->add(m_indexing.index(edge.node()));
     121                edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
     122            };
    133123           
    134124            switch (node->op()) {
    135125            case Upsilon: {
    136                 ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes.");
     126                ASSERT_WITH_MESSAGE(!m_workset->contains(node->index()), "Upsilon should not be used as defs by other nodes.");
    137127
    138128                Node* phi = node->phi();
    139                 m_workset.remove(phi->index());
    140                 m_workset.add(node->child1()->index());
     129                m_workset->remove(m_indexing.shadowIndex(phi));
     130                handleEdge(node->child1());
    141131                break;
    142132            }
    143133            case Phi: {
     134                m_workset->remove(m_indexing.index(node));
     135                m_workset->add(m_indexing.shadowIndex(node));
    144136                break;
    145137            }
    146138            default:
    147                 m_workset.remove(node->index());
    148                 DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
     139                m_workset->remove(m_indexing.index(node));
     140                m_graph.doToChildren(node, handleEdge);
    149141                break;
    150142            }
     
    152144
    153145        // Update live at head.
    154         auto& liveAtHead = m_liveAtHead[blockIndex];
    155         if (m_workset.size() == liveAtHead.size())
     146        Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHead = m_liveAtHead[blockIndex];
     147        if (m_workset->size() == liveAtHead.size())
    156148            return false;
    157149
    158150        for (unsigned liveIndexAtHead : liveAtHead)
    159             m_workset.remove(liveIndexAtHead);
    160         ASSERT(!m_workset.isEmpty());
     151            m_workset->remove(liveIndexAtHead);
     152        ASSERT(!m_workset->isEmpty());
    161153
    162         liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
    163         for (unsigned newValue : m_workset)
     154        liveAtHead.reserveCapacity(liveAtHead.size() + m_workset->size());
     155        for (unsigned newValue : *m_workset)
    164156            liveAtHead.uncheckedAppend(newValue);
    165157
    166158        bool changedPredecessor = false;
    167159        for (BasicBlock* predecessor : block->predecessors) {
    168             auto& liveAtTail = m_liveAtTail[predecessor];
    169             for (unsigned newValue : m_workset) {
     160            HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>&
     161                liveAtTail = m_liveAtTail[predecessor];
     162            for (unsigned newValue : *m_workset) {
    170163                if (liveAtTail.add(newValue)) {
    171164                    if (!m_dirtyBlocks.quickSet(predecessor->index))
     
    177170    }
    178171
    179     ALWAYS_INLINE void addChildUse(Node*, Edge& edge)
    180     {
    181         bool newEntry = m_workset.add(edge->index());
    182         edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
    183     }
    184 
    185172    // Blocks with new live values at tail.
    186173    BitVector m_dirtyBlocks;
     174   
     175    FlowIndexing& m_indexing;
    187176
    188177    // Live values per block edge.
     
    191180
    192181    // Single sparse set allocated once and used by every basic block.
    193     IndexSparseSet<UnsafeVectorOverflow> m_workset;
     182    std::unique_ptr<IndexSparseSet<UnsafeVectorOverflow>> m_workset;
    194183};
    195184
Note: See TracChangeset for help on using the changeset viewer.