DFG should compute immediate dominators using the O(n log n) form of Lengauer and...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Aug 2014 19:23:02 +0000 (19:23 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 28 Aug 2014 19:23:02 +0000 (19:23 +0000)
https://bugs.webkit.org/show_bug.cgi?id=93361

Reviewed by Mark Hahnenberg.

Source/JavaScriptCore:

This patch also adds some new utilities for reasoning about block-keyed maps, block sets,
and block worklists. It changes preexisting code to use these abstractions.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAnalysis.h:
(JSC::DFG::Analysis::computeIfNecessary):
(JSC::DFG::Analysis::computeDependencies):
* dfg/DFGBlockMap.h: Added.
(JSC::DFG::BlockMap::BlockMap):
(JSC::DFG::BlockMap::size):
(JSC::DFG::BlockMap::atIndex):
(JSC::DFG::BlockMap::operator[]):
* dfg/DFGBlockMapInlines.h: Added.
(JSC::DFG::BlockMap<T>::BlockMap):
* dfg/DFGBlockSet.h: Added.
(JSC::DFG::BlockSet::BlockSet):
(JSC::DFG::BlockSet::add):
(JSC::DFG::BlockSet::contains):
* dfg/DFGBlockWorklist.cpp: Added.
(JSC::DFG::BlockWorklist::BlockWorklist):
(JSC::DFG::BlockWorklist::~BlockWorklist):
(JSC::DFG::BlockWorklist::push):
(JSC::DFG::BlockWorklist::pop):
(JSC::DFG::PostOrderBlockWorklist::PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::~PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::pushPre):
(JSC::DFG::PostOrderBlockWorklist::pushPost):
(JSC::DFG::PostOrderBlockWorklist::pop):
* dfg/DFGBlockWorklist.h: Added.
(JSC::DFG::BlockWorklist::notEmpty):
(JSC::DFG::BlockWith::BlockWith):
(JSC::DFG::BlockWith::operator UnspecifiedBoolType*):
(JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist):
(JSC::DFG::ExtendedBlockWorklist::forcePush):
(JSC::DFG::ExtendedBlockWorklist::push):
(JSC::DFG::ExtendedBlockWorklist::notEmpty):
(JSC::DFG::ExtendedBlockWorklist::pop):
(JSC::DFG::BlockWithOrder::BlockWithOrder):
(JSC::DFG::BlockWithOrder::operator UnspecifiedBoolType*):
(JSC::DFG::PostOrderBlockWorklist::push):
(JSC::DFG::PostOrderBlockWorklist::notEmpty):
* dfg/DFGCSEPhase.cpp:
* dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::compute):
(JSC::DFG::Dominators::naiveDominates):
(JSC::DFG::Dominators::dump):
(JSC::DFG::Dominators::pruneDominators): Deleted.
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::strictlyDominates):
(JSC::DFG::Dominators::dominates):
(JSC::DFG::Dominators::BlockData::BlockData):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::getBlocksInPreOrder):
(JSC::DFG::Graph::getBlocksInPostOrder):
* dfg/DFGInvalidationPointInjectionPhase.cpp:
(JSC::DFG::InvalidationPointInjectionPhase::run):
* dfg/DFGNaiveDominators.cpp: Added.
(JSC::DFG::NaiveDominators::NaiveDominators):
(JSC::DFG::NaiveDominators::~NaiveDominators):
(JSC::DFG::NaiveDominators::compute):
(JSC::DFG::NaiveDominators::pruneDominators):
(JSC::DFG::NaiveDominators::dump):
* dfg/DFGNaiveDominators.h: Added.
(JSC::DFG::NaiveDominators::dominates):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoops::computeDependencies):
(JSC::DFG::NaturalLoops::compute):
* dfg/DFGNaturalLoops.h:

Source/WTF:

Make BitVector operations return the previous value of the bit you're changing. This is
useful for the kinds of set operations that are commonplace in compiler graph searches.

* wtf/BitVector.h:
(WTF::BitVector::quickSet):
(WTF::BitVector::quickClear):
(WTF::BitVector::set):
(WTF::BitVector::ensureSizeAndSet):
(WTF::BitVector::clear):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@173072 268f45cc-cd09-0410-ab3c-d52691b4dbfc

21 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGAnalysis.h
Source/JavaScriptCore/dfg/DFGBlockMap.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockMapInlines.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockSet.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockWorklist.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
Source/JavaScriptCore/dfg/DFGDominators.cpp
Source/JavaScriptCore/dfg/DFGDominators.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp
Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGNaiveDominators.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp
Source/JavaScriptCore/dfg/DFGNaturalLoops.h
Source/WTF/ChangeLog
Source/WTF/wtf/BitVector.h

index 60304ac..71cac67 100644 (file)
@@ -126,6 +126,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGBasicBlock.cpp
     dfg/DFGBinarySwitch.cpp
     dfg/DFGBlockInsertionSet.cpp
+    dfg/DFGBlockWorklist.cpp
     dfg/DFGByteCodeParser.cpp
     dfg/DFGCFAPhase.cpp
     dfg/DFGCFGSimplificationPhase.cpp
@@ -175,6 +176,7 @@ set(JavaScriptCore_SOURCES
     dfg/DFGLoopPreHeaderCreationPhase.cpp
     dfg/DFGMayExit.cpp
     dfg/DFGMinifiedNode.cpp
+    dfg/DFGNaiveDominators.cpp
     dfg/DFGNaturalLoops.cpp
     dfg/DFGNode.cpp
     dfg/DFGNodeFlags.cpp
index 43c7127..082afc3 100644 (file)
@@ -1,5 +1,88 @@
 2014-08-27  Filip Pizlo  <fpizlo@apple.com>
 
+        DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+        https://bugs.webkit.org/show_bug.cgi?id=93361
+
+        Reviewed by Mark Hahnenberg.
+        
+        This patch also adds some new utilities for reasoning about block-keyed maps, block sets,
+        and block worklists. It changes preexisting code to use these abstractions.
+        
+        The main effect of this code is that all current clients of dominators end up using the
+        results of the new idom calculation. We convert the dom tree to a dominance test using
+        Dietz's pre/post number range check trick.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * dfg/DFGAnalysis.h:
+        (JSC::DFG::Analysis::computeIfNecessary):
+        (JSC::DFG::Analysis::computeDependencies):
+        * dfg/DFGBlockMap.h: Added.
+        (JSC::DFG::BlockMap::BlockMap):
+        (JSC::DFG::BlockMap::size):
+        (JSC::DFG::BlockMap::atIndex):
+        (JSC::DFG::BlockMap::operator[]):
+        * dfg/DFGBlockMapInlines.h: Added.
+        (JSC::DFG::BlockMap<T>::BlockMap):
+        * dfg/DFGBlockSet.h: Added.
+        (JSC::DFG::BlockSet::BlockSet):
+        (JSC::DFG::BlockSet::add):
+        (JSC::DFG::BlockSet::contains):
+        * dfg/DFGBlockWorklist.cpp: Added.
+        (JSC::DFG::BlockWorklist::BlockWorklist):
+        (JSC::DFG::BlockWorklist::~BlockWorklist):
+        (JSC::DFG::BlockWorklist::push):
+        (JSC::DFG::BlockWorklist::pop):
+        (JSC::DFG::PostOrderBlockWorklist::PostOrderBlockWorklist):
+        (JSC::DFG::PostOrderBlockWorklist::~PostOrderBlockWorklist):
+        (JSC::DFG::PostOrderBlockWorklist::pushPre):
+        (JSC::DFG::PostOrderBlockWorklist::pushPost):
+        (JSC::DFG::PostOrderBlockWorklist::pop):
+        * dfg/DFGBlockWorklist.h: Added.
+        (JSC::DFG::BlockWorklist::notEmpty):
+        (JSC::DFG::BlockWith::BlockWith):
+        (JSC::DFG::BlockWith::operator UnspecifiedBoolType*):
+        (JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist):
+        (JSC::DFG::ExtendedBlockWorklist::forcePush):
+        (JSC::DFG::ExtendedBlockWorklist::push):
+        (JSC::DFG::ExtendedBlockWorklist::notEmpty):
+        (JSC::DFG::ExtendedBlockWorklist::pop):
+        (JSC::DFG::BlockWithOrder::BlockWithOrder):
+        (JSC::DFG::BlockWithOrder::operator UnspecifiedBoolType*):
+        (JSC::DFG::PostOrderBlockWorklist::push):
+        (JSC::DFG::PostOrderBlockWorklist::notEmpty):
+        * dfg/DFGCSEPhase.cpp:
+        * dfg/DFGDominators.cpp:
+        (JSC::DFG::Dominators::compute):
+        (JSC::DFG::Dominators::naiveDominates):
+        (JSC::DFG::Dominators::dump):
+        (JSC::DFG::Dominators::pruneDominators): Deleted.
+        * dfg/DFGDominators.h:
+        (JSC::DFG::Dominators::strictlyDominates):
+        (JSC::DFG::Dominators::dominates):
+        (JSC::DFG::Dominators::BlockData::BlockData):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::dumpBlockHeader):
+        (JSC::DFG::Graph::getBlocksInPreOrder):
+        (JSC::DFG::Graph::getBlocksInPostOrder):
+        * dfg/DFGInvalidationPointInjectionPhase.cpp:
+        (JSC::DFG::InvalidationPointInjectionPhase::run):
+        * dfg/DFGNaiveDominators.cpp: Added.
+        (JSC::DFG::NaiveDominators::NaiveDominators):
+        (JSC::DFG::NaiveDominators::~NaiveDominators):
+        (JSC::DFG::NaiveDominators::compute):
+        (JSC::DFG::NaiveDominators::pruneDominators):
+        (JSC::DFG::NaiveDominators::dump):
+        * dfg/DFGNaiveDominators.h: Added.
+        (JSC::DFG::NaiveDominators::dominates):
+        * dfg/DFGNaturalLoops.cpp:
+        (JSC::DFG::NaturalLoops::computeDependencies):
+        (JSC::DFG::NaturalLoops::compute):
+        * dfg/DFGNaturalLoops.h:
+
+2014-08-27  Filip Pizlo  <fpizlo@apple.com>
+
         FTL should be able to do polymorphic call inlining
         https://bugs.webkit.org/show_bug.cgi?id=135145
 
index 2d6fe91..ba7ee5e 100644 (file)
     <ClCompile Include="..\dfg\DFGBasicBlock.cpp" />
     <ClCompile Include="..\dfg\DFGBinarySwitch.cpp" />
     <ClCompile Include="..\dfg\DFGBlockInsertionSet.cpp" />
+    <ClCompile Include="..\dfg\DFGBlockWorklist.cpp" />
     <ClCompile Include="..\dfg\DFGByteCodeParser.cpp" />
     <ClCompile Include="..\dfg\DFGCapabilities.cpp" />
     <ClCompile Include="..\dfg\DFGCFAPhase.cpp" />
     <ClCompile Include="..\dfg\DFGLoopPreHeaderCreationPhase.cpp" />
     <ClCompile Include="..\dfg\DFGMayExit.cpp" />
     <ClCompile Include="..\dfg\DFGMinifiedNode.cpp" />
+    <ClCompile Include="..\dfg\DFGNaiveDominators.cpp" />
     <ClCompile Include="..\dfg\DFGNaturalLoops.cpp" />
     <ClCompile Include="..\dfg\DFGNode.cpp" />
     <ClCompile Include="..\dfg\DFGNodeFlags.cpp" />
     <ClInclude Include="..\dfg\DFGBasicBlockInlines.h" />
     <ClInclude Include="..\dfg\DFGBinarySwitch.h" />
     <ClInclude Include="..\dfg\DFGBlockInsertionSet.h" />
+    <ClInclude Include="..\dfg\DFGBlockMap.h" />
+    <ClInclude Include="..\dfg\DFGBlockMapInlines.h" />
+    <ClInclude Include="..\dfg\DFGBlockWorklist.h" />
+    <ClInclude Include="..\dfg\DFGBlockSet.h" />
     <ClInclude Include="..\dfg\DFGBranchDirection.h" />
     <ClInclude Include="..\dfg\DFGByteCodeParser.h" />
     <ClInclude Include="..\dfg\DFGCallArrayAllocatorSlowPathGenerator.h" />
     <ClInclude Include="..\dfg\DFGMinifiedGraph.h" />
     <ClInclude Include="..\dfg\DFGMinifiedID.h" />
     <ClInclude Include="..\dfg\DFGMinifiedNode.h" />
+    <ClInclude Include="..\dfg\DFGNaiveDominators.h" />
     <ClInclude Include="..\dfg\DFGNaturalLoops.h" />
     <ClInclude Include="..\dfg\DFGNode.h" />
     <ClInclude Include="..\dfg\DFGNodeAllocator.h" />
index cf73ee3..94fdb0e 100644 (file)
                0FC314121814559100033232 /* RegisterSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC314101814559100033232 /* RegisterSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FC314131814559100033232 /* TempRegisterSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC314111814559100033232 /* TempRegisterSet.cpp */; };
                0FC3141518146D7000033232 /* RegisterSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3141418146D7000033232 /* RegisterSet.cpp */; };
+               0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */; };
+               0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
+               0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FC712DE17CD8779008CC93C /* DeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */; };
                0FC712DF17CD877C008CC93C /* DeferredCompilationCallback.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FC712E217CD8791008CC93C /* JITToDFGDeferredCompilationCallback.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */; };
                0FC314101814559100033232 /* RegisterSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RegisterSet.h; sourceTree = "<group>"; };
                0FC314111814559100033232 /* TempRegisterSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TempRegisterSet.cpp; sourceTree = "<group>"; };
                0FC3141418146D7000033232 /* RegisterSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RegisterSet.cpp; sourceTree = "<group>"; };
+               0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMap.h; path = dfg/DFGBlockMap.h; sourceTree = "<group>"; };
+               0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockMapInlines.h; path = dfg/DFGBlockMapInlines.h; sourceTree = "<group>"; };
+               0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockSet.h; path = dfg/DFGBlockSet.h; sourceTree = "<group>"; };
+               0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGBlockWorklist.cpp; path = dfg/DFGBlockWorklist.cpp; sourceTree = "<group>"; };
+               0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBlockWorklist.h; path = dfg/DFGBlockWorklist.h; sourceTree = "<group>"; };
+               0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaiveDominators.cpp; path = dfg/DFGNaiveDominators.cpp; sourceTree = "<group>"; };
+               0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaiveDominators.h; path = dfg/DFGNaiveDominators.h; sourceTree = "<group>"; };
                0FC712DC17CD8778008CC93C /* DeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = DeferredCompilationCallback.cpp; sourceTree = "<group>"; };
                0FC712DD17CD8778008CC93C /* DeferredCompilationCallback.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferredCompilationCallback.h; sourceTree = "<group>"; };
                0FC712E017CD878F008CC93C /* JITToDFGDeferredCompilationCallback.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = JITToDFGDeferredCompilationCallback.cpp; sourceTree = "<group>"; };
                                A70B083117A0B79B00DAF14B /* DFGBinarySwitch.h */,
                                A7D89CE417A0B8CC00773AD8 /* DFGBlockInsertionSet.cpp */,
                                A7D89CE517A0B8CC00773AD8 /* DFGBlockInsertionSet.h */,
+                               0FC3CCF519ADA410006AC72A /* DFGBlockMap.h */,
+                               0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */,
+                               0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */,
+                               0FC3CCF819ADA410006AC72A /* DFGBlockWorklist.cpp */,
+                               0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */,
                                0F8364B5164B0C0E0053329A /* DFGBranchDirection.h */,
                                86EC9DB41328DF82002B2AD7 /* DFGByteCodeParser.cpp */,
                                86EC9DB51328DF82002B2AD7 /* DFGByteCodeParser.h */,
                                0FB4B51016B3A964003F696B /* DFGMinifiedID.h */,
                                0F2BDC4C1522818300CD8910 /* DFGMinifiedNode.cpp */,
                                0F2BDC3E1522801700CD8910 /* DFGMinifiedNode.h */,
+                               0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */,
+                               0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */,
                                A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
                                A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
                                0FB4B51E16B62772003F696B /* DFGNode.cpp */,
                                C2FC9BD316644DFB00810D33 /* CopiedBlockInlines.h in Headers */,
                                C2EAA3FA149A835E00FCE112 /* CopiedSpace.h in Headers */,
                                C2C8D02D14A3C6E000578E65 /* CopiedSpaceInlines.h in Headers */,
+                               0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */,
                                0F5A52D017ADD717008ECB2D /* CopyToken.h in Headers */,
                                C2239D1816262BDD005AC5FD /* CopyVisitor.h in Headers */,
                                C2239D1916262BDD005AC5FD /* CopyVisitorInlines.h in Headers */,
                                A7BFF3C0179868940002F462 /* DFGFiltrationResult.h in Headers */,
                                A78A9777179738B8009DF744 /* DFGFinalizer.h in Headers */,
                                0F2BDC16151C5D4F00CD8910 /* DFGFixupPhase.h in Headers */,
+                               0FC3CCFC19ADA410006AC72A /* DFGBlockMap.h in Headers */,
                                0F9D339717FFC4E60073C2BC /* DFGFlushedAt.h in Headers */,
                                A7D89CF817A0B8CC00773AD8 /* DFGFlushFormat.h in Headers */,
                                86EC9DC61328DF82002B2AD7 /* DFGGenerationInfo.h in Headers */,
                                0F431738146BAC69007E3890 /* ListableHandler.h in Headers */,
                                A7E2EA6B0FB460CF00601F06 /* LiteralParser.h in Headers */,
                                0F0FC45A14BD15F500B81154 /* LLIntCallLinkInfo.h in Headers */,
+                               0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */,
                                FE20CE9E15F04A9500DF3430 /* LLIntCLoop.h in Headers */,
                                0F4680CA14BBB16C00BFE272 /* LLIntCommon.h in Headers */,
                                0F4680D314BBD16700BFE272 /* LLIntData.h in Headers */,
                                0F0123331944EA1B00843A0C /* DFGValueStrength.h in Headers */,
                                0FCEFACE1805E75500472CE4 /* LLVMAPI.h in Headers */,
                                0FCEFACF1805E75500472CE4 /* LLVMAPIFunctions.h in Headers */,
+                               0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */,
                                A7E5AB381799E4B200D2833D /* LLVMDisassembler.h in Headers */,
                                0FCEFAD31805EDCC00472CE4 /* LLVMHeaders.h in Headers */,
                                142E3139134FF0A600AFADB5 /* Local.h in Headers */,
                                7EFF00640EC05A9A00AA7C93 /* NodeInfo.h in Headers */,
                                BC18C43F0E16F5CD00B34460 /* Nodes.h in Headers */,
                                99E45A2818A1B2590026D88F /* NondeterministicInput.h in Headers */,
+                               0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */,
                                BC18C4410E16F5CD00B34460 /* NumberConstructor.h in Headers */,
                                0F5780A218FE1E98001E72D9 /* PureNaN.h in Headers */,
                                BC18C4420E16F5CD00B34460 /* NumberConstructor.lut.h in Headers */,
                                A7D89CFF17A0B8CC00773AD8 /* DFGSSAConversionPhase.cpp in Sources */,
                                2A05ABD51961DF2400341750 /* JSPropertyNameEnumerator.cpp in Sources */,
                                0FC20CB918556A3500C9E954 /* DFGSSALoweringPhase.cpp in Sources */,
+                               0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */,
                                0F9FB4F417FCB91700CB67F8 /* DFGStackLayoutPhase.cpp in Sources */,
                                0F4F29DF18B6AD1C0057BC15 /* DFGStaticExecutionCountEstimationPhase.cpp in Sources */,
                                0FE7211D193B9C590031F6ED /* DFGTransition.cpp in Sources */,
                                0FD8A31917D51F2200CA2C40 /* FTLForOSREntryJITCode.cpp in Sources */,
                                0F25F1AF181635F300522F39 /* FTLInlineCacheSize.cpp in Sources */,
                                0FEA0A281709623B00BB722C /* FTLIntrinsicRepository.cpp in Sources */,
+                               0FC3CCFF19ADA410006AC72A /* DFGBlockWorklist.cpp in Sources */,
                                0FEA0A0D170513DB00BB722C /* FTLJITCode.cpp in Sources */,
                                A78A9780179738D5009DF744 /* FTLJITFinalizer.cpp in Sources */,
                                0F6B1CB5185FC9E900845D97 /* FTLJSCall.cpp in Sources */,
index 2b9d149..4e66f76 100644 (file)
@@ -53,6 +53,8 @@ public:
     {
         if (m_valid)
             return;
+        // It's best to run dependent analyses from this method.
+        static_cast<T*>(this)->computeDependencies(graph);
         // Set to true early, since the analysis may choose to call its own methods in
         // compute() and it may want to ASSERT() validity in those methods.
         m_valid = true;
@@ -61,6 +63,12 @@ public:
     
     bool isValid() const { return m_valid; }
 
+    // Override this to compute any dependent analyses. See
+    // NaturalLoops::computeDependencies(Graph&) for an example. This isn't strictly necessary but
+    // it makes debug dumps in cases of error work a bit better because this analysis wouldn't yet
+    // be pretending to be valid.
+    void computeDependencies(Graph&) { }
+
 private:
     bool m_valid;
 };
diff --git a/Source/JavaScriptCore/dfg/DFGBlockMap.h b/Source/JavaScriptCore/dfg/DFGBlockMap.h
new file mode 100644 (file)
index 0000000..1b8ddd3
--- /dev/null
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2014 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 DFGBlockMap_h
+#define DFGBlockMap_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+template<typename T>
+class BlockMap {
+public:
+    BlockMap()
+    {
+    }
+    
+    BlockMap(Graph&);
+    
+    BlockIndex size() const
+    {
+        return m_vector.size();
+    }
+    
+    T& atIndex(BlockIndex blockIndex)
+    {
+        return m_vector[blockIndex];
+    }
+    
+    const T& atIndex(BlockIndex blockIndex) const
+    {
+        return m_vector[blockIndex];
+    }
+    
+    T& operator[](BlockIndex blockIndex)
+    {
+        return m_vector[blockIndex];
+    }
+    
+    const T& operator[](BlockIndex blockIndex) const
+    {
+        return m_vector[blockIndex];
+    }
+    
+    T& operator[](BasicBlock* block)
+    {
+        return m_vector[block->index];
+    }
+    
+    const T& operator[](BasicBlock* block) const
+    {
+        return m_vector[block->index];
+    }
+
+private:
+    Vector<T> m_vector;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockMap_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h b/Source/JavaScriptCore/dfg/DFGBlockMapInlines.h
new file mode 100644 (file)
index 0000000..e61626d
--- /dev/null
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2014 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 DFGBlockMapInlines_h
+#define DFGBlockMapInlines_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBlockMap.h"
+#include "DFGGraph.h"
+
+namespace JSC { namespace DFG {
+
+template<typename T>
+BlockMap<T>::BlockMap(Graph& graph)
+{
+    m_vector.resize(graph.numBlocks());
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockMapInlines_h
diff --git a/Source/JavaScriptCore/dfg/DFGBlockSet.h b/Source/JavaScriptCore/dfg/DFGBlockSet.h
new file mode 100644 (file)
index 0000000..2764908
--- /dev/null
@@ -0,0 +1,61 @@
+/*
+ * Copyright (C) 2014 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 DFGBlockSet_h
+#define DFGBlockSet_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+class BlockSet {
+public:
+    BlockSet() { }
+    
+    // Return true if the block was added, false if it was already present.
+    bool add(BasicBlock* block)
+    {
+        return !m_set.set(block->index);
+    }
+    
+    bool contains(BasicBlock* block) const
+    {
+        if (!block)
+            return false;
+        return m_set.get(block->index);
+    }
+    
+private:
+    BitVector m_set;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockSet_h
+
diff --git a/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp b/Source/JavaScriptCore/dfg/DFGBlockWorklist.cpp
new file mode 100644 (file)
index 0000000..1caf9ca
--- /dev/null
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2014 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 "DFGBlockWorklist.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+
+namespace JSC { namespace DFG {
+
+BlockWorklist::BlockWorklist()
+{
+}
+
+BlockWorklist::~BlockWorklist()
+{
+}
+
+bool BlockWorklist::push(BasicBlock* block)
+{
+    if (!m_seen.add(block))
+        return false;
+    
+    m_stack.append(block);
+    return true;
+}
+
+BasicBlock* BlockWorklist::pop()
+{
+    if (m_stack.isEmpty())
+        return nullptr;
+    
+    return m_stack.takeLast();
+}
+
+PostOrderBlockWorklist::PostOrderBlockWorklist()
+{
+}
+
+PostOrderBlockWorklist::~PostOrderBlockWorklist()
+{
+}
+
+bool PostOrderBlockWorklist::pushPre(BasicBlock* block)
+{
+    return m_worklist.push(block, PreOrder);
+}
+
+void PostOrderBlockWorklist::pushPost(BasicBlock* block)
+{
+    m_worklist.forcePush(block, PostOrder);
+}
+
+BlockWithOrder PostOrderBlockWorklist::pop()
+{
+    BlockWith<VisitOrder> result = m_worklist.pop();
+    return BlockWithOrder(result.block, result.data);
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
diff --git a/Source/JavaScriptCore/dfg/DFGBlockWorklist.h b/Source/JavaScriptCore/dfg/DFGBlockWorklist.h
new file mode 100644 (file)
index 0000000..9f5dfb4
--- /dev/null
@@ -0,0 +1,192 @@
+/*
+ * Copyright (C) 2014 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 DFGBlockWorklist_h
+#define DFGBlockWorklist_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGBlockSet.h"
+#include <wtf/Vector.h>
+
+namespace JSC { namespace DFG {
+
+struct BasicBlock;
+
+class BlockWorklist {
+public:
+    BlockWorklist();
+    ~BlockWorklist();
+    
+    bool push(BasicBlock*); // Returns true if we didn't know about the block before.
+    
+    bool notEmpty() const { return !m_stack.isEmpty(); }
+    BasicBlock* pop();
+    
+private:
+    BlockSet m_seen;
+    Vector<BasicBlock*, 16> m_stack;
+};
+
+// When you say BlockWith<int> you should read it as "block with an int".
+template<typename T>
+struct BlockWith {
+    BlockWith()
+        : block(nullptr)
+    {
+    }
+    
+    BlockWith(BasicBlock* block, const T& data)
+        : block(block)
+        , data(data)
+    {
+    }
+    
+    typedef void* (BlockWith<T>::*UnspecifiedBoolType);
+    operator UnspecifiedBoolType*() const
+    {
+        return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
+    }
+
+    BasicBlock* block;
+    T data;
+};
+
+// Extended block worklist is useful for enqueueing some meta-data along with the block. It also
+// permits forcibly enqueueing things even if the block has already been seen. It's useful for
+// things like building a spanning tree, in which case T (the auxiliary payload) would be the
+// successor index.
+template<typename T>
+class ExtendedBlockWorklist {
+public:
+    ExtendedBlockWorklist() { }
+    
+    void forcePush(const BlockWith<T>& entry)
+    {
+        m_stack.append(entry);
+    }
+    
+    void forcePush(BasicBlock* block, const T& data)
+    {
+        forcePush(BlockWith<T>(block, data));
+    }
+    
+    bool push(const BlockWith<T>& entry)
+    {
+        if (!m_seen.add(entry.block))
+            return false;
+        
+        forcePush(entry);
+        return true;
+    }
+    
+    bool push(BasicBlock* block, const T& data)
+    {
+        return push(BlockWith<T>(block, data));
+    }
+    
+    bool notEmpty() const { return !m_stack.isEmpty(); }
+    
+    BlockWith<T> pop()
+    {
+        if (m_stack.isEmpty())
+            return BlockWith<T>();
+        
+        return m_stack.takeLast();
+    }
+
+private:
+    BlockSet m_seen;
+    Vector<BlockWith<T>> m_stack;
+};
+
+enum VisitOrder {
+    PreOrder,
+    PostOrder
+};
+
+struct BlockWithOrder {
+    BlockWithOrder()
+        : block(nullptr)
+        , order(PreOrder)
+    {
+    }
+    
+    BlockWithOrder(BasicBlock* block, VisitOrder order)
+        : block(block)
+        , order(order)
+    {
+    }
+    
+    typedef void* (BlockWithOrder::*UnspecifiedBoolType);
+    operator UnspecifiedBoolType*() const
+    {
+        return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
+    }
+
+    BasicBlock* block;
+    VisitOrder order;
+};
+
+// Block worklist suitable for post-order traversal.
+class PostOrderBlockWorklist {
+public:
+    PostOrderBlockWorklist();
+    ~PostOrderBlockWorklist();
+    
+    bool pushPre(BasicBlock*);
+    void pushPost(BasicBlock*);
+    
+    bool push(BasicBlock* block, VisitOrder order = PreOrder)
+    {
+        switch (order) {
+        case PreOrder:
+            return pushPre(block);
+        case PostOrder:
+            pushPost(block);
+            return true;
+        }
+        RELEASE_ASSERT_NOT_REACHED();
+        return false;
+    }
+    bool push(const BlockWithOrder& data)
+    {
+        return push(data.block, data.order);
+    }
+    
+    bool notEmpty() const { return m_worklist.notEmpty(); }
+    BlockWithOrder pop();
+
+private:
+    ExtendedBlockWorklist<VisitOrder> m_worklist;
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGBlockWorklist_h
+
index f6d7df5..185332f 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGAbstractHeap.h"
+#include "DFGBlockMapInlines.h"
 #include "DFGClobberSet.h"
 #include "DFGClobberize.h"
 #include "DFGEdgeUsesStructure.h"
@@ -364,6 +365,7 @@ class GlobalCSEPhase : public Phase {
 public:
     GlobalCSEPhase(Graph& graph)
         : Phase(graph, "global common subexpression elimination")
+        , m_impureDataMap(graph)
     {
     }
     
@@ -377,13 +379,11 @@ public:
         
         m_graph.getBlocksInPreOrder(m_preOrder);
         
-        m_impureDataMap.resize(m_graph.numBlocks());
-        
         // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
         // for convenience only.
         for (unsigned i = m_preOrder.size(); i--;) {
             m_block = m_preOrder[i];
-            m_impureData = &m_impureDataMap[m_block->index];
+            m_impureData = &m_impureDataMap[m_block];
             for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
                 addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
         }
@@ -407,7 +407,7 @@ public:
     {
         m_pureValues.clear();
         
-        for (unsigned i = m_impureDataMap.size(); i--;) {
+        for (BlockIndex i = m_impureDataMap.size(); i--;) {
             m_impureDataMap[i].availableAtTail.clear();
             m_impureDataMap[i].didVisit = false;
         }
@@ -423,7 +423,7 @@ public:
         
         for (unsigned i = 0; i < m_preOrder.size(); ++i) {
             m_block = m_preOrder[i];
-            m_impureData = &m_impureDataMap[m_block->index];
+            m_impureData = &m_impureDataMap[m_block];
             m_writesSoFar.clear();
             
             if (verbose)
@@ -562,12 +562,12 @@ public:
             
             if (verbose)
                 dataLog("      Searching in block ", *block, "\n");
-            ImpureBlockData& data = m_impureDataMap[block->index];
+            ImpureBlockData& data = m_impureDataMap[block];
             
             // We require strict domination because this would only see things in our own block if
             // they came *after* our position in the block. Clearly, while our block dominates
             // itself, the things in the block after us don't dominate us.
-            if (m_graph.m_dominators.dominates(block, m_block) && block != m_block) {
+            if (m_graph.m_dominators.strictlyDominates(block, m_block)) {
                 if (verbose)
                     dataLog("        It strictly dominates.\n");
                 DFG_ASSERT(m_graph, m_node, data.didVisit);
@@ -612,7 +612,7 @@ public:
         // the reduction in compile time would warrant the increase in complexity, though.
         // https://bugs.webkit.org/show_bug.cgi?id=134876
         for (BasicBlock* block : seenList)
-            m_impureDataMap[block->index].availableAtTail.add(location, match);
+            m_impureDataMap[block].availableAtTail.add(location, match);
         m_impureData->availableAtTail.add(location, match);
         
         return match;
@@ -654,7 +654,7 @@ public:
     Vector<BasicBlock*> m_preOrder;
 
     PureMultiMap m_pureValues;
-    Vector<ImpureBlockData> m_impureDataMap;
+    BlockMap<ImpureBlockData> m_impureDataMap;
     
     BasicBlock* m_block;
     Node* m_node;
index bdd6a6a..61a9b5b 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGBlockMapInlines.h"
+#include "DFGBlockWorklist.h"
 #include "DFGGraph.h"
+#include "DFGNaiveDominators.h"
 #include "JSCInlines.h"
 
 namespace JSC { namespace DFG {
@@ -41,91 +44,387 @@ Dominators::~Dominators()
 {
 }
 
-void Dominators::compute(Graph& graph)
-{
-    // This implements a naive dominator solver.
-    
-    ASSERT(graph.block(0)->predecessors.isEmpty());
+namespace {
+
+// This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+// (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n)
+// solution. The full paper is linked below; this code attempts to closely follow the algorithm as
+// it is presented in the paper; in particular sections 3 and 4 as well as appendix B.
+// https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
+//
+// This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The
+// goal of this code is to follow the code in the paper, however our implementation must deviate
+// from the paper when it comes to recursion. The authors had used recursion to implement DFS, and
+// also to implement the "simple" EVAL. We convert both of those into worklist-based solutions.
+// Finally, once the algorithm gives us immediate dominators, we implement dominance tests by
+// walking the dominator tree and computing pre and post numbers. We then use the range inclusion
+// check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked
+// list" (see http://dl.acm.org/citation.cfm?id=802184).
+
+class LengauerTarjan {
+public:
+    LengauerTarjan(Graph& graph)
+        : m_graph(graph)
+        , m_data(graph)
+    {
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            m_data[block].label = block;
+        }
+    }
     
-    unsigned numBlocks = graph.numBlocks();
+    void compute()
+    {
+        computeDepthFirstPreNumbering(); // Step 1.
+        computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
+        computeExplicitImmediateDominators(); // Step 4.
+    }
     
-    // Allocate storage for the dense dominance matrix. 
-    if (numBlocks > m_results.size()) {
-        m_results.grow(numBlocks);
-        for (unsigned i = numBlocks; i--;)
-            m_results[i].resize(numBlocks);
-        m_scratch.resize(numBlocks);
+    BasicBlock* immediateDominator(BasicBlock* block)
+    {
+        return m_data[block].dom;
     }
 
-    // We know that the entry block is only dominated by itself.
-    m_results[0].clearAll();
-    m_results[0].set(0);
+private:
+    void computeDepthFirstPreNumbering()
+    {
+        // Use a block worklist that also tracks the index inside the successor list. This is
+        // necessary for ensuring that we don't attempt to visit a successor until the previous
+        // successors that we had visited are fully processed. This ends up being revealed in the
+        // output of this method because the first time we see an edge to a block, we set the
+        // block's parent. So, if we have:
+        //
+        // A -> B
+        // A -> C
+        // B -> C
+        //
+        // And we're processing A, then we want to ensure that if we see A->B first (and hence set
+        // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue
+        // of not noticing A->C until we're done processing B.
+        
+        ExtendedBlockWorklist<unsigned> worklist;
+        worklist.push(m_graph.block(0), 0);
+        
+        while (BlockWith<unsigned> item = worklist.pop()) {
+            BasicBlock* block = item.block;
+            unsigned successorIndex = item.data;
+            
+            // We initially push with successorIndex = 0 regardless of whether or not we have any
+            // successors. This is so that we can assign our prenumber. Subsequently we get pushed
+            // with higher successorIndex values, but only if they are in range.
+            ASSERT(!successorIndex || successorIndex < block->numSuccessors());
 
-    // Find all of the valid blocks.
-    m_scratch.clearAll();
-    for (unsigned i = numBlocks; i--;) {
-        if (!graph.block(i))
-            continue;
-        m_scratch.set(i);
+            if (!successorIndex) {
+                m_data[block].semiNumber = m_blockByPreNumber.size();
+                m_blockByPreNumber.append(block);
+            }
+            
+            if (successorIndex < block->numSuccessors()) {
+                unsigned nextSuccessorIndex = successorIndex + 1;
+                if (nextSuccessorIndex < block->numSuccessors())
+                    worklist.forcePush(block, nextSuccessorIndex);
+
+                BasicBlock* successorBlock = block->successor(successorIndex);
+                if (worklist.push(successorBlock, 0))
+                    m_data[successorBlock].parent = block;
+            }
+        }
+    }
+    
+    void computeSemiDominatorsAndImplicitImmediateDominators()
+    {
+        for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+            BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+            BlockData& blockData = m_data[block];
+            
+            // Step 2:
+            for (BasicBlock* predecessorBlock : block->predecessors) {
+                BasicBlock* intermediateBlock = eval(predecessorBlock);
+                blockData.semiNumber = std::min(
+                    m_data[intermediateBlock].semiNumber, blockData.semiNumber);
+            }
+            unsigned bucketPreNumber = blockData.semiNumber;
+            ASSERT(bucketPreNumber <= currentPreNumber);
+            m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
+            link(blockData.parent, block);
+            
+            // Step 3:
+            for (BasicBlock* semiDominee : m_data[blockData.parent].bucket) {
+                BasicBlock* possibleDominator = eval(semiDominee);
+                BlockData& semiDomineeData = m_data[semiDominee];
+                ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
+                BlockData& possibleDominatorData = m_data[possibleDominator];
+                if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
+                    semiDomineeData.dom = possibleDominator;
+                else
+                    semiDomineeData.dom = blockData.parent;
+            }
+            m_data[blockData.parent].bucket.clear();
+        }
     }
     
-    // Mark all nodes as dominated by everything.
-    for (unsigned i = numBlocks; i-- > 1;) {
-        if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
-            m_results[i].clearAll();
-        else
-            m_results[i].set(m_scratch);
+    void computeExplicitImmediateDominators()
+    {
+        for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+            BasicBlock* block = m_blockByPreNumber[currentPreNumber];
+            BlockData& blockData = m_data[block];
+            
+            if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
+                blockData.dom = m_data[blockData.dom].dom;
+        }
+    }
+    
+    void link(BasicBlock* from, BasicBlock* to)
+    {
+        m_data[to].ancestor = from;
+    }
+    
+    BasicBlock* eval(BasicBlock* block)
+    {
+        if (!m_data[block].ancestor)
+            return block;
+        
+        compress(block);
+        return m_data[block].label;
+    }
+    
+    void compress(BasicBlock* initialBlock)
+    {
+        // This was meant to be a recursive function, but we don't like recursion because we don't
+        // want to blow the stack. The original function will call compress() recursively on the
+        // ancestor of anything that has an ancestor. So, we populate our worklist with the
+        // recursive ancestors of initialBlock. Then we process the list starting from the block
+        // that is furthest up the ancestor chain.
+        
+        BasicBlock* ancestor = m_data[initialBlock].ancestor;
+        ASSERT(ancestor);
+        if (!m_data[ancestor].ancestor)
+            return;
+        
+        Vector<BasicBlock*, 16> stack;
+        for (BasicBlock* block = initialBlock; block; block = m_data[block].ancestor)
+            stack.append(block);
+        
+        // We only care about blocks that have an ancestor that has an ancestor. The last two
+        // elements in the stack won't satisfy this property.
+        ASSERT(stack.size() >= 2);
+        ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
+        ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
+        
+        for (unsigned i = stack.size() - 2; i--;) {
+            BasicBlock* block = stack[i];
+            BasicBlock*& labelOfBlock = m_data[block].label;
+            BasicBlock*& ancestorOfBlock = m_data[block].ancestor;
+            ASSERT(ancestorOfBlock);
+            ASSERT(m_data[ancestorOfBlock].ancestor);
+            
+            BasicBlock* labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+            
+            if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+                labelOfBlock = labelOfAncestorOfBlock;
+            ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+        }
     }
 
-    // Iteratively eliminate nodes that are not dominator.
-    bool changed;
-    do {
-        changed = false;
-        // Prune dominators in all non entry blocks: forward scan.
-        for (unsigned i = 1; i < numBlocks; ++i)
-            changed |= pruneDominators(graph, i);
+    struct BlockData {
+        BlockData()
+            : parent(nullptr)
+            , preNumber(UINT_MAX)
+            , semiNumber(UINT_MAX)
+            , ancestor(nullptr)
+            , label(nullptr)
+            , dom(nullptr)
+        {
+        }
+        
+        BasicBlock* parent;
+        unsigned preNumber;
+        unsigned semiNumber;
+        BasicBlock* ancestor;
+        BasicBlock* label;
+        Vector<BasicBlock*> bucket;
+        BasicBlock* dom;
+    };
+    
+    Graph& m_graph;
+    BlockMap<BlockData> m_data;
+    Vector<BasicBlock*> m_blockByPreNumber;
+};
 
-        if (!changed)
-            break;
+struct ValidationContext {
+    ValidationContext(Graph& graph, Dominators& dominators)
+        : graph(graph)
+        , dominators(dominators)
+    {
+    }
+    
+    void reportError(BasicBlock* from, BasicBlock* to, const char* message)
+    {
+        Error error;
+        error.from = from;
+        error.to = to;
+        error.message = message;
+        errors.append(error);
+    }
+    
+    void handleErrors()
+    {
+        if (errors.isEmpty())
+            return;
+        
+        startCrashing();
+        dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
+        dataLog("\n");
+        dataLog("For block domination relationships:\n");
+        for (unsigned i = 0; i < errors.size(); ++i) {
+            dataLog(
+                "    ", pointerDump(errors[i].from), " -> ", pointerDump(errors[i].to),
+                " (", errors[i].message, ")\n");
+        }
+        dataLog("\n");
+        dataLog("Control flow graph:\n");
+        for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
+            BasicBlock* block = graph.block(blockIndex);
+            if (!block)
+                continue;
+            dataLog("    Block #", blockIndex, ": successors = [");
+            CommaPrinter comma;
+            for (unsigned i = 0; i < block->numSuccessors(); ++i)
+                dataLog(comma, *block->successor(i));
+            dataLog("], predecessors = [");
+            comma = CommaPrinter();
+            for (unsigned i = 0; i < block->predecessors.size(); ++i)
+                dataLog(comma, *block->predecessors[i]);
+            dataLog("]\n");
+        }
+        dataLog("\n");
+        dataLog("Lengauer-Tarjan Dominators:\n");
+        dataLog(dominators);
+        dataLog("\n");
+        dataLog("Naive Dominators:\n");
+        naiveDominators.dump(graph, WTF::dataFile());
+        dataLog("\n");
+        dataLog("Graph at time of failure:\n");
+        graph.dump();
+        dataLog("\n");
+        dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
+        CRASH();
+    }
+    
+    Graph& graph;
+    Dominators& dominators;
+    NaiveDominators naiveDominators;
+    
+    struct Error {
+        BasicBlock* from;
+        BasicBlock* to;
+        const char* message;
+    };
+    
+    Vector<Error> errors;
+};
 
-        // Prune dominators in all non entry blocks: backward scan.
-        changed = false;
-        for (unsigned i = numBlocks; i-- > 1;)
-            changed |= pruneDominators(graph, i);
-    } while (changed);
-}
+} // anonymous namespace
 
-bool Dominators::pruneDominators(Graph& graph, BlockIndex idx)
+void Dominators::compute(Graph& graph)
 {
-    BasicBlock* block = graph.block(idx);
-
-    if (!block || block->predecessors.isEmpty())
-        return false;
-
-    // Find the intersection of dom(preds).
-    m_scratch.set(m_results[block->predecessors[0]->index]);
-    for (unsigned j = block->predecessors.size(); j-- > 1;)
-        m_scratch.filter(m_results[block->predecessors[j]->index]);
-
-    // The block is also dominated by itself.
-    m_scratch.set(idx);
+    LengauerTarjan lengauerTarjan(graph);
+    lengauerTarjan.compute();
 
-    return m_results[idx].setAndCheck(m_scratch);
-}
-
-void Dominators::dump(Graph& graph, PrintStream& out) const
-{
-    for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
+    m_data = BlockMap<BlockData>(graph);
+    
+    // From here we want to build a spanning tree with both upward and downward links and we want
+    // to do a search over this tree to compute pre and post numbers that can be used for dominance
+    // tests.
+    
+    for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
         BasicBlock* block = graph.block(blockIndex);
         if (!block)
             continue;
-        out.print("    Block ", *block, ":");
-        for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
-            if (!dominates(block->index, otherIndex))
+        
+        BasicBlock* idomBlock = lengauerTarjan.immediateDominator(block);
+        m_data[block].idomParent = idomBlock;
+        if (idomBlock)
+            m_data[idomBlock].idomKids.append(block);
+    }
+    
+    unsigned nextPreNumber = 0;
+    unsigned nextPostNumber = 0;
+    
+    // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
+    Vector<BlockWithOrder> worklist;
+    worklist.append(BlockWithOrder(graph.block(0), PreOrder));
+    while (!worklist.isEmpty()) {
+        BlockWithOrder item = worklist.takeLast();
+        switch (item.order) {
+        case PreOrder:
+            m_data[item.block].preNumber = nextPreNumber++;
+            worklist.append(BlockWithOrder(item.block, PostOrder));
+            for (BasicBlock* kid : m_data[item.block].idomKids)
+                worklist.append(BlockWithOrder(kid, PreOrder));
+            break;
+        case PostOrder:
+            m_data[item.block].postNumber = nextPostNumber++;
+            break;
+        }
+    }
+    
+    if (validationEnabled()) {
+        // Check our dominator calculation:
+        // 1) Check that our range-based ancestry test is the same as a naive ancestry test.
+        // 2) Check that our notion of who dominates whom is identical to a naive (not
+        //    Lengauer-Tarjan) dominator calculation.
+        
+        ValidationContext context(graph, *this);
+        context.naiveDominators.compute(graph);
+        
+        for (BlockIndex fromBlockIndex = graph.numBlocks(); fromBlockIndex--;) {
+            BasicBlock* fromBlock = graph.block(fromBlockIndex);
+            if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
                 continue;
-            out.print(" #", otherIndex);
+            for (BlockIndex toBlockIndex = graph.numBlocks(); toBlockIndex--;) {
+                BasicBlock* toBlock = graph.block(toBlockIndex);
+                if (!toBlock || m_data[toBlock].preNumber == UINT_MAX)
+                    continue;
+                
+                if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock))
+                    context.reportError(fromBlock, toBlock, "Range-based domination check is broken");
+                if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock))
+                    context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken");
+            }
         }
-        out.print("\n");
+        
+        context.handleErrors();
+    }
+}
+
+bool Dominators::naiveDominates(BasicBlock* from, BasicBlock* to) const
+{
+    for (BasicBlock* block = to; block; block = m_data[block].idomParent) {
+        if (block == from)
+            return true;
+    }
+    return false;
+}
+
+void Dominators::dump(PrintStream& out) const
+{
+    if (!isValid()) {
+        out.print("    Not Valid.\n");
+        return;
+    }
+    
+    for (BlockIndex blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
+        if (m_data[blockIndex].preNumber == UINT_MAX)
+            continue;
+        
+        out.print("    Block #", blockIndex, ": idom = ", pointerDump(m_data[blockIndex].idomParent), ", idomKids = [");
+        CommaPrinter comma;
+        for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
+            out.print(comma, *m_data[blockIndex].idomKids[i]);
+        out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
     }
 }
 
index e9dc5c7..bd86b63 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -30,6 +30,7 @@
 
 #include "DFGAnalysis.h"
 #include "DFGBasicBlock.h"
+#include "DFGBlockMap.h"
 #include "DFGCommon.h"
 #include <wtf/FastBitVector.h>
 
@@ -44,24 +45,39 @@ public:
     
     void compute(Graph&);
     
-    bool dominates(BlockIndex from, BlockIndex to) const
+    bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
     {
         ASSERT(isValid());
-        return m_results[to].get(from);
+        return m_data[to].preNumber > m_data[from].preNumber
+            && m_data[to].postNumber < m_data[from].postNumber;
     }
     
     bool dominates(BasicBlock* from, BasicBlock* to) const
     {
-        return dominates(from->index, to->index);
+        return from == to || strictlyDominates(from, to);
     }
     
-    void dump(Graph&, PrintStream&) const;
+    void dump(PrintStream&) const;
     
 private:
-    bool pruneDominators(Graph&, BlockIndex);
+    bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
     
-    Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
-    FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+    struct BlockData {
+        BlockData()
+            : idomParent(nullptr)
+            , preNumber(UINT_MAX)
+            , postNumber(UINT_MAX)
+        {
+        }
+        
+        Vector<BasicBlock*> idomKids;
+        BasicBlock* idomParent;
+        
+        unsigned preNumber;
+        unsigned postNumber;
+    };
+    
+    BlockMap<BlockData> m_data;
 };
 
 } } // namespace JSC::DFG
index d9a5f4b..af8d18f 100644 (file)
@@ -31,6 +31,7 @@
 #include "BytecodeLivenessAnalysisInlines.h"
 #include "CodeBlock.h"
 #include "CodeBlockWithJITType.h"
+#include "DFGBlockWorklist.h"
 #include "DFGClobberSet.h"
 #include "DFGJITCode.h"
 #include "DFGVariableAccessDataDump.h"
@@ -370,14 +371,18 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
     if (m_dominators.isValid()) {
         out.print(prefix, "  Dominated by:");
         for (size_t i = 0; i < m_blocks.size(); ++i) {
-            if (!m_dominators.dominates(i, block->index))
+            if (!this->block(i))
+                continue;
+            if (!m_dominators.dominates(this->block(i), block))
                 continue;
             out.print(" #", i);
         }
         out.print("\n");
         out.print(prefix, "  Dominates:");
         for (size_t i = 0; i < m_blocks.size(); ++i) {
-            if (!m_dominators.dominates(block->index, i))
+            if (!this->block(i))
+                continue;
+            if (!m_dominators.dominates(block, this->block(i)))
                 continue;
             out.print(" #", i);
         }
@@ -635,73 +640,30 @@ void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, Va
     }
 }
 
-// Utilities for pre- and post-order traversals.
-namespace {
-
-inline void addForPreOrder(Vector<BasicBlock*>& result, Vector<BasicBlock*, 16>& worklist, BitVector& seen, BasicBlock* block)
-{
-    if (seen.get(block->index))
-        return;
-    
-    result.append(block);
-    worklist.append(block);
-    seen.set(block->index);
-}
-
-enum PostOrderTaskKind {
-    PostOrderFirstVisit,
-    PostOrderAddToResult
-};
-
-struct PostOrderTask {
-    PostOrderTask(BasicBlock* block = nullptr, PostOrderTaskKind kind = PostOrderFirstVisit)
-        : m_block(block)
-        , m_kind(kind)
-    {
-    }
-    
-    BasicBlock* m_block;
-    PostOrderTaskKind m_kind;
-};
-
-inline void addForPostOrder(Vector<PostOrderTask, 16>& worklist, BitVector& seen, BasicBlock* block)
-{
-    if (seen.get(block->index))
-        return;
-    
-    worklist.append(PostOrderTask(block, PostOrderFirstVisit));
-    seen.set(block->index);
-}
-
-} // anonymous namespace
-
 void Graph::getBlocksInPreOrder(Vector<BasicBlock*>& result)
 {
-    Vector<BasicBlock*, 16> worklist;
-    BitVector seen;
-    addForPreOrder(result, worklist, seen, block(0));
-    while (!worklist.isEmpty()) {
-        BasicBlock* block = worklist.takeLast();
+    BlockWorklist worklist;
+    worklist.push(block(0));
+    while (BasicBlock* block = worklist.pop()) {
+        result.append(block);
         for (unsigned i = block->numSuccessors(); i--;)
-            addForPreOrder(result, worklist, seen, block->successor(i));
+            worklist.push(block->successor(i));
     }
 }
 
 void Graph::getBlocksInPostOrder(Vector<BasicBlock*>& result)
 {
-    Vector<PostOrderTask, 16> worklist;
-    BitVector seen;
-    addForPostOrder(worklist, seen, block(0));
-    while (!worklist.isEmpty()) {
-        PostOrderTask task = worklist.takeLast();
-        switch (task.m_kind) {
-        case PostOrderFirstVisit:
-            worklist.append(PostOrderTask(task.m_block, PostOrderAddToResult));
-            for (unsigned i = task.m_block->numSuccessors(); i--;)
-                addForPostOrder(worklist, seen, task.m_block->successor(i));
+    PostOrderBlockWorklist worklist;
+    worklist.push(block(0));
+    while (BlockWithOrder item = worklist.pop()) {
+        switch (item.order) {
+        case PreOrder:
+            worklist.pushPost(item.block);
+            for (unsigned i = item.block->numSuccessors(); i--;)
+                worklist.push(item.block->successor(i));
             break;
-        case PostOrderAddToResult:
-            result.append(task.m_block);
+        case PostOrder:
+            result.append(item.block);
             break;
         }
     }
index 510ed5c..54c8937 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGBlockSet.h"
 #include "DFGClobberize.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
@@ -50,7 +51,7 @@ public:
     {
         ASSERT(m_graph.m_form != SSA);
         
-        BitVector blocksThatNeedInvalidationPoints;
+        BlockSet blocksThatNeedInvalidationPoints;
         
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
             BasicBlock* block = m_graph.block(blockIndex);
@@ -63,17 +64,18 @@ public:
             // Note: this assumes that control flow occurs at bytecode instruction boundaries.
             if (m_originThatHadFire.isSet()) {
                 for (unsigned i = block->numSuccessors(); i--;)
-                    blocksThatNeedInvalidationPoints.set(block->successor(i)->index);
+                    blocksThatNeedInvalidationPoints.add(block->successor(i));
             }
             
             m_insertionSet.execute(block);
         }
         
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
-            if (!blocksThatNeedInvalidationPoints.get(blockIndex))
+            BasicBlock* block = m_graph.block(blockIndex);
+
+            if (!blocksThatNeedInvalidationPoints.contains(block))
                 continue;
             
-            BasicBlock* block = m_graph.block(blockIndex);
             insertInvalidationCheck(0, block->at(0));
             m_insertionSet.execute(block);
         }
diff --git a/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp b/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp
new file mode 100644 (file)
index 0000000..eb8c63a
--- /dev/null
@@ -0,0 +1,135 @@
+/*
+ * Copyright (C) 2011, 2014 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 "DFGNaiveDominators.h"
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGGraph.h"
+#include "JSCInlines.h"
+
+namespace JSC { namespace DFG {
+
+NaiveDominators::NaiveDominators()
+{
+}
+
+NaiveDominators::~NaiveDominators()
+{
+}
+
+void NaiveDominators::compute(Graph& graph)
+{
+    // This implements a naive dominator solver.
+    
+    ASSERT(graph.block(0)->predecessors.isEmpty());
+    
+    unsigned numBlocks = graph.numBlocks();
+    
+    // Allocate storage for the dense dominance matrix. 
+    if (numBlocks > m_results.size()) {
+        m_results.grow(numBlocks);
+        for (unsigned i = numBlocks; i--;)
+            m_results[i].resize(numBlocks);
+        m_scratch.resize(numBlocks);
+    }
+
+    // We know that the entry block is only dominated by itself.
+    m_results[0].clearAll();
+    m_results[0].set(0);
+
+    // Find all of the valid blocks.
+    m_scratch.clearAll();
+    for (unsigned i = numBlocks; i--;) {
+        if (!graph.block(i))
+            continue;
+        m_scratch.set(i);
+    }
+    
+    // Mark all nodes as dominated by everything.
+    for (unsigned i = numBlocks; i-- > 1;) {
+        if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
+            m_results[i].clearAll();
+        else
+            m_results[i].set(m_scratch);
+    }
+
+    // Iteratively eliminate nodes that are not dominator.
+    bool changed;
+    do {
+        changed = false;
+        // Prune dominators in all non entry blocks: forward scan.
+        for (unsigned i = 1; i < numBlocks; ++i)
+            changed |= pruneDominators(graph, i);
+
+        if (!changed)
+            break;
+
+        // Prune dominators in all non entry blocks: backward scan.
+        changed = false;
+        for (unsigned i = numBlocks; i-- > 1;)
+            changed |= pruneDominators(graph, i);
+    } while (changed);
+}
+
+bool NaiveDominators::pruneDominators(Graph& graph, BlockIndex idx)
+{
+    BasicBlock* block = graph.block(idx);
+
+    if (!block || block->predecessors.isEmpty())
+        return false;
+
+    // Find the intersection of dom(preds).
+    m_scratch.set(m_results[block->predecessors[0]->index]);
+    for (unsigned j = block->predecessors.size(); j-- > 1;)
+        m_scratch.filter(m_results[block->predecessors[j]->index]);
+
+    // The block is also dominated by itself.
+    m_scratch.set(idx);
+
+    return m_results[idx].setAndCheck(m_scratch);
+}
+
+void NaiveDominators::dump(Graph& graph, PrintStream& out) const
+{
+    for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
+        BasicBlock* block = graph.block(blockIndex);
+        if (!block)
+            continue;
+        out.print("    Block ", *block, ":");
+        for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
+            if (!dominates(block->index, otherIndex))
+                continue;
+            out.print(" #", otherIndex);
+        }
+        out.print("\n");
+    }
+}
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
diff --git a/Source/JavaScriptCore/dfg/DFGNaiveDominators.h b/Source/JavaScriptCore/dfg/DFGNaiveDominators.h
new file mode 100644 (file)
index 0000000..d88dd3a
--- /dev/null
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2011, 2014 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 DFGNaiveDominators_h
+#define DFGNaiveDominators_h
+
+#if ENABLE(DFG_JIT)
+
+#include "DFGBasicBlock.h"
+#include "DFGCommon.h"
+#include <wtf/FastBitVector.h>
+
+namespace JSC { namespace DFG {
+
+class Graph;
+
+// This class is only used for validating the real dominators implementation.
+
+class NaiveDominators {
+public:
+    NaiveDominators();
+    ~NaiveDominators();
+    
+    void compute(Graph&);
+    
+    bool dominates(BlockIndex from, BlockIndex to) const
+    {
+        return m_results[to].get(from);
+    }
+    
+    bool dominates(BasicBlock* from, BasicBlock* to) const
+    {
+        return dominates(from->index, to->index);
+    }
+    
+    void dump(Graph&, PrintStream&) const;
+    
+private:
+    bool pruneDominators(Graph&, BlockIndex);
+    
+    Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
+    FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
+};
+
+} } // namespace JSC::DFG
+
+#endif // ENABLE(DFG_JIT)
+
+#endif // DFGNaiveDominators_h
index b43ba95..edb78cf 100644 (file)
@@ -45,6 +45,11 @@ void NaturalLoop::dump(PrintStream& out) const
 NaturalLoops::NaturalLoops() { }
 NaturalLoops::~NaturalLoops() { }
 
+void NaturalLoops::computeDependencies(Graph& graph)
+{
+    graph.m_dominators.computeIfNecessary(graph);
+}
+
 void NaturalLoops::compute(Graph& graph)
 {
     // Implement the classic dominator-based natural loop finder. The first
@@ -57,11 +62,9 @@ void NaturalLoops::compute(Graph& graph)
     
     static const bool verbose = false;
     
-    graph.m_dominators.computeIfNecessary(graph);
-    
     if (verbose) {
         dataLog("Dominators:\n");
-        graph.m_dominators.dump(graph, WTF::dataFile());
+        graph.m_dominators.dump(WTF::dataFile());
     }
     
     m_loops.resize(0);
index 1ac67ac..57225e3 100644 (file)
@@ -93,6 +93,7 @@ public:
     NaturalLoops();
     ~NaturalLoops();
     
+    void computeDependencies(Graph&);
     void compute(Graph&);
     
     unsigned numLoops() const
index c3ce822..eb79a07 100644 (file)
@@ -1,5 +1,22 @@
 2014-08-27  Filip Pizlo  <fpizlo@apple.com>
 
+        DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
+        https://bugs.webkit.org/show_bug.cgi?id=93361
+
+        Reviewed by Mark Hahnenberg.
+        
+        Make BitVector operations return the previous value of the bit you're changing. This is
+        useful for the kinds of set operations that are commonplace in compiler graph searches.
+
+        * wtf/BitVector.h:
+        (WTF::BitVector::quickSet):
+        (WTF::BitVector::quickClear):
+        (WTF::BitVector::set):
+        (WTF::BitVector::ensureSizeAndSet):
+        (WTF::BitVector::clear):
+
+2014-08-27  Filip Pizlo  <fpizlo@apple.com>
+
         FTL should be able to do polymorphic call inlining
         https://bugs.webkit.org/show_bug.cgi?id=135145
 
index 77d95f6..f4abc40 100644 (file)
@@ -117,24 +117,31 @@ public:
         return !!(bits()[bit / bitsInPointer()] & (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1))));
     }
     
-    void quickSet(size_t bit)
+    bool quickSet(size_t bit)
     {
         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
-        bits()[bit / bitsInPointer()] |= (static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
+        uintptr_t& word = bits()[bit / bitsInPointer()];
+        uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
+        bool result = !!(word & mask);
+        word |= mask;
+        return result;
     }
     
-    void quickClear(size_t bit)
+    bool quickClear(size_t bit)
     {
         ASSERT_WITH_SECURITY_IMPLICATION(bit < size());
-        bits()[bit / bitsInPointer()] &= ~(static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1)));
+        uintptr_t& word = bits()[bit / bitsInPointer()];
+        uintptr_t mask = static_cast<uintptr_t>(1) << (bit & (bitsInPointer() - 1));
+        bool result = !!(word & mask);
+        word &= ~mask;
+        return result;
     }
     
-    void quickSet(size_t bit, bool value)
+    bool quickSet(size_t bit, bool value)
     {
         if (value)
-            quickSet(bit);
-        else
-            quickClear(bit);
+            return quickSet(bit);
+        return quickClear(bit);
     }
     
     bool get(size_t bit) const
@@ -144,31 +151,30 @@ public:
         return quickGet(bit);
     }
     
-    void set(size_t bit)
+    bool set(size_t bit)
     {
         ensureSize(bit + 1);
-        quickSet(bit);
+        return quickSet(bit);
     }
 
-    void ensureSizeAndSet(size_t bit, size_t size)
+    bool ensureSizeAndSet(size_t bit, size_t size)
     {
         ensureSize(size);
-        quickSet(bit);
+        return quickSet(bit);
     }
 
-    void clear(size_t bit)
+    bool clear(size_t bit)
     {
         if (bit >= size())
-            return;
-        quickClear(bit);
+            return false;
+        return quickClear(bit);
     }
     
-    void set(size_t bit, bool value)
+    bool set(size_t bit, bool value)
     {
         if (value)
-            set(bit);
-        else
-            clear(bit);
+            return set(bit);
+        return clear(bit);
     }
     
     void merge(const BitVector& other)