B3 should do LICM
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 26 Jul 2017 01:58:36 +0000 (01:58 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 26 Jul 2017 01:58:36 +0000 (01:58 +0000)
commitb52325df4ed40b8e51cfea6a1246d93edda832f6
treebdfac8b8f0d9d852d4d9f44b6670b556962987e5
parente2167e0e7b78e2e12036e2cf1ca8a85c98b49bef
B3 should do LICM
https://bugs.webkit.org/show_bug.cgi?id=174750

Reviewed by Keith Miller and Saam Barati.

Source/JavaScriptCore:

Added a LICM phase to B3. This phase is called hoistLoopInvariantValues, to conform to the B3 naming
convention for phases (it has to be an imperative). The phase uses NaturalLoops and BackwardsDominators,
so this adds those analyses to B3. BackwardsDominators was already available in templatized form. This
change templatizes DFG::NaturalLoops so that we can just use it.

The LICM phase itself is really simple. We are decently precise with our handling of everything except
the relationship between control dependence and side exits.

Also added a bunch of tests.

This isn't super important. It's perf-neutral on JS benchmarks. FTL already does LICM on DFG SSA IR, and
probably all current WebAssembly content has had LICM done to it. That being said, this is a cheap phase
so it doesn't hurt to have it.

I wrote it because I thought I needed it for bug 174727. It turns out that there's a better way to
handle the problem I had, so I ended up not needed it - but by then I had already written it. I think
it's good to have it because LICM is one of those core compiler phases; every compiler has it
eventually.

* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3BackwardsCFG.h: Added.
(JSC::B3::BackwardsCFG::BackwardsCFG):
* b3/B3BackwardsDominators.h: Added.
(JSC::B3::BackwardsDominators::BackwardsDominators):
* b3/B3BasicBlock.cpp:
(JSC::B3::BasicBlock::appendNonTerminal):
* b3/B3Effects.h:
* b3/B3EnsureLoopPreHeaders.cpp: Added.
(JSC::B3::ensureLoopPreHeaders):
* b3/B3EnsureLoopPreHeaders.h: Added.
* b3/B3Generate.cpp:
(JSC::B3::generateToAir):
* b3/B3HoistLoopInvariantValues.cpp: Added.
(JSC::B3::hoistLoopInvariantValues):
* b3/B3HoistLoopInvariantValues.h: Added.
* b3/B3NaturalLoops.h: Added.
(JSC::B3::NaturalLoops::NaturalLoops):
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::invalidateCFG):
(JSC::B3::Procedure::naturalLoops):
(JSC::B3::Procedure::backwardsCFG):
(JSC::B3::Procedure::backwardsDominators):
* b3/B3Procedure.h:
* b3/testb3.cpp:
(JSC::B3::generateLoop):
(JSC::B3::makeArrayForLoops):
(JSC::B3::generateLoopNotBackwardsDominant):
(JSC::B3::oneFunction):
(JSC::B3::noOpFunction):
(JSC::B3::testLICMPure):
(JSC::B3::testLICMPureSideExits):
(JSC::B3::testLICMPureWritesPinned):
(JSC::B3::testLICMPureWrites):
(JSC::B3::testLICMReadsLocalState):
(JSC::B3::testLICMReadsPinned):
(JSC::B3::testLICMReads):
(JSC::B3::testLICMPureNotBackwardsDominant):
(JSC::B3::testLICMPureFoiledByChild):
(JSC::B3::testLICMPureNotBackwardsDominantFoiledByChild):
(JSC::B3::testLICMExitsSideways):
(JSC::B3::testLICMWritesLocalState):
(JSC::B3::testLICMWrites):
(JSC::B3::testLICMFence):
(JSC::B3::testLICMWritesPinned):
(JSC::B3::testLICMControlDependent):
(JSC::B3::testLICMControlDependentNotBackwardsDominant):
(JSC::B3::testLICMControlDependentSideExits):
(JSC::B3::testLICMReadsPinnedWritesPinned):
(JSC::B3::testLICMReadsWritesDifferentHeaps):
(JSC::B3::testLICMReadsWritesOverlappingHeaps):
(JSC::B3::testLICMDefaultCall):
(JSC::B3::run):
* dfg/DFGBasicBlock.h:
* dfg/DFGCFG.h:
* dfg/DFGNaturalLoops.cpp: Removed.
* dfg/DFGNaturalLoops.h:
(JSC::DFG::NaturalLoops::NaturalLoops):
(JSC::DFG::NaturalLoop::NaturalLoop): Deleted.
(JSC::DFG::NaturalLoop::header): Deleted.
(JSC::DFG::NaturalLoop::size): Deleted.
(JSC::DFG::NaturalLoop::at): Deleted.
(JSC::DFG::NaturalLoop::operator[]): Deleted.
(JSC::DFG::NaturalLoop::contains): Deleted.
(JSC::DFG::NaturalLoop::index): Deleted.
(JSC::DFG::NaturalLoop::isOuterMostLoop): Deleted.
(JSC::DFG::NaturalLoop::addBlock): Deleted.
(JSC::DFG::NaturalLoops::numLoops): Deleted.
(JSC::DFG::NaturalLoops::loop): Deleted.
(JSC::DFG::NaturalLoops::headerOf): Deleted.
(JSC::DFG::NaturalLoops::innerMostLoopOf): Deleted.
(JSC::DFG::NaturalLoops::innerMostOuterLoop): Deleted.
(JSC::DFG::NaturalLoops::belongsTo): Deleted.
(JSC::DFG::NaturalLoops::loopDepth): Deleted.

Source/WTF:

Moved DFG::NaturalLoops to WTF. The new templatized NaturalLoops<> uses the same Graph abstraction as
Dominators<>. This allows us to add a B3::NaturalLoops for free.

Also made small tweaks to RangeSet, which the LICM uses.

* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Dominators.h:
* wtf/NaturalLoops.h: Added.
(WTF::NaturalLoop::NaturalLoop):
(WTF::NaturalLoop::graph):
(WTF::NaturalLoop::header):
(WTF::NaturalLoop::size):
(WTF::NaturalLoop::at):
(WTF::NaturalLoop::operator[]):
(WTF::NaturalLoop::contains):
(WTF::NaturalLoop::index):
(WTF::NaturalLoop::isOuterMostLoop):
(WTF::NaturalLoop::dump):
(WTF::NaturalLoop::addBlock):
(WTF::NaturalLoops::NaturalLoops):
(WTF::NaturalLoops::graph):
(WTF::NaturalLoops::numLoops):
(WTF::NaturalLoops::loop):
(WTF::NaturalLoops::headerOf):
(WTF::NaturalLoops::innerMostLoopOf):
(WTF::NaturalLoops::innerMostOuterLoop):
(WTF::NaturalLoops::belongsTo):
(WTF::NaturalLoops::loopDepth):
(WTF::NaturalLoops::loopsOf):
(WTF::NaturalLoops::dump):
* wtf/RangeSet.h:
(WTF::RangeSet::begin):
(WTF::RangeSet::end):
(WTF::RangeSet::addAll):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@219898 268f45cc-cd09-0410-ab3c-d52691b4dbfc
26 files changed:
Source/JavaScriptCore/CMakeLists.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3BackwardsCFG.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3BackwardsDominators.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3BasicBlock.cpp
Source/JavaScriptCore/b3/B3Effects.h
Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3Generate.cpp
Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3NaturalLoops.h [new file with mode: 0644]
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/testb3.cpp
Source/JavaScriptCore/dfg/DFGBasicBlock.h
Source/JavaScriptCore/dfg/DFGCFG.h
Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp [deleted file]
Source/JavaScriptCore/dfg/DFGNaturalLoops.h
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Dominators.h
Source/WTF/wtf/NaturalLoops.h [new file with mode: 0644]
Source/WTF/wtf/RangeSet.h