Diff
Modified: trunk/JSTests/ChangeLog (208372 => 208373)
--- trunk/JSTests/ChangeLog 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/JSTests/ChangeLog 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,3 +1,15 @@
+2016-11-03 Filip Pizlo <fpi...@apple.com>
+
+ 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.
+
+ This test demonstrates why the DFG needs to recognize the shadow value of a Phi.
+
+ * stress/dfg-ssa-swap.js: Added.
+ (foo):
+
2016-11-03 Commit Queue <commit-qu...@webkit.org>
Unreviewed, rolling out r208364.
Added: trunk/JSTests/stress/dfg-ssa-swap.js (0 => 208373)
--- trunk/JSTests/stress/dfg-ssa-swap.js (rev 0)
+++ trunk/JSTests/stress/dfg-ssa-swap.js 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,8 @@
+var i,c=0;
+function foo()
+{
+ var a=1,b;for(i=0;i<2;++i){[a,b]=[b,a];c++}if(!a^b)throw c
+}
+noInline(foo);
+for(var k = 0; k < 10000; ++k)
+ foo()
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (208372 => 208373)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2016-11-04 05:28:35 UTC (rev 208373)
@@ -312,6 +312,7 @@
dfg/DFGFailedFinalizer.cpp
dfg/DFGFinalizer.cpp
dfg/DFGFixupPhase.cpp
+ dfg/DFGFlowIndexing.cpp
dfg/DFGFlushFormat.cpp
dfg/DFGFlushedAt.cpp
dfg/DFGLiveCatchVariablePreservationPhase.cpp
@@ -343,7 +344,9 @@
dfg/DFGMultiGetByOffsetData.cpp
dfg/DFGNaturalLoops.cpp
dfg/DFGNode.cpp
+ dfg/DFGNodeAbstractValuePair.cpp
dfg/DFGNodeFlags.cpp
+ dfg/DFGNodeFlowProjection.cpp
dfg/DFGNodeOrigin.cpp
dfg/DFGOSRAvailabilityAnalysisPhase.cpp
dfg/DFGOSREntry.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (208372 => 208373)
--- trunk/Source/_javascript_Core/ChangeLog 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/ChangeLog 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,3 +1,138 @@
+2016-11-03 Filip Pizlo <fpi...@apple.com>
+
+ 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.
+
+ 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:
+ * _javascript_Core.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:
+
2016-11-03 Commit Queue <commit-qu...@webkit.org>
Unreviewed, rolling out r208364.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (208372 => 208373)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2016-11-04 05:28:35 UTC (rev 208373)
@@ -129,6 +129,13 @@
0F1E3A471534CBB9000F9456 /* DFGDoubleFormatState.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */; };
0F1E3A67153A21E2000F9456 /* DFGSilentRegisterSavePlan.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1E3A65153A21DF000F9456 /* DFGSilentRegisterSavePlan.h */; };
0F1FE51C1922A3BC006987C5 /* AbortReason.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F1FE51B1922A3BC006987C5 /* AbortReason.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ 0F20177F1DCADC3300EA5950 /* DFGFlowIndexing.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */; };
+ 0F2017801DCADC3500EA5950 /* DFGFlowIndexing.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */; };
+ 0F2017821DCADD4200EA5950 /* DFGFlowMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017811DCADD4000EA5950 /* DFGFlowMap.h */; };
+ 0F2017851DCAE14900EA5950 /* DFGNodeFlowProjection.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */; };
+ 0F2017861DCAE14C00EA5950 /* DFGNodeFlowProjection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */; };
+ 0F2017891DCB942400EA5950 /* DFGNodeAbstractValuePair.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */; };
+ 0F20178A1DCB942600EA5950 /* DFGNodeAbstractValuePair.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */; };
0F20C2591A8013AB00DA3229 /* VirtualRegister.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F20C2581A8013AB00DA3229 /* VirtualRegister.cpp */; };
0F21C27D14BE727A00ADC64B /* CodeSpecializationKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F21C27914BE727300ADC64B /* CodeSpecializationKind.h */; settings = {ATTRIBUTES = (Private, ); }; };
0F21C27F14BEAA8200ADC64B /* BytecodeConventions.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F21C27E14BEAA8000ADC64B /* BytecodeConventions.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -2517,6 +2524,13 @@
0F1E3A501537C2CB000F9456 /* DFGSlowPathGenerator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSlowPathGenerator.h; path = dfg/DFGSlowPathGenerator.h; sourceTree = "<group>"; };
0F1E3A65153A21DF000F9456 /* DFGSilentRegisterSavePlan.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSilentRegisterSavePlan.h; path = dfg/DFGSilentRegisterSavePlan.h; sourceTree = "<group>"; };
0F1FE51B1922A3BC006987C5 /* AbortReason.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AbortReason.h; sourceTree = "<group>"; };
+ 0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGFlowIndexing.cpp; path = dfg/DFGFlowIndexing.cpp; sourceTree = "<group>"; };
+ 0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlowIndexing.h; path = dfg/DFGFlowIndexing.h; sourceTree = "<group>"; };
+ 0F2017811DCADD4000EA5950 /* DFGFlowMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGFlowMap.h; path = dfg/DFGFlowMap.h; sourceTree = "<group>"; };
+ 0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNodeFlowProjection.cpp; path = dfg/DFGNodeFlowProjection.cpp; sourceTree = "<group>"; };
+ 0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNodeFlowProjection.h; path = dfg/DFGNodeFlowProjection.h; sourceTree = "<group>"; };
+ 0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNodeAbstractValuePair.cpp; path = dfg/DFGNodeAbstractValuePair.cpp; sourceTree = "<group>"; };
+ 0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNodeAbstractValuePair.h; path = dfg/DFGNodeAbstractValuePair.h; sourceTree = "<group>"; };
0F20C2581A8013AB00DA3229 /* VirtualRegister.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = VirtualRegister.cpp; sourceTree = "<group>"; };
0F21C27914BE727300ADC64B /* CodeSpecializationKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CodeSpecializationKind.h; sourceTree = "<group>"; };
0F21C27E14BEAA8000ADC64B /* BytecodeConventions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BytecodeConventions.h; sourceTree = "<group>"; };
@@ -6729,8 +6743,6 @@
0FFFC94E14EF909500C72532 /* DFGCSEPhase.h */,
0F2FC77016E12F6F0038D976 /* DFGDCEPhase.cpp */,
0F2FC77116E12F6F0038D976 /* DFGDCEPhase.h */,
- E322E5A01DA64435006E7709 /* DFGDOMJITPatchpointParams.cpp */,
- E322E5A11DA64435006E7709 /* DFGDOMJITPatchpointParams.h */,
0F8F2B97172F04FD007DBDA5 /* DFGDesiredIdentifiers.cpp */,
0F8F2B98172F04FD007DBDA5 /* DFGDesiredIdentifiers.h */,
0FFC92131B94E83E0071DD66 /* DFGDesiredInferredType.h */,
@@ -6745,6 +6757,8 @@
0F5A1271192D9FDF008764A3 /* DFGDoesGC.cpp */,
0F5A1272192D9FDF008764A3 /* DFGDoesGC.h */,
0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
+ E322E5A01DA64435006E7709 /* DFGDOMJITPatchpointParams.cpp */,
+ E322E5A11DA64435006E7709 /* DFGDOMJITPatchpointParams.h */,
0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
0FD3C82214115D0E00FD81CB /* DFGDriver.h */,
@@ -6761,6 +6775,9 @@
A78A976F179738B8009DF744 /* DFGFinalizer.h */,
0F2BDC12151C5D4A00CD8910 /* DFGFixupPhase.cpp */,
0F2BDC13151C5D4A00CD8910 /* DFGFixupPhase.h */,
+ 0F20177D1DCADC3000EA5950 /* DFGFlowIndexing.cpp */,
+ 0F20177E1DCADC3000EA5950 /* DFGFlowIndexing.h */,
+ 0F2017811DCADD4000EA5950 /* DFGFlowMap.h */,
0F9D339417FFC4E60073C2BC /* DFGFlushedAt.cpp */,
0F9D339517FFC4E60073C2BC /* DFGFlushedAt.h */,
A7D89CE817A0B8CC00773AD8 /* DFGFlushFormat.cpp */,
@@ -6828,9 +6845,13 @@
A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
0FB4B51E16B62772003F696B /* DFGNode.cpp */,
86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
+ 0F2017871DCB942200EA5950 /* DFGNodeAbstractValuePair.cpp */,
+ 0F2017881DCB942200EA5950 /* DFGNodeAbstractValuePair.h */,
0FB4B51F16B62772003F696B /* DFGNodeAllocator.h */,
0FA581B7150E952A00B9A2D9 /* DFGNodeFlags.cpp */,
0FA581B8150E952A00B9A2D9 /* DFGNodeFlags.h */,
+ 0F2017831DCAE14700EA5950 /* DFGNodeFlowProjection.cpp */,
+ 0F2017841DCAE14700EA5950 /* DFGNodeFlowProjection.h */,
0F5D085C1B8CF99D001143B4 /* DFGNodeOrigin.cpp */,
0F300B7718AB051100A6D72E /* DFGNodeOrigin.h */,
0FA581B9150E952A00B9A2D9 /* DFGNodeType.h */,
@@ -7612,6 +7633,7 @@
0FEC85721BDACDC70080FF74 /* AirBasicBlock.h in Headers */,
0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */,
0F338E161BF0276C0013C88F /* B3ValueKeyInlines.h in Headers */,
+ 0F2017821DCADD4200EA5950 /* DFGFlowMap.h in Headers */,
0FEC85741BDACDC70080FF74 /* AirCCallSpecial.h in Headers */,
0FEC85761BDACDC70080FF74 /* AirCode.h in Headers */,
0F3730931C0D67EE00052BFA /* AirUseCounts.h in Headers */,
@@ -8498,6 +8520,7 @@
A7C1EAF017987AB600299DB2 /* CLoopStackInlines.h in Headers */,
BC18C4270E16F5CD00B34460 /* JSString.h in Headers */,
86E85539111B9968001AF51E /* JSStringBuilder.h in Headers */,
+ 0F2017851DCAE14900EA5950 /* DFGNodeFlowProjection.h in Headers */,
E3555B8A1DAE03A500F36921 /* DOMJITCallDOMGetterPatchpoint.h in Headers */,
70EC0EC31AA0D7DA00B6AAFA /* JSStringIterator.h in Headers */,
0F070A471D543A8B006E7232 /* CellContainer.h in Headers */,
@@ -8595,6 +8618,7 @@
141448CB13A176EC00F5BA1A /* MarkedBlockSet.h in Headers */,
14D2F3DB139F4BE200491031 /* MarkedSpace.h in Headers */,
142D6F1213539A4100B02E86 /* MarkStack.h in Headers */,
+ 0F2017891DCB942400EA5950 /* DFGNodeAbstractValuePair.h in Headers */,
8612E4CD152389EC00C836BE /* MatchResult.h in Headers */,
4340A4851A9051AF00D73CCA /* MathCommon.h in Headers */,
BC18C43C0E16F5CD00B34460 /* MathObject.h in Headers */,
@@ -8663,6 +8687,7 @@
0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */,
DCEE220D1CEBAF75000C2396 /* DFGNullAbstractState.h in Headers */,
0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
+ 0F2017801DCADC3500EA5950 /* DFGFlowIndexing.h in Headers */,
0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
0F4A38FA1C8E13DF00190318 /* SuperSampler.h in Headers */,
0FF729BC166AD360000F5BA3 /* ProfilerCompiledBytecode.h in Headers */,
@@ -9858,6 +9883,7 @@
A5840E20187B7B8600843B10 /* InjectedScriptModule.cpp in Sources */,
0FA762041DB9242600B7A2FD /* CollectionScope.cpp in Sources */,
148A7BEF1B82975A002D9157 /* InlineCallFrame.cpp in Sources */,
+ 0F20178A1DCB942600EA5950 /* DFGNodeAbstractValuePair.cpp in Sources */,
0F24E55517F0B71C00ABB217 /* InlineCallFrameSet.cpp in Sources */,
A5CEEE14187F3BAD00E55C99 /* InspectorAgent.cpp in Sources */,
A593CF86184038CA00BFCE27 /* InspectorAgentRegistry.cpp in Sources */,
@@ -10087,6 +10113,7 @@
0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */,
14469DDF107EC7E700650446 /* MathObject.cpp in Sources */,
90213E3D123A40C200D422F3 /* MemoryStatistics.cpp in Sources */,
+ 0F20177F1DCADC3300EA5950 /* DFGFlowIndexing.cpp in Sources */,
0FB5467D14F5CFD6002C2989 /* MethodOfGettingAValueProfile.cpp in Sources */,
E3794E751B77EB97005543AE /* ModuleAnalyzer.cpp in Sources */,
E355F3521B7DC85300C50DC5 /* ModuleLoaderPrototype.cpp in Sources */,
@@ -10184,6 +10211,7 @@
A5FD0067189AFE9C00633231 /* ScriptArguments.cpp in Sources */,
A5FD006D189B00AA00633231 /* ScriptCallFrame.cpp in Sources */,
A5FD006F189B00AA00633231 /* ScriptCallStack.cpp in Sources */,
+ 0F2017861DCAE14C00EA5950 /* DFGNodeFlowProjection.cpp in Sources */,
A5FD007D189B0B4C00633231 /* ScriptCallStackFactory.cpp in Sources */,
A503FA25188EFFFD00110F14 /* ScriptDebugServer.cpp in Sources */,
A55D93A5185012A800400DED /* ScriptFunctionCall.cpp in Sources */,
Modified: trunk/Source/_javascript_Core/b3/air/AirLiveness.h (208372 => 208373)
--- trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/b3/air/AirLiveness.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -46,7 +46,7 @@
TmpLivenessAdapter(Code&) { }
- static unsigned maxIndex(Code& code)
+ static unsigned numIndices(Code& code)
{
unsigned numTmps = code.numTmps(adapterType);
return AbsoluteTmpMapper<adapterType>::absoluteIndex(numTmps);
@@ -65,9 +65,9 @@
{
}
- static unsigned maxIndex(Code& code)
+ static unsigned numIndices(Code& code)
{
- return code.stackSlots().size() - 1;
+ return code.stackSlots().size();
}
static bool acceptsType(Arg::Type) { return true; }
static unsigned valueToIndex(StackSlot* stackSlot) { return stackSlot->index(); }
@@ -83,9 +83,9 @@
RegLivenessAdapter(Code&) { }
- static unsigned maxIndex(Code&)
+ static unsigned numIndices(Code&)
{
- return Reg::maxIndex();
+ return Reg::maxIndex() + 1;
}
static bool acceptsType(Arg::Type) { return true; }
@@ -101,7 +101,7 @@
AbstractLiveness(Code& code)
: Adapter(code)
- , m_workset(Adapter::maxIndex(code))
+ , m_workset(Adapter::numIndices(code))
, m_liveAtHead(code.size())
, m_liveAtTail(code.size())
{
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreter.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -31,6 +31,7 @@
#include "DFGBranchDirection.h"
#include "DFGGraph.h"
#include "DFGNode.h"
+#include "DFGNodeFlowProjection.h"
#include "DFGPhiChildren.h"
namespace JSC { namespace DFG {
@@ -41,7 +42,7 @@
AbstractInterpreter(Graph&, AbstractStateType&);
~AbstractInterpreter();
- AbstractValue& forNode(Node* node)
+ AbstractValue& forNode(NodeFlowProjection node)
{
return m_state.forNode(node);
}
Modified: trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGAbstractInterpreterInlines.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -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);
Modified: trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -47,16 +47,16 @@
AtTailAbstractState::~AtTailAbstractState() { }
-void AtTailAbstractState::createValueForNode(Node* node)
+void AtTailAbstractState::createValueForNode(NodeFlowProjection node)
{
m_valuesAtTailMap.at(m_block).add(node, AbstractValue());
}
-AbstractValue& AtTailAbstractState::forNode(Node* node)
+AbstractValue& AtTailAbstractState::forNode(NodeFlowProjection node)
{
auto& valuesAtTail = m_valuesAtTailMap.at(m_block);
- HashMap<Node*, AbstractValue>::iterator iter = valuesAtTail.find(node);
- DFG_ASSERT(m_graph, node, iter != valuesAtTail.end());
+ HashMap<NodeFlowProjection, AbstractValue>::iterator iter = valuesAtTail.find(node);
+ DFG_ASSERT(m_graph, node.node(), iter != valuesAtTail.end());
return iter->value;
}
Modified: trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGAtTailAbstractState.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -31,6 +31,7 @@
#include "DFGBasicBlock.h"
#include "DFGBlockMap.h"
#include "DFGGraph.h"
+#include "DFGNodeFlowProjection.h"
namespace JSC { namespace DFG {
@@ -47,8 +48,8 @@
m_block = block;
}
- void createValueForNode(Node*);
- AbstractValue& forNode(Node*);
+ void createValueForNode(NodeFlowProjection);
+ AbstractValue& forNode(NodeFlowProjection);
AbstractValue& forNode(Edge edge) { return forNode(edge.node()); }
Operands<AbstractValue>& variables() { return m_block->valuesAtTail; }
@@ -66,7 +67,7 @@
private:
Graph& m_graph;
- BlockMap<HashMap<Node*, AbstractValue>> m_valuesAtTailMap;
+ BlockMap<HashMap<NodeFlowProjection, AbstractValue>> m_valuesAtTailMap;
BasicBlock* m_block { nullptr };
};
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011, 2013-2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2013-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -33,6 +33,7 @@
#include "DFGBranchDirection.h"
#include "DFGFlushedAt.h"
#include "DFGNode.h"
+#include "DFGNodeAbstractValuePair.h"
#include "DFGNodeOrigin.h"
#include "DFGStructureClobberState.h"
#include "Operands.h"
@@ -248,12 +249,8 @@
AvailabilityMap availabilityAtHead;
AvailabilityMap availabilityAtTail;
- Vector<Node*> liveAtHead;
- Vector<Node*> liveAtTail;
- struct NodeAbstractValuePair {
- Node* node;
- AbstractValue value;
- };
+ Vector<NodeFlowProjection> liveAtHead;
+ Vector<NodeFlowProjection> liveAtTail;
Vector<NodeAbstractValuePair> valuesAtHead;
Vector<NodeAbstractValuePair> valuesAtTail;
Modified: trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -38,8 +38,10 @@
HashSet<Node*> liveNodesAtHead(Graph& graph, BasicBlock* block)
{
HashSet<Node*> seen;
- for (Node* node : block->ssa->liveAtHead)
- seen.add(node);
+ for (NodeFlowProjection node : block->ssa->liveAtHead) {
+ if (node.kind() == NodeFlowProjection::Primary)
+ seen.add(node.node());
+ }
AvailabilityMap& availabilityMap = block->ssa->availabilityAtHead;
graph.forAllLocalsLiveInBytecode(
Modified: trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGCombinedLiveness.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -35,6 +35,11 @@
// Returns the set of nodes live at tail, both due to due DFG and due to bytecode (i.e. OSR exit).
HashSet<Node*> liveNodesAtHead(Graph&, BasicBlock*);
+// WARNING: This currently does not reason about the liveness of shadow values. The execution
+// semantics of DFG SSA are that an Upsilon stores to the shadow value of a Phi, and the Phi loads
+// from that shadow value. Hence, the shadow values are like variables, and have liveness. The normal
+// liveness analysis will tell you about the liveness of shadow values. It's OK to ignore shadow
+// values if you treat Upsilon as an opaque escape, and all of the clients of CombinedLiveness do so.
struct CombinedLiveness {
CombinedLiveness() { }
Added: trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.cpp (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,73 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFGFlowIndexing.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+FlowIndexing::FlowIndexing(Graph& graph)
+ : m_graph(graph)
+ , m_numIndices(0)
+{
+ recompute();
+}
+
+FlowIndexing::~FlowIndexing()
+{
+}
+
+void FlowIndexing::recompute()
+{
+ unsigned numNodeIndices = m_graph.maxNodeCount();
+
+ m_nodeIndexToShadowIndex.resize(numNodeIndices);
+ m_nodeIndexToShadowIndex.fill(UINT_MAX);
+
+ m_shadowIndexToNodeIndex.resize(0);
+
+ m_numIndices = numNodeIndices;
+
+ for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
+ for (Node* node : *block) {
+ if (node->op() != Phi)
+ continue;
+
+ unsigned nodeIndex = node->index();
+ unsigned shadowIndex = m_numIndices++;
+ m_nodeIndexToShadowIndex[nodeIndex] = shadowIndex;
+ m_shadowIndexToNodeIndex.append(nodeIndex);
+ DFG_ASSERT(m_graph, nullptr, m_shadowIndexToNodeIndex.size() + numNodeIndices == m_numIndices);
+ DFG_ASSERT(m_graph, nullptr, m_shadowIndexToNodeIndex[shadowIndex - numNodeIndices] == nodeIndex);
+ }
+ }
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.h (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGFlowIndexing.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,112 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include "DFGNodeFlowProjection.h"
+
+namespace JSC { namespace DFG {
+
+// This is a mapping from nodes to unique, dense indices that can be used for creating fast
+// Node-keyed maps. The special part is that it also allocated indices for the shadow values of Phi
+// nodes, which is needed for any flow-sensitive analysis.
+class FlowIndexing {
+public:
+ FlowIndexing(Graph&);
+ ~FlowIndexing();
+
+ void recompute();
+
+ Graph& graph() const { return m_graph; }
+
+ unsigned numIndices() const { return m_numIndices; }
+
+ unsigned index(unsigned nodeIndex) const { return nodeIndex; }
+
+ unsigned index(Node* node) const { return index(node->index()); }
+
+ unsigned shadowIndex(unsigned nodeIndex) const
+ {
+ return m_nodeIndexToShadowIndex[nodeIndex];
+ }
+
+ unsigned shadowIndex(Node* node) const
+ {
+ DFG_ASSERT(m_graph, node, node->op() == Phi);
+ return shadowIndex(node->index());
+ }
+
+ unsigned index(unsigned nodeIndex, NodeFlowProjection::Kind kind) const
+ {
+ switch (kind) {
+ case NodeFlowProjection::Primary:
+ return index(nodeIndex);
+ case NodeFlowProjection::Shadow:
+ return shadowIndex(nodeIndex);
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return 0;
+ }
+
+ unsigned index(Node *node, NodeFlowProjection::Kind kind) const
+ {
+ switch (kind) {
+ case NodeFlowProjection::Primary:
+ return index(node);
+ case NodeFlowProjection::Shadow:
+ return shadowIndex(node);
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return 0;
+ }
+
+ unsigned index(NodeFlowProjection projection) const
+ {
+ return index(projection.node(), projection.kind());
+ }
+
+ NodeFlowProjection nodeProjection(unsigned index) const
+ {
+ if (index < m_nodeIndexToShadowIndex.size())
+ return NodeFlowProjection(m_graph.nodeAt(index));
+ return NodeFlowProjection(
+ m_graph.nodeAt(m_shadowIndexToNodeIndex[index - m_nodeIndexToShadowIndex.size()]),
+ NodeFlowProjection::Shadow);
+ }
+
+private:
+ Graph& m_graph;
+ unsigned m_numIndices;
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_nodeIndexToShadowIndex;
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_shadowIndexToNodeIndex;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGFlowMap.h (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGFlowMap.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGFlowMap.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGFlowIndexing.h"
+#include "DFGGraph.h"
+#include "DFGNode.h"
+
+namespace JSC { namespace DFG {
+
+// This is a mapping from nodes to values that is useful for flow-sensitive analysis. In such an
+// analysis, at every point in the program we need to consider the values of nodes plus the shadow
+// values of Phis. This makes it easy to do both of those things.
+template<typename T>
+class FlowMap {
+public:
+ FlowMap(Graph& graph)
+ : m_graph(graph)
+ {
+ resize();
+ }
+
+ // Call this if the number of nodes in the graph has changed. Note that this does not reset any
+ // entries.
+ void resize()
+ {
+ m_map.resize(m_graph.maxNodeCount());
+ m_shadowMap.resize(m_graph.maxNodeCount());
+ }
+
+ Graph& graph() const { return m_graph; }
+
+ T& at(unsigned nodeIndex)
+ {
+ return m_map[nodeIndex];
+ }
+
+ T& at(Node* node)
+ {
+ return at(node->index());
+ }
+
+ T& atShadow(unsigned nodeIndex)
+ {
+ return m_shadowMap[nodeIndex];
+ }
+
+ T& atShadow(Node* node)
+ {
+ return atShadow(node->index());
+ }
+
+ T& at(unsigned nodeIndex, NodeFlowProjection::Kind kind)
+ {
+ switch (kind) {
+ case NodeFlowProjection::Primary:
+ return at(nodeIndex);
+ case NodeFlowProjection::Shadow:
+ return atShadow(nodeIndex);
+ }
+ RELEASE_ASSERT_NOT_REACHED();
+ return *bitwise_cast<T*>(nullptr);
+ }
+
+ T& at(Node* node, NodeFlowProjection::Kind kind)
+ {
+ return at(node->index(), kind);
+ }
+
+ T& at(NodeFlowProjection projection)
+ {
+ return at(projection.node(), projection.kind());
+ }
+
+ const T& at(unsigned nodeIndex) const { return const_cast<FlowMap*>(this)->at(nodeIndex); }
+ const T& at(Node* node) const { return const_cast<FlowMap*>(this)->at(node); }
+ const T& atShadow(unsigned nodeIndex) const { return const_cast<FlowMap*>(this)->atShadow(nodeIndex); }
+ const T& atShadow(Node* node) const { return const_cast<FlowMap*>(this)->atShadow(node); }
+ const T& at(unsigned nodeIndex, NodeFlowProjection::Kind kind) const { return const_cast<FlowMap*>(this)->at(nodeIndex, kind); }
+ const T& at(Node* node, NodeFlowProjection::Kind kind) const { return const_cast<FlowMap*>(this)->at(node, kind); }
+ const T& at(NodeFlowProjection projection) const { return const_cast<FlowMap*>(this)->at(projection); }
+
+private:
+ Graph& m_graph;
+ Vector<T, 0, UnsafeVectorOverflow> m_map;
+ Vector<T, 0, UnsafeVectorOverflow> m_shadowMap;
+};
+
+} } // namespace JSC::DFG
+
+namespace WTF {
+
+template<typename T>
+void printInternal(PrintStream& out, const JSC::DFG::FlowMap<T>& map)
+{
+ CommaPrinter comma;
+ for (unsigned i = 0; i < map.graph().maxNodeCount(); ++i) {
+ if (JSC::DFG::Node* node = map.graph().nodeAt(i)) {
+ if (const T& value = map.at(node))
+ out.print(comma, node, "=>", value);
+ }
+ }
+ for (unsigned i = 0; i < map.graph().maxNodeCount(); ++i) {
+ if (JSC::DFG::Node* node = map.graph().nodeAt(i)) {
+ if (const T& value = map.atShadow(node))
+ out.print(comma, "shadow(", node, ")=>", value);
+ }
+ }
+}
+
+} // namespace WTF
+
+#endif // ENABLE(DFG_JIT)
+
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -40,6 +40,8 @@
#include "DFGClobbersExitState.h"
#include "DFGControlEquivalenceAnalysis.h"
#include "DFGDominators.h"
+#include "DFGFlowIndexing.h"
+#include "DFGFlowMap.h"
#include "DFGJITCode.h"
#include "DFGMayExit.h"
#include "DFGNaturalLoops.h"
@@ -83,6 +85,9 @@
ASSERT(m_profiledBlock);
m_hasDebuggerEnabled = m_profiledBlock->wasCompiledWithDebuggingOpcodes() || Options::forceDebuggerBytecodeGeneration();
+
+ m_indexingCache = std::make_unique<FlowIndexing>(*this);
+ m_abstractValuesCache = std::make_unique<FlowMap<AbstractValue>>(*this);
}
Graph::~Graph()
Modified: trunk/Source/_javascript_Core/dfg/DFGGraph.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGGraph.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -59,9 +59,12 @@
class CFG;
class ControlEquivalenceAnalysis;
class Dominators;
+class FlowIndexing;
class NaturalLoops;
class PrePostNumbering;
+template<typename> class FlowMap;
+
#define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do { \
Node* _node = (node); \
if (_node->flags() & NodeHasVarArgs) { \
@@ -201,8 +204,6 @@
Node* nodeAt(unsigned index) const { return m_nodesByIndex[index]; }
void packNodeIndices();
- Vector<AbstractValue, 0, UnsafeVectorOverflow>& abstractValuesCache() { return m_abstractValuesCache; }
-
void dethread();
FrozenValue* freeze(JSValue); // We use weak freezing by default.
@@ -935,6 +936,9 @@
RefCountState m_refCountState;
bool m_hasDebuggerEnabled;
bool m_hasExceptionHandlers { false };
+ std::unique_ptr<FlowIndexing> m_indexingCache;
+ std::unique_ptr<FlowMap<AbstractValue>> m_abstractValuesCache;
+
private:
void addNodeToMapByIndex(Node*);
@@ -972,7 +976,6 @@
Vector<Node*, 0, UnsafeVectorOverflow> m_nodesByIndex;
Vector<unsigned, 0, UnsafeVectorOverflow> m_nodeIndexFreeList;
- Vector<AbstractValue, 0, UnsafeVectorOverflow> m_abstractValuesCache;
};
} } // namespace JSC::DFG
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -41,7 +41,7 @@
InPlaceAbstractState::InPlaceAbstractState(Graph& graph)
: m_graph(graph)
- , m_abstractValues(graph.abstractValuesCache())
+ , m_abstractValues(*graph.m_abstractValuesCache)
, m_variables(m_graph.m_codeBlock->numParameters(), graph.m_localVars)
, m_block(0)
{
@@ -57,19 +57,22 @@
ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
- // Certain phases insert nodes in a block after running through it.
- // We cannot reserve the space for AbstractValues when initializing AbstractState because the number of values
- // can increase as we execute. Instead, we increase the size as needed before processing each block.
- m_abstractValues.resize(m_graph.maxNodeCount());
+ m_abstractValues.resize();
- for (size_t i = 0; i < basicBlock->size(); i++)
- forNode(basicBlock->at(i)).clear();
+ for (size_t i = 0; i < basicBlock->size(); i++) {
+ NodeFlowProjection::forEach(
+ basicBlock->at(i), [&] (NodeFlowProjection nodeProjection) {
+ forNode(nodeProjection).clear();
+ });
+ }
m_variables = basicBlock->valuesAtHead;
if (m_graph.m_form == SSA) {
- for (auto& entry : basicBlock->ssa->valuesAtHead)
- forNode(entry.node) = entry.value;
+ for (NodeAbstractValuePair& entry : basicBlock->ssa->valuesAtHead) {
+ if (entry.node.isStillValid())
+ forNode(entry.node) = entry.value;
+ }
}
basicBlock->cfaShouldRevisit = false;
basicBlock->cfaHasVisited = true;
@@ -80,12 +83,12 @@
m_structureClobberState = basicBlock->cfaStructureClobberStateAtHead;
}
-static void setLiveValues(Vector<BasicBlock::SSAData::NodeAbstractValuePair>& values, const Vector<Node*>& live)
+static void setLiveValues(Vector<NodeAbstractValuePair>& values, const Vector<NodeFlowProjection>& live)
{
values.resize(0);
values.reserveCapacity(live.size());
- for (Node* node : live)
- values.uncheckedAppend(BasicBlock::SSAData::NodeAbstractValuePair { node, AbstractValue() });
+ for (NodeFlowProjection node : live)
+ values.uncheckedAppend(NodeAbstractValuePair { node, AbstractValue() });
}
void InPlaceAbstractState::initialize()
@@ -199,7 +202,7 @@
for (size_t i = 0; i < block->valuesAtTail.size(); ++i)
block->valuesAtTail[i].merge(m_variables[i]);
- for (auto& valueAtTail : block->ssa->valuesAtTail) {
+ for (NodeAbstractValuePair& valueAtTail : block->ssa->valuesAtTail) {
AbstractValue& valueAtNode = forNode(valueAtTail.node);
valueAtTail.value.merge(valueAtNode);
valueAtNode = valueAtTail.value;
@@ -291,13 +294,13 @@
for (size_t i = from->valuesAtTail.size(); i--;)
changed |= to->valuesAtHead[i].merge(from->valuesAtTail[i]);
- for (auto& entry : to->ssa->valuesAtHead) {
- Node* node = entry.node;
+ for (NodeAbstractValuePair& entry : to->ssa->valuesAtHead) {
+ NodeFlowProjection node = entry.node;
if (verbose)
dataLog(" Merging for ", node, ": from ", forNode(node), " to ", entry.value, "\n");
#ifndef NDEBUG
unsigned valueCountInFromBlock = 0;
- for (auto& fromBlockValueAtTail : from->ssa->valuesAtTail) {
+ for (NodeAbstractValuePair& fromBlockValueAtTail : from->ssa->valuesAtTail) {
if (fromBlockValueAtTail.node == node) {
ASSERT(fromBlockValueAtTail.value == forNode(node));
++valueCountInFromBlock;
Modified: trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGInPlaceAbstractState.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -29,6 +29,7 @@
#include "DFGAbstractValue.h"
#include "DFGBranchDirection.h"
+#include "DFGFlowMap.h"
#include "DFGGraph.h"
#include "DFGNode.h"
@@ -43,11 +44,11 @@
explicit operator bool() const { return true; }
- void createValueForNode(Node*) { }
+ void createValueForNode(NodeFlowProjection) { }
- AbstractValue& forNode(Node* node)
+ AbstractValue& forNode(NodeFlowProjection node)
{
- return m_abstractValues[node->index()];
+ return m_abstractValues.at(node);
}
AbstractValue& forNode(Edge edge)
@@ -132,7 +133,7 @@
Graph& m_graph;
- Vector<AbstractValue, 0, UnsafeVectorOverflow>& m_abstractValues;
+ FlowMap<AbstractValue>& m_abstractValues;
Operands<AbstractValue> m_variables;
BasicBlock* m_block;
Modified: trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGIntegerRangeOptimizationPhase.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -32,6 +32,7 @@
#include "DFGBlockSet.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
+#include "DFGNodeFlowProjection.h"
#include "DFGPhase.h"
#include "DFGPredictionPropagationPhase.h"
#include "DFGVariableAccessDataDump.h"
@@ -121,7 +122,7 @@
{
}
- Relationship(Node* left, Node* right, Kind kind, int offset = 0)
+ Relationship(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
: m_left(left)
, m_right(right)
, m_kind(kind)
@@ -132,17 +133,17 @@
RELEASE_ASSERT(m_left != m_right);
}
- static Relationship safeCreate(Node* left, Node* right, Kind kind, int offset = 0)
+ static Relationship safeCreate(NodeFlowProjection left, NodeFlowProjection right, Kind kind, int offset = 0)
{
- if (!left || !right || left == right)
+ if (!left.isStillValid() || !right.isStillValid() || left == right)
return Relationship();
return Relationship(left, right, kind, offset);
}
- explicit operator bool() const { return m_left; }
+ explicit operator bool() const { return !!m_left; }
- Node* left() const { return m_left; }
- Node* right() const { return m_right; }
+ NodeFlowProjection left() const { return m_left; }
+ NodeFlowProjection right() const { return m_right; }
Kind kind() const { return m_kind; }
int offset() const { return m_offset; }
@@ -258,7 +259,7 @@
// If possible, returns a form of this relationship where the given node is the left
// side. Returns a null relationship if this relationship cannot say anything about this
// node.
- Relationship forNode(Node* node) const
+ Relationship forNode(NodeFlowProjection node) const
{
if (m_left == node)
return *this;
@@ -267,7 +268,7 @@
return Relationship();
}
- void setLeft(Node* left)
+ void setLeft(NodeFlowProjection left)
{
RELEASE_ASSERT(left != m_right);
m_left = left;
@@ -984,13 +985,13 @@
RELEASE_ASSERT_NOT_REACHED();
}
- Node* m_left;
- Node* m_right;
+ NodeFlowProjection m_left;
+ NodeFlowProjection m_right;
Kind m_kind;
int m_offset; // This offset can be arbitrarily large.
};
-typedef HashMap<Node*, Vector<Relationship>> RelationshipMap;
+typedef HashMap<NodeFlowProjection, Vector<Relationship>> RelationshipMap;
class IntegerRangeOptimizationPhase : public Phase {
public:
@@ -1314,7 +1315,7 @@
if (relationship.minValueOfLeft() >= 0)
nonNegative = true;
- if (relationship.right() == node->child2()) {
+ if (relationship.right() == node->child2().node()) {
if (relationship.kind() == Relationship::Equal
&& relationship.offset() < 0)
lessThanLength = true;
@@ -1491,23 +1492,16 @@
}
case Upsilon: {
- setRelationship(
- Relationship::safeCreate(
- node->child1().node(), node->phi(), Relationship::Equal, 0));
+ setEquivalence(
+ node->child1().node(),
+ NodeFlowProjection(node->phi(), NodeFlowProjection::Shadow));
+ break;
+ }
- auto iter = m_relationships.find(node->child1().node());
- if (iter != m_relationships.end()) {
- Vector<Relationship> toAdd;
- for (Relationship relationship : iter->value) {
- Relationship newRelationship = relationship;
- if (node->phi() == newRelationship.right())
- continue;
- newRelationship.setLeft(node->phi());
- toAdd.append(newRelationship);
- }
- for (Relationship relationship : toAdd)
- setRelationship(relationship);
- }
+ case Phi: {
+ setEquivalence(
+ NodeFlowProjection(node, NodeFlowProjection::Shadow),
+ node);
break;
}
@@ -1516,6 +1510,26 @@
}
}
+ void setEquivalence(NodeFlowProjection oldNode, NodeFlowProjection newNode)
+ {
+ setRelationship(Relationship::safeCreate(oldNode, newNode, Relationship::Equal, 0));
+
+ auto iter = m_relationships.find(oldNode);
+ if (iter != m_relationships.end()) {
+ Vector<Relationship> toAdd;
+ for (Relationship relationship : iter->value) {
+ Relationship newRelationship = relationship;
+ // Avoid creating any kind of self-relationship.
+ if (newNode.node() == newRelationship.right().node())
+ continue;
+ newRelationship.setLeft(newNode);
+ toAdd.append(newRelationship);
+ }
+ for (Relationship relationship : toAdd)
+ setRelationship(relationship);
+ }
+ }
+
void setRelationship(Relationship relationship, unsigned timeToLive = 1)
{
setRelationship(m_relationships, relationship, timeToLive);
@@ -1669,7 +1683,7 @@
if (m_seenBlocks.add(target)) {
// This is a new block. We copy subject to liveness pruning.
- auto isLive = [&] (Node* node) {
+ auto isLive = [&] (NodeFlowProjection node) {
if (node == m_zero)
return true;
return target->ssa->liveAtHead.contains(node);
@@ -1701,7 +1715,7 @@
// assigned would only happen if we have not processed the node's predecessor. We
// shouldn't process blocks until we have processed the block's predecessor because we
// are using reverse postorder.
- Vector<Node*> toRemove;
+ Vector<NodeFlowProjection> toRemove;
bool changed = false;
for (auto& entry : m_relationshipsAtHead[target]) {
auto iter = relationshipMap.find(entry.key);
@@ -1791,7 +1805,7 @@
entry.value = mergedRelationships;
changed = true;
}
- for (Node* node : toRemove)
+ for (NodeFlowProjection node : toRemove)
m_relationshipsAtHead[target].remove(node);
return changed;
Modified: trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGLivenessAnalysisPhase.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -30,6 +30,7 @@
#include "DFGBasicBlockInlines.h"
#include "DFGBlockMapInlines.h"
+#include "DFGFlowIndexing.h"
#include "DFGGraph.h"
#include "DFGInsertionSet.h"
#include "DFGPhase.h"
@@ -44,10 +45,12 @@
LivenessAnalysisPhase(Graph& graph)
: Phase(graph, "liveness analysis")
, m_dirtyBlocks(m_graph.numBlocks())
+ , m_indexing(*m_graph.m_indexingCache)
, m_liveAtHead(m_graph)
, m_liveAtTail(m_graph)
- , m_workset(graph.maxNodeCount() - 1)
{
+ m_graph.m_indexingCache->recompute();
+ m_workset = std::make_unique<IndexSparseSet<UnsafeVectorOverflow>>(m_graph.m_indexingCache->numIndices());
}
bool run()
@@ -80,20 +83,20 @@
continue;
{
- const auto& liveAtHeadIndices = m_liveAtHead[blockIndex];
- Vector<Node*>& liveAtHead = block->ssa->liveAtHead;
+ const Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHeadIndices = m_liveAtHead[blockIndex];
+ Vector<NodeFlowProjection>& liveAtHead = block->ssa->liveAtHead;
liveAtHead.resize(0);
liveAtHead.reserveCapacity(liveAtHeadIndices.size());
for (unsigned index : liveAtHeadIndices)
- liveAtHead.uncheckedAppend(m_graph.nodeAt(index));
+ liveAtHead.uncheckedAppend(m_indexing.nodeProjection(index));
}
{
- const auto& liveAtTailIndices = m_liveAtTail[blockIndex];
- Vector<Node*>& liveAtTail = block->ssa->liveAtTail;
+ const HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>& liveAtTailIndices = m_liveAtTail[blockIndex];
+ Vector<NodeFlowProjection>& liveAtTail = block->ssa->liveAtTail;
liveAtTail.resize(0);
liveAtTail.reserveCapacity(liveAtTailIndices.size());
for (unsigned index : m_liveAtTail[blockIndex])
- liveAtTail.uncheckedAppend(m_graph.nodeAt(index));
+ liveAtTail.uncheckedAppend(m_indexing.nodeProjection(index));
}
}
@@ -106,67 +109,57 @@
BasicBlock* block = m_graph.block(blockIndex);
ASSERT_WITH_MESSAGE(block, "Only dirty blocks needs updates. A null block should never be dirty.");
- m_workset.clear();
+ m_workset->clear();
for (unsigned index : m_liveAtTail[blockIndex])
- m_workset.add(index);
+ m_workset->add(index);
for (unsigned nodeIndex = block->size(); nodeIndex--;) {
Node* node = block->at(nodeIndex);
- // Given an Upsilon:
- //
- // n: Upsilon(@x, ^p)
- //
- // We say that it def's @p and @n and uses @x.
- //
- // Given a Phi:
- //
- // p: Phi()
- //
- // We say nothing. It's neither a use nor a def.
- //
- // Given a node:
- //
- // n: Thingy(@a, @b, @c)
- //
- // We say that it def's @n and uses @a, @b, @c.
+ auto handleEdge = [&] (Edge& edge) {
+ bool newEntry = m_workset->add(m_indexing.index(edge.node()));
+ edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
+ };
switch (node->op()) {
case Upsilon: {
- ASSERT_WITH_MESSAGE(!m_workset.contains(node->index()), "Upsilon should not be used as defs by other nodes.");
+ ASSERT_WITH_MESSAGE(!m_workset->contains(node->index()), "Upsilon should not be used as defs by other nodes.");
Node* phi = node->phi();
- m_workset.remove(phi->index());
- m_workset.add(node->child1()->index());
+ m_workset->remove(m_indexing.shadowIndex(phi));
+ handleEdge(node->child1());
break;
}
case Phi: {
+ m_workset->remove(m_indexing.index(node));
+ m_workset->add(m_indexing.shadowIndex(node));
break;
}
default:
- m_workset.remove(node->index());
- DFG_NODE_DO_TO_CHILDREN(m_graph, node, addChildUse);
+ m_workset->remove(m_indexing.index(node));
+ m_graph.doToChildren(node, handleEdge);
break;
}
}
// Update live at head.
- auto& liveAtHead = m_liveAtHead[blockIndex];
- if (m_workset.size() == liveAtHead.size())
+ Vector<unsigned, 0, UnsafeVectorOverflow, 1>& liveAtHead = m_liveAtHead[blockIndex];
+ if (m_workset->size() == liveAtHead.size())
return false;
for (unsigned liveIndexAtHead : liveAtHead)
- m_workset.remove(liveIndexAtHead);
- ASSERT(!m_workset.isEmpty());
+ m_workset->remove(liveIndexAtHead);
+ ASSERT(!m_workset->isEmpty());
- liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
- for (unsigned newValue : m_workset)
+ liveAtHead.reserveCapacity(liveAtHead.size() + m_workset->size());
+ for (unsigned newValue : *m_workset)
liveAtHead.uncheckedAppend(newValue);
bool changedPredecessor = false;
for (BasicBlock* predecessor : block->predecessors) {
- auto& liveAtTail = m_liveAtTail[predecessor];
- for (unsigned newValue : m_workset) {
+ HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>&
+ liveAtTail = m_liveAtTail[predecessor];
+ for (unsigned newValue : *m_workset) {
if (liveAtTail.add(newValue)) {
if (!m_dirtyBlocks.quickSet(predecessor->index))
changedPredecessor = true;
@@ -176,14 +169,10 @@
return changedPredecessor;
}
- ALWAYS_INLINE void addChildUse(Node*, Edge& edge)
- {
- bool newEntry = m_workset.add(edge->index());
- edge.setKillStatus(newEntry ? DoesKill : DoesNotKill);
- }
-
// Blocks with new live values at tail.
BitVector m_dirtyBlocks;
+
+ FlowIndexing& m_indexing;
// Live values per block edge.
BlockMap<Vector<unsigned, 0, UnsafeVectorOverflow, 1>> m_liveAtHead;
@@ -190,7 +179,7 @@
BlockMap<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_liveAtTail;
// Single sparse set allocated once and used by every basic block.
- IndexSparseSet<UnsafeVectorOverflow> m_workset;
+ std::unique_ptr<IndexSparseSet<UnsafeVectorOverflow>> m_workset;
};
bool performLivenessAnalysis(Graph& graph)
Modified: trunk/Source/_javascript_Core/dfg/DFGNode.h (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGNode.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -2560,15 +2560,18 @@
BasicBlock* owner;
};
-inline bool nodeComparator(Node* a, Node* b)
-{
- return a->index() < b->index();
-}
+struct NodeComparator {
+ template<typename NodePtrType>
+ bool operator()(NodePtrType a, NodePtrType b) const
+ {
+ return a->index() < b->index();
+ }
+};
template<typename T>
CString nodeListDump(const T& nodeList)
{
- return sortedListDump(nodeList, nodeComparator);
+ return sortedListDump(nodeList, NodeComparator());
}
template<typename T>
@@ -2579,7 +2582,7 @@
typename T::const_iterator iter = nodeMap.begin();
iter != nodeMap.end(); ++iter)
keys.append(iter->key);
- std::sort(keys.begin(), keys.end(), nodeComparator);
+ std::sort(keys.begin(), keys.end(), NodeComparator());
StringPrintStream out;
CommaPrinter comma;
for(unsigned i = 0; i < keys.size(); ++i)
@@ -2593,7 +2596,7 @@
using V = typename T::ValueType;
T sortedList = nodeValuePairList;
std::sort(sortedList.begin(), sortedList.end(), [](const V& a, const V& b) {
- return nodeComparator(a.node, b.node);
+ return NodeComparator()(a.node, b.node);
});
StringPrintStream out;
Added: trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.cpp (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFGNodeAbstractValuePair.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+void NodeAbstractValuePair::dump(PrintStream& out) const
+{
+ out.print(node, "=>", value);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.h (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeAbstractValuePair.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,53 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAbstractValue.h"
+#include "DFGNodeFlowProjection.h"
+
+namespace JSC { namespace DFG {
+
+struct NodeAbstractValuePair {
+ NodeAbstractValuePair() { }
+
+ NodeAbstractValuePair(NodeFlowProjection node, const AbstractValue& value)
+ : node(node)
+ , value(value)
+ {
+ }
+
+ void dump(PrintStream& out) const;
+
+ NodeFlowProjection node;
+ AbstractValue value;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.cpp (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.cpp (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "DFGNodeFlowProjection.h"
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+void NodeFlowProjection::dump(PrintStream& out) const
+{
+ if (!*this) {
+ out.print("-");
+ return;
+ }
+ if (kind() == Primary) {
+ out.print(node());
+ return;
+ }
+ out.print("shadow(", node(), ")");
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
Added: trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.h (0 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.h (rev 0)
+++ trunk/Source/_javascript_Core/dfg/DFGNodeFlowProjection.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGNode.h"
+#include <wtf/HashTable.h>
+
+namespace JSC { namespace DFG {
+
+class NodeFlowProjection {
+public:
+ enum Kind {
+ Primary,
+ Shadow
+ };
+
+ NodeFlowProjection() { }
+
+ NodeFlowProjection(Node* node)
+ : m_word(bitwise_cast<uintptr_t>(node))
+ {
+ ASSERT(kind() == Primary);
+ }
+
+ NodeFlowProjection(Node* node, Kind kind)
+ : m_word(bitwise_cast<uintptr_t>(node) | (kind == Shadow ? shadowBit : 0))
+ {
+ ASSERT(this->kind() == kind);
+ }
+
+ NodeFlowProjection(WTF::HashTableDeletedValueType)
+ : m_word(shadowBit)
+ {
+ }
+
+ explicit operator bool() const { return !!m_word; }
+
+ Kind kind() const { return (m_word & shadowBit) ? Shadow : Primary; }
+
+ Node* node() const { return bitwise_cast<Node*>(m_word & ~shadowBit); }
+
+ Node& operator*() const { return *node(); }
+ Node* operator->() const { return node(); }
+
+ unsigned hash() const
+ {
+ return m_word;
+ }
+
+ bool operator==(NodeFlowProjection other) const
+ {
+ return m_word == other.m_word;
+ }
+
+ bool operator!=(NodeFlowProjection other) const
+ {
+ return !(*this == other);
+ }
+
+ bool operator<(NodeFlowProjection other) const
+ {
+ if (kind() != other.kind())
+ return kind() < other.kind();
+ return node() < other.node();
+ }
+
+ bool operator>(NodeFlowProjection other) const
+ {
+ return other < *this;
+ }
+
+ bool operator<=(NodeFlowProjection other) const
+ {
+ return !(*this > other);
+ }
+
+ bool operator>=(NodeFlowProjection other) const
+ {
+ return !(*this < other);
+ }
+
+ bool isHashTableDeletedValue() const
+ {
+ return *this == NodeFlowProjection(WTF::HashTableDeletedValue);
+ }
+
+ // Phi shadow projections can become invalid because the Phi might be folded to something else.
+ bool isStillValid() const
+ {
+ return *this && (kind() == Primary || node()->op() == Phi);
+ }
+
+ void dump(PrintStream&) const;
+
+ template<typename Func>
+ static void forEach(Node* node, const Func& func)
+ {
+ func(NodeFlowProjection(node));
+ if (node->op() == Phi)
+ func(NodeFlowProjection(node, Shadow));
+ }
+
+public:
+ static const uintptr_t shadowBit = 1;
+
+ uintptr_t m_word { 0 };
+};
+
+struct NodeFlowProjectionHash {
+ static unsigned hash(NodeFlowProjection key) { return key.hash(); }
+ static bool equal(NodeFlowProjection a, NodeFlowProjection b) { return a == b; }
+ static const bool safeToCompareToEmptyOrDeleted = true;
+};
+
+} } // namespace JSC::DFG
+
+namespace WTF {
+
+template<typename T> struct DefaultHash;
+template<> struct DefaultHash<JSC::DFG::NodeFlowProjection> {
+ typedef JSC::DFG::NodeFlowProjectionHash Hash;
+};
+
+template<typename T> struct HashTraits;
+template<> struct HashTraits<JSC::DFG::NodeFlowProjection> : SimpleClassHashTraits<JSC::DFG::NodeFlowProjection> { };
+
+} // namespace WTF
+
+#endif // ENABLE(DFG_JIT)
+
Modified: trunk/Source/_javascript_Core/dfg/DFGStoreBarrierInsertionPhase.cpp (208372 => 208373)
--- trunk/Source/_javascript_Core/dfg/DFGStoreBarrierInsertionPhase.cpp 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/_javascript_Core/dfg/DFGStoreBarrierInsertionPhase.cpp 2016-11-04 05:28:35 UTC (rev 208373)
@@ -126,11 +126,13 @@
// Construct the state-at-tail based on the epochs of live nodes and the
// current epoch. We grow state-at-tail monotonically to ensure convergence.
bool thisBlockChanged = false;
- for (Node* node : block->ssa->liveAtTail) {
+ for (NodeFlowProjection node : block->ssa->liveAtTail) {
+ if (node.kind() == NodeFlowProjection::Shadow)
+ continue;
if (node->epoch() != m_currentEpoch) {
// If the node is older than the current epoch, then we may need to
// run a barrier on it in the future. So, add it to the state.
- thisBlockChanged |= m_stateAtTail->at(block).add(node).isNewEntry;
+ thisBlockChanged |= m_stateAtTail->at(block).add(node.node()).isNewEntry;
}
}
@@ -178,8 +180,10 @@
return false;
m_state->beginBasicBlock(block);
- for (Node* node : block->ssa->liveAtHead) {
- if (m_stateAtHead->at(block).contains(node)) {
+ for (NodeFlowProjection node : block->ssa->liveAtHead) {
+ if (node.kind() == NodeFlowProjection::Shadow)
+ continue;
+ if (m_stateAtHead->at(block).contains(node.node())) {
// If previous blocks tell us that this node may need a barrier in the
// future, then put it in the ancient primordial epoch. This forces us to
// emit a barrier on any possibly-cell store, regardless of the epoch of the
@@ -326,7 +330,8 @@
break;
case Upsilon:
- m_node->phi()->setEpoch(m_node->epoch());
+ // Assume the worst for Phis so that we don't have to worry about Phi shadows.
+ m_node->phi()->setEpoch(Epoch());
m_node->setEpoch(Epoch());
break;
Modified: trunk/Source/WTF/ChangeLog (208372 => 208373)
--- trunk/Source/WTF/ChangeLog 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/WTF/ChangeLog 2016-11-04 05:28:35 UTC (rev 208373)
@@ -1,3 +1,16 @@
+2016-11-03 Filip Pizlo <fpi...@apple.com>
+
+ 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.
+
+ Made this API use size rather than maxIndex as its initialization parameter, because that's
+ less confusing.
+
+ * wtf/IndexSparseSet.h:
+ (WTF::IndexSparseSet<OverflowHandler>::IndexSparseSet):
+
2016-11-03 Commit Queue <commit-qu...@webkit.org>
Unreviewed, rolling out r208364.
Modified: trunk/Source/WTF/wtf/IndexSparseSet.h (208372 => 208373)
--- trunk/Source/WTF/wtf/IndexSparseSet.h 2016-11-04 05:15:11 UTC (rev 208372)
+++ trunk/Source/WTF/wtf/IndexSparseSet.h 2016-11-04 05:28:35 UTC (rev 208373)
@@ -45,7 +45,7 @@
class IndexSparseSet {
typedef Vector<unsigned, 0, OverflowHandler> ValueList;
public:
- explicit IndexSparseSet(unsigned maxValue);
+ explicit IndexSparseSet(unsigned size);
bool add(unsigned);
bool remove(unsigned);
@@ -65,9 +65,9 @@
};
template<typename OverflowHandler>
-inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned maxValue)
+inline IndexSparseSet<OverflowHandler>::IndexSparseSet(unsigned size)
{
- m_map.resize(maxValue + 1);
+ m_map.resize(size);
}
template<typename OverflowHandler>
