[CodeGen] Add machine IR value semantics

Add strongly typed machine indices, lane masks, instruction flags, fixed-point branch probabilities, and preserved-register masks.

Model immutable machine memory operands with explicit base identity, size, alignment, address space, alias information, and validated atomic operation and ordering rules. Cover normal, boundary, and invalid combinations in standalone tests.

4 files changed, 306 insertions, 0 deletions

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