3 files changed, 558 insertions, 0 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