12 files changed, 1273 insertions, 0 deletions

diff --git a/backend/include/rcc/CodeGen/LowLevelType.h b/backend/include/rcc/CodeGen/LowLevelType.h
new file mode 100644
index 0000000..1ff9ab5
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LowLevelType.h
@@ -0,0 +1,220 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LOWLEVELTYPE_H
+#define RCC_CODEGEN_LOWLEVELTYPE_H
+
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <type_traits>
+
+namespace rcc {
+
+enum class FloatSemantics : std::uint8_t {
+  IEEEHalf,
+  BFloat,
+  IEEESingle,
+  IEEEDouble,
+  IEEEQuad,
+  PPCDoubleDouble,
+  PPCDoubleDoubleLegacy,
+  Float8E5M2,
+  Float8E5M2FNUZ,
+  Float8E4M3,
+  Float8E4M3FN,
+  Float8E4M3FNUZ,
+  Float8E4M3B11FNUZ,
+  Float8E3M4,
+  FloatTF32,
+  Float8E8M0FNU,
+  Float6E3M2FN,
+  Float6E2M3FN,
+  Float4E2M1FN,
+  X87DoubleExtended,
+  Count,
+};
+
+[[nodiscard]] bool isKnownFloatSemantics(FloatSemantics Semantics) noexcept;
+[[nodiscard]] std::optional<std::uint32_t>
+getFloatSemanticsBitWidth(FloatSemantics Semantics) noexcept;
+[[nodiscard]] std::string_view getFloatSemanticsName(FloatSemantics Semantics) noexcept;
+[[nodiscard]] std::string_view getFloatSemanticsSpelling(FloatSemantics Semantics) noexcept;
+
+class LLT final {
+public:
+  enum class Kind : std::uint8_t {
+    Invalid,
+    Token,
+    AnyScalar,
+    Integer,
+    Float,
+    Pointer,
+    VectorAny,
+    VectorInteger,
+    VectorFloat,
+    VectorPointer,
+  };
+
+  static constexpr std::uint32_t MaxBitWidth = (std::uint32_t{1} << 16) - 1;
+  static constexpr std::uint32_t MaxElementCount = (std::uint32_t{1} << 16) - 1;
+  static constexpr std::uint32_t MaxAddressSpace = (std::uint32_t{1} << 24) - 1;
+
+  constexpr LLT() noexcept = default;
+
+  [[nodiscard]] static constexpr LLT token() noexcept {
+    return LLT(encode(Kind::Token, 0, 0, 0, false));
+  }
+
+  [[nodiscard]] static Expected<LLT> makeAnyScalar(std::uint64_t BitWidth);
+  [[nodiscard]] static Expected<LLT> makeInteger(std::uint64_t BitWidth);
+  [[nodiscard]] static Expected<LLT> makeFloat(FloatSemantics Semantics);
+  [[nodiscard]] static Expected<LLT> makePointer(std::uint64_t AddressSpace,
+                                                 std::uint64_t BitWidth);
+  [[nodiscard]] static Expected<LLT> makeFixedVector(std::uint64_t ElementCount, LLT ElementType);
+  [[nodiscard]] static Expected<LLT> makeScalableVector(std::uint64_t MinimumElementCount,
+                                                        LLT ElementType);
+
+  [[nodiscard]] constexpr Kind kind() const noexcept {
+    return static_cast<Kind>((RawValue >> KindShift) & KindMask);
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return kind() != Kind::Invalid;
+  }
+
+  [[nodiscard]] constexpr bool isToken() const noexcept {
+    return kind() == Kind::Token;
+  }
+
+  [[nodiscard]] constexpr bool isAnyScalar() const noexcept {
+    return kind() == Kind::AnyScalar;
+  }
+
+  [[nodiscard]] constexpr bool isInteger() const noexcept {
+    return kind() == Kind::Integer;
+  }
+
+  [[nodiscard]] constexpr bool isFloat() const noexcept {
+    return kind() == Kind::Float;
+  }
+
+  [[nodiscard]] constexpr bool isPointer() const noexcept {
+    return kind() == Kind::Pointer;
+  }
+
+  [[nodiscard]] constexpr bool isAnyVector() const noexcept {
+    return kind() == Kind::VectorAny;
+  }
+
+  [[nodiscard]] constexpr bool isIntegerVector() const noexcept {
+    return kind() == Kind::VectorInteger;
+  }
+
+  [[nodiscard]] constexpr bool isFloatVector() const noexcept {
+    return kind() == Kind::VectorFloat;
+  }
+
+  [[nodiscard]] constexpr bool isPointerVector() const noexcept {
+    return kind() == Kind::VectorPointer;
+  }
+
+  [[nodiscard]] constexpr bool isIntegerOrIntegerVector() const noexcept {
+    return isInteger() || isIntegerVector();
+  }
+
+  [[nodiscard]] constexpr bool isFloatOrFloatVector() const noexcept {
+    return isFloat() || isFloatVector();
+  }
+
+  [[nodiscard]] constexpr bool isPointerOrPointerVector() const noexcept {
+    return isPointer() || isPointerVector();
+  }
+
+  [[nodiscard]] constexpr bool isVector() const noexcept {
+    return kind() == Kind::VectorAny || kind() == Kind::VectorInteger ||
+           kind() == Kind::VectorFloat || kind() == Kind::VectorPointer;
+  }
+
+  [[nodiscard]] constexpr bool isScalableVector() const noexcept {
+    return isVector() && ((RawValue >> ScalableShift) & std::uint64_t{1}) != 0;
+  }
+
+  [[nodiscard]] constexpr bool isScalarValue() const noexcept {
+    return isAnyScalar() || isInteger() || isFloat() || isPointer();
+  }
+
+  [[nodiscard]] constexpr std::uint32_t scalarBitWidth() const noexcept {
+    return static_cast<std::uint32_t>((RawValue >> BitWidthShift) & BitWidthMask);
+  }
+
+  [[nodiscard]] constexpr std::uint32_t minimumElementCount() const noexcept {
+    if (!isVector())
+      return 0;
+    return static_cast<std::uint32_t>((RawValue >> ElementCountShift) & ElementCountMask);
+  }
+
+  [[nodiscard]] std::optional<std::uint32_t> addressSpace() const noexcept;
+  [[nodiscard]] std::optional<FloatSemantics> floatSemantics() const noexcept;
+  [[nodiscard]] std::optional<LLT> scalarElementType() const noexcept;
+
+  [[nodiscard]] constexpr std::uint64_t rawValue() const noexcept {
+    return RawValue;
+  }
+
+  [[nodiscard]] std::string toString() const;
+
+  friend constexpr bool operator==(LLT Left, LLT Right) noexcept = default;
+
+private:
+  static constexpr unsigned BitWidthShift = 0;
+  static constexpr unsigned ElementCountShift = 16;
+  static constexpr unsigned AuxiliaryShift = 32;
+  static constexpr unsigned ScalableShift = 56;
+  static constexpr unsigned KindShift = 60;
+
+  static constexpr std::uint64_t BitWidthMask = (std::uint64_t{1} << 16) - 1;
+  static constexpr std::uint64_t ElementCountMask = (std::uint64_t{1} << 16) - 1;
+  static constexpr std::uint64_t AuxiliaryMask = (std::uint64_t{1} << 24) - 1;
+  static constexpr std::uint64_t KindMask = (std::uint64_t{1} << 4) - 1;
+
+  explicit constexpr LLT(std::uint64_t RawValue) noexcept : RawValue(RawValue) {}
+
+  [[nodiscard]] static constexpr std::uint64_t encode(Kind TypeKind, std::uint32_t BitWidth,
+                                                      std::uint32_t ElementCount,
+                                                      std::uint32_t Auxiliary,
+                                                      bool IsScalable) noexcept {
+    return (static_cast<std::uint64_t>(TypeKind) << KindShift) |
+           (static_cast<std::uint64_t>(IsScalable) << ScalableShift) |
+           (static_cast<std::uint64_t>(Auxiliary) << AuxiliaryShift) |
+           (static_cast<std::uint64_t>(ElementCount) << ElementCountShift) |
+           (static_cast<std::uint64_t>(BitWidth) << BitWidthShift);
+  }
+
+  [[nodiscard]] static Expected<LLT> makeScalar(Kind TypeKind, std::uint64_t BitWidth);
+  [[nodiscard]] static Expected<LLT> makeVector(std::uint64_t ElementCount, bool IsScalable,
+                                                LLT ElementType);
+
+  [[nodiscard]] constexpr std::uint32_t auxiliaryValue() const noexcept {
+    return static_cast<std::uint32_t>((RawValue >> AuxiliaryShift) & AuxiliaryMask);
+  }
+
+  std::uint64_t RawValue = 0;
+};
+
+static_assert(sizeof(LLT) == sizeof(std::uint64_t));
+static_assert(std::is_trivially_copyable_v<LLT>);
+
+} // namespace rcc
+
+template <> struct std::hash<rcc::LLT> {
+  [[nodiscard]] std::size_t operator()(rcc::LLT Type) const noexcept {
+    return std::hash<std::uint64_t>{}(Type.rawValue());
+  }
+};
+
+#endif // RCC_CODEGEN_LOWLEVELTYPE_H
diff --git a/backend/include/rcc/CodeGen/MachineFunctionProperties.h b/backend/include/rcc/CodeGen/MachineFunctionProperties.h
new file mode 100644
index 0000000..7d1a5ad
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineFunctionProperties.h
@@ -0,0 +1,131 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEFUNCTIONPROPERTIES_H
+#define RCC_CODEGEN_MACHINEFUNCTIONPROPERTIES_H
+
+#include "rcc/Support/Error.h"
+
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <string>
+#include <string_view>
+#include <type_traits>
+
+namespace rcc {
+
+enum class MachineFunctionProperty : std::uint8_t {
+  IsSSA,
+  NoPHIs,
+  TracksLiveness,
+  Legalized,
+  RegBankSelected,
+  Selected,
+  TiedOpsRewritten,
+  NoVRegs,
+  FrameFinalized,
+  NoFrameIndices,
+  NoExecutablePseudos,
+  Count,
+};
+
+[[nodiscard]] bool isKnownMachineFunctionProperty(MachineFunctionProperty Property) noexcept;
+[[nodiscard]] std::string_view
+getMachineFunctionPropertyName(MachineFunctionProperty Property) noexcept;
+
+class MachineFunctionProperties final {
+public:
+  constexpr MachineFunctionProperties() noexcept = default;
+
+  MachineFunctionProperties(std::initializer_list<MachineFunctionProperty> Properties) noexcept;
+
+  [[nodiscard]] static Expected<MachineFunctionProperties> fromRaw(std::uint64_t RawValue);
+
+  [[nodiscard]] constexpr bool empty() const noexcept {
+    return Mask == 0;
+  }
+
+  [[nodiscard]] constexpr std::size_t count() const noexcept {
+    return static_cast<std::size_t>(std::popcount(Mask));
+  }
+
+  [[nodiscard]] constexpr bool has(MachineFunctionProperty Property) const noexcept {
+    if (!isValidPropertyValue(Property))
+      return false;
+    return (Mask & maskFor(Property)) != 0;
+  }
+
+  [[nodiscard]] constexpr bool containsAll(MachineFunctionProperties Other) const noexcept {
+    return (Mask & Other.Mask) == Other.Mask;
+  }
+
+  [[nodiscard]] constexpr bool intersects(MachineFunctionProperties Other) const noexcept {
+    return (Mask & Other.Mask) != 0;
+  }
+
+  [[nodiscard]] constexpr MachineFunctionProperties
+  missingFrom(MachineFunctionProperties Available) const noexcept {
+    return MachineFunctionProperties(Mask & ~Available.Mask);
+  }
+
+  constexpr void set(MachineFunctionProperty Property) noexcept {
+    if (isValidPropertyValue(Property))
+      Mask |= maskFor(Property);
+  }
+
+  constexpr void clear(MachineFunctionProperty Property) noexcept {
+    if (isValidPropertyValue(Property))
+      Mask &= ~maskFor(Property);
+  }
+
+  [[nodiscard]] Expected<void> applyTransition(MachineFunctionProperties Required,
+                                               MachineFunctionProperties Sets,
+                                               MachineFunctionProperties Clears);
+
+  [[nodiscard]] constexpr std::uint64_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  [[nodiscard]] std::string toString() const;
+
+  friend constexpr bool operator==(MachineFunctionProperties Left,
+                                   MachineFunctionProperties Right) noexcept = default;
+
+  friend constexpr MachineFunctionProperties operator|(MachineFunctionProperties Left,
+                                                       MachineFunctionProperties Right) noexcept {
+    return MachineFunctionProperties(Left.Mask | Right.Mask);
+  }
+
+  friend constexpr MachineFunctionProperties operator&(MachineFunctionProperties Left,
+                                                       MachineFunctionProperties Right) noexcept {
+    return MachineFunctionProperties(Left.Mask & Right.Mask);
+  }
+
+private:
+  static constexpr std::uint64_t PropertyCount =
+      static_cast<std::uint64_t>(MachineFunctionProperty::Count);
+  static_assert(PropertyCount < 64);
+
+  static constexpr std::uint64_t ValidMask = (std::uint64_t{1} << PropertyCount) - 1;
+
+  explicit constexpr MachineFunctionProperties(std::uint64_t Mask) noexcept : Mask(Mask) {}
+
+  [[nodiscard]] static constexpr bool
+  isValidPropertyValue(MachineFunctionProperty Property) noexcept {
+    return static_cast<std::uint64_t>(Property) < PropertyCount;
+  }
+
+  [[nodiscard]] static constexpr std::uint64_t maskFor(MachineFunctionProperty Property) noexcept {
+    return std::uint64_t{1} << static_cast<std::uint64_t>(Property);
+  }
+
+  std::uint64_t Mask = 0;
+};
+
+static_assert(sizeof(MachineFunctionProperties) == sizeof(std::uint64_t));
+static_assert(std::is_trivially_copyable_v<MachineFunctionProperties>);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEFUNCTIONPROPERTIES_H
diff --git a/backend/include/rcc/CodeGen/Register.h b/backend/include/rcc/CodeGen/Register.h
new file mode 100644
index 0000000..7d98a21
--- /dev/null
+++ b/backend/include/rcc/CodeGen/Register.h
@@ -0,0 +1,103 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGISTER_H
+#define RCC_CODEGEN_REGISTER_H
+
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <optional>
+#include <string>
+#include <type_traits>
+
+namespace rcc {
+
+class PhysicalRegister final {
+public:
+  constexpr PhysicalRegister() noexcept = default;
+
+  [[nodiscard]] static Expected<PhysicalRegister> create(std::uint64_t Number);
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Number != 0;
+  }
+
+  [[nodiscard]] constexpr std::uint32_t number() const noexcept {
+    return Number;
+  }
+
+  friend constexpr bool operator==(PhysicalRegister Left,
+                                   PhysicalRegister Right) noexcept = default;
+
+private:
+  explicit constexpr PhysicalRegister(std::uint32_t Number) noexcept : Number(Number) {}
+
+  std::uint32_t Number = 0;
+
+  friend class Register;
+};
+
+class Register final {
+public:
+  constexpr Register() noexcept = default;
+  explicit constexpr Register(std::uint32_t OpaqueValue) noexcept : OpaqueValue(OpaqueValue) {}
+
+  [[nodiscard]] static Expected<Register> makePhysical(std::uint64_t Number);
+  [[nodiscard]] static Expected<Register> makeVirtual(std::uint64_t Index);
+
+  [[nodiscard]] static constexpr Register fromPhysical(PhysicalRegister PhysReg) noexcept {
+    return Register(PhysReg.Number);
+  }
+
+  [[nodiscard]] constexpr bool isNoRegister() const noexcept {
+    return OpaqueValue == 0;
+  }
+
+  [[nodiscard]] constexpr bool isPhysical() const noexcept {
+    return OpaqueValue != 0 && (OpaqueValue & VirtualBit) == 0;
+  }
+
+  [[nodiscard]] constexpr bool isVirtual() const noexcept {
+    return (OpaqueValue & VirtualBit) != 0;
+  }
+
+  [[nodiscard]] std::optional<PhysicalRegister> physicalRegister() const noexcept;
+  [[nodiscard]] std::optional<std::uint32_t> virtualIndex() const noexcept;
+
+  [[nodiscard]] constexpr std::uint32_t opaqueValue() const noexcept {
+    return OpaqueValue;
+  }
+
+  [[nodiscard]] std::string toString() const;
+
+  friend constexpr bool operator==(Register Left, Register Right) noexcept = default;
+
+private:
+  static constexpr std::uint32_t VirtualBit = std::uint32_t{1} << 31;
+  static constexpr std::uint32_t IndexMask = VirtualBit - 1;
+
+  std::uint32_t OpaqueValue = 0;
+};
+
+static_assert(sizeof(PhysicalRegister) == sizeof(std::uint32_t));
+static_assert(sizeof(Register) == sizeof(std::uint32_t));
+static_assert(std::is_trivially_copyable_v<PhysicalRegister>);
+static_assert(std::is_trivially_copyable_v<Register>);
+
+} // namespace rcc
+
+template <> struct std::hash<rcc::PhysicalRegister> {
+  [[nodiscard]] std::size_t operator()(rcc::PhysicalRegister PhysReg) const noexcept {
+    return std::hash<std::uint32_t>{}(PhysReg.number());
+  }
+};
+
+template <> struct std::hash<rcc::Register> {
+  [[nodiscard]] std::size_t operator()(rcc::Register Reg) const noexcept {
+    return std::hash<std::uint32_t>{}(Reg.opaqueValue());
+  }
+};
+
+#endif // RCC_CODEGEN_REGISTER_H
diff --git a/backend/include/rcc/CodeGen/StableID.h b/backend/include/rcc/CodeGen/StableID.h
new file mode 100644
index 0000000..89a4266
--- /dev/null
+++ b/backend/include/rcc/CodeGen/StableID.h
@@ -0,0 +1,92 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_STABLEID_H
+#define RCC_CODEGEN_STABLEID_H
+
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <limits>
+#include <type_traits>
+
+namespace rcc {
+
+template <typename TagT> class StableID final {
+public:
+  constexpr StableID() noexcept = default;
+
+  [[nodiscard]] static constexpr StableID fromValue(std::uint64_t Value) noexcept {
+    return StableID(Value);
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != 0;
+  }
+
+  [[nodiscard]] constexpr std::uint64_t value() const noexcept {
+    return Value;
+  }
+
+  friend constexpr bool operator==(StableID Left, StableID Right) noexcept = default;
+
+private:
+  explicit constexpr StableID(std::uint64_t Value) noexcept : Value(Value) {}
+
+  std::uint64_t Value = 0;
+};
+
+namespace detail {
+
+struct MachineFunctionStableIDTag;
+struct MachineBlockStableIDTag;
+struct MachineInstrStableIDTag;
+
+} // namespace detail
+
+using MachineFunctionStableID = StableID<detail::MachineFunctionStableIDTag>;
+using MachineBlockStableID = StableID<detail::MachineBlockStableIDTag>;
+using MachineInstrStableID = StableID<detail::MachineInstrStableIDTag>;
+
+template <typename StableIDT> class StableIDGenerator final {
+public:
+  StableIDGenerator() = default;
+  StableIDGenerator(const StableIDGenerator &) = delete;
+  StableIDGenerator &operator=(const StableIDGenerator &) = delete;
+  StableIDGenerator(StableIDGenerator &&) noexcept = default;
+  StableIDGenerator &operator=(StableIDGenerator &&) noexcept = default;
+
+  [[nodiscard]] Expected<StableIDT> allocate() {
+    if (NextValue == 0) {
+      return makeUnexpected(ErrorCode::InternalError, "stable ID space is exhausted");
+    }
+
+    const StableIDT Result = StableIDT::fromValue(NextValue);
+    if (NextValue == std::numeric_limits<std::uint64_t>::max())
+      NextValue = 0;
+    else
+      ++NextValue;
+    return Result;
+  }
+
+private:
+  std::uint64_t NextValue = 1;
+};
+
+static_assert(sizeof(MachineFunctionStableID) == sizeof(std::uint64_t));
+static_assert(sizeof(MachineBlockStableID) == sizeof(std::uint64_t));
+static_assert(sizeof(MachineInstrStableID) == sizeof(std::uint64_t));
+static_assert(std::is_trivially_copyable_v<MachineFunctionStableID>);
+static_assert(std::is_trivially_copyable_v<MachineBlockStableID>);
+static_assert(std::is_trivially_copyable_v<MachineInstrStableID>);
+
+} // namespace rcc
+
+template <typename TagT> struct std::hash<rcc::StableID<TagT>> {
+  [[nodiscard]] std::size_t operator()(rcc::StableID<TagT> ID) const noexcept {
+    return std::hash<std::uint64_t>{}(ID.value());
+  }
+};
+
+#endif // RCC_CODEGEN_STABLEID_H
diff --git a/backend/lib/CMakeLists.txt b/backend/lib/CMakeLists.txt
index 13f7c7b..dfaff97 100644
--- a/backend/lib/CMakeLists.txt
+++ b/backend/lib/CMakeLists.txt
@@ -1,3 +1,4 @@
 # SPDX-License-Identifier: GPL-3.0-or-later
 
 add_subdirectory(Support)
+add_subdirectory(CodeGen)
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
new file mode 100644
index 0000000..f5b5b23
--- /dev/null
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -0,0 +1,55 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(
+  RCCBackendCodeGenSources
+  LowLevelType.cpp
+  MachineFunctionProperties.cpp
+  Register.cpp
+)
+set(
+  RCCBackendCodeGenHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.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/StableID.h"
+)
+
+add_library(RCCBackendCodeGen ${RCCBackendCodeGenSources})
+add_library(RCCBackend::CodeGen ALIAS RCCBackendCodeGen)
+
+rcc_backend_configure_target(RCCBackendCodeGen)
+
+target_include_directories(
+  RCCBackendCodeGen
+  PUBLIC
+    "$<BUILD_INTERFACE:${RCC_BACKEND_SOURCE_DIR}/include>"
+    "$<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}>"
+)
+target_link_libraries(RCCBackendCodeGen PUBLIC RCCBackend::Support)
+
+set_target_properties(
+  RCCBackendCodeGen
+  PROPERTIES
+    EXPORT_NAME CodeGen
+    OUTPUT_NAME RCCBackendCodeGen
+)
+
+install(
+  TARGETS RCCBackendCodeGen
+  EXPORT RCCBackendTargets
+  ARCHIVE DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+  LIBRARY DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+  RUNTIME DESTINATION "${CMAKE_INSTALL_BINDIR}"
+)
+
+rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
+  ${RCCBackendCodeGenHeaders}
+)
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
+)
diff --git a/backend/lib/CodeGen/LowLevelType.cpp b/backend/lib/CodeGen/LowLevelType.cpp
new file mode 100644
index 0000000..a276e02
--- /dev/null
+++ b/backend/lib/CodeGen/LowLevelType.cpp
@@ -0,0 +1,249 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LowLevelType.h"
+
+#include <array>
+#include <string>
+
+namespace rcc {
+namespace {
+
+struct FloatSemanticsInfo final {
+  std::uint32_t BitWidth;
+  std::string_view Name;
+  std::string_view Spelling;
+};
+
+constexpr std::array FloatSemanticsTable{
+    FloatSemanticsInfo{16, "IEEE half", "f16"},
+    FloatSemanticsInfo{16, "bfloat", "bf16"},
+    FloatSemanticsInfo{32, "IEEE single", "f32"},
+    FloatSemanticsInfo{64, "IEEE double", "f64"},
+    FloatSemanticsInfo{128, "IEEE quad", "f128"},
+    FloatSemanticsInfo{128, "PPC double-double", "ppcf128"},
+    FloatSemanticsInfo{128, "legacy PPC double-double", "ppcf128-legacy"},
+    FloatSemanticsInfo{8, "float8 E5M2", "f8e5m2"},
+    FloatSemanticsInfo{8, "float8 E5M2 FNUZ", "f8e5m2fnuz"},
+    FloatSemanticsInfo{8, "float8 E4M3", "f8e4m3"},
+    FloatSemanticsInfo{8, "float8 E4M3 FN", "f8e4m3fn"},
+    FloatSemanticsInfo{8, "float8 E4M3 FNUZ", "f8e4m3fnuz"},
+    FloatSemanticsInfo{8, "float8 E4M3 B11 FNUZ", "f8e4m3b11fnuz"},
+    FloatSemanticsInfo{8, "float8 E3M4", "f8e3m4"},
+    FloatSemanticsInfo{19, "TensorFloat-32", "tf32"},
+    FloatSemanticsInfo{8, "float8 E8M0 FNU", "f8e8m0fnu"},
+    FloatSemanticsInfo{6, "float6 E3M2 FN", "f6e3m2fn"},
+    FloatSemanticsInfo{6, "float6 E2M3 FN", "f6e2m3fn"},
+    FloatSemanticsInfo{4, "float4 E2M1 FN", "f4e2m1fn"},
+    FloatSemanticsInfo{80, "x87 double-extended", "x86fp80"},
+};
+
+static_assert(FloatSemanticsTable.size() == static_cast<std::size_t>(FloatSemantics::Count));
+
+[[nodiscard]] const FloatSemanticsInfo *getFloatSemanticsInfo(FloatSemantics Semantics) noexcept {
+  const auto Index = static_cast<std::size_t>(Semantics);
+  if (Index >= FloatSemanticsTable.size())
+    return nullptr;
+  return &FloatSemanticsTable[Index];
+}
+
+[[nodiscard]] LLT::Kind getVectorKind(LLT ElementType) noexcept {
+  switch (ElementType.kind()) {
+  case LLT::Kind::AnyScalar:
+    return LLT::Kind::VectorAny;
+  case LLT::Kind::Integer:
+    return LLT::Kind::VectorInteger;
+  case LLT::Kind::Float:
+    return LLT::Kind::VectorFloat;
+  case LLT::Kind::Pointer:
+    return LLT::Kind::VectorPointer;
+  case LLT::Kind::Invalid:
+  case LLT::Kind::Token:
+  case LLT::Kind::VectorAny:
+  case LLT::Kind::VectorInteger:
+  case LLT::Kind::VectorFloat:
+  case LLT::Kind::VectorPointer:
+    return LLT::Kind::Invalid;
+  }
+
+  return LLT::Kind::Invalid;
+}
+
+} // namespace
+
+bool isKnownFloatSemantics(FloatSemantics Semantics) noexcept {
+  return getFloatSemanticsInfo(Semantics) != nullptr;
+}
+
+std::optional<std::uint32_t> getFloatSemanticsBitWidth(FloatSemantics Semantics) noexcept {
+  const auto *Info = getFloatSemanticsInfo(Semantics);
+  if (Info == nullptr)
+    return std::nullopt;
+  return Info->BitWidth;
+}
+
+std::string_view getFloatSemanticsName(FloatSemantics Semantics) noexcept {
+  const auto *Info = getFloatSemanticsInfo(Semantics);
+  if (Info == nullptr)
+    return "unknown";
+  return Info->Name;
+}
+
+std::string_view getFloatSemanticsSpelling(FloatSemantics Semantics) noexcept {
+  const auto *Info = getFloatSemanticsInfo(Semantics);
+  if (Info == nullptr)
+    return "invalid-float";
+  return Info->Spelling;
+}
+
+Expected<LLT> LLT::makeScalar(Kind TypeKind, std::uint64_t BitWidth) {
+  if (BitWidth == 0 || BitWidth > MaxBitWidth) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "LLT bit width must be in the range [1, 65535]");
+  }
+
+  return LLT(encode(TypeKind, static_cast<std::uint32_t>(BitWidth), 0, 0, false));
+}
+
+Expected<LLT> LLT::makeAnyScalar(std::uint64_t BitWidth) {
+  return makeScalar(Kind::AnyScalar, BitWidth);
+}
+
+Expected<LLT> LLT::makeInteger(std::uint64_t BitWidth) {
+  return makeScalar(Kind::Integer, BitWidth);
+}
+
+Expected<LLT> LLT::makeFloat(FloatSemantics Semantics) {
+  const auto BitWidth = getFloatSemanticsBitWidth(Semantics);
+  if (!BitWidth) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "unknown floating-point semantics");
+  }
+
+  return LLT(encode(Kind::Float, *BitWidth, 0, static_cast<std::uint32_t>(Semantics), false));
+}
+
+Expected<LLT> LLT::makePointer(std::uint64_t AddressSpace, std::uint64_t BitWidth) {
+  if (BitWidth == 0 || BitWidth > MaxBitWidth) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "LLT pointer bit width must be in the range [1, 65535]");
+  }
+  if (AddressSpace > MaxAddressSpace) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "LLT address space must fit in 24 bits");
+  }
+
+  return LLT(encode(Kind::Pointer, static_cast<std::uint32_t>(BitWidth), 0,
+                    static_cast<std::uint32_t>(AddressSpace), false));
+}
+
+Expected<LLT> LLT::makeFixedVector(std::uint64_t ElementCount, LLT ElementType) {
+  return makeVector(ElementCount, false, ElementType);
+}
+
+Expected<LLT> LLT::makeScalableVector(std::uint64_t MinimumElementCount, LLT ElementType) {
+  return makeVector(MinimumElementCount, true, ElementType);
+}
+
+Expected<LLT> LLT::makeVector(std::uint64_t ElementCount, bool IsScalable, LLT ElementType) {
+  if (ElementCount == 0 || ElementCount > MaxElementCount) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "LLT vector element count must be in the range [1, 65535]");
+  }
+  if (!IsScalable && ElementCount == 1) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "a fixed LLT vector must contain at least two elements");
+  }
+
+  const Kind VectorKind = getVectorKind(ElementType);
+  if (VectorKind == Kind::Invalid) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "LLT vector elements must be non-vector value types");
+  }
+
+  std::uint32_t Auxiliary = 0;
+  if (ElementType.isPointer())
+    Auxiliary = *ElementType.addressSpace();
+  else if (ElementType.isFloat())
+    Auxiliary = static_cast<std::uint32_t>(*ElementType.floatSemantics());
+
+  return LLT(encode(VectorKind, ElementType.scalarBitWidth(),
+                    static_cast<std::uint32_t>(ElementCount), Auxiliary, IsScalable));
+}
+
+std::optional<std::uint32_t> LLT::addressSpace() const noexcept {
+  if (!isPointerOrPointerVector())
+    return std::nullopt;
+  return auxiliaryValue();
+}
+
+std::optional<FloatSemantics> LLT::floatSemantics() const noexcept {
+  if (!isFloatOrFloatVector())
+    return std::nullopt;
+  return static_cast<FloatSemantics>(auxiliaryValue());
+}
+
+std::optional<LLT> LLT::scalarElementType() const noexcept {
+  switch (kind()) {
+  case Kind::VectorAny:
+    return LLT(encode(Kind::AnyScalar, scalarBitWidth(), 0, 0, false));
+  case Kind::VectorInteger:
+    return LLT(encode(Kind::Integer, scalarBitWidth(), 0, 0, false));
+  case Kind::VectorFloat:
+    return LLT(encode(Kind::Float, scalarBitWidth(), 0, auxiliaryValue(), false));
+  case Kind::VectorPointer:
+    return LLT(encode(Kind::Pointer, scalarBitWidth(), 0, auxiliaryValue(), false));
+  case Kind::Invalid:
+  case Kind::Token:
+  case Kind::AnyScalar:
+  case Kind::Integer:
+  case Kind::Float:
+  case Kind::Pointer:
+    return std::nullopt;
+  }
+
+  return std::nullopt;
+}
+
+std::string LLT::toString() const {
+  if (!isValid())
+    return "LLT_invalid";
+  if (isToken())
+    return "s0";
+
+  std::string ScalarSpelling;
+  switch (kind()) {
+  case Kind::AnyScalar:
+  case Kind::VectorAny:
+    ScalarSpelling = "s" + std::to_string(scalarBitWidth());
+    break;
+  case Kind::Integer:
+  case Kind::VectorInteger:
+    ScalarSpelling = "i" + std::to_string(scalarBitWidth());
+    break;
+  case Kind::Float:
+  case Kind::VectorFloat:
+    ScalarSpelling =
+        std::string(getFloatSemanticsSpelling(static_cast<FloatSemantics>(auxiliaryValue())));
+    break;
+  case Kind::Pointer:
+  case Kind::VectorPointer:
+    ScalarSpelling =
+        "p" + std::to_string(auxiliaryValue()) + ":" + std::to_string(scalarBitWidth());
+    break;
+  case Kind::Invalid:
+  case Kind::Token:
+    break;
+  }
+
+  if (!isVector())
+    return ScalarSpelling;
+
+  std::string Result = "<";
+  if (isScalableVector())
+    Result += "vscale x ";
+  Result += std::to_string(minimumElementCount());
+  Result += " x ";
+  Result += ScalarSpelling;
+  Result += ">";
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineFunctionProperties.cpp b/backend/lib/CodeGen/MachineFunctionProperties.cpp
new file mode 100644
index 0000000..55a4ca3
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFunctionProperties.cpp
@@ -0,0 +1,88 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+
+#include <array>
+#include <string>
+
+namespace rcc {
+namespace {
+
+constexpr std::array PropertyNames{
+    std::string_view{"IsSSA"},
+    std::string_view{"NoPHIs"},
+    std::string_view{"TracksLiveness"},
+    std::string_view{"Legalized"},
+    std::string_view{"RegBankSelected"},
+    std::string_view{"Selected"},
+    std::string_view{"TiedOpsRewritten"},
+    std::string_view{"NoVRegs"},
+    std::string_view{"FrameFinalized"},
+    std::string_view{"NoFrameIndices"},
+    std::string_view{"NoExecutablePseudos"},
+};
+
+static_assert(PropertyNames.size() == static_cast<std::size_t>(MachineFunctionProperty::Count));
+
+} // namespace
+
+bool isKnownMachineFunctionProperty(MachineFunctionProperty Property) noexcept {
+  return static_cast<std::size_t>(Property) < PropertyNames.size();
+}
+
+std::string_view getMachineFunctionPropertyName(MachineFunctionProperty Property) noexcept {
+  const auto Index = static_cast<std::size_t>(Property);
+  if (Index >= PropertyNames.size())
+    return "Unknown";
+  return PropertyNames[Index];
+}
+
+MachineFunctionProperties::MachineFunctionProperties(
+    std::initializer_list<MachineFunctionProperty> Properties) noexcept {
+  for (const MachineFunctionProperty Property : Properties)
+    set(Property);
+}
+
+Expected<MachineFunctionProperties> MachineFunctionProperties::fromRaw(std::uint64_t RawValue) {
+  if ((RawValue & ~ValidMask) != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine function property mask contains unknown bits");
+  }
+  return MachineFunctionProperties(RawValue);
+}
+
+Expected<void> MachineFunctionProperties::applyTransition(MachineFunctionProperties Required,
+                                                          MachineFunctionProperties Sets,
+                                                          MachineFunctionProperties Clears) {
+  if (Sets.intersects(Clears)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "a machine function property transition cannot set and clear the "
+                          "same property");
+  }
+
+  const MachineFunctionProperties Missing = Required.missingFrom(*this);
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "missing required machine function properties: " + Missing.toString());
+  }
+
+  Mask = (Mask | Sets.Mask) & ~Clears.Mask;
+  return {};
+}
+
+std::string MachineFunctionProperties::toString() const {
+  if (empty())
+    return "none";
+
+  std::string Result;
+  for (std::size_t Index = 0; Index < PropertyNames.size(); ++Index) {
+    if ((Mask & (std::uint64_t{1} << Index)) == 0)
+      continue;
+    if (!Result.empty())
+      Result += ", ";
+    Result += PropertyNames[Index];
+  }
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/Register.cpp b/backend/lib/CodeGen/Register.cpp
new file mode 100644
index 0000000..0af26c7
--- /dev/null
+++ b/backend/lib/CodeGen/Register.cpp
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/Register.h"
+
+#include <string>
+
+namespace rcc {
+namespace {
+
+constexpr std::uint64_t MaximumRegisterIndex = (std::uint64_t{1} << 31) - 1;
+
+} // namespace
+
+Expected<PhysicalRegister> PhysicalRegister::create(std::uint64_t Number) {
+  if (Number == 0 || Number > MaximumRegisterIndex) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "physical register number must be in the range [1, 2147483647]");
+  }
+  return PhysicalRegister(static_cast<std::uint32_t>(Number));
+}
+
+Expected<Register> Register::makePhysical(std::uint64_t Number) {
+  auto PhysReg = PhysicalRegister::create(Number);
+  if (!PhysReg)
+    return std::unexpected(PhysReg.error());
+  return fromPhysical(*PhysReg);
+}
+
+Expected<Register> Register::makeVirtual(std::uint64_t Index) {
+  if (Index > MaximumRegisterIndex) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register index must fit in 31 bits");
+  }
+  return Register(VirtualBit | static_cast<std::uint32_t>(Index));
+}
+
+std::optional<PhysicalRegister> Register::physicalRegister() const noexcept {
+  if (!isPhysical())
+    return std::nullopt;
+  return PhysicalRegister(OpaqueValue);
+}
+
+std::optional<std::uint32_t> Register::virtualIndex() const noexcept {
+  if (!isVirtual())
+    return std::nullopt;
+  return OpaqueValue & IndexMask;
+}
+
+std::string Register::toString() const {
+  if (isNoRegister())
+    return "noreg";
+  if (isVirtual())
+    return "%" + std::to_string(OpaqueValue & IndexMask);
+  return "$physreg" + std::to_string(OpaqueValue);
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CMakeLists.txt b/backend/unittests/CMakeLists.txt
index 13f7c7b..dfaff97 100644
--- a/backend/unittests/CMakeLists.txt
+++ b/backend/unittests/CMakeLists.txt
@@ -1,3 +1,4 @@
 # SPDX-License-Identifier: GPL-3.0-or-later
 
 add_subdirectory(Support)
+add_subdirectory(CodeGen)
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
new file mode 100644
index 0000000..032577d
--- /dev/null
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -0,0 +1,16 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(RCCBackendCodeGenTestSources CoreTypesTest.cpp)
+
+add_executable(RCCBackendCodeGenTests ${RCCBackendCodeGenTestSources})
+rcc_backend_configure_target(RCCBackendCodeGenTests)
+target_link_libraries(RCCBackendCodeGenTests PRIVATE RCCBackend::CodeGen)
+
+add_test(NAME RCCBackend.CodeGen.CoreTypes COMMAND RCCBackendCodeGenTests)
+
+rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+)
+rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+)
diff --git a/backend/unittests/CodeGen/CoreTypesTest.cpp b/backend/unittests/CodeGen/CoreTypesTest.cpp
new file mode 100644
index 0000000..c2a7b45
--- /dev/null
+++ b/backend/unittests/CodeGen/CoreTypesTest.cpp
@@ -0,0 +1,261 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/StableID.h"
+
+#include <array>
+#include <cstdint>
+#include <iostream>
+#include <string_view>
+#include <type_traits>
+#include <unordered_set>
+
+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 testLowLevelTypes(TestContext &Context) {
+  const rcc::LLT Invalid;
+  Context.expect(!Invalid.isValid(), "default LLT must be invalid");
+  Context.expect(Invalid.toString() == "LLT_invalid", "invalid LLT spelling must be stable");
+
+  const rcc::LLT Token = rcc::LLT::token();
+  Context.expect(Token.isToken(), "token LLT must preserve its kind");
+  Context.expect(Token.scalarBitWidth() == 0, "token LLT must have no bit width");
+  Context.expect(Token.toString() == "s0", "token LLT must use the MIR token spelling");
+
+  auto Any = rcc::LLT::makeAnyScalar(3);
+  auto Integer = rcc::LLT::makeInteger(3);
+  Context.expect(Any && Integer, "arbitrary positive scalar widths must be accepted");
+  if (Any && Integer) {
+    Context.expect(Any->isAnyScalar(), "bag-of-bits LLT must preserve its kind");
+    Context.expect(Integer->isInteger(), "integer LLT must preserve its kind");
+    Context.expect(*Any != *Integer, "bag-of-bits and integer LLTs must remain distinct");
+    Context.expect(Any->toString() == "s3", "bag-of-bits LLT spelling must include its width");
+    Context.expect(Integer->toString() == "i3", "integer LLT spelling must include its width");
+  }
+
+  Context.expect(!rcc::LLT::makeInteger(0), "zero-width integer LLT must be rejected");
+  Context.expect(!rcc::LLT::makeInteger(std::uint64_t{1} << 16),
+                 "integer LLT wider than the encoding must be rejected");
+
+  constexpr std::array FloatCases{
+      std::pair{rcc::FloatSemantics::IEEEHalf, std::uint32_t{16}},
+      std::pair{rcc::FloatSemantics::BFloat, std::uint32_t{16}},
+      std::pair{rcc::FloatSemantics::IEEESingle, std::uint32_t{32}},
+      std::pair{rcc::FloatSemantics::IEEEDouble, std::uint32_t{64}},
+      std::pair{rcc::FloatSemantics::IEEEQuad, std::uint32_t{128}},
+      std::pair{rcc::FloatSemantics::PPCDoubleDouble, std::uint32_t{128}},
+      std::pair{rcc::FloatSemantics::PPCDoubleDoubleLegacy, std::uint32_t{128}},
+      std::pair{rcc::FloatSemantics::Float8E5M2, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E5M2FNUZ, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E4M3, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E4M3FN, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E4M3FNUZ, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E4M3B11FNUZ, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float8E3M4, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::FloatTF32, std::uint32_t{19}},
+      std::pair{rcc::FloatSemantics::Float8E8M0FNU, std::uint32_t{8}},
+      std::pair{rcc::FloatSemantics::Float6E3M2FN, std::uint32_t{6}},
+      std::pair{rcc::FloatSemantics::Float6E2M3FN, std::uint32_t{6}},
+      std::pair{rcc::FloatSemantics::Float4E2M1FN, std::uint32_t{4}},
+      std::pair{rcc::FloatSemantics::X87DoubleExtended, std::uint32_t{80}},
+  };
+
+  std::unordered_set<rcc::LLT> FloatTypes;
+  for (const auto &[Semantics, BitWidth] : FloatCases) {
+    auto Type = rcc::LLT::makeFloat(Semantics);
+    Context.expect(Type.has_value(), "known floating-point semantics must be accepted");
+    if (!Type)
+      continue;
+    Context.expect(Type->scalarBitWidth() == BitWidth,
+                   "float LLT must preserve its semantics bit width");
+    Context.expect(Type->floatSemantics() == Semantics,
+                   "float LLT must preserve exact floating-point semantics");
+    FloatTypes.insert(*Type);
+  }
+  Context.expect(FloatTypes.size() == FloatCases.size(),
+                 "distinct floating-point semantics must produce distinct LLTs");
+  Context.expect(!rcc::LLT::makeFloat(rcc::FloatSemantics::Count),
+                 "unknown floating-point semantics must be rejected");
+
+  auto Pointer = rcc::LLT::makePointer(rcc::LLT::MaxAddressSpace, 64);
+  Context.expect(Pointer.has_value(), "maximum encodable pointer address space must be accepted");
+  if (Pointer) {
+    Context.expect(Pointer->isPointer(), "pointer LLT must preserve its kind");
+    Context.expect(Pointer->addressSpace() == rcc::LLT::MaxAddressSpace,
+                   "pointer LLT must preserve its address space");
+    Context.expect(Pointer->toString() == "p16777215:64",
+                   "pointer LLT spelling must preserve address space and width");
+  }
+  Context.expect(!rcc::LLT::makePointer(std::uint64_t{1} << 24, 64),
+                 "pointer address spaces wider than the encoding must be rejected");
+
+  auto I33 = rcc::LLT::makeInteger(33);
+  if (!I33) {
+    Context.expect(false, "i33 construction must succeed before vector tests");
+    return;
+  }
+
+  auto FixedVector = rcc::LLT::makeFixedVector(4, *I33);
+  Context.expect(FixedVector.has_value(), "fixed integer vector LLT must be accepted");
+  if (FixedVector) {
+    Context.expect(FixedVector->isVector(), "fixed vector LLT must preserve vector kind");
+    Context.expect(!FixedVector->isScalableVector(),
+                   "fixed vector LLT must not be marked scalable");
+    Context.expect(FixedVector->minimumElementCount() == 4,
+                   "fixed vector LLT must preserve element count");
+    Context.expect(FixedVector->scalarElementType() == I33,
+                   "fixed vector LLT must preserve its scalar element type");
+    Context.expect(FixedVector->toString() == "<4 x i33>",
+                   "fixed vector LLT spelling must be stable");
+  }
+
+  auto BFloat = rcc::LLT::makeFloat(rcc::FloatSemantics::BFloat);
+  if (!BFloat) {
+    Context.expect(false, "bfloat construction must succeed before vector tests");
+    return;
+  }
+  auto ScalableVector = rcc::LLT::makeScalableVector(1, *BFloat);
+  Context.expect(ScalableVector.has_value(), "scalable vector with one minimum lane must work");
+  if (ScalableVector) {
+    Context.expect(ScalableVector->isScalableVector(),
+                   "scalable vector LLT must preserve scalability");
+    Context.expect(ScalableVector->isFloatVector() && !ScalableVector->isFloat(),
+                   "float vectors must not be classified as scalar floats");
+    Context.expect(ScalableVector->floatSemantics() == rcc::FloatSemantics::BFloat,
+                   "float vectors must preserve exact floating-point semantics");
+    Context.expect(ScalableVector->toString() == "<vscale x 1 x bf16>",
+                   "scalable float vector spelling must preserve exact semantics");
+  }
+
+  Context.expect(!rcc::LLT::makeFixedVector(1, *I33), "single-lane fixed vectors must be rejected");
+  Context.expect(!rcc::LLT::makeScalableVector(0, *I33),
+                 "zero-lane scalable vectors must be rejected");
+  Context.expect(!rcc::LLT::makeFixedVector(4, Token), "token vector elements must be rejected");
+  if (FixedVector) {
+    Context.expect(!rcc::LLT::makeFixedVector(4, *FixedVector),
+                   "nested LLT vectors must be rejected");
+  }
+}
+
+void testRegisters(TestContext &Context) {
+  const rcc::Register NoRegister{0};
+  Context.expect(NoRegister.isNoRegister(), "Register{0} must represent NoRegister");
+  Context.expect(NoRegister.toString() == "noreg", "NoRegister spelling must be stable");
+
+  auto PhysReg = rcc::PhysicalRegister::create(7);
+  Context.expect(PhysReg.has_value(), "positive physical register numbers must be accepted");
+  if (PhysReg) {
+    const rcc::Register Reg = rcc::Register::fromPhysical(*PhysReg);
+    Context.expect(Reg.isPhysical(), "physical Register must preserve its category");
+    Context.expect(Reg.physicalRegister() == PhysReg,
+                   "physical Register must round-trip through PhysicalRegister");
+    Context.expect(Reg.toString() == "$physreg7",
+                   "target-independent physical register spelling must be stable");
+  }
+
+  Context.expect(!rcc::PhysicalRegister::create(0), "physical register zero must remain reserved");
+  Context.expect(!rcc::Register::makePhysical(std::uint64_t{1} << 31),
+                 "out-of-range physical registers must be rejected");
+
+  auto FirstVirtual = rcc::Register::makeVirtual(0);
+  auto LastVirtual = rcc::Register::makeVirtual((std::uint64_t{1} << 31) - 1);
+  Context.expect(FirstVirtual && LastVirtual,
+                 "the complete virtual register index domain must be accepted");
+  if (FirstVirtual) {
+    Context.expect(FirstVirtual->isVirtual(), "virtual Register must preserve its category");
+    Context.expect(FirstVirtual->virtualIndex() == 0, "virtual Register must preserve index zero");
+    Context.expect(FirstVirtual->toString() == "%0",
+                   "virtual Register spelling must match MIR numbering");
+  }
+  Context.expect(!rcc::Register::makeVirtual(std::uint64_t{1} << 31),
+                 "out-of-range virtual register indices must be rejected");
+}
+
+void testStableIDs(TestContext &Context) {
+  static_assert(!std::is_same_v<rcc::MachineFunctionStableID, rcc::MachineBlockStableID>);
+  static_assert(!std::is_same_v<rcc::MachineBlockStableID, rcc::MachineInstrStableID>);
+  static_assert(!std::is_copy_constructible_v<rcc::StableIDGenerator<rcc::MachineInstrStableID>>);
+
+  const rcc::MachineInstrStableID Invalid;
+  Context.expect(!Invalid.isValid(), "zero StableID must be invalid");
+
+  rcc::StableIDGenerator<rcc::MachineInstrStableID> Generator;
+  auto First = Generator.allocate();
+  auto Second = Generator.allocate();
+  Context.expect(First && Second, "StableID generator must allocate IDs");
+  if (First && Second) {
+    Context.expect(First->value() == 1 && Second->value() == 2,
+                   "StableID generator must allocate monotonically");
+    Context.expect(*First != *Second, "StableID generator must not reuse live IDs");
+  }
+}
+
+void testMachineFunctionProperties(TestContext &Context) {
+  using enum rcc::MachineFunctionProperty;
+
+  rcc::MachineFunctionProperties Properties{IsSSA, TracksLiveness};
+  Context.expect(Properties.count() == 2, "property set must count active properties");
+  Context.expect(Properties.has(IsSSA), "property set must retain IsSSA");
+  Context.expect(Properties.toString() == "IsSSA, TracksLiveness",
+                 "property spelling must have deterministic enum order");
+
+  const auto Original = Properties;
+  auto MissingRequired =
+      Properties.applyTransition(rcc::MachineFunctionProperties{Legalized},
+                                 rcc::MachineFunctionProperties{RegBankSelected}, {});
+  Context.expect(!MissingRequired, "property transition must reject missing requirements");
+  Context.expect(Properties == Original, "failed property transition must be atomic");
+  if (!MissingRequired) {
+    Context.expect(MissingRequired.error().code() == rcc::ErrorCode::VerificationError,
+                   "missing property requirements must be verification errors");
+  }
+
+  auto ConflictingTransition = Properties.applyTransition(
+      {}, rcc::MachineFunctionProperties{Selected}, rcc::MachineFunctionProperties{Selected});
+  Context.expect(!ConflictingTransition,
+                 "property transition must reject overlapping sets and clears");
+  Context.expect(Properties == Original, "conflicting property transition must be atomic");
+
+  auto ValidTransition = Properties.applyTransition(rcc::MachineFunctionProperties{IsSSA},
+                                                    rcc::MachineFunctionProperties{NoPHIs},
+                                                    rcc::MachineFunctionProperties{IsSSA});
+  Context.expect(ValidTransition.has_value(), "valid property transition must succeed");
+  Context.expect(Properties.has(NoPHIs) && !Properties.has(IsSSA),
+                 "valid property transition must apply sets and clears together");
+
+  auto RawRoundTrip = rcc::MachineFunctionProperties::fromRaw(Properties.rawValue());
+  Context.expect(RawRoundTrip && *RawRoundTrip == Properties,
+                 "known property masks must round-trip");
+  Context.expect(!rcc::MachineFunctionProperties::fromRaw(std::uint64_t{1} << 63),
+                 "unknown property bits must be rejected");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testLowLevelTypes(Context);
+  testRegisters(Context);
+  testStableIDs(Context);
+  testMachineFunctionProperties(Context);
+  return Context.result();
+}