<!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>[212851] 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/212851">212851</a></dd>
<dt>Author</dt> <dd>sbarati@apple.com</dd>
<dt>Date</dt> <dd>2017-02-22 13:52:13 -0800 (Wed, 22 Feb 2017)</dd>
</dl>
<h3>Log Message</h3>
<pre>Add biased coloring to Briggs and IRC
https://bugs.webkit.org/show_bug.cgi?id=168611
Reviewed by Filip Pizlo.
This patch implements biased coloring as proposed by Briggs. See section
5.3.3 of his thesis for more information: http://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf
The main idea of biased coloring is this:
We try to coalesce a move between u and v, but the conservative heuristic
fails. We don't want coalesce the move because we don't want to risk
creating an uncolorable graph. However, if the conservative heuristic fails,
it's not proof that the graph is uncolorable if the move were indeed coalesced.
So, when we go to color the tmps, we'll remember that we really want the
same register for u and v, and if legal during coloring, we will
assign them to the same register.
* b3/air/AirAllocateRegistersByGraphColoring.cpp:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreb3airAirAllocateRegistersByGraphColoringcpp">trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (212850 => 212851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2017-02-22 21:49:54 UTC (rev 212850)
+++ trunk/Source/JavaScriptCore/ChangeLog 2017-02-22 21:52:13 UTC (rev 212851)
</span><span class="lines">@@ -1,3 +1,24 @@
</span><ins>+2017-02-22 Saam Barati <sbarati@apple.com>
+
+ Add biased coloring to Briggs and IRC
+ https://bugs.webkit.org/show_bug.cgi?id=168611
+
+ Reviewed by Filip Pizlo.
+
+ This patch implements biased coloring as proposed by Briggs. See section
+ 5.3.3 of his thesis for more information: http://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf
+
+ The main idea of biased coloring is this:
+ We try to coalesce a move between u and v, but the conservative heuristic
+ fails. We don't want coalesce the move because we don't want to risk
+ creating an uncolorable graph. However, if the conservative heuristic fails,
+ it's not proof that the graph is uncolorable if the move were indeed coalesced.
+ So, when we go to color the tmps, we'll remember that we really want the
+ same register for u and v, and if legal during coloring, we will
+ assign them to the same register.
+
+ * b3/air/AirAllocateRegistersByGraphColoring.cpp:
+
</ins><span class="cx"> 2017-02-22 Yusuke Suzuki <utatane.tea@gmail.com>
</span><span class="cx">
</span><span class="cx"> JSModuleNamespace object should have IC
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirAllocateRegistersByGraphColoringcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp (212850 => 212851)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp 2017-02-22 21:49:54 UTC (rev 212850)
+++ trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp 2017-02-22 21:52:13 UTC (rev 212851)
</span><span class="lines">@@ -250,6 +250,23 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ void addBias(IndexType u, IndexType v)
+ {
+ // We implement biased coloring as proposed by Briggs. See section
+ // 5.3.3 of his thesis for more information: http://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf
+ // The main idea of biased coloring is this:
+ // We try to coalesce a move between u and v, but the conservative heuristic
+ // fails. We don't want coalesce the move because we don't want to risk
+ // creating an uncolorable graph. However, if the conservative heuristic fails,
+ // it's not proof that the graph is uncolorable if the move were indeed coalesced.
+ // So, when we go to color the tmps, we'll remember that we really want the
+ // same register for u and v, and if legal, we will assign them to the same register.
+ if (!isPrecolored(u))
+ m_biases.add(u, IndexTypeSet()).iterator->value.add(v);
+ if (!isPrecolored(v))
+ m_biases.add(v, IndexTypeSet()).iterator->value.add(u);
+ }
+
</ins><span class="cx"> IndexType selectSpill()
</span><span class="cx"> {
</span><span class="cx"> if (!m_hasSelectedSpill) {
</span><span class="lines">@@ -327,12 +344,31 @@
</span><span class="cx"> // Try to color the Tmp on the stack.
</span><span class="cx"> m_coloredTmp.resize(m_adjacencyList.size());
</span><span class="cx">
</span><ins>+ {
+ Vector<IndexType, 4> nowAliasedBiases;
+ for (IndexType key : m_biases.keys()) {
+ if (key != getAlias(key))
+ nowAliasedBiases.append(key);
+ }
+ for (IndexType key : nowAliasedBiases) {
+ IndexTypeSet keysBiases(m_biases.take(key));
+ auto addResult = m_biases.add(getAlias(key), IndexTypeSet());
+ if (addResult.isNewEntry) {
+ ASSERT(!addResult.iterator->value.size());
+ addResult.iterator->value = WTFMove(keysBiases);
+ } else {
+ IndexTypeSet& setToAddTo = addResult.iterator->value;
+ for (IndexType tmp : keysBiases)
+ setToAddTo.add(tmp);
+ }
+ }
+ }
+
</ins><span class="cx"> while (!m_selectStack.isEmpty()) {
</span><span class="cx"> unsigned tmpIndex = m_selectStack.takeLast();
</span><del>- m_isOnSelectStack.quickClear(tmpIndex);
</del><span class="cx"> ASSERT(!isPrecolored(tmpIndex));
</span><span class="cx"> ASSERT(!m_coloredTmp[tmpIndex]);
</span><del>- RELEASE_ASSERT(getAlias(tmpIndex) == tmpIndex);
</del><ins>+ ASSERT(getAlias(tmpIndex) == tmpIndex);
</ins><span class="cx">
</span><span class="cx"> RegisterSet coloredRegisters;
</span><span class="cx"> for (IndexType adjacentTmpIndex : m_adjacencyList[tmpIndex]) {
</span><span class="lines">@@ -346,13 +382,27 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool colorAssigned = false;
</span><del>- for (Reg reg : m_regsInPriorityOrder) {
- if (!coloredRegisters.get(reg)) {
- m_coloredTmp[tmpIndex] = reg;
- colorAssigned = true;
- break;
</del><ins>+ auto iter = m_biases.find(tmpIndex);
+ if (iter != m_biases.end()) {
+ for (IndexType desiredBias : iter->value) {
+ if (Reg desiredColor = m_coloredTmp[getAlias(desiredBias)]) {
+ if (!coloredRegisters.get(desiredColor)) {
+ m_coloredTmp[tmpIndex] = desiredColor;
+ colorAssigned = true;
+ break;
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx"> }
</span><ins>+ if (!colorAssigned) {
+ for (Reg reg : m_regsInPriorityOrder) {
+ if (!coloredRegisters.get(reg)) {
+ m_coloredTmp[tmpIndex] = reg;
+ colorAssigned = true;
+ break;
+ }
+ }
+ }
</ins><span class="cx">
</span><span class="cx"> if (!colorAssigned)
</span><span class="cx"> m_spilledTmps.append(tmpIndex);
</span><span class="lines">@@ -474,6 +524,10 @@
</span><span class="cx"> Vector<Vector<IndexType, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
</span><span class="cx"> Vector<IndexType, 0, UnsafeVectorOverflow> m_degrees;
</span><span class="cx">
</span><ins>+ using IndexTypeSet = HashSet<IndexType, typename DefaultHash<IndexType>::Hash, WTF::UnsignedWithZeroKeyHashTraits<IndexType>>;
+
+ HashMap<IndexType, IndexTypeSet, typename DefaultHash<IndexType>::Hash, WTF::UnsignedWithZeroKeyHashTraits<IndexType>> m_biases;
+
</ins><span class="cx"> // Instead of keeping track of the move instructions, we just keep their operands around and use the index
</span><span class="cx"> // in the vector as the "identifier" for the move.
</span><span class="cx"> struct MoveOperands {
</span><span class="lines">@@ -483,7 +537,7 @@
</span><span class="cx"> Vector<MoveOperands, 0, UnsafeVectorOverflow> m_coalescingCandidates;
</span><span class="cx">
</span><span class="cx"> // List of every move instruction associated with a Tmp.
</span><del>- Vector<HashSet<IndexType, typename DefaultHash<IndexType>::Hash, WTF::UnsignedWithZeroKeyHashTraits<IndexType>>> m_moveList;
</del><ins>+ Vector<IndexTypeSet> m_moveList;
</ins><span class="cx">
</span><span class="cx"> // Colors.
</span><span class="cx"> Vector<Reg, 0, UnsafeVectorOverflow> m_coloredTmp;
</span><span class="lines">@@ -550,6 +604,7 @@
</span><span class="cx"> using Base::hasBeenSimplified;
</span><span class="cx"> using Base::addToSpill;
</span><span class="cx"> using Base::m_interferenceEdges;
</span><ins>+ using Base::addBias;
</ins><span class="cx">
</span><span class="cx"> public:
</span><span class="cx"> Briggs(Code& code, const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize, const HashSet<unsigned>& unspillableTmps, const UseCounts<Tmp>& useCounts)
</span><span class="lines">@@ -686,6 +741,8 @@
</span><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ addBias(u, v);
+
</ins><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Failed coalescing.\n");
</span><span class="cx">
</span><span class="lines">@@ -907,6 +964,7 @@
</span><span class="cx"> using Base::m_interferenceEdges;
</span><span class="cx"> using Base::m_adjacencyList;
</span><span class="cx"> using Base::dumpInterferenceGraphInDot;
</span><ins>+ using Base::addBias;
</ins><span class="cx">
</span><span class="cx"> public:
</span><span class="cx"> IRC(Code& code, const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize, const HashSet<unsigned>& unspillableTmps, const UseCounts<Tmp>& useCounts)
</span><span class="lines">@@ -1026,6 +1084,8 @@
</span><span class="cx"> m_activeMoves.quickSet(moveIndex);
</span><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Failed coalescing, added to active moves.\n");
</span><ins>+
+ addBias(u, v);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre>
</div>
</div>
</body>
</html>