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/ADT/Optional.h"
25 #include "llvm/Support/MathExtras.h"
26 #include <cassert>
27 #ifndef NDEBUG
28 #include <string>
29 #endif // NDEBUG
30
31 namespace 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.
39 struct Align {
40 private:
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
66 public:
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
AlignAlign76 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.
valueAlign85 uint64_t value() const { return uint64_t(1) << ShiftValue; }
86
87 /// Allow constructions of constexpr Align.
ConstantAlign88 template <size_t kValue> constexpr static LogValue Constant() {
89 return LogValue{static_cast<uint8_t>(CTLog2<kValue>())};
90 }
91
92 /// Allow constructions of constexpr Align from types.
93 /// Compile time equivalent to Align(alignof(T)).
OfAlign94 template <typename T> constexpr static LogValue Of() {
95 return Constant<std::alignment_of<T>::value>();
96 }
97
98 /// Constexpr constructor from LogValue type.
AlignAlign99 constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
100 };
101
102 /// Treats the value 0 as a 1, so Align is always at least 1.
assumeAligned(uint64_t Value)103 inline Align assumeAligned(uint64_t Value) {
104 return Value ? Align(Value) : Align();
105 }
106
107 /// This struct is a compact representation of a valid (power of two) or
108 /// undefined (0) alignment.
109 struct MaybeAlign : public llvm::Optional<Align> {
110 private:
111 using UP = llvm::Optional<Align>;
112
113 public:
114 /// Default is undefined.
115 MaybeAlign() = default;
116 /// Do not perform checks in case of copy/move construct/assign, because the
117 /// checks have been performed when building `Other`.
118 MaybeAlign(const MaybeAlign &Other) = default;
119 MaybeAlign &operator=(const MaybeAlign &Other) = default;
120 MaybeAlign(MaybeAlign &&Other) = default;
121 MaybeAlign &operator=(MaybeAlign &&Other) = default;
122
123 /// Use llvm::Optional<Align> constructor.
124 using UP::UP;
125
MaybeAlignMaybeAlign126 explicit MaybeAlign(uint64_t Value) {
127 assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&
128 "Alignment is neither 0 nor a power of 2");
129 if (Value)
130 emplace(Value);
131 }
132
133 /// For convenience, returns a valid alignment or 1 if undefined.
valueOrOneMaybeAlign134 Align valueOrOne() const { return hasValue() ? getValue() : Align(); }
135 };
136
137 /// Checks that SizeInBytes is a multiple of the alignment.
isAligned(Align Lhs,uint64_t SizeInBytes)138 inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
139 return SizeInBytes % Lhs.value() == 0;
140 }
141
142 /// Checks that Addr is a multiple of the alignment.
isAddrAligned(Align Lhs,const void * Addr)143 inline bool isAddrAligned(Align Lhs, const void *Addr) {
144 return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
145 }
146
147 /// Returns a multiple of A needed to store `Size` bytes.
alignTo(uint64_t Size,Align A)148 inline uint64_t alignTo(uint64_t Size, Align A) {
149 const uint64_t Value = A.value();
150 // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
151
152 // The division followed by a multiplication can be thought of as a right
153 // shift followed by a left shift which zeros out the extra bits produced in
154 // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
155 // are just zero.
156
157 // Most compilers can generate this code but the pattern may be missed when
158 // multiple functions gets inlined.
159 return (Size + Value - 1) & ~(Value - 1U);
160 }
161
162 /// If non-zero \p Skew is specified, the return value will be a minimal integer
163 /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
164 /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
165 /// Skew mod \p A'.
166 ///
167 /// Examples:
168 /// \code
169 /// alignTo(5, Align(8), 7) = 7
170 /// alignTo(17, Align(8), 1) = 17
171 /// alignTo(~0LL, Align(8), 3) = 3
172 /// \endcode
alignTo(uint64_t Size,Align A,uint64_t Skew)173 inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) {
174 const uint64_t Value = A.value();
175 Skew %= Value;
176 return ((Size + Value - 1 - Skew) & ~(Value - 1U)) + Skew;
177 }
178
179 /// Returns a multiple of A needed to store `Size` bytes.
180 /// Returns `Size` if current alignment is undefined.
alignTo(uint64_t Size,MaybeAlign A)181 inline uint64_t alignTo(uint64_t Size, MaybeAlign A) {
182 return A ? alignTo(Size, A.getValue()) : Size;
183 }
184
185 /// Aligns `Addr` to `Alignment` bytes, rounding up.
alignAddr(const void * Addr,Align Alignment)186 inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
187 uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
188 assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
189 ArithAddr &&
190 "Overflow");
191 return alignTo(ArithAddr, Alignment);
192 }
193
194 /// Returns the offset to the next integer (mod 2**64) that is greater than
195 /// or equal to \p Value and is a multiple of \p Align.
offsetToAlignment(uint64_t Value,Align Alignment)196 inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
197 return alignTo(Value, Alignment) - Value;
198 }
199
200 /// Returns the necessary adjustment for aligning `Addr` to `Alignment`
201 /// bytes, rounding up.
offsetToAlignedAddr(const void * Addr,Align Alignment)202 inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
203 return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
204 }
205
206 /// Returns the log2 of the alignment.
Log2(Align A)207 inline unsigned Log2(Align A) { return A.ShiftValue; }
208
209 /// Returns the alignment that satisfies both alignments.
210 /// Same semantic as MinAlign.
commonAlignment(Align A,Align B)211 inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }
212
213 /// Returns the alignment that satisfies both alignments.
214 /// Same semantic as MinAlign.
commonAlignment(Align A,uint64_t Offset)215 inline Align commonAlignment(Align A, uint64_t Offset) {
216 return Align(MinAlign(A.value(), Offset));
217 }
218
219 /// Returns the alignment that satisfies both alignments.
220 /// Same semantic as MinAlign.
commonAlignment(MaybeAlign A,MaybeAlign B)221 inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) {
222 return A && B ? commonAlignment(*A, *B) : A ? A : B;
223 }
224
225 /// Returns the alignment that satisfies both alignments.
226 /// Same semantic as MinAlign.
commonAlignment(MaybeAlign A,uint64_t Offset)227 inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) {
228 return MaybeAlign(MinAlign((*A).value(), Offset));
229 }
230
231 /// Returns a representation of the alignment that encodes undefined as 0.
encode(MaybeAlign A)232 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
233
234 /// Dual operation of the encode function above.
decodeMaybeAlign(unsigned Value)235 inline MaybeAlign decodeMaybeAlign(unsigned Value) {
236 if (Value == 0)
237 return MaybeAlign();
238 Align Out;
239 Out.ShiftValue = Value - 1;
240 return Out;
241 }
242
243 /// Returns a representation of the alignment, the encoded value is positive by
244 /// definition.
encode(Align A)245 inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
246
247 /// Comparisons between Align and scalars. Rhs must be positive.
248 inline bool operator==(Align Lhs, uint64_t Rhs) {
249 ALIGN_CHECK_ISPOSITIVE(Rhs);
250 return Lhs.value() == Rhs;
251 }
252 inline bool operator!=(Align Lhs, uint64_t Rhs) {
253 ALIGN_CHECK_ISPOSITIVE(Rhs);
254 return Lhs.value() != Rhs;
255 }
256 inline bool operator<=(Align Lhs, uint64_t Rhs) {
257 ALIGN_CHECK_ISPOSITIVE(Rhs);
258 return Lhs.value() <= Rhs;
259 }
260 inline bool operator>=(Align Lhs, uint64_t Rhs) {
261 ALIGN_CHECK_ISPOSITIVE(Rhs);
262 return Lhs.value() >= Rhs;
263 }
264 inline bool operator<(Align Lhs, uint64_t Rhs) {
265 ALIGN_CHECK_ISPOSITIVE(Rhs);
266 return Lhs.value() < Rhs;
267 }
268 inline bool operator>(Align Lhs, uint64_t Rhs) {
269 ALIGN_CHECK_ISPOSITIVE(Rhs);
270 return Lhs.value() > Rhs;
271 }
272
273 /// Comparisons between MaybeAlign and scalars.
274 inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
275 return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
276 }
277 inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
278 return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
279 }
280
281 /// Comparisons operators between Align.
282 inline bool operator==(Align Lhs, Align Rhs) {
283 return Lhs.ShiftValue == Rhs.ShiftValue;
284 }
285 inline bool operator!=(Align Lhs, Align Rhs) {
286 return Lhs.ShiftValue != Rhs.ShiftValue;
287 }
288 inline bool operator<=(Align Lhs, Align Rhs) {
289 return Lhs.ShiftValue <= Rhs.ShiftValue;
290 }
291 inline bool operator>=(Align Lhs, Align Rhs) {
292 return Lhs.ShiftValue >= Rhs.ShiftValue;
293 }
294 inline bool operator<(Align Lhs, Align Rhs) {
295 return Lhs.ShiftValue < Rhs.ShiftValue;
296 }
297 inline bool operator>(Align Lhs, Align Rhs) {
298 return Lhs.ShiftValue > Rhs.ShiftValue;
299 }
300
301 // Don't allow relational comparisons with MaybeAlign.
302 bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
303 bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
304 bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
305 bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
306
307 bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
308 bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
309 bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
310 bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
311
312 bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
313 bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
314 bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
315 bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
316
317 inline Align operator*(Align Lhs, uint64_t Rhs) {
318 assert(Rhs > 0 && "Rhs must be positive");
319 return Align(Lhs.value() * Rhs);
320 }
321
322 inline MaybeAlign operator*(MaybeAlign Lhs, uint64_t Rhs) {
323 assert(Rhs > 0 && "Rhs must be positive");
324 return Lhs ? Lhs.getValue() * Rhs : MaybeAlign();
325 }
326
327 inline Align operator/(Align Lhs, uint64_t Divisor) {
328 assert(llvm::isPowerOf2_64(Divisor) &&
329 "Divisor must be positive and a power of 2");
330 assert(Lhs != 1 && "Can't halve byte alignment");
331 return Align(Lhs.value() / Divisor);
332 }
333
334 inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) {
335 assert(llvm::isPowerOf2_64(Divisor) &&
336 "Divisor must be positive and a power of 2");
337 return Lhs ? Lhs.getValue() / Divisor : MaybeAlign();
338 }
339
max(MaybeAlign Lhs,Align Rhs)340 inline Align max(MaybeAlign Lhs, Align Rhs) {
341 return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
342 }
343
max(Align Lhs,MaybeAlign Rhs)344 inline Align max(Align Lhs, MaybeAlign Rhs) {
345 return Rhs && *Rhs > Lhs ? *Rhs : Lhs;
346 }
347
348 #ifndef NDEBUG
349 // For usage in LLVM_DEBUG macros.
DebugStr(const Align & A)350 inline std::string DebugStr(const Align &A) {
351 return std::to_string(A.value());
352 }
353 // For usage in LLVM_DEBUG macros.
DebugStr(const MaybeAlign & MA)354 inline std::string DebugStr(const MaybeAlign &MA) {
355 if (MA)
356 return std::to_string(MA->value());
357 return "None";
358 }
359 #endif // NDEBUG
360
361 #undef ALIGN_CHECK_ISPOSITIVE
362
363 } // namespace llvm
364
365 #endif // LLVM_SUPPORT_ALIGNMENT_H_
366