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