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