1/*
2 * Copyright (C) 2017-2019 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 "AirStackAllocation.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirArgInlines.h"
32#include "AirCode.h"
33#include "AirInstInlines.h"
34#include "StackAlignment.h"
35#include <wtf/ListDump.h>
36
37namespace JSC { namespace B3 { namespace Air {
38
39namespace {
40
41namespace AirStackAllocationInternal {
42static constexpr bool verbose = false;
43}
44
45template<typename Collection>
46void updateFrameSizeBasedOnStackSlotsImpl(Code& code, const Collection& collection)
47{
48 unsigned frameSize = 0;
49 for (StackSlot* slot : collection)
50 frameSize = std::max(frameSize, static_cast<unsigned>(-slot->offsetFromFP()));
51 code.setFrameSize(WTF::roundUpToMultipleOf(stackAlignmentBytes(), frameSize));
52}
53
54} // anonymous namespace
55
56bool attemptAssignment(
57 StackSlot* slot, intptr_t offsetFromFP, const Vector<StackSlot*>& otherSlots)
58{
59 if (AirStackAllocationInternal::verbose)
60 dataLog("Attempting to assign ", pointerDump(slot), " to ", offsetFromFP, " with interference ", pointerListDump(otherSlots), "\n");
61
62 // Need to align it to the slot's desired alignment.
63 offsetFromFP = -WTF::roundUpToMultipleOf(slot->alignment(), -offsetFromFP);
64
65 for (StackSlot* otherSlot : otherSlots) {
66 if (!otherSlot->offsetFromFP())
67 continue;
68 bool overlap = WTF::rangesOverlap(
69 offsetFromFP,
70 offsetFromFP + static_cast<intptr_t>(slot->byteSize()),
71 otherSlot->offsetFromFP(),
72 otherSlot->offsetFromFP() + static_cast<intptr_t>(otherSlot->byteSize()));
73 if (overlap)
74 return false;
75 }
76
77 if (AirStackAllocationInternal::verbose)
78 dataLog("Assigned ", pointerDump(slot), " to ", offsetFromFP, "\n");
79 slot->setOffsetFromFP(offsetFromFP);
80 return true;
81}
82
83void assign(StackSlot* slot, const Vector<StackSlot*>& otherSlots)
84{
85 if (AirStackAllocationInternal::verbose)
86 dataLog("Attempting to assign ", pointerDump(slot), " with interference ", pointerListDump(otherSlots), "\n");
87
88 if (attemptAssignment(slot, -static_cast<intptr_t>(slot->byteSize()), otherSlots))
89 return;
90
91 for (StackSlot* otherSlot : otherSlots) {
92 if (!otherSlot->offsetFromFP())
93 continue;
94 bool didAssign = attemptAssignment(
95 slot, otherSlot->offsetFromFP() - static_cast<intptr_t>(slot->byteSize()), otherSlots);
96 if (didAssign)
97 return;
98 }
99
100 RELEASE_ASSERT_NOT_REACHED();
101}
102
103Vector<StackSlot*> allocateAndGetEscapedStackSlotsWithoutChangingFrameSize(Code& code)
104{
105 // Allocate all of the escaped slots in order. This is kind of a crazy algorithm to allow for
106 // the possibility of stack slots being assigned frame offsets before we even get here.
107 RELEASE_ASSERT(!code.frameSize());
108 Vector<StackSlot*> assignedEscapedStackSlots;
109 Vector<StackSlot*> escapedStackSlotsWorklist;
110 for (StackSlot* slot : code.stackSlots()) {
111 if (slot->isLocked()) {
112 if (slot->offsetFromFP())
113 assignedEscapedStackSlots.append(slot);
114 else
115 escapedStackSlotsWorklist.append(slot);
116 } else {
117 // It would be super strange to have an unlocked stack slot that has an offset already.
118 ASSERT(!slot->offsetFromFP());
119 }
120 }
121 // This is a fairly expensive loop, but it's OK because we'll usually only have a handful of
122 // escaped stack slots.
123 while (!escapedStackSlotsWorklist.isEmpty()) {
124 StackSlot* slot = escapedStackSlotsWorklist.takeLast();
125 assign(slot, assignedEscapedStackSlots);
126 assignedEscapedStackSlots.append(slot);
127 }
128 return assignedEscapedStackSlots;
129}
130
131void allocateEscapedStackSlots(Code& code)
132{
133 updateFrameSizeBasedOnStackSlotsImpl(
134 code, allocateAndGetEscapedStackSlotsWithoutChangingFrameSize(code));
135}
136
137void updateFrameSizeBasedOnStackSlots(Code& code)
138{
139 updateFrameSizeBasedOnStackSlotsImpl(code, code.stackSlots());
140}
141
142} } } // namespace JSC::B3::Air
143
144#endif // ENABLE(B3_JIT)
145
146