<!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>[192816] trunk/Source/JavaScriptCore</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/192816">192816</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-30 13:05:25 -0800 (Mon, 30 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3 should be be clever about choosing which child to reuse for result in two-operand commutative operations
https://bugs.webkit.org/show_bug.cgi?id=151321
Reviewed by Geoffrey Garen.
When lowering a commutative operation to a two-operand instruction, you have a choice of which
child value to move into the result tmp. For example we might have:
@x = Add(@y, @z)
Assuming no three-operand add is available, we could either lower it to this:
Move %y, %x
Add %z, %x
or to this:
Move %z, %x
Add %y, %x
Which is better depends on the likelihood of coalescing with %x. If it's more likely that %y will
coalesce with %x, then we want to use the first form. Otherwise, we should use the second form.
This implements two heuristics for selecting the right form, and makes those heuristics reusable
within the B3->Air lowering by abstracting it as preferRightForResult(). For non-commutative
operations we must use the first form, so the first form is the default. The heuristics are:
- If the right child has only one user, then use the second form instead. This is profitable because
that means that @z dies at the Add, so using the second form means that the Move will be coalesced
away.
- If one of the children is a Phi that this operation (the Add in this case) flows into via some
Upsilon - possibly transitively through other Phis - then use the form that cases a Move on that
child. This overrides everything else, and is meant to optimize variables that accumulate in a
loop.
This required adding a reusable PhiChildren analysis, so I wrote one. It has an API that is mostly
based on iterators, and a higher-level API for looking at transitive children that is based on
functors.
I was originally implementing this for completeness, but when looking at how it interacted with
imaging-gaussian-blur, I realized the need for some heuristic for the loop-accumulator case. This
helps a lot on that benchmark. This widens the overall lead that B3 has on imaging-gaussian-blur, but
steady-state runs that exclude compile latency still show a slight deficit. That will most likely get
fixed by https://bugs.webkit.org/show_bug.cgi?id=151174.
No new tests because the commutativity appears to be covered by existing tests, and anyway, there are
no correctness implications to commuting a commutative operation.
* CMakeLists.txt:
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3LowerToAir.cpp:
(JSC::B3::Air::LowerToAir::LowerToAir):
(JSC::B3::Air::LowerToAir::canBeInternal):
(JSC::B3::Air::LowerToAir::appendUnOp):
(JSC::B3::Air::LowerToAir::preferRightForResult):
(JSC::B3::Air::LowerToAir::appendBinOp):
(JSC::B3::Air::LowerToAir::lower):
* b3/B3PhiChildren.cpp: Added.
(JSC::B3::PhiChildren::PhiChildren):
(JSC::B3::PhiChildren::~PhiChildren):
* b3/B3PhiChildren.h: Added.
(JSC::B3::PhiChildren::ValueCollection::ValueCollection):
(JSC::B3::PhiChildren::ValueCollection::size):
(JSC::B3::PhiChildren::ValueCollection::at):
(JSC::B3::PhiChildren::ValueCollection::operator[]):
(JSC::B3::PhiChildren::ValueCollection::contains):
(JSC::B3::PhiChildren::ValueCollection::iterator::iterator):
(JSC::B3::PhiChildren::ValueCollection::iterator::operator*):
(JSC::B3::PhiChildren::ValueCollection::iterator::operator++):
(JSC::B3::PhiChildren::ValueCollection::iterator::operator==):
(JSC::B3::PhiChildren::ValueCollection::iterator::operator!=):
(JSC::B3::PhiChildren::ValueCollection::begin):
(JSC::B3::PhiChildren::ValueCollection::end):
(JSC::B3::PhiChildren::UpsilonCollection::UpsilonCollection):
(JSC::B3::PhiChildren::UpsilonCollection::size):
(JSC::B3::PhiChildren::UpsilonCollection::at):
(JSC::B3::PhiChildren::UpsilonCollection::operator[]):
(JSC::B3::PhiChildren::UpsilonCollection::contains):
(JSC::B3::PhiChildren::UpsilonCollection::begin):
(JSC::B3::PhiChildren::UpsilonCollection::end):
(JSC::B3::PhiChildren::UpsilonCollection::values):
(JSC::B3::PhiChildren::UpsilonCollection::forAllTransitiveIncomingValues):
(JSC::B3::PhiChildren::UpsilonCollection::transitivelyUses):
(JSC::B3::PhiChildren::at):
(JSC::B3::PhiChildren::operator[]):
* b3/B3Procedure.cpp:
(JSC::B3::Procedure::Procedure):
* b3/B3Procedure.h:
* b3/B3UseCounts.cpp:
(JSC::B3::UseCounts::UseCounts):
* b3/B3UseCounts.h:
(JSC::B3::UseCounts::numUses):
(JSC::B3::UseCounts::numUsingInstructions):
(JSC::B3::UseCounts::operator[]): Deleted.</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreCMakeListstxt">trunk/Source/JavaScriptCore/CMakeLists.txt</a></li>
<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="#trunkSourceJavaScriptCoreb3B3LowerToAircpp">trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3UseCountscpp">trunk/Source/JavaScriptCore/b3/B3UseCounts.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3UseCountsh">trunk/Source/JavaScriptCore/b3/B3UseCounts.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3B3PhiChildrencpp">trunk/Source/JavaScriptCore/b3/B3PhiChildren.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3PhiChildrenh">trunk/Source/JavaScriptCore/b3/B3PhiChildren.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/CMakeLists.txt (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/CMakeLists.txt 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/CMakeLists.txt 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -121,6 +121,7 @@
</span><span class="cx"> b3/B3PatchpointSpecial.cpp
</span><span class="cx"> b3/B3PatchpointValue.cpp
</span><span class="cx"> b3/B3PhaseScope.cpp
</span><ins>+ b3/B3PhiChildren.cpp
</ins><span class="cx"> b3/B3Procedure.cpp
</span><span class="cx"> b3/B3ReduceStrength.cpp
</span><span class="cx"> b3/B3StackmapSpecial.cpp
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -1,5 +1,103 @@
</span><span class="cx"> 2015-11-30 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ B3 should be be clever about choosing which child to reuse for result in two-operand commutative operations
+ https://bugs.webkit.org/show_bug.cgi?id=151321
+
+ Reviewed by Geoffrey Garen.
+
+ When lowering a commutative operation to a two-operand instruction, you have a choice of which
+ child value to move into the result tmp. For example we might have:
+
+ @x = Add(@y, @z)
+
+ Assuming no three-operand add is available, we could either lower it to this:
+
+ Move %y, %x
+ Add %z, %x
+
+ or to this:
+
+ Move %z, %x
+ Add %y, %x
+
+ Which is better depends on the likelihood of coalescing with %x. If it's more likely that %y will
+ coalesce with %x, then we want to use the first form. Otherwise, we should use the second form.
+
+ This implements two heuristics for selecting the right form, and makes those heuristics reusable
+ within the B3->Air lowering by abstracting it as preferRightForResult(). For non-commutative
+ operations we must use the first form, so the first form is the default. The heuristics are:
+
+ - If the right child has only one user, then use the second form instead. This is profitable because
+ that means that @z dies at the Add, so using the second form means that the Move will be coalesced
+ away.
+
+ - If one of the children is a Phi that this operation (the Add in this case) flows into via some
+ Upsilon - possibly transitively through other Phis - then use the form that cases a Move on that
+ child. This overrides everything else, and is meant to optimize variables that accumulate in a
+ loop.
+
+ This required adding a reusable PhiChildren analysis, so I wrote one. It has an API that is mostly
+ based on iterators, and a higher-level API for looking at transitive children that is based on
+ functors.
+
+ I was originally implementing this for completeness, but when looking at how it interacted with
+ imaging-gaussian-blur, I realized the need for some heuristic for the loop-accumulator case. This
+ helps a lot on that benchmark. This widens the overall lead that B3 has on imaging-gaussian-blur, but
+ steady-state runs that exclude compile latency still show a slight deficit. That will most likely get
+ fixed by https://bugs.webkit.org/show_bug.cgi?id=151174.
+
+ No new tests because the commutativity appears to be covered by existing tests, and anyway, there are
+ no correctness implications to commuting a commutative operation.
+
+ * CMakeLists.txt:
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3LowerToAir.cpp:
+ (JSC::B3::Air::LowerToAir::LowerToAir):
+ (JSC::B3::Air::LowerToAir::canBeInternal):
+ (JSC::B3::Air::LowerToAir::appendUnOp):
+ (JSC::B3::Air::LowerToAir::preferRightForResult):
+ (JSC::B3::Air::LowerToAir::appendBinOp):
+ (JSC::B3::Air::LowerToAir::lower):
+ * b3/B3PhiChildren.cpp: Added.
+ (JSC::B3::PhiChildren::PhiChildren):
+ (JSC::B3::PhiChildren::~PhiChildren):
+ * b3/B3PhiChildren.h: Added.
+ (JSC::B3::PhiChildren::ValueCollection::ValueCollection):
+ (JSC::B3::PhiChildren::ValueCollection::size):
+ (JSC::B3::PhiChildren::ValueCollection::at):
+ (JSC::B3::PhiChildren::ValueCollection::operator[]):
+ (JSC::B3::PhiChildren::ValueCollection::contains):
+ (JSC::B3::PhiChildren::ValueCollection::iterator::iterator):
+ (JSC::B3::PhiChildren::ValueCollection::iterator::operator*):
+ (JSC::B3::PhiChildren::ValueCollection::iterator::operator++):
+ (JSC::B3::PhiChildren::ValueCollection::iterator::operator==):
+ (JSC::B3::PhiChildren::ValueCollection::iterator::operator!=):
+ (JSC::B3::PhiChildren::ValueCollection::begin):
+ (JSC::B3::PhiChildren::ValueCollection::end):
+ (JSC::B3::PhiChildren::UpsilonCollection::UpsilonCollection):
+ (JSC::B3::PhiChildren::UpsilonCollection::size):
+ (JSC::B3::PhiChildren::UpsilonCollection::at):
+ (JSC::B3::PhiChildren::UpsilonCollection::operator[]):
+ (JSC::B3::PhiChildren::UpsilonCollection::contains):
+ (JSC::B3::PhiChildren::UpsilonCollection::begin):
+ (JSC::B3::PhiChildren::UpsilonCollection::end):
+ (JSC::B3::PhiChildren::UpsilonCollection::values):
+ (JSC::B3::PhiChildren::UpsilonCollection::forAllTransitiveIncomingValues):
+ (JSC::B3::PhiChildren::UpsilonCollection::transitivelyUses):
+ (JSC::B3::PhiChildren::at):
+ (JSC::B3::PhiChildren::operator[]):
+ * b3/B3Procedure.cpp:
+ (JSC::B3::Procedure::Procedure):
+ * b3/B3Procedure.h:
+ * b3/B3UseCounts.cpp:
+ (JSC::B3::UseCounts::UseCounts):
+ * b3/B3UseCounts.h:
+ (JSC::B3::UseCounts::numUses):
+ (JSC::B3::UseCounts::numUsingInstructions):
+ (JSC::B3::UseCounts::operator[]): Deleted.
+
+2015-11-30 Filip Pizlo <fpizlo@apple.com>
+
</ins><span class="cx"> REGRESSION(r192812): This change seems to have broken the iOS builds (Requested by ryanhaddad on #webkit).
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=151669
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -306,6 +306,8 @@
</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><span class="cx"> 0F34B14A16D42013001CDA5A /* DFGUseKind.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F34B14816D4200E001CDA5A /* DFGUseKind.h */; };
</span><ins>+ 0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F37308A1C0BD29100052BFA /* B3PhiChildren.cpp */; };
+ 0F37308D1C0BD29100052BFA /* B3PhiChildren.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F37308B1C0BD29100052BFA /* B3PhiChildren.h */; };
</ins><span class="cx"> 0F37308F1C0CD68500052BFA /* DisallowMacroScratchRegisterUsage.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F37308E1C0CD68500052BFA /* DisallowMacroScratchRegisterUsage.h */; };
</span><span class="cx"> 0F3730911C0CD70C00052BFA /* AllowMacroScratchRegisterUsage.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3730901C0CD70C00052BFA /* AllowMacroScratchRegisterUsage.h */; };
</span><span class="cx"> 0F38B01117CF078000B144D3 /* LLIntEntrypoint.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */; };
</span><span class="lines">@@ -2369,6 +2371,8 @@
</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><span class="cx"> 0F34B14816D4200E001CDA5A /* DFGUseKind.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = DFGUseKind.h; path = dfg/DFGUseKind.h; sourceTree = "<group>"; };
</span><ins>+ 0F37308A1C0BD29100052BFA /* B3PhiChildren.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = B3PhiChildren.cpp; path = b3/B3PhiChildren.cpp; sourceTree = "<group>"; };
+ 0F37308B1C0BD29100052BFA /* B3PhiChildren.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3PhiChildren.h; path = b3/B3PhiChildren.h; sourceTree = "<group>"; };
</ins><span class="cx"> 0F37308E1C0CD68500052BFA /* DisallowMacroScratchRegisterUsage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DisallowMacroScratchRegisterUsage.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F3730901C0CD70C00052BFA /* AllowMacroScratchRegisterUsage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AllowMacroScratchRegisterUsage.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F38B00F17CF077F00B144D3 /* LLIntEntrypoint.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; name = LLIntEntrypoint.cpp; path = llint/LLIntEntrypoint.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -4548,6 +4552,8 @@
</span><span class="cx"> 0FEC84DE1BDACDAC0080FF74 /* B3PatchpointValue.h */,
</span><span class="cx"> 0FEC84DF1BDACDAC0080FF74 /* B3PhaseScope.cpp */,
</span><span class="cx"> 0FEC84E01BDACDAC0080FF74 /* B3PhaseScope.h */,
</span><ins>+ 0F37308A1C0BD29100052BFA /* B3PhiChildren.cpp */,
+ 0F37308B1C0BD29100052BFA /* B3PhiChildren.h */,
</ins><span class="cx"> 0FEC84E11BDACDAC0080FF74 /* B3Procedure.cpp */,
</span><span class="cx"> 0FEC84E21BDACDAC0080FF74 /* B3Procedure.h */,
</span><span class="cx"> 0FEC84E31BDACDAC0080FF74 /* B3ProcedureInlines.h */,
</span><span class="lines">@@ -6899,6 +6905,7 @@
</span><span class="cx"> 0F3B3A281544C997003ED0FF /* DFGCFGSimplificationPhase.h in Headers */,
</span><span class="cx"> 0F9D36951AE9CC33000D4DFB /* DFGCleanUpPhase.h in Headers */,
</span><span class="cx"> A77A424017A0BBFD00A8DB81 /* DFGClobberize.h in Headers */,
</span><ins>+ 0F37308D1C0BD29100052BFA /* B3PhiChildren.h in Headers */,
</ins><span class="cx"> A77A424217A0BBFD00A8DB81 /* DFGClobberSet.h in Headers */,
</span><span class="cx"> 0F3C1F1B1B868E7900ABB08B /* DFGClobbersExitState.h in Headers */,
</span><span class="cx"> 0F04396E1B03DC0B009598B7 /* DFGCombinedLiveness.h in Headers */,
</span><span class="lines">@@ -8834,6 +8841,7 @@
</span><span class="cx"> 14D2F3DA139F4BE200491031 /* MarkedSpace.cpp in Sources */,
</span><span class="cx"> 142D6F1113539A4100B02E86 /* MarkStack.cpp in Sources */,
</span><span class="cx"> 4340A4841A9051AF00D73CCA /* MathCommon.cpp in Sources */,
</span><ins>+ 0F37308C1C0BD29100052BFA /* B3PhiChildren.cpp in Sources */,
</ins><span class="cx"> 14469DDF107EC7E700650446 /* MathObject.cpp in Sources */,
</span><span class="cx"> 90213E3D123A40C200D422F3 /* MemoryStatistics.cpp in Sources */,
</span><span class="cx"> 0FB5467D14F5CFD6002C2989 /* MethodOfGettingAValueProfile.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3LowerToAircpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/b3/B3LowerToAir.cpp 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -44,6 +44,7 @@
</span><span class="cx"> #include "B3PatchpointSpecial.h"
</span><span class="cx"> #include "B3PatchpointValue.h"
</span><span class="cx"> #include "B3PhaseScope.h"
</span><ins>+#include "B3PhiChildren.h"
</ins><span class="cx"> #include "B3Procedure.h"
</span><span class="cx"> #include "B3StackSlotValue.h"
</span><span class="cx"> #include "B3UpsilonValue.h"
</span><span class="lines">@@ -65,6 +66,7 @@
</span><span class="cx"> : m_valueToTmp(procedure.values().size())
</span><span class="cx"> , m_blockToBlock(procedure.size())
</span><span class="cx"> , m_useCounts(procedure)
</span><ins>+ , m_phiChildren(procedure)
</ins><span class="cx"> , m_procedure(procedure)
</span><span class="cx"> , m_code(procedure.code())
</span><span class="cx"> {
</span><span class="lines">@@ -317,8 +319,11 @@
</span><span class="cx"> if (m_valueToTmp[value])
</span><span class="cx"> return false;
</span><span class="cx">
</span><del>- // We require internals to have only one use - us.
- if (m_useCounts[value] != 1)
</del><ins>+ // We require internals to have only one use - us. It's not clear if this should be numUses() or
+ // numUsingInstructions(). Ideally, it would be numUsingInstructions(), except that it's not clear
+ // if we'd actually do the right thing when matching over such a DAG pattern. For now, it simply
+ // doesn't matter because we don't implement patterns that would trigger this.
+ if (m_useCounts.numUses(value) != 1)
</ins><span class="cx"> return false;
</span><span class="cx">
</span><span class="cx"> return true;
</span><span class="lines">@@ -525,6 +530,36 @@
</span><span class="cx"> append(opcode, result);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Call this method when doing two-operand lowering of a commutative operation. You have a choice of
+ // which incoming Value is moved into the result. This will select which one is likely to be most
+ // profitable to use as the result. Doing the right thing can have big performance consequences in tight
+ // kernels.
+ bool preferRightForResult(Value* left, Value* right)
+ {
+ // The default is to move left into result, because that's required for non-commutative instructions.
+ // The value that we want to move into result position is the one that dies here. So, if we're
+ // compiling a commutative operation and we know that actually right is the one that dies right here,
+ // then we can flip things around to help coalescing, which then kills the move instruction.
+ //
+ // But it's more complicated:
+ // - Used-once is a bad estimate of whether the variable dies here.
+ // - A child might be a candidate for coalescing with this value.
+ //
+ // Currently, we have machinery in place to recognize super obvious forms of the latter issue.
+
+ bool result = m_useCounts.numUsingInstructions(right) == 1;
+
+ // We recognize when a child is a Phi that has this value as one of its children. We're very
+ // conservative about this; for example we don't even consider transitive Phi children.
+ bool leftIsPhiWithThis = m_phiChildren[left].transitivelyUses(m_value);
+ bool rightIsPhiWithThis = m_phiChildren[right].transitivelyUses(m_value);
+
+ if (leftIsPhiWithThis != rightIsPhiWithThis)
+ result = rightIsPhiWithThis;
+
+ return result;
+ }
+
</ins><span class="cx"> template<
</span><span class="cx"> Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble,
</span><span class="cx"> Commutativity commutativity = NotCommutative>
</span><span class="lines">@@ -598,9 +633,11 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // FIXME: If we're going to use a two-operand instruction, and the operand is commutative, we
- // should coalesce the result with the operand that is killed.
- // https://bugs.webkit.org/show_bug.cgi?id=151321
</del><ins>+ if (commutativity == Commutative && preferRightForResult(left, right)) {
+ append(relaxedMoveForType(m_value->type()), tmp(right), result);
+ append(opcode, tmp(left), result);
+ return;
+ }
</ins><span class="cx">
</span><span class="cx"> append(relaxedMoveForType(m_value->type()), tmp(left), result);
</span><span class="cx"> append(opcode, tmp(right), result);
</span><span class="lines">@@ -1658,7 +1695,8 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> case CheckAdd:
</span><del>- case CheckSub: {
</del><ins>+ case CheckSub:
+ case CheckMul: {
</ins><span class="cx"> CheckValue* checkValue = m_value->as<CheckValue>();
</span><span class="cx">
</span><span class="cx"> Value* left = checkValue->child(0);
</span><span class="lines">@@ -1684,19 +1722,21 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // FIXME: Use commutativity of CheckAdd to increase the likelihood of coalescing.
- // https://bugs.webkit.org/show_bug.cgi?id=151321
-
- append(Move, tmp(left), result);
-
</del><span class="cx"> Air::Opcode opcode = Air::Oops;
</span><ins>+ Commutativity commutativity = NotCommutative;
+ Arg::Role stackmapRole = Arg::Use;
</ins><span class="cx"> switch (m_value->opcode()) {
</span><span class="cx"> case CheckAdd:
</span><span class="cx"> opcode = opcodeForType(BranchAdd32, BranchAdd64, Air::Oops, m_value->type());
</span><ins>+ commutativity = Commutative;
</ins><span class="cx"> break;
</span><span class="cx"> case CheckSub:
</span><span class="cx"> opcode = opcodeForType(BranchSub32, BranchSub64, Air::Oops, m_value->type());
</span><span class="cx"> break;
</span><ins>+ case CheckMul:
+ opcode = opcodeForType(BranchMul32, BranchMul64, Air::Oops, checkValue->type());
+ stackmapRole = Arg::LateUse;
+ break;
</ins><span class="cx"> default:
</span><span class="cx"> RELEASE_ASSERT_NOT_REACHED();
</span><span class="cx"> break;
</span><span class="lines">@@ -1707,11 +1747,20 @@
</span><span class="cx"> // this rule here.
</span><span class="cx"> // https://bugs.webkit.org/show_bug.cgi?id=151228
</span><span class="cx">
</span><del>- Arg source;
- if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Imm, Arg::Tmp))
- source = imm(right);
- else
- source = tmp(right);
</del><ins>+ Vector<Arg, 2> sources;
+ if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Tmp, Arg::Imm, Arg::Tmp)) {
+ sources.append(tmp(left));
+ sources.append(imm(right));
+ } else if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Imm, Arg::Tmp)) {
+ sources.append(imm(right));
+ append(Move, tmp(left), result);
+ } else if (commutativity == Commutative && preferRightForResult(left, right)) {
+ sources.append(tmp(left));
+ append(Move, tmp(right), result);
+ } else {
+ sources.append(tmp(right));
+ append(Move, tmp(left), result);
+ }
</ins><span class="cx">
</span><span class="cx"> // There is a really hilarious case that arises when we do BranchAdd32(%x, %x). We won't emit
</span><span class="cx"> // such code, but the coalescing in our register allocator also does copy propagation, so
</span><span class="lines">@@ -1736,13 +1785,13 @@
</span><span class="cx"> // optimizations remove other Move's or identity-like operations. That's why we don't use
</span><span class="cx"> // LateUse here to take care of add-to-self.
</span><span class="cx">
</span><del>- CheckSpecial* special = ensureCheckSpecial(opcode, 3);
</del><ins>+ CheckSpecial* special = ensureCheckSpecial(opcode, 2 + sources.size(), stackmapRole);
</ins><span class="cx">
</span><span class="cx"> Inst inst(Patch, checkValue, Arg::special(special));
</span><span class="cx">
</span><span class="cx"> inst.args.append(Arg::resCond(MacroAssembler::Overflow));
</span><span class="cx">
</span><del>- inst.args.append(source);
</del><ins>+ inst.args.appendVector(sources);
</ins><span class="cx"> inst.args.append(result);
</span><span class="cx">
</span><span class="cx"> fillStackmap(inst, checkValue, 2);
</span><span class="lines">@@ -1751,34 +1800,6 @@
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- case CheckMul: {
- CheckValue* checkValue = m_value->as<CheckValue>();
-
- Value* left = checkValue->child(0);
- Value* right = checkValue->child(1);
-
- Tmp result = tmp(m_value);
-
- Air::Opcode opcode =
- opcodeForType(BranchMul32, BranchMul64, Air::Oops, checkValue->type());
- CheckSpecial* special = ensureCheckSpecial(opcode, 3, Arg::LateUse);
-
- // FIXME: Handle immediates.
- // https://bugs.webkit.org/show_bug.cgi?id=151230
-
- append(Move, tmp(left), result);
-
- Inst inst(Patch, checkValue, Arg::special(special));
- inst.args.append(Arg::resCond(MacroAssembler::Overflow));
- inst.args.append(tmp(right));
- inst.args.append(result);
-
- fillStackmap(inst, checkValue, 2);
-
- m_insts.last().append(WTF::move(inst));
- return;
- }
-
</del><span class="cx"> case Check: {
</span><span class="cx"> Inst branch = createBranch(m_value->child(0));
</span><span class="cx">
</span><span class="lines">@@ -1858,6 +1879,7 @@
</span><span class="cx"> HashMap<StackSlotValue*, Air::StackSlot*> m_stackToStack;
</span><span class="cx">
</span><span class="cx"> UseCounts m_useCounts;
</span><ins>+ PhiChildren m_phiChildren;
</ins><span class="cx">
</span><span class="cx"> Vector<Vector<Inst, 4>> m_insts;
</span><span class="cx"> Vector<Inst> m_prologue;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3PhiChildrencpp"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3PhiChildren.cpp (0 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3PhiChildren.cpp (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3PhiChildren.cpp 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -0,0 +1,51 @@
</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 "B3PhiChildren.h"
+
+#if ENABLE(B3_JIT)
+
+#include "B3ValueInlines.h"
+
+namespace JSC { namespace B3 {
+
+PhiChildren::PhiChildren(Procedure& proc)
+ : m_upsilons(proc.values().size())
+{
+ for (Value* value : proc.values()) {
+ if (UpsilonValue* upsilon = value->as<UpsilonValue>())
+ m_upsilons[upsilon->phi()].append(upsilon);
+ }
+}
+
+PhiChildren::~PhiChildren()
+{
+}
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3PhiChildrenh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/B3PhiChildren.h (0 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3PhiChildren.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/B3PhiChildren.h 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -0,0 +1,178 @@
</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 B3PhiChildren_h
+#define B3PhiChildren_h
+
+#if ENABLE(B3_JIT)
+
+#include "B3IndexMap.h"
+#include "B3Procedure.h"
+#include "B3UpsilonValue.h"
+#include <wtf/GraphNodeWorklist.h>
+
+namespace JSC { namespace B3 {
+
+class PhiChildren {
+public:
+ PhiChildren(Procedure&);
+ ~PhiChildren();
+
+ class ValueCollection {
+ public:
+ ValueCollection(Vector<UpsilonValue*>* values = nullptr)
+ : m_values(values)
+ {
+ }
+
+ unsigned size() const { return m_values->size(); }
+ Value* at(unsigned index) const { return m_values->at(index)->child(0); }
+ Value* operator[](unsigned index) const { return at(index); }
+
+ bool contains(Value* value) const
+ {
+ for (unsigned i = size(); i--;) {
+ if (at(i) == value)
+ return true;
+ }
+ return false;
+ }
+
+ class iterator {
+ public:
+ iterator(Vector<UpsilonValue*>* values = nullptr, unsigned index = 0)
+ : m_values(values)
+ , m_index(index)
+ {
+ }
+
+ Value* operator*() const
+ {
+ return m_values->at(m_index)->child(0);
+ }
+
+ iterator& operator++()
+ {
+ m_index++;
+ return *this;
+ }
+
+ bool operator==(const iterator& other) const
+ {
+ ASSERT(m_values == other.m_values);
+ return m_index == other.m_index;
+ }
+
+ bool operator!=(const iterator& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ Vector<UpsilonValue*>* m_values;
+ unsigned m_index;
+ };
+
+ iterator begin() const { return iterator(m_values); }
+ iterator end() const { return iterator(m_values, m_values->size()); }
+
+ private:
+ Vector<UpsilonValue*>* m_values;
+ };
+
+ class UpsilonCollection {
+ public:
+ UpsilonCollection()
+ {
+ }
+
+ UpsilonCollection(PhiChildren* phiChildren, Value* value, Vector<UpsilonValue*>* values)
+ : m_phiChildren(phiChildren)
+ , m_value(value)
+ , m_values(values)
+ {
+ }
+
+ unsigned size() const { return m_values->size(); }
+ Value* at(unsigned index) const { return m_values->at(index); }
+ Value* operator[](unsigned index) const { return at(index); }
+
+ bool contains(Value* value) const { return m_values->contains(value); }
+
+ typedef Vector<UpsilonValue*>::const_iterator iterator;
+ Vector<UpsilonValue*>::const_iterator begin() const { return m_values->begin(); }
+ Vector<UpsilonValue*>::const_iterator end() const { return m_values->end(); }
+
+ ValueCollection values() { return ValueCollection(m_values); }
+
+ template<typename Functor>
+ void forAllTransitiveIncomingValues(const Functor& functor)
+ {
+ if (m_value->opcode() != Phi) {
+ functor(m_value);
+ return;
+ }
+
+ GraphNodeWorklist<Value*> worklist;
+ worklist.push(m_value);
+ while (Value* phi = worklist.pop()) {
+ for (Value* child : m_phiChildren->at(phi).values()) {
+ if (child->opcode() == Phi)
+ worklist.push(child);
+ else
+ functor(child);
+ }
+ }
+ }
+
+ bool transitivelyUses(Value* candidate)
+ {
+ bool result = false;
+ forAllTransitiveIncomingValues(
+ [&] (Value* child) {
+ result |= child == candidate;
+ });
+ return result;
+ }
+
+ private:
+ PhiChildren* m_phiChildren { nullptr };
+ Value* m_value { nullptr };
+ Vector<UpsilonValue*>* m_values { nullptr };
+ };
+
+ UpsilonCollection at(Value* value) { return UpsilonCollection(this, value, &m_upsilons[value]); }
+ UpsilonCollection operator[](Value* value) { return at(value); }
+
+private:
+ IndexMap<Value, Vector<UpsilonValue*>> m_upsilons;
+};
+
+} } // namespace JSC::B3
+
+#endif // ENABLE(B3_JIT)
+
+#endif // B3PhiChildren_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3UseCountscpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3UseCounts.cpp (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3UseCounts.cpp 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/b3/B3UseCounts.cpp 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -35,11 +35,22 @@
</span><span class="cx"> UseCounts::UseCounts(Procedure& procedure)
</span><span class="cx"> : m_counts(procedure.values().size())
</span><span class="cx"> {
</span><del>- for (Value* value : procedure.values())
- ASSERT_UNUSED(value, !m_counts[value]);
</del><ins>+ Vector<Value*, 64> children;
</ins><span class="cx"> for (Value* value : procedure.values()) {
</span><del>- for (Value* child : value->children())
- m_counts[child]++;
</del><ins>+ children.resize(0);
+ for (Value* child : value->children()) {
+ m_counts[child].numUses++;
+ children.append(child);
+ }
+ std::sort(children.begin(), children.end());
+ Value* last = nullptr;
+ for (Value* child : children) {
+ if (child == last)
+ continue;
+
+ m_counts[child].numUsingInstructions++;
+ last = child;
+ }
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3UseCountsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3UseCounts.h (192815 => 192816)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3UseCounts.h 2015-11-30 20:45:03 UTC (rev 192815)
+++ trunk/Source/JavaScriptCore/b3/B3UseCounts.h 2015-11-30 21:05:25 UTC (rev 192816)
</span><span class="lines">@@ -40,12 +40,16 @@
</span><span class="cx"> UseCounts(Procedure&);
</span><span class="cx"> ~UseCounts();
</span><span class="cx">
</span><del>- unsigned operator[](Value* value) const
- {
- return m_counts[value];
- }
</del><ins>+ unsigned numUses(Value* value) const { return m_counts[value].numUses; }
+ unsigned numUsingInstructions(Value* value) const { return m_counts[value].numUsingInstructions; }
+
</ins><span class="cx"> private:
</span><del>- IndexMap<Value, unsigned> m_counts;
</del><ins>+ struct Counts {
+ unsigned numUses { 0 };
+ unsigned numUsingInstructions { 0 };
+ };
+
+ IndexMap<Value, Counts> m_counts;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> } } // namespace JSC::B3
</span></span></pre>
</div>
</div>
</body>
</html>