1//===-- OptimizedStructLayout.h - Struct layout algorithm ---------*- C++ -*-=//
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/// \file
10/// This file provides an interface for laying out a sequence of fields
11/// as a struct in a way that attempts to minimizes the total space
12/// requirements of the struct while still satisfying the layout
13/// requirements of the individual fields. The resulting layout may be
14/// substantially more compact than simply laying out the fields in their
15/// original order.
16///
17/// Fields may be pre-assigned fixed offsets. They may also be given sizes
18/// that are not multiples of their alignments. There is no currently no
19/// way to describe that a field has interior padding that other fields may
20/// be allocated into.
21///
22/// This algorithm does not claim to be "optimal" for several reasons:
23///
24/// - First, it does not guarantee that the result is minimal in size.
25/// There is no known efficient algoorithm to achieve minimality for
26/// unrestricted inputs. Nonetheless, this algorithm
27///
28/// - Second, there are other ways that a struct layout could be optimized
29/// besides space usage, such as locality. This layout may have a mixed
30/// impact on locality: less overall memory may be used, but adjacent
31/// fields in the original array may be moved further from one another.
32///
33//===----------------------------------------------------------------------===//
34
35#ifndef LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H
36#define LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H
37
38#include "llvm/Support/Alignment.h"
39#include "llvm/ADT/ArrayRef.h"
40#include <utility>
41
42namespace llvm {
43
44/// A field in a structure.
45struct OptimizedStructLayoutField {
46 /// A special value for Offset indicating that the field can be moved
47 /// anywhere.
48 static constexpr uint64_t FlexibleOffset = ~(uint64_t)0;
49
50 OptimizedStructLayoutField(const void *Id, uint64_t Size, Align Alignment,
51 uint64_t FixedOffset = FlexibleOffset)
52 : Offset(FixedOffset), Size(Size), Id(Id), Alignment(Alignment) {
53 assert(Size > 0 && "adding an empty field to the layout");
54 }
55
56 /// The offset of this field in the final layout. If this is
57 /// initialized to FlexibleOffset, layout will overwrite it with
58 /// the assigned offset of the field.
59 uint64_t Offset;
60
61 /// The required size of this field in bytes. Does not have to be
62 /// a multiple of Alignment. Must be non-zero.
63 uint64_t Size;
64
65 /// A opaque value which uniquely identifies this field.
66 const void *Id;
67
68 /// Private scratch space for the algorithm. The implementation
69 /// must treat this as uninitialized memory on entry.
70 void *Scratch;
71
72 /// The required alignment of this field.
73 Align Alignment;
74
75 /// Return true if this field has been assigned a fixed offset.
76 /// After layout, this will be true of all the fields.
77 bool hasFixedOffset() const {
78 return (Offset != FlexibleOffset);
79 }
80
81 /// Given that this field has a fixed offset, return the offset
82 /// of the first byte following it.
83 uint64_t getEndOffset() const {
84 assert(hasFixedOffset());
85 return Offset + Size;
86 }
87};
88
89/// Compute a layout for a struct containing the given fields, making a
90/// best-effort attempt to minimize the amount of space required.
91///
92/// Two features are supported which require a more careful solution
93/// than the well-known "sort by decreasing alignment" solution:
94///
95/// - Fields may be assigned a fixed offset in the layout. If there are
96/// gaps among the fixed-offset fields, the algorithm may attempt
97/// to allocate flexible-offset fields into those gaps. If that's
98/// undesirable, the caller should "block out" those gaps by e.g.
99/// just creating a single fixed-offset field that represents the
100/// entire "header".
101///
102/// - The size of a field is not required to be a multiple of, or even
103/// greater than, the field's required alignment. The only constraint
104/// on fields is that they must not be zero-sized.
105///
106/// To simplify the implementation, any fixed-offset fields in the
107/// layout must appear at the start of the field array, and they must
108/// be ordered by increasing offset.
109///
110/// The algorithm will produce a guaranteed-minimal layout with no
111/// interior padding in the following "C-style" case:
112///
113/// - every field's size is a multiple of its required alignment and
114/// - either no fields have initially fixed offsets, or the fixed-offset
115/// fields have no interior padding and end at an offset that is at
116/// least as aligned as all the flexible-offset fields.
117///
118/// Otherwise, while the algorithm will make a best-effort attempt to
119/// avoid padding, it cannot guarantee a minimal layout, as there is
120/// no known efficient algorithm for doing so.
121///
122/// The layout produced by this algorithm may not be stable across LLVM
123/// releases. Do not use this anywhere where ABI stability is required.
124///
125/// Flexible-offset fields with the same size and alignment will be ordered
126/// the same way they were in the initial array. Otherwise the current
127/// algorithm makes no effort to preserve the initial order of
128/// flexible-offset fields.
129///
130/// On return, all fields will have been assigned a fixed offset, and the
131/// array will be sorted in order of ascending offsets. Note that this
132/// means that the fixed-offset fields may no longer form a strict prefix
133/// if there's any padding before they end.
134///
135/// The return value is the total size of the struct and its required
136/// alignment. Note that the total size is not rounded up to a multiple
137/// of the required alignment; clients which require this can do so easily.
138std::pair<uint64_t, Align> performOptimizedStructLayout(
139 MutableArrayRef<OptimizedStructLayoutField> Fields);
140
141} // namespace llvm
142
143#endif
144

source code of llvm/include/llvm/Support/OptimizedStructLayout.h