9 files changed, 1071 insertions, 5 deletions

diff --git a/backend/include/rcc/CodeGen/MachineIRTypes.h b/backend/include/rcc/CodeGen/MachineIRTypes.h
new file mode 100644
index 0000000..6d2a710
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineIRTypes.h
@@ -0,0 +1,274 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEIRTYPES_H
+#define RCC_CODEGEN_MACHINEIRTYPES_H
+
+#include "rcc/Support/Error.h"
+
+#include <bit>
+#include <compare>
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <initializer_list>
+#include <string>
+#include <type_traits>
+
+namespace rcc {
+
+template <typename TagT, typename ValueT = std::uint32_t> class MachineIndex final {
+public:
+  constexpr MachineIndex() noexcept = default;
+
+  [[nodiscard]] static constexpr MachineIndex fromValue(ValueT Value) noexcept {
+    return MachineIndex(Value);
+  }
+
+  [[nodiscard]] constexpr ValueT value() const noexcept {
+    return Value;
+  }
+
+  friend constexpr bool operator==(MachineIndex Left, MachineIndex Right) noexcept = default;
+  friend constexpr auto operator<=>(MachineIndex Left, MachineIndex Right) noexcept = default;
+
+private:
+  explicit constexpr MachineIndex(ValueT Value) noexcept : Value(Value) {}
+
+  ValueT Value = 0;
+};
+
+namespace detail {
+
+struct FrameIndexTag;
+struct ConstantPoolIndexTag;
+struct JumpTableIndexTag;
+struct TargetIndexTag;
+struct SubRegIndexTag;
+struct RegisterBankIDTag;
+struct RegisterClassIDTag;
+struct SchedulingClassIDTag;
+struct SyncScopeIDTag;
+struct MemoryAliasSourceIDTag;
+struct OriginIDTag;
+
+} // namespace detail
+
+using FrameIndex = MachineIndex<detail::FrameIndexTag>;
+using ConstantPoolIndex = MachineIndex<detail::ConstantPoolIndexTag>;
+using JumpTableIndex = MachineIndex<detail::JumpTableIndexTag>;
+using TargetIndex = MachineIndex<detail::TargetIndexTag>;
+using SubRegIndex = MachineIndex<detail::SubRegIndexTag>;
+using RegisterBankID = MachineIndex<detail::RegisterBankIDTag>;
+using RegisterClassID = MachineIndex<detail::RegisterClassIDTag>;
+using SchedulingClassID = MachineIndex<detail::SchedulingClassIDTag>;
+using SyncScopeID = MachineIndex<detail::SyncScopeIDTag>;
+using MemoryAliasSourceID = MachineIndex<detail::MemoryAliasSourceIDTag, std::uint64_t>;
+using OriginID = MachineIndex<detail::OriginIDTag, std::uint64_t>;
+
+class Opcode final {
+public:
+  constexpr Opcode() noexcept = default;
+
+  [[nodiscard]] static constexpr Opcode fromValue(std::uint32_t Value) noexcept {
+    return Opcode(Value);
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != 0;
+  }
+
+  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
+    return Value;
+  }
+
+  friend constexpr bool operator==(Opcode Left, Opcode Right) noexcept = default;
+
+private:
+  explicit constexpr Opcode(std::uint32_t Value) noexcept : Value(Value) {}
+
+  std::uint32_t Value = 0;
+};
+
+class LaneMask final {
+public:
+  constexpr LaneMask() noexcept = default;
+
+  [[nodiscard]] static constexpr LaneMask fromRaw(std::uint64_t RawValue) noexcept {
+    return LaneMask(RawValue);
+  }
+
+  [[nodiscard]] static constexpr LaneMask all() noexcept {
+    return LaneMask(~std::uint64_t{0});
+  }
+
+  [[nodiscard]] constexpr bool empty() const noexcept {
+    return RawValue == 0;
+  }
+
+  [[nodiscard]] constexpr bool intersects(LaneMask Other) const noexcept {
+    return (RawValue & Other.RawValue) != 0;
+  }
+
+  [[nodiscard]] constexpr bool contains(LaneMask Other) const noexcept {
+    return (RawValue & Other.RawValue) == Other.RawValue;
+  }
+
+  [[nodiscard]] constexpr std::uint64_t rawValue() const noexcept {
+    return RawValue;
+  }
+
+  friend constexpr bool operator==(LaneMask Left, LaneMask Right) noexcept = default;
+
+  friend constexpr LaneMask operator|(LaneMask Left, LaneMask Right) noexcept {
+    return LaneMask(Left.RawValue | Right.RawValue);
+  }
+
+  friend constexpr LaneMask operator&(LaneMask Left, LaneMask Right) noexcept {
+    return LaneMask(Left.RawValue & Right.RawValue);
+  }
+
+private:
+  explicit constexpr LaneMask(std::uint64_t RawValue) noexcept : RawValue(RawValue) {}
+
+  std::uint64_t RawValue = 0;
+};
+
+class BranchProbability final {
+public:
+  constexpr BranchProbability() noexcept = default;
+
+  [[nodiscard]] static constexpr BranchProbability zero() noexcept {
+    return BranchProbability(0);
+  }
+
+  [[nodiscard]] static constexpr BranchProbability one() noexcept {
+    return BranchProbability(MaxRawValue);
+  }
+
+  [[nodiscard]] static constexpr BranchProbability fromRaw(std::uint32_t RawValue) noexcept {
+    return BranchProbability(RawValue);
+  }
+
+  [[nodiscard]] static Expected<BranchProbability> fromFraction(std::uint32_t Numerator,
+                                                                std::uint32_t Denominator);
+
+  [[nodiscard]] constexpr std::uint32_t rawValue() const noexcept {
+    return RawValue;
+  }
+
+  [[nodiscard]] constexpr BranchProbability saturatingAdd(BranchProbability Other) const noexcept {
+    if (MaxRawValue - RawValue < Other.RawValue)
+      return one();
+    return BranchProbability(RawValue + Other.RawValue);
+  }
+
+  [[nodiscard]] constexpr BranchProbability complement() const noexcept {
+    return BranchProbability(MaxRawValue - RawValue);
+  }
+
+  friend constexpr bool operator==(BranchProbability Left,
+                                   BranchProbability Right) noexcept = default;
+  friend constexpr auto operator<=>(BranchProbability Left,
+                                    BranchProbability Right) noexcept = default;
+
+private:
+  static constexpr std::uint32_t MaxRawValue = ~std::uint32_t{0};
+
+  explicit constexpr BranchProbability(std::uint32_t RawValue) noexcept : RawValue(RawValue) {}
+
+  std::uint32_t RawValue = 0;
+};
+
+enum class MachineInstrFlag : std::uint8_t {
+  NoSignedWrap,
+  NoUnsignedWrap,
+  Exact,
+  NoFPExcept,
+  FastMathAllowReassoc,
+  FastMathNoNaNs,
+  FastMathNoInfs,
+  FastMathNoSignedZeros,
+  FastMathAllowReciprocal,
+  FastMathAllowContract,
+  FastMathApproxFunc,
+  FrameSetup,
+  FrameDestroy,
+  BundledWithPred,
+  BundledWithSucc,
+  NoMerge,
+  Unpredictable,
+  Count,
+};
+
+class MachineInstrFlags final {
+public:
+  constexpr MachineInstrFlags() noexcept = default;
+
+  MachineInstrFlags(std::initializer_list<MachineInstrFlag> Flags) noexcept;
+
+  [[nodiscard]] constexpr bool has(MachineInstrFlag Flag) const noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index >= static_cast<std::uint32_t>(MachineInstrFlag::Count))
+      return false;
+    return (Mask & (std::uint32_t{1} << Index)) != 0;
+  }
+
+  constexpr void set(MachineInstrFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index < static_cast<std::uint32_t>(MachineInstrFlag::Count))
+      Mask |= std::uint32_t{1} << Index;
+  }
+
+  constexpr void clear(MachineInstrFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index < static_cast<std::uint32_t>(MachineInstrFlag::Count))
+      Mask &= ~(std::uint32_t{1} << Index);
+  }
+
+  [[nodiscard]] constexpr std::uint32_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  friend constexpr bool operator==(MachineInstrFlags Left,
+                                   MachineInstrFlags Right) noexcept = default;
+
+private:
+  std::uint32_t Mask = 0;
+};
+
+struct SourceLocation final {
+  std::string File;
+  std::uint32_t Line = 0;
+  std::uint32_t Column = 0;
+  std::uint32_t Discriminator = 0;
+
+  [[nodiscard]] bool isValid() const noexcept {
+    return !File.empty() && Line != 0;
+  }
+
+  friend bool operator==(const SourceLocation &Left, const SourceLocation &Right) = default;
+};
+
+static_assert(sizeof(Opcode) == sizeof(std::uint32_t));
+static_assert(sizeof(FrameIndex) == sizeof(std::uint32_t));
+static_assert(sizeof(MemoryAliasSourceID) == sizeof(std::uint64_t));
+static_assert(std::is_trivially_copyable_v<Opcode>);
+static_assert(std::is_trivially_copyable_v<FrameIndex>);
+static_assert(std::is_trivially_copyable_v<LaneMask>);
+static_assert(std::is_trivially_copyable_v<BranchProbability>);
+
+} // namespace rcc
+
+template <typename TagT, typename ValueT> struct std::hash<rcc::MachineIndex<TagT, ValueT>> {
+  [[nodiscard]] std::size_t operator()(rcc::MachineIndex<TagT, ValueT> Index) const noexcept {
+    return std::hash<ValueT>{}(Index.value());
+  }
+};
+
+template <> struct std::hash<rcc::Opcode> {
+  [[nodiscard]] std::size_t operator()(rcc::Opcode Value) const noexcept {
+    return std::hash<std::uint32_t>{}(Value.value());
+  }
+};
+
+#endif // RCC_CODEGEN_MACHINEIRTYPES_H
diff --git a/backend/include/rcc/CodeGen/MachineMemOperand.h b/backend/include/rcc/CodeGen/MachineMemOperand.h
new file mode 100644
index 0000000..52514f9
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineMemOperand.h
@@ -0,0 +1,245 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEMEMOPERAND_H
+#define RCC_CODEGEN_MACHINEMEMOPERAND_H
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineIRTypes.h"
+
+#include <cstdint>
+#include <initializer_list>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <variant>
+
+namespace rcc {
+
+enum class MemoryAccessFlag : std::uint8_t {
+  Load,
+  Store,
+  Volatile,
+  Invariant,
+  Dereferenceable,
+  NonTemporal,
+  Count,
+};
+
+class MemoryAccessFlags final {
+public:
+  constexpr MemoryAccessFlags() noexcept = default;
+
+  MemoryAccessFlags(std::initializer_list<MemoryAccessFlag> Flags) noexcept;
+
+  [[nodiscard]] constexpr bool has(MemoryAccessFlag Flag) const noexcept {
+    const auto Index = static_cast<std::uint8_t>(Flag);
+    if (Index >= static_cast<std::uint8_t>(MemoryAccessFlag::Count))
+      return false;
+    return (Mask & (std::uint8_t{1} << Index)) != 0;
+  }
+
+  constexpr void set(MemoryAccessFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint8_t>(Flag);
+    if (Index < static_cast<std::uint8_t>(MemoryAccessFlag::Count))
+      Mask |= std::uint8_t{1} << Index;
+  }
+
+  constexpr void clear(MemoryAccessFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint8_t>(Flag);
+    if (Index < static_cast<std::uint8_t>(MemoryAccessFlag::Count))
+      Mask &= static_cast<std::uint8_t>(~(std::uint8_t{1} << Index));
+  }
+
+  [[nodiscard]] constexpr std::uint8_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  friend constexpr bool operator==(MemoryAccessFlags Left,
+                                   MemoryAccessFlags Right) noexcept = default;
+
+private:
+  std::uint8_t Mask = 0;
+};
+
+enum class AtomicOperation : std::uint8_t {
+  None,
+  Load,
+  Store,
+  ReadModifyWrite,
+  CompareExchange,
+};
+
+enum class AtomicOrdering : std::uint8_t {
+  NotAtomic,
+  Unordered,
+  Monotonic,
+  Acquire,
+  Release,
+  AcquireRelease,
+  SequentiallyConsistent,
+};
+
+class Alignment final {
+public:
+  constexpr Alignment() noexcept = default;
+
+  [[nodiscard]] static Expected<Alignment> create(std::uint64_t Bytes);
+
+  [[nodiscard]] constexpr std::uint64_t bytes() const noexcept {
+    return Bytes;
+  }
+
+  friend constexpr bool operator==(Alignment Left, Alignment Right) noexcept = default;
+
+private:
+  explicit constexpr Alignment(std::uint64_t Bytes) noexcept : Bytes(Bytes) {}
+
+  std::uint64_t Bytes = 1;
+};
+
+class MemorySize final {
+public:
+  enum class Kind : std::uint8_t {
+    Unknown,
+    Fixed,
+    Scalable,
+  };
+
+  constexpr MemorySize() noexcept = default;
+
+  [[nodiscard]] static Expected<MemorySize> fixed(std::uint64_t Bytes);
+  [[nodiscard]] static Expected<MemorySize> scalable(std::uint64_t MinimumBytes);
+
+  [[nodiscard]] constexpr Kind kind() const noexcept {
+    return SizeKind;
+  }
+
+  [[nodiscard]] constexpr bool isKnown() const noexcept {
+    return SizeKind != Kind::Unknown;
+  }
+
+  [[nodiscard]] constexpr bool isScalable() const noexcept {
+    return SizeKind == Kind::Scalable;
+  }
+
+  [[nodiscard]] constexpr std::uint64_t minimumBytes() const noexcept {
+    return MinimumBytes;
+  }
+
+  friend constexpr bool operator==(MemorySize Left, MemorySize Right) noexcept = default;
+
+private:
+  constexpr MemorySize(Kind SizeKind, std::uint64_t MinimumBytes) noexcept
+      : SizeKind(SizeKind), MinimumBytes(MinimumBytes) {}
+
+  Kind SizeKind = Kind::Unknown;
+  std::uint64_t MinimumBytes = 0;
+};
+
+struct MemoryOffsetRange final {
+  std::int64_t Lower = 0;
+  std::int64_t Upper = 0;
+
+  [[nodiscard]] static Expected<MemoryOffsetRange> create(std::int64_t Lower, std::int64_t Upper);
+
+  friend constexpr bool operator==(MemoryOffsetRange Left,
+                                   MemoryOffsetRange Right) noexcept = default;
+};
+
+class MemoryBase final {
+public:
+  enum class Kind : std::uint8_t {
+    Unknown,
+    FrameIndex,
+    ConstantPool,
+    JumpTable,
+    GlobalSymbol,
+    ExternalSymbol,
+  };
+
+  MemoryBase() = default;
+
+  [[nodiscard]] static MemoryBase frameIndex(FrameIndex Index);
+  [[nodiscard]] static MemoryBase constantPool(ConstantPoolIndex Index);
+  [[nodiscard]] static MemoryBase jumpTable(JumpTableIndex Index);
+  [[nodiscard]] static MemoryBase globalSymbol(std::string Name);
+  [[nodiscard]] static MemoryBase externalSymbol(std::string Name);
+
+  [[nodiscard]] Kind kind() const noexcept {
+    return BaseKind;
+  }
+
+  [[nodiscard]] std::optional<FrameIndex> frameIndex() const noexcept;
+  [[nodiscard]] std::optional<ConstantPoolIndex> constantPoolIndex() const noexcept;
+  [[nodiscard]] std::optional<JumpTableIndex> jumpTableIndex() const noexcept;
+  [[nodiscard]] std::optional<std::string_view> symbolName() const noexcept;
+
+  friend bool operator==(const MemoryBase &Left, const MemoryBase &Right) = default;
+
+private:
+  using Storage =
+      std::variant<std::monostate, FrameIndex, ConstantPoolIndex, JumpTableIndex, std::string>;
+
+  MemoryBase(Kind BaseKind, Storage Value) : BaseKind(BaseKind), Value(std::move(Value)) {}
+
+  Kind BaseKind = Kind::Unknown;
+  Storage Value;
+};
+
+struct MachineMemOperandDesc final {
+  MemoryAccessFlags Accesses;
+  AtomicOperation AtomicKind = AtomicOperation::None;
+  AtomicOrdering SuccessOrdering = AtomicOrdering::NotAtomic;
+  AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic;
+  SyncScopeID SyncScope;
+  MemorySize Size;
+  Alignment Align;
+  std::uint32_t AddressSpace = 0;
+  MemoryBase Base;
+  std::int64_t Offset = 0;
+  std::optional<MemoryOffsetRange> OffsetRange;
+  std::optional<MemoryAliasSourceID> AliasSource;
+
+  friend bool operator==(const MachineMemOperandDesc &Left,
+                         const MachineMemOperandDesc &Right) = default;
+};
+
+class MachineMemOperand final {
+public:
+  [[nodiscard]] static Expected<MachineMemOperand> create(MachineMemOperandDesc Description);
+
+  [[nodiscard]] const MachineMemOperandDesc &description() const noexcept {
+    return Description;
+  }
+
+  [[nodiscard]] bool isLoad() const noexcept {
+    return Description.Accesses.has(MemoryAccessFlag::Load);
+  }
+
+  [[nodiscard]] bool isStore() const noexcept {
+    return Description.Accesses.has(MemoryAccessFlag::Store);
+  }
+
+  [[nodiscard]] bool isAtomic() const noexcept {
+    return Description.AtomicKind != AtomicOperation::None;
+  }
+
+  [[nodiscard]] bool isVolatile() const noexcept {
+    return Description.Accesses.has(MemoryAccessFlag::Volatile);
+  }
+
+  friend bool operator==(const MachineMemOperand &Left, const MachineMemOperand &Right) = default;
+
+private:
+  explicit MachineMemOperand(MachineMemOperandDesc Description)
+      : Description(std::move(Description)) {}
+
+  MachineMemOperandDesc Description;
+};
+
+[[nodiscard]] std::string_view getAtomicOrderingName(AtomicOrdering Ordering) noexcept;
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEMEMOPERAND_H
diff --git a/backend/include/rcc/CodeGen/RegisterMask.h b/backend/include/rcc/CodeGen/RegisterMask.h
new file mode 100644
index 0000000..d5a5b71
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegisterMask.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGISTERMASK_H
+#define RCC_CODEGEN_REGISTERMASK_H
+
+#include "rcc/CodeGen/Register.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class RegisterMask final {
+public:
+  explicit RegisterMask(std::vector<std::uint64_t> PreservedWords)
+      : PreservedWords(std::move(PreservedWords)) {}
+
+  [[nodiscard]] bool preserves(PhysicalRegister PhysReg) const noexcept;
+
+  [[nodiscard]] bool clobbers(PhysicalRegister PhysReg) const noexcept {
+    return !preserves(PhysReg);
+  }
+
+  [[nodiscard]] std::span<const std::uint64_t> words() const noexcept {
+    return PreservedWords;
+  }
+
+  friend bool operator==(const RegisterMask &Left, const RegisterMask &Right) = default;
+
+private:
+  std::vector<std::uint64_t> PreservedWords;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGISTERMASK_H
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index f5b5b23..8a45878 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -3,14 +3,20 @@
 set(
   RCCBackendCodeGenSources
   LowLevelType.cpp
+  MachineIRTypes.cpp
+  MachineMemOperand.cpp
   MachineFunctionProperties.cpp
   Register.cpp
+  RegisterMask.cpp
 )
 set(
   RCCBackendCodeGenHeaders
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h"
 )
 
@@ -44,12 +50,18 @@ install(
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
   ${RCCBackendCodeGenHeaders}
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
 )
diff --git a/backend/lib/CodeGen/MachineIRTypes.cpp b/backend/lib/CodeGen/MachineIRTypes.cpp
new file mode 100644
index 0000000..7f97e98
--- /dev/null
+++ b/backend/lib/CodeGen/MachineIRTypes.cpp
@@ -0,0 +1,29 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+
+namespace rcc {
+
+Expected<BranchProbability> BranchProbability::fromFraction(std::uint32_t Numerator,
+                                                            std::uint32_t Denominator) {
+  if (Denominator == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "branch probability denominator must be nonzero");
+  }
+  if (Numerator > Denominator) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "branch probability numerator cannot exceed its denominator");
+  }
+
+  const std::uint64_t ScaledNumerator = static_cast<std::uint64_t>(Numerator) * MaxRawValue;
+  const std::uint64_t Rounded =
+      (ScaledNumerator + static_cast<std::uint64_t>(Denominator / 2)) / Denominator;
+  return BranchProbability(static_cast<std::uint32_t>(Rounded));
+}
+
+MachineInstrFlags::MachineInstrFlags(std::initializer_list<MachineInstrFlag> Flags) noexcept {
+  for (const MachineInstrFlag Flag : Flags)
+    set(Flag);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineMemOperand.cpp b/backend/lib/CodeGen/MachineMemOperand.cpp
new file mode 100644
index 0000000..76aabd1
--- /dev/null
+++ b/backend/lib/CodeGen/MachineMemOperand.cpp
@@ -0,0 +1,244 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineMemOperand.h"
+
+#include <bit>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] bool isValidAtomicLoadOrdering(AtomicOrdering Ordering) noexcept {
+  return Ordering == AtomicOrdering::Unordered || Ordering == AtomicOrdering::Monotonic ||
+         Ordering == AtomicOrdering::Acquire || Ordering == AtomicOrdering::SequentiallyConsistent;
+}
+
+[[nodiscard]] bool isValidAtomicStoreOrdering(AtomicOrdering Ordering) noexcept {
+  return Ordering == AtomicOrdering::Unordered || Ordering == AtomicOrdering::Monotonic ||
+         Ordering == AtomicOrdering::Release || Ordering == AtomicOrdering::SequentiallyConsistent;
+}
+
+[[nodiscard]] bool isValidAtomicReadModifyWriteOrdering(AtomicOrdering Ordering) noexcept {
+  return Ordering == AtomicOrdering::Monotonic || Ordering == AtomicOrdering::Acquire ||
+         Ordering == AtomicOrdering::Release || Ordering == AtomicOrdering::AcquireRelease ||
+         Ordering == AtomicOrdering::SequentiallyConsistent;
+}
+
+[[nodiscard]] bool isValidCompareExchangeFailureOrdering(AtomicOrdering Ordering) noexcept {
+  return Ordering == AtomicOrdering::Monotonic || Ordering == AtomicOrdering::Acquire ||
+         Ordering == AtomicOrdering::SequentiallyConsistent;
+}
+
+[[nodiscard]] bool isFailureOrderingNoStrongerThanSuccess(AtomicOrdering Failure,
+                                                          AtomicOrdering Success) noexcept {
+  switch (Failure) {
+  case AtomicOrdering::Monotonic:
+    return isValidAtomicReadModifyWriteOrdering(Success);
+  case AtomicOrdering::Acquire:
+    return Success == AtomicOrdering::Acquire || Success == AtomicOrdering::AcquireRelease ||
+           Success == AtomicOrdering::SequentiallyConsistent;
+  case AtomicOrdering::SequentiallyConsistent:
+    return Success == AtomicOrdering::SequentiallyConsistent;
+  case AtomicOrdering::NotAtomic:
+  case AtomicOrdering::Unordered:
+  case AtomicOrdering::Release:
+  case AtomicOrdering::AcquireRelease:
+    return false;
+  }
+
+  return false;
+}
+
+[[nodiscard]] Expected<void> verifyAtomicDescription(const MachineMemOperandDesc &Description) {
+  const bool IsLoad = Description.Accesses.has(MemoryAccessFlag::Load);
+  const bool IsStore = Description.Accesses.has(MemoryAccessFlag::Store);
+
+  switch (Description.AtomicKind) {
+  case AtomicOperation::None:
+    if (Description.SuccessOrdering != AtomicOrdering::NotAtomic ||
+        Description.FailureOrdering != AtomicOrdering::NotAtomic) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "non-atomic memory operands cannot carry atomic orderings");
+    }
+    return {};
+  case AtomicOperation::Load:
+    if (!IsLoad || IsStore) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic load memory operands must be load-only");
+    }
+    if (!isValidAtomicLoadOrdering(Description.SuccessOrdering) ||
+        Description.FailureOrdering != AtomicOrdering::NotAtomic) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic load memory operand has an invalid ordering");
+    }
+    return {};
+  case AtomicOperation::Store:
+    if (IsLoad || !IsStore) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic store memory operands must be store-only");
+    }
+    if (!isValidAtomicStoreOrdering(Description.SuccessOrdering) ||
+        Description.FailureOrdering != AtomicOrdering::NotAtomic) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic store memory operand has an invalid ordering");
+    }
+    return {};
+  case AtomicOperation::ReadModifyWrite:
+    if (!IsLoad || !IsStore) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic read-modify-write memory operands must load and store");
+    }
+    if (!isValidAtomicReadModifyWriteOrdering(Description.SuccessOrdering) ||
+        Description.FailureOrdering != AtomicOrdering::NotAtomic) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "atomic read-modify-write memory operand has an invalid ordering");
+    }
+    return {};
+  case AtomicOperation::CompareExchange:
+    if (!IsLoad || !IsStore) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "compare-exchange memory operands must load and store");
+    }
+    if (!isValidAtomicReadModifyWriteOrdering(Description.SuccessOrdering) ||
+        !isValidCompareExchangeFailureOrdering(Description.FailureOrdering) ||
+        !isFailureOrderingNoStrongerThanSuccess(Description.FailureOrdering,
+                                                Description.SuccessOrdering)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "compare-exchange memory operand has incompatible orderings");
+    }
+    return {};
+  }
+
+  return makeUnexpected(ErrorCode::InternalError, "unknown atomic operation");
+}
+
+} // namespace
+
+MemoryAccessFlags::MemoryAccessFlags(std::initializer_list<MemoryAccessFlag> Flags) noexcept {
+  for (const MemoryAccessFlag Flag : Flags)
+    set(Flag);
+}
+
+Expected<Alignment> Alignment::create(std::uint64_t Bytes) {
+  if (!std::has_single_bit(Bytes)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "alignment must be a nonzero power of two");
+  }
+  return Alignment(Bytes);
+}
+
+Expected<MemorySize> MemorySize::fixed(std::uint64_t Bytes) {
+  if (Bytes == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "fixed memory size must be nonzero");
+  return MemorySize(Kind::Fixed, Bytes);
+}
+
+Expected<MemorySize> MemorySize::scalable(std::uint64_t MinimumBytes) {
+  if (MinimumBytes == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "scalable memory size minimum must be nonzero");
+  }
+  return MemorySize(Kind::Scalable, MinimumBytes);
+}
+
+Expected<MemoryOffsetRange> MemoryOffsetRange::create(std::int64_t Lower, std::int64_t Upper) {
+  if (Lower > Upper) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "memory offset range lower bound cannot exceed its upper bound");
+  }
+  return MemoryOffsetRange{Lower, Upper};
+}
+
+MemoryBase MemoryBase::frameIndex(FrameIndex Index) {
+  return MemoryBase(Kind::FrameIndex, Index);
+}
+
+MemoryBase MemoryBase::constantPool(ConstantPoolIndex Index) {
+  return MemoryBase(Kind::ConstantPool, Index);
+}
+
+MemoryBase MemoryBase::jumpTable(JumpTableIndex Index) {
+  return MemoryBase(Kind::JumpTable, Index);
+}
+
+MemoryBase MemoryBase::globalSymbol(std::string Name) {
+  return MemoryBase(Kind::GlobalSymbol, std::move(Name));
+}
+
+MemoryBase MemoryBase::externalSymbol(std::string Name) {
+  return MemoryBase(Kind::ExternalSymbol, std::move(Name));
+}
+
+std::optional<FrameIndex> MemoryBase::frameIndex() const noexcept {
+  if (BaseKind != Kind::FrameIndex)
+    return std::nullopt;
+  return std::get<FrameIndex>(Value);
+}
+
+std::optional<ConstantPoolIndex> MemoryBase::constantPoolIndex() const noexcept {
+  if (BaseKind != Kind::ConstantPool)
+    return std::nullopt;
+  return std::get<ConstantPoolIndex>(Value);
+}
+
+std::optional<JumpTableIndex> MemoryBase::jumpTableIndex() const noexcept {
+  if (BaseKind != Kind::JumpTable)
+    return std::nullopt;
+  return std::get<JumpTableIndex>(Value);
+}
+
+std::optional<std::string_view> MemoryBase::symbolName() const noexcept {
+  if (BaseKind != Kind::GlobalSymbol && BaseKind != Kind::ExternalSymbol)
+    return std::nullopt;
+  return std::get<std::string>(Value);
+}
+
+Expected<MachineMemOperand> MachineMemOperand::create(MachineMemOperandDesc Description) {
+  const bool IsLoad = Description.Accesses.has(MemoryAccessFlag::Load);
+  const bool IsStore = Description.Accesses.has(MemoryAccessFlag::Store);
+  if (!IsLoad && !IsStore) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine memory operand must describe a load or store");
+  }
+  if (Description.AddressSpace > LLT::MaxAddressSpace) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine memory operand address space must fit in 24 bits");
+  }
+  if (Description.Accesses.has(MemoryAccessFlag::Invariant) && (!IsLoad || IsStore)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "invariant memory operands must be load-only");
+  }
+
+  const auto AtomicResult = verifyAtomicDescription(Description);
+  if (!AtomicResult)
+    return std::unexpected(AtomicResult.error());
+
+  const auto SymbolName = Description.Base.symbolName();
+  if (SymbolName && SymbolName->empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "memory base symbol name cannot be empty");
+  }
+
+  return MachineMemOperand(std::move(Description));
+}
+
+std::string_view getAtomicOrderingName(AtomicOrdering Ordering) noexcept {
+  switch (Ordering) {
+  case AtomicOrdering::NotAtomic:
+    return "not-atomic";
+  case AtomicOrdering::Unordered:
+    return "unordered";
+  case AtomicOrdering::Monotonic:
+    return "monotonic";
+  case AtomicOrdering::Acquire:
+    return "acquire";
+  case AtomicOrdering::Release:
+    return "release";
+  case AtomicOrdering::AcquireRelease:
+    return "acquire-release";
+  case AtomicOrdering::SequentiallyConsistent:
+    return "sequentially-consistent";
+  }
+
+  return "unknown";
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegisterMask.cpp b/backend/lib/CodeGen/RegisterMask.cpp
new file mode 100644
index 0000000..027ee26
--- /dev/null
+++ b/backend/lib/CodeGen/RegisterMask.cpp
@@ -0,0 +1,21 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/RegisterMask.h"
+
+namespace rcc {
+
+bool RegisterMask::preserves(PhysicalRegister PhysReg) const noexcept {
+  if (!PhysReg.isValid())
+    return false;
+
+  constexpr std::uint32_t BitsPerWord = 64;
+  const std::uint32_t RegisterNumber = PhysReg.number();
+  const std::size_t WordIndex = RegisterNumber / BitsPerWord;
+  if (WordIndex >= PreservedWords.size())
+    return false;
+
+  const std::uint32_t BitIndex = RegisterNumber % BitsPerWord;
+  return (PreservedWords[WordIndex] & (std::uint64_t{1} << BitIndex)) != 0;
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 032577d..15b0a44 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -1,16 +1,31 @@
 # SPDX-License-Identifier: GPL-3.0-or-later
 
-set(RCCBackendCodeGenTestSources CoreTypesTest.cpp)
+set(
+  RCCBackendCodeGenTestSources
+  CoreTypesTest.cpp
+  MachineValueTypesTest.cpp
+)
+
+add_executable(RCCBackendCodeGenCoreTypesTests CoreTypesTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenCoreTypesTests)
+target_link_libraries(RCCBackendCodeGenCoreTypesTests PRIVATE RCCBackend::CodeGen)
 
-add_executable(RCCBackendCodeGenTests ${RCCBackendCodeGenTestSources})
-rcc_backend_configure_target(RCCBackendCodeGenTests)
-target_link_libraries(RCCBackendCodeGenTests PRIVATE RCCBackend::CodeGen)
+add_test(NAME RCCBackend.CodeGen.CoreTypes COMMAND RCCBackendCodeGenCoreTypesTests)
 
-add_test(NAME RCCBackend.CodeGen.CoreTypes COMMAND RCCBackendCodeGenTests)
+add_executable(RCCBackendCodeGenMachineValueTypesTests MachineValueTypesTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineValueTypesTests)
+target_link_libraries(RCCBackendCodeGenMachineValueTypesTests PRIVATE RCCBackend::CodeGen)
+
+add_test(
+  NAME RCCBackend.CodeGen.MachineValueTypes
+  COMMAND RCCBackendCodeGenMachineValueTypesTests
+)
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
diff --git a/backend/unittests/CodeGen/MachineValueTypesTest.cpp b/backend/unittests/CodeGen/MachineValueTypesTest.cpp
new file mode 100644
index 0000000..40f121b
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineValueTypesTest.cpp
@@ -0,0 +1,187 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/RegisterMask.h"
+
+#include <cstdint>
+#include <iostream>
+#include <string_view>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++FailureCount;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return FailureCount == 0 ? 0 : 1;
+  }
+
+private:
+  int FailureCount = 0;
+};
+
+void testStrongValues(TestContext &Context) {
+  static_assert(!std::is_same_v<rcc::FrameIndex, rcc::ConstantPoolIndex>);
+  static_assert(!std::is_same_v<rcc::ConstantPoolIndex, rcc::JumpTableIndex>);
+  static_assert(!std::is_same_v<rcc::RegisterBankID, rcc::RegisterClassID>);
+
+  const auto Frame = rcc::FrameIndex::fromValue(7);
+  const auto Constant = rcc::ConstantPoolIndex::fromValue(7);
+  Context.expect(Frame.value() == 7 && Constant.value() == 7,
+                 "strong machine indices must preserve their values");
+
+  const auto Opcode = rcc::Opcode::fromValue(19);
+  Context.expect(Opcode.isValid() && Opcode.value() == 19, "Opcode must preserve its opaque value");
+  Context.expect(!rcc::Opcode{}.isValid(), "Opcode zero must remain invalid");
+
+  const auto LowLanes = rcc::LaneMask::fromRaw(0x3);
+  const auto HighLanes = rcc::LaneMask::fromRaw(0x6);
+  Context.expect(LowLanes.intersects(HighLanes), "overlapping lane masks must intersect");
+  Context.expect((LowLanes | HighLanes).rawValue() == 0x7,
+                 "lane mask union must preserve all lanes");
+}
+
+void testBranchProbability(TestContext &Context) {
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  Context.expect(Half.has_value(), "valid branch probability fraction must be accepted");
+  if (Half) {
+    const auto Sum = Half->saturatingAdd(*Half);
+    const auto RawDistance = rcc::BranchProbability::one().rawValue() - Sum.rawValue();
+    Context.expect(RawDistance <= 1,
+                   "two rounded half probabilities must sum to one within one unit");
+    Context.expect(Half->complement().rawValue() == Half->rawValue() ||
+                       Half->complement().rawValue() + 1 == Half->rawValue(),
+                   "half probability complement must preserve fixed-point rounding");
+  }
+
+  Context.expect(!rcc::BranchProbability::fromFraction(1, 0),
+                 "zero branch probability denominator must be rejected");
+  Context.expect(!rcc::BranchProbability::fromFraction(3, 2),
+                 "branch probability greater than one must be rejected");
+}
+
+void testRegisterMask(TestContext &Context) {
+  std::vector<std::uint64_t> Words(2);
+  Words[0] = std::uint64_t{1} << 7;
+  Words[1] = std::uint64_t{1} << 6;
+  const rcc::RegisterMask Mask(std::move(Words));
+
+  auto Reg7 = rcc::PhysicalRegister::create(7);
+  auto Reg70 = rcc::PhysicalRegister::create(70);
+  auto Reg71 = rcc::PhysicalRegister::create(71);
+  Context.expect(Reg7 && Reg70 && Reg71, "physical registers for mask test must be valid");
+  if (Reg7 && Reg70 && Reg71) {
+    Context.expect(Mask.preserves(*Reg7), "preserved register mask bit must be one");
+    Context.expect(Mask.preserves(*Reg70), "preserved register mask must cross word boundaries");
+    Context.expect(Mask.clobbers(*Reg71), "clear register mask bit must mean clobbered");
+  }
+}
+
+rcc::MachineMemOperandDesc makeBasicLoadDescription() {
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = rcc::MemoryAccessFlags{
+      rcc::MemoryAccessFlag::Load,
+      rcc::MemoryAccessFlag::Dereferenceable,
+  };
+  Description.Size = *rcc::MemorySize::fixed(8);
+  Description.Align = *rcc::Alignment::create(8);
+  Description.AddressSpace = 0;
+  Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(3));
+  Description.Offset = 16;
+  Description.AliasSource = rcc::MemoryAliasSourceID::fromValue(11);
+  return Description;
+}
+
+void testMemoryValueTypes(TestContext &Context) {
+  Context.expect(!rcc::Alignment::create(0), "zero alignment must be rejected");
+  Context.expect(!rcc::Alignment::create(3), "non-power-of-two alignment must be rejected");
+  Context.expect(rcc::Alignment::create(16).has_value(), "power-of-two alignment must be accepted");
+  Context.expect(!rcc::MemorySize::fixed(0), "zero fixed memory size must be rejected");
+  Context.expect(!rcc::MemorySize::scalable(0), "zero scalable memory minimum must be rejected");
+
+  auto Range = rcc::MemoryOffsetRange::create(-4, 12);
+  Context.expect(Range && Range->Lower == -4 && Range->Upper == 12,
+                 "valid memory offset range must preserve both bounds");
+  Context.expect(!rcc::MemoryOffsetRange::create(1, -1),
+                 "reversed memory offset range must be rejected");
+
+  const auto Symbol = rcc::MemoryBase::globalSymbol("global");
+  Context.expect(Symbol.kind() == rcc::MemoryBase::Kind::GlobalSymbol,
+                 "global memory base must preserve its kind");
+  Context.expect(Symbol.symbolName() == "global", "global memory base must preserve its symbol");
+}
+
+void testMachineMemOperand(TestContext &Context) {
+  auto Load = rcc::MachineMemOperand::create(makeBasicLoadDescription());
+  Context.expect(Load.has_value(), "complete ordinary load MMO must be accepted");
+  if (Load) {
+    Context.expect(Load->isLoad() && !Load->isStore(),
+                   "ordinary load MMO must preserve access direction");
+    Context.expect(!Load->isAtomic() && !Load->isVolatile(),
+                   "ordinary load MMO must remain unordered and non-volatile");
+  }
+
+  rcc::MachineMemOperandDesc NoAccess;
+  Context.expect(!rcc::MachineMemOperand::create(NoAccess),
+                 "MMO without load or store access must be rejected");
+
+  auto InvariantStore = makeBasicLoadDescription();
+  InvariantStore.Accesses.set(rcc::MemoryAccessFlag::Store);
+  InvariantStore.Accesses.set(rcc::MemoryAccessFlag::Invariant);
+  Context.expect(!rcc::MachineMemOperand::create(InvariantStore),
+                 "invariant store MMO must be rejected");
+
+  auto AtomicLoad = makeBasicLoadDescription();
+  AtomicLoad.AtomicKind = rcc::AtomicOperation::Load;
+  AtomicLoad.SuccessOrdering = rcc::AtomicOrdering::Acquire;
+  Context.expect(rcc::MachineMemOperand::create(AtomicLoad).has_value(),
+                 "acquire atomic load MMO must be accepted");
+
+  AtomicLoad.SuccessOrdering = rcc::AtomicOrdering::Release;
+  Context.expect(!rcc::MachineMemOperand::create(AtomicLoad),
+                 "release ordering on atomic load must be rejected");
+
+  auto CompareExchange = makeBasicLoadDescription();
+  CompareExchange.Accesses.set(rcc::MemoryAccessFlag::Store);
+  CompareExchange.AtomicKind = rcc::AtomicOperation::CompareExchange;
+  CompareExchange.SuccessOrdering = rcc::AtomicOrdering::AcquireRelease;
+  CompareExchange.FailureOrdering = rcc::AtomicOrdering::Acquire;
+  Context.expect(rcc::MachineMemOperand::create(CompareExchange).has_value(),
+                 "compatible compare-exchange orderings must be accepted");
+
+  CompareExchange.SuccessOrdering = rcc::AtomicOrdering::Release;
+  Context.expect(!rcc::MachineMemOperand::create(CompareExchange),
+                 "failure ordering stronger than success must be rejected");
+
+  auto BadAddressSpace = makeBasicLoadDescription();
+  BadAddressSpace.AddressSpace = rcc::LLT::MaxAddressSpace + 1;
+  Context.expect(!rcc::MachineMemOperand::create(BadAddressSpace),
+                 "MMO address space wider than LLT encoding must be rejected");
+
+  auto EmptySymbol = makeBasicLoadDescription();
+  EmptySymbol.Base = rcc::MemoryBase::externalSymbol("");
+  Context.expect(!rcc::MachineMemOperand::create(EmptySymbol),
+                 "empty MMO symbol base must be rejected");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testStrongValues(Context);
+  testBranchProbability(Context);
+  testRegisterMask(Context);
+  testMemoryValueTypes(Context);
+  testMachineMemOperand(Context);
+  return Context.result();
+}