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)
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: http://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

index 5f473bc..c5c7a2f 100644 (file)
@@ -143,11 +143,13 @@ set(JavaScriptCore_SOURCES
     b3/B3DuplicateTails.cpp
     b3/B3Effects.cpp
     b3/B3EliminateCommonSubexpressions.cpp
+    b3/B3EnsureLoopPreHeaders.cpp
     b3/B3FenceValue.cpp
     b3/B3FixSSA.cpp
     b3/B3FoldPathConstants.cpp
     b3/B3FrequencyClass.cpp
     b3/B3Generate.cpp
+    b3/B3HoistLoopInvariantValues.cpp
     b3/B3InferSwitches.cpp
     b3/B3InsertionSet.cpp
     b3/B3Kind.cpp
@@ -364,7 +366,6 @@ set(JavaScriptCore_SOURCES
     dfg/DFGMinifiedNode.cpp
     dfg/DFGMovHintRemovalPhase.cpp
     dfg/DFGMultiGetByOffsetData.cpp
-    dfg/DFGNaturalLoops.cpp
     dfg/DFGNode.cpp
     dfg/DFGNodeAbstractValuePair.cpp
     dfg/DFGNodeFlags.cpp
index f9e8568..d8d8e36 100644 (file)
@@ -1,3 +1,105 @@
+2017-07-23  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should do LICM
+        https://bugs.webkit.org/show_bug.cgi?id=174750
+
+        Reviewed by Keith Miller and Saam Barati.
+        
+        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.
+
 2017-07-24  Filip Pizlo  <fpizlo@apple.com>
 
         GC should be fine with trading blocks between destructor and non-destructor blocks
index 49344f0..c758cfb 100644 (file)
                0F5A6284188C98D40072C9DF /* FTLValueRange.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5A6282188C98D40072C9DF /* FTLValueRange.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F5AE2C41DF4F2800066EFE1 /* VMInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = FE90BB3A1B7CF64E006B3F03 /* VMInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
                0F5B4A331C84F0D600F1B17E /* SlowPathReturnType.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5B4A321C84F0D600F1B17E /* SlowPathReturnType.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               0F5BF1631F2317120029D91D /* B3HoistLoopInvariantValues.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5BF1611F2317120029D91D /* B3HoistLoopInvariantValues.cpp */; };
+               0F5BF1641F2317120029D91D /* B3HoistLoopInvariantValues.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF1621F2317120029D91D /* B3HoistLoopInvariantValues.h */; };
+               0F5BF1671F23A0980029D91D /* B3BackwardsCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF1661F23A0980029D91D /* B3BackwardsCFG.h */; };
+               0F5BF1691F23A0AA0029D91D /* B3NaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF1681F23A0AA0029D91D /* B3NaturalLoops.h */; };
+               0F5BF16B1F23A0C10029D91D /* B3BackwardsDominators.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF16A1F23A0C10029D91D /* B3BackwardsDominators.h */; };
+               0F5BF1701F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5BF16E1F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp */; };
+               0F5BF1711F23A5A10029D91D /* B3EnsureLoopPreHeaders.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5BF16F1F23A5A10029D91D /* B3EnsureLoopPreHeaders.h */; };
                0F5CF9811E96F17F00C18692 /* AirTmpMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5CF9801E96F17D00C18692 /* AirTmpMap.h */; };
                0F5CF9841E9D537700C18692 /* AirLowerStackArgs.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F5CF9831E9D537500C18692 /* AirLowerStackArgs.h */; };
                0F5CF9851E9D537A00C18692 /* AirLowerStackArgs.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F5CF9821E9D537500C18692 /* AirLowerStackArgs.cpp */; };
                A730B6121250068F009D25B1 /* StrictEvalActivation.h in Headers */ = {isa = PBXBuildFile; fileRef = A730B6101250068F009D25B1 /* StrictEvalActivation.h */; };
                A730B6131250068F009D25B1 /* StrictEvalActivation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */; };
                A731B25A130093880040A7FA /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 51F0EB6105C86C6B00E6DF1B /* Foundation.framework */; };
-               A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */; };
                A737810E1799EA2E00817533 /* DFGNaturalLoops.h in Headers */ = {isa = PBXBuildFile; fileRef = A737810B1799EA2E00817533 /* DFGNaturalLoops.h */; };
                A7386554118697B400540279 /* SpecializedThunkJIT.h in Headers */ = {isa = PBXBuildFile; fileRef = A7386551118697B400540279 /* SpecializedThunkJIT.h */; };
                A7386555118697B400540279 /* ThunkGenerators.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7386552118697B400540279 /* ThunkGenerators.cpp */; };
                0F5A6281188C98D40072C9DF /* FTLValueRange.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = FTLValueRange.cpp; path = ftl/FTLValueRange.cpp; sourceTree = "<group>"; };
                0F5A6282188C98D40072C9DF /* FTLValueRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = FTLValueRange.h; path = ftl/FTLValueRange.h; sourceTree = "<group>"; };
                0F5B4A321C84F0D600F1B17E /* SlowPathReturnType.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SlowPathReturnType.h; sourceTree = "<group>"; };
+               0F5BF1611F2317120029D91D /* B3HoistLoopInvariantValues.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = B3HoistLoopInvariantValues.cpp; path = b3/B3HoistLoopInvariantValues.cpp; sourceTree = "<group>"; };
+               0F5BF1621F2317120029D91D /* B3HoistLoopInvariantValues.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3HoistLoopInvariantValues.h; path = b3/B3HoistLoopInvariantValues.h; sourceTree = "<group>"; };
+               0F5BF1661F23A0980029D91D /* B3BackwardsCFG.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3BackwardsCFG.h; path = b3/B3BackwardsCFG.h; sourceTree = "<group>"; };
+               0F5BF1681F23A0AA0029D91D /* B3NaturalLoops.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3NaturalLoops.h; path = b3/B3NaturalLoops.h; sourceTree = "<group>"; };
+               0F5BF16A1F23A0C10029D91D /* B3BackwardsDominators.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3BackwardsDominators.h; path = b3/B3BackwardsDominators.h; sourceTree = "<group>"; };
+               0F5BF16E1F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = B3EnsureLoopPreHeaders.cpp; path = b3/B3EnsureLoopPreHeaders.cpp; sourceTree = "<group>"; };
+               0F5BF16F1F23A5A10029D91D /* B3EnsureLoopPreHeaders.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = B3EnsureLoopPreHeaders.h; path = b3/B3EnsureLoopPreHeaders.h; sourceTree = "<group>"; };
                0F5CF9801E96F17D00C18692 /* AirTmpMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirTmpMap.h; path = b3/air/AirTmpMap.h; sourceTree = "<group>"; };
                0F5CF9821E9D537500C18692 /* AirLowerStackArgs.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirLowerStackArgs.cpp; path = b3/air/AirLowerStackArgs.cpp; sourceTree = "<group>"; };
                0F5CF9831E9D537500C18692 /* AirLowerStackArgs.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirLowerStackArgs.h; path = b3/air/AirLowerStackArgs.h; sourceTree = "<group>"; };
                A7299DA417D12858005F5FF9 /* SetConstructor.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SetConstructor.h; sourceTree = "<group>"; };
                A730B6101250068F009D25B1 /* StrictEvalActivation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StrictEvalActivation.h; sourceTree = "<group>"; };
                A730B6111250068F009D25B1 /* StrictEvalActivation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StrictEvalActivation.cpp; sourceTree = "<group>"; };
-               A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGNaturalLoops.cpp; path = dfg/DFGNaturalLoops.cpp; sourceTree = "<group>"; };
                A737810B1799EA2E00817533 /* DFGNaturalLoops.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGNaturalLoops.h; path = dfg/DFGNaturalLoops.h; sourceTree = "<group>"; };
                A7386551118697B400540279 /* SpecializedThunkJIT.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SpecializedThunkJIT.h; sourceTree = "<group>"; };
                A7386552118697B400540279 /* ThunkGenerators.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ThunkGenerators.cpp; sourceTree = "<group>"; };
                                0FEC84B51BDACDAC0080FF74 /* B3ArgumentRegValue.h */,
                                0F2C63B31E6343E800C13839 /* B3AtomicValue.cpp */,
                                0F2C63B41E6343E800C13839 /* B3AtomicValue.h */,
+                               0F5BF1661F23A0980029D91D /* B3BackwardsCFG.h */,
+                               0F5BF16A1F23A0C10029D91D /* B3BackwardsDominators.h */,
                                0F2C63AB1E60AE3C00C13839 /* B3Bank.cpp */,
                                0F2C63AC1E60AE3C00C13839 /* B3Bank.h */,
                                0FEC84B61BDACDAC0080FF74 /* B3BasicBlock.cpp */,
                                0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
                                0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */,
                                0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
+                               0F5BF16E1F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp */,
+                               0F5BF16F1F23A5A10029D91D /* B3EnsureLoopPreHeaders.h */,
                                0F6971E81D92F42100BA02A5 /* B3FenceValue.cpp */,
                                0F6971E91D92F42100BA02A5 /* B3FenceValue.h */,
                                0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
                                0F2C63B51E6343E800C13839 /* B3GenericBlockInsertionSet.h */,
                                0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */,
                                0FEC85C01BE167A00080FF74 /* B3HeapRange.h */,
+                               0F5BF1611F2317120029D91D /* B3HoistLoopInvariantValues.cpp */,
+                               0F5BF1621F2317120029D91D /* B3HoistLoopInvariantValues.h */,
                                DC69B99A1D15F90F002E3C00 /* B3InferSwitches.cpp */,
                                DC69B99B1D15F90F002E3C00 /* B3InferSwitches.h */,
                                0FEC85B41BE1462F0080FF74 /* B3InsertionSet.cpp */,
                                0F338E031BF0276C0013C88F /* B3MoveConstants.cpp */,
                                0F338E041BF0276C0013C88F /* B3MoveConstants.h */,
                                0F2C63C11E664A5A00C13839 /* B3NativeTraits.h */,
+                               0F5BF1681F23A0AA0029D91D /* B3NaturalLoops.h */,
                                0F338E051BF0276C0013C88F /* B3OpaqueByproduct.h */,
                                0F338E061BF0276C0013C88F /* B3OpaqueByproducts.cpp */,
                                0F338E071BF0276C0013C88F /* B3OpaqueByproducts.h */,
                                0F8F14321ADF090100ED792C /* DFGMovHintRemovalPhase.h */,
                                0FF2CD591B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp */,
                                0FF2CD5A1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h */,
-                               A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
                                A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
                                0FB4B51E16B62772003F696B /* DFGNode.cpp */,
                                86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
                                0FBB73BB1DEF8645002C009E /* DeleteAllCodeEffort.h in Headers */,
                                0F96303C1D4192CD005609D9 /* DestructionMode.h in Headers */,
                                A77A423E17A0BBFD00A8DB81 /* DFGAbstractHeap.h in Headers */,
+                               0F5BF1691F23A0AA0029D91D /* B3NaturalLoops.h in Headers */,
                                A704D90317A0BAA8006BA554 /* DFGAbstractInterpreter.h in Headers */,
                                A704D90417A0BAA8006BA554 /* DFGAbstractInterpreterInlines.h in Headers */,
                                0F620177143FCD3F0068B77C /* DFGAbstractValue.h in Headers */,
                                0F1FB3971E1AF7E300A9BE50 /* DFGWorklistInlines.h in Headers */,
                                0FE050181AA9091100D33B33 /* DirectArguments.h in Headers */,
                                0FE050161AA9091100D33B33 /* DirectArgumentsOffset.h in Headers */,
+                               0F5BF1711F23A5A10029D91D /* B3EnsureLoopPreHeaders.h in Headers */,
                                969A07980ED1D3AE00F1F681 /* DirectEvalCodeCache.h in Headers */,
                                14386A751DD69895008652C4 /* DirectEvalExecutable.h in Headers */,
                                0F37308F1C0CD68500052BFA /* DisallowMacroScratchRegisterUsage.h in Headers */,
                                A5FD0076189B038C00633231 /* IdentifiersFactory.h in Headers */,
                                C25F8BCE157544A900245B71 /* IncrementalSweeper.h in Headers */,
                                0FB7F39915ED8E4600F167B2 /* IndexingHeader.h in Headers */,
+                               0F5BF16B1F23A0C10029D91D /* B3BackwardsDominators.h in Headers */,
                                0FB7F39A15ED8E4600F167B2 /* IndexingHeaderInlines.h in Headers */,
                                0FB7F39B15ED8E4600F167B2 /* IndexingType.h in Headers */,
                                14386A791DD6989C008652C4 /* IndirectEvalExecutable.h in Headers */,
                                0F0A75231B94BFA900110660 /* InferredType.h in Headers */,
+                               0F5BF1671F23A0980029D91D /* B3BackwardsCFG.h in Headers */,
                                0FFC92121B94D4DF0071DD66 /* InferredTypeTable.h in Headers */,
                                0FF8BDEB1AD4CF7100DFE884 /* InferredValue.h in Headers */,
                                BC18C4100E16F5CD00B34460 /* InitializeThreading.h in Headers */,
                                86C36EEA0EE1289D00B3DF59 /* MacroAssembler.h in Headers */,
                                86D3B2C610156BDE002865E7 /* MacroAssemblerARM.h in Headers */,
                                A1A009C01831A22D00CF8711 /* MacroAssemblerARM64.h in Headers */,
+                               0F5BF1641F2317120029D91D /* B3HoistLoopInvariantValues.h in Headers */,
                                86ADD1460FDDEA980006EEC2 /* MacroAssemblerARMv7.h in Headers */,
                                863B23E00FC6118900703AA4 /* MacroAssemblerCodeRef.h in Headers */,
                                E32AB2441DCD75F400D7533A /* MacroAssemblerHelpers.h in Headers */,
                                0F2BDC4D1522818600CD8910 /* DFGMinifiedNode.cpp in Sources */,
                                0F8F14351ADF090100ED792C /* DFGMovHintRemovalPhase.cpp in Sources */,
                                0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */,
-                               A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
                                0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
                                0F20178A1DCB942600EA5950 /* DFGNodeAbstractValuePair.cpp in Sources */,
                                0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
                                AD2FCBE81DB58DAD00B3E736 /* JSWebAssemblyRuntimeError.cpp in Sources */,
                                AD2FCBEA1DB58DAD00B3E736 /* JSWebAssemblyTable.cpp in Sources */,
                                1442566115EDE98D0066A49B /* JSWithScope.cpp in Sources */,
+                               0F5BF1631F2317120029D91D /* B3HoistLoopInvariantValues.cpp in Sources */,
                                86E3C618167BABEE006D760A /* JSWrapperMap.mm in Sources */,
                                14280870107EC1340013E7B2 /* JSWrapperObject.cpp in Sources */,
                                BCFD8C920EEB2EE700283848 /* JumpTable.cpp in Sources */,
                                0FD3E40B1B618B6600C80E1E /* ObjectPropertyConditionSet.cpp in Sources */,
                                14469DE6107EC7E700650446 /* ObjectPrototype.cpp in Sources */,
                                E124A8F80E555775003091F1 /* OpaqueJSString.cpp in Sources */,
+                               0F5BF1701F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp in Sources */,
                                969A079A0ED1D3AE00F1F681 /* Opcode.cpp in Sources */,
                                14280850107EC0D70013E7B2 /* Operations.cpp in Sources */,
                                0FE228EE1436AB2C00196C48 /* Options.cpp in Sources */,
diff --git a/Source/JavaScriptCore/b3/B3BackwardsCFG.h b/Source/JavaScriptCore/b3/B3BackwardsCFG.h
new file mode 100644 (file)
index 0000000..2e6a71a
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "B3CFG.h"
+#include <wtf/BackwardsGraph.h>
+
+namespace JSC { namespace B3 {
+
+class BackwardsCFG : public BackwardsGraph<CFG> {
+    WTF_MAKE_NONCOPYABLE(BackwardsCFG);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    BackwardsCFG(Procedure& proc)
+        : BackwardsGraph<CFG>(proc.cfg())
+    {
+    }
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3BackwardsDominators.h b/Source/JavaScriptCore/b3/B3BackwardsDominators.h
new file mode 100644 (file)
index 0000000..bc1df09
--- /dev/null
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "B3BackwardsCFG.h"
+#include <wtf/Dominators.h>
+
+namespace JSC { namespace B3 {
+
+class BackwardsDominators : public WTF::Dominators<BackwardsCFG> {
+    WTF_MAKE_NONCOPYABLE(BackwardsDominators);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    BackwardsDominators(Procedure& proc)
+        : WTF::Dominators<BackwardsCFG>(proc.backwardsCFG())
+    {
+    }
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
index 63a4e58..1d37190 100644 (file)
@@ -57,7 +57,7 @@ void BasicBlock::append(Value* value)
 void BasicBlock::appendNonTerminal(Value* value)
 {
     m_values.append(m_values.last());
-    m_values[m_values.size() - 1] = value;
+    m_values[m_values.size() - 2] = value;
     value->owner = this;
 }
 
index b2e3fd2..f429f21 100644 (file)
@@ -75,6 +75,9 @@ struct Effects {
     // Memory fences cannot be reordered around each other regardless of their effects. This is flagged
     // if the operation is a memory fence.
     bool fence { false };
+    
+    // WARNING: The B3::hoistLoopInvariantValues() phase thinks that it understands this exhaustively. If you
+    // add any new kinds of things that can be read or written, you should check that phase.
 
     HeapRange writes;
     HeapRange reads;
diff --git a/Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp b/Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp
new file mode 100644 (file)
index 0000000..3e33153
--- /dev/null
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "B3EnsureLoopPreHeaders.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BasicBlockInlines.h"
+#include "B3BlockInsertionSet.h"
+#include "B3NaturalLoops.h"
+#include "B3ProcedureInlines.h"
+#include "B3ValueInlines.h"
+
+namespace JSC { namespace B3 {
+
+bool ensureLoopPreHeaders(Procedure& proc)
+{
+    NaturalLoops& loops = proc.naturalLoops();
+    
+    BlockInsertionSet insertionSet(proc);
+    
+    for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
+        const NaturalLoop& loop = loops.loop(loopIndex);
+        
+        Vector<BasicBlock*, 4> outOfBodyPredecessors;
+        double totalFrequency = 0;
+        for (BasicBlock* predecessor : loop.header()->predecessors()) {
+            if (loops.belongsTo(predecessor, loop))
+                continue;
+            
+            outOfBodyPredecessors.append(predecessor);
+            totalFrequency += predecessor->frequency();
+        }
+        
+        if (outOfBodyPredecessors.size() <= 1)
+            continue;
+        
+        BasicBlock* preHeader = insertionSet.insertBefore(loop.header(), totalFrequency);
+        preHeader->appendNew<Value>(proc, Jump, loop.header()->at(0)->origin());
+        preHeader->setSuccessors(FrequentedBlock(loop.header()));
+        
+        for (BasicBlock* predecessor : outOfBodyPredecessors) {
+            predecessor->replaceSuccessor(loop.header(), preHeader);
+            preHeader->addPredecessor(predecessor);
+            loop.header()->removePredecessor(predecessor);
+        }
+        
+        loop.header()->addPredecessor(preHeader);
+    }
+    
+    if (insertionSet.execute()) {
+        proc.invalidateCFG();
+        return true;
+    }
+    
+    return false;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.h b/Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.h
new file mode 100644 (file)
index 0000000..d4c64fd
--- /dev/null
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// Creates a pre-header for any loop that don't already have one. A loop has a pre-header if its header has
+// exactly one predecessor that isn't in the loop body. If a loop header has more than one out-of-body
+// predecessor, then this creates a new block and rewires those predecessors to it.
+
+bool ensureLoopPreHeaders(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
index 741f248..2284274 100644 (file)
@@ -36,6 +36,7 @@
 #include "B3EliminateCommonSubexpressions.h"
 #include "B3FixSSA.h"
 #include "B3FoldPathConstants.h"
+#include "B3HoistLoopInvariantValues.h"
 #include "B3InferSwitches.h"
 #include "B3LegalizeMemoryOffsets.h"
 #include "B3LowerMacros.h"
@@ -83,6 +84,7 @@ void generateToAir(Procedure& procedure)
     if (procedure.optLevel() >= 2) {
         reduceDoubleToFloat(procedure);
         reduceStrength(procedure);
+        hoistLoopInvariantValues(procedure);
         eliminateCommonSubexpressions(procedure);
         inferSwitches(procedure);
         duplicateTails(procedure);
diff --git a/Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.cpp b/Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.cpp
new file mode 100644 (file)
index 0000000..5f60733
--- /dev/null
@@ -0,0 +1,165 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#include "config.h"
+#include "B3HoistLoopInvariantValues.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3BackwardsDominators.h"
+#include "B3BasicBlockInlines.h"
+#include "B3Dominators.h"
+#include "B3EnsureLoopPreHeaders.h"
+#include "B3NaturalLoops.h"
+#include "B3PhaseScope.h"
+#include "B3ProcedureInlines.h"
+#include "B3ValueInlines.h"
+#include <wtf/RangeSet.h>
+
+namespace JSC { namespace B3 {
+
+bool hoistLoopInvariantValues(Procedure& proc)
+{
+    PhaseScope phaseScope(proc, "hoistLoopInvariantValues");
+    
+    ensureLoopPreHeaders(proc);
+    
+    NaturalLoops& loops = proc.naturalLoops();
+    if (!loops.numLoops())
+        return false;
+
+    proc.resetValueOwners();
+    Dominators& dominators = proc.dominators();
+    BackwardsDominators& backwardsDominators = proc.backwardsDominators();
+    
+    // FIXME: We should have a reusable B3::EffectsSet data structure.
+    // https://bugs.webkit.org/show_bug.cgi?id=174762
+    struct LoopData {
+        RangeSet<HeapRange> writes;
+        bool writesLocalState { false };
+        bool writesPinned { false };
+        bool sideExits { false };
+        BasicBlock* preHeader { nullptr };
+    };
+    
+    IndexMap<NaturalLoop, LoopData> data(loops.numLoops());
+    
+    for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
+        const NaturalLoop& loop = loops.loop(loopIndex);
+        for (BasicBlock* predecessor : loop.header()->predecessors()) {
+            if (loops.belongsTo(predecessor, loop))
+                continue;
+            RELEASE_ASSERT(!data[loop].preHeader);
+            data[loop].preHeader = predecessor;
+        }
+    }
+    
+    for (BasicBlock* block : proc) {
+        const NaturalLoop* loop = loops.innerMostLoopOf(block);
+        if (!loop)
+            continue;
+        for (Value* value : *block) {
+            Effects effects = value->effects();
+            data[*loop].writes.add(effects.writes);
+            data[*loop].writesLocalState |= effects.writesLocalState;
+            data[*loop].writesPinned |= effects.writesPinned;
+            data[*loop].sideExits |= effects.exitsSideways;
+        }
+    }
+    
+    for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
+        const NaturalLoop& loop = loops.loop(loopIndex);
+        for (const NaturalLoop* current = loops.innerMostOuterLoop(loop); current; current = loops.innerMostOuterLoop(*current)) {
+            data[*current].writes.addAll(data[loop].writes);
+            data[*current].writesLocalState |= data[loop].writesLocalState;
+            data[*current].writesPinned |= data[loop].writesPinned;
+            data[*current].sideExits |= data[loop].sideExits;
+        }
+    }
+    
+    bool changed = false;
+    
+    // Pre-order ensures that we visit our dominators before we visit ourselves. Otherwise we'd miss some
+    // hoisting opportunities in complex CFGs.
+    for (BasicBlock* block : proc.blocksInPreOrder()) {
+        Vector<const NaturalLoop*> blockLoops = loops.loopsOf(block);
+        if (blockLoops.isEmpty())
+            continue;
+        
+        for (Value*& value : *block) {
+            Effects effects = value->effects();
+            
+            // We never hoist write effects or control constructs.
+            if (effects.mustExecute())
+                continue;
+
+            // Try outermost loop first.
+            for (unsigned i = blockLoops.size(); i--;) {
+                const NaturalLoop& loop = *blockLoops[i];
+                
+                bool ok = true;
+                for (Value* child : value->children()) {
+                    if (!dominators.dominates(child->owner, data[loop].preHeader)) {
+                        ok = false;
+                        break;
+                    }
+                }
+                if (!ok)
+                    continue;
+                
+                if (effects.controlDependent) {
+                    if (!backwardsDominators.dominates(block, data[loop].preHeader))
+                        continue;
+                    
+                    // FIXME: This is super conservative. In reality, we just need to make sure that there
+                    // aren't any side exits between here and the pre-header according to backwards search.
+                    // https://bugs.webkit.org/show_bug.cgi?id=174763
+                    if (data[loop].sideExits)
+                        continue;
+                }
+                
+                if (effects.readsPinned && data[loop].writesPinned)
+                    continue;
+                
+                if (effects.readsLocalState && data[loop].writesLocalState)
+                    continue;
+                
+                if (data[loop].writes.overlaps(effects.reads))
+                    continue;
+                
+                data[loop].preHeader->appendNonTerminal(value);
+                value = proc.add<Value>(Nop, Void, value->origin());
+                changed = true;
+            }
+        }
+    }
+    
+    return changed;
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
diff --git a/Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.h b/Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.h
new file mode 100644 (file)
index 0000000..fe2377f
--- /dev/null
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+namespace JSC { namespace B3 {
+
+class Procedure;
+
+// This does loop-invariant code motion (LICM). It can hoist pure values as well as reads of state that isn't
+// modified inside the loop.
+
+bool hoistLoopInvariantValues(Procedure&);
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
diff --git a/Source/JavaScriptCore/b3/B3NaturalLoops.h b/Source/JavaScriptCore/b3/B3NaturalLoops.h
new file mode 100644 (file)
index 0000000..4a1836f
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+ * Copyright (C) 2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#if ENABLE(B3_JIT)
+
+#include "B3Dominators.h"
+#include <wtf/NaturalLoops.h>
+
+namespace JSC { namespace B3 {
+
+typedef WTF::NaturalLoop<CFG> NaturalLoop;
+
+class NaturalLoops : public WTF::NaturalLoops<CFG> {
+    WTF_MAKE_NONCOPYABLE(NaturalLoops);
+    WTF_MAKE_FAST_ALLOCATED;
+public:
+    NaturalLoops(Procedure& proc)
+        : WTF::NaturalLoops<CFG>(proc.cfg(), proc.dominators())
+    {
+    }
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
index 2c42bf1..5013e14 100644 (file)
 #if ENABLE(B3_JIT)
 
 #include "AirCode.h"
+#include "B3BackwardsCFG.h"
+#include "B3BackwardsDominators.h"
 #include "B3BasicBlockInlines.h"
 #include "B3BasicBlockUtils.h"
 #include "B3BlockWorklist.h"
 #include "B3CFG.h"
 #include "B3DataSection.h"
 #include "B3Dominators.h"
+#include "B3NaturalLoops.h"
 #include "B3OpaqueByproducts.h"
 #include "B3PhiChildren.h"
 #include "B3StackSlot.h"
@@ -200,6 +203,9 @@ void Procedure::resetReachability()
 void Procedure::invalidateCFG()
 {
     m_dominators = nullptr;
+    m_naturalLoops = nullptr;
+    m_backwardsCFG = nullptr;
+    m_backwardsDominators = nullptr;
 }
 
 void Procedure::dump(PrintStream& out) const
@@ -291,6 +297,27 @@ Dominators& Procedure::dominators()
     return *m_dominators;
 }
 
+NaturalLoops& Procedure::naturalLoops()
+{
+    if (!m_naturalLoops)
+        m_naturalLoops = std::make_unique<NaturalLoops>(*this);
+    return *m_naturalLoops;
+}
+
+BackwardsCFG& Procedure::backwardsCFG()
+{
+    if (!m_backwardsCFG)
+        m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
+    return *m_backwardsCFG;
+}
+
+BackwardsDominators& Procedure::backwardsDominators()
+{
+    if (!m_backwardsDominators)
+        m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
+    return *m_backwardsDominators;
+}
+
 void Procedure::addFastConstant(const ValueKey& constant)
 {
     RELEASE_ASSERT(constant.isConstant());
index e6c4ea7..dec13c6 100644 (file)
 
 namespace JSC { namespace B3 {
 
+class BackwardsCFG;
+class BackwardsDominators;
 class BasicBlock;
 class BlockInsertionSet;
 class CFG;
 class Dominators;
+class NaturalLoops;
 class StackSlot;
 class Value;
 class Variable;
@@ -175,6 +178,9 @@ public:
     CFG& cfg() const { return *m_cfg; }
 
     Dominators& dominators();
+    NaturalLoops& naturalLoops();
+    BackwardsCFG& backwardsCFG();
+    BackwardsDominators& backwardsDominators();
 
     void addFastConstant(const ValueKey&);
     bool isFastConstant(const ValueKey&);
@@ -271,6 +277,9 @@ private:
     SparseCollection<Value> m_values;
     std::unique_ptr<CFG> m_cfg;
     std::unique_ptr<Dominators> m_dominators;
+    std::unique_ptr<NaturalLoops> m_naturalLoops;
+    std::unique_ptr<BackwardsCFG> m_backwardsCFG;
+    std::unique_ptr<BackwardsDominators> m_backwardsDominators;
     HashSet<ValueKey> m_fastConstants;
     unsigned m_numEntrypoints { 1 };
     const char* m_lastPhaseName;
index 844d075..be88253 100644 (file)
@@ -14592,6 +14592,559 @@ void testOptimizeMaterialization()
     CHECK(found);
 }
 
+template<typename Func>
+void generateLoop(Procedure& proc, const Func& func)
+{
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* loop = proc.addBlock();
+    BasicBlock* end = proc.addBlock();
+
+    UpsilonValue* initialIndex = root->appendNew<UpsilonValue>(
+        proc, Origin(), root->appendNew<Const32Value>(proc, Origin(), 0));
+    root->appendNew<Value>(proc, Jump, Origin());
+    root->setSuccessors(loop);
+    
+    Value* index = loop->appendNew<Value>(proc, Phi, Int32, Origin());
+    initialIndex->setPhi(index);
+    
+    Value* one = func(loop, index);
+    
+    Value* nextIndex = loop->appendNew<Value>(proc, Add, Origin(), index, one);
+    UpsilonValue* loopIndex = loop->appendNew<UpsilonValue>(proc, Origin(), nextIndex);
+    loopIndex->setPhi(index);
+    loop->appendNew<Value>(
+        proc, Branch, Origin(),
+        loop->appendNew<Value>(
+            proc, LessThan, Origin(), nextIndex,
+            loop->appendNew<Const32Value>(proc, Origin(), 100)));
+    loop->setSuccessors(loop, end);
+    
+    end->appendNew<Value>(proc, Return, Origin());
+}
+
+std::array<int, 100> makeArrayForLoops()
+{
+    std::array<int, 100> result;
+    for (unsigned i = 0; i < result.size(); ++i)
+        result[i] = i & 1;
+    return result;
+}
+
+template<typename Func>
+void generateLoopNotBackwardsDominant(Procedure& proc, std::array<int, 100>& array, const Func& func)
+{
+    BasicBlock* root = proc.addBlock();
+    BasicBlock* loopHeader = proc.addBlock();
+    BasicBlock* loopCall = proc.addBlock();
+    BasicBlock* loopFooter = proc.addBlock();
+    BasicBlock* end = proc.addBlock();
+
+    UpsilonValue* initialIndex = root->appendNew<UpsilonValue>(
+        proc, Origin(), root->appendNew<Const32Value>(proc, Origin(), 0));
+    // If you look carefully, you'll notice that this is an extremely sneaky use of Upsilon that demonstrates
+    // the extent to which our SSA is different from normal-person SSA.
+    UpsilonValue* defaultOne = root->appendNew<UpsilonValue>(
+        proc, Origin(), root->appendNew<Const32Value>(proc, Origin(), 1));
+    root->appendNew<Value>(proc, Jump, Origin());
+    root->setSuccessors(loopHeader);
+    
+    Value* index = loopHeader->appendNew<Value>(proc, Phi, Int32, Origin());
+    initialIndex->setPhi(index);
+    
+    // if (array[index])
+    loopHeader->appendNew<Value>(
+        proc, Branch, Origin(),
+        loopHeader->appendNew<MemoryValue>(
+            proc, Load, Int32, Origin(),
+            loopHeader->appendNew<Value>(
+                proc, Add, Origin(),
+                loopHeader->appendNew<ConstPtrValue>(proc, Origin(), &array),
+                loopHeader->appendNew<Value>(
+                    proc, Mul, Origin(),
+                    loopHeader->appendNew<Value>(proc, ZExt32, Origin(), index),
+                    loopHeader->appendNew<ConstPtrValue>(proc, Origin(), sizeof(int))))));
+    loopHeader->setSuccessors(loopCall, loopFooter);
+    
+    Value* functionCall = func(loopCall, index);
+    UpsilonValue* oneFromFunction = loopCall->appendNew<UpsilonValue>(proc, Origin(), functionCall);
+    loopCall->appendNew<Value>(proc, Jump, Origin());
+    loopCall->setSuccessors(loopFooter);
+    
+    Value* one = loopFooter->appendNew<Value>(proc, Phi, Int32, Origin());
+    defaultOne->setPhi(one);
+    oneFromFunction->setPhi(one);
+    Value* nextIndex = loopFooter->appendNew<Value>(proc, Add, Origin(), index, one);
+    UpsilonValue* loopIndex = loopFooter->appendNew<UpsilonValue>(proc, Origin(), nextIndex);
+    loopIndex->setPhi(index);
+    loopFooter->appendNew<Value>(
+        proc, Branch, Origin(),
+        loopFooter->appendNew<Value>(
+            proc, LessThan, Origin(), nextIndex,
+            loopFooter->appendNew<Const32Value>(proc, Origin(), 100)));
+    loopFooter->setSuccessors(loopHeader, end);
+    
+    end->appendNew<Value>(proc, Return, Origin());
+}
+
+static int oneFunction(int* callCount)
+{
+    (*callCount)++;
+    return 1;
+}
+
+static void noOpFunction()
+{
+}
+
+void testLICMPure()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMPureSideExits()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.exitsSideways = true;
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMPureWritesPinned()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writesPinned = true;
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMPureWrites()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writes = HeapRange(63479);
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMReadsLocalState()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.readsLocalState = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u); // We'll fail to hoist because the loop has Upsilons.
+}
+
+void testLICMReadsPinned()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.readsPinned = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMReads()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.reads = HeapRange::top();
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMPureNotBackwardsDominant()
+{
+    Procedure proc;
+    auto array = makeArrayForLoops();
+    generateLoopNotBackwardsDominant(
+        proc, array,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMPureFoiledByChild()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value* index) -> Value* {
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+                index);
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMPureNotBackwardsDominantFoiledByChild()
+{
+    Procedure proc;
+    auto array = makeArrayForLoops();
+    generateLoopNotBackwardsDominant(
+        proc, array,
+        [&] (BasicBlock* loop, Value* index) -> Value* {
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), Effects::none(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+                index);
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 50u);
+}
+
+void testLICMExitsSideways()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.exitsSideways = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMWritesLocalState()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writesLocalState = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMWrites()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writes = HeapRange(666);
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMFence()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.fence = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMWritesPinned()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writesPinned = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMControlDependent()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.controlDependent = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMControlDependentNotBackwardsDominant()
+{
+    Procedure proc;
+    auto array = makeArrayForLoops();
+    generateLoopNotBackwardsDominant(
+        proc, array,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.controlDependent = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 50u);
+}
+
+void testLICMControlDependentSideExits()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.exitsSideways = true;
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+            
+            effects = Effects::none();
+            effects.controlDependent = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMReadsPinnedWritesPinned()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writesPinned = true;
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+            
+            effects = Effects::none();
+            effects.readsPinned = true;
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMReadsWritesDifferentHeaps()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writes = HeapRange(6436);
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+            
+            effects = Effects::none();
+            effects.reads = HeapRange(4886);
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 1u);
+}
+
+void testLICMReadsWritesOverlappingHeaps()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            Effects effects = Effects::none();
+            effects.writes = HeapRange(6436, 74458);
+            loop->appendNew<CCallValue>(
+                proc, Void, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(noOpFunction)));
+            
+            effects = Effects::none();
+            effects.reads = HeapRange(48864, 78239);
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(), effects,
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
+void testLICMDefaultCall()
+{
+    Procedure proc;
+    generateLoop(
+        proc,
+        [&] (BasicBlock* loop, Value*) -> Value* {
+            return loop->appendNew<CCallValue>(
+                proc, Int32, Origin(),
+                loop->appendNew<ConstPtrValue>(proc, Origin(), bitwise_cast<void*>(oneFunction)),
+                loop->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0));
+        });
+    
+    unsigned callCount = 0;
+    compileAndRun<void>(proc, &callCount);
+    CHECK_EQ(callCount, 100u);
+}
+
 template<typename T>
 void testAtomicWeakCAS()
 {
@@ -17128,7 +17681,29 @@ void run(const char* filter)
     RUN(testLoadBaseIndexShift2());
     RUN(testLoadBaseIndexShift32());
     RUN(testOptimizeMaterialization());
-    
+    RUN(testLICMPure());
+    RUN(testLICMPureSideExits());
+    RUN(testLICMPureWritesPinned());
+    RUN(testLICMPureWrites());
+    RUN(testLICMReadsLocalState());
+    RUN(testLICMReadsPinned());
+    RUN(testLICMReads());
+    RUN(testLICMPureNotBackwardsDominant());
+    RUN(testLICMPureFoiledByChild());
+    RUN(testLICMPureNotBackwardsDominantFoiledByChild());
+    RUN(testLICMExitsSideways());
+    RUN(testLICMWritesLocalState());
+    RUN(testLICMWrites());
+    RUN(testLICMWritesPinned());
+    RUN(testLICMFence());
+    RUN(testLICMControlDependent());
+    RUN(testLICMControlDependentNotBackwardsDominant());
+    RUN(testLICMControlDependentSideExits());
+    RUN(testLICMReadsPinnedWritesPinned());
+    RUN(testLICMReadsWritesDifferentHeaps());
+    RUN(testLICMReadsWritesOverlappingHeaps());
+    RUN(testLICMDefaultCall());
+
     RUN(testAtomicWeakCAS<int8_t>());
     RUN(testAtomicWeakCAS<int16_t>());
     RUN(testAtomicWeakCAS<int32_t>());
@@ -17181,7 +17756,7 @@ void run(const char* filter)
     RUN(testFloatEqualOrUnorderedFolding());
     RUN(testFloatEqualOrUnorderedFoldingNaN());
     RUN(testFloatEqualOrUnorderedDontFold());
-
+    
     RUN(testShuffleDoesntTrashCalleeSaves());
 
     if (isX86()) {
index cd23d53..18773d0 100644 (file)
@@ -229,9 +229,7 @@ struct BasicBlock : RefCounted<BasicBlock> {
     float executionCount;
     
     // These fields are reserved for NaturalLoops.
-    static const unsigned numberOfInnerMostLoopIndices = 2;
-    unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
-
+    
     struct SSAData {
         WTF_MAKE_FAST_ALLOCATED;
     public:
index 3a1d778..e9ed9e8 100644 (file)
@@ -59,7 +59,7 @@ public:
     unsigned index(Node node) const { return node->index; }
     Node node(unsigned index) const { return m_graph.block(index); }
     unsigned numNodes() const { return m_graph.numBlocks(); }
-
+    
     PointerDump<BasicBlock> dump(Node node) const { return pointerDump(node); }
 
     void dump(PrintStream& out) const
diff --git a/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp b/Source/JavaScriptCore/dfg/DFGNaturalLoops.cpp
deleted file mode 100644 (file)
index 351e665..0000000
+++ /dev/null
@@ -1,219 +0,0 @@
-/*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
- */
-
-#include "config.h"
-#include "DFGNaturalLoops.h"
-
-#if ENABLE(DFG_JIT)
-
-#include "DFGDominators.h"
-#include "DFGGraph.h"
-#include "JSCInlines.h"
-#include <wtf/CommaPrinter.h>
-
-namespace JSC { namespace DFG {
-
-void NaturalLoop::dump(PrintStream& out) const
-{
-    out.print("[Header: ", *header(), ", Body:");
-    for (unsigned i = 0; i < m_body.size(); ++i)
-        out.print(" ", *m_body[i]);
-    out.print("]");
-}
-
-NaturalLoops::NaturalLoops(Graph& graph)
-{
-    ASSERT(graph.m_dominators);
-
-    // Implement the classic dominator-based natural loop finder. The first
-    // step is to find all control flow edges A -> B where B dominates A.
-    // Then B is a loop header and A is a backward branching block. We will
-    // then accumulate, for each loop header, multiple backward branching
-    // blocks. Then we backwards graph search from the backward branching
-    // blocks to their loop headers, which gives us all of the blocks in the
-    // loop body.
-    
-    static const bool verbose = false;
-    
-    if (verbose) {
-        dataLog("Dominators:\n");
-        graph.m_dominators->dump(WTF::dataFile());
-    }
-    
-    m_loops.shrink(0);
-    
-    for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
-        BasicBlock* block = graph.block(blockIndex);
-        if (!block)
-            continue;
-        
-        for (unsigned i = block->numSuccessors(); i--;) {
-            BasicBlock* successor = block->successor(i);
-            if (!graph.m_dominators->dominates(successor, block))
-                continue;
-            bool found = false;
-            for (unsigned j = m_loops.size(); j--;) {
-                if (m_loops[j].header() == successor) {
-                    m_loops[j].addBlock(block);
-                    found = true;
-                    break;
-                }
-            }
-            if (found)
-                continue;
-            NaturalLoop loop(successor, m_loops.size());
-            loop.addBlock(block);
-            m_loops.append(loop);
-        }
-    }
-    
-    if (verbose)
-        dataLog("After bootstrap: ", *this, "\n");
-    
-    FastBitVector seenBlocks;
-    Vector<BasicBlock*, 4> blockWorklist;
-    seenBlocks.resize(graph.numBlocks());
-    
-    for (unsigned i = m_loops.size(); i--;) {
-        NaturalLoop& loop = m_loops[i];
-        
-        seenBlocks.clearAll();
-        ASSERT(blockWorklist.isEmpty());
-        
-        if (verbose)
-            dataLog("Dealing with loop ", loop, "\n");
-        
-        for (unsigned j = loop.size(); j--;) {
-            seenBlocks[loop[j]->index] = true;
-            blockWorklist.append(loop[j]);
-        }
-        
-        while (!blockWorklist.isEmpty()) {
-            BasicBlock* block = blockWorklist.takeLast();
-            
-            if (verbose)
-                dataLog("    Dealing with ", *block, "\n");
-            
-            if (block == loop.header())
-                continue;
-            
-            for (unsigned j = block->predecessors.size(); j--;) {
-                BasicBlock* predecessor = block->predecessors[j];
-                if (seenBlocks[predecessor->index])
-                    continue;
-                
-                loop.addBlock(predecessor);
-                blockWorklist.append(predecessor);
-                seenBlocks[predecessor->index] = true;
-            }
-        }
-    }
-
-    // Figure out reverse mapping from blocks to loops.
-    for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
-        BasicBlock* block = graph.block(blockIndex);
-        if (!block)
-            continue;
-        for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
-            block->innerMostLoopIndices[i] = UINT_MAX;
-    }
-    for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
-        NaturalLoop& loop = m_loops[loopIndex];
-        
-        for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
-            BasicBlock* block = loop[blockIndexInLoop];
-            
-            for (unsigned i = 0; i < BasicBlock::numberOfInnerMostLoopIndices; ++i) {
-                unsigned thisIndex = block->innerMostLoopIndices[i];
-                if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
-                    insertIntoBoundedVector(
-                        block->innerMostLoopIndices, BasicBlock::numberOfInnerMostLoopIndices,
-                        loopIndex, i);
-                    break;
-                }
-            }
-        }
-    }
-    
-    // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
-    // this to figure out loop parenting.
-    for (unsigned i = m_loops.size(); i--;) {
-        NaturalLoop& loop = m_loops[i];
-        RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
-        
-        loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
-    }
-    
-    if (validationEnabled()) {
-        // Do some self-verification that we've done some of this correctly.
-        
-        for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
-            BasicBlock* block = graph.block(blockIndex);
-            if (!block)
-                continue;
-            
-            Vector<const NaturalLoop*> simpleLoopsOf;
-            
-            for (unsigned i = m_loops.size(); i--;) {
-                if (m_loops[i].contains(block))
-                    simpleLoopsOf.append(&m_loops[i]);
-            }
-            
-            Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
-            
-            std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
-            std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
-            
-            RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
-        }
-    }
-    
-    if (verbose)
-        dataLog("Results: ", *this, "\n");
-}
-
-NaturalLoops::~NaturalLoops() { }
-
-Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
-{
-    Vector<const NaturalLoop*> result;
-    for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
-        result.append(loop);
-    return result;
-}
-
-void NaturalLoops::dump(PrintStream& out) const
-{
-    out.print("NaturalLoops:{");
-    CommaPrinter comma;
-    for (unsigned i = 0; i < m_loops.size(); ++i)
-        out.print(comma, m_loops[i]);
-    out.print("}");
-}
-
-} } // namespace JSC::DFG
-
-#endif // ENABLE(DFG_JIT)
-
index 9f9a733..f7c532a 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 #if ENABLE(DFG_JIT)
 
-#include "DFGBasicBlock.h"
+#include "DFGDominators.h"
 #include <wtf/FastMalloc.h>
+#include <wtf/NaturalLoops.h>
 #include <wtf/Noncopyable.h>
 
 namespace JSC { namespace DFG {
 
-class NaturalLoops;
+typedef WTF::NaturalLoop<CFG> NaturalLoop;
 
-class NaturalLoop {
-public:
-    NaturalLoop()
-        : m_header(0)
-        , m_outerLoopIndex(UINT_MAX)
-    {
-    }
-    
-    NaturalLoop(BasicBlock* header, unsigned index)
-        : m_header(header)
-        , m_outerLoopIndex(UINT_MAX)
-        , m_index(index)
-    {
-    }
-    
-    BasicBlock* header() const { return m_header; }
-    
-    unsigned size() const { return m_body.size(); }
-    BasicBlock* at(unsigned i) const { return m_body[i]; }
-    BasicBlock* operator[](unsigned i) const { return at(i); }
-
-    // This is the slower, but simpler, way of asking if a block belongs to
-    // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
-    // tries to be O(loop depth) rather than O(loop size). Loop depth is
-    // almost always smaller than loop size. A *lot* smaller.
-    bool contains(BasicBlock* block) const
-    {
-        for (unsigned i = m_body.size(); i--;) {
-            if (m_body[i] == block)
-                return true;
-        }
-        ASSERT(block != header()); // Header should be contained.
-        return false;
-    }
-
-    // The index of this loop in NaturalLoops.
-    unsigned index() const { return m_index; }
-    
-    bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
-    
-    void dump(PrintStream&) const;
-private:
-    friend class NaturalLoops;
-    
-    void addBlock(BasicBlock* block) { m_body.append(block); }
-    
-    BasicBlock* m_header;
-    Vector<BasicBlock*, 4> m_body;
-    unsigned m_outerLoopIndex;
-    unsigned m_index;
-};
-
-class NaturalLoops {
+class NaturalLoops : public WTF::NaturalLoops<CFG> {
     WTF_MAKE_NONCOPYABLE(NaturalLoops);
     WTF_MAKE_FAST_ALLOCATED;
 public:
-    NaturalLoops(Graph&);
-    ~NaturalLoops();
-    
-    unsigned numLoops() const
-    {
-        return m_loops.size();
-    }
-    const NaturalLoop& loop(unsigned i) const
-    {
-        return m_loops[i];
-    }
-    
-    // Return either null if the block isn't a loop header, or the
-    // loop it belongs to.
-    const NaturalLoop* headerOf(BasicBlock* block) const
-    {
-        const NaturalLoop* loop = innerMostLoopOf(block);
-        if (!loop)
-            return 0;
-        if (loop->header() == block)
-            return loop;
-        if (!ASSERT_DISABLED) {
-            for (; loop; loop = innerMostOuterLoop(*loop))
-                ASSERT(loop->header() != block);
-        }
-        return 0;
-    }
-    
-    const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
-    {
-        unsigned index = block->innerMostLoopIndices[0];
-        if (index == UINT_MAX)
-            return 0;
-        return &m_loops[index];
-    }
-    
-    const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
-    {
-        if (loop.m_outerLoopIndex == UINT_MAX)
-            return 0;
-        return &m_loops[loop.m_outerLoopIndex];
-    }
-    
-    bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
+    NaturalLoops(Graph& graph)
+        : WTF::NaturalLoops<CFG>(*graph.m_cfg, graph.ensureDominators(), validationEnabled())
     {
-        // It's faster to do this test using the loop itself, if it's small.
-        if (candidateLoop.size() < 4)
-            return candidateLoop.contains(block);
-        
-        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
-            if (loop == &candidateLoop)
-                return true;
-        }
-        return false;
     }
-    
-    unsigned loopDepth(BasicBlock* block) const
-    {
-        unsigned depth = 0;
-        for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
-            depth++;
-        return depth;
-    }
-    
-    // Return the indices of all loops this belongs to.
-    Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
-
-    void dump(PrintStream&) const;
-private:
-    // If we ever had a scalability problem in our natural loop finder, we could
-    // use some HashMap's here. But it just feels a heck of a lot less convenient.
-    Vector<NaturalLoop, 4> m_loops;
 };
 
 } } // namespace JSC::DFG
index 091576a..33b0263 100644 (file)
@@ -1,3 +1,46 @@
+2017-07-23  Filip Pizlo  <fpizlo@apple.com>
+
+        B3 should do LICM
+        https://bugs.webkit.org/show_bug.cgi?id=174750
+
+        Reviewed by Keith Miller and Saam Barati.
+        
+        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):
+
 2017-07-23  Michael Catanzaro  <mcatanzaro@igalia.com>
 
         Implement FALLTHROUGH attribute for C with GCC
index 95c908e..d861671 100644 (file)
                0F43D8F01DB5ADDC00108FB6 /* AutomaticThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AutomaticThread.h; sourceTree = "<group>"; };
                0F4570421BE5B58F0062A629 /* Dominators.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Dominators.h; sourceTree = "<group>"; };
                0F4570441BE834410062A629 /* BubbleSort.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BubbleSort.h; sourceTree = "<group>"; };
+               0F5BF1651F2317830029D91D /* NaturalLoops.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = NaturalLoops.h; sourceTree = "<group>"; };
                0F60F32D1DFCBD1B00416D6C /* LockedPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LockedPrintStream.cpp; sourceTree = "<group>"; };
                0F60F32E1DFCBD1B00416D6C /* LockedPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LockedPrintStream.h; sourceTree = "<group>"; };
                0F66B2801DC97BAB004A1D3F /* ClockType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ClockType.cpp; sourceTree = "<group>"; };
                                0F66B2821DC97BAB004A1D3F /* MonotonicTime.cpp */,
                                0F66B2831DC97BAB004A1D3F /* MonotonicTime.h */,
                                FE8225301B2A1E5B00BA68FD /* NakedPtr.h */,
+                               0F5BF1651F2317830029D91D /* NaturalLoops.h */,
                                1A3F6BE6174ADA2100B2EEA7 /* NeverDestroyed.h */,
                                0F0D85B317234CB100338210 /* NoLock.h */,
                                A8A472D0151A825B004123FF /* Noncopyable.h */,
index abd66cc..e15d45c 100644 (file)
@@ -79,6 +79,7 @@ set(WTF_HEADERS
     MessageQueue.h
     MetaAllocator.h
     MetaAllocatorHandle.h
+    NaturalLoops.h
     MonotonicTime.h
     Noncopyable.h
     NumberOfCores.h
index e7ab52f..7c760dc 100644 (file)
@@ -26,6 +26,7 @@
 #ifndef WTFDominators_h
 #define WTFDominators_h
 
+#include <wtf/CommaPrinter.h>
 #include <wtf/FastBitVector.h>
 #include <wtf/GraphNodeWorklist.h>
 
diff --git a/Source/WTF/wtf/NaturalLoops.h b/Source/WTF/wtf/NaturalLoops.h
new file mode 100644 (file)
index 0000000..dff6685
--- /dev/null
@@ -0,0 +1,357 @@
+/*
+ * Copyright (C) 2013-2017 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+#pragma once
+
+#include <wtf/Dominators.h>
+
+namespace WTF {
+
+template<typename Graph>
+class NaturalLoops;
+
+template<typename Graph>
+class NaturalLoop {
+public:
+    NaturalLoop()
+        : m_graph(nullptr)
+        , m_header(nullptr)
+        , m_outerLoopIndex(UINT_MAX)
+    {
+    }
+    
+    NaturalLoop(Graph& graph, typename Graph::Node header, unsigned index)
+        : m_graph(&graph)
+        , m_header(header)
+        , m_outerLoopIndex(UINT_MAX)
+        , m_index(index)
+    {
+    }
+    
+    Graph* graph() const { return m_graph; }
+    
+    typename Graph::Node header() const { return m_header; }
+    
+    unsigned size() const { return m_body.size(); }
+    typename Graph::Node at(unsigned i) const { return m_body[i]; }
+    typename Graph::Node operator[](unsigned i) const { return at(i); }
+
+    // This is the slower, but simpler, way of asking if a block belongs to
+    // a natural loop. It's faster to call NaturalLoops::belongsTo(), which
+    // tries to be O(loop depth) rather than O(loop size). Loop depth is
+    // almost always smaller than loop size. A *lot* smaller.
+    bool contains(typename Graph::Node block) const
+    {
+        for (unsigned i = m_body.size(); i--;) {
+            if (m_body[i] == block)
+                return true;
+        }
+        ASSERT(block != header()); // Header should be contained.
+        return false;
+    }
+
+    // The index of this loop in NaturalLoops.
+    unsigned index() const { return m_index; }
+    
+    bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; }
+    
+    void dump(PrintStream& out) const
+    {
+        if (!m_graph) {
+            out.print("<null>");
+            return;
+        }
+        
+        out.print("[Header: ", m_graph->dump(header()), ", Body:");
+        for (unsigned i = 0; i < m_body.size(); ++i)
+            out.print(" ", m_graph->dump(m_body[i]));
+        out.print("]");
+    }
+    
+private:
+    template<typename>
+    friend class NaturalLoops;
+    
+    void addBlock(typename Graph::Node block) { m_body.append(block); }
+
+    Graph* m_graph;
+    typename Graph::Node m_header;
+    Vector<typename Graph::Node, 4> m_body;
+    unsigned m_outerLoopIndex;
+    unsigned m_index;
+};
+
+template<typename Graph>
+class NaturalLoops {
+public:
+    typedef std::array<unsigned, 2> InnerMostLoopIndices;
+
+    NaturalLoops(Graph& graph, Dominators<Graph>& dominators, bool selfCheck = false)
+        : m_graph(graph)
+        , m_innerMostLoopIndices(graph.template newMap<InnerMostLoopIndices>())
+    {
+        // Implement the classic dominator-based natural loop finder. The first
+        // step is to find all control flow edges A -> B where B dominates A.
+        // Then B is a loop header and A is a backward branching block. We will
+        // then accumulate, for each loop header, multiple backward branching
+        // blocks. Then we backwards graph search from the backward branching
+        // blocks to their loop headers, which gives us all of the blocks in the
+        // loop body.
+    
+        static const bool verbose = false;
+    
+        if (verbose) {
+            dataLog("Dominators:\n");
+            dominators.dump(WTF::dataFile());
+        }
+    
+        m_loops.shrink(0);
+    
+        for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
+            typename Graph::Node block = graph.node(blockIndex);
+            if (!block)
+                continue;
+        
+            for (unsigned i = graph.successors(block).size(); i--;) {
+                typename Graph::Node successor = graph.successors(block)[i];
+                if (!dominators.dominates(successor, block))
+                    continue;
+                bool found = false;
+                for (unsigned j = m_loops.size(); j--;) {
+                    if (m_loops[j].header() == successor) {
+                        m_loops[j].addBlock(block);
+                        found = true;
+                        break;
+                    }
+                }
+                if (found)
+                    continue;
+                NaturalLoop<Graph> loop(graph, successor, m_loops.size());
+                loop.addBlock(block);
+                m_loops.append(loop);
+            }
+        }
+    
+        if (verbose)
+            dataLog("After bootstrap: ", *this, "\n");
+    
+        FastBitVector seenBlocks;
+        Vector<typename Graph::Node, 4> blockWorklist;
+        seenBlocks.resize(graph.numNodes());
+    
+        for (unsigned i = m_loops.size(); i--;) {
+            NaturalLoop<Graph>& loop = m_loops[i];
+        
+            seenBlocks.clearAll();
+            ASSERT(blockWorklist.isEmpty());
+        
+            if (verbose)
+                dataLog("Dealing with loop ", loop, "\n");
+        
+            for (unsigned j = loop.size(); j--;) {
+                seenBlocks[graph.index(loop[j])] = true;
+                blockWorklist.append(loop[j]);
+            }
+        
+            while (!blockWorklist.isEmpty()) {
+                typename Graph::Node block = blockWorklist.takeLast();
+            
+                if (verbose)
+                    dataLog("    Dealing with ", graph.dump(block), "\n");
+            
+                if (block == loop.header())
+                    continue;
+            
+                for (unsigned j = graph.predecessors(block).size(); j--;) {
+                    typename Graph::Node predecessor = graph.predecessors(block)[j];
+                    if (seenBlocks[graph.index(predecessor)])
+                        continue;
+                
+                    loop.addBlock(predecessor);
+                    blockWorklist.append(predecessor);
+                    seenBlocks[graph.index(predecessor)] = true;
+                }
+            }
+        }
+
+        // Figure out reverse mapping from blocks to loops.
+        for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
+            typename Graph::Node block = graph.node(blockIndex);
+            if (!block)
+                continue;
+            for (unsigned i = std::tuple_size<InnerMostLoopIndices>::value; i--;)
+                m_innerMostLoopIndices[block][i] = UINT_MAX;
+        }
+        for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
+            NaturalLoop<Graph>& loop = m_loops[loopIndex];
+        
+            for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
+                typename Graph::Node block = loop[blockIndexInLoop];
+            
+                for (unsigned i = 0; i < std::tuple_size<InnerMostLoopIndices>::value; ++i) {
+                    unsigned thisIndex = m_innerMostLoopIndices[block][i];
+                    if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
+                        insertIntoBoundedVector(
+                            m_innerMostLoopIndices[block], std::tuple_size<InnerMostLoopIndices>::value,
+                            loopIndex, i);
+                        break;
+                    }
+                }
+            }
+        }
+    
+        // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
+        // this to figure out loop parenting.
+        for (unsigned i = m_loops.size(); i--;) {
+            NaturalLoop<Graph>& loop = m_loops[i];
+            RELEASE_ASSERT(m_innerMostLoopIndices[loop.header()][0] == i);
+        
+            loop.m_outerLoopIndex = m_innerMostLoopIndices[loop.header()][1];
+        }
+    
+        if (selfCheck) {
+            // Do some self-verification that we've done some of this correctly.
+        
+            for (unsigned blockIndex = graph.numNodes(); blockIndex--;) {
+                typename Graph::Node block = graph.node(blockIndex);
+                if (!block)
+                    continue;
+            
+                Vector<const NaturalLoop<Graph>*> simpleLoopsOf;
+            
+                for (unsigned i = m_loops.size(); i--;) {
+                    if (m_loops[i].contains(block))
+                        simpleLoopsOf.append(&m_loops[i]);
+                }
+            
+                Vector<const NaturalLoop<Graph>*> fancyLoopsOf = loopsOf(block);
+            
+                std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
+                std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
+            
+                RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
+            }
+        }
+    
+        if (verbose)
+            dataLog("Results: ", *this, "\n");
+    }
+    
+    Graph& graph() { return m_graph; }
+    
+    unsigned numLoops() const
+    {
+        return m_loops.size();
+    }
+    const NaturalLoop<Graph>& loop(unsigned i) const
+    {
+        return m_loops[i];
+    }
+    
+    // Return either null if the block isn't a loop header, or the
+    // loop it belongs to.
+    const NaturalLoop<Graph>* headerOf(typename Graph::Node block) const
+    {
+        const NaturalLoop<Graph>* loop = innerMostLoopOf(block);
+        if (!loop)
+            return nullptr;
+        if (loop->header() == block)
+            return loop;
+        if (!ASSERT_DISABLED) {
+            for (; loop; loop = innerMostOuterLoop(*loop))
+                ASSERT(loop->header() != block);
+        }
+        return nullptr;
+    }
+    
+    const NaturalLoop<Graph>* innerMostLoopOf(typename Graph::Node block) const
+    {
+        unsigned index = m_innerMostLoopIndices[block][0];
+        if (index == UINT_MAX)
+            return nullptr;
+        return &m_loops[index];
+    }
+    
+    const NaturalLoop<Graph>* innerMostOuterLoop(const NaturalLoop<Graph>& loop) const
+    {
+        if (loop.m_outerLoopIndex == UINT_MAX)
+            return nullptr;
+        return &m_loops[loop.m_outerLoopIndex];
+    }
+    
+    bool belongsTo(typename Graph::Node block, const NaturalLoop<Graph>& candidateLoop) const
+    {
+        // It's faster to do this test using the loop itself, if it's small.
+        if (candidateLoop.size() < 4)
+            return candidateLoop.contains(block);
+        
+        for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
+            if (loop == &candidateLoop)
+                return true;
+        }
+        return false;
+    }
+    
+    unsigned loopDepth(typename Graph::Node block) const
+    {
+        unsigned depth = 0;
+        for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
+            depth++;
+        return depth;
+    }
+    
+    // Return all loops this belongs to. The first entry in the vector is the innermost loop. The last is the
+    // outermost loop.
+    Vector<const NaturalLoop<Graph>*> loopsOf(typename Graph::Node block) const
+    {
+        Vector<const NaturalLoop<Graph>*> result;
+        for (const NaturalLoop<Graph>* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
+            result.append(loop);
+        return result;
+    }
+
+    void dump(PrintStream& out) const
+    {
+        out.print("NaturalLoops:{");
+        CommaPrinter comma;
+        for (unsigned i = 0; i < m_loops.size(); ++i)
+            out.print(comma, m_loops[i]);
+        out.print("}");
+    }
+    
+private:
+    Graph& m_graph;
+    
+    // If we ever had a scalability problem in our natural loop finder, we could
+    // use some HashMap's here. But it just feels a heck of a lot less convenient.
+    Vector<NaturalLoop<Graph>, 4> m_loops;
+    
+    typename Graph::template Map<InnerMostLoopIndices> m_innerMostLoopIndices;
+};
+
+} // namespace WTF
+
+using WTF::NaturalLoop;
+using WTF::NaturalLoops;
index 52125df..9db10fc 100644 (file)
@@ -56,6 +56,8 @@ public:
     typedef RangeType Range;
     typedef typename Range::Type Type;
 
+    typedef Vector<Range, 8> VectorType;
+    
     RangeSet()
     {
     }
@@ -125,8 +127,23 @@ public:
     {
         out.print("{", listDump(m_ranges), ", isCompact = ", m_isCompact, "}");
     }
+    
+    typename VectorType::const_iterator begin() const
+    {
+        return m_ranges.begin();
+    }
+    
+    typename VectorType::const_iterator end() const
+    {
+        return m_ranges.end();
+    }
+    
+    void addAll(const RangeSet& other)
+    {
+        for (Range range : other)
+            add(range);
+    }
 
-private:
     void compact()
     {
         if (m_isCompact)
@@ -164,6 +181,7 @@ private:
         m_isCompact = true;
     }
     
+private:
     static bool overlapsNonEmpty(const Range& a, const Range& b)
     {
         return nonEmptyRangesOverlap(a.begin(), a.end(), b.begin(), b.end());
@@ -187,7 +205,7 @@ private:
         return UINT_MAX;
     }
     
-    Vector<Range, 8> m_ranges;
+    VectorType m_ranges;
     bool m_isCompact { true };
 };