llvm/Support/Alignment.h

0001 //===-- llvm/Support/Alignment.h - Useful alignment functions ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file contains types to represent alignments.
0010 // They are instrumented to guarantee some invariants are preserved and prevent
0011 // invalid manipulations.
0012 //
0013 // - Align represents an alignment in bytes, it is always set and always a valid
0014 // power of two, its minimum value is 1 which means no alignment requirements.
0015 //
0016 // - MaybeAlign is an optional type, it may be undefined or set. When it's set
0017 // you can get the underlying Align type by using the value() method.
0018 //
0019 //===----------------------------------------------------------------------===//
0020
0021 #ifndef LLVM_SUPPORT_ALIGNMENT_H_
0022 #define LLVM_SUPPORT_ALIGNMENT_H_
0023
0024 #include "llvm/Support/MathExtras.h"
0025 #include <cassert>
0026 #include <optional>
0027 #ifndef NDEBUG
0028 #include <string>
0029 #endif // NDEBUG
0030
0031 namespace llvm {
0032
0033 #define ALIGN_CHECK_ISPOSITIVE(decl)                                           \
0034   assert(decl > 0 && (#decl " should be defined"))
0035
0036 /// This struct is a compact representation of a valid (non-zero power of two)
0037 /// alignment.
0038 /// It is suitable for use as static global constants.
0039 struct Align {
0040 private:
0041   uint8_t ShiftValue = 0; /// The log2 of the required alignment.
0042                           /// ShiftValue is less than 64 by construction.
0043
0044   friend struct MaybeAlign;
0045   friend unsigned Log2(Align);
0046   friend bool operator==(Align Lhs, Align Rhs);
0047   friend bool operator!=(Align Lhs, Align Rhs);
0048   friend bool operator<=(Align Lhs, Align Rhs);
0049   friend bool operator>=(Align Lhs, Align Rhs);
0050   friend bool operator<(Align Lhs, Align Rhs);
0051   friend bool operator>(Align Lhs, Align Rhs);
0052   friend unsigned encode(struct MaybeAlign A);
0053   friend struct MaybeAlign decodeMaybeAlign(unsigned Value);
0054
0055   /// A trivial type to allow construction of constexpr Align.
0056   /// This is currently needed to workaround a bug in GCC 5.3 which prevents
0057   /// definition of constexpr assign operators.
0058   /// https://stackoverflow.com/questions/46756288/explicitly-defaulted-function-cannot-be-declared-as-constexpr-because-the-implic
0059   /// FIXME: Remove this, make all assign operators constexpr and introduce user
0060   /// defined literals when we don't have to support GCC 5.3 anymore.
0061   /// https://llvm.org/docs/GettingStarted.html#getting-a-modern-host-c-toolchain
0062   struct LogValue {
0063     uint8_t Log;
0064   };
0065
0066 public:
0067   /// Default is byte-aligned.
0068   constexpr Align() = default;
0069   /// Do not perform checks in case of copy/move construct/assign, because the
0070   /// checks have been performed when building `Other`.
0071   constexpr Align(const Align &Other) = default;
0072   constexpr Align(Align &&Other) = default;
0073   Align &operator=(const Align &Other) = default;
0074   Align &operator=(Align &&Other) = default;
0075
0076   explicit Align(uint64_t Value) {
0077     assert(Value > 0 && "Value must not be 0");
0078     assert(llvm::isPowerOf2_64(Value) && "Alignment is not a power of 2");
0079     ShiftValue = Log2_64(Value);
0080     assert(ShiftValue < 64 && "Broken invariant");
0081   }
0082
0083   /// This is a hole in the type system and should not be abused.
0084   /// Needed to interact with C for instance.
0085   uint64_t value() const { return uint64_t(1) << ShiftValue; }
0086
0087   // Returns the previous alignment.
0088   Align previous() const {
0089     assert(ShiftValue != 0 && "Undefined operation");
0090     Align Out;
0091     Out.ShiftValue = ShiftValue - 1;
0092     return Out;
0093   }
0094
0095   /// Allow constructions of constexpr Align.
0096   template <size_t kValue> constexpr static Align Constant() {
0097     return LogValue{static_cast<uint8_t>(CTLog2<kValue>())};
0098   }
0099
0100   /// Allow constructions of constexpr Align from types.
0101   /// Compile time equivalent to Align(alignof(T)).
0102   template <typename T> constexpr static Align Of() {
0103     return Constant<std::alignment_of_v<T>>();
0104   }
0105
0106   /// Constexpr constructor from LogValue type.
0107   constexpr Align(LogValue CA) : ShiftValue(CA.Log) {}
0108 };
0109
0110 /// Treats the value 0 as a 1, so Align is always at least 1.
0111 inline Align assumeAligned(uint64_t Value) {
0112   return Value ? Align(Value) : Align();
0113 }
0114
0115 /// This struct is a compact representation of a valid (power of two) or
0116 /// undefined (0) alignment.
0117 struct MaybeAlign : public std::optional<Align> {
0118 private:
0119   using UP = std::optional<Align>;
0120
0121 public:
0122   /// Default is undefined.
0123   MaybeAlign() = default;
0124   /// Do not perform checks in case of copy/move construct/assign, because the
0125   /// checks have been performed when building `Other`.
0126   MaybeAlign(const MaybeAlign &Other) = default;
0127   MaybeAlign &operator=(const MaybeAlign &Other) = default;
0128   MaybeAlign(MaybeAlign &&Other) = default;
0129   MaybeAlign &operator=(MaybeAlign &&Other) = default;
0130
0131   constexpr MaybeAlign(std::nullopt_t None) : UP(None) {}
0132   constexpr MaybeAlign(Align Value) : UP(Value) {}
0133   explicit MaybeAlign(uint64_t Value) {
0134     assert((Value == 0 || llvm::isPowerOf2_64(Value)) &&
0135            "Alignment is neither 0 nor a power of 2");
0136     if (Value)
0137       emplace(Value);
0138   }
0139
0140   /// For convenience, returns a valid alignment or 1 if undefined.
0141   Align valueOrOne() const { return value_or(Align()); }
0142 };
0143
0144 /// Checks that SizeInBytes is a multiple of the alignment.
0145 inline bool isAligned(Align Lhs, uint64_t SizeInBytes) {
0146   return SizeInBytes % Lhs.value() == 0;
0147 }
0148
0149 /// Checks that Addr is a multiple of the alignment.
0150 inline bool isAddrAligned(Align Lhs, const void *Addr) {
0151   return isAligned(Lhs, reinterpret_cast<uintptr_t>(Addr));
0152 }
0153
0154 /// Returns a multiple of A needed to store `Size` bytes.
0155 inline uint64_t alignTo(uint64_t Size, Align A) {
0156   const uint64_t Value = A.value();
0157   // The following line is equivalent to `(Size + Value - 1) / Value * Value`.
0158
0159   // The division followed by a multiplication can be thought of as a right
0160   // shift followed by a left shift which zeros out the extra bits produced in
0161   // the bump; `~(Value - 1)` is a mask where all those bits being zeroed out
0162   // are just zero.
0163
0164   // Most compilers can generate this code but the pattern may be missed when
0165   // multiple functions gets inlined.
0166   return (Size + Value - 1) & ~(Value - 1U);
0167 }
0168
0169 /// If non-zero \p Skew is specified, the return value will be a minimal integer
0170 /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
0171 /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
0172 /// Skew mod \p A'.
0173 ///
0174 /// Examples:
0175 /// \code
0176 ///   alignTo(5, Align(8), 7) = 7
0177 ///   alignTo(17, Align(8), 1) = 17
0178 ///   alignTo(~0LL, Align(8), 3) = 3
0179 /// \endcode
0180 inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) {
0181   const uint64_t Value = A.value();
0182   Skew %= Value;
0183   return alignTo(Size - Skew, A) + Skew;
0184 }
0185
0186 /// Aligns `Addr` to `Alignment` bytes, rounding up.
0187 inline uintptr_t alignAddr(const void *Addr, Align Alignment) {
0188   uintptr_t ArithAddr = reinterpret_cast<uintptr_t>(Addr);
0189   assert(static_cast<uintptr_t>(ArithAddr + Alignment.value() - 1) >=
0190              ArithAddr &&
0191          "Overflow");
0192   return alignTo(ArithAddr, Alignment);
0193 }
0194
0195 /// Returns the offset to the next integer (mod 2**64) that is greater than
0196 /// or equal to \p Value and is a multiple of \p Align.
0197 inline uint64_t offsetToAlignment(uint64_t Value, Align Alignment) {
0198   return alignTo(Value, Alignment) - Value;
0199 }
0200
0201 /// Returns the necessary adjustment for aligning `Addr` to `Alignment`
0202 /// bytes, rounding up.
0203 inline uint64_t offsetToAlignedAddr(const void *Addr, Align Alignment) {
0204   return offsetToAlignment(reinterpret_cast<uintptr_t>(Addr), Alignment);
0205 }
0206
0207 /// Returns the log2 of the alignment.
0208 inline unsigned Log2(Align A) { return A.ShiftValue; }
0209
0210 /// Returns the alignment that satisfies both alignments.
0211 /// Same semantic as MinAlign.
0212 inline Align commonAlignment(Align A, uint64_t Offset) {
0213   return Align(MinAlign(A.value(), Offset));
0214 }
0215
0216 /// Returns a representation of the alignment that encodes undefined as 0.
0217 inline unsigned encode(MaybeAlign A) { return A ? A->ShiftValue + 1 : 0; }
0218
0219 /// Dual operation of the encode function above.
0220 inline MaybeAlign decodeMaybeAlign(unsigned Value) {
0221   if (Value == 0)
0222     return MaybeAlign();
0223   Align Out;
0224   Out.ShiftValue = Value - 1;
0225   return Out;
0226 }
0227
0228 /// Returns a representation of the alignment, the encoded value is positive by
0229 /// definition.
0230 inline unsigned encode(Align A) { return encode(MaybeAlign(A)); }
0231
0232 /// Comparisons between Align and scalars. Rhs must be positive.
0233 inline bool operator==(Align Lhs, uint64_t Rhs) {
0234   ALIGN_CHECK_ISPOSITIVE(Rhs);
0235   return Lhs.value() == Rhs;
0236 }
0237 inline bool operator!=(Align Lhs, uint64_t Rhs) {
0238   ALIGN_CHECK_ISPOSITIVE(Rhs);
0239   return Lhs.value() != Rhs;
0240 }
0241 inline bool operator<=(Align Lhs, uint64_t Rhs) {
0242   ALIGN_CHECK_ISPOSITIVE(Rhs);
0243   return Lhs.value() <= Rhs;
0244 }
0245 inline bool operator>=(Align Lhs, uint64_t Rhs) {
0246   ALIGN_CHECK_ISPOSITIVE(Rhs);
0247   return Lhs.value() >= Rhs;
0248 }
0249 inline bool operator<(Align Lhs, uint64_t Rhs) {
0250   ALIGN_CHECK_ISPOSITIVE(Rhs);
0251   return Lhs.value() < Rhs;
0252 }
0253 inline bool operator>(Align Lhs, uint64_t Rhs) {
0254   ALIGN_CHECK_ISPOSITIVE(Rhs);
0255   return Lhs.value() > Rhs;
0256 }
0257
0258 /// Comparisons operators between Align.
0259 inline bool operator==(Align Lhs, Align Rhs) {
0260   return Lhs.ShiftValue == Rhs.ShiftValue;
0261 }
0262 inline bool operator!=(Align Lhs, Align Rhs) {
0263   return Lhs.ShiftValue != Rhs.ShiftValue;
0264 }
0265 inline bool operator<=(Align Lhs, Align Rhs) {
0266   return Lhs.ShiftValue <= Rhs.ShiftValue;
0267 }
0268 inline bool operator>=(Align Lhs, Align Rhs) {
0269   return Lhs.ShiftValue >= Rhs.ShiftValue;
0270 }
0271 inline bool operator<(Align Lhs, Align Rhs) {
0272   return Lhs.ShiftValue < Rhs.ShiftValue;
0273 }
0274 inline bool operator>(Align Lhs, Align Rhs) {
0275   return Lhs.ShiftValue > Rhs.ShiftValue;
0276 }
0277
0278 // Don't allow relational comparisons with MaybeAlign.
0279 bool operator<=(Align Lhs, MaybeAlign Rhs) = delete;
0280 bool operator>=(Align Lhs, MaybeAlign Rhs) = delete;
0281 bool operator<(Align Lhs, MaybeAlign Rhs) = delete;
0282 bool operator>(Align Lhs, MaybeAlign Rhs) = delete;
0283
0284 bool operator<=(MaybeAlign Lhs, Align Rhs) = delete;
0285 bool operator>=(MaybeAlign Lhs, Align Rhs) = delete;
0286 bool operator<(MaybeAlign Lhs, Align Rhs) = delete;
0287 bool operator>(MaybeAlign Lhs, Align Rhs) = delete;
0288
0289 bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
0290 bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
0291 bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
0292 bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete;
0293
0294 // Allow equality comparisons between Align and MaybeAlign.
0295 inline bool operator==(MaybeAlign Lhs, Align Rhs) { return Lhs && *Lhs == Rhs; }
0296 inline bool operator!=(MaybeAlign Lhs, Align Rhs) { return !(Lhs == Rhs); }
0297 inline bool operator==(Align Lhs, MaybeAlign Rhs) { return Rhs == Lhs; }
0298 inline bool operator!=(Align Lhs, MaybeAlign Rhs) { return !(Rhs == Lhs); }
0299 // Allow equality comparisons with MaybeAlign.
0300 inline bool operator==(MaybeAlign Lhs, MaybeAlign Rhs) {
0301   return (Lhs && Rhs && (*Lhs == *Rhs)) || (!Lhs && !Rhs);
0302 }
0303 inline bool operator!=(MaybeAlign Lhs, MaybeAlign Rhs) { return !(Lhs == Rhs); }
0304 // Allow equality comparisons with std::nullopt.
0305 inline bool operator==(MaybeAlign Lhs, std::nullopt_t) { return !bool(Lhs); }
0306 inline bool operator!=(MaybeAlign Lhs, std::nullopt_t) { return bool(Lhs); }
0307 inline bool operator==(std::nullopt_t, MaybeAlign Rhs) { return !bool(Rhs); }
0308 inline bool operator!=(std::nullopt_t, MaybeAlign Rhs) { return bool(Rhs); }
0309
0310 #ifndef NDEBUG
0311 // For usage in LLVM_DEBUG macros.
0312 inline std::string DebugStr(const Align &A) {
0313   return std::to_string(A.value());
0314 }
0315 // For usage in LLVM_DEBUG macros.
0316 inline std::string DebugStr(const MaybeAlign &MA) {
0317   if (MA)
0318     return std::to_string(MA->value());
0319   return "None";
0320 }
0321 #endif // NDEBUG
0322
0323 #undef ALIGN_CHECK_ISPOSITIVE
0324
0325 } // namespace llvm
0326
0327 #endif // LLVM_SUPPORT_ALIGNMENT_H_