llvm.org GIT mirror llvm / master include / llvm / Support / Alignment.h
master

Tree @master (Download .tar.gz)

Alignment.h @masterraw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
//===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains types to represent alignments.
// They are instrumented to guarantee some invariants are preserved and prevent
// invalid manipulations.
//
// - Align represents an alignment in bytes, it is always set and always a valid
// power of two, its minimum value is 1 which means no alignment requirements.
//
// - MaybeAlign is an optional type, it may be undefined or set. When it's set
// you can get the underlying Align type by using the getValue() method.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_SUPPORT_ALIGNMENT_H_
#define LLVM_SUPPORT_ALIGNMENT_H_

#include "llvm/ADT/Optional.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
#include <cassert>
#include <limits>

namespace llvm {

#define ALIGN_CHECK_ISPOSITIVE(decl)                                           \
  assert(decl > 0 && (#decl " should be defined"))
#define ALIGN_CHECK_ISSET(decl)                                                \
  assert(decl.hasValue() && (#decl " should be defined"))

/// This struct is a compact representation of a valid (non-zero power of two)
/// alignment.
/// It is suitable for use as static global constants.
struct Align {
private:
  uint8_t ShiftValue = 0; /// The log2 of the required alignment.
                          /// ShiftValue is less than 64 by construction.

  friend struct MaybeAlign;
  friend unsigned Log2(Align);
  friend bool operator==(Align Lhs, Align Rhs);
  friend bool operator!=(Align Lhs, Align Rhs);
  friend bool operator<=(Align Lhs, Align Rhs);
  friend bool operator>=(Align Lhs, Align Rhs);
  friend bool operator<(Align Lhs, Align Rhs);
  friend bool operator>(Align Lhs, Align Rhs);
  friend unsigned encode(struct MaybeAlign A);
  friend struct MaybeAlign decodeMaybeAlign(unsigned Value);

  /// A trivial type to allow construction of constexpr Align.
  /// This is currently needed to workaround a bug in GCC 5.3 which prevents
  /// definition of constexpr assign operators.
  /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
  /// FIXME: Remove this, make all assign operators constexpr and introduce user
  /// defined literals when we don't have to support GCC 5.3 anymore.
  /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
  struct LogValue {
    uint8_t Log;
  };

public:
  /// Default is byte-aligned.
  constexpr Align() = default;
  /// Do not perform checks in case of copy/move construct/assign, because the
  /// checks have been performed when building `Other`.
  constexpr Align(const Align &Other) = default;
  constexpr Align(Align &&Other) = default;
  Align &operator=(const Align &Other) = default;
  Align &operator=(Align &&Other) = default;

  explicit Align(uint64_t Value) {
    assert(Value > 0 && "Value must not be 0");
    assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2");
    ShiftValue = Log2_64(Value);
    assert(ShiftValue < 64 && "Broken invariant");
  }

  /// This is a hole in the type system and should not be abused.
  /// Needed to interact with C for instance.
  uint64_t value() const { return uint64_t(1) << ShiftValue; }

  /// Returns a default constructed Align which corresponds to no alignment.
  /// This is useful to test for unalignment as it conveys clear semantic.
  /// `if (A != Align::None())`
  /// would be better than
  /// `if (A > Align(1))`
  constexpr static const Align None() { return Align(); }

  /// Allow constructions of constexpr Align.
  template <size_t kValue> constexpr static LogValue Constant() {
    return LogValue{static_cast<uint8_t>(CTLog2<kValue>())};
  }

  /// Allow constructions of constexpr Align from types.
  /// Compile time equivalent to Align(alignof(T)).
  template <typename T> constexpr static LogValue Of() {
    return Constant<std::alignment_of<T>::value>();
  }

  /// Constexpr constructor from LogValue type.
  constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
};

/// Treats the value 0 as a 1, so Align is always at least 1.
inline Align assumeAligned(uint64_t Value) {
  return Value ? Align(Value) : Align();
}

/// This struct is a compact representation of a valid (power of two) or
/// undefined (0) alignment.
struct MaybeAlign : public llvm::Optional<Align> {
private:
  using UP = llvm::Optional<Align>;

public:
  /// Default is undefined.
  MaybeAlign() = default;
  /// Do not perform checks in case of copy/move construct/assign, because the
  /// checks have been performed when building `Other`.
  MaybeAlign(const MaybeAlign &Other) = default;
  MaybeAlign &operator=(const MaybeAlign &Other) = default;
  MaybeAlign(MaybeAlign &&Other) = default;
  MaybeAlign &operator=(MaybeAlign &&Other) = default;

  /// Use llvm::Optional<Align> constructor.
  using UP::UP;

  explicit MaybeAlign(uint64_t Value) {
    assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&
           "Alignment is neither 0 nor a power of 2");
    if (Value)
      emplace(Value);
  }

  /// For convenience, returns a valid alignment or 1 if undefined.
  Align valueOrOne() const { return hasValue() ? getValue() : Align(); }
};

/// Checks that SizeInBytes is a multiple of the alignment.
inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
  return SizeInBytes % Lhs.value() == 0;
}

/// Checks that SizeInBytes is a multiple of the alignment.
/// Returns false if the alignment is undefined.
inline bool isAligned(MaybeAlign Lhs, uint64_t SizeInBytes) {
  ALIGN_CHECK_ISSET(Lhs);
  return SizeInBytes % (*Lhs).value() == 0;
}

/// Checks that Addr is a multiple of the alignment.
inline bool isAddrAligned(Align Lhs, const void *Addr) {
  return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
}

/// Returns a multiple of A needed to store `Size` bytes.
inline uint64_t alignTo(uint64_t Size, Align A) {
  const uint64_t value = A.value();
  // The following line is equivalent to `(Size + value - 1) / value * value`.

  // The division followed by a multiplication can be thought of as a right
  // shift followed by a left shift which zeros out the extra bits produced in
  // the bump; `~(value - 1)` is a mask where all those bits being zeroed out
  // are just zero.

  // Most compilers can generate this code but the pattern may be missed when
  // multiple functions gets inlined.
  return (Size + value - 1) & ~(value - 1);
}

/// Returns a multiple of A needed to store `Size` bytes.
/// Returns `Size` if current alignment is undefined.
inline uint64_t alignTo(uint64_t Size, MaybeAlign A) {
  return A ? alignTo(Size, A.getValue()) : Size;
}

/// Aligns `Addr` to `Alignment` bytes, rounding up.
inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
  uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
  assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
             ArithAddr && "Overflow");
  return alignTo(ArithAddr, Alignment);
}

/// Returns the offset to the next integer (mod 2**64) that is greater than
/// or equal to \p Value and is a multiple of \p Align.
inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
  return alignTo(Value, Alignment) - Value;
}

/// Returns the necessary adjustment for aligning `Addr` to `Alignment`
/// bytes, rounding up.
inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
  return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
}

/// Returns the log2 of the alignment.
inline unsigned Log2(Align A) { return A.ShiftValue; }

/// Returns the log2 of the alignment.
/// \pre A must be defined.
inline unsigned Log2(MaybeAlign A) {
  ALIGN_CHECK_ISSET(A);
  return Log2(A.getValue());
}

/// Returns the alignment that satisfies both alignments.
/// Same semantic as MinAlign.
inline Align commonAlignment(Align A, Align B) { return std::min(A, B); }

/// Returns the alignment that satisfies both alignments.
/// Same semantic as MinAlign.
inline Align commonAlignment(Align A, uint64_t Offset) {
  return Align(MinAlign(A.value(), Offset));
}

/// Returns the alignment that satisfies both alignments.
/// Same semantic as MinAlign.
inline MaybeAlign commonAlignment(MaybeAlign A, MaybeAlign B) {
  return A && B ? commonAlignment(*A, *B) : A ? A : B;
}

/// Returns the alignment that satisfies both alignments.
/// Same semantic as MinAlign.
inline MaybeAlign commonAlignment(MaybeAlign A, uint64_t Offset) {
  return MaybeAlign(MinAlign((*A).value(), Offset));
}

/// Returns a representation of the alignment that encodes undefined as 0.
inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }

/// Dual operation of the encode function above.
inline MaybeAlign decodeMaybeAlign(unsigned Value) {
  if (Value == 0)
    return MaybeAlign();
  Align Out;
  Out.ShiftValue = Value - 1;
  return Out;
}

/// Returns a representation of the alignment, the encoded value is positive by
/// definition.
inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }

/// Comparisons between Align and scalars. Rhs must be positive.
inline bool operator==(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() == Rhs;
}
inline bool operator!=(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() != Rhs;
}
inline bool operator<=(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() <= Rhs;
}
inline bool operator>=(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() >= Rhs;
}
inline bool operator<(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() < Rhs;
}
inline bool operator>(Align Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return Lhs.value() > Rhs;
}

/// Comparisons between MaybeAlign and scalars.
inline bool operator==(MaybeAlign Lhs, uint64_t Rhs) {
  return Lhs ? (*Lhs).value() == Rhs : Rhs == 0;
}
inline bool operator!=(MaybeAlign Lhs, uint64_t Rhs) {
  return Lhs ? (*Lhs).value() != Rhs : Rhs != 0;
}
inline bool operator<=(MaybeAlign Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return (*Lhs).value() <= Rhs;
}
inline bool operator>=(MaybeAlign Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return (*Lhs).value() >= Rhs;
}
inline bool operator<(MaybeAlign Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return (*Lhs).value() < Rhs;
}
inline bool operator>(MaybeAlign Lhs, uint64_t Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  ALIGN_CHECK_ISPOSITIVE(Rhs);
  return (*Lhs).value() > Rhs;
}

/// Comparisons operators between Align.
inline bool operator==(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue == Rhs.ShiftValue;
}
inline bool operator!=(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue != Rhs.ShiftValue;
}
inline bool operator<=(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue <= Rhs.ShiftValue;
}
inline bool operator>=(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue >= Rhs.ShiftValue;
}
inline bool operator<(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue < Rhs.ShiftValue;
}
inline bool operator>(Align Lhs, Align Rhs) {
  return Lhs.ShiftValue > Rhs.ShiftValue;
}

/// Comparisons operators between Align and MaybeAlign.
inline bool operator==(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() == (*Rhs).value();
}
inline bool operator!=(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() != (*Rhs).value();
}
inline bool operator<=(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() <= (*Rhs).value();
}
inline bool operator>=(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() >= (*Rhs).value();
}
inline bool operator<(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() < (*Rhs).value();
}
inline bool operator>(Align Lhs, MaybeAlign Rhs) {
  ALIGN_CHECK_ISSET(Rhs);
  return Lhs.value() > (*Rhs).value();
}

/// Comparisons operators between MaybeAlign and Align.
inline bool operator==(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() == Rhs.value();
}
inline bool operator!=(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() != Rhs.value();
}
inline bool operator<=(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() <= Rhs.value();
}
inline bool operator>=(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() >= Rhs.value();
}
inline bool operator<(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() < Rhs.value();
}
inline bool operator>(MaybeAlign Lhs, Align Rhs) {
  ALIGN_CHECK_ISSET(Lhs);
  return Lhs && (*Lhs).value() > Rhs.value();
}

inline Align operator/(Align Lhs, uint64_t Divisor) {
  assert(llvm::isPowerOf2_64(Divisor) &&
         "Divisor must be positive and a power of 2");
  assert(Lhs != 1 && "Can't halve byte alignment");
  return Align(Lhs.value() / Divisor);
}

inline MaybeAlign operator/(MaybeAlign Lhs, uint64_t Divisor) {
  assert(llvm::isPowerOf2_64(Divisor) &&
         "Divisor must be positive and a power of 2");
  return Lhs ? Lhs.getValue() / Divisor : MaybeAlign();
}

inline Align max(MaybeAlign Lhs, Align Rhs) {
  return Lhs && *Lhs > Rhs ? *Lhs : Rhs;
}

inline Align max(Align Lhs, MaybeAlign Rhs) {
  return Rhs && *Rhs > Lhs ? *Rhs : Lhs;
}

#undef ALIGN_CHECK_ISPOSITIVE
#undef ALIGN_CHECK_ISSET

} // namespace llvm

#endif // LLVM_SUPPORT_ALIGNMENT_H_