<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[192539] trunk/Source</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/192539">192539</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-17 14:29:54 -0800 (Tue, 17 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Air should lay out code optimally
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):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj">trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3BlockWorklisth">trunk/Source/JavaScriptCore/b3/B3BlockWorklist.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3GenericFrequentedBlockh">trunk/Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3Procedureh">trunk/Source/JavaScriptCore/b3/B3Procedure.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirArgh">trunk/Source/JavaScriptCore/b3/air/AirArg.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirBasicBlockh">trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodecpp">trunk/Source/JavaScriptCore/b3/air/AirCode.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirCodeh">trunk/Source/JavaScriptCore/b3/air/AirCode.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirGeneratecpp">trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirOpcodeopcodes">trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFwtfGraphNodeWorklisth">trunk/Source/WTF/wtf/GraphNodeWorklist.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3airAirBlockWorklisth">trunk/Source/JavaScriptCore/b3/air/AirBlockWorklist.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirOptimizeBlockOrdercpp">trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirOptimizeBlockOrderh">trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -1,3 +1,58 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-11-17 Andreas Kling <akling@apple.com>
</span><span class="cx">
</span><span class="cx"> [JSC] JSPropertyNameEnumerator could be destructorless.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -286,7 +286,7 @@
</span><span class="cx"> 0F338DF61BE93D550013C88F /* B3ConstrainedValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */; };
</span><span class="cx"> 0F338DF91BE96AA80013C88F /* B3CCallValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */; };
</span><span class="cx"> 0F338DFA1BE96AA80013C88F /* B3CCallValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DF81BE96AA80013C88F /* B3CCallValue.h */; };
</span><del>- 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; };
</del><ins>+ 0F338DFD1BED51270013C88F /* AirSimplifyCFG.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */; };
</ins><span class="cx"> 0F338DFE1BED51270013C88F /* AirSimplifyCFG.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */; };
</span><span class="cx"> 0F338E0B1BF0276C0013C88F /* B3Compilation.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */; };
</span><span class="cx"> 0F338E0C1BF0276C0013C88F /* B3Compilation.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E001BF0276C0013C88F /* B3Compilation.h */; };
</span><span class="lines">@@ -300,12 +300,12 @@
</span><span class="cx"> 0F338E141BF0276C0013C88F /* B3ValueKey.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E081BF0276C0013C88F /* B3ValueKey.cpp */; };
</span><span class="cx"> 0F338E151BF0276C0013C88F /* B3ValueKey.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E091BF0276C0013C88F /* B3ValueKey.h */; };
</span><span class="cx"> 0F338E161BF0276C0013C88F /* B3ValueKeyInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E0A1BF0276C0013C88F /* B3ValueKeyInlines.h */; };
</span><del>- 0F338E1B1BF286EA0013C88F /* B3BlockInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */; };
</del><ins>+ 0F338E1B1BF286EA0013C88F /* B3BlockInsertionSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */; };
</ins><span class="cx"> 0F338E1C1BF286EA0013C88F /* B3BlockInsertionSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E181BF286EA0013C88F /* B3BlockInsertionSet.h */; };
</span><span class="cx"> 0F338E1D1BF286EA0013C88F /* B3LowerMacros.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F338E191BF286EA0013C88F /* B3LowerMacros.cpp */; };
</span><span class="cx"> 0F338E1E1BF286EA0013C88F /* B3LowerMacros.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */; };
</span><span class="cx"> 0F34B14916D42010001CDA5A /* DFGUseKind.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */; };
</span><del>- 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; };
</del><ins>+ 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; };
</ins><span class="cx"> 0F38B01117CF078000B144D3 /* LLIntEntrypoint.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */; };
</span><span class="cx"> 0F38B01217CF078300B144D3 /* LLIntEntrypoint.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F38B01017CF077F00B144D3 /* LLIntEntrypoint.h */; settings = {ATTRIBUTES = (Private, ); }; };
</span><span class="cx"> 0F38B01717CFE75500B144D3 /* DFGCompilationKey.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B01317CFE75500B144D3 /* DFGCompilationKey.cpp */; };
</span><span class="lines">@@ -527,6 +527,9 @@
</span><span class="cx"> 0FB17661196B8F9E0091052A /* DFGHeapLocation.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB1765D196B8F9E0091052A /* DFGHeapLocation.h */; };
</span><span class="cx"> 0FB17662196B8F9E0091052A /* DFGPureValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB1765E196B8F9E0091052A /* DFGPureValue.cpp */; };
</span><span class="cx"> 0FB17663196B8F9E0091052A /* DFGPureValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB1765F196B8F9E0091052A /* DFGPureValue.h */; };
</span><ins>+ 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 */; };
</ins><span class="cx"> 0FB438A319270B1D00E1FBC9 /* StructureSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB438A219270B1D00E1FBC9 /* StructureSet.cpp */; };
</span><span class="cx"> 0FB4FB731BC843140025CA5A /* FTLLazySlowPath.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FB4FB701BC843140025CA5A /* FTLLazySlowPath.cpp */; };
</span><span class="cx"> 0FB4FB741BC843140025CA5A /* FTLLazySlowPath.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FB4FB711BC843140025CA5A /* FTLLazySlowPath.h */; };
</span><span class="lines">@@ -2335,7 +2338,7 @@
</span><span class="cx"> 0F338DF41BE93D550013C88F /* B3ConstrainedValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ConstrainedValue.h; path = b3/B3ConstrainedValue.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F338DF71BE96AA80013C88F /* B3CCallValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3CCallValue.cpp; path = b3/B3CCallValue.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F338DF81BE96AA80013C88F /* B3CCallValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3CCallValue.h; path = b3/B3CCallValue.h; sourceTree = "<group>"; };
</span><del>- 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; };
</del><ins>+ 0F338DFB1BED51270013C88F /* AirSimplifyCFG.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = AirSimplifyCFG.cpp; path = b3/air/AirSimplifyCFG.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 0F338DFC1BED51270013C88F /* AirSimplifyCFG.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirSimplifyCFG.h; path = b3/air/AirSimplifyCFG.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F338DFF1BF0276C0013C88F /* B3Compilation.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3Compilation.cpp; path = b3/B3Compilation.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F338E001BF0276C0013C88F /* B3Compilation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3Compilation.h; path = b3/B3Compilation.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -2349,12 +2352,12 @@
</span><span class="cx"> 0F338E081BF0276C0013C88F /* B3ValueKey.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3ValueKey.cpp; path = b3/B3ValueKey.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F338E091BF0276C0013C88F /* B3ValueKey.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ValueKey.h; path = b3/B3ValueKey.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F338E0A1BF0276C0013C88F /* B3ValueKeyInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3ValueKeyInlines.h; path = b3/B3ValueKeyInlines.h; sourceTree = "<group>"; };
</span><del>- 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3BlockInsertionSet.cpp; path = b3/B3BlockInsertionSet.cpp; sourceTree = "<group>"; };
</del><ins>+ 0F338E171BF286EA0013C88F /* B3BlockInsertionSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3BlockInsertionSet.cpp; path = b3/B3BlockInsertionSet.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 0F338E181BF286EA0013C88F /* B3BlockInsertionSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3BlockInsertionSet.h; path = b3/B3BlockInsertionSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F338E191BF286EA0013C88F /* B3LowerMacros.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3LowerMacros.cpp; path = b3/B3LowerMacros.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F338E1A1BF286EA0013C88F /* B3LowerMacros.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3LowerMacros.h; path = b3/B3LowerMacros.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F34B14716D4200E001CDA5A /* DFGUseKind.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGUseKind.cpp; path = dfg/DFGUseKind.cpp; sourceTree = "<group>"; };
</span><del>- 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; };
</del><ins>+ 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = LLIntEntrypoint.cpp; path = llint/LLIntEntrypoint.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F38B01017CF077F00B144D3 /* LLIntEntrypoint.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = LLIntEntrypoint.h; path = llint/LLIntEntrypoint.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F38B01317CFE75500B144D3 /* DFGCompilationKey.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGCompilationKey.cpp; path = dfg/DFGCompilationKey.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -2575,6 +2578,9 @@
</span><span class="cx"> 0FB1765D196B8F9E0091052A /* DFGHeapLocation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGHeapLocation.h; path = dfg/DFGHeapLocation.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FB1765E196B8F9E0091052A /* DFGPureValue.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = DFGPureValue.cpp; path = dfg/DFGPureValue.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FB1765F196B8F9E0091052A /* DFGPureValue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGPureValue.h; path = dfg/DFGPureValue.h; sourceTree = "<group>"; };
</span><ins>+ 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>"; };
</ins><span class="cx"> 0FB438A219270B1D00E1FBC9 /* StructureSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StructureSet.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FB4B51016B3A964003F696B /* DFGMinifiedID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGMinifiedID.h; path = dfg/DFGMinifiedID.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FB4B51916B62772003F696B /* DFGAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGAllocator.h; path = dfg/DFGAllocator.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -4568,6 +4574,7 @@
</span><span class="cx"> 0FEC854B1BDACDC70080FF74 /* AirArg.h */,
</span><span class="cx"> 0FEC854C1BDACDC70080FF74 /* AirBasicBlock.cpp */,
</span><span class="cx"> 0FEC854D1BDACDC70080FF74 /* AirBasicBlock.h */,
</span><ins>+ 0FB3878B1BFBC44D00E3AB1E /* AirBlockWorklist.h */,
</ins><span class="cx"> 0FEC854E1BDACDC70080FF74 /* AirCCallSpecial.cpp */,
</span><span class="cx"> 0FEC854F1BDACDC70080FF74 /* AirCCallSpecial.h */,
</span><span class="cx"> 0FEC85501BDACDC70080FF74 /* AirCode.cpp */,
</span><span class="lines">@@ -4590,6 +4597,8 @@
</span><span class="cx"> 26718BA31BE99F780052017B /* AirIteratedRegisterCoalescing.h */,
</span><span class="cx"> 0FEC855D1BDACDC70080FF74 /* AirLiveness.h */,
</span><span class="cx"> 264091FA1BE2FD4100684DB2 /* AirOpcode.opcodes */,
</span><ins>+ 0FB3878C1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp */,
+ 0FB3878D1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h */,
</ins><span class="cx"> 0FEC855E1BDACDC70080FF74 /* AirPhaseScope.cpp */,
</span><span class="cx"> 0FEC855F1BDACDC70080FF74 /* AirPhaseScope.h */,
</span><span class="cx"> 0FEC85601BDACDC70080FF74 /* AirRegisterPriority.cpp */,
</span><span class="lines">@@ -7501,6 +7510,7 @@
</span><span class="cx"> 0FF729A5166AD351000F5BA3 /* ProfilerBytecode.h in Headers */,
</span><span class="cx"> 0FF729B9166AD360000F5BA3 /* ProfilerBytecodes.h in Headers */,
</span><span class="cx"> 0F13912A16771C36009CCB07 /* ProfilerBytecodeSequence.h in Headers */,
</span><ins>+ 0FB387901BFBC44D00E3AB1E /* AirOptimizeBlockOrder.h in Headers */,
</ins><span class="cx"> 0FF729BA166AD360000F5BA3 /* ProfilerCompilation.h in Headers */,
</span><span class="cx"> 0FF729BB166AD360000F5BA3 /* ProfilerCompilationKind.h in Headers */,
</span><span class="cx"> 0FF729BC166AD360000F5BA3 /* ProfilerCompiledBytecode.h in Headers */,
</span><span class="lines">@@ -7602,6 +7612,7 @@
</span><span class="cx"> 996B73261BDA08EF00331B84 /* StringIteratorPrototype.lut.h in Headers */,
</span><span class="cx"> BC18C4680E16F5CD00B34460 /* StringObject.h in Headers */,
</span><span class="cx"> BC18C46A0E16F5CD00B34460 /* StringPrototype.h in Headers */,
</span><ins>+ 0FB3878E1BFBC44D00E3AB1E /* AirBlockWorklist.h in Headers */,
</ins><span class="cx"> 142E313B134FF0A600AFADB5 /* Strong.h in Headers */,
</span><span class="cx"> 145722861437E140005FDE26 /* StrongInlines.h in Headers */,
</span><span class="cx"> BCDE3AB80E6C82F5001453A7 /* Structure.h in Headers */,
</span><span class="lines">@@ -8432,6 +8443,7 @@
</span><span class="cx"> 0FF2CD5B1B61A4F8004955A8 /* DFGMultiGetByOffsetData.cpp in Sources */,
</span><span class="cx"> A737810D1799EA2E00817533 /* DFGNaturalLoops.cpp in Sources */,
</span><span class="cx"> 0FF0F19C16B72A03005DF95B /* DFGNode.cpp in Sources */,
</span><ins>+ 0FB3878F1BFBC44D00E3AB1E /* AirOptimizeBlockOrder.cpp in Sources */,
</ins><span class="cx"> 0FA581BA150E952C00B9A2D9 /* DFGNodeFlags.cpp in Sources */,
</span><span class="cx"> 0F5D085D1B8CF99D001143B4 /* DFGNodeOrigin.cpp in Sources */,
</span><span class="cx"> 0F2B9CE619D0BA7D00B1D1B5 /* DFGObjectAllocationSinkingPhase.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3BlockWorklisth"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3BlockWorklist.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3BlockWorklist.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/B3BlockWorklist.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -35,8 +35,6 @@
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 {
</span><span class="cx">
</span><del>-class BasicBlock;
-
</del><span class="cx"> typedef GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock>> BlockWorklist;
</span><span class="cx">
</span><span class="cx"> // When you say BlockWith<int> you should read it as "block with an int".
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3GenericFrequentedBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/B3GenericFrequentedBlock.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -67,6 +67,8 @@
</span><span class="cx"> FrequencyClass frequency() const { return m_frequency; }
</span><span class="cx"> FrequencyClass& frequency() { return m_frequency; }
</span><span class="cx">
</span><ins>+ bool isRare() const { return frequency() == FrequencyClass::Rare; }
+
</ins><span class="cx"> void dump(PrintStream& out) const
</span><span class="cx"> {
</span><span class="cx"> if (frequency() != FrequencyClass::Normal)
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3Procedureh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3Procedure.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3Procedure.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/B3Procedure.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -53,7 +53,7 @@
</span><span class="cx"> JS_EXPORT_PRIVATE Procedure();
</span><span class="cx"> JS_EXPORT_PRIVATE ~Procedure();
</span><span class="cx">
</span><del>- JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = PNaN);
</del><ins>+ JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = 1);
</ins><span class="cx">
</span><span class="cx"> template<typename ValueType, typename... Arguments>
</span><span class="cx"> ValueType* add(Arguments...);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirArgh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirArg.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirArg.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirArg.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -380,6 +380,18 @@
</span><span class="cx"> return kind() == DoubleCond;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isCondition() const
+ {
+ switch (kind()) {
+ case RelCond:
+ case ResCond:
+ case DoubleCond:
+ return true;
+ default:
+ return false;
+ }
+ }
+
</ins><span class="cx"> bool isSpecial() const
</span><span class="cx"> {
</span><span class="cx"> return kind() == Special;
</span><span class="lines">@@ -724,6 +736,21 @@
</span><span class="cx"> return static_cast<MacroAssembler::DoubleCondition>(m_offset);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // 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;
+ }
+ }
+
</ins><span class="cx"> // This is valid for condition arguments. It will invert them.
</span><span class="cx"> Arg inverted(bool inverted = true) const
</span><span class="cx"> {
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirBasicBlockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -50,6 +50,10 @@
</span><span class="cx"> typedef Vector<FrequentedBlock, 2> SuccessorList;
</span><span class="cx">
</span><span class="cx"> unsigned index() const { return m_index; }
</span><ins>+
+ // 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; }
</ins><span class="cx">
</span><span class="cx"> unsigned size() const { return m_insts.size(); }
</span><span class="cx"> InstList::iterator begin() { return m_insts.begin(); }
</span><span class="lines">@@ -110,6 +114,8 @@
</span><span class="cx"> bool replacePredecessor(BasicBlock* from, BasicBlock* to);
</span><span class="cx"> bool containsPredecessor(BasicBlock* predecessor) const { return m_predecessors.contains(predecessor); }
</span><span class="cx">
</span><ins>+ double frequency() const { return m_frequency; }
+
</ins><span class="cx"> void dump(PrintStream&) const;
</span><span class="cx"> void deepDump(PrintStream&) const;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirBlockWorklisth"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirBlockWorklist.h (0 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirBlockWorklist.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirBlockWorklist.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -0,0 +1,56 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCodecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.cpp (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.cpp 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -128,7 +128,10 @@
</span><span class="cx">
</span><span class="cx"> BasicBlock* Code::findNextBlock(BasicBlock* block) const
</span><span class="cx"> {
</span><del>- return at(findNextBlockIndex(block->index()));
</del><ins>+ unsigned index = findNextBlockIndex(block->index());
+ if (index < size())
+ return at(index);
+ return nullptr;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } } } // namespace JSC::B3::Air
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirCodeh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirCode.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirCode.h 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirCode.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -55,7 +55,7 @@
</span><span class="cx">
</span><span class="cx"> Procedure& proc() { return m_proc; }
</span><span class="cx">
</span><del>- BasicBlock* addBlock(double frequency = PNaN);
</del><ins>+ BasicBlock* addBlock(double frequency = 1);
</ins><span class="cx">
</span><span class="cx"> StackSlot* addStackSlot(unsigned byteSize, StackSlotKind, StackSlotValue* = nullptr);
</span><span class="cx"> StackSlot* addStackSlot(StackSlotValue*);
</span><span class="lines">@@ -115,6 +115,10 @@
</span><span class="cx"> BasicBlock* at(unsigned index) const { return m_blocks[index].get(); }
</span><span class="cx"> BasicBlock* operator[](unsigned index) const { return at(index); }
</span><span class="cx">
</span><ins>+ // 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; }
+
</ins><span class="cx"> // Finds the smallest index' such that at(index') != null and index' >= index.
</span><span class="cx"> unsigned findFirstBlockIndex(unsigned index) const;
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirGeneratecpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirGenerate.cpp 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -34,6 +34,7 @@
</span><span class="cx"> #include "AirGenerationContext.h"
</span><span class="cx"> #include "AirHandleCalleeSaves.h"
</span><span class="cx"> #include "AirIteratedRegisterCoalescing.h"
</span><ins>+#include "AirOptimizeBlockOrder.h"
</ins><span class="cx"> #include "AirReportUsedRegisters.h"
</span><span class="cx"> #include "AirSimplifyCFG.h"
</span><span class="cx"> #include "AirSpillEverything.h"
</span><span class="lines">@@ -86,9 +87,11 @@
</span><span class="cx"> // phase.
</span><span class="cx"> simplifyCFG(code);
</span><span class="cx">
</span><del>- // FIXME: We should really have a code layout optimization here.
- // https://bugs.webkit.org/show_bug.cgi?id=150478
</del><ins>+ // 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);
</ins><span class="cx">
</span><ins>+ // This is needed to satisfy a requirement of B3::StackmapValue.
</ins><span class="cx"> reportUsedRegisters(code);
</span><span class="cx">
</span><span class="cx"> if (shouldValidateIR())
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirOpcodeopcodes"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes 2015-11-17 22:21:30 UTC (rev 192538)
+++ trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -273,6 +273,9 @@
</span><span class="cx"> ResCond, Tmp, Imm, Tmp
</span><span class="cx"> ResCond, Tmp, Tmp, Tmp
</span><span class="cx">
</span><ins>+# 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.
+
</ins><span class="cx"> Branch8 U:G, U:G, U:G /branch
</span><span class="cx"> RelCond, Addr, Imm
</span><span class="cx"> RelCond, Index, Imm
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirOptimizeBlockOrdercpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp (0 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.cpp 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -0,0 +1,174 @@
</span><ins>+/*
+ * 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)
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirOptimizeBlockOrderh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h (0 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirOptimizeBlockOrder.h 2015-11-17 22:29:54 UTC (rev 192539)
</span><span class="lines">@@ -0,0 +1,45 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,3 +1,16 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-11-11 Anders Carlsson <andersca@apple.com>
</span><span class="cx">
</span><span class="cx"> Enable cross-platform context menus by default
</span></span></pre></div>
<a id="trunkSourceWTFwtfGraphNodeWorklisth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/GraphNodeWorklist.h (192538 => 192539)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -45,6 +45,7 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ bool isEmpty() const { return m_stack.isEmpty(); }
</ins><span class="cx"> bool notEmpty() const { return !m_stack.isEmpty(); }
</span><span class="cx">
</span><span class="cx"> Node pop()
</span></span></pre>
</div>
</div>
</body>
</html>