Dominators should be factored out of the DFG
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Nov 2015 00:48:03 +0000 (00:48 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Nov 2015 00:48:03 +0000 (00:48 +0000)
https://bugs.webkit.org/show_bug.cgi?id=150764

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

Factored DFGDominators.h/DFGDominators.cpp into WTF. To do this, I made two changes to the
DFG:

1) DFG now has a CFG abstraction called DFG::CFG. The cool thing about this is that in the
   future if we wanted to support inverted dominators, we could do it by just creating a
   DFG::BackwardCFG.

2) Got rid of DFG::Analysis. From now on, an Analysis being invalidated is expressed by the
   DFG::Graph having a null pointer for that analysis. When we "run" the analysis, we
   just instantiate it. This makes it much more natural to integrate WTF::Dominators into
   the DFG.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGAnalysis.h: Removed.
* dfg/DFGCFG.h: Added.
(JSC::DFG::CFG::CFG):
(JSC::DFG::CFG::root):
(JSC::DFG::CFG::newMap<T>):
(JSC::DFG::CFG::successors):
(JSC::DFG::CFG::predecessors):
(JSC::DFG::CFG::index):
(JSC::DFG::CFG::node):
(JSC::DFG::CFG::numNodes):
(JSC::DFG::CFG::dump):
* dfg/DFGCSEPhase.cpp:
* dfg/DFGDisassembler.cpp:
(JSC::DFG::Disassembler::createDumpList):
* dfg/DFGDominators.cpp: Removed.
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::Dominators):
(JSC::DFG::Dominators::strictlyDominates): Deleted.
(JSC::DFG::Dominators::dominates): Deleted.
(JSC::DFG::Dominators::immediateDominatorOf): Deleted.
(JSC::DFG::Dominators::forAllStrictDominatorsOf): Deleted.
(JSC::DFG::Dominators::forAllDominatorsOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy): Deleted.
(JSC::DFG::Dominators::forAllBlocksDominatedBy): Deleted.
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf): Deleted.
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl): Deleted.
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl): Deleted.
(JSC::DFG::Dominators::BlockData::BlockData): Deleted.
* dfg/DFGEdgeDominates.h:
(JSC::DFG::EdgeDominates::operator()):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::Graph):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::invalidateCFG):
(JSC::DFG::Graph::substituteGetLocal):
(JSC::DFG::Graph::handleAssertionFailure):
(JSC::DFG::Graph::ensureDominators):
(JSC::DFG::Graph::ensurePrePostNumbering):
(JSC::DFG::Graph::ensureNaturalLoops):
(JSC::DFG::Graph::valueProfileFor):
* dfg/DFGGraph.h:
(JSC::DFG::Graph::hasDebuggerEnabled):
* dfg/DFGLICMPhase.cpp:
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
* dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
* dfg/DFGNaturalLoops.cpp:
(JSC::DFG::NaturalLoop::dump):
(JSC::DFG::NaturalLoops::NaturalLoops):
(JSC::DFG::NaturalLoops::~NaturalLoops):
(JSC::DFG::NaturalLoops::loopsOf):
(JSC::DFG::NaturalLoops::computeDependencies): Deleted.
(JSC::DFG::NaturalLoops::compute): Deleted.
* dfg/DFGNaturalLoops.h:
(JSC::DFG::NaturalLoops::numLoops):
* dfg/DFGNode.h:
(JSC::DFG::Node::SuccessorsIterable::end):
(JSC::DFG::Node::SuccessorsIterable::size):
(JSC::DFG::Node::SuccessorsIterable::at):
(JSC::DFG::Node::SuccessorsIterable::operator[]):
* dfg/DFGOSREntrypointCreationPhase.cpp:
(JSC::DFG::OSREntrypointCreationPhase::run):
* dfg/DFGObjectAllocationSinkingPhase.cpp:
* dfg/DFGPlan.cpp:
(JSC::DFG::Plan::compileInThreadImpl):
* dfg/DFGPrePostNumbering.cpp:
(JSC::DFG::PrePostNumbering::PrePostNumbering):
(JSC::DFG::PrePostNumbering::~PrePostNumbering):
(JSC::DFG::PrePostNumbering::compute): Deleted.
* dfg/DFGPrePostNumbering.h:
(JSC::DFG::PrePostNumbering::preNumber):
(JSC::DFG::PrePostNumbering::postNumber):
* dfg/DFGPutStackSinkingPhase.cpp:
* dfg/DFGSSACalculator.cpp:
(JSC::DFG::SSACalculator::nonLocalReachingDef):
(JSC::DFG::SSACalculator::reachingDefAtTail):
* dfg/DFGSSACalculator.h:
(JSC::DFG::SSACalculator::computePhis):
* dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
* ftl/FTLLink.cpp:
(JSC::FTL::link):
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):
(JSC::FTL::DFG::LowerDFGToLLVM::safelyInvalidateAfterTermination):
(JSC::FTL::DFG::LowerDFGToLLVM::isValid):

Source/WTF:

This takes what used to be DFGDominators.h/DFGDominators.cpp and turns it into a generic
algorithm that can take any abstract graph. The idea is that you create Dominators<CFG> and
pass it a CFG object, which defines the types of graph nodes and methods for getting
successors, predecessors, etc. The DFG now defines a class called CFG, which is a wrapper for
DFG::Graph that conforms to the thing that wtf/Dominators.h expects.

When doing things to graphs, it's common to refer to the things in the graph as "nodes".
Because I intend to reuse the CFG abstraction with many graph algorithms, that abstraction uses
the term "node" to refer to a DFG basic block. But in Dominators, the method and variable names
still use "block". This is because although Dominators are applicable to any kind of directed
graph, it's super unlikely that we will ever use them for anything but compilers. Indeed, the
only reason why I'm factoring them out of the DFG is so that I can use them with B3 and Air.

This has the nice side effect that a user of WTF::Dominators<JSC::DFG::CFG> will see familiar
terminology like "blocksStrictlyDominatedBy(...)" instead of "nodesStrictlyDominatedBy(...)",
which would be super confusing.

Overall, wtf/Dominators.h is a combination of what used to be in DFGDominators.h,
DFGDominators.cpp, DFGNaiveDominators.h, and DFGNaiveDominators.cpp. I only changed code when I
had to in order to make it generic.

* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Dominators.h: Added.
(WTF::Dominators::Dominators):
(WTF::Dominators::compute):
(WTF::Dominators::strictlyDominates):
(WTF::Dominators::dominates):
(WTF::Dominators::immediateDominatorOf):
(WTF::Dominators::forAllStrictDominatorsOf):
(WTF::Dominators::forAllDominatorsOf):
(WTF::Dominators::forAllBlocksStrictlyDominatedBy):
(WTF::Dominators::forAllBlocksDominatedBy):
(WTF::Dominators::strictDominatorsOf):
(WTF::Dominators::dominatorsOf):
(WTF::Dominators::blocksStrictlyDominatedBy):
(WTF::Dominators::blocksDominatedBy):
(WTF::Dominators::forAllBlocksInDominanceFrontierOf):
(WTF::Dominators::dominanceFrontierOf):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
(WTF::Dominators::iteratedDominanceFrontierOf):
(WTF::Dominators::dump):
(WTF::Dominators::LengauerTarjan::LengauerTarjan):
(WTF::Dominators::LengauerTarjan::compute):
(WTF::Dominators::LengauerTarjan::immediateDominator):
(WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
(WTF::Dominators::LengauerTarjan::computeSemiDominatorsAndImplicitImmediateDominators):
(WTF::Dominators::LengauerTarjan::computeExplicitImmediateDominators):
(WTF::Dominators::LengauerTarjan::link):
(WTF::Dominators::LengauerTarjan::eval):
(WTF::Dominators::LengauerTarjan::compress):
(WTF::Dominators::LengauerTarjan::BlockData::BlockData):
(WTF::Dominators::NaiveDominators::NaiveDominators):
(WTF::Dominators::NaiveDominators::dominates):
(WTF::Dominators::NaiveDominators::dump):
(WTF::Dominators::NaiveDominators::pruneDominators):
(WTF::Dominators::ValidationContext::ValidationContext):
(WTF::Dominators::ValidationContext::reportError):
(WTF::Dominators::ValidationContext::handleErrors):
(WTF::Dominators::naiveDominates):
(WTF::Dominators::forAllBlocksInDominanceFrontierOfImpl):
(WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
(WTF::Dominators::BlockData::BlockData):

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

36 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGAnalysis.h [deleted file]
Source/JavaScriptCore/dfg/DFGCFG.h [moved from Source/JavaScriptCore/dfg/DFGNaiveDominators.h with 58% similarity]
Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
Source/JavaScriptCore/dfg/DFGDisassembler.cpp
Source/JavaScriptCore/dfg/DFGDominators.cpp [deleted file]
Source/JavaScriptCore/dfg/DFGDominators.h
Source/JavaScriptCore/dfg/DFGEdgeDominates.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGGraph.h
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
Source/JavaScriptCore/dfg/DFGLoopPreHeaderCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp [deleted file]
Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp
Source/JavaScriptCore/dfg/DFGNaturalLoops.h
Source/JavaScriptCore/dfg/DFGNode.h
Source/JavaScriptCore/dfg/DFGOSREntrypointCreationPhase.cpp
Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGPlan.cpp
Source/JavaScriptCore/dfg/DFGPrePostNumbering.cpp
Source/JavaScriptCore/dfg/DFGPrePostNumbering.h
Source/JavaScriptCore/dfg/DFGPutStackSinkingPhase.cpp
Source/JavaScriptCore/dfg/DFGSSACalculator.cpp
Source/JavaScriptCore/dfg/DFGSSACalculator.h
Source/JavaScriptCore/dfg/DFGSSAConversionPhase.cpp
Source/JavaScriptCore/dfg/DFGStaticExecutionCountEstimationPhase.cpp
Source/JavaScriptCore/dfg/DFGTierUpCheckInjectionPhase.cpp
Source/JavaScriptCore/ftl/FTLLink.cpp
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Dominators.h [new file with mode: 0644]

index f8a07b8a46ddccb1e921b6ef14b3ed758ee9672c..df3733d18df43f586ddd4b43f84da320423e8141 100644 (file)
@@ -233,7 +233,6 @@ set(JavaScriptCore_SOURCES
     dfg/DFGDesiredWeakReferences.cpp
     dfg/DFGDisassembler.cpp
     dfg/DFGDoesGC.cpp
-    dfg/DFGDominators.cpp
     dfg/DFGDriver.cpp
     dfg/DFGEdge.cpp
     dfg/DFGEpoch.cpp
@@ -270,7 +269,6 @@ set(JavaScriptCore_SOURCES
     dfg/DFGMinifiedNode.cpp
     dfg/DFGMovHintRemovalPhase.cpp
     dfg/DFGMultiGetByOffsetData.cpp
-    dfg/DFGNaiveDominators.cpp
     dfg/DFGNaturalLoops.cpp
     dfg/DFGNode.cpp
     dfg/DFGNodeFlags.cpp
index feb20a7535dc06559a9a8908b8860db9a0e5a27f..676a47ae35f10d657e62e5b85ca43c7e9c010cf6 100644 (file)
@@ -1,3 +1,115 @@
+2015-11-01  Filip Pizlo  <fpizlo@apple.com>
+
+        Dominators should be factored out of the DFG
+        https://bugs.webkit.org/show_bug.cgi?id=150764
+
+        Reviewed by Geoffrey Garen.
+
+        Factored DFGDominators.h/DFGDominators.cpp into WTF. To do this, I made two changes to the
+        DFG:
+
+        1) DFG now has a CFG abstraction called DFG::CFG. The cool thing about this is that in the
+           future if we wanted to support inverted dominators, we could do it by just creating a
+           DFG::BackwardCFG.
+
+        2) Got rid of DFG::Analysis. From now on, an Analysis being invalidated is expressed by the
+           DFG::Graph having a null pointer for that analysis. When we "run" the analysis, we
+           just instantiate it. This makes it much more natural to integrate WTF::Dominators into
+           the DFG.
+
+        * CMakeLists.txt:
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * dfg/DFGAnalysis.h: Removed.
+        * dfg/DFGCFG.h: Added.
+        (JSC::DFG::CFG::CFG):
+        (JSC::DFG::CFG::root):
+        (JSC::DFG::CFG::newMap<T>):
+        (JSC::DFG::CFG::successors):
+        (JSC::DFG::CFG::predecessors):
+        (JSC::DFG::CFG::index):
+        (JSC::DFG::CFG::node):
+        (JSC::DFG::CFG::numNodes):
+        (JSC::DFG::CFG::dump):
+        * dfg/DFGCSEPhase.cpp:
+        * dfg/DFGDisassembler.cpp:
+        (JSC::DFG::Disassembler::createDumpList):
+        * dfg/DFGDominators.cpp: Removed.
+        * dfg/DFGDominators.h:
+        (JSC::DFG::Dominators::Dominators):
+        (JSC::DFG::Dominators::strictlyDominates): Deleted.
+        (JSC::DFG::Dominators::dominates): Deleted.
+        (JSC::DFG::Dominators::immediateDominatorOf): Deleted.
+        (JSC::DFG::Dominators::forAllStrictDominatorsOf): Deleted.
+        (JSC::DFG::Dominators::forAllDominatorsOf): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksDominatedBy): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl): Deleted.
+        (JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl): Deleted.
+        (JSC::DFG::Dominators::BlockData::BlockData): Deleted.
+        * dfg/DFGEdgeDominates.h:
+        (JSC::DFG::EdgeDominates::operator()):
+        * dfg/DFGGraph.cpp:
+        (JSC::DFG::Graph::Graph):
+        (JSC::DFG::Graph::dumpBlockHeader):
+        (JSC::DFG::Graph::invalidateCFG):
+        (JSC::DFG::Graph::substituteGetLocal):
+        (JSC::DFG::Graph::handleAssertionFailure):
+        (JSC::DFG::Graph::ensureDominators):
+        (JSC::DFG::Graph::ensurePrePostNumbering):
+        (JSC::DFG::Graph::ensureNaturalLoops):
+        (JSC::DFG::Graph::valueProfileFor):
+        * dfg/DFGGraph.h:
+        (JSC::DFG::Graph::hasDebuggerEnabled):
+        * dfg/DFGLICMPhase.cpp:
+        (JSC::DFG::LICMPhase::run):
+        (JSC::DFG::LICMPhase::attemptHoist):
+        * dfg/DFGLoopPreHeaderCreationPhase.cpp:
+        (JSC::DFG::createPreHeader):
+        (JSC::DFG::LoopPreHeaderCreationPhase::run):
+        * dfg/DFGNaturalLoops.cpp:
+        (JSC::DFG::NaturalLoop::dump):
+        (JSC::DFG::NaturalLoops::NaturalLoops):
+        (JSC::DFG::NaturalLoops::~NaturalLoops):
+        (JSC::DFG::NaturalLoops::loopsOf):
+        (JSC::DFG::NaturalLoops::computeDependencies): Deleted.
+        (JSC::DFG::NaturalLoops::compute): Deleted.
+        * dfg/DFGNaturalLoops.h:
+        (JSC::DFG::NaturalLoops::numLoops):
+        * dfg/DFGNode.h:
+        (JSC::DFG::Node::SuccessorsIterable::end):
+        (JSC::DFG::Node::SuccessorsIterable::size):
+        (JSC::DFG::Node::SuccessorsIterable::at):
+        (JSC::DFG::Node::SuccessorsIterable::operator[]):
+        * dfg/DFGOSREntrypointCreationPhase.cpp:
+        (JSC::DFG::OSREntrypointCreationPhase::run):
+        * dfg/DFGObjectAllocationSinkingPhase.cpp:
+        * dfg/DFGPlan.cpp:
+        (JSC::DFG::Plan::compileInThreadImpl):
+        * dfg/DFGPrePostNumbering.cpp:
+        (JSC::DFG::PrePostNumbering::PrePostNumbering):
+        (JSC::DFG::PrePostNumbering::~PrePostNumbering):
+        (JSC::DFG::PrePostNumbering::compute): Deleted.
+        * dfg/DFGPrePostNumbering.h:
+        (JSC::DFG::PrePostNumbering::preNumber):
+        (JSC::DFG::PrePostNumbering::postNumber):
+        * dfg/DFGPutStackSinkingPhase.cpp:
+        * dfg/DFGSSACalculator.cpp:
+        (JSC::DFG::SSACalculator::nonLocalReachingDef):
+        (JSC::DFG::SSACalculator::reachingDefAtTail):
+        * dfg/DFGSSACalculator.h:
+        (JSC::DFG::SSACalculator::computePhis):
+        * dfg/DFGSSAConversionPhase.cpp:
+        (JSC::DFG::SSAConversionPhase::run):
+        * ftl/FTLLink.cpp:
+        (JSC::FTL::link):
+        * ftl/FTLLowerDFGToLLVM.cpp:
+        (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+        (JSC::FTL::DFG::LowerDFGToLLVM::safelyInvalidateAfterTermination):
+        (JSC::FTL::DFG::LowerDFGToLLVM::isValid):
+
 2015-10-31  Filip Pizlo  <fpizlo@apple.com>
 
         B3::reduceStrength's DCE should be more agro and less wrong
index 40812b28c468f259de3727d921e0d56ce495927f..e8707a19e5334bb1ca647bede9e83f61b247e329 100644 (file)
                0FC3CCFD19ADA410006AC72A /* DFGBlockMapInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF619ADA410006AC72A /* DFGBlockMapInlines.h */; };
                0FC3CCFE19ADA410006AC72A /* DFGBlockSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF719ADA410006AC72A /* DFGBlockSet.h */; };
                0FC3CD0019ADA410006AC72A /* DFGBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCF919ADA410006AC72A /* DFGBlockWorklist.h */; };
-               0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */; };
-               0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */; };
                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 */; };
                0FD3E40C1B618B6600C80E1E /* ObjectPropertyConditionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4061B618B6600C80E1E /* ObjectPropertyConditionSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0FD3E40D1B618B6600C80E1E /* PropertyCondition.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */; };
                0FD3E40E1B618B6600C80E1E /* PropertyCondition.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD3E4081B618B6600C80E1E /* PropertyCondition.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */; };
                0FD81AD3154FB4F000983E72 /* DFGDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AD0154FB4EB00983E72 /* DFGDominators.h */; };
                0FD82E2114172CE300179C94 /* DFGCapabilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */; };
                0FD82E39141AB14D00179C94 /* CompactJITCodeMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD82E37141AB14200179C94 /* CompactJITCodeMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A730B6121250068F009D25B1 /* StrictEvalActivation.h in Headers */ = {isa = PBXBuildFile; fileRef = A730B6101250068F009D25B1 /* StrictEvalActivation.h */; };
                A730B6131250068F009D25B1 /* StrictEvalActivation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */; };
                A731B25A130093880040A7FA /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 51F0EB6105C86C6B00E6DF1B /* Foundation.framework */; };
-               A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */ = {isa = PBXBuildFile; fileRef = A73781091799EA2E00817533 /* DFGAnalysis.h */; };
                A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */; };
                A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = A737810B1799EA2E00817533 /* DFGNaturalLoops.h */; };
                A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386551118697B400540279 /* SpecializedThunkJIT.h */; };
                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>"; };
                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>"; };
                0FD3E4071B618B6600C80E1E /* PropertyCondition.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PropertyCondition.cpp; sourceTree = "<group>"; };
                0FD3E4081B618B6600C80E1E /* PropertyCondition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PropertyCondition.h; sourceTree = "<group>"; };
                0FD5652216AB780A00197653 /* DFGBasicBlockInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGBasicBlockInlines.h; path = dfg/DFGBasicBlockInlines.h; sourceTree = "<group>"; };
-               0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGDominators.cpp; path = dfg/DFGDominators.cpp; sourceTree = "<group>"; };
                0FD81AD0154FB4EB00983E72 /* DFGDominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGDominators.h; path = dfg/DFGDominators.h; sourceTree = "<group>"; };
                0FD82E1E14172C2F00179C94 /* DFGCapabilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCapabilities.cpp; path = dfg/DFGCapabilities.cpp; sourceTree = "<group>"; };
                0FD82E1F14172C2F00179C94 /* DFGCapabilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGCapabilities.h; path = dfg/DFGCapabilities.h; sourceTree = "<group>"; };
                A7299DA417D12858005F5FF9 /* SetConstructor.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SetConstructor.h; sourceTree = "<group>"; };
                A730B6101250068F009D25B1 /* StrictEvalActivation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StrictEvalActivation.h; sourceTree = "<group>"; };
                A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StrictEvalActivation.cpp; sourceTree = "<group>"; };
-               A73781091799EA2E00817533 /* DFGAnalysis.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAnalysis.h; path = dfg/DFGAnalysis.h; sourceTree = "<group>"; };
                A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaturalLoops.cpp; path = dfg/DFGNaturalLoops.cpp; sourceTree = "<group>"; };
                A737810B1799EA2E00817533 /* DFGNaturalLoops.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaturalLoops.h; path = dfg/DFGNaturalLoops.h; sourceTree = "<group>"; };
                A7386551118697B400540279 /* SpecializedThunkJIT.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpecializedThunkJIT.h; sourceTree = "<group>"; };
                                0F18D3CE1B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h */,
                                0F66E16814DF3F1300B7B2E4 /* DFGAdjacencyList.h */,
                                0FB4B51916B62772003F696B /* DFGAllocator.h */,
-                               A73781091799EA2E00817533 /* DFGAnalysis.h */,
                                0F1E3A431534CBAD000F9456 /* DFGArgumentPosition.h */,
                                0F2DD80C1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.cpp */,
                                0F2DD80D1AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h */,
                                0FF427621591A1C9004CB9FF /* DFGDisassembler.h */,
                                0F5A1271192D9FDF008764A3 /* DFGDoesGC.cpp */,
                                0F5A1272192D9FDF008764A3 /* DFGDoesGC.h */,
-                               0FD81ACF154FB4EB00983E72 /* DFGDominators.cpp */,
                                0FD81AD0154FB4EB00983E72 /* DFGDominators.h */,
                                0F1E3A441534CBAD000F9456 /* DFGDoubleFormatState.h */,
                                0FD3C82014115CF800FD81CB /* DFGDriver.cpp */,
                                0F8F14321ADF090100ED792C /* DFGMovHintRemovalPhase.h */,
                                0FF2CD591B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp */,
                                0FF2CD5A1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h */,
-                               0FC3CCFA19ADA410006AC72A /* DFGNaiveDominators.cpp */,
-                               0FC3CCFB19ADA410006AC72A /* DFGNaiveDominators.h */,
                                A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
                                A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
                                0FB4B51E16B62772003F696B /* DFGNode.cpp */,
                                0F18D3D01B55A6E0002C5C9F /* DFGAdaptiveStructureWatchpoint.h in Headers */,
                                0F66E16B14DF3F1600B7B2E4 /* DFGAdjacencyList.h in Headers */,
                                0FFB921816D02EB20055A5DB /* DFGAllocator.h in Headers */,
-                               A737810C1799EA2E00817533 /* DFGAnalysis.h in Headers */,
                                0F1E3A461534CBAF000F9456 /* DFGArgumentPosition.h in Headers */,
                                0F2DD8121AB3D8BE00BBB8E8 /* DFGArgumentsEliminationPhase.h in Headers */,
                                0F2DD8141AB3D8BE00BBB8E8 /* DFGArgumentsUtilities.h in Headers */,
                                0FEC85141BDACDAC0080FF74 /* B3ControlValue.h in Headers */,
                                0F8F14361ADF090100ED792C /* DFGMovHintRemovalPhase.h in Headers */,
                                0FF2CD5C1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h in Headers */,
-                               0FC3CD0219ADA411006AC72A /* DFGNaiveDominators.h in Headers */,
                                A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */,
                                86ECA3EA132DEF1C002B2AD7 /* DFGNode.h in Headers */,
                                0FFB921B16D02F010055A5DB /* DFGNodeAllocator.h in Headers */,
                                C2981FD817BAEE4B00A3BC98 /* DFGDesiredWeakReferences.cpp in Sources */,
                                0FF427641591A1CC004CB9FF /* DFGDisassembler.cpp in Sources */,
                                0F5A1273192D9FDF008764A3 /* DFGDoesGC.cpp in Sources */,
-                               0FD81AD2154FB4EE00983E72 /* DFGDominators.cpp in Sources */,
                                0FD3C82614115D4000FD81CB /* DFGDriver.cpp in Sources */,
                                0FF0F19E16B72A0B005DF95B /* DFGEdge.cpp in Sources */,
                                0F8F14331ADF090100ED792C /* DFGEpoch.cpp in Sources */,
                                0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
                                0F8F14351ADF090100ED792C /* DFGMovHintRemovalPhase.cpp in Sources */,
                                0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */,
-                               0FC3CD0119ADA411006AC72A /* DFGNaiveDominators.cpp in Sources */,
                                A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
                                0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
                                0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
diff --git a/Source/JavaScriptCore/dfg/DFGAnalysis.h b/Source/JavaScriptCore/dfg/DFGAnalysis.h
deleted file mode 100644 (file)
index 0df93d1..0000000
+++ /dev/null
@@ -1,81 +0,0 @@
-/*
- * Copyright (C) 2013, 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 DFGAnalysis_h
-#define DFGAnalysis_h
-
-#if ENABLE(DFG_JIT)
-
-namespace JSC { namespace DFG {
-
-class Graph;
-
-// Use this as a mixin for DFG analyses. The analysis itself implements a public
-// compute(Graph&) method. Clients call computeIfNecessary() when they want
-// results.
-
-template<typename T>
-class Analysis {
-public:
-    Analysis()
-        : m_valid(false)
-    {
-    }
-    
-    void invalidate()
-    {
-        m_valid = false;
-    }
-    
-    void computeIfNecessary(Graph& graph)
-    {
-        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;
-        static_cast<T*>(this)->compute(graph);
-    }
-    
-    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;
-};
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
-#endif // DFGAnalysis_h
-
similarity index 58%
rename from Source/JavaScriptCore/dfg/DFGNaiveDominators.h
rename to Source/JavaScriptCore/dfg/DFGCFG.h
index d88dd3acc03a58b4d2e0306b7e07378b69895ee1..83706c45a04ee4a93c6758e438eb59e6b18306b2 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef DFGNaiveDominators_h
-#define DFGNaiveDominators_h
+#ifndef DFGCFG_h
+#define DFGCFG_h
 
 #if ENABLE(DFG_JIT)
 
 #include "DFGBasicBlock.h"
-#include "DFGCommon.h"
-#include <wtf/FastBitVector.h>
+#include "DFGBlockMapInlines.h"
+#include "DFGBlockSet.h"
+#include "DFGGraph.h"
 
 namespace JSC { namespace DFG {
 
-class Graph;
-
-// This class is only used for validating the real dominators implementation.
-
-class NaiveDominators {
+class CFG {
 public:
-    NaiveDominators();
-    ~NaiveDominators();
-    
-    void compute(Graph&);
-    
-    bool dominates(BlockIndex from, BlockIndex to) const
+    typedef BasicBlock* Node;
+    typedef BlockSet Set;
+    template<typename T> using Map = BlockMap<T>;
+    typedef BlockList List;
+
+    CFG(Graph& graph)
+        : m_graph(graph)
     {
-        return m_results[to].get(from);
     }
-    
-    bool dominates(BasicBlock* from, BasicBlock* to) const
+
+    Node root() { return m_graph.block(0); }
+
+    template<typename T>
+    Map<T> newMap() { return BlockMap<T>(m_graph); }
+
+    DFG::Node::SuccessorsIterable successors(Node node) { return node->successors(); }
+    PredecessorList& predecessors(Node node) { return node->predecessors; }
+
+    unsigned index(Node node) const { return node->index; }
+    Node node(unsigned index) const { return m_graph.block(index); }
+    unsigned numNodes() const { return m_graph.numBlocks(); }
+
+    PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
+
+    void dump(PrintStream& out) const
     {
-        return dominates(from->index, to->index);
+        m_graph.dump(out);
     }
-    
-    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.
+    Graph& m_graph;
 };
 
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
 
-#endif // DFGNaiveDominators_h
+#endif // DFGCFG_h
+
index a3b8676166d1da3fe188bfd73828dc82c5ab2e5f..1cdee4df8f27bebd87bb6f8c5dc30dce0927090c 100644 (file)
@@ -32,6 +32,7 @@
 #include "DFGBlockMapInlines.h"
 #include "DFGClobberSet.h"
 #include "DFGClobberize.h"
+#include "DFGDominators.h"
 #include "DFGEdgeUsesStructure.h"
 #include "DFGGraph.h"
 #include "DFGPhase.h"
@@ -390,7 +391,7 @@ public:
         ASSERT(m_graph.m_form == SSA);
         
         m_graph.initializeNodeOwners();
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         
         m_preOrder = m_graph.blocksInPreOrder();
         
@@ -484,7 +485,7 @@ public:
         
         for (unsigned i = result.iterator->value.size(); i--;) {
             Node* candidate = result.iterator->value[i];
-            if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+            if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
                 m_node->replaceWith(candidate);
                 m_changed = true;
                 return;
@@ -573,7 +574,7 @@ public:
             // 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.strictlyDominates(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);
@@ -652,7 +653,7 @@ public:
                 if (!result.isNewEntry) {
                     for (unsigned i = result.iterator->value.size(); i--;) {
                         Node* candidate = result.iterator->value[i];
-                        if (m_graph.m_dominators.dominates(candidate->owner, m_block)) {
+                        if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
                             ASSERT(candidate);
                             match->replaceWith(candidate);
                             match.setNode(candidate);
index e221c4c4fe682a961c1006f06eb7d86efb31f4d8..15cbea0a5243d1bc78cb5e4f7cfe34d70fac3f68 100644 (file)
@@ -94,8 +94,8 @@ Vector<Disassembler::DumpedOp> Disassembler::createDumpList(LinkBuffer& linkBuff
     dumpHeader(out, linkBuffer);
     append(result, out, previousOrigin);
     
-    m_graph.m_dominators.computeIfNecessary(m_graph);
-    m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+    m_graph.ensureDominators();
+    m_graph.ensureNaturalLoops();
     
     const char* prefix = "    ";
     const char* disassemblyPrefix = "        ";
diff --git a/Source/JavaScriptCore/dfg/DFGDominators.cpp b/Source/JavaScriptCore/dfg/DFGDominators.cpp
deleted file mode 100644 (file)
index 79e4a55..0000000
+++ /dev/null
@@ -1,476 +0,0 @@
-/*
- * Copyright (C) 2011, 2014, 2015 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 "DFGDominators.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGBlockMapInlines.h"
-#include "DFGBlockWorklist.h"
-#include "DFGGraph.h"
-#include "DFGNaiveDominators.h"
-#include "JSCInlines.h"
-
-namespace JSC { namespace DFG {
-
-Dominators::Dominators()
-{
-}
-
-Dominators::~Dominators()
-{
-}
-
-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;
-        }
-    }
-    
-    void compute()
-    {
-        computeDepthFirstPreNumbering(); // Step 1.
-        computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
-        computeExplicitImmediateDominators(); // Step 4.
-    }
-    
-    BasicBlock* immediateDominator(BasicBlock* block)
-    {
-        return m_data[block].dom;
-    }
-
-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.node;
-            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());
-
-            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();
-        }
-    }
-    
-    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;
-        }
-    }
-
-    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;
-};
-
-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;
-};
-
-} // anonymous namespace
-
-void Dominators::compute(Graph& graph)
-{
-    LengauerTarjan lengauerTarjan(graph);
-    lengauerTarjan.compute();
-
-    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;
-        
-        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), VisitOrder::Pre));
-    while (!worklist.isEmpty()) {
-        BlockWithOrder item = worklist.takeLast();
-        switch (item.order) {
-        case VisitOrder::Pre:
-            m_data[item.node].preNumber = nextPreNumber++;
-            worklist.append(BlockWithOrder(item.node, VisitOrder::Post));
-            for (BasicBlock* kid : m_data[item.node].idomKids)
-                worklist.append(BlockWithOrder(kid, VisitOrder::Pre));
-            break;
-        case VisitOrder::Post:
-            m_data[item.node].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;
-            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");
-            }
-        }
-        
-        context.handleErrors();
-    }
-}
-
-BlockSet Dominators::strictDominatorsOf(BasicBlock* to) const
-{
-    BlockSet result;
-    forAllStrictDominatorsOf(to, BlockAdder(result));
-    return result;
-}
-
-BlockSet Dominators::dominatorsOf(BasicBlock* to) const
-{
-    BlockSet result;
-    forAllDominatorsOf(to, BlockAdder(result));
-    return result;
-}
-
-BlockSet Dominators::blocksStrictlyDominatedBy(BasicBlock* from) const
-{
-    BlockSet result;
-    forAllBlocksStrictlyDominatedBy(from, BlockAdder(result));
-    return result;
-}
-
-BlockSet Dominators::blocksDominatedBy(BasicBlock* from) const
-{
-    BlockSet result;
-    forAllBlocksDominatedBy(from, BlockAdder(result));
-    return result;
-}
-
-BlockSet Dominators::dominanceFrontierOf(BasicBlock* from) const
-{
-    BlockSet result;
-    forAllBlocksInDominanceFrontierOfImpl(from, BlockAdder(result));
-    return result;
-}
-
-BlockSet Dominators::iteratedDominanceFrontierOf(const BlockList& from) const
-{
-    BlockSet result;
-    forAllBlocksInIteratedDominanceFrontierOfImpl(from, BlockAdder(result));
-    return result;
-}
-
-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");
-    }
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
index e218ba792f261c1ad3f3055c7b0486eb1a9caa60..dd842cdb181e69bd08bcf93558d61dbe30ab587d 100644 (file)
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAnalysis.h"
 #include "DFGBasicBlock.h"
 #include "DFGBlockMap.h"
 #include "DFGBlockSet.h"
+#include "DFGCFG.h"
 #include "DFGCommon.h"
+#include "DFGGraph.h"
+#include <wtf/Dominators.h>
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
 
 namespace JSC { namespace DFG {
 
-class Graph;
-
-class Dominators : public Analysis<Dominators> {
+class Dominators : public WTF::Dominators<CFG> {
+    WTF_MAKE_NONCOPYABLE(Dominators);
+    WTF_MAKE_FAST_ALLOCATED;
 public:
-    Dominators();
-    ~Dominators();
-    
-    void compute(Graph&);
-    
-    bool strictlyDominates(BasicBlock* from, BasicBlock* to) const
-    {
-        ASSERT(isValid());
-        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 from == to || strictlyDominates(from, to);
-    }
-    
-    BasicBlock* immediateDominatorOf(BasicBlock* block) const
-    {
-        return m_data[block].idomParent;
-    }
-    
-    template<typename Functor>
-    void forAllStrictDominatorsOf(BasicBlock* to, const Functor& functor) const
-    {
-        for (BasicBlock* block = m_data[to].idomParent; block; block = m_data[block].idomParent)
-            functor(block);
-    }
-    
-    template<typename Functor>
-    void forAllDominatorsOf(BasicBlock* to, const Functor& functor) const
-    {
-        for (BasicBlock* block = to; block; block = m_data[block].idomParent)
-            functor(block);
-    }
-    
-    template<typename Functor>
-    void forAllBlocksStrictlyDominatedBy(BasicBlock* from, const Functor& functor) const
-    {
-        Vector<BasicBlock*, 16> worklist;
-        worklist.appendVector(m_data[from].idomKids);
-        while (!worklist.isEmpty()) {
-            BasicBlock* block = worklist.takeLast();
-            functor(block);
-            worklist.appendVector(m_data[block].idomKids);
-        }
-    }
-    
-    template<typename Functor>
-    void forAllBlocksDominatedBy(BasicBlock* from, const Functor& functor) const
-    {
-        Vector<BasicBlock*, 16> worklist;
-        worklist.append(from);
-        while (!worklist.isEmpty()) {
-            BasicBlock* block = worklist.takeLast();
-            functor(block);
-            worklist.appendVector(m_data[block].idomKids);
-        }
-    }
-    
-    BlockSet strictDominatorsOf(BasicBlock* to) const;
-    BlockSet dominatorsOf(BasicBlock* to) const;
-    BlockSet blocksStrictlyDominatedBy(BasicBlock* from) const;
-    BlockSet blocksDominatedBy(BasicBlock* from) const;
-    
-    template<typename Functor>
-    void forAllBlocksInDominanceFrontierOf(
-        BasicBlock* from, const Functor& functor) const
-    {
-        BlockSet set;
-        forAllBlocksInDominanceFrontierOfImpl(
-            from,
-            [&] (BasicBlock* block) {
-                if (set.add(block))
-                    functor(block);
-            });
-    }
-    
-    BlockSet dominanceFrontierOf(BasicBlock* from) const;
-    
-    template<typename Functor>
-    void forAllBlocksInIteratedDominanceFrontierOf(
-        const BlockList& from, const Functor& functor)
-    {
-        forAllBlocksInPrunedIteratedDominanceFrontierOf(
-            from,
-            [&] (BasicBlock* block) -> bool {
-                functor(block);
-                return true;
-            });
-    }
-    
-    // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
-    // given functor to return false to indicate that we don't wish to consider the given block.
-    // Useful for computing pruned SSA form.
-    template<typename Functor>
-    void forAllBlocksInPrunedIteratedDominanceFrontierOf(
-        const BlockList& from, const Functor& functor)
-    {
-        BlockSet set;
-        forAllBlocksInIteratedDominanceFrontierOfImpl(
-            from,
-            [&] (BasicBlock* block) -> bool {
-                if (!set.add(block))
-                    return false;
-                return functor(block);
-            });
-    }
-    
-    BlockSet iteratedDominanceFrontierOf(const BlockList& from) const;
-    
-    void dump(PrintStream&) const;
-    
-private:
-    bool naiveDominates(BasicBlock* from, BasicBlock* to) const;
-    
-    template<typename Functor>
-    void forAllBlocksInDominanceFrontierOfImpl(
-        BasicBlock* from, const Functor& functor) const
-    {
-        // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
-        //     "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
-        //     'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
-        //     dominate 'to'."
-        //
-        // A useful corner case to remember: a block may be in its own dominance frontier if it has
-        // a loop edge to itself, since it dominates itself and so it dominates its own immediate
-        // predecessor, and a block never strictly dominates itself.
-        
-        forAllBlocksDominatedBy(
-            from,
-            [&] (BasicBlock* block) {
-                for (unsigned successorIndex = block->numSuccessors(); successorIndex--;) {
-                    BasicBlock* to = block->successor(successorIndex);
-                    if (!strictlyDominates(from, to))
-                        functor(to);
-                }
-            });
-    }
-    
-    template<typename Functor>
-    void forAllBlocksInIteratedDominanceFrontierOfImpl(
-        const BlockList& from, const Functor& functor) const
+    Dominators(Graph& graph)
+        : WTF::Dominators<CFG>(*graph.m_cfg, validationEnabled())
     {
-        BlockList worklist = from;
-        while (!worklist.isEmpty()) {
-            BasicBlock* block = worklist.takeLast();
-            forAllBlocksInDominanceFrontierOfImpl(
-                block,
-                [&] (BasicBlock* otherBlock) {
-                    if (functor(otherBlock))
-                        worklist.append(otherBlock);
-                });
-        }
     }
-    
-    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 d95c79df2d194324e9eaf8467b68498e24369839..3da18da9bb71a677c320acdd803729b86eda0fb0 100644 (file)
@@ -28,6 +28,7 @@
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGDominators.h"
 #include "DFGGraph.h"
 
 namespace JSC { namespace DFG {
@@ -45,7 +46,7 @@ public:
     
     void operator()(Node*, Edge edge)
     {
-        bool result = m_graph.m_dominators.dominates(edge.node()->owner, m_block);
+        bool result = m_graph.m_dominators->dominates(edge.node()->owner, m_block);
         if (verbose) {
             dataLog(
                 "Checking if ", edge, " in ", *edge.node()->owner,
index 1b503e0faedfe0ccf22d03e9781757ddd2f66f2b..6d7e35065a5679dc5ec92e087e65552092f97fc5 100644 (file)
 #include "DFGBlockWorklist.h"
 #include "DFGClobberSet.h"
 #include "DFGClobbersExitState.h"
+#include "DFGCFG.h"
+#include "DFGDominators.h"
 #include "DFGJITCode.h"
 #include "DFGMayExit.h"
+#include "DFGNaturalLoops.h"
+#include "DFGPrePostNumbering.h"
 #include "DFGVariableAccessDataDump.h"
 #include "FullBytecodeLiveness.h"
 #include "FunctionExecutableDump.h"
@@ -64,6 +68,7 @@ Graph::Graph(VM& vm, Plan& plan, LongLivedState& longLivedState)
     , m_codeBlock(m_plan.codeBlock)
     , m_profiledBlock(m_codeBlock->alternative())
     , m_allocator(longLivedState.m_allocator)
+    , m_cfg(std::make_unique<CFG>(*this))
     , m_nextMachineLocal(0)
     , m_fixpointState(BeforeFixpoint)
     , m_structureRegistrationState(HaveNotStartedRegistering)
@@ -401,22 +406,22 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
     if (block->terminal()) {
         for (BasicBlock* successor : block->successors()) {
             out.print(" ", *successor);
-            if (m_prePostNumbering.isValid())
-                out.print(" (", m_prePostNumbering.edgeKind(block, successor), ")");
+            if (m_prePostNumbering)
+                out.print(" (", m_prePostNumbering->edgeKind(block, successor), ")");
         }
     } else
         out.print(" <invalid>");
     out.print("\n");
-    if (m_dominators.isValid() && terminalsAreValid()) {
-        out.print(prefix, "  Dominated by: ", m_dominators.dominatorsOf(block), "\n");
-        out.print(prefix, "  Dominates: ", m_dominators.blocksDominatedBy(block), "\n");
-        out.print(prefix, "  Dominance Frontier: ", m_dominators.dominanceFrontierOf(block), "\n");
-        out.print(prefix, "  Iterated Dominance Frontier: ", m_dominators.iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
+    if (m_dominators && terminalsAreValid()) {
+        out.print(prefix, "  Dominated by: ", m_dominators->dominatorsOf(block), "\n");
+        out.print(prefix, "  Dominates: ", m_dominators->blocksDominatedBy(block), "\n");
+        out.print(prefix, "  Dominance Frontier: ", m_dominators->dominanceFrontierOf(block), "\n");
+        out.print(prefix, "  Iterated Dominance Frontier: ", m_dominators->iteratedDominanceFrontierOf(BlockList(1, block)), "\n");
     }
-    if (m_prePostNumbering.isValid())
-        out.print(prefix, "  Pre/Post Numbering: ", m_prePostNumbering.preNumber(block), "/", m_prePostNumbering.postNumber(block), "\n");
-    if (m_naturalLoops.isValid()) {
-        if (const NaturalLoop* loop = m_naturalLoops.headerOf(block)) {
+    if (m_prePostNumbering)
+        out.print(prefix, "  Pre/Post Numbering: ", m_prePostNumbering->preNumber(block), "/", m_prePostNumbering->postNumber(block), "\n");
+    if (m_naturalLoops) {
+        if (const NaturalLoop* loop = m_naturalLoops->headerOf(block)) {
             out.print(prefix, "  Loop header, contains:");
             Vector<BlockIndex> sortedBlockList;
             for (unsigned i = 0; i < loop->size(); ++i)
@@ -428,7 +433,7 @@ void Graph::dumpBlockHeader(PrintStream& out, const char* prefix, BasicBlock* bl
         }
         
         Vector<const NaturalLoop*> containingLoops =
-            m_naturalLoops.loopsOf(block);
+            m_naturalLoops->loopsOf(block);
         if (!containingLoops.isEmpty()) {
             out.print(prefix, "  Containing loop headers:");
             for (unsigned i = 0; i < containingLoops.size(); ++i)
@@ -746,9 +751,9 @@ void Graph::killUnreachableBlocks()
 
 void Graph::invalidateCFG()
 {
-    m_dominators.invalidate();
-    m_naturalLoops.invalidate();
-    m_prePostNumbering.invalidate();
+    m_dominators = nullptr;
+    m_naturalLoops = nullptr;
+    m_prePostNumbering = nullptr;
 }
 
 void Graph::substituteGetLocal(BasicBlock& block, unsigned startIndexInBlock, VariableAccessData* variableAccessData, Node* newGetLocal)
@@ -1410,6 +1415,25 @@ void Graph::handleAssertionFailure(
     crash(*this, toCString("While handling block ", pointerDump(block), "\n\n"), file, line, function, assertion);
 }
 
+void Graph::ensureDominators()
+{
+    if (!m_dominators)
+        m_dominators = std::make_unique<Dominators>(*this);
+}
+
+void Graph::ensurePrePostNumbering()
+{
+    if (!m_prePostNumbering)
+        m_prePostNumbering = std::make_unique<PrePostNumbering>(*this);
+}
+
+void Graph::ensureNaturalLoops()
+{
+    ensureDominators();
+    if (!m_naturalLoops)
+        m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+}
+
 ValueProfile* Graph::valueProfileFor(Node* node)
 {
     if (!node)
index 054ff07f87816ac7e07cb8466c681d4d32dd7c6c..4a798d258c44670347153c1e7ab2b85ca0649e74 100644 (file)
 #include "CodeBlock.h"
 #include "DFGArgumentPosition.h"
 #include "DFGBasicBlock.h"
-#include "DFGDominators.h"
 #include "DFGFrozenValue.h"
 #include "DFGLongLivedState.h"
-#include "DFGNaturalLoops.h"
 #include "DFGNode.h"
 #include "DFGNodeAllocator.h"
 #include "DFGPlan.h"
-#include "DFGPrePostNumbering.h"
 #include "DFGPropertyTypeKey.h"
 #include "DFGScannable.h"
 #include "FullBytecodeLiveness.h"
@@ -59,6 +56,11 @@ class ExecState;
 
 namespace DFG {
 
+class CFG;
+class Dominators;
+class NaturalLoops;
+class PrePostNumbering;
+
 #define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do {            \
         Node* _node = (node);                                           \
         if (_node->flags() & NodeHasVarArgs) {                          \
@@ -820,6 +822,10 @@ public:
 
     bool hasDebuggerEnabled() const { return m_hasDebuggerEnabled; }
 
+    void ensureDominators();
+    void ensurePrePostNumbering();
+    void ensureNaturalLoops();
+
     VM& m_vm;
     Plan& m_plan;
     CodeBlock* m_codeBlock;
@@ -885,9 +891,10 @@ public:
     HashMap<CodeBlock*, std::unique_ptr<BytecodeKills>> m_bytecodeKills;
     HashSet<std::pair<JSObject*, PropertyOffset>> m_safeToLoad;
     HashMap<PropertyTypeKey, InferredType::Descriptor> m_inferredTypes;
-    Dominators m_dominators;
-    PrePostNumbering m_prePostNumbering;
-    NaturalLoops m_naturalLoops;
+    std::unique_ptr<Dominators> m_dominators;
+    std::unique_ptr<PrePostNumbering> m_prePostNumbering;
+    std::unique_ptr<NaturalLoops> m_naturalLoops;
+    std::unique_ptr<CFG> m_cfg;
     unsigned m_localVars;
     unsigned m_nextMachineLocal;
     unsigned m_parameterSlots;
index 6abd697139588c448bcc6c9bb47066a81802706e..c59fde90071589bc0db4cf921fc350bce542f853 100644 (file)
@@ -29,6 +29,7 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGBlockMapInlines.h"
+#include "DFGBlockSet.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
 #include "DFGPhase.h"
index c45dca6c9f77fbcd93b08339481dde01c417946a..f38a44021c204b2d70521db1766aa978977b10a5 100644 (file)
@@ -36,6 +36,7 @@
 #include "DFGEdgeDominates.h"
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "DFGSafeToExecute.h"
 #include "JSCInlines.h"
@@ -71,15 +72,15 @@ public:
     {
         DFG_ASSERT(m_graph, nullptr, m_graph.m_form == SSA);
         
-        m_graph.m_dominators.computeIfNecessary(m_graph);
-        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
+        m_graph.ensureNaturalLoops();
 
         if (verbose) {
             dataLog("Graph before LICM:\n");
             m_graph.dump();
         }
         
-        m_data.resize(m_graph.m_naturalLoops.numLoops());
+        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.
@@ -94,7 +95,7 @@ public:
             if (!block->cfaHasVisited)
                 continue;
             
-            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
             if (!loop)
                 continue;
             LoopData& data = m_data[loop->index()];
@@ -114,14 +115,14 @@ public:
         // 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);
+        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);
+                const NaturalLoop* outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(loop);
                 outerLoop;
-                outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop))
+                outerLoop = m_graph.m_naturalLoops->innerMostOuterLoop(*outerLoop))
                 m_data[outerLoop->index()].writes.addAll(data.writes);
             
             BasicBlock* header = loop.header();
@@ -135,7 +136,7 @@ public:
             
             for (unsigned i = header->predecessors.size(); i--;) {
                 BasicBlock* predecessor = header->predecessors[i];
-                if (m_graph.m_dominators.dominates(header, predecessor))
+                if (m_graph.m_dominators->dominates(header, predecessor))
                     continue;
 
                 preHeader = predecessor;
@@ -189,7 +190,7 @@ public:
         Vector<const NaturalLoop*> loopStack;
         bool changed = false;
         for (BasicBlock* block : m_graph.blocksInPreOrder()) {
-            const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block);
+            const NaturalLoop* loop = m_graph.m_naturalLoops->innerMostLoopOf(block);
             if (!loop)
                 continue;
             
@@ -197,7 +198,7 @@ public:
             for (
                 const NaturalLoop* current = loop;
                 current;
-                current = m_graph.m_naturalLoops.innerMostOuterLoop(*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
@@ -333,7 +334,7 @@ private:
         // because most loops are small and most blocks belong to few loops.
         for (unsigned bodyIndex = loop->size(); bodyIndex--;) {
             BasicBlock* subBlock = loop->at(bodyIndex);
-            const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock);
+            const NaturalLoop* subLoop = m_graph.m_naturalLoops->headerOf(subBlock);
             if (!subLoop)
                 continue;
             BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader;
index 3871358e88afdc47be1f0b9fe7bc96824325304e..7224b83837c298ee4ee097b0541c682675d50f10 100644 (file)
@@ -30,7 +30,9 @@
 
 #include "DFGBasicBlockInlines.h"
 #include "DFGBlockInsertionSet.h"
+#include "DFGDominators.h"
 #include "DFGGraph.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "JSCInlines.h"
 #include <wtf/HashMap.h>
@@ -94,7 +96,7 @@ BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, Basic
     
     for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) {
         BasicBlock* predecessor = block->predecessors[predecessorIndex];
-        if (graph.m_dominators.dominates(block, predecessor))
+        if (graph.m_dominators->dominates(block, predecessor))
             continue;
         block->predecessors[predecessorIndex--] = block->predecessors.last();
         block->predecessors.removeLast();
@@ -121,16 +123,16 @@ public:
     
     bool run()
     {
-        m_graph.m_dominators.computeIfNecessary(m_graph);
-        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
+        m_graph.ensureNaturalLoops();
         
-        for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) {
-            const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex);
+        for (unsigned loopIndex = m_graph.m_naturalLoops->numLoops(); loopIndex--;) {
+            const NaturalLoop& loop = m_graph.m_naturalLoops->loop(loopIndex);
             BasicBlock* existingPreHeader = 0;
             bool needsNewPreHeader = false;
             for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) {
                 BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex];
-                if (m_graph.m_dominators.dominates(loop.header(), predecessor))
+                if (m_graph.m_dominators->dominates(loop.header(), predecessor))
                     continue;
                 if (!existingPreHeader) {
                     existingPreHeader = predecessor;
diff --git a/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp b/Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp
deleted file mode 100644 (file)
index eb8c63a..0000000
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
- * 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)
-
index edb78cf5e5d158b1a46dc8013fdfd10bdf7ac2e0..89ca68b9c8ba7eb2c5509a77060658afec4f16e8 100644 (file)
@@ -42,16 +42,10 @@ void NaturalLoop::dump(PrintStream& out) const
     out.print("]");
 }
 
-NaturalLoops::NaturalLoops() { }
-NaturalLoops::~NaturalLoops() { }
-
-void NaturalLoops::computeDependencies(Graph& graph)
+NaturalLoops::NaturalLoops(Graph& graph)
 {
-    graph.m_dominators.computeIfNecessary(graph);
-}
+    ASSERT(graph.m_dominators);
 
-void NaturalLoops::compute(Graph& graph)
-{
     // Implement the classic dominator-based natural loop finder. The first
     // step is to find all control flow edges A -> B where B dominates A.
     // Then B is a loop header and A is a backward branching block. We will
@@ -64,7 +58,7 @@ void NaturalLoops::compute(Graph& graph)
     
     if (verbose) {
         dataLog("Dominators:\n");
-        graph.m_dominators.dump(WTF::dataFile());
+        graph.m_dominators->dump(WTF::dataFile());
     }
     
     m_loops.resize(0);
@@ -76,7 +70,7 @@ void NaturalLoops::compute(Graph& graph)
         
         for (unsigned i = block->numSuccessors(); i--;) {
             BasicBlock* successor = block->successor(i);
-            if (!graph.m_dominators.dominates(successor, block))
+            if (!graph.m_dominators->dominates(successor, block))
                 continue;
             bool found = false;
             for (unsigned j = m_loops.size(); j--;) {
@@ -199,6 +193,8 @@ void NaturalLoops::compute(Graph& graph)
         dataLog("Results: ", *this, "\n");
 }
 
+NaturalLoops::~NaturalLoops() { }
+
 Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
 {
     Vector<const NaturalLoop*> result;
index 57225e36fd3a1d975b946ae0c610a36c01c26d48..8454d0cb5f4d94fbbf98ddbda413968ac88ace14 100644 (file)
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAnalysis.h"
 #include "DFGBasicBlock.h"
 #include "DFGCommon.h"
+#include "DFGDominators.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
 
 namespace JSC { namespace DFG {
 
@@ -88,22 +90,19 @@ private:
     unsigned m_index;
 };
 
-class NaturalLoops : public Analysis<NaturalLoops> {
+class NaturalLoops {
+    WTF_MAKE_NONCOPYABLE(NaturalLoops);
+    WTF_MAKE_FAST_ALLOCATED;
 public:
-    NaturalLoops();
+    NaturalLoops(Graph&);
     ~NaturalLoops();
     
-    void computeDependencies(Graph&);
-    void compute(Graph&);
-    
     unsigned numLoops() const
     {
-        ASSERT(isValid());
         return m_loops.size();
     }
     const NaturalLoop& loop(unsigned i) const
     {
-        ASSERT(isValid());
         return m_loops[i];
     }
     
@@ -111,7 +110,6 @@ public:
     // loop it belongs to.
     const NaturalLoop* headerOf(BasicBlock* block) const
     {
-        ASSERT(isValid());
         const NaturalLoop* loop = innerMostLoopOf(block);
         if (!loop)
             return 0;
@@ -126,7 +124,6 @@ public:
     
     const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
     {
-        ASSERT(isValid());
         unsigned index = block->innerMostLoopIndices[0];
         if (index == UINT_MAX)
             return 0;
@@ -135,7 +132,6 @@ public:
     
     const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
     {
-        ASSERT(isValid());
         if (loop.m_outerLoopIndex == UINT_MAX)
             return 0;
         return &m_loops[loop.m_outerLoopIndex];
@@ -143,7 +139,6 @@ public:
     
     bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
     {
-        ASSERT(isValid());
         // It's faster to do this test using the loop itself, if it's small.
         if (candidateLoop.size() < 4)
             return candidateLoop.contains(block);
index 94adbe6146ef87ed3d975fcd10ab0508b27ebb3a..eedeb88c2891ec7b616234e36ad06c2251d07f0f 100644 (file)
@@ -1279,6 +1279,10 @@ struct Node {
         {
             return iterator(m_terminal, m_terminal->numSuccessors());
         }
+
+        size_t size() const { return m_terminal->numSuccessors(); }
+        BasicBlock* at(size_t index) const { return m_terminal->successor(index); }
+        BasicBlock* operator[](size_t index) const { return at(index); }
         
     private:
         Node* m_terminal;
index 7bfad4ba9e8a5ff5bd998812b95b117a8fff27f3..e6c4235ec4ca6817cd37e699834786089f2b6efa 100644 (file)
@@ -54,7 +54,7 @@ public:
         RELEASE_ASSERT(bytecodeIndex != UINT_MAX);
         
         // Needed by createPreHeader().
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         
         CodeBlock* baseline = m_graph.m_profiledBlock;
         
index 58e6eb59e6d1327f3eeec3422f89bbff0e61c932..db8dd6fb4922ee39c33867213f5b3f9b7bfbfc28 100644 (file)
@@ -727,7 +727,7 @@ private:
     {
         m_graph.computeRefCounts();
         m_graph.initializeNodeOwners();
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         performLivenessAnalysis(m_graph);
         performOSRAvailabilityAnalysis(m_graph);
         m_combinedLiveness = CombinedLiveness(m_graph);
index c76be9abe8f4e73da8d8cab101c9eee2bd6b3dd1..d328d4bfe780efa4f02c3942fd2d73f3423099a8 100644 (file)
@@ -344,9 +344,9 @@ Plan::CompilationPath Plan::compileInThreadImpl(LongLivedState& longLivedState)
     // If we're doing validation, then run some analyses, to give them an opportunity
     // to self-validate. Now is as good a time as any to do this.
     if (validationEnabled()) {
-        dfg.m_dominators.computeIfNecessary(dfg);
-        dfg.m_naturalLoops.computeIfNecessary(dfg);
-        dfg.m_prePostNumbering.computeIfNecessary(dfg);
+        dfg.ensureDominators();
+        dfg.ensureNaturalLoops();
+        dfg.ensurePrePostNumbering();
     }
 
     switch (mode) {
index 06c0ac570d90a63758ed22ce62953deeb3b7dc59..4b7923190c49a8a235d5a8d649ebd49586e3732c 100644 (file)
 
 namespace JSC { namespace DFG {
 
-PrePostNumbering::PrePostNumbering() { }
-PrePostNumbering::~PrePostNumbering() { }
-
-void PrePostNumbering::compute(Graph& graph)
+PrePostNumbering::PrePostNumbering(Graph& graph)
 {
     m_map = BlockMap<Numbering>(graph);
     
@@ -60,6 +57,8 @@ void PrePostNumbering::compute(Graph& graph)
     }
 }
 
+PrePostNumbering::~PrePostNumbering() { }
+
 } } // namespace JSC::DFG
 
 namespace WTF {
index 286bf62afb406307db8003e0572256fbe6ff27b9..de8282c4a581ba223a41d81efa9531d2e694c22b 100644 (file)
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGAnalysis.h"
 #include "DFGBasicBlock.h"
 #include "DFGBlockMap.h"
+#include <wtf/FastMalloc.h>
+#include <wtf/Noncopyable.h>
 
 namespace JSC { namespace DFG {
 
@@ -40,13 +41,13 @@ enum EdgeKind {
     BackEdge
 };
 
-class PrePostNumbering : public Analysis<PrePostNumbering> {
+class PrePostNumbering {
+    WTF_MAKE_NONCOPYABLE(PrePostNumbering);
+    WTF_MAKE_FAST_ALLOCATED;
 public:
-    PrePostNumbering();
+    PrePostNumbering(Graph&);
     ~PrePostNumbering();
 
-    void compute(Graph&);
-    
     unsigned preNumber(BasicBlock* block) const { return m_map[block].m_preNumber; }
     unsigned postNumber(BasicBlock* block) const { return m_map[block].m_postNumber; }
     
@@ -90,7 +91,7 @@ private:
         unsigned m_preNumber;
         unsigned m_postNumber;
     };
-    
+
     BlockMap<Numbering> m_map;
 };
 
index 8889c0ef52ae633140820c3ef6b7c131d199eae5..0fd86a2a56fafbf6982e0ea92b35f8485d5629e0 100644 (file)
@@ -76,7 +76,7 @@ public:
             m_graph.dump();
         }
 
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         
         SSACalculator ssaCalculator(m_graph);
         InsertionSet insertionSet(m_graph);
index 263cd2a4f1d19fe6768aa8002f5a577f8e7fd1e9..cff246fe7214f8e7c34fe8e2c2a1fa035295adfc 100644 (file)
@@ -95,12 +95,12 @@ SSACalculator::Def* SSACalculator::newDef(Variable* variable, BasicBlock* block,
 
 SSACalculator::Def* SSACalculator::nonLocalReachingDef(BasicBlock* block, Variable* variable)
 {
-    return reachingDefAtTail(m_graph.m_dominators.immediateDominatorOf(block), variable);
+    return reachingDefAtTail(m_graph.m_dominators->immediateDominatorOf(block), variable);
 }
 
 SSACalculator::Def* SSACalculator::reachingDefAtTail(BasicBlock* block, Variable* variable)
 {
-    for (; block; block = m_graph.m_dominators.immediateDominatorOf(block)) {
+    for (; block; block = m_graph.m_dominators->immediateDominatorOf(block)) {
         if (Def* def = m_data[block].m_defs.get(variable))
             return def;
     }
index 4f4f86529e69bc59a9a3f7ced7bbd3988f66c256..d3b32518c4bc9a5bc22fd1f0181c0b2b49783aab 100644 (file)
@@ -176,10 +176,10 @@ public:
     template<typename PhiInsertionFunctor>
     void computePhis(const PhiInsertionFunctor& functor)
     {
-        DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators.isValid());
+        DFG_ASSERT(m_graph, nullptr, m_graph.m_dominators);
         
         for (Variable& variable : m_variables) {
-            m_graph.m_dominators.forAllBlocksInPrunedIteratedDominanceFrontierOf(
+            m_graph.m_dominators->forAllBlocksInPrunedIteratedDominanceFrontierOf(
                 variable.m_blocksWithDefs,
                 [&] (BasicBlock* block) -> bool {
                     Node* phiNode = functor(&variable, block);
index 7e4d187d010957576b6d6cfc464d838f38f7a0f9..de100687baec7e379f8cd3cde29b5fea4d6f2708 100644 (file)
@@ -54,7 +54,7 @@ public:
         RELEASE_ASSERT(m_graph.m_form == ThreadedCPS);
         
         m_graph.clearReplacements();
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         
         if (verbose) {
             dataLog("Graph before SSA transformation:\n");
index b5e1a364f6a73ca1328033981ff68f0c1c4e10cd..bb23a7b9fc892eed8393eb04c7e73d1c51cbd65e 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "DFGBasicBlockInlines.h"
 #include "DFGGraph.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "JSCInlines.h"
 
@@ -44,7 +45,7 @@ public:
     
     bool run()
     {
-        m_graph.m_naturalLoops.computeIfNecessary(m_graph);
+        m_graph.ensureNaturalLoops();
         
         // Estimate basic block execution counts based on loop depth.
         for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
@@ -52,7 +53,7 @@ public:
             if (!block)
                 continue;
 
-            block->executionCount = pow(10, m_graph.m_naturalLoops.loopDepth(block));
+            block->executionCount = pow(10, m_graph.m_naturalLoops->loopDepth(block));
         }
         
         // Estimate branch weights based on execution counts. This isn't quite correct. It'll
index b13cdddfa7eb33c98a8ca94de3c4cd7e9e1fbac4..bd4a74aa94bf01c160ff34209d07808920c52d6f 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "DFGGraph.h"
 #include "DFGInsertionSet.h"
+#include "DFGNaturalLoops.h"
 #include "DFGPhase.h"
 #include "FTLCapabilities.h"
 #include "JSCInlines.h"
@@ -66,8 +67,8 @@ public:
 
         // First we find all the loops that contain a LoopHint for which we cannot OSR enter.
         // We use that information to decide if we need CheckTierUpAndOSREnter or CheckTierUpWithNestedTriggerAndOSREnter.
-        NaturalLoops& naturalLoops = m_graph.m_naturalLoops;
-        naturalLoops.computeIfNecessary(m_graph);
+        m_graph.ensureNaturalLoops();
+        NaturalLoops& naturalLoops = *m_graph.m_naturalLoops;
 
         HashSet<const NaturalLoop*> loopsContainingLoopHintWithoutOSREnter = findLoopsContainingLoopHintWithoutOSREnter(naturalLoops, level);
         
index 70032dcf7e5bc2a795e0f33301e3a4f53adaa9d9..548e76dfd2e143931c793d4a736e8c18cf3c9055 100644 (file)
@@ -99,8 +99,8 @@ void link(State& state)
             Profiler::OriginStack(),
             toCString("Generated FTL JIT code for ", CodeBlockWithJITType(codeBlock, JITCode::FTLJIT), ", instruction count = ", graph.m_codeBlock->instructionCount(), ":\n"));
         
-        graph.m_dominators.computeIfNecessary(graph);
-        graph.m_naturalLoops.computeIfNecessary(graph);
+        graph.ensureDominators();
+        graph.ensureNaturalLoops();
         
         const char* prefix = "    ";
         
index 59e988073f5b2eb5b6c61c6d1d10f9ee81cead68..e22e8039f8ab0512c0521a08257508cfa4e96e6e 100644 (file)
@@ -30,6 +30,7 @@
 
 #include "CodeBlockWithJITType.h"
 #include "DFGAbstractInterpreterInlines.h"
+#include "DFGDominators.h"
 #include "DFGInPlaceAbstractState.h"
 #include "DFGOSRAvailabilityAnalysisPhase.h"
 #include "DFGOSRExitFuzz.h"
@@ -121,7 +122,7 @@ public:
         } else
             name = "jsBody";
         
-        m_graph.m_dominators.computeIfNecessary(m_graph);
+        m_graph.ensureDominators();
         
         m_ftlState.module =
             moduleCreateWithNameInContext(name.data(), m_ftlState.context);
@@ -382,7 +383,7 @@ private:
             BasicBlock* target = m_graph.block(blockIndex);
             if (!target)
                 continue;
-            if (m_graph.m_dominators.dominates(m_highBlock, target)) {
+            if (m_graph.m_dominators->dominates(m_highBlock, target)) {
                 if (verboseCompilationEnabled())
                     dataLog("Block ", *target, " will bail also.\n");
                 target->cfaHasVisited = false;
@@ -9156,7 +9157,7 @@ private:
     {
         if (!value)
             return false;
-        if (!m_graph.m_dominators.dominates(value.block(), m_highBlock))
+        if (!m_graph.m_dominators->dominates(value.block(), m_highBlock))
             return false;
         return true;
     }
index 8119937f2c60b7b1cfbc0e8de038f57fada49d13..9e611ae8028b0b9863c469f17a42f11002187dd5 100644 (file)
@@ -1,3 +1,75 @@
+2015-11-01  Filip Pizlo  <fpizlo@apple.com>
+
+        Dominators should be factored out of the DFG
+        https://bugs.webkit.org/show_bug.cgi?id=150764
+
+        Reviewed by Geoffrey Garen.
+
+        This takes what used to be DFGDominators.h/DFGDominators.cpp and turns it into a generic
+        algorithm that can take any abstract graph. The idea is that you create Dominators<CFG> and
+        pass it a CFG object, which defines the types of graph nodes and methods for getting
+        successors, predecessors, etc. The DFG now defines a class called CFG, which is a wrapper for
+        DFG::Graph that conforms to the thing that wtf/Dominators.h expects.
+
+        When doing things to graphs, it's common to refer to the things in the graph as "nodes".
+        Because I intend to reuse the CFG abstraction with many graph algorithms, that abstraction uses
+        the term "node" to refer to a DFG basic block. But in Dominators, the method and variable names
+        still use "block". This is because although Dominators are applicable to any kind of directed
+        graph, it's super unlikely that we will ever use them for anything but compilers. Indeed, the
+        only reason why I'm factoring them out of the DFG is so that I can use them with B3 and Air.
+
+        This has the nice side effect that a user of WTF::Dominators<JSC::DFG::CFG> will see familiar
+        terminology like "blocksStrictlyDominatedBy(...)" instead of "nodesStrictlyDominatedBy(...)",
+        which would be super confusing.
+
+        Overall, wtf/Dominators.h is a combination of what used to be in DFGDominators.h,
+        DFGDominators.cpp, DFGNaiveDominators.h, and DFGNaiveDominators.cpp. I only changed code when I
+        had to in order to make it generic.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/CMakeLists.txt:
+        * wtf/Dominators.h: Added.
+        (WTF::Dominators::Dominators):
+        (WTF::Dominators::compute):
+        (WTF::Dominators::strictlyDominates):
+        (WTF::Dominators::dominates):
+        (WTF::Dominators::immediateDominatorOf):
+        (WTF::Dominators::forAllStrictDominatorsOf):
+        (WTF::Dominators::forAllDominatorsOf):
+        (WTF::Dominators::forAllBlocksStrictlyDominatedBy):
+        (WTF::Dominators::forAllBlocksDominatedBy):
+        (WTF::Dominators::strictDominatorsOf):
+        (WTF::Dominators::dominatorsOf):
+        (WTF::Dominators::blocksStrictlyDominatedBy):
+        (WTF::Dominators::blocksDominatedBy):
+        (WTF::Dominators::forAllBlocksInDominanceFrontierOf):
+        (WTF::Dominators::dominanceFrontierOf):
+        (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
+        (WTF::Dominators::forAllBlocksInPrunedIteratedDominanceFrontierOf):
+        (WTF::Dominators::iteratedDominanceFrontierOf):
+        (WTF::Dominators::dump):
+        (WTF::Dominators::LengauerTarjan::LengauerTarjan):
+        (WTF::Dominators::LengauerTarjan::compute):
+        (WTF::Dominators::LengauerTarjan::immediateDominator):
+        (WTF::Dominators::LengauerTarjan::computeDepthFirstPreNumbering):
+        (WTF::Dominators::LengauerTarjan::computeSemiDominatorsAndImplicitImmediateDominators):
+        (WTF::Dominators::LengauerTarjan::computeExplicitImmediateDominators):
+        (WTF::Dominators::LengauerTarjan::link):
+        (WTF::Dominators::LengauerTarjan::eval):
+        (WTF::Dominators::LengauerTarjan::compress):
+        (WTF::Dominators::LengauerTarjan::BlockData::BlockData):
+        (WTF::Dominators::NaiveDominators::NaiveDominators):
+        (WTF::Dominators::NaiveDominators::dominates):
+        (WTF::Dominators::NaiveDominators::dump):
+        (WTF::Dominators::NaiveDominators::pruneDominators):
+        (WTF::Dominators::ValidationContext::ValidationContext):
+        (WTF::Dominators::ValidationContext::reportError):
+        (WTF::Dominators::ValidationContext::handleErrors):
+        (WTF::Dominators::naiveDominates):
+        (WTF::Dominators::forAllBlocksInDominanceFrontierOfImpl):
+        (WTF::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
+        (WTF::Dominators::BlockData::BlockData):
+
 2015-11-01  Darin Adler  <darin@apple.com>
 
         Remove some dead and unneeded code (ScrollbarThemeSafari, RenderThemeSafari, OPENCL, a little color space logic)
index ed0a7be3b2e266bfd201d2d80834b5199a278008..4e051b41ac79eebb4e20f55000d6b28f6b21980f 100644 (file)
@@ -25,6 +25,7 @@
                0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
                0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
                0F3501641BB258D500F0A2A3 /* WeakRandom.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3501631BB258C800F0A2A3 /* WeakRandom.h */; };
+               0F4570431BE5B58F0062A629 /* Dominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F4570421BE5B58F0062A629 /* Dominators.h */; };
                0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
                0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
                0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
@@ -50,8 +51,8 @@
                0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
                0FEB3DCF1BB5D684009D7AAD /* SharedTask.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */; };
                0FEB3DD11BB7366B009D7AAD /* ParallelVectorIterator.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */; };
-               0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
                0FEC84AF1BD825310080FF74 /* GraphNodeWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */; };
+               0FEC84B11BDACD390080FF74 /* ScopedLambda.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FEC84B01BDACD390080FF74 /* ScopedLambda.h */; };
                0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
                0FF860951BCCBD740045127F /* PointerComparison.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FF860941BCCBD740045127F /* PointerComparison.h */; };
                0FFF19DC1BB334EB00886D91 /* ParallelHelperPool.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */; };
                0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
                0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
                0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
+               0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
                0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
                0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
                0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
                0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
                0FEB3DCE1BB5D684009D7AAD /* SharedTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SharedTask.h; sourceTree = "<group>"; };
                0FEB3DD01BB7366B009D7AAD /* ParallelVectorIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParallelVectorIterator.h; sourceTree = "<group>"; };
-               0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
                0FEC84AE1BD825310080FF74 /* GraphNodeWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = GraphNodeWorklist.h; sourceTree = "<group>"; };
+               0FEC84B01BDACD390080FF74 /* ScopedLambda.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ScopedLambda.h; sourceTree = "<group>"; };
                0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
                0FF860941BCCBD740045127F /* PointerComparison.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PointerComparison.h; sourceTree = "<group>"; };
                0FFF19DA1BB334EB00886D91 /* ParallelHelperPool.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParallelHelperPool.cpp; sourceTree = "<group>"; };
                                0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */,
                                A8A4727E151A825A004123FF /* Deque.h */,
                                A8A4727F151A825A004123FF /* DisallowCType.h */,
+                               0F4570421BE5B58F0062A629 /* Dominators.h */,
                                A8A47280151A825A004123FF /* DoublyLinkedList.h */,
                                A8A47297151A825A004123FF /* dtoa.cpp */,
                                A8A47298151A825A004123FF /* dtoa.h */,
                                1AFDE6531953B23D00C48FFA /* Optional.h in Headers */,
                                A8A473F6151A825B004123FF /* OSAllocator.h in Headers */,
                                7CBBA07419BB7FDC00BBF025 /* OSObjectPtr.h in Headers */,
+                               0F4570431BE5B58F0062A629 /* Dominators.h in Headers */,
                                A8A473FA151A825B004123FF /* OSRandomSource.h in Headers */,
                                A8A473FE151A825B004123FF /* PackedIntVector.h in Headers */,
                                A8A473FF151A825B004123FF /* PageAllocation.h in Headers */,
index 3a926faeb2aae9ad50a52bdf9bd852e0374639eb..5ed0c4542d24f15b9686212b6f8207dd57dff836 100644 (file)
@@ -16,6 +16,7 @@ set(WTF_HEADERS
     CurrentTime.h
     DataLog.h
     DateMath.h
+    Dominators.h
     DecimalNumber.h
     DeferrableRefCounted.h
     Deque.h
diff --git a/Source/WTF/wtf/Dominators.h b/Source/WTF/wtf/Dominators.h
new file mode 100644 (file)
index 0000000..82db530
--- /dev/null
@@ -0,0 +1,746 @@
+/*
+ * Copyright (C) 2011, 2014, 2015 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 WTFDominators_h
+#define WTFDominators_h
+
+#include <wtf/GraphNodeWorklist.h>
+
+namespace WTF {
+
+// This is a utility for finding the dominators of a graph. Dominators are almost universally used
+// for control flow graph analysis, so this code will refer to the graph's "nodes" as "blocks". In
+// that regard this code is kind of specialized for the various JSC compilers, but you could use it
+// for non-compiler things if you are OK with referring to your "nodes" as "blocks".
+
+template<typename Graph>
+class Dominators {
+public:
+    Dominators(Graph& graph, bool selfCheck = false)
+        : m_graph(graph)
+    {
+        LengauerTarjan lengauerTarjan(m_graph);
+        lengauerTarjan.compute();
+
+        m_data = m_graph.template newMap<BlockData>();
+    
+        // 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 (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+            typename Graph::Node block = m_graph.node(blockIndex);
+            if (!block)
+                continue;
+        
+            typename Graph::Node 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<GraphNodeWithOrder<typename Graph::Node>> worklist;
+        worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.node(0), GraphVisitOrder::Pre));
+        while (!worklist.isEmpty()) {
+            GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
+            switch (item.order) {
+            case GraphVisitOrder::Pre:
+                m_data[item.node].preNumber = nextPreNumber++;
+                worklist.append(GraphNodeWithOrder<typename Graph::Node>(item.node, GraphVisitOrder::Post));
+                for (typename Graph::Node kid : m_data[item.node].idomKids)
+                    worklist.append(GraphNodeWithOrder<typename Graph::Node>(kid, GraphVisitOrder::Pre));
+                break;
+            case GraphVisitOrder::Post:
+                m_data[item.node].postNumber = nextPostNumber++;
+                break;
+            }
+        }
+    
+        if (selfCheck) {
+            // 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(m_graph, *this);
+        
+            for (unsigned fromBlockIndex = m_graph.numNodes(); fromBlockIndex--;) {
+                typename Graph::Node fromBlock = m_graph.node(fromBlockIndex);
+                if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
+                    continue;
+                for (unsigned toBlockIndex = m_graph.numNodes(); toBlockIndex--;) {
+                    typename Graph::Node toBlock = m_graph.node(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");
+                }
+            }
+        
+            context.handleErrors();
+        }
+    }
+
+    bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const
+    {
+        return m_data[to].preNumber > m_data[from].preNumber
+            && m_data[to].postNumber < m_data[from].postNumber;
+    }
+    
+    bool dominates(typename Graph::Node from, typename Graph::Node to) const
+    {
+        return from == to || strictlyDominates(from, to);
+    }
+    
+    typename Graph::Node immediateDominatorOf(typename Graph::Node block) const
+    {
+        return m_data[block].idomParent;
+    }
+    
+    template<typename Functor>
+    void forAllStrictDominatorsOf(typename Graph::Node to, const Functor& functor) const
+    {
+        for (typename Graph::Node block = m_data[to].idomParent; block; block = m_data[block].idomParent)
+            functor(block);
+    }
+    
+    template<typename Functor>
+    void forAllDominatorsOf(typename Graph::Node to, const Functor& functor) const
+    {
+        for (typename Graph::Node block = to; block; block = m_data[block].idomParent)
+            functor(block);
+    }
+    
+    template<typename Functor>
+    void forAllBlocksStrictlyDominatedBy(typename Graph::Node from, const Functor& functor) const
+    {
+        Vector<typename Graph::Node, 16> worklist;
+        worklist.appendVector(m_data[from].idomKids);
+        while (!worklist.isEmpty()) {
+            typename Graph::Node block = worklist.takeLast();
+            functor(block);
+            worklist.appendVector(m_data[block].idomKids);
+        }
+    }
+    
+    template<typename Functor>
+    void forAllBlocksDominatedBy(typename Graph::Node from, const Functor& functor) const
+    {
+        Vector<typename Graph::Node, 16> worklist;
+        worklist.append(from);
+        while (!worklist.isEmpty()) {
+            typename Graph::Node block = worklist.takeLast();
+            functor(block);
+            worklist.appendVector(m_data[block].idomKids);
+        }
+    }
+    
+    typename Graph::Set strictDominatorsOf(typename Graph::Node to) const
+    {
+        typename Graph::Set result;
+        forAllStrictDominatorsOf(
+            to,
+            [&] (typename Graph::Node node) {
+                result.add(node);
+            });
+        return result;
+    }
+    
+    typename Graph::Set dominatorsOf(typename Graph::Node to) const
+    {
+        typename Graph::Set result;
+        forAllDominatorsOf(
+            to,
+            [&] (typename Graph::Node node) {
+                result.add(node);
+            });
+        return result;
+    }
+    
+    typename Graph::Set blocksStrictlyDominatedBy(typename Graph::Node from) const
+    {
+        typename Graph::Set result;
+        forAllBlocksStrictlyDominatedBy(
+            from,
+            [&] (typename Graph::Node node) {
+                result.add(node);
+            });
+        return result;
+    }
+    
+    typename Graph::Set blocksDominatedBy(typename Graph::Node from) const
+    {
+        typename Graph::Set result;
+        forAllBlocksDominatedBy(
+            from,
+            [&] (typename Graph::Node node) {
+                result.add(node);
+            });
+        return result;
+    }
+    
+    template<typename Functor>
+    void forAllBlocksInDominanceFrontierOf(
+        typename Graph::Node from, const Functor& functor) const
+    {
+        typename Graph::Set set;
+        forAllBlocksInDominanceFrontierOfImpl(
+            from,
+            [&] (typename Graph::Node block) {
+                if (set.add(block))
+                    functor(block);
+            });
+    }
+    
+    typename Graph::Set dominanceFrontierOf(typename Graph::Node from) const
+    {
+        typename Graph::Set result;
+        forAllBlocksInDominanceFrontierOf(
+            from,
+            [&] (typename Graph::Node node) {
+                result.add(node);
+            });
+        return result;
+    }
+    
+    template<typename Functor>
+    void forAllBlocksInIteratedDominanceFrontierOf(const typename Graph::List& from, const Functor& functor)
+    {
+        forAllBlocksInPrunedIteratedDominanceFrontierOf(
+            from,
+            [&] (typename Graph::Node block) -> bool {
+                functor(block);
+                return true;
+            });
+    }
+    
+    // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
+    // given functor to return false to indicate that we don't wish to consider the given block.
+    // Useful for computing pruned SSA form.
+    template<typename Functor>
+    void forAllBlocksInPrunedIteratedDominanceFrontierOf(
+        const typename Graph::List& from, const Functor& functor)
+    {
+        typename Graph::Set set;
+        forAllBlocksInIteratedDominanceFrontierOfImpl(
+            from,
+            [&] (typename Graph::Node block) -> bool {
+                if (!set.add(block))
+                    return false;
+                return functor(block);
+            });
+    }
+    
+    typename Graph::Set iteratedDominanceFrontierOf(const typename Graph::List& from) const
+    {
+        typename Graph::Set result;
+        forAllBlocksInIteratedDominanceFrontierOfImpl(
+            from,
+            [&] (typename Graph::Node node) -> bool {
+                return result.add(node);
+            });
+        return result;
+    }
+    
+    void dump(PrintStream& out) const
+    {
+        for (unsigned 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");
+        }
+    }
+    
+private:
+    // 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.template newMap<BlockData>())
+        {
+            for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
+                typename Graph::Node block = m_graph.node(blockIndex);
+                if (!block)
+                    continue;
+                m_data[block].label = block;
+            }
+        }
+    
+        void compute()
+        {
+            computeDepthFirstPreNumbering(); // Step 1.
+            computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
+            computeExplicitImmediateDominators(); // Step 4.
+        }
+    
+        typename Graph::Node immediateDominator(typename Graph::Node block)
+        {
+            return m_data[block].dom;
+        }
+
+    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.
+
+            ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
+            worklist.push(m_graph.node(0), 0);
+        
+            while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
+                typename Graph::Node block = item.node;
+                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 < m_graph.successors(block).size());
+
+                if (!successorIndex) {
+                    m_data[block].semiNumber = m_blockByPreNumber.size();
+                    m_blockByPreNumber.append(block);
+                }
+            
+                if (successorIndex < m_graph.successors(block).size()) {
+                    unsigned nextSuccessorIndex = successorIndex + 1;
+                    if (nextSuccessorIndex < m_graph.successors(block).size())
+                        worklist.forcePush(block, nextSuccessorIndex);
+
+                    typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex];
+                    if (worklist.push(successorBlock, 0))
+                        m_data[successorBlock].parent = block;
+                }
+            }
+        }
+    
+        void computeSemiDominatorsAndImplicitImmediateDominators()
+        {
+            for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
+                typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
+                BlockData& blockData = m_data[block];
+            
+                // Step 2:
+                for (typename Graph::Node predecessorBlock : m_graph.predecessors(block)) {
+                    typename Graph::Node 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 (typename Graph::Node semiDominee : m_data[blockData.parent].bucket) {
+                    typename Graph::Node 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();
+            }
+        }
+    
+        void computeExplicitImmediateDominators()
+        {
+            for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
+                typename Graph::Node 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(typename Graph::Node from, typename Graph::Node to)
+        {
+            m_data[to].ancestor = from;
+        }
+    
+        typename Graph::Node eval(typename Graph::Node block)
+        {
+            if (!m_data[block].ancestor)
+                return block;
+        
+            compress(block);
+            return m_data[block].label;
+        }
+    
+        void compress(typename Graph::Node 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.
+        
+            typename Graph::Node ancestor = m_data[initialBlock].ancestor;
+            ASSERT(ancestor);
+            if (!m_data[ancestor].ancestor)
+                return;
+        
+            Vector<typename Graph::Node, 16> stack;
+            for (typename Graph::Node 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--;) {
+                typename Graph::Node block = stack[i];
+                typename Graph::Node& labelOfBlock = m_data[block].label;
+                typename Graph::Node& ancestorOfBlock = m_data[block].ancestor;
+                ASSERT(ancestorOfBlock);
+                ASSERT(m_data[ancestorOfBlock].ancestor);
+            
+                typename Graph::Node labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
+            
+                if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
+                    labelOfBlock = labelOfAncestorOfBlock;
+                ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
+            }
+        }
+
+        struct BlockData {
+            BlockData()
+                : parent(nullptr)
+                , preNumber(UINT_MAX)
+                , semiNumber(UINT_MAX)
+                , ancestor(nullptr)
+                , label(nullptr)
+                , dom(nullptr)
+            {
+            }
+        
+            typename Graph::Node parent;
+            unsigned preNumber;
+            unsigned semiNumber;
+            typename Graph::Node ancestor;
+            typename Graph::Node label;
+            Vector<typename Graph::Node> bucket;
+            typename Graph::Node dom;
+        };
+    
+        Graph& m_graph;
+        typename Graph::template Map<BlockData> m_data;
+        Vector<typename Graph::Node> m_blockByPreNumber;
+    };
+
+    class NaiveDominators {
+    public:
+        NaiveDominators(Graph& graph)
+            : m_graph(graph)
+        {
+            // This implements a naive dominator solver.
+
+            ASSERT(!graph.predecessors(graph.root()).size());
+    
+            unsigned numBlocks = graph.numNodes();
+    
+            // Allocate storage for the dense dominance matrix. 
+            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.node(i))
+                    continue;
+                m_scratch.set(i);
+            }
+    
+            // Mark all nodes as dominated by everything.
+            for (unsigned i = numBlocks; i-- > 1;) {
+                if (!graph.node(i) || !graph.predecessors(graph.node(i)).size())
+                    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(i);
+
+                if (!changed)
+                    break;
+
+                // Prune dominators in all non entry blocks: backward scan.
+                changed = false;
+                for (unsigned i = numBlocks; i-- > 1;)
+                    changed |= pruneDominators(i);
+            } while (changed);
+        }
+        
+        bool dominates(unsigned from, unsigned to) const
+        {
+            return m_results[to].get(from);
+        }
+    
+        bool dominates(typename Graph::Node from, typename Graph::Node to) const
+        {
+            return dominates(from->index, to->index);
+        }
+    
+        void dump(PrintStream& out) const
+        {
+            for (unsigned blockIndex = 0; blockIndex < m_graph.numNodes(); ++blockIndex) {
+                typename Graph::Node block = m_graph.node(blockIndex);
+                if (!block)
+                    continue;
+                out.print("    Block ", m_graph.dump(block), ":");
+                for (unsigned otherIndex = 0; otherIndex < m_graph.numNodes(); ++otherIndex) {
+                    if (!dominates(m_graph.index(block), otherIndex))
+                        continue;
+                    out.print(" ", m_graph.dump(m_graph.node(otherIndex)));
+                }
+                out.print("\n");
+            }
+        }
+    
+    private:
+        bool pruneDominators(unsigned idx)
+        {
+            typename Graph::Node block = m_graph.node(idx);
+
+            if (!block || !m_graph.predecessors(block).size())
+                return false;
+
+            // Find the intersection of dom(preds).
+            m_scratch.set(m_results[m_graph.index(m_graph.predecessors(block)[0])]);
+            for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;)
+                m_scratch.filter(m_results[m_graph.index(m_graph.predecessors(block)[j])]);
+
+            // The block is also dominated by itself.
+            m_scratch.set(idx);
+
+            return m_results[idx].setAndCheck(m_scratch);
+        }
+    
+        Graph m_graph;
+        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 ValidationContext {
+        ValidationContext(Graph& graph, Dominators& dominators)
+            : graph(graph)
+            , dominators(dominators)
+            , naiveDominators(graph)
+        {
+        }
+    
+        void reportError(typename Graph::Node from, typename Graph::Node to, const char* message)
+        {
+            Error error;
+            error.from = from;
+            error.to = to;
+            error.message = message;
+            errors.append(error);
+        }
+    
+        void handleErrors()
+        {
+            if (errors.isEmpty())
+                return;
+        
+            dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
+            dataLog("\n");
+            dataLog("For block domination relationships:\n");
+            for (unsigned i = 0; i < errors.size(); ++i) {
+                dataLog(
+                    "    ", graph.dump(errors[i].from), " -> ", graph.dump(errors[i].to),
+                    " (", errors[i].message, ")\n");
+            }
+            dataLog("\n");
+            dataLog("Control flow graph:\n");
+            for (unsigned blockIndex = 0; blockIndex < graph.numNodes(); ++blockIndex) {
+                typename Graph::Node block = graph.node(blockIndex);
+                if (!block)
+                    continue;
+                dataLog("    Block ", graph.dump(graph.node(blockIndex)), ": successors = [");
+                CommaPrinter comma;
+                for (unsigned i = 0; i < block->numSuccessors(); ++i)
+                    dataLog(comma, graph.dump(block->successor(i)));
+                dataLog("], predecessors = [");
+                comma = CommaPrinter();
+                for (unsigned i = 0; i < block->predecessors.size(); ++i)
+                    dataLog(comma, graph.dump(block->predecessors[i]));
+                dataLog("]\n");
+            }
+            dataLog("\n");
+            dataLog("Lengauer-Tarjan Dominators:\n");
+            dataLog(dominators);
+            dataLog("\n");
+            dataLog("Naive Dominators:\n");
+            naiveDominators.dump(WTF::dataFile());
+            dataLog("\n");
+            dataLog("Graph at time of failure:\n");
+            dataLog(graph);
+            dataLog("\n");
+            dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
+            CRASH();
+        }
+    
+        Graph& graph;
+        Dominators& dominators;
+        NaiveDominators naiveDominators;
+    
+        struct Error {
+            typename Graph::Node from;
+            typename Graph::Node to;
+            const char* message;
+        };
+    
+        Vector<Error> errors;
+    };
+
+    bool naiveDominates(typename Graph::Node from, typename Graph::Node to) const
+    {
+        for (typename Graph::Node block = to; block; block = m_data[block].idomParent) {
+            if (block == from)
+                return true;
+        }
+        return false;
+    }
+    
+    template<typename Functor>
+    void forAllBlocksInDominanceFrontierOfImpl(
+        typename Graph::Node from, const Functor& functor) const
+    {
+        // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
+        //     "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
+        //     'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
+        //     dominate 'to'."
+        //
+        // A useful corner case to remember: a block may be in its own dominance frontier if it has
+        // a loop edge to itself, since it dominates itself and so it dominates its own immediate
+        // predecessor, and a block never strictly dominates itself.
+        
+        forAllBlocksDominatedBy(
+            from,
+            [&] (typename Graph::Node block) {
+                for (typename Graph::Node to : m_graph.successors(block)) {
+                    if (!strictlyDominates(from, to))
+                        functor(to);
+                }
+            });
+    }
+    
+    template<typename Functor>
+    void forAllBlocksInIteratedDominanceFrontierOfImpl(
+        const typename Graph::List& from, const Functor& functor) const
+    {
+        typename Graph::List worklist = from;
+        while (!worklist.isEmpty()) {
+            typename Graph::Node block = worklist.takeLast();
+            forAllBlocksInDominanceFrontierOfImpl(
+                block,
+                [&] (typename Graph::Node otherBlock) {
+                    if (functor(otherBlock))
+                        worklist.append(otherBlock);
+                });
+        }
+    }
+    
+    struct BlockData {
+        BlockData()
+            : idomParent(nullptr)
+            , preNumber(UINT_MAX)
+            , postNumber(UINT_MAX)
+        {
+        }
+        
+        Vector<typename Graph::Node> idomKids;
+        typename Graph::Node idomParent;
+        
+        unsigned preNumber;
+        unsigned postNumber;
+    };
+    
+    Graph& m_graph;
+    typename Graph::template Map<BlockData> m_data;
+};
+
+} // namespace WTF
+
+using WTF::Dominators;
+
+#endif // WTFDominators_h
+