LLVM  14.0.0git
Alignment.h
Go to the documentation of this file.
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"
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 
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  /// Allow constructions of constexpr Align.
88  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)).
94  template <typename T> constexpr static LogValue Of() {
96  }
97 
98  /// Constexpr constructor from LogValue type.
99  constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
100 };
101 
102 /// Treats the value 0 as a 1, so Align is always at least 1.
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 
126  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.
134  Align valueOrOne() const { return hasValue() ? getValue() : Align(); }
135 };
136 
137 /// Checks that SizeInBytes is a multiple of the alignment.
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.
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.
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
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.
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.
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.
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.
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.
207 inline unsigned Log2(Align A) { return A.ShiftValue; }
208 
209 /// Returns the alignment that satisfies both alignments.
210 /// Same semantic as MinAlign.
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.
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.
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.
228  return MaybeAlign(MinAlign((*A).value(), Offset));
229 }
230 
231 /// Returns a representation of the alignment that encodes undefined as 0.
232 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
233 
234 /// Dual operation of the encode function above.
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.
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) {
250  return Lhs.value() == Rhs;
251 }
252 inline bool operator!=(Align Lhs, uint64_t Rhs) {
254  return Lhs.value() != Rhs;
255 }
256 inline bool operator<=(Align Lhs, uint64_t Rhs) {
258  return Lhs.value() <= Rhs;
259 }
260 inline bool operator>=(Align Lhs, uint64_t Rhs) {
262  return Lhs.value() >= Rhs;
263 }
264 inline bool operator<(Align Lhs, uint64_t Rhs) {
266  return Lhs.value() < Rhs;
267 }
268 inline bool operator>(Align Lhs, uint64_t 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 
340 inline Align max(MaybeAlign Lhs, Align Rhs) {
341  return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
342 }
343 
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.
350 inline std::string DebugStr(const Align &A) {
351  return std::to_string(A.value());
352 }
353 // For usage in LLVM_DEBUG macros.
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_
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm::Align::operator<=
friend bool operator<=(Align Lhs, Align Rhs)
Definition: Alignment.h:288
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:148
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:138
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Optional.h
llvm::operator<=
bool operator<=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:336
llvm::DebugStr
std::string DebugStr(const Align &A)
Definition: Alignment.h:350
llvm::alignAddr
uintptr_t alignAddr(const void *Addr, Align Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: Alignment.h:186
llvm::Align::operator<
friend bool operator<(Align Lhs, Align Rhs)
Definition: Alignment.h:294
llvm::Align::operator>=
friend bool operator>=(Align Lhs, Align Rhs)
Definition: Alignment.h:291
llvm::MaybeAlign::valueOrOne
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:134
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2032
llvm::Optional
Definition: APInt.h:33
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::operator/
Align operator/(Align Lhs, uint64_t Divisor)
Definition: Alignment.h:327
llvm::Optional< Align >::hasValue
constexpr bool hasValue() const
Definition: Optional.h:288
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:672
llvm::Log2_64
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:602
llvm::Align::Align
constexpr Align(LogValue CA)
Constexpr constructor from LogValue type.
Definition: Alignment.h:99
llvm::Log2
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:207
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:109
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Align::operator==
friend bool operator==(Align Lhs, Align Rhs)
Comparisons operators between Align.
Definition: Alignment.h:282
llvm::encode
unsigned encode(MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:232
llvm::MaybeAlign::MaybeAlign
MaybeAlign()=default
Default is undefined.
Align
uint64_t Align
Definition: ELFObjHandler.cpp:83
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::Align::operator!=
friend bool operator!=(Align Lhs, Align Rhs)
Definition: Alignment.h:285
llvm::operator>=
bool operator>=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:337
llvm::Align::Constant
constexpr static LogValue Constant()
Allow constructions of constexpr Align.
Definition: Alignment.h:88
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Align::Align
constexpr Align()=default
Default is byte-aligned.
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::Optional< Align >::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:264
llvm::assumeAligned
Align assumeAligned(uint64_t Value)
Treats the value 0 as a 1, so Align is always at least 1.
Definition: Alignment.h:103
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
llvm::Align::Log2
friend unsigned Log2(Align)
Returns the log2 of the alignment.
Definition: Alignment.h:207
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2030
llvm::Align::operator=
Align & operator=(const Align &Other)=default
llvm::offsetToAlignedAddr
uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment)
Returns the necessary adjustment for aligning Addr to Alignment bytes, rounding up.
Definition: Alignment.h:202
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2154
llvm::Align::operator>
friend bool operator>(Align Lhs, Align Rhs)
Definition: Alignment.h:297
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::Align::encode
friend unsigned encode(struct MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:232
A
* A
Definition: README_ALTIVEC.txt:89
llvm::MaybeAlign::operator=
MaybeAlign & operator=(const MaybeAlign &Other)=default
llvm::Align::Of
constexpr static LogValue Of()
Allow constructions of constexpr Align from types.
Definition: Alignment.h:94
llvm::commonAlignment
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:211
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::isAddrAligned
bool isAddrAligned(Align Lhs, const void *Addr)
Checks that Addr is a multiple of the alignment.
Definition: Alignment.h:143
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::decodeMaybeAlign
MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:235
llvm::Align::decodeMaybeAlign
friend struct MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:235
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:63
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::operator>
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:339
llvm::Align::Align
Align(uint64_t Value)
Definition: Alignment.h:76
llvm::MaybeAlign::MaybeAlign
MaybeAlign(uint64_t Value)
Definition: Alignment.h:126
llvm::isPowerOf2_64
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:496
llvm::offsetToAlignment
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
Definition: Alignment.h:196
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Optional< Align >::getValue
constexpr const Align & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1172
ALIGN_CHECK_ISPOSITIVE
#define ALIGN_CHECK_ISPOSITIVE(decl)
Definition: Alignment.h:33