ed67d1c7cd89db08c0f98cf1f663a1f5abc52e3d
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirAllocateStackByGraphColoring.cpp
1 /*
2  * Copyright (C) 2015-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 "AirAllocateStackByGraphColoring.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirArgInlines.h"
32 #include "AirCode.h"
33 #include "AirHandleCalleeSaves.h"
34 #include "AirInstInlines.h"
35 #include "AirLiveness.h"
36 #include "AirPhaseScope.h"
37 #include "AirStackAllocation.h"
38 #include "StackAlignment.h"
39 #include <wtf/ListDump.h>
40
41 namespace JSC { namespace B3 { namespace Air {
42
43 namespace {
44
45 namespace AirAllocateStackByGraphColoringInternal {
46 static const bool verbose = false;
47 }
48
49 struct CoalescableMove {
50     CoalescableMove()
51     {
52     }
53
54     CoalescableMove(StackSlot* src, StackSlot* dst, double frequency)
55         : src(src)
56         , dst(dst)
57         , frequency(frequency)
58     {
59     }
60     
61     bool operator==(const CoalescableMove& other) const
62     {
63         return src == other.src
64             && dst == other.dst
65             && frequency == other.frequency;
66     }
67     
68     bool operator!=(const CoalescableMove& other) const
69     {
70         return !(*this == other);
71     }
72     
73     explicit operator bool() const
74     {
75         return *this != CoalescableMove();
76     }
77     
78     void dump(PrintStream& out) const
79     {
80         out.print(pointerDump(src), "->", pointerDump(dst), "(", frequency, ")");
81     }
82     
83     StackSlot* src { nullptr };
84     StackSlot* dst { nullptr };
85     double frequency { PNaN };
86 };
87
88 } // anonymous namespace
89
90 void allocateStackByGraphColoring(Code& code)
91 {
92     PhaseScope phaseScope(code, "allocateStackByGraphColoring");
93     
94     handleCalleeSaves(code);
95     
96     Vector<StackSlot*> assignedEscapedStackSlots =
97         allocateAndGetEscapedStackSlotsWithoutChangingFrameSize(code);
98
99     // Now we handle the spill slots.
100     StackSlotLiveness liveness(code);
101     IndexMap<StackSlot*, HashSet<StackSlot*>> interference(code.stackSlots().size());
102     Vector<StackSlot*> slots;
103
104     // We will perform some spill coalescing. To make that effective, we need to be able to identify
105     // coalescable moves and handle them specially in interference analysis.
106     auto isCoalescableMove = [&] (Inst& inst) -> bool {
107         Width width;
108         switch (inst.kind.opcode) {
109         case Move:
110             width = pointerWidth();
111             break;
112         case Move32:
113         case MoveFloat:
114             width = Width32;
115             break;
116         case MoveDouble:
117             width = Width64;
118             break;
119         default:
120             return false;
121         }
122         
123         if (!Options::coalesceSpillSlots())
124             return false;
125         
126         if (inst.args.size() != 3)
127             return false;
128         
129         for (unsigned i = 0; i < 2; ++i) {
130             Arg arg = inst.args[i];
131             if (!arg.isStack())
132                 return false;
133             StackSlot* slot = arg.stackSlot();
134             if (slot->kind() != StackSlotKind::Spill)
135                 return false;
136             if (slot->byteSize() != bytes(width))
137                 return false;
138         }
139         
140         return true;
141     };
142     
143     auto isUselessMove = [&] (Inst& inst) -> bool {
144         return isCoalescableMove(inst) && inst.args[0] == inst.args[1];
145     };
146     
147     auto addEdge = [&] (StackSlot* a, StackSlot* b) {
148         interference[a].add(b);
149         interference[b].add(a);
150     };
151     
152     Vector<CoalescableMove> coalescableMoves;
153
154     for (BasicBlock* block : code) {
155         StackSlotLiveness::LocalCalc localCalc(liveness, block);
156
157         auto interfere = [&] (unsigned instIndex) {
158             if (AirAllocateStackByGraphColoringInternal::verbose)
159                 dataLog("Interfering: ", WTF::pointerListDump(localCalc.live()), "\n");
160
161             Inst* prevInst = block->get(instIndex);
162             Inst* nextInst = block->get(instIndex + 1);
163             if (prevInst && isCoalescableMove(*prevInst)) {
164                 CoalescableMove move(prevInst->args[0].stackSlot(), prevInst->args[1].stackSlot(), block->frequency());
165                 
166                 coalescableMoves.append(move);
167                 
168                 for (StackSlot* otherSlot : localCalc.live()) {
169                     if (otherSlot != move.src)
170                         addEdge(move.dst, otherSlot);
171                 }
172                 
173                 prevInst = nullptr;
174             }
175             Inst::forEachDef<Arg>(
176                 prevInst, nextInst,
177                 [&] (Arg& arg, Arg::Role, Bank, Width) {
178                     if (!arg.isStack())
179                         return;
180                     StackSlot* slot = arg.stackSlot();
181                     if (slot->kind() != StackSlotKind::Spill)
182                         return;
183
184                     for (StackSlot* otherSlot : localCalc.live())
185                         addEdge(slot, otherSlot);
186                 });
187         };
188
189         for (unsigned instIndex = block->size(); instIndex--;) {
190             if (AirAllocateStackByGraphColoringInternal::verbose)
191                 dataLog("Analyzing: ", block->at(instIndex), "\n");
192
193             // Kill dead stores. For simplicity we say that a store is killable if it has only late
194             // defs and those late defs are to things that are dead right now. We only do that
195             // because that's the only kind of dead stack store we will see here.
196             Inst& inst = block->at(instIndex);
197             if (!inst.hasNonArgEffects()) {
198                 bool ok = true;
199                 inst.forEachArg(
200                     [&] (Arg& arg, Arg::Role role, Bank, Width) {
201                         if (Arg::isEarlyDef(role)) {
202                             ok = false;
203                             return;
204                         }
205                         if (!Arg::isLateDef(role))
206                             return;
207                         if (!arg.isStack()) {
208                             ok = false;
209                             return;
210                         }
211                         StackSlot* slot = arg.stackSlot();
212                         if (slot->kind() != StackSlotKind::Spill) {
213                             ok = false;
214                             return;
215                         }
216
217                         if (localCalc.isLive(slot)) {
218                             ok = false;
219                             return;
220                         }
221                     });
222                 if (ok)
223                     inst = Inst();
224             }
225             
226             interfere(instIndex);
227             localCalc.execute(instIndex);
228         }
229         interfere(-1);
230         
231         block->insts().removeAllMatching(
232             [&] (const Inst& inst) -> bool {
233                 return !inst;
234             });
235     }
236
237     if (AirAllocateStackByGraphColoringInternal::verbose) {
238         for (StackSlot* slot : code.stackSlots())
239             dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n");
240     }
241     
242     // Now try to coalesce some moves.
243     std::sort(
244         coalescableMoves.begin(), coalescableMoves.end(),
245         [&] (CoalescableMove& a, CoalescableMove& b) -> bool {
246             return a.frequency > b.frequency;
247         });
248     
249     IndexMap<StackSlot*, StackSlot*> remappedStackSlots(code.stackSlots().size());
250     auto remap = [&] (StackSlot* slot) -> StackSlot* {
251         if (!slot)
252             return nullptr;
253         for (;;) {
254             StackSlot* remappedSlot = remappedStackSlots[slot];
255             if (!remappedSlot)
256                 return slot;
257             slot = remappedSlot;
258         }
259     };
260     
261     for (CoalescableMove& move : coalescableMoves) {
262         move.src = remap(move.src);
263         move.dst = remap(move.dst);
264         if (move.src == move.dst)
265             continue;
266         if (interference[move.src].contains(move.dst))
267             continue;
268         
269         StackSlot* slotToKill = move.src;
270         StackSlot* slotToKeep = move.dst;
271         
272         remappedStackSlots[slotToKill] = slotToKeep;
273         for (StackSlot* interferingSlot : interference[slotToKill]) {
274             if (interferingSlot == slotToKill)
275                 continue;
276             interference[interferingSlot].remove(slotToKill);
277             interference[interferingSlot].add(slotToKeep);
278         }
279         interference[slotToKeep].add(interference[slotToKill].begin(), interference[slotToKill].end());
280         interference[slotToKill].clear();
281     }
282     
283     for (BasicBlock* block : code) {
284         for (Inst& inst : *block) {
285             for (Arg& arg : inst.args) {
286                 if (arg.isStack())
287                     arg = Arg::stack(remap(arg.stackSlot()), arg.offset());
288             }
289             if (isUselessMove(inst))
290                 inst = Inst();
291         }
292     }
293     
294     // Now we assign stack locations. At its heart this algorithm is just first-fit. For each
295     // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no
296     // overlap with other StackSlots that this overlaps with.
297     Vector<StackSlot*> otherSlots = assignedEscapedStackSlots;
298     for (StackSlot* slot : code.stackSlots()) {
299         if (remappedStackSlots[slot])
300             continue;
301         
302         if (slot->offsetFromFP()) {
303             // Already assigned an offset.
304             continue;
305         }
306
307         HashSet<StackSlot*>& interferingSlots = interference[slot];
308         otherSlots.resize(assignedEscapedStackSlots.size());
309         otherSlots.resize(assignedEscapedStackSlots.size() + interferingSlots.size());
310         unsigned nextIndex = assignedEscapedStackSlots.size();
311         for (StackSlot* otherSlot : interferingSlots)
312             otherSlots[nextIndex++] = otherSlot;
313
314         assign(slot, otherSlots);
315     }
316
317     updateFrameSizeBasedOnStackSlots(code);
318     code.setStackIsAllocated(true);
319 }
320
321 } } } // namespace JSC::B3::Air
322
323 #endif // ENABLE(B3_JIT)
324