1//===-- OptimizedStructLayout.h - Struct layout algorithm ---------*- C++ -*-=// 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 7//===----------------------------------------------------------------------===// 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 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 22/// This algorithm does not claim to be "optimal" for several reasons: 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 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. 33//===----------------------------------------------------------------------===// 35#ifndef LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H 36#define LLVM_SUPPORT_OPTIMIZEDSTRUCTLAYOUT_H 44/// A field in a structure. 46 /// A special value for Offset indicating that the field can be moved 53assert(
Size > 0 &&
"adding an empty field to the layout");
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. 61 /// The required size of this field in bytes. Does not have to be 62 /// a multiple of Alignment. Must be non-zero. 65 /// A opaque value which uniquely identifies this field. 68 /// Private scratch space for the algorithm. The implementation 69 /// must treat this as uninitialized memory on entry. 72 /// The required alignment of this field. 75 /// Return true if this field has been assigned a fixed offset. 76 /// After layout, this will be true of all the fields. 81 /// Given that this field has a fixed offset, return the offset 82 /// of the first byte following it. 89/// Compute a layout for a struct containing the given fields, making a 90/// best-effort attempt to minimize the amount of space required. 92/// Two features are supported which require a more careful solution 93/// than the well-known "sort by decreasing alignment" solution: 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 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. 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. 110/// The algorithm will produce a guaranteed-minimal layout with no 111/// interior padding in the following "C-style" case: 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. 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. 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. 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. 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. 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. 139 MutableArrayRef<OptimizedStructLayoutField> Fields);
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This is an optimization pass for GlobalISel generic memory operations.
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...
This struct is a compact representation of a valid (non-zero power of two) alignment.
const void * Id
A opaque value which uniquely identifies this field.
Align Alignment
The required alignment of this field.
uint64_t getEndOffset() const
Given that this field has a fixed offset, return the offset of the first byte following it.
void * Scratch
Private scratch space for the algorithm.
bool hasFixedOffset() const
Return true if this field has been assigned a fixed offset.
uint64_t Offset
The offset of this field in the final layout.
OptimizedStructLayoutField(const void *Id, uint64_t Size, Align Alignment, uint64_t FixedOffset=FlexibleOffset)
uint64_t Size
The required size of this field in bytes.
static constexpr uint64_t FlexibleOffset
A special value for Offset indicating that the field can be moved anywhere.
