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)
commitb197046bdd824402cbaadb430039b13407ee67b9
tree95fbd612a1f02a45c6ebdd773905d00dce327acb
parent582c734056ac42b62be9b8bdfe9d71e456989b73
Dominators should be factored out of the DFG
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]