diff options
Diffstat (limited to 'libbase/include/core/memory/Alignment.h')
| -rw-r--r-- | libbase/include/core/memory/Alignment.h | 342 |
1 files changed, 342 insertions, 0 deletions
diff --git a/libbase/include/core/memory/Alignment.h b/libbase/include/core/memory/Alignment.h new file mode 100644 index 0000000..a3b5d38 --- /dev/null +++ b/libbase/include/core/memory/Alignment.h @@ -0,0 +1,342 @@ +/* + R *CC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===-- rcc/Memory/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 value() method. +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_SUPPORT_ALIGNMENT_H_ +#define LIBBASE_SUPPORT_ALIGNMENT_H_ + +#include "core/math/MathExtras.h" +#include <cassert> +#include <optional> +#ifndef NDEBUG +#include <string> +#endif // NDEBUG + +namespace rcc { + +#define ALIGN_CHECK_ISPOSITIVE(decl) \ + assert(decl > 0 && (#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); + +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; + constexpr Align &operator=(const Align &Other) = default; + constexpr Align &operator=(Align &&Other) = default; + + explicit Align(uint64_t Value) { + assert(Value > 0 && "Value must not be 0"); + assert(rcc::isPowerOf2_64(Value) && "Alignment is not a power of 2"); + ShiftValue = Log2_64(Value); + assert(ShiftValue < 64 && "Broken invariant"); + } + + /// Returns an alignment of `1 << Log2Value` bytes. + constexpr static Align fromLog2(unsigned Log2Value) { + assert(Log2Value < 64 && "Alignment exponent is too large"); + Align Out; + Out.ShiftValue = Log2Value; + return Out; + } + + /// This is a hole in the type system and should not be abused. + /// Needed to interact with C for instance. + constexpr uint64_t value() const { return uint64_t(1) << ShiftValue; } + + // Returns the previous alignment. + Align previous() const { + assert(ShiftValue != 0 && "Undefined operation"); + Align Out; + Out.ShiftValue = ShiftValue - 1; + return Out; + } + + /// Allow constructions of constexpr Align. + template <size_t kValue> constexpr static Align Constant() { + return fromLog2(ConstantLog2<kValue>()); + } + + /// Allow constructions of constexpr Align from types. + /// Compile time equivalent to Align(alignof(T)). + template <typename T> constexpr static Align Of() { + return Constant<std::alignment_of_v<T>>(); + } +}; + +/// 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 : std::optional<Align> { +private: + using UP = std::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; + + constexpr MaybeAlign(std::nullopt_t None) : UP(None) {} + constexpr MaybeAlign(Align Value) : UP(Value) {} + explicit MaybeAlign(uint64_t Value) { + assert((Value == 0 || rcc::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 value_or(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 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. +constexpr 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 - 1U); +} + +/// If non-zero \p Skew is specified, the return value will be a minimal integer +/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for +/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p +/// Skew mod \p A'. +/// +/// Examples: +/// \code +/// alignTo(5, Align(8), 7) = 7 +/// alignTo(17, Align(8), 1) = 17 +/// alignTo(~0LL, Align(8), 3) = 3 +/// \endcode +inline uint64_t alignTo(uint64_t Size, Align A, uint64_t Skew) { + const uint64_t Value = A.value(); + Skew %= Value; + return alignTo(Size - Skew, A) + Skew; +} + +/// 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 alignment that satisfies both alignments. +/// Same semantic as MinAlign. +inline Align commonAlignment(Align A, uint64_t Offset) { + return Align(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 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; +} + +// Don't allow relational comparisons with MaybeAlign. +bool operator<=(Align Lhs, MaybeAlign Rhs) = delete; +bool operator>=(Align Lhs, MaybeAlign Rhs) = delete; +bool operator<(Align Lhs, MaybeAlign Rhs) = delete; +bool operator>(Align Lhs, MaybeAlign Rhs) = delete; + +bool operator<=(MaybeAlign Lhs, Align Rhs) = delete; +bool operator>=(MaybeAlign Lhs, Align Rhs) = delete; +bool operator<(MaybeAlign Lhs, Align Rhs) = delete; +bool operator>(MaybeAlign Lhs, Align Rhs) = delete; + +bool operator<=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator>=(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator<(MaybeAlign Lhs, MaybeAlign Rhs) = delete; +bool operator>(MaybeAlign Lhs, MaybeAlign Rhs) = delete; + +// Allow equality comparisons between Align and MaybeAlign. +inline bool operator==(MaybeAlign Lhs, Align Rhs) { return Lhs && *Lhs == Rhs; } +inline bool operator!=(MaybeAlign Lhs, Align Rhs) { return !(Lhs == Rhs); } +inline bool operator==(Align Lhs, MaybeAlign Rhs) { return Rhs == Lhs; } +inline bool operator!=(Align Lhs, MaybeAlign Rhs) { return !(Rhs == Lhs); } +// Allow equality comparisons with MaybeAlign. +inline bool operator==(MaybeAlign Lhs, MaybeAlign Rhs) { + return (Lhs && Rhs && (*Lhs == *Rhs)) || (!Lhs && !Rhs); +} +inline bool operator!=(MaybeAlign Lhs, MaybeAlign Rhs) { return !(Lhs == Rhs); } +// Allow equality comparisons with std::nullopt. +inline bool operator==(MaybeAlign Lhs, std::nullopt_t) { return !bool(Lhs); } +inline bool operator!=(MaybeAlign Lhs, std::nullopt_t) { return bool(Lhs); } +inline bool operator==(std::nullopt_t, MaybeAlign Rhs) { return !bool(Rhs); } +inline bool operator!=(std::nullopt_t, MaybeAlign Rhs) { return bool(Rhs); } + +#ifndef NDEBUG +// For usage in LLVM_DEBUG macros. +inline std::string DebugStr(const Align &A) { + return std::to_string(A.value()); +} +// For usage in LLVM_DEBUG macros. +inline std::string DebugStr(const MaybeAlign &MA) { + if (MA) + return std::to_string(MA->value()); + return "None"; +} +#endif // NDEBUG + +#undef ALIGN_CHECK_ISPOSITIVE + +} // namespace rcc + +#endif // LIBBASE_SUPPORT_ALIGNMENT_H_ |