LLVM  15.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  // 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 LogValue 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 LogValue 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 llvm::Optional<Align> {
118 private:
119  using UP = llvm::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  /// Use llvm::Optional<Align> constructor.
132  using UP::UP;
133 
135  assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&
136  "Alignment is neither 0 nor a power of 2");
137  if (Value)
138  emplace(Value);
139  }
140 
141  /// For convenience, returns a valid alignment or 1 if undefined.
142  Align valueOrOne() const { return value_or(Align()); }
143 };
144 
145 /// Checks that SizeInBytes is a multiple of the alignment.
146 inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
147  return SizeInBytes % Lhs.value() == 0;
148 }
149 
150 /// Checks that Addr is a multiple of the alignment.
151 inline bool isAddrAligned(Align Lhs, const void *Addr) {
152  return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
153 }
154 
155 /// Returns a multiple of A needed to store `Size` bytes.
156 inline uint64_t alignTo(uint64_t Size, Align A) {
157  const uint64_t Value = A.value();
158  // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
159 
160  // The division followed by a multiplication can be thought of as a right
161  // shift followed by a left shift which zeros out the extra bits produced in
162  // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
163  // are just zero.
164 
165  // Most compilers can generate this code but the pattern may be missed when
166  // multiple functions gets inlined.
167  return (Size + Value - 1) & ~(Value - 1U);
168 }
169 
170 /// If non-zero \p Skew is specified, the return value will be a minimal integer
171 /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
172 /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
173 /// Skew mod \p A'.
174 ///
175 /// Examples:
176 /// \code
177 /// alignTo(5, Align(8), 7) = 7
178 /// alignTo(17, Align(8), 1) = 17
179 /// alignTo(~0LL, Align(8), 3) = 3
180 /// \endcode
181 inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) {
182  const uint64_t Value = A.value();
183  Skew %= Value;
184  return alignTo(Size - Skew, A) + Skew;
185 }
186 
187 /// Aligns `Addr` to `Alignment` bytes, rounding up.
188 inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
189  uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
190  assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
191  ArithAddr &&
192  "Overflow");
193  return alignTo(ArithAddr, Alignment);
194 }
195 
196 /// Returns the offset to the next integer (mod 2**64) that is greater than
197 /// or equal to \p Value and is a multiple of \p Align.
199  return alignTo(Value, Alignment) - Value;
200 }
201 
202 /// Returns the necessary adjustment for aligning `Addr` to `Alignment`
203 /// bytes, rounding up.
204 inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
205  return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
206 }
207 
208 /// Returns the log2 of the alignment.
209 inline unsigned Log2(Align A) { return A.ShiftValue; }
210 
211 /// Returns the alignment that satisfies both alignments.
212 /// Same semantic as MinAlign.
213 inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }
214 
215 /// Returns the alignment that satisfies both alignments.
216 /// Same semantic as MinAlign.
217 inline Align commonAlignment(Align A, uint64_t Offset) {
218  return Align(MinAlign(A.value(), Offset));
219 }
220 
221 /// Returns a representation of the alignment that encodes undefined as 0.
222 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
223 
224 /// Dual operation of the encode function above.
226  if (Value == 0)
227  return MaybeAlign();
228  Align Out;
229  Out.ShiftValue = Value - 1;
230  return Out;
231 }
232 
233 /// Returns a representation of the alignment, the encoded value is positive by
234 /// definition.
235 inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
236 
237 /// Comparisons between Align and scalars. Rhs must be positive.
238 inline bool operator==(Align Lhs, uint64_t Rhs) {
240  return Lhs.value() == Rhs;
241 }
242 inline bool operator!=(Align Lhs, uint64_t Rhs) {
244  return Lhs.value() != Rhs;
245 }
246 inline bool operator<=(Align Lhs, uint64_t Rhs) {
248  return Lhs.value() <= Rhs;
249 }
250 inline bool operator>=(Align Lhs, uint64_t Rhs) {
252  return Lhs.value() >= Rhs;
253 }
254 inline bool operator<(Align Lhs, uint64_t Rhs) {
256  return Lhs.value() < Rhs;
257 }
258 inline bool operator>(Align Lhs, uint64_t Rhs) {
260  return Lhs.value() > Rhs;
261 }
262 
263 /// Comparisons between MaybeAlign and scalars.
264 inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
265  return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
266 }
267 inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
268  return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
269 }
270 
271 /// Comparisons operators between Align.
272 inline bool operator==(Align Lhs, Align Rhs) {
273  return Lhs.ShiftValue == Rhs.ShiftValue;
274 }
275 inline bool operator!=(Align Lhs, Align Rhs) {
276  return Lhs.ShiftValue != Rhs.ShiftValue;
277 }
278 inline bool operator<=(Align Lhs, Align Rhs) {
279  return Lhs.ShiftValue <= Rhs.ShiftValue;
280 }
281 inline bool operator>=(Align Lhs, Align Rhs) {
282  return Lhs.ShiftValue >= Rhs.ShiftValue;
283 }
284 inline bool operator<(Align Lhs, Align Rhs) {
285  return Lhs.ShiftValue < Rhs.ShiftValue;
286 }
287 inline bool operator>(Align Lhs, Align Rhs) {
288  return Lhs.ShiftValue > Rhs.ShiftValue;
289 }
290 
291 // Don't allow relational comparisons with MaybeAlign.
292 bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
293 bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
294 bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
295 bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
296 
297 bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
298 bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
299 bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
300 bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
301 
302 bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
303 bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
304 bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
305 bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
306 
307 #ifndef NDEBUG
308 // For usage in LLVM_DEBUG macros.
309 inline std::string DebugStr(const Align &A) {
310  return std::to_string(A.value());
311 }
312 // For usage in LLVM_DEBUG macros.
313 inline std::string DebugStr(const MaybeAlign &MA) {
314  if (MA)
315  return std::to_string(MA->value());
316  return "None";
317 }
318 #endif // NDEBUG
319 
320 #undef ALIGN_CHECK_ISPOSITIVE
321 
322 } // namespace llvm
323 
324 #endif // LLVM_SUPPORT_ALIGNMENT_H_
llvm::Align::operator<=
friend bool operator<=(Align Lhs, Align Rhs)
Definition: Alignment.h:278
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:156
llvm::isAligned
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:146
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
Optional.h
llvm::Align::previous
Align previous() const
Definition: Alignment.h:88
llvm::operator<=
bool operator<=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:337
llvm::DebugStr
std::string DebugStr(const Align &A)
Definition: Alignment.h:309
llvm::alignAddr
uintptr_t alignAddr(const void *Addr, Align Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: Alignment.h:188
llvm::Align::operator<
friend bool operator<(Align Lhs, Align Rhs)
Definition: Alignment.h:284
llvm::Align::operator>=
friend bool operator>=(Align Lhs, Align Rhs)
Definition: Alignment.h:281
llvm::MaybeAlign::valueOrOne
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:142
llvm::operator!=
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1992
llvm::Optional
Definition: APInt.h:33
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:699
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:629
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:209
llvm::MaybeAlign
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Definition: Alignment.h:117
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:272
llvm::encode
unsigned encode(MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:222
llvm::MaybeAlign::MaybeAlign
MaybeAlign()=default
Default is undefined.
Align
uint64_t Align
Definition: ELFObjHandler.cpp:81
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:275
llvm::operator>=
bool operator>=(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
llvm::Align::Constant
constexpr static LogValue Constant()
Allow constructions of constexpr Align.
Definition: Alignment.h:96
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
uint64_t
llvm::Align::Align
constexpr Align()=default
Default is byte-aligned.
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
llvm::Optional< Align >::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:287
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:339
llvm::Align::Log2
friend unsigned Log2(Align)
Returns the log2 of the alignment.
Definition: Alignment.h:209
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::operator==
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1990
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:204
llvm::Align::operator>
friend bool operator>(Align Lhs, Align Rhs)
Definition: Alignment.h:287
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:222
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:102
llvm::commonAlignment
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:213
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:151
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::decodeMaybeAlign
MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:225
llvm::Align::decodeMaybeAlign
friend struct MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:225
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:340
llvm::Optional::value
constexpr const T & value() const &
Definition: Optional.h:305
llvm::Align::Align
Align(uint64_t Value)
Definition: Alignment.h:76
llvm::MaybeAlign::MaybeAlign
MaybeAlign(uint64_t Value)
Definition: Alignment.h:134
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::Optional< Align >::value_or
constexpr Align value_or(U &&alt) const &
Definition: Optional.h:318
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:198
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236
ALIGN_CHECK_ISPOSITIVE
#define ALIGN_CHECK_ISPOSITIVE(decl)
Definition: Alignment.h:33