Air should lay out code optimally
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 17 Nov 2015 22:29:54 +0000 (22:29 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 17 Nov 2015 22:29:54 +0000 (22:29 +0000)
https://bugs.webkit.org/show_bug.cgi?id=150478

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

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 a branch's 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.

Source/WTF:

* wtf/GraphNodeWorklist.h:
(WTF::GraphNodeWorklist::push):
(WTF::GraphNodeWorklist::isEmpty):
(WTF::GraphNodeWorklist::notEmpty):
(WTF::GraphNodeWorklist::pop):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@192539 268f45cc-cd09-0410-ab3c-d52691b4dbfc

16 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
Source/JavaScriptCore/b3/B3BlockWorklist.h
Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/b3/air/AirArg.h
Source/JavaScriptCore/b3/air/AirBasicBlock.h
Source/JavaScriptCore/b3/air/AirBlockWorklist.h [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirCode.cpp
Source/JavaScriptCore/b3/air/AirCode.h
Source/JavaScriptCore/b3/air/AirGenerate.cpp
Source/JavaScriptCore/b3/air/AirOpcode.opcodes
Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp [new file with mode: 0644]
Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h [new file with mode: 0644]
Source/WTF/ChangeLog
Source/WTF/wtf/GraphNodeWorklist.h

index 13e3f2f..e77671e 100644 (file)
@@ -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 Geoffrey Garen.
+
+        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 a branch's 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  Andreas Kling  <akling@apple.com>
 
         [JSC] JSPropertyNameEnumerator could be destructorless.
index ba4235e..e548016 100644 (file)
                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 */; };
                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 */; };
                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 */; };
                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>"; };
                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>"; };
                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>"; };
                                0FEC854B1BDACDC70080FF74 /* AirArg.h */,
                                0FEC854C1BDACDC70080FF74 /* AirBasicBlock.cpp */,
                                0FEC854D1BDACDC70080FF74 /* AirBasicBlock.h */,
+                               0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */,
                                0FEC854E1BDACDC70080FF74 /* AirCCallSpecial.cpp */,
                                0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */,
                                0FEC85501BDACDC70080FF74 /* AirCode.cpp */,
                                26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
                                0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
                                264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
+                               0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
+                               0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
                                0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
                                0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */,
                                0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */,
                                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 */,
                                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 */,
                                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 63f04d4..af7ee2c 100644 (file)
@@ -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 992d915..d1b7a5d 100644 (file)
@@ -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 a742a46..b1e242b 100644 (file)
@@ -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 46202e6..57ad5c0 100644 (file)
@@ -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 e397d46..dcaf5ac 100644 (file)
@@ -50,6 +50,10 @@ public:
     typedef Vector<FrequentedBlock, 2> SuccessorList;
 
     unsigned index() const { return m_index; }
+
+    // This method is exposed for phases that mess with the layout of basic blocks. Currently that means just
+    // optimizeBlockOrder().
+    void setIndex(unsigned index) { m_index = index; }
     
     unsigned size() const { return m_insts.size(); }
     InstList::iterator begin() { return m_insts.begin(); }
@@ -110,6 +114,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;
 
diff --git a/Source/JavaScriptCore/b3/air/AirBlockWorklist.h b/Source/JavaScriptCore/b3/air/AirBlockWorklist.h
new file mode 100644 (file)
index 0000000..eb7cfce
--- /dev/null
@@ -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 d6406e4..3dc3930 100644 (file)
@@ -128,7 +128,10 @@ unsigned Code::findNextBlockIndex(unsigned index) const
 
 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 593dcd1..678e4c7 100644 (file)
@@ -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 485a1ce..bd655e8 100644 (file)
@@ -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& jit)
     // 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 a4bda7c..526caa7 100644 (file)
@@ -273,6 +273,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
diff --git a/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp b/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp
new file mode 100644 (file)
index 0000000..4bb38e7
--- /dev/null
@@ -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 worst 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)
diff --git a/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h b/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h
new file mode 100644 (file)
index 0000000..03d19a0
--- /dev/null
@@ -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 fe2346e..8ff87bb 100644 (file)
@@ -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 Geoffrey Garen.
+
+        * 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 810a9ce..42f507c 100644 (file)
@@ -45,6 +45,7 @@ public:
         return true;
     }
 
+    bool isEmpty() const { return m_stack.isEmpty(); }
     bool notEmpty() const { return !m_stack.isEmpty(); }
     
     Node pop()