4 files changed, 546 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