diff options
Diffstat (limited to 'llvm/lib/Support/OptimizedStructLayout.cpp')
-rw-r--r-- | llvm/lib/Support/OptimizedStructLayout.cpp | 449 |
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); +} |