LLVM  13.0.0git
OptimizedStructLayout.cpp
Go to the documentation of this file.
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 
14 
15 using namespace llvm;
16 
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) {
26  "didn't assign a fixed offset to field");
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>
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.
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 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:158
llvm::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1397
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:148
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
llvm::OptimizedStructLayoutField::Offset
uint64_t Offset
The offset of this field in the final layout.
Definition: OptimizedStructLayout.h:58
return
return
Definition: README.txt:242
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::Optional< uint64_t >
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
llvm::MutableArrayRef::end
iterator end() const
Definition: ArrayRef.h:355
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::None
const NoneType None
Definition: None.h:23
llvm::OptimizedStructLayoutField::Alignment
Align Alignment
The required alignment of this field.
Definition: OptimizedStructLayout.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MutableArrayRef::back
T & back() const
back - Get the last element.
Definition: ArrayRef.h:367
OptimizedStructLayout.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
checkValidLayout
static void checkValidLayout(ArrayRef< Field > Fields, uint64_t Size, Align MaxAlign)
Definition: OptimizedStructLayout.cpp:20
llvm::MutableArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:354
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:339
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::OptimizedStructLayoutField::getEndOffset
uint64_t getEndOffset() const
Given that this field has a fixed offset, return the offset of the first byte following it.
Definition: OptimizedStructLayout.h:82
llvm::OptimizedStructLayoutField::Size
uint64_t Size
The required size of this field in bytes.
Definition: OptimizedStructLayout.h:62
llvm::MutableArrayRef::data
T * data() const
Definition: ArrayRef.h:352
llvm::performOptimizedStructLayout
std::pair< uint64_t, Align > performOptimizedStructLayout(MutableArrayRef< OptimizedStructLayoutField > Fields)
Compute a layout for a struct containing the given fields, making a best-effort attempt to minimize t...
Definition: OptimizedStructLayout.cpp:42
Success
#define Success
Definition: AArch64Disassembler.cpp:248
llvm::OptimizedStructLayoutField::Scratch
void * Scratch
Private scratch space for the algorithm.
Definition: OptimizedStructLayout.h:69
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
llvm::OptimizedStructLayoutField
A field in a structure.
Definition: OptimizedStructLayout.h:44
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
llvm::OptimizedStructLayoutField::hasFixedOffset
bool hasFixedOffset() const
Return true if this field has been assigned a fixed offset.
Definition: OptimizedStructLayout.h:76