3b6886fed4d06ddacfb868d4c23485edc6722bb8
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirIteratedRegisterCoalescing.cpp
1 /*
2  * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "AirIteratedRegisterCoalescing.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirCode.h"
32 #include "AirFixSpillSlotZDef.h"
33 #include "AirInsertionSet.h"
34 #include "AirInstInlines.h"
35 #include "AirLiveness.h"
36 #include "AirPhaseScope.h"
37 #include "AirRegisterPriority.h"
38 #include "AirTmpInlines.h"
39 #include "AirTmpWidth.h"
40 #include "AirUseCounts.h"
41 #include <wtf/ListDump.h>
42 #include <wtf/ListHashSet.h>
43
44 namespace JSC { namespace B3 { namespace Air {
45
46 namespace {
47
48 bool debug = false;
49 bool traceDebug = false;
50 bool reportStats = false;
51
52 // The AbstractColoringAllocator defines all the code that is independant
53 // from the type or register and can be shared when allocating registers.
54 template<typename IndexType>
55 class AbstractColoringAllocator {
56 public:
57     AbstractColoringAllocator(const Vector<Reg>& regsInPriorityOrder, IndexType lastPrecoloredRegisterIndex, unsigned tmpArraySize)
58         : m_regsInPriorityOrder(regsInPriorityOrder)
59         , m_lastPrecoloredRegisterIndex(lastPrecoloredRegisterIndex)
60     {
61         initializeDegrees(tmpArraySize);
62
63         m_adjacencyList.resize(tmpArraySize);
64         m_moveList.resize(tmpArraySize);
65         m_coalescedTmps.fill(0, tmpArraySize);
66         m_isOnSelectStack.ensureSize(tmpArraySize);
67     }
68
69 protected:
70     IndexType getAlias(IndexType tmpIndex) const
71     {
72         IndexType alias = tmpIndex;
73         while (IndexType nextAlias = m_coalescedTmps[alias])
74             alias = nextAlias;
75         return alias;
76     }
77
78     void addEdge(IndexType a, IndexType b)
79     {
80         if (a == b)
81             return;
82         addEdgeDistinct(a, b);
83     }
84
85     void makeWorkList()
86     {
87         IndexType firstNonRegIndex = m_lastPrecoloredRegisterIndex + 1;
88         for (IndexType i = firstNonRegIndex; i < m_degrees.size(); ++i) {
89             unsigned degree = m_degrees[i];
90             if (!degree)
91                 continue;
92
93             if (degree >= m_regsInPriorityOrder.size())
94                 m_spillWorklist.add(i);
95             else if (!m_moveList[i].isEmpty())
96                 m_freezeWorklist.add(i);
97             else
98                 m_simplifyWorklist.append(i);
99         }
100     }
101
102     // Low-degree vertex can always be colored: just pick any of the color taken by any
103     // other adjacent verices.
104     // The "Simplify" phase takes a low-degree out of the interference graph to simplify it.
105     void simplify()
106     {
107         IndexType lastIndex = m_simplifyWorklist.takeLast();
108
109         ASSERT(!m_selectStack.contains(lastIndex));
110         ASSERT(!m_isOnSelectStack.get(lastIndex));
111         m_selectStack.append(lastIndex);
112         m_isOnSelectStack.quickSet(lastIndex);
113
114         forEachAdjacent(lastIndex, [this](IndexType adjacentTmpIndex) {
115             decrementDegree(adjacentTmpIndex);
116         });
117     }
118
119     void freeze()
120     {
121         IndexType victimIndex = m_freezeWorklist.takeAny();
122         ASSERT_WITH_MESSAGE(getAlias(victimIndex) == victimIndex, "coalesce() should not leave aliased Tmp in the worklist.");
123         m_simplifyWorklist.append(victimIndex);
124         freezeMoves(victimIndex);
125     }
126
127     void freezeMoves(IndexType tmpIndex)
128     {
129         forEachNodeMoves(tmpIndex, [this, tmpIndex] (IndexType moveIndex) {
130             if (!m_activeMoves.quickClear(moveIndex))
131                 m_worklistMoves.takeMove(moveIndex);
132
133             const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
134             IndexType srcTmpIndex = moveOperands.srcIndex;
135             IndexType dstTmpIndex = moveOperands.dstIndex;
136
137             IndexType originalOtherTmp = srcTmpIndex != tmpIndex ? srcTmpIndex : dstTmpIndex;
138             IndexType otherTmpIndex = getAlias(originalOtherTmp);
139             if (m_degrees[otherTmpIndex] < m_regsInPriorityOrder.size() && !isMoveRelated(otherTmpIndex)) {
140                 if (m_freezeWorklist.remove(otherTmpIndex))
141                     m_simplifyWorklist.append(otherTmpIndex);
142             }
143         });
144     }
145
146     void coalesce()
147     {
148         unsigned moveIndex = m_worklistMoves.takeLastMove();
149         const MoveOperands& moveOperands = m_coalescingCandidates[moveIndex];
150         IndexType u = getAlias(moveOperands.srcIndex);
151         IndexType v = getAlias(moveOperands.dstIndex);
152
153         if (isPrecolored(v))
154             std::swap(u, v);
155
156         if (traceDebug)
157             dataLog("Coalescing move at index", moveIndex, " u = ", u, " v = ", v, "\n");
158
159         if (u == v) {
160             addWorkList(u);
161
162             if (traceDebug)
163                 dataLog("    Coalesced\n");
164         } else if (isPrecolored(v) || m_interferenceEdges.contains(InterferenceEdge(u, v))) {
165             addWorkList(u);
166             addWorkList(v);
167
168             if (traceDebug)
169                 dataLog("    Constrained\n");
170         } else if (canBeSafelyCoalesced(u, v)) {
171             combine(u, v);
172             addWorkList(u);
173             m_hasCoalescedNonTrivialMove = true;
174
175             if (traceDebug)
176                 dataLog("    Safe Coalescing\n");
177         } else {
178             m_activeMoves.quickSet(moveIndex);
179
180             if (traceDebug)
181                 dataLog("    Failed coalescing, added to active moves.\n");
182         }
183     }
184
185     void assignColors()
186     {
187         ASSERT(m_simplifyWorklist.isEmpty());
188         ASSERT(m_worklistMoves.isEmpty());
189         ASSERT(m_freezeWorklist.isEmpty());
190         ASSERT(m_spillWorklist.isEmpty());
191
192         // Reclaim as much memory as possible.
193         m_interferenceEdges.clear();
194         m_degrees.clear();
195         m_moveList.clear();
196         m_worklistMoves.clear();
197         m_simplifyWorklist.clear();
198         m_spillWorklist.clear();
199         m_freezeWorklist.clear();
200
201         // Try to color the Tmp on the stack.
202         m_coloredTmp.resize(m_adjacencyList.size());
203
204         while (!m_selectStack.isEmpty()) {
205             unsigned tmpIndex = m_selectStack.takeLast();
206             ASSERT(!isPrecolored(tmpIndex));
207             ASSERT(!m_coloredTmp[tmpIndex]);
208
209             RegisterSet coloredRegisters;
210             for (IndexType adjacentTmpIndex : m_adjacencyList[tmpIndex]) {
211                 IndexType aliasTmpIndex = getAlias(adjacentTmpIndex);
212                 Reg reg = m_coloredTmp[aliasTmpIndex];
213
214                 ASSERT(!isPrecolored(aliasTmpIndex) || (isPrecolored(aliasTmpIndex) && reg));
215
216                 if (reg)
217                     coloredRegisters.set(reg);
218             }
219
220             bool colorAssigned = false;
221             for (Reg reg : m_regsInPriorityOrder) {
222                 if (!coloredRegisters.get(reg)) {
223                     m_coloredTmp[tmpIndex] = reg;
224                     colorAssigned = true;
225                     break;
226                 }
227             }
228
229             if (!colorAssigned)
230                 m_spilledTmps.append(tmpIndex);
231         }
232         m_selectStack.clear();
233
234         if (m_spilledTmps.isEmpty())
235             m_coalescedTmpsAtSpill.clear();
236         else
237             m_coloredTmp.clear();
238     }
239
240 private:
241     void initializeDegrees(unsigned tmpArraySize)
242     {
243         m_degrees.resize(tmpArraySize);
244
245         // All precolored registers have  an "infinite" degree.
246         unsigned firstNonRegIndex = m_lastPrecoloredRegisterIndex + 1;
247         for (unsigned i = 0; i < firstNonRegIndex; ++i)
248             m_degrees[i] = std::numeric_limits<unsigned>::max();
249
250         memset(m_degrees.data() + firstNonRegIndex, 0, (tmpArraySize - firstNonRegIndex) * sizeof(unsigned));
251     }
252
253     void addEdgeDistinct(IndexType a, IndexType b)
254     {
255         ASSERT(a != b);
256         if (m_interferenceEdges.add(InterferenceEdge(a, b)).isNewEntry) {
257             if (!isPrecolored(a)) {
258                 ASSERT(!m_adjacencyList[a].contains(b));
259                 m_adjacencyList[a].append(b);
260                 m_degrees[a]++;
261             }
262
263             if (!isPrecolored(b)) {
264                 ASSERT(!m_adjacencyList[b].contains(a));
265                 m_adjacencyList[b].append(a);
266                 m_degrees[b]++;
267             }
268         }
269     }
270
271     void decrementDegree(IndexType tmpIndex)
272     {
273         ASSERT(m_degrees[tmpIndex]);
274
275         unsigned oldDegree = m_degrees[tmpIndex]--;
276         if (oldDegree == m_regsInPriorityOrder.size()) {
277             enableMovesOnValueAndAdjacents(tmpIndex);
278             m_spillWorklist.remove(tmpIndex);
279             if (isMoveRelated(tmpIndex))
280                 m_freezeWorklist.add(tmpIndex);
281             else
282                 m_simplifyWorklist.append(tmpIndex);
283         }
284     }
285
286     bool isMoveRelated(IndexType tmpIndex)
287     {
288         for (unsigned moveIndex : m_moveList[tmpIndex]) {
289             if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
290                 return true;
291         }
292         return false;
293     }
294
295     template<typename Function>
296     void forEachAdjacent(IndexType tmpIndex, Function function)
297     {
298         for (IndexType adjacentTmpIndex : m_adjacencyList[tmpIndex]) {
299             if (!hasBeenSimplified(adjacentTmpIndex))
300                 function(adjacentTmpIndex);
301         }
302     }
303
304     bool hasBeenSimplified(IndexType tmpIndex)
305     {
306         return m_isOnSelectStack.quickGet(tmpIndex) || !!m_coalescedTmps[tmpIndex];
307     }
308
309     template<typename Function>
310     void forEachNodeMoves(IndexType tmpIndex, Function function)
311     {
312         for (unsigned moveIndex : m_moveList[tmpIndex]) {
313             if (m_activeMoves.quickGet(moveIndex) || m_worklistMoves.contains(moveIndex))
314                 function(moveIndex);
315         }
316     }
317
318     void enableMovesOnValue(IndexType tmpIndex)
319     {
320         for (unsigned moveIndex : m_moveList[tmpIndex]) {
321             if (m_activeMoves.quickClear(moveIndex))
322                 m_worklistMoves.returnMove(moveIndex);
323         }
324     }
325
326     void enableMovesOnValueAndAdjacents(IndexType tmpIndex)
327     {
328         enableMovesOnValue(tmpIndex);
329
330         forEachAdjacent(tmpIndex, [this] (IndexType adjacentTmpIndex) {
331             enableMovesOnValue(adjacentTmpIndex);
332         });
333     }
334
335     bool isPrecolored(IndexType tmpIndex)
336     {
337         return tmpIndex <= m_lastPrecoloredRegisterIndex;
338     }
339
340     void addWorkList(IndexType tmpIndex)
341     {
342         if (!isPrecolored(tmpIndex) && m_degrees[tmpIndex] < m_regsInPriorityOrder.size() && !isMoveRelated(tmpIndex)) {
343             m_freezeWorklist.remove(tmpIndex);
344             m_simplifyWorklist.append(tmpIndex);
345         }
346     }
347
348     void combine(IndexType u, IndexType v)
349     {
350         if (!m_freezeWorklist.remove(v))
351             m_spillWorklist.remove(v);
352
353         ASSERT(!m_coalescedTmps[v]);
354         m_coalescedTmps[v] = u;
355
356         auto& vMoves = m_moveList[v];
357         m_moveList[u].add(vMoves.begin(), vMoves.end());
358
359         forEachAdjacent(v, [this, u] (IndexType adjacentTmpIndex) {
360             addEdgeDistinct(adjacentTmpIndex, u);
361             decrementDegree(adjacentTmpIndex);
362         });
363
364         if (m_degrees[u] >= m_regsInPriorityOrder.size() && m_freezeWorklist.remove(u))
365             m_spillWorklist.add(u);
366     }
367
368     bool canBeSafelyCoalesced(IndexType u, IndexType v)
369     {
370         ASSERT(!isPrecolored(v));
371         if (isPrecolored(u))
372             return precoloredCoalescingHeuristic(u, v);
373         return conservativeHeuristic(u, v);
374     }
375
376     bool conservativeHeuristic(IndexType u, IndexType v)
377     {
378         // This is using the Briggs' conservative coalescing rule:
379         // If the number of combined adjacent node with a degree >= K is less than K,
380         // it is safe to combine the two nodes. The reason is that we know that if the graph
381         // is colorable, we have fewer than K adjacents with high order and there is a color
382         // for the current node.
383         ASSERT(u != v);
384         ASSERT(!isPrecolored(u));
385         ASSERT(!isPrecolored(v));
386
387         const auto& adjacentsOfU = m_adjacencyList[u];
388         const auto& adjacentsOfV = m_adjacencyList[v];
389
390         if (adjacentsOfU.size() + adjacentsOfV.size() < m_regsInPriorityOrder.size()) {
391             // Shortcut: if the total number of adjacents is less than the number of register, the condition is always met.
392             return true;
393         }
394
395         HashSet<IndexType> highOrderAdjacents;
396
397         for (IndexType adjacentTmpIndex : adjacentsOfU) {
398             ASSERT(adjacentTmpIndex != v);
399             ASSERT(adjacentTmpIndex != u);
400             if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()) {
401                 auto addResult = highOrderAdjacents.add(adjacentTmpIndex);
402                 if (addResult.isNewEntry && highOrderAdjacents.size() >= m_regsInPriorityOrder.size())
403                     return false;
404             }
405         }
406         for (IndexType adjacentTmpIndex : adjacentsOfV) {
407             ASSERT(adjacentTmpIndex != u);
408             ASSERT(adjacentTmpIndex != v);
409             if (!hasBeenSimplified(adjacentTmpIndex) && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()) {
410                 auto addResult = highOrderAdjacents.add(adjacentTmpIndex);
411                 if (addResult.isNewEntry && highOrderAdjacents.size() >= m_regsInPriorityOrder.size())
412                     return false;
413             }
414         }
415
416         ASSERT(highOrderAdjacents.size() < m_regsInPriorityOrder.size());
417         return true;
418     }
419
420     bool precoloredCoalescingHeuristic(IndexType u, IndexType v)
421     {
422         ASSERT(isPrecolored(u));
423         ASSERT(!isPrecolored(v));
424
425         // If any adjacent of the non-colored node is not an adjacent of the colored node AND has a degree >= K
426         // there is a risk that this node needs to have the same color as our precolored node. If we coalesce such
427         // move, we may create an uncolorable graph.
428         const auto& adjacentsOfV = m_adjacencyList[v];
429         for (unsigned adjacentTmpIndex : adjacentsOfV) {
430             if (!isPrecolored(adjacentTmpIndex)
431                 && !hasBeenSimplified(adjacentTmpIndex)
432                 && m_degrees[adjacentTmpIndex] >= m_regsInPriorityOrder.size()
433                 && !m_interferenceEdges.contains(InterferenceEdge(u, adjacentTmpIndex)))
434                 return false;
435         }
436         return true;
437     }
438
439 protected:
440 #if PLATFORM(COCOA)
441 #pragma mark -
442 #endif
443
444     // Interference edges are not directed. An edge between any two Tmps is represented
445     // by the concatenated values of the smallest Tmp followed by the bigger Tmp.
446     class InterferenceEdge {
447     public:
448         InterferenceEdge()
449         {
450         }
451
452         InterferenceEdge(IndexType a, IndexType b)
453         {
454             ASSERT(a);
455             ASSERT(b);
456             ASSERT_WITH_MESSAGE(a != b, "A Tmp can never interfere with itself. Doing so would force it to be the superposition of two registers.");
457
458             if (b < a)
459                 std::swap(a, b);
460             m_value = static_cast<uint64_t>(a) << 32 | b;
461         }
462
463         InterferenceEdge(WTF::HashTableDeletedValueType)
464             : m_value(std::numeric_limits<uint64_t>::max())
465         {
466         }
467
468         IndexType first() const
469         {
470             return m_value >> 32 & 0xffffffff;
471         }
472
473         IndexType second() const
474         {
475             return m_value & 0xffffffff;
476         }
477
478         bool operator==(const InterferenceEdge other) const
479         {
480             return m_value == other.m_value;
481         }
482
483         bool isHashTableDeletedValue() const
484         {
485             return *this == InterferenceEdge(WTF::HashTableDeletedValue);
486         }
487
488         unsigned hash() const
489         {
490             return WTF::IntHash<uint64_t>::hash(m_value);
491         }
492
493         void dump(PrintStream& out) const
494         {
495             out.print(first(), "<=>", second());
496         }
497
498     private:
499         uint64_t m_value { 0 };
500     };
501
502     struct InterferenceEdgeHash {
503         static unsigned hash(const InterferenceEdge& key) { return key.hash(); }
504         static bool equal(const InterferenceEdge& a, const InterferenceEdge& b) { return a == b; }
505         static const bool safeToCompareToEmptyOrDeleted = true;
506     };
507     typedef SimpleClassHashTraits<InterferenceEdge> InterferenceEdgeHashTraits;
508
509     const Vector<Reg>& m_regsInPriorityOrder;
510     IndexType m_lastPrecoloredRegisterIndex { 0 };
511
512     // The interference graph.
513     HashSet<InterferenceEdge, InterferenceEdgeHash, InterferenceEdgeHashTraits> m_interferenceEdges;
514     Vector<Vector<IndexType, 0, UnsafeVectorOverflow, 4>, 0, UnsafeVectorOverflow> m_adjacencyList;
515     Vector<IndexType, 0, UnsafeVectorOverflow> m_degrees;
516
517     // Instead of keeping track of the move instructions, we just keep their operands around and use the index
518     // in the vector as the "identifier" for the move.
519     struct MoveOperands {
520         IndexType srcIndex;
521         IndexType dstIndex;
522     };
523     Vector<MoveOperands, 0, UnsafeVectorOverflow> m_coalescingCandidates;
524
525     // List of every move instruction associated with a Tmp.
526     Vector<HashSet<IndexType, typename DefaultHash<IndexType>::Hash, WTF::UnsignedWithZeroKeyHashTraits<IndexType>>> m_moveList;
527
528     // Colors.
529     Vector<Reg, 0, UnsafeVectorOverflow> m_coloredTmp;
530     Vector<IndexType> m_spilledTmps;
531
532     // Values that have been coalesced with an other value.
533     Vector<IndexType, 0, UnsafeVectorOverflow> m_coalescedTmps;
534
535     // The stack of Tmp removed from the graph and ready for coloring.
536     BitVector m_isOnSelectStack;
537     Vector<IndexType> m_selectStack;
538
539     struct OrderedMoveSet {
540         unsigned addMove()
541         {
542             unsigned nextIndex = m_moveList.size();
543             m_moveList.append(nextIndex);
544             m_positionInMoveList.append(nextIndex);
545             return nextIndex;
546         }
547
548         bool isEmpty() const
549         {
550             return m_moveList.isEmpty();
551         }
552
553         bool contains(unsigned index)
554         {
555             return m_positionInMoveList[index] != std::numeric_limits<unsigned>::max();
556         }
557
558         void takeMove(unsigned moveIndex)
559         {
560             unsigned positionInMoveList = m_positionInMoveList[moveIndex];
561             if (positionInMoveList == std::numeric_limits<unsigned>::max())
562                 return;
563
564             ASSERT(m_moveList[positionInMoveList] == moveIndex);
565             unsigned lastIndex = m_moveList.last();
566             m_positionInMoveList[lastIndex] = positionInMoveList;
567             m_moveList[positionInMoveList] = lastIndex;
568             m_moveList.removeLast();
569
570             m_positionInMoveList[moveIndex] = std::numeric_limits<unsigned>::max();
571
572             ASSERT(!contains(moveIndex));
573         }
574
575         unsigned takeLastMove()
576         {
577             ASSERT(!isEmpty());
578
579             unsigned lastIndex = m_moveList.takeLast();
580             ASSERT(m_positionInMoveList[lastIndex] == m_moveList.size());
581             m_positionInMoveList[lastIndex] = std::numeric_limits<unsigned>::max();
582
583             ASSERT(!contains(lastIndex));
584             return lastIndex;
585         }
586
587         void returnMove(unsigned index)
588         {
589             // This assertion is a bit strict but that is how the move list should be used. The only kind of moves that can
590             // return to the list are the ones that we previously failed to coalesce with the conservative heuristics.
591             // Values should not be added back if they were never taken out when attempting coalescing.
592             ASSERT(!contains(index));
593
594             unsigned position = m_moveList.size();
595             m_moveList.append(index);
596             m_positionInMoveList[index] = position;
597
598             ASSERT(contains(index));
599         }
600
601         void clear()
602         {
603             m_positionInMoveList.clear();
604             m_moveList.clear();
605         }
606
607     private:
608         Vector<unsigned, 0, UnsafeVectorOverflow> m_positionInMoveList;
609         Vector<unsigned, 0, UnsafeVectorOverflow> m_moveList;
610     };
611
612     // Work lists.
613     // Set of "move" enabled for possible coalescing.
614     OrderedMoveSet m_worklistMoves;
615     // Set of "move" not yet ready for coalescing.
616     BitVector m_activeMoves;
617     // Low-degree, non-Move related.
618     Vector<IndexType> m_simplifyWorklist;
619     // High-degree Tmp.
620     HashSet<IndexType> m_spillWorklist;
621     // Low-degree, Move related.
622     HashSet<IndexType> m_freezeWorklist;
623
624     bool m_hasSelectedSpill { false };
625     bool m_hasCoalescedNonTrivialMove { false };
626
627     // The mapping of Tmp to their alias for Moves that are always coalescing regardless of spilling.
628     Vector<IndexType, 0, UnsafeVectorOverflow> m_coalescedTmpsAtSpill;
629 };
630
631 // This perform all the tasks that are specific to certain register type.
632 template<Arg::Type type>
633 class ColoringAllocator : public AbstractColoringAllocator<unsigned> {
634 public:
635     ColoringAllocator(Code& code, TmpWidth& tmpWidth, const UseCounts<Tmp>& useCounts, const HashSet<unsigned>& unspillableTmp)
636         : AbstractColoringAllocator<unsigned>(regsInPriorityOrder(type), AbsoluteTmpMapper<type>::lastMachineRegisterIndex(), tmpArraySize(code))
637         , m_code(code)
638         , m_tmpWidth(tmpWidth)
639         , m_useCounts(useCounts)
640         , m_unspillableTmps(unspillableTmp)
641     {
642         initializePrecoloredTmp();
643         build();
644         allocate();
645     }
646
647     Tmp getAlias(Tmp tmp) const
648     {
649         return AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(getAlias(AbsoluteTmpMapper<type>::absoluteIndex(tmp)));
650     }
651
652     // This tells you if a Move will be coalescable if the src and dst end up matching. This method
653     // relies on an analysis that is invalidated by register allocation, so you it's only meaningful to
654     // call this *before* replacing the Tmp's in this Inst with registers or spill slots.
655     bool mayBeCoalescable(const Inst& inst) const
656     {
657         return mayBeCoalescableImpl(inst, &m_tmpWidth);
658     }
659
660     bool isUselessMove(const Inst& inst) const
661     {
662         return mayBeCoalescableImpl(inst, nullptr) && inst.args[0].tmp() == inst.args[1].tmp();
663     }
664
665     Tmp getAliasWhenSpilling(Tmp tmp) const
666     {
667         ASSERT_WITH_MESSAGE(!m_spilledTmps.isEmpty(), "This function is only valid for coalescing during spilling.");
668
669         if (m_coalescedTmpsAtSpill.isEmpty())
670             return tmp;
671
672         unsigned aliasIndex = AbsoluteTmpMapper<type>::absoluteIndex(tmp);
673         while (unsigned nextAliasIndex = m_coalescedTmpsAtSpill[aliasIndex])
674             aliasIndex = nextAliasIndex;
675
676         Tmp alias = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(aliasIndex);
677
678         ASSERT_WITH_MESSAGE(!m_spilledTmps.contains(aliasIndex) || alias == tmp, "The aliases at spill should always be colorable. Something went horribly wrong.");
679
680         return alias;
681     }
682
683     template<typename IndexIterator>
684     class IndexToTmpIteratorAdaptor {
685     public:
686         IndexToTmpIteratorAdaptor(IndexIterator&& indexIterator)
687             : m_indexIterator(WTFMove(indexIterator))
688         {
689         }
690
691         Tmp operator*() const { return AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*m_indexIterator); }
692         IndexToTmpIteratorAdaptor& operator++() { ++m_indexIterator; return *this; }
693
694         bool operator==(const IndexToTmpIteratorAdaptor& other) const
695         {
696             return m_indexIterator == other.m_indexIterator;
697         }
698
699         bool operator!=(const IndexToTmpIteratorAdaptor& other) const
700         {
701             return !(*this == other);
702         }
703
704     private:
705         IndexIterator m_indexIterator;
706     };
707
708     template<typename Collection>
709     class IndexToTmpIterableAdaptor {
710     public:
711         IndexToTmpIterableAdaptor(const Collection& collection)
712             : m_collection(collection)
713         {
714         }
715
716         IndexToTmpIteratorAdaptor<typename Collection::const_iterator> begin() const
717         {
718             return m_collection.begin();
719         }
720
721         IndexToTmpIteratorAdaptor<typename Collection::const_iterator> end() const
722         {
723             return m_collection.end();
724         }
725
726     private:
727         const Collection& m_collection;
728     };
729
730     IndexToTmpIterableAdaptor<Vector<unsigned>> spilledTmps() const { return m_spilledTmps; }
731
732     bool requiresSpilling() const { return !m_spilledTmps.isEmpty(); }
733
734     Reg allocatedReg(Tmp tmp) const
735     {
736         ASSERT(!tmp.isReg());
737         ASSERT(m_coloredTmp.size());
738         ASSERT(tmp.isGP() == (type == Arg::GP));
739
740         Reg reg = m_coloredTmp[AbsoluteTmpMapper<type>::absoluteIndex(tmp)];
741         if (!reg) {
742             // We only care about Tmps that interfere. A Tmp that never interfere with anything
743             // can take any register.
744             reg = regsInPriorityOrder(type).first();
745         }
746         return reg;
747     }
748
749 private:
750     static unsigned tmpArraySize(Code& code)
751     {
752         unsigned numTmps = code.numTmps(type);
753         return AbsoluteTmpMapper<type>::absoluteIndex(numTmps);
754     }
755
756     void initializePrecoloredTmp()
757     {
758         m_coloredTmp.resize(m_lastPrecoloredRegisterIndex + 1);
759         for (unsigned i = 1; i <= m_lastPrecoloredRegisterIndex; ++i) {
760             Tmp tmp = AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(i);
761             ASSERT(tmp.isReg());
762             m_coloredTmp[i] = tmp.reg();
763         }
764     }
765
766     void build()
767     {
768         TmpLiveness<type> liveness(m_code);
769         for (BasicBlock* block : m_code) {
770             typename TmpLiveness<type>::LocalCalc localCalc(liveness, block);
771             for (unsigned instIndex = block->size(); instIndex--;) {
772                 Inst& inst = block->at(instIndex);
773                 Inst* nextInst = block->get(instIndex + 1);
774                 build(&inst, nextInst, localCalc);
775                 localCalc.execute(instIndex);
776             }
777             build(nullptr, &block->at(0), localCalc);
778         }
779     }
780
781     void build(Inst* prevInst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
782     {
783         Inst::forEachDefWithExtraClobberedRegs<Tmp>(
784             prevInst, nextInst,
785             [&] (const Tmp& arg, Arg::Role, Arg::Type argType, Arg::Width) {
786                 if (argType != type)
787                     return;
788                 
789                 // All the Def()s interfere with each other and with all the extra clobbered Tmps.
790                 // We should not use forEachDefWithExtraClobberedRegs() here since colored Tmps
791                 // do not need interference edges in our implementation.
792                 Inst::forEachDef<Tmp>(
793                     prevInst, nextInst,
794                     [&] (Tmp& otherArg, Arg::Role, Arg::Type argType, Arg::Width) {
795                         if (argType != type)
796                             return;
797                         
798                         addEdge(arg, otherArg);
799                     });
800             });
801
802         if (prevInst && mayBeCoalescable(*prevInst)) {
803             // We do not want the Use() of this move to interfere with the Def(), even if it is live
804             // after the Move. If we were to add the interference edge, it would be impossible to
805             // coalesce the Move even if the two Tmp never interfere anywhere.
806             Tmp defTmp;
807             Tmp useTmp;
808             prevInst->forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type, Arg::Width) {
809                 if (Arg::isLateDef(role))
810                     defTmp = argTmp;
811                 else {
812                     ASSERT(Arg::isEarlyUse(role));
813                     useTmp = argTmp;
814                 }
815             });
816             ASSERT(defTmp);
817             ASSERT(useTmp);
818
819             unsigned nextMoveIndex = m_coalescingCandidates.size();
820             m_coalescingCandidates.append({ AbsoluteTmpMapper<type>::absoluteIndex(useTmp), AbsoluteTmpMapper<type>::absoluteIndex(defTmp) });
821
822             unsigned newIndexInWorklist = m_worklistMoves.addMove();
823             ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
824
825             ASSERT(nextMoveIndex <= m_activeMoves.size());
826             m_activeMoves.ensureSize(nextMoveIndex + 1);
827
828             for (const Arg& arg : prevInst->args) {
829                 auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
830                 list.add(nextMoveIndex);
831             }
832
833             for (const Tmp& liveTmp : localCalc.live()) {
834                 if (liveTmp != useTmp)
835                     addEdge(defTmp, liveTmp);
836             }
837
838             // The next instruction could have early clobbers or early def's. We need to consider
839             // those now.
840             addEdges(nullptr, nextInst, localCalc.live());
841         } else
842             addEdges(prevInst, nextInst, localCalc.live());
843     }
844
845     void addEdges(Inst* prevInst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmps)
846     {
847         // All the Def()s interfere with everthing live.
848         Inst::forEachDefWithExtraClobberedRegs<Tmp>(
849             prevInst, nextInst,
850             [&] (const Tmp& arg, Arg::Role, Arg::Type argType, Arg::Width) {
851                 if (argType != type)
852                     return;
853                 
854                 for (const Tmp& liveTmp : liveTmps) {
855                     if (liveTmp.isGP() == (type == Arg::GP))
856                         addEdge(arg, liveTmp);
857                 }
858             });
859     }
860
861     void addEdge(Tmp a, Tmp b)
862     {
863         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.");
864
865         addEdge(AbsoluteTmpMapper<type>::absoluteIndex(a), AbsoluteTmpMapper<type>::absoluteIndex(b));
866     }
867
868     // Calling this without a tmpWidth will perform a more conservative coalescing analysis that assumes
869     // that Move32's are not coalescable.
870     static bool mayBeCoalescableImpl(const Inst& inst, TmpWidth* tmpWidth)
871     {
872         switch (type) {
873         case Arg::GP:
874             switch (inst.opcode) {
875             case Move:
876             case Move32:
877                 break;
878             default:
879                 return false;
880             }
881             break;
882         case Arg::FP:
883             switch (inst.opcode) {
884             case MoveFloat:
885             case MoveDouble:
886                 break;
887             default:
888                 return false;
889             }
890             break;
891         }
892
893         ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
894
895         if (!inst.args[0].isTmp() || !inst.args[1].isTmp())
896             return false;
897
898         ASSERT(inst.args[0].type() == type);
899         ASSERT(inst.args[1].type() == type);
900
901         // We can coalesce a Move32 so long as either of the following holds:
902         // - The input is already zero-filled.
903         // - The output only cares about the low 32 bits.
904         //
905         // Note that the input property requires an analysis over ZDef's, so it's only valid so long
906         // as the input gets a register. We don't know if the input gets a register, but we do know
907         // that if it doesn't get a register then we will still emit this Move32.
908         if (inst.opcode == Move32) {
909             if (!tmpWidth)
910                 return false;
911
912             if (tmpWidth->defWidth(inst.args[0].tmp()) > Arg::Width32
913                 && tmpWidth->useWidth(inst.args[1].tmp()) > Arg::Width32)
914                 return false;
915         }
916         
917         return true;
918     }
919
920     void selectSpill()
921     {
922         if (!m_hasSelectedSpill) {
923             m_hasSelectedSpill = true;
924
925             if (m_hasCoalescedNonTrivialMove)
926                 m_coalescedTmpsAtSpill = m_coalescedTmps;
927         }
928
929         auto iterator = m_spillWorklist.begin();
930
931         while (iterator != m_spillWorklist.end() && m_unspillableTmps.contains(*iterator))
932             ++iterator;
933
934         RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
935
936         // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
937         // gets a register.
938         auto score = [&] (Tmp tmp) -> double {
939             // Air exposes the concept of "fast tmps", and we interpret that to mean that the tmp
940             // should always be in a register.
941             if (m_code.isFastTmp(tmp))
942                 return 0;
943             
944             // All else being equal, the score should be directly related to the degree.
945             double degree = static_cast<double>(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
946
947             // All else being equal, the score should be inversely related to the number of warm uses and
948             // defs.
949             const UseCounts<Tmp>::Counts& counts = m_useCounts[tmp];
950             double uses = counts.numWarmUses + counts.numDefs;
951
952             return degree / uses;
953         };
954
955         auto victimIterator = iterator;
956         double maxScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
957
958         ++iterator;
959         for (;iterator != m_spillWorklist.end(); ++iterator) {
960             double tmpScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
961             if (tmpScore > maxScore) {
962                 if (m_unspillableTmps.contains(*iterator))
963                     continue;
964
965                 victimIterator = iterator;
966                 maxScore = tmpScore;
967             }
968         }
969
970         unsigned victimIndex = *victimIterator;
971         m_spillWorklist.remove(victimIterator);
972         m_simplifyWorklist.append(victimIndex);
973
974         freezeMoves(victimIndex);
975     }
976
977     void allocate()
978     {
979         ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
980
981         makeWorkList();
982
983         if (debug) {
984             dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
985             dumpInterferenceGraphInDot(WTF::dataFile());
986             dataLog("Initial work list\n");
987             dumpWorkLists(WTF::dataFile());
988         }
989
990         do {
991             if (traceDebug) {
992                 dataLog("Before Graph simplification iteration\n");
993                 dumpWorkLists(WTF::dataFile());
994             }
995
996             if (!m_simplifyWorklist.isEmpty())
997                 simplify();
998             else if (!m_worklistMoves.isEmpty())
999                 coalesce();
1000             else if (!m_freezeWorklist.isEmpty())
1001                 freeze();
1002             else if (!m_spillWorklist.isEmpty())
1003                 selectSpill();
1004
1005             if (traceDebug) {
1006                 dataLog("After Graph simplification iteration\n");
1007                 dumpWorkLists(WTF::dataFile());
1008             }
1009         } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
1010
1011         assignColors();
1012     }
1013
1014 #if PLATFORM(COCOA)
1015 #pragma mark - Debugging helpers.
1016 #endif
1017
1018     void dumpInterferenceGraphInDot(PrintStream& out)
1019     {
1020         out.print("graph InterferenceGraph { \n");
1021
1022         HashSet<Tmp> tmpsWithInterferences;
1023         for (const auto& edge : m_interferenceEdges) {
1024             tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.first()));
1025             tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.second()));
1026         }
1027
1028         for (const auto& tmp : tmpsWithInterferences)
1029             out.print("    ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
1030
1031         for (const auto& edge : m_interferenceEdges)
1032             out.print("    ", edge.first(), " -- ", edge.second(), ";\n");
1033         out.print("}\n");
1034     }
1035
1036     void dumpWorkLists(PrintStream& out)
1037     {
1038         out.print("Simplify work list:\n");
1039         for (unsigned tmpIndex : m_simplifyWorklist)
1040             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1041         out.printf("Moves work list is empty? %d\n", m_worklistMoves.isEmpty());
1042         out.print("Freeze work list:\n");
1043         for (unsigned tmpIndex : m_freezeWorklist)
1044             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1045         out.print("Spill work list:\n");
1046         for (unsigned tmpIndex : m_spillWorklist)
1047             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1048     }
1049
1050     using AbstractColoringAllocator<unsigned>::addEdge;
1051     using AbstractColoringAllocator<unsigned>::getAlias;
1052
1053     Code& m_code;
1054     TmpWidth& m_tmpWidth;
1055     // FIXME: spilling should not type specific. It is only a side effect of using UseCounts.
1056     const UseCounts<Tmp>& m_useCounts;
1057     const HashSet<unsigned>& m_unspillableTmps;
1058 };
1059
1060 class IteratedRegisterCoalescing {
1061 public:
1062     IteratedRegisterCoalescing(Code& code)
1063         : m_code(code)
1064         , m_useCounts(code)
1065     {
1066     }
1067
1068     void run()
1069     {
1070         iteratedRegisterCoalescingOnType<Arg::GP>();
1071         iteratedRegisterCoalescingOnType<Arg::FP>();
1072
1073         if (reportStats)
1074             dataLog("Num iterations = ", m_numIterations, "\n");
1075     }
1076
1077 private:
1078     template<Arg::Type type>
1079     void iteratedRegisterCoalescingOnType()
1080     {
1081         HashSet<unsigned> unspillableTmps;
1082
1083         // FIXME: If a Tmp is used only from a Scratch role and that argument is !admitsStack, then
1084         // we should add the Tmp to unspillableTmps. That will help avoid relooping only to turn the
1085         // Tmp into an unspillable Tmp.
1086         // https://bugs.webkit.org/show_bug.cgi?id=152699
1087         
1088         while (true) {
1089             ++m_numIterations;
1090
1091             // FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.
1092             // We need to recompute because spilling adds tmps, but we could just update tmpWidth when we
1093             // add those tmps. Note that one easy way to remove the recomputation is to make any newly
1094             // added Tmps get the same use/def widths that the original Tmp got. But, this may hurt the
1095             // spill code we emit. Since we currently recompute TmpWidth after spilling, the newly
1096             // created Tmps may get narrower use/def widths. On the other hand, the spiller already
1097             // selects which move instruction to use based on the original Tmp's widths, so it may not
1098             // matter than a subsequent iteration sees a coservative width for the new Tmps. Also, the
1099             // recomputation may not actually be a performance problem; it's likely that a better way to
1100             // improve performance of TmpWidth is to replace its HashMap with something else. It's
1101             // possible that most of the TmpWidth overhead is from queries of TmpWidth rather than the
1102             // recomputation, in which case speeding up the lookup would be a bigger win.
1103             // https://bugs.webkit.org/show_bug.cgi?id=152478
1104             m_tmpWidth.recompute(m_code);
1105             
1106             ColoringAllocator<type> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);
1107             if (!allocator.requiresSpilling()) {
1108                 assignRegistersToTmp(allocator);
1109                 return;
1110             }
1111             addSpillAndFill<type>(allocator, unspillableTmps);
1112         }
1113     }
1114
1115     template<Arg::Type type>
1116     void assignRegistersToTmp(const ColoringAllocator<type>& allocator)
1117     {
1118         for (BasicBlock* block : m_code) {
1119             // Give Tmp a valid register.
1120             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
1121                 Inst& inst = block->at(instIndex);
1122
1123                 // The mayBeCoalescable() method will change its mind for some operations after we
1124                 // complete register allocation. So, we record this before starting.
1125                 bool mayBeCoalescable = allocator.mayBeCoalescable(inst);
1126
1127                 // On X86_64, Move32 is cheaper if we know that it's equivalent to a Move. It's
1128                 // equivalent if the destination's high bits are not observable or if the source's high
1129                 // bits are all zero. Note that we don't have the opposite optimization for other
1130                 // architectures, which may prefer Move over Move32, because Move is canonical already.
1131                 if (type == Arg::GP && optimizeForX86_64() && inst.opcode == Move
1132                     && inst.args[0].isTmp() && inst.args[1].isTmp()) {
1133                     if (m_tmpWidth.useWidth(inst.args[1].tmp()) <= Arg::Width32
1134                         || m_tmpWidth.defWidth(inst.args[0].tmp()) <= Arg::Width32)
1135                         inst.opcode = Move32;
1136                 }
1137
1138                 inst.forEachTmpFast([&] (Tmp& tmp) {
1139                     if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
1140                         return;
1141
1142                     Tmp aliasTmp = allocator.getAlias(tmp);
1143                     Tmp assignedTmp;
1144                     if (aliasTmp.isReg())
1145                         assignedTmp = Tmp(aliasTmp.reg());
1146                     else {
1147                         auto reg = allocator.allocatedReg(aliasTmp);
1148                         ASSERT(reg);
1149                         assignedTmp = Tmp(reg);
1150                     }
1151                     ASSERT(assignedTmp.isReg());
1152                     tmp = assignedTmp;
1153                 });
1154
1155                 if (mayBeCoalescable && inst.args[0].isTmp() && inst.args[1].isTmp()
1156                     && inst.args[0].tmp() == inst.args[1].tmp())
1157                     inst = Inst();
1158             }
1159
1160             // Remove all the useless moves we created in this block.
1161             block->insts().removeAllMatching([&] (const Inst& inst) {
1162                 return !inst;
1163             });
1164         }
1165     }
1166
1167     template<Arg::Type type>
1168     void addSpillAndFill(const ColoringAllocator<type>& allocator, HashSet<unsigned>& unspillableTmps)
1169     {
1170         HashMap<Tmp, StackSlot*> stackSlots;
1171         unsigned newStackSlotThreshold = m_code.stackSlots().size();
1172         for (Tmp tmp : allocator.spilledTmps()) {
1173             // All the spilled values become unspillable.
1174             unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
1175
1176             // Allocate stack slot for each spilled value.
1177             StackSlot* stackSlot = m_code.addStackSlot(
1178                 m_tmpWidth.width(tmp) <= Arg::Width32 ? 4 : 8, StackSlotKind::Anonymous);
1179             bool isNewTmp = stackSlots.add(tmp, stackSlot).isNewEntry;
1180             ASSERT_UNUSED(isNewTmp, isNewTmp);
1181         }
1182
1183         // Rewrite the program to get rid of the spilled Tmp.
1184         InsertionSet insertionSet(m_code);
1185         for (BasicBlock* block : m_code) {
1186             bool hasAliasedTmps = false;
1187
1188             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
1189                 Inst& inst = block->at(instIndex);
1190
1191                 // The TmpWidth analysis will say that a Move only stores 32 bits into the destination,
1192                 // if the source only had 32 bits worth of non-zero bits. Same for the source: it will
1193                 // only claim to read 32 bits from the source if only 32 bits of the destination are
1194                 // read. Note that we only apply this logic if this turns into a load or store, since
1195                 // Move is the canonical way to move data between GPRs.
1196                 bool forceMove32IfDidSpill = false;
1197                 bool didSpill = false;
1198                 if (type == Arg::GP && inst.opcode == Move) {
1199                     if ((inst.args[0].isTmp() && m_tmpWidth.width(inst.args[0].tmp()) <= Arg::Width32)
1200                         || (inst.args[1].isTmp() && m_tmpWidth.width(inst.args[1].tmp()) <= Arg::Width32))
1201                         forceMove32IfDidSpill = true;
1202                 }
1203
1204                 // Try to replace the register use by memory use when possible.
1205                 for (unsigned i = 0; i < inst.args.size(); ++i) {
1206                     Arg& arg = inst.args[i];
1207                     if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
1208                         auto stackSlotEntry = stackSlots.find(arg.tmp());
1209                         if (stackSlotEntry != stackSlots.end() && inst.admitsStack(i)) {
1210                             arg = Arg::stack(stackSlotEntry->value);
1211                             didSpill = true;
1212                         }
1213                     }
1214                 }
1215
1216                 if (didSpill && forceMove32IfDidSpill)
1217                     inst.opcode = Move32;
1218
1219                 // For every other case, add Load/Store as needed.
1220                 inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Arg::Type argType, Arg::Width) {
1221                     if (tmp.isReg() || argType != type)
1222                         return;
1223
1224                     auto stackSlotEntry = stackSlots.find(tmp);
1225                     if (stackSlotEntry == stackSlots.end()) {
1226                         Tmp alias = allocator.getAliasWhenSpilling(tmp);
1227                         if (alias != tmp) {
1228                             tmp = alias;
1229                             hasAliasedTmps = true;
1230                         }
1231                         return;
1232                     }
1233
1234                     Arg arg = Arg::stack(stackSlotEntry->value);
1235                     Opcode move = Oops;
1236                     switch (stackSlotEntry->value->byteSize()) {
1237                     case 4:
1238                         move = type == Arg::GP ? Move32 : MoveFloat;
1239                         break;
1240                     case 8:
1241                         move = type == Arg::GP ? Move : MoveDouble;
1242                         break;
1243                     default:
1244                         RELEASE_ASSERT_NOT_REACHED();
1245                         break;
1246                     }
1247
1248                     tmp = m_code.newTmp(type);
1249                     unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
1250
1251                     if (Arg::isAnyUse(role) && role != Arg::Scratch)
1252                         insertionSet.insert(instIndex, move, inst.origin, arg, tmp);
1253                     if (Arg::isAnyDef(role))
1254                         insertionSet.insert(instIndex + 1, move, inst.origin, tmp, arg);
1255                 });
1256             }
1257             insertionSet.execute(block);
1258
1259             if (hasAliasedTmps) {
1260                 block->insts().removeAllMatching([&] (const Inst& inst) {
1261                     return allocator.isUselessMove(inst);
1262                 });
1263             }
1264         }
1265
1266         fixSpillSlotZDef(
1267             m_code,
1268             [&] (StackSlot* stackSlot) -> bool {
1269                 return stackSlot->index() >= newStackSlotThreshold;
1270             });
1271     }
1272
1273     Code& m_code;
1274     TmpWidth m_tmpWidth;
1275     UseCounts<Tmp> m_useCounts;
1276     unsigned m_numIterations { 0 };
1277 };
1278
1279 } // anonymous namespace
1280
1281 void iteratedRegisterCoalescing(Code& code)
1282 {
1283     PhaseScope phaseScope(code, "iteratedRegisterCoalescing");
1284
1285     IteratedRegisterCoalescing iteratedRegisterCoalescing(code);
1286     iteratedRegisterCoalescing.run();
1287 }
1288
1289 } } } // namespace JSC::B3::Air
1290
1291 #endif // ENABLE(B3_JIT)