<!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>[194316] 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/194316">194316</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-12-19 13:04:55 -0800 (Sat, 19 Dec 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] Streamline Tmp indexing inside the register allocator
https://bugs.webkit.org/show_bug.cgi?id=152420
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-12-19
Reviewed by Filip Pizlo.
AirIteratedRegisterCoalescing has been accumulating a bit of mess over time.
When it started, every map addressed by Tmp was using Tmp hashing.
That caused massive performance problems. Everything perf sensitive was moved
to direct array addressing by the absolute Tmp index. This left the code
with half of the function using Tmp, the other half using indices.
With this patch, almost everything is moved to absolute indexing.
There are a few advantages to this:
-No more conversion churn for Floating Point registers.
-Most of the functions can now be shared between GP and FP.
-A bit of clean up since the core algorithm only deals with integers now.
This patch also changes the index type to be a template argument.
That will allow future specialization of "m_interferenceEdges" based
on the expected problem size.
Finally, the code related to the program modification (register assignment
and spilling) was moved to the wrapper "IteratedRegisterCoalescing".
The current split is:
-AbstractColoringAllocator: common core. Share as much as possible between
GP and FP.
-ColoringAllocator: the remaining parts of the algorithm, everything that
is specific to GP, FP.
-IteratedRegisterCoalescing: the "iterated" part of the algorithm.
Try to allocate and modify the code as needed.
The long term plan is:
-Move selectSpill() and the coloring loop to AbstractColoringAllocator.
-Specialize m_interferenceEdges to make it faster.
* b3/air/AirIteratedRegisterCoalescing.cpp:
* b3/air/AirTmpInlines.h:
(JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::lastMachineRegisterIndex):
(JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::lastMachineRegisterIndex):</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>
<li><a href="#trunkSourceJavaScriptCoreb3airAirTmpInlinesh">trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (194315 => 194316)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-12-19 19:01:50 UTC (rev 194315)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-12-19 21:04:55 UTC (rev 194316)
</span><span class="lines">@@ -1,5 +1,49 @@
</span><span class="cx"> 2015-12-19 Benjamin Poulain <bpoulain@apple.com>
</span><span class="cx">
</span><ins>+ [JSC] Streamline Tmp indexing inside the register allocator
+ https://bugs.webkit.org/show_bug.cgi?id=152420
+
+ Reviewed by Filip Pizlo.
+
+ AirIteratedRegisterCoalescing has been accumulating a bit of mess over time.
+
+ When it started, every map addressed by Tmp was using Tmp hashing.
+ That caused massive performance problems. Everything perf sensitive was moved
+ to direct array addressing by the absolute Tmp index. This left the code
+ with half of the function using Tmp, the other half using indices.
+
+ With this patch, almost everything is moved to absolute indexing.
+ There are a few advantages to this:
+ -No more conversion churn for Floating Point registers.
+ -Most of the functions can now be shared between GP and FP.
+ -A bit of clean up since the core algorithm only deals with integers now.
+
+ This patch also changes the index type to be a template argument.
+ That will allow future specialization of "m_interferenceEdges" based
+ on the expected problem size.
+
+ Finally, the code related to the program modification (register assignment
+ and spilling) was moved to the wrapper "IteratedRegisterCoalescing".
+
+ The current split is:
+ -AbstractColoringAllocator: common core. Share as much as possible between
+ GP and FP.
+ -ColoringAllocator: the remaining parts of the algorithm, everything that
+ is specific to GP, FP.
+ -IteratedRegisterCoalescing: the "iterated" part of the algorithm.
+ Try to allocate and modify the code as needed.
+
+ The long term plan is:
+ -Move selectSpill() and the coloring loop to AbstractColoringAllocator.
+ -Specialize m_interferenceEdges to make it faster.
+
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ * b3/air/AirTmpInlines.h:
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::GP>::lastMachineRegisterIndex):
+ (JSC::B3::Air::AbsoluteTmpMapper<Arg::FP>::lastMachineRegisterIndex):
+
+2015-12-19 Benjamin Poulain <bpoulain@apple.com>
+
</ins><span class="cx"> [JSC] FTLB3Output generates some invalid ZExt32
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=151905
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (194315 => 194316)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-19 19:01:50 UTC (rev 194315)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-12-19 21:04:55 UTC (rev 194316)
</span><span class="lines">@@ -47,336 +47,97 @@
</span><span class="cx"> bool traceDebug = false;
</span><span class="cx"> bool reportStats = false;
</span><span class="cx">
</span><del>-template<Arg::Type type>
-struct MoveInstHelper;
-
-template<>
-struct MoveInstHelper<Arg::GP> {
- static bool mayBeCoalescable(const Inst& inst)
- {
- bool isMove = inst.opcode == Move;
- if (!isMove)
- return false;
-
- ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
- ASSERT(inst.args[0].isType(Arg::GP));
- ASSERT(inst.args[1].isType(Arg::GP));
-
- return inst.args[0].isTmp() && inst.args[1].isTmp();
- }
-};
-
-template<>
-struct MoveInstHelper<Arg::FP> {
- static bool mayBeCoalescable(const Inst& inst)
- {
- if (inst.opcode != MoveDouble)
- return false;
-
- ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
- ASSERT(inst.args[0].isType(Arg::FP));
- ASSERT(inst.args[1].isType(Arg::FP));
-
- return inst.args[0].isTmp() && inst.args[1].isTmp();
- }
-};
-
-template<Arg::Type type>
-class IteratedRegisterCoalescingAllocator {
</del><ins>+// The AbstractColoringAllocator defines all the code that is independant
+// from the type or register and can be shared when allocating registers.
+template<typename IndexType>
+class AbstractColoringAllocator {
</ins><span class="cx"> public:
</span><del>- IteratedRegisterCoalescingAllocator(
- Code& code, const UseCounts<Tmp>& useCounts, const HashSet<Tmp>& unspillableTmp)
- : m_code(code)
- , m_useCounts(useCounts)
- , m_unspillableTmp(unspillableTmp)
- , m_numberOfRegisters(regsInPriorityOrder(type).size())
</del><ins>+ AbstractColoringAllocator(const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize)
+ : m_regsInPriorityOrder(regsInPriorityOrder)
+ , m_lastPrecoloredRegisterIndex(lastPrecoloredRegisterIndex)
</ins><span class="cx"> {
</span><del>- initializeDegrees();
</del><ins>+ initializeDegrees(tmpArraySize);
</ins><span class="cx">
</span><del>- unsigned tmpArraySize = this->tmpArraySize();
</del><span class="cx"> m_adjacencyList.resize(tmpArraySize);
</span><span class="cx"> m_moveList.resize(tmpArraySize);
</span><del>- m_coalescedTmps.resize(tmpArraySize);
</del><ins>+ m_coalescedTmps.fill(0, tmpArraySize);
</ins><span class="cx"> m_isOnSelectStack.ensureSize(tmpArraySize);
</span><del>-
- build();
- allocate();
</del><span class="cx"> }
</span><span class="cx">
</span><del>- Tmp getAlias(Tmp tmp) const
</del><ins>+protected:
+ IndexType getAlias(IndexType tmpIndex) const
</ins><span class="cx"> {
</span><del>- Tmp alias = tmp;
- while (Tmp nextAlias = m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(alias)])
</del><ins>+ IndexType alias = tmpIndex;
+ while (IndexType nextAlias = m_coalescedTmps[alias])
</ins><span class="cx"> alias = nextAlias;
</span><span class="cx"> return alias;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Tmp getAliasWhenSpilling(Tmp tmp) const
</del><ins>+ void addEdge(IndexType a, IndexType b)
</ins><span class="cx"> {
</span><del>- 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[AbsoluteTmpMapper<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;
- }
-
- const HashSet<Tmp>& spilledTmp() const { return m_spilledTmp; }
- Reg allocatedReg(Tmp tmp) const
- {
- ASSERT(!tmp.isReg());
- ASSERT(m_coloredTmp.size());
- ASSERT(tmp.isGP() == (type == Arg::GP));
-
- Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
- if (!reg) {
- // We only care about Tmps that interfere. A Tmp that never interfere with anything
- // can take any register.
- reg = regsInPriorityOrder(type).first();
- }
- return reg;
- }
-
-private:
- unsigned tmpArraySize()
- {
- unsigned numTmps = m_code.numTmps(type);
- return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
- }
-
- void initializeDegrees()
- {
- unsigned tmpArraySize = this->tmpArraySize();
- m_degrees.resize(tmpArraySize);
-
- // All precolored registers have an "infinite" degree.
- unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
- for (unsigned i = 0; i < firstNonRegIndex; ++i)
- m_degrees[i] = std::numeric_limits<unsigned>::max();
-
- bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
- }
-
- void build()
- {
- TmpLiveness<type> liveness(m_code);
- for (BasicBlock* block : m_code) {
- typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
- for (unsigned instIndex = block->size(); instIndex--;) {
- Inst& inst = block->at(instIndex);
- Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
- build(inst, nextInst, localCalc);
- localCalc.execute(instIndex);
- }
- }
- }
-
- void build(Inst& inst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
- {
- inst.forEachTmpWithExtraClobberedRegs(
- nextInst,
- [&] (const Tmp& arg, Arg::Role role, Arg::Type argType) {
- if (!Arg::isDef(role) || argType != type)
- return;
-
- // All the Def()s interfere with each other and with all the extra clobbered Tmps.
- // We should not use forEachDefAndExtraClobberedTmp() here since colored Tmps
- // do not need interference edges in our implementation.
- inst.forEachTmp([&] (Tmp& otherArg, Arg::Role role, Arg::Type argType) {
- if (!Arg::isDef(role) || argType != type)
- return;
-
- addEdge(arg, otherArg);
- });
- });
-
- if (MoveInstHelper<type>::mayBeCoalescable(inst)) {
- // We do not want the Use() of this move to interfere with the Def(), even if it is live
- // after the Move. If we were to add the interference edge, it would be impossible to
- // coalesce the Move even if the two Tmp never interfere anywhere.
- Tmp defTmp;
- Tmp useTmp;
- inst.forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type) {
- if (Arg::isDef(role))
- defTmp = argTmp;
- else {
- ASSERT(Arg::isEarlyUse(role));
- useTmp = argTmp;
- }
- });
- ASSERT(defTmp);
- ASSERT(useTmp);
-
- unsigned nextMoveIndex = m_coalescingCandidates.size();
- m_coalescingCandidates.append({ useTmp, defTmp });
-
- unsigned newIndexInWorklist = m_worklistMoves.addMove();
- ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
-
- ASSERT(nextMoveIndex <= m_activeMoves.size());
- m_activeMoves.ensureSize(nextMoveIndex + 1);
-
- for (const Arg& arg : inst.args) {
- auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
- list.add(nextMoveIndex);
- }
-
- for (const Tmp& liveTmp : localCalc.live()) {
- if (liveTmp != useTmp)
- addEdge(defTmp, liveTmp);
- }
-
- // The next instruction could have early clobbers. We need to consider those now.
- if (nextInst && nextInst->hasSpecial()) {
- nextInst->extraEarlyClobberedRegs().forEach(
- [&] (Reg reg) {
- if (reg.isGPR() == (type == Arg::GP)) {
- for (const Tmp& liveTmp : localCalc.live()) {
- addEdge(Tmp(reg), liveTmp);
- }
- }
- });
- }
- } else
- addEdges(inst, nextInst, localCalc.live());
- }
-
- void addEdges(Inst& inst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmps)
- {
- // All the Def()s interfere with everthing live.
- inst.forEachTmpWithExtraClobberedRegs(
- nextInst,
- [&] (const Tmp& arg, Arg::Role role, Arg::Type argType) {
- if (!Arg::isDef(role) || argType != type)
- return;
-
- for (const Tmp& liveTmp : liveTmps) {
- if (liveTmp.isGP() == (type == Arg::GP))
- addEdge(arg, liveTmp);
- }
- });
- }
-
- void addEdge(const Tmp& a, const Tmp& b)
- {
</del><span class="cx"> if (a == b)
</span><span class="cx"> return;
</span><del>-
- if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
- if (!a.isReg()) {
- ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].contains(b));
- m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(a)].append(b);
- m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(a)]++;
- }
-
- if (!b.isReg()) {
- ASSERT(!m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].contains(a));
- m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(b)].append(a);
- m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(b)]++;
- }
- }
</del><ins>+ addEdgeDistinct(a, b);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void makeWorkList()
</span><span class="cx"> {
</span><del>- unsigned firstNonRegIndex = AbsoluteTmpMapper<type>::absoluteIndex(0);
- for (unsigned i = firstNonRegIndex; i < m_degrees.size(); ++i) {
</del><ins>+ IndexType firstNonRegIndex = m_lastPrecoloredRegisterIndex + 1;
+ for (IndexType i = firstNonRegIndex; i < m_degrees.size(); ++i) {
</ins><span class="cx"> unsigned degree = m_degrees[i];
</span><span class="cx"> if (!degree)
</span><span class="cx"> continue;
</span><span class="cx">
</span><del>- Tmp tmp = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(i);
-
- if (degree >= m_numberOfRegisters)
- m_spillWorklist.add(tmp);
- else if (!m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)].isEmpty())
- m_freezeWorklist.add(tmp);
</del><ins>+ if (degree >= m_regsInPriorityOrder.size())
+ m_spillWorklist.add(i);
+ else if (!m_moveList[i].isEmpty())
+ m_freezeWorklist.add(i);
</ins><span class="cx"> else
</span><del>- m_simplifyWorklist.append(tmp);
</del><ins>+ m_simplifyWorklist.append(i);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Low-degree vertex can always be colored: just pick any of the color taken by any
+ // other adjacent verices.
+ // The "Simplify" phase takes a low-degree out of the interference graph to simplify it.
</ins><span class="cx"> void simplify()
</span><span class="cx"> {
</span><del>- Tmp last = m_simplifyWorklist.takeLast();
</del><ins>+ IndexType lastIndex = m_simplifyWorklist.takeLast();
</ins><span class="cx">
</span><del>- ASSERT(!m_selectStack.contains(last));
- ASSERT(!m_isOnSelectStack.get(AbsoluteTmpMapper<type>::absoluteIndex(last)));
- m_selectStack.append(last);
- m_isOnSelectStack.quickSet(AbsoluteTmpMapper<type>::absoluteIndex(last));
</del><ins>+ ASSERT(!m_selectStack.contains(lastIndex));
+ ASSERT(!m_isOnSelectStack.get(lastIndex));
+ m_selectStack.append(lastIndex);
+ m_isOnSelectStack.quickSet(lastIndex);
</ins><span class="cx">
</span><del>- forEachAdjacent(last, [this](Tmp adjacentTmp) {
- decrementDegree(adjacentTmp);
</del><ins>+ forEachAdjacent(lastIndex, [this](IndexType adjacentTmpIndex) {
+ decrementDegree(adjacentTmpIndex);
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><del>- template<typename Function>
- void forEachAdjacent(Tmp tmp, Function function)
</del><ins>+ void freeze()
</ins><span class="cx"> {
</span><del>- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
- if (!hasBeenSimplified(adjacentTmp))
- function(adjacentTmp);
- }
</del><ins>+ IndexType victimIndex = m_freezeWorklist.takeAny();
+ ASSERT_WITH_MESSAGE(getAlias(victimIndex) == victimIndex, "coalesce() should not leave aliased Tmp in the worklist.");
+ m_simplifyWorklist.append(victimIndex);
+ freezeMoves(victimIndex);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- bool hasBeenSimplified(Tmp tmp)
</del><ins>+ void freezeMoves(IndexType tmpIndex)
</ins><span class="cx"> {
</span><del>- return m_isOnSelectStack.quickGet(AbsoluteTmpMapper<type>::absoluteIndex(tmp)) || !!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
- }
</del><ins>+ forEachNodeMoves(tmpIndex, [this, tmpIndex] (IndexType moveIndex) {
+ if (!m_activeMoves.quickClear(moveIndex))
+ m_worklistMoves.takeMove(moveIndex);
</ins><span class="cx">
</span><del>- void decrementDegree(Tmp tmp)
- {
- ASSERT(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
</del><ins>+ const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
+ IndexType srcTmpIndex = moveOperands.srcIndex;
+ IndexType dstTmpIndex = moveOperands.dstIndex;
</ins><span class="cx">
</span><del>- unsigned oldDegree = m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]--;
- if (oldDegree == m_numberOfRegisters) {
- enableMovesOnValueAndAdjacents(tmp);
- m_spillWorklist.remove(tmp);
- if (isMoveRelated(tmp))
- m_freezeWorklist.add(tmp);
- else
- m_simplifyWorklist.append(tmp);
- }
- }
-
- template<typename Function>
- void forEachNodeMoves(Tmp tmp, Function function)
- {
- for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
- function(moveIndex);
- }
- }
-
- bool isMoveRelated(Tmp tmp)
- {
- for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
- return true;
- }
- return false;
- }
-
- void enableMovesOnValue(Tmp tmp)
- {
- for (unsigned moveIndex : m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.quickClear(moveIndex))
- m_worklistMoves.returnMove(moveIndex);
- }
- }
-
- void enableMovesOnValueAndAdjacents(Tmp tmp)
- {
- enableMovesOnValue(tmp);
-
- forEachAdjacent(tmp, [this] (Tmp adjacentTmp) {
- enableMovesOnValue(adjacentTmp);
</del><ins>+ IndexType originalOtherTmp = srcTmpIndex != tmpIndex ? srcTmpIndex : dstTmpIndex;
+ IndexType otherTmpIndex = getAlias(originalOtherTmp);
+ if (m_degrees[otherTmpIndex] < m_regsInPriorityOrder.size() && !isMoveRelated(otherTmpIndex)) {
+ if (m_freezeWorklist.remove(otherTmpIndex))
+ m_simplifyWorklist.append(otherTmpIndex);
+ }
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -384,12 +145,10 @@
</span><span class="cx"> {
</span><span class="cx"> unsigned moveIndex = m_worklistMoves.takeLastMove();
</span><span class="cx"> const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
</span><del>- Tmp u = moveOperands.src;
- u = getAlias(u);
- Tmp v = moveOperands.dst;
- v = getAlias(v);
</del><ins>+ IndexType u = getAlias(moveOperands.srcIndex);
+ IndexType v = getAlias(moveOperands.dstIndex);
</ins><span class="cx">
</span><del>- if (v.isReg())
</del><ins>+ if (isPrecolored(v))
</ins><span class="cx"> std::swap(u, v);
</span><span class="cx">
</span><span class="cx"> if (traceDebug)
</span><span class="lines">@@ -400,7 +159,7 @@
</span><span class="cx">
</span><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Coalesced\n");
</span><del>- } else if (v.isReg() || m_interferenceEdges.contains(InterferenceEdge(u, v))) {
</del><ins>+ } else if (isPrecolored(v) || m_interferenceEdges.contains(InterferenceEdge(u, v))) {
</ins><span class="cx"> addWorkList(u);
</span><span class="cx"> addWorkList(v);
</span><span class="cx">
</span><span class="lines">@@ -421,316 +180,261 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>- bool canBeSafelyCoalesced(Tmp u, Tmp v)
</del><ins>+ void assignColors()
</ins><span class="cx"> {
</span><del>- ASSERT(!v.isReg());
- if (u.isReg())
- return precoloredCoalescingHeuristic(u, v);
- return conservativeHeuristic(u, v);
- }
</del><ins>+ ASSERT(m_simplifyWorklist.isEmpty());
+ ASSERT(m_worklistMoves.isEmpty());
+ ASSERT(m_freezeWorklist.isEmpty());
+ ASSERT(m_spillWorklist.isEmpty());
</ins><span class="cx">
</span><del>- bool precoloredCoalescingHeuristic(Tmp u, Tmp v)
- {
- ASSERT(u.isReg());
- ASSERT(!v.isReg());
</del><ins>+ // Reclaim as much memory as possible.
+ m_interferenceEdges.clear();
+ m_degrees.clear();
+ m_moveList.clear();
+ m_worklistMoves.clear();
+ m_simplifyWorklist.clear();
+ m_spillWorklist.clear();
+ m_freezeWorklist.clear();
</ins><span class="cx">
</span><del>- // If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
- // there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
- // move, we may create an uncolorable graph.
- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
- for (Tmp adjacentTmp : adjacentsOfV) {
- if (!adjacentTmp.isReg()
- && !hasBeenSimplified(adjacentTmp)
- && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters
- && !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmp)))
- return false;
- }
- return true;
- }
</del><ins>+ // Try to color the Tmp on the stack.
+ m_coloredTmp.resize(m_adjacencyList.size());
</ins><span class="cx">
</span><del>- bool conservativeHeuristic(Tmp u, Tmp v)
- {
- // This is using the Briggs' conservative coalescing rule:
- // If the number of combined adjacent node with a degree >= K is less than K,
- // it is safe to combine the two nodes. The reason is that we know that if the graph
- // is colorable, we have fewer than K adjacents with high order and there is a color
- // for the current node.
- ASSERT(u != v);
- ASSERT(!u.isReg());
- ASSERT(!v.isReg());
</del><ins>+ while (!m_selectStack.isEmpty()) {
+ unsigned tmpIndex = m_selectStack.takeLast();
+ ASSERT(!isPrecolored(tmpIndex));
+ ASSERT(!m_coloredTmp[tmpIndex]);
</ins><span class="cx">
</span><del>- const auto& adjacentsOfU = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(u)];
- const auto& adjacentsOfV = m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
</del><ins>+ RegisterSet coloredRegisters;
+ for (IndexType adjacentTmpIndex : m_adjacencyList[tmpIndex]) {
+ IndexType aliasTmpIndex = getAlias(adjacentTmpIndex);
+ Reg reg = m_coloredTmp[aliasTmpIndex];
</ins><span class="cx">
</span><del>- if (adjacentsOfU.size() + adjacentsOfV.size() < m_numberOfRegisters) {
- // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
- return true;
- }
</del><ins>+ ASSERT(!isPrecolored(aliasTmpIndex) || (isPrecolored(aliasTmpIndex) && reg));
</ins><span class="cx">
</span><del>- HashSet<Tmp> highOrderAdjacents;
</del><ins>+ if (reg)
+ coloredRegisters.set(reg);
+ }
</ins><span class="cx">
</span><del>- for (Tmp adjacentTmp : adjacentsOfU) {
- ASSERT(adjacentTmp != v);
- ASSERT(adjacentTmp != u);
- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
- auto addResult = highOrderAdjacents.add(adjacentTmp);
- if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
- return false;
</del><ins>+ bool colorAssigned = false;
+ for (Reg reg : m_regsInPriorityOrder) {
+ if (!coloredRegisters.get(reg)) {
+ m_coloredTmp[tmpIndex] = reg;
+ colorAssigned = true;
+ break;
+ }
</ins><span class="cx"> }
</span><ins>+
+ if (!colorAssigned)
+ m_spilledTmps.append(tmpIndex);
</ins><span class="cx"> }
</span><del>- for (Tmp adjacentTmp : adjacentsOfV) {
- ASSERT(adjacentTmp != u);
- ASSERT(adjacentTmp != v);
- if (!hasBeenSimplified(adjacentTmp) && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(adjacentTmp)] >= m_numberOfRegisters) {
- auto addResult = highOrderAdjacents.add(adjacentTmp);
- if (addResult.isNewEntry && highOrderAdjacents.size() >= m_numberOfRegisters)
- return false;
- }
- }
</del><ins>+ m_selectStack.clear();
</ins><span class="cx">
</span><del>- ASSERT(highOrderAdjacents.size() < m_numberOfRegisters);
- return true;
</del><ins>+ if (m_spilledTmps.isEmpty())
+ m_coalescedTmpsAtSpill.clear();
+ else
+ m_coloredTmp.clear();
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void addWorkList(Tmp tmp)
</del><ins>+private:
+ void initializeDegrees(unsigned tmpArraySize)
</ins><span class="cx"> {
</span><del>- if (!tmp.isReg() && m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] < m_numberOfRegisters && !isMoveRelated(tmp)) {
- m_freezeWorklist.remove(tmp);
- m_simplifyWorklist.append(tmp);
- }
</del><ins>+ m_degrees.resize(tmpArraySize);
+
+ // All precolored registers have an "infinite" degree.
+ unsigned firstNonRegIndex = m_lastPrecoloredRegisterIndex + 1;
+ for (unsigned i = 0; i < firstNonRegIndex; ++i)
+ m_degrees[i] = std::numeric_limits<unsigned>::max();
+
+ bzero(m_degrees.data() + firstNonRegIndex, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void combine(Tmp u, Tmp v)
</del><ins>+ void addEdgeDistinct(IndexType a, IndexType b)
</ins><span class="cx"> {
</span><del>- if (!m_freezeWorklist.remove(v))
- m_spillWorklist.remove(v);
</del><ins>+ ASSERT(a != b);
+ if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
+ if (!isPrecolored(a)) {
+ ASSERT(!m_adjacencyList[a].contains(b));
+ m_adjacencyList[a].append(b);
+ m_degrees[a]++;
+ }
</ins><span class="cx">
</span><del>- ASSERT(!m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)]);
- m_coalescedTmps[AbsoluteTmpMapper<type>::absoluteIndex(v)] = u;
</del><ins>+ if (!isPrecolored(b)) {
+ ASSERT(!m_adjacencyList[b].contains(a));
+ m_adjacencyList[b].append(a);
+ m_degrees[b]++;
+ }
+ }
+ }
</ins><span class="cx">
</span><del>- auto& vMoves = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(v)];
- m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
</del><ins>+ void decrementDegree(IndexType tmpIndex)
+ {
+ ASSERT(m_degrees[tmpIndex]);
</ins><span class="cx">
</span><del>- forEachAdjacent(v, [this, u] (Tmp adjacentTmp) {
- addEdge(adjacentTmp, u);
- decrementDegree(adjacentTmp);
- });
</del><ins>+ unsigned oldDegree = m_degrees[tmpIndex]--;
+ if (oldDegree == m_regsInPriorityOrder.size()) {
+ enableMovesOnValueAndAdjacents(tmpIndex);
+ m_spillWorklist.remove(tmpIndex);
+ if (isMoveRelated(tmpIndex))
+ m_freezeWorklist.add(tmpIndex);
+ else
+ m_simplifyWorklist.append(tmpIndex);
+ }
+ }
</ins><span class="cx">
</span><del>- if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(u)] >= m_numberOfRegisters && m_freezeWorklist.remove(u))
- m_spillWorklist.add(u);
</del><ins>+ bool isMoveRelated(IndexType tmpIndex)
+ {
+ for (unsigned moveIndex : m_moveList[tmpIndex]) {
+ if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
+ return true;
+ }
+ return false;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void freeze()
</del><ins>+ template<typename Function>
+ void forEachAdjacent(IndexType tmpIndex, Function function)
</ins><span class="cx"> {
</span><del>- Tmp victim = m_freezeWorklist.takeAny();
- ASSERT_WITH_MESSAGE(getAlias(victim) == victim, "coalesce() should not leave aliased Tmp in the worklist.");
- m_simplifyWorklist.append(victim);
- freezeMoves(victim);
</del><ins>+ for (IndexType adjacentTmpIndex : m_adjacencyList[tmpIndex]) {
+ if (!hasBeenSimplified(adjacentTmpIndex))
+ function(adjacentTmpIndex);
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void freezeMoves(Tmp tmp)
</del><ins>+ bool hasBeenSimplified(IndexType tmpIndex)
</ins><span class="cx"> {
</span><del>- forEachNodeMoves(tmp, [this, tmp] (unsigned moveIndex) {
- if (!m_activeMoves.quickClear(moveIndex))
- m_worklistMoves.takeMove(moveIndex);
</del><ins>+ return m_isOnSelectStack.quickGet(tmpIndex) || !!m_coalescedTmps[tmpIndex];
+ }
</ins><span class="cx">
</span><del>- const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
- Tmp originalOtherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
- Tmp otherTmp = getAlias(originalOtherTmp);
- if (m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
- if (m_freezeWorklist.remove(otherTmp))
- m_simplifyWorklist.append(otherTmp);
- }
- });
</del><ins>+ template<typename Function>
+ void forEachNodeMoves(IndexType tmpIndex, Function function)
+ {
+ for (unsigned moveIndex : m_moveList[tmpIndex]) {
+ if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
+ function(moveIndex);
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void selectSpill()
</del><ins>+ void enableMovesOnValue(IndexType tmpIndex)
</ins><span class="cx"> {
</span><del>- if (!m_hasSelectedSpill) {
- m_hasSelectedSpill = true;
-
- if (m_hasCoalescedNonTrivialMove)
- m_coalescedTmpsAtSpill = m_coalescedTmps;
</del><ins>+ for (unsigned moveIndex : m_moveList[tmpIndex]) {
+ if (m_activeMoves.quickClear(moveIndex))
+ m_worklistMoves.returnMove(moveIndex);
</ins><span class="cx"> }
</span><ins>+ }
</ins><span class="cx">
</span><del>- auto iterator = m_spillWorklist.begin();
</del><ins>+ void enableMovesOnValueAndAdjacents(IndexType tmpIndex)
+ {
+ enableMovesOnValue(tmpIndex);
</ins><span class="cx">
</span><del>- while (iterator != m_spillWorklist.end() && m_unspillableTmp.contains(*iterator))
- ++iterator;
</del><ins>+ forEachAdjacent(tmpIndex, [this] (IndexType adjacentTmpIndex) {
+ enableMovesOnValue(adjacentTmpIndex);
+ });
+ }
</ins><span class="cx">
</span><del>- RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
</del><ins>+ bool isPrecolored(IndexType tmpIndex)
+ {
+ return tmpIndex <= m_lastPrecoloredRegisterIndex;
+ }
</ins><span class="cx">
</span><del>- // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
- // gets a register.
- auto score = [&] (Tmp tmp) -> double {
- // Air exposes the concept of "fast tmps", and we interpret that to mean that the tmp
- // should always be in a register.
- if (m_code.isFastTmp(tmp))
- return 0;
-
- // 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;
- };
-
- auto victimIterator = iterator;
- double maxScore = score(*iterator);
-
- ++iterator;
- for (;iterator != m_spillWorklist.end(); ++iterator) {
- double tmpScore = score(*iterator);
- if (tmpScore > maxScore) {
- if (m_unspillableTmp.contains(*iterator))
- continue;
-
- victimIterator = iterator;
- maxScore = tmpScore;
- }
</del><ins>+ void addWorkList(IndexType tmpIndex)
+ {
+ if (!isPrecolored(tmpIndex) && m_degrees[tmpIndex] < m_regsInPriorityOrder.size() && !isMoveRelated(tmpIndex)) {
+ m_freezeWorklist.remove(tmpIndex);
+ m_simplifyWorklist.append(tmpIndex);
</ins><span class="cx"> }
</span><del>-
- Tmp victimTmp = *victimIterator;
- m_spillWorklist.remove(victimIterator);
- m_simplifyWorklist.append(victimTmp);
- freezeMoves(victimTmp);
</del><span class="cx"> }
</span><span class="cx">
</span><del>- void allocate()
</del><ins>+ void combine(IndexType u, IndexType v)
</ins><span class="cx"> {
</span><del>- ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
</del><ins>+ if (!m_freezeWorklist.remove(v))
+ m_spillWorklist.remove(v);
</ins><span class="cx">
</span><del>- makeWorkList();
</del><ins>+ ASSERT(!m_coalescedTmps[v]);
+ m_coalescedTmps[v] = u;
</ins><span class="cx">
</span><del>- if (debug) {
- dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
- dumpInterferenceGraphInDot(WTF::dataFile());
- dataLog("Initial work list\n");
- dumpWorkLists(WTF::dataFile());
- }
</del><ins>+ auto& vMoves = m_moveList[v];
+ m_moveList[u].add(vMoves.begin(), vMoves.end());
</ins><span class="cx">
</span><del>- do {
- if (traceDebug) {
- dataLog("Before Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
</del><ins>+ forEachAdjacent(v, [this, u] (IndexType adjacentTmpIndex) {
+ addEdgeDistinct(adjacentTmpIndex, u);
+ decrementDegree(adjacentTmpIndex);
+ });
</ins><span class="cx">
</span><del>- if (!m_simplifyWorklist.isEmpty())
- simplify();
- else if (!m_worklistMoves.isEmpty())
- coalesce();
- else if (!m_freezeWorklist.isEmpty())
- freeze();
- else if (!m_spillWorklist.isEmpty())
- selectSpill();
</del><ins>+ if (m_degrees[u] >= m_regsInPriorityOrder.size() && m_freezeWorklist.remove(u))
+ m_spillWorklist.add(u);
+ }
</ins><span class="cx">
</span><del>- if (traceDebug) {
- dataLog("After Graph simplification iteration\n");
- dumpWorkLists(WTF::dataFile());
- }
- } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
-
- assignColors();
</del><ins>+ bool canBeSafelyCoalesced(IndexType u, IndexType v)
+ {
+ ASSERT(!isPrecolored(v));
+ if (isPrecolored(u))
+ return precoloredCoalescingHeuristic(u, v);
+ return conservativeHeuristic(u, v);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void assignColors()
</del><ins>+ bool conservativeHeuristic(IndexType u, IndexType v)
</ins><span class="cx"> {
</span><del>- ASSERT(m_simplifyWorklist.isEmpty());
- ASSERT(m_worklistMoves.isEmpty());
- ASSERT(m_freezeWorklist.isEmpty());
- ASSERT(m_spillWorklist.isEmpty());
</del><ins>+ // This is using the Briggs' conservative coalescing rule:
+ // If the number of combined adjacent node with a degree >= K is less than K,
+ // it is safe to combine the two nodes. The reason is that we know that if the graph
+ // is colorable, we have fewer than K adjacents with high order and there is a color
+ // for the current node.
+ ASSERT(u != v);
+ ASSERT(!isPrecolored(u));
+ ASSERT(!isPrecolored(v));
</ins><span class="cx">
</span><del>- // Reclaim as much memory as possible.
- m_interferenceEdges.clear();
- m_degrees.clear();
- m_moveList.clear();
- m_worklistMoves.clear();
- m_simplifyWorklist.clear();
- m_spillWorklist.clear();
- m_freezeWorklist.clear();
</del><ins>+ const auto& adjacentsOfU = m_adjacencyList[u];
+ const auto& adjacentsOfV = m_adjacencyList[v];
</ins><span class="cx">
</span><del>- // Try to color the Tmp on the stack.
- m_coloredTmp.resize(m_adjacencyList.size());
- const auto& registersInPriorityOrder = regsInPriorityOrder(type);
</del><ins>+ if (adjacentsOfU.size() + adjacentsOfV.size() < m_regsInPriorityOrder.size()) {
+ // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
+ return true;
+ }
</ins><span class="cx">
</span><del>- while (!m_selectStack.isEmpty()) {
- Tmp tmp = m_selectStack.takeLast();
- ASSERT(!tmp.isReg());
- ASSERT(!m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
</del><ins>+ HashSet<IndexType> highOrderAdjacents;
</ins><span class="cx">
</span><del>- RegisterSet coloredRegisters;
- for (Tmp adjacentTmp : m_adjacencyList[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]) {
- Tmp aliasTmp = getAlias(adjacentTmp);
- if (aliasTmp.isReg()) {
- coloredRegisters.set(aliasTmp.reg());
- continue;
- }
-
- Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(aliasTmp)];
- if (reg)
- coloredRegisters.set(reg);
</del><ins>+ for (IndexType adjacentTmpIndex : adjacentsOfU) {
+ ASSERT(adjacentTmpIndex != v);
+ ASSERT(adjacentTmpIndex != u);
+ if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()) {
+ auto addResult = highOrderAdjacents.add(adjacentTmpIndex);
+ if (addResult.isNewEntry && highOrderAdjacents.size() >= m_regsInPriorityOrder.size())
+ return false;
</ins><span class="cx"> }
</span><del>-
- bool colorAssigned = false;
- for (Reg reg : registersInPriorityOrder) {
- if (!coloredRegisters.get(reg)) {
- m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)] = reg;
- colorAssigned = true;
- break;
- }
</del><ins>+ }
+ for (IndexType adjacentTmpIndex : adjacentsOfV) {
+ ASSERT(adjacentTmpIndex != u);
+ ASSERT(adjacentTmpIndex != v);
+ if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()) {
+ auto addResult = highOrderAdjacents.add(adjacentTmpIndex);
+ if (addResult.isNewEntry && highOrderAdjacents.size() >= m_regsInPriorityOrder.size())
+ return false;
</ins><span class="cx"> }
</span><del>-
- if (!colorAssigned)
- m_spilledTmp.add(tmp);
</del><span class="cx"> }
</span><del>- m_selectStack.clear();
</del><span class="cx">
</span><del>- if (m_spilledTmp.isEmpty())
- m_coalescedTmpsAtSpill.clear();
- else
- m_coloredTmp.clear();
</del><ins>+ ASSERT(highOrderAdjacents.size() < m_regsInPriorityOrder.size());
+ return true;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-#if PLATFORM(COCOA)
-#pragma mark - Debugging helpers.
-#endif
-
- void dumpInterferenceGraphInDot(PrintStream& out)
</del><ins>+ bool precoloredCoalescingHeuristic(IndexType u, IndexType v)
</ins><span class="cx"> {
</span><del>- out.print("graph InterferenceGraph { \n");
</del><ins>+ ASSERT(isPrecolored(u));
+ ASSERT(!isPrecolored(v));
</ins><span class="cx">
</span><del>- HashSet<Tmp> tmpsWithInterferences;
- for (const auto& edge : m_interferenceEdges) {
- tmpsWithInterferences.add(edge.first());
- tmpsWithInterferences.add(edge.second());
</del><ins>+ // If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
+ // there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
+ // move, we may create an uncolorable graph.
+ const auto& adjacentsOfV = m_adjacencyList[v];
+ for (unsigned adjacentTmpIndex : adjacentsOfV) {
+ if (!isPrecolored(adjacentTmpIndex)
+ && !hasBeenSimplified(adjacentTmpIndex)
+ && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()
+ && !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmpIndex)))
+ return false;
</ins><span class="cx"> }
</span><del>-
- for (const auto& tmp : tmpsWithInterferences)
- out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
-
- for (const auto& edge : m_interferenceEdges)
- out.print(" ", edge.first().internalValue(), " -- ", edge.second().internalValue(), ";\n");
- out.print("}\n");
</del><ins>+ return true;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- void dumpWorkLists(PrintStream& out)
- {
- out.print("Simplify work list:\n");
- for (Tmp tmp : m_simplifyWorklist)
- out.print(" ", tmp, "\n");
- out.printf("Moves work list is empty? %d\n", m_worklistMoves.isEmpty());
- out.print("Freeze work list:\n");
- for (Tmp tmp : m_freezeWorklist)
- out.print(" ", tmp, "\n");
- out.print("Spill work list:\n");
- for (Tmp tmp : m_spillWorklist)
- out.print(" ", tmp, "\n");
- }
-
</del><ins>+protected:
</ins><span class="cx"> #if PLATFORM(COCOA)
</span><span class="cx"> #pragma mark -
</span><span class="cx"> #endif
</span><span class="lines">@@ -743,17 +447,15 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- InterferenceEdge(Tmp a, Tmp b)
</del><ins>+ InterferenceEdge(IndexType a, IndexType b)
</ins><span class="cx"> {
</span><del>- ASSERT(a.internalValue());
- ASSERT(b.internalValue());
</del><ins>+ ASSERT(a);
+ ASSERT(b);
</ins><span class="cx"> ASSERT_WITH_MESSAGE(a != b, "A Tmp can never interfere with itself. Doing so would force it to be the superposition of two registers.");
</span><span class="cx">
</span><del>- unsigned aInternal = a.internalValue();
- unsigned bInternal = b.internalValue();
- if (bInternal < aInternal)
- std::swap(aInternal, bInternal);
- m_value = static_cast<uint64_t>(aInternal) << 32 | bInternal;
</del><ins>+ if (b < a)
+ std::swap(a, b);
+ m_value = static_cast<uint64_t>(a) << 32 | b;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> InterferenceEdge(WTF::HashTableDeletedValueType)
</span><span class="lines">@@ -761,14 +463,14 @@
</span><span class="cx"> {
</span><span class="cx"> }
</span><span class="cx">
</span><del>- Tmp first() const
</del><ins>+ IndexType first() const
</ins><span class="cx"> {
</span><del>- return Tmp::tmpForInternalValue(m_value >> 32);
</del><ins>+ return m_value >> 32 & 0xffffffff;
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- Tmp second() const
</del><ins>+ IndexType second() const
</ins><span class="cx"> {
</span><del>- return Tmp::tmpForInternalValue(m_value & 0xffffffff);
</del><ins>+ return m_value & 0xffffffff;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool operator==(const InterferenceEdge other) const
</span><span class="lines">@@ -802,38 +504,35 @@
</span><span class="cx"> };
</span><span class="cx"> typedef SimpleClassHashTraits<InterferenceEdge> InterferenceEdgeHashTraits;
</span><span class="cx">
</span><del>- Code& m_code;
- const UseCounts<Tmp>& m_useCounts;
</del><ins>+ const Vector<Reg>& m_regsInPriorityOrder;
+ IndexType m_lastPrecoloredRegisterIndex { 0 };
</ins><span class="cx">
</span><del>- const HashSet<Tmp>& m_unspillableTmp;
- unsigned m_numberOfRegisters { 0 };
-
</del><span class="cx"> // The interference graph.
</span><span class="cx"> HashSet<InterferenceEdge, InterferenceEdgeHash, InterferenceEdgeHashTraits> m_interferenceEdges;
</span><del>- Vector<Vector<Tmp, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
- Vector<unsigned, 0, UnsafeVectorOverflow> m_degrees;
</del><ins>+ Vector<Vector<IndexType, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
+ Vector<IndexType, 0, UnsafeVectorOverflow> m_degrees;
</ins><span class="cx">
</span><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><del>- Tmp src;
- Tmp dst;
</del><ins>+ IndexType srcIndex;
+ IndexType dstIndex;
</ins><span class="cx"> };
</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<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> m_moveList;
</del><ins>+ Vector<HashSet<IndexType, typename DefaultHash<IndexType>::Hash, WTF::UnsignedWithZeroKeyHashTraits<IndexType>>> m_moveList;
</ins><span class="cx">
</span><span class="cx"> // Colors.
</span><span class="cx"> Vector<Reg, 0, UnsafeVectorOverflow> m_coloredTmp;
</span><del>- HashSet<Tmp> m_spilledTmp;
</del><ins>+ Vector<IndexType> m_spilledTmps;
</ins><span class="cx">
</span><span class="cx"> // Values that have been coalesced with an other value.
</span><del>- Vector<Tmp, 0, UnsafeVectorOverflow> m_coalescedTmps;
</del><ins>+ Vector<IndexType, 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><del>- Vector<Tmp> m_selectStack;
</del><ins>+ Vector<IndexType> m_selectStack;
</ins><span class="cx">
</span><span class="cx"> struct OrderedMoveSet {
</span><span class="cx"> unsigned addMove()
</span><span class="lines">@@ -914,155 +613,571 @@
</span><span class="cx"> // Set of "move" not yet ready for coalescing.
</span><span class="cx"> BitVector m_activeMoves;
</span><span class="cx"> // Low-degree, non-Move related.
</span><del>- Vector<Tmp> m_simplifyWorklist;
</del><ins>+ Vector<IndexType> m_simplifyWorklist;
</ins><span class="cx"> // High-degree Tmp.
</span><del>- HashSet<Tmp> m_spillWorklist;
</del><ins>+ HashSet<IndexType> m_spillWorklist;
</ins><span class="cx"> // Low-degree, Move related.
</span><del>- HashSet<Tmp> m_freezeWorklist;
</del><ins>+ HashSet<IndexType> m_freezeWorklist;
</ins><span class="cx">
</span><span class="cx"> bool m_hasSelectedSpill { false };
</span><span class="cx"> bool m_hasCoalescedNonTrivialMove { false };
</span><span class="cx">
</span><span class="cx"> // The mapping of Tmp to their alias for Moves that are always coalescing regardless of spilling.
</span><del>- Vector<Tmp, 0, UnsafeVectorOverflow> m_coalescedTmpsAtSpill;
</del><ins>+ Vector<IndexType, 0, UnsafeVectorOverflow> m_coalescedTmpsAtSpill;
</ins><span class="cx"> };
</span><span class="cx">
</span><ins>+// This perform all the tasks that are specific to certain register type.
</ins><span class="cx"> template<Arg::Type type>
</span><del>-bool isUselessMoveInst(const Inst& inst)
-{
- return MoveInstHelper<type>::mayBeCoalescable(inst) && inst.args[0].tmp() == inst.args[1].tmp();
-}
</del><ins>+class ColoringAllocator : public AbstractColoringAllocator<unsigned> {
+public:
+ ColoringAllocator(Code& code, const UseCounts<Tmp>& useCounts, const HashSet<unsigned>& unspillableTmp)
+ : AbstractColoringAllocator<unsigned>(regsInPriorityOrder(type), AbsoluteTmpMapper<type>::lastMachineRegisterIndex(), tmpArraySize(code))
+ , m_code(code)
+ , m_useCounts(useCounts)
+ , m_unspillableTmps(unspillableTmp)
+ {
+ initializePrecoloredTmp();
+ build();
+ allocate();
+ }
</ins><span class="cx">
</span><del>-template<Arg::Type type>
-void assignRegisterToTmpInProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator)
-{
- for (BasicBlock* block : code) {
- // Give Tmp a valid register.
- for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
- Inst& inst = block->at(instIndex);
- inst.forEachTmpFast([&] (Tmp& tmp) {
- if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
- return;
</del><ins>+ Tmp getAlias(Tmp tmp) const
+ {
+ return AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(getAlias(AbsoluteTmpMapper<type>::absoluteIndex(tmp)));
+ }
</ins><span class="cx">
</span><del>- Tmp aliasTmp = allocator.getAlias(tmp);
- Tmp assignedTmp;
- if (aliasTmp.isReg())
- assignedTmp = Tmp(aliasTmp.reg());
- else {
- auto reg = allocator.allocatedReg(aliasTmp);
- ASSERT(reg);
- assignedTmp = Tmp(reg);
- }
- ASSERT(assignedTmp.isReg());
- tmp = assignedTmp;
- });
</del><ins>+ bool isUselessMove(const Inst& inst) const
+ {
+ return mayBeCoalescable(inst) && inst.args[0].tmp() == inst.args[1].tmp();
+ }
+
+ Tmp getAliasWhenSpilling(Tmp tmp) const
+ {
+ ASSERT_WITH_MESSAGE(!m_spilledTmps.isEmpty(), "This function is only valid for coalescing during spilling.");
+
+ if (m_coalescedTmpsAtSpill.isEmpty())
+ return tmp;
+
+ unsigned aliasIndex = AbsoluteTmpMapper<type>::absoluteIndex(tmp);
+ while (unsigned nextAliasIndex = m_coalescedTmpsAtSpill[aliasIndex])
+ aliasIndex = nextAliasIndex;
+
+ Tmp alias = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(aliasIndex);
+
+ ASSERT_WITH_MESSAGE(!m_spilledTmps.contains(aliasIndex) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
+
+ return alias;
+ }
+
+ template<typename IndexIterator>
+ class IndexToTmpIteratorAdaptor {
+ public:
+ IndexToTmpIteratorAdaptor(IndexIterator&& indexIterator)
+ : m_indexIterator(WTF::move(indexIterator))
+ {
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // Remove all the useless moves we created in this block.
- block->insts().removeAllMatching(isUselessMoveInst<type>);
</del><ins>+ Tmp operator*() const { return AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*m_indexIterator); }
+ IndexToTmpIteratorAdaptor& operator++() { ++m_indexIterator; return *this; }
+
+ bool operator==(const IndexToTmpIteratorAdaptor& other) const
+ {
+ return m_indexIterator == other.m_indexIterator;
+ }
+
+ bool operator!=(const IndexToTmpIteratorAdaptor& other) const
+ {
+ return !(*this == other);
+ }
+
+ private:
+ IndexIterator m_indexIterator;
+ };
+
+ template<typename Collection>
+ class IndexToTmpIterableAdaptor {
+ public:
+ IndexToTmpIterableAdaptor(const Collection& collection)
+ : m_collection(collection)
+ {
+ }
+
+ IndexToTmpIteratorAdaptor<typename Collection::const_iterator> begin() const
+ {
+ return m_collection.begin();
+ }
+
+ IndexToTmpIteratorAdaptor<typename Collection::const_iterator> end() const
+ {
+ return m_collection.end();
+ }
+
+ private:
+ const Collection& m_collection;
+ };
+
+ IndexToTmpIterableAdaptor<Vector<unsigned>> spilledTmps() const { return m_spilledTmps; }
+
+ bool requiresSpilling() const { return !m_spilledTmps.isEmpty(); }
+
+ Reg allocatedReg(Tmp tmp) const
+ {
+ ASSERT(!tmp.isReg());
+ ASSERT(m_coloredTmp.size());
+ ASSERT(tmp.isGP() == (type == Arg::GP));
+
+ Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
+ if (!reg) {
+ // We only care about Tmps that interfere. A Tmp that never interfere with anything
+ // can take any register.
+ reg = regsInPriorityOrder(type).first();
+ }
+ return reg;
</ins><span class="cx"> }
</span><del>-}
</del><span class="cx">
</span><del>-template<Arg::Type type>
-void addSpillAndFillToProgram(Code& code, const IteratedRegisterCoalescingAllocator<type>& allocator, HashSet<Tmp>& unspillableTmp)
-{
- const HashSet<Tmp>& spilledTmp = allocator.spilledTmp();
</del><ins>+private:
+ static unsigned tmpArraySize(Code& code)
+ {
+ unsigned numTmps = code.numTmps(type);
+ return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
+ }
</ins><span class="cx">
</span><del>- // All the spilled values become unspillable.
- unspillableTmp.add(spilledTmp.begin(), spilledTmp.end());
</del><ins>+ void initializePrecoloredTmp()
+ {
+ m_coloredTmp.resize(m_lastPrecoloredRegisterIndex + 1);
+ for (unsigned i = 1; i <= m_lastPrecoloredRegisterIndex; ++i) {
+ Tmp tmp = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(i);
+ ASSERT(tmp.isReg());
+ m_coloredTmp[i] = tmp.reg();
+ }
+ }
</ins><span class="cx">
</span><del>- // Allocate stack slot for each spilled value.
- HashMap<Tmp, StackSlot*> stackSlots;
- for (Tmp tmp : spilledTmp) {
- bool isNewTmp = stackSlots.add(tmp, code.addStackSlot(8, StackSlotKind::Anonymous)).isNewEntry;
- ASSERT_UNUSED(isNewTmp, isNewTmp);
</del><ins>+ void build()
+ {
+ TmpLiveness<type> liveness(m_code);
+ for (BasicBlock* block : m_code) {
+ typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
+ for (unsigned instIndex = block->size(); instIndex--;) {
+ Inst& inst = block->at(instIndex);
+ Inst* nextInst = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
+ build(inst, nextInst, localCalc);
+ localCalc.execute(instIndex);
+ }
+ }
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // Rewrite the program to get rid of the spilled Tmp.
- InsertionSet insertionSet(code);
- for (BasicBlock* block : code) {
- bool hasAliasedTmps = false;
</del><ins>+ void build(Inst& inst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
+ {
+ inst.forEachTmpWithExtraClobberedRegs(
+ nextInst,
+ [&] (const Tmp& arg, Arg::Role role, Arg::Type argType) {
+ if (!Arg::isDef(role) || argType != type)
+ return;
+
+ // All the Def()s interfere with each other and with all the extra clobbered Tmps.
+ // We should not use forEachDefAndExtraClobberedTmp() here since colored Tmps
+ // do not need interference edges in our implementation.
+ inst.forEachTmp([&] (Tmp& otherArg, Arg::Role role, Arg::Type argType) {
+ if (!Arg::isDef(role) || argType != type)
+ return;
</ins><span class="cx">
</span><del>- for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
- Inst& inst = block->at(instIndex);
</del><ins>+ addEdge(arg, otherArg);
+ });
+ });
</ins><span class="cx">
</span><del>- // Try to replace the register use by memory use when possible.
- for (unsigned i = 0; i < inst.args.size(); ++i) {
- Arg& arg = inst.args[i];
- if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
- auto stackSlotEntry = stackSlots.find(arg.tmp());
- if (stackSlotEntry != stackSlots.end() && inst.admitsStack(i))
- arg = Arg::stack(stackSlotEntry->value);
</del><ins>+ if (mayBeCoalescable(inst)) {
+ // We do not want the Use() of this move to interfere with the Def(), even if it is live
+ // after the Move. If we were to add the interference edge, it would be impossible to
+ // coalesce the Move even if the two Tmp never interfere anywhere.
+ Tmp defTmp;
+ Tmp useTmp;
+ inst.forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type) {
+ if (Arg::isDef(role))
+ defTmp = argTmp;
+ else {
+ ASSERT(Arg::isEarlyUse(role));
+ useTmp = argTmp;
</ins><span class="cx"> }
</span><ins>+ });
+ ASSERT(defTmp);
+ ASSERT(useTmp);
+
+ unsigned nextMoveIndex = m_coalescingCandidates.size();
+ m_coalescingCandidates.append({ AbsoluteTmpMapper<type>::absoluteIndex(useTmp), AbsoluteTmpMapper<type>::absoluteIndex(defTmp) });
+
+ unsigned newIndexInWorklist = m_worklistMoves.addMove();
+ ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
+
+ ASSERT(nextMoveIndex <= m_activeMoves.size());
+ m_activeMoves.ensureSize(nextMoveIndex + 1);
+
+ for (const Arg& arg : inst.args) {
+ auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
+ list.add(nextMoveIndex);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>- // For every other case, add Load/Store as needed.
- inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Arg::Type argType) {
- if (tmp.isReg() || argType != type)
- return;
</del><ins>+ for (const Tmp& liveTmp : localCalc.live()) {
+ if (liveTmp != useTmp)
+ addEdge(defTmp, liveTmp);
+ }
</ins><span class="cx">
</span><del>- auto stackSlotEntry = stackSlots.find(tmp);
- if (stackSlotEntry == stackSlots.end()) {
- Tmp alias = allocator.getAliasWhenSpilling(tmp);
- if (alias != tmp) {
- tmp = alias;
- hasAliasedTmps = true;
</del><ins>+ // The next instruction could have early clobbers. We need to consider those now.
+ if (nextInst && nextInst->hasSpecial()) {
+ nextInst->extraEarlyClobberedRegs().forEach([&] (Reg reg) {
+ if (reg.isGPR() == (type == Arg::GP)) {
+ for (const Tmp& liveTmp : localCalc.live())
+ addEdge(Tmp(reg), liveTmp);
</ins><span class="cx"> }
</span><ins>+ });
+ }
+ } else
+ addEdges(inst, nextInst, localCalc.live());
+ }
+
+ void addEdges(Inst& inst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmps)
+ {
+ // All the Def()s interfere with everthing live.
+ inst.forEachTmpWithExtraClobberedRegs(
+ nextInst,
+ [&] (const Tmp& arg, Arg::Role role, Arg::Type argType) {
+ if (!Arg::isDef(role) || argType != type)
</ins><span class="cx"> return;
</span><ins>+
+ for (const Tmp& liveTmp : liveTmps) {
+ if (liveTmp.isGP() == (type == Arg::GP))
+ addEdge(arg, liveTmp);
</ins><span class="cx"> }
</span><ins>+ });
+ }
</ins><span class="cx">
</span><del>- Arg arg = Arg::stack(stackSlotEntry->value);
- Opcode move = type == Arg::GP ? Move : MoveDouble;
</del><ins>+ void addEdge(Tmp a, Tmp b)
+ {
+ ASSERT_WITH_MESSAGE(a.isGP() == b.isGP(), "An interference between registers of different types does not make sense, it can lead to non-colorable graphs.");
</ins><span class="cx">
</span><del>- if (Arg::isAnyUse(role)) {
- Tmp newTmp = code.newTmp(type);
- insertionSet.insert(instIndex, move, inst.origin, arg, newTmp);
- tmp = newTmp;
</del><ins>+ addEdge(AbsoluteTmpMapper<type>::absoluteIndex(a), AbsoluteTmpMapper<type>::absoluteIndex(b));
+ }
</ins><span class="cx">
</span><del>- // Any new Fill() should never be spilled.
- unspillableTmp.add(tmp);
- }
- if (Arg::isDef(role))
- insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
- });
</del><ins>+ bool mayBeCoalescable(const Inst& inst) const
+ {
+ switch (type) {
+ case Arg::GP:
+ switch (inst.opcode) {
+ case Move:
+ break;
+ default:
+ return false;
+ }
+ break;
+ case Arg::FP:
+ switch (inst.opcode) {
+ case MoveFloat:
+ case MoveDouble:
+ break;
+ default:
+ return false;
+ }
+ break;
</ins><span class="cx"> }
</span><del>- insertionSet.execute(block);
</del><span class="cx">
</span><del>- if (hasAliasedTmps)
- block->insts().removeAllMatching(isUselessMoveInst<type>);
</del><ins>+ ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
+
+ if (!inst.args[0].isTmp() || !inst.args[1].isTmp())
+ return false;
+
+ ASSERT(inst.args[0].type() == type);
+ ASSERT(inst.args[1].type() == type);
+
+ return true;
</ins><span class="cx"> }
</span><del>-}
</del><span class="cx">
</span><del>-template<Arg::Type type>
-void iteratedRegisterCoalescingOnType(
- Code& code, const UseCounts<Tmp>& useCounts, unsigned& numIterations)
-{
- HashSet<Tmp> unspillableTmps;
- while (true) {
- numIterations++;
- IteratedRegisterCoalescingAllocator<type> allocator(code, useCounts, unspillableTmps);
- if (allocator.spilledTmp().isEmpty()) {
- assignRegisterToTmpInProgram(code, allocator);
- return;
</del><ins>+ void selectSpill()
+ {
+ if (!m_hasSelectedSpill) {
+ m_hasSelectedSpill = true;
+
+ if (m_hasCoalescedNonTrivialMove)
+ m_coalescedTmpsAtSpill = m_coalescedTmps;
</ins><span class="cx"> }
</span><del>- addSpillAndFillToProgram<type>(code, allocator, unspillableTmps);
</del><ins>+
+ auto iterator = m_spillWorklist.begin();
+
+ while (iterator != m_spillWorklist.end() && m_unspillableTmps.contains(*iterator))
+ ++iterator;
+
+ RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
+
+ // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
+ // gets a register.
+ auto score = [&] (Tmp tmp) -> double {
+ // Air exposes the concept of "fast tmps", and we interpret that to mean that the tmp
+ // should always be in a register.
+ if (m_code.isFastTmp(tmp))
+ return 0;
+
+ // 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;
+ };
+
+ auto victimIterator = iterator;
+ double maxScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
+
+ ++iterator;
+ for (;iterator != m_spillWorklist.end(); ++iterator) {
+ double tmpScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
+ if (tmpScore > maxScore) {
+ if (m_unspillableTmps.contains(*iterator))
+ continue;
+
+ victimIterator = iterator;
+ maxScore = tmpScore;
+ }
+ }
+
+ unsigned victimIndex = *victimIterator;
+ m_spillWorklist.remove(victimIterator);
+ m_simplifyWorklist.append(victimIndex);
+
+ freezeMoves(victimIndex);
</ins><span class="cx"> }
</span><del>-}
</del><span class="cx">
</span><ins>+ void allocate()
+ {
+ ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
+
+ makeWorkList();
+
+ if (debug) {
+ dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
+ dumpInterferenceGraphInDot(WTF::dataFile());
+ dataLog("Initial work list\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ do {
+ if (traceDebug) {
+ dataLog("Before Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+
+ if (!m_simplifyWorklist.isEmpty())
+ simplify();
+ else if (!m_worklistMoves.isEmpty())
+ coalesce();
+ else if (!m_freezeWorklist.isEmpty())
+ freeze();
+ else if (!m_spillWorklist.isEmpty())
+ selectSpill();
+
+ if (traceDebug) {
+ dataLog("After Graph simplification iteration\n");
+ dumpWorkLists(WTF::dataFile());
+ }
+ } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
+
+ assignColors();
+ }
+
+#if PLATFORM(COCOA)
+#pragma mark - Debugging helpers.
+#endif
+
+ void dumpInterferenceGraphInDot(PrintStream& out)
+ {
+ out.print("graph InterferenceGraph { \n");
+
+ HashSet<Tmp> tmpsWithInterferences;
+ for (const auto& edge : m_interferenceEdges) {
+ tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.first()));
+ tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.second()));
+ }
+
+ for (const auto& tmp : tmpsWithInterferences)
+ out.print(" ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
+
+ for (const auto& edge : m_interferenceEdges)
+ out.print(" ", edge.first(), " -- ", edge.second(), ";\n");
+ out.print("}\n");
+ }
+
+ void dumpWorkLists(PrintStream& out)
+ {
+ out.print("Simplify work list:\n");
+ for (unsigned tmpIndex : m_simplifyWorklist)
+ out.print(" ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
+ out.printf("Moves work list is empty? %d\n", m_worklistMoves.isEmpty());
+ out.print("Freeze work list:\n");
+ for (unsigned tmpIndex : m_freezeWorklist)
+ out.print(" ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
+ out.print("Spill work list:\n");
+ for (unsigned tmpIndex : m_spillWorklist)
+ out.print(" ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
+ }
+
+ using AbstractColoringAllocator<unsigned>::addEdge;
+ using AbstractColoringAllocator<unsigned>::getAlias;
+
+ Code& m_code;
+ // FIXME: spilling should not type specific. It is only a side effect of using UseCounts.
+ const UseCounts<Tmp>& m_useCounts;
+ const HashSet<unsigned>& m_unspillableTmps;
+};
+
+class IteratedRegisterCoalescing {
+public:
+ IteratedRegisterCoalescing(Code& code)
+ : m_code(code)
+ , m_useCounts(code)
+ {
+ }
+
+ void run()
+ {
+ iteratedRegisterCoalescingOnType<Arg::GP>();
+ iteratedRegisterCoalescingOnType<Arg::FP>();
+
+ if (reportStats)
+ dataLog("Num iterations = ", m_numIterations, "\n");
+ }
+
+private:
+ template<Arg::Type type>
+ void iteratedRegisterCoalescingOnType()
+ {
+ HashSet<unsigned> unspillableTmps;
+ while (true) {
+ ++m_numIterations;
+ ColoringAllocator<type> allocator(m_code, m_useCounts, unspillableTmps);
+ if (!allocator.requiresSpilling()) {
+ assignRegistersToTmp(allocator);
+ return;
+ }
+ addSpillAndFill<type>(allocator, unspillableTmps);
+ }
+ }
+
+ template<Arg::Type type>
+ void assignRegistersToTmp(const ColoringAllocator<type>& allocator)
+ {
+ for (BasicBlock* block : m_code) {
+ // Give Tmp a valid register.
+ for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+ Inst& inst = block->at(instIndex);
+ inst.forEachTmpFast([&] (Tmp& tmp) {
+ if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
+ return;
+
+ Tmp aliasTmp = allocator.getAlias(tmp);
+ Tmp assignedTmp;
+ if (aliasTmp.isReg())
+ assignedTmp = Tmp(aliasTmp.reg());
+ else {
+ auto reg = allocator.allocatedReg(aliasTmp);
+ ASSERT(reg);
+ assignedTmp = Tmp(reg);
+ }
+ ASSERT(assignedTmp.isReg());
+ tmp = assignedTmp;
+ });
+ }
+
+ // Remove all the useless moves we created in this block.
+ block->insts().removeAllMatching([&] (const Inst& inst) {
+ return allocator.isUselessMove(inst);
+ });
+ }
+ }
+
+ template<Arg::Type type>
+ void addSpillAndFill(const ColoringAllocator<type>& allocator, HashSet<unsigned>& unspillableTmps)
+ {
+ HashMap<Tmp, StackSlot*> stackSlots;
+ for (Tmp tmp : allocator.spilledTmps()) {
+ // All the spilled values become unspillable.
+ unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
+
+ // Allocate stack slot for each spilled value.
+ bool isNewTmp = stackSlots.add(tmp, m_code.addStackSlot(8, StackSlotKind::Anonymous)).isNewEntry;
+ ASSERT_UNUSED(isNewTmp, isNewTmp);
+ }
+
+ // Rewrite the program to get rid of the spilled Tmp.
+ InsertionSet insertionSet(m_code);
+ for (BasicBlock* block : m_code) {
+ bool hasAliasedTmps = false;
+
+ for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
+ Inst& inst = block->at(instIndex);
+
+ // Try to replace the register use by memory use when possible.
+ for (unsigned i = 0; i < inst.args.size(); ++i) {
+ Arg& arg = inst.args[i];
+ if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
+ auto stackSlotEntry = stackSlots.find(arg.tmp());
+ if (stackSlotEntry != stackSlots.end() && inst.admitsStack(i))
+ arg = Arg::stack(stackSlotEntry->value);
+ }
+ }
+
+ // For every other case, add Load/Store as needed.
+ inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Arg::Type argType) {
+ if (tmp.isReg() || argType != type)
+ return;
+
+ auto stackSlotEntry = stackSlots.find(tmp);
+ if (stackSlotEntry == stackSlots.end()) {
+ Tmp alias = allocator.getAliasWhenSpilling(tmp);
+ if (alias != tmp) {
+ tmp = alias;
+ hasAliasedTmps = true;
+ }
+ return;
+ }
+
+ Arg arg = Arg::stack(stackSlotEntry->value);
+ Opcode move = type == Arg::GP ? Move : MoveDouble;
+
+ if (Arg::isAnyUse(role)) {
+ Tmp newTmp = m_code.newTmp(type);
+ insertionSet.insert(instIndex, move, inst.origin, arg, newTmp);
+ tmp = newTmp;
+
+ // Any new Fill() should never be spilled.
+ unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
+ }
+ if (Arg::isDef(role))
+ insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
+ });
+ }
+ insertionSet.execute(block);
+
+ if (hasAliasedTmps) {
+ block->insts().removeAllMatching([&] (const Inst& inst) {
+ return allocator.isUselessMove(inst);
+ });
+ }
+ }
+ }
+
+ Code& m_code;
+ UseCounts<Tmp> m_useCounts;
+ unsigned m_numIterations { 0 };
+};
+
</ins><span class="cx"> } // anonymous namespace
</span><span class="cx">
</span><span class="cx"> void iteratedRegisterCoalescing(Code& code)
</span><span class="cx"> {
</span><span class="cx"> PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
</span><span class="cx">
</span><del>- unsigned numIterations = 0;
-
- UseCounts<Tmp> useCounts(code);
- iteratedRegisterCoalescingOnType<Arg::GP>(code, useCounts, numIterations);
- iteratedRegisterCoalescingOnType<Arg::FP>(code, useCounts, numIterations);
-
- if (reportStats)
- dataLog("Num iterations = ", numIterations, "\n");
</del><ins>+ IteratedRegisterCoalescing iteratedRegisterCoalescing(code);
+ iteratedRegisterCoalescing.run();
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } } } // namespace JSC::B3::Air
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirTmpInlinesh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h (194315 => 194316)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h 2015-12-19 19:01:50 UTC (rev 194315)
+++ trunk/Source/JavaScriptCore/b3/air/AirTmpInlines.h 2015-12-19 21:04:55 UTC (rev 194316)
</span><span class="lines">@@ -57,6 +57,11 @@
</span><span class="cx"> return absoluteIndex(Tmp::gpTmpForIndex(tmpIndex));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ static unsigned lastMachineRegisterIndex()
+ {
+ return absoluteIndex(Tmp(MacroAssembler::lastRegister()));
+ }
+
</ins><span class="cx"> static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
</span><span class="cx"> {
</span><span class="cx"> return Tmp::tmpForInternalValue(tmpIndex);
</span><span class="lines">@@ -77,6 +82,11 @@
</span><span class="cx"> return absoluteIndex(Tmp::fpTmpForIndex(tmpIndex));
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ static unsigned lastMachineRegisterIndex()
+ {
+ return absoluteIndex(Tmp(MacroAssembler::lastFPRegister()));
+ }
+
</ins><span class="cx"> static Tmp tmpFromAbsoluteIndex(unsigned tmpIndex)
</span><span class="cx"> {
</span><span class="cx"> return Tmp::tmpForInternalValue(-tmpIndex);
</span></span></pre>
</div>
</div>
</body>
</html>