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.
(JSC::DFG::EdgeDominates::operator()):
(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):
(JSC::DFG::Graph::hasDebuggerEnabled):
(JSC::DFG::LICMPhase::run):
(JSC::DFG::LICMPhase::attemptHoist):
- dfg/DFGLoopPreHeaderCreationPhase.cpp:
(JSC::DFG::createPreHeader):
(JSC::DFG::LoopPreHeaderCreationPhase::run):
(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.
(JSC::DFG::NaturalLoops::numLoops):
(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):
(JSC::DFG::SSACalculator::computePhis):
- dfg/DFGSSAConversionPhase.cpp:
(JSC::DFG::SSAConversionPhase::run):
(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):
