Changeset 208364 in webkit


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

Location:
trunk
Files:
8 added
22 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r208326 r208364  
     12016-11-03  Filip Pizlo  <[email protected]>
     2
     3        DFG plays fast and loose with the shadow values of a Phi
     4        https://bugs.webkit.org/show_bug.cgi?id=164309
     5
     6        Reviewed by Saam Barati.
     7       
     8        This test demonstrates why the DFG needs to recognize the shadow value of a Phi.
     9
     10        * stress/dfg-ssa-swap.js: Added.
     11        (foo):
     12
    1132016-11-03  Saam Barati  <[email protected]>
    214

  • trunk/Source/JavaScriptCore/CMakeLists.txt

    r208312 r208364  
    313313    dfg/DFGFinalizer.cpp
    314314    dfg/DFGFixupPhase.cpp
     315    dfg/DFGFlowIndexing.cpp
    315316    dfg/DFGFlushFormat.cpp
    316317    dfg/DFGFlushedAt.cpp
    … …  
    344345    dfg/DFGNaturalLoops.cpp
    345346    dfg/DFGNode.cpp
     347    dfg/DFGNodeAbstractValuePair.cpp
    346348    dfg/DFGNodeFlags.cpp
     349    dfg/DFGNodeFlowProjection.cpp
    347350    dfg/DFGNodeOrigin.cpp
    348351    dfg/DFGOSRAvailabilityAnalysisPhase.cpp

  • trunk/Source/JavaScriptCore/ChangeLog

    r208343 r208364  
     12016-11-03  Filip Pizlo  <[email protected]>
     2
     3        DFG plays fast and loose with the shadow values of a Phi
     4        https://bugs.webkit.org/show_bug.cgi?id=164309
     5
     6        Reviewed by Saam Barati.
     7       
     8        Oh boy, what an embarrassing mistake! The style of SSA I like to use avoids block/value
     9        tuples as parameters of a Phi, thereby simplifying CFG transformations and making Phi largely
     10        not a special case for most compiler transforms. It does this by introducing another value
     11        called Upsilon, which stores a value into some Phi.
     12       
     13        B3 uses this also. The easiest way to understand what Upsilon/Phi behave like is to look at
     14        the B3->Air lowering. Air is not SSA - it has Tmps that you can assign to and use as many
     15        times as you like. B3 allocates one Tmp per Value, and an extra "phiTmp" for Phis, so that
     16        Phis get two Tmps total. Upsilon stores the value into the phiTmp of the Phi, while Phi moves
     17        the value from its phiTmp to its tmp.
     18       
     19        This is necessary to support scenarios like this:
     20       
     21            a: Phi()
     22            b: Upsilon(@x, ^a)
     23            c: Use(@a)
     24       
     25        Here, we want @c to see @a's value before @b. That's a very basic requirement of SSA: that
     26        the a value (like @a) doesn't change during its lifetime.
     27       
     28        Unfortunately, DFG's liveness analysis, abstract interpreter, and integer range optimization
     29        all failed to correctly model Upsilon/Phi this way. They would assume that it's accurate to
     30        model the Upsilon as storing into the Phi directly.
     31       
     32        Because DFG does flow analysis over SSA, making it correct means enabling it to speak of the
     33        shadow value. This change addresses this problem by introducing the concept of a
     34        NodeFlowProjection. This is a key that lets us speak of both a Node's primary value and its
     35        optional "shadow" value. Liveness, AI, and integer range are now keyed by NodeFlowProjection
     36        rather than Node*. Conceptually this turns out to be a very simple change, but it does touch
     37        a good amount of code.
     38       
     39        This looks to be perf-neutral.
     40
     41        * CMakeLists.txt:
     42        * JavaScriptCore.xcodeproj/project.pbxproj:
     43        * b3/air/AirLiveness.h:
     44        (JSC::B3::Air::TmpLivenessAdapter::numIndices):
     45        (JSC::B3::Air::StackSlotLivenessAdapter::numIndices):
     46        (JSC::B3::Air::RegLivenessAdapter::numIndices):
     47        (JSC::B3::Air::AbstractLiveness::AbstractLiveness):
     48        (JSC::B3::Air::TmpLivenessAdapter::maxIndex): Deleted.
     49        (JSC::B3::Air::StackSlotLivenessAdapter::maxIndex): Deleted.
     50        (JSC::B3::Air::RegLivenessAdapter::maxIndex): Deleted.
     51        * dfg/DFGAbstractInterpreter.h:
     52        (JSC::DFG::AbstractInterpreter::forNode):
     53        * dfg/DFGAbstractInterpreterInlines.h:
     54        (JSC::DFG::AbstractInterpreter<AbstractStateType>::executeEffects):
     55        (JSC::DFG::AbstractInterpreter<AbstractStateType>::forAllValues):
     56        (JSC::DFG::AbstractInterpreter<AbstractStateType>::dump):
     57        * dfg/DFGAtTailAbstractState.cpp:
     58        (JSC::DFG::AtTailAbstractState::createValueForNode):
     59        (JSC::DFG::AtTailAbstractState::forNode):
     60        * dfg/DFGAtTailAbstractState.h:
     61        * dfg/DFGBasicBlock.h:
     62        * dfg/DFGCombinedLiveness.cpp:
     63        (JSC::DFG::liveNodesAtHead):
     64        * dfg/DFGCombinedLiveness.h:
     65        * dfg/DFGFlowIndexing.cpp: Added.
     66        (JSC::DFG::FlowIndexing::FlowIndexing):
     67        (JSC::DFG::FlowIndexing::~FlowIndexing):
     68        (JSC::DFG::FlowIndexing::recompute):
     69        * dfg/DFGFlowIndexing.h: Added.
     70        (JSC::DFG::FlowIndexing::graph):
     71        (JSC::DFG::FlowIndexing::numIndices):
     72        (JSC::DFG::FlowIndexing::index):
     73        (JSC::DFG::FlowIndexing::shadowIndex):
     74        (JSC::DFG::FlowIndexing::nodeProjection):
     75        * dfg/DFGFlowMap.h: Added.
     76        (JSC::DFG::FlowMap::FlowMap):
     77        (JSC::DFG::FlowMap::resize):
     78        (JSC::DFG::FlowMap::graph):
     79        (JSC::DFG::FlowMap::at):
     80        (JSC::DFG::FlowMap::atShadow):
     81        (WTF::printInternal):
     82        * dfg/DFGGraph.cpp:
     83        (JSC::DFG::Graph::Graph):
     84        * dfg/DFGGraph.h:
     85        (JSC::DFG::Graph::abstractValuesCache): Deleted.
     86        * dfg/DFGInPlaceAbstractState.cpp:
     87        (JSC::DFG::InPlaceAbstractState::InPlaceAbstractState):
     88        (JSC::DFG::InPlaceAbstractState::beginBasicBlock):
     89        (JSC::DFG::setLiveValues):
     90        (JSC::DFG::InPlaceAbstractState::endBasicBlock):
     91        (JSC::DFG::InPlaceAbstractState::merge):
     92        * dfg/DFGInPlaceAbstractState.h:
     93        (JSC::DFG::InPlaceAbstractState::createValueForNode):
     94        (JSC::DFG::InPlaceAbstractState::forNode):
     95        * dfg/DFGIntegerRangeOptimizationPhase.cpp:
     96        * dfg/DFGLivenessAnalysisPhase.cpp:
     97        (JSC::DFG::LivenessAnalysisPhase::LivenessAnalysisPhase):
     98        (JSC::DFG::LivenessAnalysisPhase::run):
     99        (JSC::DFG::LivenessAnalysisPhase::processBlock):
     100        (JSC::DFG::LivenessAnalysisPhase::addChildUse): Deleted.
     101        * dfg/DFGNode.h:
     102        (JSC::DFG::NodeComparator::operator()):
     103        (JSC::DFG::nodeListDump):
     104        (JSC::DFG::nodeMapDump):
     105        (JSC::DFG::nodeValuePairListDump):
     106        (JSC::DFG::nodeComparator): Deleted.
     107        * dfg/DFGNodeAbstractValuePair.cpp: Added.
     108        (JSC::DFG::NodeAbstractValuePair::dump):
     109        * dfg/DFGNodeAbstractValuePair.h: Added.
     110        (JSC::DFG::NodeAbstractValuePair::NodeAbstractValuePair):
     111        * dfg/DFGNodeFlowProjection.cpp: Added.
     112        (JSC::DFG::NodeFlowProjection::dump):
     113        * dfg/DFGNodeFlowProjection.h: Added.
     114        (JSC::DFG::NodeFlowProjection::NodeFlowProjection):
     115        (JSC::DFG::NodeFlowProjection::operator bool):
     116        (JSC::DFG::NodeFlowProjection::kind):
     117        (JSC::DFG::NodeFlowProjection::node):
     118        (JSC::DFG::NodeFlowProjection::operator*):
     119        (JSC::DFG::NodeFlowProjection::operator->):
     120        (JSC::DFG::NodeFlowProjection::hash):
     121        (JSC::DFG::NodeFlowProjection::operator==):
     122        (JSC::DFG::NodeFlowProjection::operator!=):
     123        (JSC::DFG::NodeFlowProjection::operator<):
     124        (JSC::DFG::NodeFlowProjection::operator>):
     125        (JSC::DFG::NodeFlowProjection::operator<=):
     126        (JSC::DFG::NodeFlowProjection::operator>=):
     127        (JSC::DFG::NodeFlowProjection::isHashTableDeletedValue):
     128        (JSC::DFG::NodeFlowProjection::isStillValid):
     129        (JSC::DFG::NodeFlowProjection::forEach):
     130        (JSC::DFG::NodeFlowProjectionHash::hash):
     131        (JSC::DFG::NodeFlowProjectionHash::equal):
     132        * dfg/DFGStoreBarrierInsertionPhase.cpp:
     133
    11342016-11-03  Keith Miller  <[email protected]>
    2135

  • trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r208320 r208364  
    130130                0F1E3A67153A21E2000F9456 /* DFGSilentRegisterSavePlan.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1E3A65153A21DF000F9456 /* DFGSilentRegisterSavePlan.h */; };
    131131                0F1FE51C1922A3BC006987C5 /* AbortReason.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1FE51B1922A3BC006987C5 /* AbortReason.h */; settings = {ATTRIBUTES = (Private, ); }; };
     132                0F20177F1DCADC3300EA5950 /* DFGFlowIndexing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */; };
     133                0F2017801DCADC3500EA5950 /* DFGFlowIndexing.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */; };
     134                0F2017821DCADD4200EA5950 /* DFGFlowMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017811DCADD4000EA5950 /* DFGFlowMap.h */; };
     135                0F2017851DCAE14900EA5950 /* DFGNodeFlowProjection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */; };
     136                0F2017861DCAE14C00EA5950 /* DFGNodeFlowProjection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */; };
     137                0F2017891DCB942400EA5950 /* DFGNodeAbstractValuePair.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */; };
     138                0F20178A1DCB942600EA5950 /* DFGNodeAbstractValuePair.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */; };
    132139                0F20C2591A8013AB00DA3229 /* VirtualRegister.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F20C2581A8013AB00DA3229 /* VirtualRegister.cpp */; };
    133140                0F21C27D14BE727A00ADC64B /* CodeSpecializationKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F21C27914BE727300ADC64B /* CodeSpecializationKind.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    25182525                0F1E3A65153A21DF000F9456 /* DFGSilentRegisterSavePlan.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSilentRegisterSavePlan.h; path = dfg/DFGSilentRegisterSavePlan.h; sourceTree = "<group>"; };
    25192526                0F1FE51B1922A3BC006987C5 /* AbortReason.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AbortReason.h; sourceTree = "<group>"; };
     2527                0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlowIndexing.cpp; path = dfg/DFGFlowIndexing.cpp; sourceTree = "<group>"; };
     2528                0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlowIndexing.h; path = dfg/DFGFlowIndexing.h; sourceTree = "<group>"; };
     2529                0F2017811DCADD4000EA5950 /* DFGFlowMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlowMap.h; path = dfg/DFGFlowMap.h; sourceTree = "<group>"; };
     2530                0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNodeFlowProjection.cpp; path = dfg/DFGNodeFlowProjection.cpp; sourceTree = "<group>"; };
     2531                0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNodeFlowProjection.h; path = dfg/DFGNodeFlowProjection.h; sourceTree = "<group>"; };
     2532                0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNodeAbstractValuePair.cpp; path = dfg/DFGNodeAbstractValuePair.cpp; sourceTree = "<group>"; };
     2533                0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNodeAbstractValuePair.h; path = dfg/DFGNodeAbstractValuePair.h; sourceTree = "<group>"; };
    25202534                0F20C2581A8013AB00DA3229 /* VirtualRegister.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VirtualRegister.cpp; sourceTree = "<group>"; };
    25212535                0F21C27914BE727300ADC64B /* CodeSpecializationKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CodeSpecializationKind.h; sourceTree = "<group>"; };
    … …  
    67306744                                0F2FC77016E12F6F0038D976 /* DFGDCEPhase.cpp */,
    67316745                                0F2FC77116E12F6F0038D976 /* DFGDCEPhase.h */,
    6732                                 E322E5A01DA64435006E7709 /* DFGDOMJITPatchpointParams.cpp */,
    6733                                 E322E5A11DA64435006E7709 /* DFGDOMJITPatchpointParams.h */,
    67346746                                0F8F2B97172F04FD007DBDA5 /* DFGDesiredIdentifiers.cpp */,
    67356747                                0F8F2B98172F04FD007DBDA5 /* DFGDesiredIdentifiers.h */,
    … …  
    67466758                                0F5A1272192D9FDF008764A3 /* DFGDoesGC.h */,
    67476759                                0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
     6760                                E322E5A01DA64435006E7709 /* DFGDOMJITPatchpointParams.cpp */,
     6761                                E322E5A11DA64435006E7709 /* DFGDOMJITPatchpointParams.h */,
    67486762                                0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
    67496763                                0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
    … …  
    67626776                                0F2BDC12151C5D4A00CD8910 /* DFGFixupPhase.cpp */,
    67636777                                0F2BDC13151C5D4A00CD8910 /* DFGFixupPhase.h */,
     6778                                0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */,
     6779                                0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */,
     6780                                0F2017811DCADD4000EA5950 /* DFGFlowMap.h */,
    67646781                                0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */,
    67656782                                0F9D339517FFC4E60073C2BC /* DFGFlushedAt.h */,
    … …  
    68296846                                0FB4B51E16B62772003F696B /* DFGNode.cpp */,
    68306847                                86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
     6848                                0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */,
     6849                                0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */,
    68316850                                0FB4B51F16B62772003F696B /* DFGNodeAllocator.h */,
    68326851                                0FA581B7150E952A00B9A2D9 /* DFGNodeFlags.cpp */,
    68336852                                0FA581B8150E952A00B9A2D9 /* DFGNodeFlags.h */,
     6853                                0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */,
     6854                                0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */,
    68346855                                0F5D085C1B8CF99D001143B4 /* DFGNodeOrigin.cpp */,
    68356856                                0F300B7718AB051100A6D72E /* DFGNodeOrigin.h */,
    … …  
    76137634                                0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */,
    76147635                                0F338E161BF0276C0013C88F /* B3ValueKeyInlines.h in Headers */,
     7636                                0F2017821DCADD4200EA5950 /* DFGFlowMap.h in Headers */,
    76157637                                0FEC85741BDACDC70080FF74 /* AirCCallSpecial.h in Headers */,
    76167638                                0FEC85761BDACDC70080FF74 /* AirCode.h in Headers */,
    … …  
    84998521                                BC18C4270E16F5CD00B34460 /* JSString.h in Headers */,
    85008522                                86E85539111B9968001AF51E /* JSStringBuilder.h in Headers */,
     8523                                0F2017851DCAE14900EA5950 /* DFGNodeFlowProjection.h in Headers */,
    85018524                                E3555B8A1DAE03A500F36921 /* DOMJITCallDOMGetterPatchpoint.h in Headers */,
    85028525                                70EC0EC31AA0D7DA00B6AAFA /* JSStringIterator.h in Headers */,
    … …  
    85968619                                14D2F3DB139F4BE200491031 /* MarkedSpace.h in Headers */,
    85978620                                142D6F1213539A4100B02E86 /* MarkStack.h in Headers */,
     8621                                0F2017891DCB942400EA5950 /* DFGNodeAbstractValuePair.h in Headers */,
    85988622                                8612E4CD152389EC00C836BE /* MatchResult.h in Headers */,
    85998623                                4340A4851A9051AF00D73CCA /* MathCommon.h in Headers */,
    … …  
    86648688                                DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */,
    86658689                                0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
     8690                                0F2017801DCADC3500EA5950 /* DFGFlowIndexing.h in Headers */,
    86668691                                0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
    86678692                                0F4A38FA1C8E13DF00190318 /* SuperSampler.h in Headers */,
    … …  
    98599884                                0FA762041DB9242600B7A2FD /* CollectionScope.cpp in Sources */,
    98609885                                148A7BEF1B82975A002D9157 /* InlineCallFrame.cpp in Sources */,
     9886                                0F20178A1DCB942600EA5950 /* DFGNodeAbstractValuePair.cpp in Sources */,
    98619887                                0F24E55517F0B71C00ABB217 /* InlineCallFrameSet.cpp in Sources */,
    98629888                                A5CEEE14187F3BAD00E55C99 /* InspectorAgent.cpp in Sources */,
    … …  
    1008810114                                14469DDF107EC7E700650446 /* MathObject.cpp in Sources */,
    1008910115                                90213E3D123A40C200D422F3 /* MemoryStatistics.cpp in Sources */,
     10116                                0F20177F1DCADC3300EA5950 /* DFGFlowIndexing.cpp in Sources */,
    1009010117                                0FB5467D14F5CFD6002C2989 /* MethodOfGettingAValueProfile.cpp in Sources */,
    1009110118                                E3794E751B77EB97005543AE /* ModuleAnalyzer.cpp in Sources */,
    … …  
    1018510212                                A5FD006D189B00AA00633231 /* ScriptCallFrame.cpp in Sources */,
    1018610213                                A5FD006F189B00AA00633231 /* ScriptCallStack.cpp in Sources */,
     10214                                0F2017861DCAE14C00EA5950 /* DFGNodeFlowProjection.cpp in Sources */,
    1018710215                                A5FD007D189B0B4C00633231 /* ScriptCallStackFactory.cpp in Sources */,
    1018810216                                A503FA25188EFFFD00110F14 /* ScriptDebugServer.cpp in Sources */,

  • trunk/Source/JavaScriptCore/b3/air/AirLiveness.h

    r206525 r208364  
    4747    TmpLivenessAdapter(Code&) { }
    4848
    49     static unsigned maxIndex(Code& code)
     49    static unsigned numIndices(Code& code)
    5050    {
    5151        unsigned numTmps = code.numTmps(adapterType);
    … …  
    6666    }
    6767
    68     static unsigned maxIndex(Code& code)
    69     {
    70         return code.stackSlots().size() - 1;
     68    static unsigned numIndices(Code& code)
     69    {
     70        return code.stackSlots().size();
    7171    }
    7272    static bool acceptsType(Arg::Type) { return true; }
    … …  
    8484    RegLivenessAdapter(Code&) { }
    8585
    86     static unsigned maxIndex(Code&)
    87     {
    88         return Reg::maxIndex();
     86    static unsigned numIndices(Code&)
     87    {
     88        return Reg::maxIndex() + 1;
    8989    }
    9090
    … …  
    102102    AbstractLiveness(Code& code)
    103103        : Adapter(code)
    104         , m_workset(Adapter::maxIndex(code))
     104        , m_workset(Adapter::numIndices(code))
    105105        , m_liveAtHead(code.size())
    106106        , m_liveAtTail(code.size())

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h

    r206846 r208364  
    3232#include "DFGGraph.h"
    3333#include "DFGNode.h"
     34#include "DFGNodeFlowProjection.h"
    3435#include "DFGPhiChildren.h"
    3536
    … …  
    4243    ~AbstractInterpreter();
    4344   
    44     AbstractValue& forNode(Node* node)
     45    AbstractValue& forNode(NodeFlowProjection node)
    4546    {
    4647        return m_state.forNode(node);

  • trunk/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h

    r208320 r208364  
    28182818    case Phi:
    28192819        RELEASE_ASSERT(m_graph.m_form == SSA);
     2820        forNode(node) = forNode(NodeFlowProjection(node, NodeFlowProjection::Shadow));
    28202821        // The state of this node would have already been decided, but it may have become a
    28212822        // constant, in which case we'd like to know.
    … …  
    28252826       
    28262827    case Upsilon: {
    2827         m_state.createValueForNode(node->phi());
    2828         forNode(node->phi()) = forNode(node->child1());
     2828        NodeFlowProjection shadow(node->phi(), NodeFlowProjection::Shadow);
     2829        if (shadow.isStillValid()) {
     2830            m_state.createValueForNode(shadow);
     2831            forNode(shadow) = forNode(node->child1());
     2832        }
    28292833        break;
    28302834    }
    … …  
    29782982        clobberLimit++;
    29792983    ASSERT(clobberLimit <= m_state.block()->size());
    2980     for (size_t i = clobberLimit; i--;)
    2981         functor(forNode(m_state.block()->at(i)));
     2984    for (size_t i = clobberLimit; i--;) {
     2985        NodeFlowProjection::forEach(
     2986            m_state.block()->at(i),
     2987            [&] (NodeFlowProjection nodeProjection) {
     2988                functor(forNode(nodeProjection));
     2989            });
     2990    }
    29822991    if (m_graph.m_form == SSA) {
    2983         for (Node* node : m_state.block()->ssa->liveAtHead)
    2984             functor(forNode(node));
     2992        for (NodeFlowProjection node : m_state.block()->ssa->liveAtHead) {
     2993            if (node.isStillValid())
     2994                functor(forNode(node));
     2995        }
    29852996    }
    29862997    for (size_t i = m_state.variables().numberOfArguments(); i--;)
    … …  
    30383049{
    30393050    CommaPrinter comma(" ");
    3040     HashSet<Node*> seen;
     3051    HashSet<NodeFlowProjection> seen;
    30413052    if (m_graph.m_form == SSA) {
    3042         for (Node* node : m_state.block()->ssa->liveAtHead) {
     3053        for (NodeFlowProjection node : m_state.block()->ssa->liveAtHead) {
    30433054            seen.add(node);
    30443055            AbstractValue& value = forNode(node);
    … …  
    30493060    }
    30503061    for (size_t i = 0; i < m_state.block()->size(); ++i) {
    3051         Node* node = m_state.block()->at(i);
    3052         seen.add(node);
    3053         AbstractValue& value = forNode(node);
    3054         if (value.isClear())
    3055             continue;
    3056         out.print(comma, node, ":", value);
     3062        NodeFlowProjection::forEach(
     3063            m_state.block()->at(i), [&] (NodeFlowProjection nodeProjection) {
     3064                seen.add(nodeProjection);
     3065                AbstractValue& value = forNode(nodeProjection);
     3066                if (value.isClear())
     3067                    return;
     3068                out.print(comma, nodeProjection, ":", value);
     3069            });
    30573070    }
    30583071    if (m_graph.m_form == SSA) {
    3059         for (Node* node : m_state.block()->ssa->liveAtTail) {
     3072        for (NodeFlowProjection node : m_state.block()->ssa->liveAtTail) {
    30603073            if (seen.contains(node))
    30613074                continue;

  • trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.cpp

    r204130 r208364  
    4848AtTailAbstractState::~AtTailAbstractState() { }
    4949
    50 void AtTailAbstractState::createValueForNode(Node* node)
     50void AtTailAbstractState::createValueForNode(NodeFlowProjection node)
    5151{
    5252    m_valuesAtTailMap.at(m_block).add(node, AbstractValue());
    5353}
    5454
    55 AbstractValue& AtTailAbstractState::forNode(Node* node)
     55AbstractValue& AtTailAbstractState::forNode(NodeFlowProjection node)
    5656{
    5757    auto& valuesAtTail = m_valuesAtTailMap.at(m_block);
    58     HashMap<Node*, AbstractValue>::iterator iter = valuesAtTail.find(node);
    59     DFG_ASSERT(m_graph, node, iter != valuesAtTail.end());
     58    HashMap<NodeFlowProjection, AbstractValue>::iterator iter = valuesAtTail.find(node);
     59    DFG_ASSERT(m_graph, node.node(), iter != valuesAtTail.end());
    6060    return iter->value;
    6161}

  • trunk/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h

    r206525 r208364  
    3232#include "DFGBlockMap.h"
    3333#include "DFGGraph.h"
     34#include "DFGNodeFlowProjection.h"
    3435
    3536namespace JSC { namespace DFG {
    … …  
    4849    }
    4950   
    50     void createValueForNode(Node*);
    51     AbstractValue& forNode(Node*);
     51    void createValueForNode(NodeFlowProjection);
     52    AbstractValue& forNode(NodeFlowProjection);
    5253    AbstractValue& forNode(Edge edge) { return forNode(edge.node()); }
    5354    Operands<AbstractValue>& variables() { return m_block->valuesAtTail; }
    … …  
    6768private:
    6869    Graph& m_graph;
    69     BlockMap<HashMap<Node*, AbstractValue>> m_valuesAtTailMap;
     70    BlockMap<HashMap<NodeFlowProjection, AbstractValue>> m_valuesAtTailMap;
    7071    BasicBlock* m_block { nullptr };
    7172};

  • trunk/Source/JavaScriptCore/dfg/DFGBasicBlock.h

    r207475 r208364  
    11/*
    2  * Copyright (C) 2011, 2013-2015 Apple Inc. All rights reserved.
     2 * Copyright (C) 2011, 2013-2016 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3434#include "DFGFlushedAt.h"
    3535#include "DFGNode.h"
     36#include "DFGNodeAbstractValuePair.h"
    3637#include "DFGNodeOrigin.h"
    3738#include "DFGStructureClobberState.h"
    … …  
    249250        AvailabilityMap availabilityAtTail;
    250251
    251         Vector<Node*> liveAtHead;
    252         Vector<Node*> liveAtTail;
    253         struct NodeAbstractValuePair {
    254             Node* node;
    255             AbstractValue value;
    256         };
     252        Vector<NodeFlowProjection> liveAtHead;
     253        Vector<NodeFlowProjection> liveAtTail;
    257254        Vector<NodeAbstractValuePair> valuesAtHead;
    258255        Vector<NodeAbstractValuePair> valuesAtTail;

  • trunk/Source/JavaScriptCore/dfg/DFGCombinedLiveness.cpp

    r189013 r208364  
    3939{
    4040    HashSet<Node*> seen;
    41     for (Node* node : block->ssa->liveAtHead)
    42         seen.add(node);
     41    for (NodeFlowProjection node : block->ssa->liveAtHead) {
     42        if (node.kind() == NodeFlowProjection::Primary)
     43            seen.add(node.node());
     44    }
    4345   
    4446    AvailabilityMap& availabilityMap = block->ssa->availabilityAtHead;

  • trunk/Source/JavaScriptCore/dfg/DFGCombinedLiveness.h

    r206525 r208364  
    11/*
    2  * Copyright (C) 2015 Apple Inc. All rights reserved.
     2 * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3636HashSet<Node*> liveNodesAtHead(Graph&, BasicBlock*);
    3737
     38// WARNING: This currently does not reason about the liveness of shadow values. The execution
     39// semantics of DFG SSA are that an Upsilon stores to the shadow value of a Phi, and the Phi loads
     40// from that shadow value. Hence, the shadow values are like variables, and have liveness. The normal
     41// liveness analysis will tell you about the liveness of shadow values. It's OK to ignore shadow
     42// values if you treat Upsilon as an opaque escape, and all of the clients of CombinedLiveness do so.
    3843struct CombinedLiveness {
    3944    CombinedLiveness() { }

  • trunk/Source/JavaScriptCore/dfg/DFGGraph.cpp

    r208078 r208364  
    4141#include "DFGControlEquivalenceAnalysis.h"
    4242#include "DFGDominators.h"
     43#include "DFGFlowIndexing.h"
     44#include "DFGFlowMap.h"
    4345#include "DFGJITCode.h"
    4446#include "DFGMayExit.h"
    … …  
    8486   
    8587    m_hasDebuggerEnabled = m_profiledBlock->wasCompiledWithDebuggingOpcodes() || Options::forceDebuggerBytecodeGeneration();
     88   
     89    m_indexingCache = std::make_unique<FlowIndexing>(*this);
     90    m_abstractValuesCache = std::make_unique<FlowMap<AbstractValue>>(*this);
    8691}
    8792

  • trunk/Source/JavaScriptCore/dfg/DFGGraph.h

    r208077 r208364  
    6060class ControlEquivalenceAnalysis;
    6161class Dominators;
     62class FlowIndexing;
    6263class NaturalLoops;
    6364class PrePostNumbering;
     65
     66template<typename> class FlowMap;
    6467
    6568#define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
    … …  
    201204    Node* nodeAt(unsigned index) const { return m_nodesByIndex[index]; }
    202205    void packNodeIndices();
    203 
    204     Vector<AbstractValue, 0, UnsafeVectorOverflow>& abstractValuesCache() { return m_abstractValuesCache; }
    205206
    206207    void dethread();
    … …  
    936937    bool m_hasDebuggerEnabled;
    937938    bool m_hasExceptionHandlers { false };
     939    std::unique_ptr<FlowIndexing> m_indexingCache;
     940    std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
     941
    938942private:
    939943    void addNodeToMapByIndex(Node*);
    … …  
    973977    Vector<Node*, 0, UnsafeVectorOverflow> m_nodesByIndex;
    974978    Vector<unsigned, 0, UnsafeVectorOverflow> m_nodeIndexFreeList;
    975     Vector<AbstractValue, 0, UnsafeVectorOverflow> m_abstractValuesCache;
    976979};
    977980

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

  • trunk/Source/JavaScriptCore/dfg/DFGInPlaceAbstractState.h

    r206525 r208364  
    3030#include "DFGAbstractValue.h"
    3131#include "DFGBranchDirection.h"
     32#include "DFGFlowMap.h"
    3233#include "DFGGraph.h"
    3334#include "DFGNode.h"
    … …  
    4445    explicit operator bool() const { return true; }
    4546   
    46     void createValueForNode(Node*) { }
     47    void createValueForNode(NodeFlowProjection) { }
    4748   
    48     AbstractValue& forNode(Node* node)
     49    AbstractValue& forNode(NodeFlowProjection node)
    4950    {
    50         return m_abstractValues[node->index()];
     51        return m_abstractValues.at(node);
    5152    }
    5253   
    … …  
    133134    Graph& m_graph;
    134135
    135     Vector<AbstractValue, 0, UnsafeVectorOverflow>& m_abstractValues;
     136    FlowMap<AbstractValue>& m_abstractValues;
    136137    Operands<AbstractValue> m_variables;
    137138    BasicBlock* m_block;

  • trunk/Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp

    r207369 r208364  
    3333#include "DFGGraph.h"
    3434#include "DFGInsertionSet.h"
     35#include "DFGNodeFlowProjection.h"
    3536#include "DFGPhase.h"
    3637#include "DFGPredictionPropagationPhase.h"
    … …  
    122123    }
    123124   
    124     Relationship(Node* left, Node* right, Kind kind, int offset = 0)
     125    Relationship(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
    125126        : m_left(left)
    126127        , m_right(right)
    … …  
    133134    }
    134135   
    135     static Relationship safeCreate(Node* left, Node* right, Kind kind, int offset = 0)
    136     {
    137         if (!left || !right || left == right)
     136    static Relationship safeCreate(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
     137    {
     138        if (!left.isStillValid() || !right.isStillValid() || left == right)
    138139            return Relationship();
    139140        return Relationship(left, right, kind, offset);
    140141    }
    141142
    142     explicit operator bool() const { return m_left; }
    143    
    144     Node* left() const { return m_left; }
    145     Node* right() const { return m_right; }
     143    explicit operator bool() const { return !!m_left; }
     144   
     145    NodeFlowProjection left() const { return m_left; }
     146    NodeFlowProjection right() const { return m_right; }
    146147    Kind kind() const { return m_kind; }
    147148    int offset() const { return m_offset; }
    … …  
    259260    // side. Returns a null relationship if this relationship cannot say anything about this
    260261    // node.
    261     Relationship forNode(Node* node) const
     262    Relationship forNode(NodeFlowProjection node) const
    262263    {
    263264        if (m_left == node)
    … …  
    268269    }
    269270   
    270     void setLeft(Node* left)
     271    void setLeft(NodeFlowProjection left)
    271272    {
    272273        RELEASE_ASSERT(left != m_right);
    … …  
    985986    }
    986987   
    987     Node* m_left;
    988     Node* m_right;
     988    NodeFlowProjection m_left;
     989    NodeFlowProjection m_right;
    989990    Kind m_kind;
    990991    int m_offset; // This offset can be arbitrarily large.
    991992};
    992993
    993 typedef HashMap<Node*, Vector<Relationship>> RelationshipMap;
     994typedef HashMap<NodeFlowProjection, Vector<Relationship>> RelationshipMap;
    994995
    995996class IntegerRangeOptimizationPhase : public Phase {
    … …  
    13151316                            nonNegative = true;
    13161317                       
    1317                         if (relationship.right() == node->child2()) {
     1318                        if (relationship.right() == node->child2().node()) {
    13181319                            if (relationship.kind() == Relationship::Equal
    13191320                                && relationship.offset() < 0)
    … …  
    14921493           
    14931494        case Upsilon: {
    1494             setRelationship(
    1495                 Relationship::safeCreate(
    1496                     node->child1().node(), node->phi(), Relationship::Equal, 0));
    1497            
    1498             auto iter = m_relationships.find(node->child1().node());
    1499             if (iter != m_relationships.end()) {
    1500                 Vector<Relationship> toAdd;
    1501                 for (Relationship relationship : iter->value) {
    1502                     Relationship newRelationship = relationship;
    1503                     if (node->phi() == newRelationship.right())
    1504                         continue;
    1505                     newRelationship.setLeft(node->phi());
    1506                     toAdd.append(newRelationship);
    1507                 }
    1508                 for (Relationship relationship : toAdd)
    1509                     setRelationship(relationship);
    1510             }
     1495            setEquivalence(
     1496                node->child1().node(),
     1497                NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
     1498            break;
     1499        }
     1500           
     1501        case Phi: {
     1502            setEquivalence(
     1503                NodeFlowProjection(node, NodeFlowProjection::Shadow),
     1504                node);
    15111505            break;
    15121506        }
    … …  
    15171511    }
    15181512   
     1513    void setEquivalence(NodeFlowProjection oldNode, NodeFlowProjection newNode)
     1514    {
     1515        setRelationship(Relationship::safeCreate(oldNode, newNode, Relationship::Equal, 0));
     1516       
     1517        auto iter = m_relationships.find(oldNode);
     1518        if (iter != m_relationships.end()) {
     1519            Vector<Relationship> toAdd;
     1520            for (Relationship relationship : iter->value) {
     1521                Relationship newRelationship = relationship;
     1522                // Avoid creating any kind of self-relationship.
     1523                if (newNode.node() == newRelationship.right().node())
     1524                    continue;
     1525                newRelationship.setLeft(newNode);
     1526                toAdd.append(newRelationship);
     1527            }
     1528            for (Relationship relationship : toAdd)
     1529                setRelationship(relationship);
     1530        }
     1531    }
     1532           
    15191533    void setRelationship(Relationship relationship, unsigned timeToLive = 1)
    15201534    {
    … …  
    16701684        if (m_seenBlocks.add(target)) {
    16711685            // This is a new block. We copy subject to liveness pruning.
    1672             auto isLive = [&] (Node* node) {
     1686            auto isLive = [&] (NodeFlowProjection node) {
    16731687                if (node == m_zero)
    16741688                    return true;
    … …  
    17021716        // shouldn't process blocks until we have processed the block's predecessor because we
    17031717        // are using reverse postorder.
    1704         Vector<Node*> toRemove;
     1718        Vector<NodeFlowProjection> toRemove;
    17051719        bool changed = false;
    17061720        for (auto& entry : m_relationshipsAtHead[target]) {
    … …  
    17921806            changed = true;
    17931807        }
    1794         for (Node* node : toRemove)
     1808        for (NodeFlowProjection node : toRemove)
    17951809            m_relationshipsAtHead[target].remove(node);
    17961810       

  • 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

  • trunk/Source/JavaScriptCore/dfg/DFGNode.h

    r208320 r208364  
    25612561};
    25622562
    2563 inline bool nodeComparator(Node* a, Node* b)
    2564 {
    2565     return a->index() < b->index();
    2566 }
     2563struct NodeComparator {
     2564    template<typename NodePtrType>
     2565    bool operator()(NodePtrType a, NodePtrType b) const
     2566    {
     2567        return a->index() < b->index();
     2568    }
     2569};
    25672570
    25682571template<typename T>
    25692572CString nodeListDump(const T& nodeList)
    25702573{
    2571     return sortedListDump(nodeList, nodeComparator);
     2574    return sortedListDump(nodeList, NodeComparator());
    25722575}
    25732576
    … …  
    25802583        iter != nodeMap.end(); ++iter)
    25812584        keys.append(iter->key);
    2582     std::sort(keys.begin(), keys.end(), nodeComparator);
     2585    std::sort(keys.begin(), keys.end(), NodeComparator());
    25832586    StringPrintStream out;
    25842587    CommaPrinter comma;
    … …  
    25942597    T sortedList = nodeValuePairList;
    25952598    std::sort(sortedList.begin(), sortedList.end(), [](const V& a, const V& b) {
    2596         return nodeComparator(a.node, b.node);
     2599        return NodeComparator()(a.node, b.node);
    25972600    });
    25982601

  • trunk/Source/JavaScriptCore/dfg/DFGStoreBarrierInsertionPhase.cpp

    r206555 r208364  
    127127                    // current epoch. We grow state-at-tail monotonically to ensure convergence.
    128128                    bool thisBlockChanged = false;
    129                     for (Node* node : block->ssa->liveAtTail) {
     129                    for (NodeFlowProjection node : block->ssa->liveAtTail) {
     130                        if (node.kind() == NodeFlowProjection::Shadow)
     131                            continue;
    130132                        if (node->epoch() != m_currentEpoch) {
    131133                            // If the node is older than the current epoch, then we may need to
    132134                            // run a barrier on it in the future. So, add it to the state.
    133                             thisBlockChanged |= m_stateAtTail->at(block).add(node).isNewEntry;
     135                            thisBlockChanged |= m_stateAtTail->at(block).add(node.node()).isNewEntry;
    134136                        }
    135137                    }
    … …  
    179181            m_state->beginBasicBlock(block);
    180182           
    181             for (Node* node : block->ssa->liveAtHead) {
    182                 if (m_stateAtHead->at(block).contains(node)) {
     183            for (NodeFlowProjection node : block->ssa->liveAtHead) {
     184                if (node.kind() == NodeFlowProjection::Shadow)
     185                    continue;
     186                if (m_stateAtHead->at(block).contains(node.node())) {
    183187                    // If previous blocks tell us that this node may need a barrier in the
    184188                    // future, then put it in the ancient primordial epoch. This forces us to
    … …  
    327331               
    328332            case Upsilon:
    329                 m_node->phi()->setEpoch(m_node->epoch());
     333                // Assume the worst for Phis so that we don't have to worry about Phi shadows.
     334                m_node->phi()->setEpoch(Epoch());
    330335                m_node->setEpoch(Epoch());
    331336                break;

  • trunk/Source/WTF/ChangeLog

    r208357 r208364  
     12016-11-03  Filip Pizlo  <[email protected]>
     2
     3        DFG plays fast and loose with the shadow values of a Phi
     4        https://bugs.webkit.org/show_bug.cgi?id=164309
     5
     6        Reviewed by Saam Barati.
     7       
     8        Made this API use size rather than maxIndex as its initialization parameter, because that's
     9        less confusing.
     10
     11        * wtf/IndexSparseSet.h:
     12        (WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
     13
    1142016-11-03  Konstantin Tokarev  <[email protected]>
    215

  • trunk/Source/WTF/wtf/IndexSparseSet.h

    r195298 r208364  
    4646    typedef Vector<unsigned, 0, OverflowHandler> ValueList;
    4747public:
    48     explicit IndexSparseSet(unsigned maxValue);
     48    explicit IndexSparseSet(unsigned size);
    4949
    5050    bool add(unsigned);
    … …  
    6666
    6767template<typename OverflowHandler>
    68 inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned maxValue)
     68inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned size)
    6969{
    70     m_map.resize(maxValue + 1);
     70    m_map.resize(size);
    7171}
    7272
Note: See TracChangeset for help on using the changeset viewer.