<!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>[192863] 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/192863">192863</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-11-30 23:03:55 -0800 (Mon, 30 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>B3::ValueRep::Any should translate into a Arg::ColdUse role in Air
https://bugs.webkit.org/show_bug.cgi?id=151174
Reviewed by Geoffrey Garen and Benjamin Poulain.
This teaches the register allocator that it should pick spills based on whichever tmp has the
highest score:
score(tmp) = degree(tmp) / sum(for each use of tmp, block->frequency)
In other words, the numerator is the number of edges in the inteference graph and the denominator
is an estimate of the dynamic number of uses.
This also extends Arg::Role to know that there is such a thing as ColdUse, i.e. a Use that
doesn't count as such for the above formula. Because LateUse is always used in contexts where we
want it to be Cold, I've defined LateUse to imply ColdUse.
This gets rid of all spilling inside the hot loop in Kraken/imaging-gaussian-blur. But more
importantly, it makes our register allocator use a well-known heuristic based on reusable
building blocks like the new Air::UseCounts. Even if the heuristic is slightly wrong, the right
heuristic probably uses the same building blocks.
* JavaScriptCore.xcodeproj/project.pbxproj:
* b3/B3StackmapSpecial.cpp:
(JSC::B3::StackmapSpecial::forEachArgImpl):
* b3/B3ValueRep.h:
* b3/air/AirArg.cpp:
(WTF::printInternal):
* b3/air/AirArg.h:
(JSC::B3::Air::Arg::isAnyUse):
(JSC::B3::Air::Arg::isColdUse):
(JSC::B3::Air::Arg::isWarmUse):
(JSC::B3::Air::Arg::isEarlyUse):
(JSC::B3::Air::Arg::isDef):
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::iteratedRegisterCoalescing):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator): Deleted.
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg): Deleted.
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize): Deleted.
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees): Deleted.
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::build): Deleted.
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill): Deleted.
(JSC::B3::Air::isUselessMoveInst): Deleted.
(JSC::B3::Air::assignRegisterToTmpInProgram): Deleted.
(JSC::B3::Air::addSpillAndFillToProgram): Deleted.
(JSC::B3::Air::iteratedRegisterCoalescingOnType): Deleted.
* b3/air/AirLiveness.h:
* b3/air/AirSpillEverything.cpp:
(JSC::B3::Air::spillEverything):
* b3/air/AirUseCounts.h: Added.
(JSC::B3::Air::UseCounts::Counts::dump):
(JSC::B3::Air::UseCounts::UseCounts):
(JSC::B3::Air::UseCounts::operator[]):
(JSC::B3::Air::UseCounts::dump):
* runtime/Options.h:</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="#trunkSourceJavaScriptCoreb3B3StackmapSpecialcpp">trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3B3ValueReph">trunk/Source/JavaScriptCore/b3/B3ValueRep.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirArgcpp">trunk/Source/JavaScriptCore/b3/air/AirArg.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirArgh">trunk/Source/JavaScriptCore/b3/air/AirArg.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirLivenessh">trunk/Source/JavaScriptCore/b3/air/AirLiveness.h</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirSpillEverythingcpp">trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeOptionsh">trunk/Source/JavaScriptCore/runtime/Options.h</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreb3airAirUseCountsh">trunk/Source/JavaScriptCore/b3/air/AirUseCounts.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -1,3 +1,61 @@
</span><ins>+2015-11-30 Filip Pizlo <fpizlo@apple.com>
+
+ B3::ValueRep::Any should translate into a Arg::ColdUse role in Air
+ https://bugs.webkit.org/show_bug.cgi?id=151174
+
+ Reviewed by Geoffrey Garen and Benjamin Poulain.
+
+ This teaches the register allocator that it should pick spills based on whichever tmp has the
+ highest score:
+
+ score(tmp) = degree(tmp) / sum(for each use of tmp, block->frequency)
+
+ In other words, the numerator is the number of edges in the inteference graph and the denominator
+ is an estimate of the dynamic number of uses.
+
+ This also extends Arg::Role to know that there is such a thing as ColdUse, i.e. a Use that
+ doesn't count as such for the above formula. Because LateUse is always used in contexts where we
+ want it to be Cold, I've defined LateUse to imply ColdUse.
+
+ This gets rid of all spilling inside the hot loop in Kraken/imaging-gaussian-blur. But more
+ importantly, it makes our register allocator use a well-known heuristic based on reusable
+ building blocks like the new Air::UseCounts. Even if the heuristic is slightly wrong, the right
+ heuristic probably uses the same building blocks.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj:
+ * b3/B3StackmapSpecial.cpp:
+ (JSC::B3::StackmapSpecial::forEachArgImpl):
+ * b3/B3ValueRep.h:
+ * b3/air/AirArg.cpp:
+ (WTF::printInternal):
+ * b3/air/AirArg.h:
+ (JSC::B3::Air::Arg::isAnyUse):
+ (JSC::B3::Air::Arg::isColdUse):
+ (JSC::B3::Air::Arg::isWarmUse):
+ (JSC::B3::Air::Arg::isEarlyUse):
+ (JSC::B3::Air::Arg::isDef):
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::iteratedRegisterCoalescing):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::IteratedRegisterCoalescingAllocator): Deleted.
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocatedReg): Deleted.
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::tmpArraySize): Deleted.
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::initializeDegrees): Deleted.
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build): Deleted.
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill): Deleted.
+ (JSC::B3::Air::isUselessMoveInst): Deleted.
+ (JSC::B3::Air::assignRegisterToTmpInProgram): Deleted.
+ (JSC::B3::Air::addSpillAndFillToProgram): Deleted.
+ (JSC::B3::Air::iteratedRegisterCoalescingOnType): Deleted.
+ * b3/air/AirLiveness.h:
+ * b3/air/AirSpillEverything.cpp:
+ (JSC::B3::Air::spillEverything):
+ * b3/air/AirUseCounts.h: Added.
+ (JSC::B3::Air::UseCounts::Counts::dump):
+ (JSC::B3::Air::UseCounts::UseCounts):
+ (JSC::B3::Air::UseCounts::operator[]):
+ (JSC::B3::Air::UseCounts::dump):
+ * runtime/Options.h:
+
</ins><span class="cx"> 2015-11-30 Csaba Osztrogonác <ossy@webkit.org>
</span><span class="cx">
</span><span class="cx"> Fix the !ENABLE(DFG_JIT) build after r192699
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreJavaScriptCorexcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -310,6 +310,7 @@
</span><span class="cx"> 0F37308D1C0BD29100052BFA /* B3PhiChildren.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F37308B1C0BD29100052BFA /* B3PhiChildren.h */; };
</span><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><ins>+ 0F3730931C0D67EE00052BFA /* AirUseCounts.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F3730921C0D67EE00052BFA /* AirUseCounts.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">@@ -2378,6 +2379,7 @@
</span><span class="cx"> 0F37308B1C0BD29100052BFA /* B3PhiChildren.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = B3PhiChildren.h; path = b3/B3PhiChildren.h; sourceTree = "<group>"; };
</span><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><ins>+ 0F3730921C0D67EE00052BFA /* AirUseCounts.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirUseCounts.h; path = b3/air/AirUseCounts.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">@@ -4652,6 +4654,7 @@
</span><span class="cx"> 0FEC85681BDACDC70080FF74 /* AirTmp.cpp */,
</span><span class="cx"> 0FEC85691BDACDC70080FF74 /* AirTmp.h */,
</span><span class="cx"> 0FEC856A1BDACDC70080FF74 /* AirTmpInlines.h */,
</span><ins>+ 0F3730921C0D67EE00052BFA /* AirUseCounts.h */,
</ins><span class="cx"> 0FEC856B1BDACDC70080FF74 /* AirValidate.cpp */,
</span><span class="cx"> 0FEC856C1BDACDC70080FF74 /* AirValidate.h */,
</span><span class="cx"> );
</span><span class="lines">@@ -6665,6 +6668,7 @@
</span><span class="cx"> 0F338E161BF0276C0013C88F /* B3ValueKeyInlines.h in Headers */,
</span><span class="cx"> 0FEC85741BDACDC70080FF74 /* AirCCallSpecial.h in Headers */,
</span><span class="cx"> 0FEC85761BDACDC70080FF74 /* AirCode.h in Headers */,
</span><ins>+ 0F3730931C0D67EE00052BFA /* AirUseCounts.h in Headers */,
</ins><span class="cx"> 0F4570391BE44C910062A629 /* AirEliminateDeadCode.h in Headers */,
</span><span class="cx"> 0FEC85771BDACDC70080FF74 /* AirFrequentedBlock.h in Headers */,
</span><span class="cx"> 0FEC85791BDACDC70080FF74 /* AirGenerate.h in Headers */,
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3StackmapSpecialcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.cpp (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.cpp 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/B3StackmapSpecial.cpp 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -75,7 +75,8 @@
</span><span class="cx"> unsigned numIgnoredB3Args, unsigned numIgnoredAirArgs,
</span><span class="cx"> Inst& inst, Arg::Role role, const ScopedLambda<Inst::EachArgCallback>& callback)
</span><span class="cx"> {
</span><del>- Value* value = inst.origin;
</del><ins>+ StackmapValue* value = inst.origin->as<StackmapValue>();
+ ASSERT(value);
</ins><span class="cx">
</span><span class="cx"> // Check that insane things have not happened.
</span><span class="cx"> ASSERT(inst.args.size() >= numIgnoredAirArgs);
</span><span class="lines">@@ -84,9 +85,15 @@
</span><span class="cx">
</span><span class="cx"> for (unsigned i = 0; i < inst.args.size() - numIgnoredAirArgs; ++i) {
</span><span class="cx"> Arg& arg = inst.args[i + numIgnoredAirArgs];
</span><del>- Value* child = value->child(i + numIgnoredB3Args);
</del><ins>+ ConstrainedValue child = value->constrainedChild(i + numIgnoredB3Args);
</ins><span class="cx">
</span><del>- callback(arg, role, Arg::typeForB3Type(child->type()));
</del><ins>+ Arg::Role thisRole = role;
+
+ // Cool down the role if the use is cold.
+ if (child.rep().kind() == ValueRep::Any && thisRole == Arg::Use)
+ thisRole = Arg::ColdUse;
+
+ callback(arg, role, Arg::typeForB3Type(child.value()->type()));
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3B3ValueReph"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/B3ValueRep.h (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/B3ValueRep.h 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/B3ValueRep.h 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -43,9 +43,10 @@
</span><span class="cx"> class ValueRep {
</span><span class="cx"> public:
</span><span class="cx"> enum Kind {
</span><del>- // As an input representation, this means that B3 can pick any representation. As an
- // output representation, this means that we don't know. This will only arise for the
- // right operand (i.e. child(1)) of a CheckMul.
</del><ins>+ // As an input representation, this means that B3 can pick any representation. It also currently
+ // implies that the use is cold: the register allocator doesn't count it. As an output
+ // representation, this means that we don't know. This will only arise as an output
+ // representation for the active arguments of Check/CheckAdd/CheckSub/CheckMul.
</ins><span class="cx"> Any,
</span><span class="cx">
</span><span class="cx"> // As an input representation, this means that B3 should pick some register. It could be a
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirArgcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirArg.cpp (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirArg.cpp 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/air/AirArg.cpp 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -181,6 +181,9 @@
</span><span class="cx"> case Arg::UseAddr:
</span><span class="cx"> out.print("UseAddr");
</span><span class="cx"> return;
</span><ins>+ case Arg::ColdUse:
+ out.print("ColdUse");
+ return;
</ins><span class="cx"> case Arg::LateUse:
</span><span class="cx"> out.print("LateUse");
</span><span class="cx"> return;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirArgh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirArg.h (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirArg.h 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/air/AirArg.h 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -83,8 +83,13 @@
</span><span class="cx"> // always escaping, and Stack is presumed to be always escaping if it's Locked.
</span><span class="cx"> Use,
</span><span class="cx">
</span><ins>+ // Exactly like Use, except that it also implies that the use is cold: that is, replacing the
+ // use with something on the stack is free.
+ ColdUse,
+
</ins><span class="cx"> // LateUse means that the Inst will read from this value after doing its Def's. Note that LateUse
</span><del>- // on an Addr or Index still means Use on the internal temporaries.
</del><ins>+ // on an Addr or Index still means Use on the internal temporaries. LateUse also currently also
+ // implies ColdUse.
</ins><span class="cx"> LateUse,
</span><span class="cx">
</span><span class="cx"> // Def means that the Inst will write to this value after doing everything else.
</span><span class="lines">@@ -132,6 +137,7 @@
</span><span class="cx"> {
</span><span class="cx"> switch (role) {
</span><span class="cx"> case Use:
</span><ins>+ case ColdUse:
</ins><span class="cx"> case UseDef:
</span><span class="cx"> case LateUse:
</span><span class="cx"> return true;
</span><span class="lines">@@ -141,11 +147,31 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ static bool isColdUse(Role role)
+ {
+ switch (role) {
+ case ColdUse:
+ case LateUse:
+ return true;
+ case Use:
+ case UseDef:
+ case Def:
+ case UseAddr:
+ return false;
+ }
+ }
+
+ static bool isWarmUse(Role role)
+ {
+ return isAnyUse(role) && !isColdUse(role);
+ }
+
</ins><span class="cx"> // Returns true if the Role implies that the Inst will Use the Arg before doing anything else.
</span><span class="cx"> static bool isEarlyUse(Role role)
</span><span class="cx"> {
</span><span class="cx"> switch (role) {
</span><span class="cx"> case Use:
</span><ins>+ case ColdUse:
</ins><span class="cx"> case UseDef:
</span><span class="cx"> return true;
</span><span class="cx"> case Def:
</span><span class="lines">@@ -166,6 +192,7 @@
</span><span class="cx"> {
</span><span class="cx"> switch (role) {
</span><span class="cx"> case Use:
</span><ins>+ case ColdUse:
</ins><span class="cx"> case UseAddr:
</span><span class="cx"> case LateUse:
</span><span class="cx"> return false;
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -35,15 +35,18 @@
</span><span class="cx"> #include "AirPhaseScope.h"
</span><span class="cx"> #include "AirRegisterPriority.h"
</span><span class="cx"> #include "AirTmpInlines.h"
</span><ins>+#include "AirUseCounts.h"
</ins><span class="cx"> #include <wtf/ListDump.h>
</span><span class="cx"> #include <wtf/ListHashSet.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC { namespace B3 { namespace Air {
</span><span class="cx">
</span><del>-static bool debug = false;
-static bool traceDebug = false;
-static bool reportStats = false;
</del><ins>+namespace {
</ins><span class="cx">
</span><ins>+bool debug = false;
+bool traceDebug = false;
+bool reportStats = false;
+
</ins><span class="cx"> template<Arg::Type type>
</span><span class="cx"> struct MoveInstHelper;
</span><span class="cx">
</span><span class="lines">@@ -81,19 +84,22 @@
</span><span class="cx"> template<Arg::Type type>
</span><span class="cx"> class IteratedRegisterCoalescingAllocator {
</span><span class="cx"> public:
</span><del>- IteratedRegisterCoalescingAllocator(Code& code, const HashSet<Tmp>& unspillableTmp)
- : m_unspillableTmp(unspillableTmp)
</del><ins>+ IteratedRegisterCoalescingAllocator(
+ Code& code, const UseCounts<Tmp>& useCounts, const HashSet<Tmp>& unspillableTmp)
+ : m_code(code)
+ , m_useCounts(useCounts)
+ , m_unspillableTmp(unspillableTmp)
</ins><span class="cx"> , m_numberOfRegisters(regsInPriorityOrder(type).size())
</span><span class="cx"> {
</span><del>- initializeDegrees(code);
</del><ins>+ initializeDegrees();
</ins><span class="cx">
</span><del>- unsigned tmpArraySize = this->tmpArraySize(code);
</del><ins>+ unsigned tmpArraySize = this->tmpArraySize();
</ins><span class="cx"> m_adjacencyList.resize(tmpArraySize);
</span><span class="cx"> m_moveList.resize(tmpArraySize);
</span><span class="cx"> m_coalescedTmps.resize(tmpArraySize);
</span><span class="cx"> m_isOnSelectStack.ensureSize(tmpArraySize);
</span><span class="cx">
</span><del>- build(code);
</del><ins>+ build();
</ins><span class="cx"> allocate();
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -138,15 +144,15 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- static unsigned tmpArraySize(Code& code)
</del><ins>+ unsigned tmpArraySize()
</ins><span class="cx"> {
</span><del>- unsigned numTmps = code.numTmps(type);
</del><ins>+ unsigned numTmps = m_code.numTmps(type);
</ins><span class="cx"> return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void initializeDegrees(Code& code)
</del><ins>+ void initializeDegrees()
</ins><span class="cx"> {
</span><del>- unsigned tmpArraySize = this->tmpArraySize(code);
</del><ins>+ unsigned tmpArraySize = this->tmpArraySize();
</ins><span class="cx"> m_degrees.resize(tmpArraySize);
</span><span class="cx">
</span><span class="cx"> // All precolored registers have an "infinite" degree.
</span><span class="lines">@@ -157,10 +163,10 @@
</span><span class="cx"> bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
</span><span class="cx"> }
</span><span class="cx">
</span><del>- void build(Code& code)
</del><ins>+ void build()
</ins><span class="cx"> {
</span><del>- TmpLiveness<type> liveness(code);
- for (BasicBlock* block : code) {
</del><ins>+ TmpLiveness<type> liveness(m_code);
+ for (BasicBlock* block : m_code) {
</ins><span class="cx"> typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
</span><span class="cx"> for (unsigned instIndex = block->size(); instIndex--;) {
</span><span class="cx"> Inst& inst = block->at(instIndex);
</span><span class="lines">@@ -547,7 +553,6 @@
</span><span class="cx"> m_coalescedTmpsAtSpill = m_coalescedTmps;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // FIXME: we should select a good candidate based on all the information we have.
</del><span class="cx"> auto iterator = m_spillWorklist.begin();
</span><span class="cx">
</span><span class="cx"> while (iterator != m_spillWorklist.end() && m_unspillableTmp.contains(*iterator))
</span><span class="lines">@@ -555,18 +560,32 @@
</span><span class="cx">
</span><span class="cx"> RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
</span><span class="cx">
</span><ins>+ // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
+ // gets a register.
+ auto score = [&] (Tmp tmp) -> double {
+ // All else being equal, the score should be directly related to the degree.
+ double degree = static_cast<double>(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
+
+ // All else being equal, the score should be inversely related to the number of warm uses and
+ // defs.
+ const UseCounts<Tmp>::Counts& counts = m_useCounts[tmp];
+ double uses = counts.numWarmUses + counts.numDefs;
+
+ return degree / uses;
+ };
+
</ins><span class="cx"> auto victimIterator = iterator;
</span><del>- unsigned maxDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
</del><ins>+ double maxScore = score(*iterator);
</ins><span class="cx">
</span><span class="cx"> ++iterator;
</span><span class="cx"> for (;iterator != m_spillWorklist.end(); ++iterator) {
</span><del>- unsigned tmpDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(*iterator)];
- if (tmpDegree > maxDegree) {
</del><ins>+ double tmpScore = score(*iterator);
+ if (tmpScore > maxScore) {
</ins><span class="cx"> if (m_unspillableTmp.contains(*iterator))
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="cx"> victimIterator = iterator;
</span><del>- maxDegree = tmpDegree;
</del><ins>+ maxScore = tmpScore;
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -778,6 +797,9 @@
</span><span class="cx"> };
</span><span class="cx"> typedef SimpleClassHashTraits<InterferenceEdge> InterferenceEdgeHashTraits;
</span><span class="cx">
</span><ins>+ Code& m_code;
+ const UseCounts<Tmp>& m_useCounts;
+
</ins><span class="cx"> const HashSet<Tmp>& m_unspillableTmp;
</span><span class="cx"> unsigned m_numberOfRegisters { 0 };
</span><span class="cx">
</span><span class="lines">@@ -901,13 +923,13 @@
</span><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static bool isUselessMoveInst(const Inst& inst)
</del><ins>+bool isUselessMoveInst(const Inst& inst)
</ins><span class="cx"> {
</span><span class="cx"> return MoveInstHelper<type>::mayBeCoalescable(inst) && inst.args[0].tmp() == inst.args[1].tmp();
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static void assignRegisterToTmpInProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator)
</del><ins>+void assignRegisterToTmpInProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator)
</ins><span class="cx"> {
</span><span class="cx"> for (BasicBlock* block : code) {
</span><span class="cx"> // Give Tmp a valid register.
</span><span class="lines">@@ -937,7 +959,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static void addSpillAndFillToProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator, HashSet<Tmp>& unspillableTmp)
</del><ins>+void addSpillAndFillToProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator, HashSet<Tmp>& unspillableTmp)
</ins><span class="cx"> {
</span><span class="cx"> const HashSet<Tmp>& spilledTmp = allocator.spilledTmp();
</span><span class="cx">
</span><span class="lines">@@ -1007,12 +1029,13 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static void iteratedRegisterCoalescingOnType(Code& code, unsigned& numIterations)
</del><ins>+void iteratedRegisterCoalescingOnType(
+ Code& code, const UseCounts<Tmp>& useCounts, unsigned& numIterations)
</ins><span class="cx"> {
</span><span class="cx"> HashSet<Tmp> unspillableTmps;
</span><span class="cx"> while (true) {
</span><span class="cx"> numIterations++;
</span><del>- IteratedRegisterCoalescingAllocator<type> allocator(code, unspillableTmps);
</del><ins>+ IteratedRegisterCoalescingAllocator<type> allocator(code, useCounts, unspillableTmps);
</ins><span class="cx"> if (allocator.spilledTmp().isEmpty()) {
</span><span class="cx"> assignRegisterToTmpInProgram(code, allocator);
</span><span class="cx"> return;
</span><span class="lines">@@ -1021,14 +1044,17 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+} // anonymous namespace
+
</ins><span class="cx"> void iteratedRegisterCoalescing(Code& code)
</span><span class="cx"> {
</span><span class="cx"> PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
</span><span class="cx">
</span><span class="cx"> unsigned numIterations = 0;
</span><span class="cx">
</span><del>- iteratedRegisterCoalescingOnType<Arg::GP>(code, numIterations);
- iteratedRegisterCoalescingOnType<Arg::FP>(code, numIterations);
</del><ins>+ UseCounts<Tmp> useCounts(code);
+ iteratedRegisterCoalescingOnType<Arg::GP>(code, useCounts, numIterations);
+ iteratedRegisterCoalescingOnType<Arg::FP>(code, useCounts, numIterations);
</ins><span class="cx">
</span><span class="cx"> if (reportStats)
</span><span class="cx"> dataLog("Num iterations = ", numIterations, "\n");
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirLivenessh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirLiveness.h (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/air/AirLiveness.h 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -29,6 +29,7 @@
</span><span class="cx"> #if ENABLE(B3_JIT)
</span><span class="cx">
</span><span class="cx"> #include "AirBasicBlock.h"
</span><ins>+#include "AirInstInlines.h"
</ins><span class="cx"> #include "AirTmpInlines.h"
</span><span class="cx"> #include "B3IndexMap.h"
</span><span class="cx"> #include "B3IndexSet.h"
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirSpillEverythingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/b3/air/AirSpillEverything.cpp 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -130,6 +130,7 @@
</span><span class="cx"> Reg chosenReg;
</span><span class="cx"> switch (role) {
</span><span class="cx"> case Arg::Use:
</span><ins>+ case Arg::ColdUse:
</ins><span class="cx"> for (Reg reg : regsInPriorityOrder(type)) {
</span><span class="cx"> if (!setBefore.get(reg)) {
</span><span class="cx"> setBefore.set(reg);
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirUseCountsh"></a>
<div class="addfile"><h4>Added: trunk/Source/JavaScriptCore/b3/air/AirUseCounts.h (0 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirUseCounts.h (rev 0)
+++ trunk/Source/JavaScriptCore/b3/air/AirUseCounts.h 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -0,0 +1,110 @@
</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 AirUseCounts_h
+#define AirUseCounts_h
+
+#if ENABLE(B3_JIT)
+
+#include "AirArg.h"
+#include "AirBlockWorklist.h"
+#include "AirCode.h"
+#include "AirInstInlines.h"
+#include <wtf/HashMap.h>
+#include <wtf/ListDump.h>
+
+namespace JSC { namespace B3 { namespace Air {
+
+class Code;
+
+// Computes the number of uses of a variable based on frequency of execution. The frequency of blocks
+// that are only reachable by rare edges is scaled by Options::rareBlockPenalty().
+
+// Thing can be either Tmp or Arg.
+template<typename Thing>
+class UseCounts {
+public:
+ struct Counts {
+ void dump(PrintStream& out) const
+ {
+ out.print(
+ "{numWarmUses = ", numWarmUses, ", numColdUses = ", numColdUses, ", numDefs = ",
+ numDefs, "}");
+ }
+
+ double numWarmUses { 0 };
+ double numColdUses { 0 };
+ double numDefs { 0 };
+ };
+
+ UseCounts(Code& code)
+ {
+ // Find non-rare blocks.
+ BlockWorklist fastWorklist;
+ fastWorklist.push(code[0]);
+ while (BasicBlock* block = fastWorklist.pop()) {
+ for (FrequentedBlock& successor : block->successors()) {
+ if (!successor.isRare())
+ fastWorklist.push(successor.block());
+ }
+ }
+
+ for (BasicBlock* block : code) {
+ double frequency = block->frequency();
+ if (!fastWorklist.saw(block))
+ frequency *= Options::rareBlockPenalty();
+ for (Inst& inst : *block) {
+ inst.forEach<Thing>(
+ [&] (Thing& arg, Arg::Role role, Arg::Type) {
+ Counts& counts = m_counts.add(arg, Counts()).iterator->value;
+
+ if (Arg::isWarmUse(role))
+ counts.numWarmUses += frequency;
+ if (Arg::isColdUse(role))
+ counts.numColdUses += frequency;
+ if (Arg::isDef(role))
+ counts.numDefs += frequency;
+ });
+ }
+ }
+ }
+
+ const Counts& operator[](const Thing& arg) const { return m_counts.find(arg)->value; }
+
+ void dump(PrintStream& out) const
+ {
+ out.print(mapDump(m_counts));
+ }
+
+private:
+ HashMap<Thing, Counts> m_counts;
+};
+
+} } } // namespace JSC::B3::Air
+
+#endif // ENABLE(B3_JIT)
+
+#endif // AirUseCounts_h
+
</ins></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeOptionsh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/Options.h (192862 => 192863)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/Options.h 2015-12-01 06:58:44 UTC (rev 192862)
+++ trunk/Source/JavaScriptCore/runtime/Options.h 2015-12-01 07:03:55 UTC (rev 192863)
</span><span class="lines">@@ -338,6 +338,7 @@
</span><span class="cx"> v(unsigned, fireOSRExitFuzzAtOrAfter, 0, nullptr) \
</span><span class="cx"> \
</span><span class="cx"> v(bool, logB3PhaseTimes, false, nullptr) \
</span><ins>+ v(double, rareBlockPenalty, 0.001, nullptr) \
</ins><span class="cx"> \
</span><span class="cx"> v(bool, useDollarVM, false, "installs the $vm debugging tool in global objects") \
</span><span class="cx"> v(optionString, functionOverrides, nullptr, "file with debugging overrides for function bodies") \
</span></span></pre>
</div>
</div>
</body>
</html>