1 // AsmJit - Machine code generation for C++
2 //
3 // * Official AsmJit Home Page: https://asmjit.com
4 // * Official Github Repository: https://github.com/asmjit/asmjit
5 //
6 // Copyright (c) 2008-2020 The AsmJit Authors
7 //
8 // This software is provided 'as-is', without any express or implied
9 // warranty. In no event will the authors be held liable for any damages
10 // arising from the use of this software.
11 //
12 // Permission is granted to anyone to use this software for any purpose,
13 // including commercial applications, and to alter it and redistribute it
14 // freely, subject to the following restrictions:
15 //
16 // 1. The origin of this software must not be misrepresented; you must not
17 // claim that you wrote the original software. If you use this software
18 // in a product, an acknowledgment in the product documentation would be
19 // appreciated but is not required.
20 // 2. Altered source versions must be plainly marked as such, and must not be
21 // misrepresented as being the original software.
22 // 3. This notice may not be removed or altered from any source distribution.
23
24 #include "../core/api-build_p.h"
25 #ifndef ASMJIT_NO_COMPILER
26
27 #include "../core/rastack_p.h"
28 #include "../core/support.h"
29
30 ASMJIT_BEGIN_NAMESPACE
31
32 // ============================================================================
33 // [asmjit::RAStackAllocator - Slots]
34 // ============================================================================
35
newSlot(uint32_t baseRegId,uint32_t size,uint32_t alignment,uint32_t flags)36 RAStackSlot* RAStackAllocator::newSlot(uint32_t baseRegId, uint32_t size, uint32_t alignment, uint32_t flags) noexcept {
37 if (ASMJIT_UNLIKELY(_slots.willGrow(allocator(), 1) != kErrorOk))
38 return nullptr;
39
40 RAStackSlot* slot = allocator()->allocT<RAStackSlot>();
41 if (ASMJIT_UNLIKELY(!slot))
42 return nullptr;
43
44 slot->_baseRegId = uint8_t(baseRegId);
45 slot->_alignment = uint8_t(Support::max<uint32_t>(alignment, 1));
46 slot->_flags = uint16_t(flags);
47 slot->_useCount = 0;
48 slot->_size = size;
49
50 slot->_weight = 0;
51 slot->_offset = 0;
52
53 _alignment = Support::max<uint32_t>(_alignment, alignment);
54 _slots.appendUnsafe(slot);
55 return slot;
56 }
57
58 // ============================================================================
59 // [asmjit::RAStackAllocator - Utilities]
60 // ============================================================================
61
62 struct RAStackGap {
RAStackGapRAStackGap63 inline RAStackGap() noexcept
64 : offset(0),
65 size(0) {}
66
RAStackGapRAStackGap67 inline RAStackGap(uint32_t offset, uint32_t size) noexcept
68 : offset(offset),
69 size(size) {}
70
RAStackGapRAStackGap71 inline RAStackGap(const RAStackGap& other) noexcept
72 : offset(other.offset),
73 size(other.size) {}
74
75 uint32_t offset;
76 uint32_t size;
77 };
78
calculateStackFrame()79 Error RAStackAllocator::calculateStackFrame() noexcept {
80 // Base weight added to all registers regardless of their size and alignment.
81 uint32_t kBaseRegWeight = 16;
82
83 // STEP 1:
84 //
85 // Update usage based on the size of the slot. We boost smaller slots in a way
86 // that 32-bit register has higher priority than a 128-bit register, however,
87 // if one 128-bit register is used 4 times more than some other 32-bit register
88 // it will overweight it.
89 for (RAStackSlot* slot : _slots) {
90 uint32_t alignment = slot->alignment();
91 ASMJIT_ASSERT(alignment > 0);
92
93 uint32_t power = Support::min<uint32_t>(Support::ctz(alignment), 6);
94 uint64_t weight;
95
96 if (slot->isRegHome())
97 weight = kBaseRegWeight + (uint64_t(slot->useCount()) * (7 - power));
98 else
99 weight = power;
100
101 // If overflown, which has less chance of winning a lottery, just use max
102 // possible weight. In such case it probably doesn't matter at all.
103 if (weight > 0xFFFFFFFFu)
104 weight = 0xFFFFFFFFu;
105
106 slot->setWeight(uint32_t(weight));
107 }
108
109 // STEP 2:
110 //
111 // Sort stack slots based on their newly calculated weight (in descending order).
112 _slots.sort([](const RAStackSlot* a, const RAStackSlot* b) noexcept {
113 return a->weight() > b->weight() ? 1 :
114 a->weight() == b->weight() ? 0 : -1;
115 });
116
117 // STEP 3:
118 //
119 // Calculate offset of each slot. We start from the slot that has the highest
120 // weight and advance to slots with lower weight. It could look that offsets
121 // start from the first slot in our list and then simply increase, but it's
122 // not always the case as we also try to fill all gaps introduced by the fact
123 // that slots are sorted by weight and not by size & alignment, so when we need
124 // to align some slot we distribute the gap caused by the alignment to `gaps`.
125 uint32_t offset = 0;
126 ZoneVector<RAStackGap> gaps[kSizeCount - 1];
127
128 for (RAStackSlot* slot : _slots) {
129 if (slot->isStackArg())
130 continue;
131
132 uint32_t slotAlignment = slot->alignment();
133 uint32_t alignedOffset = Support::alignUp(offset, slotAlignment);
134
135 // Try to find a slot within gaps first, before advancing the `offset`.
136 bool foundGap = false;
137 uint32_t gapSize = 0;
138 uint32_t gapOffset = 0;
139
140 {
141 uint32_t slotSize = slot->size();
142 if (slotSize < (1u << uint32_t(ASMJIT_ARRAY_SIZE(gaps)))) {
143 // Iterate from the lowest to the highest possible.
144 uint32_t index = Support::ctz(slotSize);
145 do {
146 if (!gaps[index].empty()) {
147 RAStackGap gap = gaps[index].pop();
148
149 ASMJIT_ASSERT(Support::isAligned(gap.offset, slotAlignment));
150 slot->setOffset(int32_t(gap.offset));
151
152 gapSize = gap.size - slotSize;
153 gapOffset = gap.offset - slotSize;
154
155 foundGap = true;
156 break;
157 }
158 } while (++index < uint32_t(ASMJIT_ARRAY_SIZE(gaps)));
159 }
160 }
161
162 // No gap found, we may create a new one(s) if the current offset is not aligned.
163 if (!foundGap && offset != alignedOffset) {
164 gapSize = alignedOffset - offset;
165 gapOffset = alignedOffset;
166
167 offset = alignedOffset;
168 }
169
170 // True if we have found a gap and not filled all of it or we aligned the current offset.
171 if (gapSize) {
172 uint32_t gapEnd = gapSize + gapOffset;
173 while (gapOffset < gapEnd) {
174 uint32_t index = Support::ctz(gapOffset);
175 uint32_t slotSize = 1u << index;
176
177 // Weird case, better to bail...
178 if (gapEnd - gapOffset < slotSize)
179 break;
180
181 ASMJIT_PROPAGATE(gaps[index].append(allocator(), RAStackGap(gapOffset, slotSize)));
182 gapOffset += slotSize;
183 }
184 }
185
186 if (!foundGap) {
187 ASMJIT_ASSERT(Support::isAligned(offset, slotAlignment));
188 slot->setOffset(int32_t(offset));
189 offset += slot->size();
190 }
191 }
192
193 _stackSize = Support::alignUp(offset, _alignment);
194 return kErrorOk;
195 }
196
adjustSlotOffsets(int32_t offset)197 Error RAStackAllocator::adjustSlotOffsets(int32_t offset) noexcept {
198 for (RAStackSlot* slot : _slots)
199 if (!slot->isStackArg())
200 slot->_offset += offset;
201 return kErrorOk;
202 }
203
204 ASMJIT_END_NAMESPACE
205
206 #endif // !ASMJIT_NO_COMPILER
207