fourthTier: DFG should do a high-level LICM before going to FTL
https://bugs.webkit.org/show_bug.cgi?id=118749
Reviewed by Oliver Hunt.
Implements LICM hoisting for nodes that never write anything and never read
things that are clobbered by the loop. There are some other preconditions for
hoisting, see DFGLICMPhase.cpp.
Also did a few fixes:
- ClobberSet::add was failing to switch Super entries to Direct entries in
some cases.
- DFGClobberize.cpp needed to #include "Operations.h".
- DCEPhase needs to process the graph in reverse DFS order, when we're in SSA.
- AbstractInterpreter can now execute a Node without knowing its indexInBlock.
Knowing the indexInBlock is an optional optimization that all other clients
of AI still opt into, but LICM doesn't.
This makes the FTL a 2.19x speed-up on imaging-gaussian-blur.
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAbstractInterpreter.h:
(AbstractInterpreter):
* dfg/DFGAbstractInterpreterInlines.h:
(JSC::DFG::::executeEffects):
(JSC::DFG::::execute):
(DFG):
(JSC::DFG::::clobberWorld):
(JSC::DFG::::clobberStructures):
* dfg/DFGAtTailAbstractState.cpp: Added.
(DFG):
(JSC::DFG::AtTailAbstractState::AtTailAbstractState):
(JSC::DFG::AtTailAbstractState::~AtTailAbstractState):
(JSC::DFG::AtTailAbstractState::createValueForNode):
(JSC::DFG::AtTailAbstractState::forNode):
* dfg/DFGAtTailAbstractState.h: Added.
(DFG):
(AtTailAbstractState):
(JSC::DFG::AtTailAbstractState::initializeTo):
(JSC::DFG::AtTailAbstractState::forNode):
(JSC::DFG::AtTailAbstractState::variables):
(JSC::DFG::AtTailAbstractState::block):
(JSC::DFG::AtTailAbstractState::isValid):
(JSC::DFG::AtTailAbstractState::setDidClobber):
(JSC::DFG::AtTailAbstractState::setIsValid):
(JSC::DFG::AtTailAbstractState::setBranchDirection):
(JSC::DFG::AtTailAbstractState::setFoundConstants):
(JSC::DFG::AtTailAbstractState::haveStructures):
(JSC::DFG::AtTailAbstractState::setHaveStructures):
* dfg/DFGBasicBlock.h:
(JSC::DFG::BasicBlock::insertBeforeLast):
* dfg/DFGBasicBlockInlines.h:
(DFG):
* dfg/DFGClobberSet.cpp:
(JSC::DFG::ClobberSet::add):
(JSC::DFG::ClobberSet::addAll):
* dfg/DFGClobberize.cpp:
(JSC::DFG::doesWrites):
* dfg/DFGClobberize.h:
(DFG):
* dfg/DFGDCEPhase.cpp:
(JSC::DFG::DCEPhase::DCEPhase):
(JSC::DFG::DCEPhase::run):
(JSC::DFG::DCEPhase::fixupBlock):
(DCEPhase):
* dfg/DFGEdgeDominates.h: Added.
(DFG):
(EdgeDominates):
(JSC::DFG::EdgeDominates::EdgeDominates):
(JSC::DFG::EdgeDominates::operator()):
(JSC::DFG::EdgeDominates::result):
(JSC::DFG::edgesDominate):
* dfg/DFGFixupPhase.cpp:
(JSC::DFG::FixupPhase::fixupNode):
(JSC::DFG::FixupPhase::checkArray):
* dfg/DFGLICMPhase.cpp: Added.
(LICMPhase):
(JSC::DFG::LICMPhase::LICMPhase):
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
(DFG):
(JSC::DFG::performLICM):
* dfg/DFGLICMPhase.h: Added.
(DFG):
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@153295 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/JavaScriptCore/ChangeLog b/Source/JavaScriptCore/ChangeLog
index 983082d..139e7db 100644
--- a/Source/JavaScriptCore/ChangeLog
+++ b/Source/JavaScriptCore/ChangeLog
@@ -1,3 +1,96 @@
+2013-07-22 Filip Pizlo <fpizlo@apple.com>
+
+ fourthTier: DFG should do a high-level LICM before going to FTL
+ https://bugs.webkit.org/show_bug.cgi?id=118749
+
+ Reviewed by Oliver Hunt.
+
+ Implements LICM hoisting for nodes that never write anything and never read
+ things that are clobbered by the loop. There are some other preconditions for
+ hoisting, see DFGLICMPhase.cpp.
+
+ Also did a few fixes:
+
+ - ClobberSet::add was failing to switch Super entries to Direct entries in
+ some cases.
+
+ - DFGClobberize.cpp needed to #include "Operations.h".
+
+ - DCEPhase needs to process the graph in reverse DFS order, when we're in SSA.
+
+ - AbstractInterpreter can now execute a Node without knowing its indexInBlock.
+ Knowing the indexInBlock is an optional optimization that all other clients
+ of AI still opt into, but LICM doesn't.
+
+ This makes the FTL a 2.19x speed-up on imaging-gaussian-blur.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * dfg/DFGAbstractInterpreter.h:
+ (AbstractInterpreter):
+ * dfg/DFGAbstractInterpreterInlines.h:
+ (JSC::DFG::::executeEffects):
+ (JSC::DFG::::execute):
+ (DFG):
+ (JSC::DFG::::clobberWorld):
+ (JSC::DFG::::clobberStructures):
+ * dfg/DFGAtTailAbstractState.cpp: Added.
+ (DFG):
+ (JSC::DFG::AtTailAbstractState::AtTailAbstractState):
+ (JSC::DFG::AtTailAbstractState::~AtTailAbstractState):
+ (JSC::DFG::AtTailAbstractState::createValueForNode):
+ (JSC::DFG::AtTailAbstractState::forNode):
+ * dfg/DFGAtTailAbstractState.h: Added.
+ (DFG):
+ (AtTailAbstractState):
+ (JSC::DFG::AtTailAbstractState::initializeTo):
+ (JSC::DFG::AtTailAbstractState::forNode):
+ (JSC::DFG::AtTailAbstractState::variables):
+ (JSC::DFG::AtTailAbstractState::block):
+ (JSC::DFG::AtTailAbstractState::isValid):
+ (JSC::DFG::AtTailAbstractState::setDidClobber):
+ (JSC::DFG::AtTailAbstractState::setIsValid):
+ (JSC::DFG::AtTailAbstractState::setBranchDirection):
+ (JSC::DFG::AtTailAbstractState::setFoundConstants):
+ (JSC::DFG::AtTailAbstractState::haveStructures):
+ (JSC::DFG::AtTailAbstractState::setHaveStructures):
+ * dfg/DFGBasicBlock.h:
+ (JSC::DFG::BasicBlock::insertBeforeLast):
+ * dfg/DFGBasicBlockInlines.h:
+ (DFG):
+ * dfg/DFGClobberSet.cpp:
+ (JSC::DFG::ClobberSet::add):
+ (JSC::DFG::ClobberSet::addAll):
+ * dfg/DFGClobberize.cpp:
+ (JSC::DFG::doesWrites):
+ * dfg/DFGClobberize.h:
+ (DFG):
+ * dfg/DFGDCEPhase.cpp:
+ (JSC::DFG::DCEPhase::DCEPhase):
+ (JSC::DFG::DCEPhase::run):
+ (JSC::DFG::DCEPhase::fixupBlock):
+ (DCEPhase):
+ * dfg/DFGEdgeDominates.h: Added.
+ (DFG):
+ (EdgeDominates):
+ (JSC::DFG::EdgeDominates::EdgeDominates):
+ (JSC::DFG::EdgeDominates::operator()):
+ (JSC::DFG::EdgeDominates::result):
+ (JSC::DFG::edgesDominate):
+ * dfg/DFGFixupPhase.cpp:
+ (JSC::DFG::FixupPhase::fixupNode):
+ (JSC::DFG::FixupPhase::checkArray):
+ * dfg/DFGLICMPhase.cpp: Added.
+ (LICMPhase):
+ (JSC::DFG::LICMPhase::LICMPhase):
+ (JSC::DFG::LICMPhase::run):
+ (JSC::DFG::LICMPhase::attemptHoist):
+ (DFG):
+ (JSC::DFG::performLICM):
+ * dfg/DFGLICMPhase.h: Added.
+ (DFG):
+ * dfg/DFGPlan.cpp:
+ (JSC::DFG::Plan::compileInThreadImpl):
+
2013-07-21 Filip Pizlo <fpizlo@apple.com>
fourthTier: DFG Nodes should be able to abstractly tell you what they read and what they write
diff --git a/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj b/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
index 4d499b9..24624f9 100644
--- a/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
+++ b/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
@@ -837,6 +837,11 @@
A7D89CFF17A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */; };
A7D89D0017A0B8CC00773AD8 /* DFGSSAConversionPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
A7D89D0217A0B90400773AD8 /* FTLLoweredNodeValue.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D89D0117A0B90400773AD8 /* FTLLoweredNodeValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ A7D9A29417A0BC7400EE2618 /* DFGAtTailAbstractState.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D9A28F17A0BC7400EE2618 /* DFGAtTailAbstractState.cpp */; };
+ A7D9A29517A0BC7400EE2618 /* DFGAtTailAbstractState.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D9A29017A0BC7400EE2618 /* DFGAtTailAbstractState.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ A7D9A29617A0BC7400EE2618 /* DFGEdgeDominates.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D9A29117A0BC7400EE2618 /* DFGEdgeDominates.h */; settings = {ATTRIBUTES = (Private, ); }; };
+ A7D9A29717A0BC7400EE2618 /* DFGLICMPhase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7D9A29217A0BC7400EE2618 /* DFGLICMPhase.cpp */; };
+ A7D9A29817A0BC7400EE2618 /* DFGLICMPhase.h in Headers */ = {isa = PBXBuildFile; fileRef = A7D9A29317A0BC7400EE2618 /* DFGLICMPhase.h */; settings = {ATTRIBUTES = (Private, ); }; };
A7DCB97312E5193F00911940 /* WriteBarrier.h in Headers */ = {isa = PBXBuildFile; fileRef = A7DCB77912E3D90500911940 /* WriteBarrier.h */; settings = {ATTRIBUTES = (Private, ); }; };
A7E2EA6B0FB460CF00601F06 /* LiteralParser.h in Headers */ = {isa = PBXBuildFile; fileRef = A7E2EA690FB460CF00601F06 /* LiteralParser.h */; };
A7E2EA6C0FB460CF00601F06 /* LiteralParser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7E2EA6A0FB460CF00601F06 /* LiteralParser.cpp */; };
@@ -1916,6 +1921,11 @@
A7D89CF017A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGSSAConversionPhase.cpp; path = dfg/DFGSSAConversionPhase.cpp; sourceTree = "<group>"; };
A7D89CF117A0B8CC00773AD8 /* DFGSSAConversionPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGSSAConversionPhase.h; path = dfg/DFGSSAConversionPhase.h; sourceTree = "<group>"; };
A7D89D0117A0B90400773AD8 /* FTLLoweredNodeValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLLoweredNodeValue.h; path = ftl/FTLLoweredNodeValue.h; sourceTree = "<group>"; };
+ A7D9A28F17A0BC7400EE2618 /* DFGAtTailAbstractState.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGAtTailAbstractState.cpp; path = dfg/DFGAtTailAbstractState.cpp; sourceTree = "<group>"; };
+ A7D9A29017A0BC7400EE2618 /* DFGAtTailAbstractState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAtTailAbstractState.h; path = dfg/DFGAtTailAbstractState.h; sourceTree = "<group>"; };
+ A7D9A29117A0BC7400EE2618 /* DFGEdgeDominates.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGEdgeDominates.h; path = dfg/DFGEdgeDominates.h; sourceTree = "<group>"; };
+ A7D9A29217A0BC7400EE2618 /* DFGLICMPhase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGLICMPhase.cpp; path = dfg/DFGLICMPhase.cpp; sourceTree = "<group>"; };
+ A7D9A29317A0BC7400EE2618 /* DFGLICMPhase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGLICMPhase.h; path = dfg/DFGLICMPhase.h; sourceTree = "<group>"; };
A7DCB77912E3D90500911940 /* WriteBarrier.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WriteBarrier.h; sourceTree = "<group>"; };
A7E2EA690FB460CF00601F06 /* LiteralParser.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LiteralParser.h; sourceTree = "<group>"; };
A7E2EA6A0FB460CF00601F06 /* LiteralParser.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LiteralParser.cpp; sourceTree = "<group>"; };
@@ -2187,9 +2197,9 @@
034768DFFF38A50411DB9C8B /* Products */ = {
isa = PBXGroup;
children = (
- 932F5BE10822A1C700736975 /* jsc */,
0FF922CF14F46B130041A24E /* JSCLLIntOffsetsExtractor */,
932F5BD90822A1C700736975 /* JavaScriptCore.framework */,
+ 932F5BE10822A1C700736975 /* jsc */,
141211200A48793C00480255 /* minidom */,
14BD59BF0A3E8F9000BAF59C /* testapi */,
6511230514046A4C002B101D /* testRegExp */,
@@ -3079,6 +3089,8 @@
0F63948215E48114006A597C /* DFGArrayMode.h */,
0FC0976B1468AB4A00CF2442 /* DFGAssemblyHelpers.cpp */,
0FC0976C1468AB4A00CF2442 /* DFGAssemblyHelpers.h */,
+ A7D9A28F17A0BC7400EE2618 /* DFGAtTailAbstractState.cpp */,
+ A7D9A29017A0BC7400EE2618 /* DFGAtTailAbstractState.h */,
0F714CA116EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.cpp */,
0F714CA216EA92ED00F3EBEB /* DFGBackwardsPropagationPhase.h */,
A7D89CE317A0B8CC00773AD8 /* DFGBasicBlock.cpp */,
@@ -3132,6 +3144,7 @@
0FD3C82214115D0E00FD81CB /* DFGDriver.h */,
0FB4B51B16B62772003F696B /* DFGEdge.cpp */,
0F66E16914DF3F1300B7B2E4 /* DFGEdge.h */,
+ A7D9A29117A0BC7400EE2618 /* DFGEdgeDominates.h */,
A7986D5617A0BB1E00A95DD0 /* DFGEdgeUsesStructure.h */,
A78A976C179738B8009DF744 /* DFGFailedFinalizer.cpp */,
A78A976D179738B8009DF744 /* DFGFailedFinalizer.h */,
@@ -3160,6 +3173,8 @@
A78A9771179738B8009DF744 /* DFGJITFinalizer.h */,
A73A53581799CD5D00170C19 /* DFGLazyJSValue.cpp */,
A73A53591799CD5D00170C19 /* DFGLazyJSValue.h */,
+ A7D9A29217A0BC7400EE2618 /* DFGLICMPhase.cpp */,
+ A7D9A29317A0BC7400EE2618 /* DFGLICMPhase.h */,
A7D89CEC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp */,
A7D89CED17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h */,
0FB4B51C16B62772003F696B /* DFGLongLivedState.cpp */,
@@ -3528,6 +3543,7 @@
0F05C3B41683CF9200BAF45B /* DFGArrayifySlowPathGenerator.h in Headers */,
0F63948515E4811B006A597C /* DFGArrayMode.h in Headers */,
0FC0976D1468AB4E00CF2442 /* DFGAssemblyHelpers.h in Headers */,
+ A7D9A29517A0BC7400EE2618 /* DFGAtTailAbstractState.h in Headers */,
0F714CA516EA92F200F3EBEB /* DFGBackwardsPropagationPhase.h in Headers */,
0F620176143FCD3B0068B77C /* DFGBasicBlock.h in Headers */,
0FFB921A16D02EC50055A5DB /* DFGBasicBlockInlines.h in Headers */,
@@ -3558,6 +3574,7 @@
0F1E3A471534CBB9000F9456 /* DFGDoubleFormatState.h in Headers */,
0FD3C82814115D4F00FD81CB /* DFGDriver.h in Headers */,
0F66E16C14DF3F1600B7B2E4 /* DFGEdge.h in Headers */,
+ A7D9A29617A0BC7400EE2618 /* DFGEdgeDominates.h in Headers */,
A7986D5717A0BB1E00A95DD0 /* DFGEdgeUsesStructure.h in Headers */,
0FBC0AE81496C7C700D4FBDD /* DFGExitProfile.h in Headers */,
A78A9775179738B8009DF744 /* DFGFailedFinalizer.h in Headers */,
@@ -3576,6 +3593,7 @@
86EC9DCC1328DF82002B2AD7 /* DFGJITCompiler.h in Headers */,
A78A9779179738B8009DF744 /* DFGJITFinalizer.h in Headers */,
A73A535B1799CD5D00170C19 /* DFGLazyJSValue.h in Headers */,
+ A7D9A29817A0BC7400EE2618 /* DFGLICMPhase.h in Headers */,
A7D89CFC17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.h in Headers */,
0FF0F19B16B729FA005DF95B /* DFGLongLivedState.h in Headers */,
A767B5B617A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.h in Headers */,
@@ -4394,6 +4412,7 @@
0F16015D156198C900C2587C /* DFGArgumentsSimplificationPhase.cpp in Sources */,
0F63948415E48118006A597C /* DFGArrayMode.cpp in Sources */,
0FC0976E1468AB5100CF2442 /* DFGAssemblyHelpers.cpp in Sources */,
+ A7D9A29417A0BC7400EE2618 /* DFGAtTailAbstractState.cpp in Sources */,
0F714CA416EA92F000F3EBEB /* DFGBackwardsPropagationPhase.cpp in Sources */,
A7D89CF217A0B8CC00773AD8 /* DFGBasicBlock.cpp in Sources */,
A70B083217A0B79B00DAF14B /* DFGBinarySwitch.cpp in Sources */,
@@ -4431,6 +4450,7 @@
86EC9DCB1328DF82002B2AD7 /* DFGJITCompiler.cpp in Sources */,
A78A9778179738B8009DF744 /* DFGJITFinalizer.cpp in Sources */,
A73A535A1799CD5D00170C19 /* DFGLazyJSValue.cpp in Sources */,
+ A7D9A29717A0BC7400EE2618 /* DFGLICMPhase.cpp in Sources */,
A7D89CFB17A0B8CC00773AD8 /* DFGLivenessAnalysisPhase.cpp in Sources */,
0FF0F19916B729F6005DF95B /* DFGLongLivedState.cpp in Sources */,
A767B5B517A0B9650063D940 /* DFGLoopPreHeaderCreationPhase.cpp in Sources */,
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
index 5ba67b3..2521748 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreter.h
@@ -89,6 +89,7 @@
// } else
// result = true;
bool execute(unsigned indexInBlock);
+ bool execute(Node*);
// Indicate the start of execution of the node. It resets any state in the node,
// that is progressively built up by executeEdges() and executeEffects(). In
@@ -114,7 +115,7 @@
// Abstractly execute the effects of the given node. This changes the abstract
// state assuming that edges have already been filtered.
bool executeEffects(unsigned indexInBlock);
- bool executeEffects(unsigned indexInBlock, Node*);
+ bool executeEffects(unsigned clobberLimit, Node*);
void dump(PrintStream& out);
diff --git a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
index f90eade..405c183 100644
--- a/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
+++ b/Source/JavaScriptCore/dfg/DFGAbstractInterpreterInlines.h
@@ -119,7 +119,7 @@
}
template<typename AbstractStateType>
-bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned indexInBlock, Node* node)
+bool AbstractInterpreter<AbstractStateType>::executeEffects(unsigned clobberLimit, Node* node)
{
if (!ASSERT_DISABLED)
verifyEdges(node);
@@ -332,7 +332,7 @@
break;
default:
RELEASE_ASSERT(node->op() == ValueAdd);
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).setType(SpecString | SpecInt32 | SpecNumber);
break;
}
@@ -771,7 +771,7 @@
m_state.setIsValid(false);
break;
case Array::Generic:
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
break;
case Array::String:
@@ -786,7 +786,7 @@
// implies an in-bounds access). None of this feels like it's worth it,
// so we're going with TOP for now. The same thing applies to
// clobbering the world.
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
} else
forNode(node).set(m_graph, m_graph.m_vm.stringStructure.get());
@@ -796,14 +796,14 @@
break;
case Array::Int32:
if (node->arrayMode().isOutOfBounds()) {
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
} else
forNode(node).setType(SpecInt32);
break;
case Array::Double:
if (node->arrayMode().isOutOfBounds()) {
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
} else if (node->arrayMode().isSaneChain())
forNode(node).setType(SpecDouble);
@@ -814,7 +814,7 @@
case Array::ArrayStorage:
case Array::SlowPutArrayStorage:
if (node->arrayMode().isOutOfBounds())
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
break;
case Array::Int8Array:
@@ -862,24 +862,24 @@
m_state.setIsValid(false);
break;
case Array::Generic:
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
case Array::Int32:
if (node->arrayMode().isOutOfBounds())
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
case Array::Double:
if (node->arrayMode().isOutOfBounds())
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
case Array::Contiguous:
case Array::ArrayStorage:
if (node->arrayMode().isOutOfBounds())
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
case Array::SlowPutArrayStorage:
if (node->arrayMode().mayStoreToHole())
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
default:
break;
@@ -889,13 +889,13 @@
case ArrayPush:
node->setCanExit(true);
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).setType(SpecNumber);
break;
case ArrayPop:
node->setCanExit(true);
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
break;
@@ -979,7 +979,7 @@
// ToPrimitive will currently forget string constants. But that's not a big
// deal since we don't do any optimization on those currently.
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
SpeculatedType type = source.m_type;
if (type & ~(SpecNumber | SpecString | SpecBoolean)) {
@@ -1007,7 +1007,7 @@
break;
case CellUse:
case UntypedUse:
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
default:
RELEASE_ASSERT_NOT_REACHED();
@@ -1118,7 +1118,7 @@
case GetMyArgumentsLengthSafe:
// This potentially clobbers all structures if the arguments object had a getter
// installed on the length property.
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
// We currently make no guarantee about what this returns because it does not
// speculate that the length property is actually a length.
forNode(node).makeTop();
@@ -1136,7 +1136,7 @@
node->setCanExit(true);
// This potentially clobbers all structures if the property we're accessing has
// a getter. We don't speculate against this.
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
// And the result is unknown.
forNode(node).makeTop();
break;
@@ -1225,7 +1225,7 @@
}
}
}
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
break;
@@ -1294,7 +1294,7 @@
case PutStructure:
case PhantomPutStructure:
if (!forNode(node->child1()).m_currentKnownStructure.isClear()) {
- clobberStructures(indexInBlock);
+ clobberStructures(clobberLimit);
forNode(node->child1()).set(m_graph, node->structureTransitionData().newStructure);
m_state.setHaveStructures(true);
}
@@ -1366,7 +1366,7 @@
ASSERT(node->arrayMode().conversion() == Array::Convert
|| node->arrayMode().conversion() == Array::RageConvert);
node->setCanExit(true);
- clobberStructures(indexInBlock);
+ clobberStructures(clobberLimit);
filterArrayModes(node->child1(), node->arrayMode().arrayModesThatPassFiltering());
m_state.setHaveStructures(true);
break;
@@ -1378,7 +1378,7 @@
|| value.m_currentKnownStructure.isSubsetOf(set))
m_state.setFoundConstants(true);
node->setCanExit(true);
- clobberStructures(indexInBlock);
+ clobberStructures(clobberLimit);
filter(value, set);
m_state.setHaveStructures(true);
break;
@@ -1425,20 +1425,20 @@
break;
}
if (status.isSimpleTransition()) {
- clobberStructures(indexInBlock);
+ clobberStructures(clobberLimit);
forNode(node->child1()).set(m_graph, status.newStructure());
m_state.setHaveStructures(true);
m_state.setFoundConstants(true);
break;
}
}
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
break;
case In:
// FIXME: We can determine when the property definitely exists based on abstract
// value information.
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).setType(SpecBoolean);
break;
@@ -1486,7 +1486,7 @@
case Call:
case Construct:
node->setCanExit(true);
- clobberWorld(node->codeOrigin, indexInBlock);
+ clobberWorld(node->codeOrigin, clobberLimit);
forNode(node).makeTop();
break;
@@ -1530,11 +1530,21 @@
}
template<typename AbstractStateType>
+bool AbstractInterpreter<AbstractStateType>::execute(Node* node)
+{
+ if (!startExecuting(node))
+ return true;
+
+ executeEdges(node);
+ return executeEffects(UINT_MAX, node);
+}
+
+template<typename AbstractStateType>
void AbstractInterpreter<AbstractStateType>::clobberWorld(
- const CodeOrigin& codeOrigin, unsigned indexInBlock)
+ const CodeOrigin& codeOrigin, unsigned clobberLimit)
{
clobberCapturedVars(codeOrigin);
- clobberStructures(indexInBlock);
+ clobberStructures(clobberLimit);
}
template<typename AbstractStateType>
@@ -1561,11 +1571,16 @@
}
template<typename AbstractStateType>
-void AbstractInterpreter<AbstractStateType>::clobberStructures(unsigned indexInBlock)
+void AbstractInterpreter<AbstractStateType>::clobberStructures(unsigned clobberLimit)
{
if (!m_state.haveStructures())
return;
- for (size_t i = indexInBlock + 1; i--;)
+ if (clobberLimit >= m_state.block()->size())
+ clobberLimit = m_state.block()->size();
+ else
+ clobberLimit++;
+ ASSERT(clobberLimit <= m_state.block()->size());
+ for (size_t i = clobberLimit; i--;)
forNode(m_state.block()->at(i)).clobberStructures();
if (m_graph.m_form == SSA) {
HashSet<Node*>::iterator iter = m_state.block()->ssa->liveAtHead.begin();
diff --git a/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.cpp b/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.cpp
new file mode 100644
index 0000000..ca77068
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.cpp
@@ -0,0 +1,57 @@
+/*
+ * Copyright (C) 2013 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 "DFGAtTailAbstractState.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+AtTailAbstractState::AtTailAbstractState()
+ : m_block(0)
+{
+}
+
+AtTailAbstractState::~AtTailAbstractState() { }
+
+void AtTailAbstractState::createValueForNode(Node* node)
+{
+ m_block->ssa->valuesAtTail.add(node, AbstractValue());
+}
+
+AbstractValue& AtTailAbstractState::forNode(Node* node)
+{
+ HashMap<Node*, AbstractValue>::iterator iter = m_block->ssa->valuesAtTail.find(node);
+ ASSERT(iter != m_block->ssa->valuesAtTail.end());
+ return iter->value;
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h b/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h
new file mode 100644
index 0000000..a994bf8
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef DFGAtTailAbstractState_h
+#define DFGAtTailAbstractState_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAbstractValue.h"
+#include "DFGBasicBlock.h"
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+class AtTailAbstractState {
+public:
+ AtTailAbstractState();
+
+ ~AtTailAbstractState();
+
+ void initializeTo(BasicBlock* block)
+ {
+ m_block = block;
+ }
+
+ void createValueForNode(Node*);
+ AbstractValue& forNode(Node*);
+ AbstractValue& forNode(Edge edge) { return forNode(edge.node()); }
+ Operands<AbstractValue>& variables() { return m_block->valuesAtTail; }
+
+ BasicBlock* block() const { return m_block; }
+
+ bool isValid() { return m_block->cfaDidFinish; }
+
+ void setDidClobber(bool) { }
+ void setIsValid(bool isValid) { m_block->cfaDidFinish = isValid; }
+ void setBranchDirection(BranchDirection) { }
+ void setFoundConstants(bool) { }
+ bool haveStructures() const { return true; } // It's always safe to return true.
+ void setHaveStructures(bool) { }
+
+private:
+ BasicBlock* m_block;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGAtTailAbstractState_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGBasicBlock.h b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
index ade75d9..bb5f485 100644
--- a/Source/JavaScriptCore/dfg/DFGBasicBlock.h
+++ b/Source/JavaScriptCore/dfg/DFGBasicBlock.h
@@ -62,6 +62,11 @@
void grow(size_t size) { m_nodes.grow(size); }
void append(Node* node) { m_nodes.append(node); }
+ void insertBeforeLast(Node* node)
+ {
+ append(last());
+ at(size() - 2) = node;
+ }
size_t numNodes() const { return phis.size() + size(); }
Node* node(size_t i) const
diff --git a/Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h b/Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h
index 3671a2a..7f9e38a 100644
--- a/Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h
+++ b/Source/JavaScriptCore/dfg/DFGBasicBlockInlines.h
@@ -47,8 +47,7 @@
templatePre typeParams templatePost inline Node* BasicBlock::appendNonTerminal(Graph& graph, SpeculatedType type valueParamsComma valueParams) \
{ \
Node* result = graph.addNode(type valueParamsComma valueArgs); \
- append(last()); \
- at(size() - 2) = result; \
+ insertBeforeLast(result); \
return result; \
}
DFG_VARIADIC_TEMPLATE_FUNCTION(DFG_DEFINE_APPEND_NODE)
diff --git a/Source/JavaScriptCore/dfg/DFGClobberSet.cpp b/Source/JavaScriptCore/dfg/DFGClobberSet.cpp
index 01456e8..7913141 100644
--- a/Source/JavaScriptCore/dfg/DFGClobberSet.cpp
+++ b/Source/JavaScriptCore/dfg/DFGClobberSet.cpp
@@ -40,7 +40,7 @@
void ClobberSet::add(AbstractHeap heap)
{
HashMap<AbstractHeap, bool>::AddResult result = m_clobbers.add(heap, true);
- if (result.isNewEntry) {
+ if (!result.isNewEntry) {
if (result.iterator->value)
return;
result.iterator->value = true;
@@ -60,6 +60,9 @@
// If the other heap has a super heap, we make sure it's present but don't
// modify its value - so we had it directly already then this doesn't change.
+ if (this == &other)
+ return;
+
HashMap<AbstractHeap, bool>::const_iterator iter = other.m_clobbers.begin();
HashMap<AbstractHeap, bool>::const_iterator end = other.m_clobbers.end();
for (; iter != end; ++iter)
diff --git a/Source/JavaScriptCore/dfg/DFGClobberize.cpp b/Source/JavaScriptCore/dfg/DFGClobberize.cpp
index a7b623b..275dcf7 100644
--- a/Source/JavaScriptCore/dfg/DFGClobberize.cpp
+++ b/Source/JavaScriptCore/dfg/DFGClobberize.cpp
@@ -28,9 +28,11 @@
#if ENABLE(DFG_JIT)
+#include "Operations.h"
+
namespace JSC { namespace DFG {
-bool didWrites(Graph& graph, Node* node)
+bool doesWrites(Graph& graph, Node* node)
{
NoOpClobberize addRead;
CheckClobberize addWrite;
diff --git a/Source/JavaScriptCore/dfg/DFGClobberize.h b/Source/JavaScriptCore/dfg/DFGClobberize.h
index 9d18bd1..82fe5eb 100644
--- a/Source/JavaScriptCore/dfg/DFGClobberize.h
+++ b/Source/JavaScriptCore/dfg/DFGClobberize.h
@@ -624,7 +624,7 @@
bool m_result;
};
-bool didWrites(Graph&, Node*);
+bool doesWrites(Graph&, Node*);
} } // namespace JSC::DFG
diff --git a/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp b/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
index 162f631..d45e49d 100644
--- a/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGDCEPhase.cpp
@@ -40,6 +40,7 @@
public:
DCEPhase(Graph& graph)
: Phase(graph, "dead code elimination")
+ , m_insertionSet(graph)
{
}
@@ -104,75 +105,16 @@
}
}
- for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
- BasicBlock* block = m_graph.block(blockIndex);
- if (!block)
- continue;
-
- InsertionSet insertionSet(m_graph);
-
- for (unsigned indexInBlock = block->size(); indexInBlock--;) {
- Node* node = block->at(indexInBlock);
- if (node->shouldGenerate())
- continue;
-
- switch (node->op()) {
- case SetLocal:
- case MovHint: {
- ASSERT((node->op() == SetLocal) == (m_graph.m_form == ThreadedCPS));
- if (node->child1().willNotHaveCheck()) {
- // Consider the possibility that UInt32ToNumber is dead but its
- // child isn't; if so then we should MovHint the child.
- if (!node->child1()->shouldGenerate()
- && node->child1()->op() == UInt32ToNumber)
- node->child1() = node->child1()->child1();
-
- if (!node->child1()->shouldGenerate()) {
- node->setOpAndDefaultFlags(ZombieHint);
- node->child1() = Edge();
- break;
- }
- node->setOpAndDefaultFlags(MovHint);
- break;
- }
- node->setOpAndDefaultFlags(MovHintAndCheck);
- node->setRefCount(1);
- break;
- }
-
- case GetLocal:
- case SetArgument: {
- if (m_graph.m_form == ThreadedCPS) {
- // Leave them as not shouldGenerate.
- break;
- }
- }
-
- default: {
- if (node->flags() & NodeHasVarArgs) {
- for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
- Edge edge = m_graph.m_varArgChildren[childIdx];
-
- if (!edge || edge.willNotHaveCheck())
- continue;
-
- insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge);
- }
-
- node->convertToPhantomUnchecked();
- node->children.reset();
- node->setRefCount(1);
- break;
- }
-
- node->convertToPhantom();
- eliminateIrrelevantPhantomChildren(node);
- node->setRefCount(1);
- break;
- } }
- }
-
- insertionSet.execute(block);
+ if (m_graph.m_form == SSA) {
+ // Need to process the graph in reverse DFS order, so that we get to the uses
+ // of a node before we get to the node itself.
+ Vector<BasicBlock*> depthFirst;
+ m_graph.getBlocksInDepthFirstOrder(depthFirst);
+ for (unsigned i = depthFirst.size(); i--;)
+ fixupBlock(depthFirst[i]);
+ } else {
+ for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
+ fixupBlock(m_graph.block(blockIndex));
}
m_graph.m_refCountState = ExactRefCount;
@@ -206,6 +148,75 @@
countNode(edge.node());
}
+ void fixupBlock(BasicBlock* block)
+ {
+ if (!block)
+ return;
+
+ for (unsigned indexInBlock = block->size(); indexInBlock--;) {
+ Node* node = block->at(indexInBlock);
+ if (node->shouldGenerate())
+ continue;
+
+ switch (node->op()) {
+ case SetLocal:
+ case MovHint: {
+ ASSERT((node->op() == SetLocal) == (m_graph.m_form == ThreadedCPS));
+ if (node->child1().willNotHaveCheck()) {
+ // Consider the possibility that UInt32ToNumber is dead but its
+ // child isn't; if so then we should MovHint the child.
+ if (!node->child1()->shouldGenerate()
+ && node->child1()->op() == UInt32ToNumber)
+ node->child1() = node->child1()->child1();
+
+ if (!node->child1()->shouldGenerate()) {
+ node->setOpAndDefaultFlags(ZombieHint);
+ node->child1() = Edge();
+ break;
+ }
+ node->setOpAndDefaultFlags(MovHint);
+ break;
+ }
+ node->setOpAndDefaultFlags(MovHintAndCheck);
+ node->setRefCount(1);
+ break;
+ }
+
+ case GetLocal:
+ case SetArgument: {
+ if (m_graph.m_form == ThreadedCPS) {
+ // Leave them as not shouldGenerate.
+ break;
+ }
+ }
+
+ default: {
+ if (node->flags() & NodeHasVarArgs) {
+ for (unsigned childIdx = node->firstChild(); childIdx < node->firstChild() + node->numChildren(); childIdx++) {
+ Edge edge = m_graph.m_varArgChildren[childIdx];
+
+ if (!edge || edge.willNotHaveCheck())
+ continue;
+
+ m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->codeOrigin, edge);
+ }
+
+ node->convertToPhantomUnchecked();
+ node->children.reset();
+ node->setRefCount(1);
+ break;
+ }
+
+ node->convertToPhantom();
+ eliminateIrrelevantPhantomChildren(node);
+ node->setRefCount(1);
+ break;
+ } }
+ }
+
+ m_insertionSet.execute(block);
+ }
+
void eliminateIrrelevantPhantomChildren(Node* node)
{
for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
@@ -218,6 +229,7 @@
}
Vector<Node*, 128> m_worklist;
+ InsertionSet m_insertionSet;
};
bool performDCE(Graph& graph)
diff --git a/Source/JavaScriptCore/dfg/DFGEdgeDominates.h b/Source/JavaScriptCore/dfg/DFGEdgeDominates.h
new file mode 100644
index 0000000..0d514db
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGEdgeDominates.h
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef DFGEdgeDominates_h
+#define DFGEdgeDominates_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+class EdgeDominates {
+ static const bool verbose = false;
+
+public:
+ EdgeDominates(Graph& graph, BasicBlock* block)
+ : m_graph(graph)
+ , m_block(block)
+ , m_result(true)
+ {
+ }
+
+ void operator()(Node*, Edge edge)
+ {
+ bool result = m_graph.m_dominators.dominates(edge.node()->misc.owner, m_block);
+ if (verbose) {
+ dataLog(
+ "Checking if ", edge, " in ", *edge.node()->misc.owner,
+ " dominates ", *m_block, ": ", result, "\n");
+ }
+ m_result &= result;
+ }
+
+ bool result() const { return m_result; }
+
+private:
+ Graph& m_graph;
+ BasicBlock* m_block;
+ bool m_result;
+};
+
+inline bool edgesDominate(Graph& graph, Node* node, BasicBlock* block)
+{
+ EdgeDominates edgeDominates(graph, block);
+ DFG_NODE_DO_TO_CHILDREN(graph, node, edgeDominates);
+ return edgeDominates.result();
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGEdgeDominates_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
index 8f27ef3..a005619 100644
--- a/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGFixupPhase.cpp
@@ -705,11 +705,6 @@
break;
}
- case CreateThis: {
- setUseKindAndUnboxIfProfitable<CellUse>(node->child1());
- break;
- }
-
case GetMyArgumentByVal:
case GetMyArgumentByValSafe: {
setUseKindAndUnboxIfProfitable<Int32Use>(node->child1());
@@ -725,8 +720,7 @@
case PutStructure:
case AllocatePropertyStorage:
case ReallocatePropertyStorage:
- case GetScope:
- case GetButterfly: {
+ case GetScope: {
setUseKindAndUnboxIfProfitable<KnownCellUse>(node->child1());
break;
}
@@ -789,7 +783,9 @@
case CheckFunction:
case PutById:
case PutByIdDirect:
- case CheckHasInstance: {
+ case CheckHasInstance:
+ case CreateThis:
+ case GetButterfly: {
setUseKindAndUnboxIfProfitable<CellUse>(node->child1());
break;
}
@@ -1245,7 +1241,7 @@
if (arrayMode.usesButterfly()) {
return m_insertionSet.insertNode(
- m_indexInBlock, SpecNone, GetButterfly, codeOrigin, Edge(array, KnownCellUse));
+ m_indexInBlock, SpecNone, GetButterfly, codeOrigin, Edge(array, CellUse));
}
return m_insertionSet.insertNode(
diff --git a/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
new file mode 100644
index 0000000..9049ccd
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
@@ -0,0 +1,276 @@
+/*
+ * Copyright (C) 2013 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 "DFGLICMPhase.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGAbstractInterpreterInlines.h"
+#include "DFGAtTailAbstractState.h"
+#include "DFGBasicBlockInlines.h"
+#include "DFGClobberSet.h"
+#include "DFGClobberize.h"
+#include "DFGEdgeDominates.h"
+#include "DFGGraph.h"
+#include "DFGInsertionSet.h"
+#include "DFGPhase.h"
+#include "DFGSafeToExecute.h"
+#include "Operations.h"
+
+namespace JSC { namespace DFG {
+
+namespace {
+
+struct LoopData {
+ LoopData()
+ : preHeader(0)
+ {
+ }
+
+ ClobberSet writes;
+ BasicBlock* preHeader;
+};
+
+} // anonymous namespace
+
+class LICMPhase : public Phase {
+ static const bool verbose = false;
+
+public:
+ LICMPhase(Graph& graph)
+ : Phase(graph, "LICM")
+ , m_interpreter(graph, m_state)
+ {
+ }
+
+ bool run()
+ {
+ ASSERT(m_graph.m_form == SSA);
+
+ m_graph.m_dominators.computeIfNecessary(m_graph);
+ m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+
+ m_data.resize(m_graph.m_naturalLoops.numLoops());
+
+ // Figure out the set of things each loop writes to, not including blocks that
+ // belong to inner loops. We fix this later.
+ for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+ BasicBlock* block = m_graph.block(blockIndex);
+ if (!block)
+ continue;
+ const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+ if (!loop)
+ continue;
+ LoopData& data = m_data[loop->index()];
+ for (unsigned nodeIndex = block->size(); nodeIndex--;)
+ addWrites(m_graph, block->at(nodeIndex), data.writes);
+ }
+
+ // For each loop:
+ // - Identify its pre-header.
+ // - Make sure its outer loops know what it clobbers.
+ for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
+ const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
+ LoopData& data = m_data[loop.index()];
+ for (
+ const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop);
+ outerLoop;
+ outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
+ m_data[outerLoop->index()].writes.addAll(data.writes);
+
+ BasicBlock* header = loop.header();
+ BasicBlock* preHeader = 0;
+ for (unsigned i = header->predecessors.size(); i--;) {
+ BasicBlock* predecessor = header->predecessors[i];
+ if (m_graph.m_dominators.dominates(header, predecessor))
+ continue;
+ RELEASE_ASSERT(!preHeader || preHeader == predecessor);
+ preHeader = predecessor;
+ }
+
+ RELEASE_ASSERT(preHeader->last()->op() == Jump);
+
+ data.preHeader = preHeader;
+ }
+
+ m_graph.initializeNodeOwners();
+
+ // Walk all basic blocks that belong to loops, looking for hoisting opportunities.
+ // We try to hoist to the outer-most loop that permits it. Hoisting is valid if:
+ // - The node doesn't write anything.
+ // - The node doesn't read anything that the loop writes.
+ // - The preHeader's state at tail makes the node safe to execute.
+ // - The loop's children all belong to nodes that strictly dominate the loop header.
+ // - The preHeader's state at tail is still valid. This is mostly to save compile
+ // time and preserve some kind of sanity, if we hoist something that must exit.
+ //
+ // Also, we need to remember to:
+ // - Clear NodeExitsForward for any nodes we hoisted.
+ // - Update the state-at-tail with the node we hoisted, so future hoist candidates
+ // know about any type checks we hoisted.
+ //
+ // For maximum profit, we walk blocks in DFS order to ensure that we generally
+ // tend to hoist dominators before dominatees.
+ Vector<BasicBlock*> depthFirst;
+ m_graph.getBlocksInDepthFirstOrder(depthFirst);
+ Vector<const NaturalLoop*> loopStack;
+ bool changed = false;
+ for (
+ unsigned depthFirstIndex = 0;
+ depthFirstIndex < depthFirst.size();
+ ++depthFirstIndex) {
+
+ BasicBlock* block = depthFirst[depthFirstIndex];
+ const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+ if (!loop)
+ continue;
+
+ loopStack.resize(0);
+ for (
+ const NaturalLoop* current = loop;
+ current;
+ current = m_graph.m_naturalLoops.innerMostOuterLoop(*current))
+ loopStack.append(current);
+
+ // Remember: the loop stack has the inner-most loop at index 0, so if we want
+ // to bias hoisting to outer loops then we need to use a reverse loop.
+
+ if (verbose) {
+ dataLog(
+ "Attempting to hoist out of block ", *block, " in loops:\n");
+ for (unsigned stackIndex = loopStack.size(); stackIndex--;) {
+ dataLog(
+ " ", *loopStack[stackIndex], ", which writes ",
+ m_data[loopStack[stackIndex]->index()].writes, "\n");
+ }
+ }
+
+ for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+ Node*& nodeRef = block->at(nodeIndex);
+ if (doesWrites(m_graph, nodeRef)) {
+ if (verbose)
+ dataLog(" Not hoisting ", nodeRef, " because it writes things.\n");
+ continue;
+ }
+
+ for (unsigned stackIndex = loopStack.size(); stackIndex--;)
+ changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]);
+ }
+ }
+
+ return changed;
+ }
+
+private:
+ bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop)
+ {
+ Node* node = nodeRef;
+ LoopData& data = m_data[loop->index()];
+
+ if (!data.preHeader->cfaDidFinish) {
+ if (verbose)
+ dataLog(" Not hoisting ", node, " because CFA is invalid.\n");
+ return false;
+ }
+
+ if (!edgesDominate(m_graph, node, data.preHeader)) {
+ if (verbose) {
+ dataLog(
+ " Not hoisting ", node, " because it isn't loop invariant.\n");
+ }
+ return false;
+ }
+
+ if (readsOverlap(m_graph, node, data.writes)) {
+ if (verbose) {
+ dataLog(
+ " Not hoisting ", node,
+ " because it reads things that the loop writes.\n");
+ }
+ return false;
+ }
+
+ m_state.initializeTo(data.preHeader);
+ if (!safeToExecute(m_state, m_graph, node)) {
+ if (verbose) {
+ dataLog(
+ " Not hoisting ", node, " because it isn't safe to execute.\n");
+ }
+ return false;
+ }
+
+ if (verbose) {
+ dataLog(
+ " Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader,
+ "\n");
+ }
+
+ data.preHeader->insertBeforeLast(node);
+ node->misc.owner = data.preHeader;
+ NodeFlags didExitForward = node->flags() & NodeExitsForward;
+ node->clearFlags(NodeExitsForward);
+ node->codeOriginForExitTarget = data.preHeader->last()->codeOriginForExitTarget;
+
+ // Modify the states at the end of the preHeader of the loop we hoisted to,
+ // and all pre-headers inside the loop.
+ // FIXME: This could become a scalability bottleneck. Fortunately, most loops
+ // are small and anyway we rapidly skip over basic blocks here.
+ for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
+ BasicBlock* subBlock = loop->at(bodyIndex);
+ const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
+ if (!subLoop)
+ continue;
+ BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
+ m_state.initializeTo(subPreHeader);
+ m_interpreter.execute(node);
+ }
+
+ // It just so happens that all of the nodes we currently know how to hoist
+ // don't have var-arg children. That may change and then we can fix this
+ // code. But for now we just assert that's the case.
+ RELEASE_ASSERT(!(node->flags() & NodeHasVarArgs));
+
+ nodeRef = m_graph.addNode(SpecNone, Phantom, node->codeOrigin, node->children);
+ nodeRef->mergeFlags(didExitForward);
+
+ return true;
+ }
+
+ AtTailAbstractState m_state;
+ AbstractInterpreter<AtTailAbstractState> m_interpreter;
+ Vector<LoopData> m_data;
+};
+
+bool performLICM(Graph& graph)
+{
+ SamplingRegion samplingRegion("DFG LICM Phase");
+ return runPhase<LICMPhase>(graph);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGLICMPhase.h b/Source/JavaScriptCore/dfg/DFGLICMPhase.h
new file mode 100644
index 0000000..601918b
--- /dev/null
+++ b/Source/JavaScriptCore/dfg/DFGLICMPhase.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2013 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.
+ */
+
+#ifndef DFGLICMPhase_h
+#define DFGLICMPhase_h
+
+#include <wtf/Platform.h>
+
+#if ENABLE(DFG_JIT)
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// Does loop-invariant code motion, or LICM for short. This only hoists code
+// and never sinks anything. A node is hoisted if it does no writes, and if
+// its reads don't overlap the loop's writes.
+
+bool performLICM(Graph&);
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGLICMPhase_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGPlan.cpp b/Source/JavaScriptCore/dfg/DFGPlan.cpp
index 3a2c8f7..70e7e4d 100644
--- a/Source/JavaScriptCore/dfg/DFGPlan.cpp
+++ b/Source/JavaScriptCore/dfg/DFGPlan.cpp
@@ -42,6 +42,7 @@
#include "DFGFlushLivenessAnalysisPhase.h"
#include "DFGFixupPhase.h"
#include "DFGJITCompiler.h"
+#include "DFGLICMPhase.h"
#include "DFGLivenessAnalysisPhase.h"
#include "DFGLoopPreHeaderCreationPhase.h"
#include "DFGOSRAvailabilityAnalysisPhase.h"
@@ -208,6 +209,9 @@
performSSAConversion(dfg);
performLivenessAnalysis(dfg);
performCFA(dfg);
+ performLICM(dfg);
+ performLivenessAnalysis(dfg);
+ performCFA(dfg);
performDCE(dfg); // We rely on this to convert dead SetLocals into the appropriate hint, and to kill dead code that won't be recognized as dead by LLVM.
performLivenessAnalysis(dfg);
performFlushLivenessAnalysis(dfg);
diff --git a/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp b/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
index 2df2bc6..f1a4646 100644
--- a/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
+++ b/Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
@@ -2458,8 +2458,8 @@
SpeculationDirection direction, FormattedValue recovery)
{
if (Options::ftlTrapsOnOSRExit()) {
- LBasicBlock failCase = FTL_NEW_BLOCK(m_out, ("OSR exit failCase"));
- LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("OSR exit continuation"));
+ LBasicBlock failCase = FTL_NEW_BLOCK(m_out, ("OSR exit failCase for ", m_node));
+ LBasicBlock continuation = FTL_NEW_BLOCK(m_out, ("OSR exit continuation for ", m_node));
m_out.branch(failCondition, failCase, continuation);
@@ -2490,8 +2490,8 @@
LBasicBlock continuation = 0;
if (!Options::useLLVMOSRExitIntrinsic()) {
- LBasicBlock failCase = FTL_NEW_BLOCK(m_out, ("OSR exit failCase"));
- continuation = FTL_NEW_BLOCK(m_out, ("OSR exit continuation"));
+ LBasicBlock failCase = FTL_NEW_BLOCK(m_out, ("OSR exit failCase for ", m_node));
+ continuation = FTL_NEW_BLOCK(m_out, ("OSR exit continuation for ", m_node));
m_out.branch(failCondition, failCase, continuation);
