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/ADT/ArrayRef.h" 39 #include "llvm/Support/Alignment.h" 40 #include "llvm/Support/Compiler.h" 41 #include <utility> 42 43 namespace llvm { 44 45 /// A field in a structure. 46 struct OptimizedStructLayoutField { 47 /// A special value for Offset indicating that the field can be moved 48 /// anywhere. 49 static constexpr uint64_t FlexibleOffset = ~(uint64_t)0; 50 51 OptimizedStructLayoutField(const void *Id, uint64_t Size, Align Alignment, 52 uint64_t FixedOffset = FlexibleOffset) 53 : Offset(FixedOffset), Size(Size), Id(Id), Alignment(Alignment) { 54 assert(Size > 0 && "adding an empty field to the layout"); 55 } 56 57 /// The offset of this field in the final layout. If this is 58 /// initialized to FlexibleOffset, layout will overwrite it with 59 /// the assigned offset of the field. 60 uint64_t Offset; 61 62 /// The required size of this field in bytes. Does not have to be 63 /// a multiple of Alignment. Must be non-zero. 64 uint64_t Size; 65 66 /// A opaque value which uniquely identifies this field. 67 const void *Id; 68 69 /// Private scratch space for the algorithm. The implementation 70 /// must treat this as uninitialized memory on entry. 71 void *Scratch; 72 73 /// The required alignment of this field. 74 Align Alignment; 75 76 /// Return true if this field has been assigned a fixed offset. 77 /// After layout, this will be true of all the fields. 78 bool hasFixedOffset() const { 79 return (Offset != FlexibleOffset); 80 } 81 82 /// Given that this field has a fixed offset, return the offset 83 /// of the first byte following it. 84 uint64_t getEndOffset() const { 85 assert(hasFixedOffset()); 86 return Offset + Size; 87 } 88 }; 89 90 /// Compute a layout for a struct containing the given fields, making a 91 /// best-effort attempt to minimize the amount of space required. 92 /// 93 /// Two features are supported which require a more careful solution 94 /// than the well-known "sort by decreasing alignment" solution: 95 /// 96 /// - Fields may be assigned a fixed offset in the layout. If there are 97 /// gaps among the fixed-offset fields, the algorithm may attempt 98 /// to allocate flexible-offset fields into those gaps. If that's 99 /// undesirable, the caller should "block out" those gaps by e.g. 100 /// just creating a single fixed-offset field that represents the 101 /// entire "header". 102 /// 103 /// - The size of a field is not required to be a multiple of, or even 104 /// greater than, the field's required alignment. The only constraint 105 /// on fields is that they must not be zero-sized. 106 /// 107 /// To simplify the implementation, any fixed-offset fields in the 108 /// layout must appear at the start of the field array, and they must 109 /// be ordered by increasing offset. 110 /// 111 /// The algorithm will produce a guaranteed-minimal layout with no 112 /// interior padding in the following "C-style" case: 113 /// 114 /// - every field's size is a multiple of its required alignment and 115 /// - either no fields have initially fixed offsets, or the fixed-offset 116 /// fields have no interior padding and end at an offset that is at 117 /// least as aligned as all the flexible-offset fields. 118 /// 119 /// Otherwise, while the algorithm will make a best-effort attempt to 120 /// avoid padding, it cannot guarantee a minimal layout, as there is 121 /// no known efficient algorithm for doing so. 122 /// 123 /// The layout produced by this algorithm may not be stable across LLVM 124 /// releases. Do not use this anywhere where ABI stability is required. 125 /// 126 /// Flexible-offset fields with the same size and alignment will be ordered 127 /// the same way they were in the initial array. Otherwise the current 128 /// algorithm makes no effort to preserve the initial order of 129 /// flexible-offset fields. 130 /// 131 /// On return, all fields will have been assigned a fixed offset, and the 132 /// array will be sorted in order of ascending offsets. Note that this 133 /// means that the fixed-offset fields may no longer form a strict prefix 134 /// if there's any padding before they end. 135 /// 136 /// The return value is the total size of the struct and its required 137 /// alignment. Note that the total size is not rounded up to a multiple 138 /// of the required alignment; clients which require this can do so easily. 139 LLVM_ABI std::pair<uint64_t, Align> performOptimizedStructLayout( 140 MutableArrayRef<OptimizedStructLayoutField> Fields); 141 142 } // namespace llvm 143 144 #endif 145