Create a super rough prototype of B3
[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     // Allocate all of the locked slots in order. This is kind of a crazy algorithm to allow for
103     // the possibility of stack slots being assigned frame offsets before we even get here.
104     ASSERT(!code.frameSize());
105     Vector<StackSlot*> assignedLockedStackSlots;
106     Vector<StackSlot*> lockedStackSlotsWorklist;
107     for (StackSlot* slot : code.stackSlots()) {
108         switch (slot->kind()) {
109         case StackSlotKind::Locked:
110             if (slot->offsetFromFP())
111                 assignedLockedStackSlots.append(slot);
112             else
113                 lockedStackSlotsWorklist.append(slot);
114             break;
115         case StackSlotKind::Anonymous:
116             if (slot->offsetFromFP()) {
117                 // As a matter of sanity, unassign this. Maybe it would be good to even have a
118                 // validation rule that this cannot happen.
119                 slot->setOffsetFromFP(0);
120             }
121             break;
122         }
123     }
124     // This is a fairly expensive loop, but it's OK because we'll usually only have a handful of
125     // locked stack slots.
126     while (!lockedStackSlotsWorklist.isEmpty()) {
127         StackSlot* slot = lockedStackSlotsWorklist.takeLast();
128         assign(slot, assignedLockedStackSlots);
129         assignedLockedStackSlots.append(slot);
130     }
131
132     // Now we handle the anonymous slots. Note that theoretically we should do an escape analysis
133     // here. But, currently Air doesn't support escaping a StackSlot!
134     // FIXME: Add support for escaping a StackSlot and add escape analysis to allocateStack().
135     // https://bugs.webkit.org/show_bug.cgi?id=150430
136
137     Liveness<Arg> liveness(code);
138     IndexMap<StackSlot, HashSet<StackSlot*>> interference(code.stackSlots().size());
139     Vector<StackSlot*> slots;
140
141     for (BasicBlock* block : code) {
142         Liveness<Arg>::LocalCalc localCalc(liveness, block);
143
144         auto interfere = [&] (Inst& inst) {
145             if (verbose)
146                 dataLog("Interfering: ", listDump(localCalc.live()), "\n");
147             
148             // Form a clique of stack slots that interfere. First find the list of stack slots
149             // that are live right now.
150             slots.resize(0);
151             for (Arg arg : localCalc.live()) {
152                 if (argumentIsOnStack(arg))
153                     slots.append(arg.stackSlot());
154             }
155
156             // We mustn't mandate that the input code is optimal. Therefore, it may have dead stores
157             // to the stack. We need to treat these as interfering.
158             inst.forEachArg(
159                 [&] (Arg& arg, Arg::Role role, Arg::Type) {
160                     if (Arg::isDef(role) && argumentIsOnStack(arg)
161                         && !localCalc.live().contains(arg))
162                         slots.append(arg.stackSlot());
163                 });
164             
165             if (verbose)
166                 dataLog("    Slots: ", pointerListDump(slots), "\n");
167             for (unsigned i = 0; i < slots.size(); ++i) {
168                 StackSlot* outer = slots[i];
169                 for (unsigned j = i + 1; j < slots.size(); ++j) {
170                     StackSlot* inner = slots[j];
171
172                     interference[inner].add(outer);
173                     interference[outer].add(inner);
174                 }
175             }
176         };
177
178         for (unsigned instIndex = block->size(); instIndex--;) {
179             if (verbose)
180                 dataLog("Analyzing: ", block->at(instIndex), "\n");
181             Inst& inst = block->at(instIndex);
182             interfere(inst);
183             localCalc.execute(inst);
184         }
185         Inst nop;
186         interfere(nop);
187     }
188
189     if (verbose) {
190         for (StackSlot* slot : code.stackSlots())
191             dataLog("Interference of ", pointerDump(slot), ": ", pointerListDump(interference[slot]), "\n");
192     }
193
194     // Now we assign stack locations. At its heart this algorithm is just first-fit. For each
195     // StackSlot we just want to find the offsetFromFP that is closest to zero while ensuring no
196     // overlap with other StackSlots that this overlaps with.
197     Vector<StackSlot*> otherSlots = assignedLockedStackSlots;
198     for (StackSlot* slot : code.stackSlots()) {
199         if (slot->offsetFromFP()) {
200             // Already assigned an offset.
201             continue;
202         }
203
204         HashSet<StackSlot*>& interferingSlots = interference[slot];
205         otherSlots.resize(assignedLockedStackSlots.size());
206         otherSlots.resize(assignedLockedStackSlots.size() + interferingSlots.size());
207         unsigned nextIndex = assignedLockedStackSlots.size();
208         for (StackSlot* otherSlot : interferingSlots)
209             otherSlots[nextIndex++] = otherSlot;
210
211         assign(slot, otherSlots);
212     }
213
214     // Figure out how much stack we're using for stack slots.
215     unsigned frameSizeForStackSlots = 0;
216     for (StackSlot* slot : code.stackSlots()) {
217         frameSizeForStackSlots = std::max(
218             frameSizeForStackSlots,
219             static_cast<unsigned>(-slot->offsetFromFP()));
220     }
221
222     frameSizeForStackSlots = WTF::roundUpToMultipleOf(stackAlignmentBytes(), frameSizeForStackSlots);
223
224     // Now we need to deduce how much argument area we need.
225     for (BasicBlock* block : code) {
226         for (Inst& inst : *block) {
227             for (Arg& arg : inst.args) {
228                 if (arg.isCallArg()) {
229                     // For now, we assume that we use 8 bytes of the call arg. But that's not
230                     // such an awesome assumption.
231                     // FIXME: https://bugs.webkit.org/show_bug.cgi?id=150454
232                     ASSERT(arg.offset() >= 0);
233                     code.requestCallArgAreaSize(arg.offset() + 8);
234                 }
235             }
236         }
237     }
238
239     code.setFrameSize(frameSizeForStackSlots + code.callArgAreaSize());
240
241     // Finally, transform the code to use Addr's instead of StackSlot's. This is a lossless
242     // transformation since we can search the StackSlots array to figure out which StackSlot any
243     // offset-from-FP refers to.
244
245     for (BasicBlock* block : code) {
246         for (Inst& inst : *block) {
247             for (Arg& arg : inst.args) {
248                 switch (arg.kind()) {
249                 case Arg::Stack:
250                     arg = Arg::addr(
251                         Tmp(GPRInfo::callFrameRegister),
252                         arg.offset() + arg.stackSlot()->offsetFromFP());
253                     break;
254                 case Arg::CallArg:
255                     arg = Arg::addr(
256                         Tmp(GPRInfo::callFrameRegister),
257                         arg.offset() - code.frameSize());
258                     break;
259                 default:
260                     break;
261                 }
262             }
263         }
264     }
265 }
266
267 } } } // namespace JSC::B3::Air
268
269 #endif // ENABLE(B3_JIT)
270
271