Air needs a late register liveness phase that calls Special::reportUsedRegisters()
[WebKit-https.git] / Source / JavaScriptCore / b3 / air / AirAllocateStack.cpp
1 /*
2  * Copyright (C) 2015 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 "AirAllocateStack.h"
28
29 #if ENABLE(B3_JIT)
30
31 #include "AirCode.h"
32 #include "AirInstInlines.h"
33 #include "AirLiveness.h"
34 #include "AirPhaseScope.h"
35 #include "StackAlignment.h"
36 #include <wtf/ListDump.h>
37
38 namespace JSC { namespace B3 { namespace Air {
39
40 namespace {
41
42 const bool verbose = false;
43
44 bool argumentIsOnStack(const Arg& arg)
45 {
46     return arg.isStack() && arg.stackSlot()->kind() == StackSlotKind::Anonymous;
47 }
48
49 bool attemptAssignment(
50     StackSlot* slot, intptr_t offsetFromFP, const Vector<StackSlot*>& otherSlots)
51 {
52     if (verbose)
53         dataLog("Attempting to assign ", pointerDump(slot), " to ", offsetFromFP, " with interference ", pointerListDump(otherSlots), "\n");
54
55     // Need to align it to the slot's desired alignment.
56     offsetFromFP = -WTF::roundUpToMultipleOf(slot->alignment(), -offsetFromFP);
57     
58     for (StackSlot* otherSlot : otherSlots) {
59         if (!otherSlot->offsetFromFP())
60             continue;
61         bool overlap = WTF::rangesOverlap(
62             offsetFromFP,
63             offsetFromFP + static_cast<intptr_t>(slot->byteSize()),
64             otherSlot->offsetFromFP(),
65             otherSlot->offsetFromFP() + static_cast<intptr_t>(otherSlot->byteSize()));
66         if (overlap)
67             return false;
68     }
69
70     if (verbose)
71         dataLog("Assigned ", pointerDump(slot), " to ", offsetFromFP, "\n");
72     slot->setOffsetFromFP(offsetFromFP);
73     return true;
74 }
75
76 void assign(StackSlot* slot, const Vector<StackSlot*>& otherSlots)
77 {
78     if (verbose)
79         dataLog("Attempting to assign ", pointerDump(slot), " with interference ", pointerListDump(otherSlots), "\n");
80     
81     if (attemptAssignment(slot, -static_cast<intptr_t>(slot->byteSize()), otherSlots))
82         return;
83
84     for (StackSlot* otherSlot : otherSlots) {
85         if (!otherSlot->offsetFromFP())
86             continue;
87         bool didAssign = attemptAssignment(
88             slot, otherSlot->offsetFromFP() - static_cast<intptr_t>(slot->byteSize()), otherSlots);
89         if (didAssign)
90             return;
91     }
92
93     RELEASE_ASSERT_NOT_REACHED();
94 }
95
96 } // anonymous namespace
97
98 void allocateStack(Code& code)
99 {
100     PhaseScope phaseScope(code, "allocateStack");
101
102     // Perform an escape analysis over stack slots. An escaping stack slot is one that is locked or
103     // is explicitly escaped in the code.
104     IndexSet<StackSlot> escapingStackSlots;
105     for (StackSlot* slot : code.stackSlots()) {
106         if (slot->isLocked())
107             escapingStackSlots.add(slot);
108     }
109     for (BasicBlock* block : code) {
110         for (Inst& inst : *block) {
111             inst.forEachArg(
112                 [&] (Arg& arg, Arg::Role role, Arg::Type) {
113                     if (role == Arg::UseAddr && arg.isStack())
114                         escapingStackSlots.add(arg.stackSlot());
115                 });
116         }
117     }
118
119     // Allocate all of the escaped slots in order. This is kind of a crazy algorithm to allow for
120     // the possibility of stack slots being assigned frame offsets before we even get here.
121     ASSERT(!code.frameSize());
122     Vector<StackSlot*> assignedEscapedStackSlots;
123     Vector<StackSlot*> escapedStackSlotsWorklist;
124     for (StackSlot* slot : code.stackSlots()) {
125         if (escapingStackSlots.contains(slot)) {
126             if (slot->offsetFromFP())
127                 assignedEscapedStackSlots.append(slot);
128             else
129                 escapedStackSlotsWorklist.append(slot);
130         } else {
131             // It would be super strange to have an unlocked stack slot that has an offset already.
132             ASSERT(!slot->offsetFromFP());
133         }
134     }
135     // This is a fairly expensive loop, but it's OK because we'll usually only have a handful of
136     // escaped stack slots.
137     while (!escapedStackSlotsWorklist.isEmpty()) {
138         StackSlot* slot = escapedStackSlotsWorklist.takeLast();
139         assign(slot, assignedEscapedStackSlots);
140         assignedEscapedStackSlots.append(slot);
141     }
142
143     // Now we handle the anonymous slots.
144     // FIXME: We should tell Liveness to only track StackSlots.
145     // https://bugs.webkit.org/show_bug.cgi?id=150751
146     Liveness<Arg> liveness(code);
147     IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size());
148     Vector<StackSlot*> slots;
149
150     for (BasicBlock* block : code) {
151         Liveness<Arg>::LocalCalc localCalc(liveness, block);
152
153         auto interfere = [&] (Inst& inst) {
154             if (verbose)
155                 dataLog("Interfering: ", listDump(localCalc.live()), "\n");
156             
157             // Form a clique of stack slots that interfere. First find the list of stack slots
158             // that are live right now.
159             slots.resize(0);
160             for (Arg arg : localCalc.live()) {
161                 if (argumentIsOnStack(arg))
162                     slots.append(arg.stackSlot());
163             }
164
165             // We mustn't mandate that the input code is optimal. Therefore, it may have dead stores
166             // to the stack. We need to treat these as interfering.
167             inst.forEachArg(
168                 [&] (Arg& arg, Arg::Role role, Arg::Type) {
169                     if (Arg::isDef(role) && argumentIsOnStack(arg)
170                         && !localCalc.live().contains(arg))
171                         slots.append(arg.stackSlot());
172                 });
173             
174             if (verbose)
175                 dataLog("    Slots: ", pointerListDump(slots), "\n");
176             for (unsigned i = 0; i < slots.size(); ++i) {
177                 StackSlot* outer = slots[i];
178                 for (unsigned j = i + 1; j < slots.size(); ++j) {
179                     StackSlot* inner = slots[j];
180
181                     interference[inner].add(outer);
182                     interference[outer].add(inner);
183                 }
184             }
185         };
186
187         for (unsigned instIndex = block->size(); instIndex--;) {
188             if (verbose)
189                 dataLog("Analyzing: ", block->at(instIndex), "\n");
190             Inst& inst = block->at(instIndex);
191             interfere(inst);
192             localCalc.execute(inst);
193         }
194         Inst nop;
195         interfere(nop);
196     }
197
198     if (verbose) {
199         for (StackSlot* slot : code.stackSlots())
200             dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n");
201     }
202
203     // Now we assign stack locations. At its heart this algorithm is just first-fit. For each
204     // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no
205     // overlap with other StackSlots that this overlaps with.
206     Vector<StackSlot*> otherSlots = assignedEscapedStackSlots;
207     for (StackSlot* slot : code.stackSlots()) {
208         if (slot->offsetFromFP()) {
209             // Already assigned an offset.
210             continue;
211         }
212
213         HashSet<StackSlot*>& interferingSlots = interference[slot];
214         otherSlots.resize(assignedEscapedStackSlots.size());
215         otherSlots.resize(assignedEscapedStackSlots.size() + interferingSlots.size());
216         unsigned nextIndex = assignedEscapedStackSlots.size();
217         for (StackSlot* otherSlot : interferingSlots)
218             otherSlots[nextIndex++] = otherSlot;
219
220         assign(slot, otherSlots);
221     }
222
223     // Figure out how much stack we're using for stack slots.
224     unsigned frameSizeForStackSlots = 0;
225     for (StackSlot* slot : code.stackSlots()) {
226         frameSizeForStackSlots = std::max(
227             frameSizeForStackSlots,
228             static_cast<unsigned>(-slot->offsetFromFP()));
229     }
230
231     frameSizeForStackSlots = WTF::roundUpToMultipleOf(stackAlignmentBytes(), frameSizeForStackSlots);
232
233     // Now we need to deduce how much argument area we need.
234     for (BasicBlock* block : code) {
235         for (Inst& inst : *block) {
236             for (Arg& arg : inst.args) {
237                 if (arg.isCallArg()) {
238                     // For now, we assume that we use 8 bytes of the call arg. But that's not
239                     // such an awesome assumption.
240                     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150454
241                     ASSERT(arg.offset() >= 0);
242                     code.requestCallArgAreaSize(arg.offset() + 8);
243                 }
244             }
245         }
246     }
247
248     code.setFrameSize(frameSizeForStackSlots + code.callArgAreaSize());
249
250     // Finally, transform the code to use Addr's instead of StackSlot's. This is a lossless
251     // transformation since we can search the StackSlots array to figure out which StackSlot any
252     // offset-from-FP refers to.
253
254     for (BasicBlock* block : code) {
255         for (Inst& inst : *block) {
256             for (Arg& arg : inst.args) {
257                 switch (arg.kind()) {
258                 case Arg::Stack:
259                     arg = Arg::addr(
260                         Tmp(GPRInfo::callFrameRegister),
261                         arg.offset() + arg.stackSlot()->offsetFromFP());
262                     break;
263                 case Arg::CallArg:
264                     arg = Arg::addr(
265                         Tmp(GPRInfo::callFrameRegister),
266                         arg.offset() - code.frameSize());
267                     break;
268                 default:
269                     break;
270                 }
271             }
272         }
273     }
274 }
275
276 } } } // namespace JSC::B3::Air
277
278 #endif // ENABLE(B3_JIT)
279
280