canvas/2d.gradient.* LayoutTests failing
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirAllocateRegistersAndStackByLinearScan.cpp
1 /*
2  * Copyright (C) 2017 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 "AirAllocateRegistersAndStackByLinearScan.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirAllocateStackByGraphColoring.h"
32 #include "AirArgInlines.h"
33 #include "AirCode.h"
34 #include "AirFixSpillsAfterTerminals.h"
35 #include "AirHandleCalleeSaves.h"
36 #include "AirPhaseInsertionSet.h"
37 #include "AirInstInlines.h"
38 #include "AirLiveness.h"
39 #include "AirPadInterference.h"
40 #include "AirPhaseScope.h"
41 #include "AirRegLiveness.h"
42 #include "AirTmpInlines.h"
43 #include "AirTmpMap.h"
44 #include <wtf/ListDump.h>
45 #include <wtf/Range.h>
46
47 namespace JSC { namespace B3 { namespace Air {
48
49 namespace {
50
51 NO_RETURN_DUE_TO_CRASH NEVER_INLINE void crash()
52 {
53     CRASH();
54 }
55
56 #undef RELEASE_ASSERT
57 #define RELEASE_ASSERT(assertion) do { \
58     if (!(assertion)) { \
59         WTFReportAssertionFailure(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, #assertion); \
60         crash(); \
61     } \
62 } while (0)
63
64 bool verbose() { return Options::airLinearScanVerbose(); }
65
66 // Phase constants we use for the PhaseInsertionSet.
67 const unsigned firstPhase = 0;
68 const unsigned secondPhase = 1;
69
70 typedef Range<size_t> Interval;
71
72 struct TmpData {
73     void dump(PrintStream& out) const
74     {
75         out.print("{interval = ", interval, ", spilled = ", pointerDump(spilled), ", assigned = ", assigned, ", isUnspillable = ", isUnspillable, ", possibleRegs = ", possibleRegs, ", didBuildPossibleRegs = ", didBuildPossibleRegs, "}");
76     }
77     
78     void validate()
79     {
80         RELEASE_ASSERT(!(spilled && assigned));
81     }
82     
83     Interval interval;
84     StackSlot* spilled { nullptr };
85     RegisterSet possibleRegs;
86     Reg assigned;
87     bool isUnspillable { false };
88     bool didBuildPossibleRegs { false };
89     unsigned spillIndex { 0 };
90 };
91
92 struct Clobber {
93     Clobber()
94     {
95     }
96     
97     Clobber(size_t index, RegisterSet regs)
98         : index(index)
99         , regs(regs)
100     {
101     }
102     
103     void dump(PrintStream& out) const
104     {
105         out.print(index, ":", regs);
106     }
107     
108     size_t index { 0 };
109     RegisterSet regs;
110 };
111
112 class LinearScan {
113 public:
114     LinearScan(Code& code)
115         : m_code(code)
116         , m_startIndex(code.size())
117         , m_map(code)
118         , m_insertionSets(code.size())
119     {
120     }
121     
122     void run()
123     {
124         padInterference(m_code);
125         buildRegisterSet();
126         buildIndices();
127         buildIntervals();
128         if (shouldSpillEverything()) {
129             spillEverything();
130             emitSpillCode();
131         }
132         for (;;) {
133             prepareIntervalsForScanForRegisters();
134             m_didSpill = false;
135             forEachBank(
136                 [&] (Bank bank) {
137                     attemptScanForRegisters(bank);
138                 });
139             if (!m_didSpill)
140                 break;
141             emitSpillCode();
142         }
143         insertSpillCode();
144         assignRegisters();
145         fixSpillsAfterTerminals(m_code);
146
147         handleCalleeSaves(m_code);
148         allocateEscapedStackSlots(m_code);
149         prepareIntervalsForScanForStack();
150         scanForStack();
151         updateFrameSizeBasedOnStackSlots(m_code);
152         m_code.setStackIsAllocated(true);
153     }
154     
155 private:
156     void buildRegisterSet()
157     {
158         forEachBank(
159             [&] (Bank bank) {
160                 m_registers[bank] = m_code.regsInPriorityOrder(bank);
161                 m_registerSet[bank].setAll(m_registers[bank]);
162                 m_unifiedRegisterSet.merge(m_registerSet[bank]);
163             });
164     }
165
166     void buildIndices()
167     {
168         size_t index = 0;
169         for (BasicBlock* block : m_code) {
170             m_startIndex[block] = index;
171             index += block->size() * 2;
172         }
173     }
174     
175     size_t indexOfHead(BasicBlock* block)
176     {
177         return m_startIndex[block];
178     }
179     
180     size_t indexOfTail(BasicBlock* block)
181     {
182         return indexOfHead(block) + block->size() * 2;
183     }
184     
185     Interval interval(size_t indexOfEarly, Arg::Timing timing)
186     {
187         switch (timing) {
188         case Arg::OnlyEarly:
189             return Interval(indexOfEarly);
190         case Arg::OnlyLate:
191             return Interval(indexOfEarly + 1);
192         case Arg::EarlyAndLate:
193             return Interval(indexOfEarly, indexOfEarly + 2);
194         }
195         ASSERT_NOT_REACHED();
196         return Interval();
197     }
198     
199     void buildIntervals()
200     {
201         TimingScope timingScope("LinearScan::buildIntervals");
202         UnifiedTmpLiveness liveness(m_code);
203         
204         for (BasicBlock* block : m_code) {
205             size_t indexOfHead = this->indexOfHead(block);
206             size_t indexOfTail = this->indexOfTail(block);
207             if (verbose()) {
208                 dataLog("At block ", pointerDump(block), "\n");
209                 dataLog("  indexOfHead = ", indexOfHead, "\n");
210                 dataLog("  idnexOfTail = ", indexOfTail, "\n");
211             }
212             for (Tmp tmp : liveness.liveAtHead(block)) {
213                 if (!tmp.isReg())
214                     m_map[tmp].interval |= Interval(indexOfHead);
215             }
216             for (Tmp tmp : liveness.liveAtTail(block)) {
217                 if (!tmp.isReg())
218                     m_map[tmp].interval |= Interval(indexOfTail);
219             }
220             
221             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
222                 Inst& inst = block->at(instIndex);
223                 size_t indexOfEarly = indexOfHead + instIndex * 2;
224                 inst.forEachTmp(
225                     [&] (Tmp& tmp, Arg::Role role, Bank, Width) {
226                         if (tmp.isReg())
227                             return;
228                         m_map[tmp].interval |= interval(indexOfEarly, Arg::timing(role));
229                     });
230             }
231
232             RegLiveness::LocalCalc localCalc(liveness, block);
233             
234             auto record = [&] (unsigned instIndex) {
235                 RegisterSet regs = localCalc.live();
236                 if (Inst* prev = block->get(instIndex - 1)) {
237                     RegisterSet prevRegs = regs;
238                     prev->forEach<Reg>(
239                         [&] (Reg& reg, Arg::Role role, Bank, Width) {
240                             if (Arg::isLateDef(role))
241                                 prevRegs.add(reg);
242                         });
243                     if (prev->kind.opcode == Patch)
244                         prevRegs.merge(prev->extraClobberedRegs());
245                     prevRegs.filter(m_unifiedRegisterSet);
246                     if (!prevRegs.isEmpty())
247                         m_clobbers.append(Clobber(indexOfHead + instIndex * 2 - 1, prevRegs));
248                 }
249                 if (Inst* next = block->get(instIndex)) {
250                     RegisterSet nextRegs = regs;
251                     next->forEach<Reg>(
252                         [&] (Reg& reg, Arg::Role role, Bank, Width) {
253                             if (Arg::isEarlyDef(role))
254                                 nextRegs.add(reg);
255                         });
256                     if (next->kind.opcode == Patch)
257                         nextRegs.merge(next->extraEarlyClobberedRegs());
258                     if (!nextRegs.isEmpty())
259                         m_clobbers.append(Clobber(indexOfHead + instIndex * 2, nextRegs));
260                 }
261             };
262             
263             record(block->size());
264             for (unsigned instIndex = block->size(); instIndex--;) {
265                 localCalc.execute(instIndex);
266                 record(instIndex);
267             }
268         }
269         
270         std::sort(
271             m_clobbers.begin(), m_clobbers.end(),
272             [] (Clobber& a, Clobber& b) -> bool {
273                 return a.index < b.index;
274             });
275         
276         if (verbose()) {
277             dataLog("Intervals:\n");
278             m_code.forEachTmp(
279                 [&] (Tmp tmp) {
280                     dataLog("    ", tmp, ": ", m_map[tmp], "\n");
281                 });
282             dataLog("Clobbers: ", listDump(m_clobbers), "\n");
283         }
284     }
285     
286     bool shouldSpillEverything()
287     {
288         if (!Options::airLinearScanSpillsEverything())
289             return false;
290         
291         // You're meant to hack this so that you selectively spill everything depending on reasons.
292         // That's super useful for debugging.
293
294         return true;
295     }
296     
297     void spillEverything()
298     {
299         m_code.forEachTmp(
300             [&] (Tmp tmp) {
301                 spill(tmp);
302             });
303     }
304     
305     void prepareIntervalsForScanForRegisters()
306     {
307         prepareIntervals(
308             [&] (TmpData& data) -> bool {
309                 if (data.spilled)
310                     return false;
311                 
312                 data.assigned = Reg();
313                 return true;
314             });
315     }
316     
317     void prepareIntervalsForScanForStack()
318     {
319         prepareIntervals(
320             [&] (TmpData& data) -> bool {
321                 return data.spilled;
322             });
323     }
324     
325     template<typename SelectFunc>
326     void prepareIntervals(const SelectFunc& selectFunc)
327     {
328         m_tmps.resize(0);
329         
330         m_code.forEachTmp(
331             [&] (Tmp tmp) {
332                 TmpData& data = m_map[tmp];
333                 if (!selectFunc(data))
334                     return;
335                 
336                 m_tmps.append(tmp);
337             });
338         
339         std::sort(
340             m_tmps.begin(), m_tmps.end(),
341             [&] (Tmp& a, Tmp& b) {
342                 return m_map[a].interval.begin() < m_map[b].interval.begin();
343             });
344         
345         if (verbose())
346             dataLog("Tmps: ", listDump(m_tmps), "\n");
347     }
348     
349     Tmp addSpillTmpWithInterval(Bank bank, Interval interval)
350     {
351         TmpData data;
352         data.interval = interval;
353         data.isUnspillable = true;
354         
355         Tmp tmp = m_code.newTmp(bank);
356         m_map.append(tmp, data);
357         return tmp;
358     }
359     
360     void attemptScanForRegisters(Bank bank)
361     {
362         // This is modeled after LinearScanRegisterAllocation in Fig. 1 in
363         // http://dl.acm.org/citation.cfm?id=330250.
364
365         m_active.clear();
366         m_activeRegs = RegisterSet();
367         
368         size_t clobberIndex = 0;
369         for (Tmp& tmp : m_tmps) {
370             if (tmp.bank() != bank)
371                 continue;
372             
373             TmpData& entry = m_map[tmp];
374             size_t index = entry.interval.begin();
375             
376             if (verbose()) {
377                 dataLog("Index #", index, ": ", tmp, "\n");
378                 dataLog("  ", tmp, ": ", entry, "\n");
379                 dataLog("  clobberIndex = ", clobberIndex, "\n");
380                 // This could be so much faster.
381                 BasicBlock* block = m_code[0];
382                 for (BasicBlock* candidateBlock : m_code) {
383                     if (m_startIndex[candidateBlock] > index)
384                         break;
385                     block = candidateBlock;
386                 }
387                 unsigned instIndex = (index - m_startIndex[block] + 1) / 2;
388                 dataLog("  At: ", pointerDump(block), ", instIndex = ", instIndex, "\n");
389                 dataLog("    Prev: ", pointerDump(block->get(instIndex - 1)), "\n");
390                 dataLog("    Next: ", pointerDump(block->get(instIndex)), "\n");
391                 dataLog("  Active:\n");
392                 for (Tmp tmp : m_active)
393                     dataLog("    ", tmp, ": ", m_map[tmp], "\n");
394             }
395             
396             // This is ExpireOldIntervals in Fig. 1.
397             while (!m_active.isEmpty()) {
398                 Tmp tmp = m_active.first();
399                 TmpData& entry = m_map[tmp];
400                 
401                 bool expired = entry.interval.end() <= index;
402                 
403                 if (!expired)
404                     break;
405                 
406                 m_active.removeFirst();
407                 m_activeRegs.remove(entry.assigned);
408             }
409
410             // If necessary, compute the set of registers that this tmp could even use. This is not
411             // part of Fig. 1, but it's a technique that the authors claim to have implemented in one of
412             // their two implementations. There may be other more efficient ways to do this, but this
413             // implementation gets some perf wins from piggy-backing this calculation in the scan.
414             //
415             // Note that the didBuild flag sticks through spilling. Spilling doesn't change the
416             // interference situation.
417             //
418             // Note that we could short-circuit this if we're dealing with a spillable tmp, there are no
419             // free registers, and this register's interval ends after the one on the top of the active
420             // stack.
421             if (!entry.didBuildPossibleRegs) {
422                 // Advance the clobber index until it's at a clobber that is relevant to us.
423                 while (clobberIndex < m_clobbers.size() && m_clobbers[clobberIndex].index < index)
424                     clobberIndex++;
425                 
426                 RegisterSet possibleRegs = m_registerSet[bank];
427                 for (size_t i = clobberIndex; i < m_clobbers.size() && m_clobbers[i].index < entry.interval.end(); ++i)
428                     possibleRegs.exclude(m_clobbers[i].regs);
429                 
430                 entry.possibleRegs = possibleRegs;
431                 entry.didBuildPossibleRegs = true;
432             }
433             
434             if (verbose())
435                 dataLog("  Possible regs: ", entry.possibleRegs, "\n");
436             
437             // Find a free register that we are allowed to use.
438             if (m_active.size() != m_registers[bank].size()) {
439                 bool didAssign = false;
440                 for (Reg reg : m_registers[bank]) {
441                     // FIXME: Could do priority coloring here.
442                     // https://bugs.webkit.org/show_bug.cgi?id=170304
443                     if (!m_activeRegs.contains(reg) && entry.possibleRegs.contains(reg)) {
444                         assign(tmp, reg);
445                         didAssign = true;
446                         break;
447                     }
448                 }
449                 if (didAssign)
450                     continue;
451             }
452             
453             // This is SpillAtInterval in Fig. 1, but modified to handle clobbers.
454             Tmp spillTmp = m_active.takeLast(
455                 [&] (Tmp spillCandidate) -> bool {
456                     return entry.possibleRegs.contains(m_map[spillCandidate].assigned);
457                 });
458             if (!spillTmp) {
459                 spill(tmp);
460                 continue;
461             }
462             TmpData& spillEntry = m_map[spillTmp];
463             RELEASE_ASSERT(spillEntry.assigned);
464             if (spillEntry.isUnspillable ||
465                 (!entry.isUnspillable && spillEntry.interval.end() <= entry.interval.end())) {
466                 spill(tmp);
467                 addToActive(spillTmp);
468                 continue;
469             }
470             
471             assign(tmp, spillEntry.assigned);
472             spill(spillTmp);
473         }
474     }
475     
476     void addToActive(Tmp tmp)
477     {
478         if (m_map[tmp].isUnspillable) {
479             m_active.prepend(tmp);
480             return;
481         }
482         
483         m_active.appendAndBubble(
484             tmp,
485             [&] (Tmp otherTmp) -> bool {
486                 TmpData& otherEntry = m_map[otherTmp];
487                 if (otherEntry.isUnspillable)
488                     return false;
489                 return m_map[otherTmp].interval.end() > m_map[tmp].interval.end();
490             });
491     }
492     
493     void assign(Tmp tmp, Reg reg)
494     {
495         TmpData& entry = m_map[tmp];
496         RELEASE_ASSERT(!entry.spilled);
497         entry.assigned = reg;
498         m_activeRegs.add(reg);
499         addToActive(tmp);
500     }
501     
502     void spill(Tmp tmp)
503     {
504         TmpData& entry = m_map[tmp];
505         RELEASE_ASSERT(!entry.isUnspillable);
506         entry.spilled = m_code.addStackSlot(8, StackSlotKind::Spill);
507         entry.assigned = Reg();
508         m_didSpill = true;
509     }
510     
511     void emitSpillCode()
512     {
513         for (BasicBlock* block : m_code) {
514             size_t indexOfHead = this->indexOfHead(block);
515             for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
516                 Inst& inst = block->at(instIndex);
517                 unsigned indexOfEarly = indexOfHead + instIndex * 2;
518                 
519                 // First try to spill directly.
520                 for (unsigned i = 0; i < inst.args.size(); ++i) {
521                     Arg& arg = inst.args[i];
522                     if (!arg.isTmp())
523                         continue;
524                     if (arg.isReg())
525                         continue;
526                     StackSlot* spilled = m_map[arg.tmp()].spilled;
527                     if (!spilled)
528                         continue;
529                     if (!inst.admitsStack(i))
530                         continue;
531                     arg = Arg::stack(spilled);
532                 }
533                 
534                 // Fall back on the hard way.
535                 inst.forEachTmp(
536                     [&] (Tmp& tmp, Arg::Role role, Bank bank, Width) {
537                         if (tmp.isReg())
538                             return;
539                         StackSlot* spilled = m_map[tmp].spilled;
540                         if (!spilled)
541                             return;
542                         Opcode move = bank == GP ? Move : MoveDouble;
543                         tmp = addSpillTmpWithInterval(bank, interval(indexOfEarly, Arg::timing(role)));
544                         if (role == Arg::Scratch)
545                             return;
546                         if (Arg::isAnyUse(role))
547                             m_insertionSets[block].insert(instIndex, secondPhase, move, inst.origin, Arg::stack(spilled), tmp);
548                         if (Arg::isAnyDef(role))
549                             m_insertionSets[block].insert(instIndex + 1, firstPhase, move, inst.origin, tmp, Arg::stack(spilled));
550                     });
551             }
552         }
553     }
554     
555     void scanForStack()
556     {
557         // This is loosely modeled after LinearScanRegisterAllocation in Fig. 1 in
558         // http://dl.acm.org/citation.cfm?id=330250.
559
560         m_active.clear();
561         m_usedSpillSlots.clearAll();
562         
563         for (Tmp& tmp : m_tmps) {
564             TmpData& entry = m_map[tmp];
565             if (!entry.spilled)
566                 continue;
567             
568             size_t index = entry.interval.begin();
569             
570             // This is ExpireOldIntervals in Fig. 1.
571             while (!m_active.isEmpty()) {
572                 Tmp tmp = m_active.first();
573                 TmpData& entry = m_map[tmp];
574                 
575                 bool expired = entry.interval.end() <= index;
576                 
577                 if (!expired)
578                     break;
579                 
580                 m_active.removeFirst();
581                 m_usedSpillSlots.clear(entry.spillIndex);
582             }
583             
584             entry.spillIndex = m_usedSpillSlots.findBit(0, false);
585             ptrdiff_t offset = -static_cast<ptrdiff_t>(m_code.frameSize()) - static_cast<ptrdiff_t>(entry.spillIndex) * 8 - 8;
586             if (verbose())
587                 dataLog("  Assigning offset = ", offset, " to spill ", pointerDump(entry.spilled), " for ", tmp, "\n");
588             entry.spilled->setOffsetFromFP(offset);
589             m_usedSpillSlots.set(entry.spillIndex);
590             m_active.append(tmp);
591         }
592     }
593     
594     void insertSpillCode()
595     {
596         for (BasicBlock* block : m_code)
597             m_insertionSets[block].execute(block);
598     }
599     
600     void assignRegisters()
601     {
602         if (verbose()) {
603             dataLog("About to allocate registers. State of all tmps:\n");
604             m_code.forEachTmp(
605                 [&] (Tmp tmp) {
606                     dataLog("    ", tmp, ": ", m_map[tmp], "\n");
607                 });
608             dataLog("IR:\n");
609             dataLog(m_code);
610         }
611         
612         for (BasicBlock* block : m_code) {
613             for (Inst& inst : *block) {
614                 if (verbose())
615                     dataLog("At: ", inst, "\n");
616                 inst.forEachTmpFast(
617                     [&] (Tmp& tmp) {
618                         if (tmp.isReg())
619                             return;
620                         
621                         Reg reg = m_map[tmp].assigned;
622                         if (!reg) {
623                             dataLog("Failed to allocate reg for: ", tmp, "\n");
624                             RELEASE_ASSERT_NOT_REACHED();
625                         }
626                         tmp = Tmp(reg);
627                     });
628             }
629         }
630     }
631     
632     Code& m_code;
633     Vector<Reg> m_registers[numBanks];
634     RegisterSet m_registerSet[numBanks];
635     RegisterSet m_unifiedRegisterSet;
636     IndexMap<BasicBlock*, size_t> m_startIndex;
637     TmpMap<TmpData> m_map;
638     IndexMap<BasicBlock*, PhaseInsertionSet> m_insertionSets;
639     Vector<Clobber> m_clobbers; // After we allocate this, we happily point pointers into it.
640     Vector<Tmp> m_tmps;
641     Deque<Tmp> m_active;
642     RegisterSet m_activeRegs;
643     BitVector m_usedSpillSlots;
644     bool m_didSpill { false };
645 };
646
647 } // anonymous namespace
648
649 void allocateRegistersAndStackByLinearScan(Code& code)
650 {
651     PhaseScope phaseScope(code, "allocateRegistersAndStackByLinearScan");
652     if (verbose())
653         dataLog("Air before linear scan:\n", code);
654     LinearScan linearScan(code);
655     linearScan.run();
656     if (verbose())
657         dataLog("Air after linear scan:\n", code);
658 }
659
660 } } } // namespace JSC::B3::Air
661
662 #endif // ENABLE(B3_JIT)