Diff
Modified: trunk/Source/_javascript_Core/CMakeLists.txt (219897 => 219898)
--- trunk/Source/_javascript_Core/CMakeLists.txt 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/CMakeLists.txt 2017-07-26 01:58:36 UTC (rev 219898)
@@ -143,11 +143,13 @@
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 @@
dfg/DFGMinifiedNode.cpp
dfg/DFGMovHintRemovalPhase.cpp
dfg/DFGMultiGetByOffsetData.cpp
- dfg/DFGNaturalLoops.cpp
dfg/DFGNode.cpp
dfg/DFGNodeAbstractValuePair.cpp
dfg/DFGNodeFlags.cpp
Modified: trunk/Source/_javascript_Core/ChangeLog (219897 => 219898)
--- trunk/Source/_javascript_Core/ChangeLog 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-07-26 01:58:36 UTC (rev 219898)
@@ -1,3 +1,105 @@
+2017-07-23 Filip Pizlo <fpi...@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:
+ * _javascript_Core.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 <fpi...@apple.com>
GC should be fine with trading blocks between destructor and non-destructor blocks
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (219897 => 219898)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2017-07-26 01:58:36 UTC (rev 219898)
@@ -464,6 +464,13 @@
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 */; };
@@ -1950,7 +1957,6 @@
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 */; };
@@ -3040,6 +3046,13 @@
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>"; };
@@ -4576,7 +4589,6 @@
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>"; };
@@ -5481,6 +5493,8 @@
0FEC84B51BDACDAC0080FF74 /* B3ArgumentRegValue.h */,
0F2C63B31E6343E800C13839 /* B3AtomicValue.cpp */,
0F2C63B41E6343E800C13839 /* B3AtomicValue.h */,
+ 0F5BF1661F23A0980029D91D /* B3BackwardsCFG.h */,
+ 0F5BF16A1F23A0C10029D91D /* B3BackwardsDominators.h */,
0F2C63AB1E60AE3C00C13839 /* B3Bank.cpp */,
0F2C63AC1E60AE3C00C13839 /* B3Bank.h */,
0FEC84B61BDACDAC0080FF74 /* B3BasicBlock.cpp */,
@@ -5532,6 +5546,8 @@
0FEC85BE1BE167A00080FF74 /* B3Effects.h */,
0F725CA31C503DED00AD943A /* B3EliminateCommonSubexpressions.cpp */,
0F725CA41C503DED00AD943A /* B3EliminateCommonSubexpressions.h */,
+ 0F5BF16E1F23A5A10029D91D /* B3EnsureLoopPreHeaders.cpp */,
+ 0F5BF16F1F23A5A10029D91D /* B3EnsureLoopPreHeaders.h */,
0F6971E81D92F42100BA02A5 /* B3FenceValue.cpp */,
0F6971E91D92F42100BA02A5 /* B3FenceValue.h */,
0F6B8AE01C4EFE1700969052 /* B3FixSSA.cpp */,
@@ -5546,6 +5562,8 @@
0F2C63B51E6343E800C13839 /* B3GenericBlockInsertionSet.h */,
0FEC84D01BDACDAC0080FF74 /* B3GenericFrequentedBlock.h */,
0FEC85C01BE167A00080FF74 /* B3HeapRange.h */,
+ 0F5BF1611F2317120029D91D /* B3HoistLoopInvariantValues.cpp */,
+ 0F5BF1621F2317120029D91D /* B3HoistLoopInvariantValues.h */,
DC69B99A1D15F90F002E3C00 /* B3InferSwitches.cpp */,
DC69B99B1D15F90F002E3C00 /* B3InferSwitches.h */,
0FEC85B41BE1462F0080FF74 /* B3InsertionSet.cpp */,
@@ -5569,6 +5587,7 @@
0F338E031BF0276C0013C88F /* B3MoveConstants.cpp */,
0F338E041BF0276C0013C88F /* B3MoveConstants.h */,
0F2C63C11E664A5A00C13839 /* B3NativeTraits.h */,
+ 0F5BF1681F23A0AA0029D91D /* B3NaturalLoops.h */,
0F338E051BF0276C0013C88F /* B3OpaqueByproduct.h */,
0F338E061BF0276C0013C88F /* B3OpaqueByproducts.cpp */,
0F338E071BF0276C0013C88F /* B3OpaqueByproducts.h */,
@@ -7393,7 +7412,6 @@
0F8F14321ADF090100ED792C /* DFGMovHintRemovalPhase.h */,
0FF2CD591B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp */,
0FF2CD5A1B61A4F8004955A8 /* DFGMultiGetByOffsetData.h */,
- A737810A1799EA2E00817533 /* DFGNaturalLoops.cpp */,
A737810B1799EA2E00817533 /* DFGNaturalLoops.h */,
0FB4B51E16B62772003F696B /* DFGNode.cpp */,
86ECA3E9132DEF1C002B2AD7 /* DFGNode.h */,
@@ -8515,6 +8533,7 @@
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 */,
@@ -8699,6 +8718,7 @@
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 */,
@@ -8883,10 +8903,12 @@
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 */,
@@ -9190,6 +9212,7 @@
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 */,
@@ -10406,7 +10429,6 @@
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 */,
@@ -10768,6 +10790,7 @@
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 */,
@@ -10834,6 +10857,7 @@
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 */,
Added: trunk/Source/_javascript_Core/b3/B3BackwardsCFG.h (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3BackwardsCFG.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3BackwardsCFG.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
+
Added: trunk/Source/_javascript_Core/b3/B3BackwardsDominators.h (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3BackwardsDominators.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3BackwardsDominators.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
+
Modified: trunk/Source/_javascript_Core/b3/B3BasicBlock.cpp (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/B3BasicBlock.cpp 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/B3BasicBlock.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -57,7 +57,7 @@
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;
}
Modified: trunk/Source/_javascript_Core/b3/B3Effects.h (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/B3Effects.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/B3Effects.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -75,6 +75,9 @@
// 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;
Added: trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.cpp (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
+
Added: trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.h (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3EnsureLoopPreHeaders.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
Modified: trunk/Source/_javascript_Core/b3/B3Generate.cpp (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/B3Generate.cpp 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/B3Generate.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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 @@
if (procedure.optLevel() >= 2) {
reduceDoubleToFloat(procedure);
reduceStrength(procedure);
+ hoistLoopInvariantValues(procedure);
eliminateCommonSubexpressions(procedure);
inferSwitches(procedure);
duplicateTails(procedure);
Added: trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.cpp (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
+
Added: trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.h (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3HoistLoopInvariantValues.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
Added: trunk/Source/_javascript_Core/b3/B3NaturalLoops.h (0 => 219898)
--- trunk/Source/_javascript_Core/b3/B3NaturalLoops.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/B3NaturalLoops.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
+
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.cpp (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/B3Procedure.cpp 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -29,6 +29,8 @@
#if ENABLE(B3_JIT)
#include "AirCode.h"
+#include "B3BackwardsCFG.h"
+#include "B3BackwardsDominators.h"
#include "B3BasicBlockInlines.h"
#include "B3BasicBlockUtils.h"
#include "B3BlockWorklist.h"
@@ -35,6 +37,7 @@
#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::invalidateCFG()
{
m_dominators = nullptr;
+ m_naturalLoops = nullptr;
+ m_backwardsCFG = nullptr;
+ m_backwardsDominators = nullptr;
}
void Procedure::dump(PrintStream& out) const
@@ -291,6 +297,27 @@
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());
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.h (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/B3Procedure.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -48,10 +48,13 @@
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 @@
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 @@
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;
Modified: trunk/Source/_javascript_Core/b3/testb3.cpp (219897 => 219898)
--- trunk/Source/_javascript_Core/b3/testb3.cpp 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/b3/testb3.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -14592,6 +14592,559 @@
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 @@
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 @@
RUN(testFloatEqualOrUnorderedFolding());
RUN(testFloatEqualOrUnorderedFoldingNaN());
RUN(testFloatEqualOrUnorderedDontFold());
-
+
RUN(testShuffleDoesntTrashCalleeSaves());
if (isX86()) {
Modified: trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h (219897 => 219898)
--- trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/dfg/DFGBasicBlock.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -229,9 +229,7 @@
float executionCount;
// These fields are reserved for NaturalLoops.
- static const unsigned numberOfInnerMostLoopIndices = 2;
- unsigned innerMostLoopIndices[numberOfInnerMostLoopIndices];
-
+
struct SSAData {
WTF_MAKE_FAST_ALLOCATED;
public:
Modified: trunk/Source/_javascript_Core/dfg/DFGCFG.h (219897 => 219898)
--- trunk/Source/_javascript_Core/dfg/DFGCFG.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/dfg/DFGCFG.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -59,7 +59,7 @@
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
Deleted: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp (219897 => 219898)
--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.cpp 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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)
-
Modified: trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h (219897 => 219898)
--- trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/_javascript_Core/dfg/DFGNaturalLoops.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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
@@ -27,142 +27,23 @@
#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
+ NaturalLoops(Graph& graph)
+ : WTF::NaturalLoops<CFG>(*graph.m_cfg, graph.ensureDominators(), validationEnabled())
{
- 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
- {
- // 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
Modified: trunk/Source/WTF/ChangeLog (219897 => 219898)
--- trunk/Source/WTF/ChangeLog 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/WTF/ChangeLog 2017-07-26 01:58:36 UTC (rev 219898)
@@ -1,3 +1,46 @@
+2017-07-23 Filip Pizlo <fpi...@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 <mcatanz...@igalia.com>
Implement FALLTHROUGH attribute for C with GCC
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (219897 => 219898)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2017-07-26 01:58:36 UTC (rev 219898)
@@ -180,6 +180,7 @@
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>"; };
@@ -860,6 +861,7 @@
0F66B2821DC97BAB004A1D3F /* MonotonicTime.cpp */,
0F66B2831DC97BAB004A1D3F /* MonotonicTime.h */,
FE8225301B2A1E5B00BA68FD /* NakedPtr.h */,
+ 0F5BF1651F2317830029D91D /* NaturalLoops.h */,
1A3F6BE6174ADA2100B2EEA7 /* NeverDestroyed.h */,
0F0D85B317234CB100338210 /* NoLock.h */,
A8A472D0151A825B004123FF /* Noncopyable.h */,
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (219897 => 219898)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2017-07-26 01:58:36 UTC (rev 219898)
@@ -79,6 +79,7 @@
MessageQueue.h
MetaAllocator.h
MetaAllocatorHandle.h
+ NaturalLoops.h
MonotonicTime.h
Noncopyable.h
NumberOfCores.h
Modified: trunk/Source/WTF/wtf/Dominators.h (219897 => 219898)
--- trunk/Source/WTF/wtf/Dominators.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/WTF/wtf/Dominators.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -26,6 +26,7 @@
#ifndef WTFDominators_h
#define WTFDominators_h
+#include <wtf/CommaPrinter.h>
#include <wtf/FastBitVector.h>
#include <wtf/GraphNodeWorklist.h>
Added: trunk/Source/WTF/wtf/NaturalLoops.h (0 => 219898)
--- trunk/Source/WTF/wtf/NaturalLoops.h (rev 0)
+++ trunk/Source/WTF/wtf/NaturalLoops.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -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;
Modified: trunk/Source/WTF/wtf/RangeSet.h (219897 => 219898)
--- trunk/Source/WTF/wtf/RangeSet.h 2017-07-26 01:19:23 UTC (rev 219897)
+++ trunk/Source/WTF/wtf/RangeSet.h 2017-07-26 01:58:36 UTC (rev 219898)
@@ -56,6 +56,8 @@
typedef RangeType Range;
typedef typename Range::Type Type;
+ typedef Vector<Range, 8> VectorType;
+
RangeSet()
{
}
@@ -125,8 +127,23 @@
{
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 @@
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 @@
return UINT_MAX;
}
- Vector<Range, 8> m_ranges;
+ VectorType m_ranges;
bool m_isCompact { true };
};
