1 //===--- OptimizedStructLayout.cpp - Optimal data layout algorithm ----------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
29            "didn't assign a correctly-aligned offset to field");  in checkValidLayout()
35     ComputedMaxAlign = std::max(Field.Alignment, MaxAlign);  in checkValidLayout()
53                "fixed-offset fields are not a strict prefix of array");  in performOptimizedStructLayout()
55                "fixed-offset fields overlap or are not in order");  in performOptimizedStructLayout()
58                "overflow in fixed-offset end offset");  in performOptimizedStructLayout()
69   // Find the first flexible-offset field, tracking MaxAlign.  in performOptimizedStructLayout()
71   while (FirstFlexible != E && FirstFlexible->hasFixedOffset()) {  in performOptimizedStructLayout()
72     MaxAlign = std::max(MaxAlign, FirstFlexible->Alignment);  in performOptimizedStructLayout()
88   // Walk over the flexible-offset fields, tracking MaxAlign and  in performOptimizedStructLayout()
96       I->Scratch = reinterpret_cast<void*>(UniqueNumber++);  in performOptimizedStructLayout()
97       MaxAlign = std::max(MaxAlign, I->Alignment);  in performOptimizedStructLayout()
103   // in Scratch.  The decreasing-size aspect of this is only really  in performOptimizedStructLayout()
104   // important if we get into the gap-filling stage below, but it  in performOptimizedStructLayout()
107                  [](const Field *lhs, const Field *rhs) -> int {  in performOptimizedStructLayout()
109     if (lhs->Alignment != rhs->Alignment)  in performOptimizedStructLayout()
110       return (lhs->Alignment < rhs->Alignment ? 1 : -1);  in performOptimizedStructLayout()
113     if (lhs->Size != rhs->Size)  in performOptimizedStructLayout()
114       return (lhs->Size < rhs->Size ? 1 : -1);  in performOptimizedStructLayout()
117     auto lhsNumber = reinterpret_cast<uintptr_t>(lhs->Scratch);  in performOptimizedStructLayout()
118     auto rhsNumber = reinterpret_cast<uintptr_t>(rhs->Scratch);  in performOptimizedStructLayout()
120       return (lhsNumber < rhsNumber ? -1 : 1);  in performOptimizedStructLayout()
127   // fixed-layout fields have no interior padding, and they end at a  in performOptimizedStructLayout()
128   // sufficiently-aligned offset for all the flexible-layout fields,  in performOptimizedStructLayout()
129   // and the flexible-layout fields all have sizes that are multiples  in performOptimizedStructLayout()
135     // Walk the fixed-offset fields.  in performOptimizedStructLayout()
137       assert(I->hasFixedOffset());  in performOptimizedStructLayout()
138       if (LastEnd != I->Offset) {  in performOptimizedStructLayout()
142       LastEnd = I->getEndOffset();  in performOptimizedStructLayout()
145     // Walk the flexible-offset fields, optimistically assigning fixed  in performOptimizedStructLayout()
147     // fixed-offset and flexible-offset fields, so if we end up  in performOptimizedStructLayout()
152         auto Offset = alignTo(LastEnd, I->Alignment);  in performOptimizedStructLayout()
157         I->Offset = Offset;  in performOptimizedStructLayout()
158         LastEnd = I->getEndOffset();  in performOptimizedStructLayout()
173   // Consider the padding gaps between fixed-offset fields in ascending  in performOptimizedStructLayout()
176   // structure.  Find the "best" flexible-offset field according to the  in performOptimizedStructLayout()
178   // Otherwise, add the field at the first properly-aligned offset for  in performOptimizedStructLayout()
183   // last fixed-offset field, or 0 if there are no fixed-offset fields.  in performOptimizedStructLayout()
184   // While there are flexible-offset fields remaining, find the "best"  in performOptimizedStructLayout()
185   // flexible-offset field according to the criteria below, add it at  in performOptimizedStructLayout()
186   // the first properly-aligned offset for that field that is >= LastEnd,  in performOptimizedStructLayout()
192   // - When filling a gap betweeen fields, the field must fit.  in performOptimizedStructLayout()
193   // - A field is preferred if it requires less padding following LastEnd.  in performOptimizedStructLayout()
194   // - A field is preferred if it is more aligned.  in performOptimizedStructLayout()
195   // - A field is preferred if it is larger.  in performOptimizedStructLayout()
196   // - A field is preferred if it appeared earlier in the initial order.  in performOptimizedStructLayout()
199   // entirely.  Preferring more-aligned fields is an attempt to eliminate  in performOptimizedStructLayout()
203   // layout in the "C-style" case.  Preferring larger fields tends to take  in performOptimizedStructLayout()
211   // efficiently.  Unfortunately, solving this perfectly is an NP-complete  in performOptimizedStructLayout()
212   // problem (by reduction from bin-packing: let B_i be the bin sizes and  in performOptimizedStructLayout()
213   // O_j be the object sizes; add fixed-offset fields such that the gaps  in performOptimizedStructLayout()
214   // between them have size B_i, and add flexible-offset fields with  in performOptimizedStructLayout()
216   // the last fixed-layout field, the objects fit in the bins; note that  in performOptimizedStructLayout()
227   // filling a gap between fixed-offset fields, which doesn't happen very  in performOptimizedStructLayout()
229   // finding the best-sized match, but it would require allocating memory  in performOptimizedStructLayout()
233   // Start by organizing the flexible-offset fields into bins according to  in performOptimizedStructLayout()
240     /// The head of the queue.  A singly-linked list.  The order here should  in performOptimizedStructLayout()
250     static Field *getNext(Field *Cur) {  in performOptimizedStructLayout()
251       return static_cast<Field *>(Cur->Scratch);  in performOptimizedStructLayout()
257     auto Alignment = I->Alignment;  in performOptimizedStructLayout()
259     uint64_t MinSize = I->Size;  in performOptimizedStructLayout()
261     for (++I; I != E && I->Alignment == Alignment; ++I) {  in performOptimizedStructLayout()
262       LastInQueue->Scratch = I;  in performOptimizedStructLayout()
264       MinSize = std::min(MinSize, I->Size);  in performOptimizedStructLayout()
266     LastInQueue->Scratch = nullptr;  in performOptimizedStructLayout()
285         assert(I->Alignment == Queue.Alignment && "bad field in queue");  in performOptimizedStructLayout()
286         assert(I->Size <= LastSize && "queue not in descending size order");  in performOptimizedStructLayout()
287         LastSize = I->Size;  in performOptimizedStructLayout()
295   auto spliceFromQueue = [&](AlignmentQueue *Queue, Field *Last, Field *Cur) {  in performOptimizedStructLayout()  argument
296     assert(Last ? Queue->getNext(Last) == Cur : Queue->Head == Cur);  in performOptimizedStructLayout()
298     // If we're removing Cur from a non-initial position, splice it out  in performOptimizedStructLayout()
301       Last->Scratch = Cur->Scratch;  in performOptimizedStructLayout()
303       // If Cur was the last field in the list, we need to update MinSize.  in performOptimizedStructLayout()
306       if (!Cur->Scratch)  in performOptimizedStructLayout()
307         Queue->MinSize = Last->Size;  in performOptimizedStructLayout()
311       if (auto NewHead = Queue->getNext(Cur))  in performOptimizedStructLayout()
312         Queue->Head = NewHead;  in performOptimizedStructLayout()
320   // Do layout into a local array.  Doing this in-place on Fields is  in performOptimizedStructLayout()
328   // Helper function to splice Cur out of the given queue and add it  in performOptimizedStructLayout()
330   auto addToLayout = [&](AlignmentQueue *Queue, Field *Last, Field *Cur,  in performOptimizedStructLayout()
331                          uint64_t Offset) -> bool {  in performOptimizedStructLayout()
332     assert(Offset == alignTo(LastEnd, Cur->Alignment));  in performOptimizedStructLayout()
335     spliceFromQueue(Queue, Last, Cur);  in performOptimizedStructLayout()
337     // Add Cur to the layout.  in performOptimizedStructLayout()
338     Layout.push_back(*Cur);  in performOptimizedStructLayout()
342     // Always return true so that we can be tail-called.  in performOptimizedStructLayout()
350                                    std::optional<uint64_t> EndOffset) -> bool {  in performOptimizedStructLayout()
351     assert(Queue->Head);  in performOptimizedStructLayout()
352     assert(StartOffset == alignTo(LastEnd, Queue->Alignment));  in performOptimizedStructLayout()
358       (EndOffset ? *EndOffset - StartOffset : ~(uint64_t)0);  in performOptimizedStructLayout()
359     if (Queue->MinSize > MaxViableSize)  in performOptimizedStructLayout()
364     for (Field *Cur = Queue->Head, *Last = nullptr; true;  in performOptimizedStructLayout()  local
365            Last = Cur, Cur = Queue->getNext(Cur)) {  in performOptimizedStructLayout()
366       assert(Cur && "didn't find a match in queue despite its MinSize");  in performOptimizedStructLayout()
367       if (Cur->Size <= MaxViableSize)  in performOptimizedStructLayout()
368         return addToLayout(Queue, Last, Cur, StartOffset);  in performOptimizedStructLayout()
374   // Helper function to find the "best" flexible-offset field according  in performOptimizedStructLayout()
376   auto tryAddBestField = [&](std::optional<uint64_t> BeforeOffset) -> bool {  in performOptimizedStructLayout()
381     // Start by looking for the most-aligned queue that doesn't need any  in performOptimizedStructLayout()
385       if (isAligned(FirstQueueToSearch->Alignment, LastEnd))  in performOptimizedStructLayout()
408       // Otherwise, scan backwards to find the most-aligned queue that  in performOptimizedStructLayout()
411       --FirstQueueToSearch;  in performOptimizedStructLayout()
412       Offset = alignTo(LastEnd, FirstQueueToSearch->Alignment);  in performOptimizedStructLayout()
416              Offset == alignTo(LastEnd, FirstQueueToSearch[-1].Alignment))  in performOptimizedStructLayout()
417         --FirstQueueToSearch;  in performOptimizedStructLayout()
421   // Phase 1: fill the gaps between fixed-offset fields with the best  in performOptimizedStructLayout()
422   // flexible-offset field that fits.  in performOptimizedStructLayout()
424     assert(LastEnd <= I->Offset);  in performOptimizedStructLayout()
425     while (LastEnd != I->Offset) {  in performOptimizedStructLayout()
426       if (!tryAddBestField(I->Offset))  in performOptimizedStructLayout()
430     LastEnd = I->getEndOffset();  in performOptimizedStructLayout()
437   // Phase 2: repeatedly add the best flexible-offset field until  in performOptimizedStructLayout()