llvm/Support/OptimizedStructLayout.h

0001 //===-- OptimizedStructLayout.h - Struct layout algorithm ---------*- C++ -*-=//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file provides an interface for laying out a sequence of fields
0011 /// as a struct in a way that attempts to minimizes the total space
0012 /// requirements of the struct while still satisfying the layout
0013 /// requirements of the individual fields.  The resulting layout may be
0014 /// substantially more compact than simply laying out the fields in their
0015 /// original order.
0016 ///
0017 /// Fields may be pre-assigned fixed offsets.  They may also be given sizes
0018 /// that are not multiples of their alignments.  There is no currently no
0019 /// way to describe that a field has interior padding that other fields may
0020 /// be allocated into.
0021 ///
0022 /// This algorithm does not claim to be "optimal" for several reasons:
0023 ///
0024 /// - First, it does not guarantee that the result is minimal in size.
0025 ///   There is no known efficient algoorithm to achieve minimality for
0026 ///   unrestricted inputs.  Nonetheless, this algorithm
0027 ///
0028 /// - Second, there are other ways that a struct layout could be optimized
0029 ///   besides space usage, such as locality.  This layout may have a mixed
0030 ///   impact on locality: less overall memory may be used, but adjacent
0031 ///   fields in the original array may be moved further from one another.
0032 ///
0033 //===----------------------------------------------------------------------===//
0034
0035 #ifndef LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H
0036 #define LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H
0037
0038 #include "llvm/Support/Alignment.h"
0039 #include "llvm/ADT/ArrayRef.h"
0040 #include <utility>
0041
0042 namespace llvm {
0043
0044 /// A field in a structure.
0045 struct OptimizedStructLayoutField {
0046   /// A special value for Offset indicating that the field can be moved
0047   /// anywhere.
0048   static constexpr uint64_t FlexibleOffset = ~(uint64_t)0;
0049
0050   OptimizedStructLayoutField(const void *Id, uint64_t Size, Align Alignment,
0051                              uint64_t FixedOffset = FlexibleOffset)
0052       : Offset(FixedOffset), Size(Size), Id(Id), Alignment(Alignment) {
0053     assert(Size > 0 && "adding an empty field to the layout");
0054   }
0055
0056   /// The offset of this field in the final layout.  If this is
0057   /// initialized to FlexibleOffset, layout will overwrite it with
0058   /// the assigned offset of the field.
0059   uint64_t Offset;
0060
0061   /// The required size of this field in bytes.  Does not have to be
0062   /// a multiple of Alignment.  Must be non-zero.
0063   uint64_t Size;
0064
0065   /// A opaque value which uniquely identifies this field.
0066   const void *Id;
0067
0068   /// Private scratch space for the algorithm.  The implementation
0069   /// must treat this as uninitialized memory on entry.
0070   void *Scratch;
0071
0072   /// The required alignment of this field.
0073   Align Alignment;
0074
0075   /// Return true if this field has been assigned a fixed offset.
0076   /// After layout, this will be true of all the fields.
0077   bool hasFixedOffset() const {
0078     return (Offset != FlexibleOffset);
0079   }
0080
0081   /// Given that this field has a fixed offset, return the offset
0082   /// of the first byte following it.
0083   uint64_t getEndOffset() const {
0084     assert(hasFixedOffset());
0085     return Offset + Size;
0086   }
0087 };
0088
0089 /// Compute a layout for a struct containing the given fields, making a
0090 /// best-effort attempt to minimize the amount of space required.
0091 ///
0092 /// Two features are supported which require a more careful solution
0093 /// than the well-known "sort by decreasing alignment" solution:
0094 ///
0095 /// - Fields may be assigned a fixed offset in the layout.  If there are
0096 ///   gaps among the fixed-offset fields, the algorithm may attempt
0097 ///   to allocate flexible-offset fields into those gaps.  If that's
0098 ///   undesirable, the caller should "block out" those gaps by e.g.
0099 ///   just creating a single fixed-offset field that represents the
0100 ///   entire "header".
0101 ///
0102 /// - The size of a field is not required to be a multiple of, or even
0103 ///   greater than, the field's required alignment.  The only constraint
0104 ///   on fields is that they must not be zero-sized.
0105 ///
0106 /// To simplify the implementation, any fixed-offset fields in the
0107 /// layout must appear at the start of the field array, and they must
0108 /// be ordered by increasing offset.
0109 ///
0110 /// The algorithm will produce a guaranteed-minimal layout with no
0111 /// interior padding in the following "C-style" case:
0112 ///
0113 /// - every field's size is a multiple of its required alignment and
0114 /// - either no fields have initially fixed offsets, or the fixed-offset
0115 ///   fields have no interior padding and end at an offset that is at
0116 ///   least as aligned as all the flexible-offset fields.
0117 ///
0118 /// Otherwise, while the algorithm will make a best-effort attempt to
0119 /// avoid padding, it cannot guarantee a minimal layout, as there is
0120 /// no known efficient algorithm for doing so.
0121 ///
0122 /// The layout produced by this algorithm may not be stable across LLVM
0123 /// releases.  Do not use this anywhere where ABI stability is required.
0124 ///
0125 /// Flexible-offset fields with the same size and alignment will be ordered
0126 /// the same way they were in the initial array.  Otherwise the current
0127 /// algorithm makes no effort to preserve the initial order of
0128 /// flexible-offset fields.
0129 ///
0130 /// On return, all fields will have been assigned a fixed offset, and the
0131 /// array will be sorted in order of ascending offsets.  Note that this
0132 /// means that the fixed-offset fields may no longer form a strict prefix
0133 /// if there's any padding before they end.
0134 ///
0135 /// The return value is the total size of the struct and its required
0136 /// alignment.  Note that the total size is not rounded up to a multiple
0137 /// of the required alignment; clients which require this can do so easily.
0138 std::pair<uint64_t, Align> performOptimizedStructLayout(
0139                         MutableArrayRef<OptimizedStructLayoutField> Fields);
0140
0141 } // namespace llvm
0142
0143 #endif