<!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>[192492] 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/192492">192492</a></dd>
<dt>Author</dt> <dd>benjamin@webkit.org</dd>
<dt>Date</dt> <dd>2015-11-16 15:47:10 -0800 (Mon, 16 Nov 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>[JSC] Speed up the coalescing-related operation of the iterated register allocator
https://bugs.webkit.org/show_bug.cgi?id=151290
Patch by Benjamin Poulain <bpoulain@apple.com> on 2015-11-16
Reviewed by Geoffrey Garen.
One step closer to removing the Hash structures:
For the coalescing operation, we need to keep track of Move instructions. We do not strictly
need those to be the Air Move, just any abstract operation that copy a Tmp into another Tmp.
In this patch, I exploit that to remove the Hash structure related to the Inst. Instead of
using the Move Inst, we just keep track of the Use() and Def() of the instructions.
Those are added in the global list m_coalescingCandidates and the index in that list represent
the move for the remaining of the algorithm.
With Moves transformed into dense indices, we can start using arrays to make fast sets.
The m_activeMoves Set is easy since we only need simple add/remove/contains. It is transformed
into a BitVector.
The bit vector is always fully allocated to allow for quick uniform access. The assumtion is that
activeMoves will contains a few values for non trivial cases.
The worklist m_worklistMoves is more complicated. I want it to be ordered to coalesce moves starting
at the top of blocks. Having a fast remove() operation is also useful for mass coalescing.
It also needs Set operations, especially a fast contains().
For m_worklistMoves, I created a new structure: OrderedMoveSet.
It contains a list of ordered values, and a map of each value to its position in the list.
This resembles Briggs' Sparse Set but it is not exactly the same. When removing a value,
I set a special marker in the map (UINT_MAX). The reason is that I want contains() to be fast
instead of remove(). The marker in the map allows contains() with a single memory operation instead of two.
* b3/air/AirIteratedRegisterCoalescing.cpp:
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::addMove):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::isEmpty):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::contains):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::takeMove):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::takeLastMove):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::returnMove):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::clear):
(JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors): Deleted.</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 (192491 => 192492)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-11-16 23:22:16 UTC (rev 192491)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-11-16 23:47:10 UTC (rev 192492)
</span><span class="lines">@@ -1,3 +1,57 @@
</span><ins>+2015-11-16 Benjamin Poulain <bpoulain@apple.com>
+
+ [JSC] Speed up the coalescing-related operation of the iterated register allocator
+ https://bugs.webkit.org/show_bug.cgi?id=151290
+
+ Reviewed by Geoffrey Garen.
+
+ One step closer to removing the Hash structures:
+
+ For the coalescing operation, we need to keep track of Move instructions. We do not strictly
+ need those to be the Air Move, just any abstract operation that copy a Tmp into another Tmp.
+
+ In this patch, I exploit that to remove the Hash structure related to the Inst. Instead of
+ using the Move Inst, we just keep track of the Use() and Def() of the instructions.
+ Those are added in the global list m_coalescingCandidates and the index in that list represent
+ the move for the remaining of the algorithm.
+
+ With Moves transformed into dense indices, we can start using arrays to make fast sets.
+
+ The m_activeMoves Set is easy since we only need simple add/remove/contains. It is transformed
+ into a BitVector.
+ The bit vector is always fully allocated to allow for quick uniform access. The assumtion is that
+ activeMoves will contains a few values for non trivial cases.
+
+ The worklist m_worklistMoves is more complicated. I want it to be ordered to coalesce moves starting
+ at the top of blocks. Having a fast remove() operation is also useful for mass coalescing.
+ It also needs Set operations, especially a fast contains().
+
+ For m_worklistMoves, I created a new structure: OrderedMoveSet.
+ It contains a list of ordered values, and a map of each value to its position in the list.
+
+ This resembles Briggs' Sparse Set but it is not exactly the same. When removing a value,
+ I set a special marker in the map (UINT_MAX). The reason is that I want contains() to be fast
+ instead of remove(). The marker in the map allows contains() with a single memory operation instead of two.
+
+ * b3/air/AirIteratedRegisterCoalescing.cpp:
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::build):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::allocate):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::forEachNodeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::isMoveRelated):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::enableMovesOnValue):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::coalesce):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::combine):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::freezeMoves):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::dumpWorkLists):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::addMove):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::isEmpty):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::contains):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::takeMove):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::takeLastMove):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::returnMove):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::OrderedMoveSet::clear):
+ (JSC::B3::Air::IteratedRegisterCoalescingAllocator::assignColors): Deleted.
+
</ins><span class="cx"> 2015-11-16 Saam barati <sbarati@apple.com>
</span><span class="cx">
</span><span class="cx"> DFGEdge's dump method should print "Untyped:" for untyped uses.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreb3airAirIteratedRegisterCoalescingcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp (192491 => 192492)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-16 23:22:16 UTC (rev 192491)
+++ trunk/Source/JavaScriptCore/b3/air/AirIteratedRegisterCoalescing.cpp 2015-11-16 23:47:10 UTC (rev 192492)
</span><span class="lines">@@ -161,12 +161,6 @@
</span><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> if (MoveInstHelper<type>::mayBeCoalescable(inst)) {
</span><del>- for (const Arg& arg : inst.args) {
- HashSet<Inst*>& list = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(arg.tmp())];
- list.add(&inst);
- }
- m_worklistMoves.add(&inst);
-
</del><span class="cx"> // We do not want the Use() of this move to interfere with the Def(), even if it is live
</span><span class="cx"> // after the Move. If we were to add the interference edge, it would be impossible to
</span><span class="cx"> // coalesce the Move even if the two Tmp never interfere anywhere.
</span><span class="lines">@@ -183,6 +177,20 @@
</span><span class="cx"> ASSERT(defTmp);
</span><span class="cx"> ASSERT(useTmp);
</span><span class="cx">
</span><ins>+ 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[AbsoluteTmpHelper<type>::absoluteIndex(arg.tmp())];
+ list.add(nextMoveIndex);
+ }
+
</ins><span class="cx"> for (const Tmp& liveTmp : localCalc.live()) {
</span><span class="cx"> if (liveTmp != useTmp && liveTmp.isGP() == (type == Arg::GP))
</span><span class="cx"> addEdge(defTmp, liveTmp);
</span><span class="lines">@@ -193,6 +201,8 @@
</span><span class="cx">
</span><span class="cx"> void allocate()
</span><span class="cx"> {
</span><ins>+ ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
+
</ins><span class="cx"> makeWorkList();
</span><span class="cx">
</span><span class="cx"> if (debug) {
</span><span class="lines">@@ -367,16 +377,16 @@
</span><span class="cx"> template<typename Function>
</span><span class="cx"> void forEachNodeMoves(Tmp tmp, Function function)
</span><span class="cx"> {
</span><del>- for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.contains(inst) || m_worklistMoves.contains(inst))
- function(*inst);
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
+ function(moveIndex);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool isMoveRelated(Tmp tmp)
</span><span class="cx"> {
</span><del>- for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.contains(inst) || m_worklistMoves.contains(inst))
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
</ins><span class="cx"> return true;
</span><span class="cx"> }
</span><span class="cx"> return false;
</span><span class="lines">@@ -384,9 +394,9 @@
</span><span class="cx">
</span><span class="cx"> void enableMovesOnValue(Tmp tmp)
</span><span class="cx"> {
</span><del>- for (Inst* inst : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
- if (m_activeMoves.remove(inst))
- m_worklistMoves.add(inst);
</del><ins>+ for (unsigned moveIndex : m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(tmp)]) {
+ if (m_activeMoves.quickClear(moveIndex))
+ m_worklistMoves.returnMove(moveIndex);
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -401,19 +411,18 @@
</span><span class="cx">
</span><span class="cx"> void coalesce()
</span><span class="cx"> {
</span><del>- Inst* moveInst = m_worklistMoves.takeLast();
- ASSERT(moveInst->args.size() == 2);
-
- Tmp u = moveInst->args[0].tmp();
</del><ins>+ unsigned moveIndex = m_worklistMoves.takeLastMove();
+ const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
+ Tmp u = moveOperands.src;
</ins><span class="cx"> u = getAlias(u);
</span><del>- Tmp v = moveInst->args[1].tmp();
</del><ins>+ Tmp v = moveOperands.dst;
</ins><span class="cx"> v = getAlias(v);
</span><span class="cx">
</span><span class="cx"> if (v.isReg())
</span><span class="cx"> std::swap(u, v);
</span><span class="cx">
</span><span class="cx"> if (traceDebug)
</span><del>- dataLog("Coalescing ", *moveInst, " u = ", u, " v = ", v, "\n");
</del><ins>+ dataLog("Coalescing move at index", moveIndex, " u = ", u, " v = ", v, "\n");
</ins><span class="cx">
</span><span class="cx"> if (u == v) {
</span><span class="cx"> addWorkList(u);
</span><span class="lines">@@ -433,7 +442,7 @@
</span><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Safe Coalescing\n");
</span><span class="cx"> } else {
</span><del>- m_activeMoves.add(moveInst);
</del><ins>+ m_activeMoves.quickSet(moveIndex);
</ins><span class="cx">
</span><span class="cx"> if (traceDebug)
</span><span class="cx"> dataLog(" Failed coalescing, added to active moves.\n");
</span><span class="lines">@@ -527,7 +536,7 @@
</span><span class="cx"> ASSERT(!m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)]);
</span><span class="cx"> m_coalescedTmps[AbsoluteTmpHelper<type>::absoluteIndex(v)] = u;
</span><span class="cx">
</span><del>- HashSet<Inst*>& vMoves = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
</del><ins>+ auto& vMoves = m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(v)];
</ins><span class="cx"> m_moveList[AbsoluteTmpHelper<type>::absoluteIndex(u)].add(vMoves.begin(), vMoves.end());
</span><span class="cx">
</span><span class="cx"> forEachAdjacent(v, [this, u] (Tmp adjacentTmp) {
</span><span class="lines">@@ -548,11 +557,12 @@
</span><span class="cx">
</span><span class="cx"> void freezeMoves(Tmp tmp)
</span><span class="cx"> {
</span><del>- forEachNodeMoves(tmp, [this, tmp] (Inst& inst) {
- if (!m_activeMoves.remove(&inst))
- m_worklistMoves.remove(&inst);
</del><ins>+ forEachNodeMoves(tmp, [this, tmp] (unsigned moveIndex) {
+ if (!m_activeMoves.quickClear(moveIndex))
+ m_worklistMoves.takeMove(moveIndex);
</ins><span class="cx">
</span><del>- Tmp otherTmp = inst.args[0].tmp() != tmp ? inst.args[0].tmp() : inst.args[1].tmp();
</del><ins>+ const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
+ Tmp otherTmp = moveOperands.src != tmp ? moveOperands.src : moveOperands.dst;
</ins><span class="cx"> if (m_degrees[AbsoluteTmpHelper<type>::absoluteIndex(otherTmp)] < m_numberOfRegisters && !isMoveRelated(otherTmp)) {
</span><span class="cx"> m_freezeWorklist.remove(otherTmp);
</span><span class="cx"> m_simplifyWorklist.append(otherTmp);
</span><span class="lines">@@ -597,7 +607,6 @@
</span><span class="cx"> m_degrees.clear();
</span><span class="cx"> m_moveList.clear();
</span><span class="cx"> m_worklistMoves.clear();
</span><del>- m_activeMoves.clear();
</del><span class="cx"> m_simplifyWorklist.clear();
</span><span class="cx"> m_spillWorklist.clear();
</span><span class="cx"> m_freezeWorklist.clear();
</span><span class="lines">@@ -667,9 +676,7 @@
</span><span class="cx"> out.print("Simplify work list:\n");
</span><span class="cx"> for (Tmp tmp : m_simplifyWorklist)
</span><span class="cx"> out.print(" ", tmp, "\n");
</span><del>- out.print("Moves work list:\n");
- for (Inst* inst : m_worklistMoves)
- out.print(" ", *inst, "\n");
</del><ins>+ out.printf("Moves work list is empty? %d\n", m_worklistMoves.isEmpty());
</ins><span class="cx"> out.print("Freeze work list:\n");
</span><span class="cx"> for (Tmp tmp : m_freezeWorklist)
</span><span class="cx"> out.print(" ", tmp, "\n");
</span><span class="lines">@@ -749,8 +756,16 @@
</span><span class="cx"> Vector<Vector<Tmp, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
</span><span class="cx"> Vector<unsigned, 0, UnsafeVectorOverflow> m_degrees;
</span><span class="cx">
</span><ins>+ // Instead of keeping track of the move instructions, we just keep their operands around and use the index
+ // in the vector as the "identifier" for the move.
+ struct MoveOperands {
+ Tmp src;
+ Tmp dst;
+ };
+ Vector<MoveOperands, 0, UnsafeVectorOverflow> m_coalescingCandidates;
+
</ins><span class="cx"> // List of every move instruction associated with a Tmp.
</span><del>- Vector<HashSet<Inst*>> m_moveList;
</del><ins>+ Vector<HashSet<unsigned, DefaultHash<unsigned>::Hash, WTF::UnsignedWithZeroKeyHashTraits<unsigned>>> 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">@@ -763,11 +778,84 @@
</span><span class="cx"> BitVector m_isOnSelectStack;
</span><span class="cx"> Vector<Tmp> m_selectStack;
</span><span class="cx">
</span><ins>+ struct OrderedMoveSet {
+ unsigned addMove()
+ {
+ unsigned nextIndex = m_moveList.size();
+ m_moveList.append(nextIndex);
+ m_positionInMoveList.append(nextIndex);
+ return nextIndex;
+ }
+
+ bool isEmpty() const
+ {
+ return m_moveList.isEmpty();
+ }
+
+ bool contains(unsigned index)
+ {
+ return m_positionInMoveList[index] != WTF::notFound;
+ }
+
+ void takeMove(unsigned moveIndex)
+ {
+ unsigned positionInMoveList = m_positionInMoveList[moveIndex];
+ if (positionInMoveList == WTF::notFound)
+ return;
+
+ ASSERT(m_moveList[positionInMoveList] == moveIndex);
+ unsigned lastIndex = m_moveList.last();
+ m_positionInMoveList[lastIndex] = positionInMoveList;
+ m_moveList[positionInMoveList] = lastIndex;
+ m_moveList.removeLast();
+
+ m_positionInMoveList[moveIndex] = WTF::notFound;
+
+ ASSERT(!contains(moveIndex));
+ }
+
+ unsigned takeLastMove()
+ {
+ ASSERT(!isEmpty());
+
+ unsigned lastIndex = m_moveList.takeLast();
+ ASSERT(m_positionInMoveList[lastIndex] == m_moveList.size());
+ m_positionInMoveList[lastIndex] = WTF::notFound;
+
+ ASSERT(!contains(lastIndex));
+ return lastIndex;
+ }
+
+ void returnMove(unsigned index)
+ {
+ // This assertion is a bit strict but that is how the move list should be used. The only kind of moves that can
+ // return to the list are the ones that we previously failed to coalesce with the conservative heuristics.
+ // Values should not be added back if they were never taken out when attempting coalescing.
+ ASSERT(!contains(index));
+
+ unsigned position = m_moveList.size();
+ m_moveList.append(index);
+ m_positionInMoveList[index] = position;
+
+ ASSERT(contains(index));
+ }
+
+ void clear()
+ {
+ m_positionInMoveList.clear();
+ m_moveList.clear();
+ }
+
+ private:
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_positionInMoveList;
+ Vector<unsigned, 0, UnsafeVectorOverflow> m_moveList;
+ };
+
</ins><span class="cx"> // Work lists.
</span><span class="cx"> // Set of "move" enabled for possible coalescing.
</span><del>- ListHashSet<Inst*> m_worklistMoves;
</del><ins>+ OrderedMoveSet m_worklistMoves;
</ins><span class="cx"> // Set of "move" not yet ready for coalescing.
</span><del>- HashSet<Inst*> m_activeMoves;
</del><ins>+ BitVector m_activeMoves;
</ins><span class="cx"> // Low-degree, non-Move related.
</span><span class="cx"> Vector<Tmp> m_simplifyWorklist;
</span><span class="cx"> // High-degree Tmp.
</span></span></pre>
</div>
</div>
</body>
</html>