Replace WTF::move with WTFMove
[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         bzero(m_degrees.data() + firstNonRegIndex, (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 = instIndex + 1 < block->size() ? &block->at(instIndex + 1) : nullptr;
774                 build(inst, nextInst, localCalc);
775                 localCalc.execute(instIndex);
776             }
777         }
778     }
779
780     void build(Inst& inst, Inst* nextInst, const typename TmpLiveness<type>::LocalCalc& localCalc)
781     {
782         inst.forEachTmpWithExtraClobberedRegs(
783             nextInst,
784             [&] (const Tmp& arg, Arg::Role role, Arg::Type argType, Arg::Width) {
785                 if (!Arg::isDef(role) || argType != type)
786                     return;
787                 
788                 // All the Def()s interfere with each other and with all the extra clobbered Tmps.
789                 // We should not use forEachDefAndExtraClobberedTmp() here since colored Tmps
790                 // do not need interference edges in our implementation.
791                 inst.forEachTmp([&] (Tmp& otherArg, Arg::Role role, Arg::Type argType, Arg::Width) {
792                     if (!Arg::isDef(role) || argType != type)
793                         return;
794
795                     addEdge(arg, otherArg);
796                 });
797             });
798
799         if (mayBeCoalescable(inst)) {
800             // We do not want the Use() of this move to interfere with the Def(), even if it is live
801             // after the Move. If we were to add the interference edge, it would be impossible to
802             // coalesce the Move even if the two Tmp never interfere anywhere.
803             Tmp defTmp;
804             Tmp useTmp;
805             inst.forEachTmp([&defTmp, &useTmp] (Tmp& argTmp, Arg::Role role, Arg::Type, Arg::Width) {
806                 if (Arg::isDef(role))
807                     defTmp = argTmp;
808                 else {
809                     ASSERT(Arg::isEarlyUse(role));
810                     useTmp = argTmp;
811                 }
812             });
813             ASSERT(defTmp);
814             ASSERT(useTmp);
815
816             unsigned nextMoveIndex = m_coalescingCandidates.size();
817             m_coalescingCandidates.append({ AbsoluteTmpMapper<type>::absoluteIndex(useTmp), AbsoluteTmpMapper<type>::absoluteIndex(defTmp) });
818
819             unsigned newIndexInWorklist = m_worklistMoves.addMove();
820             ASSERT_UNUSED(newIndexInWorklist, newIndexInWorklist == nextMoveIndex);
821
822             ASSERT(nextMoveIndex <= m_activeMoves.size());
823             m_activeMoves.ensureSize(nextMoveIndex + 1);
824
825             for (const Arg& arg : inst.args) {
826                 auto& list = m_moveList[AbsoluteTmpMapper<type>::absoluteIndex(arg.tmp())];
827                 list.add(nextMoveIndex);
828             }
829
830             for (const Tmp& liveTmp : localCalc.live()) {
831                 if (liveTmp != useTmp)
832                     addEdge(defTmp, liveTmp);
833             }
834
835             // The next instruction could have early clobbers. We need to consider those now.
836             if (nextInst && nextInst->hasSpecial()) {
837                 nextInst->extraEarlyClobberedRegs().forEach([&] (Reg reg) {
838                     if (reg.isGPR() == (type == Arg::GP)) {
839                         for (const Tmp& liveTmp : localCalc.live())
840                             addEdge(Tmp(reg), liveTmp);
841                     }
842                 });
843             }
844         } else
845             addEdges(inst, nextInst, localCalc.live());
846     }
847
848     void addEdges(Inst& inst, Inst* nextInst, typename TmpLiveness<type>::LocalCalc::Iterable liveTmps)
849     {
850         // All the Def()s interfere with everthing live.
851         inst.forEachTmpWithExtraClobberedRegs(
852             nextInst,
853             [&] (const Tmp& arg, Arg::Role role, Arg::Type argType, Arg::Width) {
854                 if (!Arg::isDef(role) || argType != type)
855                     return;
856                 
857                 for (const Tmp& liveTmp : liveTmps) {
858                     if (liveTmp.isGP() == (type == Arg::GP))
859                         addEdge(arg, liveTmp);
860                 }
861             });
862     }
863
864     void addEdge(Tmp a, Tmp b)
865     {
866         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.");
867
868         addEdge(AbsoluteTmpMapper<type>::absoluteIndex(a), AbsoluteTmpMapper<type>::absoluteIndex(b));
869     }
870
871     // Calling this without a tmpWidth will perform a more conservative coalescing analysis that assumes
872     // that Move32's are not coalescable.
873     static bool mayBeCoalescableImpl(const Inst& inst, TmpWidth* tmpWidth)
874     {
875         switch (type) {
876         case Arg::GP:
877             switch (inst.opcode) {
878             case Move:
879             case Move32:
880                 break;
881             default:
882                 return false;
883             }
884             break;
885         case Arg::FP:
886             switch (inst.opcode) {
887             case MoveFloat:
888             case MoveDouble:
889                 break;
890             default:
891                 return false;
892             }
893             break;
894         }
895
896         ASSERT_WITH_MESSAGE(inst.args.size() == 2, "We assume coalecable moves only have two arguments in a few places.");
897
898         if (!inst.args[0].isTmp() || !inst.args[1].isTmp())
899             return false;
900
901         ASSERT(inst.args[0].type() == type);
902         ASSERT(inst.args[1].type() == type);
903
904         // We can coalesce a Move32 so long as either of the following holds:
905         // - The input is already zero-filled.
906         // - The output only cares about the low 32 bits.
907         //
908         // Note that the input property requires an analysis over ZDef's, so it's only valid so long
909         // as the input gets a register. We don't know if the input gets a register, but we do know
910         // that if it doesn't get a register then we will still emit this Move32.
911         if (inst.opcode == Move32) {
912             if (!tmpWidth)
913                 return false;
914
915             if (tmpWidth->defWidth(inst.args[0].tmp()) > Arg::Width32
916                 && tmpWidth->useWidth(inst.args[1].tmp()) > Arg::Width32)
917                 return false;
918         }
919         
920         return true;
921     }
922
923     void selectSpill()
924     {
925         if (!m_hasSelectedSpill) {
926             m_hasSelectedSpill = true;
927
928             if (m_hasCoalescedNonTrivialMove)
929                 m_coalescedTmpsAtSpill = m_coalescedTmps;
930         }
931
932         auto iterator = m_spillWorklist.begin();
933
934         while (iterator != m_spillWorklist.end() && m_unspillableTmps.contains(*iterator))
935             ++iterator;
936
937         RELEASE_ASSERT_WITH_MESSAGE(iterator != m_spillWorklist.end(), "It is not possible to color the Air graph with the number of available registers.");
938
939         // Higher score means more desirable to spill. Lower scores maximize the likelihood that a tmp
940         // gets a register.
941         auto score = [&] (Tmp tmp) -> double {
942             // Air exposes the concept of "fast tmps", and we interpret that to mean that the tmp
943             // should always be in a register.
944             if (m_code.isFastTmp(tmp))
945                 return 0;
946             
947             // All else being equal, the score should be directly related to the degree.
948             double degree = static_cast<double>(m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)]);
949
950             // All else being equal, the score should be inversely related to the number of warm uses and
951             // defs.
952             const UseCounts<Tmp>::Counts& counts = m_useCounts[tmp];
953             double uses = counts.numWarmUses + counts.numDefs;
954
955             return degree / uses;
956         };
957
958         auto victimIterator = iterator;
959         double maxScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
960
961         ++iterator;
962         for (;iterator != m_spillWorklist.end(); ++iterator) {
963             double tmpScore = score(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(*iterator));
964             if (tmpScore > maxScore) {
965                 if (m_unspillableTmps.contains(*iterator))
966                     continue;
967
968                 victimIterator = iterator;
969                 maxScore = tmpScore;
970             }
971         }
972
973         unsigned victimIndex = *victimIterator;
974         m_spillWorklist.remove(victimIterator);
975         m_simplifyWorklist.append(victimIndex);
976
977         freezeMoves(victimIndex);
978     }
979
980     void allocate()
981     {
982         ASSERT_WITH_MESSAGE(m_activeMoves.size() >= m_coalescingCandidates.size(), "The activeMove set should be big enough for the quick operations of BitVector.");
983
984         makeWorkList();
985
986         if (debug) {
987             dataLog("Interference: ", listDump(m_interferenceEdges), "\n");
988             dumpInterferenceGraphInDot(WTF::dataFile());
989             dataLog("Initial work list\n");
990             dumpWorkLists(WTF::dataFile());
991         }
992
993         do {
994             if (traceDebug) {
995                 dataLog("Before Graph simplification iteration\n");
996                 dumpWorkLists(WTF::dataFile());
997             }
998
999             if (!m_simplifyWorklist.isEmpty())
1000                 simplify();
1001             else if (!m_worklistMoves.isEmpty())
1002                 coalesce();
1003             else if (!m_freezeWorklist.isEmpty())
1004                 freeze();
1005             else if (!m_spillWorklist.isEmpty())
1006                 selectSpill();
1007
1008             if (traceDebug) {
1009                 dataLog("After Graph simplification iteration\n");
1010                 dumpWorkLists(WTF::dataFile());
1011             }
1012         } while (!m_simplifyWorklist.isEmpty() || !m_worklistMoves.isEmpty() || !m_freezeWorklist.isEmpty() || !m_spillWorklist.isEmpty());
1013
1014         assignColors();
1015     }
1016
1017 #if PLATFORM(COCOA)
1018 #pragma mark - Debugging helpers.
1019 #endif
1020
1021     void dumpInterferenceGraphInDot(PrintStream& out)
1022     {
1023         out.print("graph InterferenceGraph { \n");
1024
1025         HashSet<Tmp> tmpsWithInterferences;
1026         for (const auto& edge : m_interferenceEdges) {
1027             tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.first()));
1028             tmpsWithInterferences.add(AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(edge.second()));
1029         }
1030
1031         for (const auto& tmp : tmpsWithInterferences)
1032             out.print("    ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
1033
1034         for (const auto& edge : m_interferenceEdges)
1035             out.print("    ", edge.first(), " -- ", edge.second(), ";\n");
1036         out.print("}\n");
1037     }
1038
1039     void dumpWorkLists(PrintStream& out)
1040     {
1041         out.print("Simplify work list:\n");
1042         for (unsigned tmpIndex : m_simplifyWorklist)
1043             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1044         out.printf("Moves work list is empty? %d\n", m_worklistMoves.isEmpty());
1045         out.print("Freeze work list:\n");
1046         for (unsigned tmpIndex : m_freezeWorklist)
1047             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1048         out.print("Spill work list:\n");
1049         for (unsigned tmpIndex : m_spillWorklist)
1050             out.print("    ", AbsoluteTmpMapper<type>::tmpFromAbsoluteIndex(tmpIndex), "\n");
1051     }
1052
1053     using AbstractColoringAllocator<unsigned>::addEdge;
1054     using AbstractColoringAllocator<unsigned>::getAlias;
1055
1056     Code& m_code;
1057     TmpWidth& m_tmpWidth;
1058     // FIXME: spilling should not type specific. It is only a side effect of using UseCounts.
1059     const UseCounts<Tmp>& m_useCounts;
1060     const HashSet<unsigned>& m_unspillableTmps;
1061 };
1062
1063 class IteratedRegisterCoalescing {
1064 public:
1065     IteratedRegisterCoalescing(Code& code)
1066         : m_code(code)
1067         , m_useCounts(code)
1068     {
1069     }
1070
1071     void run()
1072     {
1073         iteratedRegisterCoalescingOnType<Arg::GP>();
1074         iteratedRegisterCoalescingOnType<Arg::FP>();
1075
1076         if (reportStats)
1077             dataLog("Num iterations = ", m_numIterations, "\n");
1078     }
1079
1080 private:
1081     template<Arg::Type type>
1082     void iteratedRegisterCoalescingOnType()
1083     {
1084         HashSet<unsigned> unspillableTmps;
1085         while (true) {
1086             ++m_numIterations;
1087
1088             // FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.
1089             // We need to recompute because spilling adds tmps, but we could just update tmpWidth when we
1090             // add those tmps. Note that one easy way to remove the recomputation is to make any newly
1091             // added Tmps get the same use/def widths that the original Tmp got. But, this may hurt the
1092             // spill code we emit. Since we currently recompute TmpWidth after spilling, the newly
1093             // created Tmps may get narrower use/def widths. On the other hand, the spiller already
1094             // selects which move instruction to use based on the original Tmp's widths, so it may not
1095             // matter than a subsequent iteration sees a coservative width for the new Tmps. Also, the
1096             // recomputation may not actually be a performance problem; it's likely that a better way to
1097             // improve performance of TmpWidth is to replace its HashMap with something else. It's
1098             // possible that most of the TmpWidth overhead is from queries of TmpWidth rather than the
1099             // recomputation, in which case speeding up the lookup would be a bigger win.
1100             // https://bugs.webkit.org/show_bug.cgi?id=152478
1101             m_tmpWidth.recompute(m_code);
1102             
1103             ColoringAllocator<type> allocator(m_code, m_tmpWidth, m_useCounts, unspillableTmps);
1104             if (!allocator.requiresSpilling()) {
1105                 assignRegistersToTmp(allocator);
1106                 return;
1107             }
1108             addSpillAndFill<type>(allocator, unspillableTmps);
1109         }
1110     }
1111
1112     template<Arg::Type type>
1113     void assignRegistersToTmp(const ColoringAllocator<type>& allocator)
1114     {
1115         for (BasicBlock* block : m_code) {
1116             // Give Tmp a valid register.
1117             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
1118                 Inst& inst = block->at(instIndex);
1119
1120                 // The mayBeCoalescable() method will change its mind for some operations after we
1121                 // complete register allocation. So, we record this before starting.
1122                 bool mayBeCoalescable = allocator.mayBeCoalescable(inst);
1123
1124                 // On X86_64, Move32 is cheaper if we know that it's equivalent to a Move. It's
1125                 // equivalent if the destination's high bits are not observable or if the source's high
1126                 // bits are all zero. Note that we don't have the opposite optimization for other
1127                 // architectures, which may prefer Move over Move32, because Move is canonical already.
1128                 if (type == Arg::GP && optimizeForX86_64() && inst.opcode == Move
1129                     && inst.args[0].isTmp() && inst.args[1].isTmp()) {
1130                     if (m_tmpWidth.useWidth(inst.args[1].tmp()) <= Arg::Width32
1131                         || m_tmpWidth.defWidth(inst.args[0].tmp()) <= Arg::Width32)
1132                         inst.opcode = Move32;
1133                 }
1134
1135                 inst.forEachTmpFast([&] (Tmp& tmp) {
1136                     if (tmp.isReg() || tmp.isGP() == (type != Arg::GP))
1137                         return;
1138
1139                     Tmp aliasTmp = allocator.getAlias(tmp);
1140                     Tmp assignedTmp;
1141                     if (aliasTmp.isReg())
1142                         assignedTmp = Tmp(aliasTmp.reg());
1143                     else {
1144                         auto reg = allocator.allocatedReg(aliasTmp);
1145                         ASSERT(reg);
1146                         assignedTmp = Tmp(reg);
1147                     }
1148                     ASSERT(assignedTmp.isReg());
1149                     tmp = assignedTmp;
1150                 });
1151
1152                 if (mayBeCoalescable && inst.args[0].isTmp() && inst.args[1].isTmp()
1153                     && inst.args[0].tmp() == inst.args[1].tmp())
1154                     inst = Inst();
1155             }
1156
1157             // Remove all the useless moves we created in this block.
1158             block->insts().removeAllMatching([&] (const Inst& inst) {
1159                 return !inst;
1160             });
1161         }
1162     }
1163
1164     template<Arg::Type type>
1165     void addSpillAndFill(const ColoringAllocator<type>& allocator, HashSet<unsigned>& unspillableTmps)
1166     {
1167         HashMap<Tmp, StackSlot*> stackSlots;
1168         unsigned newStackSlotThreshold = m_code.stackSlots().size();
1169         for (Tmp tmp : allocator.spilledTmps()) {
1170             // All the spilled values become unspillable.
1171             unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
1172
1173             // Allocate stack slot for each spilled value.
1174             StackSlot* stackSlot = m_code.addStackSlot(
1175                 m_tmpWidth.width(tmp) <= Arg::Width32 ? 4 : 8, StackSlotKind::Anonymous);
1176             bool isNewTmp = stackSlots.add(tmp, stackSlot).isNewEntry;
1177             ASSERT_UNUSED(isNewTmp, isNewTmp);
1178         }
1179
1180         // Rewrite the program to get rid of the spilled Tmp.
1181         InsertionSet insertionSet(m_code);
1182         for (BasicBlock* block : m_code) {
1183             bool hasAliasedTmps = false;
1184
1185             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
1186                 Inst& inst = block->at(instIndex);
1187
1188                 // The TmpWidth analysis will say that a Move only stores 32 bits into the destination,
1189                 // if the source only had 32 bits worth of non-zero bits. Same for the source: it will
1190                 // only claim to read 32 bits from the source if only 32 bits of the destination are
1191                 // read. Note that we only apply this logic if this turns into a load or store, since
1192                 // Move is the canonical way to move data between GPRs.
1193                 bool forceMove32IfDidSpill = false;
1194                 bool didSpill = false;
1195                 if (type == Arg::GP && inst.opcode == Move) {
1196                     if ((inst.args[0].isTmp() && m_tmpWidth.width(inst.args[0].tmp()) <= Arg::Width32)
1197                         || (inst.args[1].isTmp() && m_tmpWidth.width(inst.args[1].tmp()) <= Arg::Width32))
1198                         forceMove32IfDidSpill = true;
1199                 }
1200
1201                 // Try to replace the register use by memory use when possible.
1202                 for (unsigned i = 0; i < inst.args.size(); ++i) {
1203                     Arg& arg = inst.args[i];
1204                     if (arg.isTmp() && arg.type() == type && !arg.isReg()) {
1205                         auto stackSlotEntry = stackSlots.find(arg.tmp());
1206                         if (stackSlotEntry != stackSlots.end() && inst.admitsStack(i)) {
1207                             arg = Arg::stack(stackSlotEntry->value);
1208                             didSpill = true;
1209                         }
1210                     }
1211                 }
1212
1213                 if (didSpill && forceMove32IfDidSpill)
1214                     inst.opcode = Move32;
1215
1216                 // For every other case, add Load/Store as needed.
1217                 inst.forEachTmp([&] (Tmp& tmp, Arg::Role role, Arg::Type argType, Arg::Width) {
1218                     if (tmp.isReg() || argType != type)
1219                         return;
1220
1221                     auto stackSlotEntry = stackSlots.find(tmp);
1222                     if (stackSlotEntry == stackSlots.end()) {
1223                         Tmp alias = allocator.getAliasWhenSpilling(tmp);
1224                         if (alias != tmp) {
1225                             tmp = alias;
1226                             hasAliasedTmps = true;
1227                         }
1228                         return;
1229                     }
1230
1231                     Arg arg = Arg::stack(stackSlotEntry->value);
1232                     Opcode move = Oops;
1233                     switch (stackSlotEntry->value->byteSize()) {
1234                     case 4:
1235                         move = type == Arg::GP ? Move32 : MoveFloat;
1236                         break;
1237                     case 8:
1238                         move = type == Arg::GP ? Move : MoveDouble;
1239                         break;
1240                     default:
1241                         RELEASE_ASSERT_NOT_REACHED();
1242                         break;
1243                     }
1244
1245                     if (Arg::isAnyUse(role)) {
1246                         Tmp newTmp = m_code.newTmp(type);
1247                         insertionSet.insert(instIndex, move, inst.origin, arg, newTmp);
1248                         tmp = newTmp;
1249
1250                         // Any new Fill() should never be spilled.
1251                         unspillableTmps.add(AbsoluteTmpMapper<type>::absoluteIndex(tmp));
1252                     }
1253                     if (Arg::isDef(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)