|
173
|
1 //===--- OptimizedStructLayout.cpp - Optimal data layout algorithm ----------------===//
|
|
|
2 //
|
|
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 //
|
|
|
9 // This file implements the performOptimizedStructLayout interface.
|
|
|
10 //
|
|
|
11 //===----------------------------------------------------------------------===//
|
|
|
12
|
|
|
13 #include "llvm/Support/OptimizedStructLayout.h"
|
|
|
14
|
|
|
15 using namespace llvm;
|
|
|
16
|
|
|
17 using Field = OptimizedStructLayoutField;
|
|
|
18
|
|
|
19 #ifndef NDEBUG
|
|
|
20 static void checkValidLayout(ArrayRef<Field> Fields, uint64_t Size,
|
|
|
21 Align MaxAlign) {
|
|
|
22 uint64_t LastEnd = 0;
|
|
|
23 Align ComputedMaxAlign;
|
|
|
24 for (auto &Field : Fields) {
|
|
|
25 assert(Field.hasFixedOffset() &&
|
|
|
26 "didn't assign a fixed offset to field");
|
|
|
27 assert(isAligned(Field.Alignment, Field.Offset) &&
|
|
|
28 "didn't assign a correctly-aligned offset to field");
|
|
|
29 assert(Field.Offset >= LastEnd &&
|
|
|
30 "didn't assign offsets in ascending order");
|
|
|
31 LastEnd = Field.getEndOffset();
|
|
|
32 assert(Field.Alignment <= MaxAlign &&
|
|
|
33 "didn't compute MaxAlign correctly");
|
|
|
34 ComputedMaxAlign = std::max(Field.Alignment, MaxAlign);
|
|
|
35 }
|
|
|
36 assert(LastEnd == Size && "didn't compute LastEnd correctly");
|
|
|
37 assert(ComputedMaxAlign == MaxAlign && "didn't compute MaxAlign correctly");
|
|
|
38 }
|
|
|
39 #endif
|
|
|
40
|
|
|
41 std::pair<uint64_t, Align>
|
|
|
42 llvm::performOptimizedStructLayout(MutableArrayRef<Field> Fields) {
|
|
|
43 #ifndef NDEBUG
|
|
|
44 // Do some simple precondition checks.
|
|
|
45 {
|
|
|
46 bool InFixedPrefix = true;
|
|
|
47 size_t LastEnd = 0;
|
|
|
48 for (auto &Field : Fields) {
|
|
|
49 assert(Field.Size > 0 && "field of zero size");
|
|
|
50 if (Field.hasFixedOffset()) {
|
|
|
51 assert(InFixedPrefix &&
|
|
|
52 "fixed-offset fields are not a strict prefix of array");
|
|
|
53 assert(LastEnd <= Field.Offset &&
|
|
|
54 "fixed-offset fields overlap or are not in order");
|
|
|
55 LastEnd = Field.getEndOffset();
|
|
|
56 assert(LastEnd > Field.Offset &&
|
|
|
57 "overflow in fixed-offset end offset");
|
|
|
58 } else {
|
|
|
59 InFixedPrefix = false;
|
|
|
60 }
|
|
|
61 }
|
|
|
62 }
|
|
|
63 #endif
|
|
|
64
|
|
|
65 // Do an initial pass over the fields.
|
|
|
66 Align MaxAlign;
|
|
|
67
|
|
|
68 // Find the first flexible-offset field, tracking MaxAlign.
|
|
|
69 auto FirstFlexible = Fields.begin(), E = Fields.end();
|
|
|
70 while (FirstFlexible != E && FirstFlexible->hasFixedOffset()) {
|
|
|
71 MaxAlign = std::max(MaxAlign, FirstFlexible->Alignment);
|
|
|
72 ++FirstFlexible;
|
|
|
73 }
|
|
|
74
|
|
|
75 // If there are no flexible fields, we're done.
|
|
|
76 if (FirstFlexible == E) {
|
|
|
77 uint64_t Size = 0;
|
|
|
78 if (!Fields.empty())
|
|
|
79 Size = Fields.back().getEndOffset();
|
|
|
80
|
|
|
81 #ifndef NDEBUG
|
|
|
82 checkValidLayout(Fields, Size, MaxAlign);
|
|
|
83 #endif
|
|
|
84 return std::make_pair(Size, MaxAlign);
|
|
|
85 }
|
|
|
86
|
|
|
87 // Walk over the flexible-offset fields, tracking MaxAlign and
|
|
|
88 // assigning them a unique number in order of their appearance.
|
|
|
89 // We'll use this unique number in the comparison below so that
|
|
|
90 // we can use array_pod_sort, which isn't stable. We won't use it
|
|
|
91 // past that point.
|
|
|
92 {
|
|
|
93 uintptr_t UniqueNumber = 0;
|
|
|
94 for (auto I = FirstFlexible; I != E; ++I) {
|
|
|
95 I->Scratch = reinterpret_cast<void*>(UniqueNumber++);
|
|
|
96 MaxAlign = std::max(MaxAlign, I->Alignment);
|
|
|
97 }
|
|
|
98 }
|
|
|
99
|
|
|
100 // Sort the flexible elements in order of decreasing alignment,
|
|
|
101 // then decreasing size, and then the original order as recorded
|
|
|
102 // in Scratch. The decreasing-size aspect of this is only really
|
|
|
103 // important if we get into the gap-filling stage below, but it
|
|
|
104 // doesn't hurt here.
|
|
|
105 array_pod_sort(FirstFlexible, E,
|
|
|
106 [](const Field *lhs, const Field *rhs) -> int {
|
|
|
107 // Decreasing alignment.
|
|
|
108 if (lhs->Alignment != rhs->Alignment)
|
|
|
109 return (lhs->Alignment < rhs->Alignment ? 1 : -1);
|
|
|
110
|
|
|
111 // Decreasing size.
|
|
|
112 if (lhs->Size != rhs->Size)
|
|
|
113 return (lhs->Size < rhs->Size ? 1 : -1);
|
|
|
114
|
|
|
115 // Original order.
|
|
|
116 auto lhsNumber = reinterpret_cast<uintptr_t>(lhs->Scratch);
|
|
|
117 auto rhsNumber = reinterpret_cast<uintptr_t>(rhs->Scratch);
|
|
|
118 if (lhsNumber != rhsNumber)
|
|
|
119 return (lhsNumber < rhsNumber ? -1 : 1);
|
|
|
120
|
|
|
121 return 0;
|
|
|
122 });
|
|
|
123
|
|
|
124 // Do a quick check for whether that sort alone has given us a perfect
|
|
|
125 // layout with no interior padding. This is very common: if the
|
|
|
126 // fixed-layout fields have no interior padding, and they end at a
|
|
|
127 // sufficiently-aligned offset for all the flexible-layout fields,
|
|
|
128 // and the flexible-layout fields all have sizes that are multiples
|
|
|
129 // of their alignment, then this will reliably trigger.
|
|
|
130 {
|
|
|
131 bool HasPadding = false;
|
|
|
132 uint64_t LastEnd = 0;
|
|
|
133
|
|
|
134 // Walk the fixed-offset fields.
|
|
|
135 for (auto I = Fields.begin(); I != FirstFlexible; ++I) {
|
|
|
136 assert(I->hasFixedOffset());
|
|
|
137 if (LastEnd != I->Offset) {
|
|
|
138 HasPadding = true;
|
|
|
139 break;
|
|
|
140 }
|
|
|
141 LastEnd = I->getEndOffset();
|
|
|
142 }
|
|
|
143
|
|
|
144 // Walk the flexible-offset fields, optimistically assigning fixed
|
|
|
145 // offsets. Note that we maintain a strict division between the
|
|
|
146 // fixed-offset and flexible-offset fields, so if we end up
|
|
|
147 // discovering padding later in this loop, we can just abandon this
|
|
|
148 // work and we'll ignore the offsets we already assigned.
|
|
|
149 if (!HasPadding) {
|
|
|
150 for (auto I = FirstFlexible; I != E; ++I) {
|
|
|
151 auto Offset = alignTo(LastEnd, I->Alignment);
|
|
|
152 if (LastEnd != Offset) {
|
|
|
153 HasPadding = true;
|
|
|
154 break;
|
|
|
155 }
|
|
|
156 I->Offset = Offset;
|
|
|
157 LastEnd = I->getEndOffset();
|
|
|
158 }
|
|
|
159 }
|
|
|
160
|
|
|
161 // If we already have a perfect layout, we're done.
|
|
|
162 if (!HasPadding) {
|
|
|
163 #ifndef NDEBUG
|
|
|
164 checkValidLayout(Fields, LastEnd, MaxAlign);
|
|
|
165 #endif
|
|
|
166 return std::make_pair(LastEnd, MaxAlign);
|
|
|
167 }
|
|
|
168 }
|
|
|
169
|
|
|
170 // The algorithm sketch at this point is as follows.
|
|
|
171 //
|
|
|
172 // Consider the padding gaps between fixed-offset fields in ascending
|
|
|
173 // order. Let LastEnd be the offset of the first byte following the
|
|
|
174 // field before the gap, or 0 if the gap is at the beginning of the
|
|
|
175 // structure. Find the "best" flexible-offset field according to the
|
|
|
176 // criteria below. If no such field exists, proceed to the next gap.
|
|
|
177 // Otherwise, add the field at the first properly-aligned offset for
|
|
|
178 // that field that is >= LastEnd, then update LastEnd and repeat in
|
|
|
179 // order to fill any remaining gap following that field.
|
|
|
180 //
|
|
|
181 // Next, let LastEnd to be the offset of the first byte following the
|
|
|
182 // last fixed-offset field, or 0 if there are no fixed-offset fields.
|
|
|
183 // While there are flexible-offset fields remaining, find the "best"
|
|
|
184 // flexible-offset field according to the criteria below, add it at
|
|
|
185 // the first properly-aligned offset for that field that is >= LastEnd,
|
|
|
186 // and update LastEnd to the first byte following the field.
|
|
|
187 //
|
|
|
188 // The "best" field is chosen by the following criteria, considered
|
|
|
189 // strictly in order:
|
|
|
190 //
|
|
|
191 // - When filling a gap betweeen fields, the field must fit.
|
|
|
192 // - A field is preferred if it requires less padding following LastEnd.
|
|
|
193 // - A field is preferred if it is more aligned.
|
|
|
194 // - A field is preferred if it is larger.
|
|
|
195 // - A field is preferred if it appeared earlier in the initial order.
|
|
|
196 //
|
|
|
197 // Minimizing leading padding is a greedy attempt to avoid padding
|
|
|
198 // entirely. Preferring more-aligned fields is an attempt to eliminate
|
|
|
199 // stricter constraints earlier, with the idea that weaker alignment
|
|
|
200 // constraints may be resolvable with less padding elsewhere. These
|
|
|
201 // These two rules are sufficient to ensure that we get the optimal
|
|
|
202 // layout in the "C-style" case. Preferring larger fields tends to take
|
|
|
203 // better advantage of large gaps and may be more likely to have a size
|
|
|
204 // that's a multiple of a useful alignment. Preferring the initial
|
|
|
205 // order may help somewhat with locality but is mostly just a way of
|
|
|
206 // ensuring deterministic output.
|
|
|
207 //
|
|
|
208 // Note that this algorithm does not guarantee a minimal layout. Picking
|
|
|
209 // a larger object greedily may leave a gap that cannot be filled as
|
|
|
210 // efficiently. Unfortunately, solving this perfectly is an NP-complete
|
|
|
211 // problem (by reduction from bin-packing: let B_i be the bin sizes and
|
|
|
212 // O_j be the object sizes; add fixed-offset fields such that the gaps
|
|
|
213 // between them have size B_i, and add flexible-offset fields with
|
|
|
214 // alignment 1 and size O_j; if the layout size is equal to the end of
|
|
|
215 // the last fixed-layout field, the objects fit in the bins; note that
|
|
|
216 // this doesn't even require the complexity of alignment).
|
|
|
217
|
|
|
218 // The implementation below is essentially just an optimized version of
|
|
|
219 // scanning the list of remaining fields looking for the best, which
|
|
|
220 // would be O(n^2). In the worst case, it doesn't improve on that.
|
|
|
221 // However, in practice it'll just scan the array of alignment bins
|
|
|
222 // and consider the first few elements from one or two bins. The
|
|
|
223 // number of bins is bounded by a small constant: alignments are powers
|
|
|
224 // of two that are vanishingly unlikely to be over 64 and fairly unlikely
|
|
|
225 // to be over 8. And multiple elements only need to be considered when
|
|
|
226 // filling a gap between fixed-offset fields, which doesn't happen very
|
|
|
227 // often. We could use a data structure within bins that optimizes for
|
|
|
228 // finding the best-sized match, but it would require allocating memory
|
|
|
229 // and copying data, so it's unlikely to be worthwhile.
|
|
|
230
|
|
|
231
|
|
|
232 // Start by organizing the flexible-offset fields into bins according to
|
|
|
233 // their alignment. We expect a small enough number of bins that we
|
|
|
234 // don't care about the asymptotic costs of walking this.
|
|
|
235 struct AlignmentQueue {
|
|
|
236 /// The minimum size of anything currently in this queue.
|
|
|
237 uint64_t MinSize;
|
|
|
238
|
|
|
239 /// The head of the queue. A singly-linked list. The order here should
|
|
|
240 /// be consistent with the earlier sort, i.e. the elements should be
|
|
|
241 /// monotonically descending in size and otherwise in the original order.
|
|
|
242 ///
|
|
|
243 /// We remove the queue from the array as soon as this is empty.
|
|
|
244 OptimizedStructLayoutField *Head;
|
|
|
245
|
|
|
246 /// The alignment requirement of the queue.
|
|
|
247 Align Alignment;
|
|
|
248
|
|
|
249 static Field *getNext(Field *Cur) {
|
|
|
250 return static_cast<Field *>(Cur->Scratch);
|
|
|
251 }
|
|
|
252 };
|
|
|
253 SmallVector<AlignmentQueue, 8> FlexibleFieldsByAlignment;
|
|
|
254 for (auto I = FirstFlexible; I != E; ) {
|
|
|
255 auto Head = I;
|
|
|
256 auto Alignment = I->Alignment;
|
|
|
257
|
|
|
258 uint64_t MinSize = I->Size;
|
|
|
259 auto LastInQueue = I;
|
|
|
260 for (++I; I != E && I->Alignment == Alignment; ++I) {
|
|
|
261 LastInQueue->Scratch = I;
|
|
|
262 LastInQueue = I;
|
|
|
263 MinSize = std::min(MinSize, I->Size);
|
|
|
264 }
|
|
|
265 LastInQueue->Scratch = nullptr;
|
|
|
266
|
|
|
267 FlexibleFieldsByAlignment.push_back({MinSize, Head, Alignment});
|
|
|
268 }
|
|
|
269
|
|
|
270 #ifndef NDEBUG
|
|
|
271 // Verify that we set the queues up correctly.
|
|
|
272 auto checkQueues = [&]{
|
|
|
273 bool FirstQueue = true;
|
|
|
274 Align LastQueueAlignment;
|
|
|
275 for (auto &Queue : FlexibleFieldsByAlignment) {
|
|
|
276 assert((FirstQueue || Queue.Alignment < LastQueueAlignment) &&
|
|
|
277 "bins not in order of descending alignment");
|
|
|
278 LastQueueAlignment = Queue.Alignment;
|
|
|
279 FirstQueue = false;
|
|
|
280
|
|
|
281 assert(Queue.Head && "queue was empty");
|
|
|
282 uint64_t LastSize = ~(uint64_t)0;
|
|
|
283 for (auto I = Queue.Head; I; I = Queue.getNext(I)) {
|
|
|
284 assert(I->Alignment == Queue.Alignment && "bad field in queue");
|
|
|
285 assert(I->Size <= LastSize && "queue not in descending size order");
|
|
|
286 LastSize = I->Size;
|
|
|
287 }
|
|
|
288 }
|
|
|
289 };
|
|
|
290 checkQueues();
|
|
|
291 #endif
|
|
|
292
|
|
|
293 /// Helper function to remove a field from a queue.
|
|
|
294 auto spliceFromQueue = [&](AlignmentQueue *Queue, Field *Last, Field *Cur) {
|
|
|
295 assert(Last ? Queue->getNext(Last) == Cur : Queue->Head == Cur);
|
|
|
296
|
|
|
297 // If we're removing Cur from a non-initial position, splice it out
|
|
|
298 // of the linked list.
|
|
|
299 if (Last) {
|
|
|
300 Last->Scratch = Cur->Scratch;
|
|
|
301
|
|
|
302 // If Cur was the last field in the list, we need to update MinSize.
|
|
|
303 // We can just use the last field's size because the list is in
|
|
|
304 // descending order of size.
|
|
|
305 if (!Cur->Scratch)
|
|
|
306 Queue->MinSize = Last->Size;
|
|
|
307
|
|
|
308 // Otherwise, replace the head.
|
|
|
309 } else {
|
|
|
310 if (auto NewHead = Queue->getNext(Cur))
|
|
|
311 Queue->Head = NewHead;
|
|
|
312
|
|
|
313 // If we just emptied the queue, destroy its bin.
|
|
|
314 else
|
|
|
315 FlexibleFieldsByAlignment.erase(Queue);
|
|
|
316 }
|
|
|
317 };
|
|
|
318
|
|
|
319 // Do layout into a local array. Doing this in-place on Fields is
|
|
|
320 // not really feasible.
|
|
|
321 SmallVector<Field, 16> Layout;
|
|
|
322 Layout.reserve(Fields.size());
|
|
|
323
|
|
|
324 // The offset that we're currently looking to insert at (or after).
|
|
|
325 uint64_t LastEnd = 0;
|
|
|
326
|
|
|
327 // Helper function to splice Cur out of the given queue and add it
|
|
|
328 // to the layout at the given offset.
|
|
|
329 auto addToLayout = [&](AlignmentQueue *Queue, Field *Last, Field *Cur,
|
|
|
330 uint64_t Offset) -> bool {
|
|
|
331 assert(Offset == alignTo(LastEnd, Cur->Alignment));
|
|
|
332
|
|
|
333 // Splice out. This potentially invalidates Queue.
|
|
|
334 spliceFromQueue(Queue, Last, Cur);
|
|
|
335
|
|
|
336 // Add Cur to the layout.
|
|
|
337 Layout.push_back(*Cur);
|
|
|
338 Layout.back().Offset = Offset;
|
|
|
339 LastEnd = Layout.back().getEndOffset();
|
|
|
340
|
|
|
341 // Always return true so that we can be tail-called.
|
|
|
342 return true;
|
|
|
343 };
|
|
|
344
|
|
|
345 // Helper function to try to find a field in the given queue that'll
|
|
|
346 // fit starting at StartOffset but before EndOffset (if present).
|
|
|
347 // Note that this never fails if EndOffset is not provided.
|
|
|
348 auto tryAddFillerFromQueue = [&](AlignmentQueue *Queue,
|
|
|
349 uint64_t StartOffset,
|
|
|
350 Optional<uint64_t> EndOffset) -> bool {
|
|
|
351 assert(Queue->Head);
|
|
|
352 assert(StartOffset == alignTo(LastEnd, Queue->Alignment));
|
|
|
353
|
|
|
354 // Figure out the maximum size that a field can be, and ignore this
|
|
|
355 // queue if there's nothing in it that small.
|
|
|
356 auto MaxViableSize =
|
|
|
357 (EndOffset ? *EndOffset - StartOffset : ~(uint64_t)0);
|
|
|
358 if (Queue->MinSize > MaxViableSize) return false;
|
|
|
359
|
|
|
360 // Find the matching field. Note that this should always find
|
|
|
361 // something because of the MinSize check above.
|
|
|
362 for (Field *Cur = Queue->Head, *Last = nullptr; true;
|
|
|
363 Last = Cur, Cur = Queue->getNext(Cur)) {
|
|
|
364 assert(Cur && "didn't find a match in queue despite its MinSize");
|
|
|
365 if (Cur->Size <= MaxViableSize)
|
|
|
366 return addToLayout(Queue, Last, Cur, StartOffset);
|
|
|
367 }
|
|
|
368
|
|
|
369 llvm_unreachable("didn't find a match in queue despite its MinSize");
|
|
|
370 };
|
|
|
371
|
|
|
372 // Helper function to find the "best" flexible-offset field according
|
|
|
373 // to the criteria described above.
|
|
|
374 auto tryAddBestField = [&](Optional<uint64_t> BeforeOffset) -> bool {
|
|
|
375 auto QueueB = FlexibleFieldsByAlignment.begin();
|
|
|
376 auto QueueE = FlexibleFieldsByAlignment.end();
|
|
|
377
|
|
|
378 // Start by looking for the most-aligned queue that doesn't need any
|
|
|
379 // leading padding after LastEnd.
|
|
|
380 auto FirstQueueToSearch = QueueB;
|
|
|
381 for (; FirstQueueToSearch != QueueE; ++FirstQueueToSearch) {
|
|
|
382 if (isAligned(FirstQueueToSearch->Alignment, LastEnd))
|
|
|
383 break;
|
|
|
384 }
|
|
|
385
|
|
|
386 uint64_t Offset = LastEnd;
|
|
|
387 while (true) {
|
|
|
388 // Invariant: all of the queues in [FirstQueueToSearch, QueueE)
|
|
|
389 // require the same initial padding offset.
|
|
|
390
|
|
|
391 // Search those queues in descending order of alignment for a
|
|
|
392 // satisfactory field.
|
|
|
393 for (auto Queue = FirstQueueToSearch; Queue != QueueE; ++Queue) {
|
|
|
394 if (tryAddFillerFromQueue(Queue, Offset, BeforeOffset))
|
|
|
395 return true;
|
|
|
396 }
|
|
|
397
|
|
|
398 // Okay, we don't need to scan those again.
|
|
|
399 QueueE = FirstQueueToSearch;
|
|
|
400
|
|
|
401 // If we started from the first queue, we're done.
|
|
|
402 if (FirstQueueToSearch == QueueB)
|
|
|
403 return false;
|
|
|
404
|
|
|
405 // Otherwise, scan backwards to find the most-aligned queue that
|
|
|
406 // still has minimal leading padding after LastEnd.
|
|
|
407 --FirstQueueToSearch;
|
|
|
408 Offset = alignTo(LastEnd, FirstQueueToSearch->Alignment);
|
|
|
409 while (FirstQueueToSearch != QueueB &&
|
|
|
410 Offset == alignTo(LastEnd, FirstQueueToSearch[-1].Alignment))
|
|
|
411 --FirstQueueToSearch;
|
|
|
412 }
|
|
|
413 };
|
|
|
414
|
|
|
415 // Phase 1: fill the gaps between fixed-offset fields with the best
|
|
|
416 // flexible-offset field that fits.
|
|
|
417 for (auto I = Fields.begin(); I != FirstFlexible; ++I) {
|
|
|
418 while (LastEnd != I->Offset) {
|
|
|
419 if (!tryAddBestField(I->Offset))
|
|
|
420 break;
|
|
|
421 }
|
|
|
422 Layout.push_back(*I);
|
|
|
423 LastEnd = I->getEndOffset();
|
|
|
424 }
|
|
|
425
|
|
|
426 #ifndef NDEBUG
|
|
|
427 checkQueues();
|
|
|
428 #endif
|
|
|
429
|
|
|
430 // Phase 2: repeatedly add the best flexible-offset field until
|
|
|
431 // they're all gone.
|
|
|
432 while (!FlexibleFieldsByAlignment.empty()) {
|
|
|
433 bool Success = tryAddBestField(None);
|
|
|
434 assert(Success && "didn't find a field with no fixed limit?");
|
|
|
435 (void) Success;
|
|
|
436 }
|
|
|
437
|
|
|
438 // Copy the layout back into place.
|
|
|
439 assert(Layout.size() == Fields.size());
|
|
|
440 memcpy(Fields.data(), Layout.data(),
|
|
|
441 Fields.size() * sizeof(OptimizedStructLayoutField));
|
|
|
442
|
|
|
443 #ifndef NDEBUG
|
|
|
444 // Make a final check that the layout is valid.
|
|
|
445 checkValidLayout(Fields, LastEnd, MaxAlign);
|
|
|
446 #endif
|
|
|
447
|
|
|
448 return std::make_pair(LastEnd, MaxAlign);
|
|
|
449 }
|
