summaryrefslogtreecommitdiff
path: root/llvm/lib/Support/OptimizedStructLayout.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Support/OptimizedStructLayout.cpp')
-rw-r--r--llvm/lib/Support/OptimizedStructLayout.cpp449
1 files changed, 449 insertions, 0 deletions
diff --git a/llvm/lib/Support/OptimizedStructLayout.cpp b/llvm/lib/Support/OptimizedStructLayout.cpp
new file mode 100644
index 0000000000000..9bbd767c5ce9b
--- /dev/null
+++ b/llvm/lib/Support/OptimizedStructLayout.cpp
@@ -0,0 +1,449 @@
+//===--- OptimizedStructLayout.cpp - Optimal data layout algorithm ----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the performOptimizedStructLayout interface.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/OptimizedStructLayout.h"
+
+using namespace llvm;
+
+using Field = OptimizedStructLayoutField;
+
+#ifndef NDEBUG
+static void checkValidLayout(ArrayRef<Field> Fields, uint64_t Size,
+ Align MaxAlign) {
+ uint64_t LastEnd = 0;
+ Align ComputedMaxAlign;
+ for (auto &Field : Fields) {
+ assert(Field.hasFixedOffset() &&
+ "didn't assign a fixed offset to field");
+ assert(isAligned(Field.Alignment, Field.Offset) &&
+ "didn't assign a correctly-aligned offset to field");
+ assert(Field.Offset >= LastEnd &&
+ "didn't assign offsets in ascending order");
+ LastEnd = Field.getEndOffset();
+ assert(Field.Alignment <= MaxAlign &&
+ "didn't compute MaxAlign correctly");
+ ComputedMaxAlign = std::max(Field.Alignment, MaxAlign);
+ }
+ assert(LastEnd == Size && "didn't compute LastEnd correctly");
+ assert(ComputedMaxAlign == MaxAlign && "didn't compute MaxAlign correctly");
+}
+#endif
+
+std::pair<uint64_t, Align>
+llvm::performOptimizedStructLayout(MutableArrayRef<Field> Fields) {
+#ifndef NDEBUG
+ // Do some simple precondition checks.
+ {
+ bool InFixedPrefix = true;
+ size_t LastEnd = 0;
+ for (auto &Field : Fields) {
+ assert(Field.Size > 0 && "field of zero size");
+ if (Field.hasFixedOffset()) {
+ assert(InFixedPrefix &&
+ "fixed-offset fields are not a strict prefix of array");
+ assert(LastEnd <= Field.Offset &&
+ "fixed-offset fields overlap or are not in order");
+ LastEnd = Field.getEndOffset();
+ assert(LastEnd > Field.Offset &&
+ "overflow in fixed-offset end offset");
+ } else {
+ InFixedPrefix = false;
+ }
+ }
+ }
+#endif
+
+ // Do an initial pass over the fields.
+ Align MaxAlign;
+
+ // Find the first flexible-offset field, tracking MaxAlign.
+ auto FirstFlexible = Fields.begin(), E = Fields.end();
+ while (FirstFlexible != E && FirstFlexible->hasFixedOffset()) {
+ MaxAlign = std::max(MaxAlign, FirstFlexible->Alignment);
+ ++FirstFlexible;
+ }
+
+ // If there are no flexible fields, we're done.
+ if (FirstFlexible == E) {
+ uint64_t Size = 0;
+ if (!Fields.empty())
+ Size = Fields.back().getEndOffset();
+
+#ifndef NDEBUG
+ checkValidLayout(Fields, Size, MaxAlign);
+#endif
+ return std::make_pair(Size, MaxAlign);
+ }
+
+ // Walk over the flexible-offset fields, tracking MaxAlign and
+ // assigning them a unique number in order of their appearance.
+ // We'll use this unique number in the comparison below so that
+ // we can use array_pod_sort, which isn't stable. We won't use it
+ // past that point.
+ {
+ uintptr_t UniqueNumber = 0;
+ for (auto I = FirstFlexible; I != E; ++I) {
+ I->Scratch = reinterpret_cast<void*>(UniqueNumber++);
+ MaxAlign = std::max(MaxAlign, I->Alignment);
+ }
+ }
+
+ // Sort the flexible elements in order of decreasing alignment,
+ // then decreasing size, and then the original order as recorded
+ // in Scratch. The decreasing-size aspect of this is only really
+ // important if we get into the gap-filling stage below, but it
+ // doesn't hurt here.
+ array_pod_sort(FirstFlexible, E,
+ [](const Field *lhs, const Field *rhs) -> int {
+ // Decreasing alignment.
+ if (lhs->Alignment != rhs->Alignment)
+ return (lhs->Alignment < rhs->Alignment ? 1 : -1);
+
+ // Decreasing size.
+ if (lhs->Size != rhs->Size)
+ return (lhs->Size < rhs->Size ? 1 : -1);
+
+ // Original order.
+ auto lhsNumber = reinterpret_cast<uintptr_t>(lhs->Scratch);
+ auto rhsNumber = reinterpret_cast<uintptr_t>(rhs->Scratch);
+ if (lhsNumber != rhsNumber)
+ return (lhsNumber < rhsNumber ? -1 : 1);
+
+ return 0;
+ });
+
+ // Do a quick check for whether that sort alone has given us a perfect
+ // layout with no interior padding. This is very common: if the
+ // fixed-layout fields have no interior padding, and they end at a
+ // sufficiently-aligned offset for all the flexible-layout fields,
+ // and the flexible-layout fields all have sizes that are multiples
+ // of their alignment, then this will reliably trigger.
+ {
+ bool HasPadding = false;
+ uint64_t LastEnd = 0;
+
+ // Walk the fixed-offset fields.
+ for (auto I = Fields.begin(); I != FirstFlexible; ++I) {
+ assert(I->hasFixedOffset());
+ if (LastEnd != I->Offset) {
+ HasPadding = true;
+ break;
+ }
+ LastEnd = I->getEndOffset();
+ }
+
+ // Walk the flexible-offset fields, optimistically assigning fixed
+ // offsets. Note that we maintain a strict division between the
+ // fixed-offset and flexible-offset fields, so if we end up
+ // discovering padding later in this loop, we can just abandon this
+ // work and we'll ignore the offsets we already assigned.
+ if (!HasPadding) {
+ for (auto I = FirstFlexible; I != E; ++I) {
+ auto Offset = alignTo(LastEnd, I->Alignment);
+ if (LastEnd != Offset) {
+ HasPadding = true;
+ break;
+ }
+ I->Offset = Offset;
+ LastEnd = I->getEndOffset();
+ }
+ }
+
+ // If we already have a perfect layout, we're done.
+ if (!HasPadding) {
+#ifndef NDEBUG
+ checkValidLayout(Fields, LastEnd, MaxAlign);
+#endif
+ return std::make_pair(LastEnd, MaxAlign);
+ }
+ }
+
+ // The algorithm sketch at this point is as follows.
+ //
+ // Consider the padding gaps between fixed-offset fields in ascending
+ // order. Let LastEnd be the offset of the first byte following the
+ // field before the gap, or 0 if the gap is at the beginning of the
+ // structure. Find the "best" flexible-offset field according to the
+ // criteria below. If no such field exists, proceed to the next gap.
+ // Otherwise, add the field at the first properly-aligned offset for
+ // that field that is >= LastEnd, then update LastEnd and repeat in
+ // order to fill any remaining gap following that field.
+ //
+ // Next, let LastEnd to be the offset of the first byte following the
+ // last fixed-offset field, or 0 if there are no fixed-offset fields.
+ // While there are flexible-offset fields remaining, find the "best"
+ // flexible-offset field according to the criteria below, add it at
+ // the first properly-aligned offset for that field that is >= LastEnd,
+ // and update LastEnd to the first byte following the field.
+ //
+ // The "best" field is chosen by the following criteria, considered
+ // strictly in order:
+ //
+ // - When filling a gap betweeen fields, the field must fit.
+ // - A field is preferred if it requires less padding following LastEnd.
+ // - A field is preferred if it is more aligned.
+ // - A field is preferred if it is larger.
+ // - A field is preferred if it appeared earlier in the initial order.
+ //
+ // Minimizing leading padding is a greedy attempt to avoid padding
+ // entirely. Preferring more-aligned fields is an attempt to eliminate
+ // stricter constraints earlier, with the idea that weaker alignment
+ // constraints may be resolvable with less padding elsewhere. These
+ // These two rules are sufficient to ensure that we get the optimal
+ // layout in the "C-style" case. Preferring larger fields tends to take
+ // better advantage of large gaps and may be more likely to have a size
+ // that's a multiple of a useful alignment. Preferring the initial
+ // order may help somewhat with locality but is mostly just a way of
+ // ensuring deterministic output.
+ //
+ // Note that this algorithm does not guarantee a minimal layout. Picking
+ // a larger object greedily may leave a gap that cannot be filled as
+ // efficiently. Unfortunately, solving this perfectly is an NP-complete
+ // problem (by reduction from bin-packing: let B_i be the bin sizes and
+ // O_j be the object sizes; add fixed-offset fields such that the gaps
+ // between them have size B_i, and add flexible-offset fields with
+ // alignment 1 and size O_j; if the layout size is equal to the end of
+ // the last fixed-layout field, the objects fit in the bins; note that
+ // this doesn't even require the complexity of alignment).
+
+ // The implementation below is essentially just an optimized version of
+ // scanning the list of remaining fields looking for the best, which
+ // would be O(n^2). In the worst case, it doesn't improve on that.
+ // However, in practice it'll just scan the array of alignment bins
+ // and consider the first few elements from one or two bins. The
+ // number of bins is bounded by a small constant: alignments are powers
+ // of two that are vanishingly unlikely to be over 64 and fairly unlikely
+ // to be over 8. And multiple elements only need to be considered when
+ // filling a gap between fixed-offset fields, which doesn't happen very
+ // often. We could use a data structure within bins that optimizes for
+ // finding the best-sized match, but it would require allocating memory
+ // and copying data, so it's unlikely to be worthwhile.
+
+
+ // Start by organizing the flexible-offset fields into bins according to
+ // their alignment. We expect a small enough number of bins that we
+ // don't care about the asymptotic costs of walking this.
+ struct AlignmentQueue {
+ /// The minimum size of anything currently in this queue.
+ uint64_t MinSize;
+
+ /// The head of the queue. A singly-linked list. The order here should
+ /// be consistent with the earlier sort, i.e. the elements should be
+ /// monotonically descending in size and otherwise in the original order.
+ ///
+ /// We remove the queue from the array as soon as this is empty.
+ OptimizedStructLayoutField *Head;
+
+ /// The alignment requirement of the queue.
+ Align Alignment;
+
+ static Field *getNext(Field *Cur) {
+ return static_cast<Field *>(Cur->Scratch);
+ }
+ };
+ SmallVector<AlignmentQueue, 8> FlexibleFieldsByAlignment;
+ for (auto I = FirstFlexible; I != E; ) {
+ auto Head = I;
+ auto Alignment = I->Alignment;
+
+ uint64_t MinSize = I->Size;
+ auto LastInQueue = I;
+ for (++I; I != E && I->Alignment == Alignment; ++I) {
+ LastInQueue->Scratch = I;
+ LastInQueue = I;
+ MinSize = std::min(MinSize, I->Size);
+ }
+ LastInQueue->Scratch = nullptr;
+
+ FlexibleFieldsByAlignment.push_back({MinSize, Head, Alignment});
+ }
+
+#ifndef NDEBUG
+ // Verify that we set the queues up correctly.
+ auto checkQueues = [&]{
+ bool FirstQueue = true;
+ Align LastQueueAlignment;
+ for (auto &Queue : FlexibleFieldsByAlignment) {
+ assert((FirstQueue || Queue.Alignment < LastQueueAlignment) &&
+ "bins not in order of descending alignment");
+ LastQueueAlignment = Queue.Alignment;
+ FirstQueue = false;
+
+ assert(Queue.Head && "queue was empty");
+ uint64_t LastSize = ~(uint64_t)0;
+ for (auto I = Queue.Head; I; I = Queue.getNext(I)) {
+ assert(I->Alignment == Queue.Alignment && "bad field in queue");
+ assert(I->Size <= LastSize && "queue not in descending size order");
+ LastSize = I->Size;
+ }
+ }
+ };
+ checkQueues();
+#endif
+
+ /// Helper function to remove a field from a queue.
+ auto spliceFromQueue = [&](AlignmentQueue *Queue, Field *Last, Field *Cur) {
+ assert(Last ? Queue->getNext(Last) == Cur : Queue->Head == Cur);
+
+ // If we're removing Cur from a non-initial position, splice it out
+ // of the linked list.
+ if (Last) {
+ Last->Scratch = Cur->Scratch;
+
+ // If Cur was the last field in the list, we need to update MinSize.
+ // We can just use the last field's size because the list is in
+ // descending order of size.
+ if (!Cur->Scratch)
+ Queue->MinSize = Last->Size;
+
+ // Otherwise, replace the head.
+ } else {
+ if (auto NewHead = Queue->getNext(Cur))
+ Queue->Head = NewHead;
+
+ // If we just emptied the queue, destroy its bin.
+ else
+ FlexibleFieldsByAlignment.erase(Queue);
+ }
+ };
+
+ // Do layout into a local array. Doing this in-place on Fields is
+ // not really feasible.
+ SmallVector<Field, 16> Layout;
+ Layout.reserve(Fields.size());
+
+ // The offset that we're currently looking to insert at (or after).
+ uint64_t LastEnd = 0;
+
+ // Helper function to splice Cur out of the given queue and add it
+ // to the layout at the given offset.
+ auto addToLayout = [&](AlignmentQueue *Queue, Field *Last, Field *Cur,
+ uint64_t Offset) -> bool {
+ assert(Offset == alignTo(LastEnd, Cur->Alignment));
+
+ // Splice out. This potentially invalidates Queue.
+ spliceFromQueue(Queue, Last, Cur);
+
+ // Add Cur to the layout.
+ Layout.push_back(*Cur);
+ Layout.back().Offset = Offset;
+ LastEnd = Layout.back().getEndOffset();
+
+ // Always return true so that we can be tail-called.
+ return true;
+ };
+
+ // Helper function to try to find a field in the given queue that'll
+ // fit starting at StartOffset but before EndOffset (if present).
+ // Note that this never fails if EndOffset is not provided.
+ auto tryAddFillerFromQueue = [&](AlignmentQueue *Queue,
+ uint64_t StartOffset,
+ Optional<uint64_t> EndOffset) -> bool {
+ assert(Queue->Head);
+ assert(StartOffset == alignTo(LastEnd, Queue->Alignment));
+
+ // Figure out the maximum size that a field can be, and ignore this
+ // queue if there's nothing in it that small.
+ auto MaxViableSize =
+ (EndOffset ? *EndOffset - StartOffset : ~(uint64_t)0);
+ if (Queue->MinSize > MaxViableSize) return false;
+
+ // Find the matching field. Note that this should always find
+ // something because of the MinSize check above.
+ for (Field *Cur = Queue->Head, *Last = nullptr; true;
+ Last = Cur, Cur = Queue->getNext(Cur)) {
+ assert(Cur && "didn't find a match in queue despite its MinSize");
+ if (Cur->Size <= MaxViableSize)
+ return addToLayout(Queue, Last, Cur, StartOffset);
+ }
+
+ llvm_unreachable("didn't find a match in queue despite its MinSize");
+ };
+
+ // Helper function to find the "best" flexible-offset field according
+ // to the criteria described above.
+ auto tryAddBestField = [&](Optional<uint64_t> BeforeOffset) -> bool {
+ auto QueueB = FlexibleFieldsByAlignment.begin();
+ auto QueueE = FlexibleFieldsByAlignment.end();
+
+ // Start by looking for the most-aligned queue that doesn't need any
+ // leading padding after LastEnd.
+ auto FirstQueueToSearch = QueueB;
+ for (; FirstQueueToSearch != QueueE; ++FirstQueueToSearch) {
+ if (isAligned(FirstQueueToSearch->Alignment, LastEnd))
+ break;
+ }
+
+ uint64_t Offset = LastEnd;
+ while (true) {
+ // Invariant: all of the queues in [FirstQueueToSearch, QueueE)
+ // require the same initial padding offset.
+
+ // Search those queues in descending order of alignment for a
+ // satisfactory field.
+ for (auto Queue = FirstQueueToSearch; Queue != QueueE; ++Queue) {
+ if (tryAddFillerFromQueue(Queue, Offset, BeforeOffset))
+ return true;
+ }
+
+ // Okay, we don't need to scan those again.
+ QueueE = FirstQueueToSearch;
+
+ // If we started from the first queue, we're done.
+ if (FirstQueueToSearch == QueueB)
+ return false;
+
+ // Otherwise, scan backwards to find the most-aligned queue that
+ // still has minimal leading padding after LastEnd.
+ --FirstQueueToSearch;
+ Offset = alignTo(LastEnd, FirstQueueToSearch->Alignment);
+ while (FirstQueueToSearch != QueueB &&
+ Offset == alignTo(LastEnd, FirstQueueToSearch[-1].Alignment))
+ --FirstQueueToSearch;
+ }
+ };
+
+ // Phase 1: fill the gaps between fixed-offset fields with the best
+ // flexible-offset field that fits.
+ for (auto I = Fields.begin(); I != FirstFlexible; ++I) {
+ while (LastEnd != I->Offset) {
+ if (!tryAddBestField(I->Offset))
+ break;
+ }
+ Layout.push_back(*I);
+ LastEnd = I->getEndOffset();
+ }
+
+#ifndef NDEBUG
+ checkQueues();
+#endif
+
+ // Phase 2: repeatedly add the best flexible-offset field until
+ // they're all gone.
+ while (!FlexibleFieldsByAlignment.empty()) {
+ bool Success = tryAddBestField(None);
+ assert(Success && "didn't find a field with no fixed limit?");
+ (void) Success;
+ }
+
+ // Copy the layout back into place.
+ assert(Layout.size() == Fields.size());
+ memcpy(Fields.data(), Layout.data(),
+ Fields.size() * sizeof(OptimizedStructLayoutField));
+
+#ifndef NDEBUG
+ // Make a final check that the layout is valid.
+ checkValidLayout(Fields, LastEnd, MaxAlign);
+#endif
+
+ return std::make_pair(LastEnd, MaxAlign);
+}