LLVM  10.0.0svn
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"
25 #include "llvm/Support/Compiler.h"
27 #include <cassert>
28 #include <limits>
29 
30 namespace llvm {
31 
32 #define ALIGN_CHECK_ISPOSITIVE(decl) \
33  assert(decl > 0 && (#decl " should be defined"))
34 #define ALIGN_CHECK_ISSET(decl) \
35  assert(decl.hasValue() && (#decl " should be defined"))
36 
37 /// This struct is a compact representation of a valid (non-zero power of two)
38 /// alignment.
39 /// It is suitable for use as static global constants.
40 struct Align {
41 private:
42  uint8_t ShiftValue = 0; /// The log2 of the required alignment.
43  /// ShiftValue is less than 64 by construction.
44 
45  friend struct MaybeAlign;
46  friend unsigned Log2(Align);
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 bool operator>(Align Lhs, Align Rhs);
53  friend unsigned encode(struct MaybeAlign A);
55 
56  /// A trivial type to allow construction of constexpr Align.
57  /// This is currently needed to workaround a bug in GCC 5.3 which prevents
58  /// definition of constexpr assign operators.
59  /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
60  /// FIXME: Remove this, make all assign operators constexpr and introduce user
61  /// defined literals when we don't have to support GCC 5.3 anymore.
62  /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
63  struct LogValue {
64  uint8_t Log;
65  };
66 
67 public:
68  /// Default is byte-aligned.
69  constexpr Align() = default;
70  /// Do not perform checks in case of copy/move construct/assign, because the
71  /// checks have been performed when building `Other`.
72  constexpr Align(const Align &Other) = default;
73  constexpr Align(Align &&Other) = default;
74  Align &operator=(const Align &Other) = default;
75  Align &operator=(Align &&Other) = default;
76 
77  explicit Align(uint64_t Value) {
78  assert(Value > 0 && "Value must not be 0");
79  assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2");
80  ShiftValue = Log2_64(Value);
81  assert(ShiftValue < 64 && "Broken invariant");
82  }
83 
84  /// This is a hole in the type system and should not be abused.
85  /// Needed to interact with C for instance.
86  uint64_t value() const { return uint64_t(1) << ShiftValue; }
87 
88  /// Returns a default constructed Align which corresponds to no alignment.
89  /// This is useful to test for unalignment as it conveys clear semantic.
90  /// `if (A != Align::None())`
91  /// would be better than
92  /// `if (A > Align(1))`
93  constexpr static const Align None() { return Align(); }
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.
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 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 
134  explicit MaybeAlign(uint64_t Value) {
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 hasValue() ? getValue() : 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 SizeInBytes is a multiple of the alignment.
151 /// Returns false if the alignment is undefined.
152 inline bool isAligned(MaybeAlign Lhs, uint64_t SizeInBytes) {
153  ALIGN_CHECK_ISSET(Lhs);
154  return SizeInBytes % (*Lhs).value() == 0;
155 }
156 
157 /// Checks that Addr is a multiple of the alignment.
158 inline bool isAddrAligned(Align Lhs, const void *Addr) {
159  return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
160 }
161 
162 /// Returns a multiple of A needed to store `Size` bytes.
163 inline uint64_t alignTo(uint64_t Size, Align A) {
164  const uint64_t value = A.value();
165  // The following line is equivalent to `(Size + value - 1) / value * value`.
166 
167  // The division followed by a multiplication can be thought of as a right
168  // shift followed by a left shift which zeros out the extra bits produced in
169  // the bump; `~(value - 1)` is a mask where all those bits being zeroed out
170  // are just zero.
171 
172  // Most compilers can generate this code but the pattern may be missed when
173  // multiple functions gets inlined.
174  return (Size + value - 1) & ~(value - 1);
175 }
176 
177 /// Returns a multiple of A needed to store `Size` bytes.
178 /// Returns `Size` if current alignment is undefined.
179 inline uint64_t alignTo(uint64_t Size, MaybeAlign A) {
180  return A ? alignTo(Size, A.getValue()) : Size;
181 }
182 
183 /// Aligns `Addr` to `Alignment` bytes, rounding up.
184 inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
185  uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
186  assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
187  ArithAddr && "Overflow");
188  return alignTo(ArithAddr, Alignment);
189 }
190 
191 /// Returns the offset to the next integer (mod 2**64) that is greater than
192 /// or equal to \p Value and is a multiple of \p Align.
193 inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
194  return alignTo(Value, Alignment) - Value;
195 }
196 
197 /// Returns the necessary adjustment for aligning `Addr` to `Alignment`
198 /// bytes, rounding up.
199 inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
200  return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
201 }
202 
203 /// Returns the log2 of the alignment.
204 inline unsigned Log2(Align A) { return A.ShiftValue; }
205 
206 /// Returns the log2 of the alignment.
207 /// \pre A must be defined.
208 inline unsigned Log2(MaybeAlign A) {
210  return Log2(A.getValue());
211 }
212 
213 /// Returns the alignment that satisfies both alignments.
214 /// Same semantic as MinAlign.
215 inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }
216 
217 /// Returns the alignment that satisfies both alignments.
218 /// Same semantic as MinAlign.
219 inline Align commonAlignment(Align A, uint64_t Offset) {
220  return Align(MinAlign(A.value(), Offset));
221 }
222 
223 /// Returns the alignment that satisfies both alignments.
224 /// Same semantic as MinAlign.
226  return A && B ? commonAlignment(*A, *B) : A ? A : B;
227 }
228 
229 /// Returns the alignment that satisfies both alignments.
230 /// Same semantic as MinAlign.
232  return MaybeAlign(MinAlign((*A).value(), Offset));
233 }
234 
235 /// Returns a representation of the alignment that encodes undefined as 0.
236 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
237 
238 /// Dual operation of the encode function above.
240  if (Value == 0)
241  return MaybeAlign();
242  Align Out;
243  Out.ShiftValue = Value - 1;
244  return Out;
245 }
246 
247 /// Returns a representation of the alignment, the encoded value is positive by
248 /// definition.
249 inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
250 
251 /// Comparisons between Align and scalars. Rhs must be positive.
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 inline bool operator>(Align Lhs, uint64_t Rhs) {
274  return Lhs.value() > Rhs;
275 }
276 
277 /// Comparisons between MaybeAlign and scalars.
278 inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
279  return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
280 }
281 inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
282  return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
283 }
284 inline bool operator<=(MaybeAlign Lhs, uint64_t Rhs) {
285  ALIGN_CHECK_ISSET(Lhs);
287  return (*Lhs).value() <= Rhs;
288 }
289 inline bool operator>=(MaybeAlign Lhs, uint64_t Rhs) {
290  ALIGN_CHECK_ISSET(Lhs);
292  return (*Lhs).value() >= Rhs;
293 }
294 inline bool operator<(MaybeAlign Lhs, uint64_t Rhs) {
295  ALIGN_CHECK_ISSET(Lhs);
297  return (*Lhs).value() < Rhs;
298 }
299 inline bool operator>(MaybeAlign Lhs, uint64_t Rhs) {
300  ALIGN_CHECK_ISSET(Lhs);
302  return (*Lhs).value() > Rhs;
303 }
304 
305 /// Comparisons operators between Align.
306 inline bool operator==(Align Lhs, Align Rhs) {
307  return Lhs.ShiftValue == Rhs.ShiftValue;
308 }
309 inline bool operator!=(Align Lhs, Align Rhs) {
310  return Lhs.ShiftValue != Rhs.ShiftValue;
311 }
312 inline bool operator<=(Align Lhs, Align Rhs) {
313  return Lhs.ShiftValue <= Rhs.ShiftValue;
314 }
315 inline bool operator>=(Align Lhs, Align Rhs) {
316  return Lhs.ShiftValue >= Rhs.ShiftValue;
317 }
318 inline bool operator<(Align Lhs, Align Rhs) {
319  return Lhs.ShiftValue < Rhs.ShiftValue;
320 }
321 inline bool operator>(Align Lhs, Align Rhs) {
322  return Lhs.ShiftValue > Rhs.ShiftValue;
323 }
324 
325 /// Comparisons operators between Align and MaybeAlign.
326 inline bool operator==(Align Lhs, MaybeAlign Rhs) {
327  ALIGN_CHECK_ISSET(Rhs);
328  return Lhs.value() == (*Rhs).value();
329 }
330 inline bool operator!=(Align Lhs, MaybeAlign Rhs) {
331  ALIGN_CHECK_ISSET(Rhs);
332  return Lhs.value() != (*Rhs).value();
333 }
334 inline bool operator<=(Align Lhs, MaybeAlign Rhs) {
335  ALIGN_CHECK_ISSET(Rhs);
336  return Lhs.value() <= (*Rhs).value();
337 }
338 inline bool operator>=(Align Lhs, MaybeAlign Rhs) {
339  ALIGN_CHECK_ISSET(Rhs);
340  return Lhs.value() >= (*Rhs).value();
341 }
342 inline bool operator<(Align Lhs, MaybeAlign Rhs) {
343  ALIGN_CHECK_ISSET(Rhs);
344  return Lhs.value() < (*Rhs).value();
345 }
346 inline bool operator>(Align Lhs, MaybeAlign Rhs) {
347  ALIGN_CHECK_ISSET(Rhs);
348  return Lhs.value() > (*Rhs).value();
349 }
350 
351 /// Comparisons operators between MaybeAlign and Align.
352 inline bool operator==(MaybeAlign Lhs, Align Rhs) {
353  ALIGN_CHECK_ISSET(Lhs);
354  return Lhs && (*Lhs).value() == Rhs.value();
355 }
356 inline bool operator!=(MaybeAlign Lhs, Align Rhs) {
357  ALIGN_CHECK_ISSET(Lhs);
358  return Lhs && (*Lhs).value() != Rhs.value();
359 }
360 inline bool operator<=(MaybeAlign Lhs, Align Rhs) {
361  ALIGN_CHECK_ISSET(Lhs);
362  return Lhs && (*Lhs).value() <= Rhs.value();
363 }
364 inline bool operator>=(MaybeAlign Lhs, Align Rhs) {
365  ALIGN_CHECK_ISSET(Lhs);
366  return Lhs && (*Lhs).value() >= Rhs.value();
367 }
368 inline bool operator<(MaybeAlign Lhs, Align Rhs) {
369  ALIGN_CHECK_ISSET(Lhs);
370  return Lhs && (*Lhs).value() < Rhs.value();
371 }
372 inline bool operator>(MaybeAlign Lhs, Align Rhs) {
373  ALIGN_CHECK_ISSET(Lhs);
374  return Lhs && (*Lhs).value() > Rhs.value();
375 }
376 
377 inline Align operator/(Align Lhs, uint64_t Divisor) {
378  assert(llvm::isPowerOf2_64(Divisor) &&
379  "Divisor must be positive and a power of 2");
380  assert(Lhs != 1 && "Can't halve byte alignment");
381  return Align(Lhs.value() / Divisor);
382 }
383 
384 inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) {
385  assert(llvm::isPowerOf2_64(Divisor) &&
386  "Divisor must be positive and a power of 2");
387  return Lhs ? Lhs.getValue() / Divisor : MaybeAlign();
388 }
389 
390 inline Align max(MaybeAlign Lhs, Align Rhs) {
391  return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
392 }
393 
394 inline Align max(Align Lhs, MaybeAlign Rhs) {
395  return Rhs && *Rhs > Lhs ? *Rhs : Lhs;
396 }
397 
398 #undef ALIGN_CHECK_ISPOSITIVE
399 #undef ALIGN_CHECK_ISSET
400 
401 } // namespace llvm
402 
403 #endif // LLVM_SUPPORT_ALIGNMENT_H_
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
Definition: Alignment.h:142
This class represents lattice values for constants.
Definition: AllocatorList.h:23
uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment)
Returns the necessary adjustment for aligning Addr to Alignment bytes, rounding up.
Definition: Alignment.h:199
friend bool operator==(Align Lhs, Align Rhs)
Comparisons operators between Align.
Definition: Alignment.h:306
Align operator/(Align Lhs, uint64_t Divisor)
Definition: Alignment.h:377
static constexpr LogValue Of()
Allow constructions of constexpr Align from types.
Definition: Alignment.h:102
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
friend bool operator<=(Align Lhs, Align Rhs)
Definition: Alignment.h:312
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:193
friend struct MaybeAlign decodeMaybeAlign(unsigned Value)
Dual operation of the encode function above.
Definition: Alignment.h:239
uintptr_t alignAddr(const void *Addr, Align Alignment)
Aligns Addr to Alignment bytes, rounding up.
Definition: Alignment.h:184
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:215
constexpr Align()=default
Default is byte-aligned.
const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:255
friend bool operator>(Align Lhs, Align Rhs)
Definition: Alignment.h:321
friend struct MaybeAlign
The log2 of the required alignment.
Definition: Alignment.h:45
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:86
#define ALIGN_CHECK_ISSET(decl)
Definition: Alignment.h:34
Align(uint64_t Value)
Definition: Alignment.h:77
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:661
friend unsigned encode(struct MaybeAlign A)
Returns a representation of the alignment that encodes undefined as 0.
Definition: Alignment.h:236
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:470
bool isAddrAligned(Align Lhs, const void *Addr)
Checks that Addr is a multiple of the alignment.
Definition: Alignment.h:158
friend bool operator>=(Align Lhs, Align Rhs)
Definition: Alignment.h:315
friend bool operator<(Align Lhs, Align Rhs)
Definition: Alignment.h:318
static constexpr const Align None()
Returns a default constructed Align which corresponds to no alignment.
Definition: Alignment.h:93
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:117
Align & operator=(const Align &Other)=default
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
Definition: Alignment.h:146
static constexpr LogValue Constant()
Allow constructions of constexpr Align.
Definition: Alignment.h:96
constexpr Align(LogValue CA)
Constexpr constructor from LogValue type.
Definition: Alignment.h:107
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:163
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
uint32_t Size
Definition: Profile.cpp:46
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
friend unsigned Log2(Align)
Returns the log2 of the alignment.
Definition: Alignment.h:204
friend bool operator!=(Align Lhs, Align Rhs)
Definition: Alignment.h:309
#define ALIGN_CHECK_ISPOSITIVE(decl)
Definition: Alignment.h:32
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:591
MaybeAlign(uint64_t Value)
Definition: Alignment.h:134
Align assumeAligned(uint64_t Value)
Treats the value 0 as a 1, so Align is always at least 1.
Definition: Alignment.h:111