Beef up the DFG's CFG analyses to include iterated dominance frontiers and more user...
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 4 Sep 2014 21:08:38 +0000 (21:08 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 4 Sep 2014 21:08:38 +0000 (21:08 +0000)
commit631f30d59936ded8513f4da74d4c2be2da4711fd
tree9c72796f7e6ebb2f82c920000e62974053f8ae33
parent9734e81afdf58e309e9cbe8d8813a365f43061a2
Beef up the DFG's CFG analyses to include iterated dominance frontiers and more user-friendly BlockSets
https://bugs.webkit.org/show_bug.cgi?id=136520

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

Add code to compute iterated dominance frontiers. This involves using BlockSet a lot, so
this patch also makes BlockSet a lot more user-friendly.

* CMakeLists.txt:
* JavaScriptCore.vcxproj/JavaScriptCore.vcxproj:
* JavaScriptCore.xcodeproj/project.pbxproj:
* dfg/DFGBasicBlock.h:
* dfg/DFGBlockSet.cpp: Added.
(JSC::DFG::BlockSet::dump):
* dfg/DFGBlockSet.h:
(JSC::DFG::BlockSet::iterator::iterator):
(JSC::DFG::BlockSet::iterator::operator++):
(JSC::DFG::BlockSet::iterator::operator==):
(JSC::DFG::BlockSet::iterator::operator!=):
(JSC::DFG::BlockSet::Iterable::Iterable):
(JSC::DFG::BlockSet::Iterable::begin):
(JSC::DFG::BlockSet::Iterable::end):
(JSC::DFG::BlockSet::iterable):
(JSC::DFG::BlockAdder::BlockAdder):
(JSC::DFG::BlockAdder::operator()):
* dfg/DFGBlockSetInlines.h: Added.
(JSC::DFG::BlockSet::iterator::operator*):
* dfg/DFGDominators.cpp:
(JSC::DFG::Dominators::strictDominatorsOf):
(JSC::DFG::Dominators::dominatorsOf):
(JSC::DFG::Dominators::blocksStrictlyDominatedBy):
(JSC::DFG::Dominators::blocksDominatedBy):
(JSC::DFG::Dominators::dominanceFrontierOf):
(JSC::DFG::Dominators::iteratedDominanceFrontierOf):
* dfg/DFGDominators.h:
(JSC::DFG::Dominators::forAllStrictDominatorsOf):
(JSC::DFG::Dominators::forAllDominatorsOf):
(JSC::DFG::Dominators::forAllBlocksStrictlyDominatedBy):
(JSC::DFG::Dominators::forAllBlocksDominatedBy):
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOf):
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOf):
(JSC::DFG::Dominators::forAllBlocksInDominanceFrontierOfImpl):
(JSC::DFG::Dominators::forAllBlocksInIteratedDominanceFrontierOfImpl):
* dfg/DFGGraph.cpp:
(JSC::DFG::Graph::dumpBlockHeader):
* dfg/DFGInvalidationPointInjectionPhase.cpp:
(JSC::DFG::InvalidationPointInjectionPhase::run):

Source/WTF:

Give BitVector a way to quickly find the next set (or unset) bit. Make BitVector equality
faster. Fix a minor closure goof in Spectrum.

* wtf/BitVector.cpp:
(WTF::BitVector::equalsSlowCase):
(WTF::BitVector::equalsSlowCaseFast):
(WTF::BitVector::equalsSlowCaseSimple):
* wtf/BitVector.h:
(WTF::BitVector::findBit):
(WTF::BitVector::findBitFast):
(WTF::BitVector::findBitSimple):
(WTF::BitVector::findBitInWord):
* wtf/Spectrum.h:
(WTF::Spectrum::removeIf):

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@173279 268f45cc-cd09-0410-ab3c-d52691b4dbfc
16 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGBlockSet.cpp [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGBlockSet.h
Source/JavaScriptCore/dfg/DFGBlockSetInlines.h [new file with mode: 0644]
Source/JavaScriptCore/dfg/DFGDominators.cpp
Source/JavaScriptCore/dfg/DFGDominators.h
Source/JavaScriptCore/dfg/DFGGraph.cpp
Source/JavaScriptCore/dfg/DFGInvalidationPointInjectionPhase.cpp
Source/WTF/ChangeLog
Source/WTF/wtf/BitVector.cpp
Source/WTF/wtf/BitVector.h
Source/WTF/wtf/Spectrum.h