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 
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 
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{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<T>::value>();
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.
111 inline 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.
117 struct MaybeAlign : public std::optional<Align> {
118 private:
119   using UP = std::optional<Align>;
120 
121 public:
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(Value);
138   }
139 
140   /// For convenience, returns a valid alignment or 1 if undefined.
141   Align valueOrOne() const { return value_or(Align()); }
142 };
143 
144 /// Checks that SizeInBytes is a multiple of the alignment.
145 inline 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.
150 inline bool isAddrAligned(Align Lhs, const void *Addr) {
151   return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
152 }
153 
154 /// Returns a multiple of A needed to store `Size` bytes.
155 inline 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
180 inline 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 - Skew, A) + Skew;
184 }
185 
186 /// Aligns `Addr` to `Alignment` bytes, rounding up.
187 inline 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(ArithAddr, 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.
197 inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
198   return alignTo(Value, Alignment) - Value;
199 }
200 
201 /// Returns the necessary adjustment for aligning `Addr` to `Alignment`
202 /// bytes, rounding up.
203 inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
204   return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
205 }
206 
207 /// Returns the log2 of the alignment.
208 inline unsigned Log2(Align A) { return A.ShiftValue; }
209 
210 /// Returns the alignment that satisfies both alignments.
211 /// Same semantic as MinAlign.
212 inline Align commonAlignment(Align A, uint64_t Offset) {
213   return Align(MinAlign(A.value(), Offset));
214 }
215 
216 /// Returns a representation of the alignment that encodes undefined as 0.
217 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
218 
219 /// Dual operation of the encode function above.
220 inline 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.
230 inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
231 
232 /// Comparisons between Align and scalars. Rhs must be positive.
233 inline bool operator==(Align Lhs, uint64_t Rhs) {
234   ALIGN_CHECK_ISPOSITIVE(Rhs);
235   return Lhs.value() == Rhs;
236 }
237 inline bool operator!=(Align Lhs, uint64_t Rhs) {
238   ALIGN_CHECK_ISPOSITIVE(Rhs);
239   return Lhs.value() != Rhs;
240 }
241 inline bool operator<=(Align Lhs, uint64_t Rhs) {
242   ALIGN_CHECK_ISPOSITIVE(Rhs);
243   return Lhs.value() <= Rhs;
244 }
245 inline bool operator>=(Align Lhs, uint64_t Rhs) {
246   ALIGN_CHECK_ISPOSITIVE(Rhs);
247   return Lhs.value() >= Rhs;
248 }
249 inline bool operator<(Align Lhs, uint64_t Rhs) {
250   ALIGN_CHECK_ISPOSITIVE(Rhs);
251   return Lhs.value() < Rhs;
252 }
253 inline bool operator>(Align Lhs, uint64_t Rhs) {
254   ALIGN_CHECK_ISPOSITIVE(Rhs);
255   return Lhs.value() > Rhs;
256 }
257 
258 /// Comparisons operators between Align.
259 inline bool operator==(Align Lhs, Align Rhs) {
260   return Lhs.ShiftValue == Rhs.ShiftValue;
261 }
262 inline bool operator!=(Align Lhs, Align Rhs) {
263   return Lhs.ShiftValue != Rhs.ShiftValue;
264 }
265 inline bool operator<=(Align Lhs, Align Rhs) {
266   return Lhs.ShiftValue <= Rhs.ShiftValue;
267 }
268 inline bool operator>=(Align Lhs, Align Rhs) {
269   return Lhs.ShiftValue >= Rhs.ShiftValue;
270 }
271 inline bool operator<(Align Lhs, Align Rhs) {
272   return Lhs.ShiftValue < Rhs.ShiftValue;
273 }
274 inline bool operator>(Align Lhs, Align Rhs) {
275   return Lhs.ShiftValue > Rhs.ShiftValue;
276 }
277 
278 // Don't allow relational comparisons with MaybeAlign.
279 bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
280 bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
281 bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
282 bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
283 
284 bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
285 bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
286 bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
287 bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
288 
289 bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
290 bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
291 bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
292 bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
293 
294 // Allow equality comparisons between Align and MaybeAlign.
295 inline bool operator==(MaybeAlign Lhs, Align Rhs) { return Lhs && *Lhs == Rhs; }
296 inline bool operator!=(MaybeAlign Lhs, Align Rhs) { return !(Lhs == Rhs); }
297 inline bool operator==(Align Lhs, MaybeAlign Rhs) { return Rhs == Lhs; }
298 inline bool operator!=(Align Lhs, MaybeAlign Rhs) { return !(Rhs == Lhs); }
299 // Allow equality comparisons with MaybeAlign.
300 inline bool operator==(MaybeAlign Lhs, MaybeAlign Rhs) {
301   return (Lhs && Rhs && (*Lhs == *Rhs)) || (!Lhs && !Rhs);
302 }
303 inline bool operator!=(MaybeAlign Lhs, MaybeAlign Rhs) { return !(Lhs == Rhs); }
304 // Allow equality comparisons with std::nullopt.
305 inline bool operator==(MaybeAlign Lhs, std::nullopt_t) { return !bool(Lhs); }
306 inline bool operator!=(MaybeAlign Lhs, std::nullopt_t) { return bool(Lhs); }
307 inline bool operator==(std::nullopt_t, MaybeAlign Rhs) { return !bool(Rhs); }
308 inline bool operator!=(std::nullopt_t, MaybeAlign Rhs) { return bool(Rhs); }
309 
310 #ifndef NDEBUG
311 // For usage in LLVM_DEBUG macros.
312 inline std::string DebugStr(const Align &A) {
313   return std::to_string(A.value());
314 }
315 // For usage in LLVM_DEBUG macros.
316 inline std::string DebugStr(const MaybeAlign &MA) {
317   if (MA)
318     return std::to_string(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