LLVM  17.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 
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() {
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.
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) {}
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.
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.
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.
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) {
235  return Lhs.value() == Rhs;
236 }
237 inline bool operator!=(Align Lhs, uint64_t Rhs) {
239  return Lhs.value() != Rhs;
240 }
241 inline bool operator<=(Align Lhs, uint64_t Rhs) {
243  return Lhs.value() <= Rhs;
244 }
245 inline bool operator>=(Align Lhs, uint64_t Rhs) {
247  return Lhs.value() >= Rhs;
248 }
249 inline bool operator<(Align Lhs, uint64_t Rhs) {
251  return Lhs.value() < Rhs;
252 }
253 inline bool operator>(Align Lhs, uint64_t 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_
llvm::Align::operator<=
friend bool operator<=(Align Lhs, Align Rhs)
Definition: Alignment.h:265
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:145
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Align::previous
Align previous() const
Definition: Alignment.h:88
llvm::operator<=
bool operator<=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:359
llvm::DebugStr
std::string DebugStr(const Align &A)
Definition: Alignment.h:312
llvm::alignAddr
uintptr_t alignAddr(const void *Addr, Align Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: Alignment.h:187
llvm::Align::operator<
friend bool operator<(Align Lhs, Align Rhs)
Definition: Alignment.h:271
llvm::Align::operator>=
friend bool operator>=(Align Lhs, Align Rhs)
Definition: Alignment.h:268
llvm::MaybeAlign::valueOrOne
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:141
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2040
llvm::commonAlignment
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:212
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:426
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:379
llvm::Align::Align
constexpr Align(LogValue CA)
Constexpr constructor from LogValue type.
Definition: Alignment.h:107
llvm::Log2
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:208
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
llvm::Align::operator==
friend bool operator==(Align Lhs, Align Rhs)
Comparisons operators between Align.
Definition: Alignment.h:259
llvm::encode
unsigned encode(MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:217
llvm::MaybeAlign::MaybeAlign
constexpr MaybeAlign(std::nullopt_t None)
Definition: Alignment.h:131
llvm::MaybeAlign::MaybeAlign
MaybeAlign()=default
Default is undefined.
Align
uint64_t Align
Definition: ELFObjHandler.cpp:82
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:262
llvm::operator>=
bool operator>=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:360
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Align::Of
constexpr static Align Of()
Allow constructions of constexpr Align from types.
Definition: Alignment.h:102
uint64_t
llvm::Align::Align
constexpr Align()=default
Default is byte-aligned.
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::assumeAligned
Align assumeAligned(uint64_t Value)
Treats the value 0 as a 1, so Align is always at least 1.
Definition: Alignment.h:111
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:361
llvm::Align::Log2
friend unsigned Log2(Align)
Returns the log2 of the alignment.
Definition: Alignment.h:208
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:2038
llvm::Align::operator=
Align & operator=(const Align &Other)=default
llvm::MaybeAlign::MaybeAlign
constexpr MaybeAlign(Align Value)
Definition: Alignment.h:132
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:203
llvm::Align::operator>
friend bool operator>(Align Lhs, Align Rhs)
Definition: Alignment.h:274
llvm::Offset
@ Offset
Definition: DWP.cpp:406
llvm::Align::encode
friend unsigned encode(struct MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:217
A
* A
Definition: README_ALTIVEC.txt:89
llvm::MaybeAlign::operator=
MaybeAlign & operator=(const MaybeAlign &Other)=default
llvm::None
constexpr std::nullopt_t None
Definition: None.h:28
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:150
llvm::Align::Constant
constexpr static Align Constant()
Allow constructions of constexpr Align.
Definition: Alignment.h:96
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::decodeMaybeAlign
MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:220
Other
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
llvm::Align::decodeMaybeAlign
friend struct MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:220
llvm::to_string
std::string to_string(const T &Value)
Definition: ScopedPrinter.h:85
llvm::operator>
bool operator>(int64_t V1, const APSInt &V2)
Definition: APSInt.h:362
llvm::Align::Align
Align(uint64_t Value)
Definition: Alignment.h:76
llvm::MaybeAlign::MaybeAlign
MaybeAlign(uint64_t Value)
Definition: Alignment.h:133
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:293
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:197
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
ALIGN_CHECK_ISPOSITIVE
#define ALIGN_CHECK_ISPOSITIVE(decl)
Definition: Alignment.h:33