LLVM  13.0.0git
OptimizedStructLayout.h
Go to the documentation of this file.
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 
42 namespace llvm {
43 
44 /// A field in a structure.
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 
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.
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 {
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.
138 std::pair<uint64_t, Align> performOptimizedStructLayout(
139  MutableArrayRef<OptimizedStructLayoutField> Fields);
140 
141 } // namespace llvm
142 
143 #endif
llvm
Definition: AllocatorList.h:23
llvm::OptimizedStructLayoutField::Offset
uint64_t Offset
The offset of this field in the final layout.
Definition: OptimizedStructLayout.h:59
llvm::OptimizedStructLayoutField::OptimizedStructLayoutField
OptimizedStructLayoutField(const void *Id, uint64_t Size, Align Alignment, uint64_t FixedOffset=FlexibleOffset)
Definition: OptimizedStructLayout.h:50
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::OptimizedStructLayoutField::Alignment
Align Alignment
The required alignment of this field.
Definition: OptimizedStructLayout.h:73
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:83
llvm::OptimizedStructLayoutField::Size
uint64_t Size
The required size of this field in bytes.
Definition: OptimizedStructLayout.h:63
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
llvm::OptimizedStructLayoutField::FlexibleOffset
static constexpr uint64_t FlexibleOffset
A special value for Offset indicating that the field can be moved anywhere.
Definition: OptimizedStructLayout.h:48
Alignment.h
llvm::OptimizedStructLayoutField::Scratch
void * Scratch
Private scratch space for the algorithm.
Definition: OptimizedStructLayout.h:70
llvm::OptimizedStructLayoutField::Id
const void * Id
A opaque value which uniquely identifies this field.
Definition: OptimizedStructLayout.h:66
llvm::OptimizedStructLayoutField
A field in a structure.
Definition: OptimizedStructLayout.h:45
llvm::OptimizedStructLayoutField::hasFixedOffset
bool hasFixedOffset() const
Return true if this field has been assigned a fixed offset.
Definition: OptimizedStructLayout.h:77