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
41namespace JSC { namespace B3 { namespace Air {
42
43namespace {
44
45namespace AirAllocateStackByGraphColoringInternal {
46static const bool verbose = false;
47}
48
49struct 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
90void 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
325