1//===-- llvm/Support/Alignment.h - Useful alignment functions ---*- 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// This file contains types to represent alignments.
10// They are instrumented to guarantee some invariants are preserved and prevent
11// invalid manipulations.
12//
13// - Align represents an alignment in bytes, it is always set and always a valid
14// power of two, its minimum value is 1 which means no alignment requirements.
15//
16// - MaybeAlign is an optional type, it may be undefined or set. When it's set
17// you can get the underlying Align type by using the getValue() method.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_SUPPORT_ALIGNMENT_H_
22#define LLVM_SUPPORT_ALIGNMENT_H_
23
24#include "llvm/Support/MathExtras.h"
25#include <cassert>
26#include <optional>
27#ifndef NDEBUG
28#include <string>
29#endif // NDEBUG
30
31namespace llvm {
32
33#define ALIGN_CHECK_ISPOSITIVE(decl) \
34 assert(decl > 0 && (#decl " should be defined"))
35
36/// This struct is a compact representation of a valid (non-zero power of two)
37/// alignment.
38/// It is suitable for use as static global constants.
39struct Align {
40private:
41 uint8_t ShiftValue = 0; /// The log2 of the required alignment.
42 /// ShiftValue is less than 64 by construction.
43
44 friend struct MaybeAlign;
45 friend unsigned Log2(Align);
46 friend bool operator==(Align Lhs, Align Rhs);
47 friend bool operator!=(Align Lhs, Align Rhs);
48 friend bool operator<=(Align Lhs, Align Rhs);
49 friend bool operator>=(Align Lhs, Align Rhs);
50 friend bool operator<(Align Lhs, Align Rhs);
51 friend bool operator>(Align Lhs, Align Rhs);
52 friend unsigned encode(struct MaybeAlign A);
53 friend struct MaybeAlign decodeMaybeAlign(unsigned Value);
54
55 /// A trivial type to allow construction of constexpr Align.
56 /// This is currently needed to workaround a bug in GCC 5.3 which prevents
57 /// definition of constexpr assign operators.
58 /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
59 /// FIXME: Remove this, make all assign operators constexpr and introduce user
60 /// defined literals when we don't have to support GCC 5.3 anymore.
61 /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
62 struct LogValue {
63 uint8_t Log;
64 };
65
66public:
67 /// Default is byte-aligned.
68 constexpr Align() = default;
69 /// Do not perform checks in case of copy/move construct/assign, because the
70 /// checks have been performed when building `Other`.
71 constexpr Align(const Align &Other) = default;
72 constexpr Align(Align &&Other) = default;
73 Align &operator=(const Align &Other) = default;
74 Align &operator=(Align &&Other) = default;
75
76 explicit Align(uint64_t Value) {
77 assert(Value > 0 && "Value must not be 0");
78 assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2");
79 ShiftValue = Log2_64(Value);
80 assert(ShiftValue < 64 && "Broken invariant");
81 }
82
83 /// This is a hole in the type system and should not be abused.
84 /// Needed to interact with C for instance.
85 uint64_t value() const { return uint64_t(1) << ShiftValue; }
86
87 // Returns the previous alignment.
88 Align previous() const {
89 assert(ShiftValue != 0 && "Undefined operation");
90 Align Out;
91 Out.ShiftValue = ShiftValue - 1;
92 return Out;
93 }
94
95 /// Allow constructions of constexpr Align.
96 template <size_t kValue> constexpr static Align Constant() {
97 return LogValue{.Log: static_cast<uint8_t>(CTLog2<kValue>())};
98 }
99
100 /// Allow constructions of constexpr Align from types.
101 /// Compile time equivalent to Align(alignof(T)).
102 template <typename T> constexpr static Align Of() {
103 return Constant<std::alignment_of_v<T>>();
104 }
105
106 /// Constexpr constructor from LogValue type.
107 constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
108};
109
110/// Treats the value 0 as a 1, so Align is always at least 1.
111inline Align assumeAligned(uint64_t Value) {
112 return Value ? Align(Value) : Align();
113}
114
115/// This struct is a compact representation of a valid (power of two) or
116/// undefined (0) alignment.
117struct MaybeAlign : public std::optional<Align> {
118private:
119 using UP = std::optional<Align>;
120
121public:
122 /// Default is undefined.
123 MaybeAlign() = default;
124 /// Do not perform checks in case of copy/move construct/assign, because the
125 /// checks have been performed when building `Other`.
126 MaybeAlign(const MaybeAlign &Other) = default;
127 MaybeAlign &operator=(const MaybeAlign &Other) = default;
128 MaybeAlign(MaybeAlign &&Other) = default;
129 MaybeAlign &operator=(MaybeAlign &&Other) = default;
130
131 constexpr MaybeAlign(std::nullopt_t None) : UP(None) {}
132 constexpr MaybeAlign(Align Value) : UP(Value) {}
133 explicit MaybeAlign(uint64_t Value) {
134 assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&
135 "Alignment is neither 0 nor a power of 2");
136 if (Value)
137 emplace(args&: Value);
138 }
139
140 /// For convenience, returns a valid alignment or 1 if undefined.
141 Align valueOrOne() const { return value_or(u: Align()); }
142};
143
144/// Checks that SizeInBytes is a multiple of the alignment.
145inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
146 return SizeInBytes % Lhs.value() == 0;
147}
148
149/// Checks that Addr is a multiple of the alignment.
150inline bool isAddrAligned(Align Lhs, const void *Addr) {
151 return isAligned(Lhs, SizeInBytes: reinterpret_cast<uintptr_t>(Addr));
152}
153
154/// Returns a multiple of A needed to store `Size` bytes.
155inline uint64_t alignTo(uint64_t Size, Align A) {
156 const uint64_t Value = A.value();
157 // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
158
159 // The division followed by a multiplication can be thought of as a right
160 // shift followed by a left shift which zeros out the extra bits produced in
161 // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
162 // are just zero.
163
164 // Most compilers can generate this code but the pattern may be missed when
165 // multiple functions gets inlined.
166 return (Size + Value - 1) & ~(Value - 1U);
167}
168
169/// If non-zero \p Skew is specified, the return value will be a minimal integer
170/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
171/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
172/// Skew mod \p A'.
173///
174/// Examples:
175/// \code
176/// alignTo(5, Align(8), 7) = 7
177/// alignTo(17, Align(8), 1) = 17
178/// alignTo(~0LL, Align(8), 3) = 3
179/// \endcode
180inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) {
181 const uint64_t Value = A.value();
182 Skew %= Value;
183 return alignTo(Size: Size - Skew, A) + Skew;
184}
185
186/// Aligns `Addr` to `Alignment` bytes, rounding up.
187inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
188 uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
189 assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
190 ArithAddr &&
191 "Overflow");
192 return alignTo(Size: ArithAddr, A: Alignment);
193}
194
195/// Returns the offset to the next integer (mod 2**64) that is greater than
196/// or equal to \p Value and is a multiple of \p Align.
197inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
198 return alignTo(Size: Value, A: Alignment) - Value;
199}
200
201/// Returns the necessary adjustment for aligning `Addr` to `Alignment`
202/// bytes, rounding up.
203inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
204 return offsetToAlignment(Value: reinterpret_cast<uintptr_t>(Addr), Alignment);
205}
206
207/// Returns the log2 of the alignment.
208inline unsigned Log2(Align A) { return A.ShiftValue; }
209
210/// Returns the alignment that satisfies both alignments.
211/// Same semantic as MinAlign.
212inline Align commonAlignment(Align A, uint64_t Offset) {
213 return Align(MinAlign(A: A.value(), B: Offset));
214}
215
216/// Returns a representation of the alignment that encodes undefined as 0.
217inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
218
219/// Dual operation of the encode function above.
220inline MaybeAlign decodeMaybeAlign(unsigned Value) {
221 if (Value == 0)
222 return MaybeAlign();
223 Align Out;
224 Out.ShiftValue = Value - 1;
225 return Out;
226}
227
228/// Returns a representation of the alignment, the encoded value is positive by
229/// definition.
230inline unsigned encode(Align A) { return encode(A: MaybeAlign(A)); }
231
232/// Comparisons between Align and scalars. Rhs must be positive.
233inline bool operator==(Align Lhs, uint64_t Rhs) {
234 ALIGN_CHECK_ISPOSITIVE(Rhs);
235 return Lhs.value() == Rhs;
236}
237inline bool operator!=(Align Lhs, uint64_t Rhs) {
238 ALIGN_CHECK_ISPOSITIVE(Rhs);
239 return Lhs.value() != Rhs;
240}
241inline bool operator<=(Align Lhs, uint64_t Rhs) {
242 ALIGN_CHECK_ISPOSITIVE(Rhs);
243 return Lhs.value() <= Rhs;
244}
245inline bool operator>=(Align Lhs, uint64_t Rhs) {
246 ALIGN_CHECK_ISPOSITIVE(Rhs);
247 return Lhs.value() >= Rhs;
248}
249inline bool operator<(Align Lhs, uint64_t Rhs) {
250 ALIGN_CHECK_ISPOSITIVE(Rhs);
251 return Lhs.value() < Rhs;
252}
253inline bool operator>(Align Lhs, uint64_t Rhs) {
254 ALIGN_CHECK_ISPOSITIVE(Rhs);
255 return Lhs.value() > Rhs;
256}
257
258/// Comparisons operators between Align.
259inline bool operator==(Align Lhs, Align Rhs) {
260 return Lhs.ShiftValue == Rhs.ShiftValue;
261}
262inline bool operator!=(Align Lhs, Align Rhs) {
263 return Lhs.ShiftValue != Rhs.ShiftValue;
264}
265inline bool operator<=(Align Lhs, Align Rhs) {
266 return Lhs.ShiftValue <= Rhs.ShiftValue;
267}
268inline bool operator>=(Align Lhs, Align Rhs) {
269 return Lhs.ShiftValue >= Rhs.ShiftValue;
270}
271inline bool operator<(Align Lhs, Align Rhs) {
272 return Lhs.ShiftValue < Rhs.ShiftValue;
273}
274inline bool operator>(Align Lhs, Align Rhs) {
275 return Lhs.ShiftValue > Rhs.ShiftValue;
276}
277
278// Don't allow relational comparisons with MaybeAlign.
279bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
280bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
281bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
282bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
283
284bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
285bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
286bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
287bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
288
289bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
290bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
291bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
292bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
293
294// Allow equality comparisons between Align and MaybeAlign.
295inline bool operator==(MaybeAlign Lhs, Align Rhs) { return Lhs && *Lhs == Rhs; }
296inline bool operator!=(MaybeAlign Lhs, Align Rhs) { return !(Lhs == Rhs); }
297inline bool operator==(Align Lhs, MaybeAlign Rhs) { return Rhs == Lhs; }
298inline bool operator!=(Align Lhs, MaybeAlign Rhs) { return !(Rhs == Lhs); }
299// Allow equality comparisons with MaybeAlign.
300inline bool operator==(MaybeAlign Lhs, MaybeAlign Rhs) {
301 return (Lhs && Rhs && (*Lhs == *Rhs)) || (!Lhs && !Rhs);
302}
303inline bool operator!=(MaybeAlign Lhs, MaybeAlign Rhs) { return !(Lhs == Rhs); }
304// Allow equality comparisons with std::nullopt.
305inline bool operator==(MaybeAlign Lhs, std::nullopt_t) { return !bool(Lhs); }
306inline bool operator!=(MaybeAlign Lhs, std::nullopt_t) { return bool(Lhs); }
307inline bool operator==(std::nullopt_t, MaybeAlign Rhs) { return !bool(Rhs); }
308inline bool operator!=(std::nullopt_t, MaybeAlign Rhs) { return bool(Rhs); }
309
310#ifndef NDEBUG
311// For usage in LLVM_DEBUG macros.
312inline std::string DebugStr(const Align &A) {
313 return std::to_string(val: A.value());
314}
315// For usage in LLVM_DEBUG macros.
316inline std::string DebugStr(const MaybeAlign &MA) {
317 if (MA)
318 return std::to_string(val: MA->value());
319 return "None";
320}
321#endif // NDEBUG
322
323#undef ALIGN_CHECK_ISPOSITIVE
324
325} // namespace llvm
326
327#endif // LLVM_SUPPORT_ALIGNMENT_H_
328

source code of llvm/include/llvm/Support/Alignment.h