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