<!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>[192658] 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/192658">192658</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-11-19 14:05:36 -0800 (Thu, 19 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] When the iterated allocator is forced to spill, nuke the Moves that were already proven to be useless
https://bugs.webkit.org/show_bug.cgi?id=151461
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-11-19
Reviewed by Filip Pizlo.
Previously, when we had to spill, we were just inserting new Spill() and Fill()
in code while everything else remained identical.
Coalescing moves is a big part of the algorithm and takes a non-trivial time.
Since we were never removing Moves until reaching a successful coloring, we were
paying that cost with every single iteration.
With this patch, I keep a copy of the coalescing aliases when we make the first
potential spill decision. Before doing that, we have only simplified and coalesced
vertices that are provably colorable regardless of the other vertices' colors
(because their degree is <K, potentially after other edges were removed by simplification).
If we end up actually spilling, I use the old aliases to simplify the blocks if possible.
This is a 5% progression on "testComplex(64, 384)".
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAliasWhenSpilling):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
(JSC::B3::Air::addSpillAndFillToProgram):
(JSC::B3::Air::iteratedRegisterCoalescingOnType):
(JSC::B3::Air::iteratedRegisterCoalescing):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp">trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (192657 => 192658)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-19 21:39:50 UTC (rev 192657)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-19 22:05:36 UTC (rev 192658)
</span><span class="lines">@@ -1,3 +1,35 @@
</span><ins>+2015-11-19 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] When the iterated allocator is forced to spill, nuke the Moves that were already proven to be useless
+ https://bugs.webkit.org/show_bug.cgi?id=151461
+
+ Reviewed by Filip Pizlo.
+
+ Previously, when we had to spill, we were just inserting new Spill() and Fill()
+ in code while everything else remained identical.
+
+ Coalescing moves is a big part of the algorithm and takes a non-trivial time.
+ Since we were never removing Moves until reaching a successful coloring, we were
+ paying that cost with every single iteration.
+
+ With this patch, I keep a copy of the coalescing aliases when we make the first
+ potential spill decision. Before doing that, we have only simplified and coalesced
+ vertices that are provably colorable regardless of the other vertices' colors
+ (because their degree is <K, potentially after other edges were removed by simplification).
+
+ If we end up actually spilling, I use the old aliases to simplify the blocks if possible.
+
+ This is a 5% progression on "testComplex(64, 384)".
+
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::getAliasWhenSpilling):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::selectSpill):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors):
+ (JSC::B3::Air::addSpillAndFillToProgram):
+ (JSC::B3::Air::iteratedRegisterCoalescingOnType):
+ (JSC::B3::Air::iteratedRegisterCoalescing):
+
</ins><span class="cx"> 2015-11-19 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><span class="cx"> Fix FTL->B3 lowering of Phi
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (192657 => 192658)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-19 21:39:50 UTC (rev 192657)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-19 22:05:36 UTC (rev 192658)
</span><span class="lines">@@ -244,6 +244,22 @@
</span><span class="cx"> return alias;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ Tmp getAliasWhenSpilling(Tmp tmp) const
+ {
+ ASSERT_WITH_MESSAGE(!m_spilledTmp.isEmpty(), "This function is only valid for coalescing during spilling.");
+
+ if (m_coalescedTmpsAtSpill.isEmpty())
+ return tmp;
+
+ Tmp alias = tmp;
+ while (Tmp nextAlias = m_coalescedTmpsAtSpill[AbsoluteTmpHelper<type>::absoluteIndex(alias)])
+ alias = nextAlias;
+
+ ASSERT_WITH_MESSAGE(!m_spilledTmp.contains(tmp) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
+
+ return alias;
+ }
+
</ins><span class="cx"> const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
</span><span class="cx"> Reg allocatedReg(Tmp tmp) const
</span><span class="cx"> {
</span><span class="lines">@@ -437,6 +453,7 @@
</span><span class="cx"> } else if (canBeSafelyCoalesced(u, v)) {
</span><span class="cx"> combine(u, v);
</span><span class="cx"> addWorkList(u);
</span><ins>+ m_hasCoalescedNonTrivialMove = true;
</ins><span class="cx">
</span><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Safe Coalescing\n");
</span><span class="lines">@@ -573,6 +590,13 @@
</span><span class="cx">
</span><span class="cx"> void selectSpill()
</span><span class="cx"> {
</span><ins>+ if (!m_hasSelectedSpill) {
+ m_hasSelectedSpill = true;
+
+ if (m_hasCoalescedNonTrivialMove)
+ m_coalescedTmpsAtSpill = m_coalescedTmps;
+ }
+
</ins><span class="cx"> // FIXME: we should select a good candidate based on all the information we have.
</span><span class="cx"> auto iterator = m_spillWorklist.begin();
</span><span class="cx">
</span><span class="lines">@@ -654,7 +678,9 @@
</span><span class="cx"> }
</span><span class="cx"> m_selectStack.clear();
</span><span class="cx">
</span><del>- if (!m_spilledTmp.isEmpty())
</del><ins>+ if (m_spilledTmp.isEmpty())
+ m_coalescedTmpsAtSpill.clear();
+ else
</ins><span class="cx"> m_coloredTmp.clear();
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -785,7 +811,7 @@
</span><span class="cx"> HashSet<Tmp> m_spilledTmp;
</span><span class="cx">
</span><span class="cx"> // Values that have been coalesced with an other value.
</span><del>- Vector<Tmp> m_coalescedTmps;
</del><ins>+ Vector<Tmp, 0, UnsafeVectorOverflow> m_coalescedTmps;
</ins><span class="cx">
</span><span class="cx"> // The stack of Tmp removed from the graph and ready for coloring.
</span><span class="cx"> BitVector m_isOnSelectStack;
</span><span class="lines">@@ -875,6 +901,12 @@
</span><span class="cx"> HashSet<Tmp> m_spillWorklist;
</span><span class="cx"> // Low-degree, Move related.
</span><span class="cx"> HashSet<Tmp> m_freezeWorklist;
</span><ins>+
+ bool m_hasSelectedSpill { false };
+ bool m_hasCoalescedNonTrivialMove { false };
+
+ // The mapping of Tmp to their alias for Moves that are always coalescing regardless of spilling.
+ Vector<Tmp, 0, UnsafeVectorOverflow> m_coalescedTmpsAtSpill;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><span class="lines">@@ -914,8 +946,10 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> template<Arg::Type type>
</span><del>-static void addSpillAndFillToProgram(Code& code, const HashSet<Tmp>& spilledTmp, HashSet<Tmp>& unspillableTmp)
</del><ins>+static void addSpillAndFillToProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator, HashSet<Tmp>& unspillableTmp)
</ins><span class="cx"> {
</span><ins>+ const HashSet<Tmp>& spilledTmp = allocator.spilledTmp();
+
</ins><span class="cx"> // All the spilled values become unspillable.
</span><span class="cx"> unspillableTmp.add(spilledTmp.begin(), spilledTmp.end());
</span><span class="cx">
</span><span class="lines">@@ -929,6 +963,8 @@
</span><span class="cx"> // Rewrite the program to get rid of the spilled Tmp.
</span><span class="cx"> InsertionSet insertionSet(code);
</span><span class="cx"> for (BasicBlock* block : code) {
</span><ins>+ bool hasAliasedTmps = false;
+
</ins><span class="cx"> for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
</span><span class="cx"> Inst& inst = block->at(instIndex);
</span><span class="cx">
</span><span class="lines">@@ -937,13 +973,8 @@
</span><span class="cx"> Arg& arg = inst.args[i];
</span><span class="cx"> if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
</span><span class="cx"> auto stackSlotEntry = stackSlots.find(arg.tmp());
</span><del>- if (stackSlotEntry == stackSlots.end())
- continue;
-
- if (inst.admitsStack(i)) {
</del><ins>+ if (stackSlotEntry != stackSlots.end() && inst.admitsStack(i))
</ins><span class="cx"> arg = Arg::stack(stackSlotEntry->value);
</span><del>- continue;
- }
</del><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -953,8 +984,14 @@
</span><span class="cx"> return;
</span><span class="cx">
</span><span class="cx"> auto stackSlotEntry = stackSlots.find(tmp);
</span><del>- if (stackSlotEntry == stackSlots.end())
</del><ins>+ if (stackSlotEntry == stackSlots.end()) {
+ Tmp alias = allocator.getAliasWhenSpilling(tmp);
+ if (alias != tmp) {
+ tmp = alias;
+ hasAliasedTmps = true;
+ }
</ins><span class="cx"> return;
</span><ins>+ }
</ins><span class="cx">
</span><span class="cx"> Arg arg = Arg::stack(stackSlotEntry->value);
</span><span class="cx"> Opcode move = type == Arg::GP ? Move : MoveDouble;
</span><span class="lines">@@ -972,6 +1009,9 @@
</span><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx"> insertionSet.execute(block);
</span><ins>+
+ if (hasAliasedTmps)
+ block->insts().removeAllMatching(isUselessMoveInst<type>);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -996,7 +1036,7 @@
</span><span class="cx"> assignRegisterToTmpInProgram(code, allocator);
</span><span class="cx"> return;
</span><span class="cx"> }
</span><del>- addSpillAndFillToProgram<type>(code, allocator.spilledTmp(), unspillableTmps);
</del><ins>+ addSpillAndFillToProgram<type>(code, allocator, unspillableTmps);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -1039,13 +1079,13 @@
</span><span class="cx"> assignRegisterToTmpInProgram(code, gpAllocator);
</span><span class="cx"> gpIsColored = true;
</span><span class="cx"> } else
</span><del>- addSpillAndFillToProgram<Arg::GP>(code, gpAllocator.spilledTmp(), unspillableGPs);
</del><ins>+ addSpillAndFillToProgram<Arg::GP>(code, gpAllocator, unspillableGPs);
</ins><span class="cx">
</span><span class="cx"> if (fpAllocator.spilledTmp().isEmpty()) {
</span><span class="cx"> assignRegisterToTmpInProgram(code, fpAllocator);
</span><span class="cx"> fpIsColored = true;
</span><span class="cx"> } else
</span><del>- addSpillAndFillToProgram<Arg::FP>(code, fpAllocator.spilledTmp(), unspillableFPs);
</del><ins>+ addSpillAndFillToProgram<Arg::FP>(code, fpAllocator, unspillableFPs);
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> if (!gpIsColored)
</span></span></pre>
</div>
</div>
</body>
</html>