Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (192538 => 192539)
--- trunk/Source/_javascript_Core/ChangeLog 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-11-17 22:29:54 UTC (rev 192539)
@@ -1,3 +1,58 @@
+2015-11-17 Filip Pizlo <fpi...@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.
+
+ * _javascript_Core.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 <akl...@apple.com>
[JSC] JSPropertyNameEnumerator could be destructorless.
Modified: trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj (192538 => 192539)
--- trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/_javascript_Core.xcodeproj/project.pbxproj 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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 */,
Modified: trunk/Source/_javascript_Core/b3/B3BlockWorklist.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/B3BlockWorklist.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/B3BlockWorklist.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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".
Modified: trunk/Source/_javascript_Core/b3/B3GenericFrequentedBlock.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/B3GenericFrequentedBlock.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/B3GenericFrequentedBlock.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -67,6 +67,8 @@
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)
Modified: trunk/Source/_javascript_Core/b3/B3Procedure.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/B3Procedure.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/B3Procedure.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -53,7 +53,7 @@
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...);
Modified: trunk/Source/_javascript_Core/b3/air/AirArg.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirArg.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirArg.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -380,6 +380,18 @@
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 @@
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
{
Modified: trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirBasicBlock.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -50,6 +50,10 @@
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 @@
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;
Added: trunk/Source/_javascript_Core/b3/air/AirBlockWorklist.h (0 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirBlockWorklist.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirBlockWorklist.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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
+
Modified: trunk/Source/_javascript_Core/b3/air/AirCode.cpp (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirCode.cpp 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirCode.cpp 2015-11-17 22:29:54 UTC (rev 192539)
@@ -128,7 +128,10 @@
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
Modified: trunk/Source/_javascript_Core/b3/air/AirCode.h (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirCode.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirCode.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -55,7 +55,7 @@
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 @@
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;
Modified: trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirGenerate.cpp 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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 @@
// 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())
Modified: trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes (192538 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/_javascript_Core/b3/air/AirOpcode.opcodes 2015-11-17 22:29:54 UTC (rev 192539)
@@ -273,6 +273,9 @@
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
Added: trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.cpp (0 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.cpp (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.cpp 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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)
Added: trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.h (0 => 192539)
--- trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.h (rev 0)
+++ trunk/Source/_javascript_Core/b3/air/AirOptimizeBlockOrder.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -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
+
Modified: trunk/Source/WTF/ChangeLog (192538 => 192539)
--- trunk/Source/WTF/ChangeLog 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/WTF/ChangeLog 2015-11-17 22:29:54 UTC (rev 192539)
@@ -1,3 +1,16 @@
+2015-11-17 Filip Pizlo <fpi...@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 <ander...@apple.com>
Enable cross-platform context menus by default
Modified: trunk/Source/WTF/wtf/GraphNodeWorklist.h (192538 => 192539)
--- trunk/Source/WTF/wtf/GraphNodeWorklist.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/WTF/wtf/GraphNodeWorklist.h 2015-11-17 22:29:54 UTC (rev 192539)
@@ -45,6 +45,7 @@
return true;
}
+ bool isEmpty() const { return m_stack.isEmpty(); }
bool notEmpty() const { return !m_stack.isEmpty(); }
Node pop()
