WebKit Bugzilla
New
Browse
Search+
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
[patch]
the patch
blah.patch (text/plain), 36.09 KB, created by
Filip Pizlo
on 2015-11-17 13:09:14 PST
(
hide
)
Description:
the patch
Filename:
MIME Type:
Creator:
Filip Pizlo
Created:
2015-11-17 13:09:14 PST
Size:
36.09 KB
patch
obsolete
>Index: Source/JavaScriptCore/ChangeLog >=================================================================== >--- Source/JavaScriptCore/ChangeLog (revision 192525) >+++ Source/JavaScriptCore/ChangeLog (working copy) >@@ -1,3 +1,58 @@ >+2015-11-17 Filip Pizlo <fpizlo@apple.com> >+ >+ Air should lay out code optimally >+ https://bugs.webkit.org/show_bug.cgi?id=150478 >+ >+ Reviewed by NOBODY (OOPS!). >+ >+ This adds a phase that optimizes code layout using something that's worked well for me in the past. >+ Basically, it just forces pre-ordering on the CFG, except that: >+ >+ - Blocks that are only reachable by Rare control flow are scheduled separately, all the way at the >+ end. >+ >+ - Successors of the same frequency class are pushed in ascending order of frequency, so that the most >+ frequent successor is scheduled immediately after. >+ >+ This also adds the requisite branch flipping, so that branches' taken successor is not the >+ fall-through block. We want the fall-through to be the not-taken successor if at all possible. >+ >+ * JavaScriptCore.xcodeproj/project.pbxproj: >+ * b3/B3BlockWorklist.h: >+ * b3/B3GenericFrequentedBlock.h: >+ (JSC::B3::GenericFrequentedBlock::frequency): >+ (JSC::B3::GenericFrequentedBlock::isRare): >+ (JSC::B3::GenericFrequentedBlock::dump): >+ * b3/B3Procedure.h: >+ * b3/air/AirArg.h: >+ (JSC::B3::Air::Arg::isDoubleCond): >+ (JSC::B3::Air::Arg::isCondition): >+ (JSC::B3::Air::Arg::isSpecial): >+ (JSC::B3::Air::Arg::asDoubleCondition): >+ (JSC::B3::Air::Arg::isInvertible): >+ (JSC::B3::Air::Arg::inverted): >+ * b3/air/AirBasicBlock.h: >+ (JSC::B3::Air::BasicBlock::index): >+ (JSC::B3::Air::BasicBlock::setIndex): >+ (JSC::B3::Air::BasicBlock::size): >+ (JSC::B3::Air::BasicBlock::begin): >+ (JSC::B3::Air::BasicBlock::containsPredecessor): >+ (JSC::B3::Air::BasicBlock::frequency): >+ * b3/air/AirBlockWorklist.h: Added. >+ * b3/air/AirCode.cpp: >+ (JSC::B3::Air::Code::findNextBlock): >+ * b3/air/AirCode.h: >+ (JSC::B3::Air::Code::proc): >+ (JSC::B3::Air::Code::at): >+ (JSC::B3::Air::Code::operator[]): >+ (JSC::B3::Air::Code::blockList): >+ * b3/air/AirGenerate.cpp: >+ (JSC::B3::Air::generate): >+ * b3/air/AirOpcode.opcodes: >+ * b3/air/AirOptimizeBlockOrder.cpp: Added. >+ (JSC::B3::Air::optimizeBlockOrder): >+ * b3/air/AirOptimizeBlockOrder.h: Added. >+ > 2015-11-17 Saam barati <sbarati@apple.com> > > FTLLazySlowPaths should be able to handle being passed the zero register as a location >Index: Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj >=================================================================== >--- Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (revision 192516) >+++ Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (working copy) >@@ -286,7 +286,7 @@ > 0F338DF61BE93D550013C88F /* B3ConstrainedValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */; }; > 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; }; > 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; }; >- 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; }; >+ 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; }; > 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */; }; > 0F338E0B1BF0276C0013C88F /* B3Compilation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */; }; > 0F338E0C1BF0276C0013C88F /* B3Compilation.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E001BF0276C0013C88F /* B3Compilation.h */; }; >@@ -300,12 +300,12 @@ > 0F338E141BF0276C0013C88F /* B3ValueKey.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E081BF0276C0013C88F /* B3ValueKey.cpp */; }; > 0F338E151BF0276C0013C88F /* B3ValueKey.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E091BF0276C0013C88F /* B3ValueKey.h */; }; > 0F338E161BF0276C0013C88F /* B3ValueKeyInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E0A1BF0276C0013C88F /* B3ValueKeyInlines.h */; }; >- 0F338E1B1BF286EA0013C88F /* B3BlockInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */; }; >+ 0F338E1B1BF286EA0013C88F /* B3BlockInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */; }; > 0F338E1C1BF286EA0013C88F /* B3BlockInsertionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E181BF286EA0013C88F /* B3BlockInsertionSet.h */; }; > 0F338E1D1BF286EA0013C88F /* B3LowerMacros.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E191BF286EA0013C88F /* B3LowerMacros.cpp */; }; > 0F338E1E1BF286EA0013C88F /* B3LowerMacros.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */; }; > 0F34B14916D42010001CDA5A /* DFGUseKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */; }; >- 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; }; >+ 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; }; > 0F38B01117CF078000B144D3 /* LLIntEntrypoint.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */; }; > 0F38B01217CF078300B144D3 /* LLIntEntrypoint.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F38B01017CF077F00B144D3 /* LLIntEntrypoint.h */; settings = {ATTRIBUTES = (Private, ); }; }; > 0F38B01717CFE75500B144D3 /* DFGCompilationKey.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B01317CFE75500B144D3 /* DFGCompilationKey.cpp */; }; >@@ -527,6 +527,9 @@ > 0FB17661196B8F9E0091052A /* DFGHeapLocation.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB1765D196B8F9E0091052A /* DFGHeapLocation.h */; }; > 0FB17662196B8F9E0091052A /* DFGPureValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB1765E196B8F9E0091052A /* DFGPureValue.cpp */; }; > 0FB17663196B8F9E0091052A /* DFGPureValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB1765F196B8F9E0091052A /* DFGPureValue.h */; }; >+ 0FB3878E1BFBC44D00E3AB1E /* AirBlockWorklist.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */; }; >+ 0FB3878F1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */; }; >+ 0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */; }; > 0FB438A319270B1D00E1FBC9 /* StructureSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB438A219270B1D00E1FBC9 /* StructureSet.cpp */; }; > 0FB4FB731BC843140025CA5A /* FTLLazySlowPath.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB4FB701BC843140025CA5A /* FTLLazySlowPath.cpp */; }; > 0FB4FB741BC843140025CA5A /* FTLLazySlowPath.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB4FB711BC843140025CA5A /* FTLLazySlowPath.h */; }; >@@ -2335,7 +2338,7 @@ > 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ConstrainedValue.h; path = b3/B3ConstrainedValue.h; sourceTree = "<group>"; }; > 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; }; > 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; }; >- 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; }; >+ 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; }; > 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirSimplifyCFG.h; path = b3/air/AirSimplifyCFG.h; sourceTree = "<group>"; }; > 0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3Compilation.cpp; path = b3/B3Compilation.cpp; sourceTree = "<group>"; }; > 0F338E001BF0276C0013C88F /* B3Compilation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Compilation.h; path = b3/B3Compilation.h; sourceTree = "<group>"; }; >@@ -2349,12 +2352,12 @@ > 0F338E081BF0276C0013C88F /* B3ValueKey.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ValueKey.cpp; path = b3/B3ValueKey.cpp; sourceTree = "<group>"; }; > 0F338E091BF0276C0013C88F /* B3ValueKey.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ValueKey.h; path = b3/B3ValueKey.h; sourceTree = "<group>"; }; > 0F338E0A1BF0276C0013C88F /* B3ValueKeyInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ValueKeyInlines.h; path = b3/B3ValueKeyInlines.h; sourceTree = "<group>"; }; >- 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3BlockInsertionSet.cpp; path = b3/B3BlockInsertionSet.cpp; sourceTree = "<group>"; }; >+ 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3BlockInsertionSet.cpp; path = b3/B3BlockInsertionSet.cpp; sourceTree = "<group>"; }; > 0F338E181BF286EA0013C88F /* B3BlockInsertionSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3BlockInsertionSet.h; path = b3/B3BlockInsertionSet.h; sourceTree = "<group>"; }; > 0F338E191BF286EA0013C88F /* B3LowerMacros.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3LowerMacros.cpp; path = b3/B3LowerMacros.cpp; sourceTree = "<group>"; }; > 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3LowerMacros.h; path = b3/B3LowerMacros.h; sourceTree = "<group>"; }; > 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUseKind.cpp; path = dfg/DFGUseKind.cpp; sourceTree = "<group>"; }; >- 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; }; >+ 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; }; > 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = LLIntEntrypoint.cpp; path = llint/LLIntEntrypoint.cpp; sourceTree = "<group>"; }; > 0F38B01017CF077F00B144D3 /* LLIntEntrypoint.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = LLIntEntrypoint.h; path = llint/LLIntEntrypoint.h; sourceTree = "<group>"; }; > 0F38B01317CFE75500B144D3 /* DFGCompilationKey.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCompilationKey.cpp; path = dfg/DFGCompilationKey.cpp; sourceTree = "<group>"; }; >@@ -2575,6 +2578,9 @@ > 0FB1765D196B8F9E0091052A /* DFGHeapLocation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGHeapLocation.h; path = dfg/DFGHeapLocation.h; sourceTree = "<group>"; }; > 0FB1765E196B8F9E0091052A /* DFGPureValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPureValue.cpp; path = dfg/DFGPureValue.cpp; sourceTree = "<group>"; }; > 0FB1765F196B8F9E0091052A /* DFGPureValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPureValue.h; path = dfg/DFGPureValue.h; sourceTree = "<group>"; }; >+ 0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirBlockWorklist.h; path = b3/air/AirBlockWorklist.h; sourceTree = "<group>"; }; >+ 0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirOptimizeBlockOrder.cpp; path = b3/air/AirOptimizeBlockOrder.cpp; sourceTree = "<group>"; }; >+ 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirOptimizeBlockOrder.h; path = b3/air/AirOptimizeBlockOrder.h; sourceTree = "<group>"; }; > 0FB438A219270B1D00E1FBC9 /* StructureSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StructureSet.cpp; sourceTree = "<group>"; }; > 0FB4B51016B3A964003F696B /* DFGMinifiedID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGMinifiedID.h; path = dfg/DFGMinifiedID.h; sourceTree = "<group>"; }; > 0FB4B51916B62772003F696B /* DFGAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAllocator.h; path = dfg/DFGAllocator.h; sourceTree = "<group>"; }; >@@ -4568,6 +4574,7 @@ > 0FEC854B1BDACDC70080FF74 /* AirArg.h */, > 0FEC854C1BDACDC70080FF74 /* AirBasicBlock.cpp */, > 0FEC854D1BDACDC70080FF74 /* AirBasicBlock.h */, >+ 0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */, > 0FEC854E1BDACDC70080FF74 /* AirCCallSpecial.cpp */, > 0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */, > 0FEC85501BDACDC70080FF74 /* AirCode.cpp */, >@@ -4590,6 +4597,8 @@ > 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */, > 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */, > 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */, >+ 0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */, >+ 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */, > 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */, > 0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */, > 0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */, >@@ -7501,6 +7510,7 @@ > 0FF729A5166AD351000F5BA3 /* ProfilerBytecode.h in Headers */, > 0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */, > 0F13912A16771C36009CCB07 /* ProfilerBytecodeSequence.h in Headers */, >+ 0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */, > 0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */, > 0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */, > 0FF729BC166AD360000F5BA3 /* ProfilerCompiledBytecode.h in Headers */, >@@ -7602,6 +7612,7 @@ > 996B73261BDA08EF00331B84 /* StringIteratorPrototype.lut.h in Headers */, > BC18C4680E16F5CD00B34460 /* StringObject.h in Headers */, > BC18C46A0E16F5CD00B34460 /* StringPrototype.h in Headers */, >+ 0FB3878E1BFBC44D00E3AB1E /* AirBlockWorklist.h in Headers */, > 142E313B134FF0A600AFADB5 /* Strong.h in Headers */, > 145722861437E140005FDE26 /* StrongInlines.h in Headers */, > BCDE3AB80E6C82F5001453A7 /* Structure.h in Headers */, >@@ -8432,6 +8443,7 @@ > 0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */, > A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */, > 0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */, >+ 0FB3878F1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp in Sources */, > 0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */, > 0F5D085D1B8CF99D001143B4 /* DFGNodeOrigin.cpp in Sources */, > 0F2B9CE619D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.cpp in Sources */, >Index: Source/JavaScriptCore/b3/B3BlockWorklist.h >=================================================================== >--- Source/JavaScriptCore/b3/B3BlockWorklist.h (revision 192516) >+++ Source/JavaScriptCore/b3/B3BlockWorklist.h (working copy) >@@ -35,8 +35,6 @@ > > namespace JSC { namespace B3 { > >-class BasicBlock; >- > typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist; > > // When you say BlockWith<int> you should read it as "block with an int". >Index: Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h >=================================================================== >--- Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h (revision 192516) >+++ Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h (working copy) >@@ -67,6 +67,8 @@ public: > FrequencyClass frequency() const { return m_frequency; } > FrequencyClass& frequency() { return m_frequency; } > >+ bool isRare() const { return frequency() == FrequencyClass::Rare; } >+ > void dump(PrintStream& out) const > { > if (frequency() != FrequencyClass::Normal) >Index: Source/JavaScriptCore/b3/B3Procedure.h >=================================================================== >--- Source/JavaScriptCore/b3/B3Procedure.h (revision 192516) >+++ Source/JavaScriptCore/b3/B3Procedure.h (working copy) >@@ -53,7 +53,7 @@ public: > JS_EXPORT_PRIVATE Procedure(); > JS_EXPORT_PRIVATE ~Procedure(); > >- JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = PNaN); >+ JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = 1); > > template<typename ValueType, typename... Arguments> > ValueType* add(Arguments...); >Index: Source/JavaScriptCore/b3/air/AirArg.h >=================================================================== >--- Source/JavaScriptCore/b3/air/AirArg.h (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirArg.h (working copy) >@@ -380,6 +380,18 @@ public: > return kind() == DoubleCond; > } > >+ bool isCondition() const >+ { >+ switch (kind()) { >+ case RelCond: >+ case ResCond: >+ case DoubleCond: >+ return true; >+ default: >+ return false; >+ } >+ } >+ > bool isSpecial() const > { > return kind() == Special; >@@ -724,6 +736,21 @@ public: > return static_cast<MacroAssembler::DoubleCondition>(m_offset); > } > >+ // Tells you if the Arg is invertible. Only condition arguments are invertible, and even for those, there >+ // are a few exceptions - notably Overflow and Signed. >+ bool isInvertible() const >+ { >+ switch (kind()) { >+ case RelCond: >+ case DoubleCond: >+ return true; >+ case ResCond: >+ return MacroAssembler::isInvertible(asResultCondition()); >+ default: >+ return false; >+ } >+ } >+ > // This is valid for condition arguments. It will invert them. > Arg inverted(bool inverted = true) const > { >Index: Source/JavaScriptCore/b3/air/AirBasicBlock.h >=================================================================== >--- Source/JavaScriptCore/b3/air/AirBasicBlock.h (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirBasicBlock.h (working copy) >@@ -50,6 +50,9 @@ public: > typedef Vector<FrequentedBlock, 2> SuccessorList; > > unsigned index() const { return m_index; } >+ >+ // You shouldn't call this except when you know what you're doing. >+ void setIndex(unsigned index) { m_index = index; } > > unsigned size() const { return m_insts.size(); } > InstList::iterator begin() { return m_insts.begin(); } >@@ -110,6 +113,8 @@ public: > bool replacePredecessor(BasicBlock* from, BasicBlock* to); > bool containsPredecessor(BasicBlock* predecessor) const { return m_predecessors.contains(predecessor); } > >+ double frequency() const { return m_frequency; } >+ > void dump(PrintStream&) const; > void deepDump(PrintStream&) const; > >Index: Source/JavaScriptCore/b3/air/AirBlockWorklist.h >=================================================================== >--- Source/JavaScriptCore/b3/air/AirBlockWorklist.h (revision 0) >+++ Source/JavaScriptCore/b3/air/AirBlockWorklist.h (working copy) >@@ -0,0 +1,56 @@ >+/* >+ * Copyright (C) 2015 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. >+ */ >+ >+#ifndef AirBlockWorklist_h >+#define AirBlockWorklist_h >+ >+#if ENABLE(B3_JIT) >+ >+#include "AirBasicBlock.h" >+#include "B3BlockWorklist.h" >+ >+namespace JSC { namespace B3 { namespace Air { >+ >+typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist; >+ >+// When you say BlockWith<int> you should read it as "block with an int". >+template<typename T> using BlockWith = GraphNodeWith<BasicBlock*, T>; >+ >+// Extended block worklist is useful for enqueueing some meta-data along with the block. It also >+// permits forcibly enqueueing things even if the block has already been seen. It's useful for >+// things like building a spanning tree, in which case T (the auxiliary payload) would be the >+// successor index. >+template<typename T> using ExtendedBlockWorklist = ExtendedGraphNodeWorklist<BasicBlock*, T, IndexSet<BasicBlock>>; >+ >+typedef GraphNodeWithOrder<BasicBlock*> BlockWithOrder; >+ >+typedef PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> PostOrderBlockWorklist; >+ >+} } } // namespace JSC::B3::Air >+ >+#endif // ENABLE(B3_JIT) >+ >+#endif // AirBlockWorklist_h >+ >Index: Source/JavaScriptCore/b3/air/AirCode.cpp >=================================================================== >--- Source/JavaScriptCore/b3/air/AirCode.cpp (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirCode.cpp (working copy) >@@ -128,7 +128,10 @@ unsigned Code::findNextBlockIndex(unsign > > BasicBlock* Code::findNextBlock(BasicBlock* block) const > { >- return at(findNextBlockIndex(block->index())); >+ unsigned index = findNextBlockIndex(block->index()); >+ if (index < size()) >+ return at(index); >+ return nullptr; > } > > } } } // namespace JSC::B3::Air >Index: Source/JavaScriptCore/b3/air/AirCode.h >=================================================================== >--- Source/JavaScriptCore/b3/air/AirCode.h (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirCode.h (working copy) >@@ -55,7 +55,7 @@ public: > > Procedure& proc() { return m_proc; } > >- BasicBlock* addBlock(double frequency = PNaN); >+ BasicBlock* addBlock(double frequency = 1); > > StackSlot* addStackSlot(unsigned byteSize, StackSlotKind, StackSlotValue* = nullptr); > StackSlot* addStackSlot(StackSlotValue*); >@@ -115,6 +115,10 @@ public: > BasicBlock* at(unsigned index) const { return m_blocks[index].get(); } > BasicBlock* operator[](unsigned index) const { return at(index); } > >+ // This is used by phases that optimize the block list. You shouldn't use this unless you really know >+ // what you're doing. >+ Vector<std::unique_ptr<BasicBlock>>& blockList() { return m_blocks; } >+ > // Finds the smallest index' such that at(index') != null and index' >= index. > unsigned findFirstBlockIndex(unsigned index) const; > >Index: Source/JavaScriptCore/b3/air/AirGenerate.cpp >=================================================================== >--- Source/JavaScriptCore/b3/air/AirGenerate.cpp (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirGenerate.cpp (working copy) >@@ -34,6 +34,7 @@ > #include "AirGenerationContext.h" > #include "AirHandleCalleeSaves.h" > #include "AirIteratedRegisterCoalescing.h" >+#include "AirOptimizeBlockOrder.h" > #include "AirReportUsedRegisters.h" > #include "AirSimplifyCFG.h" > #include "AirSpillEverything.h" >@@ -86,9 +87,11 @@ void generate(Code& code, CCallHelpers& > // phase. > simplifyCFG(code); > >- // FIXME: We should really have a code layout optimization here. >- // https://bugs.webkit.org/show_bug.cgi?id=150478 >+ // This sorts the basic blocks in Code to achieve an ordering that maximizes the likelihood that a high >+ // frequency successor is also the fall-through target. >+ optimizeBlockOrder(code); > >+ // This is needed to satisfy a requirement of B3::StackmapValue. > reportUsedRegisters(code); > > if (shouldValidateIR()) >Index: Source/JavaScriptCore/b3/air/AirOpcode.opcodes >=================================================================== >--- Source/JavaScriptCore/b3/air/AirOpcode.opcodes (revision 192516) >+++ Source/JavaScriptCore/b3/air/AirOpcode.opcodes (working copy) >@@ -265,6 +265,9 @@ Test64 U:G, U:G, U:G, D:G > ResCond, Tmp, Imm, Tmp > ResCond, Tmp, Tmp, Tmp > >+# Note that branches have some logic in AirOptimizeBlockOrder.cpp. If you add new branches, please make sure >+# you opt them into the block order optimizations. >+ > Branch8 U:G, U:G, U:G /branch > RelCond, Addr, Imm > RelCond, Index, Imm >Index: Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp >=================================================================== >--- Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp (revision 0) >+++ Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp (working copy) >@@ -0,0 +1,174 @@ >+/* >+ * Copyright (C) 2015 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 "AirOptimizeBlockOrder.h" >+ >+#if ENABLE(B3_JIT) >+ >+#include "AirBlockWorklist.h" >+#include "AirCode.h" >+#include "AirInstInlines.h" >+#include "AirPhaseScope.h" >+#include <wtf/BubbleSort.h> >+ >+namespace JSC { namespace B3 { namespace Air { >+ >+namespace { >+ >+class SortedSuccessors { >+public: >+ SortedSuccessors() >+ { >+ } >+ >+ void append(BasicBlock* block) >+ { >+ m_successors.append(block); >+ } >+ >+ void process(BlockWorklist& worklist) >+ { >+ // We prefer a stable sort, and we don't want it to go off the rails if we see NaN. Also, the number >+ // of successors is bounded. In fact, it currently cannot be more than 2. :-) >+ bubbleSort( >+ m_successors.begin(), m_successors.end(), >+ [] (BasicBlock* left, BasicBlock* right) { >+ return left->frequency() < right->frequency(); >+ }); >+ >+ // Pushing the successors in ascending order of frequency ensures that the very next block we visit >+ // is our highest-frequency successor (unless that successor has already been visited). >+ for (unsigned i = 0; i < m_successors.size(); ++i) >+ worklist.push(m_successors[i]); >+ >+ m_successors.resize(0); >+ } >+ >+private: >+ Vector<BasicBlock*, 2> m_successors; >+}; >+ >+} // anonymous namespace >+ >+void optimizeBlockOrder(Code& code) >+{ >+ PhaseScope phaseScope(code, "optimizeBlockOrder"); >+ >+ Vector<BasicBlock*> blocksInOrder; >+ >+ BlockWorklist fastWorklist; >+ SortedSuccessors sortedSuccessors; >+ SortedSuccessors sortedSlowSuccessors; >+ >+ fastWorklist.push(code[0]); >+ >+ while (BasicBlock* block = fastWorklist.pop()) { >+ blocksInOrder.append(block); >+ for (FrequentedBlock& successor : block->successors()) { >+ if (successor.isRare()) >+ sortedSlowSuccessors.append(successor.block()); >+ else >+ sortedSuccessors.append(successor.block()); >+ } >+ sortedSuccessors.process(fastWorklist); >+ } >+ >+ BlockWorklist slowWorklist; >+ sortedSlowSuccessors.process(slowWorklist); >+ >+ while (BasicBlock* block = slowWorklist.pop()) { >+ // We might have already processed this block. >+ if (fastWorklist.saw(block)) >+ continue; >+ >+ blocksInOrder.append(block); >+ for (BasicBlock* successor : block->successorBlocks()) >+ sortedSuccessors.append(successor); >+ sortedSuccessors.process(slowWorklist); >+ } >+ >+ ASSERT(fastWorklist.isEmpty()); >+ ASSERT(slowWorklist.isEmpty()); >+ >+ // Place blocks into Code's block list according to the ordering in blocksInOrder. We do this by leaking >+ // all of the blocks and then readopting them. >+ for (auto& entry : code.blockList()) >+ entry.release(); >+ >+ code.blockList().resize(0); >+ >+ for (unsigned i = 0; i < blocksInOrder.size(); ++i) { >+ BasicBlock* block = blocksInOrder[i]; >+ block->setIndex(i); >+ code.blockList().append(std::unique_ptr<BasicBlock>(block)); >+ } >+ >+ // Finally, flip any branches that we recognize. It's most optimal if the taken successor does not point >+ // at the next block. >+ for (BasicBlock* block : code) { >+ Inst& branch = block->last(); >+ >+ // It's somewhat tempting to just say that if the block has two successors and the first arg is >+ // invertible, then we can do the optimization. But that's wagging the dog. The fact that an >+ // instruction happens to have an argument that is invertible doesn't mean it's a branch, even though >+ // it is true that currently only branches have invertible arguments. It's also tempting to say that >+ // the /branch flag in AirOpcode.opcodes tells us that something is a branch - except that there, >+ // /branch also means Jump. The approach taken here means that if you add new branch instructions and >+ // forget about this phase, then at worse your new instructions won't opt into the inversion >+ // optimization. You'll probably realize that as soon as you look at the disassembly, and it >+ // certainly won't cause any correctness issues. >+ >+ switch (branch.opcode) { >+ case Branch8: >+ case Branch32: >+ case Branch64: >+ case BranchTest8: >+ case BranchTest32: >+ case BranchTest64: >+ case BranchDouble: >+ case BranchAdd32: >+ case BranchAdd64: >+ case BranchMul32: >+ case BranchMul64: >+ case BranchSub32: >+ case BranchSub64: >+ case BranchNeg32: >+ case BranchNeg64: >+ if (code.findNextBlock(block) == block->successorBlock(0) && branch.args[0].isInvertible()) { >+ std::swap(block->successor(0), block->successor(1)); >+ branch.args[0] = branch.args[0].inverted(); >+ } >+ break; >+ >+ default: >+ break; >+ } >+ } >+} >+ >+} } } // namespace JSC::B3::Air >+ >+#endif // ENABLE(B3_JIT) >Index: Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h >=================================================================== >--- Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h (revision 0) >+++ Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h (working copy) >@@ -0,0 +1,45 @@ >+/* >+ * Copyright (C) 2015 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. >+ */ >+ >+#ifndef AirOptimizeBlockOrder_h >+#define AirOptimizeBlockOrder_h >+ >+#if ENABLE(B3_JIT) >+ >+namespace JSC { namespace B3 { namespace Air { >+ >+class Code; >+ >+// Reorders the basic blocks to keep hot blocks at the top, and maximize the likelihood that a frequently >+// taken edge is just a fall-through. >+ >+void optimizeBlockOrder(Code&); >+ >+} } } // namespace JSC::B3::Air >+ >+#endif // ENABLE(B3_JIT) >+ >+#endif // AirOptimizeBlockOrder_h >+ >Index: Source/WTF/ChangeLog >=================================================================== >--- Source/WTF/ChangeLog (revision 192516) >+++ Source/WTF/ChangeLog (working copy) >@@ -1,3 +1,16 @@ >+2015-11-17 Filip Pizlo <fpizlo@apple.com> >+ >+ Air should lay out code optimally >+ https://bugs.webkit.org/show_bug.cgi?id=150478 >+ >+ Reviewed by NOBODY (OOPS!). >+ >+ * wtf/GraphNodeWorklist.h: >+ (WTF::GraphNodeWorklist::push): >+ (WTF::GraphNodeWorklist::isEmpty): >+ (WTF::GraphNodeWorklist::notEmpty): >+ (WTF::GraphNodeWorklist::pop): >+ > 2015-11-11 Anders Carlsson <andersca@apple.com> > > Enable cross-platform context menus by default >Index: Source/WTF/wtf/GraphNodeWorklist.h >=================================================================== >--- Source/WTF/wtf/GraphNodeWorklist.h (revision 192516) >+++ Source/WTF/wtf/GraphNodeWorklist.h (working copy) >@@ -45,6 +45,7 @@ public: > return true; > } > >+ bool isEmpty() const { return m_stack.isEmpty(); } > bool notEmpty() const { return !m_stack.isEmpty(); } > > Node pop()
<b>You cannot view the attachment while viewing its details because your browser does not support IFRAMEs. <a href="attachment.cgi?id=265700">View the attachment on a separate page</a>.</b>
View Attachment As Diff
View Attachment As Raw
Flags:
ggaren
:
review+
Actions:
View
|
Formatted Diff
|
Diff
Attachments on
bug 150478
: 265700