DFG should compute immediate dominators using the O(n log n) form of Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
https://bugs.webkit.org/show_bug.cgi?id=93361
Reviewed by Mark Hahnenberg.
Source/JavaScriptCore:
This patch also adds some new utilities for reasoning about block-keyed maps, block sets,
and block worklists. It changes preexisting code to use these abstractions.
(JSC::DFG::Analysis::computeIfNecessary):
(JSC::DFG::Analysis::computeDependencies):
- dfg/DFGBlockMap.h: Added.
(JSC::DFG::BlockMap::BlockMap):
(JSC::DFG::BlockMap::size):
(JSC::DFG::BlockMap::atIndex):
(JSC::DFG::BlockMap::operator[]):
- dfg/DFGBlockMapInlines.h: Added.
(JSC::DFG::BlockMap<T>::BlockMap):
- dfg/DFGBlockSet.h: Added.
(JSC::DFG::BlockSet::BlockSet):
(JSC::DFG::BlockSet::add):
(JSC::DFG::BlockSet::contains):
- dfg/DFGBlockWorklist.cpp: Added.
(JSC::DFG::BlockWorklist::BlockWorklist):
(JSC::DFG::BlockWorklist::~BlockWorklist):
(JSC::DFG::BlockWorklist::push):
(JSC::DFG::BlockWorklist::pop):
(JSC::DFG::PostOrderBlockWorklist::PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::~PostOrderBlockWorklist):
(JSC::DFG::PostOrderBlockWorklist::pushPre):
(JSC::DFG::PostOrderBlockWorklist::pushPost):
(JSC::DFG::PostOrderBlockWorklist::pop):
- dfg/DFGBlockWorklist.h: Added.
(JSC::DFG::BlockWorklist::notEmpty):
(JSC::DFG::BlockWith::BlockWith):
(JSC::DFG::BlockWith::operator UnspecifiedBoolType*):
(JSC::DFG::ExtendedBlockWorklist::ExtendedBlockWorklist):
(JSC::DFG::ExtendedBlockWorklist::forcePush):
(JSC::DFG::ExtendedBlockWorklist::push):
(JSC::DFG::ExtendedBlockWorklist::notEmpty):
(JSC::DFG::ExtendedBlockWorklist::pop):
(JSC::DFG::BlockWithOrder::BlockWithOrder):
(JSC::DFG::BlockWithOrder::operator UnspecifiedBoolType*):
(JSC::DFG::PostOrderBlockWorklist::push):
(JSC::DFG::PostOrderBlockWorklist::notEmpty):
- dfg/DFGCSEPhase.cpp:
- dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::compute):
(JSC::DFG::Dominators::naiveDominates):
(JSC::DFG::Dominators::dump):
(JSC::DFG::Dominators::pruneDominators): Deleted.
(JSC::DFG::Dominators::strictlyDominates):
(JSC::DFG::Dominators::dominates):
(JSC::DFG::Dominators::BlockData::BlockData):
(JSC::DFG::Graph::dumpBlockHeader):
(JSC::DFG::Graph::getBlocksInPreOrder):
(JSC::DFG::Graph::getBlocksInPostOrder):
- dfg/DFGInvalidationPointInjectionPhase.cpp:
(JSC::DFG::InvalidationPointInjectionPhase::run):
- dfg/DFGNaiveDominators.cpp: Added.
(JSC::DFG::NaiveDominators::NaiveDominators):
(JSC::DFG::NaiveDominators::~NaiveDominators):
(JSC::DFG::NaiveDominators::compute):
(JSC::DFG::NaiveDominators::pruneDominators):
(JSC::DFG::NaiveDominators::dump):
- dfg/DFGNaiveDominators.h: Added.
(JSC::DFG::NaiveDominators::dominates):
(JSC::DFG::NaturalLoops::computeDependencies):
(JSC::DFG::NaturalLoops::compute):
Source/WTF:
Make BitVector operations return the previous value of the bit you're changing. This is
useful for the kinds of set operations that are commonplace in compiler graph searches.
(WTF::BitVector::quickSet):
(WTF::BitVector::quickClear):
(WTF::BitVector::set):
(WTF::BitVector::ensureSizeAndSet):
(WTF::BitVector::clear):
